<jupyter_start><jupyter_text>Problem 2 Hidden Markov Models (50 points)In Hidden Markov Model(HMM) part, you need first implement 5 important functions with HMM parametrers we given to you. Then you need to calculate HMM parameters by yourself and use it to solve Part-of-Speech Tagging problem.After finishing the implementation, you can use hmm_test_script.py to test the correctness of your functions. Office HourWeek 12Apr. 5th Friday	LVL 2nd Floor-201A	10:00am to 12:00pm	<NAME> <EMAIL>Week 13Apr. 12th Friday LVL 2nd Floor-201A	10:00am to 12:00pm	<NAME> <EMAIL>Week 14Apr. 18th Thursday LVL 2nd Floor-201A 10:00am to 12:00pm <NAME> <EMAIL> Grading guideline2.1 Implementation    1. forward function - 5 = 5*1 points    2. backward function - 5 = 5*1 points    3. sequence_prob function - 5 = 5*1 points    4. posterior_prob function - 5 = 5*1 points    5. viterbi function - 10 = 5*2 points    There are 5 sets of grading data. Each grading data includes paramaters(pi, A, B, obs_dict, state_dict, Osequence), which we will use to initialize HMM class and test your functions. To receive full credicts, your output of function 1-4 should within an error of 10^-8, your output of viterbi function should be identical with ours.2.2 Application to Part-of-Speech Tagging    1. model_training function - 10 = 10*(your_correct_pred_cnt/our_correct_pred_cnt)    2. speech_tagging function - 10 = 10*(your_correct_pred_cnt/our_correct_pred_cnt)    We will still use the dataset we given to you to grading this part(with a different random seed). We will train your model and ours based on same train_data. We will test model_training function and speech_tagging function separatly.    In order to check your model_training function, we will use 50 sentences from train_data to do Part-of-Speech Tagging. To receive full credits, your prediction accuracy should be identical with ours.    In order to check your speech_tagging function, we will use 50 sentences from test_data to do Part-of-Speech Tagging. To receive full credits, your prediction accuracy should be identical with ours. What to submithmm.pyspeech_tagging.py 2.1 Implementation (30 points)In 2.1, you are given parameters of a HMM and you will implement two procedures.**(1) The Evaluation Problem**Given a HMM and a sequence of observations, what is the probability that the observations are generated by the model?Two algorithms usually be used for evaluation problem: the forward algorithm or the backwards algorithm (DO NOT confuse them with the forward-backward algorithm). Based on the result of forward algorithm and backward algorithm, you will be asked to calculate sequence probability and posterior probability**(2) The Decoding Problem**Given a model and a sequence of observations, what is the most likely state sequence in the model which produced the observation sequence. For decoding you will be asked to implement Viterbi algorithm. HMM ClassIn this project, we abstracted Hiddern Markov Model as a class. Each Hiddern Markov Model initialized with Pi, A, B, obs_dict and state_dict. HMM class has 5 inner functions: Forward function, backward function, sequence_prob function, posterior_prob function and viterbi function.``` You can add your own function or variables in HMM class, but you shouldn't change current exists. class HMM:    def __init__(self, pi, A, B, obs_dict, state_dict):        - pi: (1*num_state) A numpy array of initial probailities. pi[i] = P(X_1 = s_i)        - A: (num_state*num_state) A numpy array of transition probailities. A[i, j] = P(X_t = s_j|X_t-1 = s_i)        - B: (num_state*num_obs_symbol) A numpy array of observation probabilities. B[i, o] = P(Z_t = z_o| X_t = s_i)        - obs_dict: A dictionary mapping each observation symbol to their index in B        - state_dict: A dictionary mapping each state to their index in pi and A     TODO:    def forward(self, Osequence):     TODO:    def backward(self, Osequence):     TODO:    def sequence_prob(self, Osequence):     TODO:    def posterior_prob(self, Osequence):     TODO:    def viterbi(self, Osequence):``` 2.1.1 Evaluation problem (a) Forward algorithm and backward algorithm (10 points)Here $\lambda$ means the model. Please finish the implementation of forward() function and backward() function in hmm.py:- $\alpha[i, t] = P(X_t = s_i, Z_{1:t} | \lambda).$```def forward(self, Osequence):    """    Inputs:    - self.pi: (1*num_state) A numpy array of initial probailities. pi[i] = P(X_1 = s_i)    - self.A: (num_state*num_state) A numpy array of transition probailities. A[i, j] = P(X_t = s_j|X_t-1 = s_i)    - self.B: (num_state*num_obs_symbol) A numpy array of observation probabilities. B[i, o] = P(Z_t = z_o| X_t = s_i)    - Osequence: (1*L) A numpy array of observation sequence with length L    Returns:    - alpha: (num_state*L) A numpy array alpha[i, t] = P(X_t = s_i, Z_1:Z_t | λ)    """```- $\beta[i, t] = P(Z_{t+1:T}|X_t = s_i, \lambda).$```def backward(self, Osequence):    """    Inputs:    - self.pi: (1*num_state) A numpy array of initial probailities. pi[i] = P(X_1 = s_i)    - self.A: (num_state*num_state) A numpy array of transition probailities. A[i, j] = P(X_t = s_j|X_t-1 = s_i)    - self.B: (num_state*num_obs_symbol) A numpy array of observation probabilities. B[i, o] = P(Z_t = z_o| X_t = s_i)    - Osequence: (1*L) A numpy array of observation sequence with length L    Returns:    - beta: (num_state*L) A numpy array beta[i, t] = P(Z_t+1:Z_T | X_t = s_i, λ)    """``` (b) Sequence probability (5 points)Based on your forward, backward function, you will calculate the sequence probability.(You can call forward function or backward function inside of sequence_prob function)$$P(Z_1, . . . , Z_T = O|\lambda) = \sum_{i=1}^{N}P(X_t = s_i, Z_{1:T} | \lambda) = \sum_{i=1}^{N}\alpha[i, T]$$```def sequence_prob(self, Osequence):    """    Inputs:    - Osequence: (1*L) A numpy array of observation sequence with length L    Returns:    - prob: A float number of P(Z_1:Z_T | λ)    """``` (c) Posterior probability (5 points)The forward variable $\alpha[i, t]$ and backward variable $\beta[i, t]$ are used to calculate the posterior probability of a specific case. Now for t = 1...T and i = 1...N, we define posterior probability $\gamma_t(i) = P(X_t = s_i|O,\lambda)$ the probability of being in state $s_i$ at time t given the observation sequence O and the model $\lambda$.$$\gamma_t(i) = \frac{P(X_t = s_i, O|\lambda)}{P(O|\lambda)} = \frac{P(X_t = s_i, Z_{1:t}|\lambda)}{P(O|\lambda)}$$$$P(X_t = s_i, Z_{1:t}|\lambda) = P(Z_{1:t}|X_t = s_i,\lambda) \cdot P(Z_{t+1:T}|X_t = s_i,\lambda) \cdot P(X_t = s_i|\lambda) = \alpha[i, t] \cdot \beta[i, t]$$Thus$$\gamma_t(i) = \frac{\alpha[i, t] \cdot \beta[i, t]}{P(O|\lambda)}$$where$$P(O|\lambda) = \sum_{i=1}^{N}\alpha[i, T]$$Signature:```def posterior_prob(self, Osequence):    """    Inputs:    - Osequence: (1*L) A numpy array of observation sequence with length L    Returns:    - prob: (num_state*L) A numpy array of P(X_t = i|O, λ)    """```You can use $\beta_t(i)$ to find the most likely state at time t which is the state $Z_t=s_i$ for which $\beta_t(i)$ is maximum. This algorithm works fine in the case when HMM is ergodic i.e. there is transition from any state to any other state. If applied to an HMM of another architecture, this approach could give a sequence that may not be a legitimate path because some transitions are not permitted. To avoid this problem Viterbi algorithm is the most common decoding algorithms used. (d) Viterbi algorithm (10 points)Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states. We want to compute the most likely state path that corresponds to the observation sequence O based HMM. Namely, $k^∗ = (k^∗_1,k^∗_2,··· ,k^∗_T) = argmax_k P(s_{k_1},s_{k_2},··· ,s_{k_T}|Z_1,Z_2,··· ,Z_T = O, \lambda)$. Signature:```def viterbi(self, Osequence):    """    Inputs:    - Osequence: (1*L) A numpy array of observation sequence with length L    Returns:    - path: A List of the most likely hidden state path k* (return state instead of idx)    """``` 2.2 Application to Speech Tagging ( 20 points)Part-of-Speech (POS) is a category of words (or, more generally, of lexical items) which have similar grammatical properties.(noun, verb, adjective, adverb, pronoun, preposition, conjunction, interjection, and sometimes numeral, article, or determiner.)Part-of-Speech Tagging (POST) is the process of marking up a word in a text (corpus) as corresponding to a particular part of speech, based on both its definition and its context.Here you wiil use HMM to do POST. You will need to caculate the parameters(pi, A, B, obs_dict, state_dict) of HMM first and then apply Vitervi algorithm to do speech-tagging. Datasettags.txt: Universal Part-of-Speech Tagset| Tag | Meaning | English Examples || :------ | :------ | :------ || ADJ | adjective | new, good, high, special, big, local || ADP | adposition | on, of, at, with, by, into, under || ADV | adverb | really, already, still, early, now || CONJ | conjunction | and, or, but, if, while, although || DET | determiner, article | the, a, some, most, every, no, which || NOUN | noun | year, home, costs, time, Africa || NUM | numeral | twenty-four, fourth, 1991, 14:24 || PRT | particle | at, on, out, over per, that, up, with || PRON | pronoun | he, their, her, its, my, I, us || VERB | verb | is, say, told, given, playing, would || . | punctuation marks | . , ; ! || X | other | ersatz, esprit, dunno, gr8, univeristy |sentences.txt: Including 57340 sentences which have already been tagged.| Word | Tag ||:------:|:------:|| b100-48585 || She | PRON || had | VERB || to | PRT || move | VERB || in | ADP || some | DET || direction | NOUN || -- | . || any | DET || direction | NOUN || that | PRON || would | VERB || take | VERB || her | PRON || away | ADV || from | ADP || this | DET || evil | ADJ || place | NOUN || . | . | Part-of-Speech TaggingIn this part, we collect our dataset and tags with Dataset class. Dataset class includes tags, train_data and test_data. In both dataset include a list of senetences, each sentence is an object of Line class.You only need to implement model_training function and Speech_tagging function. We have provide you the accuracy function, which you can use to compare your predict_tagging and true_tagging of a sentence. You can find the definition bellow.``` You can add your own functions or variables in Dataset class, but you shouldn't change current exists. class Dataset:    def __init__(self, tagfile, datafile, train_test_split=0.8, seed=112890):		self.tags		self.train_data		self.test_data    def read_data(self, filename):    def read_tags(self, filename):    class Line:        def __init__(self, line, type):            self.id            self.words            self.tags            self.length        def show(self): TODO:def model_training(train_data, tags) TODO:def Speech_tagging(model, test_data, tags)def accuracy(predict_tagging, true_tagging)``` 2.2.1 Model traning (10 points)In this part, you will need to calculate the parameters of HMM model based on train_data and tags.Signature:```def model_training(train_data, tags):	"""	Inputs:	- train_data: a list of sentences, each sentence is an object of Line class    - tags: a list of POS tags	Returns:	- model: an object of HMM class initialized with paramaters(pi, A, B, obs_dict, state_dict) you calculated based on traning dataset. We will use the object you returned to do speech tagging.	"""``` 2.2.2 Speech_tagging (10 points)Based on HMM from 2.2.1, do speech tagging for each sentence on test data. Note when you meet a word which is unseen in training dataset. You need to modify the emission matrix and obs_dict of your current model in order to handle this case. You  will assume the emission probability from each state to a new unseen word is 10^-6(a very low probability).```For example, in hmm_model.json, we use the following paramaters to initialize HMM:S = ["1", "2"]pi: [0.7, 0.3]A: [[0.8, 0.2], [0.4, 0.6]]B = [[0.5, 0, 0.4, 0.1], [0.5, 0.1, 0.2, 0.2]]Observations = ["A", "C", "G", "T"]If we find another observation symbol "X" in observation sequence, we will modify parameters of HMM as follows:S = ["1", "2"]pi: [0.7, 0.3]A: [[0.8, 0.2], [0.4, 0.6]]B = [[0.5, 0, 0.4, 0.1, 1e-6], [0.5, 0.1, 0.2, 0.2, 1e-6]]Observations = ["A", "C", "G", "T", "X"]```Remember you are not supposed to access test_data on model_training function, you need to implement this logic on speech_tagging function.Signature:```def speech_tagging(test_data, model):	"""	Inputs:	- test_data: (1*num_sentence) a list of sentences, each sentence is an object of Line class	- model: an object of HMM class	Returns:	- tagging: (num_sentence*num_tagging) a 2D list of output tagging for each sentences on test_data	"""``` 2.2.3 Suggestion(0 points)This part won't be graded. In order to have a better understanding of HMM. Come up with one sentence by yourself and tagging it manually. Then run your forward function, backward function, seq_prob function, posterior_prob function and viterbi function on the model from 2.2.1. Print the result of each function, see if you can explain your result.<jupyter_code>!python /Users/jianfeiwang/desktop/pa4/markov/hmm_test_script.py
d = {1:'1'}
d[1]
if 1 in d:
    print('s')
