On Polynomial-Time Probably almost Discriminative Learnability

Kenji YamanishiCOLT 1993 · DOI

TL;DR

This paper introduces and analyzes the "Probably Almost Discriminative" (PAD) learning criterion, a computational framework for distinguishing between two stochastic rules. The authors develop efficient algorithms and characterize classes of rules that are "polynomial-time PAD-learnable," meaning they can be distinguished efficiently with high probability. This work bridges the gap between theoretical discrimination and practical computational efficiency.

What Problem Does This Paper Address?

Imagine you have a stream of data, and you suspect it's generated by one of two underlying processes (stochastic rules). One process is known, but the other is unknown, belonging to a specific family of possibilities. The challenge is to efficiently determine which process is generating the data. This is the core of hypothesis testing, but the paper focuses on a computationally constrained version: can we do this discrimination in polynomial time with high accuracy? The authors tackle the problem of "Probably Almost Discriminative" (PAD) learning, which formalizes this computationally bounded discrimination task for stochastic rules. They aim to identify which families of these rules can be learned (distinguished) efficiently.

Methods

The paper proposes several novel approaches:

  • Efficient Discrimination Functions: For classes of "stochastic rules with finite partitioning" (rules defined by discrete partitions of the input space and probabilities), they develop new discrimination functions that are linear in sample size.
  • MDL-based Discrimination: For non-parametric classes with certain smoothness conditions, they show that an efficient Minimum Description Length (MDL)-based discrimination function can be constructed.
  • Relating PAC and PAD Learning: They establish a crucial link between "stochastic PAC-learnability" (a standard machine learning concept for probabilistic models) and PAD-learnability. They show that if a class is efficiently PAC-learnable, it can often be transformed into an efficient PAD-learning algorithm.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithm design rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Polynomial-Time PAD-Learnability is Achievable: The paper demonstrates that for certain classes of stochastic rules, efficient (polynomial-time) discrimination is indeed possible, going beyond theoretical guarantees to practical computational feasibility.
  • The Trade-off Between Accuracy and Efficiency: While general PAD-learning might be possible, achieving polynomial-time efficiency often requires restricting the acceptable level of accuracy (the "almost" in Probably Almost Discriminative). This is highlighted by the dependence on parameters like $\epsilon$ (accuracy) in the derived bounds.
  • Non-Parametric Rules are Tractable: The work extends to non-parametric rules (those not defined by a fixed set of parameters but by smoothness constraints), showing that efficient discrimination is still possible, with sample complexity related to the "index of resolvability."
  • PAC-to-PAD Transformation: The connection between PAC and PAD learning is a significant insight, suggesting that existing PAC learning algorithms can be leveraged to build PAD learning systems, broadening the applicability of known learning algorithms.

Key Results

  • Parametric Classes: For stochastic rules with finite partitioning, if the number of parameters is polynomial in the domain size, the class is polynomial-time PAD-learnable with respect to the Kullback-Leibler divergence, under certain accuracy constraints. This includes classes like k-stochastic decision lists and k-nearest neighbor stochastic decision trees.
  • Non-Parametric Classes: For once-differentiable stochastic rules bounded away from zero, an efficient MDL-based discrimination function exists. The sample complexity is related to Barron and Cover's "index of resolvability."
  • PAC-to-PAD: If a class of stochastic rules with finite partitioning is polynomial-time stochastic PAC-learnable, it is also polynomial-time PAD-learnable under certain conditions.

Limitations and Future Work

  • Accuracy Constraints: The derived polynomial-time PAD-learnability often comes with constraints on the accuracy parameter ($\epsilon$). The paper notes that the minimum value of the function $g(\alpha, \beta, \gamma, \xi)$ (related to accuracy) is still relatively high, suggesting room for improvement.
  • Separating PAC and PAD: A key open question is whether there exist classes that are polynomial-time PAD-learnable but not polynomial-time stochastic PAC-learnable. This would imply PAD learning offers unique advantages.
  • Amplifying PAD Learning: The paper suggests exploring methods to "amplify" PAD learning to improve the bounds on the accuracy parameter, similar to how weak learners are amplified in PAC learning.
  • Empirical Validation: While theoretical, the paper's findings would benefit from empirical validation on real-world datasets to assess the practical performance of the proposed algorithms.

Summary updated

BibTeX
@inproceedings{yamanishi1993polynomial,
  author = {Kenji Yamanishi},
  title = {{On Polynomial-Time Probably almost Discriminative Learnability}},
  booktitle = {Conference on Learning Theory},
  year = {1993},
  doi = {10.1145/168304.168316},
}
Figure