Dictionary Learning.lyx

#LyX 2.2 created this file. For more info see http://www.lyx.org/
\lyxformat 508
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass amsart
\begin_preamble
\allowdisplaybreaks
\DeclareMathOperator{\E}{E}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\Cov}{Cov}
\DeclareMathOperator{\dif}{d}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator{\tr}{tr}
\usepackage{algpseudocode}
\usepackage{url}
\end_preamble
\use_default_options true
\begin_modules
theorems-ams
eqs-within-sections
figs-within-sections
knitr
\end_modules
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder false
\pdf_colorlinks false
\pdf_backref false
\pdf_pdfusetitle true
\papersize default
\use_geometry true
\use_package amsmath 2
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 1.5in
\topmargin 1.5in
\rightmargin 1.5in
\bottommargin 1.5in
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
Online Detection of Unusual Events in Audio via Dynamic Sparse Coding
\end_layout

\begin_layout Author
Courtney Grazzini
\begin_inset Newline newline
\end_inset

Meredith Miller
\begin_inset Newline newline
\end_inset

Sean Wilson
\end_layout

\begin_layout Abstract
Sparse representation of a natural signal in terms of a dictionary learned
 from the signal itself has been shown to be highly effective.
 Online methods for dictionary learning mitigate scalability issues with
 traditional batch learning methods, and offer the ability to learn dictionaries
 for streaming signals.
 We review the key concepts of sparse dictionary learning and important
 results related to the online extension of such methods.
 We show that online dictionary learning can be used to detect unusual events
 in audio signals, such as a change in meter or the introduction of a new
 instrument, and that such methods are robust to concept drift in the target
 signal.
\end_layout

\begin_layout Section
Introduction
\end_layout

\begin_layout Subsection
Dictionary learning
\end_layout

\begin_layout Standard
We can represent a signal as a linear combination of basis elements.
 We refer to the basis elements as 
\emph on
atoms
\emph default
, and to the collection of these elements as a 
\emph on
dictionary
\emph default
.
 We do not require that the atoms be linearly independent, and we allow
 the dictionary to be 
\emph on
overcomplete
\emph default
, i.e., it may contain more basis elements than the dimension of the signal
 it is used to represent.
\end_layout

\begin_layout Standard
Predefined dictionaries are often used to represent signals.
 Let 
\begin_inset Formula $\mathcal{D}=\left\{ \mathbf{u},\mathbf{v}\right\} $
\end_inset

 for some linearly independent 
\begin_inset Formula $\mathbf{u},\mathbf{v}\in\mathbb{R}^{2}$
\end_inset

.
 Then, we can represent any signal 
\begin_inset Formula $\mathbf{x}\in\mathbb{R}^{2}$
\end_inset

 in terms of the atoms 
\begin_inset Formula $\mathbf{u}$
\end_inset

 and 
\begin_inset Formula $\mathbf{v}$
\end_inset

 of the dictionary 
\begin_inset Formula $\mathcal{D}$
\end_inset

.
 We might similarly consider the two-dimensional Haar wavelet basis on the
 space of real, 
\begin_inset Formula $2\times2$
\end_inset

 matrices, whose elements can be used to encode images.
 In place of a predefined dictionary, we may also choose to learn a dictionary
 directly from the signal of interest, a procedure that has been shown,
 e.g.
 by 
\begin_inset CommandInset citation
LatexCommand cite
key "Elad2006"

\end_inset

, to perform as well as or better than the predefined approach.
\end_layout

\begin_layout Standard
A signal 
\begin_inset Formula $\mathbf{x}\in\mathbb{R}^{m}$
\end_inset

 is said to have a 
\begin_inset Formula $k$
\end_inset


\emph on
-sparse representation
\emph default
 in a dictionary 
\begin_inset Formula $\mathcal{D}=\left\{ \mathbf{v}_{i}\right\} _{i\in\mathcal{I}}\subset\mathbb{R}^{m}$
\end_inset

 if there is a system of coefficients 
\begin_inset Formula $\left\{ c_{i}\right\} _{i\in\mathcal{I}}$
\end_inset

 such that 
\begin_inset Formula $\mathbf{x}=\sum_{i\in\mathcal{I}}c_{i}\mathbf{v}_{i}$
\end_inset

 and 
\begin_inset Formula $c_{i}\neq0$
\end_inset

 for at most 
\begin_inset Formula $k$
\end_inset

 many indices 
\begin_inset Formula $i\in\mathcal{I}$
\end_inset

.
 A sparse representation of 
\begin_inset Formula $\mathbf{x}$
\end_inset

 may be preferable to a 
\begin_inset Quotes eld
\end_inset

dense
\begin_inset Quotes erd
\end_inset

 representation (assuming that both representations have similar reconstruction
 performance) for two primary reasons.
 The first is the principle of parsimony (or model interpretability): if
 we can represent the signal with relatively few atoms (the coefficients
 of the remaining atoms being zero), our understanding of the signal is
 easier to characterize than if we had to interpret the effects of a larger
 number of atoms.
 That is, we have identified redundancy in the atoms relative to the signal.
 The second is computational efficiency: fewer nonzero coefficients means
 that we can represent and manipulate the signal using fewer resources.
 
\begin_inset CommandInset citation
LatexCommand cite
key "Elad2006"

\end_inset

 and others have shown sparse representions of natural signals to be very
 effective.
 Thus, our task in 
\emph on
dictionary learning
\emph default
 given some signal 
\begin_inset Formula $\mathbf{x}$
\end_inset

 is to learn a dictionary 
\begin_inset Formula $\mathcal{D}$
\end_inset

 such that 
\begin_inset Formula $\mathbf{x}$
\end_inset

 has a sparse representation in terms of the atoms of 
\begin_inset Formula $\mathcal{D}$
\end_inset

.
\end_layout

\begin_layout Subsection
Online learning
\end_layout

\begin_layout Standard
A dictionary is typically learned from a training set (possibly the signal
 to be reconstructed) using a constrained optimization procedure.
 We can implement this optimization as a 
\emph on
batch
\emph default
 procedure, wherein the entire training set is used at each iteration.
 While such methods have been shown to be effective, they do not scale well
 to very large training sets, or to training sets that vary over time, e.g.,
 streaming audio or video signals.
 
\begin_inset CommandInset citation
LatexCommand cite
key "Mairal2009"

\end_inset

 propose an 
\emph on
online
\emph default
 approach to overcome these limitations, wherein the elements of the training
 set are accessed one at a time or in small batches.
\end_layout

\begin_layout Standard
When learning a dictionary for a streaming signal, our approach must also
 account for the phenomenon of 
\emph on
concept drift
\emph default
, wherein the statistical properties of the signal change unpredictably
 over time.
 If our learning method does not allow the dictionary to adapt to these
 changes, then reconstruction performance will degrade as we attempt to
 represent portions of the signal that the dictionary has not previously
 
\begin_inset Quotes eld
\end_inset

seen.
\begin_inset Quotes erd
\end_inset

 For example, if we wish to respresent the video feed of a traffic camera,
 we are likely to learn a dictionary well suited to representing various
 motor vehicles.
 If the same street is closed for a parade, our dictionary is not likely
 to perform acceptably when reconstructing a marching band.
 
\begin_inset CommandInset citation
LatexCommand cite
key "Zhao2011"

\end_inset

 have shown that online algorithms are robust to concept drift precisely
 because they permit the dictionary to adapt to new phenomena.
\end_layout

\begin_layout Section
Methodology
\end_layout

\begin_layout Standard
Suppose that we wish to learn a dictionary for a signal 
\begin_inset Formula $\mathbf{x}\in\mathbb{R}^{m}$
\end_inset

.
 Let 
\begin_inset Formula $\mathbf{D}\in\mathbf{M}_{m,k}\left(\mathbb{R}\right)$
\end_inset

 be the matrix whose columns are the atoms (basis vectors) of the dictionary,
 and consider the loss function
\begin_inset Formula 
\[
l\left(\mathbf{x,}\mathbf{D}\right)\coloneqq\min_{\boldsymbol{\alpha}\in\mathbb{R}^{k}}\frac{1}{2}\left\Vert \mathbf{x}-\mathbf{D}\boldsymbol{\alpha}\right\Vert _{2}^{2}+\lambda\left\Vert \boldsymbol{\alpha}\right\Vert _{1},
\]

\end_inset

which is known as the Least Absolute Shrinkage and Selection Operator (LASSO),
 and where 
\begin_inset Formula $\lambda$
\end_inset

 is a regularization parameter.
 We see that 
\begin_inset Formula $l\left(\mathbf{x},\mathbf{D}\right)$
\end_inset

 optimizes the sum of the squared error in reconstructing 
\begin_inset Formula $\mathbf{x}$
\end_inset

 using the dictionary 
\begin_inset Formula $\mathbf{D}$
\end_inset

 and the 1-norm of the coefficient vector 
\begin_inset Formula $\boldsymbol{\alpha}$
\end_inset

.
 To avoid arbitrarily small values of 
\begin_inset Formula $\boldsymbol{\alpha}$
\end_inset

, we adopt the constraint that the basis vectors 
\begin_inset Formula $\left\{ \mathbf{d}_{j}\right\} _{j=1}^{k}$
\end_inset

 have 2-norm of at most one.
 Let 
\begin_inset Formula $\mathcal{C}$
\end_inset

 be the set of matrices satisfying this constraint, i.e., 
\begin_inset Formula 
\[
\mathcal{C}\coloneqq\left\{ \mathbf{D}\in\mathbf{M}_{m,k}\left(\mathbb{R}\right):\left\Vert \mathbf{d}_{j}\right\Vert _{2}\leq1\ \forall j\in\left\{ 1,2,\ldots,k\right\} \right\} ,
\]

\end_inset

so that the optimization becomes
\begin_inset Formula 
\begin{equation}
\min_{\mathbf{D}\in\mathcal{C},\boldsymbol{\alpha}\in\mathbb{R}^{k}}\frac{1}{2}\left\Vert \mathbf{x}-\mathbf{D}\boldsymbol{\alpha}\right\Vert _{2}^{2}+\lambda\left\Vert \boldsymbol{\alpha}\right\Vert _{1}.\label{eq:lasso}
\end{equation}

\end_inset

While this problem is not jointly convex, it is convex with respect to 
\begin_inset Formula $\mathbf{D}$
\end_inset

 and 
\begin_inset Formula $\boldsymbol{\alpha}$
\end_inset

 separately, so that a solution may be obtained by alternately optimizing
 one variable while the other is held constant, as proposed by 
\begin_inset CommandInset citation
LatexCommand cite
key "Lee2007"

\end_inset

.
\end_layout

\begin_layout Standard
Now suppose that we wish to learn a dictionary to represent a set of discrete
 
\emph on
samples
\emph default
 
\begin_inset Formula $\left\{ \mathbf{x}_{i}\right\} _{i=1}^{n}$
\end_inset

 of some analog signal, where 
\begin_inset Formula $n$
\end_inset

 is possibly unknown, as in the case of a streaming signal.
 Then, the optimization 
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:lasso"

\end_inset

 becomes
\begin_inset Formula 
\[
\min_{\mathbf{D}\in\mathcal{C},\boldsymbol{\alpha}\in\mathbf{M}_{k,n}\left(\mathbb{R}\right)}\frac{1}{n}\sum_{i=1}^{n}\left(\frac{1}{2}\left\Vert \mathbf{x}_{i}-\mathbf{D}\boldsymbol{\alpha}_{i}\right\Vert _{2}^{2}+\lambda\left\Vert \boldsymbol{\alpha}_{i}\right\Vert _{1}\right),
\]

\end_inset

which is equation (4) from 
\begin_inset CommandInset citation
LatexCommand cite
key "Mairal2009"

\end_inset

.
 The same authors propose a 
\emph on
mini-batch
\emph default
 extension of their algorithm 1 that considers 
\begin_inset Formula $\eta>1$
\end_inset

 samples at each iteration 
\begin_inset Formula $t\in\left\{ 1,2,\ldots T\right\} $
\end_inset

.
 We adopt this mini-batch method to process 
\begin_inset Formula $\eta$
\end_inset

 samples of a streaming signal at a time, alternating between optimizing
 
\begin_inset Formula $\boldsymbol{\alpha}$
\end_inset

 and 
\begin_inset Formula $\mathbf{D}$
\end_inset

.
 
\end_layout

\begin_layout Standard
As in 
\begin_inset CommandInset citation
LatexCommand cite
key "Zhao2011"

\end_inset

, we will learn an initial dictionary 
\begin_inset Formula $\mathbf{D}_{0}$
\end_inset

 using the first 
\begin_inset Formula $N$
\end_inset

 samples of the signal, then use a 
\emph on
sliding window
\emph default
 of width 
\begin_inset Formula $w$
\end_inset

 to obtain the samples 
\begin_inset Formula $\left\{ \mathbf{x}_{i}^{\left(t\right)}\right\} _{i=1}^{\eta}$
\end_inset

 for each iteration 
\begin_inset Formula $t$
\end_inset

.
 We then compute the reconstruction coefficients 
\begin_inset Formula $\boldsymbol{\alpha}_{t}$
\end_inset

 using Orthogonal Matching Pursuit (OMP) and use these coefficients to compute
 the updated dictionary 
\begin_inset Formula $\mathbf{D}_{t}$
\end_inset

 using Least Angle Regression (LARS), with 
\begin_inset Formula $\mathbf{D}_{t-1}$
\end_inset

 as a warm restart.
 Algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:online-dict-learning"

\end_inset

 presents our approach.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{algorithmic}[1]
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Require
\end_layout

\end_inset

 
\begin_inset Formula $\left\{ {\bf x}_{i}\right\} _{i=1}^{n}\in\mathbb{R}^{m}$
\end_inset


\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
 (set of signals), 
\begin_inset Formula $\lambda\in\mathbb{R}$
\end_inset

 (regularization parameter), 
\begin_inset Formula $\mathbf{D}_{0}\in\mathbf{M}_{m,k}\left(\mathbb{R}\right)$
\end_inset

 (initial dictionary), 
\begin_inset Formula $w$
\end_inset

 (sliding window width).
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Ensure
\end_layout

\end_inset

 learned dictionary 
\begin_inset Formula $\mathbf{D}_{T}$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Calculate the number of iterations 
\begin_inset Formula $T$
\end_inset

 and the number of samples per iteration 
