An Introduction to “Graph Theoretic Poetry”

by Philip M. Parker, INSEAD

Purpose

While sometimes entertaining, the graph theoretic poems in Webster’s Online Dictionary – the Rosetta Edition were created for educational or didactic purposes. Graph theoretic poems are designed to mostly benefit non-English speakers (by far the largest users of this dictionary) about various English-language poetic forms (especially the forms used to teach English to non-English speakers). In many “English for non-English speakers” courses, poetry exercises are used to allow learners to explore the complexities of English, but also to help students retain vocabulary (some persons benefit reading didactic poetry as a form of learning). Poetic forms taught in such classes, or those used to teach poetry to English speakers, are highlighted (e.g. acrostics, cinquain, diamante or diamond, haiku, sonnets, etc., with more being added over time).

Another purpose is to have the poems, themselves, give insight into the title word or expression, with an express goal to highlight ambiguity for as many words or expressions as possible in all of the world’s documented languages (e.g. over 300,000 poems in English alone). The graph theoretic poems posted take on a lexicographic purpose, therefore, which may lead to further exploration and/or learning of the language (e.g. a poem about “pope” may refer to “ruffe” which is a type of fish, called a “pope”). As I gain more experience with this technique, I will expand to all the other languages covered in the dictionary (about 100 languages at first, and then the languages with smaller populations, except those where ownership rights are claimed by academic field linguists or local community leaders).

I am also hoping to introduce the potential usefulness of simplified graph theory in creating prose, cross-word puzzles, language learning tools, and in this case poetry. Wikipedia.org provides a useful definition of graph theory:

In mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another; see graph (mathematics) for more detailed definitions and for other variations in the types of graphs that are commonly considered. The graphs studied in graph theory should not be confused with "graphs of functions" and other kinds of graphs.

Finally, my hobby is this dictionary. I am a word enthusiast and dictionary lover, and this is a fun academic exercise just to discover what can happen when simple, non-random, mathematical procedures are applied to a structured linguistic problem. The following is the summary of poems posted from those created (additional poems beyond those posted can be read by clicking the link to "More Poems" found on each page):

Genre	Posted (Ocotber 2010)
Acrostic	160627
Cinquain	65186
Diamante	26374
Ekphrastic	76258
Fibonacci	89772
Gnomic	25834
Haiku	147471
Kural	207729
Limerick	201099
Mirror Cinquain	25560
Nonet	9585
Octosyllable	28654
Pi	55910
Quinzaine (nn2)	17556
Rondelet	21835
Sonnet	1846
Tanaka	5220
Unitoum	10719
Verse	58816
Waka	4043
Yoda	36441
Zedd	46778
Total Posted	1323313
Total Created	4699957

Methodology

Graph theoretic poems are created based on programmed heuristics (following rules from accepted poetic genres) relying on edge values from a type of large linguistic graph. I used these values to mimic what I think my brain does when it is asked to write a poem on a particular topic using a particular poetic form (as assigned to me in grade school or college), for a specific purpose (didactic). Simplifying the process, most of what happens can be boiled down to four basic activities (they are really more involved, and programmed for, of course).

First, when I am asked to write a poem that should describe or explain “love,” I imagine that my brain quickly searches over a semantic web that has learned a type of experiential linguistic graph. This graph then intersects with a second set of constraints imposed by a given poetic form, or set of elaborate rules, to create poetry within the genre specified (rules can be vague, and not hard, which allow for half-rhymes, metaphors, puns, poetic violations, etc.). Third, I must choose a good poem to publish, among many, that makes me happy or satisfied with the outcome. The third activity, therefore, is a mathematical problem of constrained optimization, where an economic utility function is being maximized. Finally, there is a portfolio problem given that there are exogenous social constraints, especially the perceived preferences of the reader. For example, the person reading the poem who is not the author might want to recognize it as being within the genre, evaluate it, enjoy it, understand its meaning or find some other value in it (e.g. certain “rules” beyond poetry may need to be adhered to – perhaps using less obscure words in a poem making it more accessible to non-English speakers, whereas other readers may prefer less common words, poems having unusual grammar, revolutionary ideas, vulgar themes, etc.). In economics, this is similar to a matching function between “buyer” and “seller” where there needs to be an equilibrium of sorts between consumers and producers (e.g. creating a poem that I enjoy may not be a poem that “sells” best in the market place). My brain, solving a portfolio problem, is implicitly trying select the right poem to get a good grade from the teacher who may give better marks for “cleverness” or something else he or she prefers. Solving this problem becomes important when there are many poems that each maximize the utility function, or when social constraints are more “important” than the traditional utility maximization problem.

