MOOC大學上的課程，做個學習筆記，方便以后復習回顧
教材是
1 緒論
1.1 AI概述
人工智能研究如何用硬體和軟體實作智能的理智的行為，即搜索、推理、規劃與學習，并在此之上去實作感知、認知與智能行為
人工智能自1956年誕生，經歷2次低潮后，計算能力的提升為其提供良好的平臺，多媒體資料的爆發性增長為期提供充足原料，AI先后戰勝了人類象棋、圍棋以及德州撲克的頂級選手，影像的識別與分類能力已經超越人類，指紋語音與人臉識別正在改變人機互動手段，各種型別的機器人運行在工廠和現實生活之中，人工智能的學術研究越來越深入，人工智能的創業者越來越多，人工智能正在改變我們的生活，世界上主要發達國家都把人工智能當做重大發展戰略，力爭在新一輪國際競爭中爭得主動權，中國國務院于2017年7月8日印發《新一代人工智能發展規劃》明確提出了中國人工智能發展戰略為三步走，2020年，人工智能的應用技術與世界先進水平同步，2025年人工智能基礎理論取得重大突破，2030年發展為世界主要的人工智能創新中心，所以說現在是人工智能的最好時期，有人擔心人工智能會造成大批人失業，有人認為人工智能是威脅，有人游說人工智能可能引發第三次世界大戰，更有人懼怕人工智能會毀滅人類，所以又說這是人工智能最有爭議的時期，
1956年的“Dartmouth Summer Research Project on Artificial Intelligence ”會議被廣泛認為是AI的誕生
Turing Test，圖靈測驗，1950年圖靈論文中提出，旨在提出一種令人滿意的關于智能的可操作性定義
如果一個人類提問，無法分辨書面回答者是人還是計算機，則認為通過測驗
視覺圖靈測驗，2014年唐納德·杰曼等人提出，是受人類理解影像能力的啟發而來，可用于對計算機視覺的認知能力進行評估
是采用一個輔助設備根據給定的影像產生隨機的二元問題序列
目前的計算機視覺系統是測驗任務的精度，這些任務包括物件監測、影像分割和定位，但是仍然和人類的行為方式有差距
產生的問題是相互關聯的，即后續問題與前面問題有關，如果回答正確就證明了這套計算機視覺系統是理解了這幅影像
中文屋Chines Room
是一個思想實驗，試圖揭示計算機不能描述為有“智力”或“知性”，不管它多么智能
他設想他獨自在一個房間，操作一套計算機程式來應付從門縫下塞進來的中文字符，他對中文一竅不通，然而，正如計算機所做的那樣，通過操作處理符號和數字，他生成了合適的中文字串，從而蒙騙了屋外所有人，以為屋內有一個精通中文的人，唯一的結論是，按程式運行的計算機可以使它看起來理解了語言，但并沒有產生真正的理解，由此他斷定，圖靈測驗是不充分的
1.2 人工智能的基礎
哲學、數學、經濟學、神經科學、心理學、計算機、控制理論和控制論、語言學
數學
邏輯學--得出正確結論的形式規則是什么？
計算--什么是可計算的？
NP完全性理論，是計算復雜性理論中的重要概念,能表征某些問題的固有復雜度
P：Polynomial time 多項式時間
NP：Non-deterministic Polynomial time 不確定性多項式時間
NP-complete: both in NP and NP-hard
概率--如何根據不確定資訊進行推理？
神經科學
大腦如何處理資訊？
認知心理學
人類如何思考與行動？
把大腦看做資訊處理設備，是研究心智程序的學科，包括：注意機制、語言運用、記憶、感知、問題求解、創造力、思考
記憶：三個子集，程序記憶、語意記憶、情景記憶
感知：物理感知（視覺、嗅覺、味覺、知覺），及其認知程序
語言：研究語言習得、語言形成的組件、語言使用時的語氣、或者許多其它相關領域
元認知：它是“關于認知的認知”，“關于思考的思考”，通常包含2個組成部分：關于認知的認知以及認知的調節
認知心理學：通常通過人類參與者的心理實驗來收集資訊，其目的是研究人腦如何接受外部世界的輸入、如何處理以及作用等
認知科學：關注于通過研究收集資料，其涉獵心理學、語言學、人類學、神經科學、社會學和教育學,尤其是人工智能
控制理論和控制論
機器如何在其自身的控制下運行？
控制理論：工程與數學的交叉學科分支，處理動態系統對輸入的行為以及該行為如何通過反饋進行調整
控制論：簡單的解釋為“用技術控制任何系統”
1.3 AI歷史
1950-1956，AI誕生
主要標識是圖靈測驗和達特茅斯會議
1956-1974，黃金年代
1958年，第一個人工智能程式名為邏輯理論家LT
1958年，發明Lisp編程語言
1960年，馬斯特曼設計語意網路，用于機器翻譯
1963年，發表關于模式識別的論文，描述了第一個機器學習程式
1965年，首套專家系統Dentral用于推斷有機化合物分子結構的軟體
1974年，MYCIN程式，實用的基于規則的醫學診斷方法，也可以成為醫學專家系統
1974-1980，第一個寒冬
寒冬之前是秋天，1966年機器翻譯失敗
1970年連接主義遭到遺棄
1971年至75年，美國DARPA對卡內基梅隆大學的語音理解研究專案感到沮喪
1973年英國大幅縮減AI研發
1973年-1974年，DARPA削減了一般性AI研究經費
1980-1987，AI繁榮
1980年AAAI美國人工智能學會在斯坦福大學召開第一屆國際大會
1982年，日本啟動第五代計算機系統（FGCS）專案，用于知識處理
計算機的第一代到第四代都是按照器件劃分的
1980年代中期，機器學習出現了，當時發明了決策樹模型并且以軟體形式推出，該模型具有可視化、易說明的特點
同樣在1980年代中期，還發明了多層人工神經元網路（ANN），具有足夠多的隱藏層，一個ANN可以表達任意功能，因此突破了感知的局限性
1987-1993，第二個寒冬
1987年，Lisp機的市場崩潰
1988年，美國政府取消新的AI經費
1993年，專家系統滑入低谷
1990s，日本第五代計算系統專案未能達到其初始目標悄然退場
1993至今，突破
1997年，深藍戰勝了國際象棋冠軍成為第一臺計算機國際象棋系統
2005年，斯坦福的自主機器人贏得DARPA無人駕駛汽車挑戰賽
2006年，深度學習的三個大牛之一杰佛里·辛頓和他的學生魯斯蘭·薩拉赫丁諾夫在科學雜志上發表論文讓該術語成為熱門
2011年，IBM沃森在智力競賽Jeopardy戰勝上屆冠軍獲得一百萬美元大獎
2011年谷歌啟動深度學習專案，深度大腦，作為Google X專案之一，谷歌大腦是由1萬6千的計算機的集群致力于模仿人類大腦活動的某些方面，通過一千萬張數字圖片的學習，已成功學會識別一只貓
2012年，蘋果推出Siri，Siri是一種智能個人助理和知識導航軟體，使用自然語言用戶介面來回答問題、做出建議和執行動作，支持各種語言
2012年，微軟首席研究官Rick Rashid到中國天津出席研討會演示了一款實時口譯系統，該軟體不僅翻譯準確還可以保持你的聲音和口音
2014年4月，微軟小娜
2014年6月，微軟中國推出聊天機器人小冰
2015年9月，百度在2015年百度世界大會上推出了一款機器人助理--度秘，可以為用戶提供秘書化搜索服務
2014年6月，聊天機器人Eugene，在紀念圖靈測驗60周年的一個比賽中，被33%的評委認為是人類，組織者認為通過圖靈測驗，該機器人是由3個程式員小組在2001年在圣彼得堡開發
2014年8月，IBM發表類人腦作業的TrueNorth芯片，是一款神經形態的CMOS芯片，由4096個硬體核組成，每個仿真256個可編程的硅神經元，總計剛好超過百萬個神經元
2015年2月，谷歌DeepMind公司在Nature雜志發表了Deep Q-Network，通過深度強化學習達到人類水平的操控
2015年12月，谷歌DeepMind公司的AlphaGo打敗歐洲圍棋冠軍成績五戰五勝，訊息在2016年1月才在nature雜志發表，目的是與描述演算法的論文同步發表，深度學習軟體首次擊敗人類職業棋手，2016年3月，AlphaGo在韓國首爾對壘韓國九段棋手李世石5戰4勝，后3比0超過世界第一柯潔
2016年4月，阿里小Ai預測到《我是歌手》李玟奪冠
同時也出現不同聲音，擔心人工智能有可能導致人類滅絕，2015年霍金等人簽發公開信警惕人工智恩潛在危險
2016年1月，位于華盛頓特區的資訊技術與創新基金會（ITIF）公布年度盧德獎，頒發給“一個科學家和名人組成的松散聯盟，他們在2015年警告AI將會導致人類末日，激起恐慌”，盧德獎是專門頒發給那些試圖阻礙科技創新的人
1.4 人工智能的發展現狀
人工智能的分類
第一種分類
4個分類8個定義，看到humanly早于rationally
第二種分類
弱AI、強AI、超AI
弱AI，也叫人工狹義智能Artificial Narrow Intelligence（ANI），它是無意識的AI，專注于一個具體任務（僅針對一個特定問題），比如Siri就是只有語音識別和自然語言回答的助理
強AI，也叫人工廣義智能Artificial General Intelligence(AGI),意味著機器具有將智能用于處理任何問題的能力，它像人類一樣能夠進行思考、計劃、解決問題、抽象思維、理解復雜理念、快速學習和從經驗中學習等操作，它是人工智能研究的主要目標
超AI，也叫人工超級智能Artificial Super Intelligence(ASI),是一個假定的智能體，擁有遠遠超過聰明和最有天賦的人類大腦的智慧，目前只能在電影小說中看到
人工智能應用
計算機視覺
影像處理
VR、AR和MR
模式識別
智能診斷
博弈論和策略規劃
AI游戲和游戲機器人
機器翻譯
自然語言處理和聊天機器人
非線性控制和機器人技術
其他包括：智能生活、自動推理、自動駕駛、生物計算、概念挖掘、資料挖掘、知識表示、語意Web、垃圾郵件過濾、訴訟、機器人學、混合人工智恩、智能代理、智能控制
代表性論文
“一種用于非線性降維的全域幾何框架”，2000年12月Science雜志，描述一種解決降維問題的方法，使用流形學習方法，使用易測的區域度量資訊來學習資料集潛在的全域結構，演算法簡稱Isomap（等距特征映射），創新處在于不是用傳統的歐式距離而是用測地線距離
“通過區域線性嵌入進行非線性降維”，2000年12月Science雜志同一期
“利用神經元網路降低資料的維度”，2006年7月Science，是深度學習三大牛之一的Geoffrey Hinton先生寫的（深度學習領域的三位大牛Yann LeCun、Yoshua Bengio和Geoffrey Hinton無人不知無人不曉），深度編碼器網路，通過這種網路可以有效提取資料的低維特征，描述一種初始化權重的有效方法，可讓深度編碼器網路學習低維代碼，作為一種降維工具，遠遠好于主成分分析方法，這種方法引起關注并引起學習深度學習熱潮
“通過快速查找和發現密度峰值進行聚類”，2014年6月Science，聚類作業的難點是如何尋找聚類中心點，經典的聚類演算法比如k-means是通過指定聚類中心然后通過迭代的方法更新聚類中心的方式，而這片論文基于如下的思想的方法：聚類中心點具有密度高于相鄰點、距離相對大于次高密度點的特征
“憑借概率規劃歸納法進行人類層次的概念學習”，2015年12月Science，論文研究的一次性學習能力作為對那些神經模型的挑戰：將組合性、因果性和學會學習BPL實體化的原則相結合，成為一個我們期待崛起的方向，他們創造的這款系統可以迅速的學會寫陌生文字，從某種意義說領悟到了字符的本質特征，也就是字符的總體結構，同時還可以識別非本質體征，也就是因為人工書寫造成的輕微變異
“憑借深度強化學習達到人類水平的操控”，2015年2月Nature，谷歌DeepMind在上世紀70年代末80年代初的一款老式游戲機上對49個游戲視頻軟體進行測驗結果60%達到或超過人類水平
“深度學習”，2015年5月Nature，綜述性論文
“利用深度神經網路和樹搜索征服圍棋游戲”，2016年1月Nature，這就是DeepMind的首次圍棋大戰的同步論文，使用“價值網路”評價棋盤位置，使用“策略網路”選擇走子，沒有任何前項搜索，該神經網路以先進水平的蒙特卡洛樹搜索程式博弈圍棋，模擬成千上萬次隨機自我對弈
人工智能的研究領域
搜索：針對問題空間，也叫問題求解
推理：知識
規劃：規則
學習：從資料中學習
應用：非常廣泛，溝通（自然語言處理、機器翻譯、聊天機器人等等），感知（視覺、聽覺、語音及其他），動作（機器人、無人飛行器、無人駕駛汽車等等）
本課程討論前4個，不討論應用
1.5 小結
AI的分類可分為4種：類人思考, 類人動作,理性思考和理性動作
8個基礎學科包括：哲學、數學、經濟學、神經科學、心理學、計算機工程、控制理論和控制論和語言學
AI的3種型別：弱人工智能、強人工智能以及超人工智能
2 智能Agent
縱覽人工智能的各種研究途徑
討論智能Agent性質、多樣性以及各種型別的Agent
2.1 人工智能的各種研究途徑
控制論和大腦仿真
符號和亞符號
邏輯與反邏輯
符號主義與連結主義
統計方法
智能Agent：有動作能力的sth，具有自主操作、感知環境、持續動作、順應變化、實作目標、最佳預期結果，概括的說：通過感受器感知外部環境并且通過執行器作用于外部環境，還可以通過學習或者應用知識實作目標
2.2 理性Agent
教材專注于理性Agent的一般原理和構造
人類agent、機器人agent、軟體agent、抽象agent、自主agent
定義多樣，但是一般有如下特征：逐步順應新的問題求解規則、適合在線與實時、能夠從行為錯誤與成功方面自我分析、通過與環境互動進行學習改善、迅速從大量的資料中學習、具有基于記憶體的樣本存盤和檢索能力、具有表示短期長期記憶遺忘等引數
理性Agent能使性能最大化，做最正確的事情，理性等于最優，依賴于：定義成功標準的性能指標、智能體對環境的先驗知識、智能體能夠完成的動作、智能體最新的感知序列
例子：真空吸塵器
2.3 任務環境
PEAS的描述：Performance、Environment、Actuators、Sensors
環境型別
完全可觀測與部分可觀測
單agent與多agent
確定agent與隨機agent
陣發性與連續性
動態與靜態、半動態
離散與連續
已知與未知
2.4 智能Agent結構
Agent函式是一個抽象概念，將給定的感知序列映射為動作，包含了各種決策制定的原則
Agent程式，包含agent函式和感受器、執行器
Agent結構
Agent = platform + agent程式
platform = computing device + sensors + actuators
agent程式包含agent函式
智能Agent通常是分層結構，包含許多子智能Agent，子智能體處理較低功能
Agent的內部狀態可以有三種表現方式：原子方式、因子方式、結構方式
原子方式：每個狀態是個黑盒子，不關心內部結構 比如：駕駛路徑尋找問題，從某個城市到另外一個城市，中間經過的城市，我們不關心其內部結構
因子方式：每個狀態由一組固定的屬性和值組成
結構化表示：每個狀態表示物件，每個物件有其屬性和與其他物件關系
2.5 智能Agent類別
該分類基于他們感知的智能和能力的程度：簡單反射agent、基于模型的反射agent、基于目標的agent、基于效用的agent、學習agent
簡單反射agent
簡單反射agent僅僅在當前感知的基礎上動作，忽略其余感知歷史，也就是說不關心上一個感知的東西，其agent函式是基于條件動作規則:if..then..
僅當外部環境為完全可觀測時，該agent才能發揮功能
某些反射智能體也可以包含其當前狀態的資訊，允許它們忽略執行器已被觸發的條件
agent在部分可觀測環境下運行時，有可能出現無限回圈現象
注意：如果agent可以隨機產生其動作，有可能從無限回圈中擺脫
演算法
基于模型的反射agent
除了可以完成簡單反射agent的功能外，還可以處理部分可觀測環境
其當前狀態存盤在agent中，維護某種結構，它描述不可見外部環境的一部分
關于“外部環境如何運作”的知識被稱為一個外部環境模型，由此得名
基于模型的反射agent將保持某種內部模型
內部模型依賴歷史，因此至少反射當前狀態無法觀測的方面
然后它作為反射agent選擇某種動作
演算法
基于目標的agent
通過利用“目標”資訊，進一步擴展了基于模型的反射agent
目標資訊描述所希望的狀況
它允許agent在多種可能之間選擇一種方式，挑選出達到目標的那一個
搜索和規劃是ai的子領域，目的是發現達到目標的動作序列
在某些情況下，基于目標的agent似乎不太有效
雖然顯得更低效，但是它更靈活，因為支持它決策的知識被顯示表達出來，并且可以被修改
基于效用的agent
一個特殊的狀態可通過一個效用函式得到，該函式將一個狀態映射為該狀態效用的度量
效用是一種更通用的性能度量
一個理性agent將動作結果的期待效應最大化
基于效用的agent需要建模并記錄環境、任務的軌跡，這涉及大量的感知、表征、推理、和學習的研究
學習agent
學習agent允許最初在未知的環境中運行，并且與其最初的知識相比，會變得越來越勝任
學習元件：負責改進提高
性能元件：負責選擇外部行動
學習元件利用評判元件的反饋并確定如何修改性能元件以便做的更好
學習元件的設計很大程度上依賴性能元件的設計
問題產生器：對推薦的動作負責，這將形成新的經驗
其他agent
決策agent：與決策制定相關
輸入agent：處理和理解感受器的輸入
加工agent：解決諸如語音識別的問題
2.6 小結
AI的主要方法：控制論與人腦仿真、符號與亞符號、基于邏輯與反邏輯、符號主義與聯結主義、統計學、以及智能體范例，
一個智能體是感知并作用于外部環境的任何事物，
典型的智能體：簡單反射智能體、基于模型的反射智能體、基于目標的智能體、基于效用的智能體、以及學習智能體
3 通過搜索進行問題求解
3.1 問題求解agent
解：達到目標的一組動作序列
尋找解的程序稱為搜索
問題形式化：給定一個目標，決定要考慮的動作與狀態
對于某些np完和np難問題，只能通過搜索來解決
問題求解agent：是一種基于目標的agent，通過搜索來解決問題
狀態空間：問題的狀態空間可以形式化的定義為初始狀態、動作和轉換模型
圖：狀態空間形成一個圖，其中節點表示狀態、鏈接表示動作
路徑：一系列動作連接的一個狀態序列
對一個問題進行形式化的五個要素：初始狀態、動作、轉換模型、目標測驗、路徑代價
3.2 問題實體
真空吸塵器世界
兩個房間 有無灰塵 可能的狀態 2*2^2=8狀態空間
任意狀態都可能為初始狀態
3個動作（左移右移吸塵）
轉換模型應有預期效果（以下為無效動作：左邊左移右邊右移清潔區吸塵）
目標檢測：是否所有房間都干凈
路徑代價：每個步驟cost1，所以代價是路徑個數
8數碼難題
9宮格中有8個數字和一個空格，相鄰模塊可以滑向空格，目的是達到指定狀態
簡單的方式是移動空格
8數碼難題屬于滑塊難題家族，這個家族被認定是NP完復雜
8皇后問題
2中方法：
增量形式化：空狀態開始每次加一個皇后
全態形式化：初始8個皇后都在，再移動她們
3.3 搜索求解
針對羅馬尼亞地圖問題使用圖搜索演算法生成一系列搜索路徑
也可以采用樹搜索的方法找到最短路徑
3.4 無資訊搜索策略
也稱為盲目搜索，表示無任何附加資訊
所能做的就是生成后繼節點并區分是否達到目標狀態
所有的搜索策略由節點的順序加以區分
這些搜索策略是：寬度優先、深度優先、以及一致代價搜索
評價：
完備性：是否總能找到一個存在的解
時間復雜性：花費多長時間找到這個解
空間復雜性：耗費多少記憶體
最優性：是否總能找到最優解
時間復雜度和空間復雜度用如下屬于度量：
b：搜索樹的最大分支因子
d：最淺的解的深度
m：搜索樹的最大深度
寬度優先搜索
搜索策略：擴展最淺的未擴展節點
實作方式：FIFO 先進先出，即新的后繼節點總是放佇列最后
除了圖之外也有關于樹的寬度優先搜索演算法
寬度搜索演算法有這些特性
時間復雜性 b+b^2+..+b^d=O(b^d)
空間復雜性也是O(b^d)
假設b=10，每秒1百萬節點搜索，每節點記憶體消耗1000bytes有上表消耗
記憶體的需求是個很大問題，執行時間是個主要因素
寬度優先搜索不能解決指數復雜性問題，小的分支因子除外
漢諾塔問題是個指數問題，據說最后一次移動金盤世界將毀滅，耗時不可想象
一致代價搜索
搜索策略：擴展最低代價的未擴展節點
實作方法：仍然是佇列，但是按照路徑代價排序，最低優先
復雜度
深度優先搜索
搜索策略：擴展最深的為擴展節點
采用LIFO佇列，把后繼節點放在佇列最前，這相當于一個堆疊
簡單二叉樹的深度優先搜索程序
對于搜索過的邊緣節點并未匹配的從記憶體洗掉
深度優先搜索的時間復雜性O(b^m) 空間復雜性O(bm),b為分支因子，m為任一節點的最大深度
空間復雜性大大減少
深度優先搜索變種--深度受限搜索
若狀態空間無限，則深度優先搜索會失敗，添加界限l可解決，即深度l的節點當做末梢節點，這叫做深度受限搜索
缺點：l<d,即最淺的目標在深度限制之外，這種方法就會出現不完備性；l>d,這種方法也非最優
深度優先搜索變種--迭代加深搜索
將深度優先和廣度優先結合，逐步增加深度限制反復運行直到找到目標
它以深度優先搜索相同的順序搜索，單先訪問節點的累計順序實際是寬度優先
其空間復雜度和深度優先搜索一致
雙向搜索
同時進行兩個方向搜索，一個是從初始狀態向前搜索，一個是從目標狀態向后搜索，當兩者相遇時停止
該方法可以通過一種剩余距離的啟發式估計來導向
無資訊搜索策略對比
3.5 有資訊搜索
也被稱為啟發式搜索
這類策略采用超出問題本身定義的、問題特有的知識，因此能夠找到比無資訊搜索更有效的解
一般使用如下函式中的一個或者兩個：評價函式，記f(n),用于選擇一個節點進行擴展；啟發函式，記h(n),作為f的一個組成部分
評估函式看做是代價估計，因此評估值最低的節點被優先擴展，最佳優先圖搜索的實作與一致性搜索類似
對f的選擇決定了搜索策略
一般采用最佳優先搜索
實作方式：與一致代價搜索相同，然而最佳優先演算法用f(n)替代g(n)來整理佇列
搜索策略：一個節點被選擇擴展是基于評價函式f(n)
大多數最佳優先演算法還包含一個啟發函式h(n)
h(n) = 從節點n到目標的最低徑路代價估計
3.5.1 貪婪最佳優先搜索
搜索策略：試圖擴展最接近目標的節點
評價函式 f(n) = h(n)
它僅適用啟發函式對節點進行評價
因為演算法每一步都試圖得到最接近目標的節點，所以稱為貪婪
搜索程序
解并不是最優的
最壞時間復雜性O(b^m)
空間復雜性同上
3.5.2 A*搜索
搜索策略：避免擴展代價高的路徑，使總的估計求解代價最小化
評價函式 f(n) = g(n) + h(n) g(n)是到該節點代價h(n)是從該節點到目標的估計代價
定理：A*搜索是最優的
搜索程序
3.5.3 迭代加深A*搜索
迭代加深搜索的變種
從A*搜索演算法借鑒思路，即使用啟發式函式來評價到達目標的剩余代價
因為是深度優先演算法，記憶體使用率低于A*搜索
但是不同于標準的迭代加深搜索，它集中于探索最優希望的節點，因此不會去搜索樹任何處的同樣深度
迭代加深深度優先搜索：使用搜索深度作為每次迭代的截止值
迭代加深A*搜索：使用資訊更豐富的評價函式
3.6 啟發函式
對于8數碼難題通常有2個候選：h1 錯位棋子的個數 ；h2 所有棋子到目標的曼哈頓距離之和
3.7 小結
求解一個問題就是一系列動作，并且搜索是為達到目標尋找這些動作的程序
無資訊搜索亦被稱為盲目搜索：其代表性演算法是寬度優先、一致代價、以及深度優先
有資訊搜索也被稱為啟發式搜索：最佳優先搜索依賴于評價函式，其特例是貪婪搜索和A*搜索
時間和空間復雜性是搜索演算法的一些關鍵點
4 超越經典搜索
之前討論了一個單一類別的問題,其解決方案是具有如下特點的一系列動作：可觀測、確定性、已知環境，這稱為經典搜索
本章討論更接近現實的，超越經典搜索：區域搜索和群體智能
經典搜索：系統地探索問題的空間
該系統性是由以下方法得到：在記憶體中保持一潭訓多條路徑，并且在沿著該路徑的每個點上記錄哪些已被探索過；目標找到時，該路徑也就構成問題的一個解
然而在許多問題中到達目標的路徑是無關緊要的
區域搜索是一種不同于經典搜索的演算法，它不介意什么路徑
區域搜索演算法使用一個當前節點（而不是多條路徑），并且通常僅移動到該節點相鄰的節點
通常，搜索后不保留該路徑
區域搜索有2個優點：使用很少記憶體；在大的或者無限（連續）狀態空間中，能發現合理的解
除了尋找目標外，區域搜索演算法對解決純優化問題也很有效
優化的目的是根據一個目標函式找到其最好的狀態
但是經典的搜索演算法并不一定適合優化問題
例如，達爾文進化論可以看做“試圖優化”，單對于這個問題，沒有“目標測驗”也沒有“路徑代價”
群體智能
環境中大量同類agent合作實作的
這樣的智能是分散式、自組織、并且在一個環境內分布
本章介紹2中群體智能演算法：蟻群優化（受蟻群行為所啟發，如：間接協調、覓食）、粒子群優化（受鳥群魚群的社會行為所啟發，如：群集、從眾）
4.1 區域搜索演算法
4.1.1 爬山法
是一種基于區域搜索家族的數學優化方法
是一種迭代演算法：開始選擇問題的一個任意解，然后遞增地修改該解的一個元素，若得到一個更好的解，則將該修改作為新的解；重復執行知道無法找到進一步的改善
大多數基本的區域搜索演算法都不保持一顆搜索樹
可通過區域搜索演算法對其搜索
一個完備的區域搜索演算法總能找到一個存在的目標
一個最優的區域搜索演算法總能找到一個全域的最小或最大值
爬山搜索演算法是最基礎的區域搜索演算法
它常常會朝著一個解快速的進展，因為通常很容易改善一個不良狀態
它往往被稱為貪婪區域搜索，因為它只顧抓住一個好的鄰接點的狀態，而不提前思考下一步該去哪兒
盡管貪婪是“七宗罪”之一，但是貪婪演算法往往表現的相當好
n皇后問題 區域搜索演算法解決n皇后問題，通常使用完整狀態形式化
爬山法弱點：爬山法是貪婪搜索演算法，它在下述情況容易被困：
區域最大值：高于相鄰節點但是低于全域最大值
高原：可能是一個平坦的區域最大值，或山肩
山嶺：結果是一系列區域最大值，很難爬行
針對這三個情況，需要隨機重啟功能來幫助逃脫，爭取找到全域最大值，因此出現各種爬山法變體：
隨機爬山法：在向上移動的程序中隨機選擇；選擇的概率隨向上移動的斜度而變化，與最陡爬山相比，收斂速度通常較慢
首選爬山法：它通過隨機生成后繼節點來實作隨機法，直到生成一個比當前狀態好的點，當某個狀態有許多后繼時，用此策略為好
隨機重啟爬山法：它好于其他爬山搜索方法，從隨機生成的初始狀態直到找到目標，它十分完備，概率接近1，因為他將生成一個目標狀態作為初始狀態，如果每次爬山搜索成功的概率為p，則重啟需要的期望值為1/p
4.1.2 區域束搜索
在記憶體中保持1個節點似乎對記憶體限制有些極端，而區域束搜索則保持k個節點
首先開始于k個隨機生成的狀態，每一步生成k個后繼狀態，如果命中則停止，否則從完成串列選k個最好的繼續
在區域束搜索中，有用的資訊能夠在并行搜索執行緒中傳遞
例子：經典的TSP問題，即旅行售貨員問題
區域束搜索的變體：
隨機束搜索：區域束搜索會很快的集中在狀態空間的某個小區域，使得搜索代價比爬山法更昂貴；隨機束搜索模仿隨機爬山法，有助于緩解這個問題；它不是在完成表中選擇k個最好后繼節點，而是以選擇后繼節點的概率是其值的遞增函式，來隨機的選擇k個節點；有點類似于自然隨機的程序
4.1.3 禁忌搜索
是一種元啟發式演算法，用于解決組合優化問題
它使用一種區域搜索或鄰域搜索程序，從一個潛在的解x到改進的相鄰解x‘之間反復移動，知道滿足某些停止條件
禁忌表
禁止策略
釋放策略
短期策略
可以禁忌搜索解決的問題
最小生成樹問題
4.2 優化與進化演算法
模擬退火
模擬退火是一種給定函式逼近全域最優解的概率方法，發表于1953年
具體來說，是一種在大搜索空間逼近全域最優解的元啟發式方法
初始解：使用啟發式方法生成，隨機選擇
相鄰節點：隨機生成，當前解的變異
接受條件：相鄰節點具有較低代價值，具有較高代價的相鄰節點則以概率p接受
停止判據：解具有比閾值低的數值，已達到最大迭代次數
遺傳演算法
遺傳演算法的一些要素是1960年代提出
它是一種模仿自然選擇程序的搜索啟發式演算法
該演算法是隨機束搜索的一個變型，其中后繼節點是由兩個父輩狀態的組合而不是修改單一狀態生成的
其處理程序是有性繁殖而不是無性繁殖
屬于進化演算法的大分類
該演算法采用自然進化所派生的技法來生成優化問題的解，例如：遺傳、突變、選擇以及雜交
該演算法開始時具有一組k個隨機生成的狀態，稱為種群，每個單個狀態稱為個體，每個個體通常由一組字符一般為01字串，如八皇后的個體
演算法偽代碼
4.3 群體智能
蟻群優化
是一種解決計算問題的概率技術，可以用于發現一個圖上的最佳路徑
該演算法是受螞蟻在蟻巢和食物之間尋找路徑的行為啟發
蟻群優化的概念：
螞蟻從蟻巢到事物源之間盲目游蕩：
最短路徑是通過費洛蒙嗅跡發現的
每個螞蟻隨機的移動
費洛蒙就遺留在路徑上
螞蟻覺察到前面螞蟻的路徑，跟隨而去
路徑上更多的費洛蒙增加該路徑的概率
蟻群優化演算法：
在路徑上積累“虛擬”嗅跡
開始時隨機選擇某個節點
隨機選擇某一路徑：基于從初始節點至合適路徑上出現嗅跡的量；具有較多嗅跡的則有較高的概率
重復直到更多螞蟻在每個回圈都選擇同一個路徑
蟻群演算法解決旅行售貨員問題
TSP問題是一個組合優化問題中的NP難問題，在運籌學和理論計算科學中非常重要
蟻群演算法可用于解決：進度安排問題、車輛安排問題、分派問題、納米物理設計中的設備量尺問題、影像處理中的邊緣檢測、分類、資料挖掘
粒子群優化
受魚類和鳥類的社會行為啟發
采用若干粒子構成一個圍繞搜索空間移動的群體來尋找最優解
搜索空間的每個粒子根據它自己的飛行經驗和其它粒子的飛行經驗調整它的“飛行”
人工神經元網路ANN與PSO
ANN是一種大腦簡單模型的計算泛型，而反向傳播演算法是訓練ANN的最受歡迎的方法之一
有若干論文報告了采用粒子群優化來替代反向傳播演算法
4.4 小結
區域搜索：爬山法在完整狀態形式化上進行操作；區域束搜索法保持k個狀態的軌跡；禁忌搜索采用一種帶約束的鄰域搜索，
優化與進化演算法：模擬退火在大搜索空間逼近全域最優解；遺傳演算法模仿自然選擇的進化程序，
群體智能：蟻群優化可以尋找圖的最好路徑；粒子群優化通過迭代來改善一個候選解，
5 對抗搜索
去考察這樣一類會出現的問題，當我們在某個世界試圖預先謀劃時，其他智能體也在做相反的謀劃
5.1 博弈
搜索與對抗搜索
對抗搜索通常稱為博弈
零和博弈
經典例子：囚徒困境 相關困境理論
博弈有趣但很難解決
博弈，像現實世界，當無法算計出最優決策時，需要決策理論
超過人類的是完備性資訊，未超過人類的往往是隨機游戲
5.2 博弈中的最優決策
最優解
最小最大定理 對于一個零和博弈，可以使得對手最大收益最小和使得自身最大損失最小
對抗搜索的最優解
最小最大決策的特性：
時間復雜性O(b^m）
空間復雜性O(bm)演算法每次生成所有動作 O(m)演算法每次生成一個動作
b分支因子（每個點的合法走子） m任一節點的最大深度
5.3 Alpha-Beta剪枝
博弈狀態的樹隨著深度呈現指數增長，我們不能消除這種指數，但是可以將它減掉一半
α-β剪枝：是一種搜索演算法，旨在削減由minimax演算法評價的節點數量
為什么稱為α-β剪枝：
α：沿著max路徑上的任意選擇點，迄今為止我們已經發現的最高峰
β：沿著min路徑上的任意選擇點，迄今為止我們發現的最低值
搜索依次完成如下動作：邊搜索邊更新αβ值，并且一旦得知當前節點的值比max或min的α或β值更差，則在該節點減去其余分支
α-β剪枝可以應用于任意深度的樹，并且可以減去整個子樹而非葉節點
一般原則：設某個玩家移動到樹的節點n，若玩家n的父節點或更上層有更好的節點m，則玩家沒必要抵達n
5.4 不完備資訊的實時決策
minimax演算法生成整個博弈空間
α-β剪枝演算法則允許我們剪去大部分
然而，α-β仍然需要搜索抵達終端狀態的所有路徑，至少是搜索空間的一部分
這個深度通常是不實際的，因為移動必須在合理的時間內完成
應用啟發式評價函式：香農提出，程式應該早一些剪斷搜索，并在搜索中對狀態應用啟發式評價函式，有效地將非終端節點轉換為終端葉節點
建議用EVAL來替代UTILITY（EVAL是一個啟發式評價函式，用于估計位置的效用），用CUTOFF-TEST來替代TERMINAL-TEST(CUTOFF-TEST確定何時應用EVAL函式)
評價函式計算時間一定不能太長
5.5 隨機博弈
例子：西洋雙陸棋
隨機博弈沒有極大極小值，只能計算期望值
期望極大極小值
5.6 蒙特卡洛方法
alphaGo演算法：
兩個深度神經元網路：價值網路（用于評估棋局）、策略網路（用于選擇走子）
蒙特卡羅搜索樹：將蒙特卡羅仿真與價值和策略網路相結合
強化學習：用于改進博弈水平，通過自我對弈訓練
將深度神經元網路和樹搜索有機結合，并且用大量棋局訓練
蒙特卡羅方法是一種工程方法，是一大類計算演算法，它憑借重復隨機采樣來獲得數值結果
當難以或無法使用其它數學方法時候，非常有效
它們往往遵循以下特定模式：1）定義一個可能的輸入域2）從該域的一個概率分布隨機生成輸入3）對該輸入進行確定性計算4）將結果匯聚
例子：用蒙特卡羅方法計算π
蒙特卡羅搜索樹MCTS和minimax一樣，每個節點對應于一個博弈狀態，不同于minimax的地方，節點的值通過蒙特卡羅仿真來估值
5.7 小結
Minimax演算法可以通過博弈樹的深度優先計算選擇最佳移動，
Alpha–beta演算法通過剪掉不相關子樹來得到更高的效率
啟發式評價函式對于博弈的不完全實時決策很有效，
隨機博弈是具有概率轉換的動態博弈
蒙特卡羅樹搜索將蒙蒙特卡羅樹仿真與博弈樹搜索相結合，
6 約束滿足問題
6.1 定義約束滿足問題CSP
約束滿足問題是數學問題，被定義為其狀態必須滿足若干約束和限制的一組物件
CSP是AI和運籌學的共同研究課題
標準搜索 vs CSP：
標準搜索問題其狀態是原子的不可分割的，一個沒有內部結構的黑盒子；而CSP采用因子表示，是一系列變數，每個有相應的值，CSP可以發揮狀態結構的長處，采用一般用途而不是問題特有的啟發式
為什么研究CSP：CSP通常呈現高復雜性，需要降啟發式與組合搜索方法相結合
有如下形式：布爾可滿足性問題SAT,可滿足性模理論SMT，答案集編排ASP，，
可建模為CSP的例子：8皇后、地圖著色、密碼算數、數獨
形式化定義為三元組<X,D,C> 分別是變數集合、范疇集合、約束集合
四色定理
CSP是對很多問題的一種自然表示
與其他搜索技術相比，CSP求解系統更容易解決問題
CSP求解系統比狀態空間搜索更快，因為它可以快速排除大的搜索空間樣本
算式謎：一種數學游戲，目標是識別出每個字母的值，也被成為字母算數、覆面算、文字加法、隱算數
用CSP解決算式謎
CSP也是計算復雜性理論和有限模型論所要研究的問題
有限范疇的CSP問題常用搜索解決，常用技法：約束傳播、回溯、區域搜索
6.2 CSP的約束傳播
常規的狀態空間搜索所能做的唯一一件事就是搜索
CSP則能做搜索，還能做一種特殊型別的推理，稱為約束傳播
約束傳播用途：可以轉化為等價的更易解決的問題；可以證明問題的可滿足性不可滿足性
不同型別的區域一致性：節點一致性、弧一致性、路徑一致性、k一致性
最流行的約束傳播演算法AC-3演算法，支持弧一致性
k一致性，當k=1等同節點一致性，k=2，等同弧一致，k=3，等同路徑一致性
6.3 CSP的回溯搜索
是一種深度優先搜索演算法，用于查找某些計算問題的答案，尤其是CSP
回溯搜索遞增地構建解的候選，而且一旦確定部分候選c不能成為一個合法的解，就將c拋棄（回溯）
例子：8皇后
相關優化：
變數與值得排序？（最小剩余值、程度啟發式、最少約束值啟式）
搜索中推理？
當搜索到一個違反約束的賦值時該搜索能否避免重復這個失敗？智能回溯
6.4 CSP中的區域搜索
區域搜索演算法在CSP問題中也很有效，采用完整狀態形式化
最小沖突啟發式：對很多CSP問題有奇效，在n皇后問題上，最小沖突的運行時間與問題大小基本無關，甚至對于百萬皇后問題，在初始賦值后，平均50步左右就能得到解
約束加權：能聚焦重要的約束
6.5 問題的結構
問題分解
獨立子問題
樹結構問題
簡化約束圖為樹形結構：割集調節、樹分解
6.6 小結
CSPs問題用一組變數/值對表示狀態，并且用一組變數的約束表示條件，
節點、弧、路徑、以及k一致性使用約束來推斷哪個變數/值對是一致的，
回溯搜索以及采用最少沖突啟發式的區域搜索被用于CSPs，
割集調節和樹分解可被用于將約束圖簡化為樹結構，
7 知識推理
7.1 概述
資料、資訊、知識、智慧
知識庫和知識庫系統
一個知識庫系統由知識庫和推理引擎組成
7.2 知識表示
知識表示
知識表示的核心問題：
原語：用于表示知識的基礎框架，例如語意網路、一階邏輯等等
元表示
不完備性：將確定性因子與規則和結論相關聯
共性與事實
表現的充分性
典型的知識表示方法：貝葉斯網路、一階邏輯、基于Frame的系統、本體、產生式系統、腳本、語意網路
語意網路：表示概念間語意關系的網路，它是由節點和弧組成的有向或無向圖，其中節點表示概念，弧表示概念間的語意關系
用lisp語言表示語意網路
語意網路無法表示如否定、析取、或者一般的非分類知識，難以駕馭大型領域，并且不能很好的表現性能或者元知識
7.3 邏輯表示
程序性與陳述性方法
命題邏輯也叫命題演算，使用邏輯連接詞，處理簡單的陳述性命題
一階邏輯也叫一階命題演算，此外，還使用限量詞、等量詞、以及謂詞（通常與集合相關聯）
一階邏輯的形式規則：項、公式
形式規則可以用于書寫項和公式的形式寫法
形式規則通常是背景關系無關的，即每個產生式左側有一個單一的符號
項：變數、常數、函式
公式：謂詞符號、等量詞、否定、二元連接、限量
Prolog語言起源于一階邏輯，是一種通用的邏輯編程語言，已經被用于定理證明、專家系統、自然語言處理等等
不同于其他編程語言，Prolog是陳述性的：程式邏輯由關系來表達，表示為事實與規則
7.4 本體工程
本體：上層本體、領域本體、混合本體
本體的成分：個體、類、屬性、關系、功能項、限定、規則、公理、事件
本體工程：一個研究構建本體的方法和方法學的領域
兩類本體語言：傳統語法的本體語言（代表是COMMON LOGIC）、標記式的本體語言（最常用的是XML）
7.5 貝葉斯網路
不確定性知識
智能體的進化：問題求解、推理、規劃以及學習
智能體可能需要處理不確定性，由于部分可觀察性和不確定性問題
在不確定的環境下做出決策，需要概率論、效用論、決策論
理性決策
貝葉斯定理
貝葉斯網路：采用有向無環圖DAG表示，也稱置信網路、概率網路、因果網路
一個貝葉斯網路表示一組隨機變數和他們的條件依賴關系，例如它可以表示疾病與癥狀之間的概率關系
兩種觀點：將該網路視為一種聯合概率分布的表示；將其視為一組條件獨立陳述句的一種編碼
如何構建貝葉斯網路
貝葉斯網路遠比全聯合分布緊湊
節點排序
條件獨立關系
7.6 小結
知識表示捕捉資訊，其代表性的方法是：語意網路、一階邏輯、產生式系統、本體和貝葉斯網路，
本體工程是研究構建本體的方法和方法學，
不確定性知識可以用概率論、效用論和決策論來處理，
貝葉斯網路基本上可以表示任意的全聯合概率分布，并且在許多情況下可以做的非常簡潔，
8 經典與現實世界規劃
8.1 規劃問題
動作是agent的一個關鍵部分
規劃是找到一個計劃：它產生從任何初始狀態到達一個目標狀態的一系列動作，即制定一個計劃到達既定目標
什么是經典規劃：具有如下特征：完全可觀測、唯一已知初始狀態、靜態環境、確定性動作、每次僅一個動作、單一智能體
問題求解agent vs 規劃agent
PDDL試圖對AI規劃語言標準化，與1998年首次開發
定義規劃任務的三要素：狀態、動作、目標
注意謬誤動作和矛盾動作
待續
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/38996.html
標籤：其他