Bonjour à tous,
Il y a quelques temps on m'avait demandé de faire un petit topic sur les bases de l'IA, les approches statistiques etc.
Donc voilà, ça y'est, c'est parti, ça commence aujourd'hui.
Juste 2,3 précisions avant que l'on ne me tombe dessus de toutes parts: je n'ai pas pour ambition de faire un vrai cours de  
 
maths avec ses fondements, sa rigueur etc. Mon but est tout simplement d'essayer d'exposer les principes fondamentaux et  
 
utiles, et d'essayer de vulgariser la chose au maximum. On y trouvera donc pêle mêle des maths rigoureuses, des maths hyper  
 
simplifiées et du français (je voulais rajouter du cul et de la déconne pour attirer le passant mais bon...).
Il n'y aura pas non plus de programmation à proprement parler. Il existe tellement de langages, de problèmes, de projets  
 
différents que ça ne sera pas super utile. Par contre, s'il faut des algos., il y en aura.
Le premier post du topic me servira comme post de base pour indéxer les "chapitres", ajouter des remarques préalables etc.
Bonne lecture à tous, et surtout bon courage
 
 
========================================================================
Leçon 1: quelques bases de stat.
http://forum.hardware.fr/hardwaref [...] tm#t788958
 
========================================================================
Leçon 2: quelques bases (suite) - la gaussienne
http://forum.hardware.fr/forum2.ph [...] =0#t790086
 
========================================================================
Leçon 3: quelques bases (suite) - un peu d'algèbre linéaire
http://forum.hardware.fr/forum2.ph [...] =0#t791432
 
========================================================================
Leçon 4: la classification bayesienne
http://forum.hardware.fr/forum2.ph [...] =0#t794412
 
========================================================================
Leçon 5: Analyse en composantes principales (ACP) et transformée de Kerhunen-Loeve
http://forum.hardware.fr/forum2.ph [...] =0#t820061

Quelques bases de stat.
======================================================================
 
Une expérience aléatoire est une expérience dont on ne peut pas prévoir le résultat.
On connait par contre un ensemble de résultats possibles, ainsi qu'un ensemble d'événements possibles.
Une probabilité est donc une fonction de l'ensemble des événements dans [0,1] (probabilité d'un événement = 1 - probabilité de l'événement contraire).
 
Pour résumer:
probabilité d'un événement = nombre de cas favorables/nombre de cas possibles
 
Exemple:
j'ai une boîte de 50 boules (40 rouges et 10 jaunes)
P(tirer une boule rouge) 40/50
P(tirer une boule jaune) 10/50
Ici, nous avons donc l'univers U, composé des événements A (boules rouges) et B (boules jaunes).
En théorie ensembliste on retrouve

• A union B = U
• A inter B = ensemble vide

Voyons à présent ce que l'on appelle les probabilités conditionnelles:
C'est ce qu'on note par P(A|B) (se lit probabilité de A sachant B)
P(A|B) = P(A inter B)/P(B)
A ce niveau, le théorème de Bayes est très important, mais nous l'aborderons un peu plus tard.
 
Je vous passe les définitions sur les variables aléatoires (VA), seules leurs propriétés nous interressent vraiment. Il faut se rappeller que X est la VA, F sa fonction de répartition et f sa densité (je vous laisse aller vous renseigner sur la réelle signification de tout ceci).
Un petit exemple pour illuster:
Les notes des éléves à un examen:

La VA sera donc "note des élèves", et sa densité les notes en elles-mêmes

 
Ce que l'on appelle espérance (E) peut-être défini par somme des (x*f(x)) et la variance (V) par somme des ((x-E)²*f(x))
La variance est connue comme l'écart-type au carré.
 
Grosso modo (et je vous passe la démonstration), on accepte que l'espérance soit estimée par la moyenne. Donc quand on ne connait pas la loi de probabilité de ce que l'on étudie (et c'est presque toujours le cas), on utilise la moyenne.
On peut alors définir l'écart-type (cf. plus haut) comme l'écart moyen à la moyenne.
Je connais donc ma moyenne, c'est à dire la valeur autour de laquelle tournent mes résultats, et l'écart-type, qui me donne une idée de la distance moyenne de mes résultats par rapport à la moyenne.
J'ai donc 2 indicateurs qui me permettent d'avoir une idée de ce que j'étudie (plus l'écart-type est faible, plus j'ai de chance de tomber sur une valeur proche de la moyenne).
 
Alors, vous me direz que là c'est facile, on ne travaille que dans une dimension... ouais OK, mais pour généraliser à un ensemble n de dimension, on utilise la covariance estimée (grâce à la moyenne) par:  
cov(X,Y) = (1/N)*somme[(y-moyenne des y)*(x-moyenne des x)] avec N nombre total d'individus (de données).
Allez, encore un exemple bête, un nuage de points:
(0,0), (1,4), (5,1), (4,5), (6,8), (7,7)
Noté autrement on a:

Donc ma covariance entre x et y sera:

 
Dernier point, sachant que cov(X,X) = V(X) (la covariance d'une VA avec elle même est en fait sa variance), on peut calculer ce que l'on appelle la matrice de covariance qui est en fait la matrice des covariances de chacun des paramètres avec l'autre.
Par rapport à notre exemple précédent on trouverait:

On retrouve 5.0277 notre covariance entre X et Y, 6.4722 la variance de X et 8.4722 la variance de Y
 
Et, me direz-vous, quel est l'interêt de bosser en plusieurs dimensions?
Un exemple tout bête; je fait de la prévision sur un ensemble de capteurs (température, couleur, densité etc.). Chaque capteur m'apporte un ensemble de résultats OK? Donc, il faut travailler dans un espace possedant autant de dimensions que de capteurs.
 
Là encore, on verra un tout petit peu plus tard l'utilité de tout ceci.
 
Je pense vous avoir assez assommés avec ça, il faut juste se rappeller 4 choses:

• probabilité d'un truc = nombre d'événements qui réalisent mon truc sur nombre d'événements total
• la moyenne: qu'est-ce que c'est, comment on la calcule
• l'écart-type:  qu'est-ce que c'est, comment on le calcule
• la matrice de variance-covariance: comment on la calcule

Ainsi s'achève cette courte introduction, nous avons les bases, on peut passer à la suite qui est la classification bayesienne (laissez moi juste le temps de rédiger la prochaine partie).

Hop. un topic interessant  

merci moktar

+1

 
et ta mère, elle sait lire une RFC ?  
http://www.cse.ohio-state.edu/cgi-bin/rfc/rfc1738.html

wahou, terrible

Cool ce topic !
 
Au passage, vous connaissez un bon bouquin de maths appliquées à l'informatique (niveau fin de premier cycle) ?

Merci Moktar, encore un topic intéressant à suivre.
J'en profite pour signaler l'existence du langage e programmation IBAL (prononer "eyeball", soit littéralement, "à vue de nez" ), qui permet de programmer rn "logique floue", et intègre un moteur d'inférence.
 

Oups, le lien : http://www.eecs.harvard.edu/~avi/IBAL/

Euh ouais, j'irais jeter un oeil, il y a peut-être de quoi s'amuser avec ça.
J'aborderais la logique flou plus tard.
Je n'avais pas penser à présenter le principe du moteur d'inférence, mais ça peut aussi être une bonne idée

Bases élémentaires 2: la gaussienne
 
Avant d'attaquer le gros morceau, je me suis apperçu qu'il manquait encore 2 ou 3 trucs importants.
Continuons donc à nous plonger dans l'univers merveilleux des nombres.
 
Donc comme je le disais précédement, on peut représenter un phénomène aléatoire par une fonction (j'avais parlé de fonction de densité, sisi, rappellez-vous).
A partir de là, 2 cas sont possibles:

• on connait la loi de probabilité du phénomène qu'on étudie, et là c'est génial, on n'a plus rien à faire (bah oui, on connait la fonction f, donc pour un x donné on sait bêtement calculer f(x))
• on ne connait pas cette loi, donc on va chercher à l'éstimer (on en a déjà vu une partie avec l'éstimation de l'éspérance par la moyenne)

Brièvement, quelques lois de probabilités connues: loi normale (ou gaussienne, ou "en cloche" ), loi binomiale, loi exponentielle, loi de Poisson, loi de Fisher, loi du X² (chi-deux), loi de Student etc.
Vous pouvez aller vous ballader sur google et regarder un peu à quoi elles ressemblent précisement, quels sont leurs paramètres etc.
Celle qui nous interresse particulièrement (car la plus usitée, la plus connue, la plus pratique), c'est la loi Normale (ou gaussienne, ou loi de Gauss, mathématicien de son état).
On l'appelle aussi "courbe en cloche", car ça ressemble à:

 
Pour la jouer barbare, la formule précise de cette loi (en une dimension pour commencer) est:

où sigma est l'écart-type, sigma² l'écart-type au carré (donc la variance) et m la moyenne.
Donc en gros, on prend l'écart quadratique (écart au carré) de l'individu à la moyenne et on pondère par l'écart-type au carré.
Rappellez vous que l'écart-type nous donne l'information sur l'éparpillement par rapport à la moyenne, donc pondérer la distance à la moyenne par l'écart-type permet de rendre la mesure plus robuste (plus l'écart-type est grand, et plus je divise par une grande valeur et moins je prend en compte ma distance à la moyenne).
Ce calcul de distance est aussi appellé Distance de Mahalanobis.
Ensuite le exponentielle de -1/2 de ... c'est tout bêtement pour retrouver une mesure entre 0 et 1.
Le coefficient devant l'exponentielle est là pour normaliser (ce coefficient est la valeur max de la courbe, et est atteint quand x=m)
 
De toutes manières, il faut surtout se rappeller de cette formule et de ce qu'il y a dedans (sigma, x et m).
 
Et là je sens bien qu'une question vous brûle les lèvres: qu'est-ce qu'elle a de magique cette loi là?
Alors accrochez-vous bien: une brève démonstration mathématique prouve qu'on peut utiliser la loi normale pour approximer n'importe quelle loi, à partir du moment où le nombre d'individus est suffisament important (théoriquement 30, en pratique on prend minimum 50 ou 100).
Donc, quand on étudie un phénomène, si on a suffisement d'observations pour faire un bon apprentissage (donc en gros 50 ou 100), on peut considérer que ce que l'on observe suit une loi normale (dont les paramètres seront la moyenne et l'écart-type de ce que l'on a observé).
Bon, j'avoue, j'ai hyper simplifié là, mais c'est le résultat qui nous interresse le plus.
Si vous voulez du détail sur la démonstration regardez à:

• inégalité de Bienaymé-Tchebicheff
• théorème central-limite
• loi des grands nombres

Il faudrait aussi détailler un peu les [g]éstimateurs[g], mais j'aimerais faire une partie sur les éstimations par intervalles de confiance, donc on verra ça à ce moment là.
 
Voilà, c'est normalement tout, donc résumé de la partie:

• la loi normale c'est de la balle (gardez sa formule dans un coin de votre tête )

Bases élémentaires 3: bases d'algèbre linéaire
======================================================================
 
Je vais essayer de vous montrer très très vite un truc rigolo, mais avant il faudra se bouffer encore un peu de rappels-bases; cette fois-çi attaquons l'algèbre linéaire.
 
Ici nous sommes dans un domaine à cheval entre l'algèbre et la géométrie, mais ne paniquez pas (du moins pas tout de suite ) car pouvoir basculer d'un monde à l'autre c'est des fois bien commode pour comprendre les principes.
Là non plus, pas de démonstrations-théorèmes-postulats à gogo, je vais aller à l'essentiel.
 
On utilise 3 types de données: les scalaires, les vecteurs et les matrices.
Voilà c'est tout
Je vais quand même détailler un peu, notamment les calculs.
 
Alors les scalaires, on peut voir ça comme une données "simple", toute seule, tranquille, qui fait pas chier son monde (1, 12, PI, e, 24.53563 etc. sont des scalaires).
Les vecteurs nous font rentrer dans le fantastique monde des multidimensions. Quelque part d'ailleurs, un scalaire n'est qu'un vecteur de dimension 1. Ici toutefois, il faut se rappeller qu'un vecteur peut-être vu en ligne ou en colonne:

et

ne sont pas tout à fait tous les 2 le même vecteur (on les appelle transposés, mais on verra plus bas à quoi ça correspond).
Pourquoi faire la distinction? On le verra au moment d'aborder les calculs entre tout ce petit monde.
Il reste enfin les matrices. Pour faire le parrallèle avec l'info., les vecteurs sont des tableaux 1D et les matrices des tableaux 2D. Voilà...
Des matrices, il en existe de toutes sortes, de toutes tailles, de toutes formes et de toutes couleurs (NxN, NxM, MxN, diagonale, symétrique etc.)
 
Abordons maintenant le vif du sujet: les opérations
Comme avec des scalaires (des nombres "normaux" ), on peut additionner, soustraire, multiplier ou diviser. Par contre, vu qu'on tape dans plusieurs dimensions, les opérations sont un peu plus complexes, et subissent plus de contraintes.

• Addition et soustraction

Les opérations les plus simples. Ici pas de contraintes précises, on retrouve la commutativité et l'associativité.
scalaire +/-  vecteur = vecteur. On prend tout bêtement chaque élément du vecteur et on additionne/soustrait le scalaire.
Exemple:

même chose pour scalaire +/- matrice = matrice

L'addition de 2 matrices est aussi bête que ça, il faut par contre que les matrices aient la même taille!!! Donc pas d'addition de matrices de tailles différentes, donc pas d'addition de matrices et vecteurs, et pas d'addition de vecteurs de tailles différentes
 

• Multiplication

Là, vous allez voir, ça devient moins drôle...
On va commencer par les choses simples: scalaire * matrice = matrice, et on multiplie chaque terme de la matrice par le scalaire (comme pour les additions/soustractions)
 
vecteur * vecteur = scalaire mais il faut que:
. les 2 vecteurs aient le même nombre d'éléments
. qu'il y ai un vecteur ligne et un vecteur colonne
le résultat et la somme des produits terme à terme (élément1_vecteur1*élément1_vecteur2 + élément2_vecteur1*élément2_vecteur2 etc.)
 
vecteur * matrice ... alors déjà un problème de taille:
. il faut que ce soit un vecteur "ligne"
. si on a une matrice de taille MxN, il faut que le vecteur soit de taille 1xM
ensuite, le calcul en lui-même:
soient le vecteur V

et la matrice M

alors V*M donnera le vecteur R (vecteur colonne)

où Ri=somme(Vj*Mji)
ici, par exemple, R0=(V0*M00)+(V1*M10)+...+(Vm*Mm0)
et ainsi de suite pour tout le vecteur R
 
Pour multiplier les matrices, c'est presque pareil, mais il faut que
. pour calculer A*B, il faut que le nombre de colonnes de A soit égal au nombre de lignes de B
sinon, c'est comme pour vecteur*matrice, une addition de produits termes à termes. Il faut en fait voir les matrices comme des tableaux de vecteurs, donc la matrice résultat et la matrice des multiplications des vecteurs uns à uns.
 
Notons vite fait que, si A et B sont 2 matrices carrés (même nombre de lignes et de colonnes), A*B != B*A
 

• Division

Et là... c'est le drame...
Cette partie c'est la pire, car elle fait intervenir une notion importante: l'inverse
En fait, pour diviser A par B, on calcul précisement A*(B^-1)
Je ne vais pas rentrer dans le détail du comment, du pourquoi, comment on le calcule tout ça, car ça fait intervenir d'autres notions comme celle du déterminant.
 
On va juste dire que pour calculer A/B, il faut calculer A*(B^-1) voilà.
 

• Transposée

On en a parlé un peut tout à l'heure, c'est une notion tout bête mais oh! combien pratique, qui réalise en fait une inversion de la matrice (ou du vecteur).
ATTENTION ne pas confondre avec l'inverse!!!
2 exemples pour bien comprendre ce principe:

Voilà, on inverse les lignes et les colonnes
Rappelez vous que, quand un vecteur n'a pas la tête qu'on voudrait qu'il ait (ex. on a un vecteur colonne qu'on veut multiplier avec une matrice), on a tout à fait le droit de prendre sa transposée pour le calcul, alors ne nous gênons pas
 
Donc, maintenant, on peut vraiment commencer les choses sèrieuses, et moi je pourrais vous lâcher de quoi vous amuser.
Patience...

La classification bayesienne
 
Alors voilà, nous y sommes pour de bon cette fois.
La classification consiste à séparer les données entre-elles et à créer des classes dans lesquelles se regrouperont les mesures les plus proches.
La théorie de la décision de Bayes est une approche statistique du problème. Elle est basée sur les hypothèses suivantes:

• le problème de la décision est exprimé en terme de probabilités
• la valeur des probabilités a priori du tirage d'une classe est connu

Brievement, en français courant nous dirons que la décision se fera sous la forme: "machin a plus de chance d'être de la classe truc plutôt que de la classe bidule, en sachant que la classe truc a telle probabilité d'apparaître et la classe bidule, telle probabilité".
 
Bon, un peu de maths pour détailler tout ça:
Soit w[i], une variable aléatoire représentant l'état d'un individu ([i]wj si l'individu appartient à la classe j).
Soit omega, l'esemble des S états possibles (omega={w1,w2,...,wS}).
On connaît alors les probabilités a priori: p(w1),p(w2),...,p(wS).
Si on ne connait rien d'autre, alors p(individu=wj)=p(wj): la probabilité qu'un individu appartienne à la classe [j]j[/i], est la probabilité d'apparition de cette classe elle-même (revoir l'exemple des boules de couleur).
Or, nous avons la formidable chance de disposer d'autres informations (mesures), ce qui nous donne: p(x|wj) densité de probabilité de x sachant que l'individu est wj, ou bien densité de probabilité conditionnelle à son appartenance à wj.
Pour être moins barbare, nous dirons qu'il est possible de donne une probabilité d'appartenance à telle ou telle classe sachant ce que nous savons sur l'individu (ses caractèristiques, ses attributs, ce que nous avons mesuré en somme...).
Un exemple tout bête:
Prenons le cas d'une image, avec ses pixels codés sur 3 composantes (R,G,B). Si nous restons dans le cadre tout simple des boules de couleurs, c'est à dire qu'on tire au hasard un pixel sans se poser de questions, sa probabilité d'être rouge sera la même que celle d'être bleu et sera la même que celle d'être vert; soit (2^24)/3 (si on travaille en 24 bits bien sûr). A ce propos d'ailleurs, ne vous formalisez pas et ne cherchez pas à rendre le problème trop complexe. Nous n'allons travailler que sur ces 3 solutions possible (un pixel est soit Rouge, soit Vert, soit Bleu).
Ajouter maintenant à cela, la connaissance que nous avons sur le pixel: nous tirons un pixel au hasard dans l'image et nous mesurons ses composantes (R,G,B). Et là, on trouve (190,50,40). Connaissant cela, on peut qu'il y a une forte probabilité que le pixel soit Rouge (contrairement à ce que j'ai cité au dessus, ou nous avions equiprobabilité entre les 3 solutions possibles).
Est-ce que vous voyez à présent comment combiner la connaissance a priori sur les classes et la connaissance sur l'individu que nous analysons?
 
On va se replonger un peu dans la technique pour comprendre d'où ça vient et ce que l'on peut faire avec.
On a vu que:

• p(wj) est la probabilté d'apparition a priori de la classe wj  
• p(x|wj) est la probabilité que la forme caractérisée par le vecteur x appartienne à wj

Dans ce cas, on connaît x={x1,...,xn} le vecteur aléatoire (mesures ou situation) sur Rn.
Le problème devient alors: soit un individu et sa mesure x. Comment décider à quelle catégorie (wj[/j]) affecter cet individu?
La règle de Bayes donne la réponse:
[i]p(wj|x)=[p(x|wj)*p(wj)]/p(x)
avec
p(x)=somme de tous les p(x|wj)*p(wj)
Et là, on décide wj si p(wj|x) est le plus grand.
 
Vous voulez du détail? En voici:
Cette méthode nécessite bien sûr un apprentissage. Nous avons besoin d'une idée sur les lois de probabilité pour chacune des classes.
Si le nombre d'individus appris est suffisement grand, on peut utiliser... j'attends vos réponses... et oui bien sûr, la loi normale.
Avec ce que nous avons vu, la moyenne et la variance (ou matrice de covariance pour être plus généraliste).
p(wj) c'est tout bête à calculer: nombre des individus appris appartenant à la classe wj sur nombre total des individus appris.
p(x|wj) se calcule avec la loi normale, la moyenne des individus appris appartenant à la classe wj et la matrice de covariance de TOUS les individus appris.
 
Dernier point technique avant de voir un exemple:
On va se placer directement pour un nombre infini de dimensions, comme cela on aura le système le plus générique possible.
On sait que pour la loi normale, il faut calculer l'écart à la moyenne au carré, divisé par la variance. Très bien mais... comment le faire en ndimensions?
C'est tout bête: soient un vecteur V et une matrice M. Pour avoir (V^2)/M on va travailler comme ça:

Et vous pourrez vérifier: on a bien le carré et la division.
Pour la loi normale c'est pareil, on a:

Avc P la matrice de variance/covariance et |P] son determinant.
Ce qu'il y a avant l'exponentielle n'est pas interressant, ça permet juste de normaliser le résulat et d'avoir une probabilité (i.e. entre 0 et 1).
 
Que diriez-vous d'une petite mise en application? hein?
Alors pour les exemples, pour le moment j'utiliserais un truc hyper sympa nommé scilab (http://scilabsoft.inria.fr/).
C'est gratuit et ça permet de faire des trucs de ce genre de manière très simple.
Je ne peux que vous conseiller de le ramener et de l'installer chez vous (de toutes manières, mes exemples sont des scripts scilab ).
Le premier script se trouve sur:
http://moktar1er.site.voila.fr/scilab/rgb1.sci
 
Alors décorticons ce script... et poussons même le vice à commencer par le début:

 
Là je crée 3 matrices (nommées rouges, verts et bleus), de 100 lignes chacuns et de 3 colonnes. Chaque colonne est une composante (R,G et B).
La valeur de ces composantes est tirée au hasard, mais j'ai fait attention que pour les rouges, la valeur R soit forcément plus grande que les autres, et ainsi de suite pour verts et bleus (une valeur entre 190 et 255 pour la composante dominante et une valeur entre 0 et 100 pour les 2 autres).
Je crée aussi 3 vecteurs moyrouges, moyverts et moybleus qui sont, respectivement, les vecteurs moyennes (à 3 dimensions car 3 composantes) pour rouges, verts et bleus.
Ensuite je calcule prouges, pverts et pbleus qui sont les probabilité a priori d'apparition de mes classes (100 individus par classe, 300 individus appris, 3 classes donc 1/3 par classe).
 

 
Cette partie là est l'apprentissage à proprement parler.
Notre connaissance regroupe en fait les vecteurs moyennes et la matrice de variance/covariance.
Ici je calcule à l'avance mon inverse (et je vous conseille de le faire aussi) pour ne plus avoir à le faire au moment de la reconnaissance.
Vous comprenez pourquoi je fais mon illustration avec scilab ? (c'est magique les mean, mvvacov et autres inv).
Vous trouverez, j'en suis sûr, sur le net les librairies mathématiques correspondant à votre langage préféré, permettant facilement ce genre d'exercices.
 
L'apprentissage terminé, on peut passer à la reconnaissance proprement dite:

 
Là je tire un individu complètement au hasard; histoire de voir ce que ça donne...
 

 
Ici rien de bien méchant, c'est juste l'implémentation bête et méchante du calcul avec les lois normales
 

 
Et le calcul du résultat...
 
Un exemple de ce que je trouve:

 
J'ai donc là un individu avec ses composantes R,G,B et on voit ses probabilités d'appartenance à chacune des classes (de gauche à droite: Rouge, Vert, Bleu).
 
Voilà, bon courage, faizez bien mumuse avec ça, si vous avez des questions, allez-y...
 
Je vais juste préciser 2, 3 trucs:

• C'est une classification dite "supervisée", c'est à dire qu'il faut quand même expliquer au bouzin qu'il y a des classes, quelles sont-elles et à quoi elles ressemblent. Il existe aussi des méthodes non supervisées du type "voilà des données en vrac, crée moi 3 classes avec ça" (ça s'appelle aussi du clustering).
• Il existe des méthodes d'apprentissage incrémental (calcul incrémental de la moyenne et de la variance/covariance). Cet exemple est figé, on apprend et on reconnaît tout de suite. Vous pouvez facilement concevoir un système capable d'apprendre "à la volée" (i.e. enrichir sa connaissance), de récupérer sa connaissance passée sur demande pour classification.
• L'exemple des couleurs n'est peut-être pas ce qu'il y a de plus parlant, mais dites-vous que vous, vous savez ce que c'est une couleur, mais pas la machine. De toutes manières, vous pouvez-tout envisager.

• ERRATUM:

L'idéal est quand même de calculer 1 matice de variance/covariance par classe, et non pas une matrice pour tous les individus

• ADDENDUM:

Un cas particulier peut se poser: l'individu que je cherche à identifier ne ressemble à rien de connu...
je peux avoir:
Distance à la classe A -> 1e-210
Distance à la classe B -> 0
Or, si je normalise, je vais avoir:
p(A/i) = 1
p(B/i) = 0
Et là... ça ne va pas du tout...
Alors, ce que je conseille, c'est de regarder la valeur de la somme des probas d'appartenance à toues les classes.
Si cette valeur est torp insignifiante, on décide que... on ne peut pas décider

avis à tous ceux qui ont drapeauté ici: j'aurais besoin d'un retour, de vos avis etc. pour savoir comment continuer (et si cela mérite de l'être)

L'analyse en composantes principales (ACP) - Transformée de Kerhunen-Loeve
 
Bon... je me suis longtemps taté avant d'aborder cette partie là.
C'est un outil statistique hyper pratique et en même temps... il nécessite d'aborder des notions mathématiques assez complexes. Je vais essayer de faire court et efficace, attachez vos ceintures...
 
 
 
Reprenons notre point de départ: nous avons un paquet de points, chaque point ayant des coordonnées sur n dimensions (n capteurs...).
Au cours de la partie sur la classification bayesienne, nous avions des points en 3 dimensions (ça c'est pour faire avec un exemple).  
 
On a vu qu'un s'en sortait pas mal mais... bah on bosse sur plusieurs dimensions, ce qui allourdi toujours les calculs.
De plus, dans l'espace des capteurs, comment peut-on réellement juger des problèmes d'échelles ou autre? Comment calculer la distance entre 2 variables si l'une est exprimée en centimètre et l'autre en kilogramme? Est-ce que deux individus ont des valeurs assez voisines pour chacune des variables, ou au contraire très proches pour certaines et éloignées pour d'autres?
Dans ce cas, il nous faudrait un outil magique de transformation d'espace qui puisse nous arranger tout ça... et si en plus il pouvait le faire tout seul, ce serait bien non?
Ca tombe bien, l'ACP permet de le faire. Si tout va bien ça va:

• transormer l'espace de manière à augmenter les distances inter-classes et à minimiser les distances intra-classes
• réduire le nombre de dimensions

Mais avant, bouffons des maths
Il y a 2 notions à connaître ici, qui sont: valeurs propres d'une matrice et vecteurs propres d'une matrice.
Oui, je sais, on replonge dans le calcul matriciel, l'algèbre linéaire tout ça mais... les matrices c'est quand même un outil pratique. Cela permet d'aborder plusieurs points de vue en un (géométrie, algèbre etc.).
Soient A une matrice, V un vecteur et s un scalaire.
s est dit valeur propre de A, ssi il existe V différent de 0 tel que A.V = s.V
Dans ce cas, V est appellé vecteur propre associé à la valeur propre s.
 
Alors, à partir de là, la transformée de karhunen-loeve consiste en:

• calculer la matrice des variances-covariances pour l'ensemble des individus appris
• calculer ses valeurs propres et ses vecteurs propres
• trier les vecteurs propres par ordre décroissant de valeur propre

Pourquoi trier? Tout simplement parceque la valeur propre la plus forte, vu que l'on travaille sur la matrice des covariances, désigne l'axe de la transformation sur lequel on fera apparaitre le maximum d'information.
La matrice formée par les vecteurs propres triés, sera la matrice de transformation qui nous ouvre les portes du nouvel espace de représentation optimisé.
 
Reprenons l'exemple du RGB.
J'ai refait un script sous scilab avec pour la génération des points:

Notons que, pour le rouge mais c'est valable pour le vert et le bleu, je tire la composante rouge au hasard entre 190 et 255, et les autres composantes entre 0 et 190. Ca devrait permettre de paver tout l'espace RGB, en évitant quand même les chevauchements (cyan, magenta, jaune, blanc et noir).
 
Si je représente chaucune des 3 dimensions de mon espace (chaque dimension est projetée sur son axe), on devrait avoir quelque chose comme:

 
C'est bien joli, chacune des trois classe est bien séparée, mais je me tape toujours 3 dimensions à gérer.
 
Alors, je fais mon ACP, notamment grace à la fonction bdiag qui me renvoie valeurs et vecteurs propres:

Bon je sais, mon algo de tri est tout pourave, mais pour 3 valeurs propres je n'allais pas me faire scier...
Ce qui compte c'est que vecprop soit ma matrice des vecteurs propres triés.
Pour changer d'espace, je n'ai qu'à faire:

 
En reprenant mes tableaux rouges, verts et bleus et en les multipliant avec vecprop, j'ai changé mon espace d'apprentissage.
Et maintenant, si je ne projete que la première dimension de ce nouvel espace, je trouve:

 
Donc, à présent, une seule dimension me suffit à faire ma classif.
A la rigueur, je n'ai même plus à m'embêter à implémenter un gros classifieur... une simple distance euclidienne pourrait suffire.
Mais je ne peux que vous conseiller de combiner ACP et classifieur, les résultats sont convaincants.
Il faut d'abord faire l'ACP pour savoir comment changer d'espace, puis faire l'apprentissage et la reconnaissance dans ce nouvel espace.
 
Notez aussi, que ce que l'on obtient est une rotation du cube RGB, rotation pour laquelle les distance intra et inter-classes sont optimisées. On aurait pu le faire à la main avec une bête matrice de rotation mais... quel angle choisir? Et une rotation sur quel axe? Là, l'ACP à fait le travail toute seule...

quel succes

ouais tu trouves aussi?

c'est trop fort pour le commun des forumeurs, stout!

spa parce qu'on dit rien qu'on apprecie pas

 
pourtant un blanc apres une blague on apelle ca un bide

J'en chie méchamment pour implémenter l'acp en c++ d'après mon vieux support de cours, je risque d'avoir besoin d'aide - j'ai bien peur d'avoir mal compris un truc...

Tiens, je croyais que ce topic faisait quand même au moins 5 pages

Voilà ce que je ressors de mes cours :
1) Calculer le tableau de données centré-réduit Z
Z(i,j) = (valeur(i,j) - moyenne(j)) / ecart-type(j)
 
2) Calculer la matrice de corrélation R
R(i,j) = somme(k=1->nbindividus) (Z(k,i)*Z(k,j))
 
...et là mes valeurs devraient être entre 0 et 1, ce qui n'est pas le cas...

J'ai acheté ce bouquin, il est pas mal:
http://www.amazon.com/exec/obidos/ [...] s&n=507846
 
Y a quelques chapitres sur les aspects statistiques et probalistiques (que j'ai pas encore abordés)

Pour la classification bayesienne:

• ERRATUM:

L'idéal est quand même de calculer 1 matice de variance/covariance par classe, et non pas une matrice pour tous les individus

• ADDENDUM:

Un cas particulier peut se poser: l'individu que je cherche à identifier ne ressemble à rien de connu...
je peux avoir:
Distance à la classe A -> 1e-210
Distance à la classe B -> 0
Or, si je normalise, je vais avoir:
p(A/i) = 1
p(B/i) = 0
Et là... ça ne va pas du tout...
Alors, ce que je conseille, c'est de regarder la valeur de la somme des probas d'appartenance à toues les classes.
Si cette valeur est torp insignifiante, on décide que... on ne peut pas décider

Bon... je vois que ça passionne toujours autant les foules...
Pour la peine vous me lirez l'excellent:
http://neuron.tuke.sk/~hudecm/PDF_ [...] N_Book.pdf
Qui est le "The ANN (Artificial Neural Network) Book, de Hristev", un super bouquin sur la théorie des réseaux neuronnaux.
Je pense que la prochaine partie de ce topic abordera les RDN justement. J'imagine parler du perceptron (reconnaissance de formes), d'un RDN un peu plus évolué (rétropropagation) et enfin jouer avec les cartes de Kohonen (et ça c'est de la baballe atomique).
Après ça, il faudra que je prenne du temps pour préparer quelque chose sur la logique floue.
(Je sais, tout le monde s'en tape, mais au moins ça a le mèrite de me faire un mémo personnel disponible à tout instant ).

Non non je m'en fous pas...

chuis toujours là aussi

 
Quand tu normalise tu fait quoi ? T'applique la loi normale ? Pourquoi tu normalise ?