注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

开新坑系列第一篇——梯度下降与线性回归(随时弃坑)  

2017-09-12 14:14:20|  分类: oi无关向 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
正如很久以前写的上一篇文章一样,这个系列的文章是为了给现高三保送党的人看的,难度偏易。
本来是想写神经网络的,但是一上来就直接写神经网络的话我不是很知道从何写起,所以这个第一篇就从机器学习最简单的部分说起了,所以第一篇选了这个内容。
希望做到每周产出一篇吧。
待续。
===================================
好,我们先讲一个很简单的问题,回归问题。
先来看一个可能OI考试中就遇到过的题目,假设平面上有n个点,你要找一条直线y=kx+b,尽量拟合这n个点。拟合的定义的话就是,假设点i是(xi,yi),你要求k,b最小化Σ(kxi+b-yi)^2
这个大家肯定会做,ZJOI都出过,就是最小二乘法,这个大家学线代就肯定知道,简单地说就是假设||x||表示向量x的模长,给定矩阵n*m矩阵A,m*1向量x和n*1向量b,我要最小化||Ax-b||,就有x=(A^Tb)*(A^TA)^{-1},然后如果A^TA不可逆的话就有多解blablabla。如果不会用线代来推的话,就求偏导然后列方程,能得到一样的式子。
现在我们引入另一个做法,梯度下降。这个做法在这道题上写起来没最小二乘法简单,精确度肯定不如最小二乘法直接得到答案,时间复杂度各有所长(因为参数不同),但是这个方法适用范围非常广。
首先假设你学过多元函数微积分,你就知道梯度。如果没有学过的话也很容易理解,只要你知道偏导数就好了。假设对于多元函数f(x,y,z),那么(偏f/偏x,偏f/偏y,偏f/偏z)就是梯度,梯度就是函数增长速度最快的方向,取符号就是变小速度最快的方向。
这个题目要求的函数有个性质,就是函数图像是这样的开新坑系列第一篇——梯度下降与线性回归(随时弃坑) - ydc - ydc的博客(其实不确切,总之是一个叫凸函数的东西),你可以想象是一个山谷,我们每次沿着负梯度方向跑的话,就相当于一个登山者每次沿着下降速度最快的地方往下滑,然后如果是山谷的话肯定就会滑到谷底了
所以算法流程很简单,你随机一个点作为初始答案,定义一个步长参数λ(比如取个0.1,0.01之类的),然后每次减去步长乘以当前点的梯度,然后循环个很多次,就可以收敛到最终解了。
该算法只要是凸函数就靠谱,如果不是凸函数的话,就容易陷入局部极小值
最后要做的就是推导一下这个函数的梯度了……顺便把问题从平面进行推广,我们现在不是假设平面上有n个点,而是D维空间有n个点xi,每个点有个输出yi,你要找一个m维向量θ,要使得f(θ)=Σ(θ^T*xi-yi)^2/2n最小,(为什么要/2n呢,/n是取个平均值,这样对比误差的话就不会受n的大小的影响。/2是为了式子好看,因为待会求导会正好把2消掉),那么对θj的偏导数就是Σ(θ^T*xi-yi)*xij/n,其中xij表示点xi的第j维坐标。
(天哪写个最简单的梯度下降法解线性回归就搞得我好像要弃坑了)
下次可能会讲logistics回归以及科普一下机器学习是什么东西……但是如果我坑掉了的话就可能只有科普文了。
  评论这张
 
阅读(159)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018