因子分解机(Factorization Machine, FM), 是由Konstanz大学(德国康斯坦茨大学)Steffen Rendle(现任职于Google)于2010年最早提出的,旨在解决大规模稀疏数据下的特征组合问题。

所谓的因子即潜因子(latent factors),在推荐系统中矩阵分解中常提及。ratings(n,m)评分矩阵,分解为:users(n,x) * items(x,m).

对于分类和回归问题,核心的一个问题是:特征组合。它的威力巨大。如果每个特征两两组合,n个特征下,产生的组合特征有:n * (n-1)/2。当n=100时,就有4950种. 如果每种特征以one-hot编码,每个特征的取值有100个,那这个数字又要另算了…(100 * 100 * (100 * 100-1) / 2)=5000w种了…当然,这个矩阵是稀疏的。

如果模型为多项式模型:$ y(x)=w_0+\sum_{i}^{n}{w_i}{x_i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{ij}{x_i}{x_j} $

后一项为交叉项。

本文简述下manual上的几个要点。

1.准备

1.下载、编译:https://github.com/srendle/libfm

2.编译出三个bin:

  • libFM: the libFM tool
  • convert: a tool for converting text-files into binary format , 文本转二进制工具
  • transpose: a tool for transposing binary design matrices,二进制设计矩阵转置工具

2.数据格式

libsvm sparse格式:

1
2
3
4 0:1.5 3:-7.9 
2 1:1e-5 3:2 
-1 6:1

3.格式转换

script下,内置了脚本。

推荐系统中,常见格式:

1
userid itemid rating

例如:Movielens 1M数据集:

1
./triple_format_to_libfm.pl -in ratings.dat -target 2 -delete_column 3 -separator "::"

如果同时对训练集、测试集处理:

1
./triple_format_to_libfm.pl -in train.txt,test.txt -target 2 -separator "\t"

4.二进制格式

二进制数据格式优点:

  • 1.读取快
  • 2.原始数据不能直接装进内存(太大);二进制格式可以存在磁盘上,一部分装进内存中 (使用–cache size)
  • 3.如果使用ALS 和 MCMC,可以预先计算转置矩阵

示例:将movielens数据集转换成二进制格式:

1
./convert --ifile ratings.dat.libfm --ofilex ratings.x --ofiley ratings.y

生成两个文件:

  • ratings.x: 设计矩阵X,即:要预测的变量X
  • ratings.y: 输出target:y

推荐使用这种后缀命名法。

5.转置数据

对于MCMC和ALS学习,需要使用转置的设计矩阵。

  • 如果使用文本格式,数据在内部会自动进行转置。
  • 如果使用二进制格式,进行转置。

示例:

1
./transpose --ifile ratings.x --ofile ratings.xt

6.train与test

6.1 完整参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
-cache_size     cache size for data storage (only applicable if data is
            in binary format), default=infty
-dim            'k0,k1,k2': k0=use bias, k1=use 1-way interactions,
            k2=dim of 2-way interactions; default=1,1,8
-help           this screen
-init_stdev     stdev for initialization of 2-way factors; default=0.1
-iter           number of iterations; default=100
-learn_rate     learn_rate for SGD; default=0.1
-load_model     filename for reading the FM model
-meta           filename for meta information about data set
-method         learning method (SGD, SGDA, ALS, MCMC); default=MCMC
-out            filename for output
-regular        'r0,r1,r2' for SGD and ALS: r0=bias regularization,
                r1=1-way regularization, r2=2-way regularization
-relation       BS: filenames for the relations, default=''
-rlog           write measurements within iterations to a file;
                default=''
-save_model     filename for writing the FM model
-seed           integer value, default=None
-task           r=regression, c=binary classification [MANDATORY]
-test           filename for test data [MANDATORY]
-train          filename for training data [MANDATORY]
-validation     filename for validation data (only for SGDA)
-verbosity      how much infos to print; default=0

6.2 强制参数

1
2
3
4
5
6
7
-task: 分类(-task c)或回归(-task r)
-train: 训练
-test: 测试
-dim: libfm的维度. k0, k1, k2.  
	k0: {0,1},是否使用bias: w0
	k1: {0,1},是否使用one-way interactions(每个变量都加上bias)
	k2: 实数集。使用pairwise interactions所需的因子数。k表示R^(pxk)

示例:一个回归任务,使用bias,1-way interaction, k=8 pairwise interaction.

1
./libFM -task r -train ml1m-train.libfm -test ml1m-test.libfm -dim ’1,1,8’

6.3 可选参数

1
2
3
-out:输出。对于分类,输出为正例的概率
-rlog:每次迭代的统计信息日志。csv格式
-verbosity: 是否打印更详细信息。

6.4 高级参数

Grouping

使用meta选项对输入变量进行group分组。用于MCMC, SGDA and ALS的grouping,定义了一个更复杂的正则结构。每个group都有独自的正则项参数。如要使用grouping,meta参数最好是文件名,行数与输入变量数(列)相同。每行为相应的输入变量指定groupid。注意:group_id必须是从0开始的数值型。

例如:一个设计矩阵的grouping文件,它有7列;最大id是6:

1
2
3
4
5
6
7
2
2
0
1
1
1
0

这里总共有3个组,前两个变量(设置矩阵中的列)具有相同的分组,第三个和最后一个具有相同分组;第4、5、6具有相同分组

Binary Data and Caching

对于设计矩阵,二进制的文件名以.x结尾,target以.y结尾,转置数据以.xt结尾。如果你想在libFM中使用二进制数据,训练、测试、验证时的命令行参数中文件名,则不必使用.x, .y, .xt结尾。

例如:如果你训练(ml1m-train.x, ml1m-train.y, ml1m-train.xt)和测试数据的调用(ml1m-test.x, ml1m-test.y, ml1m-test.xt):

1
./libFM -task r -train ml1m-train -test ml1m-test -dim ’1,1,8’

libFM会自动将合适的文件扩展名附加上后面进行学习。

如果你的数据太大装不进内存,你可以指定libFM允许的文件内容大小:

1
./libFM -task r -train ml1m-train -test ml1m-test -dim ’1,1,8’ -cache_size 100000000

在该例中,会使用100MB用于缓存每个.x或.xt文件。注意,.y文件总是能完整读到内存中。

如果参数cache_size没有指定,所有数据都会加载到内存中。注意:只要你的数据比内存大,你就应该使用caching;因为caching会使用硬盘,它会略比内存慢。

6.4 学习方法

缺省下,使用MCMC推断(MCMC inference)进行学习,因为MCMC最便于处理(没有学习率,没有正则项)。在LibFM中,你可以从以下的学习方法中选择:SGD, ALS, MCMC和SGDA. 对于所有学习方法,都需要指定迭代次数iter。

6.4.1 SGD

使用-method sgd即可。对于随机梯度下降法,需要指定以下参数:

  • learn_rate: 学习率,即SGD的step size,必须是非0正值
  • regular: 正则参数。非零正值。
  • init_stdev: 正态分布的标准差,它用于初始化参数V。你应使用一个非零正值

对于SGD,你需要指定以下的正则参数:

  • 1个值(-regular value): 所有模型参数都使用相同正则项
  • 3个值(-regular ‘value0,value1,value2’): 0-way interactions(w0),使用value0作为正则项;1-way interactions(w)使用value1,而pairwise interactions(V)使用value2.
  • 没有值:如果参数-regular完全没指定任何数,则对应于没有正则项。比如:-regular 0

示例:

1
2
3
4
5
6
7
8
9
./libFM -task r \
		-train ml1m-train.libfm \
		-test ml1m-test.libfm \
		-dim ’1,1,8’ \
		-iter 1000 \
		-method sgd \
		-learn_rate 0.01 \
		-regular ’0,0,0.01’ \
		-init_stdev 0.1

6.4.2 ALS

使用-method als即可做ALS学习。参数选择如下:

  • regular: 正则项,非零正值.
  • init_stdev: 正态分布的标准差,它用于初始化参数V。你应使用一个非零正值

对于ALS,你需要指定以下的正则参数:

  • 1个值(-regular value): 所有模型参数都使用相同正则项
  • 3个值(-regular ‘value0,value1,value2’): 0-way interactions(w0),使用value0作为正则项;1-way interactions(w)使用value1,而pairwise interactions(V)使用value2.
  • 分组指定值(-regular ‘value0,value1g1,…,value1gm,value2g1,…value2gm’),对于m组,存在着1+2m项正则项:如果输入参数分过组,每组的1-way和2-way interaction,都需要一个正则项.
  • 没有值:如果参数-regular完全没指定任何数,则对应于没有正则项。比如:-regular 0

示例:

1
2
3
4
5
6
7
8
./libFM -task r \
	-train ml1m-train.libfm \
	-test ml1m-test.libfm \
	-dim ’1,1,8’ \
	-iter 1000 \
	-method als \
	-regular ’0,0,10’ \
	-init_stdev 0.1

6.4.3 马尔可夫链蒙特卡尔理论(Markov Chain Monte Carlo:MCMC)

使用 -method mcmc 用作MCMC学习。参数如下:

  • init_stdev: 正态分布的标准差,它用于初始化参数V。你应使用一个非零正值

示例:

1
2
3
4
5
6
7
./libFM -task r \
	-train ml1m-train.libfm \
	-test ml1m-test.libfm \
	-dim ’1,1,8’ \
	-iter 1000 \
	-method mcmc \
	-init_stdev 0.1

6.4.4 自适应SGD(SGDA)

使用参数 -method sgda可用于SGD学习。SDGA学习中,正则项的值(每个分组和每层)会自动发现。你可以指定一个验证集,用于调整正则项:

  • validation: 该数据集用于调整正则项参数。该数据集应与训练集不重合
  • learn_rate: 学习率,即SGD的step size。它具有非零正值
  • init_stdev: 正态分布的标准差,它用于初始化参数V。你应使用一个非零正值

示例:

1
2
3
4
5
6
7
8
9
./libFM -task r \
  -train ml1m-train.libfm \
  -test ml1m-test.libfm \
  -dim ’1,1,8’ \
  -iter 1000 \
-method sgda \
-learn_rate 0.01 \
-init_stdev 0.1 \
-validation ml1m-val.libfm

7. BS扩展

  • (a)LibFM数据文件(即设计矩阵X的表示),包含了大的重复的pattern块
  • (b)LibFM的BS extension,它允许使用一个关于数据文件的更有效压缩表示,对于重复的patterns只会出现一次.

在关系设置中,设计矩阵(Design Matrix)会包含重复的patterns大块。这会产生一个很大的设计矩阵,从而使得学习变慢,并且占用大量内存。LibFM的BS扩展,允许定义和使用设计矩阵的块结构。使用BS,runtime和内存消耗都是随数据size线性增长的。更多细节详见[7].

7.1 数据格式

BS extension允许定义块(比如:上图中的B1, B2, B3),并在libFM中使用它们。每个块的定义包含这几部分:

  • 关于块的设计矩阵(上图中的X^B1)
  • 训练样例(或测试样例),映射到块中的行(例如:图中的:ø^B1)
  • 设计矩阵中,可选参数grouping

对于每个块,期望以下的文件:

1
2
3
4
5
<blockname>.x: 块的设计矩阵,二进制文件
<blockname>.xt: <blockname>.x的转置矩阵
<blockname>.train: 从train rows到block rows的映射
<blockname>.test: 与train相类似
<blockname>.groups: 可选文件,用于grouping预测变量

7.3 运行BS数据

使用命令行参数 –relation. 假设定义了两个块(rel.user和rel.item):

1
2
3
4
5
./libFM -task r \
	-train ml1m-train \
	-test ml1m-test \
	-dim ’1,1,8’ \
	--relation rel.user,rel.item

注意,对于每个块,上述列出的文件必须出现(比如:rel.user.x, rel.user.xt, rel.user.train, rel.user.test, (rel.user.groups), rel.item.x, rel.item.xt,等)

7.4 注意BS的使用

  • BS只支持MCMC和ALS/CD.
  • 当使用BS时,–train和–test参数仍是必选的,必须指定文件。libFM文件,通过–train和–test参数传递,具有预测变量,也可以是空。文件可以是二进制或文本格式。
  • BS设计矩阵的变量ids的名字空间是不一样(distinct)的。例如:在X^B1,和在X^B2的索引7的变量,是不同的。LibFM内部会给大的变量id添加offset。
  • BS文件分组的名字空间也是不一样的。每个分组文件分组从0开始,重复的解析方式与predictor variable ids相同。
  • 如果没有分组文件传进去,每个块都会自动假设它有一个不同分组

参考

  • www.libfm.org
  • [1] Chih-Chung Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. ACM Trans. Intell. Syst. Technol., 2:27:1–27:27, May 2011.
  • [2] Christoph Freudenthaler, Lars Schmidt-Thieme, and Steffen Rendle. Bayesian factorization machines. In NIPS workshop on Sparse Representation and Low-rank Approximation, 2011.-
  • [3] Thorsten Joachims. Making large-scale support vector machine learning practical, pages 169–184. MIT Press, Cambridge, MA, USA, 1999.
  • [4] Steffen Rendle. Factorization machines. In Proceedings of the 10th IEEE International Conference on Data Mining. IEEE Computer Society, 2010.
  • [5] Steffen Rendle. Factorization machines with libFM. ACM Trans. Intell. Syst. Technol., 3(3):57:1– 57:22, May 2012.
  • [6] Steffen Rendle. Learning recommender systems with adaptive regularization. In WSDM ’12: Pro- ceedings of the third ACM international conference on Web search and data mining, New York, NY, USA, 2012. ACM.
  • [7] Steffen Rendle. Scaling factorization machines to relational data. In Proceedings of the 39th in- ternational conference on Very Large Data Bases, PVLDB’13, pages 337–348. VLDB Endowment, 2013.
  • [8] Steffen Rendle, Zeno Gantner, Christoph Freudenthaler, and Lars Schmidt-Thieme. Fast context- aware recommendations with factorization machines. In Proceedings of the 34th ACM SIGIR Con- ference on Reasearch and Development in Information Retrieval. ACM, 2011.

libfm方面,其它推荐好文:

介绍

FM(Factorization Machines)是一个新模型:它会结合SVM和因子分解模型的优点。FM是一个通用预测器,可以很好地与实数值特征向量一起工作。对比SVM,FM模型会使用因子分解参数来对变量进行交叉。因而,我们可以估计推荐系统中海量稀疏性(huge sparsity)问题中的交叉(这种情况SVM会失败)。我们展示了FM的模型等式,它可以在线性时间内计算,因而FM可以直接进行最优化(optimize)。不同于非线性SVM需要以对偶式做转换,FM可以直接估计模型参数,无需求解任何支持向量(support vector)。本paper也展示了FM和SVM的关系,以及FM在稀疏(sparse)环境下的参数估计的优点。

另一方面,有许多不同的因子分解模型,比如:矩阵分解,并行因子分析模型(如:SVD++,PITF or FPMC)。这些模型的缺点是,不能应用于常见的预测任务(但对于一些特殊的输入数据管用)。这些模型等式和优化算法对于每个任务各不相同。我们展示了FM可以模仿这些模型,只需要指定输入数据(即:特征向量)即可。这让FM很容易使用,即使是对于那些在因子分解模型没有专家经验的用户。

1.介绍

SVM是最流行的预测器之一。然而,在协同过滤领域,SVM基本上毫无用武之地,该领域最好的模型是标准的矩阵/张量分解模型(matrix/tensor factorization model),比如:PARAFAC或者使用因子分解参数的特殊模型[2][3][4]。在本paper中,我们展示了为什么标准的SVM预测器在这些任务上不能成功的原因:在非常sparse的数据上,不能在复杂(非线性)kernel spaces上学到可靠的参数(超平面)。另一方面,张量分解模型的缺点是:

  • (1) 它们不能应用于标准的预测数据(比如:在$R^n $ 空间中的实数值特征向量)
  • (2) 对于特定的任务,需要在建模和算法设计时进行单独构建

在本paper中,我们引入了一个新的预测器,Factorization Machine(FM),它是一个通用的预测器(类似于SVM),但也能在高度稀疏(sparsity)的数据下估计得到可靠参数。FM模型所有都嵌套着变量交叉(对比:在SVM中通过一个polynomial kernel),但它会使用一个因子分解参数( factorized parametrization)的方法,而非SVM中的dense参数化(dense parametrization)。我们展示了FM的模型等式,它可以在线性时间内计算,只依赖于一个线性数量的参数。这允许直接优化和模型参数存储,无需存储任意训练中数据(比如:支持向量)来进行预测。对比于FM,非线性SVM通常以对偶形式(dual form)进行优化,依赖于训练中数据(支持向量)来计算预测。我们也展示了,FM把许多对于协同过滤任务的成功方法(biased MF, SVD++, PITF, FPMC)包含在内。

总之,我们提出的FM的优点有:

  • 1) FM允许在非常sparse的数据(SVM会失败)上进行参数估计
  • 2) FM具有线性复杂度,可以以原始形式优化,不需要依赖像SVM中的支持向量(SV)。我们展示了FM可以扩展到大数据集上(比如:Netflix 1000w训练实例)
  • 3) FM是一个通用预测器,可以与任意实数型特征向量(real valued feature vector)一起工作。对比于FM,其它state-of-art的因子分解模型非常受限于输入数据。我们将展示通过定义输入数据的特征向量,FM可以模仿state-of-the-art的模型(biased MF, SVD++, PITF, FPMC)。

