UNIT 5: Optimization Techniques in Machine Learning - Short Notes

I. Foundations of Machine Learning and Optimization

Learning Paradigms

Historical Progression of Deep Learning: 1940s (McCulloch-Pitts neuron) → 1950s-60s (Perceptron, ADALINE) → 1980s (Backpropagation, MLPs, ReLU introduced) → 1990s-2000s (SVMs dominate, "AI Winter") → 2006 (Hinton's Deep Belief Nets, "Deep Learning" term) → 2012 (AlexNet wins ImageNet) → 2010s (ResNet, GANs, Transformers, BERT, GPT).

Representation Learning: Automatically discover latent features/representations from raw data (e.g., pixels, words) rather than relying on manual feature engineering. Core strength of deep neural networks.

II. Linear Models and Optimization

Logistic Regression

Model Formulation: For binary classification, predicts probability $$\displaystyle P(y=1|\mathbf{x}) = \sigma(\mathbf{w}^T\mathbf{x} + b) $$, where $$\displaystyle \sigma(z) = \frac{1}{1+e^{-z}} $$ is the sigmoid function.

Loss Function: Binary Cross-Entropy (Log Loss)

$$J(\mathbf{w}) = -\frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)} \log(\hat{p}^{(i)}) + (1-y^{(i)}) \log(1-\hat{p}^{(i)}) \right]$$

Optimization Methods:

1. Gradient Descent (GD): Iteratively update weights $$\displaystyle \mathbf{w} := \mathbf{w} - \eta \nabla J(\mathbf{w}) $$.

   • Gradient: $$\displaystyle \nabla J(\mathbf{w}) = \frac{1}{m} \mathbf{X}^T (\sigma(\mathbf{X}\mathbf{w}) - \mathbf{y}) $$

2. Iteratively Reweighted Least Squares (IRLS): A Newton-Raphson method. At each iteration, solve a weighted least squares problem: $$\displaystyle \mathbf{w}_{new} = (\mathbf{X}^T \mathbf{W} \mathbf{X})^{-1} \mathbf{X}^T \mathbf{W} \mathbf{z} $$, where $\mathbf{W}$ is a diagonal matrix of weights $$\displaystyle p^{(i)}(1-p^{(i)}) $$ and $$\displaystyle \mathbf{z} = \mathbf{X}\mathbf{w}_{old} + \mathbf{W}^{-1}(\mathbf{y} - \mathbf{p}) $$.

III. Neural Network Fundamentals

Feedforward Neural Network (MLP) Architecture

A directed acyclic graph with an input layer, one or more hidden layers (fully connected), and an output layer. Information flows forward from input to output without cycles.

Activation Functions

Representation Power & Universal Approximation Theorem

• Universal Approximation Theorem: A feedforward network with a single hidden layer containing a finite number of neurons and appropriate activation functions (e.g., sigmoid, ReLU) can approximate any continuous function on compact subsets of $$\displaystyle \mathbb{R}^n $$ to any desired accuracy, given sufficient neurons.

• Representation Power of Sigmoid Neurons: A network of sigmoid neurons can compute any boolean function and approximate any continuous function, but depth provides exponential efficiency for certain functions (e.g., parity, hierarchical concepts).

Forward Propagation

For a 2-layer MLP (one hidden layer):

1. Hidden layer pre-activation: $$\displaystyle \mathbf{z}^{(1)} = \mathbf{W}^{(1)}\mathbf{x} + \mathbf{b}^{(1)} $$

2. Hidden layer activation: $$\displaystyle \mathbf{a}^{(1)} = g(\mathbf{z}^{(1)}) $$ ($g$ is activation function)

3. Output layer pre-activation: $$\displaystyle \mathbf{z}^{(2)} = \mathbf{W}^{(2)}\mathbf{a}^{(1)} + \mathbf{b}^{(2)} $$

4. Output: $$\displaystyle \hat{\mathbf{y}} = h(\mathbf{z}^{(2)}) $$ ($h$ is output activation, e.g., softmax)

IV. Training Neural Networks: Optimization Algorithms

Loss Functions

• Mean Squared Error (MSE): For regression. $$\displaystyle J = \frac{1}{m} \sum_{i=1}^{m} (\hat{y}^{(i)} - y^{(i)})^2 $$

• Cross-Entropy Loss:

  • Binary: $$\displaystyle J = -\frac{1}{m} \sum [y \log(\hat{p}) + (1-y)\log(1-\hat{p})] $$

  • Multi-class: $$\displaystyle J = -\frac{1}{m} \sum_{i=1}^{m} \sum_{j=1}^{K} y_j^{(i)} \log(\hat{p}_j^{(i)}) $$

Backpropagation Algorithm

Core Idea: Efficiently compute the gradient $\nabla J$ of the loss w.r.t. all weights using the chain rule. It consists of:

1. Forward Pass: Compute activations and loss for a mini-batch.

2. Backward Pass (Backprop): Starting from output layer, propagate error signals backward to compute $$\displaystyle \frac{\partial J}{\partial \mathbf{W}} $$ and $$\displaystyle \frac{\partial J}{\partial \mathbf{b}} $$ for each layer using local gradients.

   • Output layer error: $$\displaystyle \delta^{(L)} = \nabla_{\mathbf{z}} J \odot g'(\mathbf{z}^{(L)}) $$

   • Hidden layer error: $$\displaystyle \delta^{(l)} = ((\mathbf{W}^{(l+1)})^T \delta^{(l+1)}) \odot g'(\mathbf{z}^{(l)}) $$

   • Gradients: $$\displaystyle \frac{\partial J}{\partial \mathbf{W}^{(l)}} = \delta^{(l)} (\mathbf{a}^{(l-1)})^T $$, $$\displaystyle \frac{\partial J}{\partial \mathbf{b}^{(l)}} = \delta^{(l)} $$

Gradient Descent Variants

Advanced Gradient Descent Methods

• Momentum: Accumulates past gradients to accelerate along consistent directions. $$\displaystyle \mathbf{v} = \beta \mathbf{v} + (1-\beta) \nabla J $$, $$\displaystyle \mathbf{w} := \mathbf{w} - \eta \mathbf{v} $$. Reduces oscillations.

• Nesterov Accelerated Gradient (NAG): "Lookahead" momentum. Computes gradient at the approximated future position: $$\displaystyle \mathbf{v} = \beta \mathbf{v} + (1-\beta) \nabla J(\mathbf{w} - \eta \beta \mathbf{v}) $$. Corrects overshoot.

Adaptive Optimization Algorithms

• AdaGrad: Adapts learning rate per parameter based on historical sum of squared gradients. $$\displaystyle G_t = G_{t-1} + (\nabla J_t)^2 $$, $$\displaystyle \mathbf{w} := \mathbf{w} - \frac{\eta}{\sqrt{G_t + \epsilon}} \odot \nabla J_t $$. Cons: Accumulated sum grows, learning rates decay to zero.

• RMSProp: Fixes AdaGrad's decay by using an exponentially weighted moving average of squared gradients. $$\displaystyle G_t = \gamma G_{t-1} + (1-\gamma) (\nabla J_t)^2 $$. Prevents aggressive learning rate decay.

• Adam (Adaptive Moment Estimation): Combines Momentum (1st moment) and RMSProp (2nd moment) with bias correction.

  \begin{aligned}

  \mathbf{m}t &= \beta_1 \mathbf{m}{t-1} + (1-\beta_1) \nabla J_t \quad &\text{(1st moment estimate)} \

  \mathbf{v}t &= \beta_2 \mathbf{v}{t-1} + (1-\beta_2) (\nabla J_t)^2 \quad &\text{(2nd moment estimate)} \

  \hat{\mathbf{m}}_t &= \frac{\mathbf{m}_t}{1-\beta_1^t}, \quad \hat{\mathbf{v}}_t = \frac{\mathbf{v}_t}{1-\beta_2^t} \quad &\text{(bias correction)} \

  \mathbf{w} &:= \mathbf{w} - \eta \frac{\hat{\mathbf{m}}_t}{\sqrt{\hat{\mathbf{v}}_t} + \epsilon}

  \end{aligned}

  Default: $$\displaystyle \beta_1=0.9, \beta_2=0.999, \epsilon=10^{-8} $$.

Batch Normalization

Goal: Reduce internal covariate shift (distribution change of layer inputs during training) to stabilize and accelerate training. Mechanism: For a mini-batch $$\displaystyle \mathcal{B} = \{x_1,...,x_m\} $$ and per-feature:

1. Compute batch mean $$\displaystyle \mu_{\mathcal{B}} = \frac{1}{m} \sum_{i=1}^m x_i $$ and variance $$\displaystyle \sigma_{\mathcal{B}}^2 = \frac{1}{m} \sum_{i=1}^m (x_i - \mu_{\mathcal{B}})^2 $$.

2. Normalize: $$\displaystyle \hat{x}_i = \frac{x_i - \mu_{\mathcal{B}}}{\sqrt{\sigma_{\mathcal{B}}^2 + \epsilon}} $$.

3. Scale and shift (learnable): $$\displaystyle y_i = \gamma \hat{x}_i + \beta $$. Advantages: Allows higher learning rates, acts as regularizer (adds noise via batch stats), reduces dependency on careful initialization.

Data Preprocessing

V. Challenges in Deep Learning and Mitigation Strategies

Vanishing and Exploding Gradients

• Cause: Repeated multiplication of gradients through many layers (deep networks) during backprop. With sigmoid/tanh, derivatives are <1 (vanishing). With large weights, derivatives >1 (exploding).

• Impact: Vanishing: early layers learn very slowly/not at all. Exploding: unstable training, NaN weights.

