Task: Given features \(\mathbf{x} \in \mathbb{R}^d\), predict class \(y \in \{0, 1\}\)

Classical approach: Find decision boundary

Probabilistic approach: Estimate \(P(y=1|\mathbf{x})\)

Main challenges:

1. How do we model \(P(y|\mathbf{x})\)?
2. What loss function captures objective?
3. What threshold \(\tau\) minimizes expected cost?

Classification pipeline:

1. Model: Estimate \(P(y=1|\mathbf{x})\)
2. Training: Learn parameters from data
3. Inference: Compute \(p = P(y=1|\mathbf{x}_{\text{new}})\)
4. Decision: Choose \(\hat{y} \in \{0, 1\}\)

The decision rule maps \(p\) to \(\hat{y}\):

Simple threshold:

This assumes all errors cost the same

Example: Credit card fraud

• False positive: Block legitimate transaction ($10 cost)
• False negative: Approve fraud ($1000 loss)

Optimal threshold depends on these costs

Different thresholds lead to different decisions

1. States (observations): \(\Omega = \{\omega_1, \omega_2, \ldots\}\)

   • True class labels: \(y \in \{0, 1\}\) or \(\{1, 2, \ldots, K\}\)

2. Actions: \(\mathcal{A} = \{a_1, a_2, \ldots\}\)

   • Predicted labels: \(\hat{y}\)
   • Or “reject” option (defer to human)

3. Decision rule: \(\delta: \mathcal{X} \to \mathcal{A}\)

   • Maps observations to actions

4. Loss function: \(L: \Omega \times \mathcal{A} \to \mathbb{R}\)

   • Cost of action \(a\) when true state is \(\omega\)

Objective: Minimize expected loss

Bayes risk: Minimum achievable expected loss

Bayes risk minimization:

Given observation \(\mathbf{x}\), choose action to minimize expected loss:

Expanding the expectation:

For binary classification with \(y \in \{0, 1\}\):

where \(p = P(Y=1|\mathbf{x})\)

Optimal decisions depend on:

1. Posterior probabilities \(P(Y=k|\mathbf{x})\)
2. Loss function \(L(k, a)\)

Bayes rule minimizes expected loss at each point

0-1 Loss (uniform error cost):

Expected loss for action \(a\):

Minimizing expected loss:

This is the MAP rule!

MAP minimizes error probability when all errors cost the same

Bayes error rate (irreducible error):

No classifier can do better — this is the error from class overlap

Each region: highest posterior probability wins

Binary Bayes decision rule:

Choose class 1 if “expected loss of choosing 1” < “expected loss of choosing 0”:

where \(L_{ij}\) = loss of predicting \(j\) when true class is \(i\)

Using Bayes theorem:

Rearranging:

Likelihood Ratio Test:

where threshold \(\tau = \frac{L_{01}P(Y=0)}{L_{10}P(Y=1)}\)

Log-likelihood ratio (more stable):

Linear boundary in log-space → stability

Binary classification with costs:

where:

• \(c_{01}\): Cost of false positive (say 1 when true is 0)
• \(c_{10}\): Cost of false negative (say 0 when true is 1)

Expected loss of predicting 1:

Expected loss of predicting 0:

Optimal decision: Predict 1 if \(R_1(\mathbf{x}) < R_0(\mathbf{x})\)

Optimal threshold: \(\tau^* = \frac{c_{01}}{c_{01} + c_{10}}\)

Cancer screening scenario:

• State: Cancer (1) or Healthy (0)
• Action: Treat (1) or Don’t treat (0)

Realistic costs:

• False negative (miss cancer): Death = $1,000,000
• False positive (unnecessary treatment): $50,000
• True positive (treat cancer): $50,000
• True negative (no treatment): $0

Loss matrix:

Note: treatment cost even for true positives

Optimal threshold:

Treat if \(P(\text{cancer}|\text{test}) > 0.05\)

Three-way decision:

1. Predict class 0
2. Predict class 1
3. Reject (defer to expert)

Extended loss matrix:

where \(c_r\) = cost of rejection (expert review)

Decision regions:

• Predict 0 if \(p < \tau_1\)
• Reject if \(\tau_1 \leq p \leq \tau_2\)
• Predict 1 if \(p > \tau_2\)

Optimal thresholds (for symmetric costs):

Reject when model confidence is low

Reject option reduces error on uncertain samples

Hard decisions: \(\hat{y} \in \{0, 1, ..., K-1\}\)

• Single class prediction
• Required for final action
• Information loss through discretization

Soft decisions: \(\mathbf{p} = [p_0, p_1, ..., p_{K-1}]\)

• Full distribution of outcomes
• Preserves uncertainty information
• Useful for downstream processing

Soft decisions ideal for:

1. Cascaded systems: Next stage uses probabilities

   • Speech recognition → language model
   • Object detection → tracking

2. Confidence assessment: Reliability measures

   • Medical diagnosis (refer if uncertain)
   • Autonomous driving (hand off to human)

3. Cost-sensitive decisions: Context-dependent losses

   • Fraud detection (amount matters)
   • Email filtering (sender importance)

4. Ensemble methods: Combining multiple models

1. Discrimination (ranking ability):

• ROC curve: TPR vs FPR
• AUC: Area under ROC
• Precision-Recall curve

2. Calibration (probability accuracy):

• Do predicted probabilities match frequencies?
• Among all \(\mathbf{x}\) where \(P(y=1|\mathbf{x}) = 0.7\), is the true fraction positive ≈ 70%?

3. Proper scoring rules:

• Log-loss: \(-\sum_i [y_i \log p_i + (1-y_i)\log(1-p_i)]\)
• Brier score: \(\sum_i (y_i - p_i)^2\)

These penalize both discrimination and calibration errors

Note: Good discrimination ≠ Good calibration

Imbalanced data: 99% negative, 1% positive

Problem with accuracy:

• Trivial classifier (always predict negative): 99% accurate
• Does not detect rare positive cases

Metrics for imbalanced data:

Precision: Of predicted positives, how many correct?

Recall (Sensitivity): Of true positives, how many found?

F1 Score: Harmonic mean

Connection to costs: Optimize threshold based on

where \(\pi\) = class prior P(y=1)

Try modeling probability directly:

With \(w = 0.3\), \(b = 0.5\):

• \(p(x=-2) = -0.1\) (invalid)
• \(p(x=0) = 0.5\)
• \(p(x=2) = 1.1\) (invalid)

Problem: Linear outputs \(\in (-\infty, \infty)\) but probabilities need \(\in [0, 1]\)

Need transformation \(\mathbb{R} \to [0, 1]\) that:

1. Outputs valid probabilities
2. Preserves linear decision boundaries
3. Is differentiable for optimization

Candidates:

• Threshold: \(p = \mathbb{1}[z > 0]\)
• Clamp: \(p = \max(0, \min(1, z))\) – Not differentiable
• Sigmoid: \(p = \frac{1}{1 + e^{-z}}\)

Odds: Alternative to probability

For binary outcome

Examples:

• \(p = 0.5\): Odds = 1 (1:1, “even odds”)
• \(p = 0.75\): Odds = 3 (3:1 in favor)
• \(p = 0.25\): Odds = 1/3 (1:3 against)

Range: \([0, \infty)\)

Log-odds (logit):

Range: \((-\infty, \infty)\)

Model log-odds linearly:

Solving for \(p(\mathbf{x})\):

Let \(z = \mathbf{w}^T\mathbf{x} + b\)

Gives the logistic (sigmoid) function

Inputs: \(\mathbf{x} = [x_1, x_2, \ldots, x_d]^T\)

Weights: \(\mathbf{w} = [w_1, w_2, \ldots, w_d]^T\)

Bias: \(b\)

Linear combination:

Activation function:

Output: \(p = P[\text{class 1}] \in (0, 1)\)

Decision rule: Predict class 1 if \(p > 0.5\)

