(復習)ニューラルネットワークの誤差逆伝播法による学習 例）パリティ（偶奇性）判定 ニューラルネットワーク 最初に中間層をどれだけ取ればいいのかが不明である。 区分的線形識別関数と等価であるが、ニューラルネットワークほど効果的な学習方法がない ニ…

5.2 正規表現によるパターンマッチング KMPのアルゴリズムを良くみると、入力が戻らない（1方向）である。 ⇒決定性有限オートマトンができるんじゃない？ マッチングオートマトンという。 本質的にはKMPアルゴリズムと同じもの マッチングオートマトンは正規…

6.1 シークェント 定義 A1,A2,...,An ⇒ B1,B2,...,Bm 論理式の多重集合同士の関係 解釈Iに対して、I |= A1,A2,...,An ⇒ B1,B2,...,Bm (Iはシークェントを満たす） iff あるiが存在してI［[Ai]］=falseまたはあるjが存在してI［[Aj]］=true iff I |= A1,A2,..…

3.2 符号の基本的性質 クラフトの定理 長さl1,l2,...,lMとなるM個の符号語を持つr元符号（r個のシンボルを用いた符号）が瞬時符号となりうるための必要十分条件は 十分性の証明 長さiの符号語がni個あって、全体でlグループM個の符号語があるとすると、 nは…

線形時不変（LTI）システム 出力は、入力とインパルス応答の畳み込みで表現できる。 このようなシステムは定数係数差分方程式で記述することができる。 非再帰型システムと再帰型システム 非再帰型システムはかならずFIRになる。 再帰型システムはどちらにな…

例）確率密度関数の積分が確率になる。 計算が大変 区分求積法 積分の定義に基づいた方法 定義： 台形公式 短冊よりも台形のほうがイイだろうという発想。

最少2乗法 実験データの曲線フィッティングなどに用いられる。 定式化が容易である。 直観に合う（2乗和＝分散を最小にする⇒標準偏差を最小にする） 2乗誤差の最小値⇒2乗した合計を微分すると1次の式になるので計算が容易。3.44式は重要ぽ

ニューラルネットワーク 入力層と出力層の間に、閾値論理ユニットが多数存在する。 誤差逆伝播法による学習 全額集パターンに対する2乗誤差を求める。(3.49) 最急降下法を用いて、Jの最小解を求めると （中略） シグモイド関数を用いると と表すことができる…

ストリングマッチング 単純に考えると、n文字の文字列からm文字を探索するにはO(nm)の時間がかかる。 →KMPアルゴリズム・BMアルゴリズム：O(n+m)で実行できる KMPアルゴリズム 2DPDA：2方向決定性オートマトン 前後に動く＆スタックがある。 定理：RAMは2DPD…

ハッシュ法 ハッシュ＝切り刻む ハッシュドビーフのハッシュ

証明系の健全性 ある証明系において、Φ├{PS}AならばΦ|=Aという証明系を健全であるという。 （PSの推論規則においてΦからAが導けるならばΦを満たすすべての解釈はAを満たす） 証明系の完全性 ある証明系において、Φ|=AならばΦ├{PS}Aという証明系を完全である…

情報源符号化/通信路符号化 3.1 符号の分類 符号化をすると符号語ができる。 記号の種類数による分類 符号に使う記号の種類数 よく使うのは２元符号 {0,1} 符号化の単位による分類 通報の記号毎 通報のブロック毎（n文字毎：n次拡大情報源）…（等長の）ブロ…

英語の語句を情報源と考える 第ゼロ近似 独立、等確率 第１近似 独立、確率：頻度（表6.1） 無記憶情報源 第２近似 単純マルコフ情報源 ２文字の確率を考える。 第３近似 ２重マルコフ情報源 ３文字の確率を考える。状態数は27*27

覚えておくべき点 記憶なし情報源のエントロピー： マルコフ情報源のエントロピー：各状態のエントロピーの平均 随伴情報源のエントロピー： 拡大情報源のエントロピー： 拡大情報源の随伴情報源のエントロピー：

離散フーリエ変換DFT 離散フーリエ変換の性質 線形定理 線形だということ。Nは長いほうにあわせる。 対称定理 折り返したものは位相が反転しているということ。 循環推移定理 周期信号の推移定理として考えるということ。 循環たたみ込み定理 たたみ込みも周…

ラグランジュ補間 復習 N+1の点→N次の多項式 ラグランジュ補間の誤差 を満たすξが存在する。 ルンゲの現象 高次のラグランジュ補間を行うと、x=±1の付近で誤差が発散する。 高次のラグランジュ補間は避けよう スプライン補間 ラグランジュ補間の問題点 点数…

区分的線形識別関数 どのような複雑な決定境界も任意の精度で近似できる パーセプトロンの学習法が適用できない 多層ニューラルネットワークと極限において等価である 誤差評価に基づく学習 線形分離不可能な場合（線形関数で完全に識別することができない場…

パシステント構造 領域を分割した構造。今自分がどの領域にいるかという問題（点位置決定問題）がお手軽に解ける。 何度も同様な質問が繰り返されるときに最適っぽい。 分割格子点がn個くらいあるとすると、すべての分割格子点で縦に分割した“スラブ”を2分探…

5.1 自然演繹による証明 を証明する。 こういうときは、勝手に選んだ値y=aを決める。 が成り立つことを示せば、任意のaについて、 を証明できる。この証明を木構造で表すと（めんどい） 証明木と推論規則 証明木を定義する Asmp(Π)：証明木Πの上の仮定 Concl…

2.3.1 マルコフ情報源のエントロピー k元m重マルコフ情報源の状態数はr=k^m存在する。 状態sjにいるときのシンボルの平均情報量は で表すことができる。 したがってすべてのエントロピーは 2.4 随伴情報源とマルコフ情報源の拡大 2.4.1 随伴情報源 あるマル…

離散時間信号のフーリエ変換 Z変換 両側z変換 片側z変換 因果的な信号なら両側z変換＝片側z変換 Z変換の性質 線形性 時間軸推移 共役信号 離散畳み込み演算 複素畳み込み演算 パーセバルの定理 単位円を積分路とする場合。 （詳しい内容は教科書でも見るべし…

http://www.vision.ie.niigata-u.ac.jp/~tamaki/2000signal/signal000519/

ニュートン法 方程式の反復法による解法のひとつ 以下の漸化式を解く（ホワイトボードには斬化式と書いてある…） 例題 f(x)=(x-1)(x-2)(x-3)について解く f'(x)=3x^2-12x+11やったことにした 計算量 P次収束（1次収束、2次収束） 誤差：εn=xn-α について …1…

比較の件（メール消してしまったので一応メモ） http://www.watanabe.ss.is.nagoya-u.ac.jp/~y_tanaka/compiler/data/2A.ok.p http://www.watanabe.ss.is.nagoya-u.ac.jp/~y_tanaka/compiler/data/3B.ok.p 比較は：scanner ./sample/PL2A.p | diff -b 2A.ok.…

アンケート実施結果（ノートとる意味ないけど） 「想定の範囲内です」らしい。 以下省略P65- 特徴空間の次元数とパターン数 パターンが少なければ、線形分離が簡単にできてしまうが、正しくクラスを識別できない可能性がある。 特徴相互に強い相関がある場合…

4.1 2分探索 検索・挿入・削除がO(logn)時間で実行される。 4.2 2分探索木 右の子 検索・挿入・削除は木の高さに比例する。 最悪の場合木の高さはn-1になる。 ランダムに要素を挿入すると… データの割り当てられている点の個数をn個として、これを内点と呼び…

1.意味論的同値が同値関係であることを証明せよ 反射的であるのは定義から自明 対称的であるのは定義から自明 推移的であるのは定義から自明 よって意味論的同値は同値関係である。 2.AとBが意味論的同値であってもα等価でない例を挙げよ。 解答例）AとA∨A（…

4.5 意味論的同値 どんな解釈の仕方をしてもAとBは真偽が同じ 定義：すべての付値について 意味論的同値は同値関係である 復習：同値関係 反射的 対称的 ならば 推移的 かつならば 補題4.5.6 変数の名前替えをしたもの同士は意味論的に同値である。 命題4.5.…

P.20- 統計的性質 長さnのシンボル系列 X1,X2,...,Xn-1 Xi : 確率変数 これを p(x0,x1,...,xn-1)のようにあらわす。 結合確率分布から確率分布を求める講義では定常情報源を扱う 無記憶定常情報源 どの時点から始めても統計的性質が変わらない。 定常性 ： …