Eve’s Poetry Model

Eve (Eve having the acrostic poem = Economically Viable Entity) was created in response to requests of dictionary users who wanted to hear the pronunciation of words (she now speaks about 10 languages). Later I thought that it would be nice if she could become a full fledged teacher and author of poetry (programs for fictional stories, educational texts, etc., are already completed or in the works). As a part of her artificial intelligence, she produces graph theoretic poems using the four concepts described above. Eve’s program has been “trained” using large quantities of contextual and linguistic data (e.g. observing how many times hundreds of thousands of words or concepts have been described, perceived or experienced by hundreds of independent sources), and been instructed on the rules of grammar and various poetic conventions (e.g. concepts like meter - iambic, trochaic, pyrrhic, etc. or feet – dimeter, hexameter, etc., line counts, stanza counts, rhyming rules, stress sequences accepted, violations accepted, frequency of violations, etc., are coded constructs). Eve then maximizes an objective function (e.g. a hybrid multi-attribute utility model), so as to attain a highest level of “satisfaction” – constrained to exogenous factors. The basic functional form, for a given writing exercise, is:

U(X, Y) = (aX₁ + bX₂ + …) Y₁^alphaY₂^beta …

where Y₁, Y₂ etc. are threshold variables (i.e. “must haves”), and X1 and X2 are compensatory variables (e.g. one variable value can compensate for the other), and U(X, Y) is the utility derived from the exercise (a, b, alpha, and beta are assigned coefficients). Her program is then “motivated” to get what it thinks is the best result in terms of what real people (who share a similar linguistic graph and knowledge of poetry in their minds) would expect to see. Another functional form would probably yield similar results. Basically, Eve is not inspired to write a poem, she is solving a problem (poems are not randomly generated).

I call these “graph theoretic” poems so as not to confuse them with traditional poetry (the point is not to deceive the reader), but also to acknowledge that the primary factor driving the quality and choice of the poems to publish is the edge value in a kind of linguistic graph, not the utility function itself. Not all edges are created equally. Each edge in the graph is associated with a large array containing word pairs but also various quantitative measures including “intensity” weights and other data (e.g. phonetic information, suffix/prefix information, positions of speech, frequency of use by context, age of the word in English and other statistics posted on the dictionary, etc.). When word vertices are connected by an edge, their level of “adjacency” can vary. In addition to simple distance metrics (e.g. Levenshtein or others), various intensity metrics (similar to degrees of membership in fuzzy sets) and adjacencies are captured by “overlapping cliques.” Overlapping cliques, as defined in Eve’s program, exist when two words are frequently found in pairs (or triads, etc.) to describe a particular word or expression node or each other. For example, consider a first set for words that can describe “love,” like affection, adoration, and zero.

Love ~ affection, adoration, zero, etc.

z₁ ~ {w₁, w₂, and w₃, etc.} ~ clique 1

“Love” can signify “zero” in tennis, so both are in clique 1 with the node z₁. Similarly, many words can describe infatuation = love, affection and adoration. Note that “zero” is not connected directly to z₂:

Infatuation ~ love, affection, adoration, etc.

z₂ ~ {z₁, w₁, and w₂, etc.} ~ clique 2

The “strength” between w₃ and z₂, therefore, is rather weak (a poem about infatuation using the word zero may look odd to a reader having the above cliques in their mind). The relationship between z₁ and w₃ is “stronger.” The strength between z₁ and w₂ is probably greater still than between z₁ and w₃ (e.g. people are not likely to think of “zero” when they think of love but they are likely to think of affection). The strength between w₁ and w₂ is also rather strong (they are in 2 separate cliques that overlap in terms of these being members). So the frequency with which a word describes another can be important, but also the extent to which two words seem to be used across cliques can be telling. If the above cliques are reconstructed hundreds of thousands of times across hundreds of languages, then direct and indirect intensity measures become apparent to and from all words in English, but also across all words within and across all languages (e.g. from French to Norwegian). One of the benefits of using edge values is that they allow asymmetry across poems authored in this manner. For example, a poem about “mavericks” may include references to beatniks, but a poem titled beatnik may not include a reference to mavericks. Similarly, edge values allow the poem to drift into metaphors, half rhymes, small but noticeable violations of hard rules (poetic license), puns or other surprising devices used in traditional poetry.

