王川: 深度學習有多深? (十八) -- 從貪婪算法和動態規劃說起

2021-02-20 investguru


本文是

王川: 深度學習有多深? (十七) -- 衡量GPU的計算能力

的續篇.

    (1)

迄今為止我們討論的人工智慧的問題,都還是局限在"認知"方面的應用, 比如圖像識別,語音識別,自然語言處理,等等.

這類問題的特點是,機器獲得大量原始數據的培訓. 每一個輸入,都有標準的"輸出"的答案. 這種學習方式,也稱為"有監督學習".

但是生活中大多數問題,是沒有標準正確答案的.你的所作所為,偶爾會得到一些時而清晰, 時而模糊的反饋信號. 這就是"增強學習" (Reinforcement Learning) 要解決的問題.

"增強學習"的計算模型,最核心的有三個部分:

1. 狀態 (State): 一組當前狀態的變量 (是否吃飽穿暖, 心滿意足? 是鬱鬱寡歡, 還是志得意滿? )
2. 行動 (Action): 一組可以採取的行動變量 (是努力工作, 還是遊山玩水? 是修身養性, 還是夜夜笙歌? )
3. 回報 (Reward): 採取行動, 狀態改變後,把當前獲得的回報定量化. (喝酒就臉紅, 吃多了就發胖, 大怒就傷肝, 工作超過八個小時身體就被掏空, 等等).


增強學習的最終目的,就是在和外界環境的接觸/探索/觀察的過程中,不斷改進策略,把長期的回報/利益最大化而已.

    

    (2)

增強學習的理論基礎, 要從運籌學裡的"貪婪算法" (Greedy Algorithm) 說起.

什麼是貪婪算法? 簡單說,就是,任何時候的決策,都是選擇當前觀察的最優解,而沒有整體長遠的規劃.

貪婪算法的優點是容易理解,簡單快速.但缺點是,得到的往往是局部最優解,而不是全球最優.

在子女教育中,"不要讓孩子輸在起跑線上"就是一種典型的貪婪算法的思維.那些放棄自己的努力,而把希望寄托在下一代的家長們,處心積慮地尋求當前最優解. 他們把孩子推送到重點幼兒園,重點小學,重點中學,重點大學,讓各種小提琴/鋼琴/奧林匹克數學培訓班佔用孩子的業餘時間,生怕孩子看上去比別人落後一點點.

但是學校教授的技能和社會需求變化往往存在嚴重脫節,同時大多數孩子缺乏對挫折和壓力的靈活應對的訓練. 當孩子從學校出來走向社會時,巨大的落差導致的各種不適應和問題就出現了.

郭德綱老師在一次訪談中,深刻地指出, "吃虧要趁早,一帆風順不是好事. 從小嬌生慣養,沒人跟他說過什麼話,六十五歲走街上誰瞪他一眼當時就猝死".

這就是對"貪婪算法"在兒童教育上的局限性的最無情犀利的鞭撻.


    (3)

動態規劃,英文是 Dynamic Programming, 直譯為"動態程序", 這個概念由美國數學家 Richard Bellman 在1950年提出. 它是在貪婪算法的基礎上改進的算法. 實際上它和"動態","程序"兩個概念沒啥關係.

據 Bellman 老師介紹,當初為了忽悠政府的經費,就使用了"動態"這個詞.動態,給人一種靈活,性感,高大上的感覺.誰會對"動態"說不?

動態規划算法的本質,是把一個複雜的問題拆分為多個子問題,並且把子問題的答案存儲起來,避免以後的重複計算.


由於動態規劃是從全局分析問題,所以往往可以找到全局最優解.但它的局限是,

第一, 計算量大,需要窮舉和存儲子問題的解答方案.

第二,動態規劃的隱藏的假設是一個叫做"最優化原理"的東西,就是說,最優化的解決方案,可以通過其子問題的最優解決方案獲得. 換句話說,最優化問題的子決策,對於相應的子問題也是最優的.

什麼樣的問題不符合"最優化原理"?

一個典型的反例, 從點 A 到 點 B 的機票,最便宜的路線選擇,是要到點 C 轉機. 但從 A 到 C 最便宜的機票 (子問題), 卻要從 點 D 再轉機.

(未完待續)

==============================

點擊下面連結獲得本公眾號的介紹

王川： 如何從我的公眾號 investguru 裡面獲得最大的收穫

在投資和事業發展的路上如何集思廣益，舉重若輕？歡迎加入王川的俱樂部，這是一個凝聚來自世界四大洲各行各業精英的高端收費社區.有意入會者請和王川（微信號: 9935070) 直接聯繫。

作者簡介：王川，投資人，中科大少年班校友，現居加州矽谷。個人微信號9935070,公眾號 investguru ,新浪微博「矽谷王川"，知乎專欄 "兵無常勢". 文章表達個人觀點僅供參考，不構成對所述資產投資建議，投資有風險，入市須謹慎.


<王川自選集> 第一卷電子書，現可在百度雲盤上免費下載，訂閱本公眾號後,在公眾號菜單右下角點擊"電子書", 即可獲得下載指令. 總共收錄我過去一年五十多篇原創的財經科技評論文章，近三百頁，歡迎下載傳閱！)


長按下面二維碼訂閱本公眾號. 訂閱後輸入'目錄『兩字看看你錯過了多少好文章!


相關焦點

  • 【算法資源】貪婪算法
    貪婪算法(Greedy algorithm)是一種對某些求最優解問題的更簡單、更迅速的設計技術。
  • DNN的隱喻分析:「深度學習」,深在何處
    嚴格說來，搖滾樂界並不是一個王國，但這裡借用「王」這個字，我們會腦補出一個王國：那裡有各位不同地位的歌手，以及浩浩蕩蕩的簇擁人群（即他們的粉絲團）。回到「深度學習」這個詞，它糾纏在錯綜複雜的隱喻網中。真的有足夠複雜的機器能夠顯示出像人類一樣的學習能力？學習這種抽象的行為又何謂「深度」（亦或淺度）？我在這篇文章裡將探究這些問題。
  • 人工智慧程式設計師入門應該學哪些算法?
    初期一.基本算法:枚舉.遞歸和分治法.遞推.二.圖算法:圖的深度優先遍歷和廣度優先遍歷.四.搜索最優化剪枝和可行性剪枝搜索的技巧和優化記憶化搜索五.動態規劃較為複雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)記錄狀態的動態規劃.樹型動態規劃(六.數學組合數學: 1.容斥原理. 2.抽屜原理. 3.置換群與Polya定理4.遞推關係和母函數.
  • 深度學習算法 | LSTM算法原理簡介及Tutorial
    LSTM（Long Short-Term Memory）算法作為深度學習方法的一種，在介紹LSTM算法之前，有必要介紹一下深度學習（Deep Learning）的一些基本背景。目前在機器學習領域，最大的熱點毫無疑問是深度學習，從谷歌大腦（Google Brain）的貓臉識別，到ImageNet比賽中深度卷積神經網絡的獲勝，再到Alphago大勝李世石，深度學習受到媒體、學者以及相關研究人員越來越多的熱捧。這背後的原因無非是深度學習方法的效果確實超越了傳統機器學習方法許多。從2012年Geoffrey E.
  • 深度學習最常用的學習算法:Adam優化算法
    聽說你了解深度學習最常用的學習算法：Adam優化算法？-深度學習世界。深度學習常常需要大量的時間和機算資源進行訓練，這也是困擾深度學習算法開發的重大原因。雖然我們可以採用分布式並行訓練加速模型的學習，但所需的計算資源並沒有絲毫減少。而唯有需要資源更少、令模型收斂更快的最優化算法，才能從根本上加速機器的學習速度和效果，Adam 算法正為此而生！
  • 深度學習:神經網絡算法的昨天、今天和明天
    而這些應用背後的核心算法就是深度學習（Deep Learning），這也是機器學習（Machine Learning）領域最火熱的一個分支。和其他機器學習算法有很大不同，深度學習依賴大量數據的迭代訓練，進而發現數據中內在的特徵（Feature），然後給出結果。
  • 機器學習算法匯總:人工神經網絡、深度學習及其它
    以下為原文： 學習方式根據數據類型的不同，對一個問題的建模有不同的方式。在機器學習或者人工智慧領域，人們首先會考慮算法的學習方式。在機器學習領域，有幾種主要的學習方式。將算法按照學習方式分類是一個不錯的想法，這樣可以讓人們在建模和算法選擇的時候考慮能根據輸入數據來選擇最合適的算法來獲得最好的結果。
  • 深度學習筆記 | 第3講:深度學習優化算法之從SGD到Adam
    又到了每周一狗熊會的深度學習時間了。在上一期中，小編和大家介紹了機器學習和深度學習中的核心任務以及神經網絡的正則化方法和dropout方法來防止過擬合。本期將借著第一期推送小編關於模型與算法的討論的引子，和大家深入探討機器學習和深度學習的數學本質，並在此基礎上重點介紹深度學習中常用的優化算法。
  • 偽逆學習算法教程 (上)
    通過該策略，偽逆學習算法最多需要兩個隱層即可達到精確學習。 （這是由於噪聲是隨機值，所形成的矩陣只是以概率1可逆，不一定絕對可逆，但有兩個隱層的話，則矩陣不可逆的概率為要比只有一個隱層時小的多得多，也就可以說概率一定為零了）。現在總結一下偽逆學習思想的特點：（1）訓練MLP不需要梯度下降迭代學習。
  • 智能決策論壇系列解讀 | 深度強化學習理論和算法
    為了減小基於模型強化學習方法的複合誤差，張偉楠提出了一種基於雙向建模的BMPO算法（Bidirectional Model-based Policy Optimization），其利用正反雙向建模更有效地約束複合誤差，然後通過基於玻爾茲曼分布的採樣策略和模型預測控制方法來得到更有價值的軌跡，並在理論與實驗中證明了BMPO方法在訓練速度、採樣效率和模型複合誤差上都達到了更好的效果。
  • 【強化學習實戰】基於gym和tensorflow的強化學習算法實現
    1新智元推薦【新智元導讀】知乎專欄強化學習大講堂作者郭憲博士開講《強化學習從入門到進階》，我們為您節選了其中的第二節《基於gym和tensorflow的強化學習算法實現》，希望對您有所幫助。同時，由郭憲博士等擔任授課教師的深度強化學習國慶集訓營也將於 10 月 2 日— 6 日在北京舉辦。
  • 玩轉算法「基礎篇」| 貪婪算法
    2.1  適用場景貪婪算法常用於尋求最優解問題。將問題分成若干個求解步驟，在每個步驟中都依據某個最優原則選擇當前狀態的最優解，以此希望最後得到的結果也是最優的。貪婪算法在迭代完一輪之後就不再進行回溯，簡單高效，這種只關注當前狀態最優解的方法，通常可能會錯過全局最優解。
  • 深度強化學習算法與應用研究現狀綜述
    概述了基於值函數和策略梯度的兩類深度強化學習算法，詳細闡述了深度Q網絡、深度策略梯度及相關改進算法的原理，並綜述了深度強化學習在視頻遊戲、導航、多智能體協作以及推薦系統等領域的應用研究進展。最後，對深度強化學習的算法和應用進行展望，針對一些未來的研究方向和研究熱點給出了建議。
  • 聽說你了解深度學習最常用的學習算法:Adam優化算法?
    By蔣思源2017年7月12日　　深度學習常常需要大量的時間和機算資源進行訓練，這也是困擾深度學習算法開發的重大原因。雖然我們可以採用分布式並行訓練加速模型的學習，但所需的計算資源並沒有絲毫減少。而唯有需要資源更少、令模型收斂更快的最優化算法，才能從根本上加速機器的學習速度和效果，Adam算法正為此而生！
  • 機器學習和深度學習有什麼區別?
    除了深度學習和機器學習的比較外，我們還將研究他們未來的趨勢和走向。深度學習 VS 機器學習深度學習與機器學習簡介一、什麼是機器學習？通常，為了實現人工智慧，我們使用機器學習。我們有幾種算法用於機器學習。
  • 程式設計師必須掌握的核心算法有哪些?
    由於我之前一直強調數據結構以及算法學習的重要性，所以就有一些讀者經常問我，數據結構與算法應該要學習到哪個程度呢？，說實話，這個問題我不知道要怎麼回答你，主要取決於你想學習到哪些程度，不過針對這個問題，我稍微總結一下我學過的算法知識點，以及我覺得值得學習的算法。
  • Python深度學習:邏輯、算法與編程實戰
    今天為您推薦一本精品圖書--Python深度學習：邏輯、算法與編程實戰（ISBN:978-7-111-65861-0）。本書可作為深度學習相關從業人員的參考指南，也可作為大中專院校人工智慧相關專業的教材，還可作為廣大人工智慧愛好者的拓展學習手冊。國家「萬人計劃」領軍人才、西安電子科技大學計算智能研究所所長公茂果，浙江宇視科技有限公司研發副總裁/研究院副院長、人工智慧專家周迪聯合推薦。
  • 貪婪算法
    令人驚嘆，它完美地詮釋了貪婪算法的內涵，局部最優，最終未必最優，或者有時候可以不負責任而武斷地說，最終必定不最優。這個算法是有哲學意味在裡面的，映射了我們的人生，也許也是這樣，總在局部與全局中選錯了那個最優。
  • 學習這麼多算法到底在解決哪些問題?深度學習之外,我們要選擇誰
    在深度學習領域，階梯網絡試圖通過一個網絡把有標籤的監督學習和同類但無標籤數據進行共同訓練，實現一個端到端的半監督深度模型。階梯網絡通過在反向傳播的同時最小化有監督和無監督的損失，從而避免分層預訓練的需求。通過 Skip Connection 使編碼層的每一層都有一個到解碼層的橫向連接；同時在編碼層，每一層都引入噪聲以實現類似於降噪自編碼器的能力。
  • AI 人工智慧的深度學習(3月16日文章)
    深度學習作為機器學習的一個分支，其學習方法可以分為監督學習和無監督學習。兩種方法都具有其獨特的學習模型：多層感知機 、卷積神經網絡等屬於監 督學習；深度置信網 、自動編碼器 、去噪自動編碼器 、稀疏編碼等屬於無監督學習。