複雑系の科学

Author

gentam

Status
draft
Date
2018-04-09
Category

lecturenote

Tag

complexity, nature, lecture

Updated

2018-07-16

複雑系の科学の授業ノート

Contents

シラバス

科目概要

生命システム、情報システム、経済システム、社会システムを含む、複雑な動的システム の本質を非線形相互作用の数理モデルにより解読する新たな研究の方法論の開拓を目指し た「複雑系科学」は、自然科学、社会科学、情報通信技術などの多様な学問分野を横断的 に統合するというSFCの理念を具現化する、一つのソリューションを与え得る。また、SFC の学生が活躍する時代においては、新たなテクノロジーの研究開発や社会・経済システム の設計などの様々な場面において、複雑系科学の問題意識や研究手法を「基礎知識」とし て習得しておくことが必須になる。本科目は、受講者が自ら複雑系科学の数理モデルやデ ータ解析手法をプログラミングしながら学ぶことで、将来の研究開発やシステム設計に応 用できるようになることを目指す。

主題と目標/授業の手法など

本科目は複雑系科学の入門的な内容を学ぶことを主題としています。授業は標準的な講義 の形式を取り、数回に一度宿題が出ます。宿題はいくつかの簡単に解ける数学、物理、計 算機科学の問題です。ラップトップパソコンを持参すれば、Mathematicaでモデルシミュ レーションやデータ解析手法を実装する方法を学びつつ、よりビジュアル、ダイナミック 、インタラクティブに複雑系の本質を理解することができるでしょう。学期の最後には、 学生が自ら設定した最終プロジェクト(プログラム、作品、ウェブサイトなど自由に設定 可能)を提出してもらい、そのスコアが成績評価において重視されます。

第1回 複雑系のイントロダクション:伝統的科学の限界?

複雑系科学の導入として、その誕生の背景となった伝統的科学における要素還元主義の 限界に関する議論を振り返り、その克服のための新たな方法論として提案されてきたい くつかの数理モデルや分析手法を紹介しながら、次回以降の講義内容の全体像を概説す る。また、Mathematicaのインストールとプログラミング方法の基本を確認する。

青野真士 (環境情報学部 准教授)

行ってきた研究:

アメーバ計算をモデルに,

  1. 基礎理論(AmoebaSAT)を作成

  2. それをデバイス実装

    • 非ノイマン型コンピュータをアナログ回路,デジタル回路(FPGA実装),超電導回路 で実装

  3. アメーバモデルを拡張した応用を探る: 化学反応やロボット

複雑系とは?

  • 90年代に「複雑系」のブームがあった.

  • サンタフェ研究所

「複雑系」の関連図書

  • 歴史や概要

    • Mitchel M. Waldrop, 1994, 複雑系

    • 「複雑系」とは何か

  • 複雑系の詳細

    • 自己組織化と進化の理論

    • 複雑系入門

  • 非線形科学

    • 非線形科学

    • ストロガッツ 非線形ダイナミクスとカオス

  • 批判やさらに深いところを

    • 生命とは何か, 金子

    • 非線形な世界, 大野

    • 生命,微動だにせず, 郡司

複雑系の科学の核心には, 「生命」とは何か? という問いに答えられる新しい科学を創 造したい というモチベーションがある.

生命とは何か

一定の合意が得られている生命の定義:

  1. 区画化: 自己と他を区別する

  2. 自己複製: 自己を増やす

  3. 代謝: エネルギーを効率的に取り組み活動する

要素還元主義

複雑な物事でもそれを部分に分解して,それらの要素を理解すれば,全体を理解できる と信じる伝統的な方法論

この要素還元主義が17~20世紀の物理学,化学,一部の生物学の大きな発展を支えた. しかしながら,この方法論では対処できない限界も見えてきた.

例えば,生命を構成する有機物を分解していき,その特性を調べても「生命」という現象 そのものについての理解は深まらない.

生命,知性,意識はどのように生じたのか?

全体とは部分の総和以上の何かである

—アリストテレス

創発 (emergence)

部分の性質の単純な総和に止まらない性質が,全体として現れること.局所な複数の 相互作用が複雑に組織化することで,個別の要素の振る舞いからは予測できないような システムが構成される

複雑系の科学の主な研究史

各研究者が「生命」をどう表現するかという, "ロックスター"達の作品集

理論・ソフトウェア研究に重心

  • 1944 ゲーム理論 - J. フォンノイマン

  • 1950s 囚人のジレンマ - A. タッカー

  • 1950s セル・オートマトン - S. ラウム, J. フォンノイマン

  • 1958 パーセプトロン - F. ローゼンブラット

  • 1961 カオス - 上田, E. ローレンツ

  • 1960s コルモゴロフ複雑性 - A. コルモゴロフ, G. チャイティン

  • 1970s ライフゲーム - J. H. コンウェイ

  • 1971 計算複雑性 - S. クック

  • 1975 遺伝的アルゴリズム - J. H. ホランド

  • 1977 フラクタル - B. マンデルブロ

  • 1980s 再帰型ニューラルネット - 甘利俊一, J. ホップフィールド

  • 1981 初等セル・オートマトン - S. ウルフラム

  • 1984 結合振動子論 - 蔵本由紀

  • 1986 人工生命 - C. ラングトン

  • 1990s Tierra - T. S. レイ

  • 1998 複雑ネットワーク - D. ワッツ, S. ストロガッツ

人工知能ブーム.実験・ハードウェア研究に重心

  • 2006 ディープラーニング - J. ヒントン

  • 2000s 生命の起源 - ハーバード大, NASA, 東工大ELSI

  • 2012 自然計算 - G. Rozenberg

第2回 カオス:単純なのに予測不能?

複雑な振舞いが単純な決定論的時間発展方程式からいかにして生じてくるかを学ぶ。ま ず、離散力学系、とくにロジスティック写像やテント写像を例にとり、その予測不可能 性を理解する。そこでは、パイこね変換の概念を学ぶことが理解の近道となる。さらに 、連続力学系、とくにローレンツ方程式やレスラー方程式において現れるストレンジア トラクタの特徴を理解する。これらのカオス力学系を、Mathematicaでシミュレーショ ンできるようにする。最後に、カオス性を定量的に評価する指標として、初期値のわず かな違いが時間とともに拡大する度合いを評価するリアプノフ指数の概念を学ぶ。

ここからは以下の本を参考に進んでいく:

Title

カオス学入門

Author

合原一幸

Published

2001-03-20

Publisher

放送大学教育振興会

ISBN

4-595-89201-2

1. 実数の複雑性

可算無限と不可算無限

