数学基础
- 线性代数
- 概率论与随机过程
- 数值计算
- 蒙特卡洛方法与 MCMC 采样
- 机器学习方法概论
统计学习
深度学习
- 深度学习简介
- 深度前馈网络
- 反向传播算法
- 正则化
- 深度学习中的最优化问题
- 卷积神经网络
- CNN:图像分类
- 循环神经网络 RNN
- Transformer
- 一、Transformer [2017]
- 二、Universal Transformer [2018]
- 三、Transformer-XL [2019]
- 四、GPT1 [2018]
- 五、GPT2 [2019]
- 六、GPT3 [2020]
- 七、OPT [2022]
- 八、BERT [2018]
- 九、XLNet [2019]
- 十、RoBERTa [2019]
- 十一、ERNIE 1.0 [2019]
- 十二、ERNIE 2.0 [2019]
- 十三、ERNIE 3.0 [2021]
- 十四、ERNIE-Huawei [2019]
- 十五、MT-DNN [2019]
- 十六、BART [2019]
- 十七、mBART [2020]
- 十八、SpanBERT [2019]
- 十九、ALBERT [2019]
- 二十、UniLM [2019]
- 二十一、MASS [2019]
- 二十二、MacBERT [2019]
- 二十三、Fine-Tuning Language Models from Human Preferences [2019]
- 二十四 Learning to summarize from human feedback [2020]
- 二十五、InstructGPT [2022]
- 二十六、T5 [2020]
- 二十七、mT5 [2020]
- 二十八、ExT5 [2021]
- 二十九、Muppet [2021]
- 三十、Self-Attention with Relative Position Representations [2018]
- 三十一、USE [2018]
- 三十二、Sentence-BERT [2019]
- 三十三、SimCSE [2021]
- 三十四、BERT-Flow [2020]
- 三十五、BERT-Whitening [2021]
- 三十六、Comparing the Geometry of BERT, ELMo, and GPT-2 Embeddings [2019]
- 三十七、CERT [2020]
- 三十八、DeCLUTR [2020]
- 三十九、CLEAR [2020]
- 四十、ConSERT [2021]
- 四十一、Sentence-T5 [2021]
- 四十二、ULMFiT [2018]
- 四十三、Scaling Laws for Neural Language Models [2020]
- 四十四、Chinchilla [2022]
- 四十七、GLM-130B [2022]
- 四十八、GPT-NeoX-20B [2022]
- 四十九、Bloom [2022]
- 五十、PaLM [2022] (粗读)
- 五十一、PaLM2 [2023](粗读)
- 五十二、Self-Instruct [2022]
- 句子向量
- 词向量
- 传统CTR 预估模型
- CTR 预估模型
- 一、DSSM [2013]
- 二、FNN [2016]
- 三、PNN [2016]
- 四、DeepCrossing [2016]
- 五、Wide 和 Deep [2016]
- 六、DCN [2017]
- 七、DeepFM [2017]
- 八、NFM [2017]
- 九、AFM [2017]
- 十、xDeepFM [2018]
- 十一、ESMM [2018]
- 十二、DIN [2017]
- 十三、DIEN [2019]
- 十四、DSIN [2019]
- 十五、DICM [2017]
- 十六、DeepMCP [2019]
- 十七、MIMN [2019]
- 十八、DMR [2020]
- 十九、MiNet [2020]
- 二十、DSTN [2019]
- 二十一、BST [2019]
- 二十二、SIM [2020]
- 二十三、ESM2 [2019]
- 二十四、MV-DNN [2015]
- 二十五、CAN [2020]
- 二十六、AutoInt [2018]
- 二十七、Fi-GNN [2019]
- 二十八、FwFM [2018]
- 二十九、FM2 [2021]
- 三十、FiBiNET [2019]
- 三十一、AutoFIS [2020]
- 三十三、AFN [2020]
- 三十四、FGCNN [2019]
- 三十五、AutoCross [2019]
- 三十六、InterHAt [2020]
- 三十七、xDeepInt [2023]
- 三十九、AutoDis [2021]
- 四十、MDE [2020]
- 四十一、NIS [2020]
- 四十二、AutoEmb [2020]
- 四十三、AutoDim [2021]
- 四十四、PEP [2021]
- 四十五、DeepLight [2021]
- 图的表达
- 一、DeepWalk [2014]
- 二、LINE [2015]
- 三、GraRep [2015]
- 四、TADW [2015]
- 五、DNGR [2016]
- 六、Node2Vec [2016]
- 七、WALKLETS [2016]
- 八、SDNE [2016]
- 九、CANE [2017]
- 十、EOE [2017]
- 十一、metapath2vec [2017]
- 十二、GraphGAN [2018]
- 十三、struc2vec [2017]
- 十四、GraphWave [2018]
- 十五、NetMF [2017]
- 十六、NetSMF [2019]
- 十七、PTE [2015]
- 十八、HNE [2015]
- 十九、AANE [2017]
- 二十、LANE [2017]
- 二十一、MVE [2017]
- 二十二、PMNE [2017]
- 二十三、ANRL [2018]
- 二十四、DANE [2018]
- 二十五、HERec [2018]
- 二十六、GATNE [2019]
- 二十七、MNE [2018]
- 二十八、MVN2VEC [2018]
- 二十九、SNE [2018]
- 三十、ProNE [2019]
- Graph Embedding 综述
- 图神经网络
- 一、GNN [2009]
- 二、Spectral Networks 和 Deep Locally Connected Networks [2013]
- 三、Fast Localized Spectral Filtering On Graph [2016]
- 四、GCN [2016]
- 五、神经图指纹 [2015]
- 六、GGS-NN [2016]
- 七、PATCHY-SAN [2016]
- 八、GraphSAGE [2017]
- 九、GAT [2017]
- 十、R-GCN [2017]
- 十一、 AGCN [2018]
- 十二、FastGCN [2018]
- 十三、PinSage [2018]
- 十四、GCMC [2017]
- 十五、JK-Net [2018]
- 十六、PPNP [2018]
- 十七、VRGCN [2017]
- 十八、ClusterGCN [2019]
- 十九、LDS-GNN [2019]
- 二十、DIAL-GNN [2019]
- 二十一、HAN [2019]
- 二十二、HetGNN [2019]
- 二十三、HGT [2020]
- 二十四、GPT-GNN [2020]
- 二十五、Geom-GCN [2020]
- 二十六、Graph Network [2018]
- 二十七、GIN [2019]
- 二十八、MPNN [2017]
- 二十九、UniMP [2020]
- 三十、Correct and Smooth [2020]
- 三十一、LGCN [2018]
- 三十二、DGCNN [2018]
- 三十三、AS-GCN
- 三十四、DGI [2018]
- 三十五、DIFFPOLL [2018]
- 三十六、DCNN [2016]
- 三十七、IN [2016]
- 图神经网络 2
- 图神经网络 3
- 推荐算法(传统方法)
- 一、Tapestry [1992]
- 二、GroupLens [1994]
- 三、ItemBased CF [2001]
- 四、Amazon I-2-I CF [2003]
- 五、Slope One Rating-Based CF [2005]
- 六、Bipartite Network Projection [2007]
- 七、Implicit Feedback CF [2008]
- 八、PMF [2008]
- 九、SVD++ [2008]
- 十、MMMF 扩展 [2008]
- 十一、OCCF [2008]
- 十二、BPR [2009]
- 十三、MF for RS [2009]
- 十四、 Netflix BellKor Solution [2009]
- 推荐算法(神经网络方法 1)
- 一、MIND [2019](用于召回)
- 二、DNN For YouTube [2016]
- 三、Recommending What Video to Watch Next [2019]
- 四、ESAM [2020]
- 五、Facebook Embedding Based Retrieval [2020](用于检索)
- 六、Airbnb Search Ranking [2018]
- 七、MOBIUS [2019](用于召回)
- 八、TDM [2018](用于检索)
- 九、DR [2020](用于检索)
- 十、JTM [2019](用于检索)
- 十一、Pinterest Recommender System [2017]
- 十二、DLRM [2019]
- 十三、Applying Deep Learning To Airbnb Search [2018]
- 十四、Improving Deep Learning For Airbnb Search [2020]
- 十五、HOP-Rec [2018]
- 十六、NCF [2017]
- 十七、NGCF [2019]
- 十八、LightGCN [2020]
- 十九、Sampling-Bias-Corrected Neural Modeling [2019](检索)
- 二十、EGES [2018](Matching 阶段)
- 二十一、SDM [2019](Matching 阶段)
- 二十二、COLD [2020 ] (Pre-Ranking 模型)
- 二十三、ComiRec [2020](https://www.wenjiangs.com/doc/0b4e1736-ac78)
- 二十四、EdgeRec [2020]
- 二十五、DPSR [2020](检索)
- 二十六、PDN [2021](mathcing)
- 二十七、时空周期兴趣学习网络ST-PIL [2021]
- 推荐算法之序列推荐
- 一、FPMC [2010]
- 二、GRU4Rec [2015]
- 三、HRM [2015]
- 四、DREAM [2016]
- 五、Improved GRU4Rec [2016]
- 六、NARM [2017]
- 七、HRNN [2017]
- 八、RRN [2017]
- 九、Caser [2018]
- 十、p-RNN [2016]
- 十一、GRU4Rec Top-k Gains [2018]
- 十二、SASRec [2018]
- 十三、RUM [2018]
- 十四、SHAN [2018]
- 十五、Phased LSTM [2016]
- 十六、Time-LSTM [2017]
- 十七、STAMP [2018]
- 十八、Latent Cross [2018]
- 十九、CSRM [2019]
- 二十、SR-GNN [2019]
- 二十一、GC-SAN [2019]
- 二十二、BERT4Rec [2019]
- 二十三、MCPRN [2019]
- 二十四、RepeatNet [2019]
- 二十五、LINet(2019)
- 二十六、NextItNet [2019]
- 二十七、GCE-GNN [2020]
- 二十八、LESSR [2020]
- 二十九、HyperRec [2020]
- 三十、DHCN [2021]
- 三十一、TiSASRec [2020]
- 推荐算法(综述)
- 多任务学习
- 系统架构
- 实践方法论
- 深度强化学习 1
- 自动代码生成
工具
- CRF
- lightgbm
- xgboost
- scikit-learn
- spark
- numpy
- matplotlib
- pandas
- huggingface_transformer
- 一、Tokenizer
- 二、Datasets
- 三、Model
- 四、Trainer
- 五、Evaluator
- 六、Pipeline
- 七、Accelerate
- 八、Autoclass
- 九、应用
- 十、Gradio
Scala
- 环境搭建
- 基础知识
- 函数
- 类
- 样例类和模式匹配
- 测试和注解
- 集合 collection(一)
- 集合collection(二)
- 集成 Java
- 并发
九、DR [2020](用于检索)
推荐系统数十年来在各种商业应用中都取得了巨大的成功。推荐系统的目标是基于用户特征和历史行为从庞大的语料库中检索相关候选
item
。在移动互联网时代,来自内容提供商content provider
的候选item
数量、以及活跃用户数量都迅速增长到数千万甚至数亿,这使得设计准确的推荐系统accurate recommendation system
变得更加具有挑战性。算法的可扩展性scalability
和效率efficiency
是现代推荐系统面临的主要挑战。大规模推荐的核心问题之一是准确accurately
、高效地efficiently
检索出最相关的候选item
,最好是在亚线性sub-linear
时间内。推荐系统早期的成功技术之一是协同过滤
collaborative filtering: CF
,它基于相似用户可能更喜欢相似item
的简单想法进行预测。基于item
的协同过滤item-based collaborative filtering: Item-CF
通过考虑item
和item
之间的相似性扩展了这一思想,后来为Amazon
的推荐系统奠定了基础。最近,基于向量的推荐
vector-based recommendation
算法已经被广泛采用。主要思想是将用户和item
嵌入到相同的潜在向量空间latent vector space
中,用向量的内积来表示用户和item
之间的偏好。向量embedding
方法的典型代表有:矩阵分解matrix factorization: MF
、因子分解机factorization machines: FM
、DeepFM
、Field-aware FM: FFM
等等。然而,当
item
数量很大时,对所有item
计算内积的计算复杂度是不可行的。因此,当语料库较大时,通常使用最大内积搜索maximum inner product search: MIPS
、或者近似最近邻approximate nearest neighbor: ANN
算法来检索item
。高效的MIPS
或ANN
算法包括基于树tree-based
的算法、局部敏感哈希locality sensitive hashing: LSH
、乘积量化product quantization: PQ
、hierarchical navigable small world graphs: HNSW
等方法。尽管在实际应用中取得了成功,但是基于向量的算法有两个主要缺陷:
- 学习向量
representation
和学习良好的MIPS
结构,二者目标并不完全一致。 - 用户
embedding
和item embedding
内积的形式限制了模型的能力capability
。
为了打破这些限制,人们已经提出了基于树
tree-based
的模型。这些方法使用树作为索引indices
,并将每个item
映射为树的一个叶节点。模型参数和树结构的学习目标可以很好地对齐aligned
,从而提高准确性accuracy
。然而,树结构本身是很难学习的:叶子level
的可用数据可能很少,并且可能无法提供足够的信号来学习在该level
上表现良好的树。论文
《Deep Retrieval: An End-to-End Learnable Structure Model for Large-Scale Recommendations》
提出了一种端到端的可训练结构模型trainable structure model
--Deep Retrieval: DR
。受到
《Learning k-way d-dimensional discrete codes for compact embedding representations》
的启发,我们提出使用如下图所示的 $ D\times K $ 矩阵来索引indexing
。每个item
由一个或者多个长度为 $ D $ 、取值范围在 $ \{1,2,\cdots,K\} $ 的编码code
(或者也称路径path
)来索引indexing
。如下图所示为一个宽度为 $ K=100 $ 、深度为 $ D=3 $ 的结构。假设和巧克力相关的一个
item
由长度 $ D $ 的向量[36, 27, 20]
(称作code
或者path
)进行编码。该路径表示该item
已经分配了 $ K\times D $ 的(1,36), (2,27), (3,20)
索引indices
。图中,相同颜色的箭头形成一条路径,不同的路径可以通过在某一层layer
共享相同的索引从而彼此相交。一共有 $ K^D $ 条可能的路径,并且每条路径可以解释为一族
cluster
的item
:每条路径可以包含多个item
、每个item
也可以属于多条路径。如果添加一个虚拟的
root
节点,那么DR
就成为一棵高度为 $ D $ 的树。和TDM
不同的是:DR
中每个level
都有 $ K $ 个节点,父节点可以有多个子节点,父节点之间可以共享子节点,叶子节点不是代表一个item
而是代表一组item
。DR
有两个的优点:在训练中,可以使用
expectation-maximization: EM
类型的算法将item path
和结构模型structure model
的神经网络参数一起学习。因此,整个训练过程是端到端的,可以轻松部署到深度学习平台上。结构模型包含 $ D $ 层
layer
、每层有 $ K $ 个节点。关于结构模型我们在下面重点描述。就模型能力
model capability
方面,多对多multiple-to-multiple
编码方案使得DR
能够学习用户和item
之间更复杂的关系。实验表明了学习这种复杂关系的好处。
- 学习向量
DR
将所有候选item
编码为离散的潜在空间。这些候选item
的潜在码latent code
是模型参数,将和其它神经网络参数一起学习从而最大化相同的目标函数。在模型学习之后,我们对
latent code
进行beam search
,从而检索最佳候选item
。实验表明,DR
具有亚线性的计算复杂度,并且可以达到和暴力搜索基线brute-force baseline
几乎相同的准确性accuracy
。
9.1 模型
9.1.1 结构模型
这里我们详细介绍
DR
中的结构模型structure model
。首先,在给定模型参数 $ \theta $ 的情况下,我们构建用户 $ \mathbf{\vec x}_i $ (即用户输入特征向量)选择路径 $ \mathbf{\vec c}_i $ 的概率,并给出训练目标。
$ \mathbf{\vec c}_i $ 是一个长度为 $ D $ 的向量,每个元素 $ c_{i,d}\in \mathbb K $ 。
然后,我们引入一个多路径机制
multi-path mechanism
,使得模型能够捕获item
的多方面属性multi-aspect properties
。在推断阶段,我们引入一种
beam search
算法,根据用户embedding
选择候选路径。
结构目标函数
Structure Objective Function
:结构模型structure model
包含 $ D $ 层layer
,每层有 $ K $ 个节点。- 每层是一个带跳跃连接
skip connection
和softmax
输出的多层感知机multi-layer perceptron: MLP
。 - 每层输入一个
input vector
,并基于参数 $ \theta $ 输出在 $ \{1,2,\cdots,K\} $ 上的概率分布。
令 $ \mathbb V = \{1,2,\cdots,V\} $ 为所有
item
的索引集合, $ \mathbb K=\{1,2\cdots,K\} $ 为单个code
取值集合, 令 $ \pi: \mathbb V \rightarrow \underbrace{\mathbb K\times\cdots\times\mathbb K}_{ D } $ 为item
到路径的映射。这里我们假设 $ \pi $ 是已知的(即给定item
,对应的路径是已知的),并将在后文介绍共同学习 $ \pi $ 和 $ \theta $ 的算法。给定一对训练样本 $ \left(\mathbf{\vec x},y\right) $ ,它表示在用户 $ \mathbf{\vec x} $ 和
item
$ y $ 之间的一个positive
交互(如点击、转化、喜欢like
等等),以及给定item
$ y $ 关联的路径 $ \mathbf{\vec c}=(c_1,c_2,\cdots,c_D) $ ,其中 $ c_d\in \mathbb K $ ,概率 $ p(\mathbf{\vec c}\mid \mathbf{\vec x},\theta) $ 是按照如下方式逐层构建的(如下图(b)
所示)。第一层以用户
embedding
$ \text{emb}(\mathbf{\vec x}) $ 作为输入,基于参数 $ \theta_1 $ 输出在所有 $ K $ 个节点上的概率分布 $ p(c\mid \mathbf{\vec x},\theta_1), c=1,2,\cdots,K $ 。即:已知用户
embedding
的条件下,第一层选择 $ c_1 $ 的概率。从第二层开始,我们将用户
embedding
$ \text{emb}(\mathbf{\vec x}) $ 和所有先前层的embedding
$ \text{emb}(c_{d-1}) $ (称作path embedding
)拼接起来作为MLP
的输入,并基于参数 $ \theta_d $ 输出layer d
上 $ K $ 个节点的概率 $ p(c \mid \mathbf{\vec x},c_1,\cdots,c_{d-1},\theta_d),c=1,2,\cdots,K $ 。即:已知用户
embedding
、以及前 $ d-1 $ 层选择 $ (c_1,\cdots,c_{d-1}) $ 的条件下,第 $ d $ 层选择 $ c_d $ 的概率。概率 $ p(\mathbf{\vec c}\mid \mathbf{\vec x},\theta) $ 是所有层的概率的乘积:
$ p(\mathbf{\vec c}\mid \mathbf{\vec x},\theta) = \prod_{d=1}^D p(c_d\mid \mathbf{\vec x},c_1,\cdots,c_{d-1},\theta_d) $
给定 $ N $ 个训练样本的集合 $ \left\{(\mathbf{\vec x}_i,y_i)\right\}_{i=1}^N $ ,我们最大化结构模型
$ \mathcal Q_{\text{str}}(\theta,\pi) = \sum_{i=1}^N \log p(\mathbf{\vec c}_i=\pi(y_i)\mid \mathbf{\vec x}_i,\theta) = \sum_{i=1}^N\sum_{d=1}^D\log p(c_{i,d}\mid \mathbf{\vec x}_i,c_{i,1},\cdots,c_{i,d-1},\theta_d) $structure model
的对数似然函数:注意:
- 这里的目标函数只有
positive
交互,而没有negative
交互。但是通过softmax
函数可以引入负样本信息。 - 这里没有使用
item
的特征,仅仅将item
作为一个label
。
感觉这是一种聚类算法,基于路径来将不同的
item
进行聚类,召回时仅需要召回相应的路径即可。layer d
的输入向量的尺寸是embedding
向量尺寸乘以 $ d $ (因为 $ d $ 个embedding
向量的拼接),输出向量尺寸是 $ K $ ,因此layer d
的参数数量为 $ \Theta(Kd) $ 。参数 $ \theta $ 包含所有层的参数 $ \{\theta_d\}_{d=1}^D $ ,以及path embedding
。整个模型中的参数数量大概在 $ \Theta(KD^2) $ 的量级,这明显小于所有可能的路径的数量 $ K^D $ (当 $ D\ge 2 $ 时)。这个结构模型和典型的
DNN
推荐模型不同,该模型更偏向于GNN
图神经网络。- 每层是一个带跳跃连接
多路径结构目标
Multi-path Structure Objective
:在tree-based
深度模型以及我们之前介绍的结构模型structure model
中,每个item
只属于一个cluster
,这限制了模型在真实数据中表达多方面信息multi-aspect information
的能力。例如,一个与烤串
kebab
相关的item
应该属于一个与食物food
相关的cluster
。一个和鲜花flower
相关的item
应该属于和礼物gift
有关的cluster
。然而,与巧克力chocolate
或者蛋糕cake
相关的item
应该同时属于食物和礼物两个cluster
,以便推荐给对食物或礼物感兴趣的用户。在现实世界的推荐系统中,一个
$ \mathcal Q_{\text{str}}(\theta,\pi) = \sum_{i=1}^N \log \left(\sum_{j=1}^Jp(\mathbf{\vec c}_{i,j}=\pi_j(y_i)\mid \mathbf{\vec x}_i,\theta)\right) $cluster
可能没有明确的含义,比如食物或礼物,但是这个示例促使我们将每个item
分配给多个cluster
。在DR
中,我们允许每个item
$ y_i $ 被分配到 $ J $ 个不同的路径 $ \{\mathbf{\vec c}_{i,1},\cdots,\mathbf{\vec c}_{i,J}\} $ 。 令 $ \pi: \mathbb V\rightarrow \underbrace{\mathbb K\times\cdots\times\mathbb K}_{ D\times J } $ 为item
到multiple paths
的映射,则multiple path
结构目标定义为:这里将多个路径的概率相加,是否取
max
可能更有意义?取sum
表示用户对单个item
背后的多个概念偏好的总和,取max
表示用户对单个item
背后的多个概念偏好的最大值。针对推断的
beam search
:在推断阶段,给定用户embedding
为输入,我们希望从结构模型中检索item
。为此,我们利用beam search
算法来检索多个path
,并将检索到的path
中的item
合并。- 首先,在第一层挑选
top B
节点。 - 然后,在前一层所有节点的后续节点
successors
中挑选top B
节点。 - 最后一层输出最终的 $ B $ 个节点。
算法如下所示。在每一层中,从 $ K\times B $ 个候选节点中选择
top B
节点的算法复杂度为 $ O(KB\log B) $ 。总的算法复杂度为 $ O(DKB\log B) $ ,它相对于item
的数量是亚线性sub-linear
的。- 首先,在第一层挑选
beam search
算法:输入:
- 用户特征 $ \mathbf{\vec x} $
- 参数 $ \theta $ 的结构模型
beam size
$ B $
输出: $ B $ 条路径的集合 $ \mathbb C_D $ 。
算法步骤:
基于 $ \{p(c_1\mid \mathbf{\vec x},\theta):c_1\in \{1,\cdots,K\}\} $ 中的
top B
项挑选 $ \mathbb C_1=\{c_{1,1},\cdots,c_{1,B}\} $ 。迭代, $ \text{ for } d= 2,\cdots, D $ :
基于以下顺序,从 $ \mathbb C_{d-1} $ 集合中节点的所有后继
$ \{p(c_1,\cdots,c_{d-1}\mid \mathbf{\vec x},\theta)p(c_d\mid \mathbf{\vec x},c_1,\cdots,c_{d-1},\theta):(c_1,\cdots,c_{d-1})\in \mathbb C_{d-1}, c_d\in \{1,2,\cdots,K\}\} $successors
中挑选top B
项:然后得到集合:
$ \mathbb C_d=\{(c_{1,1},\cdots,c_{d,1}),\cdots,(c_{1,B},\cdots,c_{d,B})\} $因为 $ \mathbb C_{d-1} $ 一共 $ B $ 项,每项有 $ K $ 个后继,所以需要从 $ KB $ 项中挑选
top B
项。如果采用最大堆,则算法复杂度为 $ O(KB\times \log B) $ 。返回 $ \mathbb C_D $ 。
9.1.2 学习
前面我们介绍了
DR
中的结构模型structure model
和要优化的结构目标structure objective
。目标函数相对于参数是完全连续的,因此可以通过任何基于梯度的优化器进行优化。但是,目标函数涉及从item
到path
$ \pi $ 的映射,这是离散的,无法通过基于梯度的优化器来优化。这种映射充当
item
的 "clustering
" ,这促使我们使用EM
风格的算法来联合优化离散的映射和连续的参数。在本节中,我们将详细描述EM
算法,并引入惩罚项来防止过拟合。针对联合训练的
$ \mathcal Q_{\text{str}}(\theta,\pi) = \sum_{i=1}^N \log \left(\sum_{j=1}^Jp(\mathbf{\vec c}_{i,j}=\pi_j(y_i)\mid \mathbf{\vec x}_i,\theta)\right)\\ = \sum_{v=1}^V\left(\sum_{i:y_i=v}\log\left(\sum_{j=1}^Jp(\mathbf{\vec c}_{i,j}=\pi_j(v)\mid \mathbf{\vec x}_i,\theta)\right)\right) $EM
算法EM Algorithm for Joint Training
:给定训练集中的一个user-item
的pair
对 $ (\mathbf{\vec x}_i,y_i) $ ,令item
关联的path
为 $ \left(\left\{\pi_1(y_i),\cdots,\pi_J(y_i)\right\}\right) $ 为EM
算法中的潜在数据latent data
。连同连续参数 $ \theta $ ,目标函数由下式给出:其中第二个等式是将训练集中
item = v
的所有item
聚集在一起。我们在所有可能的映射 $ \pi $ 上最大化目标函数。然而,存在 $ K^D $ 条可能的
path
,因此我们无法在所有的 $ \pi_j(v) $ 上最大化目标函数。相反,我们仅使用beam search
来记录top path
的值,而剩下的path
为零分。不幸的是,由于上式中存在 $ \log (0) $ ,这使得函数的数值不稳定。为了解决这个问题,我们使用上限 $ \sum_{i=1}^N \log p_i\le N\left(\log \sum_{i=1}^N p_i - \log N\right) $ 来近似目标函数,从而得到:
$ \mathcal Q_{\text{str}}(\theta,\pi)\le \overline {\mathcal Q}_{\text{str}}(\theta,\pi)= \sum_{v=1}^V\left(N_v \log\left(\sum_{j=1}^J\sum_{i:y_i=v}p(\mathbf{\vec c}_{i,j}=\pi_j(v)\mid \mathbf{\vec x}_i,\theta)\right)-\log N_v\right) $其中: $ N_v = \sum_{i=1}^N \mathbb I[i:y_i = v] $ 为
item
$ v $ 出现在训练集中的次数,它独立于映射 $ \pi $ 。因为 $ \overline {\mathcal Q}_{\text{str}}(\theta,\pi) $ 是我们最大化的真实目标 $ \mathcal Q_{\text{str}}(\theta,\pi) $ 的上限,因此无法保证前者的最大化来得到后者的最大化。但是,在实践中我们发现这种近似的做法表现良好。
要使得 $ \overline {\mathcal Q}_{\text{str}}(\theta,\pi) $ 最大,则我们需要使得每个
item
$ v $ 的项 $ \sum_{j=1}^J\sum_{i:y_i=v}p(\mathbf{\vec c}_{i,j}=\pi_j(v)\mid \mathbf{\vec x}_i,\theta) $ 最大。为简单起见,我们记得分score
$ s[v,\mathbf{\vec c}] = \sum_{i:y_i=v}p(\mathbf{\vec c}=\pi(v)\mid \mathbf{\vec x}_i,\theta) $ 。在实践中不可能保留所有的得分,因为路径 $ \mathbf{\vec c} $ 的可能的数量是指数级的,所以我们通过beam search
来仅仅保留得分最大的 $ S $ 条path
的子集。$ s[v,\mathbf{\vec c}] $ 的物理意义为:所有目标
item
为 $ v $ 的、路径为 $ \pi $ 的概率之和。这里有两点注意:- 路径为 $ \pi $ 的、目标
item
为 $ v $ 的路径概率之间可能不相等,因为用户特征 $ \mathbf{\vec x}_i $ 可能不同。 - 同一个用户、目标
item
为 $ v $ 的路径概率之间也可能不等,因为存在 $ J $ 条不同的路径 $ \pi_j $ 。
在
M-step
,我们简单地在每个 $ \pi_j(v) $ 上最大化 $ \sum_{j=1}^Js[v,\pi_j(v)] $ ,这相当于在来自beam search
的top path
$ \mathbf{\vec c} $ 中挑选 $ J $ 个最高的 $ s[v,\mathbf{\vec c}] $ 分。- 路径为 $ \pi $ 的、目标
结构学习
structure learning
的EM
算法:输入:
- 训练集 $ \left\{\mathbf{\vec x}_i,y_i\right\}_{i=1}^N $
- 预定义的
epoch
数量 $ T $
输出: $ J $ 条路径 $ \left\{\pi^{(T)}_1(v),\cdots,\pi^{(T)}_J(v)\right\}_{v=1}^V $
算法步骤:
随机初始化 $ \pi_j^{(0)} $ 和 $ \theta $ 。
迭代, $ \text{ for } t=1\cdots T $ :
固定 $ \pi_j^{(t-1)} $ ,使用基于梯度的优化器优化参数 $ \theta $ ,以最大化结构目标函数
structure objective
$ \mathcal Q_{\text{str}}\left(\theta,\pi^{(t-1)}\right) $ 。$ \text{ for } v=1\cdots V $ :
- 针对
beam search
得到的top path
$ \mathbf{\vec c} $ 计算得分 $ s[v,\mathbf{\vec c}] $ 。 - 令 $ \left\{\pi^{(t)}_1(v),\cdots,\pi^{(t)}_J(v)\right\} $ 为 $ s[v,\mathbf{\vec c}] $ 中的
top
$ J $ 个得分。
- 针对
返回 $ J $ 条路径 $ \left\{\pi^{(T)}_1(v),\cdots,\pi^{(T)}_J(v)\right\}_{v=1}^V $
path size
的惩罚Penalization on Size of Paths
: 如果我们不对上述EM
算法进行任何惩罚,那么很可能发生过拟合。假设结构模型
structure model
发生过拟合,并且对于任何输入,特定的path (0,0,0)
都有非常高的概率。那么在M-step
中,所有的item
都将分配给路径(0,0,0)
,使得模型无法对item
进行cluster
。即单条路径上路径上分配了所有的
item
。为了防止过拟合,我们对
$ \mathcal Q_{\text{pen}}(\theta,\pi) =\overline {\mathcal Q}_{\text{str}}(\theta,\pi) -\alpha\times \sum_{\mathbf{\vec c}\in \mathbb R^D,\;c_i\in \mathbb K}f(|\mathbf{\vec c}|)\\ = \sum_{v=1}^V\left(N_v \log\left(\sum_{j=1}^Js[v,\pi_j(v)]\right)-\log N_v\right)-\alpha\times \sum_{\mathbf{\vec c}\in \mathbb R^D,\;c_i\in \mathbb K}f(|\mathbf{\vec c}|) $path size
引入了一个罚项。引入惩罚的 $ \mathcal Q $ 函数定义为:其中:
- $ \alpha \gt 0 $ 为惩罚因子。
- $ |\mathbf{\vec c}| $ 表示路径 $ \mathbf{\vec c} $ 中的
item
数量。 - $ f(\cdot) $ 为一个递增的凸函数。二次函数 $ f(|\mathbf{\vec c}|) = |\mathbf{\vec c}|^2/2 $ 控制
path
的平均size
。更高阶的多项式在更大的path
上惩罚更多。在我们的实验中,我们使用 $ f(|\mathbf{\vec c}|) = |\mathbf{\vec c}|^4/4 $ 。
值得一提的是,罚项仅适用于
M-step
,而不适用于训练连续参数 $ \theta $ 。针对路径分配的坐标下降算法
coordinate descent algorithm for path assignment
:在所有路径分配path assignment
上联合优化带惩罚的目标函数 $ \mathcal Q_{\text{pen}}(\theta,\pi) $ 是困难的,因为罚项不能被分解为每个item
项的求和。所以我们在M-step
中使用坐标下降coordinate descent
算法。当优化item
$ v $ 的路径分配 $ \pi_j(v) $ 时,我们固定所有其它item
的路径分配。注意,项 $ -\log N_v $ 和 $ \pi_j(v) $ 无关,因此可以删掉。对每个
$ \arg\max_{\{\pi_j(v)\}_{j=1}^J} N_v \log\left(\sum_{j=1}^Js[v,\pi_j(v)]\right) -\alpha\times \sum_{j=1}^Jf(|\pi_j(v)|) $item
$ v $ ,部分的partial
目标函数可以重写为:因为不同
item
的目标函数之间是相互独立的,因此可以拆分为每个item
的目标函数最大化。坐标下降算法如下,其时间复杂度为 $ O(VJS) $ ,其中 $ S $ 为候选路径的
pool size
。在实践中,3
到5
次迭代足以确保算法收敛。coordinate descent algorithm for penalized path assignment
算法:输入:
- 评分函数 $ \log s[v,\mathbf{\vec c}] $
- 迭代次数 $ T $
输出:路径分配 $ \left\{\pi_j^{(T)}(v)\right\}_{j=1}^J $
算法步骤:
对所有路径 $ \mathbf{\vec c} $ 初始化 $ |\mathbf{\vec c}| = 0 $ 。
迭代, $ \text { for } t =1,\cdots,T $ :
对每个
item
$ v $ 迭代:sum
设置为0
。sum
存放 $ J $ 条路径的累计评分 $ \sum_{j=1}^Js[v,\pi_j(v)] $ 。迭代, $ \text{ for } j=1,\cdots,J $ :
如果 $ t\gt 1 $ ,则更新 $ \left|\pi_j^{(t-1)}(v)\right|\leftarrow \left|\pi_j^{(t-1)}(v)\right|-1 $ 。
对
$ \tilde s[v,\mathbf{\vec c}] = \log (s[v,\mathbf{\vec c}]+\text{sum}) -\alpha\times (f(|\mathbf{\vec c}|+1) - f(|\mathbf{\vec c}|)) $item
$ v $ 的所有候选路径 $ \mathbf{\vec c} $ ,且 $ \mathbf{\vec c}\notin \left\{\pi_l^{(t)}(v)\right\}_{l=1}^{j-1} $ ,计算penalized score
:更新:
$ \pi_j^{(t)}(v)\leftarrow \arg\max_{\mathbf{\vec c}} \tilde s[v,\mathbf{\vec c}]\\ \text{sum}\leftarrow \text{sum}+s\left[v,\pi_j^{(t)}(v)\right]\\ \left|\pi_j^{(t)}(v)\right|\leftarrow \left|\pi_j^{(t)}(v)\right| +1 $
输出 $ \left\{\pi_j^{(T)}(v)\right\}_{j=1}^J $
带
softmax
模型的多任务学习和排序Multi-task Learning and Reranking with Softmax Models
:基于我们在本文中进行的实验,我们发现联合训练DR
和softmax
分类模型大大提高了性能。
$ p(y\mid \mathbf{\vec x}) = \frac{\exp\left(\mathbf{\vec x}\cdot \mathbf{\vec w}_y\right)}{\sum_{v\in \mathbb V }\exp\left(\mathbf{\vec x}\cdot \mathbf{\vec w}_v\right)} $softmax
分类模型:给定用户特征 $ \mathbf{\vec x} $ ,用户选择item
$ y $ 的概率为:其中 $ \mathbf{\vec w}_v $ 为
item
$ v $ 的embedding
。我们推测这是因为:
$ \mathcal Q = \mathcal Q_{\text{str}} + \mathcal Q_{\text{softmax}} $item
的路径在开始时是随机分配assignment
的,导致优化难度增加。通过与容易训练的softmax
模型共享输入,我们能够在优化方向optimization direction
上提升结构模型structure model
。所以我们最大化的最终目标final objective
是:这里是用两路并行模型,将它们的损失函数按照
1:1
相加。一路模型是DR
模型、另一路模型是简单的softmax
输出的DNN
模型,它们共享用户特征 $ \mathbf{\vec x} $ 。在使用
beam search
算法执行beam search
以检索一组候选item
之后,我们使用softmax
模型(即 $ \mathbf{\vec x}\cdot \mathbf{\vec w}_v $ )来重新排列这些候选item
,从而获得最终的top
候选item
。这种多任务的方式是否表明
DR
模型还不够完善,需要依赖于传统的DNN
模型。那么DR
模型的价值体现在哪里?实验部分也没有给出明确的回答。算法复杂度分析:我们将
DR
中每个阶段的时间复杂度总结如下。- 推断阶段的时间复杂度是每个样本 $ O(DKB\log B) $ 的复杂度,相对于
item
数量而言是亚线性sub-linear
的。 - 训练连续参数 $ \theta $ 的时间复杂度是 $ O(NJKD^2) $ ,其中 $ N $ 是一个
epoch
中训练样本的数量, $ J $ 是路径的多重性multiplicity
。 - 通过坐标下降算法进行路径分配的时间复杂度为 $ O(VJS) $ ,其中 $ V $ 是语料库大小, $ S $ 为候选
path
的pool size
。
- 推断阶段的时间复杂度是每个样本 $ O(DKB\log B) $ 的复杂度,相对于
未来研究方向:
- 首先,结构模型仅基于用户侧信息定义路径上的概率分布。一个有用的想法是如何将
item
侧信息更直接地整合到DR
模型中。 - 其次,我们仅利用
user-item
之间的positive
互动(如点击、转化、喜欢like
)。在将来的工作中,也应该考虑诸如non-click
、dislike
、取消关注unfollow
之类的negative
互动,从而改善模型性能。 - 最后,当前的
DR
仍然使用softmax
模型作为reranker
,这可能受到softmax
模型的性能限制。我们也在积极努力解决这个问题。
- 首先,结构模型仅基于用户侧信息定义路径上的概率分布。一个有用的想法是如何将
人们普遍认为:推荐系统不仅反映了用户的偏好,而且随着时间的推移,它们往往会重塑
reshape
用户的偏好(即,影响用户)。由于系统中的连续反馈回路continuous feedback loop
,这可能导致用户决策或用户行为的潜在bias
。我们提出的方法更多地是从改进核心机器学习技术的角度出发,基于用户历史行为数据更好地检索出最相关的候选item
。我们的方法是否放大、还是减缓了实际推荐系统中的现有bias
,这还需要进一步研究。读者注:
DR
算法本质上和TDM
算法是相同的。DR
训练算法是最大化路径的概率,如果用负采样来代替softmax
,则它就和TDM
思想一致。不同点:
TDM
模型使用attention
等复杂结构,而DR
模型仅用简单的softmax
;TDM
的负样本是每个level
中所有正样本共享的,而DR
的负样本是每个正样本独立采样的。DR
预测算法是对每一层进行beam search
,这和TDM
思想一致。不同点:二者的
score
不同。TDM
采用当前层每个节点的当前选中概率,DR
使用当前层每个节点的累积选中概率。DR
结构学习算法和TDM
不同。TDM
采用迭代来优化树结构,而DR
采用EM
算法来优化树结构。DR
采用多任务来共同学习用户representation
。
9.2 实验
这里我们研究了
DR
在两个公共推荐数据集上的性能:MovieLens-20M
和Amazon books
。我们将
DR
算法和暴力搜索brute-force
算法、以及其它一些推荐baseline
算法(包括tree-based
算法TDM
和JTM
)。最后,我们研究了重要的超参数在
DR
中的作用。数据集:
MovieLens-20M
:该数据集包含来自一个叫做MovieLens
的电影推荐服务中的评分rating
和自由文本标记free-text tagging
活动。我们使用
1995
年到2015
年之间138493
名用户的行为创建的20M
子集。每个user-movie
交互都包含一个user-id
、一个movie-id
、一个1.0~5.0
之间的评级、以及一个时间戳。为了公平地进行比较,我们严格遵循和
TDM
相同的数据预处理过程。我们仅保留评级大于等于4.0
的记录、仅保留至少十条评论的用户。经过预处理之后,数据集包含129797
名用户、20709
部电影、以及9939873
条交互记录。然后我们随机抽取
1000
个用户和相应的交互记录来构造验证集,另外随机抽取1000
个用户和相应的交互记录来构造测试集,剩余用户及其交互记录作为训练集。对于每个用户,根据时间戳将前半部分评级作为历史行为特征,后半部分评级作为待预测的ground truth
。Amazon books
:该数据集包含用户对Amazon
的books
的评论,其中每个user-book
交互都包含一个user-id
、一个item-id
、以及相应的时间戳。类似于
MovieLens-20M
,我们遵循和JTM
相同的预处理过程。数据集包含294739
名用户、1477922
个item
、以及8654619
条交互记录。注意,和Movielens-20M
相比,Amazon books
数据集具有更多的item
,但是交互更少。我们随机抽取
5000
名用户及其相应的交互记录作为测试集,另外随机抽取5000
名用户及其相应的交互记录作为验证集,剩余用户及其相应的交互记录作为训练集。对于每个用户,根据时间戳将前半部分评级作为历史行为特征,后半部分评级作为待预测的ground truth
。
评估指标:我们使用
precision, recall, F-measure
作为指标来评估每个算法的性能。我们强调,这些指标是为每个用户分别计算的,并按照
TDM
和JTM
相同的设置,在没有用户权重的情况下对所有用户进行平均。我们通过检索
MovieLens-20M
数据集中每个用户的top 10
的item
来计算指标、通过检索Amazon books
数据集中每个用户的top 200
的item
来计算指标。训练配置:这里我们提供一些关于实验中的模型和训练过程的一些细节。
由于数据集是以这样的方式进行拆分的:即训练集、验证集、测试集中的用户是不相交的,所以我们删除
user-id
,仅使用行为序列作为DR
的输入。如果行为序列长于
69
,则将其长度截断为69
;如果行为序列长度短于69
,则将其长度用占位符填充到69
。我们使用一个
GRU
的递归神经网络,来将行为序列映射到一个固定维度的embedding
上,从而作为DR
的输入。我们采用多任务学习框架
multi-task learning framework
,并且通过softmax reranker
对召回路径中的item
进行rerank
。我们在前两个
epoch
共同训练DR
和softmax
的embedding
,然后在接下来的两个epoch
中冻结softmax
的embedding
并训练DR
的embedding
。原因是为了防止softmax
模型的过拟合。在推断阶段,由于
path size
的差异,beam search
检索到的item
数量并不固定,但是方差并不太大。根据经验,我们控制beam size
,使得beam search
的item
数量是最终检索item
数量的5 ~ 10
倍。
实验结果:我们将
DR
的性能和以下算法进行比较:Item-CF
、YouTube product DNN
、TDM
、JTM
。我们直接使用来自
TDM
和JTM
论文的Item-CF
、YouTube product DNN
、TDM
、JTM
结果进行公平地比较。在不同的TDM
变体中,我们选择了性能最佳的一种来比较。JTM
的结果仅适用于Amazon books
。我们还将
DR
和暴力brute-force
检索算法进行了比较,后者直接计算用户embedding
和所有item embedding
之间的内积(这些embedding
都是从softmax
模型学到),从而返回top K item
。在实际的大型推荐系统中,暴力算法通常在计算上是不可行的,但是在小型数据集上可以作为基于内积模型的上限。下表分别给出了
MovieLens-20M
、Amazon books
数据集上DR
方法和其它方法的比较结果。对于DR
和暴力方法,我们独立地训练同一个模型5
次,并计算每个指标的均值和标准差。可以看到:DR
相比包括tree-based
的检索算法(如TDM
和JTM
)在内的所有其它方法表现更好。DR
的性能相比暴力法的性能非常接近或者不相上下。
参数敏感性:
DR
引入了一些可能显著影响性能的关键超参数,包括结构模型structure model
的宽度 $ K $ 、多路径multiple path
数量 $ J $ 、beam size
$ B $ 、以及惩罚因子 $ \alpha $ 。在
MovieLens-20M
的实验中,我们选择 $ K=50, B=25,J=3,\alpha=3\times 10^{-5} $ ;在Amazon books
的实验中,我们选择 $ K=100, B=50, J=3,\alpha=3\times 10^{-7} $ 。我们在
Amazon books
数据集研究了这些超参数的使用,并观察它们如何影响性能。我们在下图中展示了当这些超参数变化时,recall@200
指标是如何变化的(我们以recall@200
为例,precision@200
和F-measure@200
也遵循类似的趋势)。当改变一个超参数时,我们不改变其它超参数的值。模型宽度 $ K $ : $ K $ 控制了结构模型的整体容量。
- 如果 $ K $ 太小,那么对于所有
item
而言,cluster
的数量太小。 - 如果 $ K $ 太大,那么训练和推断的时间复杂度随着 $ K $ 线性增加。而且 $ K $ 太大可能会增加过拟合的可能性。
应该根据语料库的大小选择合适的 $ K $ 。
- 如果 $ K $ 太小,那么对于所有
路径数量 $ J $ : $ J $ 使模型能够表达
item
的多方面信息multi-aspect information
。$ J=1 $ 时性能最差,并随着 $ J $ 的增加而不断增加。较大的 $ J $ 可能不会影响性能,但是训练的时间复杂度随着 $ J $ 的增加而线性增加。实际上建议选择 $ J $ 在
3
到5
之间。beam size
$ B $ : $ B $ 控制召回的候选路径的数量。较大的 $ B $ 导致更好的性能,但是也会带来推断阶段更大的计算量。
惩罚因子 $ \alpha $ : $ \alpha $ 控制每个路径中的
item
数量。当 $ \alpha $ 值落在一定范围内时,性能最佳。较小的 $ \alpha $ 导致较大的
path size
(如下表所示为包含最多item
的path
(称作top path
)的path size
和惩罚因子的关系),因此在reranking
阶段计算量较大。beam size
$ B $ 和惩罚因子 $ \alpha $ 应该适当选择,从而在模型性能和推断速度之间进行权衡trade-off
。
总体而言,我们可以看到
DR
对于超参数是相当稳定的,因为超参数的范围很广wide range
,这导致了接近最优near-optimal
的性能。
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论