机器学习必刷题-手撕推导篇(3)：FM与softmax
2019-08-03 本文已影响1人
arrnos
本系列文章对常见的机器学习面试题进行了搜集、分类和整理，主要包括”手撕推导篇“、“模型比较篇”、“工程经验篇”以及“基础概念篇”等多个板块，旨在帮助广大算法工作者能够从容应对求职面试！
推导FM
(1) 线性拟合(LR)
image
缺点： 线性拟合无法自动表示特征的相互组合，组合特征都是通过人工特征工程加入的，费时费力。
(2) Poly2
在LR基础上，加入任意两个特征之间的关系 其中，wij是feature pair（xi,xj）的权重，只有xi和xj都非零时，组合特征xixj才有意义。
由于样本数据非常稀疏，满足“xi和xj都非零”的样本将会非常少，很容易导致参数wij不准确，严重影响模型性能。
缺点：
- 参数空间大幅增加，由线性增加至平方级，训练效率极低且容易内存溢出； - 在数据稀疏的场景下，二次项系数难以充分训练。 - 当样本量不足以训练巨大的参数空间时，非常容易过拟合；
(3) FM
FM将wij分解为两个向量的内积：
image
其中，vi是一个k维向量。直观上看，FM的复杂度为O(kn2)，但是通过下式，FM的二次项可以化简，其复杂度可以优化到O(kn)。由此可见，FM可以在线性时间对新样本做出预测。
划重点：FM推导过程
(1) 根据矩阵对称性
image
(2) f求和项可以单独出来，而且
image
FM的优势：
- 参数的数量大幅度缩减，从n×(n−1)/2降低到nk； - 隐向量的点积可以表示原本两个毫无相关的参数之间的关系； - 可以解决稀疏向量问题，因为每个特征都有一个隐向量，就算是稀疏向量在训练样本没有出现过的组合在预测时也可以进行计算。
推导softmax
1、softmax函数
softmax回归是LR在多分类问题上的推广，一般用于神经网络的输出层，叫做softmax层。
假设在进入softmax函数之前，模型的全连接网络输出为：
image
其中，C为类别的个数。则对每个样本，它属于类别 i 概率为：
image
image
更详细地如下图所示：
image
2、softmax求导
对softmax函数进行求导，即求:
image
第 i 项的输出 yi 对j项输入 aj 求导。
代入softmax函数表达式，可以得到：
image
因此，
当 i = j 时：
image
当 i != j 时：
img
image
3、结合交叉熵loss求导
对一个样本来说，真实类标签分布与模型预测的类标签分布可以用交叉熵来表示：
image
最终，对所有的样本，我们有以下loss function：
img
img
更多参考：
- softmax详细推导(简单实例)：https://www.cnblogs.com/zongfa/p/8971213.html
image
