FM模型的算法思想

本章涉及到的知识点清单：

1、LR模型方程

2、多项式模型方程

3、FM模型方程

4、矩阵分解

5、FM模型化简

6、损失函数

7、目标函数

8、最优化目标函数

9、FM模型的算法步骤

10、案例演示

11、FM模型的优势

一、LR模型方程

对于监督学习，机器学习模型的预测是一个估计函数 $\hat{y}$ （映射F）

监督学习

其中 $X$ 属于n维特征向量，即 $X \ \epsilon \ \mathbb{R}^{n}$ ， $y$ 属于目标值，回归问题中 $y \ \epsilon \ \mathbb{R}$ ，二分类问题中 $y \ \epsilon \ \{ -1,+1 \}$

我们首先回顾一般的线性回归方程LR，对于输入任意一个n维特征向量 $X = (x_{1},x_{2},...,x_{n})$ ，建模估计函数 $\hat{y}(X)$ 为

LR模型方程

LR模型的参数为： $w_{0} \ \epsilon \ \mathbb{R}$ ， $w \ \epsilon \ \mathbb{R^{n}} = (w_{1},w_{2},...,w_{n})$

从LR模型方程中我们可以看到：

（1）各个特征分量 $x_{i}$ 和 $x_{j}$ $(i \neq j)$ 彼此之间是独立的

（2） $\hat{y}(X)$ 将单个特征分量线性的组合起来，却忽略了特征分量彼此之间的相互组合关系

对于特征的组合关系，我们定义：

（1）一阶特征：即单个特征，不产生新特征，如 $x_{1}$

（2）二阶特征：即两个特征组合产生的新特征，如 $x_{1}x_{2}$

（3）高阶特征：即两个以上的特征组合产生的新特征，如 $x_{1}x_{2}x_{3}$

所以LR模型只考虑了一阶特征的线性组合关系

二、多项式模型方程

为了克服模型欠缺二阶特征组合因素，我们将LR模型改写为二阶多项式模型

二阶多项式模型

其中 $x_{i}x_{j}$ 表示两个互异特征组合的二阶特征， $w_{ij}$ 表示二阶特征的交叉项系数

至此，该模型似乎已经加入了特征组合的因素，接下来只要学习参数即可

但是，上述二阶多项式模型却有一个致命的缺陷：

数据稀疏性普遍存在的实际应用场景中，二阶特征系数 $w_{ij}$ 的训练是很困难的

造成学习困难的原因是：

（1） $w_{ij}$ 的学习需要大量特征分量 $x_{i}$ 和 $x_{j}$ 都非零的样本

（2）样本本身是稀疏的，同时满足 $x_{i}x_{j} \neq 0$ 的样本非常稀少

所以多项式模型虽然加入了二阶特征组合，却受到数据稀疏的影响

三、FM模型方程

为了克服模型无法在稀疏数据场景下学习二阶特征系数 $w_{ij}$ ，我们需要将 $w_{ij}$ 表示为另外一种形式

为此，针对样本 $X$ 的第i维特征分量 $x_{i}$ ，引入辅助隐向量 $v_{i}$

辅助隐向量

其中k为超参数，表示特征分量 $x_{i}$ 对应一个k维隐向量 $v_{i}$ ，则将 $w_{ij}$ 表示为：

二阶特征系数

上式引入隐向量的含义为：

二阶特征系数 $w_{ij}$ 等价于：特征分量 $x_{i}$ 和 $x_{j}$ 对应的隐向量 $v_{i}$ 和 $v_{j}$ 的内积 $<v_{i}, v_{j}>$ ，这就是FM模型的核心思想

则我们将二阶多项式模型改写为FM模型

FM模型方程

从FM模型方程可知，FM模型的参数为：

FM模型的参数

各个参数的意义为：

（1） $w_{0} \in \mathbb{R}$ 表示FM模型的偏置

（2） $w \in \mathbb{R}^{n}$ 表示FM模型对一阶特征的建模

（3） $V \in \mathbb{R}^{n\times k}$ 表示FM模型对二阶特征的建模

参数的个数为： $1+n+nk$

模型的复杂度为： $O(n^2k)$

下面我们从数学的角度来分析FM模型方程的可行性

四、矩阵分解

我们引入下面几个矩阵

（1）每个特征 $x_{i}$ 对应的隐向量 $v_{i}$ 组成的矩阵 $V$ ：

V矩阵

即矩阵 $V$ 的第i行表示：第i维特征 $x_{i}$ 的隐向量 $v_{i}$

则矩阵 $V^{T}$ 为：

V矩阵转置

（2）多项式模型的二阶特征系数 $w_{ij}$ 组成的方阵 $W$

多项式模型的W方阵

（3）FM模型的二阶特征系数 $<v_{i}, v_{j}>$ 组成的方阵 $\hat{W}$

FM模型的W方阵

从上面三个矩阵，我们可以看到：

