はじめに

Federated Learningに興味があり色々確認していたのですが、決定木ベースのモデルはないのかと思うようになりました。

探してみると以下の論文が出てきたので、読みました。

メモとしてここで簡単にまとめます。

arxiv.org

はじめに
概要
イントロ
事前知識
設定
- 環境の設定
- FLの設定
Vertical FederBoost
Horizontal FederBoost
実装と実験
- 有用性の検証
- 効率性の確認
  - LAN設定の場合の結果
  - WAN設定の場合の結果

概要

Federated Learningは、トレーニングデータをローカルのみに保持した状態でネットワーク全体のグローバルモデルを取得することができる
FLには大きく二つの問題がある
- 垂直に分割されたデータを処理できない
- 決定木ベースのアルゴリズムは利用できない
勾配ブースティング決定木(GBDT)によるFL：FederBoostを提案
三つのデータセットで集約データによる学習と同等レベルのAUCを達成

イントロ

Federated Learning(連合学習)は、複数の参加者が観測したデータをやり取りすることなく、全体の情報を利用した学習モデル(グローバルモデル)を得るフレームワーク
大きく二種類
- 参加者のデータが同じ特徴量保持するが、ローカルごとの参加者が異なるHorizontally FL
- 参加者は共通だが、保持する特徴量がローカルごとに異なるVertical FL

主な貢献は以下 - GBDT Federated Learning フレームワーク：FederBoostを提案

水平方向のFederBoostではバケットを分散して構築する新しい方法を提案
FederBoostの有用性を3つの公開されたデータセットで検証
プールされた全データによる学習と同程度のAUCが得られた
FederBoostの完全な実装を提供し最大32ノードのクラスタに展開し、1つのGBDTモデルは、WAN環境下でも30分以内で学習可能

事前知識

GBDT

Gradient boosting decision tree(GBDT)は決定技 $f_t(x)$ のアンサンブルモデルである。

推定値 $\hat y$ は以下のように表現される。

f:id:saltcooky:20220104155453p:plain:w120

GBDTは各決定木における1次勾配 $g_i$ と2次勾配 $h_i$ を用いて、決定木の分割を行なっていく。

f:id:saltcooky:20220104155555p:plain:w250

以下の評価関数を最大にするような分割を探索していく。

f:id:saltcooky:20220104155726p:plain:w460

$\lambda$ はハイパーパラメータ， $I_L$ は左の子ノードに分割されたサンプル， $I_R$ は右の子ノードに分割されたサンプルを表す。

なお、全体サンプル $I$ はソートされている。

ほとんどのGBDTフレームワークでは、学習プロセスを速くするために、各特徴の勾配の統計量を要約し勾配ヒストグラム $G_i$ , $H_i$ で構築する動作を加えている。

f:id:saltcooky:20220104160643p:plain:w480

学習アルゴリズムの流れは以下のようになっている。

f:id:saltcooky:20220103202530p:plain:w500

Federated learning

horizontal FLは2017年にGoogleが提案されたものが代表的。

中央(パラメータ)サーバと参加者の二者が存在する。

最初に中央サーバはランダムな値でモデルを初期化し、すべての参加者 $P_s$ に送信する。

各 $P_s$ は受信したモデルを用いそれぞれで学習する。

その際に生成された勾配をパラメータサーバに送信し、中央サーバは受信した勾配を集計、グローバルモデルを更新することができる。

Secure aggregation

水平FLにおける局所勾配を保護した形で集計するプロトコルが提案されている

参加者の局所勾配を保護するためにペア加法的マスキングを使用し，マスキングされた入力をサーバに集約させる。

共有されたシード値を用いた擬似乱数生成器(PRG)を利用しマスクされ、乱数による影響は集計によりキャンセルされる。

Differential privacy

差分プライバシーは、各個人のデータを保護しながら統計的分析を可能する手法/分野。

各個人/ノードのデータに対して乱数により発生させたノイズを負荷することで可能になる。

差分プライバシーのプライバシー保護度合い等を定義した考え方として、 $( \epsilon, \delta )$ Differential privacyが挙げられる。

f:id:saltcooky:20220108021355p:plain:w360

設定

環境の設定

各参加者が共同でモデルを学習したい
2人の参加者の間には安全なチャンネルが存在
参加者は良いモデルを訓練するインセンティブがある
プロトコルの途中で脱落することはない

FLの設定

従来の分散型MLに近い効率、すなわち暗号処理回数を最小にする
精度は集中型学習に近いものであるべき
プライバシー保護レベルはローカル学習（各参加者が自分のローカルデータのみで学習）に近いものであるべきそのためには、転送されるデータを暗号化技術や差分プライバシーで保護する必要がある。

Vertical FederBoost

学習

決定木を構築するための重要なステップは、特徴量に対するサンプルの最適な分割を見つけることであり、これにはサンプルの順序と1次と2次の勾配 $g_is$ , $h_is$ だけが必要。

各参加者に特徴量のサンプルを並べ替えてもらい、その順番を $P_l$ に伝えることができれば全体の学習を完了することができる。

参加者はサンプルの値は必要なく、順番を伝えるだけで良いので、情報量が格段に少なくなる。

一方で、順序情報からの情報漏洩する可能性が残っている。

例えば特徴量が"給与"とすると、 $P_l$ はこのような情報を得ることができる。

アリスの給料 ≦ ボブの給料 ≦ シャーリィの給料

もし $P_l$ がアリスの給料とシャーリィの給料を知っていれば、ボブの給料（または少なくともその範囲）を推論することができてしまう。

このような情報漏洩を防ぐために、サンプルをバケットに入れる方法と、差分プライバシーノイズを加える方法の2つを組み合わせる。

バスケット化

サンプルの特徴量の値をソートし、サンプルを分割して $q$ 個のバケットに分ける
$P_l$ はバケットの順番だけを知っており、バケット内のサンプルの順番は何も知らない

差分プライバシーノイズ付加

元々 $i$ 番目のバスケットに割り当てられていたサンプルに対して
- 確率 $p=\frac{e^\epsilon}{e^\epsilon+q-1}$ で $i$ 番目のバスケットに入れる
- 確率 $p=\frac{1}{e^\epsilon+q-1}$ で $i$ 番目のそれ以外のバスケットに入れる
この方式は任意の2つのサンプル $x1, x2$ に対して以下の $\epsilon$ -LDPを満たすことになる

f:id:saltcooky:20220104181017p:plain:w400

実験結果（セクション6.1参照）はε=2、q=16とした場合、垂直方向の FederBoost は DP を用いない場合と非常に近い値を示した。

学習の全体像

f:id:saltcooky:20220104181747p:plain:w600

Vertical FBの学習アルゴリズムは以下のようになっている。

f:id:saltcooky:20220104165813p:plain:w500

1-7行目: 参加者は、まずローカルにバケットを構築し、各バケットのサンプルIDを $P_l$ に送信する
8-24行目: Plは集中型GBDTと全く同じ方法で学習アルゴリズムを実行
- 10-12行目：各サンプルに対して1次および2次の勾配を計算
- 10-12行目：木の各ノードに対して，各特徴の最適な分割を求める
- 14-20行目：各特徴の勾配ヒストグラムを構築
  - 16行目：各バケット内のサンプルIDを更新する必要があることに注意
  - 19行目：親ノードを構築した際にサンプルが分割
- 21行目：最適な特徴量が見つかったら、 $P_l$ はその特徴量を持つ参加者 $P_j$ に、サンプルがどのように分割するかを送信. そして、Pjはこのノードの閾値を計算し、将来の予測に役立てる

推論

予測フェーズでは、 $T$ 個の決定木すべてに $x$ を入力し予測値を出力する。

このために分割の閾値と特徴量を比較し、どのノードに進むか判断する必要がある。

具体的には

