Pages

Hidden Markov Models

Monday, May 30, 2011

Nowadays, many applications use Hidden Markov Models (HMMs) to solve crucial issues such as bioinformatics, speech recognition, musical analysis, digital signal processing, data mining, financial applications, time series analysis and many others. HMMs are probabilistic models which are very useful to model sequence behaviours or discrete time series events. Formally it models Markov processes with hidden states, like an extension for Markov Chains. For computer scientists, is a state machine with probabilistic transitions where each state can emit a value with a given probability.

For better understanding HMMs, I will illustrate how it works with "The Fair Bet Casino" problem. Imagine you are in a casino where you can bet on coins tosses, tossed by a dealer. A coin toss can have two outcomes: head (H) or tail (T). Now suppose that the coin dealer has two coins, a fair (F) which outputs both H and T with 1/2 probabilities and a biased coin (B) which outputs H with probability 3/4 and T with 1/4. Using probability language we say:
  • P(H|F) = 1/2
  • P(T|F) = 1/2
  • P(H|B) = 3/4
  • P(T|B) = 1/4
Now imagine that the dealer changes the coin in a way you can't see, but you know that he does it with a 1/10 probability. So thinking the coin tosses as a sequence of events we can say:
  • P(Fi+1|Fi) = 9/10
  • P(Bi+1|Fi) = 1/10
  • P(Bi+1|Bi) = 9/10
  • P(Fi+1|Bi) = 1/10 
We can model it using a graph to illustrate the process:

HMM for "The Fair Bet Casino" problem

That's a HMM! It isn't any rocket science. Is just important to add a few remarks. We call the set of all possible emissions of the Markov process as the alphabet Σ ({H, T} in our problem). For many of computational method involving HMMs you will also need a initial state distribution π. For our problem we may assume that the we have equal probability for each coin.

Now comes in our mind what we can do with the model in our hands. There are lot's of stuff to do with it, such as: given a sequence of results, when the dealer used the biased coin or even generate a random sequence with a coherent behaviour when compared to the model.

There is a nice library called ghmm (available for C and Python) which handles HMMs and already gives us the most famous and important HMM algorithms. Unfortunately the python wrapper is not pythonic. Let's model our problem in python to have some fun:

import ghmm

# setting 0 for Heads and 1 for Tails as our Alphabet
sigma = ghmm.IntegerRange(0, 2)

# transition matrix: rows and columns means origin and destiny states
transitions_probabilities = [
    [0.9, 0.1], # 0: fair state
    [0.1, 0.9], # 1: biased state
]

# emission matrix: rows and columns means states and symbols respectively
emissions_probabilities = [
    [0.5, 0.5], # 0: fair state emissions probabilities
    [0.75, 0.25], # 1: biased state emissions probabilities
]

# probability of initial states
pi = [0.5, 0.5] # equal probabilities for 0 and 1

hmm = ghmm.HMMFromMatrices(

    sigma,
    # you can model HMMs with others emission probability distributions
    ghmm.DiscreteDistribution(sigma),    
    transitions_probabilities,
    emissions_probabilities,
    pi
)


>>> print hmm
DiscreteEmissionHMM(N=2, M=2)

  state 0 (initial=0.50)
    Emissions: 0.50, 0.50
    Transitions: ->0 (0.90), ->1 (0.10)

  state 1 (initial=0.50)
    Emissions: 0.75, 0.25
    Transitions: ->0 (0.10), ->1 (0.90)


Now that we have our HMM object on the hand we can play with it. Suppose you have the given sequence of coin tosses and you would like to distinguish which coin was being used at a given state:

tosses = [1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1]


The viterbi algorithm can be used to trace the most probable states at each coin toss according to the HMM distribution:

# not as pythonic is could be :-/
sequence = ghmm.EmissionSequence(sigma, tosses)

viterbi_path, _ = hmm.viterbi(sequence)

>>> print viterbi_path
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]


Nice! But sometimes is interesting to have the probability of each state on the point instead of only the most probable one. To have that, you must use the posterior or forward algorithms to have more detailed information.

states_probabilities = hmm.posterior(sequence)

>>> print
states_probabilities
[[0.8407944139086141, 0.1592055860913865], [0.860787703168127, 0.13921229683187356], ... ]

The posterior method result, returns the list of probabilities at each state, for example, in the first index we have [0.8407944139086141, 0.1592055860913865]. That means that we have ~0.84 probability of chance that the dealer is using the fair coin and ~0.16 for the biased coin. We also can plot a graph to show the behaviour of the curve of the probability of the dealer being using the fair coin (I used matplotlib for the graphs).