2.sparsity下的预测

最常见的预测任务是:估计一个函数:

从一个实数值特征向量 ,到一个目标域T(比如:对于回归, T=R;对于分类,T={+, -})。

在监督学习领域,假设存在一个训练样本数据集:,y为目标函数(target function)。我们也研究了排序任务,其中函数y的目标 T=R 可以被用于得分特征向量(score feature vectors)x,可以根据score进行排序。得分函数(score functions)可以通过pairwise的训练数据进行学习得到,其中特征tuple 意味着的排序比更高。由于pairwise的排序关系是不对称的(antisymmetric),只使用正例进行训练就足够了。

在本paper中,我们处理该问题,其中x是高度稀疏的(比如:向量x中几乎大多数元素都是0)。假设m(x)是特征向量x中非零元素的数目,是所有向量 的m(x)的平均非零元素个数。现实世界中十分稀疏(huge sparsity )的情况很常见(),比如事件交互(推荐系统中的购买),或者文本分析(bag-of-word方法)。huge sparsity的一个原因是,需要处理海量的类别型变量域。

示例1:假设我们具有一个电影评论系统的交互数据。该系统记录了:用户对一部电影的评分,时间为,评分为。假设用户U和item I如下:

U = {Alice (A), Bob (B), Charlie (C), . . .}

I = {Titanic (TI), Notting Hill (NH), Star Wars (SW), Star Trek (ST), . . .}

观察到的数据S:

S = {(A, TI, 2010-1, 5),(A, NH, 2010-2, 3),(A, SW, 2010-4, 1), (B, SW, 2009-5, 4),(B, ST, 2009-8, 5), (C, TI, 2009-9, 1),(C, SW, 2009-12, 5)}

对于一个使用该数据的预测任务,目标是估计一个函数来预测:在某个时间点上,一个用户对一个item的评分行为。

图一:示例1的交互所创建的稀疏实数特征向量x。每一行表示了一个特征向量,以及它对应的目标,前4列(蓝色)表示用户的指示变量:接下来的5列(红色)表示item的指示变量。接下来的5列(黄色)持有着额外的隐式指示(比如:该用户评过分的其它电影)。一个特征(绿色)表示了月份时间。最后的5列(棕色)表示在该电影前评过分的最后一部电影。最右边的列是target:这是评分。

图1展示了特征向量是如何从S中被创建的。首先,是个二元变量(蓝色),它表示了一个交互的当前用户————通常对于一个交互只有一个用户,例如:在第一个( )的用户Alice。下一个二元变量(红色)持有着item(例如:)。图1的特征向量还包含了该用户评分过的其它电影(黄色)。对于每个用户,变量被归一化成总和为1. 例如:Alice评分了Titanic,Notting Hill和 Star Wars。另外,该样本包含了月份时间。最后,该向量包含了评分前最后一部电影的信息。例如,对于,Alice在对Notting Hill评分前,就对Titanic进行了评分。在第V节,我们展示了FM使用这样的特征向量作为输入数据,并与state-of-art算法进行比较。

