显示带有标签的帖子 Matlab的. 显示所有帖子
显示带有标签的帖子 Matlab的. 显示所有帖子

2015年7月23日,星期四

极端分类代码发布


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

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

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

2014年11月16日星期日

大型CCA

有很多未标记的数据,所以最近我一直在花更多的时间在无监督的方法上。 尼科斯 我花了一些时间 CCA,类似于SVD,但在数据上采用了一些结构。特别是,它假设有两个(或多个)数据视图,其中一个视图基本上是一组功能。一种 生成解释 给定一个特征,条件是给定一个未观察到的潜在变量的高斯分布。数值线性代数的解释是我们试图解决以下优化问题:给定两个视图$ \ mathbf {A} \ in \ mathbb {R} ^ {n \ times d_a} $和$ \ mathbf {B} \ in \ mathbb {R} ^ {n \ time d_b} $,CCA投影$ \ mathbf {X} _a \ in \ mathbb {R} ^ {d_a \ times k} $和$ \ mathbf {X} _b \ in \ mathbb {R} ^ {d_b \ times k} $是\ [
\ begin {aligned}
\ mathop {\ mathrm {maximize}} _ {\ mathbf {X} _a,\ mathbf {X} _b}&\ mathop {\ mathrm {Tr}} \ left(\ mathbf {X} _a ^ \ top \ mathbf { A} ^ \ top \ mathbf {B} \ mathbf {X} _b \ right),\ nonumber \\
\ mathrm {subject \ to} \;&\ mathbf {X} _a ^ \ top \ mathbf {A} ^ \ top \ mathbf {A} \ mathbf {X} _a = n \ mathbf {I},\\
\;&\ mathbf {X} _b ^ \ top \ mathbf {B} ^ \ top \ mathbf {B} \ mathbf {X} _b = n \ mathbf {I}。
\ end {aligned}
\]
对于“small data”,CCA可以使用SVD解决,并且我们有很好的SVD随机化方法,在分布式环境中效果很好。那么,为什么我们没有好的CCA随机方法呢?基本上,约束使CCA变成了广义特征值问题,尽管有两个分母。实际上,对于两个视图数据,CCA可以简化为一对广义特征值问题,\ [
\ mathbf {A} ^ \ top \ mathbf {B}(\ mathbf {B} ^ \ top \ mathbf {B})^ {-1} \ mathbf {B} ^ \ top \ mathbf {A} \ mathbf {X } _a = \ mathbf {A} ^ \ top \ mathbf {A} \ mathbf {X} _a \ Lambda_a,
\]类似的问题来找到$ \ mathbf {X} _b $。我们有 随机平方根自由算法 对于广义特征值问题,那么问题就解决了吧?是的,有一些重要警告。首先,频谱是不利的,因此随机测距仪将需要多次通过或大量的过采样。其次,范围查找涉及计算$(\ mathbf {B} ^ \ top \ mathbf {B})^ {-1} $对$ \ mathbf {B} ^ \ top \ mathbf {A} \ Omega $的作用,并反之亦然,这是最小二乘问题(实际上 不需要非常精确地计算)。第三,这对广义特征值问题共享显着状态,因此对操作进行交织是有益的。通过这些观察,我们最终得到了一种非常类似于经典的CCA计算算法的东西,该算法称为 霍斯特迭代,但具有Halko风格的“过采样,提前停止,然后在较小的子空间中使用精确的解决方案进行完善。”我们在此方法上很幸运,该方法在github上作为 阿尔卡.

此外,事实证明,有时您可以完全避免最小二乘:在范围查找过程中,您可以将逆协方差近似为可缩放的恒等矩阵,并用(大量)额外的过采样进行补偿。如果您将使用大型正则器,则此方法效果很好,并且通过简化计算(尤其是在分布式上下文中)可以补偿过采样的开销。本质上,我们将优化限制在$ \ mathbf {A} ^ \ top \ mathbf {B} $的最高频谱中, 可以产生好的结果。这可以在github上以 rcca.m.

CCA具有多种用途:一种应用是 创建单词嵌入,在精神上类似于 word2vec。作为演示,我们采用了美国英语Google n-gram语料库,并使用CCA创建了嵌入。在商用台式机上的Matlab大约需要一个小时才能生成嵌入,这比下载数据要花费许多小时要快。可以在以下位置找到要复制的代码 的github (警告:您需要大约40 GB的内存,50 GB的磁盘空间和带宽才能下载n克)。您可以验证嵌入是否满足“ultimate test” of word 嵌入s: 国王-皇后$ \大约$男人-女人.

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]}。
\] 对于the specific choice of $\phi (z) = z^2$ this is tractable, as it results in a 瑞利商 在两个有条件的第二时刻之间,\ [
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)。

的 features that result from this procedure pass the smell test. 对于example, starting from a raw pixel representation on 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
        if 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
        if 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倍,并且精度更高。

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

对于binary 分类, the 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

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机器学习随机方法 尼科斯将讨论的研讨会。 阿伦·库玛(Arun Kumar)于今年夏天在CISL实习,他在 Biglearn 关于实施于 .

