机器学习导论

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 正规方程在矩阵不可逆情况下的解决方法

$$\theta=(X^TX)^{-1}X^Ty$$

如果$X^TX$不可逆怎么办？其实这种情况很少发生。

不可逆的原因：

• 包含多余的特征
  • E.g. $x_1=size\ in\ feet^2\quad x_2=size\ in\ m^2$（两个特征线性相关）
• 有很多特征（E.g. $m\leq m$）

伪逆

5.1 基本操作

Octave

控制语句while，if，break

5.2 移动数据

将训练集导入程序

5.3 计算数据

矩阵间操作

5.4 数据绘制

5.5 矢量

线性代数库

Vectorization example:

$$h_\theta(x)=\sum_{j=0}^n\theta_jx_j=\theta^Tx$$

可以转化为两个向量的内积

6.1 分类

要预测的变量y是一个离散值，情况下的分类问题，开发一个logistics回归算法，当时最流行最广泛使用的学习算法之一，

例子：Classification

Email: Spam/Not Spam?

Online Transactions: Fraudulent(Yes/No)? 网上交易是否欺诈

Tumor: Malignant/Benign? 肿瘤分类

都有以下两变量

​ $y\in \{0,1\}$ 0: “Negative Class”(e.g., benign tumor)负类

​ 1: “Positive Class”(e.g., malignant tumor)正类

先讨论二分类问题，稍后多分类问题$y\in \{0,1,2,3\}$，

如何开发一个分类算法？

阈值Threshold classifier output $h_\theta(x)\ at\ 0.5$:即纵坐标值为0.5

• If $h_\theta(x)\ge 0.5$, predict “y=1”
• If $h_\theta(x)\lt 0.5$, predict “y=0”

线性回归也可以简单分类，但会出现问题，

黄线运气好，拟合得很好，对用阈值A也分类很好；但加入P点后，反而效果没那么好了

Classification: y=0 or 1, $h_\theta(x)\ can\ be\ \gt1\ or \lt 0$，预测值远大于1或远小于0，就离谱，

后面介绍的logistic算法，得到的预测值总会在0到1之间

6.2 假设陈述

开始谈logistic回归，函数表达，解释

Logistic Regression Model

Want $0\le h_\theta(x)\le 1$

$$h_\theta(x)=g(\theta^Tx)$$

sigmoid函数或logistic函数$g(z)=\frac{1}{1+e^{-z}}$，函数图像

则$h_\theta(x)=\frac{1}{1+e^{-\theta^Tx}}$

解释：假设h(x)的输出，当假设输出某个数字，把这个数字当做对一个输入x，y=1的概率估计，

肿瘤Example: If $x=\begin{bmatrix}x_0\\x_1\end{bmatrix}=\begin{bmatrix}1\\tumorSize\end{bmatrix}\quad h_\theta(x)=0.7$

将一位病人的tumorSize输入已经建立好的模型，得到输出0.7，

解释：对于一个特征为x的患者，y=1的概率是0.7，也就是说这个患者70%或者说0.7的可能性是恶性肿瘤，

公式表达：$h_\theta(x)=P(y=1|x;\theta)$，即在给定x的条件下y=1的概率。

这是个分类任务，y必须是0或1，

则$P(y=0|x;\theta)+P(y=1|x;\theta)=1\quad P(y=0|x;\theta)=1-P(y=1|x;\theta)$

6.3 决策陈述

决策边界的概念，帮助理解logistic函数，及假设函数在计算什么，

sigmoid函数，何时会将y预测为1，何时将其预测为0；假设函数的特征，形状，多个特征时。

具体地说，这个假设函数输出的是给定x和参数$\theta$时，y=1的估计概率；因此如果想要预测y=1还是等于0，可以这样做：（取决于估计概率）

Suppose predict “y=1” if $h_\theta(x)\ge0.5$ predict “y=0” if $h_\theta(x)\lt0.5$

