聊聊因子分解机（FM）

说到FM先说一个叫交叉特征的事，因为特征都是相互独立的，我们想要找到一些组合特征，只能两两交叉相乘，所以我们在线性模型加一个多项式
$\hat y = f(\vec x) = w_0 + \sum_{i = 1}^{n}w_ix_i + \sum_{0 < i < j <= n}w_{i, j}x_ix_j.$
这是不是看起来就是一个SVM模型：核函数选择为二阶多项式核
看起来很完美，但是我们的特征都是独热编码（OneHot），所以 $x_ix_j$ 的结果大多数情况下就是0，这样的话后面这个多项式就没法学习了，就算可以学习，如果出现不是0的情况就会出现问题，泛化能力很差。
因子分解机（FM）我们的主角就是解决这个问题：
FM 模型的解决办法是为每个维度的特征（ $x_i$ ）学习一个表征向量（ $v_i$ ，其实可以理解为是特征 ID 的 embedding 向量）。而后将 $x_i$ 和 $x_j$ 的乘积的权重设定为各自表征向量的点积。
$\hat y = f(\vec x) = w_0 + \sum_{i = 1}^{n}w_ix_i + \sum_{0 < i < j <= n}\langle \vec v_i, \vec v_j\rangle x_ix_j.$
中间的推倒过程在后面。简化结果：
$\hat y = f(\vec x) = w_0 + \sum_{i = 1}^{n}w_ix_i + \frac{1}{2}\sum_{f= 1}^{k}((\sum_{i=1}^{n} \vec v_{i,f} x_i)^2-\sum_{i=1}^{n}\vec v_{i,f}^2 x_i^2)$
这里很容易看到没有了特征相乘了，接下来说说效率问题；
考虑到 FM 模型会对特征进行二阶组合，在有 $n$ 个原始特征时，交叉特征就会有 $\frac{n ^ 2 - n}{2}$ 个。因此，如果不做任何优化，FM 模型的复杂度会是 $O(n^2)$ ，具体来说是 $O(kn^2)$ （其中 $k$ 是表征向量的长度）。在特征规模非常大的场景中，这是不可接受的。
那么问题来了，是否有办法将复杂度降低到 $O(kn)$ 呢？答案是可以的，我们来看针对特征交叉项的一系列变换。

$\begin{aligned} \sum_{0 < i < j <= n}\langle \vec v_i, \vec v_j\rangle x_ix_j &{} = \sum_{i = 1}^{n - 1}\sum_{j = i + 1}^{n} \langle \vec v_i, \vec v_j\rangle x_ix_j \\ &{} = \frac{1}{2}\sum_{i = 1}^{n}\sum_{j = 1}^{n}\langle \vec v_i, \vec v_j\rangle x_ix_j - \frac{1}{2}\sum_{i = 1}^{n}\langle \vec v_i, \vec v_i\rangle x_ix_i \\ &{} = \frac{1}{2}\biggl(\sum_{i = 1}^{n}\sum_{j = 1}^{n}\sum_{d = 1}^{k}\vec v_{i, d}\vec v_{j, d}x_ix_j - \sum_{i = 1}^{n}\sum_{d = 1}^{k}\vec v_{i, d}^2x_i^2\biggr) \\ &{} = \frac{1}{2}\sum_{d = 1}^{k}\biggl(\sum_{i = 1}^{n}\sum_{j = 1}^{n}\vec v_{i, d}\vec v_{j, d}x_ix_j - \sum_{i = 1}^{n}\vec v_{i, d}^2x_i^2\biggr) \\ &{} = \frac{1}{2}\sum_{d = 1}^{k}\biggl(\Bigl(\sum_{i = 1}^{n}\vec v_{i, d}x_i\Bigr)\Bigl(\sum_{j = 1}^{n}\vec v_{j, d}x_j\Bigr) - \sum_{i = 1}^{n}\vec v_{i, d}^2x_i^2\biggr) \\ &{} = \frac{1}{2}\sum_{d = 1}^{k}\biggl(\Bigl(\sum_{i = 1}^{n}\vec v_{i, d}x_i\Bigr)^2 - \sum_{i = 1}^{n}\vec v_{i, d}^2x_i^2\biggr). \end{aligned}$

