Information Retrieval (AL-503 (A)) - Unit 5 Short Notes

UNIT 5: Deep Learning

1. Foundations of Deep Learning

Historical Progression & Key Milestones

• 1940s-50s: McCulloch-Pitts neuron (1943), perceptron (Rosenblatt, 1958).

• 1980s: Backpropagation popularized (Rumelhart, Hinton, Williams, 1986). Early success on simple tasks.

• 2000s: "Deep Learning" renaissance. Key catalysts:

  • Large labeled datasets (ImageNet, 2009).

  • GPU computing for massive parallelization.

  • Algorithmic advances: ReLU activation, better initialization (He, Xavier), dropout, batch normalization.

  • Breakthroughs: AlexNet (2012, ImageNet win), GANs (2014), ResNet (2015), Transformer (2017).

• 2010s-Present: Dominance in vision (CNNs), NLP (RNNs, Transformers), speech, and reinforcement learning.

Representation Learning

• Definition: The automatic discovery of useful features/representations from raw data (e.g., pixels, words) without explicit human feature engineering.

• Core Idea: Deep neural networks learn a hierarchy of features—simple patterns in early layers combine to form complex, abstract concepts in deeper layers.

• Significance: Eliminates the need for domain-specific, manual feature extraction, making models more generalizable and powerful.

Learning Paradigms

[!TIP] Exam Distinction: Supervised learning has a "teacher" (labels). Unsupervised learning finds structure without labels. RL learns from trial-and-error via reward signals.

2. Neural Network Fundamentals

Architecture of a Simple Neural Network (Perceptron/MLP Unit)

A single neuron computes:

$$z = \mathbf{w}^T\mathbf{x} + b = \sum_{i=1}^{n} w_i x_i + b$$

$$\hat{y} = f(z)$$

where:

• $\mathbf{x}$ = input vector, $\mathbf{w}$ = weight vector, $b$ = bias.

• $f$ = activation function (non-linear).

• $\hat{y}$ = neuron's output.

Activation Functions

• Definition & Importance: Introduce non-linearity, enabling networks to learn complex, non-linear decision boundaries. Without them, a deep network collapses to a single linear transformation.

• Types & Characteristics:

  | Function | Formula | Range | Key Properties & Use Cases | | :--- | :--- | :--- | :--- | | Sigmoid | $$\displaystyle f(z) = \frac{1}{1+e^{-z}} $$ | (0, 1) | Smooth, outputs probabilities. Problems: Vanishing gradients, not zero-centered. Used in output layer for binary classification. | | Tanh | $$\displaystyle f(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}} $$ | (-1, 1) | Zero-centered, stronger gradients than sigmoid. Still suffers vanishing gradients. | | ReLU | $$\displaystyle f(z) = \max(0, z) $$ | [0, ∞) | Computationally cheap, sparsifies activations, mitigates vanishing gradient (for positive z). Dominant in hidden layers of CNNs/MLPs. | | Leaky ReLU | $$\displaystyle f(z) = \max(\alpha z, z) $$ (α~0.01) | (-∞, ∞) | Fixes "dying ReLU" problem (gradient=0 for z<0). | | Softmax | $$\displaystyle f(z_j) = \frac{e^{z_j}}{\sum_{k=1}^{K} e^{z_k}} $$ | (0, 1), sums to 1 | Used in output layer for multi-class classification. Converts logits to probability distribution. |

[!TIP] ReLU in CNNs: ReLU's sparsity (outputs zero for negative inputs) and computational efficiency make it ideal for the large, deep architectures of CNNs, helping mitigate vanishing gradients in very deep networks.

Feedforward Neural Networks (MLPs)

• Architecture: Input layer → one or more hidden layers (fully connected) → Output layer. Information flows forward only.

• Working Principle: Each neuron in layer l receives inputs from all neurons in layer l-1, computes a weighted sum, applies an activation function, and passes the result to the next layer.

• Representation Power: A network with a single hidden layer containing a finite but large number of sigmoid/tanh neurons is a Universal Approximator. It can approximate any continuous function on a compact domain to arbitrary precision (Cybenko, Hornik theorems). Deep networks (multiple hidden layers) can represent certain functions (e.g., highly compositional ones like parity) much more efficiently (exponentially fewer neurons) than shallow ones.

Backpropagation Algorithm

• Explanation: The core algorithm for training neural networks. It efficiently computes the gradient of the loss function with respect to all weights in the network using the chain rule.

• Weight Update Mechanism (Gradient Descent):

  1. Forward Pass: Compute network output $\hat{y}$ and loss $L(\hat{y}, y)$ for a batch.

  2. Backward Pass (Backprop): Starting from the output layer, propagate the error backward, computing $$\displaystyle \frac{\partial L}{\partial w} $$ for each weight using the chain rule.

  3. Update: Update weights using the gradient and an optimization algorithm (e.g., SGD, Adam):

$$w_{new} = w_{old} - \eta \cdot \frac{\partial L}{\partial w}$$

    where $\eta$ is the learning rate.

• Role: Enables the network to learn by iteratively adjusting weights to minimize the loss function.

3. Training Deep Neural Networks

Optimization Algorithms

Challenges: Vanishing & Exploding Gradients

• Problem: During Backpropagation Through Time (BPTT) for RNNs or deep forward nets, gradients are multiplied by weight matrices repeatedly.

  • Vanishing Gradient: Gradients shrink exponentially toward zero (if weights < 1). Early layers learn extremely slowly or not at all. Impact: Fails to learn long-range dependencies in sequences.

  • Exploding Gradient: Gradients grow exponentially (if weights > 1). Causes unstable, large weight updates.

• Mitigation Strategies:

  • Architectural: Use ReLU (gradient=1 for z>0), Residual Connections (ResNet) (create identity shortcut paths, gradient flows directly).

  • Normalization: Batch Normalization (stabilizes layer input distributions).

  • Gradient Clipping: Cap gradient norm to prevent explosion (common in RNNs).

  • Weight Initialization: He/Xavier initialization to keep activations/gradients in stable range.

  • Architectural Choice: Use LSTM/GRU for sequences (designed to mitigate vanishing gradient).

Regularization & Overfitting/Underfitting

• Overfitting: Model learns noise/training data specifics, performs poorly on new data. High variance.

• Underfitting: Model fails to capture underlying pattern. High bias.

• Prevention Techniques:

  • Dropout: During training, randomly "drop" (set to zero) a fraction p of neurons in a layer. Forces network to learn redundant representations and prevents co-adaptation. At test time, use all neurons with weights scaled by 1-p. Improves generalization significantly.

  • Weight Decay (L2 Regularization): Add penalty $$\displaystyle \frac{\lambda}{2} \|\mathbf{w}\|^2 $$ to loss. Encourages small weights, simpler models.

  • Batch Normalization: Has a slight regularization effect (adds noise via mini-batch statistics).

  • Data Augmentation: Artificially enlarge training set via transformations (rotation, crop for images; synonym replacement for text).

  • Early Stopping: Monitor validation loss; stop training when it starts rising.

Data Preprocessing

4. Convolutional Neural Networks (CNNs)

Core Architecture & Components

1. Convolutional Layer: Applies learnable filters (kernels) to input, producing feature maps.

   • Operation: $$\displaystyle Output(i,j) = \sum_{m}\sum_{n} Input(i+m, j+n) \cdot Kernel(m,n) + b $$

   • Parameters: Filter size, number of filters, stride (step size), padding.

2. Pooling Layer (Subsampling): Reduces spatial dimensions (width/height), provides translation invariance, reduces parameters.

   • Types: Max Pooling (take max in window), Average Pooling.

3. Padding: Adding zeros around input border to control output spatial size. 'same' padding preserves size; 'valid' (no padding) shrinks size.

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

Applications in Image Recognition

• Primary Domain: Image classification (AlexNet, VGG, ResNet), object detection (YOLO, Faster R-CNN), segmentation (U-Net).

• Why CNNs? Exploit spatial locality and translation invariance via shared weights (convolution) and pooling. Far more parameter-efficient than fully connected networks for grid-like data.

Data Formats for CNNs

[!TIP] Common Pitfall: Confusing channel ordering (channels_last vs. channels_first). Always check your deep learning framework's convention.

5. Recurrent Neural Networks (RNNs)

