二维欧氏空间内线性凸区域概念的PAC学习算法

许道云

摘 要：实例空间X的一个子集规定一个概念，表现为一个函数c：X→{0，1}。给定X上一个分布D，可能近似正确（PAC）学习算法的目的是基于独立同分布样本S，由算法产生一个近似函数hS，以高概率保证它与目标函数c的误差不超过给定误差值。如果存在这样的算法其样本复杂性及时间复杂性受多项式界，则认为目标概念可以有效PAC学习。本文讨论二维欧氏空间上有界线性凸区域定义的目标概念的学习理论和方法，证明了有界线性凸区域定义的目标概念是有效PAC可学习的，其方法可以推广到n维欧氏空间上由超平面界定的有界凸区域对应的目标概念学习。

关键词：

二维欧氏空间;线性凸区域;概念学习;PAC算法

中图分类号：TP301.6

文献标识码： A

在机器学习中，对给定实例进行分类是一种基本处理方法，其中二分类是重要而基础的分类问题。当实例空间较大或复杂时，精准分类变得复杂或困难，依采样进行近似分类显得有效和实用。可能近似正确（Probably Approximately Correct， PAC）算法提供了一种学习架构，其原理来源于依概率收敛假设。假定实例空间依赖于某个分布，通过独立取样得到容量为m的样本S，如果存在一个算法A能够产生一个输出函数hS，当m趋于无穷大时，hS依概率收敛于目标函数c是PAC可学习的。形式上，对于任意给的误差参数0<ε<1以及可靠性参数0<δ<1，存在一个正整数M，当样本容量m超过M时，算法输出一个近似分类函数hS，至少以概率为（1-δ）确保hS与目标分类函数c的误差不超过ε。如果存在这样的算法，其样本复杂性M和算法的时间复杂性受1/ε，1/δ的多项式界，则称目标概念c是可以有效PAC学习的。PAC学习中，往往加强到对目标概念集C、任意分布D下寻找有效PAC学习算法。如果这样的算法存在，则称概念集C是可以有效PAC学习的。

在本文中，假定实例空间X为二维欧氏空间R2，R2的一个子集的特征函数c：R2→{0，1}规定一个概念。文章重点讨论有界线性凸区域规定的概念的PAC学习理论和方法，线性凸区域是由一组线性不等式界定的区域{（x，y）：aix+biy≤ci（i=1，2，……，k）}，有界性指区域内的点被一个有界矩形（或圆）包含，目标概念c定义为：c（x，y）=1aix+biy≤ci（i=1，2，……，k）成立。 本文给出了这类概念学习的理论和方法，并证明了它是可以有效PAC学习的。相关的理论和方法容易推广到n维欧氏空间由超平面界定的有界凸区域规定的目标概念的PAC学习。

这类概念的学习可以用于大范围线性规划问题可行解的近似识别。

1 PAC学习基础知识

假定X为实例（数据）空间，有限集Y作为数据标记集，通常取Y={0，1}（或{-1，+1}）。一个函数f：X→Y决定X中数据一个划分（分类）：f（x）=f（y）当且仅当x，y属于同一类。X的一个子集称为一个概念，可用其特征函数表示该子集。因此，形式上一個函数c：X→{0，1}表示一个概念，由概念构成的集合C称为概念集。本文中相关的基本知识来自于文献[1]， 更多的实例和应用可参考文献[2-4]。

5 结语

本文将轴对齐矩形概念的有效PAC学习方法一般化到欧氏平面上有界线性凸区域规定的概念学习，其思想和方法在于有界线性凸区域是由有限条（k条）直线围成的多边形区域，在Pr[A]>ε条件下，几何上可以构造目标区域A的边界内侧的一条ε/k-环带，该环带由k个概率是ε/k区域构成。并且，在条件Pr[A]>ε下，依样本S从算法产生的目标区域AS与其中之一不相交，此时有PrS～Dm[er（A，AS）>ε]≤k（1-εk）m≤kexp（-mεk）成立，由此估计算法的样本复杂性。文中的方法对于n维欧氏空间中由超平面界定的有界线性凸区域的PAC学习方法与分析是有效的。

文中的方法适用于数据集中的数据按预定凸区域聚类及误差分析，也可通过适当变换在非欧空间中讨论PAC学习算法。

参考文献：

[1]MOHRI M，ROSTAMIZADEH A，TALWAKAR A.Foundations of Machine Learning[M].Cambridge：The MIT Press，2012.

[2]MITCHELL T M.机器学习[M].曾华军，等译.北京：机械工业出版社，2012.

[3]周志华.机器学习[M].北京：清华大学出版社，2016.

[4]GOODFELLOW I，BENGIO Y，COURVILLE A.深度学习[M].赵申剑，等译.北京：中国工信出版集团，2017.

（责任编辑：周晓南）