FM

FM模型（Factorization Machines）

1.线性回归

​ 回归是一种预测性的，我们是主要根据已有的数据来训练一个回归模型，来预测将要到来的数据的类型。

\text{假设目标值与特征之间线性相关}\\ \hat{y} = wx+b\\\\ \text{我们在定义一个损失函数，假设为均方误差：}\\ L=\frac{1}{n} \sum_{i=1}^{n}(\hat{y_i}-y_i)^2 = \frac{1}{n}\sum_{n=1}^{n}(wx_i+b-y)^2 \\\\ \text{所以现在要最小化损失函数,得到对应的w^*,b^*，即：}\\ (w^*,b^*) = arg \min_{w,b} \sum_{i = 1}^{n}(wx_i+b-y_i)^2

求解$ w^* ,b^*$的方式有两种：

(1)最小二乘法

$\frac{\partial L}{\partial w} = \frac{2}{n} \sum_{i = 1}^{n}(wx_i+b-y_i)x_i = \frac {2w}{n}\sum_{i=1}^{n}x_i^2-\frac{2}{n} \sum_{i=1}^{n}(y_i-b)x_i\\ \frac{\partial L}{\partial b} = \frac{2}{n}\sum_{n=1}^{n}(wx_i+b-y_i) = 2b+\frac{2}{n}\sum_{i=1}^{n}(wx_i-y_i)$

接下来另两个偏导数等于0，得到 w,b最优解的闭式解：

$\frac{\partial L}{\partial b} = 0 \Rightarrow b=\frac{\sum_{i=1}^{n} (y_i-wx_i)}{n} \\\\ \frac {\partial L}{\partial w} = 0 \Rightarrow w\sum_{i=1}^{n}x_i^2-\sum_{i=1}^{n}y_ix_i+b\sum_{i=1}^{n}x_i = 0 \Rightarrow w\sum_{i=1}^{n}x_i^2-\sum_{i=1}^{n}y_ix_i+\sum_{n=1}^{n}x_i\frac{\sum_{i=1}^{n}(y_i-wx_i)}{n}= 0 \\\\ \Rightarrow w\sum_{i=1}^{n}x_i^2-\sum_{i=1}^{n}y_ix_i+\frac{1}{n} (\sum_{n=1}^{n}x_i\sum_{i=1}^{n}y_i)-\sum_{n=1}^{n}x_i\frac{\sum_{i=1}^{n}wx_i}{n} = 0\\\\ \Rightarrow w\sum_{i=1}^{n}x_i^2-\sum_{i=1}^{n}y_ix_i+\frac{1}{n} (\sum_{n=1}^{n}x_i\sum_{i=1}^{n}y_i)-\frac{1}{n} w(\sum_{n=1}^{n}x_i)^2 = 0\\\\ \Rightarrow w (\sum_{i=1}^{n}x_i^2 - \frac{1}{n} (\sum_{n=1}^{n}x_i)^2) = \sum_{i=1}^{n}x_iy_i-\overline x\sum_{i=1}^{n}y_i\\\\ \Rightarrow w = \frac{\sum_{i=1}^{n}y_i(x_i-\overline x)}{\sum_{i=1}^{n}x_i^2-\frac{1}{n} (\sum_{n=1}^{n}x_i)^2 }$

(2)梯度下降

​ 梯度下降的核心是不断的更新w,b

$w \leftarrow w-\alpha\frac{\partial L}{\partial w} \\\\ b \leftarrow b-\alpha\frac{\partial L}{\partial b} \\\\$

2.逻辑回归跟线性回归

$\text{逻辑回归} \qquad \qquad\qquad\qquad\qquad\text{线性回归}\\\\ \text{判别模型:}f_{w,b}(x) = \sigma(\sum_ix_iy_i+b)\qquad \qquad f_{w,b} = \sum_ix_iy_i+b\\ \text{输出:} \in(0,1) \qquad \qquad\qquad\qquad\qquad\text{输出:任意值}$

3.FM模型（因子分解机）

​ 传统的模型中，特征都是独立的。但是有些特征之间存在交互作用，比如我们说一件衣服，颜色跟版型都会影响穿上的效果；比如同一个版型，一件黑色，一件白色，那么一般我们穿上之后总会觉得黑色的穿上显瘦。

​ FM考虑到了特征之间的交互作用，并对特征进行了交叉组合。

$\text{一般的线性模型:}\quad \hat{y} =w_0+w_1x_1+w_2x_2+......+w_nx_n = w_0+\sum_{i=1}^{n}w_ix_i \\\\ \text{FM的模型，我们以二阶多项式模型为例:}\quad\hat{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\\ (\text{其中}\\\text{n: 样本特征的个数，类别特征onehot后的维度，两两交互可以得到} \frac{n(n-1)}{2} \text{个交叉项。}\\ w_{ij}:\text{是每两个特征之间的权重，用于表达这对特征的重要性。})$

Q1:

​ 我们分析一下样本经过onehot编码，我们假如样本有n个特征，我们用$x_i$ 来表示第 i 个特征，这个特征经过onehot编码后可能是一个m*1的数据（而且每一个特征都不一定是m个）。

​ 那么，问： 我们需不需要对该one-hot之后的样本进行补全，比如我们取特征可以选择的数量最多的为m*1,那么其他特征可选择的量小于m,我们用不用把这个样本矩阵用0 来补齐为 n *m 的矩阵？

​ 答：经过在网上资料的查阅，这个是不需要补齐的，我们在使用到特征的时候使用的方式都是$x_i$ 来代替样本的第 i 个特征的编码向量，不需要进行补全。

​ 再问：假如我们补齐了这个矩阵为n*m的矩阵那么上面公式中 $\sum_{i=1}^{n-1}\sum_{j = i+1}^{n}w_{ij}x_ix_j$ 再计算的时候如何计算，我们倒推一下， $x_i$ 是一个m * 1的矩阵，那么$w_{ij}x_i$的shape应该是 （）*1的，无法与$x_j$相乘，所以这其中有涉及到矩阵转置吗？如果有，为什么公式不表达？还有如果我们没有补齐，那么计算时，涉及到的维度更加麻烦，怎么解决？

​ 答：计算过程中确实涉及到了矩阵的转置，我们没有进行补全的操作，我们样本的每个特征的编码向量也不固定。 此外我查阅到了$w_{ij}$的一个更详细的表达，下面是更新后的FM公式：

$\hat {y} = w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}<v_i^T,v_j>x_ix_j$

