☆お言葉
「著作権で保護された出典の出版されたプログラムに本書のプログラムが『基づく』というとき、アイデアが同じであることを意味する。アイデアのソースコードとしての表現は著者たち自身のものである」
－－－Press他
「本書のプログラムにバグ（誤り）がないと言い張るつもりは毛頭ない。」
－－－Press他
「コンピュータプログラムと、紙に書いた詩や楽譜とは、ある意味で非常に似ている。～中略～つまり、視覚的な、２次元の、時間を凍結した形で表現されるが、それらが伝達しようとするものは、時間的に展開する一つの過程である。」
－－－Press他
「構造化プログラミングの目的は、プログラムの制御構造を人間の目にわかりやすくすることである。」
－－－Press他
「モーツアルトの創造性がソナタ形式で阻害されたり、シェークスピアの創造性がソネットの韻律規則で阻害されるなら、プログラマの想像性も阻害されるであろう。」
－－－Press他
「これはgotoが危険だからではなく、危険なのはむしろラベルである。」
－－－Press他
「中括弧が不要な場合でも、入れた方が意図がはっきりし、プログラムが改善される。」
－－－Press他
「計算理学の問題は計算だけではないのである」
－－－江沢洋
☆一般
◎並列性
◆データ並列性
◆命令並列性
◆スレッド並列性
☆計算理学
計算物理
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:温度
※実験において測定されるある物理量Ａの値は、平衡状態でのＡの重みつき平均
<A>=Σ[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概念
◎Google
◆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)と呼ばれる実行イメージをインスタンス化することで仮想マシンを起動する
☆Graphics
◎Graphics基礎
◆色の三原色
＿◇光の三原色
赤
青
緑
赤と緑をまぜると黄色
緑と青をまぜるとシアン
青と赤をまぜるとマゼンタ
赤、緑、青をまぜると白となる
＿◇印刷の三原色
シアン(Cyan) 青緑 （赤い光を吸収）
マゼンタ(Magenta) 赤紫 （緑の光を吸収）
イエロー(Yellow) 黄色 （青の光を吸収）
例）シアンとマゼンタをまぜると、赤と緑が吸収され青のみ反射される
※混ぜ合わせると全ての色を吸収するはずだが、完全な黒にするのは難しいので、通常は、黒インクを併用する
◆色空間と表色系
※色空間
各色の成分の濃度を軸にとった空間で、色はその空間内の点として示される。
※表色系
＿◇マンセル表色系
色相(hue) 色の種類
明度(brightness) 明るさ
彩度(chromaticness) 鮮やかさ
※HSV方式
※HSL方式
◎ＣＧ
◆曲線
＿◇スプライン曲線
spline curve
指定した点を通るなめらかな曲線
＿◇ベジェ曲線
Bezier curve
※ルノーの車のデザイナーであったベジェが考案した。
アンカーポイントの両側に方向ポイントがあり、これを動かすことで曲線の形を変えることができる
◆塗りつぶし
＿◇tint paint
ブラシの色と背景の色を混ぜ合わせる。
水性絵具の重ね塗り風
＿◇value paint
ブラシで描いた部分の明るさを変化させる。
◆アンチエイリアシング
ジャギー(Jaggy)を目立たなくする処理
◆補正
＿◇トーンカーブ
明るさの補正に使う
◆フィルタ
＿◇フィルタ行列
＿◇シャープ化
となりあう画素の濃度値を引き算⇒輪郭での変化を大きくする
0 -1 0
-1 5 -1
0 -1 0
＿◇エッジ抽出
1 0
0 -1
＿◇エンボス
エッジ抽出した画像に適当な値を加えて明るくする
◎３Ｄ描画
◆モデリングとレンダリング
※モデリング
立体のデータをつくる
※レンダリング
画面上に表示する
＿◇ワイヤフレームモデル
wireframe model
頂点の座標と、頂点と頂点を結ぶ線のデータから立体の骨組みのみを定義する。
⇒面についての情報なし
＿◇サーフェスモデル
surface model
頂点と、線のデータに加え、線からくみたてられる面の情報が定義される。
⇒物体の内部を示す情報はない
※ポリゴン
立体を表現するために使われるひとつひとつの多角形
⇒通常３角形のポリゴンが使われる（３頂点からはかならず平面が定義されるので）
※曲面表現
Bスプライン曲面
ベジェ曲面
NURBS曲面
⇒複数の曲面（パッチ）
＿◇ソリッドモデル
solid model
中身が詰まったモデル。球、立方体などの基本図形（プリミティブ）を組み合わせ、それらの間の論理演算で複雑な図形を定義する
⇒ＣＳＧ表現
Constructive Solid Geometry representation
＿◇立体モデルの生成：回転とスイープ
※回転
断面形状から立体化
※スイープ
２次元形状を直線や曲線にそってスイープ
※ポイントスイープ
スイープしながら大きさを変え、１点に集中させる
※ベベル
立体のカドの部分に丸みを持たせる処理
＿◇立体モデルの生成：メタボール
meta-ball
※クーロン力の考え方で複数の点においた電荷から電位が等しくなる点を物体の面として考える。
＿◇隠線消去、隠面消去
※Zソート法
ポリゴンを奥行方向の順にならべて奥から描いてゆく
⇒簡単だが、複雑な形状ではソートできずにうまく描けないこともある
※Zバッファ法
画素毎に奥行の判断をする
⇒ビデオゲーム向き
※スキャンライン法
走査線にそったスキャンライン面毎に奥行を調べる
⇒画素毎のZバッファでできない、アンチエイリアシング処理などが可能
⇒ガラスのような透明物体の表現にも向く
＿◇シェーディングとシャドウイング
※陰 (shade)
物体表面で、面の向きと光の方向とにより、面の明るさが変化して暗くなる部分
※影 (shadow)
物体が光をさえぎって、他の物体上に光が当たらない部分
※フラットシェーディング
ポリゴンは平面なのでポリゴンの中のシェーディングは一定
※スムーズシェーディング
ポリゴンは平面だが、ポリゴンの中でシェーディングを変化させ、あたかも曲面のように見せる
⇒グーローシェーディング
ポリゴン内部の明るさは、各頂点からの距離から計算する
演算簡単だが、ハイライト表現には向かない
⇒フォンシェーディング
ポリゴンの頂点毎の法線方向から、内部の法線の方向を補間してもとめる
＿◇拡散反射と鏡面反射
※拡散反射
ディヒューズ
表面がざらざらしたものの反射
※鏡面反射
スペキュラ
⇒物体の表面の一部にハイライトを生じる
＿◇環境光と屈折
※環境光
⇒間接光、アンビエント
＿◇光源
平行光源
点光源
スポット光源
⇒点光源にカサをつけたもの
◆投影方法、視点
＿◇透視投影
ビューウインドウ（投影面）の手前にある視点から投影面の後ろにある図形を透視してみる
＿◇平行投影
平行な交戦で図形を投影面に映し出す。ＣＡＤなどで使われる
＿◇視点
※視角
ビューウィンドウの対角の２点のなす角
※ビューボリューム
視点を頂点とし、視角のなかに含まれる４角錐
⇒ビューボリュームに含まれない部分を切り取る処理＝クリッピング
⇒処理面をクリッピング面
※焦点距離
視点からビューウィンドウまでの距離
⇒焦点距離が小さいと視野角が大きくなる⇒相対的に物体は小さく見える
⇒焦点距離が大きいと視野角は小さくなる⇒狭い範囲が映し出されるので大きく見える
◆座標系
親指＝X
人差し指＝Y
中指＝Z
Zが奥行方向
＿◇右手系と左手系
※右手系
CADなどで主として使われる
※左手系
３ＤＣＧは通常こちら
＿◇ワールド座標とローカル座標
ワールド座標だけだと物体の回転、変形の計算が面倒なので、それぞれの立体毎にローカル座標を定義することが多い
◆フラクタル
◆ジオメトリ
アプリケーション内で定義した空間上の立体モデルの座標をスクリーン座標に変換するための演算処理
◆表面処理
＿◇テクスチャ
モデルの表面に紙や金属、木、砂といった質感を与えるための処理
２次元の写真や模様などの画像を３次元物体の表面に張り付ける
※テクスチャマッピング
※ソリッドテクスチャ
２Ｄでなく３Ｄのテクスチャを用意し、切断面を見せる
＿◇バンプマッピング
実際の物体表面をデコボコにさせるのは大変なので、シェーディングを計算するときの面の向きをマッピングにより変化させ、表面にデコボコがあるように見せる
⇒あまり大きな凹凸表現はできない
＿◇環境マッピング
※リフレクション
reflection
周囲の映像を物体外部の仮想円筒などにマッピングし、物体表面の色をそこから決める
反射
※リフラクション
refraction
屈折
リフレクションどうような方法で、屈折効果を狙う
◆レイトレーシング
＿◇レイトレーシング
＿◇ラジオシティ
◆ボリュームレンダリング
※ボクセル
voxel
◎画像処理
◆ビデオコーデック
符号化、復号化
ブロック単位で、動きベクトル探索、DCT、量子化など
※スレッド並列性
◆ISP
Image Signal Processing
光学系の補正や、センサの傷補正、画素単位の処理が中心
※データ並列性
◆超解像度処理
フレーム内での超解像度処理
フレーム間での超解像度処理
＿◇フレーム内での超解像度処理
１フレーム内の入力信号から高解像度画像を推測（主として輝度信号）
※フレーム間より軽いが、画素に誤りがでる可能性がある。
※入力のサンプリングポイントの間の画素の補間
⇒単純な線形フィルタ⇒波形滑らか⇒メリハリなし
⇒前後だけでなく他の走査線などの情報も加味して推定
※適用領域の限定
全画面に一律適用⇒遠近感がなくなり平面的画像となる
①テクスチャ、エッジ、平坦の３領域分割
⇒テクスチャ（輝度信号が細かく変化している領域）にのみ超解像度を適用
②遠近解析⇒前面映像にのみ適用。拝啓には適用しない。
※再構成法
アップコンバートした画像をダウンコンバートしたものと
元画像の差分をとり、アップコンバートした画像に補正処理をかける方式
＿◇フレーム間での超解像度処理
複数フレームを処理
※１枚１枚の解像度が低くても、フレーム間で画素がずれていれば解像度を高められる
⇒対象物が写る画素がフレーム間でずれなければならない
（対象物の位置情報、移動量の推定が必要）
特定対象物の画素位置あわせ⇒入力映像以上のサンプリングポイント
※メモリ量、処理量がおおくなるが、雑音除去でき、原理的にも高精度
◆画像認識
特徴抽出（データ並列度高い）
識別、統計量計算（短いデータ並列＋スレッド並列）
推論、判断
☆SuperComputing
☆OpenCL
Open Common Language
ヘテロジニアスコンピューティング環境
GPUが念頭にある
ロイヤリティフリー
クロノスグループが標準化
（⇒OpenGLも同様。OpenGLとの連携も考慮されている）
◆４つのモデル
＿◇プラットフォームモデル
＿◇実行モデル
＿◇メモリモデル
＿◇プログラミングモデル
☆Tips
◆古いC言語処理系の互換性
＿◇VAX C
malloc(), free()
ヘッダファイル無し
※ANSI-C stdlib.h
＿◇Microsoft C（旧）
malloc(), free()
malloc.h
※ANSI-C stdlib.h
☆Algorithm
曖昧性なく定義された基本操作の有限系列として記述される。
※必ずしも有限停止が保証されていない場合
⇒手続き(procedure)
※有限停止が保証されている場合
⇒アルゴリズム
アルゴリズムは対象とする問題(problem)を解くという目的で書かれる。
⇒一つの問題は、通常、無限個の問題例(problem instance)からなる
⇒問題例は問題の記述に含まれるパラメタの値を具体化することで定義される。
⇒アルゴリズムは入力されるどのような問題例に対しても有限ステップで正しい解を求めて停止するものでなければならない。
※答えがあるかないかわからない／いつ結果が出るかわからない問題
⇒答えではなく最良の解／近似解を求める
☆基本
◎基本モデル
◆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
☆最適化問題
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が非常に大きいとき。
⇒得られた解を元の方程式に代入すれば分かる
☆浮動小数点演算
http://754r.ucbtest.org/
浮動小数点の危険
http://www.lahey.com/float.htm
◎DEC, HP, IBM
◆DEC VAX (D Format)
①
radix: 2
number of digits:24
Emin:-128
Emax:126
max.value:1.7…e38
②
radix: 2
number of digits:56
Emin:-128
Emax:126
max.value:1.7…e38
◆HP 28, 48G
radix:10
number of digits:12
Emin:-500
Emax:498
max.value:9.9…e498
◆IBM 370 and 390
IBM Hex浮動小数点形式
※指数が４ビット単位なので、頭に０がつまることがあり、有効ビット数は３ビット範囲で変動する
①単精度
符号１ビット、指数７ビット、Fraction２４ビット
最上位ビットの左に小数点があり、整数部は０とみなす。
指数部の底は16．EXPは64が０のバイアス表現
radix:16
number of digits:6(24bits)
Emin:-65
Emax:62
max.value:7.2…e75
②倍精度
radix:16
number of digits:14(56bits)
Emin:-65
Emax:62
max.value:7.2…e75
◆CRAY-1
倍精度
符号１ビット、指数１５ビット（バイアスは１６３８４）、２を底とする
Ｆｒａｃｔｉｏｎ４８ビット、最上位ビットの左に「０．」があるものとする。
※非常に広い範囲の指数を扱うことができるが、データの有効ビット数は少ない。
◎IEEE形式浮動小数点数
※元はインテル８０８７であり、バークレーのカーン、クーネン、ストーンの３名で起案されたのでＫＣＳと呼ばれた。
※ＤＥＣはＫＣＳに反対し、ＶＡＸフォーマットを押した。
※２進表現の場合、正確に０．１は表現できない
⇒実際に格納されている値は２進法小数による最近傍代表値である
⇒１０進法の異なる数で２進の最近似値が同じものは数多く存在する
⇒もっとも短い表現を選ぶのが人間にとっては分かり易い
◆IEEE Std 754-1985
David Stevenson(Zilog)が議長
＿◇特徴
①指数部は２を底。
②正規化された数値の最上位ビットは必ず１となるので、これをヒドンビットと称して省略し、１ビットを稼いでいる
③指数部は単精度では１２７の下駄はかせ表現
④指数部が０の場合はデノーマル(Denormal)数を表す
⑤最少と最大の指数は特別なデータを表す
※ゼロの表現
EXP, Fractionがオール０
符号は０と１があり得るので、＋０、－０の表現がある
⇒通常は区別する必要ないが、符号を取り出す演算では差がでる
※無限大とＮａＮ
EXP最大値（単精度255、倍精度2047）でFractionが0は無限大
符号ビットにより正負がある。
EXP最大値でFractionにゼロでない値が入っている場合はNaN(Not a Number)
⇒NaNは０÷０、０×無限大のような数値では表現できない結果
⇒NaNを入力として含む演算結果もNaNとなる
⇒最終結果にNaNがあれば、途中の異常を検出できる
⇒メモリをNaNで埋めておけば、初期化しないデータで演算することなどを発見できる
※quietNaNとsignalingNaN
quietNaN 単に伝播していくだけ
signalingNaN 入力に現れるとトラップを発生
※演算の規定
無限の精度で計算を行った結果について規定の丸めを行って、データフォーマットに格納する場合と同じ結果を与えなければならない。
⇒無限精度という規定から、例えば切り上げと行う場合には、精度以下の下位のどこか１ビットにでも１が立つのであれば最下位ビットに１を加える必要がある
⇒ガードビット、ラウンドビット、スティッキービットが必要
ガードビット：最下位ビットの直下
ラウンドビット：その下
スティッキービット：さらにその下の全ビットのＯＲを示す
※誤差を含んだ数値で計算を行う
⇒πなどの無理数や、循環小数は表現できない
⇒得られた結果の含む誤差が分からない。
⇒これに対して区間演算を行えば正確な答えの範囲が保証される
※区間演算(Interval Arithmetic)
⇒常に数値は上限と下限のペアで持ち、演算結果で最大となる組み合わせが上限、最小が下限となるように計算していく
⇒上限の場合は切り上げ、下限は切り捨て
⇒IEEE754では区間演算対応のための丸めが定義されている
※トラップ
異常演算が起こるたびにＯＳに割り込むと性能が低下するので、トラップの原因を記憶し、後で処置をするのが普通
⇒ＩＡ３２ではトラップ６種にマスクビットがありＯＳ割り込みをマスク。トラップを示すフラグは自動ではクリアされずＯＲされる。
＿◇単精度
世界標準のIEEE 形式の単精度浮動小数点数。
bit 31 S:符号
bit 30-23 E:指数
bit 22-0 F:仮数
(-1)^S (1.F)*2^E-127
符号桁（S）が1ビット、指数部（E）が8ビット、仮数部（F）が23ビット、合計32ビット。
符号桁と仮数部で絶対値表現の小数を示す。Fは23ビットではあるが、最上位に”1″を暗に1ビット追加した実質24ビットの数として解釈する。これを正規化された仮数という。ただし、指数部Eが0と255のときは特別なモノを示す。
※浮動小数点数では、指数部に負の数が現れたとき、指数部に一定の数を足し、常に正数とすることが多いが、これをバイアスという。
指数部はバイアスをもち。実際の指数部の大きさeはEから127引いた数で示される（e=E-127）。
e は128から-127を表している。eが127から-126までの値をとるときは、上記のように正規化された仮数を表す。
eが128の場合は無限大や非数（NaN）、eが-127のときはゼロや非正規化数を表す。非正規化数では仮数を（0.F）として表現し、指数は2-126を示す。
e=128 F=0 のとき (-1)^S ∞
e=128 F≠0のとき 非数 NaN
e=-127 F=0のとき (-1)^S 0
e=-127 F≠0のとき (-1)^S 2^-126 (0.F) 非正規数化
＿◇倍精度形式
符号桁は1ビット、指数部は11ビットで1023のバイアス、仮数部は52ビットである。eが1024のときは無限大や非数、eが-1023のときはゼロや非正規化数を表す。1024＞e ＞-1023のときは正規化された（1.F）で示される合計53ビットのデータが表現される。
＿◇4倍精度
指数部が符号桁1ビット、15ビット、仮数部は112ビットである。バイアスは-16383で表現形式は上記と同等である。
＿◇拡張倍精度
符号桁が1ビット、指数部が15ビット、仮数部が64ビット合計80ビットである。
＿◇段階的アンダーフロー
Gradual Underflow
アンダーフローが起きた場合、直ぐにゼロになるのでなく、ヒドンビットを０として、有効ビット数を徐々に低下させながら計算を続けられる
⇒通常の浮動小数点数とは異なる処理（正規化のためのシフト）が必要となる
⇒デノーマル数についてはソフトウエア処理のプロセッサも多い
※デノーマル数の処理は速度が遅くなるため、デノーマル数を自動的にゼロにし、トラップを発生させないプロセッサも多い
⇒x86 MXCSRレジスタdenormals-are-zeroフラグ
◆IEEE Std 754R
①binary 128
radix:2
number of digits:112+1
Emin:-16382
Emax:16383
max.value:1.2…e4932
②decimal 64
radix:10
number of digits:16
Emin:-383
Emax:384
max.value:9.9…9e384
◆IEEE 754-2008
※基本的な２進浮動小数点演算
積和演算が規格に追加された
128ビット長の4倍精度の浮動小数点数も正式のデータ形式が定義された
（Fraction112, Exponent15)
⇒1985版ではFraction64ビット以上、Exponent15ビット以上という拡張倍精度データ形式であった（インテル8087の80ビット長の拡張倍精度など）
※１０進浮動小数点演算の追加
◎初等関数の演算についての福井先生ノート
http://edu-gw2.math.cst.nihon-u.ac.jp/~kurino/2005/analysis/20051101/memo.txt
初等関数の計算
◆関数近似
単純には.. テーラー展開
多項式 / 連分数
※テーラー展開は、h が 0 の近くでは誤差が小さいが、h が大きくなると、誤差が大きくなる。
望ましい誤差曲線
近似区間の誤差の最大が、最小になるように係数を調整
min-max 近似 ( 最良近似 )
※この為には、誤差カーブが決らないといけない→しかし、誤差カーブが解るということは、真値が解るということ
※真値が解らないから、関数近似をしている..
例）24 bit の真値を計算するには ( まるめ誤差のことを考えると.. ) 倍精度の 64 bit で計算し、テーラーの項目をふやせば、時間がかかるが、ある程度求めることができる。
※ハードウェアの bit 数は、限界があるのでソフトウェアでの多倍長ルーチン。
※真値がわかっても..与えられた真値と、近似関数から、min-max を計算するのも非線形な計算なので大変
※関数近似の大家、日大の故山下先生、小野先生、多田先生、浜田先生
①三角関数の近似
sin が理解れば、cos も解る。
# できるだけ計算をサボりたいので..
周期関数なので [0,2π]
形が対称なので [0,π]
同じ対称なので [0,π/2]
加法定理を使えば、更に π/4, π/6 まで狭めることができる。
# 人の好き嫌いでπ/4, π/6を選ぶ
# π/4 : 計算する区間は広いが、折畳む手間が少い
# π/6 : 計算する区間は狭いが、折畳む手間が多い
## 計算量的には、どっちもどっち
\sin{x} のテーラ展開
f(x)=\sin{x}
f(x+h)= f(x)+\frac{h}{1!}f'(x)+\frac{h^2}{2!}f”(x)+\frac{h^3}{3!}f”'(x)+\frac{h^4}{4!}f^{(4)}(x) + ..
より、
\sin{x+h}= \sin{x}+\frac{h}{1!}\cos{x}-\frac{h^2}{2!}\sin{x}-\frac{h^3}{3!}\cos{x}+\frac{h^4}{4!}\sin{x} + ..
ここで x = 0 を代入すれば、
\sin{h}= \frac{x}{1!}-\frac{x^3}{3!}+\frac{h^5}{5!}-\frac{h^7}{7!} ..
これが、近似式
0 <= h <= π/4 < 1
※階乗の計算は速く大きくなるので収束は速い
※さらに、これを min-max にすると…
\sin{h}=h-0.1.666h^3 + 0.083h^5 ..
のようになる。
# ここらへんの係数の調整は、それだけで、ノウハウが沢山ある !!
※引数の誤差の問題
周期関数なので、 x の計算をするときには、 x mod 2π を計算すれば良いが..
x の値がすごく大きいと、 x mod 2π の精度が悪くなってしまう..
=> 桁落が生れる
# 名古屋の二宮先生
# x を a + b x 2π の形で、計算する !!
# => a の所に誤差は出ない。
※πの値に含まれる誤差も問題 !!
# 計算機の中で、何を使っているかは良くわからない !!
# \arctan{1} で π/2 を計算する..
位相の誤差がしょうじている
# 丁度、符号が変るあたりが、怪しい。
# ここらへんは、sin 関数固有の問題
# tan も別な点で気を付ける必要がある
②sqrt は、多項式近似でもよいが、ニュートン法が速くてよい。
f(x) = x^2 – a
とし、
f(x) = 0
の解αを求めれば、
α = \sqrt{a}
となる。
※ニュートン法
f'(x) = 2x
より、
x_{k+1} = x_k – \frac{f(x_k)}{f'(x_k)}
なので、
x_{k+1} = x_k – \frac{(x_k^2-a)}{2x_k}
= \frac{1}{2}( x_k + \frac{a}{x_k} )
初期値の x_0 が問題だが、一般には、テーブルをもっている。単精度の値がでれば、もう１回で、倍精度の精度が出る
# cf 二次収束
a が 0 に近いと収束が速い ( 大きいと遅くなる )。
a が大きい時は、
a = A * 4^n1 \le A \lt 4
とすれば、
\sqrt{a} = \sqrt{A*4^n}
= \sqrt{A}*\sqrt{4^n}
= \sqrt{A}*2^n
となる。
こうすれば、x_0 のテーブルも小くできる。
※4 でわる、2 をかけるは、非常に単純な計算…指数部を調整するだけ。
cf. 一松信、「関数近似」教育出版
培風館の「関数近似」の三冊 ( 最後に、定数表があるので厚い )
ハーツの本
# 関数近似を行っている先生は少い
※関数近似は、計算機の前から研究されている
30 年前に、関数近似に関する衝撃があった。
HP 35 : プログラム電卓
50 万円 : 一松先生 日本で最初
30 万円 : 平野先生
◆多項式近似ではない近似
計算機が得意な、論理演算、シフト等で関数計算をする。⇒多項式近似は、浮動小数点計算ができることを前提としている
⇒浮動小数点計算ではなく、論理演算やシフトで計算したい
＿◇CORDIC
x を二進数展開し、各桁を x_i で表す
x_i = 0 / 1
x = \sum{i= 0}^n{x_i 2^{-i}}
sin の加法公式を使うと..
\sin{A+B} = \sin{A}\cos{B}+\cos{B}\sin{A}
\sin{x} = \sin{\sum{i= 0}^n{x_i 2^{-i}}}
= …
展開した先の値にかんしては関数表をを作る
関数表は、まばらなので、全部記憶してなくて、シフトで計算すればよいので、それほど大きな表にならない
シフトと和で計算ので掛け算と良くにた計算でできる。
# 手計算の時代には、考えられなかった手法
# 仮におもいついても、実行できなかっただろう..
※STL ( Successiable, Table, Lookup )
Intel の Chip の関数表に誤りがあった
※CODIC のよい点
bit 数がふえても、loop 数が増えるだけで実現できる
◆折畳み
計算する空間を縮小する手法
関数の性質を巧く利用して行う
初等関数はだいたい、性質がよい
\tan だけはだめ
結果が無限に飛ぶのは性質が悪い
\log は、
\log{x*2^n} = \log{x} + n\log{2}
なので、なんとかなる。
◎CORDIC
COordinate Rotation DIgital Computer.
http://www.dspguru.com/info/faqs/cordic.htm
◎ERROR
◆Approximation error
「近似」による真値との差
◆Evaluation error
有限の桁数による誤差
◎TEST
①Hough’s UCBTEST
http://www.netlib.org/fp/ucbtest.tgz
②MPCHECK
http://www.loria.fr/~zimmerma/free/
③Test of Mathematical Functions of the Standard C Library
http://www.vinc17.org/research/testlibm/index.html.en
☆正規表現マッチャ
◆Rob Pike作
＿◇仕様
文字 意味
c 文字 c そのもの
. 任意の一文字
^ 入力文字列の先頭にマッチ
$ 入力文字列の末尾にマッチ
* 直前の文字の0回以上の反復
＿◇コード
/* match */
int march(char *regexp, char *text)
{
if (regexp[0] == ‘^’)
return matchhere(regexp+1, text);
do {
if (matchhere(regexp, text))
return 1;
} while (*text++ != ‘\0’);
return 0;
}
/* matchhere テキスト先頭正規表現マッチ*/
int matchhere(char *regexp, char *text)
{
if (regexp[0] == ‘\0’)
return 1;
if (regexp[1] == ‘*’)
return matchstar(regexp[0], regexp+2, text);
if (regexp[0] == ‘$’ && regexp[1] == ‘\0’)
return *text == ‘\0’;
if (*text!=’\0′ && (regexp[0]==’.’ || regexp[0]==*text))
return matchhere(regexp+1, text+1);
return 0;
}
/* matchstar C*型の正規表現をテキスト先頭からマッチ*/
int matchstar(int c, char *regexp, char *text)
{
do {
if (matchhere(regexp, text))
return 1;
} while (*text != ‘\0′ && (*text++==c || c==’.’));
return 0;
}
☆BitBlt
初期のWindowsのBitBlt関数は、ある種のミニコンパイラを含んでおり、ラスタ演算を受け取ると、BitBlt関数がスタック上に8086の機械語命令をサブルーチン形式で生成し、それを呼び出していた。
※３項ラスタ演算
パターンP 11110000
ソースS 11001100
行き先D 10101010
この８通りの組み合わせに対応する結果は256通りありえる。
☆線形計画法など
◎線形計画法
◎シンプレックス法
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=1013
m=2^32 s=3 2953
s=1041
＿◇乗算型合同法
加数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
☆画像認識
◆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
を計測
☆Reference
情報処理 Vol.50 No.11 2009/11/15 情報処理学会
丸山「クラウドの成立過程とその技術的特徴について」
EDN Japan 2010/1 「画像処理プロセッサの基本を学ぶ」
中西
コンピュータグラフィックス 山田宏尚 ナツメ社 2002/5/2
Numerical Recipes in C [日本語版] Press他著 丹慶他訳 1993/6/25 技術評論社
岩波講座 応用数学19 計算理学の方法 1994/2/10 能勢、寺倉、松野、佐藤 岩波書店
実践機械学習システム 2014/10/24 Richert&Coelho著 齊藤訳 オライリー・ジャパン
日経エレクトロニクス 2015/06 ディープラーニングは万能か
考えるコンピュータのアルゴリズム 2007/9/20 アルベルト パラシオス パウロブスキ ソフトバンククリエイティブ
人工知能の基礎(第2版) 2015/2/25 馬場口、山田著 オーム社