列挙木とMCMCを組み合わせた部分グラフサンプリングアルゴリズムの構築

列挙木と

MCMC

を組み合わせた

部分グラフサンプリングアルゴリズムの構築

Sampling Algorithms for Subgraphs

Based on Enumration Trees and MCMC

和佐 州洋

1∗

_{石畠 正和}

2

_{宇野 毅明}

1

_{湊 真一}

2

Kunihiro Wasa

1

_{Ishihata Masakazu}

2

_{Takeaki Uno}

1

_{Shin-ichi Minato}

2 1

_{国立情報学研究所}

1

_{National Institute of Informatics}

2

_{北海道大学}

2

_{Hokkaido University}

Abstract: In this paper, we propose sampling algorithms for subgraphs in a given graph, which is based on enmueration trees and Markov Chain Monte Carlo method. We also demonstrate computational experiments for measuring the performance of the algorithms.

1

はじめに

近年の計算機やネットワークの性能の向上に伴い，グ ラフやその一般化である超グラフといった構造を持つ 複雑なデータが，指数的に増加している．特に，生命科 学やデータベースなどの分野でその現象は非常に顕著 であり，その膨大な情報からの知識発見は喫緊の課題 となっている．このような背景のもとで，複雑なデー タからの機械学習を行うときに，グラフの部分構造か ら特徴量を得るカーネル法 [4,7] が登場してきた．そこ で，本稿では，グラフ G に含まれている各部分グラフ に対して，ある評価関数 f を用いてその評価値を計算 し，G に対する f に関する期待値を計算する問題を考 察する． 部分グラフを抽出する研究のひとつとして，部分グ ラフ列挙問題が挙げられる．部分グラフ列挙問題とは， グラフ G と制約 C が与えられたとき，C を満たす G のすべての部分グラフを漏れなく重複なく出力する問 題である．これまでに，路 [1,3,6] や，閉路 [1,3,6]，全 域木 [6, 8]，クリーク [2, 9] などの部分グラフを効率よ く列挙するアルゴリズムが与えられてきた．効率よい 列挙アルゴリズムを構築する際の主なアプローチの一 つとして，列挙木を用いたアルゴリズムの構築があげ られる．列挙木とは，列挙対象すべてを含む樹状の探 索空間であり，これを用いた列挙アルゴリズムは，列 挙木を探索することで，解を列挙する．この探索を効 ∗_{連絡先：国立情報学研究所 情報学プリンシプル研究系} 〒 101-8430 東京都千代田区一ツ橋 2-1-2 E-mail: [email protected] 率よく行える列挙木を構築することで，効率よい列挙 アルゴリズムを実現する．列挙木は，解を網羅する点 で非常に優れた構造を持つが，一方で，列挙する対象 が指数的である場合，入力サイズが大きくなるにつれ， 解の出力自体が現実的でなくなる． 本稿では，前述の計算コストの増加を，サンプリング アルゴリズムを用いて部分グラフを特定の分布に従い 確率的に出力し，評価関数の期待値をサンプル近似す ることで克服することを目標とする．我々は，Markov Chain Monte Carlo (MCMC) 法とこれまで知られてい る列挙木の構築技法を組み合わせることで，制約を満 たす部分グラフを効率よくサンプリングするアルゴリ ズムを提案する．これまでに論理制約を満たすモデル をサンプリングするアルゴリズム [5] などが提案されて きた．また，Monte Carlo Tree Seach 法と MCMC 法 を組み合わせた s-t 路のサンプリングアルゴリズム [11] が提案されているが，この手法は列挙手法ではなくフ ロンティア法と呼ばれる部分グラフを列挙索引化する 技術を使っているところが今回とは異なり，リジェク ションが伴うため，列挙木を直接構成する本手法と比 べると 1 回のサンプリングのコストが高い．一方で，サ ンプリング後半はサンプル履歴を表現するデータ構造 を用いてより提案分布を補正するためより正確なサン プリングができる．本稿では，さらに，ランダムウォー クするグラフ構造を二種類あたえ，計算機による性能 の比較実験を行う． 本稿の構成は以下のとおりである．まず，2 節では，用 語の定義を行う．次に，3 節では，Metropolis-Hasting 法によるサンプリングアルゴリズムのフレームワーク 人工知能学会研究会資料 SIG-FPAI-504-07

