Introduction

• Lecture: S0-Intro
• Version: current
• Notes to Read: Numpy Tutorial
• Video: M2 / M3

Lecture 1 Study Guide

Course Logistics and Overview

Course Staff and Communication

• Instructor: Prof. Yanjun Qi (Pronounced: /ch ee/)
• Communication: Email and Slack (details on Course overview)
• TA and Office Hours: Information available on the Course Website

Course Materials

• Textbook: None required; multiple reference books shared via Course Website
• Official Content: Anything not mentioned in Prof. Qi’s slides is not an official topic
• Resources:
  • All slides, videos, readings, and homework on Course Website
  • Assignments/Project: UVA CourseSite
  • Quizzes: Google Forms

Background Needed

• Required:
  • Calculus
  • Basic linear algebra
  • Basic probability
  • Basic Algorithm
• Recommended: Statistics
• Programming: Python (required for all assignments)

Assessment Breakdown

• Weekly Quizzes: 20% (top 10 scores count, 14 total, 10 minutes each, closed book via Google Form)
• Homework Assignments: 65% (HW1-HW5, 10% each)
• Final Project: 10% (apply ML to real-world problems)
• Weekly Reading Question Submissions: 5%
• Final Exam: 15% (December 9th)
• See CourseWeb for detailed policy

Course Format (2025F Flipped Classroom - Starting Week 3)

In-Class Activities

• Pre-class question submission
• Quizzes
• Quiz review
• Assignment review
• In-class solution examples
• Short presentations/code demos

Emphasis

• Active learning
• Understanding core ML concepts
• Applying models (Python, scikit-learn, Keras)
• Analyzing performance and ethics
• Becoming an ML tool builder

Key Objectives

• Learn fundamental principles, algorithm design, methods, and applications
• Build simple machine learning tools from scratch (not just tool users)
• Understand complex machine learning methods at the source code level

Machine Learning History and Concepts

Artificial Intelligence (AI)

• Definition: The study of computer systems that attempt to model and apply the intelligence of the human mind
• Attributes of Intelligence (for machines):
  • Perceive
  • Understand
  • Interact
  • Think/Reason/Learn
  • Imagine/Make analogy
• Impact: Economic, cultural, social, health disruptions; potential for job automation; existential threat concerns

History of AI/ML (Timeline)

• 1950: Alan Turing’s “Computing Machinery and Intelligence” (“Can machines think?”)
• 1956: Dartmouth workshop, John McCarthy coins “artificial intelligence”
• 1950s-60s: Enthusiasm, early Neural Networks (NNs) popular
• 70s-80s: Rule-based/Knowledge-based systems, Expert systems
• 1959: Arthur Samuel popularizes “machine learning” (Samuel Checkers-playing Program)
• 90s: Classic ML (SVM, RF, BN), Convolutional Neural Networks (CNNs) and Recurrent Neural Networks (RNNs) invented
• 2000s: ImageNet, Deep Learning breakthroughs
• 2010s: Deep Learning breakthroughs continue (2015-2016 CNN/RNN invented, 2017 Deep Learning, Deep Reinforcement Learning, GANs)
• 2023-Now: ChatGPT / Generative AI / Agentic AI

Reasons for 2010s Deep Learning Breakthroughs

1. Plenty of good quality (labeled) data (text, visual, audio, user activity, knowledge graphs, genomics, medical imaging)
2. Advanced computer architecture that fits Deep Learning (e.g., GPUs for faster, more accurate results)
3. Powerful, well-engineered machine learning libraries (easy to learn, use, extend)

Recent Advances (2023-Now) on Generative AI

• Definition: AI systems that create content (text, images, audio, video, code), powered by foundation models (transformers, diffusion, LLMs). Distinct from discriminative AI
• Key Applications:
  • LLMs (text/chat)
  • Diffusion models (images)
  • Gen-2/Sora (video)
  • GitHub Copilot (code)
  • Multi-modal models
• Enabling Factors: Scaling law, data, advanced architecture, powerful libraries

Machine Learning Basics

Goal

Build computer systems that learn and adapt from “experience” (data examples)

Traditional Programming vs. Machine Learning

• Traditional: Computer + Data + Program → Output
• ML (Training Phase): Computer + Input Data (X) + Output (Y) → Program/Model f()

Common Notations

• Inputs (X):
  • Matrix (bold capital)
  • p variables, n observations
  • Xⱼ is jth element
  • Xⱼ,ᵢ is ith observed value
  • Vectors are column vectors
• Outputs:
  • Quantitative (Y)
  • Qualitative/Categorical (C)
• Observed Variables: Lowercase

Supervised Learning

Find a function f() to map input space X to output space Y such that the difference between true y and f(x) is small

Example: Linear Binary Classifier

f(x,w,b) = sign(wᵀx + b)

• wᵀx + b > 0 (e.g., +1 point)
• wᵀx + b < 0 (e.g., -1 point)

Training

Learning parameters w, b by minimizing a loss/cost function L() on the training set (available x and y pairs)

Testing

Evaluating performance on “future” (unseen) points by comparing true y to predicted f(x). Key: testing examples are not in the training set

Basic Concepts

• Loss Function: Measures difference between y and f(x) (e.g., hinge loss for binary classification)
• Regularization: Additional information added to the loss function to control f
• Generalization: The ability to learn a function from past data to “explain,” “predict,” “model,” or “control” new, unseen data examples (inductive reasoning)

Two Modes of ML

1. Training: Input-output pairs (X, Y) are fed into a model to learn f()
2. Testing/Production: Unseen input X’ is fed into the learned model f() to produce f(X’) (predicted output)

Three Aimed Features of ML Models

1. Robustness
2. Computation
3. Prediction

General Lessons for Excellence

• Good breadth in fundamentals is key
• Strength in particular targeted topics helps stand out

Recommended Extra-Curriculum Books

1. Master Algorithm by Pedro Domingos (explores different “tribes” of ML: Symbolists, Connectionists, Evolutionists, Bayesians, Analogizers)
2. Homo Deus: A Brief History of Tomorrow by Yuval Noah Harari

Quiz: UVA CS 4774: Machine Learning - Introduction

Instructions: Answer each question in 2-3 sentences.

1. What is the main distinction between “Traditional Programming” and the “Machine Learning (training phase)” as illustrated in the lecture?
2. Name three specific reasons cited in the lecture for the significant breakthroughs in Deep Learning during the 2010s.
3. Define “Generative AI” and explain how it differs from “discriminative AI” as presented in the source material.
4. In the context of supervised learning, what is the purpose of the “training phase” for a linear binary classifier, and what is being minimized?
5. What is the concept of “generalization” in machine learning, and why is it crucial for model performance?

Quiz Answer Key

1. Machine Learning Goal
   The primary goal of machine learning is to build computer systems that can learn and adapt from their “experience.” In this context, “experience” refers to the available data examples, also known as instances or samples, which are described with various properties.

2. Traditional vs ML Programming
   Traditional Programming involves a computer executing a pre-defined program on data to produce an output. In contrast, the Machine Learning training phase takes input data (X) and corresponding outputs (Y) to learn or create the program/model f().

3. Deep Learning Breakthroughs
   The significant breakthroughs in Deep Learning during the 2010s were primarily due to the availability of plenty of good quality labeled data, advanced computer architectures suitable for Deep Learning (like GPUs), and powerful, well-engineered machine learning libraries.

4. Generative AI
   Generative AI refers to AI systems that are capable of creating new content, such as text, images, or code, powered by foundation models. This differs from discriminative AI, which primarily focuses on tasks like classification rather than content generation.

5. Training Phase Purpose
   In supervised learning, the training phase for a linear binary classifier aims to learn the parameters w and b. This is achieved by minimizing a loss or cost function L(), which quantifies the difference between the true output y and the model’s prediction f(x) on the available training examples.

6. Generalization
   Generalization in machine learning is the ability of a model to apply the knowledge learned from past, observed data to effectively “explain,” “predict,” or “model” new, unseen data examples. It is crucial because it indicates whether the model has truly learned the underlying patterns rather than just memorizing the training data.

Algebra Review

• Lecture: S0-AlgbReview
• Version: current
• More advanced to Read: S0-linalg-extra.pdf
• Notes to Read: Khanacademy Math + CMU study note
• Video: Python Data Science Code tutorials

Comprehensive Linear Algebra and Matrix Calculus Review

Study Guide

This study guide is designed to reinforce your understanding of fundamental concepts in linear algebra and matrix calculus, as presented in the source material. Mastering these topics is crucial for advanced studies in machine learning and related fields.

I. Fundamental Definitions

• Scalar: Understand what a scalar is and how it’s denoted.
• Vector: Define a vector, differentiate between row and column vectors, and understand its representation in real space (R^n).
• Matrix: Define a matrix, understand its dimensions (m-by-n), how its entries are denoted, and the concept of a square matrix.

II. Special Matrices

• Identity Matrix (I): Understand its structure and significance.
• Diagonal Matrix: Recognize its form.
• Upper/Lower Triangular Matrices: Identify these structures.
• Symmetric Matrix: Understand the property that defines a symmetric matrix.
• Orthogonal Matrix: Define an orthogonal matrix and its key property related to its inverse.

III. Matrix Operations

Transposition

• Concept: “Flipping” rows and columns.
• Notation: A^T.
• Application: Understand how to transpose a given matrix.

Addition and Subtraction

• Condition: Matrices must be of the same size.
• Process: Entry-wise operation.
• Examples: Be able to perform addition and subtraction.

Multiplication

• Notation: AB (pre-multiplying B by A, post-multiplying A by B).
• Conformability: Understand the condition for multiplication (number of columns in premultiplier must equal number of rows in postmultiplier).
• Dimensions: Predict the dimensions of the resulting matrix (m × n * n × p = m × p).
• Non-Commutativity: Recognize that AB ≠ BA, generally.
• Associativity: Understand A(BC) = (AB)C.
• Properties: (AB)^T = B^T A^T; multiplication with Identity Matrix.

Special Uses

• Scalar & Matrix Product: Understand bA = Ab.
• Dot (Inner) Product of Vectors: a^T b (result is a scalar).
• Outer Product of Vectors: ab^T (result is a matrix).
• Sum of Squared Elements of a Vector: a^T a (useful for L2 norm).

Norm (of Vector)

• Concept: Measure of “length” of a vector.
• Common Norms: L1, L2 (Euclidean), L∞.

• L2 Norm (Euclidean):

  x

  = √(x^T x).

• General Definition: Understand the properties a function must satisfy to be a norm.

Matrix Inversion

• Notation: A^(-1) or inv A.
• Definition: AA^(-1) = I = A^(-1)A.
• Nonsingular vs. Singular: Differentiate between matrices that have an inverse and those that don’t.

• Determinant Condition: An inverse exists if and only if

  A

  ≠ 0.

• Properties: (AB)^(-1) = B^(-1)A^(-1); (A^T)^(-1) = (A^(-1))^T; (A^(-1))^(-1) = A.
• Special Cases: Inverse of diagonal matrices, orthogonal matrices (A^(-1) = A^T).
• Pseudo-inverse (Extra): Basic understanding of its existence for non-square matrices.

Matrix Rank

• Linear Independence: Define linearly independent vectors.
• Definition of Rank: Maximal number of linearly independent columns (or rows).
• Properties: rank(A) ≤ min(m,n). Full row rank, full column rank.
• Determinant Connection: Rank is the dimension of the largest square sub-matrix with a non-zero determinant.
• Relationship to Singular Matrices: How rank relates to singularity.
• Rank of Product: rank(AB) ≤ min(rank(A), rank(B)).

Matrix Calculus

• Review of Derivatives: Understand the basic definition of a derivative for single-variable functions.
• Multivariate Calculus Concepts:
  • Partial Derivative: Extension of derivative to functions of multiple variables.
  • Gradient: Vector of partial derivatives (first derivative to gradient).
  • Hessian Matrix: Matrix of second partial derivatives (second derivative to Hessian).
  • Denominator Layout: Understand that the gradient’s size is the same as the variable’s size.
  • Examples: Be able to calculate simple gradients.

IV. Additional Concepts (Mentioned as Extra or for Future Reference)

• Trace(): Sum of diagonal elements (not detailed in this source, but mentioned as “must know”).
• Eigenvalue / Eigenvectors: Important for future topics.
• Positive Definite Matrix, Gram Matrix, Quadratic Form, Projection: Future topics.
• Khan Academy: A recommended resource for review.
• Linear Transformation and Determinant: Connection to matrix determinant and Jacobian determinant.
• Laplacian of a function: Trace of the Hessian.
• Harmonic function: Function whose Laplacian is 0.

Quiz: Short-Answer Questions

1. What is the primary difference between a scalar and a vector in linear algebra notation?
2. Define a “column vector” and provide an example of a vector in R^4.
3. Explain the condition for two matrices to be “conformable” for multiplication. Why is this condition important?
4. Given matrices A (3×2) and B (2×4), what are the dimensions of the resulting matrix C = AB? What about C = BA?
5. State two key properties of matrix multiplication that distinguish it from scalar multiplication.
6. Describe the concept of a “norm” of a vector. What does the L2 norm represent?
7. What is the definition of the inverse of a matrix A (denoted A^(-1))? Under what crucial condition does a matrix inverse exist?
8. Differentiate between a “nonsingular” and a “singular” matrix.
9. Explain the concept of “linear independence” in the context of vectors. How does this relate to the rank of a matrix?
10. What is the gradient of a multivariate function? How does it relate to partial derivatives?

Quiz Answer Key

1. Scalar vs. Vector: A scalar is a single number (e.g., 1 or 22), denoted with regular type. A vector is a single row or column of numbers (e.g., [1 2 3]), denoted with bold small letters.

2. Column Vector and R^4 Example: A column vector is a vector arranged vertically. An example of a vector in R^4 (a column vector) is v = (1,6,3,4)^T.

3. Conformable Matrices: For two matrices A and B to be conformable for multiplication (AB), the number of columns in the premultiplier (A) must equal the number of rows in the postmultiplier (B). This ensures that the dot product for each entry in the resulting matrix can be calculated.

4. Matrix Multiplication Dimensions: If A is (3×2) and B is (2×4), then C = AB will have dimensions (3×4). C = BA cannot be performed because the number of columns in B (4) does not equal the number of rows in A (3).

5. Properties of Matrix Multiplication:
   • Matrix multiplication is generally not commutative (AB ≠ BA).
   • Matrices must be conformable for multiplication to occur.

6. Vector Norm: A norm of a vector

   x

   is a measure of its “length.” The L2 norm, also known as the Euclidean norm, represents the straight-line distance from the origin to the vector’s endpoint (calculated as the square root of the sum of the squared elements).

7. Matrix Inverse Definition and Condition: The inverse of an n × n matrix A is the matrix A^(-1) such that AA^(-1) = I = A^(-1)A, where I is the identity matrix. A crucial condition for an inverse to exist is that the determinant of A (

   A

   ) must not be zero.

8. Nonsingular vs. Singular Matrix: A “nonsingular” matrix is an n × n matrix that has an inverse. A “singular” matrix is an n × n matrix that does not have an inverse.

9. Linear Independence and Rank: A set of vectors is linearly independent if none of them can be written as a linear combination of the others. The rank of a matrix is defined as the maximal number of linearly independent columns (or rows) in that matrix.

10. Gradient of a Multivariate Function: The gradient of a multivariate function is a vector containing its partial derivatives with respect to each variable. It extends the concept of a derivative to functions of multiple variables, indicating the direction of the steepest ascent of the function.

Section 1 - Basics Supervised & On Tabular Input Type

Scikit-learn

• Lecture: S0-scikit-learn-self-study
• Version: current
• Notes to Read: basic tutorial + scikit-learn code examples
• Video: How install

Machine Learning in a Nutshell

• Lecture: S1-nutshell
• Version: current
• Notes to Read: two modes running example
• Video: M1 / M2 / M3

Machine Learning in a Nutshell: Comprehensive Study Guide

I. Core Concepts of Machine Learning

A. Definition and Goal

• Machine Learning (ML): A field of artificial intelligence where systems learn from data to optimize a performance criterion, aiming to generalize to unseen data.
• Goal: To enable computers to learn from example data or past experience without being explicitly programmed, and then apply this learned knowledge to make predictions or decisions on new, unseen data.

B. The Machine Learning Pipeline (Nutshell Components)

• Data: The raw material for learning, consisting of examples/instances/samples, each with features/attributes and potentially a target/label.
• Task: The specific problem ML aims to solve (e.g., classification, regression, clustering).
• Representation: The way data and the learning function are structured (e.g., linear function, neural network).
• Score Function (Loss/Cost Function): A metric used to evaluate how well the model’s predictions align with the actual values. The goal is often to minimize this function.
• Search/Optimization: The algorithms used to find the best model parameters by minimizing the score function (e.g., gradient descent).

Models, Parameters, Hyperparameters, Metrics

• Models: The learned functions or structures.
• Parameters: Internal variables of the model learned from data (e.g., w, b in a linear classifier).
• Hyperparameters: Parameters whose values are set before the learning process begins (e.g., learning rate, regularization strength).
• Metrics: Measures used to evaluate model performance (e.g., accuracy, precision, recall, MSE).

C. Two Phases of Machine Learning

Training (Learning Parameters)

• Uses a training set of input-output pairs (X, Y).
• The objective is to find model parameters (e.g., w, b) that minimize the loss/cost function, representing the difference between predicted f(x) and true y on the training examples.

Testing / Deployment / Inference (Evaluating Performance)

• Uses a testing set of examples (x?) that were not included in the training set.
• Evaluates the model’s performance by measuring the difference between true y? and predicted f(x?).
• Crucial for assessing the model’s ability to generalize to new data.

D. When to Use Machine Learning

• Extracting knowledge from data: Discovering hidden relationships and correlations in large datasets.
• Learning tasks difficult to formalize: Problems hard to define explicitly with rules (e.g., face recognition).
• Creating software that improves over time: Systems that can adapt to new knowledge and data without continuous manual redesign.

II. Data Types in Machine Learning

A. General Terminology

• Data/points/instances/examples/samples/records: Rows in a dataset.
• Features/attributes/dimensions/independent variables/covariates/predictors/regressors: Columns in a dataset (excluding the target).
• Target/outcome/response/label/dependent variable: The special column to be predicted.

B. Main Types of Columns

• Continuous: Real numbers (e.g., weight, temperature).
• Discrete: Symbols or categories (e.g., “Good”, “Bad”, “Cat”, “Dog”).

C. Examples of Data Types

• Tabular Data: Structured data in rows and columns (e.g., patient records with gene quantities).
• 1D Sequence Data: Data with a sequential order (e.g., language text, genome sequences, audio).
• 2D Grid Data: Data arranged in a grid (e.g., images).
• Graph Data: Data representing relationships between entities (e.g., social networks).

III. Machine Learning Tasks

A. Supervised Learning

Definition: Learning from labeled input-output pairs (X, Y). The goal is to predict Y for unseen X.

Classification: Predicting a discrete target variable (Y)

• Binary Classification: Two possible output classes (e.g., positive/negative review, disease present/absent).
• Multi-class Classification: More than two possible output classes (e.g., categorizing text into Sports, Business, Education).
• Multi-label Classification: Assigning a set of target labels to a single input (e.g., an image being tagged with “Castle” and “Mountains”).
• Hierarchical Classification: Classification where classes are organized in a hierarchy.

Regression: Predicting a continuous target variable (Y)

Generating: Creating new data instances based on learned patterns (e.g., Text2Image, Edges2Image)

B. Unsupervised Learning

• Definition: Learning from unlabeled data (no Y provided).
• Goal: Finding patterns, structures, or relationships within the data.
• Example: Clustering – grouping instances into “natural” clusters.

C. Structured Output Learning

• Definition: Prediction tasks where output labels have complex structured correlations or constraints (e.g., spatial, temporal, relational dependencies).
• Example: Language parsing (predicting a parse tree), sequence labeling (predicting a sequence of labels for a sequence of inputs).

D. Reinforcement Learning (RL)

• Definition: An agent interacts with an environment and learns to maximize a scalar reward signal.
• Key Characteristics: Not independent and identically distributed (IID) data, sequential decision-making.
• Variations: Basic RL (no labels/supervision), imitation learning (supervised).

IV. Representation Types

A. Concept of Representation

How the input data (X) and the function (f) mapping X to Y are structured.

B. Examples of Representations

• Linear functions: f(x,w,b) = sign(w^T x + b) for binary classification.
• Nonlinear functions: Polynomial expansion, logistic function, trees, multi-layer networks (neural networks).
• Prob-density family: Bernoulli, multinomial, Gaussian, mixture of Gaussians.
• Vector Space Representation: Representing text as vectors (e.g., Bag of Words).
• Representation Learning (Deep Learning/Feature Learning): Automatically learning useful features from raw data, often through multi-layer architectures. This replaces traditional, time-consuming “Feature Engineering.”

V. Loss/Cost Types

A. Purpose of Loss Functions

• Quantify the difference between the model’s prediction and the true target value.
• Minimizing the loss function guides the learning process.

B. Examples of Loss Functions

• Mean Squared Error (MSE): Common for regression tasks.
• Hinge Loss: Used in binary classification (e.g., Support Vector Machines).
• Log-likelihood / Cross-entropy: Common for classification tasks, especially with probabilistic models.
• 0-1 Loss: Simple loss for classification, counts misclassifications.
• Regularized loss functions (L1, L2): Add penalty terms to the loss function to control model complexity and prevent overfitting.

VI. Optimization and Model Properties

A. Search/Optimization Algorithms

Purpose: To find the optimal model parameters by minimizing the loss/cost function.

Examples:

• Gradient Descent (GD): An iterative first-order optimization algorithm that takes steps proportional to the negative of the gradient.
• Stochastic Gradient Descent (SGD): A variant of GD that updates parameters using a single training example or a small batch at a time.
• Newton’s Method: A second-order optimization algorithm.
• Linear Programming, Quadratic Programming: For specific types of optimization problems.
• EM (Expectation-Maximization): For models with latent variables.
• Backpropagation: Used to train neural networks by efficiently computing gradients.

B. Model Properties / Basic Concepts

• Generalization: The ability of a model to perform well on unseen data. This is the ultimate goal of ML.
• Overfitting: When a model learns the training data too well, including noise, leading to poor performance on new data.
• Underfitting: When a model is too simple to capture the underlying patterns in the data, leading to poor performance on both training and test data.
• Bias-Variance Tradeoff: A fundamental concept balancing model simplicity (high bias, low variance) and complexity (low bias, high variance).
  • Big gap between train/validation loss suggests overfitting (high variance).
  • No gap, both bad, suggests underfitting (high bias).
• Regularization: Techniques (e.g., L1, L2) that add a penalty to the loss function to discourage overly complex models and prevent overfitting.

VII. Evaluation and Advanced Considerations

A. Measuring Prediction Accuracy

• Evaluate models on test data using appropriate metrics.
• For supervised classification, common metrics include accuracy, precision, recall, F1-score.

B. Human-Centric ML/AI Research

• Trustworthy ML: Ensuring models are reliable and fair.
• Explainable ML: Understanding why a model makes certain predictions.
• Robustness: How well a model performs under adversarial conditions (e.g., adversarial examples).
• Interacting with/Understanding/Modeling Human Intent: Developing AI that better collaborates with humans.

Quiz: Machine Learning Fundamentals

Instructions: Answer each question in 2-3 sentences.

1. What is the primary goal of machine learning, and how does it differ from traditional programming?
2. Explain the concept of “generalization” in machine learning. Why is it important, and what happens if a model fails to generalize?
3. Describe the two main phases of a machine learning process. What is the key difference in the data used during these phases?
4. Define a “loss function” and explain its role in training a machine learning model.
5. What is the difference between “parameters” and “hyperparameters” in a machine learning model? Provide a brief example for each.
6. List three types of data commonly encountered in machine learning. Give a real-world example for each.
7. Distinguish between supervised and unsupervised learning tasks. Provide a task example for each.
8. Briefly explain what “representation learning” is and why it has become more prominent compared to traditional “feature engineering.”
9. What is the “bias-variance tradeoff”? How might you diagnose a model that is suffering from high variance?
10. Describe the purpose of “regularization” in machine learning. How does it help in model training?

Answer Key

1. Primary Goal of ML: The primary goal of ML is to optimize a performance criterion using example data or past experience, aiming to generalize to unseen data. It differs from traditional programming where rules are explicitly coded; instead, ML systems learn patterns from data to make predictions or decisions.

2. Generalization Concept: Generalization refers to a model’s ability to perform accurately on new, unseen data, not just the data it was trained on. It is crucial because the ultimate purpose of an ML model is to make predictions in real-world scenarios. A model that fails to generalize is said to be overfitting, meaning it has learned the training data too specifically, including noise, and will perform poorly on new examples.

3. Two Main Phases: The two main phases are training and testing/deployment. During training, the model learns parameters from a labeled “training set.” During testing, the model’s performance is evaluated on a separate “testing set” of examples that were not part of the training data.

4. Loss Function: A loss function quantifies the discrepancy between a model’s predicted output and the actual true output for a given example. Its role in training is to provide a metric that the optimization algorithm (e.g., gradient descent) attempts to minimize, thereby iteratively adjusting the model’s parameters to improve its accuracy.

5. Parameters vs Hyperparameters: Parameters are internal variables of the model learned from the data during training, like the weights (w) and bias (b) in a linear classifier. Hyperparameters are external configurations set before the training process begins, such as the learning rate in gradient descent or the regularization strength.

6. Three Data Types: Three common data types are tabular, 2D grid, and 1D sequence data. Tabular data can be patient records with various medical attributes. 2D grid data commonly refers to images, like photographs for object recognition. 1D sequence data includes text documents for sentiment analysis or genome sequences.

7. Supervised vs Unsupervised: Supervised learning involves learning from labeled input-output pairs (X, Y) to predict Y for new X; an example is classifying emails as spam or not spam. Unsupervised learning, conversely, deals with unlabeled data to find patterns or structures within it; an example is clustering customer data to identify distinct market segments.

8. Representation Learning: Representation learning is the process where a machine learning model automatically discovers the representations (features) needed for detection or classification from raw data. It has become prominent because it often yields more effective features and reduces the laborious, time-consuming, and often task-dependent manual effort required in traditional “feature engineering.”

9. Bias-Variance Tradeoff: The bias-variance tradeoff refers to the dilemma of simultaneously minimizing two sources of error that prevent models from generalizing well: bias (error from overly simplistic assumptions) and variance (error from sensitivity to small fluctuations in the training data). High variance (overfitting) can be diagnosed by observing a large gap between the model’s performance on the training data (very good) and its performance on validation or test data (significantly worse).

10. Regularization Purpose: Regularization is a technique used to prevent overfitting by adding a penalty term to the loss function during training. This penalty discourages the model from becoming too complex or assigning excessively large weights to features. By controlling model complexity, regularization helps the model generalize better to unseen data.

Linear Regression

• Lecture: S1-LinearReg
• Version: current
• Notes to Read: linear regression coderun
• Video: M1 / M2 / M3 / M4

• Notebook Resources: notebook/L3_plot_ols.ipynb

Understanding Linear Regression: A Study Guide

Quiz

Instructions: Answer the following questions in 2-3 sentences each.

1. What is the primary goal of Machine Learning in a nutshell, as described in the lecture?
2. Define “regression” in the context of machine learning, specifically mentioning the nature of the target variable.
3. Explain the purpose of the “score function” (or loss/cost function) in linear regression.
4. Describe what the training dataset consists of for supervised regression.
5. In the linear regression equation f(x) = wx + b, what do w and b represent?
6. How does the concise notation ŷ = f(x) = x^T θ = θ^T x simplify the representation of linear regression with multiple features?
7. What is the “Sum of Squared Error” (SSE) and why is it used as a loss function in linear regression?
8. Briefly explain the concept of “Normal Equations” in the context of finding optimal regression coefficients.
9. Why is it important for a learned model to “Generalize Well” to unseen data?
10. What are the three main aims for a learned model besides generalizing well, as discussed in the lecture?

Answer Key

1. Primary Goal of Machine Learning: The primary goal of Machine Learning is to optimize a performance criterion using example data or past experience. The ultimate aim is to generalize this learned knowledge effectively to unseen data.

2. Regression Definition: In machine learning, regression refers to tasks where the target variable (Y) is continuous. This means the model predicts a numerical value rather than a category or class.

3. Score Function Purpose: The score function (or loss/cost function), denoted as L(), quantifies the difference between the model’s predictions and the actual target values. The goal of the learning algorithm is to minimize this function, thereby finding the optimal model parameters.

4. Training Dataset: The training dataset for supervised regression consists of input-output pairs. These pairs include available examples (input features, X) and their corresponding continuous target labels (output, Y), which the model uses to learn.

5. Linear Regression Parameters: In the linear regression equation f(x) = wx + b (for a single variable), w represents the weight or slope, indicating how much Y changes for a unit change in X. b represents the bias or intercept, which is the value of Y when X is zero.

6. Concise Notation: The concise notation ŷ = f(x) = x^T θ = θ^T x uses vector/matrix products to represent multiple features and their corresponding weights in a single expression. This compact form simplifies mathematical derivations and computational implementation for multivariate linear regression.

7. Sum of Squared Error (SSE): The Sum of Squared Error (SSE) measures the sum of the squared differences between the predicted values (f(x)) and the actual target values (y). Squaring the errors ensures that all errors contribute positively to the total loss and penalizes larger errors more heavily, providing a clear objective for minimization.

8. Normal Equations: The Normal Equations provide a closed-form solution to find the optimal regression coefficients (θ) by setting the derivative (gradient) of the cost function with respect to θ to zero. This method directly calculates the θ that minimizes the SSE for linear regression.

9. Generalization: Generalizing well means that the model performs accurately not only on the data it was trained on but also on new, unseen data. This indicates that the model has learned underlying patterns rather than just memorizing the training examples, making it useful in real-world applications.

10. Additional Model Aims: Besides generalizing well, the lecture suggests that a learned model should also be computationally scalable and efficient, and robust, trustworthy, and interpretable. These attributes contribute to the practical utility and reliability of machine learning models.

Linear Regression Basics

1. Machine Learning in a Nutshell

Definition: Machine Learning (ML) is a field that grew out of Artificial Intelligence (AI). Its core purpose is to “Optimize a performance criterion using example data or past experience, aiming to generalize to unseen data.”

Key Components of ML: The process of machine learning can be broken down into several fundamental elements:

• Task: What needs to be predicted or achieved (e.g., y in regression).
• Representation: How the data and model are structured (e.g., x, f()).
• Score Function: A measure of how well the model is performing (e.g., L()).
• Search/Optimization: The method used to find the best model parameters (e.g., argmin()).
• Models, Parameters: The specific mathematical structure and adjustable values of the model (e.g., w, b for regression coefficients).
• Data: The input used for training and testing (e.g., X: Tabular).

2. Regression Fundamentals

Definition: Regression specifically deals with predicting a continuous target variable y.

Linear Regression: In linear regression, the target Y is modeled as a “Weighted linear sum of Xs.”

• For a single variable x, the function is f(x) = wx + b. Here, w is the weight (slope) and b is the bias (intercept). A slope of 2 means “every 1-unit change in X yields a 2-unit change in Y.”
• For multiple features x₁, x₂, …, the model becomes ŷ = f(x) = θ₀ + θ₁x₁ + θ₂x₂. Here, θ₀ is the intercept, and θ₁, θ₂ are coefficients for x₁, x₂ respectively.

Supervised Learning: Linear Regression is a type of supervised learning. This means the training dataset consists of “input-output pairs” (X, Y), where Y (the target) is known for each input X.

3. Data Representation for Regression

Tabular Dataset Structure

• Data/points/instances/examples/samples/records: Rows of the dataset.
• Features/attributes/dimensions/independent variables/covariates/predictors/regressors: Columns of the dataset, excluding the target.
• Target/outcome/response/label/dependent variable: A special column (usually the last) that is continuous-valued and to be predicted.

Concise Vector/Matrix Notation

To simplify computations, especially with multiple features:

• Each data sample x is represented as a column vector.
• A pseudo feature x₀=1 (the intercept term) is added to the feature vector, making it x^T = [(x₀=1), x₁, x₂, …, xₚ].
• The parameter vector θ is also a column vector [θ₀, θ₁, …, θₚ]^T.
• The linear regression function can then be concisely written as ŷ = f(x) = x^T θ = θ^T x.

Training Set in Matrix Form: The entire training set with n samples can be represented as a matrix X (where each row is a feature vector x_i^T) and a target vector y_train = [y₁, y₂, …, yₙ]^T.

4. Training and Optimization

Training Goal: To find the optimal parameters (w, b or θ) by minimizing a Loss/Cost function L(). This function quantifies the “difference between y and f(x) on available examples in the training set.”

Sum of Squared Error (SSE) / Mean Squared Error (MSE)

The most common loss function for linear regression:

• J(θ) = 1/2 × Σ (f(xᵢ) - yᵢ)²
• In matrix form, J(θ) = 1/2 × (Xθ - y)^T (Xθ - y)

Finding Optimal Parameters (θ)

Closed-form Solution (Normal Equation)

Since J(θ) is a convex function, its minimum can be found by taking the derivative (gradient) with respect to θ and setting it to zero (∇θJ(θ) = 0). This leads to the “normal equations”: X^T Xθ = X^T y.

The solution for θ is then θ* = (X^T X)^(-1) X^T y.

Convexity of J()

The loss function J(θ) is convex. “Intuitively, a convex function (1D case) has a single point at which the derivative goes to zero, and this point is a minimum.” For multivariate functions, if the Hessian matrix is positive definite (which X^T X is, given certain conditions), the function is convex and the point where the gradient is zero is a minimum.

Gradient Descent (GD) / Stochastic Gradient Descent (SGD)

These are iterative optimization algorithms used when a closed-form solution is not feasible or computationally too expensive. (Mentioned in outline, but not detailed in excerpts).

5. Evaluating Model Performance

Generalization: A primary aim is for the “learned model [to] Generalize Well” to unseen data. It should also be “Computational Scalable and Efficient” and “Robust / Trustworthy / Interpretable.”

Testing Mode: After training, the model is tested on “Production Data” (also called test data), which consists of new inputs X? for which the output f(X?) is predicted.

Metrics for Regression

• Test MSE Error: A common metric reported for evaluating regression models, calculated on the test set: J_test = 1/m × Σ (x_i^T θ* - y_i)².
• Other metrics exist (referencing scikit-learn documentation).

6. Computational Considerations

Why Vector/Matrix Form? It allows for “Concise Notation,” “Closed form solution” for training, and efficient computation for testing (ŷ_test = X_test θ*).

Computational Cost (Naive Matrix Multiply)

A naive matrix multiplication C = C + A×B has a complexity of O(n³) flops.

Optimizing Computational Cost

Data Parallelization

Utilizing CPU SIMD (Single Instruction, Multiple Data), multithreading, and GPU parallelization. SIMD allows “one operation [to produce] multiple results.”

Memory Hierarchy/Locality

Exploiting spatial (accessing nearby data) and temporal (reusing data) locality to improve average memory access speed through caches.

Better Algorithms

Examples include Strassen’s Matrix Multiply, which reduces complexity to O(n^2.81) (asymptotically faster than naive O(n³)).

BLAS (Basic Linear Algebra Subroutines)

Industry-standard interfaces (e.g., numpy wraps BLAS) providing optimized implementations for vector (BLAS1), matrix-vector (BLAS2), and matrix-matrix (BLAS3) operations. BLAS3 is generally preferred for its potential for higher computational intensity.

7. Advanced/Optional Concepts

Probabilistic Interpretation: Linear regression can be viewed probabilistically by assuming the error term ε (representing unmodeled effects or random noise) follows a Gaussian distribution N(0, σ). This leads to the concept of Maximum Likelihood Estimation for finding θ.

Gram Matrix: X^T X is referred to as a Gram Matrix and is always positive semi-definite. If X has full rank, X^T X is positive definite and invertible, ensuring a unique minimum for J(θ).

Regularization: Used when X has less than full column rank to handle non-invertible X^T X (not detailed in these excerpts but mentioned as a solution).

Scalability to Big Data: While polynomial time algorithms are good, O(n) can still be too slow for truly massive datasets, leading to research in “low rank, sparse, hardware, sampling, randomized…” solutions.

GD and SGD for LR

• Lecture: S1-LROptimization
• Version: current
• Notes to Read: SGD Jupyter notebook + numpy linalg +
• Extra Notes to Read: more SGD + ELS Ch3.2
• Video: M1 + M2

• Notebook Resources: notebook/L4_stochastic_gradient_descent.ipynb

Optimization for Linear Regression: A Study Guide

I. Course Overview & Core Concepts

This section of the course focuses on optimization techniques for Linear Regression (LR), specifically for tabular data. It revisits fundamental machine learning concepts within this context.

A. Course Sectioning Context

• Section 1: Basic Supervised Regression on Tabular Data
• Section 2: Basic Deep Learning on 2D Imaging Data
• Section 3: Advanced Supervised Learning on Tabular Data
• Section 4: Generative and Deep Learning on 1D Sequence Text Data
• Section 5: Unsupervised Learning (Mostly on Tabular Data)

B. Regression Fundamentals

• Regression: Deals with predicting a continuous output variable (y).
• Linear Regression (LR): Models the output (Y) as a weighted linear sum of input features (Xs).
• Sum of Squared Error (Least Squares): The standard cost function used to measure the difference between predicted and actual values in LR.
• Metrics, Implementation, Regression Coefficients (w, b): Key aspects to consider in LR.

C. Machine Learning Task Components

• Task: Predicting ‘y’.
• Representation: Input features ‘x’ and the function ‘f()’.
• Score Function: The loss function ‘L()’.
• Search/Optimization: The process of finding ‘argmin()’ for the loss function.
• Models, Parameters: The chosen model and its adjustable parameters.
• Data: ‘X’, typically tabular.
• Prediction: ŷ = f(x) = θ^T x (where θ represents the parameters/weights).

D. Optimization Principles

• Objective Function: The function to be minimized or maximized (e.g., the cost function).
• Variables: The parameters being optimized (e.g., weights ‘w’ or ‘θ’).
• Constraints: Conditions that the variables must satisfy.
• Goal: Find variable values that optimize the objective function while satisfying constraints.

II. Methods for Optimizing Linear Regression

The lecture covers two main approaches to optimizing Linear Regression: Direct Optimization (Normal Equation) and Iterative Optimization (Gradient Descent variants).

A. Method 1: Directly Optimize (Normal Equation)

Concept: For convex functions (like the Sum of Squared Error in LR), the minimum occurs where the derivative (slope) is zero.

Process:

1. Write the cost function J(θ) in matrix form.
2. Take the gradient of J(θ) with respect to θ and set it to zero.
3. Solve the resulting equation for θ.

Formula: θ = (X^T X)^(-1) X^T y

Pros: A single-shot algorithm, easiest to implement.

Cons:

• Requires computing the pseudo-inverse (X^T X)^(-1), which can be computationally expensive (especially for large datasets).
• Prone to numerical issues if the matrix is singular or ill-conditioned.

Direct vs. Iterative: A direct method, meaning it finds the solution in a finite number of steps.

B. Method 2: Iteratively Optimize via Gradient Descent

Concept: An iterative algorithm that moves towards the minimum of a function by taking steps proportional to the negative of the gradient at the current point.

Gradient Definition: A vector whose entries contain the partial derivatives of the function with respect to each variable. It points in the direction of the greatest rate of increase of the function.

General Algorithm:

1. Initialize k=0, choose an initial x₀ (randomly or by prior).
2. While k < k_max (or until a stopping criterion is met): x_k = x_{k-1} - α∇x F(x{k-1})

Key Factors Influencing GD:

• Learning Rate (α): Determines the step size. A critical parameter.
• Objective Function: Its shape (e.g., convexity) affects convergence.
• Starting Point: Can influence which local minimum is found (though not an issue for LR’s convex cost function).
• Stop Criterion: When to stop the iterative process.

Pros:

• Works on any objective function as long as its gradient can be evaluated.
• Useful for minimizing complex functions.
• Guaranteed convergence for convex functions like LR’s cost function.

Cons:

• Can be slow converging (especially batch GD).
• Can get stuck in local minima for non-convex functions (not an issue for LR).
• Learning rate selection is crucial.

C. Variants of Gradient Descent

1. Batch Gradient Descent (GD)

Concept: Calculates the gradient of the cost function with respect to the parameters for all training examples in each iteration.

Update Rule: θ_{t+1} = θ_t - α∇_θ J(θ_t) = θ_t + αX^T (y - Xθ_t)

Characteristics:

• Computes the exact gradient in each step.
• Smooth convergence path.
• Can be computationally expensive for very large datasets, as it needs to process the entire dataset per update.

2. Stochastic Gradient Descent (SGD)

Concept: Calculates the gradient and updates the parameters for each individual training example (or a very small subset) at a time.

Update Rule (for a single training point i): θ_{t+1} = θ_t + α(y_i - x_i^T θ_t)x_i

Characteristics:

• “Noisier” updates due to processing one example at a time.
• Faster per-step computation compared to batch GD.
• Can escape shallow local minima due to the noise (advantage for non-convex problems).
• Useful for massive datasets that don’t fit in memory or for online/streaming data.

Epoch: One complete pass over the entire training data when using SGD for offline training.

Pros:

• Low per-step cost.
• Can be faster converging to an approximate solution.
• Less prone to getting stuck in local optima (for non-convex cases).
• Efficient for large datasets and online learning.

Cons:

• Convergence to the exact optimum is not always guaranteed (it tends to oscillate around the minimum).
• More variation in the objective function during training.

3. Mini-Batch Gradient Descent

Concept: A compromise between Batch GD and SGD. Computes the gradient on a small “mini-batch” of samples (e.g., B=32, 64, 128).

Update Rule: θ_{t+1} = θ_t + (1/B)αX_B^T (y_B - X_B θ_t) (where B refers to the mini-batch size and X_B, y_B are the mini-batch data)

Characteristics:

