【机器学习】因子分解机FM、场感知因子分解机FFM 算法整理

╰+攻爆jí腚メ 2022-05-26 01:56 174阅读 0赞

逻辑回归无法学习到特征间的组合关系，因此有了 因子分解机FM 和 场感知因子分解机FFM。

接下来，介绍下场感知因子分解机的主要应用。FFM模型可以自动做特征组合和处理高维稀疏特征，因而它在处理大量离散特征问题上往往有比较好的效果。但要注意对连续特征做归一化或者离散化。

# 因子分解机FM #

### 1.FM背景 ###

在计算广告中，CTR预估(click-through rate)是非常重要的一个环节，因为DSP后面的出价要依赖于CTR预估的结果。在前面的相关博文中，我们已经提到了CTR中相关特征工程的做法。对于特征组合来说，业界现在通用的做法主要有两大类：FM系列与Tree系列。今天，我们就来讲讲FM算法。

### 2.one-hote编码带来的问题 ###

FM(Factorization Machine)主要是为了解决数据稀疏的情况下，特征怎样组合的问题。已一个广告分类的问题为例，根据用户与广告位的一些特征，来预测用户是否会点击广告。数据如下：(本例来自美团技术团队分享的paper)

![20190505144132462.png][]  
clicked是分类值，表明用户有没有点击该广告。1表示点击，0表示未点击。而country,day,ad\_type则是对应的特征。对于这种categorical特征，一般都是进行one-hot编码处理。

将上面的数据进行one-hot编码以后，就变成了下面这样  
![2019050514423161.png][]

因为是categorical特征，所以经过one-hot编码以后，不可避免的样本的数据就变得很稀疏。举个非常简单的例子，假设淘宝或者京东上的item为100万，如果对item这个维度进行one-hot编码，光这一个维度数据的稀疏度就是百万分之一。由此可见，数据的稀疏性，是我们在实际应用场景中面临的一个非常常见的挑战与问题。

one-hot编码带来的另一个问题是特征空间变大。同样以上面淘宝上的item为例，将item进行one-hot编码以后，样本空间有一个categorical变为了百万维的数值特征，特征空间一下子暴增一百万。所以大厂动不动上亿维度，就是这么来的。

### 3.对特征进行组合 ###

普通的线性模型，我们都是将各个特征独立考虑的，并没有考虑到特征与特征之间的相互关系。但实际上，大量的特征之间是有关联的。最简单的以电商为例，一般女性用户看化妆品服装之类的广告比较多，而男性更青睐各种球类装备。那很明显，女性这个特征与化妆品类服装类商品有很大的关联性，男性这个特征与球类装备的关联性更为密切。如果我们能将这些有关联的特征找出来，显然是很有意义的。

一般的线性模型为：  
![20190505143607159.png][]

从上面的式子很容易看出，一般的线性模型压根没有考虑特征间的关联。为了表述特征间的相关性，我们采用多项式模型。在多项式模型中，特征 xi 与 xj 的组合用xixj表示。为了简单起见，我们讨论二阶多项式模型。具体的模型表达式如下：

![20190505143617475.png][]

上式中，n 表示样本的特征数量,xi表示第 i 个特征。  
与线性模型相比，FM的模型就多了后面特征组合的部分。

### 4.FM求解 ###

![20190505143722845.png][]

![20190505143743181.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlY29uZExpZXV0ZW5hbnQ_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlY29uZExpZXV0ZW5hbnQ_size_16_color_FFFFFF_t_70 1][]

# 场感知因子分解机FFM（Field-aware Factorization Machine） #

### 1、FFM理论 ###

在CTR预估中，经常会遇到one-hot类型的变量，one-hot类型变量会导致严重的数据特征稀疏的情况，为了解决这一问题，在上一讲中，我们介绍了FM算法。这一讲我们介绍一种在FM基础上发展出来的算法-FFM（Field-aware Factorization Machine）。

FFM模型中引入了类别的概念，即field。还是拿上一讲中的数据来讲，先看下图：

![Image 1][]

在上面的广告点击案例中，“Day=26/11/15”、“Day=1/7/14”、“Day=19/2/15”这三个特征都是代表日期的，可以放到同一个field中。同理，Country也可以放到一个field中。简单来说，同一个categorical特征经过One-Hot编码生成的数值特征都可以放到同一个field，包括用户国籍，广告类型，日期等等。

