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倍,并且精度更高。

第二种算法甚至更快,并且适用于多类以及多标签问题。还有一个缺点是,您不会在尾巴中获得非常准确的概率估计:这种方法不能优化交叉熵。基本思想是我们将学习链接功能,有时也称为校准。

对于二进制分类, 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