显示带有标签的帖子 真实数据 . 显示所有帖子
显示带有标签的帖子 真实数据 . 显示所有帖子

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的网站运行。
function 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  与  .^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)$广义特征值问题,那也是不合理的。我们正在努力解决这些问题,我们也很高兴将此策略扩展到结构化预测。希望我们在接下来的几届会议上能有更多的话要说。

2013年11月9日,星期六

我们可以哈希一下

该实验室位于西北太平洋,因此很自然地会问什么机器学习原语和 酸洗 。目前有两名主要候选人: 随机特征图哈希技巧。事实证明,后者可以有益地用于随机PCA。

正如我所见,随机PCA算法 最近讨论, 是真棒。根据经验,要获得非常好的结果,似乎需要两个(或更多个)通过算法。理想情况下,可以只使用一种(结构化的)随机性将数据向下传递到某个计算上合适的维度,然后使用精确的技术将其完成。在实践中,这并不是很好,尽管有时计算上的好处(单次传递数据和低内存使用)是合理的。两遍算法使用第一遍构造正交基础,然后将该基础用于第二遍。除了额外的数据传递外,还需要存储两个传递算法作为基础,以及正交化步骤。如果原始特征维数为$ p $,所需分量数为$ k $,则存储需求为$ O(p k)$,并且正交化步骤的时间复杂度为$ O(p k)$。如果$ O(p k)$可以放入主存储器中,这不是问题,但否则就很麻烦,因为本质上需要分布式QR分解。

哈希技巧(更一般而言,结构化随机性)可以在两个极端之间建立桥梁。想法是使用结构化随机性将特征维数从$ p $减少到$ d $,以使$ O(d k)$适合主存,然后使用两次通过随机算法。这可以看作是利用结构化随机性的一遍算法与传统的两遍算法之间的插值。实际上,我们只是在尝试使用可用的空间资源来获得良好的答案。我们发现散列是稀疏域(例如文本或图形数据)的良好结构化随机性,而其他结构化随机性(例如,子采样 哈特利变换)更适合密集数据。当使用哈希时,该方法继承了哈希技巧的其他便利,例如不需要知道输入数据先验的特征基数。

这些随机方法不应令人生畏:一旦您理解它们,它们将非常简单。这是一些Matlab使用散列进行随机PCA:
function H=makehash(d,p)
  i = linspace(1,d,d);
  j = zeros(1,d);
  s = 2*randi(2,1,d)-3;

  perm = randperm(d);
  j=1+mod(perm(1:d),p);
  H = sparse(i,j,s);
end
function [V,L]=hashpca(X,k,H)
  [~,p] = size(H);
  Omega = randn(p,k+5);
  [n,~] = size(X);
  Z = (X*H)'*((X*H)*Omega)/n;
  Q = orth(Z);
  Z = (X*H)'*((X*H)*Q)/n;
  [V,Lm,~] = svd(Z,'econ');
  V = V(:,1:k);
  L = diag(Lm(1:k,1:k));
end
你可以用类似的东西来调用
>> H=makehash(1000000,100000); [V,L]=hashpca(sprandn(4000000,1000000,1e-5),5,H); L'

ans =

   1.0e-03 *

    0.1083    0.1082    0.1081    0.1080    0.1079
因此,与往常一样,好处之一就是让您在商用笔记本电脑上进行一些计算,而这又使其他实现难以为继。这是PCA产生的图片 公开可用的Twitter社会图 在我的笔记本电脑上使用大约800 MB的内存。散列节省的空间仅约20倍,因此,如果您有一台具有16 GB内存的计算机,则可以使用 红碟 毫无困难,但是当然有了更大的数据集,最终内存会变得昂贵。
该图像可能很难看懂,但是如果单击它会变大,然后如果在新选项卡中打开较大的版本并放大,则可以获得更多细节。

如果您喜欢这种东西,可以查看 ,或者您可以访问 NIPS机器学习随机方法 Nikos将讨论的研讨会。 阿伦·库玛(Arun Kumar) 于今年夏天在CISL实习,他在 Biglearn 关于实施于 .

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年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月13日,星期一

更好的标签相似性可视化

好吧,我花了整个周末的大部分时间来改善自己的 标签相似度可视化,没有很好的理由,只是发痒时就必须挠痒。这就是最终看起来最好的东西。
  1. 计算每个哈希标签的词项频率向量。
    1. 对于每个推文X:
      1. 对于X $中的每个主题标签$ h:
        1. 对于X $中的每个非标签令牌$ t \:
          1. $(h,t)$的增量计数。
  2. 计算前1000个最频繁的标签中的每个标签对的成对余弦$ \ cos \ theta(h,h ^ \ prime)$。
  3. 将相似度定义为$ s(h,h ^ \ prime)= \ arccos(\ cos \ theta(h,h ^ \ prime))$。
    1. 与$ 1.0-\ cos \ theta(h,h ^ \ prime)$相比,我得到的负特征值更少。这是在超球面上移动和跨越超弦之间的区别。
  4. 做60维 MDS 在$ s $。
    1. 60个特征值中有两个为负,因此我将其视为0。所以实际上是58维MDS。
    2. 我在这里得到任何负特征值时感到有些惊讶,因为我所有的项向量都占据了超球面的正超象限。显然,我的超直觉需要超调……或者我有一个错误。
  5. 将产生的60维表示输入 吨位 .
    1. 我使用困惑10。
我选择t-SNE是因为高维结构似乎是相对孤立的簇。我推断是因为我将邻域定义为$ \ epsilon \ theta $球并运行 弗洛伊德·沃歇尔 在邻域图中,我注意到我必须使用一个非常大的邻域($ \ cos \ theta \ geq 0.8 $),然后才能获得足够大的连接组件以变得有趣。

最终,当我绘制此标签时,我尝试将颜色随机化,以便在所有标签相互叠放时能够看到一些东西。真的png不能公正,您应该得到 pdf版本 并放大。

2011年6月9日,星期四

标签相似性可视化

永远不要低估漂亮图片的力量。一方面, 探索性数据分析 确实有助于建立更好的模型。此外,无论您想要更多的补助金还是更多的薪水,漂亮的图片都是说服人们您正在做有趣事情的好方法。

所以我开始研究Twitter 井号 采用;最终目标是通过在编写推文时自动建议或纠正哈希标签,在阅读推文时解释哈希标签等来改进我们的客户端软件。Twitter的新手用户经常抱怨这没有任何意义,因此这将是一个不错的选择增值。

标签受累于 词汇问题。基本上,您说的是#potato,我说的是#spud。通常,人们使用的变体在语义上几乎是等效的,但有时在词汇上却完全不同。一些例子是
  • #shoutouts和#shoutout:这种情况似乎适合词法分析。
  • #imjustsaying和#imjustsayin:这些都非常接近,也许我们希望基于``阻止''的策略能够奏效。
  • #nowplaying和#np:有很多用长缩写代替长哈希标签的示例,以节省费用,也许可以为此制定定制的词汇策略。
  • #libya和#feb17:完全不是词法,但是这些标签的当前几乎等效的性质可能随时间而不稳定。
代替词法驱动的方法,最好开发一种数据驱动的方法来建议,更正或解释哈希标签:毕竟,不乏推文。

好了,偷偷摸摸,这是漂亮的照片。我在推文样本中提取了1000个最受欢迎的哈希标签,并通过将所有带有该哈希标签的推文相加来计算每个哈希标签的词项频率向量。接下来,我计算 余弦相似度 哈希标记之间,阈值设为0.985,然后将结果反馈给Mathematica的 图形图 。这是结果(点击放大)。
根据我要花多少时间,合理的下一步是雇用一些 降维 技术将其投影到2维并查看生成的图片(希望能提供更多信息)。但是,即使上面的简单过程也会产生一些有趣的信息:
  1. 通常,此图有助于围绕使用的某些词法转换建立直觉。
  2. 哈希标签用于执行以下操作:指示要遵循的意愿和意图进行交互。
  3. 对于英语和葡萄牙语的读者来说,星座运势显然都很重要。但是用来描述每个符号的实际单词模式却非常相似。 :)
  4. 有几种方法可以限定潜在的煽动性言论,以表明寻求真相的动机(``真实对话''集群)。
  5. 我最喜欢的#sex和#porn群集。在互联网上,它们确实是相同的。

