2011年11月28日,星期一

重要性感知多项式逻辑更新

由于我在内部使用多项逻辑回归 弹奏钢琴 我很好奇是否有 重要度更新 为了它。我正在使用的损失函数是目标概率向量$ q $和权重$ w $和输入特征$ x $计算的预测概率向量$ p $的交叉熵。
\ begin {aligned}
l(x,w,q)&= \ sum_ {j \ in J} q_j \ log p_j(x,w),\\
p_k(x,w)&= \ frac {\ exp(x ^ \ top w_k)} {\ sum_ {j \ in J} \ exp(x ^ \ top w_j)},\\
w_0&= 0。
\ end {aligned}
通常,通过集成瞬时损失函数的梯度动力学来得出重要性感知更新,对于该更新,通常的SGD更新步骤可以看作是一阶欧拉逼近。对于$ j>0 $,权重的梯度动力学为\ [
\ begin {aligned}
\ frac {d w_j(t)} {d t}&= \ frac {\ partial l(x,w(t),q)} {\ partial w_j(t)} \\
&= \ bigl(q_j-p_j(x,w(t))\ bigr)x。
\ end {aligned}
\]所有的梯度都指向相同的方向,因此我将寻找形式$ w_j(t)= w_j + s_j(t)x $的解,得出\ [
\ begin {aligned}
\ frac {d s_j(t)} {d t}&= q_j-\ tilde p_j(x,w,s(t)),\\
\ tilde p_k(x,w,s)&= \ frac {\ exp(x ^ \ top w_k + s_k x ^ \ top x)} {\ sum_ {j \ in J} \ exp(x ^ \ top w_j + s_j x ^ \ top x)} \\
&= \ frac {p_k(x,w)\ exp(s_k x ^ \ top x)} {\ sum_ {j \ in J} p_j(x,w)\ exp(s_j x ^ \ top x)},\ \
s_j(0)&= 0。
\ end {aligned}
\]在这一点上,我无法取得分析进展。但是,这现在看起来像$(| J | -1)$维ODE,由于可以记住$ p $和$ x ^ \ top x $,因此其右手边可以用$ O(| J |)$计算。因此,在实践中,可以将其数字化集成,而不会产生大量开销(我只看到整体速度降低了10% 弹奏钢琴)。对于顺序案例,Polytomous Rasch有一个类似的技巧。

即使在所有重要权重都为1的数据集上,我也得到了改进的结果。这不是破天荒的举动,但我确实看到了在一些问题上的泛化误差的持续适度改善。我怀疑如果我详尽地搜索学习参数的空间(初始学习率$ \ eta $和幂律衰减$ \ rho $),我可能会找到无需提升重要性即可更新的提升设置。但这是重要性感知更新的好处之一:它使最终结果对学习速率参数的选择不那么敏感。

2011年11月23日,星期三

有序逻辑回归是一个热点