import numpy as np
a = [0.35,0.15]
b = [[0.8,0.2],[0.4,0.6]]
a = np.array(a)
b = np.array(b)
print(a)
print(b)
print(np.multiply(a,b))
c = [0.4, 0.2]
d = [3.84e-06, 1.152e-05]
c = np.array(c)
d = np.array(d)
print(c*d)
print(np.multiply(c,d))
print(np.multiply(np.multiply(a,b),np.multiply(c,d)))
c = [[0.4],[0.2]]
c = np.array(c)
print(np.multiply(np.multiply(a,b),c.T))
d = [[3.84],[1.152]]
d = np.array(d)
print(np.multiply(np.multiply(np.multiply(a,b),c.T).T,d).T)
 A = np.array([[[ 1,  2,  3],
                [ 4,  5,  6],
                [12, 34, 90]],
                [[ 4,  5,  6],
                 [ 2,  5,  6],
                [ 7,  3,  4]]])


np.sum(A,axis = 0)
a = [[3,4],[1,2]]
b = [[1],[2]]
a = np.array(a)
b = np.array(b)
a / b 
tmp = np.zeros([3,1])
tmp
tmp[0][0]+=1
tmp<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12111559425214129, 'fraction_numerical': 0.024704466624194805, 'mean_word_length': 3.993990809473312, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '631873', 'license': 'MIT', 'n_tokens_mistral': 4761, 'n_tokens_neox': 4482, 'n_words': 1840, 'path': 'PA4/Markov/PA4_HMM.ipynb', 'repo_name': 'Magicicesea/Python-Machine-Learning-algorithm-implement', 'size': '14163'}