Complexidade da amostra - Sample complexity

A complexidade da amostra de um algoritmo de aprendizado de máquina representa o número de amostras de treinamento necessárias para aprender uma função de destino com sucesso.

Mais precisamente, a complexidade da amostra é o número de amostras de treinamento que precisamos fornecer ao algoritmo, de modo que a função retornada pelo algoritmo esteja dentro de um erro arbitrariamente pequeno da melhor função possível, com probabilidade arbitrariamente próxima de 1.

Existem duas variantes de complexidade da amostra:

A variante fraca corrige uma distribuição particular de insumo-produto;
A variante forte assume a complexidade da amostra do pior caso em todas as distribuições de insumo-produto.

O teorema No Free Lunch, discutido abaixo, prova que, em geral, a complexidade da amostra forte é infinita, ou seja, que não há algoritmo que pode aprender a função de destino globalmente ideal usando um número finito de amostras de treinamento.

No entanto, se estamos apenas interessados em uma classe particular de funções de destino (por exemplo, apenas funções lineares), então a complexidade da amostra é finita e depende linearmente da dimensão VC na classe de funções de destino.

Definição

Seja um espaço que chamamos de espaço de entrada e seja um espaço que chamamos de espaço de saída e denotemos o produto . Por exemplo, na configuração da classificação binária, é normalmente um espaço vetorial de dimensão finita e é o conjunto . ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle Z}$ ${\ displaystyle X \ times Y}$ ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle \ {- 1,1 \}}$

Fixe um espaço de hipóteses de funções . Um algoritmo de aprendizagem é um mapa computável de para . Em outras palavras, é um algoritmo que recebe como entrada uma sequência finita de amostras de treinamento e gera uma função de para . Algoritmos de aprendizagem típicos incluem minimização de risco empírico , sem ou com regularização de Tikhonov . ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle h \ dois pontos X \ a Y}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle Z ^ {*}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle X}$ ${\ displaystyle Y}$

Corrija uma função de perda , por exemplo, a perda quadrada , onde . Para uma determinada distribuição em , o risco esperado de uma hipótese (uma função) é ${\ displaystyle {\ mathcal {L}} \ dois pontos Y \ times Y \ to \ mathbb {R} _ {\ geq 0}}$ ${\ displaystyle {\ mathcal {L}} (y, y ') = (y-y') ^ {2}}$ ${\ displaystyle h (x) = y '}$ ${\ displaystyle \ rho}$ ${\ displaystyle X \ times Y}$ ${\ displaystyle h \ in {\ mathcal {H}}}$

{\ displaystyle {\ mathcal {E}} (h): = \ mathbb {E} _ {\ rho} [{\ mathcal {L}} (h (x), y)] = \ int _ {X \ vezes Y} {\ mathcal {L}} (h (x), y) \, d \ rho (x, y)}

Em nosso cenário, temos , onde é um algoritmo de aprendizagem e é uma sequência de vetores que são todos desenhados independentemente de . Defina o risco ideal ${\ displaystyle h = {\ mathcal {A}} (S_ {n})}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle S_ {n} = ((x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n})) \ sim \ rho ^ {n}}$ ${\ displaystyle \ rho}$

{\ displaystyle {\ mathcal {E}} _ {\ mathcal {H}} ^ {*} = {\ underset {h \ in {\ mathcal {H}}} {\ inf}} {\ mathcal {E}} (h).}

Defina , para cada um . Observe que é uma variável aleatória e depende da variável aleatória , que é extraída da distribuição . O algoritmo é chamado de consistente se probabilisticamente convergir para . Ou seja, para todos existe um número inteiro positivo , tal que, para todos , temos

{\ displaystyle h_ {n} = {\ mathcal {A}} (S_ {n})}

{\ displaystyle n}

{\ displaystyle h_ {n}}

{\ displaystyle S_ {n}}

{\ displaystyle \ rho ^ {n}}

{\ displaystyle {\ mathcal {A}}}

{\ displaystyle {\ mathcal {E}} (h_ {n})}

{\ displaystyle {\ mathcal {E}} _ {\ mathcal {H}} ^ {*}}

{\ displaystyle \ epsilon, \ delta> 0}

{\ displaystyle N}

{\ displaystyle n \ geq N}

{\ displaystyle \ Pr _ {\ rho ^ {n}} [{\ mathcal {E}} (h_ {n}) - {\ mathcal {E}} _ {\ mathcal {H}} ^ {*} \ geq \ varejpsilon] <\ delta.}

