PhD

The LaTeX sources of my Ph.D. thesis
git clone https://esimon.eu/repos/PhD.git
Log | Files | Refs | README | LICENSE

graph.tex (8418B)


      1 \section{Modélisation à l'aide de graphes de la structure des jeux de données}
      2 \label{sec:french:graph}
      3 Comme mentionné dans la Section~\ref{sec:french:context}, les approches récentes utilisent une définition plus souple des relations en extrayant une fonction de similarité au lieu d'un classifieur.
      4 De plus, elles considèrent un contexte plus large : au lieu de traiter chaque phrase individuellement, la cohérence globale des relations extraites est prise en compte.
      5 Cependant, ce deuxième type d'approches a principalement été appliqué au cadre supervisé, avec une utilisation plus limitée dans le cadre non supervisé.
      6 Notre deuxième contribution concerne l'utilisation de ce contexte plus large pour l'extraction non supervisée de relations.
      7 En particulier, nous établissons des parallèles avec le test d'isomorphisme de Weisfeiler--Leman pour concevoir de nouvelles méthodes utilisant conjointement des caractéristiques topologiques (au niveau des jeux de données) et linguistiques (au niveau des phrases).
      8 
      9 Nous encodons le problème d'extraction de relations comme un problème d'étiquetage d'un multigraphe \(G=(\entitySet, \arcSet, \gfendpoints, \gfrelation, \gfsentence)\) défini comme suit:
     10 \begin{itemize}[nosep]
     11 	\item \(\entitySet\) est l'ensemble des nœuds qui correspondent aux entités.
     12     \item \(\arcSet\) est l'ensemble des arcs qui connectent deux entités.
     13     \item \(\gfsource: \arcSet\to \entitySet\) associe à chaque arc son nœud d'origine (l'entité marquée \(e_1\)),
     14     \item \(\gftarget: \arcSet\to \entitySet\) associe à chaque arc son nœud de destination (l'entité marquée \(e_2\)),
     15     \item \(\gfsentence: \arcSet\to \sentenceSet\) associe à chaque arc \(a\in \arcSet\) la phrase correspondante contenant \(\gfsource(a)\) et \(\gftarget(a)\),
     16 	\item \(\gfrelation: \arcSet\to \relationSet\) associe à chaque arc \(a\in\arcSet\) la relation entre les deux entités véhiculée par \(\gfsentence(a)\).
     17 \end{itemize}
     18 Étant donné un chemin dans ce graphe:
     19 \begin{center}
     20 	\input{mainmatter/graph/3-path.tex}
     21 \end{center}
     22 nous avons conçu un algorithme de comptage basé sur l'exponentiation de la matrice d'adjacence de \(G\) et sur un échantillonnage préférentiel%
     23 \sidenote{\emph{importance sampling}}
     24 qui nous permet d'approcher l'information mutuelle \(\operatorname{I}(\rndm{r}_2; \rndm{r}_1, \rndm{r}_3) \approx 6\mathord{,}95\ \text{bits}\).
     25 Elle se décompose en une entropie conditionnelle \(\entropy(\rndm{r}_2\mid\rndm{r}_1,\rndm{r}_3)\approx 1\mathord{,}06\ \text{bits}\) soustrait à l'entropie croisée%
     26 \sidenote{\emph{cross-entropy}}
     27 \(\expectation_{r_1, r_3}[\entropy_{P(\rndm{r}_2)}(\rndm{r}_2\mid r_1, r_3)]\approx 8\mathord{,}01\ \text{bits}\).
     28 Cela signifie que la majeure partie de l'information relationnelle est extractible à partir du voisinage dans le graphe \(G\).
     29 
     30 \begin{marginfigure}[-92mm]
     31 	\centering
     32 	\input{mainmatter/graph/isomorphism.tex}
     33 	\scaption[Exemple de graphes isomorphes.]{
     34 		Exemple de graphes isomorphes.
     35 		Chaque nœud \(i\) dans le graphe de gauche correspond à la \(i\)-ième lettre de l'alphabet dans le graphe de gauche.
     36 		Par ailleurs, ces graphes contiennent des automorphismes nontriviaux, par exemple en associant le nœud \(i\) au nœud \(9-i\).
     37 		\label{fig:french:isomorphism}
     38 	}
     39 \end{marginfigure}
     40 
     41 Fort de cette observation, nous utilisons l'hypothèse suivante pour concevoir un nouveau paradigme pour l'extraction non supervisée de relations:
     42 \begin{spacedblock}
     43 	\strong{Hypothèse distributionnelle faible sur le graphe d'extraction de relations.}
     44 	\emph{Deux arcs véhiculent des relations similaires s'ils ont des voisinages similaires.}
     45 \end{spacedblock}
     46 
     47 \begin{marginfigure}
     48 	\centering
     49 	\input{mainmatter/context/bert.tex}
     50 	\scaption[Schéma de \textsc{bert}, un modèle de langue masqué basé sur un \emph{transformer}.]{
     51 		Schéma de \textsc{bert} \parencite{bert}, un modèle de langue masqué basé sur un \emph{transformer}.
     52 		Le modèle est entrainé à reconstruire des mots \(\hat{w}_t\) corrompus en \(\tilde{w}_t\) (plongés en \(\tilde{\vctr{x}}_t\)).
     53 		\bertcoder{} est une spécialisation de ce modèle pour l'extraction de relations \parencite{mtb}.
     54 		\label{fig:french:bert}
     55 	}
     56 \end{marginfigure}
     57 \begin{marginparagraph}
     58 	\Textcite{gcn_spectral_semi} ont déjà tracé un parallèle entre \textsc{wl} et les approches à base de réseaux neuronaux convolutifs pour graphes (\textsc{gcn}).
     59 	Toutefois, nous avançons que les fonctions d'apprentissage habituellement utilisées pour les \textsc{gcn} ne sont pas adaptées au problème d'extraction non supervisée de relations.
     60 \end{marginparagraph}
     61 
     62 Pour exploiter cette information de voisinage présente dans la topologie du multigraphe \(G\), nous proposons de nous inspirer du test d'isomorphisme de Weisfeiler--Leman (\textsc{wl}, \cite{weisfeiler-leman}).
     63 Deux graphes sont dits isomorphes s'il existe un morphisme entre leur sommets qui conserve la relation de voisinage.
     64 Ce concept est illustré par la Figure~\ref{fig:french:isomorphism}.
     65 Nous pouvons donc traduire l'hypothèse ci-dessus par l'affirmation que si les voisinages de deux échantillons sont isomorphes, alors ces deux échantillons véhiculent la même relation.
     66 Pour évaluer la proximité de deux voisinages, nous définissons \(\symfrak{S}_\gfnright(a, k)\), le plongement par \bertcoder{} (voir Figure~\ref{fig:french:bert}) de la sphère de rayon \(k\) autour de l'arête \(a\in\arcSet\) comme:
     67 \begin{align*}
     68 	S_\gfnright(a, 0) & = \{\,a\,\} \\
     69 	S_\gfnright(a, k) & = \{\,x\in\arcSet \mid \exists y\in S_\gfnright(a, k-1): \gfsource(x)=\gftarget(y)\,\} \\
     70 	\symfrak{S}_\gfnright(a, k) & = \{\,\bertcoder(\gfsentence(x))\in\symbb{R}^d \mid x\in S_\gfnright(a, k)\,\}.
     71 \end{align*}
     72 Ces sphères correspondent au voisinage à distance \(k\).
     73 À partir de celles-ci, nous pouvons définir une fonction de distance prenant en compte le voisinage jusqu'à une distance \(K\):
     74 \begin{equation*}
     75 	d(a, a'; \vctr{\lambda}) =
     76 		\sum_{k=0}^K \frac{\lambda_k}{2}
     77 			\sum_{o\in\{\gfoleft, \gforight\}}
     78 				W_1\left(\symfrak{S}_o(a, k), \symfrak{S}_o(a', k)\right),
     79 \end{equation*}
     80 où \(W_1\) désigne la distance de Wasserstein d'ordre 1.
     81 En particulier, cette fonction évaluée en \(\vctr{\lambda}=[1]\) correspond à la distance habituelle entre plongements de phrases modulo l'utilisation de \(W_1\) à la place d'une distance cosinus.
     82 Pour des raisons de limites de calcul, nous fixons \(K=2\).
     83 Dans ce cas, \(d(a_1, a_2, [1, 0]\transpose)\) correspond à la distance linguistique entre deux échantillons \(a_1, a_2\in\arcSet\), tandis que \(d(a_1, a_2, [0, 1]\transpose)\) correspond à la distance topologique entre les voisinages des échantillons \(a_1\) et \(a_2\).
     84 Nous proposons de faire coïncider ces deux distances pour tirer parti de l'information mutuelle au voisinage et à la phrase afin d'identifier la sémantique relationnelle des échantillons.
     85 Pour ce faire, nous introduisons une fonction de coût par triplet:%
     86 \sidenote{\emph{triplet loss}}
     87 \begin{equation*}
     88 	\loss{lt}(a_1, a_2, a_3) = \max\left(
     89 	\begin{aligned}
     90 		0, \zeta &
     91 		  + 2 \big(d(a_1, a_2, [1, 0]\transpose) - d(a_1, a_2, [0, 1]\transpose)\big)^2 \\
     92 		& \hspace{5mm} - \big(d(a_1, a_2, [1, 0]\transpose) - d(a_1, a_3, [0, 1]\transpose)\big)^2 \\
     93 		& \hspace{5mm} - \big(d(a_1, a_3, [1, 0]\transpose) - d(a_1, a_2, [0, 1]\transpose)\big)^2
     94 	\end{aligned}
     95 	 \right).
     96 \end{equation*}
     97 \begin{margintable}
     98 	\centering
     99 	\input{backmatter/french/graph quantitative.tex}
    100 	\scaption[Résultats quantitatifs des méthodes à base de graphe sur le jeu de données FewRel.]{
    101 		Résultats quantitatifs des méthodes à base de graphe sur le jeu de données FewRel \parencite{fewrel}.
    102 		Ces résultats portent uniquement sur les échantillons de FewRel connectés par au moins une arête dans le graphe \(G\) du jeu de données \textsc{t-re}x.
    103 	}
    104 	\label{tab:french:graph quantitative}
    105 \end{margintable}
    106 
    107 Des résultats préliminaires sur l'utilisation d'informations topologiques sont donnés dans la Table~\ref{tab:french:graph quantitative}.
    108 Comme on pouvait s'y attendre, l'information relationnelle encodée dans le voisinage d'ordre 1 du graphe est moindre que celle directement contenue dans la phrase.
    109 Toutefois, ces informations peuvent être combinées ce qui permet d'améliorer significativement la performance du modèle d'extraction de relation.