Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 254
Текст из файла (страница 254)
По аналогии с обучением деревьев решений могут быть выбраны пороговые значения для максимизации различительной мощи проверки. Возникающий в результате коэффициент ветвления в этом пространстве поиска очень велик (см. упр, 19.6), но в программе ро11 для его уменьшения может также использоваться информация о типе. Например, если проблемная область включает 934 Часть ЪЧ. Обучение данные не только о числах, но и о людях, то ограничения типов позволят исключить возможность выработки в процедуре нем-).ьсепа1я таких литералов, как Рапепс(х, и), где х — человек, ап — число. В процедуре С)зоояе-т ьсега1 используется эвристика, немного напоминающая эвристику, основанную на приросте информации (см.
с, 878), для определения того, какой литерал должен быть выбран для добавления. Точные сведения о том, как это осушествляется, не имеет в контексте данной главы слишком большого значения, к тому же было опробовано много различных вариантов таких эвристик. Одно интересное дополнительное средство программы Ро11 состоит в использовании принципа бритвы Оккама для устранения некоторых гипотез. Если некоторое выражение становится длиннее (согласно определенной метрике), чем общая длина положительных примеров, объясняемых с помощью этого выражения, оно больше не рассматривается в качестве потенциальной гипотезы. Такой метод предоставляет удобный способ предотвращения создания чрезмерно сложных выражений, которые обусловлены наличием шума в данных.
Объяснение связи между шумом и ллиной выражений приведено на с. 949. Программа Ро11 и аналогичные ей программы использовались для изучения широкого ряда определений. Одна из наиболее впечатляющих демонстраций возможностей таких программ [1260] касалась решения длинной последовательности упражнений по функциям обработки списков из учебника по языку Рго)ой, написанного Братке [! 74). В каждом случае программа показала свою способность найти в процессе обучения правильное определение функции на основе небольшого множества примеров, используя в качестве фоновых знаний ранее изученные функции.
Индуктивное обучение с помощью обратной дедукции Второй важный подход к индуктивному логическому программированию предусматривает обращение обычного процесса дедуктивного доказательства. Метод 'в. обратной резолюции основан на том наблюдении, что если классификация С1аяяхЕхсасхопя примера следует из выражения нас)сдпоипблнурос)зеяхялреяспхрсхопя, то должна существовать возможность доказать этот факт с помощью метода резолюции (поскольку метод резолюции является полным).
А если есть возможность "провести доказательство в обратном направлении, то можно наЙти такую гипотезу нуроспеяхя, через которую проходит это доказательство. Поэтому задача состоит в том, чтобы найти способ обращения процесса резолюции. В этом разделе будет показан процесс обратного доказательства для инверсного правила резолюции, который состоит из отдельных обратных этапов. Напомним, что в обычном этапе резолюции берутся два выражения, С, и С„и к ним применяется операция уничтожения взаимно противоположных литералов (операция резолюции) для получения резольвенты с.
С другой стороны, на этапе инверсной резолюции берется резольвента Си формируются два выражения, С, и С,, такие, что сявляется результатом применения операции уничтожения взаимно противоположных литералов в выражениях С, и С,. Еше один вариант состоит в том, что можно взять резольвенту С и выражение С, и сформировать выражение С„такое, что С является результатом применения операции резолюции к С, и Се Начальные этапы процесса обратной резолюции показаны на рис. 19.9; на этих этапах вся работа сосредоточивается на положительном примере бгапс)рапепс 936 Часть |Ч. Обучение Более того, выражения, которые участвуют на каждом этапе, могут быть выбраны из фоновых знаний Вас)сдпоипд, из описаний примеров Резспурс1опэ, из отрицаемых выражений в множестве с1аээуГусагуопэ или из выражений, выдвинутых в качестве гипотезы, которые уже были сформированы в дереве обратной резолюции. Такое большое количество возможностей означает, что без дополнительного управления возникает большой коэффициент ветвления (и поэтому поиск становится неэффективным).
В реализованных на практике системах 1ЬР был опробован целый ряд подходов к управлению поиском, в том числе подходы, описанные ниже. 1. Могут быть удалены избыточные варианты выбора, например, путем формирования только наиболее конкретных гипотез из всех возможных и соблюдения требования о том, чтобы все выражения, принятые в качестве гипотез, были совместимыми и друг с другом, и с результатами наблюдений. Применение последнего критерия позволило бы исключить выражение — рапепс1а,у) чспапс)рапепе1сеопде, у), приведенное выше.
2. Могут быть наложены ограничения на стратегию доказательства. Например, в главе 9 было показано, что линейная резолюция — это полная, ограниченная стратегия, которая позволяет создавать только такие деревья доказательства, которые имеют линейную структуру ветвления (как на рис. 19.9). 3. Могут быть наложены ограничения на язык представления, например, путем устранения функциональных символов или применения только хорновских выражений. Например, язык Ргойо1 оперирует с хорновскими выражениями с использованием 'а. обратного логического следствия. Идея этого метода состоит в том, что ограничение логического следствия: Вас)гдгоипП л пурпе)зезхп л репсгврехопп и й1ападедеаехопп должно быть преобразовано в такую логически эквивалентную форму: вас)гдгоипе) л Реппгхредопз л й1азп1Гдпаеуппп л нуроепепхз Исходя из этой формы представления, для вывода гипотезы нурое)зеэ1в можно использовать процесс, аналогичный обычной делукции Рго1о8 с помощью хорновских выражений, в котором применяется отрицание как не- достижение цели.
Поскольку данный метод ограничивается хорновскими выражениями, он является неполным, но может оказаться более эффективным, чем полная резолюция. Кроме того, при обратном логическом следствии появляется возможность использовать полный логический вывод [717]. 4. Логический вывод может осуществляться с помошью проверки по модели, а не с помощью доказательства теоремы. В системе Ргойо1 11098) для ограничения поиска используется определенная форма проверки по модели. Это означает, что в этой системе, как и в программировании множества ответов, вырабатываются все возможные значения логических переменных, которые затем проверяются на совместимость.
5. Логический вывод может осуществляться с помошью базовых пропозициональных выражений, а не выражений в логике первого порядка. Система Ь)пиз )897) действует по принципу преобразования теорий логики первого порядка в выражения пропозициональной логики, поиска для этих выражений решений с помошью пропозициональной обучающейся системы, а затем 937 Глава 19. Применение знаний в обучении обратного преобразования.
Как было показано на примере алгоритма я)(тр1ап в главе ! 1, при решении некоторых задач может оказаться более эффективной организация работы с помошью пропозициональных формул. Совершение открытий с помощью индуктивного логического программирования Любая процедура обратной резолюции, в которой стратегия полной резолюции действует в противоположном направлении, в принципе представляет собой полный алгоритм изучения теорий первого порядка.
Это означает, что если на основе некоторой неизвестной гипотезы нурс спездв вырабатывается множество примеров, то процедура обратной резолюции может выработать гипотезу ну)зог)зеэзэ из этих примеров. Такое замечание подсказывает любопытную возможность: предположим, что имеющиеся примеры включают данные о разнообразных траекториях падаюших тел.
Существует ли такая теоретическая возможность, что программа обратной резолюции позволит вывести логическим путем закон гравитации? Очевидно, что ответ на этот вопрос является положительным, поскольку именно закон гравитации позволяет объяснять все примеры траекторий при использовании полходяшего вспомогательного математического аппарата. Аналогичным образом, вполне можно представить себе, что в пределах возможностей программ 1ЬР находится открытие законов электромагнитного поля, квантовой механики и теории относительности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
