Algorithm第4章

算法2035主講：王紅梅知識目標(biāo)：能理解計算機算法的基本概念和算法表示，能描述常見的排序和搜索算法，能理解和掌握機器學(xué)習(xí)算法、神經(jīng)網(wǎng)絡(luò)算法等人工智能核心算法。能力目標(biāo)：能結(jié)合現(xiàn)實生活判斷不同應(yīng)用可能采用的算法種類；能結(jié)合實際，分析其算法建立的過程和方法。素養(yǎng)目標(biāo)：培養(yǎng)學(xué)生的算法意識和思維能力。4.14.24.34.4算法那些事算法概述搜索算法機器學(xué)習(xí)目錄CONTENTS4.5神經(jīng)網(wǎng)絡(luò)與深度學(xué)習(xí)擴展：循環(huán)神經(jīng)網(wǎng)絡(luò)4.64.14.24.34.4算法那些事算法概述搜索算法機器學(xué)習(xí)目錄CONTENTS4.5神經(jīng)網(wǎng)絡(luò)與深度學(xué)習(xí)擴展：循環(huán)神經(jīng)網(wǎng)絡(luò)4.6討論：（1）你是否聽說或了解過算法？如果有，請列舉（2）你對算法的認(rèn)識是什么？A.解決問題的方法B.數(shù)學(xué)問題C.很神秘的問題D.計算機程序?qū)崿F(xiàn)的思想基礎(chǔ)

其實算法和我們的日常生活緊密聯(lián)系在一起，無論是高考錄取、火車票購買、商品推薦、地圖導(dǎo)航，還是現(xiàn)在的人工智能大模型等都離不開算法。

日常中像抖音（國際名TikTok）之所以受歡迎，有很大一部分原因是因為它的算法特別好，能準(zhǔn)確把用戶期待的內(nèi)容精準(zhǔn)推薦給用戶。小智的手寫字平板電腦

小智在課堂上一邊記錄人工智能課程的筆記，一邊看著這臺平板電腦把自己手寫的字識別出來，他在想？？？討論：找一個用平板電腦做筆記的同學(xué)，來分享一下是否了解平板電腦是怎么把寫的字識別出來的？ArtificialIntelligenceandFuture人工智能與未來2035主講：王紅梅Algorithm第4章

算法2035主講：王紅梅4.14.24.34.4算法那些事算法概述搜索算法機器學(xué)習(xí)目錄CONTENTS4.5神經(jīng)網(wǎng)絡(luò)與深度學(xué)習(xí)擴展：循環(huán)神經(jīng)網(wǎng)絡(luò)4.64.2.1什么是算法？4.2.2如何描述算法？4.2.3算法實現(xiàn)案例：冒泡算法4.2.4實現(xiàn)算法常用的數(shù)據(jù)結(jié)構(gòu)4.2.5算法和程序的關(guān)系

算法是指計算機等設(shè)備用來進行計算或者解決問題的方法和步驟。4.2.1什么是算法？算法和食譜類比聽著好高深哦！可到底什么是算法！4.2.1什么是算法？找2組同學(xué)，每組5個人到教室前面再找2個同學(xué)，分別對上面的兩組進行排列問全體同學(xué)對排列滿意嗎？讓排列的同學(xué)分享他們?yōu)槭裁匆@樣排，他們是怎么做到的？4.2.1什么是算法？-【場景模擬】學(xué)生一般是這么排的...4.2.1什么是算法？-【場景模擬】12354從低到高54321從高到低12345但這是人的思維，而不是機器思維！那機器思維是啥？5個人，按高低個的排列需要排4輪，第一輪：全5個人，比較4次，找出最高個子，排在5個人的最后4.2.1什么是算法？-【場景模擬】第一次比較。每次比較高的后移。5個人，按高低個的排列需要排4輪，第一輪：全5個人，比較4次，找出最高個子，排在5個人的最后4.2.1什么是算法？-【場景模擬】第二次比較。每次比較高的后移。5個人，按高低個的排列需要排4輪，第一輪：全5個人，比較4次，找出最高個子，排在5個人的最后4.2.1什么是算法？-【場景模擬】第二次比較。每次比較高的后移。5個人，按高低個的排列需要排4輪，第一輪：全5個人，比較4次，找出最高個子，排在5個人的最后4.2.1什么是算法？-【場景模擬】第三次比較。每次比較高的后移。5個人，按高低個的排列需要排4輪，第一輪：全5個人，比較4次，找出最高個子，排在5個人的最后4.2.1什么是算法？-【場景模擬】第四次比較。每次比較高的后移。5個人，按高低個的排列需要排4輪，第一輪：全5個人，比較4次，找出最高個子，排在5個人的最后4.2.1什么是算法？-【場景模擬】第四次比較。每次比較高的后移。5個人，按高低個的排列需要排4輪，第一輪：全5個人，比較4次，找出最高個子，排在5個人的最后4.2.1什么是算法？-【場景模擬】第四次比較。每次比較高的后移。5個人，按高低個的排列需要排4輪，第二輪：前4個人，比較3次，找出最高個子，排在4個人的最后4.2.1什么是算法？-【場景模擬】5個人，按高低個的排列需要排4輪，第二輪：前4個人，比較3次，找出最高個子，排在4個人的最后4.2.1什么是算法？-【場景模擬】5個人，按高低個的排列需要排4輪，第三輪：前3個人，比較2次，找出最高個子，排在3個人的最后4.2.1什么是算法？-【場景模擬】5個人，按高低個的排列需要排4輪，第四輪：前2個人，比較1次，找出最高個子，排在2個人的最后4.2.1什么是算法？-【場景模擬】5個人，按高低個的排列需要排4輪，全部完成排序4.2.1什么是算法？-【場景模擬】5個人，按高低個的排列需要排4輪，全部完成排序4.2.1什么是算法？-【場景模擬】這種對一件事情的處理思路和方法就是算法或算法指的是解決問題或完成任務(wù)的一系列步驟集合。4.2.1什么是算法？-【場景模擬】討論：生活中還有哪些算法呢？你都是怎么描述的呢？請舉例自己班的學(xué)生日常生活中處處都有。如樂譜是樂隊演奏的算法，菜譜是做菜肴的算法，珠算口訣是使用算盤的算法。設(shè)計出一個解決問題的算法，也需要用能被算法執(zhí)行者理解的形式加以呈現(xiàn)，才能被算法執(zhí)行者理解并執(zhí)行。算法的這種呈現(xiàn)就稱為算法的描述。如何描述算法4.2.2如何描述算法?常見的算法描述方式：1.自然語言描述2.流程圖描述3.偽代碼描述4.程序設(shè)計語言描述4.2.2如何描述算法？1.自然語言

自然語言描述就是用我們熟悉的語言來描述算法，在進行3個整數(shù)求最大值的問題中，我們可以這樣描述:我們把求最大值的三個整數(shù)，分別放在A，B，C中，把最大值命名為Max。第一步：我們先假定A是最大值，把A給Max；第二步：把B和Max比較，如果B大于Max，就把B再次賦給Max，否則不變；第三步：把C和Max比較，如果C大于Max，就把C再次賦給Max，否則不變；第四步：結(jié)束，輸出Max的值，就是最大值。4.2.2如何描述算法？2.流程圖

常說一圖勝千言，流程圖就是算法的圖形化表示了，為了人人都能看懂流程圖，往往對流程圖中的符號約定如下：（1）流程圖的開始和結(jié)束，用橢圓框表示；（2）平行四邊形框表示輸入輸出框，用于輸入數(shù)據(jù)和輸出數(shù)據(jù)；（3）矩形框用于表示業(yè)務(wù)處理；（4）菱形框表示判斷，判斷有兩個分支（滿足條件或者不滿足條件）；（5）箭線表示流程的方向。4.2.2如何描述算法？求3個整數(shù)最大值流程圖描述3.編程語言

