Примеры и гипотезы
Вернемся к описанной в главе 18 задаче обучения с рестораном, в которой нужно было изучить правило принятия решения о том, при каких условиях следует ждать освобождения столика. В этой главе для описания примеров применялись атрибуты, такие как Al ternate, Bar, Fri/Sat и т.д. В логической формулировке задачи любой пример представляет собой объект, для описания которого используется логическое высказывание, а атрибуты становятся унарными предикатами. Примем общее обозначение xL для i-ro примера. В частности, первый пример, приведенный в табл. 18.1, может быть описан с помощью таких высказываний:
AlternateiXi) л -iBar(Xi) л -.Fri/Sat (Xi) л Нипдгу{Хг) л ...
Обозначение DL(Xi) будет использоваться для ссылки на описание Xi? где Di может представлять собой любое логическое выражение, принимающее один параметр. Классификация объекта определяется примерно таким высказыванием:
WillWait (Xi)
Общее обозначение Q(XL) будет применяться, если пример является положительным, a -iQ(Xi) — если отрицательным. В таком случае полное обучающее множество представляет собой конъюнкцию всех описательных и классификационных высказываний.
Целью индуктивного обучения в логической постановке задачи является поиск эквивалентного логического выражения для целевого предиката Q, который может использоваться для правильной классификации примеров. Подобное выражение, которое мы будем называть потенциальным определением целевого предиката, предлагается в каждой гипотезе. Используя d для обозначения потенциального определения, можно утверждать, что каждая гипотеза Hi представляет собой высказывание в форме Vx Q(x) <=>Ci (х). В частности, дерево решений представляет собой утверждение, что целевой предикат принимает истинное значение по отношению к какому-то объекту тогда и только тогда, когда выполняются условия в одной из ветвей, ведущих к листовому узлу со значением true. Таким образом, на рис. 18.4 в графической форме выражено следующее логическое определение (которому мы присвоим обозначение Яг для использования его в будущем):
Vr WillWait [г) <=> Patrons {г, Some)
v Patrons{г,Full) л Hungry(г) л Туре{г,French)
v Patrons{г,Full) л Hungryir) л Type[r,Thai)
л Fri/Sat(г)
v Patrons {г, Full) л Hungry (г) л Туре (г, Burger) (19.1)
Каждая гипотеза предсказывает, что некоторое множество примеров (а именно множество тех примеров, которые соответствуют ее потенциальному определению) будет представлять собой примеры целевого предиката. Такое множество называется
расширением предиката. Это означает, что две гипотезы с разными расширениями являются логически несовместимыми друг с другом, поскольку они не согласуются в своих предсказаниях по меньшей мере в одном примере. А если две гипотезы имеют одно и то же расширение, они логически эквивалентны.
Пространство гипотез н алгоритма обучения представляет собой множество всех гипотез {я1;...,Яп}, для поддержки которых предназначен данный конкретный обучающий алгоритм. Например, алгоритм Decision-Tree-Learning способен поддерживать любую гипотезу в дереве решений, определенную в терминах заранее предусмотренных атрибутов, поэтому пространство гипотез этого алгоритма состоит из всех таких деревьев решений. Предполагается, что алгоритм обучения позволяет с полной уверенностью утверждать, что одна из гипотез является правильной; это означает, что данный алгоритм выражает определенную степень уверенности в истинности следующего высказывания:
ft v Я2 v Я3 v ... v Яп (19.2)
По мере поступления новых примеров появляется возможность исключать гипотезы, не совместимые с этими примерами. Рассмотрим более внимательно затронутое здесь понятие совместимости. Очевидно, что если гипотеза HL совместима со всем обучающим множеством, то она должна быть совместимой с каждым примером. А что повлекла бы за собой его несовместимость с одним из примером? Такая ситуация может проявиться в одном из двух описанных ниже вариантов.
• Некоторый пример может оказаться ложно отрицательным для данной гипотезы, если гипотеза утверждает, что он должен быть отрицательным, но фактически этот пример положителен. В частности, новый пример Х13, описанный выражением
Patrons (Xn, Full) л Wai t {Х1Ъ, 0-10 ) л -Hungry (Х1Ъ) л ... л WillWait (Х13>)
был бы ложно отрицателен для гипотезы Яг, приведенной выше. Из гипотезы Яг и описания этого можем вывести и выражение WillWait (Х13), которое как раз является утверждением данного примера, и выражение -л WillWait (Х13), которое представляет собой предсказание самой гипотезы. Поэтому в данном случае гипотеза и пример логически несовместимы.
• Пример может быть ложно положительным для данной гипотезы, если в гипотезе утверждается, что он должен быть положительным, но фактически он является отрицательным1.
Если некоторый пример является ложно положительным или ложно отрицательным применительно к некоторой гипотезе, то данный пример и данная гипотеза являются логически несовместимыми друг с другом. При условии, что рассматриваемый пример представляет собой правильное наблюдение факта, такая ситуация позволяет исключить данную гипотезу. С точки зрения логики соответствующая операция исключения гипотезы полностью аналогична операции применения правила резолюции в логическом выводе (см. главу 9); в этой аналогии дизъюнкция гипотез соответствует выражению, а пример соответствует литералу, который взаимно уничтожается с одним из литералов выражения. Поэтому в принципе может быть обеспечено обучение на примерах обычной системы логического вывода путем удаления одной или нескольких гипотез. В частности, предположим, что пример оформлен в виде высказывания Х1? а пространство гипотез представляет собой высказывание H1vH2vH3vH4. В таком случае, если высказывание 1г несовместимо с выражениями я2 и я3, то система логического вывода может сформировать новое высказывание HxvH4, соответствующее уточненному пространству гипотез.
Таким образом индуктивное обучение в логической постановке задачи можно охарактеризовать как процесс постепенного устранения гипотез, несовместимых с примерами, и сужения пространства возможных гипотез. Но поскольку пространство гипотез обычно является колоссальным (или даже бесконечным, в случае логики первого порядка), не рекомендуется даже пытаться создать систему обучения с использованием доказательства теорем на основе резолюции и полного перебора пространства гипотез. Вместо этого в этой главе будут описаны два подхода, которые позволяют находить логически совместимые гипотезы с гораздо меньшими усилиями.