自律分散協調システム的妄想と群知能クラスタリング

※本文読まなくてもいいので、ぜひ図だけでも見ていってください笑

※このあたりお詳しい人がいたらコメント、補足など大歓迎

目次

0. はじめに

 私のやりたい構想をまとめたブログ(超個体型データセンターにおける群知能クラスタリングの利用構想 - クマガリウムぶろぐ)を実現するためには、群知能クラスタリングと相性が良いのではないかと考えています。そこで、前回のブログ(焼きなまし法と粒子群最適化法の探索挙動を可視化してみた - クマガリウムぶろぐ)では、群知能クラスタリングにつながる最適化アルゴリズムの基本的なところの理解のために可視化を利用して簡単にまとめました。

 今回は、いよいよ(自分の中で)本題の群知能クラスタリングについてまとめていきたいと思います。ここでは、クラスタリング挙動の可視化によって、その特性を簡単にまとめていきます。 それぞれのアルゴリズムごとにブログを書いてもいいくらい奥が深いですが、ここでは群知能クラスタリングでどんなことをしたいのかの全体像をなんとなく伝えるだけにします。

1. 更新版ビジョン

 まず群知能クラスタリングについて、私のイメージを図にすると以下のようになります。何かしらの特徴ベクトルを擬獣化(動物として捉える)、あるいは物理の分野の量子化(仮想粒子として捉える)し、それぞれのアナロジーに基づくルールに基づいた自律駆動によって、全体として意味のある状態を作る(クラスタリングが行われる)というものです。この場合の空間は、特徴空間(例えば、縦軸が身長、横軸が体重のようなもの)ではなく、擬獣化した特徴ベクトルを動き回らせるただの人工的な仮想空間を意味します。この点が個人的に非常に面白いと感じいます。つまり、擬獣間の相互作用や周りの環境変数などをこちらで勝手に定義することができ、まるで神が新しい世界を作るかのようなイメージを持つこともできます(←個人的にそんな妄想をしています)。

f:id:kumagallium:20190807094517p:plain:w500

では、これをわれわれの研究所のビジョンである「超個体型データセンター」にどのように当てはめるかを改めて考えてみます。正直、私自身運用の経験やネットワークなどの知識が不足していて、ゴールの明確なイメージはできていませんので、皆さんの経験に当てはめて補完していただきたい。とりあえず私の漠然としたイメージは以下の図の通り。VMやコンテナなどを擬獣化し、巣となるホスト(あるいは、小規模データセンター)を配置することで、類似したVMが集まると同時にホストの最適配置問題に適用できないか、またユーザを環境変数に取り入れることで、ユーザに近いところで配置の最適化が行われることも実現できないかというものです。また、異常な挙動をする個体を検知することも可能になるのではないかと考えています。さらに、VMの集積率が高くなりすぎる、アクセスが集中しすぎる状況が発生した場合には、環境温度が高くなるというルールを取り入れることで自動的に分散する構造もできるかもしれません。もっとこんな応用の方が面白いなどあれば、ぜひ教えていただきたい。

f:id:kumagallium:20190813131256p:plain:w200

2. 代表的なクラスタリング

 群知能クラスタリングを説明する前に、代表的なクラスタリング手法についても簡単に示しておきます。これら代表的なクラスタリング手法については、正しく説明されている本やサイトがあるので、詳しくはそちらで補完してください。

 クラスタリングは、大きく分けて2種類の手法が存在しますので、ここではその観点でまとめます。

2.1非階層型(K-means法)[1,2]

 K-means法は、非階層型のクラスタリング手法として広く利用されている手法の1つです。この手法は、以下の式を最小化する重心を見つけることで、データ点をk個のクラスタに分割します。

 { \displaystyle
 \sum_{i=0}^{n} \min_{\mu_{j} \in C} \left( || x_i - \mu_j ||^{2} \right)
}


ここで、 { \displaystyle x_i}は各データ点で、nはデータ点の総数を表します。また、 { \displaystyle \mu_j}は、各クラスターの重心です。アルゴリズムは以下の通りです。

  1. k個の重心 { \displaystyle \mu_j}をランダムに配置します。

  2. 各データ点 { \displaystyle x_j}を最も近いクラスタ { \displaystyle j}に割り当てます。

  3. クラスタごとに、以下の式に基づいて重心を求めます。ここで、 { \displaystyle C_j}は各クラスタに含まれるデータ集合、 { \displaystyle N_{C_j}}は各クラスタに含まれるデータ数です。

 { \displaystyle
\mu_j = \frac{1}{N_{C_j}}  \sum_{x_i \in C_j}^{n} x_i
}

 4. クラスタに変化がなくなるまで、2,3を繰り返します。

 K-means法は、クラスタの重心を求めて分割するという簡単なアルゴリズムであり、計算コストが小さいことから多くの場面でよく用いられている。しかし、重心の初期値にクラスタリング結果が依存したクラスタリングになることや、入れ子構造をしているデータの場合にうまくクラスタリングできないカーネルを使うなどの工夫をすればできるが)などの問題がある。

2.2 階層型(樹形図:デンドログラム)[2,3,4]

 デンドログラムは、階層型のクラスタリング手法として広く利用されている手法の1つです。ここでは、Ward法ユークリッド距離を利用した場合のアルゴリズムおよび図を示します。

  1. 全てのデータ点からユークリッド距離で最も近い点で、一つのグループを作ります。

  2. 点が2つ以上集まってグループになった場合は、グループの重心を計算する。

  3. グループ化されたところは重心で考えて、1,2を繰り返して距離が近い順にグループ化を繰り返します。

  4. 上記プロセスによって得られた樹形図から、指定のクラスター数で分割します。あるいは、しきい値を元にクラスタ数を決定します。

 階層型クラスタリング手法は、データの構造を直感的に理解しやすくなっている。非階層型クラスタリング手法で課題であった入れ子構造のデータに対してもうまくクラスタリングでき、初期値の依存性もなく再現性があることが知られている。ところが、全データのデータ感の類似度の計算が必要になるため、データ点が多くなった場合に計算コストが膨大になる。この問題に関しては、K-means方で予めクラスターを大まかにクラスタリングしたあとにデンドログラムを適用することで計算コストを下げることも行われたりします。また、時系列的にデータ点の特徴量が変化した場合、非階層型は重心位置をずらす作業をすればよく前回の結果を利用できる(改良性がある)が、階層型は位置から計算する必要がある(改良性がない)などの問題がある。

f:id:kumagallium:20190809134628p:plain

画像出典元:クラスター分析の手法②(階層クラスター分析) | データ分析基礎知識

2.4 その他

 後述する群知能クラスタリングは、高次元な特徴ベクトルを利用して低次元空間上に類似したものを近い距離に、類似していなものを遠くに配置するという点で、次元圧縮手法とも捉えることができそうです。なので、代表的な次元圧縮手法である、主成分分析(PCA:principal component analysis)や多次元尺度法 (MDS: multi-dimensional scaling) 、t-SNE(t-distributed Stochastic Neighbor Embedding)あたりとの比較も別の機会にまとめたいと思います。

3. 群知能クラスタリング[5]

 上記代表的なクラスタリングの利点、欠点も参考に、群知能クラスタリングと一般的なクラスタリング手法との比較を以下に示しています(群知能クラスタリングにもいろいろありますし、K-meansなども改良されたものもあるので、あくまで私の考えです。鵜呑みにはしないように)。計算コストについては、全体の類似度を計算しない溶けない階層型が一番高く、近傍の類似度の計算でよい群知能クラスタリングは比較的小さく、K-meansが最も小さいと考えられます。特徴ベクトルが時系列的に変わるなどした場合に動的にクラスターを変化できるかどうか(改良性)については、重心を変えるだけで済みそうなK-meansや自律的に個体が移動しそうな群知能(条件設定による)は改良性がありますが、階層型は変わるたびに計算し直す必要がありそうです。再現性については、K-meansは初期値依存性がありますが、階層型にはなく、群知能も設計次第では再現性できそうです。階層性や入れ子構造については、K-meansは考慮できませんが、階層型はもちろんのこと、類似度に基づくクラスタリングを行うう群知能クラスタリングも可能です。群知能を用いたクラスタリングに代表例を次節から説明します。

f:id:kumagallium:20190809144711p:plain:w500

3.1 Ant Colony Clustering Model (ACCM)

3.1.1 概要

  蟻コロニークラスタリングモデル(ACCM)は、蟻が幼虫の仕分けをする行動に基づいたクラスタリングアルゴリズムです。蟻は知覚範囲内に同じ種類の幼虫が存在するかどうかを判断します。もし周りに幼虫がいない、もしくは同じ種類の幼虫があまりいない場合には拾う行為をし、周りに同じ幼虫がいる場合に幼虫を下ろします。この作業を繰り返すことにより、小さなクラスタは縮小、消滅し、大きなクラスタはより大きなものに成長します。

f:id:kumagallium:20190426154759p:plain

3.1.2 クラスタリング挙動の可視化

 もっとも単純な例として、特徴量として1か-1のどちらかを有する幼虫がいた場合に、ランダムに放たれた幼虫を蟻がどのように仕分けるかの挙動を可視化した図が以下の通りです。ここで、左がランダムに配置された初期値、右がクラスタリング挙動を表しています。黄色と紫の幼虫をクラスタリングすることができれば成功ですが、正しくクラスタリングできていることが確認できます。

