paper note 002 && Scalable Inference in Latent Variable Models - louiss007/lsml GitHub Wiki

摘要

从预测用户点击模式和定向广告到组织新闻和管理用户生成内容，隐变量技术是关键的。隐变量技术提供了一种对复杂数据的潜在的结构的本质的理解的方法，例如主题模型，聚类，子控件估计，对于大规模，快速变化的数据集，很少或者没有额外的保证，它们是合理的。不幸的是，由于数据的依赖性，隐变量推断迭代的本性，隐变量技术应用到大规模流式数据集是极其昂贵的。 本文我们描述了一个可扩展的并行的框架，用于隐变量模型在大规模流式数据集上的高效推断。我们的框架解决了三个关键的挑战：1）同步包括全局隐变量的全局状态（例如，聚类中心和词典）；2）高效存储和检索大量包括数据点和对应的隐变量的本地状态（例如，类簇关系）；3）串行地合并流式数据（例如，新闻）。我们通过以下的方法解决这3个挑战：1）利用一种带宽高效的通信协议实现了一种新的基于增量的聚合系统；2）核外存储的显示调度；3）近似前向采样，快速地合并新数据。通过简单地处理了比当前性能最好的系统所处理的数据多两个数据级的数据，论证了我们的框架性能是目前最好的。另外，我们提供了框架的一个最优的，易定制的开源实现版本。

主要思想

主要贡献

  • 一个显示调度的基于硬盘的缓存，用于本地隐变量（每个数据）
  • 一个重要的改进是通用的通信结构，用于异步更新全局变量
  • 一个高效的在线算法，用于流式数据的隐变量推断
  • 一种新的容错的，快速恢复的机制，用于大规模分布式的全局状态

思想

  • 全局变量（即模型参数）在一台机器上

一般是没执行一次采样，即更新一次全局变量。这样就没办法实现算法的并行。所以如果允许一定的近似，采样一次，同时在多核中进行多次更新。即可实现并行。但带来一个问题，有些更新用到的zi都是陈旧的。

  • 全局变量（即模型参数）在多台机器上

对于单机多核系统，由于是内存内，所以操作是低成本的，但是在多机系统中通过网络来进行操作时，那将变的昂贵。我们借用对偶分解的思想—将全局变量做了多个本地副本，并使它们保持数据一致性。如下图 star topology of ps 通过这种多个本地（per machine）完全全局变量的副本的方式，来降低多机操作的网络开销成本。 decomposition of star topology of ps 本地机器存储的是一个完整的全局变量的副本，没有对模型参数进行分片，依然无法解决单个模型size大于单机内存的情况。 如果要使得上述方法（全局变量在多台机器上）可行，我们需要指定：a)详细的更新方程，b) 在多台机器上分布全局变量的有效方式，c) 一个避免通信开销的调度方法

  • 异步增量聚合

通过memcached进行单边通信带来的高延迟的后果，困扰着第一代ps。另外，由于很多分布式key-value存储缺失服务端的处理，导致第一代ps框架对于全局变量的高效通信并不合适。再者，第一代ps中worker节点不是把参数的变化量推送给server,而是整个全局变量的向量。相反，server也不是把相对的变化量发送给worker节点，而是全部全局变量。这样大大增加了网络通信的开销（增加了带宽需求）。 这个可以通过在客户端和服务端增加一些处理操作（一般即使简单的计算，如比较，加减等），将全局变量的变化量计算出来，传递给server，来降低网络开销。虽然增加了计算开销，但网络开销大于该计算开销，这么做还是划算的。注意但是从server端传递给worker节点的好像还是全部，不是变化量，这块不是太清楚，好像也不是太容易实现全局变量的diff。

  • 分布与调度

给定p个client和k个全局变量，那么每次同步时的traffic是O（kp）。如果我们选择p个server，那么每个server的traffic是O(k)。我们通过一致性哈希协议保证k个全局变量均匀的分布在p个server上。期望是每个server存储k/p个全局变量。对于100台机器，这种方法没问题。但是当随着机器数进一步增多的时候，第二个问题出现了。因为每个client与每台server进行通信，这意味着任意一对机器之间的数据交换量都是O(k/p)。这意味着数据量随着机器数增多而呈1/p递减，而网络连接数随着机器数增多而呈p增加。事实上，对于1000台机器时，通信的开销是关键的，因此，需要对原始的一致性哈希协议做一个扩展。 关键的改进是同步重复性的发生，并且对于每台机器要发送哪些信息，发送之前就知道。因此我们重新布局一下上一节中同步算法要发送的信息，每次只与一台机器通信（降低对网络带宽要求）。结果每个client每次只与一个server连接，发送所有要发送的信息到这个特别的server上。

不幸的是，这种方法有个缺点，虽然我们减少了连接数从p^2到p，但是这会导致每个server获得的连接数不均匀。解决方法是随机选择r<<p个servers，同时与r个servers通信。对于普通的通信算法的主要的改进是按照预先规定的顺序同步全局变量，确保在任意给定的时间，每台机器只开放了r个连接。这样，确保了空闲的机器较少。

  • 容错

容错是大型分布式系统的重要的话题。第一代ps只提供了一个非常弱的保证，就是一旦有机器失败，全部的全局变量需要从头重新生成。这是非常耗成本的。相反，我们使用下面这样的策略。在任意给定的时间，当我们想计算一个checkpoint的时候，停止所有的通信，采样操作，并一直等到输入的消息队列被处理完。这时每个client和server只是将它们的状态写到云文件系统即可（HDFS）。这意味着我们可以检查分布式同步的状态，通过加载文件系统中的状态即可恢复。

  • 本地变量和核外存储

当为每个word估计一个topic时，会带来状态空间超出内存的需求。一种解决方案是将部分隐状态写到核外的硬盘空间上，当需要时，按流式方式从从读取。

  • 序列估计

通常，数据输入带有一定的序列顺序，通过使用序列蒙特卡洛估计来进行数据的推断。

缺点

  1. 没有明确参数划分方法
  2. worker节点中存储与server中相同的全局参数，依然没有解决单机无法存储这个模型的问题。

总结

相比于第一代ps，第二代参数服务器做了很大的改进，包括同步的策略，全局参数的增量更新策略，全局参数的划分存储（server包含多个机器的情况时），以及相应的调度策略，分布式系统的容错性，大量本地隐状态的存储问题，固有的串行数据的估计问题等方面。但依然属于某一特定领域的参数服务器，与通用的参数服务器还有一定的差距。