• Combines benefits of both: more stable updates than SGD, but computationally more efficient than Batch GD (especially with GPU acceleration).
• Commonly used in practice.
• Special Cases: B=1 is standard SGD, B=N (total data size) is standard Batch GD.

Pros:

• Much faster computationally than single-point SGD (better use of computer architecture like GPUs).
• Low per-step cost.
• Fast convergence.

D. Stopping Criteria for Gradient Descent

• Predetermined Maximum Number of Iterations: A common and simple stopping rule.
• Threshold for Improvement: Stop when the improvement in the objective function (e.g., MSE) drops below a certain threshold.
• Monitoring Training Error: Plotting Train-MSE per sample to observe its decrease over epochs is helpful for understanding behavior.

Quiz: Optimization for Linear Regression

1. What is the primary goal of optimization in the context of Linear Regression?
2. Briefly explain the main idea behind the “Normal Equation” method for Linear Regression.
3. What are two significant disadvantages of using the Normal Equation, especially for large datasets?
4. Define “Gradient Descent” as an iterative optimization algorithm.
5. List three critical factors that influence the behavior and performance of Gradient Descent.
6. How does Stochastic Gradient Descent (SGD) differ from Batch Gradient Descent (GD) in terms of gradient calculation and parameter updates?
7. Provide two advantages of using Stochastic Gradient Descent (SGD) compared to Batch Gradient Descent for very large datasets.
8. What is “Mini-Batch Gradient Descent,” and why is it often preferred in practice?
9. Explain the concept of an “epoch” in the context of Stochastic Gradient Descent.
10. Name two common stopping criteria for iterative optimization algorithms like Gradient Descent.

Quiz Answer Key

1. Primary Goal of Optimization: The primary goal of optimization in Linear Regression is to find the set of model parameters (weights ‘w’ or ‘θ’) that minimize the chosen cost function, typically the Sum of Squared Error (Least Squares). This minimization results in the best-fit line or hyperplane for the given data.

2. Normal Equation Method: The Normal Equation method directly solves for the optimal Linear Regression parameters by setting the gradient of the cost function to zero. It analytically calculates the parameters in a single step using matrix operations, without needing an iterative process.

3. Disadvantages of Normal Equation: Two significant disadvantages of the Normal Equation are its high computational cost due to the requirement of computing a matrix inverse, particularly for large numbers of features, and its susceptibility to numerical issues if the (X^T X) matrix is singular or ill-conditioned.

4. Gradient Descent Definition: Gradient Descent is an iterative optimization algorithm that minimizes an objective function by repeatedly moving in the direction opposite to the gradient of the function. Each step adjusts the parameters by a small amount proportional to the negative of the gradient, gradually approaching a local (or global) minimum.

5. Critical Factors for GD: Three critical factors influencing Gradient Descent are the learning rate (α), which determines the step size; the shape of the objective function, which dictates the gradient landscape; and the starting point, which can affect the path to the minimum or which local minimum is found.

6. SGD vs Batch GD: Stochastic Gradient Descent (SGD) updates parameters using the gradient calculated from a single training example at a time, leading to noisy but frequent updates. In contrast, Batch Gradient Descent (GD) calculates the gradient using all training examples before making a single parameter update, resulting in smoother but less frequent updates.

7. Advantages of SGD: Two advantages of SGD for very large datasets are its low per-step computational cost, as it processes only one sample at a time, making it suitable for data that doesn’t fit in memory, and its ability to converge faster to an approximate solution.

8. Mini-Batch Gradient Descent: Mini-Batch Gradient Descent is an optimization technique that computes the gradient and updates parameters using a small, randomly selected subset (mini-batch) of the training data. It is often preferred because it balances the stability of Batch GD with the computational efficiency of SGD, leading to faster training and better utilization of hardware like GPUs.

9. Epoch Concept: In the context of Stochastic Gradient Descent, an “epoch” refers to one complete pass through the entire training dataset. If SGD is used for offline training, it repeatedly cycles through all samples in the dataset, and each such pass constitutes an epoch.

10. Stopping Criteria: Two common stopping criteria for Gradient Descent algorithms include a predetermined maximum number of iterations (epochs) and stopping when the improvement in the objective function (e.g., Train MSE) between consecutive iterations drops below a specified small threshold.

LR with basis

• Lecture: S1-LRSelectExtend
• Version: current
• More advanced to Read: S1-nonparametric
• Notes to Read: L5_Poly_Regression.ipynb
• Extra Notes to Read: NonLinearR + ELS Ch5
• Video: M1 + M2

• Notebook Resources: notebook/L5-Poly-Regression.ipynb

• Notebook Resources: notebook/L5-RBF-regressionLR.ipynb

Understanding Linear Regression with Basis Functions Expansion

Study Guide

This study guide is designed to review your understanding of Linear Regression with Basis Functions Expansion, as presented in the provided lecture material.

I. Core Concepts of Linear Regression

Definition of Regression

What is the primary characteristic of the y variable in a regression task?

Goal of Linear Regression with Basis Expansion

How does Linear Regression (LR) achieve the ability to model non-linear relationships using basis functions?

Key Components of a Machine Learning Task

Identify and briefly describe the four fundamental components mentioned for any machine learning task:

• Task: What needs to be predicted
• Representation: How data and functions are structured
• Score Function: Metric to evaluate model performance
• Search/Optimization: Algorithms to find optimal parameters

Parameters vs. Models

Differentiate between “models” and “parameters” in the context of machine learning.

Optimization Methods

List the three primary methods mentioned for optimizing the Sum of Squared Error:

1. Normal Equation
2. Gradient Descent (GD)
3. Stochastic Gradient Descent (SGD)

“KEY” Insight

Explain the fundamental implication of having predefined basis functions on the nature of the learning problem.

II. Basis Functions Expansion

Purpose of Basis Functions

Why are basis functions introduced in linear regression?

Types of Basis Functions

Name at least three different types of basis functions mentioned in the lecture:

• Polynomial basis functions
• Radial Basis Functions (RBFs)
• Trigonometric basis functions

Polynomial Regression

What is the specific form of the basis function φ(x) for polynomial regression up to degree two (d=2)?

For degree 2: φ(x) = [1, x, x²]ᵀ

How is the prediction ŷ formulated using polynomial basis functions?

ŷ = θᵀφ(x) = θ₀ + θ₁x + θ₂x²

Radial Basis Functions (RBFs)

Define what an RBF is in terms of its dependency. RBFs are functions whose output depends only on the distance from a central point.

Describe the characteristic behavior of a Gaussian RBF as distance from its center increases. The output decreases exponentially as the distance from the center increases, creating a bell-shaped curve.

What are the “hyperparameters” that users need to define for RBF basis functions?

• Centers (μⱼ): The central points where RBFs are located
• Widths (λⱼ): Parameters controlling the spread of the RBF

Provide the general mathematical form of a Gaussian RBF, specifically φⱼ(x).

III. Parametric vs. Non-Parametric Models

Parametric Learning Algorithm

Define a parametric learning algorithm, using (unweighted) linear regression as an example. What is a key characteristic regarding the need for training data after fitting?

Parametric algorithms have a fixed number of parameters that are learned from data. Once trained, the training data can be discarded as predictions are made using only the learned parameters.

Non-Parametric Learning Algorithm

Define a non-parametric learning algorithm, providing examples like K-Nearest Neighbor (KNN) or Locally Weighted Linear Regression. How does the “amount of knowledge” required to represent the hypothesis differ from parametric models?

Non-parametric algorithms require the entire training dataset to be kept for making predictions. The amount of knowledge grows with the size of the training set.

IV. Mathematical Notations and Formulas

General Prediction Equation

Write down the general equation for ŷ (predicted output) using basis functions φ(x) and weights θ.

ŷ = θᵀφ(x)

Normal Equation

Provide the formula for calculating the optimal weight vector θ* using the Normal Equation, given φ(x) and y.

θ* = (ΦᵀΦ)⁻¹Φᵀy

where Φ is the design matrix with rows φ(xᵢ)ᵀ

Quiz: Linear Regression with Basis Functions

Instructions: Answer each question in 2-3 sentences.

1. How does Linear Regression with basis functions expansion allow for the modeling of non-linear relationships, despite being fundamentally a “linear” model?

2. What is the significance of the “KEY” insight mentioned in the lecture regarding predefined basis functions?

3. Describe the primary goal of the “Search/Optimization” component in a machine learning task, as it relates to the score function.

4. If you are performing polynomial regression with a degree up to three, what would be the form of the basis function vector φ(x)?

5. Explain why Radial Basis Functions (RBFs) are often described as “bell-shaped” or having an output that decreases with distance from a center.

6. What role do the “centers” and “widths” play in defining Radial Basis Functions?

7. Differentiate between the “Task” and “Representation” components of a machine learning problem.

8. Briefly explain the main difference in how parametric and non-parametric learning algorithms utilize training data after the initial fitting phase.

9. Which optimization methods, other than the Normal Equation, are mentioned for finding the optimal regression coefficients?

10. In the context of the general prediction equation ŷ = θᵀφ(x), what do θ and φ(x) represent, respectively?

Quiz Answer Key

1. Non-linear Modeling: Linear Regression with basis functions models non-linear relationships by transforming the input features x into a higher-dimensional space using non-linear basis functions φ(x). The relationship between the transformed features φ(x) and the output y remains linear, allowing linear regression techniques to be applied.

2. KEY Insight: The “KEY” insight is that even when non-linear basis functions are used, the problem of learning the parameters from the data is still considered Linear Regression. This is because the model is linear with respect to the parameters θ, even if it’s non-linear with respect to the original input x.

3. Search/Optimization Goal: The “Search/Optimization” component’s primary goal is to find the set of model parameters that minimize (or maximize, depending on the objective) the score function. This process iteratively adjusts the parameters to achieve the best possible fit to the training data according to the defined score.

4. Polynomial Basis Vector: For polynomial regression with a degree up to three, the basis function vector φ(x) would be [1, x, x², x³]ᵀ. This expands the single input feature x into a set of features including its powers.

5. RBF Bell Shape: RBFs are “bell-shaped” because their output typically reaches a maximum at a central point and then decreases symmetrically as the input moves further away from that center. For Gaussian RBFs, this decay is exponential, creating a characteristic bell-like curve.

6. RBF Centers and Widths: In RBFs, “centers” (μⱼ) define the point in the input space where the basis function’s influence is maximal, while “widths” (λⱼ) determine how rapidly the function’s output decreases as the input moves away from that center, thus controlling the spread or local influence of the RBF.

7. Task vs Representation: “Task” defines what needs to be predicted (e.g., y is continuous for regression). “Representation” refers to how the input data x and its potential transformations f() are structured for the model, essentially defining the features used for prediction.

8. Parametric vs Non-parametric Data Usage: Parametric algorithms, once trained, can discard the training data as predictions are made solely using the learned, fixed parameters. Non-parametric algorithms, in contrast, require the entire training dataset to be kept available for making future predictions, as their “knowledge” grows with the data size.

9. Other Optimization Methods: Besides the Normal Equation, the lecture also mentions Gradient Descent (GD) and Stochastic Gradient Descent (SGD) as optimization methods for finding optimal regression coefficients by minimizing the Sum of Squared Error.

10. Prediction Equation Components: In ŷ = θᵀφ(x), θ represents the vector of regression coefficients (weights) that the model learns from the data. φ(x) represents the basis function expansion of the input x, which transforms the original features into a potentially higher-dimensional space.

Workflow for model selection

• Lecture: S1-ModelSelect
• Version: current
• Notes to Read: hyperpara select notebook + flow API
• Extra Notes to Read: ELS Ch5
• Video: M1

• Notebook Resources: notebook/L6-Hyperparameters-and-Model-Validation.ipynb

Model Selection and Validation Study Guide

Quiz: Short Answer Questions

1. What is the primary goal of model selection in machine learning? The primary goal is to choose the right model type and its hyperparameters to ensure good generalization, meaning the model can accurately predict future data drawn from the same distribution, rather than just fitting the training data well. This involves balancing between underfitting and overfitting.

2. Explain the difference between overfitting and underfitting. Underfitting occurs when a model is too simple to capture the underlying patterns in the data, leading to high training and test errors (high bias). Overfitting happens when a model is too complex and fits noise in the training data, resulting in low training error but high test error (high variance).

3. Why is simply choosing the model with the best fit to the training data not a reliable strategy for model selection? Choosing the model with the best fit to the training data is unreliable because it often leads to overfitting. An overfit model memorizes the training data, including noise, and performs poorly on new, unseen data, failing to generalize effectively.

4. Describe the process of the “Train-Validation” (Hold-out) method for model selection. The train-validation method involves splitting the labeled data into two sets: a training set (e.g., 70%) and a validation set (e.g., 30%). The model is trained on the training set, and its performance is then estimated using the validation set to evaluate its future performance.

5. What are the main advantages and disadvantages of the “Train-Validation” method? Advantages include its simplicity and ease of implementation. Disadvantages are that it “wastes data” (the validation set is not used for training the final model) and can lead to a high variance in performance estimation if the validation set is small or unrepresentative.

6. What problem does K-Fold Cross-Validation aim to solve compared to the simple train-validation method? K-Fold Cross-Validation addresses the issue of data wastage and high variance in performance estimation inherent in the train-validation method, especially when data is scarce. It ensures that each data point is used for both training and validation, providing a more robust estimate.

7. Briefly explain how K-Fold Cross-Validation works. In K-Fold Cross-Validation, the dataset is divided into K equal “folds.” The model is trained K times; in each iteration, one fold is used as the validation set, and the remaining K-1 folds are used as the training set. The scores from each validation step are collected, and their mean is typically reported as the overall performance estimate.

8. What is Leave-One-Out Cross-Validation (LOOCV), and how does it relate to K-Fold Cross-Validation? Leave-One-Out Cross-Validation (LOOCV) is a specific type of K-Fold Cross-Validation where K is equal to n, the number of data points in the dataset. In LOOCV, each data point individually serves as the validation set, and the model is trained on the remaining n-1 points.

9. When analyzing a validation curve (score vs. model complexity), what typically happens to the training and validation scores as model complexity increases, and why? As model complexity increases, the training score generally increases (or error decreases) because a more complex model can fit the training data better. The validation score will initially increase alongside the training score but will eventually start to decrease after a certain point due to overfitting, as the model begins to learn noise from the training data.

10. Define Bias and Variance in the context of machine learning models. Bias refers to the error introduced by approximating a real-world problem, which may be complex, by a simplified model. It represents how much the average model over all training sets differs from the true model. Variance refers to how much the models estimated from different training sets differ from each other, reflecting the model’s sensitivity to small fluctuations in the training data.

Essay Format Questions

1. Compare and contrast the Train-Validation (Hold-out), K-Fold Cross-Validation, and Leave-One-Out Cross-Validation methods for model selection. Discuss their respective advantages, disadvantages, and typical use cases, particularly considering data availability.

2. Elaborate on the concepts of overfitting and underfitting. Explain how these phenomena manifest in model performance metrics (training error, test error) and discuss various strategies for mitigating each, referencing the bias-variance tradeoff.

3. Discuss the “generalization” goal in machine learning. Why is it more important than achieving a perfect fit to training data, and what techniques are employed to ensure a model generalizes well to new, unseen data?

4. Explain the significance of the bias-variance tradeoff in model selection. Provide examples of how model complexity influences bias and variance, and describe how one might navigate this tradeoff using techniques discussed in the source material.

5. Imagine you are tasked with selecting the optimal polynomial degree for a regression model on a limited dataset. Describe a step-by-step process you would follow, incorporating at least two different validation techniques, to make an informed decision while addressing potential pitfalls.

Glossary of Key Terms

• Model Selection: The process of choosing the right model type and its hyperparameters to achieve the best performance on unseen data.

• Hyperparameter: A parameter whose value is used to control the learning process, which is set before the learning process begins (e.g., polynomial degree, number of folds in cross-validation).

• Overfitting: A phenomenon where a model learns the training data too well, including its noise and irrelevant details, leading to excellent performance on training data but poor performance on new, unseen data. Characterized by low bias and high variance.

• Underfitting: A phenomenon where a model is too simple to capture the underlying patterns in the training data, resulting in poor performance on both training and new data. Characterized by high bias and low variance.

• Generalization: The ability of a machine learning model to perform accurately on new, unseen data, reflecting its capacity to “explain,” “predict,” or “model” new examples from the same distribution as the training data.

• Training Set: The portion of the labeled dataset used to train the machine learning model.

• Validation Set (Hold-out Set): A separate portion of the labeled dataset used to estimate the model’s performance during training and hyperparameter tuning, helping to avoid overfitting to the test set.

• Test Set: A completely independent portion of the labeled dataset, kept separate from both training and validation, used to provide an unbiased evaluation of the final chosen model’s performance on new data.

• Mean Squared Error (MSE): A common metric for regression models, calculated as the average of the squares of the differences between predicted and actual values. Lower MSE indicates better model performance.

• Variance (of performance estimator): Refers to how much an estimate of performance might change if a different validation set or data split were used. High variance implies an unreliable estimate.

• K-Fold Cross-Validation: A resampling procedure used to evaluate machine learning models on a limited data sample. The dataset is divided into K folds, and the model is trained and validated K times, with each fold serving as the validation set once.

• Leave-One-Out Cross-Validation (LOOCV): A special case of K-Fold Cross-Validation where K equals the number of data points (n). Each data point is used as a validation set, with the remaining n-1 points used for training.

• Bias: The error due to inaccurate assumptions or simplifications made by the model. A high bias model typically underfits the data.

• Variance: The error due to the model’s sensitivity to small fluctuations in the training data. A high variance model typically overfits the data.

• Bias-Variance Tradeoff: The inherent conflict in machine learning where reducing one type of error (bias or variance) tends to increase the other. The goal is to find a balance that minimizes overall prediction error.

• Learning Curve: A plot showing the performance of a learning model (e.g., score or error) on both the training set and validation set as a function of the number of training examples or model complexity.

• Validation Curve: A plot showing the performance of a learning model (e.g., score or error) on both the training set and validation set as a function of a model hyperparameter (e.g., model complexity).

Linear Prediction with Regularization

• Lecture: S1-lrRegularized
• Version: current
• Extra Notes to Read: More Ridge
• Video: M1 + M2 + Extra M3

• Notebook Resources: notebook/L7_regularizedRegression_06_Linear_Regression.ipynb

Study Guide: Regularized Linear Regression

This guide provides a comprehensive review of the concepts surrounding regularized multivariate linear regression, based on the provided source material. It includes a quiz to test understanding, essay questions for deeper exploration, and a glossary of key terminology.

Quiz

Answer the following questions in 2-3 sentences each, based on the provided source material.

1. Why is standard linear regression often problematic for datasets where the number of features (p) is greater than the number of samples (n)?
2. What is regularization in the context of machine learning, and what problem does it primarily address?
3. Describe the penalty term used in Ridge (L2) regression and explain how it affects the model’s coefficients.
4. Describe the penalty term used in LASSO (L1) regression and explain its key advantage over Ridge regression.
5. What is the primary purpose of the regularization parameter, λ (lambda), and how is its optimal value typically determined?
6. Explain the concept of a “regularization path” and what it visualizes.
7. What is Elastic Net regularization and why was it developed?
8. From a geometric perspective, why does LASSO (L1) regularization tend to produce sparse models (i.e., set some coefficients to exactly zero)?
9. What are the three main goals for a trained machine learning model mentioned in the lecture?
10. What is the “grouping effect” in the context of Elastic Net, and when is it particularly useful?

Quiz Answer Key

1. When p > n, the matrix X^T X in the normal equation for linear regression has less than full column rank and is therefore not invertible. This prevents the direct calculation of a unique solution for the regression coefficients using Ordinary Least Squares.

2. Regularization is an additional criterion added to the loss function to ensure the model does not overfit the training data. It primarily addresses the issue of overfitting by keeping the model’s parameters more “normal” or regular, effectively adding a bias that prefers certain types of weights (e.g., smaller ones) over others.

3. Ridge regression adds an L2 penalty, which is proportional to the sum of the squared coefficient weights (λ Σ βj²). This penalty shrinks the coefficients towards zero, with the effect becoming stronger as λ increases. However, it does not set the coefficients exactly to zero.

4. **LASSO regression uses an L1 penalty, proportional to the sum of the absolute values of the weights (λ Σ

   βj

   ).** Its key advantage is that it performs both shrinkage and variable selection simultaneously, as the penalty can force some coefficients to be exactly zero, creating a more interpretable and sparse model.

5. The regularization parameter λ controls the strength of the penalty; λ=0 corresponds to standard least squares, while a large λ pushes coefficients towards zero. The optimal value is chosen to ensure good generalization ability on new data and is typically determined using k-fold cross-validation.

6. A regularization path is a plot that visualizes how the model’s regression coefficients (βj) change in value as the regularization parameter λ is varied. It illustrates the effect of the penalty on each feature’s weight, from the unregularized solution to a highly constrained one.

7. Elastic Net is a hybrid regularization method that combines both L1 (LASSO) and L2 (Ridge) penalties. It was developed to address disadvantages of LASSO, such as its limitation of selecting at most n variables in a p>n scenario and its tendency to arbitrarily select only one variable from a group of highly correlated ones.

