Алгоритм отсеивания кандидатов

20.2.3. Алгоритм отсеивания кандидатов

Пространство версий, как следует из приведенного описания, есть не что иное, как структура данных для представления множества описаний концептов. Однако термин "пространство версий" часто применяется и по отношению к технологии обучения, использующей при работе с этой структурой данных алгоритм, известный как алгоритм отсеивания кандидатов (candidate elimination). Этот алгоритм манипулирует с граничными множествами, представляющими определенное пространство версий.

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

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

В этом алгоритме нет никакой эвристики, поскольку ограничения четкие и тем самым гарантируется сходимость алгоритма. Монотонность поиска оказалась тем "золотым ключиком", с помощью которого удалось решить проблему комбинаторики обновления пространств.

Технология пространства версий обладает множеством привлекательных свойств, которые стоят того, чтобы их здесь перечислить.

Гарантируется совместимость всех описаний концептов со всеми экземплярами в обучающей выборке.
Пространство поиска суммирует альтернативные интерпретации наблюдений.
Результат не зависит от порядка обработки обучающей выборки.
Каждый экземпляр в обучающей выборке анализируется только один раз.
Не возникает необходимость возвращаться к однажды отвергнутой гипотезе.

Тот факт, что пространство версий суммирует данные, означает, что его можно использовать в качестве базиса для формирования новых экземпляров для обучающей выборки, т.е. экземпляров, которые могли бы еще более сблизить границы. То, что программа анализирует каждый экземпляр только один раз, позволяет обойтись без сохранения ранее обработанных экземпляров. Следовательно, и время обучения пропорционально объему обучающей выборки, а не связано с количеством экземпляров в ней какой-либо показательной функцией. Поскольку отпадает необходимость в обратном прослеживании, эффективность процедуры должна быть довольно высокой. Наиболее серьезным "подводным камнем" в этой технологии является фактор ветвления в процессе частичного упорядочения образцов, который имеет тенденцию к комбинаторному росту по мере увеличения количества дизъюнктов в описаниях концептов.