2011年5月27日,星期五

双向重要性意识更新:第三部分

下次有人问时, “谁害怕非凸损失函数?”,我要举手。这个 二元模型 只是略微不凸,但事实证明,正确无误。

我下载了 书本交叉 数据集。排名是按序排列的,因此标准评估指标为 平均绝对误差。幸运的是,$ \ tau $分位数的损失也具有动力学的解析解决方案,因此我认为自己已经做好了。 $ \ tau $分位数的损失由\ [
l(p,y)= \开始{cases} \ tau(y-p)& y >p \\(1-\ tau)(p-y)&y \ leq p \ end {cases}。
\]当$ \ tau = 1/2 $时,这与平均绝对误差相同。

我将这种情况发送到了“可算账”数据集,但是在以下意义上它没有用。随着学习速度的提高,可能会表现出病理行为,例如渐进的验证损失趋于分散。尽管有这样一个事实,即重要性感知更新不能超出标签。我认为正在发生(基于printf)是有很多方法可以使当前示例中的损失变为零,并且其中一些方法涉及将大二元参数乘以小二元参数。不幸的是,这种组合不可能很好地推广。

$ L ^ 2 $正则化将有利于均等幅度的二进参数配置,而且幸运的是,如果仅对二进参数进行正则化,则存在$ \ tau $分位数损失(和铰链损失)的解析解。带正则化的动力学由\ [
\ begin {aligned}
a'(h)&=-\ eta b(h)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s( h)x)^ \ top x}-\ eta \ lambda a(h),\\
b'(h)&=-\ eta a(h)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s( h)x)^ \ top x}-\ eta \ lambda b(h),\\
s'(h)&= \ eta \ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s(h)x)^ \ top x},
\ end {aligned}
\]其中$ \ tau $分位数的损失具有解决方案\ [
\ begin {aligned}
a(h)&= e ^ {-\ eta \ lambda h} \ left(a_0 \ cosh(-s(h))+ b_0 \ sinh(-s(h))\ right),\\
b(h)&= e ^ {-\ eta \ lambda h} \ left(b_0 \ cosh(-s(h))+ a_0 \ sinh(-s(h))\ right),\\
s(小时)&= -\eta h \begin{cases} \tau & y >p \\(\ tau-1)和y \ leq p \ end {cases}。
\ end {aligned}
\]如果不进行正则化,则一旦$ p = y $,动力学就会停止。使用正则化不一定是正确的。如果$ \ lambda $足够大,则动态可以超出在正则化器上取得进展的标签。即使$ p = y $是吸引子,也可以在保持恒定预测的同时权衡线性参数(未正规化)与二进制参数。我忽略了那些奇怪的情况,只是在$ p = y $时停止更新。

所以我尝试了一下,但是它也没有用,但是换了一种方式。只要$ \ lambda $不为零,它就不会表现出具有高学习率的病理行为(这很好:这意味着减少学习和主动学习不会成为障碍)。另外,有可能在没有二元尺寸的情况下将训练集上的渐进式验证损失降低得更低。但是,这种改进不会转化为测试集。换句话说,它更适合训练数据,但不能很好地推广。

所以我实际上从 梅农和埃尔坎 为了比较。我发现在书本交叉数据集上也没有很好地概括。然后,我发现他们的论文中报告的评分,用户数量等与我的不符。我不确定结账数据集是怎么回事,所以我决定切换到 1百万个电影镜头 数据集。 Menon和Elkan方法确实在这里显示了一些提升,虽然没有论文中报道的那么大,但是另一方面,我并没有实现他们论文中所有的风吹草动,例如变量正则化和简化参数化。现在,我有了一个有望取得进展的数据集。关于机器学习的有趣的事情:当您知道应该做的事情时,要工作起来要容易得多:)

这就是我与1M电影镜头收视率的二进合表现。\ [
\ begin {array} {c | c | c}
\ mbox {模型}&\ mbox {测试集上的$ 0.5 $分位数损失}&\ mbox {评论} \\ \ hline
\ mbox {最佳常数}&\ mbox {0.428}&\ mbox {中位数为4} \\ \ hline
\ mbox {线性}&\ mbox {0.364}&\ mbox {预测为$ \ alpha_ {rid} + \ beta_ {tid} + c $} \\ \ hline
\ mbox {Dyadic $ k = 1 $}&\ mbox {0.353}&\ mbox {预测为$ a_ {rid} ^ \ top b_ {tid} + \ alpha_ {rid} + \ beta_ {tid} + c $} \\ \ hline
\ mbox {Dyadic $ k = 2 $}&\ mbox {0.351}&\ mbox {像以前一样,以$ a_ {rid},b_ {tid} $作为2个向量} \\ \ hline
\ mbox {Dyadic $ k = 5 $}&\ mbox {0.349}&\ mbox {像以前一样,只有5个向量而不是2个向量}
\ end {array}
\]再说一次, 牛肉在哪里? 最佳常数上的大多数预测能力都来自线性分量。从Menon和Elkan论文的表3中可以看出,它们的潜在维数也没有显着提升。

2011年5月20日,星期五

双向重要性意识更新:第二部分

实施的目的和目的

原来我在我讨论过的二元模型 以前的帖子 比通常使用的要简单一些。更典型的模型结构是\ [
p = a ^ \ top b + a ^ \ top 1 + 1 ^ \ top b + w ^ \ top x
\]但是更改了变量\ [
\ begin {aligned}
\ tilde a(h)&= a(h)+ 1 \\
\波浪号b(h)&= b(h)+ 1 \\
\ tilde p&= p + 1 ^ \顶部1
\ end {aligned}
\]恢复原始方程式。这也具有使梯度动力学的鞍点从零移开的效果。但是,将所有模型参数初始化为零仍然存在问题,因为没有任何东西可以破坏模型参数之间的对称性。 (我选择在第一次更新时对二进参数施加较小的扰动来破坏对称性。)在下文中,我将引用原始方程式以简化说明,但实际上使用变量的更改。

数值计算特定步长\ [
p(s)= a_0 ^ \ top b_0 \ cosh(2 s)-(|| a_0 || ^ 2 + || b_0 || ^ 2)\ cosh(s)\ sinh(s)+ x ^ \ top( w-sx)
\]和隐式定义的逆$ p ^ {-1}(y)$显得很重要。这种形式非常方便,因为只需要$ a_0 $和$ b_0 $的范数及其内部乘积来模拟特定步骤。在软件方面:损失函数的接口需要增加两个额外的标量输入($ || a_0 || ^ 2 + || b_0 || ^ 2 $和$ a_0 ^ \ top b_0 $;以及变量的变化,$ 1 ^ \ top 1 $)。

在向前的方向上,$ p(s)$是 灾难性的取消 因此在计算时需要格外小心。一旦解决了这个问题,反向$ p ^ {-1}(y)$的行为通常就很好,可以使用 牛顿法回溯线搜索。但是,当$ a ^ \ top b \ approx \ frac {1} {2}(|| a_0 || ^ 2 + || b_0 || ^ 2)$和$ x \ approx 0 $时,精度问题占主导地位。本质上,当没有线性特征($ x \ approx 0 $)时,二进角项位于双对角线附近(例如,$ a_0 \ approx \ pm b_0 $),并且预测是错误的符号,那么它花费的时间非常大$ s $更改预测的符号。幸运的是,在模型中放置恒定的线性特征可确保$ x ^ \ top x \ geq 1 $。在这种情况下,遇到超对角线本质上意味着不学习二进位模型参数,但是希望将二元组在训练序列中``充分随机地''配对,这在实践中不是问题。

