Дедуктивный классификатор
Дедукти́вный классифика́тор — это разновидность инференс-машины (выводящей системы) в области искусственного интеллекта. Входными данными для классификатора служит набор утверждений, сформулированных на фреймовом языке о некоторой предметной области, например медицинских исследованиях или молекулярной биологии. К примеру, это могут быть названия классов, подклассов, свойства и ограничения допустимых значений. Классификатор определяет, согласуются ли сделанные утверждения между собой с логической точки зрения; в случае противоречий он указывает на конкретные неконсистентные утверждения и характер их несогласованности. Если утверждения непротиворечивы, классификатор может сделать дополнительные выводы исходя из поступившей информации — например, добавить сведения о существующих классах, создать дополнительные классы и пр. В отличие от традиционных выводящих систем, основанных на правилах «ЕСЛИ-ТО», классификатор работает с описательными декларациями. Классификаторы схожи с доказателями теорем, поскольку используют логику первого порядка для входа и вывода. Первые классификаторы появились в рамках фреймовых языков семейства KL-ONE. Они приобретают всё большее значение как составная часть технологий семантической паутины. Современные классификаторы активно используют Web Ontology Language (OWL). Модели, которые анализируются и строятся с их помощью, называются онтологиями[1].
История
Классической проблемой представления знаний в искусственном интеллекте является компромисс между выразительной мощностью и вычислительной эффективностью системы представления знаний. Наиболее мощной формой представления знаний выступает логика первого порядка; однако невозможно реализовать такую систему, которая обеспечивала бы всю выразительную мощь логики первого порядка — например, возможность описать множество всех целых чисел, перебор которого невозможен. Попытки реализовать утверждения, параметризованные по бесконечным множествам, по определению приводят к неразрешимости задачи или бесконечной работе программы. Как показал Гектор Левеск, чем ближе механизм представления знаний к логике первого порядка, тем больше вероятность возникновения утверждений, требующих для обработки бесконечных или неприемлемо больших вычислительных ресурсов[2].
В результате большого числа подобных компромиссов значительная часть ранних исследований в области представления знаний была посвящена поиску подходящих подмножеств логики первого порядка, дающих приемлемую скорость вычислений. Одним из первых и наиболее успешных компромиссных решений стало развитие языков, преимущественно основанных на modus ponens — то есть на правилах типа «ЕСЛИ-ТО». Экспертные системы, использующие такие правила вывода, составляли основу первых систем искусственного интеллекта и обеспечивали хорошую производительность при достаточно универсальном представлении знаний. Кроме того, такой подход был близок интуитивному пониманию предметно-ориентированных специалистов: психологические исследования показывали, что люди зачастую склонны структурировать знания в виде правил[3].
Со временем, однако, наряду с правилами всё более широкое применение находили фреймовые языки, либо правила и фреймы стали использоваться совместно. Фреймы позволяли более естественно описывать определённые типы понятий, особенно связанные с иерархией подклассов или частей. Это стимулировало разработку нового типа выводящей системы — классификатора. Классификатор мог анализировать иерархию классов (иначе — онтологию) и проверять её согласованность; при наличии противоречий он указывал несогласованные элементы. Для того чтобы язык мог использовать классификатор, требовалась строгая формальная база. Первой категорией языков, успешно реализовавших классификатор, было семейство KL-ONE. Позднее язык Loom, разработанный в Институте информационных наук (ISI), был во многом основан на KL-ONE и ориентирован на растущую популярность объектно-ориентированных инструментов: Loom поддерживал полноценную объектную модель (например, передачу сообщений) наряду с фреймовыми возможностями. Классификаторы играют значимую роль в развитии концепции семантической паутины: язык онтологий Web (OWL) позволяет строить формальные модели, валидируемые классификаторами, такие как Hermit и Fact++[4].
Внедрения
Первые версии классификаторов представляли собой системы автоматического доказательства теорем. Первый классификатор, работавший с фреймовым языком, был создан для фреймового языка KL-ONE[5][6]. Позднее в среде Common Lisp была разработана система LOOM Института информационных наук, которая предоставляла расширенные объектно-ориентированные возможности на основе Common Lisp Object System в сочетании с фреймовым языком[7]. В семантической паутине инструмент Protege, разработанный в Стэнфордском университете, содержит классификаторы как часть стандартной среды[8].