技術創新篇

第三章 機器學習算法

第一節 總體發展概況

機器學習是指“計算機利用經驗自動改善系統自身性能的行為”，是一門多領域交叉學科，涉及概率論、統計學、逼近論、凸分析、算法復雜度理論等多門學科。簡而言之，機器學習指的是計算機可以像人類學習新事物一樣，在處理數據的過程中不斷地分析規律性信息，獲取新的知識和經驗，找到更優性能的解決方案以提升系統性能和智能性。它是人工智能核心，是使計算機具有智能的根本途徑，是機器智能化道路上邁出的重要一步。

一、發展歷程

2016年 3 月 15 日，谷歌公司開發的人工智能機器AlphaGo以總比分 4 : 1 戰勝圍棋世界冠軍李世石，轟動世界的“人機大戰”落下帷幕。2017年 1 月 4 日，升級為Master的AlphaGo，經過 7 天的“踢館”大戰，力克國際 60 位頂級圍棋高手，再次掀起“腥風血雨”。事實上，早在 20 世紀 50年代，人工智能便開始向人類發起挑戰。當時來自IBM工程研究組的薩繆爾（Samuel）開發出一款跳棋程序，該程序能夠在與人對弈的過程中，不斷累積經驗提升棋藝，并于 1959年戰勝了薩繆爾本人。應該說，無論是半個多世紀前的“跳棋對決”，還是當前的“人機大戰”，推動人工智能發展的核心動力未曾改變，即計算科學的璀璨明珠—機器學習。圍棋僅是機器學習應用的極小方面，在過去半個多世紀里，機器學習經歷了以下五個發展階段。

第一階段，是 20 世紀 40年代的萌芽時期。在這一時期，心理學家McCulloch和數理邏輯學家Pitts引入生物學中的神經元概念，在分析神經元基本特性的基礎上，提出“M-P神經元模型”。在該模型中，每個神經元都能接收到來自其他神經元傳遞的信號，這些信號往往經過加權處理，再與接受神經元內部的閾值進行比較，經過神經元激活函數產生對應的輸出。M-P神經元模型主要具有以下特征：

① 每個神經元都是多輸入輸出的信息處理單元。

② 神經元之間的連接方式包括“興奮”和“抑制”兩種，當某個神經元處于“興奮”狀態時，便會向相連神經元發送信號并改變其“電位”。

③ 每個神經元需要整合所有輸入信號并根據閾值決定是否“興奮”起來，即神經元具有空間整合特性和閾值特性。當接受信號的神經元“電位”超過自身閾值時，便“興奮”起來并重復信號發送過程。

④ 激活函數的選取應當視具體應用而定，主要分為連續型和非連續型。M-P神經元模型是神經網絡學習的基礎，而后者則是機器學習中出現時間最早、應用時間最長的模型。

第二階段，是 20 世紀 50年代中葉至 60年代中葉的熱烈時期。盡管在萌芽階段，神經元的運作過程得到明晰，但神經網絡學習的高效運作需要依賴相關學習規則。熱烈時期的標志正是經典學習規則的提出。早在 1949年，心理學家Hebb便提出與神經網絡學習機理相關的“突觸修正”假設。其核心思想是當兩個神經元同時處于興奮狀態時，兩者的連接度將增強，基于該假設定義的權值調整方法被稱為“Hebbian規則”。由于Hebbian規則屬于無監督學習，故在處理大量有標簽分類問題時存在局限。1957年，美國神經學家Rosenblatt提出了最簡單的前向人工神經網絡—感知器，開啟了有監督學習的先河。感知器的最大特點是能夠通過迭代試錯解決二元線性分類問題。在感知器被提出的同時，求解算法也相應誕生，包括感知器學習法、梯度下降法和最小二乘法（Delta學習規則）等。1962年，Novikoff推導并證明了在樣本線性可分情況下，經過有限次迭代，感知器總能收斂，這為感知器學習規則的應用提供了理論基礎。在熱烈時期，感知器被廣泛應用于文字、聲音、信號識別、學習記憶等領域。

第三階段，是 20 世紀 60年代中葉至 70年代中葉的冷靜時期。由于感知器結構單一，并且只能處理簡單線性可分問題，故如何突破這一局限，成為理論界關注的焦點。在冷靜時期，機器學習的發展幾乎停滯不前。究其原因，主要在于：

① 理論匱乏是制約人工神經網絡發展的關鍵因素。

② 隨著現實問題難度提升，單層人工神經網絡的應用局限越來越多。盡管這一時期出現了Winston的結構學習系統和Roth的邏輯歸納學習系統，但由于只能學習單一概念而未投入實際使用。

