機器學習綜述

1、機器學習機器學習分類和組合技術綜述分類和組合技術綜述 匯報人：邵宏贍 導 師：嚴愛軍 2013.1.13 目錄目錄 1 引言 2 基本概念與學習系統(tǒng) 3 機器學習主要策略 4 發(fā)展與展望 1 引言引言 隨著信息技術的發(fā)展, 互聯(lián)網數(shù)據及資源呈現(xiàn) 海量特征。為了有效地管理和利用這些分布的海量 信息, 如何使機器具有認識問題和解決問題的能力, 就是讓機器如何更聰明、更具有人的智能, 這就是 機器學習。 ML 基本概念基本概念 機器學習的核心是學習。學習是一種多側面、綜合性 的心理活動,它與記憶、思維、知覺、感覺等多種心理 行為都有著密切的聯(lián)系 2 基本概念與學習系統(tǒng)基本概念與學習系統(tǒng) 目前在機器學

2、習研究領域影響較大的是H. Simon的觀 點:學習是系統(tǒng)中的任何改進學習是系統(tǒng)中的任何改進, ,這種改進使得系統(tǒng)在重這種改進使得系統(tǒng)在重 復同樣的工作或進行類似的工作時復同樣的工作或進行類似的工作時, ,能完成得更好。能完成得更好。 機器學習研究的就是如何使機器通過識別和利用現(xiàn)有 知識來獲取新知識和新技能。 機器學習是一門邊緣學科 機器學習的一個形象描述 基本概念基本概念 研究一種算法 1）提高它的性能（P） 2）在某項任務中（T） 3）利用一些經驗（E） well-defined learning task: 目前在眾多涉及計算機處理的技術應用中, 機器學習在許多領域都取得了很大的 進步,

3、 如用于人工智能、數(shù)據挖掘、自然語言處理、漢字識別、機器翻譯、專家 系統(tǒng)以及商業(yè)領域等。 機器學習應用機器學習應用 學習系統(tǒng)學習系統(tǒng) 學習系統(tǒng)學習系統(tǒng) 為了使計算機系統(tǒng)具有某種程度的學習能力, 使它能通 過學習增長知識,改善性能, 提高智能水平,需要為它建 立相應的學習系統(tǒng)。 一個學習系統(tǒng)一般應該由環(huán)境、學習、知識庫、執(zhí)行與 評價四個基本部分組成。 環(huán)境學習知識庫執(zhí)行與評價 學習系統(tǒng)學習系統(tǒng) 箭頭 表示信息的流向 根據反饋信息決定是否要從環(huán)境中索取進一步的信息進行學習, 以修改、完善知識庫中的知識 環(huán)境 外部信息的來源 為系統(tǒng)的學習提供有關信息 學習 系統(tǒng)的學習機構 對信息進行分析、綜合、類比

4、、歸納，獲得知識 知識庫 存儲由學習得到的知識 存儲時進行適當?shù)慕M織, 既便于應用又便于維護 執(zhí)行 處理系統(tǒng)面臨的現(xiàn)實問題 應用學習到的知識求解問題 評價 驗證、評價執(zhí)行環(huán)節(jié)的效果 機器學習的發(fā)展極為迅速,應用亦日益廣泛, 有很多優(yōu)秀 的學習算法,基本上可以分為基于符號學習和基于非符 號學習( 連接學習) 。其中符號學習比較好的有機械式 學習、指導式學習、示例學習、類比學習、基于解釋 的學習。 3 3 機器學習主要策略機器學習主要策略 集成學習集成學習 最近鄰算法最近鄰算法 遺傳算法遺傳算法 貝葉斯網絡貝葉斯網絡 決策樹決策樹 八種主要學習策略八種主要學習策略 MLML主要策略主要策略 支持向

5、量機支持向量機 EM算法算法 人工神經網絡人工神經網絡 遺傳算法 決策樹 EM算法 最近鄰算法 貝葉斯網絡 人工神經網絡 集成學習 按原理分類按原理分類 支持向量機 決策樹決策樹 決策樹就是根據特征值對實例進行分類。決定樹中的每個節(jié)點代表待分 類實例的一個特征，每個分支代表該節(jié)點可以假設的一個值。 決策樹模型決策樹模型 決策樹決策樹 決策樹可看作一個樹狀預測模型, 它通過把實例從根節(jié)點排列到 某個葉子節(jié)點來分類實例, 葉子節(jié)點即為實例所屬的分類。決策樹的 核心問題是選擇分裂屬性和決策樹的剪枝。 決策樹的算法有很多, 有ID3、C4. 5、CART 等等。這些算法均 采用自頂向下的貪婪算法, 每

6、個節(jié)點選擇分類效果最好的屬性將節(jié)點 分裂為2個或多個子結點, 繼續(xù)這一過程直到這棵樹能準確地分類訓練 集, 或所有屬性都已被使用過。 決定樹最有用的特性之一是其可理解性。人們可以很容易地理解 為什么一顆決策樹把一個實例分類歸類到一個特定的類。 決策樹原理及優(yōu)點決策樹原理及優(yōu)點 遺傳算法遺傳算法 遺傳算法（遺傳算法（GA）是建立在自然選擇和群體遺傳學機理基礎上的隨機迭 代和進化,具有廣泛適用性的搜索方法, 具有很強的全局優(yōu)化搜索能力。它模 擬了自然選擇和自然遺傳過程中發(fā)生的繁殖、交配和變異現(xiàn)象,根據適者生 存、優(yōu)勝劣汰的自然法則,利用遺傳算子選擇、交叉和變異逐代產生優(yōu)選個 體(即候選解) ,最終

7、搜索到較優(yōu)的個體。遺傳算法本質上是基于自然進化原 理提出的一種優(yōu)化策略, 在求解過程中, 通過最好解的選擇和彼此組合,則可 以期望解的集合將會愈來愈好。 遺傳算法受到研究人員廣泛重視是由于它采用隨機搜索方法隨機搜索方法,其特點是 幾乎不需要所求問題的任何信息而僅需要目標函數(shù)的信息,不受搜索空間是 否連續(xù)或可微的限制就可找到最優(yōu)解,具有強的適應能力和便于并行計算。 遺傳算法介紹遺傳算法介紹 遺傳算法遺傳算法 遺傳算法是一種種群型操作,該操作以種群 中的所有個體為對象。具體求解步驟如下: ( 1)參數(shù)編碼(2)初始種群的生成( 3) 適應度 函數(shù)的設計( 4)選擇復制( 5)雜交( 交叉) ( 6

8、) 變異 GA適用于解決復雜的非線性和多維空間尋 優(yōu)問題。經典遺傳算法的缺點是:有時計算 時間過長,不能保證解是全局最優(yōu)的。 遺傳算法步驟及優(yōu)缺點遺傳算法步驟及優(yōu)缺點 編碼生產初始種群 種群中個體適應度的計算與評價 物種選擇 雜交 變異 最近鄰規(guī)則最近鄰規(guī)則（NN）就是將待分類樣本點決策為距離 它最近的已知類別樣本點所屬的類別。通過這一規(guī)則構造 分類器，其誤差率為 最近鄰算法是一種基于實例的算法，也是一種懶惰學 習算法。在訓練階段比渴望學習算法（如決策樹，神經網 絡和貝葉斯網絡）有更少的計算時間，但在分類過程中需 要更多的計算時間。 其改進算法有，k-近鄰近鄰、剪輯最近鄰、剪輯最近鄰、SNN等

9、。 最近鄰算法最近鄰算法 ) )1(2( * MMRRRR 最近鄰算法最近鄰算法 貝葉斯網絡（貝葉斯網絡（ Bayesian network ）由于具有圖形化的模型表 示形式、局部及分布式的學習機制、直觀的推理；適用于表達和分 析不確定性和概率性的事物；能夠對不完全、不精確或不確定的知 識或信息中做出有效的推理等特性，而成為目前不確定知識表達和 推理領域最有效的模型之一。 貝葉斯網絡的學習主要包括：結構學習和參數(shù)學習，通過網絡 結構與數(shù)據集可以確定參數(shù)，因此結構學習是貝葉斯網絡學習的核 心，有效的結構學習方法和算法是構建最優(yōu)網絡結構的基礎。 貝葉斯網絡貝葉斯網絡 貝葉斯網絡簡介貝葉斯網絡簡介

10、貝葉斯網絡分類及特點貝葉斯網絡分類及特點 貝葉斯分類器家族中具有代表性的分類器, 即樸素( naive) 貝葉斯分類器、 貝葉斯網絡分類器和TAN( tree augmented nave Bayesian) 分類器；發(fā)現(xiàn)屬性 變量之間的依賴相對于屬性變量與類變量之間的依賴是可以忽略的，因此在所有 樹形分類器中TAN分類器是最優(yōu)的。 貝葉斯分類具有如下三個特點： （1）貝葉斯分類并不把一個對象絕對地指派給某一類，而是通過計算得出屬 于某一類的概率，具有最大概率的類便是該對象所屬的類； （2）一般情況下在貝葉斯分類中所有的屬性都潛在的起作用，即并不是一個 或幾個屬性決定分類，而是所有的屬性都參與

11、分類； （3）貝葉斯分類的對象的屬性可以是離散的、連續(xù)的、也可以是混合的。 貝葉斯網絡貝葉斯網絡 在人工智能、數(shù)據挖掘、模式識別和機器學習中有許多的應用都 要進行模型的參數(shù)估計, 也就是要進行極大似然估計或極大后驗似然 估計。一種非常流行的極大似然估計方法是Expectation- Maximization算法,通常簡稱為EM算法。 算法的命名,是因為算法的每一迭代包括兩步: 第一步求期望 (Expectation Step)，稱為E步；第二步求極大值(Maximization Step)，稱為M步。EM算法主要用來計算基于不完全數(shù)據的極大似然估 計。 EM算法的特點是簡單和穩(wěn)定， 特別是每一

12、次迭代能保證觀察數(shù) 據對數(shù)后驗似然是單調不減的。 EM算法算法 EMEM算法算法 一個連接模型(神經網絡) 是由一些簡單的類似神經元的單元以及單元間帶權的 連接組成。每個單元具有一個狀態(tài)，這個狀態(tài)是由與這個單元相連接的其他單元的 輸入決定的。連接學習通過使用各類例子來訓練網絡，產生網絡的內部表示，并用 來識別其他輸入例子。學習主要表現(xiàn)在調整網絡中的連接權,這種學習是非符號的， 并且具有高度并行分布式處理的能力。 一個人工神經網絡是由大量神經元節(jié)點經廣泛互連而組成的復雜網絡拓撲，用 于模擬人類進行知識和信息表示、存儲和計算行為。 人工神經網絡學習的工作原理是：一個人工神經網絡的工作由學習和使用兩

13、個 非線性的過程組成。從本質上講，人工神經網絡學習是一種歸納學習，它通過對大 量實例的反復運行，經過內部自適應過程不斷修改權值分布，將網絡穩(wěn)定在一定的 狀態(tài)下。 比較出名的網絡模型和學習算法有單層感知器(Perceptron)、Hopfield網絡、 Boltzmann機和反向傳播算法(Back Propagation，BP) 。 人工神經網絡人工神經網絡 ANNANN原理原理 人工神經網絡人工神經網絡 j T kj k Kjjj WOO )1 ( 是一個正數(shù)（為學習率），它決定梯 度下降搜索的步長。一個較大的值使反 向傳播以更快的速度向目標權重配置移 動，但同時也增加了不能達到這個目標 的幾

14、率。 對于輸出神元， 是第j個神經元的期望輸出 對于內部（隱藏）神經元， ijji OW i O )(1 ( Jjjjj OTOO j T 更新權重的一般規(guī)則是： 其中： 是第i個神經元的計算輸出 反向傳播ANN 權重計算權重計算 在神經網絡中，因為缺乏問題的先驗知識，往往需要經過大量費力費時的試 驗摸索才能確定合適的神經網絡模型、算法以及參數(shù)設置，其應用效果完全取決 于使用者的經驗?；诖嗽颍?990年，Hansen和Salamon開創(chuàng)性地提出了 神經網絡集成(Neural Network Ensemble) 方法。該技術來源于機器學習界目前 極熱門的Boosting 方法，也已成為當前

15、研究的熱點。 神經網絡的另一大缺陷就是其典型的“黑箱性”，即訓練好的神經網絡學到 的知識難以被人理解，神經網絡集成又加深了這一缺陷。 神經網絡是基于經驗風險最小化原則經驗風險最小化原則的學習算法, 有一些固有的缺陷,比如層 數(shù)和神經元個數(shù)難以確定, 容易陷入局部極小, 還有過學習現(xiàn)象, 這些本身的缺陷 在SVM算法中可以得到很好的解決。 人工神經網絡人工神經網絡 ANNANN缺陷缺陷 支持向量機支持向量機是Vapnik等人提出的一類新型的機器學習算法。 SVM算法的目的在于尋找一個超平面H(d)，該超平面可以將訓練集中的 數(shù)據分開，且與類域邊界的沿垂直于該超平面方向的距離最大，故SVM法亦 被

16、稱為最大邊緣( Maximum Margin) 算法。所謂最優(yōu)超平面就是要求超平面 不但能將兩類正確分開，而且使分類間隔最大；使分類間隔最大實際上就是 對模型推廣能力的控制，這正是SVM的核心思想所在。 總的來說,支持向量機就是首先通過用核函數(shù) 定義的非線性變換 將輸入空間變換到一個高維空間, 在這個空間中求( 廣義) 最優(yōu)分類面。SVMs 分類函數(shù)形式上類似于一個神經網絡,輸出是中間節(jié)點的線性組合, 每個中間節(jié) 點對應一個支持向量,如圖所示。 選擇不同的核函數(shù)就可以生成不同的支持向量機。常用的核包括: 多項式 核、高斯(徑向基函數(shù)) 核、二層神經網絡核等。目前支持向量機的訓練算法 是以序貫最

17、小最優(yōu)化(SMO)為代表的，其中工作集的選擇是實現(xiàn)SMO算法的 關鍵。 支持向量機支持向量機 ),( ji xxK SVMSVM算法實現(xiàn)算法實現(xiàn) 基于統(tǒng)計學習理論的支持向量機（SVM）方法，與傳統(tǒng)的基于經驗風險 最小化原則的學習方法不同，SVM基于結構風險最小化結構風險最小化，能在訓練誤差和分 類器容量之間達到一個較好的平衡,它具有全局最優(yōu)、適應性強、推廣能力強 等優(yōu)點。但是直到目前為止,支持向量機方法還存在一些問題，例如訓練時間 過長、核參數(shù)的選擇等，成為限制支持向量機應用的瓶頸。 支持向量機支持向量機 SVMSVM模型及優(yōu)缺點模型及優(yōu)缺點 集成學習集成學習 集成學習提出集成學習提出 集成學

18、習集成學習（Ensemble Learning）始于 Hansen 和 Salamon 的開創(chuàng)性工 作。他們研究發(fā)現(xiàn)，通過訓練多個神經網絡并將其結果按照一定的規(guī)則進行組 合，就能顯著提高整個學習系統(tǒng)的泛化性能。Schapire通過構造性方法提出 Boosting 算法，證明了這一點。 集成學習通過訓練和組合多個準確而有差異的分類器，提高了分類系統(tǒng) 的泛化能力，成為近十年來機器學習領域最主要的研究方向之一。目前，國內 外以神經網絡、決策樹等為基分類器的集成學習研究已經取得了很大的進展。 在分類時， 采用投票的 方式決定新 樣本屬于哪 一類。 集成學習示意圖集成學習示意圖 集成學習集成學習 由于每個分類 器的分類能力 不同，在集成 時，需要對所 有分類器加權 均，以決定分 哪類。 集成學習構造集成學習構造 集成學習集成學習 基分類器的構造方法基分類器的構造方法： 1）采用不同訓練樣本集 2）采用不同輸入特征子集 3）輸出編碼分解方法 4）引入隨機性 5）多種方法相結合 分類器的輸出信息可以分為抽象層、排序層和度量層三個層次。 基分類器的組合方法基分類器的組合方法