Exemple de calcul de part of speech

Dans cette explication, je me base sur l'algorithme expliqué ici :

• [1] A Simple Introduction to Maximum Entropy Models for Natural Language Processing de Adwait Ratnaparkhi qui explique l'algorithme.
• [2] Exploitation d'une ressource lexicale pour la construction d'un étiqueteur morphosyntaxique état-de-l'art du français de P. Denis et B. Sagot qui montrent la démarche pour le français.

Supposons que le corpus est 5 phrases qui contiennent le mot schtroumpf:

1. Un schtroumpf vert, c'est la jaunisse.
2. Mais c’est très schtroumpf, ça !
3. Tu te promènes toujours le schtroumpf en lair.
4. Certains parlent plus schtroumpf que les autres.
5. Il est complètement schtroumpf.

Dans les exemples 1,3 et 4 c'est un nom commun, dans les exemples 2 et 5 un adjectif. On peut donc dire d'après ce corpus que si on ne considère que le mot schtroumpf :

• c'est un nom dans 3 cas sur 5 = 60%
• c'est un adjectif dans 2 cas sur 5 = 40%

Mais comment trouver cela automatiquement ?

On souhaite calculer la probabilité observé d'un label par rapport à un context en fonction du jeu d'exemple. Il faut tout d'abord choisir le context h. Par exemple : le tag avant, le mot considéré. Pour simplifier ici, on ne va regarder que le cas du mot schtroumpf :

• dans la phrase Un schtroumpf vert, c'est la jaunisse. le contexte est $h_1 = (DET, 'schtroumpf')$.
• dans la phrase Mais c’est très schtroumpf, ça ! le contexte est $h_2 = (ADV, 'schtroumpf')$
• dans la phrase Tu te promènes toujours le schtroumpf en l'air le contexte $h_3 = (DET, 'schtroumpf')$
• dans la phrase Certains parlent plus schtroumpf que les autres. le contexte est $h_4=(ADV, 'schtroumpf')$
• dans la phrase Il est complètement schtroumpf. le contexte est $h_5=(ADV, 'schtroumpf')$.

Ici, il y a 2 contextes différents observés :

• le mot 'schtroumpf' précédé d'un déterminant ($h_1, h_3$)
• le mot 'schtroumpf' précédé d'un adverbe ($h_2, h_4, h_5$)

L'ensemble des classes possibles est $\mathcal{A} = \{NOM, ADJ\}$. Donc l'ensemble des évènements possibles est $\epsilon = \mathcal{A}\times \mathcal{B} = \{x = [t, h] \mbox{ t.q. } t\in\mathcal{A} \mbox{ et } h \in \mathcal{B}\}$. Cet ensemble à 4 élément : \begin{eqnarray*}

x_1 & = & \left[ t:NOM, h:(DET, 'schtroumpf')\right]\\
x_2 & = & \left[ t:NOM, h:(ADV, 'schtroumpf')\right]\\
x_3 & = & \left[ t:ADJ, h:(DET, 'schtroumpf')\right]\\
x_4 & = & \left[ t:ADJ, h:(ADV, 'schtroumpf')\right]\\

\end{eqnarray*}

On peut voir que le mot 'schtroumpf' est utilisé dans 3 cas sur 5 en tant que nom et dans 2 cas sur 5 en tant qu'adjectif. Mais si on tient compte du label précédant, le mot schtroumpf précédé d'un déterminant est utilisé dans 2 cas sur 2 en tant que nom et jamais en tant qu'adjectif. S'il est précédé d'un adverbe, il est utilisé dans 1 cas sur 3 en tant que nom… Il nous faut trouver un modèle permettant de calculer ces probabilités en fonction du contexte.

pour commencer on peut facilement calculer la fréquence de chaque evennement dans le jeu d'exemple : \begin{eqnarray*} \bar{p}(x_1) & = & \frac{2}{5}
\bar{p}(x_2) & = & \frac{1}{5}
\bar{p}(x_3) & = & \frac{0}{5}
\bar{p}(x_4) & = & \frac{2}{5}
\end{eqnarray*}

