显示带有标签的帖子 随机方法. 显示所有帖子
显示带有标签的帖子 随机方法. 显示所有帖子

2015年7月23日,星期四

极端分类代码发布


极端分类讲习班 集成电路 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: 国王-皇后$ \大约$男人-女人.

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; cosplay
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研讨会。

2013年6月22日,星期六

集成电路 2013 :稀疏,深度和随机

集成电路 2013 对组织者来说,这是今年的一次伟大的会议。 对于个人来说,要全面了解所有内容实在太大了,但我确实注意到了三种趋势。

首先,稀疏性作为一种结构性约束似乎无处不在。 由于我对该子领域知之甚少,因此我非常关注最初两分钟的谈话,这些谈话通常会(很快地)讨论一些基本问题,例如,“人们为什么完全关心稀疏性?”.  我听到了一些通用动机,例如计算便利性和清晰度。 我还听到了一些具体的动机,例如 阿南库玛(Anandkumar)等等 表明对于特定的生成模型结构,可以通过稀疏编码技术来识别参数; Ruvolo和Eaton主张 模型的稀疏编码 在多任务学习中促进任务之间的知识转移。

第二,深度学习继续复苏。 特别是两次演讲提出了一些重要的未来方向。 首先是Coates关于以下架构的深度学习的演讲: 16台带有4个GPU的机器,每个通过infiniband连接.  我在这个博客上抱怨过SGD的高通信成本如何使它成为一种不良的分布式学习算法,但Coates等。等直接用硬件来解决这个问题。 这显然是不久的将来。 最重要的是,我们确实没有更好的神经网络训练算法,但是解决问题的经济性非常重要,以至于有可能“throw hardware 在 it”,硬件将被抛出。 The second talk was 递归神经网络训练的难点 由Pascanu等等人讨论了在递归环境中基于梯度的学习的一些改进。 显然,深度学习专家主导了“natural UI”在移动空间中如此重要的问题(例如语音识别和图像标记)现在正在寻求控制顺序预测任务(随着自治系统的普及,其重要性将日益增加)。 他们将与核心人员展开激烈的竞争:Le Song在精彩的演讲中 条件分布的希尔伯特空间嵌入 应用于顺序预测。

说到内核家伙,第三个主题是随机的,尤其是Alex Smola的演讲 核学习的快速随机逼近 (“FastFood”) was a real treat.  据推测,随机计算技术与条件分布的希尔伯特空间表示相结合,将产生用于顺序预测和其他潜在建模任务的强大算法。 在这方面的另一个突出表现是Mahoney的演讲 回顾Nyström方法以改善大型机器学习.

请注意,与前两个主题(稀疏和深层主题)不同,我不会说random是广泛流行的主题。 我个人对此感到非常兴奋,并且我认为对机器学习的影响很大,尤其是在分布式环境中。 基本上,使用这些随机算法的数值线性代数专家一直在研究“架构感知计算”多年以来,机器学习社区才开始意识到这一点。 想要一窥这对您意味着什么,请考虑戴维·格莱希(David Gleich)关于 Hadoop中的瘦身QR分解.

最后,我不得不提到John Langford和HalDaumé进行了关于命令式学习的精彩演讲,这与上述任何内容都不适合。 我找不到任何在线资料,这很不幸,因为这真的很酷,而且如果您曾经将机器学习算法应用于现有的生产系统中,那么您会立即喜欢上它。 基本思想是您,最终用户,程序“normally”并调用实现为协同程序的学习算法。 这有两个优点:首先,该算法自然地体验了由程序引起的决策的分布,因此“dataset collection”问题和相关错误得到缓解(这对于顺序预测尤为重要);其次,训练和评估时间码的路径相同,因此在生产中的实现既容易,又不易出错。 请注意,此设置中的评估时间开销很小,因此没有诱惑来重写生产算法。 引入了测试时间开销,但是可以通过使用额外的注释修饰代码来减轻此负担,从而使学习算法能够适当地记忆。 实在太热了,我想自愿在附近尝试一些顺序的预测任务,以尝试一下。