显示带有标签的帖子 分布式机器学习. 显示所有帖子
显示带有标签的帖子 分布式机器学习. 显示所有帖子

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年1月12日星期日

群集集群

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

几年前,可以肯定的是,机器学习的迭代处理工作负载将越来越多地迁移到可以在数据所累积的同一硬件上运行,毕竟,我们要“将代码移至数据”。现在看起来不太清楚。当深度学习通过利用GPU跃升至多个基准数据集的前端时,就出现了这种世界观的第一个严峻挑战。 院长等等 开始使用具有以太网互连功能的大型多核CPU群集来复制并超越这些结果,并且尽管成功了,但所需的硬件数量却令人惊讶。然后 科茨(Coates)等。等 通过密切关注通信成本(通过以通信友好的格式布置模型,抽象通信原语并利用Infiniband互连),使用少得多的机器即可获得可比的结果。

是科茨等人。等为深度学习提供定制解决方案?有趣的是 坎尼和赵 他们得出类似的结论“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岛之间的信息传输。

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

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