Dernier article sur trois publiés sur le site Alliance Géostratégique le 12 octobre 2012
http://alliancegeostrategique.org/

Compresser pour Régner – Acte III- Epilogue

Ce troisième volet requiert de la part du lecteur un peu plus d'attention que les deux premiers, c'est normal, c'est le plus profond des trois....

Tout ne se compresse pas !

Nous considérons ici toutes les techniques de compression de l'information sans perte, présentes et à venir , et allons montrer sans gros effort mathématique qu'il existe des informations incompressibles quels que soient les algorithmes appliqués (existants ou pas encore inventés, c'est ce qui fait le charme de ce résultat profond).

Partons du fait que toute information finie peut s'écrire, via une convention de codage fixée, sous la forme d'un mot binaire (une suite finie de 0 et de 1)

Par exemple, M= 001011100001, je ne sais pas ce que ce mot signifie, mais il fait partie de l'ensemble des 2^12 mots binaires de longueur 12; il y a en effet 2 choix pour chaque bit d'information donc 2x2x.....X2 possibilités.
Considérons maintenant un mot binaire quelconque de longueur n.
Il existe 2^n mots binaires différents de longueur n; chacun de ces mots peut a priori être compressible; si un tel mot M est compressible, alors sa compression est de taille strictement inférieure à n, c'est-à-dire n-1, ou n-2, ...., ou 1 ou 0; il y a donc au plus :
2^0 + 2^1 + ..... + 2^(n-1) mots de compression possibles pour mon mot M fixé.
cette somme est la somme des termes d'un suite géométrique et un résultat classique de lycée me dit qu'elle vaut (2^n – 1)/(2-1) soit 2^n – 1 mots possibles !
Voyez-vous le problème ? D'un coté j'ai 2^n mots à compresser mais de l'autre je n'ai que 2^n – 1
possibilités (au plus) de codage compressif ....
Il reste donc un mot de longueur n parmi les 2^n qui n'admet aucune compression !
C'est mon mot totalement incompressif, je le tiens ! ou plutôt, je viens de prouver son existence car je suis dans l'incapacité absolue de vous dire de quel mot il s'agit... c'est purement un théorème d'existence comme les aiment les mathématiciens.

Que peut-on en faire ? En premier lieu, on peut affirmer que quel que soit le futur logiciel de compression sans perte à venir mis en vente, il ne faudra pas croire le vendeur qui vous affirmera sans sourciller que son produit compresse tout : ce sera faux, profondément faux!

Le hasard ne se résume pas...

Il faut rapprocher l'existence de ce mot particulier de l'aléatoire qui est si mal modélisé par les probabilités et si bien par la théorie algorithmique de l'information (celle de Kolmogorov).
On y est !, l'aléatoire se cache derrière cette incompressibilité de l'information :
« Est aléatoire ce qui est incompressible ! » (tel sera mon premier tweet)
ou encore : « Le hasard ne se résume pas ! ».
Ce principe quasi philosophique se démontre sans peine, nous l'avons fait en quelques lignes;
il induit de nombreux résultats utilisables lorsque l'on cherche à mieux comprendre un phénomène aléatoire.

On peut à présent s'interroger sur la proportion d'incompressible par rapport au compressible

Effectuons un simple dénombrement : il existe 2^n mots binaires de longueur n , regardons ensuite ceux qui se compressent en une représentation plus courte de longueur n-q (plus q est élévé et plus je compresse). Il y en a au plus 2^n-q , si bien que la proportion des mots binaires de longueur n compressibles en mots binaires de longueur n-q vaut 2^n-q / 2^n soit 1/2^q. Ce qui est très très faible, dès que q augmente un peu !! ;
Ce simple calcul nous montre que le compressible sans perte est rare dans la nature, et qu'il existe beaucoup plus d'incompressible (d'aléatoire donc) que de compressible.
On peut relativiser cette dernière constatation en précisant que l'information qui nous atteint (presse,
radio, tv, internet, etc) et que nous manipulons quotidiennement est très structurée, très organisée et donc en général bien compressible sans perte.

L'incompressible se trouve dans la partie aléatoire de l'information :

Imaginons que je joue à pile ou face avec une pièce de monnaie non truquée, et que je répète ce jeux 200 fois de suite en notant chaque résultat sous la forme 1 pour Face et 0 pour Pile.
A l'issue de mon jeu, j'aurai une chaine binaire de longueur 200 du type :
M = 110100011011110.......00.
Imaginons ensuite que je souhaite transmettre mon résultat en le twittant :
je suis limité à 140 caractères , il faut donc que je compresse sans perte mon mot M pour passer d'une longueur de 200 à 140.
J'applique alors mon petit calcul rédigé plus haut :
je me retrouve avec une probabilité de 1/2^(200-140)= 1/2^60 soit 0,0000... avec 19 zeros suivis de 867 chance de pouvoir twitter mon résultat sans le dégrader, 10^-19 c'est quasiment l'évènement IMPOSSIBLE.
Moralité : mon mot M ne peut pas passer par twitter !!! car il contient a priori bien trop d'aléatoire.

Pour cloturer ces résultats déconcertants, il faut préciser que le niveau de compression sans perte maximal possible pour un mot binaire donné est en fait lié à sa complexité de Kolmogorov, c'est-à-dire à la longueur du plus court programme fonctionnant sur une machine de Turing fixée , donnant ce mot M en sortie et s'arrêtant.
Les gros mots sont lachés , mais c'est la réalité : la complexité de Kolmogorov se cache irrémédiablement derrière ces problèmes de compressions de données et d'alèatoires, c'est elle le réel maître du jeu !

Que pensent les philosophes de la compression ?

Les citations de cette section sont empruntées au bel article de Patrick Williams sur les formats courts publié dans Philosophie Magazine – Juin 2012.
Il y a clairement deux écoles : La première affirme (en simplifiant un peu) que le format court est quasiment incompatible avec une pensée profonde :
« La pensée a besoin de place pour dérouler son chemin, déployer ses arguments et former une image dans l'esprit du lecteur . On imagine mal l'Ethique de Spinoza résumée en quelques formules chocs, sans sa série de propositions, de scolies, de démonstrations, qui lentement, très lentement infuse dans l'esprit de celui qui lit » selon Gilles Finchelstein auteur de « La dictature de l'urgence - Fayard 2011 »
Un défaut souvent exposé du format compressé est qu'il implique une profusion, un papillonage qui étourdit notre attention.
Selon le philosophe William James, « L'attention est la prise de possession par l'esprit, sous une forme claire et vive, d'un objet ou d'une suite de pensées parmi plusieurs qui semblent possibles.
Elle implique le retrait de certains objets afin de traiter plus efficacement les autres. »
C'est ce retrait qui pose problème dans le cas d'une information compressée.

Et puis, on trouve un autre courant de pensée concernant les formats brefs :

Le philosophe Anglais Alain de Botton affirme avec un brin de malice qu'un bon nombre d'essais philosophiques ont une fâcheuse tendance à délayer leur pensée, alors même que l'essentiel de leur thèse pourrait se résumer aux quelques lignes qui ornent la quatrième de couverture...
« Nous sommes habitués à l'idée qu'un concept n'est valable que s'il prend 400 pages pour se déployer! Mais la vérité est que l'immense majorité des livres d'idées qui sortent aujourd'hui pourraient être réduits à un tiers de leur taille sans en souffrir. J'attends avec impatience le jour où l'on pourra présenter une thèse de doctorat sous la forme d'aphorismes! »
D'autres philosophes affirment, (comme le disait Jean-François Lyotard) que « Le postmodernisme est marqué par la fin des grands récits ; d'un simple point de vue psychologique, il n'existe plus un idéal du moi suffisamment fort qui permette un Kant ou un Hegel »
Sans oublier que Kant ou Hegel n'étaient pas stimulés par un bombardement incessant d'informations et de propositions hétérogènes et que ce calme informationnel était propice à la rédaction d'écrits plus longs.

La compression de l'information semble être un moment inévitable de la pensée occidentale; il ne découle pas seulement des nouveaux outils technologiques mais correspond à une phase de l'histoire

où nous ne pouvons plus « faire le long ».
Alain de Botton explique : «  Les fragments et les maximes se révèlent idéaux pour exprimer des vérités ambigues. Et parce que tant de nos vérités actuelles semblent ambigues, la forme courte est parfaitement adaptée à notre époque »

Roland Jaccard défend avec vigueur la pensée concise : pour lui, l'aphorisme est un art de vivre, un acte autant moral qu'esthétique témoignant d'un respect scrupuleux porté aux autres et à soi-même;
il ajoute : « s'étendre sur un sujet est une forme d'impolitesse », j'espère ne pas être impoli avec ces 3 articles ???
« Dans un monde flottant, l'aphorisme est une bouée de sauvetage. La forme révèle le fond mieux que n'importe quelle démonstration : Ce qui est bref et bon est deux fois bon ! »
Il conclut par «  L'art de l'aphorisme relève de la guérilla. La philosophie classique, elle, n'est jamais qu'une forme dévoyée de la religion. Elle appartient au monde d'avant. De là vient son charme un peu suranné . L'aphorisme est une clef pour ouvrir les psychismes »
Alain de Botton met en pratique tout ce qui précède et publie sur tweeter des maximes en 140 caractères afin de les tester grâce aux réactions de ses followers : il trouve un écho instantané à ses intuitions et oriente son travail en fonction des réactions.

Enfin, il y a cette interrogation : serions-nous au début d'une nouvelle époque ?

D'après Luis de Miranda, « les pensées qui s'expriment en bref sont les éléments d'une série à venir,comme des briques, l'expression d'une recherche de système qui n'est pas encore là. La brièveté est un moment nécessaire qui annoncerait le début de nouveaux mythes, d'un nouveau cycle long : un Platon 2.0 verra-t-il le jour ? »

A titre personnel, je rejoins et adhère à la thèse de Miranda : je suis convaincu que cette montée en puissance des formats compressés résulte d'une auto–organisation des quantums d'information circulant sur notre planète. L'information se restructure d'elle-même, évolue dans sa forme vers une morphologie plus riche, plus dense , et finalement compatible avec l'émergence d'une  conscience globale , une intelligence numérique unitaire.

Pardon de n'avoir pas compressé tout cela....



















Les "portes du code" - Matrix

Second épisode consacré à la compression de l'information et publié le 12 octobre 2012 sur le site Alliance Géostratégique
http://alliancegeostrategique.org/

Compresser pour Régner – Acte II/III

« tournez tournez bons chevaux de bois,

tournez cent tours tournez mille tours,
tournez souvent et tournez toujours,
tournez tournez au son des hautbois. »
Chevaux de bois, « Bruxelles », Romances sans paroles, Paul Verlaine.

Compressons Verlaine !

Compresser une information consiste à la transformer afin de lui donner une forme plus courte.
Ceci implique immédiatement deux types de méthodes de natures très différentes:

La compression sans perte qui va conserver l'intégralité de l'information tout en lui donnant une forme plus courte.

La compression avec perte, qui va volontairement dégrader l'information initiale afin d'en donner une forme réduite.

Observons un exemple simple de compression sans perte en partant de l'extrait du poème de Verlaine figurant en préambule :

Ce texte contient 23 mots, occupant une position numérotée de 1 à 23 et 125 lettres hors ponctuation.
Je peux réécrire l'extrait en précisant la position de chaque mot dans la phrase :
« tournez 1, 2, 7,10,13,16,18,19 bons chevaux de bois,
cent 8 tours 9,12 mille 11 souvent et toujours, au son des hautbois. »
celle-ci contient maintenant 91 lettres, soit un gain de 34 lettres par rapport au message initial.
Je n'ai perdu aucune quantité d'information puisque lorsque je décompresse cette phrase, je retrouve intégralement le texte d'origine !
On peut faire mieux via un nouvel algorithme de compression appliqué à ma précédente compression puis réitèrer le procédé jusqu'à une forme compactée de l'information non dégradée par rapport au texte initial.

La compression sans perte

Sans entrer dans le détail technique, il faut évoquer les algorithmes classiques de compression sans perte utilisés notamment pour coder les images :

Le codage de Huffman qui repose sur un codage statistique d'un fichier, octet par octet, sachant que plus les octets apparaissent souvent dans le mot initial et plus les codes qui les remplacent doivent être courts.

L'algorithme parcourt les données d'un fichier octet par octet ainsi que le nombre de fois où cet octet apparaît, il construit ensuite un arbre (graphe) en débutant par les feuilles jusqu'aux racines ;
les octets sont alors classés par ordre décroissant de fréquence d'apparition.
Cette technique est utilisée en partie dans les formats MP3 pour le son, et PNG.

Le RLE (Run-Lenght encoding) qui parcourt les données et recherche les octets identiques qui se suivent, l'algorithme trouve un octet répété successivement n fois, il crée une paire de données composée du nombre de répétitions n suivi de l'octet à répéter.

Ainsi, « A, A, A, la queue leu leu » se code par « 3A 1la 1queue 2leu »
cet algorithme est d'autant plus efficace que le mot initial à coder contient de nombreuses répétitions, ce n'est pas toujours le cas, mais pour des fichiers images, il est fréquent et fortement probable de trouver des pixels contigus identiques.Cette technique est utilisée dans le format PCX et BMP.

La classe des algorithmes Lempel Ziv : LZ77, LZ78, LZW
Il s'agit d'une famille de méthodes utilisant un dictionnaire et où les codes utilisent les indices des séquences d'octets placées dans le dictionnaire.
Ceci donne les formats d'images PNG , ZIP et GIF.

la compression avec perte

Arrêtons-nous maintenant sur quelques techniques classiques de compression avec perte :
On rappelle que l'information initiale y est volontairement et définitivement dégradée.

La transformée en cosinus discrète DCT

C'est une variante de la transformée de Fourier discrète qui est utilisée dans les formats MP3, JPEG, MPEG. Grosso-modo, cet algorithme transforme les pixels de l'image ou les séquences audio en fréquences puis élimine les fréquences qui ne sont pas pertinentes pour l'oeil ou l'oreille humaine.

Le DWT pour Discrete Wavelet Transform

Elle utilise une transformation classique de théorie du signal par ondelettes; celles-ci sont quantifiées pour être enfin tamisées afin de ne garder que la partie principale de l'information.
Le DWT est la base du format JPEG2000.

La compression fractale pour les images
Elle utilise la théorie du « rugueux » initiée par Benoit Mandelbrot.
Basée sur l'idée classique de similarité d'échelle, elle exploite le fait que toute image peut être vue comme un ensemble fini de transformations géométriques (rotations , translations, homothéties...) appliqué aux sous-motifs de taille variable qui composent l'image initiale.
Cette méthode exploite les propriétés géométriques de l'information initiale; elle s'applique en général assez bien aux paysages mais est particulièrement lente lors de la phase de compression (parfois 50 fois plus longue qu'un algo JPEG classique...).

 

Image initiale : 192ko

 

 

 

 

 

 

 

 

 

Image compressée par DWT , ondelettes de Haar : 15.6 ko

soit un taux de compression deux fois meilleur qu'avec jpeg mais une dégradation perceptible de l'image sur le haut...

Après ce tour d'horizon ultra rapide des algorithmes de compression usuels, il nous faut revenir à la question initiale : Tout peut-il se compresser ?
Si l'on compresse en acceptant de dégrader l'information, la réponse est immédiate et triviale :
OUI ! , tout se compresse avec perte ! Il convient simplement de se fixer un seuil d'acceptabilité de la perte d'information; c'est ce que l'on fait lorsque l'on se contente des informations fournies sur twitter.

Considérons maintenant notre question en n'autorisant que la compression sans perte :
la réponse est alors beaucoup moins évidente :
A priori, je peux imaginer un texte de longueur finie pour lequel je serai toujours en mesure de fixer un codage suffisamment astucieux pour en réduire sa représentation codée ! non ?
Et bien NON ! Ici, il ne faut pas se fier à son intuition première car elle est fausse.

Nous démontrerons ce théorème profond dans le dernier épisode consacré à la compression.

Cet article, premier d'une série de trois, est publié le 12 octobre 2012 sur le site Alliance Géostratégique.
http://alliancegeostrategique.org/

Compresser pour Régner – Acte I/III

Le développement de notre civilisation technologique induit une course effreinée à l'information, autant dans sa forme que dans sa vitesse de circulation.

Les volumes d'informations toujours croissants nous obligent à optimiser sa diffusion notamment par la compression des messages, au prix parfois d'une perte de sens.
Une question naturelle émerge alors :

L'information réduite est-elle nécessairement réductrice ?

On réunit ici quelques éléments d'analyse permettant de se forger une idée plus précise sur cette tendance qui impacte de nombreux secteurs, en particulier celui de la finance.

« Les jaunes sont verts »

Avant d'examiner les enjeux, succès et limites de la compression, arrêtons-nous un instant sur un tweet rédigé début septembre par un trader expatrié et facétieux :
« Les jaunes sont verts »
Je demande au lecteur, dans toute sa clémence, de bien vouloir m'excuser pour le sens péjoratif du terme « jaune » employé.
18 lettres et 4 mots pour ce tweet qui peut paraître elliptique s'il est sorti de son contexte ;
Il s'agit à l'origine de la reformulation compressée du message suivant :
«  Le gouvernement Chinois a adopté une loi de nature écologique »
Cette fois, en 52 lettres et 10 mots, l'ambiguité initiale est levée et il ne reste plus qu'à suivre le lien hypertexte pour prendre connaissance de la nature exacte de la loi adoptée.
Le taux de compression peut s'écrire 18/52 , soit environ un tiers.
Avec cette phrase, « les jaunes sont verts », on parvient au dernier niveau de compression possible ; celui-ci induit une perte d'information et une ambiguité si le message n'est pas associé à son contexte, mais le noyau de l'information initiale, bien que dégradé, subsiste.
L'optimum est atteint car si l'on retire encore un mot, par exemple verts, la phrase restante « les jaunes sont » perd tout son sens, l'information a disparu (idem pour les trois autres mots).
On conçoit alors facilement une structuration de l'information sous la forme d'un cône contenant dans ses sections les plus larges l'information complète, précise, sans ambiguité, puis les différents niveaux de compression dans les sections de cône plus étroites et pour finir l'information finale, fortement dégradée à la pointe du cône; chaque niveau étant relié au suivant par une fonction de compression ou un lien de type hypertexte par exemple.
C'est typiquement ce type d'architecture que l'on retrouve dans les flux d'informations circulant sur twitter.

La compression selon Homo Sapiens

On retrouve sur les parois de la grotte Chauvet, de la grotte de Limeuil en Dordogne, ou celle des trois frères en Ariège, des représentations compressées de mouvements de cheveaux ou de lions, peintes il y a près de 30 000 ans.
Les conventions graphiques utilisées à l'époque sont proches de celles adoptées par la BD ou le cinéma, en superposant différentes prises de vues lors du déplacement.
L'impression de mouvement est renforcée lorsque l'on approche des fresques une source lumineuse, par le jeu d'hombre et de vacillement de flamme.
Homo Sapiens a volontairement cherché à compresser sa représentation sans dégrader l'information initiale.

 

 

 

 

 

Scène de lions bondissant – grotte Chauvet -32000 ans

A partir du VII siècle avant J.-C, en Grèce, à l'ère des présocratiques, puis dans les siècles suivants, l'art de l'aphorisme s'est déployé : la formule courte et efficace était très à la mode, obligeant les philosophes de l'époque à reformuler en compressant sans perdre le sens premier de leur pensée.
Plus près de nous, Nietzsche aimait à juxtaposer des maximes courtes puis les croisait pour obtenir un résultat compilé plus profond ; c'était là encore une forme de compression.

L'art contemporain nous offre lui aussi de beaux exemples de compression avec les oeuvres militantes de Cesar ou d'Arman au début des années 60 visant à briser les codes et limites établies.

 

 

 

 

Compression d'une moto Honda par Cesar

L'acte de compression se retrouve partout, à travers le temps et l'espace, déformant parfois l'information jusqu'à sa perte.

Le comprimé d'aujourd'hui

La forme courte semble parfaitement adaptée à notre époque.
Il s'agit de faire du bref et percutant presque partout, « time is money », c'est ce qu'on applique dans la publicité, dans les émissions très courtes de tv de type zapping, dans certaines émissions politiques (où il est exclu d'émettre une idée durant plus de 3 minutes); dans la forme de certaines conférences scientifiques: celles du TED (Technology Entertainment Design) n'excèdent jamais les 18 minutes montre en main.
Les communications SMS, les tweets n'échappent pas à cette régle : 140 caractères maximum pour twitter, nous verrons dans un second billet ce que cela implique sur la nature et la forme de l'information transportée.
Le fluide d'information circulant sur twitter peut alors paraître terriblement superficiel et réducteur.
Peut-être ! Mais il participe à un mouvement de fond en tant que nouvelle forme de diffusion de l'information.
Analysé via un outil algorithmique pertinent, ce flot d'informations compressées peut devenir un baromètre particulièrement fiable lors d'une prévision :
Un exemple suffisament éloquent est l'étude récente réalisée lors de l'introduction en bourse de Facebook ;
Cette étude a mis en lumière une forte corrélation entre l'évolution en temps réel du cours de l'action Facebook et une mesure du sentiment du public sur twitter au regard de cet événement.

La courbe twitter précède et annonce celle du cours de l'action facebook...

 

 

 

 

 

Dans les billets – acte II III-, nous nous pencherons sur l'aspect théorique de la compression de l'information, sur les définitions sous-jacentes et les résultats limitant l'efficacité d'une compression.

Nous montrerons en particulier et de façon élémentaire qu'il existe des messages incompressibles quel que soit le type de compression envisagé!

Ce premier article pèse 714 Ko en format OpenOffice et peut certainement se compresser...

Dernier article d'une série de trois publiés le 19 septembre 2012 sur le site d'analyse financière Margin Call
http://www.margincall.fr/

Les algorithmes vont-ils vous tuer ? - Episode III

Informatique Quantique

L'informatique quantique, issue d'une technologie complètement physique basée sur des flux controlés de photons, constitue sans doute l'une des plus importantes révolutions à venir dans le monde du calcul, et donc dans tous les secteurs par la suite .
Lorsqu'elle sera pleinement opérationnelle, il faudra être rapidement réactif notamment dans le domaine de la cryptographie.
Une machine quantique viendra à bout immédiatement de n'importe quel système RSA.
Ce système rendu public en 1973 nécessite que la taille des clés utilisées soit renforcée très régulièrement ; sa sécurité est basée sur la difficulté de la factorisation d'un grand nombre entier en facteurs premiers (par exemple 15 = 3x5, je sais faire ! Par contre en remplaçant 15 par un entier de 200 chiffres, je ne sais plus faire avec les algorithmes actuels issus de l'arithmétique!)
Tout va bien jusqu'à présent, mais il a été démontré que l'algorithme RSA sera cassé par une « attaque quantique » : on parle ici de toutes les transactions financières réalisées sur le réseau !
Les algorithmes de cryptographie quantiques existent, ils remplaceront nos algorithmes de cryptographie conventionelle .
Les algorithmes quantiques de traitement de l'information révolutionneront le domaine du calcul; certains existent déjà !
Cette technologie, qui commence à donner des résultats, va relèguer nos machines actuelles au rang d'objets préhistoriques.

Puissances de calcul

Donnons pour terminer un certain nombre des chiffres sur la puissance de calcul en général.
Issus du livre incontournable « Complexités » de Jean Paul Delahaye – CNRS Université de Lille,
ils sont suffisament parlants pour ne pas être commentés :

Puissance	En instructions par seconde
console de jeu	10^10 inst/s
Deep Blue, l'ordinateur qui a battu Kasparov	5x 10^12 inst/s
réseau de calcul SETI	10^15
Le plus puissant ordinateur (2007)	10^15 inst/s
Puissance cumulée des consoles de jeu	10^18 inst/s
Puissance cumulée (2007) des ordinateurs	10^19 inst/s
on continue à monter en puissance , plus proche de nous :
Puissance de calcul du système génétique d'un être humain, en supposant que chaque information génétique de chaque cellule est activée toutes les 1000 secondes	5x10^19 inst/s
Puissance de calcul artificiel totale aujourd'hui	10^20 inst/s
Puissance de tous les cervaux humains	de 10^23 à 10^29 inst/s (avec beaucoup d'inégalités si l'on regarde les choses au cas par cas...)
Puissance cumulée des systèmes génétiques de tous les êtres humains	10^30 inst/s
Puissance cumulée des systèmes génétiques de tous les êtres vivants sur terre	10^34 inst/s
Puissance de l'ordinateur de 1 kilogramme le plus puissant possible d'après un résultat de mécanique quantique de Margolus et Levitin	10^45 inst/s
Pour terminer :
l'ensemble de tous les calculs informatiques menés depuis le début de l'informatique est évalué à	10^28 instructions.
En considérant les manipulations d'informations opérées à patir du génome comme des calculs, il y aurait eu sur terre environ	10^50 instructions de calculs faites depuis l'origine de la vie (avec une incertitude de plusieurs ordres sur ce chiffre)
Enfin, en considérant que chaque mouvement dans l'univers est équivalent à un calcul, il a été évalué que l'univers aurait produit un calcul d'environ	10^115 instructions.