就是用一種能在計算機中實現(xiàn)的編程語言來實現(xiàn)問題的解決，找到問題的答案。當(dāng)然你也可能還沒有學(xué)過相應(yīng)的編程語言，也沒有關(guān)系，你只要知道可以用程序語言實現(xiàn)就可以了。4.2.2如何描述算法？用python來實現(xiàn)求三個數(shù)A，B，C最大值，此代碼不能直接復(fù)制，可查看源文件。#定義三個數(shù)

#開頭的表示注釋，幫助理解，但程序不執(zhí)行A=18B=25C=9#先把A的值給MaxMax=A#開始與B進行比較ifB>Max:

Max=B#開始與C進行比較ifC>Max:

Max=C#輸出最大值print(f"三個數(shù)A,B,C中的最大值是:{Max}")4.偽代碼

是一種介于自然語言和編程語言之間的算法描述方式。使用類似編程語言的語法，但不嚴(yán)格遵守具體編程語言的語法規(guī)則。4.2.2如何描述算法？#初始化三個數(shù)值設(shè)定A為18設(shè)定B為25設(shè)定C為9#預(yù)設(shè)最大值為A將Max初始化為A#比較B與當(dāng)前最大值若B大于Max，則更新Max為B#比較C與當(dāng)前最大值若C大于Max，則更新Max為C#輸出最終的最大值打印"三個數(shù)A,B,C中的最大值是:"緊接著顯示Max的值用偽代碼描述求三個數(shù)A，B，C最大值分組練習(xí)：把上面5人排序的算法描述出來，每組完成一種即可，然后下節(jié)課分享討論

在算法中，尤其基礎(chǔ)算法中，冒泡排序是一個經(jīng)典的算法，主要用來解決數(shù)據(jù)的排序問題。我們以數(shù)據(jù)18，13，25，85，9，45為例，進行升序排列。4.2.3算法實現(xiàn)案例：冒泡算法4.2.3算法實現(xiàn)案例：冒泡算始第二次比較，不需要下較，大的下三次比較，不需要下沉比較，大的下四次比較，需要下沉比較，大的下沉第五次比較，需要下較，大的下一次比較，需要下沉比較，大的下輪結(jié)果

6個整數(shù)冒泡排序第一輪，5次比較

6個整數(shù)冒泡排序第二輪，4次比較4.2.3算法實現(xiàn)案例：冒泡算一次比較，不需要下沉比較，大的下沉第二次比較，不需要下較，大的下沉第三次比較，需要下較，大的下較，大的下沉四次比較，不需要下輪結(jié)果6個整數(shù)冒泡排序第三輪，3次比較4.2.3算法實現(xiàn)案例：冒泡算始比較，大的下一次比較，不需要下沉比較，大的下二次比較，需要下沉1813258594518132585945三輪結(jié)果比較，大的下沉第三次比較，不需要下沉6個整數(shù)冒泡排序第四輪，2次比較4.2.3算法實現(xiàn)案例：冒泡算較，大的下沉第一次比較，需要下較，大的下沉第二次比較，不要下四輪結(jié)果6個整數(shù)冒泡排序第五輪，1次比較4.2.3算法實現(xiàn)案例：冒泡算法原始181325859456個整數(shù)冒泡排序第五輪，1次比較4.2.3算法實現(xiàn)案例：冒泡算法原始1813258594518132585945第一次比較，不要下沉比較，大的下果在Python中具體的實現(xiàn)演示，執(zhí)行代碼看源文件，#定義一個包含六個未排序整數(shù)的列表numbers=[18,13,25,85,9,45]#實現(xiàn)冒泡排序算法n=len(numbers)

#獲取列表的長度foriinrange(n):

#外層循環(huán)，控制比較的輪數(shù)

forjinrange(0,n-i-1):

#內(nèi)層循環(huán)，控制每輪中相鄰元素的比較

ifnumbers[j]>numbers[j+1]:

#如果當(dāng)前元素大于下一個元素

numbers[j],numbers[j+1]=numbers[j+1],numbers[j]#交換這兩個元素#輸出排序后的列表print("使用冒泡排序算法對列表進行排序后的結(jié)果為：",numbers)4.2.3算法實現(xiàn)案例：冒泡算法為實現(xiàn)前面6個數(shù)排序算法，需要一個像抽屜格子一樣的數(shù)據(jù)結(jié)構(gòu)：數(shù)組程序=算法+數(shù)據(jù)結(jié)構(gòu)4.2.4實現(xiàn)算法常用的數(shù)據(jù)結(jié)構(gòu)a0a1a2a3a4a5組織結(jié)構(gòu)樹學(xué)校各個場所圖4.2.4實現(xiàn)算法常用的數(shù)據(jù)結(jié)構(gòu)討論：為什么這么簡單的問題，計算機處理起來這么復(fù)雜？請舉例自己班的學(xué)生第一輪：全5個人，比較4次，找出最高個子，排在5個人的最后第二輪：前4個人，比較3次，找出最高個子，排在4個人的最后第三輪：前3個人，比較2次，找出最高個子，排在3個人的最后第四輪：前2個人，比較1次，找出最高個子，排在2個人的最后人腦高度發(fā)達，能處理復(fù)雜的問題計算機只能通過簡單的電路處理簡單問題。因此，需要把復(fù)雜問題簡單化或邏輯化。第一輪：全5個人，比較4次，找出最高個子，排在5個人的最后第二輪：前4個人，比較3次，找出最高個子，排在4個人的最后第三輪：前3個人，比較2次，找出最高個子，排在3個人的最后第四輪：前2個人，比較1次，找出最高個子，排在2個人的最后計算思維

通過上面的學(xué)習(xí)，你可能會產(chǎn)生算法和程序是否有聯(lián)系的疑問，實際上他們既有聯(lián)系，又有區(qū)別，這種聯(lián)系和區(qū)別可以通過表來理解。4.2.5算法和程序的關(guān)系算法程序概念算法是解決問題的方法程序是算法在某種具體編程語言如Python中的具體實現(xiàn)對數(shù)據(jù)的依賴算法可以沒有數(shù)據(jù)支持程序必須需要數(shù)據(jù)支持對設(shè)備的依賴算法不依賴任何設(shè)備程序運行必須要在計算機等設(shè)備上抽象程度問題的描述，高度抽象問題的實現(xiàn)，比較具體使用對象算法師等程序員等關(guān)系算法是程序的基礎(chǔ)程序是算法的實現(xiàn)ArtificialIntelligenceandFuture人工智能與未來2035主講：王紅梅Algorithm第4章

算法2035主講：王紅梅4.14.24.34.4算法那些事算法概述搜索算法機器學(xué)習(xí)目錄CONTENTS4.5神經(jīng)網(wǎng)絡(luò)與深度學(xué)習(xí)擴展：循環(huán)神經(jīng)網(wǎng)絡(luò)4.6討論：現(xiàn)實生活中你用過那些搜索？你是否了解這些搜索背后的算法呢？圖書館查書

小智今天計劃外出一趟，習(xí)慣性的用地圖導(dǎo)航一下，和之前不一樣的是，這次導(dǎo)航小智多了個想法，由于開始學(xué)習(xí)算法了，小智就琢磨地圖是怎么在眾多路徑中找到最短路徑的？又是怎么實現(xiàn)最快達到的呢？其實地圖導(dǎo)航的基本算法是Dijkstra算法和A*（AStar）搜索算法，分別用來解決小智如何找到最短路徑和如何實現(xiàn)快速達到的問題。

4.3.1基于圖的搜索1.圖的構(gòu)建

