|
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 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 w_C(c). The value \max\ is called the teaching dimension of ''C''. Computational learning theory {{Compu-AI-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 mainly deal with a type of inductive learning called supervised learning. In supervised learning, an algorithm is given samples that are labeled in some useful way. For example, the samples might be descriptions of mushrooms, and the labels could be whether or not the mushrooms are edible. The algorithm takes these previously labeled samples and uses them to induce a classifier. This classifier is a function that assigns labels to samples, including samples that have not been seen previously by the algorithm. The goal of the supervised learning algorithm is to optimize some measure of performance such as minimizing the number of mistakes made on new samples. In addition to performance bounds, computational learning theory studies the t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 terminology frequently appears in model theory associated with probably approximately correct (PAC) learning. In this setting, if one takes a set ''Y'' as a set of (classifier output) labels, and ''X'' is a set of examples, the map , i.e. from examples to classifier labels (where and where ''c'' is a subset of ''X''), ''c'' is then said to be a ''concept''. A ''concept class'' is then a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Teaching Dimension
In computational learning theory, the teaching dimension of a concept class ''C'' is defined to be \max_\, where is the minimum size of a witness set for ''c'' in ''C''. Intuitively, this measures the number of instances that are needed to identify a concept in the class, using supervised learning 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, 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 Combinato ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |