"A simple linear algebraic explanation of the algorithm in "A Spectral Algorithm for Learning Hidden Markov Models" (COLT 2009). Most of the content is in Figure 2; the text just makes everything precise in four nearly-trivial claims."

"Hidden Markov Models (HMMs) can be accurately approximated using co-occurrence frequencies of pairs and triples of observations by using a fast spectral method in contrast to the usual slow methods like EM or Gibbs sampling. We provide a new spectral method which significantly reduces the number of model parameters that need to be estimated, and generates a sample complexity that does not depend on the size of the observation vocabulary. We present an elementary proof giving bounds on the relative accuracy of probability estimates from our model. (Correlaries show our bounds can be weakened to provide either L1 bounds or KL bounds which provide easier direct comparisons to previous work.) Our theorem uses conditions that are checkable from the data, instead of putting conditions on the unobservable Markov transition matrix."

"For independent $d$-variate random samples $X_1, cdots, X_{n_1}$ i.i.d. $f(x), Y_1, cdots, Y_{n_2}$ i.i.d. $g(x)$, where the densities $f$ and $g$ are assumed to be continuous a.e., consider the number $T$ of all $k$ nearest neighbor comparisons in which observations and their neighbors belong to the same sample. We show that, if $f = g$ a.e., the limiting (normal) distribution of $T$, as $min(n_1, n_2) rightarrow infty, n_1/(n_1 + n_2) rightarrow tau, 0 < tau < 1$, does not depend on $f$. An omnibus procedure for testing the hypothesis $H_0: f = g$ a.e. is obtained by rejecting $H_0$ for large values of $T$. The result applies to a general distance (generated by a norm on $mathbb{R}^d$) for determining nearest neighbors, and it generalizes to the multisample situation."

"We describe Information Forests, an approach to classification that generalizes Random Forests by replacing the splitting criterion of non-leaf nodes from a discriminative one -- based on the entropy of the label distribution -- to a generative one -- based on maximizing the information divergence between the class-conditional distributions in the resulting partitions. The basic idea consists of deferring classification until a measure of "classification confidence" is sufficiently high, and instead breaking down the data so as to maximize this measure. In an alternative interpretation, Information Forests attempt to partition the data into subsets that are "as informative as possible" for the purpose of the task, which is to classify the data. Classification confidence, or informative content of the subsets, is quantified by the Information Divergence. Our approach relates to active learning, semi-supervised learning, mixed generative/discriminative learning."

After reading: meh.

"We propose four approaches to estimating the directed information rate between a pair of jointly stationary ergodic processes with the help of universal probability assignments. The four approaches yield estimators with different merits such as nonnegativity and boundedness. We establish consistency of these estimators in various senses and derive near-optimal rates of convergence in the minimax sense under mild conditions. The estimators carry over directly to estimating other information measures of stationary ergodic processes, such as entropy rate and mutual information rate, and provide alternatives to classical approaches in the existing literature. Guided by the theoretical results, we use context tree weighting as the vehicle for the implementations of the proposed estimators. Experiments on synthetic and real data are presented, demonstrating the potential of the proposed schemes in practice and the efficacy of directed information estimation as a tool for detecting and measuring causality and delay."

"We describe an adaptive context tree weighting (ACTW) algorithm, as an extension to the standard context tree weighting (CTW) algorithm. Unlike the standard CTW algorithm, which weights all observations equally regardless of the depth, ACTW gives increasing weight to more recent observations, aiming to improve performance in cases where the input sequence is from a non-stationary distribution. Data compression results show ACTW variants improving over CTW on merged files from standard compression benchmark tests while never being significantly worse on any individual file."

"We suggest new recursive formulas to compute the exact value of the Kullback-Leibler distance (KLD) between two general Hidden Markov Trees (HMTs). For homogeneous HMTs with regular topology, such as homogeneous Hidden Markov Models (HMMs), we obtain a closed-form expression for the KLD when no evidence is given. We generalize our recursive formulas to the case of HMMs conditioned on the observable variables. Our proposed formulas are validated through several numerical examples in which we compare the exact KLD value with Monte Carlo estimations."

"This paper describes the Context Tree Switching technique, a modification of Context Tree Weighting for the prediction of binary, stationary, n-Markov sources. By modifying Context Tree Weighting's recursive weighting scheme, it is possible to mix over a strictly larger class of models without increasing the asymptotic time or space complexity of the original algorithm. We prove that this generalization preserves the desirable theoretical properties of Context Tree Weighting on stationary n-Markov sources, and show empirically that this new technique leads to consistent improvements over Context Tree Weighting as measured on the Calgary Corpus."

