Week 1

引言

什么是机器学习？

Tom Mitchell provides a modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.”
Example:
过滤垃圾邮件，电子邮件系统会根据用户对电子邮件的标记(是/不是垃圾邮件)不断学习，从而提升过滤垃圾邮件的准确率，定义中的三个字母分别代表：
- T: 过滤垃圾邮件
- P: 电子邮件系统过滤垃圾邮件的准确率
- E: 用户对电子邮件的标记

目前，机器学习的算法主要分为监督学习和无监督学习两种。

监督学习(Supervised Learning)

In supervised learning, we are given a data set and already know what our correct output should look like, having the idea that there is a relationship between the input and the output.

监督学习: 教计算机如何去完成预测任务（有反馈），预先给一定数据量的输入和对应的结果即训练集，建模拟合，最后让计算机预测未知数据的结果

监督学习被分为“回归(regression)”和“分类(classification)”两类

回归(regression): 预测一系列的连续值

Example: 房屋价格预测
提供面积，价格数据关系，根据这些数据来预测任意面积的房屋价格。因为价格关于面积的函数是连续的，所以这是一个回归问题。

线性模型与实际数据的拟合度不是特别好。如果采用二次函数进行拟合，拟合度更高。因此，回归问题的模型选取是十分重要的。
分类(classification): 预测一系列的离散值，即根据数据预测对象属于哪个分类

Example: 癌症肿瘤，判断良性，恶性
提供一些乳腺癌关于（肿瘤尺寸，良性/恶性）的真实数据，现在要根据某一肿瘤的尺寸，来判断是否是良性的。在这个例子里，输出是Yes or Not, 是一个分类问题。

无监督学习(Unsupervised Learning)

Unsupervised learning allows us to approach problems with little or no idea what our results should look like. We can derive structure from data where we don’t necessarily know the effect of the variables.

监督学习，使我们能够处理那些对结果了解甚少、甚至根本不了解的问题。我们可以在不知道变量的具体影响的情况下，从数据中提取出结构 (structure)

计算机可能会把特定的数据集归为几个不同的簇，故叫做聚类算法(clustering)

Example 1:新闻聚合
在例如谷歌新闻这样的网站中，每天后台都会收集成千上万的新闻，然后将这些新闻分组成一个个的新闻专题，这样一个又一个聚类，就是应用了无监督学习的结果。

Example 2: 基因测定
在这个例子中，你得到了一系列的个体，用不同颜色标记了它们特定基因序列的拥有程度。现在通过聚类算法，你能把这些个体归入不同的类里。

Example 3: 鸡尾酒问题
在鸡尾酒会上，大家说话声音彼此重叠，几乎很难分辨出面前的人说了什么。我们很难对于这个问题进行数据标注，而这里的通过机器学习的无监督学习算法，就可以将说话者的声音同背景音乐分离出来

编程语言建议

看起来，鸡尾酒会问题算法的实现不是一个简单的事情。但是在Octave编程环境（免费的开源软件）下，问题可以用一行代码解决： [W,s,v] = svd((repmat(sum(x.*x,1),size(x,1),1).*x)*x');

在机器学习刚开始时，推荐使用 Octave 类的工程计算编程软件，因为在 C++ 或 Java 等编程语言中，编写对应的代码需要用到复杂的库以及要写大量的冗余代码，比较耗费时间，建议可以在学习过后再考虑使用其他语言来构建系统。另外，在做原型搭建的时候也应该先考虑使用类似于 Octave 这种便于计算的编程软件，当其已经可以工作后，才将模型移植到其他的高级编程语言中。

模型和代价函数(Model and cost function)

模型描述(Model Represent)

首先，我们定义三个变量：

$m$=用于训练的样本数
$x^i$=第i个训练样本“输入”变量/特征量
$y^i$=第i个训练样本“输出”变量/特征量

以及一个函数：

$h_{\theta}=\theta_{0}+\theta_{1} x$

其中$h$称为假设(hypothesis) 。假设函数根据输入，给出预测结果输出,即是一个的映射。

代价函数(cost function)

一般而言，我们通过调整θ，使得所有训练集数据与其拟合数据的差的平方和更小，即认为得到了拟合度更好的函数。

我们的目的在于求解最接近实际结果的 $h$ 方程，该问题可以表达为求解

$J\left(\theta_{0}, \theta_{1}\right)=\frac{1}{2 m} \sum_{i=1}^{m}\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right)^{2}$

注意，其中的$\frac{1}{2m}$取$2m$而非$m$当系数是为了后面梯度下降算法里，求导后消掉2

讨论到这里，我们的问题就转化成了求解 $minimize J\left(\theta_{0}, \theta_{1}\right)$ 。对于我们研究的单变量线性回归而言，$J$函数关于$θ$的等高线图像大致如下：

当我们找到了这些同心椭圆的中心点时，就找到了J函数的最小值，此时拟合度更好。

梯度下降(Gradient Descent)

在特征量很大的情况下，即便是借用计算机来生成图像，人工的方法也很难读出 $J$ 的最小值，并且大多数情况无法进行可视化，故引入梯度下降(Gradient Descent)方法，让计算机自动找出最小化代价函数时对应的 $\theta$ 值。

思想:

从某一对 $\theta_0,\theta1$ 出发
不断尝试改变 $\theta_0,\theta1$ ，使得$J(\theta_0,\theta1)$ 减小，逐步逼近最小值
改变的策略：每一次改变的方向，取当前位置梯度下降的方向
由于下降的情况只考虑当前参数组合周围的情况，只能确定局部最小值

下图根据不同的起始点，产生了两个不同的局部最小值

线性回归中的梯度下降:

线性回归模型

$h_{\theta}(x)=\theta_{0}+\theta_{1} x$
$J\left(\theta_{0}, \theta_{1}\right)=\frac{1}{2 m} \sum_{i=1}^{m}\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right)^{2}
$

梯度下降算法

repeat until convergence:{

$\theta_{j}:=\theta_{j}-\alpha \frac{\partial}{\partial \theta_{j}} J\left(\theta_{0}, \theta_{1}\right)$

}

$\begin{aligned}
&\alpha: \text { 学习速率(learning rate) }, \alpha>0\\
&\frac{\partial}{\partial \theta_{j}} J\left(\theta_{0}, \theta_{1}\right): J\left(\theta_{0}, \theta_{1}\right)\text{的偏导}
\end{aligned}$

学习速率决定了参数值变化的速率即”走多少距离“，而偏导这部分决定了下降的方向即”下一步往哪里“走。