L1, L2 norm in definition, loss function and regularization

本文乃下方來源之個人心得整理：

• Ref1: 黃子嘉，線性代數及其應用 (下) 第五版
• Ref2: Stanford University 電機系上課簡報，Supervised Learning via Empirical Risk Minimization
• Ref3: 台部落 理解L1，L2 範數在機器學習中應用 阪本龍一 2019-03-07 13:04
• Ref4: Hung-yi Lee，Tips for Deep Learning

Definition

Norm 的定義就是向量的長度 (length)

1. 由內積定義：
   • 前言–內積的定義：
     • 內積 (inner product) 是一個將有序對對應至純量的函數，記作：
       $<\cdot ,\cdot >:V\times V\to F$
   • 定義 norm：
     $||v||:=\sqrt{<v,v>}$
2. 由長度線性空間定義

   • 假設

     $V$ 為佈於
     $F$ 的向量空間，定義
     $||\cdot ||:V\to F$ 為一個函數滿足
     $\mathrm{\forall }v,u\in V,\alpha \in F$, 並滿足下列三個性質：
     1. $||v||\ge 0$ and
        $||v||=0\iff v=0$ (零向量的長度是零)
     2. $||\alpha v||=|\alpha |||v||$ (純量可提出)
     3. $||v+u||\le ||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$ =
      $\varphi (u)$ is the corresponding feature vector

      Often

      $x$ is a vector of feature：
      我們定義

      $x$ 是 predictor 的輸入，而通常

      $x$ 並不是最原始的資料 (定義為

      $u$)，而是經過特徵工程 (Feature Engineering) 萃取出的特徵向量 (feature vector

      $x$) 再當作預測模型的輸入資料。

    • $\varphi$ 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\to R$
    • for feature vector
      $x$ and our prediction (of y) is
      $\hat{y}=g(x)$，即
      $\hat{y}$ 是 predictor 的輸出
    • 資料擬合中 (也就是機器學習所說的訓練階段)，我們希望模型預測值與資料對盡可能相似
      $\widehat{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\to 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)\ge 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}(\widehat{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}\mathcal{(}\theta \mathcal{)}=\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}\mathcal{(}\theta \mathcal{)}$
• thus, ERM chooses
  $\theta$ by attempting to match given data
• for the linear predictor
  $g_{\theta }(x)={\theta }^{⊺}\cdot x$, we have
  
  $\mathcal{L}\mathcal{(}\theta \mathcal{)}=\frac{1}{n}\sum _{i=1}^n\mathcal{l}({\theta }^{⊺}\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}\mathcal{(}\theta \mathcal{)}$

• 在機器學習中除了數值方法之外，也可以使用梯度下降法求解 empirical risk minimization problem

(額外討論個人見解) 經驗風險函數與期望值之間的關係

• 經驗風險函數就是多筆資料對 (data pairs) 的平均損失值
• 期望值是隨機樣本的加權平均值，並以隨機樣本的機率值作為權重值。只有在均勻分佈 (Uniform Sampling) 的情況下，才會假設所有隨機樣本的抽樣機率相同，機率等於
  $\frac{1}{n}$。
• 期望值不一定是平均值，會有這個誤會其實是我們計算樣本平均值的無偏估計時，最終得到樣本平均值的期望值會是母體平均值，期望值只是一個估計變量的概念，可以套用在任何變量上，公視也會不一樣。
• 談到期望值的時候有三重點：
  1. 這個期望值公式想要估計的對象是誰
  2. 方法的重點聚焦在抽樣 (Sampling)
  3. 我們真正在意的期望值是不偏估計值
• 所以一般情況，不論是損失函數或經驗風險函數都不會用期望值的方式來表達，損失函數本身是強調「誤差」，經驗風險函數本身是要強調「參數與誤差之間的變化，並希望找到最好的餐數使損失函數值達到最小」，而期望值本身是強調「透過某個特殊推導的不偏估計算式，可以達到的目標值」或闡述「本估計的目標是誰」。以這個想法來說，經驗風險函數的期望值，也就是其最理想目標，就是使損失函數值達到最小化。
  
  因此若硬要寫出數學式的話大概可以這樣表示：
  
  
  $\mathbb{E}[\mathcal{L}\mathcal{(}\theta \mathcal{)}]=\underset{\theta }{min}\mathcal{L}\mathcal{(}\theta \mathcal{)}$

---

Regularization (正規化)

在機器學習中，在損失函數中增加正規化項 (Regularization Term) 可以降低模型過擬合 (Overfitting) 的問題，進而提升模型對於未見資料的預測正確率。而增加參數的 L1/L2-norm 可以使模型的參數變得更加稀疏 (sparse)，使參數的值平均變小或是有些值變成零，讓模型對輸入資料的敏感度下降，這又稱為平滑化 (Smoothness)。

• 前言：
  • Loss function 加入 Regularization 之後要重新改寫 Loss Funcion:
    
    $\mathcal{L}\mathcal{(}\theta {\mathcal{)}}^{\prime }=\mathcal{L}\mathcal{(}\theta \mathcal{)}+\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 }^{\ast }=\arg \underset{\theta }{min}\mathcal{L}\mathcal{(}\theta {\mathcal{)}}^{\prime }$

    「

    $\arg mi{n}_{\theta }\mathcal{L}\mathcal{(}\theta {\mathcal{)}}^{\prime }$」的意思是「回傳使 lose function's lose value 值達到最小的參數

    $\theta$」，若未加上

    $\arg$，則

    $mi{n}_{\theta }\mathcal{L}\mathcal{(}\theta {\mathcal{)}}^{\prime }$ 是回傳最小的 lose value。

    在 StackExchange 的討論提到:
    "

    $\arg min$ (or

    $\arg max$) return the input for minimum (or maximum) output."

• L1-norm Regularization
  • 
  • 推導後，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
  • 
  • 推導後，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 平均都得到小值