Skip to content

README.md

Latest commit

 

History

History
executable file
·
125 lines (90 loc) · 4.95 KB

README.md

File metadata and controls

executable file
·
125 lines (90 loc) · 4.95 KB

Example Viterbi Implementation

This package includes a python / numpy implementation to find the Viterbi Path of an input set of observations. This is useful when dealing with Hidden Markov Models.

Generating Synthetic Observations

The generate_observations .py file takes in an initial probability, transition matrix, and emissions matrix to generate synthetic observations.

    # Initial State Probability
    initial_state_probability = [0.9999, 0.0001]

    # Transition Matrix
    transition_matrix = [[0.95, 0.05],\
                        [0.10, 0.90]]

    # Emission Matrix
    emission_matrix = [[1/6, 1/6, 1/6, 1/6, 1/6, 1/6],\
                      [0.1, 0.1, 0.1, 0.1, 0.1, 0.5]]

    true_state, dice_rolls = generate_observations(initial_state_probability, transition_matrix, emission_matrix,
                                            num_samples=300,
                                            state_space=['F','L'],
                                            observation_space=['1', '2', '3', '4', '5', '6'],
                                            seed=515)

Output:

$ python generate_observations.py

Rolls   : 453521123164266656412446615666665444621516153163662666666436
Actual  : FFFFFFFFFFFFFFFFFFFFFFLLLLLLLLLLFFFFFFFFFFFFFFLLLLLLLLLLLLLL

Rolls   : 215466646561664242124651212224225422545115322161655131312216
Actual  : LLFLLLLLLLLLLLFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

Rolls   : 353245565163614165255512335126565264624343664131653133463636
Actual  : FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFLLLLLLLLLLL

Rolls   : 616464666651231154666531254315654541152461665513656641614366
Actual  : LLLLLLLLLLLLLLLLLLLLFFFFFFFFFFFFFFFFFFLLLLLLFFFLLLLFFFFFFFFF

Rolls   : 642545611166666366446616266662554646212346453256561435435121
Actual  : FFFFFFLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLFFFFFFFFFFFFFFFFFF

Example Viterbi Path

In the example_viterby.py file, a 6-sided die is rolled while being interchanged with a loaded die. The loaded die has an affinity for 6.

Initial State Probability:

Transitions Fair Loaded
Begin 0.9999 0.0001

Transition Matrix:

Transitions Fair Loaded
Fair 0.95 0.05
Loaded 0.10 0.90

Emission Matrix:

Emissions 1 2 3 4 5 6
Fair 0.25 0.25 0.25 0.25 0.25 0.25
Loaded 0.2 0.3 0.3 0.2 0.25 0.25 
$ python example_viterbi.py

Observed : 453521123164266656412446615666665444621516153163662666666436
Actual   : FFFFFFFFFFFFFFFFFFFFFFLLLLLLLLLLFFFFFFFFFFFFFFLLLLLLLLLLLLLL
Viterbi  : FFFFFFFFFFFFFLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL

Observed : 215466646561664242124651212224225422545115322161655131312216
Actual   : LLFLLLLLLLLLLLFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Viterbi  : LLLLLLLLLLLLLLFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

Observed : 353245565163614165255512335126565264624343664131653133463636
Actual   : FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFLLLLLLLLLLL
Viterbi  : FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFLLLLL

Observed : 616464666651231154666531254315654541152461665513656641614366
Actual   : LLLLLLLLLLLLLLLLLLLLFFFFFFFFFFFFFFFFFFLLLLLLFFFLLLLFFFFFFFFF
Viterbi  : LLLLLLLLLLFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFLLLLLLLLLLLLLLLLLLLL

Observed : 642545611166666366446616266662554646212346453256561435435121
Actual   : FFFFFFLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLFFFFFFFFFFFFFFFFFF
Viterbi  : LLLLLLLLLLLLLLLLLLLLLLLLLLLLLFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

Estimating Transition and Emission Matrices from Observations

In estimate_based_on_observation.py, a loaded die is rolled 1,000,000 times and the viterbi algorithm is used to estimate the transition and emission matrices.

$ python estimate_based_on_observation.py

Truth:

Transitions Fair Loaded
Fair 0.95 0.05
Loaded 0.05 0.95
Emissions 1 2 3 4 5 6
Fair 0.166667 0.166667 0.166667 0.166667 0.166667 0.166667
Loaded 0.04 0.04 0.04 0.04 0.04 0.8

Estimated After 11 Runs:

Transitions Fair Loaded
Fair 0.970688 0.029312
Loaded 0.0283057 0.971694
Emissions 1 2 3 4 5 6
Fair 0.167174 0.166878 0.167176 0.168417 0.168816 0.161539
Loaded 0.0419376 0.041629 0.04249 0.0412889 0.0415386 0.791116