显示带有标签的帖子 排行. 显示所有帖子
显示带有标签的帖子 排行. 显示所有帖子

2012年6月27日,星期三

等级+ IR

门农等等在有论文 ICML 2012用排名损失预测准确的概率。基本思想是针对排名损失(例如AUC)训练分类器,然后使用 等渗回归 校准分类器。与使用 适当的计分规则 (例如,逻辑回归),此过程会非参数地探索链接函数的空间,并声称这会带来更好的结果。请注意,从模型复杂性的角度来看,非参数地探索链接函数的空间在直觉上是``安全的'',因为这是一维过程,对基础分类器输出的分数进行运算。

事实证明,我们在eHarmony意外地支持了这一点。当我加入生产系统时,顺序交付了比赛,所以我们从排名损失开始。后来,生产系统转而使用线性程序进行比赛,最简单的方法是在训练流水线的末尾添加校准步骤,然后使用线性插值进行等渗回归。我们想改用具有正确评分规则的直接训练进行分类,但是我们开始 对负数进行二次采样 因此我们需要继续校准分类器,因此从未发生过。我们一直都在怀疑自己是``不连贯的''。嘿,幸运总比好要好。现在,如果我发现自己将来处于类似情况,那么我将能够阐明该方法的基本原理。

这里的元课程是,如果您是一名应用机器学习的从业人员,并且看到上面写有Charles Elkan的名字的论文,则应该阅读。我还没有失望。

2012年6月26日,星期二

关于链接预测的思考

我正在读Richard等的论文。等来自 ICML 2012论文清单同时稀疏和低秩矩阵的估计。我不确定为什么直到现在我仍将这两个想法混为一谈,但回想起来,它们显然是不同的,并且可能要针对这两个进行优化。自从 潜在特征日志线性 Mennon和Elkan(LFLL)模型本质上是一种低阶矩阵分解算法,我想知道如何在其中同时执行稀疏性;我认为在潜在功能上使用$ L_1 $正则化函数可能值得尝试。

但是,这篇论文也让我思考了链接预测。这是这篇论文的引文:
链接预测 -矩阵$ A $是部分观测图的邻接矩阵;不存在和未发现的链接的条目均为0。搜索空间像以前一样不受限制,矩阵$ S $包含链接预测的分数;理想损耗函数是每个系数的零一损耗的经验平均值\ [
l_ {E}(S,A)= \ frac {1} {| E |} \ sum _ {(i,j)\ in E} 1 _ {(A_ {ij}-1/2)\ cdot S_ {ij} \ leq 0}。
\]
所以我读为,``这是一个 P-U问题 我们正在简化为逐点分类。'' 首选方法 对于P-U问题,是降低到排名(AUC损失)。链接预测会是什么样?
  1. 实例是边(即,成对的顶点加上二进位的特定信息)。
  2. 减少AUC是成对分类,即成对的边或成对的顶点。
  3. 邻接图中的每个正(观察)边都将与未标记(未观察或未开发)边配对,后者可能从所有可能的边上均匀地绘制;或可能从给定一个顶点的所有可能边缘开始(``每个顶点AUC'')。
  4. 最终的分类模型可以是纯粹的潜伏模型(例如,纯LFLL),也可以是纯粹由特征驱动的模型(例如,使用 大众)或组合(例如带有辅助信息的LFLL)。
    1. 根据我的经验,与纯粹的LLFL不同,带有辅助信息的LLFL很难训练。

下次我遇到链接预测问题时,我将稍作讨论。

2012年6月25日,星期一

互动学习

Shivaswamy和Joachims的论文叫做 通过主动学习进行在线结构化预测ICML 2012 今年。当然,Joachims与经典的 研究 因此,我将总结一下:试图从行为数据消耗中估算绝对相关性分数是无效的,而利用注意力模型(例如,串行扫描)来估算相对偏好则更为有效。这是您可以带入许多不同情况的那些``深层技巧''之一。

因此,经典示例是当您获得搜索引擎结果时,仅在特定位置$ p $上单击一次,而注意模型假定用户考虑了该位置之前的每个结果再加上一个。因此,部分偏好$ \ forall x \ in [1,p + 1],x \ neq p:r_p>显示r_x $并将其添加到(排名)训练集中。

在我职业生涯的后期,我开始欣赏随机的背景强盗,尤其是为了获得一致的估计值而对历史国家行动密度进行偏置的重要性。这给我带来了一个矛盾:一方面,利用点击反馈优化搜索引擎无疑是必不可少的。 通过探索学习,因为您仅获得有关所显示项目(子项目)的相对偏好的信息。另一方面,当我直奔约阿希姆斯时,我并没有试图消除历史国家行动密度的偏见。

