---

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

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

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

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

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

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

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

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

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

• Hinge loss（合頁(yè)損失）：這是支持向量機(jī)中使用的損失函數(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（邏輯損失）：這是邏輯回歸中使用的。它對(duì)于異常值更為穩(wěn)健，并且為概率提供了良好的估計(jì)。

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

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

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

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

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

滿足上述條件意味著在大部分情況下，對(duì)于一個(gè)給定的數(shù)據(jù)點(diǎn)，分類器 $h$ 使代理?yè)p失最小化時(shí)，也會(huì)使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)}

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

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

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

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

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

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

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

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

當(dāng)我們的訓(xùn)練數(shù)據(jù)量無(wú)限大時(shí)，使用替代損失函數(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))}]$$

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

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