大數(shù)據(jù)下的PAC－Bayesian學(xué)習(xí)理論綜述

楊雪冰，張文生，楊陽(yáng)

（中國(guó)科學(xué)院 自動(dòng)化研究所，北京 100190）

0 引言

隨著產(chǎn)業(yè)技術(shù)的飛速發(fā)展，大數(shù)據(jù)覆蓋行業(yè)越來(lái)越廣，人們逐漸認(rèn)識(shí)到海量數(shù)據(jù)中蘊(yùn)涵巨額經(jīng)濟(jì)價(jià)值與社會(huì)效益。如何有效地分析數(shù)據(jù)結(jié)構(gòu)，建立數(shù)據(jù)之間的聯(lián)系和挖掘數(shù)據(jù)的內(nèi)在價(jià)值是當(dāng)前人工智能領(lǐng)域的研究熱點(diǎn)。機(jī)器學(xué)習(xí)是人工智能的核心研究方法，然而大數(shù)據(jù)的產(chǎn)生呈現(xiàn)價(jià)值稀疏、規(guī)模巨大、高維異構(gòu)、實(shí)時(shí)非確定、關(guān)系復(fù)雜等特點(diǎn)，使得傳統(tǒng)的機(jī)器學(xué)習(xí)方法無(wú)法直接用于大數(shù)據(jù)處理與分析。目前已有諸多經(jīng)典的機(jī)器學(xué)習(xí)方法經(jīng)過(guò)優(yōu)化與調(diào)整應(yīng)用于大數(shù)據(jù)，同時(shí)也有很多新的針對(duì)大數(shù)據(jù)的思路和方法提出，然而，對(duì)大數(shù)據(jù)的分析與處理仍然處在探索階段，至今未有統(tǒng)一的適合于大數(shù)據(jù)的理論框架與系統(tǒng)應(yīng)用。

按照計(jì)算學(xué)習(xí)理論（computational learning theory）［1］的觀點(diǎn)，概念的可學(xué)習(xí)性是利用機(jī)器學(xué)習(xí)方法挖掘數(shù)據(jù)內(nèi)在價(jià)值時(shí)首先要考慮的。對(duì)于海量數(shù)據(jù)下的問(wèn)題，通過(guò)在理論上對(duì)其是否可學(xué)習(xí)做出判斷，可以顯著降低分析與處理的代價(jià)。然而，傳統(tǒng)意義的可學(xué)習(xí)理論（PAC learnable）在大數(shù)據(jù)學(xué)習(xí)中存在著很多局限性，自提出以來(lái)經(jīng)諸多學(xué)者進(jìn)行了發(fā)展與推廣，其中效果最好、應(yīng)用最廣并且在當(dāng)今仍有后續(xù)研究的便是PAC－Bayesian學(xué)習(xí)理論。該理論將可學(xué)習(xí)理論與貝葉斯學(xué)習(xí)高度結(jié)合，為已有算法提供其泛化誤差界的證明以指導(dǎo)算法改進(jìn)或驗(yàn)證算法是否適合某些具體問(wèn)題。PAC－Bayesian學(xué)習(xí)理論給出的界不依賴(lài)樣本分布以及先驗(yàn)的正確性，同時(shí)給出足夠緊（甚至是最緊）的泛化誤差界，因此在理論與應(yīng)用層面均具有很大的研究?jī)r(jià)值。

湯莉等人在PAC－Bayesian邊界計(jì)算［2－3］方面做了很多突出的工作，且在文獻(xiàn)［4］中從介紹PAC－Bayesian邊界在SVM中的應(yīng)用出發(fā)，詳細(xì)而全面地綜述了PAC－Bayesian邊界在眾多機(jī)器學(xué)習(xí)算法中的應(yīng)用并指出該理論未來(lái)的研究方向，但是并未介紹PAC－Bayesian定理最基本的形式以及最一般的形式，也沒(méi)有對(duì)PAC的核心概念樣本復(fù)雜度進(jìn)行深入考慮，故而沒(méi)有揭示該理論得以廣泛應(yīng)用的根本原因。本文旨在從PAC的角度來(lái)理解PAC－Bayesian學(xué)習(xí)理論的核心內(nèi)容，并探討該理論在大數(shù)據(jù)環(huán)境下得以廣泛應(yīng)用的可能。

