Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 237
Текст из файла (страница 237)
Интуитивно ясно, что такой подход имеет смысл, поскольку гипотезы не позволяют извлекать из данных какую-либо информацию, если они не проще самих данных. Определить, какая гипотеза проще, а какая сложнее, обычно нелегко, но, повидимому, вполне резонным является утверждение, что полипом первой степени проще по сравнению с полиномом двенадцатой степени. 1(х) 1(х) 1(х) 1(х) в) б) а) Рис. 1б.1. Типичные задачи обучения: пример пар (х, х (х) ) и совместимой линейной гипотезы (а); совместимая гипотеза для того же набора данных в виде полинома седьмой степени (б); другой набор данник который точно соответствует папиному шестой степени или приблизительно соответствует прямой линии (в); простая синусоидальная функция, которая точно соответствует тому же набору данных (г) На рис.
18.1, в показан второй набор данных. С этим набором данных нельзя совместить прямую линию; в действительности для обеспечения точного согласования с ним требуется полипом шестой степени (с семью параметрами). Количество точек равно только семи, поэтому полином должен иметь столько же параметров, сколько имеется точек данных; таким образом„создается впечатление, что этот полипом не позволяет найти в данных какие-либо повторяюгциеся шаблоны, и поэтому не следует ожидать, что с его помощью будет получено хорошее обобзцение. Может оказаться, что лучше согласовать этот набор данных с прямой линией, которая не будет точно совместимой, но позволит получать вполне обоснованные предсказания.
Принятие данного решения равносильно признанию такой возможности, что истинная функция не является детерминированной (или, что примерно эквивалентно з Этот принцип получил название в честь английского философа Х1У века Уильяма нз Окхсмв, но в его обозначении название города, в котором работал философ, записывают квк "Окквм", в соответствии с французской транскрипцией, тдшйвшпс С'Оссагп" — Гийом нз Оккама. Глава 18.
Обучение на основе наблюдений 869 этому утверждению, истинные входные данные не являются полностью наблюдаемыми). сЗь При наличии недетерминированных функций неизбежно приходится искать компромисс между сложностью гипотезы и степенью ее согласования с даннььни. В главе 20 показано, как достичь этого компромисса с помошью теории вероятностей. Следует всегда учитывать, что возможность или невозможность найти простую, согласованную гипотезу зависит главным образом от выбранного пространства гипотез.
На рис. 18.1, г показано, что данные, приведенные на рис. 18.1, в, могут быть точно согласованы с простой функцией в форме ах+Ь+свйпх. Этот пример подчеркивает важность выбора пространства гипотез. Пространство гипотез, состоящее из полиномов конечной степени, не позволяет точно представить синусоидальные функции, поэтому ученик, используюший такое пространство гипотез, не сможет осушествить обучение с использованием синусоидальных данных. Принято считать, что задача обучения является Ъ. реализуемой, если пространство гипотез содержит подходящую функцию; в противном случае она является сь нереализуемой. К сожалению, в любой ситуации невозможно сразу же определить, относится ли данная конкретная задача обучения к категории реализуемых, поскольку не известна истинная функция. Один из способов, позволяюьцих преодолеть этот барьер, состоит в использовании априорных знаний для логического вывода пространства гипотез, в котором, как известно, должна находиться истинная функция.
Эта тема рассматривается более подробно в главе! 9. Еше один подход состоит в применении наибольшего возможного пространства гипотез. Например, почему бы не использовать в качестве и класс всех машин Тьюринга? В конечном итоге любая вычислимая функция может быть представлена с помошью некоторой машины Тьюринга, и это — наилучший способ представления, который только может применяться. Но при реализации этой идеи возникает проблема, связанная с тем, что в ней не учитывается вычислительная сложность обучения. зг' Необходима найти компромисс между выразительностью пространства гипотез и сложностью поиска простой, совместимои гипотезы в этом пространстве. Например, подгонка к данным прямых линий осуществляется очень просто; подбор полиномов высокой степени становится сложнее, а создание соответствуюших машин Тьюринга действительно представляет собой очень сложную задачу, поскольку неразрешима в обшем виде даже проблема определения того, является ли конкретная машина Тьюринга совместимой с данными.
Второй причиной, по которой следует предпочесть простые пространства гипотез, является то, что результирующие гипотезы могут оказаться более простыми в использовании, т.е. вычисление )з)х), если )з — линейная функция, будет осушествляться быстрее, чем при использовании программы, моделирующей произвольную машину Тьюринга. По этим причинам основной объем исследований в области обучения был сосредоточен на относительно простых способах представления. В данной главе в основном рассматриваются пропозициональная логика и связанные с ней языки. В главе 19 рассматриваются теории обучения в логике первого порядка. Ниже будет показано, что компромисс между выразительностью и сложностью найти не так просто, как кажется на первый взгляд, поскольку, как было описано в главе 8, выразительный язык позволяет создать простую теорию, согласующуюся с данными, а ограничение выразительности языка приводит к тому, что любая согласованная теория должна стать очень сложной.
Например, правила шахмат могут быть записаны в 870 Часть У). Обучение логике первого порядка на одной или двух страницах, но потребуют тысячи страниц при их формулировке в пропозициональной логике. Кроме того, в подобных случаях при использовании более выразительного языка намного ускоряется обучение. 18.3.
ФОРМИРОВАНИЕ ДЕРЕВЪЕВ РЕШЕНИЙ НА ОСНОВЕ ОБУЧЕНИЯ Индуктивный логический вывод деревьев решений представляет собой одну из простейших и вместе с тем наиболее успешных форм алгоритмов обучения. Эта тема может служить хорошим введением в проблематику индуктивного обучения, а алгоритмы, разработанные в ее рамках, легко поддаются реализации. В настоящем разделе вначале описан производительный элемент проекта агента, а затем показано, как обеспечить его обучение.
В ходе этого изложения представлены основные понятия, которые применяются во всех областях индуктивного обучения. Деревья решений, рассматриваемые как производительные элементы 'в. Дерево решений принимает в качестве входных данных объект или ситуацию, описанную с помощью множества 'ж атрибутов, и возвращает "решение" — предсказанное выходное значение, соответствующее входным данным. Входные атрибуты могут быть дискретными или непрерывными. На данный момент подразумевается, что входные данные являются дискретными. Выходные значения также могут быть дискретными или непрерывными; процесс формирования в ходе обучения функции с дискретными значениями называется обучением 'а. классификации; формирование в ходе обучения непрерывной функции называется обучением 'сь регрессии. Вначале мы сосредоточимся на булевой классификации, согласно которой каждый пример обозначается как истинный (сь положительный) или ложный (Ж отрицательный).
Дерево решений позволяет перейти к содержащемуся в нем решению путем выполнения последовательности проверок. Каждый внутренний узел в дереве соответствует проверке значения одного из свойств, а ветви, исходящие из этого узла, обозначены возможными значениями результатов проверки. Каждый листовой узел в дереве задает значение, возвращаемое после достижения этого листа. Повидимому, представление в виде дерева решений кажется людям вполне естественным; в действительности многие инструктивные руководства (например, по ремонту автомобилей) полностью оформлены в виде одного дерева решений, разбросанного по нескольким сотням страниц. Несколько более простой пример может быть основан на применении методов обучения к задаче, в которой клиент ждет, пока освободится место за столиком в ресторане.
Цель состоит в том, чтобы изучить определение для Ж целевого предиката гуз22ягаз с (Следует ли ждать). Подготавливая данный пример для использования в качестве задачи обучения, необходимо вначале определить, какие атрибуты доступны для описания примеров ситуаций в данной проблемной области. В главе!9 будет показано, как автоматизировать выполнение этого этапа, а на данный момент предположим, что решено использовать приведенный ниже список атрибутов. Главз 1К.
ОГючснке на основе н,'баю ~ ний 872 Часть \г). Обучение Выразительность деревьев решений С точки зрения логики любая конкретная гипотеза из дерева решений для целевого п реди ката ))гз 2 2 Я)аз Г может рассматриваться как угверждение в следующей форме: Ча ягггт)гадс(а) аа (гг(а) ч )гг(а) ч ... ч )г,(а) ) где каждое условие Р,(а) представляет собой конъюнкцию проверок, соответствуюших пути от корня дерева к листу с положительным результатом.
Хотя это выражение с виду напоминает высказывание в логике первого порядка, оно в определенном смысле является пропозициональным, поскольку содержит только одну переменную, а все предикаты являются унарными. Это дерево решений фактически описывает связь между предикатом и(з22игаа с и некоторой логической комбинацией значений атрибутов. Деревья решений не могут использоваться для представления проверок, относящихся к двум или нескольким разным объектам, например, таких проверок, как показано ниже (?Есть ли поблизости более дешевый ресторант).
Згг )уаагЬу(гг,г) л Рггсе(г,р) л гггаа(гг,рг) л С)гаарег(рг,р) Очевидно, что можно было бы ввести еше один булев атрибут с именем С?геарехяеасаигапсьеагЬу (Наличие поблизости более дешевого ресторана), но задача введения всех подобных атрибутов является трудно осушествимой. В главе 19 приведены дополнительные сведения о задаче правильного обучения в логике первого порядка. Деревья решений в рамках класса пропозициональных языков являются полностью выразительными; это означает, что в виде дерева решений может быть оформлена любая булева функция. Такую задачу можно выполнить тривиально, предположив, что каждая строка в истинностной таблице для данной функции соответствует определенному пути в дереве. Но подобный подход приводит к получению представления в виде дерева решений с экспоненциальными размерами, поскольку количество строк в истинностной таблице увеличивается экспоненциально, тогда как очевидно, что деревья решений позволяют представить многие функции с помощью гораздо меньших деревьев.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
