Instagram一直是我很喜歡用的App，剛好先前在準備Machine Learning System Design Interview的時候在Facebook AI blog看到Instagram的探索頁面推薦算法，這篇文章第一次看的時候覺得蠻簡單的，但看了好幾次之後發覺有很多不錯的細節，因此就寫篇文來介紹一下，主要內容都是根據英文原文(Powered by AI: Instagram’s Explore recommender system)加上自己的理解整理出來的，如有任何疑問或錯誤歡迎在底下留言或是寄信給我
Instagram Explore探索頁面
Instagram探索頁面主要會針對你過去使用Instagram的行為，例如Like、追蹤、評論、以及過去看過或分享的內容，來推薦你Instagram覺得你“可能”喜歡的內容。最終讓你越來越喜歡Instagram，以提升Instagram的用戶時長跟廣告收入。基本上目前的大部分的App或Website都是走這種套路。
補充：從商業角度來看Instagram的探索功能，除了傳統推薦系統著重的「點擊率」跟「用戶時長」之外，還有一個非常重要的意義是要增加「多樣性」，讓你多探索陌生帳戶的內容，如果是熟悉的帳戶內容應該就要放在首頁，這也是為什麼Instagram探索功能的候選內容不會直接採用Alice的photos，而是要間接採用Alice的相似帳號Bob的內容(詳情參考文章後半部)。除了Instagram之外Youtube也有這樣的探索功能。探索功能相較於傳統的推薦系統要考慮的點更多，太直接跟使用者相關的不好(畢竟來探索頁面是要找新內容的)，太不相關也不好，要如何拿捏尺度是最困難的。
介紹算法之前- Instagram Explore探索頁面現況分析
原文提到超過一半的Instagram使用者至少每個月會造訪Explore探索頁面去找些新的內容(圖片、影片、Story)，以我自己使用Instagram App的經驗來說也差不多，畢竟大部分的時候都是在首頁一直往下滑看朋友的資訊而已。但別以為這功能很少人用，根據STATISTA統計，在2018 六月時 Instagram的活躍使用者已達到10億，以一半的使用者來算也就是每個月約有5億的用戶會造訪Explore探索頁面。
如果在面試時以系統設計的觀點來看，這時候就會快速算一下QPS(query per seconds)的量，先假設這五億的人每個月只會造訪一次（或自行假設x次也行），QPS就是 500,000,000/(86,400*30) = 192，也就是假設有個Instagram工程師做了這個Explore探索頁面背後的服務API，到時每秒的QPS loading是192次。 另外真實情況通常還得考慮尖峰流量的處理狀況，而且這邊的粗估也沒有考慮到即使只造訪一次，使用者在不斷往下滑的過程中也會呼叫api很多次，但這邊先不多加描述。Instagram原文直接說該功能的QPS大概是9000萬次，這樣的QPS在工程上來說是相當大的挑戰。
另外這些的推薦內容是要從Instagram現有大量的內容（所有使用者的圖片、影片）去挑選，這些內容的數量級約為數十億。要怎麼在短時間內從數十億的內容，最終選出25筆排序過的並最適合的使用者內容就是這篇文章想要介紹的。
Instagram這篇文主要有三個重點
- 創造一個新的查詢語法IGQL
- 利用Ig2Vec達成Candidate Generation
- 利用三種不同複雜度的 Deep learning model來做最後的ranking
1. 創造一個新的查詢語法IGQL
相較於一般的Data/ML 團隊在查詢使用者資料時需要自己使用SQL like的語言去查詢資料（業界通常用Hive, BigQuery之類的語言），但通常使用者的資料不會只在一張table，可能要資料科學家自己寫一堆join table的指令才能拿到自己想要的數據，Instagram團隊開發了一個更方便的查詢語法，讓資料科學家可以撰寫如Python般的簡潔語法去快速撈到資料，使用這樣的語法可讀性也比SQL高，增進整個團隊的開發效率，並因為底層是用C++來實踐，所以查詢資料的執行速度很快
但很可惜的是Instagram並沒有把文中IGQL的語法開源出來，對一般人來說可能比較沒幫助，對於ML團隊可以自己開發類似這樣的Library取代SQL，長期來看可以增加團隊的開發效率。
2. 利用Ig2Vec達成Candidate Generation
這段是最重要的一部分，由於Instagram上面所有候選的影片、圖片有數十億筆，第一個要解決的問題就是要怎麼在短時間內從數十億的內容中先挑選出比較適合的500筆內容呢？這邊Instagram用的方法概念也非常簡單，就是先找出跟你行為很像的人，看他們喜歡什麼（跟什麼內容互動），再把內容推薦給你，基本上就是協同過濾的概念。
It’s challenging to maintain a clear and ever-evolving catalog-style taxonomy for the large variety of interest communities on Explore — with topics varying from Arabic calligraphy to model trains to slime. As a result, content-based models have difficulty grasping such a variety of interest-based communities.
原文提到因為Instagram上面大家的興趣太廣泛了很難基於catalog-style taxonomy達到很好的效果（在下方個人觀點的部分有進一步討論）
所以Instagram的探索功能就放棄以主題的方式來做推薦了
Instagram的作法就是先在所有使用者中找出跟你最像的人，那要怎麼找出跟你相似的人呢？Instagram 使用NLP Embedding當中最著名的模型概念 - Word2Vec，Word2Vec模型的輸入是提供一連串斷詞後的文字(ex: wikipedia或是一堆新聞文字)，輸出是把斷詞後的文字編碼成向量，並且在現實中意思相似的文字在產生出來的向量空間中距離也會很近。
有興趣了解Word2Vec實作可以，參考這篇-自然語言處理入門- Word2vec小實作
但Word2Vec 處理的是文字，要怎麼把Instagram使用者也轉成向量空間呢？Instagram 提出了Ig2Vec 模型，但基本上就是Word2Vec的概念，Instagram會把你的互動(Like, Saved…)的紀錄變成如下圖所示的序列
其他的就跟Word2Vec一樣了，最後輸出的向量就可以當作User Embedding的向量，很可惜的是這篇文沒提到Word2Vec的細節像是CBOW, Skip gram的效果或是跟把使用者的互動變成網狀結構再用Graph embedding之類的方式去產出User embedding的比較。
蠻有趣的一點
For each version of the embedding, we train a classifier to predict a set of accounts’ topic solely based on the embedding. By comparing the predicted topics with human-labeled topics for accounts in a hold-out set, we can assess how well the embeddings capture topical similarity.
這邊有多一道步驟來怎麼評估Embedding好不好， 一般來說我們用Embedding算法都是只用最後Embedding的任務的結果，看整體效果有沒有提升來推測Embedding的效果好不好，這樣的缺點是要等下游任務完成或是系統上線好一陣子才知道，如果模型很大這樣可能要好幾天或好幾週，但如果有人工標記的offline資料，Embedding model train完可能幾分鐘就知道Embedding的結果好不好了，這幫可以幫助做Embedding的ML engineer快速修正Embedding的效果，大幅增加迭代速度，符合Facebook move fast的精神ＸＤ
有了User embedding模型之後就可以用KNN(k-nearest neighbors)，找出與該User向量相鄰的K個向量，但KNN通常是一個線性時間複雜度的問題 O(D*N) D: 空間維度 N: User數量。比如說你要找離你住最近的K的朋友，你就必須要把所有N個朋友的距離都算出來然後排序，如果在二維空間算一個朋友的的距離就是 (X² + Y²)開根號（算距離只是比大小不開根號也沒差），D維空間的話就是 (X1²+..Xd²)，時間複雜度是O(D)。Instagram的用戶有超過10億，如果你只想找離某個用戶空間中最近（最相似）的10個用戶，你必須算出該用戶與其他10億個用戶的距離，再排序取出最近的前十名，會導致運算速度非常慢。
這時候局部敏感哈希算法(Locality Sensitive Hashing, LSH)就派上用場了，你可以想像局部敏感哈希算法就是快速版的KNN，可以在近似常數時間幫你算出離某個用戶最近的K個用戶，大概念有點類似Geo Hash。這邊Instagram用的是Facebook開源的FAISS套件
這邊找候選內容的方式就是假設你有喜歡Alice的圖片，Instagram就會去找最像 Alice的用戶Bob，並且把Bob的貼文放到候選集當中，依此類推會在第一階段湊到500個候選內容，並也會濾掉一些不符合Instagram政策的貼文（像是Not Safe For Work的內容或是垃圾貼文）。這邊之所以不直接選擇Alice的其他圖片貼文是因為在探索頁面中，希望能增加你看到更多新的內容（增加多樣性），如果是Alice的其他圖片貼文應該是放在首頁。
個人觀點
一般推薦系統的作法都是把使用者分成喜歡什麼主題，來推薦相關主題的內容，通常會先用一些方式把每個人身上貼上不同的主題，這樣的方式不僅能用在推薦系統上幫助使用者做分群，在廣告上面也能提供很多的方便的功能，比方說在Facebook上如果你要宣傳某一則粉絲專頁的貼文，這時你就可以選這篇貼文要針對Python跟狗有興趣的人來做投放，這樣的優點是很符合商業邏輯、可解釋性高，但缺點就是這種主題的分類沒辦法做到太細，像是Facebook上受眾的主題只能到選到貓但沒辦法到特定品種像是德文力克斯貓（Devon Rex cats），因此如果在Instagram探索頁面的場景下使用主題的模型可能不是一個好的推薦模型
這邊Instagram採用了很不一樣的做法，一開始有點不能理解，想了很久才了解Instagram上面的Account很多都是針對某種主題來發表內容，跟一般社群媒體不一樣，Instagram上同一個帳號所發的內容同質性非常高。另外Instagram的內容其實也較難分析，大部分的內容都是只有一兩張圖片（或短影片）跟少量文字，而且帶有隱喻的梗圖也很多，ML 模型很難正確判斷這篇文是哪個主題，因此用Ig2Vec的作法我覺得非常聰明。
另外如果直接採用主題來看，這些主題會一直增加，像是德文郡雷貓或老式拖拉機，利用人為製作的主題列表來做的話，把人分到主題，並推薦這個人的主題做法可能就需要人為的一直去維護那張表，而且也不太自動化，太細的興趣也不會被考慮到（德文力克斯貓或老式拖拉機）不會每一品種的貓或車都分類。另外因為Instagram是時下年輕人的愛用產品，主題的迭代速度也很快，可能這幾天馬保國特別紅，幾週後就沒人想看他了。
3. 利用三種不同複雜度的Deep learning model來做最後的Ranking
前面從Instagram數十億的貼文中篩選到500個候選內容就是一般推薦系統的Candidate generation的階段，接下來就是Ranking階段了，在Ranking階段有分三小階段
- 第一階段 500->150 篇貼文
- 第二階段 150->50 篇貼文
- 第三階段 50->25 篇貼文
這三階段的差異根據原文敘述主要是模型的深度跟Features數量的差異，主要是因為運算效能的考量，因為如果直接丟500篇貼文到第三階段的深度模型運算量會太大
First pass: the distillation model mimics the combination of the other two stages, with minimal features; picks the 150 highest-quality and most relevant candidates out of 500.
Second pass: a lightweight neural network model with full set of dense features; picks the 50 highest-quality and most relevant candidates.
Final pass: a deep neural network model with full set of dense and sparse features. Picks the 25 highest-quality and most relevant candidates (for the first page of Explore grid).
這邊用的深度模型 multi-task multi-label (MTML) neural network，主要原因也蠻直覺，不同的action(like, save, 或是負面的動作“See Fewer Posts Like This” (SFPLT))，背後有很多概念是類似的，因此參數共用效果會比較好。而不是分開去train一個like的模型、一個save的模型、一個SFPLT的模型再合併起來
最後模型會告訴我們該使用者針對某一則貼文的各Actions機率（Like, Saved, See Fewer Posts Like This），Instagram團隊最後會設計一個權重分數來做最後的排序
w_like * P(Like) + w_save * P(Save) — w_negative_action * P(Negative Action)
有了這樣的權重分數設計，會很好的讓Instagram的產品經理做各種嘗試或是搭配一些商業策略，比如說最近想讓使用者在探索頁面看到Like的內容變多，或是會Save的內容變多時都可以讓產品經理隨時調整權重。
另外在ML model裡面也有加入一些Rule base的設定，像是如果內容都來自同一個Account的話就會額外再降低權重，以符合探索頁面增加多樣性的精神
思考
- [冷啟動問題]當一個新用戶加入，Instagram並不能很好的推斷用戶向量，可能只能塞熱門內容在Explore頁面？
