Tian Jun
Fight For Dream!

解读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一样用循环迭代更新,效率上慢了将近一个数量级。

About This Site

Tags: Clojure, Web, Django,

Last Update: 2016-01-08 15:02:15

BugFix

记录昨天fix的一个Bug,之前后台自动保存的功能出了个bug,直接导致一个文档的content同步覆盖掉了另一个文档的content。要命的是不知道怎么复现这个bug。查看log日志,所有的请求都正常。昨晚跟同学讨论了下,感觉应该是js自动保存逻辑出问题了。仔细review了下代码,果真是。

原来的实现是,自动保存和markdown渲染封装在同一个按键检测事件里,并加入了一个10秒钟的延时,如果10秒钟内没有按键触发则发起PUT请求保存当前内容。原来的代码所存在的问题是,编辑一个文件的时候,如果10秒钟内切换到了另外一个文档,那么,会导致读取的id和content不一致,具体说明如下:

    $('#response').keyup(function () {
        var v = $('#response').val(),
            s = markdown.core.mdToHtml(v);
        $("#rendered").html(s)
        MathJax.Hub.Queue(["Typeset",MathJax.Hub,"rendered"]);

        if(save_time_out) { clearTimeout(save_time_out); } //10 秒钟内检测到输入则重置延时
        save_time_out = setTimeout(function () {
            var ref = $('#tree-container').jstree(true),
                sel = ref.get_selected();
            if(!sel.length) { return false; }
            sel = sel[0];
            $.ajax({
                type: "PUT",
                url: "/essays/"+sel,
                data: JSON.stringify({"id":sel, "body": v}), // 问题出在这里,
                //PUT请求时,传递的是10秒钟前读到的v,
                //而此时的blog_id(即变量sel)可能变了,
                //导致一个文档的content更新到另一个文档里去了
                // 更改后的代码每次PUT重新读取当前的content和id
                // data: JSON.stringify({"id":sel, "body": $('#response').val() }),
                contentType: "application/json; charset=utf-8",
                datatype: "json",
                success: function(data){
                    save_tree("Blog " + sel + " Content AutoSaved: ")
                },
                failure: function(err){console.log(err)}
            })
            }, 
            10000);
    });

Update

貌似这个网站保持每年更新一次的频率。最近这次又重新折腾了下,不过目前依然是半成品。这次折腾的时间稍微有点长,前前后后大概有一个月时间吧。先说说改版的原因:

  1. 印象笔记基本被我弃用,而且原来写的网站后台同步系统有点小bug一直没有修复;
  2. 最近一段时间学习了下Clojure,挺有意思的一门语言,想动手实践下;
  3. 原来的HTML5模板总觉得被我改的有点丑,想再重新写一版;
  4. 希望将网站的后台管理系统设计成个性化的笔记管理系统,一定程度上替代印象笔记,为知笔记等;

针对上面几点,分别对网站做了以下改进:

  1. 抛弃原来的同步系统后,重写了后台的文档管理体系统,整个编辑界面借鉴了作业部落的设计方案,双屏切分(左边编辑,右边预览),导航栏用于管理文档结构,由于是自己用,舍弃了账户管理模块;
  2. 网页框架采用了luminus,我觉得这就是个大杂烩,把各个优秀的部件组织在一起,然后提供一些高可用的模板,上手非常方便。数据存储方面,抛弃了之前用的SQLite,换了Redis(没别的原因,只是对Redis用着熟悉点),文件存储上,仍然采用了七牛云存储qiniu-clojure-sdk的作者封装得真简洁......网页权限管理用到了之前说的Buddy,简单易行;后台管理的安全性方面,目前暂时把csrf模块给去掉了,因为后台有很多的ajax请求,还没想好该怎么绑定csrf-token,缺少这方面的经验,这应该是整个网站最大的安全漏洞;
  3. 重写前端页面。这块挺花时间的,主要是自己对js不熟,又重新翻了下JavaScript高级程序设计这本书,然后熟悉了下jquery和react,感觉react写前端的想法确实有点不太一样,然后继续往前学习了下ClojureScript以及对react封装的库OM,完全刷新了我对前端的认识(我承认之前一直很BS前端干的活......),然而时间精力有限,这些都仅仅是浅尝辄止。最后前端部分主要用jquery写的;

说说感受

整个从前端到后端全都写了一遍,说实话,觉得挺累的。很多地方都是从零开始,完全没有经验可谈。除了HTML是在WebStorm下写的,其余都是在vim下写的,并不是我排斥IDE,而是IDE用着效率太低了。

总的来说,我挺喜欢Clojure这门语言的,简洁,有魔力!可惜的是我到目前为止还算不上入门,也没体会到其在处理并发问题上的优势。而且,最近写clojure的过程中,也读了不少框架的源码,感觉很多代码还是很难懂。接下来的一段时间估计没空深入学习了,毕竟clojure又不能拿来跑RNN......我能想到后面会用到clojure的地方估计就是用它来写SICP的习题了......

====================================

写在前面

之前网站一直放在SAE上,除了每月扣点豆子,用着也没啥问题,除了扩展性不太好之外。不过,间歇性的出了几次意外,后台往sql中写入数据的时候,不知道是啥原因,提交后页面卡死了,然后再去sae后台一看,哗啦啦几百豆子没了......我总共才送了1.5k,无语了。想了半天也没找出时什么原因,只知道是全都扣在sql的读写上了。也罢,懒得在上面折腾了,写的东西暂时都放在印象笔记里。前些天忽然想起来github送的DigitalOcean优惠券还没用,最近有点闲时间,再折腾了一把。之前的后台是刚熟悉python的时候写的,现在再看看,真是渣渣......然后动手重新写了一遍部署到DO上(回头看了一下,其实还是渣渣......忧桑)。这段时间用印象笔记用着很爽,主要是方便,所以,这次后台的改动主要就一个,利用Evernote的api把网站后台跟印象笔记打通了,这样便于随时积累,持续更新。另外,rss给去掉了,有兴趣的话加个印象笔记吧~

