\documentclass[12pt,twoside]{article} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Consistency of Feature Markov Processes %% %% Peter Sunehag and Marcus Hutter (2010) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{amsmath,amssymb} \def\eqvsp{} \newdimen\paravsp \paravsp=1.3ex \topmargin=-10mm \oddsidemargin=5mm \evensidemargin=5mm \textwidth=15cm \textheight=22cm \sloppy\lineskip=0pt %-------------------------------% % Macro-Definitions % %-------------------------------% \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{remark}[theorem]{Remark} \newenvironment{keywords}{\centerline{\bf\small Keywords}\begin{quote}\small}{\par\end{quote}\vskip 1ex} \newenvironment{proof}{\paradot{Proof}}{} \def\beq{\begin{equation}} \def\eeq{\end{equation}} \def\beqn{\begin{displaymath}}\def\eeqn{\end{displaymath}} \def\bqa{\begin{eqnarray}} \def\eqa{\end{eqnarray}} \def\bqan{\begin{eqnarray*}} \def\eqan{\end{eqnarray*}} \newdimen\paravsp \paravsp=1.3ex \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\eps{\varepsilon} \def\epstr{\epsilon} % for empty string \def\nq{\hspace{-1em}} \def\qmbox#1{{\quad\mbox{#1}\quad}} \def\qed{\hspace*{\fill}\rule{1.4ex}{1.4ex}$\quad$} \def\eoe{\hspace*{\fill} $\diamondsuit\quad$} % end of example \def\eor{\hspace*{\fill} $\diamond\quad$} % end of remark \def\A{{\cal A}} \def\S{{\cal S}} \def\X{{\cal X}} \def\Y{{\cal Y}} \def\EE{I\!\!E} % expected value \def\t{\theta} \def\Cost{\mbox{\sl Cost}} \def\ICost{\mbox{\sl ICost}} \def\OCost{\mbox{\sl OCost}} \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% T i t l e - P a g e %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{ \vskip 2mm\bf\Large\hrule height5pt \vskip 4mm Consistency of Feature Markov Processes \vskip 4mm \hrule height2pt} \author{{\bf Peter Sunehag} and {\bf Marcus Hutter} \\[3mm] \normalsize RSISE$\,$@$\,$ANU and SML$\,$@$\,$NICTA \\ \normalsize Canberra, ACT, 0200, Australia \\ \texttt{\small\{Peter.Sunehag,Marcus.Hutter\}@anu.edu.au} } \date{12 July 2010} \maketitle \begin{abstract} We are studying long term sequence prediction (forecasting). We approach this by investigating criteria for choosing a compact useful state representation. The state is supposed to summarize useful information from the history. We want a method that is asymptotically consistent in the sense it will provably eventually only choose between alternatives that satisfy an optimality property related to the used criterion. We extend our work to the case where there is side information that one can take advantage of and, furthermore, we briefly discuss the active setting where an agent takes actions to achieve desirable outcomes. % Table of contents \def\contentsname{\centering\normalsize Contents} {\parskip=-2.5ex\tableofcontents} \end{abstract} \begin{keywords} Markov Process (MP); Hidden Markov Model (HMM); Finite State Machine (FSM); Probabilistic Deterministic Finite State Automata (PDFA); Penalized Maximum Likelihood (PML); ergodicity; asymptotic consistency; suffix trees; model selection; learning; reduction; side information; reinforcement learning. \end{keywords} \newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction}\label{sec:Intro} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% When studying long term sequence prediction one is interested in answering questions like: What will the next $k$ observations be? How often will a certain event or a sequence of events occur? What is the average rate of a variable like cost or income? This can be interesting for forecasting time series and for choosing policies with desirable outcomes. Hidden Markov Models \cite{CapMouRyd05,EphMer02} are often used for long term forecasting and sequence prediction. In this article we will restrict our study to models based on states that result from a deterministic function of the history, in other words, states that summarize useful information that has been observed so far. We will consider finite state space maps with the property that given the current state and the next observation we can determine the next state. These maps are sometimes called Probabilistic-Deterministic Finite Automata (PDFA) \cite{VidThoHig05a} and they have recently been applied in reinforcement learning \cite{Mah10}. A particular example of this is to use suffix trees \cite{Ris83,Sin96,McC96}. Our goal is to prove consistency for our penalized Maximum Likelihood criteria for picking a map from histories to states in the sense that we want to eventually only choose between alternatives that are optimal for prediction. The sense of optimality could relate to predicting the next symbol, the next $k$ symbols or to have minimal entropy rate for an infinite horizon. %-------------------------------% %\paradot{Outline} %-------------------------------% After the preliminary Section \ref{sec:Prelim} we begin our theory development in Section \ref{sec:HtoS}. In our problem setting we have a finite set $\Y$, a sequence $y_n$ of elements from $\Y$, and we are interested in predicting the future of the sequence $y_n$. To do this, being inspired by \cite{Hut09a} where general criteria for choosing a feature map for reinforcement learning were discussed, we first want to learn a \emph{feature map} $\Phi(y_{1:n})=s_n$ where $y_{1:t}:=y_1,....,y_t$. We would like the map to have the following properties: \begin{enumerate} \item The distribution for the sequence $s_n$ induced by the distribution for the sequence $y_n$ should be that of a Markov chain or should be a distribution which is indistinguishable from a Markov chain for the purpose of predicting the sequence $y_n$. \item We want as few states as possible so that we can learn a model from a modest amount of data. \item We want the model of the sequence $y_n$ that arises as a function of the Markov chain $s_n$ to be as good as possible. Ideally it should be the true distribution. \end{enumerate} Our approach consists of defining criteria that can be applied to any class of $\Phi$, but later we restrict our study to a class of maps that are defined by finite-state machines. These maps are defined by introducing a deterministic function $\psi$ such that $s_{n}=\psi(s_{n-1},y_n)$. If we have chosen such a map $\psi$ and a first state $s_0$ then the sequence $y_n$ determines a unique sequence $s_n$ and therefore we have also defined a map $\Phi(y_{1:n})=s_n$. In Section \ref{sec:Prelim} we provide some preliminaries on random sequences and Hidden Markov Models. We introduce a class of ergodic sequences which is the class of sequences that we work with in this article. They are sequences with the property that an individual sequence determines a distribution over infinite sequences. % We present our consistency theory by first presenting very generic results in the beginning of Section \ref{sec:HtoS} and then we show how various classes of maps and models fit into this. This has the consequence that we first have results where we guarantee optimality given that the individual sequence that we work with has certain properties (and these results, therefore, have no ``almost sure'' in the statement since the setting is not probabilistic) while in the latter part we show that if we sample the sequence in certain ways we will almost surely get a sequence with these properties. % In particular in Section \ref{sec:fsmmap} we will take a closer look at suffix tree sources and maps based on finite state machines related to probabilistic deterministic finite automata. % Section \ref{sec:Main} summarizes the findings in a main theorem that says under some assumptions (a class of maps based on finite state machines of bounded memory and ergodicity) we will recover the true model (or the closest we can get to the true model). % Section \ref{sec:Side} contains a discussion of sequence prediction with side information, % Section \ref{sec:Active} briefly discusses the active case where an agent acts in an environment and earns rewards, and finally % Section \ref{sec:Conc} contains our conclusions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries}\label{sec:Prelim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section we will review some notions and results that the rest of the article will rely upon. We start with random sequences and then follows a section on Hidden Markov Models (HMM). %-------------------------------% \paradot{Random Sequences} %-------------------------------% Consider the set of all infinite sequences $y_t, t=1,2,...$ of elements from a finite alphabet $\Y$. We equip the set with the $\sigma$-algebra that is generated by the cylinder sets $\Gamma_{y_{1:n}}=\{x_{1:\infty} |\ x_t=y_t, t=1,...,n\}$. A measure with respect to this space is determined by its values on the cylinder sets. Not every set of values is valid. We need to assume that the measure of $\Gamma_{y_{1:t}}$ is the sum of the measures of the sets $\Gamma_{y_{1:t}\tilde y}$ for all possible $\tilde y\in \Y$. If we want it to be a probability measure we furthermore need to assume that the measure of the whole space $\Y^\infty$ (which is the cylinder set $\Gamma_\epstr$ of the empty string $\epstr$) equals to one. The concept that is introduced in the following two definitions is of central importance to this article. In particular \emph{ergodic sequences} is the class of sequences that we intend to model. They are sequences that can be used to define a distribution over infinite sequences that we will be interested in learning. \begin{definition}[Distribution defined from one sequence] A sequence $y_{1:\infty}$ defines a probability distribution on infinite sequences if the (relative) frequency of every finite substring of $y_{1:\infty}$ converges asymptotically. The probabilities of the cylinder sets are defined to equal those limits:\\ \centerline{$ \Gamma_{z_{1:m}}:=\lim_{n\to\infty}\#\{t\leq n:y_{t+1:t+m}=z_{1:m}\}/n $} \end{definition} \begin{definition}[ergodic sequence]\label{def:erg} We say that a sequence is ergodic if the frequencies of every finite substring are converging asymptotically. \end{definition} As probabilistic models for random sequences we will in this article focus on Hidden Markov Models (HMMs) \cite{BauPet66,Pet69}. More recent surveys on Hidden Markov Models are \cite{EphMer02,CapMouRyd05}. %-------------------------------% \paradot{Hidden Markov Models} %-------------------------------% Here we define distributions over sequences of elements from a finite set $\Y$ of size $Y$ based on an unobserved Markov chain of elements from a finite state set $\S$ of size $S$. \begin{definition}[Hidden Markov Model, HMM] Assume that we have a Markov chain with an $S\times S$ transition matrix $T=(T_{s,s'})$ and that we also have an $S\times Y$ emission matrix $E=(E_{s,y})$ where $E_{s,y}$ is the probability that state $s$ will generate outcome $y\in \Y$. If we introduce a starting probability vector we have defined a probability distribution over sequences of elements from $\Y$. This is called a Hidden Markov Model (HMM). \end{definition} %-------------------------------% \paradot{Sequence Prediction} %-------------------------------% One use of Hidden Markov Models (and functions of Markov chains) is sequence prediction. Given a history $y_1,...,y_n$ we want to predict the future $y_{n+1},...$. In some situations we know what state we are in at time $n$ and that state then summarizes the entire history without losing any useful information since the future is conditionally independent of the past, given the current state. If we are doing one step prediction we are interested in knowing $Pr(y_{n+1}|s_n).$ We can also consider a zero step lookahead (called filtering) $Pr(y_{n}|s_n)$ or an $m$ step $Pr(y_{n+1},...,y_{n+m}|s_n).$ The $m$ step could also be just $Pr(y_{n+m}|s_n).$ In a sense we can consider an infinite lookahead ability evaluated by the entropy rate $-\lim_{m\to\infty}\frac{1}{m}\log Pr(y_{n+1},...,y_{n+m}|s_n).$ If the Markov chain is ergodic this limit does not depend on the state $s_n$. %-------------------------------% \paradot{Limit Theorems} %-------------------------------% The following theory that is the foundation for studying consistency of HMMs was developed in \cite{BauPet66} and \cite{Pet69}. See \cite{CapMouRyd05} chapter 12 for the modern state of the art. \begin{definition}[ergodic Markov chain] A Markov chain (and the stochastic matrix that contains its transition probabilities) is called ergodic if it is possible to move from state $s$ to state $s'$ in a finite number of steps for all $s$ and $s'$. \end{definition} The following theorem \cite{CapMouRyd05} introduces the generalized cross-entropy $H$ and shows that it is well defined and that it can be estimated for ergodic HMMs. It can be interpreted as the (idealized) expected number of bits needed for coding a symbol generated by a distribution defined by $\t_0$ but using the distribution defined by $\t$. \begin{theorem}[ergodic HMMs]\label{thm:erg} If $\t$ and $\t_0$ are HMM parameters where the transition matrix for $\t_0$ is an ergodic stochastic matrix, then there exists a finite number $H(\t_0,\t)$ (which can also be defined as $\lim_{n\to\infty} H_{n,s}(\t_0,\t)$ for any initial state $s$ where $H_{n,s}(\t_0,\t):= \frac{1}{n}\EE_{\t_0}\log{Pr(y_1,...,y_n|s_0=s,\t)})$ such that $P_{\t_0}$ a.s. \beqn -\lim_{n\to\infty}\frac{1}{n}\log{Pr(y_1,...,y_n|\ \t)} ~=~ H(\t_0,\t) \eeqn and the convergence is uniform in the parameter space. \end{theorem} \begin{definition}[Equivalent HMMs] For an HMM $\t_0$, let $M[\t_0]$ be the set of all $\t$ such that the HMM with parameters $\t$ define the same distribution over outcomes as the HMM with parameters $\t_0$. \end{definition} \begin{theorem}[Minimal cross-entropy for the truth and only the truth] $H(\t_0,\t)\geq H(\t_0,\t_0)$ with equality if and only if $\t\in M[\t_0]$. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Maps From Histories To States}\label{sec:HtoS} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Given a sequence of elements $y_n$ from a finite alphabet we want to define a map $\Phi:\Y^*\to\S$, which maps histories (finite strings) of elements to states $\Phi(y_{1:n})=s_n$. The reasons for this include, as was explained in the introduction, in particular the ability to learn a model efficiently. Suppose that every $\Phi$ under consideration is such that the size of its state space $\S$ is a finite number that depends on $\Phi$. We are also interested in the case when we have side information $x_n\in \X$ and we define a map $\Phi:(\X\times\Y)^*\to\S$. In this more general case the models that we consider for the sequence $y$ will have hidden states while in the case without side information the state (given the $y$ sequence) is not hidden. We have two reasons for expressing everything in an HMM framework. We can model long-range dependence in the $y_n$ sequence through having states and we include the more general case where there is side information. \begin{definition}[Feature sequence/process] A map $\Phi$ from finite strings of elements from $\Y$ (or $\X\times\Y$) to elements in a finite set $\S$ and a sequence $y_{1:n}$ induces a state sequence $s_{1:n}$. Define an HMM through maximum likelihood estimation: The sequence $s_t=\Phi(y_{1:t})$ gives transition matrix $T(n)=(T_{s,s'})$ of probabilities \beqn T_{s,s'}(n) ~:=~ \frac{\#\{t\leq n|s_t=s,\ s_{t+1}=s'\}}{\#\{t\leq n|s_t=s\}} \eeqn and emission matrix $E(n)$ of probabilities \beqn E_{s,y}(n) ~:=~ \frac{\#\{t\leq n|s_t=s,\ y_{t}=y\}}{\#\{t\leq n| s_t=s\}}. \eeqn Denote those HMMs by $\hat{\t}_n:=(T(n),E(n))$. We will refer to the sequence $\hat{\t}_n$ as the parameters corresponding to $\Phi$ or generated by $\Phi$. \end{definition} We will first state results based on some generic properties that we have defined with just the goal of making the proofs work. Then we will show that some more easily understandable cases will satisfy these properties. We structure it this way not only for generality but also to make the proof techniques clearer. %-------------------------------% \paradot{Ergodic Sequences}\label{sec:ergseq} %-------------------------------% We begin by defining the fundamental ergodicity properties that we will rely upon. We provide asymptotic results for individual sequences that satisfy these properties. In the next two subsections we identify situations where we will almost surely get such a sequence which satisfies these ergodicity properties. \begin{definition}[ergodic w.r.t.\ $\Phi$]\label{def:phierg} As stated in Definition \ref{def:erg}, we say that a sequence $y_t$ is ergodic if all substring frequencies converge as $n\to\infty$. Furthermore we say that \\1. the sequence $y_t$ is ergodic with respect to a map $\Phi(y_{1:t})=s_t$ if all state transition frequencies $T_{s,s'}(n)$ and emission frequencies $E_{s,y}(n)$ converge as $n\to\infty$. \\2. the sequence $y_t$ is ergodic with respect to a class of maps if it is ergodic with respect to every map in the class. \end{definition} \begin{definition}[HMM-ergodic]\label{def:hmmerg} We say that a sequence $y_t$ is HMM-ergodic for a set of HMMs $\Theta$ if there is an HMM with parameters $\t_0$ such that \beqn -\frac{1}{n}\log Pr(y_1,...,y_n\ |\ \t) ~\to~ H(\t_0,\t) \eeqn uniformly on compact subsets of $\Theta$. \end{definition} \begin{definition}[Log-likelihood] $L_n(\Phi)=-\log{Pr(y_1,...,y_n|\hat{\t}_n)}$ \end{definition} We will prove our consistency results by first proving consistency using Maximum Likelihood (ML) for a finite class of maps and then we prove that we can add a sublinearly growing model complexity penalty and still have consistency. \begin{proposition}[HMM consistency of ML for finite class]\label{genfinite} Suppose that $y_t$ is HMM-ergodic for the parameter set $\Theta$ with optimal parameters (in the sense of Definition \ref{def:hmmerg}) $\t_0$, $y_t$ is ergodic for the finite class of maps $\{\Phi_i\}_{i=1}^K$ and suppose that $\t_i\in\Theta$ are the limiting parameters generated by $\Phi_i$. Then it follows that there is $N<\infty$ such that for all $n\geq N$ the map $\Phi_i$ selected by minimizing $L_n$ generates parameters $\hat{\t}_i^n$ whose limit is in $\arg\min_{\t_i} H(\t_0,\t_i)$. \end{proposition} \begin{proof} It follows from Definition \ref{def:hmmerg} and continuity (in $\t$) of the log-likelihood that \beqn \lim_{n\to\infty} \frac{1}{n}L_n(\Phi_i) ~=~ H(\t_0,\t_i) \eeqn since the convergence in Definition \ref{def:hmmerg} is uniform. Note that the parameters that define the log-likelihood $L_n(\Phi_i)$ can be different for every $n$ so the uniformity of the convergence is needed to draw the conclusion above. By Definition \ref{def:phierg} we know that if $\hat{\t}_n^i$ are the parameters generated by $\Phi_i$ at time $n$, then $\lim_{n\to\infty}\hat{\t}_n^i=\t_i$ exists for all $i$. It follows that if $\t_i\notin \arg\min_{\t_j} H(\t_0,\t_j)$ then there must be an $N<\infty$ such that $\Phi_i$ is not selected at times $n\geq N$. Since there are only finitely many maps in the class there will be a finite such $N$ that works for all relevant $i$. \qed\end{proof} \begin{definition}[HMM Cost function]\label{def:hmmcost} If the HMM with parameters $\hat{\t}_n$ that has been estimated from $\Phi$ at time $n$ has $S$ states, then let \beqn \Cost_n(\Phi) ~=~ -\log{Pr(y_1,...,y_n|\hat{\t}_n)}+pen(n,S) \eeqn where $pen(n,S)$ is a positive function that is increasing in both $n$ and $S$ and is such that $pen(n,S)/n\to 0$ for $n\to\infty$ for all $S$. \end{definition} We call the negative log-probability term the \emph{data coding cost} and the other term is the \emph{model complexity penalty}. They are both motivated by coding (coding the data and the model). For instance in MDL/MML/BIC, $pen(n,S)={d\over 2}\log n+O(1)$, where $d$ is the dimensionality of the model $\t$. \begin{proposition}\label{genfewer} Suppose that $\Phi_0$ has optimal limiting parameters $\t_0$ with as few states as possible. In other words if an HMM has fewer states than the HMM defined by $\t_0$, then it has a strictly larger entropy rate. We use a (finite, countable, or uncountable) class of maps that includes only $\Phi_0$ and maps that have strictly fewer states. We assume that all the maps generate converging parameters. Then there is an $N$ such that the function $\Cost$ is minimized by $\Phi_0$ at all times $n\geq N$. \end{proposition} \begin{proof} Suppose that $\t_0$ has $S_0$ states. We will use a bound for how close one can get to the true HMM using fewer states. We would like to have a constant $\eps>0$ such that $H(\t_0,\t)>H(\t_0,\t_0)+\eps$ for all $\t$ with fewer then $S_0$ states. The existence of such an $\eps$ follows from continuity of $H$ (which is actually also differentiable \cite{BauPet66}), the fact that the HMMs with fewer than $S_0$ states can be compactly (in the parameter space) embedded into the space of HMMs with exactly $S_0$ states, and that this embedded subspace has a strictly positive minimum Euclidean distance from $\t_0$ in this parameter space. The existence of $\eps>0$ with this property implies the existence of $D>0$ such that the alternatives with fewer than $S_0$ states have, for large $n$, at least $Dn$ worse log probabilities than the distribution $\t_0$. Therefore the penalty term (for which $pen(n,S)/n\to 0$) will not be able to indefinitely compensate for the inferior modeling. \qed\end{proof} \begin{theorem}[HMM consistency of Cost for finite class]\label{corgenfinite} Proposition \ref{genfinite} is also true for $\Cost$. \end{theorem} \begin{proof} $H(\t_0,\t_k)0$ such that for large $n$, $L_n(\Phi_j)-L_n(\Phi_k)\geq Cn$. Since $pen(n,S)/n\to 0$ for $n\to\infty$ we know that any difference in model penalty will be overtaken by the linearly growing difference in data code length. \qed\end{proof} %-------------------------------% \paradot{Maps that induce HMMs}\label{sec:indhmm} %-------------------------------% In this section we will assume that we use a class of maps whose states we know form a Markov chain. \begin{definition}[Feature Markov Process, $\mathbf\Phi$MP] Suppose that \beqn Pr(y_{n}|\Phi_0(y_1),...,\Phi_0(y_{1:n})) ~=~ Pr(y_n|\Phi_0(y_{1:n})) \eeqn and that the state sequence is Markov, i.e. \beqn Pr(\Phi_0(y_{1:n})|\Phi_0(y_1),...,\Phi_0(y_{1:n-1})) ~=~ Pr(\Phi_0(y_{1:n})|\Phi_0(y_{1:n-1})). \eeqn Then we say that $\Phi_0$ induces an HMM. We call HMMs induced by $\Phi_0$, Feature Markov Process ($\Phi$MP). If the HMM that is defined this way by $\Phi_0$ is the true distribution for the sequence $y_1,y_2,...$, then we say that ``$\Phi_0$ is correct''. We will only discuss the situation when the true HMM is ergodic so we will only say that there is a correct $\Phi_0$ in those situations, hence the statement $\Phi_0$ is correct will contain the assumption that the truth is ergodic. \end{definition} \begin{example} The map $\Phi$ which sends everything to the same state always induces an HMM but, unless the sequence $y_1,y_2,...$ is i.i.d, it is not correct. \eoe\end{example} \begin{proposition}[Convergence of estimated distributions] If $\Phi_0$ is correct then $P_{\hat{\t}_n}\to P_{\t_0}$ for $n\to\infty$ (as distributions on finite strings of a (any) fixed length), where $P_{\t_0}$ is the true HMM distribution for the outcomes, $P_\t$ is the HMM distribution defined by $\t$ and $\hat{\t_n}$ are the parameters generated by $\Phi_0$. \end{proposition} \begin{proof} We are estimating the parameters $\hat{\t}_n$ through maximum likelihood for the generated sequence of states. Consistency of maximum likelihood estimation for Markov chains implies that $\hat{\t}_n\to\t_0$. This implies the proposition due to continuity with respect to the parameters of the likelihood (for any finite sequence length). \qed\end{proof} \begin{proposition}[Inducing HMM implies drawing ergodic sequences] If we have a set of maps that induce HMMs and the sequence $y_t$ is drawn from one of the induced ergodic HMMs, then almost surely \\1. $y_t$ is HMM-ergodic\\2. we will draw an ergodic sequence $y_t$ with respect to the considered class of maps. \end{proposition} \begin{proof} 1. is a consequence of Theorem \ref{thm:erg}. \\2. This follows from consistency of maximum likelihood for Markov chains (generalized law of large numbers) since the claim is that state transition frequencies and emission frequencies converge. \qed\end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Maps based on Finite State Machines (FSMs)}\label{sec:fsmmap} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We will in this section consider maps of a special form that are related to PDFAs. We will assume that $\Phi$ is such that there is a $\psi$ such that \beqn \Phi(y_{1:n}) ~=~ \psi(\Phi(y_{1:n-1}),y_n). \eeqn In other words, the current state is derived deterministically from the previous state and the current perception. Given an initial state the state sequence is then deterministically determined by the perceptions and therefore the combination of $\psi$ with an initial state defines a map $\Phi$ from histories to states. This class of maps $\Phi$ can also define a class of probabilistic models of the sequence $y_n$ by assuming that $y_n$ only depends on $s_{n-1}=\Phi(y_{1:n-1})$. This leads to the formula \beqn Pr(s'|s) ~=~ \sum_{y:\psi(s,y)=s'} Pr(y|s) \eeqn and as a result we have defined an HMM for the sequence $y_n$. \begin{definition}[Sampling from FSM]\label{def:samplemap} If we follow the procedure above we say that we have sampled the sequence $y_t$ from the FSM. If the Markov chain of states is ergodic we say that we have sampled $y_t$ ergodically from the FSM. \end{definition} %-------------------------------% \paradot{Suffix Trees} %-------------------------------% We consider a class of maps based on FSMs that can be expressed using Suffix Trees \cite{Ris86} with the same states (suffixes) as the FSM. The resulting models are sometimes called FSMX sources. A suffix tree is defined by a suffix set which is a set of finite strings. The set must have the property that none of the strings is an ending substring (a suffix) of another string in the set and such that any sufficiently long string ends with a substring in the suffix set. Given any sufficiently long string we then know that it ends with exactly one of the suffixes from the suffix set. If the suffix set furthermore has the property that given the previous suffix and the new symbol there is exactly one element (state) from the suffix set that can (and is) the end of the new longer string, then it is an FSMX source. Another terminology says that the suffix set is FSM closed. The property implies (directly by definition) that there is a map $\psi$ such that $\psi(s_{t-1},y_t)=s_t$. The following proposition shows a very nice connection between ergodic sequences and FSMX sources which will be generalized in Proposition \ref{FSMerg} to more general sources based on bounded-memory FSMs. \begin{proposition}[ergodicity of suffix trees]\label{suffix} If we have a set of maps based on FSMs that can be expressed by suffix trees, and the sequence $y_t$ is sampled ergodically (Definition \ref{def:samplemap}) using one of the maps, then almost surely we get a sequence $y_t$ that is ergodic with respect to the considered class of maps and $y_t$ is HMM-ergodic. \end{proposition} \begin{lemma}\label{sufone} If the sequence $y_t$ is ergodic, then the state transition frequencies and emission (of $y$) frequencies for a FSM closed suffix tree are converging. \end{lemma} \begin{proof} Let the map $\Phi$ be defined by the suffix set in question. Suppose that $s'$ is a suffix that can follow directly after $s$. This means that there is a symbol $y$ such that if you concatenate it to the end of the string $s$, then this new string $\tilde{s}$ ends with the string $s'$. This means that whenever a string of symbols $y_{1:n}$ ends with $\tilde{s}$, then the sequence of states generated by applying the map $\Phi$ to the sequence $y_{1:n}$ will end with $s_{n-1}=s$ and $s_n=s'$. It is also true that whenever the state sequence ends with $ss'$ then $y_{1:n}$ ends with $\tilde{s}$. Therefore, the counts (of $ss'$ in the state sequence and $\tilde{s}$ in the $y$ sequence) up until any finite time point are also equal. We will in this proof say that $\tilde{s}$ is the string that corresponds to $ss'$. \\ Given any ordered pair of states $(s,s')$ where $s'$ can follow $s$, let $c_{s,s'}(n)$ be the number of times $ss'$ occurs in the state sequence up to time $n$ and let $d_{s,s'}(n)$ be the number of times the string $\tilde{s}$ that corresponds to $ss'$ has occurred. We know that $c_{s,s'}(n)=d_{s,s'}(n)$ for any such pair $ss'$ and any $n$. If $s'$ cannot follow $s$ we let both $c_{s,s'}=0$ and $d_{s,s'}=0$. The state transition frequency for the transition from $s$ to $s'$ up until time $n$ is \beqn \frac{c_{s,s'}(n)}{\sum_{s'} c_{s,s'}(n)} ~=~ \frac{d_{s,s'}(n)}{\sum_{s'} d_{s,s'}(n)} ~=~ \frac{d_{s,s'}(n)}{d_{s}(n)} ~=~ \frac{d_{s,s'}(n)}{n}\frac{n}{d_{s}(n)} \eeqn where $d_s(n)$ is the number of times that the string that defines $s$ has occurred up until time $n$ in the $y$ sequence. The right hand side converges to the frequency of the string $\tilde{s}$ divided by the frequency of the string that defines $s$. Thus we have proved that state transition frequencies converge. Emissions work the same way. \qed\end{proof} \begin{lemma}\label{suftwo} If we sample $y_t$ ergodically from a suffix tree FSM, then the frequency for each finite substring will converge almost surely. In other words the sequence $y_t$ is almost surely ergodic. \end{lemma} \begin{proof} If the suffix tree defines an FSM as we have defined it above, the states of the suffix tree will form an ergodic Markov chain. An ergodic Markov chain is stationary. For any state and finite string of perceptions there is a certain fixed probability of drawing the string in question. The frequency of the string $str$ is $\sum_s Pr(s)Pr(str|s)$ where $Pr(s)$ is the stationary probability of seeing $s$ and $Pr(str|s)$ is the probability of directly seeing exactly $str$ conditioned on being in state $s$. It follows from the law of large numbers that the frequency of any finite string $str$ converges. Another way of understanding this result is that it is implied by the convergence of the frequency of any finite string of states in the state sequence. \qed\end{proof} \begin{proof} {\bf of Proposition \ref{suffix}.} Lemma \ref{sufone} and Lemma \ref{suftwo} together imply the proposition since they say that if we sample from a suffix tree then we almost surely get converging frequencies for all finite substrings and this implies converging transition frequencies for the states from any suffix tree. \qed\end{proof} %-------------------------------% \paradot{Bounded-Memory FSMs} %-------------------------------% We here notice that the reasons that the suffix tree theory above worked actually relate to a larger class, namely a class of FSMs where the internal state is determined by at most a finite number of previous time steps in the history. \begin{definition}[bounded memory FSM] Suppose that there is a constant $\kappa$ such that if we know the last $\kappa+1$ perceptions $y_{t-\kappa},...,y_t$ then the present state $s_t$ is uniquely determined. Then we say that the FSM has memory of at most length $\kappa$ (not counting the current) and that it has bounded memory. \end{definition} \begin{proposition}[ergodicity of FSMs]\label{FSMerg} 1. Consider a sequence $y_t$ whose finite substring frequencies converge (i.e.\ the sequence is ergodic) and an FSM of bounded memory, then the sequence is ergodic with respect to the map defined by the FSM. \\ 2. If we sample a sequence $y_t$ ergodically from an FSM with bounded memory then almost surely $y_t$ is HMM-ergodic and its finite substring frequencies converge. \end{proposition} \begin{proof} The proof works the same way as for suffix tree FSMs. If an FSM has finite memory of length $\kappa$ then there is a suffix tree of that depth with every suffix of full length and every state of the FSM is a subset of the states of that suffix tree. The FSM is a partition of the suffix set into disjoint subsets. Every state transition for the FSM is exactly one of a set of state transitions for the suffix tree states and the frequency of every ordered pair of suffix tree states converge almost surely as before. Therefore, the state transition frequencies for the FSM will almost surely converge. A distribution that is defined using an FSM of bounded memory can also be defined using a suffix tree, so 2. reduces to this case \qed\end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The Main Result For Sequence Prediction}\label{sec:Main} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section we summarize our results in a main theorem. It follows directly from a combination of results in previous sections. They are stated with respect to our main class of maps, namely the class that is defined by bounded-memory FSMs. The generating models that we consider are models that are defined from a map in this class in such a way that the states form an ergodic Markov chain. We refer to this as sampling ergodically from the FSM. Our conclusion is that we will under these circumstances eventually only choose between maps which generate the best possible HMM parameters that can be achieved for the purpose of long-term sequence prediction. The model penalty term will influence the choice between these options towards simpler models. The following theorem guarantees that we will almost surely asymptotically find a correct HMM for the sequence of interest under the assumption that it is possible. \begin{theorem}\label{thm:passive} If we consider a finite class of maps $\Phi_i, i=0,1,...,k$ based on finite state machines of bounded memory and if we sample ergodically from a finite state machine of bounded memory, then there almost surely exist limiting parameters $\t_i$ for all $i$ and there is $N<\infty$ such that for all $n\geq N$ the map $\Phi_i$ selected at time $n\geq N$ by minimizing $\Cost$, generates parameters whose limit is $\t_0$ which is assumed to be the optimal HMM parameters. \end{theorem} \begin{proof} We are going to make use of Proposition \ref{FSMerg} together with Theorem \ref{corgenfinite}. Proposition \ref{FSMerg} shows that our assumptions imply the assumptions of Theorem \ref{corgenfinite} which provides our conclusion. \qed\end{proof} %-------------------------------% \paradot{Extension to countable classes} %-------------------------------% To extend our results from finite to countable classes of maps we need the model complexity penalty to be sufficiently rapidly growing in $n$ and $m$. This is also necessary if we want to be sure that we eventually find a minimal representation of the optimal model that can be achieved by the class of maps. \begin{proposition}[Consistency for countable class]\label{countable} Suppose that we have a countable class of maps $\Phi_i,\ i=0,1,...$ and \begin{enumerate} \item Suppose that our class is such that for every finite $k$, there are at most finitely many maps with at most $k$ states. \item Suppose that $\theta_0$ is an optimal HMM for the sequence $y_t$, that it has $m$ states and that $\theta_0$ is the limit of the parameters generated by $\Phi_0$. Furthermore, suppose that there is finite $N$ such that whenever $n>N$, $\tilde{m}>m$ and $\tilde{\theta}$ is any HMM with $\tilde{m}$ states we have $pen(n,m)-\log P_{\hat{\theta}_0^n}(y_1,...,y_n)< pen(n,\tilde{m})-\log{P_{\tilde{\theta}}(y_1,...,y_n)}$. where $\hat{\theta}_0^n$ are the parameters generated by $\Phi_0$. \end{enumerate} then Theorem \ref{corgenfinite} is true also for this countable class and we will furthermore eventually pick a map with at most $m$ states. \end{proposition} \begin{proof} The idea of the proof is to reduce the countable case to the finite case that we have already proven by using that when $n>N$ we will never pick a $\Phi$ with more than $m$ states and then use the first property to say that the remaining class if finite. This reduction also shows that we will eventually not pick a map with more states than $m$. \qed \end{proof} The first property in the proposition above holds for the class of suffix trees and for the class based on FSMs with bounded memory. The second property, but with the HMM maximum likelihood parameters $\theta(n)$ with $m$ states (while we have ML for a sequence of states and observations) will almost surely hold if the penalty is such that we have strong consistency for the HMM criteria $\theta^*=\arg\max \log{P_\theta(y_1,...,y_n)}-pen(n,m)$. This is studied in many articles, e.g. \cite{GasBou03} where strong consistency is proven for a penalty of the form $\beta(m)\log{n}$ where $\beta$ is a cubic polynomial. Note that in the case without side information (if our map has the properties that $\Phi_0(y_{1:n})$ determine $y_n$ and that $\Phi(y_{n-1})$ and $y_n$ determine $\Phi(y_{1:n})$) the emissions are deterministic and the state sequence generated by any map is determined by the $y$ sequence. This puts us in a simpler situation akin to the Markov order estimation problem \cite{Fin96, Csi00} where it is studied which penalties (e.g.\ BIC) will give us property 2. above. \begin{conjecture} We almost surely have Property 2. from Proposition \ref{countable} for the BIC penalty studied in \cite{Csi00}. \end{conjecture} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Sequence Prediction With Side Information}\label{sec:Side} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Introduction In this section we will broaden our problem to the setting where we have side information available to help in our prediction task. In our problem setting we have two finite sets $\X$ and $\Y$, a sequence $p_n=(x_n,y_n)$ of elements from $\X\times \Y$, and we are interested in predicting the future of the sequence $y_n$. To do this we first want to learn a {\emph {feature map}} $\Phi(p_{1:n})=s_n$. In other words we want our current state to summarize all useful information from both the $x$ and $y$ sequence for the purpose of predicting the future of $y$ only. % modeling y and x. One obvious approach is to predict the future of the entire sequence $p$, i.e. predicting both $x$ and $y$ and then in the end only notice what we find out about $y$. This brings us back to the case we have studied already, since from this point of view there is no side information. A drawback with that approach can be that we create an unnecessarily complicated state representation since we are really only interested in predicting the $y$ sequence. % modeling only y In the case when there is no side information, $s_t=\Phi(y_{1:t})$. An important difference of the case with side information is that the sequence $s_{1:t}$ depends on both $y_{1:t}$ and $x_{1:t}$. Therefore for the latter case, if we would like to consider a distribution for $y$ only, $y_1,...,y_n$ does not determine the state sequence $s_1,...,s_n$: \beqn Pr(y_1,...,y_n|\hat{\t}_n) ~= \sum_{s_{1:n},x_{1:n}} Pr(s_1,...,s_n)Pr(x_1,...,x_n,y_1,...,y_n|s_1,...,s_n,\hat{\t}_n). \eeqn This is expression is of course also true in the absence of side information $x$, but then the sum collapses to one term since there is only one sequence of states $s_{1:n}$ that is compatible with $y_{1:n}$. An alternative to using the $\Cost$ criteria on the $p$ sequence is to only model the $y$ sequence and let \beqn L_n(\Phi) ~=~ -\log{Pr(y_1,...,y_n|\hat{\t}_n)} \eeqn and then define $\Cost$ in exactly the same way as before. This cost function was called $\ICost$ in \cite{Hut09a}. %-------------------------------% %\paradot{ICost} %-------------------------------% \begin{theorem}\label{thm:icost} Theorem \ref{thm:passive} is true for sequence prediction with side information using \beqn \ICost_n(\Phi_i) ~=~ -\log{Pr(y_1,...,y_n|\hat{\t}_n)}+pen(n,S) \eeqn if we define ``sample ergodically'' to refer to the sequence $p_t=(x_t,y_t)$ instead of $y_t$. \end{theorem} \begin{proof} The proofs work exactly as they are written for the case without side information. \qed\end{proof} Note that a map that is optimal for predicting the $y$ sequence can have fewer states than a minimal map that can generate the model of the $p$ sequence. It is interesting to note that the interpretation of this result is not as clear as the case without side information. It guarantees that, given enough history, the chosen $\Phi$ can and will (with the asymptotic parameters) define the correct model for the $y_t$ sequence but the $x_t$ sequence has only played a part in the estimation and we are not guaranteed that we will make use of the extra information if it does not impact the entropy rate. In particular it is true if the information in $x_t$ is only helpful for a finite number of time steps forward. In this case that gain will not affect the entropy rate which is a limit of averages. We have a more conclusive result for the case with side information when we use the first mentioned approach of applying $\Cost$ to the sequence $p$, since we proved consistency in the previous section in the sense of finding the true model when possible. %-------------------------------% %\paradot{OCost} %-------------------------------% If we have injective maps $\Phi$, e.g.\ maps defined by non-empty suffix trees, then we can rewrite $\Cost$ in a form that was used in \cite{Hut09a} also more generally. Therein a cost called \emph{original cost} was defined as follows: \begin{definition}[OCost] \beqn \OCost ~=~ -\log{Pr(s_1,...,s_n)}-\log{Pr(y_1,...,y_n|s_1,...,s_n,\hat{\t}_n)}+pen(n,S). \eeqn \end{definition} % \begin{remark} If $\Phi_i$ is injective and we calculate $\Cost$ in the side information case then $\Cost~=~ \OCost$. \eor\end{remark} If we have no side information both $\OCost$ and $\ICost$ will be the same as $\Cost$ but they may differ when there is side information available. We remarked above that if we consider only injective $\Phi$ (e.g. non-empty suffix tree based maps) then $\OCost$ equals using $\Cost$ on the joint sequence $p_t=(x_t,y_t)$. As noted in \cite{Hut09a} $\OCost$ penalizes having many states more than $\ICost$ does and when considering non-injective $\Phi$ one risks getting a smaller than desired state space. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The Active Case}\label{sec:Active} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this very brief section we will discuss how to map the active case to the previously introduced notions. The active case will be treated in depth in future articles. In the active case \cite{RusNor10,SutBar98} we have an agent that interacts with an environment. The agent perceives observations $o_t$ and real-valued rewards $r_t$ and the agent takes actions $a_t$ from a finite set of possible actions $\cal{A}$ with the goal of receiving high total reward in some sense. We will denote the events that have just occurred when the agent will take an action at time step $t$, i.e.\ $a_{t}$, $o_t$, and $r_t$ by $e_t$. We consider maps based on FSMs (PDFAs) that takes event sequences $e_t$ as input. In the previous section's notation $x_t=(o_t,a_t)$ and $y_t=r_t$ and $p_t=e_t$. We chose this since we are interested in predicting which future rewards will result from actions chosen with the help of the observations. This would give us the possibility of determining which actions will earn the highest rewards. At time $t-1$ the past $e_1,...,e_{t-1}$ determines $s_{t-1}$ and the agent takes an action $a_{t-1}$ and $o_{t}$ and $r_{t}$ are generated according to distributions that only depend on $s_{t-1}$ and $a_{t-1}$. Then we have generated $e_{t}$ and $s_{t}=\psi(s_{t-1},e_{t})$. \begin{definition}\label{def:ergenv} The above describes what we mean when we say that the FSM generates the environment. We say that the FSM generates the environment ergodically, if for any sequence of actions chosen such that the action frequencies for any state converge asymptotically, we will have state transitions and emission frequencies that converge almost surely to an ergodic HMM. \end{definition} \begin{proposition}\label{FSMpr} Suppose that we have an FSM of bounded-memory generating the environment ergodically and the action frequencies for any state converge asymptotically, then we will almost surely generate an ergodic sequence of events and the reward sequence is HMM-ergodic. \end{proposition} \begin{proof} The situation reduces through Definition \ref{def:ergenv} to that of Proposition \ref{FSMerg}. \qed\end{proof} \begin{theorem}\label{thm:active} If we consider a finite class of maps $\Phi_i, i=0,1,...,k$ based on finite state machines of bounded memory and if the environment is generated ergodically by a finite state machine of bounded memory and if the action frequencies for any internal state of the generating finite state machine converge, then there almost surely exist limiting state transition parameters $\t_i$ for all $i$ and there is $N<\infty$ such that for all $n\geq N$ the map $\Phi_i$ selected by minimizing $\ICost$ at time $n\geq N$ generates parameters whose limit is $\t_0$ which is the optimal HMM. \end{theorem} \begin{proof} We combine Proposition \ref{FSMpr} with Theorem \ref{thm:icost}. \qed\end{proof} How to choose the actions to make the implications for reinforcement learning what we want them to be is the subject of ongoing work \cite{Hut09a}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Conclusions}\label{sec:Conc} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Feature Markov Decision Processes were introduced \cite{Hut09a} as a framework for creating generic reinforcement learning agents that can learn to perform well in a large variety of complex environments. It was introduced as a concept without theory or empirical studies. First empirical results are reported in \cite{Mah10}. Here we provide a consistency theory by focusing on the sequence prediction case with and without side information. We briefly discuss the active case where an agent takes actions that may affect the environment. The active case and empirical studies is the subject of ongoing and future work. %-------------------------------% \paradot{Acknowledgement} %-------------------------------% We thank the reviewers for their meticulous reading and valuable feedback and the Australian Research Council for support under grant DP0988049. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Bibliography % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{small} \newcommand{\etalchar}[1]{$^{#1}$} \begin{thebibliography}{ABCD} \bibitem[BP66]{BauPet66} Leonard~E. Baum and Ted Petrie. \newblock Statistical inference for probabilistic functions of {F}inite {S}tate {M}arkov chains. \newblock {\em The Annals of Mathematical Statistics}, 37(6):1554--1563, 1966. \bibitem[CMR05]{CapMouRyd05} Olivier Capp\'{e}, Eric Moulines, and Tobias Ryden. \newblock {\em Inference in Hidden {M}arkov Models (Springer Series in Statistics)}. \newblock Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005. \bibitem[CS00]{Csi00} Imre Csisz‡r and Paul~C. Shields. \newblock The consistency of the bic markov order estimator., 2000. \bibitem[EM02]{EphMer02} Y.~Ephraim and N.~Merhav. \newblock Hidden {M}arkov processes. \newblock {\em IEEE Transactions on Information Theory}, 48(6):1518--1569, 2002. \bibitem[FLN96]{Fin96} L.~Finesso, C.~Liu, and P.~Narayan. \newblock The optimal error exponent for markov order estimation. \newblock {\em IEEE Trans. Inform. Theory}, 42:1488Đ1497, 1996. \bibitem[GB03]{GasBou03} Elisabeth Gassiat and St{\'e}phane Boucheron. \newblock Optimal error exponents in hidden {M}arkov models order estimation. \newblock {\em IEEE Transactions on Information Theory}, 49(4):964--980, 2003. \bibitem[Hut09]{Hut09a} Marcus Hutter. \newblock Feature reinforcement learning: Part {I}: Unstructured {MDP}s. \newblock {\em Journal of Artificial General Intelligence}, 1:3--24, 2009. \bibitem[Mah10]{Mah10} M.~M. Mahmud. \newblock Constructing states for reinforcement learning. \newblock In {\em The 27:th International Conference on Machine Learning (ICML'10)}, 2010. \bibitem[McC96]{McC96} Andrew~Kachites McCallum. \newblock {\em Reinforcement learning with selective perception and hidden state}. \newblock PhD thesis, The University of Rochester, 1996. \bibitem[Pet69]{Pet69} T.~Petrie. \newblock Probabilistic functions of {F}inite {S}tate {M}arkov chains. \newblock {\em The Annals of Mathematical Statistics}, 40(1):97--115, 1969. \bibitem[Ris83]{Ris83} Jorma Rissanen. \newblock A universal data compression system. \newblock {\em IEEE Transactions on Information Theory}, 29(5):656--663, 1983. \bibitem[Ris86]{Ris86} Jorma Rissanen. \newblock Complexity of strings in the class of {M}arkov sources. \newblock {\em IEEE Transactions on Information Theory}, 32(4):526--532, 1986. \bibitem[RN10]{RusNor10} Stuart Russell and Peter Norvig. \newblock {\em Artificial Intelligence: A Modern Approach}. \newblock Prentice Hall, 3 edition, 2010. \bibitem[SB98]{SutBar98} Richard~S. Sutton and Andrew~G. Barto. \newblock {\em Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning)}. \newblock The MIT Press, March 1998. \bibitem[Sin96]{Sin96} Yoram Singer. \newblock Adaptive mixtures of probabilistic transducers. \newblock {\em Neural Computation}, 9:1711--1733, 1996. \bibitem[VTdlH{\etalchar{+}}5a]{VidThoHig05a} Enrique Vidal, Franck Thollard, Colin de~la Higuera, Francisco Casacuberta, and Rafael~C. Carrasco. \newblock Probabilistic finite-state machines -- {Part I}. \newblock {\em IEEE Transactions on Pattern Analysis and Machine Intelligence}, 27(7):1013--1025, 2005a. \end{thebibliography} \end{small} \end{document} %----------------------End-of-PhiMP.tex-----------------------%