本章是關(guān)于機(jī)器學(xué)習(xí)的理論基礎(chǔ)嘲叔，其目的是分析學(xué)習(xí)任務(wù)的困難本質(zhì)塞关，為學(xué)習(xí)算法提供理論保證，并根據(jù)分析結(jié)果指導(dǎo)算法設(shè)計(jì)絮供。

12.1 基礎(chǔ)知識(shí)

本章主要討論二分類(lèi)問(wèn)題关筒，故y_i∈Y={-1,+1}。
給定樣本集D={(x₁,y₁),(x₂,y₂),…,(x_m,y_m)}杯缺，x_i∈X。樣本服從某個(gè)分布Ψ睡榆，D中樣本都是獨(dú)立同分布樣本萍肆。
設(shè)h為X→Y的一個(gè)映射，泛化誤差E(h)和h在D上的經(jīng)驗(yàn)誤差E^(h)分別為

不合

• 常用不等式
  1.Jensen不等式：對(duì)任意凸函數(shù)f(x)讹堤，有
  
  2.Hoeffding不等式：若x₁,x₂,…吆鹤，x_m為m個(gè)獨(dú)立隨機(jī)變量，且0≤x_i≤1洲守，則對(duì)于任意ε＞0疑务，有
  
  3.McDiarmid不等式：若x₁,x₂,…,x_m為m個(gè)獨(dú)立隨機(jī)變量，且1≤i≤m梗醇，函數(shù)f滿(mǎn)足
  sup是單詞supremum的簡(jiǎn)寫(xiě),意思是最小上界
  則對(duì)任意ε＞0知允，有

12.2 PAC學(xué)習(xí)

計(jì)算機(jī)理論中最基礎(chǔ)的理論為概率近似正確PAC學(xué)習(xí)理論。PAC學(xué)習(xí)理論有四個(gè)核心定義：PAC辨識(shí)叙谨、PAC可學(xué)習(xí)温鸽、PAC學(xué)習(xí)算法、樣本復(fù)雜度唉俗。在講解四個(gè)定義前嗤朴，先說(shuō)明幾個(gè)名詞配椭。

• 幾個(gè)名詞解釋
  1）設(shè)樣本空間X到標(biāo)記空間Y的映射為c，稱(chēng)為概念(concept)雹姊。
  它決定了樣本x的真實(shí)標(biāo)記y股缸，即對(duì)任意樣本，有y=c(x)成立吱雏；則c稱(chēng)為目標(biāo)概念敦姻。
  目標(biāo)概念c構(gòu)成的集合C，稱(chēng)為"概念類(lèi)"歧杏。
  2）假設(shè)空間H：給定學(xué)習(xí)算法￡镰惦，它所考慮的所有可能概念的集合為假設(shè)空間H。
  H與C通常不同犬绒，因?yàn)镠包含的可能目標(biāo)概念除了真實(shí)目標(biāo)概念外還有其他可能目標(biāo)概念旺入，即學(xué)習(xí)算法事先不知道概念類(lèi)C的存在。
  也就是說(shuō)凯力，對(duì)于H里面的可能概念h茵瘾，是一個(gè)假設(shè)h，h∈H咐鹤，h也是樣本空間X→標(biāo)記空間Y的映射拗秘。
  3）可分與不可分
  ① 若目標(biāo)概念c∈H，則H中存在假設(shè)h能將所有樣本按照與其真實(shí)標(biāo)記一致的方式正確分類(lèi)祈惶，則該問(wèn)題對(duì)學(xué)習(xí)算法￡來(lái)說(shuō)是可分的雕旨、一致的。
  ② 若目標(biāo)概念c?H捧请，則H中不存在假設(shè)h能將所有樣本正確分類(lèi)凡涩，則該問(wèn)題對(duì)學(xué)習(xí)算法￡來(lái)說(shuō)是不可分的、不一致的疹蛉。

由于機(jī)器學(xué)習(xí)過(guò)程中受到諸多因素制約突照，如，樣本數(shù)量有限氧吐、采樣的偶然性讹蘑，因此我們無(wú)法總是精確地學(xué)到目標(biāo)概念真實(shí)映射c。
于是筑舅，我們退而求其次座慰。給定數(shù)據(jù)集D，我們希望基于學(xué)習(xí)算法￡學(xué)得的模型所對(duì)應(yīng)的假設(shè)h盡可能接近目標(biāo)概念c翠拣。
也就是說(shuō)版仔，以較大的概率學(xué)得誤差滿(mǎn)足預(yù)設(shè)上限ε的模型，這就是"概率"，"近似正確"的含義蛮粮。下面用數(shù)學(xué)語(yǔ)言來(lái)進(jìn)行描述：

