2012年7月30日,星期一

技术工作

我先说这个 绝不 反映了我到目前为止在Microsoft的经验,或者实际上是我过去10年的任何工作经验。尽管如此,出于某种原因,我还是从今天早上的一个梦中醒来,这在我脑海中:刚开始从事技术行业的人可能会对此感到赞赏。
顺便说一句arxiv纸是 经典任天堂游戏是(NP-)Hard 由Aloupis等撰写。等

2012年7月28日,星期六

新工作

什么时候 雅虎研究的一部分被交易给了微软,开辟了独特的机会。因此,今天是我在Microsoft的第一周,成为Cloud 和 Information Services Laboratory(CISL)的一部分。该团队将专注于推进大数据集群式机器学习,其中涉及一些真正的最高级人员。现在您和我一样了解!希望随着时间的推移,您会通过我们的外部影响有机地遇到CISL。

微软毫不夸张地说,比我过去7年工作的典型公司大3到4个数量级。既然有 城市规模创造力的超线性扩展,我希望工作场所也能使用类似的方法:)

2012年7月10日,星期二

如何用电子表格向人类推荐

我今天作了一个演讲,介绍解决互联网上的匪徒问题的实用技巧。除非面对一个完全的冷启动情况,否则现有的系统会做出决策,而您期望这些决策会得到改善。从理论上讲,这类系统通常没有明确地构造决策,而常见的情况是由一群拥有电子表格软件的笨拙的人开发的一堆试探法。这自然导致了如何击败此类系统的话题。

重要的是要注意什么可能行不通:获取与人类电子表格算法(HSA)相同的信息,对其应用最新的whiz-bang机器学习算法,并希望做得更好。您可能会很幸运,但是特别是在咨询方面,最好按您的喜好叠放甲板。之所以说这不是一个好的策略,是因为机器学习算法是其核心优化算法,但是HSA也是一种优化算法,并且有足够的时间,HSA可以具有相当的竞争力,因此了解其缺点非常重要。

HSA倾向于使用由少量功能(典型数量为5)驱动的计数估计量。这些功能本身可以是少量基本信息(同样通常为5)的非线性手动调整组合,通常可以在电子表格的其他``标签''中找到这些信息。因此,我认为将HSA视为 低维深度学习算法.

HSA的深度学习不是最先进的,但考虑到它通常需要数个人工年的运行时间,所以它可能会很好。因此,您在寻求麻烦,希望仅通过改进的深度学习来最好地获得HSA。 HSA的真正致命弱点是低维度:将所有选项卡中所有基本信息的并集合起来,通常您只看不到20条信息。此外,这些信息通常在原始数据流中密集。

这建议了一个获胜的策略:寻找决策系统可利用的其他信息,而HSA不会考虑这些信息。尤其要寻找稀疏的功能,这些功能很少出现,以至于不能支持统计统计,但是它们可以提供大量的信息(原始文本字段可以具有此属性)。

HSA的另一个潜在弱点是人工方面以及与非平稳性的相互作用。有时,服务系统中的试探法不经常更新,在这种情况下,自动化和处理最新数据可以提供帮助。有时,HSA包含由数据子集驱动的单独的不同季节模型,在这种情况下,您可以通过对所有数据进行训练并包括时间,季节和假日特征来做得更好(对历史数据进行加权加权是个好主意:确保任何交叉验证均在时间上超出样本)。

无论如何,我建议您健康尊重HSA驱动的系统。自然地,当我刚开始时,我认为这样的系统将是简单的目标,并且我已经学会了``艰难的方式''谦卑。

2012年7月2日,星期一

P-U学习与逐点分类

一旦意识到某些事情,便随处可见。特别是当我了解到 P-U问题 我开始看到人们(隐含!)像对待普通数据集一样对待P-U数据集的例子。令人惊讶的是,这似乎通常可以解决,我发现了Elkan和Noto撰写的一篇论文, 仅从肯定和未标记的数据中学习分类器 这有助于解释原因。

