换元积分

注意积分上下限的变化，关键是 积分上下限与被积变量对应

第一类换元法

$g=g(x)$ ，如果视 $g$ 为被积变量

$$ \inta^bf(g(x)) g’(x) dx = \int{g(a)}^{g(b)} f(g) dg = F(g) \bigg|_{g(a)}^{g(b)} $$

如果仍视 $x$ 为被积变量

$$ \int_a^bf(g(x)) g’(x) dx = \inta^b f(g(x)) dg(x) = F(g(x)) \bigg|{a}^b $$

第二类换元法

$$ \inta^bf(x) dx = \int{x^{-1}(a)}^{x^{-1}(b)} f(x(t)) x’(t) dt = F(t) \bigg|_{x^{-1}(a)}^{x^{-1}(b)} $$

无穷项数列和的极限

可考虑使用定积分的定义：

$$ \inta^b f(x) dx = \lim{n \rightarrow \infty} \frac{b-a}{n} \sum_{i=1}^n f(a+\frac{b-a}{n} i) $$

其关键是猜测出上下限，分离出 $\frac{b-a}{n}$ ，确认 $f(x)$

分段积分

对分段函数，绝对值函数等

变上限积分

注意，求导时被积函数不能包含自变量，同时，注意在积分外部，自变量不是常数。例子：

$$ F’(x) = \left( \int_0^x x f(t) dt \right)’ =\left( x \int_0^x f(t) dt \right)’ = \int_0^x f(t) dt + x f(x)$$

Bootstrapping 是统计学上通过对样本 重采样（re-sampling） 来估计样本分布情况，并将结果作为总体分布的参考。其背后的思想是样本与总体独立同分布，用样本分布估计总体分布似乎合理。重采样方式是，对样本做 有放回的随机抽取 以得到“新样本”。

Bootstrapping 取名自美国俚语 “pull oneself up by one’s bootstraps”，呵呵，用自己的提靴带把自己提起来，现指做事充分利用自身条件，所以被称为自助法，又称提靴法。

Bootstrapping (statistics)——wikipedia) 上有个估计世界上人的身高均值的例子。当然，统计所有人身高是不现实的，所以可以抽取容量为 N 的样本，算出均值。但是，这个值有多可信呢？这需要知道总体的分布情况。这时可以采用 Bootstrapping。通过在样本中做有放回的随机抽样，抽取到容量为 N 的“新样本”，计算其均值。重复该步骤许多次（典型的1000或10000次），得到一系列身高均值数据，也就能估计总体均值的大致分布了，进而计算均值的置信区间。

Bootstrapping 的优势在于对一系列估计量——如相关系数的置信区间——的简单直接的计算方式，引自 Wikipedia ：

A great advantage of bootstrap is its simplicity. It is a straightforward way to derive estimates of standard errors and confidence intervals for complex estimators of complex parameters of the distribution, such as percentile points, proportions, odds ratio, and correlation coefficients.

参考

• Bootstrapping (statistics)——Wikipedia)

机器学习中，”模型验证”用验证数据集对模型做测试。一般用于 模型选择 ，针对多个模型在同一验证数据集的测试表现，选择表现最佳的模型。如果同种模型，有不同参数可选，也可用验证手段选择最佳参数，称为 参数选择。 （其实，同种模型不同参数也可视作不同模型，那么“参数选择”也属于“模型选择”了）

模型测试与验证

两者都对模型进行测试以观察模型的表现，并无本质区别。只是模型测试的目的是估计模型的实际表现。例如，在竞赛中，测试数据往往是参赛者未知的，测试由主办方进行。所以，模型测试一般是在模型确定后进行的。而模型验证的目的一般是模型选择，针对多个候选模型进行测试。验证数据一般是可知的，实际上，一般从训练数据分出一部分做验证（另一部分做训练）。在竞赛中，参赛者可能从得到的训练数据（“已知的”）中分出一部分做验证（剩下的做训练），选出自己的最佳模型。

验证数据

测试（不管是模型测试还是验证）数据应该与训练数据不同 。这样，训练出的模型对测试数据是“未知”的，其测试表现才能更接近于实际情况。反之，如果用训练数据测试模型，其表现与实际情况相差可能是很大的。例如，未经剪枝的 决策树模型 ，即完全树，在训练数据上做分类预测可以做到 0 误差，即完全正确分类，而实际应用时差许多。

Holdout 验证

Holdout 验证是常用的模型验证方法，它随机地从原始的样本数据中抽取一部分（一般小于1/3）留做验证，剩下的作为训练数据。

K-Folder 交叉验证

由于验证数据与训练数据必须分开，Holdout 验证又为了保证训练数据的数量，可能导致其验证数据比较少。交叉验证，即 Cross Validation（CV），避开了上述问题。

k-folder 交叉验证将样本数据分成 k 份。做 k 次训练和验证，每次取其中一份作为验证数据，其余作为训练数据。最后取 k 次验证的平均作为结果。这样，验证数据的数量与原始样本数据量持平，充分利用了原始数据。k 常取 10。

留一验证

留一验证，即 Leave One Out Cross Validation，记为LOOCV ，是 K-Folder 交叉验证中的特殊情况。顾名思义，每次只留下一笔数据做验证，相当于 K-Folder 交叉验证中 k 取原始样本数据量。它把 K-Folder 交叉验证的优势发挥到极致，但相应地计算量相当高。

此文是本人学习林轩田老师教授的机器学习技法第十——Decision Tree——的笔记。

Random Forest 模型概括讲，就是以 Decision Tree 为基础模型，这里选择未经剪枝的完全树，用 Bagging 进行集合训练。完全决策树在训练集上的零误差，对样本选择十分敏感，有较大的 varaince，但有着训练高效等优点。而 Bagging 能够降低模型预测的 varaince 误差，特别适用于对样本敏感的波动比较大的模型。所以，结合两者应该可以取得好效果。

参考

• 机器学习技法
• 课件
• Decision Tree
• Bagging
• 置换检验

增强随机性

在 Random Forest 中，为了进一步降低算法 variance 误差，不仅抽取样本时做到随机抽取，还在选择特征时保证一定的随机性。普遍使用方式是 随机选取子空间。

随机选取子空间（random subspace）

在训练 Decision Tree 的每一个节点时，需要按照某种准则（如基尼值）选取一个特征用于数据划分。未经处理的特征选择数目是所有特征的数目 $M$， 为了增大随机性，随机抽取其中的 $m$ （往往 $M,m$ 差距比较大）个特征供选择。一项数据 $(\mathbf{x}, y)$， 将 $\mathbf{x}$ 视作一个空间向量，每个特征对应一个维度，所以，这个过程可以理解成随机抽取一个子空间用做训练。

随机结合子空间（random combination）

与随机选取子空间不同，随机结合子空间将数据向量 $\mathbf{x}$ 投影到另一个空间成为 $\mathbf{x’}$。 $\mathbf{x’}$ 的每一维都是从原 $\mathbf{x}$ 的 $M$ 维中随机选择 $m$ 维结合（相加）而得。

Out Of Bag 验证

Bagging 采用 Bootstrapping 的方式取样，有些样本没有被抽到不能用作训练数据，称其为 Out Of Bag（简称 OOB） 数据，但它们也可以被利用起来，作为验证使用。

具体做法是，在为每个 Decision Tree 抽取训练数据时就标记那些未被抽取的 OOB 数据，在整个 Random Forest 训练结束后用 OOB 做验证。在用某项 OOB 数据做验证时，该数据可能被一些 Decision Tree 用作训练数据，所以必须排除这些 Decision Tree。

特征选择——置换重要性

特征选择 指从所有特征中选取对结果有影响（有用）的特征，剔除无关特征。Random Forest 能很容易实现这个功能。

如果一个特征 $x_i$ 对结果 $y$ 无影响，那么 $x_i$ 与 $y$ 是否正确对应也就无关紧要。基于这个思想，研究者提出一个通过置换特征计算其重要程度的方法：

$$ importance(i) = E{oob}(G) - E{oob}^{(p)}(G) $$

其中，G 指已经训练完成的 Random Forest 模型， $E{oob}$ 指 OOB 验证误差，未经任何处理，而 $E{oob}^{(p)}$ 指在进行 OOB 验证前，所有 OOB 数据的第 $i$ 个特征（第 $i$ 维数值 $x_i$）相互间进行随机置换（互换）。

这个思想类似 permutation test 置换检验。

树越多越好？

老师指出，理论上讲，树越多，Random Forest 的越强，建议在预测效果不好时，适当增加树的个数。

$$\underset{a}{\arg\min}$$

$$\overline{y}$$

$$ |_{a}^b,\; \big|a^b,\; \bigg|{a}^b $$

$$ y = \left{ \begin{array}{l}
first\
second
\end{array} \right. $$

$$
\begin{bmatrix}
1 & x & x^2 \
1 & y & y^2 \
1 & z & z^2 \
\end{bmatrix}
$$

$$
\left|\begin{array}{}
\mathbf{i} & \mathbf{j} & \mathbf{k} \
a_1 & a_2 & a_3 \
b_1 & b_2 & b_3
\end{array}\right|
$$

$$ A \cap B=\varnothing $$

$$ A \cup B=\Omega $$

$$ \approx $$

$$ \frac{\partial z}{\partial x} $$

$$ \equiv $$

$$ \Leftrightarrow $$

MathJax

markdown语法之如何使用LaTeX语法编写数学公式

此文是本人学习林轩田老师教授的机器学习技法第九课——Decision Tree——的笔记。这节课主要讲解 CART (Classification And Regression Tree) 算法，属于决策树。

参考

• 机器学习技法
• 课件

决策树的基本思想

就举课上的例子好了。要处理的问题是：我回家后是否看学习视频呢？处理这个问题，首先可能想到，我是什么时候回家的呢？那么这个问题分成2种情况。如果回家很早，那么，我是不是有什么约会呢？有约会就不看了，没约会就看。如果回家晚，那么，学习的截止时间是不是快到了呢？快截止了就勉强看下吧，否则就算了。

决策树模型与上述处理问题的过程类似。决策树顾名思义，是一棵树。树的节点是决策器，决策器输入问题，稍做判断，又将问题交给某个合适的下层决策器（下层节点），最终最下层的决策器输出这个问题的处理结果。所以，在处理问题时，问题从决策树的根节点进入，经过一层层的决策，最终输出决策结果。

CART 是决策树中的一种，它是一棵二叉树，可处理分类或回归问题。

CART 训练步骤

CART 模型训练主要分为 2 步，一、生成完全树，二、剪枝。

完全树 是能够将所有训练数据都完全无误地预测的决策树，即在训练集上的误差为 0。实际上，训练数据往往有误差，而完全树做到对训练数据判断的无误差，导致在实际预测时误差较大，有很大的复杂度方面的代价。所以，需要做正则化方面的工作，CART 采用的就是 剪枝 。顾名思义，剪枝会剪去完全树的部分树枝，减小模型的复杂度。

生成完全树

完全树的训练可用递归方式。完全树的节点是“决策器”，实际上是分类器（或回归算法）。决策器将数据大致分类（或用回归预测做大致分类），然后分别交给下层的决策器。

1
2
3
4
5
6
7
8
9

function trainCART：
  - 输入：训练数据集 D
  - 输出：CART 二叉树 Tree
学习决策器 decisionNode，将 D 分为 Dl, Dr;
if Dl 可以再分：
  call trainCART 处理 Dl 得到 treeL;
同上处理 Dr 得到 treeR;
decisionNode 作为根节点，合并 treeL, treeR, 得到二叉树 tree;
return tree;

递归训练终止条件

整个递归的终止条件是“数据是否可再分”，在两种条件下不再分。如果训练数据都相同，即 $\mathbf{x}_n$ 都相同，无法分割；如果训练数据分类都相同，即 $y_n$ 都相同，不用分割。

决策器选择指标与不纯度

学习决策器时，CART 的每个决策器被称为 决策树桩（decision stump） ，每个决策树桩对输入数据进行切割。对于多个候选决策器，CART 的选择标准为：

$$ \underset{decision\; stumps\; hi(\mathbf{x})}{argmin} \frac{|D{i,l}|}{|D|} \cdot impurity(D{i,l}) + \frac{|D{i,r}|}{|D|} \cdot impurity(D_{i,r}) $$

其中，$hi(\mathbf{x})$ 指第 $i$ 个决策树桩模型， $D$ 指训练数据， $D{i,l},\; D_{i,r}$ 分别是 $hi(\mathbf{x})$ 将 $D$ 划分的数据， $\frac{|D{i,l}|}{|D|}$ 计算了 $D_{i,l}$ 数据量在 $D$ 中的占比， impurity 是计算划分数据的 不纯度 函数。一个决策树桩划分的数据的不纯度越小越好。

不纯度指数据中类别的不相同的程度。比如，”被判定为鸭群，有 7 只鸭和 3 只鸡”比“被判定为鸡群，有 9 只鸡和 1 只鸭”更“不纯”，前者不纯度更高。

CART 对于回归与分类的不纯度公式稍有区别。

回归不纯度公式

$$ impurity(D) = \frac{1}{N} \sum_{n=1}^N (y_n - \overline{y})^2 $$

分类不纯度——Gini 指数

$$ impurity(D) = 1-\sum{k=1}^K(\frac{\sum{n=1}^N [y_n=k]}{N})^2 $$

其中， $K$ 是分类的种数，对于二分类， $K=2$； $k$ 表示分类编号； $[y_n=k]$ 是一个布尔判断，如果第 $n$ 个数据是第 $k$ 类，得 1，否则为 0。

剪枝（Pruning）

CART 采用 后剪枝(Post-Pruning)，即在已生成的完全树上进行剪枝。大致流程：

• 分别剪去一个叶子节点，得到多棵决策树
• 计算每棵决策树剪枝“代价”，保留代价最小的决策树
• 重复以上流程，直至剪枝代价高于不剪枝的代价

代价公式可表示为：

$$ cost(G) = E_{in}(G) + \lambda\cdot NumberOfLeaves(G) $$

其中， $G$ 表示一个决策树模型， $NumberOfLeaves(G)$ 即决策树的树叶数目，树叶数目越少，模型越复杂，（回归）越容易过拟合， $\lambda$ 是指定的正则化参数。

决策树桩（decision stump）

如前撰述，决策树桩是深度为一的决策树，典型的弱分类器，也可用于回归，常被用作集成学习中的基础模型。它可以将输入数据按照某种标准分为两部分。

决策树桩需要选择一个恰当的特征维度 $i$（ 输入向量 $\mathbf{x}$ 的一个维度）、 阈值 $\theta$ 与方向 $s={-1,1}$ 进行切割。它的分类器可表示为：

$$h_{s,i,\theta}(\mathbf{x}) = s \cdot sign(x_i - \theta)$$

对于训练数据 $D$ ，如何训练出一个最佳的决策树桩？根据决策树的训练方法，最原始的方法应该是尝试每一个可选的 $i, \theta, s$ ，计算不纯度，选择不纯度最低的一组参数。

极值点、拐点与泰勒公式

$$ f(x) = f(x_0) + f’(x_0)(x-x_0) + \frac{f’’(x_0)}{2!}(x-x_0)^2 + … + \frac{f^{(n)}(x_0)}{n!}(x-x_0)^n + R_n(x)
$$

对存在 n 阶导数的函数，

• 极值点要求一阶导数为 0，并且函数在邻域内先增后减或先减后增，称为“折回”的趋势；
• 拐点要求二阶导数为 0，并且要求二阶导数在邻域内左右异号，即单调的趋势。

从泰勒公式可见，在 $x_0$ 的 附近 ，

• 在 $x_0$ 的非 0 的偶数次导数使函数有“折回”的趋势（不受 $(x-x_0)$ 符号影响），
• 在 $x_0$ 的非 0 的奇数次导数使函数有单调趋势。
• 低阶导数比高阶导数更有“影响力”。

所以，有以下结论：

• 对极值点，要求一阶导数为 0，还要求第一个非 0 的更高阶导数的阶数为偶数；若为正，增加了附近的函数值，所以该点值更小，故为极小值，反之，极大值
• 对拐点，要求二阶导数为 0，还要求第一个非 0 的更高阶导数的阶数为奇数

凹凸性与泰勒公式

对存在 n 阶导数的函数，

• 上凸函数要求附近的值比切线值小一点，即曲线在切线的下方
• 下凸函数要求附近的值比切线值大一点，即曲线在切线的上方

对偶数阶导数，因为折回的趋势，对凹凸性有着影响；而对奇数阶导数，对函数左边加右边减或右边减左边加，且程度相同，对凹凸性没影响。

类似极值点，第一个非 0 的偶数阶导数，若为正，增加了附近的函数值，为下凸，反之为上凸。

微分中值定理

• 类柯西定理证明，存在一值使得等式成立： 构造辅助函数（原函数）
  • 必要时用积分，有时需要变换方程方便积分
  • 必要时解微分方程
• 定理运用经典条件：开区间可导，定区间连续，（罗尔中值定理）两点值相等
• 判断方程根存在
  • 介值定理
  • 罗尔中值定理，也需构造辅助函数（原函数）
• 用中值定理处理 2 个变量的等式
  • 首先考虑两者相等
  • 寻找三点值相等
  • 解 k 法：将其中一部分视为常数 k，构造辅助函数，令端点值相等（罗尔中值条件），解出 k 并用变量表示。

泰勒公式

出现二阶及以上的导数，可以用泰勒公式，展开点多选择特殊点，如极值点，中点等。

第一类换元法（凑微分）

将 积分变量 视作换元方程的 自变量
$$\int f[u(x)]u’(x) dx = \int f[u(x)] du(x)$$

第二类换元法

将 积分变量 视作换元方程的 函数
$$\int f(x) dx = \int f[x(t)]x’(t) dt$$
对 根式 可考虑第二类换元。

三角换元

存在下列类型的 根式，做三角换元：
$$\sqrt{a^2 - x^2},\quad let\; x=a\sin t$$
$$\sqrt{x^2 + a^2},\quad let\; x=a\tan t \quad (\tan^2t + 1 = \sec^2 t)$$
$$\sqrt{x^2 - a^2},\quad let\; x=a\sec t \quad (\sec^2t - 1 = \tan^2t )$$
实际上，只要存在 变量平方与常数和 的因子，都可以考虑三角代换，（$x^2+bx+c$ 可变换成 $x^2+c$ 形式）

例代换

新旧变量之间互为倒数换元。一般适用于 被积函数分母的幂至少比分子的高二次。

分部积分法

$$\int u dv = uv - \int v du$$

• 适用 两类函数相乘的结构，同类的两个函数也可考虑，如 $\sqrt{x}/(x-1)^2$
• 按 反、对、幂、三、指 的顺序选择 $u$ 效果较好
• 注意 循环、递推公式

分部积分中，首要任务 是发现被积函数是由两类函数构成的，而分式结构容易让人忽略这点，以下列举几个例子：
$$\frac{\arcsin x}{\sqrt{1+x}}, \quad \frac{\arctan e^x}{e^x}$$

有理公式

两个实系数多项式的商所表示的函数，如 $x / (x^2+1)$。积分方法是

1. 化为多个 真分式 的和，真分式有：

$$ \frac{A}{x+a},\quad \frac{A}{(x+a)^k},\quad \frac{Mx + N}{x^2+px+q},\quad \frac{Mx + N}{(x^2+px+q)^k} $$

1. 对真分式分别积分

三角函数有理式

其分母总能用 $sin x, cos x$ 表示，可令 $\tan \frac{x}{2} = t$ 做换元积分，因为 $\arctan x$ 求导为有理式，所以被积函数可转化为有理式，被称为 万能代换。

无法用初等函数表示的积分

$$\sin x^2,\quad e^{-x^2},\quad \sqrt{1+x^2},\quad \frac{\sin x}{x},\quad \frac{x}{\ln x}$$

连续必可积

连续函数必可积，但可积函数未必连续。

分段函数积分（包括绝对值函数）

如果分段函数连续则可积。分段求出原函数后，注意，因为原函数可导必连续，分段的常数 $C$ 应该有关联。

导数存在性

导数定义

首要注意在 $x_0$ 的某邻域内有定义

以下是错误例子：
$$ f’(x0) = \lim{\Delta x \rightarrow 0} \frac {f(x_0 + \Delta x) - f(x_0 - \Delta x)} {2 \Delta x}
$$
这里有 2 个问题：

1. 在 $x_0$ 处是否有定义
2. 在 $x_0$ 即使有定义，如果不连续（跳跃间断点），左右导数不相等

左导数等于右导数

导函数判断

• 连续
• 导函数左极限等于右极限
  导函数左右极限与左右导数，顾名思义，并非同一个概念。注意，该条件是可导的充分非必要条件。该条件可用于对分段函数可导做快速判断。

一阶微分形式不变性

无论 u 是中间变量还是自变量，都有 $dy = y’(u) du$。运用：

• 求复合函数的导数（微分）
• 凑微分积分法

隐函数、反函数及参数函数求导

隐函数

方程 $F(x, y) = 0$ 所确定的隐式函数 $y=f(x)$，往往不能用显式公式表示。求导方法：方程两边同时求导，同时将 y 视为 x 的函数。

反函数求导

如果 $x = g(y)$ 为 $y=f(x)$ 的反函数，则 $g’(y) = \frac {1} {f’(x)}$

参数函数求导

当参数方程不便将 y 由 x 表达时，用下列公式求导
$$\frac{dy}{dx} = \frac{\frac{dy}{dt}}{\frac{dx}{dt}}$$

n 阶导数

往往可以提出低次幂因子并消去

等价无穷小

化繁为简，要求 乘除因子

• 真底互换 + 等价无穷小：$\lim{x \rightarrow 0} {x+1} = \lim{x \rightarrow 0} {e^x}$
• 用带 $o(x)$ 余项的 泰勒公式

极限的四则运算及洛必达法则

两者的共性是，分别处理后极限存在才能做分别处理，即分别处理后极限不存在不能说明原式极限不存在。

转化成 $\frac{0}{0}$, $\frac{\infty}{\infty}$

• 使用 真底互换 处理幂型式子
• $f(x) + g(x) = g(x)(\frac{f(x)}{g(x)} + 1)$

洛必达使用条件

去心邻域 函数必须可导，尤其在应用题中注意。

导数定义处理

数列极限

常用 单调有界 证明极限存在，过程中常用数学归纳法。一般步骤：

• 代值猜测数列变化趋势（单调 上升或下降）
• 证明单调性
• 证明有界，可以先猜测得上界或下界，再证明

可导、连续与极限

可导必连续，连续必存在极限，反之不一定