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: and 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, and then it gets worse, better, and 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年10月2日,星期三

缺乏监督

对于计算广告和互联网约会,标准的统计学习理论手册对我来说效果很好。是的,存在不稳定的环境,探索利用困境和其他协变量转变;但是大部分教科书的直觉都是有价值的。现在,在潜在的情况下 彼得原理 ,我在操作遥测和安全性方面遇到的问题似乎相去甚远,这对教科书的帮助较小。在向Gartner致意时,我将恐吓概括为4个象限的助记符。
环境
遗忘的 对抗性
标签 丰富 教科书机器学习 恶意软件检测
罕见 服务监控和警报 入侵检测

第一个维度是环境:它是遗忘的还是对抗性的?遗忘意味着,尽管环境可能会发生变化,但它的行为与系统做出的任何决定无关。对抗性意味着环境正在根据我所做的决定而改变,从而使我的决定变得更糟。 (当然,Adversarial不是疏忽的对立面:环境可能是有益的。)第二个方面是标签信息的普及,我广义上讲是指通过数据定义模型质量的能力。对于每种组合,我都会给出一个示例问题。

顶部是教科书监督学习,在这种环境中,学习环境可以忽略不计,标签也很丰富。我目前的老板有很多这样的问题,但也有很多人需要解决,还有很多很酷的工具可以解决。底部是入侵检测,入侵检测是每个人都想做得更好的一个领域,但这极具挑战性。这是象限开始提供帮助的地方,方法是建议缓解入侵检测的困难,我可以将其用作热身。在恶意软件检测中,环境具有很高的对抗性,但标签却很多。鉴于 震网 保持隐藏状态这么长时间,但实际上所有主要的防病毒软件供应商都雇用大量的人类,他们的日常活动提供了丰富的标签信息,尽管公认的是不完整的。在服务监视和警报中,某些标签相对较少(因为严重的中断很少发生),但是工程师并没有以明显逃避检测的方式注入缺陷(尽管有时会感觉到这种情况)。

我怀疑在标签信息稀少时取得胜利的关键是降低标签获取成本。这听起来似乎是重言式的,但是它确实提出了来自主动学习,众包,探索性数据分析,搜索和隐式标签插补的想法;所以不是完全虚空。换句话说,我正在寻找一种系统,该系统会审慎地询问域专家,提出一个可以可靠回答且其回答具有较高信息内容的问题,以有效的格式显示他们需要回答该问题的信息,并允许域导出以指导学习,并且可以从现有的未标记数据中进行引导。十分简单!

对于对抗性设置,我认为在线学习是难题的重要组成部分,但只是其中一部分。我特别赞同这样的观点: 在对抗环境中,可理解的模型具有优势 因为它们可以更好地与需要维护它们,了解其脆弱性并加强防御主动和反应攻击的人员一起工作。我勉强承认这一点,因为迄今为止,我感觉到机器学习的一大优势就是能够使用难以理解的模型:可理解性是一个严格的限制!但是,可理解性并不是一个固定的概念,并且只要有了正确的(模型和数据)可视化工具,机器学习技术的种类就会越来越广泛。

有趣的是,对于稀有标签和对抗性问题,用户界面问题似乎都很重要,因为两者都需要与人类进行有效交互(出于不同目的)。