2013年12月12日,星期四

NIPSplosion 2013

NIPS 今年真是太棒了,对所有组织者,区域主席,审稿者和志愿者都表示敬意。在创纪录的与会者人数,众多公司赞助商和 马克·扎克伯格(Mark Zuckerburg)秀,今年的会议以绝对的规模最为著名。一个人可以有效地总结这一点已经超出了重点,但这是我的回顾,很自然地偏向于我的兴趣。

主题演讲非常出色,与综合演讲一致“big picture”会议的遗产。我最喜欢的是达芙妮·科勒(Daphne Koller),他谈到了“其他在线学习”,即通过电信进行的教学法。类似于在线移动对话如何使我们能够准确地描述 斯诺基,在线移动指令有助于使用机器学习来改善人类学习。从早期信息支配地位到成熟的边缘刺激小腿,基于一般的互联网弧线,很明显, Coursera 平台将在附近 求爱技巧,但在此期间,很多人将获得更多实质性利益。

就整体主题而言,我没有发现任何新兴技术,这与往年不同,例如深度学习,随机方法和频谱学习之类的技术激增。从理智上讲,这次会议就像是巩固阶段,好像以前的突破仍在被消化。但是,输出表示学习和极端分类(大型基数多类或多标签学习)代表了有趣的新领域,并希望明年在这些领域将取得进一步的进展。

There were several papers about improving the convergence of 随机梯度下降 which appeared broadly similar from a 理论的 standpoint (约翰逊和张; 王等等; 张等等)。我喜欢 控制变量 王等人的解释。等生成直觉的最佳选择,但是如果您想实现某种功能,Johnson 和 Zhang的图1的伪代码则可理解。

协方差矩阵很热,而不仅仅是PCA。大& QUIC algorithm of Hseih等。等 for estimating large sparse inverse covariance matrices was technically very impressive 和 should prove 有用 for causal modeling of biological 和 neurological systems (presumably some hedge funds will also take interest). 巴兹和Müller 有一些有趣的想法 收缩率估算器, 包括“正交补码”顶本征空间应该 因为样本估计实际上是很好的,所以将其缩小。

随机方法中的一件有趣的工作是 McWilliams等。等,然后将两个随机特征图与CCA在未标记的数据上对齐,以提取“useful”随机特征。这是在半监督设置中利用未标记数据的直接方法,并且计算成本低廉,并且与CCA回归的理论结果一致。我期待着尝试。

讲习班很棒,尽管像往常一样,同时发生了很多有趣的事情,使得选择困难。我弹跳之间 极端分类, 随机方法大学习 第一天。迈克尔·乔丹(Michael Jordan)在大型学习中的演讲非常出色,特别是将各种优化松弛的计算复杂度降低与统计风险增加并置的部分(均因可行集的扩展而产生影响)。这开始在数据和计算资源之间进行权衡。极端分类(大型基数多类或多标签学习)是一个令人兴奋的开放领域,这很重要(例如,对于NLP中出现的结构化预测问题),并且在短期内看来很容易解决。有两份相关的会议文件是 弗罗姆等等 (利用 word2vec 以减少极端分类以使用最近邻解码进行回归)和 西塞等。等 (它利用了标签图的近乎分离的性质,而标签图在实践中经常遇到大规模多标签问题)。

第二天我大部分时间都在 光谱学习 但是我看到了布莱的讲话 主题建模。光谱学习进行了有趣的讨论。三个有趣的问题是
  1. 为什么频谱技术没有得到更广泛的应用?
  2. 怎样才能使光谱方法更广泛地适用,类似于后验推断的变分贝叶斯或MCMC?
  3. 模型错误指定的后果是什么?如何使光谱方法对模型错误指定更可靠?
关于第一个问题,我认为缺少的是可以轻松找到,安装和试用的坚如磐石的软件。临时从业者并不关心算法的理论优势,实际上他们倾向于“theoretical” as a synonym for “putative”。 c.f.在第二个问题上取得了很大进展, 概率编程。给定哪里 硬件正在发展,未来属于最具说服力的。第三个问题是多年生的贝叶斯问题,但是对于频谱方法来说可能具有特殊的结构,这可能会建议例如鲁棒的优化准则。

2013年12月10日,星期二

翻转车间

今年在NIPS上,最重要的主题之一是 达芙妮·科勒(Daphne Koller) 关于Coursera和 翻转教室。改天,我与亚马逊的Chetan Bhole一起吃午餐,他指出我们每个人都去参加会议以听取彼此的演讲:由于翻转的教室很棒,我们应该将这一概念应用于会议。

我喜欢这个主意。

考虑将整个会议转变为这种形式是不切实际的(至少要等到该想法获得信誉之前),但是由于组织者是全体会议,所以研讨会提供了一个很好的实验平台。它是这样工作的:对于一些勇敢的讲习班,将向接受讲习班的演讲者(并邀请演讲者!)附带视频,希望参加讲习班的人员能在讲习班之前观看。 (也许我们甚至可以使用Coursera的平台来获得诸如掌握问题和论坛之类的额外信息。)在研讨会上,演讲者只花了2分钟左右的时间提醒听众他们是谁,以及视频的内容是什么。然后,它变成完全交互式的问答,大概是由白板或智能板驱动的。

随意窃取这个想法。否则,也许我会尝试组织一个研讨会来尝试这个想法。

2013年11月9日,星期六

我们可以哈希一下

The lab is located 在里面 Pacific Northwest, so it's natural to ask what machine learning primitives are as ubiquitously 有用 as 酸洗。目前有两名主要候选人: 随机特征图哈希技巧。事实证明,后者可以有益地用于随机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;      % 不e: 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
% 不e: 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 不 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不是疏忽的对立面:环境可能是有益的。)第二个方面是标签信息的普及,我广义上讲是指通过数据定义模型质量的能力。对于每种组合,我都会给出一个示例问题。

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

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

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

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

2013年9月21日,星期六

R和D之间的关系

在Microsoft,我是应用研究团队的一部分,从技术上讲是MSR的一部分,但仍在产品团队附近进行部署。微软正在尝试这种结构,因为像许多组织一样,他们希望降低研究与生产之间的阻抗失配。经过这样的一年,我开始体会困难。

请考虑以下情形:一个生产团队遇到一个特殊的问题,该问题最近使他们烦恼,并且感到困惑。他们安排与研究部门的一些主管部门开会,来回讨论,但没有后续行动。发生了什么? (还有相反的情况:研究人员开发或听到了他们认为适用于某些产品的新技术,因此他们安排与产品小组开会,来回进行了一些讨论,但是没有后续行动。我今天不会再讨论。)

我考虑为什么这样的会议在激励和动机方面什么都没有产生。换句话说,由于某些原因,研究人员认为他们的时间有更好的用途。这就引出了一个问题,即一个致力于研究的人的愿望和目标是什么(记住哲学意味着“love of knowledge”)。知识分子一旦获得了最低限度的经济支持,就会激发其他动机。重要的是对声望或追求的渴望。 自我 (与推动博客和开源软件相同的力量)。拐角处反社会不当行为的流行文化学术讽刺画似乎非常不准确:我认识的成功研究人员是高度社交和协作的人,他们认同研究社区并寻求对此的尊重和关注(并影响)。社区。最终,这样的声望可以赎回加入机构(例如,大学或工业研究部门)的机会,与其他聪明人一起闲逛是知识分子的另一个主要动机,因为他们中的许多人认识到聚集效应的非线性力量。换句话说,与孤立的人在一起时,与聪明的人一起闲逛会使您变得更聪明,并为您提供更好的想法,这已被广泛认可。

认识到前者,我试图了解研究人员如何分配自己的时间。首先,我要说的是我不是要规范,或者给研究人员一种以自我为中心的印象。在某种程度上,公司中的每个人都是以自我为中心的,而使活动与团体目标保持一致,在很大程度上与激励措施(包括社会规范)有关。在上一段中应该明确的一件事是,金钱不会成为大多数知识分子的有效诱因,除非您谈论的金钱太多,以至于他们基本上可以建立自己的研究所à拉斯蒂芬·沃尔夫拉姆。就像在VISA广告中一样,有些东西是钱买不到的,事实证明,知识分子想要这些东西。这些事情大体上是:克服知识挑战,与其他聪明人合作以及影响整个研究社区。

回到这个问题,产品团队带给研究人员。问题是否没有足够的挑战性?从我所看到的并不是问题所在:如果有一个简单的解决方案,研究人员将提供一些指导和咨询,每个人都会很高兴。更典型的是,这个问题太过具有挑战性,有时从根本上讲,但是往往更多是由于特质方面。

根本上具有挑战性的问题就像Hal Duame的问题 最近写了关于,而他博客文章中最好的部分是“好吧,我承认:我真的不知道该怎么做。 ”我认为研究人员通常会保持沉默,因为这需要一个非常自信的人说这样的话,尤其是当他们被认为是专家时。对于研究者决定如何分配时间,从根本上讲具有挑战性的问题是有风险的,因为很难从缺乏进展中获得声望。因此,我认为研究人员仅将部分问题集中在根本困难上是合理的。[1](顺便说一句,了解边界在哪里是一门艺术:无限的未知部分具有挑战性,但有可能触手可及,因此值得关注。)有时可以通过启发式方法在基本问题上取得部分进展方法(又名黑客),但很难获得此类活动的社区认可。

与基本挑战相反,由于特质约束而引起的挑战无处不在。毕竟,产品团队通常对某个领域的最新技术水平有些熟悉,这正是促使会议开始的原因。但是,有一些原因导致无法应用直接解决方案,例如,过于昂贵,战略上难以置信,过于复杂以至于无法可靠地实施,与遗留基础架构太不兼容等等。解决此类问题是否与社区是否正常有关。会发现约束很有趣(或者,如果有一位真正的资深思想领袖,无论社区是否可以确信约束很有趣)。有趣通常是通用性的函数,特质问题本身就是特定于问题的。在解决了许多不同的特质问题后,研究人员也许可以通过通用的解决方案总结经验并抽象出一类新的问题,但是将时间分配给特质问题也是一种冒险的策略,希望能有一个概括之所以会出现,是因为没有这种概括,就很难获得社区的认可。

有时问题会带来一个多目标优化方案,该方案超出了概念复杂性的范围。换句话说,尚不清楚哪个更好。在这种情况下,社区可以专注于明确但无关紧要的目标。在 今年的UAI 卡洛斯·乌里韦(Carlos Uribe)表示,就他们所知,更准确地预测Netflix电影的星级不会影响客户体验。他不得不说这样的话,因为几年来,通过在Netflix数据集上做得更好,可以获得最好的论文,并且他希望看到我们专注于其他事情。

那么,拥有数十亿美元研究部门的组织应该如何降低研究与生产之间的阻抗失配?我不知道!我认为答案的一部分是改变有名望的事物。我几乎可以看到一家机构担任«no publications»,不是因为他们害怕告知竞争对手,也不是因为他们没有看到当前收集思想并将其接受同行评审的价值;而是因为管理出版物的外部社区分配了声望,因此有效地控制了研究部门的薪酬。但是我认为这是站不住脚的。因此,取而代之的是,人们必须创建和培育一个场所,在其中容纳特殊性,承认部分解决方案,并且仅考虑实际挑战和经验(即混乱)而做出的贡献。

对我个人而言,很明显我需要更多。我喜欢参加大型的ML会议,例如NIPS,ICML和UAI,但我从未去过KDD。 KDD论文喜欢 值得信赖的在线控制实验:解释了五个令人困惑的结果 建议我错过了。

1


您可能会问:“研究人员不是专心于根本上的困难吗?”视频游戏设计师会告诉您人们喜欢困难但又不太困难的问题。但即使从这个角度来看,也假设研究人员在选择问题时拥有​​全权酌情权。实际上,有职业方面的考虑。此外,随着时间的推移,研究人员会在某个领域投资并开发一定的能力,并且存在转换成本。结果是活动的很大一部分是增量进度。他们被称为大挑战问题是有原因的!

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年7月19日,星期五

