☆コンピュータサイエンスの体系
※デニング図
☆コンピュータサイエンスのパラダイムと専門分野
理論パラダイム
数学を源とした理論体系
抽象化パラダイム
実験科学的方法を源にしたモデル体系
設計パラダイム
エンジニアリング体系
※専門分野
◎チューリングマシン
※Turing Complete チューリング完全
⇒チューリングマシンでできることと同等のことができること
◎セルラ・オートマトン
ノイマン
並列計算モデル、自己増殖、自己複製
⇒同期型、超細粒度、並列計算モデル
⇒発想された当時は、ハード量が多くなり過ぎ現実になるとは思われなかった
⇒セルラ・アーキテクチャの並列計算機の実現
◆Kung、シストリック・コンセプト、シストリック・コンピュータ
◆DAP610(Active Memory Technology)
4K個のビット・プロセッサをメッシュ結合
超並列画像処理マシン
◆MasPar MP-1
MasPar社
16K個の4ビットプロセッサをメッシュとクロスバー結合で接続
◎超並列/超分散処理
◎コネクショニズム
◎パラレル・プロセッサ
◎ニューロ/ファジイ・コンピュータ
※パーセプトロン
⇒Minsky & Papertによりダメ印となった
⇒ニューロとして復活
※ファジイ理論
KalmanとZadehが論争
◎オプティカル・コンピュータ
◎バイオコンピュータ
☆理論
◎符号理論
※情報を表現する対象そのものを情報担体と呼ぶ
⇒情報担体を記号列に変換することを符号化と呼ぶ
◆２元符号化
＿◇補数
負の数の表現法のひとつ。減算を加算にして扱える。
※ｒ桁のｎ進数の数Ａの補数は
ｎ＾ｒ－Ａ
※２進数の場合
０と１を反転（１の補数）し、１を足すことで２の補数が得られる。
＿◇符号化
①標本化 sampling
②量子化 quantization
③符号化 coding
◆情報源符号化
＿◇情報量
ある事象が起こったときに得られる情報量
⇒事象の起こる確率が小さいほど大きい
＿◇生起確率と情報量
ある事象Ｊが起こる確率Ｐ⇒Ｐ（Ｊ）
実際にＪが起こったときに得られる情報量をＩ（Ｊ）
Ｉ（Ｊ）＝－ｌｏｇ２｛Ｐ（Ｊ）｝
※このときのＩ（Ｊ）の単位をビットと呼ぶ
＿◇平均情報量
※無記憶情報源
生起する事象同士に関連がなく独立している情報源
※平均情報量（エントロピー）
無記憶情報源において、事象Ｊ１～Ｊｎの生起確率からもとまる平均情報量Ｅ
E = P(J1)xI(J1) + … + P(Jn)xI(Jn)
※最小および最大平均情報量
無記憶２元情報源においては
最小⇒一方がおきて、他方がおきない。生起する事象が特定できる場合
Emin=1*(-log2(1))+0*I(J2)=0
最大⇒均等に事象がおき、どの事象が起こるかわからない場合
Emax=…=1
※自然界ではエントロピーが最大になる傾向がある
＿◇マルコフ情報源
記憶情報源のひとつ
ｎ重マルコフ情報源とは、時間的にｎ回前までさかのぼった事象が継続的に関係しながら生起するような情報源
※ｎ＝１の場合を単純マルコフ情報源と呼ぶ
⇒状態遷移図で表すことができる
※事象Ｊ２が生じた後に事象Ｊ１が生じた場合の確立
Ｐ（Ｊ１｜Ｊ２）
＿◇エルゴート情報源
ある情報源からの生起事象を長時間にわたって観察すると、ある値に帰着するような情報源
◆通信路符号化
＿◇通信速度と通信路容量
平均情報量を、通信路を伝達する情報に対して適用する
⇒これに時間の概念を導入することで通信速度と容量を扱うことができる
※事象数N,事象J1,事象J2が起こる。その情報を通信路で送るのに必要となる時間をt1,t2とする。
J1の情報量 -N*P(J1)*log(P(J1))
J1すべてを送るために必要となる時間 t1*N*P(J1)
全情報量E
E = -N*P(J1)*log(P(J1)) -N*P(J2)*log(P(J2))
全伝達T
T = t1*N*P(J1) + t2*N*P(J2)
通信速度 TR
TR = E/T
※通信速度が最大になった値を通信路容量Cとする
⇒２つの情報を扱う場合には、それぞれの情報量と伝達時間の比率が等しいとき
TRの式の両辺をP(J1)で微分し、０とおいて極値を求める
dP(J2)/dP(J1)=-1を代入、整理する
-log(P(J1))/t1 = log(P(J2))/t2 = -C
＿◇誤り訂正符号化
※冗長検査 余分な符号を付加する
パリティ検査（奇偶検査）
CRC Cyclic Redundancy Code
◆暗号
cryptosystem
平文 plaintext
暗号化 encrypt encryption
暗号文 ciphertext
暗号解読 cryptanalyze, cryptanalysis
＿◇DES
Data Encryption Standard
＿◇FEAL
Fast Data Encipherment Algorithm
◎命題論理
◆記号論理学
（数理論理学）
古典論理学
命題論理
述語論理
非古典論理
多値論理
直観論理
様相論理
＿◇命題論理
命題の持つ真理値のみに着目する
※命題
真か偽か規定できる叙述
⇒判定の論拠は論理(logic)でなく理論(theory)
※真理値
truth value
※命題変数
命題を組み合わせるときに、命題となる叙述を変数として扱う
※基本命題 ひとつだけの命題変数で構成されるもの
※論理記号 命題変数同士を組み合わせるために用いる記号
論理和 ＋、∨
論理積 ・、∧
論理否定 ￢
含意 ⊃
命題１が真ならば命題２も真のとき、真
命題１が偽ならば命題２にかかわらず真
※複合命題 ２つ以上の命題変数を論理記号によって組み合わせたもの
＿◇論理代数
ブール代数
※命題の論理演算を代数的に処理する
＿◇述語論理
命題があらわす事象の関係や性質に着目する
変数の具体的な値を与えることで真偽性が定まる述語に対する推論形式
※述語論理の構文
述語と限定作用素
※述語
「ｘはｙである」
個体変数ｘにある値を与えることによりｙであるの真偽がきまる
⇒y(x)と表す
※限定作用素
①全称作用素
ある個体変数(x)に対してすべてのxにおいてという意味を付加する
∀
例）すべての自然数は整数である
(∀a)(N(a)→I(a))
②特殊作用素
ある個体変数(x)に対して「。。。となるようなxが存在する」
∃
例）a<bを満たすべてのaとbについて、a>t*bとなるtが存在する
(∀a)(∀b)(∃t)(L(a,b)→G(a,M(t,b)))
※導出原理
１階述語論理
２階述語論理
高階述語論理
＿◇Prolog
※ホーン節
論理を条件と結論の関係として記述する際に、結論部が一つだけで構成される
◎ノイマン・アーキテクチャ
John von Neumann
◆ノイマン・ボトルネック
Neumann bottleneck
ノイマン型計算機は、CPU、メモリ、両者をつなぐバスからなる。
メモリは多量にあり、それらはビンに詰め込まれている
バスはビンの狭い口を経由してビンの外側にあるCPUとつながっている。
◆ノイマン・サイクル
CPUはプログラムカウンタとよばれる逐次的に動作するカウンタをもち、一つの命令を次の４つの動作に分解して処理する
①命令フェーズ
instruction phase
フェッチとデコード
②オペランド・フェーズ
operand phase
オペランドの番地を計算し、メモリから取ってくる
③実行フェーズ
execution phase
命令を実行する
④オペランド・フェーズ
operand phase
結果をメモリに格納する
◎基本モデル
◆Turing machine
◆random access machine
◎アルゴリズムの計算量とその評価
◆計算量の定義
※計算量 complexity 計算複雑度
領域量(space complexity)
時間量(time complexity)
＿◇クラスP、クラスNP
※クラスP
多項式時間帰着可能問題
効率のよいアルゴリムズがある問題。
データ量に応じて計算時間が増える。増え方はいろいろだが、見積もり可能。
※クラスNP
計算の手間が簡単には求まらない。
最悪の場合、答えが出ない
◆問題例の規模
一つのアルゴリズムであっても、問題例によって計算量は異なる
※問題例の規模(size)Ｎを基準にして、計算量がＮのどのような関数であるかを評価
⇒N*logN, N^2, 2^N
※問題例の規模：通常必要な入力長さとする
◆オーダー表記
order notation
※Ｎの関数形を議論するとき
⇒データの格納法などアルゴリズムの細部の影響を除外
⇒定数倍の違いを無視
T(N)=O(f(N)) オーダーf(N)と読む
⇒ある定数 c と N0 が存在し、N≧N0に対し常に
T(N)≦c*f(N)
例）N^2, 100*N^2, 1000*N + 2*N^2 ⇒みなO(N^2)
※O(1) : 定数オーダー
Ｎに独立なある定数で抑えられる
※オーダー表記においては、等式の右辺が左辺より精密な情報を提供することはない、と約束して＝記号を使う
◆計算量
同じ規模Ｎを持つ問題例が多数（無限個）存在する場合全体評価のために考える
＿◇最悪計算量
worst-case complexity
規模 N のすべての問題例の中で最大の計算量を要するもの
＿◇平均計算量
average-case complexity
規模 N の問題例のそれぞれの生起確率を考慮して決める
＿◇多項式オーダー
polynomial order
※アルゴリズムの実用性を判断するのに用いられる
※多項式オーダー
⇒問題例の規模Nに対し、ある定数kを用いてO(N^k)と書ける場合
※多項式より大きなオーダーはＮにともなって急激に大きくなるので実用的でない
⇒O(N^(logN)), O(k^N), O(k^(MN))
※多項式時間アルゴリズム
plynomial time algorithm
⇒多項式オーダーの時間量をもつアルゴリズム
データ構造
data structure
※１語文のデータを格納する基本単位cell
※cellを結び合わせてアルゴリズムの実行に適した構造にまとめあげたもの
◆リスト
list
※要素を0個以上一列に並べたものをリストという
※n=0のとき空リスト(null list)
※配列(array)もリストを実現する具体的なデータ構造の一つ
⇒リスト長が変化する操作は簡単ではない
⇒ポインタ(pointer)を用いたデータ構造が適する
＿◇連結リスト
linked list
※構造体とポインタを用いて実現
struct cell { int data;
struct cell *next; }
＿◇スタック
stack
※リスト要素の挿入や削除を限られた方法で行うデータ構造の一つ
CREATE(S)
POP(S)
PUSH(x, S)
※LIFO(last-in-first-out)リスト
※プッシュダウン(push down)リスト
※連結リストにより基本操作はすべてO(1)時間
＿◇待ち行列
queue
※リスト要素の挿入や削除を限られた方法で行うデータ構造の一つ
CREATE(Q)
ENQUEUE(x, Q)
DEQUEUE(Q)
※FIFO(first-in-first-out)リスト
※連結リストにより基本操作はすべてO(1)時間
◆グラフとネットワーク
Graph
グラフGは、有限個の節点(node, 頂点vertex)の集合Vとそれらをつなぐ枝(branch, 辺edge)の集合Eからなり、
G=(V, E)
と記される。
E⊆VｘV
※各枝 e=(u, v)
⇒端点(end node)の対で示される
⇒uとvに接続する(incident)という
＿◇グラフの種類
※無向グラフ
undirected graph
※有向グラフ
directed graph, digraph
⇒(u, v)と(v, u)を区別
⇒アーク(arc, 弧）ともよぶ
※多重グラフ
multigraph
⇒同じ端点ついをもつ枝が複数個存在することを許す場合
※単純グラフ
simple graph
⇒一本に限る場合
※次数(degree)
グラフGにおいて節点vに接続する枝の本数
⇒deg(v)
⇒有向グラフにおいて、出る枝の本数を出次数(out-degree), 入る枝の本数を入次数(indegree)という
※部分グラフ
subgraph
G=(V,E)に対し、V’⊆V, E’⊆Eを満たすG’=(V’,E’)がグラフであるとき
※生成部分グラフ
induced subgraph
⇒導出部分グラフ
⇒節点の部分集合V’⊆Vに対し、V’内に両端点を持つ全ての枝e⊆Eの集合をE_v’
G’=(V’, E_v’)
をV’の生成部分グラフという
＿◇パスと連結
※路(path)
グラフG=(V,E)の節点列
P: v1, v2, … , vk
が(vi, vi+1)∈E, i=1,2,…,k-1をみたすとき（有向グラフの場合は、枝の方向がviからvi+1に向いていること）、始点v1から終点vkへの路とよぶ
⇒v1からvkへ到達可能(reachable)
⇒路Pの長さは枝の本数k-1
※単純路
simple
⇒Pの節点viが全て異なる
※閉路
cycle, circuit
⇒始点v1と終点vkが等しい
※単純閉路
v1からvk-1が全て異なる
※連結
connected
◆木
＿◇2分探索木
自分より小さい→左、自分より大きい→右
間順走査。。。左ー自分ー右。。。大きさの順になる。
前順走査。。。まず自分、それから左、戻ったら右。。。元の木と同じものが構成できる。
＿◇AVL木
高さの差が１になるように２分木を維持。追加、削除時に回転が必要。AVL木は左右の子の木の高さに大きな違いがないため、探索の時間O (log2N ) が保証される。
※二分探索木の一種であり、探索時間には差がない。データ管理に手間がかかるので、探索時間を保証することが必要な用途のみに向く。
＿◇B木
データを区切るための値と、子のレコードを参照するフィールドをもつ、このとき、区切るための値の個数は、フィールドの数より1少ない。
※B木は、レコードを外部記憶装置に保管し、必要なレコードだけをメモリに持ってくることで、多量のデータの保管と検索を行う用途に向く。検索以外でも、データの追加や削除で、外部記憶装置へのアクセスが多数必要になることもあるが、多くの場合よく参照されるレコードに偏りがあるため、最近使用したレコードをメモリに保存しておくことで効率を上げることができる。
＿◇トライ
◆ヒープ
ヒープ構造は、どこでもa [i ] ≧a [2×i ]、a [i ] ≧a [2×i +1] が満たされている。
◎整数
└ｘ┘ floor（床、ｘの整数部分）
┌ｘ┐ ceiling（天井、ｘより小さくない最小の整数）
◆Euclidの互除法
◎ハッシュ関数
※ハッシュ値の計算でのオーバフロー
長い文字列のハッシュ関数値を求めるときに、文字列全体を式通りに整数値に置き換えると、通常の整数変数ではオーバフローが起こる。この場合は1文字ずつ剰余をとりながら計算をするとよい。
h = 0
iを1から文字列の長さまで増やしながら、
h = (h *256 + code(c i )) % m
※ “%” は余りを求める計算
※この方法でも、m が非常に大きい場合にオーバフローが起こることがあるので、ビット列のシフトやビット演算を活用したハッシュ関数を用いてもよい。
◎ソーティング、探索
◆ソート
※ソートアルゴリズムの「安定」
同じキー値を持つ要素のソート前後の位置関係が保たれる場合⇒安定
⇒cのqsort関数は安定とは限らない
＿◇選択法
i を 1 からN -1 まで増やしながら、
k ← i
j を i +1 から N まで増やしながら、
a [i ] < a [k ] ならば、 k ← j i ≠ k ならば、 a [i ]とa [k ]を交換する ＿◇バブルソート i を 1 からN -1 まで増やしながら、 j を 1 から N-i まで増やしながら、 もしa [j ] > a [j+1 ] ならば、
a [j ]とa [j+1 ]を交換する
＿◇挿入法
i を 2 からN まで増やしながら、
v ← a[i], j←i
j>1かつa[j-1]>vである間、
a [j] ← a [j-1]
j ← j-1
a [j]←v
＿◇マージ法
R<-1
R < Nの間、
k<-1
k<=Nの間、
i<-k, j<-i+R, k<-j+R
もしj<Nなら、 もしk>Nなら
k<-N+1
merge(i,j-1,j,k-1,i)
iをからNまで増やしながら、
a[i]<-b[i]
R<-2*R
＿◇クイックソート
quick sort
考案者 C.A.R. Hoare
※配列内の一つの要素（枢軸 pivot)に注目し、枢軸以上のグループと以下のグループにわけることを繰り返す。
①配列の左（先頭）と右（末尾）にカーソルをおき、左は枢軸以上、右は枢軸以下の要素をさがす。
②みつけた左右の要素を交換する。
③これをカーソルが交差するまで繰り返す⇒枢軸より右に枢軸以上の要素が、左に以下の要素が並ぶ。
右グループと、左グループにわけて上記の処理を分割によってつくられたグループの要素数が１になるまで繰り返す。
◆探索
＿◇２分探索
binary search
要素がソートされている配列から探索を行う
中央要素に着目し、比較の度に探索範囲を半分に絞り込む
⇒繰り返し毎に範囲半分⇒比較回数の平均はlogN
⇒探索失敗はlog(N+1)、探索成功は約log(N-1)
※天井関数
ceiling
☆計算理学
計算物理
Computational Physics
計算工学
Computational Engineering
◎計算機シミュレーションの分類
◆対象による分類
＿◇粒子系
微視的な原子、分子電子。
微視的な力学、電磁学、量子力学にもとづく運動
⇒星の運動もそれぞれを質点と考えればこの分類
＿◇連続系
空間を粗視化。個々の粒子でなく、空間的に連続に変化する粒子の密度、エネルギー分布などを考える。
流体力学
有限要素法
※同じ問題を粒子系、連続系の両方で扱うこともできる
＿◇格子系
結晶状態で粒子の位置が固定⇒取扱いが簡単になる
Isingスピン系
※複雑な体系を粗視化してとり得る状態を制限し、より単純な格子系に置き換えることが行われる。
◆シミュレーション問題の設定
＿◇初期値問題
※ある粒子配置の時間変換をおいかけるもの
⇒最初に設定した粒子配置とその後の変化の対応
⇒ＭＤ法が中心
＿◇平衡状態計算
平衡状態で体系が示す性質を調べる。
⇒実現する状態とパラメータの値の変化による構造変化
⇒初期状態によらない結果を得ることが重要
⇒平行状態への緩和過程は捨てる
⇒Monte Carlo法(MC法)も用いられる
◆ＭＤ法
分子動力学(molecular dynamics)法
※古典的力学の法則に従って粒子を動かす
運動方程式（微分方程式）の数値積分
⇒粒子の運動（時間発展）を逐次求める
※ｎ個の粒子の運動方程式＝ｎ個の２階常微分方程式（運動方程式)
d^2 r_i
m_i * ——- = F→_i
dt^2
⇒このとき力は、位置エネルギーφの座標につじての微分（勾配）から求まる。
∂φ
F→_i = – —–
∂r_i
※一般に計算時間の90%は力の計算
①一般の数値積分ではRunge-Kutta法が良く用いられる
②ＭＤではより軽い
中心差分法(Verlet法）
予測子・修正子法(Gear法）
predictor corrector
＿◇中心差分法
d^2 r_i r_i(t+⊿t) – 2*r_i(t) + r_i(t-⊿t)
——- = ———————————-
dt^2 (⊿t)^2
を変形し
F_i(t)
r_i(t+⊿t)=2*r_i(t) – r_i(t-⊿t) + ——(⊿t)^2
m_i
※全体の誤差は(⊿t)^2に比例する
※全体のエネルギーが保存される問題では保存則を使って検証する
⇒⊿tを変えたときの誤差の大きさも調べること
※時間反転に対して対称
※積分安定性がよい
※計算精度はあまりよくない。速度が座標と同時には求まらない。
⇒力が速度に依存する場合にはアルゴリズムの一部修正が必要
＿◇予測子・修正子法
座標とその微分をTaylor展開の形で予想する
⇒n階まで
さらに補正値Ciで修正する。
補正値は次数により異なる。
※⊿tが小さいとき精度がよい
※ポテンシャルの不連続な変化に弱い。
※時間反転に対称的でない。
◆モンテカルロ法
＿◇粒子系シミュレーションにおけるモンテカルロ法
※粒子の動きを確率的に行って、平衡状態分布を作り出す
ある状態 i の出現確率
⇒状態 i での体系の全エネルギーをE_iとして
正準分布(canonical distribution または Boltzmann分布)
f_i = C * exp(-E_i/(k*T))
k:Boltzmann定数
T:温度
※実験において測定されるある物理量Ａの値は、平衡状態でのＡの重みつき平均
=Σ[i]A_i*f_i
に対応する
⇒巨視的な体系では位相空間の中の非常に限られた領域に含まれる状態のみが大きな確率で現れる
⇒ある粒子配置に近い状態の中から新しい配置を状態の重みf_iに比例した回数だけ現れるようにし、作り出した状態の数Ｍで割って平均を求める
＿◇マルコフ過程
ある状態 i から他の状態 j へ順次変わっていく確率過程
⇒１回の変化を１ステップと呼ぶ
※遷移の過程 P_ji が現在の状態だけで定まり、過去の履歴によらないとき、Markov過程と呼ぶ
※平衡状態分布f_i（主に考えるのは正準分布）が得られるための十分条件
①エルゴード性
ある状態から遷移確率 P_jiの基本的な動きを続けていくことにより、すべての可能な状態をつくすことができること
②詳細釣合
平衡分布f_iに達したとき、ある状態iから他の状態jに変わる確率Pijfiと、jからiへ変わる確率Pijfjが等しいこと
◆Car-Parrinello法
◆KdV方程式
Korteweg-de Vries
※粒子のように個性を保持して動く波（ソリトン）
◎粒子系のシミュレーション
多粒子系
例）コップ一杯の水 Avogadro数 6e23の10倍の水分子が含まれる。
◆粒子間相互作用
その結果の妥当性は、計算に用いた粒子間相互作用が、現実物質をどの程度よく再現しているかに依存
※粒子間相互作用を定める位置エネルギー（ポテンシャル）Φ(r1,…,rn)は原理的に求められるが膨大
⇒簡略化した相互作用を仮定
＿◇２体相互作用
※相互作用⇒多数の粒子の配置に依存
※２体力近似
２粒子ごとの相互作用の和で表す
Φ=ΣΣ[i<j]φ(r_ij)
r_ijは２粒子i,j間の距離
※３体力、４体力の精度よい決定は難しい
※良く知られている２体相互作用
①万有引力相互作用 G*mi*mj/rij
②電荷間のクーロン相互作用 qi*qj/4π*ε0*rij
③中性粒子の間のvan der Waals相互作用 -b/r_ij^6
※反発項の表現
①ベキ型 c/rij^n
②指数型 A*exp(-α*rij)
＿◇Lennard-Jonesポテンシャル
希ガスに対するよいモデル
◎物質設計の数理
◎計算地球流体力学
☆Cloud
◎技術的特徴
◆Scale-outアーキテクチャ
数を増やして性能を向上する
＜＞スケールアップ
１台のマシンで機能や性能を向上する
※Scalability, Availability
※Key/Value型データストア
※Eventually Consistency概念
◆GFS
Google File System
通常のファイルシステムの機能の一部を含まず、大規模なデータを安全に処理することに特化している。
※クライアント、１台のマスタ、多数のチャンクサーバから構成される。
クライアント＝アプリケーションプログラム
マスタ＝メタ情報（チャンクの配置など）を管理
チャンクサーバ＝チャンクをローカルディスクに保持
※チャンク＝６４Ｍバイト
デフォルトで３つの複製が作成され、異なるチャンクサーバに納められる。あるチャンクサーバが停止しても、マスタは３複製を維持するため、失われていない複製から別のチャンクサーバに複製をつくる
◆BigTable
大規模データの分散ストレージだが、検索操作が実装されておらず、キーに対するスキャン操作のみが可能
※基本データ構造
(行キー、列キー、タイムスタンプ)→データ
データは単なるバイト列
行と列からなるといっても「疎」
データは行キーに対してソートされて保持
連続する行キーの範囲に対してスキャンできる
※ある行キーに属するデータに対する読み書きはアトミック
※タブレット
行キーを単位に分割したテーブルの単位
※クライアント、マスタ、タブレットサーバから構成されるが、タブレットサーバはＧＦＳのクライアントである
※Chubby
クライアントとマスタ間に入る小容量データとロック機構に特化した特殊なファイルシステム
◆MapReduce
汎用の並列データ処理機構
◆Google App Engine
PaaS型のクラウドサービス。Webアプリケーションを構築するための枠組みをクラウド上で提供する。
※枠組みにそって記述すればスケーラブルなサービスが構築できる
※PythonとJavaで記述
※負荷に対して自動的にスケールアウトする
※Entity
AppEngineのデータストアの基本要素
複数のProperty（名、値のペア）を収めることができる
個々のEntityに対して自由にPropertyが定義できる
※Kind
複数のEntityをまとめたもの
※検索のために別のテーブルSingle-property indexを持つ。Kind,Property名、Property値を鍵としてソートしたもので, Entityキーを値とする
◎Amazon
◆Amazon Web Services (AWS)
＿◇Amazon Elastic Computing Cloud (EC2)
一種の仮想マシンのホスティングサービス。 Amazon Machine Image(AMI)と呼ばれる実行イメージをインスタンス化することで仮想マシンを起動する
☆ソフトウエア工学
◎プログラミングパラダイム
☆最適化問題
combinatiorial optimization problem
解の中からもっとも適切な解を導き出す必要のある問題
⇒解を選ぶことを最適化(optimization)という。
◆全網羅法
total search method
全網羅探索法、全解探索法、列挙法
◆ランダム探索法
random search method
解空間(solution space)の中から無作為にいくつかの解を選び出して、一番よい解を取り出す方法
◆統計による方法
検索パターンの選び方に、過去の経験や統計を利用
☆AI
◎人工知能研究
「形式指向研究」
述語論理、定理証明、知識表現、探索、構文解析、意味論
「内容指向研究」
知識ベース、知識獲得、知識共有・再利用
◎GA
①遺伝子をいろいろ作る
②それぞれの遺伝子を評価する。
※評価方法がうまく進化するかどうかの鍵
③順位の低い遺伝子を淘汰する。
※淘汰についても方法（エリート戦略、ルーレット戦略など）あり
④子孫の遺伝子を作る。
※親の選び方にもいろいろあり。
※遺伝子の交叉
※突然変異（確率はかなり低い確率に抑える必要あり）
⑤
◎NN
パーセプトロン
①入力セル、出力セル、その結合の仕方と初期値を定める。
②学習
入力セルはそれぞれへの入力があれば、決められた値を出力セルへ送る。
出力セルは、与えられたスレッショルドを越えれば偽を、そうでなければ真を出力する。
この判断を判定し、正しい判断でなければ各セルの値を修正する。
真と出力するべきなのに、偽であった場合は、関係した入力セル（入力されていないセルを除く）の値を減らし、出力セルの値を増やす。逆の場合は、逆の操作をする。
※なお、学習については、エラー値という判断基準を持ってそれを下回れば
完了とする。
◎エキスパートシステム+ファジー
◆IF THEN ELSEルール
◆ルールについての確信度と、その評価の仕方
◆入力値のファジー理論による度合いへの変換。
◎オントロジー
ontology
元は哲学用語、個々に存在するモノの特殊な性質ではなく、それらに共通の性質を研究すること。存在学。
「存在に関する体系的な思想や理論（存在論）」
人工知能では「概念化の明示的な記述」
概念であると同時に現実世界を正確に記述・表現する技術でもある
※知識ベースに依拠する考え方
（実行可能性、知識ベース構築のコンポーネント、部品などの方法を重視）
※自然言語処理に依拠する考え方
（語彙、辞書、索引、コーパスなどの観点を重視）
※コンセプト／哲学レベルの研究に依拠する考え方
（より汎用性の高い上位モデルの立場に固執）
☆典型的デモ関数など
◆フィボナッチ数 fib[n] の数学的定義
fib[0] = 1
fib[1] = 1
fib[n] = fib[n-1] + fib[n-2] (n > 1)
☆省メモリ算法
◆兎と亀法
ループを発見するための算法
兎と亀に対応する２つの変数を用いる
亀。。。基本ステップの速さ
兎。。。亀の２倍の速さで進む
そのうち、兎が亀に追いつくのでループであることが分る。
その後、兎だけを先頭にもどし、亀と同じ速さで進ませる。
⇒するとループの先頭で再び出会う
◆定数領域アルゴリズム
constant-work-space algorithm
☆数値計算法
計算機の実数計算
⇒有限桁の近似計算
◆誤差
＿◇離散化誤差
極限を有限で打ち切ったり、近似式を用いたりする計算法そのものから生じる誤差
※同義
打ち切り誤差、公式誤差、理論誤差、近似誤差
＿◇丸め誤差
実数値を有限桁の浮動小数点数で扱うために生ずる誤差
※実数ｘはそれに近い浮動小数点数 xf で近似的に表現される
⇒上下２つの候補からどちらかを採用する
切り捨て
４捨５入((β/2-1)捨(β/2)入)
※マシンエプシロン (machine epsilon)
実数 x が Fmin ≦ | x | ≦ Fmax の範囲にあるとき、
xf = x(1+εx), |εx|≦εM
がなりたつ場合、浮動小数点体系と丸めの方式で決まる数 εM を
マシンエプシロンと呼ぶ
⇒β進n桁で切り捨て εM=β^(1-n)
⇒β進n桁で４捨５入 εM=(β^(1-n))/2
※厳密な４捨５入はβが偶数のとき
※オーバーフロー
overflow
|x|＞Fmax
※アンダーフロー
underflow
|x|＜Fmin
＿◇誤差の発生と伝播
※２つの実数 x, y に対する演算φの結果z
z=φ(x,y)
⇒計算機上での実現
①x,yは浮動小数点数 xf, yf に丸められる
②近似的な計算φ~がほどこされる
③結果は浮動小数点数 zf に丸められる
zf – z = [φ~(xf,yf)-φ(xf,yf)] + [φ(xf,yf)-φ(x,y)]
※演算φにおける発生誤差
δ=φ~(xf,yf)-φ(xf,yf)
元のx,yが浮動小数点数であっても生じる誤差
⇒通常
|δ|≦c * εM * |φ~(xf,yf)|
※桁落ち
xとyがほぼ等しいときの減算
⇒仮数部の大部分が打ち消し合って zf の相対精度が著しく落ちる
※桁落ち回避の式の変形
分子の有利化
※情報落ち（積み残し）
絶対値の大きな浮動小数点数 xf に絶対値の小さな数 yfを足す
⇒演算結果を浮動小数点数に丸めたものが xf に等しくなる
⇒だんだん小さくなる級数などでは、小さい項から足していくとよい
※誤差の伝播
計算途中の誤差が最終結果に影響を及ぼす
※不安定な算法
誤差が拡大しながら伝播していくような算法
※誤差が伝播が減衰するもの
⇒後退漸化式による計算法⇒最小解を求めるときに有効
◆数値表現
＿◇β進ｎ桁浮動小数点表現
※浮動小数点体系
４パラメタ
基数（底) β
桁数 n
最小指数L
最大指数U
※表現可能な数xf
xf=0 または
xf=±f*β^m
f=x1/β+x2/β^2+…+xn/β^n
ここでxk(k=1..n)は
1≦x1≦β-1,
0≦xk≦β-1(k=2..n)
を満たす整数
mは予め決まっている
L≦m≦Uの整数
fをxfの仮数部 mantissaまたはfraction
mをxfの指数部 exponent
※浮動小数点数の絶対値 Fmax と最小値 Fmin
Fmax = β^U * (1-β^-n)
Fmin = β^(L-1)
◆算法の評価
①収束性 (convergency)
②安定性 (stability)
③精度 (accuracy)
④計算時間
◆方程式の解法
①区間縮小法
方程式 f(x)=0 の解の存在すると思われる区間について f(x)の符号を調べつつ次第に区間の幅を狭めていく方法
２分の１ずつに縮小していく方法→２分法
区間の幅を１０等分していく方法→10等分法
②割線法
解に近い２つの値の勾配から１次式で近似値を求めることを繰り返して解に近ずく方法
③ニュートン・ラプソン法
y=f(x)が微分可能であるとき、f(x)の導関数f'(x)を使って、割線法同様に解に近づく方法
※ベイリー法 ２次近似式を用いて収束を速くする方法
④反復法
方程式 f(x)=0 を変形して x=F(x) とする。f(x)=0 の解すなわち x=F(x) の解αは、xy平面上で直線 y=x と曲線 y=F(x) との交点のx座標として与えられる。
曲線 y=F(x) が y=x と交わっているとき、その近傍の点 x1 に対して x2=F(x1) はより良い近似解となる。これを繰り返し解に近づく。
※F(x)への変形の仕方には複数あることがあり、それぞれに複数の解への接近の仕方が異なる。
◆連立方程式の解法
①掃き出し法（ガウスの消去法）
②ガウスザイデル法
③逆行列
＿◇掃き出し法（ガウスの消去法）
＿◇ガウスザイデル法
[a_11 .. a_1j][x_1] [b_1]
[.. .. ][.. ]=[b_2]
[a_i1 .. a_ij][x_i] [b_3]
とするとき、ガウスザイデル法の漸化式は
x_i(k+1) = (1/a_ii)*{b_i – Σ[j=1:i-1]a_ij*x_j(k+1) – Σ[j=i+1:n]a_ij*x_j(k)}
⇒反復のk番目の近似解から、より精度の良いk+1番目の解を求める式
⇒x1のk+1に対してはx2~はk番目であるが、x2においてはk+1のx1が求まっているのでそれを使う、順次、x3以降はk+1番目のxiが使われる
⇒式そのものは、連立方程式の各行の式を各x_iについて解いた形の式にほかならない
※この式を繰り返し適用すれば、真の解に近づくというのがアルゴリズムのアイディア
＿◇SOR法
＿◇逆行列
◆固有値分解
ＲＦ応用：
MIMO, アダプティブアレーアンテナ、車載レーダ
画像認識応用：
特徴抽出
＿◇CORDIC法
＿◇QR分解
◆多項式近似
①テーラ展開
②ニュートンの補間法
③ラグランジュの補間法
◆常微分方程式の解法
＿◇微分係数の差分近似
部分係数を次のように差分近似する
ｄｙ Ｙｎ＋１ － Ｙｎ
－－＝Ｙｎ’＝－－－－－－－－－
ｄｘ ｈ
ここでＹｎ＋１、Ｙｎはｘが微小値ｈだけ離れた点のｙの値
※オイラー法
Ｙｎ＋１＝Ｙｎ＋ｈ＊Ｙｎ’
⇒Ｙｎ点の微分係数をＹｎと、ｈだけ全身した値Ｙｎ＋１から得るので前進差分という
※常微分方程式の、収束性、安定性、精度は、多くの場合、
きざみ幅 hで決まる
＿◇前進差分、後退差分、中央差分
※前進差分
Y_n’=(Y_n+1 – Y_n)/h
※後退差分
Y_n’=(Y_n – Y_n-1)/h
※中央差分
Y_n’=(Y_n+1 – Y_n-1)/(2*h)
＿◇収束性
もとの微分方程式の正確な解をU
差分近似式の正確な解をu
として、キザミ幅⊿xが０に収束するとき
u→Uになるならば
この差分近似式は収束するという
※差 U-u を離散化誤差(discretization error)という
＿◇安定性
有限な桁数で計算するため、得られた数値解Ｎと、差分近似式の正確な解uの間には
N-u
なる差が存在する
⇒丸め誤差(round-off error)
※一般に丸め誤差の累積効果が無視できるように組み立てられた差分近似式を安定(stable)であるという。
＿◇全誤差
全誤差=U-N=(U-u)+(u-N)
=離散化誤差＋計算誤差
ここで計算誤差＝Σ丸め誤差
＿◇打ち切り誤差と精度
※打ち切り誤差
truncation error
⇒もとの微分方程式と差分近似式との差
⇒差分近似式＝微分方程式中の関数のTaylor展開のある項数以下の切捨て⇒切り捨てたことで生じる誤差
xの関数f(x)
f(x+⊿x)のTaylor展開
f(x+⊿x)=f(x)+f'(x)*⊿x+(f”(s)/2!)*⊿x^2+…
右辺第2項までをとり、以下切り捨てると
f'(x)=({f(x+⊿x)-f(x)}/⊿x)+O(⊿x)
O(⊿x)は⊿xのオーダー
⇒１次のオーダー
※一般に精度をもとめるにはTaylor展開を使う
＿◇常微分方程式の初期値問題
y’=dy/dx=f(x,y)
の解 y=y(x) を初期条件y(x0)=y0のもとで解く
※解が存在することは証明されている
⇒数値的に解くということは、きざみ幅⊿ｘを精度を考慮してきめ、計算区間につき与えられた初期値から出発して、次々にyの値を計算していくこと
＿◇Euler法
オイラー法
はじめのx0について、初期値y0が与えられているとき
y1=y0+f(x0,y0)*⊿x
によりy1を求め
以下
y_n=y_n-1+f(x_n-1,y_n-1)*⊿x
⇒前進差分
⇒精度は一次
＿◇修正オイラー法
y_n+1 = y_n-1 + 2*y_n’*⊿x + O(⊿x^3/3)
⇒中央差分をとる
⇒精度は２次
＿◇Runge-Kutta法
ルンゲクッタ法
①精度が３次の公式
y_n+1 = y_n + (1/6)*(k0+4*k1+k2) + O(h^4)
ここで
k0=h*f(x_n,y_n)
k1=h*f(x_n+h/2, y_n+k0/2)
k2=h*f(x_n+h,y_n+2*k1-k0)
hはキザミ幅⊿x
②精度が４次の公式
y_n+1 = y_n + (1/6)*(k0+2*k1+2*k2+k3) + O(h^5)
k0=h*f(x_n,y_n)
k1=h*f(x_n+h/2, y_n+k0/2)
k2=h*f(x_n+h/2, y_n+k1/2)
k3=h*f(x_n+h,y_n+k2)
＿◇Runge-Kutta-Gill法
＿◇Milne法
◆偏微分方程式の解法
※偏微分方程式の、収束性、安定性、精度は、多くの場合、
時間のきざみ幅⊿tと距離のきざみ幅⊿xの比によって決まる
＿◇ラプラス方程式のガウス・ザイデル法による解法
◆定積分の近似値
①区分求積法
②シンプソン公式
ｘの区間 h 毎にとったX1, X2, X3のときのY1, Y2, Y3をつかって
面積 S = (Y1 + 4*Y2 + Y3) * (h/3)
※積分する関数の区間X1,X3における２次式近似
◆Numerical Recipies
＿◇月齢計算
flmoon 月齢を計算する
n:1900/1/1以来n回目
nph:月相 0=新月 1=上弦 2=満月 3=下弦
そのときのユリウス日をjd と fracに返す。
グリニッジ標準時
julday iyyy/mm/id日の正午から始まるユリウス日を返す。
負は紀元前
※ユリウス日に１を加えて７で割れば曜日が分かる。０＝日曜
caldat ユリウス日を普通の日に戻す。
＿◇ベクトルと配列
※ベクトルと１次元配列
a[j] == *((a)+(j)) これは定義
⇒Ｃの配列は０オリジン
１オフセットのベクトルの方が良い場合⇒１オフセットベクトルへの
読み替え
a[0]はa-1として引数に与えたポインタを使ってptr[1]に見える。
⇒配列範囲を明記すること
※nrutil.c
任意オフセット、任意長のベクトルを確保、開放する関数群
範囲[nl..nh]
float *vector(long nl, long nh)
int *ivector
unsigned char *cvector
unsigned long *lvector
double *dvector
使用例)
float *b;
b = vector(1,7);
記憶域解放
void free_vector(float *v, long nl, long nh)
void free_ivector(float *v, long nl, long nh)
void free_cvector(float *v, long nl, long nh)
void free_lvector(float *v, long nl, long nh)
void free_dvector(float *v, long nl, long nh)
※Ｃの固定寸法の２次元配列は、科学技術計算で多く用いられる
可変サイズの行列には不向き
⇒ポインタの配列へのポインタを使う
例)
float a[13][9], **aa;
int i;
aa=(float **)malloc((unsigned)13*sizeof(float*));
for(i=0; i<=12; i++) aa[i]=a[i];
⇒aaという名前で関数の引数として渡せる
⇒受けとる関数側では float **a;と宣言すれば受け取れる
任意行列の確保開放
float **matrix(long nrl, long nrh, long ncl, long nch)
double **dmatrix(long nrl, long nrh, long ncl, long nch)
int **imatrix(long nrl, long nrh, long ncl, long nch)
void free_matrix(float **m, long url, long nrh, long ncl, long nch)
void free_dmatrix(double **m, long url, long nrh, long ncl, long nch)
void free_imatrix(int **m, long url, long nrh, long ncl, long nch)
例)
a=matrix(1,13,1,9);
…
a[3][5]=…
…+a[2][9]/3.0 …
someroutine(a, …);
…
free_matrix(a,1,13,1,9);
※既存の行列（またはその部分）を参照する新しいポインタの配列の確保設定
float **submatrix(float **a, long oldrl, long oldrh, long oldcl, long oldch, long newrl, long newcl)
例）
既存の行列a[1..13][1..9]をb[0..12][0..8]にする
float **a, **b;
a=matrix(1,13,1,9);
…
b=submatrix(a,1,13,1,9,0,0)
既存の行列の部分a[4..5][2..3]を取り出してb[1..2][1..2]にする
float **a, **b;
a=matrix(1,13,1,9);
…
b=submatrix(a,4,5,2,3,1,1)
⇒submatrixの第１引数に他の型を与え（ただしfloat**にキャストする）、結果を望みの型にキャストしなおせば
他の型にも使える。
void free_submatrix(float **b, long nrl, long nrh, long ncl, long nch)
⇒submatrixで確保した行ポインタ配列を開放する。元の配列は依然として存在するので
データは消えない。
※complex.c
typedef struct FCOMPLEX {float r,i;} fcomplex;
＿◇単精度、倍精度
古いK&R-Cは、float型は演算や関数引数渡し時に常にdouble型に暗黙変換される。
⇒標準Cライブラリは全て倍精度
ANSI-C規格は暗黙の型変換をしない。
＿◇Cにおける整数乗の問題
⇒FORTRANなどと異なり効率よく展開する演算子などがない
#deinfe SQR(a) ((a)*(a))
上のマクロをSQR(sin(x))などと呼び出すとサイン関数を２回呼び出すことになってしまう
static float sqrarg;
#define SQR(a) (sqrarg=(a), sqrarg*sqarg)
上のマクロでは大域変数sqrargの有効範囲が全モジュールに広がってしまう。
また、型によって異なるマクロを必要とする。
＿◇精度と誤差
機械精度(machine accuracy)または機械エプシロン
浮動小数点数1.0に加えたとき１．０と異なるような結果になるような最小の正の浮動小数点数
εm
丸め誤差(roundoff error)
⇒さらに演算では少なくともεmの相対誤差を生じる
⇒正負の誤差がランダムウオークすると、√(N)*εmの丸め誤差累積となる
⇒実際には丸め誤差が同じ方向に累積することがよくあるので(N)*εmとなる
⇒桁落ちが発生すると１回の演算でも大きな誤差が生じる。
εmは仮数部のビットによる
打切り誤差(trancation error)
プログラムやアルゴリズムの特性で、ハードウエアによらない部分
級数の項数など、パラメータが有限であることによる。
＿◇計算の安定性
計算の初期の段階の丸め誤差が次第に拡大され、真の値が飲み込まれてしまうこと。
⇒不安定な計算の例
黄金分割比φのべき乗を漸化式で求めるφ_n+1=φ_n-1 – φ_n
⇒語調３２ビットではn=16あたりで不安定となる
＿◇連立方程式
N個の未知数xjがM個の方程式で関連づけられ、係数と右辺が既知の数であれば、解xjが一意に定まる可能性がある。
※行退化 row degeneracy
M個の方程式のうち１つでも他の方程式の線形結合ならば解は一意に定まらない
※列退化 column degeneracy
どの方程式にも幾つかの変数がまったく同じ線形結合となって現れるならば、解は一意には定まらない
※行退化と列退化は同値条件
⇒退化している方程式は「特異」singular
⇒数値計算の場合、非常に線形従属に近い方程式は丸め誤差により線形従属になる可能性がある
⇒丸め誤差の累積により真の値が飲み込まれることがある。Nが非常に大きいとき。
⇒得られた解を元の方程式に代入すれば分かる
☆線形計画法など
◎線形計画法
◎シンプレックス法
simplex method
線形計画法を解くアルゴリズム。実行可能解（超多面体の頂点）の一つから出発して目的関数の値をなるべく大きくするようなところに移動させていく動作を繰り返して最適解を見つけ出す。
◎分枝限定法
BB branch and bound method
離散最適化と組み合わせ最適化の最適解を求める。
①集合Ｓを、小さい複数の集合に分割する（小さい集合の和集合がＳとなる） branching
②小さい部分集合の最小値の上限と下限を計算する bounding
③あるノード（候補集合）Ａの下限が別のノードＢの上限より大きければ、Ａは探索するまでもなく捨てる pruning
④再帰は候補集合Ｓが一つの元になったときか、Ｓの上限が下限と一致した場合に停止
◎PSLQ
ｎ次元実ベクトルｘに対し、ｘとの標準内積をとると０になるｎ次元非零整数ベクトルmをxのinteger relationという。このinteger relationを発見するアルゴリズム。
http://mathworld.wolfram.com/PSLQAlgorithm.html
◎動的計画法
DP(Dynamic Programming)
◆最適性の原理
最適経路中の部分経路もまた最適経路になっている
決定の全系列にわたって最適化を行うためには，初期の状態と最初の決定がどんなものであっても，残りの決定は最初の決定から生じた状態に関して最適な政策を構成していなければならない
現段階の最適戦略が過去に遡ることなしに、直前の段階の最適結果だけから決まる
◎ビタビアルゴリズム
viterbi
DP(Dynamic Programming)の延長にある
①送信シンボル系列を有限長とする
②既知チャネル歪を用いて、可能なすべてのシンボル系列の受信信号レプリカを作る
③実際の受信信号とすべてのレプリカの自乗誤差を計算し、最小を与えたシンボル系列を判定する
→組み合わせ爆発をおさえ、演算量をシンボル長に比例するように工夫した
◆最尤系列推定
MLSE: Maximum Likelihood Sequence Estimation
☆確率過程
◆マルコフモデル
＿◇マルコフ過程
Malkov Process
ある記号の出現確率が、直前のｍ個の記号によって決定されるような確率過程
⇒未来の挙動が現在の値だけで決定され、過去の挙動とは無関係。
⇒過去によらない微分方程式によって記述される微分方程式に従う物理現象に確率論的解析をする場合にも現れる。
※単純マルコフ過程
m=1の場合
◆隠れマルコフモデル
内部状態はマルコフ過程に従って遷移する
確率モデルは、内部状態と各状態における記号の出現確率分布から構成される
⇒外部からは記号の系列だけが観測でき、内部の状態遷移は直接観測できない
☆進化論的アルゴリズム
◎GA
genetic algorithm
◎GP
genetic programming
遺伝的プログラミング
遺伝子を木構造で表現する
◎進化的プログラミング
◎進化的戦略
◎EA
evolutionary algorithm
進化的アルゴリズム
自然淘汰の概念導入
☆乱数
乱数（列）というのは、確率変数の具現値の系列のことである。
※一様乱数というのは、考えている範囲のあらゆる値を等確率でとる確率変数の具現値の系列である。
◎線形合同法
Linear congruential method
(Lehmerにより提案された）
◆算法の概要
次の漸化式を用いて非負整数列を生成する
Xn = a * Xn-1 + c (mod m)
a: 乗数、正整数
m: 法(modulus)、正整数
c: 加数、非負整数
※区間[0,1)上の実数が必要なときは、計算機の実数型演算により、
xn = Xn / m
を計算して用いる。
※Xnのとりうる値は、0,1,…,m-1のいずれかであり、XnはXn-1だけから決まるので、数列{Xn}は周期列となり、周期はm以下である。
※周期を長くするため、ｍとして計算機の１語のビット数をeとすれば、
2^e
2^(e-1)
あるいは上記を超えない最大の素数
などを使う。
※a, cは数列{Xn}がなるべく長い周期で、ランダムになるように選ぶ
◆線形合同法に関する定理
＿◇定理１－１
線形合同法が最長周期mを持つための必要十分条件は、次の３条件がすべて満たされることである
①cとmが互いに素である
②a-1がmのすべての素因数で割り切れる
③mが4の倍数ならば、a-1も4の倍数である
＿◇定理１－２
c=0である乗算型合同法に関する定理。定理１－１の①が成り立たないので最長周期は達成できない
①m=2^e(e≧4)の場合、最長周期はm/4であり、これを達成できるのは a (mod 8) = 3 または 5 で、X0=奇数のときに限られる。
②mが2より大きい素数pの場合、最長周期はp-1であり、これを達成できるのは、X0≠0で、かつp-1の任意の素因数qに対してa^((p-1)/q)≠1(mod p)が成り立つ場合に限られる
※このときaはpの原子根(primitive root)であるという
＿◇合同法RANDU
規則的な数列になってしまう例
m=2^31, a=65539(2^31+3), c≠0
※このとき、
Xn+2 – 6*Xn+1 + 9*Xn =
{(2^16+3)^2 – 6*(2^16+3) +9}*Xn
= 0 (mod m)
となり、３次元単位立方体内に点列{(Xn, Xn+1, Xn+2)}をプロットすると、１５枚の平行で等間隔な平面9x-6y+x=k (k=-5,…,9)にのってしまう。
＿◇合同法乱数列の多次元疎結晶構造
ｓ次元空間に点列をプロットすると、それらはたかだか
(s!m)^(1/s)枚
の平行で等間隔に並んだｓ－１次元超平面の上にのる
※超平面の枚数の上界
ｍが小さいほど、ｓが大きいほど上界が小さい
m=2^16 s=3 73
s=10 13
m=2^32 s=3 2953
s=10 41
＿◇乗算型合同法
加数c=0の場合
＿◇混合型合同法
加数c≠0の場合
◆スペクトル検定
超平面の間隔(1/νs )を計算する
νs=min{√(u1^2+…+us^2)
|u=(u1,…,u2)は非零整数ベクトル,
u1+a*u2+…+a^(s-1)*us=0 (mod m’)}
ここでm’は、{Xn}の周期がmまたはm-1の場合には、m’=mとし、a=5 (mod 8)の場合にはm’=m/4とする。
νsを計算することにより乗数aの良さを判定する
νs : 合同法乱数数列のS次元精度
この精度を持つ数列によって生成されるｓ次元点列は、その座標成分を上位log2(νs）ビットまでの分解能でみれば、ほぼ一様に分布しているものとみなすことができる。
＿◇比較的成績のよい乗数
a c m log2(νs )
1664525 0 2^32 14.1
1664525 * 2^32 16.1
1566083941 0 2^32 14.8
1566083941 * 2^32 16.1
16807 0 2^31-1 14.0
314159269 0 2^31-1 15.2
630360016 0 2^31-1 15.3
950706376 0 2^31-1 15.4
*:任意の奇数
＿◇限界
周期がＮの数列のｓ次元精度に関しては、パラメタをどのように選んでも、次の限界を超えられない
log2(νs)≦(log2(N)/s)+Cs
ここで、Cs(2≦s≦8)は0.1~0.5程度の定数
※所望の精度を得るための周期Ｎ（法ｍ）をどの程度異常にする必要があるか概算できる。
◎Ｍ系列
◆Ｍ系列の定義
maximum length linearly recurring sequence
0と1からなる周期列a0,a1,…
シフトレジスタ(shift register)系列とも呼ばれる
次の形の漸化式で生成される
a_n = c1*a_n-1 + c2*a_n-2 +…+ cp*a_n-p (mod 2)
ここで
ci(1≦i≦p-1)は0または1で、cp=1である。
初期値a0,a1,…,a_p-1
※特に周期が 2^p – 1 に等しい場合にp次の最大周期系列あるいはＭ系列と呼ぶ
※Ｍ系列になるための必要十分条件
特性多項式
f(x)=1+c1*x+c2*x^2+…+cp*x^p
がGalois体GF(2)上の原始多項式となること
◆原始３項式
発生速度が速いので３項式が使われる。
f(x)=1+x^q+x^p (q<p)
※周期2^p-1が素数となるもの
p q
89 38
127 1, 7, 15, 30, 63
521 32, 48, 158, 168
607 105, 147, 273
1279 216, 418
2281 715, 915, 1029
3217 67, 576
4423 271, 369, 370, 649, 1393, 1419, 2098
9689 84, 471, 1836, 2444, 4187
◆Ｍ系列の性質
p次のＭ系列 {a_n} は次の性質を持つ
(P1) {a_n}の周期はN=2^p-1である
(P2) p次元ベクトル系列{(a_n, a_n+1,…,a_n+p-1)}の一周期分には、零ベクトル以外のあらゆるベクトルがちょうど１回ずつ現れる
(P3) {a_n}の１周期分中の１の個数は2^(p-1)個、0の個数は2^(p-1)-1個である。また１周期中にあらわれる長さｋ(1≦k≦p-2)の１の連（１がｋ個続き、その両側が0ではさまれた部分）および0の連はいずれも2^(p-k-2)個である。
(P4)
(P5)
(P6)
(P7)
◎一様分布以外の乱数
一様分布以外の分布に従う乱数
⇒多くは、一様乱数に何らかの変換を施して得る
◆乱数の変換
U, U1, U2 … 区間[0,1)上の互いい独立な一様乱数
発生させたい乱数をX
その分布関数をF(x)
連続分布ならば密度関数をf(x)
＿◇逆関数法
F(x)の逆関数 F^-1(y) = min{x:F(x)≧y}, 0≦y≦1
を用いて
X = F^-1(U)
※正規分布の場合には、逆関数が解析的に求められないので、近似式を使う
※指数分布へ適用することができる
＿◇採択－棄却法
acceptance-rejection method
※高速化のために「えぐり出し」(squieeze)技法が用いられることがある。
＿◇合成法
composition method
＿◇一様乱数の比を用いる方法
＿◇別名法
alias method
◆正規分布
＿◇ボックス＝ミュラー法
Box-Muller’s method
一様分布に従う確率変数から標準ガウス分布に従う確率変数を生成する方法
⇒ガウス分布に従う疑似乱数の生成
＿◇多次元正規分布
※Cholesky分解
◆幾何分布
※幾何分布は指数分布を離散化したものとみなすことができる
◆Poisson分布
☆エラー検出／訂正
◎誤り検出符号
error detecting code
☆確率的シミュレーション
◎モンテカルロ法
Monte Carlo
大数の法則に基づいて、乱数を用いて実験を何度も繰り返し、その結果得られる測定値の平均値で真の数を推定しようとする方法
※単純モンテカルロ法による推定量A(N)の持つ誤差の標準偏差は
c/√N
※N→∞のときA(N)は、ほとんど確実にθに収束するが、収束は遅い
◆分散減少法
c/√Nの c を小さくするための方法
⇒解こうとする個々の問題について、サンプリングの方法を単純なランダムサンプリングからもっと効率的なものに変えるもの
⇒統計の活用
⇒予備サンプリング⇒本格サンプリング
＿◇加重サンプリング
importance sampling
※一様にサンプルをとるのでなく、重要と考えられる領域からより多くのサンプルをとる。
※Cauchy-Schwarzの方程式
＿◇層別サンプリング
stratified sampling
※複数の小区間に分割し、各小区間からあらかじめ定めた個数のサンプルをとる
※Lagrangeの未定係数法
＿◇制御変量と負相関変量
※制御変量 control variate
θの不偏推定量Ｙに対して、これと相関があって平均値ζが分かっている確率変数Ｚがあれば、これをＹに対する制御変量と呼ぶ
※負相関変量 antithetic variate
Ｙと期待値が同じで負の相関を持つ変量Ｚ
◆準モンテカルロ法
周期内で、２度と同じ乱数が現れない擬似乱数系列
⇒ランダムな点列としては望ましくない
⇒多重積分の近似値の評価としては同じ点を評価してもしょうがないので、全ての点が異なるのは好ましい
※多重積分の近似値を求めるために積分領域内になるべく一様に分布する点列を標本点として使う方法
＿◇差異の小さい点列を用いる方法
low-discrepancy sequence
＿◇優良格子点法
good lattice points method
☆データベースおよび情報検索システム
◎集合論
集合：１つ以上の同じ属性を持つ要素の集まり
◆集合と要素の関係
集合Sに要素sが含まれる
S∋s
集合Sに要素sが含まれない
S∋/s
要素がまったくない集合＝空集合S*
S*=φもしくは{}
ある集合のすべての要素を含んだもの＝全体集合U
（普遍集合）
集合X以外の集合Uの要素で構成されている集合＝Xの補集合 X^C
集合Xのすべての要素が集合Yに含まれている場合
⇒集合Xは集合Yの部分集合
X⊆Y
集合Xのすべての要素が集合Yに含まれていて、集合Xに含まれない要素が少なくとも一つ存在する場合
⇒集合Xは集合Yの真部分集合
X⊂Y
◆集合演算
集合演算：集合をもとにした演算
①積演算
X1∩X2 = {x | x∈X1 ∧ x∈X2}
②和演算
X1∪X2 = {x | x∈X1 ∨ x∈X2}
③差演算
X1－X2 = {x | x∈X1 ∧ x∈/X2}
⇒X2⊂X1において、X1-X2をX1におけるX2の補集合と呼ぶ
◆集合における直積演算
直積：各集合がもつ要素同士のすべての組み合わせを並べたもの
⇒要素同士の組み合わせを関係の組という
⇒組の個数を次数という
⇒次数ｎ個のものをｎ項リレーションとよぶ
⇒個々の要素は関係の属性と呼ぶ
⇒２次元的にあらわしたものをリレーション・テーブル（関係表）
横が組、縦が属性
※リレーション・テーブルをデータベースのスキーマモデルとして採用したもの
⇒リレーショナル・データベース
◆関係演算
リレーショナルデータベース特有の演算
①射影演算
該当する属性のみを取り出す。（テーブルの縦方向切り出し）
②選択演算
属性がある条件を満たす組だけを取り出す。（横方向）
③結合演算
関係表同士について、共通する属性において値が一致する組同士を取り出して結合し、新たな組を生成する操作
④商演算
関係表同士について、共通する属性の値を持つものだけを抽出する
※上記の関係演算と、集合演算をあわせたものを関係代数と呼ぶ
演算相互の等価性により、
和
差
直積
射影
選択
の５演算で構成できる
◎関係代数論
◎データモデル
◎データベーススキーマ
◎ＲＤＢ
◎ＳＱＬ
◆SQLと関係代数
☆人口知能、ロボティクス
◎述語論理
◎知識表現
◎知識モデル
◎Prolog
◎エキスパートシステム
☆画像認識
◆SIFT
◆CARD
デンソーアイティーラボラトリ
SIFTの1/10の計算量
ＬＵＴを使って主方向にあわせた分割パターンを選択
マッチングにはユークリッド距離ではなく、ハミング距離をつかう
☆ニューロ、機械学習
◎基礎
機械学習の作業に」おいて最も大切なことは、データを理解しデータを扱いやすい形に成形すること
正しい評価を行うために訓練データとテストデータを区別すること
◆機械学習の典型的な作業の流れ
①データの読み込み、データの整形
②入力データの調査と解釈
③学習アルゴリズムにどのような形でデータを入力するのがよいか分析
④正しいモデルと学習アルゴリズムの選択
⑤結果に対する評価
※特徴エンジニアリング
feature engineering
⇒機械学習のワークフローにおいてデータを改良する行為
◆訓練データとテストデータ
※ホールドアウトデータ
例えば全データの数%をとりわけておく
⇒残りのデータをで学習を行う
⇒ホールドアウトデータで用いて誤差を計算する
※テストデータは訓練データに含めない
◆機械学習と統計学
機械学習＝論理命題の自動的な産出
※統計学で古くから知られていた層別が機械学習にとって本質的に重要
※層別
stratification
下位集団の統計的な性質は、全体集団のそれとは異なっていることが珍しくない
◆機械学習と80年代型エキスパートシステム
※80年代型エキスパートシステム
完成された知識をLISPやProlog等の記号処理言語でプログラマー自身が表現する
⇒決定論的命題
⇒表現する知識が不明確ならお手上げ
データ爆発⇒そもそも表現すべき知識がなんであるかわからない
⇒自力で知識を獲得するアルゴリズム⇒機械学習(machine learning)
※機械学習の技術的本質
⇒多段層別⇒決定論的命題ではない⇒統計的な相関関係
◎ディープラーニング
ニューラルネットワークのうち
入力層―隠れ層―出力層
⇒隠れ層が多層なものをディープラーニングと分類する
※ニューラルネットワークにおける学習
出力が所望の結果に近づくように各入力にかける重みの値を逐次的に更新すること
◆表現学習
representation learning
特徴量の形式を人間がヒューリスティックに設計するのではなく、学習によって自動的に導き出そうというアプローチ
◆主要分類
※主に教師あり学習の適用
①CNN (convolutional nerual network)
画像認識、自然言語処理など向け
一方方向
入力層の後、
畳みこみ層
局所的なフィルタ処理
プーリング層
平均化／最大値取得などの間引き処理
を交互に繰り返す。繰り返すことで抽象的な特徴を得る
最大で２０～３０層
出力層
最後のプーリング層の後、全結合
分類クラスと同数の出力ユニットを置く
②RNN (recurrent neural network)
自然言語処理、音声認識での言語モデル
アルゴリズムの自己獲得、ロボット行動生成
前の時刻の隠れ層の状態を隠れ層にフィードバックする
内部状態を持つことで、時系列データの扱いにも向く
３層中心
③フィードフォーワード型ニューラルネットワーク
音声認識での音素推定に向く
（音声認識分野では単にDNNと呼ばれる）
入力層には音声特徴量ベクトルを入力
層間は全結合
出力層は音素を出力
６～９層
※主に教師無し学習を適用（あるは教師あり学習の事前学習）
④オートエンコーダー(AE: autoencoder)
画像認識、雑音除去、次元削減
入力データを再現するような低次元の特徴ベクトルを獲得
入力データ自身を教師信号として学習
入力層と隠れ層の前半がエンコーダー部
隠れ層の後半と出力層がデコーダー部
出力層の出力に対して入力データを教師信号として学習させる
⇒学習後デコーダー部を取り除く
⇒入力を復元できるような圧縮した情報表現が現れる
⑤ボルツマンマシン（マルコフ確率場）
画像認識、音声認識
入力層と隠れ層の結合は双方向
層同士の関係を確率モデルで記述
⇒入力データをうまく再現するように学習
＿◇教師あり学習と教師なし学習
教師あり学習
supervised learning
入出力の明示的な対応関係（関数）を学習
教師データ（ラベル）が必要だが汎用
教師なし学習
近いデータ同士をクラスタリング
抽象的な特徴を抽出（次元削減）
ラベル不要。データの傾向を見ながら自動分類
⇒各集合に言語情報を結びつけるには教師あり学習を組み合わせる必要あり
◆誤差逆伝播法
back propagation
現在の出力と正解値との差＝誤差をとる
⇒重みで偏微分して更新⇒誤差は前の層に順次伝える
◆活性化関数
①シグモイド関数
出力範囲０～１
②tanh関数
出力範囲‐１～１
③softmax関数
全ニューロン出力の合計値で正規化、確率として解釈できる値を出力
④ReLU (rectified linear unit)
非正規領域で出力０
生領域で入力をそのまま出力とする
⇒深い層でも誤差が消失しにくい
◆ディープラーニング・フレームワーク
①Caffe
②Theano/Pylearn2
③Torch7
④cuda-convnet2
⑤cuDNN
⑥H20
⑦DL4J
◆データオーグメンテーション
画像の見え方の変動を増やし、頑健性を高めるために、元の訓練データの画像に対して加工を加えてデータ数を増加させる
◆CNN
convolutional neural network
＿◇畳み込み層
フィルタの内容を学習によって決める
＿◇プーリング層
一定領域内の最大値をとるなどして解像度を落とす
＿◇フル結合層
特徴抽出後はフル結合層で実施、教師データと比較する
＿◇ReLU
rectified linear unit
◆音声認識へのニューラルネットワークの応用
音声認識の段階
連続的な音声信号を周波数解析（FFT）
特徴量に変換
対数メルフィルターバンク
メル周波数ケプストラム（MFCC)
特徴量から音素を推定＜＝DNNが使われる部分
音素列に発話辞書をあてはめて単語変換
単語間の組み合わせ出現確率である言語モデルで推定
※オープンソースフレームワーク
Kaldi
※N-gram
言語モデル
直前の数単語の組み合わせの生起確率
◆自然言語処理へのニューラルネットワークの応用
※one-hot表現
ベクトルの一要素に１単語。語彙語数の次元を持つ０１ベクタ
※bag-of-words
各要素が単語の登場頻度を表すようにする
※分散表現(distributed representation)
語彙数によらず数百程度の低次元
１単語の情報をベクトルの要素として全体に拡散
⇒ニューラルネットで分散表現を得る
※オープンソースソフト
word2vec
◆SOM
self organizing map
◆RNN
recurrent neural network
原理的にはチューリング完全
＿◇LSTM
long short-term memory
ゲート付きRNN
◎問題別
◆クラス分類
classification
◎サンプルデータセット
計測されたデータ⇒特徴量(features)
◆UCI機械学習データセット・レポジトリ
University of California at Irvine
http://archive.ics.uci.edu/ml/
◆アイリスデータセット
1930年代
統計分類の分野の近代的サンプルデータの初期のもの
３品種のアイリスについての花の品種でラベル付けされたデータ
サイズ小さい（１５０）
Sepal length
Sepal width
Petal length
Petal width
を計測
☆マンマシン間インタフェース
◎認知科学
◎パターン認識
☆概念、用語
☆アルゴリズムとデータ構造
◎グラフ理論
◎計算量理論
◎検証理論
◎フローチャート
◎構造化チャート
☆数値、記号計算
◎数値解析
◎線形計算
◆数値計算
＿◇桁落ち
計算結果の有効数字の桁数よりも、得られた結果の有効数字の桁数が少なくなること。
※おおきさの小さい２つの数を引き算すると桁落ちが生じる。例）２次方程式の根の公式
4acがb^2にくらべて非常に小さい場合はけた落ちの危険がある。
◆シリアライズ
１リソースの利用の調整、一つの主体だけが利用できるようにする（逐次化）
（マルチスレッドプログラミングにおける）⇒排他制御
２オブジェクトをバイト列やＸＭＬに変換すること（直列化）＜＞デシリアライズ（直列化復元）
⇒オブジェクトを直列化してファイルなどの永続記憶に保存すること（永続化）
◆スレッドセーフ
複数のスレッドから呼び出してもよいように設計されていること
☆問題
◆算術
＿◇バベッジの問題
その数の平方が269696で終わる最小の値を求めよ
バベッジの解 99736（階差計算を繰り返した得た）
クラインの解 25264 (暗算で３分で解いたといわれる）
＿◇アッカーマン関数
非負の整数 m と n に対し
{n+1, if m=0
Ack(m,n)= {Ack(m-1,1), if n=0
{Ack(m-1,Ack(m,n-1)), otherwise