structure

header

lettre mu, logo du site manthano.fr

μανθάνω

nav

aside

footer

les algorithmes

accueil

logo-utl.jpg
la passion des algorithmes
organigramme%20jeu%20deviner%20un%20nombre.jpg

plan

la passion des algorithmes
  • Qu'est-ce qu'un algorithme ?

histoire, exemples, définition(s)

  • Les algorithmes sont ils nécessaires ?
  • Les algorithmes sont ils dangereux ?
  • Conclusion

la maîtrise citoyenne : un enjeu collectif.

qu'est-ce qu'un algorithme ?

Pré-histoire

Antiquité

Les algorithmes ont existé bien avant les ordinateurs. Leur histoire est indissociable de l'histoire des mathématiques d'abord, puis de l'histoire de l'informatique.
Deux mille ans av J.C. les sumériens utilisaient des algorithmes de calcul : trouver une carré dont la surface est égale à 2.
Ces algorithmes sont repris par les mathématiciens grecs

(voir les fichiers netlogo)

  • calcul du nombre d'or ou du nombre π (Archimède, -200).
Al-Khwārizmī

Le terme algorithme vient du terme algorismus, latinisation de Al-Khwārizmī (Bagdad, IXème siècle)
Son origine est mathématique : logistique et algébrique, conjugaison du calcul et du littéral.
Al-Khwarizmi décrit les méthodes pour effectuer les opérations de base (addition, multiplication, ...) avec des chiffres décimaux que les arabes viennent de rapporter d'Inde. Il est à noter qu'Al-Khwārizmī invente en même temps le type de représentation et d'organisation des calculs qui va donner l'algèbre.
statue%20d'Al-Khwarizmi.jpg

définition

Un algorithme est une séquence d’instructions à suivre minutieusement pour arriver au résultat voulu par une série d’étapes simples et ennuyeuses.
exemples :

  • effectuer une multiplication (à la main !)
  • une recette de cuisine (pas tout à fait vrai : elle demande un "coup de main")
logigramme.png
des lapins de Fibonacci ...

Au début du XIIIème siècle Léonard de Pise (dit Fibonacci) traduit les textes arabes.
C'est lui qui, dans son Liber abaci, après une vaine tentative au Xème siècle due à Gerbert d'Aurillac (futur pape Sylvestre II), va introduire les chiffres "arabes" en Occident.
Il est aussi connu pour ce qu'on appelle maintenant la suite de Fibonacci.
nombre%20d'or%20Fibonacci.jpg

... aux graines de tournesol

La modélisation est elle une démonstration ?
Changement de paradigme pour les sciences qui, depuis les Grecs en mathématiques et depuis le XVIIème siècle en physique, sont fondées sur le raisonnement à partir d'axiomes et de lois.
Dans les sciences classiques, même si les lois sont induites à partir de l'expérience donc de l'observation des données, elles doivent être démontrées. Le paradigme algorithmique tend souvent à faire croire que "le fait que ça marche est une preuve de vérité".
Ce changement de paradigme dans les sciences est accompagné d'un bouleversement socio-culturel analogue dans les sociétés.
(voir le fichier netlogo)
modélisation
spirales%20tournesol.png

L'informatique

Les précurseurs

Pascal (1642) : première "machine à calculer" (Pascaline)
Babbage (vers 1850) : tentative de création d'une "machine analytique" à cartes perforées
Ada Lovelace (vers 1850) : premier programme informatique pour la machine de Babbage
machine%20de%20Babbage.jpg

Turing, Church, Shannon, Von Neumann
  • La machine (théorique) de Turing (1936)

Elle permet de calculer en déplaçant une bande de papier contenant les données à traiter devant une tête de lecture / écriture munie du programme à exécuter.

  • Turing et Church prouvent que tout ce qui est calculable peut l'être avec cette machine.

Ils en améliorant le procédé : le programme de traitement est lui aussi écrit sur la bande de papier et la tête de lecture / écriture "universelle" traite les données et le programme de manière équivalente (repris par von Neumann).

  • Shannon (milieu du XXème siècle) crée la théorie de l'information (et la notion de bit) qui va permettre de coder et de traiter tout type de données (mot, image, musique, ...) par la machine de Turing.
informatique = données + algorithmes (programmes)
Ordinateurs et Internet
  • le premier ordinateur ENIAC vers 1945
  • l'internet fin des années 60
  • le web au début des années 90

