AB測試：從埋點到棄療
AB測試棄療第一步：
不管是使用頻率學派還是貝葉斯學派的方法，我們需要決策還是要走AB測試的一整個流程，但是很多時候使用AB測試來做所有決策的機會成本太高，人力成本太高（數據科學家太貴），較差的版本帶來的損失等等原因讓使用AB測試做數據驅動淪為了一句口號。
AB測試棄療第二步：
即使一個開發者下定決心走上了利用AB測試做數據驅動的道路，想要搭建一個自有的AB測試平臺成本太高，而使用第三方的AB測試服務又缺少靈活的數據分析能力。
如果某個事件沒有埋點的話，想要做AB測試就只能SDK重新發版了，在SDK還沒有達到一定覆蓋率時還是沒有辦法做AB測試，於是使用AB測試做產品迭代向後延期直到被忘記。AB測試棄療。
AB測試棄療第三步：
即使一個開發者用上了友盟+的統計SDK，科學的做了自定義埋點，科學的做了用戶的分流，預估了樣本數，正確的收集到了數據，正確的做了AB測試，然後發現兩個版本並沒有區別。或者有時甚至發現新的版本還更差（cue一下被用爛的Facebook的例子）。
作為一個運營你怎麼給老闆匯報你的負面結果，你作為一個技術團隊的大佬怎麼抉擇改版的問題。AB測試棄療。我曾經也去問過一個大佬，為什麼AB測試這麼成熟而有用的方法在中國還不那麼普及呢？大佬的說：每一次改版/運營活動後大家都等著去邀功了，誰還想著看數據分析結果呢？
在很多次做AB測試的過程中，還有大佬問有沒有迭代更快的AB測試算法呢？有沒有不那麼嚴格的AB測試呢？在運營場景的時候被問的最多的問題就是：這個活動就搞3天，你們做AB測試需要多久？你們能不能在運營活動前做AB測試？這類直擊靈魂的問題。經過深入的溝通，對於這類問題的AB測試需求其實是希望能夠在減少風險的情況下更快的，自動的優化方案。
AB測試療法
對於這些問題我們有沒有什麼好的方法去解決呢？當然是有解法的。對於第一和第二步AB測試棄療的原因的解法只能是進行科學化的埋點首先滿足主要的統計需求，因為AB測試是建立在統計模塊基礎上的。對於AB測試棄療第三步的解法就是多臂賭博機（Multi-armed bandits）。
多臂賭博機 Multi-armed bandits
那麼這種可以自動優化找到最佳方案的算法到底是怎麼回事呢？這種算法是如何實現更快的，自動的優化方案的選擇呢？
張三在拉斯維加斯
下面我們講一個張三去拉斯維加斯賭博的故事（畢竟統計學就是起源於賭博）。話說有一天賭徒張三帶著自己的積蓄來到拉斯維加斯，想要憑藉著自己黑科技眼鏡和最近研究的bandits算法贏光拉斯維加斯的賭場成為賭聖。
根據他的多年賭博經驗，賭場的每個老虎機的贏率是不同的，但是每個老虎機的贏率是不會變化的，根據江湖傳聞這家賭場存在一個老虎機贏率大於50%，他的策略就是找到那個贏率最大的老虎機。
那麼張三該如何找到那個贏面最大的老虎機呢？一個最簡單的策略就是將賭場裡每個老虎機都嘗試一遍，然後把每個老虎機的贏率都算一遍，然後選取那個贏率最大的老虎機。這個方法類似於AB測試都是將流量平均的分給了很多個方案。
這個方法的一個明顯缺點就是試錯成本很高，而且最後才能發現贏率最大的老虎機。如果我們能夠在嘗試的過程中發現一些方案可能不是最佳，那麼我們就不在那些次佳的方案上面浪費時間和精力，那麼我們是不是就可以更快的，花更少的錢找到最佳方案呢？那麼問題來了，我們應該如何定義哪個算法在尋找最佳方案的時候更優呢？
這裡計算的就是如果知道最佳方案的贏錢數減去bandits算法在探索最佳方案的贏錢數的差。
張三的bandits算法
張三作為一個賭徒自然是知道一些bandits的算法的，那麼他打算使用怎麼樣的策略呢？他從師傅那裡學到的是Epsilon-greedy和Upper bound confidence（UCB）的方法。
Epsilon-greedy的算法就是Epsilon比例的次數選擇非最佳的方案，1-Epsilon比例的次數選擇當前最佳的方案。Epsilon就是需要人工選擇的比例，比如10%的時候都是選擇非當前最佳的方案，而90%的時候選擇當前最佳的方案。
但是這個方法有一個明顯的問題，師傅臨行前告訴他使用這個bandits的方法可能會陷入局部的最優解很久都沒有辦法找到全局最優解，就是不一定能夠找到那個贏率最高的老虎機。師傅千叮嚀萬囑咐讓他小心使用這個bandits 的方法。
於是張三就決定使用UCB這個算法來賭，UCB的算法是怎麼實現的呢？
這個是每個老虎機的得分，前面一項就是這個老虎機的平均贏率，第二項是和嘗試次數有關的bonus項，其中t是目前實驗的次數，而T_{ij}則是這個老虎機被嘗試的次數。第二項bonus前還可以有一個係數來調節bonus項的影響大小。
每次實驗完成後重新計算每個老虎機的得分然後選擇得分最高的那個老虎機進行下一個實驗。UCB的bandits算法在足夠長的時間是一定可以找到最佳方案的。一般來說UCB的算法在regret的定義下是優於Epsilon-greedy的。
李四的bandits算法
話說那邊張三還有一個師兄喚做李四，早年曾經在貝老爺子（貝葉斯）門下修習過貝葉斯大法。貝葉斯大法有一個巨大的優勢就是它和吸星大法一般可以利用別人修習的成果，這就是貝葉斯裡面的先驗分布（priors）。
李四在暗中觀察著張三在老虎機上的實驗並且記錄下來每個老虎機的贏率。但是李四也不能等待過久，等到張三發現贏率最大的老虎機的時候他就沒法靠那個老虎機贏錢了。於是李四在覺得自己積累夠一定數據後下場了，他使用的是基於貝葉斯的Thompson sampling的方法。
在張三嘗試的基礎上，李四給了每個老虎機了一個基於Beta分布的先驗概率，然後自己也開始尋找贏率最大的老虎機，他的每次實驗都是基於Beta分布取到一個隨機數，然後選擇隨機數最大的老虎機進行實驗。當老虎機積累了更多的數據，Beta分布的方差也越小，每次選取的隨機數也更接近於均值，而當老虎機積累了較少的數據時，Beta分布的方差也越大，每次選取的隨機數也會忽大忽小。
張三師傅王五的bandit算法
張三的師傅其實也早早來到了拉斯維加斯。他通過內部情報知道其實每個老虎機的贏率是會隨著很多因素變化的，比如是否是周末，這個人是男是女等等。
而張三和李四的算法都是沒有考慮一些其他的外部因素的，這類考慮其他外部因素的bandits算法叫做contextual bandits。張三師傅使用的是基於UCB算法+ridge regression的LinUCB算法。
欲知張三，李四，王五到底誰最快找到了那個傳說中的老虎機，還請繼續往下看。
bandits和AB測試應該什麼時候使用呢？
圖來自於VWO的網站
bandits算法主要解決的問題是如何更快的和以更小損失的找到最佳方案。上圖就是bandits在尋找最佳方案中的流量分配的優化。bandits能夠實現以最小的損失尋找最佳方案。
為什麼還要做AB測試呢？
首先，AB測試主要用於指導重要的商業決策/產品的版本迭代，而這個決策可能是有很多個指標共同影響的，bandits現在只能是基於單一指標的優化。當然也可以把多個指標疊加成為一個複合指標，但是bandits的優化目標就是單一的一個指標。
其次，AB測試主要適用於獲得各個版本的優劣的統計置信（statistical significance）。這麼說比較抽象，就是你花了時間開發出來了一個新的版本，你需要確信的知道這個版本到底有沒有之前的版本好，到底好在哪裡？到底是留存提升了還是用戶的使用時長提升了。
這些提升和降低的知識獲得是可以使用在產品之後的迭代中的，而bandits是無法幫你分析得到這些知識的。
那麼什麼時候應該用bandits算法呢？
當你關心的問題和張三一樣只是轉化率，留存率等等的單一指標時並且你不在乎數據結果的解釋和分析的時候。當你的運營活動只有短短的幾天或者一天時，你沒有時間等到AB測試達到統計置信（statistical significance）的時候，這就是一些大佬們和App開發者提到的更加快的AB測試吧。還有就是如果你有一些長期需要優化的指標，而這些指標經常發生變化，那麼這個也是bandits的一個重要的應用場景。
圖來自於vwo的blog
總而言之，AB測試適合測試一些變化周期較長的變化，獲得的知識應該具有泛化能力。而bandits算法適合一些變化快周期短的優化場景，獲得的知識不一定具有泛化能力。
友盟+的bandits使用
在友盟+的U-Push產品裡覆蓋了大量的外部用戶，而大量的開發者的Push策略都是非常簡單的定時廣播，而個性的定製化的發送策略幾乎沒有（除了頭條系）。即使開發者想要基於已有的工具對發送時間和發送內容進行優化，現有的標籤和用戶行為數據積累也不會很充分。
國內的友商們都還沒有這個功能也是因為他們的數據量遠遠沒有友盟+的數據覆蓋度大。而美國的很多針對開發者服務的平臺如Recombee，airship，Leanplum等等不僅僅實現了發送時間上的優化，並且實現了基於用戶生命周期和其他標籤的全鏈路閉環的用戶促活和防流失的產品。
我們未來的工作是為了實現這個非常user-friendly的產品，而我們的起點是對發送時間的優化即LeanPlum的功能。如果我們能夠在用戶使用App的時候或者是接受Push消息意願比較強的時候去發送這個消息，那麼消息觸達用戶以後用戶也更加願意打開。這樣實現了提高了用戶的使用體驗和更高的Push點擊率的雙贏局面。
友盟+的時間優化方案就是基於Thompson sampling的方法，使用Beta分布來給用戶+App+時段粒度的打分。
我們發現使用Collaborative filtering能夠提高那些數據裡沒有點擊的用戶的點擊，而Thompson sampling則能夠更好的確定那些有點擊用戶的最佳發送時間。
那麼怎麼樣能夠把Collaborative filtering和Thompson sampling結合在一起提高用戶的Push體驗和點擊率將是未來探索的方向。
故事的結局
故事的最後張三，李四，王五都把積蓄都輸完了，然後離開了拉斯維加斯，因為他們不知道gambler『s ruin這個統計原理，這個故事告訴我們還是要遠離賭博，小賭不怡情，大賭更傷身。
更多乾貨