使用更少的数据

在一个 以前的帖子 我指出,在进行数据科学时,对较小的数据集进行操作是确保生产率和快速实验的最佳方法之一。在ICML 2013上,我和Nikos提出了 一般策略 使用较少的数据来解决各种各样的问题。

这个想法的灵感来自 类不平衡二次采样启发式。这是计算广告从业者中的一个众所周知的技巧,这种技术的奇特效果一直吸引着我。诀窍在于:当二元分类数据集主要由一个类别的示例组成时,可以对更频繁的类别进行二次采样而不会影响最终分类器的质量。事实证明,我们能够将这一技巧概括如下。

假设您打算通过最小化损失函数$ \ mathcal {L} $(即经验风险最小化(ERM))来从集合$ \ mathcal {H} $中选择假设$ h ^ * $。还要假设有人给您一个假设$ \ tilde h \ in \ mathcal {H} $。您可以在执行ERM之前使用$ \ tilde h $对数据集进行子采样,并且引入的超额风险是适度的(有关确切的超额风险界限,请参见本文)。可以丢弃的数据量取决于$ \ tilde h $的经验损失。如果$ \ tilde h $的经验损失较低,那么您可以主动进行子采样。该策略很简单:以与$ x $上$ \ tilde h $的损失成比例的比率对每个示例$ x $进行采样。您必须对最终子样本进行重要性加权以保持无偏,并在最后一步中将重要性加权的经验损失降至​​最低,但是许多机器学习算法可以直接合并重要性加权(如果没有,则可以使用 将重要性加权损失减少为均匀加权损失 通过拒绝采样)。

在这种解释中,类不平衡子采样启发法对应于使用$ \ tilde h $,它是一个常量预测变量,例如,$ \ forall x,\ tilde h(x)= 0 $对于在正数广告中是一个很好的选择。例子(例如点击)相对较少。但是,此技术的概括适用范围更广。首先,我们有一个非常广泛的损失概念,不仅包括分类,回归,排名和结构化预测。但是还有一些无监督的设置,这些设置可以优化逐点丢失,例如重构错误或困惑。其次,我们允许使用假设集$ \ mathcal {H} $中的任何$ \ tilde h $。通常,对于\\ tilde h $的一个很好的选择是可以容易地按比例估计但损失很小的任何假设。对于类不平衡的问题,最好的常数预测器是很好的,并且很容易按比例估计(只需对标签计数!),但是即使对于那些不平衡的问题,自由选择$ \ tilde h $的能力也具有很大的灵活性。

作为自由选择$ \ tilde h $启用的功能的示例,考虑一下我以前工作过的eHarmony。 eHarmony的一个问题是估计两个人(如果匹配)彼此交流的可能性。 eHarmony已派发约10次6 多年来每天都进行匹配,因此它们拥有庞大的数据集。尽管eHarmony使用数百种功能来预测通信,但仍有一些功能非常有用,而许多功能则非常有用。如果您在会议期间获得了Vaclav Petricek的精彩演讲 UAI 2013推荐研讨会,您知道身高差,年龄差和身体距离是三个具有较高预测价值的功能。仅基于这三个预测变量的预测变量可以轻松地仅使用Hive进行大规模组装,而并非最优的它将损失相对较低。因此,这是$ \ tilde h $的不错的选择。我没有在eHarmony的数据上尝试过此操作,因为在那儿工作时我并不了解这些事情,但是我与Vaclav进行了交谈,他愿意尝试一下。

此技术的一个重要特殊情况是对\\ tilde h $使用线性预测器,对最终ERM使用神经网络或决策树。这很有用,因为线性预测变量可以 估计规模。请注意,要满足定理的条件,您必须确保线性预测变量在$ \ mathcal {H} $中,这对于神经网络意味着从输入到最后一层的直接连接,而对于这两种技术,这意味着非线性预测变量具有访问所有线性特征(可以为最终ERM添加特征)。作为额外的效果,对于线性模型也适用的特征表示也将 也倾向于帮助非线性模型.

因此,现在您有一个原则性的方法可以对巨型数据集进行二次采样,这将在比类不平衡更一般的设置中工作。继续并丢弃一些数据!

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”问题和相关错误得到缓解(这对于顺序预测尤为重要);其次,训练和评估时间码的路径相同,因此在生产中的实现既容易,又不易出错。 请注意,此设置中的评估时间开销很小,因此没有诱惑来重写生产算法。 引入了测试时间开销,但是可以通过使用额外的注释修饰代码来减轻此负担,从而使学习算法能够适当地记忆。 实在太热了,我想自愿在附近尝试一些顺序的预测任务,以尝试一下。

2013年6月6日,星期四

生产力即将等待

我最近发表了有关应用数据科学的实用技巧的演讲,我认为我的最佳观察确实很简单:从业人员要经历长期运行的数据处理过程,这意味着要等待的时间很多。如果您可以减少等待时间,那么这将直接转化为您的生产力。有一部很酷的科幻书,叫做 碳改变 角色将自己上载到模拟器中以便更快地思考:在减少等待的程度上,您正在做类似的事情。

为了使事情简单,我在头脑中将事情分为不同的时间范围:
  1. 立即:不到60秒。
  2. 上厕所休息时间:少于5分钟。
  3. 午休时间:少于1小时。
  4. 隔夜:少于12小时。
即时休息次数是午休时间的20倍以上。您一个月只能工作20天,因此减少等待时间意味着您一天之内就可以完成别人一个月内的工作。 此外,由于您(人类)在面对更长的延迟时会更倾向于尝试执行多任务,并且当人们从即时区域移至洗手间区域时,生产率会出现超线性下降。 在多任务处理方面很恐怖.

这是我避免等待的一些技巧。

使用更少的数据

