L1, L2 norm in definition, loss functino and regularization

--- tags: norm, l1, l2, L1, L2, length, Norm, NORM, distance, similarity, cauchy inequality, triangle inequality, arg, argmin, argmax, minimization, FL --- # L1, L2 norm in definition, loss function and regularization 本文乃下方來源之個人心得整理： * Ref1: 黃子嘉，線性代數及其應用 (下) 第五版 * [Ref2: Stanford University 電機系上課簡報，Supervised Learning via Empirical Risk Minimization](https://web.archive.org/web/20181024045752/http://ee104.stanford.edu/lectures/supervised.pdf) * [Ref3: 台部落理解L1，L2 範數在機器學習中應用阪本龍一 2019-03-07 13:04](https://www.twblogs.net/a/5c80a66abd9eee35cd693c3e) * [Ref4: Hung-yi Lee，Tips for Deep Learning](https://speech.ee.ntu.edu.tw/~tlkagk/courses/ML_2017/Lecture/DNN%20tip.pdf) ## Definition ==Norm 的定義就是向量的長度 (length)== 1. 由內積定義： * 前言--內積的定義： * 內積 (inner product) 是一個將有序對對應至純量的函數，記作：$<\cdot,\cdot>: V \times V \rightarrow F$ * 定義 norm： $||v|| := \sqrt{<v, v>}$ 2. 由長度線性空間定義 * 假設 $V$ 為佈於 $F$ 的向量空間，定義 $||\cdot||: V \rightarrow F$ 為一個函數滿足 $\forall v,u \in V, \alpha \in F$, 並滿足下列三個性質： 1. $||v|| \geq 0$ and $||v|| = 0 \Leftrightarrow v=0$ (零向量的長度是零) 2. $||\alpha v|| = |\alpha| \; ||v||$ (純量可提出) 4. $||v+u|| \leq ||v||+||u||$ (三角不等式) 則稱 $V$ 是長度線性空間 (normed linear space) 且 $||v||$ 稱為 $v$ 的長度 (norm)。 * 補充--距離： * 所謂的距離 (distance) 就是兩向量相減後，再取 norm。即 $d(x,y):=||x-y||$ > 個人理解：「兩個對象之間的長度」才稱為距離；而單獨一個對象的長度通常不會稱為距離，即使依國中數學會解釋為「某一個向量點至零點 (原點) 的距離」。故只有一個向量時，該向量的 Norm (范數) 解釋為向量的長度應該更貼切。 * 補充--==一般化的 $p$-norm 定義==： * $||x||_p := [ \sum_{i=1}^{n} |x_i|^p ]^{1/p} = (|x_1|^p + |x_2|^p + ... +|x_n|^p)^{1/p}$ ## L1-norm $||x||_1 := \sum_{i=1}^{n}|x_i|$ * L1-norm 又稱為 Taxicab-norm (計程車幾何範數) 或 Manhattan-norm (曼哈頓距離範數) ## L2-norm $||x||_2 := [ \sum_{i=1}^{n} |x_i|^2 ]^{1/2} = \sqrt{|x_1|^2 + |x_2|^2 + ... +|x_n|^2}$ ## 機器學習應用 norm 在機器學習領域的兩個地方： 1. Loss Function：描述損失函數本身 2. Regularization：描述損失函數額外增加的「參數的正規化項」 --- ### Loss Function (損失函數) 與 Empirical Risk Function (經驗風險函數) 狹義上，「損失函數 (Loss Function)」又可稱為「風險函數 (Risk Function)」是在描述**單一筆資料**的預測值 (prediction) 與目標值 (target) 之間的誤差。而**多筆資料的平均損失值**稱為「**經驗風險函數 (Empirical Risk Function)**」。但是廣義上，人們稱呼「損失函數 (Loss Function)」時，經常是代指「經驗風險函數 (Empirical Risk Function)」。這也許是溝通方便或單純一般人對定義不了解所導致。 * 前言--資料、features (特徵資料)、predictor (預測模型): * 定義原始資料 ($u$) 與特徵函數 (feature function) * Use $u$ to denote the **raw input data** * $x$ = $\phi{(u)}$ is the corresponding **feature vector** > **Often $x$ is a ++vector of feature++：** > 我們定義 $x$ 是 predictor 的輸入，而通常 $x$ 並不是++最原始的資料 (定義為 $u$)++，而是經過++特徵工程 (Feature Engineering)++ 萃取出的++特徵向量 (feature vector $x$)++ 再當作預測模型的輸入資料。 * $\phi$ is feature (extractor) function (特徵萃取函數) 或 embedding function > 換句話說，Extractor 的輸出就稱為 embedding (目前中文只翻作「嵌入」，但與此處的意義不太貼近)。 > > 通常 embedding 是指 a laten vector, with not necessarily the different dimension, responding to input data. * 定義模型的 (資料對): * Given data $x_1, x_2, ..., x_n \in R^d$ * ($R^d$ 是實數域，每個 $x_i$ 擁有 d 個 feature 維度) * $x$ is called the **independent variable** or **feature vector** * And $y_1, y_2, ..., y_n \in R$ * $y$ is called the **outcome** or **response** or **target** or **dependent variable** or ++label (視情況而定，若為非監督式學習則無 label)++ * Often $y$ is something we want to predict * We don’t know the ‘true’ relationship between $x$ and $y$ * **Thus $(x_i, y_i)$ is the $i$-th data pair (資料對) or observation (觀察值) or example** * 定義我們的目標： * 我們希望模型輸出與目標 $y$ 越接近越好，稱為 Data Fitting (資料擬合)，即 $y \approx f(x)$ * 定義 predictor: * We seek a predictor (or model) $g$: $R^d \rightarrow R$ * for feature vector $x$ and our prediction (of y) is $\hat{y} = g(x)$，即 $\hat{y}$ 是 predictor 的輸出 * 資料擬合中 (也就是機器學習所說的訓練階段)，我們希望模型預測值與資料對盡可能相似 $\hat{y_i} \approx y_i$ * 然而，我們真正的目標是希望模型對於「未見資料」亦能達到 $\hat{y} \approx y$ for $(x, y)$ pairs we have not seen. #### 損失函數數學定義: * A **loss** or **risk function** $\mathcal{l} = R \times R \rightarrow R$ quantifies how well (more accurately, how badly) $\hat{y}$ approximates $y$ * Smaller values of $\mathcal{l}(\hat{y},y)$ indicate that $\hat{y}$ is a good approximation of $y$ * Typically (but not always) $\mathcal{l}(\hat{y},y)=0$ and $\mathcal{l}(\hat{y},y) \geq 0$ for all $\hat{y}$, $y$ * ==L1-norm Loss== * 正式名稱應為「==Absolute Loss (絕對損失)==」 * 函數：$\mathcal{l}(\hat{y},y) = |\hat{y} - y|$ * ~~又稱作 Least Absolute Deviation (LAD，最小絕對偏差)~~ * ==L2-norm Loss== * 正式名稱應為「==Quadratic Loss (平方損失)==」，俗稱「==Square Loss==」 * 函數：$\mathcal{l}(\hat{y},y) = (\hat{y} - y)^2$ * ~~又稱作 Least Squares Error (LSE, 最小平方誤差)~~ #### 經驗風險函數數學定義 * Empirical Risk Function 其實就是多筆資料對 (data pairs) 的平均損失值 > **The empirical risk** is **the average loss over the data points**, > $\mathcal{L} = \frac{1}{n} \sum_{i=1}^{n} \mathcal{l}(\hat{y_i},y_i)= \frac{1}{n} \sum_{i=1}^{n} \mathcal{l}(f(x_i),y_i)$ > if $\mathcal{L}$ is small, the predictor predicts the given data well > > When the predictor is parametrized by $\theta$, we write > $\mathcal{L(\theta)} = \frac{1}{n} \sum_{i=1}^{n} \mathcal{l}(g_\theta(x_i),y_i)$ > to show the dependence on the predictor parameter $\theta$ * 經驗風險函數也可以寫成 L1-norm 或 L2-norm 的形式，直接將對應公式帶入即可。 * **L1-norm** lose function 的 **empirical risk function 又稱為「==mean-absolute error (平均絕對誤差)==」**: $\mathcal{L} =$ MAE $=\frac{1}{n} \sum_{i=1}^{n} |g(x_i) - y_i|$ for $i$-th data pair > mean-absolute error has same units/scale as outcomes $y_i$ * **L2-norm** lose function 的 **empirical risk function 又稱為「==mean-square error (平均平方誤差)==」**: $\mathcal{L} =$ MSE $= \frac{1}{n} \sum_{i=1}^{n} (g(x_i) - y_i)^2$ for $i$-th data pair > often we use **root-mean-square error**, $RMSE = \sqrt{MSE}$, which has same units/scale as outcomes $y_i$ #### ==Empirical Risk Minimization (求解經驗風險最小化)== * 補充: Empirical Risk Function 其實就是文獻中常提到的 Objective Function (目標函數)，求解 Empirical Risk Minimization 就可以得到使損失函數輸出最小值的參數 $\theta$ > **Empirical Risk Minimization (ERM)** is a general method for choosing the parameter $\theta$ in a parametrized predictor $g_{\theta}(x)$ > * ERM: choose $\theta$ to minimize empirical risk $\mathcal{L(\theta)}$ > * thus, ERM chooses $\theta$ by attempting to match given data > * for the linear predictor $g_{\theta}(x)=\theta^{\intercal} \cdot x$, we have $\mathcal{L(\theta)} = \frac{1}{n} \sum_{i=1}^{n} \mathcal{l}(\theta^{\intercal} \cdot x_i, y_i)$ > Often there is no analytic solution to this minimization problem, so we use numerical optimization to find $\theta$ that minimizes $\mathcal{L(\theta)}$ * 在機器學習中除了數值方法之外，也可以使用梯度下降法求解 empirical risk minimization problem #### (額外討論個人見解) 經驗風險函數與期望值之間的關係 * 經驗風險函數就是多筆資料對 (data pairs) 的平均損失值 * 期望值是隨機樣本的**加權平均值**，並以隨機樣本的**機率值作為權重值**。只有在均勻分佈 (Uniform Sampling) 的情況下，才會假設所有隨機樣本的抽樣機率相同，機率等於 $\frac{1}{n}$。 * **期望值不一定是平均值，會有這個誤會其實是我們計算樣本平均值的無偏估計時，最終得到樣本平均值的期望值會是母體平均值，期望值只是一個估計變量的概念，可以套用在任何變量上，公視也會不一樣。** * 談到期望值的時候有三重點： 1. 這個期望值公式想要估計的對象是誰 2. 方法的重點聚焦在抽樣 (Sampling) 3. 我們真正在意的期望值是不偏估計值 * 所以一般情況，不論是損失函數或經驗風險函數**都不會**用期望值的方式來表達，損失函數本身是強調「誤差」，經驗風險函數本身是要強調「參數與誤差之間的變化，並希望找到最好的餐數使損失函數值達到最小」，而期望值本身是強調「透過某個特殊推導的不偏估計算式，可以達到的目標值」或闡述「本估計的目標是誰」。**以這個想法來說，經驗風險函數的期望值，也就是其最理想目標，就是使損失函數值達到最小化**。 因此若硬要寫出數學式的話大概可以這樣表示： $\mathbb{E}[\mathcal{L(\theta)}] = \min_{\theta}\mathcal{L(\theta)}$ --- ### Regularization (正規化) 在機器學習中，在損失函數中增加正規化項 (Regularization Term) 可以降低模型過擬合 (Overfitting) 的問題，進而提升模型對於未見資料的預測正確率。而增加參數的 L1/L2-norm 可以使模型的參數變得更加稀疏 (sparse)，使參數的值平均變小或是有些值變成零，讓模型對輸入資料的敏感度下降，這又稱為平滑化 (Smoothness)。 * 前言： * Loss function 加入 Regularization 之後要重新改寫 Loss Funcion: $\mathcal{L(\theta)'} = \mathcal{L(\theta)} + \lambda \cdot \frac{1}{p} \cdot ||\theta||_p$ 其中 $\lambda$ 是控制正規化項的比重的超參數，而 $\frac{1}{p}$ 只是為了後面偏微分的推導比較方便，實務上可以將其視為 $\lambda$ 的一部分。 * 對於 Regularization Term "$\lambda \cdot \frac{1}{p} \cdot ||\theta||_p$"，其中的參數都不會考慮 bias parameter，因為 bias parameter 對於平滑化沒有的關聯。 > Model paremeter 中，weights 值越小則越 smooth，但 bias 只是對 model function 造成位移，並不會改變 error of variance，反而會改變 error of bias。 * 為了方便後推導描述，定義參數為 $\theta$ 是所有模型參數 $w$ 的集合 $\theta = \{w_1, w_2, ..., w_m\}$ 假設模型有 m 個參數 $w$。 * 關於參數最佳化的目標式可以如此描述： $\theta^{*} = \arg \min_\theta \mathcal{L(\theta)'}$ >「$\arg min_{\theta} \mathcal{L(\theta)'}$」的意思是「回傳使 lose function's lose value 值達到最小的參數 $\theta$」，若未加上 $\arg$，則 $min_{\theta} \mathcal{L(\theta)'}$ 是回傳最小的 lose value。 > > 在 [StackExchange 的討論](https://math.stackexchange.com/questions/227626/explanation-on-arg-min)提到: > "$\arg \min$ (or $\arg \max$) **return the input** for minimum (or maximum) output." * L1-norm Regularization * ![](https://i.imgur.com/Ok3xnzz.png) * 推導後，L1-regularization 是更新參數 $w_i^{t+1}$ 時，$w_i^{t}$ 會減去一個與自身值 ($w_i^{t}$) 乘上 $\eta \lambda$ 的固定值 * 雖然更新速度較為固定，但是當 $w_i$ 值很小時，$w_i$ 更新較快，而且**容易產生 $w_i = 0$ 的現象，使得 $\theta$ 相較 L2-regularization 能使 model 更加 Sparse。** * L2-norm Regularization * ![](https://i.imgur.com/Vl6yosO.png) * 推導後，L2-regularization 是更新參數 $w_i^{t+1}$ 時，$w_i^{t}$ 會先乘上一個小於且趨近 1 的小數 (通常 $\eta \lambda$ 值都很小)，再減去 gredient，即 $w_i^{t}$ 先變小再減去一個很小的梯度 (L2 的函數圖形是拋物線，$w_i$ 趨近零時，斜率變緩，即梯度也逐漸變小)。 * 當 $w_i$ 值離零很遠時 (極大或極小)，$w_i$ 向零更新地很快；但是反之，當 $w_i$ 值趨近零則更新得慢。並且 L2-regularization 先變小再減去某值，使 $w_i$ 不容易變成零值，**容易產生所有參數均小的現象。通常效果不如 L1-regularization 好。** * 探討： 1. Regu 是使值不要離零太遠但效果可能不如 early stop 2. L1 sparse 有零有大值、L2 平均都得到小值