排序算法如何在機(jī)器學(xué)習(xí)技術(shù)中發(fā)揮重要作用

在機(jī)器學(xué)習(xí)中，支持向量機(jī)（SVM）算法是針對(duì)二分類任務(wù)設(shè)計(jì)的，可以分析數(shù)據(jù)，識(shí)別模式，用于分類和回歸分析。訓(xùn)練算法構(gòu)建一個(gè)模型，將新示例分配給一個(gè)類別或另一個(gè)類別，使其成為非概率二元線性分類器；使用核技術(shù)還可以有效地執(zhí)行非線性分類。迄今為止線性核技術(shù)仍是文本分類的首選技術(shù)。

今天，人工智能頭條將首先從支持向量機(jī)的基礎(chǔ)理論知識(shí)入手，和大家探討一個(gè)良好的排序算法如何在解決 SVM 問題過程中，在機(jī)器學(xué)習(xí)技術(shù)中發(fā)揮的重要作用。

▌前言

當(dāng)前，機(jī)器學(xué)習(xí)(ML)正在迅速成為現(xiàn)實(shí)社會(huì)中最重要的計(jì)算技術(shù)之一。作為人工智能(AI)的一個(gè)分支，這項(xiàng)技術(shù)適用于諸多領(lǐng)域，包括自然語(yǔ)言翻譯和處理領(lǐng)域(如Siri和Alexa)、醫(yī)學(xué)研究，自動(dòng)駕駛及商業(yè)戰(zhàn)略發(fā)展等。一些令人眼花繚亂的算法正在被不斷創(chuàng)造來(lái)解決ML問題，并從數(shù)據(jù)流中學(xué)習(xí)模式以構(gòu)建AI的基礎(chǔ)設(shè)施。

然而，有時(shí)候我們需要回頭思考并分析一些基本算法是如何在這場(chǎng)機(jī)器學(xué)習(xí)革命中發(fā)揮作用及其所帶來(lái)的影響。下面我就舉一個(gè)非常重要的案例。

▌支持向量機(jī)

支持向量機(jī)(SVM)是過去幾十年發(fā)展中出現(xiàn)的最重要的機(jī)器學(xué)習(xí)技術(shù)之一。它的核心思想是給定一組訓(xùn)練樣本，每個(gè)樣本標(biāo)記屬于二分類中的一類，SVM將構(gòu)建一個(gè)用于對(duì)一個(gè)新的樣本進(jìn)行分類的模型，也就是說，它其實(shí)是一個(gè)非概率的二元線性分類器，廣泛用于工業(yè)系統(tǒng)，文本分類，模式識(shí)別，生物ML應(yīng)用等。

SVM的核心思想主要如下圖所示，它的最終目標(biāo)是將二維平面中的點(diǎn)分為紅藍(lán)兩類，這可以通過在兩組點(diǎn)集之間創(chuàng)建分類器邊界(利用分類算法從帶標(biāo)記的數(shù)據(jù)中學(xué)習(xí)邊界信息)來(lái)實(shí)現(xiàn)。下圖中展示了一些可能的分類器，它們都將正確地對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分類，但并非所有分類器都能使得分類后最接近邊界的數(shù)據(jù)點(diǎn)具有相同的邊距(距離)。從下圖中我們可以看出，其中只有一個(gè)分類器能夠最大化紅色和藍(lán)色點(diǎn)之間的距離，我們用實(shí)線表示該分類器而用虛線表示其他分類器。這種邊距最大化的效用是盡可能地放大兩個(gè)類別之間的距離，以便對(duì)新的點(diǎn)分類時(shí)分類器的泛化誤差盡可能小。

SVM算法最明顯的特征是分類器不依賴于所有數(shù)據(jù)點(diǎn)，這不同于依賴每個(gè)數(shù)據(jù)點(diǎn)特征并將其用于構(gòu)造分類器邊界函數(shù)的邏輯回歸算法。實(shí)際上，SVM分類器會(huì)依賴于一個(gè)非常小的子數(shù)據(jù)點(diǎn)集，這些數(shù)據(jù)點(diǎn)最接近邊界，同時(shí)它們?cè)诔矫嬷械奈恢每梢杂绊懛诸惼鬟吔缇€。由這些點(diǎn)構(gòu)成的向量唯一地定義并支持分類器函數(shù)，因此我們把這種分類器稱之為“支持向量機(jī)”，它的概念圖解如下圖所示。

這里，我們?yōu)榇蠹覝?zhǔn)備了一個(gè)關(guān)于 SVM的精彩視頻教程。

▌關(guān)于SVM工作背后的幾何解釋：Convex Hull

SVM算法背后的形式數(shù)學(xué)相當(dāng)復(fù)雜，但從直觀地我們可以理解為這是一種稱為 Convex Hull 的特殊幾何結(jié)構(gòu)。

什么是Convex Hull呢？形式上，在歐幾里德平面（Euclidean plan）或歐幾里德空間（Euclidean space）中的一組 X點(diǎn)的凸包（convex hull）或凸殼（convex envelope）或閉包（convex closure），是包含 X點(diǎn)的最小凸集。我們可以通過類比“橡皮筋”來(lái)更容易地理解這個(gè)概念。想象一下，橡皮筋在一組釘子（類比我們的感興趣點(diǎn)）周圍伸展。如果橡皮筋被釋放，它會(huì)纏繞在釘子周圍，從而形成一個(gè)緊密的邊界，這是我們開始定義的集合。由此產(chǎn)生的形狀就是凸包，我們可以通過那些由橡皮筋產(chǎn)生的邊界釘子集來(lái)描述它，下面的圖解將有助于更直觀地感受這個(gè)概念。

現(xiàn)在，我們可以很容易想象SVM分類器只不過是一種線性分類器，它通過二分法將連接這些凸包的線一分為二。因此，確定SVM分類器也就解決了找到一組點(diǎn)的凸包問題。

▌那么，如何確定凸包呢？

我們通過下面這個(gè)動(dòng)畫來(lái)說明這個(gè)問題！這里，我將展示用于確定一組點(diǎn)的凸包的Graham’s scan算法。該算法能夠沿著凸包的邊界順序，依次找到其所有的頂點(diǎn)，并通過堆棧的方法有效地檢測(cè)和去除邊界中的凹陷區(qū)域。

現(xiàn)在還有個(gè)問題是這種算法的效率如何，即Grahan’s scan算法的時(shí)間復(fù)雜度是多少呢？

事實(shí)證明，Grahan’s scan算法的時(shí)間復(fù)雜性取決于它用于尋找構(gòu)成凸包的正確點(diǎn)集的基礎(chǔ)排序算法。但是，一開始的排序算法又是什么呢？

Grahan’s scan算法的基本思想來(lái)自凸包的兩種特性：

只能通過逆時(shí)針轉(zhuǎn)動(dòng)來(lái)橫穿凸包區(qū)域

關(guān)于具有最低y坐標(biāo)的點(diǎn)p而言，凸包的頂點(diǎn)將以極角遞增的順序出現(xiàn)。

首先，這些點(diǎn)以數(shù)組 points的形式存儲(chǔ)。因此，算法由定位的參考點(diǎn)開始，這是具有最低 y坐標(biāo)的點(diǎn)（在有捆綁關(guān)系(ties)的情況下，我們通過選擇具有最低 x和 y坐標(biāo)的點(diǎn)來(lái)解綁）。一旦我們找到參考點(diǎn)，我們可以將該點(diǎn)移動(dòng)到數(shù)組 points的開頭，使其與數(shù)組中第一個(gè)點(diǎn)互換位置。

接著，利用剩余點(diǎn)相對(duì)于參考點(diǎn)的極角關(guān)系，我們對(duì)其進(jìn)行排序。經(jīng)過排序后，相對(duì)于參考點(diǎn)的極角最小點(diǎn)將位于數(shù)組的開始處，而具有最大的極角點(diǎn)將位于數(shù)組的末尾。

隨著所有的點(diǎn)都被正確地排序，現(xiàn)在我們可以運(yùn)行算法的主循環(huán)部分。當(dāng)我們處理主數(shù)組中的點(diǎn)時(shí)，循環(huán)并將增長(zhǎng)和縮小第二個(gè)列表?；旧希绻覀冺槙r(shí)針地旋轉(zhuǎn)點(diǎn)，那么這些點(diǎn)將被推到堆棧上；反之，則如果我們以逆時(shí)針地方向，則拒絕并從堆棧彈出這些點(diǎn)。第二個(gè)列表一開始是個(gè)空列表，在算法結(jié)束時(shí)，構(gòu)成凸邊界的點(diǎn)將出現(xiàn)在此列表中。堆棧數(shù)據(jù)結(jié)構(gòu)正用于此目的。

#Threepointsareacounter-clockwiseturnifccw>0,clockwiseif#ccw

因此，Graham’s scan算法的時(shí)間復(fù)雜度取決于排序算法的效率。我們可以使用任何通用的排序算法，但對(duì)于時(shí)間復(fù)雜度為 O (n^2)和 O (n.log(n))的算法而言（如下面的動(dòng)畫所示），它們之間的 Graham’s scan算法的效率存在很大差異。

▌總結(jié)

在本文中，我們展示了簡(jiǎn)單排序算法在解決 SVM 問題過程中發(fā)揮的作用，以及它與廣泛使用的機(jī)器學(xué)習(xí)技術(shù)之間的關(guān)系。雖然有許多基于離散優(yōu)化的算法可以用來(lái)解決SVM問題，但在構(gòu)建復(fù)雜的AI學(xué)習(xí)模型方面，這種方法被視為是一種重要而基礎(chǔ)高效的算法。