Dimensión de exclusión de la muestra

En la teoría del aprendizaje computacional , las dimensiones de exclusión de muestras surgen en el estudio del aprendizaje exacto de conceptos 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 sobre${\displaystyle Y\subsetequ X}$de tal manera que c es una extensión de S.

Sea C una clase de conceptos y c un concepto (no necesariamente perteneciente a C ). Entonces, un conjunto especificador para c con respecto a C , denotado por S, es una aproximación parcial S de c tal que C contiene como máximo una extensión a S. Si hemos observado un conjunto especificador para algún concepto con respecto a C , entonces tenemos suficiente información para verificar un concepto en C con como máximo un cambio de opinión adicional.

La dimensión de exclusión , denotada por XD ( C ), de una clase de concepto es el máximo del tamaño del conjunto mínimo de especificación de c ' con respecto a C , donde c ' es un concepto que no está en C .