Comments
Description
Transcript
複雑ネットワークにおける経路学習問題に関する研究
滋賀大学大学院教育学研究科論文集 91 第 13 号，pp. 91-102，2010 原著論文 複雑ネットワークにおける経路学習問題に関する研究 伊 藤 友 洋† A Study on Path Learning Problem in Complex Networks Tomohiro ITOH Abstract Many networks in the real world show the scale-free property in which degree distribution of a network follows a power-law. It has been suggested that scale-free networks are vulnerable to attack on the highly connected nodes, called hubs. Thus, path learning in scale-free networks faces problems of optimality and attack-tolerance of learned path. In this study, I attempted to obtain attack-tolerant behavior of the reinforcement learning agent by employing the cost function and tuning the three learning parameters. The cost function aiming at avoiding paths consisting of hubs improved the attacktolerance. Tuning of a parameter called the discount rate was also found to be effective in decreasing the attack damage. 習」の二種類に大別される2)。教師あり学習で 1．序 論 は，学習時に与えられる正解に関する情報 (教 師信号) を基に，ロボットがより正解に近い行 現代社会においては，コンピュータも含めた 動を学習する。一方，教師なし学習では，正解 広義の「機械」が，我々の生活に様々な形で浸 の行動そのものが教えられるのではなく，ロ 透してきている。機械の利用形態の多様化によ ボットが行動結果の評価を通じて，より評価の り，個々の機械を知能化し，ユーザの使用目的 高い行動を獲得するように学習を行う。このた に合わせて自律的に機能を変化させることが求 め，教師なし学習は，ロボットの利用形態の多 められている。このような背景から，学習のた 様化という時代背景に適合した機械学習の方法 めの機構をロボットなどの機械に組み込む研究 であると考えられる。 が盛んに進められている。特に，ロボティクス 近年，情報科学の分野は急速な発展を遂げ， 分野においてロボットの学習は主要な研究課題 我々の周りを取り巻くシステムの多様化・複雑 の一つである1)。 化は歯止めがかからない状況にある。その最た 機械学習は「教師あり学習」と「教師なし学 る例がインターネットである。1980 年代まで は，インターネットは一部の企業・大学・研究 †学校教育専攻 情報教育専修 指導教員：右田正夫 機関で使用されていたに過ぎないが，1990 年 から 2000 年の間にかけて家庭用のパーソナル 92 伊 藤 友 洋 コンピュータの普及と共にインターネット人口 れる経路は，ネットワークにおいて基幹的な役 が爆発的に増えた。2006 年時点で世界に存在 割を果たすノードを含む場合が多い。基幹的な する web サイトは 350 億を超えるとも言われ 役割を持つノードはその利便性から，恰好の攻 3) ている 。そのサイト同士を結ぶリンクが複雑 撃対象とされやすく，また破壊された時にネッ に絡み合い，複雑な構造を造り上げており，シ トワーク全体に及ぼす影響は大きい。したがっ ステムの枠組みを設計した我々人間にもその全 て，ネットワークの経路学習問題において，重 体像を掌握する事は困難を極める。 要かつ基幹的なノードを利用するという事には 更に，このような大規模且つ複雑な現実世界 のネットワークは，重大な脆弱性を抱えている。 2006 年 8 月 14 日，日本の首都圏において大規 一定のリスクもある。 そこで本論文では，学習エージェントがネッ トワーク上のノードをどのように利用するかを 模な停電が起こった。被害は東京 23 区東部， 調べ，リスクの高い経路を避ける耐攻撃性の高 横浜市・川崎市，浦安市，市川市など広い範囲 い学習エージェントを提案する。 に及び，約 139 万世帯の住宅や鉄道等の公共機 関に影響が出た。停電の原因は新京葉変電所， 江東変電所，並びに荏田変電所を接続する「江 2．強化学習による人工エージェント の獲得 東線」と呼ばれる高圧電線がクレーン船の接触 強化学習とは，エージェントと呼ばれる学習 によって切断された事にある。この，変電所同 者が試行錯誤を通して自律的に行動獲得を行う 士を結ぶ基幹的な送電線の切断により，首都圏 機械学習法である。環境の外部からの情報を基 は著しい電力不足に見舞われた。平成 17 年の に学習する「教師あり学習」とは異なり，エー 国勢調査によれば，首都圏の世帯数は 1400 万 ジェント自身が行動によって得た経験に基づい 戸を超える。ネットワークの規模から言えば， て学習を行う。その為，全体像が把握できてい たった一本の送電線が切れた程度なら微小なダ ない未知環境においても適応的な行動を獲得す メージに終わりそうだが，現実世界のネット ることが可能な学習法である。 ワークは，そうではない。 本研究では，インターネットや電力の供給網 心理学者のスキナーは，動物の行動が試行錯 誤を通して形成され得ることを示すため，「ス など，現実世界に多く見られる複雑なネット キナー箱」として知られる実験装置を用いて， ワークに，教師なし学習の一種とされる強化学 ラットが餌を得るために，装置内のレバー操作 習を適用することを試みる。本来，強化学習は を学習できる事を示した4)。箱の中には，レ 2 次元のグリッド空間のような単純なグラフ構 バーを押すと餌が出現する装置がある。実験初 造 (トポロジー) を持つ環境において有効性が 期の段階では，ラットはレバーを押せば餌が得 高いとされているが，インターネットのような られるといった因果関係を把握していない。そ 複雑なネットワークシステムに強化学習のナビ の為ラットが動き回る内に偶然レバーが押され ゲーション問題を適用した際，行動学習は機能 て，餌を得るという事が繰り返される。しかし， するのか，また，学習で可能であった場合，ど ラットは次第に「レバーを押すと餌を得られ のような行動が獲得されるのか，その有効性や る」という関係を学習し，「空腹時にレバーを 特徴について考察する。また，ネットワークの 押す」という行動傾向が強化されていく。強化 基幹的なノードに起こる障害によって，学習し 学習もこれと同様であり，報酬 (餌) を積算し た行動が阻害されないようにするための方策に ていくことで探索に基づいた知識の利用により ついても考えたい。 行動する。強化学習においては，探索と知識利 ナビゲーション問題では，特別な問題設定で もない限り最短経路が最適解とされる場合が多 用という，相反する傾向のバランスが非常に重 要である。 い。本研究においても，基本的に距離の短い経 路を学習する事を目的として実験を行う。しか 2. 1 Q 学習 し現実世界のネットワークにおいて，最短とさ 本節では，機械学習の代表的な手法として 複雑ネットワークにおける経路学習問題に関する研究 Q 学習を取り上げ，その枠組みについて述べ 93 づいて行動を決定する。その行動の選択法とし る。Q 学習では，ある時刻におけるエージェ て，本研究ではソフトマックス選択を採用する。 ントが状態 s にある時，行動 a をどのような確 ソフトマックス選択 率で選択するかという方策を，蓄積された経験 ソフトマックス選択では，エージェントが行 に基づいて学習していく1)。過去の経験は Q 動 i を選択する確率を以下の式(2) によって決 値という評価値に反映され，これがエージェン 定する。 トの行動選択の指針となる。また，Q 学習は， Qs, a τ Pi= Qs, a ∑ exp τ 離散空間・離散時間を扱う事を前提としており， マルコフ性を満たすマルコフ決定過程の下で。 最適解に収束する事が証明されている5)。マル exp ⑵ コフ性とは，ある時刻 t+1 における環境への 基本的には，Q 値の高い行動が選択されや 応答は時刻 t における状態と行動にのみ依存す すく，Q 値の差が明確であればある程グリー るという事を意味する。Q 値の更新式は以下 ディ選択に近い行動選択を行う。しかし，ソフ の通りである。 トマックス選択では，温度パラメータと呼ばれ Qs, aQs, a+αr+γmax Q s , b−Qs, a ⑴ る τ の値によって Q 値に対する選好性を変化 させる事ができる。例えば，τ が 0 に近づくほ ど行動選択の確率は Q 値の高低に鋭敏になり， エージェントが目標状態に達すると，目標状 Q 値の高い行動がより高い確率で選択される 態に至った状態・行動の Q 値に報酬 r が加算 ようになる。逆に τ が大きくなれば，行動選択 される。また Q 値は，次ステップでの状態・ の確率はより均等になりエージェントはランダ 行動の組の中で行動価値が最大となる Q 値を ムに近い行動選択を行う。ソフトマックス選択 用いて更新が行われる。1 ステップ先の状態の によって，強化学習の課題である，探索と知識 Q 値を参照する事により，報酬 r は次第に目標 利用のトレードオフという問題に対処する事が から遠い状態の Q 値にも影響を与えることに 可能である6)。 なる。「←」は代入記号であり，右辺で最新の Q 値 Q(s, a) を計算し，左辺に代入する。なお， maxQ(s’, b) とは，状態 s の次の状態 s’を引数 として持つ Q 値の内で最大の Q 値を指す。状 2. 2 二次元グリッド空間におけるナビゲー ションの適用 6×6 の正方グリッド空間での実験について 態 s’と状態 s の Q 値の差を加算することで， 述べる。エージェントは上・下・左・右 4 パ 直接報酬が与えられない行動の評価も可能にな ターンの行動を逐次選択し，スタート地点 (0, る。 0) からゴール地点 (5, 5) を目指すものとす α は，学習による Q 値の更新の大きさを調 る。また，マス目一つの移動を 1 ステップとし 節するパラメータであり，学習率と呼ばれる。 てカウントする。(0, 0) から (5, 5) までの最 ここでは，0<α≦1 の値を用いる。 短ステップ数は 10 であり，エージェントは 10 強化学習は過去経験を積算して学習を行うが， ステップでゴールに到達する経路を最適解とし 学習初期の行動で得た経験と直近の行動で得た て目指す。エージェントがゴールに到達した時 経験を同等に扱う事は，動的な環境で学習を行 点まで，または 100 ステップ経過した時点ま う上で妥当であるとはいえない。そこで割引率 でを 1 エピソードとし，200 エピソードを 1 試 γ(0<γ<1) を用いる。γ が小さいとエージェ 行の学習期間とする。学習を開始する時点での ントは即時報酬をのみを考慮し，近視眼的な学 Q 値の初期値は，全ての状態と行動の組み合 習を行う。逆に γ が大きいとエージェントは報 わせについて 2.0 に設定されており，学習開始 酬が得られるまでの時間が長い，いわゆる「報 直後のエージェントは，ランダムに近い行動を 酬遅れ」の問題に対処しやすくなる。 とる。行動を繰り返す毎に Q 値は更新され， Q 学習において，エージェントは Q 値に基 その Q 値は次のエピソードに継承される。こ 94 伊 藤 友 洋 のようにしてエージェントはエピソードが進ん を除けば，学習の速度に違いが出る程度であり， でいく過程で，経験に基づいて Q 値を更新し， ほぼ最適解である 10 ステップでゴールに到達 適応的な行動を学習する。 できている事が見て取れる。割引率 γ を変化さ 1000 試行の結果を平均したものを，図 1 に せた場合，先の 2. 1 節で述べた通り，学習エー 示す。なお，ここで，Q 学習のパラメータは ジェントは将来の報酬が期待できるような行動 特に断らない限り α=0.7，γ=0.7，τ=1.0 に設 の連鎖を学習する。今回のように学習途中で変 定している。 図 1 より，学習エージェントは，6×6 の正 化しない静的な環境下では，図 1(b) の通り γ を高く設定すると，より良い行動を学習する。 方グリッド空間において最適解である 10 ス 逆に γ=0.1 の場合のように割引率を低く設定 テップでゴールに到達可能である事がわかる。 すると，エージェントは冗長な経路を学習しや Q 学習は元来このような規則性の高い環境で すい。 の学習を非常に得意としている。 3．複雑ネットワーク上の ナビゲーション学習 また，Q 学習のパラメータ α，γ，τ をそれ ぞれ変化させて学習させた結果より，割引率 γ WWW，友人関係，はたまた伝染病の感染経 路に至るまで，我々の周りには様々な繋がりが 存在し，それらは複雑なネットワーク構造を有 している。近年，この複雑ネットワークの研究 が活発である7)。それまでランダムな構造を持 つとされた現実世界のネットワークも解析が進 むにつれ，いくつかの興味深い特徴を持つ事が 示された。本章では複雑ネットワークを簡単に 紹介し，また現実世界のネットワークに近い構 造を持つネットワークにおいて，Q 学習が有 用であるかという問題について検証する。 3. 1 複雑ネットワークについて 20 世紀末以降，「複雑ネットワーク」に関す る研究が世界的に注目を集めている。今日にお いては，経済，社会科学，生物学に至るまであ らゆる角度から，現実世界のネットワークに関 する研究が盛んに進められている。 3.1.1 複雑ネットワークとは何か 現実世界のネットワークは複雑かつ巨大なも のである。また，そのネットワークの繋がりは 一見ランダムで規則性が無いようであるが，厳 密にはランダムにつながっているわけではない。 数学者のポール・エルデシュは，非常に多数 の論文を発表したことで知られている。彼と共 著論文を執筆した研究者の数は研究者全体の数 から見れば非常に少ないが，共著関係にある者 同士の距離を 1 として考えると，ほとんどの研 (a) 学習率 α，(b) 割引率 γ，(c) 温度パラメータ τ 図1 6×6 の正方グリッド空間における学習曲線 究者がエルデシュとは平均して 5 から 6 といっ た比較的短い距離で繋がっている。このような 複雑ネットワークにおける経路学習問題に関する研究 95 ネットワークにおいて，エルデシュのように数 大多数を有するハブが使用不可になれば，ネッ 多くの研究者と繋がっている者は少なく，大多 トワーク全体の機能に大きな影響が及ぶ事が知 数の研究者は少数の共著関係しか持たない。 られている8)。 WWW ネットワークにも同様の事が言える。 3. 1. 4 クラスター性 大手ポータルサイト Google のように多数のリ ネットワークの構造を示す「クラスター係 ンクを持つサイトがある一方で，数多くの殆ど 数」という指標がある。あるノード vi の次数 リンクを持たないサイトが存在する。後述のよ を kiとする。viと，vi の隣接ノードから 2 つの うに，このようなネットワークにおいては，そ 点を選びペアを作るとすると，ペアとなる組み れぞれのノードが持つ次数 (リンクの数) は完 合わせは ki (ki −1)/2 通りである。クラスター 全にランダムではない。また，ノード同士の距 係数は，ki (ki −1)/2 をさらに，vi の隣接ノー 離 (頂点間距離) も，ネットワークの要素数 ド同士でリンクを持つ組み合わせの数で割った N に対して logN 程度であり，要素数 N の 2 次 数値で表わされる。 元格子の平均頂点間距離が N 程度であること クラスター係数が高いとき，ネットワークは を考えると，非常に短いといえる。このような クラスター性を持つという，このようなネット 性質を持つネットワークを総称して複雑ネット ワークでは，リンクで繋がる二つのノードにつ ワークと呼ぶ。 いて，ネットワークからもう一つのノードを選 3. 1. 2 スモールワールド性 スモールワールド性とは，多くのノードから なるネットワークであっても，任意の 2 点が平 んだときに，三者が互いにリンクで繋がれてい ることが多い。 3. 1. 5 BA モデル 均的に短い距離によって結ばれているという現 WS モデルは，スモールワールド性を満たし 実世界のネットワークにしばしば見られる特徴 てはいるもののノード次数がベキ分布にはなら である。上述のエルデシュの例で言うと，数多 ず，現実世界のネットワークの特徴をよく表わ くの研究者が存在する一方で論文の共著関係を している，とは言い難いものである。そこで 辿れば，ある研究者とエルデシュの距離が平均 ネットワークのスケールフリー性を再現する して 5 から 6 程度といった短い距離で繋がれて ネットワークモデルが，1999 年に Barabási と いる事に相当する。 Albert に よ っ て 発 表 さ れ た。Barabási と 1998 年に Watts と Strogatz がスモールワー ルド性を持つネットワークのモデルを発表した。 これが近年の複雑ネットワーク科学の始まりと も言われている。 3. 1. 3 スケールフリー性 Albert の頭文字を取って BA モデルと呼ばれ る9)。 この BA モデルには二つの特徴がある。第一 に，ネットワークが成長していく事である。 WS モデルでは，ネットワーク生成初期の段階 大多数のノードは少数のノードとしか繋がっ で使用するノードを全て用意しなければならな ていないが，非常に多くのノードと繋がるノー いが，BA モデルはネットワークを生成する過 ドが少数存在する。横軸に次数，縦軸にその次 程でノードを徐々に追加していく。このモデル 数を持つノードの割合をプロットし，両対数で では，インターネットでユーザ数が年々増え続 表示したときにグラフが直線状になるなら，そ けるようなネットワークの成長を表現する事が のネットワークの次数分布はベキ則に従うとい 可能である。また，第二の特徴は優先的選択で う。また，次数分布がベキ則に従うとき，その ある。新規にネットワークに参加したノードが， ネットワークはスケールフリー性を持つという。 既存のノードにリンクを張る際には，リンク先 共著関係のネットワークにおけるエルデシュ として次数の高いノードが高い確率で選ばれる のように特に次数の高いノードを「ハブ」と呼 ようになっている。 ぶ。ハブの存在はスケールフリー性を持つス この二つの特徴により，結果的に生成される ケールフリー・ネットワークにおいて弱点にも ネットワークの次数分布がベキ則に従うものと なり得る。ネットワーク上に存在するリンクの なる。すなわち，WS モデルでは再現できな 96 伊 藤 友 洋 かったスケールフリー性を持つネットワークの ノードが使用不可となる場合のナビゲーション 生成が可能である。 学習の実験について述べる。 3. 2 ネットワークの耐攻撃性 3. 1 節で述べたように，現実世界のネット 4. 1 複雑ネットワークにおける Q 学習の適用 BA モデルにより生成されたネットワークに ワークは基幹的なノードに対する攻撃に弱い。 おいて，Q 学習による経路学習を行う。Q 学 現実世界においての基幹的なノードはスケール 習が規則性の高い空間に強い事は 2 章にて述べ フリー・ネットワークのハブに相当する。ス たが，本章では現実世界のネットワークを模し ケールフリー性を持つネットワークはこのよう たグラフ上でのエージェントの振る舞いについ な脆弱性を抱えており，ハブに相当するノード て述べる。ネットワークがスケールフリー性を は，悪意ある攻撃の格好の対象となり得る。ス 持つ点が正方グリッド空間と大きく異なる点で ケールフリー・ネットワークを運用する上で， ある。 耐攻撃性を考慮する事は必要不可欠である。 4. 1. 1 複雑ネットワークにおける Q 学習の 実験の概要 3. 3 複雑ネットワークと Q 学習 本実験では，BA モデルによって生成された 2. 2 節でも述べたように，Q 学習に関する先 ノード数 N=1000 のネットワーク (図 2) を 行研究の例としては，シングルエージェントに 用いる。なお，ネットワークを生成する際のパ よるナビゲーション学習はもちろんの事，複数 ラメータは，それぞれ m0 =4，m=2 とした。 のエージェントを用いたマルチエージェントに 図 3 は横軸に次数，縦軸に出現頻度をプロット よる協調・競合行動獲得などが挙げられる。し し，両軸に対数をとったグラフである。次数の かし，スケールフリー・ネットワークを含む複 分布はベキ則に従い，BA モデルによって生成 雑ネットワーク上の経路学習に適用された例は ない。スケールフリー・ネットワークではハブ と呼ばれる，圧倒的に多くの次数を持つノード が存在する。エージェントがハブに到達した場 合を考えると，エージェントは多数の選択肢を 突きつけられることになり，最適とされる状 態・行動の Q 値が十分に高い値に収束する事 が困難であると予想される。 そこで本研究では，現実世界における複雑な 環境を模したネットワークにおいて，エージェ ントがどのように振る舞うか観察する。このと き，現実世界のネットワークに起こり得る問題 を考慮し，実験を行う10)。 図2 実験に用いた N=1000 のネットワーク 4．計算機実験 本章では，複雑ネットワーク上のナビゲー ション問題に Q 学習を適用した実験を紹介す る。4. 1 節において BA モデルによって生成し たスケールフリー・ネットワーク上での Q 学 習の実験を紹介する。そして 4. 2 節以降は現実 世界のネットワーク上でも起こり得る問題とし て，ネットワークが攻撃を受け，次数の大きな 図3 次数 k のノードの分布 p(k) 複雑ネットワークにおける経路学習問題に関する研究 97 されたネットワークがスケールフリー性を持つ が，遥かに多いノードを有する。その影響か， ことがわかる。 6×6 の正方グリッド空間での結果と比較して ネットワークのスケールフリーという性質上， 学習の速度に差はあるものの，パラメータの設 最短経路はハブ，またはそれに準ずる次数の大 定による挙動についてもほぼ同様の結果が得ら きいノードを経由する経路が多数を占めており， れた事がわかる。そして，比較的次数の高い エージェントがハブに入ると次ステップで移動 ノードを含む経路を多く学習していた事より， 可能なノードが急激に増える。このネットワー エージェントが多数の選択肢の存在に対応可能 クの最大次数は 60 である為，エージェントは 突如として 60 通りの選択肢を突きつけられる 可能性がある。Q 学習は行動可能な全ての選 択肢に対応する Q 値を参照する為，選択肢の 多い問題に適応するには時間を要すると予想さ れる。この為，本研究では選択肢が多数存在す る場合においてもエージェントが環境に適応で きるのかという点に注目する。 まず，頂点間距離が最大となる二つのノード をそれぞれスタート・ゴールと設定する。エー ジェントはリンクの張られているノード間を移 動していくことで，スタート地点のノードから ゴール地点のノードを目指す。1 エピソードあ たりの最大ステップ数は 200 までとし，200 エ ピソード繰り返す。この一連の流れを 1 試行の 実験とし，後述する各設定について 100 試行ず つ実験を行い，エピソード毎の所要ステップ数 の平均によって学習曲線を得た。また，Q 学 習のパラメータに関しては，2. 2 節の実験と同 様 に，特 に 断 ら な い 限 り は α=0.7，γ=0.7， τ=1.0 に設定している。 4. 1. 2 複雑ネットワークにおける Q 学習の 実験の結果 スケールフリー・ネットワークにおいて，Q 学習のエージェントを適用した結果を図 4 に示 す。エージェントは，パラメータによって程度 の差はあるものの，エピソードが進むに従い ゴールまでの所要ステップ数を減少させていく。 スケールフリー・ネットワークにおいても Q 学習が適応可能であることが解る。 ま た，表 1 に 示 す 通 り，N=1000 の BA それぞれ，(a) 学習率 α，(b) 割引率 γ，(c) 温度パラメー タ τ を変化させた場合について示す。 図4 ネットワークの方が，最長の頂点間距離は短い パラメータごとの学習曲線の相違 (100 試行の平均) 表 1 6×6 グリッド空間と N=1000 のネットワーク (BA モデル) の特徴量 6×6 グリッド空間 BA ノード数 (N) 36 1000 最大頂点間距離 10 7 平均次数 3.333 3.996 最大次数 4 60 98 伊 藤 かという懸念も解消されている。 友 洋 ネットワーク全体に存在するリンク数が 1998 しかしながら，現実世界のネットワークにお 本であるから，次数上位 4 % のノードを破壊 いて次数の高いノードを含む経路は，ノードが する事で，約 46% のリンクが寸断されてしま 悪意ある攻撃の対象にされやすいという点，そ う。 して利便性の高さから非常に混雑し易いという なお，本論文において「攻撃」とは，上述の 点においてハイリスクな経路であるとも考えら ように次数上位のノードに対して行われるもの れる。 で，攻撃対象となったノード，およびそのリン 次節では，このようなリスクを避けるための 学習法を提案する。 クは使用不可となるものとする。また，特に断 りがない限り，攻撃対象となるノードは次数上 位 4 % 以内のものとする。 4. 2 耐攻撃性の高い経路学習 4. 2. 2 ネットワークへの攻撃に対するコス 本節では，3. 2 節で述べたようなスケールフ リー・ネットワークの脆弱性を考慮した Q 学 ト関数の効果 方法 次数が上位のノードを含む経路は，悪意ある 習について実験を行う。 前節でも述べたように，スケールフリー・ 攻撃に対して影響を受けやすいという意味でハ ネットワークにおいては，ハブを通る最短経路 イリスクな経路である。悪意ある攻撃の影響を の数が多く，その為学習初期の段階でランダム 軽減させるという意味で，次数上位のノードを ウォークを行う Q 学習はハブを通る経路を学 避ける経路を意図的に学習させ，耐攻撃性の高 習する頻度が高い。また，次数上位 1 % 以内 い経路学習を実現したい。そこで，Q 値に対 のノードが攻撃を受けるだけで，エージェント してかかるコストを設定することで，次数の高 が学習した経路の 8 割が寸断されるという事も いノードを避ける経路を学習させる。インター 11，12) 。そこで，本研究では Q ネットのような，動的なネットワーク環境下で 学習でハブを避ける耐攻撃性の高い経路学習 のルーティングアルゴリズムにおいては，回線 確認されている を実現する事を目指す 13) 。パラメータに関し の帯域幅や経路長に応じたコストを設定し経路 ては，4. 1 節と同様に，特に断りがない限り， 探索問題に利用する手法がある14)。本研究で α=0.7，γ=0.7，τ=1.0 と設定する。 は，そうした手法を参考に，現在のノードの次 4. 2. 1 ネットワークへの攻撃について 2. 2 節で述べたように，スケールフリー性を 数と移動先のノードの次数の平均に応じたコス トを設定する手法を提案する。コストによって， 持つネットワークは，ハブのような基幹的な Q 値の減少幅が決定される。現在いるノード ノードに対する攻撃に弱い。このような，ス と移動先のノードの次数の平均値が高い程，リ ケールフリー・ネットワークの攻撃に対する脆 スクの高い経路と評価され Q 値の減少の幅は 弱性は，BA ネットワークを提案した Albert 大きくなる。次数の高いノードに対応する Q 8) らによっても指摘されている 。 そこで本実験では，ハブが悪意ある攻撃を受 ける事を想定し，一定数のエピソードが経過し 値が減少する事で，次数の高いノードを避ける 行動が獲得されやすくなると期待される。 なお，コストはエージェントが通過したノー た後に次数が上位のノードを破壊する。次数上 ドの次数を考慮し，現在のノードの次数 dt と 位のノードの破壊によって，学習によって獲得 移動先ノードの次数 dt+1 の関数とし，次式に された経路がどの程度破壊されるのか，また獲 よって与えられる。 得経路が破壊された場合，別の迂回経路をどの ようにして再学習を行うかについても調べる。 ちなみに，N=1000 の BA ネットワークに Cd, d1=0.5 2− d+d1 2dmax ⑶ おいて，次数が上位 4 % 以内，すなわち 40 個 ここで，dtと dt+1の平均値の最大次数に対す のノードを破壊したとする。その 40 個のノー る比でコスト値が決定される。ただし，Q 学 ドが 持つ リン ク の和 は 926 本 で あ る。一方， 習へ与える影響の程度を考慮し，0.5≦C≦1.0 複雑ネットワークにおける経路学習問題に関する研究 99 る事もコスト効果の一つである。逆にコストを 設定しない場合の再学習の収束性が，比較的悪 い事から，コストをかけない場合には，エー ジェントが解を獲得できずその行動が収束しな い場合が存在する事が確認された。 考察 攻撃前の学習時には，学習の速度，収束した ステップ数，等を学習曲線から比較をしたが， コストの有無によって大きな差は見受けられな かった。一方で，ノードを破壊した後の再学習 では，わずかながらコストを設定した方で学習 が早く進み，学習曲線の収束も早かった。 本研究では，ハブを避ける冗長な経路学習を 考え，コストを設定する実験を行った。そこで は，エージェントに冗長な経路学習を行わせて， ハブに対する攻撃の影響を軽減させることを試 みた。しかし，コストの設定によって攻撃前の 学習においても，冗長な経路学習を行い，学習 の速度や収束するステップ数に悪影響が出るの ではないかとの懸念があった。 (a) 1 から 500 エピソードまでの学習曲線 (b) 攻撃後 (300 エピソード以後) の学習曲線 次数上位 4 パーセントのノードに攻撃を加えた結果。 (b) に限定して見ると，コスト付き Q 学習のほうが学習は 早い。 かった。それにも関わらず，攻撃を受けた直後 図5 の学習において，攻撃に対する影響が軽減する 通常の Q 学習 (Control) とコスト付き Q 学習 (With cost) の比較 結果的に，攻撃前の学習において，コスト設 定の有無によって結果が大きく変わる事は無 といった結果が得られた。 以上のことから，Q 値にコストを設定する とした。このように設定されたコストを Q 値 事で，ハブに至る行動の Q 値の増加の抑制が にかける事で，次数の高いノードに移動する行 行われ，エージェントが予めハブを避ける経路 動の Q 値を低く評価する。 を比較的多く学習していたものと考えられる。 結果 しかし，ハブの攻撃によって多大な影響を被 図 5 は Q 値にコストを設定し実験を行った ることからも依然ハブを通る経路が多く学習さ 結果である。前半エピソードに相当する攻撃前 れていることがわかった，このような場合，ハ の学習時には大きな差は認められなかったが， ブに至る行動選択の Q 値が依然高い値を示し 次数上位のノードが破壊される後半エピソード ているものと推察され，コストの設定には，改 において一定の効果が見られた。 善の余地があると考えられる。 まず，次数上位のノードが破壊された直後， 4. 2. 3 学習によって獲得された経路の大半が使用不可 能となってしまう為，エージェントのステップ 数は一時的に増大する。しかし，予め Q 値に ネットワークへの攻撃に対するパラ メータ調整の効果 方法 Q 学 習 で は，式 (1) の 学 習 率 α，割 引 率 γ， コストを設定していた場合はステップ数の増大 そして式(2) の温度パラメータτの 3 種のパラ が軽減されている事が解る。 メータ (2. 1 節参照) を調節することで，学習 ノード破壊後の再学習においてもコストを設 のパフォーマンスを調整する事ができる。わず 定すると若干であるが学習が速いという事が確 か 3 種のパラメータであるが，その組み合わせ 認された。また，学習曲線が一定の値に収束す 次第で様々なパフォーマンスを得ることができ 100 伊 藤 友 洋 る15)。 (a) 学習率 α 学習率 α は，学習の更新の大きさを決定す るパラメータであり，学習の効率を調整する事 が可能である。α の値を下げ，敢えて学習の効 率を悪くする事で，環境の変化による影響を比 較的受け難いとされている。ネットワークが攻 撃を受けた後のエージェントの柔軟な対応を期 待した。 (b) 割引率 γ 割引率 γ は，比較的低い値に設定するとエー ジェントは即時報酬を優先し将来の報酬を軽視 する近視眼的な学習を行う。その逆に，γ を高 く設定するとゴールから遠いノードでの行動選 択において，比較的強い選好性を持つ。そして， 2. 2 節の正方グリッド空間の実験結果からも γ の設定如何で，エージェントは冗長な経路を選 択する事が予想され，次数上位のノードを避け る経路も学習しやすくなる事が期待できる。 (c) 温度パラメータ τ τ を比較的大きく設定すれば，学習エージェ ントは知識の利用を相対的に軽視し，探索的な 行動を行う。ノードが攻撃され，一度学習した 経路が寸断される状況においても柔軟に対応で きるのではないかと期待される。逆に，探索的 な行動を行うという事は，ただ単純に最短経路 を最適解とした場合において，冗長な経路選択 が多いという事でもある。 結果 (a) 学習率 α を変化させる場合 図 6(a) より，α の値が高ければ高いほど学 (a) 学習率 α，(b) 割引率 γ，(c) 温度パラメータ τ 301 エピソード目からハブに相当するノードの破壊に伴いス テップ数が増大する 図6 習が早く進み，収束も早い事が解る。α=0.1 パラメータごとのによる学習曲線の相違 (100 回平均) の場合を除いて，攻撃前の学習，攻撃後の再学 習共に，学習曲線が 200 エピソード以内に収束 している。収束までのエピソード数や，学習さ れた経路の長さにもほとんど差は見られない。 (b) 割引率 γ を変化させる場合 攻撃前の学習時は，γ の値が高い方が学習曲 線の収束が早い。攻撃後の再学習においても， 基本的には同様の傾向がみられた。しかし， γ=0.9 の場合だけは，ステップ数が減少しない ことからも，攻撃後の再学習において経路を学 習できずにいる事が解る。 また，図 7 は，横軸に γ，縦軸に攻撃直後の 図7 攻撃を受けたノードの割合別に見た，攻撃直 後 (301 エピソード) のステップ数 いずれの場合も γ=0.3(γ=0.2〜0.4) 付近で最 小値となる。 複雑ネットワークにおける経路学習問題に関する研究 101 平均ステップ数を示し，それらを攻撃対象とな を抑さえられるものの，基本的に冗長な経路学 る次数上位ノードの割合別にプロットしたもの 習であるため，学習の速度は遅くなり，最短に である。この図より，比較的 γ が低く設定され 近い経路を獲得できない傾向にある。耐攻撃性 ているエージェントは，攻撃を受けた直後のス という観点では非常に意味のある結果であるが， テップ数の増大が抑えられる事が確認された。 本来の経路学習問題という観点から考えれば， (c) 温度パラメータ τ を変化させる場合 図 6(b) の結果からも，むしろ γ の値が高い方 攻撃前の学習時には学習の速度に影響が出た。 これは，4. 1 節の実験で示された通りであるが が良いと考えられる。次数の低いノードを含み， かつ，最短であるような経路の学習については (図 4c)，攻撃後の学習曲線は，τ の値に依らず 今後の課題としたい。 一致する (図 6c)。攻撃直後のステップ数は， (c) 温度パラメータ τ の調節について 全ての場合において，ほぼ同程度で平均ステッ τ を高く設定すると，エージェントは探索的 プ数は 180 を超える。また，その後収束までに な行動選択を行う傾向が強くなるため，動的環 要するエピソード数も 100 程度であり，τ の値 境への適応性の向上が期待でき，破壊後の再学 の調整による差は確認できなかった。 習の速度に影響を及ぼすと予想された。しかし， 考察 そのような予想に反して τ の値の変化によって (a) 学習率 α の調節について 破壊後のエージェントの挙動について大きな違 図 6(a) の結果からも，学習率 α に関しては， いは見られなかった。 値が高い程，収束までの所要エピソード数が少 攻撃によって，学習された経路が破壊される なく，より良い結果が得られている。2. 1 節で ことが多いので，基本的に τ の値が高い探索的 も述べたように，α は Q 値の更新の大きさを なエージェントが有利である。しかし，τ の値 調整するパラメータであり，α を低く設定すれ が低いと Q 値の差異に鋭敏になり学習が速く ば，Q 値の変化率が低くなり，エージェント 進むため，探索の遅さがカバーされるものと考 は慎重な学習を行う。短い周期で目まぐるしく えられる。結果的に，攻撃後の学習では，τ の 変化する環境においては，α の低い慎重な学習 高低の長所・短所が相殺される形となり，τ の が功を奏す場面も考えられる。しかし，本研究 値によらず同様の学習曲線が得られたものと考 のように，一度学習が収束した後に，突発的に えられる (図 6c)。 変化が起こる環境においては，α を低く設定す る事の有利性はみられなかった。突発的な攻撃 5．結 論 を考慮する，耐攻撃性という観点からは，α を 高めに設定して，早く学習する事がより良い方 本研究では，BA モデルにより生成したス 策であると考えられる。 ケールフリー・ネットワーク上に Q 学習を適 (b) 割引率 γ の調節について 用し，学習エージェントの挙動の解析を行った。 図 6(b)より，γ=0.9 の場合は攻撃後の再学 また，スケールフリー・ネットワークの攻撃 習が行われていない。しかし，それ以外の場合 に対する脆弱性を考慮し，耐攻撃性の高い学習 は基本的に，攻撃前の学習，攻撃後の学習共に， 法の提案を試みた。その結果，Q 値にコスト γ が高いほど学習曲線の収束が早い。 を設定する手法や Q 学習のパラメータを調整 基本的に，全てのエージェントにおいて，獲 する事により，わずかながらスケールフリー・ 得された経路はハブの破壊により崩される。し ネットワークの弱点であるハブを避ける学習傾 かし，図 7 より，ハブに対する攻撃の影響が γ 向が観察された。特に，攻撃直後のステップ数 の値によって差がある事が解る。特に γ=0.3 の増大に関しては，その増大幅を減少させる事 付近では，攻撃直後のステップ数が少なくなる に成功した。その一方で，コストの設定法や， 傾向にある。これは，エージェントが，ハブを 環境に応じたパラメータ設定等，耐攻撃性の向 避ける冗長な耐攻撃性を持った経路を学習して 上に関して改良の余地は十分に残されている。 いる為であると考えられる。その一方で，被害 我々を取り巻く環境は，今後ますます複雑・ 102 伊 藤 多様化していくと予想される。システムの開発 においても，ロボットのような人工エージェン トを必要とする場面が増えるであろう。既に， ネットワーク上のパケットフロー問題を強化学 習によって解決しようという研究例も存在す る16)。い ず れ に し て も，現 実 世 界 の ネ ッ ト ワーク上で動作する，自律的かつ知的な人工 エージェントを構築するために，耐攻撃性を持 つ行動学習の必要性は，高まっていくと思われ る。そのような研究の適用対象として，具体的 には，ノードの離脱等が想定されているピュア 型 P2P ネットワーク等において，学習を行い ながら自律的に情報を収集するロボット等応用 が考えられる。今後の研究の発展に期待したい。 参考文献 1 ) 浅田 稔， 「強化学習の実ロボットへの応用とそ の 課 題」，人 工 知 能 学 会 誌，vol. 12，23-28， 1997. 2 ) R. S. Sutton and A. G. Barto (三上，皆川訳)， 「強化学習」，森北出版，2000. 3 ) 加藤 真，山名早人，「Fact of the Web ―30 億 ページのウェブの解析―」 ，第 17 回データ工 学ワークショップ，DEWS2006 3B-i6，2006. 4 ) 梅本堯夫，大山 正， 「心理学史への招待―現代 心理学の背景―」 ，サイエンス社，1994. 5 ) C. J. C. H. Watkins and P. Dayan, “Q-Learning”, Machine Learning，8，272-292，1992. 6 ) 吉田和子，石井 信， 「強化学習における exploration と exploitation の制御」 ，電子情報通信 学 (NC2001-28)，41-48，2001. 7 ) 増田直紀，今野紀雄，「複雑ネットワークの科 友 洋 学」 ，産業図書，2005. 8 ) R. Albert, H. Jeong and A. Barabási, “Error and attack tolerance of complex networks”, Nature, 406, 378-382，2000. 9 ) A. Barabási and R. Albert, “Emergence of scaling in random networks”, Science, 286, 509-512，1999. 10) 伊藤友洋，右田正夫，田尻俊宗， 「強化学習に よる複雑ネットワーク上の行動獲得」，ロボ ティクス・メカトロニクス講演会09 講演論 文集，2A2-D11，2009. 11) 右田正夫，伊藤友洋，田尻俊宗， 「複雑ネット ワークにおける強化学習と獲得行動の耐攻撃 性」 ，第 27 回ロボット学会学術講演会予稿集， RSJ2009AC1L2-02，2009. 12) 右田正夫，伊藤友洋，田尻俊宗， 「スケールフ リー・ネットワーク上での強化学習における 経路選好性について」，ネットワーク生態学シ ンポジウム 2010，1-10，2009. 13) 伊藤友洋，右田正夫，田尻俊宗， 「スケールフ リー・ネットワークにおける耐攻撃性学習」， ネットワーク生態学シンポジウム 2010，1-9， 2009. 14) R. Malhotra (清 水 訳)， 「入 門 IP ル ー テ ィ ン グ」 ，オライリー・ジャパン，2002. 15) T. Unemi, M. Nagayoshi, N. Hirayama, T. Nade, K. Yano and Y. Mashujima, “Evolutionary differentiation of learning abilities a case study on optimism parameter values in Q-learning by a genetic algorithm”, in Artificial Life IV, the MIT Press, 331-336, 1994. 16) T. Horiguchi, K. Hayashi and A. Tretiakov, “Reinforcement learning for congestionavoidance in packet flow”, Physica A, 329-348, 2005.