Aprendizagem Occam - Occam learning

Na teoria da aprendizagem computacional , a aprendizagem Occam é um modelo de aprendizagem algorítmica em que o objetivo do aluno é produzir uma representação sucinta dos dados de treinamento recebidos. Isso está intimamente relacionado ao aprendizado provavelmente aproximadamente correto (PAC) , em que o aluno é avaliado em seu poder preditivo de um conjunto de testes.

A capacidade de aprendizagem do Occam implica a aprendizagem do PAC e, para uma ampla variedade de classes de conceitos , o inverso também é verdadeiro: a capacidade de aprendizagem do PAC implica a aprendizagem do Occam.

Introdução

Occam Learning tem o nome da navalha de Occam , que é um princípio que afirma que, considerando que todas as outras coisas são iguais, uma explicação mais curta para os dados observados deve ser preferida em vez de uma explicação mais longa. A teoria da aprendizagem Occam é uma justificativa formal e matemática para este princípio. Foi mostrado pela primeira vez por Blumer, et al. que a aprendizagem Occam implica aprendizagem PAC, que é o modelo padrão de aprendizagem na teoria de aprendizagem computacional. Em outras palavras, parcimônia (da hipótese de produção) implica poder preditivo .

Definição de aprendizagem Occam

A sucinta de um conceito na classe de conceito pode ser expressa pelo comprimento da string de bits mais curta que pode representar em . O aprendizado Occam conecta a precisão da saída de um algoritmo de aprendizado ao seu poder preditivo em dados invisíveis. ${\ displaystyle c}$ ${\ displaystyle {\ mathcal {C}}}$ ${\ tamanho do displaystyle (c)}$ ${\ displaystyle c}$ ${\ displaystyle {\ mathcal {C}}}$

Let and be classes de conceito contendo conceitos-alvo e hipóteses, respectivamente. Então, para constantes e , um algoritmo de aprendizagem é um algoritmo -Occam para usar iff, dado um conjunto de amostras rotuladas de acordo com um conceito , produz uma hipótese tal que ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle \ alpha \ geq 0}$ ${\ displaystyle 0 \ leq \ beta <1}$ ${\ displaystyle L}$ ${\ displaystyle (\ alpha, \ beta)}$ ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle S = \ {x_ {1}, \ dots, x_ {m} \}}$ ${\ displaystyle m}$ ${\ displaystyle c \ in {\ mathcal {C}}}$ ${\ displaystyle L}$ ${\ displaystyle h \ in {\ mathcal {H}}}$

${\ displaystyle h}$ é consistente com em (ou seja, ) e ${\ displaystyle c}$ ${\ displaystyle S}$ ${\ displaystyle h (x) = c (x), \ forall x \ in S}$
${\ displaystyle size (h) \ leq (n \ cdot size (c)) ^ {\ alpha} m ^ {\ beta}}$

onde é o comprimento máximo de qualquer amostra . Algoritmo de um Occam é chamado eficiente se ele é executado em polinomial tempo em , e Dizemos uma classe conceito é Occam aprendida no que diz respeito a uma classe hipótese se existe um algoritmo Occam eficiente para usar ${\ displaystyle n}$ ${\ displaystyle x \ in S}$ ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ tamanho do displaystyle (c).}$ ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle {\ mathcal {H}}.}$

A relação entre Occam e aprendizagem PAC

A capacidade de aprendizagem de Occam implica a capacidade de aprendizagem do PAC, conforme o seguinte teorema de Blumer, et al. mostra:

Teorema ( aprendizagem Occam implica aprendizagem PAC )

Deixe ser um algoritmo -Occam eficiente para usar . Então, existe uma constante tal que para qualquer , para qualquer distribuição , dadas amostras retiradas e rotuladas de acordo com um conceito de bits de comprimento cada, o algoritmo produzirá uma hipótese tal que com probabilidade, pelo menos . ${\ displaystyle L}$ ${\ displaystyle (\ alpha, \ beta)}$ ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle {\ mathcal {H}}}$ ${\ displaystyle a> 0}$ ${\ displaystyle 0 <\ epsilon, \ delta <1}$ ${\ displaystyle {\ mathcal {D}}}$ ${\ displaystyle m \ geq a \ left ({\ frac {1} {\ epsilon}} \ log {\ frac {1} {\ delta}} + \ left ({\ frac {(n \ cdot size (c) ) ^ {\ alpha})} {\ epsilon}} \ right) ^ {\ frac {1} {1- \ beta}} \ right)}$ ${\ displaystyle {\ mathcal {D}}}$ ${\ displaystyle c \ in {\ mathcal {C}}}$ ${\ displaystyle n}$ ${\ displaystyle L}$ ${\ displaystyle h \ in {\ mathcal {H}}}$ ${\ erro displaystyle (h) \ leq \ epsilon}$ ${\ displaystyle 1- \ delta}$

Aqui, é no que diz respeito ao conceito e distribuição . Isso implica que o algoritmo também é um aprendiz do PAC para a classe de conceito usando a classe de hipóteses . Uma formulação um pouco mais geral é a seguinte: ${\ erro de displaystyle (h)}$ ${\ displaystyle c}$ ${\ displaystyle {\ mathcal {D}}}$ ${\ displaystyle L}$ ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle {\ mathcal {H}}}$

Teorema ( aprendizagem Occam implica aprendizagem PAC, versão de cardinalidade )

Deixe . Seja um algoritmo tal que, dadas amostras retiradas de uma distribuição fixa mas desconhecida e rotuladas de acordo com um conceito de bits de comprimento cada, produza uma hipótese que é consistente com as amostras rotuladas. Então, existe uma constante tal que se , então é garantido que produza uma hipótese tal que com probabilidade, pelo menos . ${\ displaystyle 0 <\ epsilon, \ delta <1}$ ${\ displaystyle L}$ ${\ displaystyle m}$ ${\ displaystyle {\ mathcal {D}}}$ ${\ displaystyle c \ in {\ mathcal {C}}}$ ${\ displaystyle n}$ ${\ displaystyle h \ in {\ mathcal {H}} _ {n, m}}$ ${\ displaystyle b}$ ${\ displaystyle \ log | {\ mathcal {H}} _ {n, m} | \ leq b \ epsilon m- \ log {\ frac {1} {\ delta}}}$ ${\ displaystyle L}$ ${\ displaystyle h \ in {\ mathcal {H}} _ {n, m}}$ ${\ erro displaystyle (h) \ leq \ epsilon}$ ${\ displaystyle 1- \ delta}$

Embora os teoremas acima mostrem que o aprendizado Occam é suficiente para o aprendizado do PAC, eles não dizem nada sobre a necessidade. Board e Pitt mostram que, para uma ampla variedade de classes conceituais, o aprendizado Occam é de fato necessário para o aprendizado do PAC. Eles provaram que, para qualquer classe de conceito polinomialmente fechada sob listas de exceção, a capacidade de aprendizado do PAC implica a existência de um algoritmo Occam para essa classe de conceito. As classes de conceito que são fechadas polinomialmente sob listas de exceção incluem fórmulas booleanas, circuitos, autômatos finitos determinísticos , listas de decisão, árvores de decisão e outras classes de conceito definidas geometricamente.

Uma classe de conceito é polinomialmente fechada sob listas de exceções se existir um algoritmo de tempo polinomial de modo que, quando dada a representação de um conceito e uma lista finita de exceções , produza uma representação de um conceito de modo que os conceitos e concordem, exceto no conjunto . ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle A}$ ${\ displaystyle c \ in {\ mathcal {C}}}$ ${\ displaystyle E}$ ${\ displaystyle c '\ in {\ mathcal {C}}}$ ${\ displaystyle c}$ ${\ displaystyle c '}$ ${\ displaystyle E}$

Prova de que a aprendizagem Occam implica aprendizagem PAC

Primeiro provamos a versão de cardinalidade. Chame uma hipótese de ruim se , onde novamente está em relação ao conceito verdadeiro e à distribuição subjacente . A probabilidade de que um conjunto de amostras seja consistente é, no máximo , pela independência das amostras. Pelo limite de união, a probabilidade de que exista uma hipótese ruim em é no máximo , que é menor do que se . Isso conclui a prova do segundo teorema acima. ${\ displaystyle h \ in {\ mathcal {H}}}$ ${\ erro displaystyle (h) \ geq \ epsilon}$ ${\ erro de displaystyle (h)}$ ${\ displaystyle c}$ ${\ displaystyle {\ mathcal {D}}}$ ${\ displaystyle S}$ ${\ displaystyle h}$ ${\ displaystyle (1- \ epsilon) ^ {m}}$ ${\ displaystyle {\ mathcal {H}} _ {n, m}}$ ${\ displaystyle | {\ mathcal {H}} _ {n, m} | (1- \ epsilon) ^ {m}}$ ${\ displaystyle \ delta}$ ${\ displaystyle \ log | {\ mathcal {H}} _ {n, m} | \ leq O (\ epsilon m) - \ log {\ frac {1} {\ delta}}}$

Usando o segundo teorema, podemos provar o primeiro teorema. Como temos um algoritmo -Occam, isso significa que qualquer hipótese gerada por pode ser representada por no máximo bits e, portanto . Isso é menor do que se definirmos para alguma constante . Assim, pelo Teorema da versão de Cardinalidade, produzirá uma hipótese consistente com probabilidade, pelo menos . Isso conclui a prova do primeiro teorema acima. ${\ displaystyle (\ alpha, \ beta)}$ ${\ displaystyle L}$ ${\ displaystyle (n \ cdot size (c)) ^ {\ alpha} m ^ {\ beta}}$ ${\ displaystyle \ log | {\ mathcal {H}} _ {n, m} | \ leq (n \ cdot size (c)) ^ {\ alpha} m ^ {\ beta}}$ ${\ displaystyle O (\ epsilon m) - \ log {\ frac {1} {\ delta}}}$ ${\ displaystyle m \ geq a \ left ({\ frac {1} {\ epsilon}} \ log {\ frac {1} {\ delta}} + \ left ({\ frac {(n \ cdot size (c) ) ^ {\ alpha})} {\ epsilon}} \ right) ^ {\ frac {1} {1- \ beta}} \ right)}$ ${\ displaystyle a> 0}$ ${\ displaystyle L}$ ${\ displaystyle h}$ ${\ displaystyle 1- \ delta}$

Melhorar a complexidade da amostra para problemas comuns

Embora a capacidade de aprendizado de Occam e PAC sejam equivalentes, a estrutura de Occam pode ser usada para produzir limites mais estreitos na complexidade da amostra de problemas clássicos, incluindo conjunções, conjunções com poucas variáveis relevantes e listas de decisão.

Extensões

Os algoritmos Occam também demonstraram ser bem-sucedidos no aprendizado do PAC na presença de erros, conceitos probabilísticos, aprendizado de funções e exemplos não independentes de Markovian.

Languages

In other projects