を与え，ランダムウォークに用いるグラフ構造を 2 種 類あたえる．4 節では，前節で与えたフレームワーク とグラフ構造を元に，実データと人工データを用いて 計算機実験を行い，性能を比較する．5 節では，結論を 述べる．

2

準備

2.1

部分グラフ

グラフ G = (V (G), E(G)) は，頂点集合 V (G) と辺集 合 E(G)⊆ V (G) × V (G) の組からなる．以下では，頂 点数_{|V (G)| を n とし，辺数 |E(G)| を m とする．V (G)} 中の任意の 2 頂点 u, v に対して，(u, v)∈ E(G) なら ば，u と v は隣接しているといい，辺 (u, v) は u と v を 接続しているという．また，u に隣接している頂点集 合を N (u) とし，|N(u)| を u の次数という．頂点の列 π =⟨v1, . . . , vt⟩ に対して，任意の i, j = 1, . . . , t − 1 に おいて，(vi, vi+1)∈ E(G) ならば，π を G 中の路とい う．また，π の長さ|π| を |π| = t−1 とする．ここで，長 さ 3 以上の路 π に対して，v1= vtのとき，路を閉路と 呼ぶ．また，路や閉路中の全ての頂点が異なる時，それ ぞれ，単純路や単純閉路と呼ぶ．以下では，単純路や 単純閉路を単に路や閉路と呼ぶ．グラフ G 中の任意の 2 頂点間に路が存在する時，G は連結であるという．グ ラフ G の部分頂点集合 S⊆ V (G) に対して，S の誘導 グラフ G[S] を，S と S から誘導される辺集合 E[S] の 組とする．ただし，E[S] ={(u, v) ∈ E(G) | u, v ∈ S}

とする．G[S] は S から一意に決まる．したがって，文 脈から明らかならば，S と G[S] を同一視する．また， V′ ⊆ V かつ E′ ⊆ E[V′] を満たす V′と E′に対して， G′= (V′, E′) を G の部分グラフとよぶ． グラフ G が連結で，かつ，閉路を持たないとき，G を木と呼ぶ．木 T 中の頂点で，次数がちょうど 1 のも のを葉と呼ぶ．木 T の部分頂点集合 S⊆ V (T ) と任意 の正整数 k に対して，|S| = k かつ，T [S] が連結なと き，S を k-部分木と呼ぶ．S を k-部分木としたとき，S 中の頂点に隣接し，かつ，S に含まれない T 中の頂点 を境界頂点と呼ぶ．T に含まれる全ての k-部分木の集 合を，_{S(T, k) とする．}

2.2

部分グラフサンプリング

