Лекция 2. Модели представления знаний в системах искусственного интеллекта
Лекция 2. Модели представления знаний в системах искусственного интеллекта
Логические модели
Постановка и решение любой задачи всегда связаны с ее "погружением" в подходящую предметную область. Так, решая задачу составления расписания обработки деталей на металлорежущих станках, мы вовлекаем в предметную область такие объекты, как конкретные станки, детали, интервалы времени, и общие понятия "станок", "деталь", "тип станка" и т. п. Все предметы и события, которые составляют основу общего понимания необходимой для решения задачи информации, называются предметной областью. Мысленно предметная область представляется состоящей из реальных или абстрактных объектов, называемых сущностями. Сущности предметной области находятся в определенных отношениях друг к другу (ассоциациях), которые также можно рассматривать как сущности и включать в предметную область. Между сущностями наблюдаются различные отношения подобия. Совокупность подобных сущностей составляет класс сущностей, являющийся новой сущностью предметной области.
Отношения между сущностями выражаются с помощью суждений. Суждение-это мысленно возможная ситуация, которая может иметь место для предъявляемых сущностей или не иметь места. В языке (формальном или естественном) суждениям отвечают предложения. Суждения и предложения также можно рассматривать как сущности и включать в предметную область. Языки, предназначенные для описания предметных областей, называются языками представления знаний. Универсальным языком представления знаний является естественный язык. Однако использование естественного языка в системах машинного представления знаний наталкивается на большие трудности ввиду присущих ему нерегулярностей, двусмысленностей, пресуппозиций и т. п. Но главное препятствие заключается в отсутствии формальной семантики естественного языка, которая имела бы достаточно эффективную операционную поддержку.
Для представления математического знания в математической логике давно пользуются логическими формализмами - главным образом исчислением предикатов, которое имеет ясную формальную семантику и операционную поддержку в том смысле, что для него разработаны механизмы вывода. Поэтому исчисление предикатов было первым логическим языком, который применили для формального описания предметных областей, связанных с решением прикладных задач. Описания предметных областей, выполненные в логических языках, называются (формальными) логическими моделями.
Сетевые модели
Введем ряд определений. Под сущностью будем понимать объект произвольной природы. Этот объект может существовать в реальном мире. В этом случае он будет называться П-сущностью. В базе знаний ему соответствует некоторое описание, полнота которого определяется той информацией, которую имеет о П-сущности ИС. Такое представление в базе знаний называется М-сущностью. Отметим, что могут существовать М-сущности, для которых в окружающем ИС мире нет соответствующих П-сущностей. Такие М-сущности представляют собой абстрактные объекты, полученные в результате операций типа обобщения внутри базы знаний.
Разделение на два типа сущностей позволяет использовать в сетевых моделях идеи, впервые сформулированные в теории семиотических моделей и основанном на них ситуационном управлении. Под семиотическими моделями проблемных областей будет пониматься комплекс процедур, позволяющих отображать в базе знаний П-сущности и их связи, фиксируемые в проблемной области инженером по знаниям, в совокупность связанных между собой М-сущностей. Способ интерпретации взаимосвязанных П-сущностей будет называться денотативной семантикой, а способ интерпретации взаимосвязанных М-сущностей - коннотативной семантикой.
П-сущность по отношению к соответствующей ей в базе знаний М-сущности называется денотатом или референтом этой М-сущности, а М-сущность по отношению к исходной П-сущности - ее десигнатом, именем, меткой, идентификатором и т. п. Десигнат-это простейший элемент в сетевой модели. Он входит в класс терминальных объектов сетевой модели. Терминальным объектом называется М-сущность, которая не может быть разложена на более простые сущности. Остальные М-сущности называются производными объектами или производными М-сущностями.
Перечень терминальных объектов, которые могут образовывать классы или типы, задается при проектировании ИС. Ими могут быть целые вещественные числа, идентификаторы, строки, списки и т. п. Семантика терминальных объектов определяется набором допустимых процедур, оперирующих с ними, например: арифметические действия над числами, сравнение между собой строк или идентификаторов, операции ввода-вывода, включающие необходимые трансформации представлений, и т. д.
Продукционные модели
Продукции наряду с фреймами являются наиболее популярными средствами представления знаний в ИС. Продукции, с одной стороны, близки к логическим моделям, что позволяет организовывать на них эффективные процедуры вывода, а с другой стороны, более наглядно отражают знания, чем классические логические модели. В них отсутствуют жесткие ограничения, характерные для логических исчислений, что дает возможность изменять интерпретацию элементов продукции.
В общем виде под продукцией понимается выражение следующего вида: (i); Q; Р; А=>В; N. Здесь i-имя продукции, с помощью которого данная продукция выделяется из всего множества продукций. В качестве имени может выступать некоторая лексема, отражающая суть данной продукции (например, "покупка книги" или "набор кода замка"), или порядковый номер продукции в их множестве, хранящемся в памяти системы.
Элемент Q характеризует сферу применения продукции. Такие сферы легко выделяются в когнитивных структурах человека. Наши знания как бы "разложены по полочкам". На одной "полочке" хранятся знания о том, как надо готовить пищу, на другой-как добраться до работы и т. п. Разделение знаний на отдельные сферы позволяет экономить время на поиск нужных знаний. Такое же разделение на сферы в базе знаний ИС целесообразно и при использовании для представления знаний продукционных моделей.
Основным элементом продукции является ее ядро: А=>В. Интерпретация ядра продукции может быть различной и зависит от того, что стоит слева и справа от знака секвенции =>. Обычное прочтение ядра продукции выглядит так: ЕСЛИ A, ТО B, более сложные конструкции ядра допускают в правой части альтернативный выбор, например, ЕСЛИ А, ТО B1, ИНАЧЕ B2. Секвенция может истолковываться в обычном логическом смысле как знак логического следования В из истинного А (если А не является истинным выражением, то о В ничего сказать нельзя). Возможны и другие интерпретации ядра продукции, например A описывает некоторое условие, необходимое для того, чтобы можно было совершить действие В.
Элемент Р есть условие применимости ядра продукции. Обычно Р представляет собой логическое выражение (как правило, предикат). КогдаР принимает значение "истина", ядро продукции активизируется. Если Р ложно, то ядро продукции не может быть использовано. Например, если в продукции "НАЛИЧИЕ ДЕНЕГ; ЕСЛИ ХОЧЕШЬ КУПИТЬ ВЕЩЬ X, ТО ЗАПЛАТИ В КАССУ ЕЕ СТОИМОСТЬ И ОТДАЙ ЧЕК ПРОДАВЦУ" условие применимости ядра продукции ложно, т. е. денег нет, то применить ядро продукции невозможно.
Элемент N описывает постусловия продукции. Они актуализируются только в том случае, если ядро продукции реализовалось. Постусловия продукции описывают действия и процедуры, которые необходимо выполнить после реализации В. Например, после покупки некоторой вещи в магазине необходимо в описи товаров, имеющихся в этом магазине, уменьшить количество вещей такого типа на единицу. Выполнение N может происходить не сразу после реализации ядра продукции.
Если в памяти системы хранится некоторый набор продукций, то они образуют систему продукций. В системе продукций должны быть заданы специальные процедуры управления продукциями, с помощью которых происходит актуализация продукций и выбор для выполнения той или иной продукции из числа актуализированных.
В ряде ИС используются комбинации сетевых и продукционных моделей представления знаний. В таких моделях декларативные знания описываются в сетевом компоненте модели, а процедурные знания - в продукционном. В этом случае говорят о работе продукционной системы над семантической сетью.
Методы решения задач
Функционирование многих ИС носит целенаправленный характер (примером могут служить автономные интеллектуальные роботы). Типичным актом такого функционирования является решение задачи планирования пути достижения нужной цели из некоторой фиксированной начальной ситуации. Результатом решения задачи должен быть план действий - частично-упорядоченная совокупность действий. Такой план напоминает сценарий, в котором в качестве отношения между вершинами выступают отношения типа: "цель-подцель" "цель-действие", "действие-результат" и т. п. Любой путь в этом сценарии, ведущий от вершины, соответствующей текущей ситуации, в любую из целевых вершин, определяет план действий.
Поиск плана действий возникает в ИС лишь тогда, когда она сталкивается с нестандартной ситуацией, для которой нет заранее известного набора действий, приводящих к нужной цели. Все задачи построения плана действий можно разбить на два типа, которым соответствуют различные модели: планирование в пространстве состояний (SS-проблема) и планирование в пространстве задач (PR-проблема).
В первом случае считается заданным некоторое пространство ситуаций. Описание ситуаций включает состояние внешнего мира и состояние ИС, характеризуемые рядом параметров. Ситуации образуют некоторые обобщенные состояния, а действия ИС или изменения во внешней среде приводят к изменению актуализированных в данный момент состояний. Среди обобщенных состояний выделены начальные состояния (обычно одно) и конечные (целевые) состояния. SS-проблема состоит в поиске пути, ведущего из начального состояния в одно из конечных. Если, например, ИС предназначена для игры в шахматы, то обобщенными состояниями будут позиции, складывающиеся на шахматной доске. В качестве начального состояния может рассматриваться позиция, которая зафиксирована в данный момент игры, а в качестве целевых позиций - множество ничейных позиций. Отметим, что в случае шахмат прямое перечисление целевых позиций невозможно. Матовые и ничейные позиции описаны на языке, отличном от языка описания состояний, характеризуемых расположением фигур на полях доски. Именно это затрудняет поиск плана действий в шахматной игре.
При планировании в пространстве задач ситуация несколько иная. Пространство образуется в результате введения на множестве задач отношения типа: "часть - целое", "задача - подзадача", "общий случай - частный случай" и т. п. Другими словами, пространство задач отражает декомпозицию задач на подзадачи (цели на подцели). PR-проблема состоит в поиске декомпозиции исходной задачи на подзадачи, приводящей к задачам, решение которых системе известно. Например, ИС известно, как вычисляются значения sin x и cos x для любого значения аргумента, и как производится операция деления. Если ИС необходимо вычислить tg x, то решением PR-проблемы будет представление этой задачи в виде декомпозиции tgx=sin x/cos x (кроме х= /2+k ).
Лекция 2. Модели представления знаний в системах искусственного интеллекта
Логические модели
Постановка и решение любой задачи всегда связаны с ее "погружением" в подходящую предметную область. Так, решая задачу составления расписания обработки деталей на металлорежущих станках, мы вовлекаем в предметную область такие объекты, как конкретные станки, детали, интервалы времени, и общие понятия "станок", "деталь", "тип станка" и т. п. Все предметы и события, которые составляют основу общего понимания необходимой для решения задачи информации, называются предметной областью. Мысленно предметная область представляется состоящей из реальных или абстрактных объектов, называемых сущностями. Сущности предметной области находятся в определенных отношениях друг к другу (ассоциациях), которые также можно рассматривать как сущности и включать в предметную область. Между сущностями наблюдаются различные отношения подобия. Совокупность подобных сущностей составляет класс сущностей, являющийся новой сущностью предметной области.
Отношения между сущностями выражаются с помощью суждений. Суждение-это мысленно возможная ситуация, которая может иметь место для предъявляемых сущностей или не иметь места. В языке (формальном или естественном) суждениям отвечают предложения. Суждения и предложения также можно рассматривать как сущности и включать в предметную область. Языки, предназначенные для описания предметных областей, называются языками представления знаний. Универсальным языком представления знаний является естественный язык. Однако использование естественного языка в системах машинного представления знаний наталкивается на большие трудности ввиду присущих ему нерегулярностей, двусмысленностей, пресуппозиций и т. п. Но главное препятствие заключается в отсутствии формальной семантики естественного языка, которая имела бы достаточно эффективную операционную поддержку.
Для представления математического знания в математической логике давно пользуются логическими формализмами - главным образом исчислением предикатов, которое имеет ясную формальную семантику и операционную поддержку в том смысле, что для него разработаны механизмы вывода. Поэтому исчисление предикатов было первым логическим языком, который применили для формального описания предметных областей, связанных с решением прикладных задач. Описания предметных областей, выполненные в логических языках, называются (формальными) логическими моделями.
Сетевые модели
Введем ряд определений. Под сущностью будем понимать объект произвольной природы. Этот объект может существовать в реальном мире. В этом случае он будет называться П-сущностью. В базе знаний ему соответствует некоторое описание, полнота которого определяется той информацией, которую имеет о П-сущности ИС. Такое представление в базе знаний называется М-сущностью. Отметим, что могут существовать М-сущности, для которых в окружающем ИС мире нет соответствующих П-сущностей. Такие М-сущности представляют собой абстрактные объекты, полученные в результате операций типа обобщения внутри базы знаний.
Разделение на два типа сущностей позволяет использовать в сетевых моделях идеи, впервые сформулированные в теории семиотических моделей и основанном на них ситуационном управлении. Под семиотическими моделями проблемных областей будет пониматься комплекс процедур, позволяющих отображать в базе знаний П-сущности и их связи, фиксируемые в проблемной области инженером по знаниям, в совокупность связанных между собой М-сущностей. Способ интерпретации взаимосвязанных П-сущностей будет называться денотативной семантикой, а способ интерпретации взаимосвязанных М-сущностей - коннотативной семантикой.
П-сущность по отношению к соответствующей ей в базе знаний М-сущности называется денотатом или референтом этой М-сущности, а М-сущность по отношению к исходной П-сущности - ее десигнатом, именем, меткой, идентификатором и т. п. Десигнат-это простейший элемент в сетевой модели. Он входит в класс терминальных объектов сетевой модели. Терминальным объектом называется М-сущность, которая не может быть разложена на более простые сущности. Остальные М-сущности называются производными объектами или производными М-сущностями.
Перечень терминальных объектов, которые могут образовывать классы или типы, задается при проектировании ИС. Ими могут быть целые вещественные числа, идентификаторы, строки, списки и т. п. Семантика терминальных объектов определяется набором допустимых процедур, оперирующих с ними, например: арифметические действия над числами, сравнение между собой строк или идентификаторов, операции ввода-вывода, включающие необходимые трансформации представлений, и т. д.
Продукционные модели
Продукции наряду с фреймами являются наиболее популярными средствами представления знаний в ИС. Продукции, с одной стороны, близки к логическим моделям, что позволяет организовывать на них эффективные процедуры вывода, а с другой стороны, более наглядно отражают знания, чем классические логические модели. В них отсутствуют жесткие ограничения, характерные для логических исчислений, что дает возможность изменять интерпретацию элементов продукции.
В общем виде под продукцией понимается выражение следующего вида: (i); Q; Р; А=>В; N. Здесь i-имя продукции, с помощью которого данная продукция выделяется из всего множества продукций. В качестве имени может выступать некоторая лексема, отражающая суть данной продукции (например, "покупка книги" или "набор кода замка"), или порядковый номер продукции в их множестве, хранящемся в памяти системы.
Элемент Q характеризует сферу применения продукции. Такие сферы легко выделяются в когнитивных структурах человека. Наши знания как бы "разложены по полочкам". На одной "полочке" хранятся знания о том, как надо готовить пищу, на другой-как добраться до работы и т. п. Разделение знаний на отдельные сферы позволяет экономить время на поиск нужных знаний. Такое же разделение на сферы в базе знаний ИС целесообразно и при использовании для представления знаний продукционных моделей.
Основным элементом продукции является ее ядро: А=>В. Интерпретация ядра продукции может быть различной и зависит от того, что стоит слева и справа от знака секвенции =>. Обычное прочтение ядра продукции выглядит так: ЕСЛИ A, ТО B, более сложные конструкции ядра допускают в правой части альтернативный выбор, например, ЕСЛИ А, ТО B1, ИНАЧЕ B2. Секвенция может истолковываться в обычном логическом смысле как знак логического следования В из истинного А (если А не является истинным выражением, то о В ничего сказать нельзя). Возможны и другие интерпретации ядра продукции, например A описывает некоторое условие, необходимое для того, чтобы можно было совершить действие В.
Элемент Р есть условие применимости ядра продукции. Обычно Р представляет собой логическое выражение (как правило, предикат). КогдаР принимает значение "истина", ядро продукции активизируется. Если Р ложно, то ядро продукции не может быть использовано. Например, если в продукции "НАЛИЧИЕ ДЕНЕГ; ЕСЛИ ХОЧЕШЬ КУПИТЬ ВЕЩЬ X, ТО ЗАПЛАТИ В КАССУ ЕЕ СТОИМОСТЬ И ОТДАЙ ЧЕК ПРОДАВЦУ" условие применимости ядра продукции ложно, т. е. денег нет, то применить ядро продукции невозможно.
Элемент N описывает постусловия продукции. Они актуализируются только в том случае, если ядро продукции реализовалось. Постусловия продукции описывают действия и процедуры, которые необходимо выполнить после реализации В. Например, после покупки некоторой вещи в магазине необходимо в описи товаров, имеющихся в этом магазине, уменьшить количество вещей такого типа на единицу. Выполнение N может происходить не сразу после реализации ядра продукции.
Если в памяти системы хранится некоторый набор продукций, то они образуют систему продукций. В системе продукций должны быть заданы специальные процедуры управления продукциями, с помощью которых происходит актуализация продукций и выбор для выполнения той или иной продукции из числа актуализированных.
В ряде ИС используются комбинации сетевых и продукционных моделей представления знаний. В таких моделях декларативные знания описываются в сетевом компоненте модели, а процедурные знания - в продукционном. В этом случае говорят о работе продукционной системы над семантической сетью.
Методы решения задач
Функционирование многих ИС носит целенаправленный характер (примером могут служить автономные интеллектуальные роботы). Типичным актом такого функционирования является решение задачи планирования пути достижения нужной цели из некоторой фиксированной начальной ситуации. Результатом решения задачи должен быть план действий - частично-упорядоченная совокупность действий. Такой план напоминает сценарий, в котором в качестве отношения между вершинами выступают отношения типа: "цель-подцель" "цель-действие", "действие-результат" и т. п. Любой путь в этом сценарии, ведущий от вершины, соответствующей текущей ситуации, в любую из целевых вершин, определяет план действий.
Поиск плана действий возникает в ИС лишь тогда, когда она сталкивается с нестандартной ситуацией, для которой нет заранее известного набора действий, приводящих к нужной цели. Все задачи построения плана действий можно разбить на два типа, которым соответствуют различные модели: планирование в пространстве состояний (SS-проблема) и планирование в пространстве задач (PR-проблема).
В первом случае считается заданным некоторое пространство ситуаций. Описание ситуаций включает состояние внешнего мира и состояние ИС, характеризуемые рядом параметров. Ситуации образуют некоторые обобщенные состояния, а действия ИС или изменения во внешней среде приводят к изменению актуализированных в данный момент состояний. Среди обобщенных состояний выделены начальные состояния (обычно одно) и конечные (целевые) состояния. SS-проблема состоит в поиске пути, ведущего из начального состояния в одно из конечных. Если, например, ИС предназначена для игры в шахматы, то обобщенными состояниями будут позиции, складывающиеся на шахматной доске. В качестве начального состояния может рассматриваться позиция, которая зафиксирована в данный момент игры, а в качестве целевых позиций - множество ничейных позиций. Отметим, что в случае шахмат прямое перечисление целевых позиций невозможно. Матовые и ничейные позиции описаны на языке, отличном от языка описания состояний, характеризуемых расположением фигур на полях доски. Именно это затрудняет поиск плана действий в шахматной игре.
При планировании в пространстве задач ситуация несколько иная. Пространство образуется в результате введения на множестве задач отношения типа: "часть - целое", "задача - подзадача", "общий случай - частный случай" и т. п. Другими словами, пространство задач отражает декомпозицию задач на подзадачи (цели на подцели). PR-проблема состоит в поиске декомпозиции исходной задачи на подзадачи, приводящей к задачам, решение которых системе известно. Например, ИС известно, как вычисляются значения sin x и cos x для любого значения аргумента, и как производится операция деления. Если ИС необходимо вычислить tg x, то решением PR-проблемы будет представление этой задачи в виде декомпозиции tgx=sin x/cos x (кроме х= /2+k ).