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 ...
, let ''C'' be a
concept class In computational learning theory in mathematics, a concept over a domain ''X'' is a total Boolean function over ''X''. A concept class is a class of concepts. Concept classes are a subject of computational learning theory.
Concept class terminolog ...
over a domain ''X'' and ''c'' be a concept in ''C''. A subset ''S'' of ''X'' is a witness set for ''c'' in ''C'' if ''c''(''S'') verifies ''c'' (i.e., ''c'' is the only consistent concept with respect to ''c''(''S'')). The minimum size of a witness set for ''c'' is called the ''witness size'' or ''specification number'' and is denoted by
. The value
is called the
teaching dimension of ''C''.
Computational learning theory
{{Compu-AI-stub