Индуктивное обучение с помощью обратной дедукции
Второй важный подход к индуктивному логическому программированию предусматривает обращение обычного процесса дедуктивного доказательства. Метод обратной резолюции основан на том наблюдении, что если классификация Classifications примера следует из выражения Backgrouncb\HypothesisADescriptions, то должна существовать возможность доказать этот факт с помощью метода резолюции (поскольку метод резолюции является полным). А если есть возможность "провести доказательство в обратном направлении", то можно найти такую гипотезу Hypothesis, через которую проходит это доказательство. Поэтому задача состоит в том, чтобы найти способ обращения процесса резолюции.
В этом разделе будет показан процесс обратного доказательства для инверсного правила резолюции, который состоит из отдельных обратных этапов. Напомним, что в обычном этапе резолюции берутся два выражения, С1 и С2, и к ним применяется операция уничтожения взаимно противоположных литералов (операция резолюции) для получения резольвенты С. С другой стороны, на этапе инверсной резолюции берется резольвента С и формируются два выражения, Сг и С2, такие, что С является результатом применения операции уничтожения взаимно противоположных литералов в выражениях Сг и С2. Еще один вариант состоит в том, что можно взять резольвенту С и выражение Ci и сформировать выражение С2, такое, что С является результатом применения операции резолюции к Сг и С2.
Начальные этапы процесса обратной резолюции показаны на рис. 19.9; на этих этапах вся работа сосредоточивается на положительном примере Grandparent
{George, Anne). Процесс начинается с конца доказательства (который обозначен квадратом в нижней части рисунка). Предполагается, что резольвента С представляет собой пустое выражение (т.е. противоречие), а в качестве С2 берется выражение -Grandparent (George, Anne), которое является отрицанием целевого примера. В первом обратном этапе используются выражения С и С2 и формируется выражение Grandparent (George, Anne), соответствующее Сг. На следующем этапе это выражение берется в качестве С, выражение Parent (Elizabeth, Аппе) используется в качестве С2, а в качестве сг формируется следующее выражение:
-Parent (Elizabeth,у) v Grandparent (George,у)
На последнем этапе данное выражение рассматривается как резольвента. Если в качестве С2 берется выражение Parent (George, Elizabeth), то одним из возможных выражений d становится гипотеза:
Parent (х, z) л Parent (z, у) => Garent (х, у)
Теперь в нашем распоряжении имеется доказательство с помощью резолюции, что из данной гипотезы, описаний и фоновых знаний следует классификация
Grandparent(George,Anne).
Очевидно, что в процессе обратной резолюции требуется поиск. Каждый этап обратной резолюции является недетерминированным, поскольку для любого выражения С может существовать большое или даже бесконечное количество выражений Сг и С2, которые в результате операции резолюции преобразуются в с. Например, вместо применения выражения —iParen t(Eli zabe th, у) vGrandparen t (George, у) в качестве Сг на последнем этапе, показанном на рис. 19.9, на этом этапе обратной резолюции можно было выбрать любое из следующих высказываний (см. упр. 19.4 и 19.5):
-Parent(Elizabeth,Anne) v Grandparent(George,Anne) -Parent (z, Anne) v Grandparent (George, Anne) —lParent(z,y) v Grandparent (George,y)
Более того, выражения, которые участвуют на каждом этапе, могут быть выбраны из фоновых знаний Background, из описаний примеров Descriptions, из отрицаемых выражений в множестве Classifications или из выражений, выдвинутых в качестве гипотезы, которые уже были сформированы в дереве обратной резолюции. Такое большое количество возможностей означает, что без дополнительного управления возникает большой коэффициент ветвления (и поэтому поиск становится неэффективным). В реализованных на практике системах ILP был опробован целый ряд подходов к управлению поиском, в том числе подходы, описанные ниже.
1. Могут быть удалены избыточные варианты выбора, например, путем формирования только наиболее конкретных гипотез из всех возможных и соблюдения требования о том, чтобы все выражения, принятые в качестве гипотез, были совместимыми и друг с другом, и с результатами наблюдений. Применение последнего критерия позволило бы исключить выражение ?Parent (z,y) vGrandparent (George, у), приведенное выше.
2. Могут быть наложены ограничения на стратегию доказательства. Например, в главе 9 было показано, что линейная резолюция — это полная, ограниченная стратегия, которая позволяет создавать только такие деревья доказательства, которые имеют линейную структуру ветвления (как на рис. 19.9).
3. Могут быть наложены ограничения на язык представления, например, путем устранения функциональных символов или применения только хорновских выражений. Например, язык Progol оперирует с хорновскими выражениями с использованием обратного логического следствия. Идея этого метода состоит в том, что ограничение логического следствия:
Background л Hypothesis л Descriptions t= Classifications
должно быть преобразовано в такую логически эквивалентную форму:
Background л Descriptions л -Classifications t= -Hypothesis
Исходя из этой формы представления, для вывода гипотезы Hypothesis можно использовать процесс, аналогичный обычной дедукции Prolog с помощью хорновских выражений, в котором применяется отрицание как недостижение цели. Поскольку данный метод ограничивается хорновскими выражениями, он является неполным, но может оказаться более эффективным, чем полная резолюция. Кроме того, при обратном логическом следствии появляется возможность использовать полный логический вывод [717].
4. Логический вывод может осуществляться с помощью проверки по модели, а не с помощью доказательства теоремы. В системе Progol [1098] для ограничения поиска используется определенная форма проверки по модели. Это означает, что в этой системе, как и в программировании множества ответов, вырабатываются все возможные значения логических переменных, которые затем проверяются на совместимость.
5. Логический вывод может осуществляться с помощью базовых пропозициональных выражений, а не выражений в логике первого порядка. Система Linus [897] действует по принципу преобразования теорий логики первого порядка в выражения пропозициональной логики, поиска для этих выражений решений с помощью пропозициональной обучающейся системы, а затем обратного преобразования. Как было показано на примере алгоритма SATplan в главе 11, при решении некоторых задач может оказаться более эффективной организация работы с помощью пропозициональных формул.
Совершение открытий с помощью индуктивного логического программирования
Любая процедура обратной резолюции, в которой стратегия полной резолюции действует в противоположном направлении, в принципе представляет собой полный алгоритм изучения теорий первого порядка. Это означает, что если на основе некоторой неизвестной гипотезы Hypothesis вырабатывается множество примеров, то процедура обратной резолюции может выработать гипотезу Hypothesis из этих примеров. Такое замечание подсказывает любопытную возможность: предположим, что имеющиеся примеры включают данные о разнообразных траекториях падающих тел. Существует ли такая теоретическая возможность, что программа обратной резолюции позволит вывести логическим путем закон гравитации? Очевидно, что ответ на этот вопрос является положительным, поскольку именно закон гравитации позволяет объяснять все примеры траекторий при использовании подходящего вспомогательного математического аппарата. Аналогичным образом, вполне можно представить себе, что в пределах возможностей программ ILP находится открытие законов электромагнитного поля, квантовой механики и теории относительности. Разумеется, открытие этих законов находится и в пределах возможностей такой экспериментальной установки, в которой обезьяну посадили за пишущую машинку; нужны лишь более качественные эвристики и новые способы структуризации пространства поиска.
Но не углубляясь в эти крайности, можно отметить, что системы обратной резолюции действительно позволяют совершать небольшие, но важные открытия — создавать новые предикаты. Такую их способность часто рассматривают как нечто магическое, поскольку компьютеры принято считать устройствами, "просто работающими с тем, что им задано". Но в действительности новые предикаты непосредственно следуют из этапов обратной резолюции. Простейшим случаем создания таких предикатов является преобразование в гипотезы двух новых выражений d и С2 на основе выражения С. Применение операции резолюции к выражениям d и С2 приводит к удалению в этих двух выражениях общего литерала, поэтому вполне возможно, что удаленный литерал содержал предикат, который не присутствовал в С. Таким образом, при проведении доказательства в обратном направлении одна из возможностей состоит в формировании нового предиката, из которого реконструируется недостающий литерал.
На рис. 19.10 показан пример, в котором новый предикат Р формируется в процессе изучения определения для отношения Ancestor. После его формирования предикат Р может использоваться на дальнейших этапах обратной резолюции. Например, на одном из дальнейших этапов может быть выдвинута гипотеза, что Mother (х,у) =>Р(х,у). Таким образом, новый предикат Р имеет смысл, определяемый процессом выработки гипотез, в которых он участвует. А обработка еще одного примера может привести к созданию ограничения Father (х, у) =>Р(х, у). Иными словами, предикат Р представляет собой описание того, что обычно рассматривается как отношение Parent. Как было указано выше, введение новых предикатов позволяет существенно уменьшить размер определения целевого предиката. Это означает, что системы обратной резолюции часто позволяют решать задачи обучения, неразрешимые с помощью других методов, поскольку предоставляют возможность изобретать новые предикаты.
Некоторые из самых радикальных революций в науке стали следствием изобретения новых предикатов и функций; в качестве примера можно привести открытие Галилеем принципа ускорения или уточнение Джоулем понятия тепловой энергии. Как только в распоряжении ученых оказываются эти новые определения, открытие новых законов становится относительно простым. При этом труднее всего понять, что какая-то новая сущность, имеющая конкретную связь с уже известными сущностями, позволяет объяснить целый класс результатов наблюдений с помощью гораздо более простой и изящной теории по сравнению с теми теориями, которые применялись раньше.
До сих пор с помощью систем ILP еще не были сделаны открытия на уровне Галилея или Джоуля, но даже небольшие открытия, сделанные с их помощью, оказались достойными публикации в научной литературе. Например, в Journal of Molecular Biology были описаны результаты автоматизированного открытия правил сворачивания белка с помощью программы Progol, действующей по принципу индуктивного логического программирования [1517]. Многие правила, открытые программой Progol, и раньше можно было вывести из известных принципов, но большинство из них еще не было до сих пор опубликовано в составе какой-либо стандартной биологической базы данных (один из примеров такого правила приведен на рис. 19.7). В одной из работ, относящихся к близкой теме, рассматривалась проблема открытия правил определения мутагенной способности нитроароматических веществ, обусловленной их молекулярной структурой [1454]. Такие вещества были обнаружены в выхлопных газах автомобилей. Для 80% этих веществ, данные о которых содержались в стандартной базе данных, удалось выявить четыре важные характеристики, причем применение метода линейной регрессии для анализа данных характеристик показало, что этот метод превышает по своей производительности метод ILP. А для оставшихся 20% веществ такие характеристики, отдельно взятые, не позволяют получить надежный прогноз, но система ILP выявила отношения, которые позволили ей превзойти по производительности системы с линейной регрессией, нейронными сетями и деревьями решений. В [798] показано, как обеспечить прогнозирование терапевтической эффективности различных лекарств, исходя из их молекулярной структуры. Анализ этих практических примеров позволяет прийти к выводу, что достижению высокой производительности систем ILP способствует то, что они позволяют представлять новые отношения и использовать фоновые знания. Тот факт, что правила, найденные системами ILP, могут интерпретироваться людьми, стал причиной того, что эти методы были взяты на вооружение не только специалистами в области компьютерных наук, но и биологами.
Применение методов ILP способствует развитию не только биологии, но и других наук. Одним из наиболее важных таких направлений является обработка естественного языка, в котором системы ILP используются для извлечения сложной реляционной информации из текста. Итоговые результаты, достигнутые в этом научном направлении, описаны в главе 23.
В данной главе рассматривались различные способы, при использовании которых априорные знания могут помочь агенту обучаться на основе новых опытных данных. Поскольку основная часть априорных знаний выражена в терминах реляционных моделей, а не моделей, основанных на атрибутах, в настоящей главе описаны также системы, которые позволяют изучать реляционные модели. Наиболее важные идеи, изложенные в этой главе, перечислены ниже.
• Успешное применение априорных знаний в обучении показывает, что еще более перспективным является кумулятивное обучение, в котором обучающиеся агенты повышают свою способность к обучению по мере того, как приобретают все больше и больше знаний.
• Априорные знания способствуют обучению, поскольку позволяют устранять ошибочные гипотезы, которые в ином случае считались бы совместимыми, а также "дополнять" объяснения примерами, что приводит к созданию более коротких гипотез. Такие возможности часто позволяют добиться ускоренного обучения с помощью меньшего количества примеров.
• Априорные знания могут выполнять различные функции в логическом выводе, а описания этих функций, выраженные в форме ограничений логического следствия, позволяют определить целый ряд разнообразных методов обучения.
• В методе обучения на основе объяснения (Explanation-Based Learning — EBL) предусматривается извлечение общих правил из отдельных примеров путем формирования объяснений для этих примеров и обобщения объяснений. Метод EBL представляет собой дедуктивный метод, с помощью которого знания основных принципов преобразуются в полезные, эффективные экспертные знания специального назначения.
• В методе обучения с учетом релевантности (Relevance-Based Learning — RBL) используются априорные знания в форме определений для выявления релевантных атрибутов, что приводит к созданию уменьшенного пространства гипотез и ускорению обучения. Метод RBL обеспечивает также создание дедуктивных обобщений на основе отдельных примеров.
• В методе индуктивного обучения на основе знаний (Knowledge-Based Inductive Learning — KBIL) предусматривается поиск индуктивных гипотез, позволяющих объяснять множества результатов наблюдений с помощью фоновых знаний.
• В методах индуктивного логического программирования (Inductive Logic Programming — ILP) метод KBIL применяется к знаниям, выраженным в логике первого порядка. Методы ILP позволяют получать в процессе обучения такие реляционные знания, которое не могут быть выражены в системах на основе атрибутов.
• Индуктивное логическое программирование может осуществляться в рамках нисходящего подхода, в котором осуществляется уточнение очень общего правила, или восходящего подхода, обратного по отношению к процессу дедуктивного логического вывода.
• С помощью методов ILP естественным путем вырабатываются новые предикаты, с помощью которых могут быть выражены новые емкие теории, поэтому они открывают возможность создания систем формирования научных теорий общего назначения.