Fundamentals & Handling Sequential Data

• Core Idea: Have memory via a hidden state $$\displaystyle h_t $$ that propagates through time steps. Output at time t depends on current input $$\displaystyle x_t $$ and previous hidden state $$\displaystyle h_{t-1} $$.

• Equations (Simple RNN/Elman):

$$h_t = \tanh(W_{hh} h_{t-1} + W_{xh} x_t + b_h)$$

$$y_t = W_{hy} h_t + b_y$$

• Use Case: Natural Language Processing (language modeling, translation), time series forecasting, speech recognition. Handles variable-length sequences.

Backpropagation Through Time (BPTT)

• Unfolds the RNN through time steps (e.g., t=1 to T), creating a deep feedforward network.

• Applies standard backpropagation to this unfolded graph to compute gradients.

• Challenge: For long sequences, the computational graph becomes very deep, leading to vanishing/exploding gradients.

Deep RNN Architectures

• Stacked RNNs: Multiple RNN layers. Output of layer l at time t is input to layer l+1 at time t. Deeper temporal abstraction.

• Bidirectional RNNs (BiRNN): Two RNNs: one processes sequence forward ($$\displaystyle \overrightarrow{h_t} $$), one backward ($$\displaystyle \overleftarrow{h_t} $$). Final output $$\displaystyle y_t $$ often concatenates both states. Captures past and future context.

• Comparison with Feedforward NNs: FFNNs are memoryless; same input always gives same output. RNNs have internal state; output depends on entire history of inputs. RNNs are Turing-complete in principle.

Challenges with Long-Range Dependencies

• Simple RNNs struggle to learn dependencies where the relevant information is many steps apart (e.g., subject-verb agreement across long sentences).

• Primary Cause: Vanishing gradient problem during BPTT. Gradients from distant time steps are multiplied by small weights repeatedly, shrinking to near zero before reaching early time steps.

• Solution: Use gated architectures like LSTM or GRU.

6. Long Short-Term Memory (LSTM)

Detailed Working Mechanism

Designed to explicitly address the vanishing gradient problem and learn long-term dependencies.

• Core Concept: A cell state $$\displaystyle C_t $$ (the "conveyor belt") runs through the entire sequence, with minimal linear interaction. Information can be added/removed with regulated gates.

• Gates (all use sigmoid for 0-1 output, tanh for -1 to 1 candidate):

  1. Forget Gate $$\displaystyle f_t $$: Decides what information to remove from cell state.

     $$\displaystyle f_t = \sigma(W_f \cdot [h_{t-1}, x_t] + b_f) $$

  2. Input Gate $$\displaystyle i_t $$ & Candidate Cell State $$\displaystyle \tilde{C}_t $$: Decides what new information to store.

     $$\displaystyle i_t = \sigma(W_i \cdot [h_{t-1}, x_t] + b_i) $$

     $$\displaystyle \tilde{C}_t = \tanh(W_C \cdot [h_{t-1}, x_t] + b_C) $$

  3. Cell State Update: $$\displaystyle C_t = f_t \odot C_{t-1} + i_t \odot \tilde{C}_t $$ (⊙ = element-wise multiply). Forget old, add new.

  4. Output Gate $$\displaystyle o_t $$ & Hidden State $$\displaystyle h_t $$: Decides what to output based on filtered cell state.

     $$\displaystyle o_t = \sigma(W_o \cdot [h_{t-1}, x_t] + b_o) $$

     $$\displaystyle h_t = o_t \odot \tanh(C_t) $$

Advantages over Standard RNNs

• Mitigates Vanishing Gradient: The additive nature of the cell state update ($$\displaystyle C_t = ... + ... $$) creates a near-linear path for gradients to flow through many time steps.

• Explicit Memory Control: Forget and input gates allow precise, learned control over what information to retain or discard from the long-term memory ($$\displaystyle C_t $$).

• Empirically Superior: Consistently performs better on tasks requiring long-range context (e.g., machine translation, text generation).

7. Other Neural Network Architectures

Recursive Neural Networks

• Idea: Apply the same set of weights recursively over a structured, hierarchical input (e.g., a parse tree of a sentence), not just a linear sequence.

