機器學習(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