google在google+这个产品上提出了《Improving User Topic Interest Profiles by Behavior Factorization》，我们来看下具体实现：

1.介绍

2.相关工作

2.1 构建user profiles

对于许多用户而言，社交媒体上共享的信息是过饱和的。因此，主题兴趣画像(topic interest profiles)的构建是个性化推荐系统中很重要的一部分。我们的工作受关于利用行为信号的个性化研究的启发。

搜索引擎研究者已经利用user profiles来提供个性化搜索结果【9,11,4,30,35】。通常，user profiles会被表示成一个在高维空间中的向量，这些向量表示了在不同items上的用户偏好（比如：网页、电影、社交媒体posts），或者在不同空间上的用户偏好（例如：表示主题的关键词、或来自类目树taxonomy的主题类别）

2.1.1 MF & Embedding模型

推荐方法的一大类是CF，系统通常会使用一个user-by-item矩阵，每个条目表示用户在一个相应item上的评分。因此，在输入矩阵中的某一行表示：一个特征用户对items的偏好。关于一个用户在一个指定item上的未知偏好，可以使用矩阵补全（matrix completion）来进行推断（infer），研究者们已经使用MF方法取得了巨大进展。

在我们的paper中，我们并没有使用通过items（发表：posts）偏好来表示user profile的方法，我们更关注对user的主题兴趣(topical interests)进行推断，其中主题通过Google知识图谱的条目进行表示（比如：”basketball”、’video games’）。研究者已经使用MF来创建embedding模型，或者生成式模型（如：LDA）来构建user profiles[21]。MF以及生成式模型可以学到latent embedding空间，其中偏好可以通过user和item间的latent embedding factors的相似度进行计算。

比起item-based方法，topic-based方法在社交媒体中更加可扩展，其中实际items（posts）数目会很大。做为替代，通过计算在user topic兴趣和item(post)兴趣间的相似度，我们可以预测在一个item上的一个用户的兴趣。

2.2 社交媒体的个性化user profiles

正如在其它推荐问题上一样，社交媒体研究者通常将构建一个user profile看成是构建一个个性化推荐系统的首要任务。研究者在社交媒体上已经应用MF和生成式模型(LDA)来建模user-topic矩阵，并专门构建了user profiles[8,7,34,3,6,15,33,27]。例如，Guy等人基于content和item的偏好来构建user profiles，接着为社交媒体items（比如：书签和社交软件）来提供个性化推荐[8,7]。Chen等人在twitter上构建了user topic profiles并提供了会话的个性化推荐。User profile也被用于提供好友推荐[6]，社群推荐[33]，动作推荐（mentioning推荐[33], commenting[27]）。

对于一个user profile来说，用户偏好可以使用隐式反馈（比如：用户活动）进行infer[8]。作为对比，在传统推荐系统中，CF通常需要显式评分，这会带来用户的额外开销。例如，Hu等人提出了一个MF方法来利用稀疏数据的隐式反馈。在该思想基础上，Noel等人在MF上提出了一个新的目标函数，并考虑上在feature-based相似度、以及user-user信息。

2.3 上下文个性化

社交媒体平台提供了用户丰富的上下文信息，比如：用户在何时（when）对某用户发表（who’s post）的某主题（what topic）进行了web评论。许多最近研究讨论了如何利用这些丰富的上下文来学习更好的user profiles。Singh等人提出的CMF（协同矩阵因子分解），目标是使用上下文信息来在异构网络上提供推荐。与该工作比较接近的有：

• (a) Liu提出了 a social-aided context-aware recommender systems for books and movies. 会利用丰富的上下文信息来将user-item矩阵划分为多个矩阵[20]
• (b) Jamali等人提出了: a context-dependent matrix factorization model to create user profiles for recommendation in social network [14]。

除了矩阵分解技术外，研究者提出了context-aware generative models来在Twitter上帮助创建user profiles和隐语义模型[25,32,36]。例如，Zhang等人使用生成模型提出了一个two-step framework来首先发现不同的主题域，接着使用MF方法在每个域上提供推荐[37]。不同用户可能对不同领域感兴趣，与我们工作相关，但在用户行为上有些区别。我们主要关注：每个用户的主题兴趣是如何通过不同类型的行为进行划分的。

研究者们已经使用内存来构建和提升user profiles。Li等人提出了一种 transfer learning方法来对两个领域的两个向量，使用相互间的信息进行因子分解[18]。Hu等人提出了一个三元因子分解（triadic-factorization-based）方法来对user-item-domain的tensor进行因子分解，来提供跨领域的个性化推荐。

2.4 行为因子分解

“如果你将知觉（perception）看成是一种联系（contact）和洽谈(communion)的方式，那么，支配感知就是支配联系，限制和管理感知就是限制和管理联系。”—Erving Goffman, The Presentation of Self in Everyday Lif.

最近工作表明，多种上下文可以提升user profiles的质量。在我们的paper中，展示了社交媒体用户具有不同类型的行为与不同主题进行交互，我们应使用行为类型看成是一种重要的上下文。我们也会为不同行为类型构建多个user profiles，接着在不同行为独立的推荐中，灵活使用这些不同的profiles。例如：推荐阅读(read)的内容，推荐分享(reshare)的内容。等

社会学家表明，人们在他们的每一天生活中，会呈现不同的画面给其它人；他们每天的对话会以不同主题展开，具有不同的听众。社交媒体的出现吸引了社会学家的兴趣，他们在网络社群上研究了该现象。例如，社会学家建立了这样的理论：由于用户对于在公开社交媒体上的准确受众（exact audiences）没有清晰看法，他们的行为具有模糊上下文边界[22]。然而，由于不同类型的行为，比如：发表（posting）和评论（commenting），会影响非常不同的受众，我们以下的分析建议，用户在社交媒体上仍会展示出不同的“身份（’identities’）”，以及对不同的主题展示不同类型的行为。通过定量研究，Zhao等人指出：用户体验社交媒体平台（比如：Facebook），与现实中的多种身份相似。据我们所知，我们的paper是首次提出：用户在一个社交媒体上利用不同的在线表示。

3. google+行为分析

我们分析了在google+上的匿名用户在线行为。我们首先抽取了在发表（posts）上的主题条目作为我们的特征，来为每个post构建特征向量。对于每个用户在posts上的行为动作，我们会聚合post对应的feature vectors来为每个用户-行为组合(user-behavior combination)构建一个entity vector。接着，我们对这些user-behavior entity vectors表示的不同的主题兴趣进行粗粒度的measure。我们展示了在这些向量间存在很大的不同，这启发了我们利用行为因子分解来建模不同的行为类型。

3.1 数据集描述

使用了2014 五月的google+用户公开行为来进行分析。我们在所有公开发现上分析了所有用户行为，每条记录被表示为一个tuple：(u,b,E)，其中一个用户u（具有一个匿名id）使用行为b来参与一个包含了实体集合E的post。有4种类型的行为：发表（post），分享（reshare）、评论（comment）、+1.

我们会使用google知识图谱的实体形式（它包含的概念有：computer algorithms, landmarks, celebrities, cities, or movies.）来抽取更高级的语义概念，而非使用更低级向量（比如：word tokens）。它当前包含了5亿实体，在主题覆盖上提供了广度与深度。

我们基于标准的实体识别方法（利用实体间的共现先验，实体间的相关度似然，实体在文本中位置，接着最终对实体主题进行最终排序），使用一个实体抽取器。

对于给定的一个post，我们使用相应的知识图谱实体作为特征来表示它的主题。因此，在input tuple(u,b,E)中每个E是一个关于知识图谱实体的集合。例如，如果一个用户\(u_1\)创建了一个关于宠物狗图片的post，与该行为对应的是：(\(u_1\), CreatePost, {“Dog”, “Pet”, …})。如果另一个用户\(u_2\)在一个关于Xbox Minecraft的youtube视频post上进行了评论，该行为对应于该tuple：(\(u_2\), Comment, {“Minecraft”, “Xbox”, …})。

3.2 衡量行为间的不同

对于每个user，我们会使用一个特定类型行为来从他交互的posts中聚合实体。最后，对于每个用户，我们对应于4种不同类型的行类会获得4个主题实体集合。

我们接着使用Jaccard相似度来衡量集合间的不同。

表1: Average Jaccard similarity between pairs of behavior types

在我们计算了每个用户不同行为的jaccard相似得分后，我们接着在所有用户上对分数进行平均。我们过滤掉了：小于10个实体的用户认为是不活跃。表1展示了平均jaccard相似度的结果。我们可以看到，任意两种行为类型间的平均jaccard系统很低。以comment和+1行为为例，在这两种行为间只有9%的主题重合。我们也衡量了用户的发布(publishing)和消费(cosuming)行为上的不同。我们会将用户comment和+1行为的实体组合成一个consuming实体集合，我们将create post和reshare行为的实体组合成一个publishing实体集合。平均jaccard index为0.122. 关于jaccard得分的低重合率表明：用户在不同行为上差异很大。

3.3 讨论

结果分析表明，对于每个用户，他通常在每个行为上具有不同的主题兴趣。也就是说，她通常会在create posts上的主题与comments上的主题会很不同。结果表明，常见的无指定行为（non-behavior-specific）的user profiles可能会在那些强调不同行为类型的应用上执行效果差。

内容推荐者通常会对用户要消费的内容进行定向预测，它可能会受行为（comment和+1）的影响要更好。在其它上下文中，我们会替代预测：用户会创建什么主题的posts。因此，通过为每种行为类型创建主题偏好，特定行为的user profile在不同的推荐上下文上具有更好的效果。

总之，用户在社交媒体上的不同行为包含了重要的上下文信息，它可以帮助我们提升用户个性化profiles上的效果。我们展示了，用户在G+上不同的行为类型会极大影响不同的主题兴趣，使用单独的行为类型构建不同的profiles允许我们为不同的行为上下文定制内容推荐系统。

4.问题定义

4.1 输入行为信号

我们不会为每个用户构建单个profile，相反的，我们提出了为一个用户构建多个profiles来表示它的不同行为类型。特别的，这里我们将社交媒体上的posts行为作为输入，输出一个主题兴趣向量集合来表示每个用户的不同类型的profiles。

给定一个用户集合\(U\)，不同的行为类型\(B\)，以及一个可以表示社交媒体内容\(E\)的特征集合，输入数据可以被表示成：

\[I = \lbrace t_i = (u_i, b_i, E_i), i=1, ..., N \rbrace\]

其中\(u_i \in U, b_i \in B, E_i \subset E\)。

• 每个\(t_i\)表示一个用户在社交媒体内容的某个特定片段上的动作。例如，一个\(t_i\)可以是：创建一个post，或者对某个post进行comment。
• \(E_i\)是该post的特征集合。

这里由于我们正构建user topic profiles，我们使用Google知识图谱的实体作为我们的特征集。然而，总体上，\(E\)可以是任意low-level（例如：words）或high-level的特征（例如：其它实体，或地理位置特征）。

4.2 User profiles

我们将user profiles定义成在特征空间E中的向量集合：

\[B = \lbrace P_u = \lbrace V_{u_B} \rbrace \rbrace\]

其中，\(u \in U, B \subset B\)，

• \(P_u\)是用户u的user profile，
• \(V_{u_B}\)是用户u在对应于她的行为类型B上的偏好向量。

\(P_u\)可以被认为是一个user tensor。

B即可以是单个行为类型（例如：创建一个post），或是一个不同行为类型的组合（例如：创建一个post和reshare一个post组合）。准确表述为：

\[V_{u_B} = ( p_{u_B}^{e_1}, p_{u_B}^{e_2}, ..., p_{u_B}^{e_k} ), e_j \in E\]

其中，对于j=1,…,k，\(p_{u_B}^{e_j}\)是用户u的行为类型 B在特征\(e_j\)上的偏好。

5.我们的方法

图1: 生成矩阵和因子分解框架

我们引入了行为因子分解法来为个性化推荐构建user profiles，它包含了三个steps，如图1和2所示。

• step 1: 给定第4节中定义的input user action tuples \(I\)，我们首先构建不同行为类型的矩阵。这对应于图1中的左部分。
• step 2: 我们对step 1中生成的矩阵进行因子分解来学到latent embedding space。这对应于图1中的右部分。
• step 3: 最后，我们使用学到的latent space来对兴趣主题做预测来构建user profiles。这会为每个用户u创建profiles \(P_u = \lbrace V_{u_B} \rbrace\)。这对应于图2.

图2: 使用latent embedding space构建user profiles

我们会轮流做介绍。

5.1 step 1: 为不同行为类型构建矩阵

在常见的矩阵因子分解技术中，输入的user-item矩阵R被表示成一个\(N \times K\)的矩阵，其中N表示user的数目，K表示items的数目。R被分解成两个矩阵的乘积，矩阵X (\(N \times L\))，矩阵Y（\(K \times L\)）。换句话说，R中的行向量和列向量被映射到一个L维的latent embedding space中。有了这个学到的隐向量，对于在user-item矩阵中任意观察到的行向量，学到的embedding空间可以被用于帮助完成特定的行向量来补全一个用户在items上的估计偏好。

由于我们正构建user-topic-based profiles，我们使用users在主题的兴趣（\(N \times K\) user-topic matrix）作为输入，而非将users在items上的兴趣（\(N \times K\)的user-item matrix）作为输入。

另外，除了使用一个\(N \times K\)矩阵作为输入之外，我们构建和因子分解得到多个矩阵，包括：

• (a) 传统的\(N \times K\)矩阵，被称为Behavior Non-specific User-topic Matrix(BNUM)
• (b) Single Behavior-Specific User-topic Matrix(SBSUM)
• (c) Combined Behavior-Specific User-topic Matrix(CBSUM)

5.1.1 BNUM (Behavior Non-specific User-topic Matrix)

这里，每个条目表示一个用户在特定主题上的隐式兴趣。给定输入用户tuples \(I=\lbrace t_i = (u_i, b_i, E_i), i=1, 2, ... \rbrace\)，我们首先引入涉及用户u的tuples \(I_u\)：

\[I_u = \lbrace t_j = (u_j, b_j, E_j) \rbrace, t_j \in I \wedge u_j = u\]

接着，我们为每个user和topic pair生成观察值：

\[r_{ui} = r(I_u, i)\]

也就是说，我们首先抽取所有涉及用户u的tuples \(I_u\)，在给定用户u涉及主题i的tuples下，使用函数r来计算隐式兴趣。该函数有许多可能的形式，对于不同行为可以训练不同的权重。我们使用以下的等式做为baseline来计算隐式兴趣：

\[r_{ui} = \frac{(\sum\limits_{I_u} \sum\limits_{e \in E_j} \sigma_i(e)) + 1}{(\sum\limits_{I_u} \| E_j \|) + (\|\cup_{I_u} E_j\|)}\]

…(1)

如果i=e，\(\sigma_i(e)\)为1; 否则为0. 也就是说用户u对主题i的隐式兴趣，可以通过i在所有用户u行为上的出现次数，除以所有items的出现总和来计算。我们会使用additive smoothing来对该值进行平滑。

5.1.2 SBSUM (Single Behavior-Specific User-topic Matrix SBSUM)