等式第一行是一个平凡的变换，很容易理解。

等式第二行修改了求和符号的范围。原本的求和符号中有 $\frac{n ^ 2 - n}{2}$ 项；变换之后第一项中的求和符号有 $n^2$ 项，第二项中的求和符号有 $n$ 项。因此两式恰好相等。

等式第三行是对向量内积的展开，很容易理解。

等式第四行是运用了加法的结合律，将 $\sum_{d = 1}^{k}$ 抽到外面，这步容易理解。

等式第五行是连续两次逆向使用了乘法对加法的分配率（提取公因子），这一步可能稍微难理解一些。简便起见，我们将 $\vec v_{i, d}x_i$ 记作 $a_i$ ；将 $\vec v_{j, d}x_j$ 记作 $a_j$ 。则变换前的公式记作 $\sum_{i = 1}^{n}\sum_{j = 1}^{n}a_ia_j$ 。将它展开是：

$\begin{aligned} \sum_{i = 1}^{n}\sum_{j = 1}^{n}a_ia_j = {}& a_1a_1 + a_1a_2 + \cdots + a_1a_n + \\ {}& a_2a_1 + a_2a_2 + \cdots + a_2a_n + \\ {}& \cdots + \\ {}& a_na_1 + a_na_2 + \cdots + a_na_n \\ = {}& a_1\bigl(a_1 + a_2 + \cdots + a_n\bigr) + \\ {}& a_2\bigl(a_1 + a_2 + \cdots + a_n\bigr) + \\ {}& \cdots + \\ {}& a_n\bigl(a_1 + a_2 + \cdots + a_n\bigr) \\ = {}& a_1\Bigl(\sum_{j = 1}^{n}a_j\Bigr) + a_2\Bigl(\sum_{j = 1}^{n}a_j\Bigr) + \cdots + a_n\Bigl(\sum_{j = 1}^{n}a_j\Bigr) \\ = {}& \sum_{i = 1}^{n}a_i\sum_{j = 1}^{n}a_j \\ = {}& \Bigl(\sum_{i = 1}^{n}\vec v_{i, d}x_i\Bigr)\Bigl(\sum_{j = 1}^{n}\vec v_{j, d}x_j\Bigr). \end{aligned}$
等式第六行也很明显。第五行的结果中的两个求和项仅仅是下标不同，实际上完全是一回事，因此直接平方就好了。

如此一来，FM 的预测公式变成了下面这样

$\begin{aligned} \hat y &{} = f(\vec x) \\ &{} = w_0 + \sum_{i = 1}^{n}w_ix_i + \frac{1}{2}\sum_{d = 1}^{k}\biggl(\Bigl(\sum_{i = 1}^{n}\vec v_{i, d}x_i\Bigr)^2 - \sum_{i = 1}^{n}\vec v_{i, d}^2x_i^2\biggr). \end{aligned}$

显然，它的复杂度是 $O(kn)$ 。考虑到特征的稀疏性，尽管 $n$ 可能很大，但很多 $x_i$ 都是零。因此其实际复杂度应该是 $O(k\bar n)$ ——其中 $\bar n$ 表示样本不为零的特征维度数量的平均值。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 230,002评论 6赞 542
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 99,400评论 3赞 429
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 178,136评论 0赞 383
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 63,714评论 1赞 317
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 72,452评论 6赞 412
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 55,818评论 1赞 328
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 43,812评论 3赞 446
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 42,997评论 0赞 290
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 49,552评论 1赞 335
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 41,292评论 3赞 358
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 43,510评论 1赞 374
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 39,035评论 5赞 363
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 44,721评论 3赞 348
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 35,121评论 0赞 28
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 36,429评论 1赞 294
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 52,235评论 3赞 398
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 48,480评论 2赞 379

聊聊因子分解机（FM）

推荐阅读更多精彩内容