Mathematics

エンジニアリングというよりは数学向けの話。

\def\vector#1{\boldsymbol{#1}}

数値解析

Scala による数値演算アルゴリズム

学生の頃に Numerical Recipes in C という多くの実数演算アルゴリズムの載った書籍があった。英語版は 3rd Ed. が出ているようだが日本語版は出ていない。アルゴリズム辞典や数値演算ライブラリを作る気はないのだが系統としてはあの本の方向で行ければ良いと思っている。…

2017年9月27日(Wed)

浮動小数点演算

浮動小数点演算 (floating-point arithmetic) は実数をある範囲の精度で近似した数式表現で行う算術演算のこと。この近似表現を浮動小数点数という。科学技術計算では非常に大きな値や小さな値を扱う代わりに、観測精度の限界から必要な有効数字が保証されていれば十分であることが多い。…

2017年9月29日(Fri)

有効数字

有効数字 (significant figures of number) は実数の分解能を意味する数字。数値のどの桁までが意味を持つかを表している。

2017年10月14日(Sat)

機械イプシロン

機械イプシロン (machine epsilon) は浮動小数点演算の丸めによって発生する相対誤差の上限を意味する。これはコンピュータ演算を使った数値解析特有のトピックである。macheps, unit roundoff または計算機イプシロンとも呼ばれ記号 $\epsilon$ , ${\bf u}$ で表される。…

2017年10月14日(Sat)

解析学

ラグランジュの未定乗数法

ラグランジュの未定乗数法 (method of Lagrange multiplier) は制約付き最適化問題で極値を求めるための手法である。ある 1 つ以上の条件 $g(x)=0$ の下で関数 $f(x)$ が最大値/最小値を取ることを式 ( $\ref{optimal_consumption}$ ) のように表す。…

2017年9月10日(Sun)

不動点反復法

不動点反復法 (fixed-point iteration) は、集合 $X$ からそれ自身への写像 $f:X \to X$ が与えられたとき、方程式 $x = f(x)$ の解を求めるための数値解析的手法。…

2017年10月6日(Fri) 作業中

マルコフ連鎖

時刻やステップの推移で状態空間 $\{1, 2, \ldots, k\}$ のいずれかの値を持つ確率変数について考える。ある時点 $t\in(0, 1, \ldots)$ での確率変数を $x^{(t)}$ とする。…

2017年10月10日(Tue)

指数平滑化法

指数平滑化法 (exponential smoothing) は時系列データを平滑化する代表的な時系列分析手法。観測値の中でより新しいデータに大きな重みを設定し、過去になるほど指数関数的に重みを減少させた期待値 (移動平均) を算出する。…

2018年1月22日(Mon)

Holt-Winters 法

ホルト-ウィンターズ法 (Holt-Winters method) は指数平滑化法における時系列の変動にトレンドと季節変動を追加し、それぞれの指数平滑の重ね合わせを期待値として算出する方法。…

2018年1月31日(Wed) #HoltWinters

初等関数

高速逆二乗根

高速逆二乗根 (fast inverse square root) は浮動小数点と定数を用いて $\frac{1}{\sqrt{x}}$ を高速に演算する方法。

2017年9月29日(Fri) 作業中

特殊関数

ガンマ関数と階乗

ガンマ関数 (gamma function) は 0 または負の整数以外の複素数に対して以下の積分で定義される特殊関数。 $\Gamma(z) = \int_0^\infty t^{z-1} e^{-t} dt$ また漸化式 $\Gamma(z+1) = z \Gamma(z)$ でも表すことができる。…

2017年9月14日(Thu)

ベータ関数

ベータ関数 (beta function) は以下の積分で定義される特殊関数。 $B(x, y) = B(y, x) = \int_0^1 t^{x-1} (1-t)^{y-1} dt$ またガンマ関数を使用して以下のように表すこともできる。…

2017年9月14日(Thu)

代数学

集合論

集合論は数学の基礎的な分野であり、数学的対象を扱う上での基本的な概念や枠組みを提供する。これは集合や要素の集まりを厳密に定義し、それらの性質や関係を明確にすることでそれらを形式的に表現したり操作を行うことができる。…

2023年6月24日(Sat) #集合論

群論

集合とその演算や作用によって定まる構造を代数的構造という。ある集合 $G$ 上の要素 $a,b \in G$ に対して $c = a \ast b \in G$ となるような何らかの演算 $\ast$ が定義されているとき、集合 $G$ は代数系であり $(G,\ast)$ や単に $\mathbb{G}$ と表される。…