我已将序数支持添加到 弹奏钢琴。如果您想预测某人是否 热不热,现在这是适合您的工具。[1](来自Wikipedia文章的最佳语段:``此外,根据这些研究人员的说法,大脑的基本功能之一是将图像分类为热门或不分类的类别。''很显然,大脑研究人员拥有 所有的乐趣

虽然我已经有一个 工人模型 我需要一个分类器来搭配它。 有序逻辑回归 似乎是自然选择,但由于计算原因,我最终没有使用它。有序逻辑回归概率模型为\ [
\ begin {aligned}
P(Y = j | X = x; w,\ kappa)&= \ frac {1} {1 + \ exp(w \ cdot x-\ kappa_ {j + 1})}-\ frac {1} {1 + \ exp(w \ cdot x-\ kappa_j)},
\ end {aligned}
\]其中$ \ kappa_0 =-\ infty $,而$ \ kappa_ {n + 1} = \ infty $。所以第一个问题是,除非约束$ i<j \暗示\ kappa_i <\ kappa_j $被强制执行,预测概率变为负数。由于我用对数表示概率,这对我来说是个问题。然而,更糟糕的是,关于类别权重相对于权重的梯度的公式在计算上不是很方便。

将此与 多模型Rasch模型,\ [
\ begin {aligned}
p(Y = 0 | X = x; w,\ kappa)&\ propto 1 \\
p(Y = j | X = x; w,\ kappa)&\ propto \ exp \ left(\ sum_ {k = 1} ^ j(w \ cdot x-\ kappa_j)\ right)
\ end {aligned}
\]违反$ i没有特别的数值困难<j \暗示\ kappa_i <\ kappa_j $。当然,如果确实发生了这种情况,则强烈暗示有一些非常错误的事情(例如,响应变量实际上未按照我的假定顺序排序),但关键是我可以进行无限制的优化,然后最后检查是否合理。另外,计算类别概率相对于权重的梯度是相对令人满意的。因此,我采用了Polytomous Rasch功能形式。

这是一个在数据集上运行的示例,试图从他们的个人资料预测Twitter用户的(离散的)年龄。
strategy = ordinal
initial_t = 10000
eta = 0.1
rho = 0.9
n_items = 11009
n_labels = 8
n_worker_bits = 16
n_feature_bits = 18
test_only = false
prediction file = (no output)
data file = (stdin)
cumul    since    cumul    since      example current current current  current
avg q    last     avg ce   last       counter   label predict ratings features
-1.15852 -1.15852 -2.20045 -2.20045         2      -1       2       3       33
-1.21748 -1.25678 -1.8308  -1.58437         5      -1       2       4       15
-1.20291 -1.1873  -1.89077 -1.95075        10      -1       2       3       34
-1.15344 -1.09367 -1.94964 -2.01505        19      -1       2       1       18
-1.21009 -1.2637  -1.99869 -2.05351        36      -1       4       1       29
-1.13031 -1.04421 -1.80028 -1.58384        69      -1       3       2       46
-1.1418  -1.15346 -1.58537 -1.35723       134      -1       3       2       35
-1.14601 -1.15028 -1.38894 -1.18489       263      -1       2       4       31
-1.1347  -1.12285 -1.14685 -0.89911       520      -1       3       2       42
-1.12211 -1.10868 -1.03302 -0.91764      1033      -1       3       3       26
-1.11483 -1.10755 -0.91798 -0.80203      2058      -1       3       3       43
-1.10963 -1.10447 -0.82174 -0.72509      4107      -1       3       4       16
-1.07422 -1.03901 -0.82659 -0.83145      8204      -1       2       4       29
-1.02829 -0.98195 -0.84504 -0.86352     16397      -1       3       2       55
-0.98414 -0.93991 -0.85516 -0.86528     32782      -1       2       1       16
-0.94415 -0.90447 -0.84898 -0.84281     65551      -1       2       4       27
-0.90247 -0.86075 -0.86127 -0.87355    131088      -1       2       4       15
-0.88474 -0.83311 -0.86997 -0.89529    176144      -1       4       3       27
applying deferred prior updates ... finished
gamma = 0.4991 1.4993 2.5001 3.5006 4.5004 5.5001 6.5001
  13.65s user 0.19s system 89% cpu 15.455 total
弹奏钢琴 可从 Google代码存储库.

脚注1

实际上,“热还是不热”是一个不好的例子,因为可能没有普遍的地面真理热度。而是一个个性化的概念,因此也许可以通过诸如 这个 适用于垃圾邮件过滤。 弹奏钢琴 更适用于具有客观事实的问题,例如根据Twitter用户的Twitter个人资料预测其年龄。听起来不那么性感,对吗?究竟。这就是为什么在脚注中。

2011年11月16日,星期三

众包数据的Logistic回归

最近我一直在处理众包数据 生成模型 在地面真相标签上创建分布。然后,通过考虑我的分类损失函数相对于地面真实分布的期望,我将该分布转换为成本向量,以进行成本敏感的分类。因为生成模型假设典型的工作人员通常是正确的,所以它们受共识驱动:他们将假定在分配标签时始终与同辈意见不一致的工作人员的准确性较低,因此应减少对基础事实的分配。

雷卡尔(Raykar)等等 请注意,接受众包数据训练的分类器最终将与特定众包标签达成或不同意。最好用它来告知模型每个工作人员可能的错误,但是到目前为止,在我一直使用的顺序过程中,这是不可能的:首先要估算出地面真实性,而不是要对分类器进行估算。因此,他们建议共同估算地面真相和分类器,以使彼此相互告知。

在这一点上,让我提供相同的示意图以帮助阐明。


这是与我迄今为止使用的生成模型相对应的板图。未观察到的地面真相标签$ z $与通过向量$ \ alpha $和标量项目难度$ \ beta $参数化的每个工人模型相结合,以创建用于项目的观察到的工人标签$ l $。 $ \ mu $,$ \ rho $和$ p $分别是$ \ alpha $,$ \ beta $和$ z $先前分布的超优先级参数。根据问题(多类,有序多类或多标签),有关$ z $,$ \ alpha $和$ \ beta $如何产生$ l $变化的分布的详细信息,但是上图给出了一般结构。

雷卡尔(Raykar)等等扩展生成模型以允许观察到的项目特征。


该图假定项目具有$ \ psi $的特征,并且给定真实标签$ z $时有条件地独立发出工作标签$ l $。这听起来像是伪造的,因为大概项目特征直接或至少间接地通过标量困难驱动了工人,除非项目特征对于众包工人而言是完全不可访问的。尝试丰富以上图表以解决问题可能是一个合理的下一步,但是事实是所有生成模型都是方便的小说,因此我现在使用上面的内容。雷卡尔(Raykar)等等提供了用于联合分类的批处理EM算法,但以上内容非常适合我一直使用的在线算法。

对于每个输入对$(\ psi,\ {(w_i,l_i)\})$,这是在线过程。
  1. 使用项目特征$ \ psi $,询问使用 适当的计分规则,并将输出解释为$ P(z | \ psi)$。
  2. 使用$ P(z | \ psi)$作为在线算法中$ z $的优先分布 先前讨论过 用于处理众包标签$ \ {(w_i,l_i)\} $。这将产生结果$ P(z | \ psi,\ {(w_i,l_i)\})$。
  3. 针对分配$ P(z | \ psi,\ {(w_i,l_i)\})$使用预期的先前评分规则损失的SGD更新分类器。例如,对数损失(多类logistic回归)的目标函数是交叉熵\ [
    \ sum_j P(z = j | \ psi,\ {(w_i,l_i)\})\ log P(z = j | \ psi)。
    \]
我有一个图表可帮助可视化在线过程。


请注意,如果您观察到特定实例的地面真理$ \ tilde z $,则更新工作模型,就好像$ P(z = j | \ psi)= 1_ {z = \ tilde z} $作为先验分布,并且分类器将更新为$ P(z = j | \ psi,\ {(w_i,l_i)\})= 1_ {z = \ tilde z} $。在这种情况下,分类器更新与``普通''逻辑回归相同,因此可以认为这是对人群数据进行逻辑回归的概括。

我总是将常量项功能添加到每个输入。因此,在没有项目特征的情况下,该算法与之前相同,除了它正在学习$ z $上的先验分布。太好了,这是一件值得指定的事情。但是,在具有项目功能的情况下,事情会变得更加有趣。如果有一个可以强烈表明地面真实性的特征(例如, lang = es 在Twitter资料上强烈地表明了西班牙裔种族),该模型可以潜在地识别出准确的工人,这些工人在标签上的每个项目上都与同龄人不同, 如果 工人在具有共同特征的物品上与其他工人同意。如果一个工作人员碰巧变得不幸并与多个不准确的工作人员一起完成多项任务,则可能会发生这种情况。当那些不准确的工人对其他比较模糊的项目的影响减小时,这才真正开始得到回报。

这是一个真实的例子。任务是预测Twitter个人资料的性别。要求机械土耳其人工作人员访问特定的个人资料,然后选择性别:男性,女性或两者都不选。 ``都不''主要用于像这样的组织的Twitter帐户 洛杉矶道奇队, 不必要 保罗。物品的功能可以通过以下方式获得 GET用户/查找 (请注意,所有这些功能对于Mechanical Turk工人都是显而易见的)。训练示例最终看起来像
A26E8CJMP5S4WN:2,A8H56XB9K7DB5:2,AU9LVYE38Q6S2:2,AHGJTOTIPCL8X:2 WONBOTTLES,180279525|firstname taste |restname this ? ?? |lang en |description weed girls life cool #team yoooooooo #teamblasian #teamgemini #teamcoolin #teamcowboys |utc_offset utc_offset_-18000 |profile sidebar_252429 background_1a1b1f |location spacejam'n in my jet fool
如果它看起来像Vowpal Wabbit,那是因为我再次撕掉了它们的输入格式,但是标签规范得到了丰富。特别是可以指定零个或多个worker:label对,以及一个可选的true标签(只是一个标签,没有worker)。这是训练集中的多次通过的样子。
initial_t = 10000
eta = 1.0
rho = 0.9
n_items = 10130
n_labels = 3
n_worker_bits = 16
n_feature_bits = 16
test_only = false
prediction file = (no output)
data file = (stdin)
cumul    since    cumul    since      example current current current  current
avg q    last     avg ce   last       counter   label predict ratings features
-0.52730 -0.52730 -0.35304 -0.35304         2      -1       0       4        7
-0.65246 -0.73211 -0.29330 -0.25527         5      -1       0       4       23
-0.62805 -0.60364 -0.33058 -0.36786        10      -1       1       4       13
-0.73103 -0.86344 -0.29300 -0.24469        19      -1       0       4       12
-0.76983 -0.81417 -0.25648 -0.21474        36      -1       0       4       20
-0.75015 -0.72887 -0.26422 -0.27259        69      -1       2       4       12
-0.76571 -0.78134 -0.25690 -0.24956       134      -1       2       4       37
-0.76196 -0.75812 -0.24240 -0.22752       263      -1       0       4       21
-0.74378 -0.72467 -0.25171 -0.26148       520      -1       2       4       12
-0.75463 -0.76554 -0.24286 -0.23396      1033      -1       2       2       38
-0.72789 -0.70122 -0.24080 -0.23874      2058      -1       0       4       30
-0.68904 -0.65012 -0.25367 -0.26656      4107      -1       2       4       25
-0.61835 -0.54738 -0.25731 -0.26097      8204      -1       0       4       11
-0.55034 -0.48273 -0.24362 -0.23001     16397      -1       2       3       12
-0.49055 -0.43083 -0.20390 -0.16423     32782      -1       2       3       29
-0.44859 -0.40666 -0.15410 -0.10434     65551      -1       2       4       12
-0.42490 -0.40117 -0.11946 -0.08477    131088      -1       0       4        9
-0.41290 -0.40090 -0.10018 -0.08089    262161      -1       2       4        9
-0.40566 -0.39841 -0.08973 -0.07927    524306      -1       0       4       33
-0.40206 -0.39846 -0.08416 -0.07858   1048595      -1       2       4       22
-0.40087 -0.39869 -0.08206 -0.07822   1620800      -1       0       4       18
applying deferred prior updates ... finished

gamma:
     \  ground truth
      |   0       1       2
label |
    0 | -1.0000 0.0023  0.0038
    1 | 0.0038  -1.0000 0.0034
    2 | 0.0038  0.0018  -1.0000
在我的笔记本电脑上生成该输出大约需要3分钟。如果那看起来像Vowpal Wabbit,那是因为我再次撕掉了它们的输出格式。前两列是EM辅助功能,类似于对数似然,因此,增加的数字表示工作人员模型能够更好地预测工作人员标签。接下来的两列是分类器的交叉熵,因此越来越多的数字表明分类器能够更好地根据项目特征预测地面事实的后验(相对于众包工作者标签)。

以上软件可从 Google代码存储库。叫做 弹奏钢琴,因为我发现使用众包工作者为分类器提供训练数据的过程让人联想到 冯内古特的反乌托邦,其中上一代人类大师级工匠的动作记录在磁带上,然后永久性地从工业生产中驱逐出去。马上 弹奏钢琴 只支持名义上的问题,但是我已经写了一些东西,因此希望将序数和多标签添加到同一可执行文件中会很容易。

2011年11月7日,星期一

在洛杉矶机器学习聚会上发表11/8/2011

如果你在附近, 随时停下来。主题是使用生成模型来处理众包数据。

2011年11月3日,星期四

人工智能与劳动力市场

机器学习会议通常会邀请来自机器学习之外但与机器学习有关的领域的从业者进行邀请演讲。我希望看到一位受邀的经济学家谈论有关人工智能将如何改变劳动力市场的当前最佳猜测。

当前的经济环境让人想起反乌托邦小说 钢琴演奏者在美国,富裕的工程师阶层与因自动化而流离失所的体力劳动阶层之间存在着巨大的失业和极端的收入不平等,这在美国颇受困扰。实际上,尽管失业率尚未恢复,但GDP已恢复到衰退前的水平,导致一些经济学家制定了 零边际产品工人假说。零MP假设的前提是,自从大衰退开始以来``与此同时,没有重大技术突破'',因此当工人被雇用时,他们的MP为零,但没人注意到。但是,正如NPR指出的那样, 技术正在淘汰熟练的工作。他们举了一个与我很接近的法律职业的例子:首先是因为我妻子是被解雇的律师,其次是因为我咨询了一家有兴趣在Vowpal Wabbit中使用LDA功能的电子发现公司。以提高他们的电子发现效率。我要说的是,自从大萧条(2007)开始以来,机器学习发生了技术变革,伴随着知识的扩散和开源工具包的出现。此外,由于经济好时机延迟了成本压力,因此可能尚未应用过去十年机器学习中的一些技术变革(取得了巨大的进步!)。因此,我怀疑工人以过时的方式流离失所,即正式成为国会议员,但由于技术变革而不再需要。

总的来说,我对技术和生产率的提高将为所有人带来更好的生活水平感到乐观。但是,美国最近的收入不平等历史表明,创造的财富并不一定在整个人口中公平分配。对于我们正在创造的人工智能未来而言,了解谁可能是劳动力市场的赢家和输家对机器学习社区而言将是一件大事。