Hidden Markov Model

 

 

[Hidden Markov Model ]




1. Tujuan 


a. Memahami apa itu Hidden Markov Model.
b. Mencari implementasi Hidden Markov Model


 2. Alat dan Bahan





3. Materi


A. Apa itu Hidden Markov Model.


Hidden Markov Model (HMM) adalah salah satu varian supervised learning,7 diberikan sekuens input dan output yang bersesuaian sebagai training data. Pada kasus POS tagging, yaitu input -nya adalah sekuens kata dan output -nya adalah sekuens kelas kata (masing-masing kata/token berkorespondensi den- gan kelas kata).

Saat melatih HMM, kita ingin mengestimasi parameter A dan b yaitu transition probabilities dan emission probabilities. 

B. Probabilistic Reasoning


Pada logika matematika (first order logic), ketika kita memiliki premis “bila hujan, maka ayu terpeleset.” Pada level first order logic, apabila “hujan” ter-jadi, maka “terpeleset” juga pasti akan terjadi. Tetapi tidak sebaliknya, apa- bila kita “terpeleset”, belum tentu “hujan” juga terjadi. Pada probabilistic reasoning kita mengkuantifikasi kepastian atau ketidakpastian itu. Apabila “hujan” terjadi, berapa besar kemungkinan “terpeleset” juga terjadi (dan sebaliknya).

Hal ini disebut Bayesian network



Gambar ini menerangkan hubungan pengkon- disian events, disebut Bayesian Network. Panah dari  “hujan”  ke  “terpe- leset” merepresentasikan bahwa “hujan” adalah kondisi yang menyebabkan “terpeleset” terjadi (causality ).

Dalam Bayesian network maka terbagi :




  1. Serial. Bila kita mengetahui A maka kita bisa mengetahui sesuatu tentang B dan C. Tetapi apabila kita mengetahui B, mengetahui A tidak akan membantu inferensi kita terhadap C. Mengetahui C akan membuat kita mengetahui sesuatu tentang A ketika kita tidak mengetahui B. Artinya, hubungan antara A dan C di-block ketika B diketahui. 
  2. Diverging. Bila kita mengetahui A maka kita bisa mengetahui sesuatu tentang C, dan sebaliknya. Tetapi apabila B diketahui, maka hubungan antara A dan C menjadi terputus. Dengan bahasa lebih matematis, A dan C independen kondisional ketika B diketahui.
  3.  Converging. Tanpa mengetahui B, kita tidak bisa mencari tahu hubungan antara A dan C. Dengan bahasa lebih matematis, A dan C dependen kondisional ketika B diketahui.

Hubungan antara serial, diverging dan converging bisa dilihat di gambar ini:


C. Generative model


generative model memodelkan p(x, y). Per- samaan itu dapat difaktorkan sebagai p(x, y) = p(y    x)p(x).  sementara Pada supervised learning   kita memodelkan p(y x), memodelkan target y (label) ketika diberikan input x,2 yaitu mencari tahu decision boundary antara keputusan. x dan y dapat berupa vektor, skalar, gambar, dan lain sebagainya. Sementara pada unsupervised learning, kita ingin mengaproksimasi distribusi asli dari sebuah input sebagai p(x)

D. POS Tagging


POS tagging adalah salah satu bentuk pekerjaan sequential  classifi- cation. Diberikan sebuah sekuens kata (membentuk satu kalimat), kita in- gin menentukan kelas setiap kata/token pada kalimat tersebut. Kita ingin memilih sekuens kelas kata syntactic categories yang paling cocok untuk kata- kata/tokens pada kalimat yang diberikan. Secara formal, diberikan sekuens kata-kata w1, w2, . . . , wT , kita ingin mencari sekuens kelas kata c1, c2, . . . , cT sedemikian sehingga kita memaksimalkan nilai probabilitas


contoh:

diberikan sebuah kalimat “Budi/Noun menendang/Verb bola/Noun” “Budi menendang bola”. Sete- lah proses POS tagging, kamu akan mendapat (Gambar 8.4).

 


 

POS tagging adalah salah satu bentuk pekerjaan sequential  classifi- cation. Diberikan sebuah sekuens kata (membentuk satu kalimat), kita in- gin menentukan kelas setiap kata/token pada kalimat tersebut. Kita ingin memilih sekuens kelas kata syntactic categories yang paling cocok untuk kata- kata/tokens pada kalimat yang diberikan. Secara formal, diberikan sekuens kata-kata w1, w2, . . . , wT , kita ingin mencari sekuens kelas kata c1, c2, . . . , cT sedemikian sehingga kita memaksimalkan nilai probabilitas

kata sangat sulit untuk didaftar/sangat banyak). Teori Bayes digunakan untuk melakukan aproksimasi permasalahan ini. Ingat kembali teori Bayes seperti




E. Hidden Markov Model Tagger


