Machine Learning - Stanford CS229

Stanford CS229: Machine Learning I Spring 2022 - YouTube

This course provides a comprehensive and mathematically-grounded introduction to the foundational principles, algorithms, and paradigms of modern machine learning. The curriculum is structured around the three core areas of the field: supervised, unsupervised, and reinforcement learning, building from classical models to the state-of-the-art.
In supervised learning, the course begins with the fundamentals of learning from labeled data. It starts with Linear Regression, deriving its least-squares cost function from the principle of Maximum Likelihood Estimation (MLE) under Gaussian assumptions. This probabilistic framework is then generalized to solve classification problems using Logistic Regression. These concepts are unified under the powerful abstraction of Generalized Linear Models (GLMs) and the Exponential Family of distributions, demonstrating how a vast array of models can be understood and optimized through a common lens. The course then tackles non-linearity through two key approaches: the classical elegance of Kernel Methods and the modern power of Neural Networks. The core training mechanism for deep learning, Backpropagation, is derived from first principles as an efficient application of the chain rule.
The practical realities of building effective models are addressed through a deep dive into generalization. The course covers the classical bias-variance trade-off to explain underfitting and overfitting, and introduces the modern phenomenon of double descent seen in overparameterized models. This motivates the use of regularization techniques, such as L1 (LASSO) and L2 (Weight Decay), to control model complexity. The full machine learning lifecycle is explored, emphasizing the critical importance of data splitting (train/validation/test), hyperparameter tuning, and data quality.
In unsupervised learning, the focus shifts to discovering hidden structure in unlabeled data. The course covers clustering with the classic k-means algorithm and the more sophisticated, probabilistic Gaussian Mixture Models (GMMs). The key algorithmic tool for these latent variable models, the Expectation-Maximization (EM) algorithm, is formally derived. The second major unsupervised task, dimensionality reduction, is explored through Principal Component Analysis (PCA), which finds directions of maximal variance, and Independent Component Analysis (ICA), which solves the "cocktail party problem" by assuming non-Gaussian, independent sources. These classical ideas build towards the modern paradigm of self-supervised learning, where models like Transformers are pre-trained on massive unlabeled datasets (e.g., by predicting the next word) to create powerful foundation models that can be adapted to numerous downstream tasks through fine-tuning or prompting.
Finally, the course provides a concise introduction to Reinforcement Learning (RL), the paradigm of learning to make sequential decisions. It establishes the formal language of Markov Decision Processes (MDPs)—including states, actions, rewards, and transitions. The concepts of the policy, the value function, and the recursive Bellman Equation are developed, culminating in the Value Iteration algorithm, a foundational dynamic programming method for finding the optimal policy when the environment's model is known.

L1: Introduction

The course is introduced by instructors Tony Ma, a researcher in machine learning theory (including RL and supervised learning), and Chris, who works on building large-scale, robust ML systems and has contributed to products like Google Search and Assistant. They frame the course as providing the absolute foundational layer of machine learning, which is more relevant than ever as ML products have become part of daily life. The course aims to give students insight into how these systems work and why significant research challenges remain.
2. Course Logistics and Administration
A significant portion of the lecture is dedicated to outlining the structure and expectations for the course.

• Teaching Team: The course is supported by a large team, including 12+ TAs, a head TA, and a course coordinator.
• Course Website: A central course website serves as a hub, linking to comprehensive Google Docs covering logistics, the syllabus, lecture notes, and project guidelines. Students are encouraged to consult these documents first before asking questions.
• Prerequisites: The course is described as mathematically intense. Students should be comfortable with at least two of the following three areas:
  • Probability (CS109 level): Concepts like random variables, expectation, variance, and conditional probability are essential.
  • Linear Algebra (Math 104/113 level): Matrix multiplication and eigenvectors are the most critical topics.
  • Programming (Python and NumPy): Homeworks will involve both mathematical derivations and coding. A lack of programming background could be difficult, as it can be hard to distinguish between a math error and a syntax/library error.
  • Support: The TAs will hold review lectures on these prerequisite topics.
• Honor Code: This is emphasized upfront due to past issues.
  • Collaboration is encouraged: Students can discuss homework problems in study groups.
  • Work must be independent: All solutions (code and write-ups) must be written up independently.
  • Acknowledge collaborators: The names of study group members must be listed on submissions.
  • Prohibited: Looking at or copying solutions from previous years is a strict violation.
• Course Components:
  • Homeworks: There will be four homework assignments.
  • Midterm: There is one midterm exam.
  • Final Project: A significant component done in groups of 1-3. Students apply ML to a topic of their interest. Past projects have covered a wide range of applications, from music and finance to core ML algorithm development. There is no final exam.
  • TA Lectures: Optional sessions covering prerequisite reviews and advanced topics not required for the course.
  • Discussion Sections: Optional, smaller, interactive sessions led by TAs to bridge the gap between lectures and homeworks by working through similar problems.

3. What is Machine Learning?
The lecture introduces the core concept of machine learning through two historical definitions.

1. Arthur Samuel (1959): The field of study that gives computers the ability to learn without being explicitly programmed. This distinguishes ML from traditional programming where every rule is hard-coded.
2. Tom Mitchell (1997): A more formal definition: "A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E."
   • Experience (E): Typically refers to data (e.g., a dataset of past games).
   • Task (T): The problem to be solved (e.g., playing checkers).
   • Performance Measure (P): A metric to evaluate success (e.g., the win rate).
   • Learning: The key is that performance improves as the program is exposed to more experience (data).

4. A Taxonomy of Machine Learning
The course is structured around three primary paradigms of machine learning, which are presented as distinct but often overlapping fields.

• Core Idea: Learning from a dataset containing labeled examples, where each example is a pair of an input x and a known output y. The goal is to learn a function that can predict the output y for a new, unseen input x.
• Running Example: House Price Prediction.
• Key Terminology:
  1. Features / Input (x): The attributes used for prediction (e.g., square footage, lot size).
  2. Label / Output / Supervision (y): The value to be predicted (e.g., price).
  3. Training Data: The dataset of (x, y) pairs.
• Two Main Types:
  1. Regression: The output y is a continuous value (e.g., predicting the exact price of a house). This is visualized by fitting a line or curve to a scatterplot.
  2. Classification: The output y is a discrete category (e.g., predicting whether a residence is a "house" or a "townhouse"). This is visualized by finding a decision boundary that separates the different classes.
• Broader Applications: Image classification (e.g., ImageNet), machine translation (predicting a sentence in one language from another), and object detection.
• Core Idea: Learning from a dataset that contains only inputs , with no corresponding labels y. The goal is to discover interesting patterns or hidden structures within the data.
• Clustering: A primary task in unsupervised learning. The algorithm groups similar data points together. For example, given house data without labels, a clustering algorithm could automatically discover that there seem to be two distinct types of residences.
• Applications:
  • Gene Clustering: Grouping individuals based on their genetic data to discover subtypes that may respond differently to treatments.
  • Topic Modeling: Analyzing a large corpus of documents (e.g., a word-document matrix) to automatically discover underlying topics (e.g., one cluster of words and documents is about space travel, another is about finance).
  • Word Embeddings: Representing words as vectors in a high-dimensional space. This allows the model to capture semantic relationships (e.g., vector('Italy') - vector('Rome') is parallel to vector('France') - vector('Paris')).
  • Foundation Models (e.g., GPT-3): A major breakthrough where gigantic models are pre-trained on vast amounts of unlabeled text (like Wikipedia). These single models can then be used to solve many different tasks (story generation, Q&A, unscrambling words) without task-specific training, demonstrating a powerful form of unsupervised learning.
• Core Idea: Learning to make a sequence of decisions in an environment to maximize a long-term reward.
• Key Distinctions:
  • Sequential Decisions: The agent takes a series of actions over time.
  • Long-Term Consequences: An action taken now can affect all future states and rewards.
  • Interactive Data Collection: Unlike supervised/unsupervised learning where the dataset is fixed, an RL agent actively collects its own data through trial and error. It tries a strategy, observes the feedback (rewards), and uses that new data to improve its strategy.
• Example: Humanoid Walking. A simulated robot learns to walk by trying different joint movements. Initially, it falls repeatedly. Over thousands of iterations, it refines its strategy based on the feedback of moving forward without falling, eventually learning a stable walking gait.

5. Other Course Topics
The lecture concludes by mentioning other key areas that will be covered, which cut across the three main paradigms:

• Deep Learning Basics: The techniques of using neural networks as the model class, which has been central to recent progress.
• Learning Theory: Understanding the trade-offs in ML, such as feature selection and overfitting, to achieve good generalization.
• Fairness and Robustness: A guest lecture will cover the critical societal impacts of ML, including issues of bias and reliability.

L2: Supervised Learning Set Up

This lecture, led by instructor Chris, marks the beginning of a three-lecture block focused on building the fundamental models of supervised learning. The plan is to start with the simplest case, linear regression, and then progressively generalize to classification and a broad class of models known as the exponential family. A key theme is that these seemingly different models can all be solved using the same underlying optimization algorithm: stochastic gradient descent.

• Logistics: The instructor highlighted the use of an Ed thread for live questions during the lecture to encourage participation. He also noted that handwritten notes and templates would be provided to facilitate following along.

2. Supervised Learning: Formal Setup and Notation

The lecture formally defined the supervised learning problem, establishing notation that will be used throughout the course.

• The Goal: To learn a prediction function (or hypothesis), denoted as h, which maps from an input space X to an output space Y.
• Examples:
  • Input (X): Images, text, or structured data like house features.
  • Output (Y): Discrete labels (e.g., 'cat', 'dog', 'hate speech') or continuous values (e.g., house price).
• The Training Set: The learning process is based on a given training set, which is a collection of n input-output pairs: {(x⁽¹⁾, y⁽¹⁾), (x⁽²⁾, y⁽²⁾), ..., (x⁽ⁿ⁾, y⁽ⁿ⁾)}.
  • Each x⁽ⁱ⁾ is an input or feature vector.
  • Each y⁽ⁱ⁾ is the corresponding output, label, or supervision.
• The Prediction Task: The ultimate goal is not just to perform well on the training data but to generalize and make accurate predictions on new, unseen inputs x that were not in the training set. This implies an underlying assumption that the training and future data are drawn from the same distribution.
• Regression vs. Classification:
  • Regression: The task of predicting a continuous output y (e.g., house prices).
  • Classification: The task of predicting a discrete output y (e.g., 'cat' or 'dog').

3. Linear Regression: The Model

The lecture focused on the simplest predictive model: the linear model.

• The Hypothesis Class: The function h is restricted to be a linear function of the input features. For an input vector x with d features, the prediction is:
  h_θ(x) = θ₀ + θ₁x₁ + ... + θ_d x_d
• Parameters (Weights): The model is defined by its parameters θ = [θ₀, θ₁, ..., θ_d]. Learning the model means finding the best values for these parameters.
• Notation Trick (Bias Term): To simplify the notation, a convention is adopted where an extra feature x₀ is always added to the input and set to 1. This allows the intercept term θ₀ (the "bias") to be treated just like any other weight, and the hypothesis can be written compactly using a dot product:
  h_θ(x) = Σ θ_j x_j = θᵀx
• Data as a Matrix: The entire training set can be represented as a design matrix X of size n x (d+1), where each row is a training example, and a vector y of n labels.

4. Finding the Best Model: The Cost Function

To find the "best" parameters θ, we need a way to measure how well a given model fits the data. This is done using a cost function (or loss function).

• Least Squares: For linear regression, the standard cost function is the sum of squared errors (also known as the residual sum of squares):
  J(θ) = (1/2) Σ [h_θ(x⁽ⁱ⁾) - y⁽ⁱ⁾]²
• The Optimization Problem: The goal of learning is to find the parameters θ that minimize this cost function:
  min_θ J(θ)
• Intuition: The model is considered good if its predictions h_θ(x⁽ⁱ⁾) are close to the true labels y⁽ⁱ⁾ on the training data. The squaring penalizes larger errors more heavily. The 1/2 is a convenience for making the derivative cleaner.

5. Solving the Optimization Problem: Gradient Descent

The lecture introduced gradient descent as a general-purpose algorithm for minimizing cost functions. This is the workhorse algorithm that will be reused for many other models.

• The Intuition: Imagine the cost function J(θ) as a landscape. To find the minimum, we start at a random point θ and repeatedly take small steps in the direction of the steepest descent, which is the negative of the gradient.
• The Update Rule:
  θ_j ← θ_j - α * (∂/∂θ_j) J(θ)
  • α is the learning rate, a hyperparameter that controls the size of each step.
  • The update is performed simultaneously for all parameters j.
• Computing the Gradient for Least Squares: By applying the chain rule, the partial derivative of the least squares cost function is derived:
  (∂/∂θ_j) J(θ) = Σ [h_θ(x⁽ⁱ⁾) - y⁽ⁱ⁾] * x_j⁽ⁱ⁾
  This has a simple and intuitive form: the gradient is the sum of the prediction error for each data point, scaled by the corresponding feature value.

6. Practical Optimization: Batch vs. Stochastic Gradient Descent

A major practical issue with the "batch" gradient descent described above is that it requires summing over the entire training dataset to compute a single gradient step. This is computationally infeasible for large datasets.

