В інформатиці теорія обчислювального навчання (або просто теорія навчання) — підгалузь штучного інтелекту, яка вивчає проєктування та аналіз алгоритмів машинного навчання.
Огляд Теоретичні результати машинного навчання часто зосереджені на типі індуктивного навчання, відомому як навчання з учителем. У навчанні з учителем алгоритму надаються . Наприклад, зразки можуть бути описами грибів із позначками, які вказують, чи гриби їстівні, чи ні. Алгоритм використовує ці позначені зразки для створення класифікатора. Цей класифікатор призначає позначки новим зразкам, включно з тими, з якими він раніше не стикався. Метою алгоритму навчання з учителем є оптимізація показників продуктивності, як-от мінімізація помилок на нових зразках.
Окрім меж продуктивності, теорія обчислювального навчання вивчає часову складність та доцільність навчання. В теорії обчислювального навчання обчислення вважається можливим, якщо його можна виконати за поліноміальний час. Існує два види результатів часової складності:
Позитивні результати показують, що певний клас функцій можна вивчити за поліноміальний час. Негативні результати показують, що певні класи неможливо вивчити за поліноміальний час.
Негативні результати часто спираються на загальноприйняті, але ще не доведені припущення, наприклад:
Обчислювальна складність — P ≠ NP (задача P проти NP) ; Криптографічні — існують односторонні функції.
Існує кілька різних підходів до теорії обчислювального навчання, що базуються на різних припущеннях щодо принципів виведення, які використовуються для узагальнення з обмежених даних. Сюди входять різні визначення ймовірності (див. частотницька ймовірність, байєсова ймовірність) та різні припущення щодо генерування вибірок. Різні підходи включають:
Точне навчання, запропоноване ; Ймовірнісно приблизно коректне навчання (ЙПК-навчання), запропоноване Леслі Веліантом; Теорія ВЧ, запропонована Володимиром Вапником та ; , розроблений ; , з праці ; Інтерактивне машинне навчання, з праці Ніка Літтлстоуна.
Хоча її основною метою є абстрактне розуміння навчання, теорія обчислювального навчання дала змогу розробити практичні алгоритми. Наприклад, теорія ЙПК-навчання надихнула на принцип підсилювання, теорія ВЧ привела до машин на опорних векторах, а баєсівський висновок привів до мереж довіри.
Див. також Теорія інформації
Примітки
Література Опис деяких із цих результатів наведено у важливих публікаціях з машинного навчання.
Дослідження 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
Допустимість помилок
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.
Посилання
Основи баєсового виведення