点击量：824

Factorization Machines
要真正理解这个东西，我们得先从线性回归和多项式回归说起。

• 线性回归
  一个基本的线性回归模型可以表示为：
  $$
  \hat{y(x)} = w_{0} + \sum_{i=1}^{n}w_{i}x_{i}
  $$
• 多项式回归
  那么多项式回归就是在此基础上增加交叉项（也就是多项式）：
  $$
  \hat{y(x)} = w_{0} + \sum_{i=1}^{n}w_{i}x_{i} + \sum_{i=1}^{n}\sum_{j=i+1}^{n}w_{ij}x_{i}x_{j}
  $$
  后面增加的就是多项式交叉项，Factorization Machines的主要目的就是优化多项式交叉项。那么这个多项式交叉项有什么问题呢？为什么需要被优化呢？

• 第一个明显的问题就是参数太多了,\(n\)个特征，两两交叉，参数个数就是\(n(n-1)/2\).

• 各个参数\(w_{ij}\)之间是互相独立，并没有什么联系。
• 在高度稀疏的训练样本中无法准确地学习得到这些参数。为什么？因为最终的模型参数是由非零项训练，学习而来的。而在稀疏数据中，非零项很少，所以学习效果会非常差。这一点在推荐系统领域表现的尤为明显。

那么Factorization Machines是如何解决这两个问题的呢？受启发于矩阵分解，Factorization Machines提出了一个非常巧妙的方法解决这些问题，它把多项式交叉项的系数\(w_{ij}\)替换成（近似等于）两个向量\(v_{i}\)和\(v_{j}\)的点积（dot product）形式：\( \left \langle v_i,v_j \right \rangle\)。这就是FM模型最最最最最核心的思想了。于是得到如下的模型：
$$
\hat{y(x)} = w_{0} + \sum_{i=1}^{n}w_{i}x_{i} + \sum_{i=1}^{n}\sum_{j=i+1}^{n}
\left \langle v_i,v_j \right \rangle
x_{i}x_{j}
$$
其中，\(\left \langle v_i,v_j \right \rangle\)的计算公式是：
$$
\left \langle v_i,v_j \right \rangle = \sum_{f=1}^{k}v_{i,f}.v_{j,f}
$$
这里重点说下这个向量\(v\)：
\(v_{i}\)表示第\(i\)个特征的隐向量，他可以被表示成：\(v_{i} = (v_{i,1},v_{i,2},…,v_{i,k})\),其中\(k\)是向量的长度，也被称为隐向量的degree或者维度。那么我们知道对于一个特征数量为\(n\)的训练模型而言，隐向量的大小就是\(n \times k\)。好了，基本的介绍完了，接下来我们来看看这两个隐向量的点积为何能神奇地解决上面所说问题？

• 首先是参数的数量大幅度缩减，从\(n \times (n – 1)/2\)降低到\(n \times k\),这个之前说过了。
• 参数之间是互相联系的。比如对于多项式回归模型，我们有两个参数\(w_{12},w_{23}\)，那么这两个参数完全是独立的。但是如果替换成两个隐向量的点积之后就不一样了，比如换成：\(\left \langle v_1,v_2 \right \rangle\)和\(\left \langle v_2,v_3 \right \rangle\),此时你会发现这两个参数之间是有联系的：他们有一个共同的隐向量\(v_{2}\)，不再彼此独立。
• 如何解决稀疏数据下学习不充分的问题？比如多项式回归的参数\(w_{12}\)的学习只能依赖于特征\(x_{1}\)和\(x_{2}\)；而对参数\(\left \langle v_1,v_2 \right \rangle\)而言就完全不一样了，它由\(v_1\)和\(v_2\)组成。对于\(v_1\)而言，它可以通过多个交叉组合特征学习得到，比如可以由\({x_1x_2},x_1x_3,…,x_1x_n\)学习获得。\(v_2\)也是如此。这样可供学习的非零样本就大大增加了，这样就能很大程度避免因为数据过度稀疏而导致的学习不充分的问题。

好了，FM就介绍到这里，后面的推导和优化不再详细介绍了，总之训练这个模型的复杂度是线性的。

One-hot Encoding
一堆bits中只有一个1，其余都是0，这种编码被称为one-hot encoding。比如001 100 010等，这种编码在机器学习领域解决categorical分类数据有一定的应用。比如假设我们有如下一些数据：

country是一个categorical feature，那么在进行学习时就要先把他转化为数值。那么一个非常简单的想法就是找到一个一一对应的整数把他们映射起来。比如China-1,US-2,Canada-3,Russia-4。那么这么做有什么问题呢？问题很大。因为这样处理之后这些国家分类都是有大小的，比如Russia就大于China，那么最终训练的结果肯定会有影响。而实际情况应该是这些国家是互相独立的，他们不应该区分大小。所以一个典型的做法就是使用one-hot encoding，比如用000001-China,000010-US,00100-Canada,01000-Russia。这样一来呢，特征的数量就被扩展了。相当于把1维的country扩展成\(1 \times k\)维度了。具体的，比如原来我们有一个特征叫country，现在经过one-hot编码之后就变成k个特征了，分别是US,China,Canada,…,每一个特征都是二元的，要么0要么1。

为什么我们需要多项式特征？
这是一个很值得思考的问题，为什么特征交叉组合之后模型的效果会更好？举个例子：比如我们有以下一些categorical feature:
China, US, Canada, Thanksgiving, SpringFestival, Male, Female, Sports, Makeups.
很明显，China和SpringFestival，US和Thanksgiving，以及Female和Makeups的相关性是很高的，那么自然而言的把这些特征组合起来是有现实意义的。

Field-aware Factorization Machine(FFM)
昨天我们理解了FM，今天则趁热打铁学习一些FFM。这个东西咋一看很好理解，但是细看又不好理解，总之，一番顿悟之后，懂了。所谓的场感知分解机，重点在Field-aware（场感知）。
我们知道FM提出使用两个隐向量的点积\( \left \langle v_i,v_j \right \rangle\)来近似估计两个交叉特征\(x_ix_j\)的参数\(\hat{w_{ij}}\)，这里的\(v_i\)和\(v_j\)只是跟第\(i\)和第\(j\)个特征有关，那么FFM提出的思想是引入一个场（field）的概念，使得交叉特征的参数不仅跟特征有关，还跟他关联的特征所属的场有关。那么什么是field（场）呢？这东西说白了就是分类，最典型的场景就是categorical features经过one-hot编码之后变成多个二元的的特征，比如这几个特征：China, US, Canada就属于country分类，那么他们的field就是country。这种思想的提出个人感觉就是针对categorical features的，因为每一个非categorical feature都属于一个field嘛。但是话说回来，现实场景中很难不出现categorical features啊。接下来我们看下FFM模型的公式：
$$
\hat{y(x)} = w_{0} + \sum_{i=1}^{n}w_{i}x_{i} + \sum_{i=1}^{n}\sum_{j=i+1}^{n}
\left \langle v_{i,f_{j}},v_{j,f_{i}} \right \rangle
x_{i}x_{j}
$$
其中，\(f_{i}\)表是的是第\(i\)个特征所属的场，它只是一个数字或者一个标识，比如1代表country，2代表date，3代表gender。理解这个公式的重点在于理解\(\left \langle v_{i,f_{j}},v_{j,f_{i}} \right \rangle\),这个我看了好久都不能理解，那是因为我把\(v_{i,f_{j}}\)看成向量\(v\)的第\(i\)行和第\(f_{j}\)列的元素，然后对这个向量的维度搞不清楚。其实，这么理解是错误的，这个下标\(i,f_j\)只是标识不同的向量，可以理解为索引，它所表达的意思是第\(i\)个特征和第\(j\)个特征所属的field(场)的联系，每个向量的长度仍然是\(k\)。 所以FFM的多项式参数的个数就是\(n \times f \times k\)，其中\(f\)表示field（场）的个数。