在FFM中，每一维特征 xi，针对其它特征的每一种field fj，都会学习一个隐向量 v\_i,fj。因此，隐向量不仅与特征相关，也与field相关。也就是说，“Day=26/11/15”这个特征与“Country”特征和“Ad\_type"特征进行关联的时候使用不同的隐向量，这与“Country”和“Ad\_type”的内在差异相符，也是FFM中“field-aware”的由来。

假设样本的 n个特征属于 f个field，那么FFM的二次项有 nf个隐向量。而在FM模型中，每一维特征的隐向量只有一个。FM可以看作FFM的特例，是把所有特征都归属到一个field时的FFM模型。根据FFM的field敏感特性，可以导出其模型方程。

![Image 1][]

可以看到，如果隐向量的长度为 k，那么FFM的二次参数有 nfk 个，远多于FM模型的 nk个。此外，由于隐向量与field相关，FFM二次项并不能够化简，其预测复杂度是 O(kn^2)。

下面以一个例子简单说明FFM的特征组合方式。输入记录如下：

![Image 1][]

这条记录可以编码成5个特征，其中“Genre=Comedy”和“Genre=Drama”属于同一个field，“Price”是数值型，不用One-Hot编码转换。为了方便说明FFM的样本格式，我们将所有的特征和对应的field映射成整数编号。

![Image 1][]

那么，FFM的组合特征有10项，如下图所示。

![Image 1][]

其中，红色是field编号，蓝色是特征编号。

# 2、FFM实现细节 #

这里讲得只是一种FFM的实现方式，并不是唯一的。

**损失函数**  
FFM将问题定义为分类问题，使用的是logistic loss，同时加入了正则项

![Image 1][]

什么，这是logisitc loss？第一眼看到我是懵逼的，逻辑回归的损失函数我很熟悉啊，不是长这样的啊？其实是我目光太短浅了。逻辑回归其实是有两种表述方式的损失函数的，取决于你将类别定义为0和1还是1和-1。大家可以参考下下面的文章：[https://www.cnblogs.com/ljygoodgoodstudydaydayup/p/6340129.html][https_www.cnblogs.com_ljygoodgoodstudydaydayup_p_6340129.html]。当我们将类别设定为1和-1的时候，逻辑回归的损失函数就是上面的样子。

**随机梯度下降**

训练FFM使用的是随机梯度下降方法，即每次只选一条数据进行训练，这里还有必要补一补梯度下降的知识，梯度下降是有三种方式的

![20190505144339409.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlY29uZExpZXV0ZW5hbnQ_size_16_color_FFFFFF_t_70 2][]

![20190505144407215.png][]

[20190505144132462.png]: /images/20220526/b91517d573e843ac959427d80ddae29f.png
[2019050514423161.png]: /images/20220526/c426e071a03643b08d05efecc20361f5.png
[20190505143607159.png]: /images/20220526/2040058e372d4985a6ab8673cecf128b.png
[20190505143617475.png]: /images/20220526/887997d458ba4332a28d89700b761400.png
[20190505143722845.png]: /images/20220526/c2d98b100f044921a0e03053182dc7fd.png
[20190505143743181.png]: /images/20220526/6350c409f851404a8d36e69334f225b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlY29uZExpZXV0ZW5hbnQ_size_16_color_FFFFFF_t_70]: /images/20220526/3582eece4a7d46968ee335dfc9a040cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlY29uZExpZXV0ZW5hbnQ_size_16_color_FFFFFF_t_70 1]: /images/20220526/595899f1ccac4f2ebf292e06607ff7ff.png
[Image 1]: 
[https_www.cnblogs.com_ljygoodgoodstudydaydayup_p_6340129.html]: https://link.jianshu.com?t=https%3A%2F%2Fwww.cnblogs.com%2Fljygoodgoodstudydaydayup%2Fp%2F6340129.html
[20190505144339409.png]: /images/20220526/1a1a20df6229489a8fe7956381585349.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NlY29uZExpZXV0ZW5hbnQ_size_16_color_FFFFFF_t_70 2]: /images/20220526/da695a279b0344cbaeb9420f99816b65.png
[20190505144407215.png]: /images/20220526/0251e5a2dccd4865b207125a1c00746d.png