記事一覧
パターン認識と機械学習 学習ノート - 正規分布2
この記事は「パターン認識と機械学習 (丸善出版社)」の読書ノートです。
今、ある正規分布$${\mathcal{N}(x|\mu, \sigma^2)}$$にしたがう確率変数の$${N}$$個の組$${\mathcal{X} \equiv (x_1, x_2, \cdots, x_N)}$$を考える。これらは互いに独立である、つまりそれぞれの値の現出・観測がお互いに影響しないような実験を考えると
パターン認識と機械学習 学習ノート - 正規分布1
この記事は「パターン認識と機械学習 (丸善出版社)」の読書ノートです。
この記事では連続変数の分布の中でも極めて重要な正規分布と呼ばれる分布を導入し、その性質を少し見ていく。
正規分布とは、以下の$${x}$$という連続変数に対し、以下の確率密度関数を持つ分布のことを指す。
$$
\mathcal{N}(x | \mu, \sigma^2) = \frac{1}{\sqrt{2\pi \si
量子計算学習ノート - 計算問題の解析2
この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。
この記事では前回導入した漸近表示、$${O, \Omega, \Theta}$$について実例を見ていこう。
$${f(n) = 2n}$$のとき、$${f}$$は$${O(n^2)}$$のクラスに属する
$${f(n) = 2^n}$$のとき、$${f}$$は$${\Omega(n^3)}$$のクラスに属する
$${
パターン認識と機械学習 学習ノート - ベイズ確率2
この記事は「パターン認識と機械学習 (丸善出版社)」の読書ノートです。
前回の記事ではベイジアンの考え方について述べ、以下に示すベイズの定理から尤度関数$${p(\mathcal{D}|\bold w)}$$というものについて紹介した。
$$
p(\bold w | \mathcal{D}) = \frac{p(\mathcal{D}|\bold w)p(\bold w)}{p(\mathca
パターン認識と機械学習 学習ノート - ベイズ確率1
この記事は「パターン認識と機械学習 (丸善出版社)」の読書ノートです。
ここまで確率とは、繰り返し試行において起こりやすさ（つまり頻度）とみなしてきた。このような確率を古典的確率とよび、このような確率の解釈を頻度主義的な確率解釈という。
この記事ではより一般的なベイズ的な（ベイジアン）解釈・見方を導入する。この見方では確率は確実度合を与える尺度に昇華される。
これまで考えてきた事象は、リンゴと
パターン認識と機械学習 学習ノート - 期待値と分散
この記事は「パターン認識と機械学習 (丸善出版社)」の読書ノートです。
確率を含む操作において最も重要なものは期待値を求める操作である。今、確率分布$${p(x)}$$が離散的であるとき、ある関数$${f(x)}$$の期待値とは次のように定義される関数$${\mathbb{E}[f(x)]}$$のことである。
$$
\mathbb{E}[f(x)] \equiv \sum_{x} p(x) f
パターン認識と機械学習 学習ノート - 確率密度
この記事は「パターン認識と機械学習 (丸善出版社)」の読書ノートです。
ここまでは離散的、すなわち有限もしくは可算無限の事象集合の場合における確率を議論してきた。実数のような非加算無限、つまり連続的な事象集合の場合における確率を議論する。
実数値を取る確率変数$${X}$$が区間$${(x, x+\delta x)}$$に入る確率が、$${\lim_{\delta \to 0} p(x)\de
量子計算学習ノート - 計算問題の解析1
この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。
ここからは計算機によって計算される問題自体についての考察を深める。まず、計算問題についての私たちの基本的疑問は次の3つである。
計算問題とはいったいどんな問題か？
与えられた計算問題を解くためのアルゴリズムをうまく設計する方法は？
与えられた計算問題を解くために必要最小限なリソースは何か？
ここから数回は1と3につ
量子計算学習ノート - 回路モデルとチューリング機械モデル
この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。
以前、回路による計算モデルとチューリング機械による計算モデルは計算できる関数のクラスが同じという意味で等価であると述べた。ここではそれを示そう。
まず、回路族$${\{C_n\}}$$という集合を考えることにする。回路族とは特定の関数$${C: \mathbb{N} \to \mathbb{N}}$$を計算する回路$${
量子計算学習ノート - 回路3
この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。
前回、有限数ビットから有限数ビットを出力するあらゆる関数に対して、その関数を計算する回路が存在することを示した。この記事ではそのようなあらゆる回路は実はNANDゲートだけあれば構成できることを示す。
前回構成した回路の構成要素には次の4つがある。
配線
補助ビット
FANOUT
AND、XOR、NOTゲート
こ
量子計算学習ノート - 回路2
この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。
前回は回路を構成するいくつかのゲートと、それを用いて自然数の和を求める回路を構成した。今回は和だけではなく、任意の関数を計算する回路がここまで使ってきたゲートで構成できることを示そう。
まず、簡単のために$${n}$$入力、$${1}$$出力の場合を示す。つまり任意の$${f: \{0,1\}^n \to \{0,1\}
計算理論学習ノート - 非決定性
この記事は「計算理論の基礎(共立出版)」の読書ノートです
前回は有限オートマトンの認識する言語、正規言語と正規演算について紹介した。また和集合演算に対しては正規言語で閉じていることを示した。
順当には連結演算に対して正規言語で閉じていることを示したいが、実はこの証明をするためには非決定性の有限オートマトンを導入したほうがわかりやすい。よってここで非決定性の有限オートマトンを導入することにする。
量子計算学習ノート - 回路1
この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。
これまでは計算モデルとしてチューリング機械を扱ってきたが、チューリング機械は少し理想化されたモデルだった。というのもテープの長さは片方に無制限であり、実際のコンピュータは記憶領域は有限であることに反している。そこで回路による計算モデルを導入しよう。
回路による計算モデルは後に示すが計算能力としてチューリング機械と等価であ
計算理論学習ノート - 正規言語と正規演算
この記事は「計算理論の基礎(共立出版)」の読書ノートです
ある有限オートマトンで認識される言語を正規言語という。正規言語に対して以下の演算が定義できる。
スター演算は$${k = 0}$$の場合も含むため、空文字列$${\varepsilon}$$は常にスター演算後の言語に含まれる。
ところで正規演算の結果が再び正規言語になるかどうか、すなわち認識する有限オートマトンが存在するかどうかは自明
計算理論学習ノート - 有限オートマトン
この記事は「計算理論の基礎(共立出版)」の読書ノートです
有限オートマトンはメモリ容量が著しく制限された計算機に対する良いモデルとなる。
有限オートマトンは次の5つの組からなる数学的対象だ。
有限集合$${Q}$$: 状態集合と呼ばれ、要素を状態という
有限集合$${\Sigma}$$: アルファベットとよばれ、要素を文字という
関数$${\delta: Q \times \Sigma
量子計算学習ノート - チューリング数3
この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。
前回チューリング数を定義したので、このチューリング数を用いて「万能チューリング機械」と「停止問題」について述べる。まずは万能チューリング機械について説明しよう。
万能チューリング機械は、任意のチューリング機械のシミュレーションができるチューリング機械のことだ。万能チューリング機械$${UTM}$$はチューリング機械$${