  Kernel methods on discrete domains have shown great promise for many
challenging data types, for instance, biological sequence data and molecular
structure data. Scalable kernel methods like Support Vector Machines may offer
good predictive performances but do not intrinsically provide uncertainty
estimates. In contrast, probabilistic kernel methods like Gaussian Processes
offer uncertainty estimates in addition to good predictive performance but fall
short in terms of scalability. While the scalability of Gaussian processes can
be improved using sparse inducing point approximations, the selection of these
inducing points remains challenging. We explore different techniques for
selecting inducing points on discrete domains, including greedy selection,
determinantal point processes, and simulated annealing. We find that simulated
annealing, which can select inducing points that are not in the training set,
can perform competitively with support vector machines and full Gaussian
processes on synthetic data, as well as on challenging real-world DNA sequence
data.