函数$ p ^ {-1}(y)$直接用于增强铰链损耗的边界。它也与最小重要性权重相关,该最小重要性权重将导致预测改变符号,即主动学习期间出现的数量。 (在线性模型的主动学习中会出现这种情况;尚不清楚同一理论是否适用于二元模型,但我希望在``边界附近''进行采样并使用重要性权重会做一些合理的事情。)当标签为$ y $时导致模型输出为$ x $的权重由$ h_ {min}(x,y)= s ^ {-1}(p ^ {-1}(x); y给出)$。利用变量技巧的分离 Karampatziakis和Langford,更新函数$ s(h; y)$可以通过\ [求解而无需求解初始值问题。
\ begin {aligned}
s'(h; y)&= \eta \frac{\partial l (p, y)}{\partial p}\biggr|_{p = p (s)} = \eta F (s; y), \\
dh &= \frac{1}{\eta F (s; y)} ds \\
s ^ {-1}(x; y)&= \frac{1}{\eta} \int_{0}^x \frac{d s}{F (s; y)}.
\ end {aligned}
\]对于铰链损失,可以归结为$ h_ {min}(x,y)= -p ^ {-1}(x)/(\ eta y)$;对于其他损失,必须在数值上进行积分,但是出于主动学习的目的,大概只需要进行粗略的数值积分。

它行得通吗?

好吧,有很多方法可以回答这个问题:)

我有一些二元数据,与来自Mechanical Turk HIT的结果相对应,其中我要求用户根据其公开资料猜测Twitter用户的种族:共有10,000个任务和5个评估者,总共50,000个数据点。我将数据拆分,在大部分数据上进行训练(15/16分),在其余数据上进行测试(1/16分)。我仅将标识符用作功能,例如,输入行可能看起来像
2 2 |评分器r_2737 |任务t_89 | id r_2737 t_89
对于具有一个潜在维度的模型
2 2 |评分器r_2737 r2_2737 |任务t_89 t2_89 | id r_2737 t_89
如果输入看起来很有趣,那是因为现在我不为点积在一起的要素空间发出线性要素(在这种情况下,“评估者”和“任务”是点积的)。这违反了 干燥 所以我可能会改变这一点。 (此外,我不必重新生成输入来更改潜在维数,因此需要更改。)

我的 标称提取物 我整理来处理这些数据的模型类似于具有一个潜在维度的二进模型。使用上述框架,我可以轻松添加其他潜在维度,这让人联想到 Welinder等。等 多维嵌入。但是,这里的目标有些不同:在这种情况下,想法是提取``基本事实'',即任务的``真实''种族的概率分布。这里的目标仅仅是预测评估者将分配给任务的标签。这与任务的真实基础标签有关,但也与评估者的属性有关。

顺便说一句,在一定程度上可以根据训练集标签可靠地预测测试集标签,这意味着我为标签付出了太多钱,因为测试集中的标签是多余的。在此问题上使用主动学习技术可能会减轻冗余。然而,相反,这可能会奖励评分者随机回答更多工作。

我随机进行训练/测试拆分,在相同的训练集上训练每个模型,并在相同的测试集上测试每个模型。这个想法是使两个数据集之间的单个评分者和单个任务(但不是成对;每对最多出现一次)之间有一些(配对!)配对。我正在使用 评分过滤树 减少将多类简化为二进制,然后将铰链损失用于二进制分类器。这是一些结果。 \ [
\ begin {array} {c | c | c}
\ mbox {模型}&\ mbox {0/1测试集损失}(\ pm 0.007)&\ mbox {评论} \\ \ hline
\ mbox {最佳常数}&\ mbox {0.701}&\ mbox {最频繁发生的种族}大约是\ mbox {当时的30 %%} \\ \ hline
\ mbox {线性}&\ mbox {0.214}&\ mbox {预测为} \ alpha_ {rid} + \ beta_ {tid} + c \\ \ hline
\ mbox {Dyadic} k = 1&\ mbox {0.198}&\ mbox {预测是} a_ {rid} ^ \ top b_ {tid} + \ alpha_ {rid} + \ beta_ {tid} + c \\ \ hline
\ mbox {Dyadic} k = 2&\ mbox {0.198}&\ mbox {与之前的} a_ {rid},b_ {tid} \ mbox {作为2个向量}一样\\ \ hline
\ mbox {二进位} k = 3&\ mbox {0.199}&\ mbox {像以前一样,只有3个向量而不是2个向量}
\ end {array}
\]好吧,这并没有使我的袜子破灭,差异不是统计学上显着的(使用伪造的二项式方差估计)。当添加单个潜在维度时,似乎会产生一点点汁液,然后便会排出。回想起来,这是测试数据集的不佳选择,因为评估者缺乏对抗行为,重要的变量是评估者偏差和真实任务标签,两者都可以通过线性模型很好地捕获。顺便说一下,我选择了所有学习参数以为线性模型提供最佳结果,然后将其重新用于其他模型。

另一方面,从操作上看,事情看起来很有希望。首先,速度损失在二元$ k = 3 $和线性之间是很小的(80秒与50秒进行160次通过)。由于在二元$ k = 3 $情况下输入记录较大,因此我尝试在二元$ k = 3 $输入数据上训练线性模型,在这种情况下,差异消失了。我不认为区别在于解析;而是我怀疑每行访问更多的权重值,这导致更多的缓存丢失。无论如何,对于相等数量的有效特征,计算$ p ^ {-1}(y)$的开销并不明显。当然,铰链损耗对动力学有解析的解决方案。对于其他损失函数,我必须解决一个初始值问题,这可能会大大降低速度。

其次,关于学习率的设置,结果是可靠的。就最大程度地减少测试集损失而言,绝对有一个最佳的学习率,但是当我将学习率变化超过4个数量级时,就从来没有任何病理行为。也许在更复杂的模型中会遇到麻烦,或者在使用其他损失函数时(较大的学习率可能会使在数值上求解初始值问题变得复杂)。另外,我还没有实现正则化,这可能是使更复杂的模型工作所必需的。

因此,下一步是将其应用于Menon和Elkan中提到的某些测试数据集,例如 书本交叉 数据集并实现其他损失函数,看看我是否得到了不好的结果(由于用一维ODE逼近多维ODE),学习率的不稳定性(解决初值问题时上升)或吞吐速度令人无法接受(由于每次更新都包含所有其他数字)。

2011年5月13日,星期五

双向重要性感知更新

所以最近我谈到 二元建模,以及它看起来如何与目前在vowpal wabbit内部实现的模型非常接近。但是,由于``明显较小''的差异,会出现一些皱纹。

vowpal中的基本算法本质上是 GLM 用优化 新元。引擎盖下的巧妙技巧之一是 重要体重感知更新。关键的观察结果是,对于GLM,特定示例的所有梯度都指向同一方向,并且仅在幅度上有所不同,即,如果预测为$ p = w ^ \ top x $,则$ \ nabla_w l(p, y)= x \ frac {\ partial l} {\ partial p} | _ {p = w ^ \ top x} $。 Karampatziakis和Langford利用此方法通过求解一个常微分方程来模拟大量小梯度步的极限。产生的更新具有三个不错的属性。第一个是安全性:对于可能超出标签的损失函数,重要性感知更新将永远不会超出标签,这与渐变的天真缩放不同。第二个是不变性:重要性加权为$ w_1 $和$ w_2 $的两个顺序更新等效于重要性加权为$ w_1 + w_2 $的单个更新。安全性使SGD的结果对准确选择学习率的敏感性降低;而不变性对于利用重要性权重的减少非常重要。什么是第三个不错的酒店?事实证明,对于各种常用损失函数都有封闭式更新,因此,重要性感知更新的计算成本较低。

二元模型不是GLM,但是某些原理仍然适用。考虑一个简单的二元模型,\ [
\ begin {aligned}
p&= a ^ \ top b,\\
\ nabla_a l(p,y)&= b \ frac {\ partial l} {\ partial p} | _ {p = a ^ \ top b},\\
\ nabla_b l(p,y)&= a \ frac {\ partial l} {\ partial p} | _ {p = a ^ \ top b}。
\ end {aligned}
\]所有的梯度都不指向相同的方向,但是尽管如此,尝试创建重要性加权感知更新仍会产生一对方程,\ [
\ begin {aligned}
a'(h)&=-\ eta b(h)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)},\\
b'(h)&=-\ eta a(h)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)}。
\ end {aligned}
\] Mathematica只能为我解决铰链丢失问题;在线性状态下,解看起来像\ [
\ begin {aligned}
a(h)&= a_0 \ cosh(\ eta h y)+ b_0 \ sinh(\ eta h y),\\
b(h)&= b_0 \ cosh(\ eta h y)+ a_0 \ sinh(\ eta h y),
\ end {aligned}
\],然后只要有人到达$ a(h)^ \ top b(h)= y $的边界,就不会再有变化。 Mathematica还可以分析得出最小的$ h_ {min} $,其中$ a(h)^ \ top b(h)= y $并且计算起来也不算太糟(涉及$ \ cosh ^ {-1} $和平方根);尽管当$ a_0 \ approx b_0 $时需要一些注意(有系列扩展可用)。

此更新具有所有三个理想的属性。产品碰到标签后立即停止,以确保安全。不变性成立,可以通过利用等式$ \ cosh(a + b)= \ cosh(a)\ cosh(b)+ \ sinh(a)\ sinh(b)$来证明线性不变性。最后,该更新的计算成本相对较低。

如果用$ p = w ^ \ top x + a ^ \ top b $代替预测,则故事基本上保持不变。方程是\ [
\ begin {aligned}
a'(h)&=-\ eta b(h)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s( h)x)^ \ top x},\\
b'(h)&=-\ eta a(h)\ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s( h)x)^ \ top x},\\
s'(h)&= \ eta \ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s(h)x)^ \ top x},
\ end {aligned}
\]对于铰链丢失有解决方法\ [
\ begin {aligned}
a(h)&= a_0 \ cosh(\ eta h y)+ b_0 \ sinh(\ eta h y),\\
b(h)&= b_0 \ cosh(\ eta h y)+ a_0 \ sinh(\ eta h y),\\
s(小时)&= -\eta h y.
\ end {aligned}
\]但是$ h_ {min} $的计算更为复杂;我无法获得解析表达式,因此很遗憾,需要一维求根,\ [
\ text {求解} \ left [\ frac {1} {2} \ left(|| a_0 || ^ 2 + || b_0 || ^ 2 \ right)\ sinh(2 \ eta hy)+ a ^ \ top b \ cosh(2 \ eta hy)+ x ^ \ top(\ eta hx y + w)= y,h \ right]。
\]这可能会使更新没有资格被视为``便宜的计算''。

总的来说,我认为此更新可能与二元分类问题有关,因为铰链丢失将是一个合理的选择。从理论上讲,分位数损失也可以接受,但其他损失则不行。

当我对从不同起点开始的一维二元更新进行$ a(h)$和$ b(h)$的参数图绘制时,我得到了一张很酷的图片,我想发布。这让我想起了科幻小说之类的东西。
通过数值积分将上述方程式用于不同的损失会产生相似的图像,尽管对于某些损失(例如逻辑损失)没有边界,所以耐克不断前进。这表明铰链损耗情况捕获了更新的基本曲率,但是由于损耗的非线性,对于不同的损耗,更新的大小是不同的。这进一步暗示了像\ [
\ begin {aligned}
a(h)&= a_0 \ cosh(-s(h))+ b_0 \ sinh(-s(h)),\\
b(h)&= b_0 \ cosh(-s(h))+ a_0 \ sinh(-s(h)),\\
s'(h)&= \ eta \ frac {\ partial l} {\ partial p} \ biggr | _ {p = a(h)^ \ top b(h)+(w-s(h)x)^ \ top x}。
\ end {aligned}
\]因此,这里有一些有关此黑客的猜测。首先猜测:这是一个下降方向,因为如果损耗在$ h = 0 $处线性化,我将得到上述等式重现的铰链损耗更新。第二个猜测:此更新是不变的,因为通过替换,我可以将其简化为一阶ODE,并且cosh和sinh不会破坏损失函数的连续微分性。第三个猜测:此更新具有安全性。

当然,此更新涉及对一维ODE进行数值积分,因此在实践中可能会过于昂贵。基本上,hack将多维ODE简化为一维ODE,这在计算上是节省的,但绝对不如封闭形式那么酷。

