\documentclass[twoside,11pt]{article}

\usepackage{jmlr2e}
\usepackage{latexsym}
%\usepackage[dvips]{graphics}
\usepackage{graphicx}
\usepackage{psfrag}
\usepackage[ruled,vlined,titlenotnumbered,]{algorithm2e}
\special{papersize=8.5in,11in}
 % $Id: jmlr.tex,v 1.22 2004/03/14 21:30:09 clark Exp $
\usepackage{amsmath}


\newcommand{\marginnote}[1] { 
  \marginpar{\setlength{\baselineskip}{2pt} 
             \begin{scriptsize} #1 \end{scriptsize}} 
} 

%
%  Replace this with citep
% \newcommand{\pcite}[1]{(\cite{#1}\,)}
\newcommand{\warning}{**~{\Large$\bigtriangleup$}\hspace*{-.8em}!~** ~~~}
\jmlrheading{5}{2004}{473-497}{10/03; Revised 3/04}{5/04}{Alexander Clark and Franck Thollard}

\ShortHeadings{Pac-Learnability of PDFAs}{Clark and Thollard}
\firstpageno{473}
\DeclareSymbolFont{AMSb}{U}{msb}{m}{n}
\DeclareMathSymbol{\N}{\mathbin}{AMSb}{"4E}
\DeclareMathSymbol{\Z}{\mathbin}{AMSb}{"5A}
\DeclareMathSymbol{\R}{\mathbin}{AMSb}{"52}
\DeclareMathSymbol{\Q}{\mathbin}{AMSb}{"51}
%\DeclareMathSymbol{\I}{\mathbin}{AMSb}{"49}
\DeclareMathSymbol{\C}{\mathbin}{AMSb}{"43}
\DeclareMathSymbol{\B}{\mathbin}{AMSb}{"42}
%\addtolength{\textwidth}{1em}
%\addtolength{\textheight}{1em}


\begin{document}
\title{PAC-learnability of Probabilistic Deterministic \\Finite State Automata \\ 
%% \small{  
%%  $Revision: 1.22 $
%% }
}

\author{\name Alexander Clark  
\email{asc@aclark.demon.co.uk} \\
\addr 
     ISSCO/TIM, Universit\'e de Gen\`eve 40 \\
             Bvd du Pont d'Arve CH-1211 \\
Gen\`eve 4, Switzerland \\
\AND Franck Thollard \email{thollard@univ-st-etienne.fr} \\
\addr EURISE, Universit\'e Jean Monnet, 23 \\ Rue du Docteur Paul Michelon\\ 42023 Saint-Etienne C\'edex 2, France \\
}

\editor{Dana Ron}

%\newtheorem{definition}{Definition}
%\newtheorem{lemma}{Lemma}



\maketitle

\begin{abstract}
We study the learnability of Probabilistic Deterministic Finite State Automata  under a modified PAC-learning criterion. 
We argue that it is
necessary to add additional parameters to the sample complexity polynomial, namely 
a bound on the expected length of strings generated from any state, and a bound on the distinguishability between states.
With this, we demonstrate that the class of PDFAs is PAC-learnable using a variant of a standard state-merging algorithm 
and the Kullback-Leibler divergence as error function.
\end{abstract}

\begin{keywords}
Grammatical inference, PAC-learnability, finite state automata, regular languages.
\end{keywords}

\section{Introduction}

Probabilistic Deterministic Finite State Automata (PDFAs) are widely used in a number of different
fields, including Natural Language Processing (NLP), Speech Recognition
\citep{MOHRI97} and  Bio-informatics \citep{durbin99}.
The deterministic property here means that at any point in producing  a string they are in a single state, which allows for
very efficient implementations and accounts for much of their appeal. 
Efficient  algorithms for inducing the models 
from data are thus important. We are interested primarily in algorithms which learn from positive
data under stochastic presentation, where the data are drawn from the distribution defined by the
target automaton. 
In addition we are concerned with automata that  generate finite strings of unbounded length.  This is necessary in many problem classes, 
particularly in NLP, where the sequences can be words or  sentences with particular global structures. 
 
Here we provide a proof that a particular algorithm  Probably Approximately Correctly (PAC) learns the class of PDFAs, 
using the Kullback-Leibler divergence as the error function,
when we allow the algorithm
to have amounts of data polynomial in three quantities associated with the complexity of the problem: 
first, the number of states of the target, 
secondly the 
distinguishability of the automata --- a lower bound on the $L_\infty$ norm between the suffix
distributions of any pair of states of the target --- 
and thirdly a bound on the expected length of strings generated from \emph{any state} of the target, a quantity that can be used to bound the variance of the length of the strings generated by the target.
The algorithm uses polynomial amounts of computation.
We will motivate these additional parameters to the sample complexity polynomial with reference to
specific counter-examples. 


 The algorithm we present here is a state-merging algorithm of a fairly standard type 
 \citep{CARRASCO94,RON95,THOLLARD00,kd_sgiwmt2002}. The convergence properties of this class  
 of algorithm have been studied before, but proofs have been restricted either to  the subclass of
 acyclic automata \citep{RON95, RON98}, or using only the identification in the limit  with probability one
 paradigm \citep{CDLH96,CARRASCO99,CDLH00}, which is generally considered less interesting as a guide
 to their practical usefulness.  
 We wish to note here that we shall follow closely the notation and techniques of \cite{RON95}. Unfortunately, our
 technique is too different to merely present modifications to their algorithm,
 but in points we shall adopt wholesale their methods of proof. We shall also use notation as close as possible to the notation used in their paper.
%Where sections of this paper are particularly close, we shall note this in the relevant sections.


\subsection{Learning Paradigm}

%% We shall first define the learning paradigm we are interested in before defining the PDFAs
%% formally.  For the moment we can take them 
%% as a class of stochastic languages over a finite alphabet.
We are interested in learning in the Probably Approximately Correct (PAC) framework
\citep{VALIANT84}, more specifically in cases  where the amount of data and the amount of
computation required can be bounded by polynomials in the various parameters, including some
characterisation of the complexity of the target.  
 
We will use, as is standard, the Kullback-Leibler Divergence (KLD) \citep{cover-91} between the target
and the hypothesis  to measure the error. Intuitively, this is the hardest measure to use since it
is unbounded, and bounds  other plausible distance measures (quadratic, variational etc.)
\citep{cover-91,ABE01}.  

The problem class  $\mathcal{C}$  is a  subset of the set of all distributions over $\Sigma^*$,
where $\Sigma$ is a finite alphabet. 
The algorithm is presented with a sequence $S_m$ of $m$ strings  from $\Sigma^*$
that are drawn identically and independently from the target distribution $c$. Such a sequence is called a sample. 
Given this sample, the algorithm returns a hypothesis $H(S_m)$.

\begin{definition}[KL-PAC]
Given a class of stochastic languages  or distributions $\mathcal{C}$ over $\Sigma^*$, an algorithm A
   \emph{KL-Probably Approximately Correctly (KL-PAC)-learns}  $\mathcal{C}$ if there is a 
polynomial $q$ such that for all $c$ in $\mathcal{C}$,  all $\epsilon > 0$ and $\delta >0$, 
$A$ is given a sample $S_m$ and produces a hypothesis $H$, such that  $Pr[D(c||H)  > \epsilon] <
\delta$ whenever $m >  q(1/\epsilon, 1/\delta, |c|)$, where $|c|$ is some measure of the
complexity of the target, with running time bounded by a polynomial  in $m$ plus the total length of  the strings in $S_m$.
\end{definition}

Note here two points: first, the examples are drawn from the target distribution
so this approach is very different from the normal distribution-free approach. Indeed
here we are interested in learning the distribution itself, so the approach is closely related to the
traditional problems of density estimation,  and also to the field of  language modelling in speech recognition and NLP.
It can also be viewed as a way of learning languages from positive samples under a restricted class of distributions,
which  is in line with other research  which has found that the requirement to learn under all distributions is
too stringent.
 Secondly, we are concerned with distributions 
over $\Sigma^*$ not over $\Sigma^n$, for some fixed $n$, which form a finite set, which distinguishes us
from \cite{RON95}. Note that though \cite{RON95} study distributions over
$\Sigma^*$ since they study acyclic automata of bounded size and depth,  the distributions
are, as a result,  limited to distributions over $\Sigma^n$. 


\subsection{Negative Results}

For PAC-learning stochastic languages there 
are some negative results  that place quite strict limits on how far we can hope to go.
First, let us recall that the stochastic languages generated by PDFAs are a proper subclass of the class of all stochastic regular languages.
The results in 
\cite{ABE92} establish that robust learning of general
(non-deterministic) finite state automata is hard.  This strongly suggests that we cannot hope to learn all of this class, though
the  class of Probabilistic Residual Finite State Automata \citep{esposito02} is a
promising intermediate class between stochastic deterministic regular languages and stochastic
regular languages. 
Secondly, \cite{KEARNS94} show that under certain cryptographic assumptions it is impossible to
efficiently learn PDFAs defining  distributions over two letters.  They define a correspondence between 
  noisy parity functions and a certain subclass of automata. Since the complexity results they rely
  upon are  generally considered  to be true, this establishes that the class of all PDFAs is not
  PAC-learnable using polynomial computation. 
These results apply to distributions over $\Sigma^n$ for some fixed $n$, and thus also to our more general case of distributions over $\Sigma^*$.
However, \cite{RON95} show that if one restricts one's
  attention to a class of automata that have a certain distinguishability  criterion between the
  states, that we shall define later, it is possible to PAC-learn acyclic PDFAs.  Formally, there are
  two ways to define this: either one defines a subclass of the problem class where the
  distinguishability is bounded by some inverse polynomial of the number of states or we allow the sample
  complexity polynomial to have another parameter.  
We follow \cite{RON95} in using the latter
  approach. 

However the extension from acyclic PDFAs to all PDFAs produces an additional problem.
As we shall see, the KLD between the target and  the hypothesis 
can be decomposed into terms based on the contributions of particular
states. The contribution of each state is related to the expected number of times the target
automaton visits the state and not the probability that the target automaton will visit this state. 
%% I don't understand the next sentence. Can you make it more simpler ? 
%Thus, states which the automaton reaches with low probability,  but that when it does reach them, it reaches them many times
%can cause a  substantial increase in the KLD between the target and the
%hypothesis. 
%%% 
Therefore there is a potential problem with states that are both rare (have a low probability of being reached) and yet have a high expected number of visits, a combination of
properties that can happen, for example, when a state is very rare but has a transition to itself with probability very close to one.
If the state is very rare we cannot guarantee that our sample will contain any strings which visit the state, but yet this state can make a non-negligible contribution to the error.

In particular, as we show in Appendix~A, it is possible to construct families of
automata, with bounded expected length,  that will with high probability produce the same samples, but where
some targets must have large KLD from any hypothesis. We refer the reader to the appendix for
further details. 
This is only a concern with the use of the KLD as error function; with other 
distance measures the error on a set of strings with low aggregate probability is also low.
In particular with the variation distance, while it is straightforward to prove a similar result with a bound on
the overall expected length, we conjecture that it is also possible with no length bound at all -- i.e. with a sample complexity 
that depends only on the number of states, the distinguishability and the alphabet size.



Accordingly, we argue that, in the case of learning with the KLD, it is necessary to accept an upper bound on the expected length of the
strings from any state of the  target automaton, or a bound on the expected length of strings  from
the start state and a bound on the variance.  
It also seems reasonable that in most real-world applications of the algorithm, the expectation and
variance of the length will be close to the mean observed length and sample variance. 
% No





\subsection{Positive Results}

\cite{CARRASCO99} proposed  a proof of the identification in the limit with
probability one of the  structure of the  automaton. In \cite{CDLH00}, the proof of the
identification of the probabilities was added achieving the complete identification of the class of
the PDFA with rational probabilities. 
With regard to the more interesting PAC-learnability criterion with respect to the KLD (KL-PAC),
Ron et al.~proposed an algorithm that can KL-PAC-learn the class of distinguishable acyclic
automata. The distinguishability is a guarantee that the distributions generated from any state differ by at least $\mu$
in the $L_{\infty}$ norm.  This is sufficent to immunise the algorithm against the counterexample discussed by
\cite{KEARNS94}. 

Our aim is to extend the work of \cite{RON95} to the full class of PDFAs. This requires us to deal with cycles, and with the
ensuing problems caused by allowing strings of unbounded length, since with acyclic automata a bound on the number
of states is also a bound on the expected length. 
These are of three types: first, the support of the distribution can be infinite, which rules out the direct application of Hoeffding bounds at a particular point in the proof; secondly, the automaton can be in a particular state more than once in the generation of a particular string, which requires a different decomposition of the KLD, and thirdly deriving the bound on the KLD requires slightly different constraints.  
Additionally, we simplify the algorithm somewhat by drawing new samples at each step of the algorithm, which avoids the use of ``reference classes'' in \cite{RON95}, which are necessary to ensure the independence of different samples.



The article is organized as follow: we first start with the definitions and notations we will use (Section~\ref{section:prelim}).
The algorithm is then presented in Section~\ref{sec:algo} and  its correctness   is
proved in Section~\ref{sec:algo_anal}. We then conclude with a discussion of the relevance of this result. The
reader will find on Page~\pageref{tbl:aide} a glossary for the notation.  


\section{Preliminaries}
\label{section:prelim}
We start by defining some basic notation regarding languages,
distributions over languages and finite state automata of the type we
study in this paper.

%In this section we put some basic and fairly standard definitions.

\subsection{Languages}

We have a finite alphabet $\Sigma$, and $\Sigma^*$ is the free monoid generated by $\Sigma$, i.e. the set of all words with letters from $\Sigma$, with $\lambda$  the empty string (identity). 
For $s \in \Sigma^*$ we define $|s|$ to be the length of
$s$. The subset of $\Sigma^*$ of strings of length $d$ is denoted by $\Sigma^d$.
A distribution or stochastic language $D$ over $\Sigma^*$ is a function $D: \Sigma^* \rightarrow [0,1]$ such that
$\sum_{s \in \Sigma^*} D(s) = 1$. 
The \emph{Kullback-Leibler Divergence} (KLD) is denoted by 
$D_{KL}(D_1||D_2)$ and defined as

\begin{equation}
D_{KL}(D_1||D_2) = \sum_s D_1(s) \log \left( \frac{D_1(s)}{D_2(s)} \right).
\end{equation}
The $L_{\infty}$ norm between two distributions is defined as
\begin{equation*}
 L_{\infty}(D_1, D_2) =  \max_{s \in \Sigma^*} | D_1(s) - D_2(s)|.
\end{equation*}
We will use $\sigma$ for letters and $s$ for strings.


\label{multiset}
If $S$ is a multiset of strings from $\Sigma^*$  for any $s \in \Sigma^*$
we write 
$S(s)$ for the multiplicity of $s$ in $S$ and define 
$|S| = \sum_{s \in \Sigma^*} S(s)$, and for every $\sigma
 \in \Sigma$ define $S(\sigma) =  \sum_{s \in \Sigma^*} S(\sigma s)$.
We also write $S(\zeta) = S(\lambda)$.
We will write $\hat{S}$ for the empirical distribution of a non-empty multiset $S$ which gives to the string
$s$ the probability $S(s)/|S|$.
This notation is slightly ambiguous for strings of length one; we will rely on the use of lower-case Greek letters to signify elements
of $\Sigma$ to resolve this ambiguity. 


\subsection{PDFA}

A probabilistic deterministic finite state automaton is a mathematical object that stochastically generates strings of symbols. It has a finite number of states one of which is a distinguished start state. 
Parsing or generating  starts in the start state, and at any given moment makes a transition with a certain probability
to another state and emits a symbol. We have a particular symbol and state which correspond to finishing.  \\

\begin{definition}
A PDFA $A$ is a tuple $(Q, \Sigma,  q_0, q_f,  \zeta, \tau, \gamma)$ , where 
\begin{itemize}
\item  $Q$ is a finite set of states,
\item  $\Sigma$ is the alphabet, a finite set of symbols,
\item   $q_0 \in Q$ is the single initial state, 
\item  $q_f \not \in Q$ is the final state, 
\item  $\zeta \not \in \Sigma$ is the final symbol, 
\item  $\tau: Q \times \Sigma \cup \{ \zeta \} \rightarrow Q \cup \{ q_f \}$ is the transition function and
\item  $\gamma:Q \times \Sigma \cup \{ \zeta \}\rightarrow [0,1]$ is the next symbol probability function. $\gamma(q,\sigma)
  =0$ when  $\tau(q,\sigma)$ is not defined. 
\end{itemize}
\end{definition}


We will sometimes refer to automata by the set of states.
All transitions that emit $\zeta$ go to the final state. In the following $\tau$ and $\gamma$ will be extended to
strings recursively as follows:
\begin{eqnarray*}
 \tau(q,\sigma_1 \sigma_2 \dots \sigma_k) &=& \tau(\tau(q,\sigma_1), \sigma_2 \dots \sigma_k), \\
 \gamma(q,\sigma_1 \sigma_2 \dots \sigma_k) &=& \gamma(q,\sigma_1) \times \gamma(\tau(q,\sigma_1), \sigma_2 \dots \sigma_k).
 \end{eqnarray*}
Also we define $\tau(q, \lambda) = q$ and $\gamma(q,\lambda) = 1$.
 If $\tau(q_0, s) = q$ we say that $s$ \emph{reaches} $q$.


 The sum of the output probabilities  from each states must be one, so for all $q \in Q$,
 \begin{equation*}
 \sum_{\sigma \in \Sigma \cup \{\zeta\}} \gamma(q, \sigma) = 1.
 \end{equation*}
Assuming further that there is a non-zero probability of reaching the
final state from each state, i.e.
\begin{equation*}
  \forall q \in Q \, \, \exists s \in \Sigma^* : \tau(q,s\zeta) = q_f \wedge \gamma(q,s\zeta) > 0,
 \end{equation*}
the PDFA then defines a probability  distribution over $\Sigma^*$, where the probability of 
generating a string $s \in \Sigma^*$ is  

\begin{equation}
\label{eqn:pas}
P^A(s) = \gamma(q_0, s \zeta).
\end{equation}

We will also use    $P^A_q(s) = \gamma(q, s \zeta)$ which we call the suffix distribution of the state $q$. 
We will  omit the automaton symbol when there is no risk of ambiguity.
Note that $\gamma(q_0, s)$ where $s \in \Sigma^*$ is the prefix probability of the string $s$,
i.e. the probability that the  automaton will generate a string that \emph{starts} with $s$.  


%We also follow \cite{RON95} and define
\begin{definition}[Distinguishability]
For $\mu > 0$ two states $q_1,q_2 \in Q$ are $\mu$-distinguishable if there exists a string $s$ such that 
$|\gamma(q_1,s \zeta) - \gamma(q_2, s \zeta)| \geq \mu$. A PDFA $A$ is $\mu$-distinguishable if every pair of states in it is $\mu$-distinguishable.
\end{definition}
Note that any PDFA has an equivalent form in which indistinguishable states have been merged, and thus $\mu>0$.



\section{Algorithm \label{sec:algo}}


% FIX bad page reference
We will now describe the algorithm we use here to learn PDFAs. It is formally described in pseudocode starting at Page~\pageref{tbl:aide}.




%% First, to ensure that relevant samples are independent, so that we can bound the probability of atypical samples 
%% in a standard way. To do this, we resample -- after each step of the algorithm we draw a fresh sample.  This avoids 
%% some of the complicated technical machinery of \cite{RON95} especially the idea of ``reference classes''. 





%% The algorithm incrementally constructs a graph that 
%%  will, with high probability, be isomorphic to   subgraph of the
%% target automaton. This graph is  a directed graph with the edges or arcs labelled with symbols from the alphabet. Each
%% node has associated with it a multiset of strings that are drawn from the suffix distribution of that node. We start with 
%% a single node and no arcs, which corresponds to the start state of the target automaton.

%% At each step we sample $N$ strings from the target distribution. This re-sampling ensures the independence of all of the samples, and allows us to apply bounds in a straightforward way. 
%% For each node $v$ in the graph and letter $\sigma$ in the
%% alphabet, we build a set of candidate nodes. 
%% This set will contain nodes that are reached from  $v$ \emph{via} a single transition labelled with $\sigma$
%% in the graph and for which the multiset of strings is sufficiently large in order 
%% to guarantee that, with high
%% probability, the candidate nodes will be good representatives of the sample distribution of the corresponding state in
%% the automaton.  
%% For each candidate node, we then try to find a similar node in the graph. If such a node exists, 
%% we add an edge, labelled by $\sigma$, from node $v$ to the node found, else we build a new node.  

%% This building of the structure ends when no nodes adjacent to the graph have sufficiently large a multiset; 
%% intuitively, when nearly all of the strings we sample do not exit the graph, 
%% at which point we can be confident we have all of the states with significant weight.

%% We then produce a PDFA from the graph. This consists of two steps: 
%% \begin{enumerate}
%% \item If the graph is not complete --- i.e. if there
%% is at least one  node and a letter of the alphabet such that the node does not have an edge leaving it labelled with that letter --
%% we complete by adding an additional state, together with all possible arcs leading to that state. This ensures that the automaton will accept/generate all strings.
%% \item We estimate the transition probabilities using a simple smoothed  maximum likelihood estimate.  
%% \end{enumerate}

%% We now provide  a more formal description of the algorithm. 


We are given the following parameters
\begin{itemize}
\item an alphabet $\Sigma$, or strictly speaking an upper bound on the size of the alphabet,
\item an upper bound on the expected length of strings generated from any state of the target $L$,
\item an upper bound on the number of states of the target $n$,
\item a lower bound $\mu$ for the distinguishability,
\item a confidence $\delta$, and 
\item a precision $\epsilon$.
\end{itemize}

We start by computing the following quantities. First, we compute $m_0$,  which is a threshold on the size of a multiset.
When we have a multiset whose size is larger than $m_0$, which will be a sample drawn
from a particular distribution, 
 then with high probability the empirical estimates derived from that sample will be 
sufficiently close to the true values.
Secondly, we compute $N$, which is the size of the sample we draw at each step of the algorithm.
Finally,  we compute $\gamma_{min}$, which is a small smoothing constant. 
These are defined as follows, using some intermediate variables to simplify the expressions slightly:


\begin{equation}
\gamma_{min} = \frac{\epsilon}{4(L+1)(|\Sigma| + 1)},
\end{equation}

\begin{equation}
\label{eqn:deltaprime}
\delta' = \frac{ \delta}{2(n |\Sigma| + 2)},
\end{equation}

\begin{equation}
\epsilon_1 =  \frac{\epsilon^2}{16 ( |\Sigma| + 1)(L+1)^2},
\end{equation}


\begin{equation}
\label{eqn:mzero}
m_0 = \max \left( 
\frac{ 8}{\mu^2} \log \left( \frac{96 n |\Sigma|}{\delta' \mu} \right) 
,
\frac{1}{2 \epsilon_1^2}\log \left( \frac{12 n |\Sigma| |\Sigma+1|}{\delta'} \right)
 \right),
\end{equation}


\begin{equation}
\label{eqn:ethree}
\epsilon_3 = \frac{\epsilon}{2 (n+1) \log (4(L+1)(|\Sigma|+ 1) / \epsilon)},
\end{equation}

\begin{equation}
\label{eqn:N}
N 
=
\frac{4n|\Sigma|L^2(L+1)^3} {\epsilon_3^2}
\max \left(
2 n |\Sigma| m_0
,
4  \log \frac{1}{\delta'}
\right).
\end{equation}






%
%  Start pseudocode
%
%







%%
%% What is it if not a data structure ?
%% 
The basic data structure of the algorithm represents  a digraph $G=(V,E)$ with labelled edges, $V$ being a set of vertices (or nodes) and $E
\subseteq V \times \Sigma  \times V$ a set of edges. The graph holds our current hypothesis about the
structure of the target automaton. We have a particular vertex in the graph, $v_0 \in V$ that corresponds to the
initial state of the hypothesis. Each arc in the graph is labelled with a letter from the alphabet, and there is at most one edge labelled with a particular letter leading from any node.
Indeed, the graph can be thought of as a (non-probabilistic) deterministic finite automaton, but we will not use this terminology to avoid confusion. 
We will use $\tau_G(v, \sigma)$ as a transition function in this graph to refer to the node reached by the arc labelled with $\sigma$ that leads from $v$, if such a node exists,
and we will extend it to strings as above.
 At each node $v \in
V$ we associate a multiset of strings $S_v$ that represents the suffix distribution of the state that the node
represents.  At any given moment in the algorithm we wish the graph to be isomorphic to a subgraph
of the target automaton. 
% Obviously sometimes with low probability we will have misleading samples that will make this not be the case. 
Initially we have a single node that represents the initial state of the target automaton, together
with a multiset that is just a sample of strings from the automaton. 





At each step we are given a multiset of $N$ data points (i.e. strings from $\Sigma^*$) generated independently by a target PDFA
$T$. For each node $u$ in the graph, and each letter $\sigma$  in the alphabet that does not yet label an arc out of
$u$, we hypothesize a candidate node. We can refer to this node by the pair $(u,\sigma)$. The first step is to compute
the multiset of suffixes of that node.  For each string in the sample, we trace its path through the graph, deleting
symbols from the front of the string as we proceed, until we arrive at the node $u$, or the string is empty, in which case we discard it.
 If the string then starts with
$\sigma$ we delete this letter  and then add the resulting string to the multiset associated with $(u, \sigma)$. Intuitively, this should be a
sample from the suffix distribution of the relevant state.  More formally, for any input string $s$, if 
$\tau_G(v_0, s)$ is defined then we discard the string. Otherwise we take the longest prefix $r$ such that
there is a node $u$ such that $\tau_G(v_0, r) = u$ and $s = r \sigma t$ and add the string $t$ to the multiset of the candidate node $(u, \sigma)$.
%Practically this would be stored as some form of character trie. 
If this
multiset is sufficiently large (at least $m_0$),  
then we compare it with each of the nodes in the graph. 
The comparison operator
computes the $L_{\infty}$-norm between  the empirical distributions defined by the multisets.
%(i.e. the largest difference
%in empirical probability between the suffixes of all the multisets that go through the states). 
 When we first add a node to  the graph we keep with it the multiset of strings it has at that step, 
and it remains with this multiset for the rest of the algorithm.
% This
%avoids complications with rare states being noticed and then failing to have sufficiently large counts later on.  
% Insert a bit of Francks piece
%Since the empirical distributions have finite support, this computation can be performed efficiently using character tries. 
%Indeed, we do not have to compute the $L_{\infty}$-norm
%exactly since we are only interested in finding out if it exceeds a threshold value or not.  Thus there are a number of alternative algorithms that might be more efficient depending on the relative magnitudes of $n$, $|\Sigma|$ and $1/\mu$.

\begin{definition}[Candidate node]
%\begin{definition}[Candidate node / $m_0$-candidate node]
 A candidate node is a pair $(u, \sigma)$ 
where $u$ is a node in the graph and $\sigma \in \Sigma$
where  $\tau_G(u,\sigma)$ is undefined. %that $u$  does not already have an arc labelled with $\sigma$ going from it.
It will have an associated multiset $ S_{u,\sigma}$.
A candidate node $(u, \sigma)$ and a node $v$ in a hypothesis graph $G$ are similar if and only
  if, for all strings $s \in \Sigma^*$, 
$| S_{u,\sigma}(s)/|S_{u,\sigma}| - S_v(s)/|S_v| |  \leq \mu/2$, i.e. if and only if $L_{\infty}(\hat{S}_{u,\sigma},\hat{S_v})\leq \mu/2$.
%A candidate node  $(u, \sigma)$ such that $|S_{u,\sigma}| > m_0$ is a  $m_0$-candidate node.
\end{definition}

We will later see that the value of $\mu/2$, 
given that any two states in the target are at least $\mu$ apart in the $L_{\infty}$-norm,
allows us to ensure that the nodes are similar if and only if they are representatives of the same state.
We will define this notion of representation more precisely below.
If the candidate node $(u, \sigma)$ is similar to one of the nodes in the graph, say $v$ then we add an arc labelled
with $\sigma$ from $u$ to $v$. If it is not similar to any node, then we create a new node in the graph, and add an
arc labelled with $\sigma$ from $u$ to the new node. 
We attach the multiset to it at this point. 
We then delete all of the candidate nodes, sample some more data and
continue the process, until we draw a sample where no candidate node has sufficiently large a multiset.   

\paragraph{Completing the Graph}
 If the graph is incomplete, i.e. if there are strings not accepted by the graph,  we add a new node called the
 ground node which  represents all the low frequency states. We then complete the graph by adding all possible 
 arcs  from all states leading  to the ground node, including from the ground node to itself. 
Since the hypothesis automaton must accept every string, every state must  have an arc leading out of it for each letter in the alphabet. 
We then define for each node in the
 graph a state in the automaton. We add a final state  $\hat{q}_f$, together with a transition labelled with $\zeta$
 from each state to  $\hat{q}_f$. The transition function $\tau$ is defined by the structure of this graph.

\paragraph{Estimating Probabilities}
 The  transition probabilities are then
 estimated using a simple additive smoothing scheme (identical to that used by Ron et al., 1995).
 % manual citation to avoid duplicate brackets.
 For a state $u$,  
 $\sigma \in \Sigma \cup \{\zeta\}$,    
\begin{equation}
\label{eqn:gammahat}
\hat{\gamma}(\hat{q},\sigma) = (S_u(\sigma)/|S_u|)\times (1 - (|\Sigma|+1)\gamma_{min}) +  \gamma_{min}.
\end{equation} 
This is also used for the ground node where of course the multiset is empty.
















\section{Analysis of the Algorithm \label{sec:algo_anal}}


We now proceed to a proof that this algorithm will learn the class of PDFAs. 
We first state our main result.

\begin{theorem}
For every PDFA $A$ with $n$ states, with distinguishability $\mu > 0$, such that the expected length of the string generated from every state is less than $L$,
for every $\delta >0$ and $\epsilon > 0$, Algorithm LearnPDFA outputs a  hypothesis PDFA $\hat{A}$, such that with probability greater than $1- \delta$,
$D_{KL}(A, \hat{A}) < \epsilon$.
\end{theorem}



%% We will now prove that the algorithm defined above will KL-PAC-learn the target class. First, we need to prove
%%  that if the algorithm makes no important mistakes,  the  divergence between the target
%% and our hypothesis will be small, and secondly that the probability of a serious mistake can be
%% guaranteed to be low. 


%%
%% Start high level description of proof.
%%

We start by giving a high-level overview of our proof. 
In order to bound the KLD we will use a decomposition of the KLD between two automata presented in \cite{CARRASCO97}. 
This requires us to define various expectations relating the number of times that the two automata are in various states.

 \begin{itemize}
 \item We  define the notion of a good sample -- this means that certain quantities are close to
   their expected values. We  show that a sample is likely to be good if it is large
   enough. 
 \item We show that if all of the samples we draw are good, then at each step the hypothesis graph will be isomorphic to a subgraph of the target.
 \item We show that when we stop drawing samples, there will  be in the hypothesis graph a state representing each frequent state in the target. In addition we  show that all frequent transitions will also have a representative edge in the graph.
 \item We  show that the estimates of all the transition probabilities will be close to the target values.
 \item Using these bounds we  derive a bound for  the KLD between the target and the hypothesis. 
 \end{itemize}




We shall use a number of quantities calculated from the parameters input to the algorithm to bound the various quantities we are estimating. 
Table~\ref{tbl:aide} summarises these.

\begin{table}
\begin{tabular}{lll}
Symbol   & Description & Definition  \\
\hline
\hline
$\epsilon$ & Precision &   input  \\
$\delta$ & Confidence  & input \\
$L$ & Bound on the expected length of strings & input\\
$\mu$ & Distinguishability of states & input \\
$n$ & Bound on the number of states of the target automaton & input\\
\hline 
$\Phi$  & Function from states of the  target to  nodes in graph & Definition~\ref{def:phi} \\
$W_d(q)$ & Probability to reach state $q$ after $d$ letters & Equation~\ref{eqn:wdq}\\
$W(q)$   & Expected number of times state $q$ is reached &  Equation~\ref{eqn:wq}\\
$W_d(q,\hat{q})$ & Expected number of times a path is  in  $q$ and $\hat{q}$ & Equation~\ref{eqn:wdqq}\\ 
$P(q)$   & Probability that a state $q$ is reached & Equation~\ref{eqn:pq}\\\
$P(s), P^A(s)$  & Probability that a string is generated & Equation~\ref{eqn:pas}\\
$P_q(s)$ & Probability that a string is generated from $q$ & $\gamma(q, s \zeta)$ \\
$S_u$ & Multiset of node $u$  & Page~\pageref{multiset}\\
$\hat{S_u}$ & Empirical distribution of multiset of node $u$  & Page~\pageref{multiset}\\
$|S_u|$ & Size of multiset of node $u$ & Page~\pageref{multiset} \\
$S_u(s)$ & Count of string $s$ in multiset & Page~\pageref{multiset}\\
$S_u(\sigma)$ & Count of letter $\sigma$ in multiset & Page~\pageref{multiset} \\
\hline
$N$ & One step sample size & Equations~\ref{eqn:N} \\
$m_0$ & Threshold for size of multiset of candidate node  & Equation~\ref{eqn:mzero}\\
$\gamma_{min}$ & Smoothing constant for transition probabilities &  Equation~\ref{eqn:gammahat}  \\
$\epsilon_1$  & Bound on  transition counts&  $  \epsilon_4^2/4 ( |\Sigma| + 1)$ \\
$\epsilon_2$ & Threshold for weight of frequent states & $\epsilon_3/2nL(L+1) $ \\
$\epsilon_3$ & Bound on difference between weights in target and hypothesis  & Equation~\ref{eqn:ethree} \\
$\epsilon_4$ & Bound on smoothed estimates of transition probabilities &  $\epsilon/2(L+1)$\\
$\epsilon_5$ & Threshold for frequent transitions  & $\epsilon_3/2|\Sigma|L(L+1)$\\
$\epsilon_6$ & Bound on exit probability  & $\epsilon_2 \epsilon_5 /(L+1) $ \\
$\delta'$   & Fraction of confidence &   Equation~\ref{eqn:deltaprime} 
\end{tabular}
\caption{Glossary for notation}
\label{tbl:aide}
\end{table}


\subsection{Weights of States}

% Motivate this by reference to bounding the KLD

We will use a particular decomposition of the KLD, that allows us to represent the divergence as a weighted sum of
the divergences between the distributions  of the transition probabilities between states in the target and states in the hypothesis.
This requires us to define a number of quantities which relate to the expected number of times the automaton will be in various states. 

%%
%% Definitions of weights moved from preliminaries
%%


We will define below  the \emph{weight} of a state. Informally, this is the expected number of times the automaton will reach, or pass through, that state.
Here we encounter one of the differences that cyclicity introduces. With acyclic automata, the automaton can reach each state at most once. 
Thus the expectation is equal to the probability -- and thus we can operate with sets of strings, and simply add up the probabilities. 
With cyclic automata, the automata can repeatedly be in  a particular state while generating a single string. 
We start by defining 
\begin{equation}
\label{eqn:wdq}
 W_d(q) = \sum_{s \in \Sigma^d: \tau(q_0,s) = q} \gamma(q_0,s).
\end{equation}
Informally,  $W_d(q)$  is the probability that it will generate at least $d$ characters and be in the state $q$ after having generated the first $d$. 
%In this case since the value of the underlying random variable is either 0 or 1,  the probability is equal to the expectation.
This is an important difference in notation to that of \cite{RON95}, who use $W$ to refer to a set of strings.


Since $s$ does not end in $\zeta$, we are not summing over the probability of strings but rather the probability of prefixes.
Note that $W_0(q_0)$ is by definition 1 and that we can also calculate  this quantity recursively as 
\begin{equation}  \label{eq:wd(q)recurs}
W_d(q) = \sum_{p \in Q} W_{d-1}(p) \sum_{\sigma: \tau(p, \sigma) = q} \gamma(p,\sigma).
\end{equation}



We now define the probability that the automaton 
will generate a string of length at least $d$ as $W_d$:
\begin{equation*}
W_d = \sum_{q \in Q} W_d(q).
\end{equation*}
Note that  the probability that it will be of length exactly $d$ is
$W_{d} - W_{d+1}$, and that $W_0 = 1$.
We also define here the \emph{expected} number of times the automaton will be in the state $q$ as
\begin{equation}
\label{eqn:wq}
W(q)  = \sum_{d=0}^{\infty}W_d(q) = \sum_{s \in \Sigma^*:~ \tau(q_0,s) = q} \gamma(q_0,s).
\end{equation}
We shall refer to this quantity  as the \emph{weight} of the state $q$.
%% \begin{align} 
%% W_0(q_0) & = 1 \nonumber \\
%% W_0(q)  & = 0 \text{ when } q \not = q_0 \nonumber \\
%% W_d(q) &= \sum_{p \in Q} W_{d-1}(p) \sum_{\sigma: \tau(p, \sigma) = q} \gamma(p,\sigma)
%% \end{align}
Therefore the expectation of the length of strings is
\begin{equation*}
E[|s|] = \sum_{d=0}^{\infty} d  (W_{d} - W_{d+1}) =  \sum_{d=1}^{\infty} W_d = \left(\sum_{d=0}^{\infty} W_d \right)  - W_0 
= \left( \sum_{d=0}^{\infty} W_d \right) - 1 
=  \sum_{s \in \Sigma^*}  \gamma(q_0,s) - 1.
\end{equation*}

The expected length of strings generated from any state can be defined likewise. 
We will be given a bound on the expected length of strings generated from any state, denoted by  $L$.
Formally, for all $q$ we shall require that
\begin{equation*}
 \sum_{s \in \Sigma^*} \gamma(q, s) \leq L + 1 .
\end{equation*}
Using this bound we can establish that for any length $k$,
\begin{equation*}
\sum_{d > k}^{\infty} W_d = \sum_q W_k(q)  \sum_{d>0} \, \, \, \, \sum_{s \in \Sigma^d} \gamma(q, s)   \leq L  W_k.
\end{equation*}
We will later need to bound the quantity $\sum_d d W_d(q)$,
which we can do in the following way:

\begin{equation} \label{eq:boundOnWq}
\sum_{d=0}^{\infty} d W_d(q) \leq \sum_{d=0}^{\infty} d W_d = \sum_{d=0}^{\infty} \sum_{k > d} W_k \leq  \sum_{d=0}^{\infty} L W_d  \leq L (L+1).
\end{equation}

In addition to these expected values, we will also need to lower bound the probability of the automaton being in  a state at least once in terms of the expected number of times it will be in that state. 
% The probability that at some point the automaton is in state $q$ 
The probability of it being in a  state  at some point can be defined in terms of 
the set of strings that have a prefix that reaches the state, 
 \begin{equation*}
 S(q) = \{ s \in \Sigma^* : \exists r, t \in \Sigma^* \, \text{s.t.} \, s=rt \wedge \tau(q_0, r) = q \},
 \end{equation*}
or in terms of the set of strings that reach $q$ for the first time (i.e.  have no proper prefix that also reaches $q$):

 \begin{equation*}
 R(q) = \{ s \in \Sigma^* : \tau(q_0, s) = q  \wedge (\not \exists u,v \in \Sigma^*  \, \text{s.t.} \,v \neq \lambda \wedge uv = s \wedge \tau(q_0, u) = q )\}.
 \end{equation*}
The probability of it being in  the state at least once can therefore be written in two ways  
 \begin{equation*}
\label{eqn:pq}
 P(q) = \sum_{s \in S(q)}  \gamma(q_0,s \zeta) =  \sum_{s \in R(q)} \gamma(q_0,s).
 \end{equation*}
Note that in the absence of a bound on the expected length of strings, a state can have arbitrarily small probability of
being visited  but have large weight. 

\begin{lemma} \label{lemma:probbound}
For any automaton such that the expected length from any state is less than L, for all states $q$,
$P(q) \geq W(q)/(L+1)$.
\end{lemma}

\paragraph{Proof}
Intuitively,  after we reach the state $q$, the expected number of times we reach the state $q$ again will be at most the expected number of times we reach any state after this, which is bounded by $L$. Formally,
\begin{eqnarray*}
 W(q) &  = &  \sum_{s \in S(q):~ \tau(q_0,s) = q} \gamma(q_0,s) \\
  & = & \sum_{r \in R(q)}   \, \, \, \, \sum_{s \in \Sigma^*:~ \tau(q_0,rs) = q} \gamma(q_0,rs) \\
& = & \sum_{r \in R(q)} \, \, \, \, \sum_{s \in \Sigma^*:~ \tau(q_0,rs) = q} \gamma(q_0,r) \gamma(q,s) \\
& = & \sum_{r \in R(q)}  \gamma(q_0,r) \sum_{s \in \Sigma^*:~ \tau(q_0,rs) = q} \gamma(q,s) \\
& = & P(q) \sum_{s \in \Sigma^*:~ \tau(q_0,rs) = q} \gamma(q,s) \\
& \leq & P(q) \sum_{s \in \Sigma^*} \gamma(q,s) \\
\hspace{1.8in}& \leq & P(q) (L +1).\hspace{2.7in} \blacksquare
\end{eqnarray*}

We also define here a related quantity given two automata.
Given two automata $A, \hat{A}$ with sets of states $Q, \hat{Q}$, the joint weight  $W(q,\hat{q})$ is defined to be  the expected
number of times the
automata are simultaneously in the states $q \in Q$ and $\hat{q} \in \hat{Q}$, 
when strings are being generated by $A$, and parsed by $\hat{A}$.

Define
\begin{equation}
\label{eqn:wdqq}
W_d(q,\hat{q}) = \sum_{\substack{s: \tau(q_0,s) = q \\ \hat{\tau}(\hat{q_0}, s) = \hat{q} \\ |s| = d}} \gamma(q_0,s).
\end{equation}
We can also define this recursively with $W_0(q_0, \hat{q}_0) = 1$ and  
\begin{equation*}
W_d(q,\hat{q}) = \sum_{p \in Q} \sum_{\hat{p} \in \hat{Q}} W_{d-1}(p,\hat{p}) 
                % \sum_{\sigma:  \tau(p,\sigma) = q \, \wedge \, \hat{\tau}(\hat{p}, \sigma) = \hat{q} } 
 \sum_{\substack{\sigma:  \tau(p,\sigma) = q \\ \hat{\tau}(\hat{p}, \sigma) = \hat{q} }} 
                 \gamma(p,\sigma).
\end{equation*}

%% \begin{equation}
%% \begin{split}
%% W_0(q_0,\hat{q_0}) &= 1 \\
%%  W_0(q,\hat{q}) &= 0 \text{ otherwise} \\
%% W_d(q,\hat{q}) & = \sum_{p \in Q} \sum_{p' \in \hat{Q}} W_{d-1}(p,p') 
%% \sum_{
%% \substack{
%% \sigma: \tau(p,\sigma) = q \\
%% \hat{\tau}(p', \sigma) = q' 
%% }
%% }
%% \gamma(p,\sigma)
%% \end{split}
%% \end{equation}

We now define the expected number of times the first automaton will be in state $q$ and the second in state $\hat{q}$ thus
\begin{equation*}
W(q,\hat{q}) = \sum_{d}W_d(q,\hat{q}).
\end{equation*}
Note also that 
\begin{equation}
\label{eqn:wqq}
W(q) = \sum_{\hat{q} \in \hat{Q}} W(q,\hat{q}) .
\end{equation}
Given these quantities we can now use the following  decomposition of the KLD \citep{CARRASCO97}  to bound the error: 

\begin{equation}
\label{eqn:carrasco}
D_{KL}(T||H) = \sum_{q \in Q_T} \sum_{\hat{q} \in Q_H} \sum_{\sigma \in \Sigma \cup \{\zeta\}} W(q, \hat{q}) \gamma(q,\sigma) 
\log 
\frac{\gamma(q,\sigma)}{\hat{\gamma}(\hat{q},\sigma)}.
\end{equation}





%%
%% End of stuff from preliminaries
%%


%
% Start new explanation
%

\subsection{Probably Correct}



We define a notion of \emph{goodness} of a  multiset  which is satisfied if certain 
properties of the multiset are close to their expected values.


\begin{definition}[Good multiset]
\label{def:multiset}
We say that a multiset $S$ is  $\mu$-$\epsilon_1$-\emph{good} 
for a state $q$ iff
  $L_{\infty}(\hat{S}, P_q) < \mu/4$  and for every $\sigma \in \Sigma \cup \{ \zeta \}$,
$|S(\sigma)/|S|- \gamma(q,\sigma)| < \epsilon_1$.
\end{definition}


The algorithm produces a sequence of graphs $G_0, G_1, \dots, G_k$, with multisets attached to each node.
We will first show that all of these graphs have the right structure, and then we will show that the final graph will 
have all of the important structure and finally we will bound the KLD.



\begin{definition}[Good hypothesis graph]
\label{def:phi}
We say that a hypothesis graph $G$ for an automaton $A$ is \emph{good} if there is a bijective function  $\Phi$ from  a subset of states of $A$ to all the  nodes of $G$ such that $\Phi(q_0) = v_0$,
 and if $\tau_G(u, \sigma) = v$ then 
%there is an edge labelled with $\sigma$ from node $u$ to node $v$ in the graph then
 $\tau(\Phi^{-1}(u), \sigma) = \Phi^{-1}(v)$, and for every node $u$ in the graph, the multiset attached to $u$ is $\mu$-$\epsilon_1$-good for 
the state $\Phi^{-1}(u)$.
\end{definition}

Note that if there is such an isomorphism then it is unique.
When $\Phi(q) = u$ we shall call $u$  a representative of the state $q$. When we have a candidate node $(u,\sigma)$ we shall call this also a representative of the state $\tau(q, \sigma)$.
We will extend the use of $\Phi$ to a mapping from the states of the target to the states of the final hypothesis automaton. 
In this case it will no longer be bijective since in general more than one state can be mapped to the ground state.



\begin{lemma}
If a graph $G_i$ is good and we draw a sample of size $N$ such that
for every candidate node with multiset $S$ such that $|S|>m_0$ is 
 $\mu$-$\epsilon_1$-good for the state $\tau(\Phi^{-1}(u), \sigma)$ , and there is at least one such candidate node,
then the graph $G_{i+1}$ is also good.
\end{lemma}


Consider a candidate node $(u, \sigma)$ and a node $v$
 Suppose these are both representatives of the same state $q$ in which case $\Phi^{-1}(v) = \tau(\Phi^{-1}(u), \sigma)$.
Then as $L_{\infty}(\hat{S}_{u,\sigma},P_q) < \mu/4$ and $L_{\infty}(\hat{S_v},P_q)  < \mu/4$ (by the goodness of the multisets),   the triangle inequality shows that 
$L_{\infty}(\hat{S}_{u,\sigma},\hat{S_v})  < \mu/2$, and therefore the comparison will return true.
On the other hand, let us suppose that they are representatives of different states $q$ and $q_v$.
We know that $L_{\infty}(\hat{S}_{u,\sigma},P_{q}) < \mu/4$ and $ L_{\infty}(\hat{S_v},P_{q_v}) < \mu/4$ (by the goodness of the multisets), 
and $ L_{\infty}(P_{q},P_{q_v})  \geq \mu$ (by the $\mu$-distinguishability of the target).
By the triangle inequality 
$ L_{\infty}(P_{q},P_{q_v}) \leq   L_{\infty}(\hat{S}_{u,\sigma},P_{q}) + L_{\infty}(\hat{S}_{u,\sigma},\hat{S_v}) +  L_{\infty}(\hat{S_v},P_{q_v})   $,
 therefore 
$   L_{\infty}(\hat{S}_{u,\sigma},\hat{S_v})  > \mu/2$ and the comparison will return false.
If there is a node in the graph that is similar to the candidate node, then this is because there is the relevant transition in the
target automaton, which means the new graph will also be good.
If there is no such node, then that is because there is no node $v$ such that $\Phi^{-1}(v)= \tau(\Phi^{-1}(u), \sigma)$ 
in which case we can define a new node $v$ and define  $\Phi^{-1}(v)= \tau(\Phi^{-1}(u), \sigma)$, and thereby show that the new graph is good.
Additionally since the candidate node multisets are   $\mu$-$\epsilon_1$-good, the multiset of this node will also be good.\hfill{$\blacksquare$}

Since $G_0$ is good if the initial sample is good, 
using this we can prove by induction on $i$ that the final hypothesis graph will be 
 $\mu$-$\epsilon_1$-good if all the samples satisfy the criteria defined above.






 % Perhaps remove this part and put it into a later section.


%\footnote{Added this -- is this enough?}


% We can rewrite this with tau_g
%% We now define the \emph{exit probability} of the graph. This is the probability that a random string from the automaton will leave the graph when we trace the sequence of edges in the graph corresponding to each letter in the string. Equivalently, if the graph is good, this corresponds to the probability that the automaton will take a transition not represented in the graph.
%% \begin{definition}[exiting the graph]
%% We say that a string $s \in \Sigma^*$, $ \sigma_1 \dots \sigma_k$  exits the graph G if there is no sequence  of nodes
%% in $G$ starting with the inital node $g_0 \dots g_k$, such that there is an edge labelled with $\sigma_i$ from node
%% $g_{i-1}$ to  node $g_{i}$.  
%% The exit probability of a graph $G$, which we write $P_{exit}(G)$ is $\displaystyle \sum_{s : s  \text{ exits } G} \gamma(q_0, s
%% \zeta)$ 
%% \end{definition}

\begin{definition}[exiting the graph]
A string exits a graph $G$ if there is no node $v$ such that $\tau_G(v_0,s) = v$.
The exit probability of a graph $G$ (with respect to an automaton $A$) 
 which we write $P_{exit}(G)$ is defined as
\begin{equation*}
P_{exit}(G)  = \sum_{s : s  \text{ exits } G} \gamma(q_0, s\zeta).
\end{equation*}
\end{definition}

\begin{definition}[Good sample]
We say that a sample of size $N$ is good given a good graph $G$ if 
for every candidate node $(u,\sigma)$,  such that $|S_{u,\sigma}| > m_0$,
$S_{u,\sigma}$ is $\mu$-$\epsilon_1$-good for the state $\tau(\Phi^{-1}(u),\sigma)$ 
and that if $P_{exit}(G) > \epsilon_6$ then the number of strings that exit the graph is more than $\frac{1}{2} N P_{exit}(G)$.
\end{definition}




Note that if there are  no candidate nodes with multisets larger than $m_0$,
then the total number of strings that exited the graph must be less than $n |\Sigma| m_0$ 
(since there are at most $n$ nodes in a good graph, and therefore at most $n |\Sigma|$ candidate nodes). 
Therefore in this circumstance, if the samples are good, we can conclude that either $P_{exit}(G)
\leq \epsilon_6$ or  $P_{exit}(G) < 2n |\Sigma| m_0/N$.



 We  then prove that the hypothesis graph will probably contain a node representing each  state with non-negligible weight, and an edge representing each transition
from a state with non-negligible weight that has a non-negligible transition probability. 
We define two intermediate quantities: $\epsilon_2$, a bound on the
weight of states, and $\epsilon_5$, a bound on transition weights. We have

\begin{equation}
\label{eqn:e2bound}
\epsilon_2 = \frac{\epsilon_3}{2nL(L+1)} 
\text{ and } 
\epsilon_5 = \frac{\epsilon_3}{2|\Sigma|L(L+1)}.
\end{equation}


%% We define a frequent state of the target as a state $q$ where $W(q) > \epsilon_2$. 
%%  A frequent
%% transition is a transition from a frequent state $q$, labelled with a letter $\sigma$ such that  
%% $\gamma(q,\sigma) > \epsilon_5$.


\begin{lemma}
\label{lemma:frequentStateHasRepresentativ}
For any state $q$ in the target such that $W(q) > \epsilon_2$, 
if all the samples are good, then there will be 
a node  $u$ in the final  hypothesis graph such that
$\Phi(q) = u$. Furthermore, for such a state  for any $\sigma \in \Sigma$,
such that  $\gamma(q,\sigma) > \epsilon_5$,
then $\tau_G(u, \sigma)$ is defined and is equal to $\Phi(\tau(q,\sigma))$.
\end{lemma}

\paragraph{Proof} 


Since $W(q) > \epsilon_2$, we know by Lemma~\ref{lemma:probbound} that  $P(q) > \epsilon_2/(L+1)$.

From the definitions of $N$ and $\epsilon_6$

\begin{equation*}
\frac{2n |\Sigma| m_0}{N} < \epsilon_6 = \frac{\epsilon_2 \epsilon_5}{(L+1)} <  P(q) \epsilon_5 < P(q).
\end{equation*}
Clearly if there were no 
 representative node $u$ for state $q$, then all strings that reached the state would exit the graph, and thus $P_{exit}(G) \geq P(q)$. 
Similarly, if there were no edge labelled $\sigma$ from the node, then $P_{exit}(G) \geq P(q) \epsilon_5$.
By the goodness of the sample we know that  either $P_{exit}(G)
\leq \epsilon_6$ or  $P_{exit}(G) < 2n |\Sigma| m_0/N$, in both cases
 $P_{exit}(G) <  P(q) \epsilon_5$. Therefore there is a suitable state $u$ and edge in the graph,
and since the final hypothesis graph is $\mu$-$\epsilon_1$-good, $\tau_G$ will have the correct value. \hfill{$\blacksquare$}
 


\subsection{Close Transition Probabilities} 


Assuming that all the samples are good, we now want to show that 
the final smoothed transition probabilities will be close to the correct values.
More precisely,
we want to show that for all transitions, the ratio of the true value to the estimate is 
not much greater than unity.

For every  state $q$  with $W(q) > \epsilon_2$, with  $u = \Phi(q)$ and for every  symbol $\sigma \in \Sigma \cup \{ \zeta \}$,  we will have, by the goodness of the multisets
\begin{equation}
\label{eqn:transest}
 \left| 
\gamma(q, \sigma) - 
       \frac{S_u(\sigma)}{|S_u|} 
\right| \leq  \epsilon_1.
\end{equation}
Define
\begin{equation*}
 \epsilon_4 = \frac{\epsilon}{2(L+1)},
\end{equation*}


\begin{equation*}
\gamma_{min} = \frac{\epsilon_4}{2 ( |\Sigma| + 1)} \textrm{ \, and \,} \epsilon_1 = \frac{\epsilon_4^2}{4 ( |\Sigma| + 1)}.
\end{equation*}
We use exactly the argument in Lemma 5.3 of  \citet{RON95}: 
if $\gamma(q, \sigma)$ is small (at most $ \gamma_{min} + \epsilon_1$) 
then the estimate will anyway be at least $\gamma_{min}$ and thus the ratio will be not much larger than the true value, 
and if it is large then it will be close to the true value.
We can verify that
\begin{equation}\label{eq:trans_proba_end}
  \frac{\gamma(q, \sigma)}{\hat{\gamma}(q, \sigma)} \leq 1 + \epsilon_4.
\end{equation}




\subsection{Close Weights}

We now come to the most complex part of the proof. 
We want to show for every frequent state $q$ in the target, which will have a corresponding state in the hypothesis $\hat{q} = \Phi(q)$,
  that (again under the assumption that all the samples are good)
 \begin{equation}
\label{eqn:closeweights}
W(q) - W(q,\hat{q}) \leq \epsilon_3.
 \end{equation}      
As a consequence of this and Equation~\ref{eqn:wqq}, we will
have

 \begin{equation}
\label{eqn:closeweights2}
\sum_{\hat{q}: \Phi(q) \not = \hat{q}}  W(q,\hat{q}) \leq \epsilon_3 .
 \end{equation}
%
%This means that we can say that nearly all of the probability mass that goes through the 
%state $q$ also goes through the state $\hat{q}$.
So we will do this by showing that for any $d$
\begin{equation*}
W_d(q) - W_d(q,\hat{q})  < \frac{\epsilon_3 d W_d(q)}{L(L+1)}. 
\end{equation*}
Then, since we know that 
$\sum_d d W_d(q) < L(L+1)$ by Equation~\ref{eq:boundOnWq},
 we can  sum with respect to $d$ and derive the result. 

%% Now we want to prove that 
%% the quantity $W_d(q) - W_d(q,\hat{q})  $ is below a linear function of $d$. 
%% So at step $d+1$, we have a state $q$; we know that at the previous step, all of the weights
%% $W_d(q)$ are close to the weights $W_d(q,\hat{q})$
%% and we can prove that the transitions are close to each other. 

\begin{lemma} \label{lemma:correctWeight}
For all states $q \in Q$ such that
$W(q) > \epsilon_2$, there is a state $\hat{q}$ in the  hypothesis  such that
$\Phi(q) = \hat{q}$ and for all $d \geq 0$
\begin{equation*}
 W_d(q) - W_d(q,\hat{q}) \leq \frac{\epsilon_3 d  W_d(q)}{L(L+1)}.
\end{equation*}

\end{lemma}

\paragraph{Proof}
%\footnote{I changed $\Phi$ into $\Phi^{-1}$ because of def of $\Phi$. This is still wrong since it goes from states
 % to nodes and not from states to states.... . \\
%I have fixed this (I think!)}
We will prove the lemma by induction on $d$.
For $d=0$ this is clearly true.
For the inductive step, we assume that it is true for $d -1$.




We can rewrite the joint weight as
\begin{align}
W_d(q,\hat{q}) 
& = \sum_{p \in Q} 
\sum_{\hat{p} \in \hat{Q}}
W_{d-1}(p,\hat{p})
\sum_{
\substack{
\sigma: \tau(p,\sigma) = q \\
\hat{\tau}(\hat{p}, \sigma) = \hat{q}
}
}
\gamma(p,\sigma) .
\end{align}
If we consider only the cases where $W(p) > \epsilon_2$ and $\Phi(p) = \hat{p}$ we can see that
\begin{align}
W_d(q,\hat{q}) & \geq \sum_{p \in Q: W(p) > \epsilon_2 } W_{d-1}(p,\Phi(p))
\sum_{
\substack{
\sigma: \tau(p,\sigma) = q \\
\hat{\tau}(\Phi(p), \sigma) = \hat{q}
}
}\gamma(p,\sigma) .
\end{align}
And then  by the inductive hypothesis, for these frequent states
\begin{align}
W_d(q,\hat{q}) & \geq 
\sum_{p \in Q: W(p) > \epsilon_2 } 
W_{d-1}(p)
\left(
1 - \frac{\epsilon_3 (d -1)}{L(L+1)}
\right)
\sum_{
\substack{
\sigma: \tau(p,\sigma) = q \\
\hat{\tau}(\Phi(p), \sigma) = \hat{q}
}
}\gamma(p,\sigma) .
\end{align}
Using the fact that $W_d \leq 1$ for all $d$, and using the recursive definition of $W_d$ we can write this as
\begin{align}
W_d(q,\hat{q}) & \geq 
\sum_{p \in Q: W(p) > \epsilon_2 } 
W_{d-1}(p)
\sum_{
\substack{
\sigma: \tau(p,\sigma) = q \\
\hat{\tau}(\Phi(p), \sigma) = \hat{q}
}
}
\gamma(p,\sigma)  
 - \frac{\epsilon_3 (d-1) W_{d-1}}{L(L+1)} \\
%%  new line
\label{eqn:xxx}
& \geq 
\sum_{p \in Q : W(p) > \epsilon_2 } 
W_{d-1}(p)
\sum_{\sigma: \tau(p,\sigma) = q}
\gamma(p,\sigma) \nonumber \\
& \, \, \, \, \, \,  \, \, \, \, \, \, -
 \sum_{p \in Q : W(p) > \epsilon_2 } 
W_{d-1}(p)
\sum_{
\substack{
\sigma: \tau(p,\sigma) = q \\
\hat{\tau}(\Phi(p), \sigma) \not = \hat{q}
}
}
\gamma(p,\sigma) \nonumber \\
& \, \, \, \, \, \,  \, \, \, \, \, \,- 
\frac{\epsilon_3 (d-1)}{L(L+1)} .
\end{align}
So we need to show that most of the  weight from $W_{d-1}$  must be
from states $p$  with $W(p) > \epsilon_2$. Then we can change 
from $W_{d-1}(p)$ to $W_{d}(q)$. 


Using Equation~\ref{eq:wd(q)recurs} we can see that
\begin{eqnarray*}
 W_d(q)  & =  &  \sum_{p \in Q: W(p) \leq \epsilon_2} W_{d-1}(p) \sum_{\sigma: \tau(p, \sigma) = q} \gamma(p,\sigma) + \sum_{p \in Q: W(p) > \epsilon_2} W_{d-1}(p) \sum_{\sigma: \tau(p, \sigma) = q} \gamma(p,\sigma) \\
& \leq &  n \epsilon_2 + \sum_{p \in Q: W(p) > \epsilon_2} W_{d-1}(p) \sum_{\sigma: \tau(p, \sigma) = q} \gamma(p,\sigma) .
\end{eqnarray*}
%We can now say, since we know that all of the frequent states have representative states in the hypothesis,
Using this to replace the first term on the right hand side of Equation~\ref{eqn:xxx} we get

\begin{equation*}
W_d(q,\hat{q})  \geq 
W_{d}(q) - n \epsilon_2 - \frac{\epsilon_3 (d-1)}{L(L+1)} 
 -
\sum_{p \in Q: W(p) > \epsilon_2} 
W_{d-1}(p)
\sum_{
\substack{
\sigma: \tau(p,\sigma) = q \\
\hat{\tau}(\Phi(p), \sigma) \not = \hat{q}
}
}
\gamma(p,\sigma) .
\end{equation*}
Since by Lemma~\ref{lemma:frequentStateHasRepresentativ} all of the transitions from frequent states with probability greater than $\epsilon_5$ must go to the correct states,
we know that the values of $\gamma(p,\sigma) $ in the final term must be less than $\epsilon_5$.

\begin{eqnarray*}
W_d(q,\hat{q}) &  \geq &
 W_{d}(q) - n \epsilon_2
 - \frac{\epsilon_3 (d-1)}{L(L+1)} 
 -
\sum_{p \in Q: W(p) > \epsilon_2} 
W_{d-1}(p)
\sum_{\sigma} \epsilon_5
\\
& \geq & 
 W_{d}(q) - n \epsilon_2
 - \frac{\epsilon_3 (d-1)}{L(L+1)} -  |\Sigma| \epsilon_5.
\end{eqnarray*}
By our definitions of $\epsilon_2$ and $\epsilon_5$
\begin{equation*}
n \epsilon_2 + |\Sigma| \epsilon_5 \leq \frac{\epsilon_3}{L(L+1)},
\end{equation*}
and therefore
the lemma will hold. \hfill{$\blacksquare$}


%% Summing over $d$, we finally get
%% %\footnote{\warning I changed things here. It was  $W_d(q) - W_d(q,\hat{q}) \leq W_d(q) \epsilon_3$ }
%% \begin{equation*}
%%  W(q) - W(q,\hat{q}) \leq W(q) \epsilon_3
%% \end{equation*}


\section{Proof that the Divergence is Small}\label{sec:correctKLD}

We are now in a position to show that the KLD between the target and the hypothesis is small. 
We use Carrasco's decomposition of the KLD  \citep{CARRASCO97}   to bound the error: 

\begin{equation*}
D_{KL}(T||H) = \sum_{q \in Q_T} \sum_{\hat{q} \in Q_H} \sum_{\sigma \in \Sigma \cup \{\zeta\}} W(q, \hat{q}) \gamma(q,\sigma) 
\log 
\frac{\gamma(q,\sigma)}{\hat{\gamma}(\hat{q},\sigma)}.
\end{equation*}

We are going to divide the summands into three parts.
We define
\begin{equation*}
D(q,\hat{q}) =   W(q, \hat{q})  \sum_{\sigma \in \Sigma \cup \{\zeta\}}\gamma(q,\sigma) 
\log 
\frac{\gamma(q,\sigma)}{\hat{\gamma}(\hat{q},\sigma)},
\end{equation*}
 
\begin{eqnarray*}
D_1 &=& \sum_{q \in Q_T: W(q) > \epsilon_2}  \sum_{\hat{q} \in Q_H: \Phi(q) = \hat{q}} D(q, \hat{q}), \\
D_2 &=& \sum_{q \in Q_T: W(q) > \epsilon_2}  \sum_{\hat{q} \in Q_H: \Phi(q) \not = \hat{q}} D(q, \hat{q}), \\
D_3 &=& \sum_{q \in Q_T: W(q) \leq \epsilon_2}  \sum_{\hat{q} \in Q_H}  D(q, \hat{q}).
\end{eqnarray*}
Note that for the frequent states with $W(q) > \epsilon_2$,  $\Phi$ will be well-defined. \\
\begin{equation*}
D_{KL}(T||H) = D_1 + D_2 + D_3
\end{equation*}
We will bound these separately.  
We bound $D_1$  by showing  that for these matching pairs of states $q$, $\Phi(q)$, all of the transition probabilities are close to
each other.
We can bound  $D_2$  by showing that  $W(q,\hat{q})$ is small when $\hat{q} \not = \Phi(q)$, and  $D_3$ since  $W(q)$ is small. 

Using Equation~\ref{eq:trans_proba_end} and recalling that $W(q) \geq
W(q,\hat{q})$ we bound $D_1$.


%\footnote{\warning I'm  still  puzzled for eq D1: why $W(q) < L$ ? and not $W(q) < L(L+1)$ (equation \ref{eq:boundOnWq} page \pageref{eq:boundOnWq})} 

\begin{eqnarray*}
D_1  & \leq & \sum_{q \in Q_T: W(q) > \epsilon_2} W(q) \log  \left( 1 + \epsilon_4 \right)  \leq
(L+1)
\log 
\left( 1 + \epsilon_4 \right) 
\leq (L + 1) \epsilon_4.
\end{eqnarray*}
Bounding $D_2$ is done using Equation~\ref{eqn:closeweights2}, the fact that $\gamma(q,\sigma) \leq 1$ and that 
$\hat{\gamma}(\hat{q},\sigma) \ge \gamma_{min}$ by the smoothing technique. 


\begin{eqnarray*}
D_2  
& \leq & \sum_{q \in Q_T, W(q)> \epsilon_2}  
\sum_{\hat{q} \in Q_H: \Phi(q) \not = \hat{q}}
 W(q, \hat{q})  \sum_{\sigma \in \Sigma \cup \{\zeta\}}\gamma(q,\sigma) 
\log 
\frac{1}{\gamma_{min}}
\\
& \leq & \sum_{q \in Q_T, W(q) > \epsilon_2} \epsilon_3 
\log \frac{1}{\gamma_{min}} \leq n \epsilon_3 \log \frac{1}{\gamma_{min}}.
\end{eqnarray*}
With regard to  $D_3$, using Equation~\ref{eqn:wqq} and the bound on $W(q)$ we can see that

\begin{eqnarray*}
\begin{aligned}
D_3 & \leq \sum_{q \in Q_T, W(q) \leq \epsilon_2} \sum_{\hat{q} \in Q_H} W(q, \hat{q})
\sum_{\sigma \in \Sigma \cup \{ \zeta \}} 
\gamma(q,\sigma)
\log \frac{1}{\gamma_{min}} \leq n  \epsilon_2 \log \frac{1}{\gamma_{min}}. 
\end{aligned}
\end{eqnarray*}


%Now we make various substitutions here to derive the appropriate values of $\epsilon_2,\epsilon_3,\epsilon_4,\gamma_{min}$ that will guarantee that the result will be less than $\epsilon$. 
%We then derive the sample size we need to guarantee that the $\epsilon_2,\epsilon_3,\epsilon_4$ conditions are satisfied with probability greater than $1 - \delta$.

 Substituting in Equation~\ref{eqn:e2bound}, and assuming  that $L > 1$,
\begin{eqnarray*}
D_{KL}(T||H) & < & (L+1) \epsilon_4 +  \left( n \epsilon_3 +  \frac{\epsilon_3}{2nL(L+1)}\right) \log \frac{1}{\gamma_{min}} \\
&<& (L +1) \epsilon_4 + (n + 1)\epsilon_3 \log \frac{1}{\gamma_{min}}.
\end{eqnarray*}
Substituting in the   values of $\gamma_{min}$, $\epsilon_3$ and $\epsilon_4$ gives us  $D_{KL}(T||H) < \epsilon$ as desired. \hfill{$\blacksquare$}


We have thus shown that if all of the samples are good at each step, the  resulting hypothesis will be approximately correct. 
We must now show  that all of the samples will be  good with high probability, by showing that $N$ and $m_0$ are large enough.

%Our next step is then to determine how much data we will need to be sure that all of our estimates will probably be close enough.
%If they all are, then we know we will be approximately correct.

\section{Bounding the Probability of an Error}

We need to show that with high probability a sample of size $N$ will be good for a given good graph $G$. We assume that the graph is good at each step.
Each step of the algorithm will increase the number of transitions in the graph by at least 1.
There are at most $n|\Sigma|$ transitions in the target; so there are at most $n |\Sigma| + 2$ 
steps in the algorithm since we need an initial step to get the multiset for $u_0$ and another at the end when we terminate.
So we want to show that a sample will be good with probability at least $1- \delta/(n |\Sigma| + 2) = 1 - 2 \delta'$.

There are two sorts of errors that can make the sample bad. 
First, one of the multisets could be bad, and secondly too few strings might exit the graph.
There are at most $n |\Sigma|$ candidate nodes, 
so we ensure that the probability of getting a bad multiset at a particular candidate node is
less than $\delta'/n |\Sigma| $, 
and we will ensure that  the probability of the second sort of error is less than $\delta'$. 


\subsection{Good Multisets}

First we bound the probability of getting a bad multiset. Recall from Definition~\ref{def:multiset} that we have two requirements.  First, for every string we must have the empirical probability 
within $\mu/4$ of its true value. 
Secondly, for each $\sigma \in \Sigma \cup \{ \zeta \}$ the empirical probability must be within $\epsilon_1$ of the true value.

A difficulty here is that in the first case we will be comparing over an infinite number of strings. Clearly only finitely many strings will have non-zero counts, but nonetheless, we need to show that for every string in $\Sigma^*$ the empirical probability is close to the true probability.
This will be true  if all of the strings with probability less than $\mu/8$ have empirical probability less than $\mu/4$
    and all of the strings with probability greater than this have empirical probability within $\mu/4$ of their true values.


Consider the strings of probability greater than $\mu/8$. There are at most $8/\mu$ of these.
Therefore for a given string $s$, by Hoeffding bounds \citep{hoeffding63}:
\begin{equation} \label{eq:frequent_string_comp}
Pr\left[\left| \frac{S_u(s)}{|S_u|} - \gamma(q,s \zeta)\right| > \mu/4 \right] < 2 e^{-m_u \mu^2/8} <  2 e^{-m_0 \mu^2/8}.
\end{equation}
The probability of making an error on one of these frequent strings is 
less than $\frac{16}{\mu}  e^{-m_0 \mu^2/8}$.  We also need to bound the probability of all of the rare strings--those  with 
$\gamma(q,s \zeta) \leq \mu/8$.
 
%% We divide the set of all rare strings into a set of groups

%% \begin{equation}
%% S_{rare} = \left\{  s \in \Sigma^*: \gamma(q,s \zeta) \leq \mu/8 \right\}
%% \end{equation}

Consider all of the strings whose probability is in $ [\mu 2^{-(k+1)}, \mu 2^{-k})$.
\begin{equation*}
S_k = \{ s \in \Sigma^*: \gamma(q,s \zeta) \in [\mu 2^{-(k+1)}, \mu 2^{-k}) \}.
\end{equation*}
Define $S_{rare} = \bigcup_{k=3}^{\infty} S_k$.
We bound each of the $S_k$ separately, using the binomial Chernoff bound where $n = |S_u| \mu/4 > |S_u| p$ (which is true since $p < \mu/4$):

\begin{equation*}
Pr\left[\frac{S_u(s)}{|S_u|} \geq \frac{\mu}{4}\right] \leq  \left( \frac{|S_u| p}{n} \right)^n e^{n - |S_u| p}.
\end{equation*}
 This bound decreases with $p$, so we can replace this for all strings in $S_k$ with
 the upper bound for the probability, and we can replace $|S_u|$ with $m_0$. We write $\mu' = \mu/4$ to reduce clutter.

\begin{align}
Pr\left[\frac{S_u(s)}{|S_u|} \geq \mu' \right] & \leq  \left( \frac{m_0 \mu' 2^{-k}}{m_0 \mu'} \right)^{m_0 \mu'} 
e^{
m_0 \mu' - m_0 \mu'2^{-k}
}\\
& \leq
\left( 2^{-k} e^{1 - 2^{-k}} \right) ^{ m_0 \mu'} < 2^{-k m_0 \mu'}.
\end{align}


Assuming that $m_0 \mu' > 3 $ we can see that
\begin{eqnarray}
Pr\left[\frac{S_u(s)}{|S_u|} \geq \mu' \right] & < & 2^{-2k} 2^{k(2 - m_0 \mu')} \leq 2^{-2k} 2^{2- m_0 \mu'}  \\
Pr\left[\exists s \in S_k: \frac{S_u(s)}{|S_u|} \geq \mu'\right] & \leq &   |S_k| 2^{-2k} 2^{  2- m_0 \mu' }  \leq   \frac{1}{\mu}2^{-k + 1} 2^{ 2- m_0 \mu' }.
\end{eqnarray}
The $2^{-k}$ factor allows us to sum over all of the $k$
to calculate the probability that there will be an error with any rare string: 
\begin{align}
\label{eqn:rare}
Pr\left[\exists s \in S_{rare}: \frac{S_u(s)}{|S_u|} \geq \mu'\right]
 & < \frac{1}{\mu}  \sum_{k=3}^{\infty}2^{-k + 1} 2^{ 2-
  m_0 \mu' }   < \frac{2}{\mu}2^{ - m_0 \mu' }  .
\end{align}


The next step is to show that for every $\sigma \in \Sigma \cup \{ \zeta \}$, 
 \begin{equation*}
\left| \gamma(q, \sigma) - 
       \frac{S_u(\sigma)}{|S_u|} \right| \leq  \epsilon_1.
 \end{equation*}
We can use Chernoff bounds to show that the probability of an error will be less than $e^{-2 m_0 \epsilon_1^2}$.
Putting these together we can show that the probability of a single multiset being bad 
can be bounded as in the equation below, and that this is satisfied by the value of $m_0$ defined above in Equation~\ref{eqn:mzero}:
\begin{equation}
\label{eqn:multisetbad}
\frac{16}{\mu}  e^{-m_0 \mu^2/8}  + \frac{2}{\mu}2^{- m_0 \mu/4 }  +   (|\Sigma| +1 ) e^{-2 m_0
  \epsilon_1^2}   < 
\frac{\delta'}
{n |\Sigma| } .
\end{equation}





\subsection{Exit Probability Errors}

We next need to show that roughly the expected number of strings exit the graph, if the
exit probability is greater than $\epsilon_6 = \epsilon_2 \epsilon_5 / (L + 1)$. Again we can  use
Chernoff bounds to show that the probability of this sort of  error will be less than  $e^{-N P_{exit}(G)/4} <
e^{-N \epsilon_6/4}$. 
It is easy to verify that for our chosen value of $N$,

\begin{equation}
\label{eqn:exit}
 e^{-N \epsilon_6 /4} < \delta'.
\end{equation}



%% \subsection{Sample Complexity}

%% We are now in a position to discuss the sample  complexity of this algorithm.
%% Define $\delta' = \delta/2(n |\Sigma| + 2)$.
%% To satisfy the inequality in Equation~\ref{eqn:multisetbad} 
%% we can bound each term in the left hand side separately as a third of the right hand side, getting
%% \begin{eqnarray} \label{eqn:mzero}
%% m_0 & > - 8/\mu^2 \log ( \delta' \mu /96 n |\Sigma| )  \\
%% m_0 & > - 4/\mu \log ( \delta' \mu /12 n |\Sigma| )  \nonumber \\ 
%%  m_0 & > - 1/ 2\epsilon_1^2 \log ( \delta'  /12 n |\Sigma| (|\Sigma+1| )\nonumber
%% \end{eqnarray}



%% Equation~\ref{eqn:exit} requires
%% \begin{equation}
%% \label{eqn:n1}
%%  N > \frac{- 4  \log \delta'}{\epsilon_6}
%% \end{equation}
%% we further need from Equation~\ref{eqn:sample}
%% \begin{equation}
%% \label{eqn:n2}
%% N > m_0 \frac{2 n |\Sigma|}{\epsilon_6}
%% \end{equation}


%% The overall sample complexity will then be $N n (|\Sigma| + 2)$.

\subsection{Complexity \label{sec:complexities}}

Since when the algorithm runs correctly  there are at most  $n |\Sigma| + 2$ steps, the sample complexity will be 
$N_{total} = N(n |\Sigma| + 2)$ which is polynomial by inspection.

As the strings can be of unbounded  length the computational complexity has to be bounded in terms of the total lengths of the strings as well.
If $S_{total}$ is the multiset representing the overall sample of size at most $N(n |\Sigma| + 2)$, then
define
\begin{equation*}
N_l = \sum_{s \in \Sigma^*} |s| S(s).
\end{equation*}
We denote the maximum observed length $L_{max}$ (clearly $L_{max} \leq N_l$).
%We will ignore that complexity here, and assume that all of the strings are  bounded by some  multiple of the expected length $L$.

Since  there are at most $n$ nodes in the graph at any time, and at most $n |\Sigma|$ candidate nodes, the number of comparisons will be at most
$n^2 |\Sigma|$ at each step and thus $n^2 |\Sigma|(n |\Sigma| + 2)$ in all. 
For each multiset we only need to store at most $m_0$ so there will be at most $m_0$ distinct strings in each multiset, so the comparison
will need to compare at most $2m_0$ strings, and each comparison will take at most $L_{max}$. 
The construction of the candidate nodes can be done in less than $N_l$ time.
 These observations suffice to show that the algorithm is polynomial in $N_l$ and $N_{total}$.
We have assumed here that $|\Sigma|$ is sufficiently small that two characters can be compared in constant time.



%% FIXME: rewrite completely.

%% The computational complexity can be estimated in
%% the usual way. 
%% Let $N_l$ be the total length of all the strings the algorithm sees, and $m$ be the total number of strings.
%% These must pre processed into appropriate data structures, for example tries,  which will take $O(N_l +m)$ time.
%% We will have at most $n |\Sigma| + 1$ steps in the algorithm, at each of which we compare  one
%% candidate to at most $n$ other nodes, making $O(n^2 |\Sigma|)$ comparisons.
%%  Each comparison can be done by iterating over the leaves of the trie, which will take $O(m_0)$, since we can bound the size of the multisets.
%% All other computation can be done in constant time giving us an overall time complexity of $O(N_l + n^2 |\Sigma| m_0)$.
%% Note also that we do not need to store the entire sample but only at most $n |\Sigma| m_0$ strings  for the nodes in the graph and $N$ for the candidate nodes.



%% We will use an adapted trie in order to represent the 
%% suffix distributions. As a new sample S of size N is drawn, we will build a trie that represent it. Building a trie can
%% be done in $O(N)$. In case of big vocabularies (\emph{e.g.} while dealing with NLP applications), we can save some place
%% by using a hash table for each node of the trie. Iterating over the candidates nodes can be done by iterating over the
%% leaf of the trie. This can be done in $O(N)$. Iterating over each node of the graph is bound by $n$, the size of the
%% target. The computation of the $L_\infty$ norm is bound by $O(N)$. All the other computation can be done in constant
%% time. The overall computational complexity is then $O(n^2|\Sigma|m)$ because of the link between the \texttt{while} loop
%% and quantities $N$ and $m$. \\

%% The space complexity will be the max between the size representation of the trie and  the graph one. Coding
%% the trie  can be done in $O(N\times |\Sigma|)$ (for a classic trie). The $|\Sigma|$ factor could be replace by
%% constant one if a hash table is used at each node of the trie.  Representing the graph can be done in $O(n |\Sigma|)$
%% using a matrix representation. Again here, if one deals with big vocabularies, an adjacent list can be used to represent
%% the graph and a dynamic smoothing used while parsing string using the automaton. \verb++

%% \section{Symmetric Difference}

%% When we use the divergence as error function, it is clear that any succesful algorithm must produce hypotheses whose support is all of $\Sigma^*$ -- i.e.
%% which give a  non-zero probability to very string. 
%% While desirable in this context, in many  other situations it may be more natural to consider an error function that depends on the languages rather than the distributions; the obvious choice being the
%% symmetric difference.
%% We shall now show that a slight variant of this algorithm can also learn with respect to this error function.
%% This is closer to more traditional error-functions. It is well known that regular languages cannot be PAC-learned with this error function even with positive and negative data, in a distribution-free setting.
%% However we can prove that if the distribution is closely related to the automaton -- 
%% namely if the distribution is generated by a PDFA such that the support of the distribution generated by the automaton is equal to the language -- then we can PAC-learn as long as we 
%% allow the sample complexity polynomial to contain the additional terms as above.
 

%%  We will write the symmetric difference between two languages $L_1, L_2 \subseteq \Sigma^*$ as $ L_1 \oplus L_2$.


%% \begin{theorem}
%% For all regular languages, $L$, for any distribution $D$ generated by a PDFA $A$ such that $L = \{ s : P_A(s) > 0\}$,
%% there is an algorithm and a polynomial $q$  that can produce a hypothesis $H \in RE$ such that \\
%% $Pr( L \oplus H > \epsilon) < \delta$, whenever the sample size is greater than $q(n, \Sigma, \delta^{-1}, \epsilon^{-1}, \mu^{-1}, L)$.
%% \end{theorem}
  



\section{Conclusion}

We have presented an algorithm and a  proof that it KL-PAC-learns the class of PDFAs given certain reasonable additional parameters
for the sample complexity. We argue that these additional parameters or some substitutes are necessary given the counter-examples previously studied and presented here.
Furthermore the classes we present here cover the whole space of  distributions defined by PDFAs. 
%Given the negative results for learnability of PFAs, the gap between what is known to be learnable and what is known not to be learnable is now quite small. 
Convergence properties of these sorts of state merging algorithms have been  studied 
before in the identification in the limit paradigm \citep{CARRASCO99}, but not in the KL-PAC framework.


% Comparison to other work

The work presented here can be compared to traditional types of PAC learning. 
Distribution free learning of regular languages has been shown to be hard under some standard cryptographic assumptions \citep{kearns94crypto}, but learnability under limited classes of distributions is still an open question.  
We can view the algorithm presented here, if the graph completion and smoothing is removed, as learning regular languages from positive samples only, where the distributions are restricted to be generated by PDFAs which define the target language.
We can compare the result presented in \citet{parekh01}, where it is shown that DFAs can be PAC-learned from positive and negative samples,
using a \emph{simple} distribution. This means a distribution where examples of low Kolmogorov complexity, given a representation of the target, have a high probability.  
Indeed, \citet{denis01learning} shows that using this approach they can also be probably exactly learned from positive examples only. Since the Solomonoff-Levin distribution dominates every other computable distribution, up to a constant factor, this is in some sense the easiest distribution to learn under.
Moreover, the use of simple distributions has a number of flaws:
first, there are some very large non-computable constants that appear in the sample complexity polynomial. Secondly, representations of the target will also have low complexity with respect to the target, and thus will almost certainly occur in polynomial samples (what is sometimes called ``collusion''), which does allow trivial learning algorithms in the case of the positive and negative samples.
This may  also be the case with  positive samples alone. 
This is an open question, and beyond the scope of this paper, but certainly if the support of the language is large enough, collusive learning becomes possible.
Thirdly, the examples provided will be those that are comparatively predictable -- i.e. carry little information; in many realistic situations, 
the strings are used to carry information and thus generally will have high complexity.
 Thus we feel that  though  mathematically quite correct, as a characterisation of the convergence properties of algorithms, these approaches are too abstract.

%Future work

One further extension we intend to study is to the class of the probabilistic residual automata \citep{esposito02} which should be tractable with matrix perturbation theory. 


% To the best of our knowledge this is the first attempt to provide a proof of convergence in the PAC framework for arbitrary PDFAs.


\acks{We are grateful to anonymous reviewers of this paper and  an earlier draft, for helpful comments.  We would also like to thank Codrin Nichitiu, Colin de la Higuera and Marc Sebban.}

\newpage

\appendix



\section*{Appendix A.}

% Informal overview

In this appendix we establish our counter-example that justifies our addition of a bound on the expected length of the
strings generated from every state. Our basic argument is as follows: 
we construct a countable family of automata such
that given any sample size N, even exponentially large, 
all but finitely many automata in the family will give the same sample set  with probability greater than 0.5. 
Given this sample set, the algorithm will produce a particular hypothesis. 
We show that whatever hypothesis,
 $H$,  a learning algorithm produces must have $D(H||T) > 0.05$ for some of the targets in the subset that will generate this same set.   
Thus arguing by contradiction, we see that it is not possible to have a PAC-learning algorithm unless we allow it to have a sample complexity polynomial that includes some additional  parameter relating in some way to the expected length.
We neglect the possibility that the algorithm might be randomised, but it is easy to deal with that eventuality.

% Simple bound

It is quite straightforward to construct such a family of automata  if we merely want to demonstrate the necessity of
a bound on the overall expected length of the strings generated by the automaton.
Consider a state of the target that is reached with prob $n^{-1}$, but that generates strings of length $n^2$ through a transition to itself of probability $1- n^{-2}$. For such a state $q$,  the weight  $W(q)$ will be $n$. Thus any small differences in the transitions can cause unbounded increases in the KLD. Here we want to establish a slightly sharper result, which applies even when we have a bound on the overall  expected length.

% Description




We define a family of automata $\mathcal{F}_k$ for some $k > 0$, over a two letter alphabet 
$\Sigma = \{a,b\}$, 
$\mathcal{F}_k = \{A_p^s | s \in \Sigma^k , p \in (0,1)\}$.
Each of these automata $A = A_p^s$ defines a distribution as follows:

\begin{equation*}
\begin{aligned}
P_A(t) & = & p           & \text{ when } t = a; \\
P_A(t) & = & (1-p)^2 p^i & \text{ when  } t = bs^i \text{ for } i \geq 0 \text{   };\\
P_A(t) & = &  0          & \text{ otherwise }.  
\end{aligned}
\end{equation*}
The automata will have $k+2$ states, and the expected length of the strings 
generated by these automata will be $k + 1$. Figure~\ref{fig:counter} shows a simple example for $k=4$.

\begin{figure}
\label{fig:counter}
\begin{center}
\psfrag{z1}{$\zeta:1$}
\psfrag{s0}{$q_0$}
\psfrag{s1}{$q_1$}
\psfrag{s2}{$q_2$}
\psfrag{s3}{$q_3$}
\psfrag{s4}{$q_4$}
\psfrag{s5}{$q_5$}
\psfrag{b1}{$b:1$}
\psfrag{a1}{$a:1$}
\psfrag{f}{$q_f$}
\psfrag{z2}{$\zeta:q$}
\psfrag{bq}{$b:q$}
\psfrag{ap}{$a:p$}

\includegraphics[scale=0.5]{counterexample.ps}
\end{center}
\caption{Example automaton with $k= 4$ and $s = aabb$. The arcs are labelled with the symbol and then the probability. $p$ will be very close to 1 and $q = 1 - p$.}
\end{figure}
 

Suppose we have an algorithm $H$ that can learn a superset of $\mathcal{F}$.
Set $\epsilon = \frac{1}{8} \log (3/2)$ and $\delta = \frac{1}{2}$. 
Since we have a 
polynomial algorithm there must be a polynomial bound on the number of states of the target 
$q(\epsilon,\delta, |\Sigma|, k+2, L)$, when there is an upper 
bound on the length of the strings in the sample, $L$. 
This additional
caveat is necessary because the strings in the sample in general can be of unbounded length.
Here we will be considering a sample where all the strings are of length 1.
Fixing these values of $\epsilon,\delta, |\Sigma|$  and $L$  we will have a polynomial in $k$, so 
we can find a value of $k$ such that $2^k > q(\epsilon,\delta, |\Sigma|, k+2)$. 
Denote the smallest such $k$ by $k_0$. Let $N$ be the sample complexity of the 
algorithm $H$ for these values. We can set $p$ to be so close to 1 that $p^N > 0.5$, which means that
with probability greater than 0.5 the sample generated by the target will
consist of $N$ repetitions of the string $a$.
 Let $A_H = (\hat{Q}, \hat{\gamma}, \hat{\tau})$ be the hypothesis automaton produced by the algorithm $H$
 on such a data set. By construction $2^k > |\hat{Q}|$.


It is not enough just to show that for some string $s$ the hypothesis will give a low probability to strings of the form
$bs^i$. We must also show that this probability decreases exponentially as $i$ increases. We must therefore show, using a pumping argument,
that there is a low probability transition in the cycles in the hypothesis automaton traced by the strings for large values of $i$.
We can assume, without loss of generality, 
that the hypothesis assigns a non-zero probability to all the strings $bs^i$, or the KLD will be infinite.
For each string $s \in \Sigma^{k_0}$, consider the states in $\hat{Q}$ defined by
$\hat{\tau}(\hat{q_0}, bs^i)$. 
There must be two distinct values $i < j \leq |\hat{Q}|$ such that
$\hat{\tau}(\hat{q_0}, bs^i) = \hat{\tau}(\hat{q_0}, bs^j)$, by the pigeonhole principle.
Select the smallest $i$ such that this is true, denote these values of $i$ and $j$ by  $s_i$ and $s_j$,
 and let  $q_s$ denote the state  $\hat{\tau}(\hat{q_0}, bs^{s_i})$. By construction
$0 < s_j - s_i \leq |\hat{Q}|$.
 The state $q_s$ will therefore be in a suitable cycle since
\begin{equation*}
q_s = \hat{\tau}(\hat{q_0}, bs^{s_i}) =  \hat{\tau}(\hat{q_0}, bs^{s_j}) = \hat{\tau}(\hat{q_0}, bs^{s_i + k(s_j - s_i)})
\end{equation*}
for all $k \geq 0$.

We now want to show that for some string $s$ there is transition in the cycle with a probability at most $\frac{1}{2}$.
Since the number of strings is larger than $|\hat{Q}|$ there must be two distinct strings,
 $s, s'$, such that $q_s = q_{s'}$. 


We can write $s = u \sigma v$ and $s' = u \sigma' v'$, where $u,v, v' \in \Sigma^*, \sigma, \sigma' \in \Sigma$.
and $\sigma \neq \sigma'$, $u$ here being the longest common prefix of $s$ and $s'$.
Consider the transitions from the state $\hat{\tau}(q_s,u)$. At least one of the two values
$\hat{\gamma}(\hat{\tau}(q_s,u), \sigma)$, $\hat{\gamma}(\hat{\tau}(q_s,u), \sigma')$ must be less than or equal to 0.5.
Without loss of generality we can say it is $\sigma$, which means that $\hat{\gamma}(q_s,s) \leq 1/2$.


This means that we can say the probability of a string of the form $bs^{k |\hat{Q}| + l}$ 
for any $k,l \geq 0$ 
must be less than or equal to $2^{-k}$. For $k=0$ this is trivially true. For $k>0$ 
define  $n = k (|\hat{Q}| + s_i - s_j) + l - s_i \geq 0$ we can write the probability as
\begin{eqnarray*}
\hat{\gamma}(\hat{q_0},bs^{k |\hat{Q}| + l} \zeta)
& = & \hat{\gamma}(q_0, bs^{s_i})  \hat{\gamma}(q_s,s^{s_j - s_i})^k 
   \hat{\gamma}(q_s, s^{n}) \hat{\gamma}(\hat{\tau}(bs^{k |\hat{Q}| + l}), \zeta) \\
& \leq & \hat{\gamma}(q_s,s^{s_j - s_i})^k  \\
& \leq & \hat{\gamma}(q_s,s)^{(s_j - s_i)k}  \\
& \leq &  2^{-k}.
\end{eqnarray*}
We can now use this upper bound on the probability that the hypothesis gives the strings to
lower bound the divergence with respect to the target.


Expanding out the definition of the KLD and the target automaton, we have
\begin{equation*}
D_{KL}(A_p^s, A_H) = p \log \frac{p}{\hat{\gamma}(\hat{q_0}, a \zeta)} +
\sum_{i=0}^{\infty}
\sum_{j=0}^{|\hat{Q}|- 1}
(1-p)^2 p^{i |\hat{Q}| + j}\log \frac{(1-p)^2 p^{i |\hat{Q}| + j}}{\hat{\gamma}(\hat{q_0}, bs^{i |\hat{Q}| + j} \zeta)}.
\end{equation*}
Substituting in the bound above, and the fact that
$\hat{\gamma}(\hat{q_0}, a \zeta) \leq 1$ yields
\begin{eqnarray*}
D_{KL}(A_p^s, A_H) 
& \geq &
 p \log p +
\sum_{i=0}^{\infty}
\sum_{j=0}^{|\hat{Q}|- 1}
(1-p)^2 p^{i |\hat{Q}| + j}\log (1-p)^2 p^{i |\hat{Q}| + j}2^i \\
& \geq &
 p \log p +
|\hat{Q}|
\sum_{i=0}^{\infty}
(1-p)^2 p^{i |\hat{Q}| +|\hat{Q}| }\log (1-p)^2 p^{i |\hat{Q}| + |\hat{Q}|}2^i \\
& \geq &
 p \log p +
|\hat{Q}|
(1-p)^2
p^{|\hat{Q}|}
\left(
\log (1-p)^2 p^{|\hat{Q}|}
\sum_{i=0}^{\infty}
 p^{i |\hat{Q}|}
+
\log 2p^{|\hat{Q}|}
\sum_{i=0}^{\infty}
 i p^{i |\hat{Q}|}
\right).
\end{eqnarray*}
Recall that   $\sum_{i=0}^{\infty}
i p^i = p (1-p)^{-2}$  and  $\sum_{i=0}^{\infty}
p^i = (1-p)^{-1}$, so that
\begin{eqnarray*}
D_{KL}(A_p^s, A_H) 
& \geq &
 p \log p +
|\hat{Q}|
(1-p)^2
p^{|\hat{Q}|}
\left(
\log (1-p)^2 p^{|\hat{Q}|}
(1-  p^{|\hat{Q}|})^{-1}
+
\log 2p^{|\hat{Q}|}
p^{|\hat{Q}|} (1-  p^{|\hat{Q}|})^{-2}
\right).
\end{eqnarray*}
We can take $p$ to be large enough that $p^{|\hat{Q}|} > 3/4$, giving
\begin{eqnarray*}
D_{KL}(A_p^s, A_H) 
& \geq &
 p \log p +
|\hat{Q}|
\frac{(1-p)^2}
{(1-  p^{|\hat{Q}|})}
p^{2|\hat{Q}|}
\left(
\log (1-p)^2 
+
(1-  p^{|\hat{Q}|})^{-1}
\log 3/2
\right).
\end{eqnarray*}
Now if we write $p = (1 - 1/n)$, 
\begin{eqnarray*}
D_{KL}(A_p^s, A_H) 
& \geq &
  \log p +
|\hat{Q}|
\frac{(1-p)^2}
{(1-  p^{|\hat{Q}|})}
p^{2|\hat{Q}|}
\left(
\frac{n}{|\hat{Q}|} \log \frac{3}{2}
- 2 \log n
\right).
\end{eqnarray*}

Now using a simple linear bound on the logarithm it can be shown that for any $\beta > 1 $
if $n > 2 \beta \log 2 \beta$ then $ \log n < n/\beta$. If we set $\beta = 4 |\hat{Q}|/ \log(3/2)$ and 
 $n > 8  |\hat{Q}| \log |\hat{Q}| $,
 and $p^{|\hat{Q}|} > (1 - |\hat{Q}|/n)$
 and assuming that $p > (2/3)^{1/8}$ we have
\begin{eqnarray*}
D_{KL}(A_p^s, A_H) 
& \geq &
  \log p +
|\hat{Q}|
\frac{(1-p)^2}
{(1-  p^{|\hat{Q}|})}
p^{2|\hat{Q}|}
\frac{n}{2|\hat{Q}|}  \log \frac{3}{2} \\
& \geq &
  \log p +
\frac{(1-p)}
{(1-  p^{|\hat{Q}|})}
p^{2|\hat{Q}|}
\frac{1}{2}  \log \frac{3}{2}
 \\
& \geq &
  \log p +
\left(\frac{3}{4}\right)^2
\frac{1}{2} \log \frac{3}{2}
%%   \\
%% & \geq &
%%   \log p +
%%  1/4 \log 3/2 
%% \\
 \geq  \frac{1}{8} \log \frac{3}{2} .
\end{eqnarray*}

Thus for sufficiently large values of $n$, and thus for values of $p$ sufficiently close to 1, there must be an automaton $A_p^s$ 
such that the algorithm will with probability at least 0.5 produce a hypothesis with an error of at least $ \frac{1}{8} \log \frac{3}{2}$.
\hfill{$\blacksquare$}


















%% \section*{Appendix A.}

%% In this appendix we establish our counter-example that justifies our addition of a bound on the expected length of the
%% strings generated from every state. Our basic argument is as follows: 
%% we construct a countable family of automata such
%% that given any sample size N, even exponentially large, 
%% all but finitely many automata in the family will give the same sample set  with probability greater than 0.5. 
%% Given this identical sample set, the algorithm will produce a hypothesis. 
%% We show that whatever hypothesis,
%%  $H$ a learning algorithm produces must have $D(H||T) > 0.5$ for some of the targets in the subset that will generate this same set.   
%% Thus arguing by contradiction, we see that it is not possible to have a PAC-learning algorithm unless we allow it to have a sample complexity polynomial that includes some additional  parameter relating in some way to the expected length.

%% \begin{figure}
%% \begin{center}
%%     \psfrag{a}{\hspace*{-1.1cm}$1- 1/n: a$}    
%%     \psfrag{b}{1: $\zeta$}
%%     \psfrag{c}{\hspace*{-.8cm}$1/n: b$}
%%     \psfrag{e}{$1/n: \zeta$}
%%     \psfrag{d}{$1-1/n: b$}
%%     \includegraphics[scale=0.4]{./aut.eps} \hfil
%%     \psfrag{a}{\hspace*{-1.1cm}$1- 1/n: a$}    
%%     \psfrag{b}{1: $\zeta$}
%%     \psfrag{c}{\hspace*{-.8cm}$1/n: b$}
%%     \psfrag{e}{$1/n: \zeta$}
%%     \psfrag{d}{$1-1/n: a$}
%%     \includegraphics[scale=0.4]{./aut.eps}
%%   \end{center}
%% \caption{The automata $A_n$ and $B_n$. Transition labels of the form $p:a$ mean with
%%     probability $p$ emitting/parsing symbol $a$. } 
%% \label{fig:aut}
%% \end{figure}


%% Figure~\ref{fig:aut} shows a
%%   family of automata $\mathcal{F} = \{A_n, B_n | n \in \N\}$ with 4 states, and an expected length less than 2, over a two-letter alphabet
%%   that are suitable. Intuitively, these automata will with very high probability generate only the string $a$.  Occasionally they will generate a very long string that starts with $b$.
%% Even with exponentially large amounts of data, there are automata
%%   from this family which will produce with high probability only strings of $a$, and yet have high
%%   divergence from any given automata.
%%  %% Suppose there was a learning algorithm that could PAC-learn
%% %%   this class. Suppose for certain values of $\epsilon, \delta$ say $1/2,1/2$ the algorithm could learn this family
%% %%   after $N$ strings. For all but finitely many $n$ the automata will with probability greater than
%% %%   $\delta$ produce only $N$ repetitions of $a$.   It is straightforward to establish that whatever
%% %%   hypothesis is produced by the algorithm when presented with this data, will  have  KLD of more than $1/2$
%% %%  from  many members of the family. 

%% %% New explanation

%% Suppose that there is some algorithm that can KL-PAC learn some superset of $\mathcal{F}$ and that for fixed $\epsilon, \delta$, say $0.5, 0.5$ respectively, the sample complexity polynomial is bounded over the family $\mathcal{F}$. Let us call the bound $N$. Denote by $H$ the hypothesis the learner will produce when given a sample that consists of $N$ repetitions of $a$.  We will show that for all sufficiently large $n$,
%%  $D_{KL}(A_n||H) + D_{KL}(B_n||H) > 1$ regardless of the hypothesis $H$.  
%% Therefore one of $A_n$ or $B_n$ must have divergence from the target of more than $1/2$. Therefore the learner will  fail with high probability either on $A_n$ or $B_n$.

%% To prove that  $D_{KL}(A_n||H) + D_{KL}(B_n||H) > 1$, we
%% shall  use the Carrasco decomposition of the KLD (Equation~\ref{eqn:carrasco}). 
%% For each pair of states $q,\hat{q}$ the sum over the letters must be non-negative, since it is just the KLD between the transition distributions. 
%% Thus we can lower bound the sum of the divergences by examining only the state labelled 1 in Figure~\ref{fig:aut}.
%% So we can say



%% \begin{eqnarray*}
%% D_{KL}(A_n||H) + D_{KL}(B_n||H) 
%% &>& \sum_{\hat{q}} W(q_1,\hat{q}) 
%% \left(
%% (1 -1/n) 
%% \log 
%% \frac{(1 - 1/n)^2}{\hat{\gamma}(\hat{q},a)\hat{\gamma}(\hat{q},b)}
%% +
%% 2/n 
%% \log 
%% \frac{1/n}{\hat{\gamma}(\hat{q},\zeta)}
%% \right)
%% \end{eqnarray*}


%% Since $\hat{\gamma}(\hat{q},a) + \hat{\gamma}(\hat{q},b) \leq 1$, 
%% we know  $\hat{\gamma}(\hat{q},a)\hat{\gamma}(\hat{q},b) \leq 1/4$.
%% Since $\sum_{\hat{q}} W(q,\hat{q}) = W(q)$ and  $W(q_1) = 1$
%% this gives us
%% \begin{equation*}
%% D_{KL}(A_n||H) + D_{KL}(B_n||H) >   (1 -1/n) 
%% \log 
%% 4(1 - 1/n)^2 + 2/n \log 1/n
%% \end{equation*}

%% which,   for $n > 1000$ will be greater than 1 nat. This means that at least one of the two divergences must be greater  than $1/2$.  Therefore we can conclude that for any hypothesis $H$ for sufficiently large $n$, either $D_{KL}(A_n|| H) > 0.5$ or $D_{KL}(B_n|| H) > 0.5$. Since for sufficiently large $N$ with probability greater than 0.5 the two targets would produce the same sample data, the algorithm cannot guarantee that it will probably produce an approximately correct answer, since when it is given the uninformative sample, it must fail. 
%% Therefore, any algorithm must have an additional parameter in its sample complexity polynomial that is unbounded over the family of automata $\mathcal{F}$; we suggest that the only reasonable candidate is the expected length of the strings generated by every state, or some equivalent such as the entropy of the distribution generated from each state. 
%% Note that we have neglected the possibility that the algorithm might be randomised. It is straightforward to extend the proof to deal with this eventuality.
%% %\footnote{Is it?}



\bibliography{inference}


\end{document}

