如果我是 Threads 工程師,要怎麼寫推薦演算法
目錄
我不是 Threads 工程師,但在以億為等級的系統做推薦,只是想想也好玩!
單純從技術上思考,做一個推薦系統可能的思路、手法、考量…。這是個人的思想練習與研究練習,幻想文,不一定是真實狀況
問題 #
目標 #
先有目標 (objective metrics) 。以 Threads 為例 – 我隨便瞎說 – 使用者文章瀏覽時間。之後的演算法訓練都以目標前進
*關於「目標」的碎碎念,有興趣再打開*
題外話,不同產品的目標也可能是
- engagement 類:點擊、喜歡、轉發…
- 比較打高空的、或比較深的。像是 App 停留時間、廣告或電商的轉換率/購買率之類的
單純的 metrics 可能比較好計算,在改進的途中相對比較容易分析
有些偏商業目標的 metrics 比較複雜:內在外在變因太多,且中途可能有好幾個 metrics 去引導 (funnel)。例如電商要讓一個產品被購買,至少要經過 使用者看到 (view) 去點 (click) 去買 (convert),演算法要改進比較困難
最實際但也最難行動的目標叫「公司要賺越多錢」;變因越多的 metrics 演算法越難有信心地調,但越單純的 metrics 也可能不實際 或走火入魔 overfit
資料 #
接下來看手上有哪些資料、資料規模、現有資料能達到什麼地步、收集新資料的用處 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
![Random walk on vertex to make sentences and use word2vec](./random-walk-to-word2vec.webp)
無論是 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 上面的值
![matrix factorization to get embedding](./matrix-factorization.webp)
這間接算出讀者跟文章的 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 關吧)
然而,這個有額外的工夫
- 每個使用者要運算歸類成某一群
- 隨著時間變化,怎麼調整每個使用者的族群(例如族群比較久才變一次嗎?單個使用者屬於哪個族群可以比較常變嗎?)