Исследование дидактических возможностей сетевых моделей при разработке программных приложений систем искусственного интеллекта

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

В системах искусственного интеллекта имеются четыре основные модели представления знаний. Более наглядной и понятной студентам моделью считаются модели, представленные в виде семантической сети, которая является аналогом взвешенных графов. Но данная модель не совсем удобна для реализации на компьютере. Менее наглядной является формальная логическая модель преставления знаний, но именно для нее имеется эффективная реализации на компьютере. Возникает проблема эффективного перевода задач с языка теории графов на язык формальной логики предикатов. Если брать во внимание то, что наиболее распространенной реализацией формальной логической модели представления знаний в программировании является логическое программирование, в частности, язык Пролог, то проблему можно переформулировать следующим образом: как научить студентов представлять базовые алгоритмы на сетях (графах) в виде логической модели знаний и реализовывать их с помощью Пролог — системы.

Разработка учебных систем для студентов специальности «информатика» не должна проводиться эмпирическим путем. Каждая задача должна иметь математическое обоснование, в нашем случае, обоснование правильности перевода условий и решения задачи с языка теории графов на язык формальной логики.

Объект исследования: Процесс обучения студентов педагогической специальности «информатика» дисциплине «Основы искусственного интеллекта».

Предмет исследования: Использование семантических сетей при разработке учебных программных систем дисциплины «Основы искусственного интеллекта».

Цель: Исследование дидактических возможностей сетевых моделей при разработке программных приложений систем искусственного интеллекта в рамках дисциплины «Основы искусственного интеллекта» .

Исходя из цели дипломной работы, были определены следующие задачи:

Определить перечень вопросов раздела «Основы искусственного интеллекта» современной образовательной информатики на основе анализа учебно-методической литературы и документов Министерства образования и науки РФ.

Провести сравнительный анализ дидактических возможностей различных моделей знаний в преподавании дисциплины «Основы искусственного интеллекта» .

Выделить класс учебных задач дисциплины «Основы искусственного интеллекта» на основе представления моделей предметных областей.

Привести математическое обоснование хода решения выделенных задач.

Сформулировать математические высказывания на языке предикатов 1-го порядка.

Выделить класс учебных систем дисциплины «Основы искусственного интеллекта», рассмотреть этапы построения их прототипа.

Сформулировать методические рекомендации к преподаванию технологии логического программирования в дисциплине «Основы искусственного интеллекта».

Провести апробацию работы для студентов специальности «математика, информатика».

Для решения поставленных задач были использованы следующие методы: анализ учебно-методической литературы по данной проблеме; метод практического эксперимента.

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

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

Дипломная работа состоит из введения, двух глав, заключения и двух приложений.

В первой главе рассматриваются цели и задачи преподавания дисциплины «Основы искусственного интеллекта», современные направления исследований в области искусственного интеллекта; проводится обзор логической и сетевой моделей представления знаний; приведено математическое обоснование решения классических задач теории графов с помощью логической модели представления знаний.

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

В приложении 1 изложена реализация задачи коммивояжера и задачи китайского почтальона на языке Прологе. В приложении 2 рассмотрены этапы разработки прототипа учебной экспертной системы.

Результаты проведенной работы были изложены н6а седьмой научно-практической конференции «Наука и образование: проблемы и перспективы» (15 апреля 2005 г), доклад на тему: «Методика решения задач обхода сетей на Прологе при изучении дисциплины «Основы искусственного интеллекта» и на научно-практической конференции ФМФ (16 мая 2005 г), доклад на тему: «Дидактические возможности сетевых моделей при преподавании дисциплины «Основы искусственного интеллекта».

Глава 1. Взаимосвязь моделей представления знаний в дисциплине «Основы искусственного интеллекта»

§ 1. Содержание дисциплины «Основы искусственного интеллекта» для педагогических специальностей

Современные направления исследований в области искусственного интеллекта.

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

Несмотря на свою краткость, история исследований и разработок систем искусственного интеллекта может быть разделена на 4 периода [14]:

60-е — начало 70-х годов XX века — исследования по «общему интеллекту», попытки смоделировать общие интеллектуальные процессы, свойственные человеку: свободный диалог, решение разнообразных задач, доказательство теорем, различные игры (шашки, шахматы и т. д.), сочинение стихов и музыки и т. д.;

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

с конца 70-х — разработка специализированных на определенных предметных областях интеллектуальных систем, имеющих прикладное практическое значение (экспертных систем);

90-е годы — фронтальные работы по созданию ЭВМ нового поколения, построенных на иных принципах, чем обычные универсальные ЭВМ, и программного обеспечения для них.

В настоящее время «искусственный интеллект» — мощная ветвь информатики, имеющая как фундаментальные, чисто научные основы, так и весьма развитые технические, прикладные аспекты, связанные с созданием и эксплуатацией работоспособных образцов интеллектуальных систем. Значение этих работ для развития информатики таково, что именно от их успеха зависит появление ЭВМ нового поколения. Именно этот качественный скачок возможностей компьютеров — обретение ими в полной мере интеллектуальных возможностей — положен целью развития вычислительной техники в ближайшей перспективе и является признаком компьютерной техники нового поколения.

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

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

Основные направления развития искусственного интеллекта [8]:

Представление знаний и разработка систем, основанных на знаниях.

Это основное направление искусственного интеллекта. Оно связано с разработкой моделей представления знаний, созданием баз знаний, образующих ядро экспертных систем. В последнее время включает в себя модели и методы извлечения и структурирования знаний и сливается с инженерией знаний.

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

Разработка естественно-языковых интерфейсов и машинный перевод.

Распознавание образов. Берет начало у самых истоков развития искусственного интеллекта. Это направление тесно связано с нейрокибернетикой.

Новые архитектуры компьютеров. Это направление занимается разработкой новых аппаратных решений и архитектур, направленных на обработку символьных и логических данных. Создаются Пролог-машины и Лисп-машины, компьютеры 5-го поколения.

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

Специальное программное обеспечение. В рамках этого направления разрабатываются специальные языки для решения задач невычислительного типа (LISP, PROLOG, РЕФАЛ). Помимо этого создаются пакеты прикладных программ, ориентированных на промышленную разработку интеллектуальных систем, или программные инструментарии искусственного интеллекта, например, KEE, ARTS.

Обучение и самообучение. Включает модели, методы и алгоритмы, ориентированные на автоматическое накопление знаний на основе анализа и обобщения данных. Включает обучение по примерам (или индуктивное), а также традиционные подходы распознавания образов.

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

Обзор образовательных стандартов педагогического образования в области искусственного интеллекта

Рассмотрим Федеральный государственный стандарт образования для специальности «информатика» и рабочие программы образовательных стандартов учебных дисциплин различных вузов.

Государственный образовательный стандарт высшего профессионального образования для педагогической специальности «информатика», Министерство Образования РФ

2) Рабочая программа учебной дисциплины «Основы искусственного интеллекта», Белгородский государственный университет, разработана доцентом Паком Д.Н.

Объем дисциплины и виды учебной работы:

Содержание дисциплины:

3) Рабочая программа учебной дисциплины «Программирование», модуль «Языки программирования искусственного интеллекта», Бийский педагогический государственный университет, разработан ст. преподавателем Дудышевой Е.В.

Лекции ИИ и области его применения. Программное обеспечение, предназначенное для решения задач ИИ. Типы знаний и методы их представления. Основные методы решения задач ИИ, их связь с методами программирования. Понятие парадигмы программирования, основные парадигмы.(2 часа) Основы программирования на языке Лисп (6 часов) Основы программирования на языке Пролог (6 часов) Принципы логического программирования. Основные понятия языка Пролог, его теоретические основы. Представление системы знаний в виде фактов и правил, организация запросов. Особенности программирования на Турбо-Прологе: структура программы, синтаксис правил и фактов. (2 часа) Различные подходы к программированию на Прологе. Организация выполнения программ: механизм перебора и возврата. Управление перебором с помощью «отсечения». Рекурсивная организация программ. Принудительный откат как рекурсивное средство повторения вычислений. (2 часа) Структуры данных языка Пролог, их реализация в Турбо-Прологе: составные объекты, множественные типы, списки. Механизм сопоставления. Базы данных: статистические, динамические, внешние. Предикаты Турбо-Пролога для работы с данными, стандартный предикат FINDALL. Шаблоны предикатов. (2 часа) Введение в экспертные системы.(2 часа) Семинарские занятия (18 часов).

На семинарских занятиях рассматриваются практические примеры программирования на языках Лисп и Пролог, а также простейшая реализация некоторых задач ИИ.

