Læringsdimensjon

Innen maskinlæringsteori er læringsdimensjonen til en konseptklasse C definert som , der  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 
 
så er læringsdimensjonen til C større enn k.

Informatikk