samer@41: \documentclass[conference]{IEEEtran}
samer@59: \usepackage{fixltx2e}
samer@4: \usepackage{cite}
samer@4: \usepackage[cmex10]{amsmath}
samer@4: \usepackage{graphicx}
samer@4: \usepackage{amssymb}
samer@4: \usepackage{epstopdf}
samer@4: \usepackage{url}
samer@4: \usepackage{listings}
samer@18: %\usepackage[expectangle]{tools}
samer@9: \usepackage{tools}
samer@18: \usepackage{tikz}
samer@18: \usetikzlibrary{calc}
samer@18: \usetikzlibrary{matrix}
samer@18: \usetikzlibrary{patterns}
samer@18: \usetikzlibrary{arrows}
samer@9: 
samer@9: \let\citep=\cite
samer@33: \newcommand{\colfig}[2][1]{\includegraphics[width=#1\linewidth]{figs/#2}}%
samer@18: \newcommand\preals{\reals_+}
samer@18: \newcommand\X{\mathcal{X}}
samer@18: \newcommand\Y{\mathcal{Y}}
samer@18: \newcommand\domS{\mathcal{S}}
samer@18: \newcommand\A{\mathcal{A}}
samer@25: \newcommand\Data{\mathcal{D}}
samer@18: \newcommand\rvm[1]{\mathrm{#1}}
samer@18: \newcommand\sps{\,.\,}
samer@18: \newcommand\Ipred{\mathcal{I}_{\mathrm{pred}}}
samer@18: \newcommand\Ix{\mathcal{I}}
samer@18: \newcommand\IXZ{\overline{\underline{\mathcal{I}}}}
samer@18: \newcommand\x{\vec{x}}
samer@18: \newcommand\Ham[1]{\mathcal{H}_{#1}}
samer@18: \newcommand\subsets[2]{[#1]^{(k)}}
samer@18: \def\bet(#1,#2){#1..#2}
samer@18: 
samer@18: 
samer@18: \def\ev(#1=#2){#1\!\!=\!#2}
samer@18: \newcommand\rv[1]{\Omega \to #1}
samer@18: \newcommand\ceq{\!\!=\!}
samer@18: \newcommand\cmin{\!-\!}
samer@18: \newcommand\modulo[2]{#1\!\!\!\!\!\mod#2}
samer@18: 
samer@18: \newcommand\sumitoN{\sum_{i=1}^N}
samer@18: \newcommand\sumktoK{\sum_{k=1}^K}
samer@18: \newcommand\sumjtoK{\sum_{j=1}^K}
samer@18: \newcommand\sumalpha{\sum_{\alpha\in\A}}
samer@18: \newcommand\prodktoK{\prod_{k=1}^K}
samer@18: \newcommand\prodjtoK{\prod_{j=1}^K}
samer@18: 
samer@18: \newcommand\past[1]{\overset{\rule{0pt}{0.2em}\smash{\leftarrow}}{#1}}
samer@18: \newcommand\fut[1]{\overset{\rule{0pt}{0.1em}\smash{\rightarrow}}{#1}}
samer@18: \newcommand\parity[2]{P^{#1}_{2,#2}}
samer@4: 
samer@4: %\usepackage[parfill]{parskip}
samer@4: 
samer@4: \begin{document}
samer@41: \title{Cognitive Music Modelling: an\\Information Dynamics Approach}
samer@4: 
samer@4: \author{
hekeus@16: 	\IEEEauthorblockN{Samer A. Abdallah, Henrik Ekeus, Peter Foster}
hekeus@16: 	\IEEEauthorblockN{Andrew Robertson and Mark D. Plumbley}
samer@4: 	\IEEEauthorblockA{Centre for Digital Music\\
samer@4: 		Queen Mary University of London\\
samer@41: 		Mile End Road, London E1 4NS}}
samer@4: 
samer@4: \maketitle
samer@18: \begin{abstract}
samer@61: 	We describe an information-theoretic approach to the analysis
samer@61: 	of music and other sequential data, which emphasises the predictive aspects
samer@61: 	of perception, and the dynamic process
samer@61: 	of forming and modifying expectations about an unfolding stream of data,
samer@61: 	characterising these using the tools of information theory: entropies,
samer@61: 	mutual informations, and related quantities.
samer@61: 	After reviewing the theoretical foundations, 
samer@61: %	we present a new result on predictive information rates in high-order Markov chains, and 
samer@61: 	we discuss a few emerging areas of application, including
samer@61: 	musicological analysis, real-time beat-tracking analysis, and the generation
samer@61: 	of musical materials as a cognitively-informed compositional aid.
hekeus@16: \end{abstract}
samer@4: 
samer@4: 
samer@25: \section{Introduction}
samer@9: \label{s:Intro}
samer@56: 	The relationship between
samer@56: 	Shannon's \cite{Shannon48} information theory and music and art in general has been the
samer@56: 	subject of some interest since the 1950s 
samer@70: 	\cite{Youngblood58,CoonsKraehenbuehl1958,Moles66,Meyer67,Cohen1962}. 
samer@56: 	The general thesis is that perceptible qualities and subjective states
samer@56: 	like uncertainty, surprise, complexity, tension, and interestingness
samer@56: 	are closely related to information-theoretic quantities like
samer@56: 	entropy, relative entropy, and mutual information.
samer@56: 
samer@56: 	Music is also an inherently dynamic process, 
samer@61: 	where listeners build up expectations about what is to happen next,
samer@61: 	which may be fulfilled
samer@61: 	immediately, after some delay, or modified as the music unfolds.
samer@56: 	In this paper, we explore this ``Information Dynamics'' view of music,
samer@61: 	discussing the theory behind it and some emerging applications.
samer@9: 
samer@25: 	\subsection{Expectation and surprise in music}
samer@70: 	The idea that the musical experience is strongly shaped by the generation
samer@61: 	and playing out of strong and weak expectations was put forward by, amongst others, 
samer@61: 	music theorists L. B. Meyer \cite{Meyer67} and Narmour \citep{Narmour77}, but was
samer@18: 	recognised much earlier; for example, 
samer@9: 	it was elegantly put by Hanslick \cite{Hanslick1854} in the
samer@9: 	nineteenth century:
samer@9: 	\begin{quote}
samer@9: 			`The most important factor in the mental process which accompanies the
samer@9: 			act of listening to music, and which converts it to a source of pleasure, 
samer@18: 			is \ldots the intellectual satisfaction 
samer@9: 			which the listener derives from continually following and anticipating 
samer@9: 			the composer's intentions---now, to see his expectations fulfilled, and 
samer@18: 			now, to find himself agreeably mistaken. 
samer@18: 			%It is a matter of course that 
samer@18: 			%this intellectual flux and reflux, this perpetual giving and receiving 
samer@18: 			%takes place unconsciously, and with the rapidity of lightning-flashes.'
samer@9: 	\end{quote}
samer@9: 	An essential aspect of this is that music is experienced as a phenomenon
samer@61: 	that unfolds in time, rather than being apprehended as a static object
samer@61: 	presented in its entirety. Meyer argued that the experience depends
samer@9: 	on how we change and revise our conceptions \emph{as events happen}, on
samer@9: 	how expectation and prediction interact with occurrence, and that, to a
samer@9: 	large degree, the way to understand the effect of music is to focus on
samer@9: 	this `kinetics' of expectation and surprise.
samer@9: 
samer@25:   Prediction and expectation are essentially probabilistic concepts
samer@25:   and can be treated mathematically using probability theory.
samer@25:   We suppose that when we listen to music, expectations are created on the basis 
samer@25: 	of our familiarity with various styles of music and our ability to
samer@25: 	detect and learn statistical regularities in the music as they emerge,
samer@25: 	There is experimental evidence that human listeners are able to internalise
samer@25: 	statistical knowledge about musical structure, \eg
samer@70: %	\citep{SaffranJohnsonAslin1999,EerolaToiviainenKrumhansl2002}, and also
samer@70: 	\citep{SaffranJohnsonAslin1999}, and also
samer@25: 	that statistical models can form an effective basis for computational
samer@25: 	analysis of music, \eg
samer@25: 	\cite{ConklinWitten95,PonsfordWigginsMellish1999,Pearce2005}.
samer@25: 
samer@56: %	\subsection{Music and information theory}
samer@24: 	With a probabilistic framework for music modelling and prediction in hand,
samer@70: 	we can %are in a position to 
samer@70: 	compute various
samer@25: \comment{
samer@25: 	which provides us with a number of measures, such as entropy
samer@25:   and mutual information, which are suitable for quantifying states of
samer@25:   uncertainty and surprise, and thus could potentially enable us to build
samer@25:   quantitative models of the listening process described above.  They are
samer@25:   what Berlyne \cite{Berlyne71} called `collative variables' since they are
samer@25:   to do with patterns of occurrence rather than medium-specific details.
samer@25:   Berlyne sought to show that the collative variables are closely related to
samer@25:   perceptual qualities like complexity, tension, interestingness,
samer@25:   and even aesthetic value, not just in music, but in other temporal
samer@25:   or visual media.
samer@25:   The relevance of information theory to music and art has
samer@25:   also been addressed by researchers from the 1950s onwards
samer@25:   \cite{Youngblood58,CoonsKraehenbuehl1958,Cohen1962,HillerBean66,Moles66,Meyer67}.
samer@25: }
samer@9: 	information-theoretic quantities like entropy, relative entropy,
samer@9: 	and mutual information.
samer@9: %	and are major determinants of the overall experience.
samer@9: 	Berlyne \cite{Berlyne71} called such quantities `collative variables', since 
samer@9: 	they are to do with patterns of occurrence rather than medium-specific details,
samer@9: 	and developed the ideas of `information aesthetics' in an experimental setting.  
samer@9: %	Berlyne's `new experimental aesthetics', the `information-aestheticians'.
samer@9: 
samer@9: %	Listeners then experience greater or lesser levels of surprise
samer@9: %	in response to departures from these norms. 
samer@9: %	By careful manipulation
samer@9: %	of the material, the composer can thus define, and induce within the
samer@9: %	listener, a temporal programme of varying
samer@9: %	levels of uncertainty, ambiguity and surprise. 
samer@9: 
samer@9: 
samer@9: \subsection{Information dynamic approach}
samer@70: 	Our working hypothesis is that, as an intelligent, predictive
samer@70: 	agent (to which will refer as `it') listens to a piece of music, it maintains
samer@70: 	a dynamically evolving probabilistic belief state that enables it to make predictions
samer@24: 	about how the piece will continue, relying on both its previous experience
samer@61: 	of music and the emerging themes of the piece.  As events unfold, it revises
samer@70: 	this belief state, which includes predictive
samer@25: 	distributions over possible future events.  These 
samer@25: %	distributions and changes in distributions 
samer@25: 	can be characterised in terms of a handful of information
samer@25: 	theoretic-measures such as entropy and relative entropy.  By tracing the 
samer@24: 	evolution of a these measures, we obtain a representation which captures much
samer@25: 	of the significant structure of the music.
samer@25: 	
samer@70: 	One consequence of this approach is that regardless of the details of
samer@25: 	the sensory input or even which sensory modality is being processed, the resulting 
samer@25: 	analysis is in terms of the same units: quantities of information (bits) and
samer@61: 	rates of information flow (bits per second). The information
samer@25: 	theoretic concepts in terms of which the analysis is framed are universal to all sorts 
samer@25: 	of data.
samer@25: 	In addition, when adaptive probabilistic models are used, expectations are
samer@61: 	created mainly in response to \emph{patterns} of occurence, 
samer@25: 	rather the details of which specific things occur.
samer@25: 	Together, these suggest that an information dynamic analysis captures a
samer@25: 	high level of \emph{abstraction}, and could be used to 
samer@25: 	make structural comparisons between different temporal media,
samer@25: 	such as music, film, animation, and dance.
samer@25: %	analyse and compare information 
samer@25: %	flow in different temporal media regardless of whether they are auditory, 
samer@25: %	visual or otherwise. 
samer@9: 
samer@25: 	Another consequence is that the information dynamic approach gives us a principled way
samer@24: 	to address the notion of \emph{subjectivity}, since the analysis is dependent on the 
samer@24: 	probability model the observer starts off with, which may depend on prior experience 
samer@24: 	or other factors, and which may change over time. Thus, inter-subject variablity and 
samer@24: 	variation in subjects' responses over time are 
samer@24: 	fundamental to the theory. 
samer@9: 			
samer@18: 	%modelling the creative process, which often alternates between generative
samer@18: 	%and selective or evaluative phases \cite{Boden1990}, and would have
samer@18: 	%applications in tools for computer aided composition.
samer@18: 
samer@18: 
samer@18: \section{Theoretical review}
samer@18: 
samer@34: 	\subsection{Entropy and information}
samer@41: 	\label{s:entro-info}
samer@41: 
samer@34: 	Let $X$ denote some variable whose value is initially unknown to our 
samer@34: 	hypothetical observer. We will treat $X$ mathematically as a random variable,
samer@36: 	with a value to be drawn from some set $\X$ and a 
samer@34: 	probability distribution representing the observer's beliefs about the 
samer@34: 	true value of $X$.
samer@34: 	In this case, the observer's uncertainty about $X$ can be quantified
samer@34: 	as the entropy of the random variable $H(X)$. For a discrete variable
samer@36: 	with probability mass function $p:\X \to [0,1]$, this is
samer@34: 	\begin{equation}
samer@41: 		H(X) = \sum_{x\in\X} -p(x) \log p(x), % = \expect{-\log p(X)},
samer@34: 	\end{equation}
samer@41: %	where $\expect{}$ is the expectation operator. 
samer@41: 	The negative-log-probability
samer@34: 	$\ell(x) = -\log p(x)$ of a particular value $x$ can usefully be thought of as
samer@34: 	the \emph{surprisingness} of the value $x$ should it be observed, and
samer@61: 	hence the entropy is the expectation of the surprisingness, $\expect \ell(X)$.
samer@34: 
samer@34: 	Now suppose that the observer receives some new data $\Data$ that
samer@34: 	causes a revision of its beliefs about $X$. The \emph{information}
samer@34: 	in this new data \emph{about} $X$ can be quantified as the 
samer@61: 	relative entropy or
samer@34: 	Kullback-Leibler (KL) divergence between the prior and posterior
samer@34: 	distributions $p(x)$ and $p(x|\Data)$ respectively:
samer@34: 	\begin{equation}
samer@34: 		\mathcal{I}_{\Data\to X} = D(p_{X|\Data} || p_{X})
samer@36: 			= \sum_{x\in\X} p(x|\Data) \log \frac{p(x|\Data)}{p(x)}.
samer@41: 			\label{eq:info}
samer@34: 	\end{equation}
samer@34: 	When there are multiple variables $X_1, X_2$ 
samer@34: 	\etc which the observer believes to be dependent, then the observation of 
samer@34: 	one may change its beliefs and hence yield information about the
samer@34: 	others. The joint and conditional entropies as described in any
samer@34: 	textbook on information theory (\eg \cite{CoverThomas}) then quantify
samer@34: 	the observer's expected uncertainty about groups of variables given the
samer@34: 	values of others. In particular, the \emph{mutual information}
samer@34: 	$I(X_1;X_2)$ is both the expected information
samer@34: 	in an observation of $X_2$ about $X_1$ and the expected reduction
samer@34: 	in uncertainty about $X_1$ after observing $X_2$:
samer@34: 	\begin{equation}
samer@34: 		I(X_1;X_2) = H(X_1) - H(X_1|X_2),
samer@34: 	\end{equation}
samer@34: 	where $H(X_1|X_2) = H(X_1,X_2) - H(X_2)$ is the conditional entropy
samer@34: 	of $X_2$ given $X_1$. A little algebra shows that $I(X_1;X_2)=I(X_2;X_1)$
samer@34: 	and so the mutual information is symmetric in its arguments. A conditional
samer@34: 	form of the mutual information can be formulated analogously:
samer@34: 	\begin{equation}
samer@34: 		I(X_1;X_2|X_3) = H(X_1|X_3) - H(X_1|X_2,X_3).
samer@34: 	\end{equation}
samer@34: 	These relationships between the various entropies and mutual
samer@61: 	informations are conveniently visualised in \emph{information diagrams}
samer@34: 	or I-diagrams \cite{Yeung1991} such as the one in \figrf{venn-example}.
samer@34: 
samer@18: 	\begin{fig}{venn-example}
samer@18: 		\newcommand\rad{2.2em}%
samer@18: 		\newcommand\circo{circle (3.4em)}%
samer@18: 		\newcommand\labrad{4.3em}
samer@18: 		\newcommand\bound{(-6em,-5em) rectangle (6em,6em)}
samer@18: 		\newcommand\colsep{\ }
samer@18: 		\newcommand\clipin[1]{\clip (#1) \circo;}%
samer@18: 		\newcommand\clipout[1]{\clip \bound (#1) \circo;}%
samer@18: 		\newcommand\cliptwo[3]{%
samer@18: 			\begin{scope}
samer@18: 				\clipin{#1};
samer@18: 				\clipin{#2};
samer@18: 				\clipout{#3};
samer@18: 				\fill[black!30] \bound;
samer@18: 			\end{scope}
samer@18: 		}%
samer@18: 		\newcommand\clipone[3]{%
samer@18: 			\begin{scope}
samer@18: 				\clipin{#1};
samer@18: 				\clipout{#2};
samer@18: 				\clipout{#3};
samer@18: 				\fill[black!15] \bound;
samer@18: 			\end{scope}
samer@18: 		}%
samer@18: 		\begin{tabular}{c@{\colsep}c}
samer@18: 			\begin{tikzpicture}[baseline=0pt]
samer@18: 				\coordinate (p1) at (90:\rad);
samer@18: 				\coordinate (p2) at (210:\rad);
samer@18: 				\coordinate (p3) at (-30:\rad);
samer@18: 				\clipone{p1}{p2}{p3};
samer@18: 				\clipone{p2}{p3}{p1};
samer@18: 				\clipone{p3}{p1}{p2};
samer@18: 				\cliptwo{p1}{p2}{p3};
samer@18: 				\cliptwo{p2}{p3}{p1};
samer@18: 				\cliptwo{p3}{p1}{p2};
samer@18:             \begin{scope}
samer@18:                \clip (p1) \circo;
samer@18:                \clip (p2) \circo;
samer@18:                \clip (p3) \circo;
samer@18:                \fill[black!45] \bound;
samer@18:             \end{scope}
samer@18: 				\draw (p1) \circo;
samer@18: 				\draw (p2) \circo;
samer@18: 				\draw (p3) \circo;
samer@18: 				\path 
samer@18: 					(barycentric cs:p3=1,p1=-0.2,p2=-0.1) +(0ex,0) node {$I_{3|12}$}
samer@18: 					(barycentric cs:p1=1,p2=-0.2,p3=-0.1) +(0ex,0) node {$I_{1|23}$}
samer@18: 					(barycentric cs:p2=1,p3=-0.2,p1=-0.1) +(0ex,0) node {$I_{2|13}$}
samer@18: 					(barycentric cs:p3=1,p2=1,p1=-0.55) +(0ex,0) node {$I_{23|1}$}
samer@18: 					(barycentric cs:p1=1,p3=1,p2=-0.55) +(0ex,0) node {$I_{13|2}$}
samer@18: 					(barycentric cs:p2=1,p1=1,p3=-0.55) +(0ex,0) node {$I_{12|3}$}
samer@18: 					(barycentric cs:p3=1,p2=1,p1=1) node {$I_{123}$}
samer@18: 					;
samer@18: 				\path
samer@18: 					(p1) +(140:\labrad) node {$X_1$}
samer@18: 					(p2) +(-140:\labrad) node {$X_2$}
samer@18: 					(p3) +(-40:\labrad) node {$X_3$};
samer@18: 			\end{tikzpicture}
samer@18: 			&
samer@18: 			\parbox{0.5\linewidth}{
samer@18: 				\small
samer@18: 				\begin{align*}
samer@18: 					I_{1|23} &= H(X_1|X_2,X_3) \\
samer@18: 					I_{13|2} &= I(X_1;X_3|X_2) \\
samer@18: 					I_{1|23} + I_{13|2} &= H(X_1|X_2) \\
samer@18: 					I_{12|3} + I_{123} &= I(X_1;X_2) 
samer@18: 				\end{align*}
samer@18: 			}
samer@18: 		\end{tabular}
samer@18: 		\caption{
samer@61: 		I-diagram of entropies and mutual informations
samer@18: 		for three random variables $X_1$, $X_2$ and $X_3$. The areas of 
samer@18: 		the three circles represent $H(X_1)$, $H(X_2)$ and $H(X_3)$ respectively.
samer@18: 		The total shaded area is the joint entropy $H(X_1,X_2,X_3)$.
samer@18: 		The central area $I_{123}$ is the co-information \cite{McGill1954}.
samer@18: 		Some other information measures are indicated in the legend.
samer@18: 		}
samer@18: 	\end{fig}
samer@30: 
samer@30: 
samer@36: 	\subsection{Surprise and information in sequences}
samer@36: 	\label{s:surprise-info-seq}
samer@30: 
samer@36: 	Suppose that  $(\ldots,X_{-1},X_0,X_1,\ldots)$ is a sequence of
samer@30: 	random variables, infinite in both directions, 
samer@36: 	and that $\mu$ is the associated probability measure over all 
samer@61: 	realisations of the sequence. In the following, $\mu$ will simply serve
samer@30: 	as a label for the process. We can indentify a number of information-theoretic
samer@30: 	measures meaningful in the context of a sequential observation of the sequence, during
samer@61: 	which, at any time $t$, the sequence can be divided into a `present' $X_t$, a `past' 
samer@30: 	$\past{X}_t \equiv (\ldots, X_{t-2}, X_{t-1})$, and a `future' 
samer@30: 	$\fut{X}_t \equiv (X_{t+1},X_{t+2},\ldots)$.
samer@41: 	We will write the actually observed value of $X_t$ as $x_t$, and
samer@36: 	the sequence of observations up to but not including $x_t$ as 
samer@36: 	$\past{x}_t$.
samer@36: %	Since the sequence is assumed stationary, we can without loss of generality,
samer@36: %	assume that $t=0$ in the following definitions.
samer@36: 
samer@41: 	The in-context surprisingness of the observation $X_t=x_t$ depends on 
samer@41: 	both $x_t$ and the context $\past{x}_t$:
samer@36: 	\begin{equation}
samer@41: 		\ell_t = - \log p(x_t|\past{x}_t).
samer@36: 	\end{equation}
samer@61: 	However, before $X_t$ is observed, the observer can compute
samer@46: 	the \emph{expected} surprisingness as a measure of its uncertainty about
samer@61: 	$X_t$; this may be written as an entropy 
samer@36: 	$H(X_t|\ev(\past{X}_t = \past{x}_t))$, but note that this is
samer@61: 	conditional on the \emph{event} $\ev(\past{X}_t=\past{x}_t)$, not the
samer@36: 	\emph{variables} $\past{X}_t$ as in the conventional conditional entropy.
samer@36: 
samer@41: 	The surprisingness $\ell_t$ and expected surprisingness
samer@36: 	$H(X_t|\ev(\past{X}_t=\past{x}_t))$
samer@41: 	can be understood as \emph{subjective} information dynamic measures, since they are 
samer@41: 	based on the observer's probability model in the context of the actually observed sequence
samer@61: 	$\past{x}_t$. They characterise what it is like to be `in the observer's shoes'.
samer@36: 	If we view the observer as a purely passive or reactive agent, this would
samer@36: 	probably be sufficient, but for active agents such as humans or animals, it is
samer@36: 	often necessary to \emph{aniticipate} future events in order, for example, to plan the
samer@36: 	most effective course of action. It makes sense for such observers to be
samer@36: 	concerned about the predictive probability distribution over future events,
samer@36: 	$p(\fut{x}_t|\past{x}_t)$. When an observation $\ev(X_t=x_t)$ is made in this context,
samer@41: 	the \emph{instantaneous predictive information} (IPI) $\mathcal{I}_t$ at time $t$
samer@41: 	is the information in the event $\ev(X_t=x_t)$ about the entire future of the sequence $\fut{X}_t$,
samer@41: 	\emph{given} the observed past $\past{X}_t=\past{x}_t$.
samer@41: 	Referring to the definition of information \eqrf{info}, this is the KL divergence
samer@41: 	between prior and posterior distributions over possible futures, which written out in full, is
samer@41: 	\begin{equation}
samer@41: 		\mathcal{I}_t = \sum_{\fut{x}_t \in \X^*} 
samer@41: 					p(\fut{x}_t|x_t,\past{x}_t) \log \frac{ p(\fut{x}_t|x_t,\past{x}_t) }{ p(\fut{x}_t|\past{x}_t) },
samer@41: 	\end{equation}
samer@41: 	where the sum is to be taken over the set of infinite sequences $\X^*$.
samer@46: 	Note that it is quite possible for an event to be surprising but not informative
samer@70: 	in a predictive sense.
samer@41: 	As with the surprisingness, the observer can compute its \emph{expected} IPI
samer@41: 	at time $t$, which reduces to a mutual information $I(X_t;\fut{X}_t|\ev(\past{X}_t=\past{x}_t))$
samer@41: 	conditioned on the observed past. This could be used, for example, as an estimate
samer@41: 	of attentional resources which should be directed at this stream of data, which may
samer@41: 	be in competition with other sensory streams.
samer@36: 
samer@36: 	\subsection{Information measures for stationary random processes}
samer@43: 	\label{s:process-info}
samer@30: 
samer@18: 
samer@18:  	\begin{fig}{predinfo-bg}
samer@18: 		\newcommand\subfig[2]{\shortstack{#2\\[0.75em]#1}}
samer@18: 		\newcommand\rad{1.8em}%
samer@18: 		\newcommand\ovoid[1]{%
samer@18: 			++(-#1,\rad) 
samer@18: 			-- ++(2 * #1,0em) arc (90:-90:\rad)
samer@18:  			-- ++(-2 * #1,0em) arc (270:90:\rad) 
samer@18: 		}%
samer@18: 		\newcommand\axis{2.75em}%
samer@18: 		\newcommand\olap{0.85em}%
samer@18: 		\newcommand\offs{3.6em}
samer@18: 		\newcommand\colsep{\hspace{5em}}
samer@18: 		\newcommand\longblob{\ovoid{\axis}}
samer@18: 		\newcommand\shortblob{\ovoid{1.75em}}
samer@56: 		\begin{tabular}{c}
samer@43: 			\subfig{(a) multi-information and entropy rates}{%
samer@43: 				\begin{tikzpicture}%[baseline=-1em]
samer@43: 					\newcommand\rc{1.75em}
samer@43: 					\newcommand\throw{2.5em}
samer@43: 					\coordinate (p1) at (180:1.5em);
samer@43: 					\coordinate (p2) at (0:0.3em);
samer@43: 					\newcommand\bound{(-7em,-2.6em) rectangle (7em,3.0em)}
samer@43: 					\newcommand\present{(p2) circle (\rc)}
samer@43: 					\newcommand\thepast{(p1) ++(-\throw,0) \ovoid{\throw}}
samer@43: 					\newcommand\fillclipped[2]{%
samer@43: 						\begin{scope}[even odd rule]
samer@43: 							\foreach \thing in {#2} {\clip \thing;}
samer@43: 							\fill[black!#1] \bound;
samer@43: 						\end{scope}%
samer@43: 					}%
samer@43: 					\fillclipped{30}{\present,\bound \thepast}
samer@43: 					\fillclipped{15}{\present,\bound \thepast}
samer@43: 					\fillclipped{45}{\present,\thepast}
samer@43: 					\draw \thepast;
samer@43: 					\draw \present;
samer@43: 					\node at (barycentric cs:p2=1,p1=-0.3) {$h_\mu$};
samer@43: 					\node at (barycentric cs:p2=1,p1=1) [shape=rectangle,fill=black!45,inner sep=1pt]{$\rho_\mu$};
samer@43: 					\path (p2) +(90:3em) node {$X_0$};
samer@43: 					\path (p1) +(-3em,0em) node  {\shortstack{infinite\\past}};
samer@43: 					\path (p1) +(-4em,\rad) node [anchor=south] {$\ldots,X_{-1}$};
samer@43: 				\end{tikzpicture}}%
samer@70: 			\\[1em]
samer@43: 			\subfig{(b) excess entropy}{%
samer@18: 				\newcommand\blob{\longblob}
samer@18: 				\begin{tikzpicture}
samer@18: 					\coordinate (p1) at (-\offs,0em);
samer@18: 					\coordinate (p2) at (\offs,0em);
samer@18: 					\begin{scope}
samer@18: 						\clip (p1) \blob;
samer@18: 						\clip (p2) \blob;
samer@18: 						\fill[lightgray] (-1,-1) rectangle (1,1);
samer@18: 					\end{scope}
samer@18: 					\draw (p1) +(-0.5em,0em) node{\shortstack{infinite\\past}} \blob;
samer@18: 					\draw (p2) +(0.5em,0em) node{\shortstack{infinite\\future}} \blob;
samer@18: 					\path (0,0) node (future) {$E$};
samer@18: 					\path (p1) +(-2em,\rad) node [anchor=south] {$\ldots,X_{-1}$};
samer@18: 					\path (p2) +(2em,\rad) node [anchor=south] {$X_0,\ldots$};
samer@18: 				\end{tikzpicture}%
samer@18: 			}%
samer@70: 			\\[1em]
samer@43: 			\subfig{(c) predictive information rate $b_\mu$}{%
samer@18: 				\begin{tikzpicture}%[baseline=-1em]
samer@18: 					\newcommand\rc{2.1em}
samer@18: 					\newcommand\throw{2.5em}
samer@18: 					\coordinate (p1) at (210:1.5em);
samer@18: 					\coordinate (p2) at (90:0.7em);
samer@18: 					\coordinate (p3) at (-30:1.5em);
samer@18: 					\newcommand\bound{(-7em,-2.6em) rectangle (7em,3.0em)}
samer@18: 					\newcommand\present{(p2) circle (\rc)}
samer@18: 					\newcommand\thepast{(p1) ++(-\throw,0) \ovoid{\throw}}
samer@18: 					\newcommand\future{(p3) ++(\throw,0) \ovoid{\throw}}
samer@18: 					\newcommand\fillclipped[2]{%
samer@18: 						\begin{scope}[even odd rule]
samer@18: 							\foreach \thing in {#2} {\clip \thing;}
samer@18: 							\fill[black!#1] \bound;
samer@18: 						\end{scope}%
samer@18: 					}%
samer@43: 					\fillclipped{80}{\future,\thepast}
samer@18: 					\fillclipped{30}{\present,\future,\bound \thepast}
samer@18: 					\fillclipped{15}{\present,\bound \future,\bound \thepast}
samer@18: 					\draw \future;
samer@18: 					\fillclipped{45}{\present,\thepast}
samer@18: 					\draw \thepast;
samer@18: 					\draw \present;
samer@18: 					\node at (barycentric cs:p2=1,p1=-0.17,p3=-0.17) {$r_\mu$};
samer@18: 					\node at (barycentric cs:p1=-0.4,p2=1.0,p3=1) {$b_\mu$};
samer@18: 					\node at (barycentric cs:p3=0,p2=1,p1=1.2) [shape=rectangle,fill=black!45,inner sep=1pt]{$\rho_\mu$};
samer@18: 					\path (p2) +(140:3em) node {$X_0$};
samer@18: 	%            \node at (barycentric cs:p3=0,p2=1,p1=1) {$\rho_\mu$};
samer@18: 					\path (p3) +(3em,0em) node  {\shortstack{infinite\\future}};
samer@18: 					\path (p1) +(-3em,0em) node  {\shortstack{infinite\\past}};
samer@18: 					\path (p1) +(-4em,\rad) node [anchor=south] {$\ldots,X_{-1}$};
samer@18: 					\path (p3) +(4em,\rad) node [anchor=south] {$X_1,\ldots$};
samer@18: 				\end{tikzpicture}}%
samer@70: 				\\[0.25em]
samer@18: 		\end{tabular}
samer@18: 		\caption{
samer@30: 		I-diagrams for several information measures in
samer@18: 		stationary random processes. Each circle or oval represents a random
samer@18: 		variable or sequence of random variables relative to time $t=0$. Overlapped areas
samer@61: 		correspond to various mutual informations.
samer@61: 		In (a) and (c), the circle represents the `present'. Its total area is
samer@33: 		$H(X_0)=\rho_\mu+r_\mu+b_\mu$, where $\rho_\mu$ is the multi-information
samer@18: 		rate, $r_\mu$ is the residual entropy rate, and $b_\mu$ is the predictive
samer@43: 		information rate. The entropy rate is $h_\mu = r_\mu+b_\mu$. The small dark
samer@43: 		region  below $X_0$ in (c) is $\sigma_\mu = E-\rho_\mu$.
samer@18: 		}
samer@18: 	\end{fig}
samer@18: 
samer@41: 	If we step back, out of the observer's shoes as it were, and consider the
samer@41: 	random process $(\ldots,X_{-1},X_0,X_1,\dots)$ as a statistical ensemble of 
samer@41: 	possible realisations, and furthermore assume that it is stationary,
samer@41: 	then it becomes possible to define a number of information-theoretic measures,
samer@41: 	closely related to those described above, but which characterise the
samer@41: 	process as a whole, rather than on a moment-by-moment basis. Some of these,
samer@41: 	such as the entropy rate, are well-known, but others are only recently being
samer@41: 	investigated. (In the following, the assumption of stationarity means that
samer@41: 	the measures defined below are independent of $t$.)
samer@41: 
samer@61: 	The \emph{entropy rate} of the process is the entropy of the `present'
samer@61: 	$X_t$ given the `past':
samer@41: 	\begin{equation}
samer@41: 		\label{eq:entro-rate}
samer@41: 		h_\mu = H(X_t|\past{X}_t).
samer@41: 	\end{equation}
samer@51: 	The entropy rate is a measure of the overall surprisingness
samer@51: 	or unpredictability of the process, and gives an indication of the average
samer@51: 	level of surprise and uncertainty that would be experienced by an observer
samer@61: 	computing the measures of \secrf{surprise-info-seq} on a sequence sampled 
samer@61: 	from the process.
samer@41: 
samer@41: 	The \emph{multi-information rate} $\rho_\mu$ (following Dubnov's \cite{Dubnov2006}
samer@41: 	notation for what he called the `information rate') is the mutual
samer@41: 	information between the `past' and the `present':
samer@41: 	\begin{equation}
samer@41: 		\label{eq:multi-info}
samer@41: 			\rho_\mu = I(\past{X}_t;X_t) = H(X_t) - h_\mu.
samer@41: 	\end{equation}
samer@61: 	It is a measure of how much the preceeding context of an observation 
samer@61: 	helps in predicting or reducing the suprisingness of the current observation.
samer@41: 
samer@41: 	The \emph{excess entropy} \cite{CrutchfieldPackard1983} 
samer@41: 	is the mutual information between 
samer@41: 	the entire `past' and the entire `future':
samer@41: 	\begin{equation}
samer@41: 		E = I(\past{X}_t; X_t,\fut{X}_t).
samer@41: 	\end{equation}
samer@43: 	Both the excess entropy and the multi-information rate can be thought
samer@43: 	of as measures of \emph{redundancy}, quantifying the extent to which 
samer@43: 	the same information is to be found in all parts of the sequence.
samer@41: 	
samer@41: 
samer@30: 	The \emph{predictive information rate} (or PIR) \cite{AbdallahPlumbley2009}  
samer@61: 	is the mutual information between the `present' and the `future' given the 
samer@61: 	`past':
samer@18: 	\begin{equation}
samer@18: 		\label{eq:PIR}
samer@61: 		b_\mu = I(X_t;\fut{X}_t|\past{X}_t) = H(\fut{X}_t|\past{X}_t) - H(\fut{X}_t|X_t,\past{X}_t),
samer@18: 	\end{equation}
samer@61: 	which can be read as the average reduction
samer@18: 	in uncertainty about the future on learning $X_t$, given the past. 
samer@18: 	Due to the symmetry of the mutual information, it can also be written
samer@18: 	as 
samer@18: 	\begin{equation}
samer@18: %		\IXZ_t 
samer@43: b_\mu = H(X_t|\past{X}_t) - H(X_t|\past{X}_t,\fut{X}_t) = h_\mu - r_\mu,
samer@18: %		\label{<++>}
samer@18: 	\end{equation}
samer@18: %	If $X$ is stationary, then 
samer@41: 	where $r_\mu = H(X_t|\fut{X}_t,\past{X}_t)$, 
samer@34: 	is the \emph{residual} \cite{AbdallahPlumbley2010},
samer@34: 	or \emph{erasure} \cite{VerduWeissman2006} entropy rate.
samer@18: 	These relationships are illustrated in \Figrf{predinfo-bg}, along with
samer@18: 	several of the information measures we have discussed so far.
samer@51: 	The PIR gives an indication of the average IPI that would be experienced
samer@51: 	by an observer processing a sequence sampled from this process.
samer@18: 
samer@18: 
samer@46: 	James et al \cite{JamesEllisonCrutchfield2011} review several of these
samer@46: 	information measures and introduce some new related ones.
samer@46: 	In particular they identify the $\sigma_\mu = I(\past{X}_t;\fut{X}_t|X_t)$, 
samer@46: 	the mutual information between the past and the future given the present,
samer@46: 	as an interesting quantity that measures the predictive benefit of
samer@61: 	model-building, that is, maintaining an internal state summarising past 
samer@61: 	observations in order to make better predictions. It is shown as the
samer@46: 	small dark region below the circle in \figrf{predinfo-bg}(c).
samer@46: 	By comparing with \figrf{predinfo-bg}(b), we can see that 
samer@46: 	$\sigma_\mu = E - \rho_\mu$.
samer@43: %	They also identify
samer@43: %	$w_\mu = \rho_\mu + b_{\mu}$, which they call the \emph{local exogenous
samer@43: %	information} rate.
samer@34: 
samer@4: 
samer@36: 	\subsection{First and higher order Markov chains}
samer@53: 	\label{s:markov}
samer@70: %	First order Markov chains are the simplest non-trivial models to which information 
samer@70: %	dynamics methods can be applied. 
samer@70: 	In \cite{AbdallahPlumbley2009} we derived
samer@41: 	expressions for all the information measures described in \secrf{surprise-info-seq} for
samer@70: 	ergodic first order Markov chains (\ie that have a unique stationary
samer@61: 	distribution). 
samer@61: %	The derivation is greatly simplified by the dependency structure
samer@61: %	of the Markov chain: for the purpose of the analysis, the `past' and `future'
samer@61: %	segments $\past{X}_t$ and $\fut{X}_t$ can be collapsed to just the previous
samer@61: %	and next variables $X_{t-1}$ and $X_{t+1}$ respectively. 
samer@61: 	We also showed that 
samer@70: 	the PIR can be expressed simply in terms of entropy rates:
samer@36: 	if we let $a$ denote the $K\times K$ transition matrix of a Markov chain over
samer@36: 	an alphabet of $\{1,\ldots,K\}$, such that
samer@61: 	$a_{ij} = \Pr(\ev(X_t=i|\ev(X_{t-1}=j)))$, and let $h:\reals^{K\times K}\to \reals$ be
samer@36: 	the entropy rate function such that $h(a)$ is the entropy rate of a Markov chain
samer@70: 	with transition matrix $a$, then the PIR is
samer@36: 	\begin{equation}
samer@61: 		b_\mu = h(a^2) - h(a),
samer@36: 	\end{equation}
samer@36: 	where $a^2$, the transition matrix squared, is the transition matrix
samer@36: 	of the `skip one' Markov chain obtained by jumping two steps at a time
samer@36: 	along the original chain.
samer@36: 
samer@36: 	Second and higher order Markov chains can be treated in a similar way by transforming
samer@70: 	to a first order representation of the high order Markov chain. With 
samer@70: 	an $N$th order model, this is done by forming a new alphabet of size $K^N$
samer@41: 	consisting of all possible $N$-tuples of symbols from the base alphabet. 
samer@41: 	An observation $\hat{x}_t$ in this new model encodes a block of $N$ observations 
samer@70: 	$(x_{t+1},\ldots,x_{t+N})$ from the base model. 
samer@70: %	The next
samer@70: %	observation $\hat{x}_{t+1}$ encodes the block of $N$ obtained by shifting the previous 
samer@70: %	block along by one step. 
samer@70: 	The new Markov of chain is parameterised by a sparse $K^N\times K^N$
samer@66: 	transition matrix $\hat{a}$, in terms of which the PIR is
samer@36: 	\begin{equation}
samer@41: 		h_\mu = h(\hat{a}), \qquad b_\mu = h({\hat{a}^{N+1}}) - N h({\hat{a}}),
samer@36: 	\end{equation}
samer@36: 	where $\hat{a}^{N+1}$ is the $(N+1)$th power of the first order transition matrix.  
samer@41: 	Other information measures can also be computed for the high-order Markov chain, including
samer@70: 	the multi-information rate $\rho_\mu$ and the excess entropy $E$. (These are identical
samer@41: 	for first order Markov chains, but for order $N$ chains, $E$ can be up to $N$ times larger 
samer@70: 	than $\rho_\mu$.)
samer@43: 
samer@70: 	In our experiments with visualising and sonifying sequences sampled from
samer@61: 	first order Markov chains \cite{AbdallahPlumbley2009}, we found that
samer@70: 	the measures $h_\mu$, $\rho_\mu$ and $b_\mu$ correspond to perceptible
samer@70: 	characteristics, and that the transition matrices maximising or minimising
samer@61: 	each of these quantities are quite distinct. High entropy rates are associated
samer@70: 	with completely uncorrelated sequences with no recognisable temporal structure
samer@70: 	(and low $\rho_\mu$ and $b_\mu$). 
samer@70: 	High values of $\rho_\mu$ are associated with long periodic cycles (and low $h_\mu$
samer@70: 	and $b_\mu$). High values of $b_\mu$ are associated with intermediate values
samer@61: 	of $\rho_\mu$ and $h_\mu$, and recognisable, but not completely predictable,
samer@61: 	temporal structures. These relationships are visible in \figrf{mtriscat} in
samer@70: 	\secrf{composition}, where we pick up this thread again, with an application of 
samer@61: 	information dynamics in a compositional aid.
samer@36: 		
samer@36: 
hekeus@16: \section{Information Dynamics in Analysis}
samer@4: 
samer@70:  	\subsection{Musicological Analysis}
samer@70: 	\label{s:minimusic}
samer@70: 
samer@24:     \begin{fig}{twopages}
samer@70:       \colfig[0.96]{matbase/fig9471}\\  % update from mbc paper
samer@33: %      \colfig[0.97]{matbase/fig72663}\\  % later update from mbc paper (Keith's new picks)
samer@70: 			\vspace*{0.5em}
samer@24:       \colfig[0.97]{matbase/fig13377}  % rule based analysis
samer@24:       \caption{Analysis of \emph{Two Pages}.
samer@24:       The thick vertical lines are the part boundaries as indicated in
samer@24:       the score by the composer.
samer@24:       The thin grey lines
samer@24:       indicate changes in the melodic `figures' of which the piece is
samer@24:       constructed. In the `model information rate' panel, the black asterisks
samer@70:       mark the six most surprising moments selected by Keith Potter.
samer@70:       The bottom two panels show two rule-based boundary strength analyses.
samer@70:       All information measures are in nats.
samer@70: 	Note that the boundary marked in the score at around note 5,400 is known to be
samer@70: 	anomalous; on the basis of a listening analysis, some musicologists have
samer@70: 	placed the boundary a few bars later, in agreement with our analysis
samer@70: 	\cite{PotterEtAl2007}.
samer@24:       }
samer@24:     \end{fig}
samer@24: 
samer@70: 	In \cite{AbdallahPlumbley2009}, we analysed two pieces of music in the minimalist style 
samer@36: 	by Philip Glass: \emph{Two Pages} (1969) and \emph{Gradus} (1968).
samer@36: 	The analysis was done using a first-order Markov chain model, with the
samer@36: 	enhancement that the transition matrix of the model was allowed to
samer@36: 	evolve dynamically as the notes were processed, and was tracked (in
samer@36: 	a Bayesian way) as a \emph{distribution} over possible transition matrices,
samer@61: 	rather than a point estimate. Some results are summarised in \figrf{twopages}:
samer@36: 	the  upper four plots show the dynamically evolving subjective information
samer@70: 	measures as described in \secrf{surprise-info-seq}, computed using a point
samer@61: 	estimate of the current transition matrix; the fifth plot (the `model information rate')
samer@70: 	shows the information in each observation about the transition matrix.
samer@36: 	In \cite{AbdallahPlumbley2010b}, we showed that this `model information rate'
samer@61: 	is actually a component of the true IPI when the transition
samer@61: 	matrix is being learned online, and was neglected when we computed the IPI from
samer@70: 	the transition matrix as if it were a constant.
samer@36: 
samer@70: 	The peaks of the surprisingness and both components of the IPI 
samer@36: 	show good correspondence with structure of the piece both as marked in the score
samer@36: 	and as analysed by musicologist Keith Potter, who was asked to mark the six
samer@70: 	`most surprising moments' of the piece (shown as asterisks in the fifth plot). %%
samer@70: %	\footnote{%
samer@70: %	Note that the boundary marked in the score at around note 5,400 is known to be
samer@70: %	anomalous; on the basis of a listening analysis, some musicologists have
samer@70: %	placed the boundary a few bars later, in agreement with our analysis
samer@70: %	\cite{PotterEtAl2007}.}
samer@70: %
samer@36: 	In contrast, the analyses shown in the lower two plots of \figrf{twopages},
samer@36: 	obtained using two rule-based music segmentation algorithms, while clearly
samer@37: 	\emph{reflecting} the structure of the piece, do not \emph{segment} the piece,
samer@37: 	with no tendency to peaking of the boundary strength function at
samer@36: 	the boundaries in the piece.
samer@36: 	
samer@46: 	The complete analysis of \emph{Gradus} can be found in \cite{AbdallahPlumbley2009},
samer@46: 	but \figrf{metre} illustrates the result of a metrical analysis: the piece was divided
samer@46: 	into bars of 32, 64 and 128 notes. In each case, the average surprisingness and
samer@46: 	IPI for the first, second, third \etc notes in each bar were computed. The plots
samer@46: 	show that the first note of each bar is, on average, significantly more surprising
samer@46: 	and informative than the others, up to the 64-note level, where as at the 128-note,
samer@46: 	level, the dominant periodicity appears to remain at 64 notes.
samer@36: 
samer@24:     \begin{fig}{metre}
samer@70: %      \scalebox{1}{%
samer@24:         \begin{tabular}{cc}
samer@33:        \colfig[0.45]{matbase/fig36859} & \colfig[0.48]{matbase/fig88658} \\
samer@33:        \colfig[0.45]{matbase/fig48061} & \colfig[0.48]{matbase/fig46367} \\
samer@33:        \colfig[0.45]{matbase/fig99042} & \colfig[0.47]{matbase/fig87490} 
samer@24: %				\colfig[0.46]{matbase/fig56807} & \colfig[0.48]{matbase/fig27144} \\
samer@24: %				\colfig[0.46]{matbase/fig87574} & \colfig[0.48]{matbase/fig13651} \\
samer@24: %				\colfig[0.44]{matbase/fig19913} & \colfig[0.46]{matbase/fig66144} \\
samer@24: %        \colfig[0.48]{matbase/fig73098} & \colfig[0.48]{matbase/fig57141} \\
samer@24: %       \colfig[0.48]{matbase/fig25703} & \colfig[0.48]{matbase/fig72080} \\
samer@24: %        \colfig[0.48]{matbase/fig9142}  & \colfig[0.48]{matbase/fig27751}
samer@24:  
samer@24:         \end{tabular}%
samer@33: %     }
samer@24:       \caption{Metrical analysis by computing average surprisingness and
samer@70:       IPI of notes at different periodicities (\ie hypothetical
samer@24:       bar lengths) and phases (\ie positions within a bar).
samer@24:       }
samer@24:     \end{fig}
samer@24: 
samer@64:     \subsection{Real-valued signals and audio analysis}
samer@64: 	 Using analogous definitions based on the differential entropy
samer@64: 	 \cite{CoverThomas}, the methods outlined
samer@64: 	 in \secrf{surprise-info-seq} and \secrf{process-info}
samer@70: 	 can be reformulated for random variables taking values in a continuous domain.
samer@70: 	 Information-dynamic methods may thus be applied to expressive parameters of music
samer@70: 	 such as dynamics, timing and timbre, which are readily quantified on a continuous scale.
samer@70: 	
samer@65: %    \subsection{Audio based content analysis}
samer@65: %    Using analogous definitions of differential entropy, the methods outlined
samer@65: %     in the previous section are equally applicable to continuous random variables.
samer@65: %     In the case of music, where expressive properties such as dynamics, tempo,
samer@65: %     timing and timbre are readily quantified on a continuous scale, the information
samer@65: %     dynamic framework may also be considered.
peterf@39: 
samer@64: 	 Dubnov \cite{Dubnov2006} considers the class of stationary Gaussian
samer@70: 	 processes, for which entropy rate may be obtained analytically
samer@64: 	 from the power spectral density of the signal. Dubnov found that the
samer@64: 	 multi-information rate (which he refers to as `information rate') can be
samer@70: 	 expressed as a function of the \emph{spectral flatness measure}. Thus, for a given variance,
samer@64: 	 Gaussian processes with maximal multi-information rate are those with maximally
samer@70: 	 non-flat spectra. These essentially consist of a single
samer@70: 	 sinusoidal component and hence are completely predictable once
samer@64: 	 the parameters of the sinusoid have been inferred.
samer@62: %	 Local stationarity is assumed, which may be achieved by windowing or 
samer@62: %	 change point detection \cite{Dubnov2008}. 
samer@62: 	 %TODO
samer@62: 
samer@64: 	 We are currently working towards methods for the computation of predictive information
samer@64: 	 rate in some restricted classes of Gaussian processes including finite-order
samer@70: 	 autoregressive models and processes with power-law (or $1/f$) spectra,
samer@70: 	 which have previously been investegated in relation to their aesthetic properties 
samer@70: 	 \cite{Voss75,TaylorSpeharVan-Donkelaar2011}.
peterf@69: 	 
samer@70: %	(fractionally integrated Gaussian noise).
peterf@69: %	 %(fBm (continuous), fiGn discrete time) possible reference:
peterf@69: %			@book{palma2007long,
peterf@69: %		  title={Long-memory time series: theory and methods},
peterf@69: %		  author={Palma, W.},
peterf@69: %		  volume={662},
peterf@69: %		  year={2007},
peterf@69: %		  publisher={Wiley-Blackwell}
peterf@69: %	}
peterf@69: 
peterf@69: 
samer@64: 
samer@64: %	 mention non-gaussian processes extension Similarly, the predictive information
samer@64: %	 rate may be computed using a Gaussian linear formulation CITE. In this view,
samer@64: %	 the PIR is a function of the correlation  between random innovations supplied
samer@64: %	 to the stochastic process.  %Dubnov, MacAdams, Reynolds (2006) %Bailes and Dean (2009)
samer@64: 
samer@65: %     In \cite{Dubnov2006}, Dubnov considers the class of stationary Gaussian
samer@65: %     processes. For such processes, the entropy rate may be obtained analytically
samer@65: %     from the power spectral density of the signal, allowing the multi-information
samer@65: %     rate to be subsequently obtained. One aspect demanding further investigation
samer@65: %     involves the comparison of alternative measures of predictability. In the case of the PIR, a Gaussian linear formulation is applicable, indicating that the PIR is a function of the correlation  between random innovations supplied to the stochastic process CITE.
peterf@63:     % !!! FIXME
peterf@26: 
samer@4: 
samer@4: \subsection{Beat Tracking}
samer@4: 
samer@43: A probabilistic method for drum tracking was presented by Robertson 
samer@70: \cite{Robertson11c}. The system infers a beat grid (a sequence
samer@70: of approximately regular beat times) given audio inputs from a 
samer@70: live drummer, for the purpose of synchronising a music 
samer@70: sequencer with the drummer. 
samer@70: The times of kick and snare drum events are obtained
samer@70: using dedicated microphones for each drum and a percussive onset detector 
samer@70: \cite{puckette98}. These event times are then sent
samer@70: to the beat tracker, which maintains a probabilistic belief state in
samer@70: the form of distributions over the tempo and phase of the beat grid.
samer@70: Every time an event is received, these distributions are updated
samer@70: with respect to a probabilistic model which accounts both for tempo and phase 
samer@70: variations and the emission of drum events at musically plausible times
samer@70: relative to the beat grid.
samer@70: %continually updates distributions for tempo and phase on receiving a new 
samer@70: %event time
samer@43: 
samer@70: The use of a probabilistic belief state means we can compute entropies
samer@70: representing the system's uncertainty about the beat grid, and quantify
samer@70: the amount of information in each event about the beat grid as the KL divergence
samer@70: between prior and posterior distributions. Though this is not strictly the
samer@70: instantaneous predictive information (IPI) as described in \secrf{surprise-info-seq}
samer@70: (the information gained is not directly about future event times), we can treat
samer@70: it as a proxy for the IPI, in the manner of the `model information rate'
samer@70: described in \secrf{minimusic}, which has a similar status.
samer@43: 
samer@70: \begin{fig*}{drumfig}
samer@70: %	\includegraphics[width=0.9\linewidth]{drum_plots/file9-track.eps}% \\
samer@72: 	\includegraphics[width=0.97\linewidth]{figs/file11-track.eps} \\
samer@70: %	\includegraphics[width=0.9\linewidth]{newplots/file8-track.eps}
samer@70: 	\caption{Information dynamic analysis derived from audio recordings of
samer@70: 	drumming, obtained by applying a Bayesian beat tracking system to the
samer@70: 	sequence of detected kick and snare drum events. The grey line show the system's
samer@70: 	varying level of uncertainty (entropy) about the tempo and phase of the 
samer@70: 	beat grid, while the stem plot shows the amount of information in each
samer@70: 	drum event about the beat grid. The entropy drops instantaneously at each
samer@70: 	event and rises gradually between events.
samer@70: 	}
samer@70: \end{fig*}
samer@70: 
samer@70: We carried out the analysis on 16 recordings; an example
samer@70: is shown in \figrf{drumfig}. There we can see variations in the
samer@70: entropy in the upper graph and the information in each drum event in the lower
samer@70: stem plot. At certain points in time, unusually large amounts of information
samer@70: arrive; these may be related to fills and other rhythmic irregularities, which
samer@70: are often followed by an emphatic return to a steady beat at the beginning
samer@70: of the next bar---this is something we are currently investigating. 
samer@70: We also analysed the pattern of information flow
samer@70: on a cyclic metre, much as in \figrf{metre}. All the recordings we
samer@70: analysed are audibly in 4/4 metre, but we found no
samer@70: evidence of a general tendency for greater amounts of information to arrive
samer@70: at metrically strong beats, which suggests that the rhythmic accuracy of the
samer@70: drummers does not vary systematically across each bar. It is possible that metrical information 
samer@70: existing  in the pattern of kick and snare events might emerge in an information
samer@70: dynamic analysis using a model that attempts to predict the time and type of
samer@70: the next drum event, rather than just inferring the beat grid as the current model does.
samer@70: %The analysis of information rates can b
samer@70: %considered \emph{subjective}, in that it measures how the drum tracker's 
samer@70: %probability distributions change, and these are contingent upon the 
samer@70: %model used as well as external properties in the signal.
samer@70: %We expect, 
samer@70: %however, that following periods of increased uncertainty, such as fills 
samer@70: %or expressive timing, the information contained in an individual event 
samer@70: %increases. We also examine whether the information is dependent upon 
samer@70: %metrical position.
samer@70: 
samer@4: 
samer@24: \section{Information dynamics as compositional aid}
samer@43: \label{s:composition}
samer@43: 
samer@53: The use of stochastic processes in music composition has been widespread for
samer@53: decades---for instance Iannis Xenakis applied probabilistic mathematical models
samer@53: to the creation of musical materials\cite{Xenakis:1992ul}. While such processes
samer@53: can drive the \emph{generative} phase of the creative process, information dynamics
samer@53: can serve as a novel framework for a \emph{selective} phase, by 
samer@53: providing a set of criteria to be used in judging which of the 
samer@53: generated materials
samer@53: are of value. This alternation of generative and selective phases as been
samer@70: noted before \cite{Boden1990}.
samer@70: %
samer@53: Information-dynamic criteria can also be used as \emph{constraints} on the
samer@53: generative processes, for example, by specifying a certain temporal profile
samer@53: of suprisingness and uncertainty the composer wishes to induce in the listener
samer@53: as the piece unfolds.
samer@53: %stochastic and algorithmic processes: ; outputs can be filtered to match a set of
samer@53: %criteria defined in terms of information-dynamical characteristics, such as
samer@53: %predictability vs unpredictability
samer@53: %s model, this criteria thus becoming a means of interfacing with the generative processes.  
samer@53: 
samer@62: %The tools of information dynamics provide a way to constrain and select musical
samer@62: %materials at the level of patterns of expectation, implication, uncertainty, and predictability.
samer@53: In particular, the behaviour of the predictive information rate (PIR) defined in 
samer@53: \secrf{process-info} make it interesting from a compositional point of view. The definition 
samer@53: of the PIR is such that it is low both for extremely regular processes, such as constant
samer@53: or periodic sequences, \emph{and} low for extremely random processes, where each symbol
samer@53: is chosen independently of the others, in a kind of `white noise'. In the former case,
samer@53: the pattern, once established, is completely predictable and therefore there is no
samer@53: \emph{new} information in subsequent observations. In the latter case, the randomness
samer@53: and independence of all elements of the sequence means that, though potentially surprising,
samer@53: each observation carries no information about the ones to come.
samer@53: 
samer@53: Processes with high PIR maintain a certain kind of balance between
samer@53: predictability and unpredictability in such a way that the observer must continually
samer@53: pay attention to each new observation as it occurs in order to make the best
samer@53: possible predictions about the evolution of the seqeunce. This balance between predictability
samer@53: and unpredictability is reminiscent of the inverted `U' shape of the Wundt curve (see \figrf{wundt}), 
samer@70: which summarises the observations of Wundt \cite{Wundt1897} that stimuli are most
samer@70: pleasing at intermediate levels of novelty or disorder, where there is a balance between
samer@53: `order' and `chaos'. 
samer@53: 
samer@53: Using the methods of \secrf{markov}, we found \cite{AbdallahPlumbley2009}
samer@53: a similar shape when plotting entropy rate againt PIR---this is visible in the
samer@53: upper envelope of the scatter plot in \figrf{mtriscat}, which is a 3-D scatter plot of 
samer@53: three of the information measures discussed in \secrf{process-info} for several thousand 
samer@53: first-order Markov chain transition matrices generated by a random sampling method. 
samer@53: The coordinates of the `information space' are entropy rate ($h_\mu$), redundancy ($\rho_\mu$), and
samer@62: predictive information rate ($b_\mu$). The points along the `redundancy' axis correspond
samer@62: to periodic Markov chains. Those along the `entropy' axis produce uncorrelated sequences
samer@53: with no temporal structure. Processes with high PIR are to be found at intermediate
samer@53: levels of entropy and redundancy.
samer@70: These observations led us to construct the `Melody Triangle', a graphical interface
samer@53: for exploring the melodic patterns generated by each of the Markov chains represented
samer@53: as points in \figrf{mtriscat}.
samer@53: 
samer@70: 
samer@70: %It is possible to apply information dynamics to the generation of content, such as to the composition of musical materials. 
samer@70: 
samer@70: %For instance a stochastic music generating process could be controlled by modifying
samer@70: %constraints on its output in terms of predictive information rate or entropy
samer@70: %rate.
samer@70: 
samer@43:   \begin{fig}{wundt}
samer@43:     \raisebox{-4em}{\colfig[0.43]{wundt}}
samer@43:  %  {\ \shortstack{{\Large$\longrightarrow$}\\ {\scriptsize\emph{exposure}}}\ }
samer@43:     {\ {\large$\longrightarrow$}\ }
samer@43:     \raisebox{-4em}{\colfig[0.43]{wundt2}}
samer@43:     \caption{
samer@43:       The Wundt curve relating randomness/complexity with
samer@43:       perceived value. Repeated exposure sometimes results
samer@43:       in a move to the left along the curve \cite{Berlyne71}.
samer@43:     }
samer@43:   \end{fig}
hekeus@45:  
hekeus@13: 
hekeus@13: 
samer@23:  \subsection{The Melody Triangle}  
samer@23: 
samer@70: The Melody Triangle is an interface for the discovery of melodic
samer@70: materials, where the input---positions within a triangle---directly map to information
samer@62: theoretic properties of the output. 
samer@62: %The measures---entropy rate, redundancy and
samer@62: %predictive information rate---form a criteria with which to filter the output
samer@62: %of the stochastic processes used to generate sequences of notes.  
samer@70: %These measures
samer@70: %address notions of expectation and surprise in music, and as such the Melody
samer@70: %Triangle is a means of interfacing with a generative process in terms of the
samer@70: %predictability of its output.
samer@23: 
samer@62: The triangle is populated with first order Markov chain transition
samer@62: matrices as illustrated in \figrf{mtriscat}.
samer@70: The distribution of transition matrices in this space forms a relatively thin
samer@70: curved sheet. Thus, it is a reasonable simplification to project out the 
samer@62: third dimension (the PIR) and present an interface that is just two dimensional. 
samer@64: The right-angled triangle is rotated, reflected and stretched to form an equilateral triangle with
samer@64: the $h_\mu=0, \rho_\mu=0$ vertex at the top, the `redundancy' axis down the left-hand
samer@64: side, and the `entropy rate' axis down the right, as shown in \figrf{TheTriangle}.
samer@62: This is our `Melody Triangle' and
samer@62: forms the interface by which the system is controlled. 
samer@62: %Using this interface thus involves a mapping to information space; 
samer@70: The user selects a point within the triangle, this is mapped into the 
samer@70: information space and the nearest transition matrix is used to generate
samer@70: a sequence of values which are then sonified either as pitched notes or percussive
samer@70: sounds. By choosing the position within the triangle, the user can control the
samer@70: output at the level of its `collative' properties, with access to the variety
samer@70: of patterns as described above and in \secrf{markov}.
samer@70: %and information-theoretic criteria related to predictability
samer@70: %and information flow
samer@70: Though the interface is 2D, the third dimension (PIR) is implicitly present, as 
samer@70: transition matrices retrieved from
samer@62: along the centre line of the triangle will tend to have higher PIR.
samer@70: We hypothesise that, under
samer@62: the appropriate conditions, these will be perceived as more `interesting' or 
samer@62: `melodic.'
samer@70: 	
samer@70: %The corners correspond to three different extremes of predictability and
samer@70: %unpredictability, which could be loosely characterised as `periodicity', `noise'
samer@70: %and `repetition'.  Melodies from the `noise' corner (high $h_\mu$, low $\rho_\mu$
samer@70: %and $b_\mu$) have no discernible pattern;
samer@70: %those along the `periodicity'
samer@70: %to `repetition' edge are all cyclic patterns that get shorter as we approach
samer@70: %the `repetition' corner, until each is just one repeating note. Those along the 
samer@70: %opposite edge consist of independent random notes from non-uniform distributions. 
samer@70: %Areas between the left and right edges will tend to have higher PIR, 
samer@70: %and we hypothesise that, under
samer@70: %the appropriate conditions, these will be perceived as more `interesting' or 
samer@70: %`melodic.'
samer@62: %These melodies have some level of unpredictability, but are not completely random.
samer@62: % Or, conversely, are predictable, but not entirely so.
samer@41: 
hekeus@45: %PERHAPS WE SHOULD FOREGO TALKING ABOUT THE 
hekeus@45: %INSTALLATION VERSION OF THE TRIANGLE? 
hekeus@45: %feels a bit like a tangent, and could do with the space..
samer@70: The Melody Triangle exists in two incarnations: a screen-based interface
samer@42: where a user moves tokens in and around a triangle on screen, and a multi-user
samer@42: interactive installation where a Kinect camera tracks individuals in a space and
hekeus@45: maps their positions in physical space to the triangle.  In the latter each visitor
hekeus@45: that enters the installation generates a melody and can collaborate with their
samer@62: co-visitors to generate musical textures. This makes the interaction physically engaging
samer@62: and (as our experience with visitors both young and old has demonstrated) more playful.
samer@62: %Additionally visitors can change the 
samer@62: %tempo, register, instrumentation and periodicity of their melody with body gestures.
samer@41: 
samer@70: 
samer@70:  \begin{fig}{mtriscat}
samer@70: 	\colfig[0.9]{mtriscat}
samer@70: 	\caption{The population of transition matrices in the 3D space of 
samer@70: 	entropy rate ($h_\mu$), redundancy ($\rho_\mu$) and PIR ($b_\mu$), 
samer@70: 	all in bits.
samer@70: 	The concentrations of points along the redundancy axis correspond
samer@70: 	to Markov chains which are roughly periodic with periods of 2 (redundancy 1 bit),
samer@70: 	3, 4, \etc all the way to period 7 (redundancy 2.8 bits). The colour of each point
samer@70: 	represents its PIR---note that the highest values are found at intermediate entropy
samer@70: 	and redundancy, and that the distribution as a whole makes a curved triangle. Although
samer@70: 	not visible in this plot, it is largely hollow in the middle.}
samer@70: \end{fig}
samer@70: 
samer@70: 
samer@70: The screen based interface can serve as a compositional tool.
samer@62: %%A triangle is drawn on the screen, screen space thus mapped to the statistical
samer@62: %space of the Melody Triangle.  
samer@62: A number of tokens, each representing a
samer@70: sonification stream or `voice', can be dragged in and around the triangle.
samer@70: For each token, a sequence of symbols is sampled using the corresponding
samer@70: transition matrix, which
samer@70: %statistical properties that correspond to the token's position is generated.  These
samer@70: %symbols 
samer@70: are then mapped to notes of a scale or percussive sounds%
samer@70: \footnote{The sampled sequence could easily be mapped to other musical processes, possibly over
samer@62: different time scales, such as chords, dynamics and timbres. It would also be possible
samer@70: to map the symbols to visual or other outputs.}%
samer@70: .  Keyboard commands give control over other musical parameters such
samer@70: as pitch register and inter-onset interval.  
samer@62: %The possibilities afforded by the Melody Triangle in these other domains remains to be investigated.}.
samer@70: %
samer@70: The system is capable of generating quite intricate musical textures when multiple tokens
samer@70: are in the triangle, but unlike other computer aided composition tools or programming
samer@70: environments, the composer excercises control at the abstract level of information-dynamic
samer@70: properties.
samer@70: %the interface relating to subjective expectation and predictability.
samer@23: 
samer@70: \begin{fig}{TheTriangle}
samer@70: 	\colfig[0.7]{TheTriangle.pdf}
samer@70: 	\caption{The Melody Triangle}
samer@70: \end{fig}	
hekeus@38: 
samer@66: \comment{
samer@66: \subsection{Information Dynamics as Evaluative Feedback Mechanism}
samer@66: %NOT SURE THIS SHOULD BE HERE AT ALL..?
samer@42: Information measures on a stream of symbols can form a feedback mechanism; a
hekeus@45: rudimentary `critic' of sorts.  For instance symbol by symbol measure of predictive
samer@42: information rate, entropy rate and redundancy could tell us if a stream of symbols
samer@42: is currently `boring', either because it is too repetitive, or because it is too
hekeus@45: chaotic.  Such feedback would be oblivious to long term and large scale
hekeus@45: structures and any cultural norms (such as style conventions), but 
hekeus@45: nonetheless could provide a composer with valuable insight on
samer@42: the short term properties of a work.  This could not only be used for the
samer@42: evaluation of pre-composed streams of symbols, but could also provide real-time
samer@42: feedback in an improvisatory setup.
samer@66: }
hekeus@38: 
samer@66: \subsection{User trials with the Melody Triangle}
samer@66: We are currently in the process of using the screen-based
samer@66: Melody Triangle user interface to investigate the relationship between the information-dynamic
samer@66: characteristics of sonified Markov chains and subjective musical preference.
samer@66: We carried out a pilot study with six participants, who were asked
samer@66: to use a simplified form of the user interface (a single controllable token,
samer@66: and no rhythmic, registral or timbral controls) under two conditions:
samer@66: one where a single sequence was sonified under user control, and another
samer@70: where an additional sequence was sonified in a different register, as if generated
samer@70: by a fixed invisible token in one of four regions of the triangle. In addition, subjects
samer@66: were asked to press a key if they `liked' what they were hearing.
hekeus@16: 
samer@66: We recorded subjects' behaviour as well as points which they marked
samer@66: with a key press.
samer@70: Some results for two of the subjects are shown in \figrf{mtri-results}. Though
samer@66: we have not been able to detect any systematic across-subjects preference for any particular
samer@66: region of the triangle, subjects do seem to exhibit distinct kinds of exploratory behaviour.
samer@66: Our initial hypothesis, that subjects would linger longer in regions of the triangle
samer@70: that produced aesthetically preferable sequences, and that this would tend to be towards the
samer@66: centre line of the triangle for all subjects, was not confirmed. However, it is possible
samer@66: that the design of the experiment encouraged an initial exploration of the space (sometimes
samer@70: very systematic, as for subject c) aimed at \emph{understanding} %the parameter space and
samer@70: how the system works, rather than finding musical patterns. It is also possible that the
samer@66: system encourages users to create musically interesting output by \emph{moving the token},
samer@66: rather than finding a particular spot in the triangle which produces a musically interesting
samer@70: sequence by itself.
samer@70: 
samer@70: \begin{fig}{mtri-results}
samer@70: 	\def\scat#1{\colfig[0.42]{mtri/#1}}
samer@70: 	\def\subj#1{\scat{scat_dwells_subj_#1} & \scat{scat_marks_subj_#1}}
samer@70: 	\begin{tabular}{cc}
samer@70: %		\subj{a} \\
samer@70: %		\subj{b} \\
samer@70: 		\subj{c} \\
samer@70: 		\subj{d}
samer@70: 	\end{tabular}
samer@70: 	\caption{Dwell times and mark positions from user trials with the
samer@70: 	on-screen Melody Triangle interface, for two subjects. The left-hand column shows
samer@70: 	the positions in a 2D information space (entropy rate vs multi-information rate
samer@70: 	in bits) where each spent their time; the area of each circle is proportional
samer@70: 	to the time spent there. The right-hand column shows point which subjects
samer@70: 	`liked'; the area of the circles here is proportional to the duration spent at
samer@70: 	that point before the point was marked.}
samer@70: \end{fig}
samer@46: 
samer@67: Comments collected from the subjects
samer@67: %during and after the experiment 
samer@67: suggest that
samer@66: the information-dynamic characteristics of the patterns were readily apparent
samer@66: to most: several noticed the main organisation of the triangle,
samer@70: with repetetive notes at the top, cyclic patterns along one edge, and unpredictable
samer@70: notes towards the opposite corner. Some described their systematic exploration of the space.
samer@70: Two felt that the right side was `more controllable' than the left (a consequence
samer@67: of their ability to return to a particular distinctive pattern and recognise it
samer@70: as one heard previously). Two reported that they became bored towards the end,
samer@70: but another felt there wasn't enough time to `hear out' the patterns properly.
samer@66: One subject did not `enjoy' the patterns in the lower region, but another said the lower
samer@67: central regions were more `melodic' and `interesting'.
samer@4: 
samer@66: We plan to continue the trials with a slightly less restricted user interface in order
samer@66: make the experience more enjoyable and thereby give subjects longer to use the interface;
samer@66: this may allow them to get beyond the initial exploratory phase and give a clearer
samer@66: picture of their aesthetic preferences. In addition, we plan to conduct a
samer@66: study under more restrictive conditions, where subjects will have no control over the patterns
samer@67: other than to signal (a) which of two alternatives they prefer in a forced
samer@66: choice paradigm, and (b) when they are bored of listening to a given sequence.
samer@66: 
hekeus@38: %\emph{comparable system}  Gordon Pask's Musicolor (1953) applied a similar notion
hekeus@38: %of boredom in its design.  The Musicolour would react to audio input through a
hekeus@38: %microphone by flashing coloured lights.  Rather than a direct mapping of sound
hekeus@38: %to light, Pask designed the device to be a partner to a performing musician.  It
hekeus@38: %would adapt its lighting pattern based on the rhythms and frequencies it would
hekeus@38: %hear, quickly `learning' to flash in time with the music.  However Pask endowed
hekeus@38: %the device with the ability to `be bored'; if the rhythmic and frequency content
hekeus@38: %of the input remained the same for too long it would listen for other rhythms
hekeus@38: %and frequencies, only lighting when it heard these.  As the Musicolour would
hekeus@38: %`get bored', the musician would have to change and vary their playing, eliciting
hekeus@38: %new and unexpected outputs in trying to keep the Musicolour interested.
samer@4: 	
hekeus@13: 
samer@70: \section{Conclusions}
samer@61: 
samer@61: 	% !!! FIXME
samer@70: %We reviewed our information dynamics approach to the modelling of the perception
samer@70: We have looked at several emerging areas of application of the methods and
samer@70: ideas of information dynamics to various problems in music analysis, perception
samer@70: and cognition, including musicological analysis of symbolic music, audio analysis,
samer@70: rhythm processing and compositional and creative tasks. The approach has proved
samer@70: successful in musicological analysis, and though our initial data on
samer@70: rhythm processing and aesthetic preference are inconclusive, there is still
samer@70: plenty of work to be done in this area: where-ever there are probabilistic models,
samer@70: information dynamics can shed light on their behaviour. 
hekeus@50: 
hekeus@50: 
hekeus@45: 
samer@59: \section*{acknowledgments}
samer@51: This work is supported by EPSRC Doctoral Training Centre EP/G03723X/1 (HE),
hekeus@54: GR/S82213/01 and EP/E045235/1(SA), an EPSRC DTA Studentship (PF), an RAEng/EPSRC Research Fellowship 10216/88 (AR), an EPSRC Leadership Fellowship, EP/G007144/1
samer@51: (MDP) and EPSRC IDyOM2 EP/H013059/1.
hekeus@55: This work is partly funded by the CoSound project, funded by the Danish Agency for Science, Technology and Innovation.
samer@61: Thanks also Marcus Pearce for providing the two rule-based analyses of \emph{Two Pages}.
hekeus@55: 
hekeus@44: 
samer@59: \bibliographystyle{IEEEtran}
samer@43: {\bibliography{all,c4dm,nime,andrew}}
samer@4: \end{document}