f:id:kumagallium:20190809113523g:plain

また、上記のアルゴリズムに対して、各アリが短期記憶を持つように変更を加えた場合の挙動が以下の通りです。ここでの記憶する内容は、これまで降ろしてきた場所とその点の密度情報です。つまり、今拾った幼虫に対して、これまで降ろしてきた場所の中で最も適した場所をどこかを検索してその場所に移動する行動を取ります。それにより、まだ訪れていない場所に幼虫が降ろされることを防ぐことができ、より効率よくクラスタリングが行われます。

f:id:kumagallium:20190809113605g:plain

では、より複雑な特徴量を持つデータに対して、どのように動作するのかを見てみます。以下は、Irisデータセットに対してクラスタリングを行った結果です。ランダムに配置された初期値からクラスタリングが行われていることが確認できます。しかし、そもそもIrisデータセットは三種類の花のデータが含まれていますが、setosaはその他の花と特徴が異っていますが、 versicolorとvirginicaは似ている特徴を持っていてクラスタリングが難しいです。なので、実際に以下の図においても、紫(setosa)はクラスタリングがうまくできていますが、他の二種類は完全には分割することはできていないことがわかります。

f:id:kumagallium:20190809114813g:plain

 上記はシンプルなACCMのアルゴリズムを利用して実装しました。しかし、このアルゴリズムの場合、データによっては離れた距離に同じ種類のクラスタが複数生成されてしまうことがあり、その統合が難しくなってしまう場合があるようです。その課題については、拾い上げる確率に情報エントロピーの効果を取り入れる、類似度の計算式を変更する、記憶の仕方を変更する、適応的にαなどのパラメータを変更するなど様々な改善策が提案されてきています。

3.2 Boids(Bird-oid:仮想的な鳥)、あるいはFlock Algorithm

3.2.1 概要

 Flockアルゴリズム[2]は、鳥などの群れの動きを模倣するアルゴリズムを取り入れたアルゴリズムです。鳥が群れを作る行動である1. 同種の群れの近くで留まる(Flock)、2. 同種でない群れから離れる(衝突回避)、3. 最近傍の鳥と速度を合わせる(速度調整)の3つの規則を利用してクラスタリングをします。この規則に従って各個体を動かすことにより種類別のクラスタリングが可能となります。

f:id:kumagallium:20190426153850p:plain

3.2.2 クラスタリング挙動の可視化

 ACCMと同様に、まずもっとも単純な例として、特徴量として1か-1のどちらかを有する鳥がいた場合のクラスタリングの結果を以下に示します。ACCMは、蟻(エージェント)が動き回って幼虫(クラスタリングする対象)をクラスタリングしていましたが、Boidsでは種類の異なる鳥そのものが自律的にクラスタリングされる挙動をしていることが確認できます。

f:id:kumagallium:20190809133624g:plain

 また、Irisデータセットの場合のクラスタリング結果を以下に示します。ACCMと同様に、紫(setosa)はきれいに分離されている一方で、 黄色(versicolor)と緑(virginica)は近いところを飛んでいます。ACCMもBoidsも、Irisに対する最終的なクラスターは2つと判断することになります(多くは、鳥の移動速度を遅くしていき、鳥が止まったときの塊で判断している印象)。

f:id:kumagallium:20190809133644g:plain

3.2.3 入れ子構造のクラスタリング

 入れ子構造のデータに対するクラスタリングについては、あえて節を変えてまとめてみます。まず、以下の特徴をもつ5つのデータを用意します。

これらを描画してみると、入れ子構造のデータをしていることが確認できます。今は、色が分かれているので5種類存在することがわかります。しかし、色がなかった場合、おそらく人間は外側と内側の2種類としてクラスタリングするのではないでしょうか。

f:id:kumagallium:20190809134035p:plain

では、この特徴量に対してK-means法を適応するとどうなるでしょう。外側と内側の2種類をクラスタリングしたいと思い、クラスター数を2として実行した結果が以下のとおりです。K-means法は、重心を探すだけなので入れ子構造をうまく分けてくれませんでした。

f:id:kumagallium:20190809134045p:plain

では、階層型のデンドログラムではどうでしょうか。しきい値の設定によりますが、中と外は別ものであることは判断してくれそうです。(ただし、外側と内側の2種類でうまく切り分けてくれるしきい値は、今回は存在しませんでした)

f:id:kumagallium:20190809134156p:plain

次に、Boidsに適用してみます。クラスタリングの様子は以下の図のとおりです。Boidsの場合、入れ構造であるかどうかは、関係なくデータ点間の類似度(個々では距離)に基づいて動かすため、外側と内側を分離することができます。

f:id:kumagallium:20190809133706g:plain

以下に、最終的に外側と内側が分離されている様子を示しています。

f:id:kumagallium:20190809133859p:plain

このクラスタリング結果を、元の図に適用してみた結果が以下の図です。一部クラスタリングミスはあるものの外側と内側が別物であることが分割できていることが確認できます。

f:id:kumagallium:20190809134218p:plain

3.2.4 補足

 参考文献[5]のアルゴリズム(上記3つのルール)に従って実装しましたが、あまりうまく動いてくれませんでした(どこかミスもあるかもしれない)。なので、後述する変更を加えたアルゴリズムで実装しています。特に、違和感を覚えたのがルール1のFlockの実装でした。参考文献では、類似したk近傍との重心に移動する実装になっていましたが、クラスタリングの終盤になってk匹以上の鳥が重なってしまった場合、現状のクラスターで満足してしまい、別の場所に存在する同じ種類の鳥と合流することをやめてしまいました。そこで、私が行った上記実装は、ルール4として「類似する個体とも一定の距離をとる」という実装も加えてました。これにより、鳥どうしが程よく距離を保てるので、常に同じ種類の鳥を探す行動を取りやすくなりました。

 また、ACCMも同様ですが、Irisのクラスタリングにおいて3種類に分割できなかったことについてどう考えるべきでしょうか。このサイト(クラスタリング (クラスター分析))に興味深いことが書いてあります。

クラスタリングは探索的 (exploratory) なデータ解析手法であって,分割は必ず何らかの主観や視点に基づいているということです.

Irisが3つに分かれているという前情報(主観)があった上で、クラスタリングして2種類だったということは間違いに感じます。似ているものと似てないものを切り分けるだけなら、2種類でいいかもしれません。入れ子構造の結果も、なんとなく外側と内側で分かれそうと人間が判断しますが、デンドログラムの結果のように、一部切れているところで分けて5種類でも問題ないかもしれません。そもそも5つの特徴量で構成されていたデータである訳ですから、正解とは何なのかということです。

4. おわりに

 我々の研究所で掲げている「超個体型データセンター」というコンプトをベースに、自分がワクワクするシステム、を考えた結果、現状ではこのブログにも紹介したような群知能クラスタリングに基づいた自律分散協調システムを実現することでした。というよりむしろ、個人的にアナロジーを利用して最適化やクラスタリングを行う「群知能」自体に非常に興味があり、今後も続けていきたいなと思っています。  クラスタリングと主観の話(3.2.4 補足)を書きましたが、私が示したビジョンにおいても、綺麗なクラスタリングができる必要はないと考えています。綺麗にクラスタリングできないとしても、類似している個体が集まって動いていることはある程度保証できそうですし、それよりも改良性や再現性、階層性などのメリットを持つクラスタリング手法であることが、私のビジョンにとって重要であると考えています。

 全体的に書きたいことが多すぎて、うまくまとまっていないような気もしますが、見ていただいてありがとうございます。(もうちょっと文章もうまくなりたいし、まとめ上手になりたい。。)

5. 参考

  1. https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html

  2. https://www.jstage.jst.go.jp/article/fss/27/0/27_0_55/_pdf

  3. PythonによるDendrogramの作成とlinkageの要素について - Qiita

  4. クラスター分析の手法②(階層クラスター分析) | データ分析基礎知識

  5. 群知能とデータマイニング [ アジス・アブラハム ]

焼きなまし法と粒子群最適化法の探索挙動を可視化してみた

目次

0. はじめに

 以前書いたブログ(超個体型データセンターにおける群知能クラスタリングの利用構想 - クマガリウムぶろぐ)の構想実現を進めるために、最適化アルゴリズムの基本的なところを理解するため、山登り法をはじめ、焼きなまし法や粒子群最適化法の探索挙動を可視化した結果を簡単にまとめてみます。

※このあたりお詳しい人がいたらコメント、補足など大歓迎

1. 最適化アルゴリズム

1.1 山登り法

 山登り法は、現在の解より近傍の解のほうが良い場合(今回は、値が小さい場合)に、現在の解と近傍の解を入れ替えて極値を探索する探索アルゴリズムです[1]。探索手法の中では最も単純かつ代表的な手法ですが、大域的極値以外の局所的極値に陥った場合に抜け出すことが出来ない欠点を持っています。

f:id:kumagallium:20190724111408p:plain:h200

