En la teoría del aprendizaje computacional , las dimensiones de exclusión de muestras surgen en el estudio del aprendizaje de conceptos exactos con consultas. [1]
En la teoría del aprendizaje algorítmico , un concepto sobre un dominio X es una función booleana sobre X . Aquí solo consideramos dominios finitos. Una aproximación parcial S de un concepto c es una función booleana sobrede tal manera que c es una extensión de S .
Sea C una clase de conceptos yc un concepto (no necesariamente en C ). A continuación, un conjunto especificando para c wrt C , denotado por S es una aproximación parcial S de c tal que C contiene a lo sumo una extensión a S . Si hemos observado un conjunto de especificación para algún concepto wrt C , entonces tenemos suficiente información para verificar un concepto en C con como máximo un cambio de mente más.
La dimensión de exclusión , denotado por XD ( C ), de una clase concepto es el máximo del tamaño del mínimo especificando conjunto de c 'con respecto a C , donde c ' es un concepto no en C .
Referencias
- ^ D. Angluin (2001). "Consultas revisadas". En N. Abe; R. Khardon; T. Zeugmann (eds.). Teoría del aprendizaje algorítmico: 12ª Conferencia Internacional, ALT 2001, Washington, DC, EE. UU., Noviembre de 2001, Actas . Saltador. pp. 26 -28. ISBN 3-540-42875-5.