Théorie

Scoring/Approche statistique

lundi 24 avril 2006 par ClarK

A ce stade, nous disposons déjà d’une base de données contenant les tokens, avec leur nombre d’occurrences, provenant des pages traitées lors de l’apprentissage.

Une page au contenu inconnu peut alors être tokenisée à son tour. Chaque token trouvé dans cette page est alors recherché dans la base d’apprentissage afin de calculer la probabilité qu’elle soit classée comme interdite sachant qu’elle contient ce token.

La méthode statistique mise en oeuvre dans le projet est tirée des calculs utilisés dans les logiciels de détection de Spam. Elle est basée sur des calculs bayésiens et se divise en quatre étapes :

le calcul de probabilités individuelles,
l’altération de ces probabilités,
La combinaison de toutes les probabilités individuelles,
Le calcul d’un indicateur global sur la page.

Probabilités individuelles

Pour chaque constituant de la page tokenisée (balises, domaines, mots et bi-mots) il est tout d’abord nécessaire de calculer leurs probabilités individuelles. Un token est cette fois comptabilisé autant de fois qu’il apparaît dans une page. Pour ce faire nous nous basons sur les valeurs (occurrences) stockées en base d’apprentissage. Pour chaque token qui apparaît dans la page nous calculons :

b(w) (b comme “bad” et w comme “word”) qui représente le nombre de pages interdites contenant le mot “w” (noté Card(B|wεB)) divisé par le nombre total de pages interdites (Card(B)).

Proportion d’occurrences interdites d’un mot
g(w) (g comme “good”) qui représente le nombre de pages autorisées contenant le mot “w” (noté Card(G|wεG)) divisé par le nombre total de pages autorisées (Card(G)).

Proportion d’occurrences autorisées d’un mot
p(w) qui peut être interprété comme la probabilité qu’une page choisie aléatoirement et contenant le mot “w” soit une page interdite.

Probabilité individuelle

Ces probabilités obtenues pour chaque token présent dans la page peuvent ensuite être combinées pour attribuer un score et ainsi catégoriser la page en question.

On peut cependant noter un problème dans ce calcul. En effet lors de l’apprentissage tous les mots pouvant exister (de n’importe quelle langue) n’ont pas forcément été rencontrés plusieurs où même une seule fois. Il en va de même pour les balises HTML et leur contenu ; il est impossible d’en avoir une liste exhaustive suite à l’apprentissage étant donnée l’étendue des possibilités offertes (ne serait-ce que sur le choix d’une couleur).
Ainsi pour un token n’ayant été rencontré qu’une seule fois lors de l’apprentissage ce calcul donne trop d’importance à la probabilité individuelle correspondante.

Exemple 1 :
Pour simplifier les choses nous dirons que nous avons autant de pages interdites et autorisées en apprentissage ce qui donne le calcul de probabilité individuelle :

Probabilité individuelle simplifiée

Admettons maintenant que nous voulons calculer la probabilité relative à un token, trouvé dans une page que l’on désire catégoriser, et que celui-ci n’est apparu qu’une seule fois lors de l’apprentissage dans une page interdite.
On obtiendra donc : p(w)=1/(1+0)=1

Exemple 2 :
Prenons un token ayant 10 occurrences interdites et 1 autorisée.
On aura : p(w)=(10)/(10+1)=0.91

Or notre expérience nous montre que la première probabilité ne peut être de 1, nous ne pouvons pas être certains que ce mot désigne une page interdite, nous manquons seulement de données à son sujet. De même pour le deuxième exemple.
Il nous faut donc trouver un moyen d’altérer ces probabilités afin de diminuer la force qui leur est attribuée.

Altération

La méthode suivante permet de prendre en compte les mots rares c’est à dire ceux n’apparaissant pas souvent, voir jamais, lors de l’apprentissage.
Cette méthode nous est fournie par les statistiques bayésiennes qui permettent de traiter ce genre de cas avec efficacité. Le principe est d’attribuer un degré de confiance à un évènement donné.
Ceci nous permet d’ajouter notre expérience aux données et valeurs collectées lors de l’apprentissage.
Nous calculons ce degré de confiance basé sur le calcul précédent de p(w) comme suit :

Probabilité individuelle avec altération

s est la force donnée à notre expérience
x est la probabilité assumée qu’un mot que l’on ne connaît pas appartienne à la catégorie interdite
n est le nombre de pages contenant le token w

Pour commencer ces valeurs sont initialisées à 1 pour s et 0.5 pour x. Il faudra ensuite les modifier en testant plusieurs pages pour tenter d’optimiser les résultats.
Maintenant nous utiliserons f(w) plutôt que p(w) car ce dernier ne donne pas des résultats réalistes prenant en compte notre expérience.

Reprenons les exemples précédents avec s=4 et x=0.45 :
Exemple 1 :f(w)=((4×0.45)+(1×1))/(4+1)=0.56 et non plus 1
Exemple 2 :f(w)=((4×0.45)+(11×0.95))/(4+11)=0.79 et non plus 0.91

La force donnée à un mot rare est donc maintenant beaucoup plus faible. L’exemple 1 qui avait avant une probabilité plus forte que l’exemple 2 est maintenant plus faible comme cela doit l’être réellement aux vues de notre expérience.

Explications

Afin d’expliquer ce calcul prenons pour exemple le jeu de pile ou face. Il y a n lancers effectués, chaque lancer est un essai et nous comptabilisons le nombre de face obtenu. Il s’agit d’un test suivant une loi binomiale (il y a deux valeurs, pile et face), de plus chaque lancer est indépendant.
On peut ainsi calculer la probabilité que le n+unième lancer donne une face par le calcul suivant :

Loi binomiale

q est le nombre de succès (nombre de fois où l’on a obtenu ’face’)
n est le nombre de lancers
u et v sont les paramètres de la loi binomiale (ici et dans la supposition que la pièce n’est pas biaisée u=v=0.5)

On peut maintenant rapporter ce calcul au cas nous concernant. Lors de la recherche de la probabilité individuelle d’un token, nous réalisons un essai indépendant des autres (le fait qu’une page contienne le mot ’porn’ n’est pas corrélé au fait que la prochaine le contienne également), pouvant avoir deux issues (autorisée ou interdite). Nous sommes donc dans le même cas que le lancer de pièce et la probabilité qu’une page contenant un token donné appartienne à la catégorie interdite suit une loi binomiale.

Si on pose, dans l’équation précédente :

u = s × x
v = s × (1 - x)
q = n × p(w)

On retrouve alors :

Probabilité individuelle avec altération

En essayant avec s = 1 et x = 0.5 (les paramètres de départ) on obtient les paramètres de la loi binomiale : u = v = 0.5.
Donc nos paramètres de départ ont été choisis en faisant l’hypothèse d’équiprobabilité des évènements (un token inconnu a autant de chance d’appartenir à une page autorisée qu’à une page interdite).

Avec le calcul de f(w) plutôt que p(w) nos résultats devraient être plus précis.

Il est maintenant temps de combiner les différentes probabilités afin d’obtenir un score global de la page.

Combinaisons de probabilités

Nous sommes donc maintenant capables de calculer les probabilités individuelles de chaque token rencontré dans une page, basées sur notre expérience et sur les données stockées en base.
Chaque page peut être alors représentée par un ensemble de probabilités. Il nous faut combiner cet ensemble de probabilités afin de produire un indicateur correct du contenu de la page.

Reprenons l’exemple du lancer de pièce.
Si nous partons avec l’hypothèse de départ que cette pièce n’est pas biaisée, et lançons 10 fois la pièce et obtenons 10 fois face, la probabilité globale sera de (1/ 2)¹⁰ = 1/1024 . Ce serait un événement très peu probable en prenant en compte l’hypothèse de départ.
Mais en rejetant cette hypothèse de départ et à la place prendre celle qui dit que la pièce est biaisée, alors ce résultat deviendrait normal.

Une méthode a été écrite par R.A. Fisher (1932), qui, appliquée à notre modèle permet de tirer le même genre de conclusion, en l’occurrence de rejeter ou valider une hypothèse de départ.

Notre hypothèse de départ est : "les probabilités individuelles sont précises, et les pages pour lesquelles ont attribue les scores sont une collection aléatoire de tokens, indépendants les uns par rapport aux autres, tels que ces probabilités suivent une loi uniforme."

La méthode de combinaison de Fisher permet de combiner les probabilités de n études indépendantes. Les n probabilités p₁ ,p₂ ,..., p_n représentent un échantillon indépendant de la loi binomiale.
Il est noter que dans le cas de non indépendance des probabilités individuelles, la méthode de Ficher conduit à des obtenir de grandes valeurs qui nous permettent de rejeter notre hypothèse de départ.

Les étapes du calcul sont :

tout d’abord calculer -2lnΠp-(i)
puis considérer que le résultat obtenu suit une distribution du Chi² avec 2n degrés de liberté,
enfin utiliser une table du Chi² afin d’obtenir la probabilité combinée,
Cette probabilité est censée résumer toutes les probabilités individuelles.

Dans notre cas les n études indépendantes sont les n tokens récupérés dans la page pour laquelle on désire attribuer un score.

La formule globale est :

Fonction de combinaison des probabilités individuelles de Fisher

Où C-^-1 est la fonction de du Chi² inverse.
Le cas où les probabilités individuelles sont dépendantes nous donne des résultats élevés nous intéresse particulièrement. En effet on cherche à rejeter notre hypothèse de départ car on sait très bien qu’une page Web n’est pas une collection aléatoire de tokens. L’ensemble des tokens d’une page Web a un sens et ils sont donc dépendants les uns des autres.

Un score proche de 0 nous permettra donc de rejeter notre hypothèse de départ et à la place prendre celle qui dit que la page à laquelle on attribue un score appartient à la catégorie autorisée.
Un score proche de 1, au contraire, nous fera choisir l’hypothèse de départ selon laquelle la page appartient à la catégorie interdite.

Indicateur global pour la page

Le résultat précédent nous pose cependant problème dans le sens où la combinaison présente une faiblesse. En effet dans ce calcul du produit des logarithmes les valeurs faibles (proches de 0) apporteront plus de poids dans le résultat final que les valeurs proches de 1 (dans un produit de valeurs comprises entre 0 et 1 les valeurs proches de 0 font tendre celui-ci vers 0 plus rapidement que les valeurs proches de 1 ne le font tendre vers 1).

Sachant que la méthode de combinaison de Fisher est basé sur un produit de valeurs on en déduit que les pages appartenant à la catégorie autorisée sont avantagées par ce calcul.

Cependant, il a des moyens de gérer ce problème qui n’apporte pas de tendance à mal classifier les pages autorisées en interdites.

La méthode la plus efficace est la suivante :

Inverser les probabilités individuelles en les soustrayant à la valeur 1, soit calculer, pour chaque tokenf, 1-f(w-). Comme les f(w) représentent la probabilité qu’une page prise aléatoirement parmi l’ensemble des pages contenant le mot w soit une page interdite, 1-f(w) est la probabilité qu’une telle page soit autorisée.
Effectuer la même combinaison de Fisher que celle vue précédemment mais cette fois en combinant les 1-f(w). Cette combinaison est appelée S :

S = C-^-1 (—2lnΠ-(1 — f(w)),2n)
Enfin calculer :

Indicateur global de la page

I est un indicateur qui sera proche de 1 quand la majorité des probabilités sera en faveur de la conclusion que la page est interdite et sera proche de 0 dans le cas contraire (page autorisée).

A ce point et afin d’améliorer les résultats pour qu’ils soient réellement proches de 0 ou de 1, le meilleur moyen est de supprimer, lors de la combinaison des probabilités individuelles, celles à faible déviation, c’est-à-dire qui font tendre le résultat vers 0.5. Ces probabilités sont 28 principalement dues à des tokens non présents en base d’apprentissage et ils sont extrêmement nombreux ce qui peut fausser les calculs. La déviation peut être bien évidemment réglée et 0.4 (les probabilités comprises entre 0.4 et 0.6 seront supprimées du calcul final) semble être un bon point de départ.