はじめに
この記事では、MPCを用いて決定木を作成するSID3プロトコルについて解説します。SID3プロトコルは、決定木の学習アルゴリズムの一つであるID3をベースにして作られています。また、この記事で参照する原著論文は以下から確認できます。
“https://fc14.ifca.ai/papers/fc14_submission_103.pdf“
SID3プロトコルは、一般的なID3アルゴリズムと同様な手順で処理を行います。そこで、まずは一般的なID3アルゴリズムの概要を簡単に説明し、その後にSID3プロトコルについて紹介していきます。
語句の説明
まず、本記事で用いる語句及び記法の説明をします。
- クラス属性値：識別対象のクラスの値
- 属性値：クラス属性を判別するために使用される属性の値
- トランザクション：ユーザID毎にクラス属性値、属性値を持つデータ
- $Tau$ : 最初に入力された全てのトランザクションを表すビットベクトル
- $T$ : SID3プロトコルに入力された全てのトランザクションを表すビットベクトル
- $R$ : 使用することが可能な属性を表すビットベクトル
- $c_i$ : クラス属性の$i$ 番目のクラス属性値
- 例：クラス属性 = {購買する, 購買しない}の時、$c_1$ = 購買する $c_2$ = 購買しない
- $A_k$ : $k$ 番目の属性
- 例：$A_1$＝ 性別
- ただし、$A_0$ はクラス属性を表す
- $a_{k,j}$ : $k$ 番目の属性の$j$ 番目の属性値
- 例：$a_{1,2}$= 女性
- $S_{k,j}$ : $a_{k,j}$ を持つトランザクションのビットベクトル
- $S_{0,j}$ はクラス属性値$a_{0,j}$ をもつトランザクションのベクトルを表す。
以下の図は、各記号が意味することがわかりやすいように、全てのトランザクションを表にしたものです。
ID3アルゴリズム
ID3アルゴリズムは、決定木作成のためのアルゴリズムの一つです。基本的なアイディアは、「分類されるクラス属性値の偏りが大きくなるような属性を木のノードとする」という操作を繰り返すことです。
ID3アルゴリズムは、各ノードに割り振られたデータに対して再帰的にアルゴリズムを適用します。
具体的なアルゴリズムは以下です。
アルゴリズム
- ノード$a$ を作成して全データを$a$ に割り振る
- 終了条件チェック
- $a$ に割り振られているデータのクラス属性値が全て同じなら処理を終了する
- もしくは、木の高さが制限に達した場合も終了する
- ノード$a$ のデータのクラス属性値の散らばり度合いを計算する
- 属性値でデータを分けたときの散らばり度合いを計算する
- 3, 4の計算から最もクラス属性値の散らばり具合が小さいものを選択する
- 選択した属性でデータを分けたノードを作成し、データを割り振る
- 各ノードで操作2~6を繰り返す
最終的に全てのノードが終了条件を満たした時に、決定木の学習が終了します。
このようなID3アルゴリズムを、MPCで実行する方法を次に紹介していきます。
SID3プロトコル
ID3アルゴリズムをMPC実装する際の問題
ID3アルゴリズムをMPCで実装するには、1つの問題があります。それは、特定のクラスに分類されるトランザクションの数を数えるという操作が非常に難しいということです。
ID3アルゴリズムにおける操作3, 4では、散らばり度合いの計算にトランザクションの数を数える操作が必要になります。しかし、MPCではデータの値を秘匿化しているため、ある値をもつトランザクションを数え上げることが困難です。
アイディア
そこで、以下の3つのアイディアで解決します。
- ある属性の有無を0,1で表現するビットベクトルを用いる
- トランザクションの分割をビットベクトルで表現する
- ベクトル演算で集合に対する演算を表現する
ある属性値の有無を0,1で表現するビットベクトルを用いる
ある属性値$a_{k,j}$ を持つ場合は1、持たない場合は0 とするビットベクトル$S_{k,j}$ を用いて、トランザクションのデータを表現し直します。
すなわち、以下のように$S_{k,j}$ を定義します。
$$ S_{k,j} = [b_1, b_2, \cdots , b_N],\space \space b_i \in \{0,1\}
$$
ここで、$N$ は全てのトランザクション数を表し、$b_i$ は$i$ 番目のトランザクションが$a_{k,j}$ をもつ場合に$1$ 、持たない場合に$0$ とします。
トランザクションの分割状態をビットベクトルで表現する
トランザクションの分割状態を、ビットベクトル$T$ を用いて表現します。トランザクションが該当ノードに割り当てられている場合に1、割り当てられていない場合に0とします。
すなわち、以下のように$T$ を定義します。
$$ T=[b_1,b_2, \cdots, b_N] $$
ここで、先ほどと同様に$b_i$ はトランザクションが割り当てられている場合に$1$, 割り当てられていない場合に$0$ となります。例えば、SID3プロトコルに入力される初期状態では$T = [1,1, …,1]$ となります。
ベクトル演算で集合に対する演算を表現する
属性値$a_{k,j}$ を持つトランザクションの数え上げ
トランザクション集合に対して、ある属性値$a_{k,j}$ を持つ要素を数えあげる処理を、上記で定義したビットベクトル$S_{k,j}, T$ を用いることで効率よく計算することができます。
2つのビットベクトル同士で内積を計算すると、$T$ のうち$a_{k,j}$ を持つトランザクションの個数を得ることができます。
例えば、$T = [1, 0, 1, 1, 0], S_{k,j} = [1, 1, 0, 1, 1]$ の時に内積を計算すると、
$$ T\cdot S_{k,j} = [1, 0, 1, 1, 0]\cdot [1, 1, 0, 1, 1]=2 $$
となることから、該当するトランザクション数が2つであることを簡単に求めることができます。
クラス属性値$c_j$ をもつトランザクション集合の算出
トランザクション集合($T$)に対して、クラス属性値$c_j$ を持つ集合との共通集合($T \cap S_{0,j}$)を求める場合も、ビットベクトル$T, S_{0,j}$ を用いて効率良く求めることができます。
2つのビットベクトル同士の要素毎の乗算（アダマール積：$\star$）を行うことで共通集合を求めることができます。
例えば、$T = [1, 0, 1, 1, 0], S_{0,j} = [1, 1, 0, 0, 1]$ の時にアダマール積を計算すると、
$$ T\star S_{0,j} = [1, 0, 1, 1, 0]\star [1, 1, 0, 1, 1]=[1,0,0,1,0] $$
となることから、共通集合が$[1,0,0,1,0]$ であることを簡単に求めることができます。
プロトコル詳細
次に、実際のSID3プロトコルの処理について説明します。
以下が全体の流れを表す疑似コードです。再帰的にSID3関数が使用されている点に注意してください。また、前提条件として入力データである$T,S_{k,j}$ の値は秘密分散法を用いてシェアとして表現されています。
疑似コード解説
1 – 2行目
$T\cdot S_{0,i}$ によって、入力されたトランザクション集合$T$ に含まれる、クラス属性値$c_i$ を持つトランザクションの個数$s_i$ を計算しています。
3行目
全ての$s_i$ の中で最大の値を持つ$s_{i*}$ のインデックス$i*$ を取り出します。
4 – 5 行目
ここでは終了条件のチェックを行っています。
以下のいずれかの条件を満たす時、クラス値の推定結果$c_{i*}$ を出力して終了します。
- 属性の集合 $R = \varnothing$ のとき
- 分割に使用できる属性値がなくなった時に相当する
- 最初に入力されたトランザクションの大きさ$|T|$ と、現在入力されているトランザクションの大きさ$|T|$ の比が十分小さくなったとき($\epsilon$ 以下)
- 制限された木の高さに到達した時に相当する
- $s_{i*} = |T|$ のとき
- クラス属性値$c_{i*}$ を全ての$T$ が持っていた時に相当する
7 – 8行目
$T\star S_{0,i}$ によって、トランザクションを各クラス属性を持つものに分割しています。
例えば以下の場合、
- クラス属性 = {晴れ, 雨}
- $T=[1,1,0,1,1]$
- $S_{0,晴れ}=[1,1,1,0,1]$
- $S_{0,雨}=[0,0,1,1,0]$
$U_i$ はそれぞれ以下のように計算されます。
$U_{晴れ} = T \star S_{0,晴れ} = [1,1,0,1,1] \star [1, 1, 1, 0, 1] = [1,1,0,0,1]$
$U_{雨} = T \star S_{0,雨} = [1,1,0,1,1] \star [0,0,1,1,0] = [0,0,0,1,0]$
9 – 15 行目
ここから各属性値毎のクラス属性の散らばり具合を計算していきます。SID3プロトコルでは、散らばり具合の算出にジニ係数を使用します。
まずは、ジニ係数の算出に必要な値$x_{i,j}, y_j$ を計算します。
$x_{i,j}$ は、 $U_i\cdot S_{k,j}$ により属性値$a_{k,j}$ を持つトランザクションのうち、クラス属性値$c_i$ に分類されるものの数に相当します。
$y_{j}$ は属性値$a_{k,j}$ を持つトランザクションの総数に相当しますが、以下に説明する近似版ジニ係数の計算の都合上必要な値$\alpha$ の乗算と1の加算を行います。
SID3プロトコルでは、以下に示すような厳密なジニ係数の定義とは少し異なる、近似版ジニ係数を用います。理由は、元のジニ係数の式において、分母が空の場合分けを行うには空となる属性を明らかにする必要性があり、計算コストが増加するためです。
元のジニ係数
$$ G_k = \sum_{j \: s.t. \: | T \cap S_{k.j}| \neq 0} \dfrac {\sum_{i} | T \cap S_{0, i} \cap S_{k, j} |} {| T \cap S_{k, j}|} $$
近似版ジニ係数
$$ \tilde{G_k} = \sum_j \dfrac{\sum_i x_{ij}^2}{y_j} $$
$y_j$ は1 を加算することによって分母が0 になることを防いでいます。$\alpha$ はハイパーパラメタであり$\alpha = 8$ のときに、最も元のジニ係数の値に近くなると原論文では示されています。
さらに、計算を簡単にするためにこれを式変形すると以下になります。
$$ \tilde{G_k} = \dfrac{\sum_j (\sum_i x^2_{ij})\prod_{l \neq j}y_l} {\prod_l y_l} $$
ただし、$\prod_{l\neq j} y_l$ は最終的に割ることが可能なため、計算する必要性がありません。よって、計算する式は以下となります。
$$ \tilde{G_k} = \dfrac{\sum_j (\sum_i x_{ij}^2)} {y_j} $$
このとき、計算の要素の$x_{ij} \, y_j$ は、単なる四則演算で計算可能であることから、MPCを用いて計算することが容易になります。
16 – 17 行目
最大のジニ係数をもつものを $\tilde{G_{k*}}$ とし、そのインデックス$k*$ をビットベクトルとして取得します。例えば、3番目の属性に決まった時を考えると$k* = [0,0,1,0,…,0]$ となります。
次に、$k*$ の属性$A_{k*}$ を$R$ から取り除きます。ここでは単に$R$ から$k*$ を要素毎の減算をすることで計算できます。
最後に、トランザクション$T$ を$a_{k*,j}$ を持つものと持たないもので分割を行い、分割後の$T$ と属性$R$ を関数SID3の引数として入力します。
以上がSID3プロトコルの処理の説明でした。上記のプロトコルを実行することで、MPC上で入力データの値を明らかにすることなく、安全に決定木の作成が可能です。
まとめ
- データをビットベクトルとすることで様々な操作を簡単にした
- 特定のトランザクションの数え上げ
- 特定のトランザクション集合の抽出
- 比較演算と基本的な四則演算の組み合わせで決定木の作成が可能となる