你每天是不是往返于學(xué)校的宿舍、餐廳、教學(xué)樓、圖書館、實驗樓和運動場等場地之間，各個場地之間的連線表示它們之間有路，這樣就構(gòu)成了無向圖。A：代表宿舍，用B代表餐廳，用C代表圖書館，用D代表教學(xué)樓，E代表實驗樓，F(xiàn)代表運動場；各個場所的距離用連線上的數(shù)字表示（也稱為權(quán)值）。注意：這里線的長短并不代表距離的遠(yuǎn)近，數(shù)字才代表距離的遠(yuǎn)近。

4.3.1基于圖的搜索2.圖的搜索

圖的搜索指的就是從圖的某個頂點開始，到達其它頂點的方法和過程，如圖中，從A點出發(fā)，分別達到B、C、D、E、F頂點的過程。根據(jù)搜索的順序不同，圖的搜索算法可分為廣度優(yōu)先搜索和深度優(yōu)先搜索這兩種。實際上這兩種方法即可以進行圖的搜索，也可以進行樹的搜索。4.3.2廣度優(yōu)先搜索*廣度優(yōu)先搜索（Breadth-FirstSearch,BFS）是一種用于遍歷或搜索樹或圖的算法。該算法從根節(jié)點開始，逐層遍歷樹或圖的分支，直到找到目標(biāo)節(jié)點或無法再前進為止。（每一層有點像海浪的一波）4.3.2廣度優(yōu)先搜索*6個頂點組成的圖如（a），現(xiàn)在從A點開始進行搜索，設(shè)想一下，組成各個點之間的線可以伸縮，我們拎著A點，其它頂點位置根據(jù)和A的遠(yuǎn)近自然下垂，效果如圖（b）所示。當(dāng)然，你也發(fā)現(xiàn)了，只是重新調(diào)整一下各個頂點的位置，它們的結(jié)構(gòu)并沒有改變。4.3.2廣度優(yōu)先搜索*搜索的步驟如下，藍色是當(dāng)前訪問節(jié)點，灰色是已經(jīng)訪問節(jié)點：4.3.3深度優(yōu)先搜索*深度優(yōu)先搜索和廣度優(yōu)先搜索一樣，都是對圖進行搜索的算法。不同的是深度優(yōu)先搜索會沿著一條路徑不斷往下搜索直到不能再繼續(xù)為止，然后再折返，開始搜索下一條路徑。4.3.3深度優(yōu)先搜索*同樣，為了方便理解，我們對原始圖（a）以A為起點，根據(jù)能探索的深度來進行調(diào)整形狀，同樣只是調(diào)整位置，并沒有改變結(jié)構(gòu)，4.3.3深度優(yōu)先搜索*深度優(yōu)先搜索詳細(xì)步驟：4.3.3深度優(yōu)先搜索*深度優(yōu)先搜索詳細(xì)步驟：4.3.4最短路徑算法Dijkstra最短路徑算法，屬于廣度優(yōu)先搜索的一種。該算法是求從一個頂點到其余各頂點的最短路徑算法，解決的是有權(quán)圖中最短路徑問題。Dijkstra算法的策略實際上采用貪心算法策略，貪心算法的基本思想是每一步都選擇當(dāng)前狀態(tài)下的最優(yōu)選擇，希望通過局部最優(yōu)解的累積最終得到全局最優(yōu)解?。4.3.4最短路徑算法策略(貪心算法的一種）：每次選擇一個點，這個點滿足兩個條件：1、未被訪問過；2、到源點距離最短這個點就是一個全局最優(yōu)解！后續(xù)這個點到源點的距離是不需要修改的！！通過局部最優(yōu)解獲得全局最優(yōu)解。求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a，b）c5（a，c）d∞e∞f∞最短路徑∞表示沒有直接相連的點。最短路徑就是那些點最短距離eabcdf21541134314.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a，b）c5（a，c）d∞e∞f∞最短路徑2（a，b）∞表示沒有直接相連的點。最短路徑就是那些點最短距離eabcdf21541134314.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）e∞∞f∞∞最短路徑2（a,b）∞表示沒有直接相連的點。最短路徑就是那些點最短距離eabcdf21541134314.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）e∞∞f∞∞最短路徑2（a,b）3（a,b,c）∞表示沒有直接相連的點。最短路徑就是那些點最短距離eabcdf21541134314.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）f∞∞4（a,b,c,f）最短路徑2（a,b）3（a,b,c）4（a,b,c,f）∞表示沒有直接相連的點。最短路徑就是那些點最短距離eabcdf2154113431由于,6（a,b,c,d）是，大于5（a,b,d），用短的距離4.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）f∞∞4（a,b,c,f）最短路徑2（a,b）3（a,b,c）4（a,b,c,f）∞表示沒有直接相連的點。最短路徑就是那些點最短距離eabcdf21541134314.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）f∞∞4（a,b,c,f）最短路徑2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）∞表示沒有直接相連的點。最短路徑就是那些點最短距離eabcdf2154113431f沒有去向的路徑，數(shù)據(jù)不更新4.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）f∞∞4（a,b,c,f）最短路徑2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）∞表示沒有直接相連的點。最短路徑就是那些點最短距離eabcdf21541134314.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）6（a,b,d,e）f∞∞4（a,b,c,f）最短路徑2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）eabcdf21541134314.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）6（a,b,d,e）f∞∞4（a,b,c,f）最短路徑2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）6（a,b,d,e）eabcdf21541134314.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）6（a,b,d,e）f∞∞4（a,b,c,f）最短路徑2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）6（a,b,d,e）eabcdf21541134314.3.4最短路徑算法求a到其他點的最短路徑。每次選距離a最近的點，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）6（a,b,d,e）f∞∞4（a,b,c,f）最短路徑2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）6（a,b,d,e）eabcdf211134.3.4最短路徑算法討論和分享：科學(xué)家故事：最短路徑算法發(fā)明人Dijkstra的故事4.3.5A*搜索算法Dijkstra算法求最短路徑的時候，會從離起點近的頂點開始，按順序求出起點到各個頂點的最短路徑，也就是說，一些離終點較遠(yuǎn)的頂點的最短路徑也會被計算出來，但這樣做，有時候是無用而且浪費時間的；你試想一下，如果你在鄭州，你的目的地是北京，你從鄭州搜索到上?；驈V州的路徑?jīng)]有太大價值。4.3.5A*搜索算法我們會發(fā)現(xiàn)廣度優(yōu)先搜索，當(dāng)數(shù)據(jù)量很大的時候，它的搜索性能就低下，如何進行優(yōu)化呢？在實際的應(yīng)用過程中，基于啟發(fā)式搜索的A*搜索就是常用的一種方法。A*搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標(biāo)。這樣可以省略大量無畏的搜索路徑，提高了效率。4.3.5A*搜索算法AB尋找一條從起點A到終點B的路徑，只能上下左右的移動，而且不能穿越障礙物。紅色的方塊是代表障礙物4.3.5A*搜索算法1111AB如果按照廣度優(yōu)先搜索的方法，它是朝4個方向進行搜索。搜索過的地方用灰色來標(biāo)注。4.3.5A*搜索算法22121122122AB按廣度優(yōu)先搜索，會從A點朝4個方向進行搜索。并且會標(biāo)記這4探索的方向為邊界，就是圖中綠色的部分。以這些邊界為檢索點重復(fù)進行。搜索過的地方用灰色來標(biāo)注。4.3.5A*搜索算法323212112212323AB按廣度優(yōu)先搜索，會從A點朝4個方向進行搜索。并且會標(biāo)記這4探索的方向為邊界，就是圖中綠色的部分。以這些邊界為檢索點重復(fù)進行。搜索過的地方用灰色來標(biāo)注。4.3.5A*搜索算法3234212112123234AB按廣度優(yōu)先搜索，會從A點朝4個方向進行搜索。并且會標(biāo)記這4探索的方向為邊界，就是圖中綠色的部分。以這些邊界為檢索點重復(fù)進行。搜索過的地方用灰色來標(biāo)注。4.3.5A*搜索算法3234521211221232345AB按廣度優(yōu)先搜索，會從A點朝4個方向進行搜索。并且會標(biāo)記這4探索的方向為邊界，就是圖中綠色的部分。以這些邊界為檢索點重復(fù)進行。搜索過的地方用灰色來標(biāo)注。4.3.5A*搜索算法32345621261122126323456AB按廣度優(yōu)先搜索，會從A點朝4個方向進行搜索。并且會標(biāo)記這4探索的方向為邊界，就是圖中綠色的部分。以這些邊界為檢索點重復(fù)進行。搜索過的地方用灰色來標(biāo)注。4.3.5A*搜索算法323456721267112212673234567AB按廣度優(yōu)先搜索，會從A點朝4個方向進行搜索。并且會標(biāo)記這4探索的方向為邊界，就是圖中綠色的部分。以這些邊界為檢索點重復(fù)進行。搜索過的地方用灰色來標(biāo)注。4.3.5A*搜索算法32345678212678112821267832345678AB按廣度優(yōu)先搜索，會從A點朝4個方向進行搜索。并且會標(biāo)記這4探索的方向為邊界，就是圖中綠色的部分。以這些邊界為檢索點重復(fù)進行。搜索過的地方用灰色來標(biāo)注。4.3.5A*搜索算法32345678212678911289212678932345678AB按廣度優(yōu)先搜索，會從A點朝4個方向進行搜索。并且會標(biāo)記這4探索的方向為邊界，就是圖中綠色的部分。以這些邊界為檢索點重復(fù)進行。搜索過的地方用灰色來標(biāo)注。4.3.5A*搜索算法AB最短路徑就是上面一次探索過的路徑。橘黃色方塊。可以看到廣度搜索算法是可以幫我們找到最短路徑的。4.3.5A*搜索算法AB不過有點傻。為什么說呢？因為它是沒有方向性的。在最壞的情況下可能需要找遍整個地圖才能找到最短路徑，那怎么有更好的方法呢？那就是我們接下來要說的A*算法。4.3.5A*搜索算法↑←→↓ABA*搜索不會去探索所有的邊界，而是去選擇當(dāng)前“代價”最低的邊界進行探索。也就是選擇一個有方向性的邊界進行探索。在四個方向的邊界中，而

