%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Universal Prediction of Selected Bits %%
%% Tor Lattimore, Marcus Hutter, Vaibhav Gavane (2011) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt,twoside]{article}
\topmargin=-10mm \oddsidemargin=5mm \evensidemargin=5mm
\textwidth=15cm \textheight=22cm
\usepackage{latexsym,amsmath,amssymb}
%-------------------------------%
% Macro-Definitions %
%-------------------------------%
\newcommand{\eqn}[1]{\begin{align}#1\end{align}}
\newcommand{\eq}[1]{\begin{align*}#1\end{align*}}
\newcommand{\proofof}{Proof of }
\newcommand{\proofend}{}
\def\subsubsect#1{\vspace{1ex plus 0.5ex minus 0.5ex}\noindent{\bf\boldmath{#1.}}}
\newcommand{\argmax}{\operatornamewithlimits{arg\,max}}
\newcommand{\ind}[1]{[\![ #1 ]\!]}
\newcommand{\R}[0]{\mathbb R}
\newcommand{\N}[0]{\mathbb N}
\usepackage{amsthm}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\theoremstyle{remark}
\newenvironment{keywords}{\centerline{\bf\small
Keywords}\begin{quote}\small}{\par\end{quote}\vskip 1ex}
\newcommand{\M}{\mathbf M}
\newcommand{\m}{\mathbf m}
\newcommand{\Mn}{\mathbf M_{norm}}
\newcommand{\Um}{{U_M}}
\newcommand{\Up}{{U_P}}
\newcommand{\Rc}{\mathcal R}
\newcommand{\Mc}{\mathcal M}
\newcommand{\Q}{\mathbb Q}
\newcommand{\B}{\mathcal B}
\newcommand{\leqt}{\stackrel{\times}\leq}
\newcommand{\geqt}{\stackrel{\times}\geq}
\newcommand{\eqt}{\stackrel{\times}=}
\newcommand{\prefix}{\sqsubset}
\newcommand{\prefixeq}{\sqsubseteq}
\renewcommand{\Alph}{\mathcal A}
\sloppy
\raggedbottom
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Title - Page %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{%\vspace{-4ex}
\vskip 2mm\bf\Large\hrule height5pt \vskip 4mm
Universal Prediction of Selected Bits
\vskip 4mm \hrule height2pt}
\author{{\bf Tor Lattimore} and {\bf Marcus Hutter} and {\bf Vaibhav Gavane}\\[3mm]
\normalsize Australian National University \\[-0.5ex]
\normalsize\texttt{tor.lattimore@anu.edu.au} \\
\normalsize Australian National University and ETH Z{\"u}rich \\[-0.5ex]
\normalsize\texttt{marcus.hutter@anu.edu.au} \\
\normalsize VIT University, Vellore \\[-0.5ex]
\normalsize\texttt{vaibhav.gavane@gmail.com}
}
\date{20 July 2011}
\maketitle
\begin{abstract}
Many learning tasks can be viewed as sequence prediction problems. For example, online classification can be converted
to sequence prediction with the sequence being pairs
of input/target data and where the goal is to correctly predict the target data given input data and previous input/target pairs.
Solomonoff induction is known to solve the
general sequence prediction problem, but only if the entire sequence is sampled from a computable distribution. In the case of classification
and discriminative learning though,
only the targets need be structured (given the inputs). We show that the normalised version of Solomonoff induction can still be used in this case,
and more generally that it can detect any recursive sub-pattern (regularity) within an otherwise completely unstructured sequence. It is also shown
that the unnormalised version can fail to predict very simple recursive sub-patterns.
%
\def\contentsname{\centering\normalsize Contents}
{\parskip=-2.7ex\tableofcontents}
\end{abstract}
\begin{keywords} %\small
Sequence prediction;
Solomonoff induction;
online classification;
discriminative learning;
algorithmic information theory.
\end{keywords}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The sequence prediction problem is the task of predicting the next symbol, $x_n$ after observing $x_1 x_2 \cdots x_{n-1}$.
Solomonoff induction \cite{Sol64a,Sol64b} solves this problem by taking inspiration from Occam's razor and Epicurus' principle of multiple
explanations. These ideas are formalised in the field of Kolmogorov complexity, in particular by the universal a priori semi-measure $\M$.
Let $\mu(x_n|x_1\cdots x_{n-1})$ be the true (unknown) probability of seeing $x_n$ having already observed $x_1\cdots x_{n-1}$.
The celebrated result of Solomonoff \cite{Sol64a} states that if $\mu$ is computable then
\eqn{\label{eqn-sol}
\lim_{n\to\infty} \left[\M(x_n|x_1\cdots x_{n-1}) - \mu(x_n | x_1\cdots x_{n-1})\right] = 0 \text{ with } \mu\text{-probability } 1
}
That is, $\M$
can learn the true underlying distribution from which the data is sampled with probability 1. Solomonoff induction is arguably the gold
standard predictor, universally solving many (passive) prediction problems \cite{Hut04,Hut07, Sol64a}.
However, Solomonoff induction makes no guarantees if $\mu$ is not computable. This would not be problematic if it were unreasonable to
predict sequences sampled from incomputable $\mu$, but this is not the case. Consider the sequence below, where every
even bit is the same as the preceding odd bit, but where the odd bits may be chosen arbitrarily.
\eqn{
\label{eqn-intro-1} \text{00 11 11 11 00 11 00 00 00 11 11 00 00 00 00 00 11 11}
}
Any child will quickly learn the pattern that each even bit is the same as the preceding odd bit and will
correctly predict the even bits. If Solomonoff induction is to be considered a truly intelligent predictor then it too should be
able to predict the even bits. More generally, it should be able to detect any computable sub-pattern.
It is this question, first posed in \cite{Hut04,Hut09open} and resisting attempts by experts for 6 years, that we address.
At first sight, this appears to be an esoteric question, but consider the following problem. Suppose you are given a sequence of pairs,
$x_1 y_1 x_2 y_2 x_3 y_3\cdots$
where $x_i$ is the data for an image (or feature vector) of a character and $y_i$ the corresponding ascii code (class label) for that character.
The goal of online classification is to construct a predictor
that correctly predicts $y_i$ given $x_i$ based on the previously seen training pairs. It is reasonable to assume that there is a relatively
simple pattern to generate $y_i$ given $x_i$ (humans and computers seem to find simple patterns for character recognition). However it is not necessarily reasonable to assume there exists a simple, or even computable,
underlying distribution generating the training data $x_i$. This problem is precisely what gave rise to discriminative learning \cite{LR06}.
It turns out that there exist sequences with even bits equal to preceding odd bits on which the conditional distribution of $\M$
fails to converge to $1$ on the even bits.
On the other hand, it is known that $\M$ is a defective measure, but may be normalised to a proper measure, $\Mn$.
We show that this normalised version {\it does} converge on any recursive sub-pattern
of any sequence, such as that in Equation (\ref{eqn-intro-1}). This outcome is unanticipated since (all?) other results in the field
are independent of normalisation \cite{Hut04,Hut07,LV08, Sol64a}. The proofs are completely different to the standard proofs of
predictive results.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Notation and Definitions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We use similar notation to \cite{Gacs83,Gacs08,Hut04}. For a more comprehensive introduction to Kolmogorov complexity and
Solomonoff induction see \cite{Hut04,Hut07, LV08, ZL70}.
%-------------------------------%
\subsubsect{Strings}
%-------------------------------%
A finite binary string $x$ is a finite sequence $x_1x_2x_3\cdots x_n$ with $x_i \in \B = \left\{0, 1\right\}$. Its length is denoted $\ell(x)$.
An infinite binary string $\omega$ is an infinite sequence $\omega_1\omega_2\omega_3\cdots$.
The empty string of length zero is denoted $\epsilon$.
$\B^n$ is the set of all binary strings of length $n$. $\B^*$ is the set of all finite binary strings. $\B^\infty$ is the
set of all infinite binary strings.
Substrings are denoted $x_{s:t} := x_s x_{s+1}\cdots x_{t-1}x_{t}$ where $s,t \in \N$ and $s \leq t$. If $s > t$ then $x_{s:t} = \epsilon$.
A useful shorthand is $x_{ 0$ such that $f(x) \geq c \cdot g(x)$ for all $x$. $f(x) \leqt g(x)$ is defined similarly.
$f(x) \eqt g(x)$ if $f(x) \leqt g(x)$ and $f(x) \geqt g(x)$.
\end{definition}
\begin{definition}[Measures]
We call $\mu:\B^* \to [0,1]$ a {\it semimeasure} if $\mu(x) \geq \sum_{b\in\B} \mu(xb)$ for all $x \in \B^*$, and a probability measure if equality
holds and $\mu(\epsilon) = 1$. $\mu(x)$ is the $\mu$-probability that a sequence starts with $x$. $\mu(b | x) := {\mu(xb) \over \mu(x)}$ is the
probability of observing $b \in \B$ given that $x \in \B^*$ has already been observed.
A function $P:\B^* \to [0,1]$ is a {\it semi-distribution} if $\sum_{x\in\B^*} P(x) \leq 1$ and a probability distribution if equality holds.
\end{definition}
\begin{definition}[Enumerable Functions]
A real valued function $f:A \to \R$ is {\it enumerable} if there
exists a computable function $f:A\times\N \to \Q$ satisfying
$\lim_{t\to\infty} f(a, t) = f(a)$ and $f(a, t+1) \geq f(a, t)$ for all $a \in A$ and $t \in \N$.
\end{definition}
\begin{definition}[Machines]
A Turing machine $L$ is a recursively enumerable set (which may be finite) containing pairs of finite binary strings $(p^1, y^1), (p^2, y^2), (p^3, y^3),\cdots$.
$L$ is a {\it prefix machine} if the set $\left\{p^1, p^2,p^3\cdots\right\}$ is prefix free (no program is a prefix of any other).
It is a {\it monotone machine} if for all $(p, y), (q, x) \in L$ with $\ell(x) \geq \ell(y)$, $p \prefixeq q \implies y \prefixeq x$.
We define $L(p)$ to be the set of strings output by program $p$. This is different for monotone and prefix machines.
For prefix machines, $L(p)$ contains only one element, $y \in L(p)$ if $(p, y) \in L$. For monotone machines, $y \in L(p)$ if there
exists $(p, x) \in L$ with $y \prefixeq x$ and there does not exist a $(q, z) \in L$ with $q \prefix p$ and $y \prefixeq z$.
For both machines $L(p)$ represents the output of machine $L$ when given input $p$.
If $L(p)$ does not exist then we say $L$ does not halt on input $p$.
Note that for monotone machines it is possible for the same program to output multiple strings. For example $(1, 1), (1, 11), (1, 111), (1, 1111), \cdots$
is a perfectly legitimate monotone Turing machine. For prefix machines this is not possible. Also note that if $L$ is a monotone machine
and there exists an $x \in \B^*$ such that $x_{1:n} \in L(p)$ and $x_{1:m} \in L(p)$ then $x_{1:r} \in L(p)$ for all $n \leq r \leq m$.
\end{definition}
\begin{definition}[Complexity] Let $L$ be a prefix or monotone machine then define
\eq{
\lambda_L(y) &:= \sum_{p : y \in L(p)} 2^{-\ell(p)} & C_L(y) &:= \min_{p \in \B^*} \left\{ \ell(p) : y \in L(p) \right\}
}
If $L$ is a prefix machine then we write $\m_L(y) \equiv \lambda_L(y)$. If $L$ is a monotone machine then we write $\M_L(y) \equiv \lambda_L(y)$.
Note that if $L$ is a prefix machine then $\lambda_L$ is an enumerable semi-distribution while if $L$ is a monotone machine, $\lambda_L$ is
an enumerable semi-measure. In fact, every enumerable semi-measure (or semi-distribution) can be represented via some machine $L$ as $\lambda_L$.
\end{definition}
For prefix/monotone machine $L$ we write $L_t$ for the first $t$ program/output pairs in the recursive
enumeration of $L$, so $L_t$ will be a finite set containing at most $t$ pairs.\footnote{$L_t$ will contain exactly $t$ pairs unless $L$ is finite,
in which case it will contain $t$ pairs until $t$ is greater than the size of $L$. This annoyance will never be problematic.}
The set of all monotone (or prefix) machines is itself recursively enumerable \cite{LV08},\footnote{Note the
enumeration may include repetition, but this is unimportant in this case.} which allows one to define a
universal monotone machine $\Um$
as follows. Let $L^i$ be the $i$th monotone machine in the recursive enumeration of monotone machines.
\eq{
(i'p, y) \in \Um \Leftrightarrow (p, y) \in L^i
}
where $i'$ is a prefix coding of the integer $i$. A universal prefix machine, denoted $\Up$, is defined in a similar way. For details see \cite{LV08}.
\begin{theorem}[Universal Prefix/Monotone Machines]\label{thm_universal}
For the universal monotone machine $\Um$ and universal prefix machine $\Up$,
\eq{
\m_\Up(y) &> c_L \m_L(y) \text{ for all } y\in \B^* & \M_\Um(y) &> c_L \M_L(y) \text{ for all } y\in\B^*
}
where $c_L > 0$ depends on $L$ but not $y$.
\end{theorem}
For a proof, see \cite{LV08}. As usual, we will fix reference universal prefix/monotone machines $\Up$, $\Um$ and drop the subscripts by letting,
\eq{
\m(y) &:= \m_\Up(y) \equiv \sum_{p : y \in \Up(p)} 2^{-\ell(p)} & \M(y) &:= \M_\Um(y) \equiv \sum_{p : y\in \Um(p)} 2^{-\ell(p)} \\
K(y) &:= C_\Up(y) \equiv \min_{p \in \B^*} \left\{\ell(p) : y\in\Up(p)\right\} & Km(y) &:= \min_{p\in\B^*} \left\{\ell(p) : y\in\Um(p)\right\}
}
The choice of reference universal Turing machine is usually\footnote{See \cite{HM07} for a subtle exception. All the results in this paper are independent of universal Turing machine.} unimportant since a different choice varies $\m, \M$ by only a multiplicative
constant, while $K, Km$ are varied by additive constants.
For natural numbers $n$ we define $K(n)$ by $K(\left)$ where $\left$ is the binary representation of $n$.
$\M$ is not a proper measure, $\M(x) > \M(x0) + \M(x1)$ for all $x \in \B^*$, which means that $\M(0|x) + \M(1|x) < 1$, so $\M$
assigns a non-zero probability that the sequence will end. This is because there are monotone programs $p$ that halt, or enter infinite loops.
For this reason Solomonoff introduced a normalised version, $\Mn$ defined as follows.
\begin{definition}[Normalisation]
\eq{
\Mn(\epsilon) &:=1 & \Mn(y_n | y_{ N$ where $f(\omega_{ 0$ since $p \prefix q$. For other values, $P(\cdot, t) = P(\cdot, t+1)$.
\end{enumerate}
Note that it is not possible that $p = q$ since then $x = y$ and duplicates are not added to $L$.
Therefore $P$ is an enumerable semi-distribution. By Theorem \ref{thm_kolmogorov} we have
\eqn{
\label{eqn-pos1} \m(\omega_{ 0$ there exists a $z \in \B^*$ such that $\M(0|z) + \M(1|z) < \delta$. This result is already known
and is left as an exercise (4.5.6) with a proof sketch in \cite{LV08}. For completeness, we include a proof. Recall that $\M(\cdot, t)$ is
the function approximating $\M(\cdot)$ from below. Fixing an $n$, define $z \in \B^*$ inductively as follows.
\begin{enumerate}
\item $z := \epsilon$
\item Let $t$ be the first natural number such that $\M(zb, t) > 2^{-n}$ for some $b \in \B$.
\item If $t$ exists then $z := z\neg b$ and repeat step 2. If $t$ does not exist then $z$ is left unchanged (forever).
\end{enumerate}
Note that $z$ must be finite since each time it is extended, $\M(zb, t) > 2^{-n}$. Therefore $\M(z\neg b, t) < \M(z, t) - 2^{-n}$ and so
each time $z$ is extended, the value of $\M(z, t)$ decreases by at least $2^{-n}$ so eventually $\M(zb, t) < 2^{-n}$ for all $b \in \B$. Now once the $z$
is no longer being extended ($t$ does {\it not} exist in step 3 above) we have
\eqn{
\label{eqn-lem1} \M(z0) + \M(z1) &\leq 2^{1 - n}.
}
However we can also show that $\M(z) \geqt 2^{-K(n)}$. The intuitive idea is that the process above requires only the value of $n$, which can be
encoded in $K(n)$ bits. More formally, let $p$ be such that $n \in \Up(p)$ and note that the following set is
recursively enumerable (but not recursive) by the process above.
\eq{
L_{p} := (p, \epsilon), (p, z_{1:1}), (p, z_{1:2}), (p, z_{1:3}), \cdots, (p, z_{1:\ell(z) - 1}), (p, z_{1:\ell(z)}).
}
Now take the union of all such sets, which is a) recursively enumerable since $\Up$ is, and b) a monotone machine because $\Up$ is a prefix machine.
\eq{
L := \bigcup_{(p, n) \in \Up} L_{p}.
}
Therefore
\eqn{
\label{eqn-lem2} \M(z) \geqt \M_L(z) \geq 2^{-K(n)}
}
where the first inequality is from Theorem \ref{thm_universal} and the second follows since if $n^*$ is the program of length $K(n)$
with $\Up(n^*) = n$ then $(n^*, z_{1:\ell(z)}) \in L$. Combining Equations (\ref{eqn-lem1}) and (\ref{eqn-lem2}) gives
\eq{
\M(0|z) + \M(1|z) &\leqt 2^{1 - n + K(n)}.
}
Since this tends to zero as $n$ goes to infinity,\footnote{An integer $n$ can easily be encoded in $2 \log n$ bits, so $K(n) \leq 2 \log n + c$ for some $c > 0$ independent of $n$.} for each $\delta > 0$ we can construct a $z\in\B^*$ satisfying $\M(0|z) + \M(1|z) < \delta$, as required.
%
For the second part of the proof, we construct $\omega$ by concatenation.
\eq{\omega := z^1 z^2z^3 \cdots
}
where $z^n \in \B^*$ is chosen such that,
\eqn{
\label{eqn-lem0} \M(0|z^n) + \M(1|z^n) < \delta_n
}
with $\delta_n$ to be chosen later. Now,
\eqn{
\label{eqn-lem3} \M(b|z^1\cdots z^n) &\equiv {\M(z^1\cdots z^n b) \over \M(z^1\cdots z^n) } \\
\label{eqn-lem4} &\leqt \left[{2^{K(\ell(z^1\cdots z^{n-1})) + K(z^1\cdots z^{n-1})} }\right]{\M(z^n b) \over \M(z^n)} \\
\label{eqn-lem5} &\equiv \left[2^{K(\ell(z^1\cdots z^{n-1})) + K(z^1\cdots z^{n-1})} \right] \M(b|z^n)
}
where Equation (\ref{eqn-lem3}) is the definition of conditional probability. Equation (\ref{eqn-lem4}) follows by
applying Lemma \ref{lem_M} with $x = z^1z^2\cdots z^{n-1}$ and $y = z^n$ or $z^n b$.
Equation (\ref{eqn-lem5}) is again the definition of conditional probability. Now let
\eq{
\delta_n = {2^{-n} \over 2^{K(\ell(z^1 \cdots z^{n-1})) + K(z^1\cdots z^{n-1})}}.
}
Combining this with Equations (\ref{eqn-lem0}) and (\ref{eqn-lem5}) gives
\eq{
\M(0 | z^1 \cdots z^n) + \M(1|z^1 \cdots z^n) \leqt 2^{-n}.
}
Therefore,
\eq{
\liminf_{n\to\infty} \left[\M(0|\omega_{ 0$ such that
$\M(\bar\omega_{2n}|\bar\omega_{<2n}) > c$ for all $n \in \N$. In this sense $\M$ can still be used to predict in the same way as $\Mn$,
but it will never converge as in Equation (\ref{eqn-sol}).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Discussion}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%-------------------------------%
\subsubsect{Summary}
%-------------------------------%
Theorem \ref{thm_positive} shows that if an infinite sequence contains a computable sub-pattern then the normalised universal semi-measure $\Mn$
will eventually predict it. This means that Solomonoff's normalised version of induction is effective in the classification example given
in the introduction. Note that we have only proven the binary case, but expect the proof will go through identically for arbitrary finite
alphabet.
On the other hand, Theorem \ref{thm_negative} shows that plain $\M$ can fail to predict such structure in the sense that the conditional distribution
need not converge to $1$ on the true sequence. This is because it is not a proper measure, and does not converge to one.
These results are surprising since (all?) other predictive results, including Equation (\ref{eqn-sol}) and many others in \cite{Hut04,Hut07,LV08,Sol64a},
do not rely on normalisation.
%-------------------------------%
\subsubsect{Consequences}
%-------------------------------%
We have shown that $\Mn$ can predict recursive structure in infinite strings that are incomputable (even stochastically so).
These results give hope that a Solomonoff inspired algorithm may be effective at online classification, even when the training data is
given in a completely unstructured way. Note that while $\M$ is enumerable and $\Mn$ is only approximable,\footnote{A function $f$ is
approximable if there exists a computable function $f(\cdot, t)$ with $\lim_{t\to\infty} f(\cdot, t) = f(\cdot)$. Convergence need not be monotonic.}
both the conditional distributions are only approximable, which means it is no harder to predict using $\Mn$ than $\M$.
%-------------------------------%
\subsubsect{Open Questions}
%-------------------------------%
A number of open questions were encountered in writing this paper.
\begin{enumerate}
\item Extend Theorem \ref{thm_positive} to the stochastic case where a sub-pattern is generated
stochastically from a computable distribution rather than merely a computable function. It seems likely that a different approach
will be required to solve this problem.
\item Another interesting question is to strengthen the result by proving a convergence rate. It may be possible to prove that under
the same conditions as Theorem \ref{thm_positive} that $\sum_{i=1}^\infty \left[1 - \Mn(\omega_{n_i}|\omega_{ 0$ such that $f(x) > c\cdot g(x)$ for all $x$ \\
$\leqt$ & $f(x) \leqt g(x)$ if there exists a $c > 0$ such that $f(x) < c\cdot g(x)$ for all $x$ \\
$\eqt$ & $f(x) \eqt g(x)$ if $f(x) \geqt g(x)$ and $f(x) \leqt g(x)$ \\
$x \prefix y$ & $x$ is a prefix of $y$ and $\ell(x) < \ell(y)$ \\
$x \prefixeq y$ & $x$ is a prefix of $y$ \\
\hline
\end{tabular}
\end{document}
%--------------------End-of-EvenBits.tex----------------------%