The identi cation of similarity is crucial for reusing experience, where it provides the criterion for which elements to reuse in a given context, and for creativity, where generation of artifacts that are similar to those that already existed is not considered creative. Yet similarity is di cult to compute between complex artifacts such as stories. The present paper compares the judgment on similarity between stories explained by a human judge with a similarity metric for stories based on plan re nements. The need to identify the features that humans consider important when judging story similarity is paramount on the road to selecting appropriate metrics for the various tasks.
Appropriate metrics for similarity are fundamental tools in many elds of Arti cial Intelligence. For instance, there are several data mining and machine learning methods that are based on the similarity between the elements being considered. In case-based reasoning, similarity metrics are crucial for the retrieval and reuse of previous cases. Similarity is also fundamental for computational creativity because artifacts that are very similar to previously existing ones might not be considered creative. For this reason, it is important to take into account whether the metrics considered for a particular task adequately represent the concept of similarity that humans faced with the same task would apply. The present paper compares the judgment on similarity between stories explained by a human judge with a particular similarity metric for stories. The main goal is to identify which of the features that a human considers when evaluating story similarity are already taken into account by the metric, and which ones are not. The results of this comparison should provide a check list that might later on be applied to evaluate the appropriateness of other metrics.
The research reported in this paper was partially supported by the Project WHIM 611560 funded by the European Commission, Framework Programme 7, the ICT theme, and the Future and Emerging Technologies FET programme; and by the Spanish Ministry of Economy and Competitiveness under grant TIN2014-55006-R. Copyright © 2015 for this paper by its authors. Copying permitted for private and academic purposes. In Proceedings of the ICCBR 2015 Workshops. Frankfurt, Germany.
We focus on the structural similarity of stories represented as plans composed of actions corresponding to the events in the story. In order to do so, we apply a similarity metric based on plan re nements and compare the obtained results for a pair of stories with the similarities found by a human expert. The key point of this comparison is that the metric does not only calculate a numerical similarity between the compared stories, but provides a report of the found similarities. This report is then compared with the observations obtained by the human expert. The comparison allows us to see if the automatic metric has been able to grasp the same features the expert considered important, and if structural similarity is enough for comparing computer-generated stories. 2
Existing work on similarity for stories has focused on two di erent axes: story similarity for retrieval and classi cation of stories, and story similarity applied to the assessment of their novelty in a computational creativity setting. 2.1
In general, there is relative consensus on the fact that comparing stories can be made at di erent levels. Comparing stories at a relatively abstract level is common, to the point of comparing not the exact sequence of events but the overall plot, or even the relations between the characters. This aspect of narrative has been addressed by structuralist and cognitive Narratology.
In particular, comparing narratives has been a long term goal of
Computational Narrative, and several approaches have been taken with varying results
[
With respect to the assessment of creativity, a fundamental pillar is whether the
results of a creative process have produced novel artifacts [
The representation includes predicates representing narrative events and predicates describing properties of the characters that hold in particular states of the story. These appear jointly in the stream of predicates for the story, but have been separated in the presentation of stories in this paper for clarity.
The predicates presented here result from an e ort of reverse engineering of the stories that Propp describes as examples of the application of his framework to analyse existing Russian folk tales.
The rst two columns of Table 1 present two examples of the stories produced by the Propper system. Predicates in this table describe actions or events in the story. Table 2 represents non-narrative facts that are true for the arguments of the actions in Table 1. In order to compare the human interpretation of the stories with an automatically extracted report, we asked a human expert to write both stories in English and compare them. It is important to mention that the expert was familiar with this type of representation based on predicates, but she had to gure out the meaning of the predicates based solely on their names.
This story has the following main characters: a hero (373), a villain (818), and a false hero (672). In addition, a donor (371), a victim (819) and a dispatcher (189) appear as secondary characters.
The hero (373) is rst o ered a magical agent by a donor (371) if he performs a service. He does not perform the service but he obtains another magical agent anyway, which he consumes to acquire magical abilities.
Then, a villain (818) appears who declares war to a victim (819). The victim does not appear again.
Meanwhile, a dispatcher (189) talks about a past misfortune. The hero decides to react, sets out and wins (the war?), bringing peace with him. After that, the hero goes home, but he is disguised as the apprentice of an artisan and is not recognised. He nds a false hero (672) at home, who claims that he defeated the villain.
The hero is marked, solves a di cult task and returns to the court, this time disguised but as a groom. The false hero still claims that he defeated the villain, but he is exposed and it is known that he did not solved a di cult task.
This story has the following main characters: a hero (142), a villain (818), and a false hero (672). In addition, a victim (819) appears only at the beginning.
The story starts with the villain (818) declaring war to the victim (819). The hero (142) decides to react, becomes a seeker hero, sets out and wins (the war?). He brings peace and arrives to the court. But he is disguised as a groom and he is not recognized.
At the court, the false hero (672) claims that he defeated the villain. Someone (165) sets the hero a di cult task that involves strength. He solves the di cult task before the deadline, and returns to the court. Again he is disguised as a groom and he is not recognized.
And again, the false hero claims that he defeated the villain. However, the false hero is exposed and does not solve a di cult task. The hero gets a new physical appearance (undisguised?), and the villain is punished being tied to a horse tail.
Next, we asked the expert to compare both stories and describe the main similarities and di erences between them.
Both stories are similar in their characters and roles: a hero, a villain, and a false hero who claims to have defeated the villain.
In addition, in both stories the villain declares war to a victim, and the hero wins the war and brings peace. After that the hero returns (home or to the court) disguised (as a groom or as an apprentice), and he nds that a false hero claims to have defeated the villain. But at the end the false hero is exposed in both stories. Also, in both stories the hero makes two di erent journeys: one to win the war and return home/court, and one to solve a di cult task and then returning to court.
From the point of view of the di erences, Story 1 involves magic. The hero tries twice to obtain a magical agent, and the second time he achieves it and gets magical abilities. However, they are not used in the story. The main di erence in Story 2 is that at the end the villain is explicitly punished by being tied to a horse tail.
It is interesting to note that the rst things mentioned by the expert both in the descriptions and the comparison are the characters, although in the comparison only the most important characters are mentioned, as the others are considered less important for the plot.
In addition, the descriptions are based on the most important events in the story, so not all events are considered equally important. The comparison also shows that there is a high similarity between both stories in terms of characters and some of the narrative arcs. For example, the hero returns in both stories but to di erent places and with di erent disguises. However, these di erences (place and disguise) are not considered as important and the expert nds similarity in what is happening even when the stories are not exactly the same.
One of the main di erences between the stories is that one of them involves magic, but it is not considered so important because magic is not used in the rest of the story. Finally, the di erences in the endings are explicitly addressed in the comparison. This means that the end of the story is an important part of it. 3.3
Computing the Common Structure of Two Stories using Plan
Re nements
A story in its more basic form can be represented as a sequence of actions,
i.e., as a plan. There are di erent approaches to compute the similarity of two
plans. In this paper we use the similarity measure based on plan re nements
presented in [
Besides the actions and their order, this similarity measure also considers the action parameters and, if they are di erent in both plans, it is able to infer their common type according to a domain taxonomy. In this way, we are able to detect objects, characters and locations in di erent stories that have a di erent name but play the same role in the story.
The similarity measure computes this common structure performing
successive re nements in the space of partial plans [
The similarity measure works as follows. Let us suppose we want to compare two plans (or stories) p1 and p2. The similarity measure begins with an empty partial plan (a plan with no actions) that represents any possible plan and thus it is more general than p1 and p2. Then the partial plan is specialized using a re nement operator (adding new actions and ordering constraints or specializing the action's parameters) until we reach another partial plan that cannot be specialized anymore while being more general that both p1 and p2. This partial plan is the most speci c generalizer of p1 and p2, M SGpp1; p2q, and represents the common structure shared by the two plans. The length of the re nement chain from the empty plan to the M SGpp1; p2q is an indicator of how similar the two plans are. In the same way, the length of the re nement chain from the M SGpp1; p2q to each one of the two plans is an indicator of how much information is contained only in one of them but not in the other. The similarity value is computed as the ration between the amount of information shared and the total amount of information contained in the two plans.
The last columns of Tables 1 and 2 show the common structure computed by the similarity measure. In this case, the two stories are very similar and the inferred common graph of actions is so simple that, in fact, it can be represented as a sequence of actions. Constants representing characters, locations and objects common to both stories are kept in the common structure, and the other constants are replaced by variables with generalized types (variable names begin with `?').
The common structure of both stories could be summarized as follows. A villain declares war on a victim, what triggers the intervention of a hero that defeats him and brings peace back. Then the hero travels disguised and see how a false hero claims that he, and not the original hero, has defeated the villain. The hero leaves, solves a di cult task before some deadline, and comes back disguised. The false hero is exposed in court because he was not able to solve the di cult task. 4
There are a number of issues that the similarity metric considered here does not take into account.
First, the point in the story in which a particular sequence of actions takes place may lead to di erent results. A marriage at the start of the story sets the scene for later actions, but at the end of the story it usually acts as a reward for the e orts of some character. This in uence of context is not considered in the metric that has been described.
Second, some events are more signi cant than others. The presence of a murder in a given story is more signi cant than that of more mundane events such as setting o on a journey. This aspect might be captured by some kind of weighting of the importance of speci c events. The described metric does not allow for this type of behaviour.
The judgment expressed by the human placed considerable emphasis on the relative importance of the elements that appear in the stories. Characters are mentioned rst, then speci c actions. In both cases, a certain degree of abstraction is applied to identify conceptual similarity even between instances that are di erent. This suggests that taxonomical reasoning might be a useful tool for assessing similarity and that, as expected, abstraction is fundamental in story similarity.
These two aspects suggest that automatic story comparison needs to address
lifting between di erent levels of abstraction to be able to match those features
that humans are able to match. It also seems that the abstract matching at
di erent levels is a fundamental cognitive tool for comparing stories in humans.
This conclusion relates to the approach in [
The version of the Propper system that has been employed here provides only limited description of the characters. The descriptions considered are restricted to speci cation of the roles played in the narrative by particular characters, and a number of properties of particular arguments that are relevant for the correct chaining of later actions with their context of occurrence via their set of preconditions.
An important problem from the point of view of assessing the novelty of
creative processes is the need to consider an existing set of artifacts as a reference.
Generated artifacts are only novel if they are not similar to existing ones.
However, from a computational point of view, the approach of keeping a record of
all existing artifacts of a given type, and computing the similarity of any newly
generated artifacts with this set is not practical [
Overall, it seems that there are a number of aspects of stories that are relevant when attempting to establish similarity between two instances of story. Just how many such aspects should be included in a particular implementation as a similarity metric may depend substantially on the purpose for which it is intended. In the particular case of similarity metrics employed for case-based reasoning, the choice of which aspects of similarity to model should be guided by the particular aspects of the case that will be reused. If the cases are intended to provide story structure, the similarity should focus on story structure. If the cases are intended to inform decisions on the set of characters to employ, the similarity should focus on the set of characters. In relation to the point raised above concerning abstraction, it is important to note that focusing on particular aspects of story similarity may require speci c types of abstraction to implement the described lifting operation. Where similarity metrics are used for evaluating novelty in Computational Creativity settings, their use is much broader and it becomes more di cult to focus on particular aspects. Nevetheless, as it is very important to consider issues of e ciency, abstraction as means of reducing the range of attributes that need to be compared will clearly play a fundamental role in practical implementations.
The present work describes a process by which a computational system for computing the similarity between narrative structures is compared and calibrated against human judgment.
A number of issues considered by the human judge but not covered by the system have been discovered. These should be considered as a check list for the consideration of alternative metrics, and possibly as driving guidelines for the development of more elaborate metrics speci c to the assessment of story similarity.
The work described in this paper has addressed sequential single narrative threads. More complex narratives usually involve parallel story lines which merge or split at several points in the overall narrative. Whether the current metrics are valid for comparing similarity between this kind of narratives or not is yet an open question. Additionally, the use of di erent structures for stories also opens a new path, namely the application of the current process to stories that, while outputting an equivalent format, are generated by other story generation systems, probably conveying di erent semantics in the sequence of events, and possibly richer relations between characters.
From this point of view, more recent versions of the Propper system [
State is also fundamental in narrative composition and analysis. Narrative understanding of statements like \John squashed the spider" heavily depend on the relation between John and the spider (was it his mascot?). This kind of information must be taken into account in a general model of story similarity.
In all cases, further research must look into more metrics for story comparison and employ more experts to analyse how humans evaluate narratives. Following the intuition that we, as humans, perform a complex set of comparisons for evaluating similarity at di erent levels can lead to the discovery of plausible metrics and plausible aggregation methods into one single judgment.