Algorithmes, Applications

Algorithmes du plus proche voisin

On pourrait penser que les meilleurs algorithmes d’intelligence artificielle sont ceux qui peuvent traiter la plus grande quantité de données en très...

Écrit par Ilyes Talbi · 2 min lecture >
Algorithmes du plus proche voisin

On pourrait penser que les meilleurs algorithmes d’intelligence artificielle sont ceux qui peuvent traiter la plus grande quantité de données en très peu de temps. C’est un vrai…mais pas que.

Les limites de la puissance de calcul


Il faut savoir que les premiers ordinateurs qui ont réussi à nous concurrencer sur des activités humaines, n’étaient pas vraiment ‘’intelligents’’.

C’étaient des machines avec une puissance de calcul énorme. Là ou mon cerveau peine à faire plus d’une opération par seconde (par semaine quand je suis fatigué), nos smartphones peuvent en effectuer des dizaines de milliards. Ainsi, DeepBlue, l’algorithme d’IBM qui a battu Kasparov aux échecs en 1997, se contentait de prévoir tous les coups possibles en anticipant la réponse de l’adversaire et en choisissant ce qui semble être la meilleure option.

Certes aux échecs il y a un nombre immense de coups possibles, mais tous les étudier est quelque chose de largement accessible pour un ordinateur bien configuré.

Les limites de cette approche reposent sur le fait que pour certaines activités les possibilités sont presque infinies. Ont pourrait croire que pour configurer un assistant comme Siri, il suffit de mémoriser toutes les conversations, mais c’est quelques choses d’impossible. Le nombre de conversations possible entre deux humains est tellement grand que la plupart des discussions ont lieues pour la première et dernière fois.

Rendons les machines un peu intelligentes


Si vous demandez à Siri ‘’Comment vas-tu ?’’ il est peu probable qu’il sache de quoi vous parlez. Néanmoins il a certainement dans sa base de données des questions du type ‘’Ça va ?’’, ‘’Tu vas bien ?’’ ou ‘’Comment tu vas ?’’ auxquelles il sait répondre. Il va alors faire ce que l’on appelle de l’interpolation pour vous donner une réponse (vous pouvez aller voir notre article sur la reconnaissance vocale).

Cette approche est utilisée dans plusieurs applications. Vous avez sans doute déjà vu sur Amazon : ‘’ceux qui ont achetés cet article ont aussi appréciés ’’.

Le principe est le suivant. Vous voulez savoir si un article vous plaira, vous cherchez alors une personne qui a des goûts similaires aux votre. Si elle a aimé alors vous aimerez surement si elle n’a pas aimé, ça sera surement le cas pour vous aussi.

Cet algorithme est appelé algorithme du plus proche voisin. C’est un des algorithmes d’apprentissage supervisé les plus utilisés. Mathématiquement, vous avez des données X et X’ qui sont proches et vous souhaitez faire une estimation sur ces données. Si pour X le résultat est Y il y a de grandes chances que pour X’ le résultat soit Y’=Y.

La notion de proximité est définie par rapport au calcul de la distance entre X et X’. Il y a une infinité de définitions de la distance possibles. Pour des textes on peut définir des distances avec TF-IDF ou bien depuis le modèle Word2vec.

Pour la reconnaissance d’objet on peut raisonner de la même manière. Des algorithmes comme les réseaux de types CNN, permettent d’évaluer les distances entres images. Elles calculent la similarité en parcourant l’image par groupes de pixels. C’est d’ailleurs comme cela que les systèmes de reconnaissance d’objets ou de reconnaissance faciale fonctionnent.

Parlons de de k-NN

L’algorithme k-NN est une adaptation mathématiques de ce que l’on fait instinctivement tous les jours.

Si je veux acheter un livre, je demande leur avis à mes amis qui ont des goûts similaires aux miens, s’ils sont une majorité à avoir aimé, j’ai de grandes chances d’aimer ce livre aussi. Cet algorithme est appelé k-NN (k nearest neighbors : k plus proches voisins).

Aujourd’hui, des informations sur nous sont disponibles partout à travers le web. Ainsi l’algorithme k-NN de Facebook par exemple, peut vous comparer avec des gens en dehors de votre cercle d’amis.

On peut imaginer un calcul de similarité entre deux profils, basé sur leur âge, les pages ou les publications qu’ils ont aimé, leurs nombres d’amis et pleins d’autres critères. Et à partir de là, ils vous proposeront des publicités en lien avec ce que vous aimez.

Reconnaissance d’images grâce au k-NN

Les difficultés de ces méthodes résident dans le calcul des similarités et dans le choix des critères. Ils doivent être indépendants, non corrélés, on doit tous les avoir et d’autres hypothèses qui compliquent l’étude considérablement les choses. Ça sera le sujet d’un de mes futurs articles.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *