Deep Learning - Numerical Optimization & Learning Theory
Numerical Optimization
Numerical Computation
在機器學習中，會有大量的浮點數計算，受限於浮點數儲存的精度，有時候會產生 numeric errors
Overflow & Underflow
對於 Softmax 函數來說
$$
\text{softmax}(z_i) = \frac{\exp(z_i)}{\sum_{j} \exp(z_j)}
$$
如果對於 $z_i = c \ \forall i$，如果 $|c|$ 很大
- 如果 $c$ 是正數，則 $\exp(c)$ 會 overflow
- 如果 $c$ 是負數，則 $\exp(c)$ 會 underflow，還有可能導致分母為 0
為了解決這個問題，可以對 $z$ 進行平移 (shift)：
$$
\text{softmax}(z_i) = \frac{\exp(z_i - z_{\max})}{\sum_{j} \exp(z_j - z_{\max})}
$$
這樣的計算結果會和原本的 softmax 函數相同，但可以避免 overflow 和 underflow 的問題
- 分子最多是 $\exp(0) = 1$，不會 overflow
- 分母至少有一項是 $\exp(0) = 1$，不會為 0
$$
\begin{aligned}
\text{softmax}(z_i) &= \frac{\exp(z_i - z_{\max})}{\sum_{j} \exp(z_j - z_{\max})} \newline
&= \frac{\exp(z_i) \exp(-z_{\max})}{\sum_{j} \exp(z_j) \exp(-z_{\max})} \newline
&= \frac{\exp(z_i)}{\sum_{j} \exp(z_j)} \newline
\end{aligned}
$$
Poor Conditioning
Condition number 是用來衡量一個函數對輸入變化的敏感度
像是我們有 $f(x) = Ax = y$，其中 $A$ 是一個矩陣，且 $A^{-1}$ 存在
那麼其 condition number 定義為
$$
\kappa(A) = \max_{i, j} \frac{|\lambda_i|}{|\lambda_j|}
$$
- $\lambda_i$: $A$ 的第 $i$ 個 eigen value，如前面所述，可以想成是對某個方向的伸縮最大值和最小值的比值
- 當 $\kappa(A)$ 很大時，對 $x$ 的微小變化會導致 $y$ 有很大的變化，這會影響到優化算法的收斂速度和穩定性，稱為 ill-conditioned
- 在解 $x = A^{-1} y$ 時，會放大 $y$ 的 numeric errors，導致 $x$ 有很大的誤差
Optimization Problems
Optimization problem 的目標是去最小化一個 cost function $f: \mathbb{R}^d \to \mathbb{R}$
$$
\text{argmin}_{x \in \mathbb{R}^d} f(x) \newline
\text{subject to } x \in \mathcal{C}
$$
$\mathcal{C} \subseteq \mathbb{R}^d$: constraint set，表示 $x$ 必須滿足的約束條件，又稱 為 feasible set，$x$ 稱為 feasible point
- 例如: $\mathcal{C} = {x : g_i(x) \leq 0, h_j(x) = 0}$
- 如果 $\mathcal{C} = \mathbb{R}^d$，稱為 unconstrained optimization problem
- 如果是最大化 objective function 問題，可以把目標改成最小化 $-f(x)$
Examples
- Critical Point: $\mathbf{C} = {x : \nabla f(x) = 0}$
- Minima: $\mathbf{C} = {x : \nabla f(x) = 0, H(f)(x) \succ 0}$
- Maxima: $\mathbf{C} = {x : \nabla f(x) = 0, H(f)(x) \prec 0}$
- Plateau/Saddle Point: $\mathbf{C} = {x : \nabla f(x) = 0, H(f)(x) = \mathbf{O} \ \text{or} \text{ indefinite}}$
- Global Minimum: $\min_{x \in \mathcal{C}} f(x) \in \mathbf{R}$
- Optimal Point: $x^* \in \mathcal{C}$ such that $f(x^*) = \min_{x \in \mathcal{C}} f(x)$
Convex Optimization
滿足以下條件的 optimization problem，稱為 convex optimization problem
- $H(f)(x) \succeq 0$ for all $x \in \mathcal{C}$
- $g_i(x)$ 是 convex function for all $i$
- $h_j(x)$ 是 affine function for all $j$
- affine function: $h(x) = Ax + b$，就是 Linear + Constant shift
Gradient Descent
根據 Taylor expansion，可以用函數 $\tilde{f}(x)$ 的多項式
近似來描述函數在某一點附近的行為，例如在點 $a$ 附近，可以用一階 Taylor expansion 來近似函數：
$$
f(x) \approx \tilde{f}(x) = f(a) + \nabla f(a)^T (x - a)
$$
當我們選擇 $x = a - \eta \nabla f(a)$ for some $\eta > 0$ 時，可以得到
$$
\tilde{f}(x) = f(a) - \eta |\nabla f(a)|^2 \leq \tilde{f}(a)
$$
Negative Gradient is the Direction of Steepest Descent
給定一個 function $f$，一個方向 $u$ 和點 $a$
Directional Derivative:
$$
D_u f(a) = \lim_{h \to 0} \frac{f(a + h u) - f(a)}{h} = \nabla f(a)^T u
$$
我們想找到一個單位向量 $u$，使得 $D_u f(a)$ 最小化
$$
\begin{aligned}
\arg\min_{u, |u| = 1} D_u f(a) &= \arg\min_{u, |u| = 1} \nabla f(a)^T u \newline
&= \arg\min_{u, |u| = 1} |\nabla f(a)| |u| \cos \theta \newline
&= \arg\min_{u} \cos \theta \newline
\end{aligned}
$$
所以，當 $u = -\frac{\nabla f(a)}{|\nabla f(a)|}$ 時，也就是負梯度方向，Directional Derivative 會達到最小值
Set Learning Rate
有空再補
Problems of Gradient Descent
沒有考慮到 $H(f)(x)$ 的 Conditioning 的問題，可能在某個方向下降很快，但在另一個方向下降很慢，導致整體收斂速度變慢
- Zig-Zags
Newton’s Method
根據二維 Taylor expansion，可以用函數 $\tilde{f}(x)$ 的多項式近似來描述函數在某一點附近的行為，例如在點 $a$ 附近，可以用二階 Taylor expansion 來近似函數：
$$
f(x) \approx \tilde{f}(x) = f(a) + \nabla f(a)^T (x - a) + \frac{1}{2} (x - a)^T H(f)(a) (x - a)
$$
當 $f$ 是 strictly convex 時，我們可以去解 $\nabla \tilde{f}(x) = 0$，來找到 $\tilde{f}(x)$ 的最小值，得到
$$
a - H(f)(a)^{-1} \nabla f(a)
$$
- $H(f)(a)$ 就是 gradient 的 corrector
在這種情況下，只要不斷找
$$
x^{(k+1)} = x^{(k)} - \eta H(f)(x^{(k)})^{-1} \nabla f(x^{(k)})
$$
就可以快速收斂
當 $f$ 不是 strictly convex 時，$H(f)(x) \preceq 0$ 或 indefinite，會導致找出來的方向不是下降方向，因此會需要 Levenberg-Marquardt adjustment
$$
x^{(k+1)} = x^{(k)} - \eta (H(f)(x^{(k)}) + \lambda I)^{-1} \nabla f(x^{(k)})
$$
選一個足夠大的 $\lambda$，可以確保 $H(f)(x^{(k)}) + \lambda I \succ 0$，使得方向為下降方向
Problems of Newton’s Method
- 計算 $H(f)(x)$ 和 $H(f)(x)^{-1}$ 的時間和空間複雜度都很高，尤其是在高維度的情況下
- 時間複雜度: $O(d^3)$
- 空間複雜度: $O(d^2)$
- $H(f)(x)$ 可能有很大的 Condition Number
- 當 gradient 有 numeric errors 時，會被放大，導致方向不正確，越往後誤差越大
- 可能會收斂到 Saddle Point
- 因為在 Saddle Point 處，$H(f)(x)$ 是 indefinite，可能會導致找出來的方向不是下降方向
Optimization in Machine Learning
大部分的機器學習模型都有 convex function，e.g. Linear Regression, Logistic Regression, SVM…
但是在深度學習中，通常都是 non-convex function，e.g. Neural Networks
Lipschitz Continuity
我們通常會假設 Cost Function $C$ 是 Lipschitz Continuous 的，表示存在一個常數 $K > 0$，使得：
$$
|C(w^1) - C(w^2)| \leq K |w^1 - w^2|, \quad \forall w^1, w^2 \in \mathbb{R}^d
$$
這個條件保證了函數的變化不會太劇烈，有助於優化算法的收斂性分析
Perceptron Learning Algorithm
Binary Classification 問題
假設資料集 $D = {(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)}$，其中 $x_i \in \mathbb{R}^d$ 是特徵向量，$y_i \in {-1, 1}$ 是標籤
定義線性分類器 $f(x) = sign(w^T x + b)$
- 其中 $w \in \mathbb{R}^d$ 是權重向量，$b \in \mathbb{R}$ 是偏差
- 也可以把 $b$ 合併到 $w$ 中，令 $\tilde{x} = [x; 1]$，$\tilde{w} = [w; b]$，則 $f(x) = \tilde{w}^T \tilde{x}$
訓練時，每個 Epoch 會根據每筆資料 $(x^t, y^t)$ 來更新權重 $w$
$$
w^{(t+1)} = w^{(t)} + \eta (y^t - \hat{y}^t) x^t
$$
如果 $\hat{y}^t = y^t$，則不更新
如果 $\hat{y}^t \ne y^t$，得到 $w^{(t+1)} = w^{(t)} + 2 \eta y^t x^t$
- $y^t = 1$
$$
\begin{aligned}
\text{sign}(w^{(t+1)T} x^t) &= \text{sign}((w^{(t)} + 2 \eta x^t)^T x^t) \newline
&= \text{sign}(w^{(t)T} x^t + 2 \eta |x^t|^2) \newline
&= \text{sign}(w^{(t)T} x^t + c)
\end{aligned}
$$
因為 $c > 0$，所以 $\text{sign}(w^{(t+1)T} x^t)$ 會傾向於變成 1
- $y^t = 1$
如果資料沒辦法線性可分，則 Perceptron Learning Algorithm 可能無法收斂
ADAptive LInear NEuron (Adaline)
Adaline 是一種線性分類器，與 Perceptron 類似，但使用連續的輸出值來進行學習
Cost Function:
$$
\arg\min_{w} \frac{1}{2} \sum_{i=1}^{N} (y_i - w^T x_i)^2
$$
訓練完之後，使用 $f(x) = sign(w^T x)$ 來進行分類
Update Rule:
$$
w^{(t+1)} = w^{(t)} + \eta \sum_{i=1}^{N} (y_i - w^{(t)T} x_i) x_i
$$
因為 Cost function 是 Convex 的，所以可以保證可以收斂到全域最小值
Stochastic Gradient Descent (SGD)
把資料集 $D$ 分成多個 mini-batch，每次只使用一個 mini-batch 來更新權重
$$
w^{(t+1)} = w^{(t)} - \eta \nabla C_{MB}(w^{(t)})
$$
- $C_{MB}(w)$: mini-batch 上的 Cost Function
- 每次更新只需要計算 mini-batch 的 gradient，計算量較小，適合大規模資料集
- 支援 Online Learning
Constrained Optimization
Problem:
$$
\text{min}_{x} f(x) \newline
\text{subject to } x \in {x : g_i(x) \leq 0, h_j(x) = 0}
$$
Karush-Kuhn-Tucker (KKT) Methods
可以把問題轉成
$$
\text{min}x\text{max}{\alpha, \beta, \alpha \geq 0} \mathcal{L}(x, \alpha, \beta) = \newline
\text{min}x\text{max}{\alpha, \beta, \alpha \geq 0} f(x) + \sum_{i} \alpha_i g_i(x) + \sum_{j} \beta_j h_j(x) \newline
$$
當 $x$ 是 Feasible Point 時，$\mathcal{L}(x, \alpha, \beta) = f(x)$，因為 $g_i(x) \leq 0$ 和 $h_j(x) = 0$，會選 $\alpha_i = 0$ 和任意 $\beta_j$ 來 maximize $\mathcal{L}(x, \alpha, \beta)$
當 $x$ 不是 Feasible Point 時，會有某些 $g_i(x) > 0$ 或 $h_j(x) \ne 0$，這時候可以選擇很大的 $\alpha_i$ 或 $\beta_j$ 來讓 $\mathcal{L}(x, \alpha, \beta)$ 變無限大，這樣就不會選擇這些 $x$ 來 minimize $\mathcal{L}(x, \alpha, \beta)$
KKT Conditions
假設 $f, g_i, h_j$ 都是可微分的，且 $x^*$ 是問題的最優解，則存在 $\alpha^*, \beta^*$，使得以下條件成立：
- Primal Feasibility: $g_i(x^*) \leq 0$ for all $i$, $h_j(x^*) = 0$ for all $j$
- Dual Feasibility: $\alpha_i^* \geq 0$ for all $i$
- Stationarity: $\nabla f(x^*) + \sum_{i} \alpha_i^* \nabla g_i(x^*) + \sum_{j} \beta_j^* \nabla h_j(x^*) = 0$
- Complementary Slackness: $\alpha_i^* g_i(x^*) = 0$ for all $i$
Complementary Slackness
如果 $g_i(x^*) = 0$，稱為 active，$\alpha_i^* g_i(x^*) = 0$
如果 $g_i(x^*) < 0$，稱為 inactive，為了 maximize $\mathcal{L}(x^*, \alpha^*, \beta^*)$，必須有 $\alpha_i^* = 0$
今天我有一個 $\alpha_i^* > 0$，我就可以知道 $g_i(x^*)$ 一定是 0，可以快速找到 active constraints，就可以確定最優解真正被哪些限制所決定
The Regression Problem
給定資料集 $D = {(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)}$，其中 $x_i \in \mathbb{R}^d$ 是特徵向量，$y_i \in \mathbb{R}$ 是目標值
目標是找到一個函數 $f: \mathbb{R}^d \to \mathbb{R}$，使得對於所有的 $(x_i, y_i)$，$f(x_i)$ 盡可能接近 $y_i$
Sum of Squared Errors (SSE):
$$
SSE(f; D) = \sum_{i=1}^{N} (y_i - f(x_i))^2
$$
Mean Squared Error (MSE):
$$
MSE(f; D) = \frac{1}{N} \sum_{i=1}^{N} (y_i - f(x_i))^2
$$
Relative Squared Error (RSE):
$$
RSE(f; D) = \frac{\sum_{i=1}^{N} (y_i - f(x_i))^2}{\sum_{i=1}^{N} (y_i - \bar{y})^2}
$$
- $\bar{y} = \frac{1}{N} \sum_{i=1}^{N} y_i$: 目標值的平均值
- 一般來說，RSE 越小表示模型越好，如果算出來大於 1，表示模型比直接用平均值來預測還差，你乾脆直接用平均值算就好
- R-squared ($R^2$) 是用來衡量模型解釋變異的比例
$$
R^2 = 1 - RSE
$$- $R^2$ 越接近 1，表示模型解釋變異的能力越強
Data Augmentation
在機器學習中，可以把 Linear model 轉換成多項式特徵，或是加入其他變換，以增加模型的表達能力
[HW] How many variables to solve in $w$ for a polynomial regression problem with degree $P$
Regularization
為了 Generalization ，而不是只在訓練資料上表現好，可以在 Cost Function 中加入 Regularization term，來懲罰過於複雜的模型
$$
\text{argmin}_{w \in \mathbb{R}^d} \frac{1}{2} | y - (Xw - b)|^2 \newline
\text{subject to } |w|^2 \leq R
$$
可以寫成
$$
\text{argmin}_{w \in \mathbb{R}^{d+1}} \frac{1}{2} | y - (Xw )|^2 \newline
\text{subject to } w^T S w \leq R
$$
其中 $S = \begin{bmatrix} 0 & 0 \ 0 & I_d \end{bmatrix}$
By KKT，可以轉成 unconstrained problem
$$
\text{argmin}w \text{max}{\alpha, \alpha \ge 0} \frac{1}{2} (| y - (Xw )|^2 + \alpha( w^T S w - R))
$$
Dual Problem
給定 primal problem:
$$
p^* = \text{min}x \text{max}{\alpha, \beta, \alpha \geq 0} \mathcal{L}(x, \alpha, \beta)
$$
dual problem 定義為:
$$
d^* = \text{max}_{\alpha, \beta, \alpha \geq 0} \text{min}_x \mathcal{L}(x, \alpha, \beta)
$$
[HW] By max-min inequality, we have
$$
d^* \leq p^*
$$
當 primal problem 是 convex，且有解，則 strong duality 成立，$d^* = p^*$，有時候解問題會更有效率
Example
考慮
$$
\text{argmin}_{w \in \mathbb{R}^d} \frac{1}{2} |x|^2 \newline
\text{subject to } Ax \geq b, A \in \mathbb{R}^{n \times d}, b \in \mathbb{R}^n
$$
By KKT，可以寫成
$$
\text{argmin}x \text{max}{\alpha, \alpha \geq 0} \frac{1}{2} |x|^2 + \alpha^T (b - Ax)
$$
因為是 Convex problem，滿足 Strong Duality，可以交換 min 和 max
$$
\text{argmax}_{\alpha, \alpha \geq 0} \text{min}_x \frac{1}{2} |x|^2 + \alpha^T (b - Ax)
$$
對 $x$ 求導並設為 0，得到 $x = A^T \alpha$，帶回上式，得到
$$
\text{argmax}_{\alpha, \alpha \geq 0} -\frac{1}{2} |A^T \alpha|^2 + b^T \alpha
$$
現在只需要解 $n$ 維的問題，而不是 $d$ 維的問題，當 $n \ll d$ 時，會更有效率
Learning Theory
Empirical Error / risk
Empirical Error 是在訓練資料集上計算的平均 Loss
$$
E_N[f] = \frac{1}{N} \sum_{i=1}^{N} \text{loss}(f(x_i; w), y_i)
$$
Generalization Error / risk
Generalization Error 是在整個資料分佈上計算的平均 Loss，代表模型在未見過的資料上的表現
$$
C[f] = \int \text{loss}(f(x; w), y) dP(x, y)
$$
Learining Theory 就是在理解怎麼去 Characterize
$$
C[f_N] = \int \text{loss}(f_N(x; w), y) dP(x, y)
$$
- $f_N$: model learned from training data of size $N$
- $C[f_N]$: generalization error
Bounding Methods
$min_fC[f] = C[f^*]$ 稱為 Bayes Error，表示在給定資料分佈下，最佳模型的誤差下限
- 如果 $P(y|x)$ 有隨機性，則 Bayes Error > 0
- 目標是讓 $C[f_N]$ 越接近 $C[f^*]$ 越好
$\Epsilon = C(f_N) - C(f^*)$ 稱為 Excess Error，又可以寫成
$$
\Epsilon = (C(f_F^*) - C(f^*)) + (C(f_N) - C(f_F^*))
$$
其中前項稱為 Approximation Error，後項稱為 Estimation Error
- 選越複雜的 $F$，Approximation Error 越小，但 Estimation Error 越大
Properties of Estimators
Bias
- Bias 衡量估計值的期望與真實值之間的差異，來看這個 estimator 準不準
- 定義為
$$
\text{Bias}(\hat{\theta}) = \mathbb{E}[\hat{\theta}] - \theta
$$ - 如果 $\text{Bias}(\hat{\theta}) = 0$，則稱為無偏估計 (Unbiased Estimator)
Variance
- Variance 衡量估計值的變異程度，來看這個 estimator 穩不穩定
- 定義為
$$
\text{Var}(\hat{\theta}) = \mathbb{E}[(\hat{\theta} - \mathbb{E}[\hat{\theta}])^2]
$$ - Variance 越小，表示估計值越穩定
Sample Mean Estimator
給定資料集 $D = {x_1, x_2, \ldots, x_N}$，樣本均值估計量定義為
$$
\hat{\mu} = \frac{1}{N} \sum_{i=1}^{N} x_i
$$Bias:
$$
\begin{aligned}
\mathbb{E}[\hat{\mu}] &= \mathbb{E}\left[\frac{1}{N} \sum_{i=1}^{N} x_i\right] \newline
&= \frac{1}{N} \sum_{i=1}^{N} \mathbb{E}[x_i] \newline
&= \frac{1}{N} \sum_{i=1}^{N} \mu \newline
&= \mu \newline
\end{aligned}
$$- 因此，$\text{Bias}(\hat{\mu}) = \mathbb{E}[\hat{\mu}] - \mu = 0$，樣本均值估計量是無偏的
Variance:
$$
\begin{aligned}
\text{Var}{\mathbb{X}}(\hat{\mu})
&= \mathbb{E}{\mathbb{X}}[(\hat{\mu} - \mathbb{E}{\mathbb{X}}[\hat{\mu}])^2] = \mathbb{E}[\hat{\mu}^2 - 2\hat{\mu}\mu + \mu^2] = \mathbb{E}[\hat{\mu}^2] - \mu^2 \
&= \mathbb{E}\left[\frac{1}{n^2} \sum{i,j} x^{(i)}x^{(j)}\right] - \mu^2 = \frac{1}{n^2} \sum_{i,j} \mathbb{E}[x^{(i)}x^{(j)}] - \mu^2 \
&= \frac{1}{n^2} \left( \sum_{i=j} \mathbb{E}[x^{(i)}x^{(j)}] + \sum_{i \neq j} \mathbb{E}[x^{(i)}x^{(j)}] \right) - \mu^2 \
&= \frac{1}{n^2} \left( \sum_{i} \mathbb{E}[x^{(i)2}] + n(n-1)\mathbb{E}[x^{(i)}]\mathbb{E}[x^{(j)}] \right) - \mu^2 \
&= \frac{1}{n} \mathbb{E}[x^2] + \frac{(n-1)}{n} \mu^2 - \mu^2 = \frac{1}{n} (\mathbb{E}[x^2] - \mu^2) = \frac{1}{n} \sigma_{\text{x}}^2
\end{aligned}
$$- 因此，$\text{Var}(\hat{\mu}) = \frac{1}{N} \sigma_{\text{x}}^2$，樣本均值估計量的變異程度隨著樣本數增加而減少
Sample Variance Estimator
樣本變異數估計量定義為
$$
\hat{\sigma}^2 = \frac{1}{N} \sum_{i=1}^{N} (x_i - \hat{\mu})^2
$$Bias:
$$
\begin{aligned}
\text{E}_{\mathbb{X}}[\hat{\sigma}]
&= \text{E}\left[\frac{1}{n} \sum_i (x^{(i)} - \hat{\mu})^2 \right] = \text{E}\left[ \frac{1}{n} (\sum_i x^{(i)2} - 2\sum_i x^{(i)}\hat{\mu} + \sum_i \hat{\mu}^2) \right] \
&= \text{E}\left[ \frac{1}{n} (\sum_i x^{(i)2} - n\hat{\mu}^2) \right] = \frac{1}{n} \left( \sum_i \text{E}[x^{(i)2}] - n\text{E}[\hat{\mu}^2] \right) \
&= \text{E}[x^2] - \text{E}[\hat{\mu}^2] = \text{E}[(x-\mu)^2 + 2x\mu - \mu^2] - \text{E}[\hat{\mu}^2] \
&= (\sigma^2 + \mu^2) - (\text{Var}[\hat{\mu}] + \text{E}[\hat{\mu}]^2) \
&= \sigma^2 + \mu^2 - \frac{1}{n}\sigma^2 - \mu^2 = \frac{n-1}{n}\sigma^2 \neq \sigma^2
\end{aligned}
$$
因此，$\text{Bias}(\hat{\sigma}^2) = \mathbb{E}[\hat{\sigma}^2] - \sigma^2 = -\frac{1}{N} \sigma^2$，樣本變異數估計量是有偏的
如果要 unbiased，可以改成
$$
\hat{\sigma}^2 = \frac{1}{N-1} \sum_{i=1}^{N} (x_i - \hat{\mu})^2
$$
Consistency
- Consistency 衡量估計值隨著樣本數增加而收斂到真實值的能力
- 定義為
$$
\lim_{N \to \infty} P(|\hat{\theta}_N - \theta| > \epsilon) = 0, \quad \forall \epsilon > 0
$$
Decomposing Generalization Error
前面提到，我們有一個模型 $f_N$，把它看作是一個 estimator，可以用上述方法分析這個 estimator 的 Bias 和 Variance
$$
\begin{aligned}
E_\mathbb{X}(C[f_N]) &= E_\mathbb{X}\left( \int (y - f_N(x))^2 P(x, y) dx dy \right) \newline
&= E_{\mathbb{X}, x, y}[\text{loss}(f_N(x) - y)] \newline
&= E_{x}(E_{\mathbb{X}, y}[\text{loss}(f_N(x) - y) | x = x]) \newline
\end{aligned}
$$
在 Linear/ Polynomial Regression 的情況下
$\text{loss}$ 是平方誤差
$y = f^*(x) + \epsilon$，其中 $\epsilon$ 是高斯雜訊，$\epsilon \sim \mathcal{N}(0, \sigma^2)$
- $E_y[y|x] = f^*(x)$
- $\text{Var}_y[y|x] = \sigma^2$
則
$$
\begin{aligned}
E_{\mathbb{X}, y}[\text{loss}(f_N(x) - y) | x] &= E_{\mathbb{X}, y}[(f_N(x) - y)^2 | x] \newline
&= E_{\mathbb{X}, y}[y^2 + f_N(x)^2 - 2y f_N(x) | x] \newline
&= E_{\mathbb{X}}[f_N(x)^2 | x] + E_y[y^2 | x] - 2 E_{\mathbb{X}, y}[yf_N(x) | x] \newline
&= (Var_\mathbb{X}[f_N(x) | x] + (E_{\mathbb{X}}[f_N(x) | x])^2) + (Var_y[y|x] + (E_y[y|x])^2) - 2 E_{\mathbb{X}}[f_N(x) | x] E_y[y|x] \newline
&= \text{Var}y[y|x] + Var_\mathbb{X}[f_N(x) | x] + (E{\mathbb{X}}[f_N(x) | x] - E_y[y|x])^2 \newline
&= \text{Var}y[y|x] + Var_\mathbb{X}[f_N(x) | x] + (E{\mathbb{X}}[f_N(x) - f^*(x) | x])^2 \newline
&= \sigma^2 + Var_\mathbb{X}[f_N(x) | x] + \text{Bias}[f_N(x) | x]^2 \newline
\end{aligned}
$$
得到
$$
\begin{aligned}
E_\mathbb{X}(C[f_N]) &= E_x\left( \sigma^2 + Var_\mathbb{X}[f_N(x) | x] + \text{Bias}[f_N(x) | x]^2 \right) \newline
\end{aligned}
$$
- $\sigma^2$: Irreducible Error，無法避免的誤差，因為資料本身有雜訊
- $E_x(Var_\mathbb{X}[f_N(x) | x])$: Variance，模型對於不同訓練資料集的敏感度
- $E_x(\text{Bias}[f_N(x) | x]^2)$: Bias，模型預測值與真實值的差異
Regularization
前面有提到，為了避免 Overfitting，任何能夠讓 $f_N$ 更穩定的方式，都可以視為 Regularization
Weight Decay
Occam’s razor
根據前面的 Learning Theory 的結果，兩個模型如果有一樣的 empirical error，應該選擇較簡單的模型，因為較簡單的模型通常有較低的 Variance，能夠更好地 Generalize 到未見過的資料
所以可以加上一個 Term 來去程罰複雜的模型
Model Complexity
- 模型的 degree 不能直接拿來當作複雜度的衡量，因為它是固定的，不會隨著參數的改變而改變
- 可以用參數的範數 (norm) 來衡量模型的複雜度
所以我們使用 $w$ 的 norm 作為正則化項，在 $w = 0$ 時，模型最簡單
Ridge Regression (L2 Regularization)
$$
\text{argmin}_{w \in \mathbb{R}^d} \frac{1}{2} | y - (Xw - b)|^2 \text{subject to } |w|^2 \leq T
$$
一般會轉成 unconstrained problem
$$
\text{argmin}_{w \in \mathbb{R}^d} \frac{1}{2} | y - (Xw - b)|^2 + \frac{\alpha}{2} |w|^2
$$
- $\alpha$: regularization parameter，控制正則化項的權重，$\alpha$ 越大，模型越簡單
- $b$ 通常不會被正則化，因為 $y$ 的平均值不一定是 0，所以 $b$ 不應該被懲罰
Lasso Regression (L1 Regularization)
$$
\text{argmin}_{w \in \mathbb{R}^d} \frac{1}{2} | y - (Xw - b)|^2 + \alpha |w|_1
$$
- $|w|1 = \sum{i=1}^{d} |w_i|$
- L1 regularization 會導致參數稀疏化，很多參數會被壓縮到 0，適合用於特徵選擇
- 因為 L1 norm 的區域是菱形，會傾向於在坐標軸上取交點，把不重要的參數壓縮到 0
Elastic Net
LASSO 在某些情況下會有限制
- No Group Selection: 當有一組高度相關的特徵時，LASSO 可能只會選擇其中一個，而忽略其他相關特徵
- 最大選擇數量: LASSO 最多只能選擇 $N$ 個特徵，當特徵數量 $d$ 遠大於樣本數量 $N$ 時，LASSO 可能無法選擇足夠的特徵來建構模型
Elastic Net 結合了 L1 和 L2 正則化的優點，可以同時達到稀疏化和穩定性的效果
$$
\text{argmin}_{w \in \mathbb{R}^d} \frac{1}{2} | y - (Xw - b)|^2 + \alpha(\beta |w|_1 + (1 - \beta) |w|^2)
$$
- $\beta \in [0, 1]$: 控制 L1 和 L2 正則化的權重比例，當 $\beta = 1$ 時，等同於 LASSO；當 $\beta = 0$ 時，等同於 Ridge Regression
Validation
- 調整各種 hyperparameter (e.g. regularization parameter $\alpha$) 可以來控制模型的複雜度，以達到最佳的 Generalization Performance
- 通常會使用 Cross-Validation 來評估不同 hyperparameter 下模型的表現，選擇在驗證集上表現最好的參數組合
Probabilistic Models
Maximum Likelihood Estimation (MLE)
Linear Regression via MLE
假設 $y = f^*(x) + \epsilon$，其中 $\epsilon$ 是高斯雜訊，$\epsilon \sim \mathcal{N}(0, \beta^{-1})$，則 $f^*(x)$ 可以寫成
$$
f^*(x; w^*) = w^{*\top} x
$$
其中所有資料已經經過 z-normalization，平均值為 0，則
$$
(y | x) \sim \mathcal{N}(w^{*\top} x, \beta^{-1})
$$
所以目標會是找到一個 $w$ 接近 $w^*$
$$
\hat{y} = \argmax_y P(y | x, w) = w^{\top} x
$$
- $\beta^{-1}$ 跟 $w$ 無關，可以忽略
MLE 的目標是最大化在所有資料點上的似然函數
$$
\text{argmax}_w P(\mathbf{X} | w)
$$
其中
$$
\begin{aligned}
P(\mathbf{X} | w) &= \prod_{i=1}^{N} P(x_i, y_i | w) \newline
&= \prod_{i=1}^{N} P(y_i | x_i, w) P(x_i | w) \newline
&= \prod_{i=1}^{N} P(y_i | x_i, w) P(x_i) \newline
&= \prod_{i=1}^{N} \mathcal{N}(y_i | w^{\top} x_i, \beta^{-1}) P(x_i) \newline
&= \prod_{i=1}^{N} \sqrt{\frac{\beta}{2\pi}} \exp\left( -\frac{\beta}{2} (y_i - w^{\top} x_i)^2 \right) P(x_i) \newline
\end{aligned}
$$
先取 log，可以把乘法轉成加法，且 log 是單調遞增函數，不會影響最大值的位置
$$
\begin{aligned}
&\text{argmax}w \log P(\mathbf{X} | w) \newline
&= \text{argmax}w \sum{i=1}^{N} \log \prod{i=1}^{N} \left( \sqrt{\frac{\beta}{2\pi}} \exp\left( -\frac{\beta}{2} (y_i - w^{\top} x_i)^2 \right) \right) P(x_i) \newline
&= \text{argmax}w N \sqrt{\frac{\beta}{2\pi}} + \sum{i=1}^{N} P(x_i) - \frac{\beta}{2} \sum_{i=1}^{N} (y_i - w^{\top} x_i)^2 \newline
\end{aligned}
$$
因為前兩項不依賴於 $w$，可以忽略，且 maximize 等同於 minimize 負的東西，所以可以寫成
$$
\text{argmin}w \sum{i=1}^{N} (y_i - w^{\top} x_i)^2
$$
- 這就是我們之前提到的 Sum of Squared Errors (SSE)
- 所以 MLE 在這個情況下等同於最小化 SSE，可以讓我們知道為什麼要最小化 SSE
Logistic Regression via MLE
假設 $y \in {-1, 1}$，且
$$P(y=1 | x, w) = \sigma(w^{\top} x) = \frac{1}{1 + \exp(-w^{\top} x)}$$
則
$$
P(y=-1 | x, w) = 1 - \sigma(w^{\top} x) = \frac{\exp(-w^{\top} x)}{1 + \exp(-w^{\top} x)}
$$
機率可以寫成
$$
P(y | x, w) = \sigma(w^{\top} x)^{y^\prime} (1 - \sigma(w^{\top} x))^{1-y^\prime}
$$
- 其中 $y^\prime = \frac{y+1}{2} \in {0, 1}$
預測的目標是
$$
\begin{aligned}
\hat{y} &= \argmax_y P(y \mid x, w) \newline
&= \argmax_y {\sigma(w^{\top} x), (1 - \sigma(w^{\top} x))} \newline
&= \text{sign}(w^\top x) \newline
\end{aligned}
$$
MLE 的目標是最大化在所有資料點上的似然函數
$$
\text{argmax}_w P(\mathbf{X} | w)
$$
一樣採用 log 來簡化計算
$$
\begin{aligned}
\log P(\mathbf{X} | w)&= \log \prod_{i=1}^{N} P(x_i, y_i | w) \newline
&= \log \prod_{i=1}^{N} P(y_i | x_i, w) P(x_i | w) \newline
&\propto \log \prod_{i=1}^{N} \sigma(w^{\top} x_i)^{y_i^\prime} (1 - \sigma(w^{\top} x_i))^{1-y_i^\prime} \newline
&= \sum_{i=1}^{N} \left( y^\prime_i x_i - \log(1 + e^{-w^{\top} x_i})\right) \text{[HW]}
\end{aligned}
$$
所以對 $w$ 做偏微並設為 0，可以找到 MLE 的解
$$
\begin{aligned}
\nabla_w \log P(\mathbf{X} | w) &= \sum_{i=1}^{N} [y^\prime_i - \sigma(w^{\top} x_i)]x_i \newline
&= 0 \newline
\end{aligned}
$$
因為沒辦法直接解出來，所以通常會用 Gradient Ascent 來找到最大值
Maximum A Posteriori (MAP) Estimation
在 MLE 的基礎上，加入 Prior knowledge 來進行估計
$$
\text{argmax}_w P(w | \mathbf{X}) = \text{argmax}_w P(\mathbf{X} | w) P(w)
$$
- $P(w)$: prior distribution over parameters $w$
Linear Regression via MAP
$$
\argmax_w \log[P(\mathbf{X} | w) P(w)]
$$
如果假設 $w \sim \mathcal{N}(0, \lambda^{-1} I)$，則
$$
\begin{aligned}
\log [P(\mathbf{X} | w) P(w)] &= \log P(\mathbf{X} | w) + \log P(w) \newline
&\propto -\sum_i (y_i - w^{\top} x_i)^2 \newline
& \quad + \sqrt{\frac{1}{(2\pi)^D \text{det}(\lambda^{-1} I)}} \exp\left( -\frac{1}{2} (w-0)^\top (\lambda^{-1}I)^{-1} (w-0) \right) \newline
&\propto -\sum_i (y_i - w^{\top} x_i)^2 - \lambda |w|^2 \newline
\end{aligned}
$$
所以 MAP 的目標變成
$$
\text{argmin}_w \sum_i (y_i - w^{\top} x_i)^2 + \lambda |w|^2
$$
- 這就是 Ridge Regression 的目標函數
- $P(w)$ 就是 weight decay 的來源
ML and MAP estimation
- ML estimator $\theta_{ML}$ 是 consistent 的，也就是說當樣本數 $N \to \infty$ 時，$\theta_{ML} \to \theta^*$，只要 $P(y|x; \theta^*)$ 是在我們假設的 $F$ 裡面
- 在樣本數 ($N$) 足夠大的情況下，跟其他所有也是「準確（一致）」的估計方法相比，MLE 的均方誤差 (MSE) 是最小的。
- MAP estimator 可以用在 $N$ 較小的情況下，因為它加入了 prior knowledge，可以幫助減少 overfitting 的風險，減少模型的 variance
Bayesian Estimation
把 prediction 和 estimation 合在一起看，一次算出答案
$$
\hat{y} = \argmax_y P(y | x^\prime, \mathbf{X}) = \argmax_y \int P(y, \Theta | x^\prime, \mathbf{X}) d\Theta
$$
- 考慮所有的 $\Theta$ 來做預測
- 適合在 $N$ 很小的時候，模型不會 Overfit
- 不適合 在 $N$ 很大的時候，計算量會很大