樣本量估計

ERM

  1. 真實(shí)損失
    定義D為總體分布，f為真實(shí)標(biāo)簽函數(shù)，h為標(biāo)簽函數(shù)，也叫模型或分類器。
    L_{D,f}(h)為在總體分布和真實(shí)標(biāo)簽函數(shù)分別為D和f時h所對應(yīng)的誤差，也叫做真實(shí)損失。其公式為
    \begin{align} L_{D,f}(h) &= P_{x \sim D}[f(h(x) \neq f(x)] \\ &= D(\{x \in D:h(x) \neq f(x)\}) \\ \end{align}

  2. 經(jīng)驗(yàn)損失
    抽取m個獨(dú)立同分布樣本，組成一個m-tuples的樣本組S_x，將S_x的集合定義為樣本集S。
    以[m]表示數(shù)據(jù)集{1,2,...,m}，L_S表示形式上的經(jīng)驗(yàn)損失函數(shù)。
    則有如下經(jīng)驗(yàn)損失的定義公式
    L_S(h)=\frac{\|\{i \in [m]: h(x_i)\neq y_i \} \|}{m}
    當(dāng)L_S \to 0時，可訓(xùn)練得到模型h_S。

  3. 過擬合
    定義\epsilon為誤差精度，過擬合是指經(jīng)驗(yàn)損失可訓(xùn)練而真實(shí)損失超過了誤差精度，表達(dá)式為
    L_{D,f}(h_S)>\epsilon
    為消除過擬合，我們主要手段是限制合理模型范圍。

  4. 經(jīng)驗(yàn)風(fēng)險最小化(ERM)
    定義模型的有限假設(shè)類\mathscr{H}，則令
    h_S=\arg\min_{h \in \mathscr{H} }L_S(h)

置信度

  1. 誤導(dǎo)集
    定義模型的有限假設(shè)類\mathscr{H}，則無效的模型集合為
    \mathscr{H}_B = \{ h \in \mathscr{H}:L_{D,f}(h)>\epsilon \}
    定義S_x表示樣本集S中的一個樣本組，則樣本組的誤導(dǎo)集可表示為
    M=\{S_x \in S: \exists h \in \mathscr{H}_B , L_S(h) \to 0 \}

  2. 置信度
    定義_\delta為抽取到無效樣本組的概率，1-\delta為置信度。其定義式為
    \delta = D^m(\{ S_x \in S:L_{D,f}(h_S)>\epsilon \})
    如下推導(dǎo)
    \begin{align} \delta &\le D^m(M) \\ & \le \sum_{h \in \mathscr{H}_B}D^m(\{S_x \in S: L_S(h) \to 0 \}) \\ & = \sum_{h \in \mathscr{H}_B}\prod_{i=1}^{m}D(\{ x_i:h(x_i)=y_i=f(x_i) \}) \\ & \le \sum_{h \in \mathscr{H}_B}\prod_{i=1}^{m}(1-\epsilon) \\ & = \| \mathscr{H}_B \| (1-\epsilon)^m \\ & \le \| \mathscr{H} \| e^{-\epsilon m} \end{align}
    得到
    \delta \leq \| \mathscr{H} \| e^{-\epsilon m}

  3. 樣本量
    m \ge \frac{\ln(\| \mathscr{H} \|/\delta)}{\epsilon}

舉例：性別估計是個二分類，假設(shè)使用1000個0-1特征，則\| \mathscr{H} \|=2^{1000}，根據(jù)經(jīng)驗(yàn)\delta=0.001，希望的精度\epsilon=0.1，則樣本量m \ge 10100\ln(2)

設(shè)模型參數(shù)數(shù)量為N，參數(shù)取值范圍為R，則
\begin{align} m & \ge \frac{\ln(\| \mathscr{H} \|/\delta)}{\epsilon} \\ & = \frac{N\ln(R)- \ln(\delta)}{\epsilon} \end{align}
可見樣本數(shù)量應(yīng)與參數(shù)數(shù)量N成正比例關(guān)系。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容