2011年6月2日,星期四

尺寸分析和梯度下降

考虑根据损失函数$ l $,\ [
\ begin {aligned}
p ^ {(t)}&= w ^ {(t)\ top} x ^ {(t)},\\
w ^ {(t + 1)}&= w ^ {(t)}-\ eta \ frac {\ partial l} {\ partial p} x ^ {(t)}。
\ end {aligned}
\] Suppose the optimal 权重向量 is $w^*$. If all the inputs are scaled by a constant amount $r$, then the optimal 权重向量 is $w^* / r$, 和 it would be nice 如果 the learning algorithm produced output that respected this identity. A more general way to think along these lines is dimensional analysis.

假设预测的维度为\ rho $,输入的维度为\ chi \。那么权重必须具有$(\ rho / \ chi)$的维数才能计算出预测方程。假设损失的大小为$ \ lambda $,这意味着学习率$ \ eta $必须具有$ \ rho ^ 2 / /(\ lambda \ chi ^ 2)$的单位才能计算出更新方程。在实践中,这意味着,如果我们有一个权重向量序列收敛到我们喜欢的某个位置,然后我们更改所有输入以使它们加倍,则学习率必须四分之一,以使生成的权重向量的整个序列将其减半,以使整个预测序列相同。

所以这些想法已经被纳入 Vowpal兔子 (实际上,这就是我意识到它们的方式:我请Vowpal团队帮助我理解我在源代码中看到的内容)。特别是在命令行上指定的$ \ eta $由$ x ^ {(t)\ top} x ^ {(t)} $规范化,对应于$ {1 / / chi ^ 2)$部分。 $ \ eta $维数;但是,这不能解决$ \ rho ^ 2 / \ lambda $部分。 (为什么这么重要?假设我创建了一个新的损失函数,该函数是另一个损失函数的输出的两倍;在命令行上指定的学习率必须降低一半。)