• 定義1：PAC辨識(shí)
  對(duì)0＜ε,δ＜1益缎，所有c∈C和分布Ψ，若存在學(xué)習(xí)算法￡然想，其輸出假設(shè)h滿(mǎn)足莺奔，

  學(xué)習(xí)算法￡能以較大的概率(至少 1-δ) 學(xué)得目標(biāo)概念c的近似 (誤差最多為 ε)
  則稱(chēng)學(xué)習(xí)算法￡能從假設(shè)空間對(duì)中 PAC 辨識(shí)概念類(lèi) C。

• 定義2：PAC可學(xué)習(xí)
  令m表示在分布Ψ中獨(dú)立同分布采樣得到的樣本數(shù)目变泄。
  對(duì)0＜ε,δ＜1令哟，對(duì)所有分布Ψ，若存在學(xué)習(xí)算法￡和多項(xiàng)式函數(shù)poly()妨蛹，使得 對(duì)于任意m≥ploy(1/ε,1/δ,size(x),size(c))屏富，
  有￡能從假設(shè)空間H中PAC辨識(shí)概念類(lèi)C，則概念類(lèi)C是PAC可學(xué)習(xí)的蛙卤。
  size(x)和size(c)分別表示數(shù)據(jù)本身的復(fù)雜度和目標(biāo)概念的負(fù)責(zé)度狠半。

• 定義3：PAC學(xué)習(xí)算法
  

• 定義4：樣本復(fù)雜度
  

• PAC學(xué)習(xí)理論的作用
  PAC 學(xué)習(xí)給出了一個(gè)抽象地刻畫(huà)機(jī)器學(xué)習(xí)能力的框架，基于這個(gè)框架能對(duì)很多重要問(wèn)題進(jìn)行理論探討颤难。

• PAC的關(guān)鍵
  PAC學(xué)習(xí)的關(guān)鍵因素是假設(shè)空間H的復(fù)雜度典予。
  在現(xiàn)實(shí)任務(wù)中，假設(shè)空間H往往和概念類(lèi)C不同乐严，即H≠C。
  一般而言衣摩，H越大昂验，包含任意目標(biāo)概念c的可能性越大，但尋找難度隨之增加艾扮。若H有限時(shí)既琴，稱(chēng)H為"有限假設(shè)空間"；否則為"無(wú)線假設(shè)空間"泡嘴。

12.3 有限假設(shè)空間

12.3.1 可分情形

可分情形意味著目標(biāo)概念c∈假設(shè)空間H甫恩。給定m個(gè)樣本的數(shù)據(jù)集D，如何找出滿(mǎn)足誤差參數(shù)ε的假設(shè)h呢酌予？

一種策略如：由于D中的樣例標(biāo)記y_i是由目標(biāo)概念c映射的磺箕，且c∈H，也就是說(shuō)訓(xùn)練集D上出現(xiàn)了錯(cuò)誤標(biāo)記的假設(shè)h抛虫，則h肯定不是我們要的c松靡。因此，我們只保留與D一致的假設(shè)h建椰，剔除與D不一致的假設(shè)即可雕欺。
通常，訓(xùn)練集規(guī)模有限，假設(shè)空間H可能存在多個(gè)假設(shè)h與D一致屠列，對(duì)于這些h啦逆，我們需要進(jìn)一步比較，找出更優(yōu)的h與目標(biāo)概念c近似笛洛。

那么需要多少(m個(gè))樣本才能學(xué)得近似目標(biāo)概念c的假設(shè)呢夏志？
PAC學(xué)習(xí)中，只要訓(xùn)練集D的規(guī)模能使學(xué)習(xí)算法￡以概率1-δ找到目標(biāo)假設(shè)的ε近似即可撞蜂。最終m如下

樣本數(shù)m

12.3.2 不可分情形