Learning requires \(\frac{\partial \ell}{\partial \mathbf{w}}\). Since \(p = \sigma(\mathbf{w}^T\mathbf{x} + b)\), the chain rule needs \(\frac{d\sigma}{dz}\).

Start with: \(\sigma(z) = \frac{1}{1 + e^{-z}}\)

Apply chain rule:

Rewriting:

And:

This equals \(\sigma(-z) = 1 - \sigma(z)\)

Therefore:

Properties:

• Maximum at \(z = 0\)
  • \(\sigma'(0) = 0.25\)
• Symmetric around \(z = 0\)
• Vanishes as \(z \to \pm\infty\)

Computing \(p = \sigma(z)\) first gives derivative as \(p(1-p)\).

Other candidates that map \(\mathbb{R} \to [0,1]\):

Probit (cumulative normal):

• No closed form
• Derivative involves normal PDF
• Used in econometrics

Complementary log-log:

• Asymmetric
• Good for rare events
• Different tail behavior

Logistic function advantages:

1. Natural interpretation: Log-odds are intuitive
2. Simple derivative: \(\sigma'(z) = \sigma(z)(1-\sigma(z))\)
3. Computational efficiency: Closed form everything
4. Information theory: Maximizes entropy given constraints

The sigmoid function \(\sigma(z) = \frac{1}{1 + e^{-z}}\):

1. Valid probabilities: \(\sigma(z) \in (0, 1)\) always

2. Smooth and differentiable:

   \[\sigma'(z) = \sigma(z)(1 - \sigma(z))\]

3. Linear decision boundary:

   • Predict 1 if \(p > 0.5\)
   • This occurs when \(\mathbf{w}^T\mathbf{x} + b > 0\)
   • Boundary: \(\mathbf{w}^T\mathbf{x} + b = 0\) (hyperplane)

4. Interpretable coefficients:

   • \(w_j\) = change in log-odds per unit \(x_j\)
   • \(e^{w_j}\) = odds multiplication factor

Logistic regression assumes:

Nonlinear boundaries: Concentric classes, XOR — no linear \(f(\mathbf{x})\) works

• Best linear classifier on XOR: 50% accuracy
• More data doesn’t help — the model class is wrong

Outlier sensitivity: One extreme point pulls \(\|\mathbf{w}\| \to \infty\)

• MLE maximizes confidence on every sample
• No mechanism to downweight outliers

High dimensions (\(d > n\)): Perfect separation \(\Rightarrow\) \(\hat{\mathbf{w}}_{\text{MLE}}\) diverges

• 100 features, 80 samples: \(\|\mathbf{w}\|\) grows without bound
• Regularization (Section 5) fixes this

Misspecification: MLE finds best sigmoid approximation in KL divergence

Model: \(P(y=1|\mathbf{x}) = \sigma(\mathbf{w}^T\mathbf{x} + b)\)

Training data: \(\{(\mathbf{x}_i, y_i)\}_{i=1}^n\)

Objective: Find \(\mathbf{w}, b\) that make observed labels most probable

Equivalent to minimizing cross-entropy:

Gradient: \(\nabla_\mathbf{w} \ell = \sum_{i=1}^n (y_i - p_i)\mathbf{x}_i\)

Errors weighted by features — intuitive and cheap to compute

Problem: Classify emails as spam or legitimate

Features extracted from email:

• Word frequencies: “FREE”, “CLICK”, “offer”
• Sender reputation score
• Number of ALL CAPS words
• Exclamation marks count
• Links to external domains
• Time of day sent

Example vector \(\mathbf{x} \in \mathbb{R}^6\):

Email: "FREE OFFER! Click HERE!!!"
x = [2, 0.1, 2, 3, 1, 0.3]
     ↑   ↑   ↑   ↑   ↑   ↑
   FREE low  2   3   1   3am
   offer rep CAPS !!  link

In practice, \(d\) = 100–10,000 features (bag-of-words counts, TF-IDF weights, metadata)

Goal: Learn \(P(\text{spam}|\mathbf{x})\)

Spam filters use 1000s of features

Model:

Training (gradient ascent on log-likelihood):

# Initialize
w = np.random.randn(100) * 0.01
b = 0

for epoch in range(100):
    # Compute predictions
    z = X @ w + b
    p = sigmoid(z)

    # Gradient step
    grad_w = X.T @ (y - p) / n
    grad_b = np.mean(y - p)

    w += learning_rate * grad_w
    b += learning_rate * grad_b

Learned weights reveal spam indicators:

• \(w_{\text{FREE}} = 2.3\) (strong spam signal)
• \(w_{\text{meeting}} = -1.8\) (legitimate signal)
• \(w_{\text{sender_rep}} = -3.1\) (reputation matters)

Target: >95% detection, <0.1% false positive, <10ms latency

Inference for new email:

def classify_email(email_text, w, b):
    # Extract features
    x = extract_features(email_text)

    # Compute probability
    z = np.dot(w, x) + b
    p_spam = sigmoid(z)

    # Decision with threshold
    if p_spam > 0.95:  # High threshold
        return "spam", p_spam
    else:
        return "legitimate", p_spam

Example performance:

• Accuracy: 97.2%
• Spam recall: 95.1%
• False positive rate: 0.08%
• Inference time: 0.3ms per email

Advantages:

• Interpretable: see why email flagged
• Fast: millions of emails per second
• Updatable: online learning for new spam

Threshold tuning possible since calibrated probabilities

Bayes theorem for weights (i.e., parameters):

Maximum a posteriori (MAP):

With uniform prior \(P(\mathbf{w}) = \text{const}\):

“Find parameters that make observed data most probable”

MLE properties:

• Consistent: \(\hat{\mathbf{w}} \to \mathbf{w}^*\) as \(n \to \infty\)
• Efficient: Achieves lowest possible variance (Cramér-Rao bound)
• Invariant: Same estimate under reparameterizations
• Information-theoretic: Minimizes KL divergence to true distribution

For regression: Gaussian noise → squared loss

For classification: Bernoulli observations → cross-entropy loss

Each observation \(y_i \in \{0, 1\}\) is Bernoulli:

Compact form:

Check: \(y_i = 1\) gives \(p\), \(y_i = 0\) gives \(1-p\)

Likelihood (independent observations):

where \(p_i = \sigma(\mathbf{w}^T\mathbf{x}_i + b)\)

Log-likelihood (products become sums):

Why log?

• Products → sums (numerically stable)
• Same maximum (log is monotonic)
• Derivatives are simpler

Maximizing log-likelihood = Minimizing NLL:

This is binary cross-entropy loss

Dataset: 4 points in 1D

X = [-2, -1, 1, 2]
y = [0, 0, 1, 1]

Current Model: \(p(x) = \sigma(wx + b)\)

with \(w = 0.5\), \(b = 0\)

Compute predictions:

• \(z_1 = 0.5(-2) + 0 = -1\), \(p_1 = \sigma(-1) = 0.27\)
• \(z_2 = 0.5(-1) + 0 = -0.5\), \(p_2 = \sigma(-0.5) = 0.38\)
• \(z_3 = 0.5(1) + 0 = 0.5\), \(p_3 = \sigma(0.5) = 0.62\)
• \(z_4 = 0.5(2) + 0 = 1\), \(p_4 = \sigma(1) = 0.73\)

Errors \(y - p\):

• Point 1: \(0 - 0.27 = -0.27\)
• Point 2: \(0 - 0.38 = -0.38\)
• Point 3: \(1 - 0.62 = +0.38\)
• Point 4: \(1 - 0.73 = +0.27\)

Log-likelihood:

So:

• \(i=1\): \(0 \cdot \log(0.27) + 1 \cdot \log(0.73) = -0.31\)
• \(i=2\): \(0 \cdot \log(0.38) + 1 \cdot \log(0.62) = -0.48\)
• \(i=3\): \(1 \cdot \log(0.62) + 0 \cdot \log(0.38) = -0.48\)
• \(i=4\): \(1 \cdot \log(0.73) + 0 \cdot \log(0.27) = -0.31\)

Total: \(\ell = -1.58\)

Negative log-likelihood: \(\text{NLL} = 1.58\)

Minimize this loss function

Gradient formulas (from earlier):

For our example:

\(\frac{\partial \ell}{\partial w}\):

\(\frac{\partial \ell}{\partial b}\):

Computing contributions:

Sum: \(\nabla_w \ell = 1.84\)

1. Model: \(p = \sigma(\mathbf{w}^T\mathbf{x} + b)\)

2. Objective: Maximize log-likelihood

   \[\ell = \sum_{i=1}^n [y_i \log p_i + (1-y_i)\log(1-p_i)]\]

3. Gradient:

   \[\nabla_\mathbf{w} \ell = \mathbf{X}^T(\mathbf{y} - \mathbf{p})\]

4. Update: Gradient ascent

   \[\mathbf{w} \leftarrow \mathbf{w} + \eta \nabla_\mathbf{w} \ell\]

5. Converge: When \(||\nabla \ell|| < \epsilon\)

Iterate until convergence (typical: 100s of steps)

Standard initialization:

w = np.random.randn(d) * 0.01
b = 0

Why random: Zero works but random is standard

• Gradient: \(\nabla_\mathbf{w} \ell = \mathbf{X}^T(\mathbf{y} - \mathbf{p})\)
  • Gradient depends only on data, not symmetry
  • With \(\mathbf{w} = \mathbf{0}\): all predictions \(p_i = 0.5\)
• Works for logistic regression (unlike neural networks)
• Random initialization is standard practice

Why small (0.01 scale):

• Prevents sigmoid saturation: \(\sigma(z) \approx 0\) or \(1\) when \(|z|\) large
• Keeps gradients large: \(\sigma'(z) = \sigma(z)(1-\sigma(z))\) peaks at \(z=0\)
• Scale of 0.01 typical for normalized features

Update rule (minimize NLL):

Addition follows from maximizing log-likelihood (equivalent to subtracting gradient of NLL)

With learning rate \(\eta = 0.5\):

• \(w^{\text{new}} = 0.5 + 0.5 \cdot 1.84 = 1.42\)
• \(b^{\text{new}} = 0 + 0.5 \cdot 0 = 0\)

New predictions:

• \(p_1^{\text{new}} = \sigma(1.42 \cdot (-2)) = 0.055\)
• \(p_2^{\text{new}} = \sigma(1.42 \cdot (-1)) = 0.195\)
• \(p_3^{\text{new}} = \sigma(1.42 \cdot 1) = 0.805\)
• \(p_4^{\text{new}} = \sigma(1.42 \cdot 2) = 0.945\)

NLL decreased from 1.582 to 0.506

Hessian = matrix of second derivatives

For logistic regression:

For our 1D example with current \(p = [0.27, 0.38, 0.62, 0.73]\):

Weights: \(p_i(1-p_i)\)

• Point 1: \(0.27(0.73) = 0.197\)
• Point 2: \(0.38(0.62) = 0.236\)
• Point 3: \(0.62(0.38) = 0.236\)
• Point 4: \(0.73(0.27) = 0.197\)

Hessian matrix:

For NLL minimization, consider \(-\mathbf{H}\):

Positive definite → Convex

Generalize to \(n\) samples, \(d\) features:

Data matrix: \(\mathbf{X} \in \mathbb{R}^{n \times d}\)

Predictions: \(\mathbf{p} = \sigma(\mathbf{X}\mathbf{w} + b)\)

Gradient:

This equals \(\sum_{i=1}^n (y_i - p_i)\mathbf{x}_i\)

Hessian:

where \(\mathbf{D} = \text{diag}(p_1(1-p_1), \ldots, p_n(1-p_n))\)

Example for our 4-point dataset:

Theorem: NLL is strictly convex if \(\mathbf{X}\) has full rank.

Proof sketch:

1. Hessian: \(\mathbf{H} = -\mathbf{X}^T\mathbf{D}\mathbf{X}\)

2. For any \(\mathbf{v} \neq \mathbf{0}\):

   \[\mathbf{v}^T(-\mathbf{H})\mathbf{v} = \mathbf{v}^T\mathbf{X}^T\mathbf{D}\mathbf{X}\mathbf{v}\]

3. Let \(\mathbf{u} = \mathbf{X}\mathbf{v}\):

   \[= \mathbf{u}^T\mathbf{D}\mathbf{u} = \sum_{i=1}^n p_i(1-p_i)u_i^2\]

4. Since \(0 < p_i < 1\): all \(p_i(1-p_i) > 0\)

5. Sum of positive terms → \(\geq 0\)

6. Equals 0 only if \(\mathbf{u} = \mathbf{0}\)

7. If \(\mathbf{X}\) full rank: \(\mathbf{X}\mathbf{v} = \mathbf{0} \Rightarrow \mathbf{v} = \mathbf{0}\)

8. Therefore: \(-\mathbf{H} \succ 0\) (positive definite)

Convexity implications:

Gradient Descent:

• Linear convergence: \(\epsilon_{t+1} \leq \rho \cdot \epsilon_t\)
• Rate depends on condition number
• Many iterations needed
• Simple, memory efficient

Newton’s Method:

• Quadratic convergence: \(\epsilon_{t+1} \leq c \cdot \epsilon_t^2\)
• Few iterations (5-10 typical)
• Each iteration expensive: \(O(d^3)\)
• Needs to store/invert Hessian

Trade-off:

• Small \(d\) (<1000): Use Newton
• Large \(d\): Use gradient methods
• Very large \(d\): Use stochastic gradient

Fisher Information measures parameter certainty:

At convergence for our example:

• \(w^* \approx 2.2\), \(b^* \approx 0\)
• \(p^* = [0.013, 0.050, 0.950, 0.987]\)

Weights at optimum:

• Points 1,4: \(p(1-p) \approx 0.013\) (low)
• Points 2,3: \(p(1-p) \approx 0.048\) (low)

Low weights everywhere → High certainty

Asymptotic distribution:

High Fisher information → Low variance → Confident estimates

One-vs-Rest approach:

• Train K binary classifiers
• Classifier k: class k vs all others
• Predict: argmax of K outputs

Problem: Probabilities do not sum to 1

Example with 3 classes:

• Classifier 0: P(0 vs rest) = 0.7
• Classifier 1: P(1 vs rest) = 0.6
• Classifier 2: P(2 vs rest) = 0.4

Sum = 1.7 ≠ 1

Not valid probabilities for the K classes

1. Valid probabilities: All outputs in (0,1), sum to 1

   \[\sum_{k=1}^K \text{softmax}(\mathbf{z})_k = 1\]

2. Preserves order: If \(z_i > z_j\), then \(p_i > p_j\)

3. Translation invariant:

   \[\text{softmax}(\mathbf{z} + c) = \text{softmax}(\mathbf{z})\]

   Since: \(\frac{e^{z_k + c}}{\sum_j e^{z_j + c}} = \frac{e^c \cdot e^{z_k}}{e^c \cdot \sum_j e^{z_j}} = \frac{e^{z_k}}{\sum_j e^{z_j}}\)

4. Temperature scaling:

   \[\text{softmax}(\mathbf{z}/T)\]
   • \(T \to 0\): approaches argmax (one-hot)
   • \(T \to \infty\): uniform distribution

For K classes, we need:

• K linear models: \(z_k = \mathbf{w}_k^T\mathbf{x} + b_k\)
• Parameter matrix: \(\mathbf{W} \in \mathbb{R}^{d \times K}\)
• Bias vector: \(\mathbf{b} \in \mathbb{R}^K\)

Model:

Over-parameterized:

• Can set \(\mathbf{w}_K = \mathbf{0}\), \(b_K = 0\) (reference class)
• Still get valid probabilities
• Reduces parameters by \(d+1\)

Each boundary is linear (hyperplane)

One-hot encoding for labels:

• Class 0: \(\mathbf{y} = [1, 0, 0]\)
• Class 1: \(\mathbf{y} = [0, 1, 0]\)
• Class 2: \(\mathbf{y} = [0, 0, 1]\)

Cross-entropy loss:

Since only one \(y_k = 1\):

For entire dataset:

where \(p_{i,y_i}\) is predicted probability for true class of sample \(i\)

Data: 3 points, 3 classes

X = [[1, 0], [-1, 0], [0, 1]]
y = [0, 1, 2]  # Class labels

Current parameters:

W = [[0.5, 0.2, 0],    # w for class 0
     [0.1, 0.3, 0]]    # w for class 1,2
b = [0.1, 0, -0.1]

Computing predictions:

Point 1: \(\mathbf{x} = [1, 0]\)

• \(z_0 = 0.5(1) + 0.1(0) + 0.1 = 0.6\)
• \(z_1 = 0.2(1) + 0.3(0) + 0 = 0.2\)
• \(z_2 = 0(1) + 0(0) - 0.1 = -0.1\)
• \(\mathbf{p} = \text{softmax}([0.6, 0.2, -0.1]) = [0.47, 0.32, 0.21]\)
• True class: 0, Loss: \(-\log(0.47) = 0.76\)

Perfect separation scenario:

# 2D data with polynomial features
X = [[-2, -1], [-1, -2], [1, 2], [2, 1]]
y = [0, 0, 1, 1]
# Add polynomial features
X_poly = [[x1, x2, x1², x2², x1x2] 
          for x1, x2 in X]

With 5 features for 4 points:

• Can achieve perfect separation
• MLE drives weights → ∞
• Predictions become 0 or 1 exactly
• No unique solution

The problem:

• Loss keeps decreasing: NLL → 0
• But weights explode: ||w|| → ∞
• Model becomes overconfident
• Poor generalization to new data

As ||w|| increases:

• Decision boundary sharpens
• Probabilities → 0 or 1
• Model becomes “too sure”

Example: 100 features, 80 samples

Without regularization:

n, d = 80, 100  # More features than samples
X = np.random.randn(n, d)
y = (X @ w_true + noise > 0).astype(int)

What happens during optimization:

1. Early iterations: Reasonable weights
2. Middle: Some weights grow large
3. Late: Many weights explode
4. “Solution”: Perfect training accuracy
5. But: Poor generalization (test performance)

Weight explosion occurs when:

• \(d > n\) (more features than samples)
• Features are highly correlated
• Perfect or near-perfect separation exists

Loss decreases but weights are unstable.

Modified objective:

Gradient with regularization:

Compare to unregularized:

Effect: Pull weights toward zero

Update rule:

Weight decay: Shrink by factor \((1 - 2\eta\lambda)\)

L2 Regularization = Bias toward smaller weights.

Larger λ → Smaller weights → More stable model

L2 regularization = Gaussian prior

Prior on weights:

MAP estimation:

Taking logarithm:

With \(\lambda = \frac{1}{2\sigma^2}\):

This is Ridge regression

Smaller σ gives stronger regularization

LASSO (Least Absolute Shrinkage and Selection Operator)

L1 penalty:

Subgradient (not differentiable at 0):

where \(\text{sign}(w) = \begin{cases} +1 & w > 0 \\ [-1, 1] & w = 0 \\ -1 & w < 0 \end{cases}\)

Induces exact sparsity: Many weights become exactly zero

Bayesian view: Laplace prior

L1 hits corners → Some weights exactly 0

Combine L1 and L2:

Alternative parameterization:

where:

• \(\alpha = 1\): Pure L1 (Lasso)
• \(\alpha = 0\): Pure L2 (Ridge)
• \(0 < \alpha < 1\): Mix of both

Advantages:

1. Sparsity from L1
2. Grouping from L2 (correlated features)
3. Stability when \(p > n\)

Elastic Net: Selects groups of correlated features

k-fold cross-validation:

1. Split data into \(k\) “folds”

2. For each \(\lambda\):

   • Train on \(k-1\) folds
   • Validate on remaining fold
   • Repeat \(k\) times

3. Average validation error

4. Choose \(\lambda\) with lowest error

Common choices:

• \(k = 5\) or \(k = 10\)
• Leave-one-out: \(k = n\) (expensive)

One standard error rule:

• Find \(\lambda_{\text{min}}\) with minimum validation error
• Find largest \(\lambda\) within 1 standard error of minimum
• Choose simpler model (larger \(\lambda\)) when comparable

Larger λ within 1 SE yields simpler models with comparable performance

XOR (Exclusive OR):

• (0,0) → Class 0 (blue)
• (0,1) → Class 1 (red)
• (1,0) → Class 1 (red)
• (1,1) → Class 0 (blue)

No linear boundary exists

Any line through the space:

• Misclassifies at least 2 points
• 50% accuracy at best

Logistic regression fails because:

enforces linear decision boundary

Solution: Add hidden layer

• Transform features nonlinearly
• Create linearly separable representation
• 2 hidden units sufficient for XOR

Neuron 1 (OR-like): \(h_1 = \sigma(x_1 + x_2 - 0.5)\)

• Off only at \((0, 0)\)

Neuron 2 (NAND-like): \(h_2 = \sigma(-x_1 - x_2 + 1.5)\)

• Off only at \((1, 1)\)

Output (AND): \(y = \sigma(h_1 + h_2 - 1.5)\)

Hidden representation \((h_1, h_2)\):

In \((h_1, h_2)\) space: linearly separable

Same equations, different vocabulary:

Forward pass:

Backward pass (chain rule):

A single neuron with sigmoid activation is logistic regression. The gradient computation is backpropagation through one layer.

Two-layer network:

• \(\mathbf{W}_1 \in \mathbb{R}^{m \times d}\): first layer weights
• \(\mathbf{h} \in \mathbb{R}^m\): hidden representation
• \(\mathbf{w}_2 \in \mathbb{R}^m\): output layer weights

What stays the same:

• Cross-entropy loss
• Gradient = (error \(\times\) features), extended by chain rule

What changes:

• Hidden layer learns representation \(\mathbf{h}\) where data becomes linearly separable
• Optimization is non-convex: multiple local minima, initialization matters
• Parameters: \((d+1)m + (m+1)\) vs \(d+1\) for logistic

Each hidden unit: one linear boundary

Hidden layer: learned feature extractor

Output layer: linear classifier on \(\mathbf{h}\)

The key idea:

• Input space: classes overlap or form complex boundaries
• Hidden space: data becomes linearly separable
• The network learns what features to extract

This is representation learning — the central idea behind deep learning

Logistic regression (convex):

• Any starting point → global optimum
• Solution is unique (if \(\mathbf{X}\) full rank)

Neural networks (non-convex):

• Different initializations → different local minima
• Different minima → different generalization

Zero initialization breaks symmetry:

• All hidden units compute \(\sigma(\mathbf{0}^T\mathbf{x} + 0) = 0.5\)
• All receive identical gradients
• All learn the same function
• \(m\) hidden units collapse to 1

Random initialization:

• Breaks symmetry: each unit starts differently
• Scale matters: too large → saturation, too small → slow

Permutation symmetry: \(m\) hidden units → \(m!\) equivalent solutions from reordering alone

Logistic regression = neural network with 0 hidden layers

Adding layers:

• Same loss function (cross-entropy)
• Same gradient principle (chain rule extends naturally)
• New representational power: universal approximation with sufficient width

What breaks:

• Convex \(\to\) non-convex: no guarantee of global optimum
• Initialization matters (zero init causes symmetry problems)
• Multiple solutions with different generalization behavior

Parameter growth: