2014年12月15日,星期一

NIPS 2014

With a new venue 和 a 深 在titude, NIPS was a blast this year, kudos to the organizers.

让我们从“会议讲话 ”。我的意思是本着时代精神“Man of the Year”,即我不宽容内容,只是指出内容最有影响力。当然,赢家是...伊利亚·萨兹维克(Ilya Sutsveker)的演讲 神经网络的序列到序列学习. The swagger was jaw-dropping: as introductory material he declared that all supervised vector-to-vector problems are now solved thanks to 深 feed-forward neural networks, 和 then proceeded to declare that all supervised sequence-to-sequence problems are now solved thanks to 深 LSTM networks. Everybody had something to say about this talk. On the positive side, the inimitable 约翰·赫尔希 在喝酒时告诉我,LSTM允许他的团队清除语音清洁管道中的多年积垢,同时获得更好的结果。其他对这次演讲的慈善解释较差的人可能不希望我在博客上写下他们陶醉的反应。

It is fitting that the conference was in Montreal, underscoring that the giants of 深 learning have transitioned from exiles to rockstars. As I learned the hard way, you have to show up to the previous talk if you want to get into the room when one of these guys is scheduled 在 a workshop. Here's an actionable observation: placing all the 深 learning posters next to each other in the poster session is a bad idea, as it creates a ridiculous traffic jam. Next year they should be placed 在 the corners of the poster session, just like staples in a grocery store, to facilitate the exposure of other material.

现在我的个人亮点。首先,我要指出的是,这次会议是如此之大,以至于即使使用单轨格式,我也只能体验其中的一小部分,因此您的观点有偏差。也让我祝贺安树 最佳论文奖。他今年夏天是微软的实习生,这个家伙真是太酷了。

分布式学习

既然这是我的日常工作,我当然会感到困惑,因为各个计算节点(增强了GPU)的功能越来越强大,因此分布式学习的需求正在减少。所以我准备好迎接朱尔·莱斯科维奇的 专题讲座。这是一个杀手screenshot。
杰瑞说,每个研究生实验室都是其中一台机器,几乎所有感兴趣的数据都适合RAM。考虑一下。

尽管如此,在这个方向上还是有一些很好的研究。

其他趋势

随机方法:我现在真的很喜欢随机算法,因此很高兴看到太空中的健康活动。 LOCO(如上所述)是一大亮点。也很酷 拉达格勒,这是Adagrad和随机投影的混搭。实际上,Adagrad是通过对角线近似实现的(例如,在vowpal wabbit中),但Krummenacher和McWilliams表明,可以通过随机投影轻松地获得完整Adagrad度量的近似值。它使数据致密,因此也许不适合文本数据(并且vowpal wabbit当前专注于稀疏数据),但是密集数据(即视觉,语音)和非线性模型(即神经网络)的潜力是有希望的。

极限学习 Clearly someone internalized the most important lesson from 深 learning: give your research program a sexy name. Extreme learning sounds like the research area for those who like skateboarding 和 consuming a steady supply of Red Bull. What it actually means is multiclass 和 multilabel classification problems where the number of classes is very large. I was pleased that Luke Vilnis' talk on 大型多类问题的广义特征向量 受到好评。安树最佳论文获奖作品 近似最大内部产品搜索 也与此领域有关。

离散优化 我很无知 这个领域 我在行李领取时遇到了Jeff Bilmes,并请他告诉我他的研究兴趣。但是,假设Ilya是正确的,未来将是学习具有更复杂的输出结构的问题,并且该领域正在朝着一个有趣的方向发展。

概率编程 罗布·辛科夫(Rob Zinkov)没有出席(afaik),但他向我展示了一些病态的演示 ru,他的实验室正在开发的概率编程框架。

Facebook实验室 我很高兴看到Facebook Labs 解决雄心勃勃的问题 进行文本理解,图像分析和知识库建设。他们在想大...极端的收入不平等可能不利于西方民主国家的长期稳定,但这在AI研究中掀起了黄金时代。

结论

最好。会议。曾经我等不及明年。

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 embeddings: 国王-皇后$ \大约$男人-女人.

2014年10月21日,星期二

死后的反驳

艾萨克·阿西莫夫(Isaac Asimov)最近发表的一篇文章,标题为 论创造力 部分反驳 我以前的帖子。这是一个关键摘录:
因为没有赚到钱而感到内’在我看来,因为没有一个好主意的薪水是确保下一次也不会有好主意的最可靠方法。
我同意阿兹莫夫的所有文章。根据我的经验,它可以使真理产生共鸣,例如,我与不惧怕看起来很愚蠢的人之间的合作效率最高。

那么如何与研究由某种程度上关心``投资回报率''的人资助的现实相吻合呢?

我不太确定,但我会做一个流行文化的比喻。我目前正在欣赏该系列 尼克斯,这是关于20世纪初期的医学实践。在开幕式上,医生们使用当时的学术术语和方法在教学手术室演示手术。该患者与当时所有患者一样死亡,因为当时的前置胎盘手术死亡率为 100%。随着时间的流逝,程序有所改善,现在的死亡率很低,但是当时,医生只是不知道自己在做什么。学术态度是发信号``我们正在尽力而为,努力进取''的一种方式。

我们仍然不知道如何从工业研究中可靠地产生``投资回报''。阿兹莫夫的观点是,为提高研究效率而提出的许多机制实际上是相反的。因此,前进的道路还不清楚。目前,我最好的想法就是专业地操守自己,寻找机会为老板提供价值,同时朝着我认为有趣的方向发展,并在合理的时间内对业务产生积极影响帧。在这个特定时刻,机器学习非常实用,因此并不是很难,但是对于其他领域的研究人员而言,这种平衡的行为将更加困难。

2014年10月16日,星期四

成本与收益

tl; dr:如果您热爱研究,并且您是一名专业研究人员,则您有道义上的义务来确保您的恩人既可以从研究中获得一些收益,也可以意识到收益。

我喜欢研究。伟大的研究至少在两个方面是美丽的。首先,它揭示了我们所生活的世界的真相。其次,它展现了人类最高绩效的内在美。伟大的研究者是美丽的,就像伟大的艺术家或运动员是美丽的。 (诺亚·史密斯 显然同意。)不幸的是, 五百万人 不会支付观看优秀研究人员表演技艺的门票,因此需要其他资助工具。

Recent events have me thinking again about the viability of privately funded basic research. In my opinion, the history of Xerox PARC is 深ly troubling. What?! At it's peak the output of Xerox PARC was breathtaking, 和 许多 advances in computation that became widespread during my youth 可以追溯到Xerox PARC。不幸的是,施乐没有从其研发部门的一些世界上变化最大的创新中受益。现在,一代人的MBA被告知 思科模式,而不是拥有自己的研究部门,而是等待其他公司进行创新,然后再购买它们。
...它继续收购小型创新公司,而不是从头开始开发新技术...
要明确的是,我的雇主微软仍然对基础研究表现出坚定的决心。此外,Microsoft最近的研究裁员与研究质量或该研究对Microsoft产品的影响无关。 这篇文章与微软无关,它与激励和经济学的强大力量有关。

Quite simply, it is irrational to expect any institution to fund an activity unless that organization can realize sufficient benefit to cover the costs. That calculation is ultimately made by people, 和 if those people only hear stories about how basic research generates benefits to other firms (or even, competitors!), appetite will diminish. In other words, benefits must not only be real, they must be recognizable to decision makers. This is, of course, a 深 challenge, because the benefits of research are often not recognizable to the researchers who perform it. Researchers are compelled to research by their nature, like those who feel the need to scale Mount Everest. It so happens that a byproduct of their research obsession is the advancement of humanity.

因此,如果您是一名专业研究人员,那么从逻辑上讲,作为对科学和人类进步的热情的一部分,您应该努力使活动的收益对支持您的任何机构都很重要,因为您希望您的资助工具能够长期可行。此外,让我们认识一些很棒的人:研究部门的经理们不断在董事会中倡导预算,以便部门中的人们可以做得很好。

2014年9月24日,星期三

子线调试

I have a post on 亚线性调试 on 微软的机器学习博客.
在线学习算法是一类机器学习(ML)技术,它们将输入作为流使用,并在它们使用输入时进行调整。它们通常用于计算方面的需求,例如速度,使用大数据集的能力以及处理非凸目标的能力。但是,它们还有另一个有用的好处,即“sub-linear debugging”.
如果您有兴趣点击 多赫蒂阈值 在机器学习中,阅读 整件事!

2014年8月26日,星期二

更多深度学习的困惑


Yoshua Bengio, one of the luminaries of the 深 learning community, gave multiple talks about 深 learning 在 集成电路 2014 this year. I like Bengio's focus on the statistical aspects of 深 learning. Here are some thoughts I had in response to his presentations.

通过深度进行正则化

Bengio的话题之一是深度是一种有效的调节器。该论点是这样的:通过组合多层(有限容量)非线性,相对于相似的前导灵活性的浅层模型,整体体系结构能够探索有趣的高柔性模型子集。在这里有趣的是,这些模型具有足够的灵活性来对目标概念进行建模,但是受到足够的约束,仅需适度的数据需求即可学习。这实际上是关于我们正在尝试建模的目标概念的声明(例如,在人工智能任务中)。另一种说法是(释义)“寻找比平滑度假设更具约束力的正则化器,但仍广泛适用于感兴趣的任务。”

是这样吗

As a purely mathematical statement it is definitely true that composing nonlinearities through bottlenecks leads to a subset of larger model space. 对于example, composing order $d$ polynomial units in a 深 architecture with $m$ levels results in something whose leading order terms are monomials of order $m d$; but 许多 of the terms in a full $m d$ polynomial expansion (aka “shallow architecture”) 缺失。因此,前导顺序具有灵活性,但模型空间有限。但是,这有关系吗?

