Один из важных вопросов, поставленных в разделе 18.2, на который не был получен ответ, состоял в следующем: как можно убедиться в том, что в результате применения разработанного кем-то обучающего алгоритма была создана теория, позволяющая правильно предсказывать будущее? Формально этот вопрос можно переформулировать следующим образом: как определить, насколько гипотеза h близка к целевой функции f, если неизвестно, каковой является сама функция f? Подобные вопросы были предметом размышлений ученых в течение нескольких столетий. До тех пор, пока на них не будут получены ответы, машинное обучение в лучшем случае может рассматриваться лишь как научная область, причины успешных достижений которой остаются необъяснимыми.

Подход, принятый в данном разделе, основан на теории вычислительного обучения— научной области, которая находится на стыке искусственного интеллекта, статистики и теоретических компьютерных наук. Принцип, лежащий в ее основе, состоит в следующем: любая гипотеза, которая содержит серьезные ошибки, почти наверняка будет "открыта" с большой вероятностью после обработки небольшого количества примеров, поскольку она дает неправильные предсказания. Поэтому любая гипотеза, согласованная с достаточно большим множеством обучающих примеров, с меньшей вероятностью будет содержать серьезные ошибки; это означает, что она обязательно будет приблизительно правильной с определенной вероятностью. Любой обучающий алгоритм, вырабатывающий гипотезы, которые с определенной вероятностью являются приблизительно правильными (Probably Approximately Correct — РАС), называется алгоритмом РАС-обучения.

При анализе приведенных выше доводов необходимо учитывать некоторые нюансы. Основной вопрос состоит в том, какова связь между обучающими и проверочными примерами; в конечном итоге желательно, чтобы гипотеза была приблизительно правильной применительно к проверочному множеству, а не только к обучающему множеству. Основное предположение состоит в том, что и обучающее, и проверочное множества примеров извлекаются случайно и независимо друг от друга из одной и той же популяции примеров с одним и тем же распределением вероятностей. Это предположение называется предположением о стационарности. Если не принято предположение о стационарности, то теория вычислительного обучения не позволяет формулировать вообще какие-либо утверждения о будущем, поскольку не определена необходимая связь между будущим и прошлым. Предположение о стационарности равносильно тому предположению, что процесс, в котором осуществляется отбор примеров, не подвержен неблагоприятному влиянию. Очевидно, что если обучающее множество состоит только из надуманных примеров (например, фотографий двухголовых собак), то обучающий алгоритм не сможет сделать ничего иного, кроме как предложить безуспешные обобщения, касающиеся того, как распознавать обычных собак.