排序算法与机器学习
机器学习(ML)正迅速成为现代社会中最重要的计算技术之一。作为人工智能(AI)的一个分支，它正被应用于从自然语言翻译和处理(如Siri或Alexa)到医学、自动驾驶或商业策略开发的方方面面。为了解决ML问题，从数据流中学习模式并构建人工智能基础设施，人们正在不断开发一系列令人眼花缭乱的智能算法。
在本文中，我们展示简单排序算法是如何解决计算几何中的一个重要问题的核心，以及它与广泛使用的机器学习技术的关系。
支持向量机
支持向量机，简称SVM，是近几十年来发展起来的最重要的机器学习技术之一。给定一组训练示例(每个都标记为属于两个类别中的一个或另一个)，SVM训练算法构建一个模型，将新的示例分配给一个类别或另一个类别，使其成为一个非概率二元线性分类器。它广泛应用于工业系统、文本分类、模式识别、生物ML应用等领域。
这个想法在下面的图片中得到了说明。主要目标是将二维平面上的点分为红蓝两类。可以通过在两组点之间创建分类器边界(通过运行分类算法并从标记的数据中学习)来完成。图中显示了一些可能的分类器。它们都将正确地对数据点进行分类，但并非所有的数据点都与最接近边界的数据点集有相同的“margin”(即距离)。可以看出，在蓝色和红色的点之间，只有其中一个能最大限度地增加这种“margin”。唯一的分类器用实线表示，而其他分类器用虚线表示。这种边距最大化的效用是，两个类之间的距离越大，泛化误差就越小。
图1：SVM和Maximum-margin分类器
SVM算法的主要区别特征是分类器不依赖于所有数据点（不同于逻辑回归，其中每个数据点的特征将用于构造分类器边界函数）。实际上，SVM分类器依赖于非常小的数据点子集，这些数据点最接近边界并且其在超平面中的位置可以影响分类器边界线。由这些点形成的向量唯一地定义分类器函数并且它们“ 支持 ”分类器，因此称为“支持向量机”。这个概念如下图所示
支持向量机工作原理的几何解释:凸壳
支持向量机算法背后的形式化数学是相当复杂的，但是从直观上来说，它可以通过考虑一种称为凸壳的特殊几何结构来理解。
什么是Convex Hull？在欧几里得平面或欧几里得空间中，一个集合X的凸壳或凸包是包含X的最小的凸集。假设一根橡皮筋被拉伸到一组钉子(我们的兴趣点)的周长。如果橡皮筋松开，它就会缠绕在挂钩上，从而形成一个定义原始集合的紧密边界。所得到的形状是凸壳，可以通过接触橡皮筋创建的边框的一组胶皮来描述。想法如下所示
现在，很容易想象SVM分类器只是一个线性分离器，它将连接这些凸壳的直线一分为二。
因此，确定支持向量机分类器就减少了求一组点的凸包的问题。
如何确定凸壳？
让我展示用于确定一组点的凸包的算法。它被称为格雷厄姆扫描。该算法找到沿其边界排序的凸包的所有顶点。它使用堆栈有效地检测和去除边界中的凹陷。
图：格雷厄姆扫描找到凸壳
现在，问题是这个算法的效率如何，即格雷厄姆扫描方法的时间复杂度是多少？
格雷厄姆扫描的时间复杂度取决于它需要使用的底层排序算法来找到构成凸包的正确的点集。但是排序一开始是什么呢?
这种扫描技术的基本思想来自于凸壳的两个性质
- 只能通过逆时针转动来穿过凸包
- 凸壳的顶点相对于具有最低y坐标的点p以极角的递增顺序出现
首先，这些points存储在一个数组中。因此，算法首先定位一个参考点。这是y坐标最低的点(如果有约束，我们通过选择y坐标最低的点和x坐标最低的点来打破约束)。一旦我们定位了参考点，我们就把这个点移动到点的起点，使它与数组中的第一个点交换位置。
图：堆栈数据结构
通过正确排序的点，我们现在可以在算法中运行主循环。循环使用第二个列表，当我们处理主数组中的点时，该列表将增长和缩小。基本上，如果旋转变为顺时针，我们将以逆时针方向旋转出现的点推到堆栈并拒绝点（从堆栈弹出）。第二个列表开始是空的。在算法结束时，构成凸边界的点将出现在列表中。
伪代码
# Three points are a counter-clockwise turn if ccw > 0, clockwise if
# ccw < 0, and colinear if ccw = 0 because ccw is a determinant that #gives twice the signed area of the triangle formed by p1, p2, and #p3.
function ccw(p1, p2, p3):
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)
let N be number of points
let points[N] be the array of points
swap points[0] with the point with the lowest y-coordinate
# This is the most time-consuming step
sort points by polar angle with points[0]
let stack = NULL
push points[0] to stack
push points[1] to stack
push points[2] to stack
for i = 3 to N:
while ccw(next_to_top(stack), top(stack), points[i]) <= 0:
pop stack
push points[i] to stack
end
因此，格雷厄姆扫描的时间复杂度取决于排序算法的效率。可以使用任何通用排序技术，但使用O（n ^ 2）和O（n.log（n））算法（如下面的动画所示）之间存在很大差异。
图：各种排序算法的动画
最后
在本文中，我们展示了简单排序算法如何解决计算几何中的一个重要问题以及它与广泛使用的机器学习技术的关系。虽然有许多基于离散优化的算法来解决SVM问题，但这种方法证明了在核心使用基本有效的算法来构建复杂的AI学习模型的重要性。