在线学习与优化

【导语】数字经济是我国经济增长的重要引擎、学术界的研究热点，也是我们“漫谈系统”广播节目经常聊的话题。数字经济有三个主要驱动要素，即数据、算法和算力。上一期节目我们邀请了清华大学经济管理学院的林志杰老师跟大家聊了数据，本期节目我们聚焦数字经济背后的算法，邀请到了北京大学工学院宋洁老师跟大家聊一聊在线学习与优化。在线学习和优化理论在数字平台收益管理与资源配置方面应用非常广泛。比如淘宝、京东等电商平台都会对用户进行产品推荐。但用户的喜好平台在初始阶段并不了解，因此需要利用在线学习与优化的理念，在不断的探索与学习中进行更好的决策。该领域的一个基本模型是多臂老虎机，你以前有没有听说过，是不是对这个怪怪的名字很好奇？那么且听宋洁老师娓娓道来。

大家好，我是来自北京大学工学院工业工程与管理系的宋洁，今天很高兴和大家分享一下我对在线学习与优化的一些理解及相关的一些应用。在线学习类问题的目标是根据实时反馈的数据进行快速的模型修正，使得模型能够更加及时反映环境的变化，从而提高决策的精准性和效率。在数字经济大背景下，平台经济也发展迅速，比较成熟的，有包括以好大夫、微医为代表的医疗服务平台，以及以淘宝京东为代表的电商平台。

在线学习和优化理论在互联网平台收益管理与资源配置方面都有着非常广泛的应用。例如很多电商平台会对用户进行商品推荐，但用户的偏好平台在开始时可能并不了解，因此需要利用在线学习与优化的理念，不断地探索和学习去进行更好的决策。

首先我们来介绍一下在线学习和优化领域中的经典理论。在线学习中最常见的模型是多臂老虎机。多臂老虎机问题指的是面对K个具有未知收益的选项时，如何通过T次连续选择来最大化累积收益。我们通常假设每个选项的收益服从一个未知的概率分布，在总共T轮的选择当中，系统每轮只能选择一个选项，并且也只能观察到该选项的收益，而无法了解未被选则的选项可能带来的收益。

因此在面对选择时，系统需要考虑两个不同的目标，首先系统需要通过探索来收集数据样本，从而对模型中的未知参数分布进行估计，即系统应该要去不断尝试不同的选项，同时未来最大化总收益，系统也需要利用已有的信息进行最优决策，也就是应该选择目前能够使得获得最高回报的选项。

由于这两个目标存在一定冲突，在线学习问题的策略制定关键就是在有限的时间范围内，如何平衡“探索”与“利用”之间的关系。这类研究中通常用“遗憾”来衡量特定算法的优劣，即该算法与参数已知情况下的最优算法的总收益差距。解决这类问题的常见算法包括贪心算法、上置信界算法、汤普森采样算法等。为了适应当前的大数据背景，学界也对多臂老虎机模型进行了很多拓展与延伸。例如在上下文老虎机模型下，每个选项的收益会取决于当时观察到的情景信息，这部分信息通常会用一个特征数据向量来表示，能够帮助我们进行模型的修正，进而做更好的一些决策。

之前提到在多臂老虎机问题中，需要利用已有的信息进行最优决策，这一步便涉及到了优化理论。也就是当我们通过探索获得了未知参数的估计值后，我们进一步要基于这些估计值，寻找到能够使得系统收益最高的最优策略。并且当我们计算算法的遗憾时，以及我们对于算法的性能进行评估时，同样需要对参数已知时的最优决策问题进行求解。优化理论覆盖的范围很广，通常需要我们根据问题的特点和性质来选择相应的方法。

例如在收益管理领域，我们的目标可能是最大化收益及价格和需求之间的沉积，由于需求很多时候是未知的，因此会采用在线学习的方法。当我们已经通过一定次数的价格实验，估计出了需求和价格之间的函数关系，接下来优化问题即找到能够使得收益最大化的价格，那么就变成了一个最优的定价问题。

根据目标函数和约束条件的不同形式，我们在研究当中可以设计多种优化问题的求解方法。例如当目标函数和约束条件都是决策变量的线性函数时，此类优化问题被称之为线性规划问题，可以通过单纯型法等进行求解。另一类常见的问题，如凸优化问题，即假设我们想要最小化的目标函数是凸函数时，我们可以通过梯度下降的方法进行求解。

此类方法的原理是我们知道梯度的方向是函数在给定点上升最快的方向，那么梯度的反方向就是函数在给定点下降最快的方向。所以我们只要沿着梯度的反方向一直进行探索，就可能走到局部的最低点。而凸函数的局部最低点即为全局最低点，因此梯度下降法可以帮我们找到全局最优解。

那么上面也是跟大家介绍了几类比较经典的优化求解的方法。最后我们再来谈谈在线学习和优化理论的应用。以前面提到的互联网平台商品推荐为例，用户的偏好平台在初始阶段并不了解，那么通过平台对于数据的收集，我们实现了一些偏好参数的估计，进一步结合多臂老虎机模型来进行建模和求解。具体来说我们可以把每种产品当做一个选项，而产品的点击率是我们需要通过实验来进行学习和预测估计的。通过一定数量的数据收集后，我们可以基于这样的信息去进行更加精准的推荐。

同时互联网在数据收集方面具有很多便利性，它还可以运用上下文老虎机模型去进一步进行模型修正，即我们可以根据用户的特征，比方说性别、年龄，一些地理位置等，来更好地预测用户的点击率。那么这些信息都可以在这些基于情境的老虎机模型当中进行建模和参数估计，实现更好的精准推荐和决策。

除了前面提到的互联网平台中的收益管理和资源配置等应用场景，在线学习和优化，还可以和社交网络进行结合应用。通过选定社交网络中一些传播信息的关键节点，来最大化社交网络中最终被信息影响到的用户质量。这些关键节点通常在社交平台上表现的是一些活跃程度很高、有一定的权威性且拥有很多粉丝的博主或者是主播。那么一些平台企业通常会给这些主播提供免费试用商品或者一些激励。

之后，主播基于自己在社交平台上的一些影响力来进行发文推荐产品，最终企业希望这些产品的推荐信息可以通过主播的粉丝群进行多次转发，进而影响到社交平台中更多的用户，以此来提高产品或者服务的知名度以及潜在的购买概率。

此类关键节点的选择同样需要我们首先对社交网络当中传播概率等未知参数进行估计，并进一步根据相应的传播影响力的目标函数的性质进行最优的一些决策。

这就是今天跟大家分享的我对于在线学习和优化的一些理论的介绍和相应的应用。再次感谢大家。

作者简介：宋洁现为北京大学工学院党委书记，北京大学大数据分析与应用技术国家工程实验室、能源研究院联聘教授，工业工程与管理系博士生导师；先后入选教育部青年长江学者，长江学者特聘教授。主要研究领域为在线学习、仿真优化及在系统工程领域的应用，在国际高水平期刊发表学术论文70余篇。承担国家自然科学基金创新群体、重大、重点等多项课题。2022年获得中国系统工程学会第六届“系统科学与系统工程科学技术奖”青年科技奖，担任中国系统工程学会第十一届理事会理事。