0
| 本文作者： 張利 | 編輯：溫曉樺 | 2017-04-14 15:08 | 專題：雷峰網(wǎng)公開課 |
在上一期雷鋒網(wǎng)AI掘金志硬創(chuàng)公開課《十大場景案例詳解：人工智能如何提升商業(yè)效益》中，我們通過案例詳細介紹了AI用于商業(yè)實戰(zhàn)中的場景和效益。而為了真正幫助推動AI落地，我們將帶來更多場景單點技術干貨分享，以饗讀者。
因此，本期公開課，雷鋒網(wǎng)邀請到杉數(shù)科技CTO王子卓博士來進行主題為“如何利用機器學習做運籌優(yōu)化與智能決策”的分享。
以運籌優(yōu)化與智能決策為例，王子卓表示，大數(shù)據(jù)要產(chǎn)生實質價值，必須真正提升決策質量。規(guī)律性分析能夠從海量數(shù)據(jù)中發(fā)掘出規(guī)律，但是找到規(guī)律并不自然而然帶來決策方案，所以運籌優(yōu)化學和機器學習，就是將實際中決策問題轉化為數(shù)學模型，并用高效的優(yōu)化算法求解。因此，本次公開課，王子卓博士將分享他在解決實際問題過程中的建模、算法優(yōu)化實踐經(jīng)驗。
王子卓，杉數(shù)科技CTO、明尼蘇達大學工業(yè)與系統(tǒng)工程系助理教授，曾就職于IBM Watson研究中心及Janestreet capital等機構，擔任分析/研究員；清華大學數(shù)學與應用數(shù)學系學士，斯坦福大學金融數(shù)學碩士，斯坦福大學管理科學與工程博士，主要研究方向為定價與收益管理，電子商務、網(wǎng)絡經(jīng)濟學，隨機優(yōu)化與魯棒優(yōu)化及其在管理科學與金融中的應用。
杉數(shù)科技是一家專注于打造人工智能決策的初創(chuàng)公司，杉數(shù)科技旨在通過人工智能算法構建企業(yè)在大數(shù)據(jù)時代下的決策閉環(huán)——從數(shù)據(jù)收集、規(guī)律分析、到最終的決策，主要服務客戶領域為電商零售、物流、金融。
以上是王子卓博士公開課視頻，強烈建議先看視頻！
以下是本次公開課實錄，雷鋒網(wǎng)做了不改變原意的編輯：
我今晚分享的內容主要有運籌優(yōu)化的背景；什么是運籌優(yōu)化；運籌優(yōu)化能解決的問題；運籌優(yōu)化和機器學習之間的關系；最后展示幾個運籌優(yōu)化在實際中的應用以及和機器學習共同解決實際問題的場景。
如今是大數(shù)據(jù)的時代，公司都希望能利用數(shù)據(jù)做更好的決策。我認為從數(shù)據(jù)到?jīng)Q策主要有三個步驟：
第一是數(shù)據(jù)的采集與管理，這是大數(shù)據(jù)時代的根本，這部分更多是由計算機技術實現(xiàn)的，包括硬件技術和軟件技術，可以認為是數(shù)據(jù)驅動決策的原材料；
第二是對數(shù)據(jù)進行規(guī)律性分析，找到數(shù)據(jù)背后的規(guī)律，以預測未來，這一步是由統(tǒng)計技術或者機器學習技術完成的；
但在實際的場景中，并不是簡單地對數(shù)據(jù)規(guī)律性分析，想要創(chuàng)造實際價值，我們需要根據(jù)分析結果進行決策，即第三步，利用數(shù)據(jù)進行決策建模與求解，這一步用到的技術是我們接下來討論的運籌優(yōu)化技術。
數(shù)據(jù)是數(shù)據(jù)時代的原材料，規(guī)律性分析或機器學習把原材料加工成一些更精細內容，之后經(jīng)過決策引擎，將這些材料轉化成于公司有益的知識。具體到底什么是運籌優(yōu)化呢？簡單來說，我們可以將實際生活中的決策轉化成數(shù)學模型，并且用運籌優(yōu)化方法進行求解。
從廣義上講，優(yōu)化運籌是非常古老的學科，可以追溯到人類有生產(chǎn)生活之后的非常久遠的歷史。著名的數(shù)學家歐拉有一句話：“Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear。"意思是，世間萬物無非都是優(yōu)化過程，企業(yè)生產(chǎn)、普通人的生活，甚至一些重要的自然規(guī)律，實際上都是某種優(yōu)化的問題。給大家舉個簡單的例子，物理學中的光折射定律或者光反射定律，實際上都可以認為是光線在尋找一條路徑以最短的時間達到某一點的某種優(yōu)化問題。
通常認為，現(xiàn)代的運籌優(yōu)化起源于大約上世紀的四五十年代，大約在第二次世界大戰(zhàn)期間，那個時候很多應用都集中于軍事領域，盟軍發(fā)現(xiàn)他們在作戰(zhàn)時有很多數(shù)學問題需要解決，比如說雷達部署問題、運輸船的護航問題、炸彈的投擲問題等，這些問題都是某種非常復雜的具體場景中的優(yōu)化問題或者說數(shù)學問題。當時盟軍雇傭了大量數(shù)學家及計算機學家，像馮諾依曼等。在這期間，人們系統(tǒng)地發(fā)展出一套解決這類問題的方法，這就是運籌學最初的背景。
值得一提是，1947年，運籌學的泰斗George Dantzig發(fā)明了一個數(shù)學里最經(jīng)典問題——線性優(yōu)化問題的解法。如果大家對這種算法比較感興趣，可以在網(wǎng)上找一找，這個算法被評為20世紀的十大算法。戰(zhàn)爭結束之后，運籌學更多的被用到民用場景中，包括企業(yè)、政府、經(jīng)濟發(fā)展等，并且也產(chǎn)生了大量的新算法以及運籌學的各個分支。
在大約二三十年之前，由于計算機的發(fā)展，運籌學得到革命性突破，計算機的發(fā)展使得很多研究的算法得以真正實現(xiàn)，使得其能真正幫助企業(yè)進行優(yōu)化和決策。過去十幾年里，大數(shù)據(jù)的發(fā)展又給運籌學帶來了更大的舞臺，剛才也說到，運籌學可以認為是把實際中的數(shù)據(jù)轉化成企業(yè)所需要的決策。大數(shù)據(jù)時代到來，我們有了大量的數(shù)據(jù)支撐，那我們就可以通過這一套方法幫助更多的企業(yè)進行更優(yōu)決策。
運籌優(yōu)化有兩大重要的工具，第一是所謂的優(yōu)化工具，我們說運籌優(yōu)化，自然的優(yōu)化本身是最核心的內容。優(yōu)化問題有三個組成部分。
首先是決策。在很多實際場景中，我們都是針對特定的某件事或特定的目的進行決策。比如公司會經(jīng)常面臨著庫存方面問題，要決策每天訂多少貨物；電商可能面臨著價格的決策、定價問題，在這個場景下，決策就是每一件商品的價格；在其他場景中，我們可能需要設計最優(yōu)路線，比如快遞公司以最快的速度投遞每天的信件，決策就是投遞的路線，路線的整體就是決策。
第二是目標或目標函數(shù)，即我們做決策時希望達到的目的。比如剛才提到的有關庫存的決策，目標通常是減少庫存堆積、降低庫存成本等；有關定價的決策目的是增加企業(yè)收入或者銷量；路徑優(yōu)化的目的是使完成路線所需時間或者所需要的成本最小化。
第三是約束，實際場景中，決策往往受到客觀條件的約束，比如庫存可能受到滿足用戶需求的約束；路徑優(yōu)化可能會有道路上的限制；或有時候我們希望盡量少左轉，左轉的次數(shù)就成為約束。
優(yōu)化問題便是要尋找在滿足這些約束的條件下最好地達到目標的決策。
在解決實際問題時，有兩個關鍵的步驟：
第一是建模，將實際問題通過最有效的數(shù)學形式來表達出來，建立數(shù)學模型。
第二是求解，有了數(shù)學模型型之后，通過算法找到最優(yōu)的決策、能夠達到最優(yōu)的目標的且滿足約束條件的決策。
這兩步是整個優(yōu)化問題中核心的兩部分，缺一不可。
首先，我們需要好的模型簡潔有效地刻畫實際問題。有效很容易理解，我們希望模型能夠盡可能地和實際問題吻合，即考慮實際問題的各個因素；簡潔是為了更好求解，另外也可以讓人們更好地理解優(yōu)化模型。算法或求解也是非常重要的。好的算法可以更有效地求解更大規(guī)模的問題，現(xiàn)在遇到的問題經(jīng)常是非常大規(guī)模的，好的算法能保證在有效的時間內找到最優(yōu)化目標的決策。
第二個工具是隨機建模。主要的目的是科學刻畫不確定性，并且基于不確定性環(huán)境分析，比如分析事物的發(fā)展規(guī)律及如何做出較優(yōu)的決策。其中有很多具體的模型，比如隨機優(yōu)化模型、魯棒優(yōu)化模型、隨機模擬方法以及像馬爾可夫決策過程這樣更加復雜的優(yōu)化和決策模型。在復雜場景中，通常通過優(yōu)化加隨機建模的方法刻畫問題，再通過優(yōu)化的算法進行求解，最終得到在復雜問題場景之下的決策建議。
以上就是運籌學兩大核心內容，即優(yōu)化和隨機建模方法。
這幾年，人工智能有非常大的發(fā)展，比如圖像識別、語言識別等技術，應用領域包括自動駕駛、智能診斷等。但機器學習或人工智能的本質到底是什么呢？這個問題有很多角度，但在我看來，機器學習或人工智能應用到具體問題中的話，它的核心也是兩部分，一部分是模型，另一部分是算法。比如在自動駕駛中，我們需要通過模型判斷如何識別障礙物或路況，有模型之后，我們需要通過算法求解這個模型。
這里的算法包括兩個部分，首先模型中存在大量參數(shù)，我們需要通過算法找到模型中的參數(shù)，使得模型能最好地刻畫想刻畫的場景。另外，通過算法求解最優(yōu)決策。在自動駕駛中，我需要決定車往左走多少度或往右走多少度；在游戲里要決定我下一步做什么。算法的第二部分就是在模型基礎上做出最優(yōu)決策。
我認為，機器學習和人工智能在解決實際問題的任何場景中，核心部分仍然是模型和算法兩部分，雖然不同的場景有可能有不同模型和算法，這與上面介紹的運籌優(yōu)化是一致的。
很多時候，機器學習本身的核心也是運籌優(yōu)化的一部分。機器學習中一個非常經(jīng)典的問題：支持向量機問題，簡稱SVM問題。
這個問題的背景是這樣的：我有很多數(shù)據(jù)點，我知道一些數(shù)據(jù)屬于某種類別，另一些不屬于，我需要找到方法區(qū)分這兩類數(shù)據(jù)點，如果有新數(shù)據(jù)點進來，我就可以判斷其是否屬于某個類別，這可以用到智能診斷中。數(shù)據(jù)點對應病人的病歷，通過歷史數(shù)據(jù)，我們知道某些病人患有哪些疾病，通過這樣的分類，我們對未來病人自動診斷。
這類問題的應用場景非常廣泛，除去剛才提到的智能診斷之外，還比如垃圾郵件自動分類、模式識別等，甚至一些圖像識別都可以用類似方法處理。這是非常基本、也是非常核心的機器學習問題，從數(shù)學角度來看，這個問題無非就是優(yōu)化問題。
上面PPT的右上角坐標系中，我們希望找到一種分割方式，把紅點和藍點盡可能地區(qū)分開。假設先考慮簡單的劃分方法，比如找到一條直線盡可能將紅點和藍點區(qū)分，那么，決策就是找到這條線，這條線對應運籌優(yōu)化中的決策。有了決策，即我們找到了這條線之后，未來有一個新的點，只需判斷其在線上還是線下，就能判斷它是紅色還是藍色。
我們的目標是盡可能使這條線把不同類別的數(shù)據(jù)點能夠分開。在實際情況，顯然不可能有一條線數(shù)據(jù)點徹底分開，必然存在誤差，這種情況下，我們就要盡量減小誤差。除此之外，實際中對于這些線也有約束，比如參數(shù)要滿足特定條件。
這樣，我們可以把這個問題寫成優(yōu)化問題，通過求解找到最優(yōu)參數(shù)。如今，通過一些先進的優(yōu)化算法，可以非常有效地求解這類優(yōu)化問題，把這類問題轉化線性規(guī)劃問題或凸優(yōu)化問題，現(xiàn)在算法可以非常有效地求解。對于上述問題，哪怕存在幾百萬變量求解也可以很容易，在筆記本電腦上求解可能只需要幾秒或者幾分鐘。其中的核心是優(yōu)化算法。
剛才我們是用直線劃分，其實我們也可以用其他形狀劃分，比如橢圓、圓形等。不同情況對應不同的模型，不同的模型對應不同的優(yōu)化問題，寫優(yōu)化問題的時候需要修改，修改后又會面臨求解問題，其中會涉及到優(yōu)化問題求解算法。其中，優(yōu)化模型和算法是機器學習問題的關鍵。
實際上，基本所有機器學習問題都可以歸類成優(yōu)化問題，我們需要選擇的是機器學習模型下的參數(shù)，用x表示；歷史的數(shù)據(jù)用D表示，我們要尋找最優(yōu)參數(shù)使其可以最好描述歷史數(shù)據(jù)。f表示x和D的擬合程度，通常對于x，我們會加一些懲罰函數(shù)使得x滿足某種條件，甚至有時對x加一些約束條件。
從這個角度來講，所謂的機器學習問題，本質上都是優(yōu)化問題，如果我們有優(yōu)化算法方面的優(yōu)勢，意味著我們也有機器學習算法的優(yōu)勢。
研究機器學習或討論機器學習時，一方面模型的選取非常重要，另外一方面，背后的優(yōu)化算法也很重要，這些才是使你在面對新模型或復雜場景時都找到好的解決方案的基礎。
一、在線匹配問題
靜態(tài)匹配的問題
我簡單介紹一下靜態(tài)匹配問題，在很多場景中我們都會面臨這樣的問題，即將供給和需求進行匹配，比如打車軟件需要將出租車司機和乘客進行匹配；搜索引擎需要把搜索關鍵詞和廣告商進行匹配；在線交友網(wǎng)站需要把男生和女生進行匹配，其中每一個匹配都有其分數(shù)，即兩端匹配程度。
在靜態(tài)的匹配問題中，我們的目標是供給與需求如何匹配以最大化匹配總分數(shù)，這樣的問題實際上就是典型的優(yōu)化問題。我們按照剛才說的決策目標和約束，把它寫成優(yōu)化問題。
在實際場景中會存在一些約束，比如一個供給只能匹配給一個需求，一個需求只能配給一個供給，以及一些更復雜約束都有需要考慮，但是不管怎樣，我們把這個問題寫成優(yōu)化問題，有好的算法之后就可以高效求解。
在線匹配問題
上面講的是靜態(tài)匹配問題，即假設匹配的兩端都是在確定的情況下進行匹配的。但在實際場景中，我們通常面臨動態(tài)或在線的問題，比如在打車過程中，車和乘客都是動態(tài)出現(xiàn)的；在搜索引擎場景下，匹配一端比如廣告商是固定的，但關鍵詞是逐個出現(xiàn)的，每出現(xiàn)一個關鍵詞的時候都要決定把它匹配給哪個廣告商。這些問題涉及不確定性，我們在匹配這個需求的時候，并不知道未來可能還會產(chǎn)生哪些需求或者供給，但目標仍是使得最終匹配分數(shù)最大，在某個時間段或長時間維度上獲得最大價值。這就是一個不確定性下的優(yōu)化問題。
這個問題就比靜態(tài)匹配問題復雜不少，但我們仍然可以把它寫成優(yōu)化問題形式，只不過在這類優(yōu)化問題中，系數(shù)不是事先給定而是動態(tài)生成的，我們可以用多種方式假設，比如這些系數(shù)可能是按某種概率分布生成的，甚至我們可能都不知道這些系數(shù)分布，只知道出現(xiàn)的順序是隨機的。我們可以有不同的假設，但在每一個點產(chǎn)生之后，我們要決定如何進行分配，是分配給某資源？或不匹配這個點，這就是實際中做決策的問題。
實際上，對于做運籌優(yōu)化的人來說，我們要對這個問題設計一系列算法，即如何決策才能達到最優(yōu)目標。經(jīng)過一系列研究之后，人們提出一些算法。其中一種算法是，觀察少量樣本，求得每個右端資源j的“合理”價格，在優(yōu)化里稱之為“對偶變量”。當新的需求或匹配產(chǎn)生之后，將匹配分數(shù)和所需消耗資源的價值進行比較，看這個匹配是否帶來了應有的價值，如果匹配的價值比計算出的合理價格高的化，我們就進行這個匹配，而且選擇其中最有匹配使得價值比價格高最多。否則，就拒絕這個匹配請求，這就形成了可以實際運行的算法。
另外， 做運籌優(yōu)化的人不僅是提出一個算法，還希望能證明一個算法確實能夠達到最優(yōu)的決策，實際上，通過一些數(shù)學方法也可以證明。
從某方面看，這個問題也有一個機器學習的成分，比如通過不斷觀察樣本，機器可以學習每件商品的價值。本質上，這也是優(yōu)化結合隨機建模的問題，我們剛才講到優(yōu)化和隨機建模是運籌學的兩大核心內容，通過這樣的算法和模型，我們可以面對這種實際的場景，達到長期最優(yōu)的策略。
二、收益管理
第二個是關于收益管理的場景。簡單來說，收益管理就是定價和銷售問題，商家要決定其商品以什么形式什么價格賣給消費者，或者說希望以正確的時間將正確的商品以正確的價格賣給正確的人，通常在進行收益管理的決策的時候會有這樣的過程。
首先是數(shù)據(jù)采集；然后根據(jù)數(shù)據(jù)對消費者進行分析，比如客戶挖掘、對消費者進行標注、分析消費者對價格的敏感程度等；在此基礎上進一步?jīng)Q策，比如用什么樣的價格買哪些商品、什么時間賣等。實際上這部分與我們開始說的從數(shù)據(jù)到?jīng)Q策的鏈條是一致的。
組合定價
其中一個很重要的問題叫組合定價問題。商家要管理很多商品，商品之間可能會有需求的關聯(lián)性，比如同時銷售可樂和百事的話，一種商品的價格可能會影響另一種商品的銷量，在這種情況下，商家需要決定如何對多種商品進行組合定價。其中的決策就是每一種商品的具體價格，目標是未來最大化整體收益，這個過程也涉及建模和求解兩個步驟。
這里也有很多模型，比如通過消費者選擇模型刻畫消費者對商品的選擇，其中用到優(yōu)化和機器學習選擇最好的模型。有了模型之后，我們要決定如何定價以最大化利潤或銷量等，這就變成了非常經(jīng)典的優(yōu)化問題。除定價以外，商家還面臨著像選品、商品展示區(qū)等問題，仍然需要考慮到商品之間互相影響情況，這些問題均可以寫成優(yōu)化問題，同樣需要優(yōu)化算法對這類問題求解。
三、動態(tài)定價
上述組合定價問題可以看做靜態(tài)問題，在實際中我們經(jīng)常遇到動態(tài)問題。一開始，我們對消費者的偏好不是非常了解，希望通過動態(tài)定價、數(shù)據(jù)收集來了解消費者對商品的偏好、或學習消費者的行為，這就涉及如何動態(tài)定價的問題。我們要確定到底要通過多少數(shù)據(jù)點、怎么設計這些價格以學習消費者行為，同時不能由于定價波動太大造成收益損失、或對消費者產(chǎn)生負面影響，我們要確定什么樣的方案是長期最優(yōu)方案，既能學習到消費者對商品的偏好，又能夠獲得最大收益，這個可以認為是機器學習問題，也可以看做運籌優(yōu)化和機器學習結合問題。
同樣，關于這類問題有大量算法，但重要的是，我們不僅要提出算法，還要證明這個算法是所有算法中最好的。
四、路徑優(yōu)化
我們之前也提到過，像電商、物流公司等企業(yè)在經(jīng)營過程中都會面臨這樣的問題：比如每天要把貨物送達幾個消費者，想要設計一條在最短的時間或路程內完成任務的路線，這就是路徑優(yōu)化問題的基本形式。
有許多優(yōu)化模型或算法可以求解這個模型，但實際生活中，基于這個基本的場景還有很多非常復雜的變化或需求，比如不僅要送貨，還要取貨；不僅是一個人送貨，可能有很多人或車要送貨或取貨，這就涉及到車輛和人員的分配問題；或有些需求不是事先確定的，還有一些實時需求，比如快遞員突然接到上門取件的訂單；另外，在送貨路途上花費的時間也有很大不確定性，這些情況下，就需要在線算法應對這樣的需求。現(xiàn)在比較火的自動化倉庫管理，機器人管理倉庫時會遇到貨物擺放問題、機器人如何取貨問題等，這里要平衡不同機器人之間任務以及優(yōu)化每一個機器人路徑，其中也會面臨復雜的建模和求解問題。
實際場景中的問題是非常復雜的，而把這些場景的要求轉化為數(shù)學模型，之后進行求解，這是運籌優(yōu)化最擅長的。
說了這么多，我希望大家能了解這幾點：
對運籌優(yōu)化有基本了解。什么是運籌優(yōu)化，對于實際問題能產(chǎn)生什么價值，運籌優(yōu)化和機器學習的關系。兩者之間更多是一種相互支持的關系，在很多場景下，優(yōu)化運籌和機器學習結合才能提高好的解決方案。
運籌優(yōu)化的一些基本方法。包括優(yōu)化和隨機建模。
最后，我想談一下國內運籌優(yōu)化的發(fā)展情況。
總的來說，國內運籌優(yōu)化的發(fā)展比美國要落后一些，美國很多的大企業(yè)，像亞馬遜、谷歌或者一些物流企業(yè)，內部都有一大批運籌學背景的團隊來解決公司生產(chǎn)可能面臨的問題，比如亞馬遜中有50~200個的運籌學博士做定價、庫存、物流等方面的決策支持。這方面，國內要落后一些，但我認為，未來幾年，國內很多企業(yè)會在這方面轉型，過程中正需要運籌優(yōu)化的技術，這些技術幫助企業(yè)將大數(shù)據(jù)轉換為真正的決策。
相關文章：
IBM人工智能技術商業(yè)化落地現(xiàn)狀：目前已滲透到60多個職業(yè)領域
大數(shù)據(jù)反欺詐+保險賠付：看互聯(lián)網(wǎng)保險如何普惠
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權禁止轉載。詳情見轉載須知。
專題
