Disciplina Discipline MAE5903
Cadeias Estocásticas com Memória de Alcance Variável

Stochastic Chains With Memory of Variable Length

Área de Concentração: 45133

Concentration area: 45133

Criação: 14/12/2018

Creation: 14/12/2018

Ativação: 14/12/2018

Activation: 14/12/2018

Nr. de Créditos: 8

Credits: 8

Carga Horária:

Workload:

Teórica

(por semana)

Theory

(weekly)

Prática

(por semana)

Practice

(weekly)

Estudos

(por semana)

Study

(weekly)

Duração Duration Total Total
4 2 4 12 semanas 12 weeks 120 horas 120 hours

Docente Responsável:

Professor:

Jefferson Antonio Galves

Objetivos:

O objetivo do curso é apresentar uma introdução auto-suficiente à classe de cadeias estocásticas de memória de alcance variável.

Objectives:

The goal of the course is to present a self-contained introduction to the class of Stochastic Chains with Memory of Variable Length.

Justificativa:

Cadeias com memória de alcance variável são interessantes tanto de um ponto de vista puramente probabilístico, quanto do ponto de vista da estatística teórica e aplicada. Do ponto de vista probabilístico elas constituem de um quadro de referência natural conectando cadeias de Markov e cadeias de ordem infinita. Do ponto de vista estatístico a identificação das árvores de `contexto` caracterizando as dependências temporais foi abordada por diversos autores e está na origem de importantes desenvolvimentos na área de seleção estatística de modelos. Cadeias com memória de alcance variável e suas recentes extensões também se revelaram ferramentas performantes em estatística aplicada, obtendo de forma eficiente classificações e predições em proteômica, genômica, neurobiologia, linguistica, etc.

Rationale:

Stochastic Chains with Memory of Variable Length are interesting both from a purely probabilistic point of view, and from a theoretical and applied statistical point of view. From the probabilistic point of view they constitute the natural framework connecting Markov chains to stochastic chains of infinite order. From a statistical point of view the identification of the tree of “contexts” characterising the temporal dependencies of the chain has been addressed by many authors and is at the origin of important developments in the field of statistical model selection. Chains with memory of variable length and their recent extensions also revealed to be very performing tools in applied statistics, by achieving in an efficient way classification and prediction tasks in proteomics, genomics, neurobiology, linguistics, etc.

Conteúdo:

1. Introdução e motivação: compressão de dados, cadeias parcimoniosas, cadeias de Markov observadas de forma imperfeita. Motivações neurobiológicas: sistemas de disparos de neurônios, e sequências de dados de EEG obtidos enquanto um voluntário é exposto à uma sequência de estímulos. 2. Propriedades matemáticas, definições básicas e fatos. Árvores de contexto probabilísticas, definição de uma cadeia através de partições do passado, a propriedade sufixo, função do alcance do contexto. Resultados sobre a existência e singularidade para cadeias de memória de alcance variável e cadeias de ordem infinita. Estrutura regenerativa, decomposição de Kalikow e simulação perfeita. 3. Seleção de modelos de árvores de contexto com memória de alcance variável. O algoritmo "contexto", critério de informação bayesiana (BIC). Desigualdades de concentração. O critério MDL (menor comprimento de descrição) . Seleção de modelos de constantes livres. O critério do menor maximizador (`smallest maximizer criterion SMC`) para cadeias com memória variável limitada. 4. Sistemas infinitos de cadeias interagindo com memória de alcance variável. Modelos estocástica para redes neurais biológica. Decomposição de Kalikow e simulação perfeita. De- correlação de intervalos inter-disparos consecutivos. Atribuição de árvores de contexto para sequências de disparos. Seleção estatística de modelos: estimação da vizinhança de interação de um determinado neurônio. 5. Sequências de objetos aleatórios conduzidas por modelos de árvores de contexto.

Content:

1. Introduction and motivation: data compression, parsimonious chains, Imperfecttly observed Markov chains. Neurobiological motivations: systems of spiking neurons and sequences of EEG data recorded while the volunteer is exposed to a sequence of stimuli. 2. Mathematical properties, basic definitions and facts. Probabilistic context trees, definition of a chain through a partition of the past, the suffix property, context length function. Existence and uniqueness results for chains of variable length and chains of infinite order. Regenerative structure, Kalikow-type decomposition and perfect simulation. 3. Context tree model selection for chains with memory of bounded variable length. The algorithm ``Context'', the Bayesian information criterion (BIC). Concentration inequalities. The minimum description length (MDL) point of view. Constant free model selection. The smallest maximizer criterion (SMC) for chains with bounded variable range. 4. Infinite systems of interacting chains with memory of variable length. Stochastic models for biological neural nets. Kalikow decomposition and perfect simulation. De-correlation of consecutive interspike intervals. Assigning context trees to spike trains. Statistical model selection: estimating the interaction neighborhood of a given neuron. 5. Sequences of random objects driven by context tree models.

