Teoria de aprendizagem computacional - Computational learning theory

Parte de uma série sobre
Aprendizado de máquina e mineração de dados
Problemas Classificação Clustering Regressão Detecção de anomalia AutoML Regras de associação Aprendizagem por reforço Previsão estruturada Engenharia de recursos Aprendizagem de recursos Aprendizagem online Aprendizagem semissupervisionada Aprendizagem não supervisionada Aprendendo a classificar Indução gramatical
Aprendizagem supervisionada ( classificação  • regressão ) Árvores de decisão Conjuntos Ensacamento Boosting Floresta aleatória k -NN Regressão linear Baías ingénuas Redes neurais artificiais Regressão logística Perceptron Máquina de vetor de relevância (RVM) Máquina de vetores de suporte (SVM)
Clustering BÉTULA CURA Hierárquico k- significa Expectativa-maximização (EM) DBSCAN ÓPTICA Mudança média
Redução de dimensionalidade Análise Fatorial CCA ICA LDA NMF PCA PGD t-SNE
Previsão estruturada Modelos gráficos Rede Bayes Campo aleatório condicional Markov Oculto
Detecção de anomalia k -NN Fator de outlier local
Rede neural artificial Autoencoder Computação cognitiva Aprendizagem profunda DeepDream Perceptron multicamadas RNN LSTM GRU ESN Máquina de Boltzmann restrita GAN SOM Rede neural convolucional U-Net Transformador Spiking rede neural Memtransistor RAM eletroquímica (ECRAM)
Aprendizagem por reforço Q-learning SARSA Diferença temporal (TD)
Teoria Compensação de polarização-variância Teoria de aprendizagem computacional Minimização de risco empírico Aprendizagem Occam Aprendizagem PAC Aprendizagem estatística Teoria VC
Locais de aprendizado de máquina NeurIPS ICML ML JMLR ArXiv: cs.LG
Artigos relacionados Glossário de inteligência artificial Lista de conjuntos de dados para pesquisa de aprendizado de máquina Esboço do aprendizado de máquina
v t e

Na ciência da computação , a teoria do aprendizado computacional (ou apenas teoria do aprendizado ) é um subcampo da inteligência artificial dedicado ao estudo do projeto e análise de algoritmos de aprendizado de máquina .

Visão geral

Os resultados teóricos em aprendizado de máquina lidam principalmente com um tipo de aprendizado indutivo denominado aprendizado supervisionado . No aprendizado supervisionado, um algoritmo recebe amostras que são rotuladas de alguma forma útil. Por exemplo, as amostras podem ser descrições de cogumelos e os rótulos podem indicar se os cogumelos são ou não comestíveis. O algoritmo pega essas amostras previamente rotuladas e as usa para induzir um classificador. Este classificador é uma função que atribui rótulos a amostras, incluindo amostras que não foram vistas anteriormente pelo algoritmo. O objetivo do algoritmo de aprendizado supervisionado é otimizar algumas medidas de desempenho, como minimizar o número de erros cometidos em novas amostras.

Além dos limites de desempenho, a teoria do aprendizado computacional estuda a complexidade do tempo e a viabilidade do aprendizado. Na teoria de aprendizagem computacional, um cálculo é considerado viável se puder ser feito em tempo polinomial . Existem dois tipos de resultados de complexidade de tempo:

• Resultados positivos - mostrando que uma determinada classe de funções pode ser aprendida em tempo polinomial.
• Resultados negativos - Mostrando que certas classes não podem ser aprendidas em tempo polinomial.

Os resultados negativos muitas vezes dependem de suposições geralmente aceitas, mas ainda não comprovadas, como:

• Complexidade computacional - P ≠ NP (o problema P versus NP) ;
• Criptográfico - Existem funções unilaterais.

Existem várias abordagens diferentes para a teoria de aprendizagem computacional com base em diferentes suposições sobre os princípios de inferência usados ​​para generalizar a partir de dados limitados. Isso inclui diferentes definições de probabilidade (ver probabilidade de frequência , probabilidade bayesiana ) e diferentes suposições sobre a geração de amostras. As diferentes abordagens incluem:

• Aprendizagem exata, proposta por Dana Angluin ;
• Aprendizagem provavelmente correta ( aprendizagem PAC), proposta por Leslie Valiant ;
• Teoria VC , proposta por Vladimir Vapnik e Alexey Chervonenkis ;
• Inferência bayesiana ;
• Teoria da aprendizagem algorítmica , do trabalho de E. Mark Gold ;
• Aprendizado de máquina online , do trabalho de Nick Littlestone.

Embora seu objetivo principal seja compreender a aprendizagem de forma abstrata, a teoria da aprendizagem computacional levou ao desenvolvimento de algoritmos práticos. Por exemplo, a teoria do PAC inspirou impulso , a teoria VC levou a máquinas de vetores de suporte e a inferência bayesiana levou a redes de crenças .

Veja também

• Indução gramatical
• Teoria da informação
• Estabilidade (teoria de aprendizagem)
• Tolerância a erros (aprendizagem PAC)

Referências

pesquisas

• Angluin, D. 1992. Teoria da aprendizagem computacional: Pesquisa e bibliografia selecionada. Em Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (maio de 1992), páginas 351-369. http://portal.acm.org/citation.cfm?id=129712.129746
• D. Haussler. Aprendizagem provavelmente correta. Em AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA, páginas 1101-1108. American Association for Artificial Intelligence, 1990. http://citeseer.ist.psu.edu/haussler90probably.html

Dimensão VC

• V. Vapnik e A. Chervonenkis. Sobre a convergência uniforme de frequências relativas de eventos às suas probabilidades . Theory of Probability and Its Applications, 16 (2): 264–280, 1971.

Seleção de recursos

• A. Dhagat e L. Hellerstein, "PAC learning with irrelevant attribute", em 'Proceedings of the IEEE Symp. on Foundation of Computer Science ', 1994. http://citeseer.ist.psu.edu/dhagat94pac.html

Inferência indutiva

• Gold, E. Mark (1967). “Identificação do idioma no limite” (PDF) . Informação e controle . 10 (5): 447–474. doi : 10.1016 / S0019-9958 (67) 91165-5 .

Aprendizagem de notação O ideal

• Oded Goldreich , Dana Ron . Sobre algoritmos de aprendizagem universais . http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2224

Resultados negativos

• M. Kearns e Leslie Valiant . 1989. Limitações criptográficas na aprendizagem de fórmulas booleanas e autômatos finitos. Em Proceedings of the 21st Annual ACM Symposium on Theory of Computing, páginas 433-444, New York. ACM. http://citeseer.ist.psu.edu/kearns89cryptographic.html

Boosting (aprendizado de máquina)

• Robert E. Schapire. A força do aprendizado fraco. Machine Learning, 5 (2): 197–227, 1990 http://citeseer.ist.psu.edu/schapire90strength.html

Occam Learning

• Blumer, A .; Ehrenfeucht, A .; Haussler, D .; Warmuth, navalha de MK Occam Inf.Proc.Lett. 24, 377-380, 1987.
• Blumer, A .; Ehrenfeucht, A .; Haussler, D .; Warmuth, MK Learnability e a dimensão Vapnik-Chervonenkis . Journal of the ACM, 36 (4): 929–865, 1989.

Aprendizagem provavelmente correta

• L. Valiant. A Theory of the Learnable . Communications of the ACM, 27 (11): 1134-1142, 1984.

Tolerância de erro

• Michael Kearns e Ming Li. Aprender na presença de erros maliciosos. SIAM Journal on Computing, 22 (4): 807–837, agosto de 1993. http://citeseer.ist.psu.edu/kearns93learning.html
• Kearns, M. (1993). Aprendizagem eficiente com tolerância a ruído a partir de consultas estatísticas. Em Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, páginas 392-401. http://citeseer.ist.psu.edu/kearns93efficient.html

Equivalência

• D.Haussler, M.Kearns, N.Littlestone e M. Warmuth , Equivalence of models for polynomial learnability, Proc. 1º Workshop ACM em Teoria de Aprendizagem Computacional, (1988) 42-55.
• Pitt, L .; Warmuth, MK (1990). "Redutibilidade de Preservação de Predição" . Journal of Computer and System Sciences . 41 (3): 430–467. doi : 10.1016 / 0022-0000 (90) 90028-J .

Uma descrição de algumas dessas publicações é fornecida em publicações importantes em aprendizado de máquina .

Teoria da Aprendizagem da Distribuição

links externos

• Noções básicas de inferência bayesiana