Sébastien Giguère

Algorithms for the Hard Pre-Image Problem of String Kernels and the General Problem of String Prediction

We address the pre-image problem encountered in structured output prediction and the one of finding a string maximizing the prediction function of various kernel-based classifiers and regressors. We demonstrate that these problems reduce to a common combinatorial problem valid for many string kernel…