[ANALYSE] Les mystères de l’algorithme sous l’emprise de notre imagination

N’entendons-nous pas partout ce type d’affirmation : « L’algorithme de Facebook a changé… c’est pour cette raison que je ne vois plus les mêmes posts ou bien que je reçois de nouvelles publicités. » ? On s’attaque aussi à ceux d’Instagram et ainsi de suite. Or, les algorithmes autour de nous sont bien plus présents que nous ne l’imaginons, plus dynamiques et diversifiés.

Généralement associé, de manière réductrice, à l’apprentissage automatique, l’algorithme est en définitive un ensemble d’instructions à suivre. Comme dans le cas d’une recette de cuisine, où nous suivons un certain nombre d’instructions, les algorithmes sont simplement des procédés codés.

Aussi, les algorithmes ne sont pas nécessairement numériques. Ils peuvent tout simplement être une liste de tâches à effectuer, comme dans le cas de la recette de cuisine. Mais puisque nous sentons beaucoup de mystère autour de l’intelligence artificielle, nous attribuons une sorte de magie aux algorithmes.

« Les gens ont besoin d’un mot pour décrire le monde confus, opaque et parfois douteux de l’apprentissage automatique, et algorithme est en train de devenir ce mot. »

Moyens I/O

Lorsque nous évoquons l’algorithme de Facebook, par exemple, nous le démonisons un peu, par crainte de l’inconnu. Mais pour éviter les confusions de genre et surtout, afin de démystifier les algorithmes, prenons un peu de temps pour tenter de nous y retrouver, à travers tous ceux-ci.

DÉFINITION

Selon Wikipédia: Un algorithme est une suite finie et non ambiguë d’opérations ou d’instructions permettant de résoudre un problème ou d’obtenir un résultat.

I. CINQ ALGORITHMES CÉLÈBRES

Il est amusant de voir que l’algorithme en tant que suite d’instructions n’est pas récent et nous pouvons en énoncer de très anciens.

1. L’algorithme d’Euclide : 300 ans avant J.-C., Euclide crée un algorithme permettant de trouver les plus grands diviseurs communs de deux nombres ou entiers positifs.
2. Celui de Dijkstra : Inventé en 1957 par un chercheur hollandais, l’algorithme permet de déterminer le plus court chemin d’un point à l’autre en tenant compte des réseaux routiers existants.
3. PageRank : Il fut inventé en 1997 par Larry Page, cofondateur de Google, pour classer des pages Web en fonction de leur popularité et de leur influence sur le réseau.
4. CRUSH : Algorithme de probabilité utilisé par la police de Memphis, au Tennessee, pour déterminer les secteurs à haut risque de criminalité et y déployer des patrouilles policières.
5. TrueAllele : Il permet d’effectuer le génotypage probabiliste rapide de l’ADN pour résoudre des crimes.

Et il en existe une multitude. Certains sont aujourd’hui contestés, car ils peuvent conduire à l’exécution de tâches discriminantes par l’entremise de biais causés soit par la pauvreté des données ou une mauvaise classification de départ.

II. QUELQUES TYPES D’IMPLANTATION ALGORITHMIQUES

a) Récursif versus itératif

L’algorithme est dit récursif parce qu’il s’invoque lui-même.

Monsieur Jourdain, dans le Bourgeois Gentilhomme de Molière, explore toutes les manières galantes d’écrire un billet doux : « Belle Marquise, vos beaux yeux me font mourir d’amour... D’amour, me font mourir, vos beaux yeux, Belle marquise… ». Il utilise ainsi un processus récursif en énumérant toutes les occurrences possibles.

Par ailleurs, un algorithme est dit itératif, lorsqu’il existe une boucle de répétition. Les solutions sont alors successivement raffinées.

b) Logique

C’est la base de la programmation logique. L’algorithme est alors une déduction logique contrôlée. Les propositions de base sont définies et les déductions appliquées à ces propositions (ou axiomes) sont également prédéfinies.

c) En série versus en parallèle

De manière générale, on suppose que les tâches des algorithmes sont exécutées une par une, c’est-à-dire en série.

Par contre, certains algorithmes fonctionnent de façon parallèle, en traitant plusieurs instructions en même temps. Les algorithmes itératifs peuvent procéder en parallèle, comme le font les algorithmes de tri.

d) Déterministe ou non

