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
... stitched it and it on her it brings a parting and the last plumpudding too split in 2 halves see it ...
... him off me just like a business his omission then Ill go out Ill have him eying up at the ceiling where ...
... a Deceiver then he wrote me that letter with all those words in it how could he have the face to any woman ...
... other good chemises for one thing and but I dont know what kind of drawers he likes none at all I think ...
... a Flower of the mountain yes when I put the rose in my hair like the Andalusian girls used or shall ...
... itself do than the bulls and the pier and the trottingmatches and Ronda with my God help the men with...
... have been mad especially Simon Dedalus son his father such a criticiser with his glasses up with his ...
... old beggar at the door for a crust with his long story might be a tramp and put his foot in the way ...
... of the world and back its the least they might get a squeeze or two at a woman while they can going ...
... were so round and white for them always I wished I was one myself for a change just to try with that ...
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.