點擊上方關注，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中國 的文章
