Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
public:algo-txt:statistiques_sur_les_lettres [2015/11/12 11:54] – [Probabilité conditionnelle] edauce | public:algo-txt:statistiques_sur_les_lettres [2016/03/14 09:43] (Version actuelle) – [Comparer les langues] edauce | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ===== Statistiques sur les lettres ===== | ||
+ | |||
+ | Soit un document $d$ : | ||
+ | * constitué de $T$ symboles $d[1]$, …, $d[i]$, …. | ||
+ | * appartenant à l' | ||
+ | |||
+ | ==== Modèles probabilistes ==== | ||
+ | |||
+ | Les modèles probabilistes interprètent les données de type texte comme étant générées par une distribution de probabilité $P$ inconnue. | ||
+ | |||
+ | La distribution $P$ définit le langage utilisé dans le texte. On ne s' | ||
+ | |||
+ | ==== Fréquence d'un symbole ==== | ||
+ | |||
+ | Soit $\alpha \in A$ un symbole de l' | ||
+ | $$P(X=\alpha) = \frac{|\omega \in \Omega : X=\alpha|}{|\Omega|}$$ | ||
+ | où $\Omega$ représente l' | ||
+ | |||
+ | On a par définition~: | ||
+ | $$\sum_{\alpha \in V} P(X=\alpha) = 1$$ | ||
+ | |||
+ | La fréquence empirique du symbole $\alpha$ dans le document $d$ | ||
+ | est donnée par~: | ||
+ | <note important> | ||
+ | $$f_d(\alpha) = \frac{|\{i: | ||
+ | </ | ||
+ | où |d| est le nombre de caractères dans le document. | ||
+ | |||
+ | <note tip> | ||
+ | **Fréquence des lettres en français** | ||
+ | {{http:// | ||
+ | </ | ||
+ | |||
+ | * Voir aussi : {{https:// | ||
+ | |||
+ | === Représentation vectorielle === | ||
+ | |||
+ | On suppose que les caractères d'un langage $\mathcal{L}$ donné sont numérotés de 1 à $K$, soit $A_\mathcal{L} = \{\alpha_1, | ||
+ | |||
+ | On notera $\boldsymbol{p}_\mathcal{L}$ le vecteur des fréquences des caractères dans un langage $\mathcal{L}$ donné, où $p_\mathcal{L}(k)$ donne la fréquence du $k^{ème}$ caractère. | ||
+ | |||
+ | < | ||
+ | **Exemple**: | ||
+ | $$\boldsymbol{p}_\text{Français} = (0.0942, 0.0102, 0.0264, | ||
+ | où | ||
+ | * $p_1 = 0.0942$ est la fréquence de la lettre ' | ||
+ | * $p_2 = 0.0102$ est la fréquence d' | ||
+ | * etc. | ||
+ | </ | ||
+ | avec bien sûr : | ||
+ | $$\sum_{k\in\{1, | ||
+ | |||
+ | ==== Probabilité jointe ==== | ||
+ | |||
+ | On s' | ||
+ | |||
+ | Soient $\alpha$ et $\beta$ deux symboles de l' | ||
+ | |||
+ | La probabilité jointe est définie comme : | ||
+ | $$P(X=\alpha, | ||
+ | où $\Xi$ est l' | ||
+ | |||
+ | <note tip> | ||
+ | {{public: | ||
+ | </ | ||
+ | |||
+ | avec par définition: | ||
+ | $$\sum_{(\alpha, | ||
+ | |||
+ | La **probabilité jointe empirique** est donnée par~: | ||
+ | <note important> | ||
+ | $$f_d(\alpha, | ||
+ | </ | ||
+ | * Les séquences de deux caractères sont classiquement appelées des // | ||
+ | * On définit de même les // | ||
+ | * etc. | ||
+ | |||
+ | |||
+ | === Représentation matricielle === | ||
+ | |||
+ | On notera $\boldsymbol{P}_\mathcal{L}$ la matrice des fréquences des bigrammes dans un langage $\mathcal{L}$ donné, où $P_{ij}$ donne la fréquence du bigramme $(\alpha_i, | ||
+ | |||
+ | < | ||
+ | **Exemple**: | ||
+ | $$\boldsymbol{P}_\text{Français} = 10^{-5} \times \left( | ||
+ | \begin{array}{cccc} | ||
+ | 1.5 & 116.8 & 199.1 & ...\\ | ||
+ | 62.8 & 1.6 & 0.14 & ...\\ | ||
+ | 184.8 & 0 & 52.4 & ...\\ | ||
+ | & | ||
+ | \end{array} | ||
+ | \right)$$ | ||
+ | |||
+ | |||
+ | où | ||
+ | * $P_{11} = 1.5 \times 10^{-5}$ est la fréquence du bigramme ' | ||
+ | * $P_{12} = 116.8 \times 10^{-5}$ est la fréquence d' | ||
+ | * etc. | ||
+ | </ | ||
+ | |||
+ | avec bien sûr : | ||
+ | $$\sum_{(i, | ||
+ | |||
+ | <note tip> | ||
+ | voir {{http:// | ||
+ | </ | ||
+ | |||
+ | ====Corpus de documents==== | ||
+ | Soit $B$ un corpus de documents, constitué de $n$ documents. | ||
+ | < | ||
+ | La fréquence empirique du symbole $\alpha$ dans le corpus $B$ | ||
+ | est donnée par~: | ||
+ | $$f_B(\alpha) = \frac{|\{(i, | ||
+ | où |B| est le nombre total de caractères dans le corpus. | ||
+ | |||
+ | La fréquence jointe du couple $(\alpha, | ||
+ | $$f_B(\alpha, | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | ==== Probabilité conditionnelle==== | ||
+ | |||
+ | La **probabilité conditionnelle** du caractère $\beta$ étant donné le caractère précédent $\alpha$ est définie comme : | ||
+ | |||
+ | $$P(Y = \beta | X=\alpha) = \frac{|\xi \in \Xi : (X, | ||
+ | |||
+ | <note tip> | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | </ | ||
+ | |||
+ | qui se calcule empiriquement comme : | ||
+ | |||
+ | $$f_d(\beta|\alpha) = \frac{|\{i: | ||
+ | |||
+ | < | ||
+ | * La probabilité $P(.|\alpha_i)$ se représente sous forme vectorielle~: | ||
+ | |||
+ | * L' | ||
+ | $$ | ||
+ | \begin{array}{cl} | ||
+ | M &= \left( | ||
+ | \begin{array}{c} | ||
+ | \boldsymbol{\mu}_1\\ | ||
+ | \boldsymbol{\mu}_2\\ | ||
+ | ... | ||
+ | \end{array} | ||
+ | \right) | ||
+ | \\ | ||
+ | & | ||
+ | \begin{array}{cccc} | ||
+ | P(\alpha_1|\alpha_1)& | ||
+ | P(\alpha_1|\alpha_2)& | ||
+ | & | ||
+ | \end{array} | ||
+ | \right) | ||
+ | \end{array} | ||
+ | $$ | ||
+ | |||
+ | </ | ||
+ | |||
+ | Sachant que $P(\alpha) = \sum_{\beta \in A} P(\alpha, \beta)$, on a : | ||
+ | $$\boldsymbol{\mu}_i = \frac{P_{i,: | ||
+ | |||
+ | Soit en français : | ||
+ | |||
+ | < | ||
+ | $$ | ||
+ | M_\text{Français} = \left( | ||
+ | \begin{array}{cccc} | ||
+ | 0.0016 & 0.0124 & 0.0211 & ...\\ | ||
+ | 0.0615 & 0.0016 & 0.0001 & ...\\ | ||
+ | 0.0700 & 0.0000 & 0.0198 & ...\\ | ||
+ | & ... &&& | ||
+ | \end{array} | ||
+ | \right) | ||
+ | $$ | ||
+ | où : | ||
+ | * $M_{11}$ est la probabilité de voir un ' | ||
+ | * $M_{12}$ est la probabilité de voir un ' | ||
+ | * etc. | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | La matrice des probabilités conditionnelles $M$ permet de définir un **modèle génératif** de langage inspiré des **processus aléatoires de Markov**: | ||
+ | * La production d'un mot ou d'un texte est modélisée comme un parcours aléatoire sur une chaîne de Markov définie par la matrice de transitions $M$. | ||
+ | * La fréquence d' | ||
+ | |||
+ | < | ||
+ | {{public: | ||
+ | </ | ||
+ | |||
+ | </ | ||
+ | |||
+ | ==== Comparer les langues | ||
+ | |||
+ | On considère deux langues $\mathcal{L}_1$ et $\mathcal{L}_2$ utilisant le même alphabet. | ||
+ | La différence de fréquence des caractères dans ces deux langages permet de les distinguer. | ||
+ | il est ainsi possible de définir une distance entre deux langages basée sur la distance | ||
+ | Euclidienne entre les vecteurs de fréquence empirique des caractères dans les deux langages. | ||
+ | |||
+ | Une autre approche consiste à utiliser la //théorie de l' | ||
+ | |||
+ | L’information apportée par la lecture du symbole $\alpha$ est définie comme : | ||
+ | $$I(\alpha) = -\log_2(P(X = \alpha)) $$ | ||
+ | où $p_\alpha = P(X = \alpha)$ est la fréquence d’apparition de ce symbole dans la langue considérée. | ||
+ | |||
+ | Si le symbole $\alpha$ est “rare” ($p_\alpha$ petit), l’information qu’il apporte est élevée. Si le symbole | ||
+ | |||
+ | L’entropie d’un langage est définie comme l' | ||
+ | $$H(\mathcal{L}) = E_X(I(\alpha)) = -E_X(\log_2(P(X = \alpha)) $$ | ||
+ | i.e. | ||
+ | $$H(\mathcal{L}) = - \sum_{k \in \{1, | ||
+ | |||
+ | L’entropie représente l’ “imprévisibilité” d'une production de symboles. Une entropie faible indique que la séquence est très prévisible, | ||
+ | |||
+ | Pour comparer deux langues $\mathcal{L}_1 et \mathcal{L}_2$, | ||
+ | |||
+ | $$D(\mathcal{L}_1||\mathcal{L}_2) = \sum_{k \in \{1, | ||
+ | |||
+ | où $P_1$ désigne la distribution des symboles du langage $\mathcal{L}_1$ et $P_2$ la distribution des symboles du langage $\mathcal{L}_2$. | ||
+ | |||
+ | La divergence de K-L représente l' | ||