我们来看下Feng Niu等人提出的《Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent》。

#

SGD是许多机器学习任务的一种流行优化算法。之前的许多研究者都提出了并行化SGD的schemes，但都需要影响性能的内存锁和同步机制。本文主要展示了使用新的理论分析、算法和Hogwild!实现，它允许处理器以相互覆写（overwriting）的方式访问共享内存。当相关优化问题是sparse时，大多数梯度更新（gradient updates）只会修改决策变量的很小一部分，接着Hogwild!可以达到一个近似最优的收敛率。实验结果表明Hogwild!的效果要比使用锁版本的要好一阶。

1.介绍

由于较小的内存占用、对噪声健壮、以及快速的learning rate，SGD被证明是很适合数据密集（data-intensive）的机器学习任务。然而，SGD的扩展性受它的顺序型(serial)特性限制；很难并行化。随着不贵的多核处理器和超大型机器出现，大规模（web-scale）数据集启发着研究者们为SGD开发了许多并行化schemes。许多大型数据集当前在类MapReduce并行处理框架上进行预处理，在并行SGD上的最近的许多工作都主要关注在MapReduce实现。MapReduce是一个很强大的工具，但它不适合online、数值密集的数据分析。迭代型计算很难在MapReduce上表示，并且确保容错的开销可能会产生更大的吞吐量。Google研究者建议其它系统（例如：Dremel）比MapReduce更适合。

对于一些数据集，数据的绝对规模（sheer size）预示着是否需要一个机器集群。然而，存在一个问题，在合适预处理后，对于统计分析所需要的数据，可能仍包含上兆（TB）字节。而对于一些问题，并不需要上百台集群，可以使用单个便宜的工作站就行。多核系统具有极大的性能优点：包括：

• 1）低延迟、高吞吐，共享主要内存：这样的系统中一个处理器可以以超过12GB/s的速率读写共享物理内存，延迟只有数10ns
• 2）跨多磁盘高带宽（high bandwidth off multiple disks）：一个上千美金的RAID可以以超过1GB/s的速率将数据导入到主存中。而作为对比，由于存在容错机制上频繁的checkpoint，一个典型的MapReduce setup会以低于数十MB/s的速率读取数据。多核系统可以达到高速率，瓶颈在处理器间的同步（或locking）上。因而，为了能在多核机器上允许可扩展的数据分析，一些好的解决方案必须能最小化加锁开销。

在本paper中，我们提出了一种称为”HOGWILD!”的简单策略来消除与锁相关的开销：无锁方式并行运行SGD。在HOGWILD中，各处理器被允许公平访问共享内存，并且能随意更新内存私有变量（individual components）。这样的lock-free scheme看起来注定会失败，因为处理器可以覆盖写（overwrite）其它的处理器的操作。然而，当数据处理是稀疏时，这意味着单独的SGD steps只会修改决策变量的一小部分，我们展示了内存覆盖写（memory overwrites）很少发生，并且当它们发生时只会将很少的错误引入到计算中。我们展示了，理论上和实验上一个近似的与处理器数成线性加速，这通常发生在稀疏学习问题上。

在第2节，我们对稀疏概念公式化，它足够保障这样的加速，并提供了在分类问题、协同过滤、图分割上关于稀疏机器学习问题的示例。我们的稀疏性概率允许我们提供关于线性加速的理论保证。作为我们分析的一个副产品，我们也派生了常数步长（constant stepsizes）收敛率的算法。我们展示了使用constant stepsize schemes的1/k收敛率是可能的，它实现了一个在常数时间上的指数级补偿（backoff）。该结果本身挺有意思的，它展示了不必满足于$1/\sqrt{k}$来保证在SGD算法上的健壮性。

实际上我们发现，无锁版的计算性能要超过我们的理论保证。我们实验上比较了lock-free SGD，以及其它最近提出的方法。结果展示了所有提出内存锁(memory locking)的方法，比起lock-free版本要慢很多。

2.稀疏可分的cost functions

我们的目标是，最小化一个函数：$f: X \subseteq R^n \rightarrow R$：

…(1)

这里，e表示了$\lbrace 1, ..., n \rbrace$的一个小的子集，其中$x_e$表示向量x在坐标索引e上的值。在我们的lock-free方法中的关键点是，与许多机器学习问题相关的cost functions是稀疏的（sparse）的，$\mid E \mid$和n都非常大，但每个单独的$f_e$只在x的一小部分成分起作用。也就是说，每个子向量$x_e$只包含了x的一少部分成分(components)。

(2.1)的cost function引入了一个hypergraph：$G=(V,E)$，它的节点是x的单个元素。每个子向量$x_e$相当于在图$e \in E$中引入一条边，它包含了节点的一些子集。以下的示例展示了该概念。

图1: 由cost function引入的样本图. (a) 一个sparse SVM会引入一个hypergraph，其中每个hyperedge对应一个样本 (b) 一个矩阵补全示例，它在行与列间引入了一个二分图（bipartite graph），如果有出现一个entry，那么两个节点间就有一条edge (c) 在graph-cut问题中的hypergraph就是一个简单图，它的切分就是我们想找的

2.1 Sparse SVM