Лабораторные работы Знакомство со средой Турбо-Пролога. Задание фактов, нерекурсивных правил. Организация сложных запросов. (4 часа) Определение рекурсивных предикатов. Правила задания рекурсии с учетом процедурного смысла программ. (4 часа) Управления механизмами перебора и возврата, использование «отсечения». (2 часа) Структура данных на Прологе на примере задачи управления кадрами. (2 часа) Динамические базы данных, накопление фактов. (2 часа) Использование предиката FINDALL для преобразования баз данных в структуры данных. (2 часа) Мы видим, что в рамках данной дисциплины рассматриваются следующие темы: основные направления исследований в области искусственного интеллекта, система знаний и модели представления знаний, понятие об экспертной системе, общая характеристика экспертных систем, представление о логическом и функциональном программировании. В рассмотренных рабочих программах внимание акцентируется либо на общетеоретическом изложении технологии построения систем ИИ, либо чисто на практическом программировании. Заметим, однако, что эти разделы не противоречат друг другу и могут изучаться совместно.

Сравнительный анализ учебно-методической литературы по дисциплине «Основы искусственного интеллекта» .

Проведем обзорный анализ учебников и методических пособий для студентов педагогических вузов по общей информатике, рекомендованных Министерством образования и науки РФ. Мы не включили в обзор специальную литературу, которая рассматривает указанные вопросы достаточно глубоко, и может быть использована либо для инженерных дисциплин, либо для спецкурсов по практике построения систем искусственного интеллекта. Рассмотрим следующие учебные пособия:

А.В. Могилев, Н. И. Пак, Е. К. Хеннер «Информатика» [14]

" Информатика" под редакцией Н. В. Макаровой [8]

В.А. Каймин «Информатика» [10]

М.П. Лапчик, И. Г. Семакин, Е. К. Хеннер «Методика преподавания информатики» .

В учебнике А. В. Могилева и др. вопрос о системах искусственного интеллекта рассматривается в I главе § 12 «Понятие искусственного интеллекта». В первом пункте данного параграфа авторы показывают направления исследований и разработок в области систем искусственного интеллекта. Затрагивается и вопрос об истории исследований в этой области. Далее авторы описывают модели представления знаний в системах искусственного интеллекта, они выделяют три основные модели представления знаний:

продукционная модель;

формальная логическая модель;

семантические сети;

фреймы.

Каждому из этих понятий даны определения и приведены примеры. Далее авторы останавливаются на вопросе о моделировании рассуждений; формулируют основные определения логики предикатов 1-го порядка и рассматривают логическое правило вывода, используемое в моделирование рассуждений: метод резолюций.

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

В учебнике под редакцией профессора Н. В. Макаровой вопрос о системах искусственного интеллекта рассматривается в двух главах: главе 16 «Интеллектуальные системы» и главе 17 «Инженерия знаний».

Прежде всего, автор освещает вопрос об истории развития искусственного интеллекта за рубежом и в нашей стране, а далее излагает направления развития искусственного интеллекта.

В следующем параграфе автор дает определение данных и знаний, рассматривает различные классификации знаний. Далее даны четыре модели представления знаний в системах искусственного интеллекта:

продукционная модель;

семантические сети;

фреймы;

формальные логические модели.

Здесь также каждой из моделей даны определения и приведены примеры всех моделей представления знаний, кроме формальной логической модели.

В следующих двух параграфах данной главы авторы уделяют внимание экспертным системам и технологии их разработки.

В главе 17 данного учебника проводится обзор теоретических аспектов инженерии знаний. Авторы знакомят читателей и с некоторыми практическими методами работы инженеров по знаниям, в частности, с практическими методами извлечения знаний и структурировании знаний о предметной области.

В учебнике В. А. Каймина как таковые, проблемы искусственного интеллекта не рассматриваются, но достаточно полно разбираются технологии проектирования логических систем искусственного интеллекта. Вопрос об искусственном интеллекте затрагивается в пункте 3.3. В данном пункте рассмотрены общие вопросы, относящиеся и к системам искусственного интеллекта и к математической логике.

В главе 10 пункте последнего учебника очень кратко рассматривается вопрос о моделировании знаний в школьном курсе информатики. Автор затрагивает следующие вопросы: что такое база знаний, различные типы знаний, логическая модель знаний и язык Пролог. Дано определение базы знаний, кратко описана каждая из моделей представления знаний (семантические сети, фреймы, логическая модель, продукционная модель). Рассмотрен язык Пролог, как один из языков программирования для изучения в школе и даны ссылки на литературу, в которой можно подробнее познакомиться с данным языком программирования.

На основе анализа приведенных источников можно выделить следующие учебные темы образования в области искусственного интеллекта: «Направления исследования ИИ», «Модели представления знаний в системах ИИ», «Принципы построения программных систем ИИ», «Инженерия знаний», «Технологии и языки программирования ИИ».

Сводная таблица освещения тем в учебной литературе, рассмотренной ранее:

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

В специальной литературе, такой как Братко И. [1], Малпас Дж. [13], Хювёнен Э. [21], примеры построения систем ИИ, в частности, экспертных систем, рассматриваются подробно, но только после изложения конструкций самого языка, что не укладывается в рамки дисциплины «Основы искусственного интеллекта». К тому же специальная литература слишком сложна и объемна для изучения студентами рассматриваемой дисциплины.

Выше мы отметили, что логическое программирование (технологические средства) и способы построения систем ИИ (технология разработки) дополняют друг друга и, в принципе, могут изучаться вместе. Таким образом, необходимо подобрать такие дидактические средства, которые позволят реализовать данную дидактическую задачу.

§ 2. Логическое программирование как технология реализации логической модели представления знаний

Модели представления знаний в системах искусственного интеллекта.

Основной особенностью интеллектуальных систем является то что, они основаны на знаниях, а вернее, на некотором их представлении. Знания — это выявленные закономерности предметной области (принципы, связи, законы), позволяющие решать прикладные задачи в этой области.

При обработке на ЭВМ знания трансформируются, условно проходя следующие этапы:

знания в памяти человека как результат мышления;

материальные носители знаний (учебники, методические рекомендации);

поле знаний — условное описание основных объектов предметной области, их атрибутов и закономерностей, их связывающих;

знания, описанные на языках представления знаний;

базы знаний.

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

В настоящее время наиболее известны четыре подхода к представлению знаний в обсуждаемых системах:

продукционные модели;

семантические сети;

фреймы;

формальные логические модели.

Продукционная модель основана на представлении знаний в форме правил, структурированных в соответствии с образцом «ЕСЛИ — ТО». Часть правила «ЕСЛИ» называется условие, а «ТО» — выводом или действием. Под условием понимается некоторое предложение-образец, по которому осуществляется поиск в базе знаний, а под действием — действия, выполняемые при успешном исходе поиска. Правило в общем виде записывается так:

ЕСЛИ А1, А2, …, Аn ТО В.

Такая запись означает, что «если все условия от А1 до Аn являются истинными, то В также истинно» или «когда все условия от А1 до Аn выполняются, то следует выполнить действие В». В случае n=0 продукция описывает знание, состоящее только из вывода, т. е. факт. Переменные в правиле показывают, что правило содержит некое универсальное общее знание, абстрагированное от конкретных значений переменных. Одна и та же переменная, использованная в выводе и различных посылках, может получать различные конкретные значения. При использовании продукционной модели база знаний состоит из набора правил. В интеллектуальную систему входит также механизм выводов, который позволяет на основе знаний, имеющихся в базе знаний, получать новые знания.

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

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

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

По количеству типов отношений:

однородные (с единственным типом отношений);

неоднородные (с различными типами отношений).

По типам отношений бинарные;

n-арные.

Наиболее часто в семантических сетях используются следующие отношения:

связи типа «часть-целое» («класс-подкласс», «элемент-множество» и т. д.);

функциональные связи;

количественные (больше, меньше, равно …);

пространственные (далеко от, близко от, под, над …);

временные;

атрибутивные связи (иметь свойство, иметь значение …);

логические связи (и, или, не) и др.

Ниже приведен пример части семантической сети.

Основное преимущество этой модели — в соответствии с современным представлениям об организации долговременной памяти человека. Недостаток модели — сложность поиска вывода на семантической сети.

Фреймовая система имеет все свойства, присущие языку представления знаний, и одновременно являет собой новый способ обработки информации. Слово «фрейм» в переводе с английского языка означает «рамка». Фрейм является единицей представления знаний об объекте, которую можно описать некоторой совокупностью понятий и сущностей. Фрейм имеет определенную внутреннюю структуру, состоящую из множества элементов, называемых слотами. Каждый слот в свою очередь, представляется определенной структурой данных, процедурой, или может быть связан с другим фреймом. Приведем пример фрейма: человек [14]

