运筹学教授叶荫宇:AI时代,优化算法如何应用于实际问题?
i黑马 i黑马

运筹学教授叶荫宇:AI时代,优化算法如何应用于实际问题?

把实际问题变成数学问题,变成优化问题,然后来求解。

i 黑马讯 7月1日消息,钛媒体和杉数科技联合主办的“2017AI大师论坛”6月24日在京成功举办,杉数科技首席科学顾问叶荫宇出席了活动并发表了学术演讲。

叶荫宇是斯坦福大学 K.T.Li 讲座教授,是杉数科技首席科学顾问,同时也是美国运筹与管理学会最高奖冯诺依曼理论奖迄今唯一华人获得者。作为在运筹学领域的顶尖学者,叶荫宇以《优化算法的思想及应用》为题,主要在运筹学应用的物流选址及路径优化、库存管理、投资组合优化三个方面详细阐述了他的看法。

从古至今,“优化”一直是生产生活中重要的部分。而运筹学作为优化算法的重要根基,在第二次世界大战期间首先在英美两国发展起来。运筹学是 20 世纪 30 年代初发展起来的一门新兴学科,其主要目的是在决策时为管理人员提供科学依据,是实现有效管理、正确决策和现代化管理的重要方法之一。

运筹学诞生的时间要比 AI 早,但与 AI 的关系密切。学者把运筹学描述为就组织系统进行各种经营所作出决策的科学手段。二战结束后,人们将运筹学应用到了企业和政府之中,为经济发展加速,运筹学广泛的引用在生产、服务、金融行业之中。在大数据时代,运筹学进一步蓬勃发展,而如何将大数据转化为最优决策成为了运筹学重点。

事实上,运筹学中“优化”这一概念对于机器学习本身也是适用的——比如说算法方面。随着计算能力的提升和大数据时代的来临,利用算法提高机器学习的能力成为了目前业界的焦点之一。而运筹学插上机器学习的翅膀,适用范围和能力也变广变强了。

那么这两者相结合,都有哪些具体的案例可循呢?哪些方面又得到了改进呢?叶教授在演讲中给出了生动的案例。同时他也以案例分析指出了目前国内人工智能发展中遇到的问题——通盘调配方面依然是弱项。

以下为叶荫宇演讲实录:

1982 年刚到美国读书的时候 ,AI 非常热,我差点就去搞 AI 了。那时候要搞所谓的专家系统 AI 空间,学的语言是学 Lisp,没有很多的数据,人家有些就总结不出来,AI 就慢慢地冷下去了。我比较喜欢数学,就从事了运筹学。

什么是运筹学?运筹学是一种研究优化的学问,就是怎么能够在有约束的所有的实际生活中,从事把事情做到极致。不仅仅是找一个可行的方案,而且是一定要找到最优的方案。

Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear. 这是大数学家欧拉的话。

这种理论也是基于自然形成,也是所谓的一个平衡,也是能量函数,到了极值。

运筹学的起源,是一部分数学统计那个时候还没有计算机,数学怎么能接地气,怎么落到实地,怎么真正对人们生活产生一些影响?数学家们就开始寻求这样的方案。也有一些紧迫感,在二次大战的时候,如何研究盟军配置,还包括一些博弈问题。以前看过一个电影叫《A Beautiful Mind》,研究这个东西研究到博弈空间。

标志性的结果就是 1947 年 George Dantzig 提出线性优化,为优化中最经典的算法,其实美国早在 20 世纪就提出来了,但是那个时候没有算法,那个时候也不需要算法。因为那个时候没有计算机,把最优解选出来很慢,能不能有数学的这个记忆依靠这个逻辑来算出来, 这就是里程碑的意义,虽然他自己因为搞数学,没有得诺贝尔奖。

后来运用到经济发展中,运筹学得到很大的发展。特别是之后计算机的高速发展。以前是结构问题,可能是要 1 小时,现在可能不到 1 秒就可以解出来,这既有硬件的提升,也有算法的提升。所以我们可以预见运筹学比 AI 要老,机器学习更老,但是 AI 和机器学习又提供了一种机会,很多顶层的东西都是要靠优化,不管是学习还是刚才讲到的要用决策问题。不过,我认为无论是哪一种,很多都需要依靠优化。整体而言,所谓“优化”就是,量化我们的很多决策。满足一定的约束条件下,使某一个函数最大,这就是优化问题。量化一件事物,就需要建模。一般优化过程就是从建模到求解,然后再到决策,最后我们需要一套算法来求解。

把实际问题变成数学问题,变成优化问题,然后来求解。我认为大数据就是,达到可以量化的数据。当数据量化之后,我们可以用数学的方程、公式来描述它,然后来决策变成一个量化的决策问题。我认为数据大再加上机器学习,能把问题更加量化。这其中,优化问题是各行各业都不可或缺的,这其中又涉及到很多算法方面的问题。

1982 年我去美国中间经历了 AI,当时是最红,现在又红起来。但是有些点我觉得没变的,优化好像始终是不动点一样,不管是你在各行各业都需要它,因为在这点上也可以说起来像统计、数学还是一些机理。

这里面有很多算法的问题,学习有很多深度学习、MDP、机器学习等等。

我个人怎么理解 AI?特别是大数据时代的商务决策,各自所采取的作用,我们要用到很多计算机、信息学,包括机器学习、数据搜集,然后我们要通过很多机器学习做一些规律性分析,然后建模做出决策。

机器学习与运筹学如何结合?我觉得机器学习在量化,需求管理、规律性分析上面确实做的好。但是怎么决策?这里面都有一些很传统的优化模型和运筹学的模型。我给大家举几个简单的例子,为什么有些决策模型并不需要深刻的理解就可以得出来?

一、物流选址及路径优化

比如说这个选址问题,寻求一个区域内最优的仓库选择,成本最少。我要建一二三四五个库建在什么地方,那么这里面就要权衡很多,一次建设费多少?建成之后,我服务区域有多大?那么区域大了,远地方的人运输成本会提高多少?这就需要运用数学工具去计算。

像这个问题,很早来说我们就知道它是一个凸问题:在哪些点上有些是离散变量?那么这样的问题怎么选才好?按照以前的算法,我就把它写成一个整数规划,就去算。现在不行,客户提出的需求,有些算法几个月都算不出解来。现在很多东西,要随时计算。得把它们视为是变化的,进行随时的调配,重新选址,这个时候我的算法就非常的快,然后就会有很多的近似算法。这里面我们也做过一些工作,这就是比较确定性的这个问题。这里面的算法问题,选址的问题,我们杉数在跟国外国内很多大企业合作过程中出现了很多这样的问题。

那么有一个问题就稍微更复杂一点,不是选址。是选择一个仓库,提供一个区域服务——有点像是中转站。航班调运也会面临同样的问题。通常我们把选址的问题,叫作战略性的决策,一旦选了以后几年都不会变。决策也分为战略决策,战术决策,以及经营性决策。经营性决策是指,如果我现在要送货,送到这么多的点上,如何都送出去,然后回到出发的地点使整个距离最小?这叫旅行商问题,这个也是很经典的问题。

当然所有的物流公司都是在解决这个问题。

这有一个简单的解决方案,分而治之。我现在有 5 辆车,我要服务这个区域,首先就建立一个服务区的概念。把这个大的区域分成 50 份,每一个区域选择一个分点。选了以后,我知道我在分这个区域的时候,尽量保证每个区域的工作量均等。同时还要保证这些车辆跑的路线街道总长度不变,这个主要是地图公司做的。

我不知道大家刚才看到我在排序的过程中,在这个路径过程当中大家也都没有遇到,我原来认为我排出来最后的总路程最短,后来给我们提一个要求这里面有多少是左转多少是右转,你能不能排路径的时候,尽量向右转。因为考虑的是要完成的时间,左转所要花的时间,要比向右转高 5 到 10 倍。因为有红绿灯,所以我们用运筹学的办法把这个解决掉。

再举一个路径优化的问题,大家都在搞所谓的无人仓。有一些小车搬运载有货物的托盘到空闲工作台,然后小车搬运到托盘从工作台回到仓库空储位,我们叫回库。然后小车搬运空托盘从工作台到托盘回收处,我们叫回收。这里面都是一些货柜,怎么拖起来怎么用,又要路径又要协调。

我觉得在我们国内研究机器人,研究的比较多的是提高机器人自身的能力,我觉得做的非常好。个人能力都非常好,但是我们国家在很多问题上,缺少通盘调配和安排。

机器人那么强,在团队里工作可能就没那么强了。我们就比较缺乏统筹的软件决策系统。就像我们中国足球:个人能力不管强弱,在一起就不行。我们很注重个人能力的提高,人都不要输在起跑线上,但是我觉得我们国家,长期缺乏一种集体统筹决策能力的开发和提高每个机器人都在瞎跑的话肯定不行,包括无人车。

很多公司都在考虑无人车的技术多强,但是其实最主要的问题是什么,反而是无人车之间的协调、调配和统一指挥。

比如说这里面是工作台,某一个区域的货来了以后,我们来分担,然后这是一个动图,整个的这个货品的分担,这里面有很多问题。我们在研究过程中,比如说这里面的路径,怎么找路径,从设计上来说,你是设计成单行线还是双程线,这里面有学问的,如果设置单行线跑的距离要长,碰撞的可能性就少一些,这里面都可以通过优化来进行解决。

机器人怎么配到货柜,怎么收检这个站?这个方法目前是用机器人去托盘,拖这个货柜,把整个的货柜用到旁边的这个台上,然后又把这个拿下来,再把托盘送回去,大家觉得这个是否适合中国国情?我们中国人就很喜欢把国外的东西搬过来。首先是机器人,把整个的货柜拖起来,可能那个货柜员就检一个东西下来。那么为什么不能货柜不动,而且货源坐在机器人身上然后去检货呢?可能人需要多一点,但是货柜可以装的更高了,空间利用率更高了。

我觉得我们大家可以想到一些更好的,但是这套技术可以用,而且人坐在机器上,不仅前后移动还可以升降货柜,可以放更高,运行过程中形成三维的仓库而不是平面的仓库,这样我们就可以计算出来,包括货的这个密度,增加多少,仓库的利用率可以增加多少。那么对于像我们国家,人力相对比较便宜,房非常贵,是不是就更好一点,但整个也是靠产品运输来优化问题进行求解。

世事不可预测,但可以进行结果优化。

我在国内跟工业界接触也有一段时间,工业界总是觉得我们需要深度学习,需要机器学习,需要把预测的精度提高 1%,再提高 1%。我觉得有时候忽略了一点,有个测不准的这个定理到一定时候不可能提高的,有一个不确定的这个规律存在。股票市场存在一两百年,也没有人能 100% 预测股票市场,所以在测不准的情况下,在决策上是不是可以做点工作,在知道测不准,可能有不同的这个状况出现的情况下,我的决策是不是可以调整一下,从数据到决策我们是不是也可以做一些工作。比如说我可以保证我在期望值省时一些,但是我保证永远不会破产,防备那些恶性大事件发生,所以这些模型在 OR 应用到很多的。

比如说路径优化,我们搞了一个 PonyPlus,我给这个送货员把一个任务今天要派 10 个单,给到这个送货员,就搞一个辅助工具怎么去路径最好,排了一个,这里面都有这样一些工具。

二、库存管理

这里面最典型的是库存问题,就是典型的知道你测不准,我怎么能够把预测做到最好,把库存做到最好。以前早的时候还没有深度学习,比如你是小零售商,你进货进多少,进一个星期的货,但是不知道这个星期有多少,多的有多的损失,少的有少的损失。所以这个时候运筹学就有一套方法来处理这个问题。

最近大家是否听说过美联航上面有一个人,因为机票卖多了,上了飞机被人拖下去,后来是赔了几个亿,为什么说这是典型问题,是不确定环境下的决策?

飞机上座位是固定的 300 个,你事先只卖 300 张票,不会卖多,来的人都可以登记,问题是总有 5% 到 10% 的人,因为各种各样的原因是不会来的。那么你卖 300 张票,5% 到 10% 是不会来,那么那部分就会损失,所以航空公司一般都会多卖一点。这个道理是一样的它也要权衡,它知道有些人不来,我怎么多卖几张,最好的是有些人不来,不来的人数正好是我多卖的人数。但是永远是测不准的,也就出现美联航的这个问题。

一般我们决策是什么,业内通过拍卖的形式,你愿意乘坐下一次航班,给你多少钱,美联航说到 600 块钱就不向上提,所以我们要找一个权衡,多卖几张最好。

这点我们做过很多实际案例,特别是在我们国内比较大的电商里,帮他安排,通常周转率在 25 天的,现在降到 16.5天。大家也都知道零售商最怕的就是库存周转率太低,买了人家的东西自己又卖不出去。库存金额降 19.2%,现货率也有提升,GMV 上升 1.9%,而周转天数下降到 16.5天。就是说我们主要是在不损失这两个标准的情况下,降低了这部分人力成本。

还有一个办法根据某一个电商的特点,叫闪购,出一份货卖一个星期就不卖了,那么这个时候他们通常这个电商把那个星期的预测,需要备多少货就决定下来,我们采取两阶段的策略,首先我有一个总的估量,但是我发货的时候是发三天的货,通过第一天的销量我再决定追不追货,不知道大家听懂了没有,本来一周的需求量是 100,我实际送到前沿仓库送 60 件,头一天的这个销量是够,我是否需要把这 40 件补上去就看第一天的销量,第一天的销量对后续的这个预测度就更高。

王曦也是我们斯坦福的学生,现在是杉数的产品经理。设计了一个叫 Stockgo,根据我们跟电商还有其他接触的这个规律,我们觉得应该给每一个中小电商,至少提供一个可能的工具,观察库存的周转来确定,帮助他决策。

这里面有很多的功能,比如说对目前库存状态的量化评估,对高精度的销量预测,高精度的补货策略,供应链管理的智能化转型,包括很多的机器学习工具还有深度学习工具,对你的库存状态进行评估,精确到每一个 SKU,还有补货策略,以及个性化的全云端解决方案,也可以直接把数据传送到杉数,然后帮你进行诊脉。

总的目的是,把这些 OR 的东西对经济起大作用,这是已经在跟很多 ERP 的公司发给他们使用,通常周转率会提高到 50%,资金及人力成本降低,电商自动化库存能力也都是在提高,这是一个小工具,到时候这些能够为广大的小电商服务。你也可以自己调整,但是至少给了你一个可能性。

三、投资组合优化

最后我就讲一讲最近还研究一些投资组合优化,也就是防范风险。

这里面很多情况有一个叫 Markowitz,叫现代投资前沿理论。Markowitz 也是在我们斯坦福工作过一段时间,把投资组合的问题写成一个二次规划,它的目标函数不是线性函数,是二次函数,所有的约束也都是线性。

如何解这个问题解的最快,这个时候我们就有很多的问题,因为出现了二次函数呢,大家知道在统计中,二次的 X 的平方通常描述变化量,我们需要波动不太大,这就是简单的这个二次函数,实际上要解的也就是二次规划,常见的软件 Barra、Axioma、ITG、Mosek 等。

那么在交易过程当中,你的算法你的求解器比人家快一些,我个人认为高频交易的竞赛也就是算法速度的这个竞赛。我知道国内就用到过这样的模型,自己解需要解 10 秒钟的时间。从 10 秒到 0.04 秒,这里面有算法的模型。

FICO 也是二次规划的问题,很多大数据公司,越来越重视优化,我个人认为美国最早的大数据公司就是产生 FICO 的一家公司,国内是叫征信打分,就是最早的一个公司把个人所有的信息收集起来给这个人的信誉打分。我 1982 年去美国要租房子到银行开款,人家就必要 FICO,我说我是中国来的没有,到美国租房要担保首先就是看这个 FICO,打这个分。

这个公司后来做的很好,大家都用他的 FICO,也就提供这个服务,包括在网上查一查这个征信也都要交钱,这是美国很早的大数据公司,收集很多公司对每个人也都有打分。就是我说的英国优化公司,就被这个 FICO 公司买下来,在大数据处理中需要优化,能力需要加强。

这里面刚才我提到,我个人呢,包括杉数里很多我的学生,也跟美国运通公司做了很多,它是一个纯信用卡公司,不是一个单元,实际上是一个担保公司。信用卡消费什么东西,你如果消费了什么东西,把前期的这个还上,你没什么,要还不上就加利息。那么它的资源是什么,它的核心技术是什么?就是防范风险,希望你消费但又希望你不要还钱而且希望你还钱不要还得太快,但是又不希望你永远不还。当时在运通公司我们工作的时候,有一个专门的团队就搞这个,是一个大数据公司,特别是个人的一些数据。在那个时候没有英特网,有比信用卡交易纪录的更多数据,也都是这个数据来进行识别。具体项目我不清楚了。

有一个就是我们帮他搞了一个怎么追债的算法模型,运通公司信用卡如果三个月连续不还钱,人家不还钱不能雇杀手卸个脖子什么的,所以必须要通过合理的方法博弈,心理学很复杂的过程。所以有一些和追债公司联合起来一起搞。

很多是基于算法的,国内公司搞的这个 AI 非常热,趋势跟随很紧,在有些问题上结合中国特色进行研究和开发。我个人在 AI 革命过程中,看到了中国体制的这个优点。

为什么?这可以说是文化的优点——怎么说呢?深度学习本身还在一个快速发展时期,很多理论问题还没解决,这个过程有点像我们中医,有什么问题它很有效,但是有时候也说不出什么道理来;有的时候也不是 100% 的准确,但是准确起来非常好。比如,一个癌症病人吃了几副药好了,怎么解释?解释不了。所以我觉得特别适合中国的这个文化,不问原由只看效果。西方在这块反而比较保守的。另外,中国相对来说数据壁垒意识不是那么强,像美国大公司数据绝对不会给你的,所以我觉得为 AI 开辟了很多前途。所以我就说中国相对来说数据还比较公开自由,壁垒意识没那么强,像美国大公司数据绝对不会给你的,所以我觉得为 AI 开辟了很多前途。

但是中国发展过程中忽略了算法的力量,他们通常是以问题为根本,找了一些参考资料在开源软件中找一个算法进行试一试,这是要花非常大的这个功夫,确实是要耐得住寂寞,但是要用人家的开源软件,不给的话永远会被牵着鼻子走。我知道其实他们很需要线性规划或者说其他的运营规划。但是你要买人家,出于安全考虑也不行。

比如说 CPLEX,Mosek,现在有些大学、包括财经大学、杉数科技,不光是做实际应用,也培养自己的算法开发,这样的话就比较有核心技术了,真正的成为技术公司而不是咨询公司。

所以大家投资要是很有钱的话,要耐得住寂寞,要有核心的技术等等这样的一些东西。

未来的话,我觉得真是 AI、深度学习和机器学习提供了很多的支撑,模型规模也飞速增长,因为需要超大规模的优化算法,以前我认为我就要搞出个万能的算法,解所有的线性规划都要解得快,但是我后来反观看AI是非常定制的,我可以对某一类方法用的好就用那个方法,不是追求某一个统一的算法,或者类别法。反而是比较定制化的,用中国话来讲比较实用主义一些。

不一定追求理论上的完美,有一个统一的算法,所以这点上,我觉得反过来,AI 对我们的这个东西有很大的促进,什么问题需要什么样的算法,本身需要学习的过程。

还有一个问题,我们以前比较重视凸规划,大量的问题是凸规划。现在需要考虑如何集群化、软硬件结合,如何利用 GPU 实现并行运算,包括应用在智慧供应链、智能金融、健康管理等领域,我对我们国家的挂号系统,有很多的问题能不能采取更好的方法,这样的话对大家都有好处,这个东西,我们在 OR 叫排序。

总的来说我是搞运筹,因为也是搞优化的,1982 年到现在也大半辈子看到学术研究的起伏变化,我原来比较重视理论,很多问题都是写文章,证明一些东西,也小有成就,但是人到年纪大的时候会维护自己工作利益所在。我觉得最大的利益还是对一般人生活产生一些影响,因为谁也不知道很多理论证明的结果有什么东西。我仔细想,那些用 PonyPlus 的人,你证明不证明,我可能还是用这个方法。这就是到一定年龄的时候,就追求鼓励这些年轻人,不光是有一定的学术造诣,把自己的学术成果转化成技术,对人的基本生活产生影响,这才是 OR 的本质,OR 是一个接地气的科学,是一个落地的科学,怎么落地不能云里雾里说吓死人,经过我们的试验,还有杉数这些年轻人都是从斯坦福回来的学生,像运筹学、深度学习、机器学习确实对国内一些大的企业都开始产生一些影响。

所以我就希望大家多支持我们,使得中国的企业,从一个比较粗放的形式进一步拓展为依赖于大数据、国际技术来进行决策的环境里面。

运筹学 最优算法 杉树科技 AI
赞(...)
文章评论
匿名用户
发布