Markov Models and Hidden Markov Models

In this post will give introduction to Markov models and Hidden Markov models as mathematical abstractions, with some examples.

In probability theory, a Markov model is a stochastic model that assumes the Markov property. A stochastic model models a process where the state depends on previous states in a non-deterministic way. A stochastic process has the Markov property if the conditional probability distribution of future states of the process.

	System state is fully observable	System state is partially observable
System is autonomous	Markov chain	Hidden Markov model
System is controlled	Markov decision process	Partially observable Markov decision process

Markov chain

A Markov chain named by Andrey Markov, is a mathematical system that representing transitions from one state to another on a state space. The state is directly visible to the observer. It is a random process usually characterized as memoryless: the next state depends only on the current state and not on the sequence of events that preceded it. This specific kind of "memorylessness" is called the Markov property.

Let's talk about the weather. we have three types of weather sunny, rainy and cloudy.

Let's assume for the moment that the weather lasts all day and it does not change from rainy to sunny in the middle of the day.

Weather prediction is try to guess what the weather will be like tomorrow based on a history of observations of weather

simplified model of weather prediction
Wewill collect statistics on what the weather was like today based on what the weather was like yesterday the day before and so forth. We want to collect the following probabilities.

Using above expression, we can give probabilities of types of weather for tomorrow and the next day using n days of history.

The larger n will be problem in here. The more statistics we must collect Suppose that n=5 then we must collect statistics for 3⁵ = 243 past histories Therefore we will make a simplifying assumption called the "Markov Assumption".

This is called a "first-order Markov assumption" since we say that the probability of an observation at time n only depends on the observation at time n-1. A second-order Markov assumption would have the observation at time n depend on n-1 and n-2. We can the express the joint probability using the “Markov assumption”.

So this now has a profound affect on the number of histories that we have to find statistics for, we now only need 3² = 9 numbers to characterize the probabilities of all of the sequences. (This assumption may or may not be a valid assumption depending on the situation.)

Arbitrarily pick some numbers for P (w_tomorrow | w_today).

Tabel2: Probabilities of Tomorrow's weather based on Today's Weather

“What is w0?” In general, one can think of w as the START word so P(w1w2) is the probability that w1 can start a sentence.

For first-order Markov models we can use these probabilities to draw a probabilistic finite state automaton.

eg:

1. Today is sunny what's the probability that tomorrow is sunny and the day after is rainy

First we translates into

P(w2= sunny,w3=rainy|w1=sunny)

P(w2= sunny,w3=rainy\|w1=sunny)	= P(w2=sunny\|w1=sunny) * P(w3=rainy\|w2=sunny,w3sunny)
	= P(w2=sunny\|w1=sunny) * P(w3=rainy\|w2=sunny)
	= 0.8 * 0.05
	=0.04

Hidden Markov model

A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved (hidden) states. A HMM can be considered the simplest dynamic Bayesian network. Hidden Markov models are especially known for their application in temporal pattern recognition such as speech, handwriting, gesture recognition, part-of-speech tagging, musical score following, partial discharges and bioinformatics.

Example

Well suppose you were locked in a room for several days and you were asked about the weather outside The only piece of evidence you have is whether the person who comes into the room carrying your daily meal is carrying an umbrella or not.

Table 3: Probabilities of Seeing an Umbrella

The equation for the weather Markov process before you were locked in the room.

Now we have to factor in the fact that the actual weather is hidden from you We do that by using Bayes Rule.

Where u_i is true if your caretaker brought an umbrella on day i and false if the caretaker did not. The probability P(w₁,..,w_n) is the same as the Markov model from the last section and the probability P(u₁,..,u_n) is the prior probability of seeing a particular sequence of umbrella events.

The probability P(w₁,..,w_n|u₁,..,u_n) can be estimated as,

Assume that for all i given w_i, u_i is independent of all u_j and w_j. I and J not equal

Next post will explain about “Markov decision process” and “Partially observable Markov decision process”.

We used have Singleton Design Pattern in our applications whenever it is needed. As we know that in singleton design pattern we can create only one instance and can access in the whole application. But in some cases, it will break the singleton behavior.

There are mainly 3 concepts which can break singleton property of a singleton class in java. In this post, we will discuss how it can break and how to prevent those.

Here is sample Singleton class and SingletonTest class.

Singleton.Java

package demo1;

public final class Singleton {

    private static volatile Singleton instance = null;

    private Singleton() {
    }

