该系列笔记内容是楼主在观看课程时记录的，其中图片是视频中ppt的截图，内容仅供参考，有问题欢迎大家指出。

常见的最优化算法

• 在机器学习的世界中，很多问题并没有最优的解，或是要计算出最优的解要花费很大的计算量，面对这类问题一般的做法是利用迭代的思想尽可能的逼近问题的最优解
  感兴趣的同学可以看最优化算法——常见优化算法分类及总结
• 特征缩放（Feature Scaling）
  • 在使用绝大多数优化算法前最好对数据做一定处理，将所有特征标准化，使其数值尽量接近 [-1, 1] 这个区间（数值不要太大或太小，吴恩达推荐缩放范围在 [-3, 3] 都能接受）
  • 这样做可以使得优化算法下降速率不是那么的缓慢，即收敛所需的迭代数少，下图以梯度下降法为例说明特征不同取值范围的影响

特征不同取值范围的影响

• 均值归一化（Mean Normalization）
  • 最常见的特征缩放方法是均值归一化：可以根据公式$\frac{x_i-\mu_i}{si}$sixi​−μi​​进行标准化，这样使得最后取值范围结果尽量以0对称；其中μ_i表示平均值，s_i是标准差

均值归一化

1. 梯度下降算法（Batch Gradient Descent）

对整个训练集（名字中batch的含义）进行求和计算

梯度下降算法步骤

• 上图为梯度下降算法步骤，其中 := 表示赋值操作，=表示两边值相等，θ_j表示更新后的特征值，α表示学习速率（决定更新参数θ_j的幅度）
• 公式中$\frac{\partial}{\partial\theta_j}J(\theta_0, \theta_1)$∂θj​∂​J(θ0​,θ1​)为偏导，用于算出当前特征对于代价函数全局（或局部）最低点的方向，以便向最低点靠近；并且梯度下降会根据偏导的减小自动下降的速度降低
• 值得注意的是，在更新特征θ₀和θ₁时需要同步进行，否则代价函数将会发生变化导致其中一方的数值不准

梯度下降法示意图

• 如上面右图所示，若学习速率α过小则下降速度会很慢，若过大则容易达不到局部最低点

1.1 多元梯度下降法计算

• 与前者相似，在多元梯度下降中需要同时更新所有特征，其中偏导得到的公式为$\frac{\partial}{\partial\theta_j}J(\theta)=\frac{1}{m}\sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$∂θj​∂​J(θ)=m1​i=1∑m​(hθ​(x(i))−y(i))xj(i)​
• 注意原来代价函数中的$\frac{1}{2}$21​被消去，后面多了x⁽ⁱ⁾（视x₀⁽ⁱ⁾为1），即得到下图右侧的式子

多元梯度下降算法步骤

• 将输入和特征进行向量化，令$x^{(i)}=\begin{bmatrix} x_0^{(i)}\\ x_1^{(i)}\\ \vdots\\ x_n^{(i)}\\ \end{bmatrix}$x(i)=⎣⎢⎢⎢⎢⎡​x0(i)​x1(i)​⋮xn(i)​​⎦⎥⎥⎥⎥⎤​表示输入向量，$\Theta=\begin{bmatrix} \theta_0\\ \theta_1\\ \vdots\\ \theta_n\\ \end{bmatrix}$Θ=⎣⎢⎢⎢⎡​θ0​θ1​⋮θn​​⎦⎥⎥⎥⎤​表示特征向量，令$\delta_j=\frac{1}{m}\sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$δj​=m1​∑i=1m​(hθ​(x(i))−y(i))xj(i)​，向量$\Delta=\begin{bmatrix} \delta_0 \\ \delta_1 \\ \vdots \\ \delta_n \\ \end{bmatrix}$Δ=⎣⎢⎢⎢⎡​δ0​δ1​⋮δn​​⎦⎥⎥⎥⎤​，则可以得到更新式为$\Theta:=\Theta-\alpha\Delta$Θ:=Θ−αΔ

向量化多元梯度下降法

• 值得注意的是，梯度下降法在线性回归和逻辑回归中的更新式子相同，但是其中假设函数h(x)有所区别

1.2 学习率（Learning Rate）

• 在梯度下降法中学习率α很重要，合适的学习率可以使得算法用较少的迭代次数达到较优解
• 对于不同机器学习的问题所需要的迭代次数可能差别很大

使用合适学习率的迭代-代价图

• 一般很难预测需要多少步迭代才能使得函数收敛，但是有两种办法可以在学习过程中调整学习率：
  1. 通过画出迭代-损失图进行判断调整（推荐）
  2. 自动收敛测试：即判断代价函数是否下降到某个很小的值ε，但选择阈值ε较困难，所以通常不建议使用
• 迭代-损失图判断：
  1. 学习率大时：下图左侧两种情况（另外若下降速度过缓也可能是由于α过大），即随着迭代次数的增多逐渐发散，或曲线成波动型时，则表示需要更小的学习率
  2. 学习率小时：会造成梯度下降速率的降低，即迭代次数的增多损失下降不明显

学习率过大造成的影响

• 建议调整测试的时候以三倍的增长学习率α

学习率调整测试

1.3 优化梯度下降法

优化梯度下降法使得更适合处理大数据集

1.3.1 随机梯度下降法（Stochastic Gradient Descent）

• 具体步骤：
  1. 随机打乱样本集，使得数据重新排列
  2. 依次计算每个单独样本的代价，即每次迭代只看一个样本，不需要对全部样本求和后再更新特征值
  3. 循环步骤2以保证正确性，循环次数取决于数据集大小以及计算情况（一般1到10次左右即可，样本数极大的情况下1次就足够）

随机梯度下降法步骤

• 与梯度下降法不同的是，随机梯度下降法不会直接找到全局最优，而是可能在最小值区域内徘徊，但是能得到很接近全局最小值的特征值
• 在线学习（Online Learning）——随机梯度下降法的变形：
  • 每从网站上获取到新的数据时，对参数θ及时更新，并且不保留数据，从而能够随着时间的变化更好的适应环境
  • 整体步骤与随机梯度下降法相似，区别是学习中不需要用固定的样本数据，而是实时获取，更新完即可扔掉，不用保存

1.3.2 Mini-batch梯度下降法（Mini-batch Gradient Descent）

• 与（每次迭代使用所有样本的）梯度下降法和（每次只用一个样本的）随机梯度下降法不同的是，Mini-batch梯度下降法每次迭代用b（称为Mini-batch Size）个样本

Mini-batch梯度下降法与其他梯度下降法的区别

1.3.3 优化梯度算法的学习率选择

• 在使用某些（或某个）样本更新θ前，计算并保存该代价函数，同时规定每用i次迭代后将其的迭代-损失图绘制出来

优化梯度算法的学习率表现

• 如上图中左下曲线所示，当有噪音明显时（蓝色曲线），可以通过增加迭代次数再次绘图
• 若绘制的曲线下降缓慢甚至平行（粉色曲线），或逐渐发散（上图右下），则需要将学习率调小一些
• 值得注意的是，设置学习率α随着迭代次数逐渐减小有助于更加接近最小值，如$\alpha=\frac{const\ 1}{interation\ num\ +\ const\ 2}$α=interation num + const 2const 1​

2. 正规方程（Normal Equation）

对于某些线性回归问题可以更好的求得参数θ的最优值

• 与梯度下降法的迭代不同，正规方程通过一次性求解即可获得特征θ的最优值
• 其基本思想是求导置零，即计算每个偏导并通过使所有值为0求得各个最优解，可以用于计算较为复杂的函数式

求导置零思想

• 正规方程表达式如下图所示，值得注意的是，若使用正规方程则无需进行特征缩放

正规方程表达式

---

小插曲：线性代数问题——X^TX奇异/不可逆怎么办？

• 不可逆的原因有如下两点：
  1. 特征冗余（特征线性相关）
  2. 特征远大于样本数
• 解决办法：可以通过删除特征，或使用正则化技术解决

---

3. 前两种方法比较

梯度下降法与正规方程算法对比

• 梯度下降法需要选择学习率，并且需要不断迭代运算出最优解；而正规方程则不需要，一步到位
• 由于正规方程计算X^TX，即量级是梯度下降的N倍，建议在规模大于10000的时候可以开始考虑使用梯度下降法

4. 高级优化算法

这些算法更适合大型机器学习问题（如有数目庞大的特征），比梯度下降法更适合计算逻辑回归函数

• 高级优化算法有：共轭梯度法、BFGS、L-BFGS等等
• 优点：无需手动选择学习率（线搜索算法可以智能选择合适学习率），且收敛速度比梯度下降法快
• 缺点：算法更为复杂，需要十分了解其中的原理

5. MapReduce架构（分布式）

该架构可以使得优化算法更快的处理大样本数据集，其中单机上的计算还可以节省传输成本

MapReduce架构原理

• 上图是以平均误差代价函数和梯度递归方程为例解释MapReduce架构原理，基本思想是将数据等量的分程n个部分并让不同计算机（或单机副CPU/多核）进行处理，得到的结果一并传回中心服务器（或单机主CPU/某个核）求和，并对参数θ进行更新