[paper阅读] 在线广告中使用主题模型进行用户聚类(一)

动机及背景介绍

pLSA中, 在给定集群信息的情况下, 用户和物品(举个例子, 推荐系统中待推荐的物品, 或者文档聚类中生成的单词)是相互独立的, 而在本文中, 给定一个用户之前的行为之后, 集群id和用户id是相互独立的.

这种差异性帮助我们在有限的时间内通过它的行为历史就能判断出新用户属于哪个集群. 相反, pLSA需要大量内存存储每个现有用户集群id, 然后针对新用户从头开始重新计算主题模型.

Probabilistic Latent Semantic User Segmentation (PLSUS): 基于用户的查询历史将用户表示为词袋. 该方法使用了pLSA, 因此也遇到了上面提到的问题(新用户计算耗时)

LDA: 假设用户为文档, 访问的网站为单词, 使用主题模型LDA对网站用户进行聚类. 这类方法的主要问题在于: 训练LDA时计算复杂度非常高, 以及为新用户进行分群(主题)的难度.

利用移动用户模式并且基于模式的相似性来对用户进行分群. 作者利用了位置和活动的分类以及基于约束的贝叶斯矩阵分解模型来解决稀疏性的问题. 该方法的主要问题在于隐私和可扩展性, 例如, 缺少详细的行为信息以及广告领域中的用户数目使得这些方法非常难以使用.

方法

正如上面提到的, 我们的聚类方法主要是给定用户的历史之后, 基于probabilistic Latent Semantic Analysis(pLSA)和用户及分群的独立性假设的区别. 这个部分中, 我们将介绍pLSA, 然后介绍模型的不同之处以及我们选择该模型的动机.

概率潜在语义分析

概率潜在寓意分析假设存在一个潜在的类变量(例如, 集群或者主题), 以及每个文档在一系列主题上有一个分布. 进一步, 假设给定了主题的信息, 一个单词在一篇文档中出现的概率于文档的id信息无关:

p(word_k | document_j, topic_i) = p(word_k | topic_i)

这使得pLSA成为一个非常强大的生成模型. 也就是说, 如果我们希望在文档d中生成一个新的词, 其步骤如下: 首先, 我们需要基于p(c|d)来生成主题或者集群c, 然后基于p(w|c)获取一个单词w. 将这个过程映射到推荐系统中, 对应的步骤如下, 为用户(文档)选择集群, 然后从该集群中生成物品(单词).

pLSA模型的参数一般使用EM算法获得:

  • Expectation Step: 给定文档和单词计算集群的概率:
    p(c_i | d_j, w_k) = \frac{p(c_i, d_j, w_k)}{\sum_{c_m}p(c_m, d_j, w_k)}
    =\frac{p(w_k|c_i)p(c_i|d_j)p(d_j)}{\sum_{c_m}p(w_k|c_m)p(c_m|d_j)p(d_j)}
    =\frac{p(w_k|c_i)p(c_i|d_j)}{\sum_{c_m}p(w_k|c_m)p(c_m|d_j)}
  • Maximization Step: 更新给定集群后单词的条件概率以及给定文档后集群的条件概率:
    p(w_k|c_i)=\frac{\sum_{d_j}p(c_i, d_j, w_k)}{\sum_{w_m}\sum_{d_j}p(c_i, d_j, w_m)}
    =\frac{\sum_{d_j}\alpha\cdot p(d_j, w_k) p(c_i|d_j, w_k)}{\sum_{w_m} \sum_{d_j}\alpha\cdot p(d_j, w_m) p(c_i|d_j, w_m)}
    =\frac{\sum_{d_j}n(d_j, w_k)p(c_i|d_j, w_k)}{\sum_{w_m}\sum_{d_j}n(d_j, w_m)p(c_i|d_j, w_m)}

其中, n(d_j, w_k)d_jw_k被同时看到的次数. 当\alpha为单词-文档共同出现的总次数时, 这个数会增加(也就是说: p(d_j, w_k)=\frac{n(d_j, w_k)}{\sum_{d_n}\sum_{w_m}n(d_n, w_m)}, 因此 \alpha = \sum_{d_n} \sum_{w_m} n(d_n, w_m)).

进一步,

p(c_i|d_j)=\frac{\sum_{w_k}p(c_i, d_j, w_k)}{\sum_{c_m}\sum_{w_k}p(c_m, d_j, w_k)}
=\frac{\sum_{w_k}p(d_j, w_k)p(c_i|d_j, w_k)}{p(d_j)}
=\frac{\sum_{w_k}\alpha \cdot p(d_j, w_k)p(c_i|d_j, w_k)}{\alpha \cdot p(d_j)}
=\frac{\sum_{w_k}n(d_j, w_k)p(c_i|d_j, w_k)}{n(d_j)}

其中, n(d_j)为训练数据集中文档d_j出现的次数. 当 \alpha为单词-文档共同出现的总次数时, 这个数会增加(也就是说: p(d_j)=\frac{\sum_{w_m}n(d_j, w_m)}{\sum_{d_n}\sum_{w_m}n(d_n, w_m)}, 因此 \alpha = \sum_{d_n} \sum_{w_m} n(d_n, w_m)) 而 n(d_j)=\sum_{w_m}n(d_j,w_m). 注意: \alpha的值也会使得分式上面的p(d_j,w_k)转化为n(d_j,w_k).

正如上面提到的, pLSA模型时一个非常适合用于推荐系统的模型, 因为它能够基于给定的集群id, 为用户推荐一些新的物品(例如, 用户之前没有看过的物品.), 其中物品集和用户集相互独立. 但是, 会带来一个成本问题, 需要存储每个用户的集群信息, 而第二个问题在于如何给新用户进行分群. 在大多数推荐系统中, 用户集合相对稳定(也就是说, 很少有用户的流动), 因此, 很少会出现需要在训练时间段结束之后确定用户集群的情况. 即使物品列表频繁变化, 更新每个集群的物品概率是一件更加简单的工作(一个简单的maximization step). 而在用户集合变化非常大的情况下, 我们则需要运行整个EM步骤.

下周, 将会继续介绍在 在线广告领域作者们遇到的困难, 以及具体的解决方案.

打赏

mickey

记录生活,写给几十年后的自己。