基于上述考慮，本文首先介紹PAC可學(xué)習(xí)理論的基本思想，而后簡(jiǎn)要介紹貝葉斯學(xué)習(xí)，進(jìn)而從分析二者的優(yōu)勢(shì)與局限出發(fā)，揭示PAC－Bayesian學(xué)習(xí)理論的產(chǎn)生背景與本質(zhì)內(nèi)涵，最后著眼于大數(shù)據(jù)理論與應(yīng)用，分析PAC－Bayesian適合于大數(shù)據(jù)的原因以及該理論在大數(shù)據(jù)環(huán)境下的研究現(xiàn)狀和未來(lái)的研究方向。

1 PAC可學(xué)習(xí)理論的基本思想

概率近似正確理論（probably approximately correct，PAC），又稱(chēng)可學(xué)習(xí)（learnable）理論，由 Valiant于1984年首次提出［5］，而后在計(jì)算學(xué)習(xí)、統(tǒng)計(jì)機(jī)器學(xué)習(xí)、人工智能、人工神經(jīng)元網(wǎng)絡(luò)、模式識(shí)別等領(lǐng)域得到廣泛研究［1］。PAC是一種基于統(tǒng)計(jì)的學(xué)習(xí)理論，其思想與VC維（Vpanik－Chervonenkis dimension）的思想有很多相近之處［6－8］。PAC可學(xué)習(xí)理論的核心是首先將模型的泛化誤差ε與置信水平δ作為評(píng)價(jià)一個(gè)學(xué)習(xí)模型性能好壞的參數(shù)，而后在給定這兩個(gè)參數(shù)之后，得到一個(gè)所需訓(xùn)練樣本個(gè)數(shù)的理論下界，這個(gè)理論下界便是PAC可學(xué)習(xí)理論中的關(guān)鍵概念，即樣本復(fù)雜度（sample complexity）。下面對(duì)該理論的基本思想作一個(gè)簡(jiǎn)要的介紹。

PAC是一種基于樣本的概念學(xué)習(xí)（concept learning）理論。給定一個(gè)空間X∈R，待研究的概念空間C是該空間的子空間，C?X，我們通過(guò)學(xué)習(xí)算法得到的假設(shè)構(gòu)成的空間也是X的子空間，H?X，需要說(shuō)明的是，H與C可能相等也可能不等（往往是不相等的）。一般地，我們只關(guān)心概念空間中的某一個(gè)概念c，并希望通過(guò)有限數(shù)量的樣本來(lái)“盡可能近似地”學(xué)習(xí)到此概念，即在某種確定的度量下，學(xué)習(xí)算法輸出的假設(shè)h和c是足夠接近的。如果用泛化誤差ε來(lái)描述所得假設(shè)h與目標(biāo)概念c的差異是否“近似”，用置信水平δ來(lái)表征上述結(jié)果是否“盡可能”，我們稱(chēng)一個(gè)算法對(duì)概念空間C是PAC的當(dāng)且僅當(dāng)對(duì)于較小的ε，δ，對(duì)任意概念空間中的概念c和任意概率分布Pμ，滿(mǎn)足

我們稱(chēng)使得上述公式成立最小訓(xùn)練樣本數(shù)為樣本復(fù)雜度m0。換句話(huà)說(shuō)，當(dāng)算法的輸入樣本數(shù)大于m0時(shí)，算法可以在概率意義上完成對(duì)目標(biāo)概念足夠近似正確地學(xué)習(xí)［9］。

為了更直觀說(shuō)明PAC的基本思想，這里介紹一個(gè)經(jīng)典的例子［6］，如圖1所示。

Fig.1 Learning concept of“medium build”圖1 學(xué)習(xí)概念“中等身材”

解釋?zhuān)簩?duì)成年男子而言，認(rèn)為身高在1.63～1.83m之間，體重在68～84kg之間為中等身材，隨機(jī)選擇有限數(shù)量的樣本進(jìn)行訓(xùn)練，即輸入帶標(biāo)簽［＋，－］的樣本［體重，身高］進(jìn)行學(xué)習(xí)，得到的最優(yōu)假設(shè)是以正樣本為邊界點(diǎn)的最大矩形。

通過(guò)這個(gè)例子，可以容易地發(fā)現(xiàn)隨著訓(xùn)練樣本增多，代表最優(yōu)假設(shè)的矩形越有可能更好地逼近代表目標(biāo)概念的矩形。在給定δ下，若算法是PAC的，樣本數(shù)量（m）與逼近程度（泛化誤差）在假設(shè)空間的勢(shì)｜H｜有限時(shí)關(guān)系如下［9］：

式（2）說(shuō)明欲達(dá)到給定的泛化誤差與置信水平要求并且確保算法是PAC的，只需要保證假設(shè)空間的勢(shì)有限并且訓(xùn)練樣本數(shù)量大于樣本復(fù)雜度，該式中所得的下界與遺傳算法中的初始種群規(guī)模（population size）類(lèi)似，文獻(xiàn)［10］指出PAC理論得到的樣本復(fù)雜度可有效地用于指導(dǎo)遺傳算法選擇初始種群規(guī)模，說(shuō)明了樣本復(fù)雜度的實(shí)際應(yīng)用價(jià)值。

與式（2）等價(jià)的描述為：

式（3）說(shuō)明，PAC理論的最大優(yōu)點(diǎn)在于給定訓(xùn)練樣本數(shù)量，如果能夠證明算法是PAC的，則說(shuō)明算法的效果有一個(gè)不依賴(lài)于目標(biāo)概念（即目標(biāo)概念可以在概念空間隨機(jī)選擇）且不依賴(lài)于訓(xùn)練樣本分布與選擇方式的理論上界，Vapnik在文獻(xiàn)［11］中介紹了關(guān)于這個(gè)理論上界的更多內(nèi)容并且擴(kuò)展到對(duì)假設(shè)空間的勢(shì)｜H｜無(wú)限時(shí)算法PAC性質(zhì)的討論。

2 貝葉斯學(xué)習(xí)

Mitchell在文獻(xiàn)［12］中系統(tǒng)介紹了貝葉斯方法在機(jī)器學(xué)習(xí)中的理論與應(yīng)用，這里我們從一個(gè)二分問(wèn)題出發(fā)簡(jiǎn)要地對(duì)貝葉斯學(xué)習(xí)框架進(jìn)行介紹，主要考慮兩類(lèi)分類(lèi)器，貝葉斯最優(yōu)分類(lèi)器與吉布斯分類(lèi)器。

假定訓(xùn)練樣本集S＝｛（x1，y1），…，（xm，ym）｜xi∈X?Rn，yi∈Y＝｛－1，＋1｝｝?X×Y，在PAC學(xué)習(xí)模型假設(shè)下，每一個(gè)帶標(biāo)簽的樣本（xi，yi）依固定但未知的分布D從X×Y中隨機(jī)選擇。假設(shè)空間H中的每一個(gè)假設(shè)均可以看作一個(gè)分類(lèi)器，即h∶X→Y。從統(tǒng)計(jì)角度，對(duì)真實(shí)誤差和經(jīng)驗(yàn)誤差定義如下（這里統(tǒng)一采用文獻(xiàn)［13］中的符號(hào)記法）：

其中，I（a）為1若a為真，I（a）為0若a為假。

貝葉斯學(xué)習(xí)規(guī)則是根據(jù)訓(xùn)練樣本，確定假設(shè)空間中的假設(shè)（分類(lèi)器）h所服從的后驗(yàn)分布Q，而后根據(jù)此分布賦予每一個(gè)假設(shè)相應(yīng)的權(quán)重，最后以一個(gè)加權(quán)投票的方式得到分類(lèi)器BQ，即：

可見(jiàn)，貝葉斯學(xué)習(xí)的關(guān)鍵是假定假設(shè)空間的先驗(yàn)分布，利用觀測(cè)數(shù)據(jù)得到的似然，確定假設(shè)空間的后驗(yàn)分布，在對(duì)新來(lái)的樣本進(jìn)行分類(lèi)時(shí)依據(jù)得到的后驗(yàn)分布利用多個(gè)假設(shè)通過(guò)加權(quán)使得經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，這種學(xué)習(xí)算法得到的分類(lèi)器稱(chēng)為貝葉斯最優(yōu)分類(lèi)器，屬于加權(quán)投票算法的特例［14－15］，能夠從給定訓(xùn)練數(shù)據(jù)中獲得最好的性能［16］。

