基于粒子群优化的因子分解机算法

邱煜炎， 吴福生

蚌埠医学院图文信息中心， 安徽 蚌埠 233000

0 引言

近年来，云计算、大数据和移动互联网技术发展迅速，网络资源的信息量一直呈指数增长的趋势，推荐系统作为解决信息过载和挖掘用户潜在需求的技术手段得到普遍应用.推荐系统通过分析用户与物品的关系行为，根据用户偏好和相关属性为其提供推荐列表，有效解决了信息过载问题[1].作为推荐系统的核心，机器学习算法的性能直接决定推荐质量.

线性回归(linear regression,LR)[2]模型具有可解释性、较强的泛化能力以及简单快速求解的特点，是机器学习领域的基本算法.然而，在训练过程中只有当输入数据特征具有明显的线性关系时，才能表现出较好的建模效果.并且，线性模型本身缺乏对输入特征间关系的探索机制，它只考虑了每个特征对结果的单独影响，而没有考虑特征间的组合对结果的影响.

因子分解机(factoration machine,FM)[3，4]作为一种新式通用的机器学习算法，其设计思想来自矩阵分解和线性回归模型.因子分解机在对特征建模时，不仅考虑线性回归算法中单个特征对模型的影响，而且考虑特征间的相互关系，以构建二阶线性模型.FM模型适合高维稀疏的数据集，学界基于此模型也做了广泛研究[5]和应用[6].

粒子群优化(Particle Swarm Optimization,PSO)[7，8]是一种群体随机优化算法技术，其最初目的是生动模拟鸟群优雅而又难以预测的队形设计.作为一种全局优化技术，PSO的特点是不要求被优化函数具有可微可导连续等性质，而且能够达到快速收敛的效果[9].

尽管FM模型对于稀疏型数据集有较好的表现，但是在样本量较小的情况下，梯度下降方法不能保证参数收敛到全局最优解[10].针对以上问题，本文提出一种基于粒子群优化的因子分解机算法(particle swarm optimization factorization machine,PSO-FM).首先运用PSO算法快速获得全局最优区域，然后利用FM模型的梯度下降算法进行精确求解，最后在医疗诊断数据集Diabetes上进行验证.实验结果表明，相对于FM算法，PSO-FM算法在模型训练速度和测试集准确度上都有较好的表现.

1 因子分解机

1.1 线性模型

线性模型包含线性回归、逻辑回归等，其特点是只包含若干个特征对结果的单独影响，而没有考虑特征间相互组合对结果的影响.对于一个含有n维特征的模型，线性回归形式如下：

(1)

其中，(ω0,ω1,ω2,...,ωn)为模型参数，(x1,x2,...,xn)为数据特征.从(1)式可以看出，模型来自各个特征独立的计算结果，并没有考虑特征之间的相互关系.然而，组合特征在一定程度上具有意义，比如“美国”与“感恩节”，“中国”与“春节”，这两组特征组合，同时出现会表现出更强的购买意愿，而单独考虑国家及节日是没有意义的.

1.2 二项式模型

在(1)式的基础上，考虑任意2个特征分量之间的关系，可得以下模型

(2)

模型涉及参数的数量为

(3)

对于一次项参数ωi的训练，只要样本对应的xi不为0，即可完成一次训练.然而对于二次项参数ωij，需要样本xi和xj同时不为0，才可以完成一次训练.对于数据稀疏的实际应用场景，二次项参数ωij训练非常困难，xi和xj同时不为0的样本非常稀少，这会导致ωij不能得到足够的训练，从而导致模型准确度不高.

1.3 因子分解机

为解决上述由于数据稀疏引起训练不足的问题，为每个特征维度引入一个辅助向量

Vi=(vi1,vi2,vi3,...,vik)T∈Rki=1,2,...,n

(4)

其中，k(k∈N+)是辅助变量的维度，属于超参数，一般k<

(5)

由于W不方便求解，因此引入隐变量V

(6)

并令

VVT=W

(7)

理论研究表明[11]：当k足够大时，对于任意正定的实矩阵W∈Rn×k，均存在实矩阵V∈Rn×k，使得W=VVT.假设样本中有n个特征，每个特征对应的隐变量维度为k，则参数个数为1+n+nk.在线性模型的基础上，利用隐变量替代二次项系数矩阵，得出以下模型

(8)

(9)

最终得出，时间复杂度为O(kn)的表达式

(10)

对于机器学习问题，基于梯度优化的参数更新表达式如下

(11)

(12)

(13)

结合公式(11)～公式(13)，得参数的优化公式

(14)

如果针对回归问题，其偏导数为

(15)

如果针对二分类问题，其偏导数为

(16)

上述二分类问题使用对数损失函数进行求解，公式(16)中的σ表示为跃阶函数Sigmoid:

(17)

2 粒子群优化算法

2.1 算法描述

作为一种进化计算技术，粒子群优化PSO算法源于对鸟群捕食的行为研究.鸟群通过种群交流以及自身经验调整个体搜寻路径，从而搜寻捕食最优位置[12].其中每只鸟的位置/路径则是自变量的组合，每次到达的地点的食物密度即函数值.每次搜寻都会根据自身经验(自身历史搜寻的最优地点pbest)和种群交流(种群历史搜寻的最优地点gbest,gbest是pbest中的最好值)调整自身搜寻的方向和速度，从而找到最优解[13].相对于其他优化算法，PSO算法的优势在于简单容易实现并且没有许多参数的调节.

2.2 算法流程

PSO算法适用于连续函数极值问题的求解，流程如图1所示

图1 粒子群优化算法流程
Fig.1 Particle swarm optimization algorithm flow

根据流程，PSO算法中所涉及的参数有：(1) 种群数量：粒子群算法的最大特点就是速度快，因此初始种群取值50～1 000皆可；(2) 迭代次数：取值范围100～4 000，要在时间耗费和搜索广度进行权衡；(3) 惯性权重：取值范围0.5～1，该参数反映了个体历史成绩对现在的影响；(4) 学习因子：取值范围0～4，分为个体和群体两种学习因子；(5) 空间维数：粒子搜索空间维数，即代表自变量的个数；(6) 位置限制：限制搜索空间范围，即代表自变量的取值范围；(7) 速度限制：设置合理的粒子速度可以防止速度过快导致的跳过最优解位置以及速度过慢导致的收敛速度慢的问题.

2.3 算法规则与公式

PSO算法首先初始化一组随机解，然后利用反复迭代搜索出最优解.每次迭代后，粒子通过对比两个极值(pbest和gbest)来更新自己的参数[14].当粒子确定最优位置后，更新粒子的速度和位置，公式如下

Vi=ω×Vi+c1×rand()×(pbesti-xi)+c2×rand() ×(gbesti-xi)

(18)

xi=xi+Vi

(19)

公式(18)、公式(19)中，i=1,2,...,N，N是此群中的粒子总数，vi是粒子的速度，xi是粒子所在当前位置，ω是上次更新速度的惯性因子，rand()是随机数(范围0～1之间)，c1和c2代表学习因子.

3 基于粒子群优化的因子分解机算法

3.1 PSO-FM算法思路

根据公式(14)，对于少量数据集，利用梯度下降方法对FM进行参数求解容易陷入局部最优解.为此，本文提出了基于粒子群优化的因子分解机算法(PSO-FM)，利用粒子群算法全局搜索能力求解因子分解机模型参数.

PSO-FM算法融合了PSO全局搜索能力以及FM局部梯度求解精度能力的优势.首先采取PSO算法确定优化区域，然后利用基于公式(14)的梯度方法提升参数精度，以达到全局搜索，加速寻优的目的.

3.2 PSO-FM算法模型

(20)

对于二分类问题，需要添加Sigmoid函数进行映射.在利用PSO算法求解时，首先需要构建粒子群P={p1,p2,...,pm}，即包含m个粒子群，每个粒子pi按照公式(20)可以表示为

pi={ω0,ω1,ω2,...,ωn,υ1,1,υ1,2,...,υ1,k,...,υn,1,υn,2,...,υn,k}

(21)

每个粒子pi代表PSO模型的参数向量即速度，该向量的维度为D=1+n+n×k.

根据公式(18)利用粒子群优化算法进行参数求解过程中，采用错误率作为适应度函数

(22)

其中,#error表示正确个数，#all表示所有训练样本个数.当PSO算法适应度收敛到一定阈值[15]，则利用公式(14)对参数进行梯度求解.

3.3 算法步骤

根据以上描述，PSO-FM算法的目的就是通过公式(20)快速获取全局最优区域，然后在区域内利用公式(14)进行梯度求解，以此达到全局最优.具体算法步骤如下：

Step 1：设置超参数，包括粒子规模m，惯性权重ω，优化参数c1、，设置公式(14)中的η和λ，隐变量维度k，迭代次数i，PSO适应度阈值r1和FM模型交叉熵损失函数阈值r2;

Step 2：初始化每个粒子参数，即粒子的速度和位置；

Step 3：根据公式(22)计算单个粒子适应度；

Step 4：对单个粒子当前适应度与该粒子时间轴上最佳适应度pbest进行对比，如果优于pbest，则对pbest进行更新；

Step 5：将粒子群中的各个粒子当前适应度，与整个群体最佳适应度gbest进行对比，如果某粒子优于gbest，则对gbest进行更新；

Step 6：根据公式(18)和公式(19)更新每个粒子的位置和速度；当适应度小于阈值r1，保存当前粒子参数向量，执行Step 7；当适应度大于阈值r1，反复执行Step 3；

Step 7：利用公式(14)进行梯度计算；

Step 8：当满足迭代次数i或者损失函数值小于r2，返回最优参数向量Xbest；

Step 9：根据Xbest构建FM模型，用于待测试数据进行预测.

4 实验与结果分析

4.1 实验准备

本实验针对二分类问题对PSO-FM模型算法进行验证，选取医疗诊断数据集Diabetes，并与传统的FM算法进行对比.Diabetes数据集包含786条数据，特征个数为8，分类结果为是否有糖尿病({0,1}).按实验要求，将数据集按4∶1的比例分为614条训练集和154条测试集.

实验算法采用Python 3.6编写的代码，硬件环境采用Pentinum(R) G4400-3.3 GHz处理器，8 G内存.根据本文3.3算法步骤，Step 1超参数设置如表1所示.

FM算法的运行参数如表2所示.

表1中的超参数已在本文3.3中说明，不做赘述.表2中参数根据公式(14)，η表示学习率，λ表示正

表1 PSO-FM运行超参数Tab.1 PSO-FM running hyperparameters

则化参数，k表示隐向量维度，i表示迭代次数[16].

4.2 结果及分析

为验证PSO-FM算法能否在短时间内收敛并获得满意精度，图2对比了PSO-FM模型与FM模型在训练集根据公式(17)所得损失函数值的变化情况.

表2 FM运行超参数Tab.2 FM running hyperparameters

图2 算法对数损失函数迭代对比
Fig.2 Iterative comparison of algorithm logarithmic loss function

由图2可以看出，PSO-FM算法在同样的迭代次数内，对数损失函数值一直优于FM算法.表3列出两种算法训练时间(TraingTime,TT)以及在训练集的准确率(TrainingAccuracy,TRA)和测试集上的准确率(TestingAccuracy,TEA)指标.

从表3的结果可以看出，PSO-FM算法训练时间明显短于传统的FM算法，而且无论在训练集还是测试集，其准确性都要优于后者.本实验数据集具有训练样本量少、属性参数多的特点，对于传统的基于梯度的FM算法很容易陷入局部最优.凭借PSO算法全局搜索能力，并结合梯度下降求解参数，PSO-FM算法对于复杂参数寻优问题表现出更强的数据建模效果.

表3 算法运行指标Tab.3 Algorithm operation index

5 总结

本文利用PSO算法引入FM模型中，在全局快速搜索的前提下进行基于梯度参数的求解方法.通过在数据集Diabetes上进行实验，结果表明，相对于传统的FM模型，PSO-FM模型表现出更快的模型训练速度，以及更高的模型预测准确率.本文中的PSO-FM基于前人经验，使用统一的超参数，基于实验数据量比较小的情况，种群规模和迭代次数设置都比较小.在以后的实验中，可以考虑使用网格搜索(Grid search)方法，基于不同的数据集发掘出表现能力更强的超参数配置值.后续的研究工作中，将针对大规模多维度数据，解决PSO-FM算法应对单机计算时内存溢出问题以及针对该算法设计多机并行计算问题.