假设我们的目标是，拟合一个SVM：数据对为$E = \lbrace (z_1,y_1), ..., (z_{\mid E \mid}, y_{\mid E \mid}\rbrace$。其中$z \in R^n$和y是对于每个$(z,y) \in E$的一个label：

…(2.2)

其中，我们知道一个先验（priori）是，样本$z_{\alpha}$是非常稀疏的。为了以(2.1)的形式编写该cost function，假设$e_{\alpha}$表示该组件在$z_{\alpha}$中是非零的，并假设$d_u$表示在第u(u=1,2,…,n)维上非零的训练样本数。可以将(2.2)改写成：

…(2.3)

在(2.3)中的求和只依赖通过集合$e_a$索引的x的components。

2.2 矩阵补全（Matrix Completion）

在矩阵补全问题上，我们从索引集合E中提供了一个低秩的、$n_r \times n_c$的矩阵X的entries。这种问题在协同过滤（CF）、欧氏距离估计、聚类中常出现。我们的目标是，从该数据的稀疏样本中重构Z。一种流行的启发法（heuristic）可以将Z的估计恢复成：以下最小化公式得到的一个$LR^*$的因子乘积：

…(2.4)

其中，L是$n_r \times r$， R为$n_c \times r$，$L_u(对应R_v)$表示L（对应:R）的第u（对应：vth）行。为了将该问题放入到稀疏形式，如(2.1)所示，我们将(2.4)编写成：

其中：$E_{u-}= \lbrace v: (u,v) \in E \rbrace$，$E_{-v} = \lbrace u: (u,v) \in E \rbrace$

2.3 Graph Cuts

略

2.4 结论

在所有三个示例中，在一个特定项$f_e$上所涉及的components数目，对于所有总条目数来说只占很小比例。我们将该概率进行公式化，定义了以下的关于hypergraph G的统计：

…(2.6)

量$\Omega$可以简单量化hyper edges的size。$\rho$决定了与任意给定edge交叉的edges最大比例。$\Delta$决定了与任何变量交叉的edges的最大比例。$\rho$是一个关于hypergraph稀疏度的衡量，其中$\Delta$决定着节点的正则化（node-regularity）。对于我们的例子，我们可以做出以下关于$\rho$和$\Delta$的观察：

• 1.Sparse SVM。$\Delta$是在一个样本中出现的任何特征的最大频率，$\rho$决定着hypergraph是如何聚类的。如果一些特征在整个数据集上很常见，那么$\rho$会与某一个很接近。
• 矩阵补全（Matrix Completion）：如果我们假设，提供的样本是随机均匀抽样的，我们可以看到超过$n_c log(n_c)$个样本，接着$\Delta \approx \frac{log(n_r)}{n_r}$和$\rho \approx \frac{2log(n_r)}{n_r}$ 。它会遵从一个彩票收集问题（coupon collector argument）。
• 3.Graph Cuts。 $\Delta$是由$\mid E \mid$划分的最大度(degree)，$\rho$至少为$2\Delta$。

我们现在描述了一个简单的protocol，当$\Omega, \Delta, \rho$都很小时，它会在处理器数上达到一个线性加速。

3.Hogwild!算法

这里我们讨论并行化处理setup。我们假设，一个具有p个处理器的共享内存模型。决策变量x可以被所有处理器访问。每个处理器可以读取x，也可以为x贡献一个更新向量（update vector）。向量x存储在共享内存中，我们假设，component-wise加法操作是原子的，也就是说：

对于一个标量a和$v \in \lbrace 1,...,n \rbrace$，该操作可以被任意处理器原子执行。该操作在大多数现代硬件上不需要一个独立的锁结构：这样的一个操作在GPUs和DSPs上是单个原子指令，它在像Intel Nehalem这样的专有目的多核处理器上可以通过一个compare-and-exchange操作来实现。相反的，一次更新多个components的操作需要一个辅助锁(auxiliary locking)结构。

每个处理器接着按照算法1的流程。为了完整描述该算法，假设：

• $b_v$表示在$R^n$中的标准基元素（standard basis elements）之一，其中v的范围为1, …, n。也就是说，$b_v$在第v个component上等于1, 否则为0. 假设$P_v$表示在坐标v上的欧几里德投影矩阵，例如：$P_v = b_v b_v^T$。其中$P_v$是一个对角矩阵，它在第v个对角上为1,否则为0。
• $G_e(x) \in R^n$表示函数$f_e$与 $\mid E \mid$相乘的一个梯度或者子梯度。也就是说，我们将$f_e$，从坐标e上的一个函数扩展为$R^n$上所有坐标上，通过忽略下标e来得到。那么：

这里，在$\neg e$的组件上的$G_e$等于0.使用一个稀疏表示，只需要知道通过e索引的components中的x的值，我们就可以计算$G_e(x)$。注意，从E进行平均随机抽样得到e（uniform random sampling），我们具有：

在算法1中，每个处理器会均匀地随机抽取一个项$e \in E$，计算在$x_e$上$f_e$的梯度，接着：

(3.1)

重要的是，注意，该处理器只修改通过e索引的变量，在$\neg e$中（e之外）的保持不变。

• $\gamma$: 我们假设，stepsize $\gamma$是一个固定的常数。
• $x_j$: 尽管这些处理器并不知道任何其它处理器是否已经修改了x，我们定义$x_j$是决策变量x在j执行更新后的状态(state)。由于两个处理器可能会在同时写入x，我们需要注意该定义，但我们会通过随机方式来简单断绝关系。注意，$x_j$通常使用一个旧的梯度进行更新，它基于x的一个在多个时钟周期前读取的值。我们使用$x_{k(j)}$来表示用于产生状态$x_j$的用于计算梯度或次梯度的决策变量值。

在下文中，我们提供了这种异步、增量梯度算法收敛的条件。另外，我们也展示了，如果通过f引入的hypergraph是同性的（isotropic）并且稀疏的，那么，该算法的收敛几乎与它的serial版本具有相同数目的梯度计算steps。由于我们以并行方式运行并且无锁，这意味着我们会得到一个与处理器数目成接近线性关系的加速。

注意：下标i,j,k指的是迭代数，v和e指的是components或者components的子集。

4.Lock-Free Parallelism的Fast Rates

我们接着讲述Hogwild!算法的理论分析。为了让这个分析更易理解，我们假设，我们会使用以下的“有放回（with replacement）”过程进行更新：每个处理器会均匀随机抽样一条边e，并计算该决策变量的当前值上的$f_e$的一个次梯度。

注意，该stepsize比(3.1)的step要更多一个因子$\mid e \mid$。注意，该更新完全等价于：

…(4.1)

该概念对于下面的分析更方便。

该有放回（with replacement）scheme假设：一个梯度被计算，那么它的components中只有一个元素被用于更新该决策变量。这样的一个scheme计算很浪费，因为该梯度的components其它部分携带着关于对cost function进行递减的信息。因此，实际上以及在我们的实验中，我们会执行该过程的一个修改版本。在每个epoch的开始处，我们将这些边进行无放回（without replacement）划分到所有处理器上。这些处理器接着在它们各自的队列上，对每条边的所有components执行完全更新（full updates）。然而，我们需再次强调的是，我们不会实现对任何变量的任何锁机制。我们不会分析该“无放回（without replacement）”过程，因为在任何无放回抽样模型中，没人可以对SGD进行可控分析。实际上据我们所知，无放回抽样的所有分析，会产生与一个标准的次梯度下降算法(它会采用(2.1)完全梯度的steps)相当的rates。也就是说，这些分析建议：无放回抽样需要一个$\mid E \mid$因子，因而比有放回抽样需要更多的steps。实际上，这种糟糕的情况从不会观察到。事实上，在机器学习中更明智的做法是，在SGD上进行无放回抽样，实际效果要好于有放回的形式。

为了说明我们的理论结果，我们必须描述一些工程量，它对于我们的并行化SGD scheme的分析很重要。为了简化该分析，我们假设，在(2.1)中的每个$f_e$是一个convex函数。我们假设f的Lipschitz连续微分，会使用Lipschitz常数L：

…(4.2)

我们也假设，f是具有系数c很强的convex性质。这意味着：

…(4.3)

其中，f具有很强的convex性，存在一个唯一的最小解$x_*$，我们表示$f_* = f(x_*)$。我们额外假设，存在一个常数M，使得:

…(4.4)

我们假设，$\gamma c < 1$。（实际上，当$\gamma c > 1$，普通的梯度下降算法也会离散）

我们的主要结果通过以下进行归纳：

命题(Proposition) 4.1

假设在算法1中，当一个梯度被计算时，与它在step j被使用时，两者间的lag——$j - k(j)$，总是小于或等于$\tau$，即$j - k(j) \lt \tau$，那么$\gamma$被定义为：

…(4.5)

对于一些 $\epsilon > 0$和$\vartheta \in (0, 1)$的情况。定义$D_0 := \| x_0 - x_* \|^2$， 并让整数k满足：

…(4.6)

那么在关于x的k个compoments更新后，我们有$E[f(x_k) - f_*] \lt \epsilon$

在该case中，$\tau = 0$，它可以精准减小到由serial SGD达到的rate。如果$\tau = o(n^{1/4})$，$\rho$和$\Delta$通常为$o(1/n)$，可以达到一个相同的rate。在我们的setting中，$\tau$与处理器数据成比例，只要处理器数目小于$n^{1/4}$，我们就可以获得在线性rate的循环。

我们在附录证明了命题4.1的两个steps. …(略)

注意，在(4.6)中$log(1/\epsilon)$，对于一个常数stepsize的SGD scheme，我们的分析接近提供了一个1/k 的收敛率，不管是顺序版本（serial）还是并行版本（parallel）。另外，注意，我们的收敛率相当robust；我们会为曲率f的低估花费线性时间。相反的，, Nemirovski等人展示了当stepsize与迭代数成反比时，高估的c可能会产生指数下降（n exponential slow-down）。我们转向展示，我们可以消除(4.6)的log项，通过一个稍微复杂些的方式，其中stepsize会在多次迭代后缓慢递减。

5.Robust 1/k rates

假设，对于算法1, 我们使用stepsize $\gamma < 1/c$运行固定数目K次的梯度更新。接着，我们等待线程合并结果，通过一个常数因子$\beta \in (0,1)$来对$\gamma$进行reduce，接着运行$\beta^{-1} K$轮迭代。从某种意义上说，该piecewise constant stepsize protocol近似成一个1/k衰减的diminishing stepsize。以下分析与之前工作的主要不同之处是，对比开始非常大的stepsizes，我们的stepsize总是比1/c小。总是使用小的stepsizes运行，允许我们避免可能的指数级递减（exponential slow-downs），它发生于标准的diminishing stepsize schemes中。

为了更精准，假设$a_k$是任意满足下述条件的实数的序列：

…(5.1)

其中，$a_{\infty}$是一些关于$\gamma$的非负函数，它满足：

其中$c_r$和B是常数。这种递归是许多SGD收敛证明的基础，其中$a_k$表示在k轮迭代后的最优解的距离。我们会在附录中为Hogwild!选择合适的常数。我们也会在下面讨论对于标准的SGD算法的这些常数。

在$\gamma$上的依赖，对于下面的情况很有用。将(5.1)化解开：

假设我们希望该量（quantity）要比$\epsilon$要小。两项都要小于$\epsilon/2$是充分的。对于第二项，这意味着：

…(5.2)

对于第一项，我们需要：

它持有：

…(5.3)

通过(5.2)，我们应选择：$\gamma = \frac{\epsilon \theta}{2B}$，其中$\theta \in (0, 1]$。使用(5.3)进行组合，k满足

在k轮迭代后，我们会有$a_k \ge \epsilon$。这几乎可以提供给我们一个1/k的rate，模上$log(1/\epsilon)$因子。

为了消除log因子，我们可以实现一个backoff scheme，其中，我们在多轮迭代后通过一个常数因子来减小stepsize。这种backoff scheme有两个phases：第一个阶段将包含以一个指数的rate收敛到 $x_*$的平方半径（它比$\frac{2B}{c_r}$要小）的球。接着，我们将通过对stepsize进行微调（shrinking）收敛到$x_*$。

为了计算到达在球体内所需的迭代次数，假设初始stepsize选择为：$\gamma = \frac{\theta}{c_r} (0< \theta <1)$。stepsize的选择保证了$a_k$会收敛到$a_{\infty}$。我们使用参数$\theta$来展示，我们不需要做多少调整，即可在我们的算法中得到最优stepsize（例如：$\theta=1$）的下限。使用(5.3)，我们可以发现：

(5.4)

k轮迭代后足够收敛到该球体。注意，这是一个线性rate的收敛率。

现在，假设$a_0 < \frac{2\theta B}{c_r}$。假设在每一轮通过一个因子$\beta$来减小stepsize。这会导致通过一个因子$\beta$来减小已经达到的$\epsilon$。从而，在$log_{\beta} (a_0 / \epsilon)$轮迭代后，我们的accuracy会是$\epsilon$。迭代的总轮数接着会是公式(5.3)的各项求和，其中，$a_0$通过之前的epoch被设置成已经达到的半径，$\epsilon$被设置成$\beta \times a_0$。从而，对于epoch数v，初始距离是$\beta^{v-1} a_0$，最终的半径为$\beta^v$。

5.1 顺序型（serial）SGD的结论

我们对比了constant step-size protocol，以及在第k轮迭代将stepsize设置为$\gamma_0 / k$（应用在等式(2.1)的标准顺序型(serial)增量梯度算法的一些初始step size $\gamma$）。 Nemirovsk[23]等人展示了到最优解的期望平方距离，$a_k$, 满足：

我们可以将该递归式放到公式(5.1)中，通过设置：$\gamma_k = \gamma, c_r = 2c, B= \frac{M^2}{4c}, a_{\infty} = \frac{\gamma M^2}{4c}$。

[23]的作者演示了一个大的step size: $\gamma_k = \frac{\theta}{2ck}, \theta > 1$ 可以产生一个边界：

该边界可以通过将这些算法参数插入到公式(5.6)中、并使得$D_0=2a_0$ 来得到。

注意，两个边界渐近的在M、c、k上有相同的依赖，表达式：

当$\beta \approx 0.37$是最小的，等于1.34. 表达式：

当$\theta=2$时是最小的，等于1. 因此，产生的常数在constant stepsize protocol中当所有其它参数设置为最优时，会稍微变差些。然而，如果$D_0 \gt M^2/c^2$，那么1/k protocol的error会与$D_0$成比例，但我们的constant stepsize protocol仍在初始距离上只有一个log依赖。再者，constant stepsize scheme在对曲率参数c高估上会更健壮些（robust）。而对于1/k protocol，如果你高估了曲率（对应于$\theta$的一个小值），你会获得较慢的收敛率。简单的，在[23]中的一维样本展示了，$\theta=0.2$可以生成一个$k^{-1/5}$的收敛率。在我们的scheme中，$\vartheta=0.2$会通过一个因子5来简单增加迭代数目。

在[23]中提出的fix，会渐近式产生比$1/\sqrt{k}$更慢的收敛率。值得注间的是，我们不需要满足于这些更慢的收敛率，仍可以在1/k rates达到健壮收敛。

5.2 补偿（backoff） scheme的并行化实现

该scheme会为HOGWILD!产生一个1/k的收敛率，只有在每一轮（round/epoch）迭代结果时发生同步开销。当为Hogwild实现一个backoff scheme时，处理器间会在何时reduce stepsize上达到一致。一个简单的策略是，在所有的处理器上以一个固定数目的迭代次数运行，等待所有线程完成，然后在一个主线程上全局进行reduce stepsize。我们注意到，它可以为这些线程消除合并的需要，通过发送带外信息（out-of-band messages）给处理器来发送何时对$\gamma$进行reduce的信号来完成。这会让理论分析变得复杂，因为有可能有例外：当不同处理器以不同stepsizes运行时，但实际上可以允许某一个避免同步开销。我们不会实现该scheme，因此不会更进一步分析该思想。

6.相关工作

大多数并行化SGD的schemes是 Bertsekas and Tsitsiklis[4]提出的变种。实际上，在[4]中，他们描述了通过主从方式（master-worker）跨多机计算来使用stale gradient updates（老的梯度更新）,也描述了不同处理控制访问决策变量的特定组件的settings。他们证明了这些方法的全局收敛，但没有提供收敛率。这些作者已经展示了SGD收敛率对多种模型是健壮的。

我们也注意到，constant stepsize protocols结合backoff过程在SGD实践中是权威，但在理论上不是。一些理论性工作至少已经展示了这些protocols的收敛性，可以在[20, 28]中找到。这些工作并没有确立上述的1/k rates。

最近，许多parallel schemes被提出。在MapReduce中，Zinkevich等提出在不同的机器上运行许多SGD实例，然后对output进行平均[30]。尽管作者宣称该方法可以同时reduce他们的估计方差(variance)和整体偏差（bias），在我们的实验中，对于我们关注的那类问题来说，该方法的效果不能胜过serial scheme。

通过一个distributed protocol对梯度求平均的schemes也由许多作者提出[10, 12]。而这些方法也可以达到线性加速，但他们很难在多核机器上有效实现，因为他们需要大量通信开销。分布式梯度求平均需要在多核之间进行消息传递，多个核需要频繁进行同步，以便计算合理的梯度平均。

与我们工作最接近的是round-robin scheme，它由Langford[16]提出。在该scheme中，多个处理器会排好序，然后按顺序更新决策变量。其中为进行写操作对内存上锁时所需时间，对比起梯度计算时间来说忽略不计，该方法会产生一个线性加速，因为在梯度中的lag所产生的errors并不会太剧烈。然而，我们注意到，在许多机器学习应用中，梯度计算时间是非常快的，我们现在证明了在许多应用中，Hogwild!的效果要胜过round-robin方法一个阶的量级。

7.实验

我们在许多机器学习任务上运行了数值型实验，并对比了[16]中的round-robin方法，它在Vowpal Wabbit[15]中有实现。我们将该方法简写为RR。为了公平，我们手工编码RR以便接近等同于Hogwild!方法，唯一的区别是，他们如何更新梯度的scheme不同。与Vowpal Wabbit软件中的RR的一个明显不同是，我们优化了RR的locking和signaling机制，以便使用spinlocks和busy waits（这对于通用signaling来说没有必要去实现round robin）。我们验证了对于我们讨论的问题，该optimization在wall clock time是会产生多一个阶。

我们也比较了一个称为AIG的模型，它可以看成是RR和Hogwild!间的一个折中。AIG会运行一个等同于Hogwild!的protocol，但它会锁住在e中的所有变量（在算法1中第4行的for loop的前后）。我们的实验演示了该细粒度的locking会产生不希望看到的速度减慢。

所有实验都以C++进行编码，并运行一个相同的配置：一个dual Xeon X650 CPUs(6 cores x 2超线程)机器，它具有24GB的RAM，software RAID-0超过7, 2TB Seagate Constellation， 7200RPM disks。kernel为Linux 2.6.18-128. 我们使用的内存不超过2GB。所有训练数据都存储在一个7-disk raid 0上。我们实现了一个定制的文件扫描器来演示从磁盘将数据集读取到共享内存的速度。这允许我们从raid读取的速率达到接近1GB/s。

所有的实验均使用一个constant stepsize $\gamma$，它在每次整个训练集pass后会通过一个因子$\beta$进行衰减。我们使用20个这样的passes运行所有的实验，尽管更少的epochs通常就能达到收敛。我们的结果表明，对于learning rate $\gamma$收敛的最大值，我们会使用$\beta = 0.9$的吞吐量。我们注意到，结果与更大范围$(\gamma,\beta)$ pairs看起来相似，所有这三种并行化schemes的train erros和test errors都在相互很小的误差内。在分类问题会在第2节描述。

Sparse SVM。我们在Reuters RCV1数据集上测试了我们的sparse SVM实现，使用二分类任务CCAT。它具有804414条样本，划分为：23149训练样本，781265测试样本，存在47236个特征。我们在我们的实验中交换了训练集和测试集，以演示并行多核算法的可扩展性。在本例上，$\rho = 0.44, \Delta = 1.0$，Hogwild中大值通常会产生一个badcase。在图3a中，我们看到，Hogwild可以达到3倍加速，而RR会随着线程的增加而变差。确实，对于快速梯度，RR要比顺序实现（serial implement）还差。

图3: 对于不同(a) RCV1 (b) Abdomen (c)DBLife，总CPU时间 vs. 线程数

对于该数据集，我们也实现了在[30]中的方法，它会以并行并对输出求平均方式运行多个SGD。在图5b中，我们展示了跨并行线程并在每个pass结尾进行ensemble求平均的方式的train error。我们注意到，线程只在计算的最后需要通信，每个并行线程会在每个pass中接触到每条数据样本。因而，10线程会比顺序版本（serial version）运行10倍（更多）的梯度计算。这里，不管是serial版本还是10个实例的版本，error是相同的。我们可以在该问题上下结论，并行求平均的scheme并没有优点。

矩阵补全（Matrix completion）。我们在三个非常大的matrix比赛问题中运行Hogwild!。Netflix Prize数据集具有17770行，480189列，以及100198085个条目。KDD Cup 2011(task 2）数据集具有624961行，1000990列，252800275个条目。我们也人工生成了一个低秩矩阵，它的rank=10, 1e7个行和列，2e9个条目。我们把该数据集称为”Jumbo”。在人工生成的样本中，$rho$和 $\Delta$都在1e-7. 这些值与$rho$和 $\Delta$都在1e-3阶上的真实数据集形成鲜明对比。

图4:

图5a展示了这三个数据集在使用Hogwild!的加速。注意，Jumbo和KDD数据集不能完全装载进(fit in)我们分配的内存，但即使从磁盘读取数据时，Hogwild都能获取一个接近线性的加速。Jumbo会花费2个半小时来完成。图4展示了Hogwild!、AIG和RR在三个矩阵补全（Matrix completion）数据集上的实验结果。与快速计算梯度的实验相似，RR并没有展现出比serial版本的方式有任何提升。事实上，使用10个线程，RR在KDD Cup上会比serial版本慢12%，在Netflix版本上会慢62%。实际上，以合理的时间量完成Jumbo实验是很慢的，而10-way并行化Hogwild!实现可以在3个小时内解决该问题。

图5

Graph Cuts。 我们的第一个cut问题是一个在计算机视觉中很流行的标准图片切分。xxx（略）

如果梯度很慢会怎么样？ 在DBLIFE数据集上，当梯度计算很慢时，RR方法会获得一个几乎线性的加速。这抛出了一个问题：对于梯度计算慢的问题，RR是否要胜过Hogwild？为了回答这个问题，我们运行了RCV1实验，并在每次梯度计算时引入一个人工生成的delay来模仿一个慢梯度计算。如图5c所示，我们画出了求解SVM问题所需的wall clock time，我们会对比RR与Hogwild方法的delay。

注意到，Hogwild!会获得一个更大的计算时间减少的收益。当delay为几ms时，两种方法的加速是相同的。也就是说，如果一个梯度花费超过1ms的计算时间，RR会与Hogwild相当（但不是超过）。在该rate上，每个小时只能计算大约100w次SGD，因此，梯度计算必须非常耗时，这时RR方法才有竞争力。

8.结论

我们提出的Hogwild算法利用了在机器学习中的稀疏性，在多种应用上可以达到接近线性的加速。经验上，我们的实验可胜过理论分析。例如，$\rho$在RCV1 SVM问题上相当大，我们也仍能获得巨大加速。再者，我们的算法允许并行加速，即使当梯度计算非常密集时。

我们的Hogwild scheme可以泛化到：一些变量的出现相当频繁的问题上。我们可以在高度竞争的那些特定变量上，选择不更新。例如，我们可能希望添加一个bias项到我们的SVM上，然后仍运行一个Hogwild scheme，更新bias只需要每上千次迭代时进行。

对于将来的工作，我们有兴趣枚举那些允许没有冲突的并行梯度计算的结构。也就是说，可能会与SGD迭代有偏差，以便完全避免处理器间的内存竞争。例如，最近的工作【25】提出了一个在matrix比赛问题中的SG的biased ordering，来完全避免处理器间的内存竞争。关于如何将该方法泛化到其它结构上，以便更快的机器学习计算，这样的调查也在开展中。

参考

1.https://arxiv.org/pdf/1106.5730v2.pdf

SM McNee等人在2006年《Being Accurate is Not Enough: How Accuracy Metrics have hurt Recommender Systems》中提出accurate是不够的：

1.介绍

假设你正使用一个关于旅游的推荐系统。假设它给出的所有推荐都是你已经旅行过的地方，即使该系统在ranking上做的很好（所有的地方都根据你的访问偏好排序），这仍是一个很差的推荐系统。你会使用这样的系统吗？

不幸的是，我们当前就是这样测试我们的推荐系统的。在标准方法中，旅游推荐器会对推荐新地方进行惩罚（而非对已经访问过的地方进行惩罚）。当前的accuracy指标（比如：MAE），会将算法的预测与用户对item的评分进行比较来衡量推荐算法效果。使用这些指标的最常用技术是：留一法（leave-n-out方法）。本质上：我们会对推荐用户已经访问过的地方进行奖励（reward），而非对用户将要访问的新地方进行奖励。

2.Similarity

通常，推荐列表中会包含相似的items。

Accuracy指标不会看到该问题，因为它们被设计用来判断单个item预测的accuracy；他们不会判断整个推荐列表的内容。不幸的是，用户是与这样的列表进行交互的。所有推荐是在当前推荐列表、以及之前用户已经看过的列表的上下文中做出的。该推荐列表应作为一个整体进行评判，而非作为各个单独items的一个集合。

解决该问题的一个方法是：[Ziegler 2005]：推荐列表的Intra-List Similarity Metric和Topic Diversification。返回的列表可以进行变更（增加/减小diversity）。结果表明，变更后的列表在accuracy上更差，但用户更喜欢变更后的列表。

依赖于用户的意图，出现在该list中的items组合，对用户对推荐的满意度的影响要超过item accuracy的变更。

3.惊喜性（Serendipity）

推荐系统中的Serendipity指的是：接收到一个意料之外的item推荐。与Serendipity相关的心理反应很难在指标上捕获。但如果去掉该构成，该概念的unexpectedness部分——（即：收到推荐的新颖性novelty）——仍然很难measure。该概念的反面即：ratability(可估的），则很容易measure。可以使用leave-n-out方法进行measure。

我们可以将一个item的ratability定义为：在已知user profile的情况下，该item作为用户将消费的next item的概率。从机器学习的角度，具有最高ratability的item会成为next item。因此，推荐器算法在accuracy metrics打分良好。

隐式假设是：一个用户总是会对具有最高ratability的items感兴趣。而该假设在分类问题中是true的，但在推荐系统(recomenders)中并不总是true的。用户通常会对那些不可预料的items的推荐进行judge。例如，一个在线音乐商店的推荐系统，会使用一个User-User CF算法。最常见的推荐是： the Beatle乐队的“White Album”。从accuracy的角度，这些推荐是十分准确的（dead-on）：大多数用户非常喜欢该专辑。但从有用性(usefulness)的角度，该推荐是完全失败的：每个用户已经拥有了“White Album”、或者明确表示不买它。尽管它的估计分非常高，但“White Album”推荐几乎从不会被用户播放，因为它们几乎没价值。

之前的许多研究【[McNee 2002, Torres 2004】表明：推荐算法会生成相互间不同品质的推荐列表。用户偏向于来自不同的推荐算法的列表。用户会选择不同词汇（words）来描述推荐（比如：User-based CF被认为是生成“novel”的推荐）

这建议我们需要其它方法来对推荐算法进行分类。而没有用户的反馈，“serendipity metric”可能很难被创建，评判许多算法的其它指标会提供关于推荐算法不同之处的一个更详细的画面。

3.用户体验和期望

用户满意度并不总是与推荐的accuracy相关。还有许多重要的因素必须考虑。

在推荐器中，新用户与老用户间有不同的需求。新用户可能会从一个生成高概率items的算法中受益，因为在采用推荐器之前他们必须与推荐器确立信任和交往。之前的工作表明，对于新用户的算法选择，会极大影响用户体验和推荐系统生成它们的accuracy。

我们之前的工作表明，不同的语言和文化背影会影响着用户满意度[Torres 2004]。一个在母语用户环境下的推荐器要比使用其它语言的推荐器更受喜欢，即使被推荐的items本身是使用另一种语言的（比如：一个葡萄牙语的研究paper推荐器会推荐使用英语的papers）

4.往前看

accuracy metrics可以极大帮助推荐系统；他们给我们提供了一种可比较算法的方式，并能创建健壮的实验设计。我们不应停止使用它们。但我们也不能只使用它们来判断推荐器。现在，我们需要思考如何与推荐系统的用户更贴近。他们不关心使用一个具有在某指标上更高得分的算法，他们想要一个有意义的推荐。有许多方法可以做到。

首先，我们需要评判：当用户看到推荐时的质量：推荐列表。为了这样做，我们需要创建一些在推荐列表上的指标，而非出现在一个list上的items。已经存在一些指标，比如：Intra-List Similarity metric，但我们需要更多指标来理解这些lists的其它方面。

第二，我们需要理解在推荐算法间的不同之处，并能以ratability之外的方式来进行measure。用户可以告诉在推荐算法间的不同。例如，当我们更改在MovieLens电影推荐器上的算法，我们会接收到许多来自用户的emails，它们会有疑惑：为什么MovieLens的推荐会变得如引“守旧（conservative）”。在MAE measures上的得分良好，但对用户来说却很明显不同。

最后，用户回复推荐会超过一段时间，从新用户到已体验用户会增长。每当他们来到系统时，他们具有一些理由过来：他们有一个诉求（purpose）。我们需要判断我们为每个用户生成的推荐是否能满足它们的需要。到到我们认识与用户的这种关系之前，recommenders会继续生成不匹配的推荐。

最后，recommenders的存在可以帮助用户。作为一个社区，我们已经创建了许多算法和方法来研究recommender算法。现在也开始从用户为中心的角度来研究recommenders，而不再仅仅是accurate的角度。

参考：

https://dl.acm.org/citation.cfm?id=1125659

本文主要译自Tomas Mikolov、Jeffrey Dean等人的.

Abstract

最近介绍的continuous Skip-gram model是一个很有效的方法，用于学习高质量的分布式向量表示，它可以捕获大量精准的语法结构和语义词关系。在该paper中，我们介绍了许多种扩展，用来改进向量的质量和训练速度。通过对高频词进行subsampling，我们可以获得极大的速度提升，也可以学到更常规的词表示。我们也描述了在hirearchical softmax之外的一种简单的备选方法：negative sampling。

词向量表示的一个限制是，它不区分词顺序(word order)，它们不能表示常用短语。例如，”Canada”和”Air”的意思，不能简单的组合在一起来获取”Air Canada”（加拿大航空）。受该示例的启发，我们描述了另一种方法来寻找文本中的短语，并展示了如何在上百万的句子中学习到好的向量表示。

介绍

词在向量空间上的分布式表示(distributed representations)，通过将相似的词语进行群聚，可以帮助学习算法在nlp任务中完成更好的性能。词向量表示的最早应用可以追溯到1986年Rumelhart, Hinton等人提的(详见paper 13). 该方法用于统计语言建模中，并取得了可喜的成功。接下来，应用于自动语音识别和机器翻译(14,7)，以及其它更广泛的NLP任务(2,20,15,3,18,19,9)

最近，Mikolov（8）提出了Skip-gram模型，它是一个高效的方法，可以从大量非结构化文本数据中学到高质量的词向量表示。不同于以往用于词向量学习所使用的大多数神经网络结构，skip-gram模型(图1)不会涉及到稠密矩阵乘法(dense matrix multiplications)。这使得学习过程极为高效：一个优化版的单机实现，一天可以训练超过10亿个词。

使用神经网络的词向量表示计算非常有意思，因为通过学习得到的向量可以显式地对许多语言学规律和模式进行编码。更令人吃惊的是，许多这些模式可以被表示成线性变换(linear translations)。例如，比起其它向量，向量计算vec(“Madrid”)-vec(“Spain”)+vec(“France”)与vec(“Paris”)的结果更接近(9,8)。

本文中，我们描述了一些原始skip-gram模型的扩展。我们展示了对高频词进行subsampling，可以在训练期间带来极大提升（2x-10x的性能提升），并且同时能改进低频词的向量表示的精度。另外，我们提出了一种Noise Contrastive Estimation (NCE) (4)的变种，来训练skip-gram模型，对比于复杂的hierachical softmax，它的训练更快，并可以为高频词得到更好的向量表示。

词向量表示受限于它不能表示常用短语，因为它们不由独立的单词组成。例如, “Boston Globe”（波士顿环球报）实际是个报纸，因而它不是由“Boston”和”Globe”组合起来的意思。因此，使用向量来表示整个短语，会使得skip-gram模型更有表现力。因此，通过短语向量来构成有意义的句子的其它技术（比如：递归autoencoders 17)，可以受益于使用短语向量，而非词向量。

从基于词的模型扩展成基于短语的模型相当简单。首先，我们使用数据驱动的方式标注了大量短语，接着我们在训练中将这些短语看成是独自的tokens。为了评估短语向量的质量，我们开发了一个类比推理任务(analogical reasoning tasks)测试集，它同时包含了词和短语。我们的测试集中的一个典型的类比对(analogy pair)如下：

“Montreal”:“Montreal Canadiens”::“Toronto”:“Toronto Maple Leafs”

如果与vec(“Montreal Canadiens”)-vec(“Montreal”)+vec(“Toronto”)最接近的向量是：vec(“Toronto Maple Leafs”)，那么我们可以认为回答是正确的。

译者注1：

• Montreal: 蒙特利尔(城市)
• Montreal Canadiens: 蒙特利尔加拿大人(冰球队)
• Toronto: 多伦多(城市)
• Toronto Maple Leafs: 多伦多枫叶队(冰球队)

译者注2:

英文是基于空格做tokenized的. 常出现这个问题。

最后，我们再描述skip-gram模型的另一个有趣特性。我们发现，向量加法经常产生很有意思的结果，例如：vec(“Russia”)+vec(“river”)的结果，与vec(“Volga River”)接近。而vec(“Germany”)+vec(“capital”)的结果，与vec(“Berlin”)接近。这种组成暗示着，语言中一些不明显的程度，可以通过使用基本的词向量表示的数据操作来获取。

2.Skip-gram模型

Skip-gram模型的训练目标是，为预测一个句子或一个文档中某个词的周围词汇，找到有用的词向量表示。更正式地，给定训练词汇$w_1,w_2,w_3,...,w_T$, Skip-gram模型的学习目标是，最大化平均log概率：

… (1)

其中，c是训练上下文的size($w_t$是中心词)。c越大，会产生更多的训练样本，并产生更高的准确度，训练时间也更长。最基本的skip-gram公式使用softmax函数来计算 $p(w_{t+j} | w_t)$:

… (2)

其中，vw和v’w表示w的输入向量和输出向量。W则是词汇表中的词汇数。该公式在实际中不直接采用，因为计算$\nabla {logp(w_{O} | w_I)}$与W成正比，经常很大($10^5-10^7$次方)

2.1 Hierarchical Softmax

略，详见另一篇。

2.2 Negative Sampling

Hierarchical Softmax外的另一可选方法是Noise Contrastive Estimation(NCE)，它由Gutmann and Hyvarinen（4）提出，将由Mnih and Teh(11)用于语言建模中。NCE假设，一个好的模型应该能够通过logistic regression从噪声中区分不同的数据。这与Collobert and Weston（2）的hinge loss相类似，他通过将含噪声的数据进行排序来训练模型。

而NCE可以近似最大化softmax的log概率，Skip-gram模型只关注学习高质量的向量表示，因此，我们可以自由地简化NCE，只要向量表示仍能维持它的质量。我们定义了Negative sampling(NEG)的目标函数：

在Skip-gram目标函数中，每个$P(w_O \mid w_I)$项都被替换掉。该任务是为了区分目标词wo，以及从使用logistic回归的噪声分布$P_n(w)$得到的词。其中每个数据样本存在k个negative样本。我们的试验中，对于小的训练数据集，k的值范围(5-20)是合适的；而对于大的数据集，k可以小到2-5。Negative sampling和NCE的最主要区分是，NCE同时需要样本和噪声分布的数值概率，而Negative sampling只使用样本。NCE逼近最大化softmax的log概率时，该特性对于我们的应用不是很重要。

NCE和NEG都有噪声分布$P_n(w)$作为自由参数。对于$P_n(w)$我们采用了一些不同选择，在每个任务上使用NCE和NEG，我们尝试包含语言建模（该paper没提及），发现unigram分布U(w)提升到3/4幂（如：$U(w)^{2/4}/Z$）时，胜过unigram和uniform分布很多！

2.3 高频词的subsampling

3.结果

该部分我们评估了Hierarchical Softmax(HS), Noise Contrastive Estimation, Negative Sampling和训练词汇的subsampling。我们使用由Mikolov引入的analogical reasoning task进行评估(8)。该任务包含了类似这样的类比：s“Germany” : “Berlin” :: “France” : ?。通过找到这样的一个向量x，使得在cosine距离上，vec(x)接近于vec(“Berlin”)-vec(“Germany”)+vec(“France”)。如果x是”Paris”，则该特定示例被认为是回答正确的。该任务有两个宽泛的类别：

• syntactic analogies：句法结果的类比(比如： “quick” : “quickly” :: “slow” : “slowly”)
• semantic analogies：语义类比（比如：国家与城市的关系）

对于训练Skip-gram模型来说，我们已经使用了一个大数据集，它包括许多新文章（内部Google数据集，超过10亿单词）。我们抛弃了训练集中在词汇表中出现次数不足5次的词汇，这样产生的词汇表大小为：692k。在词类比测试中，多种Skip-gram模型的性能如表1。在analogical reasoning task上，该表展示了Negative Sampling的结果比Hierarchical Softmax效果要好，并且它比Noise Contrasitive Estimation的效果也略好。高频词的subsampling提升了好几倍的训练速度，并使得词向量表示更加精准。

仍有争议的是，skip-gram模型使它的向量更适合linear analogical reasoning，但Mikolov的结果(8)也展示了在训练数据量极剧增加时，由标准的sigmoidal RNN(非线性)可以在该任务上获得极大的提升，建议，对于词向量的线性结果，非线性模型同样可以有很好的表现。

4.学习短语

在前面的讨论中，许多短语具有特定的意义，它不是单个词的含义的简单组合。为了学习到短语的向量表示，我们首先发现，在一些不常见的上下文中，有些词经常共现。例如，“New York Times”和”Toronto Maple Leafs”在训练数据中，被替换成唯一的token，但另一个bigram:”this is”则保留不做更改。

表2：短语的analogical reasoning task（完整测试集：3218个示例）。目标是使用前三2上计算第4个短语。在该测试集上最好的模型的准确率为72%

这种方法，我们可以产生许多合理的短语，同时也不需要极大增加词汇的size；理论上，我们可以使用所有n-gram来训练Skip-gram模型，但这样很耗费内存。在文本上标识短语方面，之前已经有许多技术提出。然而，对比比较这些方法超出了该paper范围。我们决定使用一种简单的基于数据驱动的方法，短语的形成基于unigram和bigram的数目，使用：

…(6)

其中，delta被用于一个打折系数(discounting coefficient)，它可以阻止产生过多的包含许多不常见词的短语。bigram的score如果比选择的阀值要大，那么则认为该短语成立。通常，我们会不断降低阀值，运行2-4遍的训练数据，以允许形成包含更多词的更长短语。我们使用一个新的关于短语的analogical reasoning task，来评估短语表示的质量。该数据集在网上是公开的。下载

4.1 短语的Skip-Gram结果

我们使用在前面的试验中相同的新闻数据，我们首先基于训练语料来构建短语，接着我们训练了多个Skip-gram模型，它们使用不同的超参数。在这之前，我们使用了300维的向量，上下文size=5。该设置可以在短语数据集上达到很好的效果，我们快速比较Negative Sampling和Hierarchical Softmax，是否采用高频token的subsampling。结果如表3所示：

表3：Skip-gram在短语类比数据集上的准确率。这些模型在10亿词的新闻数据集上进行训练

为了最大化短语类比任务的准确率，我们增加了训练数据量，使用了另一个包含330亿词汇的数据集。我们使用hierarchical softmax，1000维，上下文为整个句子。模型上的结果，准确率将达到72%。当我们将训练数据集减小到60亿的词汇量时，得到更低的准确率66%，这意味着，数据量的大小是十分重要的。

为了更深理解，不同模型学到的词向量表示的不同，我们人工检查了不同模型下的不常用短语的最近邻词。如表4，我们展示了这样的一个比较样例。前面的结果是一致的，它展示了可以学到的短语最佳向量表示模型是：hierarchical softmax和subsampling。

表4：两个模型下，给定短语，与它们最接近的其它条目

5.加法组合

我们展示了由Skip-gram模型学到的词和短语向量表示，它们展示出一种线性结构，这使得使用向量运算来执行精准的analogical reasoing成为可能。有意思的是，我们发现，Skip-gram表示法展示出了另一种线性结构，它可以将词向量进行element-wise加法组成。该现象见表5.

表5：使用element-wise加法的向量组合。使用最好的skip-gram模型得到的， 与该向量和接近的4个接近的tokens

向量的加法属性可以通过对训练目标进行检查来解释。该词向量与softmax非线性的输入存在线性关系。训练出的词向量用来预测句子周围的词，这些向量可以被看成是，用来表示一个词在特定上下文出现中的分布。这些值与由输出层计算的概率的对数(logP)相关，两个词向量的和（sum）与两个上下文分布的乘积（product）相关联。这里的该乘积是AND函数：两个词向量中都分配了高概率的词，也会得到高概率，否则会得到低概率。因而，如果“Vloga River”在相同的句子中，与”Russian”和”river”出现的很频繁，那么两个词向量的和将产生这样的特征向量，它们与”Vloga River”很接近。

6.目前的词向量表示的比较

之前，有许多作者在基于词向量的神经网络领域工作，并发表了许多模型，可以用于进一步使用和比较：最著名的有Collober和Weston(2), Turian(17)，以及Mnih和Hinton的(10). 我们从网上下载了这些词向量, 下载地址。Mikolov(8)已经在词类比任务上评估了这些词向量表示，其中，Skip-gram模型达到了最好的性能和效果。

表6：各种模型比较，空意味着词不在词汇表里.

为了更深地理解学到的向量质量的不同之处，我们提供了表6的比较。这些示例中，Skip-gram模型在一个大的语料上进行训练，可以看到，效果比其它模型好。部分原因是因为模型训练的词料词汇超过300亿个词，是其它数据集的3个数量级。有意思的是，尽管训练集更大，Skip-gram的训练时间复杂度比前面的模型还要短。

参考

－ 1.Domain adaptation for large-scale sentiment classi- fication: A deep learning approach

• 1 Yoshua Bengio, R´ejean Ducharme, Pascal Vincent, and Christian Janvin. A neural probabilistic language model. The Journal of Machine Learning Research, 3:1137–1155, 2003.
• [2] Ronan Collobert and Jason Weston. A unified architecture for natural language processing: deep neural networks with multitask learning. In Proceedings of the 25th international conference on Machine learning, pages 160–167. ACM, 2008.
• [3] Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Domain adaptation for large-scale sentiment classi- fication: A deep learning approach. In ICML, 513–520, 2011.
• [4] Michael U Gutmann and Aapo Hyv¨arinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. The Journal of Machine Learning Research, 13:307–361, 2012.
• [5] Tomas Mikolov, Stefan Kombrink, Lukas Burget, Jan Cernocky, and Sanjeev Khudanpur. Extensions of recurrent neural network language model. In Acoustics, Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on, pages 5528–5531. IEEE, 2011.
• [6] Tomas Mikolov, Anoop Deoras, Daniel Povey, Lukas Burget and Jan Cernocky. Strategies for Training Large Scale Neural Network Language Models. In Proc. Automatic Speech Recognition and Understanding, 2011.
• [7] Tomas Mikolov. Statistical Language Models Based on Neural Networks. PhD thesis, PhD Thesis, Brno University of Technology, 2012.
• [8] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. ICLR Workshop, 2013.
• [9] Tomas Mikolov, Wen-tau Yih and Geoffrey Zweig. Linguistic Regularities in Continuous Space Word Representations. In Proceedings of NAACL HLT, 2013.
• [10] Andriy Mnih and Geoffrey E Hinton. A scalable hierarchical distributed language model. Advances in neural information processing systems, 21:1081–1088, 2009.
• [11] Andriy Mnih and Yee Whye Teh. A fast and simple algorithm for training neural probabilistic language models. arXiv preprint arXiv:1206.6426, 2012.
• [12] Frederic Morin and Yoshua Bengio. Hierarchical probabilistic neural network language model. In Proceedings of the international workshop on artificial intelligence and statistics, pages 246–252, 2005.
• [13] David E Rumelhart, Geoffrey E Hintont, and Ronald J Williams. Learning representations by backpropagating errors. Nature, 323(6088):533–536, 1986.
• [14] Holger Schwenk. Continuous space language models. Computer Speech and Language, vol. 21, 2007.
• [15] Richard Socher, Cliff C. Lin, Andrew Y. Ng, and Christopher D. Manning. Parsing natural scenes and natural language with recursive neural networks. In Proceedings of the 26th International Conference on Machine Learning (ICML), volume 2, 2011.
• [16] Richard Socher, Brody Huval, Christopher D. Manning, and Andrew Y. Ng. Semantic Compositionality Through Recursive Matrix-Vector Spaces. In Proceedings of the 2012 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2012.
• [17] Joseph Turian, Lev Ratinov, and Yoshua Bengio. Word representations: a simple and general method for semi-supervised learning. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 384–394. Association for Computational Linguistics, 2010.
• [18] Peter D. Turney and Patrick Pantel. From frequency to meaning: Vector space models of semantics. In Journal of Artificial Intelligence Research, 37:141-188, 2010.
• [19] Peter D. Turney. Distributional semantics beyond words: Supervised learning of analogy and paraphrase. In Transactions of the Association for Computational Linguistics (TACL), 353–366, 2013.
• [20] Jason Weston, Samy Bengio, and Nicolas Usunier. Wsabie: Scaling up to large vocabulary image annotation. In Proceedings of the Twenty-Second international joint conference on Artificial Intelligence-Volume Volume Three, pages 2764–2770. AAAI Press, 2011.

本文主要译自paper 1.

Abstract

神经网络概率语言模型(NPLM)与过去广泛使用的n-gram语言模型相互竞争，甚至偶尔优于后者。NPLM最大的缺点是训练和测试时间超长。Morin和Bengio提出了一种层次化语言模型，它会构建一棵关于词的二叉树，它比非层次化的使用专家知识的模型快2个数量级。我们引入了一种快速的层次化语言模型，它使用一种简单的基于特征的算法，可以从数据中自动构建word树。我们接着展示，产生的模型胜过非层次化神经网络模型、n-gram模型。

介绍

统计语言模型的关注点是，构建基于词序列的概率模型。这样的模型可以被用于区分可能的序列与不可能的序列，广泛用于语音识别，信息检索，机器翻译。大多数统计语言模型都基于Markov猜想：一个词的分布只依赖于 在它之前出现的固定数目的词。该猜想明显是错误的，但它很简洁方便，因为它将固定长度的词序列的概率分布建模问题，缩减成：给定前面固定数目的词（称为上下文：context），建模下一个词的分布。此处，我们使用：$P(w_n | w_{1:n-1})$来表示分布，wn是下一个词, $w_{1:n-1}$表示上下文$(w_1,..,w_{n-1})$。

目前n-gram模型是最流行的统计语言模型，因为简单，并且性能很好。这些模型的条件概率表$P(w_n | w_{1:n-1})$，通过统计训练数据中的n元组，并进行归一化进行估计。因为n元组的数据是n的指数级，对raw counts进行平滑会达到很好的性能。n-gram模型有许多平滑方法，详见paper 2. 尽管n-gram模型有许多复杂的平滑方法，n-gram模型很难利用大量上下文，因为数据的稀疏性问题很严重。这种现象的主要原因是，经典的n-gram模型是本质上有界的条件概率表，里面的条目都是相互独立的。这些模型不会利用这样的事实：即相似的词常出现在相似的上下文中，因为它们没有相似性的概率。基于分类的n-gram模型（paper 3）主要解决该问题，通过将词和上下文，基于使用模式聚类到分类中，使用这些分类信息来提升泛化。它会提升n-gram的性能，这种方法引入了严格死板的相似性，因为每个词很典型，都属于确定的某个类。

另一种可选的、更灵活的抵消数据稀疏性问题的方法是，将每个词使用一个real-valued的特征向量，它会捕获该特性，以便相似的上下文中的词，具有相似的特征向量。接着，下一个词的条件概率可以被建模成一个关于上下文词和下一个词的平滑函数。这种方法提供了自动平滑，因为对于一个给定的上下文，相似的词可以保证分配到相似的概率。同样的，相似的上下文现在也可能具有相似的表示，并会生成对下一个词相似的预测。大多数基于该方法的模型，使用一个前馈神经网络(feed-forwark NN)，将上下文词汇的特征向量映射到下一个词的分布上。这种方法的可能最好模型是神经网络语言模型NPLM(paper 4)，在100w词级别的语料上，它胜过n-gram模型。

层次化神经网络语言模型

NPLM的主要缺点是，这样的相类似模型，训练和测试时间很慢。因为下一个词的概率计算，需要显式对词汇表中所有词进行归一化，对于给定下一个词的概率计算开销，以及对于在下一个词之上的所有分布的计算开销，事实上两者几乎一样：它们会花费关于词汇表size的线性时间开销。由于在这样的模型上，计算精确的梯度，需要重复计算给定上下文的下一个词的概率，通过增加概率来更新模型参数，训练时间与词汇表size成线性关系。通常，自然语言数据集包含着上万的词汇，这意味着即使以最简单方式训练这种类NPLM模型，在实际中的计算开销仍过大。一种加速该过程的方法是，使用专门的重要性sampling过程，来逼近要学习所需的梯度(paper 5)。然而，该方法可以本质上加速训练时间，测试时间的开销依然很快。

我们引入了层次化NPLM(paper 6)，对比普通的NPLM，它在训练和测试的时间复杂度均做到了指数级的衰减。通过二叉树替代NPLM中非结构化的词汇表，可以表示成一个层次化的词汇表词簇。每个词对应于树上的叶子节点，可以由顶点到叶子节点的路径唯一确定。如果N是词汇表的词数，并且树是一棵平衡树，任何词都可以由一串O(log N)二分决策来指定，它会指定两个子节点，当前节点可以访问到下一节点。该过程将N-way选择替换成一串O(log N)的二分选择。在概率术语中，N-way归一化，可以替换成一串O(log N)的局部(二分)归一化。结果上，词汇表中的词分布，可以通过提供访问左子节点的概率来指定。在层次化NPLM中，这样NPLM方式的局部概率的计算：采用一个特征向量作为上下文词汇，同时给当前节点的一个特征向量作为输入。下一个词的概率，由该词所对应路径的二分决策的概率指定。

当数据集包含上百万的词时，该模型的表现优于基于分类的3-gram，但比paper 6中的NPLM表现差。这种层次化NPLM模型，比普通的NPLM快2个数量级。这种方法的主要限制，主要是用于构建word树的过程。该树可以从WordNet IS-A分类体系开始，通过结合人工和数据驱动处理，并将它转换成一个二叉树。我们的目标是，将该过程替换成从训练数据中自动构建树，不需要任何专家知识。我们也探索了使用树（里面的词汇至少出现一次）的性能优点。

log-bilinear model

我们使用log-bilinear语言模型（LBL：Paper 7）作为我们层次化模型的基础，因为它的性能十分出色，并且很简洁。类似于所有神经网络语言模型，LBL模型将每个词表示成一个real-valued的特征向量。我们将词w的特征向量表示成:$r_w$，所有词的特征向量组成矩阵R. 模型的目标：给定上下文$w_{1:n-1}$，预测下一个词$w_n$。我们将要预测下一个词的的特征向量表示成$\hat{r}$，它可以通过对上下文词汇的特征向量进行线性组合得到：

公式一：$\hat{r}=\sum_{i=1}^{n-1}C_{i}r_{w_i}$

其中，$C_i$是权重矩阵，它与位置i的上下文有关。接着，要预测的特征向量，和词汇表中每个词的特征向量，两者间的相似度通过内积计算。该相似度接着进行指数化，归一化，从而获取下一个词的分布：

公式二： $P(w_n=w | w_{1:n-1})= \frac{exp(\hat{r}^T r_{w} + b_{w})}{\sum_{j} exp(\hat{r}^T r_{j} + b_{j})}$

这里的$b_w$是词w的偏置bias，它被用于捕获上下文独立的词频。

注意，LBL模型可以被解释成一种特殊的前馈神经网络，它只有一个线性隐层，以及一个softmax输出层。该网络的输入是上下文词汇的特征向量，而从隐层到输出层的权重矩阵，则可以简单通过特征向量矩阵R指定。该向量隐单元的激活，对应于下一个词的预测特征向量。不同于NPLM，LBL模型需要计算隐层激活，每次预测只计算一次，隐层不存在非线性。虽然LBL模型很简单，但表现很好，在相当大的数据集上，优于NPLM和n-gram模型。

4.层次化log-bilinear模型

我们的层次化语言模型基于该模型. 该模型的特点是，使用log-bilinear语言模型来计算每个节点的概率，并处理树中每个词的多次出现率。注意，使用多个词出现率的思想，由papar 6提出，但它并没有实现。

HLBL的第一部分是：一棵关于词作为叶子的二叉树。接着，我们假设词汇表中每个词对应一个叶子结点。接着，每个词可以通过从树顶点到叶子节点的路径唯一指定。该路径本身可以编码成一串二进制字符串d(每个节点会做二分决策)，$d_i=1$对应于：访问当前节点的左子节点。例如，字符串”10”表示的是：从顶点，到左子节点，然后到右子节点。这样，每个词可以被表示成一串二进制码。

HLBL模型的第二部分是：每个节点会做出二分决策的概率模型，在我们的case中，使用了一个LBL模型的改进版本。在HLBL模型中，和非层次化的LBL类似，上下文词汇表示成real-valued特征向量。树上的每个非叶子节点，也具有一个特征向量与它相关联，它用于区分词是在该节点的左子树还是在右子树。不同于上下文词汇，被预测的词，被表示成使用它们的二进制码。然而，这种表示相当灵活，因为编码中的每种二进制数字，相当于该节点做出的决策，它依赖于节点的特征向量。

在HLBL模型中，给定上下文，下一个词是w的概率，就是由该词编码指定的一串二分决策的概率。因为在一个节点上做出一个决策的概率，只取决于要预测的特征向量（由上下文决定），以及该节点的特征向量，我们可以将下一个词的概率表示成二分决策的概率乘积：

公式三：$P(w_{n}=w | w_{1:n-1}) = \prod P(d_{i} | q_i,w_{1:n-1})$

di是词汇w的第i位数字编码，qi是编码所对应路径上第i个节点的特征向量。每个决策的概率为：

公式四：$P(d_{i}=1 | q_{i},w_{1:n-1})= \delta (\hat{r}^T q_{i}+b_{i})$

其中，$\delta(x)$是logistic函数，而$\hat{r}$是使用公式一计算得到的要预测的特征向量，在该公式中的bi是该节点的偏置bias，它可以捕获当离开该节点到它的左子节点上的上下文独立的趋势。

D(w)表示词汇w所对应的一串编码集合。每个词允许多个编码，可以更好地预测词，具有多种含义或者多种使用模式。每个词使用多种编码，也可以使它更容易将多种不同的词层次结构，组合成单一的结构。这也反映了一个事实：没有单一的层次结构可以表示词之间的所有关系。

使用LBL模型（而非NPLM）来计算局部概率，允许我们避免计算隐层的非线性，这可以让我们的层次模型，比层次化NPLM模型更快作出预测。更重要的是，对于O(log N)个决策中的每一个，层次化NPLM都需要计算一次隐层激活，而HLBL模型只在每次预测时计算一次要预测的特征向量。然而，在LBL模型中，单个二分决策的概率计算的时间复杂性，仍然是特征向量维度D的二次方，这会使高维特征向量的计算开销很高昂。我们可以使时间复杂度与D是线性关系，通过将权重矩阵Ci限制为对角阵。注意，对于上下文size=1的情况，该限制条件不会减小模型表示的幂(power)，我们相信，这种损失(loss)，多于可以通过使用更复杂的树更快的训练时间的补偿。

HLBL模型可以通过最大化（带罚项的）log似然进行训练。因为下一个词的概率只依赖于上下文权重、上下文词汇的特征向量、以及从顶点到词汇所在叶子节点路径上的节点的特征向量，在每个训练case上，只有一小部分（log级别）的参数需要更新。

参考

• 1.A Scalable Hierarchical Distributed Language Model
• 2.An empirical study of smoothing techniques for language modeling
• 3.Class-based n-gram models of natural language
• 4.A neural probabilistic language model
• 5. Quick training of probabilistic neural nets by ´ importance sampling
• 6.Hierarchical probabilistic neural network language model
• 7.Three New Graphical Models for Statistical Language Modelling

介绍

word2vec中的logistic function计算使用的是快速算法，初始先算好值，然后在神经网络训练迭代中直接查表加快计算和训练速度。设计也还算精巧。

代码

在初始化时，有代码片段一，会对expTable做专门的初始化：

#define EXP_TABLE_SIZE 1000
#define MAX_EXP 6



// step 4: 分配logistic查表.
expTable = (real *)malloc((EXP_TABLE_SIZE + 1) * sizeof(real));
  
// 初始化: 预先计算好指数运算表. 
for (i = 0; i < EXP_TABLE_SIZE; i++) {
    expTable[i] = exp((i / (real)EXP_TABLE_SIZE * 2 - 1) * MAX_EXP); // Precompute the exp() table
    expTable[i] = expTable[i] / (expTable[i] + 1);                   // Precompute f(x) = x / (x + 1)
  }

expTable数据的大小为1000，存了1000个值用于查表。

而在模型训练阶段，代码片段二：

// 前向传播: f=∑ neu1*syn1
// Propagate hidden -> output
for (c = 0; c < layer1_size; c++) {
  f += neu1[c] * syn1[c + l2];
}

// 范围判断，查表
if (f <= -MAX_EXP) 
  continue;
else if (f >= MAX_EXP) 
  continue;
else 
  f = expTable[(int)((f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))];

将代码片段二代入到代码片段一，我们可以发现很神奇的现象：

将上式简单做个替换，把f替成z，整体输入看成i：

而再做一次运算，即知该表的值刚好与 logit函数 y = 1/(1+e^-z) 相同。

为什么要这么设计呢？

通过查表法，当然是为了加快指数运算。如果在每次迭代时，都去做指数运算，cpu开销蛮大。这样的设计，可以优化训练时间。

我来来看前前一段代码中，expTable[0 … EXP_TABLE_SIZE]中具体对应的值是哪些？这里，我提供了它的python实现：代码下载 ，绘制出实际的取值曲线（logistic regression的某一段取值），详见上面链接提供的代码：

另外，还有一点，就是这样的分割：EXP_TABLE_SIZE=1000， MAX_EXP=6？ 把数字代入，即知：

为什么要做这样的trick进行分解呢？上图展示的是从输入z的角度去理解。要真正理解为什么这样取，还要结合实际代码中Hierarchical softmax代码里的情况去理解。

里面的f输入范围在(-MAX_EXP, MAX_EXP), 即(-6, 6)。

第一阶段：(f + MAX_EXP)/MAX_EXP/2 * EXP_TABLE_SIZE 所做的操作：

• f + MAX_EXP: 平移，(0, 12)
• (f + MAX_EXP)/MAX_EXP: 压缩，(0,2)
• (f + MAX_EXP)/MAX_EXP/2: 归一化，(0,1)
• (f + MAX_EXP)/MAX_EXP/2 * EXP_TABLE_SIZE: 即将归一化后的f映射到[0,1000)个expTable的格子里，即是第一式的输入i

第二阶段：(i / (real)EXP_TABLE_SIZE * 2 - 1) * MAX_EXP 所做的操作：

• i / EXP_TABLE_SIZE: 将上面第一阶段的i，重新压缩到(0,1)
• i / (real)EXP_TABLE_SIZE * 2: 拉伸成(0,2)
• i / (real)EXP_TABLE_SIZE * 2 - 1: 平移为(-1,1)
• (i / (real)EXP_TABLE_SIZE * 2 - 1) * MAX_EXP: 放大为(-6,6)

ok，这时候，我们就会明白，为啥取(-6,6)了。因为:

• logit(6)=0.997527376843
• logit(-6)=0.00247262315663

这个范围内的值足够了。

但如果你细发现，两步合在一起，我们发现仿佛又回到了原点，于是可能开始会怀疑，为什么不干脆直接用f，省去中间这么多的变换，直接原封不动地输入expTable呢？

比如类似这样的实现：

def logit(x):
    e = math.exp(x)
    return e/(e+1)

我们可以推导下，如果让你设计一个需要1000个值的数组，存储logit函数值。假设数组名为expTable，即：

• 输入x为(0,1000)
• expTable[x]的输出值对应概率值(0,1)

由于logit(0)=0.5，常用的一个实现是：

从0开始刚好为0，输入(0,+inf)，输出(0,1)。如果想让x刚好对应索引，刚在原基础上除以1000即可。即：

再在原基础上做一下范围控制，就是我们上面的：

如果希望得到更精准的值，将EXP_TABLE_SIZE和MAX_EXP调大些即可以。