際際滷

際際滷Share a Scribd company logo

Crash Course on Graphical models

Jong Wook Kim
Jong Wook Kim

覿蠍一 CRF螳 一企讌 危危蠍 襴 殊企. Graphical Models 焔 覦レ(Bayesian Networks), 觜覦レ(Markov Random Fields) Graphical Models 譟郁唄覿襴 煙 危ｴ覲願, Generative Discriminative 覈語 谿伎 襴 Discriminative + Undirected 覈碁 Conditional Random Fields襯 螳. 朱 覿 CRF襯 螳 螳.

1 of 65
Crash Course on Graphical Models 2014.08.06 蟾譬
蠏瑚 覘 讌 螳 襾語 覿殊 螳 覦
覲企 襷 蟆 蠍 To gain global insight based on local observations
企至 Representation 語 襯覲 襯覿襦 蠍 P(X1,
油
油,
Xn) 企至 螳蟆 蟾 Directed Graphical Models (Bayesian Networks) Undirected
油赫姻温沿鞄庄界温鉛
油珂看糸艶鉛壊
油(珂温姻一看厩
油檎温稼糸看馨
油酷庄艶鉛糸壊,
油遺檎酷壊,
油
) Learning Maximum Likelihood Estimation, Others? 朱 襷 一危郁 蟾? 朱 襷 螻磯 蟲蟾? 豢襦 Inference 譟郁唄覿 襯 P(Y | X1,
油
油,
Xn) 蟲蠍
覿れ煙 覦朱 豢襦蠍 覿ろ 語 願 磯Μ 80蟾讌 郁規 願 覓伎
油粥鴛
Winter 豕蠏 觜曙 覦 襯 蠏朱朱 企伎
representation learning 豢襦inference 覈 襾殊 螳 螳 蟆曙磯 伎(discrete)襯覲 蟯豸° 覈 (exact) 糾骸 豢襦 蠏碁Μ螻 朱 一(continuous)襯覲 覿覿朱 蟯豸° 覈 (latent/hidden variables) 蠏殊(approximate) 糾骸 豢襦
1. Directed Graphical Models (Bayesian Networks) 2. Undirected Graphical Models (Markov Random Fields) 3. Generative vs Discriminative Models 4. Conditional Random Fields 5. POS Tagging with CRF
蠍磯蓋螳 襯螻糾probability space 襯probability 蟇events 襯覲random variables 襯覿probability distributions 蠍磯螳expectation 襴independence 譬dependence 譟郁唄覿襴conditional independence 譟郁唄覿襯conditional probability 蟆壱襯覿joint probability distribution 一覯豺chain rule 覯伎 襴Bayes Rule 豌危襯 襴Law of Total Probability = () () , = (|) () = ()
Marginal Probability
襯覿: 讌覲 讌 讀(, 蠍一宏, 螳, 蟲)襷 襯覲 讌覲(, 螳, 螳蠍)襷 襯覲 譟郁唄覿襯襦 豢襦inference 蟆朱 讌 螳 p( = 1 | 蠍一宏 = 1 , = 1 , 蟲 = 0 ) Quick Medical Reference (QMR-DT, 1991): 600螳 讌覲螻 4000螳 讀 覈
襯覿襯 覦覯 覈 覲 覈 螳 譟壱 襯 襷り鍵 QMR-DT襯 蠍 譟壱? 24600 : 朱 覿螳ロ (一殊
2250) 覿襯 learnる 豌蟆 襷 一危郁 譟郁唄覿 襯 蟲る 覓 襷 螳 伎
蠏碁蟾 襴曙 伎 襷 覈 覲螳 襦 襴曙企 , , , = (binary 蟆曙) 2 螳 2螳 襷朱 螳 覈 襴曙企 蠏碁れ 碁螳 : 襯 蟆 襯 蟆 覓企 讌 譟郁唄覿襴曙 覲伎!
蠏碁蟾 譟郁唄覿 襴曙 伎 螳 譯殊伎 , , , 襦 譟郁唄覿 襴曙企 , , , , = , , , , = る Na誰ve Bayes Philosophy: 讌 朱 碁 覈語 谿場
Crash Course on Graphical models
Bayesian Network 覦レ 觜 蠏碁directed acyclic graph G(V, E) 螳 碁 襯覲 襯 碁 覿覈碁 Pa() 譟郁唄覿 襯 覿 れ Factorization螻 1:1 , , , =
Crash Course on Graphical models
Crash Course on Graphical models
Bayesian Network 覈generative model 覈語 覃 れ螻 螳 企殊 generate ~() 磯 ろ 覿 襯 蟆一 ~( |) 磯 螳 企ゼ
Bayesian Network 譟郁唄覿 襴曙 蠏碁襦覿 蟆壱襯覿: Chain Rule 伎 覈 襯覿 れ螻 螳 : , | , , |
蠏碁襦 譟郁唄覿 襴
蟆曙 1 : 螳 indirect cause , , = , | = (, , ) () = (|)(|) () = , (, ) ()() = 蠏碁レ X, Y螳 譬, Z螳 譯殊伎覃 X, Y 襴 X, Y 襴螳 覦企 襷谿螳讌
蟆曙 2 : 螻牛 common cause 蠏碁レ X, Y螳 譬, Z螳 譯殊伎覃 X, Y 襴 蟆曙 1螻 equivalent 覈 , , = , | = (, , ) () = (|)(|) () = , (, ) ()() =
蟆曙 3 : 螻牛 螻common effect 蠏碁レ X, Y螳 襴, Z螳 譯殊伎覃 X, Y螳 譬 るジ 語 る伎朱explaining away 螻 , , = () , , , = , (chain rule) = ( , ) ( ) = () (, ) = ()()
Explaining Away X : 讌讌 覦 Y : 螳 豎れ伎 Z : 讌 る
Explaining Away
D-Separation
D-Separation 1
D-Separation 2
Hidden Markov Models is a BN
Bayesian Network 襴 Bayesian Network 襯覲れ 譟郁唄覿襯覿CPD襦 譯殊伎. 覈Generative Model襦 覲 . D-Separation 伎 譟郁唄覿 襴曙 誤 . 轟 蟇伎 殊企 襯 CPD襯 螻燕 蟆朱 詞 . 譟郁唄覿 襯 詞朱る 覯伎 覯豺Bayes Rule 覃 . 豢襦Inference 螻磯 襷 企れ 螳 襷. Viterbi Algorithm, Max-Product Belief Propagation, Sum-Product Algorithm, : Na誰ve Bayes, Hidden Markov Model, Latent Dirichlet Analysis
Crash Course on Graphical models
Undirected Graphical Models 襯覲 伎 覦レ煙 蟆 伎 蟆曙郁 曙 蟆襦 る 覦レ 蟆 一る 覲discriminative覈語 覦レ煙 螳 焔レ 譬 (CRF)
Markov Random Fields 譟郁唄覿襯覿CPD potential 螻煙朱
螳 Markov Random Field
譟郁唄覿 襴 谿剰鍵 | Global Markov Property
Markov Blanket { ()} | () Local Markov Property
Pairwise Markov Property | { } ( ) Pairwise Markov Property
Markov Properties are Equivalent
Moralization : Convert BN to MRF
Factor Graphs
Crash Course on Graphical models
generative VS 覲discriminative 覈
ろ誤磯 ろ語企 Y = 1 , ろ語 覃 Y = 0 ~ : 覈 () 螳 企殊 覃 = 1 , 覃 = 0
蠏碁殊 蟆郁記 螳 襯覿 (, )襯 讌襷 Y襯 豸″蠍 伎 )襷 覃 豢覿 殊曙 蟆曙 () (|)襯 覈 るジ讓 覈語 (|)襷 覃 豢覿! () 伎 螳 譴 朱襷 蟯谿壱 蟆曙 () 伎 螳 覲磯 伎 覲 覈 generative VS 覲discriminative 覈
螳 覈語 伎 蟆 覈語: ( | ( ), )襯 朱誤壱 覦覯 | 手 螳蠍 (Na誰ve Bayes) 覲 覈語: P(Y|)襯 朱誤壱 覦覯 = 1 ; ) = ( ) 手 螳蠍 (Logistic Regression) generative VS 覲discriminative 覈
覲覈語 螳ロ Logistic Regression 譟郁唄覿襴曙 螳讌 bank account豌 螳 願 襷 蠏碁覃 = , 讀 譟郁唄覿襴曙 讌襷 Na誰ve Bayes P( |) = ( |) 襦 覯 豺伎危 譟郁唄覿襴曙 Featureれ 伎 覲企 壱 Feature 螳
焔語 碁 衰 覈 豸′螳ロ 襷 覲覈語 . 酔 朱襷 朱 焔語 P(Y| )襯 螻郁 朱 朱誤磯ゼ 牛 豢覿 譬 蟆郁骸襯 至鍵 碁企 一危一 : Na誰ve Bayes O(log n)螳 Logistic Regression O(n)螳 Na誰ve Bayes螳 (覿 讌襷) 觜襯願 危
Na誰ve Bayes Logistic Regression [Ng Jordan 2002]

