# Federated Online Learning to Rank with Evolution Strategies (2023/06/21 更新)

## Introduction
1. 移動裝置是現代主要接收網路資訊的工具，因此，多數的排名模型 (ranking model) 會用來自行動裝置的資料進行訓練
:::success
Learning To Rank (LTR) :
用於訊息檢索，會根據相關性進行排序，並為查詢項目提供搜尋結果排名。
主要可以分為以下 3 類 : PointWise(單點法) 、 PairWise(配對法) 、 ListWise(列表法)

:::
2. 由於不希望資料離開使用者的裝置，且想要保護隱私並限制傳輸頻寬，於是 Federated Learning 便被提了出來
3. Federated Online Learning to Rank (FOLtR) 可用於解決 Online Learning to Rank 問題，並且可與私有訊息檢索 (Private Information Retrieval) 做結合以達到提供差分隱私的效果
:::success
Online Learning (在線學習) : 資料會按順序獲取，適合用於須連續接收資料並能適應快速變化的機器學習系統，EX : 天氣預測、股價分析
Offline Learning (離線學習) : 需要蒐集資料並做批量學習，相較在線學習在時間和資源上消耗較多，EX : 圖像分類
:::
4. Online learning 可能面臨挑戰
1. noisy online feedback
2. non-continuous quality metrics
3. explore the space of potential rankers
5. 本篇提出了 Federated Online Learning to Rank - Evolution Strategies (FOLtR-ES) ，將 FOLtR 與進化策略 (Evolution Strategies) 結合，可降低溝通時傳輸大小的影響，同時達到降低溝通花費與保證隱私的目的
6. 貢獻
1. 提出了將 FOLtR 結合進化策略的 FOLtR-ES
2. 證明了此方法有確實做到差分隱私
3. 透過實驗觀察此方法對於優化效能的權衡 (trade-offs)
:::success
Differential Privacy (差分隱私) :
加入噪音隱藏敏感屬性，模糊使用者之間的差別
:::

## Background
#### 1. Online learning to rank
- 早期，會根據點擊回饋 (Click Feedback)，並用 RankingSVM 來做到在線學習 (Online Learning) 的排名訓練
:::success
RankingSVM :
為一種 Pairwise 的排序演算法，透過相關性，訓練一個 SVM (支援向量機) 做分類
:::
- 現有的在線學習排名訓練往往需要集中處理，EX : Multileave Gradient Descent會蒐集 interleaving / multileaving feedback
- 本篇提出的 FOLtR-ES 將基於強化學習中的進化策略 (Evolution Strategies)，除了能提供在線學習外還能保護客戶隱私
:::success
Genetic Algorithm (基因演算法) :

Evolution strategies (進化策略) :
:::

#### 2. Federated and privacy-aware learning
- 最早的 FL 演算法為 Google 所提出的 Federated Averaging (FedAvg)
- 將排名問題結合在線以及聯邦式學習所面臨的兩大挑戰
- bandit feedback & the need for exploration
- non-continuous optimized measures of quality
- FOLtR-ES 做到了客戶層級 (client-level) 的差分隱私，也就是說隱私資料不會離開客戶的裝置

## Federated online learning to rank with evolution strategies

這裡將 FOLtR-ES 演算法分成 3 個部分來討論

#### 1. Optimization Scenario
- 這裡的想法與 Federated SGD 時一樣，排名模型會在客戶端進行訓練，以保障隱私
- 每輪選 N 個客戶參與，每個客戶會在本地端進行 B 次互動 (interaction)，在將互動完的梯度會被傳回並且聚合，以產生出新的模型
:::success
Interaction :
這裡的定義為 "A single event of submitting a query and interacting with its results"
:::

#### 2. Getting a Gradient Estimate
- 根據進化策略(Evolution Strategies)，我們需要考慮的是一個群體

- 這裡梯度的求法類似於 REINFORCE 演算法

- 導入高斯分布(Gasuuian Distribution)

- 在進化策略 (ES) 中，經常使用隨機種子 (random seed) 做溝通

#### 3. Privatization procedure
- 作法 : 在傳輸的值中加入噪音，EX : Laplace noise

## Privacy Analysis



至少可以到 log[p(n-1)/(1-p)] 的差分隱私

## Evaluation Setup
目標 :
1. 分析不同演算法對效能的 trade-off
2. 用 FOLtR-ES 訓練高效能 Ranker

:::success
本篇使用公開的離線排名資料庫 (rank dataset) 模擬使用者行為
:::

#### 1. Simulating users
- 每個客戶從資料集中隨機且均勻的採樣 B 個 query
- 這裡模擬 2000 個客戶

#### 2. Simulating user clicks
- 用 Cascade Click Model (CCM) 模擬使用者
- 只看前 10 的，因為太後面幾乎不會用到


#### 3. Models
- 2 種模型
1. 線性模型(沒有 bias)
2. 神經網路(有一層含有 10 個神經元的隱藏層)

#### 4. Baselines
- 2 種基準
1. MSE(一個線性回歸模型，可由 `scikit-learn` 實作)
- 用以預測文檔與查詢(query)的關聯性
3. RankingSVM

#### 5. Datasets
- 2 個資料集
1. MQ2007
- 1692 unique queries, 69623 relevance labels
2. MQ2008
- 784 unique queries, 15211 relevance labels
:::success
MQ2007 / MQ2008 :
由人類專家所提供，每個文檔的相關標籤 (relevance labels) 可分為 "相關"、"部分相關"、"不相關"
:::
#### 6. Quality Metric
- MaxRR

#### 7. Optimization
- Optimizer : Adam

## Results and Discussion
這裡分成 3 個部分討論

#### 1. How tight is the estimate
- 這裡採取用模擬的方式模擬使用者點擊 (click)
- 相關標籤 (relevance labels) (依相關程度來分) : {0 : Navigational, 1 : Informational, 2 : Perfect}
:::success
Relevance Labels :
常見的分法有 perfect 、 excellent 、 good 、 fair 、 bad
EX : query = “Facebook” ， FB 的官網是 perfect ，只提到 FB 這個詞叫 fair ，和 FB 毫不相關就是 bad
:::

- 從實驗結果可知，當使用者的行為接近 Informational 模型時，在隱私上能得到較好的保障

#### 2. Hyperparameter analysis
- Antithetic variates (對立變量) :
- 為了要分析對立變量的影響，所以這裡訓練了兩次 linear ranker (使用 variance reduction 和不使用 variance reduction)
- 可以觀察到對立變量確實能有效的加快優化速度，尤其是在 Informational 模型中
- 因此，接下來的實驗都會用到對立變量

- Feedback size sensitivity (回饋大小靈敏度) :
- 這裡分析互動次數 B 對優化的影響 (B = {2, 4, 8, 16, 32} )
- 較大的 B ( B = 16, 32 ) 與較小的 B ( B = 2, 4, 8 ) 相比優化速度較慢
- 為了簡單起見，之後的實驗會將 B 設為 4

- Privatization vs optimization speed trade-off (隱私與優化速度的權衡) :
- 由於加入了噪音， 所以會使優化速度下降
- 這裡用一個隱私參數 p 來分析 (p = {0.15, 0.25, 0.5, 1.0} )
- 可以觀察到 p 越高表現越好，特別的是當 p = 0.5 和 p = 1.0 時差異並不大

#### 3. Ranking quality
- 想要了解 FOLtR-ES 的排名表現
- 這裡用了對立變量，且 B = 4 ， p = 0.9
- 會和線性模型以及兩層的神經網路去比較
- 相較於 Navigational 模型和 Perfect 模型，Informational 模型能看出較大的差異

MQ2007

WQ2008

Result

## Conclusions
- 本篇論文透過使用者的即時回饋訓練一個排名器 (ranker)，與伺服器溝通時只需 8 ~ 12 bytes ，且不會傳輸敏感資料
- 在 Navigation 模型上能讓隱私達到足夠緊 (tight)