Представление знаний

Самые ранние работы по компьютерному представлению знаний были связаны с созданием общих решателей задач, таких как General Problem Solver (GPS), разработанный Алленом Ньюэллом и Гербертом Саймоном в 1959 году, а также системой Advice Taker, предложенной Джоном Маккарти в том же году. GPS предлагал структуры данных для планирования и декомпозиции задач: он начинал с общей цели, разбивал её на подцели и строил стратегию для их достижения. Advice Taker, напротив, предполагал использование исчисления предикатов для реализации разумных рассуждений.

Многие ранние подходы к представлению знаний использовали графовые структуры — семантические сети, аналогии графов знаний. В этих подходах решение задач сводилось к поиску пути в графе^[5], например, как в алгоритме поиска A*. Классическими приложениями были планирование действий робота и игры.

Другие учёные сосредоточились на разработке доказчиков теорем для логики первого порядка, основываясь на идеях формализации математики через математическую логику и автоматизацию доказательства теорем. Важным шагом стало появление метода резолюции Джона Алана Робинсона.

Параллельно Джон Маккарти и Пэт Хейс создали ситуационное исчисление для логического описания законов причинности и здравого смысла. Корделл Грин показал применение резолюции к ситуационному исчислению для формирования планов и реализовал автоматический ответ на вопросы и программирование^[6].

В то же время в Массачусетском технологическом институте (MIT) критиковали универсальную процедуру доказательства через резолюцию и продвигали идею процедурного представления знаний^[7]. Конфликт между логическими и процедурными подходами разрешился в начале 1970-х с появлением логического программирования и языка Prolog, где SLD-резолюция позволяла трактовать рогатые предложения как процедуры уменьшения целей.

Ранняя история логического программирования была в основном европейской. В Северной Америке исследователи (Эд Фейгенбаум, Фредерик Хейс-Рот) настаивали на моделировании предметных областей вместо универсального вывода^[8].

Эти исследования стали основой когнитивной революции в психологии и развития направления КЗ, приведших к появлению экспертных систем, продукционных систем, языков фреймов в 1970–1980-е годы. С акцента на универсальные решатели задач ИИ перешёл к экспертным системам, решающим конкретные задачи уровня компетенции человека — например, медицинскую диагностику^[9].

Экспертные системы ввели терминологию: знания делятся на базу знаний (факты и правила предметной области) и выводящий механизм (какой применяет знания к решению задач). Первые базы знаний имели плоскую структуру — утверждения о значениях переменных для использования правилами^[10].

В то же время Марвин Минский предложил концепцию фрейма (1974)^[11]. Фрейм аналогичен классу объектов: это абстрактное описание категории объектов/ситуаций/решений. Фреймы позволяли обрабатывать сложные сценарии естественного языка и социальные ожидания в ситуациях вроде заказа еды.

Вскоре исследователи поняли синергетический эффект объединения фреймов и правил: фреймы лучше моделируют реальный мир, правила — сложную логику; интегрированные системы (как KEE от Intellicorp, 1983) объединяли оба подхода: полноценный выводящий механизм с прямым и обратным выводом, фреймовая база знаний с триггерами, слотами (данными), наследованием и пересылкой сообщений^[12].

Интеграция фреймов, правил и объектно-ориентированного программирования активно велась коммерческими компаниями вроде KEE и Symbolics. В то же время параллельно развивались формалистские подходы, где важнейшим языком был KL-ONE (1980-е) — формальный язык фреймов с чёткой семантикой и формальным определением отношений «является» («is-a»)^[13]. Классификаторы (reasoners) скрыто выводили новые связи над классами, осуществляли проверку согласованности базы знаний^[14].

Одной из важнейших задач стало моделирование здравого смысла: для функционирования в естественном языке программы должны обладать обширными базами повседневных знаний, которые человек считает самоочевидными (базовые физические принципы, причинность, намерения и т.д.). Примером такого вызова стала проблема фрейма — необходимость явно описывать устойчивость мира в формальных моделях. Помимо исчисления ситуаций, одним из крупнейших проектов стала система Cyc, где специалисты вручную моделировали здравый смысл в собственном фреймовом языке^[15].

Формально начало современной теории КЗ положена гипотеза представления знаний (Brian Cantwell Smith, 1985)^[16]:

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

Одним из наиболее активно развивающихся направлений является Семантическая паутина. Семантическая паутина пытается добавить слой семантики к сегодняшнему интернету: вместо индексирования по ключевым словам сайты описываются с помощью онтологий понятий. Фреймовые языки и автоматическая классификация лежат в основе этого будущего: статическое определение онтологий ограничивает возможности динамичных интернет-систем, поэтому классификаторы позволяют справляться с постоянно меняющейся средой^[17].

Современные проекты, финансируемые в том числе DARPA, интегрируют фреймовые языки и классификаторы с маркировочными языками на базе XML. Resource Description Framework (RDF) реализует определение классов, подклассов и свойств объектов; Web Ontology Language (OWL) добавляет дополнительную семантику и интеграцию с классификационными механизмами^[18].

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

Основание КЗ заключается в том, что традиционный процедурный код не всегда подходит для решения сложных задач. Представление знаний позволяет создавать и поддерживать сложные программные системы проще и эффективнее, а также лежит в основе экспертных систем.

Например, работа с экспертами в терминах бизнес-правил (а не кода) сокращает смысловой разрыв между пользователями и разработчиками, делая возможной практическую разработку сложных систем.

Представление знаний тесно связано с автоматизированным рассуждением, поскольку одна из целей КЗ — обеспечить возможность рассуждать над явным знанием, делать выводы, добавлять новое знание. Фактически все языки представления знаний включают в себя выводящий механизм^[19].

Ключевая дилемма в проектировании формализмов КЗ — это баланс между выразительностью и разрешимостью^[20]. Логика первого порядка (ЛПО), обладающая высокой выразительностью и способная формализовать почти всю математику, служит своего рода стандартом для сравнения возможностей языков КЗ.

Однако ЛПО имеет два недостатка как формализм КЗ: сложность использования и низкая эффективность реализации. Высокая выразительная сила ведёт к множеству способов выражения одной и той же информации, что затрудняет формализацию. Сложность доказательных процедур делает реализацию ЛПО неэффективной и непонятной для конечного пользователя.

Одно из важнейших открытий ИИ 1970-х — языки с меньшей выразительной силой могут по сути приближаться к возможностям ЛПО, но быть гораздо проще для понимания человеком и машиной. Большинство ранних формализмов, от баз данных до семантических сетей, делали разные выборы по балансу между выразительностью, естественностью выражения и эффективностью^[21]. Именно такая «золотая середина» стала мотивом появления IF-THEN правил в экспертных системах.

Похожий баланс был важен при создании логического программирования и языка Prolog. Несмотря на схожий с продукционными правилами синтаксис, логические программы имеют строго определённую формальную семантику.

Ранняя форма логического программирования базировалась на рогатых предложениях ЛПО. Позднее появилось расширение — правило отрицание как сбой, переводящее ЛП в область немонотонных логик и умолчательные рассуждения. Такая семантика совмещает особенности стандартной ЛПО с предположениями о единственности имён и замкнутом мире, которые в чистой ЛПО выразить крайне сложно^[22].

В 1993 году Рэндалл Дэвис (MIT) выделил пять ключевых ролей формализма КЗ^[23]:

• КЗ выступает в роли суррогата — заменителя объекта, что позволяет субъекту делать выводы «мысленно», рассуждая о последствиях, а не действуя в реальном мире;
• КЗ — это набор онтологических обязательств, отвечающих на вопрос: «в терминах каких сущностей я мыслю о мире?»;
• Формализм КЗ — фрагментарная теория интеллектуального рассуждения: (i) концепция рассуждения, (ii) набор допустимых и (iii) рекомендуемых выводов;
• КЗ — это среда для эффективных вычислений: формализм облегчает организацию информации и ускоряет рассуждения;
• КЗ — это средство человеческого выражения: язык, в котором мы формулируем знания о мире.

Представление знаний и рассуждение — ключевые технологии семантической паутины. Языки на основе фреймов с автоматической классификацией реализуют слой семантики над интернетом: становится возможно строить логические запросы вместо простого текстового поиска^[17]. Классификаторы (reasoners) ориентированы на отношения подчинения (subsumption): они могут автоматически выводить новые классы и динамически перестраивать онтологию при поступлении новой информации^[24].

Семантическая паутина сочетает идеи КЗОЗ с языками разметки на основе XML. RDF обеспечивает базовые возможности описания объектов и отношений типа «является» и свойств; OWL дополняет семантику и интеграцию с классификаторами^[18].

В 1985 году Рональд Брачман выделил ключевые проблемы для исследований КЗ^[25]:

• Примитивы: исходные средства моделирования знаний — семантические сети, структуры и алгоритмы поиска, языки с логикой первого порядка (например, Prolog), специализированные системы доказательства теорем.
• Мета-представление: способность формализма представлять собственную структуру (reflection), например, метапротоокол в Smalltalk и CLOS позволяет динамически изменять классы и структуру базы знаний во время выполнения.
• Неполнота: для описания реального мира в логике часто нужны дополнительные аксиомы и ограничения. Важен учёт степеней уверенности (например, «Сократ — человек с вероятностью 50%»), что привело к промышленному применению коэффициентов уверенности и появлению нечёткой логики^[26].
• Определения и универсалии против фактов и значений по умолчанию: универсалии — общие утверждения о мире («Все люди смертны»), факты — частные примеры («Сократ — человек, следовательно смертен»). Практически все формализмы КЗ решают эту проблему через варианты теории множеств.
• Немонотонное рассуждение: формализм допускает гипотетические рассуждения, динамическую изменяемость выводов при изменении фактов (реализуется через систему поддержки истины)^[27].
• Выразительная достаточность: эталон — ЛПО; однако реализовать её полноценно невозможно, и исследователи предварительно оговаривают степень выразимости выбранного формализма^[28].
• Эффективность вывода: быстрота обновления базы знаний и получения новых выводов; чаще всего выраженная выразительность снижает эффективность рассуждения, что было актуально для ранних систем, работавших в медленных интерпретируемых средах, например, Lisp.

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

С масштабированием и необходимостью интегрировать обширные или модульные базы знаний возникло направление онтологической инженерии — проектирование и построение крупных, разделяемых между проектами знаний. Одним из ведущих проектов был Cyc, который стремился создать энциклопедическую базу общего и здравого смысла. Для взаимодействия ИИ с человеком оказалось необходимо моделировать не только специальные, но и тривиальные человеческие знания. Для Cyc был специально создан язык CycL.

Позднее появились и другие языки онтологий. Большинство из них — декларативные языки (фреймовые или производные от ЛПО). Модульность — возможность четко определить границы предметных областей и задачи — стала обязательным свойством формализмов: "Каждая онтология — соглашение в сообществе с общей целью" (Том Грубер). Различие взглядов неизбежно, всеобщая онтология невозможна: мировоззрение нужно объединять^[29].

Работы по построению онтологий проводились в разных предметных областях — онтология физических жидкостей^[30], модель сосредоточенных параметров для электрических цепей^[31], онтологии времени, убеждений, даже программирования.

Например, модель сосредоточенных параметров предполагает описание схем в терминах компонентов и соединений, мгновенной передачи сигналов по связям. Если же требуется учитывать электродинамику — сигналы распространяются с конечной скоростью, а резистор становится распределённой средой. Аналогично, медицина в терминах правил (MYCIN) и фреймов (INTERNIST) выглядит по-разному: MYCIN делает выводы на основе эмпирических связей, INTERNIST — на основе прототипических заболеваний.

Онтологии могут быть представлены в различных языках и нотациях (логика, LISP и др.); не форма важна, а моделируемые понятия — например, компоненты и связи. Граница между онтологиями чётко меняет модель задачи: медицинская диагностика на правилах и на фреймах — разные по подходу системы.