Learnability

Learnability is a concept used across disciplines to describe the extent to which a learner can acquire a target concept, skill, or behavior from data or experience. In machine learning and statistical learning theory, learnability asks whether a given class of target functions can be reliably inferred from finite samples.

A central framework is Probably Approximately Correct (PAC) learning, introduced by Valiant. PAC theory studies whether an algorithm can, with high probability, produce a hypothesis that approximates the true target function within a specified error, given enough data. In the realizable setting, a key result is that a concept class is PAC-learnable if and only if it has finite VC dimension, a measure of a class’s complexity. When data are noisy or the realizable assumption does not hold, agnostic learning or distribution-free learning addresses the achievable guarantees and typically requires larger sample sizes.

Related ideas include online learning, where learnability is framed in terms of regret or cumulative performance over time, and No Free Lunch theorems, which show that no algorithm can be universally superior when averaged over all possible problems.

In linguistics, learnability concerns how children acquire their language from imperfect and limited input. Questions focus on whether language can be learned under plausible data constraints without assuming extensive innate knowledge. Classic results such as Gold’s identification in the limit have spurred ongoing debate about the role of innate biases and the nature of linguistic evidence.

Practically, learnability informs algorithm design, data collection, and expectations about generalization. It highlights how assumptions about data, noise, and the target notion influence what can be learned and how efficiently learning can proceed.