2013年10月15日,星期二

另一种随机技术

在一个 以前的帖子 我讨论了随机特征图,它可以结合内核的功能和原始线性方法的速度。我最近还使用了另一种随机技术来实现正义, 随机SVD。这是具有许多应用程序的出色原始语言,例如,您可以与随机化的特征图混搭以获得快速的内核PCA,用作双线性潜在因子模型(又称为矩阵分解)的快速初始化器,或用于计算 巨型CCA.

基本思想是用随机向量探测矩阵,以发现矩阵的低维顶部范围,然后在该空间中执行更便宜的计算。对于平方矩阵,这是直观的:特征向量构成了矩阵的作用仅是按比例缩放的基础,而顶部特征向量具有与之相关的较大比例因子,因此由矩阵缩放的随机向量将成比例地变大。最高的特征方向。这种直觉表明,如果本征谱几乎是平坦的,那么用随机探针捕获顶部本征空间将真的很困难。一般来说,这是对的,如果存在“large spectral gap”,即连续的特征值之间存在较大差异时。但是,即使这有点悲观,因为在机器学习中,有时您并不关心是否获得了子空间“wrong”,例如,如果您要最小化平方重建误差,则几乎相等的特征值会产生较低的后悔。

这是mnist上随机PCA的示例:您需要 以Matlab格式下载mnist 运行这个。
rand('seed',867);
randn('seed',5309);

tic
fprintf('loading mnist');

% get mnist from http://cs.nyu.edu/~roweis/data/mnist_all.mat
load('mnist_all.mat');

trainx=single([train0; train1; train2; train3; train4; train5; train6; train7; train8; train9])/255.0;
testx=single([test0; test1; test2; test3; test4; test5; test6; test7; test8; test9])/255.0;
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=[]; for i=1:10; yt=[yt; repmat(paren(eye(10),i,:),st(i),1)]; end
ys=[]; for i=1:10; ys=[ys; repmat(paren(eye(10),i,:),ss(i),1)]; end

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

fprintf(' finished: ');
toc

[n,k]=size(yt);
[m,p]=size(trainx);

tic
fprintf('estimating top 50 eigenspace of (1/n) X”X using randomized technique');

d=50;
r=randn(p,d+5);                % NB: we add an extra 5 dimensions here
firstpass=trainx'*(trainx*r);  % this can be done streaming in O(p d) space
q=orth(firstpass);
secondpass=trainx'*(trainx*q); % this can be done streaming in O(p d) space
secondpass=secondpass/n;
z=secondpass'*secondpass;      % note: this is small, i.e., O(d^2) space
[v,s]=eig(z);
pcas=sqrt(s);
pcav=secondpass*v*pinv(pcas);
pcav=pcav(:,end:-1:6);         % NB: 和 we remove the extra 5 dimensions here
pcas=pcas(end:-1:6,end:-1:6);  % NB: the extra dimensions make the randomized
                               % NB: algorithm more accurate.

fprintf(' finished: ');
toc

tic
fprintf('estimating top 50 eigenspace of (1/n) X”X using 艾格斯');

