劉妙妙，趙聯(lián)文，宋海龍，姜 英

（西南交通大學(xué)數(shù)學(xué)學(xué)院，四川成都 610031）

基于Bayes分類的PAC-Bayesian定理證明＊

劉妙妙，趙聯(lián)文，宋海龍，姜 英

（西南交通大學(xué)數(shù)學(xué)學(xué)院，四川成都 610031）

采用類似基于Gibbs分類的PAC-Bayesian定理的證明方法，證明基于Bayes分類的PAC-Bayesian定理.對(duì)于PAC-Bayesian定理的證明采用Bayes分類，可以方便有效地運(yùn)用到統(tǒng)計(jì)問(wèn)題中來(lái)解決相關(guān)問(wèn)題.

Bayesian方法；Bayes分類；PAC-Bayesian

統(tǒng)計(jì)學(xué)習(xí)理論以概率理論作為基礎(chǔ)，以訓(xùn)練樣本形成統(tǒng)計(jì)模型，以檢驗(yàn)樣本評(píng)價(jià)統(tǒng)計(jì)模型的優(yōu)劣，并用于預(yù)測(cè).PAC（Probabaly approximately correct，概率近似正確）學(xué)習(xí)模型［1］其實(shí)質(zhì)是以樣本訓(xùn)練為基礎(chǔ)，使得到的統(tǒng)計(jì)模型以高概率逼近真實(shí)的目標(biāo).最早在1984年，Valiant L G［2］首先提出PAC學(xué)習(xí)模型，近20年來(lái)才開(kāi)始將PAC與Bayesian結(jié)合起來(lái)對(duì)其進(jìn)行充分的研究.

PAC-Bayesian界（McAllester，2003；seeger，2002；Langford，2005；Catoni，2007）似乎是胎緊的.2006年，Arindam Banerjee［3］給出一些關(guān)于Bayesian［4］的重要界限，其中包括PAC-Bayesian界限.2011年，Of er Dekel［5］對(duì)PAC-Bayesian界限作了進(jìn)一步分析，并給出一些有關(guān)KL信息量的推論.2012年，Taiji Suzuki［6］又將高斯過(guò)程回歸應(yīng)用到PAC-Bayesian界，對(duì)于模型的選擇［7］起到很重要的作用.

PAC模型可解決信息分類問(wèn)題，比如判斷一個(gè)病人是否患有心臟病.為解決信息分類問(wèn)題［8］，學(xué)習(xí)算法會(huì)根據(jù)過(guò)去的經(jīng)驗(yàn)而給出一個(gè)概率假設(shè)，并將此概率假設(shè)作為判斷依據(jù).然而，這種根據(jù)過(guò)去經(jīng)驗(yàn)的泛化也可能不適合于將來(lái).PAC模型可最大限度地降低泛化帶來(lái)的錯(cuò)誤，其實(shí)質(zhì)是以樣本訓(xùn)練為基礎(chǔ)，使算法的輸出以概率接近未知的目標(biāo)概念.此模型被用于機(jī)器學(xué)習(xí)、人工智能、統(tǒng)計(jì)學(xué)習(xí)和其他計(jì)算領(lǐng)域.

對(duì)于分類器的問(wèn)題，一般給一個(gè)例子的訓(xùn)練集——按照某個(gè)相同的未知的分布D，并且目的是找一個(gè)分類使得真實(shí)風(fēng)險(xiǎn)最?。ɑ蛘呤瞧谕麚p失）.因?yàn)檎鎸?shí)風(fēng)險(xiǎn)被定義僅僅依賴于未知分布D，其分布是未知的，故不能確切地求出真實(shí)風(fēng)險(xiǎn)，只能給出大概的界限，所以涉及到優(yōu)化風(fēng)險(xiǎn)問(wèn)題.問(wèn)題在于怎么樣找一個(gè)分類來(lái)優(yōu)化，使得所研究的訓(xùn)練數(shù)據(jù)有一個(gè)盡可能最小的真實(shí)風(fēng)險(xiǎn).

以往PAC-Bayesian定理都是基于Gibbs分類器［9］的證明.Seeger認(rèn)為Bayes分類比Gibbs分類更簡(jiǎn)單，計(jì)算和決定更有效，更能經(jīng)常被運(yùn)用到實(shí)際問(wèn)題中.

主要考慮基于Bayes分類的PAC-Bayesian定理的證明，以便有效運(yùn)用到統(tǒng)計(jì)問(wèn)題中.在此，最簡(jiǎn)單地來(lái)講，Bayes分類是利用貝葉斯變換公式的分類算法.

1 關(guān)于PAC-Bayesian定理的簡(jiǎn)單知識(shí)點(diǎn)

1.1 PAC模型

X為輸入空間，Y為輸出空間，X＝｛x1，x2，...，xm｝，Y＝｛y1，y2，...，yn｝，Y＝f（x），Θ為所有可能的假設(shè)空間.在Θ中選取可行的f去估計(jì)Y，在假設(shè)空間Θ中的任何一個(gè)假設(shè)h為了描述輸出的假設(shè)h對(duì)真實(shí)函數(shù)Y的逼近程度，進(jìn)而引入了假設(shè)h對(duì)于Y和實(shí)例分布D的真實(shí)錯(cuò)誤率，error（h）＝PD（h（X）≠Y）.給定任意的實(shí)數(shù)ε，δ滿足0＜ε＜1以及0＜δ＜1，有PH（PD（h（X）≠Y）≤ε）≥1－δ，此時(shí)叫作PAC可學(xué)習(xí)［1］.

PAC模型中重要的2個(gè)參數(shù)是ε和δ.ε用來(lái)限制模型的誤差，由于隨機(jī)性的存在，想要保證學(xué)到好模型的概率很大，而這由參數(shù)δ來(lái)控制，1－δ構(gòu)造了算法的置信度，δ越小說(shuō)明h（x）越逼近y.

1.2 損失函數(shù)

已知輸出空間Y，稱函數(shù)l：Y×Y→R＋為在輸出空間Y上的損失函數(shù)［10］，l（h（x），y）代表當(dāng)參數(shù)為y∈Y時(shí)采取假設(shè)h（x）所造成的損失，損失函數(shù)可以看作是學(xué)習(xí)者為了降低損失所采取的假設(shè).

在PAC學(xué)習(xí)中為了逼近y在假設(shè)空間找到的假設(shè)h（x）一定有一個(gè)損失，這里在損失函數(shù)上定一個(gè)標(biāo)準(zhǔn)，進(jìn)而在此標(biāo)準(zhǔn)上來(lái)定義真實(shí)風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn).文中這個(gè)標(biāo)準(zhǔn)定義為0－1損失函數(shù).

1.3 Bayes分類

已知一個(gè)有限維輸入空間X和輸出空間Y，在X×Y上的未知分布D和假設(shè)空間Θ以及0－1損失函數(shù)，在假設(shè)空間Θ上找一個(gè)能使真實(shí)風(fēng)險(xiǎn)最小的假設(shè)h＊（x），叫作Bayes分類［11］，h＊（x）＝s gn Eh～Qy（x）.

1.4 真實(shí)風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn)

經(jīng)驗(yàn)風(fēng)險(xiǎn)被定義為h的訓(xùn)練錯(cuò)誤的頻率，其中l(wèi)為損失函數(shù)，當(dāng)h（xi）＝y(tǒng)i時(shí)，l＝0，當(dāng)h（xi）≠yi時(shí)，l＝1.當(dāng)α為真時(shí)，I（α）＝1，反之為0.

h（xi）和yi的關(guān)系如圖1所示.

由于在實(shí)際分類問(wèn)題中所給數(shù)據(jù)的分布不知道，因此不能直接估計(jì)真實(shí)風(fēng)險(xiǎn)，只能根據(jù)大數(shù)定律思想用算術(shù)平均值代替數(shù)學(xué)期望，即用經(jīng)驗(yàn)風(fēng)險(xiǎn)來(lái)估計(jì)真實(shí)風(fēng)險(xiǎn)，盡可能地在訓(xùn)練數(shù)據(jù)上優(yōu)化，找一個(gè)分類使真實(shí)風(fēng)險(xiǎn)最小.

基于Gibbs分類的真實(shí)風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn)為

基于Bayes分類的真實(shí)風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn)為

圖1 h（xi）和yi的關(guān)系

2 PAC-Bayesian定理及證明

筆者主要介紹基于Bayes分類的PAC-Bayesian定理證明.下面首先介紹基于Bayes分類的PAC-Bayesian定理，進(jìn)而來(lái)證明基于Bayes分類的PAC-Bayesian界，以便在計(jì)算機(jī)學(xué)習(xí)領(lǐng)域和統(tǒng)計(jì)學(xué)習(xí)理論中更廣泛地應(yīng)用.

