Теорія обчислювального навчання

В інформатиці теорія обчислювального навчання (або просто теорія навчання) — підгалузь штучного інтелекту, яка вивчає проєктування та аналіз алгоритмів машинного навчання.^[1]

Огляд

Теоретичні результати машинного навчання часто зосереджені на типі індуктивного навчання, відомому як навчання з учителем. У навчанні з учителем алгоритму надаються позначені зразки^[en]. Наприклад, зразки можуть бути описами грибів із позначками, які вказують, чи гриби їстівні, чи ні. Алгоритм використовує ці позначені зразки для створення класифікатора. Цей класифікатор призначає позначки новим зразкам, включно з тими, з якими він раніше не стикався. Метою алгоритму навчання з учителем є оптимізація показників продуктивності, як-от мінімізація помилок на нових зразках.

Окрім меж продуктивності, теорія обчислювального навчання вивчає часову складність та доцільність навчання.^{[джерело?]} В теорії обчислювального навчання обчислення вважається можливим, якщо його можна виконати за поліноміальний час.^{[джерело?]} Існує два види результатів часової складності:

Позитивні результати – показують, що певний клас функцій можна вивчити за поліноміальний час.
Негативні результати – показують, що певні класи неможливо вивчити за поліноміальний час.^[2]

Негативні результати часто спираються на загальноприйняті, але ще не доведені припущення,^{[джерело?]} наприклад:

Обчислювальна складність — P ≠ NP (задача P проти NP) ;
Криптографічні — існують односторонні функції.

Існує кілька різних підходів до теорії обчислювального навчання, що базуються на різних припущеннях щодо принципів виведення, які використовуються для узагальнення з обмежених даних. Сюди входять різні визначення ймовірності (див. частотницька ймовірність, байєсова ймовірність) та різні припущення щодо генерування вибірок.^{[джерело?]} Різні підходи включають:

Точне навчання, запропоноване Даною Англуїн^[en];^[3]^[4]
Ймовірнісно приблизно коректне навчання (ЙПК-навчання), запропоноване Леслі Веліантом;^[5]
Теорія ВЧ, запропонована Володимиром Вапником та Олексієм Червоненкісом^[ru];^[6]
Індуктивний висновок^[en], розроблений Реєм Соломоновим^[en];^[7]^[8]
Теорія алгоритмічного навчання^[en], з праці Е. Марка Ґолда^[en];^[9]
Інтерактивне машинне навчання, з праці Ніка Літтлстоуна.^{[джерело?]}

Хоча її основною метою є абстрактне розуміння навчання, теорія обчислювального навчання дала змогу розробити практичні алгоритми. Наприклад, теорія ЙПК-навчання надихнула на принцип підсилювання, теорія ВЧ привела до машин на опорних векторах, а баєсівський висновок привів до мереж довіри.

Див. також

Теорія інформації

Примітки

↑ ACL - Association for Computational Learning.
↑ Kearns, Michael; Vazirani, Umesh (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. Архів оригіналу (PDF) за 17 травня 2019. Процитовано 24 листопада 2022.
↑ 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 (Березень 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

Oded Goldreich, Dana Ron. On universal learning algorithms. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2224

Негативні результати

M. Kearns and Leslie Valiant. 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^{[недоступне посилання з 01.08.2024]}

Допустимість помилок

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.

Посилання

Основи баєсового виведення

[ACL-1] ACL - Association for Computational Learning.

[2] Kearns, Michael; Vazirani, Umesh (15 серпня 1994). An Introduction to Computational Learning Theory. MIT Press. ISBN 978-0262111935.

[3] 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.

[4] D. Angluin (1978). On the Complexity of Minimum Inference of Regular Sets. Information and Control. 39 (3): 337—350.

[5] Valiant, Leslie (1984). A Theory of the Learnable (PDF). Communications of the ACM. 27 (11): 1134—1142. doi:10.1145/1968.1972. S2CID 12837541. Архів оригіналу (PDF) за 17 травня 2019. Процитовано 24 листопада 2022.

[6] 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.

[7] Solomonoff, Ray (Березень 1964). A Formal Theory of Inductive Inference Part 1. Information and Control. 7 (1): 1—22. doi:10.1016/S0019-9958(64)90223-2.

[8] 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.

[9] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]