这是一个简单的策略,但是人们仍然无法利用。在进行试验或调试时,您对数据或软件的了解不足,无法证明对所有数据或软件进行计算都是合理的。正如埃迪·伊扎德(Eddie Izzard)所说, ``缩小一点!''

亚线性调试

这里的想法是随着计算的进行输出足够的中间信息,以在完成之前确定您是否注入了重大缺陷或重大改进。在线学习尤其适用于此,因为它取得了相对稳定的进步并提供了瞬时损失信息,但是可以采用其他技术来做到这一点。学习曲线有时会交叉,但是亚线性调试非常适合立即识别出您已经胖了一些东西。

巧妙的术语由John Langford提供。

线性特征工程

我发现线性模型的工程功能然后在相同表示形式(例如神经网络,梯度提升决策树)上切换到更复杂的模型是一个富有成果的模式,因为线性模型的速度有助于快速实验。某些适用于线性模型的事物将倾向于适用于其他模型。当然,要设计出适用于线性模型的特征比较困难。另外,您必须牢记要使用的最终模型,例如,如果最终要使用树,则单变量的单调变换只会对线性模型有所帮助。

将代码移至数据

这是Hadoop的存在点,但是即使在更简单的设置中,确保您在数据所在的位置附近进行工作也可以节省宝贵的传输时间。如果您的数据位于云存储提供商中,请在同一数据中心内启动虚拟机。

2013年5月5日,星期日

数据量大:相应地编码!

机器现在越来越大,越来越快:您可以租用一台具有244 GB RAM和数十个内核的机器,用于$每小时3.50。这意味着您可以删除庞大的数据集,而不必担心分布式编程的麻烦(如Jeff Hodges所指出的那样,``一台机器本地的问题很容易``)但是我尝试的大多数机器学习软件都不能真正胜任该任务,因为它没有尊重以下事实: 数据量大。对于想编写机器学习软件并希望通过使用大型单机进行扩展的人们来说,这是我的一些想法。

需要记住的数字是I / O昂贵;在单机环境中,尤其是将数据移入磁盘或从磁盘移出数据。当一件软件强迫您不必要地将数据移入或移出磁盘时,例如,强迫您将多个文件组合成一个文件,强迫您解压缩数据,或更普遍地强迫您实现任何易于计算的形式,这会很痛苦。数据转换。这里有一些避免引起最终用户(包括您自己!)痛苦的方法。

首先,如果可以的话,请流式传输数据,而不是在数据中随意查找。为什么这很重要?因为如果程序将输入视为流,则可以在输入到程序之前按需在内存中对其进行转换,这使程序的用途更加广泛。仅此一项就解决了许多其他问题。例如,如果我的数据分散在多个文件中,我可以即时将它们连接成一个流,或者如果我的数据以有趣的格式压缩,则可以即时对其进行解压缩。现在您可能会说``嘿,我没有在线算法'',但是尽管如此,许多程序还是错过了以流形式访问其输入的机会。例如,(否则确实很棒!) 线性 在数据上进行两次精确的顺序传递(第一个确定维度,第二个将数据读入核心),但是在这两次传递之间它调用 倒带。倒带的电话使事情变得非常困难。如果相反,liblinear仅关闭并重新打开了文件,那么我可以使用命名管道来玩弄技巧,以避免各种I / O。更好的是,如果liblinear允许一个文件指定两个文件而不是一个文件(第二个文件规范是可选的,默认是第二个文件与第一个文件相同),那么事情就变得容易了,因为 流处理重定向 技巧可以承担。 las,它都不做这些事情。

宗教上遵守流媒体访问模式是最佳的实践模式,但有时是不可能的。在那种情况下,仍然可以支持一些常见的模式。 不要让我串联文件:比这差 无用的猫,这是痛苦的缓慢,不必要地使用了猫。如果可以采用一个文件参数,则可以采用多个文件参数,就像它们被串联一样。 不要让我解压缩数据:您应该支持直接读取压缩数据。这不仅消除了实现数据的解压缩版本的需要,而且读取压缩数据并即时对其进行解压缩也比读取解压缩数据要快。 允许我假装输入比实际小 并且仅让您的程序在输入的第一个指定单位上运行(例如,前10000条记录);这有助于对逐渐更大的数据部分进行实验。 (我说数据科学就像求爱一样;我不喜欢一路走动去处理大量的数据,直到我偶然遇到了一些规模较小的偶然事件)。同样,如果您对待输入作为一个流,我可以在不需要您程序的额外帮助的情况下实现所有这些目标和其他目标,因此,这些警告仅适用于出于任何原因需要无顺序访问其输入的那些人。顺便说一下,您可以判断是否将输入视为流:只能执行打开,读取和关闭操作。

很少有机器学习工具包可以完全达到另一个层次,这是一个 DSL 用于实时数据转换。如果程序将输入数据视为流,并且只要转换后的数据不会太大,则可以使用进程间通信来模拟,而无需使用进程间通信来实现。 IPC 是可以接受的。这是mnist演示中的示例shell脚本摘录 Vowpal兔子
SHUFFLE='BEGIN { srand 69; };
         $i = int rand 1000;
         print $b[$i] if $b[$i];
         $b[$i] = $_; } { print grep { defined $_ } @b;'

paste -d' '                                                             \
  <(zcat train8m-labels-idx1-ubyte.gz | ./extract-labels)               \
  <(zcat train8m-images-idx3-ubyte.gz | ./extractpixels) |              \
perl -ne ${SHUFFLE} |                                                   \
./roundrobin ./pixelngrams 3 |                                          \
time ../../vowpalwabbit/vw --oaa 10 -f mnist8分钟11png.model               \
   -b 20 --adaptive --invariant                                         \
   --nn 5 --inpass                                                      \
   -l 0.05
在没有中间实现到磁盘的情况下,这里要解决的问题是:1)标签和数据位于不同的文件中(它们不是面向行的),需要将它们连接在一起; 2)有助于稍微整理数据以打破顺序相关性 新元;和3)需要计算其他像素图特征,这是CPU密集型的,因此为此使用了3个内核(通过辅助脚本循环)。

