推荐系统之FM算法原理及实现（附代码）

导读

本文介绍FM原理及实现

    由于在逻辑回归中使用的是特征的最原始组合，最终得到的分隔超平面属于线性模型，其只能处理线性可分的二分类问题。现实生活中的分类问题是多种多样的，存在大量的非线性可分的分类问题。

    为了使得逻辑回归能够处理更多的复杂问题，对其的优化主要有两种：①对特征进行处理，如核函数的方法，将非线性可分的问题转换成近似线性可分的问题；②对模型本身进行扩展，因子分解机应运而生，其本质是一种基于矩阵分解的方法。笔者在自己科研课题中也曾用过一种FM的改良版，所以对该方法比较有亲切感~

Factorization Machine

      对于FM模型，引入度的概念。对于度为2的FM模型为：

    其中<V_i,V_j>表示的是两个大小为k的向量V_i和向量V_j的点积：

     其中V_i表示的是系数矩阵V的第i维向量，k称为超参数，且大小为模型的度。整个模型由线性部分和交叉部分组成。

损失函数

     由于该方法引入了非线性的交叉项，因此可以适用于三类问题，分别是：二分类问题，回归问题，召回&排序问题。本文以二分类问题为例，只需要将模型输出最后通过Sigmoid函数激活即可。

     使用logit loss作为损失函数，即：

交叉项处理

     将模型改写为一般形式为：

     由于这种直接在交叉项的前面加上交叉项系数的方式，在稀疏数据的情况下存在一个很大的缺陷，即在对于观察样本中未出现交互的特征分量时，不能像逻辑回归那样对交叉项系数直接进行估计。

    这里针对每一个原始特征引入辅助向量V_i来利用V_iV_j^T对交叉项系数进行估计：

    假设：

    可得：

    这就是矩阵分解的形式，而k可以影响模型的表达能力。

梯度下降法

       这里对交叉项的形式进行一定的推导改写，过程如下：

     这里选用梯度下降法中的随机梯度法来进行迭代训练，优点在于每次迭代只使用一个样本，在大规模数据集中可以大大降低计算成本。优化流程为：

     对损失函数求一阶导为：

     而模型输出对参数一阶导有不同形式，分情况讨论：

     代入损失函数一阶导后，参数各自的梯度表达式为：

    现在让我们用代码实现训练过程：

import numpy as npdef fm_sgd(dataMatrix, classLabels, k, max_iter, alpha):    '''input: dataMatrix特征            classLabels标签            k v的维数            max_iter最大迭代次数            alpha学习率    output: w0,w,v权重'''    m, n = np.shape(dataMatrix)    # 1、初始化参数    w = np.zeros((n, 1))      w0 = 0    v = initialize_v(n, k)
    # 2、训练    for it in range(max_iter):        for x in range(m):            inter_1 = dataMatrix[x] * v            inter_2 = np.multiply(dataMatrix[x], dataMatrix[x]) * \             np.multiply(v, v)            # 完成交叉项            interaction = np.sum(np.multiply(inter_1, inter_1) - inter_2) / 2.            p = w0 + dataMatrix[x] * w + interaction            loss = sigmoid(classLabels[x] * p[0, 0]) - 1
            w0 = w0 - alpha * loss * classLabels[x]            for i in range(n):                if dataMatrix[x, i] != 0:                    w[i, 0] = w[i, 0] - alpha * loss * classLabels[x] * dataMatrix[x, i]                                      for j in range(k):                        v[i, j] = v[i, j] - alpha * loss * classLabels[x] * \                        (dataMatrix[x, i] * inter_1[0, j] -\                          v[i, j] * dataMatrix[x, i] * dataMatrix[x, i])
        # 计算损失函数的值        if it % 1000 == 0:            print("\t------- iter: ", it, " , cost: ", \            Cost(Prediction(np.mat(dataMatrix), w0, w, v), classLabels))        return w0, w, v

     其中激活函数和辅助矩阵的初始化函数分别为sigmoid和initialize_v。

import numpy as npfrom numpy import normalvariatedef sigmoid(x):    return 1.0 / (1 + np.exp(-x))
def initialize_v(n, k):    '''input: n特征的个数            k超参数    output: v辅助矩阵'''    v = np.mat(np.zeros((n, k)))
    for i in range(n):        for j in range(k):                    v[i, j] = normalvariate(0, 0.2)    return v

     其中模型预测函数和损失函数的计算函数分别为Prediction和Cost。

def Prediction(dataMatrix, w0, w, v):    '''input: dataMatrix特征            w常数项权重            w0一次项权重            v辅助矩阵    output: result预测结果'''    m = np.shape(dataMatrix)[0]       result = []    for x in range(m):
        inter_1 = dataMatrix[x] * v        inter_2 = np.multiply(dataMatrix[x], dataMatrix[x]) * \         np.multiply(v, v)         # 完成交叉项        interaction = np.sum(np.multiply(inter_1, inter_1) - inter_2) / 2.        p = w0 + dataMatrix[x] * w + interaction                pre = sigmoid(p[0, 0])                result.append(pre)            return result
def Cost(predict, classLabels):    '''input: predict预测值            classLabels标签    output: error损失函数值'''    m = len(predict)    error = 0.0    for i in range(m):        error -=  np.log(sigmoid(predict[i] * classLabels[i] ))      return error 

     到这里整个流程基本就结束了~

推荐阅读

[1]. 由Logistic Regression所联想到的...

[2]. 推荐系统之矩阵分解家族

来都来了，点个在看再走吧~~~