Election Prediction & MCMC Basics

• Election prediction involves considering the prior probability of candidate A, denoted as p(A), and incorporating polling data.

Parallel Postings

• Sequential updating calculates the posterior probability of A given all data points by multiplying the prior with the likelihood of each data point given A: $p(A|D_1...D_n) \propto p(A) \cdot \prod_{i=1}^{n} p(D_i|A)$.
• Parallel updating divides the data into batches to compute the posterior probability as $p(A|D_1...D_n) \propto p(A) \cdot \prod_{j=1}^{k} p(D_j|A)$, thus each batch ($D_j$) can be processed independently.
• A key aspect of parallel updating is the assumption of conditional independence, meaning $D_i$ are conditionally independent given A.

MCMC Basics

• MCMC involves using Monte Carlo methods, drawing samples to approximate values, and Markov Chains, a sequence of states depending only on the current state.
• In a Markov Chain, the probability of transitioning to the next state ($x'$) depends solely on the current state ($x$): $P(x^{(t+1)} = x' | x^{(t)} = x, x^{(t-1)} = x_{t-1},... x^{(0)} = x_0) = P(x^{(t+1)} = x' | x^{(t)} = x)$.
• Constructing a Markov chain with a stationary distribution matching the distribution of interest is the key idea behind MCMC.

Example: Gibbs Sampling

• The Gibbs sampling algorithm is an MCMC method used to sample from $p(x, y)$.
• In Gibbs Sampling, initialize $x^{(0)}, y^{(0)}$, then iteratively sample $x^{(t+1)} \sim p(x | y = y^{(t)})$ and $y^{(t+1)} \sim p(y | x = x^{(t+1)})$ for each step t.
• Under specific conditions, the samples $(x^{(t)}, y^{(t)})$ converge to samples from $p(x, y)$ as $t$ approaches infinity.

Topic Models

• Topic models are used for document clustering, topic extraction, and information retrieval.

Latent Dirichlet Allocation (LDA)

• LDA is a topic model where each document is a mixture of topics, and each topic is a distribution over words.
• In LDA's Generative process, for each topic, a distribution over words is drawn. Also, for each document, a distribution over topics is drawn. Then for each word in a document, a topic is assigned and a word is drawn from that topic's distribution.
• In LDA, topics $k \in [1, K]$, draw a distribution over words $\beta_k \sim Dirichlet(\eta)$.
• In LDA, for each document $d \in [1, D]$, draw a distribution over topics $\theta_d \sim Dirichlet(\alpha)$.
• In LDA, for each word $n \in [1, N_d]$, draw a topic assignment $z_{dn} \sim Multinomial(\theta_d)$ and a word $w_{dn} \sim Multinomial(\beta_{z_{dn}})$.

Plate Notation

• Plate Notation provides a graphical representation of probabilistic models.

Deep Generative Models

Variational Autoencoders (VAEs)

• VAEs aim to learn a latent representation of input data.
• VAEs use an encoder to map data to a latent space and a decoder to reconstruct the data from the latent space.
• VAEs use a variational approach to train the model to reconstruct the input data, regularizing the latent space to follow a known distribution like Gaussian.

Generative Adversarial Networks (GANs)

• GANs consist of a generator that generates fake data and a discriminator that distinguishes between real and fake data.
• In GANs, the generator and discriminator are trained adversarially which causes the generator tries to fool the discriminator, and the discriminator tries to identify fake data.
• The goal of GAN training is for the generator to learn to produce realistic data.