线性模型
给出$xy$平面上的一个含有$n$个样例点的训练集，要找到最匹配这些数据的线性函数$hw$，该任务被称为线性回归，要用数据拟合出一条直线，实际上需要做的就是找到对应的权重值使得其经验损失最小。通常采用平方误差损失函数$L2$，并对所有训练样例进行求和，该问题有唯一解。
许多形式的学习都涉及调整权重以最大限度地减小损失，因此对损失函数在权重空间——由所有可能权重值构成的空间——上的变化有一个直观认识是有帮助的。对于单变量线性回归，由$w_0$和$w_1$定义的权重空间是一个二维空间，因此可以在三维图中绘制损失函数与$w_0$和$w_1$的函数关系图。可以发现损失函数是凸的；对于采用$L2$损失的每个线性回归问题，这个结果都是正确的，凸的性质意味着损失函数没有局部极小值。从某种意义上来说，线性回归模型到这里已经完成了。
单变量线性回归模型有一个很好的性质，即利用最优解处的偏导数为 0，很容易找到模型的最优解。但在其他模型中，情况并非总是如此，因此需要介绍另一种使损失函数最小化的方法，该方法不依赖于通过求解导数的零点来求解模型，并且可以应用于任何损失函数，无论它有多复杂。其方法为通过逐步修改参数来搜索连续的权重空间，在搜索中将此算法称为爬山算法，但现在的目标是将损失最小化，而不是将收益最大化，因此使用梯度下降一词。首先选择权重空间中的任何一点作为起点——该问题中选择$(w_0, w_1)$平面上的一个点，然后计算梯度的估计值，并在最陡峭的下坡方向移动一小步，重复这一过程直到收敛到权重空间上某一点为止，它将在权重空间具有（局部）最小的损失。
其中参数$\alpha $，在搜索中称之为步长，当试图最小化学习问题中的损失函数时，通常称之为学习率。它可以是一个固定的常数，也可以随着学习过程的进行逐渐衰减。
通常用于单变量线性回归的是批梯度下降学习法则（也称确定性梯度下降）。其损失曲面是凸的，这意味着训练不会陷入局部极小值，到全局最小值的收敛性可以保证（只要不选择一个过大的$\alpha $），但是有可能非常慢：在每一步更新中必须对所有$N$个训练样例进行求和，并且可能会进行很多轮更新。如果$N$的大小超过处理器的内存大小，那么问题就更加复杂了。遍历了所有训练样例的一步更新，称之为轮（$epoch$）。一种速度更快的变种是随机梯度下降（$SGD$）：它在每一步中随机选择少量训练样例进行更新。$SGD$的初始版本为在每一步中仅选择一个训练样例，但现在更常见的做法是从$N$个样例中选择一个大小为$m$的小批量。
小批量$SGD$的收敛性是没有严格保证的；因为它会在最小值附近波动，而不会稳定下来。$SGD$在在线的情境中可能会有较大作用，在这种情况下，新数据的产生是逐次逐个的，并且平稳性假设可能不成立。在选择了一个较好的学习率$\alpha $后，模型就会逐渐优化，并记住它过去学到的一些知识，还可以适应蕴含在新数据中的分布的变化。$SGD$已经被广泛地应用于除线性回归以外的模型，尤其是神经网络。即使损失平面不是凸的，该方法也已被证明可以有效地找到接近全局最小值的性质良好的局部极小值。
对线性函数来说，函数的复杂性取决于权重的大小，可以考虑如下的正则化函数族：
它和损失函数的联系在于，当$q = 1$时，它是$L1$正则化，它最小化输入的绝对值和；当$q = 2$时，它就是$L2$正则化，最小化输入的平方和。那么应该选择哪个正则化函数？这取决于待解决的特定问题，但总的来说，$L1$正则化有一个重要的优势：它倾向于生成一个稀疏模型。也就是说，它通常能将许多权重置为$0$，从而表明相应的特征是完全不相关的，舍弃一些特征的假设对人类而言更容易理解，并且不太可能过拟合。$L2$正则化不会有产生$0$权重的倾向。在很多问题上的经验性证据表明，在$L2$正则化的情形下，找到一个性质良好的 h 所需的样例数与不相关特征的数量是呈线性关系的，但是在$L1$正则化的情形下则是对数级别的。
另一种看待$L1$正则化与$L2$正则化区别的方式是，$L1$正则化对维度轴的选取是严肃的，而 L2 正则化将它们看得很随意。$L2$函数是球对称的，因此具有一定的旋转不变性。
首先考虑带有硬阈值的线性分类器，线性函数可用于回归，也可以用于分类。决策边界是一条直线、一个平面或者更高维的面，它将不同类的数据分离。线性决策边界也被称为线性分离器，而允许这种分离器存在的数据称之为线性可分的数据。
当数据点线性可分时，感知机学习规则会收敛到理想的线性分离器。但是如果数据不符合条件怎么办？这种情况在真实世界中是很普遍的。通常来说，如果采用一个固定的学习率$\alpha $，感知机学习规则可能不会收敛到一个稳定的解，但是如果以$O(1/t)$的速度衰减，其中$t$是迭代次数，则可以证明，当样例以一个随机序列的形式逐个输入时，该更新规则会收敛到最小误差解。还可以证明寻找最小误差解是$NP$困难的，因此所希望的算法收敛需要的样例可能是非常多的。
接下来考虑基于逻辑斯谛回归的线性分类器，将线性函数的输出作为一个阈值函数的输入可以建立一个线性分类器。然而，硬阈值导致了一些问题：假设$hw(x)$是不可微的甚至关于输入和权重是不连续的。这使得使用感知机规则进行学习成为一种非常不可预测的冒险。除此之外，线性分类器始终输出一个确定性的 1 或 0 预测，即使对于非常接近于边界的样本也是如此。
如果能将一些样例明确分类为 0 或 1，而将其他处于边界的样本分类为“不清楚”，将是一个更好的结果。所有这些问题都可以通过软阈值这一扩展方法来解决——通过使用一个连续的、可微的函数来近似硬阈值函数。在概率推理中，提及了两个类似于软阈值的函数：标准正态分布的积分（用于概率单位模型）和逻辑斯谛函数（用于$logit$模型）。尽管这两个函数的形状非常相似，但逻辑斯谛函数具有更好的数学性质：
拟合该模型的权重以最小化数据集上的损失的过程，称为逻辑斯谛回归。在该模型中，没有简单的闭式解可以找到$w$的最优值，但是梯度下降的计算很直接。这个假设不再只输出$0$或$1$，可以使用$L2$损失函数。为了保持公式的可读性，使用$g$表示逻辑斯谛函数，并使用$g’$作为其导数。
在线性可分的数据中逻辑斯谛回归的收敛速度相对更慢，但收敛的过程可预测性更高。当数据分别是带有噪声的和不可分的时，逻辑斯谛回归的收敛速度明显更快，更稳定。这些优势往往会延续到实际应用中，目前逻辑斯谛回归已经成为医学、市场营销、调查分析、信用评分、公共卫生和其他应用中最流行的分类技术之一。
非参数模型
非参数模型是指无法用参数个数固定的参数集来表示的模型。例如，将所有数据点保留为模型的一部分。这样做的学习方法也被称为基于实例的学习或基于记忆的学习。最简单的基于实例的学习方法是查表：取所有的训练样例，将它们放在查找表中，然后在需要访问$h(x)$时，查看$x$是否在表中；如果是，则返回相应的$y$。这种方法的问题在于它不能很好地泛化：当$x$不在表中时，没有信息去输出一个合理的值。
可以对查表法进行一些细微的改进：给定待查询的$x_q$，寻找最接近它的$k$个样例，而不是寻找等于$x_q$的样例。这样的方法称为$k$近邻查找。使用符号$NN(k, x_q)$表示$x_q$的$k$个最近邻邻居的集合。
为了实现分类，找到一组邻居$NN(k, x_q)$，并以最常见的输出值为例，如果$k = 3$且输出值为$〈Yes, No, Yes〉$，则分类结果将为$Yes$。为了避免二分类结果数量相同，通常将$k$选择为奇数。为了实现回归，可以取$k$个邻居的平均值或中位数，也可以在最近邻邻居上求解一个线性回归问题。
和参数方法一样，非参数方法仍会面临欠拟合和过拟合的问题。1 近邻将会过拟合。它对离群值反应太大。但较高的$k$会导致欠拟合。通常，可以使用交叉验证来选择$k$的最佳值。“最近”一词意味着距离度量。那么如何测量从查询点$x_q$到样例点$x_j$的距离呢？通常，使用闵可夫斯基距离或$L^p$范数，其定义为：
当$p = 2$时，它为欧几里得距离，当$p = 1$时，它代表曼哈顿距离。对于布尔属性值，两个数据点不同的属性的数量称为汉明距离。如果维度所测量的是度量单位相似的特性，例如零件的宽度、高度和深度，通常使用欧几里得距离；如果维度的度量单位不相似，例如患者的年龄、体重和性别，则通常使用曼哈顿距离。注意，如果使用每个维度的原始数据来建模，则总距离将受到任何维度上单位变化的影响。也就是说，如果将高度的度量单位从米更改为英里，而宽度和深度的度量单位保持不变，那么将得到不同的最近邻。此外，如何比较年龄和体重这两种差异呢？一
种常见的方法是对每一个测量维度进行归一化。可以计算每个维度上的平均值和标准偏差，然后重新缩放它们。一个更复杂的方法称为马氏距离，它考虑了维度之间的协方差。
如果我们有低维空间中的大量数据，最近邻模型的效果将非常好：通常会有足够多的近距离数据点来获得较好的答案。但是随着维数的增加，我们会遇到一个问题：在高维空间中，最接近的数据点之间的距离通常并不小，这个问题被称为维数灾难。
将具有任意维数的数据集上的平衡二叉树称为$k$-$d$树，即$k$维树。$k$-$d$树的构造类似于平衡二叉树的构造。详见：
文章目录[隐藏] 红黑树 $kd$-树 红黑树 性质 插入 & […]
哈希表可能是一个比二叉树更快捷的查找方式。但哈希码依赖于精确的匹配，如何使用哈希表找到最近邻呢？哈希码在箱子（值容器）中随机分布数值，但是通常希望将距离近的数据点分在同一组并分布于同一个箱子中，因此我要使用局部敏感哈希（$LSH$）。从直觉上讲，如果 n 维空间的数据点是靠在一起的，即距离很近的，那么当把它们投影到一个一维空间（一条直线）上时，它们也必定是靠近的。实际上，可以将线离散化为多个箱子——哈希桶，以高概率将相近的点投影到同一箱子中。彼此距离较远的点往往会投影到不同的箱子中，但是总会有一些投影巧合地将相距较远的点同时投影到同一箱子中。因此，存储数据点$x_q$的箱子包含许多靠近$x_q$的点，但它也可能包含一些距离$x_q$较远的点。
$LSH$的技巧在于它创建了多个随机投影并将其进行组合，一个随机投影只是位串表示的一个随机子集，选择$\ell $个不同的随机投影并创建$\ell $个哈希表$g_1\left( x \right) ,…,g_{\ell}\left( x \right) $，然后将所有样例输入到每个哈希表中。给定查询点$x_q$，在每个哈希表箱子$g_{i}\left( x_q \right) $中获取点集，并将这些集合取并集作为一组候选点$C$。然后计算$x_q$到$C$中每一个点的实际距离，并返回其中$k$个距离最近的点。
每个接近$x_q$的点都以高概率出现在至少一个箱子中，虽然箱子中也会存在一些距离较远的点，但可以忽略这些点。对于现实中的大型问题，例如在含有$1300$万幅$512$维$Web$图像的数据集中找到其近邻，局部敏感哈希仅需要查找$1300$万幅图像中的几千幅就能找到最近邻，相比穷举法或$k$-$d$树方法，速度提高了上千倍。
现在考虑将非参数方法用于回归问题，而非分类问题下图给出了一些非参数模型的例子。第一个图使用了也许是所有模型中最简单的方法，非正式地称为“点连接”，正式一点也可以称为“分段线性非参数回归”。该模型构造了一个函数$h(x)$，当给定一个查询点$x_q$时，该函数考虑紧邻在$x_q$的左右两侧的样例，并在它们两点之间进行内插值。当数据中的噪声很小时，这种简单的方法效果还不错，这就是为什么它是电子表格的图表软件所用的标准技术。但是当数据噪声较大时，这个方法得出的函数将变得很尖锐，并且不能很好地泛化。
k 近邻回归在点连接的基础上做了改善，不使用查询点$x_q$左右两侧的两个样例进行预测，而是使用$k$个最近邻。尽管这个方法所得的函数是不连续的，但较大的$k$值会倾向于使尖峰的幅度减小并变得平滑。下图给出了$k$近邻回归的两个实现方式。在图 b 中，采用$k$个近邻的平均值，即$h(x)$是 k 个点的平均值。注意，在离群点$x = 0$和$x = 14$处这一估计的表现不太好，因为所有信息都来自同一侧（数据内侧），从而忽略了数据的趋势。在图 c 中，进行了$k$近邻线性回归，该回归通过$k$个样例去找到最佳拟合直线。这样可以更好地刻画离群值的变化趋势，但是函数仍然是不连续的。在图 b 和图 c 中，剩下的未提及的问题是如何选择合适的$k$值。解决方法通常是使用交叉验证。
局部加权回归（图 d）的方法利用了近邻的优势，且没有不连续性。为了避免$h(x)$中的不连续性，需要避免用于估计$h(x)$的样例集中的不连续性。局部加权回归的基本思想是，在每个查询点$x_q$上，接近$x_q$的样例将被赋予较高的权重，而距离较远的样例权重较小，最远的样例则将没有权重。权重的大小随距离的变化通常是渐变的，而不是突变的。
局部加权回归使用一个核（$kernel$）来确定每个样例的权重，该函数的输入是查询点与样例点之间的距离。核函数是关于距离递减的函数，其最大值在 0 处取到，因此$\mathcal{K}\left( Distance\left( x_j,x_q \right) \right) $将赋予更接近希望预测的查询点$x_q$的样例$x_j$更高的权重。核函数值在$x$的整个输入空间上的积分必须是有限的，如果令其积分为 1，则将使一些计算变得更容易。
图 d 中的函数是使用二次核$\mathcal{K}\left( d \right) =max\left( 0,1-\left( 2\left| d \right|/w \right) ^2 \right) $生成的，其核宽度为$w = 10$。其他形状的函数，例如高斯核函数，也经常被使用。通常来说，核宽度比实际形状更重要：这是模型的超参数，最好通过交叉验证来选择。如果核宽太大，将可能欠拟合；如果核宽太小，将可能过拟合。
利用核函数进行局部加权回归很容易，不过每当有一个新的查询点出现时，都需要重新解一个回归问题——这就是所谓局部的含义。（在传统的线性回归中，只需要解一个全局的回归问题，然后对任何查询点使用相同的预测函数$hw$。）能减轻这些额外工作的一个事实是，每个回归问题都是容易求解的，因为它仅考虑权重非零的样例——处于查询核宽度内的样例。当核宽度较小时，样本点可能只有少量几个。大多数非参数模型都有一个优点，即可以轻松应用留一交叉验证而无须重新计算所有内容。
在 21 世纪初期，当人们对某个领域没有任何专门的先验知识时，支持向量机（$SVM$）是最流行的解决监督学习问题的“现成”方法。这一地位现在已经被深度学习网络和随机森林取代了，但是$SVM$仍拥有 3 个具有吸引力的特性：
（1）支持向量机构造了一个极大边距分离器，即到样例点距离最大的决策边界。 这有助于它们较好地泛化。
（2）支持向量机构造了一个线性分离超平面，但是它们能通过使用所谓的核技巧来将数据嵌入更高维空间中。通常原始输入空间中不是线性可分的数据很容易在高维空间中被分离。
（3）支持向量机是非参数的——其分离超平面是由一组样例点而不是参数值的集合定义的。虽然例如最近邻等模型需要保留所有样例的信息，但$SVM$模型仅需要保留最靠近分离平面的样例——通常是一个较小的常数乘以维数。因此，$SVM$结合了非参数模型和参数模型的优点：它们可以灵活地表示复杂的函数，同时可以防止过拟合。
SVM 试图解决这样的问题：$SVM$并不是最小化训练数据上的期望经验损失，而是最小化期望泛化损失。人们不知道尚未观测的样例可能出现在哪里，但是在概率假设下，它们是从与之前所观测到的样例相同的分布中采样得到的，计算学习理论提出的一些观点表明，选择与到目前为止所观测到的样例相距最远的分离器，可以实现最小化泛化损失。称此分离器为极大边距分离器，如下图所示。边距是图中虚线所围成的区域的宽度，即从分离器到最近的样例点的距离的两倍。
支持向量机通过寻找带有最大边距的线性分离器来改进分类的泛化表现。即使原数据不是线性可分的，核方法也可以隐式地将输入数据投影到可能存在线性分离器的高维空间中。
