The N-Gram predictor can be improved by having a handler with several other predictors ranging from 1 to n, and obtaining the best possible action after comparing the best guess from each one of them.
We need to make some adjustments prior to implementing the hierarchical N-Gram predictor.
Add the following member function to the NGramPredictor class:
public int GetActionsNum(ref T[] actions)
{
string key = ArrToStrKey(ref actions);
if (!data.ContainsKey(key))
return 0;
return data[key].total;
}Just like the N-Gram predictor, building the hierarchical version takes a few steps:
- Create the new class:
using System; using System.Collections; using System.Text; public class HierarchicalNGramP<T> { public int threshold; public NGramPredictor<T>[] predictors; private int nValue; } - Implement the constructor for initializing member values:
public HierarchicalNGramP(int windowSize) { nValue = windowSize + 1; predictors = new NGramPredictor<T>[nValue]; int i; for (i = 0; i < nValue; i++) predictors[i] = new NGramPredictor<T>(i + 1); } - Define a function for registering a sequence, just like its predecessor:
public void RegisterSequence(T[] actions) { int i; for (i = 0; i < nValue; i++) { T[] subactions = new T[i+1]; Array.Copy(actions, nValue - i - 1, subactions, 0, i+1); predictors[i].RegisterSequence(subactions); } } - Finally, implement the function for computing the prediction:
public T GetMostLikely(T[] actions) { int i; T bestAction = default(T); for (i = 0; i < nValue; i++) { NGramPredictor<T> p; p = predictors[nValue - i - 1]; T[] subactions = new T[i + 1]; Array.Copy(actions, nValue - i - 1, subactions, 0, i + 1); int numActions = p.GetActionsNum(ref actions); if (numActions > threshold) bestAction = p.GetMostLikely(actions); } return bestAction; }
The hierarchical N-Gram predictor works almost exactly like its predecessor, with the difference being that it holds a set of predictors and computes each main function using its children. Registering sequences, or finding out the most likely future action, works by decomposing the set of actions and feeding the children with them.