2012年4月25日,星期三

选择性分类与主动学习

El-Yaniv和Wiener的一篇论文中有一颗宝石 不可知选择分类。本文的重点是选择性分类是主动学习的测试时间模拟。

在选择性分类中,分类器可以选择拒绝输入并放弃预测。在实现高分类精度的同时,很少会拒绝这种想法。这是 多目标优化 ,所以一个 帕累托边疆 出现,称为 风险覆盖曲线 在这种情况下。

可以将其形式化如下:选择性分类器是一对$(h,g)$函数$ g:X \ to \ {0,1 \} $和$ h:X \ to Y $,其中$ g $指示是否拒绝输入,如果接受输入,$ h $是分类规则,\ [
(h,g)(x)= \ begin {cases} \ mathrm {reject}& \mathrm{if}\;g(x)= 0,\\ h(x)和\ mathrm {否则} \ end {cases}。
\]假设$ h $来自集合$ \ mathcal {H} $;该论文对于我们要与之竞争$ g $的设置尚不清楚,但最终它们的最优性概念较弱,因此无关紧要。特征$ X $和标签$ Y = \ {0,1 \} $根据$ D $联合分配。在被动批处理设置中,有人将一袋数据(例如i.i.d)交给我们。从$ D $和拒绝预算$ b $,然后我们必须产生一对$(h,g)$,理想情况下,该对是靠近Pareto边界\ [
\ begin {aligned}
\ mathop {\ operatorname {arg \,min \,}} \ limits_ {h \ in \ mathcal {H}} \ mathbb {E} _ {(x,y)\ sim D}&[1_ {g(x) = 1} 1_ {h(x)\ neq y}] \\
&\ mathrm {s.t。} \\
E _ {(x,y)\ sim D}&[1_ {g(x)= 1}] \ leq b。
\ end {aligned}
\]这真的很难,所以El-Yaniv和Wiener考虑了另一个问题。令$ h ^ * = \ mathop {\ operatorname {arg \,min \,}} _ {h \ in \ mathcal {H}} \ mathbb {E} _ {(x,y)\ sim D} [1_ { h(x)\ neq y}] $是最佳分类器。对$(h,g)$称为a 弱最优 如果\ [
\ mathbb {E} _ {(x,y)\ sim D} [1_ {g(x)= 1} 1_ {h(x)\ neq y}] \ leq \ mathbb {E} _ {(x,y )\ sim D} [1_ {g(x)= 1} 1_ {h ^ *(x)\ neq y}],
\],即在选择分类器接受的输入空间区域中,它的表现至少与最优假设相同。这不如帕累托边境上的存在,但是比尖锐的棍棒要好!

现在是漂亮的部分。作者表明,可以(如下所示)构造弱最优的选择性分类器(概率很高)。令$ \ tilde h $为经验风险$ R(h)$的最小值,并通过\ [定义$ x $的经验不一致假设。
h'_x \ doteq \ mathop {\ operatorname {arg \,min \,}} \ limits _ {\ substack {h \ in \ mathcal {H},h(x)\ neq \ tilde h(x)}} R( H)。
\]然后 怀疑指数 是经验风险$ R(h'_x)-R(\ tilde h)$与由[[
g(x)= 0 \ iff R(\ tilde h_x)-R(\ tilde h)\ leq \ Delta
\]是弱最优的,其中$ \ Delta $是训练集大小,VC维度$ \ mathcal {H} $和概率约束$ \ delta $的函数。换句话说,如果不同意当前输入的经验最小化器在经验上并不昂贵,则拒绝对输入进行分类,否则根据经验最小化器进行分类。

如果看起来很熟悉,那是因为难以置信指数等于 阿尔威特 在确定查询标签的可能性时。这在训练时``寻求标签''和测试时``拒绝预测''之间建立了令人愉快的对应关系。

这也表明 Vowpal兔子 可以轻松地用作选择性分类器,因为它已经为主动学习目的计算了难以置信指数的快速近似值。

没意见:

发表评论