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] t. q. t\in \mathcal{A} 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 tien compte du label précédant, le mot schroumpf précédé d'un déterminant est utilisé dans 2 cas sur 2 en tant que nom, 1 cas sur 3 en tant que nom s'il est précédé d'un adverbe … Il nous faut trouver un modèle permettant de calculer ces probabilités en fonction du contexte.

pour commencer on peu 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é. 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.