    public static Singleton getInstance() {
        if (instance == null) {
            synchronized (Singleton.class) {
                if (instance == null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

SingletonTest.java

package demo1;

public class SingletonTest {
    public static void main(String[] args) {
        Singleton object1 = Singleton.getInstance();
        Singleton object2 = Singleton.getInstance();
        System.out.println("Hashcode of Object 1 - " + object1.hashCode());
        System.out.println("Hashcode of Object 2 - " + object2.hashCode());
    }
}

Here is output, you can see it the same hashcode for objectOne and objectTwo

Hashcode of Object 1 - 1836019240
Hashcode of Object 2 - 1836019240

Now we will break this pattern. First, we will use java reflection.

Reflection

Java Reflection is an API which is used to examine or modify the behavior of methods, classes, interfaces at runtime. Using Reflection API we can create multiple objects in singleton class. Consider the following example.

ReflectionSingleton.java

package demo1;

import java.lang.reflect.Constructor;

public class ReflectionSingleton {
    public static void main(String[] args)  {

        Singleton objOne = Singleton.getInstance();
        Singleton objTwo = null;
        try {
            Constructor constructor = Singleton.class.getDeclaredConstructor();
            constructor.setAccessible(true);
            objTwo = (Singleton) constructor.newInstance();
        } catch (Exception ex) {
            System.out.println(ex);
        }

        System.out.println("Hashcode of Object 1 - "+objOne.hashCode());
        System.out.println("Hashcode of Object 2 - "+objTwo.hashCode());

    }
}

Example to show how reflection can break the singleton pattern with Java reflect. You will get two hash code as below. It has a break on the singleton pattern.

Hashcode of Object 1 - 1836019240
Hashcode of Object 2 - 325040804

Prevent Singleton pattern from Reflection

There are many ways to prevent Singleton pattern from Reflection API, but one of the best solutions is to throw run time exception in the constructor if the instance already exists. In this, we can not able to create a second instance.

    private Singleton() {
        if( instance != null ) {
           throw new InstantiationError( "Creating of this object is not allowed." );
        }
    }

Deserialization

In serialization, we can save the object of a byte stream into a file or send over a network. Suppose if you serialize the Singleton class and then again de-serialize that object will create a new instance, hence deserialization will break the Singleton pattern.

Below code is to illustrate how the Singleton pattern breaks with deserialization.

Implements Serializable interface for Singleton Class.

DeserializationSingleton.Java

package demo1;

import java.io.*;

public class DeserializationSingleton {

    public static void main(String[] args) throws Exception {

        Singleton instanceOne = Singleton.getInstance();
        ObjectOutput out = new ObjectOutputStream(new FileOutputStream("file.text"));
        out.writeObject(instanceOne);
        out.close();

        ObjectInput in = new ObjectInputStream(new FileInputStream("file.text"));
        Singleton instanceTwo = (Singleton) in.readObject();
        in.close();

        System.out.println("hashCode of instance 1 is - " + instanceOne.hashCode());
        System.out.println("hashCode of instance 2 is - " + instanceTwo.hashCode());
    }

}

The output is below and you can see two hashcodes.

hashCode of instance 1 is - 2125039532
hashCode of instance 2 is - 381259350

Prevent Singleton Pattern from Deserialization

To overcome this issue, we need to override readResolve() method in Singleton class and return same Singleton instance. Update Singleton.java, with below method.

   protected Object readResolve() { 
           return instance; 
     }

Now run above DeserializationDemo class and see the output.

hashCode of instance 1 is - 2125039532
hashCode of instance 2 is - 2125039532

Cloning

Using the "clone" method we can create a copy of original object, samething if we applied clone in singleton pattern, it will create two instances one original and another one cloned object. In this case will break Singleton principle as shown in below code.

Implement the "Cloneable" interface and override the clone method in the above Singleton class.

Singleton.java

    @Override
    protected Object clone() throws CloneNotSupportedException  {
        return super.clone();
    }

Then Test with cloning for breaking the singleton
CloningSingleton.java

public class CloningSingleton {
    public static void main(String[] args) throws CloneNotSupportedException, Exception {
        Singleton instanceOne = Singleton.getInstance();
        Singleton instanceTwo = (Singleton) instanceOne.clone();
        System.out.println("hashCode of instance 1 - " + instanceOne.hashCode());
        System.out.println("hashCode of instance 2 - " + instanceTwo.hashCode());
    }

}

Here is the output

hashCode of instance 1 - 1836019240
hashCode of instance 2 - 325040804

If we see the above output, two instances have different hashcodes means these instances are not the same.

Prevent Singleton Pattern from Cloning

In the above code, breaks the Singleton principle i. e created two instances. To overcome the above issue we need to implement/override clone() method and throw an exception CloneNotSupportedException from clone method. If anyone try to create clone object of Singleton, it will throw an exception as see below code.

    @Override
    protected Object clone() throws CloneNotSupportedException  {
        throw new CloneNotSupportedException();
    }

Now we can run the CloningSingleton class, it will throw CloneNotSupportedException while creating a clone object of Singleton object.

Add a comment

Madhuka

Microservices, Java, DevOps, WSO2, Enterprise Solution, Enterprise Integration, SOA, EDA, Restful, C#, C++ tutorial, Ruby on rails, API Manager, jaggery, javascript, Madhuka

Reflection

Deserialization

Cloning

View comments