成本敏感的多标签：观察

我遇到了一个成本敏感的多标签分类（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损失无关紧要。