Índice de complejidad

En la informática y la estadística modernas , el índice de complejidad de una función denota el nivel de contenido informativo, lo que a su vez afecta la dificultad de aprender la función a partir de ejemplos . Esto es diferente de la complejidad computacional , que es la dificultad de calcular una función. Los índices de complejidad caracterizan toda la clase de funciones a la que pertenece la que nos interesa. Centrándonos en las funciones booleanas , el detalle de una clase${\displaystyle {\mathsf {C}}}$En el caso de las funciones booleanas, c denota esencialmente cuán profundamente está articulada la clase.

Para identificar este índice primero debemos definir una función centinela de${\displaystyle {\mathsf {C}}}$Centrémonos por un momento en una sola función c , llamémosla un concepto definido en un conjunto${\displaystyle {\mathcal {X}}}$de elementos que podemos representar como puntos en un espacio euclidiano . En este marco, la función anterior asocia a c un conjunto de puntos que, al estar definidos como externos al concepto, impiden que se expanda en otra función de${\displaystyle {\mathsf {C}}}$Podemos definir estos puntos de forma dual en términos de proteger un concepto dado c de ser completamente encerrado (invadido) por otro concepto dentro de la clase. Por lo tanto, llamamos a estos puntos centinelas o puntos centinela ; se asignan mediante la función centinela.${\displaystyle {\boldsymbol {S}}}$a cada concepto de${\displaystyle {\mathsf {C}}}$de tal manera que:

1. los puntos de vigilancia son externos al concepto c que se va a vigilar e internos a al menos otro que lo incluye,
2. cada concepto${\displaystyle c'}$incluyendo c tiene al menos uno de los puntos de centinela de c ya sea en el espacio entre c y${\displaystyle c'}$o fuera${\displaystyle c'}$y distinto de los puntos de centinela de${\displaystyle c'}$, y
3. Constituyen un conjunto mínimo con estas propiedades.

La definición técnica que proviene de ( Apolloni 2006 ) se basa en la inclusión de un concepto aumentado.${\displaystyle c^{+}}$compuesto por c más sus puntos de centinela por otro${\displaystyle \left(c'\right)^{+}}$en la misma clase.

Para una clase conceptual${\displaystyle {\mathsf {C}}}$en un espacio${\displaystyle {\mathfrak {X}}}$, una función centinela es una función total${\displaystyle {\boldsymbol {S}}:{\mathsf {C}}\cup \{\emptyset ,{\mathfrak {X}}\}\mapsto 2^{\mathfrak {X}}}$que cumplan las siguientes condiciones:

1. Los centinelas están fuera del concepto de centinela (${\displaystyle c\cap {\boldsymbol {S}}(c)=\emptyset }$a pesar de${\displaystyle c\in {\mathsf {C}}}$) .
2. Los centinelas están dentro del concepto invasor ( Habiendo introducido los conjuntos${\displaystyle c^{+}=c\cup {\boldsymbol {S}}(c)}$, un concepto invasor${\displaystyle c'\in {\mathsf {C}}}$es tal que${\displaystyle c'\not \subsetequ c}$y${\displaystyle c^{+}\subseteq \left(c'\right)^{+}}$. Que denota${\displaystyle \mathrm {arriba} (c)}$el conjunto de conceptos que invaden c , debemos tener que si${\displaystyle c_{2}\in \mathrm {up} (c_{1})}$, entonces${\displaystyle c_{2}\cap {\boldsymbol {S}}(c_{1})\neq \emptyset }$) .
3. ${\displaystyle {\boldsymbol {S}}(c)}$es un conjunto mínimo con las propiedades anteriores ( No${\displaystyle {\boldsymbol {S}}'\neq {\boldsymbol {S}}}$existe que satisface (1) y (2) y tiene la propiedad de que${\displaystyle {\boldsymbol {S}}'(c)\subseteq {\boldsymbol {S}}(c)}$por cada${\displaystyle c\in {\mathsf {C}}}$) .
4. Los centinelas son guardianes honestos. Puede ser que${\displaystyle c\subseteq \left(c'\right)^{+}}$pero${\displaystyle {\boldsymbol {S}}(c)\cap c'=\emptyset }$de modo que${\displaystyle c'\not \in \mathrm {up} (c)}$. Sin embargo, esto debe ser consecuencia del hecho de que todos los puntos de${\displaystyle {\boldsymbol {S}}(c)}$están involucrados en realmente vigilar c contra otros conceptos en${\displaystyle \mathrm {up} (c)}$y no solo evitando la inclusión de${\displaystyle c^{+}}$por${\displaystyle (c')^{+}}$Por lo tanto, si eliminamos${\displaystyle c',{\boldsymbol {S}}(c)}$permanece sin cambios ( Siempre que${\displaystyle c_{1}}$y${\displaystyle c_{2}}$son tales que${\displaystyle c_{1}\subset c_{2}\cup {\boldsymbol {S}}(c_{2})}$y${\displaystyle c_{2}\cap {\boldsymbol {S}}(c_{1})=\emptyset }$, entonces la restricción de${\displaystyle {\boldsymbol {S}}}$a${\displaystyle \{c_{1}\}\cup \mathrm {up} (c_{1})-\{c_{2}\}}$es una función centinela en este conjunto ) .

${\displaystyle {\boldsymbol {S}}(c)}$es la frontera de c sobre${\displaystyle {\boldsymbol {S}}}$.

Con referencia a la imagen de la derecha,${\displaystyle \{x_{1},x_{2},x_{3}\}}$es una frontera candidata de${\displaystyle c_{0}}$contra${\displaystyle c_{1},c_{2},c_{3},c_{4}}$. Todos los puntos están en el espacio entre un${\displaystyle c_{i}}$y${\displaystyle c_{0}}$. Evitan la inclusión de${\displaystyle c_{0}\cup \{x_{1},x_{2},x_{3}\}}$en${\displaystyle c_{3}}$, siempre que estos puntos no sean utilizados por este último para protegerse contra otros conceptos. Por el contrario, esperamos que${\displaystyle c_{1}}$usos${\displaystyle x_{1}}$y${\displaystyle x_{3}}$como sus propios centinelas,${\displaystyle c_{2}}$usos ${\displaystyle x_{2}}$y${\displaystyle x_{3}}$y${\displaystyle c_{4}}$usos ${\displaystyle x_{1}}$y${\displaystyle x_{2}}$Análogamente. Punto${\displaystyle x_{4}}$no está permitido como${\displaystyle c_{0}}$puesto centinela ya que, como cualquier asiento diplomático, debe estar ubicado fuera de todos los demás conceptos solo para asegurar que no esté ocupado en caso de invasión por${\displaystyle c_{0}}$.

• Apolloni, B.; Malchiodi, D.; Gaito, S. (2006). Inferencia algorítmica en aprendizaje automático . Serie internacional sobre inteligencia avanzada. Vol.  5 (2.ª  ed.). Adelaida: Magill. Advanced Knowledge International
• Apolloni, B.; Chiaravalli, S. (1997). "Aprendizaje PAC de clases de conceptos a través de los límites de sus elementos" . Theoretical Computer Science . 172 ( 1–2 ): 91–120 . doi : 10.1016/S0304-3975(95)00240-5 .