Teaching dimension

In computational learning theory, the teaching dimension of a concept class C is defined to be $\backslash max\_\{c\backslash in\; C\}\backslash \{w\_C(c)\backslash \}$, where $\{w\_C(c)\}$ 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,{{cite journal

| last1 = Goldman | first1 = Sally A. | author1-link = Sally Goldman

| last2 = Kearns | first2 = Michael J. | author2-link = Michael Kearns (computer scientist)

| doi = 10.1006/jcss.1995.1003

| issue = 1

| journal = Journal of Computer and System Sciences

| mr = 1322630

| pages = 20–31

| title = On the complexity of teaching

| volume = 50

| year = 1995| doi-access = free

}} based on earlier work by Goldman, Ron Rivest, and Robert Schapire.{{cite journal

| last1 = Goldman | first1 = Sally A. | author1-link = Sally Goldman

| last2 = Rivest | first2 = Ronald L. | author2-link = Ron Rivest

| last3 = Schapire | first3 = Robert E. | author3-link = Robert Schapire

| doi = 10.1137/0222062

| issue = 5

| journal = SIAM Journal on Computing

| mr = 1237160

| pages = 1006–1034

| title = Learning binary relations and total orders

| volume = 22

| year = 1993}}

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

:$2^k\{|X|\backslash choose\; 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,{{cite journal

| last = Balbach | first = Frank J.

| doi = 10.1016/j.tcs.2008.02.025

| issue = 1–3

| journal = Theoretical Computer Science

| mr = 2401488

| pages = 94–113

| title = Measuring teachability using variants of the teaching dimension

| volume = 397

| year = 2008}} recursive teaching (RT),{{cite journal|last=Sandra Zilles, Steffen Lange, Robert Holte, and Martin Zinkevich|title=Models of cooperative teaching and learning|journal=Journal of Machine Learning Research|year=2011|volume=12|pages=349–384}} preference-based teaching (PBT),{{cite journal|last=Ziyuan Gao, Christoph Ries, Hans Ulrich Simon, and Sandra Zilles|title=Preference-based teaching|journal=Journal of Machine Learning Research|year=2017|volume=18|arxiv=1702.02047 }} and non-clashing teaching (NCT).{{cite journal|last=Kirkpatrick, Hans U Simon, and Sandra Zilles|title=Optimal collusion-free teaching|journal=Algorithmic Learning Theory|year=2019|pages=506–528|arxiv=1903.04012 }}