Markov chain adalah kasus spesial weighted automaton yang mana sekuens input menentukan states yang akan dilewati oleh automaton. Sederhananya, automaton mencapai goal states setelah mengunjungi berbagai states. Total bobot outgoing edges untuk masing - masing state pada automaton haruslah bernilai satu apabila dijumlahkan kasus spesial yang yang dimaksud adalah emission.

        Sebagai Contoh pada gambar. ART adalah article, N adalah noun, V adalah verb dan P adalah preposition. Mereka adalah contoh kelas kata yang disederhanakan demi membuat contoh yang mudah. Tabel dibawah mempresentasikan probabilitas kelas kata, ketika dikonversi menjadi weighted automaton.



        

        
    Tabel dan Gambar diatas merepresentasikan probabilitasa prior, sekarang kitang ingin model yang kita punya juga mencakup lexical emission probabilities, yaitu likelihood pada persamaan Lexical emission probabilities dibawah.

    


        Seumpama kita mempunyai lexical emission probabilities seperti pada tabel. Setiap state pada automaton, dapat menghasilkan/meng-outputkan suatu kata (word) dengan probabilitas pada tabel kita bisa mengembangkan gambar weighted aytomaton tadi menjadi 


        Automaton ini disebut hidden markov model (HMM). Kata hidden berarti, untuk setiap kata pada sekuens, kita tidak mengetahui kata tersebut dihasilkan oleh state mana secara model. Misalkan kata flies dapat dihasilkan oleh state N(noun) atau V(verb).




 F. Algoritma Viterbi

Algoritma Viterbi adalah salah satu algoritma dynamic programing yang prinsip kerjanya mirip dengan minimum edit distance. Ide utama algoritma viterbi adalah mengingat sekuens untuk setiap posisi tertentu( setiap iterasi, setiap panjang kalimat). apabila kita telah smpai pada kata terakhir, kita lakukan backtrace untuk mendapatkan sekuens terbaik.



        Pada gambar diatas menunjukkan pseudo-code untuk algoritma Viterbi. Variabel c berarti kelas kata, a adalah transition probability, dan b adalah lexical-generation probability. Pertama-tama algoritma tersebut membuat suatu matrik berukuran SxT dengan S adalah banyaknya states ( tidak termasuk start state ) dan T (time) adalah panjang sekuens. Pada setiap iterasi, kita pindah ke observasi kata lainnya.
    
Gambat diatas adalah ilustrasi algoritma Viterbi untuk kalimat input (observed sequence ) "flies like a flowe" dengan lexical generation probability pada Lexical emisson probabilities dan transition probabilities pada probabilitas bigram.

   Panah bewarna merah melambangkan backpointer yaitu state mana yang memberikan nilai tertinggi untuk melambangkan backpointer yaitu state mana yang memberikan nilai tertinggi untuk ekspansi ke state berikutnya. Setelah iteration step selesai, kita lakukan backtrace terhadap state terakhir yang memiliki nilai probabilitas tertinggi dan mendapat hasil seperti pada gambar dibawah.


 G. Proses training Hidden Markov Model


    Hidden Markov Model (HMM) adalah salah satu varian supervised learning, diberikan sekuens input dan output yang bersesuaian sebagai training data. Pada kasus POS tagging, yaitu inputnya adalah sekuens kata dan outputnya adalah sekuens kelas kata ( masing - masing kata/token berkorepondensi dengan kelas kata). Saat melatih HMM, kita ingin mengestimasi parameter A dan B yaitu transition probabilities dan emission probabilities/lexical-generation probabilitie. Kita melatih dengan menggunakan algoritma Forward-Backward (Baum-Welch Algorithm).

Algoritma forward

Algortima backward

Algoritma forward-backward (EM)


Dengan menggunakan teorema Bayes maka:

Disederhanakan jadi :



5. Contoh 


Kita mulai dengan mengimport library

Source : https://www.mygreatlearning.com/blog/pos-tagging/

 <atas input> || <bawah output>





# Importing libraries
import nltk
import numpy as np
import pandas as pd
import random
from sklearn.model_selection import train_test_split
import pprint, time
 
#download the treebank corpus from nltk
nltk.download('treebank')
 
#download the universal tagset from nltk
nltk.download('universal_tagset')
 
# reading the Treebank tagged sentences
nltk_data = list(nltk.corpus.treebank.tagged_sents(tagset='universal'))
 
#print the first two sentences along with tags
print(nltk_data[:2])

Output:



1
2
3
4
#print each word with its respective tag for first two sentences
for sent in nltk_data[:2]:
  for tuple in sent:
    print(tuple)

Output:




Bagi data menjadi testing data dan training data



Menggunakan data type untuk cek unique tag



Output:



1
2
3
4
# convert the matrix to a df for better readability
#the table is same as the transition table shown in section 3 of article
tags_df = pd.DataFrame(tags_matrix, columns = list(tags), index=list(tags))
display(tags_df)

