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

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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[editar | editar código-fonte]

Uma cadeia com memória de alcance variável é uma cadeia estocástica , tomando valores em um alfabeto finito e caracterizada por uma árvore probabilística de contextos , tal que

  1. é o conjunto de todos os contextos. Um contexto , sendo o tamanho do contexto, é uma porção finita do passado que é relevante para predizer o próximo símbolo ;
  2. é uma família de probabilidade de transição associada a cada contexto.

História[editar | editar código-fonte]

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[editar | editar código-fonte]

Fonte de Luz Interrompida[editar | editar código-fonte]

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 uma cadeia de Markov que represente o estado da lâmpada, com valores em e com uma matriz de probabilidade de transição . Seja também uma sequência de variáveis aleatórias independentes que represente o estado da porta, também assumindo valores em , independente da cadeia e tal que

onde . Define-se uma nova sequência tal que

para todo .

Para descobrir o último instante em que o observador conseguiu ver a lâmpada acesa, isto é, identificar o menor instante , com tal que .

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 é, então, uma cadeia com memória de alcance variável, assumindo valores em e compatível com uma árvore probabilística de contextos , onde

.

Propriedades probabilísticas[editar | editar código-fonte]

Existência[editar | editar código-fonte]

Simulação perfeita[editar | editar código-fonte]

Inferência em cadeias com memória de alcance variável[editar | editar código-fonte]

Dada uma amostra , 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[editar | editar código-fonte]

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:

  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 uma amostra de uma árvore probabilística finita . Para qualquer sequência com , denotamos por o número de ocorrências da sequência na amostra, isto é,

Rissanen primeiramente construiu um candidato máximo de contexto, dado por , onde e uma constante positiva arbitrária. A razão intuitiva para a escolha de decorre da impossibilidade de estimar as probabilidades de sequência de comprimento maior que baseado em uma amostra de tamanho .

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 defina o estimador da probabilidade de transição por

onde . Caso , defina .

Para definimos

onde e

Note que é a razão do logaritmo das verossimilhanças para testar a consistência da amostra com a árvore probabilística de contextos contra a alternativa que é consistente com , onde e diferem apenas por um conjunto de nós irmãos.

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

onde é qualquer constante positiva. Por fim, por Rissanen(1983)[1] temos o seguinte resultado. Dada uma realização de uma árvore probabilística de contextos finita, então

quando .

Critério de informação Bayesiana (BIC)[editar | editar código-fonte]

O estimador da árvore de contexto pelo BIC com constante penalizadora é definido como

Critério do menor maximizador (SMC)[editar | editar código-fonte]

O critério do menor maximizador [3] se dá ao selecionar a menor árvore de um conjunto de árvores tal que

Ver também[editar | editar código-fonte]

Referências

  1. 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 
  2. 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 
  3. 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 
  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 
  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 
  6. Galves, A; Löcherbach, E (2008). «Stochastic chains with memory of variable length». TICSP Series. 38: 117-133