但是，由于貝葉斯最優(yōu)分類(lèi)器算法開(kāi)銷(xiāo)大并且可能得到不屬于假設(shè)空間中的假設(shè)，因此人們?cè)O(shè)計(jì)了另外一種常用的近似最優(yōu)分類(lèi)器來(lái)替代，即吉布斯分類(lèi)器。該分類(lèi)器在得到Q之后不采用加權(quán)處理，而是通過(guò)采樣的方式依概率分布Q隨機(jī)地選擇一個(gè)分類(lèi)器h。類(lèi)似地，可以定義吉布斯分類(lèi)器的真實(shí)誤差和經(jīng)驗(yàn)誤差：

理論上［17］已嚴(yán)格證明貝葉斯最優(yōu)分類(lèi)器的泛化誤差R（BQ）最多為吉布斯分類(lèi)器泛化誤差的2倍（這一點(diǎn)從二分問(wèn)題可以很直觀地得出），即：

依據(jù)此公式，研究者在分析貝葉斯最優(yōu)分類(lèi)器的泛化誤差上界時(shí)往往轉(zhuǎn)化為分析相應(yīng)的吉布斯分類(lèi)器的泛化誤差上界。

3 PAC－Bayesian理論

前面已經(jīng)論述了PAC的泛化誤差界在假設(shè)空間有限時(shí)很容易得出并且是一個(gè)較緊的界，現(xiàn)在考慮一種更為一般的情況，考慮概念空間是一個(gè)元素可數(shù)無(wú)窮多的集合，其VC維是無(wú)限的［15］，這時(shí)便無(wú)法直接使用一般的PAC理論來(lái)給出泛化誤差的界，而若采用VC維的理論，給出泛化誤差界太松。另一方面，傳統(tǒng)的貝葉斯方法對(duì)先驗(yàn)知識(shí)過(guò)于依賴(lài)，以至于先驗(yàn)分布不正確時(shí)，模型的泛化誤差難以控制?？梢?jiàn)傳統(tǒng)的PAC理論與貝葉斯學(xué)習(xí)有其固有的缺點(diǎn)。

從另一個(gè)角度，注意到PAC理論的優(yōu)勢(shì)在于給定置信水平與訓(xùn)練樣本數(shù)目（這里關(guān)注泛化誤差，換個(gè)角度可同樣關(guān)注樣本復(fù)雜度）之后，不依賴(lài)于模型的先驗(yàn)對(duì)錯(cuò)，也不依賴(lài)于由訓(xùn)練數(shù)據(jù)得到的后驗(yàn)分布，均能夠給出模型的泛化誤差界；貝葉斯學(xué)習(xí)的優(yōu)勢(shì)在于不同程度地利用領(lǐng)域知識(shí)作為先驗(yàn)（雖然承受先驗(yàn)可能不正確的風(fēng)險(xiǎn)），并且以先驗(yàn)和后驗(yàn)的概念來(lái)描述概念空間和假設(shè)空間的性質(zhì)，描述了一種統(tǒng)計(jì)意義的“平均”情況而不局限于分析假設(shè)空間的勢(shì)或者概念空間的VC維?？梢?jiàn)，PAC理論與貝葉斯學(xué)習(xí)是優(yōu)劣互補(bǔ)的，因此PAC－Bayesian理論的出發(fā)點(diǎn)與精髓之處在于考慮假設(shè)空間先驗(yàn)分布，但不限制該分布的正確性，給出模型一個(gè)泛化誤差上界。而后根據(jù)這個(gè)上界，可以進(jìn)行可學(xué)習(xí)性的證明，模型選擇與評(píng)價(jià)以及基于這個(gè)界進(jìn)行度量學(xué)習(xí)與相關(guān)優(yōu)化算法的改進(jìn)。