Output:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def Viterbi(words, train_bag = train_tagged_words):
    state = []
    T = list(set([pair[1] for pair in train_bag]))
     
    for key, word in enumerate(words):
        #initialise list of probability column for a given observation
        p = []
        for tag in T:
            if key == 0:
                transition_p = tags_df.loc['.', tag]
            else:
                transition_p = tags_df.loc[state[-1], tag]
                 
            # compute emission and state probabilities
            emission_p = word_given_tag(words[key], tag)[0]/word_given_tag(words[key], tag)[1]
            state_probability = emission_p * transition_p   
            p.append(state_probability)
             
        pmax = max(p)
        # getting state for which probability is maximum
        state_max = T[p.index(pmax)]
        state.append(state_max)
    return list(zip(words, state))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Let's test our Viterbi algorithm on a few sample sentences of test dataset
random.seed(1234)      #define a random seed to get same sentences when run multiple times
 
# choose random 10 numbers
rndom = [random.randint(1,len(test_set)) for x in range(10)]
 
# list of 10 sents on which we test the model
test_run = [test_set[i] for i in rndom]
 
# list of tagged words
test_run_base = [tup for sent in test_run for tup in sent]
 
# list of untagged words
test_tagged_words = [tup[0] for sent in test_run for tup in sent]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#Here We will only test 10 sentences to check the accuracy
#as testing the whole training set takes huge amount of time
start = time.time()
tagged_seq = Viterbi(test_tagged_words)
end = time.time()
difference = end-start
 
print("Time taken in seconds: ", difference)
 
# accuracy
check = [i for i, j in zip(tagged_seq, test_run_base) if i == j]
 
accuracy = len(check)/len(tagged_seq)
print('Viterbi Algorithm Accuracy: ',accuracy*100)

Output:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#Code to test all the test sentences
#(takes alot of time to run s0 we wont run it here)
# tagging the test sentences()
test_tagged_words = [tup for sent in test_set for tup in sent]
test_untagged_words = [tup[0] for sent in test_set for tup in sent]
test_untagged_words
 
start = time.time()
tagged_seq = Viterbi(test_untagged_words)
end = time.time()
difference = end-start
 
print("Time taken in seconds: ", difference)
 
# accuracy
check = [i for i, j in zip(test_tagged_words, test_untagged_words) if i == j]
 
accuracy = len(check)/len(tagged_seq)
print('Viterbi Algorithm Accuracy: ',accuracy*100)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#To improve the performance,we specify a rule base tagger for unknown words
# specify patterns for tagging
patterns = [
    (r'.*ing$', 'VERB'),              # gerund
    (r'.*ed$', 'VERB'),               # past tense
    (r'.*es$', 'VERB'),               # verb   
    (r'.*\'s$', 'NOUN'),              # possessive nouns
    (r'.*s$', 'NOUN'),                # plural nouns
    (r'\*T?\*?-[0-9]+$', 'X'),        # X
    (r'^-?[0-9]+(.[0-9]+)?$', 'NUM'), # cardinal numbers
    (r'.*', 'NOUN')                   # nouns
]
 
# rule based tagger
rule_based_tagger = nltk.RegexpTagger(patterns)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#modified Viterbi to include rule based tagger in it
def Viterbi_rule_based(words, train_bag = train_tagged_words):
    state = []
    T = list(set([pair[1] for pair in train_bag]))
     
    for key, word in enumerate(words):
        #initialise list of probability column for a given observation
        p = []
        for tag in T:
            if key == 0:
                transition_p = tags_df.loc['.', tag]
            else:
                transition_p = tags_df.loc[state[-1], tag]
                 
            # compute emission and state probabilities
            emission_p = word_given_tag(words[key], tag)[0]/word_given_tag(words[key], tag)[1]
            state_probability = emission_p * transition_p   
            p.append(state_probability)
             
        pmax = max(p)
        state_max = rule_based_tagger.tag([word])[0][1]      
        
         
        if(pmax==0):
            state_max = rule_based_tagger.tag([word])[0][1] # assign based on rule based tagger
        else:
            if state_max != 'X':
                # getting state for which probability is maximum
                state_max = T[p.index(pmax)]               
             
         
        state.append(state_max)
    return list(zip(words, state))
1
2
3
4
5
6
7
8
9
10
11
12
13
#test accuracy on subset of test data
start = time.time()
tagged_seq = Viterbi_rule_based(test_tagged_words)
end = time.time()
difference = end-start
 
print("Time taken in seconds: ", difference)
 
# accuracy
check = [i for i, j in zip(tagged_seq, test_run_base) if i == j]
 
accuracy = len(check)/len(tagged_seq)
print('Viterbi Algorithm Accuracy: ',accuracy*100)

Output:



1
2
3
4
5
6
7
8
#Check how a sentence is tagged by the two POS taggers
#and compare them
test_sent="Will can see Marry"
pred_tags_rule=Viterbi_rule_based(test_sent.split())
pred_tags_withoutRules= Viterbi(test_sent.split())
print(pred_tags_rule)
print(pred_tags_withoutRules)
#Will and Marry are tagged as NUM as they are unknown words for Viterbi Algorithm

Output:





Di video diatas dijelaskan mengenai apa itu observable 




lalu apa itu emission probabilities


dan probability of time




1. Rangkaian simulasi download

2. Video download

3. HTML download



































 

No comments:

Post a Comment

Subscribe to: Posts (Atom)