CS 224N Final Project Report Ryan Thompson "Mixing Deterministic and Probabilistic Models for Simple Story Generation"The Problem Creativity has never been a strong point for computers. Statistical Natural Language Generation is a difficult topic, since context and meaning are carried over for more than just 3 words ahead or 3 words behind. In highly deterministic settings where the structure of sentences can be crafted by humans ahead of time, such as in question answering, this is a simpler problem. But when discussing the problem of generating text in a freer setting, the old adage about monkeys and typewriters comes to mind. In educational circles, with some slight crossover into natural language processing, story grammars have been debated and explored in the interest of best helping young children learn to read. Children recognize a certain grammar and set of story elements, which has led to discussion about how to write educational stories in a way that helps children learning to read, rather than hindering them. There are some commercial story generation tools that have been criticized in academic papers for not adequately providing this story grammar framework. For my project, I set out to combine this story grammar and deterministic structure with the large statistical NLP base of knowledge in order to probabilistically generate sentences within the given framework. In order to achieve this, I used a corpus of 450+ fairy tales from the Andrew Lang fairy tales collection, which provided a hefty 1.45 million words with which to develop a language model, perform parts-of-speech tagging, and generate my own pseudo-fairytales. The Model In 1996, Anderson and Evans developed a canonical story grammar, synthesizing the work of several research groups from the earlier decades. In its simplest sense, a story was: Setting -> Beginning Event -> Internal Reaction -> Attempt -> Ending Element Definition Setting Introduction of the main character and description of the time, location, and/or social context of the story. Beginning Event A cause which initiates a reaction or response of the main character.Internal Reaction An emotional response by the character which leads to the creation of a goal. Attempt An action of the character to achieve the goal. Ending Attainment or nonattainment of the goal by the character and/or the character’s reaction to the outcome and/or a moral. In this project, I broke this grammar sequence into several distinct parts: Characters, Places, Actions, Emotions, Goals, and Outcomes. They are pretty self-explanatory, although they interact in certain specific ways: an Action generally has a Character as the subject or object of its verb, and it may occur at a Place. Similarly, a Goal consists of a Character and an Action, Characters have Descriptions and Relationships, etc. Grammar: Story -> Setting BeginningEvent Reaction Attempt Ending Setting -> Place Characters | Characters Characters -> Character Characters | Character Place -> Name Description Description -> Adjective | Adjective Description Character -> Name Description Interactions | Name Description Interactions Place Interactions -> Interaction Interactions | e Interaction -> Character Relationship Beginning Event -> Action Action -> Subject Verb Object Place | Subject Verb Object Subject -> Character | noun | e Object -> Character | noun | e Reaction -> Emotion Goal Emotion -> Character Feeling Goal -> Character Verb Object Attempt -> Action Attempt | Action Ending -> Outcome Reaction Outcome -> positive | negative Implementation When implementing this story generation project, I made extensive use of the RASP tool tolexicalize, parse, and tag parts of the fairytale corpus. While I was unable to tag the entire corpora in CLAWS-7 POS tags due to the huge processing time and propensity to get booted from corn machines while running, I managed to get more than 12 MB of data from RASP. Using the CLAWS-7 tags and grammar relations on the data from RASP, I was able to generate Counters of words and their parts of speech, as well as CounterMaps of noun-adj pairs, verb-subject pairs, etc. In addition, I trained a Trigram language model on the entire fairytale corpus – since we are only concerned with generation, instead of testing unseen data, no smoothing is needed, just measured counts. In addition to the traditional forward-trigram model, I also kept track of the word just before the current word, as well as the bigram before the current word, which is necessary for the most difficult part of generation – linking words in a way that results in coherent English phrases. Sentences were generated basically according to the grammar above, with a rigid deterministic structure in place while constructing all sentences except for Actions and Goals. This mainly consisted of a limited set of words, phrases, transitions, etc chosen probabilistically and mixed in with traits like Character names and Place descriptions. For example, for an Emotion, the structure is: It made CHARACTER.NAME feel DESCRIPTOR FEELING. Descriptor is probabilistically selected from all words tagged as “RG” in the RASP output, FEELING is one of 3 positive or 3 negative emotions, and the Character’s name is the name of the Character the emotion is being generator for. Without any special work for Actions or Goals, a story at this point is not very probabilistic at all – we have a rigid structure, choose words from a limited vocabulary of, in most cases, preselected words, and everything is fairly repetitive. There is a lot of work that went into developing the framework, but it is not actually very interesting – the same goes for using RASP and developing the corpus. What really adds creativity to the story generator is the diversity in Actions that results from breaking out of the Subject Verb Object mold and linking up words in ways that still make sense. A Goal with verb=engage and object=affection can generate this: “engage himself to the giant s affection”, which strikes the fancy and adds a more interesting element to the story.I ended up using the same linkWords method for any set of two words, but almost exclusively for verbs. The general premise behind the method is that it takes two words and uses the trigram model to work inwards to find a match in a part of speech. However, instead of focusing on either the most likely part of speech or a random one, it creates a set and examines all parts