Índice de complexidade

Além da complexidade como uma dificuldade para calcular uma função (consulte complexidade computacional), na ciência da computação moderna e em estatística outro índice de complexidade de uma função serve para denotar o seu conteúdo de informação, por sua vez afetando a dificuldade de aprender funções a partir de exemplos. índices de complexidade, neste sentido, caracterizam toda a classe de funções à qual as funções nas quais estamos interessados pertencem. Focando em funções Booleanas, o detalhe de uma classe ${\mathsf {C}}$ de funções Booleanas c , essencialmente, denota o quão profundamente a classe é articulada.

Para identificar este índice devemos primeiro definir um função sentinela de ${\mathsf {C}}$. Vamos nos concentrar por um momento em uma única função, c, chame-o de um conceito definido sobre um conjunto ${\mathcal {X}}$ de elementos que podemos imaginar como pontos em um espaço Euclideano. Neste quadro, a função acima associa a c um conjunto de pontos que, uma vez que são definidos para serem externos ao conceito, previnem que ele se expanda para outra função de ${\mathsf {C}}$. Podemos duplamente definir estes pontos em termos de proteger um determinado conceito c de ser totalmente fechado (invadido) por outro conceito dentro da classe. Portanto, chamamos a estes pontos sentinelas ou pontos sentinela; eles são atribuídos pela função de sentinela ${\boldsymbol {S}}$ para cada conceito de ${\mathsf {C}}$ de tal forma que:

1. o ponto sentinela  é externo ao conceito c para ser vigiado e interno para pelo menos um outro, incluindo,
2. cada conceito $c'$ incluindo c tem pelo menos um ponto sentinela de c, que é ou a distância entre c e $c'$ ou fora de $c'$ e distinto dos pontos sentinelas de $c'$ e
3. eles constituem um conjunto mínimo com essas propriedades.

A definição técnica proveniente de (Apolloni 2006) está enraizada na inclusão de um conceito aumentado $c^{+}$ composto de c e seus pontos sentinela por outro $\left(c'\right)^{+}$ na mesma classe.

Definição de função de sentinela

Para um conceito de classe ${\mathsf {C}}$ em um espaço ${\mathfrak {X}}$ uma função sentinela é uma função total ${\boldsymbol {S}}:{\mathsf {C}}\cup \{\emptyset ,{\mathfrak {X}}\}\mapsto 2^{\mathfrak {X}}$ satisfazendo as seguintes condições:

1. Sentinelas estão fora  do conceito sentinela ($c\cap {\boldsymbol {S}}(c)=\emptyset$ para todo $c\in {\mathsf {C}}$).
2. Sentinelas estão dentro do conceito invasor (Tendo introduzido os conjuntos $c^{+}=c\cup {\boldsymbol {S}}(c)$, um conceito invasor $c'\in {\mathsf {C}}$ é tal que $c'\not \subseteq c$ e $c^{+}\subseteq \left(c'\right)^{+}$. Denotando $\mathrm {up} (c)$ como o conjunto de conceitos invadindo c, temos que ter, se $c_{2}\in \mathrm {up} (c_{1})$, então $c_{2}\cap {\boldsymbol {S}}(c_{1})\neq \emptyset$).
3. ${\boldsymbol {S}}(c)$ é o conjunto mínimo com as propriedades acima (No ${\boldsymbol {S}}'\neq {\boldsymbol {S}}$ existe satisfazendo (1) e (2) e tendo a seguinte propriedade ${\boldsymbol {S}}'(c)\subseteq {\boldsymbol {S}}(c)$ $c\in {\mathsf {C}}$).
4. Sentinelas são guardiões honestos. Pode parecer que $c\subseteq \left(c'\right)^{+}$ mas ${\boldsymbol {S}}(c)\cap c'=\emptyset$ para que $c'\not \in \mathrm {up} (c)$. isto, porém deve ser uma consequência do fato de que todos os pontos de ${\boldsymbol {S}}(c)$ estão envolvidos em realmente proteger c contra outros conceitos em $\mathrm {up} (c)$ e não somente em evitar inclusões de $c^{+}$ por $(c')^{+}$. Assim, se removermos $c',{\boldsymbol {S}}(c)$ permanece a mesma (Sempre que $c_{1}$ e $c_{2}$ são tais que $c_{1}\subset c_{2}\cup {\boldsymbol {S}}(c_{2})$ e $c_{2}\cap {\boldsymbol {S}}(c_{1})=\emptyset$, então a restrição de ${\boldsymbol {S}}$ para $\{c_{1}\}\cup \mathrm {up} (c_{1})-\{c_{2}\}$ é uma função sentinela nesse conjunto).

${\displaystyle }$${\boldsymbol {S}}(c)$ é a fronteira de c sobre ${\boldsymbol {S}}$.${\displaystyle }$

Um diagrama esquemático da perspectiva da funcionalidade sentinela exterior.

Fazendo referência a imagem na direita, $\{x_{1},x_{2},x_{3}\}$ é uma fronteira candidata de $c_{0}$ contra $c_{1},c_{2},c_{3},c_{4}$. todos os pontos estão na lacuna entre um $c_{i}$ e $c_{0}$. Eles evitam a inclusão de $c_{0}\cup \{x_{1},x_{2},x_{3}\}$ em $c_{3}$, desde que esses pontos não são usados pelo último para se proteger contra outros conceitos. Vice versa esperamos que $c_{1}$ use $x_{1}$ e $x_{3}$ como suas próprias sentinelas, $c_{2}$ use $x_{2}$ e $x_{3}$ e $c_{4}$ use $x_{1}$ e $x_{2}$ analogamente. O ponto $x_{4}$ não é permitido como um ponto sentinela de $c_{0}$ pois, como qualquer assento diplomático, deveria ser alocado fora de todos os outros conceitos apenas para confiar que não está ocupado em caso de ser invadido por $c_{0}$.

Definição de detalhes

O tamanho da fronteira do conceito mais caro a ser protegido com a função sentinela menos eficiente, i.e. a quantidade

$\mathrm {D} _{\mathsf {C}}=\sup _{{\boldsymbol {S}},c}\#{\boldsymbol {S}}(c)$,

é chamada de detalhe de ${\mathsf {C}}$. ${\boldsymbol {S}}$ abrange também as funções sentinelas em subconjuntos de ${\mathfrak {X}}$ vigiando neste caso, as interseções dos conceitos com esses subconjuntos. Na verdade, subconjuntos próprios de ${\mathfrak {X}}$ podem hospedar tarefas sentinelas que provam ser mais difíceis do que as emergindo com ${\mathfrak {X}}$.

O detalhe $\mathrm {D} _{\mathsf {C}}$ é uma medida de complexidade do conceito de classes dupla para a dimensão VC $\mathrm {D} _{{\mathsf {V}}C}$. O antigo usa pontos para separar os conjuntos de conceitos, estes últimos conceitos de particionamento de conjuntos de pontos. Em particular, a seguinte desigualdade vale (Apolloni 1997)

$\mathrm {D} _{\mathsf {C}}\leq \mathrm {D} _{{\mathsf {V}}C}+1$

Veja também complexidade de Rademacher para tomar conhecimento de uma recém-introduzida classe de índice de complexidade.

Exemplo: espaços contínuos

A classe C de círculos em $\mathbb {R} ^{2}$ tem detalhe $\mathrm {D} _{\mathsf {C}}=2$, como mostrado na imagem à esquerda. Similarmente, para a classe de segmentos em $\mathbb {R}$, como mostrado na imagem à direita.

Dois pontos $x_{1},x_{2}$ fora de c (círculo grosso) são suficientes para prevenir um círculo maior que não os contém de incluir-los

A classe de segmentos em $\mathbb {R}$ e dois pontos necessários para vigiar seus conceitos

Exemplo: espaços discretos

A classe ${\mathsf {C}}=\{c_{1},c_{2},c_{3},c_{4}\}$ sobre ${\mathfrak {X}}=\{x_{1},x_{2},x_{3}\}$ cujos conceitos são ilustrados no esquema seguinte, onde "$+$" denota um elemento $x_{j}$ pertencente a $c_{i}$, "$-$" um elemento fora de $c_{i}$ e $\bigcirc$ um ponto sentinela:

$x_{1}$	$x_{2}$	$x_{3}$
$c_{1}=$	$\bigcirc \!\!\!\!\!-$	$\bigcirc \!\!\!\!\!-$	$-$
$c_{2}=$	$\bigcirc \!\!\!\!\!-$	$+$	$+$
$c_{3}=$	$+$	$\bigcirc \!\!\!\!\!-$	$+$
$c_{4}=$	$+$	$+$	$+$

Esta classe tem $\mathrm {D} _{\mathsf {C}}=2$. Como de costume, podemos ter diferentes funções sentinelas. O pior caso $\mathbf {S}$, como ilustrado, é: $\mathbf {S} (c_{1})=\{x_{1},x_{2}\},\mathbf {S} (c_{2})=\{x_{1}\},\mathbf {S} (c_{3})=\{x_{2}\},\mathbf {S} (c_{4})=\emptyset$. No entanto, um mais barato é $\mathbf {S} (c_{1})=\{x_{3}\},\mathbf {S} (c_{2})=\{x_{1}\},\mathbf {S} (c_{3})=\{x_{2}\},\mathbf {S} (c_{4})=\emptyset$:

$x_{1}$	$x_{2}$	$x_{3}$
$c_{1}=$	$-$	$-$	$\bigcirc \!\!\!\!\!-$
$c_{2}=$	$\bigcirc \!\!\!\!\!-$	$+$	$+$
$c_{3}=$	$+$	$\bigcirc \!\!\!\!\!-$	$+$
$c_{4}=$	$+$	$+$	$+$

Referências

• Apolloni, B; Malchiodi, D.; Gaito, S. (2006). Algorithmic Inference in Machine Learning. International Series on Advanced Intelligence 5 (2nd ed.). Adelaide: Magill. Advanced Knowledge International 
• Apolloni, B.; Chiaravalli, S. (1997). "PAC learning of concept classes through the boundaries of their items". Theoretical Computer Science 172 (1–2): 91–120. doi:10.1016/S0304-3975(95)00240-5.