1 Regression and Classification

Classification vs Regression:

• The target variables in classification are discrete, while in regression are continuous
• Classes have their order, while Clusters are exchangeable

Notations and general concepts

L-p norm

Minkowski distance(L-norm)

def minkowski_distance(a, b, p):
 return sum(abs(e1-e2)**p for e1, e2 in zip(a,b))**(1/p)

• p = 1, Manhattan Distance
• p = 2, Euclidean Distance

If the number of training instances: N

KNN: O(Np + N log N) for each test instance

Normalization

• Z score(See probability)
• Min - max

Batch Normalization

Internal Covariate Shift(ICS)

• While training a model, we expect independent and identically distributed data
• For a deep learning model, as the parameter of a lower layer changes, the input distribution of the upper layer also changes. It's called Internal Covariate Shift
• The upper layer's parameters need to continuously adapt to the new input data distribution, thus reduces the learning speed

Problems caused by ICS

• Require Lower learning rates: Training would be slower
• More careful about initializing: saturated regime will slow down the convergence

Batch normalization

• Batch normalize: Calculate mini-batch mean and variance of each layer to decrease covariate shift
• Scale and shift: Identity transform in order to avoid linear regime of the nonlinearity

Layer Normalization

Compute the layer normalization all the hidden units in the same layer

Cross Validation

simple cross validation:

1. Randomly divide training data into $S_{train}$ and $S_{cv}$(cross validation)
2. For each model, traing on $S_{train}$
3. Estimate error on validation set $S_{cv}$
4. find the smallest error

K fold cross validation:

1. Randomly divide training data into k equal parts $S_1,S_2,...,S_k$
2. For each model, traing on all the data except $S_j$
3. Estimate error on validation set $S_j$: $error_{S_j}$
4. Repeat k times, find the smallest error

$Error = \frac1k \sum_{i=1}^k error_{S_j}$

Leave-one-out cross validation:

repeatedly train on all but one of the training examples and test on that held-out example

K fold vs LOO:

• much faster
• more biased(LOO used in sparse dataset)

Metrics

• Precision: the proportion of correctly predicted positive instances out of all instances the model predicted as positive. $\text{Precision}_i = \frac{\text{TP}_i}{\text{TP}_i + \text{FP}_i}$
• Recall: the proportion of correctly predicted positive instances out of all actual positive instances. $\text{Recall}_i = \frac{\text{TP}_i}{\text{TP}_i + \text{FN}_i}$
• $\text{Macro F1} = \frac{1}{n} \sum_{i=1}^{n} \text{F1}_i$, $\text{Macro Precision} = \frac{1}{n} \sum_{i=1}^{n} \text{Precision}_i$
• $\text{Micro Precision} = \frac{\sum_c TP_c}{\sum_c TP_c + \sum_c FP_c}$, $\text{Micro Recall} = \frac{\sum_c TP_c}{\sum_c TP_c + \sum_c FN_c}$

Linear Regression

Say we find a function $f(x,\theta) = \theta^T x$

minimize a loss function $L(\theta) = \sum_{i=1}^Nl(f(x^{(i)},\theta),y^{(i)})$

Ordinary Least Square Regression

• $\theta: \omega,b$
• $l$: square loss

$L = \frac1{2N}\sum_{i=1}^N(f(x^{(i)},\theta) - y^{(i)})^2$ ($\frac1{2N}$ 为了gradients约分还有average)

Gradient descent

For square loss,

$$\nabla_{\theta} L(\theta_t) = \frac{\partial L(\theta)}{\partial \theta} = \boxed{\frac1{N}\sum_{i=1}^{N} \left(f(x^{(i)},\theta)-y^{(i)}\right)x^{(i)}}$$

1. Initialize $\theta_0$ randomly, t = 0
2. Repeat: $\theta_{t+1} = \theta_{t} - \eta \nabla_{\theta} L(\theta_t)$, t = t+1

$\eta$ is the learing rate

• Too small: slow convergence.
• Too large: may overshoot or diverge.

Adjust Learning rate

• constant learning rate
• linear decay: linearly decreases over the training period
• cosine learning rate: a max learning rate times the cosine value(from 0 to 1)
• adaptive learning rate

Adagrad:

$$\begin{aligned} \eta_t = \frac{\eta}{\sqrt{t+1}}, g_t = \nabla_{\theta} L(\theta_t) \\ \theta_{t+1} = \theta_t - \frac{\eta_t}{\sigma^t}g_t \\ \sigma_t = \sqrt{\frac{\sum_{i=0}^{t}g^2_i}{t+1}} \end{aligned}$$

Stochastic Gradient Descent

Gradient descent could be slow: Every update involves the entire training data

Stochastic Gradient Descent (SGD)

Sample a batch of training data to estimate $\nabla L(\theta_t)$

Classification

Assume in C1, $X \sim N(\mu_1,\sigma^2)$; in C2, $X \sim N(\mu_2,\sigma^2)$

Apply min-max normalization for the target variable $\rightarrow$ [0,1]

Bayes‘ rule:

$$P(C_1|x) = \frac{P(x|C_1)P(C_1)}{P(x|C_1)P(C_1) + P(x|C_2)P(C_2)}$$

we can proof that Logistic Regression

$$\log\frac{P(C_1|x)}{P(C_2|x)} = \theta^T x$$

As

$$\begin{aligned} P(C_1|x) + P(C_2|x) = 1 \\ P(C_1|x) = \frac1{1+e^{-{\theta}^Tx}} = \frac1{1+e^{-z}} \end{aligned}$$

We called it "Sigmoid"

Maximum Likelihood Estimate

For binary classification, labels $y^{(i)} \in \{0, 1\}$.

Assuming $N$ samples are independent and identically distributed (i.i.d.):

$$L(\theta) = \prod_{i=1}^N P(y^{(i)} \mid x^{(i)}; \theta) = \prod_{i=1}^N f(x^{(i)}, \theta)^{y^{(i)}} (1 - f(x^{(i)}, \theta))^{1 - y^{(i)}}$$

Average Log-Likelihood (to maximize):

$$\ell(\theta) = \frac{1}{N} \log L(\theta) = \frac{1}{N} \sum_{i=1}^N \left[ y^{(i)} \log f(x^{(i)}, \theta) + (1 - y^{(i)}) \log(1 - f(x^{(i)}, \theta)) \right]$$

Thus:

$$\nabla_{\theta}\ell(\theta) = \frac{\partial \ell(\theta)}{\partial \theta} = \boxed{\frac{1}{N} \sum_{i=1}^N \left( y^{(i)} - f(x^{(i)}, \theta) \right) x^{(i)}}$$

Update via Gradient Ascent:

$$\theta_{t+1} = \theta_t + \eta \nabla_{\theta}\ell(\theta_t) = \theta_t \mathbf{+} \eta \left( \frac{1}{N}\sum_{i=1}^{N}\left(y^{(i)} - f(x^{(i)},\theta)\right)x^{(i)} \right)$$

Cross-Entropy Loss

Define loss (Negative Log-Likelihood) to minimize:

$$J(\theta) = -\ell(\theta) = -\frac{1}{N} \sum_{i=1}^N \left[ y^{(i)} \log f(x^{(i)}, \theta) + (1 - y^{(i)}) \log(1 - f(x^{(i)}, \theta)) \right]$$

Gradient:

$$\nabla_{\theta} J(\theta) = \frac{\partial J(\theta)}{\partial \theta} = \boxed{\frac{1}{N} \sum_{i=1}^N \left( f(x^{(i)}, \theta) - y^{(i)} \right) x^{(i)}}$$

Update via Gradient Descent:

$$\theta_{t+1} = \theta_t - \eta \nabla_{\theta}J(\theta_t) = \theta_t \mathbf{-} \eta \left( \frac{1}{N}\sum_{i=1}^{N}\left(f(x^{(i)},\theta) - y^{(i)}\right)x^{(i)} \right)$$

same as gradient descent

Multiclass Classification

If we look at sigmoid function $P(y_1|x) = \frac{e^{\theta^Tx}}{e^{\theta^Tx} + 1}$, we could extend the dimension and proof that

$$P(y|x;\theta) = \frac{\exp(\vec{\theta^T x})}{\sum_{j=1}^n\exp(\theta_j^Tx)}$$

We define softmax: softmax$(t_1, . . . , t_k) = \frac{\exp(\vec{t})}{\sum_{j=1}^n\exp(t_j)}$

In fact, that's the same as

$$p(y_i|x) = \frac{p(x|y_i)p(y_i)}{\sum_jp(x|y_j)p(y_j)}$$

We could also proof that MLE loss is the same as cross entropy CE$(y,\hat y)$

$$\mathcal{L}_{NLL} = - \frac{1}{m} \sum_{i=1}^m \sum_{y \in Y_i} \log P(y \mid x_i; \theta)$$

$$\mathcal{L}_{CE} = - \frac{1}{m} \sum_{i=1}^m \sum_{j=1}^n y_{ij} \log P(y_j \mid x_i; \theta)$$

Naive Bayes

Bayes' rule for classification:

$$P(y = c \mid x) = \frac{P(x \mid y = c)P(y = c)}{P(x)} \propto P(y = c)P(x \mid y = c)$$

Naive conditional independence assumption: features $x_1, \dots, x_d$ are conditionally independent given class $y$:

$$P(x \mid y = c) = \prod_{j=1}^d P(x_j \mid y = c)$$

Decision rule:

$$\boxed{\hat{y} = \arg\max_{c} P(y = c)\prod_{j=1}^d P(x_j \mid y = c) = \arg\max_c \left[ \log P(y = c) + \sum_{j=1}^d \log P(x_j \mid y = c) \right]}$$

Prior: $P(y = c) = \frac{N_c}{N}$

Likelihood models $P(x_j \mid y = c)$:

• Gaussian NB (continuous features): $x_j \mid y=c \sim \mathcal{N}(\mu_{cj}, \sigma_{cj}^2)$
• Multinomial NB (discrete / word count features):
  $$P(x_j \mid y = c) = \frac{N_{cj} + \alpha}{N_c + \alpha d} \quad (\alpha = 1: \text{Laplace Smoothing})$$
• Bernoulli NB (binary features): $P(x_j \mid y = c) = p_{cj}^{x_j}(1 - p_{cj})^{1 - x_j}$

Naive Bayes vs Logistic Regression:

• Generative ($P(x, y)$) vs Discriminative ($P(y \mid x)$)
• NB reaches its asymptotic error faster with fewer samples ($O(\log d)$ vs $O(d)$), but LR has lower asymptotic error when data is sufficient.

import numpy as np

class GaussianNaiveBayes:
    def __init__(self, var_smoothing=1e-9):
        self.var_smoothing = var_smoothing

    def fit(self, X, y):

        self.classes_, counts = np.unique(
            y, return_counts=True
        )

        # P(y = c)
        self.class_prior_ = counts / len(y)

        # Mean and variance for each class and feature
        self.theta_ = np.array([
            X[y == c].mean(axis=0)
            for c in self.classes_
        ])

        self.var_ = np.array([
            X[y == c].var(axis=0)
            for c in self.classes_
        ])

        # Prevent division by zero
        eps = max(
            self.var_smoothing * np.var(X, axis=0).max(),
            1e-12
        )
        self.var_ += eps

        return self

    def predict(self, X):
        X = np.asarray(X, dtype=float)

        # Shape:
        # X[:, None, :] -> (n_samples, 1, n_features)
        # theta_[None, :, :] -> (1, n_classes, n_features)
        diff = X[:, None, :] - self.theta_[None, :, :]

        # Log Gaussian density
        log_likelihood = -0.5 * np.sum(
            np.log(2 * np.pi * self.var_)[None, :, :]
            + diff**2 / self.var_[None, :, :],
            axis=2
        )

        # Add log prior
        log_posterior = (
            log_likelihood
            + np.log(self.class_prior_)[None, :]
        )

        # Choose class with maximum posterior score
        return self.classes_[
            np.argmax(log_posterior, axis=1)
        ]

Support Vector Machine

Suppose

$$H:\quad w^Tx+b=0,$$

$\textbf{w}\neq 0$ is the normal vector

Distance from $x_0$ to $H$ is

$$\boxed{ d(x_0,H)= \frac{|w^Tx_0+b|}{\|w\|_2} }$$

Support vectors are the data points, which achieve the maximum margin ($y_i(w^Tx_i-b)=1$)

hard-margin SVM

$$\boxed{ \begin{aligned} \min_{w,b}\quad & \frac12\|w\|_2^2\\ \text{s.t.}\quad &y_i(w^Tx_i-b)\ge1,\quad i=1,\ldots,n. \end{aligned}}$$

The constraints are the annoying part. Lagrange multipliers let us fold all those constraints into one function.

$$L(w,b,\alpha) = \frac12\|w\|^2 - \sum_{i=1}^n \alpha_i \left[ y_i(w^Tx_i-b)-1 \right],$$

with

$$\alpha_i\ge0.$$

Take derivatives of the Lagrangian.

With respect to (w):

$$\frac{\partial L}{\partial w}=w-\sum_i\alpha_i y_i x_i=0 \Rightarrow \boxed{ w=\sum_i\alpha_i y_i x_i }.$$

$$\frac{\partial L}{\partial b}=\sum_i\alpha_i y_i=0 \Rightarrow \boxed{ \sum_i\alpha_i y_i=0 }.$$

Dual SVM:

$$\boxed{ \max_{\alpha} \sum_i\alpha_i - \frac12 \sum_{i,j} \alpha_i\alpha_j y_i y_j x_i^Tx_j }$$

subject to

$$\alpha_i\ge0,$$

$$\sum_i\alpha_i y_i=0.$$

Notice the crucial thing:

$$\boxed{x_i^Tx_j}$$

is the only way input vectors appear.

That is exactly what later allows the kernel trick:

$$x_i^Tx_j \longrightarrow K(x_i,x_j).$$

So historically/conceptually:

$$\text{primal SVM} \rightarrow \text{Lagrangian} \rightarrow \text{dual SVM} \rightarrow \text{kernel SVM}.$$

Decision Tree

Non-parametric model: recursively partitions feature space into axis-aligned rectangular regions.

Splitting Criteria

Let dataset $D$ have classes $k = 1, \dots, K$ with empirical probabilities $p_k$.

1. Information Gain (ID3)

Entropy:

$$H(D) = -\sum_{k=1}^K p_k \log_2 p_k$$

Information Gain for feature $A$:

$$\boxed{\text{Gain}(D, A) = H(D) - \sum_{v \in \text{Values}(A)} \frac{|D_v|}{|D|} H(D_v)}$$

• Bias: favors features with many distinct values (e.g. ID numbers).

2. Information Gain Ratio (C4.5)

Penalizes high-cardinality features using intrinsic value $\text{IV}(A)$:

$$\text{GainRatio}(D, A) = \frac{\text{Gain}(D, A)}{\text{IV}(A)}, \quad \text{IV}(A) = -\sum_{v \in \text{Values}(A)} \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|}$$

3. Gini Impurity (CART - Classification)

$$\text{Gini}(D) = 1 - \sum_{k=1}^K p_k^2$$

Binary split on feature $A$:

$$\boxed{\text{Gini}(D, A) = \frac{|D_1|}{|D|}\text{Gini}(D_1) + \frac{|D_2|}{|D|}\text{Gini}(D_2)}$$

• CART produces binary trees only.

4. Squared Error (CART - Regression)

Find split feature $j$ and threshold $s$ minimizing sum of squared errors:

$$\min_{j, s} \left[ \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 \right], \quad c_m = \text{mean}(y_i \mid x_i \in R_m)$$