En parallèle, développement des langages de programmation.
Eniac.jpg

Exemples

Les algorithmes "classiques"
  • algorithmes mathématiques

dans le domaine des statistiques, des sciences de l'ingénieur (simulation), ...

  • algorithmes de tri
  • le théorème des 4 couleurs

théorie des graphes ; exemple important de "changement de paradigme" en mathématiques.
the%20art%20of%20computer%20programming.jpg

Le cryptage RSA (Rivest, Shamir, Adleman)

Protocole R.S.A simplifié :

  • Amandine choisit deux nombres premiers P et Q qu'elle multiplie. Le nombre \(C=P \times Q\) est la clé publique.
  • Bernard veut envoyer un message secret \(M\) (suite de nombres) à Amandine.

On utilise pour cela le petit théorème de Fermat qui démontre qu'il existe deux fonctions \(f\) et \(g\) telles que :

  • Bernard code \(M\) avec \(f\) qui ne dépend que de \(C\) on obtient un message crypté \(f(M)\)
  • Alice peut alors décoder \(f(M)\) pour lire le message \(M\) en se servant de \(g\) qui ne dépend que de \(P\) et \(Q\)

\(f: M → f(M)\) à l'aide de la clé publique C d'Amandine
\(g: f(M) → M\) à l'aide de P et Q
Sécurité du protocole R.S.A :
La sécurité de ce codage à clef publique, repose sur la difficulté qu'il y a à calculer les facteurs premiers de \(C\).

Les algorithmmes "sociaux"
PageRank (Larry Page)
  • Le principe de base est d'attribuer à chaque page une valeur - la pagerank - d'autant grande qu'est grande la somme des PageRanks des pages qui pointent vers elle (elle comprise, s'il y a des liens internes). Le PageRank est une mesure de centralité sur le réseau.
  • L'algorithme est une marche aléatoire sur le graphe du Web. Il s'agit d'un processus de Markov. La taille (gigantesque) de ce graphe et son évolution dynamique (modifications de pages et hyperliens, connexion ou déconnexion de serveur web) rendent cependant impossible un calcul direct : des algorithmes d'approximation sont utilisés.

Le théorème de point fixe est le concept mathématique qui a permis l'invention du PageRank. Celui-ci permet en effet d'assurer que le calcul du PageRank est possible.
En dehors de cet algorithme public on utilise d'autres méthodes "secrètes" : contrôle des liens fictifs, mesure de la qualité des pages (web thématique), mots clés (web sémantique), ... sont utilisées.
(voir fichiers netlogo)

Intelligence artificielle

Ceci sera sans doute traité dans une prochaine conférence
2 conceptions de l'intelligence artificielle : faire comme le cerveau humain ou faire autrement !

L'apprentissage :
intelligence artificielles (années 70) -> appprentissage automatique (années 90) -> apprentissage profond (deep learning 2010)
apprentissage_profond.jpg

