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édenteDernière révisionLes deux révisions suivantes | ||
tc_info:2020_cm_textes [2023/11/29 17:12] – [1 Données texte] edauce | tc_info:2020_cm_textes [2023/11/30 00:09] – [5. Modèles génératifs] edauce | ||
---|---|---|---|
Ligne 75: | Ligne 75: | ||
</ | </ | ||
* On peut inversement afficher le caractère à partir de son code entier : | * On peut inversement afficher le caractère à partir de son code entier : | ||
- | < | + | < |
int code1 = 233; | int code1 = 233; | ||
int code2 = 119070; | int code2 = 119070; | ||
Ligne 89: | Ligne 89: | ||
=== 1.3 Codage des mots et du texte === | === 1.3 Codage des mots et du texte === | ||
Chaîne de caractère : | Chaîne de caractère : | ||
- | < | + | < |
- | s = " | + | String |
</ | </ | ||
* '' | * '' | ||
Ligne 96: | Ligne 96: | ||
* " | * " | ||
* assimilable à un tableau de caractère : | * assimilable à un tableau de caractère : | ||
- | < | + | < |
- | for c in s : | + | for (char c : s.toCharArray()) { |
- | | + | |
+ | } | ||
</ | </ | ||
Affiche : | Affiche : | ||
Ligne 136: | Ligne 137: | ||
* Il existe une fonction '' | * Il existe une fonction '' | ||
* Exemple : | * Exemple : | ||
- | < | + | < |
- | s = 'paul.poitevin@centrale-marseille.fr' | + | String |
- | b = s.encode() | + | |
+ | // Encodage de la chaîne en bytes en utilisant UTF-8 | ||
+ | byte[] | ||
+ | |||
+ | // Affichage des bytes encodés | ||
+ | for (byte byteValue : b) { | ||
+ | System.out.print(byteValue + " "); | ||
+ | } | ||
</ | </ | ||
+ | |||
+ | ce qui affiche: | ||
+ | < | ||
+ | 112 97 117 108 46 112 111 105 116 101 118 105 110 64 99 101 110 116 114 97 108 101 45 109 97 114 115 101 105 108 108 101 46 102 114 | ||
+ | </ | ||
+ | |||
Un nombre en base 256 est difficile à lire et interpréter. On le traduit en base 10 : | Un nombre en base 256 est difficile à lire et interpréter. On le traduit en base 10 : | ||
- | < | + | < |
- | i = int.from_bytes(b, byteorder=' | + | // Conversion des bytes en BigInteger |
- | print("i =", i) | + | BigInteger bigInteger |
+ | |||
+ | // Affichage du résultat | ||
+ | System.out.println("i = " | ||
</ | </ | ||
Ce qui donne : | Ce qui donne : | ||
Ligne 230: | Ligne 247: | ||
Cette approche a un inconvénient : après une comparaison infructueuse, | Cette approche a un inconvénient : après une comparaison infructueuse, | ||
- | ** Algorithme de Knuth-Morris-Pratt | + | ** Algorithme de Boyer-Moore ** |
- | L' | + | L' |
* On suppose qu'on peut tester si un caractère '' | * On suppose qu'on peut tester si un caractère '' | ||
* Le but est de calculer un décalage permettant de ne pas inspecter les positions où il n'y a aucune chance de trouver le motif '' | * Le but est de calculer un décalage permettant de ne pas inspecter les positions où il n'y a aucune chance de trouver le motif '' | ||
* On commence par chercher la position '' | * On commence par chercher la position '' | ||
- | * On inspecte la chaîne | + | * Soit '' |
- | * Soit '' | + | * Si '' |
- | * On note '' | + | * Sinon on note '' |
- | * Le décalage est égal à '' | + | * si '' |
- | * Si on ne trouve rien (ou si le décalage vaut 0), le décalage vaut '' | + | * Sinon le décalage est égal à '' |
<note tip> | <note tip> | ||
Ligne 252: | Ligne 269: | ||
CHINE | CHINE | ||
CHINE | CHINE | ||
- | CHINE | + | |
- | | + | |
- | CHINE | + | |
CHINE | CHINE | ||
RECHERCHE DE CHAINES CODEES EN MACHINE | RECHERCHE DE CHAINES CODEES EN MACHINE | ||
</ | </ | ||
- | < | ||
- | Algo : recherche améliorée (Knuth-Morris-Pratt) | ||
- | Données : d, t : chaînes de caractères | ||
- | Début: | ||
- | n = len (d) | ||
- | m = len (t) | ||
- | i <-- m - 1 | ||
- | tant que i < n : | ||
- | # PRE-TRAITEMENT | ||
- | j <-- 0 | ||
- | tant que j < m - 1: | ||
- | c = d[i - j] | ||
- | si c appartient à t[:m-j-1] | ||
- | k <-- dernière_occurrence(c, | ||
- | | ||
- | break | ||
- | sinon | ||
- | j += 1 | ||
- | si j == m - 1 ou si décalage == 0: | ||
- | | ||
- | # TRAITEMENT | ||
- | j <-- 0 | ||
- | tant que j < m : | ||
- | si t[m - j - 1] = d[i - j] | ||
- | j += 1 | ||
- | sinon | ||
- | break | ||
- | si j = m: | ||
- | retourner i - m + 1 | ||
- | # DECALAGE | ||
- | i <-- i + decalage | ||
- | retourner -1 | ||
- | Fin | ||
- | </ | ||
- | |||
=== 2.2 Compter les mots === | === 2.2 Compter les mots === | ||
Ligne 445: | Ligne 426: | ||
* Les classes d' | * Les classes d' | ||
* En python, les expressions régulières s' | * En python, les expressions régulières s' | ||
+ | * Les expressions régulières (regex) servent à décrire des motifs complexes à chercher (" | ||
+ | |||
Traduction de l' | Traduction de l' | ||
Ligne 455: | Ligne 438: | ||
* reconnaître une expression arithmétique | * reconnaître une expression arithmétique | ||
* vérifier la syntaxe d'un code informatique | * vérifier la syntaxe d'un code informatique | ||
- | |||
- | |||
=== Syntaxe des expressions régulières Python === | === Syntaxe des expressions régulières Python === | ||
Ligne 495: | Ligne 476: | ||
accepte tous les mots de 3 lettres | accepte tous les mots de 3 lettres | ||
- | **Branchements et Récursion** | + | **Branchements et itération** |
* Les parenthèses permettent : | * Les parenthèses permettent : | ||
* de factoriser une expression (qui peut alors être traitée comme une transition) | * de factoriser une expression (qui peut alors être traitée comme une transition) | ||
* '' | * '' | ||
- | * de définir des branchements : | + | * de définir des branchements |
* '' | * '' | ||
Ligne 506: | Ligne 487: | ||
* ''?'' | * ''?'' | ||
+ | <note tip> ** Récapitulatif ** | ||
+ | |||
+ | 1. **Caractères littéraux :** | ||
+ | * Les caractères alphabétiques et numériques sont traités littéralement. Par exemple, le motif ''" | ||
+ | |||
+ | 2. **Caractères spéciaux :** | ||
+ | * Certains caractères ont une signification spéciale dans une expression régulière et doivent être échappés s'ils doivent être traités littéralement. Ces caractères spéciaux incluent '' | ||
+ | |||
+ | 3. **Classes de caractères :** | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | 4. **Caractères génériques :** | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | 5. **Quantificateurs :** | ||
+ | * '' | ||
+ | * '' | ||
+ | * ''?'' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | 6. **Ancrages :** | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | 7. **Groupes et Alternatives :** | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | 8. **Échappement :** | ||
+ | * '' | ||
+ | |||
+ | </ | ||
==exemples== | ==exemples== | ||
Ligne 535: | Ligne 558: | ||
* début de mot : '' | * début de mot : '' | ||
* complétions possibles : '' | * complétions possibles : '' | ||
+ | |||
+ | ** Autre exemple:** | ||
+ | {{https:// | ||
==== 4 Comparaison/ | ==== 4 Comparaison/ | ||
On cherche à exprimer une distance entre deux chaînes de caractères. | On cherche à exprimer une distance entre deux chaînes de caractères. | ||
Ligne 659: | Ligne 685: | ||
{{: | {{: | ||
+ | |||
+ | ===== 5. Modèles génératifs ===== | ||
+ | |||
+ | Soit un document $d$ : | ||
+ | * constitué de $T$ symboles $d[1]$, …, $d[i]$, …. | ||
+ | * appartenant à l' | ||
+ | |||
+ | |||
+ | Une description statistique d’un texte correspond à un histogramme qui porte sur un ensemble de symboles : | ||
+ | |||
+ | {{: | ||
+ | |||
+ | <note tip> | ||
+ | Modèles probabiliste : la suite de symbole observés (le message) est générée par un processus aléatoire: | ||
+ | $d = (d_1, d_2, ..., d_T$) | ||
+ | * chaque $d_i$ est la réalisation d'un tirage aléatoire | ||
+ | * obéissant à une distribution de probabilité $p$ | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | Les symboles sont au choix : | ||
+ | * des caractères appartenant à un alphabet | ||
+ | * des termes appartenant à un vocabulaire | ||
+ | </ | ||
+ | |||
+ | === 5.1 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' | ||
+ | |||
+ | On a par définition~: | ||
+ | $$\sum_{\alpha \in V} P(X=\alpha) = 1$$ | ||
+ | |||
+ | |||
+ | < | ||
+ | **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. | ||
+ | </ | ||
+ | |||
+ | |||
+ | === Probabilité jointe === | ||
+ | |||
+ | On s' | ||
+ | |||
+ | Soient $\alpha$ et $\beta$ deux symboles de l' | ||
+ | |||
+ | < | ||
+ | * Les séquences de deux caractères sont classiquement appelées des // | ||
+ | * On définit de même les // | ||
+ | * etc. | ||
+ | </ | ||
+ | |||
+ | 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:// | ||
+ | </ | ||
+ | |||
+ | 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: | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | 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: | ||
+ | </ | ||
+ | |||
+ | </ | ||
+ | |||
+ | On peutétendre ce principe à la distribution des mots dans les textes, ce qui permet de produire des //modèles génératifs de langage//. | ||
+ | |||
+ | * Exemple : le pseudo latin (" | ||
+ | * Exemple de pseudo-français (Utilisant une trace (mémoire) de 1 mot): | ||
+ | <note tip> | ||
+ | //j'ai vu parfois des yeux, remonter vers toi bien fatiguée! n'est pas un appel de la terre– je hume à coups mutins les voiles la blafarde lumière puisée au delà les vieux flacon débouché rien ne puis la pourriture les forêts ou bien que vénus par des choses dans les forts des senteurs confondues de ma chère, prêtre orgueilleux danse amoureusement l' | ||
+ | </ | ||
+ | |||
+ | === 5.2 Espaces de plongement (Word embedding) === | ||
+ | Le plongement des mots (word embedding) | ||
+ | * est une technique en traitement automatique du langage naturel (TALN) | ||
+ | * qui consiste à représenter les mots **sous forme de vecteurs de nombres réels dans un espace vectoriel**. | ||
+ | * L' | ||
+ | * de projeter les mots dans cet espace vectoriel | ||
+ | * où la proximité spatiale entre les vecteurs reflète la sémantique des mots. | ||
+ | |||
+ | <note tip> | ||
+ | Largement utilisés dans diverses tâches de traitement du langage naturel: | ||
+ | - classification de texte, | ||
+ | - la traduction automatique, | ||
+ | - l' | ||
+ | - la recherche d' | ||
+ | </ | ||
+ | |||
+ | **Word2Vec** est un algorithme d' | ||
+ | |||
+ | * L' | ||
+ | * Word2Vec utilise des modèles de **prédictions** pour apprendre des représentations vectorielles en analysant les contextes d' | ||
+ | |||
+ | Il existe deux architectures principales de Word2Vec : Skip-Gram et CBOW | ||
+ | |||
+ | === 1. Skip-Gram === | ||
+ | Dans l' | ||
+ | |||
+ | \[ \max \sum_{t=1}^{T} \sum_{-c \leq j \leq c, j \neq 0} \log P(w_{t+j} \mid w_t) \] | ||
+ | |||
+ | où \(T\) est la taille du corpus, \(w_t\) est le mot central, \(w_{t+j}\) est le mot contexte, et \(c\) est la taille de la fenêtre contextuelle. | ||
+ | |||
+ | === 2. CBOW (Continuous Bag of Words) === | ||
+ | Dans l' | ||
+ | |||
+ | \[ \max \sum_{t=1}^{T} \log P(w_t \mid w_{t-c}, \ldots, w_{t-1}, w_{t+1}, \ldots, w_{t+c}) \] | ||
+ | |||
+ | où \(T\) est la taille du corpus, \(w_t\) est le mot central, et \(w_{t-i}\) sont les mots contextuels dans la fenêtre de contexte. | ||
+ | |||
+ | === Fonctionnement Général === | ||
+ | Le processus d' | ||
+ | |||
+ | Une fois l' | ||
+ | |||
+ | Word2Vec a été révolutionnaire en raison de sa capacité à apprendre des représentations de mots utiles à partir de grands volumes de texte non annoté, et ses embeddings sont souvent utilisés comme points de départ pour de nombreuses tâches de traitement du langage naturel (NLP) et d' | ||