我们将使用该样本数据进行本paper的演示。然而,注意FM是通用的预测器,任何实数型特征向量都可以使用,并不局限于推荐系统。

3.FM

在本节中,我们引入了因子分解机(FM)。我们详细讨论了模型等式,简短展示了如何应用FM到一些预测任务上。

A.FM模型

1)模型等式(Model Equation):阶(degree)为2,定义如下:

…(1)

其中,要估计的模型参数是:

…(2)

其中<.,.>是两个size=k的向量的点乘:

…(3)

在V中的一行描述了具有k个因子的第i个变量。是一个超参数,它定义了因子分解的维度。

一个2-way FM(degree d = 2)捕获了所有变量间的single和pairwise交叉:

  • 是全局bias
  • 建模了第i个变量的权重
  • 建模了第i个和第j个变量间的交叉(interaction)。FM模型不会为每个交叉使用单独的模型参数,作为替代,FM模型通过对它进行因子分解(factorizing)来对交叉进行建模。稍后我们可以看到,对于稀疏的高阶交叉(d>=2)允许高质量参数估计,这就是其关键点。

2) 表现力(Expressiveness):我们都知道:当k足够大时,对于任意正定矩阵W(positive definite matrix),存在一个矩阵V,使得 (Cholesky decomposition)。这表明:当k足够大时,一个FM可以表示任意交叉矩阵W。然而在稀疏情况下,通常会选择一个小k,因为没有足够多的数据来估计复杂交叉W。限制k(也就是限制FM的表现力),可以产生更好的泛化,这样可以提升稀疏情况下的交叉矩阵。

3)稀疏条件下的参数估计:在sparse情况下,通常没有足够多的数据来直接地、独立地估计变量间的交叉(interactions)。FM可以在这样的情况下很好地估计交叉,因为他们通过对它们进行因子分解分离出交叉参数的独立性。总之,这意味着,对于一次交叉的数据可以帮助估计相关交叉的估计。以下的示例会利用来自图1的数据,使该思想更清晰。

假设:我们希望估计在Alice(A)和Star Trek(ST)间的交叉,来预测目标y(即rating)。很明显,在训练数据中,没有这样的样本x,同时满足都是非零的,因而一个直接的估计是没有交叉()。但是,这种情况下的因子分解的交叉参数是可以估计的。首先,Bob和Charlie具有相似的因子向量(factor vector),因为对于预测评分来说,两人与Star Wars()的交叉相似:必须相似。相比之下,Alice()和Charlie()之间会具有不同的因子向量(factor vector),因为在评分上,Alice与Titanic 和 Star Wars的因子也存在不同的交叉。另外,Star Trek的因子向量可能与Star Wars的相似,因为对于预测y来说,Bob与这两部电影具有相同的交叉。总之,这意味着,Alice和Star Trek的因子向量点积(交叉) ,将与Alice和Star Wars的因子向量点积相似——这在直观上是说得通的。

4)计算

接着,我们将展示如何从计算角度来让FM可用。等式(1)的计算复杂度是,因为所有pairwise交叉必须被计算。但是,用公式重新表示会下降到线性运行时(linear runtime)。

引理3.1:FM的模型等式(1)可以以线性时间O(kn)被计算。

证明:由于pairwise型交叉(interaction)的因子分解,不存在直接依赖这两个变量的模型参数(例如:一个带有索引(i,j)的参数)。因而,pairwise的交叉可以重新进行公式化:

该等式具有O(kn)的线性复杂度

再者,在sparsity情况下,x中的大多数元素为0(例如:m(x)很小),因而,该求和可以通过非零元素的计算来得到。在sparse应用中,FM的计算复杂度为,例如:,对于常见的推荐系统,比如MF方法。

B.FM作为预测器

FM可以应用到许多预测任务中。比如:

  • 回归:可以直接用于预测,最优化准则可以是在D上最小化square error。
  • 二元分类:,最优化准则可以使用hinge loss或者logit loss。
  • 排序(Ranking):向量x会通过的得分进行重新排序,最优化通过实例向量对,根据pairwise classification loss进行分类。

在所有的case中,正则项L2通常被添加到目标函数上来进行优化来阻止overfit。

C.FM的学习

FM具有一个封闭(closed)的模型等式,可以在线性时间上计算。这样,FM的模型参数(w0, w和 V)——可以有效地通过梯度下降法学到。——例如SGD,计算square, logit or hinge loss。FM模型的梯度如下:

…(4)

是与i独立的,可以预计算(例如:当计算 时)。总之,每个梯度都可以在常数时间内被计算。对于(x,y)的所有参数更新可以在O(kn)——或者稀疏情况下O(km(x))时间内完成。

我们提供了一个泛化实现,LibSVM,使用SGD,并支持element-wise和pairwise loss。

D.d-way FM

2-way FM可以很容易泛化到d-way Fm上:

…(5)

其中,l次交叉的交叉参数可以通过使用以下模型参数的PARAFAC模型进行因子分解:

…(6)