对于me the best evidence comes from that old chestnut MNIST. 对于many years the Gaussian kernel yielded better results than 深 learning on MNIST among solutions that did not exploit spatial structure. Since the discovery of dropout this is no longer true 和 one can see a gap between the Gaussian kernel (at circa 1.2% test error) 和, e.g., maxout networks (at 0.9% test error). The Gaussian kernel essentially works by penalizing all function derivatives, i.e., enforcing smoothness. Now it seems something more powerful is happening with 深 architectures 和 dropout. You might say, “嘿1.2%和0.9%,我们不是要分开头发吗?”但我不这么认为。我怀疑这里还会发生其他事情,但这只是一个猜测,我当然不理解。

The counterargument is that, to date, the major performance gains in 深 learning happen when the composition by depth is combined with a decomposition of the feature space (e.g., spatial or temporal). In speech the Gaussian kernel (in the highly scalable form of random fourier features) is able to approach the performance of 深 learning on TIMIT, if the 深 net cannot exploit temporal structure, i.e., RFF is competitive with non-convolutional DNNs on this task, but is surpassed by convolutional DNNs. (Of course, from a computational standpoint, a 深 network starts to look downright parsimonious compared to hundreds of thousands of random fourier features, but we're talking statistics here.)

远距离关系的危险

So for general problems it's not clear that ``regularization via depth'' is obviously better than general smoothness regularizers (although I suspect it is). However for problems in computer vision it is intuitive that 深 composition of representations is beneficial. This is because the spatial domain comes with a natural concept of neighborhoods which can be used to beneficially limit model complexity.

对于诸如自然场景理解之类的任务,空间范围有限的各种对象将被放置在众多背景之上的不同相对位置。在这种情况下,歧视的一些关键方面将由本地统计数据确定,而其他方面则由远端统计数据确定。但是,给定一个包含256x256像素图像的训练集,训练集中的每个示例都提供了一对像素的一种实​​现,该像素对向右下方偏移256个像素(即,左上左下右像素)。相反,每个示例都提供一对像素的252 ^ 2 $实现,该像素向右下方偏移4个像素。尽管这些实现不是独立的,但是对于正常摄影比例的自然场景图像,每个训练示例中有关局部依存关系的数据要比远端依存关系多得多。从统计学上讲,这表明尝试估计附近像素之间的高度复杂关系较为安全,但是必须更严格地规范远距离依存关系。深度分层体系结构是实现这些双重目标的一种方法。

理解此先验功能的一种方法是,注意它适用于通常与深度学习无关的模型类。在经过验证的MNIST数据集上,高斯核最小二乘可实现1.2%的测试误差(无训练误差)。将每个示例划分为4个象限,在每个象限上计算一个高斯核,然后在所得的4个向量上计算高斯核的最小二乘可实现0.96%的测试误差(无训练误差)。高斯核与核的区别。“deep”高斯核是建模远端像素交互的能力受到限制。尽管我还没有尝试过,但我相信通过约束从根到叶的每条路径以包含空间上相邻像素的分割,可以类似地改善决策树集合。

这是附近美好的一天

The outstanding success of hard-wiring hierarchical spatial structure into a 深 architecture for computer vision has motivated the search for similar concepts of local neighborhoods for other tasks such as speech recognition 和 natural language processing. 对于temporal data time provides a natural concept of locality, but for text data the situation is more opaque. 乐xical distance in a sentence is only a moderate indicator of semantic distance, which is why much of NLP is about uncovering latent structure (e.g., topic modeling, parsing). One line of active research synthesizes NLP techniques with 深 architectures hierarchically defined given a traditional NLP decomposition of the input.

对用文字表达邻里关系的相对困难的另一种回应是问“can I learn the neighborhood structure instead, just using a general 深 architecture?”从头开始学习是一种自然的吸引力,尤其是当直觉用尽时;但是,在视觉上,当前有必要将空间结构硬连接到模型中,以获取接近最新技术水平的性能(给定当前数据和计算资源)。

因此,对于例如机器翻译的良好解决方案将在多大程度上涉及手工指定的先验知识与从数据得出的知识之间是一个悬而未决的问题。这听起来像旧的“nature vs. nuture”认知科学方面的争论,但是我怀疑在这个问题上会取得更多进展,因为现在辩论是通过实际尝试设计执行相关任务的系统而获得的。

2014年6月30日,星期一

集成电路 2014评论

集成电路 2014取得了不错的成绩,对组织者表示敬意。地点(北京)和CVPR的重叠无疑影响了与会者的分布,因此会议感觉与去年不同。 (我还了解到,我的博客已被中国屏蔽,谷歌与中国政府之间发生了一些口角,造成了附带损害)。

Deep learning was by far the most popular conference track, to the extent that the conference room for this track was overwhelmed 和 beyond standing room only. I missed several talks I wanted to 在tend because there was no physical possibility of entrance. This is despite the fact that 许多 深 learning luminaries 和 their grad students were 在 CVPR. Fortunately Yoshua Bengio chose 集成电路 和 via several talks provided enough insight into 深 learning to merit another blog post. Overall the theme is: having conquered computer vision, 深 learning researchers are now turning their 在tention to natural language text, with some notable early successes, e.g., 段落矢量。当然,该品牌的销量很高,这解释了一些纸质标题的选择,例如,“深 boosting”。还有一个会议标题为“神经理论与光谱方法”...有趣的床友!

ADMM突然变得流行(大约在18个月前,由于想法,会议提交和演示之间的延迟)。通过这种方式,我并不是说要使用ADMM进行分布式优化,尽管有很多。相反,有几篇使用ADMM解决受约束的优化问题的论文,否则这些问题将很烦人。带回家的课程是:在针对您遇到的任何受限优化问题提出定制的求解器之前,请尝试ADMM。

现在获取洗衣清单(也请注意上述纸张):
  1. 非平稳函数的贝叶斯优化的输入变形。如果要引起社区的注意,就必须打号码,所以不要带着刀子进行枪战。
  2. 通过主动子空间选择使核规范最小化。无与伦比的谢祖瑞再次做到了,这次将主动变量方法的思想应用到核规范的正则化中。
  3. 驯服怪物:上下文盗贼的快速简单算法。不可知论语境盗贼所需的计算复杂性得到了显着改善。
  4. 高效的可编程学习搜索。自NIPS以来,命令式编程的其他改进。如果您要进行结构化预测,尤其是在需要将产品投入生产的工业环境中,则需要研究这种方法。首先,它减轻了指定复杂的结构化预测任务的负担。其次,它减少了培训和评估之间的差异,这不仅意味着更快的部署,而且还减少了实验与生产系统之间引入的缺陷。
  5. 不变位移核的准蒙特卡洛特征图。确认准随机数可以更好地适用于随机特征图。
  6. 单次通过算法可有效恢复高维数据的稀疏聚类中心。我需要在本文上花一些时间。
  7. 多分辨率矩阵分解。 尼科斯和我通过使用经典矩阵分解来学习判别表示法时非常幸运。我希望可以对这种新的分解技术进行类似的调整。
  8. 基于样本的近似正则化。我发现依赖数据的正则化很有希望(例如,最小二乘法的遗失等效于无标度L2正则化器),因此本文引起了我的注意。
  9. 适应性和乐观:改进的指数梯度算法。本文没有进行任何实验,因此也许这是``纯粹的理论胜利'',但看起来很有趣。

2014年6月16日,星期一

微软启动了ML博客和ML产品

我的雇主Microsoft已开始 关于ML的新博客 并宣布了 ML的新产品.

该博客令人兴奋,因为微软将有多位ML杰出人物将为之贡献。 约瑟夫·西罗什 也涉及到,因此大概还会有面向应用程序的内容的健康组合。

该产品也令人兴奋。但是,如果您是已经熟悉特定工具链的ML专家,您可能会想知道为什么全世界都需要此产品。那些在Microsoft,Google,Facebook或Yahoo等大型公司工作的人大概知道,有一大批工程师维护和改善数据科学基础的系统基础结构(例如,数据收集,提取和组织,自动模型再培训和部署;监控和质量保证;生产实验)。但是,如果您从未在初创公司工作过,那么您实际上就不会意识到所有这些人为实现数据科学所做的全部工作。如果将这些功能作为服务产品的一部分提供,那么具有高见解的个人数据科学家就有可能与大公司竞争。更现实的是,考虑到我在初创公司的经验,单个数据科学家将有机会在必须投入大量资本开发基础设施之前确定他们的热门想法不是那么热门:)

