Tian Jun
Fight For Dream!

完整记录ijcai2016参赛过程

Tags: Competition,

Last Update: 2016-05-03 22:21:14

最近刚刚完成了毕业论文,闲着也是闲着,做个比赛找回点学习的感觉,对比了几个比赛,感觉ijcai2016这个比较对胃口。想想马上要毕业了,大概,这是毕业前参加的最后一个比赛了,不追求取得多好的名次,完全是探索性地做一下,把自己的一些思考记录在这里,算是留作纪念吧。

1. 赛题理解

简单来说,整个比赛的任务就是,给定2015/07/01~2015/11/30期间用户分别在线上的交互行为和线下实体店的购买行为,来预测2015年12月份指定用户在指定地点可能购买的商家,同时线下实体店商家的预算做了限制。

全部的数据包含4个表。表1是用户在线上的点击购买行为,包含[user_id, seller_id, item_id, category_id, action_id, time]6个字段。表2是用户在线下的消费信息,包含[user_id, merchant_id, location_id, time]4个字段,表3是线下商家的location信息以及budget限制,包含[merchant_id, budget, location_id_list]3个字段,表4是需要预测的[user, location] pair。

评价指标则是,基于微平均F1值的变种(主要是强调了budget的限制)。

upload/venn1.png_3b95e1c83a1786146cf30dec93df44f1

首先看线上和线下的数据之间的联系,线上用户数为963923,而线下的用户数为645375(其中训练集230496和测试集465366,二者的交集为50487),线上用户数据和线下总的用户的交集为509098。具体的韦恩图如上图所示(需要注意的是,这个图是自动生成的,由于需要借助面积来表示数据量大小,koubei_train 与koubei_test的交集50487人中仍有(50487-40853)不在taobao数据中,这部分在图中没有表示出来),这意味着:

  1. 现在要对46万用户进行线下消费预测,但是约1/5(89347/465366)的用户既没有过线上消费记录,也没有线下的消费记录。这一点需要在设计模型的时候格外考虑。
  2. 待预测的用户中只有约1/10(40853/465366)的用户是拥有线下消费历史数据的,相对来说,这部分用户更容易预测一些。剩下的7/10(325532/465366)用户拥有线上的数据。

2. 数据分析

先来对数据做一些简单的分析,以加深对整个数据集的感性认识。

2.1 线上数据分析

首先是线上数据的流量图: upload/.png_e0b9e9cb5f5f7da672e866fde8a98585

其中,11/01~11/20的数据缺失,赛题的数据说明里提到,主要是为了避免双十一数据带来的干扰,除了周期性比较明显这点之外,没有太多信息量。

再看看线上商品种类的分布,总共有72个类: upload/category.png_f4bb3e09529983acdc9c5b5d89b4d06e

其中,类别1的数据稍微有点异常,其它类别分布比较均衡,我猜是衣服类别,哈哈~

另外就是,线上卖家的流量直方图: upload/seller.png_1625d44888eaa04f4e0a2de3720e5dcf

其长尾比较明显,大多数卖家5个月内的流量在5000以内。

线上数据分析先不做进一步深入,主要是还没有理清如何利用这部分信息。我们知道,线上数据与线下数据唯一的交集就是用户重叠。下一步分析的重点可能放在:

  1. 用户线上的消费习惯以及消费能力对线下消费有多大影响?(也就是那1/10的待预测用户)
  2. 线上消费行为相似的用户,在线下消费过程中是否也有指导意义?(用户迁移学习,也就是那7/10的用户)

2.2 线下数据分析

首先看一下线下的流量图: upload/liuliang2.png_7e53265f6dafa40ffba0cc37edbc47e3

可以看到,koubei数据几乎是爆发式增长。不过有点奇怪的是,11/01附近,流量出现了一个明显的下跌,我猜要么是那段时间没怎么发优惠券了,要么是商家有所调整。11月份开始,周期性变得更明显。然后我们按月看下流量的柱状图:

upload/liuliang3.png_6beb75faa0df56292b401a00b68dd6d0

保守估计,12月的累积流量应该增长到75000。因为,我清楚滴记得去年双十二线下的火爆场面,增长量应该比11月相对10月的增长量要更大。

3 解决方案

在对数据有了初步的认识后,如何解决这个问题呢?

初步来看,相比传统的推荐问题,这个问题复杂的地方在于,数据的缺失以及背景信息的丰富(这里指的是线上数据)。

我们不妨先把这个问题一点点简化,然后将其对应到熟悉的问题上去解决,在解决的过程中慢慢比较异同点并优化解决方案。

首先,我们把线上的数据先放一边。尽管,线上的数据量很大,但是线上的数据和线下数据之间的联系并不是特别强(直觉而已。。。),线上的卖家和线下的卖家是相互独立的,有交集的只是用户。那么现在手上只有7/01~11/30期间的线下用户消费数据,然后需要预测12月份用户在指定地点可能消费的商家。这样,12月份的用户又可以分为两部分,其中5万用户有历史消费记录,41万用户没有消费记录。显然,对于没有消费记录的用户,我们在对其做推荐的时候,可以把他当做是anonymous用户,这样,对该用户的推荐行为将只依赖于指定地点的商家(这里还有一个budget的问题,暂且不考虑)。对于有消费记录的5万用户,则需要结合其历史记录来综合推荐。

需要明确的一点是,对于anonymous用户而言,我们能唯一确定的是,其在指定地点一定发生了消费行为。因此,我们可以给每个用户推荐该地区最受欢迎的merchant。更细一点,这里有几点需要考虑的,一是给每个用户推荐多少个merchant,赛题要求不多于10个,实际上,这里我们可以简单的使用均值来确定给anonymous用户的推荐个数,该均值还未统计,不过可以预计是肯定不是一个整数,取其临近的整数即可。另外一个问题是,某一地区里,anonymous用户可能会很多,这导致该地区的热门merchant所发出的优惠超过了budget上限,因而涉及到一个用户筛选的问题。然而,在没有背景信息的情况下,只能采取随机筛选,不过借助线上的用户数据,可以简单的根据用户的购买力和活跃度作为排序标准。

对于有历史数据的用户,我们可以考虑:

  1. 用户是否在该区域消费过?如果是,优先推荐其消费过的merchant,如果没有,那么优先推荐与其消费喜好相似的店
  2. 超出merchant的budget了怎么办?由于有历史数据的用户是优质用户,所以理论上应该优先考虑,然后再考虑anonymous的用户。

4 训练集和测试集的划分

为了方便本地验证,需要从训练集里划分出本地的训练集和测试集(为了方便,以下分别称为train_set 和test_set)。由于7月份的数据量不是很大,因此我们可以简单地将7~10月份的数据作为train-set,11月份的数据作为test-set。为了确认这样的划分相对于线上的测试集没有特别大的偏差,需要对本地的train-set和test-set中的用户交集情况以及与线上数据的交集情况做一个对比。

upload/venn2.png_f40c90d048ecb9bfe8d8ede3bf7e2d30

对比本地的train-set和test-set用户分布相比线上的训练集测试集来看,可以分析出以下几点:

  1. 11月份的时候,还有6万多的用户有历史数据,12月的时候就只有4万多了,说明用户流失有点严重;
  2. 12月份的时候,线上用户大量涌向线下。从6万增长到了32万。

另外,还统计了下面两条信息: 11月份的新用户中转化到12月份购买用户的数量: 17733; 7~10月份的老用户中转化到12月份购买用户的数量: 32754。 这里面的关系有点乱,暂时理不清了。。。

接下来,需要用实际的模型来检验这种划分的效果。

5 实验

5.1 如何衡量merchant的影响力

先不考虑线上的用户记录和线下的budget限制来思考这个问题。

已有数据:

  • train_set:7~10月份的用户线下购买记录,以及11月份用户实际购买的记录。
  • test_set:7~11月份的用户线下购买记录,需要预测12月份用户对 实际购买行为(加上约束)。

分两步走,首先是新用户的预测,其次是老顾客的预测。

新用户的预测在这里相对简单点,只需要考虑某一地区merchant信息。从先验的角度来讲,应该给每个用户推荐该地区最热门的merchant。那么哪些特征会影响merchant的热门程度呢?

  • 该merchant的历史用户量,当月用户量(这个应该算作弊吧。。。),用户购买频次,分店数量,日活,月活,增量,回头客等等(想到更多的了再补充)
  • 新店/老店,budget数量,
  • 该地区平均消费能力
  • 整体排名
  • 第一次到该地区的用户都选择了哪些店?

对于老顾客,为了简化问题,我们也将其看作是前一个问题的强化。对于有历史记录的用户,如果该用户曾经在指定location有过购买行为,先直接推荐,对于没有来过该地方的用户,我们将其退化成anonymous用户。

最后,我们需要结合budget做一些限定,这个需要结合具体的数据来确定。这样我们就得到了一个该解决问题的初步方案。先试试效果看~

这两天没有做太多的深入工作,一些基本问题的思考倒是对这个赛题有了一些新的认识。接着上面的实验说,当时抽取好特征之后,想的是衡量一个商店的热门程度。然而,抽完特征我才发现,之前都是理所当然地当做分类问题在思考,然而实际上,我们只有正样本的数据(用户发生了购买),却没有明显的负样本数据。唯一可以用来当做负样本的隐式数据是用户没有发生购买的区域内的店家。然而,我们抽取的特征是围绕商家来的,这样必然导致每一个商家既是正样本,也是负样本(当然,正负比例不同,与热门程度相关)。可不可以继续分类呢?也不是不行,但是总觉得不太合理。换个角度去想,不妨把这个问题看做是回归问题,我需要结合商家的历史数据去预测下个月该商家实际购买量(购买量直接反应商家的热门程度),这样就显得更合理了。这部分还没开始做,还需要结合budget的限制去处理(有点麻烦)。

说说另外一点,前面提到用线下11月的本地训练结果来模拟线上的分类结果,如何评估这种拟合是可行的呢?我先做了一个最简单的验证。从前面两个韦恩图可以看到,有部分用户是重复购买的用户,那么我只预测该部分用户,线上得到的f1-score 是0.16,那么线下用同样策略得到的是多少呢?0.453!具体的数据如下:

n_hit: 68403
n_predicts: 94009
n_hit_budget: 57818
precision: 0.727621823442
precision_with_budget: 0.615026220894
n_real: 195481
n_real_budget: 161186
recall: 0.349921475744
recall_with_budget: 0.358703609495
f1: 0.472575909358
f1_with_budget 0.453128000157
 

上面数据中的后缀_with_budget表示考虑了budget限制后得到的结果。可以看到budget对准确率是降低的作用,对召回率有提升的作用,二者综合后,对f1的影响不大(显然,该结论的进一步推广有待验证)。

我想说的是,线下的预测和线上的预测之所以差别很大,原因是线下的重复购买用户所占比例接近1/2而线上数据的占比只有约1/10,所以相差很远。这也说明,这种用线下去拟合线上的方法不太靠谱。需要想想其它方法来训练模型。马上要去实习了,感觉花在这上面的时间不太多了呀。。。

Deep Learning 相关库简介

Tags: DeepLearning,

Last Update: 2016-03-17 22:15:40

本文将从deep learning 相关工具库的使用者角度来介绍下github上stars数排在前面的几个库(tensorflow, keras, torch, theano, skflow, lasagne, blocks)。由于我的主要研究内容为文本相关的工作,所以各个库的分析带有一定主观因素,以RNN模型为主,CNN相关的内容了解得不是特别深入(本文没有比较caffe和mxnet,其实主要原因还是自己C++太久没用了......)。

阅读本文你会了解:

  1. 各个库是如何对神经网络中的结构和计算单元进行抽象的;
  2. 如何用每个库跑RNN相关的模型;
  3. 各个库学习和使用的难以程度对比;
  4. 在各个库基础之上进一步改进和开发的难易程度;

本文不会涉及:

  1. 各个库运行时间效率的对比(我没有自己做过相关的对比实验,但是网上有很多数据可以查);
  2. CNN相关模型的构建(前面提到了自己最近对这块了解得不多);
  3. RNN相关模型的原理和解释(网上很多资料,可以先学习后再进一步阅读);

先说说这几个库之间的大致关系

对于一个优秀的深度学习系统,或者更广来说优秀的科学计算系统,最重要的是编程接口的设计。他们都采用将一个领域特定语言(domain specific language)嵌入到一个主语言中。例如numpy将矩阵运算嵌入到python中。这类嵌入一般分为两种,其中一种嵌入的较浅,其中每个语句都按原来的意思执行,且通常采用命令式编程(imperative programming),其中numpy和Torch就是属于这种。而另一种则用一种深的嵌入方式,提供一整套针对具体应用的迷你语言。这一种通常使用声明式语言(declarative programing),既用户只需要声明要做什么,而具体执行则由系统完成。这类系统包括Caffe,theano和刚公布的TensorFlow。

以上是摘自MXNet设计和实现中的一段话。理解了这段话后,对后面各个库的进一步理解很有帮助。MXNet的设计者表示融合了这两种编程模式,我们先抛开mxnet,如上所述torch是采用命令式编程,然后theano和tensorflow是采用声明式编程,skflow对常用的tensorflow的封装,lasagne是对theano的封装,blocks除了对theano进行封装之外还提供了额外的处理机制,keras则是用一套接口同时封装了theano和tensorflow。

从theano说起

