推荐算法：FM算法原理与实践

作者: 张虾米试错 | 来源:发表于2019-06-23 22:59 被阅读0次

一直对FM（Factorization Machines)算法知其然而不知其所以然，今天看了下推导过程，对原理有了新的认识，先做个记录。

提纲

FM原理
FM代码实践

1. FM原理

FM被提出是为了解决特征之间的关联性，比如在电商数据中，“USA”与“Thanksgiving”、“China”与“Chinese New Year”这样的关联特征，对用户的点击有着正向的影响。换句话说，"China"和"Chinese New Year"组合后，与最终的label有更正相关的联系。因此，学习特征之间的关联性是非常有帮助的。
表示特征之间的关联，最直接的方法的是构造组合特征。方法有两种：

人工构造
deep learning 、FM系列算法
FM模型是通过增加多项式项来表示特征之间的关联，这里只讨论二阶的模型：
$y = w_0 + \sum_{i=1}^n{w_ix_i}+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}w_{ij} x_ix_j$
其中， $n$ 表示特征的数量， $w_0,w_i,w_{ij}$ 都是模型参数。
从上式中可以看出，组合特征的参数有 $\frac{n(n-1)}{2}$ 个，任意两个参数之间独立。

然而，在数据稀疏性普遍存在的实际应用场景中，二次项参数的训练是很困难的。其原因是，回归模型的参数 $w$ 的学习结果就是从训练样本中计算充分统计量（凡是符合指数族分布的模型都具有此性质），而在这里交叉项的每一个参数 $w_{ij}$ 的学习过程需要大量的 $x_i$ 、 $x_j$ 同时非零的训练样本数据。由于样本数据本来就很稀疏，能够满足“ $x_i$ 和 $x_j$ 都非零”的样本数就会更少。训练样本不充分，学到的参数 $w_{ij}$ 就不是充分统计量结果，导致参数 $w_{ij}$ 不准确，而这会严重影响模型预测的效果（performance）和稳定性。

如果把 $w_{ij}$ 看做一个矩阵，则可以借鉴矩阵分解的方法，将 $w_{ij}$ 分解成 $V^TV$ ，即每个参数 $w_{ij}=<v_i, v_j>$ ，因此FM模型可以写成(只考虑二阶的情况)：
$y = w_0 + \sum_{i=1}^n{w_ix_i}+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}<v_i, v_j>x_ix_j$
其中， $v_i$ 是第 $i$ 维特征的隐向量，<,>表示点积，计算公式为：
$<v_i, v_j> = \sum_{f=1}^{k}v_{i,f}v_{j,f}$
其中， $k$ 表示隐向量的长度，并且 $k<<n$ 而公式可以看成：

线性模型+交叉项：前两项是线性回归模型，最后一项是二阶特征交叉项
交叉项 -->隐向量內积：将交叉项转换成隐向量內积求解

直观上看FM的算法复杂度是 $O(kn^2)$ ，但是通过公式转换，可以将复杂度优化到 $O(kn)$ ，具体如下：
$ab + ac + bc = \frac{1}{2} [(a+b+c)^2 - (a^2 + b^2 + c^2)]$

$\begin{aligned} \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}<v_i, v_j>x_ix_j \\ & =\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}<v_i, v_j>x_ix_j - \frac{1}{2}\sum_{i=1}^{n}<v_i, v_i>x_ix_i \\ & =\frac{1}{2}(\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{f=1}^kv_{i,f}v_{j,f}x_ix_j - \sum_{i=1}^{n}\sum_{f=1}^k v_{i,f}v_{i,f}x_ix_i) \\ & =\frac{1}{2}\sum_{f=1}^k(\sum_{i=1}^{n}v_{i,f}x_i\sum_{j=1}^{n}v_{j,f}x_j-\sum_{i=1}^{n}v_{i,f}^2x_i^2) \\ & =\frac{1}{2}\sum_{f=1}^k[(\sum_{i=1}^{n}v_{i,f}x_i)^2-\sum_{i=1}^{n}v_{i,f}^2x_i^2] \end{aligned}$

采用随机梯度下降SGD求解

$\frac{\partial y}{\partial \theta} =\begin{cases} 1 & \theta =w_0 \\ x_i & \theta = w_i \\ (x_i\sum_{j=1}^nv_{j,f}x_j) - v_{i, f}x_i^2 & \theta = v_{i,f} \end{cases}$

第3种情况的第一项其实是对 $\frac{1}{2}\sum_{i=1}^{n}{v_{i,f}x_i}^2$ 求导；第二项是对 $\frac{1}{2}\sum_{i=1}^{n}v_{i,f}^2x_i^2$ 求导。

在使用SGD训练模型时，每次只需要计算1次所有 $f$ 的 $\sum_{j=1}^nv_{j,f}$ ，这样计算 $\sum_{j=1}^nv_{j,f}$ 的复杂度为 $O(kn)$ ，模型参数为 $nk+n+1$ ，因此FM的复杂度为 $O(nk)$ 。

2. FM代码实践

代码主要参考FM.py，通过第1部分的式子可以看出，与LR相比，loss主要是多了多项式的部分，因此在LR代码的基础上加上多项式即可。

self.xv = tf.multiply(df_v, batch_embedding) # none * n * embedding_size
sum_square = tf.square(tf.reduce_sum(self.xv, axis=1)) # none * embedding_size
square_sum = tf.reduce_sum(tf.square(self.xv), axis=1) # none * embedding_size
fm_result = 0.5 * (tf.subtract(sum_square, square_sum))

其中， $self.xv$ 表示 $v_{i,f}x_i$ ， $sum\_square$ 计算的是 $(\sum_{i=1}^{n}v_{i,f}x_i)^2$ , $square\_sum$ 计算的是 $\sum_{i=1}^{n}v_{i,f}^2x_i^2$ ，所以上面这段代码计算的是多项式的loss.

tensorflow版本

import tensorflow as tf
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score, roc_auc_score
import numpy as np


class FactorizationMachine:

    def __init__(self, n_dim=1, k=4, learning_rate=0.05, epochs=8):
        self._learning_rate = learning_rate
        self._n_dim = n_dim
        self._k = k
        self._epochs = epochs
        self.sess = tf.Session()
        self.x_input = tf.placeholder(shape=[None, self._n_dim], dtype=tf.float32)
        self.y_input = tf.placeholder(shape=[None, 1], dtype=tf.float32)
        # 初始化W和V
        self.w = tf.Variable(tf.truncated_normal(shape=[self._n_dim, 1], dtype=tf.float32))
        self.V = tf.Variable(tf.truncated_normal(shape=[self._n_dim, self._k], dtype=tf.float32))
        self.b = tf.Variable(tf.truncated_normal(shape=[1, 1]))
        self.linear = tf.add(self.b, tf.matmul(self.x_input, self.w))
        self.quadratic = 1/2 * tf.reduce_sum(tf.square(tf.matmul(self.x_input, self.V)) - tf.matmul(tf.square(self.x_input), tf.square(self.V)), axis=1, keepdims=True)
        self.y_out = self.linear + self.quadratic
        self.y_pred = tf.round(tf.sigmoid(self.y_out))
        self.loss = tf.reduce_mean(tf.nn.sigmoid_cross_entropy_with_logits(logits=self.y_out, labels=self.y_input))
        self.train_op = tf.train.GradientDescentOptimizer(self._learning_rate).minimize(self.loss)
        self.accuracy = tf.reduce_mean(tf.cast(tf.equal(self.y_pred, self.y_input), tf.float32))
        init = tf.global_variables_initializer()
        self.sess.run(init)

    def train(self, X, Y, iterations=1000, batch_size=16, validation_size=0.1):
        x_train, x_test, y_train, y_test = train_test_split(X, Y, test_size=validation_size)
        for epoch in range(self._epochs):
            for i in range(iterations):
                rand_idx = np.random.choice(x_train.shape[0], size=batch_size)
                rand_x = x_train[rand_idx]
                rand_y = y_train[rand_idx]
                self.sess.run(self.train_op, feed_dict={self.x_input: rand_x, self.y_input: rand_y})
                if i % 100 == 99:
                    loss = self.sess.run(self.loss, feed_dict={self.x_input: x_test, self.y_input: y_test})
                    acc = self.sess.run(self.accuracy, feed_dict={self.x_input: x_test, self.y_input: y_test})
                    print('epoch = {}, iteration ={}, loss = {}, accuracy ={}'.format(epoch, i, loss, acc))

    def predict(self, x):
        return self.sess.run(self.y_pred, feed_dict={self.x_input: x})

3. FM优缺点

3.1 优点

以下优点应该是和传统机器学习方法，如LR、SVM等对比。

总结一下，FM模型的优点有如下几点：

FM模型的参数支持非常稀疏的特征，而SVM等模型不行

FM的时间复杂度为，并且可以直接优化原问题的参数，而不需要依靠支持向量或者是转化成对偶问题解决

FM是通用的模型，可以适用于任何实数特征的场景，其他的模型不行

前面两点是因为FM可以将交叉项转换成向量点积的方式，因此算法复杂度降低成 $O(kn)$ ，又因为 $k$ 为常数项，所以算法复杂度为 $O(k)$ 。

推荐算法：FM算法原理与实践

提纲

1. FM原理

2. FM代码实践

3. FM优缺点

3.1 优点

参考资料

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读