等于0.5的情况预测哪个都行，这里归为1类，

还有，$when\ z\ge0,g(z)\ge0.5$，同理，$when\ \theta^Tx\ge0,h_\theta(x)=g(\theta^Tx)\ge0.5$

Decision Boundary $h_\theta(x)=g(\theta_0+\theta_1x_1+\theta_2x_2)$

如何拟合次模型中的参数？（下一节）现假设已经拟合好了参数，

假设$h_\theta(x)=g(-3+1x_1+1x_2)\quad 向量\theta=[-3,1,1]$

Predict “y=1” if $-3+x_1+x_2\ge0, 也就是x_1+x_2\ge3$，对应图像上半区域，同理，小于0对应下半区域，两个区域的边界线称为决策边界，即$x_1+x_2=3$这条直线，等于0.5的点，

决策边界是假设函数的一个属性，即使去掉图上的点圈，边界依然存在，决定于其参数，并不是数据集的属性，不需要通过绘制训练集来确定边界，

更复杂的例子：Non-liner decision boundaries（叉代表正样本，圈代表负样本）

怎么拟合呢？多特征？高阶多项？

这样$h_\theta(x)=g(\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x^2_1+\theta_4x^2_2)$添加额外2个特征，现有5个参数，假设向量$\theta=[-1,0,0,1,1]$

Predict “y=1” if $-1+x^2_1+x^2_2\ge0$，的特征越复杂，决策边界也就越复杂，不仅仅是用直线隔开，

更复杂的边界$h_\theta(x)=g(\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x^2_1+\theta_4x^2_2+\theta_5x^2_1x^2_2+\theta_6x^3_1x_2+...)$

6.4 代价函数

拟合logistics函数，

监督学习中logistic回归模型的拟合问题：

Training set: {$(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(m)},y^{(m)})$}

m examples $x\in\begin{bmatrix}x_0\\x_1\\...\\x_n\end{bmatrix}\quad x_0=1,y\in \{0,1\}\quad h_\theta(x)=\frac{1}{1+e^{-\theta Tx}}$

How to choose parameters $\theta$ ?

在之前的代价函数基础上改进

Cost Function: $J(\theta)=\frac{1}{m}\sum_{i=1}^m\frac12[h_\theta(x^{(i)})-y^{(i)}]^2$

将$Cost(h_\theta(x^{(i)}),y^{(i)})=\frac12[h_\theta(x^{(i)})-y^{(i)}]^2$

代价函数变为：$J(\theta)=\frac{1}{m}\sum_{i=1}^mCost(h_\theta(x^{(i)},y^{(i)}) \quad h_\theta(x)$是很复杂的非线性函数，所以会导致代价函数是非凸函数（波浪线），局部最优；

抹掉(i)，平方定义，会得到凹函数，全局最小值

Logistic regression cost function: $Cost(h_\theta(x,y)=\begin{cases} -log(h_\theta(x))\quad if\ y=1\\ -log(1-h_\theta(x))\quad if\ y=0 \end{cases}$

画出图像看，凸优化问题

6.5 简化代价函数与梯度下降

如何实现一个完整的logistic回归算法

Logistic regression cost function: 分类问题

$$J(\theta)=\frac{1}{m}\sum_{i=1}^mCost(h_\theta(x^{(i)},y^{(i)}) \quad Cost(h_\theta(x,y)=\begin{cases} -log(h_\theta(x))\quad if\ y=1\\ -log(1-h_\theta(x))\quad if\ y=0 \end{cases}$$

Note: $y=0\ or\ 1\ always$对于分类问题y总是非0即1

则$Cost(h_\theta(x^{(i)},y^{(i)})=-ylog(h_\theta(x))+(1-y)log(1-h_\theta(x))$带入原代价函数，极大似然法，统计学

To fit parameters $\theta$: $\underbrace{min}_\theta J(\theta)$

To make a prediction given new x: output $h_\theta(x)=\frac{1}{1+e^{-\theta Tx}}$

输出概率，如何最小化这个代价函数，这样才能为训练集拟合出参数$\theta$，梯度下降

Gradient descent：

$$J(\theta)=-\frac1m[\sum_{i=1}^my^{(i)}logh_\theta(x^{(i)})+(1-y^{(i)})log(1-h_\theta(x^{(i)}))]$$

Want $\underbrace{min}_\theta J(\theta)$

Repeat {

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

​ (simultaneously update $\theta_j$)

}

logistic回归对比之前的线性回归，$h_\theta$已发生变化，更新规则相同，但由于假设的定义发生了变化，所以和线性回归的梯度下降是两个完全不同的东西。

6.6 高级优化

高级优化算法和高级优化的概念，与梯度算法相比，大大提高logistic回归的速度，更适合解决大型机器学习问题

Optimization algorithm

Cost function $J(\theta)$. Want $\underbrace{min}_\theta J(\theta)$

Given $\theta$, we have code that can compute（代码计算下面两值）

—- $J(\theta)$ （收敛性）

—- $\frac{\partial}{\partial\theta_j}J(\theta)\quad (for j=0,1,...,n)$

Gradient descent:（带入，更新）

Repeat {

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

}

Optimization algorithms:（更高级的优化算法，需要一种方法来计算$J(\theta)$和偏导项）

• Gradient descent
• Conjugate gradient
• BFGS（共轭梯度法）
• L-BFGS

上面的第2,3,4个算法优点和缺点：

• 优点
  • 不需要手动选择学习率$\alpha$，给出计算导数项和代价函数的方法，智能内循环（线性搜索算法，自动尝试不同的学习率并自动选择一个好的学习速率，甚至可以为每次迭代选择不同的学习速率）
  • 收敛得远远快于梯度下降，更复杂的事情，不止于选择一个好的学习率，
• 缺点
  • 比梯度下降复杂得多，超出我们研究的范围，除非数值计算的专家，否则不要实现这种算法，直接用库

代码，例子，优化一个二元二次函数，代码写出它的偏导，利用库函数求出最优解

6.7 多元分类：一对多

逻辑回归解决多类别分类问题，介绍“一对多”的分类算法

Multiclass classification

Email foldering/tagging: Work, Friends, Family, Hobby（自动地将邮件归类到不同的文件夹里），所以这是个包含四个分类的问题

用数字表示，分别用y=1,y=2,y=3,y=4来代表；

天气分类，病情分类

其中6.1到6.3节讲过2分类问题；那么多分类问题的数据集是下图这样：

3种不同的符号代表3个类别；如何针对这种数据集得到一个学习算法来进行分类呢？我们已知可以用逻辑回归解决二分类问题，利用直线将数据集分为正负类，是否可以利用一对多的思想？

一对多（一对余）分类的原理

将上图3分类问题，转化为3个独立的二元分类问题；

以三角形为例，创建新的“伪”训练集，其中类别2类别3设定为负类，类别1设定为正类，创建一个新的数据集，拟合一个分类器，称其为$h_\theta^{(1)}(x)$，上标1表示类别1，对三角形类别1进行这样的处理，来训练一个标准的逻辑回归分类器；得到一个判定边界；

同理，以正方体拟合第二个逻辑回归分类器$h_\theta^{(2)}(x)$；以叉拟合第三个逻辑回归分类器$h_\theta^{(3)}(x)$；

拟合出：$h_\theta^{(i)}(x)=P(y=i|x;\theta)\quad (i=1,2,3)$

One-vs-all

Train a logistic regression classifer $h_\theta^{(i)}(x)$ for each class i to predict the probability that y=i.

On a new input x, to make a prediction, pick the class i that maximizes $\underbrace{max}_i h_\theta^{(i)}(x)$，3个分类器运行输入x，然后选择h最大的类别，也就是要选择分类器，选择出3个中，

可信度最高，效果最好的那个分类器，无论i值是多少，都能得到一个最高的概率值，

预测y就是那个值。

7.1 过拟合问题

已经介绍几种不同的学习算法，线性回归和逻辑回归

解释过拟合，讨论正则化的技术，可改善过拟合问题

欠拟合：算法具有高偏差；上下波动，过度拟合，具有高方差；如果拟合一个高阶多项式，那么这个假设函数，能拟合几乎所有的数据，这就面临可能的函数太过庞大，变量太多的问题，没有足够的数据来约束它，来获得一个好的假设函数，这就是过渡拟合；

间于欠拟合和过拟合之间的情况叫：“刚好合适”。

过度拟合的问题将会在变量过多的时候出现。这时训练出的假设能很好地拟合训练集，代价函数可能非常接近于0，但会得到过拟合的曲线，无法泛化到新的样本中，无法预测新样本的价格；这里“泛化”指的是一个假设模型应用到新样本的能力。

线性回归过拟合的例子；类似的应用到逻辑回归；

逻辑回归的例子

从左到右，加入更多高阶项，逻辑回归变得扭曲，千方百计找出一条曲线拟合数据；

调试和诊断；导致学习算法出错的问题时，用工具识别过拟合和欠拟合的情况；

过拟合问题发生时如何解决？当使用一维或二维数据时，可以通过汇出假设模型的图像，来研究问题，再选择合适的多项式阶数，以之前的房屋价格为例，绘制假设模型图像；

可以看出来绘制的曲线非常扭曲，来选择合适的多项式阶次，绘制假设模型曲线；

多个特征变量时，绘图变得更难，通过数据的可视化，来决定保留哪些特征变量也更难；

具体如果要预测房价，可能会有很多特征变量有关，如果有过多变量，而只有很少的训练数据，就会出现过拟合的问题；

为了解决过拟合问题，有两个办法解决，

1. 尽量减少选取变量的数量，可以人工检查变量清单，并以此决定哪些变量更为重要，哪些特征变量应该保留，哪些应该舍弃；模拟选择算法，这种算法可以自动选择，有效减少过拟合的发生；缺点：舍弃一部分特征变量，也就是舍弃了关于问题的一些信息，
2. 正则化：保留所有特征变量，但是减少量级，或参数$\theta_j$的大小；其中每一个变量都能对预测的y值产生一点影响，

7.2 代价函数

高阶函数（$\theta_0+\theta_1x+\theta_2x^2+\theta_3x^3+\theta_4x^4$）过拟合，泛化不好，不妨在函数中加入惩罚项，使得参数$\theta_3$和$\theta_4$都非常小

优化问题：$\underbrace{min}_\theta\frac{1}{2m}\sum_{i=1}^m[h_\theta(x^{(i)})-y^{(i)}]^2$

最小化其均方误差代价函数，修改，变为：

优化问题：$\underbrace{min}_\theta\frac{1}{2m}\sum_{i=1}^m[h_\theta(x^{(i)})-y^{(i)}]^2+1000*\theta_3^2+1000*\theta_4^2$

1000只是随便一个比较大的数，要使这个函数最可能小，就是$\theta_3$和$\theta_4$要尽可能小，因为他们的系数很大，会使得整个函数变得很大，

尽量使$\theta_3$和$\theta_4$尽量接近于0，函数还是相当于2次函数，因为2次函数是一种更好地假设模型，这就是正则化背后的思想，简化假设模型，

参数值越小，得到函数越平滑，更不易出现过拟合问题，

例子：100个特征值，并不知道$\theta_3,\theta_4$是高阶项，就是不知道哪些变量的相关度较低，因此正则化中，就是对代价函数，修改它来缩小所有的参数，因为不知道该修改谁，所以在后面添加新的项，加一个额外的正则化项，来缩小每个参数的值，

正则化的优化目标：$J(\theta)=\frac{1}{2m}[\sum_{i=1}^m[h_\theta(x^{(i)})-y^{(i)}]^2+\lambda\sum_{j=1}^n\theta_j^2]\quad \lambda$是正则化参数，作用是控制两个不同目标之间的取舍

第一个目标与目标函数的第一项有关，更好拟合训练集；第二个目标就是要保持参数尽可能地小，与目标函数第二项有关，与正则化目标有关，与正则化项有关；$\lambda$控制两个目标间的平衡关系，即更好地去拟合训练集的目标，和将参数控制得更小的目标，从而保持假设模型的相对简单，避免出现过拟合的情况。

例如100个参数，都想保留去，其中有高阶项，可以利用加入正则项，也可以得到平滑曲线，但这个曲线并不是一个二次函数，

其中$\lambda$设置过大，就会对参数有太大的惩罚程度，就会降低为一次函数，甚至常函数，就会欠拟合，偏见性太低，偏差过高，合适地选择正则化参数$\lambda$；后面会有方法自动选择这个参数，

7.3 线性回归的正则化

对于线性回归，之前推导了两种算法，一种基于梯度下降，另一种基于正规方程，

这节将两种算法推广到正则化线性回归中去，

之前使用梯度下降法，在没有正则化项的情况下，去最小化最初的代价函数，进行常规的线性回归，

Repeat {

​ $\theta_0:=\theta_0-\alpha\frac 1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}$，其中$\frac 1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}$是$J(\theta)$对$\theta_0$的偏导数

​ $\theta_j:=\theta_j-\alpha\frac 1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$，其中$\frac 1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$是$\frac{\partial}{\partial\theta_j}J(\theta)$

}

正则化项时，没有惩罚$\theta_0$，正则化线性回归在处理$\theta_0$的时候，会将它区别对待，用正则化项修改这个算法，将上式修改为

$$\theta_j:=\theta_j-\alpha[\frac 1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}+\frac \lambda m\theta_j]$$

就可以对正则化代价函数$J(\theta)$用梯度下降法进行最小化。

化简：$\theta_j:=\theta_j(1-\alpha\frac \lambda m)-\alpha\frac 1m\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$，通常学习率$\alpha$很小，但$m$很大。就是$\theta_j:=\theta_j*0.9999...$，就是$\theta_j$的平方范数变小了，

正则化线性回归时，都是将$\theta_j$乘以一个非常小的数，把参数缩小一些，然后减去剩余的项，

第二种方法，用正规方程来解决，建立一个设计矩阵X，每一行代表一个单独的训练样本，然后建立一个向量y，m维向量，包含了训练集中所有标签，X是一个$m*(n+1)$维的矩阵，

最小化代价函数的方法：

Non-invertibility(optional/advance).

Suppose $m(\#eamples)\le n(\#features)$，样本总数m小于等于特征的数量n

​ $\theta=(X^TX)^{-1}X^Ty$

If $\lambda\gt0$, $\theta=(X^TX+\lambda\begin{bmatrix}0&&&&\\&1&&&\\&&1&&\\&&&...&\\&&&&1\end{bmatrix})^{-1}X^Ty$

这个计算出来的$\theta$，可以使代价函数$J(\theta)$最小化，此时的代价函数是没有正则化项的，

现用正则化来得到想要的最小值，将对各个参数的偏导数设为0，然后进行一些数学推导，

这个矩阵是$(n+1)*(n+1)$维矩阵，不可逆问题？

如果样本数量比特征数量少，那么这个X转置乘X的矩阵是不可逆的，奇异矩阵，矩阵退化，伪逆矩阵，模型不好，

只要$\lambda$严格大于0，$X^TX+[]$一定不是奇异矩阵，因此进行正则化可以解决一些X的转置乘X不可逆的问题，

7.4 Logistic回归的正则化

8.1 非线性假设

8.2 神经元与大脑

8.3 模型展示Ι

8.4 模型展示Ⅱ

8.5 例子与直觉理解Ι

8.6 例子与直觉理解Ⅱ

8.7 多元分类