In computational learning theory, the teaching dimension of a concept class C is defined to be, where 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
then the teaching dimension of C is greater than k.
Famous quotes containing the words teaching and/or dimension:
“What is all wisdom save a collection of platitudes? Take fifty of our current proverbial sayings—they are so trite, so threadbare, that we can hardly bring our lips to utter them. None the less they embody the concentrated experience of the race and the man who orders his life according to their teaching cannot go far wrong.”
—Norman Douglas (1868–1952)
“By intervening in the Vietnamese struggle the United States was attempting to fit its global strategies into a world of hillocks and hamlets, to reduce its majestic concerns for the containment of communism and the security of the Free World to a dimension where governments rose and fell as a result of arguments between two colonels’ wives.”
—Frances Fitzgerald (b. 1940)