​ 其中$v_i,v_j$是两个隐向量，所有的隐向量构成了一个隐向量矩阵，这个矩阵是一个n*k的矩阵，其中n代表了特征的数量，k代表了隐向量的维度。

​ 这里强调一下： 隐向量矩阵是一个要通过优化算法来不断更新的矩阵。他的维度与隐向量的维度k有关，是初始化的一个值，跟特征维度无关。（注特征维度是指一个特征有多少个可选择项）

Q2:

​ 对于这个公式我有我的疑惑，我在许多地方看到这两个w，我不知道这两个w 是不是同一个矩阵，所以我们接下来从矩阵运算以及实际意义的角度分析一下。

​ 从$w_ix_i$ 相乘，我们知道 $x_i$ 应该是可以用 n*1 的矩阵来表示，那么$w_i$ 就应该是一个 m * n 的矩阵，代表着第 i 个特征的权重。

​ 从$w_{ij}x_ix_j$ 中，我们知道，$w_{ij}$应该是一个n*n的矩阵，且$w_{ij}$又代表样本 i 特征跟样本 j 特征之间的关系权重。

​ 所以，这其实是两个矩阵，我是不太理解为什么要写成一样的符号，对于初学者而言，总会觉得会不会这两个矩阵被大牛给统一了。

Update:

​ 首先是FM的一个表达式：

$\hat{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\\\\ \hat {y} = w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}<v_i^T,v_j>x_ix_j$

​ 这个表达式的改进原因如下：

		1. $w_{ij}$在更新的时候涉及到梯度$x_i,x_j$，而$x_i,x_j$经过onthot后数据非常稀疏，导致大部分参数无法得到从分训练。
		1. 考虑到复杂度的问题：原始的$w$是一个$\frac{n(n-1)}{2}$个参数，而改善过后变成了一个n*k的 V 矩阵，因为 k << n，所以降低了训练的复杂度。

​ 我们先了解一个简化式：

$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} x_ix_j = \frac{1}{2}(\sum_{i=1}^{n}\sum_{j=1}^{n}x_ix_j-\sum_{i=1}^{n}x_ix_i)$

​ 这个公式的思想可以理解为x_ix_j是一个新的矩阵w，那么这个矩阵是一个对称矩阵，因为$w_{ij}=x_ix_j=x_jx_i=w_{ji}$，而公式左边的代表右上三角，所以我们用整个矩阵减去对角线元素然后在取一半就行。

​ 接下来我们在进一步优化上面代码：

$\hat {y} = w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}<v_i^T,v_j>x_ix_j\\ =w_0+\sum_{i=1}^{n}w_ix_i+\frac{1}{2}(\sum_{i=1}^{n}\sum_{j=1}^{n}v_i^Tv_jx_ix_j-\sum_{i=1}^{n}v_i^Tv_ix_ix_i)\\ =w_0+\sum_{i=1}^{n}w_ix_i+\frac{1}{2}(\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{l=1}^{k}v_{i,l}^Tv_{j,l}x_ix_j-\sum_{i=1}^{n}\sum_{l=1}^{k}v_{i,l}^Tv_{i,l}x_ix_i)\\ =w_0+\sum_{i=1}^{n}w_ix_i+\frac{1}{2}\sum_{l=1}^{k}[(\sum_{i=1}^{n}v_{i,l}x_i)(\sum_{j=1}^{n}v_{j,l}x_j)-\sum_{i=1}^{n}v_{i,l}^2x_i^2]\\ =w_0+\sum_{i=1}^{n}w_ix_i+\frac{1}{2}\sum_{l=1}^{k}[(\sum_{i=1}^{n}v_{i,l}x_i)^2-\sum_{i=1}^{n}v_{i,l}^2x_i^2]\\$

​ 经过这样的一个变化，时间复杂度由$O(n^2)$变为了$O(n)$。

Loss:

​ 假如我们的任务是一个回归任务，那么模型的损失函数可以是最小二乘损失：

$L = -\sum_{i=1}^{n}(\hat y ^{(i)}-y^{(i)})^2 \\ \text{假如这是一个二分类任务，则:}\\ \hat y^{(i)} :=\sigma(\hat y ^{(i)}) = \frac{1}{1+e^{-\hat y^{(i)}}} \\ \text{然后我们在计算交叉熵:} \\ L = -\sum_{i=1}^{n}[y^{(i)}log \sigma(\hat y ^)+(1-y^{(i)}) log (1-\hat y^{(i)})]$

​