Authorship attribution for music: developments and challenges

It has been a while now that the two authors of this particular academic blog have been interested in computational methods applied to authorship attribution. Until now, our research have been focused on texts, mostly from the Middle Ages and the XVIIth century. Given our shared scientific interest for digital musicology, one question arised:  can our methods, designed for textual sources, apply to scores ? Finding out which compositor wrote a specific piece of music seems even more tricky than finding the author of text.

Looking for fingerprints

To understand who could be a text’s author, we know which clues to look for. Most of the time, the author of a text will reveal his identity through the unconscious repetition of certain grammatical structures, the use of certain function words, or, for versified texts, the choice of a specific vocabulary for his rhymes.

What would be the equivalent of all these phenomena in a musical work ? Is it possible to define a short list of specific phenomena that we should spot to identify a composer’s signature, no matter the style or the era ?

Here are a few insights gained from this year’s edition of the Digital Humanities at Oxford Summer School.

Are improvisations signatures ?

Using material from Stanford University’s Josquin Research Project (ca. 1420- ca 1520) (Stanford University) and from the CESR (Tours) Les livres de Chansons Nouvelles de Nicolas Du Chemin (1549–1568) project, Catherine Motuz gives us a first possible answer.

Josquin Des Prez, Facsimile of Petrus Opmeer’s woodcut, Opvs chronographicvm orbis vniversi a mvndi exordio vsqve ad annvm MDCXI (Antwerp, 1611).

During the the fifteenth and sixteenth centuries, musicians were used to improvise codified and sometimes very complex polyphony. The structures of these improvisations follow very strict rules,  recorded in various treatises by several authors, from Guillelmus Monachus around 1480 to Tomàs de Santa Maria in the middle of the 1560s. Yet, these rules leave a composer with a few choices, and each composer seems to favour specific formulas, that could give his identity away.

To work on the structure of these polyphony, one have to study the succession of vertical intervals – which Catherine Motuz does through the Electronic Locator of Vertical Interval Successions (ELVIS). Working on polyphonic n-grams (yes, musicologists use n-grams for authorship attribution too!), she detects the use of different polyphonic models –  canons, parallel sixths, parallel tenths… With two-grams, the separation between Josquin and Du Chemin is not obvious ; but with three-grams, the contrast is striking!

Tell me how you end, I will tell you who you are

Another work by Frauke Jurgensen points in the same direction. Studying chansons written by composers from the “Burgundian school”, mostly by Gilles Binchois (ca 1400- 1460) and Guillaume du Fay (1397-1474), she tries to identify unique features of those composers. Binchois writed tunes more jagged than du Fay. He also differentiated more among voices than Du Fay, in terms of voice leading style. One place though looks like a reasonable candidate to look for specificities: cadences.

Gilles Binchois, Watercolour from Le Champion des dames by Martin Le Franc

Even if identifying a cadence, especially when they are somewhat elaborate, can be tricky for the computer, Jurgensen manages to clearly isolate 8000 cadences. Their study shows that, even if there is no such thing as a cadence specific to Binchois or du Fay, big differences can be exhibited between the way these two authors write their cadences. They mostly use the same patterns, but not with the same frequency. Computing the proportion of certain cadences  in an unattributed piece could then help find its plausible author.

What is next ?

Following these two studies, it seems that authorship attribution in musicology will not easily be able to reproduce the methodology used in text studies. For now, only an expert view on the compositions from a certain place and period might allow to identify the markers of a certain composer. To understand who is the author of an unattributed piece of music, we would have to spot a certain feature in this piece, different according to the genre, place and time, and compare it to the way this feature is normally executed by one or the other composer.

Will we find techniques that we could apply more generally ? The properly digitized corpora are still rare, and the studies in this field look quite rare (I would be grateful to any reader pointing me to papers addressing this problem). It is thus very difficult to answer this question – but I am eager to find out !

Bibliography

ANTILA Christopher, CUMMING Julie, “The VIS Framework: Analyzing Counterpoint in Large Datasets”, in  ISMIR (pp. 71-76), 2014

JURGENSEN Frauke, “Symbolic Music Analysis of Renaissance Counterpoint: current challenges”, Digital Humanities at the Oxford Summer School, Oxford University, July 5th 2017

MOTUZ Catherine, “Authorial fingerprinting for Renaissance Polyphony: Finding Contrapuntal Formulas in Two Corpora of French Chansons”, Digital Humanities at the Oxford Summer School, Oxford University, July 4th, 2017

Florian CAFIERO

Ancien élève de l'Ecole Normale Supérieure Paris-Saclay et diplômé de l'Ecole nationale des chartes, Florian Cafiero est ingénieur de recherche en mathématiques appliquées aux sciences humaines et sociales au CNRS. Il enseigne les méthodes quantitatives appliquées aux sciences humaines à l'Ecole nationale des chartes.

More Posts - Website

Follow Me:
TwitterLinkedIn

Roadmap for an R Stemmatology Package

We have written a post, quite some time ago, about an R Stemmatology Package1, and started its development (it is available on Github2). Now, we come back to this long overdue subject, to draft a roadmap for future developments.

NB: this is a working post, that will evolve in the course of development of this package.

Main tasks

1. Documentation

  • Document all the existing functions, datasets (necessary for 2);
  • Document new functions when they are added.

2. R packaging

  • Finish documentation;
  • Other packaging tasks?

3. Implementation of new exploratory methods / methods to detect contamination

  • Finish implementation of methods presented in Camps 2013a et 2013b3;
  • Implement cardiograms from Wattel et Van Mulken 1996, Den Hollander 2004 4;
  • find and implement new methods.

4. Implementation of new tree building algorithms

  • Implementation of tree building algorithms, different from the PCC method5, proposed by other researchers;

5. Implementation of algorithms for theoretical stemmatology

  • Implement a function for bifidity calculations.

  1. J.B. Camps, «An R Stemmatology Package ?», Sacré Gr@@l, 14 mai 2013, en ligne: https://graal.hypotheses.org/665 []
  2. Jean-Baptiste Camps, Florian Cafiero, Stemmatology : an R Stemmatology package, Paris, 2013-…, en ligne: https://github.com/Jean-Baptiste-Camps/stemmatology []
  3. JB Camps, «Detecting Contaminations in Textual Traditions. Computer Assisted and Traditional Methods», unpublished paper presented to the International Medieval Congress, Leeds, 2013; Id., «Sélection des lieux variants et construction d’un stemma: nouvelles expérimentations», communication non publiée présentée au XXVII Congrès International de Linguistique et de Philologie Romanes, Nancy, 2013. []
  4. See E. Wattel & M.J.P. Van Mulken, « Schock Waves in Text Traditions, Cardiograms of the Medieval Litterature », in Studies in Stemmatology, P. Van Reenen, M.J.P. Van Mulken, Amsterdam, 1996, p.105-121; A.A. Den Hollander, « How shock waves revealed successive contamination. A cardiogram of early sixteenth-century Dutch Bibles. » in Studies in Stemmatology 2, dir. P. Van Reenen, A.A. Den Hollander & M.J.P. Van Mulken, Amsterdam, 2004, p. 99-112. You can also have a look at our post, Florian Cafiero, «Le scandale du stemma contaminé. Note sur l’usage des cardiogrammes en philologie», Sacré Gr@@l, 18 décembre 2011, en ligne: https://graal.hypotheses.org/517. []
  5. Eric Poole, « The Computer in Determining Stemmatic Relationships », Computers and the Humanities 8-4 (1974), p. 207‑16; Id., « L’analyse stemmatique des textes documentaires », in La pratique des ordinateurs dans la critique des textes, Paris, 1979, p. 151‑161; Jean-Baptiste Camps et Florian Cafiero, « Genealogical variant locations and simplified stemma: a test case », in Analysis of Ancient and Medieval Texts and Manuscripts: Digital Approaches, dir. Tara Andrews & Caroline Macé, Turnhout, 2015, p. 69‑93 (Lectio, 1). []

Jean-Baptiste Camps