• Batch Gradient Descent: The update rule uses all n examples to compute the gradient. It is accurate but very slow.
• Stochastic Gradient Descent (SGD) / Mini-batch SGD: Instead of the full dataset, the gradient is approximated using only a small, random subset of the data called a mini-batch (e.g., B=1 or B=32 examples).
  • Update Rule: θ_j ← θ_j - α * Σ_{i in B} [h_θ(x⁽ⁱ⁾) - y⁽ⁱ⁾] * x_j⁽ⁱ⁾
• Trade-offs:
  • Speed vs. Accuracy: Mini-batch updates are much faster to compute but provide a "noisy" estimate of the true gradient.
  • Why it Works: This noise is often beneficial. The algorithm can make rapid progress initially. For datasets with a lot of redundant information (like many similar images), using a small batch is nearly as informative as using the full dataset.
• Modern Practice: Almost all modern machine learning is trained using mini-batch SGD or its more sophisticated adaptive variants.

7. The Normal Equations (Briefly Mentioned)

The lecture concluded by briefly mentioning the normal equations, which provide a closed-form, analytical solution for the least squares problem: θ = (XᵀX)⁻¹Xᵀy. While useful for understanding the linear algebra of the problem and for small datasets, this method is not used in practice for large-scale ML because computing the matrix inverse is prohibitively expensive (O(d³)). The iterative gradient descent methods are far more scalable.

L3: Weighted Least Squares, Logistic Regression, NM

The lecture, led by instructor Chris, continues the structured development of supervised learning models. The primary goal is to generalize the concepts from linear regression to solve classification problems. The core pedagogical strategy is to demonstrate how a probabilistic interpretation of linear regression provides a powerful framework that can be extended to classification and, in the next lecture, to a much broader set of models known as the exponential family. This approach reveals the deep, parallel structure underlying many machine learning algorithms and their optimization methods.
2. A Probabilistic Interpretation of Linear Regression
The lecture began by revisiting the linear regression model from the previous session and providing a deeper justification for its cost function (the sum of squared errors).

• The Generative Model: Instead of just positing a cost function, a generative story for the data is assumed. The true label y is modeled as a linear function of the features x plus some random error or noise term ε.
  y⁽ⁱ⁾ = θᵀx⁽ⁱ⁾ + ε⁽ⁱ⁾
• Assumptions about the Error Several key assumptions are made about this unmodeled error term:
  1. The errors are independent and identically distributed (i.d.). The noise affecting one data point is independent of the noise affecting another.
  2. The errors are Gaussian (normally) distributed with a mean of 0 and some variance σ². This is written as ε⁽ⁱ⁾ ~ N(0, σ²).
• The Justification for the Gaussian Assumption: The Gaussian distribution is the unique choice that maximizes entropy given a fixed mean and variance. It also arises naturally from the Central Limit Theorem when noise is the sum of many small, independent factors.
• Deriving the Likelihood: These assumptions imply that the conditional probability of a label y given an input x is also Gaussian:
  p(y⁽ⁱ⁾ | x⁽ⁱ⁾; θ) ~ N(θᵀx⁽ⁱ⁾, σ²)
  Using this, we can write down the likelihood of observing the entire dataset's labels given the features and the model parameters θ. Due to the independence assumption, the total likelihood is the product of the individual probabilities for each data point.
• Maximum Likelihood Estimation (MLE): The goal is to find the parameters θ that maximize the likelihood of the observed data. Instead of maximizing the likelihood directly, it's mathematically more convenient to maximize the log-likelihood. When the log is applied to the Gaussian probability density function, the product turns into a sum, and the exponential term simplifies.
• Connecting to Least Squares: After taking the log and dropping terms that don't depend on θ, maximizing the log-likelihood is shown to be equivalent to minimizing the sum of squared errors:
  argmax_θ log L(θ) <=> argmin_θ (1/2) Σ [y⁽ⁱ⁾ - θᵀx⁽ⁱ⁾]²
  This provides a principled, probabilistic justification for the least squares cost function used in the previous lecture.

3. Classification and Logistic Regression
The lecture then pivoted from regression (continuous outputs) to classification (discrete outputs).

• The Problem with Linear Regression for Classification: While one could try to fit a line to binary (0/1) data, it's a poor fit. The model can predict values outside the range, and it is sensitive to outliers, which can drastically shift the decision boundary.
• Logistic Regression Model:
  1. The Hypothesis: To solve these issues, logistic regression introduces a non-linear "squashing" function, the sigmoid (or logistic) function, g(z) = 1 / (1 + e⁻ᶻ). The hypothesis is now:
     h_θ(x) = g(θᵀx)
  2. This function takes the linear output θᵀx and maps it to the range (0, 1), which can be naturally interpreted as a probability.
• Probabilistic Interpretation: The output of the hypothesis is interpreted as the probability of the positive class:
  P(y=1 | x; θ) = h_θ(x)
  P(y=0 | x; θ) = 1 - h_θ(x)
• Deriving the Cost Function: Following the same maximum likelihood estimation playbook as with linear regression:
  1. Write down the likelihood of the data, which is a product over the training examples. A clever trick is used to write the probability for a single data point compactly: P(y|x;θ) = (h_θ(x))^y * (1 - h_θ(x))^(1-y).
  2. Take the log to get the log-likelihood.
  3. The goal is to find the θ that maximizes this log-likelihood.
• The Gradient: Remarkably, when the gradient of the logistic regression log-likelihood is computed, it takes on the exact same form as the gradient for linear regression:
  ∇_θ J(θ) = Σ [y⁽ⁱ⁾ - h_θ(x⁽ⁱ⁾)] * x⁽ⁱ⁾
  The only difference is that h_θ(x) is now the sigmoid function instead of a simple dot product. This demonstrates the power of the abstract framework: the same gradient descent update rule applies, just with a different hypothesis function.

4. Optimization: Newton's Method
The lecture introduced Newton's method as a powerful, alternative optimization algorithm to gradient descent.

• The Goal: Instead of minimizing a function l(θ), Newton's method finds the root of its derivative, i.e., it solves l'(θ) = 0.
• The Update Rule (1D): It works by iteratively approximating the function with its tangent line and finding where the tangent line crosses the x-axis.
  θ ← θ - f(θ) / f'(θ)
• The Update Rule (Multidimensional): The multidimensional version for minimizing a cost function J(θ) is:
  θ ← θ - H⁻¹ ∇_θ J(θ)
  • ∇_θ J(θ) is the gradient (a vector of first derivatives).
  • H is the Hessian (a d x d matrix of second partial derivatives).
• Comparison to Gradient Descent:

  Method	Cost per Iteration	Convergence Rate
  Gradient Descent (Batch)	O(nd)	Slow (Linear)
  Newton's Method	O(n*d + d³)	Very Fast (Quadratic)

• The Trade-off: Newton's method converges in far fewer iterations (it's "quadratically fast"), but each iteration is extremely expensive. It requires computing and inverting the d x d Hessian matrix, an O(d³) operation. This is infeasible for modern machine learning models where d (the number of parameters) can be in the millions or billions.
• Conclusion: For this reason, while historically important and powerful for small- to medium-sized problems (and still used in classical statistics), Newton's method is not the workhorse of large-scale machine learning. That role is firmly held by stochastic gradient descent and its variants, which have much cheaper iterations despite taking more steps to converge.

L4: Exponential Family, Generalized Linear Methods

This lecture, led by instructor Chris, concludes the foundational block on supervised learning by introducing a powerful abstraction: the Exponential Family of distributions. This framework is crucial because it unifies many of the models seen so far (like linear and logistic regression) under a single theoretical umbrella. Understanding this family provides a "recipe" for constructing, analyzing, and optimizing a wide range of machine learning models, a pattern that will reappear in unsupervised learning.
2. Revisiting Linear Regression with a Probabilistic View
The lecture began by formalizing the probabilistic interpretation of linear regression to set the stage for generalization.

• Generative Model: The core assumption is that a target variable y is generated from a linear model θᵀx plus some random, zero-mean Gaussian noise ε.
• Likelihood: This assumption leads to a Gaussian likelihood function. The task of finding the best parameters θ becomes a Maximum Likelihood Estimation (MLE) problem.
• Equivalence to Least Squares: Maximizing the log-likelihood of this Gaussian model is mathematically equivalent to minimizing the sum of squared errors. This provides a principled, probabilistic justification for the least squares cost function.

3. The Exponential Family of Distributions
This is the central concept of the lecture. It is a class of probability distributions whose probability density/mass function can be written in a specific canonical form.

• The Canonical Form: A distribution p(y; η) belongs to the exponential family if it can be written as:
  p(y; η) = b(y) * exp(ηᵀT(y) - a(η))
  1. η (eta): The natural parameter of the distribution.
  2. T(y): The sufficient statistic, which is a function that captures all the relevant information from the data y about the parameter η. In many simple cases, T(y) = y.
  3. a(η): The log partition function, which acts as a normalizer to ensure the distribution integrates/sums to 1.
  4. b(y): The base measure.
• The Power of the Framework: The significance of this form is that many common distributions—including the Bernoulli, Gaussian, Poisson, Gamma, and Dirichlet—are members of the exponential family. By showing a distribution can be massaged into this form, we can apply a general set of tools for inference and learning.
• Key Properties:
  1. The log-likelihood function for any exponential family model is concave, which guarantees that gradient descent will find the single global optimum.
  2. The derivatives of the log partition function a(η) give the moments of the distribution. Specifically, the first derivative is the expected value of the sufficient statistic E[T(y)], and the second derivative is its variance. This provides a mechanical way to perform inference.

4. Generalized Linear Models (GLMs)
GLMs provide the recipe for building a supervised learning model using the exponential family. It consists of three design choices/assumptions:

1. Output Distribution: Assume that the conditional distribution p(y | x; θ) is a member of the exponential family (e.g., Gaussian for regression, Bernoulli for binary classification).
2. Linearity Assumption: Assume that the natural parameter η is a linear function of the input features x: η = θᵀx.
3. Prediction: The model's prediction h_θ(x) is defined as the expected value of the target variable E[y | x; θ].

• The GLM "Recipe": Given a new problem, a practitioner chooses the appropriate distribution from the exponential family based on the data type (e.g., counts -> Poisson). The GLM framework then automatically specifies the hypothesis function and the learning objective (maximize log-likelihood). The optimization is guaranteed to be a concave problem, which can be solved with gradient ascent.
• The Unified Gradient: Just as with logistic regression, the gradient of the log-likelihood for any GLM takes on the same elegant form:
  ∇_θ J(θ) = Σ [y⁽ⁱ⁾ - h_θ(x⁽ⁱ⁾)] * x⁽ⁱ⁾
  This highlights the unifying power of the framework: learning is always about stepping in a direction proportional to the prediction error.

5. Multiclass Classification and Softmax Regression
The final part of the lecture extended these ideas from binary to multiclass classification, where the output y can take on one of k discrete values.

• The Model: This is handled by a generalization of logistic regression called softmax regression.
  • Instead of one set of parameters, the model has a separate parameter vector θ_j for each class j.
  • The model computes a "score" θ_jᵀx for each class.
  • These scores are then converted into a probability distribution using the softmax function:
    P(y=k | x; θ) = exp(θ_kᵀx) / Σ_{j=1 to k} exp(θ_jᵀx)
  • The softmax function exponentiates the scores (making them positive) and normalizes them so they sum to 1, creating a valid probability distribution.
• One-Hot Encoding: The labels y are represented as one-hot vectors (e.g., for k=4, the label "cat" might be [1, 0, 0, 0]).
• Learning: The model is trained by maximizing the log-likelihood of the data, which is equivalent to minimizing the cross-entropy loss. Once again, this is a concave optimization problem that can be solved efficiently with gradient-based methods.
• Connection to GLMs: Softmax regression is also an instance of a Generalized Linear Model, where the underlying distribution is the Multinomial distribution.

6. Summary and Look Ahead
The lecture concluded a three-part series on the foundations of supervised learning. The key takeaway is the power of abstraction. By understanding the probabilistic framework of GLMs and the exponential family, students can see that many seemingly different algorithms (linear regression, logistic regression, softmax regression, Poisson regression, etc.) are all instances of the same underlying principles and can be solved with the same core optimization techniques. The course will next move on to more advanced supervised learning topics like Support Vector Machines and Kernel Methods.

L5: Gaussian Discriminant Analysis, Naive Bayes

The lecture, led by instructor Tony, introduces a fundamental distinction between two major classes of learning algorithms.

• Discriminative Learning Algorithms:
  • What they do: Directly model the conditional probability p(y | x; θ).
  • How they work: They learn a direct mapping from inputs x to outputs y, or more formally, they learn a decision boundary that separates the classes. The algorithms covered in the previous lectures, like linear and logistic regression (which are instances of Generalized Linear Models), fall into this category. They focus on discriminating between different classes without caring about how the input data x itself is distributed.
• Generative Learning Algorithms:
  • What they do: Model the joint probability p(x, y; θ).
  • How they work: They take a more roundabout approach. By modeling the joint distribution, which can be factored as p(x | y; θ) * p(y; θ), they learn a model of how the data is generated.
    1. First, model the class prior p(y): What is the overall probability of seeing a positive or negative example?
    2. Second, model the class-conditional probability p(x | y): Given that an example belongs to a certain class, what is the distribution of its features x?
  • Prediction: To make a prediction for a new x, they use Bayes' rule to invert the conditional probability and find the posterior p(y | x), which is what is ultimately needed for classification. p(y | x) ∝ p(x | y) * p(y).

2. Gaussian Discriminant Analysis (GDA)
GDA is the first generative learning algorithm presented, designed for classification tasks where the input features x are continuous.

• The Model Assumptions:
  1. The class prior p(y) is modeled as a Bernoulli distribution with parameter φ. This simply means there's a certain probability φ of an example being in the positive class (y=1) and 1-φ for the negative class (y=0).
  2. The class-conditional distributions p(x | y) are modeled as multivariate Gaussian distributions.
     • p(x | y=0) is a Gaussian with mean μ₀ and covariance Σ.
     • p(x | y=1) is a Gaussian with mean μ₁ and covariance Σ.
• Key Simplification: For simplicity in this model, it is assumed that both classes share the same covariance matrix . The classes are only distinguished by their different means (μ₀ and μ₁).
• Parameters: The complete set of parameters to be learned for the GDA model is {φ, μ₀, μ₁, Σ}.

3. Learning the Parameters via Maximum Likelihood Estimation (MLE)
The core principle for fitting a generative model is Maximum Likelihood Estimation. The goal is to find the set of parameters that makes the observed training data most probable.

• The Likelihood Function: The likelihood L(parameters) is the probability of the entire dataset given the parameters. Due to the i.i.d. assumption, this is the product of the joint probabilities p(x⁽ⁱ⁾, y⁽ⁱ⁾) for each example in the training set.
• The Log-Likelihood: For mathematical convenience (turning products into sums), the log-likelihood is maximized instead.
• Finding the Maximum: The maximum is found by taking the partial derivatives of the log-likelihood with respect to each parameter (φ, μ₀, μ₁, Σ), setting them to zero, and solving the resulting system of equations.
• The MLE Solutions: The lecture presented the solutions (which are derived in the homework):
  • φ: The fraction of positive examples in the dataset. (Number of y=1 examples) / n.
  • μ₀: The empirical average of the feature vectors x for all negative examples. (1 / |y=0|) * Σ_{i:y⁽ⁱ⁾=0} x⁽ⁱ⁾.
  • μ₁: The empirical average of the feature vectors x for all positive examples.
  • Σ: The weighted average of the empirical covariance matrices of the positive and negative examples.

These results are highly intuitive: the parameters that best explain the data are simply the empirical statistics calculated from that data.
4. Making Predictions with the GDA Model
Once the parameters are learned from the training data, the model can be used to make predictions on a new, unseen input x.

• The Goal: To find the class y that maximizes the posterior probability p(y | x). For binary classification, this is equivalent to checking if p(y=1 | x) > 0.5.
• The Decision Boundary: The set of points x where p(y=1 | x) = 0.5 defines the decision boundary.
• The Key Result: The lecture showed that for the GDA model, after applying Bayes' rule and simplifying the math, the posterior probability p(y=1 | x) takes the form of the sigmoid function applied to a linear function of x:
  p(y=1 | x) = 1 / (1 + exp(-(θᵀx + θ₀)))
  This is a remarkable result: the GDA model, despite being a generative algorithm with strong assumptions about the data distribution, results in a linear decision boundary, just like logistic regression (a discriminative algorithm).

5. GDA vs. Logistic Regression: A Deeper Look
The fact that these two very different modeling approaches lead to similar functional forms for the posterior probability p(y|x) raises a crucial question: when should one be preferred over the other?

• Assumptions: GDA makes much stronger assumptions about the data (that p(x|y) is Gaussian and p(y) is Bernoulli). Logistic regression makes weaker assumptions, only modeling p(y|x) directly as a sigmoid of a linear function.
• The Trade-off:
  • If the GDA assumptions are correct (or nearly correct), GDA is more data-efficient. It can learn a good model from less data because its strong assumptions provide a useful inductive bias.
  • If the GDA assumptions are incorrect (e.g., if the data is not Gaussian), Logistic Regression is more robust. Because it makes fewer assumptions, it is less susceptible to being misled by model misspecification and will often perform better, especially with large amounts of data.
• Conclusion: In practice, because it is more robust to violations of its modeling assumptions, Logistic Regression is used far more often than GDA. However, GDA provides a powerful conceptual link between generative modeling and the discriminative classifiers seen in previous lectures.

L6: Naive Bayes, LaPlace Smoothing

The lecture, led by instructor Tony, began with a concise review of GDA, the generative learning algorithm for continuous features introduced in the previous session.

• Generative Pipeline:
  1. Model: Assume a probabilistic model for the data. For GDA, this means assuming the class-conditional densities p(x|y) are multivariate Gaussian and the class prior p(y) is Bernoulli.
  2. Learn: Fit the model parameters (φ, μ₀, μ₁, Σ) by maximizing the joint log-likelihood of the data. The solutions are intuitive empirical estimates (e.g., φ is the fraction of positive examples, μ₀ is the mean of the negative examples).
  3. Predict: For a new input x, use the learned parameters and Bayes' rule to compute the posterior probability p(y|x). The prediction is the class with the higher posterior probability.
• Key Result: The decision boundary for GDA (where p(y=1|x) = p(y=0|x)) is a linear function of x.

2. GDA vs. Logistic Regression: A Deeper Comparison
A key discussion centered on the trade-offs between generative (GDA) and discriminative (Logistic Regression) models, both of which can produce linear classifiers.

• Assumptions: The primary difference lies in the strength of their assumptions.
  • GDA (Strong Assumptions): Models the full joint distribution p(x,y), requiring strong assumptions about how the features x are generated (i.e., they are Gaussian).
  • Logistic Regression (Weaker Assumptions): Directly models the conditional probability p(y|x) and makes no assumptions about the distribution of x.
• The Trade-off:
  • Data Efficiency: If the strong assumptions of GDA are correct (or nearly so), it is more data-efficient. It can learn a good model from fewer examples because the assumptions provide a powerful inductive bias.
  • Robustness: If the assumptions are incorrect (e.g., the data is not Gaussian), GDA's performance can suffer. Logistic Regression, with its weaker assumptions, is more robust to model misspecification and often performs better in practice, especially with large datasets.
• Modern Trend: In the era of big data, the trend is towards models with fewer assumptions (like neural networks and discriminative models) because the sheer volume of data often outweighs the benefits of strong, potentially incorrect, prior knowledge.

3. Naive Bayes for Text Classification (Spam Filtering)
The lecture then introduced a new generative algorithm, Naive Bayes, specifically for the task of spam classification, where the input features x are discrete.

• Step 1: Feature Representation for Text:
  • A simple bag-of-words approach is used to convert an email into a feature vector.
  • First, a vocabulary (a dictionary of, say, 50,000 words) is fixed.
  • An email is then represented as a binary feature vector of the same dimension as the vocabulary.
  • x_j = 1 if the j-th word in the vocabulary appears in the email, and x_j = 0 otherwise.
  • This representation ignores word order and frequency but is simple and effective.
• Step 2: The Naive Bayes Model:
  • The model follows the generative recipe: model p(y) and p(x|y).
  • p(y) is again modeled as a Bernoulli distribution.
  • The crucial assumption is the Naive Bayes assumption: the features x_j (the presence or absence of words) are conditionally independent given the class .
    p(x|y) = Π_{j=1 to d} p(x_j | y)
  • This is a "naive" and clearly false assumption (e.g., the presence of the word "machine" makes the word "learning" much more likely), but it works surprisingly well in practice and dramatically simplifies the model.
  • Each p(x_j | y) is a simple Bernoulli distribution, parameterized by φ_{j|y=1} (the probability of word j appearing in a spam email) and φ_{j|y=0} (the probability of word j appearing in a non-spam email).
• Step 3: Learning with MLE:
  • The parameters are again learned by maximizing the joint log-likelihood of the data.
  • The solutions are again intuitive counts:
    • φ_y (prior for spam) = (Number of spam emails) / (Total emails)
    • φ_{j|y=1} (prob. of word j in spam) = (Number of spam emails containing word j) / (Number of spam emails)
    • A similar formula applies for φ_{j|y=0}.

4. A Practical Problem: The Zero-Probability Issue
A critical issue arises with the MLE estimates for Naive Bayes.

• The Problem: If a word (e.g., "aardvark") never appears in any spam emails in the training set, its estimated probability φ_{"aardvark"|y=1} will be zero. If a new test email then contains this word, the entire conditional probability p(x|y=1) will become zero (due to the product over words), because one of its terms is zero. This leads to a 0/0 situation when calculating the posterior p(y|x) via Bayes' rule, and the model breaks.
• The Cause: This is a consequence of overfitting to the training data. The model becomes absolutely certain that an unseen word can never appear.

5. The Solution: Laplace Smoothing
To fix the zero-probability problem, a simple and effective technique called Laplace smoothing is introduced.

• The Intuition: Instead of trusting the empirical counts completely, we "pretend" to have seen each outcome one extra time. This prevents any probability from ever being exactly zero or one.
• The Formula (for a Bernoulli): Instead of estimating the probability of heads as (num_heads) / (num_heads + num_tails), the Laplace-smoothed estimate is:
  φ = (num_heads + 1) / (num_heads + num_tails + 2)
• Applying to Naive Bayes: The formulas for the word probabilities are adjusted:
  φ_{j|y=1} = (num_spam_with_word_j + 1) / (num_spam + 2)
• Effect: This ensures that even words unseen in the training data are assigned a small, non-zero probability, making the model more robust and preventing the 0/0 issue. The effect of smoothing is most pronounced for small datasets and diminishes as the amount of data grows.

L7: Kernels

The lecture, led by instructor Tony, addresses a fundamental limitation of the linear models discussed so far: they cannot capture non-linear relationships in data.

• The Problem: Using a simple regression example where the data clearly follows a cubic curve, it's shown that a simple linear model (y = θᵀx) would be a poor fit.
• A Simple Solution: The immediate solution is to manually create a model that is non-linear in the input x but remains linear in the parameters θ. For the cubic example, the hypothesis becomes:
  h_θ(x) = θ₃x³ + θ₂x² + θ₁x + θ₀
• The Feature Map: This is formalized by introducing a feature map, φ(x). This is a function that transforms the original low-dimensional input x into a new, higher-dimensional feature vector. For the cubic example, the one-dimensional input x is mapped to a four-dimensional feature vector:
  φ(x) = [1, x, x², x³]
• Reduction to Linear Regression: With this transformation, the non-linear model can be rewritten as a standard linear model in the new feature space:
  h_θ(x) = θᵀφ(x)
  This means all the machinery of linear regression (like gradient descent) can be applied directly, just by first transforming the input data x into φ(x).

2. The Computational Challenge of High-Dimensional Features
While the feature map approach is powerful, it quickly becomes computationally infeasible as the dimensionality of the original input d and the complexity of the feature map (e.g., the degree of the polynomial) increase.

• The Combinatorial Explosion: If the original input x is d-dimensional, creating features for all cubic monomials results in a new feature vector φ(x) whose dimension p is on the order of O(d³)
• The Runtime Problem: The runtime of gradient descent is proportional to the number of features p. If d=1000, then p becomes a billion (10⁹), making each gradient update step prohibitively slow (O(n*p)). This computational bottleneck makes the explicit feature map approach impractical for many real-world problems.

3. The Kernel Trick: A Computational Shortcut
The central topic of the lecture is the kernel trick, a profound idea that allows us to reap the benefits of high-dimensional (even infinite-dimensional) feature spaces without ever explicitly computing or storing the feature vectors.

• Key Observation: A close inspection of the gradient descent update rule for the feature-mapped linear regression reveals that the feature vectors φ(x) only ever appear inside inner products of the form φ(x⁽ⁱ⁾)ᵀ φ(x⁽ʲ⁾).
• The Kernel Function: A kernel is a function K(x, z) that is defined to be equal to this inner product in the high-dimensional feature space:
  K(x, z) = φ(x)ᵀ φ(z)
• The "Trick": If we can compute the value of the kernel function K(x, z) efficiently (i.e., much faster than explicitly computing φ(x) and φ(z) and then their inner product), we can rewrite the entire algorithm to only use the kernel function, completely bypassing the need for the explicit feature map φ.
• Example (Polynomial Kernel): The lecture demonstrates this for the cubic polynomial feature map. The inner product φ(x)ᵀ φ(z) can be algebraically simplified to (xᵀz + 1)³.
  • Without the trick: Computing φ(x) and φ(z) takes O(d³) time, and their inner product takes another O(d³) time.
  • With the trick: We can compute xᵀz in O(d) time and then cube the result. This reduces the computational cost from cubic in d to linear in d, a massive saving.

4. The Kernelized Algorithm and the Change of Mindset
This insight leads to a new, kernelized version of the learning algorithm.

• Dual Representation: It is shown that the learned parameter vector θ can always be represented as a linear combination of the feature vectors of the training data: θ = Σ βᵢ φ(x⁽ⁱ⁾). This means we can optimize over the n scalar coefficients βᵢ instead of the p parameters in θ.
• Kernelized Gradient Descent: By substituting this dual representation and the kernel function into the gradient descent update, we arrive at an algorithm that updates the β coefficients and whose runtime depends on n (the number of data points) and d (the original feature dimension), but not on (the high-dimensional feature space).
• The New Mindset: This leads to a powerful shift in perspective. Instead of starting with a feature map φ and deriving a kernel K, we can start by designing a kernel function K directly. As long as we can guarantee that K corresponds to some inner product in some feature space (i.e., it is a "valid" kernel), we can run the kernelized algorithm without ever needing to know what the feature map φ is.
• Infinite-Dimensional Features: This is particularly powerful because some kernels, like the popular Gaussian (or RBF) kernel, correspond to an infinite-dimensional feature space. The kernel trick allows us to work with these incredibly expressive models computationally.

