alphaFM

前言：

alphaFM是Factorization Machines的一个单机多线程版本实现，用于解决二分类问题，比如CTR预估，优化算法采用了FTRL。 FTRL是一种online learning算法，在Google于2013年给出的论文中用于解决LR的优化，但其实FTRL是一种通用的优化算法，同样可以用于FM。
算法原理见我的博客文章：http://castellanzhang.github.io/2016/10/16/fm_ftrl_softmax/
在最早写此代码时，正值alphaGo完虐人类，便随手给其取名曰alphaFM。
实现alphaFM的初衷是解决大规模数据的FM训练，在我们真实的业务数据中，训练样本数常常是千万到亿级别，特征维度是百万到千万级别甚至上亿，这样规模的数据完全加载到内存训练已经不太现实，甚至下载到本地硬盘都很困难，一般都是经过spark生成样本直接存储在hdfs上。
alphaFM用于解决这样的问题特别适合，一边从hdfs下载，一边计算，一个典型的使用方法是这样：
训练：10个线程计算，factorization的维度是8，最后得到模型文件fm_model.txt
hadoop fs -cat train_data_hdfs_path | ./fm_train -core 10 -dim 1,1,8 -m fm_model.txt
测试：10个线程计算，factorization的维度是8，加载模型文件fm_model.txt，最后输出预测结果文件fm_pre.txt
hadoop fs -cat test_data_hdfs_path | ./fm_predict -core 10 -dim 8 -m fm_model.txt -out fm_pre.txt
当然，如果样本文件不大，也可以先下载到本地，然后再运行alphaFM。
由于采用了FTRL，调好参数后，训练样本只需过一遍即可收敛，无需多次迭代，因此alphaFM读取训练样本采用了管道的方式，这样的好处除了节省内存，还可以通过管道对输入数据做各种中间过程的转换，比如采样、格式变换等，无需重新生成训练样本，方便灵活做实验。
alphaFM还支持加载上次的模型，继续在新数据上训练，理论上可以一直这样增量式进行下去。
FTRL的好处之一是可以得到稀疏解，在LR上非常有效，但对于FM，模型参数v是个向量，对于每一个特征，必须w为0且v的每一维都为0才算稀疏解，但这通常很难满足，所以加了一个force_v_sparse的参数，在训练过程中，每当w变成0时，就强制将对应的v变成0向量。这样就可以得到很好的稀疏效果，且在我的实验中，发现最终对test样本的logloss没有什么影响。
当将dim参数设置为1,1,0时，alphaFM就退化成标准的LR的FTRL训练工具。
当前版本在v1.0.0基础上做了如下优化，具体见：http://castellanzhang.github.io/2018/09/01/memory_optimization_for_alphafm/ ，注意：当前版本只在Linux x86_64系统上通过g++编译测试过，其他环境不保证能够成功编译以及成功执行：
- 内存优化，相比v1.0.0，fm_train在不改变任何运行参数的情况下内存占用能降到1/3左右，具体降幅取决于特征数据以及-dim参数；fm_predict内存占用降幅更为明显。内存优化带来的益处是显著的，比如对于我们一个典型的应用场景：单机128G内存训练LR模型，可以从原来支持3亿左右的特征维度提升到支持10亿左右。
- 增加-mnt参数，可以指定内存中模型参数的类型为double还是float，当指定为float时能够进一步降低内存占用，但可能对模型效果有一定影响，谨慎使用。
- 模型文件可以选择指定为二进制格式，模型加载和输出的速度可以带来10倍量级的提升。
- 增加模型格式转换工具model_bin_tool，可以输出二进制模型相关信息，可以相互转换二进制模型和文本模型，从二进制转为文本格式时可以选择只保留非0特征。

安装方法：

直接在根目录make即可，编译后会在bin目录下生成三个可执行文件。如果编译失败，请升级gcc版本。

输入文件格式：

类似于libsvm格式，但更加灵活：特征编号不局限于整数也可以是字符串；特征值可以是整数或浮点数（特征值最好做归一化处理，否则可能会导致结果为nan），特征值为0的项可以省略不写；正负label可以是1/0或者1/-1。举例如下：
1 sex:1 age:0.3 f1:1 f3:0.9
0 sex:0 age:0.7 f2:0.4 f5:0.8 f8:1
...

txt模型文件格式：

第一行是bias的参数：
bias w w_n w_z
其他行的格式为：
feature_name w v1 v2 ... vf w_n w_z v_n1 v_n2 ... v_nf v_z1 v_z2 ... v_zf

预测结果格式：

label score
其中label为1或-1，score等于预测为正样本的概率值。

参数说明：

fm_train的参数：

-m <model_path>: 设置模型文件的输出路径。
-mf <model_format>: 设置模型文件的输出格式，txt（文本）或bin（二进制）。 default:txt
-dim <k0,k1,k2>: k0为1表示使用偏置w0参数，0表示不使用；k1为1表示使用w参数，为0表示不使用；k2为v的维度，可以是0。 default:1,1,8
-init_stdev <stdev>: v的初始化使用均值为0的高斯分布，stdev为标准差。 default:0.1
-w_alpha <w_alpha>: w0和w的FTRL超参数alpha。 default:0.05
-w_beta <w_beta>: w0和w的FTRL超参数beta。 default:1.0
-w_l1 <w_L1_reg>: w0和w的L1正则。 default:0.1
-w_l2 <w_L2_reg>: w0和w的L2正则。 default:5.0
-v_alpha <v_alpha>: v的FTRL超参数alpha。 default:0.05
-v_beta <v_beta>: v的FTRL超参数beta。 default:1.0
-v_l1 <v_L1_reg>: v的L1正则。 default:0.1
-v_l2 <v_L2_reg>: v的L2正则。 default:5.0
-core <threads_num>: 计算线程数。 default:1
-im <initial_model_path>: 上次模型的路径，用于初始化模型参数。如果是第一次训练则不用设置此参数。
-imf <initial_model_format>: 初始化模型文件的格式，txt（文本）或bin（二进制）。 default:txt
-fvs <force_v_sparse>: 为了获得更好的稀疏解。当fvs值为1, 则训练中每当wi = 0，即令vi = 0；当fvs为0时关闭此功能。 default:0
-mnt <model_number_type>: 模型参数在内存中和二进制文件中的类型，double或float。 default:double

fm_predict的参数：

-m <model_path>: 模型文件路径。
-mf <model_format>: 模型文件格式，txt（文本）或bin（二进制）。 default:txt
-dim <factor_num>: v的维度。 default:8
-core <threads_num>: 计算线程数。 default:1
-out <predict_path>: 输出文件路径。
-mnt <model_number_type>: 模型参数在内存中和二进制文件中的类型，double或float。 default:double

model_bin_tool的参数：

-task <task_type>: 1-输出模型信息；2-格式转换，bin到txt；3-格式转换，bin到txt，只保留非零特征；4-格式转换，txt到bin。
-im <input_model_path>: 输入模型路径。
-om <output_model_path>: 输出模型路径，用于task 2、3和4。task 4必须指定，task 2和3若不指定则默认为标准输出。
-dim <factor_num>: v的维度，用于task 4。
-mnt <model_number_type>: 模型参数在二进制文件中的类型，用于task 4，double或float。 default:double

计算速度：

我的实验结果：

本地1000万的样本，200万的特征维度，2.10GHz的CPU，开10个线程，非缺省参数如下：
-dim 1,1,2 -w_l1 0.05 -v_l1 0.05 -init_stdev 0.001 -w_alpha 0.01 -v_alpha 0.01 -core 10
训练时间只需要10多分钟。若指定模型文件为二进制格式，速度会更快。

xiaobocser/alphaFM