1.2 焼きなまし法

 焼きなまし法(あるいは、シミュレーテッドアニーリング(SA))は、材料工学における焼きなまし(アニーリング)という物理プロセスに着想を得た最適化手法です[2]。アニーリングとは、物質を融解状態になるまで加熱し,徐々に冷却する操作のことであり、このアニーリングにより,分子がエネルギーが最も少ない状態に配列し,結晶構造を形成させることができます。この概念を最適化計算に利用しています。新しい点はランダムに生成され、その新しい点が現在の点より改善される場合は受け入れ、改悪される場合も一定の確率で受け入れます。その確率は、温度が高いほど、また変化量(新しい点と現在の差)が小さいほど受け入れる確率が高くなる関数となっています。それにより、高温では大域的な解の探索、低温では局所的な解の探索(極低温では山登り法と同義)が行えるため、局所的極値に陥ることを避けることができます。 本手法においては、近傍をどのように定義するか、温度スケジュールをどのように定義するかが非常に重要となる。

改悪される場合にも受け入れる確率は、以下のMetropolis法を用いることが多いようです。 { \displaystyle \Delta E}は、現在の解と新しい解との差を表します。

 { \displaystyle
p = \exp \left( - \frac{\Delta E}{T} \right)
}

f:id:kumagallium:20190724111039p:plain

f:id:kumagallium:20190723152702g:plain:w600

シミュレーテッドアニーリング(SA) 画像出典元:Wikipedia

