In the last video, we talked 在上一个视频中 我们讨论了 (字幕整理：中国海洋大学 黄海广,haiguang2000@qq.com )
about gradient descent for minimizing 用梯度下降的方法最小化
the cost function J of theta for logistic regression. 逻辑回归中代价函数 J(θ)
In this video, I'd like to 在本次视频中 我会
tell you about some advanced 教你们一些
optimization algorithms and some 高级优化算法和一些
advanced optimization concepts. 高级的优化概念
Using some of these ideas, we'll 利用这些方法 我们就能够
be able to get logistic regression 使通过梯度下降
to run much more quickly than 进行逻辑回归的速度
it's possible with gradient descent. 大大提高
And this will also let 而这也将使
the algorithms scale much better 算法更加适合解决
to very large machine learning problems, 大型的机器学习问题
such as if we had a very large number of features. 比如 我们有数目庞大的特征量
Here's an alternative view of 现在我们换个角度
what gradient descent is doing. 来看什么是梯度下降
We have some cost function J and we want to minimize it. 我们有个代价函数 J 而我们想要使其最小化
So what we need to 那么我们需要做的是
is, we need to write 我们需要
code that can take 编写代码
as input the parameters theta and 当输入参数 θ 时
they can compute two things: J 它们会计算出两样东西
of theta and these partial J(θ) 以及
derivative terms for, you J等于 0 1直到 n 时的
know, J equals 0, 1 偏导数项
up to N. Given code that 假设我们已经完成了
can do these two things, what 可以实现这两件事的代码
gradient descent does is it 那么梯度下降所做的就是
repeatedly performs the following update. 反复执行这些更新
Right? 对吧？
So given the code that 所以给出我们
we wrote to compute these partial 用于计算这些的偏导数的代码
derivatives, gradient descent plugs 梯度下降法就把它插入
in here and uses that to update our parameters theta. 到这里 从而来更新参数 θ
So another way of thinking 因此另一种考虑
about gradient descent is that 梯度下降的思路是
we need to supply code to 我们需要写出代码
compute J of theta and 来计算 J(θ) 和
these derivatives, and then 这些偏导数 然后
these get plugged into gradient 把这些插入到梯度下降中
descents, which can then try to minimize the function for us. 然后它就可以为我们最小化这个函数
For gradient descent, I guess 对于梯度下降来说 我认为
technically you don't actually need code 从技术上讲 你实际并不需要编写代码
to compute the cost function J of theta. 来计算代价函数 J(θ)
You only need code to compute the derivative terms. 你只需要编写代码来计算导数项
But if you think of your 但是 如果你希望
code as also monitoring convergence 代码还要能够监控
of some such, 这些 J(θ) 的收敛性
we'll just think of 那么我们就
ourselves as providing code to 需要自己编写代码
compute both the cost 来计算
function and the derivative terms. 代价函数和偏导数项
So, having written code to 所以 在写完能够
compute these two things, one 计算这两者的代码之后
algorithm we can use is gradient descent. 我们就可以使用梯度下降
But gradient descent isn't the only algorithm we can use. 但梯度下降并不是我们可以使用的唯一算法
And there are other algorithms, 还有其他一些算法
more advanced, more sophisticated ones, 更高级 更复杂
that, if we only provide 如果我们能用
them a way to compute 这些方法来计算
these two things, then these 这两个项的话 那么这些算法
are different approaches to optimize 就是为我们优化
the cost function for us. 代价函数的不同方法
So conjugate gradient BFGS and 共轭梯度法 BFGS (变尺度法) 和
L-BFGS are examples of more L-BFGS (限制变尺度法) 就是其中
sophisticated optimization algorithms that 一些更高级的优化算法
need a way to compute J 它们需要有一种方法来计算 J(θ)
of theta, and need a way 以及需要一种方法
to compute the derivatives, and can 计算导数项
then use more sophisticated 然后使用比梯度下降更复杂
strategies than gradient descent to minimize the cost function. 的算法来最小化代价函数
The details of exactly what 这三种算法的具体细节
these three algorithms is well beyond the scope of this course. 超出了本门课程的范畴
And in fact you often 实际上你最后通常会
end up spending, you know, many days, 花费很多天
or a small number of weeks studying these algorithms. 或几周时间研究这些算法
If you take a class and advance the numerical computing. 你可以专门学一门课来提高数值计算能力
But let me just tell you about some of their properties. 不过让我来告诉你他们的一些特性
These three algorithms have a number of advantages. 这三种算法有许多优点
One is that, with any 一个是
of this algorithms you usually do 使用这其中任何一个算法 你通常
not need to manually pick the learning rate alpha. 不需要手动选择学习率 α
So one way to think 所以对于
of these algorithms is that given 这些算法的一种思路是 给出
is the way to compute the derivative and a cost function. 计算导数项和代价函数的方法
You can think of these algorithms as having a clever inter-loop. 你可以认为算法有一个智能的内部循环
And, in fact, they have a clever 而且 事实上 他们确实有一个智能的
inter-loop called a line 内部循环
search algorithm that automatically 称为线性搜索(line search)算法 它可以自动
tries out different values for 尝试不同的
the learning rate alpha and automatically 学习速率 α 并自动
picks a good learning rate alpha 选择一个好的学习速率 α
so that it can even pick 因此它甚至可以
a different learning rate for every iteration. 为每次迭代选择不同的学习速率
And so then you don't need to choose it yourself. 那么你就不需要自己选择
These algorithms actually do 这些算法实际上在做
more sophisticated things than just 更复杂的事情 而不仅仅是
pick a good learning rate, and 选择一个好的学习率
so they often end up 所以它们往往最终
converging much faster than gradient descent. 收敛得远远快于梯度下降
These algorithms actually do more 这些算法实际上在做
sophisticated things than just 更复杂的事情 不仅仅是
pick a good learning rate, and 选择一个好的学习速率
so they often end up converging much 所以它们往往最终
faster than gradient descent, but 比梯度下降收敛得快多了 不过
detailed discussion of exactly 关于它们到底做什么的详细讨论
what they do is beyond the scope of this course. 已经超过了本门课程的范围
In fact, I actually used 实际上 我过去
to have used these algorithms for 使用这些算法
a long time, like maybe over 已经很长一段时间了 也许超过
a decade, quite frequently, and it 十年了 使用得相当频繁
was only, you know, a 而直到几年前
few years ago that I actually 我才真正
figured out for myself the details 搞清楚
of what conjugate gradient, BFGS and O-BFGS do. 共轭梯度法 BFGS 和 L-BFGS的细节
So it is actually entirely possible 因此 实际上完全有可能
to use these algorithms successfully and 成功使用这些算法
apply to lots of different learning 并应用于许多不同的学习
problems without actually understanding 问题 而不需要真正理解
the inter-loop of what these algorithms do. 这些算法的内环间在做什么
If these algorithms have a disadvantage, 如果说这些算法有缺点的话
I'd say that the main 那么我想说主要
disadvantage is that they're 缺点是它们比
quite a lot more complex than gradient descent. 梯度下降法复杂多了
And in particular, you probably should 特别是你最好
not implement these algorithms 不要使用 L-BGFS BFGS这些算法
- conjugate gradient, L-BGFS, BFGS - 共轭梯度 L-BGFS BFGS
yourself unless you're an expert in numerical computing. 除非你是数值计算方面的专家
Instead, just as I 实际上
wouldn't recommend that you write 我不会建议你们编写
your own code to compute square 自己的代码来计算
roots of numbers or to 数据的平方根或者
compute inverses of matrices, for 计算逆矩阵
these algorithms also what I 因为对于这些算法我
would recommend you do is just use a software library. 还是会建议你直接使用一个软件库
So, you know, to take a square 所以 要求一个平方根
root what all of us 我们所能做的
do is use some function 就是调用一些
that someone else has 别人已经
written to compute the square roots of our numbers. 写好用来计算数字平方根的函数
And fortunately, Octave and 幸运的是 有 Octave 和
the closely related language MATLAB 与它密切相关的 MATLAB 语言
- we'll be using that - 我们将会用到它们
Octave has a very good. Has a pretty Octave 有一个非常
reasonable library implementing some of these advanced optimization algorithms. 理想的库用于实现这些先进的优化算法
And so if you just use 所以 如果你直接调用
the built-in library, you know, you get pretty good results. 它自带的库 你就能得到不错的结果
I should say that there is 我必须指出
a difference between good 这些算法
and bad implementations of these algorithms. 实现得好或不好是有区别的
And so, if you're using a 因此 如果你正在你的
different language for your machine 机器学习程序中使用一种不同的语言
learning application, if you're using 比如如果你正在使用
C, C++, Java, and C C + + Java
so on, you 等等 你
might want to try out a couple 可能会想尝试一些
of different libraries to make sure that you find a 不同的库 以确保你找到一个
good library for implementing these algorithms. 能很好实现这些算法的库
Because there is a difference in 因为
performance between a good implementation 在 L-BFGS 或者等高线梯度的
of, you know, contour gradient or 实现上
LPFGS versus less good 表现得好与不太好
implementation of contour gradient or LPFGS. 是有差别的
So now let's explain how 因此现在让我们来说明
to use these algorithms, I'm going to do so with an example. 如何使用这些算法 我打算举一个例子
Let's say that you have a 比方说 你有一个
problem with two parameters 含两个参数的问题
equals theta zero and theta one. 这两个参数是 θ0 和 θ1
And let's say your cost function 那么你的成本函数
is J of theta equals theta J(θ)等于 θ1
one minus five squared, plus theta two minus five squared. 减去5的平方 再加上 θ2 减5的平方
So with this cost function. 因此 通过这个代价函数
You know the value for theta 1 and theta 2. 你可以得到 θ1 和 θ2 的值
If you want to minimize J of theta as a function of theta. 如果你将 J(θ) 最小化的话
The value that minimizes it is 那么它的最小值
going to be theta 1 将是 θ1
equals 5, theta 2 equals equals five. 等于5 θ2 等于5
Now, again, I know some of 我知道你们当中
you know more calculus than others, 有些人比别人微积分更好
but the derivatives of the 但是你应该知道代价函数 J 的导数
cost function J turn out to be these two expressions. 推出来就是这两个表达式
I've done the calculus. 我已经写在这儿了
So if you want to apply 那么你就可以应用
one of the advanced optimization algorithms 高级优化算法里的一个
to minimize cost function J. 来最小化代价函数 J
So, you know, if we 所以 如果我们
didn't know the minimum was at 不知道最小值
5, 5, but if you want to have 是5 5 但你想要
a cost function 5 the minimum 代价函数找到这个最小值
numerically using something like 是用比如
gradient descent but preferably more 梯度下降这些算法 但最好是用
advanced than gradient descent, what 比它更高级的算法
you would do is implement an octave 你要做的就是运行一个
function like this, so we 像这样的 Octave 函数 那么我们
implement a cost function, 运行一个函数
cost function theta function like that, 比如 costFunction
and what this does is that 这个函数的作用就是
it returns two arguments, the 它会返回两个值
first J-val, is how 第一个是 jVal 它是
we would compute the cost function 我们计算的代价函数 J
J. And so this says J-val 所以说 jVal
equals, you know, theta 等于 theta(1)
one minus five squared plus theta 减5的平方加
two minus five squared. theta(2) 减5的平方
So it's just computing this cost function over here. 这样就计算出这个代价函数
And the second argument that 函数返回的第二个值是
this function returns is gradient. 梯度值
So gradient is going to 梯度值应该是
be a two by one vector, 一个2×1的向量
and the two elements of the 梯度向量的两个元素
gradient vector correspond to 对应
the two partial derivative terms over here. 这里的两个偏导数项
Having implemented this cost function, 运行这个 costFunction 函数后
you would, you can then 你就可以
call the advanced optimization 调用高级的优化函数
function called the fminunc 这个函数叫 fminunc
- it stands for function 它表示
minimization unconstrained in Octave Octave 里无约束最小化函数
-and the way you call this is as follows. 调用它的方式如下
You set a few options. 你要设置几个 options
This is a options 这个 options 变量
as a data structure that stores the options you want. 作为一个数据结构可以存储你想要的 options
So grant up on, 所以 GradObj 和 On
this sets the gradient objective parameter to on. 这里设置梯度目标参数为打开(on)
It just means you are indeed going to provide a gradient to this algorithm. 这意味着你现在确实要给这个算法提供一个梯度
I'm going to set the maximum number 然后设置最大
of iterations to, let's say, one hundred. 迭代次数 比方说 100
We're going give it an initial guess for theta. 我们给出一个 θ 的猜测初始值
There's a 2 by 1 vector. 它是一个2×1的向量
And then this command calls fminunc. 那么这个命令就调用 fminunc
This at symbol presents a 这个@符号表示
pointer to the cost function 指向我们刚刚定义的
that we just defined up there. costFunction 函数的指针
And if you call this, 如果你调用它
this will compute, you know, will use 它就会
one of the more advanced optimization algorithms. 使用众多高级优化算法中的一个
And if you want to think it as just like gradient descent. 当然你也可以把它当成梯度下降
But automatically choosing the learning 只不过它能自动选择
rate alpha for so you don't have to do so yourself. 学习速率α 你不需要自己来做
But it will then attempt to 然后它会尝试
use the sort of advanced optimization algorithms. 使用这些高级的优化算法
Like gradient descent on steroids. 就像加强版的梯度下降法
To try to find the optimal value of theta for you. 为你找到最佳的 θ 值
Let me actually show you what this looks like in Octave. 让我告诉你它在 Octave 里什么样
So I've written this cost function 所以我写了这个关于theta的
of theta function exactly as we had it on the previous line. 的 costFunction 函数 跟前面幻灯片中一样
It computes J-val which is the cost function. 它计算出代价函数 jval
And it computes the gradient with 以及梯度 gradient
the two elements being the partial gradient 有两个元素
derivatives of the cost function 是代价函数对于
with respect to, you know, theta(1) 和 theta(2) 这两个参数的
the two parameters, theta one and theta two. 偏导数
Now let's switch to my Octave window. 现在 让我们切换到Octave窗口
I'm gonna type in those commands I had just now. 我把刚刚的命令敲进去
So, options equals optimset. This is options = optimset 这是
the notation for setting my 在我的优化算法的 options上
parameters on my options, 设置参数
for my optimization algorithm. Grant option on, maxIter, 100 的记号
so that says 100 这样就是100
iterations, and I am 次迭代
going to provide the gradient to my algorithm. 我现在要给我的算法提供梯度值
Let's say initial theta equals zero's two by one. 设置 theta 的初始值是一个2×1的零向量
So that's my initial guess for theta. 这是我猜测的 theta 初始值
And now I have of theta, 现在我就可以
function val exit flag 写出三个返回值
equals fminunc constraint. [optTheta, functionVal, exitFlag] 等于
A pointer to the cost function. 指向代价函数的指针 @costFunction
and provide my initial guess. 我猜测的初始值 initialTheta
And the options like so. 还有options
And if I hit enter this will run the optimization algorithm. 如果我敲回车 这个就会运行优化算法
And it returns pretty quickly. 它很快返回值
This funny formatting that's because 这个格式很有意思
my line, you know, my 因为我的代码
code wrapped around. 是被缠住了
So, this funny thing 所以这个有点意思
is just because my command line had wrapped around. 完全是因为我的命令行被绕住了
But what this says is that 不过这里只是
numerically renders, you know, think 数字上的一些问题
of it as gradient descent 把它看成是加强版梯度下降
on steroids, they found the optimal value of 它们找到 theta 的最优值
a theta is theta 1 是 theta(1) 为5 theta(2) 也为5
equals 5, theta 2 equals 5, exactly as we're hoping for. 这正是我们希望的
The function value at the functionVal 的值
optimum is essentially 10 to the minus 30. 实际上是10的-30次幂
So that's essentially zero, which 所以 这基本上就是0
is also what we're hoping for. 这也是我们所希望的
And the exit flag is exitFlag为1
1, and this shows 这说明它的状态
what the convergence status of this. 是已经收敛了的
And if you want you can do 你也可以运行
help fminunc to help fminunc 命令
read the documentation for how 去查阅相关资料
to interpret the exit flag. 以理解 exitFlag 的作用
But the exit flag let's you verify whether or not this algorithm thing has converged. exitFlag可以让你确定该算法是否已经收敛
So that's how you run these algorithms in Octave. 这就是在 Octave 里运行这些算法的过程
I should mention, by the way, 哦对了 这里我得指出
that for the Octave implementation, this value 用 Octave 运行的时候
of theta, your parameter vector 向量θ的值 θ的参数向量
of theta, must be in 必须是 d 维的
rd for d greater than or equal to 2. d 大于等于2
So if theta is just a real number. 所以 θ 仅仅是一个实数
So, if it is not at least 因此如果它不是
a two-dimensional vector 一个至少二维的向量
or some higher than two-dimensional 或高于二维的向量
vector, this fminunc fminunc 就可能无法运算
may not work, so and if 因此如果你有一个
in case you have a 一维的函数需要优化
one-dimensional function that you use 一维的函数需要优化
to optimize, you can look 你可以查找 Octave 里 fminuc 函数的资料
in the octave documentation for fminunc 来得到更多的细节
for additional details. 来得到更多的细节
So, that's how we optimize 这就是我们如何优化