Dans Naive Bayes, pourquoi s'embêter avec le lissage de Laplace alors que nous avons des mots inconnus dans le test?

28

Je lisais aujourd'hui la classification Naive Bayes. J'ai lu, sous le titre d' estimation des paramètres avec l'ajout de 1 lissage :

Soit référence à une classe (telle que positive ou négative), et référence à un jeton ou à un mot. $c$ $w$

L'estimateur du maximum de vraisemblance pour est $P(w|c)$
$\frac{c o u n t (w, c)}{c o u n t (c)} = \frac{compte w dans la classe c}{nombre de mots dans la classe c} .$ $\frac{count(w,c)}{count(c)} = \frac{\text{counts w in class c}}{\text{counts of words in class c}}.$

Cette estimation de pourrait être problématique car elle nous donnerait la probabilité pour les documents avec des mots inconnus. Une façon courante de résoudre ce problème consiste à utiliser le lissage de Laplace. $P(w|c)$ $0$

Soit V l'ensemble des mots de l'ensemble d'apprentissage, ajoutez un nouvel élément (pour inconnu) à l'ensemble des mots. $UNK$

Définissez
$P (w | c) = \frac{compter (w, c) + 1}{compter (c) + | V | + 1},$ $P(w|c)=\frac{\text{count}(w,c) +1}{\text{count}(c) + |V| + 1},$

où fait référence au vocabulaire (les mots de l'ensemble d'apprentissage). $V$

En particulier, tout mot inconnu aura une probabilité
$\frac{1}{compter (c) + | V | + 1} .$ $\frac{1}{\text{count}(c) + |V| + 1}.$

Ma question est la suivante: pourquoi nous embêtons-nous avec ce lissage de Laplace? Si ces mots inconnus que nous rencontrons dans l'ensemble de test ont une probabilité qui est évidemment presque nulle, c'est-à-dire, $\frac{1}{\text{count}(c) + |V| + 1}$ , à quoi bon les inclure dans le modèle? Pourquoi ne pas simplement les ignorer et les supprimer?

machine-learning classification text-mining naive-bayes laplace-smoothing Matt O'Brien
la source

3

Si vous ne le faites pas, toute déclaration que vous rencontrez contenant un mot précédemment invisible aura

p = 0

$p=0$ . Cela signifie qu'un événement impossible s'est produit. Ce qui signifie que votre modèle était incroyablement mauvais. Dans un modèle bayésien approprié, cela ne pourrait jamais se produire, car la probabilité d'un mot inconnu aurait un numérateur donné par l'a priori (peut-être pas 1). Je ne sais donc pas pourquoi cela nécessite le nom de fantaisie «lissage de Laplace».

conjectures

1

De quel texte provenait la lecture?

wordsforthewise

17

Vous avez toujours besoin de cette probabilité de sécurité intrinsèque.

Pour voir pourquoi considérer le pire des cas où aucun des mots de l'échantillon d'apprentissage n'apparaît dans la phrase de test. Dans ce cas, selon votre modèle, nous conclurions que la phrase est impossible mais qu'elle existe clairement créant une contradiction.

Un autre exemple extrême est la phrase test «Alex a rencontré Steve». où "rencontré" apparaît plusieurs fois dans l'exemple de formation, mais "Alex" et "Steve" ne le font pas. Votre modèle conclurait que cette affirmation est très probable, ce qui n'est pas vrai.

Sid
la source

Je déteste ressembler à un crétin complet, mais cela vous dérangerait-il d'élaborer? Comment la suppression de "Alex" et "Steve" modifie-t-elle la probabilité que la déclaration se produise?

Matt O'Brien

2

Si nous supposons l'indépendance des mots P (Alex) P (Steve) P (rencontré) << P (rencontré)

Sid

1

nous pourrions créer un vocabulaire lors de l'apprentissage du modèle sur l'ensemble de données d'apprentissage, alors pourquoi ne pas simplement supprimer tous les nouveaux mots qui n'apparaissent pas dans le vocabulaire lorsque vous faites des prédictions sur l'ensemble de données de test?

avocat

15

Disons que vous avez formé votre classificateur Naive Bayes sur 2 classes, "Ham" et "Spam" (c'est-à-dire qu'il classe les e-mails). Par souci de simplicité, nous supposerons que les probabilités antérieures sont de 50/50.

Maintenant que vous avez un e - mail $(w_1, w_2,...,w_n)$ que vos taux de classificateur très fortement comme "Ham", dit

P (H une m | w_{1}, w_{2}, . . . w_{n}) = .90

$P(Ham|w_1,w_2,...w_n) = .90$ et

P (S p une m | w_{1}, w_{2}, . . w_{n}) = .dix

$P(Spam|w_1,w_2,..w_n) = .10$

Jusqu'ici tout va bien.

Maintenant que vous avez un e - mail $(w_1, w_2, ...,w_n,w_{n+1})$ qui est exactement le même que l'e - mail ci - dessus , sauf qu'il ya un mot dans ce qui ne figure pas dans le vocabulaire . Par conséquent, comme le compte de ce mot est 0,

P (H une m | w_{n + 1}) = P (S p une m | w_{n + 1}) = 0

$P(Ham|w_{n+1}) = P(Spam|w_{n+1}) = 0$

Soudain,

P (H une m | w_{1}, w_{2}, . . . w_{n}, w_{n + 1}) = P (H une m | w_{1}, w_{2}, . . . w_{n}) * P (H une m | w_{n + 1}) = 0

$P(Ham|w_1,w_2,...w_n,w_{n+1}) = P(Ham|w_1,w_2,...w_n) * P(Ham|w_{n+1}) = 0$ et

P (S p une m | w_{1}, w_{2}, . . w_{n}, w_{n + 1}) = P (S p une m | w_{1}, w_{2}, . . . w_{n}) * P (S p une m | w_{n + 1}) = 0

$P(Spam|w_1,w_2,..w_n,w_{n+1}) = P(Spam|w_1,w_2,...w_n) * P(Spam|w_{n+1}) = 0$

Bien que le 1er e-mail soit fortement classé dans une classe, ce 2e e-mail peut être classé différemment en raison de la probabilité nulle de ce dernier mot.

Le lissage de Laplace résout ce problème en donnant au dernier mot une petite probabilité non nulle pour les deux classes, afin que les probabilités postérieures ne tombent pas soudainement à zéro.

RVC
la source

pourquoi garderions-nous un mot qui n'existe pas du tout dans le vocabulaire? pourquoi ne pas simplement le retirer?

avocat

4

si votre classificateur évalue un e-mail comme étant probablement du jambon, alors p (ham | w1, ..., wn) vaut 0,9, pas p (w1, ..., wn | ham)

braaterAfrikaaner

5

Cette question est assez simple si vous connaissez les estimateurs de Bayes, car c'est la conclusion directe de l'estimateur de Bayes.

Dans l'approche bayésienne, les paramètres sont considérés comme une quantité dont la variation peut être décrite par une distribution de probabilité (ou distribution antérieure).

Donc, si nous considérons la procédure de ramassage comme une distribution multinomiale, nous pouvons résoudre la question en quelques étapes.

Tout d'abord, définissez

m = | V |, n = \sum n_{i}

$m = |V|, n = \sum n_i$

Si nous supposons que la distribution antérieure de $p_i$ est une distribution uniforme, nous pouvons calculer sa distribution de probabilité conditionnelle comme

p (p_{1}, p_{2}, . . ., p_{m} | n_{1}, n_{2}, . . ., n_{m}) = \frac{Γ (n + m)}{\prod_{i = 1}^{m} Γ (n_{i} + 1)} \prod_{i = 1}^{m} p_{i}^{n_{i}}

$p(p_1,p_2,...,p_m|n_1,n_2,...,n_m) = \frac{\Gamma(n+m)}{\prod\limits_{i=1}^{m}\Gamma(n_i+1)}\prod\limits_{i=1}^{m}p_i^{n_i}$

nous pouvons trouver que c'est en fait la distribution de Dirichlet, et l'attente de $p_i$ est

E [p_{i}] = \frac{n_{i} + 1}{n + m}

$E[p_i] = \frac{n_i+1}{n+m}$

Une estimation naturelle de $p_i$ est la moyenne de la distribution postérieure. On peut donc donner l'estimateur de Bayes de $p_i$ :

{\hat{p}}_{i} = E [p_{i}]

$\hat p_i = E[p_i]$

You can see we just draw the same conclusion as Laplace Smoothing.

Response777
la source

4

Disregarding those words is another way to handle it. It corresponds to averaging (integrate out) over all missing variables. So the result is different. How?

Assuming the notation used here:

P (C^{*} | d) = \arg max_{C} \frac{\prod_{i} p (t_{i} | C) P (C)}{P (d)} \propto \arg max_{C} \prod_{i} p (t_{i} | C) P (C)

$P(C^{*}|d) = \arg\max_{C} \frac{\prod_{i}p(t_{i}|C)P(C)}{P(d)} \propto \arg\max_{C} \prod_{i}p(t_{i}|C)P(C)$ where

t_{i}

$t_{i}$ are the tokens in the vocabulary and

d

$d$ is a document.

Let say token $t_{k}$ does not appear. Instead of using a Laplace smoothing (which comes from imposing a Dirichlet prior on the multinomial Bayes), you sum out $t_{k}$ which corresponds to saying: I take a weighted voting over all possibilities for the unknown tokens (having them or not).

P (C^{*} | d) \propto \arg max_{C} \sum_{t_{k}} \prod_{i} p (t_{i} | C) P (C) = \arg max_{C} P (C) \prod_{i \neq k} p (t_{i} | C) \sum_{t_{k}} p (t_{k} | C) = \arg max_{C} P (C) \prod_{i \neq k} p (t_{i} | C)

$P(C^{*}|d) \propto \arg\max_{C} \sum_{t_{k}} \prod_{i}p(t_{i}|C)P(C) = \arg\max_{C} P(C)\prod_{i \neq k}p(t_{i}|C) \sum_{t_{k}} p(t_{k}|C) = \arg\max_{C} P(C)\prod_{i \neq k}p(t_{i}|C)$

But in practice one prefers the smoothing approach. Instead of ignoring those tokens, you assign them a low probability which is like thinking: if I have unknown tokens, it is more unlikely that is the kind of document I'd otherwise think it is.

jpmuc
la source

2

You want to know why we bother with smoothing at all in a Naive Bayes classifier (when we can throw away the unknown features instead).

The answer to your question is: not all words have to be unknown in all classes.

Say there are two classes M and N with features A, B and C, as follows:

M: A=3, B=1, C=0

(In the class M, A appears 3 times and B only once)

N: A=0, B=1, C=3

(In the class N, C appears 3 times and B only once)

Let's see what happens when you throw away features that appear zero times.

A) Throw Away Features That Appear Zero Times In Any Class

If you throw away features A and C because they appear zero times in any of the classes, then you are only left with feature B to classify documents with.

And losing that information is a bad thing as you will see below!

If you're presented with a test document as follows:

B=1, C=3

(It contains B once and C three times)

Now, since you've discarded the features A and B, you won't be able to tell whether the above document belongs to class M or class N.

So, losing any feature information is a bad thing!

B) Throw Away Features That Appear Zero Times In All Classes

Is it possible to get around this problem by discarding only those features that appear zero times in all of the classes?

No, because that would create its own problems!

The following test document illustrates what would happen if we did that:

A=3, B=1, C=1

The probability of M and N would both become zero (because we did not throw away the zero probability of A in class N and the zero probability of C in class M).

C) Don't Throw Anything Away - Use Smoothing Instead

Smoothing allows you to classify both the above documents correctly because:

You do not lose count information in classes where such information is available and
You do not have to contend with zero counts.

Naive Bayes Classifiers In Practice

The Naive Bayes classifier in NLTK used to throw away features that had zero counts in any of the classes.

