因子分解机(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格式：

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

3.格式转换

script下，内置了脚本。

推荐系统中，常见格式:

userid itemid rating

例如：Movielens 1M数据集：

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

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

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

4.二进制格式

二进制数据格式优点：

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

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

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

生成两个文件：

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

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

5.转置数据

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

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

示例：

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

6.train与test

6.1 完整参数

-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 强制参数

-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.

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

6.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：

这里总共有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）：

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

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

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

./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

示例：

./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

示例：

./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。你应使用一个非零正值

示例：

./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。你应使用一个非零正值

示例：

./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

对于每个块，期望以下的文件：

<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）：

./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方面，其它推荐好文：

libfm 1.4.2 manual

September 23, 2014