A complexidade da amostra de é então o mínimo para o qual isso se aplica, como uma função de e . Escrevemos a complexidade da amostra para enfatizar que esse valor de depende de , e . Se não for consistente , então definimos . Se existe um algoritmo para o qual é finito, dizemos que o espaço de hipóteses pode ser aprendido .

{\ displaystyle {\ mathcal {A}}}

{\ displaystyle N}

{\ displaystyle \ rho, \ epsilon}

{\ displaystyle \ delta}

{\ displaystyle N (\ rho, \ epsilon, \ delta)}

{\ displaystyle N}

{\ displaystyle \ rho, \ epsilon}

{\ displaystyle \ delta}

{\ displaystyle {\ mathcal {A}}}

{\ displaystyle N (\ rho, \ epsilon, \ delta) = \ infty}

{\ displaystyle N (\ rho, \ epsilon, \ delta)}

{\ displaystyle {\ mathcal {H}}}

Em outras palavras, a complexidade da amostra define a taxa de consistência do algoritmo: dada uma precisão e confiança desejadas , é necessário amostrar os pontos de dados para garantir que o risco da função de saída esteja dentro do melhor possível, com probabilidade pelo menos . ${\ displaystyle N (\ rho, \ epsilon, \ delta)}$ ${\ displaystyle \ epsilon}$ ${\ displaystyle \ delta}$ ${\ displaystyle N (\ rho, \ epsilon, \ delta)}$ ${\ displaystyle \ epsilon}$ ${\ displaystyle 1- \ delta}$

Na aprendizagem provavelmente aproximadamente correta (PAC) , preocupa-se se a complexidade da amostra é polinomial , ou seja, se é limitada por um polinômio em e . Se for polinomial para algum algoritmo de aprendizagem, então se diz que o espaço de hipótese pode ser

aprendido pelo PAC . Observe que esta é uma noção mais forte do que ser aprendida.

{\ displaystyle N (\ rho, \ epsilon, \ delta)}

{\ displaystyle 1 / \ epsilon}

{\ displaystyle 1 / \ delta}

{\ displaystyle N (\ rho, \ epsilon, \ delta)}

{\ displaystyle {\ mathcal {H}}}

Espaço de hipótese irrestrito: complexidade infinita da amostra

Pode-se perguntar se existe um algoritmo de aprendizagem para que a complexidade da amostra seja finita no sentido forte, ou seja, há um limite no número de amostras necessárias para que o algoritmo possa aprender qualquer distribuição sobre o espaço de entrada-saída com um erro de destino especificado. Mais formalmente, pergunta-se se existe um algoritmo de aprendizagem , tal que, para todos , existe um número inteiro positivo tal que para todos , temos ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle \ epsilon, \ delta> 0}$ ${\ displaystyle N}$ ${\ displaystyle n \ geq N}$

{\ displaystyle \ sup _ {\ rho} \ left (\ Pr _ {\ rho ^ {n}} [{\ mathcal {E}} (h_ {n}) - {\ mathcal {E}} _ {\ mathcal {H}} ^ {*} \ geq \ varepsilon] \ right) <\ delta,}

onde , como acima. O Teorema Sem Almoço Grátis afirma que, sem restrições no espaço de hipóteses , esse não é o caso, ou seja, sempre existem distribuições "ruins" para as quais a complexidade da amostra é arbitrariamente grande.

{\ displaystyle h_ {n} = {\ mathcal {A}} (S_ {n})}

{\ displaystyle S_ {n} = ((x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n})) \ sim \ rho ^ {n}}

{\ displaystyle {\ mathcal {H}}}

Assim, a fim de fazer afirmações sobre a taxa de convergência da quantidade

{\ displaystyle \ sup _ {\ rho} \ left (\ Pr _ {\ rho ^ {n}} [{\ mathcal {E}} (h_ {n}) - {\ mathcal {E}} _ {\ mathcal {H}} ^ {*} \ geq \ varepsilon] \ right),}

um deve também

restringir o espaço de distribuições de probabilidade , por exemplo, por meio de uma abordagem paramétrica, ou ${\ displaystyle \ rho}$
restringir o espaço de hipóteses , como em abordagens livres de distribuição. ${\ displaystyle {\ mathcal {H}}}$

Espaço de hipótese restrito: complexidade de amostra finita

A última abordagem leva a conceitos como dimensão VC e complexidade Rademacher que controlam a complexidade do espaço . Um espaço de hipótese menor introduz mais viés no processo de inferência, o que significa que pode ser maior do que o melhor risco possível em um espaço maior. No entanto, ao restringir a complexidade do espaço de hipóteses, torna-se possível para um algoritmo produzir funções mais uniformemente consistentes. Essa compensação leva ao conceito de

regularização .

{\ displaystyle {\ mathcal {H}}}

{\ displaystyle {\ mathcal {E}} _ {\ mathcal {H}} ^ {*}}

É um teorema da teoria VC que as três afirmações a seguir são equivalentes para um espaço de hipóteses : ${\ displaystyle {\ mathcal {H}}}$

${\ displaystyle {\ mathcal {H}}}$ pode ser aprendido pelo PAC.
A dimensão VC de é finita. ${\ displaystyle {\ mathcal {H}}}$
${\ displaystyle {\ mathcal {H}}}$ é uma classe uniforme

Glivenko-Cantelli .

Isso fornece uma maneira de provar que certos espaços de hipóteses podem ser aprendidos pelo PAC e, por extensão, aprendidos.

Um exemplo de espaço de hipótese aprendível com PAC

${\ displaystyle X = \ mathbb {R} ^ {d}, Y = \ {- 1,1 \}}$ , e deixe ser o espaço de funções afins sobre , isto é, funções da forma para alguns . Esta é a classificação linear com problema de aprendizagem em offset. Agora, observe que quatro pontos coplanares em um quadrado não podem ser quebrados por nenhuma função afim, uma vez que nenhuma função afim pode ser positiva em dois vértices diagonalmente opostos e negativa nos dois restantes. Portanto, a dimensão VC de é , portanto, é finita. Segue-se a caracterização acima das classes que podem ser aprendidas com o PAC e que podem ser aprendidas com o PAC e, por extensão, que podem ser aprendidas. ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle X}$ ${\ displaystyle x \ mapsto \ langle w, x \ rangle + b}$ ${\ displaystyle w \ in \ mathbb {R} ^ {d}, b \ in \ mathbb {R}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle d + 1}$ ${\ displaystyle {\ mathcal {H}}}$

Limites de complexidade de amostra

Suponha que seja uma classe de funções binárias (funções para ). Então, o -PAC pode ser aprendido com uma amostra de tamanho: ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle \ {0,1 \}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle (\ epsilon, \ delta)}$

{\ displaystyle N = O {\ bigg (} {\ frac {VC ({\ mathcal {H}}) + \ ln {1 \ over \ delta}} {\ epsilon}} {\ bigg)}}

onde está a dimensão VC de . Além disso, qualquer algoritmo de aprendizagem -PAC para deve ter complexidade de amostra:

{\ displaystyle VC ({\ mathcal {H}})}

{\ displaystyle {\ mathcal {H}}}

{\ displaystyle (\ epsilon, \ delta)}

{\ displaystyle {\ mathcal {H}}}

{\ displaystyle N = \ Omega {\ bigg (} {\ frac {VC ({\ mathcal {H}}) + \ ln {1 \ over \ delta}} {\ epsilon}} {\ bigg)}}

Assim, a complexidade da amostra é uma função linear da dimensão VC do espaço de hipóteses.

Suponha que seja uma classe de funções com valor real com intervalo em . Então, o -PAC pode ser aprendido com uma amostra de tamanho: ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle [0, T]}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle (\ epsilon, \ delta)}$

{\ displaystyle N = O {\ bigg (} T ^ {2} {\ frac {PD ({\ mathcal {H}}) \ ln {T \ over \ epsilon} + \ ln {1 \ over \ delta}} {\ epsilon ^ {2}}} {\ bigg)}}

onde está a pseudo-dimensão de Pollard .

{\ displaystyle PD ({\ mathcal {H}})}

{\ displaystyle {\ mathcal {H}}}

Outros ajustes

Além do ambiente de aprendizado supervisionado, a complexidade da amostra é relevante para problemas de aprendizado semissupervisionado, incluindo aprendizado ativo , onde o algoritmo pode solicitar rótulos para entradas especificamente escolhidas a fim de reduzir o custo de obtenção de muitos rótulos. O conceito de complexidade da amostra também aparece na aprendizagem por reforço , aprendizagem online e algoritmos não supervisionados, por exemplo, para aprendizagem de dicionário .

Eficiência em robótica

Uma alta complexidade de amostra significa que muitos cálculos são necessários para executar uma pesquisa de árvore de Monte Carlo . É igual a um modelo de busca de força bruta

livre no espaço de estados. Em contraste, um algoritmo de alta eficiência tem uma baixa complexidade de amostra. As técnicas possíveis para reduzir a complexidade da amostra são o aprendizado métrico e o aprendizado por reforço baseado em modelo.

Languages

In other projects