# http://colinraffel.com/wiki/

### Site Tools

identifying_repeated_patterns_in_music_using_sparse_convolutive_non-negative_matrix_factorization

# Identifying Repeated Patterns in Music Using Sparse Convolutive Non-Negative Matrix Factorization

 Authors Ron J. Weiss and Juan Pablo Bello Publication Info Retrieved here Retrieval date 2/23/11

Proposes a method for music segmentation by factoring a beat-synchronized matrix of chroma vectors. A summary of the presentation given for the paper at ISMIR10 is here.

## Background

Most music involves repetition, but it's hard to extract from the audio itself. Previous techniques use self-similarity matrices and HMMs. The proposed method uses shift-invariant PLCA, and treats music as a concatenation of a subset of short, repeated patterns, whose length is not necessarily known in advance.

## NMF, PLCA, and SI-PLCA

NMF decomposes a matrix $V$ into $WH$, where (when $V$ is a time-frequency representation of the audio signal, like beat chromagrams in the paper) $W$ has frequency templates in each column and $H$ has the “amount” of each template at each time. PLCA treats $W$ and $H$ as multinomial probability distributions and adds a diagonal mixing weight matrix $Z$. For shift invariance, PLCA is modified so that W is a tensor, and is combined via convolution: $V\approx\sum_k W_k \star z_k h_k^T$

## Enforcing sparse matrices

It is favorable to use sparse matrices in NMF, which can be encouraged by prior distributions. To learn the number of patterns, the Dirichlet (multinomial conjugate) distribution is used, with a parameter $\alpha_z \lt 1$ which favors sparse solutions. If $z$ is sparse, then initializing with many bases will prune out those which do not which do not contribute significantly (removing the need to specify the exact composition rank). The pattern length $L$ should be variable per-basis. A Dirichlet prior is also used with a parameter $\alpha_w$ that depends on the time position $\tau$ within each basis - this parameter basically penalizes pattern lengths greater than some value. The sparsity of $h_k^T$ should also be enforced to capture more information about $V$ in $W_k$. The result is that certain bases will have information which repeats often, and others will have “special case” information.

## Expectation/Maximization for Parameter Estimation

The EM algorithm is used. Expectation: calculate the posterior distribution over variables $k$ and $\tau$ for each cell in $V$, represented as a set of matrices for each possible combination where each point represents the probability that the corresponding point in $V$ was generated by basis $k$ at time $\tau$. Maximization: Update the decomposition according to parameters.

## Segmentation

$H$ encodes long-term structure; $W$ encodes short-term structure. Per-beat chromagrams are calculated, and sequences of chromagrams are assumed to happen only once, and one chromagram sequence is chosen per-segment via a rectangular smoothing window. This segmentation is not necessarily verse/chorus/etc, but instead is “groups of a similar chord progression”. The amount that this is true is parameterized by $\alpha_{w\tau}$.

## Evaluation

Tested on a set of Beatles songs, with performance measured using pairwise precision, recall, and F-measure and entropy-based over- and under-segmentation scores. The number of patterns is optimized by varying $K$ with $\al_z=1$ and varying $\al_z$ with $K=15$. Optimal results were when $\al_z = 0.98$ and $K=4$. $L$ was optimized between 10 and 120 beats, and was found to peak at $L=20$. Allowing for varying pattern length has negligible effect on segmentation performance (even if the results are quantitatively better). The proposed system (with fixed rank and with sparse $z$) to an HMM and a self-similarity matrix based system, and got comparable results. The self-similarity system had better boundary detection, mostly thanks to the smoothing used in the proposed system.