[数据结构与算法]线性回归（Linear Regression）和逻辑回归（Logistic Regression）

先举两个简单的例子，看上面的图片，可以说两种回归都是求曲线方程。

线性回归的曲线用于拟合数据。
逻辑回归的曲线用于区分数据，也就是找数据集合的边界。（它的方程也不一定是曲线，总之能够把数据区分开）

线性回归的代价函数常用平方误差函数。
逻辑回归的代价函数常用交叉熵。

参数优化（回归）的方法都是常用梯度下降。

1 线性回归（Linear Regression）

1.1 建立问题

举个例子，你有一组面积&房价的数据。

现在你有个朋友想要卖房子，他的房子是1250平方英尺，大概能卖多少钱？

我们可以根据这组数据，建立一个模型，然后用这组数据集去拟合模型。拟合完毕后，输入1250，它就会告诉你朋友能卖多少钱。

看起来这组数据似乎分布在一条直线附近：

好，只要找到这条直线的方程，你就能根据面积来预测房价了。（在这个例子里，直线方程就是我们要拟合的模型）

如何找到直线方程？方法就是，线性回归。

补充讲一下，这是一个属于监督学习（Supervised Learning）的问题：每个例子都有一个 “正确答案”，我们知道每一个面积对对应一个确定的房价。

而且这还是一个回归问题（Regression Problem）。回归问题指的是，我们预测一个具体的数值输出，也就是房价。

另外再讲一下，监督学习中还有一种被称为分类问题（Classification Problem），我们用它来预测离散值输出。比如观察肿瘤的大小，来判断是良性还是恶性的，输出只有2种：[0]良性，[1]恶性。

然后，这是你的数据集：

1.2 建立模型

现在有一个假设函数 $h$，它的英文名叫 hypothesis。至于为什么叫 hypothesis，这是一个历史问题，反正机器学习里面都这样叫的。

我们要做的是，通过训练集+机器学习算法，学习到这个函数，即 $y=h(x)$。并且输入和输出的值满足上面的数据集表格。

函数 $h$ 应该长什么样子？在这个例子里它是这样的：$$h_{\mathbf{\theta }}(x)={\theta }_0+{\theta }_{1}x\text{\hspace{1em}(1)}$$下标 $\mathbf{\theta }$ 的意思是，函数 $h$ 的参数是 $\mathbf{\theta }$（在这个例子里 $\mathbf{\theta }$ 包括 ${\theta }_0$ 和 ${\theta }_1$，是两个常数）。

显而易见它是一个直线方程：

有时候 $\mathbf{\theta }$ 不止 2 个，例如 $h_{\mathbf{\theta }}(x)={\theta }_0+{\theta }_{1}x+{\theta }_2{x}^2+{\theta }_3{x}^3...$ 但是在这个例子里不需要这么复杂的函数。

它是一条简单的直线，不包含非线性项（$x$的平方、$x$的三次方之类的）。（所以也叫线性回归？）
而且只有一个输入变量 $x$，又叫做单变量线性回归。

现在数据也有了，模型也有了，我们要做的事情就是利用已知数据找到这两个参数： ${\theta }_0$ 和 ${\theta }_1$。

1.3 代价函数

我们知道，选择不同的 ${\theta }_0$ 和 ${\theta }_1$ 的组合，会得到不同的直线：

这几条直线都不是我们想要的，我们要找的直线应该像这样：

假设每个数据点到直线的距离为 $d_i$，把所有距离加起来： $\sum d_i$ 。

调整直线，重新计算 $\sum d_i$，当直线处于某个位置时，算到的 $\sum d_i$ 最小，这条直线就对了。

假设有 $i$ 个样本，每个样本用 $(x^i,y^i)$ 表示。则：$$d_i={\left(h_{\mathbf{\theta }}\left(x^i\right)?y^i\right)}^2$$
之所以取平方，是因为我们要的距离应该是正数，而直接相减可能有正有负。
（取绝对值也可以，不过取平方方便后面计算。）
（这看起来很像最小二乘法）

把所有样本加起来：$$\sum _{i=1}^m{d}_i=\sum _{i=1}^m{\left(h_{\mathbf{\theta }}\left(x^i\right)?y^i\right)}^2$$其中 $m$ 表示我们有 $m$ 个样本。

所以我们的任务是：找到一组合适的 ${\theta }_0$ 和 ${\theta }_1$ ，使上面求和的结果最小。

再改变一下写法：$$J({\theta }_0,{\theta }_1)=\frac{1}{2m}\sum _{i=1}^m{\left(h_{\mathbf{\theta }}\left(x^i\right)?y^i\right)}^2\text{\hspace{1em}(2)}$$

意思也是一样，要找一组 ${\theta }_0$ 和 ${\theta }_1$ ，使 $J({\theta }_0,{\theta }_1)$ 最小。这就是我们的代价函数（Cost Function）。
它也叫平方误差函数（Squared Error Function）。

对于大多数问题，特别是回归问题，这个平方误差函数都是一个合理的选择。
还有其它代价函数也能发挥很好的作用，但是平方误差函数可能是解决线性回归问题的最常用手段了。

记住现在 $h_{\mathbf{\theta }}(x)$ 的表达式是 $h_{\mathbf{\theta }}(x)={\theta }_0+{\theta }_{1}x$。

我们要求的东西是 ${\theta }_0$ 和 ${\theta }_1$。

代价函数 $J({\theta }_0,{\theta }_1)$ 的参数也是 ${\theta }_0$ 和 ${\theta }_1$。

$(x^i,y^i)$ 是已有的数据集，都是已知数，是用来代进去求 $J$ 的。

1.4 梯度下降

随着 ${\theta }_0$ 和 ${\theta }_1$ 取值的不同，算出来的 $J({\theta }_0,{\theta }_1)$ 也不同，用图画出来大概像这样：

初始的时候，给 ${\theta }_0$ 和 ${\theta }_1$ 随便设一个值。然后把数据集 $(x^i,y^i)$ 都代进去算此时对应的 $J$。
（你大概率不会一下子就出现在谷底，运气这么好可以买彩票了）
然后我们要根据现在所处的位置，不断地改变 ${\theta }_0$ 和 ${\theta }_1$ 的值，使 $J({\theta }_0,{\theta }_1)$ 越来越小。

用梯度下降法可以找到这个方向，直奔谷底。。。

具体是，对 $J$ 求导，导数的方向就指向谷底，用导数更新 ${\theta }_0$ 和 ${\theta }_1$ 的值，我们就向谷底迈进了一步。

$$\begin{gathered} {{\theta }_0}^{\prime }={\theta }_0?\alpha \frac{?}{?{\theta }_0}J({\theta }_0,{\theta }_1) \\ {{\theta }_1}^{\prime }={\theta }_1?\alpha \frac{?}{?{\theta }_1}J({\theta }_0,{\theta }_1) \end{gathered}$$

其中 $\alpha$ 是学习率，决定了你的步伐。

更新 ${\theta }_0$ 和 ${\theta }_1$ ，继续迭代：
$$\begin{gathered} {\theta }_0={{\theta }_0}^{\prime } \\ {\theta }_1={{\theta }_1}^{\prime } \end{gathered}$$

重复上面两组方程，直到 $J$ 的导数为 $0$ ，此时 $J$ 就取到最小值。

若 $\alpha$ 取得太小，则前进步伐太小，收敛太慢。
若 $\alpha$ 取得太大，则容易跨过谷底，甚至迈向山峰，导致 $J$ 一直震荡，无法收敛。

为什么求导有这个功效？因为导数的物理意义是这个曲面当前位置切线的斜率，它指明了这个斜坡的方向。
你或许还记得斜率是$\frac{\Delta y}{\Delta x}$

从切面看，我们的山谷像下面这张图。不管在山谷的哪边，减去一个导数都能让你像谷底迈进一步。

但是梯度下降不是万能的，遇到这种形状的函数可能会陷入局部最优：

它有两个谷底，你从不同的地方开始走（选择不同的初值），会走到不同的山谷，深陷其中，无法翻身。。。
复杂的函数甚至有多个谷底，完全无法知道哪个是最低的。

不过请放心，这个线性回归用的平方误差函数是个凸函数（convex），它只有一个谷底，梯度下降法能很好地工作。

1.5 小结

总结一下，线性回归可以说是一个拟合直线的问题（非线性回归就是拟合曲线？）。
做法是：
$?$?首先选择一个模型（方程），它最符合你的数据集的分布，你需要找到它的参数。在这个例子里是一条直线。
$?$?然后选择一个代价函数，一般是用平方误差函数。它能反映你的数据集和你的模型（方程）之间的整体偏差。
$?$?然后选择一个优化算法，一般是用梯度下降法，把数据集代进去，更新模型（方程）的参数，使代价函数越来越小。
$?$?代价函数变得最小的时候，优化完毕，找到了这个模型（方程）的最佳参数。

2 逻辑回归（Logistic Regression）

虽然它的名字里面也有 “回归” 两个字，但是它解决的是一个分类问题，处理的是 “预测值为一个离散变量” 的情况下的分类问题。

为什么叫逻辑回归，大概是因为它的代价函数里面有一个逻辑函数。

待更新。。。