才是“代價”最低的邊界?！?.3.5A*搜索算法路徑代價=當(dāng)前代價

（F-cost)+預(yù)估代價（G-cost)目前實際走的步數(shù)當(dāng)前方塊到終點方塊大概需要的步數(shù)作用是指導(dǎo)算法進行優(yōu)化搜索4.3.5A*搜索算法路徑代價=當(dāng)前代價

（F-cost)+預(yù)估代價（G-cost)歐氏距離（歐幾里得距離），就是兩組之間的直線距離，公式：(x1-x2)2+(y1-y2)2曼哈頓距離，就是兩點在豎直和水平方向上的距離總和公式為：∣x1-x2∣+∣y1-y2∣預(yù)估代價在預(yù)估距離時，常用方法4.3.5A*搜索算法1+61+61+41+6BA在四個方向的邊界中，計算路徑代價F+G（當(dāng)前代價+預(yù)估代價）。4.3.5A*搜索算法1+61+61+41+6AB選擇最低代價。4.3.5A*搜索算法1+62+51+61+42+31+62+5BA從最低代價的邊界出發(fā)，計算各個方向的路徑代價F+G（當(dāng)前代價+預(yù)估代價）。已經(jīng)探索過的用灰色標(biāo)注4.3.5A*搜索算法1+62+51+61+42+31+62+5BA選擇最低代價。4.3.5A*搜索算法1+62+53+41+61+42+33+21+62+53+4BA重復(fù)上面過程！4.3.5A*搜索算法1+62+53+41+61+42+33+21+62+53+4BA重復(fù)上面過程！4.3.5A*搜索算法1+62+53+44+31+61+42+33+24+11+62+53+44+3BA重復(fù)上面過程！4.3.5A*搜索算法1+62+53+44+31+61+42+33+24+11+62+53+44+3BA重復(fù)上面過程！4.3.5A*搜索算法1+62+53+44+35+21+61+42+33+24+101+62+53+44+35+2BA重復(fù)上面過程！4.3.5A*搜索算法1+62+53+44+35+21+61+42+33+24+101+62+53+44+35+2BA重復(fù)上面過程！，直到找到最短路徑！地圖導(dǎo)航在機器人技術(shù)中，搜索算法用于規(guī)劃機器人在空間中的移動路徑，以避免障礙物并高效地到達目的地。機器人路徑規(guī)劃物流運輸在物流和運輸領(lǐng)域，搜索算法可幫助確定最有效的配送路線，以最小化運輸成本和時間。在地理信息系統(tǒng)（GIS）中，搜索算法被廣泛應(yīng)用于路徑規(guī)劃和導(dǎo)航。例如，Dijkstra算法和A*搜索算法可用于找到兩點之間的最短路徑。4.3.6搜索算法應(yīng)用以這個為例，進行A*搜索的話，應(yīng)該如何進行呢？請舉例自己班的學(xué)生ABArtificialIntelligenceandFuture人工智能與未來2035主講：王紅梅Algorithm第4章

算法2035主講：王紅梅4.14.24.34.4算法那些事算法概述搜索算法機器學(xué)習(xí)目錄CONTENTS4.5神經(jīng)網(wǎng)絡(luò)與深度學(xué)習(xí)擴展：循環(huán)神經(jīng)網(wǎng)絡(luò)4.6哎呦，我的媽呀機器能學(xué)習(xí)，你信嗎？它怎么學(xué)呀！

需要先談?wù)勅斯ぶ悄?、機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)之間的關(guān)系人工智能機器學(xué)習(xí)深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)人工智能是一個很大的概念

人工智能、機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)之間的關(guān)系研究人工智能要用到各種數(shù)學(xué)算法，統(tǒng)稱為機器學(xué)習(xí)貝葉斯網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)決策樹支持向量機等人工智能機器學(xué)習(xí)深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)是其中的一種方法

人工智能、機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)之間的關(guān)系神經(jīng)網(wǎng)絡(luò)是一種用多層結(jié)構(gòu)來模擬人腦神經(jīng)網(wǎng)絡(luò)的一種方法。人工智能機器學(xué)習(xí)深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)

人工智能、機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)之間的關(guān)系當(dāng)神經(jīng)網(wǎng)絡(luò)的層數(shù)非常多時就稱深度學(xué)習(xí)。這么看來，機器學(xué)習(xí)還是基礎(chǔ)。人工智能機器學(xué)習(xí)深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)

小智去圖書館借書，用校園卡一刷，屏幕上竟跳出幾本他心儀已久的人工智能書籍。小智驚訝不已，他尚未查詢，計算機如何知曉他的需求？原來，這是圖書館新引入的基于機器學(xué)習(xí)算法的智能推薦系統(tǒng)。該系統(tǒng)通過分析學(xué)生的借閱歷史、網(wǎng)絡(luò)搜索行為等數(shù)據(jù)，預(yù)測其興趣和需求，從而提供個性化書籍推薦。機器竟然也能像人類一樣學(xué)習(xí)？4.4.1什么是機器學(xué)習(xí)？4.4.2機器怎么學(xué)習(xí)？4.4.3機器學(xué)習(xí)的類別4.4.4機器學(xué)習(xí)應(yīng)用實例：KNN4.4.5機器學(xué)習(xí)的實際應(yīng)用場景討論：人類是怎么學(xué)習(xí)（廣義的學(xué)習(xí)）和并實踐的呢討論：人類是怎么學(xué)習(xí)（廣義的學(xué)習(xí)）和并實踐的呢而機器學(xué)習(xí)方法不同于前面的算法的地方就是要計算機通過歸納法從數(shù)據(jù)中發(fā)現(xiàn)規(guī)律解決問題。人類學(xué)習(xí)新知的方法演繹法歸納法如前面講的冒泡排序算法和搜索算法正是利用邏輯演繹的方法，配合計算機的計算能力開發(fā)出來的。過往經(jīng)驗規(guī)律歸納輸入新問題預(yù)測未來歷史數(shù)據(jù)模型訓(xùn)練輸入新數(shù)據(jù)預(yù)測未來屬性4.4.1什么是機器學(xué)習(xí)？

反饋改進歷史數(shù)據(jù)模型訓(xùn)練輸入新數(shù)據(jù)預(yù)測未來屬性4.4.1什么是機器學(xué)習(xí)？

改進機器學(xué)習(xí)的關(guān)鍵在于從大量的數(shù)據(jù)中發(fā)現(xiàn)一個“模型”，并通過它來模擬現(xiàn)實世界事物間的關(guān)系，從而實現(xiàn)預(yù)測或判斷的功能。建立這個模型的過程就是學(xué)習(xí)。4.4.2機器怎么學(xué)習(xí)？

如：利用一個人的身高（自變量x1）、體重（自變量x2）數(shù)據(jù)預(yù)測他所穿的鞋的尺碼（因變量y）問題。自變量：稱作特征值或者特征變量因變量：稱作目標(biāo)變量或者標(biāo)簽

4.4.2機器怎么學(xué)習(xí)？

機器學(xué)習(xí)，就是在已知數(shù)據(jù)集的基礎(chǔ)上，通過反復(fù)的計算，選擇最貼切的函數(shù)去描述數(shù)據(jù)集中自變量（x1,x2）和因變量y之間的關(guān)系的過程。如果機器通過所謂的訓(xùn)練找到了一個函數(shù)，對于已有的1000個人的身高、體重數(shù)據(jù)，它都能夠根據(jù)這些特征，大致推斷出他穿鞋的對應(yīng)尺碼。那么，再給另一批人的身高、體重數(shù)據(jù)，就很有希望用同樣的函數(shù)（模型）推斷出這另一批人所穿鞋的對應(yīng)尺碼。此時，已有的1000組身高、體重數(shù)據(jù)叫作訓(xùn)練數(shù)據(jù)集。另一批身高、體重數(shù)據(jù)叫作測試數(shù)據(jù)集。訓(xùn)練數(shù)據(jù)模型訓(xùn)練輸入測試數(shù)據(jù)輸出預(yù)測訓(xùn)練就是用算法確定模型參數(shù)的過程機器學(xué)習(xí)通過訓(xùn)練調(diào)整參數(shù)，減少誤差改進4.4.2機器怎么學(xué)習(xí)？

生活中的模型4.4.3機器學(xué)習(xí)的類別（按學(xué)習(xí)方法）

1.監(jiān)督學(xué)習(xí)。監(jiān)督學(xué)習(xí)利用已知類別的樣本（有標(biāo)記的樣本即有答案的樣本），訓(xùn)練學(xué)習(xí)得到一個最優(yōu)模型參數(shù)。是將問題的答案告知計算機，使計算機進行學(xué)習(xí)并給出模型參數(shù)的方法。監(jiān)督學(xué)習(xí)的應(yīng)用場景主要有回歸和分類。

實際可以按任務(wù)分，按學(xué)習(xí)方法分，按復(fù)雜程度分等特征1特征1特征1特征n特征n特征n··················目標(biāo)目標(biāo)目標(biāo)數(shù)據(jù)特征標(biāo)簽監(jiān)督學(xué)習(xí)算法天氣溫度風(fēng)速晴暖強雨冷中晴冷弱享受運動是否是對于天氣是否適合運動的預(yù)測：分類回歸問題通常用來預(yù)測一個值，其標(biāo)簽的值是連續(xù)的。例如前面根據(jù)身高和體重數(shù)據(jù)預(yù)測出對應(yīng)的鞋的尺碼的例子就是監(jiān)督學(xué)習(xí)中的回歸。此外，預(yù)測房價、預(yù)測高考錄取分?jǐn)?shù)線、預(yù)測未來的天氣等任何連續(xù)性的走勢、數(shù)值等問題都是回歸問題。4.4.3機器學(xué)習(xí)的類別

1.監(jiān)督學(xué)習(xí)：回歸。

分類問題是機器學(xué)習(xí)中的一種常見類型，算法需要將數(shù)據(jù)劃分到一組已定義的類別中。例如，在醫(yī)學(xué)診斷中，分類問題可能是預(yù)測患者是否患有特定疾??；在營銷領(lǐng)域，分類問題可能是預(yù)測客戶是否會購買某種產(chǎn)品；在金融領(lǐng)域，分類問題可能是預(yù)測客戶是否會逾期還貸。4.4.3機器學(xué)習(xí)的類別

1.監(jiān)督學(xué)習(xí)：分類。

4.4.3機器學(xué)習(xí)的類別

1.監(jiān)督學(xué)習(xí)：分類。

將數(shù)據(jù)分類到兩個類別中，叫做二元分類如前面的天氣是否適合運動。將數(shù)據(jù)分類到更多類別，比如10個類別的情況，這樣的情況稱為多元分類，如超市購買水果，對水果進行識別等。分類是機器學(xué)習(xí)的經(jīng)典應(yīng)用領(lǐng)域，很多種機器學(xué)習(xí)算法都可以用于分類，包括基礎(chǔ)的K近鄰算法、經(jīng)典的邏輯回歸算法、以及神經(jīng)網(wǎng)絡(luò)、深度學(xué)習(xí)等。

無監(jiān)督學(xué)習(xí)直接接收一堆特征數(shù)據(jù)作為起點。然后，它會嘗試對這些數(shù)據(jù)進行各種分析，找出數(shù)據(jù)里隱藏的一些規(guī)律或群體。通過這種方式，無監(jiān)督學(xué)習(xí)能夠逐漸理解這些數(shù)據(jù)的內(nèi)在結(jié)構(gòu)和特點。無監(jiān)督學(xué)習(xí)的典型應(yīng)用場景是聚類和降維。4.4.3機器學(xué)習(xí)的類別

2.無監(jiān)督學(xué)習(xí)

討論：物以類聚，人以群分現(xiàn)象學(xué)習(xí)的各種社團算不算？聚類問題的目的是將相似的數(shù)據(jù)聚在一起。例如，通信運營商可以對手機用戶的通話行為進行聚類，把喜歡上網(wǎng)的用戶聚為一類，喜歡夜間打電話的用戶聚為另一類。4.4.3機器學(xué)習(xí)的類別2.無監(jiān)督學(xué)習(xí):聚類把相似的數(shù)據(jù)匯總為組的方法叫聚類。

降維，簡單來說，就是把一堆有很多特征的數(shù)據(jù)，想辦法用更少的特征來表示，同時還要求保留最主要的信息。

也就是指將高維數(shù)據(jù)轉(zhuǎn)換為低維數(shù)據(jù)。

4.4.3機器學(xué)習(xí)的類別2.無監(jiān)督學(xué)習(xí):降維

降維，簡單來說，就是把一堆有很多特征的數(shù)據(jù)，想辦法用更少的特征來表示，同時還要求保留最主要的信息。

也就是指將高維數(shù)據(jù)轉(zhuǎn)換為低維數(shù)據(jù)。

4.4.3機器學(xué)習(xí)的類別2.無監(jiān)督學(xué)習(xí):降維

討論：生活中降維的例子，你了解的有沒有？我們的世界是三維的，拍的照片是二維的。我們的學(xué)科體系是復(fù)雜和多維的，我們把它轉(zhuǎn)換為一個一個的知識點和實踐項目。將大量文字總結(jié)成摘要，保留關(guān)鍵信息，減少數(shù)據(jù)量。在面臨復(fù)雜決策時，人們可能只關(guān)注最重要的幾個因素，忽略次要因素。強化學(xué)習(xí)，在不斷嘗試中通過獎懲機制來學(xué)習(xí)如何做出最好決策的方法。4.4.3機器學(xué)習(xí)的類別3.強化學(xué)習(xí)

強化學(xué)習(xí)在游戲、機器人控制、自動駕駛等需要決策和優(yōu)化長期目標(biāo)的場景中發(fā)揮著重要作用。4.4.3機器學(xué)習(xí)的類別3.強化學(xué)習(xí)

監(jiān)督學(xué)習(xí)利用已知類別的樣本（有標(biāo)記的樣本），訓(xùn)練學(xué)習(xí)得到一個最優(yōu)模型。如用于數(shù)據(jù)分類。無監(jiān)督學(xué)習(xí)半監(jiān)督學(xué)習(xí)對于沒有標(biāo)記的樣本，學(xué)習(xí)算法直接對輸入數(shù)據(jù)集進行建模，如聚類。試圖讓學(xué)習(xí)器自動地對大量未標(biāo)記數(shù)據(jù)進行利用以輔助少量有標(biāo)記數(shù)據(jù)進行學(xué)習(xí)。強化學(xué)習(xí)強化學(xué)習(xí)通過試錯來學(xué)習(xí)最優(yōu)的行為策略。系統(tǒng)會根據(jù)當(dāng)前的狀態(tài)選擇一個動作，然后觀察環(huán)境的反饋(獎勵或懲罰),并據(jù)此調(diào)整策略，以便在未來獲得更好的回報。機器學(xué)習(xí)的類別4.4.3機器學(xué)習(xí)的類別同一類別的事物通常聚集在一起“人以群分，物以類聚”說的就是這個原理？“近”“鄰”K是鄰居個數(shù)4.4.4機器學(xué)習(xí)應(yīng)用實例：KNNKNN（K-NearestNeighbor，K近鄰）算法是機器學(xué)習(xí)算法中最基礎(chǔ)、最簡單的算法之一，屬于監(jiān)督學(xué)習(xí)，主要用于分類。（一）KNN的原理B?A?4.4.4機器學(xué)習(xí)應(yīng)用實例：KNNKNN算法的核心思想是：如果一個樣本在特征空間中的K個最相似（即特征空間中最鄰近）的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。觀察這張圖，推斷A、B兩點的顏色和形狀？（一）KNN的原理B?A?推測A粉色圓點B綠色方塊4.4.4機器學(xué)習(xí)應(yīng)用實例：KNN觀察這張圖，推斷A、B兩點的顏色和形狀？B?A?原因01以A為圓心的區(qū)域：粉色圓點多02以B為圓心的區(qū)域：綠色方塊多（一）KNN的原理4.4.4機器學(xué)習(xí)應(yīng)用實例：KNN觀察這張圖，推斷A、B兩點的顏色和形狀？B?A?（一）KNN的原理4.4.4機器學(xué)習(xí)應(yīng)用實例：KNN觀察這張圖，推斷A、B兩點的顏色和形狀？KNN如何理解“最近”呢？最直觀的就是用距離量化“遠(yuǎn)近”。距離（用d表示）的計算方法有很多種。如對于直線上的距離，平面上的兩個點來說，距離可以采用歐式距離進行計算（一）KNN的原理k近鄰法步驟：1.計算輸入數(shù)據(jù)與訓(xùn)練數(shù)據(jù)之間的距離；2.按距離遞增排序；3.得到距離輸入數(shù)據(jù)最近的k個訓(xùn)練數(shù)據(jù)；4.統(tǒng)計k個訓(xùn)練數(shù)據(jù)的類別頻率，按規(guī)則確定預(yù)測結(jié)果。B?A?KNN算法的實現(xiàn)，這里不講了，學(xué)有余力的同學(xué)可以自己探索。（二）KNN的實現(xiàn)4.4.4機器學(xué)習(xí)應(yīng)用實例：KNN標(biāo)志型號長（mm）寬（mm）高（mm）價格（萬元）略過X00140531740144923瀏覽X00250871868150041略過X0034032168014509瀏覽X00443301535188528

推薦?X00845601822164534（三）KNN的實際應(yīng)用假設(shè)某網(wǎng)站發(fā)現(xiàn)用戶對某些車型的瀏覽行為如綠色數(shù)據(jù)所示，那么現(xiàn)在向用戶推送X008車型的廣告是否會引發(fā)用戶興趣？4.4.4機器學(xué)習(xí)應(yīng)用實例：KNN標(biāo)志型號長（mm）寬（mm）高（mm）價格（萬元）略過X00140531740144923瀏覽X00250871868150041略過X0034032168014509瀏覽X00443301535188528

推薦?X00845601822164534為了簡化，此處只考慮價格特征，我們計算X008與其它車型的距離，例如與X001的距離為類似的，可以算出X008與其它所有車型的距離（三）KNN的實際應(yīng)用4.4.4機器學(xué)習(xí)應(yīng)用實例：KNN用戶行為型號價格（萬元）距離d略過X0012311瀏覽X002417略過X003925瀏覽X004286

？X00834選取與被測車輛距離最小的k個點（一般k為奇數(shù)，本例k=3）作為分類判斷的依據(jù)，即圖中藍色部分的3種車型，2種為用戶感興趣的車型，1種為用戶無興趣車型；按簡單的少數(shù)服從多數(shù)原則，可推測車輛X008也是用戶感興趣的車型。（三）KNN的實際應(yīng)用4.4.4機器學(xué)習(xí)應(yīng)用實例：KNN234128934（四）KNN算法的思考討論：這個圖中，C點預(yù)測是什么？為什么？4.4.4機器學(xué)習(xí)應(yīng)用實例：KNNC?學(xué)生可能討論出新的ideaC?大圈區(qū)域

K=94:5，粉色圓點小圈區(qū)域k=54:1，綠色方塊如何確定C的類別K個近鄰？學(xué)生可能討論出新的idea（四）KNN算法的思考討論：這個圖中，C點預(yù)測是什么？為什么？4.4.4機器學(xué)習(xí)應(yīng)用實例：KNN如果考慮減小KNN算法中k的取值k取1待預(yù)測點的分類只依賴于與之最近的點，分類結(jié)果隨機性太大；k太大如極端情況，與數(shù)據(jù)集的樣本數(shù)一樣大，那么算法的分類結(jié)果沒有意義。就一般經(jīng)驗，k的取值一般低于已知類別的樣本數(shù)的平方根。other還可以不使用簡單投票規(guī)則，而對距離加權(quán)，比如可以使距離近的點更有影響力?？梢越档蚹值變化對結(jié)果的影響。C?（四）KNN算法的思考4.4.4機器學(xué)習(xí)應(yīng)用實例：KNN4.4.4機器學(xué)習(xí)應(yīng)用實例：KNNKNN算法實現(xiàn)手寫字識別演示方法一KNN算法實現(xiàn)手寫字識別演示方法二當(dāng)推薦給你的商品不能滿足你的需求是，你就會搜索搜索算法以圖搜索商品排序4.4.5機器學(xué)習(xí)的實際應(yīng)用人臉檢測活體檢測人臉識別當(dāng)最終你購買了商品，還可以刷臉支付，4.4.5機器學(xué)習(xí)的實際應(yīng)用你購買商品后，給商品打包，發(fā)貨，然后給你貼上標(biāo)簽，進一步更新你的用戶畫像。4.4.5機器學(xué)習(xí)的實際應(yīng)用信用卡欺詐檢測等人臉識別垃圾郵件過濾文字語言識別商品推薦機器學(xué)習(xí)廣泛應(yīng)用用戶畫像搜索4.4.5機器學(xué)習(xí)的實際應(yīng)用

也就是說，機器學(xué)習(xí)從樣本數(shù)據(jù)中學(xué)習(xí)得到知識和規(guī)律，然后用于實際的推斷和決策。它和普通程序的一個顯著區(qū)別是需要樣本數(shù)據(jù)，是一種數(shù)據(jù)驅(qū)動的方法。4.4.5機器學(xué)習(xí)的實際應(yīng)用機器能學(xué)習(xí)，你這會信了嗎？它怎么學(xué)呀！就像我們通過啃課本學(xué)習(xí)知識機器學(xué)習(xí)通過吃數(shù)據(jù)預(yù)測未來Algorithm第4章

算法2035主講：王紅梅4.14.24.34.4算法那些事算法概述搜索算法機器學(xué)習(xí)目錄CONTENTS4.5神經(jīng)網(wǎng)絡(luò)與深度學(xué)習(xí)擴展：循環(huán)神經(jīng)網(wǎng)絡(luò)4.6

神經(jīng)網(wǎng)絡(luò)（NeuralNetwork，NN）一般也稱為人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetwork，ANN），是在生物科學(xué)發(fā)展到一定程度后，通過借助數(shù)學(xué)和物理的方法從信息處理的角度對人腦神經(jīng)網(wǎng)絡(luò)進行抽象后建立的簡化模型。

神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)是神經(jīng)元，而神經(jīng)元是對生物神經(jīng)元的模擬。4.5.1生物神經(jīng)元與人工神經(jīng)元4.5.2神經(jīng)網(wǎng)絡(luò)4.5.3神經(jīng)網(wǎng)絡(luò)應(yīng)用——手寫數(shù)字識別4.5.4深度學(xué)習(xí)樹突:

接收來自其他神經(jīng)元的信號。細(xì)胞體:處理信息。軸突:

傳遞這個神經(jīng)元的輸出。突觸:

與其他神經(jīng)元的連接點。4.5.1生物神經(jīng)元與人工神經(jīng)元-生物神經(jīng)元是大腦最基本的功能單位生物神經(jīng)元示意圖（一）生物神經(jīng)元生物神經(jīng)元連接示意圖（1）一個神經(jīng)元接受輸入信號(樹突)，（2）之后處理這個信息（細(xì)胞體）（3）再通連接結(jié)構(gòu)（軸突和突觸）將輸出信號傳遞給其他連接的神經(jīng)元。

輸入→處理→輸出。4.5.1生物神經(jīng)元與人工神經(jīng)元（一）生物神經(jīng)元當(dāng)神經(jīng)元細(xì)胞受到足夠強度的刺激時，也就是接收到的眾多突觸輸入信號的總和超過一定的數(shù)值時（稱為閾值），神經(jīng)元細(xì)胞會被激活，這時神經(jīng)細(xì)胞會產(chǎn)生一個電信號，這個信號會沿著軸突向神經(jīng)元的末端（通常是突觸）傳播。反之，則不會被激活和傳播。4.5.1生物神經(jīng)元與人工神經(jīng)元生物神經(jīng)元激活（一）生物神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元假設(shè)你看到上圖的狗狗，大腦接收到的信息被“笑還是不笑”的一組神經(jīng)元所吸收，這些神經(jīng)元將幫助你做出是否笑的決定，一開始你可能不會笑，只有你覺得好笑到一定程度，你才會笑。也就是每個神經(jīng)元只有當(dāng)其各自達到閾值時才會被激活。生物神經(jīng)元激活實例（一）生物神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元

生物神經(jīng)元是大腦的基本構(gòu)成單元，而人工神經(jīng)元則是受生物神經(jīng)元啟發(fā)設(shè)計出的計算模型，用于模擬大腦的工作方式。（一）生物神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元1943年，心理學(xué)家McCulloch和數(shù)學(xué)家Pitts合作發(fā)表論文，提出了神經(jīng)元的數(shù)學(xué)模型，命名為M-P模型，也叫M-P神經(jīng)元模型。奠定了人工神經(jīng)網(wǎng)絡(luò)的發(fā)展基礎(chǔ)。WarrenMcCulloch（左）和

WalterPitts（右）（二）人工神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元下圖是一個典型的M-P神經(jīng)元模型：包含有3個輸入（X1,X2,X3)，1個輸出y，以及2個計算功能。x1x2zw1w2w3求和sum非線性函數(shù)sgn輸入可以類比為神經(jīng)元的樹突，輸出可以類比為神經(jīng)元的軸突，計算則可以類比為細(xì)胞體。yx3M-P神經(jīng)元模型是一個包含輸入，輸出與計算功能的模型。（二）人工神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元x1x2x3zw1w2w3求和sum非線性函數(shù)sgn輸入可以類比為神經(jīng)元的樹突，輸出可以類比為神經(jīng)元的軸突，計算則可以類比為細(xì)胞體。sum=x1*w1+x2*w2+x3*w3y=sgn(sum)sgn（z）=1z≥b0z<by這個看似復(fù)雜的公式實際上就是先乘法后加法下圖是一個典型的M-P神經(jīng)元模型：包含有3個輸入（X1,X2,X3)，1個輸出y，以及2個計算功能。M-P神經(jīng)元模型是一個包含輸入，輸出與計算功能的模型。（二）人工神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元x1x2x3yw1w2w3sumsgn為了簡化流程圖，把M-P神經(jīng)元作為一個單元，將sum函數(shù)與sgn函數(shù)合并到一個圓圈里，代表神經(jīng)元的內(nèi)部計算。y=sgn(x1*w1+x2*w2+x3*w3)sgn（z）=1z≥b0z<b（二）人工神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元y=sgn(x1*w1+x2*w2+x3*w3)sgn（z）=1z≥b0z<bx1x2x3yw1w2w3sumsgn為了簡化流程圖，把M-P神經(jīng)元作為一個單元，將sum函數(shù)與sgn函數(shù)合并到一個圓圈里，代表神經(jīng)元的內(nèi)部計算。（二）人工神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元x1x2x3w1w2w3sumsgn簡化yM-P神經(jīng)元可以看作一個計算與存儲單元。計算是神經(jīng)元對其的輸入進行計算功能。存儲是神經(jīng)元會暫存計算結(jié)果，并傳遞到下一層。（二）人工神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元A（天氣是否晴朗）B（時間是否允許）C（是否有理想的野餐地點）yw1w2w3周末是否外出野餐的應(yīng)用場景ABCY11110000理想狀態(tài)表是否野餐然而，現(xiàn)實情況往往復(fù)雜多變，條件可能部分滿足而部分不滿足。例如，即便天氣晴朗、個人時間允許，若缺乏合適的野餐地點，我們是否仍會外出野餐呢？（二）人工神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元A（天氣是否晴朗）B（時間是否允許）C（是否有理想的野餐地點）yw1w2w3周末是否外出野餐的應(yīng)用場景是否野餐實際上，在多數(shù)決策中，各條件的重要性并不等同。因此，我們可以為每個條件分配不同的權(quán)重，以反映其重要性。例如：天氣：權(quán)重0.50時間：權(quán)重0.30地點：權(quán)重0.20A（0.5）B（0.3）C（0.2）Y1111=（1×0.5+1×0.3+1×0.2）0110.5（0×0.5+1×0.3+1×0.2）0.5到底是去還是不去呢？我們可以設(shè)置一個閾值，如0.7，若加權(quán)總和超過閾值，神經(jīng)元輸出1，可以去野餐；否則，輸出0，不去野餐。（二）人工神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元A（天氣是否晴朗）B（時間是否允許）C（是否有理想的野餐地點）yw1w2w3周末是否外出野餐的應(yīng)用場景是否野餐天氣（50%）時間（30%）地點（20%）結(jié)果1111.01100.81010.71000.50110.50100.30010.20000.0閾值的高低反映了決策的嚴(yán)格程度。如平時課程60分通過，畢業(yè)論文70分才能通過等，這種決策機制在M-P神經(jīng)元模型中得到了直觀的體現(xiàn)。（二）人工神經(jīng)元4.5.1生物神經(jīng)元與人工神經(jīng)元x1x2x3yw1w2w3M-P神經(jīng)元模型的使用可以這樣理解：我們有一樣本。樣本有四個屬性，其中三個屬性已知（X1,X2,X3)，一個屬性未知（y）。我們需要做的就是通過三個已知屬性預(yù)測未知屬性。y=sgn(x1*w1+x2*w2+x3*w3)

已知的屬性稱之為特征，未知的屬性稱之為目標(biāo)。假設(shè)特征與目標(biāo)之間確實是線性關(guān)系，并且我們已經(jīng)得到表示這個關(guān)系的權(quán)值w1，w2，w3。那么，我們就可以通過神經(jīng)元模型預(yù)測新樣本的目標(biāo)。（二）人工神經(jīng)元M-P神經(jīng)元模型模型，一方面奠定了神經(jīng)網(wǎng)絡(luò)大廈的地基。另一方面，權(quán)重的值都是預(yù)先設(shè)置的，因此不能學(xué)習(xí)。這極大地限制了其適應(yīng)變化環(huán)境的能力。為了突破這一局限，科學(xué)家們開始探索如何讓神經(jīng)元自動調(diào)整權(quán)重，從而實現(xiàn)自我學(xué)習(xí)和優(yōu)化。x1x2x3yw1w2w34.5.1生物神經(jīng)元與人工神經(jīng)元（二）人工神經(jīng)元1949年心理學(xué)家Hebb提出了Hebb學(xué)習(xí)率，認(rèn)為人腦神經(jīng)細(xì)胞的突觸（也就是連接）上的強度是可以變化的。于是計算科學(xué)家們開始考慮用調(diào)整權(quán)值的方法來讓機器學(xué)習(xí)。盡管M-P神經(jīng)元模型與Hebb學(xué)習(xí)律都已誕生，但限于當(dāng)時的計算機能力，直到接近10年后，第一個真正意義的神經(jīng)網(wǎng)絡(luò)才誕生。

Hebb4.5.2神經(jīng)網(wǎng)絡(luò)-感知機1958年，計算科學(xué)家弗蘭克·羅森布拉特提出了由兩層神經(jīng)元組成的神經(jīng)網(wǎng)絡(luò)。他給它起了一個名字：“感知機”。感知機是當(dāng)時首個可以學(xué)習(xí)的人工神經(jīng)網(wǎng)絡(luò)。弗蘭克·羅森布拉特現(xiàn)場演示了其學(xué)習(xí)識別簡單圖像的過程，在當(dāng)時的社會引起了轟動。引發(fā)神經(jīng)網(wǎng)絡(luò)的第一次研究高潮。4.5.2神經(jīng)網(wǎng)絡(luò)-感知機4.5.2神經(jīng)網(wǎng)絡(luò)-感知機-結(jié)構(gòu)在原來M-P神經(jīng)元模型的輸入位置添加神經(jīng)元節(jié)點，其為“輸入單元”，其余不變。x1x2x3yw1w2w3x1x2x3yw1w2w3?代表輸入?代表輸出

M-P神經(jīng)元模型

感知機（單層神經(jīng)網(wǎng)絡(luò)）建議找個類比的例子，否則不好理解4.5.2神經(jīng)網(wǎng)絡(luò)-感知機-結(jié)構(gòu)我們把需要計算的層次稱之為“計算層”，并把擁有一個計算層的網(wǎng)絡(luò)稱之為“單層神經(jīng)網(wǎng)絡(luò)”。x1x2x3yw1w2w3輸出層輸入層在“感知機”中，有兩個層次。分別是輸入層和輸出層。輸入層里的“輸入單元”只負(fù)責(zé)傳輸數(shù)據(jù)，不做計算。輸出層里的“輸出單元”則需要對前面一層的輸入進行計算。假如我們要預(yù)測的目標(biāo)不再是一個值，而是多個值。那么可以在輸出層再增加一個“輸出單元”。x2x3w1w2w3y1上圖顯示了帶有兩個輸出單元的單層神經(jīng)網(wǎng)絡(luò)，其中輸出單元的計算公式：y1=g(x1*w1+x2*w2+x3*w3)y2=g(x1*w4+x2*w5+x3*w6)y2x1w4w5w6公式讓人不滿意的就是：w4，w5，w6是后來加的，很難表現(xiàn)出跟原先的w1，w2，w3的關(guān)系。4.5.2神經(jīng)網(wǎng)絡(luò)-感知機-結(jié)構(gòu)x2x3w1,1w1,2w1,3y1y2x1w2,1w2,2w2,3因此我們改用二維的下標(biāo)，用wm,n來表達一個權(quán)值。下標(biāo)中的m代表后一層神經(jīng)元的序號，而n代表前一層神經(jīng)元的序號（序號的順序從上到下）。例如，w1,2代表后一層的第1個神經(jīng)元與前一層的第2個神經(jīng)元的連接的權(quán)值。y1=g(x1*w1,1+x2*w1,2+x3*w1,3)y2=g(x1*w2,1+x2*w2,2+x3*w2,3)4.5.2神經(jīng)網(wǎng)絡(luò)-感知機-結(jié)構(gòu)4.5.2神經(jīng)網(wǎng)絡(luò)-感知機-效果與M-P神經(jīng)元模型不同，感知機中的權(quán)值是通過訓(xùn)練得到的。因此，可以做線性分類任務(wù)。我們可以用決策分界來形象的表達分類的效果。決策分界就是在二維的數(shù)據(jù)平面中劃出一條直線，當(dāng)數(shù)據(jù)的維度是三維的時候，就是劃出一個平面，當(dāng)數(shù)據(jù)的維度是N維時，就是劃出一個N-1維的超平面。單層神經(jīng)網(wǎng)絡(luò)（決策分界）后面的貓狗分類例子詳解決策分界4.5.2神經(jīng)網(wǎng)絡(luò)-案例：基于貓狗識別的神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練過程這里的x,y是抽象的對象的兩個輸入特征，耳朵向上取正值，尾巴向下取正值。假設(shè)我們有一個包含貓和狗圖片的數(shù)據(jù)集，這些圖片已經(jīng)被人工標(biāo)記為“貓”或“狗”。為了訓(xùn)練感知機，我們需要從每張圖片中提取特征。在這個例子中，我們簡化特征提取過程，只提取兩個特征：（1）耳朵的長度x（耳朵向上取正值）（2）尾巴的長度y（尾巴向下取正值）x=3，y=5x=-4，y=-3+1表示是貓-1表示是狗

算法

？+1-1xy這里的x,y是抽象的對象的兩個輸入特征，耳朵向上取正值，尾巴向下取正值。

輸入

輸出（lable）4.5.2神經(jīng)網(wǎng)絡(luò)-案例-基于貓狗識別的神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練過程x+y=0+1-1if(x+y)>0取+1貓if(x+y)<=0取-1狗怎么設(shè)計公式？簡單的方法就是求和，如果需要再添加個閾值。xyx=3，y=5x=-4，y=-3

輸入

算法

輸出（lable）4.5.2神經(jīng)網(wǎng)絡(luò)-案例-基于貓狗識別的神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練過程這里的x,y是抽象的對象的兩個輸入特征，耳朵向上取正值，尾巴向下取正值。x+y=0貓狗

在二維坐標(biāo)上表示

x+y=0

+1-1

輸入

算法

輸出if(x+y)<=0-1狗這個公式還行嗎？是否需要重新設(shè)計？xyx=3，y=5x=-4，y=-3x=2.5，y=-4這是個啥鬼！泛化不