大神是怎么把基础算法玩出新花样的？
点击上方关注，All in AI中国
机器学习(ML)在现代社会的发展中正扮演着一个不可或缺的角色。作为人工智能(AI)的一个分支，它被应用于从自然语言翻译处理(比如说Siri或Alexa)到药业、自主驾驶、或业务战略开发等等多个方面。越来越多的算法不断被开发出来，以解决ML中所现存在的问题，进而为人工智能的发展带来新的理念和技术创新。
俗话说退一步海阔天空。放到人工智能这一块，我们可以有新的理解。比如说，退一步分析一些（原有的）基础算法是如何在这场人工智能革命中发挥自己的作用并明白他们在当中所扮演的角色。这无疑有助于我们对整个机器学习乃至人工智能都有一个全新的、全面的认识。这也是作者将在本文讨论的主要内容。
支持向量机
支持向量机是与相关的学习算法有关的监督学习模型，可以分析数据、识别模式，用于分类和回归分析。给定一组训练样本，对他们进行标记后为两类，用支持向量机建立一个模型，分配新的实例为一类或其他类，使其成为非概率二元线性分类。广泛应用于工业系统、文本分类、模式识别、生物ML应用等领域。
具体理解如下
我们的主要目标是将二维平面上的点分为红蓝两类。这可以通过在两组点之间创建分类器边界(通过运行分类算法并对标记的数据进行学习)来完成。图中显示了一些可能的分类器。理论上它们都将正确地对数据点进行分类。但可以看出并非所有的分类器都能平均地划分出红色和蓝色的点。也就是说，与蓝色和红色的点距离相同的分类器是唯一的。我们把唯一的分类器用实线表示，而其他分类器用虚线表示。我们之所以这样做是为了减小所得结果的误差。
支持向量机算法的主要特点是分类器不依赖于所有数据点。(与逻辑回归不同。在逻辑回归中，每个数据点都非常重要)。事实上，支持向量机分类器依赖于一个非常小的数据点子集，这类数据点大多靠近边界。其在平面上的位置对分类器边界线有着非常大的影响。由这类点组成的向量定义了这种分类器。换句话说，它们对分类器发挥着"支持（撑）"作用，这也是"支持向量机"这个名称的由来。概念如下图所示。
阅读更多内容请点击：http://web.mit.edu/6.034/wwwbob/svm.pdf
支持向量机工作原理的几何解释：凸包
凸包指在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点（X1，...Xn）的线性组合来构造。在二维欧几里得空间中，凸包可想象为一条刚好包着所有点的橡皮圈。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有的点。
现在，人们很容易想象，支持向量机分类器只不过是平分这些凸包中间点的直线。
因此，确定支持向量机分类器可以简化为寻找一组凸包中间点的问题。
如何确定凸包？
在这里，作者推荐Graham's scan算法。即求出沿凸包边界排列的所有顶点，然后使用堆栈进行检测和调整。
现在的问题是，这个算法的效率有多高，换句话说，使用Graham's scan算法需要多长的时间？
作者经过研究发现，Graham's scan算法效率取决于排序算法寻找构成凸包正确点集的时间。现在，让我们回到起点，Graham's scan算法初始是怎样工作的？
这取决于凸包的两个特征：
- 可以通过逆时针旋转连到凸包上的其他点吗?
- 凸包的顶点以极角递增的方式出现
首先，这些点存储在一个名为"points"的阵列中。因此，我们的算法首先需要一个参考点。通常是位于y坐标的最低点(如果有多个点并列，我们通过选择离y坐标最近、离x坐标最近的点)。一旦我们定位了这个参考点，我们就把这个点和位于"points"阵列中第一个点交换位置。
接下来，我们根据这个点相对于参考点的极角对剩余的点进行排序。排序后，相对于参考点极角最小的点将位于阵列的开始，极角最大的点将在最后。
伪码
因此，运行Graham's scan算法的所需时常取决于排序算法的效率。需要补充的是，任何通用的排序技术都可以使用，但是使用O(n^2)和O(n.log(N)算法的效果如下面的动画所示。
总结
本文简单介绍了排序算法是如何解决计算几何的核心问题，以及它与机器学习技术的关系。虽然有许多非常优秀的算法来解决支持向量机存在的问题，但作者也证明了原有（基础）的算法对构建复杂学习模型的重要性。
运营：李佳惠
感谢您对AI中国的关注，如有转载、投稿或商务合作请私信小编！