"The present paper has two goals. First to present a natural example of a new class of random fields which are the variable neighborhood random fields. The example we consider is a partially observed nearest neighbor binary Markov random field. The second goal is to establish sufficient conditions ensuring that the variable neighborhoods are almost surely finite. We discuss the relationship between the almost sure finiteness of the interaction neighborhoods and the presence/absence of phase transition of the underlying Markov random field. In the case where the underlying random field has no phase transition we show that the finiteness of neighborhoods depends on a specific relation between the noise level and the Dobrushin coefficient. The case in which there is phase transition is addressed in the frame of the ferromagnetic Ising model. We prove that the existence of infinite interaction neighborhoods depends on the phase. The first result has a probabilistic proof using a Kalikow type decomposition of a Glauber dynamics associated to the field. The second result is proved using cluster expansion."

"We prove that uniqueness of the stationary chain compatible with an attractive regular probability kernel is equivalent to the following two assertions for this chain: (1) it is a finitary coding of an i.i.d. process with discrete state space, (2) the concentration of measure holds at exponential rate. We show in particular that if a stationary chain is uniquely defined by a kernel which is continuous and attractive, then this chain can be sampled using a coupling-from-the-past algorithm. For the original Bramson-Kalikow model we further prove that there exists a unique compatible chain if and only if the chain is a finitary coding of a finite alphabet i.i.d. process. Finally, we obtain some partial results on conditions for phase transition for general chains of infinite order."

Published version: J. Stat. Phys., 118 (2005): 555--588. Changes seem minor.

"We treat observable operator models (OOM) and their non-commutative generalisation, which we call NC-OOMs. A natural characteristic of a stochastic process in the context of classical OOM theory is the process dimension. We investigate its properties within the more general formulation, which allows to consider process dimension as a measure of complexity of non-commutative processes: We prove lower semi-continuity, and derive an ergodic decomposition formula. Further, we obtain results on the close relationship between the canonical OOM and the concept of causal states which underlies the definition of statistical complexity. In particular, the topological statistical complexity, i.e. the logarithm of the number of causal states, turns out to be an upper bound to the logarithm of process dimension."

Huh, sounds like they're using tetrad equations?

"Chains of infinite order are generalizations of Markov chains that constitute a flexible class of models in the general theory of stochastic processes. These processes can be naturally studied using approximating Markov chains. Here we derive new upper bounds for the $bar{d}$-distance and the K"ullback-Leibler divergence between chains of infinite order and their canonical $k$-step Markov approximations. In contrast to the bounds available in the literature our results apply to chains of infinite order compatible with general classes of probability kernels. In particular, we allow kernels with discontinuities and null transition probabilities.""  (Pedantry: Pretty sure Kullback did not spell his name with an umlaut!)

From 1981 but perhaps still worth looking at?

"We introduce a new clustering method based on unsupervised binary trees. It is a three stages procedure, which performs on a first stage recursive binary splits reducing the heterogeneity of the data within the new subsamples. On the second stage (pruning) adjacent nodes are considered to be aggregated. Finally, on the third stage (joining) similar clusters are joined even if they do not descend from the same node. Consistency results are obtained and the procedure is tested on simulated and real data sets"

"Hsu et al.(2009) recently proposed an efficient, accurate spectral learning algorithm for Hidden Markov Models (HMMs). In this paper we relax their assumptions and prove a tighter finite-sample error bound for the case of Reduced-Rank HMMs, i.e., HMMs with low-rank transition matrices. Since rank-k RR-HMMs are a larger class of models than k-state HMMs while being equally efficient to work with, this relaxation greatly increases the learning algorithm's scope. In addition, we generalize the algorithm and bounds to models where multiple observations are needed to disambiguate state, and to models that emit multivariate real-valued observations. Finally we prove consistency for learning Predictive State Representations, an even larger class of models. Experiments on synthetic data and a toy video, as well as on difficult robot vision data, yield accurate models that compare favorably with alternatives in simulation quality and prediction accuracy."

Growing-order Markov approximations to the non-Markov ergodic process.  Assumes all predictive probabilities are > 0, and a sort of continuity property for the predictive distribution.  This rules out many interesting processes (e.g., even process) --- could proofs be modified?

???? How is a VLMC not a source by definition? I can't tell what on earth they're doing from their abstract...

For "reset word", read "synchronizing word".

Less interesting than it sounded.

"This paper is composed of two main results concerning chains of infinite order which are not necessarily continuous. The first one is a decomposition of the transition probability kernel as a countable mixture of unbounded probabilistic context trees. This decomposition is used to design a simulation algorithm which works as a combination of the algorithms given by Comets et al. (2002) and Gallo (2009). The second main result gives sufficient conditions on the kernel for this algorithm to stop after an almost surely finite number of steps. Direct consequences of this last result are existence and uniqueness of the stationary chain compatible with the kernel."

"Suitable sequentially rejective multiple test procedures allow to “zoom in" on clusters of relevant variables in high-dimensional regression (Meinshausen [7]), or on regions of interest in some search space (Heinrich et al. [3]; Meinshausen et al. [8]). As a common framework for these schemes we propose to consider multiple testing along a tree of hypotheses together with a “keep rejecting until first acceptance" rule. Particular topics addressed in this note are control of the familywise error, and some variants and basic properties of the procedure."

