2012年1月6日,星期五

成本敏感型二进制分类和主动学习

现在,出现了多种针对二进制分类的主动学习算法,现在是时候问什么 机器学习减少 可以说关于其他类型学习问题的主动学习。现在,我将重点介绍对成本敏感的二进制分类,其目标是与\ [
h ^ * = \ mathop {\ operatorname {arg \,min \;}} _ {h \ in H} E _ {(X,Y,\ Upsilon)\ sim D} [\ Upsilon 1_ {h(X)\ neq Y}],
\]其中$ X $是要素,$ Y \ in \ {0,1 \} $是标签,$ \ Upsilon \ in [0,c_ {max}] $是成本,$ D $是未知的分布。

成本可见

首先,我假设我们可以在未标记的数据中看到费用,即无需查询标签。这在实践中并不常见,因为成本通常取决于标签(例如,误报要比误报要贵)。但是,这将为可能的情况提供一些直觉。

我可以使用拒绝采样来 将对成本敏感的分类降低为二进制分类 然后应用主动学习二进制分类器。具体来说,我可以以接受概率$ \ Upsilon_k / c_ {max} $拒绝输入流的样本,如果样本被接受,它将丢弃成本并使用二进制分类。这是后悔变换,其将所引起的二进制后悔按比例缩放$ E [$]。因此,如果我们很有可能后悔在给定$ n $个示例的情况下将$ r_b(n)$绑定到基础活动二进制分类器中,则大概替换$ n \ rightarrow(E [\ Upsilon] / c_ {max})n + O( \ frac {1} {n} \ log \ frac {1} {\ delta})$并按$ E [\ Upsilon] $缩放会给我们带来很大的可能性$ r_c(n)$问题,\ [
r_c(n)= E [\ Upsilon] r_b \ left(\ frac {E [\ Upsilon]} {c_ {max}} n + O(\ frac {1} {n} \ log \ frac {1} {\ delta})\ right)。
\]
同时,在拒绝的情况下,我们绝对不会查询标签$ Y_k $。在不拒绝的情况下,我们可以查询标签$ Y_k $,具体取决于在诱导的主动二进制分类器中使用标签的可能性。如果在给定$ n $实例的情况下,在诱导二进制分类器$ l_b(n)$的标签复杂度上具有较高的概率界限,则大概替换$ n \ rightarrow(E [\ Upsilon / c_ {max})n + O (\ frac {1} {n} \ log \ frac {1} {\ delta})$将给标签复杂度$ l_c(n)$带来高的概率边界,该复杂度是原始成本敏感问题\ [
l_c(n)= l_b \ left(\ frac {E [\ Upsilon]} {c_ {max}} n + O(\ frac {1} {n} \ log \ frac {1} {\ delta})\ right )。
\]这是一种用于主动学习的元算法,具有成本敏感的二进制分类和可见的成本。
算法:可见成本案例
具有可见成本和主动学习二进制oracle $ \ mathcal {O} $的主动成本敏感型二进制分类的拒绝采样。
  1. 以成本$ \ Upsilon_k $获得未标记的数据点$ X_k $。
  2. 用$ \ mathrm {Pr}(\ mathrm {heads))=(\ Upsilon_k / c_ {max})$掷一个偏向硬币。
    1. 如果是正面,请将未标记的特征$ X_k $传递给$ \ mathcal {O} $。
    2. 如果有尾巴,则丢弃未标记的数据点。

如果二进制oracle使用 不受约束的不可知主动学习,这种推理暗示了类似\ [
\ mathrm {err} _c(h_n)\ leq \ mathrm {err} _c(h ^ *)+ O \ left(\ sqrt {c_ {max} E [\ Upsilon] \ frac {\ log n} {n}} \对)
\]是可能的,其中\ [
\ mathrm {err} _c(h)= E _ {(X,Y,\ Upsilon)\ sim D} [\ Upsilon 1_ {h(X)\ neq Y}],
\]和诸如[[
\ mbox {要求标签} \ leq 1 + \ theta \ cdot \ frac {2} {c_ {max}} \ mathrm {err} _c(h ^ *)n + O \ left(\ theta \ sqrt {\ frac { E [\ Upsilon]} {c_ {max}} n \ log n} \ right)
\]是可能的。这里的$ \ theta $是引起的二进制子问题的分歧系数。

费用不可见

现在,我假设仅在查询标签时才可以使用成本。假设我们决定通过首先根据底层主动学习算法接受或拒绝,然后再查询标签并观察到成本$ \ Upsilon_k $,然后掷出另一枚硬币并以概率$(\ Upsilon_k接受,来实施上述拒绝抽样程序/ c_ {max})$。这将与无形成本约束相一致,但在结果方面相同。如果成本可见,这将是愚蠢的,但如果成本不可见,这是可行的策略。后悔的界限仍然是相同的,但是不幸的是,现在引起的二元问题的标签复杂度通过未经修改的$ l_c(n)= l_b(n)$。当然,标签的复杂性 游戏中的主动学习,否则我们将查询每个标签并获得金标准的被动学习后悔。因此,对于一个特定的后悔界限,具有更差的标签复杂性是非常不希望的。

算法:无形成本案
具有不可见成本和主动学习二进制oracle $ \ mathcal {O} $的主动成本敏感型二进制分类的拒绝采样。
  1. 获取未标记的数据点$ X_k $。
  2. 将未标记的数据点$ X_k $传递到$ \ mathcal {O} $,并拦截\ {0,1 \} $中的决策$ Q_k \ in查询标签。
    1. 如果$ Q_k = 0 $,则不执行任何操作。
    2. 如果$ Q_k = 1 $,
      1. 查询标签并观察$ \ Upsilon_k $和$ Y_k $。
      2. 用$ \ mathrm {Pr}(\ mathrm {heads))=(\ Upsilon_k / c_ {max})$掷一个偏向硬币。
        1. 如果是正面,将标签$ Y_k $传递给$ \ mathcal {O} $,这在$ Q_k = 1 $时可以预期。
        2. 如果有尾巴,则丢弃标签并将$ X_k $的表示``撤消''到$ \ mathcal {O} $。

特别是对于使用不受约束的不可知主动学习的基础学习者,这种推理建议何时看不到成本,\ [
\ mbox {要求标签} \ leq 1 + \ theta \ cdot \ frac {2} {E [\ Upsilon]} \ mathrm {err} _c(h ^ *)n + O \ left(\ theta \ sqrt {n \ log n} \ right)。
\]两种标签复杂度的比较表明,在“智能”成本敏感型主动学习算法和“智能”成本不可实现的情况下,我们可能会获得$(E [\ Upsilon] / c_ {max})$的改进。这里勾勒出的``哑巴''。

1条评论:

  1. 在第三段中,如何得到n \ rightarrow(E [\ Upsilon] / c_ {max})n + O(\ frac {1} {n} \ log \ frac {1} {\ delta})项?

    回复删除