1.3 粒子群最適化(Particle Swarm Optimazation: PSO

 粒子群最適化についての説明は、他のブログ(粒子群最適化(Particle Swarm Optimization: PSO)をGoで実装してみた - Fire Engine)でわかりやすく説明されていますが、一応ここでもしておきます。

  粒子群最適化は、餌を探す鳥の群れなどの行動に着想を得た最適化手法です。以下の図のように、各鳥が今までに得た最良な場所(パーソナルベスト { \displaystyle \vec{p_i} (t)})、他の鳥が得た最良の場所(グローバルベスト { \displaystyle \vec{g_i} (t)})、現在の慣性因子を考慮して次に向かうべき場所を決定します。この条件で移動を繰り返すことによって、最適な位置に鳥たちが集まり、その点が最適解となります。 移動ルールにおいて重要な移動速度の式は、以下のとおりです。 { \displaystyle I}は、慣性係数と呼ばれる定数で、1より小さい値を指定します。 { \displaystyle A_g}および { \displaystyle A_p}は加速度係数と呼ばれる値で、1に近い値を指定します[3]。

 { \displaystyle
\vec{v_i} (t+1) =I \vec{v_i} (t) + A_g \left( \vec{g}(t) - \vec{x_i} (t) \right) \times rand[0,1] + A_p \left( \vec{p_i} (t) - \vec{x_i} (t) \right) \times rand[0,1]
}


f:id:kumagallium:20190507121109p:plain:w400

2 ベンチマークを用いた探索挙動の可視化

 最適化アルゴリズムベンチマークとしては、ここ(python: ベンチマーク関数お試しコード - Qiita[4])が参考になりました。

2.1 Sphere function

 Sphere functionは、以下の式に示すように基本的な関数です。

 { \displaystyle
f(x_1 \cdots x_n) = \sum_{i=1}^{n} x_i^{2}
}

山登り法 大域的極値以外に局所的極値が存在しないため、図のように山登り法でも大域的極値を得ることができました。 f:id:kumagallium:20190723150335g:plain

焼きなまし法 焼きなまし法も、もちろん山登り法と同様に最適解を得ることができました。

f:id:kumagallium:20190724103810g:plain

粒子群最適化 粒子群最適化は、グローバルベストとして最適解を共有することができるため、上記手法よりも比較的少ない探索時間で最適解を得ることができました。 f:id:kumagallium:20190719152059g:plain

2.2 Ackley function

Ackley functionは多峰性関数で、大域的極値の周辺に多数の局所的極値を有しています。

 { \displaystyle
f(x_1 \cdots x_n) = 20 - 20 \exp \left(-0.2 \sqrt{\frac{1}{n} \sum_{i=1}^{n} x_i^{2} } \right) + e - \exp \left( \frac{1}{n} \sum_{i=1}^{n} \cos(2 \pi x_i)  \right)
}

山登り法 近傍の最適解を探索する山登り法では、多峰性のある関数における大域的極値を得ることができませんでした。初期値に近いところにある局所的極値に収束してしまいました。

f:id:kumagallium:20190724095053g:plain

焼きなまし法  焼きなまし法は、改悪される解を許容することで大域的探索できるようにしているため、図に示すように局所的極値に留まることなく、大域的極値に向かって収束できていることが確認できました。 f:id:kumagallium:20190724103501g:plain

粒子群最適化  Ackley関数における大域的極値は、その周辺と比べて極端に小さい値であるため、グローバルベストと各点の値の差が大きくなりやすく、すべての点が急激に大域的極値に収束すしていることが確認できました。

f:id:kumagallium:20190724095204g:plain

2.3 Rastrigin function

 Rastrigin functionは多峰性関数で、非常に多くの局所解を有しています。また、図に示すようにAckley関数と比較すると、大域的に比較的緩やかなお椀状をしていることが確認できます。

 { \displaystyle
f(x_1 \cdots x_n) = 20 - 20 \exp \left(-0.2 \sqrt{\frac{1}{n} \sum_{i=1}^{n} x_i^{2} } \right) + e - \exp \left( \frac{1}{n} \sum_{i=1}^{n} \cos(2 \pi x_i)  \right)
}

山登り法  Ackley関数の場合と同様に、多峰性関数であるため局所的極値に陥る結果となりました。

f:id:kumagallium:20190724095541g:plain

焼きなまし法  非常に緩やに温度を下げる必要があるものの、局所的極値に陥りつつも留まることはなく、大域的極値に収束していることが確認できました。焼きなまし法は、十分に高い温度から十分に緩やかな徐冷をおこなうことで多くの問題を解くことができることがわかりました。ただし、緩やかな徐冷が必要であるため、今回の粒子群最適化などと比べると探索時間が長時間必要でした。

f:id:kumagallium:20190724103608g:plain

粒子群最適化  粒子群最適化は、探索空間上に十分な粒子がある場合においては、多峰性かそうでないかのは比較的関係なく、大域的極値の周辺に短い探索時間で収束することがわかりました。ただし、Rastrigin関数はAckley関数よりも大域的に緩やかなお椀状であるため、大域的極値周辺の局所的極値も十分に小さな値であり、グローベルベストとの差という駆動力が小さくなるため、慣性力による移動が支配的になり大域的極値周辺で解が揺らぐことも確認できました。

f:id:kumagallium:20190719152433g:plain

2.3 Himmelblau's function

 図に示すように、Himmelblau's functionは多峰性関数で、4つの極値を有しています。

 { \displaystyle
f(x, y) = (x^2 + y - 11)^2 + (x + y^2 - 7)^2
}

山登り法 Himmelblau関数は、多峰性関数であるもののその全てが同じ値となる大域的極値と考えることができるため、図に示すようにほぼ問題なく4点に収束していることが確認できました。

f:id:kumagallium:20190724104234g:plain

焼きなまし法  焼きなまし法も、山登り法と同様に4点に収束していることが確認できます。

f:id:kumagallium:20190724104321g:plain

粒子群最適化  一方で、粒子群最適化では、基本的にグローバルベストに向かって移動する手法なので、大域的極値が複数存在する場合、初期値に依存して収束する点が決まることが確認できました。また、点によっては自分が知っているローカルベストが最適であると知って、揺らいでいる様子も図から確認できます。

f:id:kumagallium:20190724104409g:plain

3. おわりに

 最適化アルゴリズムの基本となる山登り法をはじめ、大域的極値が探索できる焼きなまし法や粒子群最適化の基本的な概要と実装、可視化によるそれぞれの挙動の違いを簡単に確認しました。また、それぞれの手法に得意不得意があることも確認できました。例えば焼きなまし法は、多くの関数に適用可能である一方で、パラメータ設定が重要で且つ探索時間が長くかかりました。ただしこの課題についても、現在までに多くの研究が行われていますのでそのあたりも抑えておく必要がありそうです[5]。また、粒子群最適化における、大域的極値と局所的極値との差が小さい場合に収束しない課題についても、多くの研究がされています。さらには、焼き鈍し法と粒子群最適化とを組み合わせた手法[6,7]なども存在するので、そのあたりの調査もまとめたいところですね。

4. 参考

  1. 山登り法 - Wikipedia
  2. Simulated annealing - Wikipedia
  3. 進化計算アルゴリズム入門 生物の行動科学から導く最適解
  4. python: ベンチマーク関数お試しコード - Qiita
  5. [Adaptive simulated annealing - Wikipedia
  6. A New Hybrid Algorithm of Particle Swarm Optimization | SpringerLink
  7. Hybrid PSO-SA Type Algorithms for Multimodal Function Optimization and Reducing Energy Consumption in Embedded Systems

論文ざっくり和訳:Look Who’s Talking: Discovering Dependencies between Virtual Machines Using CPU Utilization(2010)

 私は、物理サーバやVMなどをメトリック情報などの時系列データを利用して特徴ベクトル化し、その特徴ベクトルに群知能に基づいたクラスタリングを適用することで、異常検知・可視化を実現する研究を進めています(詳しくはこちら:超個体型データセンターにおける群知能クラスタリングの利用構想 - クマガリウムぶろぐ)。

 そこで、少し古い論文ではありますが、私のやりたい研究に関連した研究論文を自分が理解できる程度にざっくり和訳したものをメモとして残しておきます。(一部理解できていないところは直訳的になっていますので、詳しくは元論文を参照してください)

 対象とする問題の設定やそれに対するシンプルな手法による解決策、何を評価するかなど、私自身の研究をまとめていく上で参考になりました。今後は、本研究に関連する最新論文の調査を進め、随時ブログにメモしていきたいと思います。

※以下、論文の和訳です。

Look Who’s Talking: Discovering Dependencies between Virtual Machines Using CPU Utilization

URL: http://users.cis.fiu.edu/~lhu/doc/look.pdf 
著者: Renuka Apte, Liting Hu, Karsten Schwan, Arpan Ghosh 

目次

0. 概要

 データセンターやクラウドでよく見られる問題は、それらを実現する一連の仮想マシンVM)に対して外部ユーザーが提供、または実行しているサービスのマッピングに関する知識が不足していることである。そのため、特定のサービスで消費されるリソースを最小限に抑えたり、データセンターのマシンで消費される電力を削減したりするなど、プロバイダの目標を達成するためにVMの集合を管理することは困難である。本論文では、VM間の依存関係を特定するための、「LWT(Look Who's Talking)」という一連の方法とフレームワークを紹介する。 LWTでは、サービス自体の変更、ミドルウェアオペレーティングシステムが不要であり、代わりに現在のマシンの使用に関するハイパーバイザーレベルの情報への特権アクセスを使用して管理VMで動作する。 LWTの現在の実装は、小規模プロトタイプデータセンターで実行されているXenハイパーバイザーに統合されている。そのため、実験的測定により、平均97.15%の正確さでVM間の依存関係を効率的に識別できる。また、アプリケーションやワークロードへの影響、およびシステムパフォーマンスへの影響を最小限に抑えている。

1.  背景

  「非常に小さな変化が、非常に大きな結果をもたらす」。この「バタフライ効果」の有名なキャッチフレーズは、データセンターの管理者が直面しなければならないシステムにおける固有の複雑さによるジレンマを適切に捉えている。クラウドにおける仮想化は、サーバーの統合、ワークロードバランス、高可用性、マルチテナンシー、障害分離などの利点により、ますます一般的になっている。最近、シスコ、EMC、およびVMwareは、仮想化、ネットワーキング、コンピューティング、ストレージ、セキュリティ、および管理の各テクノロジをエンドツーエンドのベンダの説明責任とを完全に統合したインフラストラクチャパッケージを提供するための提携を発表した。このようなソリューションにより、顧客は新しい仮想クラウドデータセンターをプロビジョニングしたり、既存の仮想クラウドデータセンターを移動したりすることで、数分以内に多数のVMで構成されるワークロードを実行できる。

通常、このようなクラウドデータセンターで実行されているアプリケーションは、複数のVMにまたがって実行されている多数の連携コンポーネントで構成されている。図1は、3台の物理マシンに配置された多層アプリケーションを示している。たとえば、アプリケーションサーバーおよびデータベースサーバーバックエンドのサービスを利用するHTTPサーバーフロントエンドを持つ多層アプリケーションがある。一般にVMアンサンブルと呼ばれるこれらのVMは、多数のホストマシンに分散している可能性がある。

f:id:kumagallium:20190717093440p:plain

図1 VM依存性を示している多層アプリケーション

 

 VMアンサンブル内のVM間には複数の依存関係(特に、1つのVMが別のVMによって使用されるサービスを提供するため、2つのVMが通信する「いわゆる利用」の関係によって定義されるもの)がある。管理者がデータセンターを正常に管理(リソースの最適割り当て 、ワークロードのバランスと移行 、サービスレベル契約の遵守 、重大な障害の検出と軽減)するために VM間に存在する依存関係を識別できることが重要である。これは、どのVMが依存しているかを知ることによって、管理者が次のリストまたはこれに限定されないより高度な決定を下すことができるためである。

仮想マシンを別の物理マシンに移行するかどうか:2つの仮想マシンが相互に依存している場合は、物理的に離れた別の物理マシンが空いていても、同じ物理マシンに配置することをお勧めする。
•あるVMからリソースを放棄すると別の依存サービスに影響を与える可能性があるかどうか:リソースの割り当てと管理をよりインテリジェントにすることができる。 VMがオーバープロビジョニングされているように見えるかもしれないが、このVMのサービスは複数の依存VMによって使用される可能性がある。
•障害の原因の特定:管理システムは依存関係の知識に基づいて因果関係をより適切に判断し、障害がどのように発生する可能性があるかを判断できる。

 本論文では、仮想マシン間の依存関係を識別するための一連のメソッドとフレームワークを紹介する。 LWTは、アプリケーションやシステムコードを計測したり、変更したりすることなく実現する。また、 監視対象のゲストOS、ランタイム環境、アプリケーション、またはサービスから独立している。これは、管理者からの必要な入力を最小限にし、最小限のパフォーマンスペナルティをももたらす。

 LWTは、クライアントVMがサーバーに要求を出しサーバーが何らかの計算を実行して応答する、要求/応答タイプの対話を行う多層アプリケーションに適用される。クライアントのワークロードが重いほど要求が高まる。その結果、クライアントのCPU使用率が急上昇するのとほぼ同時に、サーバーのCPU使用率が急上昇することが予想される。 そのため、VMのCPU使用率をモデル化し、これらのモデル間の類似性に基づいてそれらをクラスタ化することで、それらの間の依存関係を高い精度で予測できる。

 LWTは、モニタリング、モデリング、およびクラスタリングの3つの段階で構成されている。まずxentopベースのモニターを使用して、VMごとのCPU使用率を記録および抽出する。次に、VMごとに自己回帰(AR)モデルを推定する。最後に、ARモデルをクラスタ化するためにK-meansを使用する。自己回帰モデルは、系列における1つ以上の前の値に対する現在値の単純な線形回帰である。通信中の仮想マシン群が同様のスパイク(急増)を示す場合、ARモデルは「近い」と予想される。したがってK-meansは、相互依存しているVMが1つのクラスタ内に収まるようなクラスタを作り出すことができる。また、ランダムに選択されたいくつかのVMを明示的に乱すことで、結果をさらに改善することができる。図2に、LWTシステム図を示す。

f:id:kumagallium:20190717093417p:plain

図2 LWTシステムの概略図

 

 現在のLWTの実装は、5台の物理マシンと31台のVMで構成される小規模システムで実行されているXenハイパーバイザーに統合されている。 VMは、RUBiS、Hadoop、およびIperfの3つの異なるアプリケーションのインスタンスを実行する。それにより、トータルの精度は97.15%、真陽性率は91.67%、そして真陰性は99.08%で依存性を識別することができる。

2. 関連研究

 関連する研究を4つのカテゴリ(手動、トレースベース、ミドルウェアベース、および摂動ベースの手法)に分類する。

 手動技術:

 Mercury MAMやMicrosoft MOMのような管理システムは、トポロジマップを維持することによって依存関係モデルを指定するためのサポートをアプリケーション設計者に提供する。ただし、この方法では大規模システムにおけるアプリケーションの動的な性質に追いつくためにかなりの手作業が必要であり、多くの場合同じベンダーの特定のアプリケーションに限定される。

 トレースベースの技術:

 Project5とWAP5 [17]は、ブラックボックスネットワークのトレースから因果パスを推論する。送信されたタイムスタンプと受信されたタイムスタンプの両方と共に各ホストでメッセージを記録する。そして、Project5はオフラインのネスティングと畳み込みアルゴリズムを使って因果関係を推論し、WAP5はメッセージリンクアルゴリズムを使ってタイムラインと因果ツリーを生成する。これらのアプローチは、個々のアプリケーションのデバッグとプロファイリングを対象としているという点で我々の研究とは異なる。したがって、主な関心事は、どの着信パケットがどの発信パケットをトリガーしたかを解決することである。一方、我々はリアルタイムにVM上で実行されている多層アプリケーションのサービスの依存関係を発見することに焦点を当てている。

 Magpieは、OSレベルのイベント追跡に基づいて因果経路を再構築する。 Windows OSに組み込まれているWindows用のイベントトレースを使用して、スレッドレベルのCPUおよびディスク使用量の情報を収集することにより、現実的な動作条件下でシステムのワークロードを自動的に抽出できる。ただしMagpieでは、トレースされた情報を要求パターンにまとめるために、アプリケーションの専門家によって書かれたアプリケーション固有のイベントスキーマが必要となる

 Orionは、異なるサービス間のメッセージの時間相関を使用して、エンタープライズアプリケーションの依存関係を発見した。 「時間相関」とは、サービスAがサービスBに依存している場合、AとBの間のメッセージ遅延が遅延分布における「特徴的な」急上昇を示す「特徴的な」値が似ていることを意味する。同様に、Sherlockは推論グラフを計算する。ただし、この規則は仮想マシンプラットフォームでは失敗する可能性がある。

 Gaoらは、リソースを監視し、監視されたパラメータ間のペアワイズ相関を追跡して確率モデルを作成し、観測データがモデルに準拠していない場合はアラームを発生させることにより分散システムの問題を検出する。

 ミドルウェアベースの技法:

 Pinpointは、各J2EE呼び出しに一意の要求IDをタグ付けすることによって、分散システムを通過するクライアント要求のエンドツーエンドのトレースを収集する。彼らのアプローチの鍵は、これらのトレース(経路)を使用して意味のある自動統計分析を可能にすることであり、例えば経路異常および待ち時間プロファイルを使用してシステム障害を検出することができる。 Pinpointでは、すべての分散アプリケーションを適切なロギング機能を備えた同種のプラットフォームで実行する必要があるが、実際の大規模エンタープライズデータセンターは、さまざまなベンダーの多数のオペレーティングシステムを使用しており、ほぼ不均一である。

 摂動ベースのテクニック:

 Bagchi らは、フォルトインジェクションを使用して積極的なアプローチをとることでリソースの依存関係を明らかにしている。ブラウンらは、特定のデータベーステーブルをロックして特定のコンポーネントからのクエリを拒否するなど、システムの応答を監視しながらシステムコンポーネントを明示的に乱すことで、ドメイン間の依存関係を識別する。正確性を向上させるために摂動を使用するが、依存関係を見つける唯一の手段としてそれを当てにすることはしない。 Pipは、アプリケーションを修正または少なくとも再コンパイルすることで、因果経路を抽出するための高い精度を得ることができる。

3. LWTの設計

 前述の目標に達成するために、我々のアルゴリズムは次の特性を持つ必要がある。アプリケーションやシステムにとらわれず、邪魔にならず、スケーラブルで、コンポーネントの故障や設定変更に抵抗し、そして計算上効率的であるべきである。

 

3.1 直感と概要

 要求応答型のアーキテクチャでは、クライアントの作業負荷が増加すると、一般にそれが依存しているサーバーに対してより多くの要求が行われ、サーバーの作業負荷も増加する。したがって図3に示すように、この増加に比例して、クライアントとサーバーの両方のCPU使用率が同時にスパイクすることが予想される。各スパイクの時間的な類似性に基づいてVMクラスタ化する。

 各VMのCPU使用率を時系列信号としてモデル化し、この情報を使用してVMを分類する。アルゴリズムは3つのステップ「監視、モデリング、そしてクラスタリング」 から成る。さらに、結果を改善するためにランダムに選択されたVMのアクティブ摂動を使用する。

f:id:kumagallium:20190717093626p:plain

図3 依存関係にあるVM間のCPU利用率における同じスパイク

3.2 モニタリング

 VMは、アプリケーション全体を実行する、あるいはWebサーバーのようなサービス(アプリケーションのコンポーネント)を実行すると想定している。最近のほとんどの仮想化データセンターにおける展開モデルを考えると、これは合理的な仮定である。監視モジュールは、xentopを使用してホストごとのVMのリソース使用率を記録する。記録された情報は、VMごとのCPU利用率の詳細を抽出するために解析される。

3.2.1 サンプリング周期

 サンプリング周期が短すぎると、アルゴリズムによって実行される計算量が増加する。また、読み取り値にノイズが載ってしまう(ノイズの影響を過大評価してしまう)可能性もある。同様に、サンプリング期間が非常に長いと、重要なスパイクを見逃す可能性がある。

 少数のVMには10ミリ秒から7秒のサンプリング周期を使用し、結果を分析するために単純な相関を使用した。次に、相関係数としてカットオフCを選択した。これ以上の相関係数を持つVMは依存型とマークされる。3秒のサンプリング周期に対する一例が図4に示されており、それはC = 0.9を使用している。図に示すように、Apache Webサーバー、Tomcatサーバー、MySQLサーバー、おせよびRUBiSクライアントはしきい値を超える相関を示しているため、依存関係がある。同様に、Iperfクライアントとサーバーの間には依存関係があるが、CPUベンチマークであるNbenchは他のVMと依存していない。これらの実験を通じて、1秒のサンプリング周期が最適な選択であることが確認できた。

f:id:kumagallium:20190717093219p:plain

図4 サンプリング周期=3病におけるVMの相互相関

3.2.2 サンプルサイズ

 監視対象のVMの数を増やすと、必要なサンプルサイズは徐々に増加する。現在の実装では、31個のVMを使用して、サンプルサイズ300(サンプリング周期1秒)で十分であると経験的に判断した。さらに、この手法をリアルタイム環境で使用するため、継続的に監視して300秒以上の依存関係を計算できる。そして、システムに存在する現在の依存関係を改善し続けることができる。このアプローチは、VMが動的に作成、または破棄される可能性がある環境に対応できるだけでなく、各反復で見つかった依存関係を実証または無効化することもできる。これはまたアプローチがサンプルサイズにあまり敏感ではなくなることにもなる。

3.2.3 アクティブ摂動

 摂動(乱すこと)とは、サービスの提供能力に影響を与えるために、利用可能なCPUのタイムスライスなどのVMのいくつかの要素を意図的に変更することである。具体的には、ホストシステムにアイドル状態のCPUサイクルがある場合でも、ドメインで使用できるCPUの量に上限を設定する。これはXenでxmコマンドを使用して、VMに付与できる「クレジット」の量を変更することで行う。仮想マシンを乱す(摂動)ことで、依存する仮想マシンのCPU使用率が変化することが予想される。たとえば、VMの上限を引き下げることで、要求を処理する容量を抑制する。したがって、そのCPU使用率の低下は、サービスを受けるのを待っている依存VMに伝播される。ランダムに選択されたVMのサブセットでこの上限を定期的に変更することで、サンプルセットに時間依存のスパイクを追加する。

3.3 自己回帰モデリング

時系列データセットXのの自己回帰モデルは、pこの前の値の荷重和で与えられる。ここで、pはモデルの次数である。モデルは以下の式で与えられる。

 

ここで、φpはモデルのパラメータ、cは定数、εtはホワイトノイズである。各VMの時系列CPU使用量をこのようなモデルに合わせることで、時間内の1つのスパイクが以前のスパイクによってどのように影響されるかを把握できる。このモデルを予測に使用しているわけではないが、観察結果を効果的にまとめることができる。 ARモデリングはホストごとに実行でき、特定のオーダーに対して有限の時間がかかる。

3.3.1 自己回帰モデルのオーダー

 この文脈では、モデルの次数を選択することが、どれだけ要約したいのかという選択を意味する。このモデルが予測に使用されることを想定していないため、次数を選択するために予測誤差または同様の手法を使用しない。また、この問題はサンプルサイズの選択の問題と似ている。システムがより複雑になるにつれて、pの値は着実に増加すると予想される。ただし、pが大きすぎると過剰適合になる。この傾向は図5に確認することができる。異なるpに対する予測精度の依存性を示している。

 実験的な設定の大きさでは、40〜50の範囲のオーダーがうまくいくことがわかった。

f:id:kumagallium:20190717093216p:plain

図5 自己回帰モデルのオーダーを変化させたときの精度

3.4 クラスタリング

 最後のステップは、ARモデル間の距離に基づいてクラスタリングを使用し、依存VMをグループ化することである。ユークリッド距離を使用するため、履歴内の特定のサンプルについて同様の係数を持つモデル(時間内のスパイクに効果的に対応する)が近くなる。クラスタリングにはK-meansを使用する。
 K-meansは、データを複数のクラスター= Kに分割する。K-meansは、データに対してK個の中心または重心を選択することによってクラスタリングを行う。アルゴリズムを繰り返すたびに、クラスタ内の距離に対応するメトリックを減らし、クラスタ間の距離に対応するメトリックを増やすことによって、中心のポイントが改善される。 このKの値は管理者によって提供される。
 この最後のステップは集中的に実行する必要があるが、K-meansは非常に効率的である。 1000個のサンプルと500個の実数値属性(これはオーダ500のARモデルを持つ1000個のVMに対応する)を持つデータセットの場合、K-meansは数秒以内に計算を終了する。

4. 実験設定

 我々のテストベッドは、5基のデュアルコアIntel Xeon 5150プロセッサを搭載したDell PowerEdge 1950コンピュートノード、4GBのメモリ、および80GBのハードドライブをギガビットネットワークで接続したものである。 31台の仮想マシンを持つクラスターをシミュレートした。各仮想マシンは512 MBのRAMを使用するように構成され、各ホストの仮想マシンモニターとしてXen 3.1.2を使用する。

 使用されるアプリケーションとワークロードは以下のとおりである。

 RUBiS は、オークションサイトの中核機能である販売、閲覧、入札を実行する、よく知られたeBayのようなベンチマークである。私たちは、サーブレットベースの4ノード構成のRUBiSを使用する。これは、ApacheTomcatおよびMySQLサーバー、4台のクライアントノードで構成されている。したがって、1つのRUBiSインスタンスは4つのVMで構成されている。 RUBiSによって提供されるさまざまな既存ワークロードを、そのさまざまなインスタンスに対して使用する。

 Hadoop MapReduceは、膨大な量のデータを大量の計算ノード上で並列に迅速に処理するアプリケーションを作成するためのプログラミングモデルおよびソフトウェアフレームワークである。 3つのVM、1つのマスター、3つの作業ノードを使用し、Hadoopの単一インスタンスを作成する(VMの1つはマスターとワークノードの両方)。 Hadoopインスタンス用のワークロードを作成するため、Hadoopで提供されている3つの既存のサンプルプログラム、wordcount、randomwriter、およびsortを使用する。

 Iperfは、TCPおよびUDPデータストリームを作成し、それらを伝送しているネットワークのスループットを測定できる、一般的に使用されているネットワークテストツールである。クライアントとサーバーの機能をベースにした2ノード構成のIperfを使用し、両端間のスループットを測する。 1つのIperfインスタンスは2つのVMで構成されている。 ARモデルとKMeansの計算にはMATLABを使用する。

 

5. 結果

5.1 パフォーマンス評価

 結果の概要を図5に示す。これは、ARモデルの次数を変化させたときの依存関係の予測精度、および真陽性、陰性の内訳を示している。セクション3.3.1で述べたように、過度に大きいオーダーの値は、オーバーフィットのために精度を低下させ始めることがわかる。また、この方法は特定の順序の値に対して極端に敏感ではないこともわかる。表1は、RUBiSとHadoopを個別に使用した場合と、合計31台のVM(3つのAll Workload)に対して3つのHadoopインスタンス、4つのRUBiSインスタンス、2つのIperfインスタンスを実行した場合の組み合わせの結果の内訳を示している。摂動を使用しなくても、RUBiS VM内の依存関係を100%の精度で識別できることがわかる。これは、RUBiSのようにコンポーネントVM間で多くの連携を必要とするアプリケーションが、我々のアプローチに特に適しているからである。また、依存関係を考慮することによって行われるプロビジョニング決定から最も利益を得るアプリケーションの種類である。 Hadoopでもこのアプローチがうまく機能する理由は、比較的直感的ではない。 Hadoopマスターはワークロードを分割し、タスクをワーカー(マッパーとリデューサー)に割り当てる。この時点の後、マッパーおよびリデューサーはファイルを介して通信する、すなわちマッパーは中間結果をファイルに格納し、それらの位置をマスターに通信する。マスターはこれらの場所についてレデューサーに順番に通知して、それらの場所を読み取って処理できるようにする。このセットアップでは、Hadoopインスタンスの3つのVMすべてがワーカーである(そのうちの1つはマスターとワーカーの両方です)。その結果、CPU使用率にはかなりの相関関係があり、図6で確認できる。この図は、Hadoopの2つのインスタンスのCPU使用率の時系列をプロットしている。最初のインスタンスに属する左側の列は、右側の列とは大幅に異なるパターンを示している。図7は、精度に対する摂動の影響を示している。セクション3.2.3で述べたように、サービス能力を定期的に変更することによってVMを摂動させると、依存VMのCPU使用率において顕著なスパイクが発生する。摂動により、Hadoopワークロードの精度は全体で25%上昇する(真陽性の場合は33.33%、真陰性の場合は23.23%)。同様に、すべてのワークロードの場合、精度の向上は約2.5%である。この一見したところわずかな増加は、摂動を使用せずに96.33%の真陰性がすでに識別されているという事実によるものである。

f:id:kumagallium:20190717093853p:plain

図6 HadoopインスタンスのCPU利用の時系列

 

表1 依存性を識別した結果

f:id:kumagallium:20190717093203p:plain

 

f:id:kumagallium:20190717093156p:plain

図7 予測精度における摂動の効果

 

 2つのアプリケーションインスタンスのARモデルを、時系列で前の値の係数をプロットすることによって図8に示す。同様の係数を持つモデルは、それらが時間内に同様のスパイクを示したことを意味する。同じアプリケーションインスタンスからのモデルは、他のモデルよりも係数が類似していることがわかる。その結果、それらは一緒にクラスタ化される。図9は、RUBiS VMの2次、3次、4次の係数に対する散布図を示している。従属VM(同じ色で表示)は互いに近い距離に位置していることがわかる。

f:id:kumagallium:20190717093941p:plain

図8 (a)RubiS モデル、(b)Iperfモデルの回帰モデル

f:id:kumagallium:20190717094016p:plain

図9 モデルの可視化

5.2 スケーラビリティおよび時間計算量

 アルゴリズムの時間計算量は3つの要素(VMの数N、次数pの選択、サンプルサイズWの選択)に依存する。特定のシステムにアルゴリズムを配置する前にpとWを選択するため、それらの効果を一定 (有限時間)にすることができる。 ARモデルを見つける最初のステップの計算量は、Nで線形である。モデルはホストごとに計算され、クラスタリングフェーズのために中央マシンに送信される。 k-meansの複雑度はΩ(N)である。この手順は集中的に実行されるが、1000個のサンプルと500個の実数値属性を持つデータセット(500のARモデルを持つ1000個のVMに対応)では、K-meansは数秒以内に計算を終了する。したがって、このアルゴリズムは、何千ものVMのデータセンターに容易に拡張できる。これをさらに確立するために、既存の使用率をコピーすることによって、1200 VMのCPU使用率をシミュレートした。次数p = 100を使用して、この人工のデータセットに対してアルゴリズムを実行した。 ARモデルを一元的に計算したにもかかわらず、アルゴリズムの合計実行時間は、1GBのRAMを搭載した2GHzで動作するIntel core2デュオマシンでわずか1.5分であった。

6. まとめと今後の課題

 本論文では、VM間の依存関係を識別するための一連のメソッドとフレームワークを紹介した。この方法は、邪魔にならず、アプリケーションにとらわれず、リアルタイムでスケーラブルであり、VMを変更することなく稼働中のデータセンターに簡単に展開できる。個々のVMのCPU使用率について自己回帰モデルを推定し、どのモデルが類似しているかに基づいてそれらをクラスタ化する。 LWTの現在の実装は、小規模プロトタイプデータセンターで実行されているXenハイパーバイザーに統合されている。実験測定により、VM間の依存性を平均97.15%の正解率で効果的に識別できる。この作業でまだ検討されていない側面の1つは、多数のVMが単一のVMに依存している場合にシステムがどのように反応するかということである。この場合、特徴的なスパイクがはっきりとは見えない。また、ARモデルの次数やサンプルサイズなどのパラメータの探索を自動化したいと考えている。

超個体型データセンターにおける群知能クラスタリングの利用構想

※提案手法は、まだジャストアイデアですので、コメントやアドバイス等大歓迎です。
※群知能についても勉強中ですので、こちらもコメント大歓迎です。

目次

0. スライド

 本記事は、以下のスライドについて説明します。 speakerdeck.com

1. 背景

 私の所属するさくらインターネット研究所では、研究所全体のビジョン(超個体型データセンターを目指す当研究所のビジョン – さくらインターネット研究所)を掲げています。是非ブログを読んでほしいところですが、本記事でも簡単に私なりの解釈でまとめてみます。

 一言でいうと「超個体型データセンター」です。もう少し詳しく説明してみます。現在はデータセンターに巨大なコンピューティングリソースが存在していますが、今後はレイテンシ/セキュリティ/コスト等の要件から、あらゆる場所や社会、組織に分散して溶け込んでいくことが予想されます。ただし、ただの分散ではなく"自律的に"分散あるいは"有機的に"結合するハイブリッド構造をとると考えています。そして、その自律的なハイブリッド構造によって現場最適化あるいは全体最適化を実現し、我々をよりインテリジェンスに支えてくれるデータセンター、それが「超個体型データセンター」です。 超個体とはなにかについては、Wikipedia超個体 - Wikipedia)を読んでいただくと、なんとなくイメージしていただけるかと思います。

f:id:kumagallium:20190426141220p:plain:w600
さくらインターネット研究所のコンセプト

2. アプローチ

 私自身は、インフラエンジニアやネットワークエンジニアではなく、機械学習を使った異常検知などを研究する者です。その観点から、コンセプトを実現するためにできるアプローチを考えてみます。

 「各個体が自律的に機能しながらも、局所的かつ全体的に統率されている」という超個体的イメージは、私の中で機械学習における「逐次学習する特徴ベクトル」クラスタリングの関係性のイメージと一致しています。何らかのノード(ホスト、VM、コンテナ、プロセスなど)を逐次学習によって動的な特徴ベクトルを形成し、各ノードを動的にクラスタリングすることができれば、(特徴ベクトルの定義によりますが、)クラスタリングを利用した異常検知やルーティングの最適化、(キャッシュ)サーバの最適配置など超個体型データセンターの実現に向けた要素研究につながりそうです。

 そのため私の研究テーマは、「(逐次学習する)特徴ベクトル」クラスタリングに設定しています。特徴ベクトルについては、また別の記事にまとめていきたいと思いますが、本記事ではクラスタリングについて紹介します。特に私は、超個体と親和性が高そうな「群知能を用いたクラスタリング」について調査、研究を進めています。本記事では、群知能の簡単な説明と新しい群知能のアイデアを紹介します。

f:id:kumagallium:20190426142315p:plain:w600
コンセプトに対する私の解釈

3. 群知能

3.1 群知能とは

 群知能とは、個体間の局所的で簡単なやり取りを通し、全体が高度な動きをする現象を模倣した人工知能技術です。こちらも詳しくは、Wikipedia群知能 - Wikipedia)を御覧ください。
 本記事では、群知能の代表例として蟻コロニー最適化(ACO)と粒子群最適化(PSO)を簡単に説明します。

