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 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 .
Vamos nos concentrar por um momento em uma única função, c, chame-o de um conceito definido sobre um conjunto 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 . 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 para cada conceito de de tal forma que:
o ponto sentinela é externo ao conceito c para ser vigiado e interno para pelo menos um outro, incluindo,
cada conceito incluindo c tem pelo menos um ponto sentinela de c, que é ou a distância entre c e ou fora de e distinto dos pontos sentinelas de e
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 composto de c e seus pontos sentinela por outro na mesma classe.
Para um conceito de classe em um espaço uma função sentinela é uma função total satisfazendo as seguintes condições:
Sentinelas estão fora do conceito sentinela ( para todo ).
Sentinelas estão dentro do conceito invasor (Tendo introduzido os conjuntos , um conceito invasor é tal que e . Denotando como o conjunto de conceitos invadindo c, temos que ter, se , então ).
é o conjunto mínimo com as propriedades acima (No existe satisfazendo (1) e (2) e tendo a seguinte propriedade ).
Sentinelas são guardiões honestos. Pode parecer que mas para que . isto, porém deve ser uma consequência do fato de que todos os pontos de estão envolvidos em realmente proteger c contra outros conceitos em e não somente em evitar inclusões de por . Assim, se removermos permanece a mesma (Sempre que e são tais que e , então a restrição de para é uma função sentinela nesse conjunto).
é a fronteira de c sobre .
Fazendo referência a imagem na direita, é uma fronteira candidata de contra . todos os pontos estão na lacuna entre um e . Eles evitam a inclusão de em , desde que esses pontos não são usados pelo último para se proteger contra outros conceitos. Vice versa esperamos que use e como suas próprias sentinelas, use e e use e analogamente. O ponto não é permitido como um ponto sentinela de 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 .
O tamanho da fronteira do conceito mais caro a ser protegido com a função sentinela menos eficiente, i.e. a quantidade
,
é chamada de detalhe de . abrange também as funções sentinelas em subconjuntos de vigiando neste caso, as interseções dos conceitos com esses subconjuntos. Na verdade, subconjuntos próprios de podem hospedar tarefas sentinelas que provam ser mais difíceis do que as emergindo com .
O detalhe é uma medida de complexidade do conceito de classes dupla para a dimensão VC. 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)
Veja também complexidade de Rademacher para tomar conhecimento de uma recém-introduzida classe de índice de complexidade.
A classe C de círculos em tem detalhe , como mostrado na imagem à esquerda. Similarmente, para a classe de segmentos em , como mostrado na imagem à direita.
A classe sobre cujos conceitos são ilustrados no esquema seguinte, onde "" denota um elemento pertencente a , "" um elemento fora de e um ponto sentinela:
Esta classe tem . Como de costume, podemos ter diferentes funções sentinelas. O pior caso , como ilustrado, é: . No entanto, um mais barato é :
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 Science172 (1–2): 91–120. doi:10.1016/S0304-3975(95)00240-5.