Cadeias estocásticas com memória de alcance variável

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 uma árvore probabilística de contextos $(\tau ,p)$ , tal que

1. $\tau$ é o conjunto de todos os contextos. Um contexto $X_{n-l},\dots ,X_{n-1}$, sendo $l$ o tamanho do contexto, é uma porção finita do passado $X_{-\mathrm{\infty }},\dots ,X_{n-1}$ que é relevante para predizer o próximo símbolo $X_n$;
2. $p$ é 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” e “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.

Exemplos

Fonte de Luz Interrompida

Considere um sistema composto por uma lâmpada, um observador e uma porta entre ambos. A lâmpada possui dois estados possíveis: acesa, representada por 1, ou apagada, representada por zero. Quando a lâmpada está acesa, o observador pode receber a luz emitida através da porta, que também pode se encontrar em dois estados: aberta, 1, ou fechada, 0. Estes estados independem do estado original da lâmpada.

Seja $(X_n{)}_{n\ge 0}$ uma cadeia de Markov que represente o estado da lâmpada, com valores em $A=0,1$ e com uma matriz de probabilidade de transição $p$. Seja também $({\xi }_n{)}_{n\ge 0}$ uma sequência de variáveis aleatórias independentes que represente o estado da porta, também assumindo valores em $A$, independente da cadeia $(X_n{)}_{n\ge 0}$ e tal que

$\mathbb{P}({\xi }_n=1)=1-ϵ$

onde $0<ϵ<1$. Define-se uma nova sequência $(Z_n{)}_{n\ge 0}$ tal que

$Z_n=X_n{\xi }_n$ para todo $(Z_n{)}_{n\ge 0}$.

Para descobrir o último instante em que o observador conseguiu ver a lâmpada acesa, isto é, identificar o menor instante $k$, com $k<n$ tal que $Z_k=1$.

Utilizando uma árvore de contextos é possível representar os estados passados da sequência, mostrando qual é relevante para identificar o próximo estado.

A cadeia estocástica $(Z_n{)}_{n\in \mathbb{Z}}$ é, então, uma cadeia com memória de alcance variável, assumindo valores em $A$ e compatível com uma árvore probabilística de contextos $(\tau ,p)$, onde

$\tau =\{1,10,100,\cdots \}\cup \{0^{\mathrm{\infty }}\}$.

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

Dada uma amostra $X_l,\dots ,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.

O algoritmo contexto

No artigo A Universal Data Compression System, Rissanen introduziu um algoritmo consistente para estimar a árvore probabilística de contextos finita geradora dos dados. O modo como tal algoritmo funciona pode ser sumarizado em dois passos:

1. Dada um amostra produzida por uma cadeia com memória de alcance variável, começamos com a árvore máxima cujos ramos são todos os candidatos à contextos para a amostra;
2. Os ramos dessa árvore são então podados até se obter a menor árvore que esteja bem adaptada aos dados. A decisão por encurtar ou não o contexto se dá por meio de uma dada função de ganho, como por exemplo, a razão do logaritmo das verossimilhanças.

Vamos à descrição mais formal do algoritmo. Seja $X_0,\dots ,X_{n-1}$ uma amostra de uma árvore probabilística finita $(\tau ,p)$. Para qualquer sequência $x_{-j}^{-1}$ com $j\le n$, denotamos por $N_n(x_{-j}^{-1})$ o número de ocorrências da sequência na amostra, isto é,

$N_n(x_{-j}^{-1})=\sum _{t=0}^{n-j}\mathrm{𝟏}\{X_t^{t+j-1}=x_{-j}^{-1}\}$

Rissanen primeiramente construiu um candidato máximo de contexto, dado por $X_{n-K(n)}^{n-1}$, onde $K(n)=C\log n$ e $C$ uma constante positiva arbitrária. A razão intuitiva para a escolha de $C\log n$ decorre da impossibilidade de estimar as probabilidades de sequência de comprimento maior que $\log n$ baseado em uma amostra de tamanho $n$.

A partir daí, Rissanen encurta o candidato máximo à contexto por meio de sucessivas podas dos ramos de acordo com uma sequência de testes baseados na estatística de razão de verossimilhanças. Para uma definição mais formal, se $\sum _{b\in A}{N}_n(x_{-k}^{-1}b)>0$ defina o estimador da probabilidade de transição $p$ por

${\hat{p}}_n(a|x_{-k}^{-1})=\frac{N_n(x_{-k}^{-1}a)}{\sum _{b\in A}{N}_n(x_{-k}^{-1}b)}$

onde $x_{-j}^{-1}a=(x_{-j},\dots ,x_{-1},a)$. Caso $\sum _{b\in A}{N}_n(x_{-k}^{-1}b)=0$, defina ${\hat{p}}_n(a|x_{-k}^{-1})=1/|A|$.

Para $i\ge 1$ definimos

${\mathrm{\Lambda }}_n(x_{-i}^{-1})=2\sum _{y\in A}\sum _{a\in A}{N}_n(y{x}_{-i}^{-1}a)\log \left[\frac{{\hat{p}}_n(a|x_{-i}^{-1}y)}{{\hat{p}}_n(a|x_{-i}^{-1})}\right]$

onde $y{x}_{-i}^{-1}=(y,x_{-i},\dots ,x_{-1})$ e

${\hat{p}}_n(a|x_{-i}^{-1}y)=\frac{N_n(y{x}_{-i}^{-1}a)}{\sum _{b\in A}{N}_n(y{x}_{-i}^{-1}b)}.$

Note que ${\mathrm{\Lambda }}_n(x_{-i}^{-1})$ é a razão do logaritmo das verossimilhanças para testar a consistência da amostra com a árvore probabilística de contextos $(\tau ,p)$ contra a alternativa que é consistente com $({\tau }^{\prime },p^{\prime })$, onde $\tau$ e ${\tau }^{\prime }$ diferem apenas por um conjunto de nós irmãos.

O comprimento do atual contexto estimado é então definido por

${\hat{\ell }}_n(X_0^{n-1})=\max \{i=1,\dots ,K(n):{\mathrm{\Lambda }}_n(X_{n-i}^{n-1})>C\log n\}$

onde $C$ é qualquer constante positiva. Por fim, por Rissanen(1983) temos o seguinte resultado. Dada uma realização $X_0,\dots ,X_{n-1}$ de uma árvore probabilística de contextos $(\tau ,p)$ finita, então

$P({\hat{\ell }}_n(X_0^{n-1})\ne \ell (X_0^{n-1}))⟶0,$

quando $n\to \mathrm{\infty }$.

Critério de informação Bayesiana (BIC)

O estimador da árvore de contexto pelo BIC com constante penalizadora $c>0$ é definido como

${\hat{\tau }}_{BIC}=\underset{\tau \in {𝒯}_n}{\arg \max }\{\log L_{\tau }(X_1^n)-c\text{df}(\tau )\log n\}$

Critério do menor maximizador (SMC)

O critério do menor maximizador se dá ao selecionar a menor árvore $\hat{\tau }$ de um conjunto de árvores $C$ tal que

$\underset{n\to \mathrm{\infty }}{\lim }\frac{\log L_{\tau }(X_1^n)-\log L_{\hat{\tau }}(X_1^n)}{n}=0$

Ver também

• Processo estocástico
• Cadeias de Markov