CS229 Gradient Descent

闲暇无事，看了一下吴恩达教授的CS229的课程，对于梯度下降有一些新的感受。

注：下面的文字，你将不会看到有关梯度下降的基础内容，这些在其他博客已经说的很详细了，下面仅仅是，我认为之前没有认识到的地方

Batch Gradient Descent

之前在做感知机算法的时候，用到了批量梯度下降，当时就与小伙伴争论了一下，Batch Gradient Descent 的具体形式，今天看完CS229的有关梯度下降的部分，我们彻底搞明白了他是怎么回事？

沿用吴恩达教授课程中的例子：
房屋价格的预测，线性回归问题

hypothesis function

在线性回归问题中，我们用最小二乘法作为损失函数：

Loss Function

然后，梯度下降：

Gradient Descent
这是针对单一样本，如果是所有样本的话就是：
all samples

这次，更正我们Batch Gradient Descent 要求平均的思想。
对，可能有人会问，\gamma去哪里了？
是这样的，我们假设一个x=1,那么\gamma * x就是\gamma所以就化成了统一的形式。

在此更正补充：
之前在做感知机的时候，在损失函数前面除了一个样本数目，我一直以为他是在求平均值，到最近我研究损失函数，风险函数，经验风险，结构风险的时候才明白，损失函数是评价一个样本与真值之间的差距，而风险函数也就是损失函数代表了模型的好坏，但是我们是没法求风险函数的，但是根据大数定律，我们可以用期望风险来代替风险函数，其实就像经验熵，只要带上经验两个字，一般都是估计得来的，最后，又因为当样本少的时候，经验风险会带来过拟合的情况，所以又用到了结构风险。
至于，为什么CS229中吴恩达教授用的是损失函数，我认为可能是：
1、并不影响，只是学习率大小的关系
2、还没有讲到经验风险

stochastic gradient descent

我看了一下，我在做感知机的时候好像忘了说，随机梯度下降的东西，现在一起补上，
首先，也是最重要的：
随机梯度下降是在数据量非常非常大的时候才用，而且是损失了自己的精度来加快速度，谁要是再把他用在五个点的感知机模型上，我把你鸡儿给你打折
其次，随机梯度下降最终可能会达不到（一定？）最优的结果，他可能会在局部最优解附近徘徊，注意是：局部最优解，也就是说，梯度下降的原始形式也是不一定可以到达最优解的。
然后，正是因为SGD可能会在最优解附近徘徊，所以我们应该在怎么判断现在的结果是否收敛了呢？吴恩达教授说：
可以设置一个阈值，如果两次迭代，更新的值小于这个值，我们就认为已经收敛了。
最后，是在课堂上，一个stanford的学生提的一个问题，为什么在梯度下降的过程中，更新的数值越来越小。
尽管在后来看来这个问题不难，而且没有什么意义，但是确实是我之前没有想到的。
答案是：随着不断地迭代，梯度这个值就会不断地减小，所以总的就会减小。

梯度值减小

The Normal Equaltion

前面使用了梯度下降的方法解决这个回归问题，那么我们知道，不断地迭代是一个很耗费时间的过程，那么我们怎么来省去迭代的过程？这就涉及到另一种最小值的解法。

matrix multilpy

这是对于单一样本，如果是所有样本呢？设：

all samples

解释一下这个X，实际上X是所有样本的集合，每一行都是一个样本的特征向量。所以：

h(x) - y

需要注意的是:这里X的转置与theta相乘是矩阵乘法，不要以为是向量内积，而且要注意下标m与n的区别
然后，又因为：

prove it by youself
所以：
Loss Function
现在我们要求Loss的最小值，那么我们自然而然想到了对theta求导，为了与课程中的公式保持一致，下面用Z表示X的转置：
求导
解释一下上面的式子：
首先，第二步，这里用到了矩阵的迹trace，也就是矩阵对角线元素的和，根据迹的性质，实数的迹还是实数本身
A为非奇异方阵

第三步，用到了第一个图中的第一个性质，而且最后一个向量乘积为常数，在求导时被消去。
第四步，用到了公式3。
然后，我们只需要让导数为0，然后求出参数theta。

Normal Equaltion

解得：

result
这样我们就避免了耗费时间的迭代过程，但是我们来思考一下，他是不是什么情况都可以用？

从结果看起，这里用到了矩阵的逆，那么矩阵必须是非奇异方阵，但是我们可以证明一下：
Z是一个mxn的矩阵，那么Z的转置是一个nxm的矩阵，那么Z乘Z的转置就是一个mxm的对称矩阵，那么，只有这个对称矩阵所有值都相同时，这个矩阵的行列式才等于零，所以说，大部分情况还是可以用的，包括前面trace的性质也一样。

Only The Strong Survive