机器学习导论

Introduction to Machine Learning

第一章 绪论

1.1 什么是机器学习

Arthur Samuel定义的机器学习：在没有明确设置的情况下，使计算机具有学习能力的研究领域。

Tom Mitchell定义的机器学习：一个适当的学习问题定义如下：计算机程序从经验E中学习，解决某一任务T进行某一性能度量P，通过P测试在T上的表现因经验E而提高。

最主要的两类学习算法：监督学习和无监督学习。

• 监督学习：我们会教计算机做某件事情；
• 无监督学习：我们让计算机自己学习；

机器学习方法在大型数据库中的应用称为数据挖掘（data mining）。

机器学习不仅仅是数据库方面的问题，他也是人工智能的组成部分。机器学习还可以帮助我们解决视觉、语音识别以及机器人方面的许多问题。

1.2 机器学习的应用实例

1.2.1 学习关联性

购物篮分析：发现顾客所购商品之间的关联性；打包策略。

关联规则，$P(chips|beer)=0.7$，定义规则，购买啤酒的顾客中有$70%$的人也买了薯片。

1.2.2 分类

信用评分，客户属性及其风险性的关联性。

分类：低风险客户和高风险客户。客户信息作为分类器的输入，分类器的任务是将输入指派到其中的一个类。

规则的用途是预测。

模式识别方面的应用：光学字符识别（OCR），即从字符图像识别字符编码。

人脸识别输入的是人脸，类是需要识别的人，并且学习程序应当学习人脸图像与身份识别之间的关联性。这个问题比OCR更困难，原因是人脸会有更多的类，输入图像也更大一些，并且人脸是三维的，不同的姿势和光线等都会导致图像的显著变化。

对于医学诊断（medical diagnosis），输入是关于患者的信息，而类是疾病。输人包括患者的年龄、性别、既往病史、目前症状等。

在语音识别（speech recognition），输入是语音，类是可以读出的词汇。这里要学习的是从语音信号到某种语言的词汇的关联性。由于年龄、性别或口音方面的差异，不同的人对于相同词汇的读音不同，这使得语音识别问题相当困难。语音识别的另一个特点是其输入信号是时态的（temporal），词汇作为音素的序列实时读出，而且有些词汇的读音会较长一些。一种语音识别的新方法涉及利用照相机记录口唇动作，作为语音识别的补充信息源。这需要传感器融合（sensor fusion）技术，集成来自不同形态的输入，即集成声音和视频信号。

机器学习，自然语言处理，垃圾邮件过滤，机器翻译

生物测定学（biometrics）使用人的生理和行为特征来识别或认证人的身份，需要集成来自不同形态的输人。生理特征的例子是面部图像、指纹、虹膜和手掌；行为特征的例子是签字的力度、嗓音、步态和击键。

从数据中学习规则也为知识抽取提供了可能性。风险识别。

机器学习还可以进行压缩。用规则拟合数据，得到比数据更简单的解释，存储空间更好，计算更少。

离群点检测，即发现那些不遵守规则的例外实例。

1.2.3 回归

回归（regression）问题：预测二手车价格的系统。输入是影响车价的属性信息：品牌、车龄、发动机性能等，输出是车的价格，这种输出为数值的问题。

调查交易情况，收集训练数据，机器学习程序用一个函数拟合这些数据来学习x的函数y。

回归和分类均为监督学习（supervised learning）问题，其中输入x和输出y给定，任务是学习从输入到输出的映射。参数模型，判别式函数，误差最小，非线性函数。

回归的另一个例子是对移动机器人的导航。例如，自动汽车导航。其中输出是每次转动车轮的角度，使得汽车前进而不会撞到障碍物或偏离车道。这种情况下，输入由汽车上的传感器（如视频相机、GPS等）提供。训练数据可以通过监视和记录驾驶员的动作收集。

假设造一个焙炒咖啡的机器，该机器有多个影响咖啡品质的输入：各种温度、时间、咖啡豆种类等配置。针对不同的输入配置进行大量试验，并测量测量咖啡的品质。为寻求最优配置，我们拟合一个联系这些输入和咖啡品质的回归模型，并在当前模型的最优样本附近选择一些新的点，以便寻找更好的配置。我们抽取这些点，检测咖啡的品质，将它们加入训练数据，并拟合新的模型。这通常被称为响应面设计（response surface design）。

1.2.4 非监督学习

监督学习，目标是学习从输入到输出的映射关系，输出的正确值已经由指导者提供。非监督学习中却没有这样的指导者,，只有输入数据。目标是发现输入数据中的规律。输入空间存在着某种结构，使得特定的模式比其他模式更常出现，而我们希望
知道哪些经常发生，哪些不经常发生。在统计学中，这称为密度估计（density estimation）。

密度估计的一种方法是聚类（clustering），其目标是发现输入数据的簇或分组。对于拥有老客户数据的公司，客户数据包括客户的个人统计信息，及其以前与公司的交易，公司也许想知道其客户的分布，搞清楚什么类型的客户会频繁出现。这种情况下，聚类模型会将属性相似的客户分派到相同的分组，为公司提供其客户的自然分组；这称作客户市场划分(customer segmentation)。一旦找出了这样的分组，公司就可能做出一些决策，比如对不同分组的客户提供特别的服务和产品等；这称作客户关系管理（customer relationship management）。这样的分组也可以用于识别”离群点”，即那些不同于其他客户的客户。这可能意味着一块新的市场，公司可以进一步开发。

聚类的有趣应用是图像压缩。图像被量化。主色调。

文档聚类，相似的文档分组。

机器学习方法还应用于生物信息学。计算机科学在分子生物学的应用领域之一就是比对，即序列匹配。很多模板串进行匹配问题。聚类用于学习结构域。

1.2.5 增强学习

在某些应用中，系统的输出是动作的序列。在这种情况下，单个的动作并不重要，重要的是策略，即达到目标的正确动作的序列。不存在中间状态中最好动作这种概念。如果一个动作是好的策略的组成部分，那么该动作就是好的。这种情况下，机器学
习程序就应当能够评估策略的好坏程度，并从以往好的动作序列中学习，以便能够产生策略。这种学习方法称为增强学习（reinforcement learning）算法。

游戏是一个很好的例子。在游戏中，单个移动本身并不重要，正确的移动序列才是重要的。如果一个移动是一个好的游戏策略的一部分，则它就是好的。游戏是人工智能和机器学习的重要研究领域，这是因为游戏容易描述，但又很难玩好。像国际象棋，规则少量几条，但非常复杂，因为在每种状态下都有大量可行的移动，并且每局又都包含有大量的移动。一旦有了能够学习如何玩好游戏的好算法，我们也可以将这些算法用在具有更显著经济效益的领域。

用于在某种环境下搜寻目标位置的机器人导航是增强学习的另一个应用领域。在任何时候，机器人都能够朝着多个方向之一移动。经过多次的试运行，机器人应当学到正确的动作序列，尽可能快地从某一初始状态到达目标状态，并且不会撞到任何障碍物。致使增强学习难度增加的一个因素是系统具有不可靠和不完整的感知信息。例如，装备视频照相机的机器人就得不到完整的信息，因此该机器人总是处于部分可观测状态，并且应当将这种不确定性考虑在内。一个任务还可能需要多智能主体的并行操作，这些智能主体将相互作用并协同操作，以便完成一个共同的目标。

第二章 监督学习

2.1 由实例学习类

学习，实例，被测人，涵盖目标分类的描述，预测。类识别器的输入，训练数据绘制在二维空间上，专家谈论和分析数据，确定范围，假设类集合。训练集，经验误差，预测值，预期值，泛化问题。假设，诱导类。

上海交大张志华机器学习

计算，统计，信息论，算法，控制论，最优化

机器学习=矩阵+优化+算法+统计

回归问题，数据，预测估计，

吴恩达机器学习

网页排序，图像识别，邮件过滤，

1.3 监督学习

数据集，包括正确答案，给出更多正确答案，回归问题，数值的连续输出

分类问题，预测一个离散值的输出，可能两个以上的输出值

无穷多的特征，向量机

1.4 无监督学习

数据集无任何标签，聚类算法，新闻专题，计算机集群，现在octave中建立模型，然后再迁移到其他编程语言。

2.1 模型描述

监督学习是如何工作的，预测房价，每个例子都有一个“正确答案”，也是回归问题的例子，回归是指我们预测一个具体的数值输出。

另一个监督学习常见的例子是分类问题，我们用它来预测离散值输出。做判断。

• M：样本输入量，训练样本的数量，样本容量。
• x：输入值，特征
• y：输出变量，预测的目标变量
• $(x, y)$表示一个训练样本
• $(x^{(i)},y^{(i)})$表示第i个训练样本

向算法提供房价的训练集，算法输出的假设函数，作用是：把房子的大小作为输入变量，h是一个引导从x得到y的函数。

决定怎么表示这个假设函数h。

表示假设函数：$h_\theta =\theta_0+\theta_1 x$