• Architecture: Each node in the tree is a neural network unit that combines its children's representations (vectors) to form its own representation. Root node yields final output.

• Use: Natural Language Processing (sentence-level semantics), computer vision (scene graph parsing).

• Difference from RNN: RNNs handle sequences (linear chain). Recursive NNs handle tree structures. Requires a predefined parse tree.

Autoencoders

• Purpose: Unsupervised dimensionality reduction and feature learning. Learn efficient data encoding (representation) by training to reconstruct its own input.

• Architecture: Encoder $f(x) \to z$ (compresses input to latent code z), Decoder $g(z) \to \hat{x}$ (reconstructs from z). Bottleneck layer forces compressed representation.

• Types:

  • Sparse Autoencoder: Adds a sparsity penalty (e.g., KL divergence) to hidden layer activations, encouraging only a few neurons to be active. Learns localized, interpretable features.

  • Contractive Autoencoder: Adds penalty on the Frobenius norm of the Jacobian of the encoder ($$\displaystyle \| \frac{\partial f(x)}{\partial x} \|_F^2 $$). Penalizes large changes in encoding for small input changes, leading to robust, locally invariant features.

• Regularization in Autoencoders: Prevents the trivial solution where the network just learns the identity function (z = x, \hat{x}=x). Achieved via:

  • Bottleneck constraint (small latent dimension).

  • Sparsity/contractive penalties.

  • Denoising Autoencoder (DAE): Train to reconstruct clean input from a corrupted version (e.g., added noise). Forces learning of meaningful features.

• Comparison with PCA/SVD:

  | Aspect | PCA/SVD | Autoencoder | | :--- | :--- | :--- | | Model | Linear transformation. | Deep, non-linear neural network. | | Representation | Orthogonal principal components. | Non-linear, distributed representation. | | Flexibility | Limited to linear subspace. | Can learn complex, non-linear manifolds. | | When to Use AE? | When data lies on a non-linear manifold or when you need features for a subsequent non-linear classifier (e.g., pre-training). |

Generative Models: GANs vs. VAEs

• Goal: Learn a distribution $p(x)$ to generate new, realistic data samples.

• Generative Adversarial Network (GAN):

  • Architecture: Two networks: Generator $G(z)$ (creates fake data from noise z), Discriminator $D(x)$ (classifies real vs. fake).

  • Training: Adversarial minimax game: $G$ tries to fool $D$, $D$ tries to distinguish. Objective: $$\displaystyle \min_G \max_D V(D,G) = \mathbb{E}[\log D(x)] + \mathbb{E}[\log(1-D(G(z)))] $$.

  • Pros: Generates sharp, high-fidelity samples (images).

  • Cons: Training unstable (mode collapse, difficult to evaluate), no explicit likelihood.

• Variational Autoencoder (VAE):

  • Architecture: Encoder outputs parameters ($\mu, \sigma$) of a latent distribution (usually Gaussian). Reparameterization trick: $$\displaystyle z = \mu + \sigma \odot \epsilon $$, $\epsilon \sim \mathcal{N}(0,I)$. Decoder reconstructs from z.

  • Training: Maximizes Evidence Lower Bound (ELBO) on log-likelihood: $$\displaystyle \mathcal{L} = \mathbb{E}[\log p(x|z)] - D_{KL}(q(z|x) \| p(z)) $$.

  • Pros: Stable training, explicit latent space structure, provides likelihood.

  • Cons: Generated samples often blurrier than GANs.

• Selection Criteria:

  • Choose GAN for maximum sample quality (e.g., photorealistic images), when likelihood is not needed.

  • Choose VAE for tasks needing a structured, interpretable latent space (interpolation, manipulation), or when training stability is critical.

Deep Belief Networks (DBNs)

• Architecture: Stack of Restricted Boltzmann Machines (RBMs). Each RBM is a bipartite graph (visible layer v, hidden layer h). Trained greedily, layer-by-layer (unsupervised pre-training).

• Purpose: Early method for pre-training deep neural networks before backpropagation was reliable for deep models. Initialize deep networks with useful weights. Largely superseded by better initialization and direct backpropagation (with ReLU, etc.).

Auto-regressive Models: NADE & MADE

