Сопоставление экземпляров с образцами в Meta-DENDRAL
Для описания экземпляров обучающей выборки в Meta-DENDRAL используется тот же язык, что и для описания образцов. Каждый образец представляет собой описание определенной цельной молекулы, причем основное внимание уделяется описанию компонентов.
При сопоставлении экземпляров с образцами отыскивается цепочка связных отображений узлов образца и узлов экземпляра. Отображение X является связным, если оно является однозначным и допускающим вставку и если каждая пара узлов экземпляра Х(р1), Х(р2), соответствующая узлам образца р1 и р2, разделяет общую связь в том и только в том случае, если р1 и р2 также разделяют общую связь. Требуется также, чтобы значения характеристик каждого узла экземпляра Х(р) удовлетворяли ограничениям, определенным для соответствующего узла p образца.
Теперь открывается возможность дать определение частичного упорядочения по Митчеллу, специфичное для той предметной области, в которой используется система Meta-DENDRAL. В этом определении будет использовано и приведенное выше определение связности. Строчными буквами будем обозначать узлы образца, а прописными — весь образец в целом. Образец Р1 является более специфическим или равным образцу Р2 в том и только в том случае, когда существует такое связанное отображение X узлов в Р2 на узлы в Р1, что для каждой пары узлов р2, Х(р2) ограничения на значения свойств, ассоциированные с Х(р2), являются более специфическими или равными ограничениям, ассоциированным с р2. Для того чтобы разобраться в существе этого определения, имеет смысл вновь вернуться к примеру из мира блоков, который мы рассматривали выше. В мире химических структур аналогами блоков являются атомы и "суператомы", а аналогами пространственных отношений между блоками, такими как "поддерживает" или "касается", — химические связи.
Специфические знания из области химии могут быть двояко использованы алгоритмом отсеивания кандидатов.
(1)Язык представления химических структур допускает такие языковые формы представления образцов, которые синтаксически отличны, но семантически эквивалентны, т.е.
на этом языке один и тот же образец можно описать разными выражениями. Следовательно, для удаления избыточных образцов из граничных пространств версий требуется знание семантики образца, представленного в описании. Это не оказывает никакого влияния на полноту подхода, основанного на пространстве версий.
(2) Для некоторых проблем граничные пространства версий могут вырасти и достичь достаточно большого объема. Следовательно, было бы очень полезно использовать какие-либо правила для сокращения объемов граничных пространств. Однако, если использовать для этого эвристические методы, нет уверенности, что программа сможет определить все описания концептов, совместимые с обучающей выборкой.
Митчелл утверждает, что подход, основанный на пространстве версий, добавит новые возможности первоначальному варианту программы Meta-DENDRAL.
Суммируя все сказанное выше, приходим к выводу, что использование подхода, основанного на пространствах версий, позволяет реализовать методику инкрементального обучения (обучения с последовательным наращиванием уровня полноты знаний). Стратегия отсеивания кандидатов может быть противопоставлена стратегии поиска в глубину или в ширину, поскольку она позволяет отыскать не единственное приемлемое описание концепта, как при выполнении поиска в глубину, или максимально специфические описания, как при поиске в ширину, а все описания концептов, совместимые с обучающей выборкой.Митчелл также специально акцентирует внимание на том, что ключевым вопросом применения такой технологии является разработка методов формирования обучающей выборки.
