Predicting Switching Graph Labelings with Cluster Specialists

06/17/2018
by   Mark Herbster, et al.
0

We address the problem of predicting the labeling of a graph in an online setting when the labeling is changing over time. We provide three mistake-bounded algorithms based on three paradigmatic methods for online algorithm design. The algorithm with the strongest guarantee is a quasi-Bayesian classifier which requires O(t n) time to predict at trial t on an n-vertex graph. The fastest algorithm (with the weakest guarantee) is based on a specialist [10] approach and surprisingly only requires O( n) time on any trial t. We also give an algorithm based on a kernelized Perceptron with an intermediate per-trial time complexity of O(n) and a mistake bound which is not strictly comparable. Finally, we provide experiments on simulated data comparing these methods.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset