Clase de concepto

Teoría del aprendizaje computacional

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é? ]}

Fondo

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'}$

Ejemplos

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)}$

Aplicaciones

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 }$

Referencias

1. Chase, H. y Freitag, J. (2018). Teoría de modelos y aprendizaje automático. Preimpresión de arXiv arXiv:1801.06566.
2. Angluin, D. (2004). "Consultas revisadas" (PDF) . Theoretical Computer Science . 313 (2): 188–191. doi :10.1016/j.tcs.2003.11.004.