函数的作用是预测y是关于x的线性函数，线性是学习的基础。一元线性回归模型（单变量线性回归）

2.2 代价函数

零

弄清楚如何把最有可能的直线与我们的数据相拟合，$\theta_i$称为模型参数，如何选择这两个参数值$\theta_0$和$\theta_i$，不同的参数值 $\to$ 不同的假设 $\to$ 不同的假设函数；

使$h(x)$，输入x时，我们预测的值最接近该样本对应的y值的参数$\theta_0,\theta_1$

给出标准的定义，在线性回归中，我们要解决的是一个最小化问题，所以要写出$\theta_0,\theta_1$的最小化，式子及其小？$h(x)$与y之间的差异要小，减少假设的输出与房子真实价格之间的差的平方。

对所有训练样本进行一个求和，对$i=1$到$i=M$的样本，将对假设进行预测得到的结果，此时输入是第i号房子的面积，将第i号对应的预测结果，减去第i号房子的实际价格所得的差的平方相加得到总和。$\sum_{i=1}^M[h_\theta(x^{(i)})-y^{(i)}]^2$，尽量减少这个值，也就是预测值和实际值的差的平方，误差和，或者说预测价格和实际卖出价格的差的平方。$\frac{1}{M}\sum_{i=1}^M[h_\theta(x^{(i)})-y^{(i)}]^2$，减少平均误差，表示关于$\theta_0$和$\theta_1$的最小化过程，找到$\theta_0$和$\theta_1$，使这个值最小，转化为目标函数。$\frac{1}{2M}\sum_{i=1}^M[h_\theta(x^{(i)})-y^{(i)}]^2$，加$\frac{1}{2}$是因为后面平方求导多出2

定义一个代价函数，$J(\theta_0,\theta_1)=\frac{1}{2M}\sum_{i=1}^M[h_\theta(x^{(i)})-y^{(i)}]^2$，对于函数$J(\theta_0,\theta_1)$求最小值，常用（对大多数合理），平方误差函数，平方误差代价函数，MSE（mean squared error，均方差），

对于回归问题，是个合理的选择，其他代价函数也可

一

Hypothesis：$h_\theta(x)=\theta_0+\theta_1x$

Parameters：$\theta_0,\theta_1$

Cost Function：$J(\theta_0,\theta_1)=\frac{1}{2M}\sum_{i=1}^M[h_\theta(x^{(i)})-y^{(i)}]^2$

Goal：$\underbrace{minimize}_{\theta_0,\theta_1} J(\theta_0,\theta_1)$，二次函数？

simplified

Hypothesis：$h_\theta(x)=\theta_1x$

Parameters：$\theta_1$

Cost Function：$J(\theta_1)=\frac{1}{2M}\sum_{i=1}^M[h_\theta(x^{(i)})-y^{(i)}]^2$

Goal：$\underbrace{minimize}_{\theta_1} J(\theta_1)$

使代价函数可视化，学习算法的优化目标

二

代价函数的作用，等高线图，等高图像，代价函数图形化，加入$\theta_0,\theta_1$，碗状3维图，碗状曲面，代价函数的形状，从$\theta_0,\theta_1$所在平面截取，即得到等高线图，以后更复杂，更高维

2.5 梯度下降

一种算法，梯度下降法（Gradient descent algorithm），常用，可以将代价函数J最小化，应用于线性回归及机器学习的众多领域，最小化其他函数

Have some fuction $J(\theta_0,\theta_1)$

Want $\underbrace{min}_{\theta_0,\theta_1} J(\theta_0,\theta_1)$

Outline：

• Start with some $\theta_0,\theta_1$（将其初始化都设为0，$\theta_0=0,\theta_1=0$）有时也会初始化为其他值
• Keep changing $\theta_0,\theta_1$ reduce $J(\theta_0,\theta_1)$ until we hopefully end up at a minimun（最小值，局部最小值）

更一般化的问题，$\theta_0,\theta_1,...,\theta_n$

从红色高峰尽快走下山，周围方向，直到收敛至局部最低点

算法特点：不同出发点，到达不同局部最优处

背后的数学原理：（梯度算法的定义）

repeat until convergence（收敛）{

​ $\theta_j:=\theta_j-\alpha\frac{\partial}{\partial\theta_j}J(\theta_0,\theta_1)\ (for\ j=0\ and\ j=1)$

} :=表示赋值，a=b真值判定，第一部分，$\alpha$是被称为学习速率的数字，用来控制梯度下降时，我们迈出多大的步子，$\alpha$越大，梯度下降很迅速，它控制我们以多大的幅度更新这个参数$\theta_j$，第二部分是导数项，有什么用？