因此,上面看起来不错,为什么我们需要DSL才能在机器学习软件内部进行即时数据转换?一个很大的原因是中间体变大,IPC和解析输入的开销变得很大。在这种情况下,最好将转换推迟到学习核心内部(例如, 棺材)。的 -q , - 立方体--ngram Vowpal兔子的论点构成一种简单的迷你语言,具有很大的实际实用性;更好的是像 R公式.

2013年4月30日,星期二

学习比优化容易

此博客文章的标题是一个短语,归因于 莱昂·波托(Leon Bottou) (尽管您不会从网络搜索中了解到这一点:显然,创业社区有一个 类似的格言)。这是机器学习中为数不多的深层真理之一,我认为在进入一个勇敢的新世界时要牢记这一点特别重要 数据指数压倒了计算指数。要点是,训练错误是我们真正关心的泛化错误的代名词,因此,过度花费计算精力来优化训练错误可能会适得其反。适得其反产生于(至少)两种不同的方式。首先是过多的计算工作可能会导致您使用较少的数据来补偿计算时间,而使用较少的数据意味着代理的准确性较低。第二个是不太积极的优化可以充当正则化器,当用``更好''的优化例程进行校正时,实际上会导致更严重的泛化错误。

我想到了这种现象的两个例子。一,主导地位 随机梯度下降 (SGD)。当神经网络首次出现时,SGD是唯一的优化算法,但人们很快开始尝试使用基于准牛顿的更先进技术。如今,神经网络仍然使用接近SGD的算法进行训练,可以说,我们今天看到的主要区别在于体系结构和正则化器(而体系结构是一种正则化器)。事实是,SGD是一种一般的优化算法,但它是一种很棒的学习算法。

第二个例子是 哈希技巧。对于在实际矢量表示上运行的算法(即所有算法afaik),必须将特征转换为索引,因此一种策略是构建和维护字典将特征映射到索引。对于非常高的基数特征空间,这不仅繁琐,而且可能导致无法满足的内存需求。当使用散列技巧时,将散列函数应用于特征标识以便确定特征索引。第一次遇到这种情况的每个人都认为:“那里没有碰撞吗?”。答案是:“是的,有冲突”,“在实践中似乎没有多大关系”。可以谈论它如何保留期望的点积,或者说在存在冗余的情况下统计稳定的联结特征如何提供信息,但这是真正的巧妙之处:我已经看到很多例子,其中增加了位数哈希函数会降低性能。换句话说,冲突更少,但泛化能力更差;这是因为哈希冲突为模型的复杂性提供了有用的约束, 学习比优化容易.

好吧,那又如何呢?我们所有人都应该在编码中草率行事吗? 通过把自己扔在地上而失踪飞行?不,但我认为值得保持开放的态度。特别是,要跟上现代数据的洪流,就需要开发分布式算法,而并行编程的最大低效率之一就是同步。因此,我建议对无同步学习算法保持开放的态度。

牛等等他们一直在这种思维的最前沿 霍格威尔德! 关于共享表示形式的无锁并行SGD的建议。当我第一次听说这件事时,我想:“那不可能。”但是,这就是我第一次听说该哈希技巧时所想到的。所以我还没有尝试过霍格威尔德!就个人而言,我不能保证,但是我也不愿意将其驳回。

而牛等。等建议做``脏写'', 松岛等等 提出更直观的``脏读''想法。在提出的多个想法中,有一个解析线程可以维护示例的缓冲区,而并发学习线程可以从缓冲区中训练示例,而这两者之间的同步最少。对于许多在线算法而言,解析是瓶颈,因此学习算法会在解析线程替换示例之前按预期对每个示例进行几次训练。因此,这看起来像一个迷你批处理算法,但是随着时间的推移,迷你批处理的变化缓慢,这听起来是个好主意。我在和他们玩 流支持 软件,手指交叉!

2013年3月15日,星期五

mnist演示

我已经检查了两个演示到的主要分支 威杜布 在里面 演示/ 目录,其中之一是 mnist 基于。该演示练习了由“一反所有”归约构成的神经网络归约。 mnist是规范的神经网络测试数据集,包括从灰度像素表示开始的10位多类分类问题。对于没有完全利用空间结构的方法,现有技术的测试误差约为0.8%,对于利用一切的邪恶集合体的测试误差约为0.25%。使用vee-dub时,对原始像素使用神经网络在mnist上进行训练时的测试错误率为2.2%(在我的台式机的一个核心上花费5分钟),而在mnist上进行训练时的测试错误率为1.1%。 mnist8分钟 (在我的台式机的一个核心上需要一个小时)。

上面的数字是可以的,但不会给任何顽固的神经网络爱好者留下深刻的印象。但是,vee-dub中的神经网络支持并非旨在取代传统特征工程,而是对其进行补充:这是 大声一点 风格。

令人惊讶的是,一点要素工程的效果如何。我已经注意到 n克帮助mnist 但是vee-dub中内置的n-gram支持是针对文本而设计的,因此是一维的。因此我写了一个 小程序 计算垂直,水平和对角线像素n-gram,并将其输入到vee-dub。在mnist上训练时,像素为n-gram的线性模型的测试误差为1.75%,使用3个核进行训练需要1分钟。这些核心中有2个被占用来计算像素n-gram,实际上vee-dub比2个特征提取过程要快,因此在不影响挂钟训练吞吐量的情况下,仍有空间添加一些隐藏单元。仅添加1个隐藏单元(每个班级)可将测试误差降至1.6%,而完全不影响培训时间。在mnist8m上训练像素n-gram线性模型会导致测试误差为1.25%。使用4个核心需要一个小时,其中3个专职用于计算像素n-gram。再次,vee-dub并不是瓶颈,添加5个隐藏单元(每个班级)可使测试误差降至0.9%,而不会影响训练时间。这使vee-dub受到尊重。

