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