基于上述考慮，1997年Shawe－Taylor首次將PAC理論用于貝葉斯學(xué)習(xí)［17］，形成了最早的PAC－Bayesian思想。1998年，McAllester在計(jì)算學(xué)習(xí)領(lǐng)域著名會(huì)議COLT發(fā)文，正式以定理的形式提出PAC－Bayesian學(xué)習(xí)理論［18］，此后他對(duì)提出的PAC－Bayesian泛化誤差界進(jìn)行了改善，開(kāi)始嘗試應(yīng)用于隨機(jī)模型選擇和模型均化［19－20］，后續(xù)也有學(xué)者Seeger［21］，Langford［22］，Catoni［23］陸續(xù)提出更緊的界。在2009年，Germain以定理形式推導(dǎo)出一個(gè)最為一般的PAC－Bayesian泛化誤差界，證明了前人各種形式的界均可以作為此定理的推論［13］。此后在PAC－Bayesian理論研究層面基本沒(méi)有重大的實(shí)質(zhì)性進(jìn)展。近年來(lái)在理論層面的研究主要集中于對(duì)某些情況下更緊邊界的分析和推導(dǎo)等［25－26］。另一方面，該理論在應(yīng)用層面不止局限于最初提到的模型選擇、線(xiàn)性分類(lèi)器、SVM等方向，而越來(lái)越多地出現(xiàn)于各類(lèi)機(jī)器學(xué)習(xí)領(lǐng)域，如領(lǐng)域適應(yīng)［27－28］與直推學(xué)習(xí)［29－30］等，詳見(jiàn)文獻(xiàn)［4］，本文在這一點(diǎn)上不再贅述。

這里為了方便理解前面提到的PAC－Bayesian理論本質(zhì)，介紹最早的和最一般的PAC定理。

（McAllester（1998）定理1）若由概念空間C中的概念c得到的樣本服從任意分布D，對(duì)任意先驗(yàn)分布為P的假設(shè)空間H，任意給定概念空間和樣本空間的測(cè)度，對(duì)任意δ∈（0，1］，對(duì)任意假設(shè)空間的H的子空間U，有：

其中錯(cuò)誤率ε（U）＝Ec∈Uε（c）實(shí)質(zhì)上就是學(xué)習(xí)到的后驗(yàn)分布為Q的假設(shè)（子）空間的泛化誤差。同時(shí)，通過(guò)這個(gè)定理，結(jié)合貝葉斯學(xué)習(xí)規(guī)則，可以發(fā)現(xiàn)這個(gè)泛化誤差界同時(shí)體現(xiàn)出先驗(yàn)分布P的影響，進(jìn)而可以通過(guò)優(yōu)化先驗(yàn)分布來(lái)使得該泛化誤差界更緊，即獲得更小的分類(lèi)誤差。研究表明［24］，相比于其他理論，PAC－Bayesian學(xué)習(xí)理論得到的泛化誤差界更緊，因此在式（10）基礎(chǔ)上對(duì)界做進(jìn)一步優(yōu)化成了后續(xù)研究熱點(diǎn)。

（Germain（2009）定理2.1）若由概念空間C中的概念c得到的樣本服從任意分布D，對(duì)任意先驗(yàn)分布為P 的假設(shè)空間H，對(duì)任意δ∈（0，1］以及任意凸函數(shù)Ψ：［0，1］×［0，1］→R，有：

這個(gè)定理對(duì)之前研究者得到的PAC－Bayesian泛化誤差界的高度概括之處體現(xiàn)在用一個(gè)凸函數(shù)來(lái)表示一切形式的“誤差”，當(dāng)該函數(shù)取不同形式時(shí)，可以得到不同的界，因此PAC－Bayesian與傳統(tǒng)機(jī)器學(xué)習(xí)或優(yōu)化算法結(jié)合的核心思路就是選擇特定的凸函數(shù)Ψ并對(duì)式（11）得到的泛化誤差界進(jìn)行優(yōu)化。

4 大數(shù)據(jù)與PAC－Bayesian

