2011年8月29日,星期一

从众包数据集中提取多标签

之前,我已经讨论了用于处理众包数据的技术,这些数据与``给定项目,从一组固定的标签中选择最佳的单个标签''形式的任务相对应,这对应于成本敏感的多类分类(CSMC)。该处理的结果可能是最终决定,或者可能是用于训练监督学习系统的成本向量。

现在我关注的形式是``给定一个项目,从一组固定的标签中选择零个或多个适用标签'',这与成本敏感的多标签分类(CSML)相对应。处理CSML的一种策略是将一系列独立的二进制分类问题简化为一组,每个问题都预测是否应为项目分配特定的标签。我将此策略称为IBR。如果对原始CSML问题的成本函数进行加权,则IBR是一致的减少 汉明损失 , 但是 与其他CSML损失不一致 (例如,整个组合损失0/1)。在实践中,对于引起的子问题有一定的遗憾,它甚至可能不是加权汉明损失的好策略。

尽管如此,这是我执行过的唯一方法。例如,如果我有一个10标签CSML问题,我将把众包数据处理成10个对应于二进制分类的数据集,运行 标称提取物 在10个数据集的每个数据集上,然后合并结果。此策略存在一些不良方面,所有这些方面都是同一潜在问题的不同方面。首先,如上所述,当将众包处理的结果直接用于决策时,仅对于加权汉明损失是一致的。其次,当用于构造训练集时,它产生的地面真值分布始终是可分离的(即一维分布的乘积)。第三,生成的工人错误生成模型无法对标记错误中的相关性进行建模,因为每个诱发的二进制子问题都将所有错误视为等效。特别是,如果一个工人持续混淆两个不同的标签,那么这种减少就无法利用(因为在诱发的子问题中,``信息错误''与所有其他负面响应混合在一起)。

在标签集$ L $上使用CSML的另一种方法是在标签功率集$ \ mathcal {P}(L)$上减少为CSMC。由于功率集基数的组合爆炸,这是每个人都知道并且没人喜欢的减少之一,但是它确实在成本上捕获了更高阶的结构。它与任何损失函数都是一致的,但通常会遇到样本复杂性问题,而用于减轻样本复杂性的技巧可能会导致遗憾在实践中不佳。这里的情况没有什么不同,因为当我简化为CSMC时,我将利用低秩近似 标称低秩提取 我最近介绍过,这在实践中可能会或可能不会很好地起作用。

我做了直接的事情 标称低秩提取 并通过映射多标签数据集 组合号码系统 , 导致 多低位提取 。因为中的参数数量 标称低秩提取 模型与标签$ | L | $的数量成正比, 多低位提取 模型与$ 2 ^ {|| L |} $之类的东西成比例。实际上,它有点小,因为我可以说如果标签集过多,则标签集的概率为零,例如,对于11个标签问题,其中某个项目的基础事实集最多具有3个标签诱导子问题中标签的数量为$ \ sum_ {k = 0} ^ 3 {11 \ choose k} = 232 $。这个技巧非常重要,因为推理仍然是$ O(| L | ^ 2)$ 标称低秩提取 因此,使诱导标签集保持较小是降低血压的关键。

我还在评估 多低位提取 比IBR好。我从0/1(整个集合)损失的角度看了一个问题,即我从这两种技术看了最可能的(后验)集合。两种方法趋于一致:在一个有853个项目的测试问题上,两种方法具有相同的后验模式718倍,而不同的是135倍。这不足为奇:当众包工作者达成强烈共识时,任何合理的模型都会将共识作为后验模式输出,因此``具有创造力''的唯一机会是众包工作者不同意。如果这种情况经常发生,则表明必须重新设计任务,因为任务要么定义不明确,模棱两可,要么极其困难。对于这两种方法不同的135个项目,我手动确定了我更喜欢哪个标签集。我更喜欢IBR 29次,我喜欢30次 多低位提取 更好,有76次我没有偏好(并且可以理解为什么众包工人不同意!)。这是一个统计死角。

鉴于IBR的计算扩展能力比 多低位提取 ,对于大标签集(例如$ | L | \ gg 10 $)而言,当前是明确的选择。对于小标签集,我正在使用 多低位提取 因为我喜欢它产生的更丰富的后验分布,但这仅是直觉,目前我还没有任何量化的支持。

您可以获得当前的实现 多低位提取 作为...的一部分 标称低秩提取 来自 nincompoop代码存储库.

2011年8月20日,星期六

众包工人的低等级混乱建模

在一个 以前的帖子 我提出了 标称提取物 给定众包数据的任务,该模型用于估计地面真相的分布,该数据由有限标签集合中的强制选择组成。该方法的灵感来自 GLAD框架 Whitehill et。等,但最终也类似于 戴维德和斯凯恩 它可以追溯到1970年代后期(Dawid-Skene并未对任务难度进行建模,而GLAD则无法处理多类情况并使用对称误差模型; 标称提取物 基本上是两者的融合)。基本思想是共同估算基本事实,任务难度和每个工人 混淆矩阵 通过 电磁 。当标签集$ K $小时,效果很好;例如,当$ K = 2 $(二进制标签)时,该方法将估算每个工人的误报率和误报率,或者等效地计算准确性和偏差率。如果少数派通常更准确,则这允许少数派(可能是单身人士)的工作人员覆盖多数派的决策。