• Core Idea: Model the joint distribution $p(x)$ as a product of conditionals: $$\displaystyle p(x) = \prod_{i=1}^{d} p(x_i | x_{<i}) $$. Each variable depends only on previous ones (ordered).

• NADE (Neural Autoregressive Distribution Estimator): Uses a single hidden layer with masked weights to ensure the autoregressive property (each output dimension only sees previous inputs). Efficient for likelihood computation.

• MADE (Masked Autoencoder for Distribution Estimation): Applies the masking idea to a deep autoencoder. Uses binary masks on weights to enforce the autoregressive dependency across layers. More powerful than NADE due to depth.

8. Advanced Deep Learning Topics

Deep Dream & Neural Network Activations

• Concept: A technique to visualize what neurons/layers in a trained CNN have learned. It amplifies the patterns that activate the network.

• Process: Start with an input image (or noise). Perform gradient ascent on the input image to maximize the activation of a specific neuron or layer (often a "loss" defined as the mean activation). The resulting image shows the "ideal" stimulus for that neuron—often surreal, dream-like patterns.

• Significance: Provides interpretability, reveals learned features (edges, textures, objects), and is used for artistic applications.

Model Compression: Unit Pruning

• Goal: Reduce the size/inference cost of a large trained network by removing redundant parameters/units.

• Unit Pruning (Neuron Pruning): Remove entire neurons (or filters in CNNs) based on a criterion (e.g., small L1 norm of weights, low activation magnitude).

• Process: 1) Train large network. 2) Prune unimportant units. 3) Fine-tune the smaller network. Iterate.

• Need: Deploy deep models on resource-constrained devices (mobile, IoT). Reduces memory, computation, energy.

Directed Graphical Models (Bayesian Networks)

• Definition: A probabilistic model representing a set of random variables and their conditional dependencies via a directed acyclic graph (DAG).

• Node: Random variable.

• Edge $$\displaystyle A \rightarrow B $$: Variable A is a direct cause/parent of B. Encodes conditional independence: $$\displaystyle P(B|A, \text{parents of } A) = P(B|A) $$.

• Joint Distribution: $$\displaystyle P(x_1, ..., x_n) = \prod_{i=1}^{n} P(x_i | \text{parents}(x_i)) $$.

• Connection to Deep Learning: Used in probabilistic deep learning (e.g., VAEs can be seen as directed models with latent variables). Provides a framework for reasoning under uncertainty.

Deep Reinforcement Learning

• Markov Decision Process (MDP): Formal framework for RL. Defined by $(S, A, P, R, \gamma)$:

  • $S$: State space.

  • $A$: Action space.

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

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

  • $\gamma$: Discount factor.

• Goal: Find a policy $\pi(a|s)$ (mapping states to actions) that maximizes expected discounted return $$\displaystyle G_t = R_{t+1} + \gamma R_{t+2} + ... $$.

