  This paper presents novel generalization bounds for the multi-kernel learning
problem. Motivated by applications in sensor networks and spatial-temporal
models, we assume that the dataset is mixed where each sample is taken from a
finite pool of Markov chains. Our bounds for learning kernels admit
$O(\sqrt{\log m})$ dependency on the number of base kernels and $O(1/\sqrt{n})$
dependency on the number of training samples. However, some $O(1/\sqrt{n})$
terms are added to compensate for the dependency among samples compared with
existing generalization bounds for multi-kernel learning with i.i.d. datasets.