\begin_inset Formula $\eta$
\end_inset

 based on the signal dimension 
\begin_inset Formula $m$
\end_inset

, the number of signals 
\begin_inset Formula $n$
\end_inset

, and the window width 
\begin_inset Formula $w$
\end_inset

.
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
For{$t=1$ to $T$}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Sparse coding: compute 
\begin_inset Formula $\boldsymbol{\alpha}_{t}$
\end_inset

 as in algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:omp"

\end_inset

 for the samples 
\begin_inset Formula $\left\{ \mathbf{x}_{i}^{\left(t\right)}\right\} _{i=1}^{\eta}$
\end_inset

.
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Dictionary update: compute 
\begin_inset Formula $\mathbf{D}_{t}$
\end_inset

 using LARS, with 
\begin_inset Formula $\mathbf{D}_{t-1}$
\end_inset

 as a warm restart.
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
EndFor
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Return{$
\backslash
mathbf{D}_{T}$}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{algorithmic}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "alg:online-dict-learning"

\end_inset

Online Dictionary Learning
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:omp"

\end_inset

 provides the coefficient update.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{algorithmic}[1]
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Require
\end_layout

\end_inset

 
\begin_inset Formula $\left\{ {\bf x}_{i}\right\} _{i=1}^{\eta}\in\mathbb{R}^{m}$
\end_inset


\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
 (set of samples), 
\begin_inset Formula $\lambda\in\mathbb{R}$
\end_inset

 (tolerance parameter), 
\begin_inset Formula $\mathbf{D}\in\mathbf{M}_{m,k}\left(\mathbb{R}\right)$
\end_inset

 (unit-norm dictionary).
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Ensure
\end_layout

\end_inset

 coefficients 
\begin_inset Formula $\boldsymbol{\alpha}\in\mathbf{M}_{k,\eta}\left(\mathbb{R}\right)$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
For{$i=1$ to $
\backslash
eta$}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 
\begin_inset Formula $\mathcal{I}\gets\emptyset$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 
\begin_inset Formula $\boldsymbol{\alpha}_{i}\gets\mathbf{0}$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 
\begin_inset Formula $\mathbf{r}=\mathbf{x}_{i}$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
While{$
\backslash
left
\backslash
Vert 
\backslash
mathbf{r}
\backslash
right
\backslash
Vert _{2}>
\backslash
lambda$}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 
\begin_inset Formula $i'\gets\argmax_{j\in\left[k\right]\setminus\mathcal{I}}\left|\left\langle \mathbf{r},\mathbf{d}_{j}\right\rangle \right|$
\end_inset

, where 
\begin_inset Formula $\mathbf{d}_{j}$
\end_inset

 is the 
\begin_inset Formula $j\text{th}$
\end_inset

 column of 
