next Experiments and discussion
up Methods
previous Computational models of music styles


Composer identification by comparing Kullback-Leibler distances

Assuming that composer A and composer B each has a unique style that can be recognized in a certain repertoire, one can select a feature that looks interesting, define the state space, and build up the Markov chain models $ \mathcal{C_{\mathrm{A}}}= P_{\mathrm{A}}$, $ \mathcal{C_{\mathrm{B}}}= P_{\mathrm{B}}$, for composer A and B, respectively. Based on these two Markov models, for each given unknown work U, two-way composer identification can be achieved by the following hypothesis test,

\begin{displaymath}
\mathtt{My\_Author} =
\begin{cases}
A, & D(P^{\mathrm{U}} ...
...\vert P^{\mathrm{B}} ) ;\\
B, &\text{otherwise,}
\end{cases}\end{displaymath}


where $ P_{\mathrm{U}}$ is the transition matrix of the repertoire that contains only the unknown work U, $ \mathtt{My\_Author}$ is the composer that is more likely than the other one to have written the work, and $ D$ is a distance metric on the space of $ N \times N$ probability matrice. In this research, we use the Kullback-Leibler distance metric,

$\displaystyle D(P^{(1)} \vert\vert P^{(2)}) = \sum_{i=1}^N \sum_{j=1}^N
P^{(1)}_{i,j} \log_2 \frac{P^{(1)}_{i,j}}{P^{(2)}_{i,j}}
$

Although the Kullback-Leibler distance metric is not symmetric and does not obey the trangular inequality, it is useful to interpret of the metric as the distance between distributions [#!Cover!#]. Accepting this interpretation, the above hypothesis test reads ``if the transition matrix of the unknown work is closer to that of composer A's repertoire, then it is more likely to have been written by A.'' This hand-waving statement can be justified by the following theorem.
THEOREM (likelihood ratio interpretation) For the two-way composer identification test, if the two marginal distributions are identical,

$\displaystyle P^\mathrm{A}_{i} = \sum_{j} P^{A}_{i,j} = \sum_{j} P^{B}_{i,j} = P^\mathrm{B}_{i},
\ \ \forall i,
$


then, the difference of the two distances has a likelihood ratio interpretation,

$\displaystyle 2^{D(P^{\mathrm{U}} \vert\vert P^{\mathrm{A}} ) -
D(P^{\mathrm{U...
...frac{p(\mathrm{U}\vert\mathrm{B})}{p(\mathrm{U}\vert\mathrm{A})}
\right)^{1/L}
$


where $ p($U$ \vert$A$ )$ is the a priori probability that U $ =\{U_1,U_2,...\}$ is generated according to $ P_\mathrm{A}$, and $ L$ is the length of U.

Proof:
$\displaystyle D(P^\mathrm{U}\vert\vert P^\mathrm{A})-D(P^\mathrm{U}\vert\vert P^\mathrm{B})$ $\displaystyle =$ $\displaystyle \sum_i \sum_j P^\mathrm{U}_{i,j}\log_2 \frac{P^\mathrm{U}_{i,j}}{...
...i \sum_j P^\mathrm{U}_{i,j}\log_2 \frac{P^\mathrm{U}_{i,j}}{P^\mathrm{B}_{i,j}}$  
  $\displaystyle =$ $\displaystyle \sum_i \sum_j P^\mathrm{U}_{i,j}\log_2 \frac{P^\mathrm{B}_{i,j}}{P^\mathrm{A}_{i,j}}$  
  $\displaystyle =$ $\displaystyle \sum_i \sum_j \frac{n_{i,j}}{L} \log_2 \frac{P^\mathrm{B}_{i,j}}{P^\mathrm{A}_{i,j}}$  
  $\displaystyle =$ $\displaystyle \frac{1}{L}\sum_i \sum_j \log_2
\left( \frac{P^\mathrm{B}_{i,j}}{P^\mathrm{A}_{i,j}} \right)^{n_{i,j}}$  

where $ n_{i,j}$ denotes how many times the transition between $ i^{\text{th}}$ and $ j^{\text{th}}$ states occurs in U. Therefore,

$\displaystyle 2^{D(P^\mathrm{U}\vert\vert P^\mathrm{A})-D(P^\mathrm{U}\vert\vert P^\mathrm{B})}$ $\displaystyle = \left( \prod_{t=1}^{L-1} \frac{P^\mathrm{B}_{U_t,U_{t+1}}} {P^\mathrm{A}_{U_t,U_{t+1}}} \right)^{1/L}$ (1)
  $\displaystyle = \left( \frac{P^\mathrm{B}_{U_1}}{P^\mathrm{A}_{U_1}} \prod_{t=1...
...}_{U_t}} {P^\mathrm{A}_{U_t,U_{t+1}}/P^\mathrm{A}_{U_t}} \right)^{1/L} \ \qquad$ (identical marginals) (2)
  $\displaystyle = \left( \frac{p(\mathrm{U}\vert\mathrm{B})}{p(\mathrm{U}\vert\mathrm{A})} \right)^{1/L} \qquad$ END (3)

The above theorem states that, for the purposes of composer identification, if the marginals of are identical and hence don't help, then For example, if two composers use as frequently each of the notes as one another but concatenate them differently, then Kullback-Leibler distance is the right metric to choose for the purposes of composer identification.


next Experiments and discussion
up Methods
previous Computational models of music styles

Copyright © 2002-06-11
Center for Computer Research in Music and Acoustics,   Stanford University