2019年10月10日(Thu) #群論

固有値

正方行列 $A$ について、 $Ax=\lambda x$ を満たす値 $\lambda$ とベクトル $x$ をそれぞれ $A$ の固有値 (eigenvalues)、固有ベクトル (eigenvectors) と呼ぶ。…

2024年7月18日(Thu)

組合せ

順列と置換

順列 (permutation) には次の 2 つの意味がある。複数の要素を直線的な順序で配置した状態 $n$ 個の異なる要素からなる集合 $A=\{a_0,a_1,\ldots,a_{n-1}\}$ は $n!$ 通りの順列を構成することができる。…

2024年9月2日(Mon)

論文翻訳: Ranking and unranking permutations in linear time

順列を識別する一意な整数を計算する「ランク」と、順列のランクに基づいて並びを生成する「アンランク」を効率的に行うアルゴリズムを提案する 2001 年の論文。従来の方法では $O(n \log n)$ 時間がかかることが多いが、この論文で紹介されている手法では事前計算された階乗を利用して $O(n)$ の線形時間実行できるようにしている。…

2024年9月4日(Wed) 2001年の論文 #順列

Karchmer and Wegderson は 1993 年にブール関数を計算する興味深い線形代数モデルスパンプログラム (span program) を発表した。ある関数 $f(x_1,\ldots,x_n)$ に対するスパンプログラムは、変数 $x_i$ とその否定 $\bar{x}_i$ でラベル付けされた行を持つ、ある体 (field) 上の行列として表される (一つの変数が複数の行をラベル付けしてもよい)。…

2020年3月8日(Sun) #SpanProgram #BooleanFunction #BooleanNetwork

確率分布

ベルヌーイ分布

結果が {0, 1}、{true, false}、{OK, NG} といった 2 値しかとりえない独立した事象の試みをベルヌーイ試行 (bernoulli trial) と呼ぶ。これらの結果は統計で扱う便宜上 $b \in \{0,1\}$ に置き換えて考える。…

2017年10月4日(Wed)

二項分布

試行において 1 が観測される確率 $p$ のベルヌーイ試行を $n$ 回行ったとき (あるいは $n$ 個同時に行ったとき) に 1 が $x$ 個観測される確率は $p$ と $n$ をパラメータとした以下の確率質量関数で表される。…

2017年9月30日(Sat)

カテゴリカル分布

それぞれ独立した確率 $p_k$ を持つ $K$ 個の事象 (カテゴリカル変数; categorical variable) が存在し、1 回の独立した試行でそのいずれか一つが観測される離散確率分布をカテゴリカル分布 (categorical distribution) と呼ぶ。…

2017年10月2日(Mon)

多項分布

独立した $K$ 個の事象 $k \in \{1, 2, \ldots, K\}$ のいずれか一つが観測される確率をそれぞれ $\vector{p} = (p_1, p_2, \ldots, p_K)$ とする。…

2017年9月30日(Sat) #multinomial

ベータ分布

ベータ分布 (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)$ はベータ関数である。…

2017年10月8日(Sun)

ディリクレ分布

ディリクレ分布 (dirichlet distribution) は独立した事象 $k \in \{1, 2, \cdots, K\}$ がそれぞれ $x_k=\alpha_k - 1$ 回観測されたときに各事象の生起確率が $p_k$ である確率を示す連続した確率密度関数。…

2017年9月10日(Sun)

ポアソン分布

単位時間あたりに平均 $\mu$ 回観測される事象が、単位時間あたりに $r$ 回観測される確率はポアソン分布 (poison distribution) に従う。 $P(X=r) = \frac{e^{-\lambda} \lambda^r}{r!}, \ \ r=0,1,\ldots\s$

2017年10月19日(Thu) 作業中

カイ二乗分布

$\vector{x} = (x_1, x_2, \cdots, x_k)$ が標準正規分布に従う確率変数であるとき、その自乗和 $Z = \sum_{i=1}^k x_i^2$ は自由度 $k$ のカイ二乗分布に従う ( $\chi_k^2$ と表す)。…

2017年10月1日(Sun) 作業中

統計的推定

最尤推定と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})$ で表される (条件付き確率)。…

2017年9月17日(Sun) 作業中

二項分布の推定