在处理二元模型时,我不得不弄清楚如何对此进行概括,因此我开始考虑它。通过$ x ^ {(t)\ top} x ^ {(t)} $进行归一化肯定会针对输入的全局缩放进行调整,但是如果仅对输入的一个维度进行缩放会怎样?这开始进入以下领域 预处理 这导致了自适应方法 杜契,哈桑和歌手 又名DHS(也同时在 麦克马汉和史特勒 但我将专注于DHS)。在那里他们定义了一个矩阵$ G ^ {{(t)} = \ mathrm {diag} \ left(1 / \ sqrt {\ sum_ {s \ leq t}(g ^ {{s}} _ i} ^ {2}} \ right)$,并使用更新\ [
w ^ {(t + 1)} = w ^ {(t)}-\ eta \ frac {\ partial l} {\ partial p} G ^ {(t)} x ^ {(t)},
\] 其中$ g ^ {{s}} =(\ partial l / \ partial p ^ {{s}})x ^ {{s}} $。在此更新中,$ G ^ {((t)} $)的尺寸为$ \ rho /(\ lambda \ chi)\ ldots $越来越近!不幸的是,$ \ eta $仍然不是无量纲的,其尺寸为$ \ rho / \ chi $。请注意,DHS推论1中$ \ eta $的最佳选择与$ \ max_t || w_t-w ^ * || _ {\ infty} $成正比,其单位为$(\ rho / \ chi)$。换句话说,如果所有输入都加倍,我们仍然必须将以前的最佳学习率降低一半才能获得最佳行为。

这就留下了一个问题:单位$(\ rho / \ chi)$可以用来对$ \ eta $进行规范化,使得在命令行上指定的参数是无量纲的。任何与$ t $相关的变化都不在DHS的分析范围之内,但我暂时将其忽略。两件事表明了自己:$ 1 / || x ^ {(t)\ top} x ^ {(t)} || _p $和$ 1 / /(x ^ {(t)\ top} G ^ {(t)} x ^ {(t)})$。 (这些单位为$ 1 / \ chi $,但越来越近了)。它们具有不同的属性。

直观地使自适应学习算法具有优势的是,它们在频繁出现的特征上更加保守,而在很少出现的特征上更具攻击性。使用$ || x ^ {(t)\ top} x ^ {(t)} || _p $归一化,如果遇到一个例子,其中所有特征以前都被广泛地看过和训练过,那么有效学习率将很小。因此,与在训练序列中较早看到此示例相比,预测的变化将很小。相反,通过$ x ^ {(t)\ top} G ^ {(t)} x ^ {(t)} $归一化,如果遇到一个例子,其中所有特征之前都已被广泛了解和训练,则有效学习速率将被归一化以补偿,使得相对于在训练序列中较早看到该示例而言,预测的变化不会很小。另一方面,对于一个在训练序列中较晚出现的新颖特征和频繁特征混合的示例,相对于该示例是否已发生,与采用任一归一化方案的频繁特征权重相比,更新对新颖特征权重的影响将更大。在训练序列中更早。

维度$(\ rho / \ chi)$还有其他内容。自适应学习方法的关键见解之一是使用来自整个输入历史的信息,而不仅仅是当前输入,来驱动学习。到目前为止,总结所有输入的一件事是权重向量。 DHS推论1中的最佳权重向量与$ \ max_t || w_t-w ^ * || _ {\ infty} $成正比,并且由于$ w_0 = 0 $,所以这大约是$ || ww ** ||。 _ \ infty $。 $ w ^ * $的一个近似值(可能太可怕了!)是当前的权重向量。当它为零时,这在开始时是一个特别糟糕的近似值,因此我考虑将提供的$ \ eta $缩放为$ \ max(1,|| w ^ {(t)} || __infty)$,其中仅考虑$ w ^ {(t)} $的具有$ x ^ {(t)} $的相应非零值的分量。

一个实验

有很多想法,所以我决定进行一个实验。我有数以千万计的推文,这些推文根据写该推文的人的性别进行了标记。由于推文中令牌数量的变化,输入向量具有有趣的范数。我使用恒定的学习速率(vowpal按$ x ^ \ top x $进行缩放)和DHS自适应学习算法按不同的值进行缩放进行了训练。我只对数据进行了一次传递,并且报告了训练集上渐进的验证折损。我在命令行上使用$ \ eta = 1 $进行了所有这些测试。 \ [
\ begin {array} {c | c | c}
\ mbox {方法}&\ mbox {损失}&\ mbox {评论} \\ \ hline
\ mbox {最佳常数}&\ mbox {0.722}&\ mbox {在Twitter上,女人比男人多(为什么?)}} \\
\ mbox {非自适应}&\ mbox {0.651}&\ mbox {在这种情况下,大众汽车通过$ || x ^ {(t)} || ^ 2_2 $归一化}} \\
\ mbox {自适应$ || x ^ {(t)} || _1 $规范化}&\ mbox {0.588}&\\
\ mbox {自适应$ || x ^ {(t)} || _2 $规范化}&\ mbox {0.554}和\\
\ mbox {自适应$ || x ^ {(t)} || __infty $归一化}&\ mbox {0.579}&\\
\ mbox {自适应$ x ^ {(t)\ top} G ^ {(t)} x ^ {(t)} $规范化}&\ mbox {0.621}&\ mbox {比替代方案差得多! } \\
\ mbox {自适应$ \ max(1,|| w ^ {(t)} || __infty)$缩放}&\ mbox {0.579}&\\
\ mbox {自适应$ \ max(0.1,|| w ^ {(t)} || __infty)$缩放}&\ mbox {0.562}&\\
\ mbox {自适应$ \ max(1,|| w ^ {(t)} || __infty)$缩放}&\ mbox {0.579}&\ mbox {忽略$ || w ^ {{t )} || __infty $} \\
\ mbox {自适应$ \ max(0.1,|| w ^ {(t)} || __infty)$缩放}&\ mbox {0.560}&\ mbox {忽略$ || w ^ {{t )} || __infty $} \\
\ end {array}
\]
实际上,对于$ z \ leq 0.1 $尝试$ \ max(z,|| w ^ {(t)} || __infty)$会得到相同的结果。我认为这可能是由于常量特征的权重(始终以值1表示;因此,在某种意义上,它具有固定的比例,不会随输入而变化),因此我尝试在计算时不使用常量特征$ || w ^ {(t)} || _ \ infty $,但结果大致相同。