SBSUM和CBSUM将行为类型单独划分来生成独立的user-topic矩阵。给定一个行为类型的特征集合\(B \subset B\)，我们想构建矩阵\(R_B = \lbrace r_{ui}^B \rbrace\)，其中每个条目表示从B中行为类型得到的隐式兴趣。

我们使用与等式(1)的相同方法，但增加了限制来过滤不在B中的行为类型：

\[r_{ui}^B = \frac{(\sum\limits_{I_u \wedge b_j \in B} \sum\limits_{e \in E_j} \sigma_i(e)) + 1}{ \sum\limits_{I_u \wedge b_j \in B} \| E_j \| ) + (\|\cup_{I_u \wedge b_j \in B} E_j \|)}\]

…(2)

对于每个B，使用该等式，我们可以构建一个矩阵，它使用B中的行为类型来表示用户观察隐式反馈，可以被设置成单个行为类型，或是多个行为类型集合。因此，基于B选择，我们可以构建两个类型的特定行为user-topic矩阵(BSUM)：SBSUM, CBSUM。

首先，我们为每个行为类型构建了一个user-topic矩阵，比如：creating post，resharing，commenting或+1. 每个矩阵的条目是观察值\(r_{ui}^B\)，它通过等式(2)计算，其中B是单个行为。给定\(B = \lbrace b_1, b_2, ..., b_M \rbrace\)为所有行为类型集合，我们生成以下M个SBSUM:

\[\begin{cases} R_{b_1} = \lbrace r_{ui}^B \rbrace, B=\lbrace b_1,b_1 \in \mathscr{B} \rbrace \\ R_{b_2} = \lbrace r_{ui}^B \rbrace, B=\lbrace b_2,b_2 \in \mathscr{B} \rbrace \\ ... \\ R_{b_M} = \lbrace r_{ui}^B \rbrace, B=\lbrace b_M,b_M \in \mathscr{B} \rbrace \end{cases}\]

…(3)

5.1.3 CBSUM（Combined Behavior Specific User-topic Matrix）

在构建SBSUM时，我们创建了M个矩阵，每个表示单个行为类型。然而，我们也希望捕获多种行为类型组合的主题兴趣。例如，在G+中，creating post和resharing posts会生成内容并广播给所有followers，这两种行为类型可以组合在一起来表示用户的发表（publication）。

同时，commenting和+1两者表示用户对post的消费行为。将两者组合在一起可以表示关于用户消费（consumption）的主题兴趣。因此，给定行为类型集合，每个集合是B \(\lbrace B_1, B_2, ..., B_p \rbrace\)的一个子集，我们构建了P个矩阵，每一个均表示用户的组合行为：

\[\begin{cases} R_{B_1} = \lbrace r_{ui}^B \rbrace, B=\lbrace B_1,B_1 \in \mathscr{B} \rbrace \\ R_{B_2} = \lbrace r_{ui}^B \rbrace, B=\lbrace B_2,B_2 \in \mathscr{B} \rbrace \\ ... \\ R_{B_M} = \lbrace r_{ui}^B \rbrace, B=\lbrace b_M,b_M \in \mathscr{B} \rbrace \end{cases}\]

…(4)

5.2 step 2: 学习latent embedding space

这里我们引入了一个矩阵分解（MF）技术来构建用户的主题画像(topic profile)作为baseline方法。另外，我们引入了我们提出的方法，它将baseline算法扩展成行为因子分解。

5.2.1 baseline: MF

在构建BNUM后，我们会学习一个latent embedding space，它可以被用于补全observed user-topic matrix来获得预测的user-topic偏好。在推荐研究中，在学术界和工业界有许多方法尝试改进MF技术。这里我们使用hu[13]提出的因子分解技术。

采用[13]有一个非常特别的原因。在社交媒体平台上，对于大多数用户来说，隐式兴趣信号更容易获取。然而，许多推荐算法并没有考虑显式兴趣 vs. 隐式兴趣信号间的潜在不同。在user-item矩阵上有效的所有其它MF方法，可以被应用到我们的框架中，来使用行为因子分解（behavior factorization）构建user profiles。注意：在后续讨论中，user-topic矩阵中的”topic”与user-item中的item相似。

给定从\(r_{ui}\)的隐式兴趣中观察到的user-item矩阵，Hu[13]将观察集划分成两个变量：偏好\(p_{ui}\)、置信度\(c_{ui}\)。这里\(p_{ui}\)是一个二值变量，它表示用户u是否对item i感兴趣：

\[p_{ui} = \begin{cases} 1 , r_{ui}>0 \\ 0 , r_{ui}=0 \end{cases}\]

置信度\(c_{ui}\)表示对偏好\(p_{ui}\)的置信等级。它表示你对兴趣值有多肯定。它可以通过以下方式进行计算：\(c_{ui} = 1 + \alpha r_{ui}\)。

接着，该算法会学到一个latent embedding space，它会将每个user u和item i映射到该空间上（对应于\(x_u\)和\(y_i\)）。为了学习该空间，算法会尝试解决以下的最优化等式：

\[\min\limits_{x_*,y_*} \sum\limits_{ui} c_{ui} (p_{ui} - x_u^T y_i) ^ 2 + \lambda( \sum\limits_{u} \| x_u \|^2 + \sum\limits_i \| y_i \|^2)\]

…(5)

结果\(x_u\)和\(y_i\)可以被用于补全user-item矩阵，它会估计一个user会喜欢一个item有多喜欢。[13]提出的算法对于隐式feedback/interest datasets工作良好。

在这一点上，我们使用等式(1)来构建user-topic矩阵，采用MF来学习一个latent embedding space。再者，我们可以通过估计用户u在所有主题上的偏好来建模任意用户u的兴趣。对于没有出现在原始user-topic matrix（用于训练该embedding space）中的任意新用户，我们仍能通过使用学到的topic embedding vectors \(y_i\)来将它们映射到该embedding space中。我们将在第5.3节中讨论。

5.2.2 行为因子分解模型（BF）

不同于上述介绍的矩阵因子分解模型，我们希望将用户不同的行为类型进行划分，并为每个用户对于不同的行为生成主题偏好。因此，我们不再使用对单个user-topic matrix进行因子分解，而是会对step 1生成的多个user-topic矩阵（BNUM, SBSUM, CBSUM）进行因子分解。

有一些在context-aware矩阵分解、张量分解等技术（Liu[20]）上进行的早期探索，会创建多个矩阵并同时学习一个latent space。然而，这些技术不能直接用在我们的行为因子分解问题上，因为我们正构建多个user-topic矩阵，它具有相同的列(column)/主题(topic)空间，但具有不同的行(rows)/用户(users)。他们构建的矩阵对于不同的context具有不同的items，相反的我们会使用一个隐式建模方法，也会考虑上行为上下文间的关系，比如：发布行为组合和消费行为组合。

图1展示了行为因子分解（BF）方法与baseline模型对比的区别。在step 1从用户行为构建矩阵时，不再仅构建BNUM，我们也会构建两类矩阵：SBSUM和CBSUM。

在step 2中，我们将所有生成的矩阵因子分解成相同的latent embedding space。我们会学习一个latent embedding space，并将对应每个特定的行为类型的每个用户和每个item映射到该空间中。在每个矩阵中的每个条目是对该用户行为的隐式兴趣值，因此，我们可以以如下方式扩展baseline模型。

这里\(p_{ui}^B\)和\(c_{ui}^B\)表示每个矩阵的偏好的置信度。给定所有特定的行为类型，我们使用等式(3)和(4)的\(\Gamma = \lbrace B_1, B_2, ...\rbrace\)，我们通过优化如下的等式来学习embedding space:

\[min_{x_*,y_*} \sum\limits_{B \in \Gamma} \sum\limits_{u,i} c_{ui}^B (p_{ui}^B - x_u^{B^T} y_i)^2 + \lambda (\sum\limits_{B \in \Gamma} \sum\limits_{u} \| x_u^B \|^2 + \sum\limits_{i} \|y_i\|^2)\]

….(6)

通过写出在\(\Gamma\)上的求和，我们使用一个与原始等式(5)相似解来求解该最优化问题，并为user-behavior和topics学习embedding space。

对比原始的user-topic矩阵，通过我们方法学到的embedding space的可能在对语义相似度的衡量上会更好，因为从之前分析（第3节），我们知道在user-topic矩阵上的观察值是从不同行为上的多种不同兴趣的混合。将这些信号相隔离可以产生一个更清晰的topic model。一个最近的paper：《how to learn generative graphical models such as LDA in social media》【31】。在该paper中，他们探索了如何将文档聚合成语料，并表示一个特定的context。由于生成式图模型和矩阵分解都是尝式从数据中学习latent space，该意图可以在两种方法上均可采用。我们的假设是，在user-behavior级别上构建矩阵，而非在user级别上；这可以帮忙我们清晰地标识跨主题的语义联合，不会增加太多的稀疏性。

5.3 step 3: 构建user profiles

最终，我们介绍了如何使用学到的latent embedding spaces来构建user profiles。如图2所示，我们介绍两种方法：

• i) 从profile矩阵的input row vectors构建direct profile
• ii) 通过一个回归模型学到一个权重集合，合并不同的direct profile进行构建weighted profile

对于每个user u，我们会构建\(p_u = \lbrace V_{u_B} \rbrace\)。每个\(V_{u_B}\)是一个关于用户u在特定行为类型B上的主题偏好向量。我们会构建三种类型的user profiles，对应于三种类型的input矩阵：

• BNUP:
• SBSUP:
• CBSUP:

5.3.1 DPB(Direct Profile Building)

我们会使用一个用户的embedding factors(例如：在学到的latent embedding space中对于user u的向量\(x_u\))来生成他的完整的user profiles: \(V_{u_B} \in P_u\)。在DPB中，input是矩阵\(R_B\)中的observed row vectors（对于在\(\Gamma\)中的任意B来说），我们会为每个B构建user profile。

给定一个用户u和B，我们可以获取embedding factor \(x_u^B\)，接着使用该embedding factor和topic embedding factors \(Y = \lbrace y_i \rbrace\)，通过计算点乘：\(x_u^{B^T} Y\)来生成用户u行为B的偏好列表。接着对于每个用户u，她的output user profile可以被表示成:

\[P_u = \lbrace V_{u_B} = x_u^{B^T} Y \brace, B \in \Gamma\]

…(7)

特别的，给定任意B（它是\(B\)的一个子集），我们使用以下的等式来生成用户的SBSUP和CBSUP：

\[V_{u_B} = ( p_{u_B}^{e_1}, p_{u_B}^{e_2}, ..., p_{u_B}^{e_K}), p_{u_B}^{e_i} = x_u^{B^T} y_1\]

…(8)

其中，\(x_u^B\)是用户u在行为类型B上的embedding factor。

总之，在DPB中，不同的profiles通过不同的input row vectors来生成，BNUM的row vector会生成BNUP，SBSUM的row vector会生成SBSUP，CBSUM的row vectors会生成CBSUP。例如，为了为每个用户构建BNUP，我们设置\(B = \mathcal{B}\)，并使用所有他的已观察主题兴趣值（observed topic interest value）来生成他在该embedding space中的embedding factor \(x_u\)。接着为每个topic i计算\(x_uy_i\)，来得到他的BNUP。

\[V_u = (p_u^{e_1}, p_u^{e_2}, ..., p_u^{e_K}), p_u^{e_i} = x_u^T y_i\]

…(9)

对于不在学到的embedding model中的新用户，我们仍可以使用等式(2)来生成他的row input vectors，接着将该向量投影到一个embedding factor上。

5.3.2 WPB (Weighted Profile Building)

DPB会为一个用户生成一个behavior profile（如果该用户在过往有行为）。通过将用户的行为类型相分隔，我们可以使用DPB来为用户u的行为B生成profile，但这需要用户u在行为B上具有非零的观察值。对于那些在B上没有行为的用户，\(V_{u_B}\)会为空，这意味着一个没有该行为类型动作的user，不会有一个user profile。这在某种程度上对应于在推荐系统中的冷启动问题。

然而，我们可以通过使用在其它行为类型的user profiles来解决该问题。我们可以使用加权求和（weighted sum）将他们组合来生成一个在主题上的组合偏好向量。这对应于一个transfer learning问题。

这里，为了为用户u的行为类型B生成偏好向量\(V_{u_B}\)，而非直接使用等式(7)的结果，我们可以使用等式(10)为在\(\Gamma\)中的所有行为类型所生成的所有偏好向量进行加权求和（weighted sum）：

\[V_{u_B} = \sum\limits_{B_t \in \Gamma} W_{B_t} x_u^{B_t^T} Y\]

…(10)

\(\Gamma\)中不同行为类型的权重是模型级别的参数，例如：我们会为整个数据集的每个\(B_t \in \Gamma\)学到一个权重。因此，这些权重可以使用一个监督学习方法来从在我们的数据集中具有多种行为类型的所有用户上学到。因此，对于那些在过程历史记录中没有\(B_t\)的用户，我们仍可以为他们构建profiles。

在我们的实现中，我们可以使用线性回归和SGD来学习这些参数。因此，WPB可以生成BNUP、SBSUP、CBSUP，具体取决于应用。在大多数内容推荐应用中，常见的信息消费行为（consumption behaviors）非常重要，我们使用用户已观察到消费行为（observed）来学习权重来构建consumption profile。

6.评估

在之前章节，我们提出了行为因子分解法，它可以学习一个强大的latent space，并为多种行为类型构建user profiles。在该实验中，我们希望验证两个假设：

• H1: 从我们的行为因子分解方法中学到的latent embedding模型在构建user profiles比baseline MF模型要更好
• H2: 通过从多种行为类型中组合偏好向量，我们可以提升在特定行为类型上的user profiles的覆盖度(coverage)

在乘余章节，我们首先描述了如何设置实验，例如：我们使用了什么datasets，如何评估输出的user profiles的效果。接着我们比较了行为因子模型与baseline模型。我们也比较了在构建user profiles上的我们提出的两个方法，结果表明：通过组合行为类型，可以提升高质量的用户覆盖度。

6.1 实验设置

为了评估构建user profiles的效果，我们检查了在预测用户主题兴趣的不同方法。我们将dataset划分为两部分：training set和testing set。我们使用trainingset来训练和构建user profiles，然后在testing set上比较不同模型的效果。

6.1.1 Dataset

我们的dataset包含了在2014年 5月和6月的公开的Google+ 用户行为。第3.1节描述了dataset的生成。我们会同时使用5月的数据来训练baseline和我们的MF模型。我们随机从6月的行为数据中进行20%抽样来学习5.3.2节WPB的权重。使用乘余80%行为数据来评估不同方法的效果。

输入矩阵：在我们的dataset上，我们包含了所有公开5月和6月的posts数据。有4种类型关于posts的行为数据。我们构建不同的user-behavior-topic矩阵：

• SBSUM
• Publication CBSUM
• Consumption CBSUM
• BNUM

6.1.2 评估指标

对于一个给定的行为类型\(B_t\)，我们构建的user profile是一个关于在主题\(V_{u_{B_t}}\)上的偏好向量。在该vector上的值会估计：用户u是否会喜欢在行为\(B_t\)上的每个topic。这可以使用\(R_u^{B_t} = \lbrace r_{ui}^{B_t}, i \in E \rbrace\)在testing set上使用等式(2)计算的隐式兴趣进行评估。

