MACHINE LEARNING

EM Algorithm (Expectation-Maximization):

Iterative method for MLE in presence of latent variables $Z$ (e.g., mixture components, missing data). Maximizes $\log p(X|\theta)=\log\sum_Z p(X,Z|\theta)$ intractable directly.

Idea: Iteratively construct lower bound via Jensen, maximize it.

Steps:
Given data $X$, latent $Z$, parameters $\theta$.

• E-step (Expectation): Compute posterior $q(Z)=p(Z|X,\theta^{(t)})$ and expected complete log-likelihood $Q(\theta|\theta^{(t)})=E_{Z|X,\theta^{(t)}}[\log p(X,Z|\theta)] = \sum_Z p(Z|X,\theta^{(t)})\log p(X,Z|\theta)$
  Equivalent to computing responsibilities $\gamma_{nk}=p(z_k=1|x_n,\theta^{(t)})$.

• M-step (Maximization): $\theta^{(t+1)}=\arg\max_\theta Q(\theta|\theta^{(t)})$

Iterate until $\log p(X|\theta^{(t+1)})-\log p(X|\theta^{(t)})<\epsilon$. Guaranteed monotonic increase, converges to local optimum (not necessarily global; restart needed).

Example — Gaussian Mixture Model (GMM) with $K$ components:

Model: $p(x)=\sum_{k=1}^K \pi_k N(x|\mu_k,\Sigma_k)$, latent $z_{nk}\in\{0,1\}$ indicates component.

E-step: $\gamma_{nk}= \frac{\pi_k N(x_n|\mu_k,\Sigma_k)}{\sum_j \pi_j N(x_n|\mu_j,\Sigma_j)}$

M-step: $N_k=\sum_n\gamma_{nk}$, $\pi_k^{new}=N_k/N$, $\mu_k^{new}=\frac1{N_k}\sum_n\gamma_{nk}x_n$, $\Sigma_k^{new}=\frac1{N_k}\sum_n\gamma_{nk}(x_n-\mu_k^{new})(x_n-\mu_k^{new})^T$

Example numbers: Data {1,2,10}, $K=2$ init $\mu_1=1,\mu_2=10$ → E-step assigns 1,2 to component1 ($\gamma\approx1$), 10 to component2 → M-step updates $\mu_1\to1.5$, $\mu_2\to10$ → iterates.

EM also used in HMM (Baum-Welch), k-means is hard-assignment limit of GMM-EM with spherical $\Sigma\to0$.

Main Components of Reinforcement Learning (RL):

Agent learns policy interacting with environment via trial-reward.

1. Agent: Learner/decision maker (robot, game player).
2. Environment: External system agent interacts with (maze, market).
3. State $s \in S$: Snapshot of environment (position, sensor readings).
4. Action $a \in A(s)$: Moves agent can take (up/down, buy/sell).
5. Reward $r$: Scalar feedback $r(s,a,s')$ after action (positive for goal, negative for penalty).
6. Policy $\pi(a|s)$: Agent's strategy mapping states → actions (deterministic or stochastic), goal to learn optimal $\pi^*$.
7. Value Function: $V^\pi(s)=E[\sum \gamma^t r_t | s_0=s]$, $Q^\pi(s,a)=E[\sum\gamma^t r_t | s,a]$ — expected cumulative discounted return. Optimal $V^*, Q^*$ satisfy Bellman equations.
8. Model (optional): Transition dynamics $p(s'|s,a)$ and reward model; model-based vs model-free.
9. Discount $\gamma\in[0,1]$: Balances immediate vs future reward.

Loop: $s_0 \xrightarrow{\pi} a_0 \xrightarrow{env} r_0,s_1 \xrightarrow{\pi} a_1 ...$ Goal: maximize $G=\sum \gamma^t r_t$.

Exploration-Exploitation Trade-off:

• Exploitation: Use best-known action (max $Q(s,a)$) to maximize immediate reward.
• Exploration: Try random/new actions to discover potentially better long-term rewards.

Too much exploitation → stuck in suboptimal policy (local optimum). Too much exploration → never converges, low reward.

Example: Multi-Armed Bandit / Maze.

• Robot in maze knows one path gives reward 10 (exploitation), but unexplored path may give 100. $\epsilon$-greedy: with prob $\epsilon$ explore random action, else exploit best. Anneal $\epsilon$ over time. UCB and Thompson Sampling also balance via uncertainty.

In AlphaGo, exploitation = play best known move from $Q$, exploration = try novel moves during self-play to improve.

Solution: decay $\epsilon$ from 1 → 0.1, optimistic initialization, intrinsic motivation.

Bayesian Networks:

Directed Acyclic Graph (DAG) representation of joint distribution $P(X_1..X_n)$.

Structure: Nodes = random variables, directed edges = direct dependencies (parent → child conditional). Each node has Conditional Probability Table (CPT): $P(X_i|Parents(X_i))$ for discrete, or density for continuous.

Joint factorization: $P(X_1..X_n)=\prod_i P(X_i|Pa(X_i))$ (chain rule with d-separation conditional independencies). Example: $Rain → Sprinkler → Wet Grass$, $Rain → Wet Grass$.

Inference: Compute $P(query|evidence)$ via enumeration, Variable Elimination, Belief Propagation, Junction Tree (exact exponential), or approximate MCMC/Likelihood Weighting. Bayes rule propagates evidence.

Learning:

• Parameter learning: MLE/MAP estimate CPTs from data ($\hat P(x_i|pa)=count(x_i,pa)/count(pa)$).
• Structure learning: Search over DAGs scoring via BIC/MDL, NP-hard.

Advantages: Compact, interpretable causal model, handles missing data, combines prior knowledge, supports both causal and diagnostic reasoning (e.g., $P(Disease|Symptom)$).

Uses: Medical diagnosis (ALARM network), fault detection, speech recognition (HMM is dynamic BN), decision support (Influence Diagrams).

Example: $P(Burglary)=0.001$, $P(Earthquake)=0.002$, $P(Alarm|B,E)$ CPT, $P(JohnCalls|Alarm)$ — can query $P(B|A)$ via Bayes net inference.

Limitations: DAG cannot have cycles, eliciting CPTs expensive, inference NP-hard for dense nets. For undirected cyclic dependencies use Markov Random Fields.