Overfitting & Pruning

Fully grown trees easily overfit (high variance).

• Pre-pruning: Early stopping during tree construction (max_depth, min_samples_split, min_impurity_decrease).
• Post-pruning: Grow full tree, then prune bottom-up minimizing cost-complexity:
  $$C_\alpha(T) = R(T) + \alpha |T|$$
  where $R(T)$ is training error, $|T|$ is number of terminal leaves, $\alpha \ge 0$ controls penalty for complexity.

Ensemble Learning: Bagging and Boosting

Core idea: combine multiple base (weak) learners to build a strong learner.

$$\text{Expected Error} = \text{Bias}^2 + \text{Variance} + \text{Noise}$$

• Bagging reduces Variance (averaging independent models)
• Boosting reduces Bias (sequentially fitting errors)

Bagging (Bootstrap Aggregating)

1. Bootstrap sampling: draw $N$ samples with replacement from training set of size $N$.
   • Probability an instance is never chosen:
     $$\lim_{N \to \infty} \left(1 - \frac1N\right)^N = \frac1e \approx 36.8\% \quad (\text{Out-Of-Bag, OOB data})$$
   • Each bootstrap sample contains $\approx 63.2\%$ distinct original instances.
2. Train $B$ models independently in parallel.
3. Aggregate:
   • Classification: Majority vote
   • Regression: Mean $\bar{f}(x) = \frac1B \sum_{b=1}^B f_b(x)$

Random Forest

Bagging + Feature Subspace Sampling:

• At each node split, randomly choose a subset of $m$ features out of $d$ total features (typically $m = \sqrt{d}$ for classification, $m = d/3$ for regression).
• De-correlates individual trees:
  $$\text{Var}(\bar{X}) = \rho \sigma^2 + \frac{1 - \rho}{B}\sigma^2$$
  Decreasing correlation $\rho$ between trees directly reduces ensemble variance.

Boosting

Train weak learners sequentially; each learner focuses on the mistakes of preceding ones.

AdaBoost (Adaptive Boosting)

• Base learner: shallow decision trees (decision stumps).
• Iteratively update sample weights: increase weights of misclassified instances.
• Model weight for round $t$ (with error rate $\epsilon_t$):
  $$\alpha_t = \frac12 \ln \left( \frac{1 - \epsilon_t}{\epsilon_t} \right)$$
• Final model:
  $$\boxed{H(x) = \text{sign}\left(\sum_{t=1}^T \alpha_t h_t(x)\right)}$$

Gradient Boosting (GBDT)

Instead of reweighting samples, fit the next base tree to the pseudo-residuals (negative gradient of loss):

$$r_{im} = -\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f=f_{m-1}}$$

• For square loss $L = \frac12(y - f)^2$: $r_{im} = y_i - f_{m-1}(x_i)$ (exact residual).
• Model update: $f_m(x) = f_{m-1}(x) + \eta h_m(x)$ ($\eta$: shrinkage / learning rate).

XGBoost (Extreme Gradient Boosting)

GBDT improvements:

• 2nd-order Taylor expansion of loss: uses both 1st gradient $g_i$ and 2nd Hessian $h_i$.
• Regularized objective:
  $$\mathcal{L} = \sum_{i=1}^N l(y_i, \hat{y}_i) + \sum_{k} \left( \gamma T_k + \frac12 \lambda \sum_{j=1}^{T_k} w_j^2 \right)$$
  where $T_k$ is number of leaves, $w$ is leaf weights vector.
• Column subsampling + parallel tree construction.

Bagging vs Boosting

Dimension	Bagging (e.g. Random Forest)	Boosting (e.g. AdaBoost, GBDT, XGBoost)
Strategy	Parallel & independent	Sequential & dependent
Error focus	Reduces Variance	Reduces Bias
Base learners	Deep trees (low bias, high variance)	Shallow trees / stumps (high bias, low variance)
Overfitting risk	Low (adding trees will not overfit)	Higher if rounds too large / noisy data