Discussion :

[ToTo13]

Bonjour,

J'aurai une question concernant la manipulation des probabilités.

Je souhaite savoir si un objet appartient à une certaine classe C.
Pour cela, j'ai créé N classifieurs (avec différentes méthodes) qui me donnent tous une probabilité Pi que mon objet appartienne à C.
Et là, il me faut prendre une décision finale en fonction de ces probabilités : est ce que mon objet appartient à C.
Quelle est mathématiquement/statistiquement la meilleure (si elle existe) solution pour prendre cette décision ?

- Faire une moyenne ne me semble pas mathématiquement juste, pour la simple raison qu'il faut pour cela commencer par additionner les probabilités. Et ça… ça me choque.
- Considérer chaque probabilité comme un vote est une solution (adoptée pour les forêts aléatoires), mais elle ne vaut le coup que si N est assez grand (rarement mon cas) et impair (pas forcément le cas). De plus, elle ne prend pas en compte la confiance de chaque classifieur : par exemple, si P1=0.4, P2=0.4, P3=1 et P4=1, P1 et P2 ne sont pas sûr d'eux car ils donnent une valeur proche de la frontière de décision (0.5) alors que les deux autres sont sûrs (peut être à tort) d'eux.

Est ce que quelqu'un aurait une idée ?

Merci par avance,

[prgasp77]

Bonjour, est-ce que la distribution suivie par les N classificateur peut être connue ou estimée ? Si oui, tu peux calculer la vraisemblance que ton objet appartienne à C :



où est la v.a. associée au k-ième classificateur et où est le résultat obtenu par le k-ième classificateur pour cet objet.

Note que si tous les valent 1, cette vraisemblance est de 1 ; s'ils sont tous à zéro, elle est de zéro. S'ils sont tous à 1/2, là c'est très variable, mais s'il s'agit de N v.a. gaussiennes, de tête on est à .

Ceci peut éventuellement être amélioré.

[Aleph69]

Bonjour,

- Faire une moyenne ne me semble pas mathématiquement juste, pour la simple raison qu'il faut pour cela commencer par additionner les probabilités. Et ça… ça me choque.

C'est le principe du bagging. Qu'est-ce qui te choque?
As-tu lu l'article de Breiman?

Une autre approche consiste à procéder à un vote majoritaire mais je trouve que c'est dommage vu que tu disposes de classificateurs "soft".

- Considérer chaque probabilité comme un vote est une solution (adoptée pour les forêts aléatoires), mais elle ne vaut le coup que si N est assez grand (rarement mon cas) et impair (pas forcément le cas). De plus, elle ne prend pas en compte la confiance de chaque classifieur : par exemple, si P1=0.4, P2=0.4, P3=1 et P4=1, P1 et P2 ne sont pas sûr d'eux car ils donnent une valeur proche de la frontière de décision (0.5) alors que les deux autres sont sûrs (peut être à tort) d'eux.

La parité de N n'est jamais prise en compte dans les forêts aléatoires. La probabilité d'obtenir autant de votes pour chaque classe diminue rapidement avec le nombre de classificateurs et le nombre de classes.

Pour faire grandir N, il suffit de faire du rééchantillonnage. C'est encore le principe du bagging. C'est ce qui permet de créer de la diversité. Si tu ne connais pas la théorie du méta-apprentissage, tu devrais te renseigner sur le compromis biais-variance-covariance.

Il y a une autre approche, le boosting, et en particulier adaboost, qui permet de spécialiser les classificateurs pour certaines classes. En suivant ce principe, tu répondrais directement à ta question puisque tu saurais par construction quelle degré de confiance donner aux hypothèses données par tes classificateurs.

Je pense que tu commets une erreur de raisonnement lorsque tu écris que P1 et P2 sont moins sûrs que P3 et P4 parce qu'ils donnent des probabilités moins élevées. Il y a différence entre la probabilité d'appartenance d'une classe estimé par un classificateur et la probabilité qu'une hypothèse donnée par ce même classificateur soit fausse. Si tu ne souhaites pas recourir à une heuristique (moyenner, voter majoritairement, etc), tu dois trouver un moyen d'estimer cette dernière probabilité d'une manière ou d'une autre.

Je te donne un exemple très naïf mais qui illustre bien le problème. Disons que tu entraînes N classificateurs sur une base d'apprentissage contenant des données numériques continues et décrite par un faible nombre de variables de manière à éviter le fléau de la dimension. A partir d'une base de test, tu peux estimer les performances de chaque classificateur. En particulier, pour chaque exemple de cette base, tu peux dire si un classificateur fournit une hypothèse correcte ou pas. Plaçons-nous maintenant dans la situation où tu cherches à estimer la classe d'appartenance d'un nouvel exemple. Une manière, encore une fois naïve, de préférer l'hypothèse d'un classificateur en particulier se compose des étapes suivantes :
1. trouver l'exemple e de la base de test le plus proche de l'exemple que l'on souhaite classer;
2. déterminer quelle classificateur c a correctement classé e et avec la plus grande probabilité;
3. classer l'exemple avec l'hypothèse de c.
Tu peux évidemment imaginer plein de variantes de 2. et 3. en manipulant tous les classificateurs qui ont classer correctement e, en pondérant les hypothèses des classificateurs en fonction de leurs hypothèses sur e, etc.

A noter que l'algorithme naïf proposé doit tout de même fournir de bonnes performances. En revanche, je ne suis pas certain qu'il soit significativement meilleur qu'un algorithme de plus proches voisins. Tout dépend de la manière dont tu entraînes tes classificateurs, dont tu crées de la diversité et de la spécificité. Le bagging est connu pour n'être pas performant avec k-NN. L'approche du boosting adaptatif est meilleure de ce point de vue. Les forêts aléatoires s'inspirent du bagging mais leur analyse est beaucoup plus difficile. Il y a des travaux récents là-dessus qui sont menés en France par un jeune docteur dont j'ai oublié le nom mais que je peux retrouver si tu veux.

[ToTo13]

Bonjour et merci pour vos réponses,

Bonjour, est-ce que la distribution suivie par les N classificateur peut être connue ou estimée ?

Non !

C'est le principe du bagging. Qu'est-ce qui te choque?
As-tu lu l'article de Breiman?

Mathématiquement on additionne pas des probas...
Si c'est celui sur les Random Forest, oui. Sinon il en a écrit beaucoup.

Une autre approche consiste à procéder à un vote majoritaire mais je trouve que c'est dommage vu que tu disposes de classificateurs "soft".

Je n'ai JAMAIS dit que mes classifieurs étaient "soft". C'est plutôt le contraire dans la réalité avec des classifieurs qui ont des performances autour de 90% dans la plupart des cas.

La parité de N n'est jamais prise en compte dans les forêts aléatoires. La probabilité d'obtenir autant de votes pour chaque classe diminue rapidement avec le nombre de classificateurs et le nombre de classes.

On est d'accord, mais ce n'était pas vraiment ma principale préoccupation.

Pour faire grandir N, il suffit de faire du rééchantillonnage. C'est encore le principe du bagging. C'est ce qui permet de créer de la diversité.

Je n'en vois pas l'utilité ici, vu que j'ai des déjà des bons classifieurs.

Si tu ne connais pas la théorie du méta-apprentissage, tu devrais te renseigner sur le compromis biais-variance-covariance.

Ok, je vais y jeter un coup d'oeil.

Il y a une autre approche, le boosting, et en particulier adaboost, qui permet de spécialiser les classificateurs pour certaines classes. En suivant ce principe, tu répondrais directement à ta question puisque tu saurais par construction quelle degré de confiance donner aux hypothèses données par tes classificateurs.

Il me semblait qu'Adaboost était spécialisé dans les classifieurs faibles, ce qui n'est pas mon cas.
Par ailleurs, je peux avoir une bonne mesure de confiance de mes classifieurs : je sais qu'elle est leur performance individuelle. C'est je pense la meilleure estimation de leur performance.

Je pense que tu commets une erreur de raisonnement lorsque tu écris que P1 et P2 sont moins sûrs que P3 et P4 parce qu'ils donnent des probabilités moins élevées. Il y a différence entre la probabilité d'appartenance d'une classe estimé par un classificateur et la probabilité qu'une hypothèse donnée par ce même classificateur soit fausse. Si tu ne souhaites pas recourir à une heuristique (moyenner, voter majoritairement, etc), tu dois trouver un moyen d'estimer cette dernière probabilité d'une manière ou d'une autre.

On s'est pas compris.
J'ai dis "moins sûr", car ils donnent une probabilité proche de 0.5 qui est la valeur médiane servant à la décision : P < 0.5 alors n'appartient pas à C, 0.5 <= P appartient à C.
En général, plus un classifieur donne une valeur proche de la valeur de décision, moins il est sûr de lui. En revanche, plus la valeur est extrême (proche de 0 ou 1), plus il est sûr/confiant.

décrite par un faible nombre de variables de manière à éviter le fléau de la dimension.

Tu vas te faire un grand nombre d'ennemis !!!
Car depuis que l'on dispose des Random Forests et des SVM, la plupart des chercheurs mettent tout ce qu'ils peuvent à l'intérieur (souvent de manière stupide et irréfléchie, ça je te l'accorde) et ensuite ils laissent faire le "gros" classifieur.

[davcha]

Perso, j'utiliserais le jeu de données de développement pour estimer la confiance qu'on a en chaque classifieur.

C'est ptet con, ceci dit :p

[ToTo13]

...classifieurs qui ont des performances autour de 90% dans la plupart des cas.
...
Par ailleurs, je peux avoir une bonne mesure de confiance de mes classifieurs : je sais qu'elle est leur performance individuelle. C'est je pense la meilleure estimation de leur performance.

Perso, j'utiliserais le jeu de données de développement pour estimer la confiance qu'on a en chaque classifieur.

[Aleph69]

Bonjour,

Mathématiquement on additionne pas des probas...

Il ne s'agit pas d'une somme de probabilités mais d'une combinaison linéaire de probabilités où la somme des coefficients de la combinaison vaut un. Géométriquement, cela revient à se placer dans une enveloppe convexe : la moyenne de probabilités est encore une probabilité. Il n'y a aucun argument mathématique interdisant de moyenner des probabilités.

Si c'est celui sur les Random Forest, oui. Sinon il en a écrit beaucoup.

C'est bien lui mais je fais plutôt référence à son article sur le bagging.

Je n'ai JAMAIS dit que mes classifieurs étaient "soft". C'est plutôt le contraire dans la réalité avec des classifieurs qui ont des performances autour de 90% dans la plupart des cas.

Je parle de "soft classifiers" par opposition aux "hard classifiers". Les premiers retournent des scores, les seconds des classes. Je dis que puisque tu disposes de scores, il serait dommage de les transformer en classes trop rapidement.

En revanche, je ne vois pas l'intérêt de disposer d'un ensemble de classificateurs exhibant 90% de prédictions correctes. Si c'est le cas, ta question initiale n'a plus de sens : tu peux en choisir un au hasard. Statistiquement, tous tes classificateurs se valent. Tu peux facilement le vérifier avec un test d'hypothèse.

Pour le reste, je te laisse te documenter sur le méta-apprentissage et l'apprentissage ensembliste. Le domaine ne manque pas de subtilités et nécessite beaucoup de rigueur. Il est difficile d'en expliquer les fondements au cours d'une discussion dans un forum. En revanche, je répondrai volontiers si tu as des questions précises sur le sujet.

[ToTo13]

En revanche, je ne vois pas l'intérêt de disposer d'un ensemble de classificateurs exhibant 90% de prédictions correctes. Si c'est le cas, ta question initiale n'a plus de sens : tu peux en choisir un au hasard. Statistiquement, tous tes classificateurs se valent.

Ca a du sens si les erreurs commises sont différentes.

[Aleph69]

Ca a du sens si les erreurs commises sont différentes.

Je t'invite à le vérifier à l'aide d'un test d'hypothèse ou à lire l'article de Demsar donné en lien dans mon précédent message.

[pseudocode]

Ca fait longtemps que je n'ai pas relu le papier de Breiman sur le "Bootstrap aggregation", mais je n'ai pas souvenir qu'on y additionne des probas...

Dans mes souvernirs, on construit un multi-classifieur basé sur le vote majoritaire des classifieurs simples.

Cmultiple(x) = Argmax_y( Somme{Csimple(x)=y} )

[Aleph69]

Bonjour,

Ca fait longtemps que je n'ai pas relu le papier de Breiman sur le "Bootstrap aggregation", mais je n'ai pas souvenir qu'on y additionne des probas...

Dans mes souvernirs, on construit un multi-classifieur basé sur le vote majoritaire des classifieurs simples.

Cmultiple(x) = Argmax_y( Somme{Csimple(x)=y} )

Effectivement, pour des classificateurs "hard", Breiman propose d'effectuer un vote majoritaire. En revanche, pour la régression, et en particulier pour les prédicteurs probabilistes tels que les classificateurs souples, il propose de moyenner les hypothèses.

Inutile de relire l'intégralité de l'article, c'est écrit au début de la page 2.