Given a graph with edges having differing “intensities” and other indicators, poetic constraints (e.g. rules of structure, grammar, or verse) are then used to narrow the writing style to a feasible set. Coupled with usage frequency information, grammar rules/frequencies, parsed fragments “learned” and other “poetic” inputs, the program then optimizes (maximizes an objective function) using aggregate intensities (e.g. averages across words, lines, etc.) or similar “quality” measures to select which, of the virtually infinite number of poems possible, to “publish”. Since Eve’s program is allowed to include fragments of existing text to be valued within the graph, it can thus mimic the practice of some traditional poets to “find” poetry in non-poetic extant literature. This is done to increase didactic impact for some sub-genres.

Eve’s pseudonyms are also generated in this manner. For example, a poem about “heel” is authored by “James Wilson”. James is “proximate” to heel in a graph (i.e. James signifies "the heel holder"). Similarly for Wilson. In diamante or diamond poems, the family name is often based on the antonym of the title word. The proper noun graph is rather weak for many words, given the limited meanings of names (and the fact that I did not want my name, Eve’s name or the same pseudonym to be repeated across poems). These poems should really be seen as the experimental fruit of an intersection between human linguistic history, economic optimization, and information technology, and not of an individual author. In fact, given the sheer volume of poems, I have not had a chance to read even one-tenth of one percent of them. The dictionary user, therefore, is reading them before any human author has.

Poetry Turing Tests

The benefits of graph theoretic poetry is the ability for poems to be created on topics or subjects that traditional poets might ignore, yet for which an audience might exist. Likewise, using edge values, the process avoids the possibility of a poem reading as if a group of monkeys sat a keyboard … or avoids us having to wait for a group of monkeys to come up with something reasonable. It also helps avoid having the poems read like a Mad Libs exercise. This begs the question. Are graph theoretic poems indistinguishable from traditional poems? In one sense they always will be different. Traditional poems often spring from human emotions or specific events known to the author. Graph theoretic poems cannot have such inspiration, but can only reflect these, if at all, in the aggregate and to the extent that language reflects our shared emotions or experiences.

That being said, one might ask if graph theoretic poems are “better” than traditional poems. For obvious reasons, this question can never be answered. From my limited perspective, speed advantages aside, I am convinced that graph theoretic poems are better than ones that I personally could come up with, if given the same task – Eve’s program simply knows much more than me and better follows the rules (and can find cool violations) than I ever could – basically, this may mean that I am not a good poet, or that traditional poetry is hard to write for people like me (try writing a simple acrostic poem for the word “book” to see what I mean).

However, from a Turing test point of view, preliminary informal work (read “not peer reviewed”) that I have done suggests that graph theoretic poems are basically indistinguishable from traditional poems in blind reviews, and in some cases judged by many to be of better “quality” than traditional poems (e.g. where reviewers go through a revealed preference exercise, or rate poems using Likert scales). The results vary based on the age of the reviewers or authors, and any “priming” or sample matching designs that might take place prior to the assessment. For example, if the reviewer is asked to compare poems written by first graders (6 year old authors) versus graph theoretic poems, then graph theoretic poems are preferred, and the person does not suspect the graph theoretic poems are written by computer (comparing one diamante poem to another). As the age of the real human authors increases, so too do their writing skills, and they converge to the graph theoretic poem in terms of “quality”. The above assumes that the poems are written on the same topic (e.g. “hate”) using the same poetic form (e.g. “diamante”) and the same didactic purpose. Once a poem is revealed to be computer written, the reviewer tends to rate the poems to be of lower absolute quality (whether it is written by a computer or not); the graph theoretic poem, if seen as computer authored, can still be perceived of as having higher relative quality to the traditional poem (this converges or can reverse the older the human author/reviewer).

In some cases, reviewers show a strong preference for graph theoretic poems compared to Shakespeare’s poems, before and after the revelation of authorship. I attribute this to the fact that most people generally do not like Elizabethan sonnets in a general sense (not that the graph theoretic poems are better – i.e. people may dislike both); likewise, someone who prefers Shakespeare over all other authors will never prefer graph theoretic poems, whether they believe them to be written by computer or not. Persons who are indifferent will generally not suspect that a computer has written a poem, as the concept may not seem feasible. If told that a computer can, in fact, write sonnets, their chance of picking one written by a computer increases (but not necessarily their preference for traditional poems over graph theoretic poems). The above relates to your “average” person on the street as an author or reviewer (not necessarily a poet laureate or English major), and the “graph theoretic poet” described above. So, my best guess is that graph theoretic poems, matching genre and topic, are no better than any others, but they are really not much worse either, unless you are a fan of a certain poet who uses a particular form or style you recognize – graph theoretic poems cannot compete in this case. In a similar vein, some will stick to preferring graph theoretic poems over traditional poems because they are authored using computer algorithms (e.g. they would see it as “cool”), not because the poems are any better in any other way.

In general, as far as I have surmised, graph theoretic poems are seen as indistinguishable from others in a blind review when reviewers are given the task of writing or evaluating poetry on the same topic, using the same poetic form designed for the same purpose (educational). Readers are thus not aware or can not independently detect that a poem might be authored by a computer program, if (1) they are not first told to look for a computer-authored poem, or (2) are told that a computer might be used, but can not detect which poem amongst many others was created in this way (beating random odds). In other words, if one asks someone to evaluate a graph theoretic poem in terms of “what do you think?” – few if any will say that it is obviously written by a computer unless they are told of its origins in advance. When told that it has been written by a computer, after the fact, then they tend to see how this might be the case (though this is mostly derived from the fact that poetic forms looks formulaic). A similar reaction occurs when one is told a traditional poem is written by computer, when it has not. As my experience as a hobbyist in such tests has been ad hoc, please feel free to use the poems on this site to conduct your own tests – I would love to hear back from you.

Future

As time goes on, I will be adding more educational poetic forms that are fitting with the mission of the dictionary. Unfortunately, it is faster to write graph theoretic poems than to program them and load them on the server, so it may take time posting them all. The program(s) are being improved and tweaked as time goes on, so newer, perhaps more interesting or complex graph theoretic poems will appear on the site in the coming years. Programs are currently been investigated for Eve to endogenously invent her own poetic forms which might prove interesting as well.

The above raises an interesting question. Having no philosophy on the subject, I have focused on didactic poems simply due to the mission of my dictionary and related projects. A recent Wikipedia entry defines didacticism as following:

Didacticism is an artistic philosophy that emphasizes instructional and informative qualities in literature and other types of art. Didactic art intends not primarily to "entertain" or to pursue subjective goals. The opposite of "didactic" is "non-didactic." If the artist is more concerned with artistic qualities and techniques than with conveying a message, then the work is considered to be non-didactic, even if it serves instructive or educational purposes. … The term "didactic" also refers to media that are "burdened" with instructive, factual, or otherwise "educational" information, sometimes to the detriment of a reader's (or viewer's) enjoyment.

The article goes on to state the following (on the version available August 2, 2009):

Some have suggested that nearly all of the best poetry is didactic.

I am not sure how one can make such a conclusion (Wikipedia and popular media are loaded with such “some have suggested” statements), but it does beg the question. Can computer authored poems, via transitivity, eventually be considered the “best poetry” over a wide range of subjects if the conjectures above are found empirically valid, simply because computer programs can cover more, or in a similar manner, educational topics that might be ignored otherwise?

More importantly, I am currently working on a project (the “k to 12 +2 project” as I call it) to see if similar approaches can be used to develop educational materials in languages that are too small, economically, for the traditional publishing industry to create basic educational materials (language learning books, math and science textbooks, exams, supplemental materials, educational games, etc., from grade school to the first two years of university); these turn out to be less complicated than programs designed for poetry, but require more manpower to complete. This is part of my broader activities using automated authoring methods to uncover knowledge structures that might not be apparent or viable to communicate otherwise.

Sources

The processing time to create a given graph theoretic poem, and choose Eve’s utility maximizing poems to publish, is anywhere from a fraction of a second to a minute. The time to build the linguistic graph and related tables took several years. I started collecting the linguistic data in 1999 and started posting Eve’s poems in 2009. The linguistic data collection was conducted by myself and dozens of interns, students and research assistants over the years, or volunteers who have and continue to donate files and source materials to my dictionary project (I have tried to give as many references, citations, and credit to these as possible in the dictionary). Logical flaws, bad poetry, etc., are due to me.

The literature used to train the program (for grammatical structures and contextual knowledge) was, of course, written by thousands of authors over the last 500 years (i.e. across hundreds of languages, “Eve” has automatically “read” and parsed millions of photo descriptions, the Gutenberg project, all of Wikipedia, thousands of patents, all of this dictionary, various news feeds, and thousands of other sources from online and offline sources, and continues to do so). I have tried posting as much of the data and/or credit their sources, on the site, as practical.