opts.isreal = true; 
[fromeigsv,fromeigss]=eigs(double(trainx'*trainx)/n,50,'LM',opts);

fprintf(' finished: ');
toc


% relative accuracy of eigenvalues
%
% plot((diag(pcas)-diag(fromeigss))./diag(fromeigss))

% largest angle between subspaces spanned by top eigenvectors
% note: can't be larger than pi/2 ~ 1.57
%
% plot(arrayfun(@(x) subspace(pcav(:,1:x),fromeigsv(:,1:x)),linspace(1,50,50))); xlabel('number of eigenvectors'); ylabel('largest principal angle'); set(gca,'YTick',linspace(0,pi/2,5)); 
当我在笔记本电脑上运行时,我得到
>> randsvd
loading mnist finished: Elapsed time is 6.931381 seconds.
estimating top 50 eigenspace of (1/n) X'X using randomized technique finished: Elapsed time is 0.505763 seconds.
estimating top 50 eigenspace of (1/n) X'X using 艾格斯 finished: Elapsed time is 1.051971 seconds.
运行时间的差异不是很大,但是在较大的矩阵上,差异可能是几分钟,而“比您可以等待的时间更长”。好吧,那有多好?即使假设 艾格斯 是地面真理,有几种方法可以回答这个问题,但是假设我们想从随机技术中获得与 艾格斯 (同样,这在机器学习中通常过于严格)。在这种情况下,我们可以测量最大 主角 在发现的前$ k $个子空间之间 艾格斯 并由随机PCA作为$ k $的函数。接近零的值表示两个子空间非常接近,而$ \ pi / 2 $附近的值指示一个子空间包含与另一个子空间中的向量正交的向量。

In general we see the top 6 or so extracted eigenvectors are spot on, 和n it gets worse, better, 和 worse again. Note it is not monotonic, because if two eigenvectors are reordered, once we have both of them the subspaces will have a small largest 主角. Roughly speaking anywhere there is a 光谱间隙大 we can expect to get the subspace up to the gap correct, i.e., if there is a flat plateau of eigenvalues followed by a drop than 在 the end of the plateau the largest 主角 should decrease.

Redsvd 提供两遍随机SVD和PCA的开源实现。

2013年8月27日,星期二

角色扮演

如果您喜欢原始线性方法,那么您可能已经花了很多时间考虑要素工程。如果您使用过内核学习,那么您可能已经花了很多时间来考虑适合您问题的内核,这是思考功能工程的另一种方式。事实证明,在解决原始凸优化问题时,有一种方法可以利用内核社区的工作:随机特征图。这个想法已经存在了一段时间: Rahimi和Recht撰写的论文 真正开始的事情是从2007年开始 关于它的博客完善技术,而Veeramachaneni有一个 不错的博客文章 以图形方式探索该技术。一种通用策略是找到内核的积分表示,然后通过蒙特卡洛近似积分表示。最终,这看起来像一个随机特征图$ \ phi $,其原始点积$ \ phi(x)^ \ top \ phi(y)$收敛到内核函数$ k的值(x,y)$。当使用傅立叶基础进行内核的整数表示时,随机特征图由余弦组成,因此我们在CISL中将其称为``cosplay''。

该技术应该比它更广为人知,因为它提供了良好的学习性能(当相关的内核是解决该问题的不错选择时),它易于实现并且非常快。我希望我可以通过在众所周知的数据集上提供简单的实现来提高知名度,并且本着这种精神,这里是一个Matlab脚本,它将该技术应用于mnist。在运行此程序之前,您需要下载 mnist在matlab格式,然后下载 maxent和lbfgs for matlab.

rand('seed',867);
randn('seed',5309);

tic
fprintf('loading mnist');

% get mnist from http://cs.nyu.edu/~roweis/data/mnist_all.mat
load('mnist_all.mat');

trainx=single([train0; train1; train2; train3; train4; train5; train6; train7; train8; train9])/255.0;
testx=single([test0; test1; test2; test3; test4; test5; test6; test7; test8; test9])/255.0;
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=[]; for i=1:10; yt=[yt; repmat(paren(eye(10),i,:),st(i),1)]; end
ys=[]; for i=1:10; ys=[ys; repmat(paren(eye(10),i,:),ss(i),1)]; end

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

fprintf(' finished: ');
toc

tic
fprintf('computing random feature map');

% (uncentered) pca to 50 ... makes subsequent operations faster,
% but also makes the random projection more efficient by focusing on
% where the data is

opts.isreal = true; 
[v,~]=eigs(double(trainx'*trainx),50,'LM',opts);
trainx=trainx*v;
testx=testx*v; 
clear v opts;

% estimate kernel bandwidth using the "median trick"
% this is a standard Gaussian kernel technique

[n,k]=size(yt);
[m,p]=size(testx);
sz=3000;
perm=randperm(n);
sample=trainx(perm(1:sz),:);
norms=sum(sample.^2,2);
dist=norms*ones(1,sz)+ones(sz,1)*norms'-2*sample*sample';
scale=1/sqrt(median(dist(:)));

clear sz perm sample norms dist;

% here is the actual feature map:
% Gaussian random matrix, uniform phase, 和 cosine

d=4000;
r=randn(p,d);
b=2.0*pi*rand(1,d);
trainx=cos(bsxfun(@plus,scale*trainx*r,b));
testx=cos(bsxfun(@plus,scale*testx*r,b));

fprintf(' finished: ');
toc

tic
fprintf('starting logistic regression (this takes a while)\n');

% get @maxent 和 lbfgs.m from http://www.cs.grinnell.edu/~weinman/code/
% if you get an error about randint being undefined, change it to randi

addpath recognition;
addpath opt;
addpath local;

C0=maxent(k,d);
[~,trainy]=max(yt');
options.MaxIter=300; 
options.Display='off';
C1=train(C0,trainy,trainx,'gauss',4.2813,[],[],[],options);
% regularizer was chosen by cross-validation as follows
%perm=randperm(n);
%it=logical(zeros(1,n));
%it(perm(1:int32(0.8*n)))=1;
%[C1,V]=cvtrain(C0,trainy(perm),trainx(perm,:),'gauss',10.^linspace(-4,4,20), ...
%               [],0,[],it,[],@accuracy);
        
fprintf('finished: ');
toc
fprintf('train accuracy is %g\n',accuracy(C1,trainy,trainx));
[~,testy]=max(ys');
fprintf('test accuracy is %g\n',accuracy(C1,testy,testx));

这是在笔记本电脑上运行脚本的结果:
>> clear all; 角色扮演
loading mnist finished: Elapsed time is 2.227499 seconds.
computing random feature map finished: Elapsed time is 6.994094 seconds.
starting logistic regression (this takes a while)
finished: Elapsed time is 219.007670 seconds.
train accuracy is 0.99905
test accuracy is 0.9822
这接近高斯内核SVM的性能,但具有简单性和速度。通过尝试不同 随机特征图,您可以改善此结果。

如果您喜欢这种东西,请务必检查一下 机器学习的随机方法 NIPS 2013研讨会。