Фрейм: человек Класс: Животное Структурный элемент: Голова, шея, руки, ноги, …

Рост: 30 — 220 см Масса: 1 — 200 кг Хвост: Нет Фрейм аналогии: Обезьяна Основным преимуществом фреймов как модели представления знаний является способность отображать концептуальную основу организации памяти человека, а также ее гибкость и наглядность.

Традиционно в преставлении знаний выделяют формальные логические модели, основанные на классическом исчислении предикатов 1-го порядка, когда предметная область или задача описывается в виде аксиом.

Существуют и другие, менее распространенные подходы к представлению знаний в интеллектуальных системах, в том числе гибридные, на основе уже описанных подходов.

Перечислим главные особенности машинного представления данных.

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

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

Связность. Должна быть предусмотрена возможность установления связей различного типа между информационными единицами, которые бы характеризовали отношения между информационными единицами. Эти отношения могут быть как декларированными (описательными), так и процедурными (функциональными).

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

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

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

Логическая модель представления знаний.

В предыдущем пункте выделены формальные логические модели представления знаний, которые преимущественно основаны на классическом исчислении предикатов 1-го порядка.

Начало исследованиям в области формальной логики было положено работами Аристотеля в IV в. до н.э. Логика предикатов — это универсальный абстрактный язык предназначенный для представления знаний и для решения задач. Его можно рассматривать как общую теорию отношений. Терминология логики предикатов включает следующие понятия: рассуждение, предикат, термы, литерал, метод резолюций.

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

Предикат — это конструкция вида P (t1, t2, …, tn) выражающая какую-то связь между некоторыми объектами или свойствами объектов. Обозначение этой связи или свойства, P, называют «предикатным символом»; t1, t2, …, tn обозначают объекты, связанные свойством (предикатом) P, и называют термами.

Термы могут быть только трех следующих типов:

константа (обозначает индивидуальный объект или понятие);

переменная (обозначает в разное время различные объекты);

составной терм — функция f (t1, t2, …, tm), имеющая в качестве своих аргументов m термов t1, t2, …, tm.

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

Предикаты могут быть объединены в формулы с помощью логических связок: ^ («и», конъюнкция), V («или», дизъюнкция), («не», отрицание), («следует», импликация), («тогда, и только тогда, когда «, эквиваленция).

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

Математически строго формулы логики предикатов определяются рекурсивно:

предикат есть формула;

если, А и В — формулы, то А, А^В, АVВ, АВ, АВ — тоже формулы;

других формул не бывает.

Истинность связок предикатов (И — истина, Л — ложь)

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

Из всевозможных формул нам потребуется только один их вид, называемый фразами Хорна. Фразы Хорна содержат в общем случае импликацию и конъюнкцию предикатов А, В1, В2,…, Вn следующим образом: В1 В2 … Вn> А, или в более удобных обозначениях:

А: — В1, В2, …, Вn.

Очевидно, фраза Хорна является формой записи некоего правила, и в дальнейшем и будет называться правилом. Предикат, А называется заголовком или головой правила, а предикаты В1, В2, …, Вn — его подцелями.

Отдельный предикат является частным случаем фразы Хорна: А.

Другой частный случай фразы Хорна — правило без головы

: — В1, В2, …, Вn, или : — В.

Такая фраза Хорна называется вопросом.

Поясним логический смысл такой формулы. Импликация А: — В (А>В) может быть выражена через отрицание и дизъюнкцию: ВVА. Значит, если отбросить А, останется только В — отрицание В.

Множество фраз Хорна применительно к некоторой проблемной области образует теорию (в логическом смысле).

Для выполнения логического вывода используют правила вывода, называемые методом резолюций.

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

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

Рассмотрим две фразы:

P (a) (1)

~ P (a) (2)

Фраза (1) — это заключение без условий, а фраза (2) — это условие без заключения. Присутствие фраз (1) и (2) в одной теории является противоречием. Если фразы (1) и (2) резольвируются друг с другом, то получающаяся резольвента называется пустой фразой. Если при резолюции двух фраз, входящих в теории, получается пустая фраза, то эта теория должна быть непоследовательной.

