Distance-based Learning of Hypertrees
By: Shaun Fallat , Kamyar Khodamoradi , David Kirkpatrick and more
Potential Business Impact:
Learns complex connections faster than before.
We study the problem of learning hypergraphs with shortest-path queries (SP-queries), and present the first provably optimal online algorithm for a broad and natural class of hypertrees that we call orderly hypertrees. Our online algorithm can be transformed into a provably optimal offline algorithm. Orderly hypertrees can be positioned within the Fagin hierarchy of acyclic hypergraph (well-studied in database theory), and strictly encompass the broadest class in this hierarchy that is learnable with subquadratic SP-query complexity. Recognizing that in some contexts, such as evolutionary tree reconstruction, distance measurements can degrade with increased distance, we also consider a learning model that uses bounded distance queries. In this model, we demonstrate asymptotically tight complexity bounds for learning general hypertrees.
Similar Papers
Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics
Machine Learning (CS)
Finds hidden groups in information, even if none exist.
Improved and Parameterized Algorithms for Online Multi-level Aggregation: A Memory-based Approach
Data Structures and Algorithms
Makes computer networks deliver data cheaper and faster.
On the Approximation of Phylogenetic Distance Functions by Artificial Neural Networks
Machine Learning (CS)
Helps scientists build family trees for living things.