• Mitigation Strategies:

  1. ReLU & Variants: Derivative is 1 for positive inputs, avoiding saturation.

  2. Batch Normalization: Stabilizes layer input distributions, keeping gradients in stable range.

  3. Residual Connections (ResNet): Create shortcut paths allowing gradient to flow directly: $$\displaystyle \mathbf{y} = \mathbf{F}(\mathbf{x}, \mathbf{W}) + \mathbf{x} $$. Gradient path has derivative ~1.

  4. Gradient Clipping: Cap gradient norm (e.g., if $$\displaystyle ||\mathbf{g}|| > \text{threshold} $$, set $$\displaystyle \mathbf{g} := \frac{\text{threshold}}{||\mathbf{g}||} \mathbf{g} $$). Used in RNNs/GANs.

Overfitting and Underfitting (Bias-Variance Tradeoff)

• Underfitting (High Bias): Model too simple, fails to capture pattern. High training & test error.

• Overfitting (High Variance): Model too complex, memorizes noise. Low training error, high test error.

• Tradeoff: Reducing bias increases variance and vice-versa.

Regularization Techniques

Architectural Solutions

• ReLU Activation: Avoids vanishing gradients in deep networks.

• Batch Normalization: Stabilizes training, allows higher learning rates.

• Residual Connections (ResNet): Enables training of very deep networks (100+ layers) by solving degradation problem.

VI. Convolutional Neural Networks (CNNs)

CNN Architecture

1. Convolutional Layers: Apply learnable filters (kernels) to input, producing feature maps.

   • Filter: Small matrix (e.g., 3x3, 5x5) that detects local patterns (edges, textures).

   • Output Size: $$\displaystyle O = \frac{W - K + 2P}{S} + 1 $$, where $W$=input width, $K$=kernel size, $P$=padding, $S$=stride.

2. Pooling Layers (Subsampling): Downsample feature maps, reduce spatial size, provide translation invariance.

   • Max Pooling: Take maximum value in window. Most common.

   • Average Pooling: Take average value in window.

3. Fully Connected (FC) Layers: At the end, for classification/regression.

4. Activation: ReLU almost always after conv layers.

Key Concepts

• Padding:

  • Valid: No padding. Output shrinks.

  • Same: Pad so output size = input size (for stride=1).

• Stride: Step size of filter movement. Larger stride → smaller output.

• Receptive Field: The region in the input volume that affects a particular neuron. Increases with depth.

Applications in Diverse Data Formats

Advantages over Fully Connected Networks

1. Parameter Sharing: Same filter applied across spatial locations → drastically fewer parameters.

2. Spatial Hierarchies: Lower layers learn simple features (edges), higher layers learn complex features (objects). Exploits spatial locality.

3. Translation Invariance: Pooling and convolution provide some invariance to object location.

VII. Recurrent Neural Networks (RNNs) for Sequential Data

Basic RNN Architecture

• Recurrent Connection: Hidden state $$\displaystyle \mathbf{h}_t $$ depends on current input $$\displaystyle \mathbf{x}_t $$ and previous hidden state $$\displaystyle \mathbf{h}_{t-1} $$.

• Hidden State Dynamics: $$\displaystyle \mathbf{h}_t = \tanh(\mathbf{W}_{xh} \mathbf{x}_t + \mathbf{W}_{hh} \mathbf{h}_{t-1} + \mathbf{b}_h) $$

• Output: $$\displaystyle \mathbf{y}_t = \text{softmax}(\mathbf{W}_{hy} \mathbf{h}_t + \mathbf{b}_y) $$

• Parameters: Shared across all time steps ($$\displaystyle \mathbf{W}_{xh}, \mathbf{W}_{hh}, \mathbf{W}_{hy} $$).

Backpropagation Through Time (BPTT)

• Unroll the RNN for T time steps, creating a deep feedforward network.

• Apply standard backpropagation through this unrolled graph.

• Gradients w.r.t. parameters at time t depend on all future time steps (up to T).

• Computational Cost: O(T) per forward/backward pass. Memory O(T) to store all hidden states.

Challenges with Long-Term Dependencies

• Vanishing/Exploding Gradients: Same issue as deep feedforward nets, but now across time steps. Gradients multiplied by $$\displaystyle \mathbf{W}_{hh} $$ repeatedly. If eigenvalues of $$\displaystyle \mathbf{W}_{hh} $$ < 1 → vanish; >1 → explode.

• Impact: RNN struggles to learn dependencies where the relevant information is many steps away.

Long Short-Term Memory (LSTM) Networks

Goal: Designed to explicitly address the long-term dependency problem. Core: Cell State $$\displaystyle \mathbf{C}_t $$ (the "conveyor belt") + Gates (sigmoid layers) that regulate information flow.

Gates & Working:

1. Forget Gate $$\displaystyle f_t = \sigma(\mathbf{W}_f [\mathbf{h}_{t-1}, \mathbf{x}_t] + \mathbf{b}_f) $$: Decides what to remove from cell state. Output in [0,1] per element.

2. Input Gate $$\displaystyle i_t = \sigma(\mathbf{W}_i [\mathbf{h}_{t-1}, \mathbf{x}_t] + \mathbf{b}_i) $$: Decides what new information to store.

3. Candidate Cell State $$\displaystyle \tilde{\mathbf{C}}_t = \tanh(\mathbf{W}_C [\mathbf{h}_{t-1}, \mathbf{x}_t] + \mathbf{b}_C) $$: Creates new candidate values.

