Andrew NG Coursera教程学习笔记-Week1

Introduction

什么是Machine Learning

Andrew给出了几种定义如下：
Arthur Samuel给了一个较老的定义：

He defined machine learning as the field of study that gives computers the ability to learn without being explicitly programmed.

also Tom Mitchell 给了一个较新的定义

He says, a computer program is said to learn from experience E, with respect to some task T, and some performance measure P, if its performance on T as measured by P improves with experience E.

这里机器学习就是指一个计算机程序可以通过学习经验E，然后去执行任务T，并通过表现P来判定学得好坏，最后这个程序可以不断的进化改进P来执行T通过学习E

有哪些类型的机器学习

总体上来说，机器学习分为以下两种：

• 监督式机器学习（supervised machine learning）: 即我们需要一个数据集，并且在这个数据集中含有正确的答案。比如课堂上举例关于房价的预测模型，其训练集中必须含有房价这个正确的答案。
• 无监督机器学习（unsupervised machine learning）: 在下一节讲到了无监督学习，无监督学习一般不会有明确的分类标签，只是告诉模型我这里有一些数据，你看看能分成几类，可以怎么分类。（常见的聚类算法就是用于无监督学习）

机器学习要解决的问题，可以分为两种类型：

• 回归问题：输出结果是一个连续值，比如预测房价
• 分类问题：输出结果非连续，比如预测是和否之类的问题。

此小节还提到一个问题，即现实工程中，我们可能有无穷多的属性，而这些属性可以通过数学技巧来解决其存储问题。不过并没有细讲。

这里我的问题是真的需要无穷多的属性吗？通过有限的属性，比如几千个属性值不可以吗？

无监督学习

Andrew给出了什么是无监督学习的定义，无监督学习首先是没有所谓的正确答案的，它只是有一堆数据，输入给这些无监督学习的算法，然后让算法将这些数据分类。Andrew还给出了几个例子，比如Google News就是通过将网上的新闻通过无监督学习算法进行自动分类，从而可以使得相同story的新闻聚合。还比如有一堆用户的数据，可以让聚合算法自动聚类，将客户分类（这里我感觉可以用于推荐，聚合不同类型的客户，然后推荐此类客户近期购买过的其它类型的产品）；另外还有一种是非聚类算法(non-clustering algorithm)

最后，Andrew还推荐了Octave，因为使用Octave或者Matlab可以快速实验原型，可以快速的几行代码就写出算法的原型。这里还涉及到了一个概念叫奇异值分解(singular value decomposition)，就是课程讲的鸡尾酒算法的数学表达吧？

• clustering: 算法自动分类，但我们事先并不知道分的什么类型，也就是我们不知道分类的标签是什么
• non-clustering: 比如将不同声源的声音分离

Model and Cost Function

Model Representation

针对训练集的数据，用如下符号来标记一些东西：
m: 训练集的样本数
x: 输入，variables/features x(i)表示第i行的输入
y: 输出的结果，所谓right answer y(i) 表示第i个样本的输出
(x, y)来表示一个样本
h: 算法函数 hypothesis. h maps from x to y. 就是一个映射函数，可以通过给定的X输出Y

# ɵ refers to theta
# 实际就是一个一元线性函数
h(x) = ɵ0 + ɵ1x

我们通常把这种线性函数叫做linear regression with one variable 或者 univariate linear regression

本质上，所有机器学习算法其实都是一个映射函数，通过训练，找到合适的参数，从而可以实现这样一种映射，即给定一组输入值，可以输出一个值，而这个输出值就是我们的预测值

cost function

如下公式就是一个cost function，实际是一个类平方差的公式，关于平方差请参考文章《统计基础一》，但是平方差的计算并不会除2，这里之所以乘以1/2，是为了后续做梯度下降(gradient descent)方便

cost function

这个cost function最终是要测度h(x)与y之间的距离，我们也叫这个cost function为square error function. square error function对于线性回归问题是非常通用的cost function，当然还有一些其它的cost function，但是square error function更常用。

Cost Function Intuition1