correct：Simultaneous update更新参数

$$temp0:=\theta_0-\alpha\frac{\partial}{\partial\theta_0}J(\theta_0,\theta_1)$$ $$temp1:=\theta_1-\alpha\frac{\delta}{\delta\theta_1}J(\theta_0,\theta_1)$$ $$\theta_0:=temp0$$ $$\theta_1:=temp1$$

上面满足同步更新，与下面的方式不同

Incorrect：

$$temp0:=\theta_0-\alpha\frac{\partial}{\partial\theta_0}J(\theta_0,\theta_1)$$ $$\theta_0:=temp0$$ $$temp1:=\theta_1-\alpha\frac{\partial}{\partial\theta_1}J(\theta_0,\theta_1)$$（$$\theta_0$$更新后计算这个倒数项） $$\theta_1:=temp1$$

微妙处，对于更新方程，同时更新$\theta_0,\theta_1$，梯度下降$\to$同步更新

2.6 梯度下降知识点总结

梯度算法是做什么的以及梯度下降算法的更新过程有什么意义

上面梯度算法，两部分有什么用？以及为什么当把这两部分放在一起时，整个更新过程是有意义的？

考虑最小化函数只有一个参数的情形，$\underbrace{min}_{\theta_1} J(\theta_1)，\theta_1\in R$，画出一维的曲线（想象一个二次函数曲线，开口向上），选取一点（正斜率的那点），不断更新，$\theta_1=\theta_1-\alpha*\frac{d}{d\theta_1}J(\theta_1)，\alpha$永远是一个正数，又因为是正斜率，则$\frac{d}{d\theta_1}J(\theta_1)$为正数，$\theta_1$减去正数，其减小，则会向最小点方向移动，更接近最低点；同理我们取斜率为负的点，$\theta_1$会增大。那么研究更新规则$\alpha$，如果其太大或太小会出现什么情况，如果$\alpha$太小，需要很多步才能到达最低点；如果$\alpha$太大，那么梯度下降可能会越过最低点，甚至可能无法收敛或发散？离最低点越来越远，斜率变大，使$\theta_1$的值变化很大，所以无法收敛甚至发散。

如果$\theta_1$已经处在一个局部最优点，下一步梯度下降会怎样？假设将$\theta_1$初始化在局部最低点或最优处，局部最优处导数等于0，导数项为0，$\theta_1$将不再改变，梯度下降更新其实什么都没做，但这正是我们想要的，它使解始终保持在局部最优点。这也解释了，即使学习速率$\alpha$保持不变，梯度下降法也可以收敛到局部最低点的原因。

随着越接近最优处，导数越小接近0，$\theta_0$更新的幅度就会更小，所以梯度下降法会自动采用更小的幅度，这就是梯度下降的运行方式，所以没必要在另外减小$\alpha$。

回归本质，线性回归中的代价函数，平方代价函数，综合梯度下降函数

2.7 线性回归的梯度下降

将梯度下降和代价函数结合，得到线性回归算法，它可以用直线模型来拟合数据，2.2节线性假设和平方差代价函数。将梯度算法应用到最小化平方差代价函数，为了应用梯度下降法，写好repeat until convergence部分代码，关键步骤是那个导数项，弄清楚这个偏导数是什么，写出代价函数J，

写出$\frac{\partial}{\partial\theta_j}J(\theta_0,\theta_1)=\frac{\partial}{\partial\theta_j}\frac{1}{2M}\sum_{i=1}^M[h_\theta(x^{(i)})-y^{(i)}]^2=\frac{\partial}{\partial\theta_j}\frac{1}{2M}\sum_{i=1}^M[\theta_0+\theta_1x^{(i)}-y^{(i)}]^2$

将假设的定义带入，在j等于0和J等于1的时候，两种情况的偏导数，简化，在训练集中求和

一：$j=0:\ \frac{\partial}{\partial\theta_0}J(\theta_0,\theta_1)=\frac{1}{M}\sum_{i=1}^M[h_\theta(x^{(i)})-y^{(i)}]$

二：$j=1:\ \frac{\partial}{\partial\theta_1}J(\theta_0,\theta_1)=\frac{1}{M}\sum_{i=1}^M[h_\theta(x^{(i)})-y^{(i)}]*x^{(i)}$

算出微分，即函数J的斜率，现将他们带回梯度下降算法，