При использовании правила резолюции применима более чем одна стратегия решения задач. Рассмотрим нисходящую (обратную) стратегию. В этой стратегии ставится цель обнаружить, является ли единственная фраза С следствием существующего множества фраз Т. Предполагается, что множество фраз Т является непротиворечивым. Алгоритм работает следующим образом. Вначале к существующему множеству фраз добавляется отрицание проверяемой фразы ~С. При этом образуется новое множество фраз Т', состоящее из множества Т плюс фраза ~C. Если алгоритм позволит вывести пустую фразу из Т', то Т' будет непоследовательной из-за присутствия фразы ~C, и поэтому С должно являться следствием Т.

Изложенные положения логики предикатов находят реализацию и дальнейшее развитие в логическом программировании.

Логическое программирование.

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

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

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

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

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

Таким образом, логическое программирование, во-первых, предоставляет реальный механизм для автоматизации обработки моделей знаний, а во-вторых, использует декларативный (описательный) стиль программирования, описания программы в терминах, близких предметной области задачи. Однако при изучении логического программирования для практического решения задач ИИ необходимо владение математическим аппаратом. В условиях недостаточной практики использования языка математической логики для многих студентов формулировка задач представляет трудность на начальном этапе обучения языку логического программирования. Поэтому в литературе (Братко И., Малпас Дж.) решения многих задач объясняются и иллюстрируются с помощью других формальных средств, в частности, сетей и графов. Нередко и в практической разработке систем ИИ для представления предметной области используются сетевые модели — это один из методов, применяемых в инженерии знаний.

§ 3. Применение семантических сетей для описания представления знаний

Построение модели предметной области в виде семантических сетей.

Построение формальной модели предметной области в большинстве случаев является непростой задачей. При построении формальной модели, как правило, используют два принципа: дедуктивный (от общего к частному) и индуктивный (от частного к общему). При дедуктивном подходе рассматривается частный случай общеизвестной фундаментальной модели. Здесь при заданных предположениях известная модель приспосабливается к условиям моделируемого объекта. Индуктивный способ предполагает выдвижение гипотезы, декомпозицию сложного объекта, анализ, затем синтез.

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

Для построения предметной области в виде семантической сети рассматриваются основные объекты-сущности данной предметной области и отношения между ними. Первоначально выделяют основные понятия и категории, которыми оперируют (которыми выражаются) фрагменты предметной области. Данные понятия и категории принимаются за первоначальную основу списка объектов-сущностей предметной области. Далее на основе анализа формируются атрибуты, характеризующие выраженные объекты-сущности. При определении перечня атрибутов каждого объекта предметной области, как и самого перечня объектов-сущностей, руководствуются соображениями минимальной достаточности. Часть атрибутов и понятий предметной области выражают процессы-отношения между объектами-сущностями. Такие атрибуты выделяются, и далее анализируются параметры характер связей, которые они выражают — структурность, направленность, множественность, обязательность наличия экземпляров объектов. Чаще всего выделение объектов-сущностей, их атрибутов и отношений-связей осуществляется комбинированным способом на итерационной основе, с многократным уточнением исходного списка объектов, соединением атрибутов в группы и т. д. Распространенным приемом в этом случае является «обобщение» некоторых понятий и атрибутов. Суть обобщения заключается в объединении в одну сущность близких или однотипных понятий, категорий, атрибутов на основе анализа частных проявлений и вариантов.

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

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

В качестве примера можно привести часть семантической сети, относящейся к понятию «птица» (рис. 2).

семантический сеть пролог предметный

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

С точки зрения структуры, сети являются расширением понятия графа. В информатике под графом понимается конечное множество вершин, соединенных ребрами. В теории графов данное понятие трактуется следующим образом: рассмотрим множество V, состоящее из соединенных некоторым образом точек. Назовем V множеством вершин и элементы vV — вершинами. Граф G=G (V, Е) (1) с множеством вершин V есть некоторое семейство сочетаний или пар вида E=(a, b), a, b V (2), указывающее, какие вершины считаются соединенными.

Число вершин графа G обозначим p, а число ребер — q.

В соответствии с геометрическим представлением графа каждая конкретная пара (2) называется ребром графа; вершины, а и b называются концевыми точками или граничными точками ребра Е.

В определении ребра (2) можно принимать или не принимать во внимание порядок расположения 2-х его концов. Если этот порядок не существенен, то есть если E=(a, b)=(b, a), то говорят, что Е есть неориентированное ребро, если же порядок существенен, то Е называется ориентированным ребром или дугой. В последнем случае, а называется начальной вершиной, а b — конечной вершиной ребра. Также говорят, что Е ребро, выходящее из вершины, а и входящее в вершину b. Как в случае ориентированного, так и в случае неориентированного ребра говорят, что ребро Е инцидентно вершинам, а и b, а также что, а и b инцидентны Е. На рисунке 3 изображено неориентированное ребро (a, b) и ориентированное ребро (c, d). Количество ребер, инцидентных вершине v, называется степенью вершины v и обозначается d (v).

