BxD Primer Series: Markov Chain Neural Networks

Hey there ??

Welcome to BxD Primer Series where we are covering topics such as Machine learning models, Neural Nets, GPT, Ensemble models, Hyper-automation in ‘one-post-one-topic’ format. Today’s post is on?Markov Chain Neural Networks. Let’s get started:

The What:

Markov Chain Neural Networks (MCNNs) model the probabilistic relationship between sequential inputs. Unlike traditional neural networks that use fixed-size input vectors, MCNNs can handle variable-length input sequences by modeling the sequence as a Markov chain.

At a high level, MCNN consists of two main components: a neural network and a Markov chain.

• Markov chain is used to model the temporal dependencies between successive inputs
• Neural network is used to learn the connection between Markov chain state and the output

Markov chain defines a set of states, where each state represents a particular input or feature in sequence. It then defines a set of transition probabilities that determine the likelihood of moving from one state to another. These transition probabilities are learned from training data using maximum likelihood estimation or Bayesian inference. We have covered the core concepts of Markov chains in a previous edition, check?here.

Markov chain represents the probabilistic relationship between successive inputs in a sequence. In a Markov chain, the probability of transitioning from one state to another is dependent only on the current state and not on any previous states.

Neural network component of MCNN is used to map current state of Markov chain to an output prediction. This mapping is learned by adjusting the weights of neural network to minimize the difference between predicted and actual outputs in training data.

During prediction, Markov chain is used to estimate probabilities of transitioning to each possible next state, and neural network is used to predict the output given the estimated probabilities.

Order of Markov Chain:

In a first-order Markov Chain, the probability of transitioning to next state depends only on the current state, and not on any previous states. This means that the current state fully captures all relevant information needed to predict next state.

For example, say we are trying to predict the weather. In a first-order model, the probability of weather being sunny or rainy tomorrow depends only on whether it is sunny or rainy today. We don't need to consider any previous days' weather to make prediction.

In a higher-order Markov Chain, the probability of transitioning to next state depends on the current state as well as the?k?previous states, where?k?is the order of Markov chain.

For example, say we are trying to predict the likelihood of a patient developing a certain disease. In a higher-order model, the probability of developing disease tomorrow depends on the current health status of patient, as well as their health status in previous?k?days.

The How:

Workings of a Hopfield neural network:

Step 1: Define the Markov Chain:

• Start by defining the states and transition probabilities of the Markov chain.

Step 2:?Network Initialization:

• Initialize the neural network parameters, including the weight matrix?W?and the bias vector?b.
• These parameters determine the dynamics of the neural network.

Step 3:?State Initialization: Let?x(0) = [x_1(0), x_2(0), ... , x_N(0)]?be the initial state vector, where?x_i(0)?represents the initial (0’th) activation of?i’th?neuron.

Step 4:?State Update: At each time step?t, compute the new state vector?x(t)?using following equation:

Where

• W?is the weight matrix
• x(t?1)?is the previous state vector
• b?is the bias vector
• σ?is the activation function applied element-wise to the weighted sum.

Step 5:?Markov Chain Transition:

• State vector?x(t)?represents activations of neurons in Markov chain at time step?t.
• Transition probabilities determine the transition from current to next state.
• For each neuron?i, sample the next state?x_i(t+1)?based on the probabilities?p_ij?in transition matrix?P.

Step 6:?Repeat steps 4 and 5 for predefined number of time steps or until convergence.

Step 7:?Output:

• Final state vector?x(T)?represents the activations of neurons in Markov chain after?T?time steps.

Using Cases of?Markov Chain Neural Network:

Image Recognition:

• For tasks such as recognizing handwritten digits or identifying objects in natural images, there is a strong spatial correlation between neighboring pixels.
• First step is to represent the image as a sequence of pixels.
• Then use Markov chain to model the probabilistic relationship between adjacent pixels in sequence. Use neural network component to learn the weights of model based on a training dataset of labeled images.
• Convolutional layers can also be added prior to Markov chain to capture the local spatial dependencies between neighboring pixels in an image.

Text classification and sentiment analysis:

• Potential use for text classification by modeling the relationship between words in a sentence or document as a Markov chain.
• Labeled training data with set of text documents, each of which is assigned a category or label is typically used for training.
• First step is to preprocess the text data. This involves?tokenizing text?into words or other units of meaning, and then converting those tokens into a numerical representation that can be used as input to the neural network. This can be done using word embedding techniques or bag-of-words representation.
• Markov chain component of network uses the probabilities of transitioning between words to model the relationship between words in text. Hidden Markov model is typically used for this.
• Neural network component then uses the probabilities of transitioning between words to predict the category of text. This is typically done using softmax activation function, which converts the output of neural network into a probability distribution over possible categories.

Anomaly detection:

Goal here is to identify data points that deviate significantly from the norm in a dataset. It has many applications, such as detecting fraud in financial transactions, identifying defects in manufacturing processes, and monitoring health of complex IT systems.

• First MCNN network is trained on a dataset of normal behavior. The network learns patterns of normal sequence to create a probabilistic model of normal behavior.
• Use a sliding window where model is trained to predict the next input based on fixed-length window of previous inputs. If the Probability of next input to be same as actual value is significantly low than the input is flagged as an anomaly.

Recommendation systems:

• Train a Markov Chain on user behavior data, such as user clicks, purchases, or ratings, to model the probability distribution of item transitions in the sequence.
• Neural Network component is then trained to predict the next item in sequence based on the current state of Markov Chain.

Time-series forecasting:

• Input sequence is modeled as a Markov chain, where each state represents a data point in sequence, and the probability of transitioning from one state to another is based on the current state.
• Neural network component is then used to map current state to the predicted output value.
• Use a sliding window approach where the MCNN is trained on a window of data points in time series and then used to predict the next value in series.
• Window is then shifted by one data point, and the MCNN is trained on new window of data points. This process is repeated until the entire time series has been processed.

The Why:

Reasons for Using Markov Chain Neural Networks:

1. Well-suited for modeling sequential data, where the current state depends on previous state. Markov chain component allows for capturing the dynamics of sequential data, while neural network component allows for making predictions based on the current state.
2. Can capture long-term dependencies in sequential data by learning transition probabilities between different states in Markov chain.
3. Can handle variable length sequences, where the length of input sequence vary from one example to another. This is because the Markov chain component only depends on current state, rather than the entire input sequence.
4. Can be used to combine multiple modalities of data, such as audio and video, by modeling each modality as a separate Markov chain and combining predictions from each modality using a neural network.

The Why Not:

Reasons for Not Using Markov Chain Neural Networks:

1. Have a limited memory and can only capture dependencies up to a certain number of time steps in past.
2. Makes the assumption that current state only depends on previous state, and not on any other context.
3. Have limited representational power and may not be able to capture complex patterns in data.
4. May not be scalable to large state spaces or long sequences because of data and computational requirements.

Time for you to support:

1. Reply to this email with your question
2. Forward/Share to a friend who can benefit from this
3. Chat on Substack with BxD (here)
4. Engage with BxD on LinkedIN (here)

In next edition, we will cover Hopfield Neural Networks.

Let us know your feedback!

Until then,

Have a great time! ??

#businessxdata?#bxd?#Markov #Chain #neuralnetworks?#primer