Epilogue

Revenons à l'activité du trader , chacun de ses choix, chacune de ses actions peut être vue comme résultant d'un calcul réalisé par ses neurones fortement connectés (je l'espère) dans son cerveau.
Un calcul identique peut ou pourra être mené de façon similaire par une machine (peu importe l'architecture qui se cachera derrière cette machine) , le calcul sera effectué et donnera un résultat ,
l'algorithme utilisé le fera plus rapidement , on pourra même ajouter la notion de stress afin d'optimiser les choix du code!

L'activité du trader est calculable , au sens de Turing, en conséquence, il est fort probable que le test de Turing soit rapidement passé avec succès par une machine dans le domaine restreint du traiding !

 

 

 

 

 

 

 

Super calculateur Mare nostrum – Espagne

Second article d'une série de trois, publiés sur le site d'analyse financière Margin Call
http://www.margincall.fr/

Les algorithmes vont-ils vous tuer ? - Episode II

Poursuivant notre balade sur les sentiers de l'intelligence artificielle, nous abordons à présent les domaines du traitement automatisé de l'information, des Big Data, des automates cellulaires, de la simulation multi-agents, de l'émergence et leurs applications possibles aux programmes de trading.

Les logiciels embarqués intervenant en aérospatiale (celui de Curiosity pour l'exploration martienne) ,ceux destinés à l'armement (drones),ou encore ceux du secteur automobile tendent à devenir de plus en plus autonomes et robustes.

En fonction d'informations reçues de leur environement, via de multiples capteurs, ces programmes déterminent la meilleure décision à retenir et agissent en conséquence , parfois sans aucune intervention humaine.

Traitement automatisé de l'information et Big Data

Le traitement algorithmique (évaluation, hiérarchisation par pondération puis classement) de l'information issue de très grosses bases de données se développe très rapidement et impacte un nombre croissant de secteurs stratégiques.
Les Big Data, bases de données géantes à disposition sur le réseau mondial, sont parcourues par des algorithmes moteur de recherche à l'image de Google.
Dans ces parcours, les algorithmes brassent des millions d'informations et remarquent des liaisons de fréquences ou de propriétés entre telles et telles sous tables, parfois sans aucun rapport entre elles à priori !
Ces similitudes d'information (cf billet – épisode I) sont ensuite soumises à un opérateur humain qui décide si une corrélation exhibée par la machine est sans fondement ou bien si au contraire, quelque chose de profond et de nouveau se cache derrière cette mise en relation.
Une nouvelle forme de recherche émerge de ces algorithmes voraces issus de la théorie des graphes.
Cette pratique sous-entend des puissances de calcul et de stockage très importantes !
On peut alors imaginer une machine ultra puissante, assurant en temps réel une recherche exhaustive d'information stratégique à l'usage des trader sur l'ensemble des réseaux, puis analysant efficacement cette masse d'informations (un peu comme un logiciel de jeu d'échec) et restituant après pondération de chaque micro-information traitée, une synthèse optimisée, elle-même pouvant ensuite alimenter un autre programme agissant sur le marché.

Coopération, Intelligence en essaim, Emergence

Les biologistes étudient depuis longtemps le comportement de colonies de fourmis ou de termites.
Ils ont en particulier remarqué qu'il existe souvent une dynamique globale dans ces colonies et que cette dynamique résulte de l'action réduite de chaque insecte.
La fourmi (qui n'est pas prêteuse) agit en fonction des signaux reçus de son environnement (présence ou non de phéromones), elle modifie cet environnement, puis réagit à nouveau sur cet
environnement modifié; des structures naissent alors de l'action collective.
Le monde du calcul s'est naturellement inspiré de ces constatations.
Les systèmes dynamiques, automates cellulaires, simulation multi-agents, ont permis de mettre en évidence ,par le calcul , la réalité et l'efficacité d'un intelligence émergente issue des interactions d'une nuée d'agents.
La programmation orientée multi-agent permet de simuler un grand nombre de systèmes dynamiques complexes et de mettre en place une résolution collective d'un problème.
Cela va du comportement d'une fourmilière ou termitière , à celui d'une avalanche , de l'érosion de la côte sur une plage ,du mouvement des dunes de sable ou de la propagation d'un incendie ou d'une épidémie sur un territoire donné.
Via le multi-agent, on simule efficacement le mécanisme d'une vente aux enchères ou d'une activité de trading.
Très récemment, les émeutes britaniques de l'été 2011 ont été étudiées via la SMA par Antonio A Casilli – Conférence 2012 TED – X paris Université

http://www.knowtex.com/nav/la-simulation-sociale-pour-combattre-la-censure-texte-de-la-conference-tedxpu-d-antonio-casilli_33941

L'intérêt premier est de prévoir et d'expliquer des comportements du système qui apparaissent au cours du temps et qui parfois échappent complètement aux modèles équationnels classiques :

Les équations échouent là où le multi-agent réussit !!
Plus fort encore : la simulation multi-agents (SMA) donne souvent naissance à l'émergence ,
c'est un phénomène très étudié mais qui reste encore mystérieux :
L'émergence peut se résumer de façon terriblement réductrice par la phrase :
« Le tout est plus que la somme de ses parties » (ne cherchez pas de contrepèterie ici, il n'y en pas !)
Le phénomène émergent apparaît au cours du déroulement de l'algorithme , sans qu'il ait été programmé dans le code initial ; c'est donc une structure nouvelle , un agencement inattendu à priori qui émerge de la dynamique générale du système et de la somme des interactions de chaque agent du système... c'est beau non ??
Si ce n'est pas beau, alors c'est magique !
Reste alors à comprendre et à domestiquer cette émergence, (ce qui n'est pas encore le cas aujourd'hui) afin de l'exploiter au sein des futurs programmes.
Ceux-ci pourront alors devenir auto-évolutifs, ils se corrigeront , se complèteront en fonction de leur usage, ils s'affineront, deviendront meilleurs sans intervention humaine....

 

 

 

 

Ces progrès algorithmiques ne pourront s'exprimer que si les puissances de calcul des machines poursuivent leur évolution.

Les techniques de gravures de microprocesseur issues des nanotechnologies vont permettre cette évolution technologique et ouvrir de nouvelles perspectives en IA.
Au delà, il faut évoquer l'horizon constitué par l'informatique quantique.

C'est ce que l'on fera dans l'épilogue.

Premier article sur trois publiés sur le site d'analyse financière Margin Call le 17 septembre 2012
http://www.margincall.fr/

Les algorithmes vont-ils vous tuer ? - Episode I

Ce n'est pas le titre d'une mauvaise série B de science fiction des années 60, mais bien une question essentielle que la communauté du trading doit considérer :

Un algorithme peut-il remplacer efficacement un trader ?

HFT

Cette interrogation s'illustre aujourd'hui dans la pratique du HFT ( High Freqency Trading ou algo-trading) et dans les réactions nombreuses, parfois irrationnelles, souvent justifiées, qu'elle suscite :
Faut-il encadrer HFT en incluant des bornes artificielles de vitesses au sein des algorithmes ?
Faut-il intégrer une dose de « viscosité » programmée qui lissera les épiphénomènes inévitables dans ce type de dynamique ?
HFT déforme-t-il le marché et l'économie ?
Toujours est-il que sa progression est constante (9% des volumes quotidiens sur les marchés actions européens en 2007 contre 40% en 2011) cette progression est encore plus forte sur les marchés non européens!
On retrouve invariablement ce type de questions, dès lors qu'une nouvelle technologie investit un domaine: les accidents , dérapages, effets collatéraux accompagnent toujours son déploiement.
(voir l'affaire Sergei Alaynikov VS Goldman Sachs).
HFT ne fait que préfigurer ce que seront les outils numériques de demain.
C'est en quelque sorte l'éclaireur devant la longue marche des machines engagée il y a un demi-siècle maintenant.
Il est inutile de craindre ou de lutter contre cette évolution, il faut l'accompagner en anticipant les changements à venir : « ressentir » au sens physique du terme les nouveaux algorithmes.

Dressons un panorama non exhaustif des orientations et évolutions algorithmiques qui risquent de modifier en profondeur l'informatique appliquée à la finance dans un proche avenir.
Je remercie d'avance le lecteur de ce billet d'accepter de m'accompagner pour une balade sur les chemins escarpés de la logique et de l'IA - intelligence artificielle.

Intelligence – Test de Turing

On peut avantageusement reformuler la question du titre en se demandant si un programme ou une machine est en mesure de réussir le test de Turing face à un trader humain.
En 1950, le mathématicien britanique Alan Turing a proposé le jeu de l'imitation appelé depuis « test de Turing »
La règle de ce jeu est la suivante :
Un juge dialogue par écrit avec un interlocuteur , à l'issu de ce dialogue, il doit reconnaître si celui-ci est une machine ou un être humain.
Le juge ne voit pas son interlocuteur qui doit quant à lui toujours répondre aux questions du juge.
La machine (lorsque c'est elle !) essaie de se faire passer pour un être humain et l'être humain tente de se faire reconnaitre comme humain.
Lorsque le juge se trompe dans 50% des cas ou plus, alors on considère que la machine présente une forme d' intelligence, qu'elle pense , à sa façon, et que le test de Turing est réussi.
En 1990, Hugh Loebner a créé un concours visant à passer le test de Turing; une récompense de 100.000 USD est prévue pour le premier code passant avec succès ce test.
Beaucoup de chercheurs en informatique théorique pensent que l'on est proche en terme d'années d'un succès à ce test.
En restreignant l'environnement de ce test et en le spécialisant à un domaine (le trading par exemple), on simplifie grandement l'épreuve et l'on s'approche encore plus d'une réussite.
Concrètement, il faut envisager un programme capable de fournir des réponses de niveau équivalent à celles d'un opérateur humain; le code doit donc comporter un niveau d'IA suffisant pour passer inaperçu dans l'ensemble des réactions humaines.
A titre d'illustration, on pourra aller discuter avec Alice (à l'adresse suivante) :
http://www.pandorabots.com/pandora/talk?botid=f5d922d97e345aa1
et ici : http://alicebot.blogspot.fr/
Alice est une adolescente dont le code évolue depuis plus de 16 ans.
Son père Richard S Wallace a remporté trois fois le prix Loebner, il a utilisé au niveau algorithmique certaines méthodes de « langue de bois » que l'on retrouve en politique.

Explorons à présent quelques ingrédients de l'IA

Complexité Algorithmique

Il existe aux limites des mathématiques et de l'informatique une théorie dite théorie de la complexité , initiée par le mathématicien russe Andrei Kolmogorov (1903-1987).
Celle-ci embrasse quasiment toutes les disciplines modernes , elle permet notamment de formaliser efficacement l'aléatoire et l'organisé. L'idée est la suivante :
Toute information finie ( un mot, un texte , une image, une vidéo, l'ensemble de tous les livres écrits sur cette planète, ou encore le code ADN de nos cellules...) peut se représenter, via un certain codage,sous forme d'une chaîne binaire , c'est-à-dire une suite finie de 0 et de 1.
La complexité de Kolmogorov notée K(C) de cette chaine C est définie comme la longueur du plus court programme , fonctionnant sur une machine de Turing donnée (un ordinateur ou un langage classique par exemple), et produisant cette chaine C en sortie.
Si l'on considère ensuite le temps d'éxécution de ce plus court programme, on définit alors la profondeur logique de Bennet de cette chaîne C.
Ces deux mesures sont simples à définir (cela nous a pris quelques lignes !).
Les résultats qu'elles induisent sont quant à eux d'une grande profondeur.
Elles permettent en particulier de formaliser le degré d'aléatoire ou d'organisation d'une chaîne :
une chaîne issue par exemple d'un pile ou face répété 1000 fois (O pour Pile et 1 pour face) aura une complexité maximale (en d'autres termes, le hasard ne se résume pas !)
Une chaîne régulière du genre C = 010101.....0101 aura une complexité faible : je peux la coder en écrivant le programme très court : «  répéter 500 fois le motif 01 , puis afficher le résultat»
Pour la chaîne issue de mon pile ou face , par exemple C = 0001011001...., je suis obligé de décrire chaque bit dans mon programme produisant C, donc sa complexité est grande, proche de sa longueur , on dit que la chaîne C est incompressible.

Les deux oeuvres suivantes présentent des complexités différentes :

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Mondrian – complexité C1

    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Tehos – complexité C2

 

Je peux donner une description courte et complète du tableau de Mondrian, alors que celle de l'oeuvre de Tehos sera beaucoup plus longue , d'où C1 < C2.

Un même objet peut voir sa complexité augmenter rapidement : au repos, une flute à champagne possède une complexité propre, celle ci va augmenter brusquement lorsque j'aurai laissé tomber cette flute sur le sol!
Un des ingrédients de l'intelligence humaine réside dans notre capacité à reconnaître des similarités entre objets pourtant très différents.

La complexité nous permet de transmettre cette faculté à une machine :
Si l'on cherche à mesurer l'information partagée entre deux objets A et B , on peut considérer le plus court programme qui permet de transformer l'objet A en l'objet B, puis le plus court programme effectuant la transformation inverse (de B vers A), on additionne ces deux longueurs de code et l'on obtient une mesure très efficace d'information partagée qui a donné récemment de beaux succès en classement intelligent automatisé de grosses bases de données génétiques.

Enfin, la complexité engendre des démonstrations courtes de résultats extrèmement profonds :

Le célèbre théorème de Gödel (en simplifiant, il dit qu'il existe dans tout système logique des vérités -théorèmes qui sont indémontrables dans ce système ) admet lui-même une démonstration très courte en utilisant la complexité de Kolmogorov.

Cette approche « complexité » est en train de fournir une gamme d'outils IA tres prometteuse.

L'informatique ,quant à elle, tente de canaliser cette complexité; elle le fait à une vitesse qui double tous les 18 mois (loi de Gordon Moore) ; on parle ici de l'informatique conventionnelle et pas encore de l'informatique quantique qui nous réserve de belles surprises !

Si le lecteur le souhaite, il poursuivra avec moi cette balade du coté de la simulation multi-agents, de l'Emergence ,des big datas et des capacités de calcul , ceci lors d' un prochain article.

Peut-être qu'après la lecture de ce premier billet, vous ne regarderez plus votre machine avec le même oeil.
Au fait, qui a rédigé ce billet ? Un humain ? Une guenon ? Une machine ?