Sarcasm Until I started using social media heavily, I did not know smile emoticon can be sarcastic. I, myself, have used the smile emoticon to express the “ ” expression many times. I have seen others use them a lot too to express similar expressions. and are different. What we see or observe, might not give an actual representation of the state. As the quote “ ” says, the observations and states might sometimes be in contrast to each other. Sarcasm is real! fine! Observations states an elephant has one teeth to show and other teeth to chew Binita and Emojis Binita is my wife. I have been asking her to select an emoticon daily on how she feels on a particular day. I have given her three choices — and , and she selects an emoticon daily. My intention in asking her to choose an emoticon daily is to know how she feels each day. I assume she can either feel or . laugh, smile, cry happy sad So, the observations I can make are and , and the states are and Observations are visible on me, but the states are not. The states are hidden from me. laugh, smile, cry happy sad. I want to know her state daily, and so, I am modeling this scenario as a hidden Markov model and I am using the Viterbi algorithm to find the states. Code and Modeling Let's put the things we know so far in various Python data structures. states = (‘happy’, ‘sad’) Now, I assume the state of being happy/sad satisfies Markov property. So, her state tomorrow depends only on her state today, and not on her state of yesterday and/or before. In addition, I am also assuming the transition probabilities and emission probabilities. Transition probabilities give probabilities of transition between different states. And, emission probabilities give probabilities of observations given the states. transition_p = { : { : , : }, : { : , : }
}
emission_p = { : { : , : , : }, : { : , : , : }
} 'happy' 'happy' 0.6 'sad' 0.4 'sad' 'happy' 0.3 'sad' 0.7 'happy' 'laugh' 0.7 'smile' 0.2 'cry' 0.1 'sad' 'laugh' 0.1 'smile' 0.3 'cry' 0.6 The graphical representation of the hidden Markov model is shown below: I have asked her for five days in a row about her feeling. Today I want to use the Viterbi algorithm to know her states from the observations. My note says her feelings during the last five days: observations = (‘smile’, ‘laugh’, ‘smile’, ‘cry’, ‘laugh’) Now, my task is to find out the states from the and probabilities. observations First day Let’s look at the first day. The first day, she sent me “smile” emoji. She could smile either being happy or being sad. The “smile” emoji can come two ways. Either she is happy, and she expressed her state through the “smile” emoji. Or she is being sarcastic and sending me “smile” emoji. So, the probability that she is happy on the first day is the probability that she is not being sarcastic on the first day i.e she smiled and she is happy on the first day. Similarly, the probability that she is sad on the first day is the probability that she is being sarcastic on the first day i.e she smiled though she is sad on the first day. So, probability of she being happy = probability of her smiling and being happy = probability of she being happy * probability of she smiling after being happy = 0.5 * 0.2 = 0.1 Similarly, probability of she being sad = probability of her smiling and being sad = probability of she being sad * probability of she smiling after being sad = 0.5 * 0.3 = 0.15 Interesting! According to the probabilities we assumed, she is sad on the first day. God, I should have calculated the probability on that day only. I could have tried to change her mood :| Let’s implement the first-day condition in the Python code. One implementation detail though: as we are multiplying probabilities, we might end up with very very small probabilities as we go further. We apply logarithms to them and calculate , so that we are not dealing with extreme values. log probabilities The key gives the state of her in the previous day. As we don’t have the previous day on the first day, we write it as . prev None Beyond the first day Now, we do the same thing for the other days. So, we employ a loop from the second day to the last day. For each day, we append a dictionary. The dictionary of the particular day has all the states as the and probabilities associated with all the states as the . It has one key-value pair given by key which gives the previous day state. The key would be useful for calculating the compound probabilities (log probabilities in our case). key value prev prev i range( , len(observations)): logprobabilities.append({}) prev = prev_p = float( ) state states: logprobabilities[i ][state] > prev_p:
            prev = state
            prev_p = logprobabilities[i ][state] logprobabilities[i][ ] = prev state states:
        logprobabilities[i][state] = logprobabilities[i ][prev] + math.log(transition_p[prev][state]) + math.log(emission_p[state][observations[i]]) for in 1 # append dictionary for each observation which contains log probabilities of being happy/sad # find the previous state by going in the previous day dictionary # we iterate in all the states and see which state has highest log probability None '-inf' for in if -1 -1 # set the previous state to the one we found above 'prev' # calculate log probabilities of all the states for today using previous day log probability, and probabilities matrices for in -1 Let’s take an instance of the second day, and understand the algorithm. We know her state of the first day by iterating over all the states on the first day and finding which state has the maximum log probability. We save the state in the key. Then, we go on to calculate the compound log probabilities of all the states on the second day. For doing that we make use of the transition and emission probabilities. We saw, in our example, she is on the first day. prev sad So, for calculating the probability that she is happy on the second day (given that she gave emoji), we first calculate the product of the probability of her transitioning from state to state and the probability of her ing if she is . laugh sad happy laugh happy The first probability, we would get from the transition probability matrix, and the second probability, we would get from the emission probability matrix. In our case, the first probability, the probability that she would transition from state to state, is given by , and the second probability, the probability that she laughs if she is happy, is given by . sad happy transition_p[‘sad’][‘happy’] emission_p[‘happy’][‘laugh’] The product is then multiplied with the previous day's highest probability (probability of being sad in our case which had a value of 0.15), and we will get the probability of coming to the current state on the second day. The process is continued to the last day, and we would have her states for all the days. Let’s run the code and see what are the (log) probabilities we end up with. So, we see the list, which gives (log) probabilities of all the states. The state of the first day can be found from at the of the second element. Here, the states of the first, second, third and fourth day are , , and respectively. logprobabilities value prev key sad happy, happy sad The state of the last (fifth) day can be found by seeing which state has the highest log probability in the last element of the list. As we can see ‘ state has the highest log probability, she was on the last day. happy’ happy Out of five days, she was happy for three days and sad for two days. Better than her initial probabilities, so I am happy with her states ;) Applications What we used here is the Viterbi algorithm. The algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states. The sequence of hidden states is called Viterbi path. Using the algorithm to find spouse’s state is fun. Why don’t you too try with your spouse or BF or GF or best friend or any friend? The algorithm can be used in many other applications too. In school days, I was asked a question in Nepali examination to find part of speech in a sentence — पदवर्ग छुट्याउ. That can be done using the Viterbi algorithm too — POS tagging. Other applications include speech recognition, speech synthesis, computational linguistics, and many more. More stuff on algorithms coming soon, stay tuned! In the meantime, please let me know your thoughts on this article in the comment section. Stay safe, stay healthy. :) Also published on Medium's surajregmi

Different

Breaking Down Secretary Problem

Reach me in LinkedIn.

Read My Stories

Too Long; Didn't Read

Make resilience your competitive advantage

My Journey Into Predicting States Using Emoji Observations With Viterbi Algorithm

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Breaking Down Secretary Problem

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Breaking Down Secretary Problem

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps