迭代优化信用模型

a13698822086

　　市场经济的快速发展促使信贷消费逐渐成为区别于传统消费模式的新潮流。个人信用作为信贷消费的评价基础,它体现了当事人履行信用承诺的能力,如今它也不仅仅是传统观念上的一种美德,更确切的说是一种商品,是一种建立在个人净资产和对未来收入预期基础上的支付能力。运用先进的技术构建个人信用评价模型,进而客观正确评价个人信用,能够公平维护授信双方的合法利益,也为信贷机构提供了预测信用风险的有效工具,同时维持市场经济健康稳定发展。本文在分析了国内信贷行情和国内外在个人信用评价领域的研究现状的基础上,对比分析了统计和非统计个人信用评价模型的优越性和局限性,并且探讨了人工智能算法中的BP神经网络算法和粒子群优化算法,然后运用属性信息熵对德国个人信用数据集的原始指标体系做二次优化,通过指标增益值的大小来选取合适的信用评价指标,从而构建了新的指标体系；其次,在原始预测分类模型基础评价指标(整体预测正确率、两类信用等级预测精度和两类信用等级召回精度)的基础上,创建了两个适合度量个人信用评价模型评测性能的综合评价指标：综合评价性能指标和综合评价损失率指标；再次依据新的指标体系结合BP算法和PSO算法构建了不同训练函数下的BP常规优化个人信用评价模型和基于PSO优化的个人信用评价模型。最后通过实例验证表明：在常规优化的BP个人信用评价模型中,采用trainbfg训练函数的模型收敛速度较快,而且泛化性能好,两个综合评价指标在同类常规优化算法中表现最好；基于PSO优化的BP神经网络个人信用评价模型的评测性能随着迭代次数不伺有所差别,在迭代次数为300时,PSO优化模型比基于常规优化的BP模型表现出更好的性能。本文运用BP神经网络算法和PSO算法来构建个人信用评价模型,并且运用实例来验证基于人工智能算法的个人信用评价模型的优越性和可行性,为后续深入研究打下基础,同时对于后期改进的个人信用评价模型具有一定的参考价值和理论意义!
　　如果学习机器学习算法，你会发现，其实机器学习的过程大概就是定义一个模型的目标函数J(θ)，然后通过优化算法从数据中求取J(θ)取得极值时对应模型参数θ的过程，而学习到的参数就对应于机器学习到的知识。不管学习到的是好的还是无用的，我们知道这其中的动力引擎就是优化算法。在很多开源软件包中都有自己实现的一套优化算法包，比如stanford-nlp，希望通过本篇简要介绍之后，对于开源软件包里面的优化方法不至于太陌生。本文主要介绍三种方法，分别是梯度下降，Conjugate Gradient Method(共轭梯度法)和Quasi-Newton。具体在stanford-nlp中都有对应的实现，由于前两种方法都涉及到梯度的概念，我们首先从介绍梯度开始。
梯度(Gradient)
　　什么是梯度，记忆中好像和高数里面的微积分有关。好，只要您也有这么一点印象就好办了，我们知道微积分的鼻祖是牛顿，人家是经典力学的奠基人，那么我们先来看看一道简单的物理问题：

　　一个小球在一个平面运动，沿着x轴的位移随时间的变化为：Sx=20?t2，沿着y轴的位移随时间的变化为：Sy=10+2t2，现在求在t0时刻小球的速度v？

　　大家都是为高考奋战过的人，这样的小题应该是送分题吧。牛老师告诉我们，只要通过求各个方向的分速度，然后再合成就可以求解得出。好，现在我们知道各个方向的位移关于时间的变化规律，我们来求各个方向的速度。如何求速度呢，牛老师说位移的变化率就是速度，那么我们来求在t0时刻的变化率：

　　，那么此时的合成速度
　　
　　，那么此时的合成速度v:

　　，此时的速度方向就是总位移变化最大的方向。搬到数学中，对于一个位移函数S(x,y)，它各个维度的变化率就是其对应的偏导数
　　

　　，两者组合起来的向量就是该函数的梯度，所代表的含义上面已经说过，其方向代表函数变化最大的方向，模为变化率的大小。如果我们分别沿着x,y两个维度做微小的变化Δx,Δy,那么位移总体的变化将如下：
　　

　　现在我们知道如何求取函数的梯度，而且如何利用梯度求取函数微小变化量了。
梯度下降法
　　做机器学习(监督学习)的时候，一般情况是这样的，有N条训练数据(X(i),y(i))，我们的模型会根据X预测出对应的y，也就是：

　　其中θ=[θ1,θ2,θ3,...,θn]是模型的参数。通常我们希望预测值和真实值是一致的，所以会引出一个惩罚函数:  

　　而目标函数则是：