Если элементом множества Е является пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).

Пусть G — неориентированный граф.

Маршрутом в G называется такая конечная последовательность ребер (3) что каждые два соседних ребра и имеют общую концевую точку. Отметим, что одно и то же ребро Е может встречаться в маршруте несколько раз.

Если в маршруте (3) нет ребер, предшествующих, то называется начальной вершиной S, а если нет ребер, следующих за, то называется конечной вершиной S. Любая вершина, принадлежащая двум соседним ребрам и, называется внутренней. Так как ребра и вершины в маршруте могут повторяться, внутренняя вершина может также начальной или конечной вершиной.

Если маршрут S имеет как начальную вершину, так и конечную вершину, то можно написать (4) и называть и концевыми точками. S — есть маршрут длины n, соединяющий соответствующие вершины. Если, то маршрут называется циклическим.

Маршрут называется цепью, если каждое его ребро встречается в нем не более одного раза (вершины в цепи могут повторяться). Любой участок цепи есть цепь. Нециклическая цепь называется простой цепью, если в ней никакая вершина не повторяется. Ориентированная цепь называется путем.

Циклический маршрут называется циклом, если каждое ребро в нем встречается в нем не более одного раза. Цикл с концом называется простым циклом, если не является в нем промежуточной вершиной и никакие другие вершины не повторяются.

Пусть граф G неориентированный. Две вершины a и b называются связными, если существует маршрут вида (3) с концами a и b. Граф называется связным, если любая пара вершин связана.

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

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

Не уменьшая общности рассуждений, мы можем рассматривать однородные семантические сети — те, в которых всем ребрам соответствует одно и то же отношение, т. е. одна и та же семантическая функция.

Гамильтонов цикл в однородных семантических сетях

Рассмотрим задачу теории графов на нахождение гамильтонова цикла в заданном фрагменте графа (сети).

Гамильтоновой цепью в графе называется простая цепь, проходящая через все вершины по одному разу (см. рис).

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

Теорема (Дирак): Если в графе G (V, E) vV d (v)p/2, то граф G является гамильтоновым.

Рассмотрим классическую задачу теории графов на нахождение гамильтонова цикла — задачу коммивояжера. Она звучит следующим образом: Имеется n городов, расстояния между которыми известны. Коммивояжер должен посетить все n городов по одному разу, вернувшись в тот с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным. Математическая постановка этой задачи состоит в следующем: во взвешенном графе требуется найти гамильтонов цикл наименьшего веса. Данная задача является NP — полной; для нее не существует эффективного алгоритма. Важность этой задачи связана с тем, что к ней сводятся многие другие задачи; в связи, с чем она играет роль эталонной задачи.

В данной задаче города, представляя как вершины графа G, в котором каждой паре вершин приписывается расстояние m (a, b). Тогда задача состоит в том, чтобы найти такой гамильтонов цикл P, для которого сумма минимальна.

Проследим ход решения задачи коммивояжера.

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

Вершина u в орграфе G (V, E) достижима из вершины v, если существует путь из v в u.

Тогда отношение достижимости на взвешенном графе G (V, E) будет транзитивным замыканием E1 на V бинарного отношения E.

Построить транзитивное замыкание можно следующим образом: отношения со смежными вершинами принадлежат транзитивному замыканию E1; все отношения с вершинами, достижимыми из смежных вершин, тоже принадлежат замыканию.

На языке математической логики это выглядит следующим образом:

где I — тождественное отношение.

Введенное таким образом бинарное отношение E1 определяет новую однородную семантическую сеть S1(V, E1, W) с тем же множеством вершин. Заметим, что если граф исходной сети имеет одну компоненту связности, то граф полученной сети будет полным и не будет содержать кратных ребер. Соответствующий граф для данной сети — G1 (см. рис.).

Следующим шагом мы каждому дуге полученного графа G1(V, E1) приписываем множество, состоящее из множеств вершин, пройденных по пути в исходной сети от одной смежной ребру вершины до другой. Обозначим построенное отношение D, DE2V.