Diplômé de l'École nationale des chartes et docteur en études médiévales de l'Université Paris-Sorbonne (la Chanson d'Otinel…, dir. Dominique Boutet ), Jean-Baptiste Camps est responsable pédagogique du master «Humanités numériques» à l'École nationale des chartes (PSL). [CV et liste des publications, voir : http://paris-sorbonne.academia.edu/JeanBaptisteCamps]

More Posts - Website

Follow Me:
LinkedIn

Analyse de réseaux (3): s’il vous plaît… dessine-moi un réseau

” – Dessine-moi un mouton.” Alors j’ai dessiné. Il regarda attentivement, puis: “- Non! Celui-là est déjà très malade. Fais-en un autre.” Je dessinai : […] “- Tu vois bien… ce n’est pas un mouton, c’est un bélier. Il a des cornes…” Je refis donc encore mon dessin. Mais il fut refusé, comme les précédents […] Alors, faute de patience, comme j’avais hâte de commencer le démontage de mon moteur, je griffonnai ce dessin-ci. […] “- C’est tout à fait comme ça que je le voulais !”

                      Le Petit Prince, Antoine de Saint-Exupéry, Chapitre II

Après avoir exploré très succinctement quelques possibilités et limites de l’analyse des réseaux, nous commençons une série d’articles consacrée au travail sur sa propre base de données.

En supposant que la base de données soit déjà créée et bien ordonnée, la première étape du travail est la visualisation de réseaux. C’est une étape cruciale pour comprendre ses données, mais aussi un enjeu important pour la diffusion de sa recherche, et qui comporte plus de risques qu’il n’y paraît. Des dessins radicalement différents peuvent correspondre au même graphe: lequel choisir ?

Il est parfois tentant d’adopter une démarche un brin naïve face à la représentation de notre réseau. Se contenter de choisir l’affichage par défaut minimise la peine, à défaut d’être toujours adéquat. Choisir le plus beau rendu visuel est également un travers séduisant.

Mais le risque le plus grave est ce que j’appellerai le “syndrome du Petit Prince”: demander à ce que le dessin soit fait et refait, jusqu’à ce qu’il apparaisse sous les traits dont nous rêvions, ou jusqu’à qu’il laisse assez de place à notre imaginaire pour qu’il puisse être interprété comme nous le voulions.

Il est toujours tentant, quand une multiplicité de représentations graphiques est possible, de sélectionner celle qui semble le plus manifestement aller dans le sens de nos hypothèses de départ, celle qui ressemble le plus à l’idée que nous nous étions faites de nos données.

Pour éviter tous ces écueils, nous livrons ici quelques éléments importants pour la construction d’une représentation graphique compréhensible, attrayante, mais avant tout fidèle à nos données.

PARENTHESE TECHNIQUE: LE LOGICIEL GEPHI

  • Pourquoi Gephi ?

Nous choisissons de présenter ici un logiciel développé depuis 2008 à l’université technologique de Compiègne (UTC), et dont l’usage s’impose de plus en plus dans la recherche française et internationale ces dernières années: Gephi. Relativement facile à prendre en main, ce logiciel offre néanmoins de vastes possibilités, en particulier en termes de visualisation.

Il traite tous les types de réseaux, dirigés, non dirigés ou mixtes, et est compatible avec Windows, Linux et Mac OS. C’est de surcroît un logiciel libre, publié sous licence CDDL + GNU GPL 3.

Attirons l’attention sur la version de Gephi utilisée: les changements intervenus entre Gephi 0.8.2 et Gephi 0.9.1 (celle dont nous parlerons) n’ont pas été sans conséquences, notamment en ce qui concerne les plugins. Certains tutoriaux et cours produits pour les versions antérieures ne sont donc plus toujours valables – les suivre à la lettre pouvant provoquer quelques bugs mineurs.

  • Travailler ses données sous Gephi

Gephi supporte des données à différents formats. Le GEXF (Graph Exchange XML Format) est le format développé depuis 2007 par l’équipe Gephi,

Une base de données au format gexf – exemple des la base “Les Misérables”

Notons que ce format permet de décrire explicitement dès l’encodage le caractère dirigé ou non des liens, d’assigner des labels, et d’attribuer des pondérations.

Mais le logiciel accepte bien d’autres formats: GraphML, GraphViz DOT, Netdraw VNA, PajekNET, GDF, GML, Tulip TLP, UCINET DL.

Plus simplement encore il est possible d’importer des fichiers .csv créés sous Excel, OpenOffice Calc ou autre tableur standard. Un simple tableau à deux colonnes – première colonne nœud d’origine, deuxième colonne nœud d’arrivée du lien – peut donc être exploité pour modéliser son réseau dirigé ou non.

  • Manipulations esthétiques et d’étiquetages

Via le menu du bas, minimisé par défaut, on peut appliquer la plupart des variations simples.

Dans l’onglet “global”, on permet de changer le zoom ou la couleur du fond. Dans les onglets suivants, on peut modifier les options d’affichage des nœuds et des liens (leur couleur, leur forme, leur épaisseur etc.). Gephi permet par ailleurs d’étiqueter chacun des nœuds – une option activable et configurable sur le même menu.

CHOISIR LA MISE EN FORME DE SON RÉSEAU: LA SPATIALISATION

Une étape cruciale est le choix de la spatialisation, (en anglais du “layout”) c’est à dire de la manière dont l’ordinateur va organiser les points dans l’espace.

Plusieurs options sont proposées dans GEPHI, et doivent être choisies en fonction de ses données et de l’usage que l’on veut faire de la représentation graphique. Nous présentons ici quelques options usuelles, installées par défaut ou accessibles via des plugins spécifiques.

Pour illustrer la grande variété des représentations graphiques, nous utiliserons systématiquement la même base de données (une base de données exemple de Gephi, retranscrivant les liens unissant entre eux les personnages des Misérables de Victor Hugo – son contenu est parfaitement indifférent pour notre propos du moment, nous ne commenterons bien sûr pas les résultats…).

Rapport d’import renvoyé par GEPHI à chaque importation d’une nouvelle base de données – ici pour la base de données exemple “misérables.gexf”

Une base de données de taille particulièrement modeste, qui permet d’appliquer aisément tous les traitements que nous voulions présenter.

Tout répartir au hasard ?

  • Spatialisation aléatoire

Une possibilité pour ne pas “projeter” son interprétation sur ses données, de ne pas imposer de vues au lecteur du graphique, pourrait être de demander à ce que les points soient répartis “au hasard” sur le graphique.

C’est ce que propose l’option “spatialisation aléatoire”. On n’y définit que la taille de l’espace alloué à la représentation graphique (plus l’espace défini est petit, plus le dessin apparaîtra “compact”).

Notre réseau exemple spatialisé avec l’algorithme Spatialisation aléatoire

Si séduisante puisse-t-elle paraître d’un certain point de vue, cette option aboutit cependant à des graphiques souvent impossibles à interpréter, en particulier lorsque la taille du réseau augmente.

Représenter un réseau ayant une “réalité” géographique:

Le cas le plus simple intervient quand le réseau que l’on veut représenter correspond à une réalité physique en général, géographique en particulier. Dans ce cas, les distances entre points sont une fonction de la distance physique séparant chaque point du réseau. Comme toujours en cartographie, le choix de la projection peut bien sûr influer su le regard.

  • Geo Layout

Demande l’installation du plugin GeoLayout.

On entre une base de données dans laquelle les nœuds sont définis par leurs coordonnées géographiques (longitude/latitude). Les points sont alors positionnés en fonction de ces points – les projections les plus usuelles, comme Mercator, étant bien sûr envisageables.

La faible complexité de cette opération permet l’usage de très grandes bases de données (jusqu’à 1.000.000 de nœuds).

  • Map of countries

Demande l’installation du plugin Map of Countries.

Reprenant une grande partie du fonctionnement du plugin précédent, Map of countries permet sans surprise de représenter son réseau sur une carte incluant les tracés des frontières nationales ou régionales.

Mettre en avant les complémentarités: les algorithmes basés sur les forces

La plupart des algorithmes proposés par GEPHI sont des algorithmes de dessin basés sur les forces (Force-directed ou Force-based algorithms).

L’intuition sous-jacente à ces algorithmes est simple: les points reliés entre eux sont attirés les uns envers les autres, tandis que les points isolés sont repoussés. Un mode de pensée inspiré de la physique de l’électro-magnétisme.

  • ForceAtlas:

C’est un des algorithmes “maison” de Gephi, créé par Mathieu Jacomy en 2007.

Il est pensé pour mettre en valeur les réseaux “petit monde” (pour un rappel sur ces réseaux, voir notre premier billet de cette série), et de manière plus générale, les réseaux invariants d’échelle (“scale-free network”).

Notre réseau exemple spatialisé avec l’algorithme ForceAtlas, paramètres par défaut sauf “force de répulsion = 2000.0”

On prendra garde à la configuration précise de l’algorithme, notamment à celle des forces d’attraction et de répulsion. Une force de répulsion trop faible (ou une force d’attraction trop grande) risque d’aboutir à des superpositions malvenues, et de rendre le graphique illisible.

Notre réseau exemple spatialisé avec l’algorithme ForceAtlas, paramètres par défaut – en particulier avec  “force de répulsion = 200.0”

L’auteur recommande un usage pour des données ne dépassant pas 10.000 nœuds, du fait de la complexité quadratique de l’algorithme, et du temps de calcul qu’elle engendre.

  • Yifan hu proportionnal

Pour traiter de plus grandes bases de données, on pourra se tourner vers l’option “Yifan Hu proportionnal”, du nom d’un chercheur de Yahoo! research qui a produit des travaux remarquables sur la visualisation de grands réseaux, dont on utilise ici un algorithme de 2005. On se référera par ailleurs avec bonheur à sa récente revue de littérature co-écrite avec Lei Shi [2015] pour mieux comprendre l’état actuel des débats sur la visualisation de grands réseaux.

Cet algorithme permet l’exploitation de réseaux allant jusqu’à 100.000 nœuds

Notre réseau exemple spatialisé avec l’algorithme Yifan Hu proportionnel

On note également Force Atlas 2, un autre algorithme spécifique à Gephi, qui utilise certains mécanismes d’approximation similaire pour traiter de très grandes bases de données.

  • Fruchterman Reingold

Pour une base de données peu importante, on pourra choisir l’option “Fruchterman Reingold” d’après l’algorithme de ces deux auteurs [1991].

Notre réseau exemple spatialisé selon l’algorithme de Fruchterman & Reignold (1991) sous Gephi

Une visualisation devenue classique, mais un algorithme d’une complexité importante, qui la disqualifie pour l’étude de grands réseaux.

Une barre d’attente à laquelle il faut s’habituer lorsque l’on utilise cet algorithme avec des données un peu conséquentes…

Insister sur les divisions:

  • Open ord

Open Ord est un algorithme pensé pour décrire des réseaux qui ne seraient pas des petits mondes, et dont on voudrait mettre en avant les différents groupes (clusters) constituant. S’inspirant de Fruchterman-Reingold, qui devient ici un cas particulier des traitements possibles, l’algorithme cherche aussi à s’affranchir de la complexité quadratique inhérente aux modèles “force-based” que nous venons d’évoquer.

Une idée maîtresse pour cet algorithme est de permettre de couper certains liens les plus longs (dans la représentation graphique s’entend) – ce qui augmente l’allure “découpée” du dessin. Le paramétrage de l’option “edge-cut” permet de définir à partir de quelle longueur il est tolérable de couper. La valeur est comprise entre 0, ce qui donnerait dans ce cas le même résultat qu’avec Fruchterman-Reingold, et 1 (niveau qui maximisera le partitionnement visuel des données).

Notre exemple de réseau spatialisé avec Open Ord – edge cut: 0.20

Faire varier cette valeur donne évidemment des graphiques significativement différents.

Notre exemple de réseau spatialisé avec Open Ord – edge cut: 0.95

Ces visualisations ont pour intérêt une certaine clarté, et une bonne capacité à traiter des grandes bases de données. Elles sont toutefois à manier avec précaution.

L’accroissement des distances physiques entre les points donnent l’illusion que certains sont très éloignés, quand la distance qui les sépare dans le graphe est en réalité assez courte. Elles sont par conséquent à réserver à des cas où la séparation du réseau en différents clusters très distincts est véritablement nette et significative.

Privilégier l’ordonnancement des individus selon un critère d’intérêt

Plus qu’au tracé du réseau lui-même, on peut s’intéresser aux places relatives de chacun des nœuds selon un critère particulier. Peu m’importe qui échange avec qui, je m’intéresse ici à qui échange le plus avec les autres, ou qui est le plus central dans les échanges entre individus de mon réseau.

Ces options permettent des visualisations relativement spectaculaires – et c’est bien là leur valeur. En dehors de tout petits réseaux, le tracé du réseau devient illisible. L’information véhiculée par le graphique n’excède alors plus celle qu’aurait donné un tableau ordonnant les individus selon le critère d’intérêt.

  • Circular

Demande l’installation du plugin Circular Layout.

La logique globale de cet algorithme est plutôt simple: on trace un cercle, sur lequel on projette chacun des nœuds, en les ordonnant selon un critère défini par l’utilisateur: du plus haut au plus bas degré par exemple, ou du plus central au moins central…

Notre exemple de réseau spatialisé avec Circular, en choisissant d’ordonner les nœuds par degrés décroissant.

  • Radial Axis

Demande l’installation du plugin Circular Layout.

Là encore, un définit un critère d’intérêt (degré, centralité…), mais au lieu de représenter les nœuds sur le cercle, on les représente sur des axes qui “rayonnent” autour du cercle. Sur chaque axe, on regroupe les individus possédant au même niveau le critère d’intérêt (même degré, même centralité, etc.).

Notre exemple de réseau spatialisé avec Circular, en choisissant d’ordonner les nœuds par degrés décroissant.

Ces deux algorithmes sont d’une complexité limitée (0(n)) , et permettent donc le traitement de grandes bases de données.

VERS UNE ANALYSE MATHÉMATIQUE 

Les possibilités de visualisation d’un réseau sont extrêmement larges, et les graphiques obtenus fondamentalement différents. Il convient donc de se poser les bonnes questions quant à la conception d’un graphique, pour faciliter sa lecture et non la manipuler. Et il convient surtout de passer, une fois la visualisation faite, à une autre étape: celle de l’analyse à proprement parler, qu’aucun graphique ne peut remplacer. Ce sera bien sûr le thème du prochain billet de cette série.

Bibliographie

BASTIAN M., HEYMANN S., JACOMY M. (2009). “Gephi: an open source software for exploring and manipulating networks”International AAAI Conference on Weblogs and Social Media.

FRUCHTERMAN, Thomas M. J,  REINGOLD, Edward M. (1991), “Graph Drawing by Force-Directed Placement”, Software – Practice & Experience, Wiley, 21 (11): 1129–1164

MARTIN S., BROWN W.M., KLAVANS R., BOYACK K., (2011)  “OpenOrd: An Open-Source Toolbox for Large Graph Layout“, SPIE Conference on Visualization and Data Analysis, 2011

HU Yifan, LEI Shi, “Visualizing Large Graphs“, (2015)  Wiley Interdisciplinary Reviews: Computational Statistics, Volume 7, pages 115-136.

Florian CAFIERO

Ancien élève de l'Ecole Normale Supérieure Paris-Saclay et diplômé de l'Ecole nationale des chartes, Florian Cafiero est ingénieur de recherche en mathématiques appliquées aux sciences humaines et sociales au CNRS. Il enseigne les méthodes quantitatives appliquées aux sciences humaines à l'Ecole nationale des chartes.

More Posts - Website

Follow Me:
TwitterLinkedIn

Homemade manuscript OCR (1): OCRopy

This post is the first of a small series centred on optical text recognition applied to manuscripts. There are many interesting research projects dealing with this question, but my purpose here is quite different: I wish to demonstrate how it is now possible for a single researcher to quickly get usable results with some of the open source tools that are out there, starting with OCRopy and CLSTM.

The field of optical character recognition (OCR) applied to manuscripts (handwritten text recognition) is rapidly evolving, especially now that artificial intelligence methods, such as neural networks, are getting more widespread. For the scholar of medieval manuscripts, it has interesting applications, and it can help in the constitution of textual databases or in the collation of witnesses.

Ocropy is a « collection of document analysis programs »1, that uses a Long Short Term Memory (LSTM) architecture for Recurrent Neural Networks2. It has been successfully applied to a variety of printed scripts, including old prints3. In particular, it is already being used to acquire the texts of incunabula. There are already some very good documentation on this subject, particularly Uwe Springmann’s slides from a workshop in Munich in 20154 and a paper about the Ocrocis environment5.

My interest in OCRopy started with the modest goal of digitising the text of XIXth century editions of Old French texts (namely, the collection of the Anciens poëtes de la France). With it, I got close to 1% error after some time, but soon, motivated by the successful use of OCRopy with incunabula and news I heard from a colleague6, I turned to trying it on manuscripts.

Setting up OCRopy

For the Ubuntu user (probably also for other Linux distributions), OCRopus is very easy to install (it may prove harder with Mac OS, though), following the 4 simple steps described on the repository. Once installed, the next step is getting the image files for the text you want to recognise, preferably in TIF format, and in good resolution (I used 600 DPI images, but the more common recommendation is 300 DPI). Some digital libraries offer such files with an open license, for instance the E-Codices platform7.

Capture d'écran de Scan Tailor. Ici, séparation d'une page en deux

Fig. 1: screenshot of Scan Tailor. Here, splitting the pages.

Depending on the case, you might have to preprocess the images, to rectify orientation, clean the image, crop it, etc. There are many tools to do that, for instance ScanTailor (fig. 1). Once your images are ready, and in a ./tif folder, you are good to go.

Preparing data: from layout analysis to ground truth production

Binarisation and layout analysis: column and line segmentation

Before anything, you will need (if you haven’t done it before) to binarise your images, and to try to detect columns and lines8. This first command,

$ ocropus-nlbin tif/* -o book

will binarise your images and place them in a book folder, and,

$ ocropus-gpageseg book/*.bin.png

will try to perform an identification of columns and lines. For both these commands, you might have to use the -n option, to deactivate error checking, and the skipping of pages or lines in your data. This part of the tools, layout analysis, is not based on training (yet) and can only be configured through a few options, not necessarily very documented. Some are related to scale, others to noise or baseline thresholds; I haven’t had much experience playing with those, so any feedback in comment to this post will be appreciated. Indeed, with manuscripts, this phase is often quite problematic, since lines or columns are not necessarily very regular…

On my experimentations on ms. Bodmer 68, using uniform and gaussian modes, I had the following error rates in column and line segmentation on fol. 134r, 136v and 142r :

fol. Column errors % Line errors %
Default
134r 25 60 6 7
136v 13 31 2 2
142r 22 52 1 1
Gaussian
134r 27 64 4 5
136v 16 38 4 5
142r 22 52 1 1

I do not count here errors related to lines amputated from beginning or end, and false positive (noise lines). In my experience, this is the part were Ocropy (as well as the other tools I tried) are least effective. In the end, I did column segmentation myself, with an image processing tool, and corrected line segmentation manually with Gimp. One can hope there will be improvements in this area in the near future9

Fig. 2a: a successfull segmentation

Fig. 2a: a successful segmentation

Fig. 2b: an extreme segmentation failure

Fig. 2b: an extreme segmentation failure

Ground truth

The first step in training a model to OCR a manuscript will then be to create some ground truth data, that is a correct (or, as correct as possible) transcription of a sample of the manuscript, on which to train the model, so it will learn to recognise the handwriting. This can be easily done with Ocropy, by creating an html file, with line images and text boxes:

$ ocropus-gtedit html -H 35 book/*/*.bin.png -o gt.html

and then,… well, then you have to transcribe a part of the text, to have something to train with (fig. 3).

Fig. 3: ground truth production

Fig. 3: ground truth production

The question is: how many lines do you need to get an effective model? Usually, with deep learning, the answer is: the more data, the better. For my part, I have had good results with as few as 400 lines and have not had the chance to train with more than 2000 yet. According to Uwe Springmann and David Kaumanns10, good results on incunabula were obtained with between 1000 and 5000 training lines, the latter for harder cases. In any case, I would advise you to start small (for instance, 400 lines), then train, use the model to annotate 400 more, correct, re-train, and so on until you get a satisfying model.

Training on a medieval manuscript: the ms. Bodmer 68 of the Chanson d’Otinel

Training

Once you have some ground truth data, you can begin training (that can take some time). First, you will have to extract ground truth from the html file used for transcription:

$ ocropus-gtedit extract gt.html

The lines you transcribed will go into the book folder, into the subfolders created for each page, and will be labelled <image-name>.gt.txt.

Be careful that all the line of the gt.html file containing text will be extracted (empty lines will be skipped), not only the one you edited. So, if you have some uncorrected lines with text, you have to pay attention not to include them in training or testing data.

So, in order to train, place 90% of your data in a train folder, and 10% in a test folder, to estimate the success of each model. It is then time to train. The last thing to do, if you have special characters, is to modify the file chars.py, located in your ocrolib installation (in Ubuntu, it will be in /usr/local/lib/python2.7/dist-packages/ocrolib/). The syntax is simple enough (fig. 4).

Fig. 4: the beginning of my chars.py

Fig. 4: the beginning of my chars.py

Once it is done, you can launch training with:

$ ocropus-rtrain -o myModel -d 1 train/*/*.bin.png

The -d 1 option is here to allow you to visualise the training steps (fig. 5). You can safely remove it if you want to gain time. In each training iteration, a line is read, and the results from the guess of the neural network (OUT) are compared to the ground truth (TRU), and aligned text (ALN).

54009 43.77 (616, 48) train/0017/010014.bin.png
TRU: u'D efo\ua75b\u017f hat\u0131ll\u0131e a une l\u0131ue g\u0363nt'
ALN: u'D efo~~ hat~ll~e a une l~ue g~nt'
OUT: u'D efo~\u203a hat\u2020ll\u2020e a une l\u2020ue gnt'

Fig. 5: Ocropy training

Fig. 5: Ocropy training

The visualisation shows you ground truth and training image, predicted and aligned results, probabilities for characters (green for space, blue for character with highest probability and yellow for absence of character) and the evolution of error11.

Every n iterations, the model is saved (default is 1000, but you can modify it with the -F option). Other useful options are:

-r LRATE, --lrate LRATE
LSTM learning rate, default: 0.0001
-S HIDDENSIZE, --hiddensize HIDDENSIZE
# LSTM state units, default: 100
-N NTRAIN, --ntrain NTRAIN
# lines to train before stopping, default: 1000000
--load LOAD start training with a previously trained model

The --load options allows you to retrain on an existing model (or, if you want, to split training in a few different sessions), and the -N to decide after how many iterations the training must end. But let’s have a look at the two other parameters, that will have an important effect on the training results (and training time); -r is the learning rate. In my experience, the default value is quite good, but I would be happy to have feedback on it; -S is the number of state units of the model. Increasing it to 200 or even 400 did wonder: my models learned faster and/or achieved lower error rates. On the other hand, training was more computing-intensive, and it considerably augmented the time/computing power needed for each iteration. I will develop this point in my next post, about CLSTM.

The other question is how long a training is needed to get good results. According to Uwe Springmann and David Kaumanns experiments on incunabula, they got best results with 30,000 to 200,000 iterations. Expressed as a number of epochs (an epoch is a number of iterations equal to the number of training lines, so with 400 training (ground truth) lines, it will be 400 iterations), they advise a number of 100 epochs12. As for me, best results were obtained for each model:

  • on modern print: 6 epochs (6287 training lines, 39 000 iterations, error at 1.75%, 200 state units);
  • on manuscript Bodmer 68: training 1, after 27 epochs (1722 training lines, 46 000 iterations, error at 17%, 100 state units); training 2, 31 epochs (1722 training lines, 54 000 iterations, error at 9.7%, 100 state units);
  • on manuscript Digby 23, with CLSTM: 74 epochs (403 training lines, 30 000 iterations, error at 9%, 400 state units).

For now, it seems that the raw number of iterations is a better indicator that the number of epochs, and 30 000 iterations is a good start, but it remains largely to be explored.

If you have such feedback to share, please do not hesitate to put it in a comment or send it to me. If I get enough of it, I will try to statistically estimate better configurations and make a post about it.

Evaluating the results

Once you have trained and produced a few models, the next step is to comparatively assess their performance and error rate. To do that, you can use the following bash code:
for i in *.pyrnn.gz; do
echo "$i" >> modeltest
ocropus-rpred -m $i test/*/*.bin.png
ocropus-errs test/*/*.gt.txt 2>>modeltest
done

This way, you will get a modeltest file, with the error rate of all models. For each model, you will have something like this:
bodmer-00054000.pyrnn.gz
errors 615
missing 0
total 6340
err 9.700 %
errnomiss 9.700 %

that is, the raw number of errors, of missing characters, total number of characters, and percentage of error.

On manuscript Bodmer 68, I started a first training, with 1722 lines of my transcription of the Chanson d’Otinel, and the error followed the evolution presented in fig. 6.

Fig. 6: first training on manuscript Bodmer 68

Fig. 6: first training on manuscript Bodmer 68

As you can see, the model soon arrived at around 20% of error; at iteration 46 000, it was at 16,32% of error, and never decreased afterwards.

I wasn’t quite satisfied with these results, that were not so usable. So, I went through a phase of checking the correctness of training data and its alignment with segmented lines, editing chars.py to include all the characters I needed (such as long ſ), etc. And I trained again: you can see how effective the increase of quality of input data was on this new training (fig. 7).

Fig. 7: second training on manuscript Bodmer 68

Fig. 7: second training on manuscript Bodmer 68

This time, the model got to 9.7% error, at iteration 54 000, and error never decreased afterwards. You can also observe some punctual spikes in error at iteration 23 000 and 57 000.

To understand the source of the errors, and eventually do some post-treatment to lower error rate, you can have a look at the confusions of characters, using the command:

$ ocropus-econf test/*/*.gt.txt

This will give you the most frequent confusions, in a form similar to:

32 _
29 _
21 _
13 _ ı
10 _
8 z _
7 n m
6 _
6 _ t
6 _ u

As you can see, in my case, most errors were related to whitespace, or confusions between whitespace and characters or abbreviations, or, also, in the succession of strokes constituting n, m or ı. If you want to see as well if the errors are dependant of a certain context, you can try the -C option:

$ ocropus-econf -C2 test/*/*.gt.txt

In my case, the most frequent confusions with context were more explicit:

5 Q _nt Q ͣnt
4 ml_t ml̃t
2 t_re t͛re
2 aı_n aı́n
1 cuıne cum_e
1 e ot e_ot
1 m_nt munt
1 tr_uſ trıuſ

As you can see, most errors were related to abbreviations (superscript a, tildes, etc.) or succession of minim strokes (ı, n, m, u and their various combinations) that are also hard for humans when they cannot perceive the full word.

On the other hand, the results obtained were quite usable, now. To give you an idea, here is a sample of the recognition, compared with the binarised folio of the manuscript (fig. 8). I underline errors, and indicate missing characters with ø.

v erent leſ noz uenør tut eſfreez
p aſſent auant ſıſ ont returnez
p ar gͣnt eſfoeꝛ ont paıenſ reculez
Q uatte aıpenz δe terre meſurez
D eſ abatuz e δeſaceruelez
e ſt tut lı champ pleıø e ẽꝯbrez
L ez vn pareı ſa reſteıt coꝛſabrez
Ø enſeınıe eſcrıe paıen a meı eſtez
L eſcu enbrace verſ leſ noø eſt alez
p ar gͣnt u͛tu eſt aſ eſtrøuſ fermez
Ø a euſt leſ noz Gtaanẽt δeſturbez
Q nt en leſcu la feru amırez [missing accent]
p ar teu u͛tu ken ſun frũt lar entez
Deſuz le halme a lun δeſ oılz quaſøeø
L ı paıen eſt δel colp eſpontez
N en a ſucurſ tut eſt abanδunez
J gnelemẽt le laıſıſt amørez
ø reıſ bonſ uaſſalſ a lenfeſ apelez
c o eſt Galδı́n e fauchet lı haſtez
e δaıgremũt balδeδeı́n lafıez .

Fig. 8: ms. Bodmer 68, col. 221b, binarised.

Fig. 8: ms. Bodmer 68, col. 221b, binarised.

In some cases, it might be useful to do some automatic post-treatment, to correct the most frequent errors, for instance with a database of known/existing words. In any case, once you are satisfied with your model, it is time to OCR the rest of the manuscript.

Acquiring the rest of the text and extracting it

To apply recognition to the full document, you can do:

$ ocropus-rpred -m myModel.pyrnn.gz book/*/*.bin.png

This will predict the text of the full book folder. You can then extract it in several formats. You can get it as HOCR, using:

$ ocropus-hocr book/*.bin.png

The HOCR format is interesting, as it gives you, for each text line, its alignment with the original document (that you can transform, with XSLT, to TEI facsimile elements, if you so wish):

<div class='ocr_page' title='image book2/0001.bin.png; bbox 0 0 2140 2836'>
<span class='ocr_line' title='bbox 375 173 1813 296'>Q uatre cenz mılıe cheualerſ puıſ aueır.</span><br />
<span class='ocr_line' title='bbox 374 264 1492 354'>p uıſ men cũbatre a carll̃ ⁊ a franceıſ.</span><br />
<span class='ocr_line' title='bbox 322 342 1382 437'>G ueneſ reſpunt ne uuſ a ceſte feız.</span><br />
<span class='ocr_line' title='bbox 361 429 1586 520'>D e uoz paıenſ mult grant ꝑte ı au͛reız.</span><b

The only problem with this format is with extracting manually corrected lines, that I fear may be omitted in the export procedure. You can also extract it with:

$ ocropus-gtedit text book/*/*.bin.png

This will give you a correct.txt file, with the text, and a separate reference.html file, with the indexed line images.

If you want to correct the results from the prediction, before extracting it, you can do instead:

$ ocropus-gtedit html -H30 book/*/*.bin.png

It will give you a correction.html file, that you can again edit and correct. Here, we have to be cautious, because, when extracting text, the predicted (.txt) lines are used by default, instead of the ground truth ones (.gt.txt). So, once we have corrected, we will need to remove all existing text files, extract, and rename the files from .gt.txt to .txt (yes, it is a bit of a bother):

rm book/*/*.txt
ocropus-gtedit extract correction.html
rename "s/.gt.txt/.txt/g" book/*/*.gt.txt
ocropus-gtedit text book/*/*.bin.png
ocropus-hocr book/*.bin.png

And now you have your text ! You can convert it to TEI or some other format, and start editing.

From one manuscript to the next: trying to reuse a model on another manuscript

So, from the beginning of this post, I have talked of training a model for a specific manuscript. One question remains: can this model be applied to another similar manuscript, or retrained on an other manuscript ?

I tried to apply the model created for Bodmer 68 (last third of the XIIIth century, Gothic Textualis libraria, anglo-norman) to another, quite different, manuscript I wanted to OCR, the Digby 23 (first half of the XIIth century, Praegothica, anglo-norman as well). I will talk more about the model developed for this manuscript with CLSTM in my next post, but the outline is that, without retraining, I had an error of 33% (instead of 9.7%). After a few epochs of retraining (with the --load option), it went down to 15%, but never below. In the same time, parts of the model started “exploding”, and lowering learning rate13 did not solve the problem:

# oops, got FloatingPointError overflow encountered in exp
 Traceback (most recent call last):
 File "/usr/local/bin/ocropus-rtrain", line 286, in
 pcs = network.trainSequence(line,cs,update=do_update,key=fname)
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 890, in trainSequence
 self.outputs = array(self.lstm.forward(xs))
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 605, in forward
 xs = net.forward(xs)
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 661, in forward
 outputs = [net.forward(xs) for net in self.nets]
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 559, in forward
 self.WIP,self.WFP,self.WOP)
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 428, in forward_py
 go[t] = ffunc(gox[t])
 File "/usr/local/lib/python2.7/dist-packages/ocrolib/lstm.py", line 376, in ffunc
 return 1.0/(1.0+exp(-x))

It soon turned out a lot more effective to retrain a new model from scratch. Actually, every time, in my experience, retraining an existing model, be it for print or manuscript, though it might be faster, was less effective in the end.

That’s it for now ! Do not hesitate to leave observations, remarks or feedback in the comments.

  1. Thomas M. Breuel, Ocropy: Python-based tools for document analysis and OCR, 2014, https://github.com/tmbdev/ocropy. []
  2. Thomas M. Breuel, Adnan Ul-Hasan, Mayce Ali Al-Azawi and Faisal Shafait, « High-Performance OCR for Printed English and Fraktur Using LSTM Networks », 2013 12th International Conference on Document Analysis and Recognition, 2013, DOI: 10.1109/icdar.2013.140, URL: http://staffhome.ecm.uwa.edu.au/%7E00082689/papers/Breuel-LSTM-OCR-ICDAR13.pdf. []
  3. You can find a list of publications related to Ocropy on the project wiki, http://github.com/tmbdev/ocropy/wiki/Publications. For an example of application to modern print, you can see the blogs posts by Dan Vanderkam, « Extracting text from an image using Ocropus », danvk.org, http://www.danvk.org/2015/01/09/extracting-text-from-an-image-using-ocropus.html ; Id, « Training an Ocropus OCR model », danvk.org, http://www.danvk.org/2015/01/09/extracting-text-from-an-image-using-ocropus.html. []
  4. OCR und Nachkorrektur alter Drucke für die Geisteswissenschaften / OCR and postcorrection of early printings for digital humanities, Centrum für Informations- und Sprachverarbeitung (CIS) Ludwig-Maximilians-Universität München, 2015, http://www.cis.uni-muenchen.de/ocrworkshop/program.html []
  5. Uwe Springmann and David Kaumanns, Ocrocis: a high accuracy OCR method to convert early printings into digital text, 2015, http://cistern.cis.lmu.de/ocrocis/tutorial.pdf. []
  6. Thanks to Thibault Clérice for the ideas and discussions, and for initially pointing me to the documentation for using OCRopy. []
  7. E-Codices: Virtual Manuscript Library of Switzerland, http://www.e-codices.ch/. []
  8. I used the same folder architecture as the one in the documentation by U. Springmann, of the cited workshop, OCR and postcorrection []
  9. From what I understand from the Ocropy Github page, the original developer of Ocropy, T. Breuel, is planning on working on deep learning for layout analysis. []
  10. U Springmann and D. Kaumanns, Ocrocis…, p. 13 []
  11. For more information, have again a look at U. Springmann’s slides. []
  12. U. Springmann and D. Kaumanns, Ocrocis…, p. 13 []
  13. As advised in a Github issue of Ocropy, http://github.com/tmbdev/ocropy/issues/5 []

Jean-Baptiste Camps

Diplômé de l'École nationale des chartes et docteur en études médiévales de l'Université Paris-Sorbonne (la Chanson d'Otinel…, dir. Dominique Boutet ), Jean-Baptiste Camps est responsable pédagogique du master «Humanités numériques» à l'École nationale des chartes (PSL). [CV et liste des publications, voir : http://paris-sorbonne.academia.edu/JeanBaptisteCamps]

More Posts - Website

Follow Me:
LinkedIn

L’ascension des Médicis – analyse des réseaux (2)

Dans ce deuxième billet consacré à l’analyse des réseaux, nous nous intéressons à un exemple intéressant d’application de la théorie des réseaux aux sciences humaines. L’article dont nous parlerons ici, publié en 1993 par Padgett et Ansell, pose une question à laquelle beaucoup pensaient savoir répondre: pourquoi les Médicis ont-ils réussi à s’imposer à Florence, face à des familles et clans tout aussi puissants qu’eux ? A travers cet article et les développements qu’il a suscité (notamment dans Jackson, 2008), nous explorerons quelques aspects fondamentaux de l’analyse des réseaux en sciences humaines: la diversité de la nature des liens, la notion de centralité et ses différentes variations etc.

Le pouvoir à Florence au Quattrocento

Le pouvoir des Médicis sur la cité florentine s’établit au début du XVe siècle grâce à Cosimo de’ Medici (1389-1464), dit aussi Cosme l’ancien. Leur ascension peut initialement paraître surprenante, les Médicis étant une famille objectivement moins puissante que bien d’autres familles de l’oligarchie alors au pouvoir.

Portrait de Cosimo Il Vecchio de Medici - Agnolo Bronzino (~1565/1569), Galerie des Offices, Florence

Portrait de Cosimo Il Vecchio de Medici – Agnolo Bronzino (~1565/1569), Galerie des Offices, Florence

Les Strozzi, par exemple étaient à la fois plus riches, et plus puissants politiquement, possédant notamment plus de sièges dans les instances législatives.

Une interprétation souvent avancée pour expliquer ce phénomène est d’ordre socio-économique. Les Médicis auraient incarné une classe “moyenne” et marchande, face aux familles plus riches, et surtout à la richesse plus ancienne. Pourtant d’après cet article, la richesse des soutiens des Médicis, et l’évolution de celle-ci, ne se distingue pas de celles des soutiens des oligarques. De surcroît, la richesse des Médicis aurait été tout à fait comparable à celle de ces rivaux oligarques. L’explication par une sorte de guerre des classes ne semble donc pas si probante.

“It’s the network stupid !”

L’article de Padgett and Ansell tente donc une explication alternative de ce fait étonnant par l’analyse des réseaux. Le succès des Médicis, menés par celui qui deviendra le pater patriae, viendrait de leur position centrale dans un réseau de relations économiques, politiques et matrimoniales.

Pour examiner en détail les réseaux d’influence des Médicis, les auteurs encodent séparément différents types de liens entre les familles: immobiliers, matrimoniaux, commerciaux et bancaires. Plusieurs graphes sont ainsi créés séparément puis superposés.

Structure des relations entre 92 "familles" florentines

Structure des relations entre 92 “familles” florentines

Une pratique dont la trivialité n’a d’égal que l’utilité. Ceci permet d’effectuer aussi bien des analyses synthétiques que plus détaillées quant aux liens unissant les différentes familles florentines.

Une analyse rapide fournit assez rapidement des résultats. Si l’on ne fait que compter les relations qu’entretiennent les Médicis avec d’autres familles, on remarque déjà que leur réseau est un peu plus étendu que celui de leurs rivaux. Par exemple, les Médicis arrivent en tête du nombre de mariages conclus avec d’autres familles.

Pour autant, leur domination en la matière n’est pas absolue, ce nombre dépassant d’environ 50% celui des alliances matrimoniales des Guadagni ou même des Strozzi. Suffirait-elle à expliquer l’irrésistible ascension de cette famille ? C’est dur à croire.

De l’importance d’être central

Ce que montre l’analyse des auteurs, c’est que les Médicis doivent moins leur pouvoir à une fortune ou à un nombre de relations différents des autres qu’à l’agencement même de ces relations.

Il existe ainsi une différence majeure entre les soutiens des oligarques et ceux des Médicis. Les premiers se connaissent majoritairement entre eux, et entretiennent des relations de différents types. Des relations complexes à gérer, qui ont pu générer ou exacerber rivalités et conflits d’intérêts.

A l’inverse, les différents soutiens des Médicis n’entretiennent que peu de liens entre eux. Ils ont besoin des Médicis pour accéder aux autres membres du réseau de soutien à cette famille. De surcroît, ces soutiens n’ont pas n’ont plus de connexions directes aux oligarques: ils doivent également passer par les Médicis pour s’adresser à eux.

Dans son livre de 2008, Matthew Jackson propose d’analyser ce phénomène en termes de centralité,  plus précisément de centralité d’intermédiarité (betweenness centrality).

Soit P(ij) le nombre de “plus courts chemins” entre deux familles i et j. Soit Pk(ij) le nombre de ces plus courts chemins passant par la famille k. Plus Pk(ij) est élevé par rapport à P(ij), plus on peut considérer que la famille k est un intermédiaire crucial pour les relations entre les familles et j.

Pour déterminer l’importance qu’a une famille (ou un noeud en général) pour connecter d’autres familles entre elles au sein d’un réseau, on calcule la moyenne de ces Pk(ij) pour toutes les familles i et j du réseau.

La centralité d’intermédiarité se calcule donc tout bêtement ainsi:

centralite-dintermediarite

Reprenant les bases de données utilisées par Padgett et Ansell, Matthew Jackson calcule ainsi cette centralité de la famille Médicis au sein de son réseau: 0.522 ! En d’autres termes, les Médicis sont plus de la moitié du temps sur le plus court chemin entre deux grandes familles florentines de leur réseau !

 Les Guadagni, qui arrivent seconde famille la plus influente selon cette mesure, obtiennent un score plus de moitié moindre (0.255). Quant à la centralité d’intermédiarité des Strozzi, elle dépasse péniblement les 10% (0.103).

Conclusions méthodologiques

Sans revenir sur le contenu scientifique de cet article, on retiendra deux points méthodologiques importants:

  • Dès l’encodage de la base de données, il est important de relever les différents types de liens pouvant unir les individus. Contrairement aux réseaux en mathématiques, ou parfois en physique, la notion de lien est, dans nos disciplines, avant tout métaphorique, et peut regrouper des réalités disparates. Il convient d’en être conscient, et de se laisser les moyens d’étudier séparément les différents types de lien – quitte à effectuer des regroupements ex post.
  • Dans l’analyse d’un réseau, la forme du graphe et ses propriétés peuvent être tout aussi importantes, voire plus importantes, que des résultats de base comme le nombre de liens associés à un nœud. L’importance des Médicis ici n’est pas tant manifeste à travers l’étendue de leur réseau que par la forme même de ce réseau. Un aspect qu’il est donc crucial de ne jamais négliger.

Bibliographie:

JACKSON Matthew O., Social and Economic Networks, Princeton University Press, 2008

PADGETT John F., ANSELL Christopher K., “Robust Action and the Rise of the Medici, 1400-1434. “,  American Journal of Sociology, 98-6, 1259-1319, mai 1993

Florian CAFIERO

Ancien élève de l'Ecole Normale Supérieure Paris-Saclay et diplômé de l'Ecole nationale des chartes, Florian Cafiero est ingénieur de recherche en mathématiques appliquées aux sciences humaines et sociales au CNRS. Il enseigne les méthodes quantitatives appliquées aux sciences humaines à l'Ecole nationale des chartes.

More Posts - Website

Follow Me:
TwitterLinkedIn

Un vrai filet à poissons ? – L’analyse des réseaux (1)

“C’est un réseau sans issue, un vrai filet à poissons que je tends autour de lui, une robe au faste perfide”

Eschyle, Agamemnon in Tragédies complètes (trad. Paul Mazon), éd. Gallimard, coll. « Folio », 1982, p. 308, vers 1282-1283

Nous commençons avec ce rapide billet un petit parcours théorique et pratique au sein de la très en vogue “analyse de réseaux”. Alors que les productions en sciences humaines s’en réclamant ne cessent de s’accroître, il nous a paru important de revenir sur les enjeux méthodologiques et sur la portée scientifique de ce courant d’analyse. La variété des disciplines utilisant l’analyse des réseaux est confondante, tout comme la diversité des problématiques auxquelles on lui demande de répondre. Il faut dire que son usage est séduisant: le terme “réseaux” connote une modernité certaine, et les représentations graphiques afférentes flattent l’œil… A tel point que l’on se demande parfois si on n’utilise pas ce type d’outils à tort et à travers, et si l’on ne trouve pas dans nos réseaux des prises qui n’auraient rien à faire…

Clytemnestre hésitant avant de frapper Agamemnon endormi

Clytemnestre hésitant avant de frapper Agamemnon endormi – Pierre-Narcisse Guérin, 1817, musée du Louvre (Inv. 5185)

Si l’analyse des réseaux en sciences humaines paraît parfois fourre-tout, et si certains résultats sont peu convaincants, c’est selon nous à cause de deux méprises: l’une sur la nature des réseaux; l’autre sur la nature de l’analyse des réseaux. 

SUR LA NATURE DES RÉSEAUX

Graphes et réseaux

L’analyse des réseaux nous vient originellement de l’informatique théorique et de la théorie des graphes. C’est de ces champs que nous héritons une grande majorité des outils que nous utilisons. Revenons donc, de manière informelle, sur quelques définitions importantes.

La définition d’un réseau est relativement simple, et dérive de la notion de graphe. Intuitivement, un graphe est un ensemble d’entités, appelés nœuds, reliées par des liens, aussi nommés arcs ou arêtes. Lorsque les nœuds sont nommés, on appelle ce graphe un réseau.

On distingue deux types de relation entre des nœuds:

  • Les relations orientées

On peut représenter les liens entre des entités par des flèches lorsque ces liens sont “orientés”.

Exemple de graphe orienté représentant les liens entre quatre entités

Exemple de graphe orienté représentant les liens entre quatre entités

Dans le monde physique, on peut par exemple représenter de la sorte un système routier ou ferroviaire comportant des sens uniques, des flux migratoires, le passage d’un courant électrique à travers un circuit…

  • Relations non-orientées

Dans le cas où la relation n’est pas orientée, on représente les liens entre individus par des traits.

graphe_non_oriente

Graphe non orienté, représentant les liens entre six individus

On considère dans ce cas des liens qui peuvent être considérés en première approximation au moins comme symétrique: contrat, alliance, amitié. Cette modélisation est souvent usitée car elle est souvent un peu plus maniable mathématiquement.

Une modélisation universelle ?

Le cadre théorique de la théorie des réseaux semble suffisamment souple pour s’accommoder d’à peu près n’importe quelle problématique de recherche. Pourtant, il existe quelques limites dont il est nécessaire d’être conscient.

  • La simplicité des relations

L’analyse des réseaux ne peut que représenter des interactions relativement simple entre individus. On peut certes ajouter de l’information – des liens orientés ou non, éventuellement pondérés – mais celle-ci est limitée, et rend l’analyse moins aisée.  Il est donc nécessaire de réfléchir à ce que le lien représenté révèle ou masque de la relation entre les individus.

Les liens unissent par ailleurs au maximum deux individus, ce qui ne décrit pas nécessairement toutes les situations possibles. On peut par exemple vouloir décrire une situation dans laquelle, soit A, B, C sont tous reliés entre eux, soit ils ne sont pas du tout reliés – c’est un cas qui peut arriver dans certaines coalitions militaires, accords commerciaux, amitiés etc. On peut objecter, à raison, l’existence de la notion  d’hypergraphes, qui regroupent plusieurs individus dans un même lien.

hypergraph

Un exemple d’hypergraphes, regroupant ici un, deux ou trois nœuds.

Mais les hypergraphes sont également beaucoup moins facilement manipulables, et la plupart des outils et logiciels à notre disposition ne les intègrent pas, ou de manière très marginale.

  • La sensibilité aux données manquantes

Les données manquantes sont toujours difficiles à traiter, quel que soit le mode d’analyse employés. Dans l’étude de réseaux, il est encore plus crucial de disposer d’une information la plus complète possible, sur les individus représentés et sur les liens qui les unissent. L’oubli ou le manque d’information sur quelques individus ou liens peuvent changer les trajets les plus courts d’un individu à un autre, risquent de beaucoup influer sur les personnages “centraux” (nous reviendrons sur la notion de centralité dans le prochain article) du graphique etc., et peuvent donc donner lieu à des résultats particulièrement faussés. Il est donc nécessaire de s’interroger sur sa capacité à décrire de manière exhaustive un réseau, avant de tenter de l’analyser.

SUR LA NATURE DE L’ANALYSE DES RÉSEAUX

Pour mieux comprendre ce que la théorie des réseaux peut apporter à la compréhension des objets que nous venons de définir, présentons tout d’abord une problématique importante de ce champ d’études. Pour importer l’analyse des réseaux dans nos domaines, il est important de comprendre comment elle fonctionne et à quoi elle sert dans son milieu “natif”.

Nous en profiterons pour succinctement exposer les principes de quelques outils utiles à l’analyse.

♫ It’s a small world after all ♫

Une intuition de l’homme de lettres hongrois Frigyes Karinthy, exposée dans une nouvelle de 1929 intitulée “Chaînons” (Láncszemek) (Karinthy, 2004), voulait que  nous ne soyons jamais séparé d’un autre individu que par cinq autres:

“Nous devrions sélectionner n’importe quelle personne des 7.2 milliards d’habitants de la planète, n’importe qui, n’importe où. Il parait que, n’utilisant pas plus de cinq individus, l’un d’entre eux étant une connaissance personnelle, il pourrait contacter les individus choisis en n’utilisant rien d’autre que le réseau des connaissances personnelles.”

Beaucoup ont vu en ce passage la naissance d’une théorie qui fera fortune: celle des fameux “Six degrés de séparation”, une question notamment étudiée par la suite par le psychologue américain Stanley Milgram.

On a pu décrire mathématiquement les réseaux ayant ce type de caractéristique – ceux que l’on appelle des petits mondesIls sont caractérisés par deux critères importants à analyser en théorie des réseaux: la distance à parcourir pour aller d’un point à un autre, et le coefficient d’agglomération (ou de clustering).

smallworld

Un exemple de réseau “petit monde”

Les distances (en prenant le chemin le plus court) moyennes et médianes entre nœuds, sont souvent une donnée intéressante à analyser, et sont une caractéristique importante d’un réseau. On les définit de manière triviale comme le nombre (minimal) de nœud par lequel il faut passer pour atteindre un autre nœud, ce nœud étant inclus. On appelle aussi cette distance la distance géodésique.

Dans un petit monde,  la distance géodésique moyenne (L) séparant deux points pris au hasard dans le réseau évolue comme le logarithme du nombre d’individus (n) dans le réseau.

L’autre propriété d’un petit monde est la manière dont les individus y sont regroupés – un petit monde étant typiquement un réseau où les individus sont beaucoup agglomérés.

On mesure principalement l’agglomération de deux manières: le coefficient d’agglomération global (Barrat, Weigt, 2000) et le coefficient d’agglomération local moyen (Watts, Strogatz 1998).

Dans cette dernière mesure, on cherche à savoir à quel point un nœud voisin est lui même relié à ses voisins ou non. S’il est connecté à tous ses voisins, la valeur du coefficient d’agglomération local sera de 1. S’il n’est connecté à aucun autre de ses voisins, ce coefficient sera de 0. Pour avoir une vue d’ensemble de l’agglomération dans le réseau, on calcule la moyenne arithmétique de ces coefficients d’agglomérations locaux – on obtient le coefficient d’agglomération local moyen.

Une mesure peut-être plus simple, dans le calcul comme dans l’information qu’elle contient consiste à compter le nombre de fois où certaines formes géométriques apparaissent dans le graphe. Plus l’on voit on apparaître de “triangles” (trois individus tous reliés entre eux) dans le graphique, plus on considère que l’agglomération est forte. C’est l’intuition sous-jacente du coefficient d’agglomération global.

A partir de ces deux caractéristiques relativement aisée à calculer, on définit ainsi un type de réseaux qui apparaît très fréquemment dans la nature comme dans la société. On retrouve ainsi des réseaux “petit monde” dans l’organisation de nos neurones, dans la manière dont les protéines se connectent entre elles, ou dans la manière dont de nombreux réseaux sociaux, virtuels ou réels, sont agencés. Si un réseau que l’on observe appartient à cette catégorie de “petit monde”, on pourra en déduire qu’il possède toute une série de propriétés déjà connues pour ce type de réseaux. A l’inverse, on s’interrogera sur un réseau qui n’est pas un “petit monde” – qu’est ce qui l’en différencie ? qu’est ce qui fait qu’il n’est pas organisé selon cette organisation répandue ? etc.

L’analyse graphique de réseaux ?

Comme nous le disions en préambule de cet article, il est toujours tentant de tracer des graphiques, souvent impressionnants,  représentant le ou les réseaux que l’on étudie. Une pratique que nous ne saurions trop encourager lorsque l’on commence à étudier sa base de données. La représentation graphique peut alors donner au chercheur des intuitions importantes pour la suite de son étude. Elle peut révéler la présence de formes particulières de graphe, ce qui peut faciliter les analyses à venir.

Par ailleurs, dans le cas où le réseau étudié présente peu d’individus, publier la représentation graphique peut présenter un intérêt certain.

On s’étonne par contre de voir parfois présentés aux lecteurs des graphiques qui deviennent très facilement illisibles, et d’où aucune intuition claire ne peut se dégager. On ajoutera par ailleurs que dans ces cas, la simple représentation graphique, et une éventuelle tentative d’interprétation de celle-ci, ne constituent en rien une analyse satisfaisante des données. L’analyse des réseaux repose, comme nous l’avons très succinctement montrée, sur des concepts et des procédés analytiques précis, qu’on s’étonne souvent de ne pas voir mobilisés.

Nous faisons ainsi nôtre la remarque que formulait Claire Lermercier:

 “Utile pour représenter des réseaux petits ou peu denses, la représentation graphique n’est en rien, en elle-même, une méthode d’analyse.” [Lemercier, 2005]

Une évidence qu’il est visiblement bon de rappeler plus de dix ans après la publication de son article.

QUE FAIRE ?

L’analyse des réseaux propose un ensemble d’outils puissants qui, à notre sens, et au-delà d’écueils évitables, peuvent se révéler précieux pour les sciences humaines. Nous nous proposerons donc de présenter au cours des prochains billets quelques résultats obtenus dans nos disciplines, puis des moyens d’en obtenir de nouveaux.

Dans le prochain billet, nous nous intéresserons ainsi à un exemple d’application de l’analyse des réseaux aux sciences historiques qui fit date, et en profiterons pour présenter les outils d’analyse des réseaux les plus classiques. Un article qui nous emmènera dans la Florence du Quattrocento, au milieu des grandes familles et de leurs luttes de pouvoir.

BIBLIOGRAPHIE

BARRAT Alain , WEIGT Martin, ” On the properties of small-world network models” The European Physical Journal B-Condensed Matter and Complex Systems, Springer, vol. 13, no 3,‎ 2000, p. 547-560

FRANZOSI Roberto, Quantitative Narrative Analysis, Sage Publications, 2009

KARINTHY Frigyes, Karinthy Frigyes összegyűjtött művei;  20Budapest : Akkord, 2004

LEMERCIER Claire, « Analyse de réseaux et histoire », Revue d’histoire moderne et contemporaine 2/2005 (no52-2) , p. 88-112

NEWMAN Mark E.J., Networks: an introduction, Oxford University Press, 2010

WATTS, Duncan J.; STROGATZ Steven H.,  “Collective dynamics of ‘small-world’ networks”. Nature. 393 (6684): 440–442, juin 1998

Florian CAFIERO

Ancien élève de l'Ecole Normale Supérieure Paris-Saclay et diplômé de l'Ecole nationale des chartes, Florian Cafiero est ingénieur de recherche en mathématiques appliquées aux sciences humaines et sociales au CNRS. Il enseigne les méthodes quantitatives appliquées aux sciences humaines à l'Ecole nationale des chartes.

More Posts - Website

Follow Me:
TwitterLinkedIn

Philologie numérique et méthodes quantitatives

Ce court billet sert seulement à vous signaler que, dans le cadre du programme E-Philologie, les deux contributeurs principaux de ce carnet donneront un cours sur Philologie numérique et méthodes quantitatives, qui débute demain et se poursuivra, sur un rythme hebdomadaire, durant tous les lundis d’avril.

L’essentiel de ce cours sera tourné vers les méthodes de stylométrie, et les questions d’attribution, datation et localisation de textes anciens et modernes (en vrac, parmi les corpus sur lesquels nous expérimenterons: les œuvres de Corneille et Molière, les chansons de geste, les œuvres de Chrétien de Troyes, …). En prime, nous ferons peut-être aussi un peu de stemmatologie.

Vous pourrez trouver plus d’informations sur le carnet d’E-Philologie (https://ephilolog.hypotheses.org/).

Jean-Baptiste Camps

Diplômé de l'École nationale des chartes et docteur en études médiévales de l'Université Paris-Sorbonne (la Chanson d'Otinel…, dir. Dominique Boutet ), Jean-Baptiste Camps est responsable pédagogique du master «Humanités numériques» à l'École nationale des chartes (PSL). [CV et liste des publications, voir : http://paris-sorbonne.academia.edu/JeanBaptisteCamps]

More Posts - Website

Follow Me:
LinkedIn

« Médiévistique numérique »

Galerie

Pour les médiévistes de nos lecteurs, je me permets de relayer ici l’annonce d’une séance méthodologique consacrée à la « Médiévistique numérique » (co-coordonnée par votre serviteur) du séminaire de jeunes chercheurs, « Questes ». Que les jeunes chercheurs parmi vous n’hésitent pas à venir … Continuer la lecture

Leçon inaugurale de Bernard Chazelle au Collège de France – “L’algorithmique et les sciences”

Galerie

Aujourd’hui à 18 heures a lieu la leçon inaugurale de la chaire annuelle d’ “Informatique et sciences numériques”, tenue cette année par Bernard Chazelle, spécialiste des problèmes de complexité algorithmique. Son cours intitulé “L’algorithme et les sciences” s’attachera à montrer … Continuer la lecture

Voir et comprendre: de l’importance de la visualisation dans la compréhension des entités mathématiques

Galerie

Il n’a sans doute échappé à personne que, dans la plupart des analyses statistiques ou raisonnements mathématiques employés en sciences humaines, les chercheurs utilisaient des outils éminemment visuels. La tradition veut que nos articles fourmillent d’histogrammes, de courbes ou de … Continuer la lecture

Genealogical Variant Locations & Simplified Stemma: a Test Case

Galerie

Sources for the article, including the datasets used and functions that can reproduce the results, are available as part of the stemmatology package. It can be found on Github: https://github.com/Jean-Baptiste-Camps/stemmatology Be aware that this is not the original prototype, used … Continuer la lecture

Setting bounds in a homogeneous corpus

Galerie

We inaugurate here a new category, dedicated to sources and research documents. Mostly, we will publish in this category scripts, databases and documents related to articles we have published. The main purpose is, by making our sources available, to allow … Continuer la lecture

MASHS 2012 – Modèles et Apprentissage en Sciences Humaines et Sociales – Paris, 4 et 6 juin 2012

Galerie

L’appel à communication pour le cru 20121 du colloque Modèles et Apprentissage en Sciences Humaines et Sociales, qui se tiendra à Paris, à l’Université Paris 1 Panthéon-Sorbonne, les 4 et 5 Juin 2012, est paru. Vous le trouverez sur le … Continuer la lecture

Louis Havet, Cesare Segre, critique verbale et diasystème

Galerie

Dire clairement et fournir les outils pour penser ce que tout le monde croyait savoir est peut-être ce qui caractérise certaines avancées scientifiques. Dans deux articles publiés en 1976 et 1978, Cesare Segre définit ce qu’il nomme le « diasystème » des … Continuer la lecture