在mnist8m上进行培训,尽管对计算的要求更高,但总是有帮助的。 mnist8分钟是通过采用mnist训练集并将其变形的方式构造的,该方式对预测变量进行编码(将其视为利用空间结构),从而对预测变量进行编码。这是一个古老的想法,至少可以追溯到1994年,当时是Abu Mostafa的 提示学习 论文,另外表明可以从未标记的数据构建虚拟示例。虚拟示例是一种成功态度的一部分,它表示1)首先提高模型的复杂性,然后2)担心正则化。还有其他通用的方式进行正则化(例如,装袋,辍学,正确的贝叶斯推断),但虚拟示例可让您编码特定于问题的信息并利用未标记的数据,因此我认为它们很不错。

mnist8分钟数据集由Loosli,Canu和Bottou作为社区服务实现;他们的软件在运行过程中产生了不变的变形,因此虚拟示例可能仍然短暂。这可以很好地映射到vee-dub简化架构,因为可以轻松编写一个简化来从在线实际示例中动态构建临时虚拟示例的简化。

2013年2月21日,星期四

大声一点

我和尼科斯最近 向vee-dub添加了神经网络 通过减少。这不是深度学习的实现,它只是一个隐藏层,因此您可能会问``这有什么意义?''我们最初的动机是仅使用vee-dub赢得一些Kaggle比赛。尽管最近我一直很忙,无法参加任何比赛,但是减少的效果符合预期。特别是,我希望可以通过对线性模型有利的工程特征来继续解决大多数问题,并在末尾添加一些隐藏单元以进一步提高性能。在谈论一个 计算与数据集大小的权衡,但这是一个更明确的示例。

来自的拼接站点数据集 2008年Pascal大规模学习挑战赛 是5000万个标记的DNA序列的集合,每个序列的长度为200个碱基对。就我们的目的而言,这是一个字母有限的字符串的二进制分类问题。这里有些例子:
% paste -d' ' <(bzcat dna_train.lab.bz2) <(bzcat dna_train.dat.bz2) | head -3
-1 AGGTTGGAGTGCAGTGGTGCGATCATAGCTCACTGCAGCCTCAAACTCCTGGGCTCAAGTGATCCTCCCATCTCAGCCTCCCAAATAGCTGGGCCTATAGGCATGCACTACCATGCTCAGCTAATTCTTTTGTTGTTGTTGTTGAGACGAAGCCTCGCTCTGTCGCCCAGGCTGGAGTGCAGTGGCACAATCTCGGCTCG
-1 TAAAAAAATGACGGCCGGTCGCAGTGGCTCATGCCTGTAATCCTAGCACTTTGGGAGGCCGAGGCGGGTGAATCACCTGAGGCCAGGAGTTCGAGATCAGCCTGGCCAACATGGAGAAATCCCGTCTCTACTAAAAATACAAAAATTAGCCAGGCATGGTGGCGGGTGCCTGTAATCCCAGCTACTCGGGAGGCTGAGGT
-1 AAAAGAGGTTTAATTGGCTTACAGTTCCGCAGGCTCTACAGGAAGCATAGCGCCAGCATCTCACAATCATGACAGAAGATGAAGAGGGAGCAGGAGCAAGAGAGAGGTGAGGAGGTGCCACACACTTTTAAACAACCAGATCTCACGAAAACTCAGTCACTATTGCAAGAACAGCACCAAGGGGACGGTGTTAGAGCATT
事实证明,如果将这些字符串分解为$ n $ -grams,则逻辑回归效果很好。这是一个小程序,它将DNA序列处理成4克并输出vee-dub兼容格式。
% less Quaddna2vw.cpp
#include <iostream>
#include <string>

namespace
{
  using namespace std;

  unsigned int
  codec (const string::const_iterator& c)
    {
      return *c == 'A' ? 0 :
             *c == 'C' ? 1 :
             *c == 'G' ? 2 : 3;
    }
}

int
main (void)
{
  using namespace std;

  while (! cin.eof ())
    {
      string line;

      getline (cin, line);

      if (line.length ())
        {
          string::const_iterator ppp = line.begin ();
          string::const_iterator pp = ppp + 1;
          string::const_iterator p = pp + 1;
          unsigned int offset = 1;

          cout << " |f";

          for (string::const_iterator c = p + 1;
               c != line.end ();
               ++ppp, ++pp, ++p, ++c)
            {
              unsigned int val = 64 * codec (ppp) +
                                 16 * codec (pp) +
                                  4 * codec (p) +
                                      codec (c);

              cout << " " << offset + val << ":1";
              offset += 256;
            }

          cout << endl;
        }
    }

  return 0;
}
我将使用以下Makefile来驱动学习渠道。
% less Makefile
SHELL=/bin/zsh
CXXFLAGS=-O3

.SECONDARY:

all:

%.check:
        @test -x "$$(which $*)" || {                            \
          echo "ERROR: you need to install $*" 1>&2;            \
          exit 1;                                               \
        }

dna_train.%.bz2: wget.check
        wget ftp://largescale.ml.tu-berlin.de/largescale/dna/dna_train.$*.bz2

quaddna2vw: Quaddna2vw.cpp

quaddna.model.nn%: dna_train.lab.bz2 dna_train.dat.bz2 Quaddna2vw 大众.check
        time paste -d' '                                        \
            <(bzcat $(word 1,$^))                               \
            <(bzcat $(word 2,$^) | ./quaddna2vw) |              \
          tail -n +1000000 |                                    \
        大众 -b 24 -l 0.05 --adaptive --invariant                 \
          --loss_function logistic -f $@                        \
          $$([ $* -gt 0 ] && echo "--nn $* --inpass")

quaddna.test.%: dna_train.lab.bz2 dna_train.dat.bz2 quaddna.model.% Quaddna2vw 大众.check
        paste -d' '                                             \
          <(bzcat $(word 1,$^))                                 \
          <(bzcat $(word 2,$^) | ./quaddna2vw) |                \
        head -n +1000000 |                                      \
        大众 -t --loss_function logistic -i $(word 3,$^) -p $@

quaddna.perf.%: dna_train.lab.bz2 quaddna.test.% perf.check
        paste -d' '                                             \
          <(bzcat $(word 1,$^))                                 \
          $(word 2,$^) |                                        \
        head -n +1000000 |                                      \
        perf -ROC -APR
这是使用logistic回归对数据进行一次sgd传递的结果。
% make quaddna.perf.nn0
g++ -O3 -I/home/pmineiro/include -I/usr/local/include -L/home/pmineiro/lib -L/usr/local/lib  Quaddna2vw.cpp   -o Quaddna2vw
time paste -d' '                                        \
            <(bzcat dna_train.lab.bz2)                          \
            <(bzcat dna_train.dat.bz2 | ./quaddna2vw) |         \
          tail -n +1000000 |                                    \
        大众 -b 24 -l 0.05 --adaptive --invariant                 \
          --loss_function logistic -f quaddna.model.nn0                 \
          $([ 0 -gt 0 ] && echo "--nn 0 --inpass")
final_regressor = quaddna.model.nn0
Num weight bits = 24
learning rate = 0.05
initial_t = 0
power_t = 0.5
using no cache
Reading from
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
0.673094   0.673094            3         3.0  -1.0000  -0.0639      198
0.663842   0.654590            6         6.0  -1.0000  -0.0902      198
0.623277   0.574599           11        11.0  -1.0000  -0.3074      198
0.579802   0.536327           22        22.0  -1.0000  -0.3935      198
...
0.011148   0.009709     22802601  22802601.0  -1.0000 -12.1878      198
0.009952   0.008755     45605201  45605201.0  -1.0000 -12.7672      198

finished run
number of examples = 49000001
weighted example sum = 4.9e+07
weighted label sum = -4.872e+07
average loss = 0.009849
best constant = -0.9942
total feature number = 9702000198
paste -d' ' <(bzcat dna_train.lab.bz2)   53.69s user 973.20s system 36% cpu 46:22.36 total
tail -n +1000000  3.87s user 661.57s system 23% cpu 46:22.36 total
vw -b 24 -l 0.05 --adaptive --invariant --loss_function logistic -f    286.54s user 1380.19s system 59% cpu 46:22.43 total
paste -d' '                                             \
          <(bzcat dna_train.lab.bz2)                            \
          <(bzcat dna_train.dat.bz2 | ./quaddna2vw) |           \
        head -n +1000000 |                                      \
        大众 -t --loss_function logistic -i quaddna.model.nn0 -p quaddna.test.nn0
only testing
Num weight bits = 24
learning rate = 10
initial_t = 1
power_t = 0.5
predictions = quaddna.test.nn0
using no cache
Reading from
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
0.000020   0.000020            3         3.0  -1.0000 -17.4051      198
0.000017   0.000014            6         6.0  -1.0000 -17.3808      198
0.000272   0.000578           11        11.0  -1.0000  -5.8593      198
0.000168   0.000065           22        22.0  -1.0000 -10.5622      198
...
0.008531   0.008113       356291    356291.0  -1.0000 -14.7463      198
0.008372   0.008213       712582    712582.0  -1.0000  -7.1162      198

finished run
number of examples = 1000000
weighted example sum = 1e+06
weighted label sum = -9.942e+05
average loss = 0.008434
best constant = -0.9942
total feature number = 198000000
paste -d' '                                             \
          <(bzcat dna_train.lab.bz2)                            \
          quaddna.test.nn0 |                                    \
        head -n +1000000 |                                      \
        perf -ROC -APR
APR    0.51482
ROC    0.97749
挂钟训练时间为47分钟,测试APR为0.514。 (如果仔细阅读以上内容,您会注意到我将文件的前一百万行用作测试数据,将其余的几行用作训练数据。)大规模学习挑战的条目的APR约为0.2,这是从unigram logistic回归中得到的,而此数据集上最著名的方法需要多个核心天才能计算并获得约0.58的APR。

在以上运行期间 Quaddna2vw 使用100%的1 cpu和 大众 使用约60%的另一个。换一种说法, 大众 这不是瓶颈,我们可以花一些额外的cpu学习,而不会产生实际的挂钟影响。因此,通过指定少量隐藏单元并通过输入直接连接到输出层,可以大声一点 --nn 8 --inpass。其他所有内容都相同。
% make quaddna.perf.nn8
time paste -d' '                                        \
            <(bzcat dna_train.lab.bz2)                          \
            <(bzcat dna_train.dat.bz2 | ./quaddna2vw) |         \
          tail -n +1000000 |                                    \
        大众 -b 24 -l 0.05 --adaptive --invariant                 \
          --loss_function logistic -f quaddna.model.nn8                 \
          $([ 8 -gt 0 ] && echo "--nn 8 --inpass")
final_regressor = quaddna.model.nn8
Num weight bits = 24
learning rate = 0.05
initial_t = 0
power_t = 0.5
using input passthrough for neural network training
randomly initializing neural network output weights 和 hidden bias
using no cache
Reading from
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
0.600105   0.600105            3         3.0  -1.0000  -0.2497      198
0.576544   0.552984            6         6.0  -1.0000  -0.3317      198
0.525074   0.463309           11        11.0  -1.0000  -0.6047      198
0.465905   0.406737           22        22.0  -1.0000  -0.7760      198
...
0.010760   0.009331     22802601  22802601.0  -1.0000 -11.5363      198
0.009633   0.008505     45605201  45605201.0  -1.0000 -11.7959      198

finished run
number of examples = 49000001
weighted example sum = 4.9e+07
weighted label sum = -4.872e+07
average loss = 0.009538
best constant = -0.9942
total feature number = 9702000198
paste -d' ' <(bzcat dna_train.lab.bz2)   58.24s user 1017.98s system 38% cpu 46:23.54 total
tail -n +1000000  3.77s user 682.93s system 24% cpu 46:23.54 total
vw -b 24 -l 0.05 --adaptive --invariant --loss_function logistic -f    2341.03s user 573.53s system 104% cpu 46:23.61 total
paste -d' '                                             \
          <(bzcat dna_train.lab.bz2)                            \
          <(bzcat dna_train.dat.bz2 | ./quaddna2vw) |           \
        head -n +1000000 |                                      \
        大众 -t --loss_function logistic -i quaddna.model.nn8 -p quaddna.test.nn8
