MACHINE LEARNING

Bayesian Networks (BN) vs Markov Random Fields (MRF):

Both are Probabilistic Graphical Models representing joint distribution $p(x_1..x_n)$ via graph factorization.

Bayesian Networks — Directed Acyclic Graph (DAG):

• Nodes = random variables, directed edges = direct dependencies (parent → child = causal).
• Factorization: $p(x)=\prod_{i} p(x_i | Pa(x_i))$ (chain rule with conditional independence via d-separation).
• Need Conditional Probability Tables (CPTs) for discrete nodes.
• Represents causal / asymmetric dependencies, natural for generative processes (e.g., disease → symptom).
• Inference: exact (variable elimination, junction tree) NP-hard; approx MCMC.
• Learning: DAG structure learning NP-hard, parameter learning via MLE.

Markov Random Fields — Undirected Graph:

• Nodes linked by undirected edges, factorization over cliques via potentials $\psi_C(x_C)$: $p(x)=\frac1Z \prod_{C} \psi_C(x_C)$ where $Z=\sum_x \prod_C \psi_C$ (partition function, global normalization).
• Represents symmetric / non-causal correlations, spatial interactions (e.g., pixels in image — neighboring pixels similar, Ising model).
• Conditional independence via graph separation.
• No CPTs, more flexible for cyclic dependencies.

Trade-offs:

Aspect	BN	MRF
Edge meaning	Causal, directed	Correlation, undirected
Normalization	Local (each CPT sums to 1)	Global $Z$ — expensive
Cycles	Cannot handle directed cycles	Handles cycles naturally
Interpretability	High (causal)	Lower
Learning complexity	Structure NP-hard but local norm easy	Potential learning hard, $Z$ intractable
Inference	Slightly cheaper if DAG sparse	Often costlier due to $Z$
Use cases	Diagnosis, causal reasoning, time series (DBN)	Image segmentation, stereo, spatial stats

Choosing: Use BN when direction/causality known, need generative sampling, DAG natural. Use MRF when dependencies symmetric, lattice-like, or cyclic correlations (images, social networks). Many distributions can be represented by either with transformations (moralization), but efficiency differs.

Probably Approximately Correct (PAC) Learning Model (Valiant 1984):

Framework to analyze learnability: when can learner, with high probability, find approximately correct hypothesis with polynomial sample/computation?

Setup: Instance space $X$, concept class $C$, hypothesis space $H$, distribution $D$ over $X$, target $c\in C$, training set $S\sim D^m$ labeled by $c$.

Learner outputs $h\in H$.

Definition: $C$ is PAC-learnable if exists algorithm $L$ and polynomial $poly(1/\epsilon,1/\delta,n,size(c))$ such that for any $\epsilon,\delta\in(0,1)$, any $D$, any $c\in C$, given $m\ge poly(...)$ examples, $L$ outputs $h$ with $P(Error_D(h)\le \epsilon) \ge 1-\delta$.

Error: $Error_D(h)=P_{x\sim D}[h(x)
eq c(x)]$, training error zero for consistent learner.

$\epsilon$: Accuracy parameter (approximately correct, error ≤$\epsilon$). $\delta$: Confidence (probably, with probability 1-$\delta$).

Sample complexity bounds:
For finite $|H|$: $m \ge \frac1\epsilon(\ln|H| + \ln1/\delta)$ sufficient for consistent learner (if realizable). Using Hoeffding: $P(\exists h\in H: Error_{train}=0 but Error_{true}>\epsilon) \le |H|e^{-\epsilon m}$.

For infinite $H$, VC-dimension $d=VC(H)$: $m = O(\frac1\epsilon(d\log1/\epsilon +\log1/\delta))$ (agnostic: $m=O(\frac1{\epsilon^2}(d+\log1/\delta))$).

Examples:

• Conjunctions of $n$ literals: PAC-learnable with $m=O(\frac1\epsilon(n\log n +\log1/\delta))$
• Axis-aligned rectangles in $\mathbb{R}^2$ PAC-learnable, $VC=4$.
• Parity not efficiently PAC-learnable.

Agnostic PAC: $c
otin H$or noise, learner finds$h$with error ≤$\min_{h\in H}Error_D(h)+\epsilon$.

Implications: PAC gives theoretical guarantee linking sample size, hypothesis complexity ($|H|$ or VC), accuracy and confidence. Guides Occam's razor: simpler $H$ needs fewer samples.

Limitations: Distribution-free worst-case, often loose bounds, assumes i.i.d.

(b) Reinforcement Learning:

Definition: Paradigm where agent learns optimal policy $\pi^*:S\to A$ by interacting with environment and maximizing cumulative reward, not from labeled examples but from delayed reward signal.

Components: Agent, Environment, State $s$, Action $a$, Reward $r$, Policy $\pi$, Value $V^\pi, Q^\pi$, Model $p(s'|s,a)$, discount $\gamma$.

Types:

• Model-free: No explicit model; directly learn $V/Q/\pi$. Value-based (Q-learning $Q(s,a)\leftarrow Q+\alpha[r+\gamma\max Q(s',a')-Q]$), Policy-based (REINFORCE $
  abla J=E[
  abla\log\pi(a|s) Q]$), Actor-Critic.
• Model-based: Learn/know $p(s'|s,a)$, plan via DP (Value Iteration, MCTS in AlphaGo).
• On-policy (SARSA) learns about $\pi$ being followed; off-policy (Q-learning) learns about optimal $\pi$ from any behavior.

Exploration-Exploitation: $\epsilon$-greedy, UCB, Thompson, entropy regularization.

Algorithms: Q-learning, SARSA, DQN (deep $Q$ with replay + target network), Policy Gradient, PPO, A3C.

Challenges: Credit assignment (delayed reward), exploration, instability, sample inefficiency.

Applications: Game playing (AlphaGo, Atari DQN), robotics control, autonomous driving, recommender systems (long-term engagement), finance trading.

Example: Grid maze: states = cells, actions = up/down/left/right, reward +10 goal, -1 wall, agent via Q-learning propagates values back from goal to learn shortest path.

Differences vs supervised: No correct output provided, only reward; sequential, action affects next state (non-i.i.d).

Rewards shape behavior; reward engineering crucial.