显示带有标签的帖子 开源的. 显示所有帖子
显示带有标签的帖子 开源的. 显示所有帖子

2015年7月23日,星期四

极端分类代码发布


极端分类讲习班ICML 2015 今年是爆炸。我们从强势开始,Manik Varma演示了如何使用商用笔记本电脑绕过其他学习算法。我们取得了不错的成绩,Alexandru Niculescu通过“反对另一种合理的选择”推理。看看 整个程序!

对于即将举行的活动,ECML 2015将举办一个名为“ 大的多目标预测。此外,还有关于NIPS 2015研讨会的传言。

同时,我已经 推送到github 极端的参考实现 嵌入分类 我和Nikos一直在研究的技术。这里有两个非常简单的想法在起作用。首先是使用 特定矩阵的(随机)SVD 作为标签嵌入,其次是对内核计算机的随机近似的使用。

2014年4月25日,星期五

判别表征学习技术

我和Nikos开发了一种使用数值线性代数技术学习判别特征的技术 效果很好 对于一些问题。基本思想如下。假设您遇到一个多类问题,即训练数据的形式为$ S = \ {(x,y)| x \ in \ mathbb {R} ^ d,y \ in \ {1,\ ldots,k \} \} $。 $ x $是原始表示形式(功能),您想学习有助于分类器的新功能。在深度学习中,此问题通过定义$ x $的多级参数非线性和优化参数来解决。深度学习很棒,但是由此产生的优化问题却极具挑战性,尤其是在分布式环境中,因此我们一直在寻找更适合计算的东西。

首先考虑两类情况。想象一下寻找形式为$ \ phi(w ^ \ top x)$的特征,其中$ w \ in \ mathbb {R} ^ d $是一个“weight vector”$ \ phi $是某种非线性。定义良好功能的简单标准是什么?一个想法是该功能在一个类上具有较小的平均值,而在另一类上具有较大的平均值。假设$ \ phi $为非负数,则建议最大化比率\ [
w ^ * = \ arg \ max_w \ frac {\ mathbb {E} [\ phi(w ^ \ top x)| y = 1]} {\ mathbb {E} [\ phi(w ^ \ top x)| y = 0]}。
\]对于$ \ phi(z)= z ^ 2 $的特定选择,这是易处理的,因为它会导致 瑞利商 在两个有条件的第二时刻之间,\ [
w ^ * = \ arg \ max_w \ frac {w ^ \ top \ mathbb {E} [x x ^ \ top | y = 1] w} {w ^ \ top \ mathbb {E} [x x ^ \ top | y = 0] w},
\]可以通过广义特征值分解来解决。广义特征值问题已经在机器学习和其他领域进行了广泛的研究,并且上述想法与许多其他建议(例如, 费希尔LDA),但它是不同的,而且在经验上更有效。我将引导您参考该论文进行更深入的讨论,但是我会提到在论文被接受之后,有人指出了与 CSP,这是时间序列分析中的一种技术(参见 传道书1:4-11)。

此过程产生的功能通过了气味测试。例如,从上的原始像素表示开始 mnist, the 权重向量s can be visualized as images; the first 权重向量 for discriminating 3 vs. 2 looks like
看起来像笔触,参见图1D 兰萨托等等

我们在本文中还提出了其他一些意见。首先是,如果相关的广义特征值较大,则瑞利商的多个孤立极小值将很有用,即可以从瑞利商中提取多个特征。第二个是,对于适度的$ k $,我们可以独立提取每个类对的特征,并使用所有得到的特征获得良好的结果。第三是所得方向具有附加结构,该附加结构不能被平方非线性完全捕获,这会激发(单变量)基函数展开。第四,一旦原始表示增加了其他功能,就可以重复该过程,有时还会产生其他改进。最后,我们可以将其与随机特征图组合起来,以近似RKHS中的相应操作,有时还会产生其他改进。在本文中,我们还提出了一个抛弃式的评论,即在映射简化样式的分布式框架中轻松完成计算类条件第二矩矩阵的操作,但这实际上是我们朝这个方向进行探索的主要动机,但事实并非如此。不太适合本文的论述,因此我们不再强调它。

将上述想法与Nikos的多类别预处理梯度学习结合起来, 以前的帖子,导致出现以下Matlab脚本,该脚本在(排列不变)mnist上获得91个测试错误。注意:您需要下载 mnist_all.mat 从Sam Roweis的网站运行。
功能 calgevsquared

more off;
clear all;
close all;

start=tic;
load('mnist_all.mat');
xxt=[train0; train1; train2; train3; train4; train5; ...
     train6; train7; train8; train9];
xxs=[test0; test1; test2; test3; test4; test5; test6; test7; test8; test9];
kt=single(xxt)/255;
ks=single(xxs)/255;
st=[size(train0,1); size(train1,1); size(train2,1); size(train3,1); ...
    size(train4,1); size(train5,1); size(train6,1); size(train7,1); ...
    size(train8,1); size(train9,1)];
ss=[size(test0,1); size(test1,1); size(test2,1); size(test3,1); ... 
    size(test4,1); size(test5,1); size(test6,1); size(test7,1); ...
    size(test8,1); size(test9,1)];
paren = @(x, varargin) x(varargin{:});
yt=zeros(60000,10);
ys=zeros(10000,10);
I10=eye(10);
lst=1;
for i=1:10; yt(lst:lst+st(i)-1,:)=repmat(I10(i,:),st(i),1); lst=lst+st(i); end
lst=1;
for i=1:10; ys(lst:lst+ss(i)-1,:)=repmat(I10(i,:),ss(i),1); lst=lst+ss(i); end

clear i st ss lst
clear xxt xxs
clear train0 train1 train2 train3 train4 train5 train6 train7 train8 train9
clear test0 test1 test2 test3 test4 test5 test6 test7 test8 test9

[n,k]=size(yt);
[m,d]=size(ks);

gamma=0.1;
top=20;
for i=1:k
    ind=find(yt(:,i)==1);
    kind=kt(ind,:);
    ni=length(ind);
    covs(:,:,i)=double(kind'*kind)/ni;
    clear ind kind;
end
filters=zeros(d,top*k*(k-1),'single');
last=0;
threshold=0;
for j=1:k
    covj=squeeze(covs(:,:,j)); l=chol(covj+gamma*eye(d))';
    for i=1:k
        如果 j~=i
            covi=squeeze(covs(:,:,i));
            C=l\covi/l'; CS=0.5*(C+C'); [v,L]=eigs(CS,top); V=l'\v;
            take=find(diag(L)>=threshold);
            batch=length(take);
            fprintf('%u,%u,%u ', i, j, batch);
            filters(:,last+1:last+batch)=V(:,take);
            last=last+batch;
        end
    end
    fprintf('\n');
end

clear covi covj covs C CS V v L

% NB: augmenting kt/ks with .^2 terms is very slow 和 doesn't help

filters=filters(:,1:last);
ft=kt*filters;
clear kt;
kt=[ones(n,1,'single') sqrt(1+max(ft,0))-1 sqrt(1+max(-ft,0))-1];
clear ft;
fs=ks*filters;
clear ks filters;
ks=[ones(m,1,'single') sqrt(1+max(fs,0))-1 sqrt(1+max(-fs,0))-1];
clear fs;

[n,k]=size(yt);
[m,d]=size(ks);

for i=1:k
    ind=find(yt(:,i)==1);
    kind=kt(ind,:);
    ni=length(ind);
    covs(:,:,i)=double(kind'*kind)/ni;
    clear ind kind;
end

filters=zeros(d,top*k*(k-1),'single');
last=0;
threshold=7.5;
for j=1:k
    covj=squeeze(covs(:,:,j)); l=chol(covj+gamma*eye(d))';
    for i=1:k
        如果 j~=i
            covi=squeeze(covs(:,:,i));
            C=l\covi/l'; CS=0.5*(C+C'); [v,L]=eigs(CS,top); V=l'\v;
            take=find(diag(L)>=threshold);
            batch=length(take);
            fprintf('%u,%u,%u ', i, j, batch);
            filters(:,last+1:last+batch)=V(:,take);
            last=last+batch;
        end
    end
    fprintf('\n');
end
fprintf('gamma=%g,top=%u,threshold=%g\n',gamma,top,threshold);
fprintf('last=%u filtered=%u\n', last, size(filters,2) - last);

clear covi covj covs C CS V v L

filters=filters(:,1:last);
ft=kt*filters;
clear kt;
kt=[sqrt(1+max(ft,0))-1 sqrt(1+max(-ft,0))-1];
clear ft;
fs=ks*filters;
clear ks filters;
ks=[sqrt(1+max(fs,0))-1 sqrt(1+max(-fs,0))-1];
clear fs;

trainx=[ones(n,1,'single') kt kt.^2];
clear kt;
testx=[ones(m,1,'single') ks ks.^2];
clear ks;

C=chol(0.5*(trainx'*trainx)+sqrt(n)*eye(size(trainx,2)),'lower');
w=C'\(C\(trainx'*yt));
pt=trainx*w;
ps=testx*w;

[~,trainy]=max(yt,[],2);
[~,testy]=max(ys,[],2);

for i=1:5
        xn=[pt pt.^2/2 pt.^3/6 pt.^4/24];
        xm=[ps ps.^2/2 ps.^3/6 ps.^4/24];
        c=chol(xn'*xn+sqrt(n)*eye(size(xn,2)),'lower');
        ww=c'\(c\(xn'*yt));
        ppt=SimplexProj(xn*ww);
        pps=SimplexProj(xm*ww);
        w=C'\(C\(trainx'*(yt-ppt)));
        pt=ppt+trainx*w;
        ps=pps+testx*w;

        [~,yhatt]=max(pt,[],2);
        [~,yhats]=max(ps,[],2);
        errort=sum(yhatt~=trainy)/n;
        errors=sum(yhats~=testy)/m;
        fprintf('%u,%g,%g\n',i,errort,errors)
end
fprintf('%4s\t', 'pred');
for true=1:k
        fprintf('%5u', true-1);
end
fprintf('%5s\n%4s\n', '!=', 'true');
for true=1:k
        fprintf('%4u\t', true-1);
        trueidx=find(testy==true);
        for predicted=1:k
                predidx=find(yhats(trueidx)==predicted);
                fprintf('%5u', sum(predidx>0));
        end
        predidx=find(yhats(trueidx)~=true);
        fprintf('%5u\n', sum(predidx>0));
end

toc(start)

end

% http://arxiv.org/pdf/1309.1541v1.pdf
function X = SimplexProj(Y)
  [N,D] = size(Y);
  X = sort(Y,2,'descend');
  Xtmp = bsxfun(@times,cumsum(X,2)-1,(1./(1:D)));
  X = max(bsxfun(@minus,Y,Xtmp(sub2ind([N,D],(1:N)',sum(X>Xtmp,2)))),0);
end
当我在台式机上运行它时
>> calgevsquared
2,1,20 3,1,20 4,1,20 5,1,20 6,1,20 7,1,20 8,1,20 9,1,20 10,1,20 
1,2,20 3,2,20 4,2,20 5,2,20 6,2,20 7,2,20 8,2,20 9,2,20 10,2,20 
1,3,20 2,3,20 4,3,20 5,3,20 6,3,20 7,3,20 8,3,20 9,3,20 10,3,20 
1,4,20 2,4,20 3,4,20 5,4,20 6,4,20 7,4,20 8,4,20 9,4,20 10,4,20 
1,5,20 2,5,20 3,5,20 4,5,20 6,5,20 7,5,20 8,5,20 9,5,20 10,5,20 
1,6,20 2,6,20 3,6,20 4,6,20 5,6,20 7,6,20 8,6,20 9,6,20 10,6,20 
1,7,20 2,7,20 3,7,20 4,7,20 5,7,20 6,7,20 8,7,20 9,7,20 10,7,20 
1,8,20 2,8,20 3,8,20 4,8,20 5,8,20 6,8,20 7,8,20 9,8,20 10,8,20 
1,9,20 2,9,20 3,9,20 4,9,20 5,9,20 6,9,20 7,9,20 8,9,20 10,9,20 
1,10,20 2,10,20 3,10,20 4,10,20 5,10,20 6,10,20 7,10,20 8,10,20 9,10,20 
2,1,15 3,1,20 4,1,20 5,1,20 6,1,20 7,1,20 8,1,20 9,1,20 10,1,20 
1,2,20 3,2,20 4,2,20 5,2,20 6,2,20 7,2,20 8,2,20 9,2,20 10,2,20 
1,3,20 2,3,11 4,3,17 5,3,20 6,3,20 7,3,19 8,3,18 9,3,18 10,3,19 
1,4,20 2,4,12 3,4,20 5,4,20 6,4,12 7,4,20 8,4,19 9,4,15 10,4,20 
1,5,20 2,5,12 3,5,20 4,5,20 6,5,20 7,5,20 8,5,16 9,5,20 10,5,9 
1,6,18 2,6,13 3,6,20 4,6,12 5,6,20 7,6,18 8,6,20 9,6,13 10,6,18 
1,7,20 2,7,14 3,7,20 4,7,20 5,7,20 6,7,20 8,7,20 9,7,20 10,7,20 
1,8,20 2,8,14 3,8,20 4,8,20 5,8,20 6,8,20 7,8,20 9,8,20 10,8,12 
1,9,20 2,9,9 3,9,20 4,9,15 5,9,18 6,9,11 7,9,20 8,9,17 10,9,16 
1,10,20 2,10,14 3,10,20 4,10,20 5,10,14 6,10,20 7,10,20 8,10,12 9,10,20 
gamma=0.1,top=20,threshold=7.5
last=1630 filtered=170
1,0.0035,0.0097
2,0.00263333,0.0096
3,0.00191667,0.0092
4,0.00156667,0.0093
5,0.00141667,0.0091
pred        0    1    2    3    4    5    6    7    8    9   !=
true
   0      977    0    1    0    0    1    0    1    0    0    3
   1        0 1129    2    1    0    0    1    1    1    0    6
   2        1    1 1020    0    1    0    0    6    3    0   12
   3        0    0    1 1004    0    1    0    2    1    1    6
   4        0    0    0    0  972    0    4    0    2    4   10
   5        1    0    0    5    0  883    2    1    0    0    9
   6        4    2    0    0    2    2  947    0    1    0   11
   7        0    2    5    0    0    0    0 1018    1    2   10
   8        1    0    1    1    1    1    0    1  966    2    8
   9        1    1    0    2    5    2    0    4    1  993   16
Elapsed time is 186.147659 seconds.
这是一个很好的混淆矩阵,可与(置换不变)mnist上的最新深度学习结果相提并论。在本文中,我们报告的数字稍差一些(96个测试错误),因为对于一篇论文,我们必须通过对训练集进行交叉验证来选择超参数,而不是像博客文章那样选择超参数。

此处所述的技术实际上仅对超薄设计矩阵有用(即,有很多示例,但没有太多特征):如果原始特征维数太大(例如,$>10 ^ 4 $)比单纯使用标准广义特征求解器变得缓慢或不可行,并且还需要其他技巧。此外,如果类数太大而不是解决$ O(k ^ 2)$广义特征值问题,那也是不合理的。我们正在努力解决这些问题,我们也很高兴将此策略扩展到结构化预测。希望我们在接下来的几届会议上能有更多的话要说。

2014年2月17日,星期一

机器学习狗屋

这是关于 角色扮演 发布。当我发表这篇文章时,我不得不使用次优的优化策略,因为 尼科斯 仍在完善 优越策略。现在,他同意做一个客座帖子,详细介绍更好的技术。

机器学习狗屋

大约一年前 深卡卡德 在雷德蒙访问我们。他来谈谈他在使用矩量法而不是最大似然法估算模型(例如高斯模型和潜在狄利克雷分配的混合模型)方面的出色工作。 Sham喜欢简单而强大的算法。矩量法就是这样的一个例子:您不必担心局部最小值,初始化等等。今天,我要谈谈我与Sham(和 阿列克格雷格)。

当Sham拜访时,我刚从研究生院毕业,并且主要处理了将示例表示为高维稀疏向量的问题。当时,我不完全欣赏他坚持他所说的话“处理数据中的相关性”。您知道,Sham已开始探索一系列非常不同的问题。来自图像,音频和视频的数据是密集的,而不是高维的。即使数据名义上是高维的,数据矩阵的特征值也会迅速衰减,我们可以减小维数(例如使用随机SVD / PCA),而不会影响性能。对于文本问题根本不是这样。

这对学习算法有什么影响?首先,理论表明,对于这些病态问题(在线),一阶优化器将缓慢收敛。在实践中,情况甚至更糟。这些方法不仅需要多次通过,而且根本无法达到二阶优化方法所能达到的测试精度。在尝试之前,我一直不相信。但是二阶优化可能会很慢,因此在本文中,我将描述两种快速,健壮且没有(与优化相关的)调整参数的算法。我还将探讨一种解决高维问题的方法。两种算法每次更新都花费$ O(d ^ 2k)$,它们的收敛不依赖于条件数$ \ kappa $。这比标准二阶算法每次更新所需的时间$ O(d ^ 3k ^ 3)$便宜得多。另一方面,一阶算法每次更新需要$ O(dk)$,但它们的收敛性取决于$ \ kappa $,因此,在条件数较大时,以下方法更可取。

我们将关注mutliclass(和multilabel)分类,因为这类问题具有我们将要利用的特殊结构。首先,假设我们要拟合一个\ [
\ mathbb {E} [y | x] = g(x ^ \ top W ^ *),
\]
其中$ y $是$ k $类之一的指标向量,$ x \ in \ mathbb {R} ^ d $是我们的输入向量,$ W ^ * $是$ d \ timesk $参数矩阵要估计,并且$ g:\ mathbb {R} ^ k \到\ Delta ^ k $是softmax链接函数,将实数向量映射到概率单纯形:\ [
g(v)= \ left [\ begin {array} {c}
\ frac {\ exp(v_1)} {\ sum_ {j = 1} ^ k \ exp(v_j)} \\
\ vdots \\
\ frac {\ exp(v_k)} {\ sum_ {j = 1} ^ k \ exp(v_j)} \\
\ end {array} \ right]。
\]第一种算法的基本思想是为多项式逻辑损失的Hessian提出一个很好的代理。这个坏男孩是$ dk \ times dk $,并取决于当前参数。相反,我们将使用不依赖于参数且易于计算的矩阵。底线是多项逻辑回归,我们可以得到一个对角线代理,在对角线上有$ k $个相同的块,每个块的大小为$ d \ times d $。将块选择为$ \ frac {1} {2} X ^ \ top X $可确保我们的更新永远不会发散,同时避免行搜索和弄乱步长。使用此矩阵作为前提条件,我们可以继续进行前提条件(批量)的梯度下降操作。剧本 毫升 通过两个(有原则的)修改来做到这一点,从而大大加快了工作速度。首先,我们在足够大的子样本上计算预处理器。该脚本在注释中包括完整预处理器的代码。第二个修改是我们使用 加速梯度下降 而不是梯度下降。

将此优化器插入 角色扮演 几个月前的脚本在我的计算机上以9.7秒的时间提供了0.9844的测试精度,这比LBFGS快约20倍,并且精度更高。

第二种算法甚至更快,并且适用于多类以及多标签问题。还有一个缺点是,您不会在尾巴中获得非常准确的概率估计:这种方法不能优化交叉熵。基本思想是我们将学习链接功能,有时也称为校准。

对于二进制分类, PAV算法 可以学习使所有单调函数中的平方误差最小的链接函数。有趣的是, 等温纸 证明在PAV和线性分类器的参数的最小二乘学习之间进行迭代会导致此非凸问题的全局最小值。

剧本 cls.m 从我们在拟合目标和校准之间交替的意义上讲,将这些思想扩展到多类分类。在实现中使用的校准概念有些薄弱,等同于假设未知链接函数的逆可以表示为原始预测的低次多项式。为了简单起见,我们开了两个角:首先,我们不强迫链接为单调的(尽管单调性是 为高尺寸精心定义)。其次,我们假设在训练时(也称为转导设置)可以访问未标记的测试数据。在没有任何其他见解的情况下,不假定这样做的实现将更加复杂。

将优化器插入上述角色扮演脚本中,我在机器上的9.4秒内获得了0.9844的测试精度。同样,我们比LBFGS快20倍以上,并且更加准确。有趣的是,将该算法扩展为在多标签设置中工作非常简单:我们将其投影到单元超立方体上,而不是投影到单纯形上。

高维数据呢?这就是为什么二阶方法出现在机器学习社区的狗屋中的主要原因。一个简单而实用的解决方案是从加速和协调下降方法中调适思想。我们采用了一系列功能,并根据上述任一方法对它们进行了优化。然后,我们采用另一批特征并拟合残差。通常,根据问题,批量大小可以在300到2000之间。较小的尺寸提供最大的速度潜力,较大的尺寸提供最大的准确性潜力。提供最佳运行时间/精度权衡的批次大小取决于问题。脚本 mlsinner.m 处理此过程的内循环。它需要由外部循环提供的两个附加参数。它只执行了几次迭代,试图找到如何使用新一批功能来扩展我们的初始预测,以便我们更好地近似标签。我们还传递了一个权重向量,该向量告诉我们预处理器应关注哪些示例。外循环 stagewisemls.m 只需生成新的功能批次,跟踪预测并更新预处理器的重要性权重即可。

将此优化器插入cosplay脚本中,可以在67秒内得到0.986的测试精度。

最后, 角色扮演driver.m 在mnist数据集上运行上述所有算法。这是八度复制的方法。 (我上面报告的时间是在MATLAB中进行的。)
git clone //github.com/fest/secondorderdemos.git
cd secondorderdemos
octave -q 角色扮演driver.m

2011年12月13日,星期二

可视化人群

大约一年前,我读了Welinder等人的论文。等标题 人群的多维智慧。 那时,我刚刚开始大量利用众包来进行机器学习任务,而论文的跳跃开始了我对众包数据集的想法。因此,我很高兴地宣布,我已向 弹奏钢琴 受本文启发。

我说``灵感来自''是因为模型要简单得多。特别是因为在我的数据集中通常每个项目的评分很少(例如3),所以我继承了简单项目模型的传统(即,单个标量难度参数$ \ beta $)。因此,我嵌入了隐藏的标签,而不是嵌入项目。每个工人都被建模为一个概率分类器,该分类器由与隐藏标签原型的距离\ [
p(l_ {ij} = r | \ alpha,\ beta,\ tau,z)\ propto \ exp(-\ beta_j \ lVert \ tau_ {z_j} + \ alpha_ {z_jr}-\ tau_r-\ alpha_ {ir} \ rVert ^ 2)。
\]这里$ l_ {ij} $是工作人员$ i $在项目$ j $上报告的标签,$ \ alpha_ {ir} $是工作人员$ i $的$ d $维偏差矢量,标签为$ r $ ,$ \ beta_j $是项目$ j $的难度参数,$ \ tau_r $是标签$ r $的$ d $维原型向量,$ z_j $是项目$ j $的真实隐藏标签,而$ d $是嵌入的维数。尽管需要随机初始化$ \ tau $才能打破对称性,但是此参数化操作可确保$ \ alpha_ {ir} = 0 $是合理的起始条件。 $ \ alpha $是$ L ^ 2 $正则化的(高斯先验),而$ \ tau $不是正则化的(无信息先验)。关于不变性的注释:通过将$ \ tau $转换并旋转到规范位置来消除$ d $对称性($ \ tau_0 $约束在原点,$ \ tau_1 $约束在由第一个单位向量等)。

尽管我的动机是可视化(对应于$ d = 2 $或$ d = 3 $),但还有其他两种可能的用法。 $ d = 1 $类似于非单调 顺序约束 并且可能适合某些问题。较大的$ d $可能有用,因为每个工人的参数从$ O(| L | ^ 2)$减少到$ O(d | L |)$,这可能与 减少处理的多标签问题 .

推理与以前一样(我对分类器使用了多项逻辑回归),但工人模型当然发生了变化。实际上,该工人模型的速度比多项式工人模型的速度慢大约3倍,但是由于该工人模型导致每个工人参数的减少,因此公平的比较可能与低秩逼近比较,后者也较慢。这是完成我的规范演示任务的软件,可从其个人资料预测Twitter用户的种族。
strategy = 名义上的embed
initial_t = 10000
eta = 1.0
rho = 0.9
n_items = 16547
n_labels = 9
n_worker_bits = 16
n_feature_bits = 18
n_dims = 2
seed = 45
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.64616 -1.64616 -1.90946 -1.90946         2      -1       2       4       30
-1.60512 -1.56865 -1.93926 -1.95912         5      -1       2       3       32
-1.38015 -1.15517 -2.13355 -2.32784        10      -1       1       4       28
-1.11627 -0.82685 -2.08542 -2.03194        19      -1       2       3       21
-0.89318 -0.63424 -1.89668 -1.68574        36      -1       1       3       35
-0.90385 -0.91498 -1.62015 -1.31849        69      -1       8       4       27
-0.99486 -1.0903  -1.5287  -1.43162       134      -1       1       4       54
-0.93116 -0.86077 -1.42049 -1.30809       263      -1       1       4       45
-0.90436 -0.87592 -1.47783 -1.5365        520      -1       1       3       13
-0.92706 -0.95001 -1.42042 -1.36223      1033      -1       2       1       11
-0.96477 -1.00259 -1.33948 -1.25791      2058      -1       8       3       21
-0.95079 -0.93672 -1.2513  -1.16272      4107      -1       1       3       44
-0.91765 -0.88423 -1.13014 -1.0087       8204      -1       0       3       26
-0.90145 -0.88529 -0.98977 -0.84921     16397      -1       8       3       23
-0.86520 -0.82882 -0.80860 -0.62731     32782      -1       8       3       20
-0.83186 -0.79852 -0.63999 -0.47132     65551      -1       1       3       56
-0.79732 -0.76279 -0.50123 -0.36243    131088      -1       2       3       35
-0.77279 -0.74826 -0.40255 -0.30386    262161      -1       8       3       41
-0.75345 -0.73413 -0.33804 -0.27352    524306      -1       2       3       43
-0.74128 -0.72911 -0.29748 -0.25692   1048595      -1       1       4       45
-0.73829 -0.72691 -0.28774 -0.25064   1323760      -1       1       3       27
applying deferred prior updates ... finished

tau:
     \  latent dimension
      |   0       1   
label |
    0 | 0.0000  0.0000
    1 | 2.6737  0.0000
    2 | 3.5386  -1.3961
    3 | 1.3373  -1.2188
    4 | -1.5965 -1.4927
    5 | 0.0136  -2.9098
    6 | -2.4236 1.4345
    7 | -0.0450 2.2672
    8 | 2.1513  -1.5638
  447.48s user 1.28s system 97% cpu 7:38.84 total
上面的过程会为每个项目的隐藏标签生成估计值(后验分布),以及将尝试推广到新实例的分类器和尝试推广到新工人的工人模型。此外,还有一些可视化的东西:
  1. 隐藏的标签原型向量$ \ tau_r $。靠得更近意味着两个标签更容易混淆。
  2. 每个工人的噪声矢量$ \ alpha_ {ir} $。这些调整每位用户的隐藏标签原型,导致偏差和准确性上的差异。
  3. 通过在标签上的后分布,通过形成隐藏的标签原型向量的凸组合,可以将这些项放置到潜在空间中。
这是主要标签落入二维嵌入的方式。标签的文本以该标签的$ \ tau $的值为中心(对于新工人,$ \ alpha_ {ir} = 0 $,因此$ \ tau $定义默认的混淆矩阵)。典型的$ \ beta $是1,因此在此图上的距离3表示混淆的可能性非常低。 (单击图像放大)。


结果取决于随机种子。最受欢迎的标签(亚洲,西班牙,黑色,白色和N / A)保持相对位置,但不太受欢迎的标签会四处走动。这是上面针对不同随机种子的图:请注意,x轴缩小了,但这对于后续图更方便。 (单击图像放大)。


在其余的情节中,我会坚持使用这种随机种子。现在,我将在绘图上为每个工人的原型矢量($ \ tau_z + \ alpha_ {iz} $)放置一个点。 (单击图像放大)。


点的图案提供了有关整个工人群体中错误图案分布的一些直觉。例如,西班牙裔标签周围的点具有比水平扩展更多的水平扩展。这表明在区分白人和西班牙裔与区分黑人和西班牙裔之间存在更多差异。白人和西班牙裔之间的区别更多是文化而非种族。 美国人口普查局将白人列为种族,但将“西班牙裔或拉丁裔”列为种族;因此,从某种意义上说,这是糟糕的实验设计,但是由于广告商非常关注这种区别,因此我必须使其发挥作用。

最后,这是一些根据个人资料的隐藏标签上的后验分布嵌入到潜在空间中的个人资料照片。单击下面的图像以获取矢量版本,您可以放大并查看详细信息。


在某些情况下,鉴于其嵌入位置,这些照片似乎没有任何意义。其中一些是因为工人是嘈杂的贴标签者。但是,工人可以访问并根据整个配置文件决定标签。因此,最好将这些照片视为``特定种族选择使用的个人资料照片的示例'',而不是这些种族本身的照片的示例。

最新版本 弹奏钢琴 可从 Google代码存储库.

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 = 序数
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年10月28日,星期五

从众包数据在线多标签提取

我已经申请了 在线EM方法 之前讨论过 标称标签的低等级模型,并减少到我的 多标签模型。此时,它只是以不同的标签发射可能性转动曲柄。

不幸的是,由于多标签减少的组合性质,它在实践中可能非常慢。这是一个示例应用程序,在该应用程序中,我要求Mechanical Turkers将多个标签的短语放入诸如``Politics''和``Entertainment''之类的高级类别中。
pmineiro@ubuntu-152% for r in 4; do rm model.${r}; time ~/src/multionlineextract/src/multionlineextract --model model.${r} --data <(./multicat 10 =(sort -R octoplevel.max3.moe.in)) --n_items $(cat octoplevel.max3.moe.in | wc -l) --n_raw_labels $(./statsfrompm n_raw_labels) --max_raw_labels 3 --rank ${r} --priorz $(./statsfrompm priorz) --predict flass.${r} --eta 0.5; done
seed = 45
initial_t = 1000
eta = 0.500000 
rho = 0.500000 
n_items = 3803
n_raw_labels = 10
max_raw_labels = 3
n_labels (induced) = 176
n_workers = 65536
rank = 4
test_only = false
prediction file = flass.4
priorz = 0.049156,0.087412,0.317253,0.012600,0.135758,0.079440,0.109094,0.016949
,0.157750,0.034519
cumul     since       example   current   current   current
avg q     last        counter     label   predict   ratings
-3.515874 -3.515874         2        -1         0         4
-3.759951 -3.922669         5        -1         0         4
-3.263854 -2.767756        10        -1         0         4
-2.999247 -2.696840        19        -1         0         3
-2.531113 -2.014788        36        -1         9         4
-2.503801 -2.474213        69        -1         3         4
-2.452015 -2.396817       134        -1         3         4
-2.214508 -1.968222       263        -1         6         3
-2.030175 -1.842252       520        -1         3         4
-1.907382 -1.783031      1033        -1         1         4
-1.728004 -1.547266      2058        -1         2         4
-1.582127 -1.435591      4107        -1         2         4
-1.460967 -1.339532      8204        -1         9         4
-1.364336 -1.267581     16397        -1         5         4
-1.281301 -1.198209     32782        -1         3         4
-1.267093 -1.178344     38030        -1         3        -1
applying deferred prior updates ... finished
gamma:  0.0010  0.0008  0.0007  0.0006
~/src/multionlineextract/src/multionlineextract --model model.${r} --data      2
717.98s user 3.46s system 99% cpu 45:26.28 total
遗憾的是,是的,这是我笔记本电脑的一个核心需要45分钟。好消息是,在努力加快速度的同时,我提高了 顺序在线提取标称提取物 系数是4。但是推论仍然是$ O(| L | ^ 2)$,因此上面有176个有效标签的问题比二进制问题慢7700倍。更具限制性的假设,例如``所有错误的可能性均等''(在名义情况下)或``错误可能性仅取决于与真实标签的编辑距离''(在多标签情况下)会更便宜确切的推论。

多在线提取 可从 nincompoop Google代码上的存储库。

2011年9月23日,星期五

从众包数据在线提取标签

到目前为止,我一直在使用批处理EM优化我开发的用于处理众包数据的各种生成模型(名义上的, 序数多标签)。尽管我很喜欢在线技术,但是在行走之前我不得不爬网,并且数据集的大小相当适中。但是,企业对Mechanical Turk的结果感到满意,并希望将其从涉及多个$ 10 ^ 4 $项目的任务扩展到涉及多个$ 10 ^ 6 $项目的任务。尽管这仍然可以存储在笔记本电脑上的内存中,但是开发该算法的在线变体似乎是一个很好的借口。

我以前的批量EM方法可以认为是最大化辅助函数\ [
F(\ alpha,\ beta,\ gamma,q)= E_ {Z \ sim q} [\ log L(D | \ alpha,\ beta,\ gamma,Z)] + \ log P(\ alpha,\ beta ,\ gamma)+ E_ {Z \ sim q} [\ log P(Z)] + H(q),
\]其中$ \ alpha $是工作人员索引的参数,$ \ beta $是项目索引的参数,$ \ gamma $是全局参数,$ q $是所有未观察到的标签的联合分布,$ Z $是所有未观察到的标签,$ D $是项目-工人标签三元组的数据集,$ \ log L(D | \ alpha,\ beta,\ gamma,Z)$是数据集的对数似然,$ P (\ alpha,\ beta,\ gamma)$是生成模型参数上的先验分布,$ P(Z)$是先验未观察到的标签分布,而$ H(q)$是未观察到的标签分布的熵。

假定未观察到的标签分布会影响项目$ q(Z)= \ prod_i q_i(Z_i)$,先前的分布$ P(Z)= \ prod_i P_i(Z_i)$也是如此。可替代地,在该约束条件下,仅找到辅助函数的最大约束。假定数据似然独立于$(\ alpha,\ beta,Z)$,导致\ [
\ begin {split}
F(\ alpha,\ beta,\ gamma,q)&= \\
&\ sum_i E_ {Z_i \ sim q_i} [\ log L(D_i | \ alpha,\ beta_i,\ gamma,Z_i)] + \ log P(\ alpha,\ beta,\ gamma)\\
&+ \ sum_i E_ {Z_i \ sim q_i} [\ log P_i(Z_i)] + \ sum_ {q_i} H(q_i),
\ end {split}
\]其中$ i $为项目建立索引,而$ D_i $是与项目$ i $相关联的数据集。进一步假设先验分布的形式为$ P(\ alpha,\ beta,\ gamma)= P(\ alpha,\ gamma)\ prod_i P(\ beta_i)$,并重新排列收益率[[
\ begin {aligned}
F(\ alpha,\ beta,\ gamma,q)&= \ sum_i F_i(\ alpha,\ beta_i,\ gamma,q_i),\\
F_i(\ alpha,\ beta_i,\ gamma,q_i)&= \\
E_ {Z_i \ sim q_i} [\ log L&(D_i | \ alpha,\ beta_i,\ gamma,Z_i)] + \ frac {1} {| I |} \ log P(\ alpha,\ gamma)+ \ log P(\ beta_i)+ E_ {Z_i \ sim q_i} [\ log P_i(Z_i)] + H(q_i),
\ end {aligned}
\]其中$ | I | $是项目总数。现在,目标函数看起来像项的总和,其中$ \ beta_i $和$ q_i $仅出现一次。这表明,如果在对应于同一项目的块中流传输数据,并且已知最佳$ \ alpha $和$ \ gamma $,则可以单独最大化$ \ beta_i $和$ q_i $并将其丢弃。当然,最优的\\ alpha $和$ \ gamma $尚不清楚,但是随着时间的推移,随着遇到更多数据,估计值会越来越好。这表明以下过程:
  1. 接收与单个项目相对应的item-worker-label三元组$ D_i $。
  2. 相对于$ \ beta_i $和$ q_i $,最大化$ F_i(\ alpha,\ beta_i,\ gamma,q_i)$。
    • 基本上,我使用固定的$ \ alpha $和$ \ gamma $对这块数据运行EM。
  3. 设置$ \ alpha \ leftarrow \ alpha + \ eta_t \ nabla _ {\ alpha} F_i \ bigr | _ {\ alpha,\ beta ^ * _ i,\ gamma,q ^ * _ i} $和$ \ gamma \ leftarrow \ gamma + \ eta_t \ nabla _ {\ gamma} F_i \ bigr | _ {\ alpha,\ beta ^ * _ i,\ gamma,q ^ * _ i} $。
    • $ \ eta_t $是随时间衰减的学习,例如$ \ eta_t = \ eta_0(\ tau_0 + t)^ {-\ rho} $。
    • $ \ eta_0 \ geq 0 $,$ \ tau_0 \ geq 0 $和$ \ rho \ geq 0 $是学习算法的调整参数。
    • 有效地,$ | I | $也是一个设置先验相对重要性的调整参数。
  4. 如果需要(例如``推理模式''),输出$ \ beta ^ * _ i $和$ q ^ * _ i $。
  5. 丢弃$ \ beta ^ * _ i $和$ q ^ * _ i $。
  6. 返回到(1)。
相对于项目数,它具有很好的可伸缩性,因为没有跨输入块维护每个项目的状态。它确实要求汇总特定项目的所有标签:但是,即使在真正的在线众包场景中,也不会出现可伸缩性问题。在实践中,项目以编程方式单独提交以进行众包分析,并且冗余评估的数量通常很少(例如5个),因此,一个缓冲众包数据直到整个项目标签可用的接收系统对空间的要求非常小。以我为例,我实际上是将此在线算法应用于以前离线收集的数据集,因此我可以轻松地将与特定项目相对应的所有标签放在一起。

关于工人数量的可伸缩性是一个潜在的问题。这是因为$ \ alpha $被保留为state,并且由worker索引(例如, 标称提取物,$ \ alpha_w $是工作人员$ w $的混淆矩阵)。为了克服这个问题,我使用 哈希技巧:我有固定数量的$ \ alpha $参数,并且我对工作人员ID进行了哈希处理以获得该工作人员的$ \ alpha $。当我遇到哈希冲突时,这意味着我将两个(或更多)工作程序视为同等工作,但这使我可以预先限制算法的空间使用量。在实践中,像这样的哈希技巧似乎总是奏效。在这种特殊的情况下,在大量工人的限制下,我将使用人口混淆矩阵对每个工人进行建模。由于样本复杂性压倒了(固定的)模型复杂性,因此这是一种降级的优雅方法。 (我实际上并不期望有大量的工作人员;众包似乎走的路是,一个人要做一些小的任务来确定高素质的工作人员,然后再执行较大的任务以限制那些工作人员)。

这是一个示例运行,涉及在一个小的测试数据集上进行40次传递。
% time ~/src/nincompoop/nominalonlineextract/src/nominalonlineextract --initial_t 10000 --n_items 9859 --n_labels 5 --priorz 1,1,1,1,1 --model flass --data <(./multicat 40 =(sort -R ethnicity4.noe.in)) --eta 1 --rho 0.5
initial_t = 10000
eta = 1.000000 
rho = 0.500000 
n_items = 9859
n_labels = 5
n_workers = 65536
symmetric = false
test_only = false
prediction file = (no output)
priorz = 0.199987,0.199987,0.199987,0.199987,0.199987
cumul     since       example   current   current   current
avg q     last        counter     label   predict   ratings
-1.183628 -1.183628         2        -1         0         5
-1.125888 -1.092893         5        -1         0         5
-1.145204 -1.162910        10        -1         0         5
-1.081261 -1.009520        19         0         0         5
-1.124367 -1.173712        36        -1         3         3
-1.083097 -1.039129        69        -1         0         4
-1.037481 -0.988452       134        -1         1         2
-0.929367 -0.820539       263        -1         1         5
-0.820125 -0.709057       520        -1         4         5
-0.738361 -0.653392      1033        -1         1         4
-0.658806 -0.579719      2058        -1         1         5
-0.610473 -0.562028      4107        -1         4         5
-0.566530 -0.522431      8204        -1         0         3
-0.522385 -0.478110     16397        -1         2         4
-0.487094 -0.451771     32782        -1         0         3
-0.460216 -0.433323     65551        -1         4         5
-0.441042 -0.421860    131088        -1         2         5
-0.427205 -0.413365    262161        -1         0         5
-0.420944 -0.408528    394360        -1         1        -1
~/src/nincompoop/nominalonlineextract/src/nominalonlineextract --initial_t     85.77s user 0.22s system 99% cpu 1:26.41 total
如果那种输出格式看起来很熟悉,那是因为我(再次)提高了vowpal wabbit的输出风格。第一列是渐进式验证的辅助函数,即在更新模型参数($ \ alpha $和$ \ gamma $)之前评估的(项的平均数)$ F_i $函数。这类似于对数可能性,如果一切正常,随着消耗更多数据,它应该会变得更大。

标称提取物,批处理EM类似物的实现(在上述数据集上)在大约90秒内收敛,因此运行时间非常困难。对于较大的数据集,无需对数据集进行太多遍,因此我希望在线版本变得越来越有优势。此外,我一直在改善 标称提取物 几个月,而我刚写 标称在线提取 因此后者可能会进一步提高速度。但是,对于适合于内存批处理EM的数据集来说,它具有竞争力。

标称在线提取 可从 nincompoop Google代码上的代码存储库。我将在短期内将其他算法的在线版本放在一起(基本方法适用于所有算法,但是每种特定的可能性都有不同的技巧)。

2011年9月6日,星期二

多标签众包数据建模:第二部分

先前 我讨论了两种分析通过众包获得的多标签分类数据集的策略。 (此处的``多标签''是指将固定集中的零个或多个标签分配给特定项目)。第一种策略是减少到一组独立的二元标记数据集(IBR),该数据集对应于观测值和地面真实情况中不存在特定标记的情况。 IBR速度很快,但是在成本敏感型多标签(CSML)分类的背景下,加权Hamming损失仅能持续减少。换句话说,由IBR产生的基本事实多标签集的分布必然是各个标签分布的产物。第二种策略是在强大的标签集上减少到多类标签数据集,我称之为 多低位提取 (这是执行任务的可执行文件的名称)。 多低位提取 对应于CSML始终如一地减少为成本敏感的多类分类(CSMC),但遭受组合爆炸的困扰。中的``低等级'' 多低位提取 是指对混淆矩阵使用低秩方法来降低样本复杂性要求(不幸的是,这不能减轻计算复杂性要求)。

我从一个相对较小的测试数据集中介绍了一个轶事,该数据表明从0/1(整个集)损失的角度来看,两种方法产生的结果相同。由于IBR比 多低位提取 对于后一种方法,这并不是一个好兆头。随后,我尝试了更大的数据集,我可以说 多低位提取 有时可以大大提高后验模式的质量。一个引人注目的示例是一项涉及在Twitter上将标签分配给面向流行文化的个人资料的任务。对于印度电影演员来说,众包工作者可靠地分配了``电影演员''标签,但通常无法为个人资料分配额外的``宝莱坞''标签。使用IBR,这些配置文件的后验模式通常为{``电影演员'')。但是用 多低位提取,如果只有一个工作人员为配置文件分配了“宝莱坞”标签,而所有工作人员均分配了“电影演员”标签,则该配置文件的后验模式为{“宝莱坞”,“电影演员”导致0/1(整个设定)的损失大大减少。尽管这可以说是设计不良的任务,但这恰恰是IBR无法捕获的标签相关性,并且可能在实践中出现。

回想起来,毫不奇怪 多低位提取 需要更大的数据集才能胜过IBR。 IBR本质上将标签的所有遗漏视为等效,但是要可靠地推断出联合标签上的更复杂的错误模式,则需要足够的数据。不幸, 多低位提取 比IBR慢得多;根据上述流行文化数据集,IBR大约需要一分钟,而 多低位提取 需要4个核心小时。注意 多低位提取 是经过合理优化的代码:用C编写,利用了 代表性体操上证所使用基于SGD的稀疏M步骤,并具有多核E步骤。不幸的是,我处于尝试加快慢速学习算法的位置,这从来都不是一件好事。

中的最新版本 nincompoop 代码存储库在速度方面有很大的改进,但仍然不是我认为的快速。但是,如果您遇到一个标签总数不多的标签问题(例如20个),并且在实际情况下可以出现的标签最大数目的合理上限(例如3个),我认为值得尝试。在入睡之前将其启动,也许您会在早晨感到惊喜。

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代码存储库.

2011年7月17日,星期日

快速近似兰伯特W

毕竟,这只是个人用途的问题, 兰伯特的W 功能 一旦 在机器学习上下文中,它以$ W(\ exp(x))-x $出现,最好直接近似。尽管如此,生成这些快速的近似函数使娱乐变得有趣,并且与例如进一步发展我的计算机游戏能力相比,对某处某人有用的可能性要高得多。

无分支的生活方式

Lambert W在一个方面是典型的函数:有一个很好的渐近逼近可以用来初始化一个 户主法,但仅适用于部分域。特别是对于大$ x $,\ [
W(x)\ approx \ log(x)-\ log \ log(x)+ \ frac {\ log \ log(x)} {\ log(x)},
\]很棒,因为 对数便宜。不幸的是,对于$ x \ leq 1 $,无法评估,对于$ 1< x <2 $它给出了非常差的结果。一种自然的处理方式是为$ x使用不同的初始化策略< 2$.
如果 (x < 2)
  { 
    // alternate initialization
  }
else
  {
    // use asymptotic approximation
  }

// householder steps here
这种简单的方法存在两个问题。在标量上下文中,这可以 挫败流水线架构 现代CPU。在向量上下文中,这甚至更成问题,因为组件可能会落入条件的不同分支中。

该怎么办?事实证明像这样
a = (x < 2) ? b : c
看起来像有条件的,但不是必须的,因为它们可以重写为
a = f (x < 2) * b + (1 - f (x < 2)) * c
$ f $是一个指示符函数,根据参数的真值返回0或1。 上证所指令集包含以下指标功能 比较测试,当与 ``浮点数和'' 指令最终计算出无分支三元运算符。

底线是,如果计算条件的两个分支,则可以使确定性执行具有确定性,并且在足够简单的情况下,可以直接硬件支持快速执行此操作。

无分支兰伯特W

因此,这里的主要思想是为Householderer步骤进行另一种初始化,以便可以对无输入方式进行计算,因为对于大的输入使用渐近逼近。因此,我寻找\\形式的近似值
W(x)\大约a + \ log(c x + d)-\ log \ log(c x + d)+ \ frac {\ log \ log(c x + d)} {\ log(c x + d)},
\]对于大$ x $,$ a = 0 $,$ c = 1 $和$ d = 0 $。我通过Mathematica找到了$ a $,$ c $,$ d $的值和$ x $的临界值。 (好奇的可以查看 Mathematica笔记本)。矢量版本最终看起来像
// WARNING: this code has been updated.  Do not use this version.
// Instead get the latest version from http://code.google.com/p/fastapprox

static inline v4sf
vfastlambertw (v4sf x)
{
  static const v4sf threshold = v4sfl (2.26445f);

  v4sf under = _mm_cmplt_ps (x, threshold);
  v4sf c = _mm_or_ps (_mm_and_ps (under, v4sfl (1.546865557f)),
                      _mm_andnot_ps (under, v4sfl (1.0f)));
  v4sf d = _mm_and_ps (under, v4sfl (2.250366841f));
  v4sf a = _mm_and_ps (under, v4sfl (-0.737769969f));

  v4sf logterm = vfastlog (c * x + d);
  v4sf loglogterm = vfastlog (logterm);

  v4sf w = a + logterm - loglogterm + loglogterm / logterm;
  v4sf expw = vfastexp (w);
  v4sf z = w * expw;
  v4sf p = x + z;

  return (v4sfl (2.0f) * x + w * (v4sfl (4.0f) * x + w * p)) /
         (v4sfl (2.0f) * expw + p * (v4sfl (2.0f) + w));
}
您可以从 快速约 项目。

时间和准确性

时序测试是通过编译完成的 -O3 -finline功能-fast-math,在运行64位Ubuntu Lucid(所以 gcc 4:4.4.3-1ubuntu1libc 2.11.1-0ubuntu7.6)。我还测量了以$(\ frac {1} {2} U(-1 / e,1)+ \ frac {1} {2} U(0,100))$分布的$ x $的平均相对准确度,即,从两个均匀分布中抽取50-50。将精度与牛顿方法的20次迭代进行比较,当$ x时,初始点为0<5 $,否则渐近逼近。我还测试了 gsl实施 精度更高,但速度明显慢得多。
Fastlambertw average relative error = 5.26867e-05
fastlambertw max relative error (at 2.48955e-06) = 0.0631815
fasterlambertw average relative error = 0.00798678
fasterlambertw max relative error (at -0.00122776) = 0.926378
vfastlambertw average relative error = 5.42952e-05
vfastlambertw max relative error (at -2.78399e-06) = 0.0661513
vfasterlambertw average relative error = 0.00783347
vfasterlambertw max relative error (at -0.00125244) = 0.926431
gsl_sf_lambert_W0 average relative error = 5.90309e-09
gsl_sf_lambert_W0 max relative error (at -0.36782) = 6.67586e-07
fastlambertw million calls per second = 21.2236
fasterlambertw million calls per second = 53.4428
vfastlambertw million calls per second = 21.6723
vfasterlambertw million calls per second = 56.0154
gsl_sf_lambert_W0 million calls per second = 2.7433
这些平均精度在最小域中隐藏了相对较差的性能。就在$ x = -e ^ {-1} $,这是该域的最小值, Fastlambertw 近似差(-0.938,而正确答案是-1;因此相对误差为$ 6 \%$);但是在$ x = -e ^ {-1} + \ frac {1} {100} $时,相对误差降为$ 2 \乘以10 ^ {-4} $。

2011年7月6日,星期三

快速逼近集合

我将各种快速(矢量化)近似值捆绑在一起 在Google代码上进行项目.

CISC的复仇

因此,就像我们现在所听到的那样,我的童年Commodore 64时钟速度的千倍增长已不再重复。像其他科学计算社区一样,机器学习社区正认真地拥抱多核和集群计算,以便进一步扩展,这是一件好事。

但是,这项练习告诉我的是,计算机的速度越来越快:不是以时钟速度而言,而是每个时钟滴答完成了多少工作。芯片设计人员不仅会发布新的令人敬畏的指令,而且还会与每个芯片版本一起使用,以提高其效率(例如,更少的延迟,停顿)。如果您使用的是最新版本的编译器,例如gcc 4,则某些收益会自动累积 自动向量化 但是gcc 3没有。这就是为什么我``仅''看到与之相比又增加了20%的原因之一 LDA实现的向量化 在Vowpal Wabbit中:编译器已经对明显的东西进行了矢量化处理(例如,点积,循环累加计数器),但还不足以识别我的digamma,lgamma和指数近似值也可以进行矢量化处理。如果您使用gcc 3编译Vowpal Wabbit,则可能要付出速度损失。

好吧,那又如何呢?要达到PB级,还是需要一个集群,对吗?那么,存在很多问题,在笔记本电脑上拥有几GB的样本数据对于快速实验很有用。因此,它有助于以最快的速度实现在笔记本电脑上运行的学习算法。要快速实现,请注意指令集!

2011年6月26日,星期日

更快的LDA:第二部分

我能够提高其他效率 Vowpal兔子的LDA实施 通过 向量化。基本思想是找到重复的昂贵操作的循环并通过 SIMD 同时执行多个昂贵的操作。特别是我正在利用 上证所 指令系统。

向量化范例

对于我的简单功能 近似对数和指数,转换为SSE是一项最直接的机械任务(如此机械,实际上,我想知道为什么编译器无法为我完成此任务?)。这是一个示例:首先,原始的快速以2为底的对数,
// WARNING: this code has been updated.  Do not use this version.
// Instead get the latest version from http://code.google.com/p/fastapprox

inline float
fastlog2 (float x)
{
  union { float f; uint32_t i; } vx = { x };
  union { uint32_t i; float f; } mx = { (vx.i & 0x007FFFFF) | (0x7e << 23) };
  float y = vx.i;
  y *= 1.0f / (1 << 23);

  return
    y - 124.22544637f - 1.498030302f * mx.f - 1.72587999f / (0.3520887068f + mx.f);
}
接下来是SSE版本
// WARNING: this code has been updated.  Do not use this version.
// Instead get the latest version from http://code.google.com/p/fastapprox

typedef float v4sf __attribute__ ((__vector_size__ (16)));
typedef int v4si __attribute__ ((__vector_size__ (16)));
#define v4sf_dup_literal(x) ((v4sf) { x, x, x, x })
#define v4si_dup_literal(x) ((v4si) { x, x, x, x })
#define v4sf_from_v4si __builtin_ia32_cvtdq2ps

inline v4sf
vfastlog2 (v4sf x)
{
  union { v4sf f; v4si i; } vx = { x };
  union { v4si i; v4sf f; } mx = {
    (vx.i & v4si_dup_literal (0x007FFFFF)) | v4si_dup_literal ((0x7e << 23))
  };
  v4sf y = v4sf_from_v4si (vx.i);
  y *= v4sf_dup_literal ((1.0f / (1 << 23)));
  
  const v4sf c_124_22544637 = v4sf_dup_literal (124.22544637f);
  const v4sf c_1_498030302 = v4sf_dup_literal (1.498030302f);
  const v4sf c_1_725877999 = v4sf_dup_literal (1.72587999f);
  const v4sf c_0_3520087068 = v4sf_dup_literal (0.3520887068f);
  
  return 
    y - c_124_22544637 - c_1_498030302 * mx.f - c_1_725877999 / (c_0_3520087068 + mx.f);
}
vfastlog2 运行速度与 fastlog2 (实际上有时会稍快一些,具体取决于 fastlog2 并使用x87运算进行编译),并计算几乎相同的内容(有时差异很小,比近似误差小得多)。但是,它可以一次执行4次计算。

有一个陷阱:它总是一次执行4次计算,因此,如果数组的长度不是16个字节的倍数,则最后一次计算将从内存的其他位读取(可能导致分段错误)。此外,输入必须对齐16字节,否则会出现分段错误。有人告诉我,在超高性能应用程序中,开发人员总是将阵列排列为16字节对齐,并且是16字节长的倍数。但是,没有简单的方法来安排此操作,因此我不得不进行一些防御性的编码。我使用的模式是
// WARNING: this code has been updated.  Do not use this version.
// Instead get the latest version from http://code.google.com/p/fastapprox

typedef float v4sf_aligned __attribute__ ((__vector_size__ (16))) __attribute__ ((aligned (16)));

float f (float);
v4sf vectorized_f (v4sf);

inline void
conservative_map (float* x,
                  size_t n)
{
  unsigned int i;

  // handle non-aligned prefix
  for (i = 0; i < n && (((uintptr_t) (x + i)) % 16) > 0; ++i)
    { 
      x[i] = f (x[i]);
    }

  // the good stuff
  for (; i + 4 < n; i += 4)
    { 
      * (v4sf_aligned *) (x + i) = vectorized_f (* (v4sf_aligned*) (x + i));
    }

  // handle remainder
  for (; i < n; ++i)
    { 
      x[i] = f (x[i]);
    }
}
对于大约100个主题的地图,这在最坏的情况下会导致25个操作之外的6个附加操作,因此平均可能会有10%的罚款。

结果

我在与我的基准相同的基准上进行了一些其他计时测试 以前的帖子。 \ [
\ begin {array} {c | c}
\ mbox {代码版本}&\ mbox {总挂钟} \\ \ hline
\ mbox {原始}&\ mbox {79秒} \\
\ mbox {近似值,无SSE}&\ mbox {49秒} \\
\ mbox {近似值,含SSE}&\ mbox {39秒}
\ end {array}
\]
近似加速比矢量化加速大,这很好,因为即使对于不支持SSE的环境,近似加速始终可用。

2011年6月24日,星期五

更快的LDA

现在,我已经掌握了 字节重新解释的邪恶力量 在整数和IEEE浮点数之间,我一直在寻找加速的东西。最近发布的 快速实施LDA 由Smola等等提醒我看Vowpal Wabbit的 LDA实施。的 官方网站 该文件充满了看起来昂贵的先验功能,可以使用近似版本来加快速度,希望不会破坏学习算法。

更快的Log Gamma和Digamma

除了许多我已经有了快速近似的指数和对数调用之外,还有一些对 对数伽玛地伽玛。幸运的是, 斯特林近似 是对数,因此我可以利用我的快速对数近似值 以前的博客文章.

我发现对于Log Gamma和Digamma而言,两次应用移位公式可以在精度和速度之间取得最佳折衷。
// WARNING: this code has been updated.  Do not use this version.
// Instead get the latest version from http://code.google.com/p/fastapprox

inline float
fastlgamma (float x)
{
  float logterm = fastlog (x * (1.0f + x) * (2.0f + x));
  float xp3 = 3.0f + x;

  return
    -2.081061466f - x + 0.0833333f / xp3 - logterm + (2.5f + x) * fastlog (xp3);
}

inline float
fastdigamma (float x)
{
  float twopx = 2.0f + x;
  float logterm = fastlog (twopx);

  return - (1.0f + 2.0f * x) / (x * (1.0f + x))
         - (13.0f + 6.0f * x) / (12.0f * twopx * twopx)
         + logterm;
}
时间和准确性
时序测试是通过编译完成的 -O3 -finline功能-fast-math,在运行64位Ubuntu Lucid(所以 gcc 4:4.4.3-1ubuntu1libc 2.11.1-0ubuntu7.6)。我还测量了$ x \ in [1/100,10] $的平均相对准确度(使用 lgammaf 来自libc作为Log Gamma的黄金标准,并且 boost :: math :: digamma 作为Digamma的黄金标准)。
fastlgamma relative accuracy = 0.00045967
fastdigamma relative accuracy = 0.000420604
fastlgamma million calls per second = 60.259
lgammaf million calls per second = 21.4703
boost::math::lgamma million calls per second = 1.8951
fastdigamma million calls per second = 66.0639
boost::math::digamma million calls per second = 18.9672
好吧,Log Gamma的速度大约是3倍(但是为什么boost :: math :: lgamma这么慢?)却略好于Digamma的3倍。

LDA时序

所以我将这些近似值放入 官方网站 并使用 wiki1K 来自的文件 测试/训练集/ 目录;但是我将文件本身连接了100次以减慢速度。
原始运行
% (cd test; time ../vw --lda 100 --lda_alpha 0.01 --lda_rho 0.01 --lda_D 1000 -b 13 --minibatch 128 train-sets/wiki1Kx100.dat)
your learning rate is too high, setting it to 1
using no cache
Reading from train-sets/wiki1Kx100.dat
num sources = 1
Num weight bits = 13
learning rate = 1
initial_t = 1
power_t = 0.5
learning_rate set to 1
average    since       example  example    current  current  current
loss       last        counter   weight      label  predict features
10.296875  10.296875         3      3.0    unknown   0.0000       38
10.437156  10.577436         6      6.0    unknown   0.0000       14
10.347227  10.239314        11     11.0    unknown   0.0000       32
10.498633  10.650038        22     22.0    unknown   0.0000        2
10.495566  10.492500        44     44.0    unknown   0.0000      166
10.469184  10.442189        87     87.0    unknown   0.0000       29
10.068007  9.666831        174    174.0    unknown   0.0000       17
9.477440   8.886873        348    348.0    unknown   0.0000        2
9.020482   8.563524        696    696.0    unknown   0.0000      143
8.482232   7.943982       1392   1392.0    unknown   0.0000       31
8.106654   7.731076       2784   2784.0    unknown   0.0000       21
7.850269   7.593883       5568   5568.0    unknown   0.0000       25
7.707427   7.564560      11135  11135.0    unknown   0.0000       39
7.627417   7.547399      22269  22269.0    unknown   0.0000       61
7.583820   7.540222      44537  44537.0    unknown   0.0000        5
7.558824   7.533827      89073  89073.0    unknown   0.0000      457

finished run
number of examples = 0
weighted example sum = 0
weighted label sum = 0
average loss = -nan
best constant = -nan
total feature number = 0
../vw --lda 100 --lda_alpha 0.01 --lda_rho 0.01 --lda_D 1000 -b 13 --minibatc  69.06s user 13.60s system 101% cpu 1:21.59 total
近似运行
% (cd test; time ../vw --lda 100 --lda_alpha 0.01 --lda_rho 0.01 --lda_D 1000 -b 13 --minibatch 128 train-sets/wiki1Kx100.dat)               your learning rate is too high, setting it to 1
using no cache
Reading from train-sets/wiki1Kx100.dat
num sources = 1
Num weight bits = 13
learning rate = 1
initial_t = 1
power_t = 0.5
learning_rate set to 1
average    since       example  example    current  current  current
loss       last        counter   weight      label  predict features
10.297077  10.297077         3      3.0    unknown   0.0000       38
10.437259  10.577440         6      6.0    unknown   0.0000       14
10.347348  10.239455        11     11.0    unknown   0.0000       32
10.498796  10.650243        22     22.0    unknown   0.0000        2
10.495748  10.492700        44     44.0    unknown   0.0000      166
10.469374  10.442388        87     87.0    unknown   0.0000       29
10.068179  9.666985        174    174.0    unknown   0.0000       17
9.477574   8.886968        348    348.0    unknown   0.0000        2
9.020435   8.563297        696    696.0    unknown   0.0000      143
8.482178   7.943921       1392   1392.0    unknown   0.0000       31
8.106636   7.731093       2784   2784.0    unknown   0.0000       21
7.849980   7.593324       5568   5568.0    unknown   0.0000       25
7.707124   7.564242      11135  11135.0    unknown   0.0000       39
7.627207   7.547283      22269  22269.0    unknown   0.0000       61
7.583952   7.540696      44537  44537.0    unknown   0.0000        5
7.559260   7.534566      89073  89073.0    unknown   0.0000      457

finished run
number of examples = 0
weighted example sum = 0
weighted label sum = 0
average loss = -nan
best constant = -nan
total feature number = 0
../vw --lda 100 --lda_alpha 0.01 --lda_rho 0.01 --lda_D 1000 -b 13 --minibatc  41.97s user 7.69s system 102% cpu 48.622 total
因此,从81秒降低到49秒,速度提高了大约40%。但这有效吗?好吧,我让马特(Matt)担任最终裁判(我给他寄了一封修改过的 官方网站 (用于测试),但初步迹象表明,使用昂贵功能的近似版本不会破坏学习过程。

下一步:矢量化

肯定会有更多的速度,因为 官方网站 加载像
for (size_t i = 0; i<global.lda; i++)
    {
      sum += gamma[i];
      gamma[i] = mydigamma(gamma[i]);
    }
只是为了尖叫 向量化。敬请关注!