不可分溉贿，則說(shuō)明c?H，這是較困難的學(xué)習(xí)問(wèn)題浦旱。由于c?H宇色，則對(duì)于任何假設(shè)h有，經(jīng)驗(yàn)誤差E^(h)≠0颁湖，即任何一個(gè)假設(shè)h都會(huì)在訓(xùn)練集上出現(xiàn)錯(cuò)誤宣蠕。

由Hoeffding不等式可知：

• 引理
  若訓(xùn)練集D包含m個(gè)獨(dú)立同分布樣本，0<ε<1甥捺，則對(duì)任意h抢蚀，有

• 推論
  若訓(xùn)練集D包含m個(gè)獨(dú)立同分布樣本，0<ε<1镰禾，則對(duì)任意h皿曲，有下式以至少1-δ的概率成立：

  該式表明，樣本數(shù)m越大吴侦，經(jīng)驗(yàn)誤差E^(h)與泛化誤差E(h)越接近

• 定理
  若H為有限假設(shè)空間屋休，0<δ<1，則對(duì)任意h∈H备韧，有

• 不可知PAC學(xué)習(xí)
  當(dāng)c?H劫樟，學(xué)習(xí)算法就難以找到近似于目標(biāo)概念c的h；但是在假設(shè)空間H中织堂，一定有假設(shè)h使得泛化誤差最小叠艳，找出該假設(shè)h的ε也是一個(gè)靠近c(diǎn)的較好的目標(biāo)。

  這樣子易阳，目標(biāo)就轉(zhuǎn)化為在H中尋找使得泛化誤差E(h)最小的假設(shè)h了虑绵。
  以此為目標(biāo)可將PAC學(xué)習(xí)推廣到c?H的情況，這就是"不可知學(xué)習(xí)"闽烙。

  具體數(shù)學(xué)描述如下：
  m表示獨(dú)立分布樣本數(shù)目翅睛，0<ε,δ<1声搁。
  對(duì)所有分布，若存在學(xué)習(xí)算法￡和多項(xiàng)式函數(shù)ploy(·,·,·,·)捕发，
  使得對(duì)于任何樣本數(shù)目m≥ploy(1/ε,1/δ,size(x),size(c))疏旨，學(xué)習(xí)算法￡能從假設(shè)空間H中得到假設(shè)h滿(mǎn)足下式，則稱(chēng)H是不可知PAC學(xué)習(xí)的扎酷。

  h∈H滿(mǎn)足該式檐涝，則稱(chēng)H是不可知PAC學(xué)習(xí)的

12.4 VC維

現(xiàn)實(shí)學(xué)習(xí)中通常面臨的是無(wú)線假設(shè)空間。對(duì)此情形的學(xué)習(xí)進(jìn)行研究法挨，需要度量假設(shè)空間的復(fù)雜度谁榜。最常見(jiàn)的方法是考慮假設(shè)空間的"VC維"。在介紹VC維之前先介紹幾個(gè)概念凡纳。

• 幾個(gè)概念
  給定假設(shè)空間H和樣本集D={x₁,…,x_m}窃植，H中每個(gè)假設(shè)h都能對(duì)x_i賦予標(biāo)記，所有樣本的標(biāo)記結(jié)果為

  m越大荐糜，所有假設(shè)對(duì)D中樣本所能賦予標(biāo)記的可能結(jié)果數(shù)目也隨之增大巷怜。
  1）增長(zhǎng)函數(shù)
  對(duì)所有m∈N(N是自然數(shù)域)，假設(shè)空間H的增長(zhǎng)函數(shù)為∏_H(m)暴氏，即
  增長(zhǎng)函數(shù)
  增長(zhǎng)函數(shù)表示假設(shè)空間H對(duì)m個(gè)樣本所能賦予標(biāo)記的最大可能結(jié)果數(shù)延塑。可能結(jié)果數(shù)越大，H表示能力越強(qiáng)答渔，對(duì)學(xué)習(xí)任務(wù)的適應(yīng)能力也越強(qiáng)关带。
  增長(zhǎng)函數(shù)描述了假設(shè)空間的表示能力，由此反映出假設(shè)空間的復(fù)雜度沼撕。

  2）對(duì)分和打散
  可以用增長(zhǎng)函數(shù)來(lái)估計(jì)經(jīng)驗(yàn)誤差與泛化誤差之間的關(guān)系：
  定理1：對(duì)假設(shè)空間H宋雏，m∈N, 0<ε<1和任意h，有

  假設(shè)空間中不同的假設(shè)h對(duì)于D中樣本的標(biāo)記不盡相同端朵，但即使有多個(gè)假設(shè)，對(duì)D中的樣本標(biāo)記的可能結(jié)果是有限的：對(duì)m個(gè)樣本燃箭，最多有2^m中可能冲呢。
  對(duì)分：對(duì)二分類(lèi)問(wèn)題，H中的假設(shè)對(duì)D中樣本賦予標(biāo)記的美中可能結(jié)果稱(chēng)為對(duì)D的一種"對(duì)分"招狸。如m=1敬拓，最多有2種可能，即2種對(duì)分裙戏，則其中一種"對(duì)分"乘凸，為"+"或者"-"。
  打散：若假設(shè)空間H能實(shí)現(xiàn)D上的所有對(duì)分累榜，即∏_H(m)=2^m营勤，則稱(chēng)D能被假設(shè)空間H"打散"灵嫌。

• VC維
  假設(shè)空間H的VC維是能被H打散的最大示例集的大小，即

  VC(H)=d表明存在(不是所有)大小為d的樣本集能被假設(shè)空間對(duì)打散葛作。VC維的定義與數(shù)據(jù)分布無(wú)關(guān)寿羞；因此，在數(shù)據(jù)分布未知時(shí)仍能計(jì)算出假設(shè)空間H的VC維赂蠢。
  VC維的計(jì)算如下：若存在大小為d的示例集能被H打散绪穆，但不存在任何一個(gè)大小為d+1的示例集能被對(duì)打散，則對(duì)的VC維是d虱岂。如

• VC維與增長(zhǎng)函數(shù)的關(guān)系
  引理1：若假設(shè)空間H的VC維為玖院，則對(duì)任意m∈N，有

• 增長(zhǎng)函數(shù)的上界
  推論1：若假設(shè)空間H的VC維為d第岖，則對(duì)任意整數(shù)m≥d难菌，有

  e為自然常數(shù)

• 基于VC維的泛化誤差界
  1）若假設(shè)空間H的VC維為d，則對(duì)任意m>d, 0<δ<1和h∈H绍傲，有

  基于VC維的泛化誤差界扔傅，由定理1和推論1得出
  基于VC維的泛化誤差界是分布無(wú)關(guān)、數(shù)據(jù)獨(dú)立的烫饼。

  2）h表示學(xué)習(xí)算法￡輸出的假設(shè)猎塞，若h滿(mǎn)足下式，則稱(chēng)算法￡為滿(mǎn)足經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則的算法杠纵。

  h滿(mǎn)足該式荠耽，則算法ERM原則

• 定理3
  任何VC維有限的假設(shè)空間H都是不可知PAC學(xué)習(xí)的。

12.5 Rademacher復(fù)雜度

基于VC維的泛化誤差界是與分布無(wú)關(guān)比藻、數(shù)據(jù)獨(dú)立的铝量。Rademacher復(fù)雜度與VC維不同债蜜，它是另一種刻畫(huà)假設(shè)空間的復(fù)雜度的途徑籽前，在一定程度上考慮了數(shù)據(jù)和分布忍级。

• 考慮隨機(jī)噪聲影響的假設(shè)
  給定訓(xùn)練集D={(x₁,y₁),(x₁,y₁),…,(x_m,y_m)}森逮，假設(shè)h的經(jīng)驗(yàn)誤差為

  若對(duì)所有訓(xùn)練樣本都有h(x_i)=y_i恼蓬，即經(jīng)驗(yàn)誤差為0诅需，則有
  也就是說(shuō)渔呵，經(jīng)驗(yàn)誤差最小的假設(shè)是
  但由于有一些噪聲樣本使得預(yù)測(cè)值y_i不是樣本的真實(shí)標(biāo)記责掏。于是馏段，H不如考慮隨機(jī)噪聲影響的假設(shè)轩拨，而不是使經(jīng)驗(yàn)誤差最小的假設(shè)。

  Rademacher隨機(jī)變量
  Rademacher隨機(jī)變量σ_i院喜，它以1/2的概率取值-1或+1亡蓉，基于σ_i，可以將目標(biāo)重寫(xiě)為

  對(duì)于H中所有假設(shè)h喷舀，對(duì)上式取期望得
  σ={σ₁,σ₂,…,σ_m}砍濒，期望的范圍在[0,1]淋肾，體現(xiàn)假設(shè)空間H的表現(xiàn)能力。

• 函數(shù)空間F關(guān)于Z的經(jīng)驗(yàn)Rademacher復(fù)雜度
  考慮實(shí)值函數(shù)空間F和Z={z₁,z₁,…,z_m}梯影，將X和H替換為Z和F巫员。則有
  函數(shù)空間F關(guān)于Z的經(jīng)驗(yàn)Rademacher復(fù)雜度

  經(jīng)驗(yàn)Rademacher復(fù)雜度衡量了函數(shù)空間F與隨機(jī)噪聲在集合Z中的相關(guān)性。

• 函數(shù)空間F關(guān)于Z上分布Ψ的Rademacher復(fù)雜度
  通常我們希望了解函數(shù)空間F上在Z關(guān)于分布Ψ的相關(guān)性甲棍，因此简识，對(duì)所有從Ψ獨(dú)立同分布采樣而得的大小為m的集合Z求期望可得

  函數(shù)空間F關(guān)于Z上分布Ψ的Rademacher復(fù)雜度

• 對(duì)于回歸問(wèn)題的定理1
  

  函數(shù)空間F是區(qū)間[0,1]上的實(shí)值函數(shù)，因此定理1只適用于回歸問(wèn)題感猛。

• 對(duì)于二分類(lèi)的定理2
  

  該定理給出了基于 Rademacher 復(fù)雜度的泛化誤差界七扰。可以看出12.47式與分布有關(guān)陪白，12.48式與數(shù)據(jù)D有關(guān)颈走。

12.6 穩(wěn)定性

算法的"穩(wěn)定性"考察的是算法在輸入發(fā)生變化時(shí)咱士，輸出是否會(huì)隨之發(fā)生較大的變化立由。
給定訓(xùn)練集D={z₁=(x₁,y₁),z₂=(x₂,y₂),…,z_m=(x_m,y_m)}，x_i∈X獨(dú)立同分布樣本序厉，y_i∈{-1,+1}锐膜。對(duì)假設(shè)空間H和學(xué)習(xí)算法￡，令￡_D∈H表示基于訓(xùn)練集D從假設(shè)空間究中學(xué)得的假設(shè)弛房。

1.對(duì)于D有定義以下兩種變化：

2.損失函數(shù)

損失函數(shù)L(￡_D(x),y)刻畫(huà)了假設(shè)￡_D的預(yù)測(cè)標(biāo)記￡_D(x)與真實(shí)標(biāo)記y_i的差別道盏，記為L(zhǎng)(￡_D,z)。有幾種關(guān)于假設(shè)￡_D的損失：

• 泛化損失
  泛化損失
• 經(jīng)驗(yàn)損失
  經(jīng)驗(yàn)損失
• 留一損失
  留一損失

3.算法￡的均勻穩(wěn)定性

對(duì)于任何x∈X文捶，z=(x,y)荷逞，若學(xué)習(xí)算法￡滿(mǎn)足下式，則稱(chēng)對(duì)于損失函數(shù)L粹排，￡滿(mǎn)足β-均有穩(wěn)定性种远。

算法滿(mǎn)足該式，則具有β-均有穩(wěn)定性

4.學(xué)習(xí)算法￡學(xué)得的假設(shè)的泛化誤差界

若損失函數(shù)L有界，即對(duì)所有D和z=(x,y)有0≤L(￡_D,z)≤M斧抱，則有以下定理：

給定m個(gè)獨(dú)立同分布樣本的樣本集常拓，若學(xué)習(xí)算法￡滿(mǎn)足關(guān)于損失函數(shù)L的β均勻穩(wěn)定性渐溶，且損失函數(shù)的上界為M辉浦，0 < δ < 1，則對(duì)任意m≥1茎辐，以至少 1-δ 的概率有

5.穩(wěn)定性與可學(xué)習(xí)性之間的關(guān)系

• ERM原則
  對(duì)損失函數(shù)L若學(xué)習(xí)算法￡所輸出的假設(shè)滿(mǎn)足經(jīng)驗(yàn)損失最小化，則稱(chēng)算法滿(mǎn)足經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則弛槐，簡(jiǎn)稱(chēng)算法是ERM的懊亡。

• 穩(wěn)定性與可學(xué)習(xí)性之間的關(guān)系

十二章思維導(dǎo)圖

思維導(dǎo)圖