显示带有标签的帖子 无监督学习. 显示所有帖子
显示带有标签的帖子 无监督学习. 显示所有帖子

2015年9月20日,星期日

心电图 2015审查

心电图 今年很高兴。波尔图绝对是参加会议的最佳欧洲城市的候选名单。组织者做了出色的工作,将当地的魅力注入了日程安排中,例如在 泰勒的 很高兴。这是一个葡萄酒之城,整个会议期间都适当提供葡萄酒。白天,我坚持喝咖啡:时差,柔和的灯光和低语的数学方法足以使人镇定下来,而不用咖啡代替酒精。毫无疑问,通过一些社交手段,海报发布会要好得多。

主题演讲始终出色。对我来说,一些突出之处是:
  • 佩德罗斯·多明戈斯(Pedros Domingos)介绍了他的 最新的求和产品网络 作为一类非凸函数,可以针对其找到一个全局最大值。机器学习被凸函数所困扰,因为它是一类大类,因此对于它而言,找到全局最大值很容易。最近,深度学习社区令人信服地指出,凸度太局限了,因此我们都对更多``细腻''的优化程序越来越满意。也许我们需要的是不同的函数类?
  • Hendrik Blockeel谈到了声明式机器学习。我在系统-ML组合小组中工作,我可以告诉您系统的人们喜欢这个想法。他们所有人都了解了关系代数如何通过SQL引发数据库的声明性革命,并将机器学习中的当前事务状态视为SQL之前的混乱。
  • Jure Leskovec进行了一个未经宣布的主题更改,并发表了一个神话般的主题演讲,可以将其解释为:``嘿,机器学习人员可能会对公共政策产生很大影响,但首先您需要了解反事实估计的原理和陷阱。 ''我完全同意,cf, 盖尔曼 。 (Jure还对时间考验论文进行了讨论 克罗内克图
  • Natasa Milic-Frayling详细介绍了(尽管有些不屑一顾)数字网络和移动广告公司用于跟踪和描述用户的多种技术。所有人都非常熟悉,因为我从事计算广告工作已经有多年了,但是从社会学的角度来看,广告网络的ung头态度与欧洲对隐私的高度重视并存是很有趣的。
还有一些论文,我将在这些论文上度过美好的时光。

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 关于实施于 .

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年10月2日,星期三

缺乏监督

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

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

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

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

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

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

2012年8月1日,星期三

可扩展的半监督深度学习

尽管我一直对深度学习研究人员的目标表示同情,但到目前为止,在实践中,深度学习技术并未在我的职业中扮演重要角色。我选择为具有大量数据(行为性数据耗尽)的数据公司(大多数为离散或文本形式)(例如文本搜索广告,约会个人资料和推文)工作。因此,我仅依靠浅层学习算法(线性或轻度非线性)和手动调整的特征构造。

如果深度学习很棒,那么就不需要像我这样的人付钱,将原始数据整理成更适合于浅层学习算法的形式。我也不认为历史会善待人类特征工程的能力。文本数据是一个例外,因为它易于使用:天真的编码(例如,一包bigrams)是一个很好的起点,并且有很多可用的辅助信息来源可以与令牌结合使用。相比之下,计算机视觉社区似乎面临着更加困难的问题。尽管从历史上看,按Internet标准来说,它们标记的数据集很小,但是由于众包和公共数据库定义的努力,近年来这种情况已得到缓解。因此,问题似乎在于像素比文本更难以使用。这很直观:文本有时会拼写错误,多义或惯用;但像素必须处理照明,姿势,遮挡等。

最近,由斯坦福大学,谷歌大学和纽约大学组成的深度学习和计算机视觉研究团队取得了令人兴奋的进步, 这个演讲 这个视频 。基本思想是利用大规模无监督技术生成特征,然后利用这些特征解决多个有监督的学习问题,即半监督体系结构。对于无监督的部分,他们使用具有神经网络解释的稀疏编码器。值得注意的是,它们不仅针对计算机视觉,还针对各种问题显示出优异的结果。

另一种流行的无监督学习方法是生成概率模型。从历史上看,这在计算上是昂贵的,因为两个最流行的技术系列(蒙特卡罗和变分方法)都不是速度守护程序。如果生成模型可以有效地缩放,那么稀疏编码器可能会赢得一些竞争。

因此,我为 霍夫曼等等 关于随机变异推论(SVI)的论文。对于可变方法,SVI本质上是随机梯度下降(SGD)的类似物。注意SVI已经作为Vowpal Wabbit(VW)潜在Dirichlet分配(LDA)实现的基础已经被证明是可靠的技术,但有一个重要警告:VW LDA实现非常快速,但仅使用一个内核。此警告和与SGD的类比应该在这里引起危险。当适用于单个内核时,SGD通常占主导地位。当梯度计算有些繁琐时,多核SGD通常也占主导地位,就像我们希望将SVI应用于生成模型中一样。另一方面,分布式SGD并不是简单的灌篮,因为I / O考虑开始占主导地位。相应地,分布式SVI在实践中可能效果不佳,至少对于某些没有实现技巧的生成模型而言,这种效果不佳。但是,由于SVI广泛适用,因此值得一试。 (请注意,谷歌家伙所做的一些很酷的事情可以概括为``制作分布式SGD工作'')。

另一个有希望的方向是线性代数方法在诸如LDA之类的潜在模型中的兴起。还记得语义建模和SVD是同义词吗? (如果是这样,您还记得Excite和Lycos。) 阿南库玛(Anandkumar)等等 表明使用两个SVD和三阶(trigram)统计数据可以恢复LDA中的潜在主题结构。在开发可伸缩的分布式线性代数库方面已经付出了巨大的努力,因此,这一研究领域最终可能会产生最快的潜在因子模型实现。