当然,还有很多事情要做“机器学习即服务”完全成熟,但是此产品发布是一个不错的第一步。

2014年5月3日,星期六

最具因果关系的观察者

戴维·帕克 最近有一个 来宾帖子 在Gelman的博客上。您应该阅读它。的 tl; dr 是``大数据是大事,但因果关系很重要,与预测不一样。''

我同意以下基本信息: 因果关系很重要。作为职业建议,如果您刚刚开始职业生涯,那么关注因果关系将是一个好主意。几乎没有人为预测目的而建立一个预测模型。相反,重点是 建议干预。例如,为什么要预测信用卡交易的欺诈风险?大概目标是拒绝一些交易。当您这样做时,情况会改变。最简单的是,如果您拒绝交易,您将不会了解如果您批准该交易将会发生的反事实。由于问题的对抗性质,还会出现其他问题,即欺诈者将对您的模型做出反应。不注意这些影响会导致意想不到的后果。

但是,我对``需要认真思考问题并推动这些过程的基本机制''的创意人持保留意见,以``实现大数据的承诺''。当我读到这些词时,我将其翻译为“尽管存在大量数据,也必须利用强大的结构先验知识来建立因果关系模型。”大实验系统收集的大数据将能够以不可知论的方式发现随意的关系。这里的“不可知论”基本上是指“适用于自动化的弱结构假设”。当然,总是存在一些假设,例如,在进行Vapnik风格的ERM时,人们会对数据生成过程做出虚假的假设。问题是是否需要人类和创造力。

也许更好的说法是“需要创造力的人类来履行大观测数据的诺言。”我认为这是事实,社会科学一直在处理观测数据已有一段时间,因此他们具有相关经验,洞察力和培训,我们应该更加重视。此外,另一个合理的主张是“大数据将在不久的将来成为观察性的”。当然,监视Twitter消防站很容易,而我却完全不清楚实验平台将如何操纵Twitter以确定因果关系。尽管如此,我认为大规模的自动化实验设计具有巨大的破坏潜力。

我假设的主要区别在于,机器学习将越来越多地从处理由另一个流程生成的大量数据转变为驱动收集数据的流程。对于计算广告,情况已经如此:通过平衡开发(赚钱)和探索(了解什么广告在什么条件下会很好)来放置广告。上下文强盗技术已经成熟,“大实验”已经不是天方夜谭,它每天都在发生。有人可能会争辩说,广告是一种特殊的应用程序,具有如此极端的经济重要性,以至于有创造力的人已经设计出一种结构模型,可以进行因果推理,参见 Bottou等等 我会说这是正确的,但也许只是第一步。对于预测,我们不再需要在参数有意义的情况下进行参数化建模:如今,我们有许多具有本质上有害参数的模型。一旦我们拥有了收集数据并对其进行建模的系统,是否将需要具有有意义参数的强大结构模型,或者是否有某种不可知的方式来捕获具有足够数据的大量临时关系 实验?



2014年4月25日,星期五

判别表征学习技术

我和Nikos开发了一种使用数值线性代数技术学习判别特征的技术 效果很好 for some problems. The basic idea is as follows. Suppose you have a multiclass problem, i.e., training data of the form $S = \{ (x, y) | x \in \mathbb{R}^d, y \in \{ 1, \ldots, k \} \}$. Here $x$ is the original representation (features) 和 you want to learn new features that help your classifier. In 深 learning this problem is tackled by defining a multi-level parametric nonlinearity of $x$ 和 optimizing the parameters. Deep learning is awesome but the resulting optimization problems are challenging, especially in the distributed setting, so we were looking for something more computationally felicitous.

首先考虑两类情况。想象一下寻找形式为$ \ 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)。

The 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.
That's a pretty good confusion matrix, comparable to state-of-the-art 深 learning results on (permutation invariant) mnist. In the paper we report a slightly worse number (96 test errors) because for a paper we have to choose hyperparameters via cross-validation on the training set rather than cherry-pick them as for a blog post.

此处所述的技术实际上仅对超薄设计矩阵有用(即,有很多示例,但没有太多特征):如果原始特征维数太大(例如,$>10 ^ 4 $)比单纯使用标准广义特征求解器变得缓慢或不可行,并且还需要其他技巧。此外,如果类数太大而不是解决$ O(k ^ 2)$广义特征值问题,那也是不合理的。我们正在努力解决这些问题,我们也很高兴将此策略扩展到结构化预测。希望我们在接下来的几届会议上能有更多的话要说。

2014年3月9日星期日

快速失败

我在圣诞节休息期间研究了一些与矩阵分解相关的想法。我想知道的两件事是:第一,辍学对于判别低阶二次方是否是一个很好的正则化器;其次,如何做类似 GeV表示学习 for discriminative low-rank quadratics. 对于the latter, I had an idea I was sure would work, but I wasn't able to make it work. There's a saying: “你的宝宝不像你想象的那样美丽”。尽管有我们先前的信念,但大多数想法都不是好主意,因此,尽快消除想法很重要。

新兴企业已经普及了 快速失败,因为大多数商业想法也不是好主意。的想法 最低可行产品 已成为创业社区的中心教条。类似地,在测试机器学习思想时,最好从“最小可行算法”。此类算法使用尽可能多的现有语言和包(例如,Matlab,NumPy)以尽可能高级的语言编写(例如, CVX),并且不采取任何计算捷径来提高效率。

我开始在Matlab中研究用于矩阵分解的辍学正则化,当我看到它正在起作用时 电影镜头,然后我花了一些时间来实现以减少大众使用量。我的事实 知道了 它应该可以使我克服实施时引入的多个缺陷。短话甚至更短,结果在主分支中,您可以 查看演示 .

我尝试的下一个想法是将学习低阶二次特征摆在一个交替的线性分数优化问题上。交替最小二乘的类比是如此强大,以至于从理论上讲,我确信它是赢家。对于二进制二进位示例上的多类预测任务(例如,没有附带信息的电影镜头),请执行以下操作:$ S = \ {\ {(l,r),y \} | l \ in \ {0,1 \} ^ m,r \ in \ {0,1 \} ^ n,y \ in \ {0,1,\ ldots,k \} \} $,一个预测变量潜在的MF风格功能看起来像\ [
f((l,r); w,p,q)= w ^ \ top(l,r)+(l ^ \ top p)(r ^ \ top q),
\] 为了简单起见,忽略了常量功能。这里$ p \ in \ mathbb {R} _ + ^ m $和$ q \ in \ mathbb {R} _ + ^ n $是单个潜在特征。在没有附带信息的电影镜头上,$ l $和$ r $分别是用户ID和电影ID的指示变量,因此$ p $和$ q $由这些标识符索引,并分别生成一个标量,并将其乘积添加到预测变量中。

想法是选择潜在特征在$ i $类上高度活跃,而在另一个$ j $类上高度活跃,\ [
\ max_ {p \ in \ mathbb {R} _ + ^ m,q \ in \ mathbb {R} _ + ^ n} \ frac {p ^ \ top \ mathbb {E} [l r ^ \ top | y = i] q} {\ alpha + p ^ \ top \ mathbb {E} [l r ^ \ top | y = j] q}。
\] 受$ p \ preceq 1 $和$ q \ preceq 1 $约束(否则它可以分开)。 $ \ alpha>0 $是一个正则化分母的超参数。当然,在实践中,期望值将转换为训练集的平均值。

对于固定的$ p $,这是$ q $的线性分数程序,反之亦然,因此从随机点开始,我能够快速切换到视觉上看起来不错的功能(在高收视率的用户电影对上产生高产品能量,低收视率的用户电影对产品能量较低)。但是,与没有交互作用的线性模型相比,这些功能对测试集的预测提升几乎不存在。然后,我尝试了增强型变体,其中首先拟合没有交互作用的线性模型,然后尝试区分正残差示例和负残差示例。这更有趣:除少数数据外,这些功能最终几乎都为零,这表明尽管原始功能在视觉上看起来不错,但它们大多为线性模型提供了冗余信息。

使用Matlab和CVX,我能够在短短几天之内解决这些负面结果(这有助于在假日期间不召开会议)。我可能会搞砸了,但实际上这个主意是个好主意吗?是的,但是在如此高的水平上进行工作消除了对优化器的担忧,这使它更有可能实际上是错误的策略。无论如何,我都有很多想法,我需要花时间在那些最有可能产生有趣结果的想法上。尽管不是确定的,但是这些快速的实验表明我应该将时间花在其他地方。

认为是 贝叶斯搜索理论 在思想空间上。







2014年2月21日,星期五

陌生土地上的陌生人

我参加了 SIAM PP 2014 会议在本周召开,因为我对MPI风格的并行算法(也很近)产生了兴趣。我的计划是观察HPC社区,尝试了解他们的世界观与以互联网为中心的世界观有何不同“Big Data”心态,开阔我的视野。有趣的是,高性能计算专家实际上正忙于相反的事情。他们知道我们要做什么,但是他们谈论Hadoop就像是在山坡上生活似的,然后来拜访城镇居民。听他们讲解我们将要完成的工作映射到他们的概念方面非常有启发性,并帮助我更好地了解了他们。

数据必须流动

我在会议上听到的第一件事是“map-reduce忽略数据局部性”。演讲者史蒂夫·普林顿(Steve Plimpton)清楚地理解了map-reduce, MPI的MapReduce。这是一个很大的线索,它们在数据局部性上的含义有些不同(即,它们并不意味着“将代码移至数据”).

典型的MPI作业包括将适量的初始状态加载到主存储器中,然后对该状态进行大量的迭代计算,例如,模拟生物学,天气或核爆炸。在这种情况下,数据局部性意味着重新安排数据,以便减轻计算节点之间的同步要求。

另一方面,互联网公司通常拥有大量数据,这些数据可对计算进行参数化,因此他们希望对其进行适度的计算(例如,您最多只需要传递30次数据即可获得出色的逻辑回归适合)。虽然我们进行了一些迭代计算,但数据与计算的比率使得 数据流编程适度失真,非常适合我们的需求。这种差异是为什么Cray的CTO不得不指出Hadoop的原因“一直在做I / O”.

失败不是一种选择

HPC社区对容错有精神分裂症的态度。从某种意义上说,他们更加了解并担心这一点,而从另一种意义上说,他们却无所作为。

让我们从遗忘开始。当今用于HPC的主流编程模型提供了可靠机器的抽象,即没有错误的机器。当前生产的HPC系统通过错误检测与全局检查点重新启动相结合,实现了这一承诺。硬件供应商以与应用程序无关的方式执行此操作:定期将每个节点的整个状态持久存储到持久性存储中,以及在检测到错误时 他们恢复了最新的检查点.

存在一些威胁该方法的问题。首先是基本的:随着系统变得更加并行,平均故障间隔时间会减少,但检查点时间却不会减少(更多的节点意味着更多的I / O容量,但是还有更多的状态可以持久)。由于固态硬盘和NVRAM在持久性存储方面的不断改进,全球检查点重启模型已经走了两到三年的时间,但似乎很快将需要不同的策略。

第二个是错误检测本身容易出错。 纠错码 仅防止最可能的错误类型,因此,如果发生高度不可能的错误类型,则不会检测到该错误;其他硬件(和软件)组件可能会引入其他无法检测到的错误。这些叫做 无声的腐败 在HPC社区中,由于其性质,其发生的频率尚不为人所知,但是随着并行度的增加,这种频率将增加。

最终,这听起来像是程序员的天堂(“我不必担心失败,我只是使用可靠机器的抽象对我的应用程序进行编程”)成为程序员的噩梦(“无法通知系统我的计算固有的容错能力,也无法编写软件来减轻对昂贵的通用可靠性机制的需求,这些机制甚至不总是有效。”)。释义一位小组成员,“...如果ECC模块检测到双位错误,那么即使对该存储单元执行的下一个操作是写操作,我的过程也很辛苦。”

