0
雷锋网 AI 科技评论按,日前,在中国运筹学会的闭门会议——现代运筹学发展讨论会上,冯•诺依曼理论奖得主、斯坦福大学管理科学与工程系教授,杉数科技奠基人叶荫宇老师发表了精彩的演说。
叶荫宇:斯坦福大学李国鼎工程讲席教授,管理科学与工程系工业联盟计划主任,从事最优化、运筹学、供应链方法、传感器网络、市场平衡与价格、数据与计算等方向的研究。他是运筹管理学领域最高奖项——冯·诺依曼理论奖的唯一一位华人得主,国际最知名的运筹学专家之一。
叶荫宇教授先是介绍了自己最近做的一些研究工作,提到了运筹优化与目前大热的领域如 machine learning、deep learning 互相结合的点。他表示:「优化要结合实际来解决问题,也不一定是局限于哪一个领域,比如传统的计算机领域、统计或者是其他领域。」
在演讲结束之后,他对现场的提问进行了精彩的回答,比如说如何一直保持旺盛的精力来进行科学研究,如何进行有品位的研究。
在最后,他也对中国运筹学的发展提出了自己的看法:一,不要固步自封,要时刻保持新思路、新想法;二,要做点实际的事,而不是只沉迷于纸上的研究。
以下为他的演讲内容,雷锋网 AI 科技评论做了不改变原意的编辑整理。
最近的一些研究工作
说下我最近做的一些工作,以及其中有可能跟 machine learning、deep learning 有关系的点。
众所周知 policy iteration 这个算法一直工作得非常好,在MDP(马尔科夫决策问题)中几乎都是用这套方法。可惜大家一直不知道这个算法在理论上到底好不好,但是我们证明了在理论上它就是好的,而且收敛速度是线性的。这是 OR(运筹学)中间的结果,也是传统 OR 的问题,但是在 machine learning 中情况会有不同。最近我们做了一些 value iteration 的工作,主要解决的问题是 sample complexity(样本复杂度)。具体来说,传统的 value iteration 算法需要知道所有的状态转移概率,对 information 的要求很高。而我们的算法会对转移概率进行采样,不需要用全部的信息,而且依然保留了较好的理论性质。
其实最近炒得比较火的 AlphaGo Zero,它也是个 stochastic game(随机博弈),即在马尔科夫决策过程中,有部分决策者是想把它 maximize(最大化),有部分决策者是想把它 minimize(最小化)。在 stochastic game 中有一个跟 policy iteration method 比较相像的方法叫 strategy iteration method。很多人说我不要训练集就可以把 AlphaGo Zero 训练好,其实完全是可以理解的,因为你完全可以自己去 sample 产生训练集。这个一点不奇怪,所以可能做 machine learning 的人可以注意一下这一点。
非凸优化问题
再另外一个我想讲讲非凸的问题,我们最近也研究了很多非凸问题。像 machine learning、deep learning 就是利用梯度法去解一些非凸问题找到比较好的解。其实我们在 1996 年已经有研究带约束的二次规划。在优化理论中间有所谓的一阶条件,也有二阶条件,二阶有充分条件,也有必要条件。我们可以证明很多很多的算法收敛到的解是满足二阶最优条件的。对于非正交规划,我个人觉得找起始点非常重要。我不熟悉 machine learning、deep learning 里所谓的 tune up 这些东西,我觉得在某种意义上来说,很多工作也在找起始点。
我以前在通信领域,或者是物联网领域解一些问题。例如知道某两点之间的距离,能不能反过来把位置信息找出来,这实际上是一个非常非凸的问题。我个人认为,有一个解这些非凸优化非常好的方法,就是能不能找到一些所谓的 convex relaxation(凸松弛)。很多非凸问题肯定都是找到了一些 convex relaxation,通过 convex relaxation 找到一个解,说不定就是原问题的最优解。
我发现我们在很多问题上解得很好。我们最近在帮美国一个系统解流体管道的压力最优化问题,针对他们的水管道石油管道等等。它的决策变量其实就是压力,然后再就是流量。大家知道电流里面我们有欧姆定律;流体力学就是相当于压力差等于阻力乘以流体的平方。欧姆定律是线性的,尽管压力是变量,流量也是变量,但它是线性关系,流体力学就不是线性关系,压力差,HI 减去 HJ 等于电阻,电阻是跟管道的直径有关联,等于 Q 乘以 R 的平方。这个等式中,因为 Q 是变量,压力也是变量,那么肯定就不是凸的了。这边是二次,那边是线性,那么是不是线性项大于等于 Q 的平方就可以了。因为 Q 的平方是一个凸函数,小于某个线性函数,如果我们能最终找到一个点,然后反过来再用梯度法来算,就可以最终求解。一个城市管道他们以前几天算不了的问题,现在几分钟就可以算出来。
找到一个好的起始点,所以我说我们能不能搞 smart tuning。我知道搞 deep learning 的人通常花几个月去 tune 那些东西,也得到了很好的结果,但实际上花了很多人力和时间。
我个人认为现在优化的方向,是必须跟一些数据结合起来。反过来,应该也想想这些 machine learning 中一些比较流行的方法对优化有什么帮助,例如一些 ADMM 算法怎么更快地解传统的优化问题。
将 robustness 引进到 learning 里
我今天早上的讲座关于是怎么把 robustness 引进到 learning 里。这个在我们 optimization 里面已经有了 10-20 年的历史了。我最近看到的一些学术论文说,其中有些 learning 的算法对于一些 attack、noise 比较 vulnerable。我今天早上讲,一个熊猫的图像,稍微加一点 noise,我们人眼看来还像熊猫,但是机器学习的算法会识别出它是一个猴子。
现在关于 AI 有一种看法,说它是一种不太严格的科学,甚至有人说它是炼金术,我倒不至于同意这种说法,倒觉得它更像我们的中医,即没有很多的科学证明,但是长期的经验证明还是有效的。中医经常有人说,这个病人治好了,这个病人也好了。我觉得机器学习的算法如果能够把 robustness 再提高一点,那么大家就可以放心大胆地使用了。
我觉得如果本来就没有严格的科学依据,比如说你送飞船上去,到底是用 physical 上的流体力学,以科学的方法来设计轨道,还是用 machine learning 来 design 这个轨道,我想大家目前还是比较相信用严格的数学方法来 design 这个轨道。但是到了一定的时候,没有 physical 的东西来 design 轨道,但 machine learning、deep learning 已经到了某一个可以 trust 的地步的话,我觉得这个时候就可以用了。另外,这个里面必须引进一些所谓 robustness,如果太 vulnerable,那人家稍微破坏一点,给你搞乱一下,马上学习结果就错了。我觉得我们 make decision 的时候,必须要非常小心,必须要能 trust。
这个时候,例如找最短路径时,原来那些基于线性规划的方法,在某些问题上,已经有成条的理论。不过同样也可以用 machine learning 找最短路径。我觉得可以加一些 robustness 在里面,这个方面在优化里面已经研究得很成熟了。其实它跟正则化又有关系,实际上算法复杂性不会增加,就是在 objective function 里面稍微加一点抗干扰因素。我们系里面也有一些学生在做。我的学生最近也在自己开发一些解大型非凸优化问题的算法,写一个 open source 库。他们那些方法不太实用,完全是理论性的,我倒是希望找到一些比较实用的方法,我比较喜欢做一些工具,没有什么理论基础,但是我会想办法。比如说 policy iteration method,实际中有些问题几乎比内点法好多了,很多年前就能够从理论上说明了,目前跟 AI 也是有关系的。我觉得既然工作得这么好,它一定有点道理。
我觉得我们优化要结合实际来解决问题,也不一定是局限于哪一个领域,比如传统的计算机领域、统计或者是其他领域。
问答环节
问:我想请教一下叶老师一个看法,在优化里面,boundary 一直在变,如果是线性的方式容易,非线性的就难了,后来发现这不对,是 convex、nonconvex,现在发现又不对了,nonconvex 有时候也还是容易的,但是有些 nonconvex 问题又不行,您觉得下面这个可能会怎么样。
答:我个人倒没有从这个方面来看,我现在发现 machine learning 中的一些问题和 deep learning 中,以及我们优化中的问题有一个不同的地方,就是很多的问题都是没有约束的。然后通常优化中如果这个问题没有约束,就可以用梯度法、牛顿法、拟牛顿法等进行求解。从优化角度来说,好像不是那么具有挑战性。我觉得长期以来 deep learning 的问题忽略了约束,而这一点正反映了 deep learning 的问题多把它当成是一个 black box,我的参数是没有什么物理背景,正负、无穷大、零,都没有关系。但是我觉得有一点,就是在我们学习的时候,如果参数有一定的物理背景,我们应该引进它的基本的机理,还要让他 obey 一些 basic science rule。比如说流体力学的 rule,你必须把那个条件加进去,作为约束放进去。但是有一点我不知道,像这种解的比较好的非约束的算法,怎么能够解到约束上面去。或者 deep learning 的很多模型,是不是也应该要加一些简单的 science base。
对于所有的线性规划,我们总是要评内点法好,还是单纯形法好,其实现在看来这个没有什么意义。我觉得所有的算法都要把它定制化,定制到什么样的结构上,你才能说哪一个是最好的。
刚才有人问我,machine learning 对优化算法有没有什么帮助,我说肯定有帮助,就是把优化算法的定制化。你根据问题的不同结构、不同特点,在所有的优化函数中找一个对他最实用的。这个方法可能人学不出来,只能通过大量的数据学出来。而且我觉得特别解非凸问题等,对于不同的问题,最好的解的方法不一样。能不能用 machine learning,根据这些问题的特点,找一个对症下药的方法,然后这样我倒觉得对我们优化算法很有帮助。哪怕就是解整数线性规划,不同方法的计算量差别也会很大。比如说解二次规划的问题,到底是用二阶锥规划好,还是原来的凸规划好,这个差别会很大的。
我觉得优化算法对不同问题的定制化这应该是一个方向,包括怎么样定制,参数怎么写,解线性规划。我们也调参数,不调不行,有的对这个问题好,对那个问题不好,这里你很难调到一个配方,对所有的算法都好。所以这个本身就是一个定制化的问题。
问:叶老师在我们心目中是大神,刚才有人提到,叶老师精力特别旺盛,我有个很自然的问题,您是怎么做到的?您有什么秘诀。
答:你们当老师的一定要鼓励学生热爱体育,我以前搞田径,我现在快 70 岁了,我 1965 年的时候,是全国中学生的跳高冠军,三级跳也是冠军,跳远拿的是第几名我忘记了。当时没有全国运动会,就是各个省自己开运动会,然后把成绩报到全国进行汇总,进行排名。这个成绩还是在那里,我们当初跳高是剪式跳高,当时不像现在这样。总结起来,我的意思就是说,要热爱体育。
问:您为什么能够在这么多领域里面,做出这么多有品味的研究,在这方面有什么分享?
答:我个人认为,自己只是江湖中的一个小角色。我做研究就是喜欢想。我不知道你们是不是非要写在纸上,我通常把问题想通,我自己喜欢想一环一环的问题。其实我下棋下得不好,我想这些问题的思路我觉得应该可以证明出来,其实不用纸写出来我觉得应该就可以了。然后我就告诉学生这个问题应该过得去,比如现在我的学生做的这些东西。主要是想这个问题的关键,如果能够推过去,推导的关键在什么地方,你把关键想通了,就没有什么问题了。然后就是这样先想,再写。再就是自己要有一个品位,我觉得小打小闹,有些人开始可以搞一点,但是到了一定的时候就不能这样了。
我比较容易看出学生的一些特长,是搞组合比较好,还是分析随机算法很好,例如线性方程解得蛮漂亮等。我始终认为,其实在运筹学中间的一些问题,不一定要运用到非常高深的数学,有些算法是非常基本的。找到证明的方向,比用到证明的方法更重要。方向找对了,证明非常的简单,就是线性代数,加上一些马尔科夫等,分析一下基本上就过去了。所以这些我觉得还是要有个 sense,这个方向对不对,一步一步走过来,这是我的一点体会。然后再就是对学生,因人而异,找到比较切合他的点,观察他比较擅长什么。
我有个习惯,其实我很喜欢看电视剧,我太太也说我,在电视前一天看两、三个小时电视剧。其实我看电视节目都在想问题,我可以同时 enjoy 这些电视剧,比如《人民的名义》等,我自己也有很多问题是在那个时候想出来的,可以同时进行。
问:您在斯坦福工作也会关注国内的运筹学,在您看来,我们中国的运筹优化发展,怎么样往前走一大步?您能提点见解吗?
答:现在很多搞统计、machine learning、计算机等的优秀的人才都回来了,对于运筹学,我个人有一点感觉,我们把自己封闭起来了。再加上国内大环境也比较强调管理,这个在学科内属于运筹控制等,我觉得现在我们一定要打破这个 boundary,包括在斯坦福等很多地方,学术研究很多方面都没有 boundary,只要有兴趣的问题,大家都可以去做研究。
第一,搞优化的时候,我们运筹学会要不被潮流 left out,现在 AI、machine learning、计算机蓬勃发展,我们要跟上潮流,比如关注 machine learning 中的优化问题。另外,我们能不能提供新的思路、新的方法,更好地帮助他们解决问题,这点很重要,我们一定要跟他们结合起来。
第二,还是要针对实体的经济,对比较大的公司,不管是前面发言的华为,还是其他 BAT 这样的公司,都要有用。这一点是非常不容易的,不光靠学术。可能是我年纪大了,反而觉得觉得光纸上谈兵不行,必须对实际有意义。中国运筹学,长期还是得将学术研究与深层的应用结合起来,想一些东西。再深层意义上,我觉得老师到一定的年龄,还是需要考虑到这一点:现在各个公司的研发力量都很强,包括 BAT 等,他们现在自己内部都有很多搞统计、计算机的,所以老师们可以去稍微指导一下,说一说,提供一些最新的信息。
我还是担心运筹学长期干我们之前的那些事,比较封闭。另外,我倒非常希望看到有些东西,比如将原有算法和新的 deep learning 算法比较,我非常期望看到,到底是结合的好,还是 AI 的好,还是运筹搞的这些基础的比较好。这些很有意思,都是需要去试的。
一个是 OR 要走出去,不要孤芳自赏;第二就是要做点实际的事。这是我个人的看法。
(完)
雷锋网 AI科技评论编辑整理。
雷峰网原创文章,未经授权禁止转载。详情见转载须知。