人工智能课件

緒論1.1什麼是人工智慧？1.1.1人工智慧的定義從學科方面定義：人工智慧是電腦科學中涉及研究、設計和應用智能機器的一個分支。其近期目標在於研究用機器來模仿和執行人腦的某些智力功能，並開發相關理論和技術。從能力方面定義：人工智慧是智能機器所執行的通常與人類智能有關的智能行為，如判斷、推理、證明、識別、感知、理解、設計、思考、規劃、學習和問題求解等思維活動。

1.1.2如何衡量機器是否具有智能？圖靈測試1.1.3人工智慧的起源與發展孕育時期（1956年前）形成時期（1956年~1969年）1956年夏季，人類歷史上第一次人工智慧研討會在美國的達特茅斯(Dartmouth)大學舉行，標誌著人工智慧學科的誕生。

1969年召開了第一屆國際人工智慧聯合會議(InternationalJointConferenceonAI,IJCAI)，此後每兩年召開一次。發展時期（1969~）

1970年《人工智慧》國際雜誌(InternationalJournalofAI)創刊。這些對開展人工智慧國際學術活動和交流、促進人工智慧的研究和發展起到積極作用。20世紀70～80年代，知識工程的提出與專家系統的成功應用，確定了知識在人工智慧中的地位。1.2人類智能與人工智慧思維策略初級資訊處理生理過程電腦程式電腦語言電腦硬體圖1.1人類認知活動與電腦的比較一個完善的符號系統應具有下列6種基本功能：(1)輸入符號(input)；(2)輸出符號(output);(3)存儲符號(store);(4)複製符號(copy);(5)建立符號結構；(6)條件性遷移(conditionaltransfer）。物理符號系統假設：任何一個系統，如果它能表現出智能，那麼它就必定能夠執行上述6種功能。反之，任何系統如果具有這6種功能，那麼它就能夠表現出智能；這種智能指的是人類所具有的那種智能。把這個假設稱為物理符號系統的假設推論一：既然人具有智能，那麼他(她)就一定是個物理符號系統。人之所以能夠表現出智能，就是基於他的資訊處理過程。

推論二：既然電腦是一個物理符號系統，它就一定能夠表現出智能。這是人工智慧的基本條件。

推論三：既然人是一個物理符號系統，電腦也是一個物理符號系統，那麼就能夠用電腦來模擬人的活動。1.3人工智慧的主要學派符號主義連接主義行為主義符號主義，又稱邏輯主義、心理學派或電腦學派，其原理主要為物理符號系統（即符號操作系統）假設和有限合理性原理。符號主義認為人工智慧起源於數理邏輯。連接主義，又稱仿生學派或生理學派，其原理主要為神經網路及神經網路間的連接機制和學習演算法。連接主義認為人工智慧源於仿生學，特別是對人腦模型的研究。行為主義，又稱為進化主義或控制論學派，其原理為控制論及感知-動作型控制系統。行為主義認為人工智慧源於控制論。1.4人工智慧的研究和應用領域

問題求解

人工智慧的第一個大成就是發展了能夠求解難題的下棋(如國際象棋)程式，它包含問題的表示、分解、搜索與歸約等。邏輯推理與定理證明

邏輯推理是人工智慧研究中最持久的子領域之一，特別重要的是要找到一些方法，只把注意力集中在一個大型資料庫中的有關事實上，留意可信的證明，並在出現新資訊時適時修正這些證明。自然語言理解

語言處理也是人工智慧的早期研究領域之一，並引起了進一步的重視。語言的生成和理解是一個極為複雜的編碼和解碼問題。自動程式設計

對自動程式設計的研究不僅可以促進半自動軟體開發系統的發展，而且也使通過修正自身數碼進行學習(即修正它們的性能)的人工智慧系統得到發展。程式理論方面的有關研究工作對人工智慧的所有研究工作都是很重要的。專家系統

一般地說，專家系統是一個智能電腦程式系統，其內部具有大量專家水準的某個領域知識與經驗，能夠利用人類專家的知識和解決問題的方法來解決該領域的問題。發展專家系統的關鍵是表達和運用專家知識，即來自人類專家的並已被證明對解決有關領域內的典型問題是有用的事實和過程。

機器學習

學習是人類智能的主要標誌和獲得知識的基本手段；機器學習(自動獲取新的事實及新的推理演算法)是使電腦具有智能的根本途徑；機器學習還有助於發現人類學習的機理和揭示人腦的奧秘。學習是一個有特定目的的知識獲取過程，其內部表現為新知識結構的不斷建立和修改，而外部表現為性能的改善。神經網路研究結果已經證明，神經網路處理直覺和形象思維資訊具有比傳統處理方式好得多的效果。機器人學

人工智慧研究日益受到重視的另一個分支是機器人學，其中包括對操作機器人裝置程式的研究。這個領域所研究的問題，從機器人手臂的最佳移動到實現機器人目標的動作序列的規劃方法，無所不包。目前已經建立了一些比較複雜的機器人系統。模式識別人工智慧所研究的模式識別是指用電腦代替人類或幫助人類感知模式，是對人類感知外界功能的模擬，研究的是電腦模式識別系統，也就是使一個電腦系統具有模擬人類通過感官接受外界資訊、識別和理解周圍環境的感知能力。機器視覺

智能控制

人工智慧的發展促進自動控制向智能控制發展。智能控制是一類無需(或需要盡可能少的)人的干預就能夠獨立地驅動智能機器實現其目標的自動控制。智能檢索

隨著科學技術的迅速發展，出現了“知識爆炸”的情況，研究智能檢索系統已成為科技持續快速發展的重要保證。

智能調度與指揮

確定最佳調度或組合的問題是人們感興趣的又一類問題計算智能與進化計算

計算智能涉及神經計算、模糊計算、進化計算等研究領域。進化計算是指一類以達爾文進化論為依據來設計、控制和優化人工系統的技術和方法的總稱，它包括遺傳演算法、進化策略和進化規劃。除了以上的一些應用外還包括分佈式人工智慧與Agent、數據挖掘與知識發現、人工生命、系統與語言工具。辯論主題：人工智慧能否超過人類智能？

正方觀點：人工智慧不會超過人類智能。

反方觀點：人工智慧能夠超過人類智能。

搜索推理技術

搜索是人工智慧中的一個基本問題，它與推理密切相關，一個智能系統搜索策略的優劣，將直接影響到該系統的性能與推理效率。

所謂搜索，就是為了達到某一“目標”而連續地進行推理的過程。搜索技術就是對推理進行引導和控制的技術，它也是人工智慧的基本技術之一。事實上，許多的人工智慧的過程，甚至所有的智能活動的過程，都可以看作或抽象為一個“問題求解”過程，所謂的“問題求解”過程，實質上就是在顯式的或隱式的問題空間中進行搜索的過程。3.1搜索的基本概念3.1.1什麼是搜索3.1.2搜索的類型

狀態空間搜索是指用狀態空間法來求解問題所進行的搜索。

與／或樹搜索是指用問題歸約法來求解問題時所進行的搜索。狀態空間法和問題歸約法是人工智慧中最基本的兩種問題求解方法；狀態空間表示法和與／或樹表示法則是人工智慧中最基本的兩種問題表示方法。一、按問題的表示方式狀態空間搜索與/或圖搜索3.1.2搜索的類型

盲目搜索是按預定的控制策略進行搜索，在搜索過程中獲得的中間資訊並不改變控制策略。由於搜索總是按預先規定的路線進行，沒有考慮到問題本身的特性，因此這種搜索具有盲目性。

啟發式搜索是搜索過程中加入與問題有關的啟發性資訊，用於指導搜索朝著最有希望的方向前進，加速問題的求解過程並找到最優解。二、按是否使用啟發式資訊分類1.盲目搜索2.啟發式搜索

狀態空間的搜索策略可分為：盲目搜索和啟發式搜索兩大類。儘管盲目搜索的性能不如啟發式搜索，但由於啟發式搜索需要抽取與問題本身有關的特徵資訊，而這種特徵資訊的抽取往往又比較困難，因此盲目搜索仍不失為一種有用的搜索策略。3.2狀態空間搜索

當用狀態空間法解決問題時，有以下兩個方面的因素需要考慮：對於很大的問題，電腦無法保存其全部狀態空間對於具體問題，與解有關的狀態空間一般僅是全部狀態空間的一部分

因此，在問題求解過程中，沒有必要生成和保存該問題的全部狀態空間，只要能夠生成和保存與解有關的那部分狀態空間即可。解決這一問題的方法是採用狀態空間搜索技術。

對狀態空間的搜索，由於問題的狀態空間可用一個有向圖來表示，因此狀態空間搜索實際上就是對有向圖的搜索。3.2.1一般圖搜索過程

Open表Closed表若要討論狀態空間搜索的一般演算法，還需要設立Open表和Closed表這樣兩個數據結構。

Open表用於存放剛生成的節點，由於這些節點還沒有進行擴展，因此Open表也稱為未擴展節點表；

Closed表用於存放已經擴展的節點，因此Closed表也稱為已擴展節點表。此外，對問題的初始狀態、搜索過程得到的搜索圖、當前擴展節點新生成的子節點集，也都需要用相應的符號來表示。3.2.1

一般圖搜索過程

假設用S表示問題的初始狀態，G表示搜索過程所得到的搜索圖，M表示當前擴展節點新生成的且不為自己先輩的子節點集。在上述假設下，狀態空間的一般圖搜索過程為：

（1）把初始節點S放入Open表，並建立目前僅包含S的圖G；

（2）檢查Open表是否為空，若為空，則問題無解，失敗退出；

（3）把Open表的第1個節點取出放入Closed表，並記該節點為節點n；

（4）考察節點n是否為目標節點。若是則得到了問題的解，成功退出；

（5）擴展節點n，生成一組子節點。把這些子節點中不是節點n祖先的那部分子節點記作集合M，並把這些子節點作為節點n的子節點加人G中;

（6）針對M中子節點的不同情況，分別作如下處理：

①對那些沒有在G中出現過的M成員設置一個指向其父節點（即節點n）的指針，並把它放入Open表。②對那些原來已在G中出現過，但還沒有被擴展的M成員，確定是否需要修改它指向父節點的指針。③對於那些先前已在G中出現過，並已經擴展了的M成員，確定是否需要修改其後繼節點指向父節點的指針。

（7）按某種策略對Open表中的節點進行排序。

（8）轉第（2）步。3.2.1

一般圖搜索過程

廣度優先搜索也稱為寬度優先搜索，它是一種先生成的節點先擴展的策略。

廣度優先搜索過程：

從初始節點開始逐層向下擴展，在第n層節點還沒有全部搜索完之前，不進入第n＋l層節點的搜索。Open表中的節點總是按進入的先後排序，先進入Open表的節點排在前面，後進入Open表的節點排在後面。

3.2.2盲目搜索--廣度優先搜索盲目搜索包括:

廣度優先搜索、等代價搜索、深度優先搜索、有界深度優先搜索、迭代加深搜索等

廣度優先搜索演算法如下：（1）把初始節點S放入Open表中；（2）如果Open表為空，則問題無解，失敗退出（3）把Open表的第一個節點取出放入Closed表，並記該節點為n；（4）考察節點n是否為目標節點。若是，則得到問題的解，成功退出；（5）若節點n不可擴展，則轉第（2）步；（6）擴展節點n，將其子節點放入Open表的尾部，並為每一個子節點設置指向父節點的指針，然後轉第（2）步。3.2.2廣度優先搜索例：八數碼難題。分析：可以使用的操作有：空格左移、上移、右移和下移條件：只允許把位於空格左、上、右、下方的牌移入空格。要求：應用廣度優先搜索策略尋找從初始狀態到目標狀態的解路徑。3.2.2廣度優先搜索2834765Startstate12384765Goal

state八數碼難題2834765S1283147652238476532834765428364755

8321476528371465

23847652384765284376528345762836475283647567

8910111213832147652837146512384765234876528437652834576283641752836754141521832147658132476522232837461528371465242512384765123784652627G由圖可以看出，解的路徑是：S→3→8→16→26(G)八數碼難題的廣度優先搜索圖3.2.2廣度優先搜索16171819203.2.2廣度優先搜索OPENCLOSED1.S2.S3.2345S4.345S25.34567S26.4567S237.456789S238.56789S2349.567891011S23410.67891011S234511.----------------------------------------------------------n-1.---------n.

2627S2----11----25G廣度優先搜索的特點：優點：廣度優先搜索是一種完備策略，即只要問題有解，它就一定可以找到解。廣度優先搜索找到的解，一定是路徑最短的解。缺點：盲目性較大，尤其是當目標節點距初始節點較遠時，將產生許多無用的節點，因此其搜索效率較低。3.2.2廣度優先搜索課堂練習：給出採用廣度優先演算法的Open表和Closed表3.2.2廣度優先搜索SLOMF2NF1PQF3F4廣度優先搜索G3.2.3等代價搜索（1）把初始節點S放入Open表中，並令g（S）=0；（2）如果Open表為空，則問題無解，失敗退出；（3）選擇Open表的一個節點i，使g（i）值為最小（若存在幾個節點滿足條件，則任選其一）。判斷是否為目標節點：是，則成功退出；否則，將其取出放入Closed表；（4）擴展節點i將其子節點放入Open表，並為每一個子節點設置指向父節點i的指針；若節點i不可擴展，則轉第（2）步；（5）對於節點i的每個後繼節點j，計算g（j）=g（i）+c（i，j）；（6）轉第（2）步。當圖中弧的代價不等時，如何找到一條從初始節點到目標節點的最小路徑呢？等代價搜索演算法如下：SABDGCEOPENCLOSED1.S2.S3.ABCS4.ACSB5.ACEF

SB6.AEF

SBC7.EF

SBC8.EFSBCA9.FSBCAE10.FGSBCAE322451目標節點

深度優先搜索是一種後生成的節點先擴展的策略。

這種搜索策略的搜索過程是：

1.從初始節點開始，在其子節點從初始節點開始，在其子節點中選擇一個最新生成的節點進行考察，如果該子節點不是目標節點且可以擴展，則擴展該子節點；

2.然後再在此子節點的子節點中選擇一個最新生成的節點進行考察

3.依此向下搜索，直到某個子節點既不是目標節點，又不能繼續擴展時，才選擇其兄弟節點進行考察。3.2.4盲目搜索--深度優先搜索3.2.4深度優先搜索深度優先搜索演算法如下：

（l）把初始節點S放人Open表中；

（2）如果Open表為空，則問題無解，失敗退出；

（3）把Open表的第一個節點取出放入Closed表，並記該節點為n；

（4）考察節點n是否為目標節點。若是，則得到問題的解，成功退出；

（5）若節點n不可擴展，則轉第（2）步；

（6）擴展節點n，將其子節點放入Open表的首部，並為每一個子節點設置指向父節點的指針，然後轉第（2）步。3.2.4深度優先搜索例：八數碼難題。要求用深度優先搜索策略尋找從初始狀態到目標狀態的解路徑。

解：應用深度優先搜索策略，其部分搜索樹如右圖所示。在右圖中，由於問題的目標尚未達到，因此搜索還需要繼續進行下去。8321476583214765832147652831476523184765283147652831647528314765

有界深度優先搜索過程總體上按深度優先策略進行，但對搜索深度需要給出一個深度限制db，當搜索深度達到了db，但還沒有找到目標時，就停止該分支的搜索，換到另外一個分支進行搜索。

當給定的深度限制為db時，有界深度優先搜索演算法如下：

（1）把初始節點S放入Open表中，置S的深度d（S）=0；（2）如果Open表為空，則問題無解，失敗退出；（3）把Open表的第一個節點取出放入Closed表，並記該節點為n；（4）考察節點n是否為目標節點。若是，則得到問題的解，成功退出；（5）如果節點n的深度d（n）=db或若節點n不可擴展，則轉第（2）步；（6）擴展節點n，將其子節點放入Open表的首部，並為每一個子節點設置指向父節點的指針，然後轉第（2）步。3.2.5深度優先搜索---有界3.2.5有界深度優先搜索例：八數碼難題。設深度限制成db=4，要求用有界深度優先搜索策略尋找從初始狀態到目標狀態的解路徑。G八數碼難題的有界深度優先搜索2834765S128314765223847651128347652836475

8321476528371465

238476523847652843765283457628364752836475371383214765283714651238476523487652843765283457628364175283675448832147658132476556283746152837146591012384765123784651412課堂練習：db=4OPENCLOSED1.S2.S3.LOS4.OSL5.MF2OSL6.F2OSLM7.NF2OSLM8.F2OSLMN9.F1F2OSLMN10.F2OSLMNF111.OSLMNF1F212.SLMNF1F2O13.PQSLMNF1F2O14.QSLMNF1F2OP15.F3QSLMNF1F2OP深度db=4

對有界深度優先搜索策略，還有以下幾點需要說明。

（1）在有界深度優先搜索演算法中，深度限制db是一個很重要的參數。當問題有解，且解的路徑長度小於或等於db不時，則搜索過程一定能夠找到解。但是當解的路徑長度大於db時，則搜索過程就找不到解。

（2）深度限制db的值不能太大。當db的值太大時，搜索過程將產生過多的無用節點，既浪費電腦資源，又降低了搜索效率。

3.2.2深度優先搜索—有界3.2.6迭代加深搜索（1）把初始節點S放入Open表中，並令深度界限參數db=0；（2）Loop：db=db+1，進行深度界限為db的深度優先搜索；（3）若發現目標節點，則成功退出；否則，轉第（2）步；注意：對於（2）步要注意設定迴圈終止條件既能滿足深度優先搜索的線性存儲又能保證發現一個小小深度的目標節點的方法。迭代加深搜索演算法如下：

機器學習MachineLearning機器學習概述(1)什麼是機器學習？學習是使系統在不斷重複的工作中對本身能力的增強和改進，使得系統下一次完成同樣或類似的任務時比上一次更有效，即通過對人類學習過程和特點的研究，建立學習理論和方法，並應用於機器，以改進機器的行為和性能。

1、學習是一個過程。學習是經驗積累的過程，這個過程可能很快，也可能很漫長；2、學習是對一個系統而言。這個系統可能是一個電腦系統，或一個人機系統；3、學習能夠改變系統的性能。這只說明對系統性能的改進，但是並未限制改進的方法。從人工智慧的角度看，機器學習是一門研究使用電腦獲取新的知識和技能，提高現有電腦求解問題能力的科學機器學習概述(2)什麼要研究機器學習？必要性：理解學習的本質和建立學習系統是AI研究的目標之一現有的大多數AI系統都是演繹的，沒有歸納推理，因而不能自動獲取和生成知識可行性：學習的過程是資訊處理的過程，這包括直接記憶和經過推理已有工作說明可以實現一定程度的機器學習機器學習概述(3)機器學習的研究目標和困難研究目標：通用學習演算法：理論分析任務和開發用於非實用學習任務的演算法認知模型：研究人的學習的計算模型和實驗模型工程目標：解決專門的實際問題，並開發完成這些任務的工程系統困難：學習系統性能的預測更加困難獲取知識的本質還是猜想。由特定的觀察和類比生成的知識不可能證明其正確性。機器學習概述(4)學習的一種模型環境：外部資訊的來源，它將為系統的學習提供有關資訊知識庫：代表系統已經具有的知識學習環節：系統的學習機構，它通過對環境的感知取得外部資訊，然後經分析、綜合、類比、歸納等思維過程獲得知識，生成新的知識或改進知識庫的組織結構。執行環節：基於學習後得到的新的知識庫，執行一系列任務，並將運行結果報告學習環節，以完成對新知識庫的評價，指導進一步的學習工作,是該模型的核心。

環境學習環節知識庫執行環節機器學習概述(5)機器學習的研究大致可以分為三個階段：五六十年代的探索階段：主要受神經生理學、生理學和生物學的影響，研究主要側重於非符號的神經元模型的研究，主要研製通用學習系統，即神經網路或自組織系統。主要成果有：感知機（Perceptron）Friedberg等模擬隨機突變和自然選擇過程的程式，Hunt等的決策樹歸納程式CLS。

機器學習概述(6)七十年代的發展階段：由於當時專家系統的蓬勃發展，知識獲取成為當務之急，這給機器學習帶來了契機，主要側重於符號學習的研究。機器學習的研究脫離了基於統計的以優化理論為基礎的研究方法，提出了基於符號運算為基礎的機器學習方法，並產生了許多相關的學習系統，主要系統和演算法包括：Winston的積木世界學習系統；Michalski基於邏輯的歸納學習系統AQVAL；Michalski和Chilausky的AQ11；Quinlan的ID3程式Mitchell的版本空間方法。機器學習概述(7)八九十年代至今的鼎盛階段。

理論研究和應用研究也有了新的突破，機器學習的研究進入了全面的、系統化的時期。

主要成果有：一方面傳統的符號學習的各種方法已日臻完善。Michalski等將AQ11擴充為一個多功能學習系統AQ15，ID3演算法中使用了熵，從而使決策樹歸納得到了很大的改進。

科學發現系統BACON開闢了無導師學習的兩個重要研究領域。

神經網路學習在消沉了一段時期後又重新蓬勃發展起來了，同時電腦硬體技術的高速發展也為開展大規模和高性能的人工神經網路提供了保障，使得基於神經網路的連接學習從低谷走出，發展迅猛。其中Rumelhart等人提出的BP模型，提供了一個訓練多層網路的實際可行的方法，克服了Perceptron的大部分局限性。

機器學習概述(8)另一方面，機器學習的基礎理論的研究越來越引起人們的重視。1984年美國學者Valiant提出了基於概率近似正確性的學習理論（PAC學習），對布爾函數的一些特殊子類的可學習性進行了探討，將可學習性與計算複雜性聯繫在一起，並由此派生出了“計算學習理論”（COLT）我國學者洪家榮教授證明了兩類布爾運算式：析取範式和合取範式都是PAC不可學習的，揭示了PAC方法的局限性[

1995年，Vapnik出版了“統計學習理論”一書。對PAC的研究是一種理論性，存在性的；Vapnik的研究卻是構造性的，他將這類研究模型稱為支持向量機SVM（SupportVectorMachine）。機器學習概述(9)機器學習的研究方法

按推理策略分類

。1、演繹學習：是一種常規的邏輯推理方法。其推理的過程就是從公理出發，經過邏輯變換，推導出結論。

2、歸納學習：環境或教師提供一系列正例和反例，通過歸納推理，機器將這些例子進行推廣，產生一個或一組一般的概念描述。

3、類比學習：利用兩個不同領域（目標域和源域）知識的相似性，從源域的知識（包括相似的特徵和其他特徵）推斷出目標域的相應知識的推理方法。

4、基於解釋的學習：系統已知某個理論及該理論的一個實例，通過解釋為什麼這一實例可以用理論來解決，從而產生關於待學概念的一個解釋。

Agenda機器學習概述歸納學習決策樹學習基於範例的學習(CBR)解釋學習強化學習歸納學習(1)歸納學習（InductiveLearning）就是從個別到一般，根據某個概念的一系列已知的正例和反例，從中歸納出一個一般的概念描述旨在從大量的經驗數據中歸納抽取出一般的判定規則和模式。是機器學習中最核心、最成熟的分支。歸納學習也稱為：經驗學習：歸納學習依賴於經驗數據基於相似性的學習：歸納學習依賴於數據間的相似形歸納的操作：泛化(Generalization)：擴展某假設的語義資訊，使其能夠包含更多的正例特化(Specialization)：泛化的相反操作，用於限制概念描述的應用範圍歸納學習(2)歸納學習的分類和研究領域：符號學習有導師學習：實例學習：導師事先將訓練例子（經驗數據）分類：正、負例子。由於它產生規則，所以也稱為概念學習無導師學習：事先不知道訓練例子的分類概念聚類：機器發現神經網路：本質上是實例學習，為區別起見，稱為聯結學習（？）學習的計算理論傳統的演算法複雜性分析概率近似正確性學習研究（計算學習理論）實例學習(1)基本思想：環境提供給系統一些特殊的實例，這些例子事先由施教者劃分為正例和反例。實例學習由此進行歸納推理，產生適用於更大範圍的一般性知識，得到一般的規則，它將覆蓋所有的正例並排除所有的反例。環境提供給學習環境的例子是低水準的資訊，這是在特殊情況下執行環節的行為。學習環節歸納出的規則是高水準的資訊，可以在一般情況下用這些規則指導執行環節的工作實例學習(2)兩個空間模型：例子空間要考慮的問題：示教例子的品質例子空間的組織和搜索方法規則空間要考慮的問題形成知識的歸納推理方法搜索規則空間的方法對規則空間的要求例子空間規則空間選擇例子解釋例子實例學習(3)按規則空間搜索方法分類：數據驅動方法：變形空間方法：採用統一的形式表示規則和例子。改進假設方法：例子和規則的表示不統一。程式根據例子選擇一種操作，用該操作修改H中的規則模型驅動方法：產生和測試方法：針對示教例子反復產生和測試假設的規則。利用基於模型的知識產生假設的規則，便於只產生可能合理的假設方案示例方法：使用規則方案的集合來限制可能合理的規則形式，最符合示教例子的規則被認為是最合理的規則實例學習(4)按任務的複雜性劃分為：學習單個概念：由系統提供的某個概念的正例和反例，只要求系統歸納出一個概念的描述規則學習多個概念：要求歸納出多個相互獨立的概念學習執行多步任務：執行環節使用一個操作序列去完成任務，即執行環節進行任務規劃。因此，歸納出的規則應該是進行任務規劃的規則Agenda機器學習概述歸納學習基於範例的學習(CBR)解釋學習強化學習CBR(1)人們為了解決一個新問題，先是進行回憶，從記憶中找到一個與新問題相似的範例，然後把該範例中的有關資訊和知識複用到新問題的求解之中。在基於範例推理(Case-BasedReasoning,簡稱CBR)中，把當前所面臨的問題或情況稱為目標範例(targetcase)，而把記憶的問題或情況稱為源範例(basecase)。粗略地說，基於範例推理就是由目標範例的提示而獲得記憶中的源範例，並由源範例來指導目標範例求解的一種策略。CBR(2)範例（case）：“範例是一段帶有上下文資訊的知識，該知識表達了推理機在達到其目標的過程中能起關鍵作用的經驗”。具體來說，一個範例應具有如下特性：範例表示了與某個上下文有關的具體知識，這種知識具有可操作性。範例可以是各式各樣的，可有不同的形狀和粒度，可涵蓋或大或小的時間片，可帶有問題的解答或動作執行後的效應。範例記錄了有用的經驗，這種經驗能幫助推理機在未來更容易地達到目標，或提醒推理機失敗發生的可能性有多大等等。CBR(3)傳統的推理觀點是把推理理解為通過前因後果鏈(如規則鏈)演繹出結論的一個過程。許多專家系統使用的就是這種規則鏈式的推理方法。對於知識易於表示成啟發式規則形式的問題來說，基於規則的方法比較適合，如分類問題和診斷問題等。但是人們在遇到一個新的問題的時候，一般先是回憶，從記憶中找到一個與新的問題相似的案例，然後把該案例中的有關資訊和知識複用到新問題的求解之中。基於範例推理中知識表示是以範例為基礎，範例的獲取比規則獲取要容易,大大簡化知識獲取。對過去的求解結果進行複用，而不是再次從頭推導，可以提高對新問題的求解效率。過去求解成功或失敗的經歷可以指導當前求解時該怎樣走向成功或避開失敗，這樣可以改善求解的品質。對於那些目前沒有或根本不存在可以通過計算推導來解決的問題。如在法律中的判例，基於範例推理能很好發揮作用。CBR(4)CBR採用的是和基於規則鏈推理完全不同的觀點，在CBR中，使用的主要知識不是規則而是範例(case)，這些範例記錄了過去發生的種種相關情況。對CBR來講，求解一個問題的結論不是通過鏈式推理產生的，而是從記憶裏或範例庫中找到與當前問題最相關的範例，然後對該範例作必要的改動以適合當前問題。CBR的基本思想是：人們的推理過程是基於特殊的經驗而不是一組總的指導原則。和其他基於AI的推理方法比較，CBR是通過聯想（或類比），從過去的案例出發，把過去的案例和當前面臨的問題相比較做出決策的過程。問題的解答來自於過去的經驗而不是規則，這些經驗以案例的方式存貯

CBR的過程模型

基於範例的推理是一個“回憶和調整”或“回憶和比較”的過程。在範例推理中，範例用於輔助理解和分析情景並用於輔助解決問題。我們的日常推理中，情景的理解、分析和問題的解決過程一般是相輔相成的。當我們還沒有理解一個問題所處的情景時，是不可能解決該問題的；另一方面，我們又需要通過解決某個問題才能充分理解與它有關的情況。我們常常通過採用一些評估方法去檢驗結果來評價求解結論的好壞；同時我們在評估的過程中又需要解決新的問題。Agenda機器學習概述歸納學習基於範例的學習(CBR)解釋學習解釋學習(1)實例中進行學習歷來是機器學習領域研究的焦點，早期的工作基本上局限於歸納學習的範疇，相應的研究成果很少或基本沒有考慮背景知識對學習過程的影響。因此，這些方法從根本上來說是以數據為第一位的，沒有反映出人工智慧領域基於知識的研究和發展傾向。從20世紀80年代中期開始，機器學習研究重點開始由以歸納方法為主的數據密集型學習方法的研究向多樣化方法發展，開始研究分析方法、遺傳演算法、連接學習等。其中分析學習利用豐富的領域知識為背景，只需要通過分析很少的幾個例子（通常是一個例子），就能將例子泛化為對目標概念的解釋(通過泛化實例的解釋，而不是泛化實例自身).分析方法主要依賴於演繹推理，以產生更有效的問題求解知識，如搜索控制知識。因此，分析學習的主要目的是提高問題的求解效率，而不是獲取新的概念描述。解釋學習(2)基於解釋的學習是分析學習的主要方式，基於解釋的學習（簡稱EBL）是將大量的成果彙集在一個統一、簡單的框架內，通過分析為什麼實例是某個目標概念的一個具體例子，EBL對分析過程（一個解釋）加以推廣，剔去與具體例子有關的成分，從而產生目標概念的一個描述。EBL的初始狀態：DT（DomainTheory）包含一組事實和規則，用於證明（解釋）訓練實例如何滿足目標概念。TC（TargetConcept）是待學概念的一個非操作性描述。E為目標概念的一個例子。C（OperationalityCriterion）是定義在概念描述上的一個二階謂詞，用以表示學習得到的目標概念可用哪些基本的、可操作的概念表示，以使這些知識能用於問題求解活動。解釋學習(3)基於解釋的學習過程:可劃分為下麵兩個步驟：

（1）分析階段：使用領域理論建立一個證明訓練例子滿足目標概念定義（初始描述）的解釋結構，該結構可表示為一棵證明樹，又稱為解釋樹，它用於解釋為什麼實例是目標概念的一個實例，其每個分枝的葉結點上的運算式都必須滿足可操作性準則。（2）基於解釋的泛化（Explanation-BasedGeneralization，簡稱EBG）階段：通過將實例證明樹中的常量用變數進行替換，從而完成解釋的泛化，並使其滿足可操作準則，形成一棵基於解釋的泛化樹（簡稱EBG樹），得到目標概念的一個充分條件。

計算智能計算智能涉及：神經網路模糊計算進化計算人工生命等領域

人工神經網路ANN（ArtificialNeuralNetwork）是由大量的簡單處理單元經廣泛並行互聯形成的一種神經網路系統。它是對人腦系統的簡化、抽象和模擬，具有人腦功能的許多基本特徵。

目前，人工神經網路已成為許多高科技領域的一個熱門話題。在人工智慧領域，它已實際應用於模式識別專家系統機器學習優化等許多方面。4.1人工神經網路概述

為了加深對基於神經網路的連接學習機制的理解，需要先掌握與連接學習有關的人工神經網路的基礎知識。

1．生物神經元的結構

生物神經元（Neuron）即為神經細胞，它是生物神經系統的最基本單元。從其形狀和大小來看，神經元是多種多樣的，但從組成結構看，各種神經元又具有共性。神經元的基本結構如圖4.1所示，它由細胞體、軸突和樹突三個主要部。圖4.1生物神經元結構圖圖4.2神經元模型圖∑f（_）θ-1x1ω1jx2ω2jxnωnjyjy=f(ξ)=f(∑ωij*xi

–

θ)f為神經元模型輸出變換函數（激勵函數）∑ωij*xi

(i=1,2,……,n)為神經元模型的輸入θ為神經元模型閾值2．人工神經網路

儘管人類神經系統規模宏大、結構複雜、功能神奇，但其最基本的處理單元卻只有神經元。人工神經網路是對人類神經系統的一種模擬。人工神經元之間通過互連形成的網路稱為人工神經網路。在人工神經網路中，神經元之間互連的方式稱為連接模式或連接模型。它不僅決定了神經元網路的互連結構，同時也決定了神經網路的信號處理方式。3．人工神經網路的分類

目前，已有的人工神經網路模型至少有幾十種，其分類方法也有多種。例如：按網路拓撲結構可分為無回饋網路與有回饋網路；按網路的學習方法可分為有教師的學習網路和無教師的學習網路；按網路的性能可分為連續型網路與離散型網路，或分為確定性網路與隨機型網路；按突觸連接的性質可分為一階線性關聯網路與高階非線性關聯網路。4.人工神經網路的發展過程人工神經網路的發展過程大致可分為四個階段。

（1）產生時期

這一階段為20世紀5O年代中期之前。1943年，美國心理學家麥克洛奇與數學家皮茨在其論文《神經活動中所蘊含思想的邏輯活動》中提出了一種非常簡單的神經元模型，即M-P模型，從而開創了神經網路模型的理論研究。1949年，心理學家赫布（D.O.Hebb）在其著作《行為的組織》中提出了神經元之間連接強度變化的Hebb規則，為神經網路學習的研究奠定了基礎。

（2）高潮時期

這一階段為2O世紀5O年代中期到2O世紀6O年代末期。1957年，羅森勃拉特（F．Rosenblatt）在M-P模型的基礎上提出了感知器（Perceptron）模型，把神經網路研究從純理論探討發展到工程實現。1962年，羅森勃拉特又給出了兩層感知器的收斂定理。此外，還有許多人在神經計算的結構和實現思想方面做出了很大貢獻。（3）低潮時期

這一階段為20世紀60年代末到20世紀8O年代初期。由於神經網路研究與當時占主導地位的符號人工智慧的研究途徑不同，因而引起了人們的廣泛關注，同時也產生了很大的爭議。當時在美國麻省理工學院的明斯基和裴伯特（S.Papert）對感知器的功能及其局限性從數學上作了深入研究後，於1969年發表了著名的論著《Perceptrons》（感知器），指出了雙層感知器的局限性，對人工神經網路做出了悲觀的結論。由於明斯基在人工智慧界的威望和雙層感知器本身的局限性，很多人都認為人工神經網路前途渺茫，從而使人工神經網路的研究落入低潮。值得慶倖的是，即使在這種極端艱難的條件下，還仍有一部分學者在潛心研究。正是由於他們的不懈努力，才為人工神經網路的再度復興開闢了道路。（4）蓬勃發展時期

這一階段為20世紀80年代至今。1982年，美國加州理工學院的生物物理學家霍普菲爾特（J．J．Hopfield）提出了一個用於聯想記憶和優化計算的離散神經網路模型，並成功地求解了計算複雜度為NP完全型的旅行商問題。這一突破性的研究工作，使人工神經網路研究再度興起，並進入了一個蓬勃發展的時期。4.2人工神經網路互連結構及其學習機理

多層前向神經網路模型的典型代表是BP神經網路，如圖4.3所示。輸入模式由輸入層進入網路，經中間各層的順序變換，最後由輸出層產生一個輸出模式，便完成一次網路更新。這是最簡單的一種前向多層網路。圖4.3前饋（多層）神經網路1、前饋網路

回饋網路是一種允許輸出層-隱層，隱層中各層之間，隱層-輸入層之間具有回饋連接的方式，回饋的結果將構成封閉環路。在這種神經網路中，引出有回饋連接弧的神經元稱為隱神經元，其輸出稱為內部輸出。2、回饋網路

圖4.5異或邏輯的神經網路4.3基於神經網路的知識表示與推理0x11.004x22.102y0-1.5-2-1-3.1211.071.1351.1輸入x1輸入x2輸出y

0 0 0

1 0 1

1 1 0

0 1 1

圖4.6異或邏輯的神經網路0x11x21y0-0.5-0.5-0.51-1-11輸入x1輸入x2輸出y

0 0 0

1 0 1

1 1 0

0 1 1

4.3基於神經網路的知識表示與推理4.4一種廣泛應用的神經網路B-P網路的網路學習傳播公式

網路學習的傳播公式是網路學習中用來調整網路連接權值和閾值的公式。實際上，網路學習過程就是一個對給定訓練模式，利用傳播公式，沿著減小誤差的方向不斷調整網路連接權值和閾值的過程。為了討論傳播公式的需要，下麵先給出幾個符號約定：

Oi

：節點i的輸出；

netj

：节点j的輸入；

ωij

：从节点i到節點j的連接權值；θj：節點j的閾值；

yk

：输出层上节点k的實際輸出；tk

：輸出層上節點k的期望輸出。

顯然，對隱含節點j有：

netj＝ΣωijOi

Oj＝f（netj-θj

）

在B-P演算法學習過程中，可以採用如下公式計算各輸出節點的誤差：

e=1/2*Σ(tk-yk)2

連接權值的修改由下式計算：

ωjk(t+1)=ωjk(t)+Δωjk

其中，ωjk

（t）和ωjk

（t＋1）分別是時刻t和t+1時刻，從節點j到節點k的連接權值；Δωjk是連接權值的變化量。前饋網路之B-P網路的學習演算法可描述如下：

（1）初始化網路及學習參數，即將隱含層和輸出層各節點的連接權值、神經元閾值賦予[－1，1]區間的一個亂數；

（2）提供訓練模式，即從訓練模式集合中選出一個訓練模式，將其輸入模式和期望輸出送入網路；

（3）正向傳播過程，即對給定的輸入模式，從第一隱含層開始，計算網路的輸出模式，並把得到的輸出模式與期望模式比較，若有誤差，則執行第（4）步；否則，返回第（2）步，提供下一個訓練模式；

（4）反向傳播過程，即從輸出層反向計算到第一隱含層，按以下方式逐層修正各單元的連接權值：

①計算同一層單元的誤差δk；

②按下式修正連接權值和閾值。

對連接權值，修正公式為：

ωjk（t＋1）=ωjk(t)+Δωjk

（5）返回第（2）步，對訓練模式集中的每一個訓練模式重複第（2）到第（3）步，直到訓練模式集中的每一個訓練模式都滿足期望輸出為止。ηδkOj

B-P網路模型是目前使用較多的一種神經網路，它有自己的優點，也存在一些缺點。

B-P網路的主要優點有：

（1）演算法推導清楚，學習精度較高；

（2）從理論上說，可以使多層前饋網學會任何可學習的東西；

（3）經過訓練後的B-P網路，運行速度極快，可用於即時處理。

B-P網路的主要缺點有：

（1）由於它的數學基礎是非線性優化問題，因此，可能陷入局部最小區域；

（2）學習演算法收斂速度很慢，通常需要數千步或更長，甚至還可能不收斂；

（3）網路中隱含節點的設置無理論指導。

對於上述缺點，為了解決陷入局部最小區域問題，通常需要採用模擬退火演算法或遺傳演算法等第5章計算智能之遺傳演算法

遺傳演算法（GeneticAlgorithm--GA）是一種新興的搜索尋優技術。它仿效生物的進化與遺傳，根據“生存競爭”和“優勝劣汰”的原則，借助複製、交換、突變等操作，使所要解決的問題從初始解一步步地逼近最優解。因此，它又被稱為進化計算。

5.1如何應用遺傳演算法解決問題？遺傳演算法在求解問題時主要包含了兩個基本的過程：遺傳運算：交叉、變異進化運算：選擇

5.1.1遺傳演算法解決問題的一般結構解1100101010101110111000110110011100101110110010101010111011101100101110101110101000110110010011001001110010111010111010100011001001解解碼適值計算輪盤賭選擇後代變異交叉評估編碼染色體產生新的種群

5.1.2GA的基本機理編碼和解碼

將問題結構變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為原問題結構的過程叫解碼或解碼。把位串形式編碼表示叫染色體(Chromosome)，有時也叫個體。

注意:種群中的每個個體是問題的一個解,也就是一個染色體。例1:maxf(x)=x2St:0≦x≦31

利用遺傳演算法求出問題的整數解。0≦x≦310≦x≦25

例1中利用5位二進位數表示x值，

13011012411000801000

將13、24、8轉換成二進位數的這一過程的就是編碼的過程。將二進位數轉換成十進位數的過程就是解碼過程。對於（如：01101）這樣編碼的二進位位串就是染色體，也就是個體。例1中我們設Pop_size=4,然後根據編碼方式隨機的產生初始種群。初始種群如下：

v1=[01101]

v2=[11000]

v3=[01000]v4=[10011]產生初始種群

遺傳演算法從一組隨機產生的初始解（或者說染色體）開始，在解空間中搜索問題的解。隨機產生的這組初始解就稱為初始種群(Population)。種群中染色體的個數就稱為種群大小(Pop_size)。注意：適值函數必須保證適值的非負性和保證適值增大的方向與目標函數進化方向的一致性。評估

評估是對染色體好壞的一個評價，用適值大小作為染色體評估的標準。評估時採用的手段是採用適值函數。適值越高表示個體對環境的適應性越強，相應的個體被選中進入次代的概率也越高。評估過程：

Step1：將染色體的基因型轉換為表現型；

Step2：計算目標函數值f（x）；

Step3：將目標函數值轉換為適值。對於本題我們選擇適值函數=目標函數Step1：v1=[01101]v1=[13]

v2=[11000]

v2=[24]

v3=[01000]v3=[8]

v4=[10011]

v4=[19]Step2：f（v1）=(v1)2=169

f（v2）=(v2)2=576

f（v3）=(v3)2=64f（v4）=(v4)2=361Step3：對於問題極大化，我們可以簡單的取目標函數為適值函數，即適值=目標函數值。

eval(v1)=f(v1)=169eval(v2)=f(v2)=576eval(v3)=f(v3)=64eval(v4)=f(v4)=361選擇

選擇是遺傳運算的推動力，其目的是從當前的群體中根據某種選擇策略得到下一代的進化群體。

輪盤賭是遺傳演算法中最經典的選擇方法，它是一種正比選擇策略，能夠根據與適值成正比的概率選出新的種群。輪盤賭有以下三步構成：計算種群中所有染色體的適值的和

對個染色體，計算選擇概率Pk對個染色體，計算累計概率qk

選擇過程就是旋轉輪盤賭pop_size次，每次按照如下方式選出一個染色體來構造新的種群：Step1：在[0，1]區間內產生一個均勻分佈的偽亂數rStep2：若r≦q1，則選擇第一個染色體，否則，選擇第k個染色體Vk(2≦k

≦pop_size)

，使得qk-1≦r

≦qk成立。例1中，選擇過程的各數值計算如下：

適應度eval(Vk) pk=eval(Vk)/F qk=∑PjV11690.140.14V25760.490.63V3640.060.69V44361 0.311

現在產生了4個亂數如下：

0.1，0.4，0.4，0.8；在選擇過程過程中依據亂數選出了如下新的初始種群：

V`1=[01101]V`2=[11000]V`3=[11000]V`4=[10011]交叉（Crossover）

交叉是GA中的遺傳運算。如下是幾種簡單的交叉方法：一點交叉

一點交叉是指在染色體中隨機的產生一個交叉點，將雙親染色體的後部分基因進行交換，從而產生兩個新的個體。

[01101]交叉[01100]

[11000]

[11001]兩點交叉兩點交叉是指在染色體中隨機的產生兩個交叉點，將雙親染色體的輛交叉點中間部分基因進行交換，從而產生兩個新的個體。

[01101]交叉[01001]

[11000]

[11100]

均勻交叉

均勻交叉是指隨機地產生一個與種群中染色體位長相同的二進位串，將這個二進位串稱為隨機罩，然後根據隨機罩的值（0-不交叉、1-交叉）對雙親染色體的相應位置的基因進行交叉。例如：設：隨機罩為[10100]

雙親染色體:交叉後

[01101][11001]

[11000]

[0110

0]例1中：設交叉率Pc=0.5，進行一點交叉。

對於種群中的個體進行交叉操作時，要按照設定的交叉率（Pc）進行交叉。V`1=[01101]V`2=[11000]C1=[01000]C2=[11101

]變異(Mutation)

變異是遺傳演算法的基本運算。變異有利於增加種群的多樣性，實現全局搜索，避免不成熟收斂現象的發生。二進位編碼變異通常的變異算子是隨機選中一個變異位，獎該位上的二進位基因按照0-1取反的方法進行變異。例：對於染色體[01101]隨機地產生變異位，設為3。

[01101]變異[01001]例1中：設變異率Pm=0.25。

V`3=[11000

]C3=[11100

]

對於種群中的個體進行變異操作時，要按照設定的交叉率（Pm）進行交叉。

新一代種群誕生:在經過了二~六步之後產生了新一代的種群，如下:C1=[01000]C2=[11101

]C3=[11100

]V`4=[10011]至此我們完成了GA的一次迭代。5.2演算法實現GA實現步驟:初始化群體（群體規模Pop_size）;

計算群體上每個個體的適值;

按由個體適值所決定的某個規則選擇將進入下一代的個體;

按概率Pc進行交叉操作;按概率Pm進行突變操作;沒有滿足某種