계산학습이론
| 기계 학습과 데이터 마이닝 |
|---|
 |
컴퓨터 과학에서 계산 학습 이론(또는 단순히 학습 이론)은 기계 학습 알고리즘의 설계와 분석을 다루는 인공지능의 하위 분야이다.[1]
개요
[편집]기계 학습의 이론적 결과는 주로 지도 학습이라고 알려진 귀납적 학습 유형에 초점을 맞춘다. 지도 학습에서 알고리즘은 레이블이 지정된 샘플을 제공받는다. 예를 들어, 샘플이 버섯에 대한 설명이고 레이블이 식용 여부를 나타낸다고 가정하자. 알고리즘은 이 레이블이 지정된 샘플을 사용하여 분류기를 생성한다. 이 분류기는 이전에 접해보지 못한 샘플을 포함하여 새로운 샘플에 레이블을 할당한다. 지도 학습 알고리즘의 목표는 새로운 샘플에 대한 오류 최소화와 같은 성능 지표를 최적화하는 것이다.
성능 범위 외에도 계산 학습 이론은 학습의 시간 복잡도와 실현 가능성을 연구한다.[2] 계산 학습 이론에서 연산은 다항 시간 내에 수행될 수 있으면 실현 가능한 것으로 간주된다.[2] 시간 복잡도 결과에는 두 가지 종류가 있다.
- 긍정적 결과 — 특정 함수 클래스가 다항 시간 내에 학습 가능함을 보여줌.
- 부정적 결과 — 특정 클래스는 다항 시간 내에 학습될 수 없음을 보여줌.[3]
부정적 결과는 종종 다음과 같이 널리 받아들여지지만 아직 증명되지 않은 가정에 의존한다.
- 계산 복잡도 – P ≠ NP (P-NP 문제);
- 암호학 – 일방향함수가 존재함.
제한된 데이터로부터 일반화하기 위해 사용되는 추론 원칙에 대해 서로 다른 가정을 하는 계산 학습 이론에 대한 몇 가지 다른 접근 방식이 있다. 여기에는 확률의 서로 다른 정의(참고: 빈도 확률, 베이즈 확률론)와 샘플 생성에 대한 서로 다른 가정이 포함된다. 다양한 접근 방식은 다음과 같다.
- 다나 앵글린이 제안한 정확한 학습(Exact learning);[4][5]
- 레슬리 밸리언트가 제안한 PAC 학습(Probably approximately correct learning);[6]
- 블라디미르 바프닉과 알렉세이 체르보넨키스가 제안한 VC 이론;[7]
- 레이 솔로모노프가 발전시킨 귀납적 추론;[8][9]
- E. 마크 골드의 연구에서 비롯된 알고리즘 학습 이론;[10]
- 닉 리틀스톤의 연구에서 비롯된 온라인 기계 학습.
계산 학습 이론의 주요 목표는 학습을 추상적으로 이해하는 것이지만, 실용적인 알고리즘 개발로도 이어졌다. 예를 들어, PAC 이론은 부스팅에 영감을 주었고, VC 이론은 서포트 벡터 머신으로 이어졌으며, 베이즈 추론은 신뢰 망으로 이어졌다.
같이 보기
[편집]각주
[편집]- ↑ “ACL - Association for Computational Learning”.
- 1 2 Valiant, L. G. (1984). “A Theory of the Learnable” (PDF). 《Communications of the ACM》 27 (11): 1134–1142.
- ↑ Kearns, Michael; Vazirani, Umesh (1994년 8월 15일). 《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. 2019년 5월 17일에 원본 문서 (PDF)에서 보존된 문서. 2022년 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.
추가 읽기
[편집]이러한 출판물 중 일부에 대한 설명은 기계 학습의 중요 출판물에서 제공된다.
조사
[편집]- Angluin, D. 1992. Computational learning theory: Survey and selected bibliography. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (May 1992), pages 351–369. http://portal.acm.org/citation.cfm?id=129712.129746
- D. Haussler. Probably approximately correct learning. In AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA, pages 1101–1108. American Association for Artificial Intelligence, 1990. http://citeseer.ist.psu.edu/haussler90probably.html
특징 선택
[편집]- A. Dhagat and L. Hellerstein, "PAC learning with irrelevant attributes", in 'Proceedings of the IEEE Symp. on Foundation of Computer Science', 1994. http://citeseer.ist.psu.edu/dhagat94pac.html
최적 O 표기법 학습
[편집]부정적 결과
[편집]- M. Kearns and 레슬리 밸리언트. 1989. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 433–444, New York. ACM. http://citeseer.ist.psu.edu/kearns89cryptographic.html
오차 허용
[편집]- Michael Kearns and Ming Li. Learning in the presence of malicious errors. SIAM Journal on Computing, 22(4):807–837, August 1993. http://citeseer.ist.psu.edu/kearns93learning.html
- Kearns, M. (1993). Efficient noise-tolerant learning from statistical queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 392–401. http://citeseer.ist.psu.edu/kearns93efficient.html
등가성
[편집]- D.Haussler, M.Kearns, N.Littlestone and M. Warmuth, Equivalence of models for polynomial learnability, Proc. 1st ACM Workshop on Computational Learning Theory, (1988) 42-55.
- Pitt, L.; Warmuth, M. K. (1990). “Prediction-Preserving Reducibility”. 《Journal of Computer and System Sciences》 41 (3): 430–467. doi:10.1016/0022-0000(90)90028-J.