我希望本文能为我解决这个难题。做到了,但是没有达到我的预期。引言中仅提及背景强盗文学是出于比较目的。相反,作者做出以下假设:
  1. 用户损失在(线性)效用差异中凸显出来。
  2. 用户仅提出改进建议(即用户反馈始终指向``下坡'')。
  3. 用户仅建议进行重大改进(即反馈状态的效用增量至少与最佳增量成比例)。
在这种情况下,明智的做法是采用Perceptron风格的算法来实现良好的后悔约束。作者还探索了这些假设的放松(例如,改进仅在预期上有意义,或者反馈有时指向下坡)以及由此产生的后悔保证降低。

我怀疑分析看起来不像我预期的那样,因为在上一段条件的限制下,可以从对抗性方面选择用户反馈。尽管如此,考虑一种``上下文强盗风格''表述可能是有趣的,例如,不是学习与所选手臂相关的奖励,而是学习所选手臂与另一手臂的奖励之间的差异。一个好的起点是关于 具有受控辅助信息的背景强盗,但此处的主要区别在于用户反馈不受算法控制。

2012年3月5日,星期一

PU学习与AUC

在我的新工作中,我要处理的第一个主要问题的特征是普遍存在正标记数据,无负标记数据和大量未标记数据。也称为 p-u学习。尽管有``臭''的绰号,但在这些条件下仍可能取得进展。因为这是一个普遍的困境,所以在文献中有广泛的处理方法:研究人员提倡各种不同的方法和相关的统计假设,因此,我很难总结出最佳实践。幸运的是,由于 张李 事实证明这很有用。

设置是非常自然的:假设特征$ x $和(二进制)标签$ y $通过$ D = D_x \ times D_ {y | x} = D_y \ times D_ {x | y} $共同分发;假定在给定正标签$ y = 1 $的情况下(即带有正标签的示例),您可以访问特征$ x $的分布$ D_ {x | 1} $中的样本;并假设您必须从$ D_x $功能的无条件分布访问示例,即无标签示例。请注意,您无权访问分布$ D_ {x | 0} $中的样本,即,您没有任何带有负号的示例。

事实证明,如果可以使用AUC作为目标函数,则可以直接对正数和未标记的数据进行优化。通过在p-u数据集\ [上关联AUC可以证明这一点。
\ begin {aligned}
\ mathop {\ mathrm {PUAUC}}(\ Phi) &= \mathbb{E}_{(x_+, x_-) \sim D_{x|1} \times D_x}\left[ 1_{\Phi (x_+) >\ Phi(x_-)} + \ frac {1} {2} 1 _ {\ Phi(x_ +)= \ Phi(x_-)} \ right],
\ end {aligned}
\]到使用(不可访问的)带有负标签的示例计算的标准AUC,
\ begin {aligned}
\ mathop {\ mathrm {AUC}}(\ Phi)&= \mathbb{E}_{(x_+, x_-) \sim D_{x|1} \times D_{x|0}}\left[ 1_{\Phi (x_+) >\ Phi(x_-)} + \ frac {1} {2} 1 _ {\ Phi(x_ +)= \ Phi(x_-)} \ right]。
\ end {aligned}
\] 特别是, \[
\ begin {aligned}
&\ mathop {\ mathrm {AUC}}(\ Phi)\\
&= \mathbb{E}_{(x_+, x_-) \sim D_{x|1} \times D_{x|0}}\left[ 1_{\Phi (x_+) >\ Phi(x_-)} + \ frac {1} {2} 1 _ {\ Phi(x_ +)= \ Phi(x_-)} \ right] \\
&= \frac{\mathbb{E}_{(x_+,(x_-,y)) \sim D_{x|1} \times D}\left[ 1_{y=0} \left( 1_{\Phi (x_+) >\ Phi(x_-)} + \ frac {1} {2} 1 _ {\ Phi(x_ +)= \ Phi(x_-)} \ right)\ right] \ right]} {\ mathbb {E} _ {{x, y)\ sim D} \ left [1_ {y = 0} \ right]} \\
&= \frac{\ mathop {\ mathrm {PUAUC}}(\ Phi) - \mathbb{E}_{(x_+,(x_-,y)) \sim D_{x|1} \times D}\left[ 1_{y=1} \left( 1_{\Phi (x_+) >\ Phi(x_-)} + \ frac {1} {2} 1 _ {\ Phi(x_ +)= \ Phi(x_-)} \ right)\ right]}} {\ mathbb {E} _ {(x, y)\ sim D} \ left [1_ {y = 0} \ right]} \\
&= \frac{\ mathop {\ mathrm {PUAUC}}(\ Phi) - \mathbb{E}_{(x, y) \sim D} \left[ 1_{y = 1} \right] \mathbb{E}_{(x_+,x_-) \sim D_{x|1} \times D_{x|1}}\left[ \left( 1_{\Phi (x_+) >\ Phi(x_-)} + \ frac {1} {2} 1 _ {\ Phi(x_ +)= \ Phi(x_-)} \ right)\ right]}} {\ mathbb {E} _ {(x, y)\ sim D} \ left [1_ {y = 0} \ right]} \\
&= \ frac {\ mathop {\ mathrm {PUAUC}}(\ Phi)-\ frac {1} {2} \ mathbb {E} _ {(x,y)\ sim D} \ left [1_ {y = 1} \ right]} {\ mathbb {E} _ {(x,y)\ sim D} \ left [1_ {y = 0} \ right]} \\
&= \ frac {\ mathop {\ mathrm {PUAUC}}(\ Phi)-\ frac {1} {2}} {\ mathbb {E} _ {(x,y)\ sim D} \ left [1_ { y = 0} \ right]} + \ frac {1} {2},
\ end {aligned}
\],他们在论文中写为\ [
\ mathop {\ mathrm {AUC}}(\ Phi)-\ frac {1} {2} \ propto \ mathop {\ mathrm {PUAUC}}(\ Phi)-\ frac {1} {2}。
\]这导致以下极其简单的过程:将未标记的数据视为否定数据,并针对AUC进行优化。

