Learnability with Respect to Fixed Distributions
By G. M. Benedek, A. Itai. 1991
Consider a first order typed language, with semantics $S$ for expressions and types. Adding subtyping means that a partial order $<$; on types is defined and that the typing rules are extended to the effect that expression $e$ has type $t$ whenever $e$ has type $s$ and $s<t$ We show how to adapt the semantics $S$ in a simple set theoretic way, obtaining a semantics $S'$ that satisfies, in addition to some obvious requirements, also the property that: $S'~s$ is included in $S'~t$, whenever $s < t$.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Yoshua Bengio
- Sergey Levine
- Percy Liang
- Dacheng Tao
- Ruslan Salakhutdinov
- Trevor Darrell
- Bernt Schiele
- Quoc V. Le
Citations in the corpus
- Stealing Machine Learning Models via Prediction APIs (2016, background): “Our work is related to the extensive literature on learning theory, such as PAC learning [53] and its variants [3, 8].”
- Benign overfitting in linear regression (2019, background): “The proof of the following lemma borrows heavily from [15].”
- Adaptive computation and machine learning (1998, background): “By standard bounds (see for instance [Benedek and Itai, 1991]), the number of labeled examples is enough to ensure that with probability ≥ 1− δ/2 the empirical optimum hypothesis in G has true error at most 10 .”
- Tight Sample Complexity of Large-Margin Learning (2010, background): “Benedek and Itai [8] show that if the distribution is known tothe learner, a specific hypothesis class is learnable if and only if there is a finiteǫ-cover of this hypothesis class with respect to the distribution.”
- Does Unlabeled Data Provably Help? Worst-case Analysis of the Sample Complexity of Semi-Supervised Learning (2008, methodology): “K ¨ a ¨ ari ¨ ainen [12] proposes a method for semi-supervised learning without prior assumption on the conditional label distributions.”
- Rigorous Learning Curve Bounds from Statistical Mechanics (2005, background): “Perhaps the most striking evidence for the fact that the VC bounds can sometimes fail to model the true behavior of learning curves has come from statistical physics.”
- The importance of convexity in learning with squared loss (1998, result): “lemma follows from a similar proof to that of the main result in [ 7 ].”