%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Coding of Non-Stationary Sources as a Foundation for %%
%% Detecting Change Points and Outliers in Binary Time-Series%%
%% Peter Sunehag, Wen Shao, Marcus Hutter (2012) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{article}
\usepackage{latexsym,amsmath,amsthm,amssymb}
\pagestyle{empty} \thispagestyle{empty}
\newdimen\paravsp \paravsp=1.3ex
\topmargin=-10mm \oddsidemargin=5mm \evensidemargin=5mm
\textwidth=15cm \textheight=22cm
%-------------------------------%
% Macro-Definitions %
%-------------------------------%
\newcommand{\eqn}[1]{\begin{align}#1\end{align}} % Shortcut for begin{eqnarray}
\newcommand{\eq}[1]{\begin{align*}#1\end{align*}} % Shortcut for begin{equation}
\def\,{\mskip 3mu} \def\>{\mskip 4mu plus 2mu minus 4mu} \def\;{\mskip 5mu plus 5mu} \def\!{\mskip-3mu}
\def\dispmuskip{\thinmuskip= 3mu plus 0mu minus 2mu \medmuskip= 4mu plus 2mu minus 2mu \thickmuskip=5mu plus 5mu minus 2mu}
\def\textmuskip{\thinmuskip= 0mu \medmuskip= 1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu}
\textmuskip
\newenvironment{keywords}{\centerline{\bf\small
Keywords}\begin{quote}\small}{\par\end{quote}\vskip 1ex}
\def\paradot#1{\vspace{\paravsp plus 0.5\paravsp minus 0.5\paravsp}\noindent{\bf\boldmath{#1.}}}
\def\paranodot#1{\vspace{\paravsp plus 0.5\paravsp minus 0.5\paravsp}\noindent{\bf\boldmath{#1}}}
\def\req#1{(\ref{#1})}
\def\eps{\varepsilon} % some small positive real number
\def\epstr{\epsilon} % for empty string
\def\nq{\hspace{-1em}}
\def\fr#1#2{{\textstyle{#1\over#2}}}
\def\frs#1#2{{^{#1}\!/\!_{#2}}}
\def\SetR{I\!\!R} % real numbers
\def\SetN{I\!\!N} % natural numbers
\def\SetQ{I\!\!\!Q} % rational numbers
\def\SetB{I\!\!B} % binary alphabet
\def\SetZ{Z\!\!\!Z} % integers
\def\qmbox#1{{\quad\mbox{#1}\quad}}
\def\E{{\bf E}} % Expectation]
\def\V{{\bf Var}} % Variance
\def\P{{\rm P}} % Probability
\def\lb{{\log_2}} % binary log
\def\g{\gamma} % gamma
\def\G{\Gamma} % Gamma, cylinder set
\def\t{\theta} % theta
\def\e{{\rm e}} % natural e
\def\l{{\ell}} % length of string or program
\def\M{{\cal M}}
\def\X{{\cal X}} % normally for alphabet
\def\Y{{\cal Y}} % generic set Y
\def\S{{\cal S}} % generic set S
\def\o{\omega} % omega infinite string
\def\O{\Omega} % Omega Sample space
\def\Km{K\!m}
\def\leqac{\overset{+}{\leq}} % less than up to additive constant
\def\geqac{\overset{+}{\geq}} % greater than up to additive constant
\def\eqac{\overset{+}{=}} % equal to up to additive constant
\def\leqmc{\overset{\times}{\leq}} % less than up to multiplicative constant
\def\geqmc{\overset{\times}{\geq}} % greater than up to multiplicative constant
\def\eqmc{\overset{\times}{=}} % equal to up to multiplicative constant
\def\Loss{\mbox{Loss}}
\def\u#1{{\it #1}}
\def\argmin{arg\,min} % argmin
\def\argmax{arg\,max} % argmax
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% T i t l e - P a g e %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\vskip 2mm\bf\Large\hrule height5pt \vskip 4mm
Coding of Non-Stationary Sources as a Foundation for Detecting Change Points and Outliers in Binary Time-Series
\vskip 4mm \hrule height2pt}
\author{Peter Sunehag, Wen Shao, Marcus Hutter\\Research School of Computer Science\\
Australian National University\\
ACT 0200 Australia\\
Email:~{\tt \{peter.sunehag, wen.shao, marcus.hutter\}@anu.edu.au}\\[.1in]
}
\maketitle
\begin{abstract}
An interesting scheme for estimating and adapting distributions in
real-time for non-stationary data has recently been the focus of
study for several different tasks relating to time series and data
mining, namely change point detection, outlier detection and online
compression/ sequence prediction. An appealing feature is that
unlike more sophisticated procedures, it is as fast as the related
stationary procedures which are simply modified through discounting
or windowing. The discount scheme makes older observations lose
their influence on new predictions. The authors of this article
recently used a discount scheme for introducing an adaptive version
of the Context Tree Weighting compression algorithm. The mentioned
change point and outlier detection methods rely on the changing
compression ratio of an online compression algorithm. Here we are
beginning to provide theoretical foundations for the use of these
adaptive estimation procedures that have already shown practical
promise.
\end{abstract}
\vspace{.1in}
\noindent {\em Keywords:} Non-stationary sources, time-series,
compression, detection, change point, outlier
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction} \label{sec:introduction_and_related_work} % (fold)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Data mining in time series data is an active and vast area of
research with many applications \cite{Fu11} relating to various
tasks like change detection \cite{Guralnik99,Kaw12} and outlier
detection \cite{Fawcett99,Hut09}. A unifying framework for these two
tasks were developed in \cite{Yam02,Tak06} based on online learning
in non-stationary environments using probabilistic modeling which
discounts experiences over time so as to focus on recent
observations. Recently in \cite{Kaw12}, this was further developed
into a real-time change detection method based on sequential
discounting normalized maximum likelihood coding that was applied to
security applications, in particular malware detection. In the
framework of \cite{Yam02,Tak06,Kaw12}, a scoring function based on
log loss, or in other words on arithmetic code length, was used to
decide if recent observations were anomalous. If the average score
over a number of consecutive time steps is sufficiently much higher
than before, then a change has been detected. In compression
terminology, the compressed size of those observations is higher
than those before. This basic idea is also underlying the classical
works \cite{Page55,Lorden71} on detecting change in a distribution.
Encoding a data source into a more compact representation is a long
standing problem. In this paper, we are only concerned with the task
of lossless data compression, which requires reproducing the exact
original data from the compressed encoding. A number of different
techniques for lossless data compression have been developed, for
example
\cite{ziv.j77x,ziv.j78y,cleary.j84n,cormack.g87u,burrows.m94h} to
name a few. Many data compressors make use of a concept called
arithmetic coding \cite{rissanen.j76h,rissanen.j79n}, which when
provided with a probability distribution for the next symbol can be
used for lossless compression of the data. In general, however, the
true distribution for the next symbol is unknown and must be
estimated. For stationary distributions, this estimation task is in
many situations a solved problem and arithmetic coding based on the
estimated distribution is optimal. For non-stationary distributions,
estimating the true distribution is a much harder task. The Bayesian
approaches \cite{Zacks83,Barry93} are attractive in that they are
principled and automatically optimal but they are usually much more
computationally expensive in their full form and, therefore, require
approximation, in particular if they are going to run online
\cite{Adams07, Turner09}. If one is only interested in sequence
prediction in the presence of change points and not in the change
points themselves, the Bayesian approach \cite{Willems96} offers the
possibility of using a mixture over all possible segmentations into
piece-wise stationary intervals. Instead of using segmentation for
sequence prediction, the framework by \cite{Yam02, Tak06, Kaw12}
uses sequence prediction for segmentation.
Our interest here lies in methods that are as fast as their
counterpart for the stationary case. \cite{Kaw12} achieves this
using a simple discounting scheme and a similar technique is used by
the authors of this article in \cite{Oneill12} to create a sequence
prediction and compression algorithm for non-stationary environments
based on the Context Tree Weighting (CTW) algorithm
\cite{willems.f95p}, which relies upon the Krichevsky-Trofimov (KT)
estimator. In \cite{Oneill12}, we introduce an adaptive version of
the KT estimator and use this to define the adaptive CTW algorithm.
In the case of non-stationary binary sequences, the algorithm of
\cite{Kaw12} would also naturally be based on this estimator. By
proving redundancy bounds for the adaptive KT estimator for
interesting classes of environments, we automatically get a bound
for adaptive CTW as well as a theoretical foundation for the
empirically successful change detection algorithm from \cite{Kaw12}.
An alternative approach to discounting for dealing with
non-stationarity is to use a moving window. The discounting version
can be viewed as an approximation of this approach. The windowed KT
and the resulting windowed CTW was studied in \cite{Kaw03} and
redundancy bounds was proved for stationary ($d$:th order)Markov
sources. We are instead first going to consider a source whose
Bernoulli parameter moves within an interval that is small in the
Kullback-Leibler sense and then consider drifting sources as well as
sources when the parameters (or interval of parameters) can jump
significantly but rarely.
%-------------------------------%
\paradot{Related work}
%-------------------------------%
Stationary sources have been extensively studied,
\cite{krichevsky.r81f} provides a good survey. For example,
\cite{krichevsky.r68r} provides an asymptotic lower bound for
redundancy of block to variable universal code for Bernoulli
sources; \cite{krichevsky.r70k} provides a corresponding upper
bound. \cite{trofimov.v74y} provides a finite bound for stationary
$d$:th order Markov sources which is also studied by \cite{Kaw03}.
\cite{krichevskiy.r98y} looks at asymptotic one step redundancy
bound for stationary Bernoulli sources.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Windowed Krichevsky-Trofimov Estimation for Non-Stationary Sources} \label{sec:adaptive_shemems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The KT estimator \cite{krichevsky.r81f}, in this article often
referred to as the regular KT estimator, is obtained using a
Bayesian approach by assuming a $(\frac{1}{2},\frac{1}{2})$-Beta
prior on the parameter of a Bernoulli distribution. Let $y_{1:t}$ be
a binary string containing $a$ zeros and $b$ ones. We write
$P_{kt}(a,b)$ to denote $P_{kt}(y_{1:t})$. The KT estimator can be
incrementally calculated by: $P_{kt}(a+1,b) =
\frac{a+1/2}{a+b+1}P_{kt}(a,b)$ and $P_{kt}(a,b+1) =
\frac{b+1/2}{a+b+1}P_{kt}(a,b)$ with $P_{kt}(0,0) = 1$.
% paragraph (end)
Allowing changes in the underlying sources suggests that `outdated'
histories do not necessarily provide useful and accurate information
for predicting the next bit as it does in the stationary case. The
regular KT estimator is very slow to update once many samples have
been collected, so it cannot quickly adapt to a change in the
source. Therefore, we will in this section look at a scheme where
we estimate the probability of the next bit using the KT estimator,
however, as opposed to counting the number of zeros and ones in the
entire history, we only take the latest $n$ bits into account. We
call this moving window KT or windowed KT.
%-------------------------------%
\paradot{Redundancy bounds for windowed KT}
%-------------------------------%
We are interested in one-step prediction. Assuming a stationary
Bernoulli source $\theta$, an estimation for the probability of the
next bit $x$ when given the latest $n$ bits, as a string $w$, yields
a code length $-\ln\hat{p}(x|w)$. We then take an expectation over
all possible $x$ and history $w$ to define the (expected) redundancy by
\begin{equation*}
R_\theta(n) = \sum_{|w| = n}p_\theta(w)\sum_{x\in \SetB}p_{\theta}(x)(-\ln \hat{p}(x|w)) - H(\theta)
\end{equation*}
where $H(\theta)$ is the entropy of source $\theta$. $p_\theta(w)$
and $p_\theta(x)$ are the probabilities of observing string $w$ and
$x$ under $\theta$ respectively. $\hat{p}(x|w)$ is given by the
KT-estimator
\begin{equation}
\hat{p}(x|w) = \frac{r_x(w)+1/2}{n+1}
\end{equation}
where $r_x(w)$ is the number of $x$ that appears in $w$. For a
non-stationary Bernoulli source, the one step redundancy is defined
accordingly. Suppose $x_{1:m}$ is generated by a non-stationary
Bernoulli process, with $x_i$ being sampled according to $\theta_i$,
the one step redundancy $R_{m}(n)$ at step $m$ given a window size
$n$ is
\begin{align*}
\sum_{|w|=n}p_{\theta_{m-n+1:m}}(w)\sum_{x\in\SetB}p_{\theta_{m+1}}(x)(-\ln\hat{p}(x|w))\\
-H(\theta_{m+1}).
\end{align*}
\begin{theorem}\label{thm:1}
Suppose that a binary sequence is generated by a non-stationary
Bernoulli process, with parameters $\theta_i$ where
$\theta_i=\theta^1$ when $i\leq n$ and $\theta_i=\theta^2$ when
$i>n$. We estimate the probability of the $(n+1)$:th letter by the
KT-estimator. If $\theta^1,\theta^2 \in (0,1),\ \theta^1 \leq
\theta^2$, then
\[
R(n) \leq KL(\theta^2||\theta^1) + \frac{1+o(1)}{n}\]\[ + \frac{\theta^2(3-4\theta^1)}{2n\theta^1}+\frac{(1-\theta^2)(4\theta^1-1)}{2n(1-\theta^1)}
\]
\end{theorem}
The proof technique used is largely borrowed from \cite{krichevskiy.r98y}
where the following Lemma was proven.
\begin{lemma}
\cite{krichevskiy.r98y}. Let $$b(n,k,\theta) = \left(\begin{array}{c}n \\ k\end{array}\right)\theta^k (1-\theta)^{n-k}.$$ There is a constant $C$ such that
the inequality
\[
\sum_{k=0}^{\lambda-\delta}b(n,k,\theta) < C \lambda e^{-(\delta^2/\lambda)+((\delta+1)^2/2(\lambda-\delta))}
\]
holds for $n> 2$, $0< \theta < 1$, $\lambda = np$, $1< \delta< \lambda$.
\end{lemma}
\begin{proof}[Proof for Theorem 1]
The one step redundancy we want to bound is $R(n)
=$
\begin{align}
\sum_{|w|=n}p_{\theta_{m-n+1:m}}(w)\sum_{x\in\SetB}p_{\theta_{m+1}}(x)(-\ln\hat{p}(x|w))\notag \\
-H(\theta_{m+1}) \label{eq.int.red}
\end{align}
where $\hat{p}(x|w))$ is given by the classic KT-estimator
\begin{equation}
\hat{p}(x|w) = \frac{r_x(w)+1/2}{n+1} \label{eq.int.kt}
\end{equation}
with $r_x(w)$ being the number of $x$ in string $w$. More specifically,
the redundancy for the special case of this Theorem, $R_{\theta^1,\theta^2}(n)$, can be rewritten as
\begin{equation*}
\sum_{|w|=n}p_{\theta^1}(w)\sum_{x\in\SetB}p_{\theta^2}(x)(-\ln\hat{p}(x|w))
\end{equation*}
\begin{equation}
-H(\theta^2) \label{eq.int.red2}
\end{equation}
We can rewrite $H(\theta^2)$ as
\begin{equation}
H(\theta_{R}) = \ln n - \frac{1}{n}(\lambda_{R,1}\ln\lambda_{R,1} + \lambda_{R,0}\ln\lambda_{R,0}) \label{eq.int.entr}
\end{equation}
where $\lambda_{R,x}$ is the number of expected $x$ that appear in $n$, i.e.
$\lambda_{R,x} = n\theta_{R}^x(1-\theta_{R})^{(1-x)}$. Noticing that $-\ln\hat{p}(x|w)$ in equation
(\ref{eq.int.red}) contains $\ln(n+1)$ while $H(\theta_{R})$ contains an $\ln n$ term, we Taylor expand
the function $\ln(n+1)$ at the origin and get that
\begin{equation}
\ln (n+1) < \ln n + \frac{1}{n} - \frac{1}{2n^2} \label{eq.int.taylor.lnn1}
\end{equation}
Plugging equation (\ref{eq.int.kt},\ref{eq.int.entr},\ref{eq.int.taylor.lnn1}) into
(\ref{eq.int.red2}) yields
\begin{align*}
& nR_{\theta^1,\theta^2}(n) \leq 1 + \frac{1}{n} - \frac{1}{2n^2}\\&
+ \lambda_{R,1}\ln\lambda_{R,1} -\lambda_{R,1}\sum_{k=0}^n b(n,k,\theta^1)\ln(k+\frac{1}{2})
\end{align*}
\begin{equation}
+ \lambda_{R,0}(\ln\lambda_{R,0}-\sum_{k=0}^nb(n,k,1-\theta^1)\ln(k+\frac{1}{2})) \label{eq.int.nred}
\end{equation}
where $b(n,k,\theta) = \left(\begin{array}{c}n \\ k\end{array}\right)\theta^k (1-\theta)^{n-k}$. Letting
\begin{align}
& F(n,\theta,\theta') = \notag \\& \frac{1}{2}+ \lambda\ln\lambda -\lambda\sum_{k=0}^n b(n,k,\theta')\ln(k+\frac{1}{2}) \label{eq.int.F}
\end{align}
where $\lambda = n\theta$, we can rewrite equation (\ref{eq.int.nred}) as
\begin{align}
& nR_{\theta^1,\theta^2}(n) \leq \frac{1}{n} - \frac{1}{2n^2}+ \notag \\ & F(n,\theta^2,\theta^1) + F(n,1-\theta^2,1- \theta^1) \label{eq.int.nR}
\end{align}
and to bound this we are going to show that
\begin{align*}
F(n,\theta,\theta') & \leq \frac{1}{2} + n\theta\ln\frac{\theta}{\theta'} + C''n
\end{align*}
for some constant $C''$. Next we Taylor expand $\ln(k+\frac{1}{2})$ at
$\lambda' = n\theta'$
\begin{equation}
\ln (k+\frac{1}{2}) = \ln \lambda' + \frac{k+\frac{1}{2}-\lambda'}{\lambda'} +\mathcal{R}(k) \label{eq.int.talyorlnk}
\end{equation}
The remainder $\mathcal{R}(k)$ is
\begin{equation}
\mathcal{R}(k) = - \frac{(k+\frac{1}{2}-\lambda')^2}{2\xi(k)^2}
\end{equation}
where $\xi(k)$ lies between $\lambda'$ and $k+\frac{1}{2}$. By plugging equation (\ref{eq.int.talyorlnk}) into (\ref{eq.int.F}), we get
\begin{align}
& F(n,\theta,\theta') =\\& \frac{1}{2} + n\theta\ln\frac{\theta}{\theta'} - \frac{\theta}{2\theta'} -\lambda\sum_{k=0}^{n}b(n,k,\theta')\mathcal{R}(k)
\end{align}
Take $n > \frac{1}{\theta'}+1$ and choose a natural number $\delta$ with $1< \delta < \lambda'$.
We split the summation in the last term into two parts: $0\leq k\leq \lambda-\delta$ and
$\lambda - \delta < k \leq n$. To bound the first part, we use that $\xi(k) > \frac{1}{2}$.
Putting $\delta = \lambda^{3/4}$ and using the previous lemma it follows that
$\mathcal{R}(k) \geq -2(k-\lambda+\frac{1}{2})^2$ and therefore
\begin{align*}
& -\lambda\sum_{k=0}^{\lambda-\delta}b(n,k,\theta')\mathcal{R}(k) \leq \\& 2\lambda(\lambda'+\frac{1}{2})^2\sum_{k=0}^{\lambda-\delta}b(n,k,\theta') < C' \lambda(\lambda'+\frac{1}{2})^2e^{-\sqrt{\lambda'}}
\end{align*}
for some constant $C'$. To deal with the second part, we choose $n$ large enough such that $\xi(k) >
\frac{\lambda'}{2}$ and then we have
\[
\mathcal{R}(k) \geq - \frac{2(k-\lambda'+\frac{1}{2})^2}{\lambda'^2}
\]
Therefore,
\[
-\lambda\sum_{k=\lambda-\delta}^{n}b(n,k,\theta')\mathcal{R}(k) \leq\]\[ \frac{2\lambda}{\lambda'^2}\sum_{k=0}^{n}b(n,k,\theta')(k-\lambda'+\frac{1}{2})^2
\]
Using the second central moment of binomial distribution %$m_4=3\lambda'^2(1-\theta')^2+\lambda'(1-\theta')(1-6\theta'(1-\theta'))$
$m_2=\lambda'(1-\theta')$ together with the first central moments, we have
\[
-\lambda\sum_{k=\lambda-\delta+1}^{n}b(n,k,\theta')\mathcal{R}(k) \leq \frac{2\theta(1-\theta')}{\theta'}+\frac{\theta}{n\theta'^2}
\]
Thus, we conclude that for large enough $n$
\begin{align}
& F(n,\theta,\theta') \leq \frac{1}{2} + n\theta\ln\frac{\theta}{\theta'}\\& +\frac{\theta(3-4\theta')}{2\theta'} + C' \lambda(\lambda'+\frac{1}{2})^2e^{-\sqrt{\lambda'}} \label{eq.finalF}
\end{align}
The last term decrease exponentially as $n \to \infty$ and can be replaced by $o(1)$, and write
\[
F(n,\theta,\theta') < \frac{1}{2} + n\theta\ln\frac{\theta}{\theta'} +\frac{\theta(3-4\theta')}{2\theta'} + o(1)
\]
Therefore, through Equation \ref{eq.int.nR} we have
\[
R_{\theta^1,\theta^2}(n) \leq KL(\theta^2||\theta^1) + \frac{1+o(1)}{n}\]\[ + \frac{\theta^2(3-4\theta^1)}{2n\theta^1}+\frac{(1-\theta^2)(4\theta^1-1)}{2n(1-\theta^1)}
\]
\end{proof}
If we allow the parameters to move within an interval
$[\theta_L,\theta_R]$, then Theorem \ref{thm:1} above deals with
the worst case situation, namely when $\theta_i$ is at one end point
for $m$ steps and then jumps to the other.
\begin{corollary}
Suppose $x_{1:m}$ is generated by a non-stationary Bernoulli process, with $x_i$ being sampled according to $\theta_i$. We estimate the probability of the $i$:th letter by the KT-estimator with a moving window of size $n < m$. If $i$ is such that
$m-n+1\leq i\leq m+1$$,\ \theta_i \in [\theta_L,\theta_R], \theta_L,\theta_R \in (0,1)$ and
$\theta_L \leq \theta_R$, then the redundancy for this prediction is bounded by
\begin{align*}
& R(n) \leq \frac{1+o(1)}{n} +\\& \max\{KL(\theta_L||\theta_R),KL(\theta_R||\theta_L)\} \\
& +\frac{1}{n}
\max\{\frac{\theta_R(3-4\theta_L)}{2\theta_L}+\frac{(1-\theta_R)(4\theta_L-1)}{2(1-\theta_L)},\\
&\frac{\theta_L(3-4\theta_R)}{2\theta_R}+\frac{(1-\theta_L)(4\theta_R-1)}{2(1-\theta_R)}\}
\end{align*}
\end{corollary}
\begin{example}
In the above bounds we notice that the constant factor in the
$O(1/n)$ term grows unboundedly when the parameters tend to $0$ or
$1$. This is not just a problem with the bounds but a genuine
phenomenon. Suppose that $\theta_i=1$ for $n$ time steps and then
switch to $\theta<1$. The redundancy for the next time step is then
$O(log(1+n))$. We conclude that if we want a uniform constant for
the $O(1/n)$ term we need to assume that we are a minimum distance
away from the end points.
\end{example}
\begin{corollary}\label{uniform}
Suppose $x_{1:m}$ is generated by a non-stationary Bernoulli
process, with $x_i$ being sampled according to $\theta_i\in [L,R]$
where $0 0$, we have an effective horizon of length
$\frac{1}{1-\gamma}$. The windowed estimator from the previous
section can be viewed as a hard version of this scheme.
Consider a situation where we have a stationary source
($\theta_i=\theta\ \forall i$) where we use a windowed KT with
window length $n=\frac{1}{1-\gamma}$. Compare the distribution for
the coefficient $a$ (the number of zeroes in the window) with the
distribution for the $a$ coefficient defined from discounting from
an infinite history. Both distributions are symmetric around the
same mean but the one arising from the discounting has more mass
close to the mean. Hence the discounting method will have a lower
redundancy. This is not surprising in this situation because the
discounting estimate gets to use an infinite history of observations
and if we use the full history KT we have zero redundancy. This is,
however, not the situation that we want to use discounting KT in.
Discounting KT effectively only depends on a small number of
observations. The reason we let it depend at all on things further
back is for convenience, it yields a very simple update formula
where nothing has to be stored. This is very convenient when, as in
the CTW algorithm, a KT estimator is created for every node in a
tree, which might be deep. The conclusion is that the upper bounds
for the redundancy of windowed KT should at least approximately also
hold for discounting KT. Furthermore, when the source has been close
to stationary for longer then the window length, one should expect
marginally better from the discounting algorithm. Another case when
one expect better from the discounting algorithm is for slowly
drifting sources. We will below provide a class of drifting sources
that is such that for any window, we are going to satisfy the
assumption of Corollary \ref{uniform} and one can conclude a
redundancy bound for moving window which does tell us what we should
at least expect from discounting KT.
\section{Implications for Compression and Detection of Change Points
and Outliers} We have showed that if the parameters stay within a
small interval and we have a large enough (though not too large)
window, the expected redundancy for windowed KT is small. This also
applies if instead the parameter drift is small. We argue that this
is not only true for windowed KT with a suitable window length (for
the amount of drift) but for discounting KT with an appropriate
discount factor. In this section we discuss the implications for the
motivating applications.
%-------------------------------%
\paradot{Compression}
%-------------------------------%
Since expectation is a linear operation, the total redundancy is the
sum of the per step redundancies. In the case of a stationary
source, a source constrained to a small interval or a slowly
drifting source within a larger interval our per bit redundancy
bounds are simply multiplied by the file length to get the total
redundancy. When we have a source with a small number of jumps and
otherwise only slow (geometric) drift, Theorem \ref{thm:1} tells us
that we have to add the sum of the KL-divergences times the window
length for the jumps to the estimate. Note that with a window length
$n$, the worst code length for a step is less than $\log(1+n)$. If
we have $h(N)$ jumps during the first $N$ time steps, the total
accumulated redundancy is less than $h(N)\log(n+1)+O(N/n)$. Hence,
if jumps are rare, they will not affect the total compressed length
significantly. Regular KT has unbounded one step redundancy and the
regular KT estimator also continues to be affected by all old data
as much as newer observations. Hence, if there is substantial change
in the middle of the file, the first part will adversely affect the
rest of the file. In \cite{Oneill12}, an empirical advantage of
adaptive CTW over regular CTW was demonstrated on files, which were
created by concatenating two different shorter files.
Here we have so far only proved bounds for the adaptive KT
estimators and not the CTW algorithm which is more relevant for
practical compressions since it takes context into account. However,
bounds for the adaptive KT estimator is all that is needed to prove
bounds for adaptive CTW. This can be done easily because there are
three parts contributing to the redundancy bounds for CTW
\cite{willems.f95p}: (1) redundancy used to find the `right' tree
(2) parameter redundancy given the `right' tree (3) arithmetic
coding redundancy (always bounded by 2). The first term has nothing
to do with the underlying estimator but with the code length of the
`right' tree. The problem is thus reduced to the second term (the
main term), which is the redundancy of the underlying KT estimator.
For regular KT in the stationary case, this is $O(1/m)$ for the
$m$:th time step. This adds up to a logarithmic term for the first
$N$ time steps and this is the only non-constant term. The $O(1/n)$
terms is for windowed KT replaced by an $O(1/n)$ term (Theorem
\ref{thm:1}) in the stationary case (where $n$ is the size of the
window) which accumulates to $O(N/n)$ if $N$ is the total length of
the file. In the interval case the term is replaced by $KL+O(1/n)$,
again according to Theorem \ref{thm:1}. In these cases the total
redundancy of adaptive CTW is $O(N/n)$. If we have $h(N)$ jump point
of KL-divergence at most $D$, the redundancy is $h(N)D+O(N/n)$.
%-------------------------------%
\paradot{Detecting change points and outliers}
%-------------------------------%
The algorithm for detecting change points and outliers in
\cite{Yam02,Tak06,Kaw12} relies on $\log{Pr(x_{t+1}\ |\ x_{1:t})}$
as a score. The idea is that this score is large in expectation if
the distributions have changed significantly and smaller if it has
not. They average over a number of time steps to get a good estimate
of this expectation. That it will be large if the distribution
change by much is clear but for it to be a well founded method one
also needs to be able to say that it will be small if the
distribution has at most changed a little. This is what we provide a
theory for in this article.
\section{Conclusion}
Some recent advances in real-time online change point detection,
outlier detection and compression have relied on discounting when
estimating parameters of a distribution that is changing over time.
A closely related alternative for dealing with non-stationarity in a
computationally efficient manner is to only use the last few
observations for the estimation. In this article we have provided a
theoretical analysis of how these estimators behave for important
classes of non-stationary environments and outlined the implication
of the results for the application of the mentioned algorithms.\\
\begin{small}
\begin{thebibliography}{ABCD}
\bibitem[BH93]{Barry93}
Daniel Barry and J.~A. Hartigan.
\newblock A bayesian analysis for change point problems.
\newblock {\em Journal of the American Statistical Association},
88(421):309--319, 1993.
\bibitem[BW94]{burrows.m94h}
Michael Burrows and David Wheeler.
\newblock A block-sorting lossless data compression algorithm.
\newblock {\em Digital SRC Research Report}, 1994.
\bibitem[CH87]{cormack.g87u}
G.~V. Cormack and R.~N.~S. Horspool.
\newblock Data compression using dynamic {M}arkov modelling.
\newblock {\em The Computer Journal}, 30(6):541--550, 1987.
\bibitem[CW84]{cleary.j84n}
John~G. Cleary and Ian~H. Witten.
\newblock Data compression using adaptive coding and partial string matching.
\newblock {\em IEEE Transactions on Communications}, 32:396--402, 1984.
\bibitem[E.S55]{Page55}
Page E.S.
\newblock A test for change in a parameter occurring at an unknown point.
\newblock {\em Biometrika}, 42, 1955.
\bibitem[FP99]{Fawcett99}
Tom Fawcett and Foster Provost.
\newblock Activity monitoring: noticing interesting changes in behavior.
\newblock In {\em Proceedings of the fifth ACM SIGKDD international conference
on Knowledge discovery and data mining}, KDD '99, pages 53--62, New York, NY,
USA, 1999. ACM.
\bibitem[Fu11]{Fu11}
Takchung Fu.
\newblock A review on time series data mining.
\newblock {\em Eng. Appl. Artif. Intell.}, 24(1):164--181, February 2011.
\bibitem[GS99]{Guralnik99}
Valery Guralnik and Jaideep Srivastava.
\newblock Event detection from time series data.
\newblock In {\em KDD}, pages 33--42, 1999.
\bibitem[KR03]{Kaw03}
T.~Kawabata and M.~M. Rashid.
\newblock A zero redundancy estimator for the context tree weighting method
with a finite window.
\newblock {\em IEEE International Symposium on Information Theory}, page 114,
2003.
\bibitem[Kri68]{krichevsky.r68r}
R.~E. Krichevsky.
\newblock The connection between the redundancy and reliability of information
about the sources.
\newblock {\em Problems of Information Transmission}, 4(3):48--57, 1968.
\bibitem[Kri70]{krichevsky.r70k}
R.~E. Krichevsky.
\newblock Lectures on information theory.
\newblock Technical report, Novosibirsk State University, 1970.
\bibitem[Kri98]{krichevskiy.r98y}
Rafail~E. Krichevsky.
\newblock Laplace's law of succession and universal encoding.
\newblock {\em IEEE Transactions on Information Theory}, 44:296--303, 1998.
\bibitem[KS12]{Kaw12}
Yoshinobu Kawahara and Masashi Sugiyama.
\newblock Sequential change-point detection based on direct density-ratio
estimation.
\newblock {\em Stat. Anal. Data Min.}, 5(2):114--127, April 2012.
\bibitem[KT81]{krichevsky.r81f}
Rafail~E. Krichevsky and V.~K. Trofimov.
\newblock The performance of universal encoding.
\newblock {\em IEEE Transactions on Information Theory}, 27(2):199--207, 1981.
\bibitem[Lor71]{Lorden71}
G.~Lorden.
\newblock Procedures for reacting to a change in distribution.
\newblock {\em Annals of Mathematical Statistics}, 42(6):1897--1908, 1971.
\bibitem[OHSS12]{Oneill12}
Alexander O'Neill, Marcus Hutter, Wen Shao, and Peter Sunehag.
\newblock Adaptive context tree weighting.
\newblock In {\em 2012 Data Compression Conference, Snowbird, UT, USA, April
10-12, 2012}, pages 317--326. IEEE Computer Society, 2012.
\bibitem[RD07]{Adams07}
Adams R.P and MacKay D.J.
\newblock Bayesian online changepoint detection, 2007.
\bibitem[Ris76]{rissanen.j76h}
Jorma~J. Rissanen.
\newblock Generalized {K}raft inequality and arithmetic coding.
\newblock {\em IBM Journal of Research and Devlopment}, 20(3):198--203, 1976.
\bibitem[RL79]{rissanen.j79n}
Jorma~J. Rissanen and Glen~G. Langdon.
\newblock Arithmetic coding.
\newblock {\em IBM Journal of Research and Devlopment}, 23:149--162, 1979.
\bibitem[Tro74]{trofimov.v74y}
V.~K. Trofimov.
\newblock The redundancy of markov source encoding.
\newblock {\em Problems of Information Transmission}, 10(4):16--24, 1974.
\bibitem[TSR09]{Turner09}
Ryan Turner, Yunus Saatci, and Carl~Edward Rasmussen.
\newblock Adaptive sequential {B}ayesian change point detection.
\newblock In {\em Advances in Neural Information Processing Systems (NIPS):
Temporal Segmentation Workshop}, 2009.
\bibitem[TY06]{Tak06}
Junichi Takeuchi and Kenji Yamanishi.
\newblock A unifying framework for detecting outliers and change points from
time series.
\newblock {\em IEEE Trans. Knowl. Data Eng.}, 18(4):482--492, 2006.
\bibitem[Wil96]{Willems96}
Frans M.~J. Willems.
\newblock Coding for a binary independent piecewise-identically-distributed
source.
\newblock {\em IEEE Transactions on Information Theory}, 42(6):2210--2217,
1996.
\bibitem[WST95]{willems.f95p}
Frans M.~J. Willems, Yuri~M. Shtarkov, and Tjalling Tjalkens.
\newblock The context tree weighting method: Basic properties.
\newblock {\em IEEE Transactions on Information Theory}, 41:653--664, 1995.
\bibitem[YT02]{Yam02}
Kenji Yamanishi and Junichi Takeuchi.
\newblock A unifying framework for detecting outliers and change points from
non-stationary time series data.
\newblock In {\em Proceedings of the Eighth ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, July 23-26, 2002, Edmonton, Alberta,
Canada}, pages 676--681. ACM, 2002.
\bibitem[Zac83]{Zacks83}
S.~Zacks.
\newblock {\em Survey of classical and Bayesian approaches to the change-point
problem: Fixed sample and sequential procedures in testing and estimation}.
\newblock Academic Press, 1983.
\bibitem[ZHJ09]{Hut09}
Ke~Zhang, Marcus Hutter, and Warren Jin.
\newblock A new local distance-based outlier detection approach for scattered
real-world data.
\newblock In {\em Proc. 13th Pacific-Asia Conf. on Knowledge Discovery and Data
Mining (PAKDD'09)}, volume 5467 of {\em LNAI}, pages 813--822, Bangkok, 2009.
Springer.
\bibitem[ZL77]{ziv.j77x}
Jacob Ziv and Abraham Lempel.
\newblock A universal algorithm for sequential data compression.
\newblock {\em IEEE Transactions on Information Theory}, 23:337--342, May 1977.
\bibitem[ZL78]{ziv.j78y}
Jacob Ziv and Abraham Lempel.
\newblock Compression of individual sequences via variable-rate coding.
\newblock {\em IEEE Transactions on Information Theory}, 24:530--536, 1978.
\end{thebibliography}
\end{small}
\end{document}