当前位置: 华文问答 > 数码

有什么理论复杂但是实现简单的算法?

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.