不幸的是,随着标签集的增长,每个工人模型中参数的数量也随着$ O(| K | ^ 2)$增长。在我的数据集中,中位数工作人员通常执行大约100项任务,因此当$ | K | >5美元左右,每个工作者的参数数量使数据不堪重负。由于生成模型中的层次结构,降级是合理的:最终使用均值混淆矩阵对工人进行建模。但是,这令人难以理解:众包工作者的技能,动机和意图(有时是对抗性的)差异很大,并且一些个性化是可取的。

合理的方法是对从混乱矩阵的混合物中抽取的人口进行建模,并从整个人口中估算出均值,并从每个工人身上估算出混合物的权重(或者,可以通过艰苦的工作将工人离散分配给工人组) 电磁 )。但是,在准备本博客文章时,我只有这种见识,所以我没有这样做。取而代之的是,自从几周前我在大脑上完成了矩阵完成运算以来,我采用了低秩近似。

在核心 标称提取物 型号是\ [
p(L_ {ij} = l | Z_j = k)\ prope e ^ {-\ alpha_i ^ {(k,l)} \ beta_j},
\]其中$ L_ {ij} $是工作人员$ i $在示例$ j $上输出的标签,$ Z_j $是真实标签,$ \ alpha_i $是工作人员$ i $的混淆矩阵,以及$ \ beta_j $是每个图像的困难因素。回想起来,这可以看作是按标签,真实标签,工作人员ID和图像ID索引的$ 4 ^ \ mathrm {th} $订单对数似然张量的临时低秩近似。

规范多元分解 顾名思义,它是张量的低秩逼近的标准。在元素方面,对于$ 4 ^ \ mathrm {th} $阶张量,它看起来像\ [
p(L_ {ij} = l | Z_j = k)\ propto \ exp(x_ {ijkl})\ approx \ exp \ left(-\ sum_n a ^ {(n)} _ i b ^ {(n)} _ j c ^ {(n)} _ k d ^ {(n)} _ l \ right)。
\]现在实际上只对单个图像评分了几次(例如5次),因此大概最好将每个图像参数折叠成标量$ b_j ^ {(n)} = \ beta_j 1 $,产生\ [
p(L_ {ij} = l | Z_j = k)\ propto \ exp \ left(-\ beta_j \ sum_n a ^ {(n)} _ i c ^ {(n)} _ k d ^ {(n)} _ l \对)。
\]因此,每个评估者都有一个混淆矩阵,该矩阵是等级1矩阵的共享集的线性组合,所产生的参数比 标称提取物 .

通过EM进行估算,如 标称提取物 ,尽管众包数据集的规模通常不大,但效率不是特别好,因此可以完成工作。为了使EM运作良好,有一个良好的起点会有所帮助;在 标称提取物 先前的规范使模型最初将未观察到的真实标签分布估计为平滑的经验标签分布,这是一个合理的初步猜测。这是通过确保最初混淆矩阵的对角元素小于所有其他元素来完成的,因此在此进行复制。完整的模型由\ [
\ begin {aligned}
\ gamma_n&\ sim \ mathcal {N}(0,1),\\
\ log a ^ {(n)} _ i&\ sim \ mathcal {N}(\ gamma_n,1),\\
c ^ {(n)} _ k&\ sim \ mathcal {N}(\ frac {1} {N},1),\\
d ^ {((n)} _ l&\ sim \ mathcal {N}(1,1),\\
\ log \ beta_j&\ sim \ mathcal {N}(1、1),\\
p(L_ {ij} = k | Z_j = k)&\ proto 1,\\
p(L_ {ij} = l | Z_j = k)&\propto \exp \left(-\beta_j \sum_n a^{(n)}_i c^{(n)}_k d^{(n)}_l \right) \;\; (k \neq l),
\ end {aligned}
\]其中\ [
\ begin {array} {c | c}
\ mbox {变量}和\ mbox {说明} \\ \ hline
k,l和\ mbox {索引标签} \\
j&\ mbox {为图片建立索引} \\
i&\ mbox {为工作者编制索引} \\
n和\ mbox {索引近似分量} \\
\ gamma和\ mbox {混淆矩阵混合超参数} \\
a ^ {(n)} _ i和\ mbox {每个工人的混淆矩阵混合向量} \\
c ^ {(n)} {d ^ {{n}}} ^ \ top&n ^ \ mathrm {th} \ mbox {rank-1混淆矩阵} \\
\ beta_j和\ mbox {每个图片的难度} \\
L_ {ij}和\ mbox {观察到的由工作人员分配给图像的标签} \\
Z_j和\ mbox {与图片关联的未知真实标签}
\ end {array}
\]尽管此模型减轻了样本复杂性问题,但计算复杂性仍然是$ O(| K | ^ 2)$,因为我在未观察到的标签上保持了完整的分布,被边缘化以计算可能性,即做软EM。进行硬EM是不希望的,因为基于地面事实的分布可用于为立即进行成本敏感的决策或创建成本敏感的多类分类(CSMC)训练集提供成本向量。换句话说,最好是在众包数据对底层标签没有决定性的情况下进行编码,而硬EM则不这样做。我怀疑吉布斯的抽样策略可能会起作用(通过抽样来估算地面真实情况的分布),但是我还没有尝试过。我也听说过软EM的一种变体,其中在e-step中将小概率强制为零,这可能值得尝试。由于我的众包数据集规模往往不大,因此这还不足以令人烦恼,无法证明进一步的创新。但是,在不久的将来,当我将一些对成本敏感的多标签分类问题减少到电源上的CSMC上时,烦恼程度可能会显着上升。

开源实现可以 标称低秩提取 来自 nincompoop代码存储库.