之前讲过一个SVD算法，它能够通过一个U-I矩阵分解，然后把User和Item分别变成想要的向量表示，然后通过向量相似度的计算做关联推荐或者user2item的推荐。
这个算法有一个局限性，就是它没有办法用到一些重要的特征，如果推荐的优化目标是点击率的话，那么本身Item的点击率是一个很重要的特征，我们有没有办法把这些特征也建模到这个算法中呢，这就是Factorization Machines算法了，中文叫向量分解机，一般直接简称Fm算法。
定义问题
在逻辑回归算法中，我们定义了一个线性模型，基本上是一个最简单的二分类模型，如果问题稍微复杂一点，我们可能要在特征工程上做很多事情，简单来说就是处理特征或者特征组合，那么有没有可能直接把特征组合建模到模型中呢，我们这样定义
问题定义好了，但是如果我们直接去求解这个问题的话，有两方面的问题
- 这里的\(x_i\)是对特征进行one-hot后的，比如itemId或者ItemTag之类本身one-hot后就很稀疏，而我们后面做特征交叉用了\(x_i*x_j\)，那么就必须保证两个都必须不为0，这对于稀疏矩阵来说很难，这样学习出来模型效果和稳定性无法保证。
- 直接去学习的话复杂度是\(O(n^2)\)的复杂度，因为n本身就很大，一般都是千万到亿级别的，这个复杂度直接学习比较困难。
问题变换
那么我们借鉴之前SVD的思路，把\(w_{i,j}\)这个参数矩阵去做分解，变成一个nk的矩阵和一个kn的矩阵的乘积，这样做的好处是对于所有的特征，我们都能够用一个向量(vec)来表示，向量表示后就可以很灵活的计算各种相似度了，这也是现在很火的各种embeding表示的思想。那么我们可以变换为
\[y(x) = w_0 + \sum_{i=1}^n{w_i x_i} = \sum_{i=1}^{n} \sum_{j=i+1}^n <v_i,v_j> x_i x_j \tag 2\]这里\(v_i,v_j\)分别是两个向量，表示i,j特征的embeding，但是这样做会发现有一个很大的问题，复杂度变得更高了，变成\(O(kn^2)\)，别着急，我们变换一下
\[\begin{eqnarray*} combine & = & \sum_{i=1}^n \sum_{j=i+1}^n <v_i, v_j> x_i x_j \\ & = & \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n <v_i,v_j>x_i x_j - \frac{1}{2} \sum_{i=1}^n <v_i,v_i> x_i x_i \\ & = & \frac{1}{2} (\sum_{i=1}^n \sum_{j=1}^n \sum_{f=1}^k v_{i,f} v_{f,j} x_i x_j - \sum_{i=1}^n \sum_{f=1}^k v_{i,f} v_{i,f} x_i x_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 x_{i,f}^2 x_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}^2 x_i^2] \end{eqnarray*} \tag 3\]这里第一步变换中本来两层循环，第二层从i+1开始，但是我们让两个都从1开始，那么相当于算了两次，所以除以二，另外还要去掉对角线上的值。 第二步变换是对矩阵做展开，因为我们前面说了\(v_i,v_j\)是两个向量，而这个向量是k维的，直接展开之后就多了一层k的循环。 第三步矩阵分解的k维向量提出来放到最外层，最后一步因为都是计算n维向量和x的乘积，所以可以直接合并变成平方。
这样下来复杂度变成了\(O(kn)\)，而k « n，计算起来就很容易了。
优势
- 计算效率高，因为k是一个常数，所以复杂度和lr差不多，训练速度也差不多。
- 解决矩阵稀疏性问题，通过矩阵分解，让每一个参数通过特征隐含向量的内积表示，能够使得学习更加充分。
- 提高了模型预估能力，比如用户特征是性别，物品特征是类型，分为汽车和化妆品，而训练数据中没有男性喜欢化妆品，但是假设让我们预估某个男性对化妆品的喜好程度，我们可以直接通过计算男性的embeding向量和化妆品的embeding向量的相似度，同样可以预估。
- 相比较其他模型，矩阵分解类算法是他的一个特殊情况，之前讲过的SVD，相当于是只有userid和itemid这两类特征的fm。当然另一方面，也可以从这个角度去理解fm算法，比如对于一个nm的U-I矩阵，我们通过矩阵分解为两个矩阵nk和km的乘积，另一方面我们有一个np的item和年龄的矩阵，我们可以分解为两个矩阵nk和kp的矩阵，那么对于这两个物品embeding矩阵n*k显然是不一样的，但是如果我们在fm中userId和年龄特征放进去训练，出来结果会是综合了年龄和userId的，它会把年龄的特征权重也吸收到模型中。
- 实用性强，可以通过分解后的向量计算向量相似度做u2i或者i2i召回，也可以通过训练做精排模型打分。
求解方法
最简单的就是梯度下降法，模型的各个参数梯度如下。
\[\frac{\partial}{\partial \theta} = \left\{ \begin{aligned} 1 & , & \ \ \ \ if \ \theta \ is \ w_0 \\ x_i & , & \ \ \ if \ \theta \ is \ w_i \\ x_i \sum_{j=1}^n v_{j,f} x_j - v_{i,f} x_i^2 & , & \ \ \ \ if \ \theta \ is \ v_{i,f} \end{aligned} \right.\]ffm
ffm顾名思义，引入filed -aware概念，之前fm每个特征做交叉的时候为两个向量的乘积，比如上面的女性对化妆品偏好，北京人群对化妆品的偏好，按照fm，化妆品对女性和对base北京计算权重用的是相同的向量，但是很显然这两个差异很大，计算为一个会引入很大的噪声。
所以ffm就是来解决这个问题的，对于不同类型的特征使用不停的field，比如上面，化妆品会计算多个向量，之后给性别用一套向量，给所在地城市用一套向量。
\[y(x) = \sum_{i=1}^{n} \sum_{j=i+1}^n <v_{i,f1},v_{j,f2}> x_i x_j \tag 4\]引入feild之后，模型首先更精确符合实际情况了，但是但来一个问题是复杂度变大，变成f * k * n。
