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 이상의 모델을 사용하여 원본 작업을 모델링하면 결과 작업의 복잡성과 일관성이 매우 흥미로울 것입니다.