部分グラフ列挙問題とは，グラフ G と制約 C が与 えられたとき，C を満たす G の部分グラフを漏れなく 重複なく出力する問題である．G の部分グラフ S⊆ G が制約 C を満たすことを C(S) = 1 と表し，満たさ ないことを C(S) = 0 と表す．部分グラフ列挙問題で は，制約 C を満たす G の部分グラフの集合C(G, C) = {S | C(S) = 1} を出力することを目的とする．部分グ ラフ集合_{C(G, C) のサイズが G のサイズに対して指数} 的であるとき，_{C(G, C) を出力するには指数的な時間} を要する． 一方，部分グラフサンプリング問題とは，グラフ G と制約 C が与えられたとき，C を満たす G の部分グ ラフを特定の確率分布に従い出力する問題である．関 数 w : C(G, C) → R を C(G, C) 上の重み関数とし， w(S) (S ∈ C(G, C)) を S の重みとする．このとき， p(S; G, C, w) をC(G, C) 上の確率分布とし，以下のよ うな指数型分布族で定義されるとする． p(S; G, C, w) = 1 Z(G, C, w)exp(w(S)) Z(G, C, w) = ∑ S∈C(G,f) exp(w(S)) 部分グラフサンプリング問題では，確率分布 p(S; G, C, w) に従って部分グラフ S を出力することを目的とする．部 分グラフのサンプリングが効率的に行えれば，_{C(G, C)} のサイズが指数的であっても，評価値の高い部分グラ フを効率的に出力することが可能となる．また部分グ ラフサンプリングが効率的になれば，_{C(G, C) に含ま} れる部分グラフの様々な統計量を効率的に評価可能と なる．f (S) を G の部分グラフ S に関する何らかの評 価関数とする．このとき，f (S) の p(S; G, C, w) に関す る期待値は以下である． E[f|p] = ∑ S∈C(G,C) f (S)p(S; G, C, w) 上式を定義通りに計算すると，_{C(G, C) を計算する必要} があり，一般に指数的な計算コストが必要となる．一 方，部分グラフサンプリングが効率的に行える場合，こ の期待値を以下のサンプル近似によって求めることが できる． E[f|p] ≃ 1 J J ∑ j=1 f (S(j)), S(j)∼ p(S; G, C, w) (j = 1, . . . , J) ここで，S(j)_{は，p(S; G, C, w) より得た j 番目のサン} プルである． 列挙木を用いて部分グラフ集合_{C(G, C) を一旦出力} してしまえば，その結果を用いて p(S; G, C, w) から のサンプリングを正確に行うことが可能である．しか し，その計算量は出力された_{C(G, C) のサイズに比例} し，これは一般的に指数である．そこで本稿では部分 グラフサンプリングを効率的に行うために，列挙木と Markov Chain Monte Carlo (MCMC) 法を組み合わせ た手法を提案する．

3

提案アルゴリズム

3.1

M-H 法による部分グラフサンプリング

