該文章來自阿裡巴巴技術協會（ata）精選集
何為雙鍊路實時計算體系？
微觀實時計算鍊路
a) 最細粒度商品/店鋪/使用者資料的實時
b) 底層模型的實時
宏觀實時計算鍊路
相比微觀實時，宏觀實時的對象粒度更粗，更上層
a) 以實時效果為目标，基于bandit learning的實時政策尋優
b) 以流量實時勻速化投放為目标，基于pid控制理論的實時流量調控
在整個實時計算算法優化工作中，金榕教授給予了細緻指導，使得項目得以順利開發和落地。
pora是淘寶搜尋基于istream（自主研發的運作在hadoop yarn上的實時計算引擎）+ hbase基礎平台打造的一套實時計算和線上學習系統，支援在秒級别内對海量使用者行為及其相關聯的海量商品作實時分析處理，從中提取多元度的使用者/商品資料特征，并采用分布式parameter server架構進行線上學習，進而使使用者行為可以在幾秒内影響搜尋排序等線上服務。pora目前已經應用于實時個性化搜尋/推薦、實時反作弊、實時流量優化等諸多領域。
雙11期間，pora實作7*24持續運作無重新開機，雙11當天共處理消息量1300億，峰值qps 500萬。
igraph是淘寶搜尋打造的實時線上圖存儲與查詢的系統，可以提供大規模kv/kkv資料的存儲、查詢、更新和計算服務。目前支援了包括搜尋/推薦個性化在内的衆多業務線。
雙11期間，igraph 通路峰值qps 245w，同時支援大規模實時資料更新，如使用者實時點選表峰值更新qps 28wqps，使用者資訊表 40w qps
sp（search planer）是搜尋面向前端應用的統一服務接口，根據使用者指定的查詢條件制定查詢計劃，查詢包括qp,igraph,isearch5引擎在内的各個搜尋後端系統，得到最終結果傳回個前端。sp通過将業務邏輯從前端往後端下沉，簡化了搜尋調用邏輯，提升了前端系統性能。
isearch5是搜尋最新一代引擎平台，服務于淘寶、天貓、b2b等各個搜尋業務線，支援秒級實時索引，資料實時更新等衆多特性。
基于galaxy平台的實時報表系統，實時統計分平台/桶/政策/商品類型/使用者類型等多元度業務名額資料（包括但不限于曝光,點選,成交與加購等）。該系統提供分鐘級别的實時回報精度，讓算法、産品、營運同學能夠在功能更新、大促、營運推廣中及時準确了解業務名額的變化，通過強大的資料閉環功能為快速響應及決策提供依據。該系統同時提供了豐富的使用接口，為算法同學在大促中線上尋優提供了可靠實時資料。
btsserver是搜尋的分桶測試管理服務平台，能夠随時調整每個分桶的測試内容。依托實時報表系統産出的實時資料，今年在btsserver平台上開發了實時政策尋優和實時流量調控兩個子產品，可以根據實時報表做智能化的分桶測試尋優，實作整體效果的最優化。
資料和模型是算法的兩大核心，14年基于pora我們現實了資料的實時更新。15年我們又在pora上開發了基于parameter server架構的線上學習架構，實作了模型的實時更新。
why線上學習？
在batch learning中，一般會假設樣本獨立服從一個未知的分布d，學習得到的模型都是基于該分布的，如果分布變化，模型效果會明顯降低。而在實際業務中，很多數情況下，一個模型生效後，樣本的分布會發生大幅變化，是以學到的模型并不能很好的fit線上資料。而實時模型，能通過不斷的去拟合最近的線上資料，解決這一問題；同時實時模型還能catch使用者和商品的實時特征，是以效果會較離線模型有較大提升，特别是在實時資料極為豐富的情況下，例如雙11和雙12這種大促。
why秒級更新？
相比曆史長期模型，小時級模型和純實時秒級模型的時效性都有大幅提升，為什麼我們選擇了純實時模型？一個方面是系統工程能力的允許，另外更重要的原因是業務需要，特别是在雙11這種成交爆發力強，變化劇烈的場景，秒級實時模型時效性的優勢會更加明顯。下圖是大家都看到的今年雙11實時成交額情況，前面1小時已經完成了大概總成交的1/3，小時模型無法很好的catch這段時間裡面的變化。
子產品介紹：
sample worker：處理日志生成訓練樣本，fetch最新的模型計算特征梯度
featurehq：将相同特征的梯度送到同一個featureworker
feature worker：接收梯度，計算更新模型
hbase：模型存儲（lr模型的w，ftrl的z,n，矩陣分解的user,item向量）
特點：異步，并行，平台化
異步，并行：整個訓練過程就像不斷疊代的map-reduce，需要注意的是sample worker中的各個worker和feature worker中的各個worker是完全異步的，并沒有做任何同步。一開始我們也非常擔心這種純異步的sgd訓練方式是否有問題，但實驗發現這套系統能夠很好做到模型收斂，并且得到和同步訓練差不多的準确性。
平台化：做為一個線上學習架構，我們不僅僅隻是提供現成的算法，也可以讓大家能夠在這個架構下友善地開發實作自己定制的線上學習算法。目前是把三個主要的接口開放給開發者自己來實作：calcsample（樣本采樣，樣本特征,目标建構），calcgradient（梯度計算），calcweight（模型更新）
目前這套線上學習架構已經支援訓練樣本百億級别/每天，特征十億級别。包括pc搜尋，手淘搜尋，天貓搜尋，聚劃算，淘金币在内的多個業務場景已經有10+的線上模型跑在上面。
logistical regression（邏輯回歸）作為最常用算法之一，是我們實作的第一個線上學習算法。随後在lr基礎上了做了簡單的改動實作了ftrl，模型更新（calcweight的實作）這一步不同。這裡就不介紹lr和ftrl的原理了，有非常多的資料可以參考。下面說一下遇到的一些問題：
a) 純異步訓練的收斂性和準确性
前面提到過，異步訓練的收斂性和準确性是我們非常擔心的點，實際的實驗效果表明模型能夠正确收斂，并且準确性和離線同步訓練比也差異不大。
下面是某一場景下的ctr預估應用在不同訓練方式下的auc對比：
線上異步訓練的auc比離線同步訓練的auc是要差一點，但差異很小。有初值下效果更好一點。都遠好于使用曆史長期模型（曆史資料訓練的模型）的效果。
b) 模型穩定性
模型不穩定是線上學習在實際應用中遇到的一個大問題，比如在搜尋排序場景下，如果短時間内模型變化太大，會造成排序結果劇烈變化，使用者體驗不連續。為了解決這個問題，預測打分的時候使用模型的平均值，可以有效地平滑掉這種不穩定。
實際操作中，還可以考慮把最開始的n輪去掉後再做平均（無初值情況下，最開始n輪模型的效果可能還比較差）。
當然了，模型的穩定性和時效性是一個trade off，為了兼顧這兩點，更好的做法是使用移動平均（目前輪的前面t輪模型做平均）。
c) 熱點問題
通過前面的架構圖可以看到，feature worker其實就是一個reduce的過程。如果存在熱點特征，比如截距特征beta0，這類特征的梯度會非常非常多，會造成這個特征所在的feature worker處理不過來，出現阻塞，進而造成這個worker節點上的所有特征的更新都延遲。為了解決這個問題，我們在sample worker上做了feature grad的合并（類似于mapreduce的map節點做local combine），大幅減少了往featurehq發送的資料。
與online lr/ftrl 不同的是，線上學習中有一類是直接針對 auc 進行優化的算法。auc 直接優化是 np-hard，但有一些近似算法能夠進行高效的求解。我們實作了 auc 最大化算法- one-pass auc (refence one-pass auc optimization, wei gao, rong jin, lu wang, shenghuo zhu, zhi-hua zhou. artificial intelligence journal, 2014 )
why pair-wise？
在搜尋中，算法更關注的是商品的排序，而不是單個商品的算分。使用point-wise算法，是通過回歸單個樣本的分數進而得到排序效果；而使用pair-wise算法，是直接優化商品之間的序關系。是以從loss的角度來看，point-wise上會有不必要的限制，這些限制常常會對序關系産生負向影響；pair-wise算法目标明确，是沒有這些限制的。另外，從工程架構上來開，日志的不均勻會對point-wise的算法産生極大的不良影響，而pair-wise則不受此幹擾。
是以，我們設計了一套針對排序優化的實時協同過濾架構，并在這個架構上設計和實作了2個pair-wise算法。2個算法均有實時和離線2部分，離線模型會作為實時模型的初始值使用，使用odps graph實作；線上模型由pora實作。下面會簡單介紹模型的含義和實驗結果
假設我們有m個使用者和n個商品，除使用者向量
和向量
外，我們還為每個商品j學習一個bias，
。此時的我們将每個使用者對每一個商品的偏好标示為：
在搜尋排序中，我們更關注的是商品之間的順序，而不是模型對偏好程度的預測值和真實值之間的平方誤差或絕對值誤差。從搜尋日志中我們抽取訓練三元組
，其中每一個三元組
表示使用者i更偏好商品j，相比于商品k。對于這樣的一個三元組，我們定義損失函數如下
其中，
是使用者在商品j和k上的真實偏好程度，例如對于一次搜尋展現引導的行為，可以設定偏好程度為：成交>加購>收藏>點選>pv。注意這裡我們引入了hinge loss，目的是當我們的模型排序正确時不去做備援的抑制。此外，我們還使用了已有的一份資料
，描述的是商品之間關于被購買行為的相似度矩陣。如果2個商品在被購買的行為上相似，那麼它們在隐空間的向量應該是盡可能靠近的。是以，類似于經典的拉普拉斯特征映射（laplacian eigenmap），我們使用了一個正則項展現這項限制
最後，我們需要優化的目标函數可以形式化為
定義u為全體使用者，i為全部商品，使用者回報s表示implicit feedback，
，每個商品，item(
)，由2部分組成，分别是靜态特征（static descriptors）和動态特征（temporal characteristics）； 每個使用者，user(
)，同樣由2部分組成，分别是特征(u)與使用者id(b)；行為，
（interactive feedback），其中
是0/1（實際上也可以是實數，這裡隻考慮0/1的implicit feedback）,表示使用者u對商品i的偏好。
我們排序的目标是對使用者設定全部商品上的排序方案，
，其中
表示偏序關系。
另外，我們定義
為使用者u點選的全部商品,
為點選過商品i的全部使用者。
在bilinear model中，每個使用者對商品的偏好表示為：
d和c分别表示使用者和商品的特征次元，b表示每個使用者id在商品特征上的偏移。将使用者的b看做自身feature的一個稀疏次元，那麼考慮商品有靜态和動态2類屬性，有：
該模型可以看做是将使用者feature的每個次元向item的每個次元做投影，然後在商品空間上做點乘，w表示投影矩陣。
有了上面表示後，根據貝葉斯公式，我們求一個最大後驗估計(map)。假設所有參數表示為
，則後驗分布為：
右邊第一項
，這裡
這裡表示判斷函數。考慮到資料全局上的反對稱性，可以對它進行簡化：
在已知
和
的情況下，偏好i與j的內插補點表示為：
那麼點選i而沒有點選j的機率為：
我們算法的目标是最大化後驗，于是：
實時個性化算法的目标是在淘寶搜尋中提升使用者的搜尋體驗，提高流量效率。從名額上表現為搜尋的ndcg/mrr等名額，以及線上的ctr等名額。
下面2張圖是一天的模型曲線，左圖是矩陣分解的ndcg變化情況，右圖是雙線性模型的mrr變化情況。可以明顯的看到随着模型的運作，mrr和ndcg值在不斷上升，直接達到收斂。在收斂時候的名額值較最開始的初期，會有20%以上的提升。
從廣義上講，政策可以是非常寬泛的概念。但在這裡我們講的政策主要是指排序中的特征融合政策。說起特征融合，ltr（learn to rank）是最傳統的特征融合方法，也在我們搜尋排序得到了廣泛應用。但傳統的ltr在特定場景下有一些局限：
a) 特征分無法通過曆史資料準确擷取。比如雙11當天的實時特征分，日常流量下和大促流量下，特征分的分布完全不一樣。
b) ltr的優化目标是我們定義的一個目标函數，并不是最終的線上結果，但任何目标函數的假設，都與線上真實的目标有一定的gap。是以離線效果（比如ndcg）提升，并不代表線上測試效果一定提升。
基于上面的局限性，今年我們嘗試了另外一個思路，直接基于線上最終bts結果做政策優化。而bandit learning和zero-order優化是正是解決這類問題的方法。
在學術領域，與bandit learning和zero-order 優化問題相關的方法非常多。但我們實際線上排序系統特征多，參數空間大，同時我們希望整體收益的最大化，即對不好的政策投入做嘗試的流量盡量少，并盡快收斂到比效好的政策；是以，我們接合了bandit learning和zero-order opt設計整體算法流程圖如下：
基本的思路就是：先用mab從有限的離散政策集合裡面選出最優政策，然後在最優政策基礎上用zeroorderopt做連續參數空間的進一步尋優。在尋優過程中會不斷把目前的最優政策全量到接受桶。
根據已知的知識找到最優的政策，同時還能發現是否有新的政策收益更大，這是典型的增強學習裡的double e（exploitation and exploration）問題。定義n個政策集，μ1,..,μn是n個政策收益分布的均值，每輪t選擇某一個政策it=i，都可以得到其收益g(i,yt)，是以，在t輪之後，定義損失函數ρ=tμ∗−∑tt=1g(i,yt)，μ∗是每輪最大收益的均值，即μ∗=maxn{μn}。如果每一輪都選擇都是最優的，那麼損失ρ就等于0。定義g(i,yt)的無偏估計g˜(i,yt),
顯然，e[g˜(i,yt)|i1,...,it−1]=g(i,yt)。
具體算法如下：
其中β，η，γ是參數。
首先需要選擇參與融合的特征，然後将這些特征按照權重高、中、低檔組合成候選政策集（特征a低中高 * 特征b低中高*..），并剔除一些人工認為不靠譜的政策。最終，我們選擇n=18個政策。
開始尋優時，會從所有測試捅中拿出m個桶做bandit，剩餘的桶做接受桶。每輪按照機率p選擇m個政策做測試，每輪測試半個小時。然後根據這半個小時的實時回報資料計算收益g(i,yt)，并更新每個政策的機率pi,t。如此反複執行上述過程。同時每輪将目前機率pi,t最大的政策發送到接受桶。
當mab收斂後（某一兩個政策的機率p明顯勝出），因為政策集是有限的，全局最優的政策可能并不在裡面，是以，我們會再采用extra gradient算法在連續參數空間内繼續尋優，找出更優的政策。
question
為什麼mab收斂前就發送接收桶了?
answer
判斷mab(從候選離散政策集合選最優)是否收斂的目的是用來判斷是否可以開始run extragradient了(作為extragradient的初值),mab本身并不是一定要收斂才發送。因為mab收斂需要時間(雙11當天早上大概7點才第一次收斂)，如果收斂之前不發送，那麼這段時間(7點之前)接受桶的效果是浪費了的，沒有享受到測試桶更好的效果。
那麼沒有收斂的情況下是否能發送呢？
a) 我們判斷收斂的條件比較嚴格，即使沒收斂目前的最優政策也是不錯的。
b) 我們在發送之前還有一個和接受桶做pk的最後保障環節(不管是否收斂都會有這個環節)，pk赢了才會發送。
今年的雙11紅包有了很多不同于往年的新鮮玩法，其中個在搜尋發放的關鍵詞紅包就利用到了實時流量調控技術。關鍵詞紅包發放有兩個方面的要求：一方面，需要履行與商家簽訂的合同，完成承諾給商家的到店 uv 數量；另一方面，要求完成的過程是平穩可控的。在 uv 資源充分的情況下，隻要設定較大的發放機率，就能完成第一個目标。 然而發放機率過大容易導緻很快就會将一天的目标完成了， 達不到平穩發放的目的。 在這裡，我們采用 pid 控制器技術來控制發放的速度。
a) pid 控制器介紹
在控制理論和實踐中，pid 是一類廣泛使用的控制方法。pid 是“比例-積分-微分”的簡寫， pid 控制器根據控制原理，對偏差進行比例、積分、微分的調節，進而使被控變量的實際值與既定目标保持一緻。
上圖是pid控制系統的圖示，其中 e(t) 是誤差信号，u(t) 是控制量，kp, ki, kd 分别是 p、i、d 的系數。
比例（p）控制：直接針對誤差進行比例調節，誤差越大，比例信号輸出越強。舉個例子，熱水器溫度調節系統，目前溫度離設定溫度差異較大時，就會開啟較強的加熱功率，等到離設定溫度很近時，加熱就會緩一些了。
積分（i）控制：對累積誤差進行控制，其功能就是消除累積誤差。
微分（d）控制：以誤差的變化率作為控制因素，例如溫度上升較快時，雖然沒有達到設定溫度，微分控制此時會适當降低加熱功率，而單純的比例控制器則可能導緻超調現象。
搜尋作為流量一大入口，除了做好流量的利用效率，還需要從宏觀上做一些流量平衡。比如集市和天貓之間流量平衡，大/小/腰部賣家之間的流量平衡。我們目标并不僅僅是短期成交的最大化，而是考慮平台長期利益，在一些流量平衡限制條件下的最大化。實時操作中也利用了pid控制器的技術。
上述實時計算體系在今年雙11發揮了至關重要的作用，是我們搜尋成交增長的核動力。下面是各業務線和基準桶（平時全流量生效的最優效果）對比的提升資料。
pc搜尋/手淘搜尋
預熱期引導成交提升 11%，當天成交提升 8%
天貓搜尋/貓客搜尋
當天成交提升 7%
店鋪内搜尋
當天成交提升 3.4%
要感謝的人太多，搜尋大部分同學都或多或少參與了實時計算體系的建設，要感謝大家的共同努力。
去年雙11，實時計算第一次在大促展露頭角，并初露鋒芒。今天雙11，實時計算在各條業務線全面開花，實時計算體系也更加豐富。我們相信這遠遠不是終點，期待未來實時給我們帶來更多的精彩！