Joint estimation of intersecting context tree models

Abstract

We study a problem of model selection for data produced by two different context tree sources. Motivated by linguistic questions, we consider the case where the probabilistic context trees corresponding to the two sources are finite and share many of their contexts. In order to understand the differences between the two sources, it is important to identify which contexts and which transition probabilities are specific to each source. We consider a class of probabilistic context tree models with three types of contexts: those which appear in one, the other, or both sources. We use a BIC penalized maximum likelihood procedure that jointly estimates the two sources. We propose a new algorithm which efficiently computes the estimated context trees. We prove that the procedure is strongly consistent. We also present a simulation study showing the practical advantage of our procedure over a procedure that works separately on each dataset.

References in corpus (5)

• On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems
• Context tree selection and linguistic rhythm retrieval from written texts
• Testing statistical hypothesis on random trees and applications to the protein classification problem
• Optimism in Reinforcement Learning and Kullback-Leibler Divergence
• Joint estimation of intersecting context tree models

Cited by in corpus (8)

• A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
• Time-uniform, nonparametric, nonasymptotic confidence sequences
• Informational Confidence Bounds for Self-Normalized Averages and Applications
• Joint estimation of intersecting context tree models
• Learning the distribution with largest mean: two bandit frameworks
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
• Stochastic processes with random contexts: a characterization, and adaptive estimators for the transition probabilities
• Oracle approach and slope heuristic in context tree estimation