　　，我们目的是解决下面的优化问题:
　　argminθJ(θ)
　　，一般一组θ和N条数据会对应一个J(θ)，也就是N维平面上的一个点，那么不同θ就可以得到一个N维的超平面(hyper plane)。特殊的假如N=3，我们可能的超平面就如下图所示：

　　如何找到最优的θ呢？一个想法是这样的：我们随机在超平面上取一个点，对应我们θ的初始值，然后每次改变一点Δθ，使J(θ)也改变ΔJ(θ)，只要能保证ΔJ0就一直更新θ直到J(θ)不再减少为止。具体如下：

• 　　随机初始化θ
  
• 　　对于每一个θi选择合适的Δθi，使得J(θ+Δθ)?J(θ)0,如果找不到这样的Δθ，则结束算法
  
• 　　对于每一个θi进行更新：θi=θi+Δθi，回到第2步。
  

　　想法挺好的，那么如何找到所谓合适的Δθ呢？根据上一节中我们知道：

　　,要如何保证ΔJ(θ)0呢？我们知道，两个非0数相乘，要保证大于0，只要两个数一样即可，如果我们要保证ΔJ(θ)>0，只要另每一个θi＝?J(θ)?θi即可，此时

　　，有人疑问了，我们目标可是要使ΔJ(θ)0，上面的做法刚好相反啊！反应快的人可能马上想到了，我们只需另每一个θi＝??J(θ)?θi不就好了，而这样的求取向量θ各个维度相对于J(θ)的偏导数实际上就是求取J(θ)的梯度！回忆上一节梯度的含义，表示J(θ)变化最大的方向，想象一个球在上面的图中上方滚下来，而我们的做法是使他沿着最陡的方向滚。不错，我们找到了上述算法所说的合适的Δθ了！其实上述的算法就是我们本文的主角——梯度下降法(gradient descent)，完整算法如下：

• 　　随机初始化θ
  
• 　　求取θ的梯度?θ，也就是对于每个θi求取其偏导数?J(θ)?θi，并更新θi=θi?η??J(θ)?θi(η>0并足够小)
  
• 　　判断?θ是否为0或者足够小，是就输出此时的θ，否则返回第2步
  

　　上述算法的第二步中多了一个未曾介绍的η，这是步伐大小，因为求取每一个维度的偏导，只是求取了该维度上的变化率，具体要变化多大就由η控制了，η的选取更多考验的是你的工程能力，取太大是不可行的，这样导致算法无法收敛，取太小则会导致训练时间太长，有兴趣的可参考An overview of gradient descent optimization algorithms这篇文章中对η选取的一些算法。如何计算?J(θ)?θi呢？根据定义，可如下计算：

　　，由于每次计算梯度都需要用到所有N条训练数据，所以这种算法也叫批量梯度下降法(Batch gradient descent)。在实际情况中，有时候我们的训练数据数以亿计，那么这样的批量计算消耗太大了，所以我们可以近似计算梯度，也就是只取M(MN)条数据来计算梯度，这种做法是现在最流行的训练神经网络算法，叫mini-batch gradient descent。最极端的，我们只用一条训练数据来计算梯度，此时这样的算法叫做随机梯度下降法(stochastic gradient descent)，适合数据是流式数据，一次只给一条训练数据。
　　Conjugate Gradient Method
　　上一节中，我们介绍了一般的梯度下降法，这是很多开源软件包里面都会提供的一种算法。现在我们来看看另外一种软件包也经常见到算法——Conjugate Gradient Descent，Jonathan在94年的时候写过《An Introduction to the Conjugate Gradient Method Without the Agonizing Pain》详细而直观地介绍了CGD，确实文如其名。这里我只是简要介绍CGM到底是一个什么样的东西，具体还需阅读原文，强烈推荐啊！
　　最陡下降法(Steepest Descent)
　　上一节中，我们介绍了如何反复利用θi=θi?η??J(θ)?θi求得最优的θ，但是我们说选取η是一个艺术活，这里介绍一种η的选取方式。首先明确一点，我们希望每次改变θ，使得J(θ)越来越小。在梯度确定的情况下，其实ΔJ(θ)是关于η的一个函数：

　　，既然我们想让J(θ)减小，那么干脆每一步都使得|ΔJ(θ)|最大好了，理论上我们可以通过求导求极值，令：
　　?′(η)=0
　　求得此时的η，这样每次改变J(θ)是最大的，而实际操作中，我们一般采用line search的技术来求取η，也就是固定此时的梯度?θ，也就是固定方向，尝试不同的η值，使得
　　J(θ?η??θ)
　　近似最小即可。这样固定方向的搜索和直线搜索没太大区别，也是名字的由来。如果J(θ)是一个二次函数也就是J(θ)=θTAθ+bTθ+c，通过运行算法，我们可以得到一个如下的轨迹：

　　我们可以发现，每一次走的步伐和上一次都是垂直的(事实上是可以证明的，在前面我推荐的文中有详细的证明:-))，这样必然有很多步伐是平行的，造成同一个方向要走好几次。研究最优化的人野心就来了，既然同一个方向要走好几次，能不能有什么办法，使得同一个方向只走一次就可以了呢？ Magnus和Eduard经过研究之后，便设计了这样的方法——Conjugate Gradient Method。
Conjugate Gradient Method
　　具体简明的原理还是强烈推荐《An Introduction to the Conjugate Gradient Method Without the Agonizing Pain》一文，我只讲讲它的表现。CG对于解决大规模线性系统比较奏效，比如下面形式:
　　Ax=b
　　，其中A是方形对称半正定的。对于一个n维度的二次目标函数，我们可以抽象为：
　　J(θ)=0.5?θTAθ+bTθ+c
　　，而在任意点θ′的梯度：
　　?J(θ)=0.5ATθ+0.5Aθ+b=Aθ+b
　　，此时CG的拿手形式就出现了，利用CGM可以保证在每个维度上只走一步，并在n步之内使得算法收敛，也就是实现我们上面提到同一个方向走几次合并为只走一次的算法，上面利用Steepest Method的优化问题利用CGM就变成了如下：

　　二维的情况下，可以保证只走两步就达到收敛。多么神奇啊！我们知道，越是神奇的算法我们必须更加了解他的适用场景，CGM的复杂度依赖于矩阵A,对于稀疏矩阵可以很快，但是对于Dense的，如果可以有效将A分解，那么也是可以的，但是如果不能有效分解(比如内存不足)，那么CGM就不是非常有效了。上述只是说明CGM在线性系统有奏效，对于非线性系统，只要修改一些细节，CG同样有效。总之一句话概括，CGM是对于n维的目标函数可以保证走n步就能到达极值的梯度下降法。一般都有现成的工具库可以使用，只要我们提供目标函数的一次导函数和初始值，CGM就能帮我们找到我们想要的了！一切面纱皆在《An Introduction to the Conjugate Gradient Method Without the Agonizing Pain》文中揭开。
　　Quasi-Newton Method
　　上一节中介绍开源软件包常见的方法Conjugate Gradient Method，这一节我们来介绍另一个常见的方法——Quasi-Newton Method。
Newton Method
　　我们高中的时候数学课本上介绍过牛顿求根法，具体的做法是：对于一个连续可导的函数f(x)，我们如何求取它的零点呢，看看维基百科是如何展示牛老师的方法:

　　如图所示，我们首先随机初始化x0，然后每一次利用曲线在当前xi的切线与横轴的交点作为下一个尝试点xi+1，具体更新公式：

　　，直到f(xi)≈0为止。牛老师告诉我们一个求取函数0点的方法，那么对于我们本篇的优化问题有什么帮助呢，我们知道，函数的极值在于导数为0的点取得，那么我们可以利用牛老师的方法求得导数为0的点啊。我们目的是求取J′(θ)=0对应的θ，那么我们可以依样画葫芦（假设J(θ)是二阶可导的）按照如下更新：

其中J′′(θ)是一个矩阵：

也就是大名鼎鼎的Hession矩阵。而牛顿法更新中:

　　涉及到Hession矩阵的求逆过程，对于一些参数比较多的模型，这个矩阵将非常巨大，计算也极其耗时，所以这就为什么实际项目中很少直接使用牛老师的方法。不过之前我们介绍的方法都只利用了一阶信息，牛老师的方法启发了利用二阶信息优化方式。
L-BFGS算法
　　上一小节中，我们介绍了牛顿法，并且指出它一个严重的缺陷，就是计算Hession矩阵和求逆有时候内存和时间都不允许。那么有什么办法可以近似利用牛顿法呢，也就是有没有Quasi-Newton Method呢？答案是有的，BFGS算法就是一个比较著名的近似牛顿法，对于BFGS的介绍，另外有一篇博客有很好的介绍，具体参阅《Numerical Optimization: Understanding L-BFGS》，也是非常直观简洁的介绍，还附有Java和Scala源码，非常值得学习。
BFGS算法核心在于他利用迭代的方式近似求解Hession矩阵的逆，使得求解Hession矩阵的逆变得不再是神话。而迭代的过程步骤是无限制的，这也会导致内存不足问题，所以工程上利用有限步骤来近似BFGS求解Hession的逆，就成了Limit-BFGS算法。与很多算法一样，这个算法名字是取4位发明者的名字首字母命名的，所以单看名字是没有意义的:-)。

　　以上是几位大佬的尊荣。利用Quasi-Newton法，在处理数据规模不大的算法模型，比如Logistic Regression，可以很快收敛，是所有优化算法包不可或缺的利器。