基于Bayes分类的PAC-Bayesian定理证明＊

刘妙妙，赵联文，宋海龙，姜 英

（西南交通大学数学学院，四川成都 610031）

基于Bayes分类的PAC-Bayesian定理证明＊

刘妙妙，赵联文，宋海龙，姜 英

（西南交通大学数学学院，四川成都 610031）

采用类似基于Gibbs分类的PAC-Bayesian定理的证明方法，证明基于Bayes分类的PAC-Bayesian定理.对于PAC-Bayesian定理的证明采用Bayes分类，可以方便有效地运用到统计问题中来解决相关问题.

Bayesian方法；Bayes分类；PAC-Bayesian

统计学习理论以概率理论作为基础，以训练样本形成统计模型，以检验样本评价统计模型的优劣，并用于预测.PAC（Probabaly approximately correct，概率近似正确）学习模型［1］其实质是以样本训练为基础，使得到的统计模型以高概率逼近真实的目标.最早在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模型可最大限度地降低泛化带来的错误，其实质是以样本训练为基础，使算法的输出以概率接近未知的目标概念.此模型被用于机器学习、人工智能、统计学习和其他计算领域.

对于分类器的问题，一般给一个例子的训练集——按照某个相同的未知的分布D，并且目的是找一个分类使得真实风险最小（或者是期望损失）.因为真实风险被定义仅仅依赖于未知分布D，其分布是未知的，故不能确切地求出真实风险，只能给出大概的界限，所以涉及到优化风险问题.问题在于怎么样找一个分类来优化，使得所研究的训练数据有一个尽可能最小的真实风险.

以往PAC-Bayesian定理都是基于Gibbs分类器［9］的证明.Seeger认为Bayes分类比Gibbs分类更简单，计算和决定更有效，更能经常被运用到实际问题中.

主要考虑基于Bayes分类的PAC-Bayesian定理的证明，以便有效运用到统计问题中.在此，最简单地来讲，Bayes分类是利用贝叶斯变换公式的分类算法.

1 关于PAC-Bayesian定理的简单知识点

1.1 PAC模型

X为输入空间，Y为输出空间，X＝｛x1，x2，...，xm｝，Y＝｛y1，y2，...，yn｝，Y＝f（x），Θ为所有可能的假设空间.在Θ中选取可行的f去估计Y，在假设空间Θ中的任何一个假设h为了描述输出的假设h对真实函数Y的逼近程度，进而引入了假设h对于Y和实例分布D的真实错误率，error（h）＝PD（h（X）≠Y）.给定任意的实数ε，δ满足0＜ε＜1以及0＜δ＜1，有PH（PD（h（X）≠Y）≤ε）≥1－δ，此时叫作PAC可学习［1］.

PAC模型中重要的2个参数是ε和δ.ε用来限制模型的误差，由于随机性的存在，想要保证学到好模型的概率很大，而这由参数δ来控制，1－δ构造了算法的置信度，δ越小说明h（x）越逼近y.

1.2 损失函数

已知输出空间Y，称函数l：Y×Y→R＋为在输出空间Y上的损失函数［10］，l（h（x），y）代表当参数为y∈Y时采取假设h（x）所造成的损失，损失函数可以看作是学习者为了降低损失所采取的假设.

在PAC学习中为了逼近y在假设空间找到的假设h（x）一定有一个损失，这里在损失函数上定一个标准，进而在此标准上来定义真实风险和经验风险.文中这个标准定义为0－1损失函数.

1.3 Bayes分类

已知一个有限维输入空间X和输出空间Y，在X×Y上的未知分布D和假设空间Θ以及0－1损失函数，在假设空间Θ上找一个能使真实风险最小的假设h＊（x），叫作Bayes分类［11］，h＊（x）＝s gn Eh～Qy（x）.

1.4 真实风险和经验风险

经验风险被定义为h的训练错误的频率，其中l为损失函数，当h（xi）＝yi时，l＝0，当h（xi）≠yi时，l＝1.当α为真时，I（α）＝1，反之为0.

h（xi）和yi的关系如图1所示.

由于在实际分类问题中所给数据的分布不知道，因此不能直接估计真实风险，只能根据大数定律思想用算术平均值代替数学期望，即用经验风险来估计真实风险，尽可能地在训练数据上优化，找一个分类使真实风险最小.

基于Gibbs分类的真实风险和经验风险为

基于Bayes分类的真实风险和经验风险为

图1 h（xi）和yi的关系

2 PAC-Bayesian定理及证明

笔者主要介绍基于Bayes分类的PAC-Bayesian定理证明.下面首先介绍基于Bayes分类的PAC-Bayesian定理，进而来证明基于Bayes分类的PAC-Bayesian界，以便在计算机学习领域和统计学习理论中更广泛地应用.

定理1 对任何分布D和任何分类集合H，以及支撑集合H上的先验分布，对∀δ∈（0，1）和凸函数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，FRANCOIS 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

中央高校基本科研业务费专项资金资助（SWJTU11CX155）

刘妙妙（1988－），女，山西朔州人，西南交通大学数学学院硕士研究生，主要从事统计与应用研究；赵联文（1964－），男，四川巴中人，西南交通大学数学学院教授，硕士研究生导师，主要从事随机过程、贝叶斯分析和概率极限理论研究.