如果我是 Threads 工程師，要怎麼寫推薦演算法

我不是 Threads 工程師，但在以億為等級的系統做推薦，只是想想也好玩！

單純從技術上思考，做一個推薦系統可能的思路、手法、考量…。這是個人的思想練習與研究練習，幻想文，不一定是真實狀況

問題 #

目標 #

先有目標 (objective metrics) 。以 Threads 為例 – 我隨便瞎說 – 使用者文章瀏覽時間。之後的演算法訓練都以目標前進

資料 #

接下來看手上有哪些資料、資料規模、現有資料能達到什麼地步、收集新資料的用處 vs. 成本

(data pipeline / lake / warehouse 等等的很重要但這篇先不提)

以 Threads 為例，可能的會有

• 物件（人/角色: 作者, 讀者、文章）
• 物件的性質
  • 作者 的粉絲數、文章數、被看被讚數… over time
  • 讀者 看、點讚、追蹤、其他行動… over time
  • 文章的觀看數、被讚數、其他行動… over time （根據時間變化有一些性質像 popular/recent values, trending/value delta, long term values）
• 物件間的關係
  • 這篇文章是誰寫的；這個 作者 寫了哪些文章
• 物件間互動、行為
  • 讀者 - 文章/作者 engagement instances, 包括不僅限於
  • 這個 讀者 過去真正看了哪些文章？點了喜歡哪些文章
  • 這個 讀者 追蹤了哪些 作者

規模上，查了一下 Threads 的使用者應該有 100M 等級，每天文章數不知。而想像中，一個 讀者 會點擊閱讀的文章在 30 天內頂多 100K 等級，也就是人雖然多，但與文章的互動是 sparse 的

問題挑戰與直覺 #

• 資料規模很大：（隨便查查假設一下） 100M 使用者，10M daily active users, 每天 100M 新文章/回文。在儲存、訓練、線上推薦都是挑戰
• 24/7 推薦：每秒都有使用者使用，推薦不能是空的
• 一個使用者能互動的有限 (壞事)：開頭幾篇推薦的契合度可能就會影響使用者的滿意度 (precision)

不過

• 一個使用者互動有限 (好事)：資料是 sparse matrix，運算上會輕鬆一點
• 一個使用者互動有限 (好事)：不見得要把「所有」相關文章找出來 (recall)

直覺： 猜測 讀者 點擊文章的順序性 “sequence” 不太影響未來點擊（模型看「一堆」契合的文章、而不是有序的歷程），所以 seq2seq 類的 (e.g. RNN, GRU4Rec) 不會是第一個想試的，但也不會排除

策略與概念 #

問題定義 #

「對於每個 讀者 進來，給出一堆文章的順序。使得他們瀏覽文章的時間，最大化其平均值 (over all active users in the last 7 days, for example)」

輸入：人。輸出：a list of 文章

策略 #

twitter 之前 open source 說「先選一些文章當候選，然後根據互動資料，重新排序，再顯示給使用者」。 Twitter 嘗試在幾億短文裡選出約 1500 則（有無追蹤的都有）。這策略跟公司看履歷分階段篩選一樣。recall + ranking 在搜尋領域也常用。

因為要媒合 讀者 與文章，所以需要讓電腦多多認識他們，建構出 讀者 跟文章的各種特徵 (features / representation) ，然後算出 契合度分數(讀者, 文章) （或者 排序(讀者, 文章) ）

其中特徵可以分成三類：

• f(文章) – 例如文章夯不夯，文章作者夯不夯
• f(讀者) – 例如他的族群
• f(文章, 讀者) – 例如他喜歡這篇文章的機率
  • f(作者, 讀者) – 算是上面的一部分，這個 讀者 會對這個 作者 文章（無論是什麼）喜歡的機率

最後，再加上突破同溫層，選一些隨機或待探索的文章

總結，策略上可能會這樣

• 第一關：用算比較快的特徵 + 能事先算的特徵 + 加上一些陌生文章（來源可隨機也可依據特徵），拿出例如幾千篇文章
• 第二關：對於第一關的文章，利用各種能用的特徵（包括算得稍微比較慢的）做 ranking 或 regression model, 去排序那幾千篇文章

第二關的 training 可以用未來的回饋。第一關的策略可能要觀察與用手調？

可能的推薦演算法 #

演算法可能會不只用一種，而是綜合相加 and/or 逐步篩選。大略分成兩類：拿到特徵跟第二關 model。文章最後有對於 cold start 的想法

雖然先列一些演算法，但思路上是先想（或同時想）有哪些特徵是可利用，再來想有哪些手法

Node2Vec #

把人（同時身為讀者跟作者）之間的交互當作一個 graph，例如有無追蹤，有沒有喜歡/喜歡了多少篇對方的文章

這個 graph 可以藉由 random walk 每次取出一些 node，當作是一個句子，取樣很多句子以後當作 word2vec 問題處理就能把 node (人) 做出 embedding

無論是 word2vec 或 node2vec，概念都是會出現在一起的性質應該都很類似，所以怎麼調整 embedding 去最大化周圍出現這些人的可能性

Item-based collaborative filtering #

「已經有一些 user 在 item 上的互動，對於還沒機會顯示給該 user 的 item，有哪些預期會有互動？」是常見的推薦問題

把 讀者 當作 user, 文章當作 item, User-item matrix 矩陣的每一個值代表某個讀者喜不喜歡某篇文章，例如可能是 1, 0, 或 missing (還沒看過不知道)

collaborative filtering 是只靠已知的關係互動去預測未知，其中

• User based: 有跟你相似的人，他喜歡的文章，你應該也會喜歡 – 相似是指你們兩個常常喜歡/討厭同一篇文章
• Item based: 你喜歡一篇文章，那你應該喜歡跟這篇文章相近的文章 – 相近是這兩篇文章被同樣一群人喜歡/討厭

Item based 是把每篇文章用一個向量代表，維度是人數，每個值代表某個人喜不喜歡，某種角度這個向量就是這篇文章的表徵

所以某個讀者喜歡了一篇文章以後，可以推薦跟這篇文章很「相近」的文章，例如用 nearest neighbors

因為使用者很多，這個向量維度很大 (e.g. 100M)，但是 sparse （不太可能一篇文章被推到所有人牆上）。要做 nearest neighbors 可能可以切 bin 或階層的 ANN 手法

Sparse Matrix Factorization #

同樣已知 user-item matrix, 另一個想法是有沒有辦法把 user 跟 item 都對應到同一個 vector space，也就是給他們 embedding，而每個 user 跟 item 的內積會近似於 user-item matrix 上面的值

這間接算出讀者跟文章的 embedding，是比較低維度但 dense 的向量。不但可以拿來算契合度(讀者, 文章)，還可能拿來算讀者之間的相似度，或文章間的相似度

算出這兩個矩陣可能可以用 ALS, 在 SparkML 上面有函式庫可用，大意上是固定其中一個 matrix 去對另一個 matrix 做最佳化，反覆交替著做

特徵: f(讀者) #

Embedding - 藉由 Node2vec 得到的

Embedding - Matrix factorization 後取的

(for filtering) 讀者族群: 從 embedding 可以做 Clustering (K-means, DBSCAN, …)，進而得到一個人（讀者或作者）的族群

特徵: f(文章) #

Popularity, trending… - 從文章本身的閱讀數按讚數，看絕對數值，或是一段時間後的變化值

Authority - 文章的作者的追蹤數、文章數等等

Embedding - 文章內容本身的 sentence embedding

Embedding - matrix factorization 後取的

特徵: f(文章, 讀者) #

契合度(作者, 讀者): 之前的互動數

契合度(作者, 讀者): 看兩個人的 embedding 相似度

User-item matrix

• Item based filtering by k-NN: 填空預測 契合度(文章,讀者)
• matrix factorization: 從 embedding 得到 契合度(文章,讀者)

題外話實際的 Threads, 我有觀察到 follower 回應的文也會出現在牆上。建築在這層關係上的文章也可以考慮

Explore and exploit #

為了「突破同溫層」與「探索新文章」，也可從文章要推給誰的角度思考

固定留一部份的候選文章名額

• 隨機從 Threads 裡面所有文章（或同語言、族群、…）拿出來
• 或把新文章先給追蹤者（作者的特徵）或是根據「文章內容 embedding 」快速算要不要推 – 雖然他們在第一關第二關都可以被計算丟入模型，所以不見得要保障，不過少了一些詳細的特徵

這種保障名額，跟特徵無關的，可以去記錄曝光多少次，被互動多少次，逐漸去計算還有沒有救 (bandit)，還需要佔保障名額嗎 – 例如曝光 100 次互動 0，可能沒有情境的話就不受歡迎，之後只靠個人化用特徵算分數的方式

有了特徵以後的算法 #

第一關：用算比較快的特徵 + 能事先算的特徵 + 加上探索文章（上面的 Explore and exploit），拿出幾千篇候選文章

第二關：我們不確定這些特徵哪個重要，所以一個方式是把這些特徵餵給 regression model, 從單純 linear regression 到複雜 NN 都可能，最後輸出一個值

Twitter 做得更細膩，他們分多個情境，每個情境都預測出一個機率，再用不知道是人調的還是機器學的權重加總起來變一個分數

調教參數 #

有些演算法裡面有參數可調整（例如多少 view 算夯？ranking model 裡面的 weight 是多少），調配參數的其中一種方法是：讓機器用學的

藉由「過去」一段時間當作訓練資料，「過去的未來」跳過/沒跳過哪些文章當答案去訓練。

線下學的缺點是根據過去的資料，如果某篇文章在過去不被重視甚至沒被挑選，我們不大清楚如果重視他了以後是好是壞，沒有標準答案

實際讓一部分的使用者看到新的演算法參數的推薦是一個方式，例如 A/B test 評估現行的方法跟改動過的方法哪一個目標 (objective metrics) 有顯著的變好

成本跟速度考量 #

不同資料規模有不同的考量。可能需要有一些思考讓營運成本變低，或是使用者體驗變好

減少計算 #

能少算的東西就少算。每次算都一樣的東西就算一次。

服務有分線下算的，跟使用者進來線上算的。線下算的可以自己控制頻率 + 分等級 + 分地區/語言 …

• Offline calculation: Feature, embedding, …
• Online: feature lookup / cache + score calculation

例如，假設契合度(讀者, 文章)其中一個要素是文章的種類 f_種類(文章) ，這個分類誰來看都不會變，可以線下算而且算一次就好，放在資料庫的一欄。 當線上某個使用者開啟 Threads app，計算契合度公式需要文章種類時，查了就好

利用多階段的演算法也可以減少計算，有點像人資看履歷一樣

• 先用簡單便宜的演算法篩出可能有興趣的文章，再用比較複雜一點的再篩…，剩下的文章數能負荷以後，最後排序的演算法可能是計算量最高的
• 讀者 一次能看的文章相對於 Threads 上所有的文章如滄海ㄧ粟，只要「有推薦出來的」precision 夠，讀者 就開心（當然對於 作者 來說，如果自己的文章一直沒被 recall 就會很傷心）

數值的計算上，有沒有辦法多利用 reduce 或 addible 的值，而不用整個重新算（例如瀏覽數只要 +1 +1 就好。或者是模型參數是根據有更新的資料去調整，而不是每次有更新就重新訓練）

分等級 #

• 線上演算法複雜度的取捨 (特別是 cold start)：例如
  • 對於剛加入、沒信號的 讀者 用比較簡單只看 f(文章) 的推薦演算法
  • 對於幾分鐘的新文章，如果 user-item matrix 來不及算出文章的 embedding，先靠「文章的 作者 的特徵」或「文章內容本身的 (sentence) embedding 」
  • 對於剛加入的 作者 的第一篇，用「explore and exploit」或「文章內容本身的 (sentence) embedding 」
  • 這樣讓線下 model training (which 可能可以比較提供精準的推薦) 不用太頻繁
• 在儲存上分成新文章 (e.g. 一個禮拜內) 跟舊文章，讓需要推薦的文章池子不會成長過大
• 線上計算時，主力在計算相同地區/語言的文章 + 用簡單演算法隨便拿不同地區/語言的
• 有些互動上的數值也分新的與舊的。這同時跟品質與運算量有關。為了達到這個目的，資料庫的設計上對於互動要有時間，以及能夠輕易對於某個時間區段 aggregate (例如能相加的、每天能 reduce 成一個值 + 當天即時的數值)

減少精細度 #

把使用者分群 (clustering) ；推薦文章的時候是考慮「這一群人平均來說會不會喜歡」

• 例如 100M 的使用者，如果分成 100 人一組，那就只剩 1M 的「族群」去計算推薦
• 這對於儲存量 (space) 可能會有幫助
• 在第一關拿出候選文章也能很快速。例如 40% 只從有追蹤的 作者 的文章找，40% 只從同族群的文章找，就有 80% 的候選文章是從分母很小的文章中找出來（或者可以說第 0 關吧）

然而，這個有額外的工夫

• 每個使用者要運算歸類成某一群
• 隨著時間變化，怎麼調整每個使用者的族群（例如族群比較久才變一次嗎？單個使用者屬於哪個族群可以比較常變嗎？）