ИНДУКТИВНОЕ ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
В индуктивном логическом программировании (Inductive Logic Programming — ILP) объединяются индуктивные методы с мощными представлениями в логике первого порядка, и оно в основном сосредоточивается на представлении теорий в виде логических программ4. Это научное направление получило широкую известность по трем причинам. Во-первых, индуктивное логическое программирование лежит в основе строгого подхода к решению общих задач индуктивного обучения на основе базы знаний. Во-вторых, в рамках этого направления созданы полные алгоритмы логического вывода общих теорий в логике первого порядка с использованием примеров; это означает, что данные алгоритмы могут успешно применяться для обучения в тех проблемных областях, в которых использование алгоритмов на основе атрибутов связано с определенными затруднениями. В качестве соответствующего примера можно привести применение методов ILP в изучении того, как сворачиваются белковые структуры (рис. 19.7). Трехмерную конфигурацию молекулы белка невозможно представить с помощью какого-либо приемлемого способа в виде множества атрибутов, поскольку конфигурация молекулы неявно обусловлена связями между объектами, а не атрибутами отдельного объекта. Одним из языков, подходящих для описания таких связей, является логика первого порядка. В-третьих, с помощью методов индуктивного логического программирования могут вырабатываться гипотезы, которые являются (относительно) простыми для восприятия людьми. Например, перевод на естественный язык правила, приведенного в подписи к рис. 19.7, может уточняться и подвергаться критике биологами, которые работают в данной области. Это означает, что системы индуктивного логического программирования могут участвовать в научном цикле экспериментирования, выработки гипотез, обсуждения и опровержения. Такое участие невозможно при использовании таких систем, которые вырабатывают классификаторы в виде "черных ящиков", например нейронных сетей.
Правило такого рода невозможно выработать путем обучения или даже представить с помощью любых механизмов, основанных на атрибутах, наподобие тех, которые рассматривались в предыдущих главах. Это правило можно перевести на естественный язык, как показано ниже.
Белок Р относится к классу методов сворачивания "связка из четырех восходящих и нисходящих спиралей", если он включает длинную спираль hi во второй структурной позиции между позициями 1 и 3 и если спираль hi находится рядом со второй спиралью
Практический пример
Как было указано выше, из уравнения 19.5 следует, что общая задача индукции на основе знаний состоит в "решении" ограничения логического следствия для неизвестной гипотезы Hypothesis, если даны фоновые знания Background и примеры, представленные с помощью описаний Descriptions и классификаций Classifications'.
Background л Hypothesis л Descriptions N Classifications
ДЛЯ иллюстрации этого процесса рассмотрим задачу изучения семейных связей на примерах. Описания будут состоять из развернутого генеалогического дерева, описанного в терминах отношений Mother (Мать), Father (Отец) и Married (Состоит в браке), а также свойств Male (Мужчина) и Female (Женщина). В качестве примера будет использоваться генеалогическое дерево, рассматриваемое в упр. 8.11, которое показано на рис. 19.8. Соответствующие описания приведены ниже.
Высказывания, входящие в состав классификаций Classifications, зависят от изучаемого целевого понятия. Например, может потребоваться изучить понятия Grandparent (Дедушка или бабушка), BrotherlnLaw (Двоюродный брат) или Ancestor (Предок). Что касается понятия Grandparent, то полное множество Classifications содержит 2 0x20 = 400 конъюнктов в следующей форме:
Grandparent {Mum, Charles) Grandparent{Elizabeth,Beatrice)
—Grandparent {Mum, Harry) -Grandparent (Spencer, Peter)
Безусловно, обучение может быть проведено на основе какого-то подмножества этого полного множества.
Задачей применения любой программы индуктивного обучения является выработка множества высказываний, соответствующих гипотезе Hypothesis, такого, что в нем выполняется заданное ограничение логического следствия. На данный момент предположим, что у агента отсутствуют фоновые знания: отношение Background является пустым. В таком случае одно из возможных решений для Hypothesis состоит в следующем:
Grandparent {х, у) <=> [3z Mother(x,z) л Mother{z,y)]
v [3z Mother{x,z) л Father{z,y) ]
v [3z Father(x,z) л Mother(z,y)]
v [3z Father(x, z) л Father(z,y) ]
Следует отметить, что алгоритм обучения на основе атрибутов, такой как Dec is ion-Tree-Learning, в попытке решить эту задачу бесконечно углубится в дерево, но не достигнет успеха. Для того чтобы выразить отношение Grandparent в виде атрибута (т.е. унарного предиката), необходимо будет преобразовывать пары людей в объекты:
Grandparen t ((Mum, Charl es)) ...
Затем мы окажемся в тупике, пытаясь представить описания примеров. Единственно возможными атрибутами станут такие ужасно неуклюжие конструкции, как следующая:
FirstElementlsMotherOfElizabeth {(Mum, Charles))
Определением отношения Grandparent в терминах этих атрибутов становится большая дизъюнкция описаний конкретных случаев, которая вообще не может быть обобщена с учетом новых примеров. Алгоритмы обучения на основе атрибутов не способны обеспечить изучение реляционных предикатов. Таким образом, одним из принципиальных преимуществ алгоритмов ILP является их применимость для решения гораздо более широкого диапазона задач, включая реляционные задачи.
Читатель должен был, безусловно, заметить, что для представления определения Grandparent мог бы помочь небольшой фрагмент фоновых знаний. Например, если в состав фоновых знаний Background входит следующее высказывание:
Parent(x,y) <=> [Mother(х,у) v Father(x,y) ]
то определение отношения Grandparent можно свести к следующему:
Grandparent {х, у) <=> [3z Parent{x,z) л Paren t (z, у) ]
Этот пример показывает, насколько существенно фоновые знания позволяют сократить размер гипотез, требуемых для объяснения результатов наблюдений.
Алгоритмы ILP позволяют также создавать новые предикаты для упрощения способов выражения объяснительных гипотез. Применительно к примеру данных, приведенному выше, было бы вполне резонно, чтобы программа ILP предложила дополнительный предикат, который можно было бы назвать "Parent" (Родитель), для упрощения определений целевых предикатов. Алгоритмы, которые способны вырабатывать новые предикаты, называются алгоритмами конструктивной индукции. Очевидно, что конструктивная индукция является необходимой частью подхода к обучению на основе накопления знаний, который был кратко описан во введении. Задача накопления знаний всегда была одной из сложнейших задач машинного обучения, но некоторые методы ILP предоставляют эффективные механизмы ее решения.
В оставшейся части данной главы исследуются два принципиальных подхода к индуктивному логическому программированию. В первом из них используется обобщение методов на основе деревьев решений, а во втором используются методы, основанные на инвертировании доказательства с помощью резолюции.