Точность гипотез

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

Чаще всего критерием успеха в индуктивном машинном обучении является точ­ность предсказаний на основе логически выведенных гипотез. Но есть и другие кри-

Глава 18. Машинное обучение 413

терии успеха; наиболее широко известным из них является критерий достижимости, или "понятности", выведенных гипотез. Он определяет, насколько осмысленными являются выведенные гипотезы для человека-эксперта. Эта тема рассматривается бо­лее подробно в разделе 18.7.