因此,该实验表明,通过自适应范数$ x ^ {(t)\ top} G ^ {(t)} x ^ {(t)} $进行归一化确实会破坏自适应策略的有效性。否则,在此实验的基础上,很难真正偏爱一种策略。话虽如此,我个人最喜欢的是$ \ max(0.1,|| w ^ {(t)} || __ \ infty)$缩放比例,因为它直接来自遗憾分析并具有正确的单位。

现在,我需要回到最初的目标:在训练一个 二元模型 .

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年4月24日,星期日

半监督的LDA:第三部分

在我的 以前的帖子 我讨论了半监督LDA的想法:在语料库上构建主题模型,其中一些文档具有关联的标签,但大多数文档没有关联的标签。目的是提取主题,该主题由语料库中的所有文本告知(例如,无监督的LDA),但也可以预测观察到的标签(如有监督的LDA)。

监督结果

在我以前的文章中,我没有说明如何计算$ p(y | w)$,即给定文档文本的文档标签的分布。继 DiscLDA论文 我使用了谐波均值估算器( 最糟糕的蒙托卡罗方法),但我只使用了1个样本量(有史以来最差的样本量)。实际上,这意味着:
  1. 对于每个标签$ y $
    1. 使用以标签为条件的Gibbs采样器绘制$ z \ sim p(\ cdot | w,y)$。
    2. 计算$ p(w | z,y)= \ prod_i \ frac {n ^ {(w_i)} _ {-d,u ^ k_ {z_i}} + \ beta} {n ^ {(\ cdot)} _ { -d,u ^ k_ {z_i}} + W \ beta}。$
    3. 估计$ p(w | y)\大约p(w | z,y)$。
  2. 计算未归一化的后验$ p(y | w)\ propto p(w | y)p(y)$并归一化。
在完全标记的数据集(即监督学习)上,这可以提供良好的结果。这是经过监督的跑步的结果,
这里没有其他分类器:给定由LDA程序生成的文档文本,将根据标签的后验分布确定0/1丢失。

您可能会问:为什么分类器不会将训练集上的损失设为零?通过(临时)从训练集中删除文档,然后运行推理算法来获取标签后验,可以评估此​​处的井损失。这仍然是泛化性能的有偏估计,但有些保守。测试集上的实际0/1损失约为0.23(即77%的准确度)。

接下来,您可能会问:只有77%?正如我在 以前的帖子 ,从用户的关注者集中预测性别具有挑战性,主要是因为我仅标记了数据的一小部分,而受欢迎的Twitter帐户(即最有可能被关注的Twitter帐户)往往不会具有性别歧视性。我能够相当准确地预测Twitter用户的性别,但是我必须在Twitter帐户中组合多种信息来源,社交图仅是其中的一个组成部分。以我的经验,相对于我尝试过的其他事情,仅使用关注者信息的准确性为77%,这确实非常好。特别是在所有社交图边缘集上执行无监督的LDA,然后对标记的子集(通过Vowpal Wabbit)进行有监督的分类,可以达到72%的准确性。请注意,准确率是72%并不是草率的:这是一系列实验的最佳结果,在这些实验中,我改变了LDA模型中主题的数量和其他参数。

我的直觉是,在标记的子集上进行监督的LDA不会比在整个集合上进行无监督的LDA做得好,然后在标记的子集上进行监督的分类,因为后者技术使用了所有数据。现在我必须更新我的直觉!

半监督结果

不幸的是,当我添加无人监督的数据时,情况变得很糟糕。这是测试集上的准确度图,它是未标记的训练数据所占比例的函数。
这很不幸,因为我想将此图中的x轴设为0.99(即,仅标记了我总体数据的1%),而且趋势不是我的朋友。

仍然有很多调优和错误查找功能,因此我不必沉没。但是,也没有很好的理论结果来推动事情:我不知道由于基于生成模型向分类器添加无监督数据而导致的分类改进的任何保证,尤其是当已知生成模型不正确时(例如,文档实际上不是以这种方式生成的)。所以在某个时候,我将不得不举起白旗。