8. Geometrically, the L1 constraint region is a diamond shape with sharp corners that lie on the axes. The elliptical contour lines of the least squares error function are more likely to first make contact with this region at one of its corners. This contact point corresponds to a solution where coefficients for other axes are zero, thus producing sparsity.

9. The three main goals for a trained model are to (1) generalize well to new data, (2) be computationally scalable and efficient, and (3) be trustworthy, meaning it is robust and interpretable.

10. The “grouping effect” is a property of Elastic Net that encourages the model to select or deselect groups of highly correlated variables together. This is useful when features are naturally grouped, as LASSO by itself tends to arbitrarily select only one variable from such a group.

Essay Questions

The following questions are designed for longer, essay-style responses to encourage a deeper synthesis of the material. No answers are provided.

1. Compare and contrast Ridge, LASSO, and Elastic Net regularization. Discuss the mathematical formulation of their penalty terms, their impact on model coefficients, and the specific scenarios where one might be preferred over the others.

2. Explain the problem of overfitting in multivariate linear regression, particularly in the context of “large p, small n” datasets. How does regularization serve as a solution to this problem, and what is the trade-off involved?

3. Describe the role and importance of the hyperparameter λ in regularized regression. Detail the process of using k-fold cross-validation to select an optimal λ and explain why this process is crucial for building a model that generalizes well.

4. Using the geometric interpretation of regularized regression, explain why L1 regularization (LASSO) leads to sparse solutions while L2 regularization (Ridge) does not. Use the concepts of constraint regions and objective function contour lines in your explanation.

5. Discuss the practical application of regularized regression in a real-world problem like text regression for predicting movie revenues. Explain how model interpretability, a key feature of LASSO and Elastic Net, is valuable in such a domain.

Glossary of Key Terms

KNN and Theory

• Lecture: S1-KNN
• Version: current
• More advanced to Read: S1-KNN-extra
• Video: M1 + M2

• Notebook Resources: notebook/L8_Knearest.ipynb

K-Nearest Neighbor (KNN) Study Guide

Short-Answer Quiz

Answer each question in 2-3 sentences.

1. Describe the three main categories of supervised classifiers and provide an example for each.
2. Explain the concept of “lazy learning” as it applies to the K-Nearest Neighbor algorithm.
3. What are the three essential components required for a K-Nearest Neighbor (Instance-based) method?
4. Contrast the process for making a prediction in KNN for a regression task versus a classification task.
5. What happens during the “Training Mode” of a naïve K-Nearest Neighbor algorithm?
6. Outline the three steps involved in the “Testing Mode” when using KNN to classify an unknown sample.
7. Why is feature scaling important for K-Nearest Neighbor algorithms? Provide a brief example.
8. Discuss the bias-variance tradeoff when selecting the value of k. What is the effect of a k that is too small or too large?
9. What is the “curse of dimensionality,” and how can it negatively impact the performance of a KNN model?
10. According to the Cover and Hart theorem (1967), what is the asymptotic relationship between the error rate of 1-nearest-neighbor classification and the Bayes rate?

Quiz Answer Key

1. The three major types of supervised classifiers are Discriminative, Generative, and Instance-based. Discriminative classifiers, like logistic regression or support vector machines, directly estimate a decision boundary. Generative classifiers, such as Naïve Bayes, build a statistical model of the data. Instance-based classifiers, like KNN, use the training observations directly without building an explicit model.

2. Instance-based learning is referred to as “lazy learning” because the decision of the output value is delayed until a new instance arrives for prediction. In KNN, no model is built during a training phase; instead, the original training instances themselves represent the knowledge, and computation is deferred until a prediction is requested.

3. The three essential components for a KNN method are: (1) the set of stored training samples, (2) a distance metric to compute the distance between samples (e.g., Euclidean distance), and (3) the value of k, which specifies the number of nearest neighbors to retrieve.

4. For a regression task, where the target variable is continuous, KNN makes a prediction by taking the mean value of the k nearest training examples. For a classification task, where the target is discrete, the prediction is determined by a majority vote among the class labels of the k nearest neighbors.

5. In the naïve version of the K-Nearest Neighbor algorithm, the training mode involves doing nothing other than storing the training samples. The algorithm does not build a model but simply retains the dataset, which will be used directly during the testing or deployment phase.

6. The three steps in the testing mode are: (1) Compute the distance from the unknown sample to all records in the training set. (2) Identify the k nearest neighbors based on these computed distances. (3) Use the class labels of these nearest neighbors to determine the class label of the unknown record, typically by taking a majority vote.

7. Feature scaling is important because attributes with larger ranges can dominate distance calculations, skewing the model’s performance. For example, if one feature is a person’s income (e.g., $10K to $1M) and another is height (e.g., 1.5m to 1.8m), the income attribute would have a much larger influence on the Euclidean distance calculation unless the features are scaled to a comparable range.

8. When selecting k, a small value can lead to a model that is sensitive to noise points, resulting in high variance and an unstable, though potentially accurate, local model. Conversely, a large k can cause the neighborhood to include points from other classes, leading to a model with high bias and an inaccurate estimation, though it will be more stable.

9. The “curse of dimensionality” refers to the problem where a nearest neighbor algorithm can be easily misled when working with high-dimensional data (i.e., data with many features). In a high-dimensional space, most points are far apart, and the concept of a “close” neighbor becomes less meaningful, especially if many attributes are irrelevant to the target function.

10. The Cover and Hart theorem states that asymptotically (with an infinite number of training samples), the error rate of 1-nearest-neighbor classification is less than twice the Bayes rate. The Bayes rate is the error rate of an optimal classifier that knows the true data-generating model, representing the lowest achievable error.

Essay Questions

1. Discuss the core principles of instance-based learning. How does KNN exemplify these principles, and what are the primary advantages and disadvantages of this “lazy” approach compared to “eager” learning models like linear regression?
2. Explain the role of distance metrics in the KNN algorithm. Compare and contrast at least three different distance metrics mentioned in the source material (e.g., Euclidean, Manhattan, Mahalanobis) and discuss scenarios where one might be preferable over the others.
3. Elaborate on the different variations of the standard KNN algorithm, such as Distance-Weighted KNN and RBF kernel Weighted KNN. How do these methods attempt to improve upon the naïve majority-vote approach?
4. Describe the relationship between KNN, non-parametric density estimation, and the Bayes classifier. How can the principles of the Bayes classifier be used to provide a probabilistic interpretation for KNN?
5. While KNN is conceptually simple, its computational cost can be a significant drawback. Discuss the computational time cost of the naïve KNN search and explain how a data structure like a KD Tree can be used to optimize the search for nearest neighbors.

Glossary of Key Terms

Lasso and Elastic Net

• Lecture: S1-lrRegularized
• Version: current
• Notes to Read: Elastic paper
• Video: Extra M3

Bias Variance Tradeoff

• Lecture: S1-biasVariance
• Version: current
• More advanced to Read: S1-Tibshirani-modelbasics
• Notes to Read: notebook validation and learning curves
• Extra Notes to Read: Useful BiasVar + ESL Ch7
• Video: M1 + M2

• Notebook Resources: notebook/L6-Hyperparameters-and-Model-Validation.ipynb

• Notebook Resources: notebook/L9-LearningCurves.ipynb

Study Guide: The Bias-Variance Tradeoff

This guide is designed to review and reinforce key concepts related to the bias-variance tradeoff in machine learning. It includes a quiz with an answer key to test comprehension, a set of essay questions for deeper exploration, and a glossary of essential terms.

Part I: Short-Answer Quiz

Instructions: Answer the following ten questions in 2-3 sentences each, based on the provided source material.

1. What is the ultimate goal in machine learning, and why is minimizing training error not always sufficient to achieve it?
2. Explain the decomposition of Expected Prediction Error (EPE). What does each component represent?
3. Describe the characteristics of a model that is “underfitting.” How does this relate to bias and variance?
4. Describe the characteristics of a model that is “overfitting.” How does this relate to bias and variance?
5. Why are bias and variance not directly computable in a real-world machine learning problem?
6. Compare the properties of a linear classification model with a 1-Nearest Neighbor model in terms of bias and variance.
7. According to statistical decision theory, what is the best theoretical estimator for a regression problem under L2 (squared error) loss?
8. Identify two distinct methods for reducing high model variance (overfitting).
9. Identify two distinct methods for reducing high model bias (underfitting).
10. What is the difference between model selection and model assessment?

Part II: Quiz Answer Key

1. The ultimate goal is generalization, which is the model’s ability to perform well on new, unseen data. Minimizing training error is not always sufficient because a model can become too complex and fit irrelevant noise in the training data (e.g., 1-NN), leading to poor performance on test data.

2. Expected Prediction Error (EPE) decomposes into three parts: EPE(x) = noise² + bias² + variance. Noise (or Irreducible/Bayes error) is the unavoidable error inherent in the data. Bias is the error from incorrect assumptions made by the model. Variance is the error due to the model’s sensitivity to the randomness of the training samples.

3. An underfitting model is too “simple” to represent the relevant characteristics of the data. This condition is defined by high bias and low variance, resulting in both high training error and high test error.

4. An overfitting model is too “complex” and fits irrelevant characteristics or noise in the training data. This condition is defined by low bias and high variance, which leads to low training error but high test error.

5. Bias and variance cannot be computed directly because their calculation relies on knowing the true underlying distribution of the input vectors (x) and output variables (y), which is unknown in practice.

6. A linear classification model is a global model that is stable but can be inaccurate, exhibiting high bias and low variance. In contrast, a 1-Nearest Neighbor model is a local model that is accurate on training data but unstable, exhibiting low bias and high variance.

7. Under L2 loss, the best theoretical estimator to minimize EPE is the conditional mean (also called conditional expectation). This is expressed as f̂(x) = E(Y

   X = x).

8. To reduce high variance, one can choose a simpler classifier, regularize the parameters, get more training data, or use a smaller set of features.

9. To reduce high bias, one can get additional features to provide more information or try a more complex learning model with more flexibility.

10. Model selection is the process of estimating the performance of different models to choose the best one. Model assessment is the subsequent process of taking the chosen model and estimating its prediction error on new, unseen data.

Part III: Essay Questions

Instructions: The following questions are designed to encourage a deeper, more synthesized understanding of the topic. Formulate comprehensive answers based on the source material.

1. Discuss the Bias-Variance Tradeoff in detail. Explain how model complexity influences bias, variance, training error, and expected test error. Use the examples of a highly regularized linear model and a 1-Nearest Neighbor classifier to illustrate the opposing ends of the complexity spectrum.

2. You are presented with a learning curve where the training error is unacceptably high and there is only a small gap between the training error and the test error. Diagnose the problem, explain the underlying issues in terms of bias and variance, and propose at least two concrete remedies to improve the model.

3. Explain the concept of Expected Prediction Error (EPE) and its decomposition into noise, bias, and variance. Describe why the noise component is considered “irreducible” and provide the theoretical justification for why the conditional mean is the optimal estimator for EPE under L2 loss.

4. Compare and contrast the Frequentist and Bayesian interpretations of probability as they relate to model parameters. How does the Bayesian approach handle parameter estimation differently from the Frequentist approach?

5. Describe the role of cross-validation (CV) in the machine learning pipeline, particularly when data is not abundant. Discuss the practical considerations for choosing the value of K in K-fold CV, including the bias-variance tradeoff inherent in this choice.

Part IV: Glossary of Key Terms

Section 2 - Deep on 2D Grid Type (e.g. Imaging)

ProbReview + MLE

• Lecture: S2-MLE
• Version: current
• More advanced to Read: S2-MLE
• Notes to Read: Error Metrics
• Extra Notes to Read: MLE / MLE code
• Video: M1

Study Guide: Maximum Likelihood Estimation

Quiz: Key Concepts Review

Answer the following questions in 2-3 sentences each based on the provided course material.

1. What is the fundamental goal of Machine Learning as described in the lecture?
2. Define “Sample Space” and “Event” in the context of probability theory, and provide an example for each.
3. What is the core principle of Maximum Likelihood Estimation (MLE)?
4. Why is it often more convenient to work with the log-likelihood function instead of the likelihood function itself?
5. For a Bernoulli distribution, what is the Maximum Likelihood Estimate for the parameter p (the probability of success)?
6. How does a probability density function (pdf) for a continuous random variable differ from a probability mass function (pmf) for a discrete random variable?
7. What do the mean and covariance matrix represent in a multivariate normal (Gaussian) distribution?
8. What key assumption connects Maximum Likelihood Estimation to the least squares error function in linear regression?
9. In the probabilistic interpretation of linear regression, what distribution is the error term (ε) assumed to follow?
10. Define the covariance between two random variables, X and Y.

Essay Questions

The following questions are designed for longer-form, essay-style answers to test a deeper synthesis of the material. Answers are not provided.

1. Explain the complete process of deriving the Maximum Likelihood Estimate for the parameter p of a Bernoulli distribution. Detail the role of the likelihood and log-likelihood functions, the use of differentiation to find the maximum, and interpret the final result.

2. Describe the relationship between basic probability concepts (sample space, events, random variables) and the task of machine learning. How do these foundational ideas enable the formulation of a model and the application of an estimation technique like MLE?

3. Compare and contrast discrete and continuous random variables. Discuss their respective probability functions (pmf vs. pdf), how their means (expectations) are calculated, and provide an example of each as mentioned in the lecture notes.

4. Discuss the probabilistic interpretation of linear regression. Explain how assuming a Gaussian distribution for the error term allows the problem to be framed as a Maximum Likelihood Estimation task, and show why maximizing the log-likelihood is equivalent to minimizing the sum of squared errors.

5. What are the key properties of a multivariate Gaussian (Normal) distribution? Describe the roles of the mean vector and the covariance matrix, and explain how they influence the shape and orientation of the probability density function, using the bivariate normal distribution as an illustrative example.

Answer Key

Quiz Answers

1. The goal of Machine Learning is to optimize a performance criterion using example data or past experience. The primary aim is to develop models that can generalize their performance to new, unseen data.

2. A Sample Space (O) is the set of all possible outcomes of an experiment, such as {HH, HT, TH, TT} for tossing a coin twice. An Event is a subset of the sample space, such as the event of the first toss being a head, which would be the set {HH, HT}.

3. The principle of Maximum Likelihood Estimation is to select the set of model parameters (θ) that are most likely to have produced the observed data. This is achieved by assuming a particular model and finding the parameter values that maximize the joint probability (the likelihood) of the observed sample set.

4. Working with the log-likelihood function is convenient because it converts the joint probability, which is a product of individual probabilities, into a sum. This transformation from Π P(Zi

   θ) to Σ log(P(Zi

   θ)) simplifies the mathematical process of finding the maximum, particularly when taking derivatives.

5. The MLE for the parameter p in a Bernoulli distribution is the sample proportion of positive outcomes. It is calculated as p̂ = x/n, where x is the number of successes (e.g., heads) observed in n trials.

6. A probability mass function (pmf) gives the probability that a discrete random variable is equal to a specific value, P(X = xi). A probability density function (pdf) describes the probability density for a continuous variable, and the actual probability is obtained by taking the integral of the pdf over a given range.

7. In a multivariate normal distribution, the mean vector (μ) is the point where the PDF reaches its peak value. The covariance matrix (Σ) captures the linear dependencies among the variables and determines the shape and orientation of the elliptical contours of equal probability density.

8. The key assumption is that the error term, or residual, in the linear regression model is independent and identically distributed (IID) according to a Gaussian (Normal) distribution with a mean of zero. This assumption makes maximizing the data likelihood equivalent to minimizing the residual sum of squares.

9. In the probabilistic view of linear regression, the error term ε is assumed to follow a Gaussian distribution with a mean of 0 and some variance σ², denoted as N(0, σ).

10. Covariance measures the joint variability of two random variables. It is defined as the expectation of the product of their deviations from their individual means: Cov(X,Y) = E((X − µx)(Y − µy)).

Glossary of Key Terms

Logistic and NN

• Lecture: S2-LogisticRegression
• Version: current
• More advanced to Read: S2-LogisticRegression
• Notes to Read: compare classifiers
• Video: M1 + M2

Study Guide: Logistic Regression and Bayes Classifiers

Short-Answer Quiz

Instructions: Answer the following questions in 2-3 sentences each, based on the provided source context.

1. What is the primary goal of a Bayes classifier when presented with a new data sample?
2. Explain the fundamental difference between discriminative and generative classifiers.
3. What is the core principle of Maximum Likelihood Estimation (MLE) for determining model parameters?
4. Describe the concept of “log-odds” or the “logit” function in the context of logistic regression.
5. How does the Bernoulli distribution serve as a conceptual model for the target variable in logistic regression?
6. In logistic regression, what is the decision boundary and what is its geometric shape?
7. Describe the two main stages of logistic regression when viewed as a single “neuron” or block.
8. What is the Expected Prediction Error (EPE) and how does a 0-1 loss function lead to the Bayes classifier rule?
9. Why is it often more convenient to work with the log-likelihood function rather than the likelihood function itself during MLE?
10. Briefly compare Newton’s method to Gradient Descent for optimization.

Answer Key

1. The primary goal of a Bayes classifier is to predict the class of a new data sample x. It achieves this by finding the class C that maximizes the posterior probability p(C

   x), a principle known as the Maximum A Posteriori (MAP) rule.

2. Discriminative classifiers, such as logistic regression and neural networks, directly estimate a decision rule or boundary to separate classes. In contrast, generative classifiers, like Naïve Bayes, build a statistical model of how the data for each class is generated and use that model to make predictions.

3. Maximum Likelihood Estimation (MLE) is a method for estimating the unknown parameters of a model. The core principle is to choose the set of parameters that are most likely to have produced the observed data set. This is achieved by maximizing the joint probability, or likelihood, of the observed samples.

4. **The “log-odds,” or “logit” function, is the natural logarithm of the odds P(y

   x) / (1-P(y

   x)).** In logistic regression, this logit is modeled as a linear function of the input features (x), forming the core representation of the model: ln[p/(1-p)] = β₀ + β₁x₁ + … + βₚxₚ.

5. Logistic regression is suitable for target variables coded as 0 or 1. The Bernoulli distribution, which models binary outcomes like a coin flip, is used to conceptually model this target variable. The probability parameter p of the Bernoulli distribution is not fixed but is instead modeled as a function of the input features, p = p(y=1

   x).

6. The decision boundary in logistic regression is the point where the log-odds equation equals zero, which corresponds to a probability of 0.5. Because the log-odds are modeled as a linear function of the features, the resulting decision boundary is also linear.

7. When viewed as a single block or “neuron,” logistic regression consists of two stages. The first is a summing function that calculates a weighted sum of the inputs (z = wᵀx + b). The second stage is the application of a sigmoid function (y = sigmoid(z)), which squashes the output of the summing function to a value between 0 and 1, representing a probability.

8. Expected Prediction Error (EPE) is the expected value of a loss function over the joint distribution of inputs and outputs. When using a 0-1 loss function, which penalizes any misclassification, minimizing the EPE is equivalent to choosing the class with the maximum posterior probability, which is precisely the MAP rule used by the Bayes classifier.

9. Working with the log-likelihood function is convenient because the joint probability of independent samples is a product of individual probabilities. Taking the logarithm transforms this product into a sum (log(Π P) = Σ log(P)), which is mathematically simpler to differentiate and maximize.

10. Both are optimization algorithms. Gradient Descent (GD) uses a first-order approximation to update parameters. In contrast, Newton’s method uses a second-order (quadratic) Taylor series approximation, incorporating curvature information via the Hessian matrix, which often allows it to find a more direct route to the minimum.

Essay Questions

Instructions: Formulate detailed responses to the following questions, synthesizing information from across the source material.

1. Synthesize the five different “views” of logistic regression presented: (I) logit as a linear function, (II) Y as a Bernoulli variable, (III) the “S” shape sigmoid function, (IV) a linear classification boundary, and (V) a two-stage neuron model. How do these perspectives complement each other to provide a comprehensive understanding of the model?

2. Discuss the role of Maximum Likelihood Estimation (MLE) in training a logistic regression model. Trace the process from defining the likelihood for a basic Bernoulli trial to deriving the conditional log-likelihood function for the entire logistic regression training set.

3. Explain the concept of the MAP (Maximum A Posteriori) rule within the framework of Bayes classifiers. How is this rule justified by the principles of Statistical Decision Theory and the minimization of Expected Prediction Error (EPE) with a 0-1 loss function?

4. Compare and contrast the three major groups of classifiers: discriminative, generative, and instance-based. Provide examples of each and explain where logistic regression fits within this taxonomy and why.

5. Describe the optimization challenge in fitting a logistic regression model. Compare the second-order Newton’s method with the first-order Stochastic Gradient Descent (SGD) method, discussing their respective approaches, requirements (e.g., first and second derivatives), and characteristics.

Glossary of Key Terms

NN and Deep Learning

• Lecture: S2-deepNNBasics
• Version: current
• Notes to Read: DNN Cheatsheets
• Video: M1+ M2+ M3

Neural Networks and Backpropagation: A Study Guide

Quiz: Short-Answer Questions