集合の要素の数

  • 集合(set)
    \(K = \{1,3,5,7,9\}\) (外延的記法)
    \(K = \{x \mid x\text{は奇数である一桁の自然数}\}\) (内包的記法)
  • \(K\) の要素(element)数: \(\#(K) = 5\)
  • \(K\) の冪乗集合(power set): \(\mathcal{P}(K)\) とは \(K\) の全て の部分集合(subset)からなる集合:

    \begin{align*} \mathcal{P}(K) = &\{\{\},\{1\},\{3\},\{5\},\{7\},\{9\}, \\ &\{1,3\},\{1,5\},\{1,7\},\{1,9\},\{3,5\},\{3,7\},\{3,9\},\{5,7\},\{5,9\},\{7,9\}, \\ &\{1,3,5\},\{1,3,7\},\{1,3,9\},\{1,5,7\},\{1,5,9\},\{1,7,9\},\{3,5,7\},\{3,5,9\},\{3,7,9\},\{5,7,9\}, \\ &\{1,3,5,7\},\{1,3,5,9\},\{1,3,7,9\},\{1,5,7,9\},\{3,5,7,9\},\{1,3,5,7,9\}\} \end{align*}

    冪集合 \(\#(\mathcal{P}(K)) = 2^{\#(K)} = 2^5\)

無限集合の濃度

自然数(natural number)全体の集合:

  • \(\Bbb N = \{1,2,3,\ldots\}\) (外延的記法)
    \(\quad = \{x \mid x\text{は自然数}\}\) (内包的記法)
  • 無限集合には要素の数という概念は適応できない → 濃度(cardinality) という概念を導入する 1

  • \(\Bbb N\) の濃度:「可算(countable)濃度」または \(\aleph_0\) (アレフ・ゼロ 2)

  • \(\Bbb N\) の無限:「可算無限」

  • 「可算」→ 1対1対応が存在するということ

    \begin{align*} \Bbb{N} =& \{1,2,3,\ldots,\,n,\ldots\}&\\ &\:\downarrow\;\,\downarrow\;\,\downarrow\qquad\;\,\downarrow & \Bbb{N} \sim \Bbb{3N} \\ \Bbb{3N} =& \{3,6,9,\ldots,3n,\ldots\} \end{align*}
    • 1対1対応がつく2つの集合は「対等」(\(\sim\))である

可算無限の集合

  • 自然数全体の集合: \(\Bbb N = \{1,2,3,\ldots\}\)

  • 整数全体の集合: \(\Bbb Z = \{\ldots,-2,-1,0,1,2,\ldots\}\)

  • 有理数全体の集合: \(\Bbb Q = \left\{ x \mid x = \frac pq, p, q \in \Bbb Z, q \ne 0 \right\}\)

これらは全て対等(\(\sim\))な集合

\begin{equation*} \Bbb{N \sim Z \sim Q} \end{equation*}
\begin{equation*} \text{Cardinality of } \Bbb{N, Z, Q}: \aleph_0 \end{equation*}

実数全体の集合は自然数全体の集合と「対等」か?

実数の二進数表現

  • ここで,区間 \([0.0, 1.0]\) の実数 \(x\)\(y_i \in \{0,1\} (i\in\Bbb N)\) のビット列として二進数表現することを考える

    \begin{align*} x &= 0.y_1y_2y_3 \cdots y_i \cdots \\ &= {y_1\over2^1} + {y_2\over2^2} + {y_3\over2^3} + \cdots + {y_i\over2^i} = \sum_{k=1}^{\infty}{y_k\over2^k} \end{align*}
  • \(k\) ビット目の値を \(1/2^k\) で表現すると例えば以下のようになる: (下位のビットを反転させた表現(下位ビット充填記法)もできる)

    \begin{align*} 0.5: & 0.100000 \cdots \\ & 0.011111 \cdots \\ 0.25: & 0.010000 \cdots \\ & 0.001111 \cdots \\ 0.125: & 0.001000 \cdots \\ & 0.000111 \cdots \end{align*}

カントールの対角線論法

  • 区間 \([0.0, 1.0]\) の実数全体の集合 \(\bf S\) と自然数全体の集合 \(\Bbb N\) が対等と仮定すると,

  • \(\bf S\) の要素 \(x\)\(\Bbb N\) の要素 \(n\) が一対一に対応するはず

  • 以下のような対応表を構成できる

    \begin{equation*} \begin{array}{|c|} \hline \Bbb N & \bf S \\ \hline 1 & 0. & y_{11} & y_{12} & y_{13} & \cdots & y_{1i} & \cdots & y_{1i^*} & \cdots \\ \hdashline 2 & 0. & y_{21} & y_{22} & y_{23} & \cdots & y_{2i} & \cdots & y_{2i^*} & \cdots \\ \hdashline 3 & 0. & y_{31} & y_{32} & y_{33} & \cdots & y_{3i} & \cdots & y_{3i^*} & \cdots \\ \hdashline \vdots & \ & \vdots & \vdots & \vdots & \ddots & \vdots & \ & \vdots & \ \\ \hdashline i & 0. & y_{i1} & y_{i2} & y_{i3} & \cdots & y_{ii} & \cdots & y_{ii^*} & \cdots \\ \hdashline \vdots & \ & \vdots & \vdots & \vdots & \ & \vdots & \ddots & \vdots & \ \\ \hdashline i^* & 0. & y_{i^*1} & y_{i^*2} & y_{i^*3} & \cdots & y_{ii} & \cdots & y_{i^*i^*} & \cdots \\ \hdashline \vdots & \ & \vdots & \vdots & \vdots & \ & \vdots & \ & \vdots & \ddots \\ \hline \end{array} \end{equation*}
  • 対角要素を全て取り出して \(x = 0. y_{11}\,y_{22}\,y_{33}\ldots y_{ii} \ldots\) を構成し,
    その全ての値を反転した \(x^* = 0. \overline{y_{11}}\,\overline{y_{22}}\, \overline{y_{33}}\ldots \overline{y_{ii}}\ldots\) (ただし \(\overline{y_{ii}} = 1-y_{ii}\)) を考える
  • \(x^*\) もまたこの対応表のどこかの行に存在するはずなので \(i^*\) 行に存在するものとする.

  • しかし \(x^*\) の対角要素 \(y_{i^*i^*}\) は, \(x\)\(y_{i^*i^*}\) を反転したもの. (つまり \(y_{i^*i^*}\) で衝突していて,一対一対応していない)

  • \(y_{i^*i^*} = 1 - y_{i^*i^*}\) となり矛盾.

    • \(\therefore\) \(\bf S\)\(\Bbb N\) は対等ではなく, \(\bf S\) の方が \(\Bbb N\) より濃度が大きい.

無限集合の濃度

  • 自然数

    • \(\Bbb N\) の濃度: 「可算濃度」or \(\aleph_0\)

    • \(\Bbb N\) の無限: 「可算無限」

  • 実数

    • \(\Bbb R\) の濃度: 「非可算濃度」「連続濃度」or \(\aleph_1\) (アレフ・ワン)

    • \(\Bbb R\) の無限: 「非可算無限」

非可算無限の集合

  • 実数全体の集合: \(\Bbb R\)

  • 複素数全体の集合: \(\Bbb C\)

  • 区間 \([0.0,1.0]\) の実数全体の集合: \(\bf S\)

  • ある直線(線分)上の点の集合 \(\bf L\)

  • ある平面上の点の集合 \(\bf P\)

  • 無理数全体の集合: \(\Bbb{ R\backslash Q}\)

これらは全て対等な集合

\begin{equation*} \cal P \Bbb{ (N) \sim R \sim C } \sim \mathbf{S \sim L \sim P} \sim \Bbb{ R\backslash Q } \end{equation*}
\begin{equation*} \text{Cardinality of } \Bbb{ R, C, }\mathbf{S, L, P}, \Bbb{ R\backslash Q }: \aleph_1 \end{equation*}
  • 以下のような無理数を 実数の二進数表現 (\(0.y_1y_2y_3 \cdots y_i \cdots\)) すると, \(y_1y_2y_3 \cdots\) は無限に続く非周期的なビット列

    • 円周率 \(\pi = 3.14159265\ldots\)

    • ネイピア数 \(e = 2.71828182\ldots\)

    • 2の平方根 \(\sqrt2 = 1.41421356\ldots\)

    • 自然対数 \(\log{e}10 = 2.30258509\ldots\)

  • ほとんど全ての実数を表現するビット列はランダムである

  • この 実数の複雑性が,カオスの複雑性の源となっている

1

Cardinality https://en.wikipedia.org/wiki/Cardinality

2

Aleph number https://en.wikipedia.org/wiki/Aleph_number

2. 離散的時間力学系のカオス

ロジスティック写像 (Logistic Map)

\begin{equation*} x(t+1) = ax(t)(1-x(t)) \quad (x \in [0.0,1.0], a \in [0.0,4.0]) \end{equation*}

\(a = 4, x(0) = 0.1\) でこの式を計算する.

非常にシンプルな規則から,ランダムで非周期的な結果が生み出される.これを, Mathematica上で実行してみる

(* 関数の定義 *)
In[27]:= logisticmap[a_, x_] := a x (1 - x)
In[28]:= logisticmap[4, 0.1]
Out[28]= 0.36

In[29]:= logisticmap[4, logisticmap[4, 0.1]]
Out[29]= 0.9216

(* Nest[logisticmap[4, #] &, 0.1, 3] *)
In[30]:= NestList[logisticmap[4, #] &, 0.1, 3]
Out[30]= {0.1, 0.36, 0.9216, 0.289014}

In[31]:= logisticmapdata1 = NestList[logisticmap[4, #] &, 0.1, 100];

In[32]:= ListPlot[logisticmapdata1, Joined -> True,
  PlotTheme -> {"scientific", "Frame", "LargeLabels"},
  FrameLabel -> {"t", "x(t)"}]
r/lec-complexity/logistic-map.png

Wolfram言語について:

?関数名 でヘルプを出せる

不規則性を生み出す規則.

カオスの特徴:

  1. 非周期的だがランダムではない.

    完全に周期的な運動(e.g. 正弦波)も,完全にランダムな運動も「生命」らしくない. 不規則を生み出す規則,カオスは「生命らしさ」を与える?

  2. 初期値の微小な違いが急速に拡大される.

    x(0)の値を,0.1から0.000001へと変えるだけで全く異なるグラフが現れることを確認 できる.

テント写像 (Tent Map)

\begin{equation*} x(t+1) = \begin{cases} 2x(t) & \text{if $\; 0 \ge x(t) < 0.5$} \\ 2(1-x(t)) & \text{otherwise; if $\; 0.5 \le x(t) \le 1$} \end{cases} \end{equation*}
  • 0.5 より小さいとき2倍する = 最上位ビットが0の間,左シフトする

  • 0.5 以上の時,1から引いたものを2倍 = 最上位ビットが1のとき,全体を反転して左シフト

→ 最下位のビットにランダムな値が補給されれば,複雑性が維持される.

この カオスの複雑性は,実数の無限に続く小さなランダム性によって作り出される

In[1]:= tentmap[x_] := If[x < 0.5, 2 x, 2 (1 - x)];

In[2]:= tentmap[0.1]
Out[2]= 0.2

In[3]:= RandomReal[{0, 1}]
Out[3]= 0.0125969

In[4]:= tentmapdata1 = NestList[tentmap[#] &, 0.9701856295739799`, 100];

In[5]:= ListPlot[tentmapdata1, Joined -> True,
 PlotTheme -> {"scientific", "Frame", "LargeLabels"},
 FrameLabel -> {"t", "x(t)"}]
r/lec-complexity/tent-map.png

上の図では最下位ビットにランダムな値が補給されずに,複雑性が枯渇してしまっている

(第3回)

シラバスではフラクタルだが,カオスの続きをやる.

エノン写像 (Henon Map)

離散時間発展方程式

In[16]:= henonmap[a_, b_, {x_, y_}] := {
   y + 1 - a x^2,
   b x
   };

In[17]:= henonmap[1.4, 0.3, {0.1, 0.2}]
Out[17]= {1.186, 0.03}

In[18]:= NestList[henonmap[1.4, 0.3, #] &, {0.1, 0.2}, 5]
Out[18]= {{0.1, 0.2}, {1.186, 0.03}, {-0.939234,
  0.3558}, {0.120774, -0.28177}, {0.697809, 0.0362323}, {0.354521, 0.209343}}

In[19]:= henonmapmapdata1 = NestList[henonmap[1.4, 0.3, #] &, {0.1, 0.2}, 10000];
In[20]:= ListPlot[henonmapmapdata1,
 PlotTheme -> {"scientific", "Frame", "LargeLabels"},
 FrameLabel -> {"x(t)", "y(t)"}, AspectRatio -> 1,
 PlotRange -> {{-1.5, 1.5}, {-0.5, 0.5}}]
r/lec-complexity/henon-map.png

このヘノン写像はフラクタルになっている.

池田写像 (Ikeda Map)

ikedamap[a_, b_, {x_, y_}] := Module[{θ},
   θ = 0.4 - 6/(1 + x^2 + y^2);
   {
    a + b (x Cos[θ] - y Sin[θ]),
    b (x Sin[θ] + y Cos[θ])
    }];

ikedamapdata1 = NestList[ikedamap[1.0, 0.9, #] &, {0.8, -1.5}, 10000];

ListPlot[ikedamapdata1, PlotTheme -> {"scientific", "Frame", "LargeLabels"},
 FrameLabel -> {"x(t)", "y(t)"}, AspectRatio -> 1]
r/lec-complexity/ikeda-map.png

グモウスキーミラー写像 (Gumowski-Mira Map)

gmmap[μ_, {x_, y_}] := Module[{F, x1, y1},
   F[x0_] := μ x0 + 2 (1 - μ) x0^2/(1 + x0^2);
   x1 = y + 0.008 (1 - 0.05 y^2) y + F[x];
   y1 = -x + F[x1];
   {x1, y1}
   ];

gmmapdata1 = NestList[gmmap[-0.8, #] &, {0.1, 0.1}, 10000];

ListPlot[gmmapdata1,
 PlotTheme -> {"scientific", "Frame", "LargeLabels"},
 FrameLabel -> {"x(t)", "y(t)"}, AspectRatio -> 1]
r/lec-complexity/gumowski-mira-map.png

ローレンツ方程式 (Lorenz Equations)

σ = 3; r = 26.5; b = 1;
lorenzA = NDSolve[{
    Derivative[1][x][t] == σ (y[t] - x[t]),
    Derivative[1][y][t] == -x[t] z[t] + r x[t] - y[t],
    Derivative[1][z][t] == x[t] y[t] - b z[t],
    x[0] == 0, z[0] == 0, y[0] == 1}, {x, y, z}, {t, 0, 400},
   MaxSteps -> ];

Show[ParametricPlot3D[Evaluate[{x[t], y[t], z[t]} /. lorenzA], {t, 0, 400},
  PlotPoints -> 1000, PlotStyle -> Directive[Thick, RGBColor[.8, 0, 0]],
  ColorFunction -> (ColorData["SolarColors", #4] &)], PlotRange -> All,
 Boxed -> True, Axes -> True, AxesLabel -> {"x", "y", "z"}]
r/lec-complexity/lorenz-equations.png
アトラクター

初期値に違いがあっても,同じ結果(軌道)へと引きつける要素

カオス系では初期値のわずかな違いによって結果が敏感に変化するが,アトラクターの存 在がそれを安定させる?

分かりやすいアトラクターの説明: AN INTERACTIVE INTRODUCTION TO ATTRACTOR LANDSCAPES by Nicky Case <http://ncase.me/attractors/>

3. カオスの特徴と意味

パイコネ変換 (Baker's Transformation)

引きのばしと折り畳みの反復適用.Tent Map がやっていることはまさにこのパイコネ変 換である:

\begin{equation*} x(t+1)= \begin{cases} 2x(t) & \text{(if $\; 0 \ge x(t) < 0.5$) 引き伸ばし} \\ 2(1-x(t)) & \text{(otherwise; if $\; 0.5 \le x(t) \le 1$) 折り畳み}\\ \end{cases} \end{equation*}
  • 実数の複雑性: 無限に続くバイナリ列のランダムさが拡大されて非周期性をもたらす

  • 引き伸ばし:

  • 折り畳み:

カオス解

  1. 非周期性

  2. 初期値敏感性

  3. 有界性

第3回 フラクタル:無限の入れ子構造の彼方に何がある?

フラクタルの概念は、カオスをより深く理解するためにも重要である。カントール集合 、コッホ曲線、シェルピンスキーのガスケットの構成法をMathematicaでシミュレーシ ョンできるようにし、自己相似の概念を学ぶ。さらに、フラクタル次元の概念を導入し 、非整数次元の計算方法を学ぶ。そして、カオス力学系のストレンジアトラクタのフラ クタル性を理解する。

フラクタル図形

  • フラクタル Fractal

  • 部分と全体が自己相似している

  • 単純な操作の繰り返しが,非常に複雑な図形を作り出す

  • 拡大していくと,そこに入れ子構造が現れる

毛細血管の構造 → 有限の体積に無限の軌道を収める

カントール集合 (Cantor Set)

  1. 線分を3等分する

  2. 得られた3つの線分の真ん中のものを取り除く

操作1, 2を再帰的に繰り返す

Do[Print@CantorMesh[n, MeshCellStyle -> {Thick}], {n, 0, 4}]
r/lec-complexity/cantor-set.png

コッホ曲線 (Koch Curve)

tmp
r/lec-complexity/koch-curve.png

シェルピンスキーのガスケット (Sierpinski Gasket)

tmp
r/lec-complexity/sierpinski-gasket.png

ジュリア集合 (Julia Set)

tmp
r/lec-complexity/julia-set.png

マンデルブロ集合 (Mandelbrot Set)

tmp
r/lec-complexity/mandelbrot-set.png

エノン写像 (Henon Map)

離散時間発展方程式

\begin{align*} x(t+1) &= y(t) + 1 - ax^2(t) \\ y(t+1) &= bx(t) \end{align*}
tmp

第4回 複雑ネットワーク:ツイートはどう拡散していくのか?

複雑ネットワーク理論の導入として、様々なネットワークの特徴付けの仕方を学ぶ。そ こから、ランダムグラフ、スケールフリー性、スモールワールド性、フラクタル性、コ ミュニティ構造といった重要概念を紹介し、実社会のインターネットやSNSなどのネッ トワークを分析する方法をMathematicaでシミュレーションできるようにする。

複雑ネットワークとは

複雑ネットワーク (Complex Network)

ネットワークの各ノードに注目するのではなく,ネットワークの構造,特徴量に注目し, そこから見えてくる普遍的な性質を探求する研究.

ここでネットワークとは,神経回路からインターネット,経済まで様々分野を横断する.

参考図書: "ネットワークの科学", 増田直紀; 今野紀雄, 2005, 産業図書

グラフとその特徴量

グラフ (Graph)

グラフGは頂点(vertex)の集合Vと,辺(edge)の集合Eで構成される.

Vertices = {a, b, c, d, e, f};
Edges = {a -> b, b -> c, b -> f, b -> d, d -> e, d -> c, e -> c,
   f -> c};

GraphPlot[Edges, DirectedEdges -> True, VertexLabeling -> True,
 VertexRenderingFunction -> ({White, EdgeForm[Black], Disk[#, .1],
     Black, FontSize -> 30, Text[#2, #1]} &)]
r/lec-complexity/graph-dir.png

頂点字数分布 (Vertex Degree Distribution)

頂点vi数うki: 頂点viからでている辺の数 p(k): 字数kを持つ頂点の数の割合 (頂点の総数で割ったもの)

V = {a,b,c,d,e,f}

E = {{a,b},{b,c},{b,f},{b,d},

{d,e},{d,c},{e,c},{f,c}}

正規分布

頂点字数分布が 正規分布 である:

ポアソン分布

r/lec-complexity/vdd-poisson.png

べき分布

r/lec-complexity/vdd-power.png

見づらいので,対数標示する:

r/lec-complexity/vdd-power-log.png
  • スケールフリー: 分布の偏りを特徴付ける尺度(スケール)が存在しない

面白いことに,実社会のネットワークの多くがべき分布となっている:

ネットワーク

べき指数

インターネット

2.1-2.5

映画俳優の共演ネットワーク

2.3-3.1

タンパク質の反応ネットワーク

2.4-2.5

平均頂点間距離 (Avarage Distance between Vertices)

頂点vi とvjの距離: 頂点vi からvj に行くために通る辺の最小の数.最小ホップ数.

実際のネットワークではnが大きくなってもLがあまり大きくならないことが多い.

クラスター係数 (Cluster Coefficient)

頂点viのクラスター係数Ci: viの字数がkiである時,ki個あるviの隣接頂点から2つを選 んでできるki(ki-1)/2対の頂点間に存在する辺の数の平均値.

\(0 \le C_i \le 1\)

グラフ全体のクラスター係数C: \(C = \frac1n\sum_{i=1}^n C_i\)

  • サイクルグラフ

  • 格子グラフ

エルデッシュ数 (Erdos Number)

  • 大量に論文を書いた Erdos さんまで,共著者をたどって何ホップでたどり着くか

ランダムグラフ (Random Graph)

Random Graph (Erdos, 1959)

  1. 頂点数nと \(0 \le p \le 1\) を固定する

  2. 各頂点ペアにつき確率pで辺をもうける (確率1-pで設けない)

  3. 辺を作るかどうかは \(_n C _2 = n(n-1)/2\) 通りのペアにつき,独立に決める

こうすると,頂点字数分布 {p(k)} がポアソン分布にしたがう.

クラスター係数 \(C = p = \frac{<k>}{n-1} \fallingdotseq \frac{<k>}{n}\)

nを大きくしていくと,C → 0 になる.

  • 実社会のネットワークとは非整合的.

...

ワッツ-ストロガッツモデル (Watss-Strogatz (WS) Model)

(Watts & Strogatz, 1998)

  1. n個の頂点をリング状に配置し,各頂点とその両隣k/2個(kは偶数)の頂点との間に辺を 定義する.(辺の数はkn/2.頂点の字数はk)

  2. kn/2本のうち,割合p(\(0 \le p \le 1\))だけの辺.すなわちpkn/2本をランダム に選ぶ

  3. 選ばれた辺の2つの頂点のうち,片方をランダムに選び,他方から切り離す.

  4. 切り離された辺の新しい接続先の頂点をランダムに決める.この操作を「つなぎかえ 」新しい辺を「ショートカット」と呼ぶ. ただし,新しい XXX

スモールワールドネットワーク

小さい平均頂点間距離Lと大きいクラスター係数C

スモールワールド・ネットワークは知人関係ネットワークだけに見られる特徴ではない. 電力網や,映画俳優の共演ネットワーク,戦中の神経細胞ネットワークなども,スモール ワールド・ネットワークの特徴を持つ.

Note

「スモールワールド的なネットワークが現れる場合は,空間的な制約が存在して いる可能性が高いといえる」

社会学者グラノベッターが提案した「弱い紐帯」という概念は「ショートカット」に対応 する.

スケールフリーネットワーク

バラバシ-アルバートモデル (Barabasi-Albert Model)

(Barabasi & Albert, 1999)

頂点が 成長 していくネットワーク

  1. 頂点がn個あって,既存の頂点vi(i<=i<=n)が字数kiをもつとき,ある新しい辺がviに 接続される確率を以下のように定義する.「優先的選択」

    \begin{equation*} \mathbf{P}(k_i) = \frac{k_i}{\sum_{j=1}^{n}k_j} \end{equation*}

    (同じ頂点から1つの頂点に辺が二本以上接続されることは避ける)

  2. XXX

r/lec-complexity/barabasi-albert.png

次数の大きい頂点を「ハブ」と呼ぶ. XXX

インターネット,航空網など現実に存在するネットワークの多くが,スケールフリーネッ トワークであることが1999年頃から盛んに報告されてきた.

スケールフリーネットワークでは病気や情報が伝播しやすいことや,ランダムに頂点が壊 れることに対しては耐性があることなどが明らかになっている.これらは感染症予防対策 やインターネットの設計に寄与している.

複雑ネットワーク (Complex Network)

部分(頂点と辺の接続)のルールから創発する全体(ネットワーク)の特徴

グラフ p(k) L C 構造 完全グラフ,均一,小 格子・サイクル,均一 ランダムグラフ,ポアソン分布 一般化ランダムグラフ,任意 WSモデル(スモールワールド),均一とポアソンの間 BAモデル(スケールフリー),べき分布k-3 現実のネットワーク,不均一

第5回 複雑性:複雑系はコンピュータ?

複雑性の概念をより深く理解するためには、複雑系と計算との関係を学ぶことが重要で ある。そこで、計算の概念を定義したチューリングマシンを紹介し、計算万能性の概念 を理解する。そこから、一般化シフト写像の挙動をMathematicaでシミュレーションで きるようにし、カオス力学系が有する計算能力の本質を学ぶ。さらに、計算複雑性の階 層、ランダム性、コルモゴロフ複雑性を紹介し、計算不能性の概念を理解する。

計算とは?

計算力のある物理現象とは?

  • 「生命」とは何か

  • 完全に周期的でも,ランダムでもないカオスは「生命」らしさを与える?

チャーチ・チューリングの提唱

  • 1930s 様々な計算モデルの提唱

    • Herbrand-Godel計算可能性

    • Turing: チューリングマシン

    • Kleene: 帰納的関数

    • Church: λ定義可能関数

    • Post: ポスト正規システム

第6回 セル・オートマトン:生命を数理モデルで表現できるか?

複雑系の数理モデルの代表例であるセル・オートマトンがもつ豊かな表現可能性を認識 するために、最も単純な生命系のモデルとも言われるライフゲームを紹介する。さらに 、最も単純化されたセル・オートマトンである初等セル・オートマトンを導入し、その ルール空間を4つのクラスに分類した上で、ランダム性を生成するルール、計算万能性 を有するルール、生命の振舞いとの類似性を示唆するルール(カオスの淵)などを学ぶ 。これらのセル・オートマトンを、Mathematicaでシミュレーションできるようにする 。そこから、数理モデルによる秩序・無秩序の創発、知性の創発、生命の創発などの表 現可能性を議論する。

第7回 結合振動子系:何故みんなシンクロしたがる?

周期的に振動する力学系(振動子)を結合することで観察される同期現象は、生命シス テムや社会システムを理解するための大きな示唆を与える。ここでは、集団引き込みと 呼ばれる現象の発生過程を理解し、複雑ネットワークとの関連性を学ぶ。さらに、カオ ス振動子を結合したモデルにおいて現れるカオス的遍歴現象を紹介し、その生命システ ムとの類似性を議論する。これらの結合振動子系を、Mathematicaでシミュレーション できるようにする。

(2018-05-31: 補講日)

tmp

メトロノームの同期:

ホタル発光の同期:

ウズラ胚拍動する心筋細胞

振動: 振幅,周期,振動数,位相の復習

蔵本モデル: 結合振動子系を位相のみで記述する

\(\theta\) は一定の傾きで増えていく

常微分方程式 \(\frac{d\theta(t)}{dt} = \omega\) を数値的に解く → \(\theta (t) = \omega t\) を確認する:

Mathematica:

\begin{equation*} \omega = 1; \text{NDSolve}\left[ \left\{ \frac{\partial \theta (t)}{\partial t}=\omega, \theta (0)=0 \right\}, \{\theta \}, \{t,0,50\}, \text{MaxSteps}\to \infty \right] \end{equation*}

相互引き込み (Mutual Entrainment)

異なる振動数を持つ2つの振動子を結合する.連立常微分方程式.

結合強度kを調整すると,同期する.

\(\omega1, \omega2, k\) の関係:

同期引き込み領域 の三角形内部では振動数の同期が起こる. \(\varDelta\omega = \omega1 - \omega2\)

ここまでが,もっとも単純な二振動モデル. 振動子を結合したネットワークは同期するか?

  • 完全グラフ

  • ランダムグラフ

ここまでは前回の話でいう,クラス2(periodic)的な振る舞いといえる.


(2018-06-11)

強制引き込み (Forced Entrainment)

異なる振動数 \(\omega_i\) をもつ振動子 \(i \in []\)

生命や計算を表現できる結合振動子系とは?

  • カオスの縁 (Edge of Chaos)

生命(情報処理能力をもつ)は,規則的振る舞いから乱雑なカオス的振る舞いへと「相転 移」が起こる狭い領域「カオスの縁」で生じるのだろう

結合振動子系 (Coupled Map Lattice)

(K. Kaneko, 1985)

カオス振動子(ロジスティック写像) \(i \in {1,2, ..., N}\) を結合する.

\begin{equation*} x_i(t+1) = (t-\varepsilon) f(x_i(t)) + \frac{\varepsilon}2 (f(x_{i-1}(t)) + f(x_{i+t})) \end{equation*}
\begin{equation*} N = 200, 非線形性 a = 1.5, 結合強度 \varepsilon = 0.3 \end{equation*}

オリジナルは実数0~1までの空間で定義されていたが,このモデルでは -1~1の空間. 本質的には同じ.

秩序立った部分と,無秩序な部分が分かれて出てくる. さらにその無秩序部分が横にずれていく.

ここで出てくる模様は,初等セル・オートマトンRule 110と似ている.

  • 時間カオス

  • 非常に単純だが,様々なバラエティがある.(特定のシステムをモデル化してできたも のはない)

    • 複雑系の抽象的な説明として利用できるのではないか,と多くの研究をインスパイア した

第8回 ゲーム理論:数学で社会を動かせるか?

マルチエージェントシステムにより経済・社会システムをモデル化する際、ゲーム理論 の研究で議論されてきた概念や手法は、有益な知見を与える。そこで、囚人のジレンマ に代表される重要なゲームをいくつか紹介し、ナッシュ均衡などの重要概念を学ぶ。さ らに、ゲーム理論が社会の意思決定に応用されている事例を紹介し、数学理論の社会実 装の可能性を議論する。

第9回 生命の起源:我々はどこから来たのか?

真の複雑系とは生命のことである。では、どのようにして無生物から生物が創発したの だろうか?科学の最大の難問の一つであるこの問いに取り組む「生命起源」研究が、近 年活発化している。ここでは、生命誕生のいくつかの有力なシナリオとして、RNAワー ルド仮説や原始代謝仮説などを概説し、最新の生命起源研究のアプローチを紹介する。 また、生命の誕生をもたらし得る環境に要求される複雑性についても議論する。

1. 生命起源研究の活発化

  • Origin of Life Initiative (Harvad Univ.)(2006)

  • NASA Astrobiology (2009)

  • 地球生命研究所 (東工大, 2013)

冥王代生命学

冥王代 (Hadean eon)

地質時代の分類のひとつ.地球誕生から40億年前までの5億年間を指す.定義としては 「岩石記録が見つからない時代」

冥王代生命学のグループが支持する生命誕生までの仮説: 全地球史アトラス <https://www.youtube.com/playlist?list=PLL5GnXiRTz-5w_jTyn4rn1LOeT_xB1lwt>

生命の起源には様々な仮説が提唱されているが,↑は海ではなく陸地の地下で生まれたとする.

2. 生命起源へのアプローチ

  • 前生物化学 (Prebiotic Chemistry)

    • Miller-Urey実験(1953): スパーク放電により,還元的ガスから水とアミノ酸が合成 されることを示した.

    • → 神の存在なしに有機物が生まれることの最初の実証実験と言える

原始スープ仮説 原始代謝仮説

3. 生命誕生場

  • 陸上起源説 vs 海底起源説

  • 自然原子炉間欠泉説

4. 保守派 vs 革新派

  • タール問題

  • Messy Chemistry

  • Astrobiology

第10回 人工生命:生命は作れるのか?

生命の概念を拡張し、ソフトウェア、ハードウェア、ウェットウェアでできた「あり得 る生命」としての複雑系を研究する分野が、人工生命である。ここでは、人工生命の代 表的数理モデルをMathematicaでシミュレーションできるようにし、合成生物学の手法 で構成される原始細胞などに関する最新の研究アプローチを紹介する。

第11回 計算複雑性: 解けない問題の難しさ?

O-記法

  • "\(f(n)\) はオーダー \(O(g(n))\) である"

  • → "no worse than g(n)" というとき

  • \(n \to \infty\)\(|f(n)| \le c|g(n)|\) が全ての \(n\) とある定 数 \(c\) について成り立つ.

一般的なオーダーの階層:

O記法

説明

\(O(1)\)

定数 (constant)

\(O(\log n)\)

対数 (logarithmic)

\(O(n)\)

線形 (linear)

\(O(n\,\log n)\)

準線形,線形対数 (quasilinear, log-linear)

\(O(n^2)\)

二乗 (quandratic)

\(O(n^c),\,\exists c\ge1\)

多項式 (polynomial)

\(O(2^n)\)

指数関数 (exponential)

\(O(n!)\)

階乗関数 (factorial, combinatorial)

\(O(2^{c^n})\)

二重指数関数 (double exponential)

多項式と指数関数の間に大きな壁がある.

時間計算量 (Time Complexity)

あるアルゴリズムを使って問題を解くのに要するステップ数.問題サイズ(入力データ の長さ) \(n\) の関数として表される.

空間計算量 (Space Complexity)

あるアルゴリズムを使ってある問題を解くのに要する記憶容量.問題サイズ \(n\) の関数.空間は再利用可能な点が,時間計算量とは違う.

決定性&非決定性チューリングマシン

Deterministic Turing Machine

Non-Deterministic Turing Machine

複雑性クラスP

Complexity P

P = Polynomial time

最小スパニングツリー問題

スパニングツリー(全域木)

全てのノードにアクセスできていて,ループがない.

e.g. 輸送経路,送電網

最短経路問題

2つの頂点間を結ぶ経路の中で,最小の重み総和(コスト)を持つものを探索する最適化問 題.

Dikstraのアルゴリズム: \(O(V^2)\) or \(O((E+V)\log V)\) or \(O(E + V \log V)\)

e.g. カーナビ

複雑性クラスNP

非決定性チューリングマシン(NTM)で,多項式時間(Polynomial Time)で解ける問題の集合

  • NTMを使って一瞬で解が得られたと仮定し,それが解であることをDTMで多項式時間で検 証できる問題.

  • NTMが実在しない現実的な状況で,NP問題の時間計算量は往々にしてシス関数となる. → "手に負えない問題(Intractable Problem)"

ハミルトン閉路問題

グラフ \(G = (V, E)\) に全ての頂点を一度だけ通る閉路(ハミルトン閉路)が存在す るかどうかを判定する問題.

Note

2018-08-23

全ての正多面体(Platonic solid)にはハミルトン閉路(Hamiltonian cycle)が存在する. <http://mathworld.wolfram.com/HamiltonianCycle.html>

r/lec-complexity/hamiltonian-cycle.png

複雑性クラスPとNPの関係

  • NP困難問題(NP-hard): クラスNPのどの問題よりも困難な問題

    • NP困難な問題はクラスNPに属するとは限らない

  • NP完全問題(NP-complete): NP困難でクラスNPに属する問題

    • NP完全問題を多項式時間で解くアルゴリズムは知られていない

\(P \not= NP\) 予想

現代数学上の最も重要な未解決問題の一つ.

NP完全問題

充足可能性問題

Satisfiability Problem; SAT

ある命題論理式(ブール式)Fが与えられた時,その中の論理変数(ブール変数) \(x_1,x_2,\ldots,x_n\) の値に真(True;1)または偽(False;0)を割り当てることに より,F全体の値を真にすることができる = 充足可能 か否かを判定する問題

e.g. 1)

\begin{equation*} F = (x_1 \lor \lnot x_2) \land (\lnot x_2 \lor x_3 \lor \lnot x_4) \land (x_1 \lor x_3) \land (x_1 \lor \lnot x_3) \land (x_3 \lor \lnot x_4) \land (\lnot x_1 \lor x_4) \end{equation*}

SATはNP完全であることが示された最初の問題.

Note

そもそもSATはNP完全という概念を言うために作られた問題.
Cookの定理(1971): SATはNP完全である.

k-充足可能性問題 (k-SAT)

ブール式Fは,節の論理積からなる情報標準系(Conjunctive Normal Form; CNF) として与 えられ,各節内の李てられの数が高々k個のとき,k-CNFと言う.k-CNFの充足可能性を判 定する問題を,k-SATと言う.

  • 2-SAT

  • 3-SAT

Note

  • 証明(Karp 1972): 3-SATはNP完全である

  • 証明(Karp 1967): 2-SATは多項式時間で判定できる

  • (物理) ランダムに生成されたN変数とM節からなる3-SATの臨界挙動

    • M/Nの比(節の数/変数)がある値付近で急激に難しくなる(解くのに時間コストがかかる)

    • DPアルゴリズムで解を見つけるのに要した反復回数を測ったところ,M/N = 4.4 付近 に臨界点

    • → 節の数がバランスした時に,システムの複雑性が創発(分析コストの極大化)

巡回セールスマン問題

Traveling Salesman Problem; TSP

グラフG=(V,E)のハミルトン閉路問題のうち,最小の重み総和(コスト)を持つもの(最短系 ろ)を探査する問題.

ハミルトン閉路問題の上位問題と言える.

これは「NP困難問題

頂点の数Nが大きくなると探査する経路の候補数が爆発的 \(\left((N-1)! \over 2\right)\) に増 大し,手に負えなくなる難しい問題.

e.g.

  • マイクロチップ設計のコスト最小化

  • 物流の配送経路最適化

NP困難問題 自然界の計算複雑性?

クラスP

  • animal transportation networks

    • アリの群れが餌と巣を結ぶ最短経路グラフを作る

  • 水や電気が,エネルギーが最小なルートを通る

クラスNP

  • タンパク質フォールディング問題

    • Bonne Berger and Tom Leighton, 1998, Protein Folding in the Hydrophobic-Hydrophilic (HP) Model is NP-Complete

    • 条件をかなり限定している

    • 自然界のナノマシンは「NP完全」(よりきっと難しい)問題を一瞬で解ける

      • 原理? 人工コンピュータの開発? タンパク質そのものをコンピュータとして利用?

        • 解きたい問題をアミノ酸にエンコーディング

最終課題

「複雑系の科学」と「SFCでの研究・活動」との接点

今学期「複雑系の科学」の講義の中で学んだ項目(スライド参照)の中から3つ以上を選び 関連性を述べた上で,それらのアプローチを組み合わせることで,今後の自分自身のSFC での研究や活動にどのようなポジティブな効果を期待できるか論じよ.

同じセクションのトピックが関連しているのは当然なので,別セクションから選ぶ. (PDFで,学部,学年,使命,学籍番号,メールアドレス記入)

第12回 アメーバ計算:単細胞のコンピュータ?

生きた複雑系である単細胞アメーバ生物・粘菌は、自律分散型計算システムの典型例で ある。ここでは、粘菌アメーバを組込んだバイオコンピュータや、その計算原理に着想 を得たアメーバ型アルゴリズムを紹介する。具体的には、組合せ最適化問題や強化学習 問題を解くアルゴリズムを受講者がMathematicaでプログラミングしてシミュレーショ ンできるようになることを目指す。

第13回 自然計算アーキテクチャ:複雑系を組込んだコンピュータ?

従来のノイマン型コンピュータの性能向上が頭打ちになることが認識される中、近年、 それらとは全く異なる複雑系の物理現象を利用するアーキテクチャをもつ「非ノイマン 型コンピュータ」の研究開発が活発化している。ここでは、カオスニューラルネットワ ーク、CMOSイジングマシン、量子アニーリングマシン、コヒーレントイジングマシン、 電子アメーバなどを紹介し、複雑系で計算する新しいコンピュータの将来像を展望する 。

自然計算とは?

自然計算 は,今世紀に入り理論と実験の両面で自然科学と計算機科学の融合研究が 活発化している学際領域であり,以下のようなステップを通じて新たなパラダウムを創生 することを目標としている.

  1. 自然現象を計算の観点から観察

  2. その観察に基づいて計算モデルを構築

  3. 計算モデルを分析し,普遍化

  4. 計算モデルを自然現象で再実装し,計算の可能性を探求

  5. 普遍化したモデルで自然現象の新たな理解生む

例:

  • 遺伝的アルゴリズム

  • ニューラルネットワーク

  • 焼きなまし法

  • DNA計算

参考図書: ナチュラルコンピューティング・シリーズ.自然計算へのいざない.

自然計算アルゴリズム

復習: 複雑性クラスNP

  • 巡回セールスマン問題 (TSP)

    • 全体でみたときの最短経路(大域最適解)ではないが,最適に見える "局所最適解" に 捕まってしまいやすい

擬似焼きなまし

焼きなまし(annealing) 3

鋼を適当な温度に加熱し,一定時間保持した後,徐々に温度を下げ,鋼組織のひずみを 取り除き, 構造の規則性を向上 させる処理.

擬似焼きなまし (simulated annealing) 4

組合せ最適化問題の解探索において,局所最適化からの脱出に必要な揺らぎ(ランダム 性)を序盤は高く設定し,徐々に低下させることで,最終的に大域最適解に到達するよ う導入する方法.

3

https://en.wikipedia.org/wiki/Annealing_(metallurgy)

4

https://en.wikipedia.org/wiki/Simulated_annealing

2-opt の擬似焼きなまし法

  • 入力:
    グラフ \(G = (V,E), V = \{C_1, C2, \ldots C_N\}\),
    \((C_i,C_j) \in E\) の重みである距離 \(\text{dist}(C_i,C_j)\),
  • 初期設定:
    ルート \(R=(r_1,\ldots,r_{N+1}=(C_1,\ldots,C_N,\ldots,C_1)\),
    暫定最短ルート \(R*\), 最大温度 \(T_{Max}\),
    冷却速度 \(k\), 反復回数上限 \(t_{Limit}\),
  • メインループ:

    1. If \(t = t_{Limit}\) then Stop else goto 2

    2. ランダムに \(i,j\ (1\le i<j<N)\) を選び,スワップルートを以下のように構 成する:

      • \(R_{Swp} = (r_1,r_2,\ldots,r_{i-1},R_{Rev(i,j)},r_{j+1},\ldots,r_{N-1},r_N,r_1)\)

      • \(R_{Rev(i,j)} = (r_j,r_{j-1},r_{j-2},\ldots,r_{i+2},r_{i+1},r_i)\)

      • \(t := t+1\)

    3. If ルート長変化 \(\Delta L(R) = L(R_{Swp})-L(R) < 0\) (改善した)
      then \(R := R_{Swp}\) goto 5
      else goto 4
    4. If \(\text{Exp}\left(\frac{-\Delta L(R)}{T_{Max}-k_t}\right) < \text{Rand}[0,1]\) (熱で揺らぐ)
      then \(R := R_{Swp}\)
      else \(R := R*\) goto 5
    5. If \(L(R_{Swp}) < L(R^*)\) (ルート長が過去最短)
      then \(R^* := R_{Swp}\)
      else \(R^* := R^*\) goto 1
  • 出力:
    \(G = (V,E)\) のハミルトン閉路のうち,最小の重み総和を持つ最短ルート.

Note

  • 冷却スケジュールの設定が,解探索の「速さ(小さいt)」と「質(短いルート長)」に 決定的に重要.

  • しかし,最適な冷却スケジュールは問題に依存

  • ノーフリーランチ定理(Wolpert 1995): どんな問題にも有効なアルゴリズムは存在し ない.(特定の問題に有効な冷却スケジュール設定方法の存在は否定していない)

ニューラルネットワーク

Hopfield Model (Computing with neural circuits: A model J. J. Hopfield, David W. Tank. Science 1986)

脳神経回路網の数式, 甘利俊一, 1978 → Hopfield-Tank-Amari Model と呼ぶべき

N都市の巡回セールスマン問題.(\(N = 5\))

\(N \times N\) ニューロンによる表現.

  • リカレント(全結合)ニューラルネット

    • 結合(重み行列の要素)の数: \(N^2 \times N^2\)

\(Vk\): 都市 \(V\)\(k\) 番目に訪問

  • ニューロン \(Vk\) の時刻 \(t\) の状態:

    • \(X_{Vk}(t) \in \{1, 0\}\) (1→発火,0→非発火)

ボルツマンマシン

Boltzmann Machine

Hopfield-Tank-Amari モデルを発展

第14回 総括:複雑系とSFC

これまでの講義内容を総括し、生命システム、情報システム、経済システム、社会シス テムを含む、複雑なシステムの全体像を複雑なまま捉える複雑系科学の数理モデルやデ ータ解析手法は、自然科学、社会科学、情報通信技術などの多様な学問分野を横断的に 統合するというSFCの理念を具現化する一つのソリューションを与え、受講者の将来の 研究開発やシステム設計に有用となり得ることを示唆して締めくくる。

これまで授業で扱った内容を踏まえて,青野先生自身の研究の紹介を行う.

複雑系科学の未来

  • 復習: 「複雑系の科学」の研究史

  • 計算能力の向上 => 理論中心の研究から,「ハードウェア」や「ウェット」な研究へと 重心が移っているような印象

  • 「サイバー空間」の発見から「フィジカル空間」への融合と発展

応用例: 物流業界の労働不足問題

  • ラスト1マイルの問題

  • 最後に複雑性・多様性が圧倒的に高くなる: i.e. 地形,家,玄関の形,人とのコミュ ニケーション, etc

  • 従来のロボットは,「ビット」(情報)と「アトム」(物質)が分離したハードロボット.

  • 登場したソフトロボットの可能性: 「ビット」と「アトム」の協会が曖昧な機能

    • 「ドラえもんの手」: 柔らかい素材がつかむ対象を包み込んだ状態で吸引して固定す ることで,様々なものをつかむことができる.

    • 外側に広がる無際限な複雑性を,ロボットの中に取り込む例といえる.

  • 情報の属性を持つ物質: 状況に対する知識を蓄えて正しい判断をできる物質

  • 物質の属性を持つ情報: 執拗や体積をもち,物体を動かす力を伝達できる情報

→ なぜ粘菌アメーバか? : 「ビット」と「アトム」が未分化な生物

粘菌アメーバコンピュータ

  • 一部を切り取っても完全なシステム

  • 8つに分けた個体を寒天の上におき,また1つに融合する

  • 中枢がない 自律分散型のシステム

  • 植物と動物,両方の特徴をもつ

  • 真性粘菌(モジホコリカビ): 多核細胞アメーバ生物 https://ja.wikipedia.org/wiki/%E3%83%A2%E3%82%B8%E3%83%9B%E3%82%B3%E3%83%AA

    • 液体(粘形質)の流動が,心臓と同じように行き来している

    • 流動が激しい部分は管の径が大きくなる → ポジティブフィードバックループがある.

  • 結合振動子がある

    • 位相がシンクロする場合,半周ずれる場合,二重の場合

    • ずっと同じ振動ではなく,確率的に別の振動に変わる「ゆらぎ」もある

  • 迷路の入り口と出口に餌をおくと (餌はオートミール),最短経路を結ぶ :: これもポ ジティブフィードバックループ

属性:

  • 発振

  • 近接相互作用

  • 長距離相互作用

  • 揺らぎ

  • 学習(記憶)

→ 原始的な脳の特製を持っているのではないか?

アメーバネットワークを使った,ニューラルネットワークを作れないか.

  • 多数の溝を持った容器にアメーバをおく

  • 光が当てられなければ,面積を最大化して餌を獲得したい

  • アメーバは光が嫌いなので,プロジェクターを使って特定の足に光を当てるというフィ ードバックループを作り出す

  • 溝に光を当てるパターンは, Hopfield-Amari model の変化番で重み付けを行う

  • 「両隣に足が伸びてはいけない」などの単純なルールにしたがって光を当てていくと, 複数の安定状態にいたる.

    • これはある種の充足可能性問題(SAT)に形式化することができる

    • リソース配分問題でもある

  • 64本の溝を使い,巡回セールス問題をときたい

  • アメーバ+バウンスバック制御のハイブリッド

  • 最適解ではないが中央値に近い解を発見

  • 時間・空間相関が強いアメーバの方が良い結果を導く傾向にあった


  1. 一固体が全体に広がった状態(64本が全て0)

  2. 一細胞ではなく,コミュニケーションできない二つの違う細胞を置いて広がるのを待 つ

  3. 一つの細胞を広げるが,広がったところで壁をもうけてコミュニケーションができな いようにする

これらを比較して,性能がどれくらい落ちるか?

  1. ほぼ見つけられる

  2. 全く見つけられない

  3. 壁を作ってすぐに計算させると,ほぼ性能は変わらなかったが,30分経つと解けなく なってきた.

  • 可能なルート数は指数関数的に増えていくが,線形時間でNP完全を再現するモデル

  • Ameoeba: SATのバウンズバック規則

  • 明示的な評価関数は与えていない

  • ダメなことしか教えていない

CPUと比べると,アメーバの方が圧倒的に遅いが,ループ回数は圧倒的に少ない. → 並列型コンピュータ

CPU時間では劣るが,このアルゴリズムの動作を実際に行うハードウェアがあれば,高速 化できるはず →

アメーバ型最適化チップ:

  • アナログ回路: 北大との共同

    • 回路自信には「ゆらぎ」がないため,外から与えてる

    • → 電子ブラウンラチェットを使って,熱雑音を取り出し,確率的な動作を実現しよう としている(1つでは検証済み)

  • 他にも様々な,ノンフォイマン型マシンが登場している.

  • アメーバが型ロボット: 整地歩行のための周期的パターン →

    • 絶対に転倒する歩行をダメだしするバウンスバック制御によって,未知の環境でも転 倒しない歩行パターンを自ら発見できる