专栏首页AI科技时讯FM:Factorization Machines

FM:Factorization Machines

... We introduce Factorization Machines (FM) which are a new model class that combines the advantages of Support Vector Machines (SVM) with factorization models ... In contrast to SVMs, FMs model all interactions between variables using factorized parameters. Thus they are able to estimate interactions even in problems with huge sparsity (like recommender systems) where SVMs fail...

TL;DR,按我个人的理解就是:

  1. 这是一种新的模型类型,可以用作任意Real-Value Vector的分类,跟LR/SVM一样
  2. 它可以拿来对不同变量之间的Interaction建模(比如不同Feature之间的相关性),这点跟带kernel的SVM类似;它胜过LR的也是这点,因为LR只是一个线性模型
  3. 它胜过SVM的地方在于,它使用了"factorization"(简单来说,理解为矩阵分解?)来进行建模,这就使得它可以用于非常稀疏的Features,而SVM更适合用于Dense Feature,在Sparse Feature上表现并不好

下面进入技术细节

模型结构

我们先从Logistic Regression出发,回顾一下LR的Score Function

基本就是一个线性模型,对输入Feautre X的每一个纬度有一个参数w_i。好处是非常简单,非常容易Scale Up,得到的泛化能力一般都还挺不错,因此在工业界得到广泛应用;坏处就是建模能力有限,毕竟只是一个线性模型。

那么,下面是FM的Score Function

这里只是二阶的情况(二阶的意思是对变量两两之间关系建模,三阶或更高就是对三个或更多个变量之间的关系进行建模),也是一般实际场景所用的模型。可以看到,跟LR相比,多出来一项是

,其中

是参数矩阵

中的一行,而V是一个 N x k 的矩阵。也就是说,对X中的每一个变量,我们会用一个k维的向量(记住是一个向量,这很重要,后面会提到为什么)来建模,然后每两个变量之间的Interaction,就用这两个k维向量的内积来模拟。

Scalability

前面讲到LR的优势之一是非常Scalable,所以在工业界得到广泛应用——工业界一般有大量数据,但是计算资源有限啊,而且对实时性要求非常高,所以很多很酷炫,理论效果很好的模型反而得不到重用,就是因为Scalability的问题。前面看到,LR是线性的,基本是O(N)的复杂度;FM加了一个新的项之后,新加的那项看起来似乎需要

的复杂度,这似乎是不可忍受的复杂度,那为什么FM还能得到广泛应用呢?

主要原因就是,原作者通过一个数学Trick,把新加项的计算复杂度降到了O(kN) (k是可以自己选择的参数,一般会远远远远小于N,所以基本就相当于O(N)了)。直接上原论文的图,不感兴趣的可以跳过:

得到这个牛逼的公式之后就可以直接上梯度下降了:)

深究与SVM的优劣——为什么这个方法在Sparse Data下可以Work?

我们把上面FM的Score Function和一个带有多项式Kernel(Degree=2)的SVM比较。我们知道,简化来看,带Kernel的SVM可以看作先把输入X投影到另外一个特征空间,再做线性分类的算法。一个二项式kernel的SVM,相当于对输入Feature做了如下的变换:

那么Score Function就是:

可以看到基本上最大的区别就在于模拟变量两两Interaction的一项:在SVM里面,对x_i 和x_j的Interaction,以及x_i和x_k之间的interaction的建模,也就是

,是相互独立的参数;但是在FM里面,这两者互不独立,因为

都依赖于

。这点看似减少了模型的自由度,但是Sparse Feature的情况下发挥出了巨大的作用(以下为个人理解):

对于SVM来说,

必须在有足够多的满足

样本存在的情况下,才能得到很好的训练。但是在输入稀疏的情况下,在输入特征X里面大部分的

值都是0,更不必提

同时不为0了。所以SVM在这种情况下不能得到很好的训练。

反观FM,尽管要训练

也依赖于

,但是好处是,所有其他非0的

都会成为梯度的一部分,这样对于

的训练就有明显更多的训练数据,可以更好地训练出合适的参数。

同样的道理,我们平常在工业界里面常常采用的N-Gram Logistic Regression (人为对输入特征对二项式的变换,再把得到之后的特征拿LR进行训练),也由于同样的问题,无法和FM在效果上媲美。

值得注意的是,这个特性是FM是优势也是它的弊病。在输入特征比较稠密的情况下,其实FM的效果应该是并不如SVM的,因为SVM的模型自由度更高。

总结

FM作为一个通用的模型,在Scalability上可以和LR媲美,又可以拿来对变量之间的Interaction建模,在工业界中被广泛应用于推荐系统,但理论上也可以应用于一般的分类问题。

Steffen Rendle. Factorization Machines, ICDM (CCF-B), 出自大阪大学。2010年。

本文分享自微信公众号 - AI科技时讯(aiblog_research),作者:知乎

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Factorization Machine模型的各种变式

    FM模型最早由Steffen Rendle在2010年提出,解决了稀疏数据场景下的特征组合问题,在广告、推荐等领域被广泛使用。FM模型简单而且效果好,可以作为业...

    用户3578099
  • 关于CNN图像分类的一份综合设计指南

    对于计算机视觉任务而言,图像分类是其中的主要任务之一,比如图像识别、目标检测等,这些任务都涉及到图像分类。而卷积神经网络(CNN)是计算机视觉任务中应用最为...

    用户3578099
  • FNN: Deep Learning over Multi-field Categorical Data

    原论文:Deep learning over multi-field categorical data

    用户3578099
  • jmeter安装教程

    地址:http://jmeter.apache.org/download_jmeter.cgi

    IT云清
  • Factorization Machine模型的各种变式

    FM模型最早由Steffen Rendle在2010年提出,解决了稀疏数据场景下的特征组合问题,在广告、推荐等领域被广泛使用。FM模型简单而且效果好,可以作为业...

    用户3578099
  • 机器学习|支持向量机参数求解

    01 — 支持向量机 支持向量机的简称为SVM,能在已知样本点很少情况下,获得很好的分类效果。 02 — SVM分类两个点 已知两个样本点,如果用SVM模型,决...

    double
  • 学习SVM(五)理解线性SVM的松弛因子

    学习SVM(一) SVM模型训练与分类的OpenCV实现 学习SVM(二) 如何理解支持向量机的最大分类间隔 学习SVM(三)理解SVM中的对偶问题 ...

    chaibubble
  • Qt识别文件类型的正确姿势

      一般识别图片类型方法: 虽然这一方法可以实现识别图片类型,但是维护起来相对困难。如果真的要识别所有的文件是否是图片类型,还需要添加更多的判断方法。

    Qt君
  • 《吊打面试官》系列-秒杀系统设计

    Redis在互联网技术存储方面使用如此广泛,几乎所有的后端技术面试官都要在Redis的使用和原理方面对小伙伴们进行360°的刁难。

    敖丙
  • 实例讲解PHP异常PHP异常的概念内置异常类异常可以冒泡传递自定义异常类自定义异常处理器像处理异常一样处理错误

    章鱼喵

扫码关注云+社区

领取腾讯云代金券