为了简化问题，先假设ɵ0 = 0，J(ɵ0, ɵ1) -> J(ɵ1)
h(x)是关于x的函数；而J(ɵ1)是关于ɵ1的函数，即这个函数的横坐标是ɵ1。
课程假定有三个样本(1, 1), (2, 2), (3, 3),这时，如果ɵ1=1，那么h(x) = x，根据J(ɵ1)的公式，可以计算如下
J(ɵ1) = (1/2*3) * ( (1-1)**2 + (2-2)**2 + (3-3)**2) = 0
假设ɵ1= 2，计算如下：
J(ɵ1) = (1/6) * ((2-1)**2 + (4-2)**2 + (6- 3)**2) = (1/6) * 14 ≈ 2.33
以此类推，最终的J(ɵ)函数的图形如下：

J(ɵ)

我们知道这个平方差函数是用来测度h(x)的预测值和实际样本的y的距离，因此距离越小说明我们选取的参数越准确，因此，我们的目标是寻找J(ɵ)的最小值，这个时候的ɵ值就可以产生最优的h(x)算法。
实际运用时，我们可以通过程序自动寻找这个最小值。

Cost Function Intuition2

这一小节主要讲了当ɵ0 != 0时的情况，这时cost function就成了J(ɵ0, ɵ1)，由于有两个variables，因此其函数表示就成了三维的图像，如下：

J(ɵ0, ɵ1)

这里有个问题，为啥不把ɵ0， ɵ1的0点放在一起？是为了展示的图形更直观？

但通常我们使用contour plot来表示J(ɵ0, ɵ1)，这个contour plot实际是上边那个3-D的平面投影，同一个等高线对应相同的函数值。contour plot如下图：

contour plot

从这个图可以看出中心点那个值是J(ɵ0, ɵ1)的最小值，也就是说这个时候的h(x)最接近实际情况。

Parameter Learning

Gradient Decent

我们在寻找特定的θ0和θ1并使得J(θ0, θ1)可以获得最小值时，我们就需要gradient decent function(梯度下降函数）。首先来直观看下如何寻找θ0, θ1使得J(θ0, θ1)最小：

gradient decent
这个过程非常像我们站在山上往山下走，一直走到最低处。但是这里可能存在这样的情况：即当我们的初始点不同时，可能最后下降到不同的低点（这里可以看Andrew的视频，讲得非常清楚），所以我们说局部最小值 (local minimum value)。

这里有个问题，就是有没有数学方法可以找到全局最小值呢？

走的过程是分步走的，每走一步都会停下来看看往哪个方向走可以下降得更快，然后再往那个方向走下一步。我们是通过导数(derivative)来判断方向的，导数就是函数曲线在某一个点的切线的斜率(The slope of the tangent is the derivative at that point)，我们就是根据这个斜率来判断哪个方向可以最陡下降(steepest descent)。
先来看看梯度下降的公式

gradient decent term

这个公式中的𝑎就是所谓的learning rate，它来决定步子迈多大。
梯度下降的过程就是不断迭代梯度下降的公式，直到收敛(convergence), 即达到最低点。这里需要注意的是，每次迭代，θ0和θ1必须同时计算，如下图所示：

θ update

Gradient Descent Intuition

gradient decent

从图中我们可以看到上方的图表明，其导数为正时，θ会减一个正数（这个数的大小显然跟𝑎有关），因此θ值会向左移动，因此向local minimum value收敛。下边的图类似，只是θ会向右移动收敛。

gradient decent2

上边的坐标图表明当𝑎很小时，收敛的非常慢，因为迈的步子小啊
下边的坐标图说明当𝑎很大时，会导致收敛失败，因为会导致离最小值点越来越远
所以，当收敛时间非常长或者收敛失败时，说明我们的𝑎设置的不合适。

gradient decent

这幅图说明了当我们采用一个固定的𝑎时，收敛的step也会越来越小(因为斜率越来越小)，直到最终收敛，所以最终我们是可以收敛成功的。

Gradient Descent For Linear Regression

要进行梯度下降，就需要迭代地计算θ0和θ1，根据前面的课程我们知道需要知道J(θ)导数才能计算，这个涉及到微积分的知识，暂且不表，先看下求导后的公式：

gradient decent equation

注意：θ1与θ0是不同的，这是求导后的结果
求导的过程如下：

derivation

梯度下降的过程就是寻找J(θ)最小值的过程，针对线性回归这种特殊情况，J(θ)实际上是一个二次的凸函数(convex quadratic function)，因此只有一个最小值，即我们找到的这个局部最小值一定是全局最小值。

另外，还涉及到一个概念叫batch gradient decent, 这是由于我们每次迭代的时候，都需要针对所有的样本进行计算再求和，因此我们说是batch。Andrew还提到了某些其它的方式可以不用全部的样本进行计算，每次只需要样本的一个子集即可，后续课程再讲。

另外，线性代数还有一个叫做normal equations的方法可以不需要迭代的方法来找到最小值，这个也是以后会涉及到。

Linear Algebra Review

Matrices and Vectors

矩阵请参考线性代数之矩阵
向量vector即n x 1的矩阵，即只有一个column的矩阵。
向量通常使用小写字母表示，而matrix通常使用大写字母表示
在表示向量的元素的时候，其下标可以从0开始，也可以从1开始，从0开始就是0-indexed vector，而从1开始就是1-indexed vector。
另外，

"Scalar" means that an object is a single value, not a vector or matrix.
ℝ refers to the set of scalar real numbers.
ℝ𝕟 refers to the set of n-dimensional vectors of real numbers.

Addition and Scalar Multiplication

本节相对简单，主要是矩阵加减运算以及标量与矩阵相乘。不再赘述
需要注意的是，在矩阵的加减运算时，两个矩阵必须是相同的维数。

Matrix Vector Multiplication

本节主要讲了Matrix和Vector的乘

矩阵与向量的乘本质上就是对多元方程式的计算，可以想象矩阵的每一行都是一个样例的特征（每个特征值都是对应一个变量值x, y, z...)，而向量就是方程的θ0, θ1, ....θn，通过相乘，实际上就可以计算出对应的h(x)结果。需要注意的是，在构筑的时候，常数项也需要构筑一列，即把变量当做1

假设我们有房价的尺寸数据[123; 234; 555; 666]， h(x) = 40 + 2x
那么我们在使用矩阵计算时，需要构筑如下矩阵

A = [1, 123; 1, 234; 1, 555; 1, 666]
v = [40; 2]
h(x) = A * v

通过这种方式不仅代码会变得简单，而且计算时会更加有效率

另外，矩阵的乘是有顺序的，且前一个矩阵的column必须与后一个矩阵的row相等。
比如一个3 x 2矩阵只能跟一个2 x n矩阵相乘，结果为3 x n矩阵
最后关于矩阵的乘，可以参考线性代数之矩阵

Matrix-Matrix Multiplication

矩阵乘有的时候是比较绕的，我觉得Andrew讲解的非常好，基本上我们需要把第二个矩阵分解成向量，然后用第一个矩阵分别于这些向量相乘，得到一个新的向量，最终再把所有的结果向量组合在一起就是最终结果。
矩阵和矩阵乘主要用于有多个假设h(x)的时候，这个时候第二个矩阵的每个向量都对应一个假设。
这块看Andrew的视频会非常清楚，不再赘述，需要注意的是
矩阵是有顺序的，而且第一个矩阵的列数必须与第二个矩阵的行数相等
A x B， 如果A为m, n矩阵， 那么B就必须为n，x矩阵，结果是m， x矩阵

Matrix Multiplication Properties

此小节主要介绍了矩阵乘法的几个属性：

• 非community属性：community属性指乘号两边的变量可以交换顺序，即ab = ba，但是对于矩阵而言，通常是非community的，即AB != BA
• associative属性：指当有多个乘数的时候，先计算前边的乘和先计算后边的乘是一样的，即a * b * c = a * (b * c) = (a * b) * c，而矩阵是associative的，即A * (B * C) = (A * B) * C
  之后Andrew引入了单位矩阵的概念(identity matrix)，单位矩阵与方形矩阵相乘的时候是community的，即I * A = A * I，关于单位矩阵，可以参考线性代数之矩阵

Inverse and Transpose

此小节主要讲了什么是逆矩阵(inverse matrix), 以及什么是转置矩阵(transpose of matrix)。
逆矩阵的计算比较复杂，涉及到行列式和余子式的概念，Andrew没有在课程上讲，可以参考线性代数之矩阵以及线性代数之逆矩阵。Andrew演示了通过octave来自动计算逆矩阵的方式。需要注意的是，并不是所有的square matrix都有逆矩阵，如果矩阵是奇异的singular或者退化的degenerate时，是没有逆矩阵的。

矩阵的转置，简单来说就是把行转为列，如下：

matrix
transpose

即一个m x n matrix转置后变为n x m matrix，且满足

transpose