Tag: libFM

如何快速计算交叉项求和——从libFM联想到的一类数学问题

libFM里面有一个很好的idea是遍历特征的交互作用。也即$\sum_{i \ne j} x_i * x_j$。
但是遍历交互作用需要计算$O(n^2)$次乘法,于是作者做了一个变换,成为$ 0.5 * ((\sum_i x_i)^2 – \sum_i x_i^2) $。变换后只需要线性次的乘法和加法即可。
听严强说,实际使用的时候常常不需要遍历所有交叉项,因为很多特征之间是没有关系的。如果那样,问题就变成了$v = \sum_{(i,j)\in S} x_i * x_j $,其中$S$是给定的指标集。可能在实际中$S$里面元素是比较少的,但无论如何,这引发一个数学问题:如何给出一个等价变换,使得用尽量少的乘法和加法就能求得这个式子?如果设计一个智能算法,自动选择有用的特征对,这时候可能就真的需要一个算法找到相应的等价变换式。
确定这个定价变换可以不用特别快速,因为只需计算一次,但是得到的结果应该是可以尽量快速计算的。

这和我以前考虑过的一个问题非常类似,但是不完全一样。
首先我们考虑“相对精确”地去找计算量最少的等价变换。说“相对精确”是因为我还没想到以一个便捷的方式处理完美的精确。我们考虑近似化为一个优化问题。
假设我们要找到一个需要至多$m$次乘法的等价表达式,则有$v = \sum_{k=1}^m \left( \sum_{i=1}^n (a_{ki} * x_i) * \sum_{j=1}^n (b_{kj} * x_j) \right)$,这里$a_{ki}$和$b_{kj}$都只从$1$,$-1$,$0$之间选择,所以他们与$x$的乘法实际是不需计算的。这样的话,根据对应项系数相等(也可以是不等号,只要覆盖到交叉项也可以认为考虑了这种特征组合,不一定非要系数为1),我们会得到$n*(n+1)/2$个约束,未知变量数目是$m*2*n$个,从自由度的角度考虑,$m$至少需要和$n$一个量级才有可行解,实际上只要$m$取$n$就一定有可行解了,可以举出例子来,只是那样可能需要计算非常多次加法,所以不是好办法。我们可以用运算量作为目标,假设一次加法的代价为$C_{add}$,一次乘法的代价为$C_{mul}$,则目标函数为$\min. C_{add}*\sum_{k,i} |a_{ki}| + C_{add}*\sum_{k,j} |b_{kj}| + C_{mul}*\sum_{k=1}^n \max_{i,j} ( |a_{ki}|, |b_{kj}| )$。这个目标其实并不精确,不过不妨碍理解问题。
可以看到,目标是线性的,约束是二次的,且为整数规划,所以非常难。如果放缩到$a$, $b$都为实数,则问题简化了一些。但是仍然是非常困难的问题,非线性,非凸,不过可以尝试计算。虽然不能保证得到最优解,但是可能会得到较好的解。一个小问题是如果$a$, $b$为实数则他们和$x$乘积的运算量稍微不好量化一些。这里面很多地方描述不精确,比如$a$, $b$确实也不需要是整数,只是取特殊值相当于少了一次计算。
一句话描述这个优化问题,就是:给定一个0-1矩阵,把他化成尽量少的rank=1的小矩阵相加,且小矩阵等于两个尽量稀疏的向量相乘。

也可以有启发式的办法,例如交叉项相似的分到一组,可以用一次乘法计算出来。但效果很难说。

和这个问题很相似的问题还有:使用最少的乘法,求矩阵乘。比如Strassen algorithm就使用了7次乘法计算2*2的矩阵乘,而传统方法需要8次乘法。如何使用更少的乘法计算矩阵乘,和上述问题很类似。这也是一个非常困难的问题,目前还没有人能精确指出任意阶矩阵乘法所需的最少乘积次数。

libFM学习感想

libFM全称为Factorization Machine Library,是由Steffen Rendle于2010年提出的。最近由于他以libFM为队名,在KDD CUP 2012和刚刚结束的Music Hackathon中都取得了很不错的成绩,所以libFM引起了一些人的注意。我最近拜读了一下libFM的相关论文,以及源代码,也有一些收获,就总结一下。

Continue reading »