Louphole

Who Wrote It: James Joyce Or Markov Chains?
James Joyce - Photo (C) Centre Pompidou, MNAM-CCI, Dist. RMN-Grand Palais / image Centre Pompidou, MNAM-CCI. Andrey Markov
... Sinner Fein or a boy to the City Arms intelligence they were on the indifferent when a year as regular...
... send him with some of father also his face swelled out you have to guiiiide him want LI or stout or...
... the day we met Mrs Joe Gallaher at the trottingmatches and she pretended not to see us in her trap ...
... friend more than theyll all know at it up a body unless he wanted her dog in the cards this time with...
... pretty it got as dull as the devil after they went I was almost planning to run away mad out of it ...
... it I suppose thats what a woman is supposed to be there for or He wouldnt have made us the way He did ...
... a bottle of those engines have in a way for his son he said over selling the stink on the women rolling...
... and drew back its bad conscience ah horquilla disobliging old brogues itself or 4 weeks usual on the...
... Blooms private hotel he suggested go and ruin himself altogether the way his father did down in Ennis ...
... print to ah yes and the funeral in Grantham street and he does of me I ought to be married to make it...
James Joyce

I have never read any work by James Joyce. But his writing and textual experimentations are undeniably very interesting to me from the perspective of computer-generated text. It sometimes looks like Joyce played with literature in the way a computer program could. The ending of the novel Ulysses is a great example of such experimentations in which the author removes all signs of punctuation and leaves a whole monologue written as a single stream of words, giving the impression of a confused and messy account of events.

This quiz randomly displays excerpts from the end of Ulysses as well as fake computer-generated ones using Markov chains. The excerpts are about a hundred characters long and regenerated on refresh.

Markov Chains

So what are these Markov chains? They are a mathematical tool used here to generate an output that mimics a given sample. For the Markov chains algorithm to work, it first needs a sample as big as possible of the kind of material it will generate. The program chunks this initial input into small "items". For each item, it browses the sample and looks at which item comes right after. Taking the number of items into account, the program computes a probability, for each item, of being the one that follows a given item, that is a probability of consecutive items. This whole process creates a statistical model of the input, it assumes that the input is representative enough as a sample to give an idea of the general rules followed by the material. Once the statistics are computed, the generation algorithm starts with a random item from the list, and it picks the item that succeeds based on the statistical model of the current item and a randomly computed probability. Then it repeats the process with the chosen item, and so on and so forth.

Text generation

In my case, I used as initial input the same sample of the end of Ulysses that I used to extract real excerpts, which is a sample of 4391 words. The input being a text, the most reasonable course of action was to use words as items, but it could have been letters, blocks of x characters, or sentences (although not in this particular case). The algorithm is then called word-based and it mimics the way words succeed one another in the sample. To get more relevant results, I raised the order of the statistical model to 1 instead of 0 which means that the model computes the probabilities of groups of 2 words following a given one. If the order is too big, then entire blocks of the sample may be used in the generated text, which is not very interesting, but on the other hand if the order is too low, the possibilities are too diverse and the result often doesn't make grammatical sense.

The PHP code of the word-based Markov chains algorithm I used to generate the fake excerpts is available on my GitHub, a demo of a letter-based Markov chains algorithm is available here.

James Joyce

Je n'ai jamais rien lu de James Joyce. Mais son style et ses expérimentations textuelles sont pour sûrs très intéressants en regard de la génération de texte par ordinateur. Parfois, c'est comme s'il jouait avec la littérature à la manière que le ferait un programme. La fin de son roman Ulysse est un très bon exemple de ce genre d'expérimentations où il retire tous les signes de ponctuation et livre un monologue entier écrit comme un flot continu de mots, provoquant une grande impression de confusion et de désordre.

Ce quiz présente de manière aléatoire des extraits de la fin de Ulysse (en anglais) ainsi que des faux extraits générés par un programme à l'aide de chaînes de Markov. Les extraits font une centaine de caractères et sont générés de nouveau à chaque chargement.

Chaînes de Markov

Donc que sont ces fameuses chaînes de Markov ? Il s'agit d'un outil mathématique utilisé ici pour générer un résultat qui imite un échantillon donné. Pour qu'un algorithme de chaînes de Markov fonctionne, il faut tout d'abord un échantillon le plus grand possible du genre de résultat qui va être généré. Le programme découpe les données initialement saisies en petits "objets". Pour chaque objet, il parcourt l'échantillon et retient l'objet qui lui succède. En comptant ces derniers, le programme calcule une probabilité, pour chaque objet, d'être le successeur d'un objet donné, c'est-à-dire une probabilité que les objets soient consécutifs. Ce processus global créé un modèle statistique des données en entrée, cela suppose que l'échantillon est suffisamment représentatif pour donner une idée de la règle générale que suit le matériau. Une fois les statistiques calculées, l'algorithme de génération commence par choisir un objet au hasard dans la liste, puis il sélectionne l'objet qui lui succède à l'aide du modèle statistique de l'objet et d'une probabilité générée aléatoirement. Le processus est ensuite répété avec l'objet sélectionné, indéfiniment.

Génération de texte

Dans mon cas, j'ai pris comme entrée le même échantillon de la fin de Ulysse que j'utilise pour prélever de vrais extraits, c'est un échantillon de 4391 mots. Le matériau d'entrée étant un texte, le plus raisonnable était d'utiliser les mots comme objets, mais j'aurais pu prendre les lettres, des blocs de x caractères ou encore les phrases (certes pas dans ce cas particulier). L'algorithme est alors basé sur les mots et imite la manière que les mots ont de se succéder dans l'échantillon. Pour obtenir des résultats plus pertinents, j'ai augmenté l'ordre du modèle statistique à 1 au lieu de 0, ce qui veut dire que le modèle calcule les probabilités de groupes de 2 mots qui suivent un groupe donné. Si l'ordre est trop élevé, des blocs entiers de l'échantillon risquent de se retrouver dans le texte généré, ce qui n'est pas très intéressant, mais à l'opposé, si l'ordre est trop petit, les possibilités sont très diverses et le résultat n'a souvent pas de sens grammatical.

Le code PHP de l'algorithme avec chaînes de Markov basé sur les mots que j'ai utilisé pour générer les faux extraits est disponible sur mon GitHub, une démo d'un algorithme avec chaînes de Markov basé sur les lettres est disponible ici.