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 ...
, the teaching dimension of 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 ...
''C'' is defined to be
, where
is the minimum size of a
witness set
In computational learning theory, 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 ...
for ''c'' in ''C''. Intuitively, this measures the number of instances that are needed to identify a concept in the class, using
supervised learning
Supervised learning (SL) is a machine learning paradigm for problems where the available data consists of labelled examples, meaning that each data point contains features (covariates) and an associated label. The goal of supervised learning alg ...
with examples provided by a helpful teacher who is trying to convey the concept as succinctly as possible. This definition was formulated in 1995 by
Sally Goldman and
Michael Kearns,
based on earlier work by Goldman,
Ron Rivest
Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial In ...
, and
Robert Schapire
Robert Elias Schapire is an American computer scientist, former David M. Siegel '83 Professor in the computer science department at Princeton University, and has recently moved to Microsoft Research. His primary specialty is theoretical and app ...
.
The teaching dimension of a finite concept class can be used to give a lower and an upper bound on the
membership query cost of the concept class.
In
Stasys Jukna's book "Extremal Combinatorics", a lower bound is given for the teaching dimension in general:
Let ''C'' be a concept class over a finite domain ''X''. If the size of ''C'' is greater than
:
then the teaching dimension of ''C'' is greater than ''k''.
However, there are more specific teaching models that make assumptions about teacher or learner, and can get lower values for the teaching dimension. For instance, several models are the classical teaching (CT) model,
[ the optimal teacher (OT) model, recursive teaching (RT), preference-based teaching (PBT), and non-clashing teaching (NCT).]
References
Computational learning theory
{{robo-stub