Повышение эффективности правила
Обобщенное дерево доказательства, показанное на рис. 19.5, фактически приводит к получению больше чем одного обобщенного правила. Например, если будет прекращено наращивание правой ветви в дереве доказательства после того, как одна ветвь достигнет этапа Primitive, т.е. если будет выполнено отсечение этой ветви, то получим следующее правило:
Primitive (z) => Simplify (lx (0 + z) , z)
Это правило является таким же действительным, как и правило, в котором используется предикат ArithmeticUnknown, но более общим, поскольку оно охватывает также случаи, в которых z является числом. Из дерева доказательства можно извлечь еще более общее правило, выполняя отсечение ветви после этапа Simplify(y+z, w), что приводит к получению такого правила:
Simpli fy{y+z, w) => Simplify(lx(y+z),w)
Вообще говоря, из любого частичного поддерева обобщенного дерева доказательства можно извлечь какое-то правило. Это означает, что имеет место еще одна проблема: какое из этих правил следует выбрать?
Выбор правила, подлежащего выработке, сводится к решению вопроса об эффективности выбранного правила. Ниже описаны три фактора, которые касаются анализа прироста эффективности, достигнутого в результате обучения на основе объяснения.
1. Введение большого количества правил влечет за собой замедление процесса формирования рассуждений, поскольку механизм логического вывода так или иначе должен проверять эти правила, даже в тех случаях, когда они не приводят к решению. Иными словами, увеличение количества правил приводит к увеличению коэффициента ветвления в пространстве поиска.
2. Для того чтобы компенсировать замедление процесса формирования рассуждений, производные правила должны обеспечивать существенное увеличение скорости для тех случаев, которые они охватывают. Такое увеличение достигается в основном благодаря тому, что производные правила позволяют избегать тупиков, которые могли бы возникнуть без их использования, а также в связи с тем, что они сокращают само доказательство.
3. Производные правила должны быть как можно более общими, для того чтобы они применялись к максимально возможному множеству случаев.
Общепринятый подход к обеспечению эффективности таких производных правил состоит в том, чтобы следить за соблюдением требования, касающегося операционной пригодности каждой подцели в правиле. Подцель является операци-онно пригодной, если ее можно достаточно "легко" решить. Например, подцель
Primi tive(z) решить легко, и для этого требуется самое большее два этапа вывода, а для достижения подцели Simplify (y+z, w) может потребоваться произвольный объем логического вывода в зависимости от значений у и z. Если проверка на операционную пригодность выполняется на каждом этапе формирования обобщенного доказательства, то появляется возможность отсечь оставшуюся ветвь, как только будет найдена операционно пригодная подцель, и оставить в качестве конъюнкта нового правила лишь эту операционно пригодную подцель.
К сожалению, обычно приходится искать компромисс между операционной пригодностью и общностью. Для более конкретных подцелей обычно бывает проще найти решение, но они охватывают меньше случаев. Кроме того, сам критерий операционной пригодности в определенной степени субъективен: можно уверенно сказать, что подцель, для достижения которой требуется один или два этапа, является операционно пригодной, но можно ли это утверждать, если количество этапов приближается к 10 или 100? Наконец, стоимость поиска решения для данной конкретной подцели зависит от того, какие еще правила имеются в базе знаний. По мере введения дополнительных правил эта стоимость может и увеличиваться, и уменьшаться. Таким образом, при эксплуатации систем EBL фактически приходится сталкиваться с очень сложными проблемами оптимизации, пытаясь добиться максимальной эффективности заданной начальной базы знаний. Иногда существует возможность вывести математическую модель влияния операции добавления какого-то конкретного правила на общую эффективность и использовать эту модель для определения наилучшего правила, подлежащего добавлению. Но такой анализ может стать очень сложным, особенно когда приходится сталкиваться с рекурсивными правилами. Один из перспективных подходов состоит в эмпирическом решении проблемы эффективности путем добавления нескольких правил и определения того, какое из них является полезным и действительно позволяет ускорить работу.
Эмпирический анализ эффективности фактически становится основой системы EBL. То, что в предыдущем абзаце неформально было названо "эффективностью заданной базы знаний", в действительности представляет собой усредненную по рассматриваемым случаям сложность решения задач, предъявляемых системе и описываемых некоторым распределением вероятностей. Система EBL позволяет проводить обобщение по результатам решения примеров задач, встретившихся в прошлом, поэтому способствует повышению эффективности базы знаний применительно к тем типам задач, которые, скорее всего, должны встретиться в будущем. Такая организация работы способствует достижению успеха, при условии, что распределение вероятностей прошлых примеров приблизительно соответствует распределению вероятностей будущих примеров; это — такое же предположение, которое лежало в основе метода РАС-обучения, описанного в разделе 18.5. Если проведено тщательное и продуманное проектирование системы EBL, то появляется возможность достичь существенного ускорения работы. Например, очень крупная система обработки естественного языка на основе Prolog, предназначенная для прямого и обратного перевода речи со шведского на английский, позволила добиться приемлемой производительности работы в реальном времени только благодаря применению системы EBL в процессе синтаксического анализа [1351].
ОБУЧЕНИЕ С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИИ О РЕЛЕВАНТНОСТИ
Путешественник, приехавший в Бразилию, о котором говорилось раньше, по-видимому, сумел прийти к достоверному обобщению, касающемуся языка, на котором говорят остальные бразильцы. Полученный этим путешественником логический вывод был основан на его фоновых знаниях, а именно на знаниях о том, что население данной конкретной страны (обычно) говорит на одном и тот же языке. Это утверждение можно выразить в логике первого порядка следующим образом3:
Nationality {х,п) л Nationality(у, п) л Languageix,1) =>
Language(у,1) (19.6)
Это высказывание буквально означает: "Если хиу имеют одинаковое гражданство лих говорит на языке 1, то у также говорит на этом языке". Нетрудно показать, что на основании этого высказывания и следующего наблюдения:
Nationality{Fernando,Brazil) л Language(Fernando,Portuguese)
можно прийти к такому заключению (см. упр. 19.1):
Nationality{х,Brazil) => Language(х,Portuguese)
Высказывания, подобные приведенному в уравнении 19.6, выражают строгую форму релевантности: если известно гражданство человека, то полностью определен язык, на котором он говорит (эту мысль можно выразить иначе — язык определяется функциональной зависимостью от гражданства). Такие высказывания называются функциональными зависимостями, или определениями, и встречаются настолько часто в приложениях определенных типов (например, в спецификациях проектов баз данных), что для их записи используется специальный синтаксис. В этой главе мы будем придерживаться системы обозначений, предложенной Дэвисом [329]:
Nationality(х,п) У Language(х, 1)
Как обычно, это обозначение представляет собой синтаксическое упрощение, но оно подчеркивает тот факт, что определение в действительности показывает связь между предикатами; в данном случае гражданство определяет язык. Аналогичным образом могут быть представлены релевантные свойства, определяющие проводимость и плотность:
Material (х, т) л Temperature (х, t) >- Conductance (х, р) Material(х,т) л Temperature(х,t) У Density{x,d)
Соответствующие обобщения следуют логически из определений и наблюдений.