DEIM Forum 2017 A4-5

P2P ネットワーク上のデータに対する偏りのない機械学習手法
高橋 良希†

首藤 一幸†† 東京工業大学〒 152–8552 東京都目黒区大岡山 2-12-1
あらまし 非構造化 P2P ネットワークにおいて，プライバシなどの理由から各ノードの保有するデータを移動させずに，ネットワーク上に分散されたデータを学習する手法が研究されている．このとき，データを移動させる代わりに学習モデルを移動させることで学習を進める方法があるが，モデルが単純にネットワーク上をランダムウォークする
場合，入次数の大きなノードのデータを多く学習してしまうような偏りが生じる．既存手法では，このような偏りを隣接ノードリストを繰り返し更新することで削減する手法が存在するが，隣接ノードを繰り返し更新することはプラ
イベート IP アドレスを使用する端末に対して容易に通信を開始できないような問題を生じる．本研究では，隣接ノードリストを更新せずとも，選択確率を用いることで，ネットワーク上のデータをバランスよく学習する手法を提案する．また，この手法によって隣接ノードリストの更新を行わずとも，既存手法と同等の精度を達成することをシミュレーションを用いた実験で示す．
キーワード

P2P, オンライン機械学習, ゴシッププロトコル， Metropolis-Hastings random walk

1. は じ め に択の手法における問題点を提起する（第 2 章）．次にそれを解決するためのノード選択の手法を提案し（第 3 章），提案した

機械学習はメールのスパムフィルタリングや通販サイトの推手法と既存手法，ナイーブな手法をそれぞれ実験し結果を考察

薦システムなど，生活の様々な面で活用されている．これらのする（第 4 章）．次に本研究の関連研究を述べ（第 5 章）最後

学習に必要なデータは，通常サーバ上に集中して管理されるが，に本研究のまとめと今後の課題を述べる（第 6 章）．

P2P のような非集中型のシステムの場合，多くのデータは端末となるピアに蓄積される．端末として PC やスマートフォン，2. 準

備

タブレットなどを想定すると，保有するデータのうちユーザのネットワーク上に分散された移動できないデータに機械学習

プロフィール情報や検索履歴，センサー情報などの個人情報にを適用する場合，中心となるノードにデータを集めて一度にま関わるデータはプライバシの問題からピア間で通信することがとめて処理することができないため，各訓練データをオンラできない．

イン学習によって逐次的に学習する．オンライン学習を用いてこのとき，データを移動させる代わりに学習モデルを移動さP2P ネットワーク上のデータを学習する gossip learning [7] でせ，モデルがノードを訪問するたびにそのノードの保有するは，隣接ノードリストの更新を用いたネットワーク上の一様ラデータを逐次的に学習することで，ネットワーク上のデータをンダムなピアサンプリングと，ゴシッププロトコルを用いたモ学習することができるが，非構造化ネットワークでは入次数のデル送信，オンライン学習によるモデル更新を繰り返すことで，大きなノードのデータを多く学習してしまうように，学習デー学習モデルがネットワーク上を移動しながら学習が進む．

タサンプルに偏りが生じる．gossip learning [7] では，各ノー

本章では，解決すべき問題を明確に提示するために，まずオドが隣接ノードリストを繰り返し更新することによって，グランライン学習と gossip learning [7] を紹介し，次に P2P 上の一フ構造によるサンプルデータへの影響を低減している．これに様ランダムなピアサンプリング手法である Newscast [8] を紹介

より学習データのサンプル列が一様に近づくように収束していする．最後に解決すべき問題を提示する．

る．しかし，既存研究における隣接ノードリストの更新は，プライベート IP アドレスを持つノードに対して容易に通信を開始できないような，NAT 越えの問題を発生させる．

また，本論文では分類問題を例に話を進めるが，他のオンライン学習においても適用可能である．

2. 1 分類問題におけるオンライン学習

我々は隣接ノードリストを更新せずとも，ノード間に選択確分類の目的はある入力ベクトル x に対し，いくつかの離散ク率を設定することで学習データサンプル列の偏りを低減する手ラスのうちのいずれかを割り当てることである．訓練データが法を提案する．提案手法の選択確率は，Metropolis-Hastings与えられたとき，パラメータが w のモデルによる i 番目の入力random walk (MHRW) [10] に倣った確率を設定する．これにベクトル xi に対する予測と，実際のクラスラベルとの間に誤差より入次数の大きなノードは選択されにくく，入次数の小さなを観測できる．モデルによる i 番目のデータに対する誤差関数

ノードは選択されやすい特性を享受する．

を Ei (w) とすると，n 個のデータ全体の誤差関数の一つとして本論文では，まず準備としてオンライン学習アルゴリズムと，既存研究であるモデル送信による学習手法を紹介し，ノード選

Alogorithm 1 に gossip learning [7] の擬似コードを載せる．

Algorithm 1 Gossip Learning Framework
1: currentModel ← initModel()各ノードは，まずモデルパラメータを適当な値で初期化し，次2: loopに ∆ で示されるインターバルでモデルの送信を行う．モデルの3:wait(∆)4:p ← selectPeer()5:

send currentModel to p

送信先は selectPeer によって隣接ノードの中から一様ランダムに選ばれるが，Newscast [8] と呼ばれるピアサンプリング手法を用い，隣接ノードリストは各サイクルごとに繰り返しシャッ

6: end loop

フルされる．モデルを受け取ったノードは，updateModel に

7: procedure OnReceiveModel(m)8:m.updateModel(x, y)

よって自身の保有するデータに基づいたオンライン学習を用い

9:

currentModel ← mてモデルパラメータを更新する．

Newscast [8] では，隣接ノードのリストを繰り返し更新する

10: end procedure

ことにより，一様ランダムなノードのサンプル列を得る．この

E=n∑手法では，各ノードは隣接ノードのリストをビュー (view) と呼Ei (w)(1)i=1ばれる構造体で管理し，一定のサイクルごとにプッシュ (push)とプル (pull) によってビューを繰り返し交換する．プッシュでを定義できる．学習の目的は訓練データに対する誤差関数を減は，自身の持つビューを自身のアドレスとともにランダムな隣少させることによって，未知のデータをうまく分類できるよう接ノードに送信する．これを受け取ったノードは，受け取ったにすることである．データ全体の誤差を減少させる最適化手法

ノードアドレスのリストと自身のビューを適切にマージして，の一つである勾配降下法では，誤差関数を減少させるような τ

これを新しいビューとして更新する．プルでは，ランダムな隣回目のパラメータの更新を接ノードに，そのノードが保有するビューを要求する．相手かw(τ +1) = w(τ ) − ητ ∇E(2)らビューの返信があれば，これと自身のビューをマージし，新しいビューとして更新する．各サイクルおきにこの操作を十分に従って行う．一方，一つのデータの誤差に対して逐次的にパな回数行うことで，隣接ノードからランダムに選択するノードラメータを更新するオンライン学習手法の一つである確率的勾はネットワーク上から独立かつ一様ランダムに選択されたサン配降下法では，誤差関数が（1）のように各データ点の誤差のプル列に収束する．

和で表される場合，パラメータ w を

しかしこの手法には問題点があり，Newscast [8] によって新w(τ +1) = w(τ ) + ητ ∇Ei(3)しく参照されたノードがプライベート IP アドレスを用いている場合，NAT 越えの問題からこのノードに対して容易に新しに従って更新する．ここで，確率的勾配降下法の収束性を保証く通信を開始することができない．NAT 越えの問題とは，プη 2 < ∞ かつτ τ

ライベート IP アドレスをグローバル IP アドレスに変換する

ητ = ∞ の条件を満たさなければならないことに注意す

NAT という技術を用いた際に，内部ネットワークから外部ネッる [4]．オンライン学習では，新しいデータを得るたびにこの更トワークへの通信は開始できるが，外部ネットワークから内部新を行い，誤差が収束するまで繰り返す．ここでオンライン学ネットワークに対しては，リクエストを適切な内部のホストに習の重要な性質として，誤差関数が凸関数である場合，データ関連付けられないために通信を開始できないという問題である．

サンプルが互いに独立かつ同一の確率分布から生成されると仮

現在，家庭用マシンからクラスタまで，多くのコンピュータが定すると，学習によるパラメータはほとんど確実に最小解に収プライベート IP アドレスを使用しているため，この手法は現束することが保証される [4]．つまり，各ノードが学習データを実的ではない．この問題を避けるために，我々は隣接ノードを保有している場合，ノードをネットワーク上から独立かつ一様更新せずとも，選択確率を用いるノード選択の手法を提案する．

するために，学習におけるパラメータ ητ が∑τ∑

ランダムに選択し，モデルを送信することで，モデルパラメータは誤差の最小解に収束することが保証される．次に紹介する

3. 提 案 手 法

gossip learning [7] では，隣接ノードリストを十分な回数シャッ

我々が提案する手法では，モデルが学習する訓練データのサンフルした後に，ランダムな隣接ノードにモデルを送信することプル列をネットワーク上からバランスよく取得するために，選択で，ネットワーク上の一様ランダムなノードのサンプリングを確率に基づいたモデルの送信先ノード選択を行う．Algorithm2行っている．に提案手法によるノード選択手法の擬似コードを示し，図 1 に

2. 2 gossip learning

本手法によるノード選択確率の例を示す．
選択確率は Metropolis-Hastings random walk (MHRW) に倣った確率を設定する．図 1 から分かるように，この選択確率は入次数の大きなノードに対して低い確率を，入次数の小さなノードに対して高い選択確率を設定し，ノードの訪問確率を調整している．ただし，この選択確率により取得するサンプル列が一様分布に従う収束を達成する保証は現時点で確認できてい表 1 実験マシンの構成

Algorithm 2 Proposed Peer Select Algorithm
1: function MHRW-basedPeerSelect( )OSUbuntu 14.04.2 LTS

2:p ← select a neighbor at random

CPUIntel 2.4 GHz Xeon E5620

3:

α←

メモリ

32 GB RAM

Java

Java SE 8 Update 45

indegree(self )indegree(p)4:if ramdom.uniform(0, 1) < α then return p5:elsereturn self

6:

end if

4. 実

7: end function
8:
9: function MH-basedPeerSelectWithoutSelfSel( )10:loop験

表 1 に実験を行ったマシンの構成を示す．実験はイベント
ベースの P2P シミュレータである PeerSim（注 1） 上で行った．

11:p ← select a neighbor at randoma ) データセット

12:indegree(self )α ← indegree(p)学習に用いるデータセットには，UCI データベースリポジ

13:

if ramdom.uniform(0, 1) < α then return pトリ（注 2） から入手した Spambase を用いる．データ数は 4601

14:

end if個で，各データは 57 つの特徴量と 0 か 1 のクラスを持つ．各15:

end loop

クラスのデータ数の比は 1813：2788 で，ランダムに選出した

16: end function

461 個のデータを検証用データとし，残りの 4140 個のデータを訓練用データとした．

b ) ネットワーク
ネットワークには Barabasi-Albert model (BA model) [1] を有向グラフに適用して生成したネットワークを使用する．BA

model は多くの実ネットワークが有する特徴の一つであるス
ケールフリー性を擬似的に発生させるアルゴリズムである．ス
ケールフリー性とは，わずかなノードが大きな次数を持ち，多くのノードが小さな次数を持つ性質であり，Gnutella [6] のような実際の P2P ネットワークもこの性質を有する．
また，入次数が 0 のノードに対してはランダムなノードの隣接ノードにこのノードを追加することで，全ノードの入次数が必ず 1 以上になるように調整を加えた．これは入次数が 0 のノードが存在するときにこのノードが常に初期化された学習モデルをネットワーク上に配信することを防止するためである．
このアルゴリズムによって生成されたグラフは，次数分布がべき乗則に従っているため（図 2），スケールフリー性を有していることが確認できる．ネットワークサイズは学習データ数と図1

提案手法によるノード選択確率の例

同じ 4140 とし，各ノードの出次数は 10 とした．また，実験は同様のアルゴリズムで生成した 5 種類のネットワークに対してない．
具体的にモデルの送信先ノードは次のように決定する．まず行った．

c) 学 習 方 法

隣接ノードからランダムにノード p を選出し，自ノード self と実験には三つのノード選択の手法を用い，それぞれの結果をp の入次数の比に応じた採択率 α を決定する．α が 1 よりも大比較する．一つ目は既存手法のノード選択方法である News-

きな場合は p を選択し，α が 1 を下回る場合は，確率 α で p をcast [8] を用いる手法で，スケールフリーネットワークを初期状選択し，確率 1 − α で self を選択する．

態として，各ノードは一定の時間区間ごとに隣接ノードのリス

この手法を用いるために，各ノードは隣接ノードの入次数をトであるビューを交換しながら，ビューから一様ランダムに選取得する必要があり，各ノードは自身の入次数の情報を通信しんだノードにモデルを送信する．二つ目は単純ランダムウォー合わなければならない．しかし，このための通信コストは，モクに倣うノード選択手法で，各ノードは固定のビューの中からデルを受け取った際の返信に自身の入次数の情報を付随させる一様ランダムに隣接ノードを選択し，学習モデルを送信する．

ことで小さく抑えることが可能である．このとき，初期状態に三つ目は MHRW ベースのノード選択手法である．

一様な選択確率を仮定した場合でも，モデル送信を数回繰り返

また，モデルの更新にはサポートベクタマシン (SVM) とロすだけで正確な選択確率を設定できるため，学習に大きな影響

ジスティック回帰の二つの手法に対し確率的勾配降下法を用いを与えない．
（注 1）：http://peersim.sourceforge.net/（注 2）：https://archive.ics.uci.edu/ml/datasets.html

課題としたい．ただ初期の収束速度に関しては，いずれの学習アルゴリズムにおいてもランダムウォークに倣った手法よりも優れている．
図 4 は上記の実験において，学習終了時である 35000 サイクル後の各ノードの予測誤差を大きい順にプロットしたグラフである．x 軸は予測誤差の大きさでソートされたノードを表し，y軸は x 番目に誤差の高かったノードの予測誤差を表す．全手法において，予測誤差が 0.5 を上回るノードから 1 ノードにおける誤差に近い誤差を持つノードまで，満遍なく存在することがわかる．このグラフにおけるほぼ学習ができていないモデルに対して特に考察をすることで，全モデルが 1 ノードにおける誤差の値まで収束することを今後の目標としたい．

5. 関 連 研 究
P2P 上のデータを対象とした機械学習手法は過去にいくつか存在する．P2P 上の機械学習の主な目標の一つに，集中型のアプローチによって得られる学習モデルの精度にできる限り近づくことが挙げられる [5] [2]．しかし，集中型の学習と比べ，P2Pを対象とした学習手法には，スケーラビリティや，ピアの挿入
図 2 入次数の分布や離脱，学習データの増減，耐故障性，プライバシ，セキュリ
ティなどいくつかの考慮すべき課題がある [5] [3]．また，ネッたアルゴリズムを用いた．また，二通りアルゴリズムに対し，トワーク上の広範囲のデータを予測に反映させるために，各所モデル受信時に直前のモデルをマージする場合と，上書きにの局所的なデータを学習したモデルをマージすることにより新よって書き換える場合の計四通りの実験を行った．

しいモデルを生成する手法 [2] [12] [3] [9] や，各ノードによる投d) 検 証 方 法

票によって予測を行う手法 [11] が存在する．モデルを送信する

検証には検証用データに対する各ノードの予測誤差の推移をことで学習行うこれらの研究では，通信先となるノードをラン用いる．学習が一定期間進むごとに，各ノードは最新の学習モダムな隣接ノードから選択したり [9], [12]，分散ハッシュテーブ

デルで共通の検証用データに対して予測を行い，実際のクラスルを用いて選択したり [3] するが，本研究では，モデルの送信との間に 0-1 誤差を算出する．この誤差の総和を検証用データ先ノードを次数に従った確率で決定する点においてこれらの研セットの数で割った値をそのノードの予測誤差とする．実験で究とは異なる．

は各ノードの予測誤差の推移を観測することで，モデルの精度と収束速度を確認する．

e) 実 験 結 果6. まとめと今後の研究課題
本論文では，隣接ノードリストを更新せずとも，モデルの送図 3 に全ノードの予測誤差の平均値の推移を示す．実験は乱信先ノードを MHRW に倣った選択によって決定することで，数を変えて生成した 5 種類のネットワークを用いたが，いずれネットワーク上のデータをバランスよく学習する手法を提案しも以下に述べる内容とほぼ同様の結果を得たため，代表としてた．また，シミュレーションを用いて実験を行い，提案手法は一つの実験結果を示す．x 軸は学習のサイクル．y 軸は予測誤

既存手法のデメリットを排しながらも既存手法と同程度の予測差を示し，誤差が下がるほど全体のモデルの精度が良くなって精度と収束速度を達成することを確認した．

いることがわかる．このグラフでは，まず全手法において予測また，今後の研究課題の一つに全ノードの誤差の収束値を最誤差の平均が 1 ノードの SVM による予測誤差を大きく上回っ小にすることが挙げられる．これは学習サンプルを一様分布にていることがわかる．ここで，既存研究である gossip learning

従うように取得するとともに，サンプルを独立に取得することの論文 [7] では 1 ノードの SVM の誤差まで収束をしているが，による改善が考えられる．今回提案手法として用いたランダム今回はこれを再現できなかったため現時点の結果として本論文

ウォークベースのノード選択手法では，モデルが隣接ノードにには記載する．

沿ったデータを学習するため，学習するデータのサンプル列はその前提で考察を行うと，提案手法は隣接ノードリストの更サンプル間の相関が強くなる．ネットワーク上の学習データを新を行わないにも関わらず，既存手法とほぼ同程度の収束値と独立に取得するためには，例えば n 個飛ばしでサンプリングを収束速度を達成していることがわかる．しかし，マージ処理を行うなど，直前にサンプリングしたデータとの相関を十分に減行わない学習アルゴリズムでは，提案手法・既存手法ともにラ少させる方法がある．ただし，このようにデータを間引くサンンダムウォークに倣ったナイーブな選択手法に対して精度で逆プリングは十分な n の値を推定する必要があり，また一回のサ転されている．これについては現在調査中なため，今後の研究ンプリングに必要なノード間の通信回数が増えるという問題も

