Press "Enter" to skip to content

FM算法简述

1线性模型

 

通常线性模型的表型形式为y=ax+b,y为因变量,x为自变量,通过最小二乘法或梯度下降来求解参数a

 

 

1.1逻辑回归

 

针对分类问题,我们对线性模型的输出进行sigmoid转换

 

 

问题:为什幺逻辑回归要用sigmoid函数?

 

论文:The equivalence of logistic regression and maximum entropymodels

 

http://www.win-vector.com/dfi… 自行脑补

 

逻辑回归是最大熵对应类别为二类时的特殊情况

 

逻辑回归目标函数Objective function:

 

 

注意:这里的目标变量是-1,+1

 

逻辑回归目标函数推导如下:

 

假设目标变量为+1,-1

 

 

基于极大似然估计:

 

 

取似然函数为:

 

 

取对数似然:

 

 

取负号,求解最小值:

 

 

1.2 线性模型的特点

通常会对特征离散化解决单变量非线性问题
简单高效,可解释性强,早期应用于推荐、广告、搜索等业务
特征组合,人肉解决

1.3 特征组合

 

引入特征组合的意义:

 

通过观察大量的样本数据可以发现,某些特征经过关联之后,与label之间的相关性就会提高。如“化妆品”类商品与“女”性,“球类运动配件”的商品与“男”性,“电影票”的商品与“电影”品类偏好等

 

人工特征组合:

 

中年+性别男=中年大叔;少年+性别女=萝莉

 

缺点:需要业务经验及其大量的数据分析

 

二次函数组合:

 

 

缺点:

 

参数个数随着特征维度的平方增长
过多的参数需要更多的数据量进行训练
对于高度稀疏的数据,数据中可能缺少x_i x_j !=0的模式,导致二次项参数训练困难

 

W权值矩阵:

 

 

FM借鉴了矩阵分解方法思想

 

已知矩阵数据W=R^(m*n),计算两个矩阵

 

 

使得U*V尽可能还原矩阵W

 

 

2FM

 

2.1针对特征组合的改进

 

对权值矩阵施加低秩约束,对其进行分解

 

 

好处:

 

➢ 组合特征参数,由之前n(n-1)/2个参数减少为nk

 

➢ 降低了交叉项参数学习不充分的影响

 

具体来说, xhxi 和 xixj 的系数分别为 ⟨vh,vi⟩和 ⟨vi,vj⟩,它们之间有共同项 vi。也就是说,所有包含“xi 的非零组合特征”(存在某个 j≠i,使得 xixj≠0)的样本都可以用来学习隐向量 vi,这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中, whi 和 wij 是相互独立的。

 

wij 必须在有足够多的满足 样本存在的情况下,才能得到很好的训练。但是在输入稀疏的情况下,在输入特征X里面大部分的 x_i 值都是0,更不必提 x_i,x_j 同时不为0了。所以多项式模型不能得到很好的训练。

 

反观FM,尽管要训练 v_i, 也依赖于 ,但是好处是,所有其他非0的 都会成为梯度的一部分,这样对于 v_i 的训练就有明显更多的训练数据,可以更好地训练出合适的参数。

 

➢ 由于交叉项参数w不再独立,没见过的交叉模式可以通过见过的进行学习

 

训练集:

 

男性,足球

 

女性,化妆品

 

测试集:

 

男性,化妆品??

 

➢ 线性时间计算复杂度(只跟非0特征有关)

 

要求出<vi,vj>,主要是采用了如公式[((a+b+c)2−a2−b2−c2)/2求出交叉项。具体过程如下:

 

 

时间复杂度降低主要体现在:

 

1) 特征交叉项预测时

 

2) 特征交叉项参数梯度求时

 

2.1 模型求解

 

对于二分类问题,其损失函数为:

 

 

 

 

更新参数θ

 

 

如何做embedding feature或者distributed representation的sparsity?

 

有个coupled group lasso的方法,对latent feature vector整体做L1

http://proceedings.mlr.press/…

2.3 FM训练demo

 

基于SGD算法训练过程代码(python):

 

def stocGradAscent(dataMatrix, classLabels, k, max_iter, alpha):
    '''利用随机梯度下降法训练FM模型
    input:  dataMatrix(mat)特征
            classLabels(mat)标签
            k(int)v的维数
            max_iter(int)最大迭代次数
            alpha(float)学习率
    output: w0(float),w(mat),v(mat):权重
    '''
    # dataMatrix=np.mat(dataMat)
    m, n = np.shape(dataMatrix)
    # 1、初始化参数
    w = np.zeros((n, 1))  # 其中n是特征的个数
    w0 = 0  # 偏置项
    # k=4
    v = initialize_v(n, k)  # 初始化V
    cost=[]
    # 2、训练
    for it in range(max_iter):
        for x in range(m):  # 随机优化,对每一个样本而言的
            # x=1
            inter_1 = dataMatrix[x] * v 
            inter_2 = np.multiply(dataMatrix[x], dataMatrix[x]) * \
                      np.multiply(v, v)  # multiply对应元素相乘
            # 完成交叉项
            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: ", \
              getCost(getPrediction(np.mat(dataTrain), w0, w, v), classLabels))
        cost.append(getCost(getPrediction(np.mat(dataTrain), w0, w, v), classLabels))
    # 3、返回最终的FM模型的参数
    return w0, w, v,cost

 

逻辑回归文献:

http://blog.csdn.net/cyh_24/a…

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注