CWYAlpha

Just another WordPress.com site

Thought this was cool: libFM学习感想

leave a comment »


libFM全称为Factorization Machine Library,是由Steffen Rendle于2010年提出的。最近由于他以libFM为队名,在KDD CUP 2012和刚刚结束的Music Hackathon中都取得了很不错的成绩,所以libFM引起了一些人的注意。我最近拜读了一下libFM的相关论文,以及源代码,也有一些收获,就总结一下。
libFM不仅仅适用于推荐系统,而是和SVM一样可以用于数据挖掘中的很多问题,以分类问题为主。他接受的数据格式和libSVM是一样的,每行一个数值(分类结果or打分结果等),对应一组特征,每个非零特征都需要给出数值,零特征忽略。
他的思想应该是从推荐系统中经典的SVD模型(因子分解模型)得到的,经典的SVD模型当中相当于只有两种类型的feature,一类feature是user,一类feature是item,而libFM是把这个模型推广到了多类feature的情况。为简单起见,考虑因子维数为1的情况,SVD模型用$a*b$来作为对打分的预测。而libFM要面对的是多类feature,假设是3类,那么就用$a*b+b*c+c*a$来作为对结果的预测。这时候就要问了,如果feature很多,这不就有平方量级的乘法次数了么?当然不是,libFM的文章中提到,他利用$((a+b+c)^2-a^2-b^2-c^2)/2$来计算刚才的式子,但是你可以看到,他们其实是相等的,不同的是,这样的计算量只是线性复杂度的。当然libFM也同时支持bias项,这和经典SVD模型类似。
以上就是libFM的创新之处,其实如果很了解SVD模型,那这个改进并不难理解。
论文中还提到,经典的SVD++模型等对于SVD模型的改进,也只是libFM的一个子集而已。只要合适的去添加feature即可。比如SVD++模型就相当于对每个item增加一个feature,来描述用户是否也给这个item打过分即可。所以有了libFM以后,最需要人工解决的问题就是添加合适的feature了。
另外再说明一下推荐系统的数据如何转化成libFM接受的形式。假设User ID范围是[0,99],Item ID范围是[0,199],则定义feature 0到feature 99对应于User,feature 100到feature 299对应于Item,假设第一条打分记录是User 4对Item 9的打分,则feature 4和feature 109的取值为1,其余feature取值都是0。由于数据文件是稀疏格式的,所以取值为0的feature都不用写,这样文件不会太大。其余对经典SVD模型的改进就需要增加一些对应feature。他的代码中,每条记录是使用map存储feature的,可以随机存取任意一个feature的值(但是可能用链表就可以了?因为一般都是顺序访问的)。
他的这种做法虽然简单,但可以很好的处理二元以上的关系。libFM能够从一个更高的层次去理解SVD模型的改进,这也包括去年xlvector对KDD CUP Track 2所做的那个改进(用户是否听过这个歌手的歌),这也难怪libFM能在多个比赛中取得出色的成绩。
最后给出libFM官方网站:http://libfm.org/

from Dora Blog: http://diaorui.net/?p=346

Written by cwyalpha

七月 27, 2012 在 4:43 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: