---
# System prepended metadata

title: Federated Online Learning to Rank with Evolution Strategies (2023/06/19 更新)

---

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

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

![](https://hackmd.io/_uploads/SJidoijvn.png =50%x)
:::
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 (基因演算法) : 
![](https://hackmd.io/_uploads/HyL_EOKv3.png)

Evolution strategies (進化策略) :
![](https://hackmd.io/_uploads/HJdzr91Oh.png)
:::

#### 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)，我們需要考慮的是一個群體
![](https://hackmd.io/_uploads/rysRiHOvh.png)

- 這裡梯度的求法類似於 REINFORCE 演算法
![](https://hackmd.io/_uploads/SkY6NU4w3.png)

- 導入高斯分布(Gasuuian Distribution)
![](https://hackmd.io/_uploads/S12dhr_w2.png)

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

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

## Privacy Analysis
![](https://hackmd.io/_uploads/SJIzqYaD2.png)

![](https://hackmd.io/_uploads/HJMyILNPn.png )

![](https://hackmd.io/_uploads/rksV19iP3.png)

至少可以到 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 的，因為太後面幾乎不會用到

![](https://hackmd.io/_uploads/ByDxDYVU3.png =50%x)

#### 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
:::
![](https://hackmd.io/_uploads/H1s-bfsUh.png =50%x)

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

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

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

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

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

MQ2007
![](https://hackmd.io/_uploads/Bk120Zs83.png)

WQ2008
![](https://hackmd.io/_uploads/SyrCR-oLh.png)

Result
![](https://hackmd.io/_uploads/B1x9vYV8n.png =50%x)

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