Les algorithmes déterministes accomplissent des tâches prédéfinies pour résoudre un problème. Par ailleurs, les algorithmes non-déterministes ont l’autonomie de choisir, à chaque étape, la meilleure solution.

On voit clairement que les types d’implantation des algorithmes ne sont pas tous les mêmes. Cependant, certaines caractéristiques se recoupent et nous donnent un meilleur portrait des familles d’algorithmes.

Un autre aspect que nous pouvons analyser est la manière de concevoir les algorithmes. Il en existe plusieurs.

III. DIFFÉRENTES FAÇONS DE CONCEVOIR UN ALGORITHME

a) La division (Clustering)

De manière récursive, l’algorithme divise les tâches en sous-ensembles afin de simplifier au mieux les instructions à suivre. Une liste à trier, par exemple, est divisée en sous-listes et triées séparément. On parle alors de partitionnement des données.

b) La programmation dynamique

Ici, les sous-ensembles créés peuvent être superposés dans l’analyse algorithmique. Le dynamisme est permis par la mémorisation sous forme de cache et la solution optimale du problème s’obtient à partir des solutions optimales de sous-problèmes.

c) La méthode gourmande (Greedy algorithm)

Dans ce cas de figure, les sous-problèmes n’ont pas besoin d’être connus à chaque étape du processus. L’algorithme procède à une recherche d’arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM). L’algorithme de Kruskal est un bon exemple. Il permet, entre autres, de supprimer les liaisons maritimes les moins rentables en préservant l’accessibilité aux différents ports.

d) La programmation linéaire

Le terme est introduit par George Dantzig vers 1947. C’est un procédé qui nous permet de trouver la solution optimale pour un problème donné. La solution optimale est celle qui représente le meilleur résultat possible face à un problème donné. Cela consiste donc à trouver la meilleure manière possible d’optimiser un objectif donné.

e) La réduction

Il s’agit ici de transformer un problème en un autre, mais plus simple à résoudre. En mathématiques, cela consiste par exemple, à trouver la médiane d’une liste non ordonnée. L’algorithme commence par trier une liste pour en tirer directement la valeur moyenne.

f) L’utilisation des graphes

Le procédé consiste à générer des vues d’ensemble au moyen de graphes ou, autrement dit, de structures de données. C’est une forme de modélisation. Ce type d’algorithme permet de résoudre des problèmes comme ceux du jeu d’échecs.

g) La probabilité

Cette méthode probabiliste fonctionne au moyen de statistiques. On peut voir trois modèles différents:

1. Probabilistique : Qui fait des choix aléatoires.
2. Génétique : Imitant le principe de survie. Cette méthode utilise les données biométriques pour envisager les meilleures solutions.
3. Heuristique : L’objectif de ce procédé est de trouver la solution la plus économe.

CONCLUSION

Puisque nous avons nommé les expressions courantes qui concernent les algorithmes de Facebook. Il est à noter que ce géant a dévoilé mercredi dernier une nouvelle option pour les administrateurs de site, nommée Admin Assist. Elle permet aux administrateurs d’élaborer des critères afin de modérer les commentaires. Ce nouvel algorithme donnera la chance aux webmasters de vérifier automatiquement les contenus et commentaires potentiellement problématiques.

Ainsi, force est de croire que nous avançons d’un algorithme à l’autre et que cette marche progressive va bel et bien continuer. Autant en savoir le plus possible sur cette manière de procéder et sur la place grandissante de ces « souffleurs discrets du présent, ces colocataires de nos vies personnelles » que sont les algorithmes, comme le précise la journaliste Isabelle Paré, dans Le Devoir.

BIBLIOGRAPHIE

Flajolet, Philippe; Parizot, Étienne; Qu’est-ce qu’un algorithme ?; Interstices, 2004.

McFadden, Christopher;15 of the Most Important Algorithms That Helped Define Mathematics, Computing, and Physics; Interesting Engineering, 2018.

Moyens I/O; Que sont les algorithmes et pourquoi mettent-ils les gens mal à l’aise?; Moyens I/O, 2020.

Paré, Isabelle; Quelques algorithmes connus; Le Devoir, 2017.

Paré, Isabelle; La main invisible des algorithmes; Le Devoir, 2017.

Paré, Isabelle; Pour s’y retrouver parmi les algorithmes; Le Devoir, 2017.

Scriptol; Classification des algorithmes; (scriptol.fr)