(b) Pegasos SVM (merge)
Average of the Prediction Error

Average of the Prediction Error(a) Pegasos SVM
0.55
0.5
0.45
0.40.35

Newscast
Random walk
MHRW
SVM

0.3
0.25
0.2
0.15
0.1
00.55
0.5
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1

5000 10000 15000 20000 25000 30000 35000

05000 10000 15000 20000 25000 30000 35000

CyclesCycles(d) Logistic Regression (merge)
Average of the Prediction Error

Average of the Prediction Error(c) Logistic Regression
0.55
0.5
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
00.550.50.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1

5000 10000 15000 20000 25000 30000 35000

05000 10000 15000 20000 25000 30000 35000

CyclesCycles
図 3 全ノードの予測誤差の平均発生する．
また，別の研究課題として適切な終了判定を設定することが挙げられる．本研究では学習の終了判定を行わず，全ノードの[3]予測誤差の平均がある程度変化しなくなった時点を学習の終了としたが，実際のシステムでは各ノードが全体のノードの予測誤差を知ることは困難なため，各ノードの終了判定を考慮する[4]必要がある．例えば，自ノードの現在保有するモデルの予測誤差がある値以下になった場合にゴシッププロトコルによるモデ[5]ルの送信を停止するような終了判定が考えられる．ただし，この終了判定では終了判定を下したノードのデータを他の学習モデルが学習できなくなるという問題が挙げられる．

謝[6]

辞

本研究は JSPS 科研費 25700008 および 16K12406 の助成を受けたものです。本研究の一部は、国立研究開発法人新エネルギー・産業技術総合開発機構（NEDO）の委託業務として行わ[7][8]れました。
[9]

文献[1] Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics,
Vol. 74, No. 1, p. 47, 2002.
[2] Hock Hee Ang, Vivekanand Gopalkrishnan, Steven CH Hoi,and Wee Keong Ng. Cascade rsvm in peer-to-peer networks.
In Joint European Conference on Machine Learning and

[10]

[11]

Knowledge Discovery in Databases, pp. 55–70. Springer,2008.
Hock Hee Ang, Vivekanand Gopalkrishnan, Wee Keong Ng,and Steven Hoi. Communication-eﬃcient classification inp2p networks. In Joint European Conference on Machine
Learning and Knowledge Discovery in Databases, pp. 83–98. Springer, 2009.
Léon Bottou. Online learning and stochastic approximations. On-line learning in neural networks, Vol. 17, No. 9,
p. 142, 1998.
Souptik Datta, Kanishka Bhaduri, Chris Giannella, Ran
Wolﬀ, and Hillol Kargupta. Distributed data mining inpeer-to-peer networks. IEEE Internet Computing, Vol. 10,
No. 4, pp. 18–26, 2006.
E. Gregori, L. Cherkasova, G. Cugola, F. Panzieri, andG.P. Picco. Web Engineering and Peer-to-Peer Computing: NETWORKING 2002 Workshops, Pisa, Italy, May
19-24, 2002, Revised Papers. Lecture Notes in Computer
Science. Springer Berlin Heidelberg, 2003.
István Hegedűs. Gossip-Based Machine Learning in Fully
Distributed Environments. PhD thesis, szte.
Márk Jelasity, Wojtek Kowalczyk, and Maarten van Steen.
Newscast computing. 2012.
Wojtek Kowalczyk, Nikos A Vlassis, et al. Newscast em. InNIPS, pp. 713–720, 2004.
Chul-Ho Lee, Xin Xu, and Do Young Eun. Beyond randomwalk and metropolis-hastings samplers: why you should not
backtrack for unbiased graph sampling. In ACM SIGMETRICS Performance evaluation review, Vol. 40, pp. 319–330.
ACM, 2012.
Ping Luo, Hui Xiong, Kevin Lü, and Zhongzhi Shi. Distributed classification in peer-to-peer networks. In Proceed-図 4 35000 サイクル後の各ノードの識別誤差の分布．

ings of the 13th ACM SIGKDD international conference on
Knowledge discovery and data mining, pp. 968–976. ACM,
2007.
[12] Stefan Siersdorfer and Sergej Sizov. Automatic documentorganization in a p2p environment. In European Conferenceon Information Retrieval, pp. 265–276. Springer, 2006.