3.1.1 蟻コロニー最適化(ACO

 蟻コロニー最適化(ACO)は、蟻の採餌行動に着想を得た最適化手法です。蟻はランダムに巣の周りを探索し、地面にフェロモンを残します。そして餌を見つけるとフェロモン量を補強しながら巣に戻ります。他の蟻はフェロモンが強い道を選ぶため、フェロモンを補強する行動をとります。ただし、フェロモンは一定時間で蒸発します。これら一連の動作を繰り返すことにより、余計な道は消えて餌までの最短距離が自動的に選択されます。  ACOは、最適経路が求まるアルゴリズムであるため、すでに通信ネットワークへの適用研究も行われています[1]。

f:id:kumagallium:20190426153939p:plain:w300
蟻コロニー最適化(ACO) 画像出典元:Wikipedia

3.1.2 粒子群最適化(PSO

 粒子群最適化(PSO)[2]は、餌を探す鳥の群れなどの行動に着想を得た最適化手法です。ACOでは、蟻が最適な経路を作るアルゴリズムでしたが、PSOは個々の鳥そのものが解となります。以下の図のように、各鳥が今までに得た最良な場所、他の鳥が得た最良の場所、現在の慣性因子を考慮して次に向かうべき場所を決定します。この条件で移動を繰り返すことによって、最適な位置に鳥たちが集まり、その点が最適解となります。収束の様子を表す図として@sz_drさんの図がわかりやすいので引用させてもらいました(←引用に問題があれば削除します)。

f:id:kumagallium:20190507121109p:plain:w400
粒子群最適化の移動規則のイメージ図

f:id:kumagallium:20190507121122p:plain:w400

粒子群最適化による解の収束の様子 画像出典元: 粒子群最適化法(PSO)で関数の最小値を求める - Qiita

3.2 群知能クラスタリング

 よく用いられる一般的なクラスタリングとして、非階層的クラスタリング手法(例えば、k-means法)と階層的クラスタリング手法が挙げられます。それらが、どういうものでそれぞれどういう利点、欠点があるのかは#02 位置と集団を見抜く / 4. クラスタ生成の統計アルゴリズム – Antecanis Inc.がわかりやすかったので、詳しい説明はそちらをご覧ください。ここでは、それら一般手法と群知能を用いたクラスタリングをざっくり比較してみます。k-means法は、階層的クラスタリングよりも計算コストが小さい点、改良性がある点が強みだとされています。ここでいう改良性とは、新しいデータが追加された時に容易にいずれかのクラスタに割当できるかどうかを意味します。k-means法であれば、どのクラスタ中心に近いかを計算するだけでクラスタリングできますが、階層型の場合は基本的にゼロから再計算をする必要があります。ところが、k-means法は、階層性を考慮しない点や再現性がない(初期値に依存してしまう)点が欠点として挙げられ、それぞれ得意不得意が存在します。
 ここで、私が描いている「逐次学習する特徴ベクトルによるクラスタリング」を実現するためには、どういうクラスタリングが必要かを考えてみます。まず、逐次的に特徴ベクトルが変化し、それに応じてクラスターも逐次的に変化してほしいので、改良性が必要です。次に、階層性も必要だと考えています。例えば異常検知への応用を想定した場合、DoS攻撃というクラスタの中にもSYNフラッド攻撃UDPフラッド攻撃など細かなクラスタが存在することが予想され、階層性を考慮したクラスタリングとの親和性が高そうです。また、異常を人間が理解しやすいように可視化する場合にも、階層性を持っている方が有用であることが予想されます。ところが、先に述べた階層性、非階層性の2種類の手法では、その改良性と階層性の両方を持っていません。そこで注目したのが群知能を用いたクラスタリングです。群知能を用いたクラスタリングは、各個体間の類似性に基づいたクラスタリングによる階層性を考慮でき、新しいデータが追加に対しても類似性に基づいて動的にクラスタに割り当てられる改良性も備えています。群知能を用いたクラスタリングに代表例を次節から説明します。

f:id:kumagallium:20190809144711p:plain:w500

3.1.1 蟻コロニークラスタリングモデル(ACCM)

  蟻コロニークラスタリングモデル(ACCM)[2]は、蟻が幼虫の仕分けをする行動に基づいたクラスタリングアルゴリズムです。蟻は知覚範囲内に同じ種類の幼虫が存在するかどうかを判断します。もし周りに幼虫がいない、もしくは同じ種類の幼虫があまりいない場合には拾う行為をし、周りに同じ幼虫がいる場合に幼虫を下ろします。この作業を繰り返すことにより、小さなクラスタは縮小、消滅し、大きなクラスタはより大きなものに成長します。

f:id:kumagallium:20190426154759p:plain:w600

3.1.2 Flockアルゴリズム

 Flockアルゴリズム[2]は、鳥などの群れの動きを模倣するアルゴリズムを取り入れたアルゴリズムです。鳥が群れを作る行動である1. 同種の群れの近くで留まる(Flock)、2. 同種でない群れから離れる(衝突回避)、3. 最近傍の鳥と速度を合わせる(速度調整)の3つの規則を利用してクラスタリングをします。この規則に従って各個体を動かすことにより種類別のクラスタリングが可能となります。

f:id:kumagallium:20190426153850p:plain:w600

4 提案手法

 以上で紹介した既存の群知能クラスタリングを利用し、超個体型データセンターにつながる研究をしていくことを考えています。その一方で、新しい群知能クラスタリングを提案するための調査やアイデア出しを行っています。例えば、私は材料工学分野の研究をしてきましたので、それに関連する群知能が提案できないか考えています。本章では、新しい群知能クラスタリングの提案のための調査および提案を簡単に紹介します。

4.1 関連研究

4.1.1 荷電系探索 (CSS)

  荷電系探索 (CSS)[3] は、物理学と力学の法則(クーロンの法則とガウスの法則とニュートン力学)に基づいた最適化手法です。適用度の値を電荷の値と定義することで、粒子間距離と合わせて電場やクーロン力が計算できます。そのクーロン力に従って粒子をどのように動かすかをニュートン力学により決定し、最適解を求めることができます(クラスタリングも可能[4]) 。PSOと同様に粒子そのものが解を表す手法です。

f:id:kumagallium:20190426154746p:plain:w600

4.1.2 シミュレーテッドアニーリング(SA)

  シミュレーテッドアニーリング(SA)は、材料工学における焼きなまし(アニーリング)という物理プロセスに着想を得た最適化手法です。アニーリングとは、物質を融解状態になるまで加熱し,徐々に冷却する操作のことであり、このアニーリングにより,分子がエネルギーが最も少ない状態に配列し,結晶構造を形成させることができます。この概念を最適化計算に利用しています。新しい点はランダムに生成され、その新しい点が現在の点より改善される場合は受け入れ、改悪される場合も一定の確率で受け入れます。その確率は、温度が高いほど、また変化量(新しい点と現在の差)が小さいほど受け入れる確率が高くなる関数となっています。それにより、高温では大域的な解の探索、低温では局所的な探索が行えるため、局所解に陥ることを避けることができます。

f:id:kumagallium:20190426153809p:plain:w600
シミュレーテッドアニーリング(SA) 画像出典元:Wikipedia

4.1.2 PSO+SA

 粒子群最適化(PSO)とシミュレーテッドアニーリング(SA)を組み合わせた手法の提案がすでにいくつか報告されている[5,6]。PSOは、単純、高速、且つ実装が容易ですが、粒子群の最適粒子が局所最適になってしまうと、粒子群が局所最適から飛び出すことは非常に難しくなる場合があります。一方でSAは、局所最適から飛び出して大域的最適値に近づくことができるように確率的にジャンプする性質を持っています。そこで、それらを組み合わせることにより、簡単で実装しやすいだけでなく、局所最適を避ける能力を強化し、収束の速度と精度も改善することが報告されています。

4.2 提案手法

 以上の関連研究を含めて以下の手法を提案する。

4.2.1 CSS-SAハイブリッド法(核生成モデル?)を用いたクラスタリング

 簡単にいうと荷電系探索 (CSS) とシミュレーテッドアニーリング(SA)の組み合わせ手法です。局所探索と大域的探索の両方を強化できるPSO+SAのPSOCSSに置き換え、さらにクラスタリングに利用しようというものです。そうすることによって、液体状態から温度を下げることによって核が生成されるアナロジーで捉えることができ、そこから新しい発想が得られないかというアイデアです。本手法では、粒子間類似度が温度の力よりも大きくなった時に結合(粒子間の手を結ぶ)とみなすことによって、類似度の高いものから順に結合していき(階層性)、最低温度を特定の温度に設定することでその時点でのクラスターが生成されると予想しています。また、最低温度の設定によって改良性も持たせることができ、温度を上げ直すせば全体のクラスタリングをリセットすることもできると考えています。
 まだジャストアイデア段階ですので、調査や実装をもう少し進める必要がありますが、この手法の強みを明確化できれば面白いかもしれないなぁと思っています。

f:id:kumagallium:20190426152836p:plain:w600
CSS-SAハイブリッド法(核生成モデル?)

4.2.2 ゾーンメルト型異常検知を用いたクラスタリング、および異常検知【おまけ】

 こちらはCSS-SAハイブリッド法よりもジャストアイデアです。まずゾーンメルト法とは、不純物の多い金属のインゴットから純度の高いインゴットを精製するための不純物分離法です。その概念をクラスタリングに利用できないかというものです。部分的に(ゾーンに分けて)クラスタリングを行い、前の部分との類似性で紐付けることにより、最終的に異常を押し出すような異常検知に応用ができないかと考えています。

f:id:kumagallium:20190426152849p:plain:w600
ゾーンメルト型異常検知

5. おわりに

 さくらインターネット研究所のコンセプト「超個体型データセンター」から自分自身の興味に落とし込んだ結果「逐次学習する特徴ベクトルによるクラスタリング」の研究を進めたいと現在は考えています。そして、クラスタリングは、階層性改良性の両方が得られる利点を持つ群知能クラスタリングに興味を持ち、特に取り組んでいきたいと考えています。また、既存の群知能クラスタリングを利用して、異常検知やサーバの最適配置のような様々な応用に落とし込む研究を進めるのはもちろん、自分自身のバックグラウンド(材料工学)を活かした新しい手法を提案できればさらに嬉しいなという気持ちです。まだまだ関連研究も調査段階ですし、アイデアもジャストアイデアな感じですが、今回のようにアウトプットをして、様々な方からフィードバックを貰って、深めていければと思っています。

 

6. 参考文献

  1. AntNet: Distributed Stigmergetic Control for Communications Networks | Journal of Artificial Intelligence Research

  2. 群知能とデータマイニング [ アジス・アブラハム ]

  3. A novel heuristic optimization method: charged system search | SpringerLink

  4. Application of Charge System Search Algorithm for Data Clustering: Computer Science & IT Book Chapter | IGI Global

  5. A New Hybrid Algorithm of Particle Swarm Optimization | SpringerLink

  6. Hybrid PSO-SA Type Algorithms for Multimodal Function Optimization and Reducing Energy Consumption in Embedded Systems

"楽しい研究"をするために考えたこと ~大きなビジョンとワクワクの根源~

※この記事で書いている内容は、完全に私の主観で、私が楽しい研究するための考えを可視化、言語化して整理したものです。そして、わかってる人からすると当たり前のことを書いているかもしれません。

目次

1. 問題提起

 「憧れを憧れのままにするな」
 最近、憧れの研究者からやあるアーティストのラジオの中から、言葉は違えど同じような内容を耳にして、胸に刺さるものがありました。なので、私自身が誰かの憧れの研究者になるために、自身の現状を客観的に把握し、現状と理想のギャップを埋めていくための整理をメモしておこうと思います。
 まず私自身が憧れの研究者のどの部分に憧れているかを考えました。私のあこがれの研究者は、どういう未来が来るのか、その未来で自分がどうなりたいかのビジョンを楽しそうに話してくれます。その楽しそうに研究をしている姿に憧れを感じていました。ではなぜ楽しそうなのか。その理由の一つが、ワクワクするような大きなビジョンを持つことが肝なのかもしれないと思い、思考を進めることにしました。

2. 思考の過程

2.1 これまでの自分のビジョンの作り方

 博士課程の私の研究は、以下の図のような進め方であったように思います。大きなビジョンを描くというよりかは、共感した他の研究者のビジョン(先行研究)を参考に、まだやられていない内容をいくつか取り上げて、一つ一つその内容を実験し、学会や論文で発表してきました。もちろんその一つ一つの内容は、それぞれ大なり小なり新規性が存在します。ところが、博士論文をまとめる段階で考えることになったのが、ビジョンです。それぞれ一つ一つに新規性が存在しているとはいえ、それをまとめて終わりではなく、それら全体がどういった意味を持ち、学術の世界や未来のためにどのように貢献できるのかを1つのビジョンとしてまとめあげる必要がありました。これが初めて描いたビジョンであり、やりきった一つの自信にはなっています。
 ただ、そのビジョンは誰かのビジョンという山からスタートして、それにコブをつけたようなビジョンではないかという気持ちが拭えずにいるのも確かでした。誰かの二番煎じ感、2流感、小さな山感など色々な表現ができるかもしれませんが、その小さなコブをナデナデしているだけではだめだなと思ったのです。そこで、ワクワクする大きなビジョンを描いてみたいという思考に至りました。

 ちなみに私の専門分野は、材料工学で熱電変換材料というエネルギー材料を研究していました。特に、Al(アルミニウム)をベースとした合金に注目して、新しい熱電変換材料を探索し、実験、計算の両面から有効性を検証するような研究でした。実際にいくつか新しい材料を提案できたため、その材料ごとに新規性は少なからず存在するので、それぞれで論文を書きました。しかし、それらをまとめるだけの博士論文ではなく、なぜAl系合金で新しい熱電変換材料が見つかったのかを、電気陰性度という基礎物性から説明し、探索指針を提案する形でまとめ、これから新しいAl系熱電変換材料が発見されるビジョンを描きました。

f:id:kumagallium:20190404104442p:plain
課題先行ビジョン後付型

2.2 ビジョンの存在意義

 そこで、ワクワクする大きなビジョン先行して考えることにしました。幸い、私の所属するさくらインターネット研究所では、ちょうど研究所全体のビジョン(超個体型データセンターを目指す当研究所のビジョン – さくらインターネット研究所)を考えるタイミングでもありましたので、自分自身のワクワクするビジョンを探しました。そして、まだなんとなくではありますが、ワクワクするビジョンのようなものを定義しました。
 次に、そのビジョンを実現させるためのマイルストーンとして、どのように細かい研究課題に落とし込んでいくかを考えていくことにしましたが、それが間違いであったように思います。つまり、ビジョンから逆算的にすべき課題を考えてしまったところが問題だと感じています。ビジョン自体は、そもそも実現までの時間的距離も遠いものですし、実現可能かどうかはともかくワクワクするものです。それなのに、ビジョンから研究課題を逆算してしまうと、そこいくまでの道は自分の分野だけで絞ってもとてつもなく多く(見えてしまう)、それぞれが太く(複数を並行して進めるほど優しい道ではない)思えました。課題が山積みだとしが見えてこなくなってしまいました。また、実現可能性を明確にしていくことでどこかワクワクが減少してしまうような気もしました。
 つまりビジョンは、逆算して自分自身の研究計画を綿密に立てためのものではないということを学びました。ビジョンは、自分自身のモチベーションを保つためのものであると同時に、共感してくれる人を集めるためのものであり、一人で解決することではそもそもないということを改めて感じました。なので、ビジョンはそのままワクワクした状態で置いておいておくだけでいいんですね。つまり、描くべきビジョンは現状から遠くて且つ自分にとって煌々と輝いているもの(遠いし、眩しくて正確な距離や場所が分からないもの)が良いのかもしれません。そして、より多くの人と共感することが大事だと仮定するのであれば、ビジョンはより多くの分野の人が引っかかるワードを選ぶべきなのかもしれませんね。

 私の場合、材料系研究者から情報系研究者になったこともあり、それを活かしたビジョンを考えています(まだだと状態)。現段階で考えているビジョンは、原子内に存在する電子と原子核との関係性や分子内の原子同士の関係性、その関係性を作り出す引力と斥力のバランス、そういったモデルを今でいうエッジコンピューティングの仕組みに取り入れることで、原子や分子がそれぞれの単位で安定的に自己組織化し、様々な機能を示す材料となるような超個体的コンピューティングの実現化です。ただし、実際に具体的な実現化を考えると現在存在するコンピューティングに関する理解、通信やネットワークの理解など学習やサーベイすべきことが数多く見えてきます。また、アナロジー的アプローチとしては群知能などすでに多くの研究がなされており、そちらもサーベイする必要があるかもしれません。

f:id:kumagallium:20190404104448p:plain
ビジョン先行天下り課題設定型

2.3 ビジョンと並んで大事なこと

 「ビジョンは大事」そう考えている中で、ビジョンと並んで大事なものがあるような気がしてきました。それは、自分自身のワクワクの根源を見つけることです。その根源が見つかれば、それに従った面白い研究課題にその都度立ち向かうだけでいいんじゃないかという気がしてきました。言い換えると、自分自身の主成分分析をして、最も自分を表す特徴ベクトル(固有値が最大となる固有ベクトル)を探し出し、そのベクトルの方向だけを大事にして、自分がワクワクするビジョンと大体の方向だけを合わせるだけで十分なのではないかということです。
 もちろんその都度見つけた面白い研究課題に対してのストーリーやそれに従った細かなマイルストーンを設定することは大事で、それぞれの小さなビジョンを掲げ、達成していくことも大事だと思っています。それは博士課程でやっていたことと大差ないようにも思えます。ただ、研究を進めていく中でその研究課題の大きさ(実現可能までの時間)が大きくなっていくはずです(むしろ、そうなって欲しい)。そして将来、自分のビジョンが当時思っていた場所と変わっている可能性があっても、それはそれでもいいんだろうなとも思っています。

f:id:kumagallium:20190404104651p:plain
ワクワク由来ベクトル先行ビジョン抽象化型

まとめ

 憧れを憧れで終わらせないために、結果的にあたり前のことかもしれませんが、ワクワクする大きなビジョンを持ち、自分自身のワクワクの根源を知ることが大事だと確認することができました。
 私が現在考えているビジョンもまだまだ改良の余地があると認識しています。また、自分自身のワクワクの根源を見つける作業も、まだまだ完了できているわけではなく、もう少し掘り下げていかないとなと思っています。