事象 $b \in \{0,1\}$ のベルヌーイ試行で $b=1$ となる確率を $p$ 、試行回数を $n$ とした時、1 が $x$ 回観測される (出た数の合計が $x$ となる) 確率関数は二項分布 $P(x;n,p)$ に従う。…

2017年9月18日(Mon)

多項分布の推定

事象 $k \in \{1,2,\cdots,K\}$ がそれぞれ生起確率 $\vector{p} = (p_1,p_2,\cdots,p_K)$ に従って観測されるとき、標本 $x=k$ が観測される確率 $P(k)=p_k$ の分布はカテゴリカル分布に従う。…

2017年10月1日(Sun)

正規分布の推定

平均 $\mu$ 、分散 $\sigma^2$ をパラメータとする正規分布 ${\rm Norm}(\mu,\sigma^2)$ にもとづいて確率変数 $x$ が観測されるとき、その確率密度関数は以下のように表される。…

2017年9月18日(Mon)

ベイズ統計

基本的な用語と方程式

不確定な量。サイコロの目やコインの裏表、温度など。

1970年1月1日(Thu) 作業中

ベイズの定理

$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)$

1970年1月1日(Thu) 作業中

モンティ・ホール問題

1990 年に話題になったとき、著名な数学者を含む多くの人が「同じ確率だから選択を変える必要はない」と答えた問題。最終的な状況を客観視すると、選択可能な箱が 2 つあってそのうちのどちらかが当たりであることから、どちらを選んでも確率は 1/2 に思える。…

2017年10月5日(Thu)

疑似乱数

疑似乱数サンプリング

疑似乱数サンプリング (pseudo-random number sampling) は与えられた確率分布に従う擬似乱数を生成する数値的手法。一般に一様乱数 $u$ を利用して一様ではない分布のサンプリングを行う。…

2017年10月10日(Tue) 作業中

マルコフ連鎖モンテカルロ法

マルコフ連鎖モンテカルロ法 (Markov chain Monte Carlo methods; MCMC 法) は確率分布から疑似乱数サンプリングを行うためのアルゴリズム。ある時点の状態 $x^{(t)}$ からランダムに採択した次の状態 $x^{(t+1)}$ へ確率付きで移動することから "マルコフ連鎖", "モンテカルロ法" の名前で呼ばれる。…

2017年10月10日(Tue) #MCMC 作業中

アルゴリズムも参照。

統計学

相関係数

相関係数 (correlation coefficient) は確率変数 $X$ に対する別の確率変数 $Y$ の線形従属性を示す尺度。最も一般的なものは線形相関係数 (linear correlation coefficient) で積率相関係数 (product-moment correlation coefficient)、Peason の $r$ (Pearson's r) とも呼ばれる。…

2017年10月14日(Sat)

統計的仮説検定

観測値の背景にある母集団の構造を仮定し、観測値の統計からその仮定が受け入れられるか、さもなくば拒否されるかを判断する統計的手法を統計的仮説検定 (statistical hypothesis testing) と呼ぶ。…

2020年6月7日(Sun)

エントロピー

エントロピー (entropy) は、情報理論において情報源から得られる平均的な情報量を表す概念である。1948 年にクロード・シャノンによって導入され、情報理論のきをを那須最も重要な概念の一つとされている。…

2025年8月31日(Sun) #Entropy

Mathematics

数値解析

Scala による数値演算アルゴリズム

浮動小数点演算

有効数字

機械イプシロン

解析学

ラグランジュの未定乗数法

不動点反復法

マルコフ連鎖

指数平滑化法

Holt-Winters 法

初等関数

高速逆二乗根

特殊関数

ガンマ関数と階乗

ベータ関数

代数学

集合論

群論

固有値

組合せ

順列と置換

論文翻訳: Ranking and unranking permutations in linear time

読書メモ: スパンプログラム

確率分布

ベルヌーイ分布

二項分布

カテゴリカル分布

多項分布

ベータ分布

ディリクレ分布

ポアソン分布

カイ二乗分布

統計的推定

最尤推定とMAP推定

二項分布の推定

多項分布の推定

正規分布の推定

ベイズ統計

基本的な用語と方程式

ベイズの定理

モンティ・ホール問題

疑似乱数

疑似乱数サンプリング

マルコフ連鎖モンテカルロ法

統計学

相関係数

統計的仮説検定

エントロピー

グラフ理論

グラフ理論 序説

最小全域木問題

最小経路問題

TRANSCRIPT: A Fast Algorithm for Finding Dominators in a Flowgraph

グラフ理論序説