機器學習研究及最新進展

譚營教授北京大學智能科學系視覺與聽覺信息處理國家重點實驗室12/19/20221譚營機器學習研究及最新進展機器學習研究及最新進展譚營教授12/17/20221目錄機器學習的定義和任務機器學習的發展歷史機器學習的主要方法機器學習面臨的挑戰最新發展方向題目：機器學習研究及最新進展

12/19/20222譚營機器學習研究及最新進展目錄機器學習的定義和任務題目：機器學習研究及最新進展12/學習系統基本構成學習環節知識庫執行環節學習環節:感知環境，獲取知識常用的學習方法機械式學習指導式學習歸納式學習類比學習一個基于知識庫的智能系統環境12/19/20223譚營機器學習研究及最新進展學習系統基本構成學習環節知識庫執行環節學習環節:感知環境，機器學習的定義

通過經驗提高系統自身的性能的過程（系統自我改進）。機器學習的重要性:機器學習是人工智能的主要核心研究領域之一,也是現代智能系統的關鍵環節和瓶頸。很難想象:一個沒有學習功能的系統是能被稱為是具有智能的系統。12/19/20224譚營機器學習研究及最新進展機器學習的定義通過經驗提高系統自身的性能的過程12/1入侵檢測系統IDS：是否是入侵？是何種入侵？如何檢測？歷史數據：以往的正常訪問模式及其表現、以往的入侵模式及其表現……對當前訪問模式分類這是一個典型的機器學習問題常用技術：神經網絡，決策樹，支持向量機，貝葉斯分類器，k近鄰，聚類，序列分析，免疫網絡等……實例1：網絡安全問題12/19/20225譚營機器學習研究及最新進展入侵檢測系統IDS：如何檢測？這是一個典型的機器學習問題實例如何預測？氣象歷史數據：以往的各種氣象數據及其變化特點……對未來一周天氣的預報這是一個典型的機器學習問題常用技術：統計多參數模型，神經網絡，貝葉斯分類器，k近鄰，聚類……實例2：天氣預報12/19/20226譚營機器學習研究及最新進展如何預測？這是一個典型的機器學習問題實例2：天氣預報12/1實例3：搜索引擎Google的成功，使得Internet搜索引擎成為一個新興的產業出現有眾多專營搜索引擎的公司（例如百度等專門針對中文搜索），而且Microsoft等巨頭也開始投入巨資進行搜索引擎的研發機器學習技術正在支撐著各類搜索引擎（尤其是貝葉斯學習技術）Google掘到的第一桶金，來源于其創始人LarryPage和SergeyBrin提出的PageRank算法12/19/20227譚營機器學習研究及最新進展實例3：搜索引擎Google的成功，使得Internet搜索Application412/19/20228譚營機器學習研究及最新進展Application412/17/20228譚營機Application4AutomaticCarDriveClassofTasks: Learningtodriveonhighwaysfrom visionstereos.Knowledge: Imagesandsteeringcommandsrecorded whileobservingahumandriver.PerformanceModule:Accuracyinclassification12/19/20229譚營機器學習研究及最新進展Application4AutomaticCarDriApplication5Learningtoclassifyastronomicalstructures.galaxystarsFeatures:ColorSizeMassTemperatureLuminosityunkown12/19/202210譚營機器學習研究及最新進展Application5LearningtoclassApplication6ClassifyingAstronomicalObjectsClassofTasks: Learningtoclassifynewobjects.Knowledge: databaseofimageswithcorrect classification.PerformanceModule:Accuracyinclassification12/19/202211譚營機器學習研究及最新進展Application6ClassifyingAstroOtherApplicationsBio-TechnologyProteinFoldingPredictionMicro-arraygeneexpressionComputerSystemsPerformancePredictionBankingApplicationsCreditApplicationsFraudDetectionCharacterRecognition(USPostalService)WebApplicationsDocumentClassificationLearningUserPreferences12/19/202212譚營機器學習研究及最新進展OtherApplicationsBio-Techno機器學習的任務令W是這個給定世界的有限或無限所有對象的集合，由于觀察能力的限制，我們只能獲得這個世界的一個有限的子集QW，稱為樣本集。機器學習就是根據這個有限樣本集Q，推算這個世界的模型，使得其對這個世界為真。QWModel建模泛化12/19/202213譚營機器學習研究及最新進展機器學習的任務令W是這個給定世界的有限或無限所有對象的集合，機器學習的三要素（1）一致性假設：機器學習的條件。（2）樣本空間劃分：決定模型對樣本集合的有效性。（3）泛化能力：決定模型對世界的有效性。12/19/202214譚營機器學習研究及最新進展機器學習的三要素（1）一致性假設：機器學習的條件。12/17要素1：一致性假設假設世界W與樣本集Q具有某種相同的性質。原則上說，存在各種各樣的一致性假設。在統計意義下，一般假設：W與Q具有同分布。或，給定世界W的所有對象獨立同分布。12/19/202215譚營機器學習研究及最新進展要素1：一致性假設假設世界W與樣本集Q具有某種相同的性質。1要素2：對樣本空間的劃分樣本集合模型：將樣本集放到一個n維空間，尋找一個超平面(等價關系)，使得問題決定的不同對象被劃分在不相交的區域。12/19/202216譚營機器學習研究及最新進展要素2：對樣本空間的劃分樣本集合模型：將樣本集放到要素3：泛化能力通過機器學習方法，從給定有限樣本集合計算一個模型，泛化能力是這個模型對世界為真程度的指標。樣本1樣本2樣本3新樣本泛化值12/19/202217譚營機器學習研究及最新進展要素3：泛化能力通過機器學習方法，從給定有限樣本集合計算一關于三要素不同時期，研究的側重點不同劃分:早期研究主要集中在該要素上泛化能力(在多項式劃分):80年代以來的近期研究一致性假設:未來必須考慮12/19/202218譚營機器學習研究及最新進展關于三要素不同時期，研究的側重點不同12/17/202218機器學習是多學科交叉機器學習統計學人工智能哲學信息論生物學計算復雜性數學認知科學控制論其他學科應用領域12/19/202219譚營機器學習研究及最新進展機器學習是多學科交叉機器學習統計學人工智能哲學信息論生物學計THEQUESTIONS--TheTop25

>WhatIstheUniverseMadeOf?>WhatistheBiologicalBasisofConsciousness?>WhyDoHumansHaveSoFewGenes?>ToWhatExtentAreGeneticVariationandPersonalHealthLinked?>CantheLawsofPhysicsBeUnified?>HowMuchCanHumanLifeSpanBeExtended?>WhatControlsOrganRegeneration?>HowCanaSkinCellBecomeaNerveCell?>HowDoesaSingleSomaticCellBecomeaWholePlant?>HowDoesEarth'sInteriorWork?>AreWeAloneintheUniverse?>HowandWhereDidLifeonEarthArise?>WhatDeterminesSpeciesDiversity?>WhatGeneticChangesMadeUsUniquelyHuman?>HowAreMemoriesStoredandRetrieved?>HowDidCooperativeBehaviorEvolve?………./sciext/125th/

On25bigquestionsfacingscienceoverthenextquarter-century.(1July2005)12/19/202220譚營機器學習研究及最新進展THEQUESTIONS--TheTop25

>Wha記憶的模型與過程記憶的模型與過程通常包括三個相互聯系的階段：1、編碼（encoding），2、存儲（storage）3、提取（retrieval）記憶的模型12/19/202221譚營機器學習研究及最新進展記憶的模型與過程記憶的模型與過程通常包括三個相互聯系的階段：工作記憶（WorkingMemory）工作記憶系統能同時儲存和加工信息，這和短時記憶概念僅強調儲存功能是不同的。工作記憶分成：中樞執行系統、視空初步加工系統和語音環路。工作記憶與語言理解能力、注意力及推理能力等聯系緊密，工作記憶蘊藏智能的玄機。12/19/202222譚營機器學習研究及最新進展工作記憶（WorkingMemory）工作記憶系統能同時儲WorkingMemoryModel12/19/202223譚營機器學習研究及最新進展WorkingMemoryModel12/17/2022機器學習的分支數據挖掘：利用歷史數據來改進決策例如：醫學記錄——>醫學知識軟件應用（不能手工編程的應用）汽車自動駕駛語音識別等自用戶化程序新聞閱讀器學習用戶的閱讀興趣。返回

12/19/202224譚營機器學習研究及最新進展機器學習的分支數據挖掘：利用歷史數據來改進決策返回12/1機器學習早期研究Rosenblatt的感知機(1956)。Widrow的Madline(1960)。Samuel的符號機器學習(1965)。Minsky的“Perceptron”著作(1969，1988)。12/19/202225譚營機器學習研究及最新進展機器學習早期研究Rosenblatt的感知機(1956)。1PerceptronsDevisedbyFrankRosenblattinthelate1950sAsingle-layernetworkwhereallinputsandactivationvaluesareeither0or1,andtheweightsarerealvaluedActivationfunctionisasimplelinearthreshold1if∑xiwi>t0otherwiseSupervisedlearning,perceptronchangesweightsbasedoncorrectresultsIfoutputiscorrect,donothingIfoutputis0andshouldbe1,incrementweightsontheactivelines(inputof1)bysomeamountd.Ifoutputis1andshouldbe0,decrementweightsontheactivelinesbysomeamountd.12/19/202226譚營機器學習研究及最新進展PerceptronsDevisedbyFrankRoLimitsofPerceptronsSingle-layernetworksareonlycapableoflearningclassesthatarelinearlyseparableForexample,exclusive-orisnotlinearlyseparable,andthuscannotberepresentedbyaperceptronForanyn-dimensionalspace,aclassificationislinearlyseparableifthesegroupscanbeseparatedwithasinglen-1dimensionalhyperplaneYXXxorY=0XxorY=101112/19/202227譚營機器學習研究及最新進展LimitsofPerceptronsSingle-la二十世紀八十年代的研究符號機器學習取得進展。神經網絡的研究。計算學習理論PAC(概率近似正確)。12/19/202228譚營機器學習研究及最新進展二十世紀八十年代的研究符號機器學習取得進展。12/17/20兩類最重要的符號機器學習算法覆蓋算法與分治算法。七十年代末，Michalski基于帶等號的邏輯演算，提出了AQ11算法，稱為符號機器學習的覆蓋算法。1986年，Quinlan提出了決策樹算法，也稱為分治算法(樹結構表示的最早研究是CLS，概念學習系統)。12/19/202229譚營機器學習研究及最新進展兩類最重要的符號機器學習算法覆蓋算法與分治算法。12/17/神經網絡Hopfield模型。Kohonen模型。Goldberg的ART模型。……。最有影響的是Remulhart等人提出的BP算法(1986)。12/19/202230譚營機器學習研究及最新進展神經網絡Hopfield模型。12/17/202230譚營-計算學習理論1984年，Valiant提出機器學習應該以模型概率近似正確(1-)為指標，而不是以概率為1為指標。學習算法必須對樣本集合的規模呈多項式。統計機器學習、集成機器學習等方法的理論基礎。12/19/202231譚營機器學習研究及最新進展計算學習理論1984年，Valiant提出機器學習應該以模型機器學習學科1983年，R.S.Michalski等人撰寫《機器學習：通往人工智能的途徑》一書1986年，MachineLearning雜志創刊1997年以TomMitchell的經典教科書（McGrawHillPress，1997）中都沒有貫穿始終的基礎體系，只不個是不同方法和技術的羅列機器學習還非常年輕、很不成熟返回12/19/202232譚營機器學習研究及最新進展機器學習學科1983年，R.S.Michalski等人撰機器學習的主要方法傳統分類歸納機器學習解釋機器學習遺傳機器學習連接機器學習現代分類（1997年，Dietterich）符號機器學習。統計機器學習。集成機器學習。增強機器學習。12/19/202233譚營機器學習研究及最新進展機器學習的主要方法傳統分類12/17/202233譚營學習方法的傳統分類傳統上，大致可分為4類：歸納學習解釋學習遺傳學習連接學習

12/19/202234譚營機器學習研究及最新進展學習方法的傳統分類傳統上，大致可分為4類：12/17/202歸納學習是從某一概念的分類例子集出發歸納出一般的概念描述。這是目前研究得最多的學習方法，其學習目的是為了獲得新的概念、構造新的規則或發現新的理論。這種方法要求大量的訓練例，而且歸納性能受到描述語言、概念類型、信噪比、實例空間分布、歸納模式等的影響。包括：有變型(版本)空間、決策樹方法、AQ11算法，一階Horn子句等12/19/202235譚營機器學習研究及最新進展歸納學習是從某一概念的分類例子集出發歸納出一般的概念描述。1解釋學習解釋學習（分析學習）是從完善的領域理論出發演繹出有助于更有效地利用領域理論的規則。其學習目的是提高系統性能，而不是修改領域理論。它與歸納學習相反，只需要少量的訓練例，但要求有完善的領域理論，而且學習效果也與例子表示形式、學習方法（正例學習或反例學習）、概括程度等有關。

12/19/202236譚營機器學習研究及最新進展解釋學習解釋學習（分析學習）是從完善的領域理論出發演繹出有助遺傳學習是通過模擬自然界遺傳與變異機制，利用進化論的自然選擇原理進行分類和優化。優點：可以使一些用傳統的精確的符號方法無法解決的問題變得易解缺點：在學習過程中會產生大量數據，如何對這些數據進行挑選和記憶？

12/19/202237譚營機器學習研究及最新進展遺傳學習是通過模擬自然界遺傳與變異機制，利用進化論的自然選擇連接學習通過以某種形式連接的大量神經元根據訓練模式集調整連接和閾值進行學習，這種學習方式就是通常所說的人工神經網絡學習，也稱為“并行分布式學習”，其出發點是著名的M－P模型。該方法在50、60年代陷入沉寂，但在80年代解決TSP問題后得到復興(BP,HNN,etc.)。這得益于隱結點的使用使其突破了早期Perceptron的限制。優點：在模式識別、語音處理等許多方面已得到成功應用。缺點：難以處理高層次的符號信息，使得應用范圍受到了限制。返回12/19/202238譚營機器學習研究及最新進展連接學習通過以某種形式連接的大量神經元根據訓練模式集調整連接機器學習方法的現代分類1997年，Dietterich的分類符號機器學習統計機器學習集成機器學習增強機器學習返回12/19/202239譚營機器學習研究及最新進展機器學習方法的現代分類1997年，Dietterich的分類符號機器學習1959年Solomonoff關于文法歸納的研究應該是最早的符號機器學習。1967年Gold證明，這是不可能的實現的。Samuel將分段劃分引入對符號域的數據處理,形成了一類基于符號數據集合的約簡算法，這是現代符號機器學習的基礎。約簡：規則長度越短，覆蓋對象越多，但是，不能增加對象矛盾。12/19/202240譚營機器學習研究及最新進展符號機器學習1959年Solomonoff關于文法歸納的研究符號機器學習的基礎劃分機器學習的本質是對樣本空間的劃分。這需要定義一個等價關系，將樣本空間劃分為等價類。12/19/202241譚營機器學習研究及最新進展符號機器學習的基礎劃分機器學習的本質是對樣本空間的劃分符號機器學習的等價關系定義在給定符號對象集合U上的等價關系a{(x,y):a(x)=a(y),x,yU}12/19/202242譚營機器學習研究及最新進展符號機器學習的等價關系定義在給定符號對象集合U上的等價關系aRoughSet理論Pawlak在1982年提出的一種數學理論，包含了兩個方面的內容：基于roughness的不精確知識表示理論。Reduct理論與邊緣理論。可以證明：覆蓋算法和分治算法與Reduct理論等價。Reduct理論是符號機器學習的理論基礎。12/19/202243譚營機器學習研究及最新進展RoughSet理論Pawlak在1982年提出的一種數學Reduct理論的貢獻給出了在結構上“非最小”解的精確數學定義Reduct。Core的概念。根據上述兩個概念，引出邊緣區域的概念。12/19/202244譚營機器學習研究及最新進展Reduct理論的貢獻給出了在結構上“非最小”解的精確數學定Reduct是一個屬性集合，當從這個集合中刪除一個屬性，則至少出現一個新的矛盾樣本對。因此，它是在的不增加新矛盾對的最小屬性集合。rR,POSR(D)POSR-{r}(D)。12/19/202245譚營機器學習研究及最新進展Reduct是一個屬性集合，當從這個集合中刪除一個屬性，則至Core是一個屬性集合。如果刪除一個這樣的屬性，必然出現一個新的樣本矛盾對。反映了信息系統的本質。12/19/202246譚營機器學習研究及最新進展Core是一個屬性集合。12/17/202246譚營機邊緣區域邊緣區域是信息系統所有矛盾樣本的集合。如果C(x)=C(y)，但是，D(x)D(y)，x與y是樣本集合中的矛盾對。這為我們提供了研究矛盾信息結構的機會。12/19/202247譚營機器學習研究及最新進展邊緣區域邊緣區域是信息系統所有矛盾樣本的集合。12/17/2性質根據reduct可以建立一個新的信息系統，這個信息系統的所有屬性是core。這個性質對形成不同簡潔程度文本有重要的應用。12/19/202248譚營機器學習研究及最新進展性質根據reduct可以建立一個新的信息系統，這個信息系統的符號機器學習的限制算法定義在符號域，連續量必須被映射到這樣的域上，算法才有效學習算法本身無法刻畫泛化能力，而依賴于與算法本身無關的上述映射目前，它是數據分析與數據挖掘的基礎返回12/19/202249譚營機器學習研究及最新進展符號機器學習的限制算法定義在符號域，連續量必須被映射到這樣的統計機器學習算法的泛化能力Vapnik的有限樣本統計理論線性空間的學習算法(劃分)SVM12/19/202250譚營機器學習研究及最新進展統計機器學習算法的泛化能力12/17/202250譚營泛化誤差由于問題世界的統計分布未知(如果已知，無需機器學習,Vapnik)，解析地計算最小期望風險是不可能的。機器學習以最小經驗風險與期望風險之差為統計基礎，稱為泛化誤差。泛化能力以此進行估計。12/19/202251譚營機器學習研究及最新進展泛化誤差由于問題世界的統計分布未知(如果已知，無需機器學習,Duda(1973)Vapnik(1971)樣本集：樣本個數趨近無窮大有限樣本，樣本集內部結構(VC維)泛化關系：模型與泛化隨機選擇樣本集的隨機變量樣本集、模型與泛化泛化能力描述：以概率為1成立以概率1-成立泛化不等式：?(無法指導算法設計)最大邊緣(指導算法設計)泛化能力描述12/19/202252譚營機器學習研究及最新進展Duda(1973)Vapnik(1971)樣本集：樣本個數“泛化誤差界”研究的演變PAC界(Valiant[1984])VC維界(Blumer[1989])最大邊緣(Shawe-Taylor[1998])12/19/202253譚營機器學習研究及最新進展“泛化誤差界”研究的演變PAC界(Valiant[1984]最大邊緣(Shawe-Taylor[1998])M>0，邊緣不能等于零。這意味著，樣本集合必須是可劃分的。邊緣最大，誤差界最小，泛化能力最強。泛化能力可以使用樣本集合的邊緣刻畫。這個不等式依賴于邊緣M。貢獻：給出了有幾何直觀的界描述，從而為算法設計奠定基礎。12/19/202254譚營機器學習研究及最新進展最大邊緣(Shawe-Taylor[1998])M>0，邊緣研究趨勢算法的理論研究已經基本完成，目前主要集中在下述兩個問題上：泛化不等式需要樣本集滿足獨立同分布，這個條件太嚴厲，可以放寬這個條件？如何根據領域需求選擇核函數，有基本原則嗎？12/19/202255譚營機器學習研究及最新進展研究趨勢算法的理論研究已經基本完成，12/17/202255有限樣本統計理論的優點所需滿足的條件相對較少，盡管需要滿足獨立同分布，但無需考慮問題世界的先驗分布這意味著，這個理論可以僅以樣本集(數據)為基礎12/19/202256譚營機器學習研究及最新進展有限樣本統計理論的優點所需滿足的條件相對較少，盡管需要滿足獨要求“線性算法”的原因對計算，非線性算法一般是NP完全的。對世界認識，只有在某個空間可以描述為線性的世界，人們才能夠說，這個世界已被認識。12/19/202257譚營機器學習研究及最新進展要求“線性算法”的原因對計算，非線性算法一般是NP完全的。1非線性問題的數學方法尋找一個映射，將非線性問題映射到線性空間，以便其可以在線性空間中線性表述。例如，牛頓萬有引力定律：映射：線性表示：12/19/202258譚營機器學習研究及最新進展非線性問題的數學方法尋找一個映射，將非線性問題映射到線性空間在機器學習中的方法方法:尋找具有一般意義的線性空間目前，機器學習主要采用兩種方法：整體線性：Hilbert空間分段線性：在流形意義下的線性子空間12/19/202259譚營機器學習研究及最新進展在機器學習中的方法方法:尋找具有一般意義的線性空間12/17線性可分問題如果一個樣本集合是線性可分的，它們一定可以構成兩個不相交的閉凸集。這樣，線性可分問題變為計算兩個閉凸集的最大邊緣問題。12/19/202260譚營機器學習研究及最新進展線性可分問題如果一個樣本集合是線性可分的，它們一定可以構成兩線性不可分問題核函數可以證明，一定存在一個映射，稱為核函數，將在歐氏空間定義的樣本映射到特征空間(一個更高維的空間)，使得在特征空間上，樣本構成兩個不相交的閉凸集。12/19/202261譚營機器學習研究及最新進展線性不可分問題核函數可以證明，一定存在一個映射，稱為核SVM線性可分為基礎。給定核函數，如果它可以保證將樣本集合在特征空間變換為兩個不相交的閉凸集，則對這個樣本集合的最大邊緣可以通過二次規劃、代數幾何、計算幾何等方法獲得。由此，可以獲得支持向量。這就是SVM。12/19/202262譚營機器學習研究及最新進展SVM線性可分為基礎。12/17/202262譚營機器存在問題SVM只從存在上解決了劃分問題，并沒有真正在劃分上解決核函數的構造問題。泛化問題不僅需要解決劃分問題，還需要解決最大邊緣問題。這意味著，需要在滿足線性劃分的核函數中選擇一個滿足最大邊緣的核函數(模型選擇)。返回12/19/202263譚營機器學習研究及最新進展存在問題SVM只從存在上解決了劃分問題，并沒有真正在劃分上集成機器學習動機(Ensembles)在形式上與Madline類似，其泛化理論來自PAC的弱分類器理論。使用多個容易設計的簡單PAC弱分類器代替一個較難設計的PAC強分類器。12/19/202264譚營機器學習研究及最新進展集成機器學習動機(Ensembles)在形式上與Madlin研究背景[Valiant’84] introducedtheoreticalPACmodelforstudyingmachinelearning[Kearns&Valiant’88] openproblemoffindingaboostingalgorithm[Schapire’89],[Freund’90] firstpolynomial-timeboostingalgorithms[Drucker,Schapire&Simard’92] firstexperimentsusingboosting12/19/202265譚營機器學習研究及最新進展研究背景[Valiant’84]12/17/202265譚營背景(cont.)[Freund&Schapire’95]introducedAdaBoostalgorithmstrongpracticaladvantagesoverpreviousboostingalgorithmsexperimentsusingAdaBoost:[Drucker&Cortes’95] [Schapire&Singer’98][Jackson&Cravon’96] [Maclin&Opitz’97][Freund&Schapire’96] [Bauer&Kohavi’97][Quinlan’96] [Schwenk&Bengio’98][Breiman’96] [ Dietterich’98]continuingdevelopmentoftheory&algorithms:[Schapire,Freund,Bartlett&Lee’97][Schapire&Singer’98][Breiman’97] [Mason,Bartlett&Baxter’98][GriveandSchuurmans’98] [Friedman,Hastie&Tibshirani’98]……12/19/202266譚營機器學習研究及最新進展背景(cont.)[Freund&Schapire’95AFormalViewofBoostingGiventrainingset

X={(x1,y1),…,(xm,ym)}yi{-1,+1}correctlabelofinstancexiXfort=1,…,T:constructdistributionDton{1,…,m}Findweakhypothesis(“ruleofthumb”)

ht:X

{-1,+1}

withsmallerrortonDt:

outputfinalhypothesis

Hfinal12/19/202267譚營機器學習研究及最新進展AFormalViewofBoostingGiven集成機器學習1990年Shapire證明，如果將多個PAC弱分類器集成在一起，它將具有PAC強分類器的泛化能力。進而，又說明，這類集成后的強分類器具有統計學習理論的基礎。12/19/202268譚營機器學習研究及最新進展集成機器學習1990年Shapire證明，如果將多個PAC弱弱分類器如果一個分類器的分類能力(泛化)稍大于50%，這個分類器稱為弱分類器。這意味著，比擲硬幣猜正面的概率稍好，就是弱分類器。12/19/202269譚營機器學習研究及最新進展弱分類器如果一個分類器的分類能力(泛化)稍大于50%，這個分集成在分類時，采用投票的方式決定新樣本屬于哪一類。由于每個分類器的分類能力不同，在集成時，需要對所有分類器加權平均，以決定分哪類。12/19/202270譚營機器學習研究及最新進展集成在分類時，采用投票的方式決定新樣本屬于哪一類。12/17集成分類器ClassifierensembleΣαihihnh2h1InputvectorClassifier1Classifier2……ClassifierNCombineClassifiersOutput12/19/202271譚營機器學習研究及最新進展集成分類器ClassifierensembleΣαihih為什么吸引人弱分類器比強分類器設計簡單。有統計學習理論的基礎。典型方法：加權多數算法，Bootstrap,ADABOOST等。返回12/19/202272譚營機器學習研究及最新進展為什么吸引人弱分類器比強分類器設計簡單。返回12/17/20AdaBoost[Freund&Schapire’97]constructingDt:

givenDtandht: where:Zt=normalizationconstantfinalhypothesis:返回12/19/202273譚營機器學習研究及最新進展AdaBoost[Freund&Schapire’97]增強機器學習增強機器學習最早提出是考慮“從變化環境中”學習蘊含在環境中知識，其本質是對環境的適應開始的動機主要是為了解決機器人規劃、避障與在環境中適應的學習問題1975年，Holland首先將這個概念引入計算機科學。1990年左右，MIT的Sutton等青年計算機科學家，結合動態規劃等問題，統稱其為增強機器學習12/19/202274譚營機器學習研究及最新進展增強機器學習增強機器學習最早提出是考慮“從變化環境中”學習蘊目前，由于網絡用戶是更為復雜的環境，例如，如何使搜索引擎適應用戶的需求，成為更為重要的應用領域Q學習，動態規劃，遺傳學習，以及免疫網絡都成為實現增強機器學習的有效方法。返回12/19/202275譚營機器學習研究及最新進展目前，由于網絡用戶是更為復雜的環境，例如，如何使搜索引擎適應機器學習面臨的挑戰隨著應用的不斷深入,出現了很多被傳統機器學習研究忽視、但非常重要的問題（下面將以醫療和金融為代表來舉幾個例子）機器學習正與眾多學科領域產生了交叉，交叉領域越多,問題也越多,也正是大有可為處12/19/202276譚營機器學習研究及最新進展機器學習面臨的挑戰隨著應用的不斷深入,出現了很多被傳統機器學醫療：以癌癥診斷為例，“將病人誤診為健康人的代價”與“將健康人誤診為病人的代價”是不同的金融：以信用卡盜用檢測為例，“將盜用誤認為正常使用的代價”與“將正常使用誤認為盜用的代價”是不同的傳統的ML技術基本上只考慮同一代價如何處理代價敏感性？在教科書中找不到現成的答案。例子1：代價敏感問題12/19/202277譚營機器學習研究及最新進展醫療：以癌癥診斷為例，“將病人誤診為健康人的代價”與“將健康醫療：以癌癥診斷為例，“健康人”樣本遠遠多于“病人”樣本金融：以信用卡盜用檢測為例，“正常使用”樣本遠遠多于“被盜用”樣本傳統的ML技術基本上只考慮平衡數據如何處理數據不平衡性？在教科書中找不到現成的答案例子2：不平衡數據問題12/19/202278譚營機器學習研究及最新進展醫療：以癌癥診斷為例，“健康人”樣本遠遠多于“病人”樣本例子醫療：以乳腺癌診斷為例，需要向病人解釋“為什么做出這樣的診斷”金融：以信用卡盜用檢測為例，需要向保安部門解釋“為什么這是正在被盜用的卡”傳統的ML技術基本上只考慮泛化不考慮理解如何處理可理解性？在教科書中找不到現成的答案例子3：可理解性問題返回12/19/202279譚營機器學習研究及最新進展醫療：以乳腺癌診斷為例，需要向病人解釋“為什么做出這樣的診斷機器學習的最新進展算法驅動(建模與數據分析)應用驅動12/19/202280譚營機器學習研究及最新進展機器學習的最新進展算法驅動(建模與數據分析)12/17/20算法驅動海量非線性數據(108-10)算法的泛化能力考慮學習結果數據的解釋代價加權的處理方法不同數據類型的學習方法返回12/19/202281譚營機器學習研究及最新進展算法驅動海量非線性數據(108-10)返回12/17/202應用驅動自然語言分析、、網絡與電信數據分析、圖像數據分析、金融與經濟數據分析、零售業數據分析、情報分析。Web信息的有效獲取(新一代搜索引擎)。由此導致各種學習任務：數據流學習、多實例學習(部分放棄獨立同分布條件)、Ranking學習。蛋白質功能分析,DNA數據分析,SNP數據分析…….

它們需要使用各種不同方法，解決實際問題。12/19/202282譚營機器學習研究及最新進展應用驅動自然語言分析、、網絡與電信數據分析、圖像數據分析、金應用驅動機器學習流形機器學習半監督機器學習多實例機器學習Ranking機器學習數據流機器學習圖模型機器學習……結束語12/19/202283譚營機器學習研究及最新進展應用驅動機器學習流形機器學習結束語12/17/202283譚流形機器學習很多問題的表示方法，使得信息十分稀疏，如何將信息稠密化是一個困難的問題（“維數災難”），PCA是一種方法，但是，只對線性情況有效流形學習是解決上述問題的非線性方法12/19/202284譚營機器學習研究及最新進展流形機器學習很多問題的表示方法，使得信息十分稀疏，如何將信息高微數據的低微表示線性方法PCA(PrincipalComponentAnalysis)ICA(IndependentComponentAnalysis)FDA(FisherDiscriminationAnalysis)MDS(Multi-DimScaleanalysis)非線性方法LLE(LocallinearEmbeding)(Roweis,Science,2000)Isomap(Tenenbaum,Science,2000)由于流形的本質是分段線性化，因此，流形學習需要解決計算開集、設計同胚映射等問題12/19/202285譚營機器學習研究及最新進展高微數據的低微表示線性方法由于流形的本質是分段線性化，因此，半監督機器學習在觀測數據中，可能有很多觀測不能決定其類別標號。這需要根據數據中已知類別標號的樣本與領域知識來推測這些樣本的類別標號，并建立問題世界的模型，這就是半監督學習這類問題直接來自于實際應用：例如，大量醫學影像，醫生把每張片子上的每個病灶都標出來再進行學習，是不可能的，能否只標一部分，并且還能利用未標的部分？12/19/202286譚營機器學習研究及最新進展半監督機器學習在觀測數據中，可能有很多觀測不能決定其類別標號多示例機器學習傳統的機器學習中，一個對象有一個描述，而在一些實際問題中，一個對象可能同時有多個描述，到底哪個描述是決定對象性質(例如類別)的，卻并不知道。解決這種“對象：描述：類別”之間1:N:1關系的學習就是多示例學習12/19/202287譚營機器學習研究及最新進展多示例機器學習傳統的機器學習中，一個對象有一個描述，而在一些Ranking機器學習其原始說法是learningforranking問題主要來自信息檢索，假設用戶的需求不能簡單地表示為“喜歡”或“不喜歡”，而需要將“喜歡”表示為一個順序，問題是如何通過學習，獲得關于這個“喜歡”順序的模型。12/19/202288譚營機器學習研究及最新進展Ranking機器學習其原始說法是learningfor數據流機器學習在網絡數據分析與處理中，有一類問題，從一個用戶節點上流過的數據，大多數是無意義的，由于數據量極大，不能全部存儲，因此，只能簡單判斷流過的文件是否有用，而無法細致分析如何學習一個模型可以完成這個任務，同時可以增量學習，以保證可以從數據流中不斷改善(或適應)用戶需求的模型12/19/202289譚營機器學習研究及最新進展數據流機器學習在網絡數據分析與處理中，有一類問題，從一個用戶研究現狀主要以任務為驅動力,學習方法有待創新以上這些機器學習方式還處于實驗觀察階段，缺乏堅實的理論基礎實際應用效果仍有待研究12/19/202290譚營機器學習研究及最新進展研究現狀主要以任務為驅動力,學習方法有待創新12/17/20存在的理論問題統計類機器學習需要滿足獨立同分布條件，嚴厲！尋找問題線性表示的空間，沒有一般的原則。信息向符號的映射，沒有好的方法。機器學習沒有一勞永逸的解決方案。領域知識與數據分析不可避免。12/19/202291譚營機器學習研究及最新進展存在的理論問題統計類機器學習需要滿足獨立同分布條件，嚴厲！1研究趨勢盡管“學習機制”還是研究的動力，然而，“煩惱網絡”的危機，使得更為重要的推動力來自“有效利用”信息。傳統領域借用機器學習提高研究水平。應用驅動的機器學習方法層出不窮。基于機器學習的數據分析方法成為解決復雜問題的關鍵之一。12/19/202292譚營機器學習研究及最新進展研究趨勢盡管“學習機制”還是研究的動力，然而，“煩惱網絡”結束語當前，機器學習所面臨情況是：

數據復雜、海量，用戶需求多樣化。從而,要求：需要科學和高效的問題表示，以便將其學習建立在科學的基礎上應用驅動成為必然,從而針對某個或某類應用給出特定的學習方法將不斷涌現對機器學習的檢驗問題只能在應用中檢驗自己對機器學習的結果的解釋,將逐漸受到重視12/19/202293譚營機器學習研究及最新進展結束語當前，機器學習所面臨情況是：12/17/202293譚謝謝!返回12/19/202294譚營機器學習研究及最新進展謝謝!返回12/17/202294譚營機器學習研究及最機器學習研究及最新進展

譚營教授北京大學智能科學系視覺與聽覺信息處理國家重點實驗室12/19/202295譚營機器學習研究及最新進展機器學習研究及最新進展譚營教授12/17/20221目錄機器學習的定義和任務機器學習的發展歷史機器學習的主要方法機器學習面臨的挑戰最新發展方向題目：機器學習研究及最新進展

12/19/202296譚營機器學習研究及最新進展目錄機器學習的定義和任務題目：機器學習研究及最新進展12/學習系統基本構成學習環節知識庫執行環節學習環節:感知環境，獲取知識常用的學習方法機械式學習指導式學習歸納式學習類比學習一個基于知識庫的智能系統環境12/19/202297譚營機器學習研究及最新進展學習系統基本構成學習環節知識庫執行環節學習環節:感知環境，機器學習的定義

通過經驗提高系統自身的性能的過程（系統自我改進）。機器學習的重要性:機器學習是人工智能的主要核心研究領域之一,也是現代智能系統的關鍵環節和瓶頸。很難想象:一個沒有學習功能的系統是能被稱為是具有智能的系統。12/19/202298譚營機器學習研究及最新進展機器學習的定義通過經驗提高系統自身的性能的過程12/1入侵檢測系統IDS：是否是入侵？是何種入侵？如何檢測？歷史數據：以往的正常訪問模式及其表現、以往的入侵模式及其表現……對當前訪問模式分類這是一個典型的機器學習問題常用技術：神經網絡，決策樹，支持向量機，貝葉斯分類器，k近鄰，聚類，序列分析，免疫網絡等……實例1：網絡安全問題12/19/202299譚營機器學習研究及最新進展入侵檢測系統IDS：如何檢測？這是一個典型的機器學習問題實例如何預測？氣象歷史數據：以往的各種氣象數據及其變化特點……對未來一周天氣的預報這是一個典型的機器學習問題常用技術：統計多參數模型，神經網絡，貝葉斯分類器，k近鄰，聚類……實例2：天氣預報12/19/2022100譚營機器學習研究及最新進展如何預測？這是一個典型的機器學習問題實例2：天氣預報12/1實例3：搜索引擎Google的成功，使得Internet搜索引擎成為一個新興的產業出現有眾多專營搜索引擎的公司（例如百度等專門針對中文搜索），而且Microsoft等巨頭也開始投入巨資進行搜索引擎的研發機器學習技術正在支撐著各類搜索引擎（尤其是貝葉斯學習技術）Google掘到的第一桶金，來源于其創始人LarryPage和SergeyBrin提出的PageRank算法12/19/2022101譚營機器學習研究及最新進展實例3：搜索引擎Google的成功，使得Internet搜索Application412/19/2022102譚營機器學習研究及最新進展Application412/17/20228譚營機Application4AutomaticCarDriveClassofTasks: Learningtodriveonhighwaysfrom visionstereos.Knowledge: Imagesandsteeringcommandsrecorded whileobservingahumandriver.PerformanceModule:Accuracyinclassification12/19/2022103譚營機器學習研究及最新進展Application4AutomaticCarDriApplication5Learningtoclassifyastronomicalstructures.galaxystarsFeatures:ColorSizeMassTemperatureLuminosityunkown12/19/2022104譚營機器學習研究及最新進展Application5LearningtoclassApplication6ClassifyingAstronomicalObjectsClassofTasks: Learningtoclassifynewobjects.Knowledge: databaseofimageswithcorrect classification.PerformanceModule:Accuracyinclassification12/19/2022105譚營機器學習研究及最新進展Application6ClassifyingAstroOtherApplicationsBio-TechnologyProteinFoldingPredictionMicro-arraygeneexpressionComputerSystemsPerformancePredictionBankingApplicationsCreditApplicationsFraudDetectionCharacterRecognition(USPostalService)WebApplicationsDocumentClassificationLearningUserPreferences12/19/2022106譚營機器學習研究及最新進展OtherApplicationsBio-Techno機器學習的任務令W是這個給定世界的有限或無限所有對象的集合，由于觀察能力的限制，我們只能獲得這個世界的一個有限的子集QW，稱為樣本集。機器學習就是根據這個有限樣本集Q，推算這個世界的模型，使得其對這個世界為真。QWModel建模泛化12/19/2022107譚營機器學習研究及最新進展機器學習的任務令W是這個給定世界的有限或無限所有對象的集合，機器學習的三要素（1）一致性假設：機器學習的條件。（2）樣本空間劃分：決定模型對樣本集合的有效性。（3）泛化能力：決定模型對世界的有效性。12/19/2022108譚營機器學習研究及最新進展機器學習的三要素（1）一致性假設：機器學習的條件。12/17要素1：一致性假設假設世界W與樣本集Q具有某種相同的性質。原則上說，存在各種各樣的一致性假設。在統計意義下，一般假設：W與Q具有同分布。或，給定世界W的所有對象獨立同分布。12/19/2022109譚營機器學習研究及最新進展要素1：一致性假設假設世界W與樣本集Q具有某種相同的性質。1要素2：對樣本空間的劃分樣本集合模型：將樣本集放到一個n維空間，尋找一個超平面(等價關系)，使得問題決定的不同對象被劃分在不相交的區域。12/19/2022110譚營機器學習研究及最新進展要素2：對樣本空間的劃分樣本集合模型：將樣本集放到要素3：泛化能力通過機器學習方法，從給定有限樣本集合計算一個模型，泛化能力是這個模型對世界為真程度的指標。樣本1樣本2樣本3新樣本泛化值12/19/2022111譚營機器學習研究及最新進展要素3：泛化能力通過機器學習方法，從給定有限樣本集合計算一關于三要素不同時期，研究的側重點不同劃分:早期研究主要集中在該要素上泛化能力(在多項式劃分):80年代以來的近期研究一致性假設:未來必須考慮12/19/2022112譚營機器學習研究及最新進展關于三要素不同時期，研究的側重點不同12/17/202218機器學習是多學科交叉機器學習統計學人工智能哲學信息論生物學計算復雜性數學認知科學控制論其他學科應用領域12/19/2022113譚營機器學習研究及最新進展機器學習是多學科交叉機器學習統計學人工智能哲學信息論生物學計THEQUESTIONS--TheTop25

>WhatIstheUniverseMadeOf?>WhatistheBiologicalBasisofConsciousness?>WhyDoHumansHaveSoFewGenes?>ToWhatExtentAreGeneticVariationandPersonalHealthLinked?>CantheLawsofPhysicsBeUnified?>HowMuchCanHumanLifeSpanBeExtended?>WhatControlsOrganRegeneration?>HowCanaSkinCellBecomeaNerveCell?>HowDoesaSingleSomaticCellBecomeaWholePlant?>HowDoesEarth'sInteriorWork?>AreWeAloneintheUniverse?>HowandWhereDidLifeonEarthArise?>WhatDeterminesSpeciesDiversity?>WhatGeneticChangesMadeUsUniquelyHuman?>HowAreMemoriesStoredandRetrieved?>HowDidCooperativeBehaviorEvolve?………./sciext/125th/

On25bigquestionsfacingscienceoverthenextquarter-century.(1July2005)12/19/2022114譚營機器學習研究及最新進展THEQUESTIONS--TheTop25

>Wha記憶的模型與過程記憶的模型與過程通常包括三個相互聯系的階段：1、編碼（encoding），2、存儲（storage）3、提取（retrieval）記憶的模型12/19/2022115譚營機器學習研究及最新進展記憶的模型與過程記憶的模型與過程通常包括三個相互聯系的階段：工作記憶（WorkingMemory）工作記憶系統能同時儲存和加工信息，這和短時記憶概念僅強調儲存功能是不同的。工作記憶分成：中樞執行系統、視空初步加工系統和語音環路。工作記憶與語言理解能力、注意力及推理能力等聯系緊密，工作記憶蘊藏智能的玄機。12/19/2022116譚營機器學習研究及最新進展工作記憶（WorkingMemory）工作記憶系統能同時儲WorkingMemoryModel12/19/2022117譚營機器學習研究及最新進展WorkingMemoryModel12/17/2022機器學習的分支數據挖掘：利用歷史數據來改進決策例如：醫學記錄——>醫學知識軟件應用（不能手工編程的應用）汽車自動駕駛語音識別等自用戶化程序新聞閱讀器學習用戶的閱讀興趣。返回

12/19/2022118譚營機器學習研究及最新進展機器學習的分支數據挖掘：利用歷史數據來改進決策返回12/1機器學習早期研究Rosenblatt的感知機(1956)。Widrow的Madline(1960)。Samuel的符號機器學習(1965)。Minsky的“Perceptron”著作(1969，1988)。12/19/2022119譚營機器學習研究及最新進展機器學習早期研究Rosenblatt的感知機(1956)。1PerceptronsDevisedbyFrankRosenblattinthelate1950sAsingle-layernetworkwhereallinputsandactivationvaluesareeither0or1,andtheweightsarerealvaluedActivationfunctionisasimplelinearthreshold1if∑xiwi>t0otherwiseSupervisedlearning,perceptronchangesweightsbasedoncorrectresultsIfoutputiscorrect,donothingIfoutputis0andshouldbe1,incrementweightsontheactivelines(inputof1)bysomeamountd.Ifoutputis1andshouldbe0,decrementweightsontheactivelinesbysomeamountd.12/19/2022120譚營機器學習研究及最新進展PerceptronsDevisedbyFrankRoLimitsofPerceptronsSingle-layernetworksareonlycapableoflearningclassesthatarelinearlyseparableForexample,exclusive-orisnotlinearlyseparable,andthuscannotberepresentedbyaperceptronForanyn-dimensionalspace,aclassificationislinearlyseparableifthesegroupscanbeseparatedwithasinglen-1dimensionalhyperplaneYXXxorY=0XxorY=101112/19/2022121譚營機器學習研究及最新進展LimitsofPerceptronsSingle-la二十世紀八十年代的研究符號機器學習取得進展。神經網絡的研究。計算學習理論PAC(概率近似正確)。12/19/2022122譚營機器學習研究及最新進展二十世紀八十年代的研究符號機器學習取得進展。12/17/20兩類最重要的符號機器學習算法覆蓋算法與分治算法。七十年代末，Michalski基于帶等號的邏輯演算，提出了AQ11算法，稱為符號機器學習的覆蓋算法。1986年，Quinlan提出了決策樹算法，也稱為分治算法(樹結構表示的最早研究是CLS，概念學習系統)。12/19/2022123譚營機器學習研究及最新進展兩類最重要的符號機器學習算法覆蓋算法與分治算法。12/17/神經網絡Hopfield模型。Kohonen模型。Goldberg的ART模型。……。最有影響的是Remulhart等人提出的BP算法(1986)。12/19/2022124譚營機器學習研究及最新進展神經網絡Hopfield模型。12/17/202230譚營-計算學習理論1984年，Valiant提出機器學習應該以模型概率近似正確(1-)為指標，而不是以概率為1為指標。學習算法必須對樣本集合的規模呈多項式。統計機器學習、集成機器學習等方法的理論基礎。12/19/2022125譚營機器學習研究及最新進展計算學習理論1984年，Valiant提出機器學習應該以模型機器學習學科1983年，R.S.Michalski等人撰寫《機器學習：通往人工智能的途徑》一書1986年，MachineLearning雜志創刊1997年以TomMitchell的經典教科書（McGrawHillPress，1997）中都沒有貫穿始終的基礎體系，只不個是不同方法和技術的羅列機器學習還非常年輕、很不成熟返回12/19/2022126譚營機器學習研究及最新進展機器學習學科1983年，R.S.Michalski等人撰機器學習的主要方法傳統分類歸納機器學習解釋機器學習遺傳機器學習連接機器學習現代分類（1997年，Dietterich）符號機器學習。統計機器學習。集成機器學習。增強機器學習。12/19/2022127譚營機器學習研究及最新進展機器學習的主要方法傳統分類12/17/202233譚營學習方法的傳統分類傳統上，大致可分為4類：歸納學習解釋學習遺傳學習連接學習

12/19/2022128譚營機器學習研究及最新進展學習方法的傳統分類傳統上，大致可分為4類：12/17/202歸納學習是從某一概念的分類例子集出發歸納出一般的概念描述。這是目前研究得最多的學習方法，其學習目的是為了獲得新的概念、構造新的規則或發現新的理論。這種方法要求大量的訓練例，而且歸納性能受到描述語言、概念類型、信噪比、實例空間分布、歸納模式等的影響。包括：有變型(版本)空間、決策樹方法、AQ11算法，一階Horn子句等12/19/2022129譚營機器學習研究及最新進展歸納學習是從某一概念的分類例子集出發歸納出一般的概念描述。1解釋學習解釋學習（分析學習）是從完善的領域理論出發演繹出有助于更有效地利用領域理論的規則。其學習目的是提高系統性能，而不是修改領域理論。它與歸納學習相反，只需要少量的訓練例，但要求有完善的領域理論，而且學習效果也與例子表示形式、學習方法（正例學習或反例學習）、概括程度等有關。

12/19/2022130譚營機器學習研究及最新進展解釋學習解釋學習（分析學習）是從完善的領域理論出發演繹出有助遺傳學習是通過模擬自然界遺傳與變異機制，利用進化論的自然選擇原理進行分類和優化。優點：可以使一些用傳統的精確的符號方法無法解決的問題變得易解缺點：在學習過程中會產生大量數據，如何對這些數據進行挑選和記憶？

12/19/2022131譚營機器學習研究及最新進展遺傳學習是通過模擬自然界遺傳與變異機制，利用進化論的自然選擇連接學習通過以某種形式連接的大量神經元根據訓練模式集調整連接和閾值進行學習，這種學習方式就是通常所說的人工神經網絡學習，也稱為“并行分布式學習”，其出發點是著名的M－P模型。該方法在50、60年代陷入沉寂，但在80年代解決TSP問題后得到復興(BP,HNN,etc.)。這得益于隱結點的使用使其突破了早期Perceptron的限制。優點：在模式識別、語音處理等許多方面已得到成功應用。缺點：難以處理高層次的符號信息，使得應用范圍受到了限制。返回12/19/2022132譚營機器學習研究及最新進展連接學習通過以某種形式連接的大量神經元根據訓練模式集調整連接機器學習方法的現代分類1997年，Dietterich的分類符號機器學習統計機器學習集成機器學習增強機器學習返回12/19/2022133譚營機器學習研究及最新進展機器學習方法的現代分類1997年，Dietterich的分類符號機器學習1959年Solomonoff關于文法歸納的研究應該是最早的符號機器學習。1967年Gold證明，這是不可能的實現的。Samuel將分段劃分引入對符號域的數據處理,形成了一類基于符號數據集合的約簡算法，這是現代符號機器學習的基礎。約簡：規則長度越短，覆蓋對象越多，但是，不能增加對象矛盾。12/19/2022134譚營機器學習研究及最新進展符號機器學習1959年Solomonoff關于文法歸納的研究符號機器學習的基礎劃分機器學習的本質是對樣本空間的劃分。這需要定義一個等價關系，將樣本空間劃分為等價類。12/19/2022135譚營機器學習研究及最新進展符號機器學習的基礎劃分機器學習的本質是對樣本空間的劃分符號機器學習的等價關系定義在給定符號對象集合U上的等價關系a{(x,y):a(x)=a(y),x,yU}12/19/2022136譚營機器學習研究及最新進展符號機器學習的等價關系定義在給定符號對象集合U上的等價關系aRoughSet理論Pawlak在1982年提出的一種數學理論，包含了兩個方面的內容：基于roughness的不精確知識表示理論。Reduct理論與邊緣理論。可以證明：覆蓋算法和分治算法與Reduct理論等價。Reduct理論是符號機器學習的理論基礎。12/19/2022137譚營機器學習研究及最新進展RoughSet理論Pawlak在1982年提出的一種數學Reduct理論的貢獻給出了在結構上“非最小”解的精確數學定義Reduct。Core的概念。根據上述兩個概念，引出邊緣區域的概念。12/19/2022138譚營機器學習研究及最新進展Reduct理論的貢獻給出了在結構上“非最小”解的精確數學定Reduct是一個屬性集合，當從這個集合中刪除一個屬性，則至少出現一個新的矛盾樣本對。