太棒了!

2011年7月20日,星期三

推荐多样性

在推荐系统中,仅使用总体平均评分,每个用户的平均评分和每个项目的平均评分的预测变量形成了强大的基线,令人惊讶地难以超越(就原始预测准确性而言)。当我向查尔斯·埃尔坎(Charles Elkan)询问此事时,他提到有已发表的论文,其报告的结果未能超过该基线。尽管这很有趣,但他指出(释义)``这不仅与准确性有关;没有人喜欢线性基线,因为它向所有人提出了相同的建议。''

我决定使用 电影镜头10m 数据集。首先,对于每个用户,我随机保留其两个评分,然后将其余评分添加到训练集中。我使用 分析重要性感知更新,用于分位数损失。然后,我在测试集中计算了评级MAE。我还计算了每个用户的AUC,如果模型正确地订购了两个保留的等级,则定义为1,否则定义为0;将整个用户的平均数量得出的结果称为``用户AUC''。当然,如果要针对AUC进行优化,则应简化为成对分类,并使用铰链损耗,而不要使用分位数损耗。但是我也很感兴趣,我在MAE中看到的适度收益是否会导致AUC收益更大。结果如下:\ [
\ begin {array} {| c | c | c |}
\ mbox {模型}&\ mbox {MAE(测试集)}&\ mbox {用户AUC(测试集)} \\ \ hline
\ mbox {最佳常数}&\ mbox {0.420}&\ mbox {0.5} \\
\ mbox {线性}&\ mbox {0.356}&\ mbox {0.680} \\
\ mbox {Dyadic $ k = 1 $}&\ mbox {0.349}&\ mbox {0.692} \\
\ mbox {Dyadic $ k = 5 $}&\ mbox {0.338}&\ mbox {0.706} \\
\ mbox {Dyadic $ k = 10 $}&\ mbox {0.335}&\ mbox {0.709}
\ end {array}
\]如前所述,预测升幅(针对两个指标)的最大份额来自线性基线,即$ \ alpha_ {user} + \ beta_ {movie} + c $形式的模型。添加具有潜在维度$ k $的形式为$ a_ {user} ^ \ top b_ {movie} $的附加二项项会稍微提高准确性(尽管我没有进行交叉验证,将User AUC视为二项式意味着$ 0.004 $的标准误,这表明用户AUC的二元提升几乎没有意义)。