整体结构

怕自己以后给忘了,画个图,以后再修改起来也方便。site.png_d2006a2a0cf19cc0de218e331d0ebf2b

跟印象笔记api打交道的过程中,坑很多,最惨的一个莫过于,在sandbox中测试的好好的,换成印象笔记的token后就出错了,各种google,居然有人给出了解决方案,把service_host改一下就好了,另外这里只是简单采用轮询的方式,因为对实时性要求不高,所以没用所谓的webhook。

目前网站布在新加坡节点,感觉速度上还行吧,没有网上说的那么差。万一不稳定了再换换。新加坡的节点有ipv6这个很不错。配合shadowsocks用着很快。

其实本来打算把shares部分大改的,主要是想跟自己的虾米账户打通,已经写了一半了,忽然发现国外不能访问国内的虾米,真是个蛋疼的世界。唉,真是应了那句话。

墙外的想到墙内去,墙内的想到墙外来......

算了,以后有空再弄弄,往所里的电脑上布个代理做跳板。也许下次会直接弄个music的二级域名出来。

说点细节

印象笔记和数据库的同步通过定时器实现,由于印象笔记的特殊性,每一条笔记对应正文和资源(包括图片等附件)两部分,因此将同步过程分为两步。

  1. 首先查询对应笔记本中每条笔记的更新时间,同时检索本地数据库中每一条记录的更新时间。然后提取需要更新和新建的记录。正文部分用正则做一个粗过滤(替换掉div,br标签)后写入数据库(其实可以经过markdown渲染之后再写入数据库,这样响应会更快,不过,这部分响应时间相比建立连接的时间而言可以忽略不计,而且有时候需要在后台查看下过滤的结果),同时提取附件相关的内容转换成链接格式。并将涉及到的资源写入数据库中的一张表。
  2. 扫描上面的资源表,对于没有下载到本地和同步到cdn的资源分别下载和上传,并校验。

分成两步的最主要原因是,如果附件比较大,很容易出现下载上传失败的情况,从而导致整个文档更新失败。将下载和上传部分独立出来后,不会影响文档内容的同步,如果某些大文件没法自动同步可手动在后台同步。

最后绑定下域名,分别把www.tianjun.ml和www.tianjun.me通过301重定向到主域名上。

谈谈感受

自己这么亲自折腾一把后,才会对现在的云平台带来的好处感受更深。其实说到底,像安装配置apache这些都是dirty work,云平台把这些集成后,可以说大大免去了这些苦力活,稳定性也有保证。

很久没写点东西了,最近会陆陆续续整理些出来,坚持坚持~

理解Clojure中Buddy认证模块

Tags: Clojure, Web,

Last Update: 2015-11-13 18:34:40

有关加密解密的知识一直是自己的盲点,最近在看如何用用clojure写网站,顺带学习了下cookie和session相关的知识,在这里介绍下Buddy这个库,并总结下自己的理解,不对的地方恳请指正。Buddy提供了基于Ring的一些安全认证相关的接口,下面内容就此展开。

先解释几个术语:

  • Handler:在Ring中,request和response都可以看做map,handler就是对request的内容分析后返回相应response的函数
  • Backend:Buddy模块中每个backend都包含2个部分Authentication和Authorization,其中Authentication包含parse(将需要的认证数据从request中提取出来)和authenticate(根据parse提取的信息判断是否通过认证)两个步骤,Authorization则包含发生认证错误后如何处理该错误并返回相应response的实现。

根据Authentication和Authorization的实现不同,Buddy模块提供了5种实现,下面以最简单的http基本认证为例:

Httpbasic

Httpbasic的处理逻辑如下图所示:

test.png_c3821b28623e8949810b26bf23a414d4

Httpbasic方式的缺点参见这里

  1. 密码采用base64编码,很容易反向转换;
  2. 每次请求都要传输密码(增加了攻击概率;
  3. 密码缓存在本地浏览器,容易通过CSRF窃取;

采用https协议的话,仅仅能解决第一点问题。

Session

该方案舍弃了httpbasic中传输username passwd的步骤,把验证和授权独立开来,授权放在login界面逻辑里去处理,将request中的:identity字段作为验证结果。而验证部分则只考虑是否存在:identity字段。

Token

基于Token的方法则是将原来Httpbasic处理过程里,request的header中Authorization内容改为了token,从而避免直接存储用户名和密码,然后服务器端存储token和用户的对应关系。

JWS Token

由于上面的token需要保存在服务器端,在用户量很大的时候,token的存储压力会很大,JWS token的用途就是将用户名密码加入签名后写进header的Authorization中,这样服务器端并不需要存储token到username的映射关系,只需要对token解码即可。这样做的好处是,不像Httpbasic简单采用base64对用户名密码编码,签名后的token很难破解得到原始的用户名密码信息。

JWE Token

JWE Token处理的过程和JWS Token很像,区别在于引入非对称加密,将一部分敏感信息用公钥加密,服务端用私钥解密。

参考

关于无状态认证的两篇讨论,里面提到了如何用python实现:

http://lucumr.pocoo.org/2013/11/17/my-favorite-database/

http://www.niwi.nz/2014/06/07/stateless-authentication-with-api-rest/