机器学习的目标是选择一个和未来的样例最佳拟合的假设。要做到这一点，需要定义“未来的样例”和“最佳拟合”。首先，假设未来的样例类似于过去观测过的样本。称之为平稳性假设；若没有它，所有的方法都没有意义。对于满足这些等式的样例，称它们为独立同分布的或$i.i.d.$。
下一步是定义“最佳拟合”。最佳拟合是最小化错误率——对于样例$(x, y)$，$h(x)\ne y$的比例——的假设。可以通过对一个假设进行测试来估计其错误率：在一组称为测试集的样例上评估它的表现。一个假设（或一个学生）在测试前偷看答案属于作弊行为。为确保这种情况不会发生，最简单的方法是将样例分割成两组：一组为用于训练从而得到假设的训练集，另一组为用于评估假设的测试集。如果只想建立一个假设，那么这个方法就足够了。但通常会得到多个假设：可能想要比较两个完全不同的机器学习模型，或者想要在同一个模型中调整不同的“超参数”。
假设一个研究者在一个超参数下的模型中训练出一个假设，并在测试集上测试了其错误率，然后继续尝试不同的超参数。没有任何一个单独的假设“偷看”或使用了测试集的数据，但整个过程通过研究者还是泄露了测试集的信息。避免这种依赖性的方法是将测试集完全锁定——直到完全完成了训练、实验、超参数调整、再训练这一系列过程。这意味着需要 3 个数据集。如果没有足够的数据来构成这 3 个数据集，则可以使用一种称为 k 折交叉验证的方法从数据中获得更多子数据集。最极端的情形是$k=n$，该情形也被称为留一交叉验证（$LOOCV$）。即使采用了交叉验证的方法，仍然需要一个单独的测试集。
一个线性的函数对数据集通常是欠拟合的，而高次多项式对数据通常是过拟合的。可以把找到一个好的假设这一目标分作两个子任务：模型选择，即选择一个好的假设空间；模型优化（也称为训练），即在这个空间中找到最佳假设。模型选择有一部分是定性的和主观的：基于对问题已有的一些了解与认识，可能会选择多项式函数而不选择决策树。模型选择的另一部分是定量的和经验性的：在多项式函数类中，可以选择次数为 2 的多项式，因为这个值在验证数据集上可能表现最好。
通常称一个完全拟合了所有训练数据的模型为对数据进行了插值。当模型的表达能力接近于插值临界点时，模型类已经开始过拟合。这似乎是因为模型的大部分表达能力都集中在训练样例上，而剩余的表达能力以不代表验证数据集中的模式的方式随机分布。有些模型类永远不会从这种过拟合的表现中自主地恢复过来，例如决策树。但是对于其他模型类，增加模型类的表达能力意味着有更多的候选函数，其中一些函数自然非常适合真实函数$f(x)$中的数据模式。表达能力越强，合适的表示函数就越多，优化方法就越有可能将结果落在其中一个之上。
深度神经网络、核机器、随机森林和增强集成都具有验证误差随模型类表达能力增加而减小的特点。可以用以下不同方式来扩展模型选择算法：比较不同的模型类，通过让模型选择函数使用决策树学习器和多项式学习器进行比较，观察哪个表现更好来实现。可以允许多个超参数的存在，这意味着需要有更复杂的优化算法以确定超参数，如网格搜索，而不是线性搜索。
到目前为止，模型一直在试图降低错误率。这显然比最大化错误率要好，但这样是不够的。例如，将电子邮件分类为垃圾邮件或非垃圾邮件的问题。把非垃圾邮件归类为垃圾邮件（这可能导致漏掉一封重要的邮件）比把垃圾邮件归类为非垃圾邮件（导致自己遭受几秒钟的骚扰）糟糕得多。因此，如果一个分类器所犯的大多数错误都是将垃圾邮件分类为非垃圾邮件，那么错误率为 1%的该分类器将比错误率仅为 0.5%但所犯的错误都是把非垃圾邮件分类为垃圾邮件的分类器要好。决策者应该最大化预期效用，那么学习器也应该最大化效用。然而，在机器学习中，传统的做法是将其表述为负面效用：最小化损失函数而不是最大化效用函数。从理论上来说，学习智能体通过选择最小化目前观测到的所有输入-输出对的预期损失的假设，来使其期望效用最大化。
通过最小化损失函数得到的最佳假设与真实函数$f$不同，有 4 种可能的原因：不可实现性、方差、噪声和计算复杂性。
第一，如果假设空间$H$实际上包含真实函数$f$，那么称该学习问题是可实现的。如果$H$是线性函数的集合，而真实函数$f$是一个二次函数，那么无论有多少数据可供使用，都无法找到真实函数$f$。
第二，方差意味着所使用的学习算法通常会针对不同的样例集合返回不同的假设。如果问题是可实现的，那么方差会随着训练样例数量的增加而逐渐减小到 0。
第三，函数$f$可能是非确定性的或有噪声的——对于同一个输入值$x$它可能返回不同的$f(x)$值。根据定义，噪声是无法被预测的（它只能被描述）。
第四，当假设空间$H$是一个庞大假设空间中的复杂函数时，系统地搜索所有可能性将是难以计算的；在这种情况下，搜索可以探索假设空间的一部分并返回一个相当好的假设，但并不能总是保证它是最佳的假设。
传统的统计学方法和早期的机器学习主要注重小规模学习，其中训练样例的数量可能从几十个到几千个不等。此时泛化损失主要来源于假设空间中不包含真实函数$f$而导致的近似误差，以及因为没有足够训练样例来限制方差而导致的估计误差。近年来，人们越来越重视大规模学习，它们通常有上百万的训练样例。在这样的问题中，泛化损失可能受到计算限制的约束，即如果有足够的数据和足够丰富的模型，可以找到一个非常接近真实函数$f$的假设$h$，但是找到它的计算是复杂的，所以需要采用近似的方法。
模型选择的另一种方法是寻找一个假设，它直接最小化经验损失与假设复杂性度量的加权和，称之为总代价：
其中$\lambda $是一个大于零的超参数，作为损失和假设复杂性度量之间的转换比率。如果选择了一个较好的$\lambda $，它可以很好地平衡简单函数中可能较大的经验损失与复杂函数中过拟合的倾向。通常把这个过程称为正则化，它显式地惩罚复杂假设的复杂性：希望寻找更规则的函数。现在结合了两种度量，即损失函数（L1 或 L2）和复杂性度量，称后者为正则化函数。正则化函数的选择依赖于假设空间。例如，对多项式假设空间来说，系数平方和是正则化函数的一个不错选择——保持系数平方和较小将引导避开剧烈波动的 12 次多项式。
另一种简化模型的方法是减少模型的维数。例如可以使用一个称为特征选择的过程来判断属性的相关性，然后丢弃不相关的属性。在没有转换因子$\lambda $的情况下，经验损失和复杂性将在同一尺度下进行度量，实际上这可能是可行的：它们都可以用计算机位来度量。首先将假设编码为图灵机程序，并计算其位数。然后计算对数据进行编码所需的位数，其中正确预测的样例的代价为零位，而错误预测的样例的代价取决于预测错误的严重程度。最小描述长度的假设为使所需的总位数最小化的假设。这个方法在一定情境下可以很好地工作，但是对于规模较小的问题，程序编码的选择——如何最好地将决策树编码为位字符串——将会影响结果。
前面描述了如何选择最佳的超参数值——通过对每个可能值应用交叉验证，直到验证错误率开始增大。当只存在一个超参数，且它的可能值不多时，这是一个很好的方法。但当存在多个超参数，或当它们具有连续值时，选择好的超参数值就较为困难。最简单的超参数调整方法是手动调参：根据个人以往的经验来猜测参数，在该参数下训练模型，并在验证集上测试其表现并分析结果，根据直觉得到参数调整的结果。之后重复此操作，直到获得满意的模型表现为止（运气不好的话，可能会耗光时间、计算预算或耐心）。如果只有几个超参数，且每个超参数都有比较少的可能值，那么一种称为网格搜索的更系统化的方法将是适用的：尝试所有超参数值的组合，观察哪个组合在验证集上表现得最好。不同的组合可以在不同的机器上并行运行，所以如果有足够的计算资源，这种尝试过程将不会太缓慢，尽管在某些情况下，模型选择一次超参数并运行会占用很大的计算资源。
如果参数可能值的组合太多，那么考虑从所有可能的超参数可能值组合的集合中随机搜索采样，并重复进行足够多次，只要愿意花费时间和计算资源就能找到足够好的参数组合。此外，随机搜索也适用于处理连续值的超参数选择。在每次训练需要花费很长时间的情况下，从每次训练中获取有用的信息将会对优化超参数有所帮助。贝叶斯优化将选择好的超参数值的任务本身视为一个机器学习问题，也就是说把超参数值$x$向量作为输入，把用这些超参数所建立与训练的模型在验证集上的总损失作为输出$y$；之后试图找到函数$y=f(x)$，来使损失$y$最小化。每次使用一组超参数进行训练时，都会得到一个新的$(y, f(x))$对，可以用它来更新对函数$f$的形式的猜测。
超参数选择的核心思想是在探索（尝试新的超参数值）与利用（选择与先前得到的结果较好的超参数值接近的超参数值）之间进行权衡。这与在蒙特卡罗树搜索中看到的权衡类似，实际上，这里也使用了上置信界的概念来最大限度地减少遗憾。如果假设函数$f$可以用一个高斯过程来近似，那么在数学上函数$f$的更新将表现得非常好。斯努克等人
一种可以代替贝叶斯优化的方法是基于群体的训练（$PBT$）。$PBT$首先使用随机搜索（并行地）训练大量
模型，其中每个模型具有不同的超参数值。接着训练第二代模型，可以基于上一代中较好的参数值，通过对其使用遗传算法中的随机突变来选择新的超参数值。因此，基于群体的训练既有随机搜索的优点，即可以并行地执行许多次训练，又具有贝叶斯优化（或由专业人士进行手动调参）的优点，即可以从过去的训练结果中获取信息并提供给之后的超参数选取。
如何确定模型所学的假设能否很好地预测还未被观测过的输入？也就是说，如果不知道目标函数$f$是什么样子的，该如何确定假设$h$是否接近目标函数$f$？这个问题已经存在了好几个世纪，奥卡姆、休谟等许多人都研究过。近几十年以来，又陆续出现了其他问题：要获得较好的假设，需要多少样例？应该选用什么假设空间？如果假设空间非常复杂，是否可以找到最佳的假设$h$，还是只能找到局部最佳的假设？$h$应该有多大的复杂性？如何避免过拟合？
首先从学习需要多少样例这一问题入手。从决策树学习在餐厅等待问题上的学习曲线中可以看出，使用更多训练数据有利于提高准确性。学习曲线是有一定效果的，但它仅限于特定问题的特定学习算法。那么是否有一些更通用的法则来衡量所需的样例数量？诸如此类的问题统称为计算学习理论，它是人工智能、统计学和计算机理论等学科交汇的理论。解决这个问题的基本原理是，在用少量的样例进行训练之后，那些非常不匹配的假设将有很高的概率被“排除”，因为它们将做出错误的预测。因此，如果一个假设与足够多的训练样例相一致，那么它不太可能是严重不匹配的，也就是说，它必须是概率近似正确的（$probably$ $approximately$ $correct$，$PAC$）。任何返回概率近似正确的假设的学习算法都称为$PAC$学习（$PAC$ $learning$）算法。可以使用这种方法为各种学习算法提供性能限界。
与所有其他理论一样，$PAC$学习理论也是公理的逻辑结果。当一个定理基于过去的知识对未来进行预言时，公理必须提供“基础”以支撑这种联系。对$PAC$学习而言，该“基础”是由平稳性假设提供的，该假设意味着，将来的样例将从与过去的样例相同的固定分布中得出。（注意，人们可能不知道分布具体是什么样的，只知道它不会改变。）此外，出于方便考虑，假定真实函数$f$是确定性的，并且是正在考虑的假设空间$H$的一个成员。
