Implementation of a sparse Markov Chain

Question

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
                    _sparseMC[p1].Add(p2, 1);
            }
            else
            {
                _size++;
                if (!_sparseMC.ContainsKey(p2))
                    _size++;
                Dictionary<T, int> nd = new Dictionary<T, int>();
                nd.Add(p2, 1);
                _sparseMC.Add(p1, nd);
                _countEltLeaving.Add(p1, 1);
            }
        }

        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;
        }
    }
}

Answer 1

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>();
nd.Add(p2, 1);
_sparseMC.Add(p1, nd);

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[p1].Add(p2, 1);
}

---

_sparseMC and _countEltLeaving can be made readonly.

Answer 2

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()
{
    _sparseMC.Add(1, new Dictionary<int, int>());
    _sparseMC[1].Add(1, 1);
    _countEltLeaving.Add(1, 1);
}

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 :)

Answer 3

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.