定理1 對(duì)任何分布D和任何分類集合H，以及支撐集合H上的先驗(yàn)分布，對(duì)?δ∈（0，1）和凸函數(shù)DBer：［0，1］×［0，1］→R＋，有［13］

其中K［q］＝－qlog q－（1－q）log（1－q）是一個(gè)q-Bernoulli變量的熵.因此，

由此可得基于Bayes分類的PAC-Bayesian定理證明，可見(jiàn)其基于Bayes分類的PAC-Bayesian界和基于Gibbs分類的PAC-Bayesian界幾乎一樣，只是Bayes分類運(yùn)用更廣.

［1］ 張鴻賓.計(jì)算機(jī)學(xué)習(xí)理論及其應(yīng)用［J］.計(jì)算機(jī)科學(xué)，1999，10（3）：18－20.

［2］ VALIANT L G.A Theory of the Learnable［J］.CACM，1984，27（11）：1 134－1 142.

［3］ ARINDAM BANERJEE.On Bayesian Bounds［C］.Pittsburgh，PA：Proceedings of the 23rdInternational Conference on Machine Learning，2006：30－32.

［4］ JAYANTA K GHOSH，MOHAN DELAMPADY，TAPAS SAMANTA.An Introduction to Bayesian Analysis：Theory and Methods［M］.Springer，2006：28－59.

［5］ OFER DEKEL.PAC-Bayesian Analysis［J］.Learning Theory Lecture，2011（14）：1－4.

［6］ TAIJI SUZUKI.PAC-Bayesian Bound for Gaussian Process Regression and Multiple Kernel Additive Model［J］.25thAnnual Conference on Learning Theory，Workshop and Conference Proceedings，2012，23（8）：1－20.

［7］ MAHDI MILANNI FARD，JOELLE PINEAU.PAC-Bayesian Model Selection for Reinforcement Learning［M］.Cambridge：An Introduction MIT Press，1998：1－8.

［8］ TREVOR HASTIE，ROBERT TIBSHIRANI，JEROME FRIEDMAN.The Elements of Statistical Learning［M］.Stanford，California：Springers Series in Statistics，2008：1－18.

［9］ PETER D HOFF.A First Course in Bayesian Statistical Methods［M］.Stanford，California：Springers Series in Statistics，2008：89－104.

［10］ TREVOR HASTIE，ROBERT TIBSHIRANI，JEROME FRIEDMAN.The Elements of Statistical Learning［M］.Stanford，California：Springers Series in Statistics，2008：18－19.

［11］ VORGELEGT VON DIPLOM-PHYSIKER.PAC-Bayesian Pattern Classification with Kernels［M］.Berlin：Tag der Wissenschaftlichen Aussprache，2002：7－12.

［12］ PASCAL GERMAIN，ALEXANDRE LACASSE，F(xiàn)RANCOIS LAVIOLETTE.PAC-Bayesian Learning of Linear Classifiers［C］.Montreal：Canada：Appearing in Proceedings of the 26thInternational Conference on Machine Learning，2009：1－4.

［13］ MATTHIAS SEEGER.PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification［J］.Journal of Machine Learning Research，2002（3）：233－269.

（責(zé)任編輯 向陽(yáng)潔）

Proof of PAC-Bayesian Theorem Based on Bayes Classifier

LIU Miao-miao，ZHAO Lian-wen，SONG Hai-long，JIANG Ying
（College of Mathematics，Southwest Jiaotong University，Chengdu 610031，China）

Method of proving PAC-bayesian theorem based on Gibbs classification is used to the proof based on Bayes classification.Through the Bayes classification，the theorem can be applied to the statistical problems conveniently and effectively to solve related problems.

Bayesian method；Bayes classifier；PAC-Bayesian

O212.8

A

10.3969／j.issn.1007－2985.2013.06.006

1007－2985（2013）06－0019－03

2013－04－10

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助（SWJTU11CX155）

劉妙妙（1988－），女，山西朔州人，西南交通大學(xué)數(shù)學(xué)學(xué)院碩士研究生，主要從事統(tǒng)計(jì)與應(yīng)用研究；趙聯(lián)文（1964－），男，四川巴中人，西南交通大學(xué)數(shù)學(xué)學(xué)院教授，碩士研究生導(dǎo)師，主要從事隨機(jī)過(guò)程、貝葉斯分析和概率極限理論研究.