読者です 読者をやめる 読者になる 読者になる

クラスの依存関係グラフ 3

手慰み Java 計算機

Java および Scala のクラスの依存関係のグラフについて調べている。

驚くべきことに(まあ予想はしていたけれども)、クラス間の依存関係のグラフはスケールフリーネットワークの性質を持つことが明らかになりました。スケールフリーネットワークでは、ノードの次数がべき乗則に従います。

勉強しながら調べているので、次数の非常に大きいクラス、例えば java.lang.Object クラスの存在がべき乗則で現れうるクラスなのかべき乗則でも説明できないほど例外的に次数の大きいクラスか、よくわからないと前回・前々回に素人っぽい言及をしました。

プロットの仕方を工夫すると、次数が大きいところも綺麗に図がかけることがわかったので、今回は次数が大きいところでもべき乗則が成立しているかどうかを検証します。

f:id:fjkz:20161112185046p:plain

上は前回載せた図で、次数の分布を示しています。これは、Bin の幅が 1 のヒストグラムです。次数が大きいところはサンプルが少ないのでガタガタになっていてべき乗則なのかどうかよく分からなくなっています。

そこで、Bin の幅を 1 に固定せずに、対数プロットしたときに Bin の幅が同じにやるようなヒストグラムを書きます。つまり、1 つめの Bin は次数が 1 のノードの割合、2 つめの Bin は次数が 2 か 3 のノードの値、3 つめは 4, 5, 6, 7 のいずれか、N つめは log2(N-1) から log2(N)-1 となります。

上のような Log-Bin で書いたヒストグラムが下の図です。

f:id:fjkz:20161123191256p:plain

次数が高いところは前の図ではが省きました、Log-Bin で描くと次数が高いところまでグラフに含められるようになりました。

入力次数は、次数が大きいところまで、きれいなべき分布になっていることが分かります。次数が 10^5 といった非常に大きな値を持つノードは、java.lang.Object クラスなのですが、この存在もべき乗則に従うことが分かりました。

出力次数は、次数が小さいところはよくわからない分布をしていますが、次数が大きいとべき乗則っぽい分布になっています。

積分布を描いても、次数の高いところが上手く表現できます。

下の2つの図は、次数 k に対して、次数が k を超えるノードの割合を示しています。上の図が入力次数、下の図が出力次数です。*1

f:id:fjkz:20161123192131p:plain f:id:fjkz:20161123192136p:plain

Log-Bin だとプロットの数が減るのでデータが丸められてしまっている不安がありますが、累積分布ではプロットの数は減りません。

さて、入力次数の方に関しては、きれいなべき乗則になっています。グラフの傾きは -1 です。累積分布の場合は傾きは べき指数 + 1 になります。累積なのに、k が小さいところの P が 1 になっていませんが、それは k = 0 のノードがいるからです。また、ヒストグラムを描いたときには気付かなかったが、次数が 10 以下のところで傾きが少し緩くなっています。べき乗則に従うと言われるデータは一般的にこうなっています。次数が大きいところはちょっとガタガタっとなっていますが、k = 10^4 に何か意味があるとは思えないので、ノイズでしょう。

出力次数の方が、k = 30 から k = 200 まではべき乗則に従っています。k が小さいところは謎の分布なのは、Log-Bin の図の方が分かりやすいです。

出力次数の次数が大きいところは、ガタガタしてわかりづらいが、グラフの傾きが急になっているようにも見えます。ソフトウェアを作る視点で考えると、出力次数は、ソースコードを書く人間が決めることで、あまりに依存先が多いクラスというのは作らないものなので、上限値があることが予想されます。べき乗則に従うということはサンプル数を増やせば、想像を絶する巨大なクラスが現れるということを意味していますが、おそらくありえないでしょう。10^3 のオーダーが上限なのではないかと推測されます。このことに関しては、ソフトウェア特有の現象なので、もう少し調べる価値がありそうです。

今はべき指数は目分量で見ているので、次回は定量的にべき指数を計算してみようと思う。

参考

Network Science

Network Science

*1:積分布の図は matplotlib で描きました。他の図は gnuplot で描いています。gnuplot が慣れているので、なんとなく guplot を使っていましたが、 matplotlib の方が使いやすいですね。

アニメーションと機械学習

所感 a.k.a. poem 映画 計算機

TV 番組で ドワンゴ の人が アニメーション監督の宮崎駿氏に機械学習のデモを見せて「生命への冒涜だ」と怒られたことが話題になりました。

インターネットの記事を見ると、「川上(ドワンゴの代表)め、ざまあみろ」といった意見が目立ちますが、私は宮崎氏の言っていることには同意できないと思いました。とは言っても、TV に放映された映像からは川上氏がどれぐらい機械学習について説明したのかも、宮崎氏がどれぐらい理解してドワンゴがやっていることを否定したのかも、分からないので、どっちが正しいとかはあまり語れないです。ただ、宮崎氏のような強い自負を持った人に対して、何かプレゼンするのは、やっぱり大変だと認識しました。

まあ、宮崎氏のような世界で最も生命の動きというものに対して敏感な人に、あんな失敗作の動画を見せたらアカンだろ――とは思いましたが。

失敗作とは、ドワンゴの人が言っているわけではなくて、私の推測です。人型の物体に、各種の力学的条件を与えて、進行する動きを学習させたら、きっと生命らしい動きを覚えるだろう、たとえば歩行を覚えるだとかを期待して実験をしてみたら、痛覚だとか重要な条件がないために、生命らしからぬ「気持ち悪い」動きを覚えてしまった――といったところだと想像します。必ずしも失敗とは言えないが、まだ研究の途中のものなのでしょう。

しかし、研究がある程度完成して、生命らしい動きを機械が覚えられるようになれば、生命らしい動きを生むための条件が分かります。それは生命を生命たらしめているものは何かを知るということです。ドワンゴの人がそんなことを考えて、機械学習の研究をしているのかは知りませんが、生命とはなんぞやということは、多くの人が考えてきた問題でこれに対してひとつの答えを出すということは、私は意味のあることだと思います。

動き、つまり力学の観点から、生命について論じた例というのはありません。単に無知なだけかも知らないが、力学から生命を論じた例を私は知りません。化学反応の連鎖として生命を見る分子生物学は成果を上げています。また、生態系、つまりマクロ的に生命を見ることもされています。心理学だとか動物行動学だとかで行動から見ることもされている。しかし、生命の動きというのはよく分かっていません。生きているものとそうでないもので動き方が異なるということもよく分かっていません。私は生物と非生物では明らかに違うと思っているが、証拠はない。ボストンダイナミクス社のロボットは生き物の動きをしていないし、トトロは生き物の動きをしている。この差異がどこから来るのかは分からないのです。

アニメーターが偉大だと思うのは、生き物らしい動きというのを想像して描くことができることです。祟り神だとか猫バスはいない。にも関わらす、存在しないものの動きを実在感を持って描くというのは、天才にしかできないことです。

ドワンゴ機械学習の技術が完成したら、天才にしかできない芸当が機械でもできるようになるかもしれません。存在しない生物であっても、力学的条件を与えれば、自ら「リアル」な動きを覚えて、動き始める。そういうことができるようになれば、アニメの表現というのが変わるかもしれない。ドワンゴの人はこういうことがしたいのかな?

機械学習はまだアニメーションには全く使えないが、古典的な力学の演算は既に広く使われています。CG アニメの怪獣の毛の動きだとか、飛び散る水しぶきの動きだとかは、もう人間が描くよりも計算機に計算させた方が「リアル」な動きをします。