Pour savoir ce que l'on va considérer dans l'apprentissage, il faut définir des features (nom utilisé par [1]) ou traits ([2]). Ici, pour commencer nous ne regarderons que le mot lui même. Cela donne 2 traits : \begin{eqnarray*} f_{NOM} (t,h) & = & \left\{\begin{array}{l} 1 \mbox{ si } h = (*,\mbox{'schtroumpf'}) \mbox{ et } t = NOM
0 \mbox{ sinon} \end{array}\right.
f_{ADJ} (t,h) & = & \left\{\begin{array}{l} 1 \mbox{ si } h = (*,\mbox{'schtroumpf'}) \mbox{ et } t = ADJ
0 \mbox{ sinon} \end{array}\right. \end{eqnarray*}

Ces traits ne tiennent compte que du mot lui même (sans utiliser d'information sur le mot qui le précède). Donc 'schtroumpf' est un nom dans 3 cas sur 2 et on devrait trouver que \begin{eqnarray*} p(NOM|(*,\mbox{sctroumpf},*)) & = & 0.6
p(ADJ|*,\mbox{sctroumpf},*) & = & 0.4
\end{eqnarray*}

Si on calcul l'espérence observée de chaque feature : \begin{eqnarray*} \hat{E}f_{NOM} & = & \sum_{x \in \epsilon} \bar{p}(x)f_{NOM}(x)
& = & \frac{2}{5}\times 1 + \frac{1}{5} \times 1 + \frac{0}{5} \times 0 + \frac{2}{5} \times 0
& = & \frac{3}{5}
& = & 0.6
\hat{E}f_{ADJ} & = & \sum_{x \in \epsilon} \bar{p}(x)f_{ADJ}(x)
& = & 0.4
\end{eqnarray*}

On souhaite maintenant obtenir un modèle de probabilité qui donne le même résultat sous la forme : \begin{eqnarray*} p(x) & = & \pi \prod_i \left(\alpha_i\right)^{f_i(x)} \end{eqnarray*}

\begin{eqnarray*} p(x_1) & = &\pi \times \left((\alpha_{NOM})^1\right)\times\left((\alpha_{ADJ})^0\right)
& = & \pi\alpha_{NOM}
p(x_2) & = &\pi \times \left((\alpha_{NOM})^1\right)\times\left((\alpha_{ADJ})^0\right)
& = & \pi\alpha_{NOM}
p(x_3) & = & \pi \times\left((\alpha_{NOM})^0\right)\times\left((\alpha_{ADJ})^1\right)
& = & \pi\alpha_{ADJ}
p(x_4) & = & \pi \times\left((\alpha_{NOM})^0\right)\times\left((\alpha_{ADJ})^1\right)
& = & \pi\alpha_{ADJ}
\end{eqnarray*}

C'est à dire que l’événement ne dépent que des traits (les $f_i$) et de coéfficients qui leur sont associés. Attention, le paramètre $\pi$ est une normalisation, sachant que $p(x_1) + p(x_2)+p(x_3)+p(x_4) = 1$, il faut que $\pi = \frac{1}{2(\alpha_{NOM}+\alpha_{ADJ})}$.

Il faut trouver les paramètres afin que $\forall i$ : \begin{eqnarray*} \hat{E}f_i & = & Ef_i & = & \sum_{x \in \epsilon}p(x)f_i(x) \end{eqnarray*}

Pour cela on va utiliser l'algorithme de GIS.

Dans [1] chapitre 7 on demande de vérifier que $\forall x \in \epsilon$, $\displaystyle \sum_{j=1}^k f(x) = C$ où $C$ est une constante. Dans notre cas, c'est facile car le mot est soit un nom soit un adjectif (donc $C = 1$).

Pour trouver un modèle où $\forall i$ : $Ef_i = \hat{E}f_i$, on utilise une méthode itérative : \begin{eqnarray*} \alpha_{NOM}^0 & = & 1
\alpha_{ADJ}^0 & = & 1
\pi^0 & = & 0.25
\alpha_i^{n+1} & = & \alpha_j^n \times \left(\frac{\hat{E}f_i}{E^nf_i}\right)^{\frac{1}{C}}
\end{eqnarray*}

À la première itération de l'algorithme $p^0(x_1) = p^0(x_2) = p^0(x_3) = p^0(x_4) = 0.25$ donc \begin{eqnarray*} E^0f_{NOM} & = & 0.25+0.25+0+0

              & = & 0.5\\

E^0f_{ADJ} & = & 0.5
\alpha^1_{NOM} & = & 1 \times \left(\frac{0.6}{0.5}\right)^1
& = & 1.2
\alpha^1_{ADJ} & = & 1 \times \left(\frac{0.4}{0.5}\right)^1
& = & 0.8
\pi^1 & = & 0.25
\end{eqnarray*}

Donc on a $p^1(x_1) = p^1(x_2) = 0.3$ et $p^1(x_3) = p^1(x_4) = 0.2$ et \begin{eqnarray*} E^1f_{NOM} & = & 0.3+0.3+0+0

              & = & 0.6\\

E^1f_{ADJ} & = & 0.4
\end{eqnarray*} Et l'algorithme s’arrête.

L'intéret de la méthode est qu'il suffit d'ajouter des traits et de relancer la méthode pour modifier l'apprentissage. Par exemple, on peut supposer que le label précédant le mot est important, cela conduit à ajouter 2 traits : \begin{eqnarray*} f_{DET+NOM}(t, h) & = & \left\{ \begin{array}{rl} 1 & \mbox{si } h = (DET, *) \mbox{ et } t = NOM
0 & \mbox{sinon} \end{array} \right.
f_{DET+ADJ}(t, h) & = & \left\{ \begin{array}{rl} 1 & \mbox{si } h = (DET, *) \mbox{ et } t = ADJ
0 & \mbox{sinon} \end{array} \right.
f_{ADV+NOM}(t, h) & = & \left\{ \begin{array}{rl} 1 & \mbox{si } h = (ADV, *) \mbox{ et } t = NOM
0 & \mbox{sinon} \end{array} \right.
f_{ADV+ADJ}(t, h) & = & \left\{ \begin{array}{rl} 1 & \mbox{si } h = (ADV, *) \mbox{ et } t = ADJ
0 & \mbox{sinon} \end{array} \right. \end{eqnarray*}

Alors les valeurs observées : \begin{eqnarray*} \hat{E}f_{NOM} & = & 0.6
\hat{E}f_{ADJ} & = & 0.4
\hat{E}f_{DET+NOM} & = & \frac{2}{5}\times 1 + \frac{1}{5}\times 0 + \frac{0}{5}\times 0 + \frac{2}{5} \times 0

                      & = & 0.4\\

\hat{E}f_{ADV+NOM} & = & \frac{2}{5}\times 0 + \frac{1}{5}\times 1 + \frac{0}{5}\times 0 + \frac{2}{5} \times 0

                      & = & 0.2\\

\hat{E}f_{DET+ADJ} & = & \frac{2}{5}\times 0 + \frac{1}{5}\times 0 + \frac{0}{5}\times 1 + \frac{2}{5} \times 0

                      & = & 0\\

\hat{E}f_{ADV+ADJ} & = & \frac{2}{5}\times 0 + \frac{1}{5}\times 0 + \frac{0}{5}\times 0 + \frac{2}{5} \times 1

                      & = & 0.4\\

\end{eqnarray*}

Si on considère le modèle : \begin{eqnarray*} p(x_1) & = &\pi \times (\alpha_{NOM})^1\times(\alpha_{ADJ})^0\times(\alpha_{DET+NOM})^1\times(\alpha_{ADV+NOM})^0\times(\alpha_{DET+ADJ})^0\times(\alpha_{ADV+ADJ})^0
& = & \pi\alpha_{NOM}\alpha_{DET+NOM}
p(x_2) & = &\pi \times (\alpha_{NOM})^1\times(\alpha_{ADJ})^0\times(\alpha_{DET+NOM})^0\times(\alpha_{ADV+NOM})^1\times(\alpha_{DET+ADJ})^0\times(\alpha_{ADV+ADJ})^0
& = & \pi\alpha_{NOM}\alpha_{ADV+NOM}
p(x_3) & = &\pi \times (\alpha_{NOM})^0\times(\alpha_{ADJ})^1\times(\alpha_{DET+NOM})^0\times(\alpha_{ADV+NOM})^0\times(\alpha_{DET+ADJ})^1\times(\alpha_{ADV+ADJ})^0
& = & \pi\alpha_{ADJ}\alpha_{DET+ADJ}
p(x_4) & = &\pi \times (\alpha_{NOM})^0\times(\alpha_{ADJ})^1\times(\alpha_{DET+NOM})^0\times(\alpha_{ADV+NOM})^0\times(\alpha_{DET+ADJ})^0\times(\alpha_{ADV+ADJ})^1
& = & \pi\alpha_{ADJ}\alpha_{ADV+ADJ}
\pi & = & \frac{1}{\alpha_{NOM}\alpha_{DET+NOM}+\alpha_{NOM}\alpha_{ADV+NOM}+\alpha_{ADJ}\alpha_{DET+ADJ}+\alpha_{ADJ}\alpha_{ADV+ADJ}} \end{eqnarray*}

On vérifie bien qu'il existe une constante $C$ telle que $\forall x \in \epsilon$, $\displaystyle \sum f_i(x) = C$. C'est la cas avec $C=2$ car dans tout les exemples 2 traits sont actifs (le mot peut être un nom ou un adjectif, le mot peut être un nom précédé d'un article ou précédé d'un adverbe, ou un adjectif précédé d'un adverbe).

Si on lance l'algorithme avec $C=2$ : $$ \begin{array}{rl} \alpha_{NOM} & = \quad \alpha_{ADJ} \quad = \quad \alpha_{DET+NOM}
& = \quad \alpha_{ADV+NOM} \quad = \quad \alpha_{ADV+NOM} \quad = \quad \alpha_{ADV+ADJ} \quad = \quad 1
\pi & = \quad 0.25
p^0(x_1) & = \quad p^0(x_2) \quad = \quad p^0(x_3) \quad = \quad p^0(x_4) \quad = \quad 0.25
E^0f_{NOM} & = \quad 0.25 + 0.25 + 0 + 0 \quad = \quad 0.5
E^0f_{ADJ} & = \quad 0.5
E^0f_{DET+NOM} & = \quad 0.25
E^0f_{ADV+NOM} & = \quad 0.25
E^0f_{DET+ADJ} & = \quad 0.25
E^0f_{ADV+ADJ} & = \quad 0.25
\alpha^1_{NOM} & = \quad 1 \times \sqrt{\frac{0.6}{0.5}}
& = \quad 1.095
\alpha^1_{ADJ} & = \quad 0.894
\alpha^1_{DET+NOM} & = \quad 1.265
\alpha^1_{ADV+NOM} & = \quad 0.894
\alpha^1_{DET+ADJ} & = \quad 0 \mbox{ Attention dans ce calcul } \frac{\hat{E}f}{Ef}= \frac{0}{0} = 1
\alpha^1_{ADV+ADV} & = \quad 1.264
\pi & = \quad 3.497
p^1(x_1) & = \quad 0.396
p^1(x_2) & = \quad 0.280
p^1(x_3) & = \quad 0
p^1(x_4) & = \quad 0.324
…
p^{17}(x_1) & = \quad 0.3999986
p^{17}(x_2) & = \quad 0.2000014
p^{17}(x_3) & = \quad 0.0000000
p^{17}(x_4) & = \quad 0.4000000
Ef^{17}_{NOM} & = \quad 0.6000000
Ef^{17}_{ADJ} & = \quad 0.4000000
Ef^{17}_{DET+NOM} & = \quad 0.3999986
Ef^{17}_{ADV+NOM} & = \quad 0.2000014
Ef^{17}_{DET+ADJ} & = \quad 0.0000000
Ef^{17}_{ADV+ADJ} & = \quad 0.4000000
\alpha^{17}_{NOM} & = \quad 1.0326433
\alpha^{17}_{ADJ} & = \quad 0.9931238
\alpha^{17}_{DET+NOM} & = \quad 1.3507368
\alpha^{17}_{ADV+NOM} & = \quad 0.6753720
\alpha^{17}_{DET+ADJ} & = \quad 0.0000000
\alpha^{17}_{ADV+ADJ} & = \quad 1.4044892 \end{array} $$