계산학습이론 : Computational Learning Theory

Computational Learning Theory

수학적인 관점에서 학습과정 (learning process)를 설명하려는 시도.

Wikipedia : Computational learning theory (COLT) : 통계학에서 COLT 는 기계학습 (Machine Learning) 알고리즘의 분석과 관련된 수학 분야이다. 기계학습은 훈련집합을 취해서, 가설 또는 모델을 만들고, 미래에 대한 예측을 한다. 훈련집합은 유한하고 미래는 불확실하기 때문에, 학습이론은 보통 알고리즘의 성능을 완전하게 보장하는 결과를 내지는 못한다. 대신에, 기계학습 알고리즘의 성능에 대한 확률적 한계를 주는 방법이 흔히 사용된다.

성능의 한계에 더해서, 계산학습 이론가들은 학습의 시간복잡도 (time complexity) 와 실현가능성 (feasibility) 를 연구한다. COLT 에서는, 만일 계산이 ploynomial time 내에 이루어 질 수 있다면 실현가능 (feasible) 하다고 한다. 시간복잡도 계산 결과 두가지 종류가 있다.

positive results : 어떤 부류 (class) 가 polynomial time 내에 학습 가능하다 (learnable, classifiable) 는 것을 보여준다.
negative results : 어떤 부류 (class) 가 polynomial time 내에 학습 불가능하다 는 것을 보여준다.

Negative results 는 가정에 의해서만 증명된다. negative results에서 흔한 가정은 다음과 같다 :

계산 복잡도 (computational complexity) - P ≠ NP
암호 (cryptographic) - One-way functions 존재

COLT 의 몇가지 다른 분야가 있는데, 그것들은 수학적으로는 모순인 것들이 있다. 이러한 모순은 다른 추론 원칙들을 (즉 제한된 데이터를 사용해서 어떻게 일반화 할 것인가 하는 원칙들) 사용하기 때문에 생기는 것이다. COLT 의 다른 분야는 다음과 같다.

Probably approximately correct learning (PAC learning), proposed by Leslie Valiant;
VC theory, proposed by Vladimir Vapnik;
Bayesian inference, arising from work first done by Thomas Bayes.
Algorithmic learning theory, from the work of E. M. Gold.

COLT 는 새로운 실용적인 알고리즘을 유도했다. 예를들면 PAC 이론은 boosting을 낳게했고, VC 이론은 support vector machines을 낳게했으며, Bayesian inference 은 belief networks (by Judea Pearl)을 낳게했다.

External links

Computational learning theory web site (http://www.learningtheory.org)
On-line book: Information Theory, Inference, and Learning Algorithms (http://www.inference.phy.cam.ac.uk/mackay/itila/), by David MacKay, gives a detailed account of the Bayesian approach to machine learning.
Review of An Introduction to Computational Learning Theory (http://www.santafe.edu/~shalizi/reviews/kearns-vazirani/)
Review of The Nature of Statistical Learning Theory (http://www.santafe.edu/~shalizi/reviews/vapnik-nature/)
Basics of Bayesian inference (http://research.microsoft.com/adapt/MSBNx/msbnx/Basics_of_Bayesian_Inference.htm)