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 d