π Markov Model
@ Adjancency List
@ λ΄ μ΄μ μ μνλ μ¬μ©νμ§ μλλ€, μ§κΈ μνλ§μ κ°μ§κ³ λ€μ μνλ₯Ό μμΈ‘νλ€ (μ§κΈ μ΄μ μνλ λͺ¨λ 무μ)
@ ν
μ€νΈ μμ±μ μν Markov Chainsμ Bigram λͺ¨λΈ
. Markov Chainsλ μ² μ κ²μ¬λΆν° μλ €μ§μ§ μμ μνμ μ μ νμΈμ μ΄λ₯΄κΈ°κΉμ§ λ€μν μμ© λΆμΌμμ μ¬μ©λ μ μμ. ν₯λ―Έλ‘μ΄ λ¬Έκ΅¬λ₯Ό λ°©μΆνλ Bigram ν
μ€νΈ μμ±κΈ°μ ꡬν. μμ± μΈμκ³Ό ν
μ€νΈ λ° μμ
λͺ¨λΈλ§μ μμ©
π« Markov Model (Markov Chain)
Markov Model (νΉμ Markov Chain) λ¬μμ μνμμΈ μλλ μ΄ λ§λ₯΄μ½λΈ(Andrei Markov)μ λ°μ λͺ λͺ λμλ€.
μ΄ λͺ¨λΈλ€μ μ¬λ¬ μνλ₯Ό ν¬ν¨ν νλ‘μΈμ€μ, μ΄ μνλ€μ ν΅κ³Όνλ κ²½λ‘λ€κ³Ό κ΄λ ¨λ νλ₯ λ€μ λ¬μ¬/μ€λͺ νλλ° μμ£Ό μ μ©νλ€.
𫧠_
Markov Chainμ λ¨μν μνλ€ κ°μ μ μ΄μ νλ₯ μ΄ λΆμ¬λ μ¬λ¬ μνλ€λ‘ ꡬμ±λ νλ‘μΈμ€
λ€.
@ μμ - λ¨μ΄ λ°μ 체μΈ
βTomorrowβ λ¨μ΄μ λ°μμ 보μ¬μ€λλ€. λ€μ΄μ΄κ·Έλ¨μμ λ κ°μ§ κ°λ₯ν λ°μμ μ¬μ©ν μ μμ΅λλ€. βTahmorrowβμ΄λΌλ λ체 λ°μμ νλ₯ μ΄ λν 0.5μΈ λ°λ©΄, βTuwmorrowβμ΄λΌλ λ°μμ νλ₯ μ 0.5μ λλ€.
μ΄κ²μ μ²΄μΈ λ΄μ ν μ§μ μμμ κ²°μ μ ν¬ν¨νλ λ§€μ° κ°λ¨ν κ²½μ°μ
λλ€. κ° μνλ μμ(phoneme)μ μμ±μ ν¬ν¨ν©λλ€.
체μΈμ λμμ μμ±λ λ°μμ μ¬μ©ν μ μμ΅λλ€.
@ μμ - μ€νΈ λ©μΌ 체μΈ
μ°λ¦¬λ μμ© νλ‘κ·Έλ¨ μΉμ μμ μ΄κ²μ λͺ©μ μ λ μμΈν μ΄ν΄λ³Ό κ²μ λλ€. λ€μμΌλ‘, λ€λ₯Έ μμ© νλ‘κ·Έλ¨μ μ΄ν΄λ΄ μλ€. μ¬μ©μμ νλμ λͺ¨λν°λ§νλ μ΄λ©μΌ νλ‘κ·Έλ¨μ μκ°ν΄ 보μΈμ. μ΄λ©μΌμ΄ λμ°©νλ©΄, κ·Έκ²μ μ¬μ©μκ° μ΄λ©μΌλ‘ 무μμ νλμ§ κ΄μ°°νκ³ μ΄ μ 보λ₯Ό μ¬μ©νμ¬ λ€μ μ΄λ©μΌμ μλμΌλ‘ μ²λ¦¬νλ λ°©λ²μ λ°°μλλ€. κ·Έλ¦Ό 10μ 체μΈμ 보μΈμ.
μ°λ¦¬μ μ΄λ©μΌ μμ΄μ νΈλ 10κ° μ€ 8κ°κ° μ€νΈμ΄κ³ , 10κ° μ€ 2κ°κ° μ¬μ©μ βdankβμ μ΄λ©μΌμμ νμΈνμ΅λλ€. λν μ΄λ©μΌ μμ΄μ νΈλ μ°λ¦¬κ° μ€νΈ μ΄λ©μΌμ μ½μ§ μκ³ μμ νλ κ²½μ°κ° 80%λΌλ κ²μ νμΈνμ΅λλ€. λλ¨Έμ§ 20%λ μ°λ¦¬κ° μ΄λ©μΌμ μ½μμ΅λλ€. μ΄λ¬ν νλ₯ λ‘ μ΄λ©μΌ μμ΄μ νΈλ μ°λ¦¬κ° μ΄λ©μΌμ μ½λ κ²λ³΄λ€ κ·Έκ²μ μμ ν κ°λ₯μ±μ΄ λ λλ€λ κ²μ μΆλ‘ ν μ μμ΅λλ€. μ΄λ©μΌ μμ΄μ νΈλ μ΄λ¬ν νλ₯ μ μ¬μ©νμ¬ μ΄λ©μΌ κ΄λ¦¬ μμ μ λ¨μνν μ μλ κΈ°νλ₯Ό μ 곡ν©λλ€.
ν. μ¬κΈ°μ νμλ μμ μμλ μ νλ μμ μνμ μ°κ²°μ μ μνμ΅λλ€. Markov Chainsμ λ§€μ° λ³΅μ‘ν νλ‘μΈμ€λ₯Ό λͺ¨λΈλ§νκΈ° μν΄ λ§€μ° λ§μ μμ μ°κ²°λ‘ λ§€μ° ν° μν 곡κ°μ μ§μν μ μμ΅λλ€.
λ μμ μ ν₯λ―Έλ‘μ΄ νΉμ±μ μ°κ²° νλ₯ μ΄ μ£Όμ΄μ§λ©΄ νμ¬ μνλ νμ μ΄μ μνμ ν¨μλΌλ κ²μ
λλ€. μ΄λ₯Ό "λ§λ₯΄μ½ν μμ±"
μ΄λΌκ³ ν©λλ€. λν μ°λ¦¬μ μμ μμ λ κ° μ΄μμ μ΄μ μν(μλ₯Ό λ€μ΄ μ€νΈ λ©μΌ 체μΈμ βμ½κΈ°β μν)μ λλ¬ν μ μμΌλ―λ‘ μ΄λ¬ν λͺ¨λΈμ μλ λ§λ₯΄μ½ν λͺ¨λΈ(Hidden Markov Models, HMMs)
λλ μλ Markov Chains(Hidden Markov Chains)
μ΄λΌκ³ ν©λλ€.
𫧠HMM Approximations
μ΄μ μμμ 체μΈμ νμ¬ μνλ μ μλ νλ₯ μ κ°μ§ 체μΈμ μ΄μ μνλ§μ ν¨μμμ΅λλ€. μ΄λ₯Ό Bi-gram (λ λ¨μ΄μ μνμ€)
μ΄λΌκ³ ν©λλ€. νμ¬ μνκ° μ΄μ μνμ ν¨μκ° μλλΌλ©΄ μν μ νμ λ¨μν 무μμ νλ‘μΈμ€μΌ κ²μ
λλ€.
μνκ° μ΄μ λ μνμ μμ‘΄μ μ΄λΌλ©΄ Tri-gram (μΈ λ¨μ΄μ μνμ€)
μ΄λΌκ³ ν κ²μ
λλ€.
μ΄μ μν(λλ 컨ν μ€νΈ)μ λν μμ‘΄μ±μ λμ΄λ©΄ 체μΈμ Useabilityλ₯Ό λμΌ μ μμ§λ§(μμ© νλ‘κ·Έλ¨ μΉμ μμ λ³Ό μ μλ―μ΄), μ΄λ¬ν λͺ¨λΈμ λ©λͺ¨λ¦¬ μꡬ μ¬νμ μ΅μ μ /μ νμ (Inhibitive)μΌ μ μμ΅λλ€.
i.e. 100κ° λ¨μ΄μ μ΄νμ νμν μμμ μλ μλμ κ°μ΅λλ€.
n | Type | Number of Elements |
2 | Bigram | 10,000 |
3 | Trigram | 1,000,000 |
4 | 4-gram | 100,000,000 |
Bigram (λ λ¨μ΄ μνμ€) = 100^2 = 10,000
Trigram (μΈ λ¨μ΄ μνμ€) = 100^3 = 1,000,000
4-gram (λ€ λ¨μ΄ μνμ€) = 100^4 = 100,000,000
100κ°μ κ³ μ λ¨μ΄λ‘ ꡬμ±λ λ§λμΉλ μλΉν μκΈ° λλ¬Έμ, λ§λμΉμ Bigram μ΄μΈμ κ²μ λ§λλ κ²μ μλΉν λΉμ©μ΄ λ§μ΄ λ€ μ μμ΅λλ€. (λ λ§μ κ³ μ λ¨μ΄λ₯Ό μΈμλ‘ λ³Όλ§ν λ¬Έμ₯μ΄ λμ€λλ°, Trigramμ΄λ 4-gramμ μ°λ©΄ λ¨μ§ 100 λ¨μ΄λ§ μ¨λ λ§λ€μ΄μ§λ κ² λ§μ. λ¨μ΄ μλ₯Ό λ릴μλ‘ κΈ°νκΈμμ μΌλ‘ μ¦κ°)
(λλ¬Έμ Bigramμ μ, μ΅μν μ΄ κΈμ μμ μ μμ΄μλ)
π« μμ© - Interesting Applications
μ΄μ HMMsλ₯Ό μν Markov Chainsμ€μ λͺ κ°μ§ μμ© μ¬λ‘λ₯Ό μ΄ν΄λ³΄κ² μ΅λλ€. 첫 λ²μ§Έ μμΈ μμ± μΈμμ μμ°μ΄ μ²λ¦¬μμ μ¬μ©λλ λ¨μ΄λ₯Ό κ²°μ νλ λ° μ¬μ©λλ μ€μ©μ μΈ λ°©λ²μ λλ€. λ€μ λ κ°μ§ μλ μ μ©νλ€κ³ μκ°λ기보λ€λ μκ·Ήμ μ΄μ§λ§ Markov Chainsμ€μ κ°λ₯μ±μ λν λ ν° μ΄ν΄λ₯Ό μ 곡ν©λλ€.
𫧠μμ± μΈμ - Speech Recognition
κ·Έλ¦Ό 10.1μμ λ¨μ΄μ λ°μμ΄ νμμ λ°©μΈ λλ κΈ°μμ λ°λΌ νλ μ΄μμ λ³νμ κ°μ§ μ μμμ κΈ°μ΅νμΈμ. κ·Έλ¬λ©΄ μμ± μΈμ μμ€ν μ ꡬμΆνλ κ²μ΄ λ§€μ° μ΄λ €μμ§λλ€. μλνλ©΄ κ·Έ μμ€ν μ μ£Όμ΄μ§ λ¨μ΄μ λ€μν λ°μμ μ²λ¦¬ν΄μΌ νκΈ° λλ¬Έμ λλ€.
HMCλ μμ±μ μμλ₯Ό νλ₯ μ μΌλ‘ νμ±ν¨μΌλ‘μ¨ μμ± μΈμ μμ€ν μ λ¨μνν μ μλ κΈ°νλ₯Ό μ 곡ν©λλ€. μλ₯Ό λ€μ΄, μμ± μμ€ν μ΄ μμμ λ¨μ΄λ₯Ό μ΄ν΄νλλ‘ μ€κ³λμλ€κ³ κ°μ ν΄ λ΄ μλ€. μμ€ν μ΄ βtahβ μμλ₯Ό μ²μ λ€μμ λ, μμ± λ¨μ΄λ βtomorrowβ λλ βtodayβ μ€ νλκ° λ μ μμ΅λλ€. μμ±μμ νμ±λ λ€μ μμλ βmβμΈλ°, μ§κΈ λ§νλ λ¨μ΄κ° βtodayβμΌ νλ₯ μ 0μ λλ€. μ°λ¦¬μ HMMμ κ°μν λ, βmβ μμλ ν©λ²μ μΈ μνμ΄λ―λ‘, μ°λ¦¬λ μ ννκ³ λ€μ μμλ₯Ό μ²λ¦¬ν©λλ€. μ νν νλ₯ μ κ°μν λ, μμ± μΈμκΈ°λ μ΄λ€μ μ¬μ©νμ¬ μ²΄μΈμ ν΅ν΄ κ°μ₯ κ°λ₯μ± μλ κ²½λ‘λ₯Ό μ ννμ¬ κ°μ₯ κ°λ₯μ± μλ μμλ₯Ό μλ³ν μ μμ΅λλ€.
μ΄ μλ μμμμ λ¨μ΄λ‘ νμ₯λ μ μμ΅λλ€. μμ± μΈμκΈ°κ° μ΄ν΄ν μ μλ λ¨μ΄ μ§ν©μ΄ μ£Όμ΄μ§λ©΄, μ£Όμ΄μ§ λ¨μ΄κ° λ€λ₯Έ λ¨μ΄ λ€μ μ¬ νλ₯ μ μλ³νλ Markov Chainμ΄ μμ±λ μ μμ΅λλ€. μ΄λ₯Ό ν΅ν΄ μΈμκΈ°λ λ¬Έλ§₯μ λ°λΌ μ΄λ€ λ¨μ΄κ° λ°νλμλμ§ λ μ μλ³ν μ μμ΅λλ€(κ·Έλ¦Ό 10.3 μ°Έμ‘°).
@ μμ -
μ΄λ¬ν μλ₯Ό ν΅ν΄ HMMμ μμ± μΈμ λ° μμ± μ΄ν΄μ κ°μ μμ μ ν¬κ² λ¨μνν μ μμμ΄ λΆλͺ ν©λλ€. μ΄ μμμ μμ μ λ ₯μ λ¨μ΄λ₯Ό μ μνκΈ° μν΄ λͺ¨λΈ λ΄ μνμ μ νμ μ λ°νμ΅λλ€. λν λ¨μ΄ μ λ ₯μ λ¬Έμ₯μ λ§₯λ½μ μ΄ν΄λ₯Ό μν μ νμ μ λ°νμ΅λλ€. λ€μμΌλ‘, μ°λ¦¬λ 미리 μ μλκ±°λ νμ΅λ μ ν νλ₯ μ κΈ°μ΄νμ¬ μ¬λ³Όμ μμ±νλ HMMμ μ¬μ©μ μ΄ν΄λ³Ό κ²μ λλ€.
𫧠Modeling Text
@ U κΈ°λ§κ³ μ¬ μΆμ : μ£Όμ΄μ§ λ§λμΉμ λνμ¬, λ§λ₯΄μ½ν νλ ¬μ λ§λ€μ΄ κ·Έλ¦¬κ³ , μ΄λ₯Ό μ΄λ»κ² νμ©ν μ μλμ§ μ€λͺ νμμ€.
I have a dream You have the dream We have dream
β μ΄μ λ¨μ΄ λ€μμ λμ€λ λ¨μ΄ λΉλ ν
β First word, Second word
β μ΄λ₯Ό λ°νμΌλ‘ λ¬Έμ₯ μμ± (λλ€ν μλ/λ¨μ΄λ₯Ό κ°μ§κ³ λ€μμ λμ¬ λ¨μ΄ μμΈ‘)
β νλ₯ μ λ°νμΌλ‘ νκΈ° λλ¬Έμ, κ°μ μ§λ¬Έμ ν΄λ λ€λ₯Έ λ΅μ΄ λμ¨λ€
μμ μμμ Markov Chainμ νμ¬ μνμ μΈλΆ μκ·Ήμ΄ μ£Όμ΄μ‘μ λ λ€μ μνλ₯Ό νλ₯ μ μΌλ‘ μλ³νλ λ° μ¬μ©λμμ΅λλ€. μ΄μ μΈλΆ μκ·Ήμ΄ μ 곡λμ§ μλ λͺ κ°μ§ μλ₯Ό μ΄ν΄λ΄ μλ€. Markov Chain μ μν κ°μ μ μ΄λ 무μμ κ³Όμ μΌλ‘ μ μλ νλ₯ μλ§ κΈ°λ°ν©λλ€.
κ·Έλ¦Ό 10.4μμλ λ κ°μ μν λ¬Έμ₯μ λν Markov Chainμ μλ₯Ό 보μ¬μ€λλ€. Markov Chainμ μ΄ λ λ¬Έμ₯μ κ³±μΌλ‘, Bigram λͺ¨λΈμ μ¬μ©ν©λλ€.
@ μμ -
μ΄ λ§λμΉ λ΄μμ μ μΌνμ§ μμ λ¨μ΄λ βisβμ λλ€. κ³ λ₯Έ νλ₯ λ‘ βisβλΌλ λ¨μ΄λ βaβ λλ βtheβλΌλ λ¨μ΄λ‘ μ΄μ΄μ§ μ μμ΅λλ€. μ΄μ μ΄κ²μ΄ Markov ChainμΌλ‘ μμ±λ μ μλ λ€ κ°μ κ°λ₯ν λ¬Έμ₯μΌλ‘ μ΄μ΄μ§λ€λ κ²μ μ£Όλͺ©νμμμ€(κ·Έλ¦Ό 10.4μ νλ¨μ νμλ¨).
𫧠Modeling Music
λ¨μ΄μ μ μ¬ν λ°©μμΌλ‘, μ£Όμ΄μ§ μ곑κ°μ μν μ΄νλ‘λΆν° HMMμ νλ ¨μν€λ κ²μ κ³ λ €ν΄λ³΄μΈμ. κ·Έλ¦¬κ³ λμ HMMμ μ£Όμ΄μ§ μ곑κ°μ μ€νμΌμ κ°μ§ μνλ€μ νλ₯ μ μΈ μμ±μ ν΅ν΄ κ΅ν₯곑μ μ곑νλλ° μ¬μ©λ μ μμ΅λλ€. λ λͺ μ΄μμ μ곑κ°λ€μ μ΄νλ‘λΆν° HMMμ νλ ¨μν€λ κ²λ κ³ λ €ν΄λ³΄μΈμ. μΆ©λΆν ν° n-gramμΌλ‘, νλ₯ν μ곑κ°λ€μ μ‘°ν©μΌλ‘λΆν° κ΅ν₯곑λ€μ νΈκ³‘ν μ μμ΅λλ€.
@ κ΅μλκ»μ 보μ¬μ£Όμ μμ
π« Bigram Sample Application
μ΄λ€ μ¬λλ€μ HMMμ λ λμ κ·Όμ¬μΉλ₯Ό μ¬μ©νμ¬ μ
°μ΅μ€νΌμ΄μ κ°μ μλν μκ°λ€μ μνμ λͺ¨λ°©
νλ κ²μ΄ κ°λ₯ν μ μλ€κ³ μ μν©λλ€. μ μμ ν
μ€νΈ λ§λμΉλ‘ HMMμ νλ ¨μν΄μΌλ‘μ¨, HMMμ νλ ¨ λ§λμΉλ‘λΆν° ν΅κ³μ μΌλ‘ μ μ¬ν λ¨μ΄λ€μ μνμ€λ₯Ό λ°©μΆ(Emit)νλ λ° μ¬μ©λ μ μμ΅λλ€.
μν μ΄ν리μΌμ΄μ μ κ²½μ° μμμ ν μ€νΈλ‘ νλ ¨ν μ μλ λΉ λ¨ HMMμ ꡬνμ λν΄ λ Όμν κ²μ λλ€. κ·Έλ° λ€μ HMMμ μ¬μ©νμ¬ μμμ λ¬Έμ μνμ€λ₯Ό μμ±ν κ²μ λλ€.
@ μμ -
κ·Έλ¬λ©΄ Bigram λ°°μ΄μ νμ±κ³Ό μ±μ°κΈ°κ° λλ©λλ€. λ€μ λ ν¨μλ Bigram λ°°μ΄μ λͺ¨λΈλ‘ λ¬Έμ₯μ λ°©μΆνλ κΈ°λ₯μ μ 곡ν©λλ€.
ν¨μ βbuild Sentenceβλ βsumVectorβ λ°°μ΄μ μ¬μ©νμ¬ βbigramArrayβ ꡬ쑰λ₯Ό ν΅ν΄ μ΄λ€ κ²½λ‘λ₯Ό μ νν μ§ κ²°μ ν©λλ€
@ ꡬν λ° μ€ν
π« Ownership?
Markov Chainsμ λ€λ₯Έ λ¬Ένλ€κ³Ό λΉμ·νκ² λνλλ κ΅ν₯곑, μ¦ ν μ€νΈμ μμ±μ λͺ¨λ°©νλ λ° μ¬μ©λ μ μμ§λ§, κ³Όμ° μλ‘μ΄ μνμ μμ μλ λꡬμΈκ° νλ μλ¬Έμ΄ λλλ€. Markov Chainsμ μλ νλ ¨ λ°μ΄ν°λ₯Ό λ³Έλ λ§λ μμ μ΄λ ν μ€νΈλ₯Ό λ°©μΆ(Emit)ν μ μμ΅λλ€. λ°λΌμ κ·Έ κ²°κ³Όλ μμμμ μνκ³Ό λ§€μ° μ μ¬νμ§λ§, κ·Έκ²μ μμμ μλ‘μ΄ ν΅κ³μ ννμ λλ€.
Trigram μ΄μμ λͺ¨λΈμ μ¬μ©νμ¬ μλ³Έ μμ μ λͺ¨λΈλ§νλ©΄ κ²°κ³Ό μμ μ 볡μ‘μ±κ³Ό μΌκ΄μ±μ΄ λ§€μ° ν₯λ―Έλ‘μΈ κ²μ λλ€.