（1）方阵 $W$ 的非对角线上三角的元素，即为多项式模型的二阶特征系数： $w_{ij}$

（2）方阵 $\hat{W}$ 的非对角线上三角的元素，即为FM模型的二阶特征系数： $<v_{i}, v_{j}>$

由于 $\hat{W} = V \times V^{T}$ ，即隐向量矩阵的相乘结果，这是一种矩阵分解的方法

引用线性代数中的结论：

当k足够大时，对于任意对称正定的实矩阵 $\hat{W} \in \mathbb{R^{n\times n}}$ ，均存在实矩阵 $V \in \mathbb{R^{n\times k}}$ ，使得 $\hat{W} = V \times V^{T}$

所以FM模型需要保证 $\hat{W}$ 的正定性。由于FM只关心互异特征之间的关系（ $i>j$ ），因此 $\hat{W}$ 的对角线元素可以任意取值，只需将它们取足够大（保证行元素严格对角占优），就可以保证 $\hat{W}$ 的正定性

五、FM模型化简

从上述FM模型方程看，模型的复杂度的确是： $O(n^2k)$

不过，数学是奇妙的，我们可以改写模型的二阶项系数项

改写模型的二阶项系数项

对上述化简过程做一些解释：

第1个等号：对称方阵 $\hat{W}$ 的所有元素之和减去主对角线元素之和

第2个等号： $<v_{i}, v_{j}>$ 向量内积展开成累加形式

第3个等号：提出公共部分 $\sum_{f=1}^{k}$

第4个等号：表示为“和平方”减去“平方和”

带入化简后的表达式，FM模型方程为：

FM模型方程

其中参数个数为： $1+n+kn$

模型的复杂度为： $O(kn)$

可以看到通过数学上的化简，FM模型的复杂度降低到了线性级别

六、损失函数

利用FM模型方程，可以进行各种机器学习预测的任务，如回归、分类和排名等

对于回归问题，损失函数可以取最小平方误差函数

最小平方误差函数

对于分类问题，损失函数可以取logit逻辑函数

logit逻辑函数

七、目标函数

通过损失函数构造出目标函数为

目标函数

其中包含具体的损失函数 $loss$ 和估计函数 $\hat{y}(X)$ 。这里 $\hat{y}$ 即FM模型方程，损失函数 $loss$ 可以带入具体的可导函数（如logit函数）即可

八、最优化目标函数

最优化目标函数，即最优化模型方程的参数，即转化为下面最优化问题

优化目标函数

目标函数对模型参数的偏导数通式为：

目标函数对模型参数的偏导数

对于 $R^2$ 和或 $logit$ 作为损失函数而言， $loss$ 对模型估计函数 $\hat{y}(X)$ 的偏导数为：

loss对模型估计函数的偏导数

对于FM模型而言，优化的参数为： $\theta^{*} = \{w_{0}, \mathbf{w}, \mathbf{V}\}$ ，则FM模型方程对各个参数 $\theta^{*}$ 的偏导数为：

FM模型方程对参数的偏导数

于是对于FM模型的优化问题，我们可以采用SGD优化目标函数

九、FM模型的算法步骤

（1）初始化模型参数： $w_{0} \in \mathbb{R}，w \in \mathbb{R}^{n}, V \in \mathbb{R}^{n \times k} \rightarrow N(0，1)$

（2）遍历每个n维样本 $X$

（3）FM方程计算 $\hat{y}(X)$

（4）更新 $w_{0} \leftarrow w_{0} - \alpha \frac{\partial}{\partial w_{0}}l(\hat{y}_{i}(X|\theta^{*}), y_{i})$

（5）遍历 $X$ 样本中的每个特征 $x_{j}$ ， $j \in (1,2,...,n)$

（6）更新 $w_{j} \leftarrow w_{j} - \alpha \frac{\partial}{\partial w_{j}}l(\hat{y}_{i}(X|\theta^{*}), y_{i})$

（7）遍历 $x_{j}$ 的k维隐向量 $v_{f}$ ， $f \in (1,2,...,k)$

（8）更新 $v_{jf} \leftarrow v_{jf} - \alpha \frac{\partial}{\partial v_{jf}}l(\hat{y}_{i}(X|\theta^{*}), y_{i})$

十、案例演示

最后我们用python实现FM算法，数据场景为二分类问题

数据场景

损失函数我们使用 $logit$ 函数

损失函数

FM模型方程

SGD更新FM模型的参数列表

模型分类结果

十一、FM模型的优势

最后我们总结出FM模型的优势：

（1）FM模型对特征的一阶组合和二阶组合都进行了建模

（2）FM模型通过MF思想，基于K维的Latent Factor Vector，处理因为数据稀疏带来的学习不足问题

（3）FM模型的训练和预测的时间复杂度是线性的

（4）FM模型可以用于DNN的embedding

案例代码见：FM模型的算法思想

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

FM模型的算法思想

推荐阅读更多精彩内容