等式(5)的计算复杂度为 。但与引理3.1有相近的参数,可以看到在线性时间内被计算。

E.总结

FM模型在特征向量x中的值之间所有可能的交叉,使用因子分解交叉(factorized interactions),而非完全参数化交叉(full parametrized)。这主要有两个优点:

  • 1) 即使很稀疏,值之间的交叉可以被估计。尤其是,它可以泛化到未观察到的交叉
  • 2) 参数的数目对于预测和训练时间是线性的。这可以使用SGD直接进行最优化,并可以使用多种loss。

与其它模型的对比

详见paper,此处不介绍.

https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf

本文是youtube在2010年提出的系统,现在回过头去看看它在当时是如何实现youtube的推荐系统的。

系统设计

推荐系统的整个设计都围绕以下的目标:我们希望相应的推荐(recommendations)是适度最新的(recent)、新鲜的(fresh),多样化的(diverse),并且与用户最近的动作有相关性(relevant)。另外,重要的一点是,用户能理解为什么某个视频会被推荐给他们

推荐的视频集合通过使用一个用户的个性化行为(观看,收藏,喜欢)来生成作为种子,然后通过基于视频图的co-visitation对集合进行扩展。该视频集接着使用多个信号为相关性(relevance)和多样性(diversity)进行排序

从工程的角度看,我们希望系统的单个组件相互解耦,允许它们进行独立的调试,以便容错,降低系统的整体复杂度。

1.输入数据

在个性化视频推荐的生成期间,我们会考虑多个数据源。总之,有两大类的数据要考虑:

  • 1)内容数据(content data),比如原始视频流和视频元信息(标题,简介等)
  • 2)用户行为数据(user activity data),可以进一步分类为显式和隐式。显式行为包括:对一个视频进行打分(rating),进行收藏/喜欢,或者订阅了某个上传者。隐式行为包括:观看、交互,比如:用户开始观看一个视频,用户观察了某个视频的大部分(长播放行为:long watch)

在所有的case中,数据的处理noisy很多:视频元信息可以不存在,不完整,过期,或者不正确;用户数据只捕获了在网站端的一部分用户行为,只能间接衡量一个用户的参与度(engagement)和高兴度(happiness),比如:用户完整地观看一个视频,不足够说明她确实喜欢这个视频。视频的长度和用户的参考程度,受信号质量的影响。再者,隐式行为数据是异步生成的,可能不完整,比如:在我们接受到一个long-watch通知前,用户可能已经关闭了浏览器。

2.相关视频

推荐系统的一个构建块是:构造一个映射(mapping),将一个视频$ v_i $映射到一个相似(similar)或相关(related)的视频集合$ R_i $上。在该上下文上,我们定义了相似视频:在观看了给定的种子视频v(seed video)后,一个用户会喜欢继续观看这些视频集。为了计算该mapping,我们使用了一些著名的技术:关联规则挖掘(association rule mining)、或者 co-visitation counts。让我们来看下:用户在网站上观看行为的session。对于给定的时间周期(24小时),我们会统计每对视频对(video pair):$(v_i,v_j)$,在session内被同时观看(co-watch)的次数。将该co-visitation count置为$ c_{ij} $,我们定义了视频$ v_j $基于视频$ v_i$的相关得分:

…(1)

其中,$c_i$和$ c_j $是所有session上视频$v_i$和$ v_j$各自的总共现次数。$ f(v_i,v_j)$是一个归一化函数,它会考虑种子视频和候选视频的“全局流行度(global popularity)“。一种最简单的归一化函数是,简单地除以视频的全局流行度的乘积:$f(v_i,v_j)=c_i \cdot c_j $。也可以选择另一种归一化函数。见paper[6]。当使用候选的简单乘积进行归一化时,$c_i$对于所有的候选相关视频是相同的,可以在我们的设置(setting)中忽略。这本质上会在流行视频中支持更低流行度的视频。

对于一个给定的种子视频$v_i$,我们接着选取相关视频$R_i$的集合,通过它们的得分$r(v_i,v_j)$进行排序,选取topN个候选视频。注意:除了只选取topN个视频外,我们也加入一个最低的得分阀值(minimum score threshold)。因而,对于许多视频,我们不能计算一个可靠的相关视频集合,因为它们整体的观看量(view count:与其它视频的co-visitation counts)很低。

注意,这是一个简化版的描述。实际上,还存在额外的问题需要去解决——表示偏差(presentation bias),噪声观看数据(noisy watch data),等————在co-visitation counts之外的额外数据源,也可以被使用:视频播放的sequence和time stamp、视频元信息等等。

相关视频可以被看成是在视频集上引导成一个直连图(directed graph):对于每个视频对$(v_i,v_j)$,从$v_i$到$v_j$上有一条边(edge) $ e_{ij} $,如果$v_j \in R_i $,该边的权重由等式(1)给定。

3 生成推荐候选

为了计算个性化推荐,我们将相关视频的关联规则,以及一个用户在网站上的个人行为相结合:它包括被观看的视频(超过某个固定阀值),以及显式收藏(favorited)、喜欢(liked)、打分(rated)、添加到播放列表(added to playlists)的视频。我们将这些视频集合称为种子集(seed set)