ルートから始めて $P_l$ は判断に必要な特徴を保持している $P_i$ に連絡
$P_i$ はその特徴値の $x$ と閾値を比較し、 $P_l$ に伝える
その結果に基づいて $P_l$ はどの分岐に進むかを決定する
$P_l$ は T本の木の葉ノードの重みを計算し最終的な予測値を出力する

プライバシー保護について

Horizontal FederBoost

学習の全体像は以下の図のようになっている。

f:id:saltcooky:20220105020528p:plain

各サンプル $x_i$ は全ての特徴量とラベルを持つ。

参加者が各ローカルでモデルを学習し、ローカルで学習したモデルを中央サーバで集計し、グローバルな共同モデルを生成する。

この考え方はGoogleのFLフレームワークに一致する。

また、参加者の各ローカルで決定木を学習しバギングするランダムフォレストも一致する。

しかし、ランダムフォレストを学習するためには、各参加者が全サンプルの63.2%以上を保有している必要があり、これはFLの設定と矛盾している。

課題が2つ

サンプルは参加者で分配されるため、一人の参加者がどの特徴量のサンプルの順番を知ることはできない
各参加者はラベルの一部しか持っていないため、各バケットのヒストグラムを情報漏洩なく計算することが困難

分散バケット構築

従来の分散型GBDTにおける分散バケット構築の最も一般的な方法は、分位点スケッチと呼ばれ、各参加者が自分のローカルデータの表現を送信して、各特徴の分布を近似することが要求される。

しかし、この方法では、参加者のローカルデータに関する情報がリークしていまう。

そこで、プライバシーを保護するため分散バケット構築法を提案。

基本的な考え方は、ある特徴量のn個のサンプル値をq個のバケットに分割するカットポイント（分位数）を求め、参加者はその分位数に基づき対応するバケットにサンプルを入れる。

$q-1$ のすべての分位数を求める擬似コードをプロトコール 3 に示す。

f:id:saltcooky:20220105015155p:plain:w500

2行目： $P_l$ は[tex:Q{min}]と[tex:Q{max}]の初期値として、特徴量の最小値と最大値で代入
5行目：[tex:Q{min}]と[tex:Q{max}]の平均値で $Q_1$ を初期化
6-8行目： $P_i$ は $Q_j$ より小さいサンプル $x$ の総数 $n_0$ を求める。
9行目：各ローカルの該当件数からセキュアな集計を行う
10-14行目： $n/q$ との大小から[tex:Q{min}]と[tex:Q{max}]を更新
16-18行目： $Q_j$ より小さいサンプルを除外

学習

水平FederBoostではバケット構築も一度だけ行う。

参加者はデータが変更されない限り、モデルを微調整するためにトレーニングフェーズを複数回実行する。

全ての分位数を求めた後、各参加者はローカルで自分のサンプルIDを角バケットに入れることができ、 $P_l$ はそのバケットの情報を集めて集計することができる。

一方で各参加者は全てのラベルを保持していないため、vertical FederBoostのように決定木を学習させることはしない。

その擬似コードをプロトコル4に示す

f:id:saltcooky:20220106004534p:plain:w500

1行目から9行目まではセットアップの段階。

1-3行目：Quantile Lookup(プロトコル3)でバスケットの取得
8-9 行目：各 $P_i$ はサンプルID のバケットを $P_l$ に送るのではなく，ローカルに各サンプルの $g_i$ と $h_i$ を計算する
18 行目：各バケットの $G _ { j,k } ^i$ と $H _ {j,k } ^i$ を計算
22行目：secure aggrigation(プロトコル5)により各バケットの $G _j ^i$ と $H _j ^i$ を計算
22行目：各参加者から集められた $G _q ^i$ と $H _q ^i$ から評価値 $score_i$ と分割位置 $split_i$ を各バケットのを計算
24-25行目：各参加者に $score_i$ と分割位置 $split_i$ を送信
27 行目：形成された木のノードの重みにより推定値 $\hat y_n$ を修正する