This used to make it perform poorly when trained using a hard EM procedure (where the classifier is bootstrapped up from very little training data).

Aiaioo Labs
la source

2

@ Aiaioo Labs You failed to realize that he was referring to words that did not appear in the training set at all, for your example, he was referring to say if D appeared, the issue isn't with laplace smoothing on the calculations from the training set rather the test set. Using laplace smoothing on unknown words from the TEST set causes probability to be skewed towards whichever class had the least amount of tokens due to 0 + 1 / 2 + 3 being bigger that 0 + 1 / 3 + 3 (if one of the classes had 3 tokens and the other had 2). ...

2

This can actually turn a correct classification into an incorrect classification if enough unknown words are smoothed into the equation. Laplace smoothing is ok for Training set calculations, but detrimental to test set analysis. Also imagine you have a test set with all unkown words, it should be classified immediately to the class with highest probability, but in fact it can and will usually, not be classified as such, and is usually classified as the class with the lowest amount of tokens.

@DrakeThatcher, highly agree with you, yes if we don't remove words not in vocabulary, then predicted proba will be skewed to class with least amount of words.

avocado

1

J'ai également rencontré le même problème en étudiant Naive Bayes.

Selon moi, chaque fois que nous rencontrons un exemple de test que nous n'avions pas rencontré pendant l'entraînement, la probabilité postérieure deviendra nulle.

Donc, en ajoutant le 1, même si nous ne nous entraînons jamais sur une caractéristique / classe particulière, la probabilité postérieure ne sera jamais 0.

Sarthak Khanna
la source

1

Matt vous avez raison vous soulevez un très bon point - oui Le lissage de Laplace est franchement un non-sens! Le simple fait de jeter ces caractéristiques peut être une approche valable, en particulier lorsque le dénominateur est également un petit nombre - il n'y a tout simplement pas suffisamment de preuves pour étayer l'estimation des probabilités.

J'ai une forte aversion pour résoudre tout problème via l'utilisation de certains ajustements arbitraires. Le problème ici, ce sont les zéros, la "solution" consiste simplement à "ajouter une petite valeur à zéro pour que ce ne soit plus zéro - MAGIQUE, le problème n'est plus". Bien sûr, c'est totalement arbitraire.

Votre suggestion d'une meilleure sélection de fonctionnalités pour commencer est une approche moins arbitraire et IME augmente les performances. De plus, Laplace Smoothing en conjonction avec des Bayes naïfs comme le modèle l'a d'après mon expérience aggrave le problème de granularité - c'est-à-dire le problème où la sortie des scores a tendance à être proche de 1,0 ou 0,0 (si le nombre de caractéristiques est infini, alors chaque score sera 1,0 ou 0,0 - c'est une conséquence de l'hypothèse d'indépendance).

Il existe maintenant d'autres techniques d'estimation des probabilités (autres que la vraisemblance maximale + le lissage de Laplace), mais elles sont massivement sous-documentées. En fait, il existe tout un domaine appelé la logique inductive et les processus d'inférence qui utilisent de nombreux outils de la théorie de l'information.

Ce que nous utilisons dans la pratique est la mise à jour d'entropie croisée minimale, qui est une extension de la mise à jour de Jeffrey où nous définissons la région convexe de l'espace de probabilité cohérente avec la preuve comme étant la région de telle sorte qu'un point dedans signifierait que l'estimation de vraisemblance maximale se situe dans le Déviation absolue attendue du point.

Cela a une belle propriété qui, à mesure que le nombre de points de données diminue, les estimations s'approchent en douceur de l'a priori - et donc leur effet dans le calcul bayésien est nul. Le lissage de Laplace, d'autre part, fait que chaque estimation approche le point d'entropie maximale qui peut ne pas être l'a priori et donc l'effet dans le calcul n'est pas nul et ne fera qu'ajouter du bruit.

samthebest
la source

Dans Naive Bayes, pourquoi s'embêter avec le lissage de Laplace alors que nous avons des mots inconnus dans le test?

Réponses: