我從大數據學到的事(3) Web Morphing
前言
在上一篇文中我們介紹了用於測試兩種版本網頁好壞的A/B testing，我們提到了一些常用的A/B 測試工具以及我們試圖回答的問題。我們必須認知到在某些情況下A/B 測試並不是網頁最佳化的最佳解，它有一些先天性的問題，如一次只能比較兩個版本，且我們必須等整個測試過程結束後才能進行下一步等。
以網頁管理者的角度而言，有時候我們想了解的並不一定只是二元性的問題，我們可能有數個版本想要測試，並在實驗過程中我們就想要多安排點最適合的版本給訪客以最大化利益，在這個情境下Web Morphing就派上了用場。
What is Web Morphing?
Web Morphing: Automatically matching website characteristics to customers’ cognitive styles.
白話來說，Web morphing即是透過演算法自動地分配最適合的morph給現在這個訪客。看完這句話，你可能仍然滿臉疑惑。
兩個會想問的問題大概是，怎樣算是適合這個訪客？以及如何 「自動地 」分配morph給訪客？在這邊先回答第一個問題，第二個問題在後面會用一定的篇幅來解釋。要想知道適合訪客的morph是哪個，我們必須要了解一個上面出現過的名詞cognitive style(認知風格)。
認知風格指的是個人在面對問題情境時，經由其知覺、記憶、思維等內在心理歷程，在外顯行為上所表現的習慣性特徵，也指學習者所喜愛的訊息處理方式。
認知風格必須經年累月才能建立，並對每個人做決定時有著舉足輕重的影響，因此可被視為一個適當的指標。了解使用者的認知風格，分配適當的morph給使用者，我們能夠最大化銷售。
至於認知風格該怎麼定義，舉例來說，我們可以將使用者分成三個層面來討論：
Impulsive(衝動的)/deliberative(謹慎的)
Visual(視覺化的)/Verbal(文字化的)
Analytic(分析量化的)/Holistic(全面整體的)如此一來，我們得到2³=8種cognitive styles，老實說，我們還能夠切割出好幾個有意義的類別，8種style在實際操作上可能還嫌少。可想而知對於一個impulsive-visual-holistic的人來說，他不習慣也不喜歡處理太多文字的資訊，不需要細節一次展露無遺，他想要的可能只是一張大圖，加上重點資訊標示出來，That’s it.
相對地，一個在光譜另一端deliberative-verbal-analytic的人，他不會喜歡大圖輸出的敷衍morph，他想要的是關於密密麻麻的資訊在一個頁面中全部呈現出來的morph。
看完以上的例子後，大概可以了解分割成不同風格的意義，但我們要如何取得使用者的風格呢？
．問卷調查
第一個方式是在使用者進入網頁前請他們先做一份設計過的問卷，透過分數區間來判斷使用者屬於哪種風格。這樣做的好處是得到的風格非常精準，因為問卷中充滿著針對該網頁設計過的問題，我們幾乎可以肯定在填完問卷後給使用者的頁面是我們最希望他們看到的。
這種做法的缺點也很明顯，如果進到網站前還要花個5分鐘填問卷，大多數人會直接選擇關掉這個網站。
．使用cookie
第二個方式則是透過cookie來達成web morphing，也是較為可行的一種方式。cookie是使用者在瀏覽網頁時留下的資料，在主畫面時先給定一樣的頁面，根據使用者的點擊、滑鼠游標的移動，以及停留在不同頁面的時間我們能夠大致判斷使用者的風格，爾後再進行morphing的工程。
在此module中我們使用的也是這種方式，這部分的計算同樣是Bayesian Update的概念(隨著每個動作我們對於使用者屬於各種style的posterior belief會改變)。有興趣的人可以回去複習第一篇！．跟Facebook要使用者資料
Just kidding hahaha. 這是一個蠻嚴肅的話題，非常推薦大家可以看看Netflix上的《個資風暴：劍橋分析事件》，或是參考這篇。
先整理一下思緒。我們目前已經設定好使用者可能屬於的數種style，並透過上述方式了解到了使用者應屬於哪個風格。接下來我們會想知道，最適合這個風格的morph是哪一個？
在了解這個問題的答案之前，我想先介紹一個強化學習中有趣的問題－Multi-armed bandit problem。
Multi-armed Bandit Problem
吃角子老虎機(Bandits)是賭場一種常見的遊戲。玩家拉下拉桿後螢幕上的圖案開始隨機出現。若是三個圖案都相同或是符合特定規則，玩家可以獲得獎賞。更簡化一點可以想成拉下拉桿後，玩家有一定機率獲得獎賞。
因為出現獎賞的事件為1或0，很直觀的想法是理性的玩家會透過平均過後的預期報酬率來判斷玩哪一台老虎機。多臂吃角子老虎機(multi-armed bandit)字面上意思是多個拉桿的一台bandit，而玩家拉下每個拉桿後的預期報酬都不同。為了說明簡單，我們也可以將MAB想成多台不同預期報酬率(各只有一個拉桿)的角子老虎機問題。
想像一個情境：玩家走進賭場看到了四台吃角子老虎機，其獲得獎賞的機率分別為10%、30%、70%、50%。請問該玩家應該選擇哪個機台玩？答案當然是第三台，因為它有著最高的預期報酬率，但這是我們用上帝視角觀察後得到的結論，在走進賭場時玩家不可能知道哪台角子老虎機能帶給他最大的報酬率。事實上，玩家可以有以下幾種策略：
．ε-優先 (ε-first) 策略：
因為對於角子老虎機沒有任何了解，玩家一開始會先探索(exploration)各個機台的平均報酬率，對於每個機台的預期報酬率有一定了解後，玩家便可開始利用(exploitation)，即只玩最高預期報酬率的機台以獲得短期最大利益。
舉例來說，若玩家有1000次機會，他可以在心中先設定 ε=10%，即有100次探索的機會。在前100次玩家將隨機試玩所有機台，在後900次則是將所有資源投入在已知預期報酬率最高的機台。
這樣簡單暴力的策略在大部分情況下可以獲得比隨機策略更好的報酬，但在兼顧探索和利用方面有不小的改善空間。若是ε設定太小，探索不足的情況下我們不能確定exploitation階段資源挹注的是對的機台；若是ε設定太大，即使我們可以得到很接近真實的預期報酬率，卻也錯失了最大化利益的機會。難以兩全其美的情況下，有了下一個策略的出現。
ε太小－探索不足，不確定利用的對不對。
ε太大－利用不足，無法最大化短期利益。．ε-貪婪(ε-greedy) 策略：
若說ε-優先策略是標準的”Learning versus Earning”策略，ε-貪婪策略就是"Learning while Earning”的代表。ε-貪婪策略的概念是在最大化利益的同時，也要維持探索。在每一次選擇機台時，玩家都有ε的機率去探索新的機台，1-ε的機率去利用目前最高平均報酬率的機台。甚至我們玩的次數越多，對於各個機台的報酬率有更高的掌握後會希望減少一點探索的比例，可以使用修正後的εn-貪婪策略。
在εn-貪婪策略中我們每一輪有εn的機率選擇探索，1-εn的機率選擇利用，而εn會隨著遊戲次數n越大會變小。因此隨著玩的次數越多，我們在每一輪選擇探索的機會越來越小，而較傾向利用我們已知最佳的bandit。
．Gittins Index：
Gittins Index是我們實際採用的方法。想像你是一個剛出社會的新鮮人，若對於目前工作不滿意，你大可以選擇換工作而不用浪費你的寶貴青春。但相對的，若你是一個再過兩個月就要退休的人，對你來說即使新的工作更好，意義也不大了。從以上的例子我們可以了解到時間對於我們的試驗(人生qq)是一個重要的factor，因此Gittins Index就是一個加入折現率(discount rate)概念的策略。
由於Gittins Index的計算方式牽扯過多數學式子且並非本篇文章的重點，讀者可暫時將其計算想成一個black box。
上方的表格是當我們將折現率定為1%時計算出來的結果。大家可以把Gittins index table想成統計中的f value table，我們在實務上並不會把一個一個f值親手算完，而是透過查詢自由度的方式找出我們需要的f值。而Gittins index也是相同的道理，只是我們是透過這個bandit成功、失敗的次數來查詢值的大小。值得一提的是可以看到在對於bandit沒有任何了解的情況下我們給了相當高的Gittins Index(.8699)，說明了Gittins Index在初期鼓勵探索的特色。
然而知道在每個state下，不同bandit的Gittins index後，我們該怎麼在bandit之間做出選擇呢？Gittins Index Theorem給了我們一個方向：
Gittins Index Theorem:
For any multi-armed bandit problem with:
．finitely many arms
．reward functions taking values in a bounded interval [−C, C]
A policy is optimal if and only if it always selects an arm with highest Gittins index.
Remark 1:定理不僅限使用於屬於鞅(martingales)的bandit，在一般的馬可夫鍊(Markov chains)即成立。Remark 2:對於屬於鞅的bandit，其在狀態s的Gittins index v(s)會大於等於在該狀態的獎賞函數值R(s)，其差異顯示出短期收穫對於長期獎賞的價值。
上述定理告訴我們只要每次都選擇最高Gittins index的機台玩，長期下來這將是最佳的策略。Gittins Index出色地處理了探索和利用的難題，可以說在每個階段我們都在exploitation的同時保持了exploration的彈性。
註1:關於Gittins Index Theorem的證明可以參考這篇論文。
註2:馬可夫鍊表達了某一狀態的機率分布只由上一狀態作決定，可以參考這篇介紹。
註3:鞅是滿足特定條件的一個隨機過程，也是賭徒謬誤(The Gambler's Fallacy)中的一個例子，非常有趣的概念，可以參考十大思維謬誤（一）：賭徒謬誤這篇文章。What We Actually Did
了解了MAB問題的解法後，我們會發現Web morphing是一個跟MAB很類似的問題。給定某個認知風格，我們想回答的問題是哪個morph(bandit)最適合這類型的人。而每一個被歸類為此認知風格的人進來後，透過分配morph給該訪客並觀察是否有成功事件(如購買、申請…)發生，正和MAB中選擇某一台bandit拉下其拉桿觀察是否有獎賞出現是如出一轍的。
因此，在解決Web Morphing的問題時，我們會先將每種認知風格分開處理，在同一種風格下的不同morph間先給予它們一個足夠高且相同的Gittins index，之後根據Gittins Index Theorem，我們不斷選擇最高Gittins index的morph來分配給下一個訪客，並透過訪客的成功/失敗來更新這個morph的Gittins index直到實驗結束。
這次報告內容的形式和前兩次較不同，我們得到兩份資料：第一份是某購物網站的網頁配置，及其後台數據顯示每個訪客被分配到的morph和他們分別的路徑。
第二份則是另外一家匿名公司提供他們網站中，針對某一認知風格使用者不同morph之間的Gittins indices。之所以會說形式不同是因為不同於前兩個module，這次報告的主軸較像是設計實驗，並從Gittins Index中找出些蛛絲馬跡。
我們先針對數種認知風格去修改Airbnb的網頁配置(抱歉Airbnb一直提到你…)，並設計實驗以測試不同morph在各種認知風格下分別的表現。此外，針對拿到的購物網站資料，我們找出在不同morph下消費者習慣的瀏覽路徑、習慣消費的時間分析，進而給出最佳化網頁的建議。
針對第二份資料，我們主要想回答的是Gittins indices在給定資料中是否收斂(converge)，及exploration和exploitation之間的關係。在資料中我們能知道原公司將使用者分成4種認知風格，將得到的Gittins值畫成圖後，我們可以分別得到4個風格Gittins值的演化過程：
由於各個Gittins值並不由同一起始點出發，我們可以推斷得到的資料並不是完整的，僅僅是全部資料中的一個subset。我們以各morph排名不再變動做為收斂的定義，然而從各個認知風格看來，我們並無法確定這些morph在任一個風格中已經收斂。
至於探索和利用，我們相信在整個實驗過程中兩者皆是同時存在，我們仍可以看到因為一些連續的”幸運”事件使被利用的morph在某個階段後可能會改變，證明了探索的存在，但我們主要的策略仍是相信在每一個選擇中都選擇利用Gittins值最高的morph會得到最佳解。
Ethical Boundaries
．The Gusto Trial
在1993年，Gusto(Global Use of Strategies to Open Occluded Coronary Arteries)針對心肌梗塞做了一項實驗：將心肌梗塞的療法分為4種，並將受試病人隨機分配給這四種療法，直到得到統計顯著。
該實驗包含了15個國家、1081間醫院，41021位病人，最後得到Accelerated t-PA + Intravenous heparin這種療法的30天死亡率最低(6.3%)。
人命關天的事，Can we do better?
答案是可以。教授Gui曾經做過一份研究，透過Gittins Index的理論去回測Gusto trial的資料。即使算出來的死亡率和1993年實驗中的不盡相同，我們能用少於一半的樣本數去得到相同的結論。
換句話說，若時光倒流回到1993年，我們能在實驗進行到一半就確定四種療法中最好的一個，並且在之後的病人中"利用"這種療法，以達到最低的死亡率。
But can we do so?
在回答這個問題之前，我想我們必須捫心自問：我們在乎的是誰的利益？
如果以全人類的福祉為前提，那我想答案是Yes，我們應該竭盡所能讓實驗最有效地進行，讓總死亡率達到最低。
另外一個方面，當實驗進行到一個階段，我們已經有相當的信心，去說某個療法可能是最好的，但我們的Gittins indices仍未收斂，即之後的病患仍可能因為一些低概率事件而被分配到次等的療法。若我們從病患以及病患的家屬的角度出發，我們能接受嗎？
我認為這是一個很重要的問題，當醫療權和實驗進行相抵觸，我們應該如何處理，又該如何給出上述問題的答案？關於生命的事從來不簡單，從來不是非黑即白。
結語
Web Morphing對我來說是一個非常有趣且非常符合人性的主題，機器試圖做的每一步都是以使用者出發，因此在我們看來是如此合理、如此符合直覺；但也因為如此，它涉及了許多科技倫理的問題。如使用cookie來判讀消費者的認知風格，很大程度上需要消費者同意提供他們的資料，這也牽扯到了資料權(data right)的問題。
資料權：
消費者有權利了解自己透露出的資訊，並主動規範各個網站中對於消費者資料的使用。關於讓各個網站掌握資料的威力，相信大家也都感受到，購物網站的推薦商品之吸引人，以及這幾年YouTube的廣告投放之精準．．．
舉例來說前陣子去冰島租車，才剛查完相關資訊的那天晚上，我的YouTube廣告全部都是某家租車公司，後來我也真的跟那家車行租車了XD。
總而言之，這是一個很有趣也與每個人切身相關的議題，最後希望拋出一個問題讓大家思考：
網站使用我們的資料權，增加我們消費、從事某項他們能夠獲利的行為的機會，是否存在正當性？
這篇文章到這邊就結束了，喜歡的話可以幫我拍手，有任何想法想交流的可以直接傳訊息到我的臉書：）
References
Gusto(1993),”An International Randomized Trial Comparing Four Thrombolytic Strategies for Acute Myocardial Infarction”
Bobby Kleinberg(2017), “ Multi-Armed Bandits and the Gittins Index”
Anson Wang(2017), “Solving the Multi-Armed Bandit Problem”
Urban, G., Liberali, G, Mac Donnald, E. ; Bordley, R., & Hauser, J. (2014), Morphing Banner Advertising, Marketing Science, 33 (1) 27–46.
Pistilli, (2019) “A Thompson-Sampling implementation of MAB”
Online Appendix of Hauser, J., Urban, G., Liberali, G. & Braun, M. (2009), “Website Morphing,” Marketing Science, 28, 2, (March-April), 202–224.
Herring, Louise;Mayhew, Helen; Midha, Akanksha and Ankur Puri. “How to Train Someone to Translate Business Problems into Analytics Questions”, Harvard Business Review, February 11, 2019
