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

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

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

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

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

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

采用類似基于Gibbs分類的PAC-Bayesian定理的證明方法，證明基于Bayes分類的PAC-Bayesian定理.對于PAC-Bayesian定理的證明采用Bayes分類，可以方便有效地運用到統(tǒng)計問題中來解決相關問題.

Bayesian方法；Bayes分類；PAC-Bayesian

統(tǒng)計學習理論以概率理論作為基礎，以訓練樣本形成統(tǒng)計模型，以檢驗樣本評價統(tǒng)計模型的優(yōu)劣，并用于預測.PAC（Probabaly approximately correct，概率近似正確）學習模型［1］其實質是以樣本訓練為基礎，使得到的統(tǒng)計模型以高概率逼近真實的目標.最早在1984年，Valiant L G［2］首先提出PAC學習模型，近20年來才開始將PAC與Bayesian結合起來對其進行充分的研究.

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

PAC模型可解決信息分類問題，比如判斷一個病人是否患有心臟病.為解決信息分類問題［8］，學習算法會根據過去的經驗而給出一個概率假設，并將此概率假設作為判斷依據.然而，這種根據過去經驗的泛化也可能不適合于將來.PAC模型可最大限度地降低泛化帶來的錯誤，其實質是以樣本訓練為基礎，使算法的輸出以概率接近未知的目標概念.此模型被用于機器學習、人工智能、統(tǒng)計學習和其他計算領域.

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

以往PAC-Bayesian定理都是基于Gibbs分類器［9］的證明.Seeger認為Bayes分類比Gibbs分類更簡單，計算和決定更有效，更能經常被運用到實際問題中.

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

1 關于PAC-Bayesian定理的簡單知識點

1.1 PAC模型

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

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

1.2 損失函數(shù)

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

在PAC學習中為了逼近y在假設空間找到的假設h（x）一定有一個損失，這里在損失函數(shù)上定一個標準，進而在此標準上來定義真實風險和經驗風險.文中這個標準定義為0－1損失函數(shù).

1.3 Bayes分類

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

1.4 真實風險和經驗風險

經驗風險被定義為h的訓練錯誤的頻率，其中l(wèi)為損失函數(shù)，當h（xi）＝y(tǒng)i時，l＝0，當h（xi）≠yi時，l＝1.當α為真時，I（α）＝1，反之為0.

h（xi）和yi的關系如圖1所示.

由于在實際分類問題中所給數(shù)據的分布不知道，因此不能直接估計真實風險，只能根據大數(shù)定律思想用算術平均值代替數(shù)學期望，即用經驗風險來估計真實風險，盡可能地在訓練數(shù)據上優(yōu)化，找一個分類使真實風險最小.

基于Gibbs分類的真實風險和經驗風險為

基于Bayes分類的真實風險和經驗風險為

圖1 h（xi）和yi的關系

2 PAC-Bayesian定理及證明

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

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

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

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

［1］ 張鴻賓.計算機學習理論及其應用［J］.計算機科學，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.

（責任編輯 向陽潔）

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

中央高校基本科研業(yè)務費專項資金資助（SWJTU11CX155）

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