Applications

  • compréhension de la parole (Siri 2012, google sur android), identification du contenu d'une image (personne ou lieu), diagnostic d'insuffisance cardiaque sur une imae IRM
  • jeu de dames : on explore une partie significative de l'arbre du jeu pour démontrer que l'algorithme est optimal.
  • jeu d'échecs (Deep Blue) : on n'a pas cette possibilité actuellement (d'ici 20 ans sans doute).

parcours du cavalier

  • jeu de go (AlphaGo) : apprentissage par renforcement. Un réseau de neurones s'affronte lui même puis on recommence avec le réseau résultant en réinjectant les résultats obtenus.

Pourquoi les algorithmes sont nécessaires

La sécurité informatique

En informatique le principal bug se trouve entre le clavier et la chaise
le%20principal%20bug%20est%20entre%20la%20chaise%20et%20le%20clavier.jpg

Les erreurs dans les algorithmes :

  • Exemple du lancement de la fusée Ariane 5

4 juin 1996, Un bug dans la représentation des données entraîne une propagation en domino à l’ensemble du programme et s'ensuit alors le crash complet du logiciel de navigation et donc de la fusée, coût: 400 millions de dollars)

  • Preuve des programmes

P ≠ NP ?

La complexité des problèmes
P est l'ensemble des problèmes qui sont solubles en temps polynomial : si on double la taille \(n\) des données sa complexité (temps + espace utilisé pour le résoudre) est multipliée par un facteur constant \(n^k\).
NP est l'ensemble des problèmes dont on peut vérifier la solution en temps polynomial. En général la complexité de ces problèmes est exponentielle (multipliée par \(k^n\))
(pour \(k=2\) et \(n=100\) par exemple on obtient \(n^{k}=10000\) et \(k^n=10^{30}\))
exemples : le problème du voyageur de commerce, la décomposition en facteurs premiers.

Big Data

  • Modélisation et prévision : exemple du réchauffement climatique.
  • Massification de la population, des objets, des données, des informations
  • L'échelle des octets
taille représentation exemples
octet une lettre de l'alphabet  
unité égale à 8 bits parmi 256 (utf-8)  
kilo octet (Ko) une page d’un livre  
mille octets    
méga octet (Mo) un livre de mille pages environ  
un million d’octets    
giga octet (Go) une bibliothèque comportant séquençage d'un génome : 1 Go
un milliard d'octets un millier de livres une heure de video : 10 Go
téra octet (To) la B.N.F  
mille milliards d'octets    
péta octet (Po) l’ensemble des cultures humaines ? LHC : 15 Po de données par an
un million de milliards d'octets    

Pourquoi les algorithmes sont dangereux

Introduction

"L'entreprise du futur n'aura plus que deux employés : un homme et un chien. L'homme sera là pour nourrir le chien. Le chien sera là pour empêcher l'homme de toucher aux ordinateurs" [Warren Bennis]
ordinateur%20chien%20homme.jpg

Le contrôle de la population

  • Origine historique

statistiques prévisionnelles (à partir du XVIIIème siècle)

  • Back-doors et NSA

concentration des données et de leur traitement par des organismes d'Etat

  • Les GAFAM [Google, Apple, Facebook, Amazon, Microsoft]

concentration des données et de leur traitement par des groupes privés
les%20GAFAM.png

Un nouveau paradigme

  • dans les sciences physiques, biologiques et sociales les modèles ne sont plus produits par une théorie préalable puis confrontés aux données mais produits par les données et confrontés à leur efficacité.

On passe d'un modèle déductif à un modèle inductif
Les données sont amnésiques de leur contexte de production. Ce qui engendre une uniformisation.

  • Passage d'un modèle dans lequel on pose sur le monde une hypothèse de connaissance vers un monde "boite noire" qui produit un résultat efficace.
  • une idéologie : le réel ce sont les données !

Les sujets deviennent des réseaux de données.

  • confusion entre corrélation et causalité
  • "prédire n'est pas expliquer" [René Thom]
  • Calculabilité inductive. Les connaissances (statistiques par exemple) liées à l'action sont remplacées par des calculs d'apprentissages : on n'a plus besoin des catégories préalables définies à priori par les statisticiens. Les traces que nous laissons se comparent entre elles.

(illustrations dans les pages suivante, en grande partie issue des travaux d'Antoinette Rouvroy en particulier)

La modélisation des comportements

autorité, popularité, réputation, comportement
"Le plus grand nombre produit l'ordre désirable des informations adressées aux autres"
On est passé avec Google (Stanley Brin et Larry Page) de l'importance des liens cliqués à l'importance des liens cités.
Ce modèle est passé dans les réseaux sociaux à celui de "l'influence et de la réputation des amis" récursivement.
On en arrive maintenant à une prédiction généralisée (recommandations) imputée aux comportements. La trace des comportements de mes "amis" (Facebook) devient l'action désirable de mon comportement.
On assiste à un véritable profilage par la relation.

Dé-responsabilisation des décideurs

Nous avons affaire aujourd’hui à un modèle de production et de distribution de l’information qui rend difficile l’identification même des responsabilités.

Ne pas déposer un substitut de la légitimité du jugement dans la machine.

la gouvernementalité algorithmique

  • Logique non causale, de pure corrélation (par anonymisation par exemple) qui engendre une nouvelle forme de discrimination "incontestable", "injustifiable". Les algorithmes se désintéressent de ce qui fait la singularité des individus et de ce qui les rattache à des contextes collectifs socialement éprouvés au profit de catégories impersonnelles mais prédictives
  • Intensification et radicalisation de ces processus. Gouvernance non plus par les nombres mais par les signaux - les phéromones numériques difficiles à appréhender par l'individu mais traitées par les algorithmes.
  • Le rêve de Laplace : tout est calculable, tout est prévisible.
  • Les GAFAM et les organisations d'état utilisent plutôt les algorithmes et le Big Data pour optimiser l'état de fait et non pour découvrir des potentialités non repérées jusqu'ici, ce qui dispense d'interroger l'état de fait.
  • Discours politique prégnant : "Enregistrer l'état de la société".

On répond à la demande sur le mode du réflexe. On n'a plus besoin de faire un projet qui transcende la réalité. Le politicien se transforme en sismographe.

Un système révolutionnaire ?

  • D'un certain point de vue il n'y a jamais eu d'instrument plus efficace pour le conservatisme.

Optimiser les états de fait est l'art de ne pas changer le monde.
On bannit toute possibilité d'évènement (notion de point fixe). Changer le monde suppose d'avoir un projet, un projet qui transcende l'état de fait pour changer quelque cchose qui n'est pas déjà dans les données.
Fin de la théorie.

  • Cela défait nos représentations (ce qui peut être positif)

Mais les espaces ouverts sont laissés aux prédateurs du profit. On n'a pas de politique de ces espaces de création et de liberté : grignotement de l'espace public.

  • Rétroaction bayésienne, apprentissage profond

La nouveauté c'est qu'elle est calculable, renforcée par les progrès de la neurobiologie.
Le modèle des réseaux de neurones remporte actuellement de grand succès dans la reconnaissance des formes, dans la reconnaissance de la parole, dans la traduction.
Cependant pour le moment les modèles sont supervisés par les hommes : pour que le réseau reconnaisse un chat il faut qu'on l"éduque en lui montrant des milliers de chats. Mais on l'éduque avec nos biais ! A nouveau le renforcement.

Chaque modèle emporte une forme de rationalité, donc aussi d'aliénation et de domination.

Craintes ancestrales ou plus récentes

  • Platon Phèdre
    «[L’écriture] ne peut produire dans les âmes, en effet, que l’oubli de ce qu’elles savent en leur faisant négliger la mémoire. Parce qu’ils auront foi dans l’écriture, c’est par le dehors, par des empreintes étrangères, et non plus du dedans et du fond d’eux-mêmes, que les hommes chercheront à se ressouvenir. Tu as trouvé le moyen, non point d’enrichir la mémoire, mais de conserver les souvenirs qu’elle a. Tu donnes à tes disciples la présomption qu’ils ont la science, non la science elle-même. Quand ils auront, en effet, beaucoup appris sans maître, ils s’imagineront devenus très savants, et ils ne seront pour la plupart que des ignorants de commerce incommode, des savants imaginaires au lieu de vrais savants.»
  • Penser, est-ce calculer ? [ voir Daniel Parrochia ]
  • Qui contrôle (les algorithmes) ?

Solutions

Justification des décisions (anti boite noire) plutôt que se retrancher derrière la soit disant objectivité des algorithmes.
Le propre de l'être humain c'est sa capacité à effacer ses traces, à mentir, à inventer (Derrida) ; sa capacité à se raconter au delà des données objectives. Il faut paramétrer les algorithmes pour qu'ils nous montrent les limites de nos représentations afin de pouvoir jouer avec, dans la narration par exemple.

Conclusion : la maîtrise citoyenne

  • Les algorithmes doivent être contrôlés, encadrés.
  • Un exemple : les logiciels libres.
  • Le problème est politique

Imaginer et produire des technologies mises au service des humains et non des intérêts privés.
Les civilisations humaines ont toujours été et sont encore au carrefour de la confrontation de leur imaginaire et du réel.
La civilisation grecque a construit la rationalité mathématique, la science, la philosophie et l'idée de démocratie au travers et au prix de la reconstruction de son imaginaire mythique.
Léonard de Vinci s'excusait auprès de Dieu de faire de la science au détriment de l'art. En fait il faisait les deux.
Nous devons assumer à notre tour de confronter la science (les algorithmes en l'occurrence) et la philosophie.

page de fin

logo-utl.jpg
Je vous remercie de votre présence et je remercie l'Université du Temps Libre de Tarbes et Bigorre.

Les documents projetés ont été réalisés entièrement à l'aide de logiciels libres sur un système libre Gnu / Linux.


cc-by-sa.png