БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ

Многие исследователи вполне обосновано утверждают [186], что исследования в области формального представления знаний начались с классических работ индийских теоретиков, посвященных грамматике шастрических текстов на санскрите, которые относятся к первому тысячелетию до н.э. На Западе к числу самых первых примеров таких исследований относится использование определений терминов в трудах древнегреческих математиков. Безусловно, как форма представления знаний может также рассматриваться разработка технической терминологии в любой области.
На первых порах дискуссии на тему представления в искусственном интеллекте в основном сосредоточивались на "представлении задач", а не на "представлении знаний" (см., например, приведенное Амарелем [24] обсуждение задачи с миссионерами и каннибалами). В 1970-х годах основной акцент в искусственном интеллекте был сделан на разработке "экспертных систем" (называемых также "системами, основанными на знаниях"), которые были способны при наличии соответствующих знаний в проблемной области достичь или превзойти производительность людей-экспертов при решении узко определенных задач. Например, даже первая экспертная система, Dendral [458], [936], интерпретировала выходные данные массового спектрометра (прибора, применяемого для анализа структуры органических химических веществ) столь же точно, как и опытные химики. Хотя успех системы Dendral позволил сообществу исследователей по искусственному интеллекту убедиться в важности представления знаний, формальные средства представления, используемые в Dendral, были в высшей степени специализированными и относящимися только к данной проблемной области химии. Со временем у исследователей появилось стремление к стандартизации формальных средств представления знаний и онтологии, что позволило бы упростить процесс создания новых экспертных систем.
В ходе решения этой проблемы им пришлось проникнуть на территорию, которая до сих пор исследовалась только философами, изучающими проблемы науки и языка. Принятое в искусственном интеллекте требование, согласно которому предлагаемые теории должны "работать", привело к более быстрому и глубокому прогрессу в решении проблем по сравнению с той ситуацией, когда эти проблемы рассматривались как принадлежащие исключительно к области философии (хотя такой подход время от времени приводил к "повторному изобретению колеса").
Первые попытки создания всеобъемлющих таксономии, или классификаций, относятся к временам древности. Применения правильных схем классификации и категоризации настоятельно требовал Аристотель (384-322 до н.э.). В Органон, коллекцию трудов Аристотеля по логике, собранную учениками Аристотеля после его смерти, включен трактат под названием Категории, в котором Аристотель попытался создать то, что мы теперь называем верхней онтологией. Он также ввел понятия родов и видов для классификации нижнего уровня, хотя и не в их современном, сугубо биологическом смысле. Современная система биологической классификации, включая использование "биноминальной номенклатуры" (в формальном смысле слова — классификации по родам и видам), была предложена шведским биологом Карлом Линнеем (1707—1778). Проблемы, связанные с естественными разновидностями и неточными границами категорий, кроме многих других работ, рассматривались в [882], [1252], [1372] и [1608].
В последнее время продолжает расти интерес к крупномасштабным онтологиям. В проекте CYC [908], [910] была разработана верхняя онтология с 6000 понятий, состоящая из 60 000 фактов, а также лицензирована гораздо более крупная глобальная онтология. Организацией IEEE был создан подкомитет Р1600.1, получивший название "Рабочей группы по стандарту верхней онтологии" (Standard Upper Ontology Working Group), а организация Open Mind Initiative привлекла к работе больше 7000 пользователей Internet, собрав свыше 400 000 фактов об обыденных понятиях. В среде Web появились такие стандарты, как RDF, XML и Semantic Web [ПО], хотя они еще не нашли широкого распространения. Много интересных статей в области общих и специализированных онтологии публикуется по материалам конференции Formal Ontology in Information Systems (FOIS).
Таксономия, используемая в этой главе, разработана авторами данной книги и частично основана на опыте их участия в проекте CYC, а также на работах Хванга, Шуберта [714] и Дэвиса 1332]. Воодушевляющее описание общего проекта представления обыденных знаний приведено в книге Хейса The Naive Physics Manifesto [634], [637].
Проблемы представления времени, изменений, действий и событий широко исследовались не только в искусственном интеллекте, но и в философии и теоретических компьютерных науках. К числу наиболее развитых направлений относится временная логика, представляющая собой специализированную логику, в которой каждая модель описывает полную траекторию развития процесса во времени (обычно либо линейную, либо ветвящуюся), а не просто статическую реляционную структуру. Эта логика включает модальные операторы, применяемые к формулам; Dp означает "р будет истинным во все времена в будущем", а <гр означает "р станет истинным в некоторый момент в будущем". Исследования в области временной логики были впервые начаты Аристотелем, а также представителями мегарской и стоической школ в древней Греции. В современной истории развития науки применение формального исчисления для проведения рассуждений о времени было впервые предложено Финдлеем [468], но считается, что наибольшее влияние оказала работа Артура Прайора [1239]. К учебникам по временной логике относятся [1283] и [1529].
Специалисты в области теоретических компьютерных наук уже давно стремились формально описать свойства программ, рассматриваемых как последовательности вычислительных действий. Бурстолл [210] выдвинул идею использования модальных операторов для формирования рассуждений о компьютерных программах. Вскоре после этого Воган Пратт [1233] разработал динамическую логику, в которой модальные операторы обозначают результаты выполнения программ или другие действия (см. также [620]). Например, в динамической логике, если а — имя программы, то " [а]р" означает "р должно быть истинным во всех состояниях мира, ставших результатом выполнения программы а в текущем состоянии мира", а "(сс)р" означает "р должно быть истинным по меньшей мере в одном из состоянии мира, ставшим результатом выполнения программы а в текущем состоянии мира". Динамическая логика была применена для фактического анализа программ Фишером и Ладнером [472]. В [1218] предложена идея использования классической временной логики для формирования рассуждений о программах.
Временная логика предусматривает введение времени непосредственно в теорию моделей языка, а методы представления времени, применяемые в искусственном интеллекте, как правило, предусматривали явное включение аксиом об интервалах времени и событиях в базу знаний, поэтому время не получало особого статуса в этой логике. Кроме того, данный подход в некоторых случаях обеспечивает большую ясность и гибкость. К тому же знания о времени, выраженные в логике первого порядка, могут быть более легко интегрированы с другими знаниями, накопленными в рассматриваемой проблемной области.
Первой попыткой представления времени и действий в искусственном интеллекте стало ситуационное исчисление, предложенное Джоном Маккарти [1010]. Первой системой искусственного интеллекта, в которой широко применялись рассуждения общего назначения о действиях в логике первого порядка, была система QA3 [592]. Ковальский [851] развил идею овеществления высказываний в рамках ситуационного исчисления.
Проблема окружения была впервые описана в [1013]. Многие исследователи считали эту проблему неразрешимой в логике первого порядка, и она стала стимулом для проведения большого объема исследований в области немонотонных логик. Многие философы, начиная от Дрейфуса [414] и заканчивая Крокеттом [310], указывали, что проблема окружения является одним из симптомов неизбежного краха всего направления работ по созданию искусственного интеллекта. Частичное решение проблемы представительного окружения с использованием аксиом состояния-преемника было предложено Рэем Рейтером [1277]; истоки решения проблемы выводимого окружения прослеживаются в [671], в которой были предложены методы, получившие название исчисления флюентных высказываний [1504]. Описание, приведенное в настоящей главе, частично основано на результатах анализа, изложенных в [931] и [1504]. Книги Шенахана [1391] и Рейтера [1279] содержат полное, современное изложение вопросов формирования рассуждений о действиях в ситуационном исчислении.
Частичное разрешение проблемы окружения снова пробудило стремление к использованию декларативного подхода для формирования рассуждений о действиях, что привело к созданию многих систем планирования специального назначения, начиная с первой половины 1970-х годов (см. главу 11). В исследованиях, проводимых в рамках когнитивной робототехники, был достигнут большой прогресс в области разработки средств логического представления действий и времени. В языке Golog используется полная выразительная мощь логического программирования для описания действий и планов [917], к тому же этот язык был дополнен, для того чтобы в нем можно было представлять параллельные действия [550], стохастические варианты среды [160] и результаты восприятия [1278].
Для создания средств представления непрерывного времени было предложено использовать исчисление событий, разработанное Ковальским и Серготом [854], а в дальнейшем появилось еще несколько вариантов исчисления событий [1341]. В [1392] представлен хороший краткий обзор. Джеймс Аллен предложил использовать для этой же цели временнь/е интервалы [15], [16], указывая, что интервалы являются гораздо более естественным средством формирования рассуждений о продолжительных и одновременных событиях, чем ситуации. В [877], [878] впервые предложены "вогнутые" временнь/е интервалы (интервалы с перерывами; по сути объединения обычных "выпуклых" временнь/х интервалов) и для представления времени применены математические методы абстрактной алгебры. Аллен [17] систематически исследовал широкий спектр методов, которые могут применяться для представления времени. Шохем [1403] описал процедуру овеществления событий и предложил использовать для этой цели разработанную им новейшую схему. Между онтологией на основе событий, приведенной в данной главе, и анализом событий, выполненным философом Дональдом Давидсоном [328], имеются весьма важные аналогии. К тому же типу относятся хронологии (history), предложенные в работе Патрика Хейса [636]; аналогичной разновидностью представления во многом является также онтология вневременных событий (liquid event).
Проблемы онтологического статуса веществ имеют длинную историю. Платон считал, что вещества — это абстрактные сущности, полностью отличающиеся от физических объектов; с его точки зрения следовало бы сказать, что кусок масла сделан из масла, MadeOf [Butter3, Butter), а не что кусок масла является элементом множества масла, Јutter3 е Butter. Такая идея ведет к созданию иерархии веществ, в которой, например, несоленое масло UnsaltedButter является более конкретно определенным веществом, чем само масло Butter. Научная позиция, принятая в этой главе, согласно которой вещества представляют собой категорию объектов, была обоснована Ричардом Монтегю [1072]. Кроме того, эта позиция была принята и в проекте CYC. В [293] на эту позицию предпринята серьезная, но не настолько уж неотразимая атака. Альтернативный подход, упомянутый в данной главе, согласно которому масло представляет собой единственный объект, состоящий из всех маслоподобных объектов во вселенной, был первоначально предложен польским логиком Лесьневским [913]. В разработанной им мереологии (это название происходит от греческого слова, обозначающего "часть") используется отношение "часть—целое" в качестве замены математической теории множеств, в целях устранения таких абстрактных сущностей, как множества. Более удобное для чтения изложение этих идей приведено в [911], а в книге Гудмана The Structure of Appearance [579] эти идеи применяются для решения различных проблем в области представления знаний. Хотя в некоторых аспектах мереологический подход является весьма громоздким (например, в нем требуется отдельный механизм наследования, основанный на отношениях "часть—целое"), он получил поддержку Квайна [1253]. Гарри Бант [207] провел широкий анализ перспектив использования этого подхода в области представления знаний.
Мыслимые объекты и мыслительные состояния были предметом интенсивных исследований в области философии и искусственного интеллекта. Модальная логика представляет собой классический метод формирования рассуждений о знаниях, применяемый в философии. В модальной логике логика первого порядка дополняется модальными операторами, такими как В (от believes— убежден) и к (от knows — знает), которые принимают в качестве своих параметров высказывания, а не термы. В теории доказательств для модальной логики жестко регламентируются подстановки в пределах модальных контекстов, что позволяет обеспечить ссылочную непрозрачность. Модальная логика знаний была предложена Яакко Хинтиккой [654]. Саул Крипке [859] определил семантику модальной логики знаний в терминах возможных миров. Грубо говоря, мир для агента является возможным, если не противоречит всему, что знает агент. На основании такого подхода могут быть разработаны правила логического вывода с использованием оператора К. Роберт К. Мур связал модальную логику знаний с таким стилем формирования рассуждений о знаниях, который позволяет непосредственно ссылаться на возможные миры в логике первого порядка [1080], [1081]. Модальная логика может на первый взгляд показаться устрашающе запутанной областью науки, но она нашла очень важные применения в области формирования рассуждений об информации в распределенных компьютерных системах. В книге Фейгина и др. Reasoning about Knowledge [449] приведено исчерпывающее введение в этот модальный подход. Приложения теории знаний в искусственном интеллекте, экономике и распределенных системах обсуждаются на проводимой один раз в два года конференции Theoretical Aspects of Reasoning About Knowledge (TARK).
Синтаксическая теория мыслимых объектов была впервые глубоко исследована Каштаном и Монтегю [770], которые показали, что эта теория может приводить к парадоксам, если при использовании ее средств не соблюдается чрезвычайная осторожность. Поскольку такая теория позволяет создавать естественные модели физических конфигураций компьютера или мозга в терминах убеждений, она в последние годы получила широкое распространение в области искусственного интеллекта. В [604] и [833] эта теория использовалась для описания машин логического вывода с ограниченной мощью, а Моргенштерн [1086] показал, как можно ее использовать для описания предусловий знаний в планировании. Методы планирования таких действий, как наблюдение, описанные в главе 12, основаны на этой синтаксической теории. Эрни Дэвис [332] дал превосходное сравнение синтаксической и модальной теорий знания.
Греческий философ Порфирий (ок. 234—305 н.э) в своих комментариях к трактату Аристотеля Категории продемонстрировал то, что может рассматриваться как первая семантическая сеть. Чарльз С. Пирс [1199] разработал экзистенциальные графы, которые могут рассматриваться как первое формальное определение семантической сети с использованием современной логики. Инициатором исследований по семантическим сетям, проводимых в рамках искусственного интеллекта, был Росс Квиллиан [1251], основным стимулом для которого был интерес к человеческой памяти и языковой обработке. В важной статье Марвина Минского [1053] представлена одна из версий семантических сетей, основанная на использовании так называемых фреймов; фреймы служили для представления объектов или категорий и характеризовались наличием атрибутов и отношений с другими объектами или категориями. Хотя эта статья послужила важной причиной пробуждения интереса к области представления знаний как таковой, она подверглась критике за то, что в ней просто под другим углом были изложены идеи статей [132], [320], разработанные ранее в объектно-ориентированном программировании, такие как наследование и использование заданных по умолчанию значений. Однако еще не совсем ясно, в какой степени на указанные статьи по объектно-ориентированному программированию, в свою очередь, повлияли еще более ранние работы в области искусственного интеллекта, посвященные семантическим сетям.
Проблемы семантики приобрели особую остроту применительно к семантическим сетям, разработанным Квиллианом (и теми, кто стал последователем предложенного им подхода), в связи с тем, что в них использовались вездесущие и весьма неопределенные "связи IS-A", а также применительно к другим ранним формальным системам представления знаний, таким как Merlin [1079], с ее загадочными операциями "flat" и "cover". Знаменитая статья Вудса " What's In a Link?' [1613] привлекла внимание исследователей в области искусственного интеллекта к тому, что в формальных системах представления знаний должна быть точно определена семантика. Брачман [167] провел исследования по этой проблеме и предложил некоторые решения. Патрик Хейс в своей книге The Logic of Frames [635] провел еще более глубокие исследования и сформулировал утверждение, что "так называемые «фреймы» по большей части представляют собой просто новые синтаксические обозначения для фрагментов логики первого порядка". Дрю Макдермотт в своей работе Tarskian Semantics, or, No Notation without Denotation! [1022] доказывал, что модельно-теоретический подход к семантике, используемый в логике первого порядка, должен быть распространен на все формальные системы представления знаний. Однако эта идея является внутренне противоречивой; замечательно то, что сам Макдермотт пересмотрел свою позицию в работе A Critique of Pure Reason [1023]. Проявлением нового подхода стала Netl [451], сложная система семантической сети, в которой связи IS-A (называемые связями "виртуальной копии", или VC — virtual сору) были основаны в большей степени на понятии характеристик "наследования" систем фреймов или объектно-ориентированных языков программирования, чем на отношении подмножества, и были определены гораздо более точно по сравнению со связями, применявшимися Квиллианом в эпоху, предшествовавшую появлению работ Вудса. Система Netl привлекла особое внимание, поскольку предназначалась для реализации в параллельном аппаратном обеспечении для преодоления сложностей выборки информации из больших семантических сетей. Дэвид Турецкий [1512] подверг понятие наследования строгому математическому анализу. В [1381] обсуждаются сложности наследования с исключениями и показано, что в большинстве формулировок задача представления наследования является NP-полной.
Разработка описательных логик представляет собой один из наиболее современных этапов в длинной цепи исследований, нацеленных на поиск полезных подмножеств логики первого порядка, для которой задача логического вывода является осуществимой с помощью вычислительных средств. Гектор Левеск и Рон Брачман [916] показали, что неразрешимость логического вывода в основном возникает из-за использования определенных логических конструкций (особенно отличаются этим и оторые варианты использования дизъюнкции и отрицания). На основе системы
KL-One [1362] был разработан целый ряд систем, в проектах которых применены результаты теоретического анализа сложности; к числу наиболее известных из них относятся Krypton [168] и Classic [155]. Полученные при этом результаты продемонстрировали заметное повышение скорости логического вывода и позволили гораздо лучше понять зависимости между сложностью и выразительностью в системах формирования рассуждений. Общий итог современного состояния дел в этой области подведен в [215]. Протестуя против этой тенденции к упрощению, Дойл и Петил [411] доказывали, что ограничение выразительности языка либо исключает возможность решения некоторых проблем, либо побуждает пользователя обходить ограничения языка с помощью нелогических средств.
Все три основные формальные системы, предназначенные для использования в немонотонном логическом выводе, — косвенное описание [1012], логика умолчания [1276] и модальная немонотонная логика [1025] — были предложены в одном специальном выпуске AI Journal. Программирование множества ответов может рассматриваться как расширение понятия отрицания как недостижения цели или как уточнение понятия косвенного описания; основополагающая теория семантики стабильных моделей была предложена в [533], а ведущими системами программирования множества ответов являются DLV [432] и Smodels [1138]. Пример с дисковым накопителем взят из руководства пользователя Smodels [1484]. В [929] обсуждается использование программирования множества ответов для планирования. В [184] приведен хороший краткий обзор различных подходов к использованию немонотонной логики. В [262] рассматривается подход к логическому программированию, основанный на отрицании как недостижении цели, и анализируется дополнение Кларка. Ван Эмден и Ковальский [1530] показали, что каждая программа Prolog без отрицаний имеет уникальную минимальную модель. Последние годы характеризуются повторным пробуждением интереса к приложениям немонотонных логик в крупномасштабных системах представления знаний. По-видимому, первой системой, достигшей коммерческого успеха, является система Benlnq для обработки данных опросов, касающихся страховых льгот; эта система представляет собой приложение системы немонотонного наследования [1087]. В [929] обсуждается применение программирования множества ответов в планировании. Целый ряд систем формирования немонотонных рассуждений, основанных на логическом программировании, описан в трудах конференции Logic Programming and Nonmonotonic Reasoning (LPNMR).
Исследования в области систем поддержки истинности начались с создания систем TMS [409] и RUP [1003], которые по существу представляли собой системы JTMS. Подход на основе систем ATMS был описан в ряде статей Йохана де Клеера [345-347]. В работе Building Problem Solvers [479] подробно объяснено, как могут применяться системы TMS в приложениях искусственного интеллекта. В [1117] показано, что использование эффективной системы TMS обеспечило возможность планирования операций космического корабля агентства NASA в реальном времени.
По очевидным причинам в данной главе подробно не рассматривается каждая область представления знаний. Ниже описаны три основные темы, которые в ней не представлены.
• Качественная физика. Это подобласть представления знаний, которая главным образом относится к формированию логической, нечисловой теории физических объектов и процессов. Этот термин был предложен Йоханом де Клеером [344], хотя вполне можно считать, что это направление исследований началось с создания Фалманом [450] программы Build — развитого планировщика для построения сложных башен из блоков. В процессе проектирования этой программы Фалман открыл, что основная часть усилий (по его оценке, 80%) уходит на моделирование физических свойств мира блоков в целях вычисления устойчивости различных субфрагментов структур блоков, а не на само планирование как таковое. Он сформулировал набросок гипотетического процесса, подобного проведению рассуждений в рамках наивной физики, для объяснения причин того, почему дети младшего возраста способны решать задачи, подобные рассматриваемым в программе Build, без обращения к быстродействующей арифметике с плавающей точкой, которая используется в физическом моделировании программой Build. Хейс [636] применил "истории" (четырехмерные фрагменты пространства-времени, аналогичные событиям Дэвидсона) для построения довольно сложной наивной физической теории жидкостей. Хейсу впервые удалось доказать в рамках искусственного интеллекта, что ванна с заткнутым сливом в конечном итоге переполнится, если вода из крана будет продолжать бежать, и что человек, упавший в озеро, весь вымокнет. В [349] и [478] описаны попытки создать нечто подобное общей теории физического мира на основе качественных абстракций физических уравнений. За последние годы качественная физика была разработана до такой степени, что с ее помощью стало возможным анализировать сложные физические системы, разнообразие которых весьма впечатляет [1340], [1631]. Качественные методы использовались для разработки новейших проектов часов, дворников для ветрового стекла и шестиногих шагающих машин [1470], [1472]. Хорошим введением в эту область является сборник статей Readings in Qualitative Reasoning about Physical Systems [ 1570].
• Пространственные рассуждения. Рассуждения, необходимые для навигации в мире вампуса и в мире совершения покупок, являются тривиальными по сравнению с теми, что требуются в богатой пространственной структуре реального мира. Результаты самых первых серьезных попыток описать обыденные рассуждения о пространстве приведены в работах Эрнеста Дэвиса [331], [332]. В исчислении региональных связей Кона и др. [280] поддерживается определенная форма качественных пространственных рассуждений; эти исследования привели к созданию географических информационных систем нового типа. Как и с помощью качественной физики, агент, так сказать, многое может сделать без обращения к полному метрическому представлению. А если такое представление становится необходимым, то можно воспользоваться методами, разработанными в робототехнике (глава 25).
• Психологические рассуждения. Психологические рассуждения касаются проблемы разработки для искусственных агентов работоспособных психологических моделей, которые могли бы использоваться агентами для формирования рассуждений о себе и о других агентах. Такие рассуждения часто основаны на так называемой народной психологии (folk psychology) — теории, претендующей на понимание того, какие принципы используются людьми в рассуждениях о себе и других людях. Когда исследователи в области искусственного интеллекта снабжают своих искусственных агентов психологическими теориями для формирования рассуждений о других агентах, эти теории часто основаны на описании исследователями проектов самих этих логических агентов. Поэтому в настоящее время наиболее продуктивны такие исследования в области психологических рассуждений в контексте понимания естественного языка, где наибольшую важность имеет предугадывание намерений говорящего.
Наиболее современными источниками сведений о работах в этих областях являются труды международной конференции Principles of Knowledge Representation and Reasoning. В работах Readings in Knowledge Representation [169] и Formal Theories of the Commonsense World [665] приведены превосходные антологии по представлению знаний; в первой в большей степени обсуждаются статьи, имевшие историческое значение в языках и формальных системах представления, а последняя посвящена накоплению самих знаний. В [332], [1448] и [1458] приведены учебные введения в проблематику представления знаний.







Материалы

Яндекс.Метрика