\begin_inset Formula $\mathbf{D}$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 
\begin_inset Formula $\mathcal{I}\gets\mathcal{I}\cup\left\{ i'\right\} $
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 
\begin_inset Formula $\mathcal{B}\gets\text{span}\left\{ \left\{ \mathbf{d}_{j}\right\} _{j\in\mathcal{I}}\right\} $
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 
\begin_inset Formula $\boldsymbol{\alpha}_{i}\gets\Pi_{\mathcal{B}}\left(\mathbf{x}_{i}\right)$
\end_inset

, where 
\begin_inset Formula $\Pi_{\mathcal{B}}\left(\mathbf{x}_{i}\right)$
\end_inset

 is the projection of 
\begin_inset Formula $\mathbf{x}_{i}$
\end_inset

 onto 
\begin_inset Formula $\mathcal{B}$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 
\begin_inset Formula $\mathbf{r}\gets\mathbf{x}_{i}-\boldsymbol{\alpha}_{i}$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
EndWhile
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
EndFor
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Return{$
\backslash
boldsymbol{
\backslash
alpha}$}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{algorithmic}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "alg:omp"

\end_inset

Orthogonal Matching Pursuit
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
As the window slides along the set of signals, the optimization at each
 iteration will produce a dictionary that is 
\emph on
adaptive
\emph default
, i.e., it can learn to represent new signal behavior, and given some specified
 number of atoms, can also 
\begin_inset Quotes eld
\end_inset

forget
\begin_inset Quotes erd
\end_inset

 previously observed signal behavior that becomes rare or ceases to occur
 altogether after some specified time.
 In this way, our approach accommodates concept drift.
\end_layout

\begin_layout Subsection
Unusual event detection
\end_layout

\begin_layout Standard
As the window slides along the set of signals, we will update our dictionary
 as described in the previous section.
 When we slide to the 
\begin_inset Formula $\left(t+1\right)\text{th}$
\end_inset

 window composed of samples 
\begin_inset Formula $\left\{ \mathbf{x}_{i}^{\left(t+1\right)}\right\} _{i=1}^{\eta}$
\end_inset

, we will use our dictionary from the previous window 
\begin_inset Formula $\mathbf{D}_{t}$
\end_inset

 to reconstruct the samples.
 If the 
\begin_inset Formula $\left(t+1\right)\text{th}$
\end_inset

 window is 
\emph on
unusual
\emph default
, i.e., it represents signal behavior that is either rare or novel, then our
 dictionary will not be able to represent it accurately (the dictionary
 will lack elements well-suited to approximating the new behavior).
 In this case, and following 
\begin_inset CommandInset citation
LatexCommand cite
key "Zhao2011"

\end_inset

, we expect that either a greater number of atoms will be required to reconstruc
t the samples for a specified reconstruction error, or that the error in
 reconstruction will increase for some desired sparsity 
\begin_inset Formula $k$
\end_inset

.
 In particular, we observe that this method is 
\emph on
unsupervised
\emph default
 insofar as we have given no prior definition for what constitutes an unusual
 event; we have not even provided prior information regarding the signal
 class.
\end_layout

\begin_layout Standard
\begin_inset CommandInset citation
LatexCommand cite
key "Zhao2011"

\end_inset

 determine the 
\begin_inset Quotes eld
\end_inset

normality
\begin_inset Quotes erd
\end_inset

 of an event 
\begin_inset Formula $\mathbf{X}_{i}=\left\{ \mathbf{X}_{i}^{1},\ldots,\mathbf{X}_{i}^{n_{i}}\right\} $
\end_inset

 by computing the objective function 
\begin_inset Formula 
\[
J\left(\mathbf{X}_{i},\boldsymbol{\alpha}_{i},\mathbf{D}\right)\coloneqq\frac{1}{2}\sum_{j=1}^{n_{i}}\left\Vert \mathbf{X}_{i}^{j}-\mathbf{D}\boldsymbol{\alpha}_{i}^{j}\right\Vert _{2}^{2}+\lambda_{1}\sum_{j=1}^{n_{i}}\left\Vert \boldsymbol{\alpha}^{j}\right\Vert _{1}+\lambda_{2}\sum_{j=1}^{n_{i}}\sum_{k=1}^{n_{i}}\mathbf{W}_{jk}\left\Vert \boldsymbol{\alpha}_{i}^{j}-\boldsymbol{\alpha}_{i}^{k}\right\Vert _{2}^{2},
\]

\end_inset

where 
\begin_inset Formula $\boldsymbol{\alpha}_{i}=\left\{ \boldsymbol{\alpha}_{i}^{1},\ldots,\boldsymbol{\alpha}_{i}^{n_{i}}\right\} $
\end_inset

 are the reconstruction weight vectors (coefficients), 
\begin_inset Formula $\mathbf{D}$
\end_inset

 is the current dictionary, 
\begin_inset Formula $\mathbf{W}$
\end_inset

 is the adjacency matrix of 
\begin_inset Formula $\mathbf{X}_{i}$
\end_inset

, and 
\begin_inset Formula $\lambda_{1},\lambda_{2}\in\mathbb{R}$
\end_inset

 are regularization parameters.
 The first term gives the (squared) reconstruction error, the second term
 implements sparsity regularization, and the third term implements 
\begin_inset Quotes eld
\end_inset

smoothness
\begin_inset Quotes erd
\end_inset

 regularization, which arises from the authors' application to video signals.
 Then, a newly observed event 
\begin_inset Formula $\mathbf{X}'$
\end_inset

 with reconstruction weight vectors 
\begin_inset Formula $\boldsymbol{\alpha}'$
\end_inset

 learned using the current dictionary 
\begin_inset Formula $\mathbf{D}$
\end_inset

 is said to be unusual if 
\begin_inset Formula $J\left(\mathbf{X'},\boldsymbol{\alpha}',\mathbf{D}\right)$
\end_inset

 is greater than some specified threshold 
\begin_inset Formula $\varepsilon$
\end_inset

.
\end_layout

\begin_layout Standard
It may not be necessary to implement smoothness regularization for other
 signal classes, e.g., audio, and in practice we find that the reconstruction
 sum of squared errors (SSE) tends to dominate the sparsity regularization.
 Thus, for each iteration 
\begin_inset Formula $t$
\end_inset

, we will compute the reconstruction SSE and define an event to be unusual
 if the SSE for the 
\begin_inset Formula $t\text{th}$
\end_inset

 iteration is greater than a specified threshold.
\end_layout

\begin_layout Section
Application
\end_layout

\begin_layout Subsection
Overview
\end_layout

\begin_layout Standard
To test the strengths of online dictionary learning for detecting change
 points, we apply the concept of initial dictionary learning with sequential
 dictionary update to an audio signal.
 As stated above, we hypothesize that the reconstruction of a signal window
 with the dictionary learned prior will perform poorly if new elements were
 encountered during that window (e.g.
 new instruments, key changes, etc.).
 This will result in a spike in the reconstruction error for that window,
 allowing for the identification of change points.
 For a test case, we consider the song 
\begin_inset Quotes eld
\end_inset

Bohemian Rhapsody
\begin_inset Quotes erd
\end_inset

 by the British rock band, Queen, due to its frequent, noticeable (to the
 human ear) changes in style, range, and tempo.
\end_layout

\begin_layout Standard
Online dictionary learning seems well suited to this application since the
 sequential updates to the dictionary inherently provide a temporal aspect
 to the learning and reconstruction process.
 If a dictionary were instead learned on the entire song, the major change
 points might be masked since the dictionary 
\begin_inset Quotes eld
\end_inset

knows
\begin_inset Quotes erd
\end_inset

 what comes after.
 With online learning, however, the dictionary has no 
\emph on
a priori
\emph default
 information on what features will be in the next signal window, so is better
 suited to identify changes.
\end_layout

\begin_layout Subsection
Audio signal structure
\end_layout

\begin_layout Standard
Analog audio is continuous as a function of time, so is digitized by taking
 discrete 
\emph on
samples
\emph default
.
 The basic properties of this digitization include:
\end_layout

\begin_layout Itemize
Each sample quantifies the 
\emph on
amplitude
\emph default
 of the signal at a point in time.
\end_layout

\begin_layout Itemize
The 
\emph on
sampling rate
\emph default
 is the average number of samples obtained in one second.
 
\end_layout

\begin_layout Itemize
The resolution of each sample corresponds to the number of possible values
 of the amplitude, which is given by the 
\emph on
bit depth
\emph default
.
\end_layout

\begin_layout Itemize
The number of 
\emph on
channels
\emph default
 used to represent a signal correspond to separate data streams that must
 be sampled.
\end_layout

\begin_layout Standard
For our application, we obtained an uncompressed, 16,000 Hz (sampling rate),
 16-bit (bit depth), monaural (1 channel) waveform audio file (WAV) for
 
\begin_inset Quotes eld
\end_inset

Bohemian Rhapsody.
\begin_inset Quotes erd
\end_inset

 At 16-bit depth, amplitudes range from 
\begin_inset Formula $-2^{15}$
\end_inset

 to 
\begin_inset Formula $2^{15}-1$
\end_inset

, so pre-processing the signal involves normalizing these amplitudes to
 range from -1 to 1.
 
\end_layout

\begin_layout Subsection
Unusual event identification
\end_layout

\begin_layout Standard
For comparison with the peaks in the reconstruction errors and assessing
 the performance of our implementation of online learning, we examined the
 sheet music of 
\begin_inset Quotes eld
\end_inset

Bohemian Rhapsody,
\begin_inset Quotes erd
\end_inset

 i.e., 
\begin_inset Quotes eld
\end_inset

ground truth,
\begin_inset Quotes erd
\end_inset

 for major musical changes and mapped them to timepoints in our audio, see
 
\begin_inset CommandInset ref
LatexCommand formatted
reference "tab:unusual-events"

\end_inset

.
 The song begins in 4/4 time in the key of B-flat major.
 Two key changes occur, as well as frequent meter and instrumentation changes,
 providing numerous opportunities to assess the algorithm's performance.
 
\end_layout

\begin_layout Standard
\begin_inset Float table
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="18" columns="2">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top" width="0pt">
<row topspace="default">
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Time
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Description
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0:07
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
meter change (5/4)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0:11
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
meter change (4/4)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0:15
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
new instrument (piano)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0:38
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
new instrument (cymbal swell)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0:48
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
new instrument (bass)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1:23
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
new instrument (set)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1:43
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
meter change (2/4)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1:45
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
meter change (4/4)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
2:19
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
new instrument (guitar)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
2:34
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
guitar solo
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3:01
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
end guitar solo, key change (A major)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3:04
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
lead vocals rejoin
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3:07
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
backing vocals rejoin
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3:22
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
key change (E-flat major)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3:24
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
bass, set rejoin
\end_layout

\end_inset
</cell>
</row>
<row topspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
4:05
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
meter change (12/8)
\end_layout

\end_inset
</cell>
</row>
<row topspace="default" bottomspace="default">
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
4:13
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
vocals rejoin
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "tab:unusual-events"

\end_inset

Unusual events in 
\begin_inset Quotes eld
\end_inset

Bohemian Rhapsody
\begin_inset Quotes erd
\end_inset

 
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Implementation
\begin_inset CommandInset label
LatexCommand label
name "subsec:Implementation"

\end_inset


\end_layout

\begin_layout Standard
The algorithms discussed in 
\begin_inset CommandInset citation
LatexCommand cite
key "Mairal2009"

\end_inset

 have been implemented in the 
\family typewriter
MiniBatchDictionaryLearning
\family default
 class of Python's 
\family typewriter
\series bold
scikit-learn
\family default
\series default
 library, so could be readily utilized for our application.
 However, our use case requires a hybrid implementation of the two methodologies
 of 
\begin_inset CommandInset citation
LatexCommand cite
key "Mairal2009"

\end_inset

 and 
\begin_inset CommandInset citation
LatexCommand cite
key "Zhao2011"

\end_inset

.
 
\end_layout

\begin_layout Standard
\begin_inset CommandInset citation
LatexCommand cite
key "Mairal2009"

\end_inset

 contains the description and recommendations for applying the basic online
 learning framework to vector data (by vectorizing image data), similar
 to the format of the monaural channel audio signal involved in this effort,
 but utilizes random sampling of the images.
 
\begin_inset CommandInset citation
LatexCommand cite
key "Zhao2011"

\end_inset

 uses online learning to detect unusual events in video, paralleling our
 application well, and details the use of a sliding window during processing,
 rather than random samples.
 Further guidance is provided by the application of online learning to speech
 samples in 
\begin_inset CommandInset citation
LatexCommand cite
key "Santos2014"

\end_inset

, which directly addresses processing audio.
 The final Python code is contained in Appendix 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:python-code"

\end_inset

, and the basic structure is detailed in the pseudocode of Algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:pseudo-python"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement h
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{algorithmic}[1]
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Require
\end_layout

\end_inset

 
\begin_inset Formula $\mathbf{y}\in\mathbb{R}^{M}$
\end_inset


\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
 (audio signal, WAV format, 16,000 Hz, monoaural channel), 
\begin_inset Formula $k\in\mathbb{N}$
\end_inset

 (number of dictionary components)
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Reshape 
\begin_inset Formula $\mathbf{y}$
\end_inset

 to 
\begin_inset Formula $\mathbf{Y}\in\mathbf{M}_{k,n}\left(\mathbb{R}\right)$
\end_inset

, where 
\begin_inset Formula $n=\left\lfloor M/k\right\rfloor $
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 INITIAL TRAINING
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Extract initial training set: 
\series bold

\begin_inset Formula $\mathbf{X}_{0}=\left\{ \mathbf{Y}_{\mathcal{I}}\right\} $
\end_inset


\series default
, where 
\begin_inset Formula $\mathcal{I}\in\left\{ 1,2,...,N\right\} $
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Learn the initial dictionary 
\begin_inset Formula $\mathbf{D}_{0}\in\mathbf{M}_{k,k}\left(\mathbb{R}\right)$
\end_inset

 from 
\begin_inset Formula $\mathbf{X}_{0}$
\end_inset

 using least angle regression (LARS) to compute the LASSO solution
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Compute the reconstruction matrix 
\begin_inset Formula $\boldsymbol{\alpha}_{0}\in\mathbf{M}_{k,N}\left(\mathbb{R}\right)$
\end_inset

 using Orthogonal Matching Pursuit (OMP) with 
\begin_inset Formula $\mathbf{D}_{0}$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Reconstruct the training set data and vectorize: 
\begin_inset Formula $\mathbf{\widehat{X}}_{0}=\mathbf{D}_{0}\boldsymbol{\alpha}_{0}\Rightarrow\hat{\mathbf{x}}_{0}\in\mathbb{R}^{Nk}$
\end_inset

 
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 ONLINE LEARNING
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 
\begin_inset Formula $T=k\left(n-N\right)/\left(16,000w\right)$
\end_inset

, where 
\begin_inset Formula $w$
\end_inset

 is the length of each sample window in seconds
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset


\begin_inset Formula $\eta=16000w/k$
\end_inset

, the number of vectors to extract 
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
For{$t=1$ to $T$}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Extract 
\begin_inset Formula $\mathbf{X}_{t}=\left\{ \mathbf{Y}_{\mathcal{I}}\right\} $
\end_inset

, where 
\begin_inset Formula $\mathcal{I}\in\left\{ N+1+(t-1)\eta,...,N+1+t\eta\right\} $
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Compute the reconstruction matrix 
\begin_inset Formula $\boldsymbol{\alpha}_{t}\in\mathbf{M}_{k,\eta}\left(\mathbb{R}\right)$
\end_inset

 with 
\begin_inset Formula $\mathbf{D}_{t-1}$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Reconstruct the window of data and vectorize: 
\begin_inset Formula $\mathbf{\widehat{X}}_{t}=\mathbf{D}_{t-1}\boldsymbol{\alpha}_{t}\Rightarrow\hat{\mathbf{x}}_{t}\in\mathbb{R}^{\eta k}$
\end_inset

 , append to previous reconstructions
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Compute the sum of squared errors (SSE), 
\begin_inset Formula $SSE_{t}=\left\Vert \mathbf{x}_{t}-\hat{\mathbf{x}}_{t}\right\Vert _{2}^{2}$
\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
State
\end_layout

\end_inset

 Update dictionary, 
\begin_inset Formula $\mathbf{D}_{t-1}\Rightarrow\mathbf{D}_{t}$
\end_inset

, using 
\begin_inset Formula $\mathbf{D}_{t-1}$
\end_inset

 as a warm restart
\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
EndFor
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Return{$
\backslash
mathbf{SSE}$ (Reconstruction Errors), 
\backslash
textbf{Reconstructed audio}}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{algorithmic}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "alg:pseudo-python"

\end_inset

Change Point Detection with Online Dictionary Learning
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Optimization of the algorithm runtime was initiated with recommendations
 from the literature, which were modified empirically until performance
 was improved to acceptable runtimes.
 The following parameters required empirical optimization:
\end_layout

\begin_layout Itemize

\series bold
Sparsity controlling parameter of Equation 
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:lasso"

\end_inset

:
\series default
 Due to the length of the signals used during online learning, the suggested
 value in 
\begin_inset CommandInset citation
LatexCommand cite
key "Mairal2009"

\end_inset

 of 
\begin_inset Formula $1.2/\sqrt{m}$
\end_inset

 did not perform well and was changed back to the default value of 1.
\end_layout

\begin_layout Itemize

\series bold
Number of iterations to perform during each training window: 
\series default
Reduced to 200 from the default of 1000 to improve runtime.
\end_layout

\begin_layout Itemize

\series bold
Algorithm used to fit the dictionary to the input signal:
\series default
 least angle regression (LARS, default); the coordinate descent alternative
 performed much more slowly.
\end_layout

\begin_layout Itemize

\series bold
Algorithm used to transform the input signal and generate the reconstruction
 vector: 
\series default
orthogonal matching pursuit (OMP); LASSO-LARS was also tested but performed
 much more slowly.
\end_layout

\begin_layout Itemize

\series bold
The tolerance parameter of the OMP algorithm: 
\series default
Set to 0.001 to ensure strong reconstruction.
\end_layout

\begin_layout Itemize

\series bold
Window size: 
\series default
The window size is of particular concern because it directly affects the
 time resolution of our ability to detect unusual events.
 That is, by having a window size that was too large, it would be difficult
 to identify the true location of changes, since a single window could potential
ly contain multiple novel musical features.
 These features would be learned in one iteration of the algorithm, but
 recorded using only a single error value, inhibiting change point detection.
 However, runtime prevented the use of a window that was too narrow.
 We chose a window size of 2 seconds to obtain an acceptably short runtime
 while maintaining adequate resolution.
\end_layout

\begin_layout Itemize

\series bold
Number of dictionary components extracted: 
\series default
500, a value that provided a good trade-off between runtime performance
 and strong reconstruction capabilities.
\end_layout

\begin_layout Standard
We implemented this algorithm on one core of an Intel Xeon 2.00GHz CPU and
 96 GB of RAM.
 Initial dictionary training on the first 10 seconds of the song, i.e.
 
\begin_inset Formula $\mathbf{X}_{0}\in\mathbf{M}_{320,500}\left(\mathbb{R}\right)$
\end_inset

, took 44 seconds.
 The online dictionary learning with a window size of 2 seconds, i.e.
 
\begin_inset Formula $\mathbf{X}_{t}\in\mathbf{M}_{64,500}\left(\mathbb{R}\right)$
\end_inset

, cycled through 172 windows to complete the song, taking 163 minutes total.
\end_layout

\begin_layout Section
Discussion
\end_layout

\begin_layout Subsection
Results
\end_layout

\begin_layout Standard
Figure 
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
ref{fig:sse}
\end_layout

\end_inset

 plots the sum of squared errors in reconstructing the signal in each 2-second
 window using the dictionary learned during the previous window.
 The 
\begin_inset Quotes eld
\end_inset

epochs
\begin_inset Quotes erd
\end_inset

 in the song are displayed based on 
\begin_inset CommandInset citation
LatexCommand cite
key "wiki:xxx"

\end_inset

, and the key and instrumental changes are as in 
\begin_inset CommandInset ref
LatexCommand formatted
reference "tab:unusual-events"

\end_inset

.
 We also plot the 75th and 90th percentiles of the SSE.
 
\family sans
R
\family default
 code to reproduce this figure is contained in Appendix 
\begin_inset CommandInset ref
LatexCommand ref
reference "sec:r-code"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout

<<sse, echo = F, fig.height = 3.5, fig.width = 5.5, fig.align = 'center', fig.pos
 = 'h', fig.cap = 'Reconstruction error for test data'>>=
\end_layout

\begin_layout Plain Layout

dat <- read.csv("sse_sparsity_objective.csv", header = F)
\end_layout

\begin_layout Plain Layout

colnames(dat) <- c("SSE","sparsity","J") 
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

sf <- stepfun(x = (seq_along(dat$SSE) - 1) * 2, y = c(0, dat$SSE))
\end_layout

\begin_layout Plain Layout

par(mgp = c(1.5,0.5,0), mar = c(2,1,3,0))
\end_layout

\begin_layout Plain Layout

plot(sf, do.points = F, main = NA, cex.lab = 0.75, cex.axis = 0.75,
\end_layout

\begin_layout Plain Layout

     xlab = NA, ylab = NA, xaxt = "n", yaxt = "n", frame.plot = F,
\end_layout

\begin_layout Plain Layout

     xaxs = "i")
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

z <- (seq_along(dat$SSE) - 1) * 2
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

sec <- z + 10 
\end_layout

\begin_layout Plain Layout

labs <- c("00:10", 
\end_layout

\begin_layout Plain Layout

          paste(sprintf("%02d", sec[sec %% 30 == 0] %/% 60), 
\end_layout

\begin_layout Plain Layout

                c("30", "00"), sep = ":"))
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

axis(side = 1, at = c(0, z[z %% 30 == 0][-1] - 10), 
\end_layout

\begin_layout Plain Layout

     labels = labs, cex.axis = 0.6)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

labs.epoch <- c("intro", "ballad", "solo", "opera",
\end_layout

\begin_layout Plain Layout

                "hard rock", "outro")
\end_layout

\begin_layout Plain Layout

sec.epoch <- c(-10, 38, 144, 171, 235, 284)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

mtext("epoch", side = 3, line = 2, cex = 0.6, at = -40, adj = 0, font = 2)
\end_layout

\begin_layout Plain Layout

for(i in seq_along(labs.epoch)) {
\end_layout

\begin_layout Plain Layout

  mtext(labs.epoch[i], side = 3, line = 2, cex = 0.6, 
\end_layout

\begin_layout Plain Layout

        at = sec.epoch[i], adj = 0)
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

labs.key <- c("B-flat maj", "A maj", "E-flat maj")
\end_layout

\begin_layout Plain Layout

sec.key <- c(-10, 171, 192)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

mtext("key", side = 3, line = 1, cex = 0.6, at = -40, adj = 0, font = 2)
\end_layout

\begin_layout Plain Layout

for(i in seq_along(labs.key)) {
\end_layout

\begin_layout Plain Layout

  mtext(labs.key[i], side = 3, line = 1, cex = 0.6, 
\end_layout

\begin_layout Plain Layout

        at = sec.key[i], adj = 0)
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

labs.inst <- c("vox", "piano", "bass", "set", "guitar", "vox", 
\end_layout

\begin_layout Plain Layout

              "bass/set", "vox")
\end_layout

\begin_layout Plain Layout

sec.inst <- c(-10, 5, 38, 73, 129, 174, 194, 243)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

mtext("instru-
\backslash
nment", line = -0.5, side = 3, cex = 0.6, at = -40, 
\end_layout

\begin_layout Plain Layout

      adj = 0, font = 2)
\end_layout

\begin_layout Plain Layout

for(i in seq_along(labs.inst)) {
\end_layout

\begin_layout Plain Layout

  mtext(labs.inst[i], side = 3, cex = 0.6, at = sec.inst[i], adj = 0)
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

col.qt <- c("red", "blue")
\end_layout

\begin_layout Plain Layout

lty.qt <- 2:3
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

legend("topright", legend = c("90th", "75th"), col = rev(col.qt), 
\end_layout

\begin_layout Plain Layout

       lty = rev(lty.qt), bty = "n", cex = 0.6,
\end_layout

\begin_layout Plain Layout

       title = "SSE percentiles")
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

eps <- quantile(x = dat$SSE, probs = c(0.75, 0.9))
\end_layout

\begin_layout Plain Layout

abline(h = eps, col = col.qt, lty = lty.qt)
\end_layout

\begin_layout Plain Layout

@
\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Unusual event detection requires that we choose some threshold 
\begin_inset Formula $\varepsilon$
\end_inset

, such that any window with reconstruction error greater than 
\begin_inset Formula $\varepsilon$
\end_inset

 is said to contain unusual signal behavior.
 We see that at the 90th percentile of SSE (corresponding to 
\begin_inset Formula $\varepsilon_{90}\approx\Sexpr{round(eps[2],0)}$
\end_inset

), we would classify as unusual 
\end_layout

\begin_layout Itemize
the initial appearance of the guitar,
\end_layout

\begin_layout Itemize
the ensuing guitar solo,
\end_layout

\begin_layout Itemize
the beginning of the 
\begin_inset Quotes eld
\end_inset

opera
\begin_inset Quotes erd
\end_inset

 epoch,
\end_layout

\begin_layout Itemize
and the simultaneous key change to E-flat major and reintroduction of the
 bass guitar and drum set.
\end_layout

\begin_layout Standard
We also observe several windows with reconstruction error greater than 
\begin_inset Formula $\varepsilon_{90}$
\end_inset

, which may represent 
\emph on
false positives
\emph default
, or possibly actual unusual events not considered in the limited classification
 of 
\begin_inset CommandInset ref
LatexCommand formatted
reference "tab:unusual-events"

\end_inset

.
 Further, we do 
\emph on
not
\emph default
 detect as unusual the initial appearances of the piano, bass, and drum
 set.
\end_layout

\begin_layout Standard
At the 75th percentile of SSE (corresponding to 
\begin_inset Formula $\varepsilon_{75}\approx\Sexpr{round(eps[1],0)}$
\end_inset

), we would classify as unusual all the events classified at the 90th percentile
, as well as
\end_layout

\begin_layout Itemize
the initial appearance of the piano,
\end_layout

\begin_layout Itemize
the initial appearance of the drum set,
\end_layout

\begin_layout Itemize
the reappearance of vocals during the 
\begin_inset Quotes eld
\end_inset

hard rock
\begin_inset Quotes erd
\end_inset

 epoch,
\end_layout

\begin_layout Itemize
and the beginning of the 
\begin_inset Quotes eld
\end_inset

outro
\begin_inset Quotes erd
\end_inset

 epoch.
\end_layout

\begin_layout Standard
The false positive rate will go to 100% as 
\begin_inset Formula $\varepsilon$
\end_inset

 goes to zero because we are reconstructing the signal from a limited dictionary
 and have explicitly favored sparse reconstructions, i.e., those with a higher
 number of zero coefficients.
 It is thus unsurprising that we observe more false positives at the 75th
 percentile than at the 90th percentile.
 The unusual events that we detect at the 75th percentile, but not at the
 90th percentile, may also be better represented by the dictionary learned
 during the previous window.
 For example, that we detect the initial appearance of the piano only at
 
\begin_inset Formula $\varepsilon_{75}$
\end_inset

 is possibly explained by the similar range during the 
\begin_inset Quotes eld
\end_inset

intro
\begin_inset Quotes erd
\end_inset

 epoch of the piano arrangement and the human voice, where the latter constitute
s the bulk of the training data available to the dictionary upon the introductio
n of the piano.
\end_layout

\begin_layout Standard
Thus, we observe reasonable performance from the algorithm on 
\begin_inset Quotes eld
\end_inset

Bohemian Rhapsody.
\begin_inset Quotes erd
\end_inset

 In particular, we successfully detect both the guitar solo and the opera
 epoch, which are two of the most identifiable passages from the song.
 The algorithm also successfully and quickly learns these new features,
 and the error drops when similar data are encountered in the subsequent
 windows.
 This is clear from the plot of the SSE, Figure 
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
ref{fig:sse}
\end_layout

\end_inset

, where we get spikes, rather than steady or increasing error as the song
 progresses.
 That the detection was performed in an unsupervised fashion makes the result
 that much more significant.
 Further application of this algorithm to a particular signal would likely
 require empirical tuning of the parameters and selection of an appropriate
 reconstruction error threshold.
\end_layout

\begin_layout Subsection
Next Steps
\end_layout

\begin_layout Standard
The concept of online dictionary learning is both flexible and powerful,
 so can be applied to a wide range of use cases and signal types.
 However, optimization to any one specific application does require extensive
 testing and tuning, as evidenced by the results detailed above.
 For example, further empirical testing of the seven parameters detailed
 in Section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Implementation"

\end_inset

 would be required before finding optimal performance in both runtime and
 reconstruction behavior.
 Eventually, as 
\begin_inset CommandInset citation
LatexCommand cite
key "Zhao2011"

\end_inset

 did, our application might require a modification to the underlying objective
 function utilized by the algorithms in 
\begin_inset CommandInset citation
LatexCommand cite
key "Mairal2009"

\end_inset

.
 This would require forgoing the use of the functions available in Python's
 
\family typewriter
\series bold
scikit-learn
\family default
\series default
 library, and instead necessitate building code from first principles.
 Similarly, other error measures could be developed to improve change point
 detection performance, rather than relying strictly on a threshold of the
 sum of the squared error.
\end_layout

\begin_layout Standard
In addition to optimization work, this use case readily suggests extensions
 in multiple directions.
 For example:
\end_layout

\begin_layout Itemize
Classification of change point types (e.g.
 instrument entrance/exit, key change, etc)
\end_layout

\begin_layout Itemize
Classification of song elements (e.g.
 highly specific genre/characteristics, a la Pandora's music genome project)
\end_layout

\begin_layout Itemize
Using a learned dictionary on one song to compress other songs by the same
 artist or in the same genre
\end_layout

\begin_layout Itemize
Using a learned dictionary to predict a song's popularity
\end_layout

\begin_layout Standard
Each of these applications could leverage the past work done on sparse represent
ations, dictionary learning, and online processing techniques to develop
 new algorithms and further the cutting-edge of signal processing technology.
\end_layout

\begin_layout Standard
\begin_inset CommandInset bibtex
LatexCommand bibtex
bibfiles "library"
options "apalike"

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage clearpage
\end_inset


\end_layout

\begin_layout Section
\start_of_appendix
\begin_inset CommandInset label
LatexCommand label
name "sec:python-code"

\end_inset

Python implementation
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout

<<eval = F, engine = 'python'>>=
\end_layout

\begin_layout Plain Layout

import numpy as np
\end_layout

\begin_layout Plain Layout

from sklearn.decomposition import MiniBatchDictionaryLearning
\end_layout

\begin_layout Plain Layout

from scipy.io import wavfile
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

fs, data = wavfile.read("Bohemian_Rhapsody_16Khz_16bit_mono_cut.wav")
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# normalize sound pressure values to (-1, 1)
\end_layout

\begin_layout Plain Layout

data = data / 2.0**15
\end_layout

\begin_layout Plain Layout

data_len = data.shape[0]
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# initialize reconstruction vector
\end_layout

\begin_layout Plain Layout

recon = np.zeros(data_len)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# set training parameters & extract sample
\end_layout

\begin_layout Plain Layout

train_factor = 10
\end_layout

\begin_layout Plain Layout

end_train = fs * train_factor
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

n_components = 500         # number of atoms
\end_layout

\begin_layout Plain Layout

n_features = n_components  # choose a "square" dictionary
\end_layout

\begin_layout Plain Layout

n_samples_training = int(end_train / n_features)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

training_data_vec = data[0:end_train]  # 160,000 samples
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# reshape the training data to an array having dimensions
\end_layout

\begin_layout Plain Layout

# (n_samples, n_features) = (320,500)
\end_layout

\begin_layout Plain Layout

training_data = training_data_vec.reshape(n_samples_training, n_features)
 
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# build the initial dictionary 
\end_layout

\begin_layout Plain Layout

dico = MiniBatchDictionaryLearning(n_components = n_components,  
\end_layout

\begin_layout Plain Layout

                                   alpha = 1, n_iter = 200,
\end_layout

\begin_layout Plain Layout

                                   transform_algorithm = 'omp',
\end_layout

\begin_layout Plain Layout

                                   transform_alpha = 0.001)
\end_layout

\begin_layout Plain Layout

dico = dico.fit(training_data)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# reconstruct the training set with the initial dictionary
\end_layout

\begin_layout Plain Layout

D = dico.components_
\end_layout

\begin_layout Plain Layout

alpha = dico.transform(training_data)
\end_layout

\begin_layout Plain Layout

out = np.matmul(alpha, D).flatten()
\end_layout

\begin_layout Plain Layout

recon[0:end_train] = out
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# extract testing signal & set online learning parameters
\end_layout

\begin_layout Plain Layout

testing_data_vec = data[end_train:data_len]
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# window width in seconds
\end_layout

\begin_layout Plain Layout

window_width = 2
\end_layout

\begin_layout Plain Layout

window_samples = window_width * fs
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# length of the test signal in seconds
\end_layout

\begin_layout Plain Layout

sig_length = len(testing_data_vec) / fs
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# calculate the number of windows
\end_layout

\begin_layout Plain Layout

num_windows = int(sig_length / window_width)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# calculate n_samples
\end_layout

\begin_layout Plain Layout

n_samples_learn = int(window_samples / n_features)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# initialize SSE vector
\end_layout

\begin_layout Plain Layout

sse = np.zeros(num_windows)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

offset = end_train
\end_layout

\begin_layout Plain Layout

# begin online learning with SSE calculation
\end_layout

\begin_layout Plain Layout

for i in range(0, num_windows):
\end_layout

\begin_layout Plain Layout

    # windows do not overlap
\end_layout

\begin_layout Plain Layout

    start_idx = window_samples * i
\end_layout

\begin_layout Plain Layout

    end_idx = window_samples * (i + 1)
\end_layout

\begin_layout Plain Layout

    
\end_layout

\begin_layout Plain Layout

    # extract window of data; window_width = 2, so 32,000 samples
\end_layout

\begin_layout Plain Layout

    orig = testing_data_vec[start_idx:end_idx]
\end_layout

\begin_layout Plain Layout

    
\end_layout

\begin_layout Plain Layout

    # reshape the new data to an array of samples (64, 500)
\end_layout

\begin_layout Plain Layout

    new_data = orig.reshape(n_samples_learn, n_features)
\end_layout

\begin_layout Plain Layout

        
\end_layout

\begin_layout Plain Layout

    # learn optimal reconstruction vector (64, 500)
\end_layout

\begin_layout Plain Layout

    alpha = dico.transform(new_data)
\end_layout

\begin_layout Plain Layout

        
\end_layout

\begin_layout Plain Layout

    # compute SSE
\end_layout

\begin_layout Plain Layout

    out = np.matmul(alpha, D).flatten()
\end_layout

\begin_layout Plain Layout

    sse[i] = sum((out - orig)**2)
\end_layout

\begin_layout Plain Layout

    
\end_layout

\begin_layout Plain Layout

    # append to the reconstruction
\end_layout

\begin_layout Plain Layout

    recon[offset + start_idx:offset + end_idx] = out
\end_layout

\begin_layout Plain Layout

    
\end_layout

\begin_layout Plain Layout

    # update the dictionary
\end_layout

\begin_layout Plain Layout

    dico = dico.partial_fit(new_data)
\end_layout

\begin_layout Plain Layout

    D = dico.components_
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

# write out the SSE
\end_layout

\begin_layout Plain Layout

np.savetxt('sse.csv', sse.T, delimiter = ",")
\end_layout

\begin_layout Plain Layout

wavfile.write('recon.wav', fs, recon)
\end_layout

\begin_layout Plain Layout

@
\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage clearpage
\end_inset


\end_layout

\begin_layout Section
\begin_inset CommandInset label
LatexCommand label
name "sec:r-code"

\end_inset


\family sans
R
\family default
 code to plot SSE 
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout

<<eval = F>>=
\end_layout

\begin_layout Plain Layout

dat <- read.csv("sse.csv", header = F)
\end_layout

\begin_layout Plain Layout

colnames(dat) <- c("SSE") 
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

sf <- stepfun(x = (seq_along(dat$SSE) - 1) * 2, y = c(0, dat$SSE))
\end_layout

\begin_layout Plain Layout

par(mgp = c(1.5,0.5,0), mar = c(2,1,3,0))
\end_layout

\begin_layout Plain Layout

plot(sf, do.points = F, main = NA, cex.lab = 0.75, cex.axis = 0.75,
\end_layout

\begin_layout Plain Layout

     xlab = NA, ylab = NA, xaxt = "n", yaxt = "n", frame.plot = F,
\end_layout

\begin_layout Plain Layout

     xaxs = "i")
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

z <- (seq_along(dat$SSE) - 1) * 2
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

sec <- z + 10 
\end_layout

\begin_layout Plain Layout

labs <- c("00:10", 
\end_layout

\begin_layout Plain Layout

          paste(sprintf("%02d", sec[sec %% 30 == 0] %/% 60), 
\end_layout

\begin_layout Plain Layout

                c("30", "00"), sep = ":"))
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

axis(side = 1, at = c(0, z[z %% 30 == 0][-1] - 10), 
\end_layout

\begin_layout Plain Layout

     labels = labs, cex.axis = 0.6)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

labs.epoch <- c("intro", "ballad", "solo", "opera",
\end_layout

\begin_layout Plain Layout

                "hard rock", "outro")
\end_layout

\begin_layout Plain Layout

sec.epoch <- c(-10, 38, 144, 171, 235, 284)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

mtext("epoch", side = 3, line = 2, cex = 0.6, at = -40, adj = 0, font = 2)
\end_layout

\begin_layout Plain Layout

for(i in seq_along(labs.epoch)) {
\end_layout

\begin_layout Plain Layout

  mtext(labs.epoch[i], side = 3, line = 2, cex = 0.6, 
\end_layout

\begin_layout Plain Layout

        at = sec.epoch[i], adj = 0)
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

labs.key <- c("B-flat maj", "A maj", "E-flat maj")
\end_layout

\begin_layout Plain Layout

sec.key <- c(-10, 171, 192)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

mtext("key", side = 3, line = 1, cex = 0.6, at = -40, adj = 0, font = 2)
\end_layout

\begin_layout Plain Layout

for(i in seq_along(labs.key)) {
\end_layout

\begin_layout Plain Layout

  mtext(labs.key[i], side = 3, line = 1, cex = 0.6, 
\end_layout

\begin_layout Plain Layout

        at = sec.key[i], adj = 0)
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

labs.inst <- c("vox", "piano", "bass", "set", "guitar", "vox", 
\end_layout

\begin_layout Plain Layout

              "bass/set", "vox")
\end_layout

\begin_layout Plain Layout

sec.inst <- c(-10, 5, 38, 73, 129, 174, 194, 243)
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

mtext("instru-
\backslash
nment", line = -0.5, side = 3, cex = 0.6, at = -40, 
\end_layout

\begin_layout Plain Layout

      adj = 0, font = 2)
\end_layout

\begin_layout Plain Layout

for(i in seq_along(labs.inst)) {
\end_layout

\begin_layout Plain Layout

  mtext(labs.inst[i], side = 3, cex = 0.6, at = sec.inst[i], adj = 0)
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

col.qt <- c("red", "blue")
\end_layout

\begin_layout Plain Layout

lty.qt <- 2:3
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

legend("topright", legend = c("90th", "75th"), col = rev(col.qt), 
\end_layout

\begin_layout Plain Layout

       lty = rev(lty.qt), bty = "n", cex = 0.6,
\end_layout

\begin_layout Plain Layout

       title = "SSE percentiles")
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout

eps <- quantile(x = dat$SSE, probs = c(0.75, 0.9))
\end_layout

\begin_layout Plain Layout

abline(h = eps, col = col.qt, lty = lty.qt)
\end_layout

\begin_layout Plain Layout

@
\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\end_body
\end_document