Answer each question in 2-3 sentences based on the provided source material.

1. How can a single neuron be conceptualized as an extension of logistic regression?
2. What was the historical Perceptron, and what type of activation function did it use?
3. Describe the structure of a Multi-Layer Perceptron (MLP). What makes a neural network “deep”?
4. What is the purpose of the Softmax function, particularly in the context of multi-class classification?
5. Identify two different types of loss functions mentioned in the text and the tasks they are suited for.
6. What is the core purpose of the backpropagation algorithm in training a neural network?
7. Briefly describe the two main phases of the training loop for a neural network using backpropagation.
8. What problem can occur with gradient magnitudes during training, and why is divergence considered the worse outcome?
9. What is “Dropout” and how does it function as a regularization technique?
10. Explain the concept of Batch Normalization and its benefits for the training process.

Answer Key

1. A single neuron can be seen as an expanded logistic regression unit. It performs a two-stage process: first, a summing function calculates a weighted sum of the inputs plus a bias (z = wᵀ · x + b), and second, a non-linear activation function (like sigmoid) “squashes” the result into a desired range.

2. The Perceptron, first proposed by Rosenblatt in 1958, was a simple one-neuron unit used to classify input into one of two categories. It used a step function as its activation function, which outputs +1 if the input is greater than or equal to zero and -1 otherwise.

3. A Multi-Layer Perceptron (MLP), or a feed-forward neural network, is composed of an input layer, one or more hidden layers, and an output layer. A neural network is considered “deep” when it contains many hidden layers.

4. The Softmax function is a normalizing function used as the final layer for multi-class classification. It converts the output of each class unit into a probability, ensuring that the sum of all output probabilities is equal to 1.

5. The text describes Sum of Squared Errors (SSE) loss, which is suitable for regression tasks, calculating (y₁-ŷ₁)²+(y₂-ŷ₂)². It also details the Cross-Entropy loss function (also called negative log-likelihood), which is used for binary and multi-class classification tasks.

6. The backpropagation algorithm is used to learn the optimal weights for a neural network by jointly optimizing all parameters. It accomplishes this by calculating the gradient of the loss function with respect to each weight in the network, even those in lower layers.

7. The first phase is the “Forward” pass, where inputs are fed through the network layer by layer to compute the final output and the loss. The second phase is the “Backward” pass, where the algorithm propagates local gradients from the final loss function back through the network to calculate each layer’s gradient for weight updates.

8. During training, gradients can become too big, leading to divergence, or too small, leading to slow convergence. Divergence is considered much worse because the training process fails to find a solution, whereas slow convergence simply takes more time.

9. Dropout is a regularization technique where some neurons are randomly set to zero during the forward pass of training. This process is akin to training a large ensemble of models that share parameters, which helps prevent overfitting.

10. Batch Normalization is a technique that standardizes the activations of a prior layer, which stabilizes and speeds up training. It improves gradient flow, allows for higher learning rates, reduces dependence on initialization, and acts as a form of regularization.

Essay Questions

Consider the following questions to synthesize the concepts from the course material. Formulate a detailed, evidence-based response for each.

1. Explain the journey from Logistic Regression as a linear classifier to a Multi-Layer Perceptron capable of modeling non-linear decision boundaries. How do hidden layers and non-linear activation functions enable this capability?

2. Describe the complete process of training a neural network for multi-class classification using Mini-batch Stochastic Gradient Descent (SGD) and backpropagation. Detail the roles of the forward pass, the Softmax layer, the cross-entropy loss function, the backward pass, and the weight update step.

3. Compare and contrast the four primary activation functions presented in the material: sigmoid, tanh, softplus, and rectify (ReLU). Discuss their mathematical forms, their derivatives, and the potential implications of these properties on the training process.

4. Discuss the importance of proper network initialization and regularization in deep learning. Using the concepts of Xavier initialization, Batch Normalization, and Dropout, explain how practitioners can avoid common training pitfalls like poor gradient flow and overfitting.

5. From a “block view,” a neural network can be seen as a series of differentiable, parameterized functions. Explain how the chain rule of calculus is the fundamental mathematical principle behind backpropagation, allowing gradients to be passed “backward” through these blocks to update parameters in the earliest layers of the network.

Glossary of Key Terms

CNN

• Lecture: S2-deepImageCNN
• Version: current
• More advanced to Read: S2-PCA
• Notes to Read: Keras notebook + another Keras Kaggle notebook
• Video: M1+ M2

Notebooks to run and experienc:

• L13 Keras notebook
• another Keras Kaggle notebook

Study Guide: Supervised Image Classification and Convolutional Neural Networks

Quiz

Answer the following questions in 2-3 sentences each, based on the provided lecture context.

1. What were the primary challenges that led to the “Winter of Neural Networks” around the 2000s?
2. Explain the three key properties of images that Convolutional Neural Networks are specifically designed to leverage.
3. What is the core function of a “filter” in a convolutional layer, and what property of images does it relate to?
4. Describe the concept of “translation invariance” and explain how a CNN achieves it.
5. What is the purpose of the Max Pooling operation in a CNN?
6. How does a convolutional layer differ from a fully-connected layer in terms of parameter usage?
7. What are the three main components of a dataset used for model selection and assessment in a “data-rich scenario”?
8. According to the lecture, who invented the CNN and in what year was the foundational paper published?
9. What happens to the output of the convolutional and max pooling layers before it is fed into a fully connected feedforward network?
10. In the context of a tabular dataset for classification, what are the three main types of columns identified in the lecture?

Answer Key

1. The “Winter of Neural Networks” was caused by several challenges. The optimization problem was non-convex, requiring many tricks for tuning hyperparameters like the number of layers and hidden units. Additionally, these networks were hard to analyze theoretically, and large labeled datasets were rare during that period.

2. CNNs leverage three key properties of images. The first is Locality, where patterns are smaller than the whole image. The second is Translation Invariance, meaning the same patterns can appear in different regions. The third is that Subsampling the pixels will not change the object, allowing the image to be made smaller.

3. A filter in a convolutional layer is a matrix of parameters (weights) designed to detect a small, specific pattern in the input image, such as an edge or a curve. This directly relates to the property of Locality, as the filter does not need to see the whole image to discover its target pattern.

4. Translation invariance is the principle that an object’s appearance is independent of its location within an image. A CNN achieves this through weight sharing, where the same set of filter parameters is applied across all regions of the image to detect a specific pattern regardless of where it appears.

5. The purpose of the Max Pooling operation is to subsample the feature map created by the convolutional layer. It reduces the spatial dimensions of the data, which makes the image smaller and results in fewer parameters for the network to process in subsequent layers.

6. A convolutional layer uses significantly fewer parameters than a fully-connected layer. This is because its neurons are only connected to a small local region of the input (locality) and it reuses the same parameters across the entire image (weight sharing), whereas every neuron in a fully-connected layer connects to every input from the previous layer.

7. In a data-rich scenario, the dataset is split into three parts for model selection and assessment. These are the Training set, the Validation set, and the Test set.

8. The Convolutional Neural Network (CNN) was invented by Professor Yann LeCun. The foundational paper, “Gradient-based learning applied to document recognition,” was published in 1998.

9. After the final max pooling layer, the resulting multi-channel, smaller image (a 3-D tensor) is processed by a Flatten operation. This converts the 3-D data into a one-dimensional vector, which can then be used as input for the subsequent fully connected feedforward network.

10. For a tabular dataset, the columns are identified as Features (also called attributes, predictors, or independent variables), which are all columns except the last. The last column is the Target (also called outcome, label, or dependent variable), which is the special column to be predicted. The rows are referred to as Data points or instances.

Essay Questions

Develop a detailed, essay-format response for each of the following prompts. No answers are provided for this section.

1. Trace the historical evolution of artificial intelligence and machine learning from Alan Turing’s 1950 paper to the landmark 2012 paper on ImageNet classification. Discuss the key milestones, influential figures, dominant technologies of each era (e.g., expert systems, SVMs), and the factors that contributed to the “Winter of Neural Networks.”

2. Provide a comprehensive explanation of the complete architecture of a standard CNN for image classification, as described in the lecture. Detail the journey of an input image through the network, explaining the purpose and mechanics of the Convolution layer, Max Pooling layer, Flatten operation, and the final Fully Connected network with softmax.

3. Elaborate on the three fundamental properties of images that make CNNs more effective than traditional Multilayer Perceptrons (MLPs) for image-related tasks. For each property (Locality, Translation Invariance, and Subsampling), explain what it is and which specific CNN mechanism (e.g., filters, weight sharing, pooling) is designed to exploit it.

4. Compare and contrast the processes of “Model Selection” and “Model Assessment.” Describe the different strategies available for these processes, such as the train/validation/test split for data-rich scenarios and methods like Cross-Validation for when data is insufficient.

5. Using the provided example of a 6x6 image and a 3x3 filter, explain the mathematical process of convolution. Describe how applying the filter across the image generates a “feature map” and how parameters like stride can alter the dimensions of this output.

Glossary of Key Terms

Huggingface

• Lecture: S3-hf-intro-2025-1016
• Version: current
• Notes to Read: S2-L0-pytorch
• Video: M1

Quick recap

The meeting covered an overview of Hugging Face’s model components and task interface, including demonstrations of how to explore models, datasets, and demo applications through the platform. Guangzhi provided detailed instructions on working with datasets in pipelines and using Hugging Face models through the Transformers library, including guidance on accessing model cards and recommended usage. The session concluded with a demonstration of a web-based demo application that enables real-time interaction with AI models through a graphical user interface, showcasing capabilities like text generation and image synthesis without requiring local resources.

Summary

Understanding Hugging Face Task Interface

Guangzhi explained the components of models, including architecture and learned parameter weights, and emphasized the importance of tasks, which vary based on input types like text or images. He demonstrated how Hugging Face’s task interface, accessible via AgentPase.co/task, categorizes tasks into natural language processing, computer vision, audio, and multimodal categories, with examples like any-to-any tasks. Guangzhi highlighted the overlap between datasets and other components in Hackerface and showed how users can explore models, datasets, and demo apps relevant to specific tasks.

Dataset Loading and Exploration

Guangzhi explained how to load and work with datasets in a pipeline, focusing on an any-to-any task dataset. He demonstrated how to use the dataset viewer to understand the data structure, including subsets and splits, and showed examples of loading datasets using the datasets package. Guangzhi also covered how to read instances from a loaded dataset by indexing and slicing, and he provided examples of accessing specific columns and labels.

Hugging Face Model Usage Tutorial

Guangzhi demonstrated how to use Hugging Face models, focusing on downloading and using models through the Transformers library. He explained how to access model cards, which provide basic information about models, and showed how to use the “Use This Model” button to download necessary files. Guangzhi also discussed using pipelines for higher-level tasks and emphasized the importance of checking model cards for recommended usage. Dr. asked about different ways to use models beyond the Hugging Face library, and Guangzhi confirmed that the Transformers library is a good starting point, with more advanced options available for experienced users.

AI Model Playground Demo

Guangzhi demonstrated a web-based demo application that allows users to interact with AI models directly through a graphical user interface without downloading the models. Dr. explained that the application consists of a frontend interface and a backend Hugging Face server, enabling real-time model interactions similar to ChatGPT. They discussed how the application serves as a useful playground for exploring model capabilities, with Guangzhi showing examples of text generation and image synthesis tasks that can be performed without requiring local resources.

pyTorch + Keras

• Lecture: S2-L0-Keras
• Version: current
• Notes to Read: S2-L0-pytorch

PCA, Feature Selection

• Lecture: S2-dimReduce
• Version: current
• More advanced to Read: S2-PCA
• Notes to Read: Great PCA Video + PCA Notebook
• Extra Notes to Read: UMAP
• Video: M1

• Notebook to try:

PCA Notebook

Study Guide: Dimensionality Reduction and PCA

running notebook

PCA Notebook

Short-Answer Quiz

Instructions: Answer the following questions in 2-3 sentences based on the provided source material.

1. What is the “Curse of Dimensionality,” and what is its practical effect on machine learning models?
2. Define the two primary methods of dimensionality reduction: feature extraction and feature selection.
3. Describe the three main approaches to feature selection discussed in the text.
4. What is the main objective of Principal Component Analysis (PCA), and what property of the data does it seek to maximize in its projections?
5. What are the two core components of an autoencoder, and what is its primary function in the context of feature learning?
6. When using PCA to project data onto a single line, what is the formal algebraic goal?
7. How are eigenvalues related to their corresponding principal components (eigenvectors) in terms of explaining the data’s structure?
8. List two criteria used to determine how many principal components should be retained after performing PCA.
9. Explain a scenario where the direction of maximum variance found by PCA might not be optimal for a classification task.
10. Briefly outline the process of using the “Eigenfaces” technique for face recognition.

Answer Key

1. The “Curse of Dimensionality” refers to the issue where the number of training examples required for a model increases exponentially with the number of features (dimensionality). In practice, including more features does not always improve accuracy and can lead to worse performance.

2. Feature extraction finds a new set of features by applying a mapping function to the existing features. Feature selection, in contrast, chooses a subset of the original, existing features without creating new ones.

3. The three approaches are Filtering, Wrapper, and Embedded. The Filtering approach ranks features independently of the predictor; the Wrapper approach uses a predictor to assess feature subsets; and the Embedded approach uses a predictor that internally selects a subset of features as it builds a single model.

4. The objective of PCA is to approximate a high-dimensional dataset with a lower-dimensional linear subspace. It achieves this by finding new axes (principal components) in the directions of the greatest variability, thereby maximizing the variance of the projected data.

5. An autoencoder consists of an encoder, which compresses the input into a lower-dimension latent space, and a decoder, which reconstructs the input from that latent space. Its function is to train the hidden layer units to become good and reliable feature detectors by minimizing the reconstruction loss between the original input and the reconstructed output.

6. The formal algebraic goal is to find a line (direction vector v) that maximizes the sum of squares of the data samples’ projections onto that line. This is equivalent to finding the eigenvector v associated with the largest eigenvalue λ of the matrix XᵀX.

7. The principal components (eigenvectors) are the new, uncorrelated features derived by PCA. The variance of the data along each principal component vₖ is equal to its corresponding eigenvalue λₖ, meaning that PCs with small eigenvalues correspond to directions of small variance in the data.

8. One method is to keep enough PCs to explain a cumulative variance greater than a certain threshold, such as 50-70%. A second method is to use a “Scree plot,” which visualizes the variance explained by each PC, and keep only the components with eigenvalues above a certain value (e.g., >1).

9. The direction of maximum variance is not always good for classification. For example, with two distinct classes represented as ellipsoidal Gaussian densities, the first principal component may capture the overall data trend, while the second, less significant component may be the one that best discriminates between the two classes.

10. The Eigenfaces technique first computes the principal components (“eigenfaces”) from a set of training face images. All training images are then projected into this new, lower-dimensional “face space.” A novel image is classified by projecting it into the same space and finding the nearest neighboring training face based on the distance between their low-dimensional coefficients.

Essay Questions

Instructions: The following questions are designed for a more in-depth, essay-style response. Answers are not provided.

1. Compare and contrast the three primary feature selection strategies: Filtering, Wrapper, and Embedded. Discuss the relative advantages and disadvantages of each in terms of computational cost, model dependency, and optimization for a specific learning algorithm.

2. Elaborate on the “Curse of Dimensionality” using the specific examples cited in the text (QSAR drug screening, Leukemia Diagnosis, and Text Categorization). Explain how high-dimensional feature spaces in these domains necessitate dimensionality reduction and what benefits are gained from applying these techniques.

3. Provide a detailed explanation of the mathematical and algebraic interpretation of Principal Component Analysis. Describe the roles of the centered data matrix, the covariance matrix, eigenvalues, and eigenvectors in the process of identifying the principal components that capture maximum variance.

4. Using the “Eigenfaces” method as a case study, describe the end-to-end application of PCA for image recognition. Explain how a high-dimensional image is transformed into a low-dimensional representation, how this representation is used for classification, and what information is potentially lost or preserved in this process.

5. Discuss the limitations of PCA. Explain why its objective of maximizing variance may not align with the objective of maximizing class separability in a supervised learning context, and illustrate with the examples provided in the source material.

Glossary of Key Terms

Feature Selection

• Lecture: S3-feaSelc
• Version: current
• Notes to Read: S3-QuizReview + ELS Ch3.4 and Ch3.3 + API
• Video: (Extra M2 + M3 )

Study Guide: Feature Selection in Machine Learning

The Purpose and Benefits of Feature Selection

In machine learning, datasets can contain thousands or even millions of low-level features. Feature selection is the process of selecting a subset of p’ original features from a total of p features. The primary goal is to identify the most relevant features to build better learning models for tasks like classification and regression.

This process yields several significant benefits:

1. Improved Generalization: Models with fewer, more relevant features are less sensitive to noise and tend to have lower variance. This aligns with Occam’s Razor (the law of parsimony).
2. Computational Efficiency: Fewer features reduce training and inference cost and often require fewer labeled examples.
3. Enhanced Interpretability: Simpler models are easier to understand and explain, important for trust and transparency.

Core Methodologies for Feature Selection

There are three primary approaches to feature selection, each differing in how they interact with the learning algorithm.

1. The Filter Approach

Filter methods select features as a pre-processing step, independently of the classifier. They include univariate and multivariate techniques.

Univariate Filtering

• Pearson Correlation: Measures linear correlation between a feature and the target (range [-1, 1]); detects only linear dependencies.
• T-test: Tests whether a feature distinguishes two classes (assumes normality and equal variance). Null hypothesis H0: class means are equal; T-statistic measures significance of mean difference.

Multivariate Filtering

Methods consider multiple variables jointly to capture interactions missed by univariate methods.

Core challenges:

1. Scoring Function: Measure the quality of a subset.
2. Search Strategy: Explore the 2^p possible subsets efficiently.

Finding the minimal optimal subset is NP-hard; good heuristics are essential.

2. The Wrapper Approach

Uses the predictive performance of a specific learner (treated as a black box) to score feature subsets.

Two key questions:

• (a) Assessment: How to measure performance?
  • Split into train/validation/test. Train on train, score on validation, choose best subset; optionally use cross-validation; assess final model once on test.
• (b) Search: How to explore 2^p subsets?
  • Heuristics:
    • Forward Selection: Start empty; add features iteratively.
    • Backward Elimination: Start full; remove features iteratively.
    • Advanced: Beam search, GSFS, PTA(l,r), floating search.

Main criticism: high computational cost due to repeated training/evaluation.

3. The Embedded Approach

Integrates selection into training a single model; selection occurs implicitly.

• Key Characteristics: Learner-specific.
• Example: L1-regularization shrinks many coefficients to zero, selecting features.

Feature Selection vs. Feature Extraction

• Feature Selection: Selects a subset of original features
  (X1, …, Xp → Xk1, …, Xkp’); features remain unchanged.
• Feature Extraction / Dimensionality Reduction: Creates new features as (possibly weighted) combinations of originals
  (X1, …, Xm → g1(X), …, gp’(X)).

Example: Principal Component Analysis (PCA) finds a linear mapping to a lower-dimensional space that maximally preserves variance; principal components are combinations of original features.

Model Selection and Assessment

Feature selection is tied to broader tasks of model selection and assessment.

• Model Selection: Estimate performance to choose the best model (e.g., hyperparameters or feature subset).
• Model Assessment: Estimate the chosen model’s prediction error on unseen data.

Data Handling Strategies

• Data-Rich Scenario: Split into train (build), validation (select), test (final assess).
• Insufficient Data: Use cross-validation or bootstrap; or analytical approximations (AIC/BIC) to mimic validation.

Review Quiz

Answer the following questions in 2-3 sentences each based on the provided material.

1. What is the primary objective of feature selection in machine learning?
2. According to the text, what are the three main benefits of applying feature selection?
3. Explain the fundamental difference between the Filter and Wrapper approaches.
4. What is a major limitation of univariate filtering methods like the Pearson Correlation?
5. Why is the task of finding a minimal optimal feature subset described as NP-hard?
6. In the Wrapper approach, what are the distinct roles of the training, validation, and test data sets?
7. Describe the core ideas behind the Forward Selection and Backward Elimination search strategies.
8. How does the Embedded approach to feature selection differ from both Filter and Wrapper methods?
9. Distinguish between Feature Selection and Feature Extraction, using Principal Components Analysis (PCA) as an example.
10. What is the purpose of model selection, and how does it differ from model assessment?

Answer Key

1. Objective: Select a subset of the most relevant original features to build models that are better, faster, and more interpretable for classification or regression.
2. Benefits: Improved generalization (lower variance, less noise sensitivity); computational efficiency (faster training/inference); enhanced interpretability (more explainable).
3. Filter vs Wrapper: Filter ranks/selects features independently of the learner as pre-processing; Wrapper uses the performance of a specific learner to score feature subsets.
4. Limitation of Univariate Filtering: Detects only linear, single-feature relationships; may miss features useful only in combination.
5. NP-hardness: With p features, there are 2^p subsets; exhaustive search is infeasible, requiring heuristics.
6. Data splits: Train to fit predictors per subset; Validation to select the best subset; Test used once for final unbiased performance estimate.
7. Search strategies: Forward Selection adds features iteratively from empty; Backward Elimination removes features iteratively from full.
8. Embedded: Selection is integrated into model training (learner-specific), unlike separate pre-processing (Filter) or external evaluation loops (Wrapper).
9. Selection vs Extraction: Selection keeps original features; Extraction creates new features (e.g., PCA components) as combinations that preserve variance.
10. Model Selection vs Assessment: Selection chooses the best model via validation; Assessment estimates final generalization on unseen data (test set).

