CHAPTER 5: MACHINE LEARNING BASICS - COMPREHENSIVE GUIDE

Based on Deep Learning Textbook by Goodfellow, Bengio, and Courville

[Link] TO MACHINE LEARNING

What is Machine Learning?

Machine learning is a field of artificial intelligence that enables computers to learn from
data without being explicitly programmed for every possible scenario. Instead of writing
specific rules for every situation, we provide examples and let the algorithm discover
patterns.

Tom Mitchell's Formal Definition (1997):

"A computer program is said to learn from experience E with respect to some class of tasks
T and performance measure P, if its performance at tasks in T, as measured by P, improves
with experience E."

This elegant definition captures three essential components that must be present in any
machine learning system:

Task (T) - The specific problem the algorithm aims to solve

 What we want the machine to accomplish

 Examples: Recognizing faces, predicting stock prices, translating languages
Performance (P) - How we quantify success or failure

 Measurable metric to evaluate the algorithm

 Examples: Accuracy percentage, error rate, prediction quality
Experience (E) - The data or interactions used for learning

 Information from which the algorithm learns

 Examples: Labeled datasets, user interactions, sensor readings

1.2 Real-World Example: Email Spam Filter

Let's understand these components through a practical example:

Task (T): Classify each incoming email as either "spam" or "not spam"

Performance (P): The percentage of emails correctly classified (accuracy)

 If 95 out of 100 emails are classified correctly, performance = 95%

Experience (E): A database of thousands of emails, each labeled as spam or not spam
  The algorithm learns from patterns in this labeled dataset
 Features include: sender address, subject line words, email content
How Learning Occurs:

1. Initially, the algorithm performs poorly (random guessing ≈ 50% accuracy)

2. As it processes more labeled examples, it discovers patterns
3. Spam emails often contain certain words: "free money", "click here", "winner"
4. Legitimate emails have different patterns: personal greetings, proper grammar
5. Over time, accuracy improves from 50% → 70% → 90% → 95%
This improvement with experience is the essence of machine learning.

2. COMMON MACHINE LEARNING TASKS

Machine learning algorithms can solve various types of problems. Understanding these task
categories helps us choose the right approach for a given problem.

2.1 Classification
Definition: Assigning an input to one of k discrete categories.

Mathematical Formulation:

 Function: f: ℝⁿ → {1, 2, ..., k}

 Input: Vector x with n features
 Output: Category identifier y
Key Characteristics:

 Output is discrete (finite set of categories)

 Mutually exclusive categories (belongs to exactly one)
 Categories are predetermined
Real-World Examples:

1. Image Recognition (MNIST Digit Classification)

 Input: 28×28 pixel image (784-dimensional vector)

 Output: One of 10 digits (0, 1, 2, ..., 9)
 Application: Automatic check reading, postal code recognition
2. Medical Diagnosis

 Input: Patient data (age, blood pressure, cholesterol, symptoms)

  Output: Disease category (healthy, diabetes, heart disease, etc.)
 Application: Assisting doctors with preliminary diagnoses
3. Spam Detection

 Input: Email features (words, sender, attachments)

 Output: Spam or Not Spam
 Application: Email filtering systems
4. Sentiment Analysis

 Input: Product review text

 Output: Positive, Neutral, or Negative
 Application: Customer feedback analysis
Variants:

 Binary Classification: Two categories (yes/no, spam/not spam)

 Multi-class Classification: Multiple categories (digit 0-9)
 Multi-label Classification: Multiple labels can apply simultaneously (image
contains both cat AND dog)

2.2 Regression
Definition: Predicting a continuous numerical value from input features.

Mathematical Formulation:

 Function: f: ℝⁿ → ℝ
 Input: Vector x with n features
 Output: Real number y
Key Difference from Classification:

 Classification outputs discrete categories

 Regression outputs continuous numbers (can be any value in a range)
Real-World Examples:

1. House Price Prediction

 Input Features: Size (square feet), number of bedrooms, location, age, amenities
 Output: Predicted sale price ($250,000, $375,500, $1.2 million, etc.)
 Application: Real estate valuation, mortgage approval
2. Weather Forecasting
  Input: Historical temperature, humidity, pressure, wind speed
 Output: Tomorrow's temperature (e.g., 23.5°C)
 Application: Weather services, agriculture planning
3. Stock Price Prediction

 Input: Historical prices, trading volume, market indicators

 Output: Next day's closing price (e.g., $142.67)
 Application: Trading algorithms, investment decisions
4. Energy Consumption Forecasting

 Input: Time of day, season, historical usage, weather

 Output: Kilowatt-hours needed (e.g., 3,456 kWh)
 Application: Grid management, resource allocation

2.3 Transcription
Definition: Converting unstructured data (images, audio) into discrete textual form.

Key Challenge: Input is continuous/analog, output is discrete symbols

Applications:

1. Optical Character Recognition (OCR)

 Input: Image of printed or handwritten text

 Output: Sequence of characters ("Hello World")
 Real-world use:
o Digitizing historical documents
o License plate recognition
o Reading checks at banks
o Accessibility tools for visually impaired
2. Speech Recognition

 Input: Audio waveform (sound waves)

 Output: Sequence of words ("What is the weather today?")
 Real-world use:
o Virtual assistants (Siri, Alexa, Google Assistant)
o Voice typing on smartphones
o Automated transcription services
 o Hands-free device control
Challenges:

 Ambiguity: Same sound can represent different words ("there" vs "their")

 Noise: Background sounds interfere with recognition
 Variations: Different accents, handwriting styles, speaking speeds
 Context dependency: Need to understand context to resolve ambiguities

2.4 Machine Translation

Definition: Converting a sequence of symbols in one language to another while preserving
meaning.

Example:

 Input: "Hello, how are you?" (English)

 Output: "Bonjour, comment allez-vous?" (French)
Why It's Difficult:

1. Not Word-by-Word Replacement

 Languages have different grammatical structures

 Word order can completely change (English: adjective-noun, French: noun-
adjective)
 Some concepts exist in one language but not another
2. Idioms and Cultural Context

 "It's raining cats and dogs" should not be translated literally

 Cultural references need localization, not direct translation
3. Ambiguity

 "Bank" could mean financial institution or river bank

 Context determines correct translation
Modern Approaches:

 Neural machine translation systems

 Attention mechanisms to focus on relevant parts
 Transformer architectures (like GPT, BERT)
Applications:

 Google Translate, DeepL

  International business communication
 Multilingual customer support
 Content localization

2.5 Anomaly Detection

Definition: Identifying inputs that deviate significantly from normal patterns.

Key Characteristic: Anomalies are rare, so we have few examples to learn from.

Applications:

1. Credit Card Fraud Detection

 Normal Pattern: Regular spending at usual locations

 Anomaly: Sudden large purchase in foreign country
 Action: Block transaction, notify customer
2. Network Intrusion Detection

 Normal Pattern: Typical traffic patterns and access requests

 Anomaly: Unusual port scanning, unauthorized access attempts
 Action: Alert security team, block suspicious IP
3. Manufacturing Quality Control

 Normal Pattern: Products within specification tolerances

 Anomaly: Defective items with unusual measurements
 Action: Remove from production line, alert supervisor
4. Medical Monitoring

 Normal Pattern: Regular vital signs (heart rate 60-100 bpm)

 Anomaly: Sudden dangerous changes (heart rate 180 bpm)
 Action: Alert medical staff immediately
Challenge: Imbalanced data - very few anomaly examples to learn from

2.6 Density Estimation

Definition: Learning the probability distribution p(x) from which data examples are drawn.

Purpose:

 Understand the underlying structure of data

 Generate new realistic samples
  Detect outliers (low probability regions)
 Enable other tasks implicitly
Example Application - Image Modeling:

 Learn distribution of natural images

 Can then evaluate how "natural" a new image looks
 Low probability → unnatural/synthetic image
 High probability → realistic image
Uses:

 Data compression (encode common patterns efficiently)

 Image denoising (remove unlikely noise)
 Generative models (create new realistic samples)
 Anomaly detection (identify low-probability examples)

3. PERFORMANCE MEASURES
How do we know if our machine learning algorithm is working well? We need quantitative
metrics to evaluate performance.

3.1 Performance Measures for Classification

3.1.1 Accuracy

Definition: The proportion of correct predictions out of all predictions made.

Formula:
Accuracy = (Number of Correct Predictions) / (Total Number of Predictions)

Example:

 Dataset: 100 emails

 Correctly classified: 92 emails
 Accuracy = 92/100 = 0.92 = 92%
Range: [0, 1] or [0%, 100%]

 0: All predictions wrong

 1: All predictions correct
 Higher is better
3.1.2 Error Rate (0-1 Loss)

Definition: The proportion of incorrect predictions.

Formula:
Error Rate = 1 - Accuracy
Error Rate = (Number of Incorrect Predictions) / (Total Predictions)

Why Called "0-1 Loss"?

 Assigns loss of 0 for correct prediction (no penalty)

 Assigns loss of 1 for incorrect prediction (full penalty)
 Binary: either perfect or wrong, no partial credit
Example:

 Accuracy = 92%
 Error Rate = 100% - 92% = 8%
3.1.3 Limitations of Accuracy

Problem 1: Imbalanced Classes

Imagine a disease affecting 1% of the population:

 Always predict "No Disease" → 99% accuracy!

 But this is useless - it never detects actual cases
 Accuracy can be misleading
Problem 2: Equal Treatment of Errors

 Doesn't distinguish between different types of errors

 Missing a cancer diagnosis is worse than a false alarm
 Accuracy treats both errors equally
Solution: Use more sophisticated metrics

3.1.4 Advanced Classification Metrics

Confusion Matrix:
Predicted Positive Predicted Negative
Actual Positive TP FN
Actual Negative FP TN

Precision: Of predicted positives, how many are actually positive?

Precision = TP / (TP + FP)
Recall (Sensitivity): Of actual positives, how many did we find?
Recall = TP / (TP + FN)

F1-Score: Harmonic mean of precision and recall

F1 = 2 × (Precision × Recall) / (Precision + Recall)

3.2 Performance Measures for Regression

3.2.1 Mean Squared Error (MSE)

Most Common Regression Metric

Formula:
MSE = (1/m) Σᵢ₌₁ᵐ (ŷ⁽ⁱ⁾ - y⁽ⁱ⁾)²

Where:

 m = number of examples
 ŷ⁽ⁱ⁾ = predicted value for example i
 y⁽ⁱ⁾ = actual value for example i
Why Squared?

1. Makes All Errors Positive

 Without squaring: (+3) + (-3) = 0 (errors cancel)

 With squaring: 3² + 3² = 18 (both count as errors)
2. Penalizes Large Errors More

 Error of 2: contributes 4 to MSE

 Error of 4: contributes 16 to MSE (4× worse, not 2×)
 Encourages avoiding big mistakes
3. Mathematical Properties

 Differentiable everywhere (smooth)

 Easy to optimize with calculus
 Connection to Gaussian likelihood (Maximum Likelihood Estimation)
Example:
Actual prices: [100, 150, 200]
Predicted prices: [110, 145, 190]
Errors: [10, 5, 10]
Squared errors: [100, 25, 100]
MSE = (100 + 25 + 100) / 3 = 75

3.2.2 Mean Absolute Error (MAE)

Formula:
MAE = (1/m) Σᵢ₌₁ᵐ |ŷ⁽ⁱ⁾ - y⁽ⁱ⁾|

Characteristics:

 Uses absolute value instead of square

 Less sensitive to outliers than MSE
 More robust but less smooth (not differentiable at zero)
Example (same data):
Errors: [10, 5, 10]
Absolute errors: [10, 5, 10]
MAE = (10 + 5 + 10) / 3 = 8.33

Comparison:

 MSE = 75 (penalizes large errors heavily)

 MAE = 8.33 (treats all errors equally)
3.2.3 Root Mean Squared Error (RMSE)

Formula:
RMSE = √MSE

Advantage: Same units as the target variable

 If predicting prices in dollars, RMSE is also in dollars

 MSE would be in dollars-squared (less interpretable)
 Easier to understand: "Average error is $8.66"
Example:
MSE = 75
RMSE = √75 ≈ 8.66

3.3 Critical Principle: Test Set Evaluation

Golden Rule: Always evaluate on data the model has never seen!

Why?

 Training performance doesn't indicate real-world performance

 Model might memorize training data (overfitting)
 Test set simulates deployment on new data
Example:
Training Accuracy: 99% (Seen this data during training)
Test Accuracy: 75% (Never seen before)
→ Model is overfitting!
True performance is 75%, not 99%.

5.1 LEARNING PARADIGMS: SUPERVISED VS UNSUPERVISED

Supervised Learning
Definition: Learning from labeled data where both inputs (x) and correct outputs (y) are
provided.

Structure of Supervised Dataset:

Example 1: (x⁽¹⁾, y⁽¹⁾)
Example 2: (x⁽²⁾, y⁽²⁾)
...
Example m: (x⁽ᵐ⁾, y⁽ᵐ⁾)

Where:

 x⁽ⁱ⁾ = input features (what we observe)

 y⁽ⁱ⁾ = label/target (what we want to predict)
Goal: Learn a function that maps inputs to outputs
f: x → y

Real-World Example: House Price Prediction

Input (x):

 Size: 2000 sq ft
 Bedrooms: 3
 Location: Downtown
 Age: 5 years
Label (y):

 Sale Price: $350,000

Learning Process:

1. Show algorithm many (house features, price) pairs

2. Algorithm discovers relationship between features and prices
3. Can now predict prices for new houses never seen before
Characteristics of Supervised Learning:

 Requires labeled data (expensive to obtain)

 Labels must be accurate (garbage in, garbage out)
  Clear objective: minimize prediction error
 Direct feedback: know when predictions are wrong
Common Applications:

 Image classification (label: cat, dog, bird)

 Speech recognition (label: transcribed text)
 Medical diagnosis (label: disease present/absent)
 Spam filtering (label: spam/not spam)

Unsupervised Learning
Definition: Learning from unlabeled data where only inputs (x) are provided, no labels (y).

Structure of Unsupervised Dataset:

Example 1: x⁽¹⁾
Example 2: x⁽²⁾
...
Example m: x⁽ᵐ⁾

Only features, no labels!

Goal: Discover hidden structure or patterns in the data

Real-World Example: Customer Segmentation

Input (x) for each customer:

 Age: 35
 Income: $75,000
 Purchase frequency: 12 times/year
 Average order value: $120
No Labels Provided!

What Algorithm Discovers:

 Group 1: Young, low income, frequent small purchases (students)

 Group 2: Middle-aged, high income, occasional large purchases (professionals)
 Group 3: Elderly, moderate income, regular purchases (retirees)
Marketing team can now:

 Target each group with appropriate strategies

 Customize product recommendations
 Optimize pricing for each segment
Common Unsupervised Tasks:

1. Clustering: Group similar examples together

 Customer segmentation
 Document organization
 Image compression
2. Dimensionality Reduction: Find compact representations

 Visualization of high-dimensional data

 Feature extraction
 Data compression
3. Density Estimation: Model probability distribution

 Anomaly detection
 Generative modeling
 Data understanding
4. Association Rule Learning: Find relationships

 Market basket analysis ("customers who buy X also buy Y")

 Recommendation systems
Comparison:

Aspect Supervised Unsupervised

Labels Required Not required
Goal Predict outputs Find structure
Feedback Direct None
Applications Classification, Regression Clustering, Dimensionality reduction
Data cost Expensive Cheaper

Design Matrix Representation

Machine learning algorithms typically work with data organized in a standardized format
called the design matrix.

Structure:

 Rows: Individual examples (data points)

  Columns: Features (attributes, variables)
Notation:

 X: Design matrix of size m × n

 m: Number of examples (rows)
 n: Number of features (columns)
 x⁽ⁱ⁾: Row vector representing example i
 xⱼ: Column vector representing feature j
Example: Iris Dataset

Famous dataset for classification with 150 flower samples:

Features (4 columns):

 Sepal Length (cm)

 Sepal Width (cm)
 Petal Length (cm)
 Petal Width (cm)
Design Matrix (150 × 4):
[sepal_len, sepal_wid, petal_len, petal_wid]
X = [ [5.1, 3.5, 1.4, 0.2 ], ← Example 1
[4.9, 3.0, 1.4, 0.2 ], ← Example 2
[4.7, 3.2, 1.3, 0.2 ], ← Example 3
...
[5.9, 3.0, 5.1, 1.8 ] ← Example 150
]

Target Vector (150 × 1):

y = [setosa, setosa, setosa, ..., virginica]

Why This Format?

1. Efficient Computation

 Matrix operations are highly optimized

 Leverage fast linear algebra libraries (NumPy, MATLAB)
 Parallel processing on GPUs
2. Standardization

 Universal format across algorithms

 Easy to switch between methods
  Consistent preprocessing
3. Mathematical Convenience

 Algorithms expressed as matrix equations

 Easy to derive and implement
 Clean notation
Example Operations:

Accessing Data:
X[0, :] → First example (all features)
X[:, 0] → First feature (all examples)
X[0, 0] → First feature of first example

Common Manipulations:
Mean of each feature: [Link](axis=0)
Standardize features: (X - mean) / std
Matrix multiplication: X @ W (features × weights)

5. 2 THE CENTRAL CHALLENGE: GENERALIZATION

What is Generalization?
Definition: The ability to perform well on new, previously unseen data.

This is the ultimate goal of machine learning. We don't just want good performance on
training data - we want the model to work in the real world on new examples it has never
encountered.

Two Types of Error:

Training Error (Empirical Error)

 Performance measured on the data used to train the model

 The model has "seen" this data during learning
 Can be made arbitrarily small with enough model complexity
 Not what we ultimately care about
Test Error (Generalization Error)

 Performance measured on completely new data

 The model has never seen this data
 Reflects real-world performance
 This is what truly matters!
The Fundamental Challenge:

We can only optimize training error directly (because we have that data), but we really care
about test error (which we can't optimize directly during training). This gap creates the
central tension in machine learning.

Example:

Imagine studying for an exam:

 Memorizing answers to practice problems = Minimizing training error

o You'll ace those exact problems if they appear

o But won't help with variations or new questions
 Understanding underlying concepts = Minimizing test error

o Can solve any question, not just memorized ones

o True learning and generalization
Goal: Minimize test error, not just training error!

Underfitting
Definition: Model is too simple to capture the underlying patterns in the data.

Characteristics:

 High training error: Performs poorly even on training data

 High test error: Performs poorly on new data
 Insufficient capacity: Model lacks flexibility to fit the data
 Fails to learn: Cannot capture even obvious patterns
Visual Example:

Imagine data that follows a curved pattern (quadratic relationship):

True relationship: y = x²

Data points: scattered along this curve

Linear model attempts to fit: y = 2x (straight line)

Result:
Data: . . .
. .
Fit: /
/
/ ← Straight line misses the curve
The linear model cannot capture the curvature, resulting in large errors everywhere.

Real-World Example: House Price Prediction

Too Simple Model: Price = $100 × (Number of Bedrooms)

Problem:

 Ignores size, location, age, condition

 Two identical 3-bedroom houses:
o 1000 sq ft in suburbs: Actually worth $200k
o 3000 sq ft downtown: Actually worth $800k
o Model predicts both at $300k!
Symptoms:

 Training accuracy: 60% (poor)

 Test accuracy: 58% (also poor)
 Model hasn't learned meaningful patterns
Causes:

 Model family too restrictive (linear when should be non-linear)

 Too few features
 Over-regularization (too much constraint)
 Wrong choice of algorithm for the problem
Solution: Increase model capacity

 Use more complex model family (polynomial instead of linear)

 Add more relevant features
 Reduce regularization strength
 Try different algorithm

Overfitting
Definition: Model learns the training data too well, including noise and random fluctuations
that don't generalize.

Characteristics:

 Very low training error: Nearly perfect on training data (often near 0%)
 High test error: Poor performance on new data
 Large gap: Big difference between training and test error
  Too much capacity: Model is too flexible
Intuition: Model memorizes rather than learns the underlying pattern.

Visual Example:

Fitting a high-degree polynomial (e.g., degree 20) to data with noise:

True relationship: y = 2x (with noise)

Training points: . . . . . (scattered near line)

High-degree polynomial fit:

/\ /
/ / \ /\ ← Wild oscillations
/ / \ ← Passes through every training point

The polynomial passes through every training point exactly but creates wild oscillations
between points. On new data points, it will perform terribly.

Real-World Example: Email Spam Detection

Overfitted Model: Memorizes exact emails from training set

Training Performance:

 Email 1: "Free money click here" → Spam ✓ (seen in training)

 Email 2: "Your account statement" → Not Spam ✓ (seen in training)
 Training accuracy: 100%!
Test Performance:

 Email 3: "Free cash click here" → Not Spam ✗ (slightly different wording)
 Email 4: "Your statement is here" → Spam ✗ (didn't memorize this exact phrase)
 Test accuracy: 50%!
Model memorized specific training examples instead of learning general patterns like
"promotional language indicates spam."

Symptoms:

 Training accuracy: 99% (excellent)

 Validation accuracy: 65% (poor)
 Large gap indicates overfitting
Causes:

 Model too complex for amount of data

  Training for too long (continuing past optimal point)
 Insufficient regularization
 Learning noise as if it were signal
Solutions:

 Reduce model complexity

 Add regularization (weight decay, L1/L2)
 Get more training data
 Early stopping (stop training before overfitting)
 Dropout (randomly ignore units during training)
 Data augmentation (create more examples)

Model Capacity
Definition: A model's ability to fit a variety of functions.

Think of capacity as the "flexibility" or "expressiveness" of a model - how complex of a

relationship it can represent.

Capacity Spectrum:

Low Capacity
←―――――――――――――――――――――――――――――――→ High
Capacity
(Simple Model) (Complex Model)

Examples:
Linear Polynomial Decision Tree Neural Network
Regression (degree 2-5) (depth 10) (many layers)

1 parameter → 5 parameters → 100 parameters → 1,000,000 parameters

Factors Affecting Capacity:

1. Number of Parameters

More parameters generally means higher capacity:

 Linear Model: y = w₀ + w₁x₁ + w₂x₂

o Parameters: 3 (w₀, w₁, w₂)

o Capacity: Low (can only fit straight lines/planes)
 Polynomial Model (degree 5): y = w₀ + w₁x + w₂x² + w₃x³ + w₄x⁴ + w₅x⁵

o Parameters: 6 (w₀ through w₅)

 o Capacity: Medium (can fit curves)
 Neural Network: Multiple layers with hundreds of units

o Parameters: Hundreds of thousands or millions

o Capacity: Very high (can fit extremely complex functions)
2. Model Family

Different types of models have inherently different capacities:

 Linear models: Can only represent linear relationships

 Polynomial models: Can represent smooth curves
 Decision trees: Can represent piecewise constant functions
 Neural networks: Universal function approximators
3. Regularization

Regularization effectively reduces capacity by constraining parameter values:

 No regularization: Full capacity

 Weak regularization: Nearly full capacity
 Strong regularization: Reduced capacity (simpler functions)
Representational Capacity vs Effective Capacity:

Representational Capacity:

 Theoretical maximum: What functions could the model represent?

 Upper bound on what's possible
 Example: Neural networks can theoretically approximate any continuous function
Effective Capacity:

 What the model can actually learn in practice

 Limited by:
o Optimization algorithm (gradient descent might not find global optimum)
o Training procedure (finite training time)
o Regularization (constrains solutions)
o Data availability (can't learn what data doesn't show)
Example:
Model: Neural network (high representational capacity)

But with:
  Poor optimization → Gets stuck in local minimum
 Limited data → Can't explore full capacity
 Strong regularization → Artificially constrained
Result: Effective capacity much lower than representational capacity

Finding the Right Capacity:

Too low → Underfitting (can't capture patterns)

Optimal → Good generalization (just right)
Too high → Overfitting (memorizes noise)

This is determined empirically using validation set.

5.5 The U-Shaped Curve

A fundamental insight in machine learning: training error and test error behave very
differently as model capacity increases.

Training Error Behavior:

As capacity increases:

 Training error monotonically decreases

 Eventually can reach zero (perfect fit to training data)
 This is expected: more flexible model can fit data better
Test Error Behavior:

As capacity increases:

 First decreases (moving from underfitting toward optimal)

 Reaches a minimum at optimal capacity
 Then increases (moving toward overfitting)
 Forms characteristic U-shape
The U-Shaped Curve:

Error
|
| Training Error
| _________
| ______
| ______
|
| Test Error
|
|\/
|\/
|\/
| / ← Minimum (optimal capacity)
|/
|/
|/
|___________________ Capacity
Low Optimal High

Underfitting | Overfitting
Zone

Interpretation:

Zone 1: Low Capacity (Underfitting)

 Both training and test error are high

 Model too simple to capture patterns
 Need more capacity
Zone 2: Optimal Capacity

 Test error is minimized

 Training error is reasonably low
 Best generalization
 This is where we want to be!
Zone 3: High Capacity (Overfitting)

 Training error very low (near zero)

 Test error increases (poor generalization)
 Large gap between training and test error
 Model memorizing instead of learning
Why This Happens:

As capacity increases:

1. Model fits training data better → training error ↓

2. Initially, better fit means better generalization → test error ↓
3. Eventually, model starts fitting noise → test error ↑
4. But noise doesn't generalize → gap widens
Mathematical Insight:
The training error is a biased estimate of test error:

 Always underestimates true generalization error

 Bias increases with model capacity
 Larger gap at higher capacities
Practical Implication:

We cannot choose model capacity based on training error alone (would always choose
maximum capacity). Instead, we use validation set to find optimal capacity where test error
is minimized.

5.3 HYPERPARAMETERS AND VALIDATION SETS

What are Hyperparameters?

Definition: Settings that control the learning algorithm but are not learned from the
training data.

Key Distinction:

Parameters (learned from data):

 Weights in neural networks

 Coefficients in linear regression
 Means and variances in Gaussian models
 Optimized during training to minimize loss
Hyperparameters (set before training):

 Learning rate
 Number of hidden layers
 Regularization strength
 Polynomial degree
 Not optimized automatically - must be chosen
Common Examples:

1. Model Structure:

 Number of layers in neural network

 Number of units per layer
 Degree of polynomial
2. Regularization:

 λ (lambda): Regularization strength

 Dropout rate
 Weight decay coefficient
3. Optimization:

 Learning rate (α or η)
 Batch size
 Number of training epochs
 Momentum coefficient
4. Algorithm-Specific:

 k in k-nearest neighbors
 Number of clusters in k-means
 Maximum depth of decision tree
 Kernel type in SVM

Why Not Use Training Data to Set Hyperparameters?

The Problem:

If we use training error to choose hyperparameters, we would always select maximum

capacity, leading to severe overfitting.

Example:

Testing different polynomial degrees on training data:

Polynomial Degree | Training Error

1 | 0.50
2 | 0.35
5 | 0.20
10 | 0.10
20 | 0.02 ← Lowest training error!

Using training error, we'd choose degree 20.

But on test data:

Polynomial Degree | Test Error
1 | 0.55
2 | 0.40
5 | 0.25 ← Actually best!
10 | 0.45
20 | 0.90 ← Terrible!

Why This Happens:

 Training error always decreases with capacity

 Higher capacity = better fit to training data
 But better fit to training ≠ better generalization
 Would systematically overfit

The Three-Dataset Solution

To properly tune hyperparameters while getting unbiased performance estimates, we split
data into three separate sets:

1. Training Set (60-80% of data)

Purpose: Learn model parameters

 Optimize weights and biases

 Fit the model to data
 Minimize training loss
Usage:

 Used repeatedly during training

 Gradients computed on this data
 Parameters updated based on this data
Example: If we have 10,000 images:

 Training set: 7,000 images

 Used to learn which features indicate each class
2. Validation Set (10-20% of data)

Purpose: Tune hyperparameters and perform model selection

 Decide which model architecture to use

 Choose regularization strength
 Determine when to stop training
 Compare different approaches
Usage:

 Evaluate performance during development

  Try different hyperparameter values
 Select best configuration
 Can be used multiple times for different experiments
Example:

 Validation set: 1,500 images

 Train model with λ = 0.01 → validation accuracy 85%
 Train model with λ = 0.001 → validation accuracy 88%
 Train model with λ = 0.0001 → validation accuracy 86%
 Choose λ = 0.001 (best validation performance)
3. Test Set (10-20% of data)

Purpose: Final evaluation ONLY

 Provide unbiased estimate of generalization

 Simulate real-world deployment
 Report final performance
Critical Rules:

 Use exactly once at the very end

 Never used during training or tuning
 No decisions made based on test set
 Kept completely separate until final evaluation
Example:

 Test set: 1,500 images

 Only touched at the end
 Final accuracy: 87.5%
 This is our honest estimate of real-world performance
Why Three Sets?

What happens with only two sets?

Scenario 1: Training + Test Only

Train on training set

Evaluate on test set
Adjust hyperparameters based on test performance
Re-train and re-evaluate on test set
Repeat...

Problem: Eventually overfit to test set!

Test set no longer provides unbiased estimate.

What happens with three sets?

Scenario 2: Training + Validation + Test

Train on training set

Evaluate on validation set
Adjust hyperparameters based on validation performance
Re-train and re-evaluate on validation set
Repeat until satisfied...
→ May overfit to validation set, but that's okay!

Final evaluation on test set (once)

→ Test set still provides unbiased estimate!

Practical Split Example:

Total dataset: 10,000 examples

Split 1: 70-15-15

 Training: 7,000 examples (70%)

 Validation: 1,500 examples (15%)
 Test: 1,500 examples (15%)
Split 2: 60-20-20 (when more tuning needed)

 Training: 6,000 examples (60%)

 Validation: 2,000 examples (20%)
 Test: 2,000 examples (20%)
Split 3: 80-10-10 (when data is limited)

 Training: 8,000 examples (80%)

 Validation: 1,000 examples (10%)
 Test: 1,000 examples (10%)
Guidelines for Choosing Split:

 More training data → better learning

 More validation data → more reliable tuning
 More test data → more reliable final estimate
  Typical default: 70-15-15 or 60-20-20

Cross-Validation
Motivation: When data is limited, a single validation split may be unreliable or wasteful.

Problem with Single Split:

 Validation set is small → high variance in estimates

 Some data "wasted" (not used for training or final evaluation)
 Performance estimate depends on luck of the split
Solution: k-Fold Cross-Validation

Procedure:

1. Divide data into k equal-sized parts (folds)

o Common choices: k = 5 or k = 10
o Each fold has m/k examples
2. For each fold i = 1 to k:

o Use fold i as validation set

o Use all other k-1 folds as training set
o Train model and evaluate on validation fold
o Record validation performance
3. Average performance across all k folds

o Final estimate = mean of k validation scores

o Can also compute standard deviation (uncertainty)
Example: 5-Fold Cross-Validation

Total data: 10,000 examples → Each fold has 2,000 examples

Fold 1: [Val ][Train][Train][Train][Train]

Accuracy: 86%

Fold 2: [Train][Val ][Train][Train][Train]

Accuracy: 88%

Fold 3: [Train][Train][Val ][Train][Train]

Accuracy: 87%

Fold 4: [Train][Train][Train][Val ][Train]

Accuracy: 89%
Fold 5: [Train][Train][Train][Train][Val ]
Accuracy: 85%

Final estimate: (86 + 88 + 87 + 89 + 85) / 5 = 87%

Standard deviation: 1.6%

Advantages:

1. Better Data Utilization

 Every example used for both training and validation

 No data "wasted"
 Especially valuable with limited data
2. More Reliable Estimate

 Average over k trials reduces variance

 Less dependent on single lucky/unlucky split
 Confidence interval from standard deviation
3. Detects Instability

 High variance across folds → model unstable

 Consistent performance → model robust
 Example: 87% ± 15% suggests problem
Disadvantages:

1. Computational Cost

 Must train k times (5-fold = 5× slower)

 Can be prohibitive for large models
 Not always feasible
2. Still Need Separate Test Set

 Cross-validation for hyperparameter tuning

 Final evaluation requires unseen test set
 Three-way split still needed
Variants:

Leave-One-Out Cross-Validation (LOOCV):

 k = m (number of examples)
 Each example is validation set once
  Maximum data utilization
 Extremely expensive (m training runs)
Stratified Cross-Validation:

 Maintains class proportions in each fold

 Important for imbalanced datasets
 Ensures representative splits
Typical Workflow:

1. Split data: Training+Validation (80%) | Test (20%)

2. On Training+Validation:

o Use 5-fold cross-validation

o Try hyperparameter 1 → CV score: 85%
o Try hyperparameter 2 → CV score: 87%
o Try hyperparameter 3 → CV score: 86%
o Select hyperparameter 2 (best CV score)
3. Train final model:

o Use hyperparameter 2
o Train on full Training+Validation set (80%)
4. Evaluate once on Test set:

o Final performance: 86.5%

Regularization
Definition: Modifications to the learning algorithm that reduce test error at the expense
of increasing training error.

Goal: Prevent overfitting by controlling model complexity.

Core Idea: Add constraints or penalties to discourage overly complex solutions.

Why It Works:

 Overfitting occurs when model is too flexible

 Regularization reduces effective capacity
 Encourages simpler, smoother functions
 Simpler functions generalize better
Weight Decay (L2 Regularization)
Most Common Form of Regularization

Standard Loss Function (without regularization):

J(θ) = Loss(θ)
= (1/m) Σᵢ L(f(x⁽ⁱ⁾; θ), y⁽ⁱ⁾)

Regularized Loss Function:

J(θ) = Loss(θ) + λ||θ||²

Where:

 Loss(θ): Original loss (MSE, cross-entropy, etc.)

 λ: Regularization strength (hyperparameter ≥ 0)
 ||θ||²: L2 norm squared = Σⱼ θⱼ²
How It Works:

1. Penalty for Large Weights

Original goal: Minimize Loss
New goal: Minimize Loss + λ(sum of squared weights)

Trade-off:

 Decreasing loss → better fit to training data

 Increasing weight penalty → simpler model
 λ controls the balance
2. Effect on Optimization
Without regularization:

 Weights can grow arbitrarily large

 Complex, wiggly functions possible
With regularization:

 Weights pushed toward zero

 Smoother, simpler functions preferred
 Trade training accuracy for generalization
Intuition: Smoothness

Large Weights → Sharp Changes:

y = 1000x
Small change in x → huge change in y
Sensitive to input variations

Small Weights → Gradual Changes:

y = 0.5x
Small change in x → small change in y
Less sensitive, more robust

Smoother functions typically generalize better because they don't react strongly to noise.

Example: Polynomial Regression

Without Regularization (λ = 0):

Polynomial: y = 5x - 200x² + 1500x³ - 3000x⁴
Large coefficients → Wild oscillations

Training error: 0.01 (fits training points perfectly)

Test error: 0.90 (terrible generalization)

With Regularization (λ = 0.1):

Polynomial: y = 2x - 3x² + 0.5x³ - 0.1x⁴
Smaller coefficients → Smoother curve

Training error: 0.15 (slightly worse fit)

Test error: 0.25 (much better generalization!)

Choosing λ (Regularization Strength):

λ = 0: No regularization

 Full model capacity

 Risk of overfitting
 Training error very low
 Test error may be high
λ very small (e.g., 0.001):

 Weak regularization
 Nearly full capacity
 Slight improvement in generalization
λ moderate (e.g., 0.1):

 Balanced regularization
 Reduced capacity
 Good generalization
 Often optimal
λ very large (e.g., 100):

 Strong regularization
  Severely reduced capacity
 Risk of underfitting
 Both training and test error high
Finding Optimal λ:

 Use validation set or cross-validation

 Try multiple values: [0.001, 0.01, 0.1, 1, 10]
 Plot validation error vs λ
 Choose λ with lowest validation error
Other Regularization Techniques:

1. L1 Regularization (Lasso)
Penalty: λ Σⱼ |θⱼ|
Effect: Encourages sparse solutions (many weights exactly zero)
Use: Feature selection, interpretability

2. Early Stopping
Method: Stop training before convergence
Effect: Prevents overfitting to training data
Advantage: Simple, no additional hyperparameter

3. Dropout
Method: Randomly ignore units during training
Effect: Prevents co-adaptation, ensemble effect
Common: Neural networks (drop 20-50% of units)

4. Data Augmentation
Method: Create more training examples artificially
Examples: Rotate/flip images, add noise to audio
Effect: Increases effective training set size

5. Ensemble Methods
Method: Combine multiple models
Examples: Bagging, boosting, stacking
Effect: Averages out individual model errors

5.4. ESTIMATORS, BIAS AND VARIANCE

Point Estimation
Context: In machine learning, we often want to estimate unknown quantities from data.

Definition: Using data to provide a single "best guess" of an unknown parameter.

Key Concepts:

Parameter (θ):

 True value we want to know

 Usually unknown and fixed
 Examples:
o Mean height of all humans
o True error rate of an algorithm
o Probability it will rain tomorrow
Estimator (θ̂ₘ):

 A function that takes data and produces an estimate

 Notation: "theta hat subscript m"
 m = number of data samples used
 Random variable (changes with different datasets)
 The function itself, not a specific value
Estimate:

 Actual numerical value produced by estimator on specific data

 Not random (it's a realized value)
 Example: θ̂₁₀₀ = 170.5 cm
Formal Definition:

Estimator: θ̂ₘ = g(x⁽¹⁾, x⁽²⁾, ..., x⁽ᵐ⁾)

Where:

 g: Function that processes data

 x⁽¹⁾, ..., x⁽ᵐ⁾: Data samples
 θ̂ₘ: Resulting estimate
Example: Estimating Population Mean Height

True Parameter:
θ = Mean height of all humans
Unknown! We want to estimate it.

Estimator:
Sample Mean: θ̂ₘ = (1/m) Σᵢ₌₁ᵐ xᵢ

Where:
  m: Number of people measured
 xᵢ: Height of person i
Process:
Sample 1: Measure 100 people
→ θ̂₁₀₀ = 170.2 cm (this is an estimate)

Sample 2: Measure different 100 people

→ θ̂₁₀₀ = 169.8 cm (different estimate!)

Sample 3: Measure another 100 people

→ θ̂₁₀₀ = 170.5 cm (different again!)

The function (sample mean) is the estimator.

The specific numbers (170.2, 169.8, 170.5) are estimates.

Properties We Care About:

Different estimators for the same parameter can have different properties. We want
estimators that:

1. Are correct on average (unbiased)

2. Don't vary too much between samples (low variance)
3. Get better with more data (consistent)
4. Are efficient (converge quickly)

Bias

Bias refers to the error introduced by approximating a real-world problem (which may be complex)
with a simpler model. In statistical estimation, bias is the difference between the expected (average)
prediction of our model and the correct value we are trying to predict.

 Mathematical Definition: For an estimator 𝜃ˆ, bias is given bybias(𝜃ˆ) = 𝔼[𝜃ˆ] − 𝜃where 𝔼[𝜃ˆ ]
is the expected value of the estimator, and 𝜃 is the true parameter value.

 High Bias means that the model makes strong assumptions about the data and is too simple,
often missing the underlying trend (underfitting).

 Example: Using a straight line (linear model) to fit data generated from a quadratic function
causes consistently wrong predictions—this is high bias.
Variance

Variance in machine learning measures the amount by which the estimation of the target function will
change if different training data was used. It quantifies how much the model’s predictions fluctuate for
different datasets.

 Mathematical Definition:Var(𝜃ˆ) = 𝔼[(𝜃ˆ − 𝔼[𝜃ˆ])2 ]

 High Variance implies that the model captures noise in the training data, causing overfitting
(model performs very well on training data but poorly on new, unseen data).

 Example: A highly flexible model (e.g., a high-degree polynomial) fits noise in the training set
and changes drastically with new datasets.

Bias-Variance Tradeoff

The bias-variance tradeoff is a fundamental concept that describes the inverse relationship between
bias and variance. As model complexity increases:

 Bias decreases (the model fits data better)

 Variance increases (the model may fit noise)

The goal is to find a balance where both bias and variance are minimized to achieve the lowest Mean
Squared Error (MSE):

MSE = (Bias)2 + Variance

 Underfitting: High bias, low variance (simple model)

 Overfitting: Low bias, high variance (complex model)

 Good Generalization: Intermediate complexity, both bias and variance are low.

Maximum Likelihood Estimation (MLE)

Maximum Likelihood Estimation (MLE) is a method to estimate the parameters of a statistical

model so that the observed data is most probable under the model.
  Likelihood Function: For data 𝒟 = {𝑥 (1) , 𝑥 (2) , . . . , 𝑥 (𝑚) }, parameterized by 𝜃:𝐿(𝜃) =
𝑃(𝒟|𝜃) = ∏𝑚 (𝑖)
𝑖=1 𝑝(𝑥 |𝜃)

 Log-Likelihood (used for convenience due to product of probabilities):log⁡𝐿(𝜃) =

∑𝑚 (𝑖)
𝑖=1 log⁡𝑝(𝑥 |𝜃)

 MLE Solution: Choose 𝜃𝑀𝐿 that maximizes log-likelihood:𝜃𝑀𝐿 = arg⁡max log⁡𝐿(𝜃)

𝜃

 Properties: Under general conditions, MLE is consistent (approaches true value with enough
data) and asymptotically efficient (achieves lowest possible variance among estimators).

5.6 Bayesian Statistics

Bayesian statistics involves using probability distributions to represent all uncertainty within a model,
including model parameters.

 Prior (𝑝(𝜃)): Initial belief about parameters before seeing data.

 Likelihood (𝑝(𝒟|𝜃)): The probability of observed data given parameters.

 Posterior (𝑝(𝜃|𝒟)): Updated belief about parameters after observing the data, calculated by
𝑝(𝒟|𝜃)⋅𝑝(𝜃)
Bayes’ Rule:𝑝(𝜃|𝒟) = 𝑝(𝒟)
where 𝑝(𝒟) = ∫ ⁡ 𝑝(𝒟|𝜃)𝑝(𝜃)𝑑𝜃 is a normalizing constant.

 MAP (Maximum A Posteriori): Mode of the posterior, combines MLE with prior information.

 Advantages: Naturally handles model uncertainty and incorporates prior knowledge; predicts by
integrating over all parameter values.

5.7 Supervised Learning Algorithms

Supervised learning uses labeled datasets, where each example is a pair (𝑥, 𝑦), to learn functions that
map inputs to outputs.

Key Algorithms:

 Linear Regression: Predicts real-valued outputs 𝑦 from input 𝑥 by fitting a linear function.

 Logistic Regression: Used for binary classification; models the probability that 𝑦 = 1 given 𝑥.
  Support Vector Machines (SVMs): Find the separating hyperplane with the largest margin
between categories.

 k-Nearest Neighbors (k-NN): Classifies based on labels of the 𝑘 closest training examples in
the feature space.

 Decision Trees: Recursive partitioning of the input space to create rules for predicting the
output.

Each algorithm has tradeoffs regarding bias-variance, interpretability, and suitability for different types
of data.

5.9 Stochastic Gradient Descent (SGD)

Stochastic Gradient Descent (SGD) is an optimization method for minimizing loss functions in
machine learning, particularly effective for large datasets.

 Instead of computing the gradient on the entire dataset (as with batch gradient descent), it
computes the gradient on a small, random subset (minibatch) in each iteration.

 Update Rule:𝜃 ← 𝜃 − 𝜖∇𝜃 𝐿(𝑓(𝑥 (𝑖) ; 𝜃), 𝑦 (𝑖) )Where 𝜖 is the learning rate, and ∇𝜃 denotes the
gradient with respect to parameters.

 Advantages:

o Faster updates, suitable for online/large-scale learning

o May escape shallow local minima due to noisy updates

 Convergence: Depends on learning rate schedule; usually learning rate decreases over time.

Manifold Learning

Manifold learning is based on the idea that high-dimensional data (like images, audio, or text) often
lie along lower-dimensional, smooth surfaces (manifolds) within their high-dimensional space.

 Manifold Hypothesis: Real-world data does not fill all of high-dimensional space but is
concentrated near a low-dimensional manifold.

 Implications:

o Dimensionality reduction techniques (like PCA) can find better data representations.
 o Helps explain why learning from high-dimensional data is possible and why models can
generalize despite the “curse of dimensionality.”

 Common Techniques:

o Principal Component Analysis (PCA): Projects data onto directions of maximal variance.

o t-SNE, Isomap: Nonlinear techniques for visualizing and understanding data manifolds.

5.10 Building a Machine Learning Algorithm

A typical machine learning algorithm can be constructed using four main
components:
1. Model:
 The function or decision rule that maps inputs to outputs.
 Example: In linear regression, the model is 𝑦 = 𝑤 𝑇 𝑥 + 𝑏, where 𝑤 and 𝑏 are
parameters that determine predictions based on input features.[1]
2. Cost (or Loss) Function:
 Quantifies how well the model's predictions match the actual outputs.
 Common examples:
o Mean Squared Error (MSE) for regression
o Negative Log-Likelihood for probabilistic modeling
o Cross-Entropy for classification
3. Optimization Procedure:
 The method used to update model parameters to minimize the cost function.
 Example: Gradient Descent or Stochastic Gradient Descent (SGD).[1]
4. Dataset:
 The data used for learning, split into training, validation, and test sets (e.g., Training
set for learning, Validation set for tuning hyperparameters, and Test set for final
evaluation).
Algorithm Construction Recipe:
A machine learning algorithm can be built by combining:
 The dataset,
 A model specification,
 A cost function,
 An optimizer to adjust model parameters.
Example - Linear Regression:
 Model: Linear function (𝑦 = 𝑤 𝑇 𝑥 + 𝑏)
 Dataset: Set of labeled examples (𝑥, 𝑦)
 Cost Function: Mean Squared Error between predicted and actual 𝑦
 Optimization: Solve for weights with gradient descent or normal equations.[1]
This modular approach supports both supervised and unsupervised learning and
allows easy substitution of each component for different tasks.

5.11 Challenges Motivating Deep Learning

Although traditional algorithms like linear regression, logistic regression, SVM, and
k-NN work well for many problems, several key challenges motivated the
development of deep learning:
1. Curse of Dimensionality:
 As data dimensionality increases, the number of possible configurations grows
exponentially, making learning and generalization extremely difficult.[1]
 Example: In image recognition, each pixel is a dimension; for a 100×100 pixel image,
there are 10,000 dimensions!
2. Local Generalization:
 Algorithms relying only on local smoothness or template matching (like k-NN or
kernel machines) struggle to generalize to new, unseen cases when data is spread
across high-dimensional space.[1]
3. Representation Power:
 Traditional algorithms often require feature engineering or transformations designed
by human experts for each domain (speech, vision, text), making them less flexible
and harder to scale.[1]
 Deep learning models automatically learn abstract features from raw data, reducing
reliance on hand-engineered features.
4. Scalability:
 Some algorithms (e.g., kernel methods) require computations that scale poorly with
dataset size, limiting their applicability to big data.
 Deep learning with SGD and similar techniques can handle massive datasets
efficiently.[1]
5. Nonlinear Complexity:
 Many tasks (e.g., speech recognition, object detection) require complex nonlinear
functions that shallow algorithms cannot represent.
 Deep architectures can capture highly nonlinear relationships by stacking multiple
layers.[1]
 6. Distributed Representations:
 Real-world data often lies on low-dimensional manifolds within high-dimensional
space (“manifold hypothesis”).
 Deep learning excels in discovering such representations, enabling better
generalization to new examples.
Summary:
Deep learning was motivated by the need to overcome shallow algorithms’ limits in
high-dimensional data, feature engineering, and complex tasks, leading to new
methods that can efficiently model, represent, and generalize in flexible ways,
especially for AI-level problems in vision, speech, and language.[1]