Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 253
Текст из файла (страница 253)
Таким образом, одним из принципиальных преимуществ алгоритмов Н Р является их применимость для решения гораздо более широкого диапазона задач, включая реляционные задачи. Читатель должен был, безусловно, заметить, что для представления определения Сгапс[рагепе мог бы помочь небольшой фрагмент фоновых знаний. Например, если в состав фоновых знаний вас]сдгоипг] входит следующее высказывание: Рагепе (х, у) ье [мое??ег(х, у) ч Рае?зег(х, у) ] то определение отношения дгапс[рагеп с можно свести к следующему: Сгапс)рагепе(х,у) ьь [Зг Рагепс(х, г) л Рагепс(г,у) ] Этот пример показывает, насколько сушественно фоновые знания позволяют сократить размер гипотез, требуемых для обьяснения результатов наблюдений.
Алгоритмы [!.Р позволяют также создавать новые предикаты для упрошения способов выражения объяснительных гипотез. Применительно к примеру данных, приведенному выше, было бы вполне резонно, чтобы программа [ЬР предложила дополнительный предикат, который можно было бы назвать" Рагепг." (Родитель), для упрощения опрелелений целевых предикатов. Алгоритмы, которые способны вырабатывать новые предикаты, называются алгоритмами ]ж коиструкпвиой индукции. Очевидно, что конструктивная индукция является необходимой частью подхода к обучению на основе накопления знаний, который был кратко описан во введении. Задача нако?пения знаний всегда была одной из сложнейших залач машинного обучения, но некоторые методы П.Р предоставляют эффективные механизмы ее решения.
931 Глава 19. Применение знаний в обучении В оставшейся части данной главы исследуются два принципиальных подхода к индуктивному логическому программированию. В первом из них используется обобщение методов на основе деревьев решений, а во втором используются методы, основанные на инвертировании доказательства с помощью резолюции. Нисходящие методы индуктивного обучения Описанный здесь первый подход к индуктивному логическому программированию начинается с получения очень общего правила и его постепенного уточнения для достижения соответствия с данными.
По сути такой же процесс происходит при обучении деревьев решений, когда дерево решений постепенно наращивается до тех пор, пока не становится совместимым с результатами наблюдений. Но для осуществления индуктивного логического программирования вместо атрибутов используются литералы первого порядка, а вместо дерева решений рассматриваются гипотезы, представляющие собой множества выражений. В этом разделе рассматривается программа рой3 [1258), одна из первых программ ГЬР.
Предположим, что предпринимается попытка изучить определение предиката Стапдта еЛет(х, у) с использованием тех же данных о семейных отношениях, как и перед этим. По такому же принципу, как и при обучении деревьев решений, эти примеры можно разделить на положительные и отрицательные. Положительными примерами являются следующие: (0еотде, лапе), (РЛ31тр, Рееет), (Бреппет, лапту), а отрицательными — такие примеры: (Беотде,Е1ттаЬетЛ), (лапту,вата), (СЛат1ее,РЛт1тр), Обратите внимание на то, что каждый пример представляет собой пару объектов, поскольку этапе)Еа еЛет — это бинарный предикат. В целом в данном генеалогическом дереве имеется 12 положительных примеров и 388 отрицательных (все прочие пары людей). Программа Ро31 строит множества выражений, в каждом из которых Стелс)ЕасЛет(х, у) является головой предиката.
Эти выражения должны классифицировать 12 положительных примеров как экземпляры отношения бтапЖаСЛет(х, у) и вместе с тем исключать 388 отрицательных примеров. Рассматриваемые выражения являются хорновскими выражениями, расширенными с помощью отрицаемых литералов, в которых используется отрицание как недостижение цели, по аналогии с языком Рго!ой. Первоначальное выражение имеет такое пустое тело: => Отапс(татлет (х,у) Это выражение классифицирует каждый пример как положительный, поэтому требует уточнения.
Такую операцию можно выполнить, каждый раз вводя по одному литералу в левую часть выражения. Ниже перечислены три возможных дополнения. татлет(х, у) => этапе(татЛет(х, у) Ратепт(х, т) => отапг)таелет(х,у) уаслет(х, т) => ОтапЖатлет(х,у) (Обратите внимание на то, что здесь предполагается, будто выражение, опрелеляющее предикат ратепе, уже является частью фоновых знаний.) Первое из этих Часть 'у'(. Обучение 932 трех выражений неправильно классифицирует все 12 положительных примеров как отрицательные и поэтому может быть проигнорировано. Второе и третье выражения согласуются со всеми положительными примерами, но второе является неправильным применительно к большей части отрицательных примеров (этих примеров вдвое больше, чем в первом случае, поскольку в них допускается произвольная подстановка данных и о матерях, и об отцах).
Поэтому предпочтительным является третье выражение. Теперь необходимо дополнительно уточнить это выражение, чтобы исключить те случаи, в которых х является отцом некоторого я, но г не является родителем у. Добавление единственного литерала Расеи с ( г, у) позволяет получить следуюшее выражение, которое правильно классифицирует все примеры: Распек(х, я) м Рагепс (я,у) => сгапс)баслег(х,у) Программа Ро11 способна найти и выбрать этот литерал, решая тем самым задачу обучения. Вообще говоря, программе ро11 обычно приходится выполнять поиск среди многих неподходяших выражений, прежде чем она сможет найти правильное решение.
Этот пример может служить очень простой иллюстрацией того, как действует программа Ро11. Набросок обшего алгоритма этой программы приведен в листинге 19.4. По существу, алгоритм повторно составляет выражение, вводя в него один литерал за другим до тех пор, пока это выражение не начинает согласовываться с некоторым подмножеством положительных примеров и при этом не согласуется ни с одним отрицательным примером. Затем положительные примеры, охваченные данным выражением, удаляются из обучающего множества и процесс продолжается до тех пор, пока не остается ни одного положительного примера.
Двумя основными процедурами, требующими пояснения, являются )(еы-Г 1сега1я, которая создает все возможные новые литералы для добавления к выражению, и С)зоояе-г 1сега1, которая выбирает литерал для добавления. Листинг 19.4. Набросок алгоритма Воз1, применяемого для изучения множеств хорновекнх выражений первого порядка на основе прнмеров. Функции нем-ь1еега1в н споове-ьйеега1 описаны в тексте гипссзоп Ро11(ехаюр1ея, Сагдее) гегигпв множество хорновских выражений 1приев: ехамр1ея, множество примеров Сагдее, литерал для целевого предиката 1оса1 чагьаЫев: с1аияея, множество выражений, первоначально пустое мМ1е множество ехаюр1ея содержит положительные примеры бо с1аияе ь — нем-э1аияе(ехатр1ея, сагдеш удалить примеры, охваченные выражением с1аияе, из множества ехаер1ея добавить выражение с1аияе к множеству с1аияея гевигп с1аияея гипссйоп Нем-О1аиве(ехамр1ея, Сагдее) гесигпв хорновское выражение 1оса1 чагйаЪ1еег с1аияе, выражение, головой которого является сагдес, а тело пусто 1, литерал, которьвй должен быть добавлен к выражению с1аияе ехеепдеб ехагпр1ея, множество примеров со значениями для новых переменных 933 Глава 19.
Применение знаний в обучении ехсепдед ехатр1ез < — ехатр1ез мпф1е ехеепдед ехалр1ез содержат отсицательные примеры ао 1 < — синове-иьсета1(неы-гфтета1з(с1анзе), ехеепдед ехатр1ез) добавить 1 к телу выражения с1анзе ехеепдес) ехатр1ез ь- множество примеров, созданных путем применения функции Вхеепд-Ехатр1е к каждому примеру в множестве ехеепдед ехатр1ез тетптп с1анзе тндсефоп вхсепд-вхаир1е(ехаер1е, 11еета1) теептпв множество примеров ЬЕ пример ехаер1е согласуется с литералом 11еета1 епеп теситп множество примеров, созданное путем дополнения примера ехатр1е каждым возможным значением константы для каждой новой переменной в литерале 11СЕта1 е1ве тетитп пустое множество Процедура ))еы-г 1сета1з выбирает некоторое выражение и составляет все возможные "полезные'* литералы, которые могут быть добавлены к этому выражению.
Рассмотрим в качестве примера следующее выражение: каплет(х, т) => стапдгас)1ет(х,у) К нему могут быть добавлены три описанные ниже разновидности литералов. 1. Литералы, в которых используются предикаты. Литерал может быть отрицаемым или неотрицаемым, в нем может применяться любой существующий предикат (включая целевой предикат), а все параметры должны быть переменными. В качестве любого параметра предиката может использоваться любая переменная, с учетом одного ограничения; каждый литерал должен включать по меньшей мере одну переменную из предыдущего литерала или из головы выражения.
Такие литералы, как мотает(т, и), ГГаттдед(з,у), ма1е(у) и стапдйасзет( у, х), являются допустимыми, а иаттд ед(и, у)— нет. Обратите внимание на то, что благодаря имеющейся возможности применять предикат из головы выражения программа ро11 может использоваться для изучения рекурсивных определений. 2. Литералы равенства и неравенства.
Эти литералы связывают переменные, уже присутствующие в данном выражении. Например, можно ввести литерал тех. Данные литералы могут также включать константы, заданные пользователем. Для изучения арифметических выражений могут использоваться константы О и 1, а для изучения функций, заданных на списках, — пустой список ( ) . 3. Арифметические сравнения. При обработке функций непрерывных переменных могут быть добавлены такие литералы, как х>у и у<т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