尽管在\(V_{u_{B_t}}\)的实际值，和\(R_u^{B_t}\)不需要是相同的，\(B_t\)的一个好的user profile，\(V_{u_{B_t}}\)主题顺序进排序，必须与我们在testing set中观察的相似。

为了比较这两个vectors的顺序，我们会将\(V_{u_{B_t}}\)和\(R_{u}^{B_t}\)转换成两个关于在E中主题的排序列表：\(L_{method} = (e_{r_1}, e_{r_2}, ..., e_{r_N})\)是由profile building方法生成的关于top N主题的排序列表，\(L_{observed} = (e_{o_1}, e_{o_2}, ..., e_{o_N'})\)是所有观察到主题的排序列表。我们会使用如下指标进行评估：

• Recall@N: \(L_{method}\)的top N的主题有多少出现在\(L_{observed}\)
• NDCG@N:
• AP@N:

7.讨论

7.1 潜在的应用

有许多应用可以使用我们方法构建的user profiles。由于我们将用户行为（还有不同的items集合：比如：posts, communities, users）映射到相同的embedding模型上，用户行为和items间的相似度可以用于为推荐生成排序列表。对比常用的user profiles（它不会分隔用户行为），我们的方法不仅会考虑users和items间的内容相似性，也会考虑不同推荐任务的上下文。例如，consumption profile可以用于为一个正在阅读post的用户推荐相关的posts，publication profile可以用于在一个用户创建一个post后为他推荐新朋友。

7.2 局限性和未来改进

提出的行为因子分解框架确实可以提升用户兴趣画像的效果，然而仍有局限性。其中之一是，我们的框架依赖于：用户不同的行为类型天然能反映用户的不同兴趣。在构建社交媒体的用户兴趣画像（比如G+）能运行良好，但不能泛化到其它领域上（比如：不同行为类型不能反映不同的用户兴趣）。

另外，结果表明我们的方法不能在用户非常稀疏、或者目标行为类型(尝试预测)没有数据的情况下。一个原因是，这些用户可能比其它用户具有更低的活跃度。另一个原因是，我们的方法会最优化多个矩阵，它们可能会对相同的用户丢失跨不同行为类型的相关性。为了解决这个问题，我们对使用tensor factorization技术（比如：PARAFAC）在行为矩阵上很感兴趣。我们的方法可以认为是一个tensor factorization上unfolding-based方法的扩展。

另外，我们想直接部署该框架到现实的推荐系统上，并通过在线实验来评估。

参考

https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/43807.pdf

Fayyad等在paper[1]提到过一种连续值离散化的方法：MDPLP。下面简单来看下：

1.介绍

分类学习算法通常要使用启发法（heuristics）来在多个属性值和类的组合间的可能关系空间上进行搜索。其中有一种这样的启发法（heuristic），它被使用在数据集中的分类上的选择局部最小化信息熵（比如ID3算法、C4､CART等）

机器学习中的属性可以是类别型的，也可以是连续型（数值型）。上述提到的属性选择过程假设所有的属性都是类别型的。连续型的属性在选择之前需要进行离散化（discretized），通过通过将属性的range范围进行划分成subrange范围。总体上，离散化是一个简单的逻辑条件，将数据划分成至少两个子集。

本文主要关注连续型属性的离散化。首先来看下二元离散化（binary discretization）。接着来看多区间离散化（multi-interval discretization）。

2.二元离散化

连续值属性通常在决策树生成时通过将它的值范围离散化成两个区间。对于连续型属性A，阈值为T， $ A \leq T $被分配到左分枝，$ A \gt T $被分配到右分枝。我们将该阈值T称为分割点（cut point）。该方法被用于ID3算法以及它的变种CART算法中的GID3。它可以被用于任何分类树算法，或者用来处理将连续型属性划分成二个区间的规则。尽管这里我们将它应用于离散化，在决策树生成的topdown的特定上下文也有使用。

假设在一个节点（样本集S具有N个样本）上对一个属性进行分枝。对于每个连续型属性A，我们在值的范围上选择最好的（“best”）分割点$ T_A $。样本首先通过属性A的值升序排列，在排完序序列中每个后继样本对（example pair）间的中点会作为一个潜在的分割点进行评估。这样，对于每个连续值属性，会发生N-1次评估（假设样本没有相同的属性值）。对于候选分割点T的每次评估，数据都会划分成两个集合，结果分区的分类熵（class entropy）会被计算。回忆一下，该离散化过程也会在决策树中的每个节点被执行。

样本集S通过T划分成两个子集：S1和S2 。假设存在K个类：$ C_1, …, C_k $，让$ P(C_i, S) $是S中含有类别$C_i$的样本比例。那么子集S的分类熵（class entropy）被定义成：

\[Ent(S) = - \sum_{i=1}^{k} P(C_i,S) log(P(C_i,S))\]

其中的log基数取2 。 Ent(S)用来衡量在S中的指定的分类信息量，单位为：bits。在集合S被划分成S1和S2后，为了评估生成的分类熵，我们采用它们生成的分类熵的加权平均：

定义1：对于一个样本集S，一个属性A，一个分割值T：假设$ S_1 \in S $是在样本S中的子集，它的A属性值$\leq T$，并且满足$ S_2 = S - S_1 $。分区的分类信息熵通过T索引，E(A,T;S)被定义成：

\[E(A,T;S) = \frac{|S_1|}{|S|} Ent(S_1) + \frac{|S_2|}{|S|} Ent(S_2)\]

…(2)

A的二分离散化通过选择分割点$T_A$来决定，其中$E(A, T_A; S)$是所有候选分割点中的最小值。

2.1 分割点选择的讨论

选择标准（selection criterion）的主要问题之一是：它的开销相当昂贵。尽管它是多项式复杂度，它为每个属性必须评估N-1次（假设有N个不同值的样本）。因为机器学习问题通常被设计成很大的训练量，N通常很大。当对一个类别型（离散化）属性进行时，该标准（criterion）只需要对r个分区进行单次评估即可，其中r为类别的数目。通常$ r « N$。确实，像ID3这样的算法在运行连续型属性时确实会慢许多。

其它缺点是：该算法具有一个天生的缺陷，当超过两个分类时，会生成”坏（bad）”的分割点。该缺点基于一个事实：该算法尝试最小化侯选二元划分集合的加权平均熵（如方程1所示）。分割点可能因此将一个分类的样本以最小化平均熵的方式进行分割。图1展示了这种情况。分割点并不会落在边界B1或B2上的其中之一，则是会落在两边的平均熵最小的点上。

这不是我们所期望的，因为它没必要将相同分类的样本分隔开，产生更大（但质量更低）的树。

然而，这些缺点不会被证明是对的。下面的理论1会展示，不管有多少分类，不管如何离散化，分割点将总是发生在两个类的边界上（见定义2, 它会对边界点有一个精准的说明）。这确实是该启发法（heuristic）的一个期待的特性，因为它展示了该启发法（heuristic）是“表现良好的（well-behaved）”。它告诉我们该启发法（heuristic）将从不选择一个在结果上（目的论：teleological）被认为是“坏”的分割（cut）。另外，该结果将帮助我们在不改变该功能的情况下提升算法的效果。

2.2 分割点总是在边界上

我们展示了属性A的值$ T_A $会最小化平均分类熵$E(A,T_A;S)$: 对于一个训练集S，必须总是在排序后样本序列不同分类的两个样本间的值。假设A(e)表示样本$ e \in S$的A值。

定义2：范围A中的值T是一个边界点，因此存在两个样本：$ e_1, e_2 \in S$具有不同的分类。比如：$A(e_1) < T < A(e_2) $，不存在着这样的样本$e’ \in S$，使得：$A(e_1) < A(e’) < A(e_2) $。

理论1：如果T能最小化E(A,T;S)，那边T就是一个边界点

证明：相当长，忽略。见paper[5]

推论1 用于ID3的该算法，可用于为连续型属性发现一个二分划分，将总是在排好序的属性样本对一个边界点划分数据。

证明：跟据理论1和定义。

推论1的第一个含义是，它可用于支持在离散化时最小化熵。我们使用信息熵的启发法（heuristic），因为我们知道，它控制一些衡量离散化需要的属性。然而，本身并不能排除不希望的情况，比如，图1中的情况。推论声明，“明显坏（obviously bad）”的分割从不会被该启发法（heuristic）所喜欢。该结果可进一步支持在离散化中使用该启发法（heuristic），因为它告诉我们，该启发法（heuristic）从目的论（teleological）的角度是表现良好的。

另外，推论1可以被用于在完全不需要更改效果的情况下增加算法的效果。通过对属性A的值进行排序之后，该算法只需要检查边界点b，而非所有的N-1个侯选。注意：$ k-1 \leq b \leq N-1 $。因为常通k « N，我们会期望节省很大的计算开销。我们演示了对ID3算法的所要评估的潜在分割点的数目上有极大的加速。ID3将连续值属性划分成两个区间。算法会检查多个区间，使用该过程的一个泛化版本（比如：下一节中要讲的一个）来达到更高的加速。算法会搜索规则，而非决策树，在离散化时会花费更多的开销。评估过程的计算加速只是推论1的一个附带效果。它的语义重要性是本文关注的，因为它证明了我们的泛化相同的算法，来生成多个区间，而非两个。

3.泛化该算法

推论1也提供了对扩展该算法的支持，在单个离散化过程中来抽取多个区间，而非两个。该动机是获取更好（“better”）的树。

训练集会做一次排序，接着算法会使用递归，总是选择最好的分割点。所使用的一个原则是：避免对一个给定区间做更进一步的二元划分。事实上，只会考虑这样的边界点：让自顶向下（top-down）的区间的得到更可行（因为该算法从不会在top上提交一个”bad”分割点），并且能减小计算开销。

为了合理地定义这样的一个算法，我们需要用公式来表示这个原则（criterion），以决定对一个给定样本做限制划分。该criterion需要理论支持。期望的测试将在后续被用于验证该理由是否合理。

从树生成的角度上看，为什么多区间（multiple range）的派生版本比二元区间（binary range）有更大的优点呢？通常，“感兴趣（interesting）”的范围可以是在属性值范围内的一个内部区间。为了得到这样的一个区间，单次做二元区间划分（”binary-interval-at-a-time”）的方法将导致不必要的、并会对样本做出超出感兴趣区间范围的过多划分。例如，假设，对于在[0,40]的属性值A，子区间 $ 12 < A \leq 20$是我们感兴趣的。假设A的范围离散化成：$ (-\infty,12), [12,20), [20,25), [25,\infty) $。给定一个算法，比如GID3,它能过滤出不相关的属性值，原则上可以获得如图2(a)所示的决策树。属性选择算法决定着只有2/4的区间是相关的。在区间外的样本会被分组到图中label=S的子集。

为了选择如图2(b)中生成的决策树两个区间范围，可以只使用一个二分区间离散化算法。注意，集S没必要划分成两个子集S1和S2 。对于第一棵树，该算法有机会使用一些其它的属性对S进行划分。该选项在第二种情况下不再使用，进一步的属性选择基于更小的子集：S1和S2. 必要的，这会导至相同的排序问题，会造成不相关值问题（irrelevant valus problem）。关于GID3如何处理该问题，以及如何只有一个子集的值被分支超出了本文的范围。

3.1 分割还是不分割？

给定集合S和一个潜在的二元划分$ \pi_{T}$，它表示在集合S上对属性A的分割值T，我们需要决定是否接受这次划分。该问题天然可以公式化成一个二分决策问题：接受或者拒绝$\pi_T$。假设HT为假设函数，其中$\pi_T$决定着是否接受。也就是说，HT是分类器，它会测试A的值，而非T，接着会对样本进行分类：根据在E中的样本小于T的值，A值<T。相似的，让NT来表示表示零假设（null hypothesis）：该假设会导致$\pi_T$被拒绝。NT会根据E中的类别来对所有样本进行分类，不需要检查A值。因为接受或拒绝都只是可能的动作，其中之一必然是正确的；另一个不正确。当然，没有其它办法来直接决定哪个是正确的。

假设$d_A$表示决定着接受划分$ \pi_T$，$d_R$表示拒绝。该情况中可能的决策集合是$ D= \lbrace d_A, d_R \rbrace $，我们具有待解决的一个二分决策问题。如果我们分配了一个cost给错误的决策，那么与一个决策规则（在$ {d_A, d_R} $间进行选择）相关的期望cost如下：

\[B = c_{11} Prob(d_A \wedge HT) + c_{22} Prob (d_R \wedge NT) + c_{12} Prob(d_A \wedge NT) + c_{21} Prob (d_R \wedge HT)\]

其中$c_{11}$和$c_{12}$表示做出正确选择的costs，而$c_{12}$和$c_{21}$表示做出错误决策的costs。这是期望贝叶斯风险（expected Bayes risk），决策规则被用于选择 $ \lbrace d_A, d_R \rbrace $的其中之一。贝叶斯决策原则（Bayes decision criterion），会调用选择决策规则来最小化期望的cost。

由于我们知道，分配给$c_{12}$和$ c_{21} $是什么值，我们会对均匀error cost分配做重排序。如果$ c_{11} = c_{22} = 0$和 $ c_{12} = c_{21} = 1$，那么最小化Bayes risk会减小一个决策规则PEC（Probalility-of-Error Criterion），它会最小化做出错误决策的概率。接着，它会通过一个简单的派生来展示Bayes决策原则来减小采用的决策规则，给定数据集S，选择假设HT，$ Prob(HT | S)$是计算假设的最大量。我们将该决策原则适用成”贝叶斯决策策略（Bayesian Decision Strategy）”。该策略有时也被称为MAP原则（maximum a posteriori），等价于PEC。

对于我们的决策问题，Bayesian decision strategy会选择$d \in D$的决策，它对应于在数据集S上具有最大概率的hypothesis：这样，如果$ Prob(HT | S) > Prob (NT |S)$，那么我们选$ d_A$。如果我们有一个方法来决策着上述两个要解决问题的概率：简单地选择hypothesis，它具有更高的概率，Bayesian决策策略会保障这是最好的策略。不幸的是，没有简单的方法来直接计算这样的概率。然而，我们应采用这样的方法：它将允许我们直接估计哪个概率更大。

3.2 MDLP(最小描述长度原则)

一个对象的最小描述长度（minimum description）被定义成所需的最小的位数，来唯一指定对象脱离于通用的所有对象。

我们会展示该决策问题，给定一个固定的样本集合，我们使用MDLP来猜测带有更高概率的hypothesis。MDLP是一个通用的原则，它的目的是，对自然界中天然的偏差进行编码，朝着更简单的理论来解释数据的相同部分。MDLP被Rissanen引入，之后被其它人使用。定义如下：

定义3：给定一个假设集合，以及一个数据集S，MDLP会调用假设HT来：$ MLength(HT) + MLength(S |HT) $是在假设集上的最小值。MLength(HT)表示对HT编码的最小可能长度，而 $ MLength(S |HT) $是对给定hypothesis编码的最小编码长度。

为了方便，我们假设长度的单位是：bits。数据的编码可以被认为是对数据点进行编码，它们是对于hypothesis HT来说“异常点（exceptions）”。如果HT能完全拟合数据，那么后一项将为0.

MDLP原则不必要要求与之前讨论的决策原则不同。它可以轻易地展示MDLP和Bayesian risk minimization strategy在理论上是相互相关的。由于篇幅原因，我们忽略了派生版本，它包含着可以包含对数据集S的hypothesis H所需要指定的bits数：$ -log_2 (Prob(H|S)) $，使用Bayes’ rule。最终获得的表达式等价于MDLP。这可以看成是采用MDLP的动机。

基于最早的争论，如果我们具有一种方法来发现真实的hypotheses的最小编码长度，那么采用MDLP来选择一个完整hypotheses的集合会导致使用最大MAP的hypothesis。接着，它等价于PEC决策原则。这意味着，选中的hypothesis将会最小化做出错误选择决策的概率。然而，在物理世界中，我们不会访问概率分布。因而，MDLP被用于对cost的估计，来在hypotheses间做比较。

3.3 应用MDLP：编码问题

现在，一个问题是编码问题（coding problem）。在我们的情况下，决策问题相当简单。完整的hypotheses包含了两个元素：{HT, NT}。我们应采用Quinlan和Rivest的公式，他们在属性选择上使用MDLP来尝试生成紧凑的决策树。在我们的情况下，该问题相当简单。

使用该公式，该问题需要解决的问题是通信问题。目标是通信一个方法（分类器），它可以允许接收器（receiver）来决定在数据集中的样本分类label。假设一个发送器（sender）具有整个训练数据样本集。而接收器具有没有该分类label的样本。sender只需要将合理的分类labeling传送给receiver。sender必须选择最短描述来指定该分类。

对Null Theory NT进行编码：在NT的情况下，sender必须简单地传递在S中的样本的类别。sender发送了N条消息，每个都是一个被编码过的类别label（其中N=$ | S | $）。为了编码在S中的样本的类别，我们必须使用一个最优化算法（比如：Huffman coding）来生成编码来优化平均编码长度。因为我们必须传递在集合S中每个样本的类别，将平均编码长度l乘以N给出了总的cost。另外，需要传递“code book”来用于解码类别。传递的code book的包含了每个类别对应的code word。因而，如果存在着K个分类，code book的长度可以通过(k * l)进行预估。注意，K是一个常数，不能随着N增长，因此，code book的cost是一个小的常数开销。

对划分HT进行编码：选中的分割点会对样本分区，必须由sender根据每两个子集中的分类编码来指定。指定分割点的开销为$log_2(N-1)$ bits，因为我们需要指定序列（分割点在之间落的地方）中N-1个样本的其中之一。

分类器HT对应于二分划分，$ \pi_T $，将集合S划分成子集：S1和S2。其中Sender必须传递分割点的一个说明书，根据S1中的类别序列，根据S2中的类别。再者，我们感兴趣的是，对S1和S2中的类别编码使最小化平均长度，如同在S中的类别编码所做的。其中$ l_1 $和$ l_2 $是对应于S1和S2各自的最小化平均编码长度（单位：bits）。传递HT的cost随着HT的数据一起：

\(log_2(N-1) + | S_1 | \cdot l_1 + | S_2 | \cdot l_2\) (bits)

我们也需要为S1和S2的类别编码各自传递code books。不同于传递S的情况(k个类别)，该情况我们必须通知receiver，哪个类别的子集会在两个子集S1和S2的其一中被表示，接着传递各自的code books。因为我们知道我们的划分是非平凡解（non-trivial）的，例如：$ S_1 \neq S_2 \neq \emptyset $，我们知道S1可能具有$2^k-1$个可能的k个类别的子集。使用一个长度派生版本，它可以被表示成：

\[G_k = [ \sum_{k_1=1}^{k-1} (C_{k_1}^{k}) 2^{k_1}] + 2^k - 1 = 3^k - 2\]

是可能的划分数目，超出我们需要指定的。由于我们需要$ log_2(G_k) $ bits。注意：$ log_2(G_k) < 2 log_2(2^k-1) < 2k$.

##

• 1.Multi-Interval Discretization of Continuous-Valued. Attributes for Classification Learning

介绍

《BPR: Bayesian Personalized Ranking from Implicit Feedback》讨论了个性化排序学习模型的一个通用方法：Bayesian Personalized Ranking。主要贡献有：

• 1.描述了通用的优化方法：BPR-OPT，它来自于对最优个性化排序的最大后验估计。我们展示了BPR-OPT在AUC上的分析。
• 2.对于最大化BPR-OPT，我们提出了通用学习算法LearnBPR，它基于SGD，在训练过程使用bootstrap sampling。我们展示了该算法会优于最优化BPR-OPT时的SGD。
• 3.我们展示了如何应用learnBPR到两个state-of-art推荐模型中
• 4.我们的实验经验上展示了个性化排序任务，使用BPR的模型效果要好于其它学习算法

2.相关工作

推荐系统中最流行的模型是kNN CF。传统上，kNN的相似矩阵通过启发法（heuristics）进行计算（例如：Pearson相关度），但在最近的工作中，相似矩阵可以看成是模型参数，可以学到。最近，矩阵分解（MF）在推荐系统中非常流行，可以使用隐式和显式反馈。在最近工作中，SVD也被证明是可以学习特征矩阵。通过SVD学习得到的MF模型，被证明是很容易overfitting。因而提出了正则化学习方法。对于item的预测，Hu等人提出了一个带case weights的正则的最小二乘优化(WR-MF)。case weights可以被用于减小负样本的影响。Hofmann提出了一个概率隐语义模型来进行item推荐。Schmidt-Thieme将该问题转成一个multi-class问题，并使用一个二分类集合来求解它。即使在item预测上的上述所有工作。。。

本文中，我们主要关注模型参数的离线学习。将学习方法扩展到在线学习情况——例如：添加一个新用户，它的历史增加从0到1，2，… feedback事件——对于MF的排序预测已经被学到。相同的fold-in策略可以被用于BPR。

。。。

3.个性化排序（Personalized Ranking）

个性化排序的任务，会为一个用户提供一个items排序列表。这也被称为item推荐。一个示例是，在线电商希望推荐一个个性化的items排序列表，用户会从中购买。在本paper中，我们会研究以下情形：ranking必须从用户的隐式行为（例如：过去的购买）进行infer得到。隐式反馈系统只提供正例数据（正样本）。未被观察到(non-observed)的user-item pairs（例如：一个用户没有购买一个item）会是一个真实负反馈（用户对购买该item不敢兴趣）以及缺失值（用户可能会在将来购买该item）的混合。

3.1 公式化

图1: 在左侧，为已观察到的数据S。直接从S中学习是不可行的，因为只有正反馈被观察到。通常负例数据通过使用0值填充矩阵来生成

假设U是所有users的集合，I是所有items的集合。在我们的场景下，隐式反馈\(S \subseteq U \times I\)（见图1左侧）。类似这种反馈方式有：电商中的购买行为，视频观看 或者 网页上的点击。推荐系统的任务是提供给用户一个个性化总排序(personlaized total ranking): \(>_u \subset I^2\)，其中\(>_u\)必须满足一个总顺序属性：

\[\begin{aligned} & \forall i,j \in I: i \neq j \Rightarrow i >_u j \vee j >_u i \ \ (totality) \\ & \forall i,j \in I: i >_u j \wedge j >_u i \Rightarrow i = j \ \ (antisymmetry) \\ & \forall i,j \in I: i >_u j \wedge j >_u k \Rightarrow i >_u k \ \ (transitivity) \end{aligned}\]

• totallity: 总体性
• antisymmetry: 反对称性
• transitivity: 传递性

出于便利，我们也定义了：

\[I_u^+ := {i \in I: (u,i) \in S} \\ U_i^+ := {u \in U: (u,i) \in S}\]

3.2 问题分析

前面提到，在隐式反馈系统中只有正例(positive classes)被观察到。剩余数据其实是实际负例(negative)与缺失值（missing value）的一个混合。对于应付缺失值问题，最常见的方法是：忽略所有缺失值。通常典型的机器学习模型不能学习任何东西，因为他们两者间不能进行区分这两者(负例和缺失值)。

对于item推荐，常用的方法是，对一个item预测一个个性化分\(\hat{x}_{ui}\)，它可以影响用户对该item的偏好。接着，该items会根据该分值进行排序。对于item推荐的机器学习方法，通常会从S中创建训练数据：给定：

• 正例：\((u, i) \in S\) pairs
• 负例：所有在\((U \times I) \backslash S\)中的其它组合

如图1所示。接着，模型会拟合该数据。这意味着模型的最优化是为在S中的元素预测value是1, 其余为0。该方法的问题是，在模型中将来进行排序的所有元素（\(U \times I \backslash S\)）在训练期间都会作为负反馈被表示给机器学习算法。这意味着：如果一个模型具有足够表现力（它可以精准拟合训练数据），它根本不能进行排序，因为它的预测值基本为全0(很稀疏，大部分为0, 全预测对）。为什么这样的机器学习方法可以预测rankings？唯一原因是，有策略阻止overfitting，比如：正则化。

我们使用一种不同的方法：通过使用item pairs作为训练数据，然后为正确(correctly)的ranking item进行最优化（而非对单个items进行打分），因为这比使用负例来替代缺失值要更好。从S中，我们可以尝试为每个user parts（\(>_u\)）进行重构。如果一个item i被user u观看过，（例如：\((u,i) \in S\)）——那么，我们假设该user喜欢该item要胜过其它未观察到的items。

图2: 在左侧，已观察到的数据S。我们的方法会在一个items pair间创建特定用户的pairwise偏好\(i >_u j\)。在右侧，加号(+)表示一个用户偏爱item i胜过item j；减号(-)表示他偏爱j胜过i。

例如，在图2中，user \(u_1\)已经观看过item \(i_2\)，但没看过item \(i_1\)，因此我们假设，该用户喜欢\(i_2\)要胜过\(i_1\)：\(i_2 >_u i_1\)。对于被一个用户同时观看过的两个items，我们不能推断更偏好哪个。对于用户未观看过的两个items来说（比如：对于user \(u_1\), item \(i_1\)和\(i_4\)），相类似，也不能推断哪个更好。为了将这种现象公式化，我们创建训练数据 \(D_S : U \times I \times I\)：

\[D_S := \lbrace (u, i, j) | i \in I_u^+ \wedge j \in I \backslash I_u^+ \rbrace\]

\((u,i,j) \in D_S\)的语义是，user \(u\)被假设成：喜欢i，胜过j。由于\(>_u\)是非对称的，负例会被隐式对待。

我们的方法有两个优点：

• 1.我们的训练数据同时包含了正负例pairs以及缺失值。介于两个未观察到的items间的缺失值是将来必须排序的item pairs。这意味着，从pairwise的角度看，训练数据\(D_S\)和测试数据是不相交的。
• 2.为排序的实际目标函数创建训练数据，例如：观察到\(>_u\)的子集\(D_S\)被用成训练数据。

4.BPR

在这部分，我们为解决个性化排序任务生成了一种通用方法。对于个性化排序，它包含了通用优化准则：BPR-OPT，它源自对该问题的Bayesian分析，会使用似然函数来为\(p(i >_u j \mid \Theta)\)以及模型参数\(p(\Theta)\)的先验概率。我们展示了排序统计AUC的分析。对于遵循BPR-OPT的学习模型，我们提出了算法learnBPR。最后，我们会展示BPR-OPT和LearnBPR是如何应用到两个state-of-art的推荐算法（MF和adaptive kNN）上。比起常用的训练方法，使用BPR来优化这些模型可以生成更好的rankings。

4.1 BPR优化原则

为所有items \(i \in I\)寻找正确的个性化排序的Bayesian公式，是为了最大化以下后验概率，其中\(\Theta\)表示一个指定模型类别(比如：MF)的参数向量。贝叶斯公式为：

\[P(\Theta | >_u) \propto p(>_u | \Theta) p(\Theta)\]

这里，\(>_u\)是对于user u希望但隐含的偏好结构。所有用户都假设行为间相互独立。我们也假设：对于一个指定用户，每个items \((i,j)\) pair的顺序，与每一个其它pair相互独立。因而，对于所有用户\(u \in U\)，以上的特定用户的似然函数\(p(>_u \mid \Theta)\)可以首先被重写成：单个密度(densities)和第二个的乘积的组合。

\[\prod\limits_{u \in U} p(>_u | \Theta) = \prod\limits_{(u,i,j) \in U \times I \times I} p(i >_u j | \Theta)^{\delta((u,i,j) \in D_S)} \cdot(1-p(i >_u j | \Theta))^{\delta((u,j,i) \notin D_S}\]

其中\(\delta\)是指示函数：

\[\delta(b) := \begin{cases} 1 & \text{if b is true,} \\ 0 & \text{else} \end{cases}\]

归因于合理的pairwise ordering scheme的总体(totality)和非对称性(antisymmetry)，上述公式可以简化为：

\[\prod\limits_{u \in U} p(>_u | \Theta) = \prod\limits_{(u,i,j) \in D_S} p(i >_u j | \Theta)\]

到目前为止，通常不会保证获得一个个性化的总顺序。为了得到它，必须满足之前提到过的合理性质（totality、antisymmetry、transitivity）。为了这样做，我们定义了一个用户喜欢item i胜过item j的独立概率：

\[p(i >_u j | \Theta) = \sigma( \hat{x}_{uij} (\Theta))\]

其中：

• \(\sigma\)是logistic sigmoid：\(\sigma(x) := \frac{1}{1+e^{-x}}\)
• \(\hat{x}_{uij}(\Theta)\)是一个特定的关于模型参数向量\(\Theta\)的real-valued函数，它会捕获user u、item i、item j间的特殊关系。

换句话说，我们的通用框架会将建模在u、i、j间的关系的任务表示到一个底层模型类（比如：MF或adaptive kNN）上，它们负责估计\(\hat{x}_{uij}(\Theta)\)。因而，统计方式建模一个个性化总顺序\(>_u\)变得可行。出于便利，后续章节我们会跳过介绍来自\(\hat{x}_{xij}\)的参数\(\Theta\)。

至今，我们已经讨论了似然函数。为了补全个性化排序任务的Bayesian建模方法，我们引入了一个通用的先验密度\(p(\Theta)\)，它是一个零均值、协方差矩阵\(\sum_{\Theta}\)的正态分布。

\[p(\Theta) \sim N(0, \sum_{\Theta})\]

下面，为了减小未知超参数的数目，我们设置\(\sum_{\Theta} = \lambda_{\Theta} I\)。现在，我们可以将最大后验估计进行公式化，来生成我们为个性化排序BPR-OPT的通用最优化准则：

\[\begin{aligned} BPR-OPT &:= ln \ p(\Theta | >_u) \\ & = ln \ p(>_u | \Theta) p(\Theta) \\ & = ln \ \prod\limits_{(u,i,j) \in D_S} \sigma(\hat{x}_{uij}) p(\Theta) \\ & = \sum\limits_{(u,i,j) \in D_S} ln \ \sigma(\hat{x}_{uij}) + ln \ p(\Theta) \\ & = \sum\limits_{(u,i,j) \in D_S} ln \ \sigma(\hat{x}_{uij}) - \lambda_{\Theta} \|\Theta \|^2 \end{aligned}\]

其中\(\lambda_{\Theta}\)是模型特定的正则化参数。

4.1.1 AUC最优化分析

有了Bayesian Personalized Ranking(BPR) scheme的公式，很容易理解BPR和AUC间的分析。每个用户的AUC通常被定义为：

\[AUC(u) := \frac{1}{ | I_u^+ | |I \backslash I_u^+ |} \sum\limits_{i \in I_u^+} \sum\limits_{j \in | I \backslash I_u^+|} \sigma(\hat{x}_{uij} > 0)\]

这里，平均AUC是：

\[AUC := \frac{1}{|U|} \sum\limits_{u \in U} AUC(u)\]

…(1)

其中, \(z_u\)是归一化常数：

\[z_u = \frac{1} { | U | | I_u^+ | | I \backslash I_u^+|}\]

在(1)和BPR-OPT间的分析是很明显的。除了归一化常数\(z_u\)外，他们只在loss function上有区别。AUC会使用不可微(non-differentiable)的loss \(\sigma(x>0)\)，它等同于Heaviside function:

\[\sigma(x > 0) = H(x) := begin{cases} 1, & \text{ x > 0 } \\ 0, & \text{ else } end{cases}\]

作为替代，我们会使用可微loss \(ln \sigma(x)\)。惯例上，当为AUC进行最优化时【3】，替代不可微的Heaviside函数。通常，替代选择是启发式的（heuristic），并且有一个与\(\sigma\)相类似的相似形状函数（similarly shaped function）（见图3）。在本paper中，受MLE的启发，我们已经已经生成了替代法 \(ln \sigma(x)\)。

图3: 用于最优化AUC的loss function。不可微的Heaviside H(x)通常使用sigmoid \(\sigma(x)\)来近似。我们的MLE导数建议使用\(ln \sigma(x)\)来替代

4.2 BPR learning算法

在最后一节，我们已经为个性化排序生成了一个最优化原则（optimization criterion）。由于criterion函数是可微的，基于梯度下降(gradient descent)的算法是一个用于最大化的很明智的选择。但正如我们所见，对于我们的问题，标准梯度下降并不适合。为了解决该问题，我们提出了LearnBPR，一个基于SGD的、在训练的三元组上进行bootstrap sampling的算法（见图4）。

图4:基于SGD的boostrapping BRP最优化模型。学习率\(\alpha\)，正则参数\(\lambda_{\Theta}\)

首先，BPR-OPT的梯度会各自按模型参数求导：

\[\begin{aligned} \frac{\partial {BPR-OPT}}{\partial \Theta} & = \sum_{(u,i,j) \in D_S} \frac{\partial}{\partial \Theta} ln \sigma(\hat{x}_{uij}) - \lambda_{\Theta} \frac{\partial}{\partial \Theta} \| \Theta \|^2 \\ & \propto \sum\limits_{(u,i,j) \in D_S} \frac{-e^{-\hat{x}_{uij}}}{1+e^{-\hat{x}_{uij}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{uij} - \lambda_{\Theta} \Theta \end{aligned}\]

对于梯度下降，两种常用算法是full GD或SGD。在第一种方法中，每一step，会在所有训练数据上进行计算，接着模型参数会使用learning rate \(\alpha\)进行更新：

\[\theta \leftarrow \Theta - \alpha \frac{\partial BPR-OPT} {\partial \Theta}\]

总之，该方法会在“正确”方向上产生一个下降，但收敛很慢。因此，我们在\(D_S\)上有\(O(\mid S \mid \mid I \mid)\)条训练三元组(triples)，在每个update step上计算full gradient是不可行的。再者，对于使用full DG进行BPR-OPT的最优化、以及在训练pairs上的数据倾斜，会导致很差的收敛。想象下，一个item i，通常是positive的。接着我们在loss中的\(\hat{x}_{uij}\)上有许多项(terms)，因为对于许多用户u、item i，会与所有负例items j进行对比（占主导的分类）。因而，模型参数的梯度依赖于i是否在梯度上占据主导地位。这意味着必须选择非常小的learning rates。第二，由于梯度的不同，正则化很难。

另一个流行的方法是SGD。在这种情况下，对于每个triple \((u,i,j) \in D_S\)，只会执行一个更新。

\[\Theta \leftarrow \Theta + \alpha ( \frac{e^{-\hat{x}_{uij}}}{1+e^{\hat{x}_{uij}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{uij} + \lambda_{\Theta} \Theta)\]

总之，对于我们的倾斜问题，这是一个好方法。但training pairs遍历的顺序是很严格的。一个常用的方法是，以item-wise或user-wise的方式遍历数据，会产生很差的收敛，因为在相同的user-item pair上有许多连续的更新——例如：对于一个user-item pair (u,i)，有许多j 满足\((u,i,j) \in D_S\)。

为了解决这个问题，我们建议使用一个SGD算法来随机选择triples（非均匀分布）。该方法在连续更新steps很小时，会选择相同的user-item组合。我们建议使用一个有放回的bootstrap sampling方法，因为在任意step上都可能执行stopping。放弃通过该数据进行full cycles的思想，在我们的case中特别有用，因为样本数目会非常大，为了收敛通常一个full cycle的一部分就足够了。在我们的评估中，我们选择了单个steps的数目，它线性依赖于观察到的正反馈S的数目。

图5展示了一个常用的user-wise SGD、与我们的带bootstrapping的LearnBPR的比较。该模型是16维的BPR-MF。正如你看到的，LearnBPR比user-wise GD收敛更快。

图5: 常见的user-wise SGD与我们的基于bootstrapp sampling的learnBPR算法收敛率的经验比较

4.3 使用BPR来学习模型

对于item推荐，下面我们描述了两个state-of-the-art的模型，以及如何使用我们提出的BPR方法来学习它们。我们已经选择两个不同的模型：MF[5,12]和learned kNN[8]。这两个模型都尝试建模一个用户在一个item上的隐式偏好。它们的预测是对于每个user-item-pair (u,l)的一个实数 \(\hat{x}_{ul}\)。

由于在我们的optimization中，我们有triples \((u,i,j) \in D_S\)，我们首先对estimator \(\hat{x}_{uij}\)进行解耦，并将它定义为：

\[\hat{x}_{uij} := \hat{x}_{ui} - \hat{x}_{uj}\]

现在，我们可以应用任意标准的CF模型来预测\(\hat{x}_{ul}\)。

需要重点注意的是，尽管在其它工作中我们使用相同的模型，我们会使用不同的准则(criterion)对它们进行最优化。这会产生一个更好的排序，因为我们的准则对于排序任务是最优的。我们的准则不会尝试将单个predictor \(\hat{x}_{ul}\)看成是单个数字，但作为替换，尝试对两个预测的差\(\hat{x}_{ui} - \hat{x}_{uj}\)进行分类。

4.3.1 MF

预测\(\hat{x}_{ui}\)的问题可以看成是估计一个矩阵：\(X: U \times I\)。对目标矩阵X使用MF，可以通过两个低秩矩阵\(W: \mid U \mid \times k\)和\(H: \mid I \mid \times k\):

\[\hat{X} := W H^t\]

其中k是维度/秩 (dimensionality/rank)的近似。在W中的每行 \(w_u\)可以被看成是描述一个user u的一个feature vector，相似的，H中的每行\(h_i\)描述了一个item i。因而，预测公式可以被写为：

\[\hat{x}_{ui} = \langle w_u, h_i \rangle = \sum\limits_{f=1}^{k} w_{uf} \cdot h_{if}\]

除了点乘\(\langle \cdot, \cdot \rangle\)外，总之类似于[11]的任意kernel都可以被使用。对于MF的模型参数是\(\Theta = (W, H)\)。该模型参数可以被看成是隐变量（latent variables），会建模一个用户的未观察到的品味(taste)、以及一个item未观察到的属性(properties)。

通常，通过SVD根据最小二乘获得的X的的最佳近似\(\hat{X}\)。对于机器学习任务，SVD会overfits，因此提出了许多其它的MF方法，包含正则化最小二乘最优化，非负因子分解，最大间隔因子分解，等。

对于排序任务，例如：估计一个用户是否偏爱一个item胜过其它item，一个更好的方法是根据BPR-OPT准则来最优化。这可以通过使用提出的LearnBPR来达到。正如之前所述，对于使用LearnBPR的最优化，每个模型参数\(\theta\)的梯度\(\hat{x}_{uij}\)是已知的。对于MF模型，导数为：

\[\frac{\partial}{\partial \theta} \hat{x}_{uij} = \begin{cases} (h_{if} - h_{jf}) & \text{if $\theta = w_{uf}$ } \\ w_{uf} & \text{if $\theta = h_{if}$} \\ -w_{uf} & \text{if $\theta = h_{jf}$} \\ 0 & \text{else} \end{cases}\]

另外，我们使用三个正则化常数：

• \(\lambda_W\)对应用户特征W;

item features H有两个正则常数：

• \(\lambda_{H^+}\)被用于只在\(h_{if}\)上用于positive更新；
• \(\lambda_{H^-}\)用于在\(h_{jf}\)上的negative更新

4.3.2 Adaptive KNN

最近邻方法在CF中很流行。它依赖items间（item-based）或users间（user-based）的相似度衡量。以下我们描述了item-based方法，通常他们会提供更好的结果，但user-based方法也类似。该思想是：为一个user u预测一个item i，它依赖于item i与该用户过往看过的其它所有items(例如：\(I_u^+\))间的相似度。通常，\(I_u^+\)中只有k个最相似的items会被看成是K个最近邻。如果items间的相似度被选中，你可以比较在\(I_u^+\)上的所有items。对于item-based KNN的item预测：

\[\hat{x}_{ui} = \sum\limits_{l \in I_u^+ \wedge l \neq i} c_{il}\]

其中：\(C: I \times I\)是对称的（item-correlation / item-similarity）矩阵。这里，kNN的模型参数为\(\Theta = C\)。

最常用的选择C的方法是，通过应用一个启发式相似度来衡量，比如：cosine向量相似度：

\[c_{i,j}^{cosine} := \frac{|U_i^+ \cap U_j^+|} {\sqrt{ |U_i^+ | \cdot |U_j^+|}}\]

一个更好的策略是，通过学习来将相似度 C适配该问题。这可以通过直接使用C作为参数，或者如果items数很大，你可以学习一个C的因子分解\(H H^t\)，其中：\(H: I \times k\)。下面，在我们的评估中，我们会使用第一种方法来直接学习C，无需因子分解。

为了对kNN模型最优化来进行ranking，我们使用BPR-OPT准则，并使用LearnBPR算法。为了应用该算法，\(\hat{x_{uij}}\)对应模型参数C的梯度为：

\[\frac{\partial}{\partial \Theta} \hat{x}_{uij} = \begin{cases} +1 & \text{if $\theta \in \lbrace c_{il}, c_{li} \rbrace \wedge l \in I_u^+ \wedge l \neq i,$} \\ -1 & \text{if $\theta \in \lbrace c_{jl}, c_{lj} \rbrace \wedge l \in I_u^+ \wedge l \neq j,$} \\ 0 & \text{else} \end{cases}\]

我们有两个正则常数，\(\lambda_+\)用于在\(c_{il}\)上更新，\(\lambda_{-}\)用于在\(c_{jl}\)上更新。

5.与其它方法的关系

• WR-MF: Weighted Regularized Matrix Factorization
• MMMF: Maximum Margin Matrix Factorization

略

6.评估

在我们的评估中，我们比较了BPR学习与其它学习方法。我们选择两个流行的模型：MF和kNN。MF模型的效果要好于其它模型（比如：Bayesian模型URP、PLSA等 ）。在我们的评估中，MF模型使用三种不同方法学到：SVD-MF, WR-MF, BPR-MF。对于kNN，我们比较了Cosine-kNN，以及一个使用BPR方法优化的模型(BPR-kNN)。另外，我们也上报了baseline（most-polular）的结果，它会按用户独立的方式来加权每个item：比如：\(\hat{x}_{ui}^{most-pop} := \mid U_i^+ \mid\)。另外，我们给出了对于任意非个性化排序方法在AUC (\(np_{max}\))的理论上界。

6.1 datasets

我们使用两个来自不同应用的数据集。

• Rossmann dataset：来自在线电商。它包含了1w用户在4k items上的购买历史。总共有426612个购买记录。该任务是预测用户希望在下次购买的一个个性化items列表.
• Netflix DVD rental dataset: 该数据集包含了用户行为的打分，其中一个用户对电影提供了1-5星的显式评分。如果我们希望以隐式反馈的方式求解，我们可以移除rating。该任务是预测用户是否可能对一个电影进行评分。我们会为用户提供一个最可能打分的个性化排序列表。对于Netflix我们创建了一个subsample: 1w用户，5000 items，包含了565738个rating动作。我们会做子抽样：每个用户至少包含10个items，每个item至少有10个用户。

6.2 评估方法

我们使用留一法（leave-one-out）来进行评估，训练集\(S_{train}\)，测试集\(S_{test}\)。该模型会在\(S_{train}\)上学习，并在\(S_{test}\)上通过平均AUC统计进行评估：

\[AUC = \frac{1}{|U|} \sum\limits_{u} \frac{1}{|E(u)|} \sum\limits_{(i,j) \in E(u)} \sigma(\hat{x}_{ui} > \hat{x}_{uj}\]

…(2)

其中，每个用户u评估的pairs为：

\[E(u) := \lbrace (i,j) | (u,i) \in S_{test} \wedge (u,j) \notin (S_{test} \cup S_{train})rbrace\]

…(2)

AUC越高表示效果越好。随机猜测法的AUC是0.5,最好为1。

我们会重复10次实验，每次抽取新的train/test splits。超参数通过grid search进行最优化。

6.3 结果

图6

参考

https://arxiv.org/pdf/1205.2618.pdf

本文主要是结合Jinhui Yuan等人在LightLDA的paper的理解。对于Gibbs sampling可以参见PRML第11章。

1.介绍

主题模型(TM: topic models)使用广泛，许多公司开发了大规模的LDA工具包实现，以适应海量的语料。互联网级别的语料更复杂，为捕获长尾的语义信息（否则将丢失这些主题信息），需要大容量（high-capacity）的主题参数空间，有成千上万的主题数和很大的词汇量。

为应对大规模数据及模型可扩展性，LightLDA实现了一种分布式数据并行策略的LDA（将文档通过workers进行分割，共享所有主题参数）。当然，你也可以使用SparseLDA和AliasLDA的sampler进行算法加速，来进一步降低运行时长。使用1000台机器，就可以使用LDA模型从10亿级别的文档中infer出具有100亿的参数。这个结果是惊人的，但开销很大：例如，一个1000台机器的集群将花费上百万美金（这还不算电费和维护费用）。另外，你可以租用云平台，这样每台机器每小时也要>=1美元，每个月的开销也要>=70w美元。这对于大多说研究者来说是不可行的。

LightLDA提出了一种花费更小的方法来解决这种大规模ML问题，在10台机器级别就能解决该问题。在三个级别上处理该问题：

• 1.以data-paralled 和 model-paralled方式实现分布式LDA inference：数据和模型会被分区（partitioned），接着跨机器进行流传输（streamed），以便在集群内更有效地利用内存和网络资源。
• 2.开发了一个Metropolis-Hastings sampler，对每个word/token，允许O(1)的采样时间，这可以在时间上产生一个高收敛率，可以击败当前state-of-art的samplers。
• 3.使用了一种不同的数据结构，利用海量语料，可以展示高频头部词，也可以展示低频长尾词，以不同的方式存储，有效利用资源，没有性能损失。

使用开源的Petuun framework，我们生成了一种即快又省内存(compute-and memory eficient)的分布式LDA实现：LightLDA。对于上亿的文档（2000亿tokens），它有1万亿的模型参数（1m的主题 x 1m的词汇量），只需要8台标准机器(与云平台常用计算实例配置类似)，在180小时内，或者24台机器60小时。对于参数的size，我们的结果是：比文本数据集上大两阶。对于数据的size（data size）至少相当或者比其它大1阶。对于吞吐量（throughput），我们的系统可以在每20-core机器上，每小时采样5000w文档（平均长度为200 tokens）。而PLDA+每机器每小时使用collasped Gibbs sampler只能达到1200个文档；YahooLDA在每8-core机器每小时200w文档。

#

LDA实现分布variational- 和 sampling-based inference算法。LightLDA只关注sampling-based的方法。因为它可以产生非常稀疏的更新，使它们很适合设置很大的主题数K。

最新的large-scale LDA实现需要使用很大的工业级的集群，使用成百上千的CPU core。这些实现需要大集群的原因是：它们使用了SparseLDA inference算法或者 更慢的原始collapsed Gibbs sampler inference算法。这些情况下，inference算法本身是一个限制因素。我们通过开发了一种新的O(1)-per-token Metropolis-Hastings sampler来处理这个瓶颈，它比SparseLDA sampler几乎快一阶——它允许我们在小集群上处理大语料。我们注意到：最新的AliasLDA也提供了一个解法来解决SparseLDA的瓶颈。然而，另一方面，AliasLDA的计算复杂度为O(Kd)，因此，并不擅长处理更长的文档（比如网页），因为doc-topic表在初始迭代时是dense的，因此Kd会很大；更一方面，AliasLDA的paper只描述了一种单机实现，它的分布式和可扩展性是不清楚的（特别是考虑到AliasLDA的高空间复杂度，对于每个词的alias table需要O(K)）。在本paper中，我们展示了Metropolis-Hastings sampler在单机上在各指标上均快于AliasLDA，这使我们不再考虑使用AliasLDA。

上述提到的large-scala LDA本质上分为：data-parallelism（在机器之间分割文档） vs. model-parallelism（在机器上分割word-topic分布）。YahooLDA[1]和基于parameter-server的实现[11]，将word-topic看成是全局共享的，在这种inference算法上，关于如何跨机器进行物理排序word-topic分布是不可知的。更重要的， 它们在token topic索引$ z_{di} $上以文档为中心的方式调度inference计算，因此将它们看成是data-parallel-only的实现。结论是，我们即不希望yahooLDA的实现，也不希望基于parameter-server的实现，来处理非常大的主题模型（1万亿参数）。一旦整个语料在足够多的机器上传输，每台机器的本地文档只有一小部分参与LDA模型，因此，每台机器需要的内存不会太大。这样的设计，如果没有大的计算集群，根本不能处理大的主题模型。

另一方面，PLDA+和Peacock会额外根据词$ w_{di}$ 将token topic indicators $ z_{di} $ 进行分组（group）；这是有好处的。因为它会减小word-topic分布(在每个worker机器上持有)的比例——可以有效地在top个data-parallelism上进行model-parallelism。特别的，采用一种grid-like model-paralled分区策略，需要让训练数据、LDA模型和worker机器进行通信（对比我们的设计，这需要额外的开销）。另一点要注意的是在PLDA+的设计中的pipeline，只需要workers在内存中持有模型的一小部分；然而，这样的系统使用了一个过时的，很慢的Gibbs sampler，它们的数据分布和调度对于极大的数据和模型来说不合适。特别的，它的word-bundling策略依靠一个关于训练数据的倒排索引表示，会是文档内存的两倍（这几乎不可承受，因为内存在large-scale LDA中很昂贵）。LightLDA采用了一种不同的data-and-model-paralled策略来最大化地减小内存和CPU开销：我们将word-topic分布以一种结构感知的model-parallel方式进行切分（slice），我们在workers上将文档块固定，所需要的模型参数通过一种异步有界的data-paralled scheme（a bounded-asynchronous data-parallel scheme）传输给它们。这允许我们可以在一个10亿级的文档上，只需要8台机器就可以训练一个1万亿参数的LDA模型。当增加额外的机器时可以获取线性加速。

3.结构感知的模型并行(Structure-Aware Model Parallelism for LDA)

当训练LDA，使用10w个主题可以极大提升所学到的模型——一个原因是，非常大的语料常包含许多小的，但很合适的主题（长尾主题：long tail），当模型只有上千个主题时常检测不到。然而，对于一个达到上百万的主题模型，这会导致word-topic分布包含万亿的参数，因为互联网大语料可以很轻易的包含上百万的唯一词汇。LDA模型在实际中是很稀疏的（许多参数为0），一个上万亿参数的模型比最新的结果要大两阶【12，1，21，11】；事实上，一些已经存在的分布式实现不会扩展到这么大的模型，因为模型需要通过workers进行划分——例如，系统设计需要假设一个worker’s的文档将从不会达到模型的一小部分，但这在一些语料上是不实际的。除了通过worker机器上进行分区外（所有最新的分布式LDA实现都以这种方式），我们必须同时以一种保守的方式对模型进行分区，以确保workers不会耗尽内存。这就是结构感知的model-parallelism。

在我们的model-parallel策略中，我们简单回顾下LDA模型来确定下相关术语。假设在语料中每个文档按以下方式生成：

• $ \phi_{k} ~ Dirichlet(\beta) $: 为每个主题k抽取词分布$ \phi_{k} $
• $ \theta_d ~ Dirichlet(\alpha) $：为每个文档d抽取主题分布$theta_d $
• $ n_d ~ Poisson(\gamma) $：对于每个文档d，抽取长度$n_d$（例如：它包含的tokens数目）
• 对于每个token $ i \in { 1,2, \cdot, n_d } $：
  • $z_{di} ~ Multinomial(\theta_{di}) $: 抽取token的主题
  • $w_{di} ~ Multinomial(\phi_{z_{di}})$：抽取token的词

对于标准的collapsed Gibbs sampler for LDA，以如下方式表述：除了token的topic indicator $z_{di}$ 外，所有变量都被analytically integrated out，我们只需要根据Gibbs sample $ z_{di} $：

\[p(z_{di}=k\| rest) \propto \frac{(n_{kd}^{-di}+\alpha_k)(n_{kw}^{-di} + \beta_{w})}{n_k^{-di} + \hat{\beta}}\]

…(1)

其中w是$w_{di}$的简写，$ \hat{\beta} := \sum_{w}\beta_{w}$， $n_{kd}^{-di}$是文档d中分配给主题k的token数（除了token $z_{di}$），$n_{kw}^{-di}$是词w（跨所有文档）被分配给主题k的token数（除了token $z_{di}$）。为了避免昂贵的重新计算开销，这些counts（也被称为是“充分统计（sufficient statistics）”）可以缓存成tables，当一个token topic indicator $z_{di}$更改时会发生更新。特别的，所有count $n_{kd}$的集合口头上指的是document-topic table(作为$\theta_d$的sufficient statistics)，而所有counts $n_{kw}$的集合则指的是word-topic table（作为$phi_{k}$的sufficient statistics）。

最小情况下，任何分布式LDA实现必须将token topic indicators $z_{di} $、doc-topic table$n_{kd}$（即data），word-topic table $n_{kw}$（即model）进行分区(partition)。当一个LDA sampler正在采样一个token topic indicator $z_{di}$时，它需要看下在word-topic table（即document）中的第$n_{kw_{di}}$行(row)。然而，原始的分区策略会导致一些机器获取word-topic table的一大块：假设我们按顺序对每个文档的tokens进行抽样，那么该worker必须将根据文档中的词汇看到在word-topic table中的所有行。使用快速的Metropolis-Hastings sampler，每个worker可以每秒抽样成千上万的文档（假设每个文档有成百上千个token）；更进一步，我们经验上观察到上百万的文档（web-scale语料会更大）足够激活整个word-topic table。这样，原始的序列只描述了word-topic table在每个worker上进出时的快速交换（swap），会生成一个过高的网络通信开销。

我们的结构感知的model-paralled方法打算解决在fast LDA sampling和每个worker上受限内存空间之间的矛盾；这受到块坐标下降算法（block coordinate descent algorithms）的启发。数据块在运行LDA sampler前生成，我们注意到，在每个块上实例化词汇表中的词汇开销很小。该信息绘作为meta-data绑定到块（block）上。如图1所示，当我们加载一个数据块（和它的meta-data）到本地内存（红色的正方形）时，我们从块中的本地词汇(local words)选择一小部分词集合（图中的V1）。这词集足够小，根据在word-topic table中的第$\n.,w_{di}$行，可以存储在worker上的本地内存中——我们将这些行集合称为一个模型切片（“model slice”）。我们的系统会通过网络获取（fetch）model slice，sampler则只对块中的这些tokens进行抽样，它们可以被获取到的切片覆盖到；所有的其它tokens将不会接触到。这种方式下，系统只需要在本地内存中维护一个瘦模型切片（thin model slice），在当前数据块中对所有文档可复用。一旦由slice所覆盖的所有tokens被抽样到，系统会通过网络获取（fetch）下一个model slice（称为V2），对由它覆盖到的tokens进行抽样处理。这种方式（类似于TCP/IP协议或图像处理中的滑动窗口），系统会处理一个数据块中的所有tokens，在从磁盘中加载下一个块之前，一次一个slice。这种和磁盘交互的块交换（swapping of blocks）可以进行核外执行（out-of-core execution）.

图1: LDA中的: Structure-aware model parallelism

除了可以让worker保持低内存需求外，结构感知的模型并行（structure-aware model parallelism）可以以如下方式缓和网络开销瓶颈：

• 1.workers不会移到下一个model slice，直到当前slice上相应的所有tokens都被抽样到，我们不需要对模型应用caching和eviction策略。
• 2.因为data-model切片是静态的、不可变更的（static and unchanging），我们将它们的加载（loading：从磁盘中读取数据块，从中心parameter server获取模型）进行pipeling，来隐藏网络通信延迟。

最后要注意一点，structure-aware model parallel策略会“发送模型给数据：（sends the model to the data）”，而非相反。这受两点启发：

• 1.数据（the data）（包含tokens $w_{di}$和相应的topic indicators $ z_{di} $）比模型(the model)更大（模型有万亿参数）
• 2.sampler收敛，模型会更加稀疏（这样可以减少网络通信），而数据的大小仍然是常数。

我们观察到其它分布式LDA的设计采用的是“发送数据给模型（send data to model）”的策略，这会开销更大。

4.LDA的Fast Sampling算法

structure-aware model-parallelism的目的是：在小集群上，从十亿级别的文档中学到非常大的，上万亿参数的LDA模型；更进一步，bounded-asynchronous data-parallel schemes可使用parameter servers来减小网络同步和通信的开销。然而，这些还不能让大的LDA模型快速地进行训练；这激发了我们更大的贡献：一种新的LDA sampling算法，它比最新的算法（SparseLDA和AliasLDA）收敛地更快。为了解释我们的算法，先简单回顾下SparseLDA和AliasLDA的机制。

SparseLDA

SparseLDA使用这样的观测：

• 1.大多数文档只有少量的主题
• 2.大多数词汇只参与少量的主题

这表现为doc-topic和word-topic table同时具有稀疏性（sparsity），其中SparseLDA通过将 collapsed Gibbs sampler的条件概率（等式1）分解三个terms：

\[p(z_{di}=k\| rest) \propto \frac{\alpha_{k}\beta_w}{n_k^{-di}+\hat{\beta}} + \frac{n_{kd}^{-di}\beta_w}{n_k^{-di}+\hat{\beta}} + \frac{n_{kw}^{-di}(n_{kd}^{-di}+\alpha_{k)}{n_k^{-di}+\hat{\beta}}\]

…(2)

第一部分为r，第二部分为s，第三部分为t。当Gibbs sampler接近收敛时，第二项s和第三项t会变得很稀疏（因为文档和词被安排到少量的主题上）。SparseLDA首先抽样三个项r,s,t中的其中之一，根据它们在k个可能结果上的概率求和，接着，SparseLDA会其于选中的r,s,t中的某项来抽样主题k。如果s或t被选中，那么抽样的主题k会各自花费$O(K_d)$或$O(K_w)$的时间，其中$K_d$是文档d所包含的主题数，而$K_w$是词w所属的主题数。折算下来SparseLDA的抽样复杂度为$O(K_d+K_w)$，而对于标准的collapsed Gibbs sampler只有O(K)。

AliasLDA

AliasLDA提出了另一种的Gibbs sampling probability分解：

\[p(z_{di}=k\| rest) \propto \frac{n_{kd}^{-di}(n_{kw}^{-di}+\beta_{w})}{n_{k}^{-di}+\hat{\beta}} + frac{\alpha_{k}(n_{kw}+\beta{w})}{n_k+\hat{\beta}}\]

…(3)

第一项为u，第二项为v，AliasLDA会预先为第二项v计算一个alias table，它允许在O(1)时间内通过Metropolis-Hastings被抽样到。通过在许多tokens上复用该table，构建该表需要O(K)的开销，折算下来每个token需要O(1)的开销。第一项u是稀疏的（在$K_d$上线性，即在文档d上的当前主题数），可以在$O(K_d)$时间内被计算。

4.1 Metropolis-Hastings sampling

我们看到，折算成每个token所需要的抽样时间，SparseLDA和AliasLDA达到了$O(K_d+K_w)$和$O(K_d)$。这样的加速抽样是很重要的，因为我们可以简化；原始的collapsed Gibbs sampler (Eq. 1)对于每个token需要O(K)的计算开销，这在K=100w个主题上明显是棘手的。SparseLDA减小了sampling的复杂度，通过利用稀疏性，而AliasLDA则利用alias方法以及Metropolis-Hastings算法。LightLDA sampler也使用Metropolis-Hastings，但对于合适的分布式设计有新的见解，这对于高性能表现来说相当重要。我们展示了sampling过程可以被加速，更进一步，使用设计良好的proposal distribution q(·)给true LDA posterior p(·)。

一个A well-designed proposal q(·)可以以两种方式加速sampling过程：

• 1.从q(·)中抽取样本，比从p(·)中抽取样本更便宜
• 2.Markov chain可以快速混合（只需要一少部分step）

这涉及到如何为p(·)构建一个良好的q(·)？如果q(·)与p(·)非常相似，那么构建的Markov chain会快速混合——然而，从q(·)中抽样的开销会和从p(·)的抽样一样昂贵。相反地，如果q(·)与p(·)非常不同，我们可以从中抽样的开销会更小——但这种构建的Markov chain的mix会过慢，需要许多步才会收敛。为了理解这种trade-off，需要考虑下面的临界情况：

• 均匀分布Proposal（Uniform Distribution Proposal）: 假设我们选择了q(·)作为均匀分布。MH算法会提出：下一状态 t ~ Uni f(1,…,K) ，并接受$min(1, \frac{p(t)}{p(s)}$的概率的状态。很明显，从一个均匀分布中进行sampling是开销很小的，可以在O(1)时间内完成；然而，均匀分布是非稀疏的，因此与p(·)会相当远，它需要多步的MH来进行mix。

• 完全条件分布Proposal（Full Conditional Distribution Proposa）：我们可以选择p(·)作为proposal分布q(·)。MH算法提出了下一步t的概率为p(t)，接受$ min{1, \frac{(p(t))p(s)}{p(s)p(t)}=1 $；例如：算法会接受所有的proposals。从q(·)中抽样很明显开销与p(·)一样多，但mixing很很快，因为所有的proposals都被接受了。

4.2 因子分解（Factorization）的Cheap Proposals

为了设计一个开销很小的MH算法，它具有高的mixing rate，我们采用了一个因子分解的策略（a factorized strategy）：我们只构建了一个O(1) proposals的集合，选在它们之间做交替选择。为了构建这样的proposals，我们从关于token topic indicator $z_{di}$的真实条件概率(true conditional probability)开始：

\[p(z_{di}=k\| rest) \propto \frac{(n_{kd}^{-di}+\alpha_k)(n_{kw}^{-di}+\beta_w)}{n_k^{-di}+\hat{beta}}\]

…(4)

观察到，它可以分解成两项：

\[p(z_{di}=k\| rest) \propto (n_{kd} + \alpha_{k}) x \frac{n_{kw}+\beta_w}{n_k + \hat{\beta}}\]

…(5)

第一项为doc-proposal，第二项为word-proposal。即使我们利用这两项的稀疏性，从该条件概率中抽样的开销至少要$ O(min(K_d,K_w)) $——我们是否可以做的更好呢？我们观察到，第一项是依赖文档的（document-dependent），也词汇独立的（word-independent），而第二项是文档独立的（document-independent）、依赖词汇的（word-dependent）。更进一步，它直觉上可看到，最可能的主题是从doc-dependent项和word-dependent项上那些高概率的部分；然而，单独的项可以作为一个好的proposal q——但如果p在主题k上具有高概率，那么这一项也可在k上具有高概率（倒过来不正确）。重要的是，alias方法（在AliasLDA中使用的）可以应用于两项，减少从这样的proposal中抽样的开销至：分摊下来，每token的时间复杂度O(1)。下面分别讨论下两种proposal。

Word-Proposal for Metropolis-Hastings

将$p_w$定义成word-proposal分布：

\[p_w(k) \propto \frac{n_{kw}+\beta_{w}}{n_k+\hat{\beta}}\]

…(6)

状态转移s->t的接受概率（aceptance probability）为：

\[min\{1, \frac{p(t)p_w(s)}{p(s)p_w(t)} \}\]

…(7)

假设$\pi_w := \frac{p(t)p_w(s)}{p(s)p_w(t)}$，我们可以展示成：

\[\pi_w = \frac{(n_{td}^{-di}+\alpha_t)(n_tw^{-di}+\beta_w)(n_s^{-di}+\hat{\beta})(n_{sw}+\beta_w)(n_t+\hat{\beta})}{(n_{sd}^{-di}+\alpha_s)(n_{sw}^{-di}+\beta_w)(n_t^{-di}+\hat{\beta})(n_{tw}+\beta_w)(n_s+\hat{\beta})}\]

…(8)

一旦$t ~ p_w(t)$被抽样到，接受概率可以在O(1)时间内被计算，只要我们根据所在的sufficient statistics n。在抽样期间。直觉上，$\pi_w$是很高的（相对于topic s），不论何时proposed topic t在文档中内很流行，或者对于词w来流行。因为word-proposal趋向于提出主题t，对于词w很流行，使用word-proposal将会探索p(k)的状态空间。为了在O(1)内抽样$p_w$，我们使用类似于[10]的alias table。如图2所示，alias方法的基本思想是，将一个非均匀的分布转化成一个均匀的分布（例如：alias table）。因为alias table会在MH sampling中复用，转称的开销可以分摊到O(1).

尽管alias方法具有O(1)的分摊时间复杂度，它的空间复杂度仍然很高，因为每个词的proposal分布的alias table会存储2K个值：每个二元（bin）的分割点和分割点上的alias value。如果我们需要存储许多词的alias table，这是禁止的。我们的见解是：alias table可以稀疏化，我们可以通过将$p_w=\frac{n_{kw}}{n_k+\beta}+\frac{\beta_w}{\n_k+\beta}$开始。接着抽取两项中的其中之一，我们使用一个预先构建的alias table（从$n_{kw}$中创建，指向于词w）中选中一个主题，它是稀疏的。如果我们抽取第二项，我们也用一个预先构建的alias table（从$n_k$中创建，对于所有词w是共用的，可为所有V个词分摊）来选中一个主题，它是dense的。这种方式下，我们将构建词w的alias table所需的时间复杂度和空间复杂度减小到：$O(K_w)$（词w所参与的主题数）

Doc-Proposal for Metropolis Hastings

将$p_d$定义成doc-proposal分布：

\[p_d(k) \propto n_{kd} + \alpha_{k}\]

…(9)

s->t状态转移的接受概率为：

\[min(1, \frac{p(t)p_d(s)}{p(s)p_d(t)})\]

…(10)

假设$\pi_d := \frac{p(t)p_d(s)}{p(s)p_d(t)}$，我们可以展示为：

\[\pi_d=\frac{(n_{td}^{-di}+\alpha_t)(n_{tw}^{-di}+\beta_w)(n_s^{-di}+\hat{\beta})(n_{sd}+\alpha_s)}{(n_{sd}^{-di}+\alpha_s)(n_{sw}^{-di}+\beta_w)(n_t^{-di}+\hat{\beta})(n_{td}+\alpha_t)}\]

…(11)

至于word-proposal，我们看到：doc-proposal满足，在任何时候主题t（相对于主题s）在文档d内是流行的，或者对于词w。我们将$p_d(k) \propto \frac{n_{kd}}{n_d+\alpha}+\frac{\alpha_k}{n_k+\alpha}$分解成类似于word-proposal的结构，当我们选择第一项时，我们不需要显式构建alias table——这是因为document token topic indicators $z_{di}$可当成是一个alias table。特别的，第一项$n_{kd}$会统计主题k在文档d内的次数，换句话说：

\[n_{kd} = \sum_{i=1}^{n_d}[z_{di}=k]\]

…(12)

其中[·]是一个指示函数。这暗示着，对于未归一化的概率分布$n_{kd}$来说，数组$z_{di}$是一个alias table，因此我们可以简化为：通过一个整数j非均匀地从{1,2,…,nd}中抽取一个整数$n_{kd}$，并设置为：$z_{di}=z_{dj}$。图3使用了一个toy example来展示该过程。因而，我们可以下结论：doc-proposal可以在O(1)的非分摊时间中被抽样（因为我们不需要构建一个alias table）。

4.3 结合proposals提升Mixing

不管doc-proposal，还是word-proposal，可以被独立用于LDA中一种有效的MH算法，实例上，许多MH-steps（为每个token重复抽样）需要生成合适的mixing。只需一少部分的MH-steps，单独使用word-proposal可以支持word-topic分布中的稀疏性（例如：每个词都属于很少的主题），但会在document-topic分布中引起很低的稀疏性（例如：每个文档包含了多个主题）。相反地，单独使用doc-proposal，只需要少量的MH-step就会导致在document-topic分布上的稀疏性，同时产生非稀疏的word-topic分布。因此，这种proposal可以很快地对tokens进行抽样，它们需要许多MH-steps来进行很好的混合(mix)。

快速Metropolis-Hastings mixing的关键是，一个proposal分布可以快速探索状态空间，并达到具有高概率（the models）的所有状态。word-proposal的$p_w(k)$擅长于proposing自己的模式（会在少量主题上产生词的聚集），并同样为doc-proposal $p_d(k)$进行proposing。如图4所示，单独使用word-proposal或doc-proposal，一些模式（modes）将从不会被快速探索到。

当仍然维持较高的sampling效率时，我们如何来达到一个更好的mixing rate？如果我们看一下$p(k) \propto p_w(k) x p_d(k) $，我们会看到：对于p(k)会很高（例如：一个mode），我们需要：$p_w(k)$或$p_d(k)$要足够大——但不需要同时满足。然而，我们的解决方案是：将doc-proposal和word-proposal结合成一个“cycle proposal”:

\[p_c(k) \propto p_d(k) p_w(k)\]

…(13)

对于每个token，通过我们构建一个MH序列，

5.对头部词(Power-Law Words)采用混合数据结构

即使是data-model分区，当对于非常大的主题数的LDA时，内存大小仍然是一个障碍。LDA模型，或者是word-topic table$ n_{kw} $，是V X K的矩阵，交且一个naive dense representation版本，会需要过高的内存——例如，对于本试验中所使用的V=K=100w，考虑32-bit的整数条件，模型需要4T字节的size。即使用合理的配置高的机器，128G的RAM，也只能需要32台机器来在内存中存储矩阵——实际上，实际的使用可能会更高，因为存在其它系统开销（比如：cache, alias tables, buffers, parameter server）。

一个常用的解决方法是，将sparse数据结构转换成：hash maps。在稀疏存储背后的原理是，文档词汇会遵循长尾分布（power-law）图5所示。有两个暗示：

• 1）在移除stop-words如果看，所有有意义的词汇的词汇几乎会超出32-bit integer的范围(2,147,483,647）；这在150亿文档和3w亿tokens，只保留300词频上的web-scale语料上测试时，会超过32-bit的限制。出于这个原因，我们选择使用32-bit的整数，而非64位。
• 2) 即使有数十亿的文档，大多数词的出现次数要少于K次（其中K是主题数，在我们的试验中达到了100w）。这意味着大多数行$n_k$，在word-topic table中是相当稀疏的，因此一个稀疏行表示（hash maps）将极大减小内存占用（memory footprint）。

然而，对比于dense arrays，sparse的数据结构表现出较差的随机访问表现，它会伤到MCMC算法（比如：SparseLDA，AliasLDA以及我们的r Metropolis-Hastings算法），因为它们所有都很严重地依赖于随机访问索引。在我们的试验中，对比于dense arrays，使用纯hash maps会导致一个serveral-fold表示的丢失。当维持高的sampling throughput时，我们怎么才可以享受低内存占用？我们的解决方案是混合数据结构（hybrid data structure），其中，word-topic table的行对应于频繁出现的热词，用dense arrays进行存储；而对于非常见的长尾词，则使用开放寻址/二次探测（open-addressing/quadratic-probing）的hash tables。在数十亿级别的web-scale的语料上，我们发现词汇表中10%的词是热词（“hot”），会覆盖95%的语料中的tokens，而剩余90%的词汇表词则是长尾词，只会覆盖5%的tokens。这暗示着：

• (1)大多数会访问我们的混合word-topic table中的dense arrays，这会保持高的throughput
• (2)word-topic中的大多数行仍是稀疏的hash tables，它可以让内存占用量合理保持较低水平

在我们的V=K=100w的试验中，我们的混合word-topic table只使用0.7TB，如果我们使用纯dense arrays会达到4TB。当该表跨24台机器分布时，每台机器只需要30GB，可以空出昂贵的内存来给其它系统组件用。

6.系统实现

分布式实现对于web-scale的数据来说是令人满意的：它们会将训练时间减少到可承受的水平，大多数实践者会访问至少一台分布式集群。然而，目前存在的分布式LDA实现，只展示出在小问题规模上（特别是模型size）工作良好，或者使用极大的计算集群（有时上千台机器）来完成可接受时间内的训练。如何使用数十台机器来应对和解决大的LDA问题？如果我们希望使用数十亿的训练语料（每个文档至少上百tokens）会占用数T空间，那么在data-paralled的这一点上，简单地从磁盘拷贝数据到内存中都会花费数十小时，当将数据通过网络进行传输时也会花费类似的时间。在model-paralled这一点上，存储1T的参数（100w词 x 100w主题）可以达到上T的内存——只能分布式存储，需要跨机器的参数同步，会有很高的网络通信开销。根据这些注意点，为LightLDA设计了一个架构，它可以将数据传输和参数通信开销尽可能地减少，并让小集群实现成为可能。

系统总览 在开源分布式机器学习Petuum上构建了LDA，对于大规模机器学习，它为结构感知的模型并行（structure-aware model parallelism）以及有界异步数据并行（bounded asynchronous data-parallelism）提供了一个总的框架。根据代码，我们会利用parameter server来实现有bounded asynchronous data-parallelism。一个parameter server对用户会隐藏分布式网络细节（通信和并发控制 ），提供好用的API来开发分布式机器学习程序——该思想让机器学习专家专注于描述算法逻辑，而非系统的细节。我们首先引入总的parameter server的思想，接着描述我们如何让大的LDA模型在小集群上进行增强。

Parameter Server和Data Placement 在基本水平上，一个parameter server(PS)会保存一个分布式共享内存接口[16]，其中编程者可以从任何机器上访问内存，对于参数的物理位置不可知。本质上，PS扩展了在单个机器上的内存结构（如图6）；存储介质越接近CPU core，越具有较低的时延和较高的传输带宽，但有更少的容量（capacity）。在PS架构上，每个机器的RAM被分成两部分：对于客户端(client)使用的局部RAM，以及对于中心化参数存储的远程RAM（也称为：“server” part）。这样的硬件限制，以及由大的主题模型数据模型引入的需要条件，强烈地影响着我们运行Metropolis-Hastings算法的方式。

我们使用PS来存储两种类型的LDA模型参数：word-topic table $ { n_{kv} }{k=1,v=1}^{K,V}$，它会统计词v分布给主题k的tokens数，一个长为K的“summary row”：$ { n_k }{k=1}^{K} $，它会统计分配给主题k的总tokens数。32-bit的整数可以被用于word-topic table（使用一个dense arrays和sparse hash maps的组合），而对于summary row则使用一个64-bit的整数数组。我们观察到，随着LDA sampler的处理，word-topic table会变得进一步稀疏，随着时间推移会产生更低的网络传输开销。更进一步，Petuum PS支持一个bounded-asynchronous consistency model，它可以减少内部迭代（inter-iteration）参数同步时间，通过一个过时的参数s——对于LightLDA，它已经是一个pipeline的设计，我们发现最优值为：s=1.

如果输入数据比模型大（仍保留不变的throughout LDA接口），通过网络进行传输数据是不明智的。相反地，我们会进行shuffle，跨所有worker机器的磁盘共享语料，每个worker只在它的本机磁盘上访问数据。在图6中，$ { w_{di}, z_{di} }_{d=1,i=1}^{D_n,n_d} $表示在第n台worker上的一份训练数据的shard，其中$D_n$表示第n台worker上的文档数，$n_d$表示在文档d上的tokens数。每个worker的本地内存会持有：

• (1)当前活动的工作数据集$ { w_{di}, z_{di} }{d=1,i=1}^{D{S_n,n_d}} $
• (2)模型$ { n_{kv} }{k=1,v=1}^{K,V_s} $需要抽样tokens的当前集合（使用Metropolis-Hastings sampler）。在抽样期间，我们更新token topic indicators $z{di}$，以及word-topic table。token-topic pairs（$w_{di}, z_{di}$）位于本地worker上，不会有网络通信，而word-topic table则被存储在PS中，因而需要一个后台线程来进行有效通信。

Token 和 Topic Indicator Storage 作为data-parallel执行的一部分，每个worker机器会在本地磁盘上存储语料的某个shard。对于web-scale级别的语料，每个shard仍会很大——如果没有许多T，也会有数百G——它不会将整个shard加载进内存中。这样，我们进一步将每个数据的shard分割成数据块（data blocks），并将这些块同时流式化进内存中（见图1左）。根据数据结构，我们故意将tokens $w_{di}$和它们的topic indicators $z_{di}$进行side-by-side放置，作为一个$(w_{di}, z_{di})$ pair的向量(vector)，而非两个独立的tokens和topic indicators数组。我们这么做是为了提升数据的locality和CPU cache更有效：无论何时当我们访问一个token $ w_{di} $时，我们总是需要访问它的topic indicator $z_{di}$，vector-of-pairs的设计方式可以直接提升locality。这种设计的一个缺点是：额外的磁盘I/O，每次读/写 tokens $w_{di}$一个数据shard到磁盘中时会swap out。然而，磁盘I/O总是通过对读/写进行pipeline的方式进行masked，当sampler正处理当前shard时会在后台完成。

我们指出，我们的streaming和disk-swapping(out-of-core)设计，天然的会以如下的方式支持容错：如果我们通过原子文件重写来执行一个data swapping到磁盘，接着当系统发生失败时，它会简单地通过warm-start来进行resume训练过程：读取swapped-to-disk模型，re-initialize word-topic和doc-topic table，继续。作为比较，像PLDA+和YahooLDA也具有容错机制，它们需要周期性地将数据和(或)模型进行dump出来——但这在大数据/模型的情况下会引发不平凡的开销。

对结构感知的模型并行进行tuning 我们在第3部分引入了Structure-Aware Model Parallelization的高级思想并应用到LDA中，仍有许多改进来提升效果。我们描述了最重要的几点：

• 1.在计算一个数据块或一个模型切片时，一个worker的CPU core需要等待下一个数据块/模型切片从磁盘/网络被加载。我们通过pipelinging（如图7所示）消除了该I/O延迟，尽管我们注意到：执行pipelining需要很仔细的参数配置（samplers的throughout，数据块的size，模型切片的size等）
• 2.为了阻止数据加载在跨模型切片时的imbalance，我们通过对词汇表通过词频进行排序来生成模型切片，接着对词汇进行shuffing。这种方式下，每个切片会同时包含热词（hot words）和长尾词（long tail words），来改善加载的平衡。
• 3.为了消除数据传输的不必要性，当生成数据块时，我们对token-topic pair $w_{di}, z_{di}$根据$w_{di}$在重排后(shuffled)的词汇表中的位置进行排序，确保属于相同的模型切片的所有tokens在数据块上实际是连续的（见图1）。这种排序只需要执行一次，在数据处理平台如Hadoop上会很快（对比于LDA sampling time）。我们认为：比起PLDA+中的”word bundle”，这种方式更有效，PLDA+会用一个倒排索引来避免数据传输，但会带来两倍的内存开销。

多线程的效果 我们的sampler在单个worker上会并行。通过将内存中的数据块分割成不相效的部分（通过独立线程进行抽样），并在线程间共防震内存中的模型切片。再进一步，我们会让shared模型切片变得immutable, 在将这些数据汇总发送到parameter server之前，会在本地延迟所有的模型更新。通过将模型切片保持immutable状态，我们避免了并发问题（比如：条件竞争和锁），这样就可以达到在接近线性的intra-node扩展性。当模型更新延迟时，理论上会减慢模型的收敛率(convergence rate)，实际上，它会消除并发问题，增加sampler throughput，轻易地胜过更慢的收敛率。

现代的server级机器包含了许多CPU sockets（每个CPU有许多物理core），可以连接到不同的内存条(memory banks)上。当这些内存条可以被所有CPU寻址时，当访问绑定到另一socket上的远端内存条时,内存延迟会更长——也是就是：Non-Uniform Memory Access (NUMA). 在我们的实验中，通过对sampling参数进行调整（比如：f Metropolis-Hastings steps数），我们对它们进行部分寻址，发现NUMA的作用相当大。也就是说，我们相信，合适的NUMA-aware编程是一个更好的长期解决方案来解决该问题。最终，我们注意到：为每个线程设置core的关系，在intel处理器上开启硬件超线程（hardware hyper-threading）效果很好，我们观察到一个30%的性能增益。

7.试验数据

对比之前的LDA实现，我们展示了：只需要更少的机器，LightLDA可以调练更大的LDA模型——这归因于data-model的分片，特别是新的Metropolis-Hastings sampler，它比SparseLDA和AliasLDA要快一阶。我们使用许多数据集（表7），注意，Bing的”web chunk”数据集有12亿的网页（共2000亿的tokens）。我们的试验表明：

• (1)在core数目和机器数目上，我们的分布式实现有接近线性的可扩展性
• (2)比起state-of-art的SparseLDA和AliasLDA samplers，我们的分布式实现有接近线性的可扩展性（在单线程设置中测量得到）
• (3)最重要的是，LightLDA可以允许很大的数据size和模型size，只需要8台左右机器即可。

参考

LightLDA: Big Topic Models on Modest Compute Clusters

最新一朋友在做比特币矿池方向的创业，受邀请帮忙研究下运营矿池的破产概率问题，以尽可能地规避风险。下面会将相应的一些概念与问题一一道来。

1.泊松分布与挖矿问题

泊松分布

• 泊松分布适合于描述单位时间内随机事件发生的次数。
• 泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生率。
• 泊松分布的期望和方差均为λt.

1.1 问题

比特币挖矿的数目服从泊松分布。

这是为什么？且细细看来。

• 1.btc挖矿机的一次计算是否产生一个合法区块可以认为是一个随机事件，任何所有的计算hash彼此相互独立。

• 2.每次hash计算有对应的计算难度，标为D，决定着发现一个合法块的难度。

• 3.每次hash计算(32位hash计算，共有1/2^32个hash值)都会有 $ \frac{1}{2^{32}D} $的概率产生一个合法区块。

• 4.矿工的算力(hashrate:每秒计算hash的次数)：h

ok，这个问题可以化简为：

t时间内，该算力的矿工可以挖到多少btc区块？它服从什么分布？

1.2 解释

ok，很明显，速率问题，泊松分布.

速率λ（即：每秒能挖到多少个区块）为：$ \lambda=\frac{h}{2^{32}D} $

• 单人在t时间内挖到的区块数目期望：$ E(X)=\lambda t=\frac{ht}{2^{32}D} $
• 单人在t时间内挖到的区块数目方差：$ D(X)=\lambda t=\frac{ht}{2^{32}D} $

另外，还有一个条件：即一个合法区块对应着B个btc。换算成btc的话，这一个常数项的线性变换，即是一个POI(BX)的问题.

根据期望和方差的性质：

• C为常数，X为随机变量
• 期望性质：$ E(CX)=CE(X) $
• 方差性质：$ D(CX)=C^{2}D(X), D(X+C)=D(X) $

从而，我们得到：

单人在t时间内对应回报的期望为：$ E(BX)=BE(X)=\frac{htB}{2^{32}D} $

单人在t时间内对应回报的方差为：$ D(BX)=B^{2}D(X)=\frac{htB^{2}}{2^{32}D} $

单人在t时间内对应回报的标准差为： $ \sigma(BX)=\sqrt{D(BX)}=\sqrt{\frac{htB^{2}}{2^{32}D} $

单人在t时间内对应回报的标准差/期望（标准差是期望的多少倍）为： $ \frac{\sigma(BX)}{E(BX)}=\sqrt{\frac{2^{32}D}{ht}} $

1.3 进一步

矿池挖矿模式与单人solo挖矿模式略有不同：

• 1.它集合了矿池内所有矿工的算力：其hashrate为：H

矿池将在周期t内获得的区块数同样服从泊松分布(为做区分，此处为随机变量Y)。修改一下算力，得到相应的期望/方差：

矿池将在周期t内获得的区块数期望：$ E(Y)=\frac{Ht}{2^{32}D} $

矿池将在周期t内获得的区块数方差：$ D(Y)=\frac{Ht}{2^{32}D} $

将区块数换算成btc，对应的期望/方差：

矿池在周期t内获得的btc期望：$ E(BY)=\frac{HtB}{2^{32}D} $

矿池在周期t内获得的btc方差：$ D(BY)=B^2D(Y)=\frac{HtB^2}{2^{32}D} $

那么在矿池中，单个矿工的收益又是肿么样的一个期望/方差呢？

这里又有另外一项变换：单个矿工的hashrate为：h=qH（其中：q是该矿工对该矿池中总算力的贡献，0<q<1）

根据期望/方差性质，再做一次换算：

在矿池中，个人在周期t内获得的btc期望: $ E(X)=E(qBY)=qE(BY)=\frac{qHtB}{2^{32}D}=\frac{htB}{2^{32}D} $，该值与solo模式一样

在矿池中，个人在周期t内获得的btc方差：$ D(X)=D(qBY)=q^{2}D(BY)=\frac{q^{2}HtB^2}{2^{32}D}=\frac{qhtB^2}{2^{32}D} $，是solo模式的q倍。（0<q<1，因而方差变小，风险也变小了）

2.矿池如何实现收支平衡？

2.1 一般的矿池

矿池通常由一个矿池运营者（pool operator）来维护，它会在相应的服务上花费一定的费用。这通常是区块回报的一个固定百分比：f。因此，对于每个发现的区块，operator都将收到一笔fB的费用，余下的(1-f)B将分配给矿工。

再做一次变换，利用期望/方差的性质：

矿池中，单个矿工获得的的实际btc收入的期望为：$ E(X)=E((1-f)qBY)=(1-f)E(qBY)=\frac{(1-f)htB}{2^{32}D} $，与solo模式略有下降（但其实个人挖一样需要支付电费等问题存在）

矿池中，单个矿工获得的的实际btc收入的方差为： $ D(X)=D((1-f)qBY)=(1-f)^{2}D(qBY)=(1-f)^{2}q\frac{htB^2}{2^{32}D} $，是solo模式的(1-f)^2q倍. 方差更小。

2.2 变态的矿池

PPS矿池就是这样。

只要挖，不管有没挖到，在周期t时间里，矿工都会有收入。

在矿池中，单个矿工的收入的方差为0。operator承担所有的方差，风险更大，因而需要对operator再做一定的补偿。如果operator不正确平衡矿池的费用以及他的财产准备金，矿池有很大可能会破产。

这里有两个问题：

• 补偿方式有变化？
• 在有限资源的情况下，准备金至少需要多少，才能让破产机率更低？

先回到原先讲的：

• 1.矿池中每次hash计算成为一个share的概率：$ \frac{1}{2^{32}} $
• 2.每个share成为合法区块都有一个概率：$ p=\frac{1}{D} $
• 3.矿工在每次提交一个share时将平均接收到的回报：pB
• 4.对于operator则收到的费用: $ (1-f)pB $

2.2.1 推导阶段一

如何分配它？

这里，每次提交share可以当成一个step。在这个周期t内，计算出来的share本身有两个状态：合法（可得到btc）、非法（无效计算，得不到btc）。合法的概率为p，非法的概率为：1-p。

如果合法，则获得B个btc。然后拿出(1-f)pB进行分配给矿工，剩余的归operator自己。如果非法，那就没有收入了，但仍要拿出(1-f)pB进行分配给矿工。这是一个典型的连续时间随机过程，可以用马尔可夫链来表示。一个周期间，operator所得到的收入（包括损失）：

$ X_{t+1}-X_{t}={ \begin{aligned} &-(1-f)pB+B & w.p. & & p \ &-(1-f)pB & w.p. & & 1-p \end{aligned} $$

它的期望为：

\[\begin{aligned} E & = (-(1-f)pB+B)*p + (-(1-f)pB)*(1-p) \\ & = -p(1-f)pB+pB + (p-1)(1-f)pB \\ & = -(1-f)pB + pB \\ & = fpB\end{aligned}\]

同理使用方差计算公式可得，真实的方差为：$ p(1-p)B^{2} $ ，而btc矿池paper将它近似认为：$ pB^{2} $，这里有些疑问（只有当p的概率较大时，才有可能近似）。

根据中心极限定理可知（这一步有待进一步求证），长期行为服从$ (fpB, p(1-p)B^{2}) $的正态分布。而这面的这个随机过程正好服从该分布（期望/方差一致），因而可以近似等价为：

\[X_{t+1}-X_{t}=\{ \begin{aligned} &+\sqrt{p}B & w.p. & & (1+f\sqrt{p})/2 \\ &-\sqrt{p}B & w.p. & & (1-f\sqrt{p})/2 \end{aligned}\]

我们再对这个初始条件按因子$ \sqrt{p}/B $做一下缩放：

\[X_{t+1}-X_{t}=\{ \begin{aligned} &+1 & w.p. & & (1+f\sqrt{p})/2 \\ &-1 & w.p. & & (1-f\sqrt{p})/2\end{aligned}\]

这样缩放的好处，对后面推导有利。每次输赢为常量（f恒定, p恒定）。

2.2.2 推导阶段二

剩下的问题，其实就等价于随机过程中马尔可夫链的经典问题：《赌徒输光问题》。

$a_n$表示，从状态n开始要达到0的概率（表示矿池破产）。我们在第一步得到的条件，表示：$q=(1+f\sqrt{p})/2 $

这个随机过程可以表示为：

\[a_n=qa_{n+1}+(1-q)a_{n-1}\]

可以用常系数齐次线性方程求解该多项式特征方程：

\[q\lambda^{2}-\lambda+(1-q)\]

该方程的解为：

\[1, \frac{1-q}{q}\]

整个特征方程，它的通解形式为：

\[a_n=A+B((1-q)/q)^{n}\]

代入初始值（边界条件）：$a_0=1,a_{\infty}=0 $

即：A=0, B=1，得到$ a_n $：

\[a_n=(\frac{1-q}{q})^{n}=(\frac{1-f\sqrt{p}}{1+f\sqrt{p}})^{n} \approx exp(-2fn\sqrt{p})\]

如果operator以一个R的话准备金启动，矿池的破产概率为：

\[\delta=a_{R/(\sqrt{p}B)} \approx exp(\frac{-2fR\sqrt{p}}{\sqrt{p}B}) = exp(\frac{-2fR}{B})\]

相反地，为了维持一个破产概率最大为$ \delta $，矿池应至少保有准备金：

\[R=\frac{Bln(\frac{1}{\delta})}{2f}\]

参考：

1.Analysis of Bitcoin Pooled Mining Reward Systems. Meni Rosenfeld