Вернемся к описанной в главе 18 задаче обучения с рестораном, в которой нужно было изучить правило принятия решения о том, при каких условиях следует ждать освобождения столика. В этой главе для описания примеров применялись атрибуты, такие как Alternate, Bar, Fri/Sat и т.д. В логической формулировке задачи любой пример представляет собой объект, для описания которого используется логическое высказывание, а атрибуты становятся унарными предикатами. Примем общее обозначениедля i-гo примера. В частности, первый пример, приведенный в табл. 18.1, может быть описан с помощью таких высказываний:

Обозначениебудет использоваться для ссылки на описание, где может представлять собой любое логическое выражение, принимающее один параметр. Классификация объекта определяется примерно таким высказыванием:

Общее обозначение будет применяться, если пример является положительным, а— если отрицательным. В таком случае полное обучающее множество представляет собой конъюнкцию всех описательных и классификационных высказываний.

Целью индуктивного обучения в логической постановке задачи является поиск эквивалентного логического выражения для целевого предиката Q, который может использоваться для правильной классификации примеров. Подобное выражение, которое мы будем называть потенциальным определением целевого предиката, предлагается в каждой гипотезе. Используядля обозначения потенциального определения, можно утверждать, что каждая гипотезапредставляет собой высказывание в форме. В частности, дерево решений представляет собой утверждение, что целевой предикат принимает истинное значение по отношению к какому-то объекту тогда и только тогда, когда выполняются условия в одной из ветвей, ведущих к листовому узлу со значением true. Таким образом, на рис. 18.4 в графической форме выражено следующее логическое определение (которому мы присвоим обозначениедля использования его в будущем):

(19.1)