Искусственный интеллект. Современный подход

Поиск на основе оценки наименьшего вклада

Перебор с возвратами возникает из-за того, что в подходе, предусматривающем поиск текущей наилучшей гипотезы, приходится выбирать конкретную гипотезу как наилучшее текущее предположение, даже несмотря на то, что еще отсутствует достаточный объем данных, позволяющий убедиться в правильности этого выбора. Вместо этого можно было бы просто "держать под рукой" те и только те гипотезы, которые являются совместимыми со всеми поступившими до сих пор данными. В таком случае каждый новый экземпляр данных либо не оказывает никакого влияния на состав гипотез, либо позволяет избавиться от некоторых гипотез. Напомним, что первоначальное пространство гипотез может рассматриваться как следующее дизъюнктивное высказывание:
Hi v Н2 v Я3 v ... v Нп
По мере обнаружения того, что различные гипотезы являются несовместимыми с примерами, эта дизъюнкция сужается и остаются только те гипотезы, которые еще не исключены. Это означает, что при условии, что первоначальное пространство гипотез действительно содержит правильный ответ, этот правильный ответ должен также содержаться в сокращенной дизъюнкции, поскольку были удалены только неправильные гипотезы. Множество оставшихся гипотез называется пространством версий, а соответствующий алгоритм обучения (приведенный в листинге 19.2) называется алгоритмом обучения в пространстве версий (а также алгоритмом удаления потенциальных гипотез).
Листинг 19.2. Алгоритм обучения в пространстве версий. Он находит подмножество гипотез V, совместимое с примерами examples
function Version-Space-Learning(examples) returns пространство версий local variables: V, пространство версий - множество всех гипотез
V <— множество всех гипотез
Необходимо, чтобы первоначальное пространство версий (существовавшее до того, как встретились какие-либо примеры) содержало все возможные гипотезы. Для этого достаточно задать G-множество таким образом, чтобы оно содержало гипотезу True (гипотезу, которая включает все возможные случаи), а S-множество — так, чтобы оно содержало гипотезу False (гипотезу, расширение которой пусто).
На рис. 19.2 показана общая структура представления пространства версий с помощью граничных множеств. Для того чтобы показать, что это представление является достаточным, необходимо определить два описанных ниже свойства.
Каждая совместимая гипотеза (отличная от гипотез граничных множеств) является более конкретной, чем некоторый элемент G-множества, и более общей, чем некоторый элемент S-множества (это означает, что за рамками пространства версий не остается ни одной "забытой гипотезы"). Такое свойство следует непосредственно из определений S- и G-множеств. Если бы существовала какая-то не охваченная гипотеза h, то она была бы не более конкретной, чем любой элемент G-множества, поскольку в таком случае она принадлежала бы к G-множеству, и не более общей, любой элемент S-множества, поскольку в таком случае она принадлежала бы к S-множеству.
Любая гипотеза, более конкретная, чем некоторый элемент G-множества, и более общая, чем некоторый элемент S-множества, является совместимой гипотезой. (Это означает, что между границами нет "пустот", в которых находились бы гипотезы, не охваченные отношениями обобщения/уточнения.) Любая гипотеза h, лежащая между S- и G-множествами, должна отвергать все отрицательные примеры, отвергнутые каждым элементом G-множества (поскольку она является более конкретной), и должна принимать все положительные примеры, принятые любым элементом S-множества (поскольку она является более общей). Таким образом, гипотеза h должна согласовываться со всеми примерами и поэтому не может быть несовместимой. Соответствующая ситуация показана на рис. 19.3 — не существует каких-либо известных примеров вне S-множества, но внутри G-множества, поэтому любая гипотеза в промежутке между ними должна быть совместимой.
Таким образом, было показано, что если будет обеспечено правильное сопровождение S- и G-множества в соответствии с их определениями, то эти множества обеспечат удовлетворительное представление пространства версий. Остается единственная проблема — как обновлять S- и G-множество с учетом нового примера (выполнение этой операции возложено на функцию Version-Space-Update). На первый взгляд эта задача может показаться довольно затруднительной, но на основе определений множеств и с помощью рис. 19.2 не слишком сложно составить необходимый для этого алгоритм.
Необходимо прежде всего обеспечить использование элементов Si и d из S- и G-множества соответственно. Применительно к каждому из таких элементов каждый новый экземпляр примера может быть ложно положительным или ложно отрицательным. Возникающие при этом варианты описаны ниже.
1. Ложно положительный пример для s±. Появление такого примера означает, что гипотеза Si является слишком общей, но (по определению) совместимое уточнение для гипотезы Si отсутствует, поэтому ее необходимо исключить из S-множества.
2. Ложно отрицательный пример для S±. Появление такого примера означает, что гипотеза .Si является слишком конкретной, поэтому она заменяется всеми своими непосредственными обобщениями, при соблюдении условия, что они остаются более конкретными, чем любой элемент G-множества.
3. Ложно положительный пример для d. Появление такого примера означает, что гипотеза Gi является слишком общей, поэтому она заменяется всеми своими непосредственными уточнениями, при соблюдении условия, что они остаются более общими, чем любой элемент S-множества.
4. Ложно отрицательный пример для G. Появление такого примера означает, что гипотеза G± является слишком конкретной, но (по определению) совместимое обобщение для гипотезы Gi отсутствует, поэтому ее необходимо исключить из G-множества.
Указанные выше операции продолжаются применительно к каждому новому экземпляру примера до тех пора, пока не произойдет одно из перечисленных ниже событий.
1. В пространстве версий останется одно и только одно определение некоторой концепции, и в этом случае оно будет возвращено как уникальная гипотеза.
2. Пространство версий свернется (либо S-, либо G-множество станет пустым), и это будет означать, что для данного обучающего множества не существуют совместимые гипотезы. Такая ситуация аналогична неудачному завершению поиска, которое возникает в простом варианте алгоритма формирования дерева решений.
3. Примеры закончатся, а в пространстве версий останется несколько гипотез. Это означает, что пространство версий представляет собой дизъюнкцию гипотез. Если при поступлении любого нового примера все дизъюнкты этой дизъюнкции согласуются, то можно возвратить определяемую ими классификацию данного примера. Если же они не согласуются, один из вариантов состоит в использовании мажоритарного голосования.
Рекомендуем читателю в качестве упражнения попытаться применить алгоритм Version-Space-Learning к данным о ресторане.
Описанный здесь подход к использованию пространства версий характеризуется описанными ниже принципиальными недостатками.
• Если проблемная область характеризуются наличием шума или недостаточного количества атрибутов для точной классификации, то пространство версий всегда свертывается.
• Если в пространстве гипотез допускается наличие неограниченного количества дизъюнкций, то S-множество всегда будет содержать единственную наиболее конкретную гипотезу, а именно дизъюнкцию описаний положительных примеров, встретившихся до сих пор. Аналогичным образом, G-множество будет содержать просто отрицание дизъюнкции описаний отрицательных примеров.
• Для некоторых пространств гипотез количество элементов в S- или в G-множестве может увеличиваться в экспоненциальной зависимости от количества атрибутов, что не позволяет решить задачу обучения, даже несмотря на то, что для этих пространств гипотез существуют эффективные алгоритмы обучения.
Полностью эффективное решение проблемы шума не найдено до сих пор. Проблемы дизъюнкции можно решить, допуская использование ограниченных форм дизъюнкции или включая иерархию обобщения более общих предикатов. Например, вместо применения дизъюнкции WaitEstimate(xf 30-60) v WaitEstimate{х,>60) можно ввести в действие единственный литерал LongWai t(x). Для реализации такого подхода можно легко дополнить множество операций обобщения и уточнения.
Рассматриваемый в этом разделе чистый алгоритм сопровождения пространства версий был впервые применен в системе Meta-Dendral, которая была предназначена для изучения правил предсказания того, как молекулы разделяются на фрагменты в массовом спектрометре [202]. Система Meta-Dendral показала свою способность вырабатывать правила, которые оказались достаточно новаторскими, чтобы гарантировать их публикацию в журнале аналитической химии; это были первые реальные научные знания, полученные с помощью компьютерной программы. Такой алгоритм использовался также в изящной системе Lex [1066], которая проявила способность к обучению методам решения задач символического интегрирования, анализируя свои собственные удачи и неудачи. Хотя методы сопровождения пространства версий, по-видимому, не могут найти практического применения в большинстве реальных задач обучения, в основном из-за проблемы шума, они позволяют многое понять в отношении того, какова логическая структура пространства гипотез.