Clase de concepto

En la teoría del aprendizaje computacional en matemáticas , un concepto sobre un dominio X es una función booleana total sobre X. Una clase de concepto es una clase de conceptos. Las clases de concepto son un tema de la teoría del aprendizaje computacional .

La terminología de clase de concepto aparece frecuentemente en la teoría de modelos asociada con el aprendizaje probablemente aproximadamente correcto (PAC). ^[1] En este contexto, si uno toma un conjunto Y como un conjunto de etiquetas (salida del clasificador), y X es un conjunto de ejemplos, el mapa , es decir, de ejemplos a etiquetas de clasificador (donde y donde c es un subconjunto de X ), se dice entonces que c es un concepto . Una clase de concepto es entonces una colección de tales conceptos. ${\displaystyle c:X\to Y}$${\displaystyle Y=\{0,1\}}$ ${\displaystyle C}$

Dada una clase de conceptos C , una subclase D es alcanzable si existe una muestra s tal que D contiene exactamente aquellos conceptos en C que son extensiones de s . ^[2] No todas las subclases son alcanzables. ^{[2] [ ¿por qué? ]}

Una muestra es una función parcial de ^{[ aclaración necesaria ]} a . ^[2] Al identificar un concepto con su función característica que se asigna a , es un caso especial de una muestra. ^[2]${\displaystyle s}$${\displaystyle X}$${\displaystyle \{0,1\}}$${\displaystyle X}$${\displaystyle \{0,1\}}$

Dos muestras son consistentes si coinciden en la intersección de sus dominios. ^[2] Una muestra extiende otra muestra si las dos son consistentes y el dominio de está contenido en el dominio de . ^[2]${\displaystyle s'}$ ${\displaystyle s}$${\displaystyle s}$${\displaystyle s'}$

Supongamos que . Entonces: ${\displaystyle C=S^{+}(X)}$

• La subclase es alcanzable con la muestra ; ^{[2] [ ¿por qué? ]}${\displaystyle \{\{x\}\}}$${\displaystyle s=\{(x,1)\}}$
• Las subclases de son alcanzables con una muestra que asigna los elementos de a cero; ^{[2] [ ¿por qué? ]}${\displaystyle S^{+}(Y)}$${\displaystyle Y\subseteq X}$${\displaystyle X-Y}$
• La subclase , que consta de los conjuntos singleton, no es alcanzable. ^{[2] [ ¿por qué? ]}${\displaystyle S(X)}$

Sea una clase de conceptos. Para cualquier concepto , llamamos a este concepto -bueno para un entero positivo si, para todos , al menos de los conceptos en concuerdan con en la clasificación de . ^[2] La dimensión de huella digital de toda la clase de conceptos es el menor entero positivo tal que cada subclase alcanzable contenga un concepto que sea -bueno para ella. ^[2] Esta cantidad se puede utilizar para limitar el número mínimo de consultas de equivalencia ^{[ aclaración necesaria ]} necesarias para aprender una clase de conceptos de acuerdo con la siguiente desigualdad : . ^[2]${\displaystyle C}$${\displaystyle c\in C}$${\displaystyle 1/d}$${\displaystyle d}$${\displaystyle x\in X}$${\displaystyle 1/d}$${\displaystyle C}$${\displaystyle c}$${\displaystyle x}$ ${\displaystyle FD(C)}$${\displaystyle C}$${\displaystyle d}$${\displaystyle C'\subseteq C}$${\displaystyle 1/d}$${\textstyle FD(C)-1\leq \#EQ(C)\leq \lceil FD(C)\ln(|C|)\rceil }$