Теорія навченого

Валіант дав означення: клас понять навченний, якщо існує алгоритм, що за поліноміальний час і розумну кількість прикладів дає майже правильну відповідь з великою ймовірністю.

Чому це важливо

Навчання отримало означення, у якому можна довести неможливість, — і питання «скільки прикладів треба» стало математичним.

Модель відома як імовірно приблизно правильне навчання. Ключове те, що вимога послаблена двічі: відповідь має бути приблизною і лише ймовірно такою. Без цих послаблень майже нічого не навченне. З моделі виросла обчислювальна теорія навчання, зв'язок із розмірністю Вапника-Червоненкіса і бустинг. Валіант отримав премію Тюрінга 2010 року.

Відомості про подію

Дата події

листопад 1984 р.

Дата на часовій осі

Дата події

Перевірка

Джерела зібрано автоматично · 17 вересня 2026 р.

Лінії

Теорія навчання

ID

evt-0144

Випуск Communications of the ACM за листопад 1984 року.

Леслі Веліант

Джерела

першоджерело A theory of the learnable (publisher record)
ACM · Опубліковано листопад 1984 р.
архівна копія A Theory of the Learnable
Communications of the ACM · Опубліковано листопад 1984 р.

Пов’язані події

Раніше

Спирається на Теорема Кука 1971
Навченість визначено через існування алгоритму, що працює за поліноміальний час.
- A Theory of the Learnable · Communications of the ACM
Пов’язано Формальна теорія індуктивного висновку 1964
Друга відповідь на питання, що означає навчитися з прикладів, цього разу обчислювана.

Пізніше

Пов’язано Ядровий трюк і опорні вектори 1992посилається на цей запис
Належить до тієї самої програми навчання з доведеними гарантіями.
Пов’язано Штучний інтелект: сучасний підхід 1995посилається на цей запис
Книга будує виклад навколо раціонального агента, спираючись на теорію навчання і рішень.
Спирається на AdaBoost 1995посилається на цей запис
Відповідає на питання, поставлене в теорії навченого: чи можна зі слабкого учня зробити сильного.
- A decision-theoretic generalization of on-line learning and an application to boosting · EuroCOLT 1995