Teaching dimension

Teaching dimension

In computational learning theory, the teaching dimension of a concept class "C" is defined to be max_{cin C}{w_C(c)}, where {w_C(c)} is the minimum size of a witness set for "c" in "C".

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:

Let "C" be a concept class over a finite domain "X". If the size of "C" is greater than :2^k{|X|choose k}, then the teaching dimension of "C" is greater than "k".


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Dimension Films — Industry Motion picture Founded November 25, 1992 Founder(s) Bob Weinstein Headquarters New York Cit …   Wikipedia

  • Teaching Mrs. Tingle — Infobox Film | name = Teaching Mrs. Tingle caption = director = Kevin Williamson producer = writer = Kevin Williamson starring =Katie Holmes Helen Mirren Barry Watson Marisa Coughlan music = cinematography = editing = distributor = Dimension… …   Wikipedia

  • Teaching Mrs. Tingle — Mrs. Tingle Mrs. Tingle ou Attention Madame Tingle! au Québec (Teaching Mrs. Tingle) est un film américain réalisé par Kevin Williamson, sorti en 1999. Sommaire 1 Synopsis 2 Fiche technique 3 Distribution …   Wikipédia en Français

  • Catholic social teaching — encompasses aspects of Catholic doctrine relating to matters dealing with the collective welfare of humanity. The foundations of modern Catholic social teaching are widely considered to have been laid by Pope Leo XIII s 1891 encyclical letter… …   Wikipedia

  • Fifth dimension — In physics and mathematics, a sequence of N numbers can be understood to represent a location in an N dimensional space. When N =5, the space consisting of all such locations is called the fifth dimension.Abstract five dimensional space occurs… …   Wikipedia

  • Mortification in Roman Catholic teaching — For an overview of corporal mortification in world religions, see Mortification of the flesh. For the theological doctrine, see Mortification (theology). For the Christian metal band, see Mortification (band). For the record label, see… …   Wikipedia

  • Witness set — In computational learning theory, let C be a concept class 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… …   Wikipedia

  • Bondy's theorem — is a theorem in computational learning theory that appear in a 1972 article by Adrian Bondy. The theorem is as follows:Let C be a concept class over a finite domain X . Then there exists a subset S of X with the size at most | C | − 1 such that S …   Wikipedia

  • Laborem Exercens — was an encyclical written by Pope John Paul II in 1981, on human work. It is part of a larger body of writings known as Catholic social teaching, that trace their origin to Rerum Novarum which was issued by Pope Leo XIII in 1891.External links*… …   Wikipedia

  • KABBALAH — This entry is arranged according to the following outline: introduction general notes terms used for kabbalah the historical development of the kabbalah the early beginnings of mysticism and esotericism apocalyptic esotericism and merkabah… …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”