傳統(tǒng)的PAC理論雖然旨在描述概念空間是否可學(xué)習(xí)，但在諸多實(shí)際問(wèn)題中的應(yīng)用碰到了種種困難，至少有兩方面的原因，一方面是之前已提到的假設(shè)空間的勢(shì)為無(wú)限的情況，不易直接應(yīng)用PAC理論；另一方面是與PAC有關(guān)的各種理論（包括PAC－Bayesian）表明在實(shí)際問(wèn)題中，若欲將算法的泛化誤差控制在一個(gè)較低的水平則得到的樣本復(fù)雜度往往特別大（如文獻(xiàn)［24］中，106量級(jí)），導(dǎo)致難以進(jìn)行實(shí)驗(yàn)驗(yàn)證。但是在大數(shù)據(jù)的時(shí)代，樣本數(shù)量已不是問(wèn)題，PAC理論的局限性在一定意義上有所減弱，另外PAC－Bayesian學(xué)習(xí)理論的深入發(fā)展進(jìn)一步給可學(xué)習(xí)理論帶來(lái)了新的血液。大數(shù)據(jù)的4V特性（體量大（volume）、異構(gòu)（variety）、低價(jià)值密度（value）、實(shí)時(shí)（velocity））［31］決定了大數(shù)據(jù)時(shí)代的機(jī)器學(xué)習(xí)問(wèn)題與傳統(tǒng)的機(jī)器學(xué)習(xí)問(wèn)題有很大不同，給相關(guān)研究工作帶來(lái)新的挑戰(zhàn)。在這樣的環(huán)境下，待求解的問(wèn)題所對(duì)應(yīng)的樣本復(fù)雜度容易被滿(mǎn)足，使得判斷問(wèn)題的可學(xué)習(xí)性成為可能，在海量的問(wèn)題中，一旦被判斷為不可學(xué)習(xí)便可節(jié)約大量的后續(xù)工作。另外，在問(wèn)題的求解過(guò)程中為了提升性能、降低訓(xùn)練時(shí)間，往往會(huì)不同程度地利用先驗(yàn)知識(shí)，但是由于大數(shù)據(jù)下的問(wèn)題的復(fù)雜性，人們?cè)谠O(shè)計(jì)算法時(shí)希望考慮領(lǐng)域先驗(yàn)知識(shí)但同時(shí)面臨所采用的先驗(yàn)知識(shí)可能不正確的風(fēng)險(xiǎn)。而PAC－Bayesian學(xué)習(xí)理論可以很好地解決這個(gè)問(wèn)題。因此，PAC－Bayesian學(xué)習(xí)理論非常適合于大數(shù)據(jù)相關(guān)的理論分析，有著無(wú)限的應(yīng)用潛力。

在已提出的PAC－Bayesian應(yīng)用中，已有相當(dāng)一部分適合于大數(shù)據(jù)環(huán)境的算法。例如Amini等在文獻(xiàn)［32］中對(duì)提出的半監(jiān)督學(xué)習(xí)算法給出PAC－Bayesian界，通過(guò)對(duì)只有少部分帶標(biāo)簽的訓(xùn)練樣本進(jìn)行估計(jì)來(lái)得到風(fēng)險(xiǎn)邊界，其算法可有效處理價(jià)值密度低的大規(guī)模數(shù)據(jù)；Germain等在文獻(xiàn)［33］中提出一種基于PACBayesian泛化誤差界的樣本壓縮方法，以先驗(yàn)分布和后驗(yàn)分布的KL散度為度量，旨在選擇出有代表性的樣本形成原樣本空間的一個(gè)子集，適合于處理具有體量大特點(diǎn)的大數(shù)據(jù)；Morvant等在文獻(xiàn)［34］中結(jié)合PACBayesian理論提出MinCq算法用于多媒體信息融合，雖然本質(zhì)上仍采用投票的思想，但充分利用了投票的多樣性，使其可用于處理異構(gòu)數(shù)據(jù)；Keshet等在文獻(xiàn)［35］中首次采用隨機(jī)梯度下降即在線(xiàn)學(xué)習(xí)的方法來(lái)解PAC－Bayesian邊界的優(yōu)化問(wèn)題，進(jìn)而用于處理語(yǔ)音信號(hào)中的音素識(shí)別問(wèn)題，表明該方法可用于處理實(shí)時(shí)數(shù)據(jù)。如Gheyas等在文獻(xiàn)［36］中所說(shuō)，算法結(jié)合能夠較好彌補(bǔ)算法相互間的不足，由于大數(shù)據(jù)具有眾多難解的特性，基于PAC－Bayesian理論的多方法融合必將是未來(lái)的趨勢(shì)。

此外，值得注意的是，現(xiàn)有的適合于處理大數(shù)據(jù)問(wèn)題的算法中，還有大量的熱門(mén)算法沒(méi)有相應(yīng)的PACBayesian分析，如采用概率圖模型［37］用于語(yǔ)音識(shí)別與社交網(wǎng)絡(luò)分析，基于隨機(jī)森林的Co－forest［38］用于輔助診斷中的分類(lèi)問(wèn)題等等，這類(lèi)算法的共性是均要考慮先驗(yàn)知識(shí)，并且尚未得到相應(yīng)的PAC－Bayesian泛化誤差界，因此算法泛化性能的提升空間還很大，這預(yù)示著PAC－Bayesian學(xué)習(xí)理論在未來(lái)的大數(shù)據(jù)環(huán)境下仍需進(jìn)一步深入研究。

5 結(jié)束語(yǔ)

本文立足于PAC可學(xué)習(xí)理論的基本思想，結(jié)合貝葉斯學(xué)習(xí)的理論框架，分析了PAC－Bayesian學(xué)習(xí)理論的由來(lái)以及本質(zhì)內(nèi)涵，通過(guò)其最初與最一般的定理揭示了該理論如何將PAC與貝葉斯結(jié)合起來(lái)達(dá)到更易應(yīng)用于相關(guān)算法分析的效果。在大數(shù)據(jù)的時(shí)代，PAC－Bayesian學(xué)習(xí)理論已經(jīng)初步展現(xiàn)出大數(shù)據(jù)算法分析的優(yōu)勢(shì)并有可能在未來(lái)的研究中在理論與應(yīng)用層面均得到進(jìn)一步的推進(jìn)。此外，并行計(jì)算用于大數(shù)據(jù)處理已引起學(xué)術(shù)界和產(chǎn)業(yè)界越來(lái)越多的關(guān)注，探討PAC－Bayesian理論在各類(lèi)并行算法上的應(yīng)用也是一個(gè)非常有意義的研究方向。

［1］Kearns M J，Vazirani U V.An Introduction to Computational Learning Theory［M］.Cambridge.MA：MIT press，1994.

［2］Tang Li，Yu Hua，Gong Xiujun，et al.On the PAC－Bayes Bound Calculation Based on Reproducing Kernel Hilbert Space［J］.Applied Mathematics and Information Sciences，2013，7（2）：817－822.

［3］Tang Li，Zhao Zheng，Gong Xiujun.A Refined MCMC Sampling from RKHS for PAC－Bayes Bound Calculation［J］.Journal of Computers，2014，9（4）：930－937.

［4］湯莉，宮秀軍，何麗.PAC－Bayes理論及應(yīng)用研究綜述［J］.計(jì)算機(jī)科學(xué)與探索，2015，9（1）：1－13.

［5］Valiant L G.A Theory of the Learnable［J］.Communications of the ACM，1984，27（11）：1134－1142.

［6］Blumer A，Ehrenfeucht A，Haussler D，et al.Learnability and the Vapnik－Chervonenkis Dimension［J］.Journal of the ACM （JACM），1989，36（4）：929－965.

［7］Pestov V.PAC Learnability Versus VC Dimension：a footnote to a basic result of statistical learning［C］∥Neural Networks（IJCNN），The 2011International Joint Conference on.IEEE，2011：1141－1145.

［8］Wesley Calvert.PAC Learning，VC Dimension，and the Arithmetic Hierarchy［Z／OL］.ArXiv Preprint ArXiv：1406.1111，2014.

［9］Anthony M，Biggs N.Computational Learning Theory for Artificial Neural Networks［J］.North－Holland Mathematical Library，1993，51：25－62.

［10］Hernández－Aguirre A，Buckles B P，Martánez－Alcántara A.The Probably Approximately Correct（PAC）Population Size of a Genetic Algorithm［C］∥Tools with Artificial Intelligence，2000.ICTAI 2000∥Proceedings of 12th IEEE International Conference on.IEEE，2000：199－202.

［11］Vapnik V N，Vapnik V.Statistical Learning Theory［M］.New York：Wiley，1998.

［12］Anderson J R.Machine Learning：An artificial intelligence approach［M］.Morgan Kaufmann，1986.

［13］Germain P，Lacasse A，Laviolette F，et al.PAC－Bayesian Learning of Linear Classifiers［C］∥Proceedings of the 26th Annual International Conference on Machine Learning.ACM，2009：353－360.

［14］Shawe－Taylor J，Langford J.PAC－Bayes ＆ Margins［J］.Advances in Neural Information Processing Systems，2003，15：439.

［15］Linial N，Mansour Y，Rivest R L.Results on Learnability and the Vapnik－Chervonenkis Dimension［J］.Information and Computation，1991，90（1）：33－49.

［16］Zoubin Ghahramani.Probabilistic Machine Learning and Artificial Intelligence［J］.Nature，2015，521：452－459.

