Læringsdimensjon

Innen maskinlæringsteori er læringsdimensjonen til en konseptklasse C definert som $\max _{c\in C}\{w_{C}(c)\}$, der ${w_{C}(c)}$ er minstestørrelsen for en vitnemengde for c i C. Læringsdimensjonen til en endelig konseptklasse kan brukes til å gi en øvre og nedre grense for konseptklassens kostnad for medlemsforespørsel (membership query cost).

I Stasys Jukna's bok Extremal Combinatorics gis en nedre grense for læringsdimensjonen:

La C vere en konseptklasse over et endelig domene X. Hvis størrelsen til C er større enn

$2^{k}{|X| \choose k},$

så er læringsdimensjonen til C større enn k.