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

\max_\

, 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 Sally Ann Goldman is an American computer scientist specializing in computational learning theory. She was a professor in the Department of Computer Science and Engineering at Washington University in St. Louis, and Edwin H. Murty Professor of En ...

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 Int ...

, 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 Member may refer to: * Military jury, referred to as "Members" in military jargon * Element (mathematics), an object that belongs to a mathematical set * In object-oriented programming, a member of a class ** Field (computer science), entries in ...

of the concept class. In

Stasys Jukna Stasys is a popular Lithuanian given name, derived from Slavic name Stanislav. Feminine variation is Stasė. *Stasys Antanas Bačkis (1906–1999), Lithuanian diplomat *Stasys Eidrigevičius (born 1949), graphic artist *Stasys Girėnas (1893–193 ...

'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 :

2^k,

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