2011年5月10日,星期二

成本敏感的多标签:观察

我遇到了一个成本敏感的多标签分类(CSML)问题,即有一组标签$ K $,我要将其中的任何一个或全部分配给实例(在我的情况下是文本文档) 。一种方法是将其视为标签$ \ mathcal {P}(K)$的幂集上的成本敏感的多类分类(CSMC)问题。到那时,我可以使用过滤树简化为二进制分类。这具有一些优点,例如一致性(对子问题引起的零后悔意味着对原始问题的零后悔)。它还具有实质性的缺点,既有理论上的(遗憾的常量是缩放为$ O(2 ^ {| K |})$),也有实践上的(最一般的实现方式是时间复杂度缩放为$ O(2 ^ { | K |})$)。

另一种流行的方法是在测试时学习$ | K | $独立的二进制分类器,在测试时独立查询它们,并输出并集。它具有很好的实用属性(时间复杂度缩放为$ O(| K |)$)。但是将问题分解为一组 独立 子问题通常是造成不一致减少的公式,因此我对这种方法感到怀疑。

因此,这是一个有趣的观察:在以下条件下,学习一组独立的二进制分类器等效于CSMC问题上的过滤树方法。
  1. 过滤树是 评分过滤树,即每个节点的分类符为\ [
    \ Phi(x)= 1_ {f(x; \ lambda)> f (x; \phi)}.
    \]
  2. 得分函数进一步分解为一组加权的指标函数,\ [
    f(x; \ lambda)= \ sum_ {k \ in K} 1_ {k \ in \ lambda} f_k(x)
    \]
  3. 华润上华问题的损失函数为 汉明损失.
  4. 构造该树使得在$ k $级别,每个节点的两个输入仅在$ K $的$ k ^ {\ mathrm {th}} $元素存在或不存在时有所不同。考虑到$ \ mathcal {P}(K)$的元素为位字符串,级别为$ k $的比赛正在决定二进制扩展中的$ k ^ {\ mathrm {th}} $位。

在这种情况下,将发生以下情况。在$ k ^ \ mathrm {th} $级别上,锦标赛全部在各组之间进行,只是其$ k ^ \ mathrm {th} $有效位不同。此级别上每个节点的分类器的格式为\ [
\ Phi(x)= 1_ {f_k(x)> 0}
\],并且此级别上所有子问题的所有重要性权重都相同(因为使用了汉明损失)。因此,树的整个$ k ^ \ mathrm {th} $级相当于一个二元分类器,该分类器独立地学习是否将$ K $的$ k ^ \ mathrm {th} $元素包括到最终结果中。

因此,好消息是:这意味着如果汉明损失是CSML问题的损失函数,则学习独立的二进制分类器是一致的。当然,后悔界限中的常数很大,并且分类器的结构假设很重要,因此在实践中性能可能会很差。

那其他损失函数呢?如果保留了分类器的结构假设,则仍可以使用单个二进制分类器来总结过滤树的每个级别。但是,馈送到此分类器的示例的重要性权重取决于先前级别的分类器的输出。

例如,考虑整个标签集的0-1损失。在树的最低层,唯一具有非零重要性权重(成本差异)的锦标赛是考虑是否在所有其他标签正确的情况下包括第一个标签的锦标赛。在树的第二层,唯一可能具有非零重要性权重的锦标赛是考虑是否在所有其他标签正确的条件下包括第二标签的锦标赛。但是,如果第一个分类器出错,则此条件将不会过滤树,所有重要权重将为零。通常,一旦分类器之一出错,训练就会停止。因此,培训过程可以大致概括为:
  1. 给定训练数据$(x,Y)\ X \ times \ mathcal {P}(K)$,
  2. 对于每个$ k = 1 \ ldots | K | $
    1. 令$ \ hat y_k $为标签$ k $是否在目标集中的分类器$ k $的预测。
    2. 将$(x,1_ {k \ in Y})$添加到分类器$ k $的训练集中。请注意,所有非零重要性权重均为1,因此这只是二进制分类。
    3. 如果$ \ hat y_k \ neq 1_ {k \ in Y} $,则停止对此训练基准重复$ k $。
如果分类器经常犯错误,则最终将数据抽取到无用的地步。抛开这个问题,此过程在直观上令人愉悦,因为它不会在链中的后续阶段浪费分类器资源,而这些决策根据整个集合的0-1损失无关紧要。

