Comment l'hypothèse de Naive Bayes rend-elle la segmentation moins exigeante en termes de calcul ?

Question

J'ai regardé une vidéo du cours d'introduction à l'IA d'Udacity et je n'arrive pas à me faire une idée.

Il est dit que pour une chaîne de longueur n 2 n-1 des segmentations sont possibles. Lorsque nous prenons l'hypothèse de Naive Bayes, la meilleure segmentation s * peut être défini comme celui qui maximise

produit(P(w _i ))

Il est possible d'écrire le meilleur comme :

s * \= argmax _s P(premier_mot) * s * (reste_des_mots)

Je comprends pourquoi ce qui précède est vrai. L'instructeur a dit qu'en raison de l'équation ci-dessus, nous n'avons pas besoin d'énumérer tous les 2 n-1 cas. Je ne parviens pas à en comprendre la raison.

Je comprends aussi que trouver P(single_word) est plus simple que d'apprendre la même prob pour les n-grammes et cela aiderait aussi au niveau du calcul.

Answer 1

Comme nous travaillons avec des mots uniques, nous devons choisir un seul mot à la fois et non pas toutes leurs combinaisons, ce qui réduit l'espace de recherche. Considérons la chaîne de caractères :

"Iliketennis"

La chaîne comporte 11 caractères, donc 2^11=2048 cas. Si nous commençons à regarder le premier mot le plus probable, cela pourrait être :

"I", "Il", "Ili", "Ilik" et ainsi de suite. 11 cas possibles. Maintenant que nous avons tous les premiers mots possibles, nous cherchons le plus probable :

• P("I")=0,4,
• P("Il")=0.0001,
• P("Ili")=0.002,
• P("Ilik")=0.00003
• ...

et ainsi de suite.

En découvrant que le plus probable est "I", nous le prenons comme premier mot et maintenant nous pouvons nous concentrer sur les 10 caractères/cas restants :

"liketennis"

En répétant le même processus, vous aurez maintenant 10 cas possibles pour le mot, avec une probabilité :

• P("l")=0,05,
• P("lI")=0,0001,
• P("lik")=0.0002,
• P("lik")=0.00003
• P("like")=0,3
• ...

et ainsi de suite.

Nous choisissons donc "like". Maintenant la recherche est répétée pour les 6 derniers caractères. Sans réécrire le processus, "tennis" est récupéré et il ne reste plus de caractères, la segmentation est donc terminée.

Puisque nous avons fait une analyse par mots, les possibilités que nous avons envisagées sont les suivantes

11+10+6=27

beaucoup moins que de couvrir les 2048 divisions possibles.

Answer 2

Je vous suggère une vidéo de Mathematicalmonk, cette vidéo : https://youtu.be/qX7n53NWYI4?t=9m43s

Il explique que sans l'hypothèse d'indépendance conditionnelle (Naive Bayes), il faut beaucoup plus d'échantillons pour estimer les probabilités lorsque l'on apprend à partir de données. Mais si vous supposez (même si c'est incorrect) l'indépendance entre les caractéristiques, vous pouvez estimer la distribution de probabilité avec moins de données d'apprentissage.

Pourquoi ? Faisons simple, sans hypothèse naïve, la probabilité d'un vecteur de caractéristiques à 2 dimensions pour une prédiction y serait :

En supposant que seules des valeurs binaires pour x_1 y x_2 vous devez stocker ces valeurs par y appris à partir d'un échantillon de données :

P(x_1=0|y), P(x_1=1|y), P(x_2=0|x_1=0,y), P(x_2=0|x_1=1,y), P(x_2=1|x_1=0,y), P(x_2=1|x_1=1,y)

En d'autres termes, vous devez stocker paramètres. Vous pouvez le généraliser à un vecteur de caractéristiques binaires à d dimensions :

Si vous prenez l'hypothèse naïve et supposez que ces caractéristiques sont indépendantes, vous obtiendrez cette formule :

ce qui signifie que vous ne devez stocker ces paramètres que par y afin de prédire toutes les possibilités X :

P(x_1=0|y), P(x_1=1|y), P(x_2=0|y), P(x_2=1|y)

Ou de le généraliser :