［17］Shawe－Taylor J，Williamson R C.A PAC Analysis of a Bayesian Estimator［C］∥Proceedings of the tenth annual conference on Computational learning theory.ACM，1997：2－9.

［18］McAllester D A.Some Pac－bayesian Theorems［C］∥Proceedings of the Eleventh Annual Conference on Computational Learning theory.ACM，1998：230－234.

［19］McAllester D A.PAC－Bayesian Model Averaging［C］∥Proceedings of the Twelfth Annual Conference on Computational Learning theory.ACM，1999：164－170.

［20］McAllester D A.PAC－Bayesian Stochastic Model Selection［J］.Machine Learning，2003，51（1）：5－21.

［21］Seeger M.Pac－bayesian Generalisation Error Bounds for Gaussian Process Classification［J］.The Journal of Machine Learning Research，2003，3：233－269.

［22］Langford J.Tutorial on Practical Prediction Theory for Classification［J］.Journal of Machine Learning Research，2005，6（3）：273－306.

［23］Catoni O.PAC－Bayesian Supervised Classification：the Thermodynamics of Statistical Learning［Z／OL］.ArXiv preprint ArXiv：0712.0248，2007.

［24］Herbrich R，Graepel T.A PAC－Bayesian Margin Bound for Linear Classifiers［J］.Information Theory，IEEE Transactions on，2002，48（12）：3140－3150.

［25］Lever G，Laviolette F，Shawe－Taylor J.Tighter PAC－Bayes Bounds Through Distribution－dependent Priors［J］.Theoretical Computer Science，2013，473：4－28.

［26］Honorio J，Jaakkola T.Tight Bounds for the Expected Risk of Linear Classifiers and PAC－Bayes Finite－Sample Guarantees［C］∥Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics，2014：384－392.

［27］Pascal Germain，Amaury Habrard，et al.A PAC－Bayesian Approach for Domain Adaptation with Specialization to Linear Classifiers［C］∥Proceedings of the 30th International Conference on Machine Learning（ICML－13）.2013：738－746.

［28］Germain P，Habrard A，Laviolette F，et al.An Improvement to the Domain Adaptation Bound in a PAC－Bayesian context［Z／OL］.ArXiv Preprint ArXiv：1501.03002，2015.

［29］Bégin L，Germain P，Laviolette F，et al.PAC－Bayesian Theory for Transductive Learning［C］∥Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics.2014：105－113.

［30］Balsubramani A，F(xiàn)reund Y.PAC－Bayes with Minimax for Confidence－Rated Transduction［Z／OL］.ArXiv Preprint ArXiv：1501.03838，2015.

［31］陳康，向勇，喻超.大數(shù)據(jù)時(shí)代機(jī)器學(xué)習(xí)的新趨勢(shì)［J］.電信科學(xué)，2013，28（12）：88－95.

［32］Amini M，Usunier N，Laviolette F.A Transductive Bound for the Voted Classifier with an Application to Semi－supervised Learning［C］∥Advances in Neural Information Processing Systems，2009：65－72.

［33］Germain P，Lacoste A，Marchand M，et al.A PAC－Bayes Sample－compression Approach to Kernel Methods［C］∥Proceedings of the 28th International Conference on Machine Learning（ICML－11）.2011：297－304.

［34］Morvant E，Habrard A，Ayache S.PAC－Bayesian Majority Vote for Late Classifier Fusion［Z／OL］.ArXiv Preprint ArXiv：1207.1019，2012.

［35］Keshet J，McAllester D，Hazan T.Pac－bayesian Approach for Minimization of Phoneme Error Rate［C］∥Acoustics，Speech and Signal Processing（ICASSP），2011IEEE International Conference on.IEEE，2011：2224－2227.

［36］Gheyas I A，Smith L S.Feature Subset Selection in Large Dimensionality Domains［J］.Pattern Recognition，2010，43（1）：5－13.

［37］Koller D，F(xiàn)riedman N.Probabilistic Graphical Models：Principles and Techniques［M］.Cambridge，MA：MIT Press，2009.

［38］Li M，Zhou Z H.Improve Computer－aided Diagnosis with Machine Learning Techniques Using Undiagnosed Samples［J］.Systems，Man and Cybernetics，Part A：Systems and Humans，IEEE Transactions on，2007，37（6）：1088－1098.