Advanced Probabilistic Graphical Models

Цели урока

• Understand HMM structure and the forward-backward, Viterbi, and Baum-Welch algorithms
• Master CRFs as a discriminative generalization of HMMs with arbitrary features
• Analyze mean-field variational inference and its link to ELBO
• Connect variational message passing with belief propagation on graphs

Предварительные знания

• Bayes' theorem and posterior distributions
• KL divergence and information theory
• Markov chains and dynamic programming
• Gaussian processes and de Finetti's theorem

• Infinite-Dimensional Probability

How are probabilistic models with billions of hidden variables trained, and why do the same tools power spaCy NER and Facebook Graph Inference?

• **HMM in speech:** Apple Siri and Google Voice before the neural era processed 95% of mobile speech with HMM and Baum-Welch
• **CRF in NLP:** spaCy and Stanford CoreNLP use BiLSTM-CRF for NER and POS tagging; the SOTA until 2018
• **Profile HMMs:** HMMER applies HMM to protein family search; Glimmer/GENSCAN use Viterbi for gene prediction
• **Variational message passing:** Facebook Graph Inference and YouTube recommendations scale inference to billions of nodes via VMP

Hidden Markov Models (HMM)

In 1966 Leonard Baum and Ted Petrie introduced HMMs for speech recognition. By 2010 these models powered 95% of mobile speech recognition in Apple Siri and Google Voice. The HMM structure is simple: a hidden state z_t evolves as a Markov chain and each generates an observation x_t. The forward-backward and Viterbi algorithms are standard tools in NLP, bioinformatics, and finance.

HMMs remain relevant in bioinformatics: profile HMMs are used in HMMER for protein family search, and Viterbi in gene prediction (Glimmer, GENSCAN). In finance HMMs model market regimes (bull/bear) as hidden states.

Conditional Random Fields (CRF)

In 2001 Lafferty, McCallum, and Pereira proposed CRFs as a discriminative generalization of HMMs. Their key advantage: CRFs model p(z|x) directly, bypassing p(x). This allows using arbitrary features of observations without modeling their distribution. Before 2018 the BiLSTM-CRF was state-of-the-art for named entity recognition, and this approach is still used in spaCy for tagging.

BiLSTM-CRF (Huang et al. 2015) is the architecture for sequence tagging: BiLSTM extracts contextual representations, the CRF models transition constraints between labels. Before the transformer era this was the standard in NER and POS tagging.

Variational Message Passing

For complex PGMs exact inference is typically infeasible (NP-hard for loopy graphs). Variational message passing generalizes belief propagation to mean-field approximations: each node exchanges 'messages' with its neighbors, updating a local approximation of the posterior. This scales to billions of nodes in Facebook Graph Inference and YouTube recommendations.