Probability of being a fair coin over time
This is only a superficial example of what can HMMs do. It's worthy give a look at it if you want do some sequence or time series analysis in any domain. I hope this post presented and cleared what are HMM and how they can be used to analyse data.

Sharing CodeCereal

Hi!

I've been recently included in the set of authors of this blog to bring you more AI content. I already write a blog called CodeCereal, and I write about AI and other stuff such as general development, computer graphics, open source technologies and whatever related to exact sciences and computing. As I write a lot about AI and this blog has already a awesome content and a bigger visibility, so I asked Marcel Caraciolo if I could join. And now here I am!

I'm an undergraduate student at the Federal University of Pernambuco, who loves science and to learn new stuff. I also an intern at Nokia Institute of Technology, and a KDE contributor (currently working at plasma). Ah! And I love white T-shirts.

Happy hacking!

Python and Machine Learning: Introductory Keynote in Portuguese


Dear readers,

I am sharing my last keynote at I Information Technology and Knowledge Management Symposium at IFPE (located at Recife, Pernambuco- Brazil) about Python and Machine Learning. It is a introductory keynote for students of that institution about machine learning and how Python is applied and useful for scientists, researchers and developers for building intelligent systems.

It is in portuguese.  The link for the slides.





Thanks for the the staff organization team for the opportunity.

Best regards,

Marcel Caraciolo

Introducing the Architecture REST - Creating APIs - Part 02

Monday, May 16, 2011



In this post, we continue talking about the REST architecture and our progress to create our first API.  This is the second part of the series, if you want to see the Introduction, please check this link

The SOA Principles

The REST is also considered a Service-Oriented Architecture (SOA) , so it the SOA principles must be considered. The REST architecture follows the interoperability by providing support for several types of response. It is a good practice to make your resource accept HTML, JSON or XML in the same method, turning it more portable.  Depending of the target of your application, the number of clients of your services can be bigger in this way. However, providing all those types of response consumes time, and you have to analyze if you are available for working on this interoperability.

It is also important that your RESTful services don't take overloaded operations. This includes heavy processing tasks such as data transformations (XML to JSON, XML to Text/Plain, etc.) as also the validation of the data before each transformation.  This results in the other principle of SOA the weak coupling, that is, make your system less dependent of other modules in order to reduce the modification effects and failure tailoring.  Generally the simple RESTful services systems are divided in the following packages:

  • resources -  The resources of your system which implement the HTTP methods POST, GET, PUT, DELETE. For each request received, it uses the modules of the utils package and the communication provided with dao, if necessary. The resources also have the task of interpret the result , possible failures and response to the client.
  • utils - The utility classes as also related to data transformation.
  • dao -  The classes with the pattern DAO (Data Access Object), responsible for the database transactions
It is also common to see the developers abuse of the methods POST and GET.  Using REST, the developer must know well the four main methods: POST, GET, PUT and DELETE.  We will explain in the next paragraphs about those and comment a little about the HEAD and OPTIONS. For illustrate the explanation, we will use a resource user implemented at http://www.example.com/resources/user/.



POST

Submit the data to be processed at a target resource, which can result in the creation of a new or an update of the existing resources. The data are included in the body of the request. For instance, making a request POST to http://www.example.com/resources/user/  and including the body represented by the JSON in the Figure 01, we will requesting to the server to add this new user. If the user was created successfully, the response will be with a status code 201, pointing that our resource was created.

Figure 1 - JSON as body

GET

Used to request a new representation of the resource specified. In practice, making a request GET in http://www.example.com/resources/user/10 will return as response the user whose the id is 10.  In the other hand if our request was to the url http://www.example.com/resources/user/ , we would have as response the list of all users.

PUT

]It updates the representation of the resource. The data must be sent in the body of the request. Besides, if the URI of the request doesn't not point out to a existing resource, it is allowed to create a new resource with this URI. In our example, if we wanted to update the password of the user with the login "marcelcaraciolo", we just need to make a PUT request to http://www.example.com/resources/user/10 putting the JSON body represented in the next figure, containing the refreshed data.

Figure 2 - JSON as body

DELETE

It deletes a specified resource. It doesn't have the body. If we request the DELETE method to URI http://www.example.com/resources/user/10 it would mean to the serve that we want it to delete the user with the id is equal to 10.

HEAD

Similar to the method GET, but without the body of the response. This method can be used to obtain the metadata of a entity target of the request, without transfer all the data (the body itself of the entity) to the client.

OPTIONS

