Computational models of narrative structure

introduction
A question of particular interest to the Computational Narrative community is the question of the notion ofstructural equivalence of stories (Löwe 2010, 2011). On the one hand, it is closely related to research in other areas such as the study of analogical reasoning in cognitive science and psychology; on the other hand, a solution to the question of when stories can count as structurally similar underlies a number of potential computational applications for narrative databases.
In our panel, the four speakers will discuss various foundational issues that have to be dealt with before a structural theory of narrative similarity can be developed. The majority of these issues have to do with the empirical validation of proposed formal representations; the aim is to develop (1) a methodology that allows to determine and investigate those aspects of narratives that are computationally and cognitively relevant for the comparison of stories and (2) a formal framework that allows to represent narratives with regard to these aspects and also allows to encode the necessary algorithm (formalization guidelines). The presentations will report on joint projects of the panelists in this field, and part of the purpose of the panel is to present the results of these projects to the Digital Humanities community.
These tasks are approached using the following empirical and computational methods: First, (quasi-)ex-perimental studies are used to determine the relevant dimensions and trainability of analysis systems (Fisseni, Bod below). Secondly, computational representation and simulation is used to evaluate representational formalisms, and will be experimentally evaluated in a final step (León, below).
theoretical background
The field of computational models of narrative goes back to the 1970s and has produced numerous computational representations of narrative structure (e.g. Lehnert 1981; Turner 1994; León 2010). Its roots lie in the structuralist school of narratology (Barthes, Genette, Greimas, Todorov, among others) that started with Vladimir Propp’s study of Russian folk tales (Propp 1928), and it was greatly successful with the methods of modern computational linguistics:
There is now a considerable body of work in artificial intelligence and multi-agent systems addressing the many research challenges raised by such applications, including modeling engaging virtual characters […] that have personality […], that act emotionally […], and that can interact with users using spoken natural language (Si, Marsella & Pynadath 2005: 21).
Recently, there has been an increased interest in developing theoretical foundations of what is called shallow story understanding in this community: high-level structural analysis of the narrative as opposed to understanding ‘deeply’, i.e., with background knowledge. The intersection of narratives and computation is also being considered in the field of Digital Humanities or the application of computer software to narrative analysis. In this context, we assume that theory of narrative structures is a prerogative to computational treatment of narratives. All work presented here is concerned with validating and extending existing theories empirically. Even though non-structural factors may influence judgment of stories, they should evidently be excluded in our formalization of structural similarity. Potentially, one will have to reconsider the notion of ‘structural core’ and its differentiation from ‘mere’ accidental features such as motifs or style (the latter is discussed by Crandell et al. 2009, presented at DH 2009).
Two central themes of the entire panel are the questions (1) Is there a structural core of narratives and can we formally approximate it? and (2) Are structural similarity judgments a ‘natural kind’ or rather a trained skill? The basis for discussing these issues will be prepared in this presentation and further developed in three following presentations.
narrative similarity and structural similarity
Löwe, Benedikt, University of Amsterdam, The Netherlands, b.loewe@uva.nl
This first presentation will introduce the notions and concepts that we shall deal with: the distinction between the narrative and its formalization (or annotation), various levels of granularity, and various dimensions of similarity. We shall discuss the human ability to identify a structural core of a narrative and discuss intersubjectively in what respects two narratives are structurally the same.
We discuss the question whether this structural core exists and how to approach it. In particular, we shall discuss a number of methodological issues that create obstacles when trying to determine this structural core(Löwe 2011; Fisseni & Löwe 2012).
empirically determining ‘optimal’ dimensions and granularity
Fisseni, Bernhard, University of Duisburg-Essen, Germany, bernhard.fisseni@uni-due.de
Dimensions that can be easily brought into focus by an adequate instruction are highly relevant for our implementations and can presumably also be annotated with high reliability and inter-annotator agreement by test subjects (see Bod, below). These dimensions may also arguably be considered important for the reception of narratives. As different dimensions can be relevant for different tasks, the setting presented to test subjects must be varied to trigger different granularities and (presumably) focus different dimensions. For example, taking the role of a magazine editor should focus different notions than considering movies in an informal setting.
Preliminary experiments (Block et al. submitted; Bod et al. 2012; Fisseni & Löwe 2012) show that naive test subjects do not have a clear preformed concept of story similarity that privileges the structural core of stories. Therefore, work will have to be done to determine how to focus structural aspect and control other, non-structural aspects.
a computational framework for narrative formalizations
León, Carlos, University of Hamburg, Germany, carlos.leon@uni-hamburg.de
Even with the most recent advances of Artificial Intelligence, completely automatic formalizations of narrative texts are still impossible, but it is well possible to develop and process formal representations of stories computationally. In this presentation, we shall focus on implementing a computational instantiation of the set of different formalizations. This instantiation will be used to formalize stories and check their structural similarity under human supervision. In order to do this, a mixed methodology will be applied: computational versions of the defined formal systems will be implemented in the form of several structured descriptions of the stories, along with information about their respective granularities. The dimensions that are modeled should be those that can be easily accessed (see Fisseni, above) and reliably annotated (see Bod, below).
A mixed human-computer process for acquisition of one of the candidate formalizations has been successfully tested by the author (León 2010; León & Gervás 2010); hence, a computational tool will assist human users during the formalization process, iteratively creating partial structures according to the defined granularity. It may also be interesting to use techniques from knowledge representation and natural language processing to formalize at least some guidelines and thus test their consistency and usability. While these guidelines may not unambiguously define how to formalize each story, they will be used to maximize the consensus among the formalizers (see Bod, below).
inter-annotator agreement for narrative annotations
Bod, Rens, University of Amsterdam, The Netherlands, L.W.M.Bod@uva.nl
A way to measure the quality of guidelines and formal representation derived by applying them is inter-annotator agreement, which is used to assess the quality of linguistic structural annotations such as treebanks (see e.g. Carletta et al. 1997; Marcu et al. 1999). We intend to apply inter-annotator agreement to the formal study of narratives (Bod et al., 2011, 2012).
As Propp’s formal analysis of Russian folktales (Propp 1928) has profoundly influenced Computational Narratology, we ran a pilot experiment in which external users are annotating several Russian folktales with a subset of Propp’s definitions, to establish the viability of the methodology (Bod et al. 2012). After a training process, test subjects were expected to have a basic knowledge about Propp’s formal system. In the main phase of the experiment, they were to apply their understanding of the formal system to other stories. The results indicate that Propp’s formal system is not easily taught (or learnt), and that this may have to do with the structural constraints of the system: Its functions and roles are so highly mutually dependent that variation is great.
Hence, similar experiments with more ‘modern’ and formal representations (such as those by León, above) are planned. These experiments will also profit from the preliminary studies (see Fisseni, above) which try to determine which dimensions can be triggered in test subjects and how to achieve this. Then it will be possible to measure agreement between test subjects (using standard statistics), which should provide an insight in the reliability of the guidelines and the viability of the formal representation.
references
Afanas’ev, A. N. (1973). Russian Fairy Tales. Translation by N. Guterman from the collections of A. Afanas’ev. Folkloristic commentary by R. Jakobson. New York: Pantheon.
Afanas’ev, A. N. (1985). Shabarsha.Translated by Kathleen Cook. In The Three Kingdoms. Russian Fairy Tales From A. Afanasiev’s Collection, illustrated by A. Kurkin. Moscow: Raduga Publisher.
Barzilay, R., and M. Elhadad (1997). Using Lexical Chains for Text Summarization. In I. Mani and M. Maybury(eds.), Intelligent Scalable Text Summarization. Proceedings of a Workshop sponsored by the ACL. Somerset, NJ: ACL, pp. 10-17.
Block, A., B. Fisseni, C. León, B. Löwe, and D. Sarikaya (submitted). Narrative summarization and its correspondence to Proppian functions.
Bod, R., B. Löwe, and S. Saraf (2011). How much do formal narrative annotations differ? A Proppian case study. In C. Ess and R. Hagengruber (eds.), The computational turn: Past, presents, futures?, Aarhus University, July 4–6, 2011. Münster: MV-Wissenschaft, pp. 242-245.
Bod, R., B. Fisseni, A. H. Kurji, and B. Löwe (2012). Objectivity and reproducibility of Proppian narrative annotations. To appear in the proceedings of the workshop on Computational Models of Narratives, Istanbul, 26-27 May 2012.
Brants, T. (2000). Inter-Annotator Agreement for a German Newspaper Corpus. In Proceedings Second International Conference on Language Resources and Evaluation LREC-2000.
Carletta, J. C., A. Isard, S. Isard, J. C. Kowtko, G. Doherty-Sneddon, and A. H. Anderson (1997). The reliability of a dialogue structure coding scheme. Computational Linguistics 23(1): 13-31.
Conroy, J. M., and D. P. O’Leary (2001). Text summarization via hidden Markov models. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’01. New York, NY: ACM, pp. 406-407.
Crandell, C., E. Gong, R. Kraus, T. Lieu, and J. Mason-Marshall (2009). Modulating Style (and Expectations): An Experiment with Narrative Voice in Faulkner’s The Sound and the Fury. Talk at Digital Humanities 2009, Maryland.
Dyer, M. G. (1983). In-depth understanding: A computer model of integrated processing for narrative comprehension. Artificial Intelligence Series. Cambridge MA: MIT Press.
Fisseni, B., and B. Löwe (2012). Which dimensions of narratives are relevant for human judgments of story equivalence? To appear in the proceedings of the workshop on Computational Models of Narratives, Istanbul, 26-27 May 2012.
Kupiec, J., J. Pedersen, and F. Chen (1995). A trainable document summarizer. In Proceedings of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, NY: ACM Press, pp. 68-73.
Lehnert, W. G. (1981). Plot units and narrative summarization. Cognitive Science 4: 293-331.
León, C. (2010). A computational model for automated extraction of structural schemes from simple narrative plots. Ph.D. thesis, Universidad Complutense de Madrid.
León, C., and P. Gervás (2010). Towards a Black Box Approximation to Human Processing of Narratives based on Heuristics over Surface Form. Paper at the AAAI 2010 Fall Symposium on Computational Models of Narrative November 11-13, 2010. Arlington, VA.
Lin, C.-Y., and E. Hovy (1997). Identifying topics by position. In Proceedings of the fifth conference on Applied natural language processing, ANLC ’97. Stroudsburg, PA: ACL, pp. 283-290.
Löwe, B. (2010). Comparing Formal Frameworks of Narrative Structures. In M. Finlayson (ed.), Computational models of narrative. Papers from the 2010 AAAI Fall Symposium, vol. FS-10-04 of AAAI Technical Reports, pp. 45–46.
Löwe, B. (2011). Methodological Remarks about Comparing Formal Frameworks for Narratives. In P. Allo and G. Primiero (eds.), Third Workshop in the Philosophy of Information, Contactforum van de Koninklijke Vlaamse Academie van België voor Wetenschappen en Kunsten. Brussel: KVAB, pp. 10-28.
Marcu, D. (1998). Improving Summarization through Rhetorical Parsing Tuning. In E. Charniak (ed.),Proceedings of the Sixth Workshop on Very Large Corpora. Montréal: Université de Montréal.
Marcu, D., M. Romera, M., and E. Amorrortu (1999). Experiments in Constructing a Corpus of Discourse Trees: Problems, Annotation Choices, Issues. In M. A. Walker (ed.), Towards Standards and Tools for Discourse Tagging. Proceedings of the Workshop, pp. 71-78.
Marcus, M. P., B. Santorini, and M. A. Marcinkiewicz (1993). Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics 19: 302-330.
Miller, G. A. (1995). WordNet: a lexical database for English. Commun. ACM, 38: 39-41.
Passonneau, R., N. Habash, and O. Rambow (2006). Inter-annotator Agreement on a Multilingual Semantic Annotation Task. In Proceedings LREC-2006, pp. 1951-1956.
Propp, V. Ya. (1928). Morfologiya skazki. Leningrad: Akademiya.
Rumelhart, D. E. (1980). On evaluating story grammars. Cognitive Science 4: 313-316.
Schank, R. C. (1982). Dynamic memory: A theory of reminding and learning in computers and people. Cambridge: Cambridge UP.
Si, M., S. C. Marsella, and D. V. Pynadath (2005). Thespian: using multi-agent fitting to craft interactive drama. In M. Pechoucek, D. Steiner, and S. Thompson (eds.), AAMAS ’05: Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (2005), pp. 21-28.
Turner, S. (1994). The creative process. A computer model of storytelling. Hillsdale, NJ: Lawrence Erlbaum.