C++ Implemetation and Sequence Prediction

[Moe]

Hi,

I was browsing the C++ implementation and I could not find a function interface for continueSequence similar to the one in the Java code. Is there a simple and efficient way to implement continueSequence in C++?

Thanks!

[Jan Gasthaus]

Hi Moe,

in the C++ implementation the same effect can be achieved by first
adding in the symbols to the underling sequence and then calling
insertContextAndObservation()
(https://github.com/jgasthaus/libPLUMP/blob/master/src/libplump/hpyp_model.h#L73)
where the first and second argument are the [start, end) interval
describing your context and the last argument is the symbol you want
add/predict.

E.g. if model is your HPYPModel, seq is your backing std::vector<int>,
and x is the observation you want to add/predict you can do:

seq.push_back(x);
double prob = model.insertObservationAndContext(0, seq.size() - 1, x)[0];

Hope this helps,

Jan

> --
> You received this message because you are subscribed to the Google Groups
> "Sequence Memoizer" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sequence-memoi...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Jan Gasthaus]

Slight correction:

On Tue, Jun 11, 2013 at 9:49 AM, Jan Gasthaus <jgas...@googlemail.com> wrote:
> double prob = model.insertObservationAndContext(0, seq.size() - 1, x)[0];

That in fact should be

double prob = model.insertContextAndObservation(0, seq.size() - 1, x).back();

It returns a vector of probabilities which are the predictions for the
given symbol for each node in the path from the root to the inserted
context. Also note that these are actual probabilities, not log-probs
as with continueSequence();

Jan

[Moe]

Hi Jan,

Thank you for the quick reply. Your comment was very helpful.

There is just one concern; to have a maximum likelihood estimate for the next symbol, we need to step through all the alphabet to get the probability estimates. However, algorithms like CTW use binary decomposition, i.e., a 256 alphabet is represented with 8 different trees for each bit. Hence, for a prediction with these algorithms we only need 8 updates (logarithmic in the size of alphabet). Is there a way to get an approximation on the next symbol probability distribution without doing 256 tree computations?

Thanks,

Moe

[Jan Gasthaus]

Hi Moe,

if you need to compute the entire predictive distribution in a given
context you can use the predictiveDistribution() method
(https://github.com/jgasthaus/libPLUMP/blob/master/src/libplump/hpyp_model.cc#L328).
This will be faster than calling predict() for every symbol in the
alphabet, as the path through the tree and the corresponding discount
and concentration parameters are only computed once. However, it still
scales linearly with the alphabet size -- and I don't really see an
obvious way around that. I suppose a similar form of binary
decomposition might be possible, but I doubt it would work so well.

Jan

[Moe]

Thank you Jan!