Проблема обучения на примерах обычно формулируется следующим образом. Имеется некоторое целевое понятие С, которое необходимо освоить. Кроме того, существует некоторый язык гипотез L, на котором могут формулироваться гипотезы, касающиеся С. Определение понятия С не дано, и единственным источником информации для освоения понятия С является множество классифицированных примеров. Обычно примеры заданы в виде пар (Object, Class), где Class указывает, к какому понятию относится объект Object. Целью обучения является составление на языке гипотез L формулы Н, в максимально возможной степени соответствующей целевому понятию С. Но как узнать, насколько хорошо формула Н соответствует понятию С? Единственный способ оценить, насколько полно Н соответствует С, состоит в использовании множества примеров S. Оценка качества Н осуществляется на множестве примеров S. Если Н обычно классифицирует примеры в S правильно (т.е. относит их к тем же классам, какие указаны в этих примерах), то можно надеяться, что Н позволит столь же правильно классифицировать другие, новые объекты. Поэтому обоснованный подход состоит в том, что среди возможных гипотез должна быть выбрана такая гипотеза, которая позволяет снова отнести все примеры объектов к тому же классу, который указан в множестве S. Такая гипотеза называется совместимой с данными. Совместимая гипотеза характеризуется 100%-ной точностью классификации учебных данных. Но, безусловно, нас больше интересует точность предсказания с помощью некоторой гипотезы: "Насколько точно эта гипотеза предсказывает класс новых объектов, не заданных в S?" Точность предсказания - это вероятность правильной классификации объектов, выбранных случайным образом в области определения задачи обучения. Хотя на первый взгляд это может показаться удивительным, но иногда обнаруживается, что гипотезы, которые достигают наивысшей точности при распознавании учебных данных S, не показывают столь же впечатляющих достижений при распознавании новых данных, не принадлежащих к S. Это наблюдение особенно характерно для обучения по зашумленным данным, когда учебные данные содержат ошибки. Данная тема рассматривается в разделе 18.6.
Чаще всего критерием успеха в индуктивном машинном обучении является точность предсказаний на основе логически выведенных гипотез. Но есть и другие кри-
Глава 18. Машинное обучение 413
терии успеха; наиболее широко известным из них является критерий достижимости, или "понятности", выведенных гипотез. Он определяет, насколько осмысленными являются выведенные гипотезы для человека-эксперта. Эта тема рассматривается более подробно в разделе 18.7.
