Authorea

Joe Corneli second major version over 8 years ago

Commit id: 0d9363bf80933b6b29f29ddf4323d6ce30ec0e7a

deletions | additions

analyses current evaluation procedures used in computational creativity, and provides a much-needed set of customisable evaluation guidelines, the \emph{Standardised Procedure for Evaluating Creative Systems} (SPECS) \cite{jordanous:12}. Originally designed to evaluate the concept of creativity, the three step SPECS process firstly requires the evaluator to define the concept(s) on which they are evaluating will evaluate the system on. system. This definition is then converted into standards that can eventually be used to test and evaluate individual systems, or comparatively evaluate multiple systems. % We follow a slightly modified version of her Jordanous's earlier evaluation guidelines, in that rather than attempt a definition and evaluation of {\em creativity}, we follow the three steps for \emph{serendipity}.

% Most prior work that deals with serendipity in a computing context focuses on computational ``discovery''; we argue that serendipity also includes an important ``invention'' aspect. % We survey literature describing serendipitous discovery and invention in science and technology, as well as the etymology and definitions of the term ``serendipity''. \emph{serendipity}. Building upon and refining previous work, we propose a model of computational serendipity that can be used to evaluate computational systems. To this end we adapt existing recommendations for evaluating computational \emph{creativity}. % We develop case studies that evaluate the serendipity of existing systems, and develop a thought experiment that applies our model to design a multi-agent environment for computer poetry. % From our analyses, we extract recommendations for practitioners working with computational serendipity, and outline future directions for research. \\[.5cm] % %% \\[.3cm] \keywords{serendipity, %% design patterns, %% intelligent machinery, %% evaluation, discovery, invention, computational creativity, evolutionary computing, recommender systems, Writers Workshops} \end{abstract}

