LIANYONGXING. BLOG

# 因子分解机

因子分解机式在poly2模型上的改进，为了改进计算交叉项参数时，矩阵稀疏的问题而引入。普通线性模型将各个特征独立考虑，没有考虑到特征之间的关系，实际上，这些特征间有一些关联，如果找出这类特征，会更有意义

比如用某条数据表示一个人：（年龄，在北京，在上海，在深圳，男，女）

则一个在北京的20岁男生可以表示为(20, 1, 0, 0, 1, 0)

一个在深圳的22岁女生可以表示为(22, 0, 0, 1, 0, 1)

当进行某个label的预测时，可以每个参数给一个权重，进行LR预测，但是其中两个特征的组合也可能产生其他影响，比如（北京的男生或者深圳的女生），会比单独的（北京的、男生、深圳的、女生）造成更大影响，就可以在设计模型时为其进行组合

# 注

简单的说就是每个特征xix_{i}，不仅有特征本身xix_{i}的值，还有一个隐向量表示viv_{i}，这样求两个特征x_{i}、x{j}之间的关系的时候，就需要计算<vi,vj>xixj<v_{i}, v_{j}>x_{i}x_{j}，即两个特征的乘积和其隐向量的点积

# 公式改写

为了克服矩阵稀疏时，交叉项参数在进行梯度下降时无法更新的问题，需要对FM公式进行改写，使得求解更加顺利，受矩阵分解的启发，对于每个特征xix_{i}引入kk维的辅助向量ViV{i}，找到一个VVT=WVV^{T} = W，当kk足够大时，对于任意对称正定的实矩阵，均存在实矩阵，使得W=VVTW = VV^{T}

也就是可以将具有交叉项的LR公式进行改写

y(x)=ω0+Σωixi+Σi=1nΣj=i+1n<vi,vj>xixjy(x) = \omega_{0} + \Sigma \omega_{i} x_{i} + \Sigma_{i=1}^{n}\Sigma_{j=i+1}^{n} <v_{i},v_{j}>x_{i}x_{j}

其中<vi,vj>=Σf=1kvi,fvj,f<v_{i}, v_{j}> = \Sigma_{f=1}^{k} v_{i,f} v_{j,f}，ff从11到kk，是维度，计算复杂度从n2n^{2}降低到knkn

Σi=1n−1Σj=i+1n<vi,vj>xixj\Sigma_{i=1}^{n-1}\Sigma_{j=i+1}^{n} <v_{i}, v_{j}>x_{i}x_{j}

=12Σi=1nΣj=1n<vi,vj>xixj−12Σi=1n<vi,vi>xixi= \frac{1}{2}\Sigma_{i=1}^{n}\Sigma_{j=1}^{n}<v_{i}, v_{j}>x_{i}x_{j} - \frac{1}{2}\Sigma_{i=1}^{n}<v_{i}, v_{i}>x_{i}x_{i}

=12(Σi=1nΣj=1nΣf=1kvi,fvj,fxixj−Σi=1nΣf=1kvi,fvi,fxixi)= \frac{1}{2}(\Sigma_{i=1}^{n}\Sigma_{j=1}^{n}\Sigma_{f=1}^{k}v_{i,f}v_{j,f}x_{i}x_{j} - \Sigma_{i=1}^{n}\Sigma_{f=1}^{k}v_{i,f}v_{i,f}x_{i}x_{i})

=12Σf=1k[(Σi=1nvi,fxi)(Σj=1nvj,fxj)−Σi=1nvi,f2xi2]= \frac{1}{2}\Sigma_{f=1}^{k}[(\Sigma_{i=1}^{n}v_{i,f}x_{i})(\Sigma_{j=1}^{n}v_{j,f}x_{j}) - \Sigma_{i=1}^{n}v_{i,f}^{2}x_{i}^{2}]

=12Σf=1k[(Σi=1nvi,fxi)2−Σi=1nvi,f2xi2]= \frac{1}{2}\Sigma_{f=1}^{k}[(\Sigma_{i=1}^{n}v_{i,f}x_{i})^2 - \Sigma_{i=1}^{n}v_{i,f}^{2}x_{i}^{2}]

化简解释：原本是一个矩阵对角线的上半部分，将其进行补全，由于上下对称，因此变为原先的一半，减去对角线元素的值（原本没有对角线的值），后续则为正常化简

# FM梯度下降

一样使用梯度下降进行参数求解，分别对ω0,ωi,vi\omega_{0}, \omega_{i}, v_{i}求导

∂y(x)∂ω0=1\frac{\partial y(x)}{\partial \omega_{0}} = 1

∂y(x)∂ωi=xi\frac{\partial y(x)}{\partial \omega_{i}} = x_{i}

∂y(x)∂vif=xiΣj=1nvj,fxj−vi,fxi2\frac{\partial y(x)}{\partial v_{if}} = x_{i}\Sigma_{j=1}^{n}v_{j,f}x_{j}-v{i,f}x^2_{i}

前两个时间O(1)O(1)，计算第三个偏导数时，每次迭代只需要计算一次所有的Σj=1nvjfxj\Sigma_{j=1}^{n}v_{jf}x_{j}就能求出所有vifv_{if}的梯度，因此复杂度时O(n)O(n)，因为vv有kk维，因此复杂度为O(kn)O(kn)，

可以看出，训练vi,fv_{i,f}只需要样本特征xix_{i}的特征非0，适合稀疏数据，并且计算复杂度低

# 优缺点

# 优点

  • 和SVM对比
    • FM能很好处理稀疏数据
    • 模型只依赖模型参数，SVM还依赖一部分数据
    • 可以在原始形式下直接优化（SVM是对偶处理）
    • FM的拟合能力不弱于任何多项式核SVM
  • 与分解模型对比
    • FM是一个通用预测器，可以处理任何真实值向量（分解模型往往只在特定输入数据形式下才能工作）
    • 只需要在特征向量中元素进行特定组合

# 缺点

  • 每个特征只引入了一个隐向量，不同特征间没有区分性（后续推出FFM对其进行改进）

← FFM →