Learning hypertrees with shortest path queries

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.

Name thesis:degree_name

Master of Science (MSc)

Level thesis:degree_level

Master's

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

Faculty of Graduate Studies and Research, University of Regina

Year dc:date.issued

2025

Author dc:creator

• Maliuk, Valerii

Advisor dc:contributor.advisor

• Zilles, Sandra

Committee member dc:contributor.committeemember

• Yang, Boting

Language dc:language.iso

en

DOI

https://doi.org/10.82465/4533

OAI identifier oai:identifier

oai:uregina.scholaris.ca:10294/16845