Usuário(a):Avertere/Testes

Cadeias estocásticas com memória de alcance variável constituem uma família de cadeias estocásticas de ordem finita em um alfabeto finito. A ideia é que, para cada passado, apenas um sufixo finito do passado, chamado contexto, é suficiente para predizer o próximo símbolo. Esses modelos foram introduzidos na literatura da teoria da informação por Jorma Rissanen, em 1983, como uma ferramenta universal para a compressão de dados. Recentemente, elas têm sido usadas para modelar dados em diferente áreas, como biologia, linguística, e música .

Definicão

Uma cadeia com memória de alcance variável é uma cadeia estocástica $(X_{n})_{n\in Z}$, tomando valores em um alfabeto finito $A$ e caracterizada por dois elementos.

1. O conjunto de todos os contextos. Um contexto $X_{n-l},\ldots ,X_{n-1}$ é uma porção finita do passado $X_{-\infty },\ldots ,X_{n-1}$ que é relevante para predizer o próximo símbolo $X_{n}$
2. Uma família de probabilidade de transição associada a cada contexto.

História

A classe das cadeias estocásticas com memória de alcance variável foi introduzida em 1983 por Jorma Rissanen, no artigo A universal system for data compression system. Essa classe de cadeias estocásticas foi popularizada na comunidade estatística e probabilística por P. Bühlmann e A. J. Wyner, em 1999, no artigo Variable Length Markov Chains. Chamadas por Bühlmann e Wyner de “cadeias de Markov de alcance variável" (em inglês, VLMC, sigla de "Variable length Markov chains"), essas cadeias também são conhecidas por "Modelos de Markov de ordem variável" (em inglês, VOM, da sigla de "Variable order Markov Models"), “Árvores probabilísticas de sufixos”, por Bejerano; “Modelos gerados por árvores de contexto” (Em inglês, “Context tree models”`). A designação “Cadeias estocásticas com memória de alcance variável” parece ter sido introduzida por Galves e Löcherbach, em 2008, no artigo Stochastic chains with memory of variable length .

Inferência em cadeias com memória de alcance variável

Dada uma amostra $X_{l},\ldots ,X_{n}$, como encontrar a árvore de contexto adequada? Os principais algoritmos já formulados para a solução desse problema são apresentados a seguir.