本節では，列挙木を用いた効率的な p(S; G, C, w) か らのサンプル法を提案する．本稿ではまず，効率的に サンプリング可能な提案分布 q(S|S(j)_{) を列挙のテク} ニックを用いて構成する．次にこの提案分布 q(S|S(j)₎ を用いて Metropolis-Hasting (M-H) 法を構成すること で，目的分布 p(S; G, C, w) からのサンプリングを実現 する． まず M-H 法の構成法を述べる．S(j) _{を時刻 j での} サンプルとし，S∗ を提案分布 q(S|S(j)_{) から得られた} サンプル候補とする．M-H 法は，サンプル候補 S∗ を 以下の受理確率 A(S(j)_{, S∗) に従って受理または棄却} することで目的分布 p(S; G, C, w) を定常分布に持つ Markov Chain を構成する． A(S(j), S∗) = min { 1, R(S(j), S∗) } , R(S(j), S∗) = p(S ∗_{; G, C, w)} p(S(j)_{; G, C, w)} q(S(j)_|S∗₎ q(S∗|S(j)₎ = exp(w(S∗)− w(S(j)))q(S (j)_|S∗) q(S∗|S(j)₎ 一般的に，提案分布 q(S|S(j)_{) が目的の分布 p(S; G, C, w)} に似ているほど，受理確率 A(S(j)_{, S}∗_{) が高くなる．よっ} て，どのような提案分布 q(S|S(j)_{) を構成するかは重} 要な問題である． 次に提案分布 q(S|S(j)_{) の構成法を述べる．部分グ} ラフ集合_{C(G, C) 上のグラフ H が与えられるとする．} つまり_{H 中のノードは，部分グラフ S ∈ C(G, C) に対} 応する．N+_{(S) をノード S と S に隣接するノードの集} 合とする．このとき，_{H 上のランダムウォーク q(S}′_|S) を以下のように定義する． 1. 現在のノードを S とする． 2. Z =∑_S′_∈N+_(S)exp(w(S)) を計算する． 3. exp(w(S′))/Z の確率で S′∈ N+(S) へ遷移する． 本稿では上記のランダムウォークを提案分布として用 いる．この方法では得られるサンプル候補 S∗は前の時 刻のサンプル S(j) _{に強く依存する．このような M-H} 法は酔歩型と呼ばれる．この酔歩型 M-H 法はサンプ ル候補 S∗を_{|N(S)| に比例する時間で得られるため高} 速である．しかし，酔歩型 M-H 法で得られるサンプル 列は相関が強いため，burn-in によりサンプル列の相 関を弱くする必要がある． 本稿では上記の酔歩型 M-H 法とは別に以下の独立型 M-H 法も考える． 今，H 上のノード上に，非循環な 親子関係が与えられるとし，ch+_{(S) をノード S と S} の子ノードの集合とする．このとき，以下のように提 案分布を構成する． 1. 現在のノードを S とする． 2. Z =∑_S′_∈ch+_(S)exp(w(S)) を計算する． 3. exp(w(S))/Z の確率で S を出力して終了する． 4. exp(w(S′))/Z の確率で S′ ∈ ch+_{(S)\ {S} へ遷} 移し 1. に戻る． 上記の提案分布では，サンプル候補 S∗ が S(j)_に依存 しないため独立型の M-H 法と呼ばれる．独立型 M-H 法は，酔歩型 M-H 法と異なり burn-in は不要である． 一方で，ランダムウォークが停止するまでに時間を要 するため，一回のサンプリングのコストは酔歩型より も高い．本稿では酔歩型と独立型の双方の M-H 法を考 え，実験的に比較する． 上記の提案分布 q(S|S(j)_{) が目的分布 p(S; G, C, w)} に近いほど，受理確率 A(S∗_{, S}(j)_{) は高くなる．提案分} 布の性能はランダムウォークを行うグラフ_{H に依存す} る．_{H が完全グラフである場合，上記の提案分布は目} 的分布と一致するが，サンプリングのコストは非常に 高くなる．ランダムウォークの１ステップの計算量は ノード S のH 上の次数に依存する．そこで本稿では 比較的次数の低い_{H を列挙のテクニックを用いること} で効率的に構成することで効率的な提案分布からのサ ンプリングを実現する．グラフ_{H の構成法に関しては} 次節で述べる．

3.2

グラフ

H の構成

本節では前節で述べた M-H 法を実現するためのグラ フ_{H の構成法を述べる．本稿では列挙木と呼ばれる木} 構造と，それを拡張した束構造の２種類の _{H を考え，} 実験的に比較する． 3.2.1 列挙木 本小節では，列挙木の具体的な構築法を与える．列挙 木とは，頂点集合は探索空間中のすべての要素からなり， かつ，木をなすグラフである．以下では，入力の木 T の 各頂点に，深さ優先探索順に 1 から n の番号を与える． また，この番号と頂点を同一視し，V ={1, . . . , n} とす る．つまり，T 中の k-部分木は，要素数 k の{1, . . . , n} の部分集合と見なせる．_{S(T, k) 中の根を {1, . . . , k} か} らなる k-部分木とする．また，次のように，k-部分木 S の親 U (S) を次のように定義する．

1. S の最小要素 h が h > 1 かつ S ={h, . . . , h + k − 1} のとき，U (S) ={u(h), h, . . . , h + k − 2}．ただ し，u(h) は T 中で h の隣接頂点かつ，h よりも 小さい番号をもつ頂点とする． 2. S がT (T, k) の根でなく，また，1 を満たさないと する．このとき，S の親を U (S) = (S\{ℓ})∪{b} とする．ただし，ℓ と b は以下を満たすものとす る：(i) ℓ を S 中の最大の番号をもつ葉とし，(ii) b を S に対する最小の境界頂点，(iii) (ℓ, b) /∈ T をみたすとする． ここで，_{E(T, k) = {(S, U(S)) | S ∈ S(T, k)} とする．} このとき，_{T (T, k) = (S(T, k), E(T, k)) と定義する．} T (T, k) は，次の定理を満たす． 定理 1 ( [10]). 木 T と正整数 k に対して，T (T, k) は， S(T, k) 中の要素を全て含む木をなす． したがって，_{T (T, k) は S(T, k) の列挙木である．Wasa} ら [10] は，この列挙木をもとに，解 1 つあたり定数時 間で T 中の k-部分木を列挙するアルゴリズムを与えて おり，また，本稿でも [10] で利用されているテクニッ クを提案アルゴリズムを実装時に適用している． 3.2.2 束への拡張 前小節で定義した親 U (S) を，2 に関して，次のよう に拡張する． 2′ S がT (T, k) の根でなく，また，1 を満たさないと する．このとき，S の親を U (S) = (S\{ℓ})∪{b} とする．ただし，ℓ と b は以下を満たすものとす る：(i) ℓ を S 中の葉とし，(ii) b を S に対する境 界頂点，(iii) (ℓ, b) /∈ T をみたすとする． つまり，葉や境界頂点に関する最大や最小の制約を除 いたものである．これにより，定義される_S′_{(T, k) 上} のグラフは，木ではなくなるが，連結であるので，遷 移を繰り返すことで任意の k-部分木へ到達することが できる．

4

計算機実験

本稿では，真の期待値 E[f|p] と，前節で与えたグラ フを基にしたサンプル近似との間に，どの程度の誤差 があるかを評価するための実験を行った．また，実行時 間の比較も行った．実験に用いた計算機の CPU は Intel Core i7，メモリは 16GB，OS は OS X10.11.5，使用し た言語は C++，コンパイラは Apple LLVM ver 7.3.0 である．関数 g としては，k-部分木の高さを用いた．ま た，部分木 S の重み w(S) は，枝の重みの和としており， 枝重みはランダムに与えてある．各 k = 1, . . . , 10, 15 に対して，上段は実際に列挙したときの期待値と計算 時間を，中段は列挙木を用いたときの期待値と計算時 間，下段は束を用いたときの期待値と計算時間を，そ れぞれ，10 回サンプル近似した時の平均をとっている． 示している．また，サンプリングは，すべて 10,000 個 とした．k = 100 以上の時は，全列挙，および，束を 用いたサンプリングアルゴリズムは 1,000 秒を超えた ため，実験が終了しなかった．

4.1

実データ

本実験では，頂点数 4,240 のインフルエンザの進化 系統樹を用いて実験を行った．表 1 は，その実験結果 である．一方で，列挙木を用いたアルゴリズムは，k に 対して非常に遅い速度で計算時間が増加していること がわかる． 実データに対しては，列挙木を用いたアルゴリズム は，束を用いたアルゴリズムと同等のサンプル近似を 示した一方で，実行時間は，列挙木を用いたアルゴリ ズムが高速であった．これは，_{H における各ノードの} 次数が，列挙木を用いたサンプリングアルゴリズムの ほうがより小さいためと考えられる．この挙動は，独 立型および酔歩型両方に見られる傾向である．近似性 能は，独立型が若干良い．

4.2

人工データ

本実験では，頂点数 1,000 のランダムに生成した木 を用いて実験を行った．表 2 は，その実験結果である． 一方で，実データの時と同様に，列挙木を用いたアル ゴリズムは，k に対して非常に遅い速度で計算時間が 増加していることがわかる． 実験の結果，実行時間は列挙木を用いたアルゴリズ ムの方が短かったものの，近似性能は劣っていること がわかる．この挙動は，独立型および酔歩型両方に見 られる傾向である．近似性能は，酔歩型が若干良い．

5

おわりに

本稿では，列挙アルゴリズムで用いられる列挙木と M-H 法とを組み合わせてランダムサンプリングアルゴ リズムを構築した．さらに，ランダムウォークさせるグ ラフの構築法を 2 通り与え，部分木の深さを評価関数 としたときの計算機による性能比較実験を行った．今 後の課題としては，他の評価関数を用いたときに性能 に大きな差がでるか，列挙木と束の中間の構造などが 定義できるか，また，ミキシング時間の理論的な見積 もり等があげられる．

謝辞

九州大学の来嶋秀治准教授ならびに，Johns Hopkins University の永幡裕研究員に多くの有益なご助言を頂 きました．ここに感謝申し上げます．また，本研究の 一部は JST CREST「データ粒子化による高速高精度 な次世代マイニング技術の創出」および JSPS 科研費 基盤 (S) 15H05711 の助成によります．

参考文献

[1] Etienne Birmel´e, Rui Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, and Gustavo Sacomoto. Optimal Listing of Cycles and st-Paths in Undirected Graphs. In

Proceed-ings of SODA 2012, pp. 1884–1896, New Orleans,

LA, USA, 2012.

[2] David Eppstein and Darren Strash. Listing All Maximal Cliques in Large Sparse Real-World Graphs. In Proceedings of ESA 2011, Vol. 6630 of

Lecture Notes in Computer Science, pp. 364–375,

2011.

[3] Rui Ferreira, Roberto Grossi, Romeo Rizzi, Gus-tavo Sacomoto, and Sagot Marie-France. Amor-tized ˜O(|V |) -Delay Algorithm for Listing

Chord-less Cycles in Undirected Graphs. In Proceedings

of ESA 2014, Vol. 8737 of Lecture Notes in Com-puter Science, pp. 418–429, Wroclaw, Poland,

2014. Springer Berlin Heidelberg.

[4] Thomas G¨artner, Peter A. Flach, and Stefan Wrobel. On Graph Kernels: Hardness Results and Efficient Alternatives. In Proceedings of

COLT/Kernel 2003, pp. 129–143, 2003.

[5] Masakazu Ishihata and Taisuke Sato. Bayesian inference for statistical abduction using Markov chain Monte Carlo. In Proceedings of ACML

2011, Vol. 20, pp. 81–96, 2011.

[6] Ronald C. Read and Robert Endre Tarjan. Bounds on backtrack algorithms for listing cy-cles, paths, and spanning trees. Networks, Vol. 5, No. 3, pp. 237–252, 1975.

[7] John Shawe-Taylor and Nello Cristianini. Kernel

Methods for Pattern Analysis. Cambridge

Uni-versity Press, 2004.

[8] Akiyoshi Shioura, Akihisa Tamura, and Takeaki Uno. An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs. SIAM Journal on Computing, Vol. 26, No. 3, pp. 678–

692, June 1997.

[9] Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. A New Algorithm for Gener-ating All the Maximal Independent Sets. SIAM

Journal on Computing, Vol. 6, No. 3, pp. 505–

517, September 1977.

[10] Kunihiro Wasa, Yusaku Kaneta, Takeaki Uno, and Hiroki Arimura. Constant Time Enumera-tion of Subtrees with Exactly k Nodes in a Tree.

IEICE Transactions, Vol. 97-D, No. 3, pp. 421–

430, 2014.

[11] 石畠正和, 佐藤泰介. モンテカルロ木探索を利用 した制約付き分布からの効率的なサンプリング法. 人工知能学会第 88 回人工知能基本問題研究会予 稿集, SIG-FPAI-B203, pp. 125–131, 2013.

独立型 酔歩型 k 部分木の数 E [f |p ] 時間 [秒 ] E [f |p ] 時間 [秒 ] 2 4,239 1.0000 0.0170 1.0000 0.0170 列挙木 1.0000 0.0840 1.0000 0.1452 束 1.0000 0.5766 1.0000 0.5725 3 6,357 1.6666 0.0223 1.6666 0.0223 1.8903 0.2020 1.7172 0.1985 1.8450 0.9000 1.0030 0.0784 4 10,591 2.3999 0.0361 2.3999 0.0361 2.4879 0.2199 2.4643 0.2130 2.4178 1.1597 2.4100 1.3582 5 19,256 2.9895 0.0720 2.9895 0.0720 3.0738 0.2286 3.0486 0.2146 3.0654 1.3936 2.0068 0.0899 6 37,370 3.5609 0.1385 3.5609 0.1385 3.8167 0.2588 3.6594 0.2167 3.6939 2.1944 3.5774 2.4938 7 76,396 4.0785 0.2517 4.0785 0.2517 4.5083 0.2822 4.3042 0.2194 4.3191 2.5942 3.0354 0.1743 8 163,025 4.5514 0.5543 4.5514 0.5543 4.8906 0.2938 5.1429 0.2195 4.7945 2.8677 4.5844 4.1129 9 360,796 4.9931 1.2790 4.9931 1.2790 4.9600 0.3047 5.8668 0.2287 5.1574 3.2619 3.3286 0.1659 10 823,951 5.4071 2.8017 5.4071 2.8017 5.2707 0.3180 6.0478 0.2170 5.6519 4.1566 5.4592 6.1312 15 72,576,397 7.1618 254.5740 7.1618 254.5740 7.9918 0.3686 10.0500 0.2169 8.3774 9.7114 7.2110 12.5728 100 列挙木 25.9970 0.7434 26.0000 0.2761 200 列挙木 25.9973 0.8646 26.0000 0.2967 500 列挙木 39.9977 1.2091 40.0000 0.4106 表 1: 実データに対するのサンプル近似の実験結果．サンプル数は 10,000 ． 独立型 酔歩型 k 部分木の数 E [f |p ] 時間 [秒 ] E [f |p ] 時間 [秒 ] 2 999 1.0000 0.0009 1.0000 0.0009 1.0000 0.0178 1.0000 0.0427 1.0000 0.3076 1.0000 0.0173 3 2,509 1.3925 0.0019 1.3925 0.0019 1.8284 0.0616 1.4248 0.0465 1.4521 0.6225 1.9998 0.0179 4 8,794 1.8333 0.0063 1.8333 0.0063 2.4479 0.0910 2.0395 0.0470 1.9527 1.1825 2.9893 0.0262 5 38,043 2.1990 0.0272 2.1990 0.0272 2.7683 0.1086 2.3688 0.0533 2.3099 2.0492 1.6867 0.2003 6 199,692 2.4743 0.1493 2.4743 0.1493 3.5070 0.1113 2.6154 0.0497 2.5967 3.1931 2.0758 0.5201 7 1,199,428 2.7063 0.9550 2.7063 0.9550 4.3677 0.1082 2.5773 0.0489 2.9095 4.6133 2.6865 4.2299 8 7,839,474 2.9102 6.4844 2.9102 6.4844 4.3592 0.1285 3.9167 0.0544 3.0708 6.9290 2.9072 7.2832 9 54,094,935 3.0788 44.5174 3.0788 44.5174 4.4442 0.1334 3.0798 0.0504 3.2135 9.5387 3.0807 10.2261 10 385,737,210 3.2104 333.5360 3.2104 333.5360 4.4372 0.1508 4.0063 0.0507 3.3250 13.1763 3.2184 13.8164 100 列挙木 5.9977 0.4132 6.0000 0.0817 200 列挙木 6.0000 0.6441 6.0000 0.1115 500 列挙木 9.9999 1.3690 9.9000 0.1957 表 2: 人工データに対するサンプル近似の実験結果．サンプル数は 10,000 ．