當前位置: 華文問答 > 數碼

有什麽理論復雜但是實作簡單的演算法?

2015-02-02數碼

毫無疑問的,隨機微分方程式與郎之萬動力學,deep learning時代最經典的離散格式就是SGD。實作很簡單:d x = f d t + g d W,算上+和=共計10個字元。前面提到的演算法裏面我目測實作復雜度都比它海了去了。

理論性質:由於SGD對收斂幾乎沒啥要求(無凸性,甚至可以不咋光滑),想要研究一般意義的收斂速度,必須理解學會用概率論聯系黎曼幾何或者PDE中Sobolev空間。無話可說....極其難......

作為上可研究最漂亮的理論 (dynamical systems; ergodic theory; optimal transport) 和純數比肩,下可跑SOTA 引領AI時代。應數渣渣表示,搞工程的人想要創新還是適合找feature搭網絡。至於高階求解演算法, 未來的世界應該還是懂套用的SDE大佬的。其topic也必然越不過概率配Sobolev或者黎曼幾何。

往細了一點說,SDE可以和PDE靠Feynman–Kac formula對應:SDE描述隨機變量的演進;SDE對應的PDE描述均值的過程,經典例子就是布朗運動對應熱方程式,你可以很容易想象出布朗運動是遊走遍歷全空間的(先不管速度快慢)。

第二點,當布朗運動加了drift(梯度)生成SDE, PDE也從熱方程式變成更一般的 Fokker Planck方程式(PDE)。它可以描述概率密度函數的演進,更nice的是這個東西在Wasserstein metrics下的entropy 是gradient flow。直觀來講,就是把概率密度函數當成"凸問題最佳化",一切變成了多少概率去擊中什麽區域,平均意義下解的收斂速度。

在套用層面:DNN裏面的調參,最重要的經驗是調整learning rate。糾其本質降低數值誤差貢獻很小,而增大擊中global optma的概率才是核心https:// arxiv.org/abs/1711.0262 1 。但是你懂得,這是經典的模擬退火演算法。也是最最基礎的非凸最佳化演算法而已。其他有潛力的演算法見: replica exchange https:// arxiv.org/pdf/2008.0536 7.pdf 和 dynamic importance sampling. https:// arxiv.org/pdf/2010.0980 0.pdf 。 總而言之,鑒於隨機過程的復雜,在外行眼裏面,DNN基本就是煉金術,什麽解是好其實還是很難理解清楚。

文獻見概率大佬們總結的mixting time常見技巧,比如有序的撲克牌最少洗牌幾次可以接近隨機。這種融入到生活中的例子不能剩數,但證明極其復雜真的不是一般人能搞定的....能創新你就...真的牛啦。

適當時候也得了解他山之石與公認強大的泛函不等式。每一次的計算器材升級與物理application的創新,都會伴隨SDE的第N次復蘇,但數學工具的變化卻往往很小。原因是對分析的要求太高了.....

當今Langevin越來越多硬骨頭,對Monte Carlo方法感興趣的PhD新生可以關註下:Piecewise deterministic Markov processes, bouncy particle sampler, and zig-zag sampler.