`
deepfuture
  • 浏览: 4321323 次
  • 性别: Icon_minigender_1
  • 来自: 湛江
博客专栏
073ec2a9-85b7-3ebf-a3bb-c6361e6c6f64
SQLite源码剖析
浏览量:79303
1591c4b8-62f1-3d3e-9551-25c77465da96
WIN32汇编语言学习应用...
浏览量:68103
F5390db6-59dd-338f-ba18-4e93943ff06a
神奇的perl
浏览量:101192
Dac44363-8a80-3836-99aa-f7b7780fa6e2
lucene等搜索引擎解析...
浏览量:280262
Ec49a563-4109-3c69-9c83-8f6d068ba113
深入lucene3.5源码...
浏览量:14535
9b99bfc2-19c2-3346-9100-7f8879c731ce
VB.NET并行与分布式编...
浏览量:65153
B1db2af3-06b3-35bb-ac08-59ff2d1324b4
silverlight 5...
浏览量:31187
4a56b548-ab3d-35af-a984-e0781d142c23
算法下午茶系列
浏览量:45069
社区版块
存档分类
最新评论

梯度下降法

 
阅读更多

一、基本概念

梯度下降法,就是利用负梯度方向来决定每次迭代的新的搜索方向,使得每次迭代能使待优化的目标函数逐步减小。梯度下降法是2范数下的最速下降法。 最速下降法的一种简单形式是:x(k+1)=x(k)-a*g(k),其中a称为学习速率,可以是较小的常数。g(k)是x(k)的梯度。

二、导数

(1)定义

 

设有定义域和取值都在实数域中的函数 y=f(x)\;。若 f(x)\; 在点 \;x_0\; 的某个邻域内有定义,则当自变量 \;x\;\;x_0\; 处取得增量 \Delta x\;(点 \;x_0+\Delta x\; 仍在该邻域内)时,相应地函数 \;y\; 取得增量 \Delta y=f(x_0+\Delta x)-f(x_0)\,\!;如果 \Delta \;y\;\Delta \;x\; 之比当 \Delta x\to 0 时的极限存在,则称函数 y=f(x)\,\! 在点 \;x_0\;可导,并称这个极限为函数 y=f(x)\,\! 在点 \;x_0\; 处的导数,记为 f'(x_0)\;,即:

 

f'(x_0)=\lim_{\Delta x \to 0}\frac{\Delta y}{\Delta x}=\lim_{\Delta x \to 0}\frac{f(x_0+\Delta x)-f(x_0)}{\Delta x}

也可记作 y^\prime (x_0)\left.\frac{\mathrm{d}y}{\mathrm{d}x}\right|_{x=x_0}\frac{\mathrm{d}f}{\mathrm{d}x}(x_0)\left.\frac{\mathrm{d}f}{\mathrm{d}x}\right|_{x=x_0}

对于一般的函数,如果不使用增量的概念,函数 f(x)\; 在点 x_0\; 处的导数也可以定义为:当定义域内的变量 x\; 趋近于 x_0\; 时,

\frac{f(x)-f(x_0)}{x - x_0}

的极限。也就是说,

f'(x_0)=\lim_{x \to x_0}\frac{f(x)-f(x_0)}{x - x_0}

 

 

 

 

导数反应的变化率

一个函数在某一点的导数描述了这个函数在这一点附近的变化率。导数的本质是通过极限的概念对函数进行局部的线性逼近。当函数f的自变量在一点x_0上产生一个增量h时,函数输出值的增量与自变量增量h的比值在h趋于0时的极限如果存在,即为fx_0处的导数,记作f'(x_0)\frac{\mathrm{d}f}{\mathrm{d}x}(x_0)\left.\frac{\mathrm{d}f}{\mathrm{d}x}\right|_{x=x_0}

 

(2)几何意义:

 

 

 

一个实值函数的图像曲线。函数在一点的导数等于它的图像上这一点处之切线的斜率,导数是函数的局部性质。不是所有的函数都有导数,一个函数也不一定在所有的点上都有导数。若某函数在某一点导数存在,则称其在这一点可导,否则称为不可导。如果函数的自变量和取值都是实数的话,那么函数在某一点的导数就是该函数所代表的曲线在这一点上的切线斜率。

具体来说:

当函数定义域和取值都在实数域中的时候,导数可以表示函数的曲线上的切线斜率。如下图所示,设P_0为曲线上的一个定点,P为曲线上的一个动点。当P沿曲线逐渐趋向于点P_0时,并且割线P P_0的极限位置P_0 T存在,则称P_0 T为曲线在P_0处的切线。

若曲线为一函数y=f(x)的图像,那么割线P P_0(蓝色)的斜率为:

\tan \varphi=\frac{\Delta y}{\Delta x}=\frac{f(x_0 + \Delta x)-f(x_0)}{\Delta x}

P_0处的切线P_0 T(红色),即P P_0的极限位置存在时,此时\Delta x \to 0\varphi \to \alpha,则P_0 T的斜率\tan \alpha为:

\tan \alpha=\lim_{\Delta x \to 0} \tan \varphi=\lim_{\Delta x \to 0} \frac{f(x_0 + \Delta x)-f(x_0)}{\Delta x}

上式与一般定义中的导数定义完全相同,也就是说f'(x_0)=\tan \alpha,因此,导数的几何意义即曲线y=f(x)在点P_0 (x_0,f(x_0))处切线的斜率 

 

(3)导函数

 

 导数是一个数,是指函数 f(x)\; 在点 x_0\; 处导函数的函数值,若函数 \;f(x)\; 在其定义域包含的某区间 \;I\; 内每一个点都可导,那么也可以说函数\;f(x)\; 在区间 \;I\; 内可导,这时对于 \;I\; 内每一个确定的\;x\; 值,都对应着 \;f\; 的一个确定的导数值,如此一来就构成了一个新的函数x \mapsto f'(x),这个函数称作原来函数 \;f(x)\;导函数,记作:\;y'\;f'(x)\; 或者 \frac{\mathrm{d}f}{\mathrm{d}x}(x),通常也可以说导函数为导数

 

 

 

 

 

 3、一元函数微分

微分和导数是两个不同的概念。但是对一元函数来说,可微与可导是完全等价的概念。可微的函数,其微分等于导数乘以自变量的微分dx,换句话说,函数的微分与自变量的微分之商等于该函数的导数。因此,导数也叫做微商。于是函数y = f(x)的微分又可记作dy = f'(x)dx[

 

(1)微分反应的变化率

微分可以近似地描述当函数自变量的取值作足够小的改变时,函数的值是怎样改变的。当某些函数\scriptstyle f的自变量\scriptstyle x有一个微小的改变\scriptstyle h时,函数的变化可以分解为两个部分。一个部分是线性部分:在一维情况下,它正比于自变量的变化量\scriptstyle h,可以表示成\scriptstyle h和一个与\scriptstyle h无关,只与函数\scriptstyle f\scriptstyle x有关的量的乘积;在更广泛的情况下,它是一个线性映射作用在\scriptstyle h上的值。另一部分是比\scriptstyle h更高阶的无穷小,也就是说除以\scriptstyle h后仍然会趋于零。当改变量\scriptstyle h很小时,第二部分可以忽略不计,函数的变化量约等于第一部分,也就是函数在\scriptstyle x处的微分,记作\displaystyle f'(x)h\displaystyle df_x(h)。如果一个函数在某处具有以上的性质,就称此函数在该点可微。

(2)定义

设函数y = f(x)在某区间\mathcal{I}内有定义。对于\mathcal{I}内一点x_{0},当x_{0}变动到附近的x_{0}+\Delta x(也在此区间内)时。如果函数的增量\Delta y = f(x_{0}+ \Delta x) - f(x_{0})可表示为 \Delta y = A \Delta x + o( \Delta x)(其中A是不依赖于\Delta x的常数),而o( \Delta x)是比\Delta x高阶的无穷小,那么称函数f(x)在点x_{0}是可微的,且A \Delta x称作函数在点x_{0}相应于自变量增量\Delta x的微分,记作dy,即dy = A \Delta xdy\Delta y线性主部[1]:141

通常把自变量x的增量\Delta x称为自变量的微分,记作dx,即dx = \Delta x

(3)几何意义

 

函数在一点的微分。其中红线部分是微分量dy,而加上灰线部分后是实际的改变量\Delta y

 

 

 

\Delta x曲线y = f(x)上的点P在横坐标上的增量,\Delta y曲线在点P对应\Delta x在纵坐标上的增量,dy是曲线在点P切线对应\Delta x在纵坐标上的增量。当\left| \Delta x \right|很小时,\left| \Delta y - dy \right|\left| \Delta y \right|要小得多(高阶无穷小),因此在点P附近,我们可以用切线段来近似代替曲线段。

 

 

(4)关于无穷小量

 

A)

如果一个序列 a=(a_n)_{n\in \mathbb{N}} 如果满足如下性质:

 

用极限符号把上述性质简记为

\lim_{n\to \infty} a_n = 0

则序列 a 被称为 n\to \infty 时的无穷小量[

B)阶的比较

a=(a_n)_{n\in \mathbb{N}}b=(b_n)_{n\in \mathbb{N}} 为两个序列,而且都是 n\to \infty时的无穷小量。虽然它们在 n 趋于无穷时都趋于零,但趋于零的速度是有区别的。可以用如下方式比较它们的速度:

  • 若对于任意正实数 \displaystyle c>0 ,存在正整数 \displaystyle N 使得

 

 a_k < c \cdot b_k


\displaystyle k>N 时总是成立,则称 \displaystyle a\displaystyle b高阶无穷小,记作

 

\displaystyle a_n=o\Big(b_n\Big) ~ ~ ~ (n\to \infty)


其中的 n\to \infty 有时也被省略不写。

在上述定义中,也可以说无穷小量 a 的阶要比 b 的要高,或者说 ab 更快地趋于零

 


 4、多元函数微分

(1) 欧几里得空间

 

\mathbb R表示实数域。对任意一个正整数n,实数的n元组的全体构成了\mathbb{R}上的一个n维向量空间,用\mathbb{R}^n来表示。有时称之为实数坐标空间\mathbb{R}^n中的元素写作X=(x_1,x_2,\cdots,x_n),这里的x_i都是实数。\mathbb{R}^n作为向量空间,其运算是这样定义的:

\mathbf{x} + \mathbf{y} = (x_1 + y_1, x_2 + y_2, \ldots, x_n + y_n)
a\,\mathbf{x} = (a x_1, a x_2, \ldots, a x_n)

 欧几里得空间,则是在\mathbb{R}^n上再添加一些内容:欧几里得结构。
为了做欧氏几何,人们希望能讨论两点间的距离,直线或向量间的夹角。一个自然的方法是在\mathbb{R}^n上,对任意两个向量\mathbf{x}\mathbf{y},引入它们的“标准内积”(一些文献上称为点积,记为\mathbf{x}\cdot\mathbf{y}):

 = \sum_{i=1}^n x_iy_i = x_1y_1+x_2y_2+\cdots+x_ny_n

也就是说,\mathbb{R}^n中的任意两个向量对应着一个实数值。 我们把\mathbb{R}^n及这样定义的内积,称为\mathbb{R}^n上的欧几里得结构;此时的\mathbb{R}^n也被称为n维欧几里得空间,内积"<,>"称为欧氏内积

利用这个内积,可以建立距离、长度、角度等概念:

  • 向量\mathbf{x}的长度:
\|\mathbf{x}\| = \sqrt{} = \sqrt{\sum_{i=1}^{n}(x_i)^2}

这里的长度函数满足范数所需的性质,故又称为\mathbb{R}^n上的欧氏范数

  • \mathbf{x}\mathbf{y}所夹的内角以下列式子给出
\theta = \cos^{-1}\left(\frac{}{\|\mathbf{x}\|\|\mathbf{y}\|}\right)

这里的\cos^{-1}为反余弦函数。

  • 最后,可以利用欧氏范数来定义\mathbb{R}^n上的距离函数,或称度量
d(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\| = \sqrt{\sum_{i=1}^n (x_i - y_i)^2}

这个距离函数称为欧几里得度量,它可以看作勾股定理一种形式。

这里的\mathbb{R}^n仅指实数向量空间,而加入了如上定义的欧几里得结构后才称为欧氏空间;有些作者会用符号\mathbb{E}^n来标记之。欧氏结构使\mathbb{E}^n具有这些空间结构:内积空间、希尔伯特空间、赋范向量空间以及度量空间。

 

 

(2)开集

开集是指不包含自己边界点的集合。或者说,开集把它所包含的任何一点的充分小的邻域也包含在其自身之中。开集的概念一般与拓扑概念是紧密联系着的,通常先公理化开集,然后通过其定义边界的概念。

 

函数分析

在Rn中点集是开集,如果在这个集合的所有点P都是内部点。

 

 

内点

S 为欧几里得空间的子集。若存在以 x 为中心的开球被包含于 S,则 xS 的内点。

这个定义可以推广到度量空间 X 的任意子集 S。具体地说,对具有度量 d 的度量空间 XxS 的内点,若对任意 r > 0,存在 y 属于 S,且 d(x, y) < r

 点 xS 的内部点,因为它包含在 S 内并有一个开球围绕着它。点 yS 的边界上

 

欧几里得空间

n维欧几里得空间Rn的子集U是开集,如果给定任何在U中的点x,存在一个实数ε > 0使得,如果给定任何Rn中点y,有着从x到它的欧几里得距离小于ε,则y也属于U。等价的说,U是开集,如果所有U中的点有包含在U中的邻域。

 

 

(3)定义

f是从欧几里得空间Rn(或者任意一个内积空间)中的一个开集\Omega射到Rm的一个函数。对于\Omega中的一点x及其在\Omega中的邻域\Lambda中的点x+h。如果存在线性映射A使得对任意这样的x+h,

\lim_{h \to 0} \left( \frac{|f (x+h) - f(x) - A(h)|}{|h|} \right) = 0

那么称函数f在点x处可微。线性映射A叫做f在点x处的微分,记作df_x

如果f在点x处可微,那么它在该点处一定连续,而且在该点的微分只有一个。为了和偏导数区别,多元函数的微分也叫做全微分全导数

当函数在某个区域的每一点x都有微分df_x时,可以考虑将x映射到df_x的函数:

df : x \mapsto df_x

这个函数一般称为微分函数

全微分(英语:total derivative)是微积分学的一个概念,指多元函数的全增量\Delta z的线性主部,记为\operatorname dz。例如,对于二元函数z=f(x,\ y),设f在点P_0(x_0,\ y_0)的某个邻域内有定义,P(x_0+\Delta x,\ y_0+\Delta y)为该邻域内的任意一点,则该函数在点P_0(x_0,\ y_0)的全增量可表示为

\Delta z = A\Delta x+B\Delta y + o(\rho)

其中AB仅与xy有关,而与\Delta x\Delta y无关,\rho=\sqrt{(\Delta x)^2 +(\Delta y)^2}。若o(\rho)是当\rho \rightarrow 0时的高阶无穷小,则称此函数z=f(x,\ y)在点 (x,\ y)可微分,而A\Delta x+B\Delta y即为函数z=f(x,\ y)在点P_0(x_0,\ y_0)的全微分,记作

\operatorname dz|_{x=x_0,\ y=y_0} = A\Delta x + B\Delta y

\operatorname df(x_0,y_0) = A\Delta x + B\Delta y

(4)邻域

是拓扑空间中的基本概念。直觉上说,一个点的邻域是包含这个点的集合,并且该性质是外延的:你可以稍微“抖动”一下这个点而不离开这个集合。

 

在平面上集合 V 是点 p 的邻域,如果围绕 p 小圆盘包含在 V

 

 

如果 X 是拓扑空间 而 pX 中的一个点,p邻域是集合 V,它包含了包含 p 的开集 U

p \in U \subseteq V

注意 V 自身不必须是开集。如果 V 是开集则它被称为开邻域。某些作者要求邻域是开集,所以注意约定是很重要的。

一个点的所有邻域的集合叫做在这点上的邻域系统。

如果 SX 的子集,S邻域是集合 V,它包含了包含 S 的开集 U。可得出集合 VS 的邻域,当且仅当它是在 S 中的所有点的邻域。

 

 

 

在度量空间 M = (X,d) 中,集合 V 是点 p邻域,如果存在以 p 为中心和半径为 r 的开球,

B_r(p) = B(p;r) = \{ x \in X \mid d(x,p) < r \}

它被包含在 V 中。

V 叫做集合 S一致邻域,如果存在正数 r 使得对于 S 的所有元素 p

B_r(p) = \{ x \in X \mid d(x,p) < r \}

被包含在 V 中。

对于 r>0 集合 Sr-邻域 S_rX 中与 S 的距离小于 r 的所有点的集合(或等价的说 S_r 是以 S 中一个点为中心半径为 r 的所有开球的并集)。

可直接得出 r-邻域是一致邻域,并且一个集合是一致邻域当且仅当它包含对某个 r 值的 r-邻域。

平面上的集合 SS 的一致邻域 V

 

 

五、梯度

1、相关概念

假如一个空间中的每一点的属性都可以以一个标量来代表的话,那么这个场就是一个标量场。

假如一个空间中的每一点的属性都可以以一个向量来代表的话,那么这个场就是一个向量场

标量场中某一点上的梯度指向标量场增长最快的方向,梯度的长度是这个最大的变化率。

梯度一词有时用于斜度,也就是一个曲面沿着给定方向的倾斜程度。

2、计算

一个标量函数\varphi的梯度记为:

\nabla \varphi\rm grad \varphi

其中\nabla(nabla)表示矢量微分算子。

在三维情况,该表达式在直角坐标中扩展为

\nabla \phi =\begin{pmatrix}
{\frac{\partial \phi}{\partial x}},  
{\frac{\partial \phi}{\partial y}}, 
{\frac{\partial \phi}{\partial z}}
\end{pmatrix}

 

 

六、梯度下降法

梯度下降法,基于这样的观察:如果实值函数 F(\mathbf{x}) 在点 \mathbf{a} 处可微且有定义,那么函数 F(\mathbf{x})\mathbf{a} 点沿着梯度相反的方向 -\nabla F(\mathbf{a}) 下降最快。

因而,如果

\mathbf{b}=\mathbf{a}-\gamma\nabla F(\mathbf{a})

对于 \gamma>0 为一个够小数值时成立,那么 F(\mathbf{a})\geq F(\mathbf{b})

考虑到这一点,我们可以从函数 F 的局部极小值的初始估计 \mathbf{x}_0 出发,并考虑如下序列 \mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots 使得

\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n \nabla F(\mathbf{x}_n),\ n \ge 0.

因此可得到

F(\mathbf{x}_0)\ge F(\mathbf{x}_1)\ge F(\mathbf{x}_2)\ge \cdots,

如果顺利的话序列 (\mathbf{x}_n) 收敛到期望的极值。注意每次迭代步长 \gamma 可以改变。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics