節（Clause） 全ての要素がアトムであるシークェントのことを節という。空シークェントを空節という。 冠頭標準形：スコーレム標準形：節集合 充足不能性で等価である。 スコーレム標準形を節の集合で表したものを節形式という。 名前変代入 名前変えにより…
加法的通信路のモデル 雑音源からの情報をEx-ORで加算する。雑音源が記憶のない情報源 →二元対称通信路 雑音源が記憶のある情報源 通信路符号化の基本的性質 雑音のない場合 雑音のない通信路に対する符号化定理＝情報源符号化定理 雑音のある場合 シャノン…
適応システム 必要に応じてシステムの特性を変化させるシステム 変化させる方法を適応アルゴリズム(adaptive algorithm)という。
土井美和子（東芝）ユビキタス：ubiquious みんなで一台→一人に一台→いたるところにコンピュータ 人とモノが等価に存在する モノとモノのコミュニケーション 情報をもとに動かすのは依然人間の役割 ヒューマンインタフェース トレードオフが重要 機能vsコス…
微分方程式を差分方程式に変換して解く h→0とすれば誤差→0となる。 hが小さくなるに従って誤差が急激に小さくなるような差分方程式は性能が良いといえる。 差分商 前進差分商:{f(a+h)-f(a)}/h 後退差分商:{f(a)-f(a-h)}/h 中心差分商:{f(a+h/2)-f(a-h/2)}/h …
共分散行列の固有ベクトルは主軸に対応する。 行列の固有値を求める 数値計算的な解法 任意のベクトルx(0)を持ってくる でk→∞とする。 (方向が)収束したxに対して 任意のiについて*1 （単位ベクトル化により） レイリー商 Aが実対称行列→固有値は実数 内積を…
復習：ベイズ決定則 次のような判別関数が使えた 学習パターンによる判別関数の生成 パラメトリックな決定境界の導出 最尤法による推定 各コインの含有確率(p(ω))はわかっているが、各コインの表が出る確率(θ)はわからない。というケースを考える。 最尤法は…
7.5 2連結成分アルゴリズム どの1個の頂点を除去しても残りのグラフが連結であるようなグラフグラフを2連結なグラフに分割する。 関節点を見つけるアルゴリズム 深さ優先探索をして、順番をつける。 ある頂点の子孫全てが自分の先祖への逆辺を持っていなけれ…
最汎単一化子 代入の合成 θ=[f(x)/x,g(z,b)/y] σ=[f(z)/x,a/z] h(x,y,z)θσ=h(f(x),g(z,b),z)σ=h(f(f(z)),g(a,b),a) こんな代入になるような代入の合成を定義する。 代入θ=[s1/u1, ... , sm/um],σ=[t1/v1, ... ,tn/vn]に対してその合成は θσ=[s1σ/u1, ... ,sm…
スコーレム標準形 スコーレム標準形とは、存在限量子を含まず、全称限量子の変数が全て異なる冠頭標準形のことである。 スコーレム標準形は任意の論理式に同値な論理式が存在するとは限らないが、任意のAに対してスコーレム標準形Bが存在し、 Aが充足不能 if…
講師：永田銕男（アルファシステムズ）
SOR法（Succesive Over-Relaxation Method） ω：加速係数（ω=1：ガウズ・ザイデル法）：一般に1〜2の値 ガウス・ザイデル法の数倍の速さで収束する SORの意味 ガウス・ザイデル法では下のようであった。 上の方の式より、 上式の左辺はx1のk+1回目とk回目の…
ベイズ統計・推定・Error 例）三種類のコインがある。 w1=10% 表の出る確率θ1=0.8 w2=40% 表の出る確率θ2=0.6 w3=50% 表の出る確率θ3=0.3ある1個のコインを取り出してn回投げてx回表が出たとする。 コインがどのコインかを推定する方法は？ ベイズの定理 計…
7.4 最小スパニング木 連結な無向グラフの全ての頂点を含む部分グラフで木であるものをスパニング木という。 行列木定理 連結な無向グラフGのスパニング木の個数はL(G)*1の任意の対角要素に関する余因子の値に等しい。 重み付きグラフの重みを最も小さくする…
連言・選言標準形 以下の議論では限量子を含むものは考えない 連言標準形 (P1 ∨ P2)∧(P3 ∨ P4)∧(P5 ∨ P6)のように、∨で結合した節(clause)を∧で結合した形。 選言標準形 (P1 ∧ P2)∨(P3 ∧ P4)∨(P5 ∧ P6)のように、∧で結合したもの（特に名前はない）を∨で結合…
4.1 通信路のモデル 通信路の統計的性質 定常：時間をずらしても統計的性質が変わらない 無記憶：その時点の入力のみに出力が依存し、他の時点での入力や出力とは無関係 一般に 入力アルファベット＝入力記号の集合：X={a1,a2,...,ar} 出力アルファベット＝…
変換方法 s-z変換に基づく方法（間接設計法） アナログフィルタの伝達関数からディジタルフィルタを求める ディジタルフィルタとして設計する方法（直接設計法） 標準z変換法（インパルス不変法） 伝達関数をラプラス逆変換して、インパルス応答を求める イ…
LU分解 http://www.fuka.info.waseda.ac.jp/~kozo/suuchi/simple_equation/simple_equation_3.html 計算量 LU分解 O(n^3) 代入 (n^2) ヤコビ法 http://www2.ee.knct.ac.jp/el/E4/H15-E406/hanpuku.html 計算法は略。単純 収束性の必要十分条件 において、Bの…
3囚人の問題 Ω(A)=Aが釈放されること X(B)=看守が「Bは処刑される」と答えること P(Ω(A))＝P(Ω(B))＝P(Ω(C))＝1/3(1) Aが釈放される→BとCが処刑される。 (2) Bが釈放される→AとCが処刑される。 (3) Cが釈放される→AとBが処刑される。P(X(B)|Ω(A))=1/2,P(X(B)…
Gの完全性の証明（続き） 復習 公平な導出木 ΦとΨ（各辺の無限経路のある位置以上の位置に存在し続ける論理式の和集合） 任意のシークェントに対して公平な導出木が存在する。 →展開レベルの小さいものから展開する。 補題6.7.6 ※このとき、有限な公理で終了…
算術符号 情報源シンボル系列⇒系列の累積確率[0,1)の2進表現（符号も2元） 例） P(0)=0.7 P(1)=0.3 累積確率二進表現符号 P(000)=0.343 0 .00000...00 P(001)=0.147 0.343 .01010...010 P(010)=0.147 0.49 .01111...011 P(011)=0.063 0.637 .10100...1010 P(…
フィルタとは、ある帯域の信号は通過し、それ以外の帯域の信号は遮断する装置 低域通過フィルタ 高域通過フィルタ 帯域通過フィルタ 帯域阻止フィルタ（ノッチフィルタを含む） FIRフィルタ FIRフィルタは直線位相特性を実現できる。 ・・・理解不能 いや、…
連立一次方程式 計算方法 直接法（消去法）変数をひとつずつ消す ガウスの消去法 LU分解法 反復法：繰り返し演算により解を収束させる。 ヤコビ法 ガウス・ザイデル法 SOR法
先週の ・基底ベクトルの正規直交性 より後ろあたりから。 両辺転置すると（Σは対象行列なので） 正規直交性があるので これより (…でなんだったんだっけ？) パラメトリックな学習とノンパラメトリックな学習 （教科書範囲外） ベイズ統計とか（テストに出す…
グラフの表現 隣接行列 接続リスト 隣接リスト n+1頂点の根付き木とn頂点の2分木の頂点の集合は1対1に対応する。 ダイクストラのアルゴリズム 最短路木を作ってやれば、最短路を求めることができる 作り方：Uからuを取り出したときに、その親との関係を保持…
Gの完全性 エルブラン解釈 一階言語の部分集合Sについての構造みたいな感じのMについて Mがエルブラン構造で、V(x)=x for all x ∈ Var_s なら、I=(M,V)はエルブラン解釈エルブラン構造 |M|＝Hs=T(Fun_s,Ver_s) M［[f]］(t1,...,tn)=f(t1,...,tn) M［[P]］は…
復習 定理3.2,3.2は重要 シャノンの符号化 ファノの符号化法 情報源のシンボルをなるべく等確率になるように二つに分けることを繰り返す。（言いたいことはわかるけどなるべく等確率になるようにの判断が難しいな…） ハフマン符号 省略させてください ハフマ…
DFTの定義式 より（中略） バタフライ演算 ビットリバーサル 演算回数の比較 複素乗算回数 DFT:N^2 FFT:{N(logN - 1)}/2 複素加算回数 DFT:N(N-1) FFT:NlogN 5.4,5.5は飛ばす FFTの応用 スペクトル推定（何がやりたいのだろう） 循環たたみ込み 循環たたみ込…
特徴空間の変換 正規化 次元の削減 より良い特徴量を選択 線形変換により次元を削減 識別に適した空間を作る⇒Fisherの方法 KL展開 KL展開は識別に適した空間を作っているわけではない。 KL展開により、元の空間をできるだけ保存したより次元の低い空間を作る…
ωn = 1の原始n乗根 n乗して初めて1になる数。 n=2:-1 n=3:(-1±√(3)i)/2 n=4:±i n=5:5個 離散フーリエ変換(Discrete Fourier Transform) 入力x=(x0,x1,x2,…,xn-1) 出力y=Ax Aはn次正方行列。 単純な計算を行うとO(n^2)となる。 たたみこみ(convolution) 例：…
