Главная arrow книги arrow Копия Глава 19. Применение знаний в обучении arrow Поиск на основе оценки наименьшего вклада
Поиск на основе оценки наименьшего вклада

Рекомендуем читателю в качестве упражнения попытаться применить алгоритм Version-Space-Learning к данным о ресторане.

Описанный здесь подход к использованию пространства версий характеризуется описанными ниже принципиальными недостатками.

•    Если проблемная область характеризуются наличием шума или недостаточного количества атрибутов для точной классификации, то пространство версий всегда свертывается.

•    Если в пространстве гипотез допускается наличие неограниченного количества дизъюнкций, то S-множество всегда будет содержать единственную наиболее конкретную гипотезу, а именно дизъюнкцию описаний положительных примеров, встретившихся до сих пор. Аналогичным образом, G-множество будет содержать просто отрицание дизъюнкции описаний отрицательных примеров.

•    Для некоторых пространств гипотез количество элементов в S- или в G-множестве может увеличиваться в экспоненциальной зависимости от количества атрибутов, что не позволяет решить задачу обучения, даже несмотря на то, что для этих пространств гипотез существуют эффективные алгоритмы обучения.

Полностью эффективное решение проблемы шума не найдено до сих пор. Проблемы дизъюнкции можно решить, допуская использование ограниченных форм дизъюнкции или включая иерархию обобщения более общих предикатов. Например, вместо применения дизъюнкции можно ввести в действие единственный литерал LongWai t (x). Для реализации такого подхода можно легко дополнить множество операций обобщения и уточнения.

Рассматриваемый в этом разделе чистый алгоритм сопровождения пространства версий был впервые применен в системе Meta-Dendral, которая была предназначена для изучения правил предсказания того, как молекулы разделяются на фрагменты в массовом спектрометре [202]. Система Meta-Dendral показала свою способность вырабатывать правила, которые оказались достаточно новаторскими, чтобы гарантировать их публикацию в журнале аналитической химии; это были первые реальные научные знания, полученные с помощью компьютерной программы. Такой алгоритм использовался также в изящной системе Lex [1066], которая проявила способность к обучению методам решения задач символического интегрирования, анализируя свои собственные удачи и неудачи. Хотя методы сопровождения пространства версий, по-видимому, не могут найти практического применения в большинстве реальных задач обучения, в основном из-за проблемы шума, они позволяют многое понять в отношении того, какова логическая структура пространства гипотез.