争取一个月把周志华老师的西瓜书以及课程视频啃完。

1. 绪论

科学	是什么、为什么
技术	怎么做
工程	做得多快好省
应用	拓展

机器学习：目前主要研究智能数据分析的理论和方法。
典型的机器学习过程：训练数据、使用学习算法训练、模型、测试集
示例（instance，无结果）、样例（example，有结果）；
属性（attribute）、属性值、属性空间、样本空间；
特征向量（feature vector）、输出空间
计算学习理论（Computational learning theory），其中最重要的模型是PAC（Probably Approximately Correct）：
$P(|f(x)-g\vert\leq\varepsilon)\geq1-\delta$
其中，f(x) 代表hypothesis，g 代表ground-truth，以很高的概率得到一个很好的模型。
监督学习（supervised learning）& 非监督学习（unsupervised learning）：按照数据是否具有类别标记把任务进行分类
未见样本（unseen instance）/ 未知分布 / 独立同分布 / 泛化（generalization）

泛化能力（generalization ability）是指机器学习算法对新样本的适应能力。学习的目的是学到隐含在数据背后的规律，对具有同一规律的学习集以外的数据，经过训练的网络也能给出合适的输出，该能力称为泛化能力。这种能力也是学习到的模型对未知数据的预测能力，这个未见过的测试数据必须是和训练数据处于同一分布,不在同一分布的数据是不符合独立同分布假设的（对同一规律不同的数据集的预测能力）。通常通过测试误差来评价学习方法的泛化能力。

归纳偏好（inductive bias）：任何一个有效的机器学习算法必有其偏好
奥卡姆剃刀原则：若有多个假设与观察一致，则选最简单的那个

学习算法的归纳偏好是否与问题本身匹配，大多数时候直接决定了算法能否取得好的性能！

NFL定理（没有免费的午餐）：一个算法a若在某些问题上比另一个算法b好，比存在另一些问题使得算法b比a好

所有问题出现的机会相同，或所有问题同等重要；具体问题，具体分析！

西瓜书习题

2. 模型评估与选择

泛化能力强，然鹅，我们手上没有unseen instance

泛化误差	在“未来”样本上的误差
经验误差	在训练集上的误差，亦称“训练误差”
过拟合(overfitting)	不是树叶(误认为树叶必须有锯齿)
欠拟合(underfitting)	不是树叶(误认为绿色的都是树叶)

所有的算法都是为了缓解overfitting，误差是一定会存在的， $P\neq NP$ .

三大问题
如何获得测试结果？评估方法
如何评估性能优劣？性能度量
如何判断实质差别？比较检验
评估方法

留出法	保持数据分布一致性；多次重复划分；测试集不能太大或太小
k-折交叉验证法	若k=m，Leave-one-out，留一法
自助法	基于自助采样(bootstrap sampling)，有放回采样；用没取到的进行测试，“包外估计”(out-of-bag estimation)；数据分布有所改变

算法的参数：一般由人工设定，“超参数”；
模型的参数：一般由学习确定；
调参过程相似：先产生若干模型，然后基于某种评估方法进行选择；
参数调的好不好，对最终性能往往有关键影响

训练集 vs 测试集 vs 验证集，算法参数选定后，再用“训练集+验证集”重新训练最终模型。

性能度量

什么样的模型是好的，不仅取决于算法和数据，还取决于任务需求。

回归任务常用均方误差
错误率 VS 精度
查准率 VS 查全率

查准率：
$P=\frac{TP}{TP+FP}$
查全率：
$R=\frac{TP}{TP+FN}$
F1度量：
$F1=\frac{2\times P\times R}{P+R}$
若对查准率/查全率有不同偏好：
$F_\beta=\frac{(1+\beta^2)\times P\times R}{(\beta^2\times P)+R}$
其中， $\beta>1$ 时查全率有更大影响， $\beta<1$ 时查准率有更大影响。

比较检验

在某种度量下取得评估结果后，不能直接比较以评判优劣。
测试性能不等于泛化性能；
测试性能随着测试集的变化而变化；
很多机器学习算法本身有一定的随机性；
统计假设检验(hypothesis test)为学习机器性能比较提供了重要依据。

3. 线性模型

线性模型（linear model）试图学得一个通过属性的线性组合来进行预测的函数：

$f(x)=\omega_1x_1+\omega_2x_2+\ldots+\omega_dx_d+b$

向量形式为： $f(x)=\omega^Tx+b$

线性回归（linear regression）
$f(x)\simeq y$
离散属性的处理：若有序（order），则连续化；否则，转化为k维向量。
最小二乘解：分别对 $\omega$ 和 $b$ 求导，令导数为0，可以得到闭式解（closed-form）
$E_(\omega,b)=\sum_{i=1}^{m}(y_i-\omega x_i-b)^2$
多元（multi-variate）线性回归
$f(x_i)=\omega^Tx_i+b$
其中 $x_i=(x_{i1};x_{i2};\dots;x_{id})$ , $f(x_i)\simeq y_i$ .
最小二乘法求解：
$\begin{aligned} \hat{\omega}^*&=\arg\,\min(y-X\hat{\omega})^T(y-X\hat{\omega}) \\ &=\arg\,\min y^Ty-y^TX\hat{\omega}-(X\hat{\omega})^Ty+(X\hat{\omega})^TX\hat{\omega} \\ &=\arg\,\min y^Ty-2y^TX\hat{\omega}+(X\hat{\omega})^TX\hat{\omega} \end{aligned}$
其中y 为 $m\times1$ ,X 为 $m\times (n+1)$ , $\hat{\omega}$ 为 $(n+1)\times1$ .

矩阵求导公式：

$\frac{\partial(A\omega)}{\partial(\omega)}=A^T$

$\frac{\partial(A\omega)^T(A\omega)}{\partial(\omega)}=2A^TA\omega$
对 $\hat\omega$ 求导，令导数为0，即
$2X^TX\hat{\omega}-2X^Ty=0$

若 $X^TX$ 为满秩或正定，则有唯一解，即 $\hat{\omega}^*=(X^TX)^{-1}X^Ty$ ；
若 $X^TX$ 不满秩，则有无穷多个解，此时可以引入正则化（regularization）或者求助于归纳偏好。
线性回归相关公式推导

广义（Generalized）线性模型
对数线性回归（log-linear regression）；
$\ln y={\omega}^Tx+b$
一般形式：
$y=g^{-1}({\omega}^Tx+b)$
对率回归（分类学习算法）

对数几率函数（logistic function），单调可微、任意阶可导：
$y=\frac{1}{1+e^{-z}}$
以对率函数为联系函数，得到对数几率回归（logistic regression）：
$\ln {\frac{y}{1-y}}=\omega^Tx+b$
其中, $\frac{y}{1-y}$ 表示几率(odds)，反映了x 作为正例的相对可能性。
无需事先假设数据分布；
可得到“类别”的近似概率预测；
可直接应用现有数值优化算法求取最优解。

对率回归求解

将y 看作类后验概率估计p(y=1 |x) ，则对率回归公式可写为
$\ln \frac{p(y=1|x)}{p(y=0|x)}=\omega^Tx+b$
不具有极值，无法采用最小二乘法求解。
对率回归详细推导

类别不平衡（class-imbalance）

不同类别的样本比例相差很大；“小类”往往更重要
若 $\frac{y}{1-y}>1$ 则预测为正例；若 $\frac{y}{1-y}>\frac{m^+}{m^-}$ 则预测为正例。
常见学习方法：
过采样（oversampling）、欠采样（undersampling）、阈值移动（threshold-moving）

4. 决策树

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

自根至叶的递归过程
信息熵（entropy）是度量样本集合“纯度”最常用的一种指标；
信息增益（information gain）直接以信息熵为基础，计算当前划分对信息熵所造成的变化。
增益率（gain ratio）

先从候选划分属性中找出信息增益高于平均水平的，再从中选取增益率最高的。

基尼指数（gini index）：反映了从D中随机抽取两个样例，其类别标记不一致的概率。
划分选择的各种准则虽然对决策树的尺寸有较大影响，但对泛化性能的影响很有限；
剪枝方法和程度对决策树泛化性能的影响更为显著。

剪枝（pruning）是决策树对付“过拟合”的主要手段。

决策树的详解
预剪枝（pre-pruning）& 后剪枝（post-pruning）
缺失值的处理：样本赋权、权重划分

决策树这一部分还得好好看看，感觉有些云里雾里的～～～

5. 支持向量机

将训练样本分开的超平面“正中间”的更好：鲁棒性最好，泛化能力最强。
超平面方程：
$\omega^Tx+b=0$
间隔（margin）与支持向量（support vector）

解的稀疏性：训练完成后，最终模型仅与支持向量有关。
支持向量机（support vector machine,SVM）因此而得名。
特征空间映射

如果原始空间是有限维（属性数有限），那么一定存在一个高维特征空间使样本线性可分。

核函数（kernel function）
$\kappa(x_i,x_j)=\phi(x_i)^T\phi(x_j)$

Mercer定理：若有一个对称函数所对应的核矩阵半正定，则它就能作为核函数来使用。

6. 神经网络

神经网络是由具有适应性的简单单元组成的广泛并行互连的网络。

“简单单元”：神经元模型
“激活函数”：理想激活函数是阶跃函数，阶跃函数具有不连续、不光滑的性质，最常见的是Sigmoid函数。
多层前馈网络结构，万有逼近性。

BP（backpropagation）算法，是一个迭代学习算法，每一轮迭代采用广义感知机学习规则，链式法则求解。
学习率不能太大或太小，考虑到学习速度和振荡问题。

7. 贝叶斯分类器

贝叶斯决策论（Bayesian decision theory）：总体风险最小，贝叶斯最优分类器，反映学习性能的理论上限。
机器学习所要实现的是基于有限的训练样本尽可能准确地估计出后验概率，有两种基本策略：

判别式模型	直接对条件概率建模	决策树；BP神经网络；SVM
生成式模型	先对联合概率建模，再得到条件概率	贝叶斯分类器

极大似然估计：先假设某种概率分布，再基于训练样例对参数进行估计。

连乘易造成下溢，因此通常使用对数似然（Log-likelihood）

朴素贝叶斯分类器

主要障碍：所有属性上的联合概率难以从有限训练样本估计获得；组合爆炸；样本稀疏

8. 集成学习和聚类

集成学习（Ensemble）
误差-分歧分解（erro-ambiguity decomposition）
集成学习方法：序列化方法（boosting）和并行化方法（bagging）
聚类：聚类的好坏不存在绝对标准

这一部分在《R语言统计分析与机器学习》这一专栏有详细介绍了，所以这里就没有做太多相关的笔记～～～

机器学习初步-西瓜书