only testing
Num weight bits = 24
learning rate = 10
initial_t = 1
power_t = 0.5
predictions = quaddna.test.nn8
using input passthrough for neural network testing
using no cache
Reading from
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
0.000041   0.000041            3         3.0  -1.0000 -15.2224      198
0.000028   0.000015            6         6.0  -1.0000 -16.5099      198
0.000128   0.000247           11        11.0  -1.0000  -6.7542      198
0.000093   0.000059           22        22.0  -1.0000 -10.7089      198
...
0.008343   0.007864       356291    356291.0  -1.0000 -14.3546      198
0.008138   0.007934       712582    712582.0  -1.0000  -7.0710      198

finished run
number of examples = 1000000
weighted example sum = 1e+06
weighted label sum = -9.942e+05
average loss = 0.008221
best constant = -0.9942
total feature number = 198000000
paste -d' '                                             \
          <(bzcat dna_train.lab.bz2)                            \
          quaddna.test.nn8 |                                    \
        head -n +1000000 |                                      \
        perf -ROC -APR
APR    0.53259
ROC    0.97844
从挂钟的角度来看,这是免费的:总培训时间增加了1秒,并且 大众Quaddna2vw 现在吞吐量大致相等。同时,实际年利率从0.515增加到0.532。这说明了一个基本思想:设计出适合您的线性模型的特征,然后当您精疲力尽时,尝试添加一些隐藏的单元。就像转动设计矩阵 最多十一.

我推测由于自适应梯度导致的学习速率安排,正在发生类似于梯度增强的事情。具体而言,如果直接连接的收敛速度比隐藏单元的收敛速度快,则可以有效地要求它们对线性模型中的残差进行建模。这表明一种更明确的强化形式可能会产生更好的免费午餐。













2013年1月2日,星期三

NIPS 2012趋势

我认为我应该对我今年在NIPS上观察到的一些趋势发表评论,而不是发表论文清单。

深度学习又回来了

对于真正的忠实的深度学习,我们再也没有离开过,但对于其他所有人,最近的一些新发展都对它们有利。

首先,数据集越来越大。更大的数据集意味着可以考虑更复杂的模型族而不会过度拟合。一旦数据集变得太大,超过了计算约束,但在10区5 to 106 行和102 to 103 专栏深度学习的计算成本是可以容忍的,并且该区域包含许多具有较高经济价值的数据集。

第二,数据集已经公开。称之为 卡格勒 如果您愿意的话,会产生影响,尽管纯粹是学术项目,例如 影像网 也很重要一旦更大的兴趣数据集成为公众有意义的技术比较就成为可能。这是一篇快速的论文阅读提示:论文的那一部分讨论论文的方法比其他方法更好,您可以跳过该部分,因为该部分中的数字受到特定的选择压力:作者不断试验他们的技术,直到证明它更好为止,而他们对竞争技术却没有同样的热情。另一方面,如果存在这样一种情况,技术A的支持者在数据集上尽可能地努力,而技术B的支持者在数据集上尽可能地努力,那么知道谁做得更好就更有趣了。 。深度学习社区受益于此类匹配,因为归根结底,它们非常注重经验。

第三,数据集变得更加多样化。如果您对域有足够的直觉来选择特征和/或内核,则线性方法会很好用。在没有领域知识的情况下,非凸优化可以提供替代。

多核和GPU驱动的计算机的兴起推动了这些趋势。虽然深度学习通常是深度神经网络的同义词,但我们可以退一步说,深度学习实际上是通过非凸优化(通常由SGD驱动)进行学习。不幸的是,由于对带宽的高要求,SGD在分布式环境中的表现不佳。具有多核或多个GPU卡的单台计算机实质上是一个具有高速互连的小型集群,有助于解决SGD的某些局限性(以及流水线和迷你分批处理)。我认为,与分布式方法相比,近期技术更倾向于使用GPU方法进行深度学习(例如 信仰区),因为存在经济压力,需要增加GPU的内存带宽以用于计算机游戏。我偏爱深度学习的分布式方法,因为在实践中,数据的可操作存储通常是一个集群,因此 原位 操纵是可取的。不幸的是,我认为这将需要一种截然不同的方法,即选择非凸性,其明确的设计目标是允许有效的分布式优化。在这些方面取得突破之前,我的钱都花在了GPU上。

概率编程

概率编程是一种建模方式,其中用户以声明方式对生成的模型和一些所需的后验摘要进行编码,然后系统将该规范转换为答案。
声明性系统是计算机科学中纯正的典范。在实践中,声明性系统面临采用方面的障碍,因为除非所讨论的域被很好地抽象,否则最终用户不可避免地会发现特定于域的语言的局限性难以忍受。如果领域是抽象的,那么如果存在广泛适用的通用策略和优化,声明式系统就会蓬勃发展,因为即使是最有经验和才华的程序员也会发现声明式框架更具生产力(至少对于原型设计而言,很可能对于完成的产品)。

因此,这里有个好消息:对于贝叶斯主义者,通过蒙特卡洛进行后验汇总时,大量的机器学习都被很好地抽象了。此外, 没有掉头采样器 看起来像是一种广泛适用的策略,某些其他技术(例如自动微分和符号模型简化)则提供了正确性和(相对)速度的希望。总的来说,这看起来像灌篮。

潜在模型的光谱方法

I 关于此的博客 已经广泛。 tl; dr是频谱方法通过消除E-step保证了更多可扩展的潜在模型学习。以我的经验,主题模型为许多领域中的后续监督分类(不只是文本!)提取了出色的功能,因此实际上这是一个令人兴奋的发展。同样,将主题模型视为提取高阶矩特征值的观点也给出了一些直觉,即它们为何具有广泛的用途。