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 Jerome Bruner, Bruner, Goodnow, & Austin (1967) as "the search for and listing of attributes that can be used to distinguish exemplars from ...
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