More Related Content

Crash Course on Graphical models

  • 1. Crash Course on Graphical Models 2014.08.06 蟾譬
  • 2. 蠏瑚 覘 讌 螳 襾語 覿殊 螳 覦
  • 3. 覲企 襷 蟆 蠍 To gain global insight based on local observations
  • 4. 企至 Representation 語 襯覲 襯覿襦 蠍 P(X1,
  • 5. 油
  • 7. Xn) 企至 螳蟆 蟾 Directed Graphical Models (Bayesian Networks) Undirected
  • 14. 油
  • 15. ) Learning Maximum Likelihood Estimation, Others? 朱 襷 一危郁 蟾? 朱 襷 螻磯 蟲蟾? 豢襦 Inference 譟郁唄覿 襯 P(Y | X1,
  • 16. 油
  • 17. 油,
  • 19. 覿れ煙 覦朱 豢襦蠍 覿ろ 語 願 磯Μ 80蟾讌 郁規 願 覓伎
  • 21. Winter 豕蠏 觜曙 覦 襯 蠏朱朱 企伎
  • 22. representation learning 豢襦inference 覈 襾殊 螳 螳 蟆曙磯 伎(discrete)襯覲 蟯豸° 覈 (exact) 糾骸 豢襦 蠏碁Μ螻 朱 一(continuous)襯覲 覿覿朱 蟯豸° 覈 (latent/hidden variables) 蠏殊(approximate) 糾骸 豢襦
  • 23. 1. Directed Graphical Models (Bayesian Networks) 2. Undirected Graphical Models (Markov Random Fields) 3. Generative vs Discriminative Models 4. Conditional Random Fields 5. POS Tagging with CRF
  • 24. 蠍磯蓋螳 襯螻糾probability space 襯probability 蟇events 襯覲random variables 襯覿probability distributions 蠍磯螳expectation 襴independence 譬dependence 譟郁唄覿襴conditional independence 譟郁唄覿襯conditional probability 蟆壱襯覿joint probability distribution 一覯豺chain rule 覯伎 襴Bayes Rule 豌危襯 襴Law of Total Probability = () () , = (|) () = ()
  • 26. 襯覿: 讌覲 讌 讀(, 蠍一宏, 螳, 蟲)襷 襯覲 讌覲(, 螳, 螳蠍)襷 襯覲 譟郁唄覿襯襦 豢襦inference 蟆朱 讌 螳 p( = 1 | 蠍一宏 = 1 , = 1 , 蟲 = 0 ) Quick Medical Reference (QMR-DT, 1991): 600螳 讌覲螻 4000螳 讀 覈
  • 27. 襯覿襯 覦覯 覈 覲 覈 螳 譟壱 襯 襷り鍵 QMR-DT襯 蠍 譟壱? 24600 : 朱 覿螳ロ (一殊
  • 28. 2250) 覿襯 learnる 豌蟆 襷 一危郁 譟郁唄覿 襯 蟲る 覓 襷 螳 伎
  • 29. 蠏碁蟾 襴曙 伎 襷 覈 覲螳 襦 襴曙企 , , , = (binary 蟆曙) 2 螳 2螳 襷朱 螳 覈 襴曙企 蠏碁れ 碁螳 : 襯 蟆 襯 蟆 覓企 讌 譟郁唄覿襴曙 覲伎!
  • 30. 蠏碁蟾 譟郁唄覿 襴曙 伎 螳 譯殊伎 , , , 襦 譟郁唄覿 襴曙企 , , , , = , , , , = る Na誰ve Bayes Philosophy: 讌 朱 碁 覈語 谿場
  • 32. Bayesian Network 覦レ 觜 蠏碁directed acyclic graph G(V, E) 螳 碁 襯覲 襯 碁 覿覈碁 Pa() 譟郁唄覿 襯 覿 れ Factorization螻 1:1 , , , =
  • 35. Bayesian Network 覈generative model 覈語 覃 れ螻 螳 企殊 generate ~() 磯 ろ 覿 襯 蟆一 ~( |) 磯 螳 企ゼ
  • 36. Bayesian Network 譟郁唄覿 襴曙 蠏碁襦覿 蟆壱襯覿: Chain Rule 伎 覈 襯覿 れ螻 螳 : , | , , |
  • 38. 蟆曙 1 : 螳 indirect cause , , = , | = (, , ) () = (|)(|) () = , (, ) ()() = 蠏碁レ X, Y螳 譬, Z螳 譯殊伎覃 X, Y 襴 X, Y 襴螳 覦企 襷谿螳讌
  • 39. 蟆曙 2 : 螻牛 common cause 蠏碁レ X, Y螳 譬, Z螳 譯殊伎覃 X, Y 襴 蟆曙 1螻 equivalent 覈 , , = , | = (, , ) () = (|)(|) () = , (, ) ()() =
  • 40. 蟆曙 3 : 螻牛 螻common effect 蠏碁レ X, Y螳 襴, Z螳 譯殊伎覃 X, Y螳 譬 るジ 語 る伎朱explaining away 螻 , , = () , , , = , (chain rule) = ( , ) ( ) = () (, ) = ()()
  • 41. Explaining Away X : 讌讌 覦 Y : 螳 豎れ伎 Z : 讌 る
  • 47. Bayesian Network 襴 Bayesian Network 襯覲れ 譟郁唄覿襯覿CPD襦 譯殊伎. 覈Generative Model襦 覲 . D-Separation 伎 譟郁唄覿 襴曙 誤 . 轟 蟇伎 殊企 襯 CPD襯 螻燕 蟆朱 詞 . 譟郁唄覿 襯 詞朱る 覯伎 覯豺Bayes Rule 覃 . 豢襦Inference 螻磯 襷 企れ 螳 襷. Viterbi Algorithm, Max-Product Belief Propagation, Sum-Product Algorithm, : Na誰ve Bayes, Hidden Markov Model, Latent Dirichlet Analysis
  • 49. Undirected Graphical Models 襯覲 伎 覦レ煙 蟆 伎 蟆曙郁 曙 蟆襦 る 覦レ 蟆 一る 覲discriminative覈語 覦レ煙 螳 焔レ 譬 (CRF)
  • 50. Markov Random Fields 譟郁唄覿襯覿CPD potential 螻煙朱
  • 52. 譟郁唄覿 襴 谿剰鍵 | Global Markov Property
  • 53. Markov Blanket { ()} | () Local Markov Property
  • 54. Pairwise Markov Property | { } ( ) Pairwise Markov Property
  • 55. Markov Properties are Equivalent
  • 60. ろ誤磯 ろ語企 Y = 1 , ろ語 覃 Y = 0 ~ : 覈 () 螳 企殊 覃 = 1 , 覃 = 0
  • 61. 蠏碁殊 蟆郁記 螳 襯覿 (, )襯 讌襷 Y襯 豸″蠍 伎 )襷 覃 豢覿 殊曙 蟆曙 () (|)襯 覈 るジ讓 覈語 (|)襷 覃 豢覿! () 伎 螳 譴 朱襷 蟯谿壱 蟆曙 () 伎 螳 覲磯 伎 覲 覈 generative VS 覲discriminative 覈
  • 62. 螳 覈語 伎 蟆 覈語: ( | ( ), )襯 朱誤壱 覦覯 | 手 螳蠍 (Na誰ve Bayes) 覲 覈語: P(Y|)襯 朱誤壱 覦覯 = 1 ; ) = ( ) 手 螳蠍 (Logistic Regression) generative VS 覲discriminative 覈
  • 63. 覲覈語 螳ロ Logistic Regression 譟郁唄覿襴曙 螳讌 bank account豌 螳 願 襷 蠏碁覃 = , 讀 譟郁唄覿襴曙 讌襷 Na誰ve Bayes P( |) = ( |) 襦 覯 豺伎危 譟郁唄覿襴曙 Featureれ 伎 覲企 壱 Feature 螳
  • 64. 焔語 碁 衰 覈 豸′螳ロ 襷 覲覈語 . 酔 朱襷 朱 焔語 P(Y| )襯 螻郁 朱 朱誤磯ゼ 牛 豢覿 譬 蟆郁骸襯 至鍵 碁企 一危一 : Na誰ve Bayes O(log n)螳 Logistic Regression O(n)螳 Na誰ve Bayes螳 (覿 讌襷) 觜襯願 危
  • 67. Conditional Random Fields 襯覲 襦 企伎 Markov Network 企 一螳 譟危 MRF 覈 覲 讌襷 企 Y襦襷
  • 68. CRF 襷り覲parameterization f (x, y ) Feature vector tion朱 蟇 譯朱 覈願 覓語襦 蟇 螻覈蟆 焔奄 w れ 覦覯 牛 牛伎
  • 69. : 谿disparity 豸′ ()襯 螻ろ讌 蟆 豐 企 蠏碁殊 れ伎讌 朱蟾
  • 70. : Named Entity Recognition Skip Chain CRF ( , ) : 語 企 伎 蟯螻 ( , ) : ′ ≠賀 螳 願 煙ロ 蟆曙 ( , ) : 豌伎 譟危 Feature
  • 71. Roadmap 襯覈碁 representation蠍 Bayesian Network Markov Random Field Conditional Random Field 豢襦inference蠍 Variable Elimination 碁Μ蟲譟一 蠏碁 message passing朱 豢襦蠍 Dual Decompositon 牛 MAP 豢襦 Variational Methods Monte Carlo Methods learn蠍 Bayesian Network 朱誤 豢 Markov Random Field 朱誤 豢 覿 一危磯覿 牛蠍 (EM Algorithm) Structured Learning
  • 74. CRF襦 覿蠍 x : 覓語 y = , , , ,, # , # : 螳ロ 郁骸 POS 譟壱 (x) : 覓語 x 螳ロ 覈 蟆暑 讌 覈: (x) 譴 覦襯 蟆暑 y襯 谿剰鍵
  • 77. 覿 CRF 覈
  • 79. ML Paramter Estimation : Forward-Backward Algorithm
  • 80. ML Parameter Estimation : Regularization Regularization Occams Razor襦 殊 Prior 螳 企 襷 螳譴豺襯 蟆郁骸 L1-norm螻 L2-norm 谿 L1-norm 蠏麹 朱 Feature る relevant 蟆郁骸 L2-norm 蟇一 覈 Featureれ relevantる 蟆郁骸
  • 82. References On Discriminative vs. Generative classi鍖ers: A comparison of logistic regression and naive Bayes (Ng Jordan 2001) Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data (Lafferty et. al. 2001) Applying Conditional Random Fields to Japanese Morphological Analysis (Kudo et. al. 2004)