Return the HTTP methods that the server supports for a specified URI. It can be used to check the features available of a web service. Making a request OPTIONS to http://www.example.com/resources/user/ , we would receive the attribute 'Allow' in the headers with the fields OPTIONS and POST. However making the request OPTIONS to the URI http://www.example.com/resources/user/* ,  we would receive the response OPTIONS, GET, PUT, DELETE and HEAD.  But wait, you may be asking yourself , where is the POST ? Is it missing ?  When you put the wildcat  (*) it is expected some response, but our method POST, using the good practices, is not mapped to accept requests with the URI finishing in 'user/*'.  In other words,  it doesn't make sense to request a POST to 'user/10' , since the id of the resource must be created by the serve. Besides that, in a OPTIONS request, in the body it will come the WADL file, which we will discuss later.

It is important to API developers to know that the client of the service represents the user. So, it is a convention to not use the methods GET and HEAD to do actions,  except the action of information recovering, therefore they are considered safe methods.

Although, knowing that the methods GET and HEAD are secure, the user are conscious about the fact that an action possibly insecure will be requested if it uses the other HTTP methods. To sum up, don't use GET and HEAD to make requests that generate collateral effects. So use the GET method to modify an entity is an anti-pattern and not a good practice in developing REST APIs.

Another important property is the idempotence. PUT, DELETE and OPTIONS are idempotent methods, that is, multiple operations must always return the same result and have the same effect in the application as  one. For instance, making several GET requests to the same URI, it will always return the same response, in case of the requested data didn't change in the interval between the requests.  Finally, the safe methods are indempotent, since it doest not present collateral effects.



HTTP Status Codes

The HTTP Status Codes were created to allow the developers to describe precisely for the clients what happened at the server or even have control of the services. For that, the more specified the response, better. 

The Status Codes has those meanings:

  • 1.xx -  Information
  • 2.xx - Success
  • 3.xx -  Redirect
  • 4.xx -  Client Error
  • 5.xx - Server Error
It is important to developers to know how to response properly with your services. Typically, the responses used by the REST services are 200, 404 or 500, but it is important to understand better the responses of other RESTful services that your application are consuming.  We will see some statuses  codes as follows.

200 - OK
The status code 200 represents that the request was successful. The response returned depends on the method used in the request. If the GET method is used, it will returned the entity corresponding to the requested resource.  In case of POST method, the headers will correspond to the requested resources. Finally if the method was HEAD, it will be returned the headers fields that correspond to the requested resources either.

201 - Created
The request was accomplished and the location of the resource created is returned by the field 'Location' in the response headers. The server must create the resource before return the status code 201. If the resource can't be created immediately, the server must response with 202 (Approved) instead.

202 - Accepted

The request was approved, but it doesn't mean that was finalized. Your purpose is to allow the server to accept asynchronous requests.  Depending on the scenario, it is interesting to include to the body of the response the current status of the request and a path to a state monitor or a time estimative to the request be accomplished.


204 - No Content
The server accomplished the request  successfully but it does not need to response any entity in the body.  Optionally, it may include new or updated meta-information about the the entities in the headers. The response 204 must not have the body. Generally it is the status code response to a DELETE request.

304 - No Modified
If the client has requested with a conditional GET method, but  the documents or the requested data weren't modified, the server must response with this status code. The response 304 must not have a body.

400 -  Invalid Request
Invalid Syntax in the request.

401 -  Not Authorized
The request requires authentication or the user has been refused by the credentials provided.

404 -  Not Found
The server didn't find the resources that correspond to the URI of the request. Generally this response comes as result of a GET request.

409 -  Conflict
There was a conflict in the request with the current state of the resource. This code is only allowed in situations where it expects that the user is able to solve the the conflict and re-send again the request.  For that, the body of the response must include an error message. Generally this scenario occurs in responses to PUT requests.

500 - Internal Server Error
The server came into a unexpected condition that stopped it of finishing the request. For instance, if a problem occurred with the database connection, the response must have the status code 500.


The table below provided gives you a resume of the most used http statuses codes when you are developing your RESTful services.  Please read carefully and know how to use it correctly in order to help the developers that will build applications that will consume your services and know how to handle properly the responses of your API.

HTTP protocol version 1.1 Server Response Codes

In the next post about the REST Services I will present a new service that I am developing using the concepts explained in this series of posts.  It will be related to Location + Question and Answers + Mobile + Python with real code of course! 

I hope you enjoyed,

Marcel Caraciolo

References

[2] http://www.w3.org/Protocols/rfc2616/rfc2616-sec10.html