La complexité de Birkhoff


La plus grande découverte d'Alan Turing est sans doute qu'il y a une notion universelle unique de fonction calculable. Cette notion se définit avec les machines élémentaires qu'il introduisit dans son article de 1936 et qu'Alonzo Church a nommées « machines de Turing ». L'idée peut aussi se formuler de nombreuses façons différentes, par le lambda-calcul, par des systèmes d'équations, par les langages de programmation, etc. On prouve que les notions obtenues sont équivalentes ce qui conforte l'idée que la notion proposée par Turing est centrale, correcte et vraiment universelle.

De cette notion de « fonction calculable », on déduit des mesures de complexité pour les algorithmes (classes de complexité P, NP, EXP, etc.) ou pour les objets finis numériques (complexité de Kolmogorov, profondeur logique de Bennett) chacune de ces notions étant elle aussi universelle à sa façon, c'est-à-dire ne dépendant pas d'un choix arbitraire ou convenu (du moins pour l'essentiel).

Ce qu'on oublie aujourd'hui c'est qu'avant cette révolution « universalisante », on pensait sans nécessairement l'exprimer clairement que les notions de « calculable » et de « complexité » dépendaient de conventions à choisir dans chaque cas particulier. Les propriétés « être linéaire », ou « être un polynôme », pour une fonction étaient par exemple des façons possibles de considérer la propriété « être calculable ». Une fonction pouvait finalement être plus ou moins calculable, et on était libre, selon les besoins, d'inclure des mécanismes plus ou moins larges et généraux pour fixer la notion de « calculable » dont on avait besoin, cela sans limite claire et avec l'idée implicite qu'il n'y en avait pas.

La révolution de Turing nous montre qu'il n'en est pas ainsi : il existe un maximum pour la propriété « être calculable », il est rapidement atteint, et c'est la Turing-calculabilité. Il n'a rien de conventionnel, mais résulte de la nature (mathématique) des choses. Pour la propriété « être complexe », il en va de même : rien n'est laissé au choix du théoricien, qu'il s'agisse des fonctions ou des objets numériques finis (et à la condition de ne pas mélanger « complexité comme incompressibilité », et « complexité comme richesse en structures » ; sur ces notions voir : a ou b  ).

Un livre porte la trace évidente d'une conception pré-Turing de la complexité et donc d'une conception pré-Turing de la calculabilité. Tout son contenu s'organise avec l'idée que mesurer la complexité des objets est une affaire relative, qu'il faut reprendre avec chaque classe d'objets envisagée en tentant au mieux d'introduire une bonne définition adaptée au contexte. Il s'agit du livre publié en 1933 par George Birkhoff, intitulé "Aesthetic measure". Birkhoff était considéré comme l'un des plus brillants mathématiciens de son époque, pourtant, son livre est en grande partie resté ignoré, en particulier dans les milieux de l'art et de la philosophie esthétique. Le livre est parfois qualifié de « curieux » ; c'est ce que fait wikipedia (ici).  Sans doute son projet était-il jugé naïf ou même scientiste… et l'est encore.

Birkhoff essayait dans cet ouvrage de définir une mesure objective et scientifique de la qualité esthétique des œuvres artistiques, particulièrement graphiques et musicales. Ou plutôt, il proposait une méthode générale et une formule pouvant s'appliquer de différentes manières selon les catégories d'œuvres envisagées, pour concevoir des mesures spécialisées de la qualité esthétique. Son but était (au moins) de classer des œuvres proches (par exemples des motifs décoratifs, ou des vases) d'une façon conforme à ce que donnerait une moyenne d'évaluations opérées par des juges indépendants humains.

Le projet peut sembler déraisonnable, mais formulé avec un peu de précaution et de modestie dans les ambitions comme le fait Birkhoff, il ne l'est sans doute pas. Les nombreux travaux qui ont prolongé, complété ou réinterprété ses idées prouvent qu'avec ce travail téméraire il a réellement créé un domaine de recherche, difficile et risqué certes, mais où se développent de nombreuses pistes rigoureuses et stimulantes de réflexion sur l'esthétique. Il établit que dans certains cas au moins, il est possible de mesurer objectivement la qualité esthétique des productions artistiques.... et cela, même si cela fait bondir ceux qui pensent que justement la science sera toujours impuissante à comprendre l'art car ce sont des domaines profondément et définitivement étrangers l'un à l'autre.

La formule générale que Birkhoff propose pour mesurer la qualité esthétique M d'un objet, d'un dessin ou d'une œuvre est :

M = O/C

O est une mesure d'ordre et C une mesure de complexité.

Birkhoff précise sagement : « If we admit the validity of such a formula, the following mathematical formulation of the fundamental aesthetic problem may be made: Within each class of aesthetic objects to define the order O  and the complexity C so that their ratio O/C yields the aesthetic measure of any object of this class. »

Tout le travail pour obtenir une mesure M satisfaisante se ramène alors à trouver des mesures elles-mêmes satisfaisantes pour O et C. Passons sur O (pour Birkhoff une forme de satisfaction provoquée par l'identification de relations internes dans l'objet, par exemple des symétries). Pour la complexité, C, Birkhoff, dans un langage qu'il veut rendre rigoureux et scientifiques, écrit :

« Suppose that  A, B, C, ... are the various automatic adjustments required with respective indices of tension a, b, c, ... , and that these adjustments A, B, C, ... take place r, s, t, ... times respectively.  Now it is the feeling of effort or tension which is the psychological counterpart of what has been referred to as the complexity C of the aesthetic object. In this manner we are led to regard the sum of the various indices as the measure of complexity, and thus to write : C = ra + sb + tc + ...  »

Dans l'idée de Birkhoff, la complexité est liée à la difficulté que nous avons à percevoir un objet présenté à nos sens quand ce qui est perçu est traité par notre cerveau, automatiquement sans que nous ayons à opérer d'analyses conscientes. Pour Birkhoff donc, la complexité est non pas dans l'objet mais dans le système qui le perçoit et qui doit faire un effort plus ou moins grand pour recevoir et comprendre l'objet en faisant fonctionner automatiquement ce qui, dans le cerveau, s'y trouve déjà. Pour un objet donné, d'un individu à l'autre, d'un animal à l'autre, la complexité changera. Elle est en quelque sorte subjective et psychologique.

La mesure de complexité qu'il défend est dépendante des capacités  des sens, de la biologie de l'être qui perçoit : elle est particulière, elle n'est pas universelle. Indirectement, l'idée d'un traitement informationnel, donc d'un calcul, est présente dans cette conception. Mails le travail que Birkhoff mène dans son ouvrage est fait en l'absence de la « grande nouvelle » de Turing qu’il existe une notion universelle de calcul, à laquelle on peut ramener tout calcul particulier. Il propose donc des modes de calcul particulier pour chaque classe d'objets. Ses propositions multiples sont parfois assez peu convaincantes : on se demande s’il n’oublie pas quelque chose, s’il pèse bien les différents éléments les uns relativement aux autres, etc. Trop d'arbitraires, en suggère d'autres !

Le choix de Birkhoff d'une définition subjective, quasi biologique pour présenter des mesures de complexité est un choix pré-Turing. Même si cela peut paraître un peu facile, il me semble possible d'affirmer que si Birkhoff avait connu les développements de la théorie du calcul après 1936, il aurait tenté de dé-subjectiviser sa notion, il aurait tenté d'en produire une version moins contextuelle. Le livre est donc composé d'une série d'études soigneuses et particulières, concernant des classes limitées d'objets dont à chaque fois il définit la complexité par un procédé ad hoc, et dont il est facile souvent de discuter les détails.

Depuis, les idées de Birkhoff ont été reprises, on a tenté de les replacer dans le moule d'universalité introduit par Turing. Une discipline en est née l'esthétique computationnelle. Sa richesse, ses hésitations, les difficultés qu'elle rencontre à produire des résultats décisifs n'étonnent personne. Cependant, la machine est en marche, et nous devons reconnaître qu'un lien d'un type nouveau existe maintenant entre art et science différent d'une science au service de l'art. La science tente de comprendre la nature et le fonctionnement du sentiment esthétique, cela grâce aux concepts sortis de la théorie mathématique du calcul dont Turing a posé de manière magistrale les bases en 1936 peu de temps après la valeureuse tentative de Birkhoff de mesurer le beau, tentative qui prend pleinement son sens avec l’universalisation des concepts de complexité.

Quelques références.

• Anikó Ekárt, Divya Sharma, Stayko Chalakov. "Modelling human preference in evolutionary art." Applications of Evolutionary Computation. Springer Berlin Heidelberg, 2011. 303-312.

• Kate Reed. Aesthetic measures for evolutionary vase design. in P. Machado, J. McDermott, A. Carballal (Eds.): EvoMUSART 2013, LNCS 7834, pp. 59–71, 2Springer Berlin Heidelberg, 2013.

• Eelco den Heijer,  A. E. Eiben. "Using aesthetic measures to evolve art." Evolutionary Computation (CEC), 2010 IEEE Congress on. IEEE, 2010.

• Jon McCormack, Mark d’Inverno. Computers and Creativity. Springer Science & Business Media, 2012.

• Jaume Rigau, Miquel Feixas, Mateu Sbert. "Informational aesthetics measures." IEEE Computer Graphics and Applications 2: 24-34, 2008.

• Jaume Rigau, Miquel Feixas, Mateu Sbert. "Conceptualizing Birkhoff's Aesthetic Measure Using Shannon Entropy and Kolmogorov Complexity." Computational Aesthetics. 2007, ici.

• Nathalie Sinclair, David Pimm. Mathematics and the aesthetic: New approaches to an ancient affinity. New York: Springer, 2006.

• George Birkhoff, Aesthetic measure. Cambridge, Mass., 1933.

 


4 commentaires pour “La complexité de Birkhoff”

  1. Christophe H. Répondre | Permalink

    Hors sujet, mais il semble qu'un script russe parasite la page d'accueil du site (que je n'arrive plus à afficher d'ailleurs).
    J'ai trouvé ça dans les sources de la page : src=http://sbads.ru/892R

  2. Peva B. Répondre | Permalink

    Bonjour,

    Très intéressant. On comprend bien que l'universalité de la machine de Turing faisait défaut à Birkhoff.

    Il me semble cependant qu'on peut "relativiser" un petit peu les choses. En effet, si on s'autorise *tout* les procédés de calculs imaginables (et si on adhère à la thèse de Church-Turing) alors on tombe sur le calcul universel à la Turing. Mais on pourrait se restreindre aux procédés de calculs d'une certaine classe, p.ex., P, NP, etc.

    Intuitivement, en suivant l'approche de Birkhoff, on peut imaginer que l'appréciation esthétique d'un certain objet serait, pour l'observateur, équivalent à la résolution d'une instance d'un problème d'une certaine classe (P, NP, etc.), et que cette appréciation différerait selon la classe considérée.

    Ce n'est cependant pas totalement 'relativiste' dans la mesure où ces classes de complexité sont elles-mêmes universelles.

    Sont-ce là des choses qui ont été étudiées en esthétique computationnelle ?

    Cordialement,
    pb

    • Jean-Paul Delahaye Répondre | Permalink

      L'idée de Birkhoff a été développée par de nombreux chercheurs (pas toujours d'accord entre eux sur le sens à donner à "complexité" et "ordre"). Plutôt que les classes de complexité P, NP, EXP, etc. (qui ne fonctionnent que pour des problèmes infinis), c'est plutôt à la complexité de Kolmogorov qu'ils se sont intéressés. Je travaille à un article sur le sujet à paraître dans Pour la science (septembre 2015), mais sans attendre vous pouvez consulter :

      Philip Galanter, "Computational aesthetic evaluation: Past and future." Computers and Creativity, Springer Berlin Heidelberg, 2012. 255-293.

      ou

      Jaume Rigau, Miquel Feixas, and Mateu Sbert, "Informational aesthetics measures." IEEE Computer Graphics and Applications 2 (2008): 24-34.

      http://www.researchgate.net/profile/Mateu_Sbert/publication/5501365_Informational_aesthetics_measures/links/0912f510865724733f000000.pdf

Publier un commentaire