
samer@18: \documentclass[conference,a4paper]{IEEEtran}
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@4: \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\\
hekeus@16: 		Mile End Road, London E1 4NS\\
hekeus@16: 		Email:}}
samer@4: 
samer@4: \maketitle
samer@18: \begin{abstract}
samer@18: 	People take in information when perceiving music.  With it they continually
samer@18: 	build predictive models of what is going to happen.  There is a relationship
samer@18: 	between information measures and how we perceive music.  An information
samer@18: 	theoretic approach to music cognition is thus a fruitful avenue of research.
samer@18: 	In this paper, we review the theoretical foundations of information dynamics
samer@18: 	and discuss a few emerging areas of application.
hekeus@16: \end{abstract}
samer@4: 
samer@4: 
samer@25: \section{Introduction}
samer@9: \label{s:Intro}
samer@9: 
samer@25: 	\subsection{Expectation and surprise in music}
samer@18: 	One of the effects of listening to music is to create 
samer@18: 	expectations of what is to come next, which may be fulfilled
samer@9: 	immediately, after some delay, or not at all as the case may be.
samer@9: 	This is the thesis put forward by, amongst others, music theorists 
samer@18: 	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@9: 	that `unfolds' in time, rather than being apprehended as a static object
samer@9: 	presented in its entirety. Meyer argued that musical 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@25: 	\citep{SaffranJohnsonAslin1999,EerolaToiviainenKrumhansl2002}, 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@25: 
samer@25: \comment{
samer@9: 	The business of making predictions and assessing surprise is essentially
samer@9: 	one of reasoning under conditions of uncertainty and manipulating
samer@9: 	degrees of belief about the various proposition which may or may not
samer@9: 	hold, and, as has been argued elsewhere \cite{Cox1946,Jaynes27}, best
samer@9: 	quantified in terms of Bayesian probability theory.
samer@9:    Thus, we suppose that
samer@9: 	when we listen to music, expectations are created on the basis of our
samer@24: 	familiarity with various stylistic norms that apply to music in general,
samer@24: 	the particular style (or styles) of music that seem best to fit the piece 
samer@24: 	we are listening to, and
samer@9: 	the emerging structures peculiar to the current piece.  There is
samer@9: 	experimental evidence that human listeners are able to internalise
samer@9: 	statistical knowledge about musical structure, \eg
samer@9: 	\citep{SaffranJohnsonAslin1999,EerolaToiviainenKrumhansl2002}, and also
samer@9: 	that statistical models can form an effective basis for computational
samer@9: 	analysis of music, \eg
samer@9: 	\cite{ConklinWitten95,PonsfordWigginsMellish1999,Pearce2005}.
samer@25: }
samer@9: 
samer@9: 	\subsection{Music and information theory}
samer@24: 	With a probabilistic framework for music modelling and prediction in hand,
samer@25: 	we are in a position to apply Shannon's quantitative information theory 
samer@25: 	\cite{Shannon48}. 
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: 	The relationship between information theory and music and art in general has been the 
samer@9: 	subject of some interest since the 1950s 
samer@9: 	\cite{Youngblood58,CoonsKraehenbuehl1958,HillerBean66,Moles66,Meyer67,Cohen1962}. 
samer@9: 	The general thesis is that perceptible qualities and subjective
samer@9: 	states like uncertainty, surprise, complexity, tension, and interestingness
samer@9: 	are closely related to 
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@9: 
samer@24: 	Bringing the various strands together, our working hypothesis is that as a
samer@24: 	listener (to which will refer as `it') listens to a piece of music, it maintains
samer@25: 	a dynamically evolving probabilistic model that enables it to make predictions
samer@24: 	about how the piece will continue, relying on both its previous experience
samer@24: 	of music and the immediate context of the piece.  As events unfold, it revises
samer@25: 	its probabilistic 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@25: 	One of the consequences 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@25: 	rates of information flow (bits per second). The probabilistic and 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@25: 	created mainly in response to 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@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@30: 		I-diagram visualisation 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: 	\subsection{Entropy and information}
samer@30: 	Let $X$ denote some variable whose value is initially unknown to our 
samer@30: 	hypothetical observer. We will treat $X$ mathematically as a random variable,
samer@30: 	with a value to be drawn from some set (or \emph{alphabet}) $\A$ and a 
samer@30: 	probability distribution representing the observer's beliefs about the 
samer@30: 	true value of $X$.
samer@30: 	In this case, the observer's uncertainty about $X$ can be quantified
samer@30: 	as the entropy of the random variable $H(X)$. For a discrete variable
samer@30: 	with probability mass function $p:\A \to [0,1]$, this is
samer@30: 	\begin{equation}
samer@30: 		H(X) = \sum_{x\in\A} -p(x) \log p(x) = \expect{-\log p(X)},
samer@30: 	\end{equation}
samer@30: 	where $\expect{}$ is the expectation operator. The negative-log-probability
samer@30: 	$\ell(x) = -\log p(x)$ of a particular value $x$ can usefully be thought of as
samer@30: 	the \emph{surprisingness} of the value $x$ should it be observed, and
samer@30: 	hence the entropy is the expected surprisingness.
samer@30: 
samer@30: 	Now suppose that the observer receives some new data $\Data$ that
samer@30: 	causes a revision of its beliefs about $X$. The \emph{information}
samer@30: 	in this new data \emph{about} $X$ can be quantified as the 
samer@30: 	Kullback-Leibler (KL) divergence between the prior and posterior
samer@30: 	distributions $p(x)$ and $p(x|\Data)$ respectively:
samer@30: 	\begin{equation}
samer@30: 		\mathcal{I}_{\Data\to X} = D(p_{X|\Data} || p_{X})
samer@30: 			= \sum_{x\in\A} p(x|\Data) \log \frac{p(x|\Data)}{p(x)}.
samer@30: 	\end{equation}
samer@30: 	If there are multiple variables $X_1, X_2$ 
samer@30: 	\etc which the observer believes to be dependent, then the observation of 
samer@30: 	one may change its beliefs and hence yield information about the
samer@30: 	others.
samer@30: 	The relationships between the various joint entropies, conditional
samer@30: 	entropies, mutual informations and conditional mutual informations
samer@30: 	can be visualised in Venn diagram-like \emph{information diagrams}
samer@30: 	or I-diagrams \cite{Yeung1991}, for example, the three-variable
samer@30: 	I-diagram in \figrf{venn-example}.
samer@30: 
samer@30: 
samer@30: 	\subsection{Entropy and information in sequences}
samer@30: 
samer@30: 	Suppose that  $(\ldots,X_{-1},X_0,X_1,\ldots)$ is a stationary sequence of
samer@30: 	random variables, infinite in both directions, 
samer@30: 	and that $\mu$ is the associated shift-invariant probability measure over all 
samer@30: 	configurations 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@30: 	which, at any time $t$, there is `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@30: 	Since the sequence is assumed stationary, we can without loss of generality,
samer@30: 	assume that $t=0$ in the following definitions.
samer@30: 
samer@30: 	The \emph{entropy rate} of the process is the entropy of the next variable
samer@30: 	$X_t$ given all the previous ones.
samer@30: 	\begin{equation}
samer@30: 		\label{eq:entro-rate}
samer@30: 		h_\mu = H(X_0|\past{X}_0).
samer@30: 	\end{equation}
samer@30: 	The entropy rate gives a measure of the overall randomness
samer@30: 	or unpredictability of the process.
samer@30: 
samer@30: 	The \emph{multi-information rate} $\rho_\mu$ (following Dubnov's \cite{Dubnov2006}
samer@30: 	notation for what he called the `information rate') is the mutual
samer@30: 	information between the `past' and the `present':
samer@30: 	\begin{equation}
samer@30: 		\label{eq:multi-info}
samer@30: 			\rho_\mu(t) = I(\past{X}_t;X_t) = H(X_0) - h_\mu.
samer@30: 	\end{equation}
samer@30: 	It is a measure of how much the context of an observation (that is,
samer@30: 	the observation of previous elements of the sequence) helps in predicting
samer@30: 	or reducing the suprisingness of the current observation.
samer@30: 
samer@30: 	The \emph{excess entropy} \cite{CrutchfieldPackard1983} 
samer@30: 	is the mutual information between 
samer@30: 	the entire `past' and the entire `future':
samer@30: 	\begin{equation}
samer@30: 		E = I(\past{X}_0; X_0,\fut{X}_0).
samer@30: 	\end{equation}
samer@30: 	
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@18: 		\begin{tabular}{c@{\colsep}c}
samer@18: 			\subfig{(a) 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@18: 			\\[1.25em]
samer@18: 			\subfig{(b) 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@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@18: 				\\[0.5em]
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@18: 		correspond to various mutual information as in \Figrf{venn-example}.
samer@33: 		In (b), 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@18: 		information rate. The entropy rate is $h_\mu = r_\mu+b_\mu$.
samer@18: 		}
samer@18: 	\end{fig}
samer@18: 
samer@30: 	The \emph{predictive information rate} (or PIR) \cite{AbdallahPlumbley2009}  
samer@30: 	is the average information in one observation about the infinite future given the infinite past,
samer@30: 	and is defined as a conditional mutual information: 
samer@18: 	\begin{equation}
samer@18: 		\label{eq:PIR}
samer@30: 		b_\mu = I(X_0;\fut{X}_0|\past{X}_0) = H(\fut{X}_0|\past{X}_0) - H(\fut{X}_0|X_0,\past{X}_0).
samer@18: 	\end{equation}
samer@18: 	Equation \eqrf{PIR} 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@18: 		I(X_t;\fut{X}_t|\past{X}_t) = H(X_t|\past{X}_t) - H(X_t|\fut{X}_t,\past{X}_t).
samer@18: %		\label{<++>}
samer@18: 	\end{equation}
samer@18: %	If $X$ is stationary, then 
samer@18: 	Now, in the shift-invariant case, $H(X_t|\past{X}_t)$ 
samer@18: 	is the familiar entropy rate $h_\mu$, but $H(X_t|\fut{X}_t,\past{X}_t)$, 
samer@18: 	the conditional entropy of one variable given \emph{all} the others 
samer@18: 	in the sequence, future as well as past, is what 
samer@18: 	we called the \emph{residual entropy rate} $r_\mu$ in \cite{AbdallahPlumbley2010},
samer@18: 	but was previously identified by Verd{\'u} and Weissman \cite{VerduWeissman2006} as the
samer@18: 	\emph{erasure entropy rate}.
samer@30: 	Thus, the PIR is the difference between 
samer@18: 	the entropy rate and the erasure entropy rate: $b_\mu = h_\mu - r_\mu$.
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@18: 
samer@18: 
samer@24:   \begin{fig}{wundt}
samer@24:     \raisebox{-4em}{\colfig[0.43]{wundt}}
samer@24:  %  {\ \shortstack{{\Large$\longrightarrow$}\\ {\scriptsize\emph{exposure}}}\ }
samer@24:     {\ {\large$\longrightarrow$}\ }
samer@24:     \raisebox{-4em}{\colfig[0.43]{wundt2}}
samer@24:     \caption{
samer@24:       The Wundt curve relating randomness/complexity with
samer@24:       perceived value. Repeated exposure sometimes results
samer@24:       in a move to the left along the curve \cite{Berlyne71}.
samer@24:     }
samer@24:   \end{fig}
samer@24: 
samer@25: 	\subsection{Other sequential information measures}
samer@25: 
samer@25: 	James et al \cite{JamesEllisonCrutchfield2011} study the predictive information
samer@25: 	rate and also examine some related measures. In particular they identify the
samer@25: 	$\sigma_\mu$, the difference between the multi-information rate and the excess
samer@25: 	entropy, as an interesting quantity that measures the predictive benefit of
samer@25: 	model-building (that is, maintaining an internal state summarising past 
samer@25: 	observations in order to make better predictions). They also identify
samer@25: 	$w_\mu = \rho_\mu + b_{\mu}$, which they call the \emph{local exogenous
samer@30: 	information} rate.
samer@24: 
samer@18: 	\subsection{First order Markov chains}
samer@18: 	These are the simplest non-trivial models to which information dynamics methods
samer@18: 	can be applied. In \cite{AbdallahPlumbley2009} we, showed that the predictive information
samer@18: 	rate can be expressed simply in terms of the entropy rate of the Markov chain.
samer@18: 	If we let $a$ denote the transition matrix of the Markov chain, and $h_a$ it's
samer@18: 	entropy rate, then its predictive information rate $b_a$ is
samer@18: 	\begin{equation}
samer@18: 		b_a = h_{a^2} - h_a,
samer@18: 	\end{equation}
samer@18: 	where $a^2 = aa$, the transition matrix squared, is the transition matrix
samer@18: 	of the `skip one' Markov chain obtained by leaving out every other observation.
samer@18: 
samer@18: 	\subsection{Higher order Markov chains}
samer@18: 	Second and higher order Markov chains can be treated in a similar way by transforming
samer@18: 	to a first order representation of the high order Markov chain. If we are dealing
samer@18: 	with an $N$th order model, this is done forming a new alphabet of possible observations 
samer@18: 	consisting of all possible $N$-tuples of symbols from the base alphabet. An observation
samer@18: 	in this new model represents a block of $N$ observations from the base model. The next
samer@18: 	observation represents the block of $N$ obtained by shift the previous block along
samer@18: 	by one step. The new Markov of chain is parameterised by a sparse $K^N\times K^N$
samer@18: 	transition matrix $\hat{a}$.
samer@18: 	\begin{equation}
samer@18: 		b_{\hat{a}} = h_{\hat{a}^{N+1}} - N h_{\hat{a}},
samer@18: 	\end{equation}
samer@18: 	where $\hat{a}^{N+1}$ is the $N+1$th power of the transition matrix.  
samer@18: 		
samer@9: 
samer@4: 
hekeus@16: \section{Information Dynamics in Analysis}
samer@4: 
hekeus@16:  	\subsection{Musicological Analysis}
samer@4: 	refer to the work with the analysis of minimalist pieces
samer@4: 	
samer@24:     \begin{fig}{twopages}
samer@33:       \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@24: 			\vspace*{1em}
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@24:       mark the
samer@24:       six most surprising moments selected by Keith Potter.
samer@24:       The bottom panel shows a rule-based boundary strength analysis computed
samer@24:       using Cambouropoulos' LBDM.
samer@24:       All information measures are in nats and time is in notes.
samer@24:       }
samer@24:     \end{fig}
samer@24: 
samer@24:     \begin{fig}{metre}
samer@33: %      \scalebox{1}[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@24:       informative 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@23: 	\subsection{Content analysis/Sound Categorisation}.  
peterf@26:         Overview of of information-theoretic approaches to music content analysis.
peterf@26:         \begin{itemize}
samer@33:             \item Continuous domain information 
samer@33: 						\item Audio based music expectation modelling
peterf@26:             \item Proposed model for Gaussian processes      
peterf@26:         \end{itemize}
peterf@26:     \emph{Peter}
peterf@26: 
samer@4: 
samer@4: \subsection{Beat Tracking}
hekeus@16:  \emph{Andrew}  
samer@4: 
samer@4: 
samer@24: \section{Information dynamics as compositional aid}
hekeus@13: 
samer@23: In addition to applying information dynamics to analysis, it is also possible
samer@23: use this approach in design, such as the composition of musical materials.  By
samer@23: providing a framework for linking information theoretic measures to the control
samer@23: of generative processes, it becomes possible to steer the output of these processes
samer@23: to match a criteria defined by these measures.  For instance outputs of a
samer@23: stochastic musical process could be filtered to match constraints defined by a
samer@23: set of information theoretic measures.
hekeus@13: 
samer@23: The use of stochastic processes for the generation of musical material has been
samer@23: widespread for decades -- Iannis Xenakis applied probabilistic mathematical
samer@23: models to the creation of musical materials, including to the formulation of a
samer@23: theory of Markovian Stochastic Music.  However we can use information dynamics
samer@23: measures to explore and interface with such processes at the high and abstract
samer@23: level of expectation, randomness and predictability.  The Melody Triangle is
samer@23: such a system.
hekeus@13: 
samer@23:  \subsection{The Melody Triangle}  
samer@23: The Melody Triangle is an exploratory interface for the discovery of melodic
samer@23: content, where the input -- positions within a triangle -- directly map to
samer@23: information theoretic measures associated with the output.
samer@23: The measures are the entropy rate, redundancy and predictive information rate
samer@23: of the random process used to generate the sequence of notes.
samer@23: These are all related to the predictability of the the sequence and as such
samer@23: address the notions of expectation and surprise in the perception of
samer@23: music.\emph{self-plagiarised}
hekeus@13:  	
samer@23: Before the Melody Triangle can used, it has to be `populated' with possible
samer@23: parameter values for the melody generators.  These are then plotted in a 3d
samer@23: statistical space of redundancy, entropy rate and predictive information rate.
samer@23: In our case we generated thousands of transition matrixes, representing first-order
samer@23: Markov chains, by a random sampling method. In figure \ref{InfoDynEngine} we see
samer@23: a representation of how these matrixes are distributed in the 3d statistical
samer@23: space; each one of these points corresponds to a transition
samer@23: matrix.\emph{self-plagiarised}
hekeus@17: 
hekeus@17: \begin{figure}
hekeus@17: \centering
samer@21: \includegraphics[width=\linewidth]{figs/mtriscat}
samer@21: \caption{The population of transition matrices distributed along three axes of 
samer@21: redundancy, entropy rate and predictive information rate (all measured in bits).
samer@21: The concentrations of points along the redundancy axis correspond
samer@21: to Markov chains which are roughly periodic with periods of 2 (redundancy 1 bit),
samer@21: 3, 4, \etc all the way to period 8 (redundancy 3 bits). The colour of each point
samer@21: represents its PIR---note that the highest values are found at intermediate entropy
samer@21: and redundancy, and that the distribution as a whole makes a curved triangle. Although
samer@21: not visible in this plot, it is largely hollow in the middle. 
samer@21: \label{InfoDynEngine}}
hekeus@17: \end{figure}
hekeus@17:  
samer@4: 	
samer@23: When we look at the distribution of transition matrixes plotted in this space,
samer@23: we see that it forms an arch shape that is fairly thin.  It thus becomes a
samer@23: reasonable approximation to pretend that it is just a sheet in two dimensions;
samer@23: and so we stretch out this curved arc into a flat triangle.  It is this triangular
samer@23: sheet that is our `Melody Triangle' and forms the interface by which the system
samer@23: is controlled. \emph{self-plagiarised}
samer@4: 	
samer@23: When the Melody Triangle is used, regardless of whether it is as a screen based
samer@23: system, or as an interactive installation, it involves a mapping to this statistical
samer@23: space.  When the user, through the interface, selects a position within the
samer@23: triangle, the corresponding transition matrix is returned.  Figure \ref{TheTriangle}
samer@23: shows how the triangle maps to different measures of redundancy, entropy rate
samer@23: and predictive information rate.\emph{self-plagiarised}
hekeus@17:  \begin{figure}
hekeus@17: \centering
samer@33: \includegraphics[width=0.9\linewidth]{figs/TheTriangle.pdf}
hekeus@17: \caption{The Melody Triangle\label{TheTriangle}}
hekeus@17: \end{figure}	
samer@23: Each corner corresponds to three different extremes of predictability and
samer@23: unpredictability, which could be loosely characterised as `periodicity', `noise'
samer@23: and `repetition'.  Melodies from the `noise' corner have no discernible pattern;
samer@23: they have high entropy rate, low predictive information rate and low redundancy.
samer@23: These melodies are essentially totally random.  A melody along the `periodicity'
samer@23: to `repetition' edge are all deterministic loops that get shorter as we approach
samer@23: the `repetition' corner, until it becomes just one repeating note.  It is the
samer@23: areas in between the extremes that provide the more `interesting' melodies.  That
samer@23: is, those that have some level of unpredictability, but are not completely ran-
samer@23: dom. Or, conversely, that are predictable, but not entirely so.  This triangular
samer@23: space allows for an intuitive explorationof expectation and surprise in temporal
samer@23: sequences based on a simple model of how one might guess the next event given
samer@23: the previous one.\emph{self-plagiarised}
samer@23: 
samer@4: 	
samer@23: 
samer@23: Any number of interfaces could be developed for the Melody Triangle.  We have
samer@23: developed two; a standard screen based interface where a user moves tokens with
samer@23: a mouse in and around a triangle on screen, and a multi-user interactive
samer@23: installation where a Kinect camera tracks individuals in a space and maps their
samer@23: positions in the space to the triangle.
samer@23:  Each visitor would generate a melody, and could collaborate with their co-visitors
samer@23:  to generate musical textures -- a playful yet informative way to explore
samer@23:  expectation and surprise in music.
samer@23: 
samer@23: As a screen based interface the Melody Triangle can serve as composition tool.
samer@23: A triangle is drawn on the screen, screen space thus mapped to the statistical
samer@23: space of the Melody Triangle.
samer@23: A number of round tokens, each representing a melody can be dragged in and
samer@23: around the triangle.  When a token is dragged into the triangle, the system
samer@23: will start generating the sequence of notes with statistical properties that
samer@23: correspond to its position in the triangle.\emph{self-plagiarised}
samer@23: 
samer@23: In this mode, the Melody Triangle can be used as a kind of composition assistant
samer@23: for the generation of interesting musical textures and melodies.  However unlike
samer@23: other computer aided composition tools or programming environments, here the
samer@23: composer engages with music on the high and abstract level of expectation,
samer@23: randomness and predictability.\emph{self-plagiarised}
samer@23: 
hekeus@13: 	
hekeus@13: Additionally the Melody Triangle serves as an effective tool for experimental investigations into musical preference and their relationship to the information dynamics models.
samer@4: 
hekeus@13: 	%As the Melody Triangle essentially operates on a stream of symbols, it it is possible to apply the melody triangle to the design of non-sonic content.
hekeus@13: 	
hekeus@13: \section{Musical Preference and Information Dynamics}
samer@23: We carried out a preliminary study that sought to identify any correlation between
samer@23: aesthetic preference and the information theoretical measures of the Melody
samer@23: Triangle.  In this study participants were asked to use the screen based interface
samer@23: but it was simplified so that all they could do was move tokens around.  To help
samer@23: discount visual biases, the axes of the triangle would be randomly rearranged
samer@23: for each participant.\emph{self-plagiarised}
hekeus@16: 
samer@23: The study was divided in to two parts, the first investigated musical preference
samer@23: with respect to single melodies at different tempos.  In the second part of the
samer@23: study, a background melody is playing and the participants are asked to continue
samer@23: playing with the system under the implicit assumption that they will try to find
samer@23: a second melody that works well with the background melody.  For each participant
samer@23: this was done four times, each with a different background melody from four
samer@23: different areas of the Melody Triangle.  For all parts of the study the participants
samer@23: were asked to signal, by pressing the space bar, whenever they liked what they
samer@23: were hearing.\emph{self-plagiarised}
samer@4: 
hekeus@13: \emph{todo - results}
samer@4: 
hekeus@13: \section{Information Dynamics as Evaluative Feedback Mechanism}
hekeus@13: 
hekeus@13: \emph{todo - code the info dyn evaluator :) }
samer@4: 	
samer@23: It is possible to use information dynamics measures to develop a kind of `critic'
samer@23: that would evaluate a stream of symbols.  For instance we could develop a system
samer@23: to notify us if a stream of symbols is too boring, either because they are too
samer@23: repetitive or too chaotic.  This could be used to evaluate both pre-composed
samer@23: streams of symbols, or could even be used to provide real-time feedback in an
samer@23: improvisatory setup.
hekeus@13: 
samer@23: \emph{comparable system}  Gordon Pask's Musicolor (1953) applied a similar notion
samer@23: of boredom in its design.  The Musicolour would react to audio input through a
samer@23: microphone by flashing coloured lights.  Rather than a direct mapping of sound
samer@23: to light, Pask designed the device to be a partner to a performing musician.  It
samer@23: would adapt its lighting pattern based on the rhythms and frequencies it would
samer@23: hear, quickly `learning' to flash in time with the music.  However Pask endowed
samer@23: the device with the ability to `be bored'; if the rhythmic and frequency content
samer@23: of the input remained the same for too long it would listen for other rhythms
samer@23: and frequencies, only lighting when it heard these.  As the Musicolour would
samer@23: `get bored', the musician would have to change and vary their playing, eliciting
samer@23: new and unexpected outputs in trying to keep the Musicolour interested.
samer@4: 	
samer@23: In a similar vein, our \emph{Information Dynamics Critic}(name?) allows for an
samer@23: evaluative measure of an input stream, however containing a more sophisticated
samer@23: notion of boredom that \dots
samer@23: 
hekeus@13: 
hekeus@13:    
hekeus@13: 
samer@4: \section{Conclusion}
samer@4: 
samer@9: \bibliographystyle{unsrt}
hekeus@16: {\bibliography{all,c4dm,nime}}
samer@4: \end{document}