repeat until convergence（收敛）{

​ $\theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m[h_\theta(x^{(i)})-y^{(i)}]$

​ $\theta_1:=\theta_1-\alpha\frac{1}{m}\sum_{i=1}^m[h_\theta(x^{(i)})-y^{(i)}]*x^{(i)}$

} 不断重复该过程直到收敛，$\theta_0和\theta_1$更新为原值减去$\alpha$乘后面的微分项，这就是线性回归算法。注意一些细节，才能同时更新$\theta_0和\theta_1$。梯度算法容易陷入局部最优，如图2，但线性回归的代价函数总是一个弓状函数，凸函数，这个函数没有局部最优解，只有一个全局最优解，总会收敛，

看假设函数$h_{\theta}(x)$和代价函数$J(\theta_0,\theta_1)$，通常在零点初始化，形象解释，初始化$\theta_0=900,\theta_1=-0.1,h(x)=-900-0.1x$，代价函数往下移（接近最优解），假设函数变化，越来越符合数据，Batch梯度下降，每一步下降，都遍历了整个训练集样本m，有的梯度下降算法，每次只关注小的子集。梯度下降适用于更大的数据集。

正规方程组法。

3.1 矩阵和向量

矩阵，数组，矩阵的项，表示，快速访问

向量是一种特殊的矩阵，常用1作为开始下标，大写字母表示矩阵，小写表示数字

3.2 加法和标量乘法

矩阵加法，矩阵乘法（kA），矩阵除法（$A/k=\frac1kA$）

3.3 矩阵向量乘法

类似于矩阵乘法，不过其中有一个矩阵是行向量或者列向量。

$$h_\theta(x)=-40+0.25x$$，转化为矩阵的形式： $$\begin{bmatrix} 1&2014\\ 1&1416\\ 1&1534\\1&852\\ \end{bmatrix} * \begin{bmatrix} -40\\ 0.25\\ \end{bmatrix}=\begin{bmatrix} -40*1+0.25*2104\\ -40*1+0.25*1416\\ -40*1+0.25*1534\\-40*1+0.25*852\\ \end{bmatrix}$$

转化为左边的式子，可以使代码简洁高效，后面线性回归会用到

3.4 矩阵乘法

矩阵乘法是如何解决$\theta_0$和$\theta_1$的问题，不需要用到梯度下降算法的迭代。

矩阵相乘（$A*[b_1,b_2]$），转化为（$[A*b_1,A*b_2]$）。

House sizes: Have 3 competing hypotheses:

$$\begin{cases} 2104\\ 1416\\1534\\852 \end{cases} \quad\quad\quad\quad\quad\quad\quad \left \{ \begin{array}{c} h_\theta(x)=-40+0.25x \\h_\theta(x)=200+0.1x \\h_\theta(x)=-150+0.4x \end{array} \right.$$

构造矩阵

$$\begin{bmatrix} 1&2014\\ 1&1416\\ 1&1534\\1&852\\ \end{bmatrix} * \begin{bmatrix} -40&200&-150\\ 0.25&0.1&0.4\\ \end{bmatrix}=\begin{bmatrix} 480&410&692\\ 314&342&416\\ 344&353&464\\173&285&191\\ \end{bmatrix}$$

线性代数库，并行计算

3.5 矩阵乘法特征

结合律，单位矩阵，是方阵，对角线元素为1。

For any matrix A, $A_{mn}*I_{nn}=I_{mm}*A_{mn}=A_{mn}$

交换律只有当其中有一个矩阵为单位矩阵才满足，且另一个矩阵为方阵。

3.6 逆和转置

If A is an m * m matrix, and if it has an inverse, $AA^{-1}=A^{-1}A=I$

求解逆矩阵的库

4.1 多功能

新的线性回归的版本，这种形式适用于多个变量，或者多特征量的情况，比如之前利用只房租面积来预测房价，现在有房租楼层、年龄等信息，多个特征量，$h(x)=\theta_0+\theta_1x+.....\theta_nx$，多元线性回归

4.2 多元梯度下降法

讨论如何设定该假设的参数，如何使用梯度下降算法来处理多元线性回归，

多元线性回归的假设形式：

Hypothesis: $h_\theta(x)=\theta^Tx=\theta_0x_0+\theta_1x_1+\theta_2x_2.....\theta_nx_n$

Parameters: $\theta_0,\theta_1,...,\theta_n$

Cost function: $J(\theta_0,\theta_1,...,\theta_n)=\frac{1}{2m}\sum_{i=1}^m[h_\theta(x^{(i)})-y^{(i)}]^2$

其中已经按惯例是$x_0=1$，不将其看作n个独立的参数，而是考虑把这些参数看作一个n+1维的$\theta$向量

Gradient descent：（以下面的方式不断更新$\theta_j$）

Repeat {

​ $\theta_j:=\theta_j-\alpha\frac{\partial}{\partial\theta_j}J(\theta_0,...,\theta_n)$

} (simultaneously update for every j=0,…,n)

将此模型的参数看作一个向量，代价函数通过误差项的平方和来给定，但又不把代价函数看作这n+1个数的函数，使用更通用的方式把J写成参数$\theta$这个向量的函数，这里$\theta$是一个向量，

Gradient descent：

Previously(n=1)：n=1时的梯度下降算法

Repeat {

​ $\theta_0:=\theta_0-\alpha\underbrace{\frac1m(h_\theta(x^{(i)})-y^{(i)})}_{\frac{\partial}{\partial\theta_0}J(\theta)}$

​ $\theta_1:=\theta_1-\alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x^{(i)}$

​ (simultaneously update $\theta_0,\theta_1$)

}

两个独立的更新规则，分别对应参数$\theta_0,\theta_1$，这是之前的，看现在的

New algorithm$(n\ge1)$：

Repeat {

​ $\theta_j:=\theta_j-\alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$

​ (simultaneously update $\theta_j$ for j=0,…,n)

}

用于多元函数线性回归的梯度下降算法

相似的，下面，考虑超过两个特征值的情况，因此，有3条更新规则来更新参数$\theta_0,\theta_1,\theta_2$：

• $$\theta_0:=\theta_0-\alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}$$
• $$\theta_1:=\theta_1-\alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_1^{(i)}$$
• $$\theta_2:=\theta_2-\alpha\frac1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_2^{(i)}$$

