一、基本术语1.1机器学习假设P计算机程序在某任务类T上的性能。T计算机程序希望实现的任务类。E表示经验即历史的数据集。若该计算机程序通过利用经验E在任务T上获得性能P的改善则称该程序对E进行了学习。所有记录的集合为数据集。每一条记录为一个示例instance或样本sample。单个的特点为特征feature或属性attribute。属性张成的空间称为属性空间attribute space、样本空间sample space或输入空间。对于一条记录如果在坐标轴上表示则也是一个向量即为一个特征向量feature vector。一个样本的特征数为维数dimensionality。计算机程序学习经验数据生成算法模型的过程中每一条记录称为一个“训练样本”同时在训练好模型后我们希望使用新的样本来测试模型的效果则每一个新的样本称为一个“测试样本”。定义所有训练样本的集合为训练集trainning set[特殊]。所有测试样本的集合为测试集test set[一般]。训练样本亦称训练示例或训练例测试样本亦称测试示例或测试例。模型亦称作学习器learner。机器学习出来的模型适用于新样本的能力为泛化能力generalization即从特殊到一般。预测值为离散值的问题为分类classification。预测值为连续值的问题为回归regression。关于示例结果的信息为标记label拥有标记的示例为样例example若将样例看作对象的部分则称为样本。所有标记的集合为标记空间label space或输出空间。对于二分类任务两个类别为正类positive class和反类negative class其中反类亦称负类。训练数据有标记信息的学习任务为监督学习supervised learning。训练数据没有标记信息的学习任务为无监督学习unsupervised learning。1.2误差与过拟合我们将学习器对样本的实际预测结果与样本的真实值之间的差异成为误差error。定义在训练集上的误差称为训练误差training error或经验误差empirical error。在测试集上的误差称为测试误差test error。学习器在所有新样本上的误差称为泛化误差generalization error。学习能力过强以至于把训练样本所包含的不太一般的特性都学到称为过拟合overfitting。学习能太差训练样本的一般性质尚未学好称为欠拟合underfitting。可以得知在过拟合问题中训练误差十分小但测试误差教大在欠拟合问题中训练误差和测试误差都比较大。如果mmm个样本中有aaa个样本分类错误则错误率error rateEa/mE a/mEa/m;相应的精度accuracy1-错误率。补充信息机器学习通常假设样本空间中所有样本满足独立同分布independent and identically从一般到特殊为特化即为演绎例如推导公式从特殊到一般为泛化显然机器学习亦称归纳学习inductive learning。解决欠拟合可以尝试在决策树中增加分支、增加训练轮数而过拟合只能缓解。二、假设空间狭义的归纳学习为概念学习或概念形成例如布尔概念学习。“记住”训练样本为机械学习所有假设组成的空间为假设空间若多个假设与训练集一致即为版本空间version space。三、归纳偏好机器学习算法在学习过程中对某种类型假设的偏好称为归纳偏好inductive bias或偏好。引导归纳偏好的原则奥卡姆剃须刀偏好更平滑、更简单。平滑曲线的描述简单性表示模型的泛化能力强是否如此我们假设样本空间X\mathcal{X}X和假设空间H\mathcal{H}H都是离散的。令P(h∣X,La)P\left(h \mid X, \mathfrak{L}_{a}\right)P(h∣X,La)代表算法La\mathfrak{L}_{a}La基于训练数据XXX产生假设hhh的概率再令fff代表我们希望学习的真实目标函数。La\mathfrak{L}_{a}La的“训练集外误差”为Eote(La∣X,f)∑h∑x∈X−XP(x)I(h(x)≠f(x))P(h∣X,La) E_{ote}\left(\mathfrak{L}_{a}|X,f\right)\sum_{h}\sum_{\mathbf{x}\in\mathcal{X}-X}P(\mathbf{x})\mathbb{I}(h(\mathbf{x})\neq f(\mathbf{x}))P\left(h|X,\mathfrak{L}_{a}\right)Eote(La∣X,f)h∑x∈X−X∑P(x)I(h(x)f(x))P(h∣X,La)其中I(⋅)\mathbb{I}(\cdot)I(⋅)是指示函数若⋅\cdot⋅为真则取值1否则取值0。考虑二分类问题且真实目标函数可以是任意函数对所有可能的fff按均匀分布对误差求和有∑fEote(La∣X,f)∑f∑h∑x∈X−XP(x)I(h(x)≠f(x))P(h∣X,La)∑x∈X−XP(x)∑hP(h∣X,La)∑fI(h(x)≠f(x))∑x∈X−XP(x)∑hP(h∣X,La)122∣X∣122∣X∣∑x∈X−XP(x)∑hP(h∣X,La)2∣X∣−1∑x∈X−XP(x)⋅1 \begin{aligned} \sum_{f}E_{ote}(\mathfrak{L}_{a}\vert X,f) \sum_{f}\sum_{h}\sum_{\mathbf{x}\in\mathcal{X}-X}P(\mathbf{x})\mathbb{I}(h(\mathbf{x})\neq f(\mathbf{x}))P(h\vert X,\mathfrak{L}_{a})\\ \sum_{\mathbf{x}\in\mathcal{X}-X}P(\mathbf{x})\sum_{h}P(h\vert X,\mathfrak{L}_{a})\sum_{f}\mathbb{I}(h(\mathbf{x})\neq f(\mathbf{x}))\\ \sum_{\mathbf{x}\in\mathcal{X}-X}P(\mathbf{x})\sum_{h}P(h\vert X,\mathfrak{L}_{a})\cfrac{1}{2}2^{\vert\mathcal{X}\vert}\\ \cfrac{1}{2}2^{\vert\mathcal{X}\vert}\sum_{\mathbf{x}\in\mathcal{X}-X}P(\mathbf{x})\sum_{h}P(h\vert X,\mathfrak{L}_{a})\\ 2^{\vert\mathcal{X}\vert-1}\sum_{\mathbf{x}\in\mathcal{X}-X}P(\mathbf{x})\cdot1 \end{aligned}f∑Eote(La∣X,f)f∑h∑x∈X−X∑P(x)I(h(x)f(x))P(h∣X,La)x∈X−X∑P(x)h∑P(h∣X,La)f∑I(h(x)f(x))x∈X−X∑P(x)h∑P(h∣X,La)212∣X∣212∣X∣x∈X−X∑P(x)h∑P(h∣X,La)2∣X∣−1x∈X−X∑P(x)⋅1显然总误差与学习算法无关即对于任意两个学习算法La\mathfrak{L}_{a}LaLa\mathfrak{L}_{a}La我们都有∑fEote(La∣X,f)∑fEote(Lb∣X,f) \sum_{f}E_{ote}\left(\mathfrak{L}_{a}|X,f\right)\sum_{f}E_{ote}\left(\mathfrak{L}_{b}|X,f\right)f∑Eote(La∣X,f)f∑Eote(Lb∣X,f)没有免费的午餐定理得证。前提条件所有“问题”出现的机会相同、或所有问题同等重要。