---

機器學習算法的目的是找到一個假設(shè)來擬合數(shù)據(jù)。這通過一個優(yōu)化過程來實現(xiàn)，該過程從預(yù)定義的 hypothesis class（假設(shè)類）中選擇一個假設(shè)來最小化目標函數(shù)。具體地說，我們想找到$\underset{h\in H}{\mathrm{argmin}}\frac{1}{n}\sum _{i=1}^n?(X_i,Y_i,h)$。其中， $H$ 是預(yù)定義的假設(shè)類。

假設(shè)類 $H$是一個函數(shù)集，其中每個函數(shù)都嘗試從輸入特征映射到輸出標簽， H = { h 1 , h 2 , … } H = \{ h_1, h_2, \dots \} H={h1?,h2?,…}。通常，$H$ 由一個特定的算法或模型結(jié)構(gòu)定義，如線性回歸、決策樹等。

首先，0-1損失函數(shù)是最直接的分類誤差度量。對于給定的分類器 $h$，它只是簡單地計算誤分類的數(shù)據(jù)點的數(shù)量。數(shù)學上，這定義為：$\underset{h}{\mathrm{argmin}}\mathbb{E}[1_{Y\ne sign(h(X))}]$。但我們通常遇到的問題是：

1. 真實數(shù)據(jù)的分布 $P(X,Y)$ 是未知的，因此我們不能直接計算上述期望。
2. 0-1損失在計算上是困難的，因為它是不連續(xù)的、非凸的，這使得優(yōu)化變得復(fù)雜。

大數(shù)定律描述了隨機變量的樣本均值與整體均值之間的關(guān)系。它確保了當樣本大小趨于無窮大時，樣本均值趨于整體均值。更形式化地說，考慮一個隨機變量 $X$，其期望值為 $\mathbb{E}[X]$。對于 $X$ 的 $n$ 個獨立同分布的樣本 $X_1,X_2,\dots ,X_n$，它們的樣本均值定義為$\overline{X_n}=\frac{1}{n}{\sum }_{i=1}^n{X}_i$。當 $n\to \infty$ 時, $\overline{X_n}\to \mathbb{E}[X]$。

通過大數(shù)定律，我們可以使用這些樣本來估計某些與分布相關(guān)的數(shù)量，例如期望損失。假設(shè)我們的目標是估計由假設(shè) $h$ 引起的期望損失 $\mathbb{E}[1_{Y\ne \text{sign}(h(X))}]$。我們可以使用來自真實分布的樣本 $\mathcal{D}$ 來估計這個期望：

$$\frac{1}{n}\sum _{i=1}^n{1}_{Y_i\ne \text{sign}(h(X_i))}$$

隨著樣本數(shù)量 $n$ 的增加，上述估計將接近真實的期望損失。

為了在實踐中使問題變得可解，我們使用所謂的 surrogate loss function（替代損失函數(shù)），它們在優(yōu)化上更容易處理，但仍旨在近似0-1損失函數(shù)。

• Hinge loss（合頁損失）：這是支持向量機中使用的損失函數(shù)。
  ? ( X , Y , h ) = max ? { 0 , 1 ? Y h ( X ) } \ell(X,Y,h) = \max \{0,1?Yh(X)\} ?(X,Y,h)=max{0,1?Yh(X)}

• Logistic loss（邏輯損失）：這是邏輯回歸中使用的。它對于異常值更為穩(wěn)健，并且為概率提供了良好的估計。

• Least square loss（最小二乘損失）：主要在回歸問題中使用。

• Exponential loss（指數(shù)損失）：是AdaBoost算法中使用的損失函數(shù)。

大多數(shù)流行的替代損失函數(shù)都是為了在大樣本極限下模擬0-1損失函數(shù)的效果。這些被稱為 classification-calibrated （分類校準的）替代損失函數(shù)。這意味著，如果訓練數(shù)據(jù)無窮大，則使用這些損失函數(shù)訓練的分類器在0-1損失上的表現(xiàn)將與真正的最佳分類器一致。

給定一個代理損失函數(shù) $?$ 和相應(yīng)的函數(shù) $?$ 使得 $?(Yh(X))=?(X,Y,h)$。這里，$Y$ 是標簽，取值為 $(?1,1)$，而 $h(X)$ 是分類器對輸入 $X$ 的預(yù)測得分。為了檢查 $?$ 是否是分類校準的，我們通常檢查以下條件:

1. $?$ 是凸的。
2. $?$ 在0處可導，并且 ${?}^{\prime }(0)<0$。

滿足上述條件意味著在大部分情況下，對于一個給定的數(shù)據(jù)點，分類器 $h$ 使代理損失最小化時，也會使0-1損失最小化。

例如，考慮Hinge損失 ? hinge ( X , Y , h ) = max ? { 0 , 1 ? Y h ( X ) } \ell_{\text{hinge}}(X,Y,h) = \max \{ 0, 1-Yh(X) \} ?hinge?(X,Y,h)=max{0,1?Yh(X)}

對應(yīng)的 $?$ 函數(shù)為 ? ( z ) = max ? { 0 , 1 ? z } \phi(z) = \max \{ 0, 1-z \} ?(z)=max{0,1?z}

這個函數(shù)在 $z=1$ 處是不可導的，但是在 $z=0$ 處是可導的，且其導數(shù)小于0，因此Hinge損失是分類校準的。

現(xiàn)在可以考慮以下兩個分類器的定義：

• $h_s$ 是基于有限訓練數(shù)據(jù)和替代損失函數(shù)的最優(yōu)分類器。
• $h_c$ 是基于整個數(shù)據(jù)分布和0-1損失函數(shù)的最優(yōu)分類器。

使用替代損失函數(shù)和訓練數(shù)據(jù)，我們可以找到 $h_s$：

$$h_s=\underset{h}{\mathrm{argmin}}\frac{1}{n}\sum _{i=1}^n?(X_i,Y_i,h)$$

與此同時，如果我們知道整個數(shù)據(jù)的分布，我們可以找到 $h_c$：

$$h_c=\underset{h}{\mathrm{argmin}}\mathbb{E}[1_{Y\ne \text{sign}(h(X))}]$$

當我們的訓練數(shù)據(jù)量無限大時，使用替代損失函數(shù)得到的 $h_s$ 將與使用0-1損失函數(shù)得到的 $h_c$越來越接近。這可以通過以下公式表示：

$$\mathbb{E}[1_{Y\ne \text{sign}(h_S(X))}]\stackrel{n\to \infty }{?}\mathbb{E}[1_{Y\ne \text{sign}(h_c(X))}]$$

這意味著，當我們基于有限的樣本數(shù)據(jù)集優(yōu)化代理損失時，我們實際上是在優(yōu)化該數(shù)據(jù)集上的經(jīng)驗損失。大數(shù)定律保證，隨著樣本數(shù)的增加，這個經(jīng)驗損失的期望會接近于真實的期望損失。同時，如果我們的代理損失是分類校準的，那么優(yōu)化這個代理損失將隱式地優(yōu)化0-1損失。當訓練數(shù)據(jù)的大小趨向于無窮大時，通過最小化替代損失函數(shù)得到的分類器的期望0-1損失將趨近于最優(yōu)的0-1損失。

當替代損失函數(shù)是凸的且光滑時，我們可以使用一系列的優(yōu)化算法，如梯度下降、牛頓法等，來解決以下問題：
$$h=\underset{h\in H}{\mathrm{argmin}}\frac{1}{n}\sum _{i=1}^n?(X_i,Y_i,h)$$