数値解析
Scala による数値演算アルゴリズム
学生の頃に Numerical Recipes in C という多くの実数演算アルゴリズムの載った書籍があった。英語版は 3rd Ed. が出ているようだが日本語版は出ていない。アルゴリズム辞典や数値演算ライブラリを作る気はないのだが系統としてはあの本の方向で行ければ良いと思っている。…
浮動小数点演算
浮動小数点演算 (floating-point arithmetic) は実数をある範囲の精度で近似した数式表現で行う算術演算のこと。この近似表現を浮動小数点数という。科学技術計算では非常に大きな値や小さな値を扱う代わりに、観測精度の限界から必要な有効数字が保証されていれば十分であることが多い。…
有効数字
有効数字 (significant figures of number) は実数の分解能を意味する数字。数値のどの桁までが意味を持つかを表している。
機械イプシロン
機械イプシロン (machine epsilon) は浮動小数点演算の丸めによって発生する相対誤差の上限を意味する。これはコンピュータ演算を使った数値解析特有のトピックである。macheps, unit roundoff または計算機イプシロンとも呼ばれ記号 \(\epsilon\), \({\bf u}\) で表される。…
解析学
ラグランジュの未定乗数法
ラグランジュの未定乗数法 (method of Lagrange multiplier) は制約付き最適化問題で極値を求めるための手法である。ある 1 つ以上の条件 \(g(x)=0\) の下で関数 \(f(x)\) が最大値/最小値を取ることを式 (\(\ref{optimal_consumption}\)) のように表す。…
不動点反復法
集合 \(X\) からそれ自身への写像 \(f\) が与えられたとき、\(f(x)=x\) を満たす元 \(x\) を不動点 (fixed-point) または固定点と言う。グラフ上では、連続関数 \(f:\mathbb{R} \Rightarrow \mathbb{R}\) の不動点は曲線 \(y=f(x)\) と対角線 \(y=x\) の交点の \(x\) 座標である。…
マルコフ連鎖
時刻やステップの推移で状態空間 \(\{1, 2, \ldots, k\}\) のいずれかの値を持つ確率変数について考える。ある時点 \(t\in(0, 1, \ldots)\) での確率変数を \(x^{(t)}\) とする。…
指数平滑化法
指数平滑化法 (exponential smoothing) は時系列データを平滑化する代表的な時系列分析手法。観測値の中でより新しいデータに大きな重みを設定し、過去になるほど指数関数的に重みを減少させた期待値 (移動平均) を算出する。…
Holt-Winters 法
ホルト-ウィンターズ法 (Holt-Winters method) は指数平滑化法における時系列の変動にトレンドと季節変動を追加し、それぞれの指数平滑の重ね合わせを期待値として算出する方法。…
初等関数
特殊関数
ガンマ関数と階乗
ガンマ関数 (gamma function) は 0 または負の整数以外の複素数に対して以下の積分で定義される特殊関数。\( \Gamma(z) = \int_0^\infty t^{z-1} e^{-t} dt \) また漸化式 \(\Gamma(z+1) = z \Gamma(z)\) でも表すことができる。…
ベータ関数
ベータ関数 (beta function) は以下の積分で定義される特殊関数。\( B(x, y) = B(y, x) = \int_0^1 t^{x-1} (1-t)^{y-1} dt \) またガンマ関数を使用して以下のように表すこともできる。…
代数学
集合論
集合論は数学の基礎的な分野であり、数学的対象を扱う上での基本的な概念や枠組みを提供する。これは集合や要素の集まりを厳密に定義し、それらの性質や関係を明確にすることでそれらを形式的に表現したり操作を行うことができる。…
群論
集合とその演算や作用によって定まる構造を代数的構造という。ある集合 \(G\) 上の要素 \(a,b \in G\) に対して \(c = a \ast b \in G\) となるような何らかの演算 \(\ast\) が定義されているとき、集合 \(G\) は代数系であり \((G,\ast)\) や単に \(\mathbb{G}\) と表される。…
固有値
正方行列 \(A\) について、\(Ax=\lambda x\) を満たす値 \(\lambda\) とベクトル \(x\) をそれぞれ \(A\) の固有値 (eigenvalues)、固有ベクトル (eigenvectors) と呼ぶ。…
組合せ
順列と置換
順列 (permutation) には次の 2 つの意味がある。複数の要素を直線的な順序で配置した状態 \(n\) 個の異なる要素からなる集合 \(A=\{a_0,a_1,\ldots,a_{n-1}\}\) は \(n!\) 通りの順列を構成することができる。…
論文翻訳: Ranking and unranking permutations in linear time
順列を識別する一意な整数を計算する「ランク」と、順列のランクに基づいて並びを生成する「アンランク」を効率的に行うアルゴリズムを提案する 2001 年の論文。従来の方法では \(O(n \log n)\) 時間がかかることが多いが、この論文で紹介されている手法では事前計算された階乗を利用して \(O(n)\) の線形時間実行できるようにしている。…
読書メモ: スパンプログラム
Karchmer and Wegderson は 1993 年にブール関数を計算する興味深い線形代数モデルスパンプログラム (span program) を発表した。ある関数 \(f(x_1,\ldots,x_n)\) に対するスパンプログラムは、変数 \(x_i\) とその否定 \(\bar{x}_i\) でラベル付けされた行を持つ、ある体 (field) 上の行列として表される (一つの変数が複数の行をラベル付けしてもよい)。…
確率分布
ベルヌーイ分布
結果が {0, 1}、{true, false}、{OK, NG} といった 2 値しかとりえない独立した事象の試みをベルヌーイ試行 (bernoulli trial) と呼ぶ。これらの結果は統計で扱う便宜上 \(b \in \{0,1\}\) に置き換えて考える。…
二項分布
試行において 1 が観測される確率 \(p\) のベルヌーイ試行を \(n\) 回行ったとき (あるいは \(n\) 個同時に行ったとき) に 1 が \(x\) 個観測される確率は \(p\) と \(n\) をパラメータとした以下の確率質量関数で表される。…
カテゴリカル分布
それぞれ独立した確率 \(p_k\) を持つ \(K\) 個の事象 (カテゴリカル変数; categorical variable) が存在し、1 回の独立した試行でそのいずれか一つが観測される離散確率分布をカテゴリカル分布 (categorical distribution) と呼ぶ。…
多項分布
独立した \(K\) 個の事象 \(k \in \{1, 2, \ldots, K\}\) のいずれか一つが観測される確率をそれぞれ \(\vector{p} = (p_1, p_2, \ldots, p_K)\) とする。…
ベータ分布
ベータ分布 (beta distribution) は以下の式で表される連続確率分布。確率変数は \(0 \lt x \lt 1\) の範囲を取る。\( P(x; \alpha, \beta) = \frac{x^{\alpha-1}(1-x)^{\beta-1}}{B(\alpha,\beta)}, \,\,\, \alpha \gt 0, \beta\gt 0 \) ここで \(B(\alpha,\beta)\) はベータ関数である。…
ディリクレ分布
ディリクレ分布 (dirichlet distribution) は独立した事象 \(k \in \{1, 2, \cdots, K\}\) がそれぞれ \(x_k=\alpha_k - 1\) 回観測されたときに各事象の生起確率が \(p_k\) である確率を示す連続した確率密度関数。…
ポアソン分布
単位時間あたりに平均 \(\mu\) 回観測される事象が、単位時間あたりに \(r\) 回観測される確率はポアソン分布 (poison distribution) に従う。\( P(X=r) = \frac{e^{-\lambda} \lambda^r}{r!}, \ \ r=0,1,\ldots\s \)
カイ二乗分布
\(\vector{x} = (x_1, x_2, \cdots, x_k)\) が標準正規分布に従う確率変数であるとき、その自乗和 \( Z = \sum_{i=1}^k x_i^2 \) は自由度 \(k\) のカイ二乗分布に従う (\(\chi_k^2\) と表す)。…
統計的推定
最尤推定とMAP推定
ある生起確率 \(\vector{\theta}=(\theta_1, \ldots, \theta_N)\) に基づいてデータ \(\vector{X} = (x_1, x_2, \ldots, x_N)\) が観測されるとき、あるデータ \(\vector{X}\) が観測される確率は \(\vector{p}(\vector{X}|\vector{\theta})\) で表される (条件付き確率)。…
二項分布の推定
事象 \(b \in \{0,1\}\) のベルヌーイ試行で \(b=1\) となる確率を \(p\)、試行回数を \(n\) とした時、1 が \(x\) 回観測される (出た数の合計が \(x\) となる) 確率関数は二項分布 \(P(x;n,p)\) に従う。…
多項分布の推定
事象 \(k \in \{1,2,\cdots,K\}\) がそれぞれ生起確率 \(\vector{p} = (p_1,p_2,\cdots,p_K)\) に従って観測されるとき、標本 \(x=k\) が観測される確率 \(P(k)=p_k\) の分布はカテゴリカル分布に従う。…
正規分布の推定
平均 \(\mu\)、分散 \(\sigma^2\) をパラメータとする正規分布 \({\rm Norm}(\mu,\sigma^2)\) にもとづいて確率変数 \(x\) が観測されるとき、その確率密度関数は以下のように表される。…
ベイズ統計
基本的な用語と方程式
不確定な量。サイコロの目やコインの裏表、温度など。
ベイズの定理
\(P(A \cap B)\) は \(P(A|B)\times P(B)\) と等しく、また \(P(B|A) \times P(A)\) とも等しい。\( P(A \cap B) = P(A) \times P(B|A) = P(B) \times P(A|B) \)
モンティ・ホール問題
1990 年に話題になったとき、著名な数学者を含む多くの人が「同じ確率だから選択を変える必要はない」と答えた問題。最終的な状況を客観視すると、選択可能な箱が 2 つあってそのうちのどちらかが当たりであることから、どちらを選んでも確率は 1/2 に思える。…
疑似乱数
疑似乱数サンプリング
疑似乱数サンプリング (pseudo-random number sampling) は与えられた確率分布に従う擬似乱数を生成する数値的手法。一般に一様乱数 \(u\) を利用して一様ではない分布のサンプリングを行う。…
マルコフ連鎖モンテカルロ法
マルコフ連鎖モンテカルロ法 (Markov chain Monte Carlo methods; MCMC 法) は確率分布から疑似乱数サンプリングを行うためのアルゴリズム。ある時点の状態 \(x^{(t)}\) からランダムに採択した次の状態 \(x^{(t+1)}\) へ確率付きで移動することから "マルコフ連鎖", "モンテカルロ法" の名前で呼ばれる。…
アルゴリズムも参照。
統計学
相関係数
相関係数 (correlation coefficient) は確率変数 \(X\) に対する別の確率変数 \(Y\) の線形従属性を示す尺度。最も一般的なものは線形相関係数 (linear correlation coefficient) で積率相関係数 (product-moment correlation coefficient)、Peason の \(r\) (Pearson's r) とも呼ばれる。…
統計的仮説検定
観測値の背景にある母集団の構造を仮定し、観測値の統計からその仮定が受け入れられるか、さもなくば拒否されるかを判断する統計的手法を統計的仮説検定 (statistical hypothesis testing) と呼ぶ。…
グラフ理論
グラフ理論 序説
グラフ理論 (graph theory) は数学的概念であるグラフを説明する理論。問題を頂点と辺からなるグラフに抽象化し、その離散構造そのものを論議の対象とする。
最小全域木問題
いくつかの頂点と、各頂点の間をつなげるコスト (辺の重み) が定義されており、最も小さいコストですべての頂点をつなぐ最適化問題。コストは 0 より大きく接続不能 (つまりコスト \(\infty\)) も取り得る。…
最小経路問題
重み付きグラフ上のある頂点 \(s\) から別の頂点 \(t\) まで到達する経路の中で最もコストの低い経路を求める問題 (重みなしグラフの場合は各辺の重みを 1 とする)。最小シュタイナー木問題において 2 点を使った最小コストの部分グラフを作成することと同じ。…
TRANSCRIPT: A Fast Algorithm for Finding Dominators in a Flowgraph
A 1979 paper on dominator tree. A transcription of an old PDF for the purpose of reading it in machine translation.