和之前两个参数的梯度算法是等效的

这样就得到了可行的线性回归模型

4.3 多元梯度下降法演练

4.3.1 特征缩放

有个机器学习问题，这个问题有多个特征，

Feature Scaling

Idea: Make sure features are on a similar scale.（如果能确保这些特征都处在一个相近的范围），这样梯度下降法就能更快地收敛

E.g. $x_1=size(0-2000feet^2)$

​ $x_2=number\ of\ bedrooms(1-5)$

假设有个模型由两个参数，$x_1$表示房屋面积，$x_2$表示卧室数量，画出等值线图，是非常高大细长的椭圆形，构成了代价函数$J(\theta)$的等值线。

如果在这种代价函数上运行梯度下降的话，最终可能需要花很长一段时间，并且可能会来回波动，然后会经过很长时间，最终才收敛到全局最小值。

如果这些等值线更夸张一些，椭圆画的更细更长，结果就是梯度下降更缓慢，反复来回震荡，才找到一条通往全局最小值的路。这种情况下，一种有效的方法是进行特征缩放。

具体来说，如果把特征$x_1$定义为房子的面积大小除以2000，并且把$x_2$定义为卧室的数量除以5，那么代价函数$J(\theta)$的等值线，就会变得偏移没那么严重，就会看起来更圆一些了，如果在这样的函数上执行梯度下降的话，就会找到一条更直接的路径，通向全局最小值，而不像上面那样，沿着一条复杂得多的路径。

因此，通过这些特征缩放，它们的值的范围变得相近，两个特征值都在0和1之间，这样得到的梯度下降算法就会更快地收敛。

更一般地，执行特征缩放时，将特征的取值约束到-1到+1的范围内，具体来说，特征$x_0$总是等于1，因此，这已经是在这个范围内（[-1, +1]），但对其他的特征，可能需要通过除以不同的数，来使其处于这个范围内。

但其实，$\pm1$不重要，如果特征$x_1\in[0,3]$，另一个特征$x_2\in[-2,0.5]$，这些范围其实非常接近$[-1,+1]$，其实都可以。但如果有个特征$x_4\in[-100,+100]$，这个范围和$[-1,+1]$有很大不同了，或者$x_4\in[-0.00001,+0.000001]$那么这同样是一个和$[-1,+1]$不同的范围。如何判断数据的不同，其实因人而异，比如以3为界。

只要范围相差不大，梯度下降算法就可以正常工作。除了将特征值除以最大值以外，在特征值缩放中，有时候也会进行一个称为均值归一化的工作，

Mean normalization

Replace $x_i$ with $x_i-\mu_i$ to make features have approximately zero mean(Do not apply to $x_0=1$).

E.g. $x_1=\frac{size-1000}{2000}$（1000是2000的平均值）

​ $x_2=\frac{\#bedrooms-2}{5}$

​ $-0.5\leq x_1\leq0.5,-0.5\leq x_2\leq0.5$

就是用$x_i-\mu_i$来替换特征$x_i$，让特征值具有为0的平均值，不需要将这一步运用到$x_0$中，因为其始终等于1，不可能有为0的平均值。

还可以这样代替：$x_1\leftarrow \frac{x_1-\mu_1}{s_1}$，定义$\mu_1$是训练集中特征$x_1$的平均值，$s_1$是该特征值的范围，这里的范围是指最大值减去最小值，同理其他特征值。

其实特征缩放并不精确，但能够运行得更快一点而已，迭代次数更少。

4.3.2 学习率

将具体讨论学习率$\alpha$，即梯度算法的更新规则

Gradient descent

​ $\theta_j:=\theta_j-\alpha\frac{\partial}{\partial\theta_j}J(\theta)$

• “Debugging”: How to make sure gradient descent is workinng correctly.
• How to choose learing rate $\alpha$.

调试，小技巧来确保梯度下降是正常工作的，并解释如何选择学习率$\alpha$。

在梯度下降算法工作时，给出代价函数$J(\theta)$的值，x轴表示的是梯度下降算法的迭代次数（与之前不同，之前x轴是$\theta$）。代价函数随迭代步数增加的变化曲线。

A点的含义：运行100次的梯度下降迭代，无论100步迭代后，得到什么$\theta$值，在100次迭代后得到某个$\theta$值，对于这个$\theta$值，将评估代价函数$J(\theta)$，A点的垂直高度就代表：梯度下降算法100步迭代之后得到的$\theta$算出的$J(\theta)$值。后面同理。

这条曲线的用处在于，它可以告诉你，在后面迭代次数增加时，看起来$J(\theta)$并没有下降多少，到达400后，已经很平坦了，梯度下降算法差不多已经收敛了，因为代价函数没有再继续下降了，所以通过这条曲线可以帮助判断，梯度下降算法是否已经收敛。

不同模型的梯度下降算法收敛时迭代次数可能回想相差很大，有些模型梯度下降算法只需要30步迭代就可以达到收敛，然而换一个问题就需要3000步迭代。实际上我们很难判断一个问题的梯度下降算法需要多少步迭代才能收敛，

通常通过看这种曲线来判断，梯度下降算法是否已经收敛，也可以进行一些自动的收敛测试，让另一种算法来判断梯度下降算法是否已经收敛，自动收敛测试。

例：如果代价函数$J(\theta)$一步迭代后的下降小于一个很小的值$\epsilon$，这个测试就判断函数已收敛，$\epsilon$可以是$10^{-3}$，不过通常要选择一个合适的阈值$\epsilon$是相当困难的。因此，为了检测梯度下降算法是否收敛，通常还是通过上面的曲线，这种曲线还可以显示出或警告算法没有正常工作。

如果得到的代价函数随迭代步数增加的变化曲线逐渐上升的曲线，即代价函数随迭代次数增多变得更大（造成这种情况的原因比如，目标函数是二次函数曲线），不趋于稳定，而这样的曲线图通常意味着应该使用较小的学习率$\alpha$（梯度算法会不断越过最小值，得到代价函数越来越大）。

已证明，学习率足够小，那么每次迭代后代价函都会下降；但不易过小。

每隔10倍（3倍）取一个$\alpha$值，然后对于这些不同的$\alpha$值，绘制$J(\theta)$随迭代步数变化的曲线，然后选择使得$J(\theta)$快速下降的一个$\alpha$值，如何找到合适的学习率。

找到一个太小的值，再找到另一个太大的值，然后取最大可能值，或者比最大值略小一些的，比较合理的值。

4.4 特征和多项式回归

一些可供选择的特征，以及如何得到不同的学习算法，当选择了合适的特征后，这些算法往往是非常有效的，

多项式回归，使得能够使用线性回归的方法来拟合非常复杂的函数，甚至是非线性函数，以预测房价为例，

假设有两个特征，分别是房子临街的宽度（$x_1$）和垂直宽度（$x_2$），在用线性回归时，不一定非要用$x_1$和$x_2$作为特征，可以创造新的特征，因此，如果要预测房子的价格，会做的是确认真正能够决定房子大小的是拥有的土地的大小。新的特征即临街宽度与纵深的乘积，就是拥有土地的面积，于是将这个乘积作为假设，只用一个特征，就是土地的面积。具体问题取决视情况而定，有时通过定义新的特征，可以得到更好的模型。

与选择特征的想法，密切相关的一个概念，被称为多项式回归，例如，现有这样一个住房价格的数据集，可能会有多个不同的模拟用于拟合，选择之一是像这样的二次模型，直线似乎并不能很好地拟合这些数据，因此，会想到，用这样的二次模型去拟合，会考虑到价格可能是一个二次函数，得到曲线一样的拟合结果，二次模型合理吗？因为一个二次模型最终会（先上升）降下来，但事实是房价会随着面积增加而下降？因此，也许会选择一个不同的多项式模型，并转而选择使用一个三次函数，用其进行拟合，不会最后下降。那么如何将模型与数据进行拟合呢？

使用多元线性回归的方法，对算法做一个简单的修改来实现它，按照之前的假设，

即$h_\theta(x)=\theta_0+\theta_1(size)+\theta_2(size)^2+\theta_3(size)^3,x_1=(size),x_2=(size)^2,x_3=(size)^3$特征缩放变得重要，因为房子大小在1到1000之间，那么立方就会到$10^9$，因此这三个特征有很大不同，这样才能将值的范围变得具有可比性，

除了3次模型不会下降，还有$h_\theta(x)=\theta_0+\theta_1(size)+\theta_2\sqrt{(size)}$凭借对数据的形状和函数的了解，

4.5 正规方程（区别于迭代方法的直接解法）

目前为止，一直使用线性回归方法，梯度下降法，

Normal equation: Method to solve for $\theta$ analytically.（不用迭代，一次性求解$\theta$的最优值）

优缺点及何时使用这个算法

Intuition: if 1D ($\theta\in R$)

​ $J(\theta)=a\theta^2+b\theta+c$

这是个二次函数，怎么求极值，倒数置0，

$$\theta\in R^{n+1}\quad J(\theta_0,\theta_1,...,\theta_m)=\frac{1}{2m}\sum_{i=1}^m[h_\theta(x^{(i)})-y^{(i)}]^2 \quad \frac{\partial}{\partial\theta_j}J(\theta)=...=0 (for every j)$$

Solve for $\theta_0,\theta_1,...,\theta_n$

这里实际问题中$\theta$是n+1维向量，代价函数是关于这个向量的函数，那么现在如何最小化这个函数呢？是对向量中每个参数$\theta_j$对代价函数求偏导，然后把这些偏导数全部置0。

但是遍历所有偏微分，麻烦，

Example：m=4，4个训练样本，如何使用正规方程方法，假设这4个样本是所有数据，加一列对应额外特征变量的$x_0$，

$x_0$	Size$(feet^2) \ x_1$	Number of bedrooms $x_2$	Number of floors $x_3$	Age of home (years) $x_4$	Price($1000)
1	2104	5	1	45	460
1	1416	3	2	40	232
1	1534	3	2	30	315
1	852	2	1	36	178

构建一个矩阵X，$X=\begin{bmatrix} 1&2014&5&1&45\\ 1&1416&3&2&40\\ 1&1534&3&2&30\\1&852&2&1&36\\ \end{bmatrix}\quad \quad y=\begin{bmatrix}460\\232\\315\\178 \end{bmatrix}$

X是一个$m*(n+1)$维矩阵，y是一个m维向量，

使用$\theta=(X^TX)^{-1}X^Ty$，就能得到使代价函数最小化的$\theta$。

m examples $(x^{(1)},y^{(1)}),...,(x^{(m), y^{m}})$; n features.

所以每个训练样本可能是：$x^{i}=\begin{bmatrix}x_0^{(i)}\\x_1^{(i)}\\x_2^{(i)}\\...\\x_n^{(i)} \end{bmatrix}\in R^{n+1}$

构建矩阵的方法，设计矩阵，用上面向量的转置作为矩阵X的行

矩阵X是一个$m*(n+1)$维矩阵，$X=\begin{bmatrix} (x^{(1)})^T\\ (x^{(1)})^T\\ ...\\(x^{(m)})^T\\ \end{bmatrix}$

使用正规方程方法就不需要特征缩放，

何时应该使用梯度下降法，何时使用正规方程法（优点和缺点）

m training examples, n feature.

Gradient Descent

• 缺点
  • Need to choose $\alpha$.
  • Needs many iterations.更多的迭代
• 优点
  • Works well even when n is large.

Normal Equation

• 优点
  • No need to choose $\alpha$.（也不需要检测收敛性）
  • Don’t need to iterate.
• 缺点
  • Need to compute $(X^TX)^{-1}$，n*n的矩阵，计算量大，$O(n^3)$
  • Slow if n is very large

根据习惯，n大于1万，就使用梯度算法，

4.6 正规方程在矩阵不可逆情况下的解决方法

4.7 导师的编程小技巧