5. Valid Kernels and Mercer's Theorem
A crucial question is how to know if a function K(x, z) is a valid kernel.

• The Kernel Matrix: For any set of n data points, we can construct an n x n kernel matrix (or Gram matrix) K, where K_ij = K(x⁽ⁱ⁾, x⁽ʲ⁾).
• Mercer's Theorem: A function K is a valid kernel if and only if the corresponding kernel matrix is positive semidefinite (PSD) for any set of input points. This theorem provides the mathematical foundation for designing and validating new kernel functions.

6. Summary and Modern Context

• The Kernel Trick: A technique to make algorithms using high-dimensional feature maps computationally efficient by replacing inner products in the feature space with a kernel function.
• Kernelized Algorithms: Not all algorithms can be "kernelized." It is only possible if the algorithm can be rewritten such that the data only appears within inner products.
• Strengths: Allows for the use of very powerful, non-linear models (even with infinite-dimensional features).
• Weaknesses and Modern Perspective:
  • The runtime of kernel methods typically scales with n², which is prohibitive for very large datasets (where n is in the millions).
  • Kernels are "hand-crafted" features. A major reason for the success of deep learning is that neural networks can be seen as learning the feature map φ from the data, rather than having it be fixed in advance. This learnable feature representation is often more powerful and flexible than a fixed kernel.

L8: Neural Networks 1

The lecture, given by instructor Masha, serves as an introduction to deep learning and neural networks. The goal is to build upon the foundational concepts of linear and logistic regression to construct more expressive, non-linear models. The key insight is that even state-of-the-art models like GPT-3 and DALL-E 2 are built from the same fundamental principles. This lecture focuses on defining the structure and forward pass of a neural network, while the next lecture will cover how to train them using backpropagation.
2. From Linear Models to Non-Linearity
The lecture begins by revisiting the limitations of the models discussed so far and motivating the need for non-linearity.

• Linear Regression Recap: The standard linear model h(x) = wᵀx + b predicts a continuous output. Its cost function is the mean squared error J(θ) = (1/n) Σ(y - h(x))². A key limitation is its inability to model non-linear relationships and the fact that its predictions are unbounded (e.g., it can predict negative house prices).
• Kernel Methods Recap: Kernel methods address non-linearity in the inputs by using a feature map φ(x), resulting in a model h(x) = θᵀφ(x). However, the model is still linear in its parameters .
• The Goal: Non-Linearity in Parameters and Inputs: The aim is to create models that are non-linear in both their parameters and inputs, allowing for much greater expressivity.

3. The Simplest Neural Network: A Single Neuron
The lecture builds the concept of a neural network from its most basic component: a single "neuron."

• The Problem with a Simple Linear Model: As identified, a linear model for house price prediction can output negative values.
• The Solution: An Activation Function: To fix this, a non-linear activation function is applied to the output of the linear model. The function introduced is the Rectified Linear Unit (ReLU):
  ReLU(z) = max(0, z)
• The "Neuron": The new hypothesis h(x) = ReLU(wᵀx + b) represents a single neuron. It takes a linear combination of the inputs and then applies a non-linear activation. This simple addition makes the model non-linear and ensures the output is always non-negative.

4. Building a Two-Layer Neural Network
The power of neural networks comes from stacking these neurons into layers, where the output of one layer becomes the input to the next.

• Example: House Price Prediction with Intermediate Features:
  • Inputs (x): [size, #bedrooms, zipcode, neighborhood_wealth] (d=4).
  • Intermediate "Hidden" Variables (a): Instead of predicting the price directly, the model first computes intermediate, meaningful features like "max family size," "walkability," or "school quality." Each of these hidden units is itself a single neuron, taking the original inputs x and applying a ReLU activation. For example:
    a₁ (family_size) = ReLU(w₁x₁ + w₂x₂ + b₁)
  • Output (y): The final prediction is then a linear combination of these learned intermediate features:
    h(x) = w₉a₁ + w₁₀a₂ + w₁₁a₃ + b₂
    (Note: By convention, the final output layer is often linear, without a ReLU).
• Fully-Connected Layer: The idea of hand-crafting which inputs go to which hidden units is generalized to a fully-connected (or dense) layer. In this architecture, every hidden unit a_j receives input from every feature x_i from the previous layer. The network's task is to learn the weights that create useful intermediate representations, rather than having them pre-specified.

5. Vectorization and Formal Notation for an R-Layer Network
To handle complex networks efficiently, the operations are expressed using matrix and vector notation (vectorization). This is not just for notational convenience; it's crucial for efficient implementation on parallel hardware like GPUs.

• A Single Layer's Computation:
  • Pre-activation (z): Compute the linear combination for all hidden units in a layer at once using a matrix-vector product: z = Wx + b.
    • W: The weight matrix for the layer, of size m_out x m_in, where m_out is the number of neurons in the current layer and m_in is the number of inputs from the previous layer.
    • b: The bias vector.
  • Activation (a): Apply the activation function (e.g., ReLU) element-wise to the pre-activation vector: a = ReLU(z).
• An R-Layer Network (Feedforward Pass): An R-layer network with R-1 hidden layers is defined by a sequence of these computations:
  • z⁽¹⁾ = W⁽¹⁾x + b⁽¹⁾, a⁽¹⁾ = ReLU(z⁽¹⁾)
  • z⁽²⁾ = W⁽²⁾a⁽¹⁾ + b⁽²⁾, a⁽²⁾ = ReLU(z⁽²⁾)
  • ...
  • h(x) = z⁽ᴿ⁾ = W⁽ᴿ⁾a⁽ᴿ⁻¹⁾ + b⁽ᴿ⁻¹⁾ (final output is linear)

6. The Importance of Non-Linearity and Connection to Kernels

• Why Activation Functions are Essential: The lecture concluded by showing what would happen if the ReLU activation were replaced with a simple identity function (g(z) = z). The entire multi-layer network would collapse into a single linear transformation: h(x) = (W₂W₁)x + (W₂b₁ + b₂) = W_tilde * x + b_tilde. Without non-linear activations, a deep network is no more expressive than a simple linear model.
• Neural Networks as Learned Feature Maps: A connection was drawn to kernel methods. The output of the penultimate layer of a neural network, a⁽ᴿ⁻¹⁾, can be viewed as a feature representation φ(x).
  • Kernel Methods: h(x) = θᵀφ(x), where φ(x) is a fixed, hand-designed feature map.
  • Neural Networks: h(x) = W⁽ᴿ⁾φ_β(x) + b⁽ᴿ⁾, where φ_β(x) is a feature map that is learned from the data (the parameters β are all the weights in the preceding layers).
  • This ability to learn the feature representation is a primary source of the power and flexibility of deep learning compared to classical methods with fixed features.

L9: Neural Networks 2, Backprop

1. Introduction: The Need for Backpropagation
The lecture, led by instructor Tony, focuses on backpropagation, arguably the most critical algorithmic component of deep learning. While modern deep learning frameworks like PyTorch and TensorFlow handle gradient computation automatically ("auto-differentiation"), understanding backpropagation is essential for grasping how neural networks are trained. The lecture aims to present a vectorized, modular view of the process, which is cleaner and more aligned with modern implementations than a fine-grained, index-heavy derivation.
2. The Core Problem: Computing the Gradient

• The Setup: We have a loss function J(θ) for a neural network, which measures the discrepancy between the model's prediction h_θ(x) and the true label y. For training, we use stochastic gradient descent (SGD), which requires computing the gradient of the loss with respect to all the model parameters θ.
• The Goal: The lecture's central aim is to explain how to efficiently compute the gradient ∇_θ J(θ) for a complex, multi-layer neural network.

3. The Power of Automatic Differentiation: A High-Level Theorem
Before diving into the mechanics, a powerful and somewhat surprising theorem is presented to frame the discussion.

• The Theorem (Informal): If a real-valued function f(x) can be computed by a differentiable circuit (a sequence of basic arithmetic operations and elementary functions like exp, log, ReLU, etc.) of size N, then its gradient ∇f(x) can also be computed by a circuit of size O(N).
• The Implication: This means that computing the gradient of a function is, in terms of computational complexity, no harder than computing the function itself. If you can evaluate the loss of your neural network in O(P) time (where P is the number of parameters), you can also compute its gradient with respect to all P parameters in O(P) time. This is a non-obvious and profound result that makes training massive neural networks feasible.

4. The Chain Rule: A Foundational Tool
The entire backpropagation algorithm is an application of the multivariate chain rule from calculus. The lecture reviews the basic form: to find the derivative of a final output J with respect to an input parameter θ_i, you sum over all intermediate variables z_k the product of (∂J/∂z_k) and (∂z_k/∂θ_i).

• Vectorized Notation: The lecture establishes a clear notation for gradients of scalars with respect to vectors and matrices. The key principle is that the gradient ∇_θ J always has the same shape as the parameter θ it is taken with respect to.

5. Backpropagation Through a Two-Layer Network: A Modular Approach
Instead of a brute-force, element-by-element derivation, the lecture presents a more elegant, modular, and vectorized approach. The neural network is viewed as a composition of simple computational blocks (e.g., matrix multiplication, element-wise activation), and "lemmas" are derived for how to backpropagate gradients through each block.

• Forward Pass Recap:
  1. z⁽¹⁾ = W⁽¹⁾x + b⁽¹⁾ (Linear layer 1)
  2. a⁽¹⁾ = ReLU(z⁽¹⁾) (Activation)
  3. z⁽²⁾ = W⁽²⁾a⁽¹⁾ + b⁽²⁾ (Linear layer 2, output h(x))
  4. J = (1/2)(y - z⁽²⁾)² (Loss computation)
• The "Lemmas" (Vectorized Chain Rules for Common Blocks):
  1. For a linear layer
     • ∇_W J = (∇_z J) uᵀ (Gradient w.r.t. weights is an outer product)
     • ∇_b J = ∇_z J (Gradient w.r.t. bias)
     • ∇_u J = Wᵀ (∇_z J) (Gradient w.r.t. input)
  2. For an element-wise activation
     • ∇_z J = (∇_a J) ⊙ σ'(z) (where ⊙ is element-wise product)
• The Backward Pass (Putting it all together): Backpropagation is the process of applying these lemmas in reverse order of the forward pass to compute the gradients.
  1. Start at the end: Compute the initial gradient ∇_{z⁽²⁾} J. Since J = (1/2)(y - z⁽²⁾)², this is simply -(y - z⁽²⁾).
  2. Backpropagate to Layer 2 parameters: Use Lemma 1 to find ∇_{W⁽²⁾} J and ∇_{b⁽²⁾} J. This requires ∇_{z⁽²⁾} J (which we just computed) and the activation a⁽¹⁾ (which was computed and stored during the forward pass).
  3. Backpropagate to Use Lemma 1 again to find ∇_{a⁽¹⁾} J = (W⁽²⁾)ᵀ (∇_{z⁽²⁾} J). This gives us the "error signal" at the output of the first hidden layer.
  4. Backpropagate through ReLU: Use Lemma 2 to find ∇_{z⁽¹⁾} J = (∇_{a⁽¹⁾} J) ⊙ ReLU'(z⁽¹⁾).
  5. Backpropagate to Layer 1 parameters: Use Lemma 1 one last time to find ∇_{W⁽¹⁾} J and ∇_{b⁽¹⁾} J using ∇_{z⁽¹⁾} J and the original input x.

6. Generalizing to Deep Networks and Computational Graphs
This modular, backward-flowing process is why the algorithm is called backpropagation.

• Deep Networks: The pattern is completely general. For an R-layer network, one starts by computing the gradient at the final output z⁽ᴿ⁾ and then recursively applies the chain rule "lemmas" backward through each layer (z⁽ᴿ⁾ -> a⁽ᴿ⁻¹⁾ -> z⁽ᴿ⁻¹⁾ -> ... -> z⁽¹⁾) to compute the gradients for all parameters.
• The Computational Graph: This process can be visualized as passing messages backward along a computational graph. The forward pass computes the values at each node. The backward pass starts with the gradient at the final node and uses the local derivative of each operation (the "backward function" for each module) to compute the gradients for its inputs. This is precisely what frameworks like PyTorch do under the hood. The key is that each module only needs to know how to compute its output and how to compute the gradient with respect to its inputs given the gradient of its output.

The lecture successfully demystified backpropagation by presenting it not as a monolithic, complex formula, but as a systematic application of the chain rule through a series of simple, reusable computational blocks.

L10: Bias - Variance, Regularization

1. Review of Backpropagation
The lecture, led by instructor Tony, began with a five-minute visual recap of backpropagation.

• Computational Graph: The forward pass of a neural network was visualized as a computational graph, where the input x flows through a series of modules (matrix multiplications, activations) to produce an output and ultimately a scalar loss J.
• The Backward Pass: Backpropagation is the process of computing gradients by flowing information backward through this graph.
  1. The process starts at the end, by computing the derivative of the loss with respect to the final output (∇_τ J).
  2. It then recursively computes the gradients with respect to the activations (a) and pre-activations (z) of each preceding layer.
  3. Each step in this backward flow (each arrow in the diagram) corresponds to applying one of the "lemmas" (vectorized chain rules) from the previous lecture.
  4. As the gradients for the activations are computed, they are used to compute the gradients for the weights (W) and biases (b) of each layer.

This modular, backward-flowing nature is the essence of backpropagation and is what enables the efficient training of deep neural networks.
2. Generalization, Training Loss, and Test Loss
The main topic of the lecture shifted from training a model to evaluating its performance, introducing the crucial concept of generalization.

• Training Loss: This is the error the model makes on the data it was trained on. All the optimization algorithms discussed so far (like SGD) are designed to minimize this training loss.
• Test Loss (Generalization Error): This is the error the model makes on new, unseen data drawn from the same underlying distribution. This is the true measure of a model's performance. In practice, it's estimated using a held-out test set.
• Generalization Gap: The difference between the test loss and the training loss. The goal of machine learning is to find a model where both the training loss and the generalization gap are small.

3. Overfitting and Underfitting
When a model's test loss is high, it typically falls into one of two failure modes:

• Underfitting: The model performs poorly on both the training and test sets. The training loss is high. This typically happens when the model is too simple to capture the underlying patterns in the data (e.g., trying to fit a complex curve with a straight line).
• Overfitting: The model performs very well on the training set (low training loss) but poorly on the test set (high test loss). This results in a large generalization gap. This typically happens when the model is too complex for the amount of data available. It memorizes the noise and spurious patterns in the training data instead of learning the true underlying signal.

4. The Bias-Variance Trade-off: A Classical View
The concepts of overfitting and underfitting are explained by the classical bias-variance trade-off. The test error of a model can be decomposed into two main components:

• Bias: Error from erroneous assumptions in the learning algorithm. High bias corresponds to underfitting. A model with high bias (like a linear model for quadratic data) is not expressive enough to capture the true function, even with infinite data.
• Variance: Error from sensitivity to small fluctuations (noise) in the training set. High variance corresponds to overfitting. A model with high variance (like a high-degree polynomial for a small dataset) is too expressive; it changes drastically with different random samples of training data, fitting the noise rather than the signal.
• The U-Shaped Curve: This trade-off is classically visualized as a U-shaped curve.
  • As model complexity (e.g., the degree of a polynomial, or the number of parameters) increases:
    • Bias decreases (the model becomes more expressive and can fit the true function better).
    • Variance increases (the model has more freedom to fit the noise in the training data).
  • The test error is the sum of these two, resulting in a U-shape. The optimal model complexity lies at the bottom of the "U," representing the sweet spot that balances underfitting and overfitting.

5. Double Descent: A Modern Phenomenon
The lecture then introduced a modern and surprising finding that challenges the classical U-shaped view of the bias-variance trade-off: double descent.

• The Observation: Empirical studies with modern deep learning models (and even linear models) have shown that as the number of parameters is increased beyond the point where the classical theory would predict massive overfitting, the test error can decrease again.
  • Classical Regime: As model complexity increases, test error follows the U-shape, peaking when the number of parameters (d) is roughly equal to the number of data points (n). This peak is where the model is just barely able to fit the training data, leading to high variance and instability.
  • Modern "Overparameterized" Regime: As d continues to increase far beyond n, the test error starts to fall again, often reaching a level lower than the best model in the classical regime.
• Data-Wise Double Descent: A similar non-monotonic pattern is observed when the model complexity is fixed, and the amount of training data (n) is varied. The test error is highest when n is close to d.

6. Explaining Double Descent
The lecture provided several intuitions for this surprising phenomenon, primarily from the study of linear models.

1. The Peak is an Algorithmic Failure: The peak in test error when n ≈ d is not a fundamental property of the problem but rather a failure of the standard learning algorithms (like unregularized gradient descent). In this "critically parameterized" region, the solution found by the algorithm has an extremely large norm (the θ vector has very large values), making it highly sensitive to noise and thus poorly generalizable.
2. The Norm as a Better Complexity Measure: This suggests that the raw number of parameters is not the best measure of a model's complexity. The norm of the parameter vector might be a better measure. The models at the peak of the curve are, in a sense, the most complex because their norms explode.
3. Implicit Regularization: In the heavily overparameterized regime (d >> n), there are infinitely many solutions that can achieve zero training error. The optimization algorithm (like SGD) doesn't just pick any solution; it has an implicit bias towards solutions with a small norm. By finding the minimum-norm solution that perfectly fits the data, the algorithm implicitly regularizes itself, leading to better generalization and the "second descent."
4. Explicit Regularization: Adding explicit regularization (a penalty on the norm of θ to the loss function) can smooth out the peak, further supporting the idea that the peak is caused by finding high-norm, poorly-generalized solutions.

This concludes the lecture, setting the stage for the next session, which will delve deeper into regularization and practical aspects of training and evaluating machine learning models.

L11: Model Selection, ML Advice

The lecture, led by instructor Tony, began by reviewing the modern phenomenon of double descent.

• Classical View: Traditionally, the test error of a model was believed to follow a U-shaped curve as model complexity increases. The sweet spot was a model complex enough to avoid underfitting but simple enough to avoid overfitting.
• Modern Phenomenon: In the "overparameterized" regime, where the number of parameters d is much larger than the number of data points n, the test error can surprisingly decrease again after an initial peak when d ≈ n.
• Explanation: This happens because when d >> n, there are infinitely many models that can achieve zero training error. The optimization algorithm (like gradient descent initialized at zero) has an implicit regularization effect, biasing it towards a specific solution—often the one with the minimum L2 norm. This minimum norm solution tends to generalize well, explaining the second descent.

2. Regularization: Controlling Model Complexity
The first major topic was regularization, a set of techniques for explicitly controlling model complexity to prevent overfitting and improve generalization.

• The Idea: Instead of just minimizing the training loss J(θ), we minimize a modified loss that includes a regularization term:
  J_reg(θ) = J(θ) + λ * R(θ)
  1. R(θ) is the regularizer, a function that penalizes model complexity.
  2. λ (lambda) is the regularization strength, a hyperparameter that controls the trade-off between fitting the data (minimizing J(θ)) and keeping the model simple (minimizing R(θ)).
• Common Regularizers:
  1. L2 Regularization (Weight Decay):
     • R(θ) = ||θ||₂²
     • This is the most common regularizer. It encourages the model parameters to be small, leading to smoother, less complex functions. In deep learning, it's almost always used, albeit often with a very small λ.
  2. L0 "Norm" (Sparsity):
     • R(θ) = ||θ||₀ (the number of non-zero parameters).
     • This encourages sparsity, meaning it pushes many parameters to be exactly zero. For linear models, this is equivalent to feature selection, as it forces the model to use only a small subset of the most important input features.
     • Problem: The L0 norm is non-differentiable and computationally hard to optimize.
  3. L1 Regularization (LASSO):
     • R(θ) = ||θ||₁ (sum of absolute values of parameters).
     • This serves as a continuous and convex surrogate for the L0 norm. It also encourages sparsity and is widely used for feature selection in linear models. The resulting model is known as LASSO (Least Absolute Shrinkage and Selection Operator).
• Choosing a Regularizer: The choice depends on prior beliefs about the problem. If you believe the solution is sparse (only a few features matter), use L1. If you believe all features contribute a little, use L2.

3. Practical Machine Learning: A Lifecycle Approach
The lecture then shifted to a more practical, applied perspective on building a real-world ML system, using a spam detector as a running example. This section was based on slides from instructor Chris Re.

• The Seven Steps of an ML Project:
  1. Acquire Data: The most critical step. Ideally, data should be sampled from the same distribution as the one the final product will run on. This is often difficult (e.g., predicting future stock prices).
  2. Look at Your Data: Before building any models, it's crucial to inspect and understand the data. This helps catch formatting errors, outliers, corruption, and provides intuition about the problem.
  3. Create Train/Dev/Test Splits:
     • Training Set: Used to train the model parameters.
     • Development (Validation) Set: Used to tune hyperparameters (e.g., learning rate, regularization strength λ, model architecture) and make modeling decisions.
     • Test Set: Held out and used only once at the very end to get an unbiased estimate of the final model's performance. Reusing the test set for tuning will cause you to overfit to it.
     • Splitting Strategy: While random splits are common in research, for real-world problems with a temporal component (like spam), it's often better to use a more recent slice of data for validation/testing (e.g., train on 2000-2015, validate on 2015-2020) to better reflect future performance.
  4. Define/Refine Specification: Clearly define the task and evaluation metrics. For spam, what is the precise definition of spam? This definition must be clear enough for human labelers to apply consistently. An inter-annotator agreement check is a good way to test the quality of the specification.
  5. Build Your Model: Start with the simplest possible model as a baseline. Don't immediately jump to complex models. Often, improving the data or the feature representation is more impactful than changing the model architecture.
  6. Measure and Analyze: Meticulously measure performance, not just on a single metric. Analyze errors to understand where the model is failing. This analysis often points back to problems in the data or the specification (Step 2 or 4).
  7. Repeat: ML development is an iterative process. The insights from analysis (Step 6) feed back into earlier stages, leading to a loop of data acquisition, model building, and evaluation.
• Distribution Shift: A major challenge in real-world ML is distribution shift, where the data distribution at test time is different from the training distribution (e.g., training a self-driving car in San Francisco and deploying it in Arizona). This is an incredibly hard open research problem with no easy solutions.

L12: K-Means, GMM (Non EM), EM

1. Introduction to Unsupervised Learning
The lecture, led by instructor Chris, transitions from supervised learning to the paradigm of unsupervised learning. This marks the beginning of a four-lecture block exploring what can be learned from data without explicit labels.

• Supervised vs. Unsupervised:
  1. Supervised: Given a dataset of inputs x and corresponding labels y, the goal is to learn a mapping h(x) → y.
  2. Unsupervised: Given only a dataset of inputs x with no labels, the goal is to discover latent or hidden structure within the data.
• Challenges of Unsupervised Learning: The instructor frames unsupervised learning as inherently "squishier" and harder than supervised learning for two main reasons:
  1. Stronger Assumptions: To find structure where none is explicitly given, we must make stronger assumptions about how the data was generated (e.g., assuming the data comes from a mixture of clusters).
  2. Weaker Guarantees: Unlike supervised learning, where we can clearly measure accuracy against ground-truth labels, the "correct" answer in unsupervised learning is often ambiguous. We aim to recover plausible structures, but there may not be a single, globally optimal solution.

2. K-Means Clustering
The lecture begins with the most classic and intuitive clustering algorithm: k-means.

• The Setup:
  • Given: A dataset of n unlabeled data points x and a hyperparameter k (the desired number of clusters).
  • Goal: To partition the n data points into k distinct clusters.
• The Algorithm (An Iterative Heuristic): K-means is an iterative algorithm that alternates between two steps:
  • Cluster Assignment Step: Assign each data point x⁽ⁱ⁾ to the cluster whose current center (μ_j) is closest. This is a "hard assignment" where each point belongs to exactly one cluster.
    c⁽ⁱ⁾ = argmin_j ||x⁽ⁱ⁾ - μ_j||²
  • Move Centroid Step: Update the location of each cluster center μ_j to be the mean of all the data points currently assigned to that cluster.
    μ_j = (1 / |S_j|) * Σ_{i in S_j} x⁽ⁱ⁾ (where S_j is the set of points in cluster j).
• Properties of K-Means:
  • Initialization: The algorithm starts by randomly initializing the k cluster centers (μ).
  • Convergence: The algorithm is guaranteed to converge (i.e., the assignments will stop changing). This is because each step monotonically decreases a "cost" function, which is the sum of squared distances from each point to its assigned center.
  • Local Minima: K-means is not guaranteed to find the global minimum of the cost function. It is a heuristic for an NP-hard problem and is sensitive to the initial random placement of the centroids. In practice, it's often run multiple times with different random initializations.
• Practical Considerations:
  • Smart Initialization (k-means++): A smarter initialization scheme that spreads the initial centers out is now the default in libraries like scikit-learn and leads to provably better solutions.
  • Choosing k: The number of clusters k is a hyperparameter that must be chosen by the user, often based on domain knowledge or by evaluating different values of k. The "correct" k can be ambiguous (e.g., a dataset could plausibly be seen as having two large clusters or four smaller ones).

3. Gaussian Mixture Models (GMMs)
The lecture then introduces a more sophisticated and probabilistic approach to clustering: Gaussian Mixture Models.

• The Problem with K-Means (Hard Assignments): K-means makes a "hard" assignment of each point to a single cluster. GMMs relax this by providing a soft assignment, representing the probability that a point belongs to each cluster.
• The Generative Model: GMMs are a latent variable model. We assume the data is generated by the following process:
  1. To generate a data point x⁽ⁱ⁾, first choose a latent cluster assignment z⁽ⁱ⁾ from a Multinomial distribution with parameters φ. (φ_j is the prior probability of a point belonging to cluster j).
  2. Once the cluster z⁽ⁱ⁾ = j is chosen, sample the data point x⁽ⁱ⁾ from the corresponding Gaussian distribution N(μ_j, Σ_j).
• The Learning Problem: We only observe the x's. The cluster assignments z are latent (hidden). The goal is to use the observed data to infer the model parameters: {φ_j, μ_j, Σ_j} for all k clusters.

4. The Expectation-Maximization (EM) Algorithm
Since we don't know the latent variables z, we cannot directly use maximum likelihood estimation. The problem is solved using the Expectation-Maximization (EM) algorithm, a powerful iterative method for finding MLE solutions in the presence of latent variables. The algorithm for GMMs mirrors the structure of k-means.

• The Algorithm:
  1. Initialize the parameters (φ, μ, Σ) randomly.
  2. Iterate:
     a. E-Step (Expectation): This is the "soft" cluster assignment step. For each data point x⁽ⁱ⁾, compute the posterior probability that it belongs to cluster j, given the current parameters. This is done using Bayes' rule:
     w_j⁽ⁱ⁾ = P(z⁽ⁱ⁾=j | x⁽ⁱ⁾; params) ∝ p(x⁽ⁱ⁾|z⁽ⁱ⁾=j) * p(z⁽ⁱ⁾=j) = N(x⁽ⁱ⁾|μ_j,Σ_j) * φ_j
     (The w's are then normalized to sum to 1).
     b. M-Step (Maximization): This is the "move centroid" step. Update the model parameters to maximize the expected log-likelihood, using the soft assignments w from the E-step as weights. The update rules are intuitive weighted averages:
     • φ_j = (1/n) * Σ_i w_j⁽ⁱ⁾ (the average "responsibility" of cluster j).
     • μ_j = (Σ_i w_j⁽ⁱ⁾x⁽ⁱ⁾) / (Σ_i w_j⁽ⁱ⁾) (the weighted mean of the data).
     • Σ_j = (the weighted covariance of the data).
• Connection to K-Means: K-means can be seen as a special "hard-assignment" version of the EM algorithm for GMMs where the Gaussians are assumed to have fixed, spherical covariance.

5. Convexity and Jensen's Inequality
The lecture concluded by introducing a key mathematical tool that will be used in the next session to formally derive and prove the convergence of the EM algorithm: Jensen's Inequality.

• Convex Sets and Functions: A brief review of convexity for sets (a set where the line segment between any two points is contained within the set) and for functions (a function where the line segment connecting two points on its graph lies above the graph).
• Jensen's Inequality: For any convex function f, the following inequality holds:
  E[f(x)] ≥ f(E[x])
  This inequality provides a way to relate the expectation of a function to the function of an expectation, and it will be the crucial building block for proving that the EM algorithm monotonically increases the data likelihood at every step.

L13: GMM (EM)

1. Introduction and Lecture Plan
The lecture, led by instructor Chris, aims to provide a more principled, mathematical foundation for the unsupervised learning algorithms introduced in the previous session, particularly Gaussian Mixture Models (GMMs). The central goal is to formally derive the Expectation-Maximization (EM) algorithm as a method for performing Maximum Likelihood Estimation (MLE) in models with latent variables.

• Recap of Latent Variable Models: The core idea from the last lecture was revisited: in unsupervised learning, we often posit the existence of a latent (or hidden) variable that explains the structure in the data. For GMMs, this latent variable z represents the cluster assignment for each data point.
• The Iterative Idea: Both k-means and GMMs follow a similar iterative two-step process:
  1. Guess the latent variables: (E.g., assign points to clusters).
  2. Update the model parameters: (E.g., re-calculate the cluster centers).
• Today's Goal: Formalize this process by showing that this iterative algorithm is, in fact, a clever way to climb the likelihood function of the observed data.

2. Technical Detour: Convexity and Jensen's Inequality
Before deriving the EM algorithm, a crucial mathematical tool was introduced: Jensen's Inequality.

• Convex Sets and Functions: The lecture reviewed the geometric definitions of convexity.
  • A convex set is one where the line segment connecting any two points in the set is also entirely within the set.
  • A convex function is one whose graph is a convex set (i.e., the region above the function's curve). Intuitively, these are "bowl-shaped" functions. A key property is that the line segment (or "chord") connecting any two points on the function's curve always lies above the curve itself.
  • Concave functions are the opposite (-f(x) is convex), and are "hill-shaped."
• Jensen's Inequality: This is the key result derived from the definition of convexity. For any convex function f:
  E[f(X)] ≥ f(E[X])
  For any concave function f (like the log function), the inequality is reversed:
  E[f(X)] ≤ f(E[X])
  This inequality provides a way to relate the expectation of a function to the function of an expectation. It will be the mathematical engine that allows the EM algorithm to work.

3. The EM Algorithm as Maximum Likelihood Estimation
With Jensen's inequality in hand, the lecture proceeded to derive the EM algorithm from first principles.

• The Challenge of Latent Variables: The goal is to maximize the log-likelihood of the observed data x, which is log p(x; θ). However, p(x; θ) involves marginalizing out the latent variable z: p(x; θ) = Σ_z p(x, z; θ). The log of a sum is difficult to optimize directly.
• Introducing a Lower Bound (The ELBO): The key trick is to introduce an arbitrary distribution Q(z) over the latent variables and use Jensen's inequality to construct a tractable lower bound on the log-likelihood. This lower bound is famously known as the Evidence Lower Bound (ELBO).
  log p(x; θ) ≥ Σ_z Q(z) * log( p(x, z; θ) / Q(z) ) = ELBO(Q, θ)
• The EM Algorithm as Coordinate Ascent: The EM algorithm can now be understood as an iterative algorithm that performs coordinate ascent on the ELBO. It alternates between maximizing the ELBO with respect to Q (the E-step) and with respect to θ (the M-step).
  1. The E-Step (Maximizing w.r.t. Q): To make the lower bound as tight as possible (i.e., equal to the true log-likelihood), we must make the term inside the expectation in Jensen's inequality a constant. This is achieved by setting the distribution Q(z) to be exactly the posterior distribution of the latent variables, p(z | x; θ). So, the E-step involves computing these posterior probabilities given the current guess for the parameters θ.
  2. The M-Step (Maximizing w.r.t. θ): With Q(z) now fixed to the posterior from the E-step, the M-step involves finding the new parameters θ that maximize the ELBO. This is a standard MLE problem, but now the log-likelihood is weighted by the posterior probabilities calculated in the E-step.
• Monotonic Improvement: This two-step process is guaranteed to monotonically increase the true log-likelihood of the observed data at every iteration, ensuring convergence to a local maximum.

4. EM for Gaussian Mixture Models (GMMs)
The lecture concluded by applying this general EM framework to the specific case of GMMs, showing that the intuitive algorithm from the previous lecture is a direct consequence of this principled derivation.

• The Model Recap:
  • Latent variable z: The cluster assignment for each point.
  • Parameters θ: {φ_j, μ_j, Σ_j} for each cluster j.
• The E-Step (in detail):
  • The goal is to compute Q(z⁽ⁱ⁾=j) = p(z⁽ⁱ⁾=j | x⁽ⁱ⁾; θ).
  • This is done using Bayes' rule, yielding the "soft assignments" or "responsibilities" w_j⁽ⁱ⁾ from the previous lecture. These are the probabilities that data point i belongs to cluster j, given the current model parameters.
• The M-Step (in detail):
  • The goal is to update the parameters (φ, μ, Σ) to maximize the ELBO, which is the expected complete-data log-likelihood.
  • Taking the derivatives of the ELBO with respect to each parameter and setting them to zero yields the same intuitive, weighted update rules seen before:
    • φ_j (cluster prior) becomes the average responsibility of cluster j.
    • μ_j (cluster mean) becomes the weighted average of the data points, where the weights are the responsibilities.
    • Σ_j (cluster covariance) becomes the weighted covariance of the data.
• Handling Constraints (Lagrange Multipliers): A brief but important note was made on how to handle the constraint that the φ_j probabilities must sum to 1. When taking the derivative, a Lagrange multiplier must be introduced to enforce this constraint, which naturally leads to the correct normalization in the M-step update.

The lecture successfully demystified the EM algorithm, framing it not as an ad-hoc heuristic but as a principled method for maximizing likelihood in the presence of unobserved data, and showed how it provides the foundation for GMMs and, as will be seen next time, other latent variable models like Factor Analysis.

L14: Factor Analysis and PCA

1. Introduction and Lecture Plan
The lecture, led by instructor Chris, continues the exploration of unsupervised learning by focusing on Factor Analysis and then introducing a classic and fundamental dimensionality reduction technique: Principal Component Analysis (PCA). The core theme is developing methods to find low-dimensional latent structures in high-dimensional data, especially in the challenging setting where the number of dimensions d is much larger than the number of data points n.
2. The Challenge: High Dimensions, Few Data Points (d >> n)
The lecture begins by motivating the need for models like Factor Analysis.

• The "d >> n" Problem: This setting is common in fields like genomics, sensor networks (e.g., thousands of sensors on campus recording data for only 30 days), and is increasingly the default in modern large-scale machine learning.
• Why Standard Methods Fail: Attempting to fit a standard multivariate Gaussian model in this setting is problematic. The empirical covariance matrix Σ is computed by summing n rank-one matrices. Since n < d, the resulting d x d covariance matrix will be rank-deficient (its rank is at most n).
• The Consequence: A rank-deficient covariance matrix is not invertible and has a determinant of zero. This breaks the Gaussian probability density function, which requires both the inverse and the determinant of Σ, making standard maximum likelihood estimation impossible.

3. Building Blocks for Factor Analysis
To address the rank-deficiency problem, two simplified covariance structures are introduced as building blocks. These models reduce the number of parameters needed to describe the covariance, ensuring it remains full-rank even with limited data.

1. Isotropic Covariance:
   • Model: Σ = σ²I (a scalar σ² times the identity matrix).
   • Geometry: Assumes the noise is spherical. The variance is the same in all directions, and the features are uncorrelated.
   • Parameters: Only one parameter (σ²) to estimate for the entire covariance structure.
2. Diagonal Covariance:
   • Model: Σ is a diagonal matrix.
   • Geometry: Assumes the noise is an axis-aligned ellipse. The features are uncorrelated, but the variance can be different along each axis.
   • Parameters: d parameters to estimate (one for each diagonal entry).

4. The Factor Analysis Model
Factor Analysis combines these ideas with a latent variable model to find a low-dimensional structure in high-dimensional data.

• The Generative Story: The model assumes that each high-dimensional data point x (in R^d) is generated by a low-dimensional latent variable z (in R^s, where s << d).
  • Sample Latent Variable: First, sample a latent variable z from a simple, standard normal distribution N(0, I).
  • Project to High Dimensions: Linearly project z into the high-dimensional space using a factor loading matrix Λ (lambda), a d x s matrix.
  • Translate: Shift the point by a global mean μ.
  • Add Noise: Add high-dimensional, diagonal Gaussian noise ε ~ N(0, Ψ), where Ψ (psi) is a d x d diagonal matrix.
  • The Full Equation: x = Λz + μ + ε
• The Resulting Distribution: This generative process implies that the observed data x is also distributed according to a multivariate Gaussian. The lecture derives the parameters of this Gaussian:
  • Mean: E[x] = μ
  • Covariance: Cov(x) = ΛΛᵀ + Ψ
• The Key Insight: This structure imposes a powerful constraint on the covariance matrix. Instead of being an arbitrary d x d matrix with ~d²/2 parameters, it is forced to be the sum of a low-rank matrix (ΛΛᵀ, with rank at most s) and a diagonal matrix (Ψ). This structure is far less complex and can be estimated even when n << d. The model finds the best low-rank approximation to the data's covariance, plus some axis-aligned noise.
• Learning with EM: The model has a latent variable z, so it is trained using the Expectation-Maximization (EM) algorithm, similar to the Gaussian Mixture Model.

5. Principal Component Analysis (PCA)
The lecture then introduced PCA, a non-probabilistic but closely related method for dimensionality reduction.

• The Goal: To find a low-dimensional linear subspace that best represents the data.
• Geometric Intuition (d=2, s=1): Given a 2D cloud of data points, PCA finds the single line (the first "principal component") that captures the maximum variance in the data. This is the direction along which the data is most "spread out."
• The PCA Optimization Problem: PCA can be formulated in two equivalent ways:
  1. Find the subspace (defined by an orthonormal basis u₁, ..., u_k) that maximizes the variance of the projected data.
  2. Find the subspace that minimizes the reconstruction error (the sum of squared distances from each data point to its projection onto the subspace).
• The Solution (Eigenvectors): The solution to this optimization problem is given by the eigenvectors of the empirical covariance matrix of the data.
  1. The first principal component (u₁) is the eigenvector corresponding to the largest eigenvalue.
  2. The second principal component (u₂) is the eigenvector corresponding to the second-largest eigenvalue, and so on.
• The Algorithm:
  1. Preprocess Data: Center the data by subtracting the mean (μ) from each point. Optionally, rescale each feature to have unit variance.
  2. Compute Covariance: Calculate the empirical covariance matrix Σ = (1/n) Σ (x⁽ⁱ⁾)(x⁽ⁱ⁾)ᵀ.
  3. Find Eigenvectors: Compute the top k eigenvectors of Σ. These vectors form the basis for the low-dimensional subspace.

PCA is a fundamental and widely used technique for data compression, visualization, and as a preprocessing step for other machine learning algorithms. It provides a deterministic, non-probabilistic counterpart to the probabilistic model of Factor Analysis.

L15: PCA/ICA

1. Introduction and Lecture Plan
The lecture, led by instructor Chris, continues the exploration of unsupervised learning by concluding the topic of Principal Component Analysis (PCA) and introducing a new, powerful technique: Independent Component Analysis (ICA). A key theme is investigating different structural assumptions that can be made about data to enable learning without labels. The lecture also briefly introduces the modern paradigm of Weak Supervision.
2. Finishing Principal Component Analysis (PCA)
The lecture began by formalizing the optimization problem at the heart of PCA.

• The Goal: To find a low-dimensional subspace that best represents a high-dimensional dataset.
• The Optimization Problem: The goal is to find an orthonormal basis u₁, ..., u_k that maximizes the variance of the projected data. Mathematically, this is expressed as:
  max_{u: ||u||=1} Σ_{i=1 to n} (x⁽ⁱ⁾ᵀu)²
• The Solution via Linear Algebra:
  1. The expression to be maximized can be rewritten as uᵀ(Σ x⁽ⁱ⁾x⁽ⁱ⁾ᵀ)u.
  2. The matrix in the middle is the empirical covariance matrix of the (centered) data.
  3. A fundamental result from linear algebra (the Rayleigh quotient) states that this expression is maximized when u is the principal eigenvector (the eigenvector corresponding to the largest eigenvalue) of the covariance matrix.
• The PCA Algorithm:
  1. Find the first principal component This is the eigenvector of the data's covariance matrix with the largest eigenvalue.
  2. Find the second principal component This is the eigenvector with the second-largest eigenvalue.
  3. ... and so on for the top k components.
• Dimensionality Reduction: To reduce the data from d dimensions to k dimensions, each data point x is mapped to a k-dimensional vector of its coordinates in the new basis: [xᵀu₁, xᵀu₂, ..., xᵀu_k].
• Choosing A common heuristic for choosing the number of components k is to look at the proportion of variance explained: (Σ_{j=1 to k} λ_j) / (Σ_{j=1 to d} λ_j). One typically chooses k to be large enough to capture a high percentage (e.g., 95% or 99%) of the total variance.

3. Independent Component Analysis (ICA)
ICA is introduced through the famous cocktail party problem.

• The Problem Setup: Imagine two people speaking simultaneously in a room with two microphones. Each microphone records a different linear combination (a mixture) of the two original speech signals. The goal is to take these two mixed recordings and separate them back into the two original, clean speech signals.
• The Mathematical Model:
  1. Let s(t) be a vector of the d unknown source signals at time t.
  2. Let x(t) be a vector of the d observed mixed signals at time t.
  3. The model assumes a linear mixing process: x(t) = A * s(t), where A is an unknown d x d mixing matrix.
• The Goal: Given only the observations x, the goal is to recover the original sources s. This seems impossible, as both A and s are unknown. If we could find A, we could recover s by computing s(t) = A⁻¹x(t). The matrix W = A⁻¹ is called the unmixing matrix.
• Inherent Ambiguities: The problem has inherent ambiguities that cannot be resolved without further assumptions:
  1. Permutation: We cannot determine the original order of the speakers. We can separate the signals but don't know which one was "speaker 1".
  2. Scaling: We cannot determine the absolute volume of the original signals. Multiplying a source s_j by a constant c and dividing the corresponding column of A by c results in the exact same observation x.
• The Key Assumption of ICA: The breakthrough of ICA is the assumption that the source signals s_j(t) are statistically independent and non-Gaussian.
  1. Why Non-Gaussian? The lecture demonstrates a crucial insight: if the source signals were assumed to be Gaussian, the problem would be unsolvable. A linear mixture of independent Gaussians is still a Gaussian, and the covariance of the resulting mixture is symmetric. This means that any rotation of the solution would be equally likely, and the original sources could not be uniquely identified.
  2. The Non-Gaussianity "Trick": By assuming the sources are non-Gaussian, we break this rotational symmetry. The algorithm can then find the unmixing matrix W that makes the recovered signals s = Wx "as independent as possible."
• The ICA Algorithm (via MLE):
  1. Model the Source Distribution: We assume a probability distribution for the sources p(s). Crucially, this must be a non-Gaussian distribution. A common choice is the derivative of the sigmoid function, p(s_j) ∝ g'(s_j) where g is the sigmoid. The independence assumption means p(s) = Π p(s_j).
  2. Derive the Likelihood of the Data: Using the change of variables formula for probability densities, we can derive the likelihood of the observed data x in terms of the unmixing matrix W.
     p(x) = |det(W)| * Π_{j=1 to d} p_s(w_jᵀx)
  3. Optimize: Find the unmixing matrix W that maximizes the log-likelihood of the observed data using gradient ascent.

The remarkable result is that this procedure works. By simply maximizing the likelihood under a non-Gaussian prior, the algorithm can successfully separate the mixed signals, a task you will implement in the homework.
4. Introduction to Weak Supervision (Data-Centric AI)
The lecture concluded with a brief, high-level introduction to a modern paradigm for dealing with the bottleneck of creating large, labeled training datasets.

• The Challenge: In many real-world applications, hand-labeling data is slow, expensive, and requires expert knowledge.
• The Idea of Weak Supervision: Instead of relying on a small set of perfect, hand-labeled data, weak supervision systems allow users to provide a large number of noisy, lower-quality signals, called labeling functions. These can be simple heuristics, rules, existing classifiers, or information from knowledge bases.
• The Generative Model: The system then learns a generative model to automatically figure out the accuracies and correlations of these noisy sources, without any ground-truth data. It then uses this model to re-weight and combine the noisy labels to produce a single, high-quality probabilistic label for each data point.
• Solving the Model: This problem can be framed as an EM-style latent variable model. However, the lecture hinted at a more modern approach where the underlying covariance structure of the noisy labels can be exploited to solve for their accuracies and correlations directly and provably, using matrix decomposition methods.
• Impact: This "programmatic" approach to creating training data is used in production at major tech companies and represents a key trend in making machine learning more practical and scalable.

L16: Self-supervised Learning

1. Review of Backpropagation (Continued)
The lecture, led by instructor Tony, began by visually summarizing the backpropagation algorithm.

• Forward Pass: The process of computing the loss for a neural network is a forward pass through a computational graph. The input x flows through layers of matrix multiplications and activations to produce an output and finally a scalar loss J.
• Backward Pass: Backpropagation is the process of computing gradients by flowing information backward through this graph. It starts with the derivative of the loss with respect to the final output (∇_τ J) and recursively uses the chain rule (encapsulated in the "lemmas" from the previous lecture) to compute the gradients for all preceding activations and weights. This backward flow is the core of how neural networks are trained efficiently.

2. Generalization and Model Complexity
The main focus of the lecture shifted to generalization—the ability of a model to perform well on new, unseen data—and its relationship to model complexity.

• Training vs. Test Loss: The distinction between training loss (error on the training set) and test loss (error on unseen data) was reiterated. The ultimate goal is to minimize the test loss.
• Overfitting vs. Underfitting: The two primary failure modes were reviewed:
  • Overfitting: Low training loss but high test loss. The model is too complex and has memorized the noise in the training data.
  • Underfitting: High training loss and high test loss. The model is too simple to capture the underlying patterns.
• Measuring Model Complexity: The idea of "model complexity" was explored. While the number of parameters is an intuitive measure, it can be misleading. A model with many small parameters might be simpler than a model with few, very large parameters. The norm of the parameter vector is often a better measure of complexity.

3. Regularization: Explicitly Controlling Complexity
Regularization refers to a set of techniques used to combat overfitting by explicitly encouraging models to have lower complexity. This is done by adding a penalty term R(θ) to the training loss.

• The Regularized Loss: J_reg(θ) = J(θ) + λ * R(θ)
  1. R(θ) is the regularizer.
  2. λ is the regularization strength, a hyperparameter controlling the trade-off.
• Common Regularizers:
  1. L2 Regularization (Weight Decay): R(θ) = ||θ||₂². This is the most common regularizer in deep learning. It penalizes large weights, encouraging smoother, less complex models.
  2. L1 Regularization (LASSO): R(θ) = ||θ||₁. This encourages sparsity by pushing many weights to be exactly zero. In linear models, this is equivalent to feature selection.
• Implicit Regularization: The lecture revisited the concept of double descent and explained that the optimization algorithm itself can have an implicit regularization effect. For example, gradient descent initialized at zero in an overparameterized linear model is biased towards finding the minimum L2 norm solution among all solutions that achieve zero training error. This implicit bias of the optimizer is a key reason why overparameterized deep learning models can generalize well without strong explicit regularization.

4. The Modern ML Pipeline: Pre-training and Adaptation
The lecture then transitioned to the dominant paradigm in modern machine learning, especially in NLP and vision: the two-stage process of pre-training and adaptation.

• The Core Idea:
  1. Pre-training: Train a very large, general-purpose model (a foundation model) on a massive, often unlabeled, dataset. The goal is not to solve a specific task but to learn a rich, transferable representation of the data (e.g., understanding the structure of language or the visual world).
  2. Adaptation: Take the pre-trained model and adapt it to a specific downstream task (e.g., sentiment analysis, image classification) which typically has a much smaller, labeled dataset.

Since pre-training is often done on unlabeled data, a "pretext" task must be created to provide a learning signal. This is known as self-supervised learning.

• Contrastive Learning (for Vision, e.g., SimCLR):
  1. Data Augmentation: Take an image and create two different random augmentations (e.g., crop, flip, color jitter). This pair is a positive pair. Pairs of augmentations from different original images are negative pairs.
  2. The Objective: Train a feature extractor network φ_θ(x) such that the representations of positive pairs are pushed closer together, while the representations of negative pairs are pushed further apart.
  3. The Loss: This is often implemented with a contrastive loss function that resembles a multi-class classification problem: for a given image, the model must identify its positive pair from a batch of negative examples.
• Language Modeling (for Text, e.g., GPT):
  1. The Task: The self-supervised task is simply predicting the next word in a sequence. The text itself provides the labels.
  2. The Model (e.g., Transformer): A large neural network (like a Transformer) is trained on a massive text corpus to model the conditional probability p(x_t | x_1, ..., x_{t-1}).
  3. The Loss: The model is trained by maximizing the log-likelihood of the text corpus (equivalent to minimizing the cross-entropy loss).

Once a model is pre-trained, it can be adapted to a new task.

• Linear Probe: The pre-trained model is used as a fixed feature extractor. Only a new, small linear classifier (the "head") is trained on top of these features using the labeled downstream data. This is computationally cheap but less powerful.
• Fine-tuning: The entire pre-trained model is initialized with its learned weights, and then all the parameters (or a subset of them) are trained (or "fine-tuned") on the labeled downstream data. This is more powerful but more computationally expensive.
• Zero-Shot Learning (for LLMs): The pre-trained language model is so powerful that it can often solve tasks without any labeled downstream examples. The task is simply described in natural language as a prompt, and the model generates the answer.
• Few-Shot In-Context Learning (for LLMs): To improve performance, a few examples of the task can be provided directly within the prompt itself. The model then "learns" the task from these in-context examples and applies the pattern to a new query, all without any gradient updates. This demonstrates the remarkable ability of foundation models to perform meta-learning.

L17: Basic concepts in RL, Value Iteration, Policy Iteration

1. Introduction to Reinforcement Learning (RL)
The lecture, led by instructor Tony, introduces the final major topic of the course: Reinforcement Learning (RL).

• Distinct Flavor: RL is presented as a distinct subfield of machine learning with a different flavor than the supervised and unsupervised paradigms studied so far. This lecture and the next will cover the foundational concepts necessary for the final homework.
• Core Task: The central task in RL is to learn to make a sequence of decisions to achieve a goal. The running example is a robot navigating a 1D grid to reach a target location.
• Key Differences from Supervised Learning:
  1. Sequential Decision-Making: RL is about making a series of decisions over time, not just a single prediction. Crucially, actions taken now affect future states and opportunities, requiring consideration of long-term consequences. A greedy approach (optimizing only for the next step's reward) is often suboptimal.
  2. No or Little Supervision: In the classic RL setting, there is no expert demonstrating the correct actions. The agent must learn through trial and error.
  3. Learning from Rewards: Instead of explicit labels, learning is guided by a scalar reward signal. The agent's goal is to discover a sequence of actions that maximizes its total accumulated reward. The human's role is to specify this reward function.
  4. Interactive Data Collection: The agent actively collects its own data by interacting with the environment. Its decisions affect the data it receives, which in turn influences its future decisions.

2. The Markov Decision Process (MDP) Framework
The problem of sequential decision-making is formalized using the Markov Decision Process (MDP) framework. An MDP is defined by five components:

1. States (S): A set of states describing the environment's configuration (e.g., the robot's position on the grid).
2. Actions (A): A set of possible actions the agent can take in each state (e.g., move left, move right).
3. Transition Probabilities (P): The dynamics of the environment. P(s' | s, a) specifies the probability of transitioning to state s' after taking action a in state s. The environment can be stochastic.
4. Reward Function (R): A function R(s) that specifies the immediate reward received for being in state s.
5. Discount Factor (γ): A value between 0 and 1 that discounts future rewards. The total payoff (or return) is the discounted sum of all future rewards: R(s₀) + γR(s₁) + γ²R(s₂) + .... The discount factor ensures this sum is finite in infinite-horizon problems and models the preference for immediate rewards over delayed ones.

• The Goal: The agent's objective is to find a policy that maximizes the expected total discounted reward.
• The Markov Property: A key assumption is that the transition probability P(s' | s, a) depends only on the current state s and action a, not on the entire history of previous states and actions.

3. Policies and Value Functions

• Policy (π): A policy is a mapping from states to actions, π(s) = a. It specifies the agent's behavior. Due to the Markov property, the optimal action only depends on the current state, so we seek a stationary policy.
• Value Function (Vπ(s)): The value function of a policy π is defined as the expected total discounted payoff an agent receives when starting in state s and following policy π thereafter.
  Vπ(s) = E[R(s₀) + γR(s₁) + ... | s₀=s, π]
  The value function measures the long-term "goodness" of a state under a specific policy.

4. The Bellman Equation
The Bellman equation is a fundamental equation in RL that provides a recursive definition for the value function. It decomposes the value of a state into the immediate reward plus the discounted value of the expected next state.

• Bellman Equation for a Policy
  Vπ(s) = R(s) + γ Σ_{s'} P(s' | s, π(s)) Vπ(s')
• Policy Evaluation: For a given policy π, this equation defines a system of |S| linear equations with |S| variables (Vπ(s) for each state s). Solving this system of equations yields the value function for that policy. This process is called policy evaluation.

5. Finding the Optimal Policy
The ultimate goal is to find the optimal policy , which is the policy that maximizes the value function for all states.

• Optimal Value Function (V* This is the maximum possible value achievable from state s: V*(s) = max_π Vπ(s).
• The Bellman Optimality Equation: The optimal value function must also satisfy a Bellman-like equation, but with a max operator over actions:
  V*(s) = R(s) + γ * max_a Σ_{s'} P(s' | s, a) V*(s')
  This equation states that the value of a state under an optimal policy is the immediate reward plus the discounted value of the best possible next state.
• The Challenge: Unlike the Bellman equation for a fixed policy, this is a system of non-linear equations due to the max operator, so it cannot be solved directly with a linear solver.

6. Value Iteration
Value iteration is a classic dynamic programming algorithm for solving the Bellman optimality equation and finding V*.

• The Algorithm:
  1. Initialize: Start with an arbitrary value function V₀(s) for all states (e.g., V₀(s) = 0).
  2. Iterate: Repeatedly update the value function using the right-hand side of the Bellman optimality equation as an update rule:
     V_{t+1}(s) ← R(s) + γ * max_a Σ_{s'} P(s' | s, a) V_t(s')
• Convergence: This iterative process is guaranteed to converge to the unique optimal value function V*. The homework will explore the proof, which relies on showing that the Bellman backup operator is a contraction mapping.
• Extracting the Policy: Once V* has been found (or approximated sufficiently well), the optimal policy π* can be extracted by acting greedily with respect to it:
  π*(s) = argmax_a Σ_{s'} P(s' | s, a) V*(s')

This lecture lays the complete groundwork for "planning" in RL, where the agent knows the model of the world (P and R) and uses dynamic programming to compute the optimal way to behave.

L18: Societal Impact of ML

1. Introduction: AI in Healthcare
The lecture, delivered by guest speaker and Stanford professor James Zou, focuses on the practical applications, challenges, and responsibilities of deploying machine learning systems in real-world healthcare settings. The talk is framed through several case studies from Professor Zou's own research.
2. Case Study 1: EchoNet - Assessing Heart Conditions

• The Problem: Cardiologists manually analyze cardiac ultrasound videos (echocardiograms) to assess heart function. This involves painstakingly finding specific frames where the heart chamber is at its largest and smallest volumes and then tracing the chamber's outline to calculate the ejection fraction—a key measure of the heart's pumping power. This process is slow, laborious, and subject to human variability.
• The ML Solution (EchoNet): An AI system was developed to automate this workflow.
  • It takes the ultrasound video as input.
  • It uses a spatio-temporal convolutional neural network (a 3D ConvNet) to process the video data.
  • One part of the network performs real-time segmentation of the heart chamber (the blue outline).
  • Another part of the network directly predicts clinically relevant phenotypes, such as the probability of heart failure and the ejection fraction for each heartbeat.
• Deployment and Robustness: The model was trained on data from Stanford Hospital and then tested at a different hospital (Cedars-Sinai in Los Angeles). It demonstrated high performance (AUC of 0.96) at the external site, showing promising robustness to shifts in data collection practices.

3. Case Study 2: TrueImage - Improving Telehealth

• The Problem: The rise of telehealth has created a new challenge: clinicians often cannot make a diagnosis because the images sent by patients are of poor clinical quality (e.g., blurry, poorly lit). This wastes time for both patients and doctors, leading to rescheduled in-person visits.
• The ML Solution (TrueImage): An algorithm designed to run on a patient's phone to provide real-time guidance for taking clinically useful photos.
  • Similar to how a mobile check deposit app guides users, TrueImage assesses the quality of a photo (e.g., of a skin lesion).
  • If the quality is poor, it provides specific, actionable feedback (e.g., "move to a brighter location," "zoom in/out").
  • The patient retakes the photo until it meets the quality standard.
• Results: In a prospective study at Stanford's dermatology clinic, TrueImage successfully filtered out ~80% of poor-quality photos and took less than a minute on average for patients to use. This demonstrates how ML can serve as an assistive tool to improve the quality of data at the point of collection.

4. The Detective Story: Why Do Dermatology AI Models Fail?
This section presents a critical investigation into why state-of-the-art dermatology AI models, which reported very high performance (e.g., AUC > 0.9) in their original papers, performed poorly (AUC ~ 0.6) when tested on real patients at Stanford. This "detective story" highlights key challenges in deploying ML in the real world.

• The Investigation: A systematic audit was conducted to explain the performance drop. The main culprits were:
  1. Label Mistakes in the Original Test Data: The "ground truth" labels in the original studies were often based on visual inspection by dermatologists, which is known to be imperfect. The Stanford evaluation used biopsy-confirmed ground truth, which is much more accurate. The original models' high performance was partly an illusion created by being evaluated against noisy labels.
  2. Distribution Shift in Diseases: The original datasets primarily contained common skin diseases. The Stanford patient population included a wider range of both common and rare diseases. The models performed significantly worse on the less common conditions they had not been sufficiently trained on.
  3. Performance Disparities (Bias): The models had substantially lower sensitivity (ability to correctly identify cancer) on images from darker-skinned patients. An investigation revealed that the original training datasets contained very few, and in some cases zero, examples from this demographic.
• The Takeaway: A model's reported performance (e.g., AUC) is nearly meaningless without a deep understanding of the data on which it was tested.

5. Lessons for Building Trustworthy AI
Based on these experiences, the lecture outlines four key lessons for improving the reliability and responsibility of AI systems, especially in high-stakes domains like healthcare.

1. Increase Data Transparency:
   • There is a critical need for transparency about the datasets used to train and evaluate models. Many medical AI models are tested on small, private datasets, making it impossible for external researchers to audit or replicate the results.
   • The speaker's group practices this by releasing large, publicly available medical datasets, such as the EchoNet dataset of over 10,000 cardiac videos.
2. Quantify Data Contributions (Data Shapley):
   • It's important to understand how individual training points contribute to a model's final performance or biases.
   • Data Shapley is a technique adapted from game theory that assigns a value to each training data point, quantifying its contribution to the model's performance on a test set.
   • This allows for identifying and up-weighting high-quality, informative data points or down-weighting noisy or harmful ones during retraining, leading to improved model robustness.
3. Understand and Explain Mistakes:
   • Analyzing why a model makes specific mistakes provides crucial insights into its blind spots.
   • The lecture presented a tool for conceptual explanation of mistakes. Instead of just saying a prediction was wrong, it provides a high-level, human-understandable reason (e.g., "The model predicted 'crocodile' instead of 'zebra' because there was too much water in the image.").
   • Applying this to the dermatology case revealed actionable insights: the model made mistakes due to dark skin tone, image blur, improper zoom, and the presence of hair.
4. Embrace Human-in-the-Loop Evaluation:
   • Standard ML development optimizes for performance on a static benchmark, which may not reflect real-world utility.
   • The ultimate goal is to optimize for the performance of the human-AI team.
   • Tools like Gradio were developed to make it easy to create simple UI wrappers around any ML model, allowing non-experts (like clinicians) to interact with, test, and provide real-time feedback throughout the development cycle. This facilitates a more collaborative and user-centered approach to building AI systems.

L19: Model-Based RL, Value Function Approximator

1. Introduction to Reinforcement Learning (RL)
The lecture, led by instructor Tony, introduces the final major topic of the course: Reinforcement Learning (RL).

• Distinct Flavor: RL is presented as a distinct subfield of machine learning with a different flavor than the supervised and unsupervised paradigms studied so far. This lecture and the next will cover the foundational concepts necessary for the final homework.
• Core Task: The central task in RL is to learn to make a sequence of decisions to achieve a goal. The running example is a robot navigating a 1D grid to reach a target location.
• Key Differences from Supervised Learning:
  1. Sequential Decision-Making: RL is about making a series of decisions over time, not just a single prediction. Crucially, actions taken now affect future states and opportunities, requiring consideration of long-term consequences. A greedy approach (optimizing only for the next step's reward) is often suboptimal.
  2. No or Little Supervision: In the classic RL setting, there is no expert demonstrating the correct actions. The agent must learn through trial and error.
  3. Learning from Rewards: Instead of explicit labels, learning is guided by a scalar reward signal. The agent's goal is to discover a sequence of actions that maximizes its total accumulated reward. The human's role is to specify this reward function.
  4. Interactive Data Collection: The agent actively collects its own data by interacting with the environment. Its decisions affect the data it receives, which in turn influences its future decisions.

2. The Markov Decision Process (MDP) Framework
The problem of sequential decision-making is formalized using the Markov Decision Process (MDP) framework. An MDP is defined by five components:

1. States (S): A set of states describing the environment's configuration (e.g., the robot's position on the grid).
2. Actions (A): A set of possible actions the agent can take in each state (e.g., move left, move right).
3. Transition Probabilities (P): The dynamics of the environment. P(s' | s, a) specifies the probability of transitioning to state s' after taking action a in state s. The environment can be stochastic.
4. Reward Function (R): A function R(s) that specifies the immediate reward received for being in state s.
5. Discount Factor (γ): A value between 0 and 1 that discounts future rewards. The total payoff (or return) is the discounted sum of all future rewards: R(s₀) + γR(s₁) + γ²R(s₂) + .... The discount factor ensures this sum is finite in infinite-horizon problems and models the preference for immediate rewards over delayed ones.

• The Goal: The agent's objective is to find a policy that maximizes the expected total discounted reward.
• The Markov Property: A key assumption is that the transition probability P(s' | s, a) depends only on the current state s and action a, not on the entire history of previous states and actions.

3. Policies and Value Functions

• Policy (π): A policy is a mapping from states to actions, π(s) = a. It specifies the agent's behavior. Due to the Markov property, the optimal action only depends on the current state, so we seek a stationary policy.
• Value Function (Vπ(s)): The value function of a policy π is defined as the expected total discounted payoff an agent receives when starting in state s and following policy π thereafter.
  Vπ(s) = E[R(s₀) + γR(s₁) + ... | s₀=s, π]
  The value function measures the long-term "goodness" of a state under a specific policy.

4. The Bellman Equation
The Bellman equation is a fundamental equation in RL that provides a recursive definition for the value function. It decomposes the value of a state into the immediate reward plus the discounted value of the expected next state.

• Bellman Equation for a Policy
  Vπ(s) = R(s) + γ Σ_{s'} P(s' | s, π(s)) Vπ(s')
• Policy Evaluation: For a given policy π, this equation defines a system of |S| linear equations with |S| variables (Vπ(s) for each state s). Solving this system of equations yields the value function for that policy. This process is called policy evaluation.

5. Finding the Optimal Policy
The ultimate goal is to find the optimal policy , which is the policy that maximizes the value function for all states.

• Optimal Value Function (V* This is the maximum possible value achievable from state s: V*(s) = max_π Vπ(s).
• The Bellman Optimality Equation: The optimal value function must also satisfy a Bellman-like equation, but with a max operator over actions:
  V*(s) = R(s) + γ * max_a Σ_{s'} P(s' | s, a) V*(s')
  This equation states that the value of a state under an optimal policy is the immediate reward plus the discounted value of the best possible next state.
• The Challenge: Unlike the Bellman equation for a fixed policy, this is a system of non-linear equations due to the max operator, so it cannot be solved directly with a linear solver.

6. Value Iteration
Value iteration is a classic dynamic programming algorithm for solving the Bellman optimality equation and finding V*.

• The Algorithm:
  1. Initialize: Start with an arbitrary value function V₀(s) for all states (e.g., V₀(s) = 0).
  2. Iterate: Repeatedly update the value function using the right-hand side of the Bellman optimality equation as an update rule:
     V_{t+1}(s) ← R(s) + γ * max_a Σ_{s'} P(s' | s, a) V_t(s')
• Convergence: This iterative process is guaranteed to converge to the unique optimal value function V*. The homework will explore the proof, which relies on showing that the Bellman backup operator is a contraction mapping.
• Extracting the Policy: Once V* has been found (or approximated sufficiently well), the optimal policy π* can be extracted by acting greedily with respect to it:
  π*(s) = argmax_a Σ_{s'} P(s' | s, a) V*(s')

This lecture lays the complete groundwork for "planning" in RL, where the agent knows the model of the world (P and R) and uses dynamic programming to compute the optimal way to behave.