In
computational learning theory
In computer science, computational learning theory (or just learning theory) is a subfield of artificial intelligence devoted to studying the design and analysis of machine learning algorithms.
Overview
Theoretical results in machine learning m ...
, sample exclusion dimensions arise in the study of exact
concept learning
Concept learning, also known as category learning, concept attainment, and concept formation, is defined by Bruner, Goodnow, & Austin (1967) as "the search for and listing of attributes that can be used to distinguish exemplars from non exemplars ...
with queries.
In
algorithmic learning theory
Algorithmic learning theory is a mathematical framework for analyzing
machine learning problems and algorithms. Synonyms include formal learning theory and algorithmic inductive inference. Algorithmic learning theory is different from statistica ...
, a ''concept'' over a domain ''X'' is a
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...
over ''X''. Here we only consider finite domains. A ''partial approximation'' ''S'' of a concept ''c'' is a Boolean function over
such that ''c'' is an extension to ''S''.
Let ''C'' be a class of concepts and ''c'' be a concept (not necessarily in ''C''). Then a ''specifying set'' for c w.r.t. ''C'', denoted by ''S'' is a partial approximation ''S'' of ''c'' such that ''C'' contains at most one extension to ''S''. If we have observed a specifying set for some concept w.r.t. ''C'', then we have enough information to verify a concept in ''C'' with at most one more mind change.
The ''exclusion dimension'', denoted by ''XD''(''C''), of a concept class is the maximum of the size of the minimum specifying set of ''c''
' with respect to ''C'', where ''c''
' is a concept not in ''C''.
References
Computational learning theory
{{comp-sci-theory-stub