# Implementation of a sparse Markov Chain

I need to create a sparse Markov chain. It is supposed to receive text, so the number of rows or columns can easily go up to 20000. Besides, if I want to consider higher orders of the Markov chain (creating pairs of consecutive words) the dimension can become much bigger. Hence the need to have something sparse.

I added the constraint to have a "uniform prior" on the transitions (so as to avoid having infinite log likelihood).

I am not sure this is the cleanest way to proceed.

using System.Collections.Generic;
using System;

namespace rossum.Machine.Learning.Markov
{
public class SparseMarkovChain<T>
{
private Dictionary<T, Dictionary<T, int>> _sparseMC = new Dictionary<T, Dictionary<T, int>>();
private Dictionary<T, int> _countEltLeaving = new Dictionary<T, int>();
private int _size = 0;

public double GetTransition(T p1, T p2)
{
if (_sparseMC.ContainsKey(p1))
{
if (_sparseMC[p1].ContainsKey(p2))
return (1f + _sparseMC[p1][p2]) / (_countEltLeaving[p1] + _size);
else
return 1f / (_countEltLeaving[p1] + _size);
}
else
return 1f / _size;
}

public void AddTransition(T p1, T p2)
{
if (_sparseMC.ContainsKey(p1))
{
_countEltLeaving[p1]++;
if (_sparseMC[p1].ContainsKey(p2))
_sparseMC[p1][p2] += 1;
else
}
else
{
_size++;
if (!_sparseMC.ContainsKey(p2))
_size++;
Dictionary<T, int> nd = new Dictionary<T, int>();
}
}

public double LogLikelihood(T[] path)
{
double res = 0;
for (int i = 1; i < path.Length; i++)
res += Math.Log(GetTransition(path[i - 1], path[i]));
return res;
}
}
}


If you're using ContainsKey, you're probably doing it wrong and you need to use Dictionary<TKey, TValue>.TryGetValue Method (TKey, TValue).

Your first method would then become:

public double GetTransition(T p1, T p2)
{
Dictionary<T, int> p1Value;
if (!_sparseMarkovChain.TryGetValue(p1, out p1Value))
{
return 1f/_size;
}

int p2Value;
if (p1Value.TryGetValue(p2, out p2Value))
{
return (1f + p2Value)/(_countEltLeaving[p1] + _size);
}

return 1f/(_countEltLeaving[p1] + _size);
}


Your naming could be improved. The "MC" in _sparseMC makes sense in context, but why not write "MarkovChain" in full? p1 and p2 aren't clear to me, but I don't know the convention.

These three lines could be a single one:

Dictionary<T, int> nd = new Dictionary<T, int>();


versus:

_sparseMC.Add(p1, new Dictionary<T, int>{{ p2, 1 }});


Use braces everywhere to avoid introducing bugs, even for code like this:

if (_sparseMC[p1].ContainsKey(p2))
{
_sparseMC[p1][p2] += 1;
}
else
{
}


_sparseMC and _countEltLeaving can be made readonly.

• I wouldn't say it's "conventional" to use braces everywhere - it is less bug-prone. – Der Kommissar Oct 22 '15 at 14:29
• @EBrown True, bad wording on my side. – BCdotWEB Oct 22 '15 at 14:33
• p1 and p2 are just points in the set on which I "train" my Markov chain. It could be point1 and point2 as well... Any other suggestion? – RUser4512 Oct 22 '15 at 15:17

In my other answer a discussion was born on the performance of 2 methods. In this answer I decided to post the code of the tests I ran for whom may be interested:

private static Dictionary<int, Dictionary<int, int>> _sparseMC = new Dictionary<int, Dictionary<int, int>>();
private static Dictionary<int, int> _countEltLeaving = new Dictionary<int, int>();
private static int _size = 0;

static void InitializeDictionaries()
{
}

public static TimeSpan TestGetTransition_OP(int accessRepetitions)
{
// "warmup" access
double methodResult = GetTransition_OP(1, 1);
Stopwatch sw = new Stopwatch();

sw.Start();

for(int i = 0; i < accessRepetitions; i++)
{
methodResult = GetTransition_OP(1, 1);
}

sw.Stop();

return sw.Elapsed;
}

public static TimeSpan TestGetTransition_GK(int accessRepetitions)
{
// "warmup" access
double methodResult = GetTransition_GK(1, 1);
Stopwatch sw = new Stopwatch();

sw.Start();

for(int i = 0; i < accessRepetitions; i++)
{
methodResult = GetTransition_GK(1, 1);
}

sw.Stop();

return sw.Elapsed;
}

public static TimeSpan TestGetTransition_BC(int accessRepetitions)
{
// "warmup" access
double methodResult = GetTransition_BC(1, 1);
Stopwatch sw = new Stopwatch();

sw.Start();

for(int i = 0; i < accessRepetitions; i++)
{
methodResult = GetTransition_BC(1, 1);
}

sw.Stop();

return sw.Elapsed;
}

public static double GetTransition_OP(int p1, int p2)
{
if (_sparseMC.ContainsKey(p1))
{
if (_sparseMC[p1].ContainsKey(p2))
return (1f + _sparseMC[p1][p2]) / (_countEltLeaving[p1] + _size);
else
return 1f / (_countEltLeaving[p1] + _size);
}
else
return 1f / _size;
}

public static double GetTransition_GK(int p1, int p2)
{
if (!_sparseMC.ContainsKey(p1))
{
return 1f / _size;
}
else if (_sparseMC[p1].ContainsKey(p2))
{
return (1f + _sparseMC[p1][p2]) / (_countEltLeaving[p1] + _size);
}
else
{
return 1f / (_countEltLeaving[p1] + _size);
}
}

public static double GetTransition_BC(int p1, int p2)
{
Dictionary<int, int> p1Value;
if (!_sparseMC.TryGetValue(p1, out p1Value))
{
return 1f/_size;
}

int p2Value;
if (p1Value.TryGetValue(p2, out p2Value))
{
return (1f + p2Value)/(_countEltLeaving[p1] + _size);
}

return 1f/(_countEltLeaving[p1] + _size);
}

static void Main()
{
int[] numberOfRepetitions = new int[]
{
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000
};

InitializeDictionaries();

for(int i = 0; i < numberOfRepetitions.Length; i++)
{
Console.WriteLine("Execution time for {0} repetitions:\tOP:{1}\tGK:{2}\tBC:{3}",
numberOfRepetitions[i],
TestGetTransition_OP(numberOfRepetitions[i]),
TestGetTransition_GK(numberOfRepetitions[i]),
TestGetTransition_BC(numberOfRepetitions[i]));
}
}


Cheers :)

I agree with what @BCdotWEB said. In the first point though you could continue using ContainsKey and if you want to just improve readability transform it from

    public double GetTransition(T p1, T p2)
{
if (_sparseMC.ContainsKey(p1))
{
if (_sparseMC[p1].ContainsKey(p2))
return (1f + _sparseMC[p1][p2]) / (_countEltLeaving[p1] + _size);
else
return 1f / (_countEltLeaving[p1] + _size);
}
else
return 1f / _size;
}


into something like the following:

    public double GetTransition(T p1, T p2)
{
if (!_sparseMC.ContainsKey(p1))
{
return 1f / _size;
}
else if (_sparseMC[p1].ContainsKey(p2)) // 'if (_sparseMC.ContainsKey(p1))' is implicit here
{
return (1f + _sparseMC[p1][p2]) / (_countEltLeaving[p1] + _size);
}
else // 'if (_sparseMC.ContainsKey(p1))' is implicit here also
{
return 1f / (_countEltLeaving[p1] + _size);
}
}


or, better yet IMO:

    public double GetTransition(T p1, T p2)
{
double result;

if (!_sparseMC.ContainsKey(p1))
{
result = 1f / _size;
}
else if (_sparseMC[p1].ContainsKey(p2)) // 'if (_sparseMC.ContainsKey(p1))' is implicit here
{
result = (1f + _sparseMC[p1][p2]) / (_countEltLeaving[p1] + _size);
}
else // 'if (_sparseMC.ContainsKey(p1))' is implicit here also
{
result = 1f / (_countEltLeaving[p1] + _size);
}

return result;
}


but if performance is key you should go with @BCdotWEB's version.

• It's not just a personal preference, TryGetValue is faster. – BCdotWEB Oct 22 '15 at 15:39
• By taking a look at the source code the ContainsKey method seems to do less operations :) – Gentian Kasa Oct 22 '15 at 15:50
• But OP doesn't just do ContainsKey, he also retrieves the value if the key is present, and does so for both p1 and p2. – BCdotWEB Oct 22 '15 at 15:55
• That's true, but if we want to consider all the benefits of each approach we have to consider also the creation of auxiliary objects and other actions that are involved in both versions... – Gentian Kasa Oct 22 '15 at 16:02
• @BCdotWEB you were right. I did some tests and your method was faster in all of them. I'm editing this answer and adding another one with the code of the tests in case anyone is interested. – Gentian Kasa Oct 22 '15 at 20:14