was observed when malarial Europeans first arrived in Peru. The joint appearance of shivering Europeans and a South American remedy was the trigger. That an extract from cinchona bark can cure and can even prevent malaria was understood learned subsequently. \end{itemize} \begin{itemize} \item \textbf{Bridge}: These include The bridge often includes reasoning techniques, such as abductive inference (what might cause a clear patch in a petri dish?); analogical reasoning (de Mestral constructed a target domain from the source domain of burrs hooked onto fabric); and conceptual blending (Kekul\'e, discoverer of the benzene ring structure, blended his knowledge of molecule structure with his vision of a snake biting its tail). The bridge may also rely on new social arrangements, such as the formation of cross-cultural research networks. \end{itemize}

begin or to continue a search into unfamiliar territory. We use this word to describe both simple curiousity and related deeper drives. Charles Goodyear \citeyear{goodyear1855gum} reflects on his own life experience as follows: ``from ``[F]rom the time his attention was first given to the subject, a strong and abiding impression was made upon his mind, that an object so desirable and important, and so necessary to man's comfort, as the making of gum-elastic available to his use,

\citeyear[p. 643]{van1994anatomy} estimates that in twenty percent of innovations ``something was discovered before there was a demand for it.'' To illustrate the role of this factor, it may be most revealing to consider a ``counterexample,'' counterexample, in which a case where dynamics were not attended to carefully and the process suffers outcome suffered as a result. Cropley \citeyear{cropley2006praise} describes the pathologist Eugen Semmer's failure to recognise the importance of the role of \emph{penicillium notatum} in restoring two unwell horses to health: ``Semmer saw the horses' return to good health as a problem that made it impossible for him to investigate the cause of their death, and reported \ldots\ on how he had succeeded in eliminating the mould from his laboratory!''

that segment the context into sub-contexts, or that cause the investigator to look in more than one direction. The tasks may have an interesting \emph{overlap}, or they may point to a \emph{gap} in knowledge. As an example of the latter, For example, Penzias and Wilson used a large antenna to detect radio waves that were relayed by bouncing off of satellites. After they had removed interference effects due to radar, radio, and heat, they found residual ambient noise that

\end{itemize} \begin{itemize} \item \textbf{Multiple influences}: The ``bridge'' bridge from trigger to result is often found through by making use of a social network, thus,for instance Penzias and Wilson only understood the significance of their work after reading a preprint by Jim Peebles that hypothesised the possibility of measuring radiation released by the big bang. \end{itemize} \noindent We will show how the key condition,the components, dimensions and environmental factors of serendipity can be modelled and assessed in computational systems in Sections \ref{sec:our-model} and \ref{sec:computational-serendipity}.

The 13 criteria from Section \ref{sec:literature-review} specify the conditions and preconditions that are conducive to serendipitous discovery. These Section \ref{sec:our-model} distills our criteria into a computational definition, and the criteria have been further formalised in Section \ref{specs-overview} using SPECS. %% \citeA{pease2013discussion} used a variant of these SPECS criteria to

Before describing these examples, as a baseline, we introduce the notion of \emph{minimally serendipitous systems}. According to our standards, there are various ways to achieve a result with \emph{low} little or no serendipity: if the observation was likely, if further developments happened with little skill, and if the the value of the result was low, then we would not say the outcome was serendipitous. We would be

user, then there is little reason to call the system's operation serendipitous -- even if it consistently does its job very well. For example, machines can learn to recognise or approximate certain types of patterns, but it ismore surprising when a computational system independently finds an entirely new kind of pattern. Furthermore, the position of the evaluator is important: a spell-checking system might suggest a particularly fortuitous substitution, but we would not

\citeA{jordanous10} reported a computational jazz improvisation system using genetic algorithms. Genetic algorithms, and evolutionary computing more generally, could encourage computational serendipity. We examine Jordanous's system (later given the name {\sf GAmprovising} \cite{jordanous:12}) as a case study for evolutionary computing in the context of our model of computational serendipity: to what extent does {\sf GAmprovising} model serendipity? {\sf GAmprovising} uses genetic algorithms to evolve a population of \emph{Improvisors}. Each Improvisor is able to randomly generate music based on various parameters such as the range of notes to be used, preferred notes to be used, notes, rhythmic implications around note lengths and other musical parameters \cite{jordanous10}. These parameters are what defines the Improvisor at any point in the system's evolution. After a cycle of evolution, each Improvisor is evaluated via a fitness function based on Ritchie's \citeyear{ritchie07} criteria for creativity. This model relies on user-supplied ratings of the novelty and appropriateness of the music produced by the Improvisor to calculate 18 criteria that collectively indicate how creative a the system is. The most successful Improvisors (according to this fitness function) are used to seed a new generation of Improvisors, through crossover and mutation operations. The {\sf GAmprovising} system can be said to have a \textbf{prepared mind} through its background knowledge of what musical concepts to embed in the Improvisors and the evolutionary abilities to evolve Improvisors. A potential \textbf{serendipity trigger} comes from the combination of the mutation and crossover operations previously employed in the genetic algorithm, and the user input feeding into the fitness function to evaluate produced music. A \textbf{bridge} is built by to new results through the creation of new Improvisors. The \textbf{results} are the various musical improvisations produced by the fittest Improvisors (as well as, perhaps, the parameters that have been considered fittest). The likelihood of serendipitous evolution is greatly enhanced by the use of random mutation and crossover operations within the genetic algorithm, which increase the diversity of the search space covered by the system during evolution. The \textbf{chance} of encountering any particular pair of Improvisor and user evaluation is vanishingly low, given the massive dimensions of the this search space. The evolution of the population of Improvisors could be described as \textbf{curiosity} about how to satisfy the musical tastes of a particular human user who identifies certain Improvisors as interesting. The system's \textbf{sagacity} corresponds to the likelihood that the user will appreciate a given Improvisor's music (or similar music) over time. One challenge here is that the tastes of the user may change. The \textbf{value} of the generated results are is maximised through by employing a fitness function. Evolutionary systems such as {\sf GAmprovising} necessarily operate in a \textbf{dynamic world} which is evolving continuously and that must, in particular, take into account the evolution of the user's tastes. \textbf{Multiple contexts} arise from the user changing their preferences over time or and through the possibility of having multiple users evaluate the musical output. This variant version of the system is not yet implemented, but would be occupied with the more complex problem of satisfying multiple different users' preferences simultaneously. Moving to a more complex problem domain would require the system to be curious about more than one user at a time, and require greater sagacity if the system is to successfully satisfy multiple tastes. \textbf{Multiple tasks} are carried out by the system including evolution of Improvisors, generation of music by individual Improvisors, capturing of user ratings of a sample of the Improvisors' output, and fitness calculations. \textbf{Multiple influences} are captured through the various combinations of parameters that could be set and the potential range of values for each parameter. %% Table \ref{caseStudies} summarizes how serendipity in such a system can be described in terms of our model. \paragraph{Recommender systems.}

Current research in this area focuses on the first aspect and tries to find and assess \textbf{serendipity triggers} by exploiting patterns in the search space. For example, \citeA{Herlocker2004} as well as \citeA{Lu2012} associate less popular items with high unexpectedness. Clustering is also frequently used to discover latent structures in the search space. For example, \citeA{Kamahara2005} partition users into clusters of common interest, while \citeA{Onuma2009} as well as \citeA{Zhang2011} perform clustering on both users and items. %\citeA{Oku2011} allow the user to select two items in order to mix their features. in a sort of conceptual blend. Note that in the course of evolution of these and other systems it is generally the system's developers who plan and perform adaptations: even in the Bayesian case, the system has limited autonomy. Nevertheless, the impetus to develop increasingly autonomous recommender systems is present, especially in complex domains where hand-tuning is either very cost-intensive or infeasible. With this challenge in mind, we investigate how serendipity could be achieved on the system side, and potentially be reflected back to the user. In terms of our model, current systems have at least the makings of a \textbf{prepared mind}, comprising both a user- and a domain model, both of which can be updated dynamically. User behaviour (e.g.~following up on these certain recommendations) may serve as a \textbf{serendipity trigger} for the system, and change the way it makes recommendations in the future. A \textbf{bridge} to a new kind of recommendation may be found by pattern matching, and especially by looking for exceptional cases: when new elements are introduced into the domain which do not cluster well, or different clusters appear in the user model that do not have obvious connections between them. The intended outcome of recommendations depends on the organisational mission, and can in most cases be situated between making money and empowering the user. The serendipitous \textbf{result} on the system side would be learning a new approach that helps to address these goals. %%% \begin{table}[Ht!]

asks how these features \emph{might} be useful. These routines suggest the relevance of a computational model of \textbf{curiosity}. % Rather than Far from being a simple look-up rule, $p^{\prime}$ involves creating new knowledge. A simple example is found in clustering systems, which generate new categories on the fly. A more complicated example, necessary in the case of updating $p$ or $p^{\prime}$, is automatic programming. There is a need for \textbf{sagacity} in this sort of affair. % Judgment of the \textbf{value} of the result $R$ may be carried out ``locally'' (as an embedded part of the process of invention of $R$)

phase. If the process operates in an ``online'' manner, $T^\star$ may be an evolving vector of interesting possibilities. % The \textbf{prepared mind} corresponds to the prior training relevant in each phase, labelled $p$ and $p^{\prime}$ in our diagram. % % The \textbf{bridge} is comprised of the actions based on $p^{\prime}$

\section{Discussion} \label{sec:discussion} In the preceding section, we applied our model to evaluate the serendipity of an evolutionary music improvisation system and a class of next-generation recommender systems, and we sketched a design for a multi-agent system for poetry based on the idea of a Writers Workshop. The model has helped to highlight directions for development that would increase the potential for serendipity in existing systems, either incrementally or more transformatively. The model has helped create a reasonably concrete system design. Our analysis of these examples illustrates some of steps that can be taken in order to design systems that can observe events that would otherwise not be observed, take an interest in them, and transformtheir observations into an artefact artefacts with lasting value. We will now discuss implications from our findings for future research, and outline potential next steps. \input{recommendations} \input{future-work-intro}

\subsection{Etymology and selected definitions} \label{sec:overview-serendipity} The English term ``serendipity'' derives from the 1302 long poem \emph{Eight Paradises}, written in Persian by the Sufi poet Am\={\i}r Khusrow in Uttar Pradesh, India.\footnote{\url{http://en.wikipedia.org/wiki/Hasht-Bihisht}} In the English-speaking world, its first chapter became known as ``The Three Princes of Serendip'', where ``Serendip'' represents the Old Tamil-Malayalam word for Sri Lanka (%{\tam சேரன்தீவு}, \emph{Cerantivu}), ``island \emph{Cerantivu}, island of the Ceran kings.'' kings). % The term ``serendipity'' is first found in a 1757 letter by Horace Walpole to Horace Mann: \begin{quote}

The term became more widely known in the 1940s through studies of serendipity as a factor in scientific discovery, surveyed by Robert Merton and Elinor Barber \citeyear{merton} in ``The Travels and Adventures of Serendipity, A Study in Historical Semantics and the Sociology of Sciences''. Merton \citeyear{merton1948bearing} \cite[pp. 195--196]{merton} describes a generalised ``serendipity pattern'' and its constituent parts: \begin{quote} ``\emph{The serendipity pattern refers to the fairly common experience of observing an \emph{unanticipated}, \emph{anomalous} \emph{and strategic} datum which becomes the occasion for developing a new theory or for extending an existing theory.}''~\cite[p. 506 {[}emphasis original{]}]{merton1948bearing} 506]{merton1948bearing}~{[}emphasis in original{]} %% The datum [that exerts a pressure for initiating theory] is, first of all, unanticipated. A research directed toward the test of one hypothesis yields a fortuitous by-product, an unexpected observation which bears upon theories not in question when the research was begun. %% Secondly, the observation is anomalous, surprising, either because it seems inconsistent with prevailing theory or with other established facts. In either case, the seeming inconsistency provokes curiosity; it stimulates the investigator to "make sense of the datum," to fit it into a broader frame of knowledge.... %% And thirdly, in noting that the unexpected fact must be "strategic," i. e., that it must permit of implications which bear upon generalized theory, we are, of course, referring rather to what the observer brings to the datum than to the datum itself. For it obviously requires a theoretically sensitized observer to detect the universal in the particular.

exploitation of chance observation, especially in the discovery of something useful or beneficial.'' Pek van Andel \citeyear[p. 631]{van1994anatomy} describes it simply as ``the art of making an unsought finding''. finding.'' Roberts \citeyear[pp. 246--249]{roberts} records 30 entries for the term ``serendipity'' from English language dictionaries dating from 1909 to 1989.

those prepared minds. These may be described as serendipitous sociocognitive microenvironments'' \cite[p. 259--260]{merton}.} Large-scale scientific and technical projects generally rely on the convergence of interests of key actors and on other cultural factors. For example, Umberto Eco \citeyear{eco2013serendipities} focuses on describes the historical role of serendipitous mistakes and falsehoods in the production of knowledge.

with built-in indeterminacy. Figure \ref{fig:va-pattern-figure} presents an example, showing how one of van Andel's patterns of serendipity can be rewritten as a design pattern using the template suggested by our model; in model. In future work, we would aim to build a more complete pattern language along similar lines. lines, and show how this language can be used to transform raw data into ``strategic data.'' % The example pattern describes a scenario that is quite close to Pease et al.'s \citeyear{pease2013discussion} description of an online system that gathers new modules over time, and for which,

groundwork for the more involved development projects discussed in the current paper. % Patterns of serendipity, like the one above, in Figure \ref{fig:va-pattern-figure}, offer useful heuristic guidelines for human programmers and convey a sense of our long-term plans for serendipitous computing systems. \begin{figure}[!ht] \begin{mdframed} \paragraph{\textbf{Successful error}}~ \vskip -1\baselineskip \begin{flushright}\emph{Van Andel's example} -- Post-it\texttrademark\ Notes \end{flushright} \vspace{-.15cm} \begin{description}[itemsep=2pt] \item[{\tt context}] -- You run a creative organisation with several different divisions and many contributors with different expertise. \item[{\tt problem}] -- One of the members of your organisation discovers something with interesting properties, but no one knows how to turn it into a product with industrial or commercial application. \item[{\tt solution}] -- You create a space for sharing and discussing interesting ideas on an ongoing basis (perhaps a Writers Workshop). \item[{\tt rationale}] -- You suspect it's possible that one of the other members of the firm will come up with an idea about an application; you know that if a potential application is found, it may not be directly marketable, but at least there will be a prototype that can be concretely discussed. \item[{\tt resolution}] -- The \emph{Successful error} pattern rewritten using this template is an example of a similar prototype, showing that serendipity can be talked about in terms of design patterns. \end{description} \end{mdframed} \caption{Our design pattern template applied to van Andel's \emph{Successful error} pattern\label{fig:va-pattern-figure}} \end{figure}

%% \end{itemize} %% \citeA{meszaros1998pattern} describe the typical scenario for authors of design patterns:\begin{figure}[!ht] \begin{mdframed} \paragraph{\textbf{Successful error}}~ \vskip -1\baselineskip \begin{flushright}\emph{Van Andel's example} -- Post-it\texttrademark\ Notes \end{flushright} \vspace{-.15cm} \begin{description}[itemsep=2pt] \item[{\tt context}] -- You run a creative organisation with several different divisions and many contributors with different expertise. \item[{\tt problem}] -- One of the members of your organisation discovers something with interesting properties, but no one knows how to turn it into a product with industrial or commercial application. \item[{\tt solution}] -- You create a space for sharing and discussing interesting ideas on an ongoing basis (perhaps a Writers Workshop). \item[{\tt rationale}] -- You suspect it's possible that one of the other members of the firm will come up with an idea about an application; you know that if a potential application is found, it may not be directly marketable, but at least there will be a prototype that can be concretely discussed. \item[{\tt resolution}] -- The \emph{Successful error} pattern rewritten using this template is an example of a similar prototype, showing that serendipity can be talked about in terms of design patterns. \end{description} \end{mdframed} \caption{Our design pattern template applied to van Andel's \emph{Successful error} pattern\label{fig:va-pattern-figure}} \end{figure} \noindent ``You are an experienced practitioner in your field. You have noticed that you keep using a certain solution to a commonly occurring problem. You would like to share your experience with others.'' There are many ways to describe a solution.

An interdisciplinary perspective on the phenomenon of serendipity promises further illumination. Here, we consider the potential for formalising this concept. This paper follows and expands \citeA{pease2013discussion}, where many of the ideas that are developed here were first presented. The current paper reassesses and updates this earlier work, developingit towards a robust computational characterisation of serendipity for computer modelling and system evaluation. New claims are advanced, positioning serendipity as a fundamental concept in computational creativity, with exciting potential to play a key role in computational intelligence more broadly. There is particularly interesting potential for serendipity within computational systems whose processes involve interaction with users, and autonomous systems that make use of a multi-agent framework.\footnote{It should not be assumed that a system that can accommodate user interaction would directly lead to serendipity; take for example the use of a calculator, where potential for serendipity through user interaction is minimal at best.} Serendipity is centred on reevaluation. For example, a non-sticky ``superglue'' that no one was quite sure how to use turned

unexpected is found to be both explicable and useful. Importantly, serendipity is not the same as luck. It involves making sense of something unexpected, in an unanticipated way. Although computational processes often evolve in unexpected ways unexpectedly \cite{minsky1967programming}, the bridge from an unexpected discovery to a useful new invention poses several difficult challenges for computational modelling.

However, we believe that serendipity is not so mystical as such statements might seem to imply, and in Section \ref{sec:discussion} we indicate that ``patterns of serendipity'' like those collected by van Andel are likely to be applicable in computational settings. First, in Section \ref{sec:literature-review}, we survey the broad literature on

\ref{sec:ww} is one possible design for a system that can \emph{learn from experience}. The Workshop model ``personifies'' the wider world in the form of one or several critics. It isclearly also possible for a lone creative agent to take its own critical approach in relationship to the world at large, using an experimental approach to generate feedback, and then looking for models to fit this feedback. We are led to consider

\textquotesingle~\textquotesingle~\textquotesingle\textbackslash n\textquotesingle~< file.txt | grep -c "stem*"}, and total word counts via {\tt wc -w}. The corresponding counts for the \emph{current} paper are 12, \emph{25}, \emph{16}, \emph{46} \emph{44} and 12.5K.} 12.7K.} \medskip

An active research community investigating computational models of serendipity exists in the field of information retrieval, and specifically, in recommender systems \cite{Toms2000}. In this domain, \citeA{Herlocker2004} and \citeA{McNee2006} view serendipity as an important factor for user satisfaction, alongside accuracy and diversity. Serendipity in recommendations is understood to imply that the system suggests \emph{unexpected} items, which the user considers to be \emph{useful}, \emph{interesting}, \emph{attractive} or \emph{relevant}. % \cite{Herlocker2004} \cite{Lu2012},\cite{Ge2010}. Definitions differ as to the requirement of \emph{novelty}; \citeA{Adamopoulos2011}, for example, describe systems that suggest items that may already be known, but are still unexpected in the current context. While standardised measures such as the $F_1$-score or the (R)MSE are used to determine the \emph{accuracy} of a recommendation (i.e.~the (i.e.~whether the recommended item is very close to what the user is already known to prefer), there is no common agreement on a measure for serendipity yet, although there are several proposals \cite{Murakami2008, Adamopoulos2011, McCay-Peet2011,iaquinta2010can}. In terms of our model, these systems focus mainly on producing a \emph{serendipity trigger} and predicting the potential for serendipitous discovery \emph{discovery} on the side of the user. Intelligent user modeling could bring other components of serendipity into play, as we will discuss in Section \ref{sec:computational-serendipity}. Recent work has examined related topics of \emph{curiosity} \cite{wu2013curiosity} and \emph{surprise} \cite{grace2014using} in

other's aims or of the work they are critiquing, and may as a consequence talk past one another to a greater or lesser degree -- while nevertheless finding the overall process of participating in the workshopitself illuminating and rewarding (often precisely because such misunderstandings elucidate poor communication choices!). Various social strategies, ranging from Writers Workshops to open source software, pair programming, and design charettes

and the degree to which the computer was responsible for coming up with this problem. As \cite[p. \citeA[p. 69]{pease2013discussion} remark, anomaly detection and outlier analysis are part of the standard machine learning toolkit -- but recognising \emph{new} patterns and defining \emph{new} problems is more ambitious. Establishing complex analogies between evolving problems and solutions is one of the key strategies for used by teams of human designers \cite{Analogical-problem-evolution-DCC}. Kazjon Grace \citeyear{kaz-thesis} presents a computational model of the creation of new concepts and interpretations, but this work did include the

interface between author and critic. In principle these modules need to be prepared to deal, more or less thoughtfully, with \emph{any} text, and in turn, with \emph{any} comment on that text. Certain limits may be agreed in advance; advance, e.g.~as to genre or length in the case of texts, and what constitutes an acceptable comment. texts; ground rules may constrain the type of comments that may be made. %% The loop for learning by asking questions as they arise is %% reminiscent of the operating strategy of {\sf SHRDLU} %% \cite{winograd1972understanding}.

learn what others see in the poem. More formally, in this case $T^\star$ may be seen as an evolving vector with shared state, but viewed and handled from different perspectives. With multiple agents involved in the discussion, the ``comment generator'' module component would expand to contain its own feedback loops.\par\medskip \noindent \textbf{Bridge.}

% The system as a whole can be further decomposed into generative components, as in Figure \ref{fig:generative-diagram}. In our thought experiment, we focuson exploring the features case ofserendipity by thinking through how this design would apply to collaborative critique of poetry; similar ideas would apply for prose and, with further adaptation, other arts.\\

\subsection{Thought experiment: Serendipity by design} \label{sec:ww} To further evaluate our computational framework in usage, in this section we apply develop a thought experiment in system design, based on a novel computational scenario where there is high potential for serendipity. As discussed above, sociological factors can influence serendipitous discoveries on a social scale. In our two case studies,

occur within a computer system as well. In \cite{poetry-workshop}, we described the preliminary designs for multi-agent systems that learn by sharing work in progress, progress and discussing partial understandings. % Following \citeA{gabriel2002writer}