要了解不变性为何起作用,请考虑在使用重要性权重$ h_1 $和$ h_2 $进行两次连续更新后,$ a $的值是什么,\ [
\ begin {aligned}
a(p_1,h_2)&= a(p_0,h_1)\ cosh(-s(p_1,h_2))+ b(p_0,h_1)\ sinh(-s(p_1,h_2)),\\
p_0&= a_0 ^ \ top b_0 + w ^ \ top x \\
p_1&= a(p_0,h_1)^ \ top b(p_0,h_1)+(w-s(p_0,h_1)x)^ \ top x \\
\ end {aligned}
\]明确了对初始预测$ p_0 $和中间预测$ p_1 $的依赖性。现在注意\ [
\ begin {aligned}
a(p_0,h_1)&= a_0 \ cosh(-s(p_0,h_1))+ b_0 \ sinh(-s(p_0,h_1)),\\
b(p_0,h_1)&= b_0 \ cosh(-s(p_0,h_1))+ a_0 \ sinh(-s(p_0,h_1))。 \\
\ end {aligned}
\]代入上述并使用双曲加法恒等式得出\ [
a(p_1,h_2)= a_0 \ cosh(-s(p_0,h_1)-s(p_1,h_2))+ b_0 \ sinh(-s(p_0,h_1)-s(p_1,h_2)),
\]因此,如果\ [
s(p_0,h_1 + h_2)= s(p_0,h_1)+ s(p_1,h_2),
\] 然后 \[
a(p_0,h_1 + h_2)= a(p_1,h_2),
\],同样也适用于$ b $。

2011年5月10日,星期二

成本敏感的多标签:观察

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

2011年5月6日,星期五

潜在因素与沃帕尔兔

有一篇不错的论文 梅农和埃尔坎 关于具有潜在特征的二元预测。它关心正确的事情:易于实施,整合多种信息源的能力以及可伸缩性。该模型可以被认为是 多项式对数矩阵分解.

在没有附带信息的情况下,以二进制形式进行描述是最容易的。在这种情况下,基本上是二项输入$ x =(r,c)$,\ [
\ log \ frac {p(y = 1 | x,w)} {p(y = 0 | x,w)} = \ alpha ^ T_r \ beta_c,
\]其中$ \ alpha $是与$ r $相关的$ k $潜在因子的向量,而$ \ beta $是与$ c $相关的$ k $潜在因子的向量。 $ r $和$ c $是此处的标识符,例如,用户ID和电影ID,用户ID和广告ID等。

我现在几乎可以在vowpal wabbit中做到这一点。假设模型中有两个潜在维($ k = 2 $)。训练数据$(y,(r,c))$将通过
y | alpha潜在_0_r潜在_1_r | beta潜在_0_c潜在_1_c
例如对于训练基准$(1,(16,432))$,
1 | alpha潜在_0_16潜在_1_16 | beta潜在_0_432潜在_1_432
然后选择--quadratic ab和--loss logistic。不幸的是,这没有做正确的事。首先,它创建了一些额外的功能(它是外部产品,而不是内部产品)。其次,这些额外的功能具有自己独立的权重,而在模型中,权重是各个权重的乘积。可能的解决方案是在vowpal中添加--dotproduct选项,该选项将采用两个名称空间并模拟与其内部乘积相对应的功能(在这种情况下,输入中功能的顺序很重要)。

如果到目前为止,您可能会看到如何将与dyad相关联的附加功能$ s(x)$添加到另一个命名空间中,以通过辅助信息来扩展模型。
y | alpha潜在_0_r潜在_1_r | beta潜在_0_c潜在_1_c |侧面特征...
同样,很容易合并与每个组件相关的辅助信息,这些辅助信息不会放置在alpha和beta命名空间中,以免被--dotproduct占用(实际上,对于与组件相关的典型辅助信息,--quadratic组件方面的信息将是合理的)。请注意,作者报告的更好的结果是,先学习潜在模型,固定潜在权重,然后学习与辅助信息相关的权重。

对于多值数据,作者使用多项式logit,但我怀疑 评分过滤树 具备物流基础的学习者可以完成工作。

最后,作者建议进行正则化对于取得良好的结果是必要的。可能我可以使用``仅一次通过训练数据''正则化样式来摆脱困境。