接下来,我介绍了推荐多样性。我从用户中随机抽取了一个子样本(结果大小为11597),详尽估计了数据集中每个电影的排名,然后为每个用户计算了前三部电影。在每种尺寸$ n = \ {1,2,3 \} $下,我查看了建议该尺寸的最受欢迎电影集的发布频率($ \ max p_n $),并且还计算了推荐的电影(集合,而不是列表:如果一个用户有推荐$ a,b,c $,而另一个用户有推荐$ c,b,a $,则认为它们相同)。 \ [
\ begin {array} {| c | c | c | c | c | c | c |}
\ mbox {模型}&\ max p_1&\ mbox {独特的1组}&\ max p_2&\ mbox {独特的2组}&\ max p_3&\ mbox {独特的3组} \\ \ hline
\ mbox {线性}&\ mbox {1}&\ mbox {1}&\ mbox {1}&\ mbox {1}&\ mbox {1}&\ mbox {1} \\
\ mbox {Dyadic $ k = 1 $}&\ mbox {0.478}&\ mbox {6}&\ mbox {0.389}&\ mbox {10}&\ mbox {0.218}&\ mbox {18} \\
\ mbox {Dyadic $ k = 5 $}&\ mbox {0.170}&\ mbox {112}&\ mbox {0.120}&\ mbox {614}&\ mbox {0.069}&\ mbox {1458} \\
\ mbox {Dyadic $ k = 10 $}&\ mbox {0.193}&\ mbox {220}&\ mbox {0.102}&\ mbox {1409}&\ mbox {0.035}&\ mbox {3390}
\ end {array}
\]正如预期的那样,线性模型中没有推荐的多样性。然而,有趣的是,即使准确性指标没有显着提高,分集也会随着潜在维数的增加而爆炸。对于$ k = 10 $,前3个建议集中的多样性是巨大的:共享相同前3个建议的最大用户组仅占用户群的3.5%。 ($ k = 10 $和$ \ max p_1 $的0.193结果不是错别字;即使有更多推荐的独特电影被推荐为用户的顶级电影,$ k = 10的最受欢迎的#1电影与$ k = 5 $相比,选择$的频率更高。不确定发生了什么。)

如果您要去产品经理那里说:“我有两个推荐模型,它们具有相同的准确性,但是一个向所有人提出相同的建议,而另一个向不同的人提出不同的建议,您想要哪个?”您可以打赌产品经理会说第二个。实际上,为了达到推荐多样性而牺牲一些准确性可能是可以接受的。考虑到二元模型可以提高准确性和多样性,因此是双赢的。

2011年6月23日,星期四

减少AUC到逐点回归

查尔斯·埃尔坎洛杉矶机器学习聚会昨天。在演讲之前,我们正在讨论AUC损失的排名问题。众所周知 归结为成对分类 导致AUC后悔界限为$ 2 r $,其中$ r $是对归类分类问题的遗憾。查尔斯说,在实践中,他通过简化为逐点逻辑回归获得了很好的结果,即估计``相关概率''并使用归纳排名。他推测后勤损失实际上是在某种程度上限制了AUC损失,这是因为它给数据点提供了有效的重要性权重(高表示``令人惊讶'',低表示``不令人惊讶'');有趣的是,它比平方损失要好得多;铰链丢失根本不起作用。关于铰链损耗的观察是有道理的,因为已知减少逐点分类并不可靠。但是平方或逻辑损失呢?

因此,在考虑减少量时,存在一个一致性问题:对引起的子问题零后悔会导致对原始问题的零后悔吗?由于平方和逻辑损失是 正确的评分规则,一致性在直觉上是可能的。但是,对于嘈杂的问题,还存在效率问题。换句话说,对引发问题的后悔如何限制对原始问题的后悔?

物流损失是棘手的,但是平方损失我取得了一些进展。假设从$ S = X \ times Y $中抽取示例对,其中$ Y = \ {0,1 \} $根据分布$ D_ {S \ times} = D_x \ times D_ {y | x} \ times D_x \ times D_ {y | x} $。如果您熟悉排名问题,那么您可能正在调整,因为在实践中很少有明确的逐点相关性二进制概念。但是,由于我正在谈论归结为点回归的减少,因此我将假设它可以取得进展。

我现在要修复$ x_1 $和$ x_2 $,最后我会期望$ D_ {x | 0} \ times D_ {x | 1} $。给定分类器$ h:S \ to \ mathbb {R} $,条件AUC损失由\ [
\ mathrm {AUC}(h | x_1,x_2)= E _ {(y_1,y_2)\ sim D _ {(y_1,y_2)| (x_1,x_2)}} \ left [\ left(1_ {y_1> y_2} 1_{h (x_1) < h (x_2)} + 1_{y_1 < y_2} 1_{h (x_1) >h(x_2)} \ right)\ right]。
\]同时平方损失由\ [
L_2(h | x_1,x_2)= E _ {(y_1,y_2)\ sim D _ {(y_1,y_2)| (x_1,x_2)}} \ left [\ sum_k y_k(1-h(x_k))^ 2 +(1-y_k)h(x_k)^ 2 \ right]。
\]
不失一般性地假定$ h(x_1)<h(x_2)$。然后有条件的AUC损失变为\ [
\ mathrm {AUC}(h_1,h_2,p_1,p_2)= p_1(1-p_2),
\]其中$ h_k = h(x_k)$和$ p_k = p(y_k = 1 | x_k)$。最佳AUC损失由\ [
\ mathrm {AUC}(h_1,h_2,p_1,p_2)= \ begin {cases}
p_1(1-p_2)和\ mbox {if} p_1 \ leq p_2,\\
(1-p_1)p_2& \mbox{if } p_1 > p_2.
\ end {cases}
\],因此AUC后悔由\ [
r_ \ mathrm {AUC} = \ max \ left(p_1-p_2,0 \ right)。
\]同时对分类器的平方损失遗憾是\ [
\ begin {aligned}
r_2(h; x_1,x_2)&= \sum_k r_2 (h_k;x_k)= \ sum_k(p_k-h_k)^ 2。
\ end {aligned}
\]作为对手,我的目标是针对给定的平方损失后悔最大化AUC后悔。要解决的程序是\ [\ max_ {p_1,p_2,h_1,h_2}(p_1-p_2)\]受\ [
\ begin {aligned}
p_2-p_1&\ leq 0,\\
h_1-h_2&\ leq 0,\\
\ sum_k(p_k-h_k)^ 2&= r_2 (h; x_1, x_2).
\ end {aligned}
\]通过 KKT条件 (感谢Mathematica!)产生解\ [
\ begin {aligned}
h_1&= h_2,\\
h_2&= \ frac {p_1 + p_2} {2},\\
p_1-p_2&= \sqrt{2 r_2 (h; x_1, x_2)}.
\ end {aligned}
\]这就是说,对手的最佳选择是将$ h_1 $和$ h_2 $放置在$ p_1 $和$ p_2 $的均值之上和之下的$ \ epsilon $;这让人联想到 中位数选民定理。在这种情况下,AUC的遗憾是\ [
r _ {\ mathrm {AUC}}(h; x_1,x_2)\ leq \ sqrt {2 r_2(h | x_1,x_2)}。
\]现在我可以对两边的$ D_ {x | 0} \ times D_ {x | 1} $做出期望,\ [
\ begin {aligned}
r _ {\ mathrm {AUC}}(h)&\leq E_{(x_1, x_2) \sim D_{x|0} \times D_{x|1}} \left[ \sqrt{2 r_2 (h;x_1,x_2)} \ right] \\
&\leq \sqrt{ 2 E_{(x_1, x_2) \sim D_{x|0} \times D_{x|1}} \left[ r_2(h; x_1,x_2)\right] } \\
&= \sqrt{2 \left( E_{x \sim D_{x|0}} \left[ r (h;x)\ right] + E_ {x \ sim D_ {x | 1}} \ left [r(h; x)\ right)\ right)} \\
&= 2 \sqrt{E_{x \sim \tilde D_x} \left[ r (h; x) \right]} \\
&= 2 \ sqrt {\ tilde r_2(h)}
\ end {aligned}
\]这里$ D_ {x | y} $是给定标签$ y $的$ x $的条件分布,$ \ tilde D_x = \ frac {D_ {x | 0} + D_ {x | 1}} {2 } $是$ x $的类平衡分布,而$ \ tilde r_2(h)$是基础分类器相对于$ \ tilde D_x $的平方误差后悔。那么这是什么意思?
  • 如果针对类平衡的数据集(即相同数目的正负数)计算平方损失后悔,则此分析仅保证减少平方损失的一致性。这可以通过例如重要性加权或拒绝采样来实现。不平衡的数据集可能会出现问题,例如,当使用几乎完全是负样本的数据集和一个正样本的数据集时,基础数据集的平均每样本均方差损失后悔与AUC后悔规模之间的界限为数据集(因为在一个积极的例子上的重要性越来越大,但被忽略了)。
  • 后悔界限对潜在遗憾具有平方根依赖性,这比成对归类到分类时对潜在遗憾的线性依赖性更差。

您可能会想到,后勤损失不适合该技术。但是,我开始欣赏查尔斯发表评论的直觉。想象一下一个在线学习场景,一个物流学习者在不考虑他们的班级标签的情况下就被不断地输入示例。如果数据集非常不平衡,例如学习者大多是负面的,他们将很快收敛于一个高度负面的常数。这将有效降低负面示例的学习率,而正面示例将保持较高的学习率。这模仿了对数据加权以进行类平衡的重要性操作。如何将这种直觉转化为正式声明?