Tokyowebmining #49 Matirx and nonparametric bayes
?
32 likes?8,470 views
Tokyowebmining #49 Martix and Nonparametric Bayesian Models
![ディリクレ過程(平易な形)
25/18
分散数および分割の仕方の如何に関わらず、確率ベクトル
g = (G(A1),???,G(Ar)) が
p(g) = Dir(α1 ,???,αr)
αi = αG0(Ai) (i = 1,…, r)
を満たすとき、このような確率分布G(θ)を生成する確率過程を
ディリクレ過程といい、次のように記す
G(θ) ～ DP(α,G0(θ))
G(Ai)の期待値と分散は
E[G(Ai)] = E[gi] = αi / α = G0(Ai)
V[G(Ai)] )] = V[gi] = αi(α - αi) / α2(α + 1)
= G0(Ai)(1 - G0(Ai)) / (α + 1)
となる。すなわちDP(α,G0(θ))からG(θ)を生成し、そのG(θ)か
ら生成したθが区間Ai 内にある確率gi =G(Ai)の値は、平均とし
てαi / α = G0(Ai)となる。また集中度αの値が大きい程、G(Ai)
の分散が小さくなってより平均に集中する。](https://image.slidesharecdn.com/20151024tokyowebminingmatrix-151024054846-lva1-app6891/85/Tokyowebmining-49-Matirx-and-nonparametric-bayes-25-320.jpg)
Tokyowebmining #49 Matirx and nonparametric bayes
- 1. 統計分析?機械学習に 関わる線形代数の整理中 とノンパラメトリックベイズのほんの走り 2015/10/24 Tokyowebmining #49 KennyISHIMURA Powered by 嫁 1/20
- 2. スライドの流れ ? 肉食系(正規分布大好き)男子?星野哲郎は銀河鉄道９９９(線形代数)に乗って、 機械の体(線形代数のテクニックを使用した文献を読める体)を手に入れるべくアン ドロメダ(主成分分析?時系列分析の収束判定や状態空間モデル???)へ旅をしようとし ていた。 ? 途中、宇宙戦士の銃(写像?固有値)という武器も手に入れて、さあ機械の 体を目指そうと思ったところ、某HMD銀河指令より「今日はノンポ リ(ノンパラメトリック)草食系(ベイジアン) があるのそっち行ってね?」との 指令を受けた。 ? 肉食系哲郎は、草食系(ベイジアン)てつろうに宗旨替えをして、銀河鉄 道９９９を降りた。 ? 草食系の中での戦いは、宇宙戦士の銃等はあまり活躍せず、禅問答 のように「Zizenn!」(事前分布)とお題を決められるとその型で「Zigo!」 (事後分布)と返すものだった。 ? 哲郎がさらに草食系の中のノンポリ系の中に入ると、実はノンポリ (ノンパラメトリック)どころが、無限ポリ(無限次元パラメトリック)ということ だった。。。 2/20
- 4. 行列はなぜ有効か？ ? 数の組をいっぺんに効率よく処理できる。 ?まさしくデータ分析処理 ? 処理=「行列を掛ける」という方式に拘ると、その処 理を繰り返すとどうなるかの判断ができる。 ? 「処理」「処理の結合」が結局どの様なものかを判 断しやすくなる。 4/20
- 5. 行列の直感理解(=写像) ? 行列とは、空間の変形である(＝写像?変換) ? 「変形」＝回転と伸ばしと次元変更 ? 標準基底(軸方向単位ベクトル)の動きで理解する。 5/20 -1 -0.5 0 0.5 1 -1 -0.5 0 0.5 1 1 0 -1 -1 0 1 行列A＝ 1 -0.3 -0.7 0.6 ポイント ?原点は原点のまま ?e1=(1,0)Tは(1,-0.7) Tへ ?e2=(0,1)TはTへ （例１） 上記は２×２の行列（２次元から２次元への写像）だが、 m×n行列はn次空間をm次空間に移す。 (1,-0.7) T (-0.3,0.6) T e1 e2 行列Aを掛けることで、空間を「回転」させたり「つぶし」たり「ぺっちゃん こ」にしたり。 Ae2 Ae1 e1の変形先 e2の変形先
- 6. 行列の直感理解(=写像) ? 行列とは、空間の変形である(＝写像?変換) ? 「変形」＝回転と伸ばしと次元変更 ? 変形の極端な例としてつぶれることもある 6/20 B＝ C＝ 0 -1 1 0は上下をつぶす行列。 は反時計回りに90度回す行列。 （例３） ?移った先の像（Im○）の次元数をランクという。例２でImBのランクは１。 ?移った先のランクが変わらないのは正則行列(逆行列が存在)。減るのは特異行列。 ?正方行列でも、ぺちゃんこにする行列もある(例2) 。 →ランクは「手がかりの実質的な個数」ともいえる。 D＝ 0.8 -0.6 0.4 -0.3 BやDのように次元が減ってしまう（移り先を知っても元が特定 できない）＝逆行列が存在しない 1 0 0 0 （例２） （例４） はぺちゃんこにしてしまう特異行列
- 7. 行列の直感理解(=写像) ? 行列とは、空間の変形である(＝写像?変換) ? 「変形」＝回転と伸ばしと次元変更 ? 面積?体積拡大率は行列から計算(行列式)で分かる。 7/20 -1 -0.5 0 0.5 1 -1 -0.5 0 0.5 1 1 0 -1 -1 0 1 行列A＝ a b c d (a,c) T (b,d) T e1 e2 行列式detAが写像の面積拡大率 Ae1 Ae2 e1の変形先 e2の変形先 http://www.ies-math.com/LoveMath/2nd_grade/adbck-j/adbck-j.html (a+b,c+d) T 行列式 = 面積拡大率 detA ＝ ad-bc 平行四辺形の面積の直感的理解
- 8. 写像のパターン ? 全射:どんなyにも元ｘが存在する 8/18 x x’ O y y’ ３次元空間 → ２次元空間 A IｍA ３次元空間 → １次元空間 A 全射でも単射でもない １次元空間 → ３次元空間 A 単射(全射ではない) O x y y’ O IｍA x x’ O y IｍA 全射(単射ではない) O 全単射 ２次元空間 → ２次元空間 A O ? 単射:同じ結果yが出る元ｘが唯一存在する
- 10. 安定性判定 ? x(t)=Ax(t-1)=Atx(0)のAtを簡単に出せればよいが、少し 複雑 ? P-1AP=Λ ? A=PΛP-1 Λ：対角行列 となるPを見つけることにより、 ? x(t) = Atx(0) = (PΛP-1)t x(0) = (PΛt P-1)x(0) とAtが簡単な式 として表せられる 10/18 x(t)= x(0)= a1 t an t a1 an t x(0)
- 11. 安定性判定 ? 対角化すると簡単になるので、この順番を狙う ① 全単射にて基底変換(相似変換) ② 対角化 ③ 計算 ④ 基底変換を戻す ? このためには上手い正則行列Pを選ぶ必要がある ? ?固有値?固有ベクトルを求める問題へ ? 対角化＝「P-1APが対角」となるような「都合のよいP」を作る。 ? Ap=λp p≠o 固有値λ1,…, λnと対応する固有ベクトルp1,…, pnを求める。 ? 固有値の絶対値| λ 1|???| λ n|のうち１つでも１より大きければ暴走。 ? 【固有値の幾何学的意味】 伸縮はしても方向は不変。 ? 伸縮率＝固有値 11/18 右の例では、 伸びてる方の固有値1.3 縮んでる方の固有値0.3
- 16. 余談 16/18 ガロアが完成させた、 「方程式の難しさを図る方法」「どんな場合にべき根を用いて方程式が解けるのか」 （『数学の言葉で世界をみたら～父から娘に贈る数学～』より） ? ガロアってどんな人 ? 19世紀最高の数学者の１人、エバリスト?ガロア ? 1811年フランス生まれ（『レ?ミゼラブル』の時代設定とほぼ重複） ? 18歳で共和主義者として７月革命に参加 ? ルイ?フィリップが立憲君主として即位し、共和主義者は挫折 ? 政治的に先鋭化したガロアは20歳で投獄 ? 出獄後に決闘の挑戦を受け、致命傷を負い、20歳７か月で死亡 ? ガロアがチャレンジするまでに分かっていた方程式の解法 ? １次方程式→四則混合計算の完成（貨幣発明の頃？）で解決。 例）a-bはx+b=aの解x ? ２次方程式→９世紀バグダードの数学者アル=フワーリズミーが発見。 ? ３次方程式→16世紀にデル?フェッロとタルタリアが 独立に発見、カルダーノが公表。 ? ４次方程式→カルダーノの弟子ロドビコ?フェラーリが発見、公表。 ? ２～４次はすべて、平方根や立方根で表記可能。 ? 次数が上がるほど「難しい」 例）２次方程式では平方根（無理数という新たな概念含む）が出てくる。 平方根は定規とコンパスで作図できるが、立方根はできない。 ? 以降300年、数学者たちの努力もむなしく、５次方程式の解は見つからなかった。
- 17. 余談 17/18 ? アーベルが「５次方程式には解の公式が存在しないことを証明」 ? ニールス?ヘンリック?アーベル。1802年ノルウェー生まれ。 ? 何かが「できない」ことを示すのは難しいが、 アーベルは「方程式の難しさを測る方法」を利用。 ? べき根だけを使って解くことのできる方程式をすべて見つけ、 どんな場合にべき根で解けるか、解明を試みた。 ? が、達成できず。 ↓これを明らかにしたのがガロア。 ? ガロア理論の完成 ? あらゆる次数の方程式について、 その方程式がべき根で解けるかどうかを判定する方法を発見。 ? この論文を世に発表しようとしたが、 唯一の理解者コーシー（王政派）が７月革命によって亡命。 ? コーシー亡き後のアカデミーには 彼の研究を理解できる数学者はいなかった。 ? 高等理工科学校の受験に２年続けて失敗したり、 町長をしていた自由派の父親が自殺したり。 ? 絶望したガロアは革命に身を投じ、投獄。→決闘。→死亡。 ? ガロアは、決闘の前夜から早朝までかけて、 親友オーギュスト?シュバリエに手紙を書いた。 ＝これが現在「ガロア理論」として知られているもの。 ? ガロアの死後、リウビルがガロアの遺稿を解読し、 1846年に解説を発表。＝ようやくガロア理論受け入れ ちなみにこの人も 26歳８か月で逝去。 貧乏で肺結核に。 今ではオスロの 王宮に記念碑が。 死の直前、 シュバリエに宛てた手紙→
- 19. ノンパラメトリックベイズとは ? ディリクレ過程やベータ?ベルヌーイ過程などを総称した確率モデル ? ノンパラメトリックという名があるが、確率分布は仮定しており、無 限個のモデルを想定した無限個のパラメータを持ちえるベイズモデル の総称 19/18 ノンパラメトリックベイズ ディリクレ過程 例)ホップの壷モデル、中華料理店過程 ベータベルヌーイ過程 ディリクレ分布 ベータ分布 ベルヌーイ分布 可測(加速)空間 確率測度 ギブスサンプリング ??? ディリクレ過程混合モデル ほんのはしりを ご紹介
- 20. なにはともあれベイズの定理 加法定理 ? P(X) = ∑YP(X,Y)、P(X) = ∫P(X,Y)dY = ∫f(x,y)dy 乗法定理 ? P(X,Y) = P(Y|X)P(X) ベイズの定理 ? P(X|Y) = P(Y|X)P(X) / P(Y) 20/18
- 21. ディリクレ分布と他の分布の関係 21/18 多項分布二項分布 ディリクレ分布ベータ分布 ? 2つの値のどちらかを取る試行(コ イン投げ)をN回実施した時の、 1(0)の出た回数別の確率分布 ? 確率変数は出た回数(スカラ) ? 複数値のどれか一つを取る試行(複 数目サイコロ)をN回実施した時の、 複数値の出た回数別の確率分布 ? 確率変数はそれぞれの目の出た回 数(ベクトル) ? 二項分布の事前情報無しの事後 確率分布(共役分布) ? 確率変数は事後確率(スカラ) ? 多項分布の事前情報無しの事後 確率分布(共役分布) ? 確率変数は事後確率(ベクトル) N項一般化 N項一般化 確率変数の変換 ベイズ推定 確率変数の変換 ベイズ推定
- 22. ディリクレ過程の一実現例 中華料理店過程(CRP:Chinese Restaurant Process) 22/18 ? 中華料理店の複数のテーブルに順次客が着席していく ? 最初の客は任意のテーブルに着席する ? n(≧2)番目以降の客は以下のルールで着席する ? すでにni(>0)人着席しているテーブルiに着席する確率 ni/(n-1+α) ? 誰も着席していない最も番号の小さなテーブルに着席する確率 α/(n-1+α) テーブル 1 テーブル 2 テーブル 3 5 1 4 2 3
- 23. ディリクレ過程の一実現例 中華料理店過程(CRP:Chinese Restaurant Process) 23/18 ? 特徴 ? 着席順に確率は依存しない ? 着席されるテーブル数は試行とともに増大する ? αの値が大きい程着席テーブル数が多くなり、逆にαの値が小さ いほど着席テーブル数が少なくなって特定のテーブルの着席数が 多くなりやすい
- 24. ディリクレ過程(厳密な定義) 24/18 集合Φとその部分集合を要素とする集合族F からなる可測空間 (Φ, F )の基底分布をG0、集中度パラメータをα(>0)とする。 確率測度Gが、θのいかなる可測な排他的分割 c i=1Ai = θ かつ Ai Aj ＝ φ (i ≠ j) に対しても、r次元確率ベクトル(G(A1),???,G(Ar))がディリク レ分布Dir(αG0(A1) ,???,G0(Ar))に従うときすなわち (G(A1),???,G(Ar)) ～ Dir(αG0(A1) ,???,αG0(Ar)) のとき、かつそのとき限り、Gはディリクレ過程に従うといい G ～ DP(α,G0) と記す。ただしG0(Ai)は、G0から生成されたθが区間Aiに所属 する確率P(θ Ai)を意味する。G(Ai)も同様である。 ? 上記定義を厳密に理解するには、可測空間、確率測度など、 確率論、測度論の知識が必要。
- 25. ディリクレ過程(平易な形) 25/18 分散数および分割の仕方の如何に関わらず、確率ベクトル g = (G(A1),???,G(Ar)) が p(g) = Dir(α1 ,???,αr) αi = αG0(Ai) (i = 1,…, r) を満たすとき、このような確率分布G(θ)を生成する確率過程を ディリクレ過程といい、次のように記す G(θ) ～ DP(α,G0(θ)) G(Ai)の期待値と分散は E[G(Ai)] = E[gi] = αi / α = G0(Ai) V[G(Ai)] )] = V[gi] = αi(α - αi) / α2(α + 1) = G0(Ai)(1 - G0(Ai)) / (α + 1) となる。すなわちDP(α,G0(θ))からG(θ)を生成し、そのG(θ)か ら生成したθが区間Ai 内にある確率gi =G(Ai)の値は、平均とし てαi / α = G0(Ai)となる。また集中度αの値が大きい程、G(Ai) の分散が小さくなってより平均に集中する。
- 26. 正規分布とディリクレ過程の対応 26/18 ? 正規分布に従って生成されるxに対応するのがディリクレ過 程に従って生成されるG(θ) ? 正規分布の平均μと精度1/σ2 がそれぞれG0(θ)とαに対応して いる ? ディルクレ過程は、生成される平均的な分布G0(θ)とその周 りのばらつきの度合いαを定めた分布関数の役割を果たして いる。ディリクレ過程が分布に対する分布と呼ばれるのはこ のような理由による。 正規分布 ディリクレ過程 確率変数 x G(θ) 分布(パラメータ) x ～ N (x; μ,σ2) G(θ) ～ DP(α,G0(θ)) 期待値 μ G0(θ) 精度 1/σ2 α
- 27. 参考資料 1. プログラミングのための線形代数 平岡和幸 堀玄 2. 数学の言葉で世界をみたら 父から娘に贈る数学: 大栗 博司 3. パターン認識と機械学習 C?Mビショップ 4. 続?分かりやすいパターン認識 石井健一郎 上田修功 Illustration by 嫁 27/20