4. Cell State Update: $$\displaystyle \mathbf{C}_t = f_t \odot \mathbf{C}_{t-1} + i_t \odot \tilde{\mathbf{C}}_t $$. Additive operation → easy gradient flow.

5. Output Gate $$\displaystyle o_t = \sigma(\mathbf{W}_o [\mathbf{h}_{t-1}, \mathbf{x}_t] + \mathbf{b}_o) $$: Decides what part of cell state to output as hidden state.

6. Hidden State: $$\displaystyle \mathbf{h}_t = o_t \odot \tanh(\mathbf{C}_t) $$.

Advantages over Basic RNN:

• Explicit long-term memory via cell state.

• Gates allow precise read/write/modify operations.

• Gradient can flow through cell state with minimal interference (additive), mitigating vanishing gradient.

Deep RNNs (Stacked RNNs)

Multiple RNN/LSTM layers stacked on top of each other. Lower layers learn short-term patterns, higher layers learn long-term, abstract representations.

Applications

• Natural Language Processing (NLP): Machine translation, text generation, sentiment analysis.

• Speech Recognition: Transcribing audio to text.

• Time Series Forecasting: Stock prices, weather prediction.

VIII. Autoencoders for Unsupervised Learning

Autoencoder Basics

• Goal: Learn efficient data encoding (compression) in an unsupervised manner by reconstructing its own input.

• Encoder: $$\displaystyle \mathbf{z} = f_{\text{enc}}(\mathbf{x}) $$, maps input to latent space (bottleneck).

• Decoder: $$\displaystyle \hat{\mathbf{x}} = f_{\text{dec}}(\mathbf{z}) $$, reconstructs from latent code.

• Loss: Reconstruction loss (MSE for real-valued, cross-entropy for binary).

• Bottleneck: Forces network to learn compressed, meaningful representation.

Autoencoder Variants

1. Sparse Autoencoder: Adds a sparsity penalty (e.g., KL divergence between average activation $\hat{\rho}$ and a small target $\rho$) to the loss. Forces only a fraction of neurons to be active, learning disentangled features.

2. Contractive Autoencoder: Adds penalty on the Frobenius norm of the Jacobian of encoder activations w.r.t. inputs: $$\displaystyle \Omega(\mathbf{x}) = \lambda \left\| \frac{\partial f_{\text{enc}}(\mathbf{x})}{\partial \mathbf{x}} \right\|_F^2 $$. Penalizes large derivatives → forces encoder to be locally invariant → learns robust features.

3. Denoising Autoencoder: Corrupt input (e.g., add Gaussian noise, drop pixels) before feeding to encoder. Trained to reconstruct the original clean input. Learns to remove noise, robust features.

Regularization in Autoencoders

Sparsity, contractive penalties, and denoising are all forms of regularization that prevent the autoencoder from simply learning the identity function and force it to learn useful representations.

Comparison with Linear Methods (PCA, SVD)

Applications

• Dimensionality Reduction: Compress high-dim data to low-dim latent space.

• Feature Learning: Pre-train encoder for supervised tasks (especially when labeled data scarce).

• Anomaly Detection: Train on normal data; high reconstruction error indicates anomaly.

• Pretraining for Deep Networks: Historically used to initialize deep nets (now less common with better initialization/ReLU).

IX. Generative Models

Generative Adversarial Networks (GANs)

• Generator (G): Creates synthetic samples from random noise $$\displaystyle \mathbf{z} \sim p_{\mathbf{z}} $$ (e.g., Gaussian). Maps $$\displaystyle \mathbf{z} \to \mathbf{x}_{\text{fake}} $$.

• Discriminator (D): Binary classifier. Distinguishes real data $$\displaystyle \mathbf{x}_{\text{real}} \sim p_{\text{data}} $$ from fake $$\displaystyle \mathbf{x}_{\text{fake}} = G(\mathbf{z}) $$.

• Min-Max Game:

  \begin{aligned}

  \min_G \max_D V(D,G) &= \mathbb{E}{\mathbf{x} \sim p{\text{data}}}[\log D(\mathbf{x})] + \mathbb{E}{\mathbf{z} \sim p{\mathbf{z}}}[\log(1 - D(G(\mathbf{z})))]

  \end{aligned}

  • D tries to maximize $$\displaystyle \log D(\mathbf{x}_{\text{real}}) + \log(1-D(\mathbf{x}_{\text{fake}})) $$.

  • G tries to minimize $\log(1-D(G(\mathbf{z})))$ or equivalently maximize $\log D(G(\mathbf{z}))$.

• Training Dynamics: Alternate between:

  1. Fix G, update D to better distinguish real/fake (increase $V$).

  2. Fix D, update G to fool D (decrease $V$).

• Challenges: Mode collapse (G generates limited varieties), training instability, difficult to evaluate.

Variational Autoencoders (VAEs)

• Goal: Learn a probabilistic latent variable model that maximizes data likelihood.

• Probabilistic Encoder: $$\displaystyle q_{\phi}(\mathbf{z}|\mathbf{x}) $$ approximates true posterior $p(\mathbf{z}|\mathbf{x})$. Typically Gaussian: $$\displaystyle \mathcal{N}(\mu_{\phi}(\mathbf{x}), \sigma_{\phi}^2(\mathbf{x})) $$.

• Probabilistic Decoder: $$\displaystyle p_{\theta}(\mathbf{x}|\mathbf{z}) $$ generates data from latent code.

• Objective (ELBO):

  \begin{aligned}

  \log p(\mathbf{x}) &\geq \mathbb{E}{q{\phi}(\mathbf{z}|\mathbf{x})}[\log p_{\theta}(\mathbf{x}|\mathbf{z})] - D_{KL}(q_{\phi}(\mathbf{z}|\mathbf{x}) || p(\mathbf{z})) \

  &= \text{Reconstruction Loss} - D_{KL}(\mathcal{N}(\mu,\sigma^2) || \mathcal{N}(0, I))

  \end{aligned}

• Reparameterization Trick: To backprop through sampling: $$\displaystyle \mathbf{z} = \mu_{\phi}(\mathbf{x}) + \sigma_{\phi}(\mathbf{x}) \odot \boldsymbol{\epsilon} $$, where $\boldsymbol{\epsilon} \sim \mathcal{N}(0, I)$. Makes gradient computation possible.

• Prior: $$\displaystyle p(\mathbf{z}) = \mathcal{N}(0, I) $$ (standard Gaussian).

• Training: Maximize ELBO (minimize negative ELBO) via SGD.

Comparison: GANs vs VAEs

Autoregressive Models

• Core Idea: Factorize joint distribution $p(\mathbf{x})$ as product of conditionals: $$\displaystyle p(\mathbf{x}) = \prod_{i=1}^n p(x_i | \mathbf{x}_{<i}) $$.

• NADE (Neural Autoregressive Distribution Estimator): Uses a neural network with masked connections to ensure each input dimension only depends on previous ones in a fixed order.

• MADE (Masked Autoencoder for Distribution Estimation): Applies the masking idea to autoencoders. Input $\mathbf{x}$ is fed through a fully connected autoencoder, but weights are masked so output dimension $i$ only sees inputs $$\displaystyle j<i $$. Can be used as a generative model by sampling sequentially.

X. Deep Belief Networks and Graphical Models

Restricted Boltzmann Machines (RBMs)

• Energy-Based Model: Defines a joint probability distribution over visible units $\mathbf{v}$ and hidden units $\mathbf{h}$ via an energy function:

$$E(\mathbf{v}, \mathbf{h}) = -\mathbf{v}^T \mathbf{W} \mathbf{h} - \mathbf{b}^T \mathbf{v} - \mathbf{c}^T \mathbf{h}$$

Probability: $$\displaystyle p(\mathbf{v}, \mathbf{h}) = \frac{e^{-E(\mathbf{v}, \mathbf{h})}}{Z} $$, where $Z$ is partition function.

• "Restricted": No connections between visible-visible or hidden-hidden units (bipartite graph). Makes sampling/gradient computation easier.

• Contrastive Divergence (CD-k): Approximate gradient of log-likelihood for training.

  1. Positive phase: Take a training sample $$\displaystyle \mathbf{v}^{(0)} $$, sample hidden $$\displaystyle \mathbf{h}^{(0)} \sim p(\mathbf{h}|\mathbf{v}^{(0)}) $$.

  2. Negative phase: Run k steps of Gibbs sampling: $$\displaystyle \mathbf{v}^{(k)} \sim p(\mathbf{v}|\mathbf{h}^{(k-1)}) $$, $$\displaystyle \mathbf{h}^{(k)} \sim p(\mathbf{h}|\mathbf{v}^{(k)}) $$.

  3. Gradient approx: $$\displaystyle \Delta \mathbf{W} \propto \langle \mathbf{v}^{(0)} {\mathbf{h}^{(0)}}^T \rangle - \langle \mathbf{v}^{(k)} {\mathbf{h}^{(k)}}^T \rangle $$.

Deep Belief Networks (DBNs)

• Structure: Stack of RBMs. Train greedily, layer-wise:

  1. Train first RBM on raw data $$\displaystyle \mathbf{v}^{(0)} $$.

  2. Use its hidden activations $$\displaystyle \mathbf{h}^{(0)} $$ as "data" for the next RBM (treat $$\displaystyle \mathbf{h}^{(0)} $$ as visible units $$\displaystyle \mathbf{v}^{(1)} $$).

  3. Repeat.

• Fine-tuning: After pre-training, optionally fine-tune entire stack with backpropagation.

• Significance: One of the first successful deep learning methods (pre-2012), demonstrated benefit of deep architectures and unsupervised pre-training.

Graphical Models

• Directed Graphical Models (Bayesian Networks): DAG. Nodes = random variables, Edges = direct conditional dependencies. Encodes factorization: $$\displaystyle p(\mathbf{x}) = \prod_i p(x_i | \text{parents}(x_i)) $$. Example: Naive Bayes.

• Undirected Graphical Models (Markov Random Fields - MRFs): Undirected graph. Factors are potential functions $\phi(\mathbf{C})$ over cliques $\mathbf{C}$. $$\displaystyle p(\mathbf{x}) = \frac{1}{Z} \prod_{\mathbf{C}} \phi_{\mathbf{C}}(\mathbf{x}_{\mathbf{C}}) $$. RBM is a special case (bipartite MRF).

Representation Learning in DBNs

Each RBM layer learns a non-linear transformation of its input, extracting increasingly abstract features. The greedy pre-training initializes deep networks in a region that leads to better solutions than random initialization, especially with limited labeled data.

XI. Deep Reinforcement Learning

Markov Decision Processes (MDPs)

• Defined by $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$:

  • $\mathcal{S}$: State space.

  • $\mathcal{A}$: Action space.

  • $P(s'|s,a)$: Transition probability (dynamics).

  • $R(s,a,s')$ or $R(s,a)$: Reward function.

  • $\gamma \in [0,1]$: Discount factor.

• Policy $\pi(a|s)$: Agent's behavior (probability of taking action a in state s).

• Value Functions:

  • State-value: $$\displaystyle V^{\pi}(s) = \mathbb{E}_{\pi}[\sum_{t=0}^{\infty} \gamma^t R_{t+1} | S_0 = s] $$

  • Action-value: $$\displaystyle Q^{\pi}(s,a) = \mathbb{E}_{\pi}[\sum_{t=0}^{\infty} \gamma^t R_{t+1} | S_0 = s, A_0 = a] $$

• Optimal Value Functions: $$\displaystyle V^*(s) = \max_{\pi} V^{\pi}(s) $$, $$\displaystyle Q^*(s,a) = \max_{\pi} Q^{\pi}(s,a) $$.

• Bellman Equations:

  $$\displaystyle V^*(s) = \max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^*(s')] $$

  $$\displaystyle Q^*(s,a) = \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma \max_{a'} Q^*(s',a')] $$

Dynamic Programming (DP)

Assumes full knowledge of $P$ and $R$.

1. Value Iteration: Initialize $$\displaystyle V_0(s)=0 $$. Iterate:

   $$\displaystyle V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V_k(s')] $$. Converges to $$\displaystyle V^* $$.

2. Policy Iteration:

   • Policy Evaluation: Given policy $$\displaystyle \pi_k $$, compute $$\displaystyle V^{\pi_k} $$ by solving linear system.

   • Policy Improvement: $$\displaystyle \pi_{k+1}(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^{\pi_k}(s')] $$.

   • Repeat until $$\displaystyle \pi_{k+1} = \pi_k $$.

Q-Learning and Deep Q-Networks (DQN)

• Q-Learning (tabular): Model-free, off-policy. Update rule:

  $$\displaystyle Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha [R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t,A_t)] $$

• Deep Q-Network (DQN): Uses deep CNN to approximate $Q(s,a;\theta)$.

  • Loss: $$\displaystyle L(\theta) = \mathbb{E}_{(s,a,r,s') \sim \mathcal{D}} \left[ (r + \gamma \max_{a'} Q(s',a';\theta^-) - Q(s,a;\theta))^2 \right] $$

  • Key Tricks:

    1. Experience Replay: Store transitions $(s,a,r,s')$ in replay buffer $\mathcal{D}$. Sample random mini-batches for training → breaks correlation, improves data efficiency.

    2. Target Network: Use a separate, slowly updated target network with parameters $$\displaystyle \theta^- $$ to compute the target $$\displaystyle r + \gamma \max_{a'} Q(s',a';\theta^-) $$. Reduces target moving target problem, stabilizes training. Update $$\displaystyle \theta^- \leftarrow \tau \theta + (1-\tau)\theta^- $$ or periodically copy.

Advanced DQN Variants

• Double DQN: Decouples action selection and evaluation to reduce overestimation bias.

  Target: $$\displaystyle r + \gamma Q(s', \arg\max_a Q(s',a;\theta); \theta^-) $$

• Dueling DQN: Decomposes $Q(s,a)$ into value $V(s)$ and advantage $A(s,a)$: $$\displaystyle Q(s,a) = V(s) + A(s,a) $$. Learns both streams separately, then combines. Improves learning of state-values independent of specific actions.

Least Squares Policy Iteration (LSPI)

• Model-free policy iteration using least-squares regression.

• Core: Approximate the action-value function $Q(s,a)$ with a linear function: $$\displaystyle Q(s,a) = \theta^T \phi(s,a) $$, where $\phi$ are features (can be hand-crafted or from a neural network).

• Algorithm:

  1. Collect data with some policy $$\displaystyle \pi_k $$.

  2. Solve Bellman error minimization in closed form (least squares):

     $$\displaystyle \theta_{k+1} = \arg\min_{\theta} \mathbb{E} \left[ \left( Q(s,a;\theta) - (r + \gamma \max_{a'} Q(s',a';\theta_k)) \right)^2 \right] $$

  3. Improve policy: $$\displaystyle \pi_{k+1}(s) = \arg\max_a Q(s,a;\theta_{k+1}) $$.

• Advantage: No need for step-size tuning (closed form). Can use with function approximation (e.g., kernel methods, RBFs).

XII. Advanced Topics and Model Optimization

Deep Dream

• Goal: Visualize what neurons/layers in a trained CNN "see" or are sensitive to.

• Method: Start with an input image (or noise). Perform gradient ascent on the input to maximize the activation of a specific neuron/layer (or a weighted combination). The loss is the negative of the target activation.

  $$\displaystyle \mathbf{x}_{\text{new}} = \mathbf{x} + \eta \frac{\partial \text{Activation}_{\text{target}}}{\partial \mathbf{x}} $$

• Result: Surreal, dream-like images that strongly activate the chosen neuron, revealing its preferred patterns. Used for network interpretability and art.

Model Pruning and Compression

• Goal: Reduce model size/inference time by removing redundant parameters.

• Unit Pruning (Neuron/Filters): Remove entire neurons or convolutional filters based on their importance (e.g., L1 norm of weights). Reduces both parameters and computations.

• Weight Pruning: Set individual weights to zero (small magnitude). Creates sparse networks. Requires sparse matrix libraries for speedup.

• Process: Train large model → prune unimportant weights/units → fine-tune remaining weights. Iterate.

• Benefits: Smaller model size, faster inference (especially on specialized hardware), less memory.

GPU Acceleration for Linear Algebra

• GPUs excel at massively parallel computations (thousands of cores).

• Key for deep learning: Large matrix multiplications (e.g., $\mathbf{W}\mathbf{x}$ in layers, convolution as matrix multiplication via im2col).

• Randomized SVD on GPU: Computes approximate SVD $$\displaystyle \mathbf{A} \approx \mathbf{U}_k \mathbf{\Sigma}_k \mathbf{V}_k^T $$ using random projections. Steps:

  1. Draw random matrix $\mathbf{\Omega}$ (size $n \times k$).

  2. Form $$\displaystyle \mathbf{Y} = \mathbf{A} \mathbf{\Omega} $$ (GPU-accelerated matmul).

  3. Orthonormalize $\mathbf{Y}$ (QR) → $\mathbf{Q}$.

  4. Form $$\displaystyle \mathbf{B} = \mathbf{Q}^T \mathbf{A} $$ (smaller matmul).

  5. Compute SVD of $$\displaystyle \mathbf{B} = \hat{\mathbf{U}} \mathbf{\Sigma} \mathbf{V}^T $$.

  6. Final: $$\displaystyle \mathbf{U} = \mathbf{Q} \hat{\mathbf{U}} $$.

  • Advantage: Only 2 full matrix multiplies with $\mathbf{A}$, much faster than full SVD for large, low-rank approximations.

Recursive Neural Networks

• Architecture: For tree-structured data (e.g., sentences, parse trees, programs). Unlike RNNs (sequences), applies same neural network recursively over the tree structure.

• Mechanism:

  • Leaf nodes: Input embeddings (e.g., word vectors).

  • Internal nodes: Combine child representations $$\displaystyle \mathbf{h}_{\text{left}}, \mathbf{h}_{\text{right}} $$ via a composition function (e.g., a neural network): $$\displaystyle \mathbf{h}_{\text{parent}} = f(\mathbf{W} [\mathbf{h}_{\text{left}}; \mathbf{h}_{\text{right}}] + \mathbf{b}) $$.

  • Root node representation used for final prediction (e.g., sentiment).

• Training: Supervised. Loss computed at root. Gradients backpropagated through the tree structure (like backprop through a computational graph).

• Applications in NLP: Sentiment analysis (capturing compositionality), semantic relatedness, question answering.

XIII. Optimization in Information Retrieval and Traditional Machine Learning

Dimensionality Reduction for IR: Latent Semantic Indexing (LSI)

• Uses SVD on term-document matrix $\mathbf{A}$ (rows=terms, cols=docs).

• $$\displaystyle \mathbf{A} \approx \mathbf{U}_k \mathbf{\Sigma}_k \mathbf{V}_k^T $$ (rank-$k$ approximation).

• Interpretation:

  • $$\displaystyle \mathbf{U}_k \mathbf{\Sigma}_k $$: Reduced term vectors (in latent "concept" space).

  • $$\displaystyle \mathbf{V}_k \mathbf{\Sigma}_k $$: Reduced document vectors.

• Purpose: Map documents/terms to a lower-dimensional "semantic" space, overcoming synonymy and polysemy. Enables cosine similarity in reduced space.

Clustering

K-means Clustering

• Objective: Minimize within-cluster sum of squares (WCSS):

$$J = \sum_{i=1}^{k} \sum_{\mathbf{x} \in C_i} ||\mathbf{x} - \boldsymbol{\mu}_i||^2$$

where $$\displaystyle \boldsymbol{\mu}_i $$ is centroid of cluster $$\displaystyle C_i $$.

• Algorithm (Lloyd's):

  1. Initialize $k$ centroids (randomly or k-means++).

  2. Assignment Step: Assign each point to nearest centroid.

  3. Update Step: Recompute centroids as mean of assigned points.

  4. Repeat 2-3 until convergence.

• Choosing k:

  • Elbow Method: Plot $J$ vs $k$. Look for "elbow" where decrease slows.

  • Silhouette Score: Measures how similar an object is to its own cluster vs other clusters. Range [-1,1], higher is better.

Agglomerative Hierarchical Clustering

• Bottom-up approach. Start with each point as its own cluster. Iteratively merge closest pairs.

• Linkage Criteria (distance between clusters):

  • Single: Min distance between points in clusters. Sensitive to noise, forms chains.

  • Complete: Max distance. Favors compact clusters.

  • Average: Average pairwise distance. Good compromise.

• Result: Dendrogram. Can cut at any level to get any number of clusters.

Classification

Naive Bayes Classifier

• Based on Bayes' Theorem: $$\displaystyle P(y|\mathbf{x}) = \frac{P(\mathbf{x}|y) P(y)}{P(\mathbf{x})} $$

• "Naive" Assumption: Features are conditionally independent given the class $y$.

  $$\displaystyle P(\mathbf{x}|y) = \prod_{i=1}^{n} P(x_i|y) $$

• Prediction: $$\displaystyle \hat{y} = \arg\max_y P(y) \prod_{i=1}^{n} P(x_i|y) $$

• Parameter Estimation (MLE):

  • Prior: $$\displaystyle P(y) = \frac{\text{count}(y)}{N} $$

  • Conditional: For discrete features (Bernoulli/Multinomial NB): $$\displaystyle P(x_i|y) = \frac{\text{count}(x_i, y) + \alpha}{\text{count}(y) + \alpha n} $$ (Laplace smoothing $\alpha$).

• Advantages: Simple, fast, works well with high-dim data (text).

• Limitations: Strong independence assumption often violated. Can't capture feature interactions.

Term Weighting: TF-IDF

• Term Frequency (TF): Frequency of term t in document d. Often $$\displaystyle \text{tf}(t,d) = f_{t,d} $$ or $$\displaystyle \log(1+f_{t,d}) $$.

• Inverse Document Frequency (IDF): Measures how common the term is across the collection.

  $$\displaystyle \text{idf}(t) = \log \frac{N}{1 + |\{d: t \in d\}|} $$ (N = total docs).

• TF-IDF Weight: $$\displaystyle \text{tf-idf}(t,d) = \text{tf}(t,d) \times \text{idf}(t) $$.

• Purpose: Increase weight of terms frequent in a specific doc but rare in the collection (discriminative). Decrease weight of common stop words.

Recommendation Systems: Content-Based Filtering

• Idea: Recommend items similar to those a user liked in the past, based on item features.

• Components:

  1. Item Profile: Feature vector for each item (e.g., for movies: genre, director, actors; for documents: TF-IDF vector).

  2. User Profile: Built from features of items the user has interacted with (e.g., weighted average of item vectors).

  3. Similarity Metric: Compute similarity between user profile and candidate item profiles (e.g., cosine similarity).

• Optimization: Learn user profile weights or item feature weights to maximize click-through rate or rating prediction (can use regression/classification).

• Advantage: No cold-start for new items (if features known). Can provide explanations.

• Disadvantage: Limited by item features; cannot discover cross-domain preferences.

Distributed Optimization: MapReduce & Hadoop

• MapReduce Paradigm:

  • Map: Process input key-value pairs, emit intermediate key-value pairs.

  • Shuffle: Group all values with same key.

  • Reduce: Process each key and its list of values to produce final output.

• For ML (e.g., k-means, logistic regression):

  • Map: Each node computes partial gradients/counts on its data partition.

  • Reduce: Aggregate partial results (sum gradients, sum counts) to update global model parameters.

• Hadoop: Open-source implementation of MapReduce (HDFS for storage, YARN for resource management).

• Benefits: Scales to massive datasets by distributing computation across clusters. Fault-tolerant.

• Challenges: Communication overhead, stragglers, not ideal for iterative algorithms (many MapReduce jobs).

Relevance Feedback: Probabilistic Relevance Feedback

• Goal: Improve search results by using user feedback on initial results (relevant/non-relevant docs).

• Probabilistic Model (e.g., Robertson-Sparck Jones):

  1. Estimate probability that a document $\mathbf{d}$ is relevant to query $\mathbf{q}$: $P(R|d,q)$.

  2. Using Bayes: $P(R|d,q) \propto P(d|R,q) P(R|q)$.

  3. Query Expansion/Re-weighting: Adjust query term weights based on their distribution in relevant vs non-relevant docs.

     • Term weight update: $$\displaystyle w_t = \log \frac{(r_t + 0.5)(N - R - n_t + r_t + 0.5)}{(R - r_t + 0.5)(n_t - r_t + 0.5)} $$

     where $R$ = num relevant docs (feedback), $$\displaystyle r_t $$ = num relevant docs containing term $t$, $$\displaystyle n_t $$ = num docs containing term $t$, $N$ = total docs.

• Result: Expanded/weighted query better reflects user's information need.

\boxed{\text{END OF UNIT 5 NOTES}}