Skip to content
Multi-thread implementation of Factorization Machines with FTRL for binary-class classification problem.
Branch: master
Clone or download
Latest commit 3f68be3 Sep 2, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
bin first commit Oct 22, 2016
src optimize memory Sep 1, 2018
LICENSE Create LICENSE Sep 1, 2018
Makefile optimize memory Sep 1, 2018
README.md Update README.md Sep 1, 2018
fm_predict.cpp optimize memory Sep 1, 2018
fm_train.cpp optimize memory Sep 1, 2018
model_bin_tool.cpp optimize memory Sep 1, 2018

README.md

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多分钟。若指定模型文件为二进制格式,速度会更快。

You can’t perform that action at this time.