修士学位論文

(1)

修士学位論文

題名

ランダムなビット列における連：ブール決定木の複雑さと道路区画への応用

指導教授鈴木登志雄准教授

平成２１年１月９日提出

首都大学東京大学院

理工学研究科数理情報科学専攻

氏名川村保敬

(2)

(3)

学位論文要旨（修士（理学））

ランダムなビット列における連：

ブール決定木の複雑さと道路区画への応用

川村保敬

07878307

首都大学東京大学院理工学研究科数理情報科学専攻平成

21

年

1

月

9

日

文字列ＡＡＢＢＢＣにおけるＡＡやＢＢＢのように，同じ文字が続く極大な部分文字列を連という．文字列のランダム性と連の関係については多くの研究が知られている．本論文は弱いランダム性と連の関係について研究したものであり，二部構成からなる．第一部（第２章）では弱いランダム性をもつビット列，およびそれをブール決定木で変換したビット列における連の分布を研究する．また，第二部（第３章）では，道路区画の複雑さを数値化する計算機実験に，連の概念を応用する．

第一部（第２章）では，ブール決定木（葉から根へのブール関数とみなす）が弱いランダム性を保存するという鈴木の研究

[ Bull. Symb. Logic , to appear]

を発展させ，「弱いランダム性をもつ無限ビット列において，連の長さの分布はどのようになっているか」という問題と「弱いランダム性をもつ無限ビット列をブール決定木で変換して得られる無限ビット列において，連の長さの分布はどのようになっているか」という問題に対して，理論的な答えを与える。

与えられたオラクル

X

を無限ビット列とみなし，その最初の

n

ビットの始切片において，連の総数に対する長さ

`

の連の個数の比率に注目し，Xと

`

を固定したまま

n

を無限大に飛ばして上記比率の極限を考察する．特にマーティンレフ・ランダムなオラクルにおいて，上記極限は

2

の

−`

乗であることを示す．

また，ブール決定木（kラウンドの

AND-OR

木）のコピーを並べた系列を葉から根への写像とみなす．この写像によってマーティンレフ・ランダムなオラクルから

1

(4)

得られるオラクルにおいて，上記比率の極限が以下の通りとなることを示す．

p

^`_k⁻¹

(1 − p

k

) + p

k

(1 − p

k

)