前面说theano是声明式语言,其基本过程可以描述为以下几步:

  1. 定义输入变量(x,y),输出变量(z);
  2. 描述变量之间的计算关系(z = x + y);
  3. 编译(f = theano.function([x, y], z);
  4. 求值(f(1,2));

那么,如果我想用theano写一个lstm呢?(具体参见这里)

  1. 准备输入变量x及x_mask(维度为 batch_size * sentence_length * vector_size),目标变量target(维度为batch_size)
  2. 定义初始化lstm结构单元中的参数(i, f, o, c)
  3. 定义好一个scan函数,在scan函数中完成每个结构单元的计算,根据lstm网络的性质,将结构单元的输出导入到下一步的输入。在这里,theano中的scan就是一个加强版的for循环
  4. 计算loss,采用某种算法更新参数
  5. 编译,f = theano.function([x, x_mask, target], loss)
  6. 对每个batch求值

注意前面加黑的几个关键词,在后我们将反复看到每个库的设计者对这几个概念的不同理解。

接着说tensorflow

tensorflow的设计思想和theano很接近。但是我感觉,tensorflow似乎更强调整体性和结构型。二者的明显区别在于:

  1. tensorflow默认有一个Graph的结构,所有添加的结点都是在这个图结构上,但是theano中并没有这个概念。我的理解是这个Graph结构对于变量的管理会方便点。
  2. tensorflow目前能够在单机上多卡并行处理,其机制是通过指定gpu来分配计算过程的。因此,可以说其并行机制是数据层面的。而theano需要在载入包之前就指定gpu,

其余的很多地方都是相似的,只是换了名字而已,比如: tensorflow中的variable对应theano下的共享变量shared variables, tensorflow中的placeholder对应theano中的tensor变量, 另外tensorflow中为了避免变量的来回复制,其所用的tensor的概念和theano中不太一样

然后来看看tensorflow是怎么实现一个LSTM网络的,与theano不同,tensorflow已经对rnn_cell和lstm_cell做了封装,因此写起来容易了很多。

  1. 定义好输入及中间变量
  2. 采用for循环将每个lstm_cell的输入输出组装起来
  3. 剩下的也就没有新意了,计算loss,更新state

我们后面再讨论这种封装方式与其他库的对比。

再说torch

torch的代码写起来有点像写matlab,本身torch是一个科学计算的大集合(我感觉只是借了lua这个语言一个外壳,方便和c及c++交互罢了,从这个角度来看,我觉得julia这门语言似乎大有潜力),这里我们主要是讨论其中的nn和rnn模块。

我自己对lua及torch都不是很熟,但是好在语法不复杂,基本都能看懂,建议大家也能花点时间学习下,这样下次看到哪篇paper里实验部分用torch写的时候,不至于完全看不懂。尽管我对torch的了解不深,但是不得不说torch对剩下其它几个库的设计影响非常大!

在torch的nn模块里,首先对整个网络结构做了分类抽象。首先是最顶层的抽象Model,这个里面最基础的就是output和grad_output,记忆中和caffe的抽象是类似的,将计算结果和偏导结果用一个抽象类来表示了。然后是Sequential, Parallel 及 Concat这三个容器。Sequential用于描述网络中一层层的序列关系,典型的就是MLP,Parallel可以用于分别处理输入的不同维度,而Concat则可以用于合并操作。一般来说,我们现在的网络结构都可以通过这三种结构拼接得到。

然后再看看torch的rnn模块中如何构建lstm网络的:

和tensorflow一样,首先是继承自AbstractRecurrent的一个抽象,然后是参数配置和初始化,不同之处在于,其对LSTM中的门结构也做了进一步抽象,最后,用Sequence代替了for循环的功能,从而提供一个完整的网络结构。

小结

通过上面的简单描述,我们对这三个基本库有了些大致的印象。

  • torch是最庞大的库,如果一开始就选择这个库作为工具的话,还算说得过去,否则学习的代价有点大,因为平常做实验涉及的往往不只是跑跑模型这么简单,还涉及到数据的预处理与分析,相关图表的绘制,对比实验等等。这样一来要学习的东西就比较多了。
  • theano由于借用了numpy,scipy等python下科学计算的库,相对torch来说要轻松一些。不过,theano本身并没有像其它两个库一样提供cnn,rnn等模型的抽象类,因此往往不会直接使用theano去写模型。
  • tensorflow则更像是为神经网络相关模型而定制的。从顶层设计上就以graph为依托,通过不同的Session来控制计算流。

从库的使用者角度来说,tensorflow和torch都还不错。但是,如果涉及网络结构(这里特指RNN相关的网络)修改,那么torch要相对容易一些,主要是多了一个Gate的抽象,中间参数的处理上不需要太操心,而tensorflow中LSTM和RNN抽象类的耦合比较紧,如果涉及内部结构的修改会稍稍麻烦点,需要重写的方法比较多。

tensorflow开源时间不久,先抛开不计。由于theano缺少对神经网络结构的抽象,而torch中nn模块又设计得很合理,于是后面涌现的基于theano的库多多少少都有所参照。

Keras

keras设计的level有点高,其设想的就是底层的计算模块是可拔插的。这个功能当然看起来很炫酷,我想用tensorflow就用tensorflow,想用theano就用theano作为计算内核,然而代价也是有的,如果你想改其中的结构,复杂程度立马上去了。我觉得这个库的目标用户仅限于使用现有神经网络单元结构的人。如果你发现某个结构keras里没有?没事,这个项目开发者众多,发起个issue,马上就有人填坑(比如highway network, 我在其它几个库里还没发现,这里居然就有了,虽然并不复杂)。如果你想构造个自己的结构单元?那得了,您还是看看后面几个库吧。

综上所述,keras最大的亮点就是,简洁而全面。正所谓人多力量大嘛! 由于其底层处于兼容性做了一套自己的封装,想改的话稍显麻烦。

如果你觉得看完keras还不知道怎么用?想来点更简单的?有!sklearn用过把,fit, predict两步即可,傻瓜式操作,人人都是机器学习大神。skflow就是类似的,看名字就知道了。不过是基于tensorflow开发的。我反正是没用过这个库......

Lasagne

lasagne对网络结构的抽象和上面的几个库有很大的不同,在lasagne中基本抽象单元是Layer,对应到整个神经网络中的一层结构。这个layer可以是cnn也可以是rnn结构,除此之外还有一个MergeLayer,就是多输入多输出的结构。和torch一样,也对Gate门结构做了抽象。

这样设计有好处也有麻烦的地方:

  • 好处是,写出来的网络结构很简洁,网络结构的初始化和配置都包含在layer初始化参数里;
  • 不方便的地方是,只引入了layer结构抽象层,是在是有些单一,如果能再加一个类似torch中的Sequential结构就perfect了,因为一旦涉及到循环,就不得不回头去使用theano中的scan函数,说实话,scan函数设计得太复杂了点。(当然,作者是不这么认为的,设计者认为lasagne并不是要将theano完全隔离开,相反,lasagne中的所有变量都应该相对theano是透明的Transparency)。

此外,lasagne中LSTM网络的实现与前面的大致相同,实现细节上,lasagne中的lstm类直接继承自MergeLayer,然后内部采用scan函数实现,像其它库由于有循环结构的抽象实现,因此每个lstm_cell类只需要完成单个结点内部的运算(也即只实现scan函数中的_step辅助函数)

总的感觉就是,lasagne在类的抽象上并没有过度设计,整个网络中的参数采用自顶向下的宽度优先算法获取,因此,只要你愿意,你可以任意在这个网络上“凿”个洞,得到该局部网络的关系。有一定的扩展性优势。

Blocks

这个库是我最看好的一个库,作者应该从torch中借鉴了很多思想。

在这个库中,每一个运算都看做是一块砖,这块砖涉及配置、分配、应用和初始化这四步。更重要的一点是,brick与brick之间可以嵌套,从而得到更抽象的brick。这下子解决了我们前面一直碰到的一个问题,:抽象层次的把握!前面大多都是根据抽象层次的不同设计各自的类,而blocks通过嵌套将类统一起来,这样我们在设计自己的模块时,可以很方便地选取合适尺寸的brick。

相比lasagne中直接根据layer.get_output来获取参数,blocks采用了ComputationGraph来管理整个网络结构,我的理解是,lasagne的那种方式还是有点野蛮......采用ComputationGraph之后,可以同时制定输入和输出对象,这样即使网络结构变得更复杂了,我们也可以随心所欲指定其中某个部分来更新。

下面用blocks文档中关于rnn的一个模型来说明blocks在个性化定制方面是多么优雅。先看图:

upload/blocks_rnn.png_7f55310225850de150599f22799cad5d

如果要设计这样一个stack的模型,就需要make your hands dirty 了。在lasagne中,这个整体会被看做一个layer,所以需要自己重写一个layer,那跟直接用theano写无异了......keras中也没有提供现有的模型,所以......对于tensorflow和torch来说,需要重写AbstractRecurrent类,从而可以让其接受两个输入。

相比之下Keras提供的解决方案就比较优雅,通过iterate将simplerecurrent在time_step维度上缩短到了1步,然后再将整个连接结构封装起来。(也许其它几个库也有类似的控制,暂时没发现)

当然,除了上面这些抽象层面的易用性,blocks还提供了丰富的可视化调试和控制接口,以及数据预处理的fuel模块。这些功能在整个工程变得越来越臃肿的时候还是很实用的。

总结

在了解theano的基础上,如果只是想跑一下现有的模型不关注底层的实现,可以直接用Keras,上手快,模块清晰。如果打算持续投入,涉及大量网络结构改进,推荐使用bricks,其对训练过程的控制有着独特的优势。

另外需要注意的一点是,同样的数据,用不同库的同一个算法时,结果很可能会出现几个点的差异,这往往是不同库中对默认参数的初始化方式不同引起的,需要仔细检查下。

解读libFM

Tags: Algorithm,

Last Update: 2016-01-18 13:38:55

写在前面

由于之前的比赛中用到了这个工具,所以顺带对矩阵分解以及FM深入学习了下。本文将结合其算法原理和Cpp源码,说说自己的使用心得,另外讲讲如何将Cpp源码分别用Python和Java改写。

问题的本质

对于推荐系统一类问题来说,最核心的就是衡量用户对未接触target的感兴趣程度。CF一类算法的思想是通过相似度计算来直接估计感兴趣程度,矩阵分解一类的思想则是借助隐变量的映射间接得到对target的感兴趣程度。那么,FM呢?

个人理解是,FM和词向量一类的做法有相通之处。通过分别对用户和商品等构建一个向量,训练结束后根据用户的向量和商品向量之间的内积,估计出用户对商品的感兴趣程度。OK,借用论文[Factorization Machines]中的一个例子来说明下:

假设观测到的数据集如下:

(A, TI, 5)
(A, NH, 3)
(A, SW, 1)
(B, SW, 4)
(B, ST, 5)
(C, TI, 1)
(C, SW, 5)

现在我们要估计A对ST的感兴趣程度,显然,如果用传统的分类算法,由于训练集中没有出现(A, ST)的pair,所以得到的感兴趣程度是0.但是FM衡量的是$(v_A, v_{ST})$之间的相似度,具体来说,是这么做的:由观测数据(B, SW, 4)和(C, SW, 5)可以得到$v_B$和$v_C$之间的相似度较高,此外,根据(A, TI, 5)和(C, TI, 1)可以推测$v_A$和$v_C$之间的相似度较低。而根据(B, SW, 4)和(B, ST, 5)可以发现,$v_{SW}$和$v_{ST}$之间的相似度较高。计算$v_A$和$v_{ST}$便可得知,A对ST的感兴趣程度较低。从这个角度来看,FM似乎是借用一种向量化表示来融合了基于用户和基于商品的协同过滤。

理解其数学模型

根据前面的描述,给定一个用户商品(U,I)pair后,我们只需计算下式即可得到估计值:

$$\hat{y}(x)=\langle v_u, v_I\rangle$$

但我们这么做的实际上是有几个潜在假设的: 1.默认特征矩阵中只有User和Item两类特征; 2.User和Item维度的特征值为1;

实际问题中除了User和Item,还通常有Time,UserContext和ItemContext等等维度的特征。此外,不同User和Item的权值并不一样,所以并不都是1。将上式改写下便得到了FM的原型:

$$\hat{y}(x)=w_0+\sum_{i=1}^{n}w_i x_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n}\langle v_i, v_j\rangle x_i x_j$$

其中$w_0$是全局bias,$w_i$是每维特征的权重, $\langle v_i, v_j \rangle$可以看做是交互特征的权重。

计算过程优化

显然,上式的计算复杂度为$O(kn^2)$,利用二次项展开式可以将计算复杂度降低到线性复杂度:

$$ \begin{split} &\sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle v_i, v_j \rangle x_i x_j\\ &=\frac{1}{2}\sum_{i=1}^{n} \sum_{j=1}^{n} \langle v_i, v_j \rangle x_i x_j - \frac{1}{2} \sum_{i=1}^{n}\langle v_i,v_j \rangle x_i x_i \\ &=\frac{1}{2}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{f=1}^{k} v_{i,f}v_{j,f} x_i x_j - \sum_{i=1}^{n}\sum_{f=1}^{k}v_{i,f}v_i x_i x_i\right)\\ &=\frac{1}{2}\sum_{f=1}^{k}\left(\left( \sum_{i=1}^{n} v_{i,f} x_i \right) \left( \sum_{j=1}^{n} v_{j,f} x_j \right) - \sum_{i=1}^{n} v_{i,f}^2 x_i^2\right) \\ &=\frac{1}{2}\sum_{f=1}^{k}\left(\left( \sum_{i=1}^{n}v_{i,f} x_i \right)^2 - \sum_{i=1}^{n}v_{i,f}^{2} x_i^2\right) \end{split} $$

当v的维度从2维扩展到d维时,上式也可以做对应的扩展。对上式中的变量($w_0, w_i, v_{i,f}$)分别求导可以得到下式:

$$ \frac{\partial}{\partial \theta} \hat{y}(x) = \left\{ \begin{aligned} &1,\hspace{3in}if\ \theta \ is\ w_0\\ &x_i, \hspace{2.9in}if\ \theta \ is\ w_i\\ &x_i\Sigma_{j=1}^{n}v_{j,f}x_j - v_{i,f}x_i^2, \hspace{1.15in} if\ \theta \ is\ v_{i,f}\\ \end{aligned} \right. $$

C+ +源码解析

下面以libfm默认的mcmc方法用于分类任务为例,对其C+ +实现做一个简单分析。

概括地来说,训练的过程分为两步:一是计算误差,二是更新系数($w_i$和$v_{i,f}$)。具体流程如下:

  • 读入参数,并初始化。对于mcmc方法,重要的参数只有三个,一是-iter,即迭代次数;二是-dim,用于确定上面的v的维度;三是init_stdev;用于控制v和w的初始值(用正态分布随机初始化,由fm.init()完成)。
  • 接下来调用_learn(train, test)来完成整个训练过程。其中cache是一个e_q_term的对象,该对象中的e用于存储最后的误差项,q可以看做一个缓存,存储一些中间计算结果(不得不说,作者把内存用到了极致!!!各种省内存的做法啊)。把_learn函数的核心部分剥离出来就是下面的内容:
    void _learn(Data& train, Data& test){
     // ...
     predict_data_and_write_to_eterms(data, cache); // 根据v和w分别计算在训练集和测试集上的估计值,并保存到cache中
     //根据训练集的target值,计算训练集上的偏差
     for (uint c = 0; c < train.num_cases; c++) {
     cache[c].e = cache[c].e - train.target(c);
     }
     
    
// 迭代更新 for (uint i = num_complete_iter; i < num_iter; i++) { //... draw_all(train); //根据偏差(cache中的e部分)和训练集数据更新v和w predict_data_and_write_to_eterms(data, cache); // 用更新后的v和w继续计算训练集和测试集上的估计值 }
  • 先看一下predict_data_and_write_to_eterms函数,其实就是求解$\hat{y}$的一个过程。将其分解为2个部分,即$\sum_{i=1}^{n}w_i x_i$和$\sum_{i=1}^{n}\sum_{j=i+1}^{n}\langle v_i, v_j\rangle x_i x_j$(对mcmc方法而言$w_0$项为0),后者的线性时间简化版可以分成$\frac{1}{2}\sum_{f=1}^{k}\left(\left( \sum_{i=1}^{n}v_{i,f} x_i \right)^2\right)$ 和$\frac{1}{2}\sum_{f=1}^{k}\left(\sum_{i=1}^{n}v_{i,f}^{2} x_i^2\right)$这两块。这样子,predict_data_and_write_to_eterms函数对应的源码就好理解了。需要注意的一点是,源码中的Data数据结构实际上是CSC格式的稀疏矩阵,因此C++源码计算过程中是转置后按行取值计算的。理解这一点后,再用python或java改写该部分时,便可直接使用矩阵计算的方式,避免for循环带来的开销。
  • ``draw_all``函数稍微复杂点。先假设没有meta文件(特征的分组信息),前面我们已经得到了v,w参数的梯度,mcmc的做法是计算梯度并更新之后,对结果分别加入了正态分布和gamma分布的采样过程,与此同时,作者边更新v和w,根据新旧v和w的变化程度同步更新error(这个部分理解得不是很透彻,一般而言会在v和w完全更新后再更新e)。最后,对训练集上的目标值做一个截断高斯分布采样,利用采样值对error进一步更新。
  • meta信息的加入,相当于对每类特征内部多了一个正则项,在我使用的过程中,加不加正则项对结果的影响还是蛮大的。主要原因可能是我不同特征组的scale差异有点大,如果采用全局的正则项,难以精确描述不同特征组之间的差异。

改写成python和java版本

由于比赛平台是java的,需要将Cpp代码改写成java,前期验证功能性的时候,为了快速分析中间变量,先用python写了一遍。整体框架都一致,核心是实现predict_data_and_write_to_etermsdraw_all这两个函数。其中predict_data_and_write_to_eterms的实现比较简单,分别借用python下的scipy中的csc矩阵和java下matrix-toolkits-java包中的FlexCompColMatrix可以将Cpp源码中的for循环大大简化。但是对于draw_all函数却不太轻松,最核心的问题是前面提到的,Cpp源码中在更新w和v的同时还在更新error项,导致无法一次通过矩阵运算后再更新error(事实上我一开始这么干过,但是跑出来的效果差太远),无奈,只能和Cpp一样用循环迭代更新,效率上慢了将近一个数量级。