In this project we implemented a Hidden Markov Model that recognized english sentences and decides wether a sentence is valid or not
There are three parts to this project:
Pattern Recognition: Implements the forward part of the forward/backwards procedure used in Hidden Markov Models
State-Path Determination: Implements the Viterbi Algorithm to determine the optimal state path for each observation set and it reports the probability
Model Optimization: Implements the Baum-Welch algorithm and reports the probabilities before and after optimization
This project consists of one overhead class (MM.h) that contains the methods for the recognize, statepath, and optimize functions. The recognize function essentially iterates through the possible combinations that will give you the given sentence through induction. It uses a function findAlpha on each sentence that implements the induction process, then adds all of the alpha values together for the total probability. The statepath function uses a similar technique but only return the maximum alpha value, as well as the statepath used to obtain said value. The optimize function takes the HMM and a sample observation and finds the gamma, eta, and beta values for the given observation. These values are used to change the a, b, and pi matrices that define the HMM. The program then writes back a .hmm file containing the new matrices.
Part One – Pattern Recognition
The observation percentages from the HMM seem low because the model has to account for all possible combinations. Even with only eight words, the number of sentences, many of which may not be grammatically correct, is huge. That is what this probability tells you: the likelihood of a given sequence out of all possible sequences. Also, some of the probabilities provided in the .hmm file seem pretty arbitrary. That is why the HMM does not always display realistic results and must be optimized to make it worthwhile. For example:
(“robots do kids play chess”) =
.1512% even though it is grammatically incorrect
P(“chess eat play kids”) = 0%
Running the Code: (in windows)
C:\[your active directory] recognize sentence.hmm example1.obs
0.027
0.0288
0.0
Each line reports P(O | lambda) for that HMM
Part Two – State Path Determination
The statepath helps to determine the meaning of the sentence. For example, if the sentence begins with an auxiliary, it is almost certainly a question, and if an auxiliary comes before a predicate, it is probably a tense modifier. However, one of the pitfalls is that the English language does not rely on auxiliaries alone to make questions. Often a question can only be determined by taking the context into account.
Each line again corresponds to a data set: In this case, the program outputs the “optimal” state path, i.e., the path with the highest probability P(O, I | lambda) and, if the probability is greater than zero, the state sequence. For example, the above code indicates that the probability of the first optimal path is 2.7%, and the tokens associated with the optimal state sequence is “SUBJECT”, “PREDICATE”, “OBJECT”. For the third input, since the probability of the obvervation is 0.0, no optimal path can be computed.
Part Three – Model Optimization
Optimizing the HMM for a zero probability observation would result in zero change because the optimization depends on existing values of state transitions. Therefore you must always optimize for a sentence that has P(“sentence”)>0
Running the Code: (in windows)
C:\[your active directory] optimize sentence.hmm example2.obs sentence-opti.hmm
0.000588 0.037037
For each data set, optimize prints out P(O | lambda) for the old HMM before optimization, and P(O | lambda) for the new HMM after optimization.
Questions
To make an HMM that can also parse adverbs, you must add an adverb state. Since in this case, the sample adverbs only come after the predicate and always end the sentence, it acts as an end state for the sentence. The present tense, however is a subset of predicate, increasing the probability of a predicate after an auxiliary will optimize the HMM for recognizing present tense verbs. A sample .hmm file might be:
Natural Language Processing
In this project we implemented a Hidden Markov Model that recognized english sentences and decides wether a sentence is valid or not
There are three parts to this project:
Pattern Recognition: Implements the forward part of the forward/backwards procedure used in Hidden Markov Models
State-Path Determination: Implements the Viterbi Algorithm to determine the optimal state path for each observation set and it reports the probability
Model Optimization: Implements the Baum-Welch algorithm and reports the probabilities before and after optimization
This project consists of one overhead class (MM.h) that contains the methods for the recognize, statepath, and optimize functions. The recognize function essentially iterates through the possible combinations that will give you the given sentence through induction. It uses a function findAlpha on each sentence that implements the induction process, then adds all of the alpha values together for the total probability. The statepath function uses a similar technique but only return the maximum alpha value, as well as the statepath used to obtain said value. The optimize function takes the HMM and a sample observation and finds the gamma, eta, and beta values for the given observation. These values are used to change the a, b, and pi matrices that define the HMM. The program then writes back a .hmm file containing the new matrices.
Part One – Pattern Recognition
The observation percentages from the HMM seem low because the model has to account for all possible combinations. Even with only eight words, the number of sentences, many of which may not be grammatically correct, is huge. That is what this probability tells you: the likelihood of a given sequence out of all possible sequences. Also, some of the probabilities provided in the .hmm file seem pretty arbitrary. That is why the HMM does not always display realistic results and must be optimized to make it worthwhile. For example:
Running the Code: (in windows)
Each line reports P(O | lambda) for that HMM
Part Two – State Path Determination
The statepath helps to determine the meaning of the sentence. For example, if the sentence begins with an auxiliary, it is almost certainly a question, and if an auxiliary comes before a predicate, it is probably a tense modifier. However, one of the pitfalls is that the English language does not rely on auxiliaries alone to make questions. Often a question can only be determined by taking the context into account.
Running the Code: (in windows)
Each line again corresponds to a data set: In this case, the program outputs the “optimal” state path, i.e., the path with the highest probability P(O, I | lambda) and, if the probability is greater than zero, the state sequence. For example, the above code indicates that the probability of the first optimal path is 2.7%, and the tokens associated with the optimal state sequence is “SUBJECT”, “PREDICATE”, “OBJECT”. For the third input, since the probability of the obvervation is 0.0, no optimal path can be computed.
Part Three – Model Optimization
Optimizing the HMM for a zero probability observation would result in zero change because the optimization depends on existing values of state transitions. Therefore you must always optimize for a sentence that has P(“sentence”)>0
Running the Code: (in windows)
For each data set, optimize prints out P(O | lambda) for the old HMM before optimization, and P(O | lambda) for the new HMM after optimization.
Questions
To make an HMM that can also parse adverbs, you must add an adverb state. Since in this case, the sample adverbs only come after the predicate and always end the sentence, it acts as an end state for the sentence. The present tense, however is a subset of predicate, increasing the probability of a predicate after an auxiliary will optimize the HMM for recognizing present tense verbs. A sample .hmm file might be:
Old Page
Executables
.HMM’s and .OBS Files
Source Files