Movatterモバイル変換

[0]ホーム

Jump to content

Computational learning theory

Edit links

From Wikipedia, the free encyclopedia

See also:Statistical learning theory

Theory of machine learning

This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Computational learning theory" – news ·newspapers ·books ·scholar ·JSTOR(November 2018) (Learn how and when to remove this message)

Machine learning anddata mining
Part of a series on
Paradigms Supervised learning Unsupervised learning Semi-supervised learning Self-supervised learning Reinforcement learning Meta-learning Online learning Batch learning Curriculum learning Rule-based learning Neuro-symbolic AI Neuromorphic engineering Quantum machine learning
Problems Classification Generative modeling Regression Clustering Dimensionality reduction Density estimation Anomaly detection Data cleaning AutoML Association rules Semantic analysis Structured prediction Feature engineering Feature learning Learning to rank Grammar induction Ontology learning Multimodal learning
Supervised learning (classification • regression) Apprenticeship learning Decision trees Ensembles Bagging Boosting Random forest k-NN Linear regression Naive Bayes Artificial neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH CURE Hierarchical k-means Fuzzy Expectation–maximization (EM) DBSCAN OPTICS Mean shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA PGD t-SNE SDL
Structured prediction Graphical models Bayes net Conditional random field Hidden Markov
Anomaly detection RANSAC k-NN Local outlier factor Isolation forest
Neural networks Autoencoder Deep learning Feedforward neural network Recurrent neural network LSTM GRU ESN reservoir computing Boltzmann machine Restricted GAN Diffusion model SOM Convolutional neural network U-Net LeNet AlexNet DeepDream Neural field Neural radiance field Physics-informed neural networks Transformer Vision Mamba Spiking neural network Memtransistor Electrochemical RAM (ECRAM)
Reinforcement learning Q-learning Policy gradient SARSA Temporal difference (TD) Multi-agent Self-play
Learning with humans Active learning Crowdsourcing Human-in-the-loop Mechanistic interpretability RLHF
Model diagnostics Coefficient of determination Confusion matrix Learning curve ROC curve
Mathematical foundations Kernel machines Bias–variance tradeoff Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory Topological deep learning
Journals and conferences AAAI ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Related articles Glossary of artificial intelligence List of datasets for machine-learning research List of datasets in computer vision and image processing Outline of machine learning
v t e

Incomputer science,computational learning theory (or justlearning theory) is a subfield ofartificial intelligence devoted to studying the design and analysis ofmachine learning algorithms.^[1]

Overview

[edit]

Theoretical results in machine learning often focus on a type of inductive learning known assupervised learning. In supervised learning, an algorithm is provided withlabeled samples. For instance, the samples might be descriptions of mushrooms, with labels indicating whether they are edible or not. The algorithm uses these labeled samples to create a classifier. This classifier assigns labels to new samples, including those it has not previously encountered. The goal of the supervised learning algorithm is to optimize performance metrics, such as minimizing errors on new samples.

In addition to performance bounds, computational learning theory studies the time complexity and feasibility of learning.^{[citation needed]} Incomputational learning theory, a computation is considered feasible if it can be done inpolynomial time.^{[citation needed]} There are two kinds of timecomplexity results:

Positive results – Showing that a certain class of functions is learnable in polynomial time.
Negative results – Showing that certain classes cannot be learned in polynomial time.^[2]

Negative results often rely on commonly believed, but yet unproven assumptions,^{[citation needed]} such as:

Computational complexity –P ≠ NP (the P versus NP problem);
Cryptographic –One-way functions exist.

There are several different approaches to computational learning theory based on making different assumptions about theinference principles used to generalise from limited data. This includes different definitions ofprobability (seefrequency probability,Bayesian probability) and different assumptions on the generation of samples.^{[citation needed]} The different approaches include:

Exact learning, proposed byDana Angluin;^[3]^[4]
Probably approximately correct learning (PAC learning), proposed byLeslie Valiant;^[5]
VC theory, proposed byVladimir Vapnik andAlexey Chervonenkis;^[6]
Inductive inference as developed byRay Solomonoff;^[7]^[8]
Algorithmic learning theory, from the work ofE. Mark Gold;^[9]
Online machine learning, from the work of Nick Littlestone^{[citation needed]}.

While its primary goal is to understand learning abstractly, computational learning theory has led to the development of practical algorithms. For example, PAC theory inspiredboosting, VC theory led tosupport vector machines, and Bayesian inference led tobelief networks.

References

[edit]

^"ACL - Association for Computational Learning".
^Kearns, Michael; Vazirani, Umesh (August 15, 1994).An Introduction to Computational Learning Theory. MIT Press.ISBN 978-0262111935.
^Dana Angluin (1976).An Application of the Theory of Computational Complexity to the Study of Inductive Inference (Ph.D. thesis). University of California at Berkeley.
^D. Angluin (1978)."On the Complexity of Minimum Inference of Regular Sets".Information and Control.39 (3):337–350.
^Valiant, Leslie (1984)."A Theory of the Learnable"(PDF).Communications of the ACM.27 (11):1134–1142.doi:10.1145/1968.1972.S2CID 12837541. Archived fromthe original(PDF) on 2019-05-17. Retrieved2022-11-24.
^Vapnik, V.; Chervonenkis, A. (1971)."On the uniform convergence of relative frequencies of events to their probabilities"(PDF).Theory of Probability and Its Applications.16 (2):264–280.doi:10.1137/1116025.
^Solomonoff, Ray (March 1964)."A Formal Theory of Inductive Inference Part 1".Information and Control.7 (1):1–22.doi:10.1016/S0019-9958(64)90223-2.
^Solomonoff, Ray (1964). "A Formal Theory of Inductive Inference Part 2".Information and Control.7 (2):224–254.doi:10.1016/S0019-9958(64)90131-7.
^Gold, E. Mark (1967)."Language identification in the limit"(PDF).Information and Control.10 (5):447–474.doi:10.1016/S0019-9958(67)91165-5.

External links

[edit]

Basics of Bayesian inference

v t e Differentiable computing
General	Differentiable programming Information geometry Statistical manifold Automatic differentiation Neuromorphic computing Pattern recognition Ricci calculus Computational learning theory Inductive bias
Hardware	IPU TPU VPU Memristor SpiNNaker
Software libraries	TensorFlow PyTorch Keras scikit-learn Theano JAX Flux.jl MindSpore
Portals Computer programming Technology