There are many di erent abstractions as to what a 'storytelling' mechanism might be, each based on a particular understanding of what makes stories come together as a whole. Examples may be: archetypical instances of plot, story grammars, or the famous canonical sequence of character functions proposed by Vladimir Propp. From a computational point of view, each of these mechanisms can be used to construct or to validate new stories. The present paper carries out a comparative evaluation of a number of plot generation procedures, by grounding all of them on a basic reference vocabulary for the representation of narrative units, and applying to all of them a set of metrics distilled from the same procedures. The resulting set of computational tools is used in combination for comparative evaluation.
Humans have for a long time tried to understand how it is that they can come up with stories that make sense and are enjoyable. In this endeavour, many di erent abstractions as to what a 'story-telling' mechanism might be have arisen. Each of these mechanisms is based on a particular understanding of what makes stories come together as a whole. Examples of how these di erent understandings of the essence of storyness are captured may be: archetypical instances of plot, story grammars, or the canonical sequence of character functions proposed by Vladimir Propp. From a computational point of view, each of these ways of capturing what makes a story work can be understood in two di erent ways: either as a procedure for constructing new stories or as a procedure for determining whether a given candidate sample is a valid story. Each of these mechanisms must be considered at most one possible simpli cation of the much more complex problem which is story-telling.
The present paper carries out a comparative evaluation of a number of plot generation procedures, by grounding all of them on a basic reference vocabulary for the representation of narrative units, and applying to all of them a set of metrics distilled from the same procedures. 2
For the purposes of this paper we focus on an abstract view of stories that concentrates on their overall narrative structure without considering details beyond a particular level of abstraction. The level of abstraction we select is that of large-grain description of activities of character that are relevant to the narrative structure. We refer to this abstract view of a story as plot.
Work on modelling the abstract structure of story has taken place both at the theoretical level { models of story structure in abstract terms { and at the computational level { computational implementations for story construction. 2.1
Vladimir Propp [
Gervas et al [
Gervas et al [
George Lako attempted [
DonorSequence ! test by donor hero reaction acquisition magical agent use magical agent Resolution ! struggle victory j difficult task task resolved
Table 1. Lako 's reinterpretation of Propp's morphology for Russian Folk Tales as a grammar
Rumelhart [
Thorndyke [
mars were discredited as an actual model of human cognitive processing of stories
[
The Propper system [
ALLOW(Setting,Episode) AND(States) (ALLOW(Event,Event) j CAUSE(Event,Event) ), INITIATE(Event,Reaction)
ALLOW(Action,Consequence) MOTIVATE(Subgoal,Attempt) procedure that take into account the possibility of dependencies between character functions { such as for instance, a kidnapping having to be resolved by the release of the victim { and the need for the last character function in the sequence for a story to be a valid ending for it. Metrics are proposed to evaluate the validity of story candidates. 3 A Toolkit of Story Structure Abstractions as
Constructors and Evaluators To achieve a meaningful comparative evaluation of the various plot generation procedures, we consider the following steps. First we establish a reference representation format of abstract units of narrative, and we map it to the di erent representations of narrative used by the construction procedures considered. Second we identify how these construction procedures may be adapted to act as validation procedures. Finally, we carry out a number of experiments that combine the resulting resources. 3.1
In order to compare di erent story generation procedures with one another, it
is important that they generate outputs in a comparable representation format.
To avoid the problems associated with evaluating natural language renderings of
narrative [
We adopt as common set of abstract units of representation of narrative the
set of plot elements described in [
The allignment between the set of plot elements and the various alternative representations is described in Tables 4 and 5.
It is important to note that the set of plot elements is more detailed and more ne-grained than the set of Propp's character functions. The correspondence between them has been established by considering that: (1) certain character functions represent more than one plot element { such as for instance Abduction and Imprisoned being types of villainy { and (2) certain character functions were phrased to encompass a range of options and the ner granularity allows for distinctions that were not available originally { such as Propp's use of hero marries to cover both Reward and Wedding.
With respect to the terminal symbols in Rumelhart's and Thorndyke's grammars, it must be noted that certain plot elements are slightly ambiguous with respect to their classi cation. Examples of this are Cross-Dressing, which in terms of Rumelhart's grammar can be considered either an Action in itself or as a Change-of-state that results from the action, or AnEnemyLoved which in terms of Thorndyke's grammar can be considered an Event in itself { if one focuses on the moment that it happens {, a State { if one focuses on the animic state of the protagonist { or as a DesiredState { if one focuses on what the protagonist hopes for. This suggests that the particular categories being used might require careful re nement. We consider this task outside the scope of the present paper. Although we might address it as further work, we opt at this stage for accepting that certain plot elements might be classi ed under more than one of the available categories.
The existence of dependencies between character functions had been
identied as a fundamental ingredient in the perception of the validity of a story [
ProppBaseline an adapted version of Propp's suggested method of selecting
elements at random from the canonical sequence of character functions [
ProppDependency an adapted version of the re nement proposed in [
PropperGrammar grammar-based generation using an instance of the
grammar used by the Propper system [
Lako Grammar grammar-based generation using an instance of Lako 's
grammar for Proppian tales [
RumelhartGrammar grammar-based generation using an instance of
Rumelhart's grammar [
ThorndykeGrammar grammar-based generation using an instance of Thorndyke's
grammar [
The di erent formalisms for story generation described in section 3.2 can be adapted to provide a diagnostic procedure that, given a sequence of plot elements, can provide a numerical score that represents some type of conformance of that sequence to the view of narrative exempli ed by the approach.
Some of the construction procedures considered provide simple solutions to
achieve this. The following metrics are considered:
SS similarity between the candidate sequence and the most similar of the schemas
in the set of schemas of narrative identi ed in [
PS conformance to Propp's canonical sequence of character functions { as
presented in [
E(Cor ) considers whether the nal plot element in a candidate sequence is valid as an ending, de ned in terms of a corpus Cor { which in the present case is Propp's original set of Russian tales (rt ).
A grammar provides a strict judgment on the validity of a given sequence, classifying it as either valid or invalid. We require a metric that indicates the degree of partial conformance of a candidate sequence to a given grammar. To this end, for any parse of a candidate plot element sequence that does not result in a valid parse, we build a shadow tree that uses empty place holder nodes for the top part of the grammar, until the nodes that have been identi ed from the input sequence can be linked to it. In any given shadow tree, there are a number of empty nodes { which are simply place holders for non-terminal symbols of the grammar for which no support has been found in the input sequence { and nonempty nodes { which correspond to assignments of non-terminal symbols of the grammar to parses of subsequences of elements found in the candidate sequence. As indicative rst approximation we consider the following metric with respect to a grammar X : GR(X ) ratio of non-empty nodes over the total number of nodes in the shadow tree. 3.4
The set of construction procedures is run 100 times to produce 100 di erent candidates sequences. The set of metrics is applied to all the candidate sequences. The average results for the various construction procedures over the basic metrics are presented in Table 6, together with some basic data on sequence length. The values of all metrics are normalised over 100 for ease of comparison.
The rst columns of Table 6 refer to the length of the generated sequences of plot elements. In each case, minimum length (minL), maximum length (maxL) and average length (Len) are given. Di erences in length across the sequences arise from di erent factors, depending on the nature of the technique employed.
The SchemaBaseline instantiates one of the available schemas, which are of xed length. ProppBaseline and ProppDependency are limited by the size of Propp's canonical sequence, and variations arise from the choices made { random (ProppBaseline) and driven by satisfaction of dependencies across the elements chosen (ProppDependency). The remaining solutions apply different grammars to generate sequences. Variations in length arise from di erent choices over the available rules of the grammar. Both PropperGrammar and Lako Grammar use grammars intended to capture Propp's account. RumelhartGrammar and ThorndykeGrammar use grammars intended for more generic concepts of story.
With respect to the proposed metrics, the behaviour of the di erent construction procedures di ers widely, as expected.
For PS, which captures conformance to Propp's canonical sequence, the best score is ProppDependency (80) with ProppBaseline a close second (74). The metric fails to give top scores of 100 because it sometimes penalises for non-appearance of elements in the sequence that are optional. Enforcement of dependencies makes more of these optional elements appear, whenever their antecedents have already been included. The relative performance of PropperGrammar and Lako Grammar can be interpreted as an indication that their grammars are not entirely capturing the essence of the canonical sequence, and that the grammar used by the Propper system does this slightly better than Lako 's grammar. In this sense, SchemaBaseline performs reasonably well (39), indicating that there is a close relation between the canonical sequence and the plot schemas used as reference. RumelhartGrammar and ThorndykeGrammar are clearly not built to consider this aspect.
For DS { degree of satisfaction of dependencies between plot elements { the top performer is again ProppDependency (49), that incorporates this aspect in its decision processes. The surprisingly low value in this case arises from the frequent existence of multiple dependents for a given plot element, whereas in a plot each appearance of an antecedent is normally resolved by a single consequent. It is interesting to note that the procedures that rely on representation of structure (SchemaBaseline, PropperGrammar and Lako Grammar) also perform reasonably well (values around 40), presumably because the structure they use captures dependencies across the elements to a certain extent. Other procedures perform poorly. The length of the plots is not an issue because the metric is normalised over the number of potential dependencies appearing in the plot.
With respect to endings as found in Russian folk tales, E(rt), it is clear that PropperGrammar (100) and Lako Grammar (100) by construction capture perfectly the typical ending of a Russian folk tale from the corpus used by Propp. ProppDependency (86) seems to have sometimes been forced to add tailing consequents that spoil its performance. SchemaBaseline does reasonably well (71) and ProppBaseline (64) succeeds often simply by picking elements from the end of the canonical sequence. Aditional metrics for endings need to be considered.
On similarity to existing schemas, SS, SchemaBaseline (100) shines, and all the procedures based on the Proppian account fare quite well. Again, pointing towards similarities between the canonical sequence and the schemas.
On compliance to a given grammar, not surprisingly, RumelhartGrammar and ThorndykeGrammar come out as top performers on their respective grammar, with others far behind.
The description of the results in terms of averages is useful to identify di erences between di erent procedures. However, it is also clouding the di erences that may arise between plots generated by the same procedure. It is at this level that valuable insights for further work may arise.
PS DS E(rt) SS GR(R) GR(T) Av
SchemaBaseline 18 52 Villainy 86 Pursuit 100 RescueFromPursuit 100 Struggle 53 Victory 37 Revenge 71.3 Riches
SchemaBaseline 03 28 Imprisoned 40 Pursuit 0 RescueFromPursuit 100 Struggle 53 Victory 37 Maturation 43.0 RepentanceRewarded
Examples of speci c plots, together with their values for the given metrics, are shown in Table 7. For each construction procedure, the best and worst performers in terms of the average of all the metrics are shown. This can serve to show a wide range of possible values without cherry-picking interesting outputs. For each example, the rst column indicates the values obtained by the story on the metrics, and the second column indicates the sequence of plot elements produced.
The results in in Table 7 show a number of interesting insights. The basic structure of Propp's account is shared by many of these solutions, resulting in frequent appearance of similar sub-sequences across samples that score highly. The Rumelhart and Thorndyke grammars result in sequences that score very low on all the other metrics, but which have more surprising plot elements, combined in ways that di er from the basic sequence. Part of the problem here, is that only the syntactic part of these grammars has been considered. If the semantic interpretation rules provided by Rumelhart were considered to inform the process of selecting plot elements to instantiate the grammar, better results may be obtained. This will be considered as further work.
The di erences in performance across the di erent approaches and the fact that now example performs well under all of the metrics indicate that each approach is focusing on a particular valuable aspect of stories. This suggests that an ideal method for plot generation should strive to combine the di erent aspects in a single constructive procedure. Alternatively, a simpler way of improving results might be achieved by using the metrics for some approaches to select best performers out of the set of results obtained by a di erent approach. This is a particularly interesting insight that will be pursued in further work.
It would be interesting to extend this evaluation to plot generation solutions beyond those developed by the author. Because the methodology invovles grounding the representation used on the reference vocabulary, this would require not just access to the source code of such solutions but also a relatively detailed understanding of the particular solution, to avoid betrayals of its spirit. 5
The analysis of the comparative evaluation shows that each type of procedure for the generation of stories focuses on features that may be necessary in a story. But such features are generally not su cient, in the sense that other attempts to formulate the structure of stories with di erent tools may be capturing additional features that are also relevant. The comparative evaluation has served to identify a number of shortcomings in the various approaches when considered individually. Re nements of the approaches and consideration of additional approaches are possible lines of future work. However, the most promising avenue of work for short-term improvement of results would be joint use of a given generative procedure and validation procedures based on di erent aspects of stories.
This paper has been partially supported by the IDiLyCo project (TIN201566655-R) funded by the Spanish Ministry of Economy, Industry and Competitiveness.