\documentclass[jair,11pt,letterpaper]{article}

%packages

% supporting JAIR style
\usepackage{jair}
\usepackage{theapa}
%%
\usepackage{setspace}

\usepackage{url}
\usepackage{epsf}
\usepackage{graphicx}
\usepackage[usenames,dvipsnames]{color}
\usepackage{amsmath,amssymb}
\usepackage{graphics,epsfig}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% letters
\newcommand{\h}{\mathcal{H}}
\newcommand{\s}{\mathcal{S}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\Y}{\mathcal{Y}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\MMM}{\mathcal{M}}
\newcommand{\LLL}{\mathcal{L}}
\newcommand{\YYY}{\mathcal{Y}}
\newcommand{\UUU}{\mathcal{U}}
\newcommand{\VVV}{\mathcal{V}}
\newcommand{\HHH}{\mathcal{H}}
\newcommand{\TTT}{\mathcal{T}}
\newcommand{\Phat}{\hat{P}}
\newcommand{\PKT}{\hat{P}_{\textsc{kt}}}
\newcommand{\PCTW}{\hat{P}_{\textsc{ctw}}}
\newcommand{\eqdef}{\triangleq}
\newcommand{\todo}[1]{#1}
\newcommand{\rE}{\mathbf{E}}
\newcommand{\Var}{\mathbf{Var}}
\renewcommand{\Pr}{\mathbf{Pr}}

\newcommand{\paperURL}{\url{http://www.cs.technion.ac.il/~ronbeg/vmm}}

% Algs
\newcommand{\lz}{\textsc{lz78}}
\newcommand{\lzs}{\textsc{lz77}}
\newcommand{\ctw}{\textsc{ctw}}
\newcommand{\ppm}{\textsc{ppm}}
\newcommand{\ppmz}{\textsc{ppm-z}}
\newcommand{\ppmc}{\textsc{ppm-c}}
\newcommand{\ppmd}{\textsc{ppm-d}}
\newcommand{\ppmII}{\textsc{ppm-ii}}
\newcommand{\lzms}{\textsc{lz-ms}}
\newcommand{\pst}{\textsc{pst}}
\newcommand{\dctw}{\textsc{de-ctw}}
\newcommand{\bctw}{\textsc{bi-ctw}}
\newcommand{\simple}{\textsc{simple}}
\newcommand{\maxmin}{\textsc{max-min}}
\newcommand{\maxratio}{\textsc{max-ratio}}
\newcommand{\self}{\textsc{self-conf}}
\newcommand{\comb}{\textsc{comb}}
\newcommand{\alg}{\textsc{alg}}
\newcommand{\act}{\textsc{active}}
\newcommand{\ff}{\textsc{FF}}
\newcommand{\kff}{\textsc{kff}}
\newcommand{\rr}{\textsc{r-robin }}
\newcommand{\rand}{\textsc{rand}}
\newcommand{\Acc}{\textrm{Acc}}
\newcommand{\bbb}{\mathbf b}
\newcommand{\eee}{\mathbf e}
\renewcommand{\ggg}{\mathbf g}
\newcommand{\Deff}{\textrm{Deff}}
\newcommand{\parent}{\textrm{parent}}
\newcommand{\suffix}{\textrm{suffix}}
\newcommand{\sub}{\textrm{sub}}
\newcommand{\leaves}{\textrm{leaves}}
\newcommand{\leftchild}{\textrm{left}}
\newcommand{\rightchild}{\textrm{right}}
\newcommand{\veps}{\varepsilon}
\newcommand{\eps}{\epsilon}

% colors
\newcommand{\Red}{\color{red}}
\newcommand{\Blue}{\color{blue}}
\newcommand{\Green}{\color{green}}
\newcommand{\Black}{\color{black}}
\newcommand{\Magenta}{\color{Magenta}}
\newcommand{\rnote}[1]{{\Blue #1}}
\newcommand{\bnote}[1]{{\Red #1}}
\newcommand{\gnote}[1]{{\Red #1}}
\newcommand{\Rnote}[2]{\textcolor{red}{\textbf{Was:} #1}
  \textcolor{blue}{\textbf{Suggested Change:} #2}}

\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial  #2}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% starts here %

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% titles/headings
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Headings %
% \jairheading{Volume}{year}{page-page}
%\jairheading{22}{2004}{?-?}{05/04}{12/04}
\jairheading{22}{2004}{385-421}{05/04}{12/04}
\ShortHeadings{On Prediction Using Variable Order Markov Models}
{Begleiter, El-Yaniv \& Yona} \firstpageno{385}

% Title %
\title{On Prediction Using Variable Order Markov Models}
\author{\name Ron Begleiter \email ronbeg@cs.technion.ac.il
        \AND
        \name Ran El-Yaniv
        \email rani@cs.technion.ac.il\\
               \addr Department of Computer Science\\
            Technion - Israel Institute of Technology\\
            Haifa 32000, Israel
        \AND
        \name Golan Yona \email golan@cs.cornell.edu \\
       \addr Department of Computer Science\\
        Cornell University\\
        Ithaca, NY 14853, USA
}



\maketitle

\begin{abstract}
This paper is concerned with algorithms for prediction of discrete
sequences over a finite alphabet, using variable order Markov
models. The class of such algorithms is large and in principle
includes any lossless compression algorithm. We focus on six
prominent prediction algorithms, including Context Tree Weighting
(CTW), Prediction by Partial Match (PPM) and Probabilistic Suffix
Trees (PSTs). We discuss the properties of these algorithms and
compare their performance using real life sequences from three
domains: proteins, English text and music pieces. The comparison
is made with respect to prediction quality as measured by the
average log-loss. We also compare classification algorithms based
on these predictors with respect to a number of large protein
classification tasks. Our results indicate that a ``decomposed''
CTW (a variant of the CTW algorithm) and PPM outperform all other
algorithms in sequence prediction tasks. Somewhat surprisingly, a
different algorithm, which is a modification of the Lempel-Ziv
compression algorithm, significantly outperforms all algorithms on
the protein classification problems.
%The source code of all the algorithms we consider is available at \paperURL.
\end{abstract}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

Learning of sequential data continues to be a fundamental task and
a challenge in pattern recognition and machine learning.
Applications involving sequential data may require prediction of
new events, generation of new sequences, or decision making such
as classification of sequences or sub-sequences. The classic
application of discrete sequence prediction algorithms is
\emph{lossless compression} \shortcite{bell90text}, but there are
numerous other applications involving sequential data, which can
be directly solved based on effective prediction of discrete
sequences. Examples of such applications are biological sequence
analysis \cite{bejerano01variations}, speech and language
modeling \cite{SchutzeS94,RabinerJ93}, text analysis and
extraction \shortcite{allum00maximum} music generation and
classification \shortcite{Pachet02,dubnov03using}, hand-writing
recognition \cite{singer94dynamical} and behaviormetric
identification
\shortcite{ClarksonP01,nisenson03Towards}.\footnote{Besides such
applications, which directly concern sequences, there are other,
less apparent applications, such as image and texture analysis and
synthesis that can be solved based on discrete sequence prediction
algorithms; see, e.g., \shortcite{BarELW01}.}


The literature on prediction algorithms for discrete sequences is
rather extensive and offers various approaches to analyze and
predict sequences over finite alphabets. Perhaps the most commonly
used techniques are based on Hidden Markov Models (HMMs)
\cite{rabiner89aTutorial}. HMMs provide flexible structures that
can model complex sources of sequential data. However, dealing with
HMMs typically requires considerable understanding of and insight
into the problem domain in order to restrict possible model
architectures. Also, due to their flexibility, successful training
of HMMs usually requires very large training samples \cite<see hardness results of>[for learning HMMs]{abeM92}.

In this paper we focus on general-purpose prediction algorithms,
based on learning \emph{Variable order Markov Models (VMMs)} over
a finite alphabet $\Sigma$. Such algorithms attempt to learn
probabilistic finite state automata, which can model sequential
data of considerable complexity. In contrast to $N$-gram Markov
models, which attempt to estimate conditional distributions of the
form $P(\sigma | s)$, with $s \in \Sigma^N$ and $\sigma \in
\Sigma$, VMM algorithms learn such conditional distributions where
context lengths $|s|$ vary in response to the available statistics
in the training data. Thus, VMMs provide the means for capturing
both large and small order Markov dependencies based on the
observed data. Although in general less expressive than HMMs, VMM
algorithms have been used to solve many applications with notable
success. The simpler nature of VMM methods also makes them
amenable for analysis, and some VMM algorithms that we discuss
below enjoy tight theoretical performance guarantees, which in
general are not possible in learning using HMMs.

There is an intimate relation between prediction of discrete
sequences and lossless compression algorithms, where, in
principle, any lossless compression algorithm can be used for
prediction and vice versa \cite<see, e.g.,>{feder94relations}.
%Therefore, there are great many useful possibilities for
Therefore, there exist an abundance of options when choosing a
prediction algorithm. This multitude of possibilities poses a
problem for practitioners seeking a prediction algorithm for the
problem at hand.

Our goal in this paper is to consider a number of VMM methods and
compare their performance with respect to  a variety of practical
prediction tasks. We aim to provide useful insights into the
choice of a good general-purpose prediction algorithm. To this end
we selected six prominent VMM algorithms and considered sequential
data from three different domains: molecular biology, text and
music. We focus on a setting in which a learner has the start of
some sequence (e.g., a musical piece) and the goal is to generate a
model capable of predicting the rest of the sequence. We also
consider a scenario where the learner has a set of training
samples from some domain and the goal is to predict, as accurately
as possible, new sequences from the same domain. We measure
performance using log-loss (see below). This loss function, which
is tightly related to compression, measures the quality of
probabilistic predictions, which are required in many
applications.

In addition to these prediction experiments we examine the six VMM
algorithms with respect to a number of large protein
classification problems.  Protein classification is one of the
most important problems in computational molecular biology. Such
classification is useful for functional and structural
categorization of proteins, and may direct experiments to further
explore and study the functionality of proteins in the cell and
their interactions with other molecules.

In the prediction experiments, two of the VMM algorithms we
consider consistently achieve the best performance. These are the
`decomposed context tree weighting (CTW)' and `prediction by
partial match (PPM)' algorithms. CTW and PPM are well known in the
lossless compression arena as outstanding players. Our results
thus provide further evidence of the superiority of these
algorithms, with respect to new domains and two different
prediction settings. The results of our protein classification
experiments are rather surprising as both of these two excellent
predictors are inferior to an algorithm, which is obtained by
simple modifications of the prediction component of the well-known
Lempel-Ziv-78 compression algorithm \cite{LZ78,langdon83aNote}.
This rather new algorithm, recently proposed by
\citeA{nisenson03Towards}, is a consistent winner in the all the
protein classification experiments and achieves surprisingly good
results that may be of independent interest in protein analysis.


%we are still interested
%to gain some insights that may help in choosing VMM algorithms
%for practical purposes. Fortunately, as we later show, two of the algorithms
%we consider consistently perform significantly better than the others.


%Something about the theory of sequence prediction; there exists an optimal alg
%(nobody knows it). Various algs achieve optimal learning rate, but with rather large constants.
%Mention other models for analysis. Another question: Is it the case that the
%best performing algs have the best bounds?


This paper is organized as follows. We begin in Section~2 with
some preliminary definitions. In Section~3, we present six VMM
prediction algorithms. In Section~4, we present the experimental
setup. In Sections~5-6, we discuss the experimental results. Part
of the experimental related details are discussed in
Appendices~A-C. In Section~7, we discuss the related work. In
Section~8, we conclude by introducing a number of open problems
raised by this research. Note that the source code of all the algorithms we
consider is available at \paperURL.


\section{Preliminaries}
\label{sec:preliminaries}

Let $\Sigma$ be a finite alphabet. A learner is given a training sequence
$q_1^n = q_1 q_2 \cdots q_n$, where $q_i \in \Sigma$ and $q_i q_{i+1}$ is the
concatenation of $q_i$ and $q_{i+1}$.
%It is assumed that $x_1^n$ was emitted by
%some unknown Markov source $P$.
Based on $q_1^n$, the goal is to learn a model $\Phat$ that
provides a probability assignment for any future outcome given
some past. Specifically, for any ``context'' $s \in \Sigma^*$ and
symbol $\sigma \in \Sigma$ the learner should generate a
conditional probability distribution $\Phat(\sigma | s)$.

Prediction performance is measured via the
\emph{average log-loss} $\ell(\Phat,x_1^T)$ of $\Phat(\cdot | \cdot)$, with respect to a test sequence
$x_1^T = x_1 \cdots x_T$,
%given some ``history'' (or
%initial context) $x_{-h}x_{-h+1}\cdots x_{-1}x_0$,
\begin{equation}
\label{eq:logloss}
\ell(\Phat,x_1^T) = -\frac{1}{T}\sum_{i=1}^T \log \Phat(x_i|x_{1}\cdots x_{i-1}),
\end{equation}
where the logarithm is taken to base 2. Clearly, the average
log-loss is directly related to the likelihood $\Phat(x_1^T) =
\prod_{i=1}^T \Phat(x_i|x_{1}\cdots x_{i-1})$ and minimizing the
average log-loss is completely equivalent to maximizing a
probability assignment for the entire test sequence.

Note that the converse is also true.
A \emph{consistent} probability assignment $\Phat(x_1^T)$, for the entire
sequence,
which satisfies $\Phat(x_1^{t-1}) = \sum_{x_t \in \Sigma} \Phat(x_1\cdots x_{t-1} x_t)$,
for all $t=1,\ldots,T$, induces conditional probability assignments,
$$
\Phat(x_t|x_1^{t-1}) = \Phat(x_1^t)/\Phat(x_1^{t-1}), \ \ t=1,\ldots,T.
$$
Therefore, in the rest of the paper
we interchangeably consider  $\Phat$ as a conditional distribution or as a
complete (consistent) distribution of the test sequence $x_1^T$.

The log-loss has various meanings. Perhaps the most important one
is found in its equivalence to lossless compression. The quantity
$-\log \Phat(x_i|x_{1}\cdots x_{i-1})$, which is also called the
`self-information', is the ideal compression or ``code length'' of
$x_i$, in bits per symbol, with respect to the conditional
distribution $\Phat(X|x_{1}\cdots x_{i-1})$, and can be
implemented online (with arbitrarily small redundancy) using
arithmetic encoding \cite{rissanen79arithmetic}. Thus, the
average log-loss also measures the average compression rate of the
test sequence, when using the predictions generated by $\Phat$. In
other words, a small average log-loss over the $x_1^T$ sequence
implies a good compression of this sequence.\footnote{The converse
is also true: any compression algorithm can be translated into
probability assignment $\Phat$; see, e.g.,
\cite{rissanen84universal}.}
%weinberger94optimal}.}


Within a probabilistic setting, the log-loss has the following
meaning. Assume that the training and test sequences were emitted
from some unknown probabilistic source $P$. Let the test sequence
be given by the value of the sequence of random variables $X_1^T =
X_1\cdots X_T$. A well known fact is that the distribution $P$
uniquely minimizes the mean log-loss; that is,\footnote{Note that
very specific loss functions satisfy this property.
\shortcite<See>{miller93lossfunc}.}
$$
P = \arg\min_{\Phat} \left\{-\rE_P\{\log \Phat(X_1^T) \} \right\}.
$$
Due to the equivalence of the log-loss and compression, as discussed above,
the mean of the log-loss of $P$ (under the true distribution $P$)
achieves the best possible compression, or the entropy
$H_T(P) = -\rE \log P(X_1^T)$.
However, the true distribution $P$ is unknown and the learner generates
the proxy $\Phat$ using the training sequence.
The extra loss (due to the use of
$\Phat$, instead of $P$) beyond the entropy, is called the \emph{redundancy}
and is given by
\begin{equation}
\label{eq:reduandancy}
D_T(P||\Phat) = \rE_P \left \{
-\log \Phat(X_1^T) - (-\log P(X_1^T) )
\right\}.
\end{equation}
It is easy to see that
$D_T(P||\Phat)$ is the ($T^{th}$ order) Kullback-Leibler (KL)
divergence \cite<see>[Sec. 2.3]{info_theory}.
The \emph{normalized redundancy} $D_T(P||\Phat)/T$ (of a sequence
of length $T$) gives the extra bits per symbol (over the entropy rate)
when compressing a sequence using $\Phat$.

This probabilistic setting motivates a desirable goal, when
devising a general-purpose prediction algorithm: minimize the
redundancy uniformly, with respect to all possible distributions.
A prediction algorithm for which we can bound the redundancy
uniformly, with respect to all distributions in some given class,
is often called \emph{universal} with respect to that class. A
lower bound on the redundancy of any universal prediction (and
compression) algorithm is $\Omega(K(\frac{\log T}{2T}))$, where
$K$ is (roughly) the number of parameters of the model encoding
the distribution $\Phat$ \cite{rissanen84universal}.\footnote{A
related lower bound in terms of channel capacity is given by
\citeA{Merhav95aStrong}.} Some of the algorithms we discuss below
are universal with respect to some classes of sources. For
example, when an upper bound on the Markov order is known, the
$\ctw$ algorithm (see below) is universal (with respect to ergodic
and stationary sources), and in fact, has bounded redundancy,
which is close to the Rissannen lower bound.




%Therefore, by the law of large numbers the average log-loss
%approaches its mean $ -\rE_P \left\{ \log \Phat(\sigma|s) \right\}$, which is
%equivalent to $D(P || \Phat) - H(P)$, where $D(\cdot||\cdot)$ is the
%Kullback-Leibler (KL) divergence $D(P || \Phat)$; see \cite{ZZZ-Cover-Thomas}.


%Each of the algorithms attempts to construct its best guess $\Phat$ for
%the unknown $P$. The main differences between the algorithms
%is their method for search of the best $\Phat$ and its representation.
%For example, $\Phat$ can be a single best model or a an average of many models.

%A useful performance measure for prediction algorithms is their \emph{redundancy},
%defined to be:
%$$
%\frac{1}{n}(\rE \left\{ -\log(P(X=x_i|s_1^n)) - H(s_1^n) \right\}.
%$$
%that is, the average difference between the predictor's loss to the best possible
%loss.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Here we are
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{VMM Prediction Algorithms}
\label{sec:the_algorithms}

In order to assess the significance of our results it is important
to understand the sometimes subtle differences between the
different algorithms tested in this study and their variations. In
this section we describe in detail each one of these six
algorithms. We have adhered to a unified notation schema in an
effort to make the commonalities and differences between these
algorithms clear.

%We will be focusing on ``variable length models'' $\Phat$ that attempt to
%estimate
%correctly $P(\sigma | s)$ for any context $s$ that appeared in the training
%sequence. In contrast to $N$-gram models, which consider only fixed contexts of
%length $N$, variable length models should handle contexts of all lengths, for which
%we have training statistics.

Most algorithms for learning VMMs include three components:
 counting, smoothing (probabilities of unobserved events) and
 variable-length modeling.
 Specifically, all such algorithms base their probability estimates
 on counts of the number of occurrences of symbols $\sigma$
 appearing after contexts $s$ in the training sequence. These counts
 provide the basis for generating the predictor $\Phat$.
%The algorithms we consider here
% implement this counting in two different ways: Systematic
%counts of all the \emph{bounded} contexts in the training sequence, and
%non-systematic consideration of \emph{unbounded} contexts.
The smoothing component defines how to handle unobserved events
(with zero value counts). The existence of such events is also
called the ``zero frequency problem''. Not handling the zero
frequency problem is harmful because the log-loss of an unobserved
but possible event, which is assigned a zero probability by
$\Phat$, is infinite. The algorithms we consider handle such
events with various techniques.

Finally, variable length modeling can be done in many ways. Some
of the algorithms discussed here construct a single model and some
construct several models and average them. The models themselves
can be bounded by a pre-determined constant bound, which means
that the algorithm does not consider contexts that are longer than
the bound. Alternatively, models may not be bounded a-priori, in
which case the maximal context size is data-driven.



There are a great many VMM prediction algorithms. In fact, any
lossless compression algorithm can be used for prediction.
%\footnote{For a probability estimate
%$\Phat(\sigma|s)$ (based on some compression algorithm $C$) one can take
%$(|s|+1)C(s\sigma) - |s|C(s)$, where $C(s)$ is the compression of $s$.}
For the present study we selected six VMM prediction algorithms,
described below. We attempted to include algorithms that are
considered to be top performers in lossless compression. We,
therefore, included the `context tree weighting (CTW)' and
`prediction by partial match (PPM)' algorithms. The `probabilistic
suffix tree (PST)' algorithm is well known in the machine learning
community. It was successfully used in a variety of applications
and is hence included in our set. To gain some perspective we also
included the well known $\lz$ (prediction) algorithm that forms
the basis of many commercial applications for compression. We also
included a recent prediction algorithm from
\citeA{nisenson03Towards} that is a modification of the $\lz$
prediction algorithm. The algorithms we selected are quite
different in terms of their implementations of the three
components described above. In this sense, they represent
different approaches for VMM prediction.\footnote{ We did not
include in the present work the prediction algorithm that can be
derived from the more recent \texttt{bzip} compression algorithm
(see \url{http://www.digistar.com/bzip2}), which is based on the
successful Burrows-Wheeler Transform
\cite{burrows94blocksorting,manzini01analysis}.}




\subsection{Lempel-Ziv 78 (LZ78)}
\label{sec:lz78}

The $\lz$ algorithm is among the most popular lossless compression
algorithms \cite{LZ78}. It is used as the basis of the Unix
\texttt{compress} utility and other popular archiving utilities
for PCs. It also has performance guarantees within several
analysis models. This algorithm (together with the $\lzs$
compresion method) attracted enormous attention and inspired the
area of lossless compression and sequence prediction.

The \emph{prediction} component of this algorithm was first discussed by \citeA{langdon83aNote} and
\citeA{Rissanen83aUniversal}. The presentation of this algorithm is simplified after the well-known $\lz$
\emph{compression} algorithm, which works as follows, is understood. Given a sequence $q_1^n \in \Sigma^n$, $\lz$
incrementally parses $q_1^n$ into non-overlapping adjacent `phrases', which are collected into a phrase
`dictionary'. The algorithm starts with a dictionary containing the empty phrase $\eps$. At each step the algorithm
parses a new phrase, which is the shortest phrase that is not yet in the dictionary. Clearly, the newly parsed
phrase $s'$ extends an existing dictionary phrase by one symbol; that is, $s' = s\sigma$, where $s$ is already in
the dictionary ($s$ can be the empty phrase). For compression, the algorithm encodes the index of $s'$ (among all
parsed phrases) followed by a fixed code for $\sigma$. Note that coding issues will not concern us in this paper.
Also observe that $\lz$ compresses sequences without explicit probabilistic estimates. Here is an example of this
$\lz$ parsing: if $q_1^{11}=\texttt{abracadabra}$, then the parsed phrases are $\texttt{a|b|r|ac|ad|ab|ra}$.
Observe that the empty sequence $\eps$ is always in the dictionary and is omitted in our discussions.

An $\lz$-based prediction algorithm was proposed by \citeA{langdon83aNote} and \citeA{Rissanen83aUniversal}.
We describe separately the
learning and prediction phases.\footnote{These ``phases'' can be
combined and operated together online.}
For simplicity we first discuss the binary case where $\Sigma = \{0,1\}$,
but the algorithm can be naturally extended to alphabets of any size
(and in the experiments discussed below we do use the
multi-alphabet algorithm).
In the
learning phase the algorithm constructs from the training sequence
$q_1^n$ a binary tree (trie) that records the parsed phrases (as
discussed above). In the tree we also maintain counters that hold
statistics of $q_1^n$. The initial tree contains a root and two
(left and right) leaves.
%\rnote{does it mean that we start with a dictionary containing
%both `0' and `1'?}
The left child of a node corresponds to a parsing of `\texttt{0}'
and the right child corresponds to a parsing of `\texttt{1}'. Each
node maintains a counter. The counter in a leaf is always set to
1. The counter in an internal node is always maintained so that it
equals the sum of its left and right child counters. Given a newly
parsed phrase $s'$, we start at the root and traverse the tree
according to $s'$ (clearly the tree contains a corresponding path,
which ends at a leaf). When reaching a leaf, the tree is expanded
by making this leaf an internal node and adding two leaf-sons to
this new internal node.  The counters along the path to the root
are updated accordingly.

To compute the estimate $\Phat(\sigma|s)$ we start from the root and
traverse the tree according to $s$. If we reach a leaf before ``consuming''
$s$ we continue this traversal from the root, etc.
Upon completion of this traversal (at some internal node, or a leaf)
the prediction for $\sigma= \ $`\texttt{0}' is the `\texttt{0}' (left) counter
divided by the sum of `\texttt{0}' and `\texttt{1}' counters at that node, etc.

For larger alphabets, the algorithm is naturally extended such that
the phrases are stored in a multi-way tree and each
internal node has exactly $k=|\Sigma|$ children. In addition,
each node has $k$ counters, one for each possible symbol.
In Figure~\ref{fig:example_lz} we depict the resulting tree for
the training sequence $q_1^{11}=\texttt{abracadabra}$ and calculate the
probability $\Phat(\texttt{b}|\texttt{ab})$, assuming $\Sigma = \{a,b,c,d,r\}$.


\begin{figure}[ht!]
\vskip 0.2in
\begin{center}
%\setlength{\epsfxsize}{2.7in} \centerline{\epsfbox{eps/lz78.eps}}
\setlength{\epsfxsize}{1.8in}
\centerline{\epsfbox{eps/lz78_example.eps}}
 \vskip 0.1in
\caption{The tree constructed by $\lz$ using the training sequence
$q_1^{11}=\texttt{abracadabra}$. The algorithm extracts the set
$\{\texttt{a,b,r,ac,ad,ab,ra}\}$ of ``phrases'' (this set is
traditionally called a `dictionary') and constructs the phrase
tree accordingly. Namely, there is an internal node for every string in the dictionary,
and every internal node has all $|\Sigma|$ children.
For calculating $\Phat(\texttt{b|ar})$ we traverse the tree as follows:
$\epsilon$$\rightarrow$\texttt{a}$\rightarrow$\texttt{r}$\rightarrow$$\epsilon$$\rightarrow$\texttt{b}
and conclude with $\Phat(\texttt{b|ar})=5/33=0.152$. To calculate
$\Phat(\texttt{d|ra})$ we traverse the tree as follow:
$\epsilon$$\rightarrow$\texttt{r}$\rightarrow$\texttt{a}$\rightarrow$\texttt{d}
and conclude with $\Phat(\texttt{d|ra})=1/5=0.2$.}
\label{fig:example_lz}
\end{center}
\vskip -0.2in
\end{figure}


Several performance guarantees were proven for the $\lz$
compression (and prediction) algorithm. Within a probabilistic
setting (see Section~\ref{sec:preliminaries}), when the unknown
source is stationary and ergodic Markov of finite order, the
redundancy is bounded above by $(1/\ln n)$ where $n$ is the length
of the training sequence \cite{Savari97Redundancy}. Thus, the
$\lz$ algorithm is a universal prediction algorithm with respect
to the large class of stationary and ergodic Markov sources of
finite order.



\subsection{Prediction by Partial Match (PPM)}
\label{sec:ppm}

The Prediction by Partial Match ($\ppm$) algorithm
\cite{cleary84data} is considered to be one of the best lossless
compression algorithms.\footnote{Specifically, the $\ppmII$ variant
of $\ppm$ currently achieves the best compression rates over the
standard Calgary Corpus benchmark \cite{shkarin02one}.}
%In
%contrast to the $\lz$ compression algorithm, which is a
%``dictionary-based'' method, $\ppm$ compression explicitly builds
%a statistical model for estimating $\Phat(\sigma|s)$, which is
%then used for coding using `arithmetic encoding'
%\citep{rissanen79arithmetic}.
The algorithm requires an upper bound $D$ on the maximal
Markov order of the VMM it constructs.
%Therefore, the estimated
%probability satisfies $\Phat(\sigma|s_1^n)= \Phat(\sigma|s_{n-D+1}^n)$, $n$$>$$D$.
$\ppm$ handles the zero frequency problem using two mechanisms
called \emph{escape} and \emph{exclusion}. There are several
$\ppm$ variants distinguished by the implementation of the escape
mechanism. In all variants the escape mechanism works as follows.
For each context $s$ of length $k \leq D$, we allocate a
probability mass $\Phat_k(escape|s)$ for all symbols that did not
appear after the context $s$ (in the training sequence). The
remaining mass $1-\Phat_k(escape|s)$ is distributed among all
other symbols that have non-zero counts for this context. The
particular mass allocation for `escape' and the particular mass
distribution $\Phat_k(\sigma|s)$, over these other symbols
$\sigma$, determine the $\ppm$ variant. The mechanism of all
$\ppm$ variants satisfies the following (recursive) relation,
\begin{equation}\label{eq:escape}
\Phat(\sigma|s_{n-D+1}^n)=
\left\{%
\begin{array}{ll}
    \Phat_D(\sigma|s_{n-D+1}^n), &
    \hbox{
    {\small
    \begin{tabular}{l}
      if $s_{n-D+1}^n \sigma$ apeared in \\
      the training sequence; \\
    \end{tabular}
    }
    } \\
%    if $s_{n-D+1}^n \sigma$ apeared in the training sequence;} \\
    \Phat_D(escape|s_{n-D+1}^n)\cdot \Phat(\sigma|s_{n-D+2}^n),
    & \hbox{\small \ \ \ otherwise.} \\
\end{array}%
\right.
%\Phat_D(escape|s_{n-D}^n)\cdots
%\Phat(escape|s_{(n-D+k-1)}^n) \cdot \Phat(\sigma|s_{(n-D+k)}^n),
\end{equation}
For the empty context $\eps$, $\ppm$ takes
$\Phat(\sigma|\epsilon)=1/|\Sigma|$.\footnote{It also makes sense to use the
frequency count of symbols over the training sequence.}

The exclusion mechanism is used to enhance the escape estimation.
It is based on the observation that if a symbol $\sigma$ appears after
the context $s$ of length $k \leq D$, there is no need to
consider $\sigma$ as part of the alphabet when calculating
$\Phat_k(\cdot | s')$ for all $s'$ suffix of $s$ (see Equation~(\ref{eq:escape})).
Therefore, the estimates $\Phat_k(\cdot | s)$ are potentially more accurate since
they are based on a smaller (observed) alphabet.

The particular $\ppm$ variant we consider here is called `Method C'
($\ppmc$) and is defined as follows. For each sequence $s$ and symbol $\sigma$
let $N(s\sigma)$ denote the number of occurrences of $s\sigma$ in the training sequence.
Let $\Sigma_s$ be the set of symbols appearing after the context
$s$ (in the training sequence); that is,
$\Sigma_s = \{ \sigma \ : \ N(s\sigma) > 0 \} $.
For $\ppmc$ we thus have
\begin{align}
\Phat_k({\sigma}|s) &=
\frac{N(s\sigma)}{|\Sigma_s|+ \sum\limits_{\sigma'\in\Sigma_s}N(s\sigma')} \ \ \
\textrm{, if $\sigma \in \Sigma_s$;}  \label{eq:ppc-prob}\\
\Phat_k(escape|s) &= \frac{|\Sigma_s|}{|\Sigma_s|+
\sum\limits_{\sigma'\in\Sigma_s}N(s\sigma')},
\label{eq:ppc-escape-prob}
\end{align}
where we assume that $|s| = k$. This implementation of the escape
mechanism by \citeA{moffat90implementing} is considered to be among the
better $\ppm$ variants, based on
empirical examination \cite{bunton97semantically}.
As noted by \citeA{witten91zero} there is
no principled justification for any of the various $\ppm$ escape
mechanisms.

One implementation of $\ppmc$ is based on a trie data structure.
In the learning phase the algorithm constructs a trie $\TTT$ from
the training sequence $q_1^n$. Similar to the $\lz$ trie, each
node in $\TTT$  is associated with a symbol and has a counter. In
contrast to the unbounded $\lz$ trie, the maximal depth of $\TTT$
is $D+1$. The algorithm starts with a root node corresponding to
the empty sequence $\eps$ and  incrementally parses the training
sequence, one symbol at a time. Each parsed symbol $q_i$ and its
$D$-sized context, $x_{i-D}^{i-1}$, define a potential path in
$\TTT$, which is constructed, if it does not yet exist. Note that
after parsing the first $D$ symbols, each newly constructed path
is of length $D+1$. The counters along this path are incremented.
Therefore, the counter of any node, with a corresponding path
$s\sigma$ (where $\sigma$ is the symbol associated with the node)
is $N(s \sigma)$.

Upon completion, the resulting trie induces the probability
$\Phat(\sigma|s)$ for each symbol $\sigma$ and context $s$ with
$|s| \leq D$. To compute $\Phat(\sigma|s)$ we start from the root
and traverse the tree according to the longest suffix of $s$,
denoted $s'$, such that $s'\sigma$ corresponds to a complete path
from the root to a leaf. We then use the counters $N(s' \sigma')$
to compute $\Sigma_{s'}$ and the estimates as given in
Equations~(\ref{eq:escape}),~(\ref{eq:ppc-prob})
and~(\ref{eq:ppc-escape-prob}).

The above implementation (via a trie) is natural
for the learning phase
and it is easy to see that
the time complexity for learning $q_1^n$ is $O(n)$ and the
space required for the worst case trie is $O(D\cdot n)$.
However, a straightforward computation of $\Phat(\sigma|s)$ using the trie incurs
 $O(|s|^2)$ time.\footnote{After the construction of the trie it is possible
 to generate a corresponding suffix tree that allows a rapid computation of
 $\Phat(\sigma|s)$ in $O(|s|)$ time. It is possible to generate this
 suffix tree in time proportional to the sum of all
 paths in the trie.} In Figure~\ref{fig:example_ppm} we depict the resulting tree for
the training sequence $q_1^{11}=\texttt{abracadabra}$ and
calculate the probabilities $\Phat(\texttt{b|ar})$ and $\Phat(\texttt{d|ra})$, assuming $\Sigma
= \{\texttt{a,b,c,d,r}\}$.

\begin{figure}[htb!]
\vskip 0.2in
\begin{center}
%\setlength{\epsfxsize}{2.7in} \centerline{\epsfbox{eps/lz78.eps}}
\setlength{\epsfxsize}{3in}
\centerline{\epsfbox{eps/ppm_example.eps}}
 \vskip 0.1in
\caption{The tree constructed by $\ppmc$ using the training
sequence $q_1^{11}=\texttt{abracadabra}$. $\Phat(\texttt{d|ra}) =
\Phat(escape|\texttt{ra})\cdot
\Phat(\texttt{\texttt{d|a}})=\frac{1}{2} \cdot \frac{1}{4+3}=0.07$
without using the exclusion mechanism. When using the exclusion,
observe that $N(\texttt{rac})>0$; therefore, we can exclude $c$ when
evaluating $\Phat(\texttt{d|ra}) = \Phat(escape|\texttt{ra})\cdot
\Phat(\texttt{d|a})=\frac{1}{2} \cdot \frac{1}{6}=0.08$.}
\label{fig:example_ppm}
\end{center}
\vskip -0.2in
\end{figure}

\subsection{The Context Tree Weighting Method (CTW)}
\label{sec:ctw}

The Context Tree Weighting Method ($\ctw$) algorithm
\shortcite{willems95contexttree} is a strong lossless compression algorithm
that is based on a clever idea
for combining exponentially many VMMs of
bounded order.\footnote{The paper presenting this idea
\cite{willems95contexttree} received the 1996 Paper Award of the
IEEE Information Theory Society.}
In this section we consider the original $\ctw$ algorithm for
\emph{binary} alphabets. In the next section we discuss extensions
for larger alphabets.

If the unknown source of the given sample sequences is a ``tree
source'' of bounded order, then the compression redundancy of
$\ctw$ approaches the Rissanen lower bound at rate
$1/n$.\footnote{Specifically, for $\Sigma=\{0,1\}$, Rissanen's
lower bound on the redundancy when compressing $x_1^n$ is
$\Omega(|M|(\frac{\log n}{2n}))$. The guaranteed $\ctw$ redundancy
is $O(|M|(\frac{\log n}{2n}) + \frac{1}{n}|M|\log |M|)$, where $M$
is the suffix set of the unknown source.} A $D$-bounded \emph{tree
source} is a pair $(M,\,\Theta_M)$ where $M$ is set of sequences
of length $\leq D$. This set must be a \emph{complete and proper
suffix set}, where `complete' means that for any sequence $x$ of
length $\geq D$, there exists $s \in M$, which is a suffix of $x$.
`Proper' means that no sequence in $M$ has a strict suffix in $M$.
The set $\Theta_M$ contains one probability distribution over
$\Sigma$ for each sequence in $M$. A proper and complete suffix
set is called a \emph{model}. Given some initial sequence
(``state'') $s \in M$, the tree source can generate a random
sequence $x$ by continually drawing the next symbol from the
distribution associated with the unique suffix of $x$.

Any full binary tree of height $\leq D$
corresponds to one possible $D$-bounded
model $M$. Any choice
of appropriate probability distributions $\Theta_M$ defines, together with $M$,
a unique tree source.
Clearly, all prunings of the perfect
binary tree\footnote{In a \emph{perfect binary tree} all internal nodes have two sons and
all leaves are at the same level.}
of height $D$
that are full binary trees
correspond to the collection of
all $D$-bounded models.

For each model $M$, $\ctw$ estimates a set of probability
distributions, $\Theta_M = \{\Phat_M(\cdot|s) \}_{s \in M}$, such
that $(M,\Theta_M)$ is a tree source. Each distribution
$\Phat_M(\cdot|s)$ is a smoothed version of a maximum likelihood
estimate based on the training sequence. The core idea of the
$\ctw$ algorithm is to generate a predictor that is a mixture of
all these tree sources (corresponding to all these $D$-bounded
models).
%corresponding to all prunings of the perfect binary tree of height $D$.
Let $\MMM_D$ be the collection of all $D$-bounded models.  For any
sequence $x_1^T$ the $\ctw$ estimated probability for $x_1^T$
is given by
\begin{align}
\PCTW(x_1^T) &=
\sum\limits_{M \in \MMM_D} w(M) \cdot \Phat_M(x_1^T); \label{eq:ctw_mixture} \\
\Phat_M(x_1^T) & = \prod_{i=1}^T  \Phat_M(x_i | \suffix_M(x_{i-D}^{i-1})), \label{eq:model_zero}
\end{align}
where $\suffix_M(x)$ is the (unique) suffix of $x$ in $M$ and
$w(M)$ is an appropriate probability weight function. Clearly, the
probability $\Phat_M(x_1^T)$, given in~(\ref{eq:model_zero}), is a
product of independent events, by the definition of a tree source.
Also note that we assume that the sequence $x_1^T$ has an
``historical'' context defining the conditional probabilities
$\Phat(x_i | \suffix_M(x_{i-D}^{i-1}))$ of the first
symbols. For example, we can assume that the sequence
$x_1^T$ is a continuation of the training sequence. Alternatively,
we can ignore (up to) the first $D$ symbols of $x_1^T$. A more
sophisticated solution is proposed by \citeA{willems98extensions};
see also Section~\ref{sec:related}.

Note that there is a huge (exponential in $D$) number of elements
in the mixture (\ref{eq:ctw_mixture}), corresponding
to all bounded models.
To describe the $\ctw$ prediction algorithm we need to describe
(i) how to (efficiently) estimate all the distributions $\Phat_M(\sigma | s)$;
(ii) how to select the weights $w(M)$; and
(iii) how to efficiently compute the $\ctw$ mixture (\ref{eq:ctw_mixture}).

%Before describing these three components note that for each
%tree source $(M,\{\Phat_M(\sigma | s)\}_{s \in M})$, the probabilities
%$\Phat_M(\sigma|s)$ can be easily used
%for computing the probability $P_M(x)$ of any sequence $x$.
%For any $s \in M$ define
%%
%%To estimate $\Phat_M(\cdot|s)$, $\ctw$ relies the following observation. For
%%each context $s \in M$ ($M \in \MMM_D$) the symbol probability
%%according to $s$, $\Phat_M^s(\sigma)$, is a memoryless (zero
%%order) probability. If we note
%$S_s(x)$ to be the unique (non-contiguous) sub-sequence of
%$x$ consisting of the symbols following the occurrences
%of $s$ in $x$ (in the order of their occurrence in $x$).
%For example, if $M=\left\{0,1\right\}$, $s=101$ and
%$x=101011010$, then $S_{101}(x)=010$.
%Then, the probability
%$P_M(x|past)=\prod\limits_{s\in M} P_M^s(s(x_1^n)|past)$.
%Therefore a good estimation to $P_M^s$ would also induce
%$\Phat_M$.
For each model $M$, $\ctw$ computes the estimate
$\Phat_M(\cdot|s)$ using the Krichevsky-Trofimov (KT) estimator
for memoryless binary sources \cite{krichevsky81the}. The
KT-estimator enjoys an optimal proven redundancy bound of
$\frac{2+\log n}{2n}$.
%, where $n$ is the length of the ``sequence''
%whose probability is estimated.
This estimator, which is very
similar to Laplace's law of succession, is also very easy to
calculate. Given a training sequence $q\neq \epsilon$, the
KT-estimator, based on $q$, is equivalent to
\begin{align*}
\PKT(0|q)&=\frac{N_0(q)+\frac{1}{2}}{N_0(q)+N_1(q)+1};\\
\PKT(1|q)&= 1 - \PKT(0|q),
\end{align*}
where $N_0(q) = N(0)$ and $N_1(q) = N(1)$. That
is, $\PKT(0|q)$ is the KT-estimated probability for `0', based on
a frequency count in $q$.\footnote{As shown by \shortciteA{tjalkens97aContext},
the above simple form of the KT estimator is equivalent to the
original form, given in terms of a Dirichlet distribution by \citeA{krichevsky81the}.
The (original) KT-estimated probability of a sequence
containing $N_0$ zeros and $N_1$ ones is
$\int_0^1 \frac{(1-\theta)^{N_0} \theta^{N_1}}{\pi \sqrt{\theta (1- \theta)}} d \theta$.}

%Assuming independence, for a sequence $s = \sigma_1\sigma_2 \cdots \sigma_k$ we define
%$$
%\PKT(s|x) = \prod_{i=1}^k \PKT(\sigma_i | x).
%$$
For any sequence $s$ define
$\sub_s(q)$ to be the unique (non-contiguous) sub-sequence of
$q$ consisting of the symbols following the occurrences
of $s$ in $q$. Namely, it is the concatenation of all symbols $\sigma$
(in the order of their occurrence in $q$) such that $s\sigma$ is a substring of $q$.
For example, if $s=\texttt{101}$ and
$q=\texttt{101011010}$, then $\sub_{\texttt{101}}(q)=\texttt{010}$.
Using this definition we can calculate the KT-estimated probability of
a test sequence $x_1^T$ according to a context $s$, based on the training sequence $q$.
Letting $q_s = \sub_s(q)$ we have,
$$
\PKT^s(x_1^T|q) = \prod_{i=1}^{T} \PKT(x_i| q_s).
$$
For the empty sequence $\eps$ we have $\PKT^s(\eps|q)=1$.

One of the main technical ideas in the $\ctw$ algorithm
is an efficient recursive computation of
Equation~(\ref{eq:ctw_mixture}).
This is achieved through the following recursive definition. For any $s$ such
that $|s| \leq D$, define
\begin{equation}
\label{eq:ctw_recurrence}
\PCTW^s(x_1^T)
%\sum\limits_{M \in \MMM_D} w(M) \cdot \Phat_M(\sigma | \suffix_M(s))
= \left \{
    \begin{array}{ll}
    \frac{1}{2} \PKT^s (x_1^T|q)
    +\frac{1}{2} \PCTW^{0s}(x_1^T) \PCTW^{1s}(x_1^T), & \textrm{if $|s| <D$;} \\
    \PKT^s (x_1^T| q), & \textrm{otherwise ($|s|=D$),} \\
\end{array}
\right.
\end{equation}
where $q$ is, as usual, the training sequence. As shown by
\citeA[Lemma~2]{willems95contexttree}, for any
training sequence $q$ and test sequence $x$, $\PCTW^{\epsilon}(x)$
is precisely the $\ctw$ mixture as given in
Equation~(\ref{eq:ctw_mixture}), where the probability weights
$w(M)$ are\footnote{There is a natural coding for
$D$-bounded models such that the length of the code in bits for a
model $M$ is exactly $C_D(M)$.}
\begin{align*}
w(M)&= 2^{-C_D(M)}; \\
C_D(M) &= |\left\{s \in M \right\}| -1 + |\{ s \in M : |s|<D \}|.
\end{align*}

%$\prod\limits_{s\in M} P_e(a_s(x_1^n), b_s(x_1^n))$.
%For the model weight, $w(M)$, $\ctw$ uses the ``universal prior''
%defined as $w(M)=2^{-|M|}$. The size measure is defined to be
%$|M|= |\left\{s \in M \right\}| -1 + |\left\{ s \in M : |s|<D
%\right\}|$.
%To compute the average
%$$
%\sum\limits_{M \in \MMM_D} w(M) \cdot
%\Phat_M(x_1^n|x_{1-D}^0)=\sum\limits_{M \in \MMM_D} 2^{-|M|} \cdot
%\prod\limits_{s\in M} P_e(a_s(x_1^n|x_{1-D}^0),
%b_s(x_1^n|x_{1-D}^0))
%$$
%$\ctw$ constructs a perfect binary tree, $\TTT$, of height $D$.
%Any pruning of $\TTT$, as mentioned above, corresponds to a
%$D$-bounded suffix set $M \in \MMM_D$. An inner node $s \in \TTT$
%then corresponds to a suffix $s \in M$ for such suffix sets in
%$\MMM_D$ that have a leaf $s$ in their corresponding pruning of
%$\TTT$. For the other suffix sets $s$ is an inner node in their
%corresponding pruning of $\TTT$. For every inner node $s \in
%\TTT$, $\ctw$ weights between these two possibilities. The
%weighting defines a distribution, $P_w^s$, for every sequence
%$s\in\Sigma^*$ such that $|s|\leq D$:
%\begin{displaymath} P_{w}^{s} =\left \{ \begin{array}{ll}
%\frac{1}{2}P_{e}^s+\frac{1}{2}P_{w}^{0s}P_{w}^{1s} & \textrm{for
%$s$ with length$<D$} \\ P_{e}^s &
%\textrm{for $s$ with length=$D$} \\
%\end{array} \right.
%\end{displaymath}
%The average is calculated by taking $s$ to be the empty sequence:
%$$
%P_w^{\lambda}(x_1^n|x_{1-D}^0)=\sum\limits_{M \in
%\MMM_D} 2^{-|M|} \cdot \prod\limits_{s\in M}
%P_e(a_s(x_1^n|x_{1-D}^0), b_s(x_1^n|x_{1-D}^0))
%$$

In the learning phase, the $\ctw$ algorithm processes a training
sequence $q_1^n$ and constructs a binary context tree $\TTT$. An
outgoing edge to a left son in $\TTT$ is labelled by `0' and an outgoing
edge to a right son, by `1'. Each node $s \in \TTT$ is associated
with the sequence corresponding to the path from this node to the
root. This sequence (also called a `context') is also
denoted by $s$. Each node maintains two counters $N_0$ and $N_1$
that count the number of `0's (resp. `1's) appearing after the
contexts $s$ in the training sequence. We start with a perfect
binary tree of height $D$ and set the counters in each node to
zero. We process the training sequence $q_1^n$ by considering all
$n-D$ contexts of size $D$ and for each context we update the
counters of the nodes along the path defined by this context. Upon
completion we can estimate the probability of a test sequence
$x_1^T$ using the relation~(\ref{eq:ctw_recurrence}) by computing
$\PCTW^{\epsilon}(x_1^T)$.
This probability estimate for
the sequence $x_1^T$ induces the conditional distributions
$\PCTW(x_i|x_{i-D+1}^{i-1})$, as noted in
Section~\ref{sec:preliminaries}. For example, in
Figure~\ref{fig:example_ctw} we depict the $\ctw$ tree with $D=2$
constructed according to the training sequence
$q_1^{9}=\texttt{101011010}$.

This straightforward implementation requires $O(|\Sigma|^D)$ space (and time) for learning
and $O(T\cdot|\Sigma|^D)$ for predicting $x_1^T$. Clearly, such time and space complexities
are hopeless even for moderate $D$ values. We presented the algorithm this way for simplicity.
However, as already mentioned by \citeA{willems95contexttree},
 it is possible to obtain linear time
complexities for both training and prediction.
The idea is to only construct tree paths that occur in the training sequence.
The counter values corresponding to all nodes along unexplored paths remain zero and, therefore,
the estimated $\ctw$ probabilities for
entire unvisited sub-trees can be easily computed
(using closed-form formulas).
The resulting time (and space) complexity for training is $O(Dn)$ and for prediction,
$O(TD)$.
More details on this efficient implementation are nicely explained by
\shortciteA{sadakane00implementing}
\cite<see also>{tjalkens97implementing}.



\begin{figure}[ht!]
\vskip 0.2in
\begin{center}
%\setlength{\epsfxsize}{2.7in} \centerline{\epsfbox{eps/lz78.eps}}
\setlength{\epsfxsize}{4in}
\centerline{\epsfbox{eps/ctw_example.eps}}
 \vskip 0.1in
\caption{\label{fig:example_ctw} A $\ctw$ tree ($D=2$)
corresponding to the training sequence
$q_1^{9}=\texttt{101011010}$, where the first two symbols in $q$ ($q_1^2$) are neglected.
We present, for each tree node, the values of the counters $N_0$, $N_1$ and
the estimations $\PKT(\texttt{0}|\cdot)$ and $\PCTW(\texttt{0}|\cdot)$.
For example, for the leaf \texttt{10}: $N_0=0$ since \texttt{0}
does not appear after \texttt{10} in $q_1^{9}=\texttt{101011010}$; \texttt{1} appears
(in $q_1^{9}$) three times after \texttt{10}, therefore, $N_1=3$;
$\PKT(\texttt{0}|\texttt{10})=\frac{0+\frac{1}{2}}{0+3+1}=\frac{1}{8}$;
because \texttt{10} is a leaf, according to Equation~(\ref{eq:ctw_recurrence})
$\PKT(\texttt{0}|\texttt{10})=\PCTW(\texttt{0}|\texttt{10})$.
}
\end{center}
\vskip -0.2in
\end{figure}

\subsection{CTW for Multi-Alphabets}
\label{sec:dctw}

The above $\ctw$ algorithm for a binary alphabet can be extended
in a natural manner to handle sequences over larger alphabets.
One must (i) extend the KT-estimator for
larger alphabets; and (ii) extend the recurrence relation~(\ref{eq:ctw_recurrence}).
While these extensions can be easily obtained, it is reported that
the resulting algorithm
preforms poorly \cite<see>[chap.~4]{volf_phd}. As noted by Volf, the reason is
that the extended KT-estimator does not provide efficient smoothing for large alphabets.
Therefore, the
problem
of extending the $\ctw$ algorithm for large alphabets is challenging.
%\footnote{In some
%sense, this problem is related to the classic problem of multi-class decomposition \cite{appropriate-ref}
%in machine learning, which was recently put in focus due to the success
%of the binary6 support vector machines.}

Several $\ctw$ extensions for larger alphabets have been proposed.
Here we consider two.
The first is a naive application of the standard binary $\ctw$ algorithm
over a binary representation of the sequence.
The binary representation is naturally obtained when the size of the
alphabet is a power of 2. Suppose that $k=\log_2 |\sigma|$
is an integer.
In this case we
generate a binary sequence by concatenating
binary words of size $k$, one for
each alphabet symbol. If $\log_2 |\sigma|$ is not an integer
we take $k=\left\lceil \log_2 |\sigma| \right\rceil$.
We denote the resulting algorithm by
$\bctw$.
A more sophisticated binary decomposition of $\ctw$ was
considered by \citeA{tjalkens97aContext}. There eight binary machines
were simultaneously constructed, one for each of the eight binary digits
of the ascii representation of text. This decomposition does not achieve the best
possible compression rates over the Calgary Corpus.

The second method we consider is Volf's `decomposed $\ctw$',
denoted here by $\dctw$ \cite{volf_phd}. The $\dctw$ uses a
tree-based hierarchical decomposition of the multi-valued prediction problem into
binary problems. Each of the
binary problems is solved via a slight variation of the binary $\ctw$ algorithm.

Let $\Sigma$ be an alphabet with size $k = | \Sigma |$. Consider a
full binary tree $\TTT_\Sigma$ with $k$ leaves. Each leaf is
uniquely associated with a symbol in $\Sigma$. Each internal node
$v$ of $\TTT_\Sigma$ defines the binary problem of predicting
whether the next symbol is a leaf on $v$'s left subtree or a leaf
on $v$'s right subtree. For example, for $\Sigma =
\{\texttt{a,b,c,d,r}\}$, Figure~\ref{fig:example_dctw} depicts a
tree $\TTT_\Sigma$ such that the root corresponds to the problem
of predicting whether the next symbol is \texttt{a} or one of
\texttt{b},\texttt{c},\texttt{d} and \texttt{r}. The idea is to
learn a binary predictor, based on the $\ctw$ algorithm, for each
internal node.

In a simplistic implementation of this idea, we construct a binary
$\ctw$ for each internal node $v \in\TTT_\Sigma$. We project the
training sequence over the ``relevant'' symbols (i.e.,
corresponding to the subtree rooted by $v$) and translate the
symbols on $v$'s left (resp., right) sub-tree to \texttt{0}s (resp.,
\texttt{1}s). After training we predict the next symbol $\sigma$
by assigning each symbol a probability that is the product of
binary predictions along the path from the root of $\TTT_\Sigma$
to the leaf labeled by $\sigma$.

Unfortunately, this simple approach may result in poor performance
and a slight modification is required.\footnote{Consider the
following example. Let $\Sigma = \{\texttt{a,b,z}\}$ and consider
a decomposition $\TTT_\Sigma$ with two internal nodes where the
binary problem of the root discriminates between $\{ \texttt{a,b}
\}$ and $\{\texttt{z}\}$ (and the other internal node corresponds
to distinguishing between \texttt{a} and \texttt{b}). Using the
simplistic approach, if we observe the training sequence
$\texttt{azaz}\cdots \texttt{azazb}$, we will assign very high
probability to \texttt{z} given the context \texttt{zb}, which is
not necessarily supported by the training data.} For each internal
node $v \in \TTT_\Sigma$, let $\ctw_v$ be the associated binary
predictor designed to handle the alphabet $\Sigma_v \subseteq
\Sigma$. Instead of translating the projected sequence (projected
over $\Sigma_v$) to a binary sequence, as in the simple approach,
we construct $\ctw_v$ based on a $|\Sigma_v|$-ary context tree.
Thus, $\ctw_v$ still generates predictions over a binary alphabet
but expands a suffix tree using the (not necessarily binary)
$\Sigma_v$ alphabet. To generate binary predictions $\ctw_v$
utilizes, in each node of the context tree, two counters for
computing binary KT-estimations (as in the standard $\ctw$
algorithm). For example, in Figure~\ref{fig:example_dctw}(b) we
depict $\ctw_3$ whose binary problem is defined by $\TTT_\Sigma$
of Figure~\ref{fig:example_dctw}(a).
Another modification suggested by Volf, is to use a variant on the KT-estimator.
Volf shows that the estimator $P_e(0|q)=\frac{N_0(q)+\frac{1}{2}}{N_0(q)+N_1(q)+1/8}$ achieves better
results in practice. We used this estimator for the $\dctw$
implementation.\footnote{We also used this estimator in the protein
classification experiment.}



%For a node $i$ in a binary tree we define the followings.
%$\leaves(i)$ are the leaves of the subtree defined by $i$;
%$left(i)$ is the left child of $i$ and $right(i)$ is the right
%child.
%
%The $\dctw$ algorithm constructs the following decomposition
%binary tree $\TTT$. $\leaves(r)=\Sigma$ where $r$ is the root of
%$\TTT$. Every internal node $i\in\TTT$ is associated with a binary
%predictor $\ctw_i$ that estimates
%$$\Phat(\sigma \in \leaves(\leftchild(i)))=1-\Phat(\sigma \in
%\leaves(\rightchild(i))),$$ for a $\sigma \in \leaves(i)$.
%
%In the learning phase the $\dctw$ train each of the $\ctw_i$
%predictors with a projection of the training sequence on the
%symbols defined by $\leaves(i)$. (See Figure
%\ref{fig:example_dctw} for example). Note that while $\ctw_i$
%computes a binary prediction, it is trained with a multi-alphabet
%sequence. Specifically, $\ctw_i$ is the following simple variation
%of the $\ctw$ algorithm. The nodes of the context-tree of $\ctw_i$
%are labelled with the alphabet symbols. The counts $N_0(\cdot)$
%correspond to symbols in $\leftchild(i)$ and the counts
%$N_1(\cdot)$ to symbols in $\rightchild(i)$.
%
%The $\dctw$ algorithm computes $\Phat(\sigma|x_1^n)$ by
%multiplying the estimations of the predictions of the inner nodes
%along the path from the root of $\TTT$ to the leaf labelled with
%$\sigma$.

A major open issue when applying the $\dctw$ algorithm is the construction
of an effective decomposition tree $\TTT_\Sigma$.
%Conceptually, it is not
%clear what is the correct optimality criterion of a decomposition tree and the number of such trees
%(all full binary trees of $k$ leaves) is exponential in $k$.
Following \cite<>[Chapter 5]{volf_phd}, we employ the heuristic now detailed.
 Given a training sequence $q_1^n$, the algorithm takes
$\TTT_\Sigma$ to be Hoffman's code-tree of $q_1^n$
\cite<see>[chapter 5.6]{info_theory} based on the frequency counts of the symbols in $q_1^n$.


The time and space complexity of the $\dctw$ algorithm, based on the efficient
implementation of the binary $\ctw$, are $O(|\Sigma | Dn)$ for training and
and $O(|\Sigma | D T)$ for prediction.

\begin{figure}[ht!]
\vskip 0.2in
\begin{center}
%\setlength{\epsfxsize}{2.7in} \centerline{\epsfbox{eps/lz78.eps}}
\setlength{\epsfxsize}{4in}
\begin{tabular}{c}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  \centerline{\epsfbox{eps/volf_dctw.eps}}\\
  \textbf{(a)}\\
  \centerline{\epsfbox{eps/dctw_c_example.eps}}\\
  \textbf{(b)}\\
\end{tabular}


\caption{A $\dctw$ tree corresponding to the training sequence
$q_1^{11}=\texttt{abracadabra}$. (a) depicts the decomposition tree $\TTT$. Each internal node in $\TTT$
uses a $\ctw$ predictor to ``solve'' a binary problem. In (b) we
depict $\ctw_3$ whose binary problem is: ``determine if $\sigma\in \{ \texttt{c,d} \}$ (or $\sigma=\texttt{r}$)''.
Tree paths of contexts that do not appear in the training sequence are marked with dashed lines.}
\label{fig:example_dctw}
\end{center}

\end{figure}



\subsection{Probabilistic Suffix Trees (PST)}\label{sec:PST}
The Probabilistic Suffix Tree ($\pst$) prediction algorithm \shortcite{ron96power}
attempts to construct the single ``best'' $D$-bounded VMM according to the training
sequence. It is assumed that an upper bound $D$ on the Markov order of the ``true source'' is known to the learner.

A $\pst$ over $\Sigma$ is a non empty rooted tree, where the degree of each node
varies between zero (for leaves) and $| \Sigma| $.
Each edge in the tree is associated with a unique symbol in $\Sigma$.
These edge labels define a unique sequence $s$ for each path from a node $v$
to the root. The sequence $s$ labels the node $v$.
Any such $\pst$ tree induces a ``suffix set'' $S$ consisting of the labels of all
the nodes.
The goal of the $\pst$ learning algorithm is to identify a good suffix set $S$
for a $\pst$ tree
and to assign a probability distribution $\Phat(\sigma|s)$
over $\Sigma$, for each $s \in S$.
Note that a $\pst$ tree may not be a tree source, as defined in Section~\ref{sec:ctw}.
The reason is that the set $S$ is not necessarily proper.
We describe the learning phase of the $\pst$ algorithm, which can be viewed
as a three stage process.
\begin{enumerate}
\item
First, the algorithm extracts from the training sequence $q_1^n$ a set of
candidate contexts and forms a candidate ``suffix set'' $\hat{S}$.
Each contiguous sub-sequence $s$ of $q_1^n$ of length $\leq D$, such that the frequency
of $s$ in $q_1^n$ is larger than a user
threshold will be in $\hat{S}$. Note that this construction guarantees that
$\hat{S}$ can be accommodated in a ($\pst$) tree (if a context $s$ appears in
$\hat{S}$, then all suffixes of $s$ must also be in $\hat{S}$).
For each candidate $s$ we associate the conditional (estimated) probability
$\Phat(\sigma|s)$, based on a direct maximum likelihood estimate (i.e., a frequency
count).
\item
In the second stage, each $s$ in the candidate set $\hat{S}$ is
examined using a two-condition test. If the context $s$ passes the test,
$s$ and all its suffixes are included in the final $\pst$ tree.
The test has two conditions that must hold simultaneously:
\begin{itemize}
\item[(i)]
The context $s$ is ``meaningful'' for some symbol $\sigma$;
that is, $\Phat(\sigma|s)$ is larger than a user threshold.
\item[(ii)]
The context $s$ contributes additional information  in predicting $\sigma$
relative to its ``parent'';
if $s = \sigma_k \sigma_{k-1} \cdots \sigma_1$, then
its ``parent'' is its longest suffix $s' = \sigma_{k-1} \cdots \sigma_1$.
We require that
the ratio $\frac{\Phat(\sigma|s)}{\Phat(\sigma|s')}$ be
larger than a user threshold $r$ or smaller than $1/r$.
\end{itemize}
Note that if a context $s$ passes the test there is no need to
examine any of its suffixes (which are all added to the tree as well).
\item
In the final stage, the probability distributions associated with the tree nodes (contexts)
are smoothed. If $\Phat(\sigma|s) = 0$, then it is assigned a minimum
probability (a user-defined constant) and the resulting conditional distribution
is re-normalized.
\end{enumerate}
Altogether the $\pst$ learning algorithm has five user parameters,
which should be selected based on the learning problem
at hand.
The $\pst$ learning algorithm has a PAC style performance guarantee
ensuring that with high probability the redundancy approaches zero
at rate $1/n^{1/c}$ for some positive integer $c$.\footnote{Specifically, the result is that,
with high probability ($\geq 1- \delta$),
the Kullback-Leibler divergence between the
$\pst$ estimated probability distribution
and the true underlying (unknown) VMM distribution
is not larger than $\veps$ after observing a training sequence
whose length is polynomial in $\frac{1}{\veps}$, $\frac{1}{\delta}$, $D$,
$|\Sigma|$ and the number of states in the unknown VMM model.}
An example of the $\pst$ tree constructed for the \texttt{abracadabra}
training sequence is given in Figure
\ref{fig:example_pst}.

The $\pst$ learning phase has a time complexity of $O(Dn^2)$ and a
space complexity of $O(Dn)$.
The time complexity for calculating $\Phat(\sigma|s)$ is $O(D)$.


% Each node is assigned a probability
%distribution vector over the alphabet. The algorithm computes
%$\Phat(\sigma|x)$ using the distribution corresponds to the
%longest suffix of $x$.
%
%In the learning phase the algorithm constructs the $\pst$ tree.
%The measurements that define ``informative'' contexts are based on
%the following five parameters: $P_{min}$, $\gamma_{min}$,
%$\alpha$, $r$, $D$; $D$ is the maximal context length (the order
%of the tree-source) and $P_{min}$, $\gamma_{min}$, $\alpha$, $r$
%are ``information'' threshold parameters. The $\pst$ tree is
%constructed in three stages:
%\begin{enumerate}
%    \item Parsing candidate contexts. $\pst$ extracts every context $s$ from the training
%    sequence, such that (i) $|s|$$\leq$$D$ and (ii) there exists a symbol, $\sigma$, for which
%    $\Phat(\sigma|s)\geq P_{min}$. The estimate
%    $\Phat(\cdot|s)$ is based on the symbol counts in $q_1^n$.
%    \item Tree construction. $\pst$ adds ``informative'' contexts to the tree (and complete the corresponding path to the root).
%    A context $s$ is ``informative'' if there exists a symbol, $\sigma$,
%    such that the following two conditions are satisfied:
%    \begin{enumerate} \item
%    $\Phat(\sigma|s)\geq(1+\alpha)\gamma_{min}$;\item
%    $\frac{\Phat(\sigma|s)}{\Phat(\sigma|\suffix(s))}\geq R$, where $R
%    \in\{r,\,\frac{1}{r}\}$ and for $s=s_1s_2 \cdots s_n$,
%    suffix($s$)$=s_2s_3\cdots s_n$.\end{enumerate}
%
%    For each ``informative'' candidate context $s$, $\pst$ adds $s$ to the tree.
%
%    \item Handle zero-frequency. For each node $s\in \TTT$, $\pst$
%    smoothes the estimation by
%    $$\Phat(\cdot|s)= (1-|\sigma|\gamma_{min})\Phat(\cdot|s)+\gamma_{min}.$$
%\end{enumerate}


\begin{figure}[ht!]
\vskip 0.2in
\begin{center}
%\setlength{\epsfxsize}{2.7in} \centerline{\epsfbox{eps/lz78.eps}}
\setlength{\epsfxsize}{4in}
\centerline{\epsfbox{eps/pst_example.eps}}
 \vskip 0.1in
\caption{A $\pst$ tree corresponding to the training sequence
$x_1^{11}=\texttt{abracadabra}$ and the parameters ($P_{min}=0.001$,
$\gamma_{min}=0.001$, $\alpha=0.01$, $r=1.05$, $D=12$). Each node
is labelled with a sequence $s$ and the distribution
$(\Phat_s(\texttt{a}),\Phat_s(\texttt{b}),\Phat_s(\texttt{c}),\Phat_s(\texttt{d}),\Phat_s(\texttt{r}))$.}
\label{fig:example_pst}
\end{center}
\vskip -0.2in
\end{figure}






%\begin{table}[ht!]
%\vskip 0.2in \setlength{\epsfxsize}{0.5in}
%\begin{center}
%\begin{tabular}{l|l}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%  $\lz(M,S)$ & Phrases Parsed from  \texttt{abracadabra}\\
%  \hline
%  $\lz(0,0) = \lz$ & $\{\texttt{a,b,r,ac,ad,ab,ra}\}$ \\
%  $\lz(0,1)$ & $\{\texttt{a,b,r,ac,ad,ab,ra,br,aca,d,bra}\}$ \\
%  $\lz(1,0)$ & $\{\texttt{a,ab,b,br,r,ra,ac,c,ca,ad,d,da,abr,r,ra}\}$ \\
%  $\lz(1,1)$ & $\{\texttt{a,ab,b,br,r,ra,ac,c,ca,ad,d,da,abr,r,ra,bra,aca,ada,abra}\}$ \\
%  $\lz(2,0)$ & $\{\texttt{a,ab,abr,b,br,bra,r,ra,rac,ac,aca,c,ca,cad,ad,ada,d,da,dab,abr,bra}\}$ \\
%\end{tabular}
%\caption{Phrased parsed from
%$q_1^{11}=\texttt{abracadabra}$ by $\lzms$ for different values of $M$ and
%$S$. Note that the phrases appears in the order of their parsing.
%}
%\label{tab:example_lzms}
%\end{center}
%\vskip -0.2in
%\end{table}


\subsection{LZ-MS: An Improved Lempel-Ziv Algorithm}
\label{sec:lzms}

There are plenty of variations on the classic $\lz$ \emph{compression} algorithm
\cite<see>[for numerous examples]{bell90text}. Here we consider a
recent variant of the $\lz$ \emph{prediction} algorithm due to \citeA{nisenson03Towards}.
The algorithm has two parameters $M$ and $S$ and, therefore,
its acronym here is $\lzms$.

A major advantage of the $\lz$ algorithm is its speed. This speed
is made possible by compromising on the systematic counts of all
sub-sequences.
For example, in Figure~\ref{fig:example_lz}, the sub-sequence \texttt{br} is not parsed
and, therefore, is not part of the tree. However, this sub-sequence is significant
for calculating $\Phat(\texttt{a}|\texttt{br})$.
While for a very long training sequence this
compromise will not affect the prediction quality significantly,
for short training sequences the $\lz$ algorithm yields sparse and noisy
statistics. Another disadvantage of the $\lz$ algorithm is its
loss of context when calculating $\Phat(\sigma|s)$. For example, in
Figure \ref{fig:example_lz}, when taking $\sigma=\texttt{b}$ and $s=\texttt{raa}$,
the $\lz$ prediction algorithm will compute $\Phat(\texttt{b}|\texttt{raa})$ by traversing the tree along
the \texttt{raa} path (starting from the root) and will end on a leaf.
Therefore, $\Phat(\texttt{b}|\texttt{raa}) = \Phat(\texttt{b}|\eps) = 5/33$. Nevertheless, we could
use the suffix \texttt{a} of \texttt{raa} to get the more accurate value
$\Phat(\texttt{b}|\texttt{a}) = 5/17$.
These are two major deficiencies of $\lz$.
The $\lzms$ algorithm attempts to overcome both these disadvantages by introducing
two corresponding heuristics.
This algorithm improves the $\lz$
predictions by
extracting more phrases during learning and by
ensuring a minimal context for the next phrase, whenever possible.
%These
%improvements are achieved by two simple heuristic modifications.

The first modification is termed \emph{input shifting}. It
is controlled by the $S$ parameter and used to
extract more phrases from the training sequence. The training
sequence $q_1^n = q_1 q_2 \cdots q_n$ is parsed $S+1$ times, where in
the $i$th parsing the algorithm learns the sequence $q_i q_{i+1} \cdots q_n$
using the standard $\lz$ learning procedure. The newly extracted phrases and
counts are combined with the previous ones (using the same tree).
Note that by taking $S = 0$ we leave the $\lz$ learning algorithm intact.
For example, the second row of Table~\ref{tab:example_lzms} illustrates the effect of input shifting
with $S = 1$, which clearly enriches the set of parsed phrases.

The second modification is termed \emph{back-shift parsing}
and is controlled by the $M$ parameter.
Back-shift parsing attempts to guarantee a minimal context of $M$ symbols when
calculating probabilities.
In the learning phase the algorithm
back-shifts $M$ symbols after each phrase extraction.
To prevent the case where
more symbols are
back-shifted than parsed (which can happen when $M>1$),
the algorithm requires that back shifting remain within the
last parsed phrase.
For example, on the third row of Table~\ref{tab:example_lzms} we
see the resulting phrase set extracted from the training sequence
using $M=1$. Observe that after extracting the first phrase (\texttt{a}) $\lzms$ back-shifts one symbol,
therefore, the next parsed symbol is (again) `a'.
This implies that the next extracted phrase is \texttt{ab}. Since $\lzms$ back-shifts after each phrase extraction
we conclude with the resulting extracted phrase set.

The back-shift parsing mechanism may improve the calculation of conditional probabilities,
which is also modified as follows.
 Instead of returning to the root after
traversing to a leaf, the last $M$-traversed symbols are first
traced down from the root to some node $v$, and then the new
traversal begins from $v$ (if $v$ exists). Take, for example, the
calculation of $\Phat(b|raa)$ using the tree in Figure
\ref{fig:example_lz}. If we take $M = 0$, then we end with
$\Phat(b|raa) = \Phat(b|\eps) = 5/33$; on the other hand, if we
take $M = 1$, we end with $\Phat(b|raa) = \Phat(b|a) = 5/17$.


\begin{table}[ht!]
\vskip 0.2in \setlength{\epsfxsize}{0.5in}
\begin{center}
\begin{scriptsize}
\begin{tabular}{l|l}
\scriptsize
 % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
 $\lz(M,S)$ & Phrases parsed from  \texttt{abracadabra}\\
 \hline
 $\lz(0,0) = \lz$ & $\{\texttt{a,b,r,ac,ad,ab,ra}\}$ \\
 $\lz(0,1)$ & $\{\texttt{a,b,r,ac,ad,ab,ra,br,aca,d,abr}\}$ \\
 $\lz(1,0)$ & $\{\texttt{a,ab,b,br,r,ra,ac,c,ca,ad,d,da,abr}\}$ \\
 $\lz(1,1)$ & $\{\texttt{a,ab,b,br,r,ra,ac,c,ca,ad,d,da,abr,bra,aca,ada,abra}\}$ \\
 $\lz(2,0)$ & $\{\texttt{a,ab,abr,b,br,bra,r,ra,rac,ac,aca,c,ca,cad,ad,ada,d,da},$\\
               & $\texttt{dab,abra}\}$ \\
 $\lz(2,1)$ & $\{\texttt{a,ab,abr,b,br,bra,r,ra,rac,ac,aca,c,ca,cad,ad,ada,d,da,}$\\
               &   $\texttt{dab,abra,brac,acad,adab} \}$ \\
 $\lz(2,2)$ & $\{\texttt{a,ab,abr,b,br,bra,r,ra,rac,ac,aca,c,ca,cad,ad,ada,d,da,}$\\
            & $\texttt{dab,abra,brac,acad,adab,raca,cada,dabr} \}$ \\

\end{tabular}
\end{scriptsize}
\caption{Phrases parsed from $q_1^{11}=\texttt{abracadabra}$ by
$\lzms$ for different values of $M$ and $S$. Note that the phrases
appear in the order of their parsing. } \label{tab:example_lzms}
\end{center}
\vskip -0.2in
\end{table}


Both `input shifting' and `back-shift parsing' tend to enhance the
statistics we extract from the training sequence. In addition, back-shift parsing
tends to enhance the utilization of the extracted statistics.
Table~\ref{tab:example_lzms} shows the phrases parsed from
$q_1^{11}=abracadabra$ by $\lzms$ for several values of $M$ and
$S$. The phrases appear in the order of their parsing.
Observe that each of these heuristics can introduce a slight bias into
the extracted statistics.

It is interesting to compare the relative advantage of
input shifting and back-shift parsing. In Appendix~\ref{app:lzms_mVSs}
we provide such a comparison using a prediction simulation
over the Calgary Corpus. The results indicate that back-shift
on its own can provide more power to $\lz$ than input shifting
parsing alone. Nevertheless, the utilization of both mechanisms
is always better than using either alone.

The time complexity of the $\lzms$ learning algorithm is
at most $MS$ times the complexity of $\lz$. Prediction using $\lzms$ can take
at most $M$ times the prediction using $\lz$.




\section{Experimental Setup}
\label{sec:experiments}

We implemented and tested the six VMM algorithms
described in Section~\ref{sec:the_algorithms}
using discrete sequences from three domains: text, music and proteins
(see more details below).
The source code of Java implementations for
the six algorithms is available at \paperURL.
We considered the following prediction setting. The learner is given the first half of
a sequence (e.g., a song)
and is required to predict the rest.
We denote the first half by
$q_1^n = q_1 \cdots q_n$ and the second, by $x_1^n = x_1 \cdots x_n$. $q_1^n$ is called
the \emph{training sequence} and $x_1^n$ is called the \emph{test sequence}.
During this learning stage the learner constructs a predictor, which is given in terms
of a conditional distribution $\Phat(\sigma|s)$. The predictor is then fixed and
tested over $x_1^n$.
The quality of the predictor is measured via the average log-loss of $\Phat(\cdot | \cdot)$
with respect to $x_1^n$ as given in Equation~(\ref{eq:logloss}).\footnote{\citeA{cover78aConvergent}
considered a very similar prediction game in their well-known work on the estimation
of the entropy of English text.}
For the protein dataset we also
considered a different, more natural setting in which the learner is
provided with a number of training sequences
emanating from some unknown source, representing some domain. The learner is then required to
provide predictions for sequences from the same domain.

During training, the learner should utilize the training sequence
for learning a probabilistic model, as well as for selecting the best
possible hyper-parameters. Each algorithm selects its
hyper-parameters from a cross product combination of ``feasible'' values,
using a cross-validation (CV) scheme over the
training sequence. In our experiments we used a five-fold CV. The
training sequence $q_1^n$ was segmented into five (roughly) equal
sized contiguous non-overlapping segments and each fold used one
such segment for testing and a concatenation of rest of the
segments for training. Before starting the experiments we
selected, for each algorithm, a set of ``feasible'' values for
its vector of hyper-parameters.
Each possible vector (from this set) was tested using
five-fold CV scheme (applied over the training sequence!) yielding five loss estimates for this vector.
The parameter vector with the best median\footnote{We used the median rather than average since the median of a small
set of numbers is considerably more robust against outliers; see, e.g., \url{http://standards.nctm.org/document/eexamples/chap6/6.6/}} (over the five estimates)
was selected for training the algorithm over the entire training
sequence. See Appendix~\ref{app:hyperparam} for more details on the
exact choices of hyper-parameters for each of the algorithms.
Note that our setting is different from the standard setup used when testing online lossless
compression schemes, where the compressor starts processing the test sequence
without any prior knowledge. Also, it is usually the case that compression algorithms do not optimize
their hyper-parameters (e.g., for text compression $\ppmc$ is usually applied
with a fixed $D=5$).

%\subsubsection{Data Sets}
%\gnote{a separate subsection?}
The sequences we consider belong to three different domains:
English text, music pieces and proteins.

\begin{itemize}
    \item For the English text we chose the well-known `Calgary Corpus' \cite{bell90text}, which
    is traditionally used for benchmarking lossless
    compression algorithms.\footnote{The Calgary Corpus is available at
    \texttt{ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus}.
    Note that this corpus contains, in addition to text, also a few
    binary files and some source code of computer programs, written
    in a number of programming languages.
    }

    \item
    The music set was assembled from MIDI files of music pieces.\footnote{MIDI
        ($=$ \emph{Musical Instrument Digital Interface}) is a standard
            protocol and language for electronic musical instruments.
    A standard MIDI file
    includes instructions on which notes to play and how long and loud to play
    them.}
    The musical benchmark was compiled using a variety of well-known pieces of different styles.
    The styles we included are: classical, jazz and rock/pop. All the pieces we consider are
    polyphonic (played with several instruments simultaneously). Each MIDI file for a polyphonic
    piece consists of several channels (usually one channel per instrument). We considered each channel as
    an individual sequence; see Appendix~\ref{app:music} for more details.
    \item
    The protein set includes proteins (amino-acid sequences) from the well-known
    \emph{Structural Classification of Proteins (SCOP)} database
    \shortcite{murzin95scop}.
    Here we used
        all sequences in release 1.63 of SCOP, after eliminating
        redundancy (i.e., only one copy was retained of sequences that
        are 100\% identical).
    %This set is the largest benchmark dataset we considered (see
    %Table~\ref{tab:the_datsets}).
    This set is hierarchically classified into classes according to biological considerations.
    We relied on this classification for testing classifiers constructed from the VMM algorithms over a number
    of large classification tasks (see Section~\ref{sec:protein-classification}).
    \end{itemize}
   Table~\ref{tab:the_datsets} summarizes some statistics of the three benchmark tests. The three
   datasets can be obtained at \paperURL .


\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  Domain & \# Sequences & $|\Sigma|$ &
\multicolumn{3}{c|} {Sequence Lengths}\\ \cline{4-6}
& & & Min & Avg & Max \\
  \hline
  Text   &18&256&11954&181560&785396\\
  Music  &285&256&24&12726&193662\\
  Protein&19676&20&21&187&8599\\
  \hline
\end{tabular}
\end{center}
\caption{\label{tab:the_datsets} Some essential properties of the
datasets. For the protein prediction setup we considered only
sequences of size larger than 100.}
\end{table}

%All Average (weighted) 187.37 All Size 19676 MAX 8599 MIN 21


%
%\begin{table}
%\begin{center}
%\begin{tabular}{|c|c|c|c|c|c|}
%  \hline
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%  Domain & \# Sequences & $|\Sigma|$ &
%\multicolumn{3}{c|}
%{Sequence lengths}\\ \cline{4-6}
%& & & Min & Avg & Max \\
%  \hline
%  Text   & 18    & 256     & 11954 & 181560 & 785396 \\
%  Music  & 285   & 256     & 24 & 1 & 193662 \\
%  Proteins& 9805  & 20(-22) & 100 & 187 & 8599 \\
%  \hline
%\end{tabular}
%\end{center}
%\caption{\label{tab:thedatsets} Some essential properties of the datasets.}
%\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Prediction Results}

Here we present the prediction results of the six VMM algorithms
for the three domains. The performance is measured via the
log-loss as discussed above. Recall that the average log-loss of a
predictor (over some sequence) is a slightly optimistic estimate
of the compression rate (bits/symbol) that could be achieved by
the algorithm over that sequence.

Table~\ref{tab:calgary} summarizes the results for the textual domain (Calgary Corpus). We see that $\dctw$ is the
overall winner with an average loss of $3.02$. The runner-up is $\ppmc$ with an average loss of $3.03$. However,
there is no statistically significant difference between the two, as indicated by standard error of the mean (SEM)
values. The worst algorithm is the $\lz$ with an average loss of $3.76$. We see that in most cases $\dctw$ and
$\ppmc$ share the first and second best results, $\lzms$ is a runner-up in five cases, and $\lz$ wins one case and
is a runner-up in one case. $\pst$ is the winner in a single case.
%Table~\ref{tab:calgary} summarizes the results for the textual domain (Calgary Corpus).
%We see that $\ppmc$ is the overall winner with an average loss of $0.96$.
%The runner-up is $\dctw$ with average loss of $1.32$.
%The worst algorithm is the $\lz$ with average loss
%of $3.3$. We see that on two cases $\dctw$ is the winner and on almost all other sequences it is the
%runner-up ($\lzms$ and $\bctw$ achieve second best losses in three sequences).

It is interesting to compare the loss results of
Table~\ref{tab:calgary} to known compression results of (some of)
the algorithms for the same corpus, which are 2.14 bps for $\dctw$
and 2.48 bps for $\ppmc$
\cite<see>[respectively]{volf_phd,cleary97unbounded}. While these
results are dramatically better than the average log-loss we
obtain for these algorithms, note that the setting is considerably
different and in the compression applications the algorithms are
continually learning the sequence. A closer inspection of this
disparity between the
compression results and our training/test results reveals that the
difference is in fact not that large. Specifically, the large
average log-loss
is mainly due to
one of the Calgary Corpus files, namely the \emph{obj1} file for which
the log-loss of $\ppmc$ is 6.75, while the compression results of
\citeA{cleary97unbounded} are 3.76 bps. Without \emph{obj1} file the
average log-loss obtained by
$\ppmc$ on the Calgary Corpus is 2.81. Moreover, the 2.48 result is obtained on
a smaller corpus that does not include the four files \emph{paper3}-\emph{6}.
Without these files the average log-loss of $\ppmc$ is 2.65.
This small difference may indicate
that the involved sequences are not governed by a stationary
distribution. Notice also that the compression results indicate
that $\dctw$ is significantly better than $\ppmc$. However, in our
setting these algorithms perform very similarly.


\begin{small}
\begin{table}[htb!]
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|}
\hline\hline
% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
Sequence &   $\bctw$ & $\dctw$ & $\lz$ & $\lzms$ & $\ppmc$ & $\pst$\\
(length$\cdot 10^3$) & & & & & & \\

\hline\hline
%\endfirsthead
%\multicolumn{8}{c}%
%{\textbf{Calgary Corpus Results \small{[bps]}}}{(\textit{continued})}\\[5Pt]
%\hline\hline
%% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%&   {\sffamily  binary} & {\sffamily  decomposed} & {\sffamily
%LZ78} & {\sffamily  LZms} &
%{\sffamily  PPMC} & {\sffamily  PPMZ} & {\sffamily  PST}\\
%\multicolumn{1}{|c|}{\sffamily File} &  {\sffamily CTW}  &  {\sffamily CTW}&  &  & & &\\
%\hline\hline
%\endhead
%\hline
%\multicolumn{8}{r}%
%{\small \itshape continued on the next page}
%\endfoot
%\hline
%\multicolumn{8}{r}%
%{\small \itshape Units are in Bit per Symbols}
%\endlastfoot
%starthere
%\multicolumn{1}{|l|}{\small $bib$(111)} & \multicolumn{1}{c|}{ {1.48}} & \multicolumn{1}{c|}{ {\textbf{0.83}}} & \multicolumn{1}{c|}{ {2.93}} & \multicolumn{1}{c|}{ {1.31}} & \multicolumn{1}{c|}{ {\textbf{0.54*}}} & \multicolumn{1}{c|}{ {1.57}}\\
%\multicolumn{1}{|l|}{\small $book1$(785)} & \multicolumn{1}{c|}{ {2.07}} & \multicolumn{1}{c|}{ {\textbf{1.93}}} & \multicolumn{1}{c|}{ {3.14}} & \multicolumn{1}{c|}{ {1.95}} & \multicolumn{1}{c|}{ {\textbf{1.74*}}} & \multicolumn{1}{c|}{ {2.29}}\\
%\multicolumn{1}{|l|}{\small $book2$(611)} & \multicolumn{1}{c|}{ {1.75}} & \multicolumn{1}{c|}{ {1.66}} & \multicolumn{1}{c|}{ {2.94}} & \multicolumn{1}{c|}{ {\textbf{1.56}}} & \multicolumn{1}{c|}{ {\textbf{1.1*}}} & \multicolumn{1}{c|}{ {1.46}}\\
%\multicolumn{1}{|l|}{\small $geo$(102)} & \multicolumn{1}{c|}{ {4.49}} & \multicolumn{1}{c|}{ {\textbf{3.7}}} & \multicolumn{1}{c|}{ {4.61}} & \multicolumn{1}{c|}{ {4.61}} & \multicolumn{1}{c|}{ {\textbf{3.21*}}} & \multicolumn{1}{c|}{ {4.44}}\\
%\multicolumn{1}{|l|}{\small $news$(377)} & \multicolumn{1}{c|}{ {2.01}} & \multicolumn{1}{c|}{ {\textbf{1.54}}} & \multicolumn{1}{c|}{ {3.37}} & \multicolumn{1}{c|}{ {1.87}} & \multicolumn{1}{c|}{ {\textbf{0.64*}}} & \multicolumn{1}{c|}{ {2.53}}\\
%\multicolumn{1}{|l|}{\small $obj1$(22)} & \multicolumn{1}{c|}{ {2.7}} & \multicolumn{1}{c|}{ {1.65}} & \multicolumn{1}{c|}{ {3.42}} & \multicolumn{1}{c|}{ {\textbf{1.63}}} & \multicolumn{1}{c|}{ {\textbf{0.67*}}} &\multicolumn{1}{c|}{ {1.73}}\\
%\multicolumn{1}{|l|}{\small $obj2$(247)} & \multicolumn{1}{c|}{ {\textbf{2.12}}} & \multicolumn{1}{c|}{ {2.55}} & \multicolumn{1}{c|}{ {3.66}} & \multicolumn{1}{c|}{ {2.59}} & \multicolumn{1}{c|}{ {\textbf{0.64*}}} & \multicolumn{1}{c|}{ {3.02}}\\
%\multicolumn{1}{|l|}{\small $paper1$(53)} & \multicolumn{1}{c|}{ {1.73}} & \multicolumn{1}{c|}{ {\textbf{1.02}}} & \multicolumn{1}{c|}{ {3.36}} & \multicolumn{1}{c|}{ {1.55}} & \multicolumn{1}{c|}{ {\textbf{0.65*}}} & \multicolumn{1}{c|}{ {1.94}}\\
%\multicolumn{1}{|l|}{\small $paper2$(82)} & \multicolumn{1}{c|}{ {1.91}} & \multicolumn{1}{c|}{ {\textbf{1.28*}}} & \multicolumn{1}{c|}{ {3.3}} & \multicolumn{1}{c|}{ {1.8}} & \multicolumn{1}{c|}{ {\textbf{1.3}}} & \multicolumn{1}{c|}{ {2.16}}\\
%\multicolumn{1}{|l|}{\small $paper3$(47)} & \multicolumn{1}{c|}{ {1.99}} & \multicolumn{1}{c|}{ {\textbf{1.26}}} & \multicolumn{1}{c|}{ {3.53}} & \multicolumn{1}{c|}{ {1.78}} & \multicolumn{1}{c|}{ {\textbf{1.22*}}} & \multicolumn{1}{c|}{ {2.87}}\\
%\multicolumn{1}{|l|}{\small $paper4$(13)} & \multicolumn{1}{c|}{ {2.13}} & \multicolumn{1}{c|}{ {\textbf{1.13}}} & \multicolumn{1}{c|}{ {3.58}} & \multicolumn{1}{c|}{ {2.12}} & \multicolumn{1}{c|}{ {\textbf{0.74*}}} & \multicolumn{1}{c|}{ {2.79}}\\
%\multicolumn{1}{|l|}{\small $paper5$(12)} & \multicolumn{1}{c|}{ {2.14}} & \multicolumn{1}{c|}{ {\textbf{0.95}}} & \multicolumn{1}{c|}{ {3.75}} & \multicolumn{1}{c|}{ {1.46}} & \multicolumn{1}{c|}{ {\textbf{0.73*}}} & \multicolumn{1}{c|}{ {2.81}}\\
%\multicolumn{1}{|l|}{\small $paper6$(38)} & \multicolumn{1}{c|}{ {1.78}} & \multicolumn{1}{c|}{ {\textbf{0.96*}}} & \multicolumn{1}{c|}{ {3.45}} & \multicolumn{1}{c|}{ {1.82}} & \multicolumn{1}{c|}{ {\textbf{1.11}}} & \multicolumn{1}{c|}{ {1.75}}\\
%\multicolumn{1}{|l|}{\small $pic$(513)} & \multicolumn{1}{c|}{ {1.11}} & \multicolumn{1}{c|}{ {\textbf{0.9}}} & \multicolumn{1}{c|}{ {1.02}} & \multicolumn{1}{c|}{ {0.95}} & \multicolumn{1}{c|}{ {\textbf{0.77*}}} & \multicolumn{1}{c|}{ {0.99}}\\
%\multicolumn{1}{|l|}{\small $progc$(40)} & \multicolumn{1}{c|}{ {1.77}} & \multicolumn{1}{c|}{ {\textbf{0.85}}} & \multicolumn{1}{c|}{ {3.53}} & \multicolumn{1}{c|}{ {1.61}} & \multicolumn{1}{c|}{ {\textbf{0.82*}}} & \multicolumn{1}{c|}{ {1.78}}\\
%\multicolumn{1}{|l|}{\small $progl$(72)} & \multicolumn{1}{c|}{ {1.31}} & \multicolumn{1}{c|}{ {\textbf{0.61}}} & \multicolumn{1}{c|}{ {2.85}} & \multicolumn{1}{c|}{ {1.22}} & \multicolumn{1}{c|}{ {\textbf{0.5*}}} & \multicolumn{1}{c|}{ {1.64}}\\
%\multicolumn{1}{|l|}{\small $progp$(49)} & \multicolumn{1}{c|}{ {1.23}} & \multicolumn{1}{c|}{ {\textbf{0.7}}} & \multicolumn{1}{c|}{ {2.89}} & \multicolumn{1}{c|}{ {1.57}} & \multicolumn{1}{c|}{ {\textbf{0.45*}}} & \multicolumn{1}{c|}{ {1.54}}\\
%\multicolumn{1}{|l|}{\small $trans$(94)} & \multicolumn{1}{c|}{ {0.86}} & \multicolumn{1}{c|}{ {\textbf{0.45}}} & \multicolumn{1}{c|}{ {2.81}} & \multicolumn{1}{c|}{ {1.02}} & \multicolumn{1}{c|}{ {\textbf{0.4*}}} & \multicolumn{1}{c|}{ {0.9}}\\
%\hline
%\multicolumn{1}{|c|}{Average} & \multicolumn{1}{c|}{ $\mathbf{1.92\pm0.78}$} & \multicolumn{1}{c|}{ $\mathbf{1.33\pm0.79}$} & \multicolumn{1}{c|}{ $\mathbf{3.23\pm0.7}$} & \multicolumn{1}{c|}{ $\mathbf{1.8\pm0.8}$} & \multicolumn{1}{c|}{ $\mathbf{0.96\pm0.66}$}  & \multicolumn{1}{c|}{ $\mathbf{2.12\pm0.85}$} \\
\multicolumn{1}{|l|} {\small $bib$(111)}& \multicolumn{1}{c|}{\scriptsize {2.15}} & \multicolumn{1}{c|}{\scriptsize {\textbf{1.8*}}} & \multicolumn{1}{c|}{\scriptsize {3.25}} & \multicolumn{1}{c|}{\scriptsize {2.26}} & \multicolumn{1}{c|}{\scriptsize {\textbf{1.91}}} & \multicolumn{1}{c|}{\scriptsize {2.57}}\\
\multicolumn{1}{|l|} {\small $book1$(785)}& \multicolumn{1}{c|}{\scriptsize {2.29}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.2*}}} & \multicolumn{1}{c|}{\scriptsize {3.3}} & \multicolumn{1}{c|}{\scriptsize {2.57}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.27}}} & \multicolumn{1}{c|}{\scriptsize {2.5}}\\
\multicolumn{1}{|l|} {\small $book2$(611)}& \multicolumn{1}{c|}{\scriptsize {2.5}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.36*}}} & \multicolumn{1}{c|}{\scriptsize {3.4}} & \multicolumn{1}{c|}{\scriptsize {2.63}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.38}}} & \multicolumn{1}{c|}{\scriptsize {2.77}}\\
\multicolumn{1}{|l|} {\small $geo$(102)}& \multicolumn{1}{c|}{\scriptsize {4.93}} & \multicolumn{1}{c|}{\scriptsize {\textbf{4.47*}}} & \multicolumn{1}{c|}{\scriptsize {\textbf{4.48}}} & \multicolumn{1}{c|}{\scriptsize {\textbf{4.48}}} & \multicolumn{1}{c|}{\scriptsize {4.62}} & \multicolumn{1}{c|}{\scriptsize {4.86}}\\
\multicolumn{1}{|l|}{\small $news$(377)}& \multicolumn{1}{c|}{\scriptsize {3.04}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.81*}}} & \multicolumn{1}{c|}{\scriptsize {3.72}} & \multicolumn{1}{c|}{\scriptsize {3.07}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.82}}} & \multicolumn{1}{c|}{\scriptsize {3.4}}\\
\multicolumn{1}{|l|}{\small $obj1$(22)}& \multicolumn{1}{c|}{\scriptsize {7}} & \multicolumn{1}{c|}{\scriptsize {6.82}} & \multicolumn{1}{c|}{\scriptsize {\textbf{5.94*}}} & \multicolumn{1}{c|}{\scriptsize {\textbf{6}}} & \multicolumn{1}{c|}{\scriptsize {6.75}} & \multicolumn{1}{c|}{\scriptsize {6.37}}\\
\multicolumn{1}{|l|}{\small $obj2$(247)}& \multicolumn{1}{c|}{\scriptsize {3.92}} & \multicolumn{1}{c|}{\scriptsize {3.56}} & \multicolumn{1}{c|}{\scriptsize {3.99}} & \multicolumn{1}{c|}{\scriptsize {\textbf{3.48}}} & \multicolumn{1}{c|}{\scriptsize {\textbf{3.45*}}} & \multicolumn{1}{c|}{\scriptsize {3.72}}\\
\multicolumn{1}{|l|}{\small $paper1$(53)}& \multicolumn{1}{c|}{\scriptsize {3.48}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.95*}}} & \multicolumn{1}{c|}{\scriptsize {4.08}} & \multicolumn{1}{c|}{\scriptsize {3.38}} & \multicolumn{1}{c|}{\scriptsize {\textbf{3.08}}} & \multicolumn{1}{c|}{\scriptsize {3.93}}\\
\multicolumn{1}{|l|}{\small $paper2$(82)}& \multicolumn{1}{c|}{\scriptsize {2.75}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.49*}}} & \multicolumn{1}{c|}{\scriptsize {3.63}} & \multicolumn{1}{c|}{\scriptsize {2.81}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.53}}} & \multicolumn{1}{c|}{\scriptsize {3.19}}\\
\multicolumn{1}{|l|} {\small $paper3$(47)}& \multicolumn{1}{c|}{\scriptsize {2.96}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.59*}}} & \multicolumn{1}{c|}{\scriptsize {3.82}} & \multicolumn{1}{c|}{\scriptsize {3.09}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.75}}} & \multicolumn{1}{c|}{\scriptsize {3.4}}\\
\multicolumn{1}{|l|}{\small $paper4$(13)}& \multicolumn{1}{c|}{\scriptsize {3.87}} & \multicolumn{1}{c|}{\scriptsize {3.63}} & \multicolumn{1}{c|}{\scriptsize {4.13}} & \multicolumn{1}{c|}{\scriptsize {\textbf{3.61}}} & \multicolumn{1}{c|}{\scriptsize {\textbf{3.36*}}} & \multicolumn{1}{c|}{\scriptsize {3.99}}\\
\multicolumn{1}{|l|}{\small $paper5$(12)}& \multicolumn{1}{c|}{\scriptsize {4.57}} & \multicolumn{1}{c|}{\scriptsize {4.5}} & \multicolumn{1}{c|}{\scriptsize {4.51}} & \multicolumn{1}{c|}{\scriptsize {\textbf{4.16}}} & \multicolumn{1}{c|}{\scriptsize {\textbf{3.92*}}} & \multicolumn{1}{c|}{\scriptsize {4.6}}\\
\multicolumn{1}{|l|}{\small $paper6$(38)}& \multicolumn{1}{c|}{\scriptsize {3.9}} & \multicolumn{1}{c|}{\scriptsize {\textbf{3.21*}}} & \multicolumn{1}{c|}{\scriptsize {4.22}} & \multicolumn{1}{c|}{\scriptsize {3.6}} & \multicolumn{1}{c|}{\scriptsize {\textbf{3.31}}} & \multicolumn{1}{c|}{\scriptsize {4}}\\
\multicolumn{1}{|l|}{\small $pic$(513)}& \multicolumn{1}{c|}{\scriptsize {0.75}} & \multicolumn{1}{c|}{\scriptsize {\textbf{0.71}}} & \multicolumn{1}{c|}{\scriptsize {0.78}} & \multicolumn{1}{c|}{\scriptsize {0.79}} & \multicolumn{1}{c|}{\scriptsize {0.73}} & \multicolumn{1}{c|}{\scriptsize {\textbf{0.7*}}}\\
\multicolumn{1}{|l|}{\small $progc$(40)}& \multicolumn{1}{c|}{\scriptsize {3.28}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.85*}}} & \multicolumn{1}{c|}{\scriptsize {3.95}} & \multicolumn{1}{c|}{\scriptsize {3.22}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.94}}} & \multicolumn{1}{c|}{\scriptsize {3.71}}\\
\multicolumn{1}{|l|}{\small $progl$(72)}& \multicolumn{1}{c|}{\scriptsize {3.2}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.85*}}} & \multicolumn{1}{c|}{\scriptsize {3.7}} & \multicolumn{1}{c|}{\scriptsize {3.26}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.99}}} & \multicolumn{1}{c|}{\scriptsize {3.66}}\\
\multicolumn{1}{|l|}{\small $progp$(49)}& \multicolumn{1}{c|}{\scriptsize {2.88}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.53}}} & \multicolumn{1}{c|}{\scriptsize {3.24}} & \multicolumn{1}{c|}{\scriptsize {2.65}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.52*}}} & \multicolumn{1}{c|}{\scriptsize {2.95}}\\
\multicolumn{1}{|l|}{\small $trans$(94)}& \multicolumn{1}{c|}{\scriptsize {2.65}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.08*}}} & \multicolumn{1}{c|}{\scriptsize {3.56}} & \multicolumn{1}{c|}{\scriptsize {2.61}} & \multicolumn{1}{c|}{\scriptsize {\textbf{2.29}}} & \multicolumn{1}{c|}{\scriptsize {3.01}}\\
\hline
\multicolumn{1}{|c|}{Average$\pm${\scriptsize SEM}} & \multicolumn{1}{c|}{\scriptsize ${3.34\pm0.07}$} & \multicolumn{1}{c|}{\scriptsize ${\mathbf{3.02\pm0.07*}}$} & \multicolumn{1}{c|}{\scriptsize ${3.76\pm0.05}$} & \multicolumn{1}{c|}{\scriptsize ${3.2\pm0.06}$} & \multicolumn{1}{c|}{\scriptsize ${\mathbf{3.03\pm0.07}}$} & \multicolumn{1}{c|}{\scriptsize ${3.52\pm0.06}$} \\
\hline\hline
\end{tabular}
\end{center}
\caption{\label{tab:calgary} Average log-loss (equivalent to
bits/symbol) of the VMM algorithms over the Calgary Corpus.
        For each sequence (row) the winner is starred and appears in boldface. The
        runner-up appears in boldface.}
\end{table}
\end{small}

Next we present the results for the music MIDI files, which are
summarized in Table~\ref{tab:music}. The table has four sections
corresponding to classical pieces, jazz, 14 improvisations of the
same jazz piece and rock/pop. Individual average losses for these
sections are specified as well. $\dctw$ is the overall winner
and $\ppmc$ is the overall runner-up. Both these algorithms are
significantly better than the rest. The worst algorithm is, again,
$\lz$.

Some observations can be drawn about the ``complexity'' of the various pieces by considering the
results of the best predictors with respect to the individual sequences.
Taking the $\dctw$ average losses,
in the classical music domain we see that the Mozart pieces are the easiest to predict (with an average
loss of at most 0.93). The least predictable pieces are Debussy's Children Corner 6 (1.86) and Beethoven's Symphony 6(1.78 loss).
%and Rachmaninov piano
%concerto 3 (1.15 loss). Note that Rachmaninov piano concerto 2 is considerably more predictable (0.6) than
%concerto 3.
The most predictable piece overall is the rock piece ``You really
got me'' by the Kinks. The least predictable rock piece is
``Sunshine of your love'' by Cream. The least predictable piece
overall is the jazz piece ``Satin doll 2'' by Duke Ellington. The
most predictable jazz piece is ``The girl from Ipanema'' by Jobim.
Among the improvisations of ``All of me'', there is considerable
variability starting with 0.5 loss (All of me 12) and ending with
1.65 loss (All of me 8).
%\footnote{The readers are encouraged to
%listen to these pieces and judge the ``complexity'' of these
%pieces for themselves. MIDI files of all the pieces are available
%at \paperURL.}
We emphasize that such observations
may have a qualitative value due to the great
variability among different arrangements of the same musical piece
(particularly jazz tunes
involving improvisation).
The readers are encouraged to
listen to these pieces and judge the ``complexity'' of these
pieces for themselves. MIDI files of all the pieces are available
at \paperURL.


\begin{table}
%\begin{singlespace}
\setstretch {0.8}
\begin{tabular}{|l|c|c|c|c|c|c|}
%\multicolumn{8}{c}%
%{\textbf{Musical Corpus Average Results \small{[bps]}}}\\[5Pt]
\hline\hline
% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%&{\sffamily{\scriptsize Binary}}&{\sffamily{\scriptsize Decomposed}}&
%{\sffamily{\scriptsize LZ78}}&{\sffamily{\scriptsize LZms}}&{\sffamily{\scriptsize PPMC}}&{\sffamily{\scriptsize PST}}\\
%\multicolumn{1}{|c|}{\sffamily {\scriptsize Average Of}}&{\sffamily{\scriptsize CTW}}&{\sffamily{\scriptsize CTW}}&&&&\\
Sequence & $\bctw$ & $\dctw$ & $\lz$ & $\lzms$ & $\ppmc$ & $\pst$ \\
\hline\hline
%\endfirsthead
%\multicolumn{8}{c}%
%{\textbf{Musical Corpus Average Results \small{[bps]}}}{(\textit{continued})}\\[5Pt]
%\hline\hline
%% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%& {\sffamily {\small Binary}} & {\sffamily {\small Decomposed}} &
%{\sffamily {\small LZ78}} & {\sffamily  {\small LZms}} &
%{\sffamily  {\small PPMC}} & {\sffamily  {\small PPMZ}} & {\sffamily  {\small PST}}\\
%\multicolumn{1}{|c|}{\sffamily {\small Average Of}} &  {\sffamily {\small CTW}}  &  {\sffamily {\small CTW}}&  &  & & &\\
%\hline\hline
%\endhead
%\hline
%\multicolumn{8}{r}%
%{\small \itshape continued on the next page}
%\endfoot
%\hline
%\multicolumn{8}{r}%
%{\small \itshape Units are in Bit per Symbols}
%\endlastfoot
%starthere
\multicolumn{1}{|l|}{\scriptsize Goldberg Variations}& \multicolumn{1}{c|}{\scriptsize 1.09} & \multicolumn{1}{c|}{\scriptsize \textbf{1*}} & \multicolumn{1}{c|}{\scriptsize 1.59} & \multicolumn{1}{c|}{\scriptsize 1.28} & \multicolumn{1}{c|}{\scriptsize\textbf{ 1.04}} & \multicolumn{1}{c|}{\scriptsize 1.15} \\
\multicolumn{1}{|l|}{\scriptsize Toccata and Fuga}& \multicolumn{1}{c|}{\scriptsize 1.17} & \multicolumn{1}{c|}{\scriptsize \textbf{1.08*}} & \multicolumn{1}{c|}{\scriptsize 1.67} & \multicolumn{1}{c|}{\scriptsize 1.34} & \multicolumn{1}{c|}{\scriptsize \textbf{1.14}} & \multicolumn{1}{c|}{\scriptsize 1.37} \\
\multicolumn{1}{|l|}{\scriptsize for Elise}& \multicolumn{1}{c|}{\scriptsize 1.76} & \multicolumn{1}{c|}{\scriptsize \textbf{1.57}} & \multicolumn{1}{c|}{\scriptsize 2.32} & \multicolumn{1}{c|}{\scriptsize 1.83} & \multicolumn{1}{c|}{\scriptsize \textbf{1.57}} & \multicolumn{1}{c|}{\scriptsize 2.08} \\
\multicolumn{1}{|l|}{\scriptsize Beethoven - Symphony 6}& \multicolumn{1}{c|}{\scriptsize 1.91} & \multicolumn{1}{c|}{\scriptsize \textbf{1.78*}} & \multicolumn{1}{c|}{\scriptsize 2.2} & \multicolumn{1}{c|}{\scriptsize 1.99} & \multicolumn{1}{c|}{\scriptsize \textbf{1.79}} & \multicolumn{1}{c|}{\scriptsize 2.26} \\
\multicolumn{1}{|l|}{\scriptsize Chopin - Etude 1 op. 10}& \multicolumn{1}{c|}{\scriptsize 1.14} & \multicolumn{1}{c|}{\scriptsize \textbf{1.07*}} & \multicolumn{1}{c|}{\scriptsize 1.75} & \multicolumn{1}{c|}{\scriptsize 1.36} & \multicolumn{1}{c|}{\scriptsize \textbf{1.09}} & \multicolumn{1}{c|}{\scriptsize 1.24} \\
\multicolumn{1}{|l|}{\scriptsize Chopin - Etude 12 op. 10}& \multicolumn{1}{c|}{\scriptsize \textbf{1.67}} & \multicolumn{1}{c|}{\scriptsize \textbf{1.54*}} & \multicolumn{1}{c|}{\scriptsize 2.11} & \multicolumn{1}{c|}{\scriptsize 1.93} & \multicolumn{1}{c|}{\scriptsize 1.73} & \multicolumn{1}{c|}{\scriptsize 1.72} \\
\multicolumn{1}{|l|}{\scriptsize Children's Corner - 1}& \multicolumn{1}{c|}{\scriptsize \textbf{1.28}} & \multicolumn{1}{c|}{\scriptsize \textbf{1.23*}} & \multicolumn{1}{c|}{\scriptsize 1.53} & \multicolumn{1}{c|}{\scriptsize 1.52} & \multicolumn{1}{c|}{\scriptsize 1.3} & \multicolumn{1}{c|}{\scriptsize 1.39} \\
\multicolumn{1}{|l|}{\scriptsize Children's Corner - 6}& \multicolumn{1}{c|}{\scriptsize 2.03} & \multicolumn{1}{c|}{\scriptsize \textbf{1.86*}} & \multicolumn{1}{c|}{\scriptsize 2.28} & \multicolumn{1}{c|}{\scriptsize 2.13} & \multicolumn{1}{c|}{\scriptsize \textbf{1.97}} & \multicolumn{1}{c|}{\scriptsize 2.28} \\
\multicolumn{1}{|l|}{\scriptsize Mozart K.551}& \multicolumn{1}{c|}{\scriptsize 1.04} & \multicolumn{1}{c|}{\scriptsize \textbf{0.85*}} & \multicolumn{1}{c|}{\scriptsize 1.64} & \multicolumn{1}{c|}{\scriptsize 1.18} & \multicolumn{1}{c|}{\scriptsize \textbf{0.96}} & \multicolumn{1}{c|}{\scriptsize 1.45} \\
\multicolumn{1}{|l|}{\scriptsize Mozart K.183}& \multicolumn{1}{c|}{\scriptsize 1.04} & \multicolumn{1}{c|}{\scriptsize \textbf{0.93*}} & \multicolumn{1}{c|}{\scriptsize 1.71} & \multicolumn{1}{c|}{\scriptsize 1.2} & \multicolumn{1}{c|}{\scriptsize \textbf{0.99}} & \multicolumn{1}{c|}{\scriptsize 1.7} \\
\multicolumn{1}{|l|}{\scriptsize Rachmaninov Piano Concerto 2}& \multicolumn{1}{c|}{\scriptsize 1.16} & \multicolumn{1}{c|}{\scriptsize \textbf{1.06*}} & \multicolumn{1}{c|}{\scriptsize 1.8} & \multicolumn{1}{c|}{\scriptsize 1.35} & \multicolumn{1}{c|}{\scriptsize \textbf{1.13}} & \multicolumn{1}{c|}{\scriptsize 1.34} \\
\multicolumn{1}{|l|}{\scriptsize Rachmaninov Piano Concerto 3}& \multicolumn{1}{c|}{\scriptsize 1.91} & \multicolumn{1}{c|}{\scriptsize 1.75} & \multicolumn{1}{c|}{\scriptsize 2.09} & \multicolumn{1}{c|}{\scriptsize 1.98} & \multicolumn{1}{c|}{\scriptsize 1.82} & \multicolumn{1}{c|}{\scriptsize 2.1} \\
\hline
{\scriptsize \textbf{Average Classical}}& \multicolumn{1}{c|}{\scriptsize ${1.43\pm0.02}$} & \multicolumn{1}{c|}{\scriptsize ${1.31\pm0.02}$} & \multicolumn{1}{c|}{\scriptsize ${1.89\pm0.02}$} & \multicolumn{1}{c|}{\scriptsize ${1.59\pm0.02}$} & \multicolumn{1}{c|}{\scriptsize ${1.38\pm0.02}$} & \multicolumn{1}{c|}{\scriptsize ${1.67\pm0.03}$} \\
\hline
\multicolumn{1}{|l|}{\scriptsize Giant Steps} & \multicolumn{1}{c|}{\scriptsize 1.51} & \multicolumn{1}{c|}{\scriptsize 1.33} & \multicolumn{1}{c|}{\scriptsize 2.01} & \multicolumn{1}{c|}{\scriptsize \textbf{1.29}} & \multicolumn{1}{c|}{\scriptsize \textbf{1.24*}} & \multicolumn{1}{c|}{\scriptsize 1.82} \\
\multicolumn{1}{|l|}{\scriptsize Satin Doll 1} & \multicolumn{1}{c|}{\scriptsize 1.7} & \multicolumn{1}{c|}{\scriptsize \textbf{1.41*}} & \multicolumn{1}{c|}{\scriptsize 2.28} & \multicolumn{1}{c|}{\scriptsize 1.73} & \multicolumn{1}{c|}{\scriptsize \textbf{1.47}} & \multicolumn{1}{c|}{\scriptsize 1.89} \\
\multicolumn{1}{|l|}{\scriptsize Satin Doll 2} & \multicolumn{1}{c|}{\scriptsize 2.56} & \multicolumn{1}{c|}{\scriptsize \textbf{2.27*}} & \multicolumn{1}{c|}{\scriptsize 2.53} & \multicolumn{1}{c|}{\scriptsize 2.54} & \multicolumn{1}{c|}{\scriptsize \textbf{2.38}} & \multicolumn{1}{c|}{\scriptsize 3.32} \\
\multicolumn{1}{|l|}{\scriptsize The Girl from Ipanema} & \multicolumn{1}{c|}{\scriptsize 1.4} & \multicolumn{1}{c|}{\scriptsize \textbf{1.11*}} & \multicolumn{1}{c|}{\scriptsize 1.95} & \multicolumn{1}{c|}{\scriptsize 1.5} & \multicolumn{1}{c|}{\scriptsize \textbf{1.2}} & \multicolumn{1}{c|}{\scriptsize 1.36} \\
\multicolumn{1}{|l|}{\scriptsize 7 Steps to Heaven} & \multicolumn{1}{c|}{\scriptsize 1.7} & \multicolumn{1}{c|}{\scriptsize \textbf{1.42*}} & \multicolumn{1}{c|}{\scriptsize 2.1} & \multicolumn{1}{c|}{\scriptsize 1.87} & \multicolumn{1}{c|}{\scriptsize \textbf{1.53}} & \multicolumn{1}{c|}{\scriptsize 1.86} \\
\multicolumn{1}{|l|}{\scriptsize Stolen Moments} & \multicolumn{1}{c|}{\scriptsize 1.81} & \multicolumn{1}{c|}{\scriptsize \textbf{1.24*}} & \multicolumn{1}{c|}{\scriptsize 2.28} & \multicolumn{1}{c|}{\scriptsize 1.59} & \multicolumn{1}{c|}{\scriptsize \textbf{1.37}} & \multicolumn{1}{c|}{\scriptsize 1.8} \\
\hline
{\scriptsize \textbf{Average Jazz}}& \multicolumn{1}{c|}{\scriptsize ${1.78\pm0.06}$} & \multicolumn{1}{c|}{\scriptsize ${\mathbf{1.46\pm0.06*}}$} & \multicolumn{1}{c|}{\scriptsize ${2.19\pm0.04}$} & \multicolumn{1}{c|}{\scriptsize ${1.76\pm0.04}$} & \multicolumn{1}{c|}{\scriptsize ${\mathbf{1.53\pm0.06}}$} & \multicolumn{1}{c|}{\scriptsize ${2.01\pm0.09}$} \\
\hline
\multicolumn{1}{|l|}{\scriptsize All of Me 1} & \multicolumn{1}{c|}{\scriptsize 1.97} & \multicolumn{1}{c|}{\scriptsize \textbf{1.43*}} & \multicolumn{1}{c|}{\scriptsize 2.33} & \multicolumn{1}{c|}{\scriptsize 1.97} & \multicolumn{1}{c|}{\scriptsize \textbf{1.73}} & \multicolumn{1}{c|}{\scriptsize 1.88} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 2} & \multicolumn{1}{c|}{\scriptsize 2.51} & \multicolumn{1}{c|}{\scriptsize \textbf{1.05*}} & \multicolumn{1}{c|}{\scriptsize 2.52} & \multicolumn{1}{c|}{\scriptsize 1.9} & \multicolumn{1}{c|}{\scriptsize 1.65} & \multicolumn{1}{c|}{\scriptsize \textbf{1.28}} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 3} & \multicolumn{1}{c|}{\scriptsize 1.29} & \multicolumn{1}{c|}{\scriptsize \textbf{1.08*}} & \multicolumn{1}{c|}{\scriptsize 1.97} & \multicolumn{1}{c|}{\scriptsize 1.42} & \multicolumn{1}{c|}{\scriptsize \textbf{1.17}} & \multicolumn{1}{c|}{\scriptsize 1.45} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 4} & \multicolumn{1}{c|}{\scriptsize 1.83} & \multicolumn{1}{c|}{\scriptsize \textbf{1.4*}} & \multicolumn{1}{c|}{\scriptsize 2.12} & \multicolumn{1}{c|}{\scriptsize 1.88} & \multicolumn{1}{c|}{\scriptsize \textbf{1.46}} & \multicolumn{1}{c|}{\scriptsize 2.32} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 5} & \multicolumn{1}{c|}{\scriptsize 0.92} & \multicolumn{1}{c|}{\scriptsize \textbf{0.78*}} & \multicolumn{1}{c|}{\scriptsize 1.72} & \multicolumn{1}{c|}{\scriptsize 1.15} & \multicolumn{1}{c|}{\scriptsize \textbf{0.9}} & \multicolumn{1}{c|}{\scriptsize 0.96} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 6} & \multicolumn{1}{c|}{\scriptsize 1.62} & \multicolumn{1}{c|}{\scriptsize \textbf{1.21*}} & \multicolumn{1}{c|}{\scriptsize 2.21} & \multicolumn{1}{c|}{\scriptsize 1.55} & \multicolumn{1}{c|}{\scriptsize \textbf{1.28}} & \multicolumn{1}{c|}{\scriptsize 1.52} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 7} & \multicolumn{1}{c|}{\scriptsize 1.97} & \multicolumn{1}{c|}{\scriptsize \textbf{1.65*}} & \multicolumn{1}{c|}{\scriptsize 2.35} & \multicolumn{1}{c|}{\scriptsize 1.94} & \multicolumn{1}{c|}{\scriptsize \textbf{1.75}} & \multicolumn{1}{c|}{\scriptsize 2.44} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 8} & \multicolumn{1}{c|}{\scriptsize 1.88} & \multicolumn{1}{c|}{\scriptsize \textbf{1.61*}} & \multicolumn{1}{c|}{\scriptsize 2.29} & \multicolumn{1}{c|}{\scriptsize 1.97} & \multicolumn{1}{c|}{\scriptsize \textbf{1.67}} & \multicolumn{1}{c|}{\scriptsize 2.21} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 9} & \multicolumn{1}{c|}{\scriptsize 1.79} & \multicolumn{1}{c|}{\scriptsize \textbf{1.58*}} & \multicolumn{1}{c|}{\scriptsize 2.2} & \multicolumn{1}{c|}{\scriptsize 1.97} & \multicolumn{1}{c|}{\scriptsize \textbf{1.7}} & \multicolumn{1}{c|}{\scriptsize 2.13} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 10} & \multicolumn{1}{c|}{\scriptsize 1.32} & \multicolumn{1}{c|}{\scriptsize \textbf{1.07*}} & \multicolumn{1}{c|}{\scriptsize 1.96} & \multicolumn{1}{c|}{\scriptsize 1.42} & \multicolumn{1}{c|}{\scriptsize \textbf{1.16}} & \multicolumn{1}{c|}{\scriptsize 1.4} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 11} & \multicolumn{1}{c|}{\scriptsize \textbf{1.61}} & \multicolumn{1}{c|}{\scriptsize \textbf{1.54*}} & \multicolumn{1}{c|}{\scriptsize 2.26} & \multicolumn{1}{c|}{\scriptsize 1.93} & \multicolumn{1}{c|}{\scriptsize 1.72} & \multicolumn{1}{c|}{\scriptsize 1.68} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 12} & \multicolumn{1}{c|}{\scriptsize 0.79} & \multicolumn{1}{c|}{\scriptsize \textbf{0.5*}} & \multicolumn{1}{c|}{\scriptsize 1.8} & \multicolumn{1}{c|}{\scriptsize 0.92} & \multicolumn{1}{c|}{\scriptsize \textbf{0.54}} & \multicolumn{1}{c|}{\scriptsize 0.57} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 13} & \multicolumn{1}{c|}{\scriptsize 0.97} & \multicolumn{1}{c|}{\scriptsize \textbf{0.68*}} & \multicolumn{1}{c|}{\scriptsize 1.78} & \multicolumn{1}{c|}{\scriptsize 1.12} & \multicolumn{1}{c|}{\scriptsize \textbf{0.7}} & \multicolumn{1}{c|}{\scriptsize 0.83} \\
\multicolumn{1}{|l|}{\scriptsize All of Me 14} & \multicolumn{1}{c|}{\scriptsize 1.85} & \multicolumn{1}{c|}{\scriptsize \textbf{1.63*}} & \multicolumn{1}{c|}{\scriptsize 2.2} & \multicolumn{1}{c|}{\scriptsize 1.89} & \multicolumn{1}{c|}{\scriptsize \textbf{1.68}} & \multicolumn{1}{c|}{\scriptsize 2.17} \\
\hline
{\scriptsize \textbf{Average Jazz Impro.}}& \multicolumn{1}{c|}{\scriptsize ${1.59\pm0.17}$} & \multicolumn{1}{c|}{\scriptsize ${\mathbf{1.23\pm0.09*}}$} & \multicolumn{1}{c|}{\scriptsize ${2.12\pm0.09}$} & \multicolumn{1}{c|}{\scriptsize ${1.65\pm0.11}$} & \multicolumn{1}{c|}{\scriptsize ${\mathbf{1.37\pm0.12}}$} & \multicolumn{1}{c|}{\scriptsize ${1.63\pm0.15}$} \\
\hline
\multicolumn{1}{|l|}{\scriptsize Don't Stop till You Get Enough} & \multicolumn{1}{c|}{\scriptsize 1.03} & \multicolumn{1}{c|}{\scriptsize \textbf{0.64*}} & \multicolumn{1}{c|}{\scriptsize 1.82} & \multicolumn{1}{c|}{\scriptsize 1.07} & \multicolumn{1}{c|}{\scriptsize \textbf{0.69}} & \multicolumn{1}{c|}{\scriptsize 0.72} \\
\multicolumn{1}{|l|}{\scriptsize Sir Duke} & \multicolumn{1}{c|}{\scriptsize 1.14} & \multicolumn{1}{c|}{\scriptsize \textbf{0.47}} & \multicolumn{1}{c|}{\scriptsize 2} & \multicolumn{1}{c|}{\scriptsize 0.99} & \multicolumn{1}{c|}{\scriptsize 0.59} & \multicolumn{1}{c|}{\scriptsize \textbf{0.35*}} \\
\multicolumn{1}{|l|}{\scriptsize Let's Dance} & \multicolumn{1}{c|}{\scriptsize 1.22} & \multicolumn{1}{c|}{\scriptsize \textbf{0.94*}} & \multicolumn{1}{c|}{\scriptsize 1.95} & \multicolumn{1}{c|}{\scriptsize 1.33} & \multicolumn{1}{c|}{\scriptsize \textbf{1.06}} & \multicolumn{1}{c|}{\scriptsize 1.28} \\
\multicolumn{1}{|l|}{\scriptsize Like a Rolling Stone} & \multicolumn{1}{c|}{\scriptsize 1.63} & \multicolumn{1}{c|}{\scriptsize \textbf{1.45*}} & \multicolumn{1}{c|}{\scriptsize 2.07} & \multicolumn{1}{c|}{\scriptsize 1.7} & \multicolumn{1}{c|}{\scriptsize \textbf{1.48}} & \multicolumn{1}{c|}{\scriptsize 1.83} \\
\multicolumn{1}{|l|}{\scriptsize Sunshine of Your Love} & \multicolumn{1}{c|}{\scriptsize 1.68} & \multicolumn{1}{c|}{\scriptsize \textbf{1.47*}} & \multicolumn{1}{c|}{\scriptsize 2.16} & \multicolumn{1}{c|}{\scriptsize 1.81} & \multicolumn{1}{c|}{\scriptsize \textbf{1.58}} & \multicolumn{1}{c|}{\scriptsize 2.01} \\
\multicolumn{1}{|l|}{\scriptsize You Really Got Me} & \multicolumn{1}{c|}{\scriptsize 0.31} & \multicolumn{1}{c|}{\scriptsize \textbf{0.16*}} & \multicolumn{1}{c|}{\scriptsize 1} & \multicolumn{1}{c|}{\scriptsize 0.49} & \multicolumn{1}{c|}{\scriptsize 0.23} & \multicolumn{1}{c|}{\scriptsize \textbf{0.17}} \\
\hline
{\scriptsize \textbf{Average Rock/Pop}}& \multicolumn{1}{c|}{\scriptsize ${1.17\pm0.05}$} & \multicolumn{1}{c|}{\scriptsize ${\mathbf{0.85\pm0.04*}}$} & \multicolumn{1}{c|}{\scriptsize ${1.83\pm0.04}$} & \multicolumn{1}{c|}{\scriptsize ${1.23\pm0.04}$} & \multicolumn{1}{c|}{\scriptsize ${\mathbf{0.94\pm0.04}}$} & \multicolumn{1}{c|}{\scriptsize ${1.06\pm0.06}$} \\
\hline
\hline
Average$\pm${\scriptsize SEM}& \multicolumn{1}{c|}{\scriptsize ${1.49\pm0.08}$} & \multicolumn{1}{c|}{\scriptsize ${\mathbf{1.21\pm0.05*}}$} & \multicolumn{1}{c|}{\scriptsize ${2.00\pm0.05}$} & \multicolumn{1}{c|}{\scriptsize ${1.56\pm0.05}$} & \multicolumn{1}{c|}{\scriptsize ${\mathbf{\mathbf{1.30\pm0.06}}}$} & \multicolumn{1}{c|}{\scriptsize ${1.59\pm0.08}$} \\
%\multicolumn{1}{|l|}{\scriptsize Goldberg Variations}&\multicolumn{1}{c|}{\scriptsize 0.8}&\multicolumn{1}{c|}{\scriptsize \textbf{0.62*}} & \multicolumn{1}{c|}{\scriptsize 1.87} & \multicolumn{1}{c|}{\scriptsize 1.37} & \multicolumn{1}{c|}{\scriptsize \textbf{0.66}} & \multicolumn{1}{c|}{\scriptsize 0.98} \\
%\multicolumn{1}{|l|}{\scriptsize Toccata and Fuga}&\multicolumn{1}{c|}{\scriptsize 0.82}&\multicolumn{1}{c|}{\scriptsize \textbf{0.74}} & \multicolumn{1}{c|}{\scriptsize 1.7} & \multicolumn{1}{c|}{\scriptsize 1.26} & \multicolumn{1}{c|}{\scriptsize \textbf{0.57*}} & \multicolumn{1}{c|}{\scriptsize 1.14} \\
%\multicolumn{1}{|l|}{\scriptsize for Elise}&\multicolumn{1}{c|}{\scriptsize 1.14}&\multicolumn{1}{c|}{\scriptsize \textbf{0.62*}} & \multicolumn{1}{c|}{\scriptsize 2.62} & \multicolumn{1}{c|}{\scriptsize 1.88} & \multicolumn{1}{c|}{\scriptsize \textbf{0.71}} & \multicolumn{1}{c|}{\scriptsize 1.4} \\
%\multicolumn{1}{|l|}{\scriptsize Beethoven - Symphony 6}&\multicolumn{1}{c|}{\scriptsize 0.98}&\multicolumn{1}{c|}{\scriptsize \textbf{0.72}} & \multicolumn{1}{c|}{\scriptsize 2.2} & \multicolumn{1}{c|}{\scriptsize 1.39} & \multicolumn{1}{c|}{\scriptsize \textbf{0.51*}} & \multicolumn{1}{c|}{\scriptsize 1.29} \\
%\multicolumn{1}{|l|}{\scriptsize Chopin - Etude 1 op. 10}&\multicolumn{1}{c|}{\scriptsize 1.5}&\multicolumn{1}{c|}{\scriptsize \textbf{1.28}} & \multicolumn{1}{c|}{\scriptsize 2.56} & \multicolumn{1}{c|}{\scriptsize 2.26} & \multicolumn{1}{c|}{\scriptsize \textbf{1.27*}} & \multicolumn{1}{c|}{\scriptsize 1.9} \\
%\multicolumn{1}{|l|}{\scriptsize Chopin - Etude 12 op. 10}&\multicolumn{1}{c|}{\scriptsize 1.04}&\multicolumn{1}{c|}{\scriptsize 0.98} & \multicolumn{1}{c|}{\scriptsize 2.08} & \multicolumn{1}{c|}{\scriptsize 1.6} & \multicolumn{1}{c|}{\scriptsize \textbf{0.9*}}  & \multicolumn{1}{c|}{\scriptsize \textbf{0.96}} \\
%\multicolumn{1}{|l|}{\scriptsize Children's Corner - 1}&\multicolumn{1}{c|}{\scriptsize 1.18}&\multicolumn{1}{c|}{\scriptsize \textbf{0.91}} & \multicolumn{1}{c|}{\scriptsize 2.16} & \multicolumn{1}{c|}{\scriptsize 1.63} & \multicolumn{1}{c|}{\scriptsize \textbf{0.55*}} & \multicolumn{1}{c|}{\scriptsize 1.44} \\
%\multicolumn{1}{|l|}{\scriptsize Children's Corner - 6}&\multicolumn{1}{c|}{\scriptsize 0.98}&\multicolumn{1}{c|}{\scriptsize \textbf{0.66}} & \multicolumn{1}{c|}{\scriptsize 2.02} & \multicolumn{1}{c|}{\scriptsize 1.37} & \multicolumn{1}{c|}{\scriptsize \textbf{0.55*}} & \multicolumn{1}{c|}{\scriptsize 1.43} \\
%\multicolumn{1}{|l|}{\scriptsize Mozart K.551}& \multicolumn{1}{c|}{\scriptsize 0.64}&\multicolumn{1}{c|}{\scriptsize \textbf{0.43}}&\multicolumn{1}{c|}{\scriptsize 1.87} & \multicolumn{1}{c|}{\scriptsize 0.97} & \multicolumn{1}{c|}{\scriptsize \textbf{0.35*}} & \multicolumn{1}{c|}{\scriptsize 0.46} \\
%\multicolumn{1}{|l|}{\scriptsize Mozart K.183}& \multicolumn{1}{c|}{\scriptsize 0.7}&\multicolumn{1}{c|}{\scriptsize \textbf{0.49}}&\multicolumn{1}{c|}{\scriptsize 1.62} & \multicolumn{1}{c|}{\scriptsize 0.99} & \multicolumn{1}{c|}{\scriptsize \textbf{0.37*}} & \multicolumn{1}{c|}{\scriptsize 0.52} \\
%\multicolumn{1}{|l|}{\scriptsize Rachmaninov Piano Concerto 2}&\multicolumn{1}{c|}{\scriptsize 0.78}&\multicolumn{1}{c|}{\scriptsize \textbf{0.63}} & \multicolumn{1}{c|}{\scriptsize 2.09} & \multicolumn{1}{c|}{\scriptsize 1.39} & \multicolumn{1}{c|}{\scriptsize \textbf{0.6*}} & \multicolumn{1}{c|}{\scriptsize 1.22} \\
%\multicolumn{1}{|l|}{\scriptsize Rachmaninov Piano Concerto 3}&\multicolumn{1}{c|}{\scriptsize 1.37}&\multicolumn{1}{c|}{\scriptsize \textbf{1.03*}} & \multicolumn{1}{c|}{\scriptsize 2.61} & \multicolumn{1}{c|}{\scriptsize 1.98} & \multicolumn{1}{c|}{\scriptsize \textbf{1.15}} & \multicolumn{1}{c|}{\scriptsize 1.7} \\
%\hline
%\multicolumn{1}{|l|}{\scriptsize \textbf{Average Classical}}&\scriptsize{$0.99\pm0.27$}&\scriptsize{$\mathbf{0.76\pm0.25}$}&\scriptsize{$2.12\pm0.34$}&\scriptsize{$1.50\pm0.39$}&\scriptsize{$\mathbf{0.68\pm0.29*}$}&\scriptsize{$1.20\pm0.43$} \\
%\hline
%\multicolumn{1}{|l|}{\scriptsize Giant Steps}&\multicolumn{1}{c|}{\scriptsize 1.45}&\multicolumn{1}{c|}{\scriptsize \textbf{0.52*}}&\multicolumn{1}{c|}{\scriptsize 2.3} & \multicolumn{1}{c|}{\scriptsize 1.62} & \multicolumn{1}{c|}{\scriptsize \textbf{0.74}} & \multicolumn{1}{c|}{\scriptsize 0.78} \\
%\multicolumn{1}{|l|}{\scriptsize Satin Doll 1}&\multicolumn{1}{c|}{\scriptsize 1.1}&\multicolumn{1}{c|}{\scriptsize \textbf{0.68}}&\multicolumn{1}{c|}{\scriptsize 2.58} & \multicolumn{1}{c|}{\scriptsize 1.75} & \multicolumn{1}{c|}{\scriptsize \textbf{0.63*}} & \multicolumn{1}{c|}{\scriptsize 1.49} \\
%\multicolumn{1}{|l|}{\scriptsize Satin Doll 2}&\multicolumn{1}{c|}{\scriptsize 1.35}&\multicolumn{1}{c|}{\scriptsize \textbf{0.91}}&\multicolumn{1}{c|}{\scriptsize 2.71} & \multicolumn{1}{c|}{\scriptsize 1.89} & \multicolumn{1}{c|}{\scriptsize \textbf{0.7*}} & \multicolumn{1}{c|}{\scriptsize 1.65} \\
%\multicolumn{1}{|l|}{\scriptsize The Girl From Ipanema}&\multicolumn{1}{c|}{\scriptsize 1.05}&\multicolumn{1}{c|}{\scriptsize \textbf{0.62}}&\multicolumn{1}{c|}{\scriptsize 2.42} & \multicolumn{1}{c|}{\scriptsize 1.67} & \multicolumn{1}{c|}{\scriptsize \textbf{0.6*}}& \multicolumn{1}{c|}{\scriptsize 1.21} \\
%\multicolumn{1}{|l|}{\scriptsize 7 Steps to Heaven}&\multicolumn{1}{c|}{\scriptsize 1.35}&\multicolumn{1}{c|}{\scriptsize \textbf{0.95}}&\multicolumn{1}{c|}{\scriptsize 2.4} & \multicolumn{1}{c|}{\scriptsize 1.84} & \multicolumn{1}{c|}{\scriptsize \textbf{0.75}} & \multicolumn{1}{c|}{\scriptsize 1.61} \\
%\multicolumn{1}{|l|}{\scriptsize Stolen Moments}&\multicolumn{1}{c|}{\scriptsize 1.32}&\multicolumn{1}{c|}{\scriptsize \textbf{0.67*}}&\multicolumn{1}{c|}{\scriptsize 2.79} & \multicolumn{1}{c|}{\scriptsize 1.83} & \multicolumn{1}{c|}{\scriptsize \textbf{0.73}} & \multicolumn{1}{c|}{\scriptsize 1.16} \\
%\hline
%\multicolumn{1}{|l|}{\scriptsize \textbf{Average Jazz}}&\scriptsize{$1.27\pm0.16$}&\scriptsize{$\mathbf{0.73\pm0.17}$}&\scriptsize{$2.53\pm0.19$}&\scriptsize{$1.77\pm0.10$}&\scriptsize{$\mathbf{0.69\pm0.06\textbf{*}}$}&\scriptsize{$1.32\pm0.33$} \\
%\hline
%\multicolumn{1}{|l|}{\scriptsize All Of Me 1}& \multicolumn{1}{c|}{\scriptsize 1.35} & \multicolumn{1}{c|}{\scriptsize \textbf{0.71}} & \multicolumn{1}{c|}{\scriptsize 2.67} & \multicolumn{1}{c|}{\scriptsize 1.75} & \multicolumn{1}{c|}{\scriptsize \textbf{0.61*}} & \multicolumn{1}{c|}{\scriptsize 1.59} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 2}& \multicolumn{1}{c|}{\scriptsize 1.33} & \multicolumn{1}{c|}{\scriptsize \textbf{0.59*}} & \multicolumn{1}{c|}{\scriptsize 3.7} & \multicolumn{1}{c|}{\scriptsize 2.25} & \multicolumn{1}{c|}{\scriptsize 1.25}&\multicolumn{1}{c|}{\scriptsize \textbf{0.79}} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 3}& \multicolumn{1}{c|}{\scriptsize 1.03} & \multicolumn{1}{c|}{\scriptsize \textbf{0.8}} & \multicolumn{1}{c|}{\scriptsize 2.36} & \multicolumn{1}{c|}{\scriptsize 1.7} & \multicolumn{1}{c|}{\scriptsize \textbf{0.62*}} & \multicolumn{1}{c|}{\scriptsize 1.31} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 4}& \multicolumn{1}{c|}{\scriptsize 1.68} & \multicolumn{1}{c|}{\scriptsize \textbf{0.59}} & \multicolumn{1}{c|}{\scriptsize 2.72} & \multicolumn{1}{c|}{\scriptsize 2.41} & \multicolumn{1}{c|}{\scriptsize 1.05}& \multicolumn{1}{c|}{\scriptsize \textbf{0.5}} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 5}& \multicolumn{1}{c|}{\scriptsize 0.72} & \multicolumn{1}{c|}{\scriptsize \textbf{0.6*}} & \multicolumn{1}{c|}{\scriptsize 2.06} & \multicolumn{1}{c|}{\scriptsize 1.43} & \multicolumn{1}{c|}{\scriptsize \textbf{0.62}}&\multicolumn{1}{c|}{\scriptsize 0.87} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 6}& \multicolumn{1}{c|}{\scriptsize 1.31} & \multicolumn{1}{c|}{\scriptsize \textbf{0.74}} & \multicolumn{1}{c|}{\scriptsize 2.71} & \multicolumn{1}{c|}{\scriptsize 1.87} & \multicolumn{1}{c|}{\scriptsize \textbf{0.68*}}&\multicolumn{1}{c|}{\scriptsize 1.73} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 7}& \multicolumn{1}{c|}{\scriptsize 1.45} & \multicolumn{1}{c|}{\scriptsize \textbf{1.01}} & \multicolumn{1}{c|}{\scriptsize 2.83} & \multicolumn{1}{c|}{\scriptsize 2.22} & \multicolumn{1}{c|}{\scriptsize \textbf{0.84*}} & \multicolumn{1}{c|}{\scriptsize 1.38} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 8}& \multicolumn{1}{c|}{\scriptsize 1.27} & \multicolumn{1}{c|}{\scriptsize \textbf{0.75}} & \multicolumn{1}{c|}{\scriptsize 2.74} & \multicolumn{1}{c|}{\scriptsize 1.97} & \multicolumn{1}{c|}{\scriptsize \textbf{0.61*}}& \multicolumn{1}{c|}{\scriptsize 1.63} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 9}& \multicolumn{1}{c|}{\scriptsize 1.45} & \multicolumn{1}{c|}{\scriptsize \textbf{1.1*}} & \multicolumn{1}{c|}{\scriptsize 2.76} & \multicolumn{1}{c|}{\scriptsize 2.18} & \multicolumn{1}{c|}{\scriptsize \textbf{1.16}} & \multicolumn{1}{c|}{\scriptsize 1.77} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 10}& \multicolumn{1}{c|}{\scriptsize 1.19} & \multicolumn{1}{c|}{\scriptsize \textbf{0.77}} & \multicolumn{1}{c|}{\scriptsize 2.4} & \multicolumn{1}{c|}{\scriptsize 1.67} & \multicolumn{1}{c|}{\scriptsize \textbf{0.68*}}& \multicolumn{1}{c|}{\scriptsize 1.26} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 11}& \multicolumn{1}{c|}{\scriptsize 1.61} & \multicolumn{1}{c|}{\scriptsize \textbf{1.46}} & \multicolumn{1}{c|}{\scriptsize 2.7} & \multicolumn{1}{c|}{\scriptsize 2.32} & \multicolumn{1}{c|}{\scriptsize \textbf{1.36*}}& \multicolumn{1}{c|}{\scriptsize 2.03} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 12}& \multicolumn{1}{c|}{\scriptsize 0.77} & \multicolumn{1}{c|}{\scriptsize \textbf{0.62}} & \multicolumn{1}{c|}{\scriptsize 2.15} & \multicolumn{1}{c|}{\scriptsize 1.18} & \multicolumn{1}{c|}{\scriptsize \textbf{0.38*}}& \multicolumn{1}{c|}{\scriptsize 0.71} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 13}& \multicolumn{1}{c|}{\scriptsize 0.87} & \multicolumn{1}{c|}{\scriptsize \textbf{0.49}} & \multicolumn{1}{c|}{\scriptsize 2.19} & \multicolumn{1}{c|}{\scriptsize 1.39} & \multicolumn{1}{c|}{\scriptsize \textbf{0.48*}}& \multicolumn{1}{c|}{\scriptsize 1.1} \\
%\multicolumn{1}{|l|}{\scriptsize All Of Me 14}& \multicolumn{1}{c|}{\scriptsize 1.15} & \multicolumn{1}{c|}{\scriptsize \textbf{0.8*}} & \multicolumn{1}{c|}{\scriptsize 2.57} & \multicolumn{1}{c|}{\scriptsize 1.97} & \multicolumn{1}{c|}{\scriptsize \textbf{0.9}}& \multicolumn{1}{c|}{\scriptsize 1.33} \\
%\hline
%{\scriptsize \textbf{Average Jazz Impro.}} & \multicolumn{1}{c|}{\scriptsize ${1.23\pm0.29}$} & \multicolumn{1}{c|}{\scriptsize $\mathbf{0.79\pm0.25}$\textbf{*}} & \multicolumn{1}{c|}{\scriptsize ${2.61\pm0.4}$} & \multicolumn{1}{c|}{\scriptsize ${1.88\pm0.38}$} & \multicolumn{1}{c|}{\scriptsize $\mathbf{0.8\pm0.3}$} & \multicolumn{1}{c|}{\scriptsize ${1.29\pm0.45}$} \\
%\hline
%\multicolumn{1}{|l|}{\scriptsize Don't Stop till You Get Enough}&\multicolumn{1}{c|}{\scriptsize 0.88}&\multicolumn{1}{c|}{\scriptsize \textbf{0.44*}} & \multicolumn{1}{c|}{\scriptsize 2.23} & \multicolumn{1}{c|}{\scriptsize 1.33} & \multicolumn{1}{c|}{\scriptsize \textbf{0.46}} & \multicolumn{1}{c|}{\scriptsize 0.7} \\
%\multicolumn{1}{|l|}{\scriptsize Sir Duke}& \multicolumn{1}{c|}{\scriptsize 1.09}&\multicolumn{1}{c|}{\scriptsize \textbf{0.47*}}&\multicolumn{1}{c|}{\scriptsize 2.52} & \multicolumn{1}{c|}{\scriptsize 1.59} & \multicolumn{1}{c|}{\scriptsize \textbf{0.55}} & \multicolumn{1}{c|}{\scriptsize 0.71} \\
%\multicolumn{1}{|l|}{\scriptsize Let's Dance}& \multicolumn{1}{c|}{\scriptsize 0.96}&\multicolumn{1}{c|}{\scriptsize \textbf{0.61}}&\multicolumn{1}{c|}{\scriptsize 2.29} & \multicolumn{1}{c|}{\scriptsize 1.63} & \multicolumn{1}{c|}{\scriptsize \textbf{0.6*}} & \multicolumn{1}{c|}{\scriptsize 1.03} \\
%\multicolumn{1}{|l|}{\scriptsize Like a Rolling Stone}&\multicolumn{1}{c|}{\scriptsize 1.22}&\multicolumn{1}{c|}{\scriptsize \textbf{0.81*}}&\multicolumn{1}{c|}{\scriptsize 2.73} & \multicolumn{1}{c|}{\scriptsize 2.02} & \multicolumn{1}{c|}{\scriptsize \textbf{0.88}}& \multicolumn{1}{c|}{\scriptsize 1.45} \\
%\multicolumn{1}{|l|}{\scriptsize Sunshine of Your Love}&\multicolumn{1}{c|}{\scriptsize 1.18}&\multicolumn{1}{c|}{\scriptsize \textbf{0.92}}&\multicolumn{1}{c|}{\scriptsize 2.33} & \multicolumn{1}{c|}{\scriptsize 1.7} & \multicolumn{1}{c|}{\scriptsize \textbf{0.73*}} & \multicolumn{1}{c|}{\scriptsize 1.46} \\
%\multicolumn{1}{|l|}{\scriptsize You Really Got Me}&\multicolumn{1}{c|}{\scriptsize 0.32}&\multicolumn{1}{c|}{\scriptsize \textbf{0.27}}&\multicolumn{1}{c|}{\scriptsize 1.1} & \multicolumn{1}{c|}{\scriptsize 0.66} & \multicolumn{1}{c|}{\scriptsize \textbf{0.24}}  & \multicolumn{1}{c|}{\scriptsize 0.25} \\
%\hline
%\multicolumn{1}{|l|}{\scriptsize \textbf{Average Rock}}&\scriptsize{$0.94\pm0.33$}&\scriptsize{$\mathbf{0.59\pm0.24}$}&\scriptsize{$2.20\pm0.57$}&\scriptsize{$1.49\pm0.46$}&\scriptsize{$\mathbf{0.58\pm0.22}\textbf{*}$}&\scriptsize{$0.93\pm0.47$} \\
%\hline \hline
%Average  & \multicolumn{1}{c|}{\scriptsize ${1.05\pm0.28}$}&\multicolumn{1}{c|}{\scriptsize ${0.71\pm0.23}$}&\multicolumn{1}{c|}{\scriptsize ${2.24\pm0.4}$} & \multicolumn{1}{c|}{\scriptsize ${1.57\pm0.37}$} & \multicolumn{1}{c|}{\scriptsize ${0.66\pm0.23}$} & \multicolumn{1}{c|}{\scriptsize ${1.16\pm0.43}$} \\
\hline\hline
\end{tabular}
%\end{singlespace}
\caption{\label{tab:music} Music MIDI sequences. Average log-loss (equivalent to bits/symbol) of the VMM algorithms over the music corpus.
        The table is partitioned into four sections: classical pieces, jazz pieces, 14 improvisations of the same
        jazz piece ``All of me'' and rock pieces.
        Each number is an average loss corresponding to several MIDI channels (see Appendix~\ref{app:music}).
        For each sequence (row) the winner is starred and appears in boldface. The
        runner-up appears in boldface.}
\end{table}

The prediction results for the protein corpus appear in Table~\ref{tab:protein}.
Here $\ppmc$ is the overall winner and $\dctw$ is the runner-up. The
difference between them and the other algorithms is not very large,
with the exception of the $\pst$ algorithm, which suffered a significantly larger average
loss.\footnote{The failure of $\pst$ in this setting could be a result
of an inadequate set of possible values for its hyper-parameters; see
Appendix~\ref{app:hyperparam} for details on the choices made.}

The striking observation, however, is that
none of the algorithms could beat a trivial prediction
based on a (zero-order) ``background'' distribution
of amino acid frequencies as
measured over a large database of proteins. The entropy of this
background distribution is 4.19. Moreover, the entropy of a yet more trivial
predictor based on the uniform distribution over an alphabet of size 20 is
$4.32 \approx \log_2(20)$. Thus, not only could the algorithms not
outperform these two trivial predictors, they generated predictions
that are sometimes considerably worse.

These results indicate that the first half of a protein
  sequence does not contain predictive information about its second half.
  This is consistent with the general perception that protein chains
  are not repetitive \footnote{This is not always true. It is not
    unusual to observe similar patterns (though not identical) within
    the same protein.  However, this phenomenon is observed for a
    relatively small number of proteins.}.  Rather, usually they are
  composed of several different elements called domains, each one with
  own specific function and unique source distribution
  \cite{rose79,lesk:rose,hol:san94}.  These unique distributions are
  usually more statistically different from each other (in terms of the
  KL-divergence) than from the background or uniform distribution.
  Therefore, a model that is trained on the first half of a protein is
  expected to perform worse than the trivial predictor - which explains
  the slight increase in the average code length.  A similar finding
  was observed by \citeA{bejerano01variations} where models that were
  trained over specific protein families coded unrelated non-member
  proteins using an average code length that was higher than the
  entropy of the background distribution.  This is also supported by
  other papers that suggest that protein sequences are incompressible
  (e.g. \citeR{nevillmanning99protein}). %%ZZZ




\begin{table}[htb!]
\begin{tabular}{|l|c|c|c|c|c|c|}
\hline\hline
Sequences Class & $\bctw$ & $\dctw$ & $\lz$ & $\lzms$ & $\ppmc$ & $\pst$ \\
\hline\hline
A (1310)&\scriptsize{$4.85\pm0.003$}&\scriptsize{$\mathbf{4.52\pm0.007}$}&\scriptsize{$4.80\pm0.005$}&\scriptsize{$4.79\pm0.007$}&\scriptsize{$\mathbf{4.45\pm0.005*}$}&\scriptsize{$8.07\pm0.01$}\\
B (1604)&\scriptsize{$4.87\pm0.003$}&\scriptsize{$\mathbf{4.55\pm0.006}$}&\scriptsize{$4.83\pm0.005$}&\scriptsize{$4.85\pm0.007$}&\scriptsize{$\mathbf{4.47\pm0.005*}$}&\scriptsize{$8.06\pm0.009$}\\
C (3991)&\scriptsize{ $4.85\pm0.002$}&\scriptsize{$\mathbf{4.49\pm0.003}$}&\scriptsize{$4.89\pm0.003$}&\scriptsize{$4.92\pm0.004$}&\scriptsize{$\mathbf{4.43\pm0.002*}$}&\scriptsize{$8.05\pm0.005$}\\
D (2325)&\scriptsize{ $4.85\pm0.003$}&\scriptsize{$\mathbf{4.65\pm0.006}$}&\scriptsize{$4.91\pm0.004$}&\scriptsize{$4.98\pm0.005$}&\scriptsize{$\mathbf{4.54\pm0.004*}$}&\scriptsize{$8.13\pm0.008$}\\
E (402)& \scriptsize{$4.88\pm0.005$}&\scriptsize{$\mathbf{4.36\pm0.006}$}&\scriptsize{$4.78\pm0.009$}&\scriptsize{$4.83\pm0.008$}&\scriptsize{$\mathbf{4.33\pm0.004*}$}&\scriptsize{$7.92\pm0.01$}\\
F (157)& \scriptsize{$4.94\pm0.015$}&\scriptsize{$\mathbf{4.37\pm0.017}$}&\scriptsize{$4.71\pm0.014$}&\scriptsize{$4.78\pm0.017$}&\scriptsize{$\mathbf{4.34\pm0.013*}$}&\scriptsize{$8.00\pm0.023$}\\
G (16)& \scriptsize{$\mathbf{4.79\pm0.018*}$}&\scriptsize{$5.00\pm0.052$}&\scriptsize{$5.08\pm0.075$}&\scriptsize{$5.03\pm0.105$}&\scriptsize{$\mathbf{4.82\pm0.047}$}&\scriptsize{$8.45\pm0.13$}\\
\hline\hline
Average$\pm$\scriptsize{SEM} & \scriptsize{$4.86\pm0.007$} & \scriptsize{$\mathbf{4.56\pm0.014}$} & \scriptsize{$4.85\pm0.16$} & \scriptsize{$4.88\pm0.022$} & \scriptsize{$\mathbf{4.48\pm0.011*}$} & \scriptsize{$8.09\pm0.028$} \\
\hline
\end{tabular}

\caption{ \label{tab:protein} Protein sequences average prediction
loss. A trivial distribution assignment based on a ``background''
amino-acid frequency (measured over a large protein database) has an entropy of 4.19.
Note also that maximal entropy of any distribution is bounded above
by the entropy of the uniform distribution $4.32 \approx \log_2(20)$.
For each sequence (row) the winner is
starred and appears in boldface. The runner-up appears in boldface. The last row represents the averages and standard error of the means.}
\end{table}

\section{Protein Classification}
\label{sec:protein-classification}

For protein sequences, a more natural setup than the sequence
  prediction setting is the classification setting. Biologists
  classify proteins into relational sets such as `families',
  `superfamilies', `fold families' and `classes'; these terms were coined by
  \citeA{dayhoff76} and \citeA{lev:cho}. Being able to classify a new protein in
  its proper group can help to elucidate relationships between novel
  genes and existing proteins and characterize unknown genes.

Prediction algorithms can be used for classification using a winner-takes-all (WTA) approach.
Consider a training set of sequences belonging to $k$ classes  $C_1,\ldots,C_k$.
For each class $C_i$ we train a sequence predictor $\Phat_i$. Given a test sequence
$x$ we classify it as class $c = \arg\max_i \Phat_i(x)$.

We tested the WTA classifiers derived from the above VMM
algorithms over several large protein classification problems.
These problems consider the same protein sequences mentioned in
the above prediction experiment. For classification we used the
partition into subsets given in the SCOP database. Specifically,
the SCOP database \cite{murzin95scop} classifies proteins into a
hierarchy of `families', `superfamilies', `folds' and `classes'
where each
  `class' is composed of several `folds', each `fold' is composed of several
  `superfamilies' and each `superfamily' is composed of several `families'. This
classification was done manually based on both sequence and
structural similarities,
resulting in seven major `classes' (at the top level), 765
`folds',\footnote{
Note the difference between the SCOP 'classes' and the term class we use in
classification problems; similarly, note the difference between
the SCOP `folds' (that are subsets of the SCOP `classes') from the folds
we use in cross-validation. Throughout our discussion, the biological
`classes' and `folds' are cited.}
 1231 `superfamilies' and 2163 `families' (release 1.63).

%  \rnote{Each protein in
%this database is designated with a letter and 3 numbers, the first is
%the class, and the numbers correspond to the fold, superfamily and
%family level.}

%Each protein
%in this database is designated with a letter and 3 numbers, the
%first is the class, and the numbers correspond to the fold
%superfamily and family level. Our task was to recover
%one level of this hierarchy, between folds that belong to the same
%class (e.g. detecting the relationship between families a.1.*.*
%and a.2.*.* where * resemble any number).
%\rnote{ OLD :
%Overall we considered seven classification probelems (designated
%by the letters 'A'-'G' in Table~\ref{tab:protein_classification},
%and also in Tables~\ref{tab:protein} and~\ref{tab:protein2}). The
%number of classes in these problems varies between 12-111 (with
%average of 58 classes). }


The seven major SCOP classes are quite distinct and can be easily
distinguished \shortcite{kumarevel,jin}.
Here we focused on the next level in this
hierarchy, the `fold' level.
Our task was to classify proteins, that
belong to the same `class', into their unique `fold'. Since there are seven `classes'
in the SCOP database, we have seven independent classification problems.
The number of `folds' (i.e., machine learning classes) in each `class'
appear in Table~\ref{tab:protein_classification}.
For example, the protein `class' D contains 111 `folds'. The classification problem
corresponding to D is, therefore, a multi-class problem with 111 (machine learning)
classes.
Consider one (of the seven) classification problems.
For each `fold', a statistical model
was trained from a training subset of sequences that belong to that `fold'.
Thus, the number of models we learn is the number of `folds' (111 in the D
'Class'). The resulting classifier is a WTA combination of all these
models.
The test set for this classifier contains all the proteins
from the same SCOP `class'
that do not appear in any training set.

%For
%example, a subset of the sequences that are labeled $a.1.*.*$ (where *
%can be any number) was used to train one model. This model was tested
%on all sequences that belong to the class $a$ (i.e.  sequences that
%are labeled $a.*.*.*$). The probability estimates were compared to the
%probability estimates of all other models for all other folds $a.*$
%that belong to the class $a$, and each protein was classified using
%the WTA approach.

Of the 765 `folds', we considered only `folds' with at least 10 members.
VMM models were trained (one for each `fold') and tested.
The test results are grouped and averaged per SCOP `class'. The number of `folds'
in these classes varies between 12-111 (with an average of 58 'folds').


%\Rnote{
%The classification experiment ``protocol" is straightforward, using five-fold CV.
%In each classification problem consisting of $k$ classes, $C_1, \ldots, C_k$,
%we randomly and uniformly partitioned each class into five (roughly) equal sized subsets.
%We then constructed five folds each consisting of a training:test pair with proportions
%$\frac{4}{5}:\frac{1}{5}$ respectively.
%For each fold (of the five folds) we trained $k$ applications of the tested VMM algorithm
%using the training set, resulting in $k$ probability estimates $\Phat_i$, one for each class.
%Using the WTA approach we classified each protein in the test set.}
As before, the experiment was repeated five times using  five-fold CV.
We measured the performance using the average over the zero-one loss (zero loss for a correct
classification). Within each fold we fine-tuned the hyper-parameters of the algorithm
using
the same ``internal'' five-fold cross validation methodology as described
in Section~\ref{sec:experiments}.

In this setup we used a slightly different $\pst$ variant
(denoted as $\pst*$) based
on \cite{bejerano01variations}.\footnote{The results of the original $\pst$
algorithm were poor (probably due to an inadequate set of
values for the hyper-parameters).
Recall that the $\pst*$ (and all other algorithms)
hyper-parameter values were chosen before starting the
experiments, following the description given in Section~\ref{sec:experiments}.}
The $\pst*$ variant is basically a standard $\pst$ with the following two modifications:
(i) A context is chosen to be a candidate according to the number
of times it appears in different `fold' sequences;
%($N_{min}$ replaces $P_{min}$);
(ii) A context $s$ is added to the tree if some symbol
appears after $s$ at least some predefined number
of times.
%($hits$ replaces $\gamma_{min}$).

We present the classification-experiment results in
Table~\ref{tab:protein_classification}. The consistent winner here
is the $\lzms$ algorithm, which came first in all of the
classification problems, differing substantially from the
runner-ups, $\dctw$ and $\ppmc$.

In general, all the VMM algorithms' classifications had a good average success
rate ($1 -$ error) that ranges between
$76\%$ (for $\pst*$) to $86\%$ (for $\lzms$).
The
  latter result is quite surprising, considering that the class definition is
  based on structural properties that are not easily recognizable from
  the sequence.  In fact, existing methods of sequence comparison
  usually fail to identify relationships between sequences that belong
  to different superfamilies within the same fold. The success rate of
  the $\lzms$ algorithm in this task suggests that the algorithm might
  be very effective in other protein classification tasks.

\begin{table}[htb!]
%\begin{longtable}{|c|c|c|c|c|c|c|c|}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline\hline
% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
Protein & \# `folds' & $\bctw$ & $\dctw$ & $\lz$ & $\lzms$ & $\ppmc$ & $\pst*$ \\
`Class'   &  & & & & & & \\
\hline \hline
%{\sffamily  Protein}&{\sffamily  Number of}&{\sffamily binary}&{\sffamily decomposed}&{\sffamily LZ78}&{\sffamily LZms}&{\sffamily  PPMC}&{\sffamily  PST}\\
%{\sffamily Class}&{\sffamily Subfamilies}&{\sffamily CTW}&{\sffamily CTW}&  &  & &\\
%\hline\hline
%\endfirsthead
%\hline\hline
%% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%{\sffamily  Protein}&   {\sffamily  Number of}&{\sffamily binary}
%& {\sffamily decomposed} & {\sffamily LZ78} & {\sffamily LZms} &
%{\sffamily  PPMC} & {\sffamily  PST}\\
%{\sffamily Class}&{\sffamily Subfamilies}&  {\sffamily CTW}  &  {\sffamily CTW}&  &  & &\\
%\hline\hline
%\endhead
%\hline
%\multicolumn{8}{r}%
%{\small \itshape continued on the next page}
%\endfoot
%
%\multicolumn{8}{r}%
%{\small \itshape }
%\endlastfoot
%starthere
   {\em {A} }&\scriptsize{86}&\scriptsize{$0.26\pm0.035$}&\scriptsize{$0.19\pm0.031$}&\scriptsize{$0.28\pm0.035$}&\scriptsize{$\mathbf{0.16\pm0.031}$}&\scriptsize{$0.21\pm0.031$}&\scriptsize{$0.22\pm0.009$}\\
   { {B} }&\scriptsize{75}&\scriptsize{$0.23\pm0.031$}&\scriptsize{$0.17\pm0.031$}&\scriptsize{$0.24\pm0.040$}&\scriptsize{$\mathbf{0.14\pm0.031}$}&\scriptsize{$0.18\pm0.035$}&-\\
   { {C} }&\scriptsize{78}&\scriptsize{$0.27\pm0.031$}&\scriptsize{$0.22\pm0.031$}&\scriptsize{$0.27\pm0.040$}&\scriptsize{$\mathbf{0.17\pm0.035}$}&\scriptsize{$0.21\pm0.031$}&-\\
   { {D} }&\scriptsize{111}&\scriptsize{$0.24\pm0.040$}&\scriptsize{$0.19\pm0.031$}&\scriptsize{$0.26\pm0.040$}&\scriptsize{$\mathbf{0.16\pm0.031}$}&\scriptsize{$0.18\pm0.035$}&\scriptsize{$0.20\pm0.03$}\\
   { {E} }&\scriptsize{17}&\scriptsize{$0.12\pm0.031$}&\scriptsize{$0.09\pm0.031$}&\scriptsize{$0.1\pm0.044$}&\scriptsize{$\mathbf{0.05\pm0.017}$}&\scriptsize{$0.08\pm0.017$}&\scriptsize{$0.16\pm0.076$}\\
   { {F} }&\scriptsize{12}&\scriptsize{$0.26\pm0.031$}&\scriptsize{$0.21\pm0.044$}&\scriptsize{$0.19\pm0.031$}&\scriptsize{$\mathbf{0.17\pm0.03}$}&\scriptsize{$0.24\pm0.067$}&\scriptsize{$0.24\pm0.062$}\\
   { {G}}&\scriptsize{29}&\scriptsize{$0.33\pm0.044$}&\scriptsize{$0.25\pm0.035$}&\scriptsize{$0.31\pm0.05$}&\scriptsize{$\mathbf{0.16\pm0.017}$}&\scriptsize{$0.23\pm0.035$}&\scriptsize{$0.36\pm0.044$}\\[1Pt]
    \hline \hline
   { {Average}} &&\scriptsize{$0.24$}&\scriptsize{$0.18$}&\scriptsize{$0.23$}&\scriptsize{$\mathbf{0.14}$}&\scriptsize{$0.19$}&\scriptsize{$0.24$}\\
   { {W. Average}} &&\scriptsize{$0.25$}&\scriptsize{$0.19$}&\scriptsize{$0.25$}&\scriptsize{$\mathbf{0.15}$}&\scriptsize{$0.19$}&\scriptsize{$0.28$}\\
   \hline
%\end{longtable}
\end{tabular}
\end{center}
   \caption{Protein corpus results -- classification error rate$\pm$SEM.
            five-fold cross validation results. Best results appear in
            boldface. W. Average stands for ``weighted average''
            where the weights are
            the relative sizes of the protein classes.}
 \label{tab:protein_classification}
\end{table}

The success of the algorithms in the classification setup contrasts with their poor
protein prediction rates (given in Table~\ref{tab:protein}).
To investigate this phenomenon, we conducted another protein prediction experiment based
on the classification setup. In each fold in this experiment (among the five-CV),
a predictor $\Phat_i$ was trained using the
concatenation of all training sequences in class $C_i$ and was tested against each individual
sequence in the test of class $C_i$.
The results of this prediction experiment are given in Table~\ref{tab:protein2}.
Here we can see that all of the algorithms yield
significantly smaller losses than the loss of the
trivial protein ``background'' distribution.
Here again, $\ppm$ and $\dctw$ are favorites with significant statistical difference between them.



\begin{table}
\begin{tabular}{|l|c|c|c|c|c|c|}
\hline\hline
\multicolumn{1}{|c|}{Sequences}  & $\bctw$ & $\dctw$ & $\lz$ & $\lzms$ & $\ppmc$ &  $\pst*$ \\
\multicolumn{1}{|c|}{Class}&&&&&&\\
\hline\hline
\multicolumn{1}{|c|}{A} &\scriptsize{$2.74\pm0.043$}&\scriptsize{$\mathbf{1.95\pm0.033*}$}&\scriptsize{$3.94\pm0.015$}&\scriptsize{$ 2.29\pm0.034$}&\scriptsize{$\mathbf{1.96\pm 0.036}$}&\scriptsize{$2.97\pm0.049$}\\
\multicolumn{1}{|c|}{B} &\scriptsize{$2.57\pm0.033$}&\scriptsize{$\mathbf{2.14\pm0.024}$}&\scriptsize{$3.76\pm0.013$}&\scriptsize{$2.18\pm0.026$}&\scriptsize{$\mathbf{1.92\pm0.028*}$}& - \\
\multicolumn{1}{|c|}{C} &\scriptsize{$2.63\pm0.036$}&\scriptsize{$\mathbf{2.07\pm0.028}$}&\scriptsize{$4.10\pm0.009$}&\scriptsize{$2.30\pm0.031$}&\scriptsize{$\mathbf{1.93\pm0.030*}$}& - \\
\multicolumn{1}{|c|}{D} &\scriptsize{$2.59\pm0.038$}&\scriptsize{$\mathbf{1.59\pm0.032*}$}&\scriptsize{$3.65\pm0.021$}&\scriptsize{$2.15\pm0.031$}&\scriptsize{$\mathbf{1.83\pm0.031}$}&\scriptsize{$2.64\pm0.037$}\\
\multicolumn{1}{|c|}{E} &\scriptsize{$1.52\pm0.105$}&\scriptsize{$\mathbf{1.24\pm0.081}$}&\scriptsize{$3.47\pm0.052$}&\scriptsize{$1.49\pm0.075$}&\scriptsize{$\mathbf{1.16\pm0.081*}$}&\scriptsize{$2.20\pm0.105$}\\
\multicolumn{1}{|c|}{F} &\scriptsize{$2.99\pm0.155$}&\scriptsize{$\mathbf{2.34\pm0.121}$}&\scriptsize{$3.92\pm0.054$}&\scriptsize{$2.49\pm0.13$}&\scriptsize{$\mathbf{2.15\pm0.135*}$}&\scriptsize{$3.04\pm0.141$}\\
\multicolumn{1}{|c|}{G} &\scriptsize{$3.49\pm0.057$}&\scriptsize{$\mathbf{2.30\pm0.057*}$}&\scriptsize{$4.04\pm0.025$}&\scriptsize{$2.88\pm0.058$}&\scriptsize{$\mathbf{2.53\pm0.057}$}&\scriptsize{$3.56\pm0.051$}\\
\hline\hline
\multicolumn{1}{|c|}{Average$\pm$\scriptsize{SEM}}&\scriptsize{$2.64\pm0.066$}&\scriptsize{$\mathbf{1.94\pm0.053}$}&\scriptsize{$3.84\pm0.027$}&\scriptsize{$2.25\pm0.055$}&\scriptsize{$\mathbf{1.92\pm0.056*}$}&\scriptsize{$2.88\pm0.076$}\\
 \hline
\end{tabular}

\caption{ \label{tab:protein2} Protein prediction based on the
classification setup. The classes B and C results of $\pst$ are
missing. We terminated these runs after a week of computation.
Observe the difference between these and the results of
Table~\ref{tab:protein}. Here all of the algorithms beat the two
trivial predictors (``background'' frequency and the uniform
distribution) mentioned in caption of Table~\ref{tab:protein}.}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Related work}
\label{sec:related}
In this section we briefly discuss some results that are related to the present work.
We restrict ourselves to comparative studies that include algorithms we consider here
and to discussions of some recent extensions of these
algorithms. We also discuss some results concerning compression and prediction
of proteins.

The $\ppm$ idea and its overwhelming success in benchmark tests has
attracted considerable attention and numerous $\ppm$ variants have been
proposed and studied. $\ppmd$ \cite{howard_phd} is very similar
to to $\ppmc$, with a slight modification of the escape mechanism;
see Section~\ref{sec:ppm}. The $\ppm^*$ variant eliminates the
need to specify a maximal order \cite{cleary97unbounded}. For
predicting the next symbol's probability, $\ppm^*$ uses
``deterministic'' contexts, contexts that give probability one to
some symbols. If no such context exists, then $\ppm^*$ use the
longest possible context (i.e., the original $\ppm$ strategy). One
of the most successful $\ppm$ variants over the Calgary Corpus is
the $\ppmz$ variant of \citeA{bloom99Solving}. The $\ppmz$ variant
introduces two improvements to the $\ppm$ algorithm: (i)
estimating the best model order, for each encoded symbol; (ii)
adding a dynamic escape estimation for different contexts.
To date, the most successful $\ppm$ variant is the `complicated
PPM with information-inheritance' ($\ppmII$) of
\citeA{shkarin02one}, which achieves a compression rate of 2.041.
Currently, this is the lowest published rate over the Calgary
Corpus. The $\ppmII$ algorithm relies on an improved escape mechanism
similar to the one used by $\ppmz$ together with a different
counting heuristic that aims to reduce the statistical sparseness
that occurs in large Markovian contexts.
%that the new idea of \emph{information-inheritance} that
%initializes new contexts' counts with their suffixes (shorter
%corresponding contexts) counts.
%scheme and uses different escape methods for different types
%of contexts. The information-inheritance (II) scheme where initializes new $\ppm$ trie node with the statistics
%of its parent node.

Traditionally, the comparison between $\ppm$ variants (and other
lossless compression algorithms) is over the Calgary Corpus. Other
corpora for lossless compression were proposed and are available.
Two examples are the Canterbury Corpus and the `Large Canterbury
Corpus' \cite{arnold97corpus} and the Silesia Compression Corpus
\cite{deorowicz03phd}, which contains significantly larger files
than both the Calgary and Canterbury corpora.\footnote{These corpora are
available at \url{http://corpus.canterbury.ac.nz/} and
\url{http://sun.iinf.polsl.gliwice.pl/~sdeor/corpus.htm},
respectively.}


\citeA{bunton97semantically} provides a (Calgary Corpus) comparison
between $\ppmc$, $\ppmd$ and $\ppm^*$ (with its `C' and `D'
versions). The average compression rates achieved by these
algorithm are: 2.417, 2.448, 2.339 and 2.374, respectively, with
a fixed order bound $D=9$ for $\ppmc$ and $\ppmd$. According to
Bloom\footnote{See \url{http://www.cbloom.com/src/ppmz.html}}, his
latest version of $\ppmz$ achieves an average rate of 2.086.
Bunton also proposes various improvements for the $\ppm$ schemes.
Her best improved $\ppm$ achieves a 2.177 rate.\footnote{At the
time (1996) this variant was probably the most successful $\ppm$
version.}

%It is interesting to note that the log-loss rates we obtain
%for some algorithms are lower than 2. For example $\ppmc$ and
%$\dctw$ achieve 0.96 and 1.33, respectively. These significantly better
%compression rates are possible due to careful training of the algorithms
%over the first half of the sequence using our cross validation methodology see
%Section~\ref{sec:experiments}. Note also that these excellent rates only
%reflect a compression of the second half of each sequence.

The general-purpose $\ppm$ scheme turns out to be rather flexible
and allows adaptations to particular domains. For example,
\citeA{nevillmanning99protein} achieve a slightly better rate than
the trivial ($\log_2(20)$) one for proteins, using a specialized variant of $\ppmd$
that uses prior amino-acids frequencies to enhance the estimation.
By combining domain knowledge into $\ppm$ using preprocessing and
$\ppm$ that predicts over dual-alphabets, \citeA{drinic02ppmexe}
develop a specialized algorithm for compressing computer
executable files (.exe). A $\ppm$ variant for compressing XML files
was proposed by \citeA{cheney01compressing}. A text-mining utilization of the $\ppm$
algorithm was tested by \shortciteA{witten99textmining} and a few text classification setups were
studied by \citeA{thaper01,teahan01using}.


Context Tree Weighting ($\ctw$), with its proven redundancy bound,
has also attracted much attention. However, unlike the $\ppm$
approach, there are not as many empirical studies of this
algorithm. A possible reason is that the original binary $\ctw$
(and straightforward extensions to larger alphabets) did not
achieve the best lossless compression results \cite{tjalkens97aContext}. The work
of Volf, which extends the binary $\ctw$ to general alphabets,
resulting in the $\dctw$ algorithm (see Section~\ref{sec:dctw}),
showed that $\ctw$ can achieve excellent compression rates. Since
then, the $\ctw$ scheme has been extended in several
directions. Perhaps
the most important extension is a modified $\ctw$
scheme that does not require the maximal order hyper-parameter ($D$).
The redundancy of this modified algorithm is bounded in a similar manner as the original
version. This more recent $\ctw$ variant is thus universal with
respect to the class of stationary and ergodic Markov sources of
finite order.

Specialized $\ctw$ variants were proposed for various domains. For
text, \citeA{aberg97textctw} proposed to replace the $\ppm$ estimator
with the KT-estimator in the $\ctw$ model. They show that this combination
of $\ppmd$ and $\ctw$ outperforms $\ppmd$.
This idea was examined by \citeA{sadakane00implementing} for both
text and biological sequences. Their results also support the observation that the combination
of a $\ppm$ predictor with the $\ctw$ model outperforms $\ppmd$ compression both
for textual data as well as for compressing DNA.

We are familiar with a number of extensions of the $\pst$ scheme.
\citeA{singer97adaptive} extends the prediction scheme for sequence
transduction and also utilizes the $\ctw$ model averaging idea.
\citeA{bejerano01variations} incorporated biological prior
knowledge into $\pst$ prediction and showed that the resulting
$\pst$-based similarity measure can outperform standard methods
such as Gapped-BLAST, and is almost as sensitive as a hidden
Markov model that is trained from a multiple alignment of the
input sequences, while being much faster. Finally,
\citeA{kermorvant02improved} propose to improve the smoothing
mechanism used in the original $\pst$ algorithm. Experiments with
a protein problem indicate that the proposed smoothing method can
help.

As mentioned earlier, there are many extensions of the $\lz$ algorithm.
See \cite{nelson96data} for more details.
It is interesting to note that Volf considered an ``ensemble'' consisting
of both $\dctw$ and $\ppm$. He shows that the resulting algorithm performs
nearly as well as the $\ppmz$ on the Calgary Corpus while beating the $\ppmz$
on the Canterbury Corpus.


Previous studies on protein classification used a variety of
methods, including generative models such as HMMs \shortcite{pfam},
PSTs \cite{bejerano01variations}, and discriminative models such
as Support Vector Machines \shortcite{ding,leslie}.
\shortciteA{jaakkola} describe a model that combines the
SVM discriminative model with a generative model (the HMM-based
Fischer kernel). These methods can be quite effective for protein
classification at the family level but they are often
expensive to train and require some manual intervention to obtain
optimal results (e.g., special input pre-processing).
Other studies used unsupervised learning
techniques, such as clustering \shortcite{protomap,cogs} and
self-organizing maps \cite{agr}.  While these methods can be
applied successfully to broader data sets, they are not as
accurate as the supervised-learning algorithms mentioned above.

Of all models, the HMM model is perhaps the most popular and
successful model for protein classification to-date \shortcite{park98}. The
specific class of HMMs that are used to model protein families
(bio-HMM) has a special architecture that resembles the one used in
speech-recognition. These models are first-order Markov models.  The
methods tested in this paper belong to the general class of HMMs.
However, unlike the first-order bio-HMMs, the family of models tested
here is capable of modeling higher order sources.  Moreover, in many
cases these models obtain comparable performance to bio-HMMs
\cite<see the work of>{bejerano01variations}
 and are easier to train than bio-HMMs,
which makes them an appealing alternative.

It should be noted that the classification task that we attempted here
has a different setting than the typical setting in other studies on
protein classification. In most studies, the classification focuses on
the family level and a model is trained for each family.  Here we
focused on the structural fold-family level. This is a more difficult
task and it has been the subject of strong interest in fold prediction
tasks \cite{casp02}. Predicting the structural fold of a protein
sequence is the first substantial step toward predicting the three-dimensional
structure of a protein, which is considered one of the
most difficult problems in computational biology.

The success rate of the VMM algorithms, and specifically the $\lzms$
algorithm, is especially interesting since the sequences that make up a
fold-family belong to different protein families with different properties.
These families manifest different variations over the same structural
fold; however, detecting these similarities has been proved to be a
difficult problem \cite{profile-profile}, and existing methods that
are based on pure sequence information achieve only moderate success
in this task.

Although we have not tested bio-HMMs, we suspect that
such a model would be only moderately successful, since a single model
architecture is incapable of describing the diverge set of
protein families that make up a fold-family.
%Mixing these different model acrhitectures would lead
In contrast, the VMM models tested here are capable of transcending the
boundaries between different protein families since they do not limit
themselves to a specific architecture. These models have very few
hyper-parameters and they can be quite easily trained from the data
without further pre-processing.  Other studies that addressed a
somewhat similar problem to ours used sequence comparison algorithms
\shortcite{mcguffin} or SVMs and Neural Networks \cite{ding} reporting a
maximal accuracy of 56\%.  It is hard to compare our results to the
results reported in these studies since they used different data sets
and a different assessment methodology. However, the remarkably high
success rate of the $\lzms$ model in this task suggests that this
model can be very effective for structural-fold prediction.



%\bibitem[Sonnhammer et al. 1997]{pfam}
% Sonnhammer, E. L., Eddy, S. R., Durbin, R.
% (1997).
% Pfam: a comprehensive database of protein domain families based on
% seed alignments.
% {\em Proteins}
% {\bf 28},
% 405-420.

%\bibitem[Leslie et al. 2004]{leslie}
%Leslie CS, Eskin E, Cohen A, Weston J, Noble WS.
%(2004).
%Mismatch string kernels for discriminative protein classification.
%{\em Bioinformatics}
%{\bf 20},
%467-76.

%\bibitem[Ding \& Dubchak 2001]{ding}
%Ding CH, Dubchak I.
%(2001).
%Multi-class protein fold recognition using support vector machines and
%neural networks.
%{\em Bioinformatics} {\bf 17}, 349-58.
%% report 56% success on a similar task.

%\bibitem[Jaakkola et al. 1999]{jaakkola}
%Jaakkola T, Diekhans M, Haussler D.
%(1999).
%Using the Fisher kernel method to detect remote protein homologies.
%{\em Proc Int Conf Intell Syst Mol Biol.}
%149-58.

%\bibitem[Tatusov et al. 1997]{cogs}
% Tatusov, R. L., Eugene, V. K. \& David, J. L.
% (1997).
% A genomic perspective on protein families.
% {\em Science}
% {\bf 278},
% 631-637.

%\bibitem[Yona et al. 1999]{protomap}
% Yona, G., Linial, N. \& Linial, M.
% (1999).
% ProtoMap: Automatic classification of protein sequences, a hierarchy of
% protein families, and local maps of the protein space.
% {\em Proteins},
% {\bf 37},
% 360-378.


%\bibitem[Agrafiotis 1997]{agr}
% Agrafiotis, D. K.
% (1997).
% A new method for analyzing protein sequence relationships based on Sammon
% maps.
% {\em Protein Sci.}
% {\bf 6},
% 287-293.





%\begin{itemize}
%\item The paper
%``An empirical comparison of the performance of PPM variants on a prediction
%task with monophonic music'' (Pearce + Wiggins), investigate the performance of PPM variants
%over a range of monophonic music.
%\item A list of applications using statistical
%language modeling: speech recognition, machine translation, handwriting recognition,
%stenotype transcription, spelling correction, reactive keyboards
%\item
%The entropy of English: (1) Shannon; (2) Cover; (3) Brown + Della Pietra + Della Pietra +
%Lai + Mercer, ``An estimate of an upper bound on the entropy of English''.
%\item Bunton - extensive experimenation with PPM variants - no major differences between
%C and D
%\item The $\ctw$ extensions - Willems, \cite{sadakane00implementing}, \cite{aberg97textctw}, \cite{tjalkens97implementing}.
%\item music prediction - Witten.
%\item compression algorithms for proteins - Matsumoto.
%\item Proteins are incompressible - Witten.
%\item PST extensions: \cite{kermorvant-improved}, \cite{bejerano01variations}, \cite{eskinprotein}.
%\item PPM - PPM*, PPMZ.
%\end{itemize}

%\begin{itemize}
%\item The paper
%``An empirical comparison of the performance of PPM variants on a prediction
%task with monophonic music'' (Pearce + Wiggins), investigate the performance of PPM variants
%over a range of monophonic music.
%\item A list of applications using statistical
%language modeling: speech recognition, machine translation, handwriting recognition,
%stenotype transcription, spelling correction, reactive keyboards
%\item
%The entropy of English: (1) Shannon; (2) Cover; (3) Brown + Della Pietra + Della Pietra +
%Lai + Mercer, ``An estimate of an upper bound on the entropy of English''.
%\item Bunton - extensive experimenation with PPM variants - no major differences between
%C and D
%\item The $\ctw$ extensions - Willems, \cite{sadakane00implementing}, \cite{aberg97textctw}, \cite{tjalkens97implementing}.
%\item music prediction - Witten.
%\item compression algorithms for proteins - Matsumoto.
%\item Proteins are incompressible - Witten.
%\item PST extensions: \cite{kermorvant-improved}, \cite{bejerano01variations}, \cite{eskinprotein}.
%\item PPM - PPM*, PPMZ.
%\end{itemize}


\section{Concluding Remarks and Open Questions}

In this paper we studied the empirical performance of a
number of prominent prediction algorithms. We focused on prediction settings that
are more closely related to those required by machine learning practitioners
dealing with discrete sequences. Previous results related to these algorithms
usually focused on a standard compression setting.

While it should not be expected that one algorithm will
consistently outperform others on all tasks, our rather extensive
empirical evaluations over the three domains indicate that there
are prominent algorithms, which consistently tend to generate more
accurate predictions than the other algorithms we examine.
These algorithms are the `prediction
by partial match' ($\ppmc$) and `decomposed context tree weighting' ($\dctw$).
For classification of proteins we
observe that there is also a consistent winner. However, somewhat
surprisingly, the best predictor under the log-loss is not the
best classifier. On the contrary, the consistently best protein
classifier is based on the mediocre $\lzms$ predictor! This algorithm is a
simple modification of the well-known Lempel-Ziv-78 ($\lz$)
prediction algorithm, which can capture VMMs with large contexts.
The surprisingly good classification accuracy achieved by this algorithm
may be of independent interest to protein analysis research and clearly deserves
further investigation.

This relative success of $\lzms$ is related to the winner-takes-all classification
scheme we use. A classifier based on this approach can suffer from a degraded performance
if only one or a few of the models generated (for some of the classes)
are wrongly fitted to other classes (in which case the erroneous model is the winner).
Clearly, the superior performance
of $\lzms$ is related to its robustness in this regard and a closer inspection
of the behavior of the algorithms may be revealing.
A possible explanation of this robustness could be related to the unbounded memory
length of the $\lzms$ model. In most of the other VMM models the memory
length is a hyper-parameter. However, as discussed in Section~\ref{sec:related},
some of the
other algorithms such as $\ppm$ can be extended to work without a known bound
on the context length.

An important observation, seen in these results, is that one cannot rely on log-loss (compression)
performance when selecting a VMM algorithm for classification (using
a WTA approach). Since the classification
of sequences has not been studied as extensively
as compression and prediction,
we believe that much can be gained by focusing on specialized VMM algorithms
for classification.

We hope that our contribution will assist practitioners in selecting suitable
prediction algorithms for prediction and classification tasks and we also provide the
code of all the algorithms we considered.
Finally, we conclude by a number of open questions and directions for future research.

One of the most successful general-purpose predictors we examined
is the $\dctw$ algorithm, with its alphabet decomposition
mechanism, as suggested by \citeA{volf_phd}.
As it turns out, this mechanism is crucial for the success of the the $\ctw$
scheme. However, currently there are no redundancy bounds
(or other type of performance guarantees) for this decomposition.
It would be interesting to prove such a bound, which will also
motivate an optimality criterion for the decomposition-tree
(see Section~\ref{sec:dctw}). Note that the heuristic proposed by Volf
for generating the decomposition-tree relies on Huffman's coding, but
we are not familiar with a compelling reason for the success of this approach.

Similarly, the $\ppm$ scheme (and the $\ppmc$ variant we examined)
do not have any known bounds on its log-loss redundancy. Clearly, such
bounds could significantly contribute to understanding this algorithm
(and its variants) and may help in designing stronger versions of this scheme.

One of the main factors that influence the success of the
$\ppm$ algorithm is the details of its
escape mechanism, including the allocation of probability mass for
the `escape' event. This probability allocation is, in essence, a solution to the zero
frequency problem (also called ``missing mass'' problem). So far, there are no
formal justifications for the performance of the more successful escape
implementations.
It would be interesting to see if some of the recent results on the missing mass problem, such
as those presented by \shortciteA{OrlitskySZ03} and \citeA{McAllesterO03},
can help in devising a formal optimality measure for the $\ppm$
escape implementations.

We can view the $\ctw$ algorithm as an ensemble of numerous
VMMs. However, the weights of the various VMM models are fixed.
Various ensemble methods in machine learning such as boosting and
online expert advice
algorithms attempt to optimize the weights of the various ensemble members.
Could we achieve better performance guarantees and better empirical performance
using adaptive weight learning approaches?
\citeA{volf_phd} has some results (on combining $\lz$ and $\dctw$)
indicating that this is a promising
direction. Other possibilities would be to employ portfolio selection algorithms
to dynamically change the weights of several models, along the lines suggested by
\shortciteA{kalai99online}.

\section{Acknowledgments}
We are very grateful to Gil Bejerano, Charles Bloom and Paul Volf
who provided valuable advice and assistance.
We would also like to thank Bob Carpenter for his PPMC compression java implementation,
Moti Nisenson for his LZms java implementation and Adiel Ben Shalom for his MIDI assistance.
Finally, we thank the anonymous referees for their good comments.
The work of Ran El-Yaniv was partially
supported by the Technion V.P.R. fund for the promotion of sponsored
research and the partial support of the PASCAL
network of excellence.

%% -- Bibliography -- %
%\begin{small}
%\bibliographystyle{theapa}
%\bibliography{./bib/universalPrediction}
%\end{small}

%\newpage
\appendix


\section{Algorithm Hyper-Parameters Selection}
\label{app:hyperparam}

In our experimental protocol each algorithm optimizes its hyper-parameters during
the training phase. The best found set of parameters is then used for training (see
Section~\ref{sec:experiments} for details). This appendix specifies the possible
hyper-parameter values that were considered for each algorithm for both the
prediction and classification experiments. These values were selected (based on
commonsense) before the start of any experiment. We also provide here, for each
algorithm, the average values that were actually selected.

We present these hyper-parameter values in two tables:
Table~\ref{tab:hyperparam_textMusic} for the prediction setup,
and Table~\ref{tab:hyperparam_bio}, for the protein
classification setup.
We used two different hyper-parameter sets
for these two setups due to memory complexity issues. Specifically,
in the classification setup, as described in Section~\ref{sec:protein-classification},
the length of training sequences is significantly larger than the length of training sequences
in the prediction experiment of Section~\ref{sec:experiments}.
For example, in the protein classification, class `C' consists of 4303 sequences
from 78 different `folds' and the \emph{average} size of a sequence in class `C' is 265.
Therefore, the size of the training sequence for this class is $912,236$.
In comparison, the \emph{maximal} training sequence length in the text prediction
experiment is $\frac{785396}{2}=392,698$.
Also, recall that in each classification experiment, the number of
constructed models is the number of `folds'
(e.g., 78 in class `C'), which also increases the memory overhead.

The requirement to accommodate long training sequences (in the classification experiment) directly influences the
space used by most of the algorithms. The lengths of training sequences described above made it impossible for us to
complete the protein classification experiment using the set of feasible parameters as described in
Table~\ref{tab:hyperparam_textMusic}. Therefore, for classification we reduced the set of possible hyper-parmeter
and, as can be seen, each parameter set in Table~\ref{tab:hyperparam_bio} is a subset of the corresponding set in
Table~\ref{tab:hyperparam_textMusic}. Finally, note that this table refers to a slight variant of the standard
$\pst$, denoted by $\pst*$, which was used in the protein classification experiment (see
Section~\ref{sec:protein-classification}).

In Tables~\ref{tab:hyperparam_textMusic} and \ref{tab:hyperparam_bio} we also
present the average (overall runs) of the hyper-parameter values selected by the cross-validated
optimization. For example, in Table~\ref{tab:hyperparam_textMusic} it is
interesting to see that different values were selected for the $\lzms$ algorithm,
for different datasets.
For protein sequence predictions $\lzms$ is optimized with values that make
it almost identical to the
$\lz$ algorithm (i.e. $M=0$ and $S=0$), while on the music predictions
these parameters are optimized with significantly larger values
($M=6.12$ and $S=16.11$).
Observe that the average order selected for $\ppmc$ on `text' data is 9.25.
When originally introduced,
$\ppm$ algorithms were applied with a hyper-parameter $D=4$
(constrained by the memory available on computers at the time).
Since then, it has often been used with a somewhat larger value,
typically 5 or 6 and it was observed that
performance begins to deteriorate when $D$ is increased
beyond this. For example, see \citeA[Figure~2]{cleary97unbounded} for a drawing of
compression vs. $D$ for \emph{book1}. We observe very similar behavior when considering
the English text files alone (not shown in our table).
For example, the value selected the hyper-parameter $D$
in most text files (including \emph{book1}) is 5.

The $\pst$ hyper-parameters presented in
Tables~\ref{tab:hyperparam_textMusic} and \ref{tab:hyperparam_bio} corresponds to the
$\pst$ algorithm description in Section~\ref{sec:PST}. Specifically, the $P_{min}$ (alternatively, \texttt{hits}) hyper-parameter
is the threshold used for filtering ``suffix set'' candidates, $\alpha$ and $\gamma$ define the first condition
of the $\pst$ second stage, $r$ (alternatively, $N_{min}$) defines the second condition of
$\pst$'s second stage and $D$ defines the maximal order of the $\pst$ ``suffix set''.



%problems in the
%protein classification setup. For example in the prediction setup
%we tested $\ppm$ with maximal $D=18$ and in the classification
%setup with maximal $D=8$. The value of the maximal $\ppm$ trie
%leaves these two $D$ values imply demonstrates their difference:
%$20^{8}=25.6\cdot10^9$ for $D=8$ and $20^{18}\approx262\cdot10^21$ for $D=18$.
%Taking into considerations that each training sequence in the classification setup
%was considerably long (see Table~\ref{tab:thedatsets}) and that for each protein class
%we kept a set of predictors (up to 111), we get that the amount of memory (two Gigabyte) was
%insufficient for such $D$ values.}


%We used different feasible sets for these two setups due to
%insufficient memory problems in the protein classification setup.
%A simple arithmetic calculation emphasis the difficulty of that
%setup: we have 20000 sequences with average size of 187 and we
%have to train (up to) 111 predictors simultaneously that is
%$$\texttt{memory without data-structures} > 20000 \cdot 187 \cdot \frac{4}{5} cdot 111 \simeq
%330,000,000$$. Note that we could train one predictor at a time
%(and save the 111 factor), however this would have hurt the
%running time since we would have to train a predictor for each
%test sequence.


\begin{table}[htb!]
\begin{center}
\begin{scriptsize}
\begin{tabular}{|c|c|l|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  Algorithm & Hyper-parameter & Possible Values & \multicolumn{3}{c|}{Selected Values (Average)}\\
  \cline{4-6}
  & & & Text & Music & Protein \\
  \hline\hline
  $\ppmc$ &  $D$ &  $\{1,3,\ldots,19\}$ & 9.25 & 16.12 & 1.85\\
\hline
  $\bctw$
          & $D$ &  $\{ 8,16,32,64\}$ & 42 & 57.76 & 34.3\\
\hline
  $\dctw$
          & $D$ &  $\{ 2,4,8,16,32\}$& 7.06 & 27.97 & 17.9\\
\hline
  $\pst$
        & $P_{min}$ &  $\{0.0001, 0.001, 0.01, 0.1\}$ & 0.006& 0.0003 & 0.001\\
        & $\alpha$ &  $\{0\}$ & 0& 0 & 0\\
        & $\gamma$ &  $\{0.0001, 0.001, 0.01, 0.1\}$ & 0.0006 & 0.0005& 0.0001\\
        & $r$ &  $\{1.05\}$ & 1.05 & 1.05 & 1.05\\
        & $D$ &  $\{5, 10, 15, 20\}$ & 7.33 & 15.6 & 20\\
\hline
  $\lzms$
          & $M$ &  $\{0,2,\ldots,6,8\}$ & 2 & 6.12 & 1.06\\
          & $S$ &  $\{0,2,\ldots,16,18\}$ & 8.4 & 16.11 & 0.29\\
  \hline
\end{tabular}
\end{scriptsize}
 \caption{\label{tab:hyperparam_textMusic}Prediction setup
hyper-parameter values.}
\end{center}
\end{table}



\begin{table}[htb!]
\begin{center}
\begin{scriptsize}
\begin{tabular}{|c|c|l|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  Algorithm & Hyper-parameter & Possible Values & Selected Values (Average)\\
  \hline\hline
  $\ppmc$
         & $D$ &  $\{1, 3, 5, 7, 9\}$ & 8.5 \\
\hline
  $\bctw$
          & $D$ &  $\{8, 16, 32\}$ & 31 \\
\hline
  $\dctw$
          & $D$ & $\{4, 8\}$ & 7.5 \\
\hline
  $\pst*$
        & \texttt{hits} &  $\{2, 3, 4\}$ & 5\\
        & $\alpha$ &  $\{0\}$ & 0\\
        & $N_{min}$ &  $\{2, 3, 4, 5\}$ & 4\\
        &$\gamma$& $\{0.001\}$ & 0.001\\
        & $r$ &  $\{1.05\}$ & 1.05\\
        & $D$ &  $\{10, 15, 20\}$ & 20\\
\hline
  $\lzms$
          & $M$ &  $\{0, 2, 4, 6, 8\}$ & 5.9 \\
          & $S$ &  $\{0, 2, 4, 6, 8\}$ & 7.9 \\
  \hline
\end{tabular}
\end{scriptsize}
 \caption{\label{tab:hyperparam_bio}Protein classification setup
hyper-parameter values. Recall that in this setup we used a slight
variation of the $\pst$ algorithm. The $\pst*$ variation uses the
$N_{min}$ parameter that defines the threshold for a context
candidate context; and the $hits$ parameter defines the threshold
for a context to be added to the $\pst$ tree. }
\end{center}
\end{table}


\section{Music Representation}\label{app:music}
Our music data consists of polyphonic music pieces given as MIDI files.
A polyphonic music piece is usually represented in a MIDI
file as a collection of \emph{channels}. Each channel is typically associated with
a single musical instrument and includes instructions (called ``events'') regarding which notes to
play and how long and loud to play them. We treat each channel as an individual sequence.
For example, if a piece is played by five instruments, encoded in five MIDI channels, we generated
five individual sequences, one for each channel. Note that each entry in Table~\ref{tab:music}
is an average of all channels of the corresponding piece.

We now describe how we represent each MIDI channel.
Each note in a channel is represented as a triple:
\emph{pitch:volume:duration}. Both pitch and volume have, according to the MIDI protocol,
128 possible values. Duration is measured in milliseconds. We also include a special note,
which we call a `silence note' and allow for negative durations of this silence
note. Such negative assignments are in fact negative time intervals, which make it
possible to represent chords or other simultaneous melodic lines
within the same channel.

The sequences corresponding to a channel are the ascii
representation of the sequence of \emph{pitch:volume:duration}.
For example, the note 102:83:4022 is represented as
``102:83:4022:''.\footnote{The first ten notes of Chopin's Etude
12 Op. 10 are: ``\texttt{83:120:240:
128:0:-240: 79:120:240: 128:0:-240: 77:120:240: 128:0:-240:
74:120:240: 128:0:-240: 71:120:240: 128:0:-180:}''.}
Clearly, this representation is over an alphabet
$\Sigma=\{0, 1, \ldots, 9, : , -\}$, of size is 12.

It is important to note that our representation
preserves much of the information encoded in the original MIDI representation and, in reality,
allows one to almost exactly reconstruct the original tunes.

%music 24 hr.
%protein classification 10 days.
%text 24 hr.

\section{On the LZ-MS Hyper-Parameters}\label{app:lzms_mVSs}
This appendix provides an indication on the effectiveness of the $M$ and $S$
hyper-parameters of the $\lzms$ algorithm.  The experimental setup is identical to
the prediction setup described in Section~\ref{sec:experiments}.
Table~\ref{tab:lzms_M_VS_S} shows the log-loss results over the Calgary Corpus of
applications of the $\lzms$ algorithm: in the second column only the $M$
parameter is enabled (and $S=0$); and the third column provides the results when
only the $S$ parameter is enabled (and $M=0$). The losses in the last column correspond
to applications where both $M$ and $S$ are enabled (this column is identical to the
$\lzms$ results in Table~\ref{tab:calgary}). It is evident that the best choice of
$M$ alone is consistently better than the best choice of $S$ alone. However, the
best combination of both $M$ and $S$ is consistently better than any of these
parameters alone.


\begin{table}[htb!]
\begin{center}
\begin{scriptsize}
\begin{tabular}{|l|c|c|l|}
\hline\hline
% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
Sequence & M & S & $\lzms$\\
(length $\cdot 10^3$) & (param. value)&(param. value)&\\

\hline\hline

\multicolumn{1}{|l|}{\small $bib$(111)}  & 2.67 (2) & \textbf{2.63} (18)& \textbf{2.26*} (2,12)\\
\multicolumn{1}{|l|}{\small $book1$(785)}& \textbf{2.76} (2)& 3.03 (18)& \textbf{2.57*} (2,12)\\
\multicolumn{1}{|l|}{\small $book2$(611)}& \textbf{2.80} (2)& 3.06 (18)& \textbf{2.63*}(2,12)\\
\multicolumn{1}{|l|}{\small $geo$(102)}  & 4.48 (0)& 4.48 (0)& 4.48 (0,0)\\
\multicolumn{1}{|l|}{\small $news$(377)} & \textbf{3.19} (2)& 3.39 (12)& \textbf{3.07*} (2,4)\\
\multicolumn{1}{|l|}{\small $obj1$(22)}  & \textbf{5.75*} (2)& 6.24 (10)& \textbf{6} (2,2)\\
\multicolumn{1}{|l|}{\small $obj2$(247)} & \textbf{3.54} (2)& 3.74 (18)& \textbf{3.48*} (2,4)\\
\multicolumn{1}{|l|}{\small $paper1$(53)}& \textbf{3.54} (2)& 3.72 (14)& \textbf{3.38*} (2,12)\\
\multicolumn{1}{|l|}{\small $paper2$(82)}& \textbf{3.10} (2)& 3.23 (18)& \textbf{2.81*} (2,12)\\
\multicolumn{1}{|l|}{\small $paper3$(47)}& \textbf{3.32} (2)& 3.44 (18)&\textbf{3.09*} (2,12)\\
\multicolumn{1}{|l|}{\small $paper4$(13)}& \textbf{3.68} (2)& 3.79 (10)& \textbf{3.61*} (2,14)\\
\multicolumn{1}{|l|}{\small $paper5$(12)}& \textbf{4.26} (2)& 4.42 (18)& \textbf{4.16*} (2,8)\\
\multicolumn{1}{|l|}{\small $paper6$(38)}&\textbf{ 3.70} (2)& 3.91 (10)& \textbf{3.6*} (2,12)\\
\multicolumn{1}{|l|}{\small $pic$(513)}  & 0.79 (2)& 0.79 (4)& 0.79 (2,0)\\
\multicolumn{1}{|l|}{\small $progc$(40)} & \textbf{3.34} (2)& 3.57 (10)& \textbf{3.22*} (2,4)\\
\multicolumn{1}{|l|}{\small $progl$(72)} & \textbf{3.26} (2)& 3.50 (18)& \textbf{3.26} (2,16)\\
\multicolumn{1}{|l|}{\small $progp$(49)} & \textbf{2.75} (2)& 2.93 (18)& \textbf{2.65*} (2,18)\\
\multicolumn{1}{|l|}{\small $trans$(94)} & \textbf{2.85} (2)& 2.89 (16)& \textbf{2.61*} (4,18)\\

\hline \multicolumn{1}{|c|}{Average} & $\mathbf{3.32\pm0.06}$ & $3.48\pm0.06$ &$\mathbf{3.2\pm0.06*}$\\
\hline\hline
\end{tabular}
\end{scriptsize}
\caption{\label{tab:lzms_M_VS_S}Comparing effectiveness of the $\lzms$
hyper-parameters. Second column: $M$ is assigned the best value from the
``feasible'' set $\{ 0, 2, 4, 6, 8\}$ and $S=0$. Third column: $S$ is assigned the
best value from $\{ 0, 2,\ldots, 16, 18 \}$ and $M=0$.
Last column: the best
combination of both
 $M$ and $S$ is selected
from the two feasible sets, respectively. Best values are determined using a five-fold
CV. Each entry in this table provides the average log-loss and the corresponding
value of the hyper-parameter that was used for obtaining this log-loss. For example,
the 2.63 loss for the bib file when optimizing $S$ alone is obtained with $S=18$.}
\end{center}
\end{table}

% -- Bibliography -- %
\begin{small}
\bibliographystyle{theapa}
\bibliography{./bib/universalPrediction}
\end{small}



%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
