Markov approximation and consistent estimation of unbounded probabilistic suffix trees

D Duarte, A Galves, NL Garcia - Bulletin of the Brazilian Mathematical …, 2006 - Springer
D Duarte, A Galves, NL Garcia
Bulletin of the Brazilian Mathematical Society, 2006Springer
We consider infinite order chains whose transition probabilities depend on a finite suffix of
the past. These suffixes are of variable length and the set of the lengths of all suffix is
unbounded. We assume that the probability transitions for each of these suffixes are
continuous with exponential decay rate. For these chains, we prove the weak consistency of
a modification of Rissanen's algorithm Context which estimates the length of the suffix
needed to predict the next symbol, given a finite sample. This generalizes to the unbounded …
Abstract
We consider infinite order chains whose transition probabilities depend on a finite suffix of the past. These suffixes are of variable length and the set of the lengths of all suffix is unbounded. We assume that the probability transitions for each of these suffixes are continuous with exponential decay rate. For these chains, we prove the weak consistency of a modification of Rissanen's algorithm Context which estimates the length of the suffix needed to predict the next symbol, given a finite sample. This generalizes to the unbounded case the original result proved for variable length Markov chains in the seminal paper Rissanen (1983). Our basic tool is the canonical Markov approximation which enables to approximate the chain of infinite order by a sequence of variable length Markov chains of increasing order. Our proof is constructive and we present an explicit decreasing upper bound for the probability of wrong estimation of the length of the current suffix.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果