对于给定的种子集合S,为了获取候选推荐,我们将它沿着相关视频图的边进行扩展:对于种子集合里的每个视频$v_i$,会考虑它的相关视频$ R_i $。我们将这些相关视频集合的合集(union)表示为$C_1$:

…(2)

在许多情况下,计算$C_1$对于生成一个候选推荐集合是足够的,它足够大并且足够多样化来生成有趣的推荐。然而,实际上任何视频的相关视频的范围都趋近于狭窄(narrow),经常会突显(highlighting)出那些与种子视频相似的视频。这会导致范围相当狭窄的推荐(narrow recommendation),它确实会让推荐内容与用户兴趣接近,但对于推荐新视频给用户时会很失败。

为了扩大推荐的范围,我们通过在相关视频图上采用一个有限的传递闭包(limited transitive closure),来扩展候选集。$C_n$被定义成这样的视频集合,它从种子集合中的任意视频在距离n内可达

…(3)

其中$ C_0=S $是该递归定义中的base case(注意:它会为$C_1$产生一个与等式(2)的同等定义)。最终的候选集合$C_{final}$接着被定义成:

…(4)

由于相关视频图的高分支因子(high branching factor),我们发现,在一个较小的距离上扩展,可以产生一个更宽更多样的推荐集合,即使用户只有一个小的种子集合。注意:候选集中的每个视频,与种子集合中一或多个视频有关联。为了进行ranking,我们继续跟踪这些种子与候选的关联,并为推荐给用户提供解释。

4.Ranking

在生成阶段,已经产生了候选视频,它们使用许多信号进行打分和排序。这些信息可以根据ranking的三个不同阶段归类成三组:

  • 1)视频质量(video quality)
  • 2)用户特征(user specificity)
  • 3)多样化

视频质量信号,是指在不考虑用户的情况下,判断视频被欣赏的似然(likelihood)。这些信息包括:观看量(view count: 一个视频被观看的总次数),视频的评分,评论,收藏,分享行为,上传时间等。

用户特征信号,用于增强一个视频与某个用户特有的品味和偏好相匹配。我们会考虑种子视频在用户观看历史中的属性,比如:观看量(view count)、观看时长(time of watch)。

通过使用这些信号的一个线性组合,我们为这些候选视频生成了一个排序列表。因为,我们只会展示少量的推荐(4到60之间),我们必须选择列表的一个子集这里不必选择最相关的视频,我们会在相关性和跨类目多样性上做一个平衡优化。因为一个用户通常在不同时刻会在多个不同的主题上有兴趣,如果视频相互间太相似会在该阶段会被移除,以便增加多样性。解决该问题的一种简单方法是,限制单个种子视频的相关推荐数目,或者限制相似频道(channel/uploader)的推荐个数。更复杂的方式是基于主题聚类,或是进行内容分析。

5.UI

推荐的表示在整个用户体验上是很重要的一环。图1展示了推荐是如何在youtube主页上进行表示的。有少量新特性需要注意:首先,所有的推荐视频使用一个缩略图(thumbnail)、标题、视频时间、流行度进行展示。这与主页上的其它部分相类似,可以帮助用户快速决定是否对一个视频有兴趣。再者,我们添加了一个带有种子视频链接(它触发了推荐)的解释(explanation)。最后,我们给出了用户控制,可以看到在主题上有多少个推荐。

在ranking那一节,我们计算了一个推荐的排序列表,但在serving time只会展示其中一个子集。这允许在每次用户到达网站时提供新的、之前未看过的推荐,即使底层的推荐没有被重新计算。

6.系统实现

我们选择一种面向批处理的预计算方式(batch-oriented pre-computation approach),而非按需计算。这样做的优点是:推荐生成阶段访问大量数据会使用大量CPU资源,而在serving时预生成的推荐项可以有极低的访问延时。该方法最大的缺点(downside)是,在生成(generating)和(serving)一个特定的推荐数据集间的delay。我们缓和了这个现象,通过对推荐生成进行pipelining,每天更新数据集多次。

youtube推荐系统的实际的实现被分为三个主要部分:

  • 1)数据收集
  • 2)推荐生成
  • 3)推荐serving。

之前提到的原始数据信号存放在YouTube的log中。这些log会被处理,提取信号,按每用户为基础保存到BigTable中。当前处理数百万的用户和上百亿的行为事件,总的footprint为TB级别。

推荐的生成通过MapReduce计算完成,它会在user/video graph上进行walk through,来累积和计分推荐项。

生成的数据集的size相当小(GB),可以很容易通过webserver进行serving。完成一个推荐的请求时间几乎由网络传输时间决定。

评估

通过A/B testing进行在线评估,真实流量分成不同的组,其中一组作为control或baseline,其它组给新特性、新数据、或新UI。两组接着进行对比。为了评估推荐质量,我们使用不同metrics的组合。主要的metrics包括CTR,long CTR(只统计点击导致观看一个视频的大部分观看行为),session length,首次long watch的时间(time until first long watch),推荐覆盖率(coverage)。我们使用这些metrics来跟踪系统的效果。

The YouTube Video Recommendation System

二次规划(Quadratic Programming)问题是最基本的非线性规划问题,目标函数是二次函数,约束条件是线性等式或不等式。目前,已经出现了很多求解二次规划问题的算法,并且仍有很多学者在从事这方面的研究工作。

在机器学习中,我们知道QP可以用来解决SVM算法的最优解问题。二次规划问题的求解证明在此处暂不讨论。

二次规划的问题可以用数学公式(octave)描述:

1
2
3
4
5
6
7
8
 min 0.5 x'*H*x + x'*q
  x

    subject to

      A*x = b
      lb <= x <= ub
      A_lb <= A_in*x <= A_ub

相应的函数为:

  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB, A_LB, A_IN, A_UB)
  • Function File: [X, OBJ, INFO, LAMBDA] = qp (…, OPTIONS)

其中,H,q分别是目标函数化成标准形式后得到的实对称矩阵,列向量。求解的目标,x。A,b定义了线性约束。如果没有线性约束,A=[],b=[]。LB,UB分别是变量x的下界和上界,如果上界、下界没有约束,则LB=[],UB=[]。可以通过OPTIONS设置其它参数:比如:

‘MaxIter (default: 200)’

INFO表示算法的运行时信息。相应如下:

  • ‘solveiter’: 解的迭代数
  • ‘info’: 状态码。
  • info=0: 表示该问题是可行的,并且是convex问题。找到全局解。
  • info=1: 该问题是not convex的。找到局部解。
  • info=2: 该问题是not convex的,并且unbounded。
  • info=3: 迭代的最大次数
  • info=6: 该问题无解

示例:

  • $ min f(x)=2x_1^2-4x_1x_2+4x_2^2-6x_1-3x_2 $
  • $ x_1+x_2<=3 $
  • $ 4x_1+x+2<=9 $
  • $ x_1\geq0,x_2\geq0 $

编写程序:

H=[4,-4;-4,8];
Q=[-6;-3];
A=[1,1;4,1];
B=[3;9];
LB=zeros(2,1);
X0=[];
UB=[];
[X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB)

对应的输出为:

X =

   2.0000
   1.0000

OBJ = -11.000
INFO =

  scalar structure containing the fields:

    solveiter =  1
    info = 0

LAMBDA =

  -3.33333
   0.33333
   0.00000
   0.00000
   

这个标题起的有点大.

国内有许多做的还算不错的、各式各样的数据分析公司。如艾瑞,友盟等等之类的。在现在的大数据概念炒得火热的背后,其实它们的运作原理基本都差不多。

一切皆围绕数据去展开。那么数据是怎么来的呢?大致的数据来源基本上有这么几种,将分别说:

第一招:提供数据统计接口,有各种各样的API:各种编程语言的如JS/php/python/java、android/ios等等。当第三方的APP不希望单独花精力去维护一个数据分析平台时,那么很自然的,它们会选择这样的接口。这样数据自然地也被这些数据分析平台公司获取到了。那么有没有可能获取到该APP之外其它的一些信息呢?当然可以,由于android平台的安全性,这些公司一些接供的接口完全可以留下后门,当程序启动时,留下后台进程常驻(非360之类的工具也你真杀不掉)。ok,一个用户的其它移动非加密数据很有可能会被人家拿到了。ios则比较安全,8.0以上的版本基本无解。当然,还有一批越狱用户,这批用户的数据也是能拿到的。(别叫我流氓,这是行情潜规则)

第二招:还可以第三方合作。这一招也可以称为“空手套白狼”。中国的互联网环境竞争激烈,竞品太多。各种各样的公司很自然的会关注对手的情况。只要能和一家公司合作,那么很自然的,围绕对手想看这家公司的数据的问题,很自然地,可以和它相应的对手也开展这样的合作。这样,这个雪球也会越滚越大。

第三招:其它途径呢:花钱呗!付费招募。

第四招:还可以运营商(电信、移动、联通)合作。很自然地可以获取运营商根服务上的相关数据。比较某些特定用户访问某些站点的明文get数据(post无解)。

ok,数据有了。虽然可以拿到许多数据了。不过貌似不全,一家公司如果想让我做个分析研究肿么办。没关系,我们的“大数据”是吹出来的。(数据部分伪造,可以拿一些专业的互联网分析报告展开)

运营商 比例
移动 62.22%
联通 17.78%
电信 14.00%

我们接着看地域数据:

地区 比例
其它 18.00%
广东 13%
浙江 7%
北京 7%
江苏 6%
河南 6%
山东 5%
河北 5%
四川 4%
湖南 4%
湖北 3%
福建 3%
天津 3%
陕西 3%
辽宁 3%
上海 3%
山西 3%

还有操作系统的数据比例:

操作系统 比例
IOS 22%
Android 78%

ok,有了这些数据信息。那么我们就可以按比例去构建这样的大样本集。根据这样的大样本集去推演出真实的大致数据的分析即可。现在,就可以做各种各样的分析了:路径分析、个性化指标分析、转化率分析等等。

当然最重要的,是赚钱。有了一些行业内比较重量级的报告,那么就可以收费啦:一个app一个月就要10几w块钱。商业模式自然滚动起来啦。

由此看,这些数据分析公司中,抽样与统计占着相当重要的作用。