Intro to Markov Models with Swift
Tags: swift, linguistics, ios
Published: 2019-01-31 03:11:31

---
title: Intro to Markov Models with Swift
published: true
description: 
tags: swift, linguistics, ios
---
![rickroll histogram](https://lh5.googleusercontent.com/GH0KkWl0ec1r_keK69bMzNRGWHx-7-CMn9Xlz4DsDzS_ZNqScRqkwqjhGe7n05XlrRubN4qoaO8Ymvj0iThpYhLbZOgfTCJlVXLcGhKSC9_zHf-7xcyp1m4keloA851WT9hE5FHG)
*This is crossposted on the [Twilio blog](https://www.twilio.com/blog/intro-to-markov-models-with-swift).*
Did you know [PageRank](https://en.wikipedia.org/wiki/PageRank), the algorithm Google uses to determine the order of search results, is a type of Markov chain? I first learned about Markov chains and Markov Models in my Speech Synthesis and Recognition elective and  was amazed at how they are used in speech recognition, music generation, and modeling sequential data to predict the outcome of a basketball game.

# What are Markov chains and Markov Models?

The most basic type of Markov Model is a Markov chain, a model whose next state is only selected based on its current state. Markov Chains are used in genetics, finance, economics, game theory, and other fields. An example of one would be predicting tomorrow's weather by looking only at today's weather,not yesterday's. 

Wikipedia defines it like so: 
> In probability theory, a Markov model is a stochastic model used to model randomly changing systems where it is assumed that future states depend only on the current state, not on the events that occurred before it (that is, it assumes the Markov property).

The transition from one state to another satisfies the Markov Property. It states that the probability of transitioning to any other state is only based on the current state, and not on the sequence of states that came before it--thus every Markov process is memoryless.

Hidden Markov Models are a type of Markov chain where some states are observable and some are hidden. They are sometimes explained by the [Ice Cream Climatology scenario](https://cs.jhu.edu/~jason/papers/eisner.tnlp02.pdf), proposed by [Jason Eisner](http://www.cs.jhu.edu/~jason/) in 2002:  

> The situation: You are a climatologist in the year 2799, studying the history of global warming. You can't find any records of Baltimore weather, but you do find my (Jason Eisner's) diary, in which I assiduously recorded how much ice cream I ate each day. What can you figure out from this about the weather that summer?

![ice cream gif](https://media.giphy.com/media/r8Kn8NaNM3xba/giphy.gif)

I recently thought, "what would be the Twilio way of explaining this concept?" Since developers are DOers let's show, not tell, an example. 

## Sample Sentence
Let's break down a sentence that means something to Twilio: Never gonna give you up. 
> Never gonna let you down.
![rickroll gif](https://lh6.googleusercontent.com/MYBpqYiHnqfR_WV4Zw2g9hIJXyXGE5U3APUqowKsX6_Pr43H6dyfSFFng96H1ZpB-6vifiW0iwUj2GB8UK5g2u_NwgDDwW2rL46YvdonHOmDChZlGfwTgAs26ptPIWGp-Y33lNq8)

This has seventeen words (also known as tokens) and eight unique words (also known as keys.) A weighted distribution is the percentage that one key will appear. It is based on the total amount of times a key shows up divided by the total number of tokens. "Never", "gonna", and "you" all have a weighted distribution of 2/10, as shown in the histogram below.
![rickroll histogram](https://lh5.googleusercontent.com/GH0KkWl0ec1r_keK69bMzNRGWHx-7-CMn9Xlz4DsDzS_ZNqScRqkwqjhGe7n05XlrRubN4qoaO8Ymvj0iThpYhLbZOgfTCJlVXLcGhKSC9_zHf-7xcyp1m4keloA851WT9hE5FHG)

Histograms are a simple way to represent weighted distributions. These keys, or words, can also represent states. Each key can point to another key: this is called a transition.

## Transitioning Between States
Let's visualize how every key is matched with an array of possible tokens that could follow that key.
![rickroll chart](https://lh6.googleusercontent.com/zn9ktrUCuoNcgdj_fCl6MnBwxaMhSAnvcNSVNYiNQdcXsNVvXkilXYtwmyAD7agdOUQ7lL1diwmE74NWhi5on5AFOP6jksp_3bwrLPQEAoUlvhZ0BmTB181Ukl5GOzZZXgIgdvma)

Here, the tokens are organized in pairs with a state corresponding to the possible states that can follow it. How can this better be visualized?
![rickroll arrows](https://s3.amazonaws.com/com.twilio.prod.twilio-docs/images/nevergonnalines.width-500.png)

In the above graphic, each word represents a key, or a state, and the arrows point to potential states that can follow it. The corresponding color-coded sentence looks like this: 
![color-coded sentence](https://s3.amazonaws.com/com.twilio.prod.twilio-docs/images/nevergonnacolor.width-1000.png)

But wait! There's more!
![Billy Mays but wait there's more!](https://lh6.googleusercontent.com/iaOUckV4UA9PQhQ9XQqOSVhBnzJ52GPInqK92lhidPwy49-BkpnDFu1FIm5YTcR6RFSYi9wuvNkaTng1Wl2a9P0v_QH67WYtpN2_e7vArSkl9kVuMCgGcAgN6daCACUYCZe602n9)

Let's try adding the weighted distributions so that each arrow has the probability that it will be selected as the transition to the next state.

![rickrolling with states](https://s3.amazonaws.com/com.twilio.prod.twilio-docs/images/nevergonnagiveyouupwithprob.width-500.png)

## Using CocoaPods with Swift Playgrounds
[Swift Playgrounds](https://www.apple.com/swift/playgrounds/) are amazing at letting you see the results of your code quickly. We'll be using them in addition to a Swift library called [MarkovModel](https://github.com/db-in/MarkovModel) to visualize our Markov Model example via code. 

To use CocoaPods with Playgrounds, first create a new directory and then make a new XCode project there. On the command line in the top level of your directory, make a podfile with `pod init` and include this code in it:
```
target 'your-project-name' do
  # Comment the next line if you're not using Swift and don't want to use dynamic frameworks
  use_frameworks!
  pod 'MarkovModel'

end
post_install do |installer|
    installer.pods_project.build_configurations.each do |config|
        config.build_settings.delete('CODE_SIGNING_ALLOWED')
        config.build_settings.delete('CODE_SIGNING_REQUIRED')
    end
    
    installer.pods_project.targets.each do |target|
        target.build_configurations.each do |config|
            config.build_settings['CONFIGURATION_BUILD_DIR'] = '$PODS_CONFIGURATION_BUILD_DIR'
        end
    end
end

```
Back on the command line run `pod install`, and close the project. Next, create a Swift Playground by opening XCode and clicking *File->New->Playground* and save it in the top level of your directory. If you don't see the playground, drag it into the workspace like so: 
![playground video](https://www.youtube.com/watch?v=ujxYr15ahro)

Now make sure you open up your *.xcworkspace* and not *.xcproject*. Now place the following starter code in your *.playground* file to check that the pod installed correctly.

```swift
import MarkovModel
import Foundation
```
You may need to clean with *cmd-shift-k* and then build with *cmd-b*, but should be good to go!

## Markov Models with Swift

Let's translate our rickrolling sentence into Swift code using methods from the MarkovModel library.

```swift
let markovModel = MarkovModel(transitions: ["Never", "gonna", "give", "you", "up", "never", "gonna", "let", "you", "down"])
markovModel.chain.next(given: "gonna") 
```

Here, we create a Markov Model to train and pass it an array of the tokens from our sentence.  We calculate a future state by calling *next*. With this library we have three possible decision process options: *predict*, *random*, and *weightedRandom*. The default is *predict*. 

You can also print out the weighted distributions of each token with 
```swift
print(markovModel)
```
which outputs
![markov model output](https://s3.amazonaws.com/com.twilio.prod.twilio-docs/images/playgroundmarkov.width-1000.png)

## What's Next?
![thank u next gif](https://s3.amazonaws.com/com.twilio.prod.twilio-docs/original_images/thankunext.gif)
Wow! Markov chains are so powerful. As a Golden State Warriors fan, I wonder about trying to predict the outcome of their games based on prior games, or maybe how Steph Curry will shoot based on previous statistics. Think of the possibilities! 

For more reading on Markov Chains and Models, I recommend this [Clemson University lecture](http://cecas.clemson.edu/~ahoover/ece854/refs/Ramos-Intro-HMM.pdf) or [UC Davis one](https://www.math.ucdavis.edu/~gravner/MAT135B/materials/ch12.pdf), this [fun, visual, and interactive explanation of Markov Chains](http://setosa.io/ev/markov-chains/), and this [Khan Academy video](https://www.khanacademy.org/computing/computer-science/informationtheory/moderninfotheory/v/markov_chains).

Stay tuned for the next post where a Markov Model will be trained with different inputs to generate similar text. In the meantime, let me know how you would use Markov Models in the comments or online:
Twitter: [@lizziepika](https://twitter.com/lizziepika)
GitHub: [@elizabethsiegle](https://github.com/elizabethsiegle)
Email: lsiegle@twilio.com