Agnostic Boosting
Agnostic Boosting
复制标题
不可知增强
DOI：
10.1007/3-540-44581-1_33
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Y. Mansour
中科院分区：
文献类型：
--
作者：
Shai Ben;Philip M. Long;Y. Mansour
我们将Boosting范式扩展到不可知性学习的现实设置，即训练样本是通过样本和标签上的任意(未知)概率分布生成的。对于假设类F，我们定义了一个β弱不可知学习器如下：给定一个分布P，它输出某个假设h∈F，其误差至多为erp(F)+β，其中erp(F)是假设在分布P下的最小误差(注意，对于某些分布，界可能超过一半)。
我们给出了一个Boosting算法，它利用弱不可知性学习器计算一个假设，其误差至多为max{c1(β)er(F)c2(β)，Ɛ}，时间多项式in 1/Ɛ。虽然这种泛化保证明显弱于已知的PAC Booking算法，但需要注意的是，β弱不可知学习者所需的假设要弱得多。事实上，弱不可知性学习概念的一个重要优点是，在许多情况下，这种学习是通过有效的算法实现的。
We extend the boosting paradigm to the realistic setting of agnostic learning, that is, to a setting where the training sample is generated by an arbitrary (unknown) probability distribution over examples and labels. We define a β-weak agnostic learner with respect to a hypothesis class F as follows: given a distribution P it outputs some hypothesis h ∈ F whose error is at most erP (F) + β, where erP (F) is the minimal error of an hypothesis from F under the distribution P (note that for some distributions the bound may exceed a half).
We show a boosting algorithm that using the weak agnostic learner computes a hypothesis whose error is at most max{c1(β)er(F)c2(β), Ɛ}, in time polynomial in 1/Ɛ. While this generalization guarantee is significantly weaker than the one resulting from the known PAC boosting algorithms, one should note that the assumption required for β-weak agnostic learner is much weaker. In fact, an important virtue of the notion of weak agnostic learning is that in many cases such learning is achieved by efficient algorithms.