Category: 数据挖掘

如何快速计算交叉项求和——从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次乘法。如何使用更少的乘法计算矩阵乘,和上述问题很类似。这也是一个非常困难的问题,目前还没有人能精确指出任意阶矩阵乘法所需的最少乘积次数。

用pLSA实现博文分类

pLSA应该是做文本聚类的,不是文本分类的。
不过我是杂牌军,非专业人士,自己看的pLSA,所以会yy还能用到哪里去。
出发点是这样一个问题:有若干博文,需要将他们自动分类为ACM竞赛相关博文,非ACM竞赛的技术相关博文,非技术博文三种类型。这个问题的来源是因为 blog.acmicpc.info 这个网站的需要,在完成后会实际上线使用。目前也有一个正在进行中的比赛针对这个问题: http://acmicpc.info/archives/1194
因为需要实际上线用,难点在于占用资源不能太多,运行时间不能太长,不能用第三方工具。但是可以用第三方工具做训练,预测的时候不用就行了。

题中给出了5000个文章。可以先对这5000个文章用pLSA聚类,提出主题。
首先,我们要对文章做预处理,预处理主要包括几个方面:
1)去除网页标签:正则表达式替换即可,<[^>]*>替换成一个空格。
2)html实体替换:主要包括&nbsp;替换成空格,&lt;替换成<之类的,如果用PHP语言,可以使用htmlspecialchars_decode函数。
3)分离文字和代码:有几个策略,高级一点的是检测代码位置,一般在<pre>标签中间或者<textarea>标签中间,当然也有可能两边没标签,只能根据内容检测。如果要用这个方法,则前面去除标签步骤应该后做。山寨一点的办法就是把ASCII码全当成代码分离出来,效果也还行。
4)统计每个文章的词,这里可以使用ICTCLAS做分词,建议添加一些人工词,比如一些算法相关词汇。ICTCLAS支持UTF8等多种编码格式。输出中也提供了词性,我们只需要统计名词和用户自定义词即可,其他的词都丢掉。词太多和词太少的文章丢掉,不拿来训练。

然后要用pLSA算法,可以学习这个博文:概率语言模型及其变形系列(1)-PLSA及EM算法,在看这篇之前先看文本语言模型的参数估计-最大似然估计、MAP及贝叶斯估计可能效果更好。

实际写程序,就是个迭代,说夸张点,只有加减乘除等基本运算,核心代码很短。他文章中给出了式子。
设定一个合理的主题数量,然后就可以聚类,算出$p(w_j|z_k)$,就是每个主题下选中每个单词的概率。

下面就是讨论怎么用到博客的分类中去。
根据$p(w_j|z_k)$,列出各个主题下概率最高的单词,然后人工判断他们有多大概率属于目标的三类文章。分别设定一个权值,我们可以记为$p(t_l|z_k)$,也即主题$z_k$属于文章类型$t_l$的概率。
实际预测的时候只需要关键词列表$w_j$,主题下选中各单词的概率$p(w_j|z_k)$,还有人工设定的分类概率$p(t_l|z_k)$
然后拿到一篇新文章,不必做分词和之前训练时的繁杂的预处理,只要用关键词列表扫一遍即可,直接寻找子串,每匹配上一次关键词就粗略的认为关键词出现了一次。这样简单,也不需要第三方库了。
可以跑一次只包含一个文章的pLSA,并且$p(w_j|z_k)$固定为之前算出来的数值不动,只迭代更新$p(z_k|d)$。算出$p(z_k|d)$之后,利用$\sum_k p(t_l|z_k)p(z_k|d)$算出文章属于每一类的概率。选取最高的一个概率做分类即可。

这里面人工的工作量只有设定$p(t_l|z_k)$,因为主题数很少,所以人工的工作量非常小。
当然,说归说,做起来还有很多小问题。我粗略的写了一个版本,也没仔细设定很准确的$p(t_l|z_k)$,已经就可以达到80%以上分类正确率,数据文件大小,运行时间等都满足问题要求,占用资源很少。只要再做一些细微的修正,我觉得由此再改进到90%以上应该问题不大。期待比赛中有更好的思路和程序。

这个思路应该同样可以用于更广泛的博文分类,或者新闻分类等。

随机样本选择——快速求解机器学习中的优化问题

前阵子去参加了数学规划会议,报告很多,人也很多。或者说报告和人过多了……
有少数感兴趣的报告,这里谈一下全场最后一个报告。报告人是Jorge Nocedal,就是著名的LBFGS的作者。
他关注的问题是一类机器学习中非常常见的优化模型:
$J(w) = \frac{1}{N} \sum_{i=1}^N l(f(w; x_i); y_i)$
他谈到了机器学习里面常用的随机梯度下降法(stochastic gradient descent, SGD)。在实际大数据的情况下,他比经典优化方法效果要好。因为经典优化方法算一次下降方向就已经需要很大计算量了。
SGD需要的一次迭代计算量非常小,但是代价是他非常可能不是下降方向,而且需要一个有经验的人选择很好的步长(学习速率)。并且,在理论上,SGD的性质少,所以在优化这个方向里没什么人提到。即使是在计算上,Nocedal也提到SGD有个很大的缺点是不容易并行。
以上这些现象我在学习推荐系统SVD模型的时候也有一些感触。
所以他采用了另外一个思路,思想简单,效果却很好。而且能很好的利用上经典优化算法。经典算法都需要计算梯度。他的思想就是:只选取一部分样本来计算梯度。
这样有一个近似的梯度计算方法,用
$J_S(w)=\frac{1}{|S|} \sum_{i \in S} l(f(w; x_i); y_i)$
代替原来目标函数,求它的梯度。
其中S是样本集,样本集的大小相对于N来说很小。但是他也不能太小。只要有了梯度,很多算法都能用上了,比如说他文章中提到梯度方法,Newton-CG方法。S中的元素可以在每次迭代的时候随机选取。
但是需要面临的一个问题就是如何确定S的大小。他给出了一个公式用来确定S的大小是否合适。
$\| \nabla J_S(w) – \nabla J(w) \|_2 \le \theta \| \nabla J(w) \|_2 $
这个式子的含义就是样本集上的近似梯度和真实梯度足够接近。当然这个又回到了老问题,就是真实梯度计算量太大。于是他又做了一些近似变换,使得只需要计算在样本集S上的方差即可近似估计上式是否满足。
$ \frac{ \| Var^2_S( l(w; i) ) \|_1 }{ \| S \| } \le \theta ^2 \| \nabla J(w) \|_2 ^2 $
这样就可以每次迭代验证一下S是否足够大,如果不够大就扩大一下。
这个技巧部分解决了我对大规模优化计算的一些困惑,他可以利用上很多经典优化算法,并且又能让每次迭代的运算量不会太大。这个技巧也使得并行计算容易用上去了。
后面考虑去使用一下,算算某个实际例子测试一下效果。
Nocedal这篇论文的链接:http://users.eecs.northwestern.edu/~nocedal/PDFfiles/dss.pdf

libFM学习感想

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

Continue reading »

大规模问题快速算法的困惑

最近所里请了南京大学何炳生老师来做系列报告,他主要研究一阶算法,所谓一阶算法,只利用一阶最优性条件,通常借助一阶信息(梯度,Jacobi矩阵),不用二阶信息(Hession)。对于大规模问题来讲,这样做会节约很多计算量。当然他主要做理论,演示了如何利用他的方法简单和巧妙的证明一些算法的全局收敛性,感觉很有收获。

Continue reading »

The Art of Lemon队的KDD CUP 2011 Track 2解决方案大致思路

随着KDD CUP 2011的结束,需要开始总结我们的解决方案了。我们在最终测试集Test2中排名第二,和在排行榜中测试集Test1上的排名是一致的。我先发一篇Blog大致总结一下我们的方案,一来自己回顾和理清整个过程便于后面详细的写Solution Paper,二来与大家分享我们队的成果。

Continue reading »

数据挖掘与推荐系统

一直没有写Blog,最近再一次决心积累知识,将blog发扬光大。
此blog仍然寄居在好友的服务器上,再次感谢~

我从未正式的学习过数据挖掘,但是以前在数学建模课程上对某些方法略有了解:决策树,SVM,模拟退火,遗传算法,蚁群算法,神经网络等。不过仅仅是知道而已。推荐系统算是数据挖掘中一类很有意思的问题。

Continue reading »