沉默但不致命

尽管编程模型占主导地位,但社区中的应用程序开发人员仍然高度意识到失败的可能性,包括上述所有问题以及数值舍入等问题。实际上,他们对失败的思考比我想象的要多得多:我最关心的自己是“糟糕,我从群集中丢失了整台计算机。 ”同时,我不仅不检查是否有无损坏,还在做诸如购买便宜的RAM,使用半精度浮点数以及忽略突然不可用的数据批之类的事情。有什么工作原理?

当然,一个答案是,机器学习计算任务的典型总核心小时数是如此之小,以致通常不会发生极不可能的事情。虽然需要很多计算机 认猫,总核心小时数仍少于106。与此同时 红杉 在LLNL,它有10万个计算节点(160万个内核),因此,需要花费一周时间进行的模拟将有10个左右2-104 暴露更多的核心时间。尽管如此,机器学习社区的野心是扩大规模,这引出了一个问题:我们是否应该担心数据损坏?我认为答案是:可能与HPC社区的水平不同。

我看到了有关自稳定应用程序的演示,该演示是关于设计算法的,以便以后进行的计算可以修复随机注入的错误计算。指示的第三张幻灯片“有些应用程序本身无需进一步修改即可自稳定。例如,收敛定点方法,例如牛顿法。”哈哈!大多数机器学习是“the easy case”(按原样,例如PageRank)。考虑到随机梯度下降算法,这并不奇怪 尽管有错误,似乎还是可以工作.

还记得蝴蝶效应吗?这是受到天气模拟中观察到的合唱动态的启发。预测天气不像机器学习!一个问题是,机器学习或数据分析中是否有类似于天气模拟的内容。训练过程中的模型状态错误通过收缩动力学进行校正,并且在评估时单个输入或中间状态的错误仅影响一个决策,因此其影响是有限的。但是,评估时的模型状态错误会影响 许多 决定,所以值得更加小心。例如,可以将每个模型的验证示例集运送到生产系统,并且在加载模型时,将计算验证集上的输出:如果不符合期望的结果,则应拒绝新模型。然而,大多数情况下,机器学习可以轻而易举地进行,因为对输入数据的信息内容存在统计限制,我们希望将其推广到新颖的情况。此外,风险更低:与目标不当的核武器相比,目标不当的广告危险性更低。

有什么要声明的吗?

在HPC社区中似乎至少有两个不同的子营。在一个阵营中,那些人主要是想保留一台可靠的机器的抽象,可能将故障处理流程移到系统软件中一点点,但仍然使应用程序程序员远离它。正如我在小组讨论中听到的那样,该营地希望“一致的架构和策略,而不是花招。”在另一个阵营中的人是那些希望对可靠性策略进行更多应用程序级控制的人,以便利用其问题的特定方面并避免全局检查点还原的巨大损失。例如,也许您有一种方法可以检查软件中的计算结果,并在不通过的情况下重做一些工作(又名 遏制域)。你想说“请不要进行昂贵的还原,我会处理的”。当前的HPC系统不支持该功能。

在应用程序级别,声明式出现是关键。当前的HPC抽象被设计为使任意计算可靠,因此价格昂贵。通过声明计算意图,可以使用更简单的可靠性模型。例如,map-reduce是一个声明性框架:据说计算具有特定的结构(数据并行映射,然后是关联约简),该结构允许进行局部故障处理(当节点发生故障时,仅与该节点关联的映射输出需要重新计算,可以推测性地完成)。这些简单的可靠性模型不仅价格便宜,而且速度更快(发生错误时减少冗余工作)。但是,它们不适用于通用计算。

根据您所处的阵营,将一组专用的计算框架与相关的可靠性策略放在一起,听起来可能是好极了,还是可怕的。我相信,在HPC社区中,有些人会恐惧和厌恶地看着Apache Foundation中的项目集合。然而,其他人则说实际上只有少量的计算模式可以完成大部分工作(例如,数值线性代数,模具/网格计算和蒙特卡洛),因此定制策略的集合可能是可行的。

大教堂vs.集市

在互联网领域,以上关于前进道路的分歧被认为是健康的。将会出现多个不同的开放源代码项目,最终,最好的想法将浮出水面,下一代创新将利用这些经验教训并重复这一循环。同时,在HPC世界中,MPI规范尚未采用任何其他有关容错的提议。最初希望是3.0,然后是3.1,现在看起来像 4.0是最早的可能性.

与Apache Foundation相比, 大教堂vs.集市 比喻是恰当的。但是,标准委员会比整个社区要保守一些,该委员会正在推动原型设计和实施,从而简化了对可靠机器的抽象,例如, 冗余MPI容错MPI。在下面的标题下,还有大量针对计算的策略“基于算法的容错”.

外卖

从这个社区中可以学到一些教训。

首先是 声明式编程 至少在分布式控制流方面将是必胜之举(非分布式部分仍将由命令性规范主导,但是例如,通过线性代数指定的学习算法可以一路声明为声明性)。此外,分布式声明式表达能力将不是通用目的。 HPC社区一直在尝试通过无故障抽象来支持通用计算,这被证明是昂贵的。 HPC社区中的一些人现在呼吁使用受限的表达性声明模型,该模型允许使用成本较低的容错策略(在云中,我们必须进一步应对多租户和弹性)。同时,开源社区一直在拥抱更具表现力但仍受限制的计算模型,例如, 吉拉夫GraphLab。短期内将出现更多具有不同但表达能力有限的声明框架,并且有必要创建一种简单的方法来在统一的集群中运行所有框架,并指定涵盖所有框架的任务。

第二个是,如果您等待足够长的时间,则肯定会发生极不可能的事情。大多数情况下,我们现在在机器学习社区中忽略这一点,因为我们的计算很短:但是鉴于我们的需求和扩大规模的雄心,我们将不得不担心这一点。通用策略,例如 遏制域怀疑编程 因此值得理解。

第三是 批量同步并行 有很大的余量。在机器学习社区中,围绕参数服务器的兴奋很多,这与 异步PGAS 在HPC中(也类似于BSP的松弛,例如, 陈旧的同步并行)。但是BSP如今在petascale上工作,并且易于推理和编程(例如,BSP是 Vowpal兔子 促使Hadoop进行分布式Logistic回归时执行此操作)。带着 优化的allreduce流水线实施,BSP算法看起来很有吸引力,尤其是当它们可以声明有关如何在部分响应(例如由于故障或多租户问题)的情况下取得进展以及如何利用新可用的额外资源(例如由于多租户)的语义时。

我本可以发誓还有第四道菜,但不幸的是我忘记了,也许是因为 异常热中子.

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 classification, 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

2014年1月12日星期日

群集集群

可以肯定的是,在不久的将来,数据将继续在群集文件系统(例如HDFS)中累积,这些文件系统由具有以太网互连功能的商用多核CPU驱动。这样的集群相对便宜,容错,可扩展,并且有大量的系统研究人员正在研究它们。

几年前,可以肯定的是,机器学习的迭代处理工作负载将越来越多地迁移到可以在数据所累积的同一硬件上运行,毕竟,我们要“将代码移至数据”. Now this is looking less clear. The first serious challenge to this worldview arose when 深 learning catapulted to the front of several benchmark datasets by leveraging the GPU. 院长等等 开始使用具有以太网互连功能的大型多核CPU群集来复制并超越这些结果,并且尽管成功了,但所需的硬件数量却令人惊讶。然后 科茨(Coates)等。等 通过密切关注通信成本(通过以通信友好的格式布置模型,抽象通信原语并利用Infiniband互连),使用少得多的机器即可获得可比的结果。

Is the 科茨(Coates)等。等 result a bespoke solution for 深 learning? Interestingly, 坎尼和赵 他们得出类似的结论“squaring the cloud”论文,他们根本没有明确提到神经网络。这是论文的关键语录:
“快速混合算法(SGD和MCMC)尤其会遭受通信开销的困扰。加速通常是$ n $的子线性函数$ f(n)$,因为网络容量会在更大范围内减小(典型的近似值是$ f(n)= n ^ \ alpha $对于某些$ \ alpha<1 $)。这意味着云计算的成本增加了$ n / f(n)$倍,因为总工作量增加了该倍数。能源使用量类似地增加相同的因素。相比之下,单节点速度提高$ k $意味着在成本和功耗上节省了简单的$ k $倍。”
换句话说,对于我们真正关心的某些算法,通过将通信成本视为主要因素,您可以用更少的机器做等效的工作,从而降低总成本。

所以这就是我所看到的当前状态。仍然有许多算法可以在运行分布式文件系统的同一硬件上最高效地运行,例如, ADMM系列,其中包括L1正则化logistic回归等美味商品。但是,也会有一些经济利益很高的算法无法正确地映射到此类硬件上。因此,我们应该期望看到数据中心正在部署“HPC islands”由相对较少的机器组成,这些机器装满了矢量化处理器,高带宽(至矢量化处理器)内存和快速互连。这些类型的集群在某些社区(例如高能物理研究人员)中很受欢迎,但是现在面向消费者的互联网公司将广泛采用此技术。

These HPC岛屿 do not need to stage all the data they are working on before they start doing useful work, e.g., SGD algorithms can start as soon as they receive their first mini-batch. 咖啡 和 a single K20 can train on Imagenet 在 7ms per image amortized, which works out to roughly 40 megabytes per second of image data that needs to be streamed to the training node. That's not difficult to arrange if the HPC island is collocated with the HDFS cluster, 和 difficult otherwise, so the prediction is near the HDFS cluster is where the HPC岛屿 will be. Of course the HPC island should have a smart caching policy so that not everything has to be pulled from HDFS storage all the time. A 智能缓存策略将是任务感知的,例如,利用 主动学习 最大限度地提高HDFS和HPC岛之间的信息传输。

对这样一个异构系统进行编程将非常具有挑战性,这将为处于适当位置的个人提供大量机会。