在Elkan和Noto模型中,在$ X \ times \ {0,1 \} $采样上有一个分布$ D $,从中可以构成传统的数据集。但是,我们取而代之的是通过$ X \ times \ {0,1 \} $定义的分布$ D ^ \ prime $通过
  1. 画$ {x,y)\ sim D $。
  2. 如果$ y = 0 $,则$ s = 0 $。
  3. 如果$ y = 1 $,则$ s = 1 $,概率为$ p(s = 1 | y = 1)$,独立于$ x $;否则$ s = 0 $。
  4. 输出$(x,s)$。
注意这些是更强的假设,然后在 针对P-U问题优化AUC;在那种情况下,只需要假设能够从阳性标记和未标记的分布中提取样品。在这里,我们做出两个更强的假设:未贴标签和正面示例的生成是``同时''的,而正面标签检查过程与功能无关。

除了警告之外,上述观察模型产生了一些有趣的结果。首先是\ [
p(s = 1 | x)= p(y = 1 | x)p(s = 1 | y = 1),
\],即观察到的数据集中阳性标记的概率与基础未观察到的数据集中阳性标记的概率成正比。这意味着只需在 适当的计分规则 使用P-U数据集应该近似于与真实概率成比例的值。根据可能足以实现良好性能的总体决策问题,我怀疑这就是为什么有时会天真的使用逐点分类的原因。

Elkan和Noto揭示了上述观察模型的其他有趣含义。他们注意到\ [
p(s = 1 | y = 1)= \ mathbb {E} _ {(x,s)\ sim D ^ \ prime} \ left [p(s = 1 | x)\,\ bigl | \,s = 1 \ right],
\],即一旦训练了一个分类器以近似$ p(s = 1 | x)$,就可以通过从$ D ^提取另一个样本来估计比例常数$ p(s = 1 | y = 1)$。 prime $并在正面示例中平均分类器输出。这意味着分类器可以相对于(不可观察!)基础分布进行(大约)校准。

此外,它们显示了如何根据期望wrt $ D ^ \ prime $,\ [来关联任意期望wrt $ D $。
\ begin {aligned}
&\ mathbb {E} _ {(x,y)\ sim D} \ left [f(x,y)\ right] \\
&= \ mathbb {E} _ {(x,s)\ sim D ^ \ prime} \ left [f(x,1)1_ {s = 1} + \ bigl(w(x)f(x,1) +(1-w(x))f(x,0)\ bigr)1_ {s = 0} \ right],
\ end {aligned}
\]其中\ [
w(x)= p(y = 1 | x,s = 0)= \ frac {1- p(s = 1 | y = 1)} {p(s = 1 | y = 1)} \ frac {p (s = 1 | x)} {1-p(s = 1 | x)}
\]是一个加权函数,将未标记的示例视为正例和负例的概率混合。注意,计算加权函数仅需要在P-U数据集$ p(s = 1 | x)$上训练的分类器,以及通过上一段的过程估算的归一化常数$ p(s = 1 | y = 1)$。这真的是很酷的东西:在最初的密度估计预处理步骤将P-U数据集转换为普通数据集之后,基本上利用这一功能可以解决许多不同的学习问题。

我什么时候应该使用它?

通常,我会谨慎地应用此技术。

在以一种方式收集正样本而以另一种方式收集未标记样本的情况下,Elkan和Noto观测模型的同时假设不是一个很好的选择。而 优化AUC 自然适用于这种情况。

对于固定图上的链接预测,底层分布是指标函数的(大!)总和,因此同时性假设似乎是安全的。但是,条件独立性$ s \ perp x | y $的假设可能很危险。例如,在Facebook,女性可能更可能发起并接受朋友的请求,这将使标签审查的可能性取决于功能。

我个人认为,当我具有复杂的目标函数并且想利用度量结果的变化来加权数据时,我很可能会使用此技术。我的直觉说,即使观察模型不准确,重要性加权也可能弊大于利(相对于重要性加权而不是将未标记的样本视为负面样本)。

当然,如果需要校准的估计器,那么优化AUC是不够的,Elkan和Noto技术变得更具吸引力。有时校准是必不可少的,例如在eHarmony,我不得不生成线性程序消耗的估计值。但是,通常校准似乎必不可少,但并非必需。你可以做 选择分类主动学习 未经校准;您可以将以前训练有素的模型合并到集成的决策系统中,而无需校准模型;你甚至可以定价 广义第二价格 样式的关键字竞价,而无需经过校准的点击率估算器。