"In this work, we present a novel approach to the mathematical analysis of equations with memory based on the notion of a state, namely, the initial configuration of the system which can be unambiguously determined by the knowledge of the future dynamics. "

"address the questions of perfectly sampling a Gibbs measure with infinite range interactions and of perfectly sampling the measure together with its finite range approximations. We solve these questions by introducing a perfect simulation algorithm for the measure and for the coupled measures. The algorithm works for general Gibbsian interaction under requirements on the tails of the interaction. As a consequence we obtain an upper bound for the error we make when sampling from a finite range approximation instead of the true infinite range measure."

Worth using in the Annals project?

" A sequence $x_1,...,x_n,...$ of discrete-valued observations is generated according to some unknown [measure] $\mu$. After observing each outcome, ... give the conditional probabilities of the next observation. ... $\mu$ [is in] an arbitrary but known class $C$ of stochastic process measures. We [want] predictors ... whose conditional probabilities converge (in some sense) to the [true] conditional probabilities if any $\mu\in C$ is chosen to generate the sequence. ... [C]haracteriz[e] the families $C$ for which such predictors exist ... a specific and simple form in which to look for a solution. ... if any predictor works, then there exists a Bayesian predictor, whose prior is discrete, and which works too. .... sufficient and necessary conditions for the existence of a predictor, in terms of topological characterizations of the family $C$, as well as in terms of local behaviour of the measures in $C$, which in some cases lead to procedures for constructing such predictors."

"a parametrized family of general hidden Markov models, where both the observed and unobserved components take values in a complete separable metric space. We prove that the maximum likelihood estimator (MLE) of the parameter is strongly consistent under a rather minimal set of assumptions. As special cases of our main result, we obtain consistency in a large class of nonlinear state space models, as well as general results on linear Gaussian state space models and finite state models. A novel aspect of our approach is an information-theoretic technique for proving identifiability, which does not require an explicit representation for the relative entropy rate. Our method of proof could therefore form a foundation for the investigation of MLE consistency in more general dependent and non-Markovian time series. Also of independent interest is a general concentration inequality for $V$-uniformly ergodic Markov chains."

"Dependence with complete connections is a more general type of stochastic process than the well-known Markovian dependence, accounting for a complete history of a stochastic evolution. This book is an authoritative survey of knowledge of the subject, dealing with the basic theoretical understanding and also with applications. These arise in a variety of situations as diverse as stochastic models of learning, branching processes in random environments, continued fractions and dynamical systems. Thus the book will appeal to mathematicians working in probability theory, ergodic theory and number theory, as well as applied mathematicians, engineers, biologists and social scientists interested in applications of stochastic methods." The "epsilon-machine" models I work with are an example of chains with complete connections.

"This paper describes the FSA Utilities toolbox: a collection of utilities to manipulate finite-state automata and finite-state transducers. Manipulations include determinization (both for finite-state acceptors and finite-state transducers), minimization, composition, complementation, intersection, Kleene closure, etc. Furthermore, various visualization tools are available to browse finite-state automata. The toolbox is implemented in SICStus Prolog." Where's something comparable in a sane language? (N.B., must handle transducers.)

... from a quick scan (the abstract is completely uninformative), this seems to be yet another near-reinvention of Knight's "prediction process". To be read, and to act as a goad for me to finish CSSR II w/ KLK. (I confess I am somewhat boggled at the idea that all HMMs are linear.)

Update: After a careful read, this really is just a rediscovery of predictive representations, with the trick of using regression to learn the state-transition and emission functions. On the one hand, I feel kind of burned by seeing them calling this "entirely new" (never mind me or my teachers, Littman, Sutton & Singh should be very upset; so should Knight if he were still alive). On the other hand, they got it _done_, which is a very real virtue.

Also: You need to put **** error bars on your average performance plots. (Yes, I realize I'm nit-picking because I'm jealous.)

I should just buy the damn thing. Later: did. Notes: http://cscs.umich.edu/~crshalizi/weblog/algae-2009-04.html#finitary

Model discovery via matrix factorization. Note: they're wrong about CSSR.

When can the state of one process be recovered without error from another? (Use of infinite time limit here is not quite relevant to my immediate needs so must see how to modify proof.)

"This paper develops a connection between the asymptotic stability of nonlinear filters and a notion of observability. We consider a general class of hidden Markov models in continuous time with compact signal state space, and call such a model observable if no two initial measures of the signal process give rise to the same law of the observation process. We demonstrate that observability implies stability of the filter, i.e., the filtered estimates become insensitive to the initial measure at large times. For the special case where the signal is a finite-state Markov process and the observations are of the white noise type, a complete (necessary and sufficient) characterization of filter stability is obtained in terms of a slightly weaker detectability condition. In addition to observability, the role of controllability in filter stability is explored. Finally, the results are partially extended to non-compact signal state spaces."