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, ^[1] como uma ferramenta universal para a compressão de dados. Recentemente, elas têm sido usadas para modelar dados em diferente áreas, como biologia,^[2] linguística,^[3] e música.^[4]

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

$\tau$ é o conjunto de todos os contextos. Um contexto $X_{n-l},\ldots ,X_{n-1}$ , sendo $l$ o tamanho do contexto, é uma porção finita do passado $X_{-\infty },\ldots ,X_{n-1}$ que é relevante para predizer o próximo símbolo $X_{n}$ ;
$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.^[1] 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” ^[2] e “Modelos gerados por árvores de contexto”^[5] (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.^[6]

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\geq 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\geq 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\geq 0}$ e tal que

$\mathbb {P} (\xi _{n}=1)=1-\epsilon$

onde $0<\epsilon <1$ . Define-se uma nova sequência $(Z_{n})_{n\geq 0}$ tal que

$Z_{n}=X_{n}\xi _{n}$ para todo $(Z_{n})_{n\geq 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^{\infty }\}$ .

Propriedades probabilísticas

Existência

Simulação perfeita

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.

O algoritmo contexto

No artigo A Universal Data Compression System,^[1] 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:

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;
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},\ldots ,X_{n-1}$ uma amostra de uma árvore probabilística finita $(\tau ,p)$ . Para qualquer sequência $x_{-j}^{-1}$ com $j\leq 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}\mathbf {1} \left\{X_{t}^{t+j-1}=x_{-j}^{-1}\right\}$

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},\ldots ,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\geq 1$ definimos

$\Lambda _{n}(x_{-i}^{-1})\,=\,2\,\sum _{y\in A}\sum _{a\in A}N_{n}(yx_{-i}^{-1}a)\log \left[{\frac {{\hat {p}}_{n}(a|x_{-i}^{-1}y)}{{\hat {p}}_{n}(a|x_{-i}^{-1})}}\right]\,$

onde $yx_{-i}^{-1}=(y,x_{-i},\ldots ,x_{-1})$ e

${\hat {p}}_{n}(a|x_{-i}^{-1}y)={\frac {N_{n}(yx_{-i}^{-1}a)}{\sum _{b\in A}N_{n}(yx_{-i}^{-1}b)}}.$

Note que $\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 ',p')$ , onde $\tau$ e $\tau '$ 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 \left\{i=1,\ldots ,K(n):\Lambda _{n}(X_{n-i}^{n-1})\,>\,C\log n\right\}\,$

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

$P\left({\hat {\ell }}_{n}(X_{0}^{n-1})\neq \ell (X_{0}^{n-1})\right)\longrightarrow 0,$

quando $n\rightarrow \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 {\mathcal {T}}_{n}}{\arg \max }}\{\log {L_{\tau }(X_{1}^{n})-c{\textrm {df}}(\tau )\log {n}}\}$

Critério do menor maximizador (SMC)

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

$\lim _{n\to \infty }{\frac {\log L_{\tau }(X_{1}^{n})-\log L_{\hat {\tau }}(X_{1}^{n})}{n}}=0$

Ver também

Referências

↑ ^a ^b ^c ^d Rissanen, J (setembro de 1983). «A Universal Data Compression System». IEEE Transactions on Information Theory. 29 (5): 656–664. doi:10.1109/TIT.1983.1056741
↑ ^a ^b Bejenaro, G (2001). «Variations on probabilistic suffix trees: statistical modeling and prediction of protein families». Bioinformatics. 17 (5): 23-43. doi:10.1093/bioinformatics/17.1.23
↑ ^a ^b Galves, A; Galves, C; García, J; Garcia, N L; Leonardi, F (2012). «Context tree selection and linguistic rhythm retrieval from written texts». The Annals of Applied Statistics. 6 (5): 186-209. doi:10.1214/11-AOAS511
↑ Dubnov, S; Assayag, G; Lartillot, O; Bejenaro G (2003). «Using machine-learning methods for musical style modeling». Computer. 36 (10): 73-80. doi:10.1109/MC.2003.1236474
↑ Galves, A; Garivier, A; Gassiat, E (2012). «Joint estimation of intersecting context tree models». Scandinavian Journal of Statistics. 40 (2): 344-362. doi:10.1111/j.1467-9469.2012.00814.x
↑ Galves, A; Löcherbach, E (2008). «Stochastic chains with memory of variable length». TICSP Series. 38: 117-133

[Rissanen-1] Rissanen, J (setembro de 1983). «A Universal Data Compression System». IEEE Transactions on Information Theory. 29 (5): 656–664. doi:10.1109/TIT.1983.1056741

[Bejenaro-2] Bejenaro, G (2001). «Variations on probabilistic suffix trees: statistical modeling and prediction of protein families». Bioinformatics. 17 (5): 23-43. doi:10.1093/bioinformatics/17.1.23

[Galves-3] Galves, A; Galves, C; García, J; Garcia, N L; Leonardi, F (2012). «Context tree selection and linguistic rhythm retrieval from written texts». The Annals of Applied Statistics. 6 (5): 186-209. doi:10.1214/11-AOAS511

[Dubnov-4] Dubnov, S; Assayag, G; Lartillot, O; Bejenaro G (2003). «Using machine-learning methods for musical style modeling». Computer. 36 (10): 73-80. doi:10.1109/MC.2003.1236474

[Galves2-5] Galves, A; Garivier, A; Gassiat, E (2012). «Joint estimation of intersecting context tree models». Scandinavian Journal of Statistics. 40 (2): 344-362. doi:10.1111/j.1467-9469.2012.00814.x

[Galves3-6] Galves, A; Löcherbach, E (2008). «Stochastic chains with memory of variable length». TICSP Series. 38: 117-133

[1]

[2]

[3]

[4]

[5]

[6]

v d e Processos estocásticos
Tempo discreto	Cadeias de Markov Passeio aleatório Autoevitante Processo de Bernoulli Processo de Galton–Watson Processo de Moran Variáveis aleatórias independentes e identicamente distribuídas
Tempo contínuo	Processo de Bessel Movimento browniano Ponte Excursão Fracionário Geométrico Meander Processo de Cauchy Processo de Cox Processo de Feller Processo de Fleming–Viot Processo de Hunt Difusão de Itô Processo de Itô Processo Lévy Tempo local Processo aditivo de Markov Processo de McKean–Vlasov Processo Ornstein–Uhlenbeck Processo de Poisson Evolução de Schramm–Loewner Processo de Wiener Processo de nascimento e morte Processo de contato Passeio aleatório de tempo contínuo Processo empírico Difusão de salto
Ambos	Processo gaussiano Modelo Galves-Löcherbach Cadeias estocásticas com memória de alcance variável Modelo oculto de Markov Processo de Markov Martingale Ruído branco Processo regenerativo
Campos e outros	Processo de Dirichlet Medida de Gibbs Modelo de Hopfield Modelo de Ising Modelo de Potts Campo aleatório de Markov Processo de Pitman–Yor Grafo aleatório
Modelos de série temporal	Modelos ARCH ARIMA ARMA
Modelos financeiros	Black–Derman–Toy Black–Karasinski Chen Cox–Ingersoll–Ross (CIR) Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White LIBOR market Rendleman–Bartter SABR volatility Vašíček Wilkie
Modelos atuariais	Bühlmann Cramér–Lundberg Sparre–Anderson
Modelos de filas	Fila M/M/1
Propriedades	Càdlàg Processo contínuo de Feller Gauss–Markov Markov Contínuo Reversível no tempo
Teoremas limites	Teorema central do limite Teorema de Donsker Teoria ergódica Teorema de Fisher–Tippett–Gnedenko Lei dos grandes números Lei do logaritmo iterado Teorema de Sanov
Desigualdades	Burkholder–Davis–Gundy Kunita–Watanabe Martingale de Doob
Ferramentas	Fórmula de Cameron–Martin Convergência de variáveis aleatórias Exponencial de Doléans-Dade Teorema da decomposição de Doob–Meyer Fórmula de Dynkin Fórmula de Feynman–Kac Teorema de Girsanov Integral de Itô Lema de Itō Teorema da continuidade de Kolmogorov Teorema da extensão de Kolmogorov Métrica de Lévy–Prokhorov Teorema de Prokhorov Integral de Skorokhod Teorema da representação de Skorokhod Espaço de Skorokhod Equação diferencial estocástica Tanaka Integral de Stratonovich Espaço de Wiener Clássico Abstrato Princípio da reflexão
Disciplinas	Ciências atuariais Econometria Teoria ergódica Matemática financeira Teoria das probabilidades Teoria das filas Estatística Cálculo estocástico Série temporal Aprendizado de máquina
Categoria:Processos estocásticos