Learning hypertrees with shortest path queries

Abstract

One branch of computational learning theory focuses on algorithms for learning discrete structured objects from queries. In this context, we consider the problem of learning a labeled hypergraph from a given family of hypergraphs using shortest path (SP) queries. An SP query specifies two vertices and asks for their distance in the target hypergraph. For various classes H of hypertrees, we present bounds on the number of queries required to learn an unknown hypertree from H. Matching upper and lower asymptotic bounds are presented for learning hyperpaths and hyperstars. Moreover, inspired by Hein’s algorithm for learning evolutionary trees with bounded vertex degrees, we develop an efficient algorithm for learning any hypertree. The query complexity of the algorithm is bounded from above by a function linear in the edge degree. As part of this research, we also introduce the notion of bag graph, which is a new way to generalize a graph, and provide an efficient algorithm for learning certain bag trees with SP queries. The query complexity of the algorithm for learning bag trees is bounded from above by a function linear in the bag degree. This algorithm allows us to carry over ideas from Hein’s algorithm for learning trees to our task of learning hypertrees.