Text document with red question mark.svg
Este artigo ou secção contém fontes no fim do texto, mas que não são citadas no corpo do artigo , o que compromete a confiabilidade das informações (desde fevereiro de 2015).
Por favor, melhore este artigo inserindo fontes no corpo do texto quando necessário.
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde fevereiro de 2015).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.

A teoria da aprendizagem computacional é a analise complexidade computacional do algoritimo de aprendizado de máquina. É a interseção da teoria da computação e aprendizado de máquina.

Visão global

Os resultados teóricos em aprendizado de máquina tendem principalmente lidar com um tipo de aprendizado indutivo chamado aprendizado supervisionado. Em aprendizagem supervisionada, é dado amostras de um algoritmo que são rotulados de alguma forma útil. Por exemplo, as amostras podem ser as descrições de cogumelos, e as etiquetas podem ser ou não os cogumelos que são comestível. O algoritmo toma estas amostras previamente rotuladas e os usam para induzir um classificador. Este classificador é uma função que atribui etiquetas para as amostras incluindo as amostras que nunca foram vistos anteriormente pelo algoritmo. O objetivo do algoritmo de aprendizado supervisionado é otimizar alguma medida de desempenho, tais como minimizar o número de erros cometidos em novas amostras.

Além dos limites de desempenho, a teoria de aprendizagem computacional estuda a complexidade de tempo e viabilidade de aprendizagem. Na teoria da aprendizagem computacional, um cálculo é considerado viável se ele pode ser feito em um tempo polinomial. Existe dois tipos de resultados de complexibilidade de tempo:

  • Resultados positivos – Mostrando que uma determinada classe de funções é aprendida em um tempo polinomial.
  • Resultados negativos – Mostrando que determinadas classes não pode ser aprendido em um tempo polinomial.

Os resultados negativos muitas vezes dependem se geralmente se acredita, mas ainda a hipóteses não comprovadas, tais como:

  • Ccomplexidade computacional - P versus NP
  • Criptografia - Função de mão única.

Há várias abordagens diferentes da teoria de aprendizagem computacional. Estas diferenças são baseadas em fazer suposições sobre a Inferência princípios usados para generalizar a partir de dados limitados. Isto inclui diferentes definições Probabilidade (veja Probabilidade de frequência, Probabilidade epistemológica) e premissas diferentes sobre a geração de amostras.

Deleção de características

    Inductive inference

      Optimal O aprendizado notação

        Resultados negativos

          Tolerância a erro

          Equivalência

          • D.Haussler, M.Kearns, N.Littlestone e Manfred K. Warmuth, Equivalência de modelos para aprendizibilidade polinômial, Proc. 1º ACM Oficina sobre Teoria da Aprendizagem computacional, (1988) 42-55.

          Este artigo usa material do artigo Wikipedia Teoria da aprendizagem computacional, que é lançado sob o Creative Commons Attribution-Share-Alike License 3.0.