Forma de Avaliação:

Média de provas, listas de exercícios, seninários e trabalhos práticos.

Type of Assessment:

Test, exercises, seminars and projects.

Observação:

(em inglês):

Notes/Remarks:

(em inglês):

Bibliografia:

[1]. P. B uhlmann and A. J. Wyner. Variable length Markov chains. Ann. Statist., 27(2):480- 513, 1999. [2]. I. Csisz ar and Z. Talata. Context tree estimation for not necessarily finite memory processes, via BIC and MDL. IEEE Trans. Inf. Theory, 52(3):1007-1016, 2006. [3]. A. Duarte, A. Galves, R. Fraiman, G. Ost, and C. D. Vargas. Context tree selection for functional data. arXiv1602.00579, 2016. [4]. A. Duarte, A. Galves, E. L ocherbach, and G. Ost. Estimating the interaction graph of stochastic neural dynamics. to appear in. Bernoulli, 2018. [5]. S. Gallo. Chains with unbounded variable length memory: perfect simulation and visible regeneration scheme. Adv. Appl. Probab., 43:735-759, 2011. [6]. A. Galves, C. Galves, J. Garcia, N.L. Garcia, and F. Leonardi. Context tree selection and linguistic rhythm retrieval from written texts. Ann. Appl. Statistics, 6:186-209, 2012. [7]. A. Galves and F. Leonardi. Exponential inequalities for empirical unbounded context trees, volume 60 of Prog. Prob., pages 257-270. Springer, 2008. [8]. A. Galves and E. Loecherbach. Stochastic chains with memory of variable length., pages 117-133. TICSP Series vol. 38, 2008. [9]. A. Galves and E. Loecherbach. Infinite systems of interacting chains with memory of variable length a stochastic model for biological neural nets. Journal of Statistical Physics, 151(5):896-921, 2013. [10]. A. Galves and E. Loecherbach. Modeling networks of spiking neurons as interacting processes with memory of variable length. Journal de la Soci et e Fran caise de Statistiques, 157:17-32, 2016. [11]. A. Garivier and F. Leonardi. Context tree selection: A unifying view. Stoc. Proc. Appl., 121:2488{2506, 2011. [12]. J. Rissanen. A universal data compression system. IEEE Trans. Inform. Theory, 29(5):656-664, 1983.

Bibliography:

[1]. P. Buhlmann and A. J. Wyner. Variable length Markov chains. Ann. Statist., 27(2):480- 513, 1999. [2]. I. Csiszar and Z. Talata. Context tree estimation for not necessarily finite memory processes, via BIC and MDL. IEEE Trans. Inf. Theory, 52(3):1007-1016, 2006. [3]. A. Duarte, A. Galves, R. Fraiman, G. Ost, and C. D. Vargas. Context tree selection for functional data. arXiv1602.00579, 2016. [4]. A. Duarte, A. Galves, E. L ocherbach, and G. Ost. Estimating the interaction graph of stochastic neural dynamics. to appear in. Bernoulli, 2018. [5]. S. Gallo. Chains with unbounded variable length memory: perfect simulation and visible regeneration scheme. Adv. Appl. Probab., 43:735-759, 2011. [6]. A. Galves, C. Galves, J. Garcia, N.L. Garcia, and F. Leonardi. Context tree selection and linguistic rhythm retrieval from written texts. Ann. Appl. Statistics, 6:186-209, 2012. [7]. A. Galves and F. Leonardi. Exponential inequalities for empirical unbounded context trees, volume 60 of Prog. Prob., pages 257-270. Springer, 2008. [8]. A. Galves and E. Loecherbach. Stochastic chains with memory of variable length., pages 117-133. TICSP Series vol. 38, 2008. [9]. A. Galves and E. Loecherbach. Infinite systems of interacting chains with memory ofvariable length a stochastic model for biological neural nets. Journal of Statistical Physics, 151(5):896-921, 2013. [10]. A. Galves and E. Loecherbach. Modeling networks of spiking neurons as interacting processes with memory of variable length. Journal de la Soci et e Fran caise de Statistiques, 157:17-32, 2016. [11]. A. Garivier and F. Leonardi. Context tree selection: A unifying view. Stoc. Proc. Appl., 121:2488{2506, 2011. [12]. J. Rissanen. A universal data compression system. IEEE Trans. Inform. Theory, 29(5):656-664, 1983.