^`⁻¹

2 ,

ただし

p

kは

[Liu-Tanaka, Inform. Process. Lett. 2007]

で与えられた確率であり，以下の漸化式で定まる：

p

0

=

¹₂

, p

k+1

= −p

⁴k

+ 2p

²k

.

第二部（第３章）では，地図の道路区画の複雑さを数値化する指標の鈴木との共同研究について述べる．ここでは特に，相似拡大について不変であるような指標について研究する．閉曲線で囲まれた図形（以下区画という）の印象の複雑さを表す量の一つとして，実験心理学では周二乗面積比が研究されている．この比は相似拡大について不変であるという点でファイル圧縮サイズ（を複雑さの尺度とした場合）

にない強みを持つ．我々は世田谷区・目黒区の道路中心線の地図を正方形分割し，

各々の小正方形領域ごとに指標

I

1（道路で囲まれた土地区画ごとの周二乗面積比を土地区画の面積で加重平均した量）を調べた．しかし指標

I

1のみでは，たとえば以下の３つの図の複雑さを判別することが出来ない．

そこで，区画面積の分散を修正した量

I

2と連の長さの分散を修正した量

I

3に着目した．三つの指標

I

1

, I

2

, I

3を（それぞれが

0

から

100

の間の値をとるように）一次式で変換した値

I

₁⁰

, I

₂⁰

, I

₃⁰ の平均値を，三指標平均値と呼ぶ．三指標平均値を指標として用いたところ，より自然な形で３つの図の複雑さを判別することができた．

この三指標平均値を用いて，地図の色を塗り分けることにより，複雑さを可視化した．まず地図を正方形領域に分割する．各正方形領域の三指標平均値を計算し，累積度数によって六段階に塗り分ける．この際色を塗り分けた正方形領域は，その領域の周囲の値も考慮して計算している．また，この三指標平均値と

I

₃⁰ には強い相関関係（相関係数：約

0.92

）があることも分かった．

2

(5)

ランダムなビット列における連：

ブール決定木の複雑さと道路区画への応用

川村保敬

首都大学東京大学院理工学研究科数理情報科学専攻

平成

21

年

2

月

13

日

(6)

(7)

i

第 1 ^章 ^序

1.1 確率分布としては捉えにくいランダム性を研究する

文字列ＡＡＢＢＢＣにおけるＡＡやＢＢＢのように，同じ文字が続く極大な部分文字列を連という．文字列のランダム性と連の関係については多くの研究が知られている．本論文は弱いランダム性と連の関係について研究したものであり，二部構成からなる．第一部（第２章）では弱いランダム性をもつビット列，およびそれをブール決定木で変換したビット列における連の分布を研究する．また，第二部（第３章）では，道路区画の複雑さを数値化する計算機実験（鈴木との共同研究）に，連の概念を応用する．

第二部における「弱いランダム性」とは，（東京の住宅街の）道路区画のもつ不規則性である．一方，第一部における「弱いランダム性」とは，計算機プログラムで表現できるいかなるランダム性の検定にも合格するという性質を表し，より正確に言うとマーティンレフのランダム性（後述）である．古典的な確率論におけるベルヌイ列の概念によって，たとえば

0000000000· · ·

と

0110100010· · ·

を区別することはできない．一方，マーティンレフのランダム性（および，それと密接に関係するコルモゴロフ計算量）は個々のビット列の複雑さの程度を表す概念であり，上記の区別を可能とするものである．

第一部（第２章）では，ブール決定木（葉から根へのブール関数とみなす）が弱いランダム性を保存するという鈴木の研究[3]を発展させ，

「弱いランダム性をもつ無限ビット列において，連の長さの分布はどのようになっているか」

という問題と

(12)

2 第1章序

「弱いランダム性をもつ無限ビット列をブール決定木で変換して得られる無限ビット列において，連の長さの分布はどのようになっているか」

という問題に対して，理論的な答えを与える。

1.2 ^{第一部の概要}

ブール決定木は，ゲーム理論や人工知能において，重要な研究テーマである．特にリーフにある確率分布のオラクルを張りつけた場合については[4]をはじめ，広く研究されている．本論文では，確率分布の代わりにマーティンレフ・ランダムなオラクルを与えた場合について考察した．

与えられたオラクルXを無限ビット列とみなし，その最初のnビットの始切片において，連の総数に対する長さの連の個数の比率に注目し，Xとを固定したままnを無限大に飛ばして上記比率の極限を考察する．

特にマーティンレフ・ランダムなオラクルにおいて，上記極限は2の−乗であることを示す．

また，ブール決定木（kラウンドのAND-OR木）のコピーを並べた系列を葉から根への写像とみなす．この写像によってマーティンレフ・ランダムなオラクルから得られるオラクルにおいて，上記比率の極限が以下の通りとなることを示す．

p⁻¹_k (1−pk) +pk(1−pk)⁻¹

2 ,

ただしpkは[4]で与えられた確率であり，以下の漸化式で定まる．

p0=1

2, pk+1=−p⁴_k+ 2p²_k.

1.3 ^{第二部の概要}

第二部（第３章）では，地図の道路区画の複雑さを数値化する指標の鈴木との共同研究について述べる．ここでは特に，相似拡大について不変であるような指標について研究する．閉曲線で囲まれた図形（以下区画という）の印象の複雑さを表す量の一つとして，実験心理学では周二乗面積比が研究されている．この比は相似拡大について不変であるという点でファイル圧縮サイズ（を複雑さの尺度とした場合）にない強みを持つ．我々

(13)

1.3. 第二部の概要 3

は世田谷区・目黒区の道路中心線の地図[12]を正方形分割し，各々の小正方形領域ごとに以下の指標I₁（道路で囲まれた土地区画ごとの周二乗面積比を土地区画の面積で加重平均した量）を調べた．

I₁:=

_N

i=1P_i² AiAi

A =

_N

i=1P_i²

A ,

ただし第i土地区画の周の長さがP_iで面積がA_i，そしてA=_N

i=1A_iである．

しかし指標I₁のみでは，たとえば以下の図1.1，1.2，1.3の複雑さを判別することが出来ない．

図1.1: 図 1.2: 図1.3:

そこで，区画面積の分散を修正した量I₂と連の長さの分散を修正した量I₃に着目した．三つの指標I₁, I₂, I₃ を（それぞれが0から100の間の値をとるように）一次式で変換した値I₁, I₂, I₃の平均値を，三指標平均値と呼ぶ．三指標平均値を指標として用いたところ，より自然な形で図1.1，1.2，1.3の複雑さを判別することができた．

この三指標平均値を用いて，地図の色を塗り分けることにより複雑さを可視化することを考える．まず，地図を正方形領域に分割する．各正方形領域の三指標平均値を計算し，累積度数によって六段階に塗り分ける．

この際色を塗り分けた正方形領域は，その領域の周囲の値も考慮して計算している．

また，この三指標平均値とI₃ には強い相関関係があることも分かった．

(14)

4 第1章序

1.4 ^発表実績

第一部（第２章）の研究を，京都大学数理解析研究所で行われた短期共同研究「証明論と論理・計算の構造」

（2008年9月）で発表した．またこの研究の経過報告書が京都大学数理解析研究所講究録[8]に掲載予定である（発表・報告書ともに鈴木登志雄との連名）．

第二部（第３章）の研究を，以下で発表した．首都大学東京南大沢キャンパス 9号館1階アトリウムで行われた「首都大学東京南大沢キャンパス産学公交流会2008 ポスターセッション」(2008年7月)．首都大学東京国際交流会館で行われた「首都大学東京平成20年度研究教育交流会ポスターセッション」(2008年10 月)(この２つのポスターセッションは，鈴木登志雄と共同発表)．

(15)

5

第 2 ^章 ^{ブール決定木の複雑さ}

2.1 ^序

ブール決定木のリーフ（葉，leaf）に固定した真理値を与える代わりに真理値の確率分布を与えたものを「ランダム化されたブール決定木」という．この概念は [4]など多くの文献で研究されている．

鈴木は確率分布の代わりにマーティンレフ・ランダムなオラクルを与えた場合について考察した．すなわち，

ブール決定木可算無限個のコピーを，リーフのオラクルからルート（根，root）のオラクルへの写像と見なし，

このような写像がランダム性を保存するか調べた．そして，マーティンレフのランダム性は保存されないが，

その必要条件は保存されることを示した．[3]

著者は，鈴木のこの条件の他にも，どんなランダム性がこの種の写像で保存されるか，特に連についてどんな性質が保存されるかについて興味があり，研究を進めている．本章で述べるのはこの研究の準備作業であり，

ブール決定木による写像で写す前の，リーフ・ビット列における連の長さの分布と，写像した後のルート・ビット列における連の長さの分布についての報告である．

著者は．まず計算機実験を行って予想を立てた．疑似乱数によって長いビット列X(0), X(1),· · ·, X(n−1) を生成し，連の長さについて以下の近似式が成り立つことを観察した．ただし，iはnに比べて小さい自然数である．

X(0), X(1),· · · , X(n−1)における長さiの連の個数 X(0), X(1),· · ·, X(n−1)における連の個数 1

2ⁱ

(16)

6 第2章ブール決定木の複雑さ

そこで，「Xがマーティンレフ・ランダムなオラクルでiが正の整数であるとき，上記の式左辺の極限（n→ ∞）が右辺に等しい」と予想した．この予想が成り立つことを第4節で示す．

また，kラウンドのAND-OR木によってマーティンレフ・ランダムなオラクルを写像して得られるオラクルにおいて，上記比率の極限が以下の通りとなることを示す．

pⁱ⁻¹_k (1−p_k) +p_k(1−p_k)ⁱ⁻¹

2 , (2.1.1)

ただしp_kはkラウンドのAND-OR木の各リーフに，確率1

2 ずつで値1と0をとる，一様で独立な確率分布を与えたときに，ルートが値1をとる確率である．このpkの値は以下の漸化式で定まることが，[4]において示されている．

p0=1

2, pk+1=−p⁴_k+ 2p²_k.

第4節での議論を発展させることにより，第5節において(2.1.1)についての結果を示す．

第2節では用語と記号の説明を行い，第3節では実験について説明する．

2.2 ^{用語と記号}

非負整数全体の集合をωで表す．長さ有限のビット列全体の集合を{0,1}^∗で表す．また，ωから{0,1}への関数をオラクルといい，オラクル全体の集合を{0,1}^ωで表す．

ビット列111001111において，111と00および1111を連という．一般的な定義は次の通りである．

定義1 ビット列において，同じ文字が連続して現れる部分で，極大となるものを，連(run)という．

次に，マーティンレフ・ランダム性について述べる．「ランダム性についての統計的検定のうち，計算機のプログラムで表せるようなものすべてに合格するようなオラクル」という概念の数学的モデルには，「計算機のプログラムで表せるようなもの」という部分をどう定式化するかに応じて様々な変種がある．その中でも代表的なものがマーティンレフ・ランダム性である[5]．

定義2 [2, Def.3.1]集合族A ⊆ {0,1}^ωがマーティンレフ零（null）集合(あるいはΣ⁰₁零集合)であるとは，Σ⁰₁ 集合の一様に再帰的可算（recursively enumerable,あるいはcomputably enumerable）な列{Ui}i∈ωであって

(17)

2.2. 用語と記号 7

「∀i∈ω(μ(Ui)≤2⁻ⁱ)」となるもの(マーティンレフ・テストとよばれる)が存在して，「A ⊆

iUi」となることをいう. オラクルAについて，{A}がΣ⁰₁零集合でないとき，「Aはマーティンレフ・ランダム（Martin-L¨of

random）である」，あるいは「1ランダムである」という．

上記定義における「Σ⁰₁集合の一様に再帰的可算な列{U_i}_i∈ω」という部分の意味は次の通りである．あるオラクル・チューリング機械M^∼（停止性についての保証はない）があって，任意のオラクルX と任意の自然数iに対して以下が成り立つ．

X∈U_i if and only ifM^X(i) = 1.

マーティンレフ・ランダム性の定義は，以下に述べる構成的零集合（constructive null set）の概念を用いて特徴付けられる．

定義3 [1, Def.6.26]

• 開集合 G ⊂ {0,1}^ω が構成的開集合（constructively open set）であるとは，ある再帰的可算な集合 X ⊂ {0,1}^∗に対してG=X{0,1}^ωとなることをいう．

• 構成的開集合G_m=X_m{0,1}^ωの列{G_m}_m≥1について以下の条件が成り立つとき，{G_m}_m≥1を「構成的開集合の構成的な列(constructive sequence of constructively open sets,略してc.s.c.o. sets)」という．「再帰的可算集合X ⊂ {0,1}^∗×ωが存在して，すべての自然数m≥1に対して，

X_m={x∈ {0,1}^∗: (x, m)∈X}

となる」．

• S⊂ {0,1}^ωが構成的零集合（constructively null set）であるとは，c.s.c.o. sets{Gm}m≥1が存在して，

以下が成り立つことをいう．

S⊂

m≥1

Gmかつ，

構成的に lim

m→∞μ(G_m) = 0.

ただし，「構成的にlim_m→∞μ(Gm) = 0」とは，単調増加で有界でない計算可能な関数H :ω →ωが存在して，任意の自然数m, kに対し「m≥H(k)ならばμ(Gm)<2^−k」となることをいう．

(18)

定理 1 [1]Xがマーティンレフ・ランダム ⇐⇒ 任意の構成的零集合Sに対して，X∈Sとなる．

構成的零集合について，以下の結果が知られている．ここで「=」は「左辺が発散するか，または右辺と異なる値に収束する」ことを表す．これは，強い意味での大数の法則とみることができる．

定理2 [1, p.173, Theorem 6.27]以下の集合Y は構成的零集合である．

Y ={X ∈ {0,1}^ω: lim

n→∞

X(0) +X(1) +· · ·+X(n−1)

n =1

2} 定理2は，チェルノフ限界（Chernoﬀ bound）を用いて証明される．

定理 3 チェルノフ限界[7, p.258, Lemma 11.9]X₀, X₁,· · ·, X_n−1の各々を，確率pで1または0をとる独立な確率変数とする．このとき任意のθ（ただし0≤θ≤1）に対して以下が成り立つ．

P rob[X₀+X₁+· · ·+X_n−1≥(1 +θ)pn]≤exp (−θ² 3pn) 本章では，構成的零集合の概念を利用して主要な結果を示す．

2.3 ^実験

ブール決定木のコピーを並べた系列をリーフのビット列からルートのビット列への写像とみなし，リーフとルートにおける連の長さの分布を調べる計算機実験を行った．実験は，以下の条件のもとに行われた．

• ブール決定木としては，図 2.1にあるようなAND-OR木を用いた．

• ルートからなるビット列が128ビットである場合について調べた．

• リーフには，疑似乱数を与えた．

木の深さ（depth）と似た概念としてラウンド（round）[4]というものを導入する．ブール決定木のコピーを並べた系列によってビット列を一回変換することを１ラウンドとよぶことにする．図2.2は2ラウンドの木を並べた例である．

(19)

2.3. 実験 9

図2.1: 木のコピーを並べた系列

図 2.2: 2ラウンドの木を並べた例

(20)

図 2.3，2.4はそれぞれ，リーフ・ビット列とルート・ビット列（5ラウンド）における連の長さの分布を表す．時計の針の３時の位置から反時計回りの順に，（連の総数に対する）長さ1の連の（個数の）比率，長さ2 の連の比率，· · · を表す．

図2.3: リーフの連の長さの分布図 2.4: ルートの連の長さの分布（5ラウンド）

疑似乱数によって生成されたリーフのビット列X(0), X(1),· · · , X(n−1)において，以下の近似式が成り立つことが観察される．ただし，nは2¹⁷(= 4⁵×128)であり，iはnに比べて小さい自然数である．

X(0), X(1),· · · , X(n−1)における長さiの連の個数 X(0), X(1),· · ·, X(n−1)における連の個数 1

2ⁱ

2.4 マーティンレフ・ランダムなオラクルにおける連の分布

前節の実験に基いて，以下の命題を予想した．

命題 4 Xがマーティンレフ・ランダムなオラクルでiが自然数であるとき，以下が成り立つ．

n→∞lim

X(0)X(1)· · ·X(n−1)における長さiの連の個数 X(0)X(1)· · ·X(n−1)における連の個数 = 1

2ⁱ 以下で上記を証明する．次の補題が証明の鍵となる．

(21)

2.4. マーティンレフ・ランダムなオラクルにおける連の分布 11

補題 5 任意の正の整数iに対し，以下の集合Yは構成的零集合である．

Y :={X ∈ {0,1}^ω: lim

n→∞

X(0)X(1)· · ·X(n−1)における長さiの連の個数 X(0)X(1)· · ·X(n−1)における連の個数 = 1

2ⁱ}

上記補題を証明するため，準備をしよう．まず，与えられたオラクルX に対して，以下のように rn, rn,i

（i= 1,2,3,· · ·）を定める．

rn := (X(0)X(1)· · ·X(n−1)における連の個数),

rn,i := (X(0)X(1)· · ·X(n−1)における長さiの連の個数).

さらにここで，

Y∞ := {X ∈ {0,1}^ω: lim

n→∞

rn

n =1 2}, Yi := {X ∈ {0,1}^ω: lim

n→∞

r_n,i

n = 1

2ⁱ⁺¹}.

とおく．これらがいずれも構成的零集合であることを示したい．

補題6 Y_∞は構成的零集合である．

証明オラクルXと各々の自然数jに対し，以下のようにy_jを定める．

y_j=

⎧⎪

⎪⎪

⎪⎨

⎪⎪

⎩

1 ifX(j)が連の右端 0 otherwise

ここで，「yj= 1」となるための必要十分条件は「X(j+ 1)=X(j)」である．このとき，任意のオラクルX に対して以下が成り立つ．ただし，ここで「」は「左辺が収束するとき，かつ，そのときに限り右辺が収束して，そのとき両辺の値が一致する」ということを表す．

n→∞lim

y₀+y₁+· · ·+y_n−2

n−1 lim

n→∞

r_n n X の各ビットを独立に1

2 の確率で0,1のいずれかに決めるとき，jに関して独立に，yjは 1

2 の確率で0,1 の値をとる．したがって，定理2の証明と同様にして（チェルノフ限界を用いて）Y∞が構成的零集合であることを示せる．Q.E.D.

(22)

補題 7 任意の構成的零集合S₁，S₂に対して，S₁∪S₂も構成的零集合である．

証明構成的零集合の定義にしたがって容易に確認できる．Q.E.D.

補題8 任意の正の整数iに対して，Yiは構成的零集合である．

補題8もチェルノフ限界を用いて証明したいのであるが，チェルノフ限界は独立な事象についての定理である．そこで，無限ビット列としてのオラクルを長さi+ 2の区間に分割することによって，証明を独立な事象についての議論に還元する．

補題 8の証明まず0≤s < i+ 2となる自然数sを固定する．

s≤j <(i+ 2)n+sかつj≡smod (i+ 2) (2.4.1)

となる自然数jの各々に対して，y_s,jを以下のように定める．

ys,j =

⎧⎪

⎪⎪

⎪⎨

⎪⎪

⎩

1 ifX(j+ 1)が長さiの連の左端

0 otherwise ここで，「y_s,j= 1」となるための必要十分条件は

X(j)=X(j+ 1) =X(j+ 2) =· · ·=X(j+i)=X(j+i+ 1)

である．Xの各ビットを独立に 1

2の確率で0,1のいずれかに決めるとき，jに関して独立にy_s,j は確率 1 2ⁱ⁺¹ で値1をとる．よって，定理2と同様にチェルノフ限界を用いて，以下の集合Y_i,sが構成的零集合であることを示せる．ここで「=」は，左辺が発散するか，または右辺と異なる値に収束することを表す．

Yi,s:={X: lim

n→∞

jys,j

n = 1

2ⁱ⁺¹}

ただし，総和記号は（s, nを固定して）(2.4.1)をみたすすべてのjに渡る和である．以下の議論では，sの固定を解除する．

したがって補題7により，Yi,0∪ Yi,1∪ · · · ∪ Yi,i+1は構成的零集合である．ここで，以下が成り立つ．ただしは集合の濃度を表す．また，変数kは非負整数を表し，「≡」はi+ 2を法とした合同関係を表す．

(23)

2.5. MLランダムなオラクルを木で写像したオラクルにおける連の分布 13

(Y_i,0∪ Y_i,1∪ · · · ∪ Y_i,i+1)^c=Y_i,0^c ∩ Y_i,1^c ∩ · · · ∩ Y_i,i+1^c

={X : 0≤ ∀s < i+ 2 lim

n→∞

jy_s,j

n = 1

2ⁱ⁺¹}

={X : 0≤ ∀s < i+ 2

n→∞lim

{k <(i+ 2)n:X(k+ 1)は長さiの連の左端かつk≡s}

n = 1

2ⁱ⁺¹}

⊆{X : lim

n→∞

{k <(i+ 2)n:X(k+ 1)は長さiの連の左端}

(i+ 2)n = 1

2ⁱ⁺¹}

=Y_i^c

したがって，Y_iは構成的零集合Y_i,0∪ Y_i,1∪ · · · ∪ Y_i,i+1の部分集合であり，ゆえにY_iは構成的零集合である．Q.E.D.

補題 5の証明 Y ⊂ Y_∞∪Y_iであるから，補題6と補題8によって補題5が成り立つことがわかる．Q.E.D.

命題 4の証明補題5と定理1により，命題4が成り立つことがわかる．Q.E.D.

2.5 ML ランダムなオラクルを木で写像したオラクルにおける連の分布

定理9 （主定理） iとkは自然数であるとする．ブール決定木のコピーを無限個（ω個）並べた系列を葉から根への写像とみなす．kラウンドのAND-OR木によってマーティンレフ・ランダムなオラクルXを写像して得られるルートのオラクルY に対して，以下が成り立つ．

n→∞lim

Y(0)Y(1)· · ·Y(n−1)における長さiの連の個数 Y(0)Y(1)· · ·Y(n−1)における連の個数

=pⁱ⁻¹_k (1−pk) +pk(1−pk)ⁱ⁻¹

2 ,

ただしp_kはkラウンドのAND-OR木の各リーフに，確率 1

2 ずつで値1と0をとる一様で独立な確率分布を与えたときに，ルートが値1をとる確率である．このp_kの値は以下の漸化式で定まることが，[4]において示

(24)

されている．

p₀=1

2, p_k+1=−p⁴_k+ 2p²_k.

以下で証明の概略を述べる．本節の残りの部分において，i, kは自然数とし，pは上記のp_kを表すものとする．また，与えられたオラクルX に対し，kラウンドのAND-OR木によってXを写像したオラクルをY で表す．

まず，与えられたオラクルX とa∈ {1,0}に対して，以下のようにr_n^a, r^a_n,i（i= 1,2,3,· · ·）を定める．

r_n^a := (Y(0)Y(1)· · ·Y(n−1)において，文字aからなる連の個数),

r^a_n,i := (Y(0)Y(1)· · ·Y(n−1)において，文字aからなる長さiの連の個数).

また，オラクルのクラスZ,Z⁰,Z¹を以下のように定める．

Z := {X∈ {0,1}^ω: lim

n→∞

rn,i

r_n = pⁱ⁻¹(1−p) +p(1−p)ⁱ⁻¹

2 },

Z⁰ := {X ∈ {0,1}^ω: lim

n→∞

r⁰_n,i

r⁰_n =p(1−p)ⁱ⁻¹}, Z¹ := {X ∈ {0,1}^ω: lim

n→∞

r¹_n,i

r¹_n =pⁱ⁻¹(1−p)}.

補題 10 任意のオラクルXに対して以下が成り立つ．

(1) r_n =r¹_n+r_n⁰. (2) r_n,i=r¹_n,i+r⁰_n,i. (3)

n→∞lim rn=∞ ならば lim

n→∞

r¹_n r⁰_n = 1.

証明定義により，容易に確認できる．Q.E.D.

補題 11 (1)Z¹は構成的零集合である．

(2) Z⁰は構成的零集合である．

(25)

2.5. MLランダムなオラクルを木で写像したオラクルにおける連の分布 15

証明の概略 (1)Z_∞¹ ,Z_i¹を以下のように定める．

Z_∞¹ := {X ∈ {0,1}^ω: lim

n→∞

r¹_n

n =p(1−p)}, Z_i¹ := {X ∈ {0,1}^ω: lim

n→∞

r¹_n,i

n = (1−p)²pⁱ}

前節と同様の議論により，これら二つのクラスは構成的零集合であることから，Z¹が構成的零集合であることがわかる．つまり，(1)が成り立つ．

(2)の証明は(1)と同様である．Q.E.D.

定理9（主定理）の証明補題11によりZ⁰∪Z¹は構成的零集合である．したがって定理1により，Z⁰∪Z¹ の任意の要素はマーティンレフ・ランダムではない．

また，{rn :n∈ω}が有界となるX全体のクラスをZ²とおく．Z²の任意の要素は，再帰的（計算可能）であるから，マーティンレフ・ランダムではない．

ところが補題10により，Z ⊆ Z⁰∪ Z¹∪ Z²が成り立つ．したがって定理9が成り立つ．Q.E.D.

なお，定理9は前節の実験結果（図2.4）と整合する．

(26)

(27)

17

第 3 章道路区画の複雑さへの応用

3.1 ^序

本章では東京都内，特に世田谷区，目黒区周辺の住宅街¹ からサンプルを拾い，道路区画の複雑さを数値化する指標のうち特に，相似拡大について不変な指標（道路で囲まれた区画面積の平均値に依存しない指標）を研究する．

計算複雑さの研究者の間では，圧縮ファイルのサイズが大きい情報ほど複雑とみなす考え方がよく知られている[11]．しかし圧縮ファイルのサイズという指標は，図形の相似拡大の影響を強く受ける．特にほぼ合同な長方形の区画が並ぶ地域であっても区画面積の平均値が小さいと圧縮ファイルのサイズは大きくなる傾向がある．この点で，圧縮ファイルサイズは道路区画の複雑さをあまりよく反映しない．たとえば，国土地理院が発行するＣＤ−ＲＯＭ版の数値地図[12]から成城６丁目，梅ヶ丘１丁目，若林３丁目の道路中心線を抽出してモノクロBMPファイルを作り（図3.1，3.2，3.3），これらを同じ圧縮ソフト（zip）の同じ設定の下で圧縮したところ，圧縮後のファイルサイズはそれぞれ2.07KB，3.24KB，3.16KBであった．

1世田谷区，目黒区周辺の住宅街は歴史と交通手段の面で多様性がみられ，興味深い．近世江戸の近郊農村の道路の名残をとどめる住宅街（例，世田谷区若林），関東大震災直後の帝都復興計画の時代前後に成立した住宅街（例，世田谷区奥沢，大田区田園調布），特別区の区域に最後に編入された新しい住宅街（例，世田谷区成城），昭和のオリンピック道路の影響を強く受けた地域（世田谷区駒沢，目黒区柿の木坂）など，様々な時代の都市形成の痕跡を観察することができる．また，東急，小田急などの私鉄の駅まで徒歩10分以内の住宅街が多い一方で，駅からは徒歩15分を越える距離を置き，環状８号線などの幹線道路を自家用車によって移動することを前提として発展した住宅街もある（例，世田谷区用賀）．

(28)

18 第3章道路区画の複雑さへの応用

図3.1: 成城６丁目図 3.2: 梅が丘１丁目図 3.3: 若林３丁目

図3.1 図3.2 図3.3 圧縮後のファイルサイズ（KB） 2.07 3.24 3.16

I₁ （周二乗面積比に基づく量） 36.01 40.39 77.31 I （三指標I₁,I₂,I₃ 加重平均） 51.63 68.48 175.15

一方，実験心理学では２０世紀半ば以降，たびたび閉曲線で囲まれた図形に対する複雑さの心証についての実験と分析がなされている[9, 10, 13]．特にAttneave とArnoultは，相似拡大で不変な量として閉曲線の周の長さの二乗と閉曲線が囲む面積の比に注目した．以下ではこれを周二乗面積比とよぶ．道路中心線の地図の複雑さを調べる場合，上記の比は相似拡大について不変である点において，ファイル圧縮サイズにない強みを持つ．我々は世田谷区・目黒区の道路中心線の地図[12]を正方形分割し，各々の小正方形領域ごとに以下の指標I₁（道路で囲まれた土地区画ごとの周二乗面積比を土地区画の面積で加重平均した量）を調べた．

I₁:=

_N

i=1P_i² AiAi

A =

_N

i=1P_i²

A ,

ただし第i土地区画の周の長さがP_iで面積がA_i，そしてA=_N

i=1A_iである．

指標I₁は図3.4，3.5のような相似拡大した図形に対しては不変である．しかし図3.6と比べると，図3.6のほうが高い値を示す．つまり，複雑さを判別することができる．

(29)

3.1. 序 19

図3.4: 図 3.5: 図3.6:

しかし，指標I1では図3.6，3.7の図形の複雑さを判別することはできない．これは，すべての区画が合同な図形から形成されているからである．

図3.6: （再掲）図 3.7:

また図3.7，3.8の図形についても，複雑さを判別することはできない．

(30)

図3.7: （再掲）図 3.8:

そこで，区画面積の分散を修正した量I2と連の長さの分散を修正した量I3に着目した．周二乗面積比は２次元の量と１次元の量の比として定義されている．区画面積の分散を修正した量は２次元の量に関わる複雑さの指標であり，連の長さの分散を修正した量は１次元の量に関わる複雑さの指標である．これらの指標は後で定義する通り，相似拡大について不変である．

図3.6，3.7の複雑さは指標I1, I2では区別することが出来ず，指標I3を用いることにより区別することができる．これはすべての区画が合同な図形のため，I1, I2は図3.6，3.7とも同じ値をとる．しかし連の長さの分散は異なるため，I3で区別することができる．

図3.7，3.8の複雑さは指標I₁, I₃では区別することが出来ず，指標I₂を用いることにより区別することができる．すべての区画が相似な図形のため，I₁の値は等しくなる．連の分散についても同じ値をとるので，I₃の値も等しくなる．しかし面積の分散は異なるため，I₂で区別することができる．

図3.5，3.6 図3.6，3.7 図3.7，3.8

I1 ○ - -

I₂ - - ○

I3 - ○ -

しかし，この三つの指標の値の範囲には大きな差がある．そこで，世田谷・目黒全域について各指標の平均 mと分散σを求めた．そして，

(31)

3.1. 序 21

α = m−1.96σ β = m+ 1.96σ

とするとき，αが0，βが100に対応するように，一次式で変換した．つまり，指標Inを変換した値I_n を以下のように定めた．

I_n =In−α

β−α ×100 (3.1.1)

ただし，右辺が0以下の場合はI_n = 0，100以上の場合はI_n = 100とする．

三つの指標I1, I2, I3を変換した値I₁, I₂, I₃ の平均値を，三指標平均値と呼ぶ．三指標平均値を指標として用いたところ，図3.4から図3.8の複雑さを判別することができた．

図3.4 図3.5 図3.6 図3.7 図3.8

I1 16 16 18 18 18

I₂ 0 0 0 0 11.5

I3 0 0 0 5.33 5.33

I 0.64 0.64 3.27 43.3 76.6

注意 1 正規分布の場合，区間[α, β]にデータの95%が入ることが知られている．

ただし，各指標の分布は必ずしも正規分布ではない．

この三指標平均値を用いて，地図の色を塗り分けることにより複雑さを可視化することを考える．まず，地図を正方形領域に分割する．各正方形領域の三指標平均値を計算し，累積度数によって六段階に塗り分ける．

この際色を塗り分けた正方形領域は，その領域の周囲の値も考慮して計算している．

また，この三指標平均値とI₃ には強い相関関係（相関係数：約0.92）があることも分かった．

(32)

3.2 ^{三つの指標の説明}

地図上の正方形領域に対して三つの指標を定義する．ただし，与えられた領域周辺部に生じる途切れた（閉曲線で囲まれていない）区画を黒塗りする．以下で「領域に含まれるすべての区画に渡って」という場合，これらの黒塗りした区画を無視する．

⇒

以下単に区画と言った場合には，閉曲線で囲まれた単一の図形のことを指すものとする．

3.2.1

周二乗面積比

ここで周二乗面積比とよぶのは，各区画の周の長さをPi，面積をAiとするときのP_i²/Aiのことである．円では最小値(4π)をとり，正方形では16，ヒトデの形のように凹凸が多い図形では大きくなる．地図上に指定された正方形領域において，この領域に含まれる区画のすべてに渡って周二乗面積比の平均値を求める．ただし，区画の面積に比例した加重平均をとる．

I₁:=

_N

i=1P_i² A_iAi

A =

_N

i=1P_i²

A , ただしA=

N i=1

A_i.

3.2.2

区画面積の分散を修正した量

地図上に指定された正方形領域において，この領域に含まれる区画の面積の分散をσ_A²，平均をmAとし，以下の量に着目する．

I2:= σ_A² m²_A

(33)

3.2. 三つの指標の説明 23

合同な区画ばかりからなる領域では最小値（0）をとる．

3.2.3

連の長さの分散を修正した量

上記I₂と似た量を１次元で考える．地図上の領域を横切る直線上において道路中心線でないピクセルが続くかたまり，つまり連の長さの分散を求めて，それを平均値の二乗で割る．具体的には以下の通りである．

この実験で用いる地図画像ビットマップにおいては道路中心線が黒，そうでない部分が白で表されている．

地図上に指定された正方形領域K（周辺部の半端な区画を黒く塗ったもの）を以下の４通りの方法でスキャンし，1（黒）と0（白）の列を作る．ここで行は水平の並び，列は垂直の並びを表す．

(A)上の行から順に，左から右へスキャン（英文方式）．

(B) 右の列から順に，上から下へスキャン（和文方式）．

(C) 領域Kを反時計回りに45度回転させて（菱形にして）から，上の行から順に，左から右へスキャン．

(D)領域Kを反時計回りに45度回転させて（菱形にして）から，右の列から順に，上から下へスキャン．

ただし(C)，(D)を行う前に

⎛

⎜⎜

⎝ 0 1 1 0

⎞

⎟⎟

⎠の形のブロックを

⎛

⎜⎜

⎝ 1 1 1 0

⎞

⎟⎟

⎠に修正し，さらに

⎛

⎜⎜

⎝ 1 0 0 1

⎞

⎟⎟

⎠の形のブロッ

クを

⎛

⎜⎜

⎝ 1 0 1 1

⎞

⎟⎟

⎠に修正する．これは斜めの線を連続にするためである．

⇒

こうして得た４つのビット列の各々について，0の連の長さの分散σ²_rと平均mrを求め，

σ²_r

m²_r (3.2.1)

(34)

を求める．(A)のビット列についての(3.2.1)と(B)のビット列についての(3.2.1)の平均値を求め，次に(C) のビット列についての(3.2.1)と(D)のビット列についての(3.2.1)の平均値を求める．こうして得たふたつの平均値のうち，小さい方をI₃とする．

3.3 ^実験方法

以下では，コンピュータ上でのデータの表現方法と，第2節で定義した指標I₁, I₂, I₃の近似値を計算する方法，特に各区画の面積と周の長さの計算方法について述べる．

3.3.1

データの表現方法

地図をモノクロBMPファイルとして与え，白を0，黒を1とみなして，それぞれの指標を計算している．

まず地図を正方形領域に分割する．次にこの正方形領域を中心とし，縦横2倍に拡大した正方形領域を考える．この拡大した正方形領域で各指標を計算し，この値によって元の正方形領域に色を塗る．

図3.9: 拡大した正方形領域に色をつけた例

これにより，塗り分ける領域の周囲の値も考慮していることになる．以下，単に正方形領域と言った場合には，

この拡大された正方形領域を指すものとする．

修 士 学 位 論 文