4条评论:

  1. 博客'的评论系统出现故障,因此约翰·兰福德(John Langford)通过电子邮件将以下内容发送给我:

    所需的深度为log(可能的输出),这意味着如果K个局部标签中有N个,则深度为:
    log(K-choose-N)〜= N log(N / K)。时间复杂度可以相同。真正的问题是空间复杂度,可能是N-choose-K。

    (2)通过使用(逻辑损失或平方损失)回归而不是分类,然后适当地设定阈值,可以使K独立预测变量方法一致。

    (3)如果我理解正确,那么这个结构是深度K吗?在这种情况下,后悔的范围可能会相对较大。

    (4)我偏爱的方法有些不同。您将在每个节点上具有两个分类器,而不是在每个节点上使用单个分类器,每个分类器可预测您是否应该进入子树。这种方法的时间复杂度为N log K,空间复杂度为K。在节点上进行训练有些棘手,因为它可以'当特定子树中有两个标签时,下降是特别重要的。因此,具有等于子树中正确标签之和的重要性权重似乎很好(或者,如果损失函数比汉明复杂,则更复杂)。我相信该算法可以证明比一般的成本敏感案例好得多。如果我们愿意接受时间复杂度K,那么我们可以按照您所考虑的方式使用表示性技巧,在此我们将为子树的所有成员汇总预测的函数值。

    回复删除
  2. >>(1)后悔必然会以过滤树的规模为深度。最大值
    >>所需深度为log(可能的输出),表示如果有N个K
    >>部分标签,则深度为:
    >>log(K-choose-N)〜= N log(N / K)。时间复杂度可以相同。的
    >>真正的问题是空间复杂度,可能是N-choose-K。

    我同意在实践中,权力集的大多数要素不需要
    达到(即,大多数东西标签很少)。

    >>
    >>(2)通过使用可以使K独立预测变量方法一致
    >>(逻辑损失或平方损失)回归而不是分类,然后
    >>适当地阈值化。

    因此,您说的是...使用适当的损失...每个独立
    分类器估计P(元素k当前| x)。这是一致的吗
    仅适用于汉明损失,或适用于任何损失(例如0-1)
    整套损失)?

    对于0-1损失,看来这不可能。考虑一个3元素
    问题,示例空间为空,并表示
    由3位字符串设置的功率

    000:概率为49%
    110:概率25.5%
    101:概率25.5%

    独立分类器将学习输出100,对吗?鉴于
    以以下方式过滤训练数据以供后续分类器使用
    在博客上进行描述将导致学习输出110
    更好的0-1损失。

    >>
    >>(3)如果我理解正确,那么此结构的深度为K吗?在这种情况下,
    >>遗憾的范围可能会比较大。

    是的,它是深度K,后悔界限很大。我只是想
    验证方法是否一致。

    >>
    >>(4)我偏爱的方法有些不同。而不是一个
    >>每个节点上的分类器,每个节点上会有两个分类器,
    >>每一个都预测您是否应该下降到子树中。这个
    >>该方法具有时间复杂度N log K和空间复杂度K。
    >>节点有点棘手,因为它'下降时特别重要
    >>特定子树中有两个标签。因此,具有重要性
    >>权重等于子树中正确标签的总和似乎很好(或
    >>如果损失函数比
    >>汉明)。我相信后悔比一般人要好得多
    >>该算法可以证明成本敏感的情况。如果我们愿意
    >>接受时间复杂度K,那么我们可以沿着
    >>您在想什么行,我们对预测函数值进行汇总
    >>对于子树的所有成员。

    是的,这似乎很有希望。

    回复删除
  3. >对于0-1损失,看来这不可能。考虑一个3元素
    >问题,示例空间为空,并表示
    >由3位字符串设置的功率
    >
    >000:概率为49%
    >110:概率25.5%
    >101:概率25.5%
    >
    >独立分类器将学习输出100,对吗?鉴于
    >以以下方式过滤训练数据以供后续分类器使用
    >在博客上进行描述将导致学习输出110
    >更好的0-1损失。
    >

    糟糕,如果我以相反的顺序训练分类器,我得到000,这
    是很好的,但不是最优的,即使每个子问题都是
    最佳解决。

    需要更多的想法:)

    回复删除
  4. 好吧,我明白了。当反向训练分类器时,在树的第一级上的后悔不为零(在000 vs 001节点处为零;而在100 vs. 101节点处为非零)。基本上,通过在树的整个级别上共享相同的分类器,我很难实现零后悔(在树中求和!)。

    尽管如此,通过分类器进行数据过滤似乎确实可以改善实际情况。

    回复删除