绪论

CH1 绪论

最重要的是一些常见的基本术语的掌握：

机器学习本身就是基于数据的，从data set开始到sample space, feature vector, dimensionality这种常见的概念，以及hypothesis(假设)， ground-truth, supervised learning, generalization， version space这种的。

通常面对样本空间，我们会做一个非常强的假设，就是获得的样本都是independent and identically(i.i.d)独立同分布的，这个简写要牢记。

归纳(induction)和演绎(deduction)是科学推理的两大手段，前者从特殊到一般，后者反之。从样本中学习显然是归纳学习。

算法在学习过程中对某种类型假设的偏好，称为”归纳偏好”(inductive bias),可以看作是在假设空间中对假设进行选择的启发式。奥卡姆剃刀(Occam’s razor)是常见的、自然科学中最基本的原则，偏好简单的。

NFL定理(No Free lunch Theorem)证明了无论学习算法多聪明，他们的期望性能是一样的。但NFL有一个重要前提：所有问题出现的机会相同。其寓意是脱离具体问题，空谈算法毫无意义。

NFL Theorem

CH2 模型评估与选择

错误率(error rate)+精度(accuracy)=1。学习器在训练集上得到的是training error / empirical error, 在新样本上得到的误差是generalization error. 前者高而后者高的现象即overfitting，而前者都没学好的即欠拟合。

考虑到样本的iid， 一般要求训练集与测试集互斥。常见的评估法:留出法，交叉验证法，自助法。

留出法(hold-out)将数据集分为互斥的两个集合(2/3~4/5作为训练)，要注意的是划分要注意保持数据分布的一致性，有保留类别比例的分层采样法。一般采用若干次随即划分、重复进行实验评估后取平均值作评估结果。

交叉验证(cross validation)将数据集D分为k个大小相似的互斥子集，每个子集保持数据分布的一致性(分层采样)，每次用k-1个训练，剩下的用来测试，可以进行k次训练，即k-fold cross validation。当k=|D|,则称为留一法(Leave-One-Out,LOO), 此时不受随机样本划分的影响。

自助法(bootstrapping)每次从D中挑选一个样本，重复|D|次，样本在m次不被采到的概率$(1-\frac{1}{|D|})^{|D|}$ 。约有36.8%的样本未被采样到，可以作为测试，这样的测试称为 包外估计(out-of-bag estimate),这对集成学习非常有帮助(能产生多个不同的训练集)。但自助法产生的数据集改变了初始数据的分布，会引入估计偏差。Introduction tp bootstrap书挺长的，这边放一篇短文。

性能度量

错误率与精度是最常用的性能度量。
$$
错误率:E(f; D) = \frac{1}{m}\sum_{i=1}^{m}I(f(x_i)\not=y_i) = 1 - acc(f; D)
\ E(f;D) = \int_{x~D}(f)
$$