Essay Questions

Formulate comprehensive responses for each:

1. Discuss Occam’s Razor and its relationship to the three primary goals of feature selection.
2. Compare univariate vs. multivariate Filter methods; give a scenario where multivariate succeeds but univariate fails.
3. With millions of features and limited compute, which approach (Filter, Wrapper, Embedded) would you choose and why? Discuss trade-offs.
4. Explain the inherent “search problem” in feature selection. Describe three heuristic strategies and when each is preferable.
5. Detail the complete Wrapper process with emphasis on data splitting. Why separate validation and test sets to avoid bias?

Glossary of Key Terms

Section 3 - Deep on 1D Sequence Type (e.g. Language Text)

Prob Review

• Lecture: S3-ProbReview
• Version: current
• Video: M1 + M2

Recent deep learning on Text

• Lecture: S3-deepNNtext
• Version: current
• Notes to Read: Keras Notebook on DNN text
• Video: M1 + M2 + M3

• Notebook to try:

L15 Keras Notebook on DNN text

In this lecture, we cover:

• What is NLP?
• Typical NLP tasks / Challenges / Pipeline
• f() on natural language
  • Before Deep NLP (Pre 2012) • (BOW / LSI / Topic Modeling LDA )
  • Word2Vec (2013-2016) • (GloVe/ FastText)
  • Recurrent NN (2014-2016) • LSTM
  • Seq2Seq
  • Attention
  • Self-Attention (2016 – now )
  • Transformer (attention only Seq2Seq)
  • BERT / RoBERTa/ XLNet/ GPT-2 / …

Study Guide: Deep Neural Networks for Natural Language Processing

Quiz: Short-Answer Questions

Instructions: Provide a concise answer (2-3 sentences) for each of the following questions based on the provided course material.

1. What is Natural Language Processing (NLP) and what fundamental goal does it aim to achieve beyond simple keyword matching?
2. Identify and briefly describe three major challenges that researchers and engineers face in the field of Natural Language Processing.
3. Explain the “Bag of Words” (BOW) representation and identify its two primary limitations for many NLP tasks.
4. What is the “one-hot vector” method for representing words, and what are its main drawbacks?
5. Describe the core characteristic of Recurrent Neural Networks (RNNs) and explain how this feature makes them suitable for processing sequence data.
6. Explain the purpose of the Encoder and Decoder components within a Seq2Seq architecture for a task like machine translation.
7. What is the core idea behind the “Attention Mechanism” in sequence-to-sequence models?
8. How does the Transformer model’s architecture fundamentally differ from that of a Recurrent Neural Network?
9. Describe the Masked Language Model (MLM) pre-training objective used by BERT.
10. Differentiate between the CBOW and SkipGram models within the Word2Vec framework.

Answer Key

1. Natural Language Processing (NLP) is a field of computer science, AI, and computational linguistics focused on the interaction between computers and human languages. Its goal is to go beyond simple keyword matching to identify the structure and meaning of words and sentences, enabling a deep understanding of broad language.

2. Three major challenges in NLP are ambiguity, such as pronoun references; the fact that language is not static and constantly changes with new slang or “cyber lingo”; and the immense scale of language data, with sources like Wikipedia containing billions of words.

3. The Bag of Words (BOW) is a method that represents text by counting the occurrences of each word, such as f()=c great 2 love 2. Its primary limitations are that it removes all word position information and cannot effectively represent word compositions.

4. The “one-hot vector” is a binary vector with a length equal to the vocabulary size, where a ‘1’ is placed in the position corresponding to a word’s ID and the rest are ‘0’s. Its main drawbacks are its extremely high dimensionality, its sparsity, and its inability to represent a word’s meaning.

5. Recurrent Neural Networks (RNNs) are networks containing loops, which allow information to persist. This structure enables them to operate over sequences of vectors with variable lengths, using recent history and current input to model dynamic temporal dependencies.

6. In a Seq2Seq architecture, the Encoder is an RNN that encodes an input sentence (e.g., in a source language) into a hidden state or feature vector. The Decoder is another RNN that takes this hidden state as input and generates the output sequence (e.g., the translated sentence).

7. The Attention Mechanism provides a weight for each input word for every single output timestep. This allows the model to create a context vector (C1) that is a weighted sum of the hidden encodings from the input, effectively letting the model focus on the most relevant parts of the input sequence when generating an output.

8. The Transformer model’s architecture is fundamentally different because it contains no recurrence. Instead of processing sequences step-by-step like an RNN, it relies entirely on self-attention mechanisms to map a sequence to itself.

9. The Masked Language Model (MLM) is a pre-training objective where some input tokens are masked with a unique [MASK] token. The model is then trained as a denoising autoencoder to predict these original masked tokens based on their surrounding context.

10. In Word2Vec, the Continuous Bag-of-Words (CBOW) model predicts the current input token based on its surrounding context tokens. Conversely, the SkipGram model does the opposite, predicting the surrounding context tokens based on the current input token.

Essay Questions

Instructions: Prepare a detailed, essay-format response for each of the following prompts. (Answers not provided).

1. Trace the evolution of natural language representation in machine learning as outlined in the course material, beginning with pre-2012 methods like Bag of Words and culminating in modern approaches like Transformer-based contextual embeddings. Discuss the key innovations and limitations at each major stage (BOW, Word2Vec, RNN/LSTM, Transformers).

2. Compare and contrast the architectural philosophies of Recurrent Neural Networks (like LSTM) and Transformer models for processing sequential data. What are the fundamental differences in how they handle sequences, and what specific advantages did the introduction of self-attention in Transformers provide over recurrence?

3. Discuss the primary challenges inherent in Natural Language Processing, specifically ambiguity, scale, and the dynamic nature of language. Using examples from the source, explain how modern deep learning approaches attempt to address these challenges more effectively than classic NLP pipeline components.

4. Explain the concept of the Seq2Seq (Encoder-Decoder) architecture and its wide range of applications in generative NLP tasks. How does the integration of an attention mechanism enhance the performance and interpretability of these models, particularly in a complex task like machine translation?

5. The source mentions several landmark pre-trained models, including BERT, ALBERT, and XLNet. Describe the concept of pre-training and fine-tuning. Explain the specific training innovations introduced by ALBERT (Sentence Order Prediction) and XLNet (Permutation Language Model) as attempts to improve upon the original BERT framework.

Glossary of Key Terms

Generative Classification

• Lecture: S3-GenerativeBayesClassify
• Version: next
• Notes to Read: text NBC notebook
• Video: M1 + M2 + (Extra M3 )

• Notebook to run:

L16 text NBC notebook

Study Guide for Generative Bayes Classifiers

This study guide provides a review of the core concepts related to Generative Bayes Classifiers, as detailed in the source material. It includes a short-answer quiz to test comprehension, a set of essay questions for deeper analysis, and a comprehensive glossary of key terms.

Quiz: Short-Answer Questions

Instructions: Answer the following ten questions based on the provided source material. Each answer should be approximately two to three sentences.

1. What are the three major types of classification approaches described in the material?
2. What is the fundamental goal of a Bayes Classifier when presented with a new data sample for testing?
3. Explain the primary difference between a generative and a discriminative probabilistic model for classification.
4. What is the core “naïve” assumption of the Naïve Bayes Classifier, and why is it crucial for the model’s functionality?
5. How does the Naïve Bayes conditional independence assumption affect the number of parameters the model needs to learn?
6. Describe the learning or training phase for a Naïve Bayes Classifier that handles discrete input attributes.
7. What is the Maximum A Posteriori (MAP) rule, and what role does it play in Generative Bayes Classifiers?
8. When using maximum likelihood estimates for training, what significant problem can arise if the training data is not perfectly representative?
9. What is the purpose of “smoothing” in the context of training a Naïve Bayes model?
10. According to the “Play Tennis” example, how many parameters were required for a general Generative Bayes Classifier compared to a Naïve Bayes Classifier?

Answer Key

1. The three major types of classification approaches are Discriminative classifiers, which directly estimate a decision boundary (e.g., SVM); Generative classifiers, which build a statistical model for the data (e.g., Naïve Bayes); and Instance-based classifiers, which use observations directly without a model (e.g., K-nearest neighbors).

2. The goal of a Bayes Classifier during testing is to predict the class for a given sample x. Specifically, it seeks to find the class c that maximizes the posterior probability p(c

   x1, x2, …, xp).

3. A generative model builds a statistical model for each class, modeling the class-conditional probability P(X

   C) and the prior probability P(C). A discriminative model, in contrast, directly estimates the posterior probability P(C

   X) or learns a direct mapping from inputs to class labels without modeling the underlying data distribution.

4. The core assumption is that all input attributes (features) are conditionally independent of one another, given the class. This assumption is crucial because it simplifies the problem of estimating the joint probability P(X1, …, Xp

   C) by allowing it to be calculated as the product of individual conditional probabilities P(Xi

   C).

5. The assumption dramatically reduces the number of parameters. Instead of estimating a parameter for every possible combination of attribute values (multiplicative complexity), the model only needs to estimate parameters for each attribute conditioned on the class (additive complexity), making it feasible to train with much less data.

6. The learning phase for a discrete Naïve Bayes Classifier involves estimating probabilities from the training data using frequencies (maximum likelihood estimates). For each class ci, the model estimates the prior probability P(C=ci), and for every attribute value xjk, it estimates the conditional probability P(Xj=xjk

   C=ci).

7. The MAP rule is a decision principle used to select the most probable class for a new instance. In Generative Bayes Classifiers, it means choosing the class cj that maximizes the product of the class-conditional probability P(x1, …, xp

   cj) and the prior probability P(cj).

8. If a specific combination of an attribute value and a class never appears in the training data, its maximum likelihood probability estimate will be zero. This “zero probability” can then nullify the entire posterior probability calculation for that class, regardless of the evidence from other attributes.

9. Smoothing is a technique used to avoid the problem of zero probabilities. It adjusts the counts used for probability estimation, for example, by adding a small value (like 1) to the numerator, which ensures that no estimated conditional probability is ever exactly zero.

10. For the “Play Tennis” example, the general Generative Bayes Classifier required estimating 72 parameters. In contrast, the Naïve Bayes Classifier, with its conditional independence assumption, only required the estimation of 20 parameters.

Essay Questions

Instructions: The following questions are designed to encourage a deeper synthesis of the source material. Answers are not provided.

1. Compare and contrast the standard Generative Bayes Classifier and the Naïve Bayes Classifier. Discuss the trade-offs between model complexity, data requirements, and the validity of underlying assumptions, using the “Play Tennis” dataset as a specific case study.

2. The source material frames classification as a process involving a Task, Representation, Score Function, and Search/Optimization. Elaborate on how each of these components is realized within the Naïve Bayes Classifier framework for discrete attributes.

3. Explain the mathematical justification for the Naïve Bayes classification rule. Begin with the primary goal of any Bayes Classifier, apply Bayes’ Rule, and then explicitly incorporate the conditional independence assumption. Conclude by explaining why the P(X) term from Bayes’ Rule can be disregarded during the final MAP classification step.

4. Discuss the “zero probability” problem in detail. Explain why this is a critical issue for models trained with maximum likelihood estimation and how the smoothing techniques presented in the source material provide a robust solution to avoid overfitting and improve model generalization.

5. While the document primarily focuses on discrete attributes, it briefly mentions Gaussian Naïve Bayes. Based on the fundamental structure of the Naïve Bayes model, hypothesize how a Gaussian Naïve Bayes classifier would differ from the discrete model in its learning (parameter estimation) and testing phases. What kind of feature data would this variant be suited for?

Glossary of Key Terms

NaiveBC on Text

• Lecture: S3-NBCtext
• Version: next
• Notes to Read: text NBC notebook
• Extra Notes to Read: Multinomial MLE
• Video: M1 + M2 + (Extra M3 + M4)

• Notebook to run:

L16 text NBC notebook

Study Guide: Naïve Bayes Classifier for Text Classification

Quiz: Short-Answer Questions

Instructions: Answer the following questions in 2-3 complete sentences, drawing only upon the provided course materials.

1. What is the core “naïve” assumption made by the Naïve Bayes classifier, particularly in the context of text classification?
2. Describe the “bag of words” representation for text documents and identify its primary simplifying assumption.
3. What are the two main probabilistic models discussed for applying the Naïve Bayes classifier to text, and how do their feature representations differ?
4. According to the materials, which of the two primary Naïve Bayes models is generally more effective for text classification tasks?
5. Explain the purpose of using log probabilities during the testing stage of a Naïve Bayes classifier.
6. How does Maximum Likelihood Estimation (MLE) determine the parameters for the Multivariate Bernoulli model?
7. In the Multinomial Naïve Bayes model, what is the concept of a “mega-document” and how is it used during training?
8. What is a primary strategy for handling out of vocabulary (OOV) or unknown words that appear in a test document but not in the training corpus?
9. Despite its simplifying assumption, why is the Naïve Bayes classifier considered robust and a good baseline model?
10. How can the Multinomial Naïve Bayes classifier be understood as a class-conditional unigram language model?

Answer Key

1. The core “naïve” assumption is that all input attributes are conditionally independent given the class. In text classification, this means that the appearance of one word in a document is assumed to be independent of the appearance of any other word, given the document’s topic or class.

2. The “bag of words” representation models a text document as a vector, where each dimension corresponds to a word in a dictionary. This vector can either contain the frequency of each word or a boolean value indicating its presence or absence. The model’s primary simplifying assumption is that word order is not important.

3. The two models are the Multivariate Bernoulli Naïve Bayes and the Multinomial Naïve Bayes. The Multivariate Bernoulli model uses binary features, representing each word as a boolean (true/false) value indicating whether it appears in the document. The Multinomial model uses integer features representing the frequency (count) of each word in the document.

4. The course materials state that the Multinomial model is “almost always more effective in text applications.” An experiment by M&N (1998) on classifying university web pages is cited as evidence supporting this conclusion.

5. Using log probabilities is a technique for underflow prevention. Multiplying many small probability values (which are between 0 and 1) can result in a number too small for standard floating-point representation. By summing the logs of the probabilities instead—since log(xy) = log(x) + log(y)—this numerical instability is avoided while preserving the ability to find the most probable class.

6. For the Multivariate Bernoulli model, Maximum Likelihood Estimation (MLE) is used to estimate the parameter P(word_i = true

   class_j). This is calculated as the fraction of documents belonging to class j in which word i appears. It is the relative frequency of a binary event (the word’s presence).

7. In the Multinomial model, a “mega-document” for a specific class is created by conceptually concatenating all training documents belonging to that class. The frequency of a word w in this mega-document is then used to calculate the probability P(w

   class) via MLE, which simplifies to the relative frequency of w across all words in all documents of that class.

8. A primary strategy is to train the model with an explicit symbol for an unknown word, such as . During preprocessing, words not in a pre-chosen vocabulary (or rare words) in the training corpus can be replaced with , allowing the model to learn a probability for it.

9. Naïve Bayes is considered a good baseline because it is very fast to train (one pass over the data) and test, has low storage requirements, and is robust to irrelevant features. For many text categorization tasks with numerous features, it performs well and was even a top performer in the KDD-CUP 97 competition.

10. The Multinomial model can be seen as a class-conditional unigram language model because it calculates the probability of a document by multiplying the probabilities of its individual words, given a class. This is equivalent to a unigram model (where each word’s probability is independent of others) where a separate set of word probabilities (a separate language model) is learned for each class.

Essay Questions

Instructions: Prepare a detailed, essay-format response for each of the following prompts.

1. Provide a comprehensive comparison of the Multivariate Bernoulli and Multinomial Naïve Bayes models for text classification. Discuss their underlying assumptions, how text documents are represented as features, the process for parameter estimation (MLE) in each, and the practical reasons one is often preferred over the other.

2. Explain the complete workflow for training and testing a Multinomial Naïve Bayes text classifier. Begin with raw text documents and a fixed set of classes, and detail the steps of text representation (including dictionary creation and the bag-of-words model), parameter estimation, and the final classification decision process for a new document.

3. Discuss the statement: “Naive Bayes is Not So Naive.” Elaborate on the strengths of the Naïve Bayes classifier that make it a powerful and dependable baseline for text classification, referencing its performance in competitions like KDD-CUP 97, its robustness to certain types of features, and its computational efficiency.

4. Describe the mathematical foundation of the Naïve Bayes classifier, starting from Bayes’ rule (argmax P(C

   X)). Explain how the “naïve” assumption of conditional independence simplifies the P(X

   C) term and makes computation tractable, especially for high-dimensional data like text.

5. What is a generative model in the context of classification? Explain how both the Multinomial and Multivariate Bernoulli Naïve Bayes classifiers can be viewed as generative models that approximate how a text document is produced, given a class label.

Glossary of Key Terms

Gaussian GBC

• Lecture: S3-GaussianGBC
• Version: next
• Notes to Read: Paper Discr vs. Genera
• Video: Extra M4

Quick survey of recent deep learning

• Lecture: S3-deepNNSurvey
• Version: next
• Notes to Read: DNN Cheatsheets
• Video: M1 + M2 + M3 + M4

Summary:

This lecture covers 10 deep learning trends that go beyond classic machine learning:

• 1. Popular CNN, RNN, Transformer models are not covered much here
• 1. DNN on graphs / trees / sets
• 1. NTM 4program induction
• 1. Deep Generative models/ DeepFake
• 1. Deep reinforcement learning

• 5 . Few-shots / Meta learning / AGI?

• 1. pretraining workflow / Autoencoder / self-supervised training
• 1. Generative Adversarial Networks (GAN) workflow
• 1. AutoML workflow / Learning to optimize /to search architecture
• 1. Validate / Evade / Test / Verify / Understand DNNs
• 1. Model Compression / Efficient Net

Disclaimer: it is quite hard to make important topics of deep learning fit on a one-session schedule. We aim to make the content reasonably digestible in an introductory manner. We try to focus on a modularity view by introducing important variables to digest deep learning into chunks regarding data/ model architecture /tasks / training workflows and model characteristics. We think this teaching style provides students with context concerning those choices and helps them build a much deeper understanding.

Briefing on Recent Trends in Deep Neural Networks

Executive Summary

This document synthesizes an overview of ten significant trends in Deep Neural Networks (DNNs), based on a lecture from the University of Virginia’s CS 4774 Machine Learning course. The analysis is structured around the “Deep Learning in a Nutshell” framework, which deconstructs the machine learning process into core components: Task, Representation (Topology), Score Function, Search/Optimization, Data, Models/Parameters, Hyperparameters/Metrics, and Hardware.

The key trends indicate that innovation in deep learning is occurring across this entire spectrum. Advancements are not limited to model architecture but also encompass the types of problems being solved, the methods used for training and optimization, and the practical challenges of deployment. The ten identified trends are:

1. Expanding Input Types: Moving beyond traditional grid-like data (images, sequences) to handle complex structures like graphs, trees, and sets.
2. Symbolic Reasoning: Employing architectures like Neural Turing Machines (NTMs) for tasks requiring program induction and manipulation of symbolic data.
3. Deep Generative Models: Creating realistic data for applications like image super-resolution, text-to-image synthesis, and DeepFakes, while also aiding in semi-supervised learning and handling missing data.
4. Deep Reinforcement Learning (RL): Enabling agents to learn complex behaviors from raw observations by maximizing reward signals, exemplified by AlphaGo’s success.
5. Meta-Learning and AGI: Shifting focus from narrow, task-specific AI towards “learning to learn” and the pursuit of Artificial General Intelligence (AGI), defined by autonomy and the ability to solve novel problems.
6. Self-Supervised Pre-training: Using autoencoders and reconstruction loss to pre-train network layers on unlabeled data, improving feature detection and mitigating training issues like vanishing gradients.
7. Generative Adversarial Networks (GANs): A powerful training workflow for generative tasks, with notable advancements seen in models like CycleGAN, Progressive GAN, and StyleGAN.
8. Automated Machine Learning (AutoML): Developing methods to automate the optimization process and the search for effective DNN architectures, reducing manual effort.
9. Robustness and Trustworthiness: A growing focus on understanding, verifying, and securing DNNs against adversarial attacks, as well as developing methods for model interpretation and bias detection.
10. Hardware Adaptation and Efficiency: Compressing large models for deployment on resource-constrained hardware like IoT and mobile devices, using techniques such as pruning, quantization, and filter decomposition.

The “Deep Learning in a Nutshell” Framework

The lecture organizes deep learning concepts and trends within a modular framework that breaks the field into its constituent parts. This structure provides a holistic view of where innovation is occurring.

Module I: Innovations in Representation and Architecture

This module focuses on trends related to the Representation component of the framework, specifically the types of data a DNN can process and the architectures designed for them.