しかし、私が面白いと思うのは、力学的な「リアル」な動きとアニメ的な「リアル」な動きは違うことです。仮にトトロが実在したとして、あんな動きができるかというと力学的に無理です。だが、力学的に正しい動きをしているトトロなんてまったく実在感のないものになるに違いありません。力学的にはリアルでないからこそ、アニメ的にはリアルなのです。「板野サーカス」と呼ばれるミサイル群がうねうね動く表現方法についても、あんな動きをするミサイルなんて現実には作ろうとしても作れないが、アニメ内ではあの動きの方がリアリティがあります。*1人間フィルターを通したときに、正しく思える動きというのは、現実とはずれているのでしょう。

人工知能がそこまで考慮できるようになったら、人工知能と人間は本当に区別できなくなるかもしれない。まあ無理かな?

*1:余談だが、板野サーカスは高速に動く物体に対して、カメラが寄ったり離れたりするのですが、カメラの方が高速に動く物体よりもずっと速く動くことに気づいてから、気持ち悪く思えてきました。

クラスの依存関係グラフ 2

手慰み 計算機 Java

前回: クラスの依存関係グラフ - 超ウィザード級ハッカーのたのしみ

クラスの依存関係のグラフについて調べています。

今回は前回よりも大きな系について調べました。

対象は、Spark 2.0.1 です。前回は、Hadoop 由来のクラスだけ調べたが、今回は Spark のクラスだでなく、Spark が呼び出している外部ライブラリ内のクラスも含めた、クラス群の依存関係のグラフについて調べます。Spark 2.0.1 の Hadoop 2.7 用ビルドに含まれている JAR をすべて調べます。*1

グラフの大きさは、頂点の数が 113434、辺の数が 1456523 となっています。可視化した結果が下の図です。Modularity を強調しています。色は可視化ツール(gephi)が計算した Modularity Class で、辺の色は元の頂点の Modularity Class を示しています。

f:id:fjkz:20161112210202p:plain

次数の分布は以下の図のようになっていました。

f:id:fjkz:20161112185046p:plain

入力次数に関しては、綺麗なべき乗則に従っています。クラスの依存関係は、一般的にべき指数 2 のスケールフリーネットワークとなっていると予想できます。このようになっている理由は、ネットワーク理論の枠組みで説明できそうです。

ただ、グラフに収まらないほど、次数が大きいところにも JavaScala の標準ライブラリのクラスがあります。java.lang.Object クラスなんかは、100957 の次数を持ちます。そいつらの存在がべき乗則に従わない例外的なのか、それともべき乗則であっても確率的現れうるのかは、今後検証する必要があります。

出力次数に関しては、前回とは見た目が異なります。すべての依存関係について調べると今回の結果になるようです。よく知られた確率分布の形ではなく、この形状の意味は物理法則では説明できない感じがします。

依存するクラスの数が 8 個の場合が最も多くなっています。この値は感覚と一致しています。

また、非常に多くのクラスに依存するようなクラスも少ないながら、存在します。べき乗則っぽい見た目をしています。入力次数の場合よりべき指数は大きいです。出力次数はクラスを書いた人が決めることですが、あまり出力次数を大きくはしたくないものなので、出力次数が大きいクラスが稀になることは妥当でしょう。サンプルをさらに大きくしたら、出力次数が大きいクラスの数はべき乗則を下回ってくるのではないかと予想されます。1000個のクラスに依存したクラスなんて巨大すぎて作れないです。

Modularity という値は 0.571 という値でした。この値の詳細はよくわからないのですが、可視化の結果からも推測できるように、Modularity が高いようです。

このサンプルで得られる情報はもっとありそうなので、もうちょっと分析してみたい。

*1:Spark は Hadoop の JAR も含んでいるので、前回と重複した要素もある。

クラスの依存関係グラフ

計算機 手慰み Java

Java のクラスの依存関係を調べてみた。

規模が大きいアプリケーションの方が統計が取りやすいので、Apache Hadoop の 3.0.0-alpha バージョンを対象に調べる。テストとアノテーションを除いた、Hadoop 由良のパッケージに含まれるクラスに依存関係のグラフについて調査する。

クラス間の依存関係を調べるのに、JDK8 に含まれる jdeps というコマンドを使った。jdeps に -verbose オプションをつけると 各 jar 内のクラスが依存しているクラスが出力される。-dotoutput オプションで DOT ファイルに結果を保存することができる。下のようなファイルが出力される。

digraph "hadoop-mapreduce-client-common-3.0.0-alpha1.jar" {
    // Path: ./mapreduce/hadoop-mapreduce-client-common-3.0.0-alpha1.jar
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.io.IOException";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.lang.Object";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.lang.String";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.net.InetSocketAddress";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "org.apache.hadoop.classification.InterfaceAudience (not found)";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "org.apache.hadoop.classification.InterfaceAudience$Private (not found)";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "org.apache.hadoop.conf.Configuration (hadoop-common-3.0.0-alpha1.jar)";

依存先のクラス名の後ろに( ) 内にパッケージ名が付く。(not found)はパッケージが見つからないという意味です。これがあると→の元と先が同じクラスでも別の名前になってしまうので、sed で取り除く。

今回は、対象の JAR 内のクラスの関係のみを調べたい。そこで、辺が示す先がorg.apache.hadoop以外から始まるパッケージに含まれるクラスとなっている辺は除いた。また、org.apache.hadoop.classification パッケージのクラスも、今回の対象のJAR内のクラスではないので、それらが先にある辺も除いた。

JAR ごとに DOT ファイルが生成されるが、全部をまとめてひとつのグラフとして調べる。

頂点が 7844, 辺が 36076 のサイズの有向グラフとなっている。

graph-tool だと描写が非力だったので、gephi で可視化をする。

f:id:fjkz:20161111223015p:plain

上の画像はグラフを可視化したものである。大きくて色の濃い丸が、in/out を問わない次数の大きい頂点である。辺の色は頂点の色に基づく。少ない頂点のみが次数が大きく、ほとんどの頂点は次数が小さいことが可視化の結果から予想できる。

そこで、次数と、その次数のクラスの数の関係を調べてみる。

f:id:fjkz:20161111203145p:plain

上の図は、次数とその次数を持つクラスの割合を示している。入力次数・出力次数いずれの場合も、次数が10以上100以下のクラスはべき乗則に従っているように見える。どうやらクラスの依存関係のグラフはスケールフリーネットワークの性質を持つ可能性があるようだ。べき係数は 2 程度で、スケールフリーネットワークでは典型的な値となっている。Barabási–Albert モデルのネットワークの成長過程は、ソフトウェアが拡大していく過程と似ていることから、クラスの関係がスケールフリーネットワークとなっていることが説明できるだろう。*1

次数が大きいクラスというのは、ソフトウェアの中で重要なクラスであると考えられる。べき乗則に従うということは、特定のクラスの重要度が飛び抜けて高いということを意味している。

入力次数が大きいクラスは多くのクラスから呼び出される Fan-in なクラスである。何度も再利用されている非常に有用な部品と言える。多くのクラスから利用されていることから、欠陥も少ないと考えられる。一方で、利用者が多いクラスの動きを変える場合は影響範囲が非常に大きくなるので、なかなか変更できあに。そのため、安定度が高いクラスであると言える。

出力次数が大きいクラスは多くのクラスを呼び出している。Fan-out なクラスである。GoFデザインパターンでいうところの Facade となっていて、そのクラスから呼び出される機能が多いということを意味していると思われる。変更の影響を受けやすく、そのため欠陥密度も高いだろう。このクラスを重点的にテストすると効果が高そうだ。

入力次数の大きいところで、べき乗則に従わない特異的に大きい次数を持ったクラスが存在していて、図の右からはみ出してしまっている。具体的には、org.apache.hadoop.conf.Configuration という設定プロパティの値を得るためのクラスが 1368 の入力次数を持っている。このクラスは、非常に多くのクラスから横断的に使用されるクラスである。このようなクラスの存在が、今回調べたソフトウェアに特有のものなのか一般的に存在しうるのかは、他のソフトウェアも調査しないと分からない。もし異常に入力次数が多いクラスが存在するということが一般的であるとしたら、ソフトウェアにスケールフリーネットワークとは異なる特別なネットワーク構造があると言えるかもしれない。

*1:Barabási–Albert モデルのべき係数は 3 で完全な説明はできない。いつかちゃんとまとめたい。

graph-tool で遊ぶ1

計算機 手慰み Python

複雑な世界のありようを理解するのに、「グラフ」の可視化だとか分析はすごく有用なのではと考え始めたので、グラフについて勉強してみる。

動くおもちゃがないと楽しくないので、いいのかどうか知らないが、検索して出てきた graph-tool というツールで可視化等をしてみる。

graph-tool.skewed.de

インストールは 「Download - graph-tool: Efficent network analysis with python」 に従えばできた。

みんな大好きな Barabási-Albert モデルのネットワークの絵を書いてみる。

import graph_tool.all as gt

# ノード数 1000 の Barabási-Albert モデルのネットワークを作る
g = gt.price_network(1000, directed=False)

# グラフを描写するときのいい感じのノードの配置を計算する。
# どうも斥力と引力が働く粒子の運動を計算して、釣り合いがとれるような場所を計算しているっぽい。
# 試行毎に違う配置になる。
p = gt.sfdp_layout(g)

# グラフを PNG 画像として出力する。
gt.graph_draw(g, pos=p, output="barabasi-albert.png")

f:id:fjkz:20161108195044p:plain

美しい……。

権威と OSS

所感 a.k.a. poem 計算機

権威とはなんなのだろう?――というのは長いこと悩んでいる疑問である。私が権威が大好きな権威主義者ということなのだろうな。

また、OSS というのも社会学的に興味深い営みであり、これを観察することも趣味である。

さて、どうも最近 OSS権威主義的になっている気がする。

OSS は一種の規格であるので、OSS に関して発言力を持つことはソフトウェアベンダーにとっては重要である。OSS の開発に関して発言力を持つことができれば、自社の製品と OSS との親和性を高めることができるので、自社の製品が売れる。そのため、有名どころの OSS では、いろんな企業が主導権をとろうと活発に開発に参加している。

既に存在している OSS の開発に参加するというだけが、OSS で主導権を取る手段もない。既存のものは先行者利益が大きい。先にいた人が強い発言力を持っているので、後から入ってきた人が発言力を持つというのは結構大変だ。OSS で最も偉い人は始めた人で、次に偉い人は最も手を動かした人である。これは OSS に限らずどこの業界であってもそうであろう。しからば、自分が完全にコントロールできるような OSS が欲しいのであれば、自分で OSS プロジェクトを初めてしまうというのは簡単な手段である。

ただ、企業が始めた OSS の開発に参加する人がいるかというと、いないだろう。どうして一企業の利益に、関係ない人が貢献するのだろうか。標準規格にすることを狙って、企業が始めた OSS プロジェクトで、参加者が集まって上手くいっている例は知らない。ただソースコードが公開されているだけで、実際には一企業の人が内々で作っているような OSS だけれどもオープンではない OSS は多い。

標準化したいならば、中立性が必要だ。中立であれば、一企業だけに利する恐れが少ないので、参加者が集まる可能性が高まる。もちろん、ソフトウェアとしての価値が高いことが前提である。

思うに中立性とは権威と同じである。中立とは他より偉いという特権だ。そのため OSS プロジェクトを権威の元におこうというのは自然な考えだ。OSS 界隈で権威ある団体といえば、Apache Software Foundation と Linux Foundation が挙げられよう。一企業主導であれば標準化が難しいからと、Apache Software Foundation にプロジェクトが寄贈されたりだとか、Linux Foundation 配下で開発が行われたりだとかがされる。

ASF や Linux Foundation の元で OSS の開発が行われたら、それが中立化というと実際のところそんなことはないと思うが、一企業に利するようなことは建前上できない。

おそらく、今後 ASF や Linux Foundation の元で OSS を作ろうという風潮がますます活発になって、これらの財団のブランド力が強くなっていくだろう。権威というのは偉いから偉いのであって、一旦権威がついたものはもっと偉くなる方に向かうものだ。OSS で標準化を狙うなら、ASF や Linux Foundation の中で発言力を持てるように頑張るのがオススメだ。*1

しかし、そういう風潮が強まると、OSS が政治的が強いパワーゲームになることもおそれている。みんなで協力して自由なソフトウェアを作ろうみたいな、牧歌的なものではなくなってしまうかもしれない。

*1:とはいっても ASF や Linux Foundation の中がどうなっているのかはようわからないのだが……

ブロックチェーンについての考察

計算機 ノート 考察

タイトルが雑だが、最近ブロックチェーンについてぼんやり考えていて、その覚書。

元の bitcoin の Proof of Work (PoW) は以下の式を満たすブロックをブロックチェーンにつなげることができる。

hash(prev, tx, nonce) < 1 / difficulty * hash_max                (eq.1)

hash       : ハッシュ値(正数とする)を返す関数
hash_max   : hash が返す最大値
prev       : 前のブロックのハッシュ値
tx         : ブロックに含めたいトランザクション
nonce      : 意味のないテキトーな値
difficulty : 困難さを表す値, (0, ∞)

PoW では上の式を満たす nonce を総当り的に探すということをする。bitcoin は diffuculty を大きくとって、めったにちょうどよい nonce が見つからないようにしている。

しかし、それでは遅いので、下のようにすることが考えられる。

hash(prev, tx, nonce) < credit / difficulty * hash_max           (eq.2)

credit という指標を導入し、信用度が高い人は PoW の難易度をおまけするようにする。credit が高い人が攻撃者の可能性が低ければ、PoW の条件が緩くても、対攻撃性は下がらない。

このような実装をとっている bitcoin 類似の仮想通貨はきっとあるだろう。調べてみると Peercoin というのがこんな感じっぽい。*1Proof of Stake 方式をとっている仮想通貨は、通貨の保持量が高い人の credit を上げるということをしているようだ。

さて、面白いと思うのは、bitcoin は decentralized なシステムであると言われるが、(eq.2) は centralized なシステムも表すことができることだ。単一のノードのみ credit ≒ ∞ で、他のノードが credit ≒ 0 のシステムであれば、centralized なシステムとなる。ひとつのノードが PoW に相当する計算なしに、データベースを更新していくような、一般的な Server-Client 型システムである。*2

(eq.1) のように credit が全ノードで同じシステムは完全に decentralized である。一部のノードの credit が非常に高くで、他のノードの credit が非常に低いシステムは centralized といえる。ということは、いろんな credit のノードがあるようなシステムは、semi-centralized なシステムということになろう。Server-Client と P2P の間のようなシステムである。コンピュータシステムではない実在するシステムにはこういう形態のシステムは多いように思う。

現実のシステムと比較すると、通貨の保持量によって信用度を高めるというやり方もかなり現実を模しているように思うが、他にも良い credit の与え方はありそうだ。通貨の保持量以外の良い credit の与え方のアイデアはあるのだが、それを書くには余白が足りない。

*1:実装はおそらくもっと複雑で、多分コンセプトはこんな感じかなという推測です。詳しい人がいらっしゃったら、教えていただけると非常に嬉しい。こういうことを質問・議論できる場所(メーリスなり掲示板なりSNSなり)はないのだろうか?

*2:複数のノードが credit ≒ ∞ の場合というのも考えられる。この場合には、ちゃんとノード間で「合意」を取るようにしないとそれぞれのノードが持つデータベースがバラバラになるので上手く行かない。credit を少しずつ下げていって、どれぐらいから「合意」がなくても上手く回るようになるのかというのも興味深い問題である。あるいは、厳密に「合意」を取る場合とブロックチェーンのように「合意」を取らない場合をシームレスにつなげる方法はないかなどは、誰も解決していない問題であろう。