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年首次開發
定義規劃任務的三要素：狀态、動作、目标
注意謬誤動作和沖突動作
待續
作者：九命貓幺
部落格出處：http://www.cnblogs.com/yongestcat/
歡迎轉載，轉載請标明出處。
如果你覺得本文還不錯，對你的學習帶來了些許幫助，請幫忙點選右下角的推薦