因子分解机算法原理及实现
由于在逻辑回归中使用的是特征的最原始组合，最终得到的分隔超平面属于线性模型，其只能处理线性可分的二分类问题。现实生活中的分类问题是多种多样的，存在大量的非线性可分的分类问题。
为了使得逻辑回归能够处理更多的复杂问题，对其的优化主要有两种：①对特征进行处理，如核函数的方法，将非线性可分的问题转换成近似线性可分的问题；②对模型本身进行扩展，因子分解机应运而生，其本质是一种基于矩阵分解的方法。笔者在自己科研课题中也曾用过一种FM的改良版，所以对该方法比较有亲切感~
Factorization Machine
对于FM模型，引入度的概念。对于度为2的FM模型为：
其中<Vi,Vj>表示的是两个大小为k的向量Vi和向量Vj的点积：
其中Vi表示的是系数矩阵V的第i维向量，k称为超参数，且大小为模型的度。整个模型由线性部分和交叉部分组成。
损失函数
由于该方法引入了非线性的交叉项，因此可以适用于三类问题，分别是：二分类问题，回归问题，召回&排序问题。本文以二分类问题为例，只需要将模型输出最后通过Sigmoid函数激活即可。
使用logit loss作为损失函数，即：
交叉项处理
将模型改写为一般形式为：
由于这种直接在交叉项的前面加上交叉项系数的方式，在稀疏数据的情况下存在一个很大的缺陷，即在对于观察样本中未出现交互的特征分量时，不能像逻辑回归那样对交叉项系数直接进行估计。
这里针对每一个原始特征引入辅助向量Vi来利用ViVjT对交叉项系数进行估计：
假设：
可得：
这就是矩阵分解的形式，而k可以影响模型的表达能力。
梯度下降法
这里对交叉项的形式进行一定的推导改写，过程如下：
这里选用梯度下降法中的随机梯度法来进行迭代训练，优点在于每次迭代只使用一个样本，在大规模数据集中可以大大降低计算成本。优化流程为：
对损失函数求一阶导为：
而模型输出对参数一阶导有不同形式，分情况讨论：
代入损失函数一阶导后，参数各自的梯度表达式为：
现在让我们用代码实现训练过程：
import numpy as np
def 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 np
from numpy import normalvariate
def 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 到这里整个流程基本就结束了~