③ 計算機有限的內存和緩慢的處理速度使得機器學習算法的應用受到限制。與此同時，這一時期數據庫的容量相對較小，數據規模的增大也使得單一機器學習算法效果失真。

④ 以Minsky、Papert等為代表的一批學者對感知器效果提出嚴重質疑。他們通過嚴密推導并出版著作（如 1969年出版的《感知器》），來說明感知器應用失敗的事實。

在此之后，多國停止了對神經網絡研究的資助，這進一步加速了以感知器為核心的單層人工神經網絡的衰敗。

第四階段，是 20 世紀 70年代中葉至 80年代末的復興時期。1980年，美國卡內基梅隆大學舉辦了首屆機器學習國際研討會，標志著機器學習在世界范圍內的復興。1986年，機器學習領域的專業期刊Machine Learning面世，意味著機器學習再次成為理論及業界關注的焦點。在此復興時期，機器學習領域的最大突破是人工神經網絡種類的豐富，由此彌補了感知器單一結構的缺陷。1983年，加州理工學院物理學家Hopfield采用新型的全互連神經網絡，很好地解決了旅行商問題。1986年，UCSD的Rumelhart與McClelland合著《并行分布式處理：認知微結構的探索》一書，提出了應用于多層神經網絡的學習規則—誤逆差傳播算法（BP算法），推動了人工神經網絡發展的第二次高潮。除了BP算法，包括SOM（自組織映射）網絡、ART（競爭型學習）網絡、RBF（徑向基函數）網絡、CC（級聯相關）網絡、RNN（遞歸神經網絡）、CNN（卷積神經網絡）等在內的多種神經網絡也在該時期得到迅猛發展。

第五階段，是 20 世紀 90年代后的多元發展時期。通過對前面四個階段的梳理可知，雖然每一階段都存在明顯的區分標志，但幾乎都是圍繞人工神經網絡方法及其學習規則的衍變展開。事實上，除了人工神經網絡，機器學習中的其他算法也在這些時期嶄露頭角。例如，1986年，澳大利亞計算機科學家羅斯·昆蘭在Machine Learning上發表了著名的ID3 算法，帶動了機器學習中決策樹算法的研究。20 世紀 90年代，自1995年蘇聯統計學家瓦普尼克在Machine Learning上發表SVM（支持向量機）起，以SVM為代表的統計學習便大放異彩，并迅速對符號學習的統治地位發起挑戰。與此同時，集成學習與深度學習的提出，成為機器學習的重要延伸。集成學習的核心思想是通過多個基礎學習器的結合來完成學習任務，最著名的是Schapire提出的Boosting算法、Freund和Schapire提出的AdaBoost算法、Breiman提出的Bagging算法以及Breiman提出的隨機森林算法。進入 21 世紀后，在計算機硬件技術飛速發展，以及研究界和產業界巨大需求刺激下，Ruslan Salakhutdinov和Geoffrey Hinton兩位機器學習界泰斗提出了深度學習模型，開啟了深度網絡機器學習的新時代，圍繞此技術的研究與應用開始急速發展，如圖 3-1 顯示，深度學習隨訓練數據的提升可有效增加預測準確率。隨著后來在云計算、大數據和計算機硬件技術發展的支撐下，深度學習開始在各行各業取得前所未有的成就，一批批成功的商業應用也不斷問市。其中具有代表性的應用有來自蘋果的Siri、微軟的Cortana語音助手，各大支付應用推出的人臉識別認證技術，以及名揚全球的谷歌AlphaGo戰勝頂尖人類圍棋高手的人機大戰事跡，標志著機器學習已經成為計算機科學中的一個重要領域。

二、算法分類

機器學習算法可以分為有監督學習、無監督學習、強化學習 3 種類型。半監督學習可以認為是有監督學習與無監督學習的結合。有監督學習通過訓練樣本學習得到一個模型，然后用這個模型進行推理。例如，我們如果要識別各種水果的圖像，則需要用人工標注的樣本進行訓練，得到一個模型，接下來，就可以用這個模型對未知類型的水果進行判斷，這稱為預測。如果只是預測一個類別值，則稱為分類問題；如果要預測出一個實數，則稱為回歸問題，如根據一個人的學歷、工作年限、所在城市、行業等特征來預測這個人的收入。

無監督學習則沒有訓練過程，給定一些樣本數據，讓機器學習算法直接對這些數據進行分析，得到數據的某些知識。其典型代表是聚類，例如，我們抓取了 1 萬個網頁，要完成對這些網頁的歸類，在這里，我們并沒有事先定義好的類別，也沒有已經訓練好的分類模型。聚類算法要自己完成對這 1 萬個網頁的歸類，保證同一類網頁是同一個主題的，不同類型的網頁是不一樣的。無監督學習的另外一類典型算法是數據降維，它將一個高維向量變換到低維空間中，并且要保持數據的一些內在信息和結構。

強化學習是一類特殊的機器學習算法，算法要根據當前的環境狀態確定一個動作來執行，然后進入下一個狀態，如此反復，目標是讓得到的收益最大化。如圍棋游戲就是典型的強化學習問題，在每個時刻，要根據當前的棋局決定在什么地方落棋，然后進行下一個狀態，反復的放置棋子，直到贏得或者輸掉比賽。這里的目標是盡可能贏得比賽，以獲得最大的獎勵。

三、主流算法

（1）支持向量機算法（Support Vector Machine）

支持向量機算法（SVM）可能是目前最流行、討論最多的機器學習算法之一，圖 3-2 為支持向量機算法示意圖。超平面是一條對輸入變量空間進行劃分的“直線”。支持向量機算法會選出一個將輸入變量空間中的點按類（類 0 或類 1）進行最佳分割的超平面。在二維空間中，你可以把他想象成一條直線，假設所有輸入點都可以被這條直線完全地劃分開來。SVM學習算法旨在尋找最終通過超平面得到最佳類別分割的系數。超平面與最近數據點之間的距離叫作間隔（margin）。能夠將兩個類分開的最佳超平面是具有最大間隔的直線。只有這些點與超平面的定義和分類器的構建有關，這些點叫作支持向量，它們支持或定義超平面。在實際應用中，人們采用一種優化算法來尋找使間隔最大化的系數值。

（2）線性回歸算法（Linear Regression）

在統計學和機器學習領域，線性回歸算法可能是最廣為人知也最易理解的算法之一，如圖 3-3 為線性回歸算法示意圖。預測建模主要關注的是在犧牲可解釋性的情況下，盡可能最小化模型誤差或做出最準確的預測。我們將借鑒、重用來自許多其他領域的算法來實現這些目標。線性回歸模型被表示為一個方程式，它為輸入變量找到特定的權重（即系數B），進而描述一條最佳擬合了輸入變量（x）和輸出變量（y）之間關系的直線。

（3）邏輯回歸算法（Logistic Regression）

邏輯回歸是機器學習從統計學領域借鑒過來的另一種技術，圖 3-4為邏輯回歸算法示意圖。它是二分類問題的首選方法，像線性回歸一樣，Logistic回歸的目的也是找到每個輸入變量的權重系數值。但不同的是，Logistic回歸的輸出預測結果是通過一個叫作“logistic函數”的非線性函數變換而來的。logistic函數的形狀看起來像一個大的“S”，它會把任何值轉換至 0～1 區間內。這十分有用，因為我們可以把一個規則應用于logistic函數的輸出，從而得到 0～1 區間內的捕捉值，并預測類別的值。

（4）線性判別算法

線性判別算法是一種傳統的分類算法，它的使用場景僅限于二分類問題，圖 3-5 為線性判別算法示意圖。如果你有兩個以上的類，那么線性判別算法（LDA）是首選的線性分類技術。LDA的表示方法非常直接。它包含為每個類計算的數據統計屬性。對于單個輸入變量而言，這些屬性包括每個類的均值和所有類的方差。線性判別分析預測結果是通過計算每個類的判別值、并將類別預測為判別值最大的類而得出的。該技術假設數據符合高斯分布，因此最好預先從數據中刪除異常值。LDA是一種簡單而有效的分類預測建模方法。

（5）最近鄰居/K-近鄰算法（K-Nearest Neighbors）

K-近鄰算法（KNN）是非常簡單而有效的，圖 3-6 為K-近鄰算法示意圖。KNN的模型表示就是整個訓練數據集。對新數據點的預測結果是通過在整個訓練集上搜索與該數據點最相似的K個實例（近鄰）并且總結這K個實例的輸出變量而得出的。對于回歸問題來說，預測結果可能就是輸出變量的均值；而對于分類問題來說，預測結果可能是眾數的類的值。關鍵之處在于如何判定數據實例之間的相似程度。如果你的數據特征尺度相同，那么最簡單的度量技術就是使用歐幾里得距離，你可以根據輸入變量之間的差異直接計算出該值。

（6）K-平均算法（K-Means）

K-平均算法是一種無監督學習算法，為聚類問題提供了一種解決方案，圖 3-7 為K-平均算法示意圖。K-Means算法把n個點劃分到k個集群，使得每個點都屬于離他最近的均值對應的集群。重復上述過程一直持續到重心不改變。

（7）決策樹算法（Decision Tree）

決策樹是一類重要的機器學習預測建模算法，圖 3-8 為決策樹算法示意圖。決策樹可以被表示為一棵二叉樹。這種二叉樹與算法設計和數據結構中的二叉樹是一樣的，沒有什么特別。每個節點都代表一個輸入變量（x）和一個基于該變量的分叉點。決策樹的葉子結點包含一個用于做出預測的輸出變量（y）。預測結果是通過在樹的各個分叉路徑上游走，直到到達一個葉子結點并輸出該葉子結點的類別值而得出。決策樹的學習速度很快，做出預測的速度也很快。它們在大量問題中往往都很準確，而且不需要為數據做任何特殊的預處理準備。

（8）樸素貝葉斯算法（Naive Bayes）

樸素貝葉斯是一種簡單而強大的預測建模算法，圖 3-9 為樸素貝葉斯算法示意圖。該模型由兩類可直接從訓練數據中計算出來的概率組成：①數據屬于每一類的概率；②給定每個x值，數據從屬于每個類的條件概率。一旦這兩個概率被計算出來，就可以使用貝葉斯定理，用概率模型對新數據進行預測。當你的數據是實值的時候，通常假設數據符合高斯分布（鐘形曲線），這樣你就可以很容易地估計這些概率。樸素貝葉斯之所以被稱為“樸素”，是因為它假設每個輸入變量相互之間是獨立的。這是一種很強的、對于真實數據并不現實的假設。不過，該算法在大量的復雜問題中十分有效。

（9）隨機森林算法（Random Forest）

隨機森林算法是最流行也是最強大的機器學習算法之一，它是一種集成機器學習算法，圖 3-10 為隨機森林算法示意圖。自助法是一種從數據樣本中估計某個量的強大統計學方法，你需要在數據中取出大量的樣本，計算均值，然后對每次取樣計算出的均值再取平均，從而得到對所有數據的真實均值更好的估計。Bagging使用了相同的方法。但是最常見的做法是使用決策樹，而不是對整個統計模型進行估計。Bagging會在訓練數據中取多個樣本，然后為每個數據樣本構建模型。當你需要對新數據進行預測時，每個模型都會產生一個預測結果，Bagging會對所有模型的預測結果取平均值，以便更好地估計真實的輸出值。隨機森林算法是這種方法的改進，它會創建決策樹，這樣就不用選擇最優分割點，而是通過引入隨機性來進行次優分割。因此，為每個數據樣本創建的模型比在其他情況下創建的模型更加獨特，但是這種獨特的方式仍能保證較高的準確率。結合它們的預測結果可以更好地估計真實的輸出值。如果使用具有高方差的算法獲得了良好的結果，那么通常可以通過該算法來獲得更好的結果。

（10）Boosting（增強算法）

Boosting是一種集成技術，它試圖集成一些弱分類器來創建一個強分類器，圖 3-11 為增強算法示意圖。它通過從訓練數據中構建一個模型，然后創建第二個模型嘗試糾正第一個模型的錯誤來完成。一直添加模型直到能夠完美預測訓練集，或添加的模型數量已經達到最大數量。AdaBoost是第一個為二分類開發的真正成功的Boosting算法。這是理解Boosting的最佳起點。現代Boosting算法建立在AdaBoost之上，最顯著的是隨機梯度提升。AdaBoost與短決策樹一起使用。在第一個決策樹創建之后，利用每個訓練實例上樹的性能來衡量下一個決策樹應該對每個訓練實例付出多少注意力。難以預測的訓練數據被分配更多權重，而容易預測的數據分配的權重較少。依次創建模型，每個模型在訓練實例上更新權重，影響序列中下一個決策樹的學習。在所有決策樹建立之后，對新數據進行預測，并且通過每個決策樹在訓練數據上的精確度評估其性能。因為在糾正算法錯誤上投入了太多注意力，所以具備已刪除異常值的干凈數據非常重要。

（11）降維算法（Dimensional Reduction）

在機器學習和統計學領域，降維是指在限定條件下，降低隨機變量個數，得到一組“不相關”主變量的過程，并可進一步細分為特征選擇和特征提取兩大方法，圖 3-12 為降維算法示意圖。一些數據集可能包含許多難以處理的變量。特別是在資源豐富的情況下，系統中的數據將非常詳細。在這種情況下，數據集可能包含數千個變量，其中大多數變量也可能是不必要的，幾乎不可能確定我們預測影響的最大變量。此時，我們需要使用降維算法，降維的過程中也可能需要用到其他算法，例如借用隨機森林、決策樹算法來識別最重要的變量。