• Value & Policy Iteration (Dynamic Programming):

  • Value Iteration: Iteratively apply Bellman Expectation Equation to compute optimal value function $$\displaystyle V^*(s) $$ until convergence. Then extract greedy policy $$\displaystyle \pi^*(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^*(s')] $$.

    • Complexity: $$\displaystyle O(|S|^2|A|) $$ per iteration.

  • Policy Iteration: Alternate between Policy Evaluation (compute $$\displaystyle V^\pi $$ for current $\pi$) and Policy Improvement (make policy greedy w.r.t $$\displaystyle V^\pi $$).

    • Complexity: Policy evaluation often requires solving a linear system ($$\displaystyle O(|S|^3) $$) or many iterations.

  • Comparison: Policy iteration often converges in fewer iterations but each iteration is costlier. Value iteration is simpler per iteration but may need many iterations. Both require full knowledge of $P$.

• Q-Learning & Advanced Algorithms:

  • Q-Learning: Model-free, off-policy TD control. Learns action-value function $Q(s,a)$ via:

$$Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$$

*   **Deep Q-Network (DQN):** Uses a deep NN to approximate $Q(s,a)$. Stabilized by **Experience Replay** (random mini-batch sampling) and **Fixed Q-Targets** (slowly updated target network).

*   **Double DQN:** Decouples action selection and evaluation to reduce overestimation bias in DQN. Uses online network to select $$\displaystyle \arg\max_a Q(s',a) $$, target network to evaluate $$\displaystyle Q_{\text{target}}(s', \arg\max_a Q(s',a)) $$.

*   **Dueling DQN:** Decomposes $Q(s,a)$ into **value stream** $V(s)$ and **advantage stream** $A(s,a)$: $$\displaystyle Q(s,a) = V(s) + A(s,a) - \frac{1}{|A|}\sum_{a'} A(s,a') $$. Learns better value estimates for states where action doesn't matter much.

*   **Least Squares Policy Iteration (LSPI):** A **policy iteration** method that uses **least-squares regression** (instead of solving a linear system) to fit the value function from samples. More sample-efficient than standard policy iteration with function approximation.

GPU Implementation of Randomized SVD

• Randomized SVD: Algorithm to compute a low-rank approximation $$\displaystyle A \approx U\Sigma V^T $$ of a matrix $A$ (size $m \times n$) using random projections. Faster than deterministic SVD for large matrices.

• GPU Implementation: Highly parallelizable.

  1. Generate random Gaussian matrix $\Omega$ (size $n \times k$, where k is target rank).

  2. Form $$\displaystyle Y = A \Omega $$ (matrix multiplication, highly parallel on GPU).

  3. Orthonormalize columns of $Y$ (QR decomposition) to get $Q$.

  4. Form $$\displaystyle B = Q^T A $$ (smaller matrix multiply).

  5. Compute SVD of small matrix $B$: $$\displaystyle B = \tilde{U} \Sigma V^T $$.

  6. Final left singular vectors: $$\displaystyle U = Q \tilde{U} $$.

• Applications in Deep Learning:

  • Eigen-decomposition of large Hessian/gradient covariance matrices (e.g., in K-FAC optimizer).

  • Low-rank approximation of weight matrices for model compression.

  • Analyzing layer activations/covariance for understanding representations.

  • Fast PCA on high-dimensional features.

9. Specific Models and Applications

Logistic Regression in Neural Network Context

• Definition: A linear model for binary classification that applies a sigmoid function to a linear combination of inputs.

$$P(y=1|x) = \sigma(z) = \frac{1}{1+e^{-(w^Tx + b)}}$$

• NN Interpretation: It is a single-layer neural network with:

  • No hidden layers.

  • A single output neuron.

  • Sigmoid activation function in the output layer.

  • Trained using cross-entropy loss and gradient descent (backpropagation reduces to simple logistic regression update).

• Significance: The simplest form of a neural network. Foundation for understanding binary classification and the link between linear models and neural nets.

Content-Based Recommendation Systems (IR Context)

• Goal: Recommend items similar to those a user has liked in the past, based on item features (content), not user behavior.

• Process:

  1. Item Representation: Represent each item as a feature vector (e.g., TF-IDF vector for text documents, CNN features for images, genre/actor vectors for movies).

  2. User Profile: Aggregate feature vectors of items the user has interacted with (e.g., average vector, weighted by rating).

  3. Similarity Matching: For a candidate item, compute cosine similarity (or dot product) between its feature vector and the user's profile vector.

  4. Ranking: Recommend items with highest similarity scores.

• Advantages: No cold-start problem for new items (if features are available). Transparent (can explain recommendation via shared features).

• Limitations: Limited by item feature quality. Cannot discover serendipitous recommendations across content types (e.g., "people who liked this also liked...").

Deep Learning in Reinforcement Learning Examples

• Deep Q-Network (DQN): Uses a deep CNN to approximate the Q-function from raw pixel inputs. Solved Atari 2600 games.

• Policy Gradient Methods (e.g., A3C, PPO): Use a deep network to directly parameterize the policy $$\displaystyle \pi_\theta(a|s) $$. The network outputs action probabilities (or mean/variance for continuous actions). Trained by optimizing expected return via gradient ascent on policy performance.

• Deep Deterministic Policy Gradient (DDPG): For continuous action spaces. Uses actor-critic architecture with deep networks for both policy (actor) and Q-function (critic).

• AlphaGo/AlphaZero: Combines deep CNNs (for board state evaluation) with Monte Carlo Tree Search (MCTS). Learns entirely through self-play (no human data).