Proceedings Abstracts of the Twenty-Fifth International Joint Conference on Artificial Intelligence

Bounds for Learning from Evolutionary-Related Data in the Realizable Case / 1655
Ondřej Kuželka, Yuyi Wang, Jan Ramon

This paper deals with the generalization ability of classifiers trained from non-iid evolutionary-related data in which all training and testing examples correspond to leaves of a phylogenetic tree. For the realizable case, we prove PAC-type upper and lower bounds based on symmetries and matchings in such trees.