International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) Investigating a thematic approach to narrative generation Charlie Hargood, David E Millard, Mark J Weal LSL, Department of Electronics and Computer Science, University of Southampton, Southampton, England cah07r@ecs.soton.ac.uk,dem@ecs.soton.ac.uk,mjw@ecs.soton.ac.uk http://www.lsl.ecs.soton.ac.uk/ Abstract. Adaptive hypermedia aims to create a tailored experience for users and with narrative generation this dynamic content can be in the form of engaging stories. Narrative generation systems range from the automatic generation of bespoke stories to the representation of existing information as narrative. However narrative generation systems often produce bland and unvaried stories. In this paper we propose that the inclusion of themes will enrich the resulting narrative and explore how a prototype thematic system might be integrated with existing methods of narrative generation. This investigation reveals that integration at the generation of story elements is important to avoid constraints on desired themes, that the detailed characters fundamental to character centric narrative generation make integration difficult, and that integration must be done carefully to avoid damaging the resulting narrative. Key words: Adaptive hypermedia, narrative, narrative generation, the- matics 1 Introduction The presentation of relevant media in an engaging fashion to users is a difficult challenge, a user constructing a presentation of information or media from a personal collection can often have difficulty finding items relevant to each other and to the task at hand as well as presenting them in a flowing an engaging manner. Adaptive Hypermedia systems create a dynamic experience for users by adapting content and navigational choices. Their goal is often to create a high quality experience that is tailored to the user’s needs and requirements, and to avoid problems of information overload [5]. Narrative systems are a particular type of adaptive hypermedia application that attempt to generate content within a narrative or story framework. However, limitations with narrative generation methods can compromise the quality of the resulting experience, with stories that amount to a list of actions of characters who coldly state their motivations and pursue them directly in steps without any elaboration or subtlety. Narratives, or stories, are a prevalent representation of human experience that can engage and entertain. Work in the field of narrative generation presents 49 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) a potentially powerful solution to the problem of generating engaging and rele- vant information dynamically. Narrative generation seeks to automatically create bespoke narratives for a variety of uses, either generating requested narratives from scratch or by representing existing information as a narrative. Existing narrative generation systems while often successfully generating short narrative can find their results bland or unvaried depending on the limita- tions of their approach. We suggest a thematic approach to narrative generation where the addition of themes will enrich generated narratives making them closer to human authored narratives with a thematic objectivity beyond the base com- munication of the information present within the narrative. A thematic model has been developed [9] based on the work on thematics in narratology [17]. The model describes themes within a narrative being built of themes and motifs and how they are connoted and denoted from elements of the narrative itself. This was further developed into a prototype, the Thematic Model Builder (TMB) that could score narrative segments on their relevance to desired narratives, and an evaluation is being performed into the effectiveness of the system and model at representing and connoting themes. The focus of this paper is how such a thematic system could be integrated with existing narrative generation approaches in order to enrich the resulting narratives. We review existing approaches to narrative discourse generation and explore at what level a thematic system should be involved with narrative gen- eration, what approaches it best compliments, and what benefits are likely to emerge from an integration. 2 Background 2.1 Narratology Narratology is the study of narrative within literature and as such is primarily focused on the analysis of narrative. However it does provide a useful insight into how stories are constructed. Structuralism is an area of narratology concerned with deconstructing nar- ratives to identify the components from which a story is built and the structures that they build within a story. Because of the tangible nature of structuralism its ideas are very useful for narrative generation as its clear definition of structures and elements give an insight into what narrative generation systems should be generating. Most structuralists assert that a narrative is composed of an au- thored sequence of human experiences [13], and as such may be deconstructed into two important components; story, and discourse [4]. The story (or fabula) is a collection of all the information to be communicated and the discourse (or sjuzhet) represents the exposed parts of the story that are told and how they are presented (shown in Figure 1). The story element is the sum of all experiences and elements that make up the narrative. The discourse represents what parts of the story are exposed in the narrative (the story selection) and how it is told (the story presentation). 50 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) Fig. 1. A narrative can be deconstructed into story and discourse Discourse is a complicated process concerning many different decisions in- cluding how the story is presented, what medium is used, the style, the genre, and the themes of the narrative. Thematics approaches themes with a structural- ist method of deconstruction and identifies the narrative elements that commu- nicate themes. Tomashevsky identified the thematic elements of themes (broad ideas such as ‘politics’ or ‘drama’) and motifs (more atomic elements directly related to the narrative such as ‘the helpful beast’ or ‘the thespian’) [17]. He explains a struc- ture of themes being built out of sub-themes and motifs. A motif is the smallest atomic thematic element and refers to an element or device within the narrative which connotes in some way the theme. Themes may always be deconstructed into other themes or motifs whereas a motif may not be deconstructed. 2.2 Narrative Generation Narrative generation systems use a variety of different approaches and have a wide range of objectives. While many systems seek to generate full narratives for entertainment such as the virtual storyteller [16] and AConf [15] some systems use narrative generation to add additional meaning to information by represent- ing it as a narrative using narratological devices like sequencing, emphasis and omission such as in Topia [3] and adaptive hypermedia systems like AHA! [8]. As a process narrative generation can be broken down into three stages; story, plot, and presentation generation. Depending on the project in question these stages can be consolidated together or separated, (for example, in the virtual storyteller, presentation generation is broken down in narration and presenta- tion [16]). The majority of narrative generation projects deal with the creation of the narrative elements (story generation); resolution of the sequence of events that comprise the narrative and selection of narrative elements to be exposed and building of relationships between these elements (plot generation); and pre- sentation of the narrative through a chosen medium (presentation generation). Figure 2 illustrates this process. According to Riedl and Young [15] narrative systems take either a character or author centric approach depending on whether the system seeks to model the characters within the story, the authorial process itself, or whether the system 51 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) is a compromise of both approaches. [15] also identifies a third approach in the form of story centric approaches these are however less common and due to their more linguistic focus are less relevant to this research. Fig. 2. Narrative generation can be broken down into three stages Character Centric Character centric narrative generation revolves around the perspective of modeling the behavior and goals of the characters of a story. With the characters successfully simulated they are released to pursue their goals and their actions are exposed, the idea being that stories are everywhere and an engaging narrative will naturally emerge from the actions of a set of well-motivated characters. Character centric narrative generation systems often use agent technology to suitably simulate the characters and their behaviors with a purpose built agent taking the part of each character such as in work by Cavazza [7] and in the Facade system [12] (Facade is not entirely character centric, but its approach is very similar). Sometimes the intelligence is much more simplistic and a reasoning system will handle the goals and behavior of all characters, such as in TaleSpin [14]. However, these systems lack the power to generate varied narratives and although short simple stories are generated the lack of in-depth modeling of individual characters behavior removes personalized variety from their actions. Automatic generation of story elements is rare in character centric narra- tive generation. This is because elegantly written characters with sophisticated behavior are key to narratives being successfully emergent from the generated result and at present the only way to ensure this is to build the characters by hand. Some story elements are generated by using character archetypes with cliche behavior such as with the supporting characters in work by Cavazza [7] but it is rare to find this for key characters. Plot generation in character centric generation is therefore a direct result of the characters behavior as dictated by the agents playing them or the intelligence modeling all of the characters. The actions they take to achieve their goals builds the relationships between story elements and the sequence of events that makes a plot. Presentation generation is not specifically tied to the character centric approach but the focus on entities and modeling their actions make character centric approaches ideal for presentation in game engines (for example AConf used the UT engine through the mimesis project [18]). Although the presentation of character centric systems still sometimes uses text as a medium of choice either 52 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) using sentence templates such as in talespin [14] or generated text using natural language processing. The main weakness of character centric narrative generation is its reliance on an engaging narrative successfully emerging from the exposition of the characters actions. Often these systems generate bland stories that merely report on a series of uninteresting actions. These stories are thus often sensible and varied but lack narrative richness or interesting plot. Author Centric Author Centric narrative generation seeks to model the au- thorial process itself rather then the content of the narrative. The systems seek to model the process by creating rule based systems or narrative grammars that use well defined structures that are typical of the desired genre of narrative in order to generate stories. Author centric narrative generation also lends itself better to the representa- tion of existing knowledge as narrative as its story elements are not necessarily the narrative devices such as characters and objects but the devices the author needs to construct a story. Systems such as ArtEquAKT [2] create narratives out of a variety of resources and media from the internet and for this project story generation is the compilation of these resources. The same could be said for narrative influenced hypertext systems such as Topia [3]. Some systems do model the contents of the narrative to be generated as part of story generation but remain author centric. Universe [11] builds stories around a set of author goals and constructs a structure for a story to satisfy these but does so using the actions of characters modeled from cliche archetypes and a finite set of actions. In other author centric systems the story structure is not explicitly generated, but emerges from the selection of a predefined set of story elements, such as in Card Shark [6]. Plot generation in these systems is a case of applying the rules of the sys- tem for the desired genre, utilizing the grammar with the available resources, or filling a story template with appropriate resources. Presentation for author centric systems is often text based, either using templates such as Universe[11] or Artequakt [2] or simply exposing the elements in sequence such as in Card Shark [6]. Author centric systems tend to be highly specialized for one particular type of narrative, making them inflexible and also often not with a view to generic narrative generation. The stories are seldom varied as they all follow a similar authoring process with the same rules and/or grammars and as such can generate engaging but not often varied narratives. Compromise Approaches Many narrative generation systems often seek a compromise between these two approaches in order to counteract the weakness of using one approach or another. Some systems such as Facade[12] and Uni- verse[11] will only make slight compromises, such as the ideal story drama curve approach in Facade or the choice to model characters in Universe, but others make much larger steps towards marrying the two approached. 53 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) The virtual storyteller [16] at first seems to be a character centric approach that uses agents to model the behavior of its characters, the difference arises with the addition of an extra director agent. The director agent has a set of rules about what makes an engaging story, much like an author centric approach, and uses these rules to influence the narrative by vetting character actions, influencing them by giving them new goals, and creating story events to channel the emergent narrative into being more engaging. AConf[15] models each ‘actor’ as an expert system seeking to achieve its goals, giving it characteristics of a character centric approach, but it is fundamentally more author centric as its process of plot generation centers around the structure of the narrative building it as a network of events using story planners. The presentation generation for these systems also vary. In the virtual story- teller [16] the director agent directly communicates with a narrator and presenter to generate text using sentence templates whereas AConf [15] uses its character’s modeling and plot plans to interact with a system called mimesis [18] which uses the UT game engine to present the narratives. These systems experienced mixed success with both reporting the generation of successful narratives. However both suffered from similar problems to charac- ter centric approaches, while the addition of measures to ensure the narratives structure is engaging does have a positive effect the engaging narrative can at times still fail to emerge from the result and the systems can be reliant of sto- ries that are heavily predefined at the request stage rather then being entirely generated. 3 A Thematic Approach 3.1 The Thematic Model Using a thematic model [9] based on Tomashevsky’s work to describe how themes are constructed within a narrative we propose a thematic underpinning to nar- rative generation. The basis of the model (as illustrated in Figure 3) is built of natoms (narrative atoms) which contain features that denote motifs which in turn connote themes. For example, we might view a digital photo as a natom, and the tags on that photo as the features that denote a particular motif. Thus a photo tagged with ‘daffodil’ could denote the motif of ‘flower’, which connotes the theme of ‘Spring’. Themes can themselves build up into new themes, for example the theme of ‘Christmas’ can be used to connote the theme of ‘Winter’. 3.2 The TMB To facilitate an evaluation of the effectiveness of the model a prototype was built that could use an instance of the model to select images from a group of Flickr 1 images based on their ability to connote a desired theme. The prototype went under the working name of the Thematic Model Builder (TMB). 1 http://www.flickr.com 54 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) Fig. 3. The Thematic Model As an original instance of the model four themes were modeled (Winter, Spring, celebration, family) along with all sub themes and motifs of these themes, XML was used to build this instance. Defining an instance of the model for par- ticular themes is a complex and subjective process. We explored a systematic method for building themes based on semiotics [9]. Initially we identify what con- notes the desired theme, these connotative signs make up the themes sub themes and motifs. However, these signs become sub-themes only if when expanded all of their connotative signs in turn connote the original theme, otherwise they are a seperate (if associated) theme. Connotative signs anchored to a specific element within the narrative become motifs which have their features defined by likely tags that denote the element. The prototype was written in java with a simple JSP front end and Flickr was used as a source of natoms. As a folksonomy its items have rich semantic annotations in metadata [1] as opposed to the automatically generated metadata present in some other media collections. This makes the features in each image apparent and it also has a large freely available body of resources. The library of images (the fabula) was generated by making a keyword search of Flickr on the desired subject and storing the top n images (where n is the desired size). The system then followed an algorithm of measuring the thematic quality of each natom in the fabula. It returns the natoms with the highest scores according to two metrics: – Component coverage: the proportion of high-level sub-themes or motifs that a natom has features for - this is useful for measuring how strongly a natom 55 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) matches the desired theme. (for example, winter expands several high-level sub-theme and motifs including christmas, snow and cold. A natom matching just one of these has less coverage than one that matches many) – Thematic coverage: the proportion of desired themes that a natom has fea- tures for - this is useful for searches with multiple themes The TMB prototype allows us to compare the effectiveness of selecting photos according to their theme with the process of selecting photos based directly on their tags. A pilot evaluation of the prototype has been completed in [10], early results are promising and show the TMB successfully compiling collections that have been evaluated as better connoting the desired themes, and performing better in a narrative context then standard keyword selection. 4 Integration Referring back to the division of narrative generation illustrated in figure 2, we can explore the possibility of a thematic systems involvement at different levels of narrative generation. Themes are intangible concepts, a subtext rather then a core focus of the narrative, and for this reason it seems at first that narrative generation would be benefit from thematic involvement at the presentation level. Here themes could be connoted by emphasis given through the presentation to the features within the narrative that denote motifs which in turn connote the desired themes. At this level a thematic subtext would become present through elaboration on the presentation of the plot. However this is a process that could potentially fail if there were no relevant features present in the narrative that could be elaborated upon to help connote the desired theme, the system might find that at the presentation level a thematic system might only be able to offer from a subset of themes. At the story level of narrative generation a thematic systems involvement would be in some ways the opposite of its involvement at a presentation level. Instead of offering elaboration on existing narrative features at the story level a thematic system would generate additional narrative elements based on a shop- ping list of required motifs for the desired themes. This way themes would be- come apparent through the presence of certain story elements that connoted the desired themes. This could potentially fail however if the systems plot genera- tion did not make use of the thematic story elements or they were not properly exposed possibly leading to absence of key motifs. Also, such an approach could damage the generated narrative more then help it potentially flooding the system with elements irrelevant to the plot. For some systems as well story generation integration is not always an option, at least on a fully autonomous level, with many systems generating plot out of pre written and defined story elements. These semi automatic approaches to story generation require a very different approach perhaps with thematic guidance on the creation of these elements as supposed to influencing the automatic generation process in others. At the plot generation level thematics could play a role in the story selection of narrative elements as well as the way relationships build. The first part of this 56 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) would be similar to how the TMB prototype builds photo montages in that a list of desired motifs would be compiled and this would be used to thematicly score potential story elements and as such influence their selection and inclusion in the plot. Also, the relationships between story elements and actions of elements could in turn be factored in as features that denote motifs, as such potential actions at the plot generation of the story could be thematicly scored influencing what occurs. For example a story in which violence is a desired theme might see the protagonist kill the antagonist rather then banish or imprison them. However, like inclusion at the story level it is possible that heavy thematic involvement could damage the plot itself, making its involvement a dangerous balancing act, potentially forcing plot actions that damage the quality of the narrative. Fur- thermore like involvement at the presentation level, a lack of complete control over the story elements could potentially restrict available themes. On the question of which approach to take character centric approaches are perhaps the most different from the current implementation using the thematic model. Rather then the natoms of narrative segments that our model describes, character centric approaches start by simulating the content of the narrative itself, modeling characters, locations, entities, and events. However, through the process of plot and presentation, character centric approaches still go on to gener- ate natoms that contain features and by extension denote motifs. An integration would have to seek to ensure that certain features were planted in order for the themes to become apparent in the finished narrative. To do this involvement at the story level seems obvious as this is where the elements present within the narrative are generated. However, as a more semi automatic approach with predefined elements is more common then automatic generation at this level in character centric approaches it could be difficult to integrate a thematic ap- proach with the prewritten characters. At the plot and presentation levels an integration seems more possible, potential character actions and story events can be thematicly scored to influence actions taken to be conducive with de- sired themes and then presented in a way that emphasises the relevant thematic content. Character centric generations frequent use of game engines means that integration at the presentation level may be easier where knowledge of the enti- ties present in a particular scene is much more exact then in natural language. However as already discussed a reliance on integration at these levels potentially limits the available themes. Author centric approaches are more similar in process to the current imple- mentation of the thematic approach in that they’re heavily based on structures and largely concerned with the authoring process rather then modeling the con- tent of the narrative. The story generation process for some is about composing a pool from large collections of potential natoms, often from the Web, based on their relevance to required parts of the narrative structure. This is very similar to the way the TMB currently puts together selections for montage, and it is easy to see that with author centric projects that work this way thematic in- tegration would be a relatively simple process of scoring potential segments to generate. At the plot level, integration could be a similar process to the inte- 57 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) gration that would be used with character centric approaches, in that elements selected for exposure could be chosen on their thematic qualities rather then only narrative ones. However, for rule based systems of plot generation thematic rules would need to be written for the system. The feasibility of this would need to be added on a system by system basis. At a presentation level natural lan- guage generation poses difficulties for thematic integration as a full lexicon for desired features would need to be developed and integrated with the system. Forcing it to uses a small subset of words might make the language clumsy and its important to remember that the thematic model was created with the theory of structuring a narrative in mind where as the structure of individual pieces of language is very different. However, for those systems that use templating or selected pre authored text presentation, using thematics becomes more feasible where narrative techniques such as emphasis (spatially or visually) can be used to highlight relevant segments to help connote a theme. The possibilities apparent from this investigation are summarised in the ta- ble in figure 4. Decisions and selections made in generation may be influenced thematically by making the objective of the decision thematic as well as for plot objectives. Further thematic integration can be achieved through emphasis at the presentation or plot levels and other presentation choices such as style may have an influence that could be worked in favor of desired themes. 5 Future Work and Conclusion In this paper we describe an investigation into the potential challenges of inte- grating a thematic system with narrative generation. It is possible that a the- matic approach may improve the quality of narrative generation by enriching the resulting narratives which, could give adapted hypertexts tailored to the user and of a high quality. However, the question of integration between nar- rative systems and thematics is a complex one. At what point in the process of generation should there be thematic influence and what style of approach or compromise makes the prospect of a thematic narrative generation system most feasible? Narrative generation is a rich and varied field with a wide variety of ap- proaches. This variety is maintained in modern work and testament to the fact that no single perspective is a perfect solution to the problem, with this compro- mise approaches are becoming more popular as systems aim to find a successful middle ground. The complexity of the problem also means there are multiple stages of a system that it being integrated could exert an influence and effect the resulting narrative in different ways, all of which pose different constraints. It seems that a combination of issues make integrating thematics with charac- ter centric narrative generation difficult. As the quality of such systems is reliant on rich and complex characters, they are often authored by hand which makes influencing the stories fundamental elements in an automatic way difficult, at the same time, abandoning thematic involvement at this level instigates constraints on the available themes to be used at later levels. These constraints mean that 58 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) Fig. 4. Summary of potential integrations of a thematic system with narrative gener- ation thematic involvement at the story level (the initial generation of elements) is important to assure a wide variety of available themes. However, in order to assure they are exposed correctly involvement at either the plot or presentation level would be necessary as well. Similarities between parts of plot generation for both approaches and existing implementations of the thematic model make plot generation the easier option. The constraints surrounding thematic involvement at the initial story level however do not necessarily rule it out as a possibility for integration as compromise approaches may allow for thematic elements to be introduced to a story using a director agent along side complex characters. With an initial exploration of the issues complete, the future of this work is experimentation with integrating thematics and narrative generation. There are still also many remaining questions surrounding this process such as how the thematic scoring would be balanced in an effective way so as to include themes without spoiling a narrative and also how the effectiveness of a resulting system could be evaluated. 59 International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09) References 1. H. Al-Khalifa and H. Davis. Folksonomies versus automatic keyword extraction: An empirical study. IADIS International Journal On Computer Science And In- formation Systems (IJCSIS), 1:132–143, 2006. 2. H. Alani, S. Kim, D. Millard, M. Weal, W. Hall, P. Lewis, and N. Shadbolt. Au- tomatic ontology-based knowledge extraction and tailored biography generation from the web. IEEE Intelligent Systems, 18:14–21, 2003. 3. M. Alberink, L. Rutledge, and M. Veenstra. Sequence and emphasis in automated domain-independent discourse generation. In Information systems, pages 1–10, 2003. 4. R. Barthes and L. Duisit. An introduction to the structural analysis of narrative. New Literary History, 6:237–272, 1975. 5. H. Berghel. Cyberspace 2000: dealing with information overload. Commun. ACM, 40(2):19–24, 1997. 6. M. Bernstein. Card shark and thespis: exotic tools for hypertext narrative. In Proceedings of the twelfth ACM conference on Hypertext and Hypermedia, 2001. 7. M. Cavazza, F. Charles, and S. J. Mead. Agents interaction in virtual storytelling. In Intelligent Virtual Agents, Springer Lecture Notes in Artificial Intelligence 2190, pages 156–170. Springer-Verlag, 2001. 8. P. DeBra, A. Aerts, B. Berden, B. de Lange, B. Rousseau, T. Santic, D. Smits, and N. Stash. Aha! the adaptive hypermedia architecture. In Proceedings of the fourteenth ACM conference on Hypertext and hypermedia, pages 81–84, 2003. 9. C. Hargood, D. Millard, and M. Weal. A thematic approach to emerging narrative structure. In Web Science at Hypertext08, 2008. 10. C. Hargood, D. Millard, and M. Weal. Using a thematic model to enrich photo montages. In Proceedings of Hypertext 09, 2009. 11. M. Lebowitz. Planning stories. In Program of the Ninth Annual Conference of the Cognitive Science Society, volume 9, pages 234–241, Seattle, Washington, 1987. Cognitive Science Scoiety Conference. 12. M. Mateas and A. Stern. Faade: An experiment in building a fully-realized inter- active drama. In Game Developers Conference, 2003. 13. M. McQuillan. The Narrative Reader. Routledge, London, 2000. 14. J. R. Meehan. Tale-spin, an interactive program that writes stories. In In Proceed- ings of the Fifth International Joint Conference on Artificial Intelligence, pages 91–98, 1977. 15. M. O. Riedl and R. M. Young. Character-focused narrative generation for execu- tion in virtual worlds. In Proceedings of the International Conference on Virtual Storytelling, pages 47–56, 2003. 16. M. Theune, S. Faas, A. Nijholt, and D. Heylen. The virtual storyteller: Story creation by intelligent agents. In TIDSE 2003: Technologies for Interactive Digital Storytelling and Entertainment, 2003. 17. B. Tomashevsky. Russian Formalist Criticism: Four Essays, chapter Thematics, pages 66–68. University of Nebraska Press, 1965. 18. R. Young. Story and discourse: A bipartite model of narrative generation in virtual worlds. Virtual Reality, 2003. 60