Python

Introduction To Hidden Markov Models

Posted on Updated on

A Hidden Markov Model is a statistical model that can be used to determine the underlying processes that affect a particular observed outcome. A HMM can be presented as the simplest dynamic Bayesian network. The mathematics behind the HMM were developed by L. E. Baum and coworkers. It is closely related to an earlier work on the optimal nonlinear filtering problem by Ruslan L. Stratonovich, who was the first to describe the forward-backward procedure.

In simpler Markov models (like a Markov chain), the state is directly visible to the observer, and therefore the state transition probabilities are the only parameters. In a hidden Markov model, the state is not directly visible, but the output, dependent on the state, is visible. Each state has a probability distribution over the possible output tokens. Therefore, the sequence of tokens generated by an HMM gives some information about the sequence of states. The adjective ‘hidden’ refers to the state sequence through which the model passes, not to the parameters of the model; the model is still referred to as a ‘hidden’ Markov model even if these parameters are known exactly.

Example:
Consider two friends, Alice and Bob, who live far apart from each other and who talk together daily over the telephone about what they did that day. Bob is only interested in three activities: walking in the park, shopping, and cleaning his apartment. The choice of what to do is determined exclusively by the weather on a given day. Alice has no definite information about the weather where Bob lives, but she knows general trends. Based on what Bob tells her he did each day, Alice tries to guess what the weather must have been like.

states = ('Rainy', 'Sunny')
observations = ('walk', 'shop', 'clean')
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
transition_probability = {
                           'Rainy': {'Rainy': 0.7, 'Sunny': 0.3}
                           'Sunny': {'Rainy': 0.4, 'Sunny': 0.6}
                         }
emission_probability = {
                         'Rainy': {'walk': 0.1, 'shop': 0.4, 'clean': 0.5}
                         'Sunny': {'walk': 0.6, 'shop': 0.3, 'clean': 0.1}
                       }

Implementation in Python:

References:
hmmlearn
wikipedia

Activate Virtual Environment In PyCharm

Posted on Updated on

I create python projects so infrequently that whenever I need to create a new project or add a package to my Python base project I completely forget how to do it; so here goes…

In the terminal window of Pycharm type: source activate [environment-name]
conda

Then you can pip install the package info your environment
wheel

The end.

Single Linked List -Python

Posted on Updated on

My practice implementation of a single linked list in Python.

Using The Master Theorem To Find the Big O Of Recursive Algorithms

Posted on Updated on

For some persons finding the Big O of recursive algorithms can prove to be difficult especially if the algorithms are complexed. The Master Theorem provides a relatively simple way to solve recurrence relations as long as the recurrence fits the theorem constraints.

Basic definition:
T(n) = aT(n/b) + f(nc) where a >= 1, b > 1, and c >= 1
T(n) = Θ(nc) if c >= logba
T(n) = Θ(nc log n) if c = logba
T(n) = Θ(nlogba) if c < logba

We can think of “b” as the number of branches and “a” as the number of recurrences done; lets take a look at the example.

If we have a function:

T(n) = 2T(n/1) + f(n0) : a = 1, b = 2, c = 0

log21 = 0 therefore c = logba which satisfies Θ(nclog n) = O(log n)

References:
anupcowkur.com
wikipedia.com

From MATLAB To Python

Posted on

MATLAB:

For many years MATLAB has been my primary tool for prototyping algorithms, because of its rich set of optimization functions and the AI tool box it has proven to be a valuable tool to have. However, It is not cheap and if you do not have a company to pay for license or attend a university that provides you with a license then you will have to find an alternative.

MATLAB is not a programming language rather its a tool that has as part of its framework a programming language called M language, this language has a lot of quirks and takes some getting use to, the other issue I found with MATLAB is that the functions while well documented do not seem to follow a standard in terms of parameters; on the whole while MATLAB is a good tool for prototyping and is used a lot in engineering and medical fields which are my core domain; However,I am forced to look for a cheaper/free alternative that will give me as much if not more tools than MATLAB now provides.

Python to the rescue:

Python is powerful… and fast;
plays well with others;
runs everywhere;
is friendly & easy to learn;
is Open

All these wonderful things make Python a big contender for my MATLAB replacement.

The first thing we want to do is install Python.
Next install my favurite Python IDE PyCharm
Create a new Python Project using PyCharm
Python project

How do we add packages to our project?
Python is nothing without its packages and two of my favourites are numpy and scipy. To add these packages simply download the Anaconda distribution and configure it to be your default python implementation.

pylibs

And here is my first piece of python code as taken from the python website 🙂

pyresult

All I need now is a good Python book and 2-4 months to delve into the language. Stay tuned for more posts on my Python journey. Happy coding!!

Introduction To Memoization

Posted on Updated on

From a previous post on recursion we see that sometimes the sub problems of a recursive solution are related or overlapping in certain ways, the Fibonacci number sequence has sub-problems which overlap. From the recursion tree we notice that most calculations repeat, which causes inefficiency in the algorithm.

Recursion Tree:
recursion tree

The solution for Fibonacci 4, 3, 2, 1 and 0 is repeated on the left and right of the recursion tree, which makes the algorithm very inefficiently. What if there was a way we could store values for previously calculated Fibonacci numbers so that in the event that we need those solutions we could find them O(1) without doing any calculations.

Memoization
In computingmemoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing[1] in a general top-down parsingalgorithm[2][3] that accommodates ambiguity and left recursion in polynomial time and space. Although related to caching, memoization refers to a specific case of this optimization, distinguishing it from forms of caching such as buffering or page replacement. In the context of some logic programming languages, memoization is also known as tabling;[4] see also lookup table more…

Original Algorithm:

def fib(num):
    if num < 2:return num     if num > 0 :return fib(num-1) + fib(num-2)

Memoized Version:

cache = {}
def fib(num):
    if num in cache:
        return cache[num]
    else:
        cache[num] = num if num < 2 else fib(num-1) + fib(num-2)
        return cache[num]

Pruned Recursion Tree:
pruned
The red lines on the above diagram shows the pruning on the recursion tree caused by the memoization of the algorithm. The algorithm is now much more efficient because it no longer needs to traverse the recursion tree for a value which has already been calculated. Until next time have fun 🙂

Refrences
Wikipedia.com

Recursion in Computer Science

Posted on Updated on

Recursion, though important is frequently overlooked by programmers who do not understand its potential and place in algorithm design. It allows the expression of some problems in a very elegant and succinct manner, problems such as the famous Fibonacci number sequence are better understood and written with the aid of recursion. We will go through a few algorithms that employ It in an attempt to explain its function in a clear and concise manner.

I will be using python in this post because its a scripting language and therefore there is no need to recompile while testing my code. If you do not have python on you machine you can get it here python;  python IDE .

“A picture is worth a thousand words” is certainly true for this photo, in order for recursion to work there has to be at least one base case. The algorithm can have multiple base cases each of which is responsible for a particular state in which the algorithm may be in at each step. So lets look at our first example of a simple recursive function written in python.

Counting backwards from 10 to 0

def countDescending(num):
     print num
     if num == 0: return
     countDescending(num - 1)

Analysis

  1. The countDescending accepts a number as input then prints that number
  2. Base case: When num = 0 return from the function.
  3. Recursive step:The function calls itself with the input being reduced by 1

NB* All recursive solutions the initial problem must be one that can be broken down into simpler  problems, which eventually leads to the base case. Also to note, each function  call along  with scoped non-static variables are held on the stack until the base case is reached at which point the stack is unwound and the resources released.

Fibonacci Number

def fib(num):
    if num < 2:return num
    if num > 0 :return fib(num-1) + fib(num-2)

Analysis

Fibonacci Number sequence: 0, 1, 1, 2, 3, 5, 8
Recursive formula: \displaystyle f_{n} = \sum_{n=1}^{8} (n-1)+(n-2)
Base case: If input is less than 2 return the original input.
Recursive step: If input greater than 0 call fib with number – 1 and number – 2
Recursion Tree:

A recursion tree allows us to gain insight into the workings of a recursive algorithm, the above diagram shows the recursion tree for the Fibonacci number  8. From it we note that there is lot of repetition in calculation, this could be avoided with the use momoization which we will discuss in a future article.