Trend 1: DNNs for Graphs, Trees, and Sets

Deep learning is expanding beyond grid-structured data. New architectures are being developed to handle more complex and irregular data formats:

• Graph Neural Networks (GNNs) are used for graph data.
• Other specialized topologies are designed for tree and set-based inputs.

Trend 2: Symbolic Reasoning and Program Induction

This trend addresses tasks that require reasoning over symbolic inputs and outputs, such as computer programs.

• Neural Turing Machines (NTMs) are a key architecture in this area. An NTM combines a neural network controller with external memory, which it can read from and write to using “blurry” read/write heads. This enables it to handle tasks involving sequential symbolic forms and decision-making.

Foundational Architectures

The lecture also recaps foundational architectures that remain central to the field:

• Convolutional Neural Networks (CNNs): Highly effective for grid-like data. Applications mentioned include:
  • Image Processing: Standard use case.
  • Playing Go: A 19x19 game board is treated as an image to predict the next move.
  • Speech Processing: A spectrogram (representing frequency over time) is treated as an image, with filters moving in the frequency direction.
• Recurrent Neural Networks (RNNs), Attention, Seq2Seq, and Transformers: These architectures are dominant in natural language processing (NLP).
  • Notable Pre-trained Models: The source highlights ELMo (pre-trained biLSTM for contextual embeddings) and BERT (pre-trained transformer encoder for sentence embeddings) as significant examples.

Module II: Expanding the Scope of Solvable Tasks

This module explores trends related to the Task component, highlighting new types of problems that deep learning is being applied to.

Trend 3: Deep Generative Models

These models are designed to generate new, realistic data. Their applications and benefits include:

• Applications: Image Super-Resolution, Label-to-Image, Edges-to-Image, Text-to-Image, and DeepFakes (swapping faces in videos).
• Utility:
  • Testing the ability to handle high-dimensional probability distributions.
  • Simulating possible futures for planning or reinforcement learning.
  • Handling missing data and enabling semi-supervised learning.
  • Producing multi-modal outputs.

Trend 4: Deep Reinforcement Learning (RL)

Deep RL combines deep neural networks with reinforcement learning principles.

• Core Concept: An agent interacts with an environment, receiving raw observations (not hand-crafted states) and a scalar reward. It learns by taking actions to maximize this cumulative reward.
• AlphaGo Case Study: The success of AlphaGo is attributed to a learning pipeline that combines Supervised Learning (SL) and Reinforcement Learning (RL) to guide its Monte Carlo Tree Search:
  • SL Policy Network: Provides prior search probability.
  • Rollout: Conducts quick simulations on leaf nodes of the search tree.
  • Value Network: Evaluates the “global feeling” or state of a leaf node.
  • Subsequent work, referenced as “Mastering the Game of Go without Human Knowledge,” further advanced this approach.

Trend 5: Meta-Learning and the Pursuit of Artificial General Intelligence (AGI)

This trend focuses on “learning to learn” and moving beyond task-specific “Narrow AI.”

• Narrow AI: Models designed for specific tasks like game-playing, medical diagnosis, or car-driving.
• Artificial General Intelligence (AGI): Defined as “the ability to achieve complex goals in complex environments using limited computational resources.” Key characteristics of AGI include:
  • Autonomy.
  • Practical understanding of self and others.
  • Ability to understand “what the problem is,” not just solve problems posed by programmers.
  • Capability to solve problems unknown to its original programmers.

Module III: Evolving Training and Optimization Workflows

This module covers trends related to the Search/Optimization and Score Function components, focusing on new ways to train models effectively.

Trend 6: Self-Supervised Learning and Autoencoders

This approach involves training models on unlabeled data by creating a supervisory signal from the data itself.

• Autoencoders: An auto-encoder is trained to reproduce its input. The Reconstruction Loss (difference between input and output) forces the hidden layers to learn reliable and descriptive features.
• Unsupervised Pre-training: A layer-wise training workflow:
  1. Train the first hidden layer using a self-supervised loss, then fix its parameters.
  2. Repeat this process for subsequent layers, working bottom-up.
  3. After pre-training, perform Supervised Fine-tuning on labeled data to refine the learned features for the specific end-task.
• Benefits: This method helps overcome common DNN training challenges like non-convexity and vanishing gradients.

Trend 7: Generative Adversarial Networks (GANs)

GANs represent a specific training framework for generative models, involving a competition between a generator and a discriminator. Notable advanced GAN architectures cited include:

• CycleGAN: Translates characteristics between two image collections without paired examples (e.g., style transfer, object transfiguration).
• Progressive GAN: Improves quality, stability, and variation in generated images.
• StyleGAN: A generator architecture that produces high-quality images and achieves an unsupervised separation of high-level attributes (disentanglement).

Trend 8: Automated Machine Learning (AutoML)

AutoML aims to automate aspects of the machine learning pipeline, particularly optimization and architecture design.

• Key Focus: “Learning to Optimize” and “Learning to Search” for optimal DNN architectures.
• Example: “Neural Optimizer Search with Reinforcement Learning” is cited as a method for hyperparameter search.

Module IV: Addressing Deployment and Real-World Challenges

This final module addresses trends related to the practical deployment of DNNs, including robustness and hardware efficiency.

Trend 9: Trust, Robustness, and Interpretability

As DNNs are deployed in critical systems, ensuring their reliability and understanding their behavior has become paramount.

• Understanding DNNs:
  • Post-hoc Explanations: Methods like feature visualization and attribution to explain model decisions after training.
  • Inherently Interpretable Models: Designing models that are transparent by construction.
• Adversarial Examples (AE): DNNs can be fooled by adding imperceptible noise to inputs. The source provides an example where adding 0.007 * noise to an image of a “panda” causes a CNN to misclassify it as a “gibbon.”
• Verification: Formal methods are being developed to prove properties about DNN behavior, such as the “Reluplex” SMT solver for verifying networks.

Trend 10: Hardware-Aware DNNs and Model Compression

This trend is driven by the need to deploy powerful DNNs on resource-constrained hardware, such as the projected 20 billion connected IoT devices by 2020.

• Goal: Enable efficient edge inference for applications like language translation, speech recognition, and object detection on mobile and IoT devices.
• Model Compression Methods:
  • (a) Model Pruning: Removing redundant neurons, filters, or layers. Methods include magnitude-based pruning and Hessian-based pruning, often involving iterative pruning and retraining.
  • (b) Simpler Filter Construction: Using techniques like matrix factorization, singular value decomposition (SVD), and flattened convolutions.
  • (c) Quantization: Reducing the precision of weights, activations, and gradients using fixed-point formats or codebooks.

Section 4 - More Advanced Supervsied on Tabular Type

SVM

• Lecture: S4-SVM-basic
• Version: next
• Notes to Read: PCA+SVM Notebook
• Video: M1 + M2

• Notebook to Run: L14 PCA+SVM Notebook

Support Vector Machines (Basics) Study Guide

This guide is designed to review the fundamental concepts of Support Vector Machines (SVMs) as presented in the source material. It includes a short-answer quiz, an answer key, suggested essay questions for deeper exploration, and a glossary of key terms.

Quiz: Short-Answer Questions

Instructions: Answer the following ten questions in 2-3 sentences each, based on the provided source context.

1. What are the three major types of classification approaches discussed, and what is the core principle of each?
2. When was the Support Vector Machine (SVM) first introduced, and what theoretical field inspired its development?
3. What specific application was instrumental in popularizing SVMs, and how did its performance compare to a contemporary neural network?
4. Describe the MNIST dataset, including its contents and original purpose.
5. What is the “margin” of a linear classifier?
6. What are “support vectors” and what role do they play in a maximum margin classifier?
7. What is the primary goal of the simplest type of SVM, known as a Large Margin Linear Classifier (LSVM)?
8. According to the source, why is maximizing the margin a desirable approach for a classifier?
9. How is the optimization problem for a linear SVM formally stated? What is being minimized, and what are the constraints?
10. What mathematical object represents the decision boundary in a linear classifier, and how is the classification function expressed in terms of parameters w and b?

Answer Key

1. The three major types are Discriminative, Generative, and Instance-based classifiers. Discriminative approaches directly estimate a decision boundary (e.g., SVM). Generative approaches build a generative statistical model (e.g., Naïve Bayes). Instance-based classifiers use observations directly without building models (e.g., K-nearest neighbors).

2. The SVM was first introduced in 1992. Its development was inspired by statistical learning theory, as detailed in V. Vapnik’s work, “The Nature of Statistical Learning Theory.”

3. SVMs became popular due to their success in handwritten digit recognition. An SVM achieved a 1.1% test error rate, which was the same as the error rate of a carefully constructed neural network known as LeNet 4.

4. The Mixed National Institute of Standards and Technology (MNIST) dataset is a database for evaluating handwritten digit recognition. It contains 60,000 training instances and 10,000 test instances of hand-written digits, each encoded as a 28x28 pixel grayscale image.

5. The margin of a linear classifier is defined as the width that the decision boundary could be increased by before it hits a datapoint from either class. A maximum margin classifier seeks to make this width as large as possible.

6. Support vectors are the specific datapoints that the margin pushes up against. These data points are critical because they alone define, or “support,” the position and orientation of the optimal decision boundary.

7. The goal of a maximum margin linear classifier (or LSVM) is to identify the single linear classifier (decision boundary) that has the maximum possible margin. Instead of fitting all data points, it focuses on the points at the boundary between classes.

8. Maximizing the margin is considered a good strategy because it is intuitive, has theoretical support from concepts like VC dimension, and has been shown to work well in practice.

9. The optimization problem is to minimize (w^T * w) / 2. This is subject to the constraints that for all training samples xi, the expression yi * (w^T * xi + b) must be greater than or equal to 1, ensuring all points are correctly classified outside the margin.

10. A hyperplane represents the decision boundary. The classification function is expressed as f(x,w,b) = sign(w^T * x + b), where w is a vector of weights and b is a scalar bias term.

Suggested Essay Questions

Instructions: The following questions are designed for longer, more detailed responses that require synthesizing multiple concepts from the source material.

1. Trace the history of machine learning from the 1950s through the 2000s as outlined in the source. For each decade, identify the key paradigms, inventions, or theoretical advancements that were prominent.

2. Using the performance data from Table 10.1 on the MNIST evaluation, compare and contrast the effectiveness of Support Vector Machines with at least three other types of classifiers. Discuss the impact of using “distortions” on classifier performance.

3. Explain the concept of a maximum margin classifier in detail. Describe the geometric intuition behind the margin, the planes defined by w^T * x + b = 1, w^T * x + b = -1, and the central decision boundary. Clarify why the vector w is orthogonal to the decision boundary.

4. Discuss the range of applications where SVMs have been successfully implemented. Based on the historical context provided, explain why SVMs were considered a dominant and “hot” area in machine learning in the 2000s.

5. Describe the formal optimization problem for finding the optimal parameters (w, b) in a linearly separable SVM. Explain what Quadratic Programming is and why it is the appropriate method for solving this specific optimization problem.

Glossary of Key Terms

SVM, Kernel

• Lecture: S4-SVM-kerneltrick
• Version: next
• Notes to Read: Practical Guide
• Video: M1 + M2 + M3 + (Extra M4)

Study Guide for Non-Linear Support Vector Machines and the Kernel Trick

This guide provides a comprehensive review of the concepts presented in the source material on non-linear Support Vector Machines (SVMs). It includes a quiz to test your understanding, an answer key for verification, suggested essay questions for deeper exploration, and a glossary of key terms.

Quiz: Short-Answer Questions

Instructions: Answer each of the following questions in 2-3 sentences, based on the provided source material.

1. What is the fundamental problem that non-linear SVMs are designed to solve, and what is the general strategy used to address it?
2. Explain the concept of Vapnik-Chervonenkis (VC) dimension in the context of making data linearly separable.
3. What are the two primary computational problems that arise from explicitly mapping data to a high-dimensional feature space?
4. Define the “kernel trick” and explain how it resolves the computational issues associated with high-dimensional feature spaces.
5. What is the role of the dual formulation in making the kernel trick possible for SVMs?
6. Name two types of non-linear kernel functions mentioned in the text and describe their mathematical form.
7. According to the practical guide for LIBSVM, why is scaling features before applying an SVM considered very important?
8. Describe the effect of using a large versus a small value for the penalty parameter C in SVM model selection.
9. Despite using potentially infinite-dimensional feature spaces, why do SVMs with kernels not necessarily overfit the data?
10. What condition must a similarity measure satisfy to be used as a kernel function, and what does this condition guarantee?

Answer Key

1. What is the fundamental problem that non-linear SVMs are designed to solve, and what is the general strategy used to address it? Non-linear SVMs are designed to classify data that is not linearly separable in its original input space. The strategy is to map the original input space (x) to a higher-dimensional feature space (φ(x)) where the training set becomes linearly separable by a hyperplane.

2. Explain the concept of Vapnik-Chervonenkis (VC) dimension in the context of making data linearly separable. The source material states that the VC dimension of separating hyperplanes in an N-dimensional space is at least N+1. This theory supports the idea that if data is mapped into a sufficiently high dimension, the samples will generally become linearly separable. Specifically, N data points are generally separable in a space of N-1 dimensions or more.

3. What are the two primary computational problems that arise from explicitly mapping data to a high-dimensional feature space? The two main problems are a high computational burden due to the high dimensionality and the significantly increased number of parameters that need to be estimated. These issues make the explicit transformation computationally intensive and complex.

4. Define the “kernel trick” and explain how it resolves the computational issues associated with high-dimensional feature spaces. The kernel trick is a method for efficient computation that allows SVMs to operate in a high-dimensional feature space without ever explicitly representing the features. It achieves this by defining a kernel function, K(x, z), that computes the dot product Φ(x)TΦ(z) directly in the original input space, avoiding the high computational cost of the explicit transformation.

5. What is the role of the dual formulation in making the kernel trick possible for SVMs? The dual formulation of the SVM optimization problem is crucial because it expresses the objective function in terms of the dot product of input samples (xi * Txj). This structure allows the dot product to be directly replaced by a kernel function K(xi, xj), enabling the model to learn a non-linear boundary without ever computing in the high-dimensional space.

6. Name two types of non-linear kernel functions mentioned in the text and describe their mathematical form. The text mentions the Polynomial kernel, with the form K(x, z) = (1 + xTz)^d, and the Radial Basis Function (RBF) kernel, with the form K(x, z) = exp(-r

   x-z

   ^2). The RBF kernel is noted to have a feature space with an infinite number of dimensions.

7. According to the practical guide for LIBSVM, why is scaling features before applying an SVM considered very important? Feature scaling is very important for two main reasons. First, it prevents attributes in greater numeric ranges from dominating those in smaller numeric ranges. Second, it helps to avoid numerical difficulties that can occur during the calculation process.

8. Describe the effect of using a large versus a small value for the penalty parameter C in SVM model selection. A large value of C heavily penalizes misclassifications, resulting in a smaller margin and less training error, which can lead to overfitting. Conversely, a small value for C is more tolerant of training errors, resulting in a larger margin and potentially better true error (generalization).

9. Despite using potentially infinite-dimensional feature spaces, why do SVMs with kernels not necessarily overfit the data? SVMs avoid overfitting for three key reasons. The number of parameters (dual weights αi) remains the same and most are set to zero; the final model only depends on the support vectors, which are usually a small subset of samples; and the objective of maximizing the margin acts as a form of regularization.

10. What condition must a similarity measure satisfy to be used as a kernel function, and what does this condition guarantee? A similarity measure must satisfy Mercer’s condition, which states that the kernel K(x, y) must be positive semi-definite. This condition guarantees that the function can be expressed as a dot product in a high-dimensional space, making it a valid kernel for an SVM.

Suggested Essay Questions

1. Describe the complete journey of classifying a non-linearly separable dataset using a kernelized SVM. Start with the initial problem, explain the theoretical justification for mapping to a higher dimension (mentioning VC dimension), detail the computational challenges this creates, and finally, explain how the combination of the dual formulation and the kernel trick provides an efficient and elegant solution.

2. Compare and contrast the Polynomial kernel and the Radial Basis Function (RBF) kernel. Discuss their mathematical forms, the nature of their respective feature spaces (finite vs. infinite dimensionality), and the computational implications of building their kernel matrices.

3. Based on the “Practical Guide to Support Vector Classification,” outline a comprehensive pipeline for a machine learning project using LIBSVM. Your pipeline should cover feature preprocessing (for categorical, scaled, and missing data), model selection (including the roles of C and kernel choice), and the use of k-folds cross-validation.

4. Elaborate on the argument that SVMs are resistant to overfitting. Connect the concepts of structural risk minimization, the role of the ½

   w

   ² term, the maximization of the margin, and the sparsity of support vectors to build a cohesive explanation for why this powerful classifier can generalize well.

5. Explain why the kernel function can be thought of as a “similarity measure.” How does this conceptual view connect to Mercer’s condition and the underlying mathematical mechanism of computing a dot product in a transformed feature space?

Glossary of Key Terms

DecisionTree and Bagging

• Lecture: S4-DecisionTree
• Version: next
• Video: M1 + M2 + M3

Summary:

• Module1: Basic Tree4Classifier @ https://youtu.be/JKcTiyvIpp8
• Module2: How2Learn Tree https://youtu.be/iKTxnJU0L1E
• Module3: Bagged DT https://youtu.be/WaWTw07Luzs

Study Guide for Decision Trees and Ensemble Methods

Quiz

Answer the following questions in 2-3 sentences, based on the provided lecture material.

1. What are the three major types of classification approaches described in the lecture, and which category do decision trees belong to?
2. Describe the basic anatomy of a decision tree as explained in the “Play Tennis” example.
3. What is Entropy in the context of information theory, and what does a lower entropy value signify for a node in a decision tree?
4. Explain the concept of Information Gain (IG) and its function in the process of building a decision tree.
5. What is a primary caveat or disadvantage of using Information Gain as a purity measure for selecting splits?
6. Identify two common problems associated with decision trees and list the two general approaches mentioned for addressing overfitting.
7. Define Bootstrap Aggregation (Bagging) and explain its primary purpose.
8. How does the “instability” or “high variance” of a model like a decision tree relate to the effectiveness of Bagging?
9. What are the main characteristics of the CART (Classification and Regression Trees) algorithm?
10. What is the purpose of “pruning” in decision tree construction, and what are the two main types mentioned?

Answer Key

1. The three major types of classification approaches are Discriminative, Generative, and Instance-based. Decision trees are a discriminative approach, meaning they directly estimate a decision rule or boundary to separate classes.

2. A decision tree consists of nodes, which represent tests on a specific feature or attribute. The branches from a node correspond to the possible values of that attribute, and the leaves of the tree represent the final decisions or classifications. As data is passed down the tree, the sample size at each node gets progressively smaller.

3. Entropy is defined as the expected amount of information when observing the output of a random variable. In a decision tree, entropy measures the purity of a node; a lower entropy value indicates that the distribution of classes within that node is less uniform and therefore purer.

4. Information Gain, calculated as entropy(parent) – [average entropy(children)], measures the reduction in uncertainty about the target variable (Y) after knowing a feature variable (X). It is used as a criterion to select which attribute provides the best split at each node, with the attribute offering the highest IG being chosen.

5. A primary caveat is that the number of possible values for an attribute influences the information gain. An attribute with more possible values is more likely to have a higher gain because it can more easily form small, pure partitions, which can be misleading.

6. Two common problems are the instability of trees (high variance) and overfitting. The two approaches to combat overfitting are: 1) stop growing the tree when further splitting provides no improvement, or 2) grow a full tree and then prune it by eliminating nodes.

7. Bootstrap Aggregation, or Bagging, is a technique for reducing the variance of a prediction function. It works by creating multiple bootstrap samples (datasets drawn with replacement from the original training data), fitting a model to each sample, and then having the models vote on the final prediction.

8. Model instability is considered beneficial for Bagging. High-variability methods like decision trees see more improvement from Bagging because the process of averaging predictions from different models (fit on different data samples) helps to smooth out their instability and reduce overall variance.

9. The CART algorithm is a popular tree-builder that constructs binary trees. It can work with discrete, continuous, and categorical values, handles missing values using “surrogate splits,” and uses cost-complexity pruning to reduce overfitting. The Scikit-learn library uses CART for its tree implementations.

10. Pruning is a technique used to reduce the size of decision trees by removing branches with little predictive power, which helps to reduce overfitting. The two main types mentioned are Reduced Error Pruning, which replaces nodes starting from the leaves, and Cost Complexity Pruning, which removes the subtree that minimizes a specific error-to-complexity ratio.

Essay Questions

Formulate comprehensive, essay-style answers to the following prompts. No answer key is provided.

1. Using the “Play Tennis” example, explain how a decision tree represents a “disjunction of conjunctions.” Detail the logical structure and show how a new test case is classified by being passed down the tree.

2. Describe the role of information theory in the greedy construction of a decision tree. Define Information, Entropy, and Information Gain, explaining the mathematical relationship between them and how they guide the selection of the optimal attribute at each split.

3. Discuss the problem of overfitting in decision trees. Elaborate on why decision trees are particularly susceptible to this issue, mentioning concepts like model instability and error propagation.

4. Explain the Bagging technique in detail. Describe the process of creating bootstrap samples, training a “committee of trees,” and making a final prediction. Why is this method particularly effective for high-variance models?

5. Compare and contrast the ID3, C4.5, and CART tree-building algorithms. Discuss their historical progression, the purity metrics they commonly use, and their respective capabilities in handling different data types (continuous vs. discrete), missing values, and overfitting.

Glossary of Key Terms

RF and Boosting

• Lecture: S4-DT-Ensemble
• Version: next
• More advanced to Read: S4-DT-moreBoosting
• Notes to Read: xgboost
• Video: M1 + M2 + M3 + M4

Summary:

• Module1: Committee of Models and Analysis https://youtu.be/NuxS9SycZG8
• Module2: Random Forest and Analysis https://youtu.be/m52bovS_eNA
• Module3: Stacking https://youtu.be/sRLyzg5hmuM
• Module4: Boosting https://youtu.be/VwFTEW_NM4o

Study Guide: Ensemble Methods in Machine Learning

This guide provides a comprehensive review of ensemble methods in machine learning, including Bagging, Random Forests, Stacking, and Boosting, based on the provided lecture materials. It includes a quiz to test your knowledge, an answer key, a set of essay questions for deeper consideration, and a glossary of key terms.

Short-Answer Quiz

Instructions: Answer the following questions in 2-3 sentences each, based on the provided source material.

1. What is the core two-step framework of an ensemble method in machine learning?
2. Explain the process of “bootstrap sampling” as it is used in Bagging.
3. Why is model instability considered a beneficial trait for the base classifiers used in Bagging?
4. What is the primary limitation of Bagging that the Random Forest algorithm is designed to address?
5. How does the Random Forest algorithm de-correlate the individual decision trees within its ensemble?
6. Explain the role that pairwise correlation (ρ) between trees plays in determining the overall variance of an ensemble model.
7. Describe the general architecture of Stacking, identifying its main components.
8. What are the three core principles that guide boosting strategies?
9. Contrast the training processes of Boosting and Bagging, highlighting a key difference in their approach to the training data.
10. List at least three key features of the XGBoost implementation that contribute to its efficiency.

Answer Key

1. The framework of an ensemble method involves two main steps. First, a set of diverse classifiers is generated. Second, the predictions of these individual classifiers are aggregated, for instance by taking a majority vote, to form a final prediction.

2. Bootstrap sampling is a technique of randomly drawing datasets with replacement from the original training data. Each new sample is the same size as the original training set, and because the sampling is done with replacement, individual data points can be duplicated within a sample.

3. Model instability is beneficial in Bagging because the more variable or unstable a basic model is, the more improvement can be gained by averaging multiple versions of it. High-variability models like decision trees see more improvement from Bagging than low-variability methods.

4. The primary limitation of Bagging is that the bagged trees are often correlated with each other. Random Forest is an extension of Bagging that was specifically designed to reduce this correlation between the trees.

5. Random Forest de-correlates its trees by introducing an additional layer of randomness during the tree-building process. At each node, when choosing a feature for a split, the algorithm only considers a random subset of m features from the total p available features, rather than all of them.

6. Pairwise correlation (ρ) between classifiers directly impacts the variance of the ensemble’s average prediction. Even as the number of classifiers (B) approaches infinity, the variance term related to correlation (ρσ²) remains, meaning that higher correlation prevents the total variance from being minimized.

7. Stacking involves learning and combining multiple classifiers. It uses a set of “base learners” trained on the data, and their predictions are then fed as input into a “meta learner” or “blender,” which is a higher-level classifier that makes the final prediction.

8. The three core principles of boosting are: (1) using many base classifiers to vote on a decision, (2) sequentially training classifiers where each corrects the mistakes of the previous ones, thereby focusing on hard examples, and (3) giving higher weight to the better-performing base classifiers.

9. Unlike Bagging, which trains classifiers in parallel on different bootstrap samples of the data, Boosting trains classifiers sequentially on the entire training set. Boosting adaptively re-weights the training examples at each step to focus on instances that previous classifiers misclassified.

10. Key features of the XGBoost implementation include: the ability to use L1 or L2 regularization, a sparsity-aware split finding algorithm for handling sparse data, and a block structure system design that enables parallel learning across multiple CPU cores. Other features include cache awareness and out-of-core computing for very large datasets.

Essay Questions

Instructions: The following questions are designed for longer, more detailed responses. Formulate your answers by synthesizing information from across the lecture materials.

1. Compare and contrast the Bagging and Boosting ensemble methods. Discuss their approaches to training data, model creation (parallel vs. sequential), and their primary goals in improving model performance.

2. Explain the Bias-Variance Tradeoff in the context of ensemble methods. How do techniques like Bagging leverage complex, high-variance base models (like full decision trees) to create a final classifier with significantly lower variance?

3. Describe the evolution from a simple Bagged Decision Tree to a Random Forest. What specific mechanism was introduced in Random Forest, and why is it mathematically significant for reducing the ensemble’s variance, as explained by the role of pairwise tree correlation?

4. Detail the sequential nature of boosting algorithms like AdaBoost. How does the process focus on “hard examples” from one iteration to the next, and what roles do example weights and classifier weights play in constructing the final, powerful model?

5. Discuss the practical implementation and features of modern boosting libraries like XGBoost and LGBM. What technical innovations allow them to be so efficient and popular in machine learning competitions, and what is a key difference in their tree growth strategies?

Glossary of Key Terms

SVM, Dual

• Lecture: S4-SVM-optimDual
• Version: next
• Notes to Read: SMO
• Extra Notes to Read: Paper SMO
• Video: Extra M4

convex optim with Dual

• Lecture: S4-SVMoptimDual-Extra
• Version: next
• Notes to Read: VC Theory

More on Boosting

• Lecture: S4-DT-moreBoosting
• Version: next

Section 5 - Not Supervised

Clustering Hier

• Lecture: S5-clustering1-Hier
• Version: next
• Notes to Read: compare Hier clusterings
• Video: M1 + M2

Summary:

Hierarchical:

• Module1: Basics of Unsupervised Clustering @ https://youtu.be/mxrcPHWCZAI
• Module2: Hierarchical Clustering @ https://youtu.be/2K6gXLf4Em4

K-means

• Module1: Basic K-Means Algorithm @ https://youtu.be/239r6zlZYhY
• Module2: Theory/Complexity of K-Means @ https://youtu.be/OFKKeVhCQfA
• Extra Module3: Gaussian Mixture Models @ https://youtu.be/pmNPXpj0eK4

Unsupervised Learning: A Study Guide on Hierarchical Clustering

Quiz: Short Answer Questions

Answer the following questions in 2-3 sentences based on the provided course material.

1. What is the core difference between unsupervised and supervised machine learning?
2. Define the primary goal of clustering and describe the two main properties of an ideal clustering solution.
3. List the four desirable properties of a distance measure and provide a brief, intuitive explanation for one of them.
4. What is the Minkowski metric, and what are its three most common forms?
5. Under what conditions is Hamming distance used, and how does it relate to the Manhattan distance?
6. Explain the fundamental difference between the operational approaches of partitional and hierarchical clustering algorithms.
7. What is a dendrogram, and what role does it play in hierarchical clustering?
8. Describe the process of bottom-up agglomerative clustering.
9. Name and briefly define the three common methods for calculating the distance between two clusters in hierarchical clustering.
10. What is the primary limitation of hierarchical clustering methods regarding their performance on large datasets?

Answer Key

1. Unsupervised learning operates on raw, unlabeled data (an unlabeled dataset X with no Y variable), aiming to find inherent structures or patterns. In contrast, supervised learning is provided with labeled examples (both X and Y variables) and aims to learn a function that maps inputs to outputs, such as in regression (continuous Y) or classification (discrete Y).

2. The goal of clustering is to group a set of objects into classes where objects within a class are similar to each other and dissimilar to objects in other classes. An ideal solution achieves high intra-class similarity (minimized intra-cluster distances) and low inter-class similarity (maximized inter-cluster distances).

3. The four properties are: Symmetry, Constancy of Self-Similarity, Positivity Separation, and Triangular Inequality. Symmetry (D(A,B) = D(B,A)) provides the intuition that if “Alex looks like Bob,” then “Bob must look like Alex.”

4. The Minkowski metric is a generalized formula for calculating the distance between two objects, x and y, that each have p features. Its three most common forms are determined by the parameter ‘r’: Euclidean distance (r=2), Manhattan distance (r=1), and “sup” distance (r=+∞).

5. Hamming distance is used when all features of the data are binary or discrete, such as gene expression levels recorded as either high (1) or low (0). It is a special case of the Manhattan distance applied to this type of data.

6. Partitional algorithms typically start with a random partitioning of the data into a pre-specified number of clusters and then refine these clusters iteratively. Hierarchical algorithms do not require a fixed number of clusters in advance and instead build a tree-based structure, either by starting with individual objects and merging them (agglomerative) or by starting with a single group and splitting it (divisive).

7. A dendrogram is a tree-based diagram that represents the hierarchical taxonomy produced by a clustering algorithm. It illustrates the history of merges or splits, showing which objects and clusters were grouped together and at what distance, allowing users to form partitions by “cutting” the tree at a desired level.

8. Bottom-up agglomerative clustering begins with each data object as its own separate cluster. In each step, the algorithm identifies the two closest clusters based on a chosen distance metric and merges them into a single new cluster, repeating this process until only one cluster containing all objects remains.

9. The three methods are Single-Link, Complete-Link, and Average-Link. Single-Link defines cluster distance as the distance between the two closest members of the clusters. Complete-Link uses the distance between the two farthest members. Average-Link calculates the average distance of all cross-cluster pairs.

10. The primary limitation is that they do not scale well to large datasets. The time complexity is at least O(n²), where n is the number of objects, because in the first iteration, the algorithm must compute the similarity for all pairs of instances.

Essay Questions

The following questions are designed for a more in-depth, essay-format response. No answers are provided.

1. Discuss the subjective nature of clustering. Using the concepts of “groupness,” “similarity/distance,” and the determination of the number of clusters, explain why different yet equally valid clustering solutions can exist for the same dataset.

2. Compare and contrast the use of Euclidean distance and the Pearson correlation coefficient as similarity measures. Explain a scenario where one would be significantly more appropriate than the other, referencing the provided discussion on gene expression time series data.

3. Provide a comprehensive explanation of the bottom-up agglomerative hierarchical clustering process, from the initial pairwise distance matrix to the final dendrogram. In your explanation, detail how the choice between Single-Link, Complete-Link, and Average-Link methods influences the process and the potential shapes of the resulting clusters.

4. Analyze the computational complexity and scalability challenges of hierarchical clustering. Elaborate on why the time complexity is at least O(n²) and can become O(n³) if implemented naively. Discuss the practical implications of this complexity when applying these methods to modern, large-scale datasets.

5. Machine learning is framed as a combination of Representation, a Score Function, and a Search/Optimization strategy. Deconstruct hierarchical clustering using this framework. What constitutes the data representation, what is the search strategy, and why is its score function described as having “no clearly defined loss”?

Glossary of Key Terms

Clustering Partition

• Lecture: S5-clustering2-kMeans
• Version: next
• More advanced to Read: L19d-EMextra-EM
• Notes to Read: compare clusterings
• Video: M1 + M2

Summary:

• Module1: Basic K-Means Algorithm @ https://youtu.be/239r6zlZYhY
• Module2: Theory/Complexity of K-Means @ https://youtu.be/OFKKeVhCQfA
• Extra Module3: Gaussian Mixture Models @ https://youtu.be/pmNPXpj0eK4

K-Means and Partitional Clustering Study Guide

Quiz: Short Answer Questions

Answer the following questions in 2-3 sentences, based on the provided source material.

1. What is the fundamental difference between unsupervised and supervised machine learning?
2. Describe the primary goal of clustering in terms of intra-cluster and inter-cluster distances.
3. How do partitional clustering algorithms, like K-means, generally operate?
4. Outline the five core steps of the K-means algorithm.
5. What role does the centroid play in the K-means algorithm, and how is its position updated?
6. Explain the concept of “elbow finding” or “knee finding” for determining the number of clusters.
7. Why is the initial selection of cluster centers (seeds) a critical consideration in K-means?
8. What is the mathematical objective of the K-means algorithm, and how does it relate to convergence?
9. Briefly describe the Gaussian Mixture Model (GMM) approach to clustering.
10. Define “purity” as an external criterion for evaluating cluster quality.

Answer Key

1. Unsupervised learning works with raw, unlabeled data, where no target variable (Y) is given. In contrast, supervised learning uses labeled data where a classification label or a continuous target variable is provided for each example.

2. The goal of clustering is to find groups where data points within a single group are similar to one another and different from data points in other groups. This is achieved by minimizing intra-cluster distances (distances within a cluster) and maximizing inter-cluster distances (distances between different clusters).

3. Partitional algorithms construct a partition of n objects into a set of K clusters, where the user must specify the number of clusters K. They typically start with a random partitioning and refine it iteratively until a stopping condition is met.

4. The K-means algorithm follows these steps: 1) Decide on a value for k. 2) Initialize k cluster centers randomly. 3) Assign each object to its nearest cluster centroid. 4) Re-estimate the cluster centers based on the new memberships. 5) Repeat steps 3 and 4 until no objects change membership.

5. A centroid is the center of gravity or mean of all data points belonging to a cluster. In each iteration of the K-means algorithm, after data points are assigned to their nearest centroid, each centroid’s position is updated by “jumping” to the mean location of the points it now “owns”.

6. “Elbow finding” is a heuristic method to determine the right number of clusters (k). It involves running K-means for a range of k values and plotting the objective function (sum of squared distances) for each k. The optimal k is often found at the “elbow” or “knee” of the plot, where the rate of decrease in the objective function value abruptly slows.

7. The initial selection of random seeds can significantly impact the results of K-means. Some seed selections can lead to a poor convergence rate or cause the algorithm to converge to a sub-optimal clustering solution. To mitigate this, it is very important to try multiple starting points or use heuristics to select good seeds.

8. The mathematical objective is to minimize the sum of squared distances between each data point and the centroid of its assigned cluster. The algorithm converges because each reassignment step monotonically decreases this objective function, and it will eventually reach a fixed point where cluster memberships no longer change.

9. A Gaussian Mixture Model (GMM) is a partitional clustering method that assumes data is generated from a mixture of Gaussian distributions. It uses the Expectation-Maximization (EM) algorithm to iteratively revise each point’s proportional membership to clusters and update each cluster’s mean (centroid) and covariance (shape).

10. Purity is an external evaluation measure that assesses clustering quality with respect to ground truth (gold standard classes). For a single cluster, it is calculated as the ratio between the number of objects from the dominant class within that cluster and the total size of the cluster.

Essay Questions

Develop a detailed response to the following prompts, synthesizing information from the source material.

1. Compare and contrast the K-means algorithm with the Gaussian Mixture Model (GMM) approach to partitional clustering. Discuss their core assumptions, iterative processes, and how they define cluster membership for data points.

2. Discuss the computational complexity and potential challenges of the K-means algorithm. How does its time complexity scale with the number of objects, dimensions, clusters, and iterations, and what are the primary strategies for overcoming its sensitivity to initialization?

3. Explain the mathematical objective function that the K-means algorithm seeks to optimize. Detail how the two main iterative steps—assigning memberships and updating centroids—work in conjunction to minimize this function and guarantee convergence.

4. Describe the methods for evaluating the quality of a clustering result. Differentiate between internal and external criteria, providing a specific example of an external criterion like “purity” and explaining how it is calculated and what it signifies.

5. Imagine you are tasked with clustering an unlabeled tabular dataset. Outline a complete workflow using the K-means methodology, from defining the problem to evaluating the final output. Your plan should address data representation, determining the value of K, the iterative clustering process, and dealing with potential convergence issues.

Glossary of Key Terms

Reinforcement Learning

• Lecture: S5_RL22
• Version: next

Reinforcement Learning Study Guide

Quiz

Answer the following questions in 2-3 sentences each, based on the provided lecture materials.

1. How does Reinforcement Learning (RL) fundamentally differ from Supervised and Unsupervised Learning?
2. Describe the four core elements of the Reinforcement Learning setup.
3. What is a Markov Decision Process (MDP) and what is its key property?
4. Explain the difference between a “reward function” and a “value function” in RL.
5. What was the significance of the TD-Gammon program developed by Gerry Tesauro?
6. Compare the primary requirements of Dynamic Programming (DP) versus Monte Carlo (MC) methods for solving RL problems.
7. What is the “explore vs. exploit” dilemma, and what is the ε-greedy policy strategy for managing it?
8. How does Temporal-Difference (TD) learning combine ideas from both Dynamic Programming and Monte Carlo methods?
9. Define Q-learning and explain why it is considered an “off-policy” algorithm.
10. What is reward shaping and what is the guiding principle for designing good reward functions?

Answer Key

1. Unlike Supervised Learning which learns a map from data x to a label y, and Unsupervised Learning which learns underlying structure from unlabeled data x, Reinforcement Learning’s goal is to maximize future rewards over many steps. The data for RL consists of state-action pairs and the resulting rewards, as the agent learns by interacting with an environment.

2. The core elements are the agent, which is the learner or decision-maker; the environment, which the agent interacts with; the action, which is what the agent chooses to do; and the reward and new state, which are the feedback the environment provides in response to an action.

3. A Markov Decision Process (MDP) is a discrete-time stochastic control process that formally defines the environment in an RL problem. Its key property is that every outcome (the new state and reward) depends only on the current state and the chosen action, not on any previous states or actions.

4. A reward function maps a state or state-action pair to an immediate, single numerical value called a reward. In contrast, a value function represents the total expected future reward an agent can accumulate over the long run, starting from a specific state or state-action pair.

5. TD-Gammon was a Backgammon-playing program that became a major success story for RL. It used temporal-difference learning and a neural network, training itself to a world-class level simply by playing 1.5 million games against itself and learning from the outcomes.

6. Dynamic Programming requires a perfect and complete model of the environment, including knowledge of state transition probabilities and rewards. Monte Carlo methods do not need a model of the environment; instead, they learn directly from experience (or simulated experience) by averaging sample returns from completed episodes.

7. The “explore vs. exploit” dilemma is the challenge of choosing between actions that are known to yield good rewards (exploit) and trying new, unknown actions that might lead to better rewards (explore). The ε-greedy policy is a strategy where the agent chooses the known best action with probability 1-ε, but chooses a random action with a small probability ε to ensure continued exploration.

8. TD learning combines ideas from both methods by learning directly from experience without a model, similar to MC methods. However, it updates its value estimates based on the values of successor states, a technique known as bootstrapping that is characteristic of DP.

9. Q-learning is a temporal-difference method that directly approximates the optimal state-action value function, Q*. It is considered “off-policy” because it can learn the optimal policy regardless of the policy the agent is actually following to explore the environment, as long as every state-action pair continues to be updated.

10. Reward shaping is the practice of providing rewards for achieving subgoals to guide the agent, which is useful when the primary positive reward is very “far away” or difficult to achieve. The principle for good rewards is that they should indicate what the agent needs to accomplish, not how it should be accomplished.

Essay Questions

Construct detailed, essay-format answers for the following prompts, synthesizing information from across the lecture materials.

1. Discuss the historical development of Reinforcement Learning, citing the key contributions of Thorndike, Bellman, Samuel, and Watkins. Explain how each contribution added a foundational piece to the modern understanding of RL.

2. Compare and contrast the three main approaches for solving RL problems: Dynamic Programming, Monte Carlo methods, and Temporal-Difference learning. For each, describe its core idea, requirements (e.g., model of the environment), and its primary advantages and disadvantages.

3. Using the “Robot in a room” example, explain the roles of states, actions, rewards, the policy, and the value function. Describe how a discount factor (γ) affects the calculation of the value function and why it is a critical component in defining the agent’s goal.

4. AlphaGo is presented as a major success for Deep Reinforcement Learning. Describe its learning pipeline, explaining how it combines Supervised Learning (SL) and Reinforcement Learning (RL) and the specific roles of the SL policy network, the value network, and the Monte Carlo Tree Search (MCTS).

5. What are the key challenges in Reinforcement Learning? Discuss at least three challenges mentioned in the lecture, such as delayed rewards, the explore vs. exploit trade-off, state representation, and reward design, providing examples for each.

Glossary of Key Terms

deep RL Gym

• Lecture: S5-RL-Gym-to-come
• Version: next
• Notes to Read: Invited Speaker

Clustering GMM

• Lecture: S5-clustering3-GMM
• Version: next
• Video: (Extra M3)

Clustering GMM

• Lecture: S5-EMextra
• Version: next
• Notes to Read: EM primer

Section 6 - Wrap Up

Final Project Poster Day

• Lecture: S6-finalProject
• Version: next
• Notes to Read: see slack
• Video: see slack

Review

• Lecture: S6-review
• Version: next
• Notes to Read: [ML Cheatsheets]
• Video: video + HW1-3 Key HW4-key + Quiz-keys

Final Exam

• Lecture: S6-finalExam
• Version: next
• Notes to Read: see slack
• Video: see slack