Abstract
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.
Introduction
A fundamental assumption in classical machine learning theory is that data points are Independent and Identically Distributed (iid). However, in biological and linguistic domains, data often exhibit significant dependencies due to shared evolutionary history. For instance, genomic sequences from different bacteria are related through a phylogenetic tree; traits inherited from a common ancestor create correlations among descendant leaves. Standard generalization bounds, such as those based on VC dimension, fail to account for these dependencies, potentially leading to catastrophic failure when training and testing sets are drawn from isolated branches. This work quantifies how tree topology and the specific placement of training and testing samples influence learnability.
The Evolutionary Model and Dataset Configurations
The study models evolution using a complete binary tree where the root represents a common ancestor. Each node represents an instance (e.g., a genome), and children are generated from parents via a conditional probability distribution. A "dataset configuration" is defined by labeling the tree's leaves as either training ($T$) or testing ($?$) samples.
To derive generalization bounds, the authors leverage tree automorphisms—structural symmetries that allow subtrees to be "flipped" without altering the underlying relationships. These symmetries are crucial for counting possible error configurations and determining how redundant specific data placements might be.
Theoretical Framework: Symmetries and Matchings
The paper introduces two primary methods for bounding error in the realizable case (where a hypothesis exists that perfectly fits the training data):
- Symmetry-Based Bounds: By analyzing the group of automorphisms of the tree that preserve the training set, the authors derive lower bounds on error. If the training and testing sets are separated by a high-level split, the error remains high regardless of sample size.
- Graph-Theoretic Matchings: Learnability is simplified into a matching problem. The authors look for disjoint paths connecting training leaves to testing leaves. The existence of many such "close" pairs facilitates better generalization.
Key Results and Insights
The research yields several critical insights into non-iid learning:
- Topology vs. Sample Size: Unlike the iid setting where more data typically improves performance, evolutionary learning is dominated by topology. A small number of well-distributed samples across the tree is often more valuable than a large number of samples from a single isolated sub-population.
- Upper and Lower Bounds: The authors provide a formula (Theorem 1) for the probability of high test error based on tree symmetries. For "well-mixed" configurations, they demonstrate that error bounds exhibit exponentially decaying tails, similar to iid bounds but scaled by the tree's matching factor.
- Expected Error: For interleaved configurations, the expected test error is bounded by $O(\frac{d \log |A|}{|A|})$, where $d$ is the VC dimension and $|A|$ is the number of leaves.
Conclusion and Future Work
This work establishes the first PAC-style generalization bounds for phylogenetic data, highlighting the "isolation penalty" incurred when training and testing sets are topologically distant. While these results focus on the realizable case and complete binary trees, they lay the groundwork for future research into agnostic learning (where no perfect hypothesis exists) and more complex, non-binary evolutionary structures.
Summary updated