决策树

基本流程

决策树基于树结构进行决策，每个内部节点对应某个属性上的“测试”（test），每个分支对应于该测试的一种可能结果，每个叶结点对应于一个预测结果。

学习过程：通过对训练样本的分析来确定“划分属性”；

预测过程：将测试实例从根节点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶子结点。

基本流程：分治：从上往下递归，在每个中间节点找到“划分”属性

停止条件：

• 当前节点包含的样本全部属于同一类别，无需划分；
• 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分：我们把当前结点标记为叶结点，其类别设定为该结点所含样本最多的类别；
• 当前节点包含的样本集合为空，不能划分：我们把当前结点标记为叶结点，其类别设定为其父节点所含样本最多的类别。

注意，第二类和第三类处理实质不同：第二类是利用当前结点的后验分布，第三类是把父节点的样本分布作为当前结点的先验分布。

Linear Regression

Model representation

线性回归的预测方程可以写为

$$h_\theta(x) = \sum_{i=0}^n\theta_ix_i$$

其中规定 $x_0 = 1$。

若令

$$\boldsymbol{\theta} = \begin{bmatrix}\theta_0 \\ \theta_1 \\ \vdots \\ \theta_n\end{bmatrix} \in \mathbb R^{n+1}, \boldsymbol{X} = \begin{bmatrix}x_0 \\ x_1 \\ \vdots \\ x_n\end{bmatrix} \in \mathbb R^{n+1}$$

则预测方程可以写为

$$h_\theta(x) = \boldsymbol{\theta}^\mathrm T\boldsymbol{X}$$

Cost function

Regularization

The problem of overfitting

过拟合（overfitting）指的是当有多个特征时，预测函数的代价可能会很低，但对于新的预测数据全都错误的情况，这会导致模型的泛化能力较差。

左侧的称为欠拟合（underfitting），右侧的称为过拟合。

当特征过多而数据过少时，就有可能出现过拟合的情况。

当过拟合的情况发生时，该如何解决呢？

1. 减少特征的数量，我们可以选择重要的特征进行保留，也可以使用模型选择算法，这种算法可以自动选择保留哪些特征和选择哪些特征，但是删去某些特征会导致一些信息的丢失，有可能这些信息都是我们需要的；
2. 保留所有的特征，进行正则化。我们通过正则化将参数 $\theta_j$ 的量级或数量减小，这在我们有很多特征的时候非常有效，由于每个特征都会对结果产生贡献，所以这种方法是行之有效的。

Cost Function

假设此时我们的模型为 $\theta_0 + \theta_1x + \theta_2x^2 + \theta_3x^3 + \theta_4x^4$，我们考虑加入惩罚项，使得 $\theta_3$ 和 $\theta_4$ 非常小，即

$$\underset{\boldsymbol{\theta}}{\arg\min}\dfrac 1{2m}\sum\limits_{i = 1}^m{\left(h_\theta(x^{(i)}) - y^{(i)}\right)^2} + 1000 \theta_3^2 + 1000\theta_4^2$$

Logistic Regression

逻辑回归可以用来处理离散标签分类的问题，如二分类、三分类 $\cdots$ $n$ 分类等。

由于在分类时我们不希望得到连续的值，而只得到两类离散值，如 $0$、$1$，我们引入 Sigmoid 函数（也称为 Logistic 函数）：

$$g(x) = \dfrac{1}{1+e^{-x}}$$

可以发现，$g(x) \in (0,1)$，$g(0) = \dfrac 12$，且 $\lim\limits_{x \to -\infty}g(x) = 0$，$\lim\limits_{x\to +\infty}g(x)=1$。

与线性回归类似地，我们定义回归函数为 $F_{\vec w, b}(\vec x) = \vec w \cdot \vec x + b$，与 Sigmoid 函数结合，就得到了逻辑回归模型 $f_{\vec w, b}(\vec x) = g(\vec w \cdot \vec x + b)=g\left(\sum\limits_{i=0}^nw_ix_i+b\right)$。

对于逻辑回归模型，它所做的是输入一个（组）特征 $x$，输出一个 0 到 1 之间的数字。

Interpretation of logistic regression output

我们将 $F_{\vec w, b}(\vec x)$ 的输出看做给定某个输入 $x$ 的分类 $y$ 等于 1 的概率。

Neural Networks

---

Non-linear hypotheses

在特征较少时，对于一个边界较为复杂的数据集中，我们可以使用逻辑回归，通过构造一个多项式来拟合决策边界，但在特征较多时，逻辑回归便显得较为繁杂，我们很难构造一个合适的多项式来较好的拟合其决策边界。

例如，当有 100 个特征时，如果我们只构造一个二次多项式，那么这个多项式最多会有 $\binom{100}{2}$ 个，也就是说，二次项会有 $\mathcal{O}(n^2)$ 个，极易导致过拟合的情况出现，同时也会出现计算量过大的问题。

如果我们继续将多项式的次数提高，那么会有 $\mathcal{O}(n^3)$ 个三次项，$\mathcal{O}(n^4)$ 个四次项……这对我们的模型构造和计算都是不可承受的。

考虑一个计算机视觉中的问题：如何让计算机识别出一辆汽车？人眼对于识别一辆汽车轻而易举，但对于计算机，它得到的可以是一个亮度的矩阵，也可以是一个颜色的矩阵等等。

在训练这样的模型时，我们需要做的是提供两个带标签的数据集，其中一个表示这里面的数据全都是车，另一个表示全都不是车。在分类器训练完成后，如果给定一个汽车的图片并要求它分类，理想状态下分类器可以识别出这是一辆汽车。

具体地，我们假设在每个图片的相同位置取两个像素点，并将其传入分类器中，如下图所示：

对于是汽车的样本和不是汽车的样本，我们可以发现，存在一个非线性的决策边界使得这两类可以被分开：

现在我们考虑每个样本的特征数量，假设每个样本都是一张 $50 \times 50$ 的图片，那么就有 2500 个像素点，特征数量 $n = 2500$，这是在只使用灰度图片的情况下，如果我们使用彩色图片，这个数字将会变为 $2500 \times 3 = 7500$。
此时如果使用逻辑回归的话极大可能会出现过拟合的问题，这就引出了我们的神经网络模型。

---