СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

Некоммерческое  акционерное общество

АЛМАТИНСКИЙ УНИВЕРСИТЕТ  ЭНЕРГЕТИКИ И СВЯЗИ

Кафедра Компьютерных Технологий

 

СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

 Конспекты лекций

для студентов - бакалавров специальности

5В070400 - Вычислительная техника и программное обеспечение

 

Алматы 2013

СОСТАВИТЕЛИ: Ахметова М. Системы Искусственного Интеллекта. Конспекты лекций для студентов - бакалавров специальности 5В070400 - Вычислительная техника и программное обеспечение,  - Алматы: АУЭС, 2013 -  67 с.

 

Конспекты лекций содержат теоретические материалы по системам искусственного интеллекта и языков функционального и логического программирования ЛИСП и ПРОЛОГ. 

Рекомендуется для студентов-бакалавров всех форм обучения по специальности 5В070400 - Вычислительная техника и программное обеспечение.

Ил. 9, табл 6., библиогр. -  25 назв.

 

Рецензент:  канд.техн.наук, проф.  Ибраева Л.К.

 

Печатается по плану издания некоммерческого акционерного общества «Алматинский университет энергетики и связи» на 2012 г.

 

© НАО «Алматинский университет энергетики и связи», 2013 г.

 

Введение

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

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

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

 

Лекция 1.  Языки Искусственного Интеллекта. Основы логического программирования

 

Цель лекций. Ознакомление с основными принципами логического программирования.

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

Многие виды деятельности человека такие, как решение головоломок, участие в играх, решения математических задач и даже вождение автомобиля требуют, как это принято считать, участия «интеллекта». Если бы вычислительные машины могли справляться с деятельностью такого типа, то они, вероятно, обладали бы в какой-то степени  искусственным интеллектом. Решение задач может показаться весьма неясным предметом, однако на нем концентрируется большая доля исследований по искусственному интеллекту. В самом широком смысле этих слов нахождение решений включает в себя всю вычислительную науку, поскольку всякая вычислительная задача может рассматриваться как задача, решение которой надо найти. Однако для наших целей нужно более узкое определение, которое исключает такие стандартные вычислительные методы, как методы, используемые, скажем, при обращении матрицы 50-го порядка или при решении системы линейных дифференциальных уравнений. Если мы внимательно рассмотрим методы нахождения решений, изучаемые в исследованиях по искусственному интеллекту, то обнаружим, что в большинстве из них используется понятие поиска путем проб и ошибок. Это значит, что в этих методах задачи решаются посредством поиска решения в пространстве возможных решений. Наша цель состоит в разъяснении наиболее важных методов решения задач с использованием процедур поиска.

Для описания интеллектуальных систем выделяется два уровня: знаний и символов. Искусственный интеллект сформировался как отдельная область знаний и продемонстрировал свою применимость для решения многих практических задач на основе языков ЛИСП и ПРОЛОГ. Однако в последнее время удельный вес этих языков при решении задач искусственного интеллекта несколько снизился. Это объясняется требованиями к разработке программных систем. Системы искусственного интеллекта зачастую служат модулями других больших приложений, поэтому стандарты разработки приводят к необходимости использования единого языка программирования всего приложения. Современные системы искусственного интеллекта реализуют на многих языках, включая Smalltalk, С, С++ и Java. Несмотря на это ЛИСП и ПРОЛОГ продолжают играть свою роль в разработке прототипов программ и новых методов решения задач. Кроме того, эти языки служат для обоснования многих средств, которые впоследствии включаются в современные языки программирования. Наиболее ярким примером является язык Java, в котором используются динамическое связывание, автоматическое управление памятью и другие средства, впервые реализованные в языках программирования задач искусственного интеллекта. Создается впечатление, что весь остальной мир программирования до сих пор пытается перенять стандарты от языков реализации искусственного интеллекта. С этой точки зрения ценность ЛИСП, ПРОЛОГ или Smalltalk со временем будет неуклонно повышаться. Эти языки пригодятся, даже если впоследствии он найдет свое место в С++, Java или любом другом конкурирующем языке.

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

Языки искусственного интеллекта (ИИ) основаны на языках функционального и логического программирования с ориентацией на декларативный стиль программирования на базе языков ЛИСП и ПРОЛОГ. Изучение языков ИИ дает возможность понимать смысл декларативного стиля программирования. В данном стиле программирования большое внимание уделяется вопросам описания ситуаций, программирование осуществляется в терминах целей, при этом задача формулируется с определения ситуаций, затем во всех деталях описывается «как» решить эту задачу, а не указанию «что» делать как в традиционных способах программирования. Хороший стиль программирования предполагает разделение конкретных свойств языка программирования и уровней программирования. Специфика задач искусственного интеллекта требует их глубокой взаимосвязи. Структура языка должна удовлетворять нижним уровням компьютерной архитектуры, включая операционную систему, архитектуру аппаратных средств, объем памяти и быстродействие процессора. Этим и объясняется их популярность при решении задач искусственного интеллекта. Искусственный интеллект сформировался как отдельная область знаний и продемонстрировал свою применимость для решения многих практических задач на основе языка ПРОЛОГ. Однако в последнее время удельный вес этих языков при решении задач искусственного интеллекта несколько снизился. Это объясняется требованиями к разработке программных систем. Системы искусственного интеллекта зачастую служат модулями других больших приложений, поэтому стандарты разработки приводят к необходимости использования единого языка программирования всего приложения. Кроме того, эти языки служат для обоснования многих средств, которые впоследствии включаются в современные языки программирования. Первая ПРОЛОГ-программа была написана в начале 1970-х годов во Франции в рамках проекта по пониманию естественного языка.  Преимущества этого языка были продемонстрированы при разработке исследовательских проектов, призванных оценить и повысить выразительность логического программирования [1,2]. В отличие от него, процедурный стиль программирования предполагает написание программы в виде последовательности инструкций по выполнению алгоритма. Развитие языка ПРОЛОГ уходит корнями в исследования, связанные с доказательством теорем, а точнее, с разработкой алгоритмов опровержения резолюции. Процедура доказательства, получившая название резолюции (resolution), стала основным методом вычислений на языке ПРОЛОГ.  Благодаря этим свойствам ПРОЛОГ зарекомендовал себя в качестве полезного средства исследования таких экспериментальных вопросов программирования, как автоматическая генерация кода, верификация программ и разработка высокоуровневых языков программирования. Несмотря на существование многочисленных диалектов языка ПРОЛОГ, обычно используется исходная версия языка, разработанная Уорреном и Перейрой. Однако существуют многочисленные отличия синтаксиса логики предикатов от языка ПРОЛОГ [3,4].

Существуют различные средства поддержки разработки программ. Транс­ляторы  языков  программирования  и отладчики были в числе первых таких средств. Отладчи­ки  наряду с экранными редакторами и в настоящее время остаются наиболее часто используемыми средствами. Системы,  Turbo-ПРОЛОГ,  ЛИСП позволяют программисту запустить программу сразу после ввода ее в систему. В ответ на ошибку системой вызывается отладчик,  чтобы дать возможность програм­мисту изучить причину сбоя.  Программист  может  затем  отредактировать программу и продолжить ее выполнение.  Этот подход сокращает время на ис­правление мелких ошибок в программе для экспериментального программиро­вания, обычно применяемого специалистами по ис­кусственному интеллекту. Проектирование больших программных средств является сложной пробле­мой,  разбиение жизненного цикла на несколько этапов таких как анализ требований, спецификации, проектирование, реализация, тестирование и отладка, работа и сопровождение,  направлено на уменьшение сложности проектирования путем изолирования и упорядочения важных задач в процессе разработки. ЛИСП, Турбо-ПРОЛОГ поддерживают только  этапы  реализации  и отладки.  Исследования показывают, что наибольший вклад в стоимость жиз­ненного цикла дает этап сопровождения.  Успех методов искусственного интеллекта в различных областях  моти­вировал их применение в разработке программного обеспечения. Показатель­ными системами являются проект «Помощник программиста» в Массачусетском технологическом институте,  проект «Пси» в Станфордского университета,  в этих проектах осуществляется попытка моделировать знания, которыми поль­зуется программист для понимания, проектирования, реализации и сопровож­дения программы. Эти знания могут быть использованы экспертными система­ми для частичной автоматизации процесса разработки программ.

 

Лекция 2. Языки Искусственного Интеллекта. Работа в ПРОЛОГе.

 

Цель лекций. Ознакомление основными возможностями работы на ПРОЛОГе,  статические, динамические базы данных на ПРОЛОГе.

Содержание лекций. Преимущества языка ПРОЛОГ. Представление переменных в ПРОЛОГе. Структуры данных. Разделы и списки ПРОЛОГа. Механизм управления. Оператор отсечения.

ПРОЛОГ - это наиболее известный пример языка логического программирования. При выполнении программы интерпретатор постоянно реализует вывод на основе логических спецификаций. Идея использования возможностей теории предикатов первого порядка - это одно из основных преимуществ языка ПРОЛОГ. В ПРОЛОГе имена предикатов и связанных переменных представляют собой последовательности буквенно-цифровых символов, которые начинаются с буквы. Переменные представляются в виде строк буквенно-цифровых символов, которые начинаются с прописной буквы. Так, выражение likes (X, Asem)  или likes (Anuar, Asem) может представлять тот факт, что «каждый любит Асем» или «Ануар любит Асем», likes(Danjar, Y), likes(Asem, Y)  представляет множество людей, которых любят Данияр и Асем. Допустим, на языке ПРОЛОГ необходимо представить следующее отношение: «Данияр любит Райхан и Данияр любит Асем». Его можно записать в виде likes(Danjar, Raihan), likes(Danjar, Asem). А отношения, связанные через «или», например, «Данияр любит Райхан или Данияр любит Асем», можно представить так: likes(Danjar, Raihan); likes(Danjar, Asem).

Программа на языке ПРОЛОГ- это набор спецификаций из логики предикатов первого порядка, описывающих объекты и отношения между ними в предметной области задачи. Интерпретатор языка отвечает на вопросы, касающиеся этого набора спецификаций. Запросы к базе данных - это шаблоны, представленные в том же логическом синтаксисе, что и записи базы данных. Интерпретатор обрабатывает запросы, выполняя поиск в базе данных в глубину слева направо и определяя, является ли данный запрос логическим следствием спецификаций из базы данных. ПРОЛОГ также позволяет определять правила, описывающие взаимосвязи между фактами с использованием знака логической импликации: «: — ».  При создании правила на языке ПРОЛОГ слева от символа «: — » может располагаться только один предикат. Этот предикат должен быть положительным литералом, он не должен представлять собой символ с отрицанием.

Любая программа, написанная на Турбо-ПРОЛОГе, состоит из пяти разделов. Ключевые слова: domains, database, predicates, goal, clauses -отмечают начала соответствующих разделов.  Большинство программ не содержит всех пяти названных разделов. Турбо-ПРОЛОГ обеспечивает возможность включения в любом месте программы комментариев любой длины, которые обрамляются символами /* и */ [1,14]. При написании программ важно соблюдать следующие правила: имена всех отношений и объектов записываются со строчной  буквы; сначала записывается имя отношения (предиката). Затем через запятую записываются имена объектов, а весь список имен объектов заключается в круглые скобки; каждый факт, цель должны заканчиваться знаком: «.» -  точкой [5].

Выполнение программы начинается, когда система встретит оператор цели. Цель – это формулировка задачи, которую данная программа должна решить. Турбо-ПРОЛОГ использует как внутренние цели, которые содержатся в программе, так и внешние цели, которые вводятся с клавиатуры после запуска программы. В этом случае Турбо-ПРОЛОГ выдает приглашение Goal (Цель). Турбо-ПРОЛОГ пытается сопоставить цель с фактами и правилами программы. Принцип сопоставления, который необходимо твердо усвоить – сверху вниз и слева направо. Если цель является фактом, то Турбо-ПРОЛОГ отвечает True (Истина) или False (Ложь) или No. Если цель содержит переменные, то Турбо-ПРОЛОГ выполняет либо те их значения, которые приводят к решению, если оно существует, либо выдает сообщение No solutions (решений нет). Последующие ответы на запрос выдаются после приглашения ПРОЛОГа. При этом происходит возврат к последнему найденному результату. Последовательные приглашения приводят к нахождению всех возможных ответов на запрос. Приведенные выше примеры также иллюстрируют допущение замкнутости мира  или отрицание как ложь.

В языке ПРОЛОГ предполагается, что любое выражение является ложным, если нельзя доказать истинность его отрицания. При обработке запроса likes (Danjar, beer) интерпретатор ищет предикат likes (Danjar, beer) или некоторое правило для получения likes (Danjar, beer). Поскольку поиск не завершается успехом, запрос считается ложным. Таким образом, в языке ПРОЛОГ предполагается, что все знания о мире представлены в базе данных. Допущение замкнутости мира приводит к многочисленным практическим и философским сложностям в языке. Например, невозможность включить некоторый факт в базу данных зачастую означает, что его истинность неизвестна. Однако в силу допущения замкнутости мира этот факт трактуется как ложный. Аспект трактовки отрицания как лжи — очень важный вопрос в области искусственного интеллекта. Хотя это предположение обеспечивает простой способ решения проблемы незаданных знаний, более сложные подходы, в том числе многозначные логики (истина, ложь, неизвестно) и немонотонные рассуждения обеспечивают гораздо более богатый контекст для интерпретации. Логика хорновских дизъюнктов (Horn clause calculus) эквивалентна полной теории предикатов первого порядка, применяемой для доказательств на основе опровержения.

Допустим, к спецификациям приведенной выше базы данных требуется добавить правило, определяющее двух друзей.  Его можно описать следующим образом:  friends (X, Y): —  likes (Х, Z), likes (Y, Z). Это выражение можно интерпретировать так: «Х и У — друзья, если существует такое Z, что Х любит Z и У любит Z». Здесь важно отметить два момента. Во-первых, поскольку ни в логике предикатов, ни в самом языке ПРОЛОГ не определены глобальные переменные, то шкала переменных Х, У и Z ограничена правилом friends. Во-вторых, переменные, унифицируемые или связываемые с Х, У и Z, должны быть сопоставлены  по всему выражению. Обработку правила friends интерпретатором языка можно проиллюстрировать на следующем примере: к набору спецификаций из предыдущего примера добавим правило friends(Danjar, Asem). Затем интерпретатору можно передать запрос.

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

 В Турбо-ПРОЛОГе имеется набор встроенных предикатов для изменения фактов динамической базы:

asserta (X) - добавляет факт в начало базы данных;

assertz (X) - добавляет факт в конец базы данных;

retract (X) - удаляет из базы данных факт, сопоставимый с заданным фактом;

consult(имя файла) - открывает файл для добавления фактов в базу данных, размещенную в оперативной памяти [6].

Основным механизмом управления при программировании на языке ПРОЛОГ является рекурсия. Однако сначала рассмотрим несколько несложных примеров обработки списков. Список - это структура данных, представляющая собой упорядоченный набор элементов. Рекурсия — это естественный способ обработки списочных структур. Для обработки списков в языке ПРОЛОГ используют процедуры унификации и рекурсии. Сами элементы списков заключаются в квадратные скобки ( [] ) и отделяются друг от друга запятыми. Приведем несколько примеров списка.  [1, 2, 3, 4] , [[Danjar, Asem], [allen, janna], [doni, targil]],  [tom, aman, sergan, dos], [[ ]. Первый элемент списка может отделяться от его хвоста оператором ~. Хвост списка - это список после удаления первого элемента. Например, для списка [tom, aman, sergan, dos] первым элементом является -  tom,  а хвостом - список [aman, sergan, dos]. С помощью оператора «~» и процедуры унификации можно разделить список на компоненты. Помимо разбиения списка на отдельные элементы, унификацию можно использовать для построения списочной структуры. Например, если Х = tom, Y = [aman] и L унифицируется с [Х ~ Y], то переменная L будет связана со списком [tom, aman]. Термы, отделенные друг от друга запятыми и расположенные до вертикальной черты, являются элементами списка, а находящаяся после вертикальной черты структура всегда является списком, а точнее, его хвостом.

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

?- member (а [а b с d, е] ) Yes

?- member(a, [1, 2, 3, 4]) No.

Хороший стиль программирования на языке ПРОЛОГ предполагает использование анонимных переменных. Они служат для указания программисту и интерпретатору того, что определенные переменные используются исключительно для проверки соответствия шаблону, т.е. само связывание переменных не является частью процесса вычислений. Так, чтобы проверить, совпадает ли элемент Х с первым элементом списка, обычно используют запись member (Х, [Х/_]). Символ «/» означает, что несмотря на важное значение хвоста списка в процессе унификации запроса, содержимое хвоста не играет роли. Анонимные переменные необходимо также использовать в рекурсивном утверждении при проверке наличия элемента в списке, если значение головы списка не играет роли. Хорошим упражнением для углубления понимания природы списков и рекурсивного управления является запись элементов списка по одному в строке.

Оператор отсечения (cut) представляется символом «!» и указывается в качестве целевого утверждения без аргументов. При этом его применение имеет несколько побочных эффектов. Во-первых, этот оператор всегда выполняется при его первом достижении, а во-вторых, если при возврате оказывается невозможным вернуться к предыдущему состоянию, то все целевое утверждение, в котором содержится этот оператор, считается ложным. Оператор отсечения в программировании используется для нескольких целей. Во-первых, он позволяет программисту явно управлять формой дерева поиска. Если дальнейший поиск не требуется, то в этой точке можно выполнить явное усечение дерева. При этом код на языке ПРОЛОГ напоминает вызов функций: если предикат ПРОЛОГ "возвращает" одно множество значений и достигается оператор отсечения, то интерпретатор не выполняет поиск для других подстановок унификации. Если это множество значений не приводит к решению, то поиск решения не продолжается. Во-вторых, оператор отсечения позволяет управлять рекурсией. Важным побочным эффектом использования оператора отсечения является ускорение работы программы и экономия памяти. Если этот оператор использован внутри предиката, то указатели в памяти, необходимые для возврата к предикатам, расположенным слева от оператора отсечения, не создаются. Дело в том, что они никогда не понадобятся. Таким образом, применение оператора отсечения приводит к нахождению желаемого решения только при более эффективном использовании памяти. Оператор отсечения также можно использовать при реализации рекурсии для повторной инициализации вызова path и продолжения поиска на графе. Для реализации этого алгоритма нам также понадобится разработать несколько абстрактных типов данных. Эффективность программирования в любой среде можно повысить за счет сокрытия информации и введения процедурных абстракций. Поскольку в алгоритмах поиска на графе,  используются такие структуры данных, как множество (set), стек (stack), очередь (queue) и приоритетная очередь (priority 'queue),  логично ввести их в языке ПРОЛОГ.

 

Лекция 3. Языки искусственного интеллекта. Основы функционального программирования

 

Цель лекций. Основные принципы функционального программирования, история и языки функционального программирования.

Содержание лекций. Лямбда-исчисление. Разные стратегии вычислений. Виды вычислений и примеры на ЛИСПе. Префиксная и инфиксная запись. Типы функций. История функционального программирования. Возможности функционального программирования.

1934 г. А. Черч применил лямбда- исчисление для теории множеств. Лямбда-исчисление это язык для формализации функций. В математике функция определяется как:  f(x) = a +bx  и содержит три компонента:  fидентификатор функции, список аргументов - (x), и правую часть - выражение. А.Чёрч записал функцию в следующем виде: f = λx.a + bx. Здесь символ «λ» понимается как значение идентификатора. Он приписывает идентификатору  f  функциональное значение представляемое лямбда-выражением. Например, (λx. x^2 + 3)5.  Если лямбда-выражение выступает в качестве оператора, то: 5^2 + 3=28. То же получим, если бы вычисляли  f(5), где  f = λx. x^2 + 3 или  f x= x^2 + 3. Большинство современных языков функционального программирования (ФП) полностью основаны на лямбда-исчислении. Объясняется это следующими причинами:

1) лямбда-исчисление позволяет найти смысл рекурсивного определения функции, понимаемого как математическое равенство, тем самым задавая декларативную семантику языков ФП;

2) лямбда-исчисление с помощью различных вариантов механизма редукции позволяет моделировать шаги вычисления любого интерпретатора функционального языка. С помощью него можно обосновать корректность механизмов вызова функции таких, как «вызов по имени», «вызов по значению» («строгие вычисления»), а также  «вызов по необходимости» («ленивые вычисления»). Приведем примеры этих вычислений на языке ЛИСП. Это показано в таблице 1.  

Значением механизмов «вызов по имени», «вызов по значению» является имя определяемой функий. Значение механизма «вызов по необходимости» («ленивые вычисления») является отложенные вычисления.

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

Виды вычислений и примеры на ЛИСПе

Таблица 1

Строгие вычисления

Ленивые вычисления

Вычисление степени

(defun st(x n)

 (do ((res 1))

   ((= n 0) res)

   (setq res (* res x))

     (setq n (- n 1))))

;;вызов по имени

> (st 3 3)

27

Операций над списками

 > (car (a b c))

A

> (cdr (a b c))

(B C)

> (cons(‘a ‘(b c))

(A B C)

> (cons(‘(a b) ‘(c d))

((A B) C D)

Разбей и переверни список

(defun razbei(l)

   (cond((null) nil)

     ((null (cdr l)) l)

(t (list (razbei (cdr l))

       (car l)))))

;;вызов по значению

> (razbei ( 1 2 3))

(3 2 1)

 

Константы в качестве аргументов передаются в функцию непосредственно, в качестве значений переменных используются те значения, которые они получили в момент передачи в качестве параметров. Если среди аргументов есть вызов функции, то сначала происходит запуск процесса вычисления этой функции. Очевидно, что если какой-либо аргумент не используется в теле функции, то вычисление его значения будет впустую. Стратегия отложенных вычислений состоит в том, что аргумент вычисляется только в том случае, если он нужен для вычисления окончательного результата, возвращаемого начальным вызовом. Для объяснения различие этих стратегий можно показывать на примере факториала (см.таблицу 2).

Разные стратегии вычислений

Таблица 2

Математическая запись

Традиционное программирование

Функциональное программирование

fact(0) = 1;

fact(n) = n*fact(n-1) n>0

Function  fact (n:integer) : integer;

Begin If n = 0 then res: = 1

Else  Res := n*fact(n-1); End;

(defun fact (n)

(do((res n (* res n)))

( (> 2 n) (if (= n 0) 1 res))

(setf n(- n 1))))

 

Функциональное программирование основано на: алгебре  списочных структур, лямбда-исчислении, теории рекурсий. К языкам ФП относятся: Lisp, Haskell, Miranda, Erlang и Рефал. Вызов функций в функциональном программировании основывается на записях лямбда-исчислении. В свою очередь их можно описать как префиксная и инфиксная запись. Виды таких записей приведены в таблице 3.

Виды записей

Таблица 3

Префиксная запись

Инфиксная запись

f(x)

(f  x)

g(x ,y)

(g x y)

h(x, g(y ,z))

(h x (g y z))

x + y  

(+ x y)

x – y

(- x y)

x * y

(* x y)

x  / y

(/ x y)

 

История появления ФП. 1924 г. М.Шейнфинкель разработал простую теорию функций. В 1934 г. Алонсо Черч применил лямбда-исчисление для теории множеств. В 1940 г. Хаскелл Карри создал теорию функций без переменных. В 1960 г. Дэвид Тернер положил начало направлению ФП. В 1960 г.  Джон Маккарти создал язык ЛИСП. Следующий язык ФП – язык АПЛ, язык для массивов. В 1960 г. российским ученым  В.Ф.Турчиным был создан язык РЕФАЛ. РЕФАЛ сейчас используется для представления xml-документов. В 1970 г. Дж.Бэкус создал ФП-системы, который отличался от фон-Нейманского подхода. В 1970-1980 г. Роберт Миллер создал язык МЛ – метаязык. В 1985-1986 г. Дэвид Тернер создал язык Миранда - первый язык ленивых вычислений. В 1980 компания Ericsson создала язык Erlang – для параллельных вычислений. В 1990 г. создали язык Хаскелл – сочетание достоинства разных языков ФП в одном [9].

Типы функций. Пусть A и B некоторые первичные типы данных (числа, строки,списки, фунций). Пусть у функций  переменные принадлежат типу A а область значения типу B. Тогда функция объект типа A→B называется функциональным типом.  Если REAL – тип действительных чисел, POSITIV- тип неотрицательных действительных чисел, INTEGER- целых, то можно записать Sin(x),  функция типа REAL → REAL, а ln(x) как функцию типа POSITIV → REAL. Каррирование. Тип функции назван в честь Хаскелла Карри. Он описал вычислительный процесс – как комбинаторную логику. Используя понятие функционального типа функцию многих переменных можно рассматривать как функцию одной переменной. Например рассмотрим функцию x + y.   Ее префиксная запись: add(x,y).  А функциональный тип будет в виде REALxREAL→ REAL.  В общем случае, если функция имеет тип  (A1 xA2 x An) → B то ее можно рассматривать как состоящую из двух элементов – чисел с типом  A1 →( A2 (An→ B)…). Такая интерпретация функции называется  каррированием. Например, тип add(x,y) определяется по виду записи. Если запись вида add(x,y) то тип функции  будет вида REALxREAL→ REAL  а если вида add x y то тип функции будет REAL→(REAL→REAL). Аппликация и обобщение конструкции выражания. Традиционно f(a) понимается как результат применения функций f к значению аргумента  a. На месте аргумента или операнда может стоять любое выражение, значение которого вычисляется перед применением функции, а на месте оператора, т.е. конструкции, которую можно применить к значению операнда, только имя некоторой функции. Налицо определенная ассиметрия.

В функциональном программировании предлагается рассматривать f(a) как результат выполнения операции аппликации(приложения) с аргументами  f и a. Это записывается следующим образом: f(a) ↔ apply(f,a). Данная операция называется  аппликацией.  А обобщение конструкции выражания  состоит в том, что операция apply вычисляет оба свои аргумента. Она имеет тип (A→ A) → (A→ A).  Например если рассматривать add как каррированную функцию, то для сложения двух действительных чисел 3 и 5  необходимо записать:  apply(apply(add, 3),5). То, что apply вычисляет оба свои аргумента, дает возможность вычислить значение данного выражения. Первое вхождение  apply требует вычислить значение apply(add, 3) и 5. Значением  apply(add, 3) будет функция одного аргумента, которая прибавляет к нему значение 3, значением константы является сама константа. Далее вычисляется внешнее вхождение apply, что и даст окончательный результат 8.  Введение операции позволяет работать не только с вычисляемым операндом, но и с вычисляемым оператором. Выражение, в котором все функции рассматриваются как функции одной переменной, а применение функции к аргументу выполняется с помощью операции apply  носит название выражение в форме оператор-операнд [10].

Внутреннее представление списков.  Для этого рассмотрим пример. Дан следующий список: [a1 [a2, a3 , [a4]], a5]. Представим представление этого списка  в виде следующего рисунка.

Рисунок 1- Графическое представление списочной структуры

 [a1 [a2, a3 , [a4]], a5]

 

На этом рисунке  Хпустой список. Атомы a1 и a5 имеют уровень вложенности 1, атомы a2 и  a3 - 2, а атом a4  - 3.

Возможности функционального программирования. Таких возможностей несколько. Краткость и выразительность программ. Он достигается за счет механизма рекурсии. Возможность применения функций только к частям аргументов. В функциональных программах создаются частичные вычислители. Он является обобщением обычного интерпретатора, который может выполнять вычисления только при полностью означенных параметрах. Отложенные вычисления. Аргумент вычисляется только в том случае, если он нужен для вычисления окончательного результата, возвращаемого начальным вызовом. Распараллеливание вычислений. В ФП все функции для вычислений используют только свои параметры, можно организовать вычисление независимых функции в произвольном порядке или параллельно, причем параллелизм может быть и на уровне компилятора языка и на уровне технических средств. Запись определения функции в виде отдельных равенств (клозов) позволяет распараллелить вычисления на уровне вычисления отдельной функции -  путем параллельного запуска вычислений каждого клоза с последующим выбором среди результатов результат нужного клоза. Клоз представляет собой запись одного варианта вычисления некоторой функции, определяемого видом последовательности образцов, записанных после имени функции.

 

Лекция 4. Языки искусственного интеллекта. Возможности языков ЛИСП и Хаскелл

 

Цель лекций. Ознакомление с основными принципами работы функциональных языков  ЛИСПа и Хаскелла. 

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

 Язык ЛИСП был впервые предложен Джоном Маккарти в конце 50-годов. В ЛИСПе символы обозначают числа, другие символы или более сложные структуры. Символы T и NIL имеют в ЛИСПе специальное назначение: T - обозначает логическое значение истина, а NIL - логическое значение ложь. Создание программы на ЛИСПе - написание некоторой функции, возможно сложной, при вычислении использующей другие функции либо рекурсивно саму себя [7,8].  На практике, написание программ осуществляется записью в файл определений функций, данных и других объектов с помощью имеющегося в программном окружении редактора. Файлу присваивается расширение *.lsp. В языке ЛИСП как для вызова функций, так и для записи выражения принята единообразная префиксная форма записи, при которой как имя функции или действия, так и сами аргументы записываются внутри скобок: (f x), (g x y), (h x (g y z)). В языке ЛИСП все действия описываются в виде функций. С точки зрения синтаксиса, обращения к функциям, как и обрабатываемые ими данные, представ­ляют собой так называемые S-выражения. В простейшем случае S-выражением является атом (идентификатор или число), в более сложном – список, который представляет собой заключенную в круглые скобки последовательность элементов списка. Списки в ЛИСПе имеют рекурсивную структуру, поскольку элементом списка может быть произвольное S-выражение – как атом, так и список. Пустой список () имеет в ЛИСПе и другое обозначение – nil, причем он одновременно относится и к атомам, и к спискам [10]. Некоторые S-выражения можно вычислять, такие выражения называются формами. Простейшими формами являются числа и атомы-константы T и nil. Формой является также обращение к функции, список вида (f a1 a2 ... an)   (n≥0) где f - имя функции, а ai - ее аргументы, которые для обычной функции должны быть формами.

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

Определение новых функций. Для этого служит встроенная функция defun, к которой возможно любое из следующих обращений:(defun f (lambda(v1 v2  ... vn) e))    (n≥0) (defun f (v1 v2 ... vn) e). Значением этой функциональной формы является имя определяемой функции, - f.  Побочным же эффектом вычисления этой формы будет опре­деление новой ЛИСПовской функции с именем f, аргументами vi и телом e - формой, зависящей от vi. При последующем обращении в программе к новой функции: (f a1 a2 ... an) сначала вычисляются аргументы функции ai, затем вводятся локальные переменные vi, которым присваиваются значения соответствующих аргументов ai, а далее вычисляется форма-тело e при этих значениях переменных vi, после чего эти переменные уничтожаются. Вычисленное значение формы становится значением функции f.

Операции над списками. (car l). Значением аргумента l должен быть непустой список; значением же функции является первый элемент верхнего уровня этого списка. (cdr l). Значением аргумента l должен быть непустой список, а значением функции является «хвост» списка, полученный отбрасыванием первого элемента. Например, если переменная X имеет своим значением список (p(q r)), то значение формы (car X) равно p, а значение (cdr X) равно ((q r)). Кроме этих двух функций, часто используются функции, задающие их суперпозиции. Имена всех таких функций начинаются на букву c, а заканчиваются на букву r, между ними же может стоять произвольная комбинация из не более чем четырех букв a и d, причем буква a означает наличие в суперпозиции функции car, а буква d – функции cdr. Сама же последовательность букв соответствует порядку следования функций car и cdr в эквивалентной суперпозиции. Например: (caddr lº  (car(cdr(cdr l))). Предполагается, что список-аргумент l у всех этих функций-суперпозиций, как и у ниже описываемой функции nth, содержит необходимое число элементов. (nth n l). Значением аргумента n должно быть положительное целое число, а значением аргумента l – список. Значением функции является N-й от начала элемент этого списка, причем элементы списка нумеруются, начиная с 0. К примеру, если переменная X имеет (p(q r)7), то значение формы (nth 2 X) равно 7, так же, как и значение формы (caddr X). Все рассмотренные выше ЛИСП-функции называются селекторами, так как они выбирают определенные элементы списков. Рассмотрим теперь функции, называемые конструкторами: они строят новый список, который и выдают в качестве своего результата.  (cons e l). Эта функция строит список, первым элементом которого будет значение аргумента e, а хвостом списка – значение аргумента l. (append l1 l2). Данная функция осуществляет слияние элементов двух списков в один результирующий список. (list e1 e2 ... en)   (n≥1). Эта функция имеет произвольное количество аргументов, из значений которых она строит список. (last l). Значением функции является список из одного элемента – последнего элемента верхнего уровня списка-аргумента l. Например, если переменная X имеет (p(q r)), а переменная Y – список (t), то значение формы  (cons X Y)   равно   ((p(q r))t), значение формы  (list X Y)   равно   ((p(q r))(t)), значение формы  (append X Y)   равно  (p(q r) t); значение формы  (last X) равно ((q r)).

Арифметические функции. (length l). Значением аргумента l должен быть список. Функция вычисляет количество элементов этого списка. К примеру, значение (length X) равно 2, если X имеет (p(q r)). Значениями аргументов следующих функций должны быть числа, над которыми производятся арифметические операции. (add1 n). Функция прибавляет число 1 к числу-аргументу и выдает результат в качестве своего значения. (sub1 n). Эта функция вычитает 1 из значения своего аргумента и выдает результат в качестве своего значения. (+ n1 n2). Значением функции является сумма значений ее аргументов. (- n1 n2). Значением этой функции является разность значений ее аргументов. (* n1 n2). Значением этой функции является произведение значений ее аргументов. (/ n1 n2). Результат вычисления этой функции – частное, получающееся при делении первого числа на второе. (rem n1 n2). Результат вычисления этой функции – остаток от деления первого числа на второе.

Предикаты. Предикатом называется форма, значение которой рассматривается как логическое значение «истина» или «ложь». Особенностью языка ЛИСП является то, что «ложью» считается пустой список, записываемый как () или nil, а «истиной» – произвольное выражение, отличное от () и nil. В частности, в роли «истины» может использоваться атом T. (null e). Эта функция проверяет, является ли значение ее аргумента пустым списком; если - да, то значение - T, иначе – nil. (eq e1 e2). Функция сравнивает значения своих аргументов, которые должны быть атомами-идентификаторами. В случае их равенства значение функции равно T, иначе – nil. (eql e1 e2). В отличие от предыдущей функции, данная функция сравнивает значения своих аргументов, которыми могут быть не только атомы-идентификаторы, но и атомы-числа. Если аргументы равны, то значение T, иначе – nil. (equal e1 e2). Функция производит сравнение двух произвольных S-выражений – значений своих аргументов. Если они равны, то значение T, иначе – nil. (neq e1 e2). Аналог предыдущей функции, но значения аргументов сравниваются на «не равно». (member a l). Значением первого аргумента должен быть атом, а второго – список. Функция производит поиск заданного атома на верхнем уровне заданного списка. В случае успеха поиска в качестве значения функции выдается хвост списка l, начиная с найденного атома, в случае же неуспеха выдается nil.  Функций (= n1 n2), (/= n1 n2), (> n1 n2),  (>= n1 n2), (< n1 n2), (<= n1 n2). Значениями аргументов этих функций должны быть числа. Эти числа сравниваются соответственно на равенство, неравенство, «больше», «больше или равно», «меньше», «меньше или равно», и если сравнение успешно, вырабатывается атом T, иначе - nil.

 Логические функции. Так называются три функции, реализующие основные логические операции. (not e). Эта функция реализует логическое отрицание и является дубликатом функции null: если значение  аргумента равно nil («ложь»), то функция выдает результат T, иначе - nil. Следующие функции являются особыми, так как, во-первых, они имеют произвольное число аргументов, а во-вторых, не обязательно вычисляют значения всех своих аргументов.  (and e1 e2 ... ek)  (k≥1). Эта функция реализует конъюнкцию. Функция по очереди вычисляет свои аргументы. Если значение очередного из них равно nil, то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу со значением nil, а иначе переходит к вычислению следующего аргумента. Если функция дошла до вычисления последнего аргумента, то с его значением она и заканчивает свою работу. (or e1 e2 ... ek) (k≥1). Эта функция реализует дизъюнкцию. Функция по очереди вычисляет свои аргументы. Если значение очередного из них не равно nil), то функция, не вычисляя оставшиеся аргументы, заканчивает свою работу со значением этого аргумента, в противном случае она переходит к вычислению следующего аргумента. Если функция дошла до вычисления последнего аргумента, то с его значением она и заканчивает свою работу. К числу логических функций можно отнести и ЛИСПовское условное выражение(cond (p1 e1,1 e1,2 ... e1,k1) ... (pn  en,1 en,2 ...  en,kn)(n≥1,  ki≥1). Функция последовательно вычисляет первые элементы своих аргументов – предикаты pi. Если все они имеют значение nil, тогда функция заканчивает свою работу с этим же значением. Но если был обнаружен предикат pi, значение которого отлично от nil, тогда функция уже не будет рассматривать остальные предикаты, а последовательно вычислит все формы ei,j из соответствующего аргумента и со значением последней из них закончит свою работу. За исключением последних форм в каждой ветви, в качестве форм ei,j имеет смысл использовать только такие, которые имеют при вычислении побочный эффект, например, присваивание переменной значения.

Другие специальные функции. (quote e)   или   'e. Это функция блокировки вычислений: она выдает в качестве значения свой аргумент, не вычисляя его. Например, значением формы '(car (2)) является само выражение (car (2)). (gensym). Это функция генерации уникальных атомов: при каждом обращении к ней выдается новый атом-идентификатор. Этот идентификатор получается склеиванием специального префикса и очередного номера.

Блочная и связанные с ней функции. (prog (v1 v2  ... vn) e1 e2  ... ek)  (n≥0, k≥1). Эту специальную функцию называют «блочной», поскольку ее вычисление напоминает выполнение блоков в других языках программирования. Вычисление функции начинается с того, что вводятся локальные переменные vi, перечисленные в ее первом аргументе, и всем им в качестве начального значения присваивается пустой список nil. После этого функция последовательно вычисляет остальные свои аргументы - формы ei. Вычислив последнюю из них, функция prog заканчивает работу со значением этой формы, уничтожив перед этим все свои локальные переменные vi. Поскольку только значение последней формы ek используется как значение всей функции prog, то в качестве остальных форм ei имеет смысл использовать  только функции с побочным эффектом. Некоторые из этих функций перечислены ниже. В качестве одной из форм ei может быть записан атом-идентификатор, в этом случае он не вычисляется, а трактуется как метка, на которую будет производиться переход внутри этого блока. (return e). Это функция досрочного выхода из блока. Она может использоваться только внутри блочной функции prog, поскольку завершает вычисление ближайшей объемлющей блочной функции, устанавливая ее значение, равным значению аргумента e. (go  e). Функция реализует переход по метке. Аргумент ее не вычисляется, в качестве ее аргумента должен быть задан идентификатор – одна из меток ближайшей объемлющей блочной функции. Функция go полностью завершает вычисление той формы этой блочной функции, в которую она входит, и осуществляет переход на вычисление формы, непосредственно следующей за указанной меткой. (setq v e). Это аналог оператора присваивания. В качестве аргумента v должно быть задано имя переменной, существующей в данный момент. Функция присваивает этой переменной новое значение – вычисленное значение формы e. Это же значение является значением и самой функции setq, однако оно, как правило, не используется [12].

На языке ЛИСП  любое предложение, заключенное в скобки, введенное вне редактора, считается функцией и выполняется сразу после нажатия «ENTER». Определения функций могут храниться в файлах и  загружаться,  используя  функцию LOAD: (load <имя файла>). <Имя файла> - это строковая константа, которая представляет собой  имя  файла  без  расширения. После нескольких секунд загрузки на экране дисплея появится знак >, означающий приглашение системы к работе. Системный редактор начинает работать и выдает на экран свое меню: File, Edit и Run.  

Язык Haskell - это современный язык общего назначения, который был разработан для того, чтобы объединить в себе коллективные знания сообщества приверженцев функционального программирования в целях создания одного элегантного, мощного и общедоступного языка [16]. В отличие от некоторых других языков функционального программирования язык Haskell является чистым. Он не допускает никаких побочных эффектов. Это, несомненно, самая важная особенность языка Haskell. Ещё одной особенностью языка Haskell является то, что он является языком с отложенными вычислениями. Это означает, что ничего не будет вычислено, пока не должно будет быть вычислено. Например, можно определить в бесконечной рекурсии бесконечный список чисел. Только те элементы списка, которые на самом деле будут использованы, будут вычислены. Отложенные вычисления делают эту операцию очень прозрачной. Если вам нужно одно решение, то вы можете просто извлечь первый элемент из получившегося списка - механизм ленивых вычислений удостоверится, что ничего ненужного не посчитано. Язык Haskell строго типизированный язык. Невозможно неосторожно привести Double к Int или вызвать метод по пустому указателю. Это ведёт к меньшему количеству ошибок. В других языках там, где это приведение выполняется неявно, проблемы часто возникают когда компилятор обращается с Double как с Int или с Int как с указателем. В отличие от других языков, типы в языке Haskell определяются автоматически. Это означает, что вам очень редко придется объявлять типы ваших функций, кроме тех случаев, которые оговорены документацией кода. Язык Haskell посмотрит на то, как вы используете переменные, и сделает вывод о том, какой должен быть тип у переменных, после этого будет проведена проверка типов для того, чтобы убедиться, что нет несовпадения типов. Ошибки отлавливаются во время компиляции чаще, чем во время выполнения, без преград, сопутствующих другим языкам. Кроме того, язык Haskell будет делать вывод для большинства общепринятых типов переменных. Так что если вы пишете, например, функцию сортировки без описания типа, язык Haskell удостоверится, что она будет работать для всех значений, которые могут быть отсортированы. Программы на языке Haskell содержат меньше ошибок, потому что язык Haskell: Чистый. Нет побочных эффектов; Строго типизированный. Не может быть неоднозначного использования типов;  Лаконичный. Программы короче, что позволяет просто взглянуть на функцию и «уяснить всё сразу», чтобы убедиться в том, что функция правильная; Высокоуровневый. Программы на языке Haskell чаще всего читаются так, как описание алгоритма. Это позволяет проще проводить проверку того, что функция делает то, что утверждает алгоритм. Так как кодирование происходит на более высоком уровне абстракции, оставляя детали компилятору, то существует меньше мест, куда может закрасться ошибка; Управляет памятью. Не надо заботиться о «повисших» ссылках, сборщик мусора позаботится о них. Программист может беспокоиться о выполнении алгоритма, а не о подсчёте памяти; Модульный. Язык предоставляет более сильный механизм составления вашей программы из уже разработанных модулей. Таким образом, программы могут быть более модульными. Кроме того, большинство людей сходятся во взглядах, что вы просто думаете по-другому, решая проблему на функциональном языке. Вы подразделяете задачу на всё меньшие и меньшие задачи, а после этого вы пишете эти маленькие задачи, которые объединяются разными способами для достижения конечного результата. Там просто нет места для ошибок!

 

Лекция 5. Введение в задачи искусственного интеллекта. Основные понятия  искусственного интеллекта

 

Цель лекций. Основные понятия искусственного интеллекта.

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

По определению Д.Люгера: «Искусственный интеллект (ИИ)это дисциплина, исследующая закономерности, лежащие в основе разумного поведения, путем построения и изучения артефактов, предопределяющие эти закономерности» [11]. Разработчиков ИИ занимают две проблемы: это – представление знаний и поиск. В представлении знаний рассматриваются языки представления знаний (ЯПЗ), понимание естественного языка, представление нечетких знаний.  ЯПЗ в свою очередь представляют такие языки, как  язык исчисления предикатов, модели представления знаний. Язык исчисления предикатов является формальной основой языка логического программирования ПРОЛОГ. Модели представления знаний в свою очередь делятся на: продукционные системы, фреймы, семантические сети. Нечеткие знания работают с механизмом нечетких выводов. Они в свою очередь связаны с выводами учета факторов уверенности и методами теорий Заде. Понимание естественного языка связано с символьным представлением информации и представлением грамматического анализа предложений. В ИИ методы поиска  разделены на три группы: поиск в пространстве состояний, поиск в пространстве задач, поиск в среде предикатов. Остаются еще важные направления в изучении искусственного интеллекта. К ним можно отнести: Обработка сенсорных данных (особенно зрительных образов и речи),  cложные системы хранения и извлечения информации, машинное обучение.

Компьютеризация общества - одно из основных направлений научно-тех­нического прогресса - вызвала существенные изменения в технологии разра­ботки и использования программных средств. Эти изменения были подготовлены всем развитием теории и практики искусственного интеллекта, наиболее существенным результатом кото­рого явился переход и создание «экспертных систем» (ЭС). Суть происшедших технологических изменений заключается в появлении нового класса инструментальных средств ИИ, который стал основой создания конечных программных продуктов на основе принципиально другой техноло­гии, с новыми качественными возможностями создаваемых продуктов, эти из­менения существенно повышают интеллект программ, новые средства заменили целый технологический ряд, в котором между конечным поль­зователем и ЭВМ находилось несколько посредников. Более полно различия программ ИИ и обычных программ иллюстрирует  следующая таблица.

 

Сравнительная характеристика программ ИИ

Таблица 4

Характеристика

Обычная программа

Программа ИИ

Тип обработки

цифровая

символьная

метод

алгоритмический

эвристический

Определение шагов

точное решения

неявное

Искомые решения

оптимальные

удовлетворительные

Разделение управления

смешано

раздельно 

Модификация

частая  

редкая

 

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

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

Все различия,  приведенные для программ ИИ, в целом характерны и для экспертных систем. Интеллект – это способ обработки информаций. Большинство программ ИИ представляют знания на некотором формальном языке, а затем обрабатываются в соответствии с алгоритмами, следуя заложенному еще фон Нейманом принципу разделения данных и программ. Формальная логика возникла как важный инструмент представления для исследований ИИ. Поэтому важно проследить историю развития логики. Она представлена в таблице 5.

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

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

 

Развитие логики

Таблица 5

Формальные теории

Цель

Авторы

Теория графов

Для моделирования скрытой структуры задачи

Лейбниц,1887,

Эйлер, 1735

Разностная и  аналитическая машина Бэббиджа

Первое программируемое механическое  и универсальное программируемое вычислительное устройство

Чарльз Бэббидж, математик 19 в., Ада Лавлейс, 1961

Булева Алгебра

Исследование фундаментальных законов  разума

Джордж Буль, 1847

Исчисление предикатов

Инструмент для записи теорем истинности, математических умозаключений

Готлоб Фреге, 1884

Автоматическое доказательство теорем

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

Рассел, Уатхейд, 1950

Тест Тьюринга

Сравнивает способности разумной машины со способностью человека

Алан  Тьюриг, 1950

Теория ссылок

Правильно построенные формулы ссылаются на объекты реального мира

Альфред Тарский, 1944

 

Роль овеществления в познании.  Архитектура сегодняшних компьютеров не дает тесного взаимодействие ИИ с миром современных устройств ввода-вывода. Он их только ограничивает. Реализация машинного разума требует интерфейса, отличного от предлагаемого современными компьютерами. Культура и интеллект. Понимание социального контекста знания и человеческого поведения не менее важны для теории интеллекта, чем понимание процесса отдельного разума-мозга. Природа интерпретации. Одна предметная область может иметь разные интерпретации в свете различных практических целей. Значение символов может быть понятно лишь в контексте его интерпретации. Необходимость построения ошибочных вычислительных моделей. Для подтверждения правильности модели не достаточно конечного числа подтверждающих экспериментов. Ошибки в существующих теориях стимулируют дальнейшие исследования. Некоторые структуры в ИИ, например, семантические сети настолько общи, что им можно смоделировать практически все, что поддается описанию. Нечеткий вывод. Неточный вывод рассмотрим по двум случаям: по фактору уверенности и по логике Заде. Когда эксперты формируют правила, они сопоставляют с каждым правилом фактор или коэффициент уверенности (КУ), представляющий надежностьправила. Например, для продукционных правил они записываются:

 CF(P1 and P2) = min(CF(P1),CF(P2))

CF(P1 or P2)=max(CF(P1),CF(P2)).

 Где P1, P2  - означают предпосылки продукционного правила. В теории нечетких множеств Лофти Заде для измерения неопределенности предлагает теорию возможностей. Он предлагает количественное измерение неточностей.  Например, если истина = 1 и ложь = 0, то остальные возможные значения находятся между ними. 

 

Лекция 6. Введение в задачи искусственного интеллекта. Классификация задач искусственного интеллекта

 

Цель лекций. Ознакомление с существующими направлениями и классификацией задач искусственного интеллекта.

Содержание лекций. Машинный интеллект. Искусственный разум. Планирование и машинное зрение. Языки управления роботами. Машинное обучение. Понимане естественного языка. Искусственные нейронные сети, эвристическое программирование, экспертные системы.

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

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

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

Второе направление задач ИИ моделирование биологических систем подразделяются на: искусственные нейронные сети (ИНС), эвристическое программирование, экспертные системы. В ИНС используются модели, имитирующие структуры нейронов в человеческом мозге. В нейронных вычислительных моделях  каждый элемент подсчитывет значение некоторой функции своих входов и передает результат к элементам сети. Конечные результаты являются следствием параллельной и распределенной обработкой в сети, образованной нейронными соединениями и пороговыми значениями. На уровне эвристического программирования рассматривается последвательность мыслительных операций, выполнение которых приводит к решению задачи. Обычно при таком подходе испытуемому человеку предлагается решить некоторую задачу, сопровождая свои размышления  комментариями хода своих рассуждений. Все высказывания тщательно протоколируются.  Затем протоколы подвергают анализу  с целью выявления хода решения. Полученный материал используется при составлении компьютерной программы – модели данного вида поведения. Таким образом, программа является моделью протокола. И наконец экспертные системы.  Знания  в таких системах могут быть реализованы в моделях представления знаний. К ним относятся: логическая модель, модель продукционной системы, фреймовая модель, модель семантических сетей [13].  Имеется два аспекта  в решении задач: представление и поиск. Но пока в исследованиях по искусственному интеллекту ещё не выработаны универсальные  методы для нахождения точных формулировок задач. Но имеются подходы к постановке задач и  различные методы поиска. Для понимания ИИ необходимо прослушать курсы дискретной математики, теорию предикатов и теорию графов. Также необходимо понятия по структурам данных  такие, как деревья, графы, иметь представления по методам рекурсивного поиска с помощью стеков, очередей. Существуют разные средства решения задач ИИ. К ним относят язык теории предикатов, для описания определенных свойств предметной области, алгоритмы и структуры данных для реализаций этого поиска. Существуют множество архитектур, предназначенных для построения алгоритмов поиска. Так, например, как методология  «классной доски» и продукционные системы. Для решения задач, использующих знания,  рассматирваются разные схемы представлений. К ним можно отнести: концептуальные графы, фреймы и сценарий. В задачах ИИ также используются модели рассуждений в условиях неопределенности и методы использования ненадежной информаций. К ним можно отнести: байесовские модели, сети доверия, неточный вывод с учетом фактора уверенности.  Вопросы машинного обучения также относятся к задачам ИИ.  Изучаются алгоритмы символьного обучения такие, как индукция, концептуальное обучение, поиск в простанстве версий. Изучение искусственных нейронных сетей также относятся к разделам ИИ. В нейронной сети  информация структирирована неявно. Она распространяется между набором взаимносвязанных процессоров с учетом весовых коэффициентов, а обучение сводится к пересортировке и модификаций весов узлов сети. К нейроподобным архитектурам относятся: персептрон, методы обратного и встречного распростарнения ошибки, модели Кохонена, Гроссберга и Хебба. 

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

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

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

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

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

 

Лекция 7. Методы решения задач. Методы в пространстве состояний

 

Цель лекций. Ознакомление с основными методами и механизмами поиска в пространстве состояний.

Содержание лекций. Выбор метода поиска решения. Краткие теоретические сведения о состояниях, операторов задачи. Различные способы поиска. Структуры LIFO и  FIFO. Механизм бектрекинга.

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

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

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

Краткие теоретические сведения. Описание состояний. Чтобы построить описание задачи с использованием  пространства состояний, мы должны иметь определенное  представление о том, что такое состояние в этой задаче. Важным этапом построения какого-либо описания задачи с использованием пространства состояний является выбор некоторой конкретной формы описания состояний этой задачи.  В сущности, любая структура величин может быть использована для описания состояний. Это могут быть строки символов, векторы, двухмерные массивы, деревья и списки. Часто выбираемая форма описания имеет сходство с некоторым физическим свойством решаемой задачи. Так, в игре «в пятнадцать» естественной формой описания состояний может быть массив 4х4. Выбирая форму описания состояний, нужно позаботиться и о том, чтобы применение оператора, преобразующего одно описание в другое, оказалось бы достаточно легким. Для обсуждения методов поиска решения оказывается полезным введение понятий состояний и операторов для данной задачи. Для игры в «15» состояние задачи - это просто некоторое конкретное расположение фишек. Начальные и целевые конфигурации представляют собой соответственно начальное и целевое состояния. Пространство состояний, достижимых из начального состояния, состоит из всех тех конфигураций фишек, которые могут быть образованны в результате допустимых правилами перемещений фишек. Многие задач имеют чрезвычайно большие пространства состояний. Для примера рассмотрим пример игра в «8» и «15». Дано начальное состояние в виде массивов 3х3 и 4х4 целевое состояние точно такой же форме но с другими данными [10]. Эти состояния показаны на рисунке  2 (а,б). 

 

Рисунок 2 - Состояния игры «8» и «15»   в виде массива чисел

 

Оператор преобразует одно состояние в другое и в общем случае мы будем предполагать, что операторы - это вычисления, преобразующие одни описания состояний в другие. Таким образом, мы видим, что для полного представления задачи в пространстве состояний необходимо задать: а) форму описания состояний и, в частности, описание начального состояния; б) множество операторов и их воздействий  на описания состояний; в) свойства описания целевого состояния [11]. Пространство состояний полезно представлять себе в виде направленного графа. Граф состоит из множества вершин. Некоторые пары вершин соединены с помощью дуг, и эти дуги направлены от одного члена этой пары к другому. Такие графы носят название направленных графов. Процесс применения множества операторов к вершине графа называется раскрытием вершин.

Рассмотрим первый из методов поиска в пространстве состояний. Поиск в глубину (Depth-first search, DFS).  В методах перебора в глубину  прежде всего раскрываются те  вершины, которые были построены последними. Определим глубину вершины следующим образом:  глубина корня дерева равна нулю. Глубина любой последующей вершины равна единице плюс глубина вершины, которая непосредственно ей предшествует. Таким образом, вершиной, имеющей наибольшую глубину в дереве перебора, в данный момент служит та, которая должна в этот момент быть раскрыта.  Такой подход может привести к процессу, разворачивающемуся вдоль некоторого бесполезного пути, поэтому нужно ввести некоторую процедуру возвращения. В качестве механизма реализаций или в качестве обработки списков для метода поиска в глубину в алгоритмах программирования выбран механизм «стек».  Для списка open реализуется механизм как стек магазинного типа, или его называют структура LIFO «last-in-first-out»,  «последним пришел – первым обслужен». Состояния добавлются и удаляются с левого конца списка.

К одним из классических алгоритмов поиска на графе пространства состояний служит метод поиска с возвратами бектрекинг (backtrack) [12]. Этот способ предлагает опреде­ленную организацию перебора всех возможных вариантов решения задачи, число которых может быть велико. Суть бектрекинга состоит в том, чтобы в каждой точке процесса решения задачи, где существует несколько априори равноправных альтернативных вариантов дальнейшего продолжения, выбрать один из них и следовать ему, предварительно запомнив другие альтернативы, для того, чтобы в случае неуспешности выбранного варианта-пути вернуться в точку выбора и выбрать для продолжения решения другой возможный вариант-путь. В общем случае в процессе решения возможно возникновение многих подобных точек выбора, называемых обычно точками бектрекинга или развилками; к каждой из таких точек может потребоваться возврат для выбора других вариантов решения.

Методы полного перебора.  Поиск в ширину.  (BFS, Breadth-first search).   В методе полного перебора вершины раскрываются в том порядке, в котором они строятся. В методе полного перебора непременно будет найден самый короткий путь к целевой вершине при условии, что такой путь вообще существует. Если такого пути нет, то в указанном методе будет объявлено о неуспехе в случае конечных графов, а в случае бесконечных графов алгоритм никогда не кончит свою работу. Если сделать резюме, то суть заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины – выбирается та, которая была раньше рассмотрена. В качестве механизма реализаций или в качестве обработки списков для метода поиска в ширину в алгоритмах программирования выбран механизм «очередь». Для списка open реализуется механизм очередь, или его называют структура FIFO «first-in-first-out», «первым пришел – первым обслужен». Состояния добавлются в список справа  и удаляются с левого конца списка.

 

Лекция 8. Методы решения задач. Эвристические методы и метод редукций

 

Цель лекций. Ознакомление с методом редукций в пространстве задач и эвристическим методом в пространстве состояний.

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

Эвристический метод. Этот способ позволяет во всех случаях найти некоторый путь от начальной вершины к целевой, стоимость которого минимальна. В то время как в вышеописанном алгоритме распространяются линии равной длины пути от начальной вершины, в более общем алгоритме, распространяются линии равной стоимости пути. Предполагается, что нам задана функция стоимости c(ni,nj),  дающая стоимость перехода от вершины ni к некоторой следующей за ней вершине nj. В методе равных цен для каждой вершины n в дереве перебора нам нужно помнить стоимость пути, построенного от начальной вершины s к вершине n. Пусть g(n) -  стоимость от вершины s к вершине n в дереве перебора. В случае деревьев перебора мы можем быть уверены, что g(n) является к тому же стоимостью того пути, который имеет минимальную стоимость.  Кроме уже рассмотренного подхода – представления задач в пространстве состояний – для решения ряда задач возможен и другой, более сложный подход. При этом подходе производится анализ исходной задачи с целью выделения такого набора подзадач, решив которые, мы решим исходную задачу. Каждая из выделенных подзадач в общем случае является более простой, чем исходная, и может быть решена каким-либо методом, в том числе – с использованием пространства состояний. Но можно продолжить процесс, последовательно выделяя из возникающих задач свои подзадачи – до тех пор, пока не получим элементарные задачи, решение которых уже известно. Такой путь называется подходом, основанным на сведении задач к подзадачам, или на редукции задач.

Для иллюстрации этого подхода рассмотрим один из вариантов известной головоломки – задачи о ханойской башне, или пирамидке [13]. В ней используются 3 колышка и 64  диска разного диаметра, которые можно нанизывать на колышки через отверстия в центре. В начале все диски расположены на колышке А, причем диски меньшего диаметра лежат на дисках большего диаметра.  Требуется переместить все диски на колышек С, двигая их по очереди и соблюдая определенные правила. Перемещать можно только самый верхний диск, и нельзя никакой диск класть на диск меньшего размера. Таким образом, в случае подхода, основанного на редукции задач, мы получаем также пространство, но состоящее не из состояний, а из задач/подзадач. Для решения задачи (простейший случай), когда пирамида состоит только из одного диска, необходимо выполнить одно действие – перенести диск со стержня i на стержень j, что очевидно (этот перенос обозначается i -> j). Общий случай задачи изображен на рисунке, когда требуется перенести n дисков со стержня i на стержень j, считая стержень w вспомогательным. Сначала следует перенести n‑1 диск со стержня i на стержень w при вспомогательном стержне j, затем перенести один диск со стержня i на стержень j и, наконец, перенести n‑1 диск из w на стержень j, используя, вспомогательный стержень i. Итак, задача о переносе n дисков сводится к двум задачам о переносе n‑1 диска и одной простейшей задаче. Схематически это можно записать так: T (n, i, j, w) = T (n‑1, i, w, j), T (1, i, j, w), T (n‑1, w, j, i). Ниже приведена программа, которая вводит число n и печатает список перемещений, решающая задачу о Ханойских башнях при количестве дисков n. Используется внутренняя рекурсивная процедура tn (n, i, j, w), печатающая перемещения, необходимые для переноса n дисков со стержня i на стержень j с использованием вспомогательного стержня w при {i, j, w} = {1,3,2}. Последовательность вызовов процедуры tn при m=3 иллюстрируется древовидной структурой на рисунке 3. Каждый раз при вызове процедуры tn под параметры n, i, j, w выделяется память и запоминается место возврата. При возврате из процедуры tn память, выделенная под параметры n, i, j, w, освобождается и становится доступной память, выделенная под параметры n, i, j, w предыдущим вызовом, а управление передается в место возврата.

Рисунок 3 - Стек Ханойских башен

 

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

При этом роль, аналогичную операторам в пространстве состояний, играют операторы, сводящие задачи в подзадачи. Точнее, каждый оператор редукции преобразует описание задачи в описание множества подзадач, причем это множество таково, что решение всех подзадач обеспечивает решение редуцированной задачи [11]. При решении задач методом редукции, как и при решении в пространстве состояний, может возникнуть необходимость перебора. Действительно, на каждом этапе редукции может оказаться несколько применимых операторов и соответственно, несколько альтер­нативных множеств подзадач. Процесс редукции продолжается, пока исходная задача не будет сведена к набору элементарных задач, решение которых известно. Аналогично представлению в пространстве состояний, формализация задачи в рамках подхода, основанного на редукции задач, включает определение следующих составляющих: формы описания задач/подзадач и описание исходной задачи; множества операторов и их воздействий на описания задач; множества элементарных задач. Эти составляющие задают неявно пространство задач, в котором требуется провести поиск решения задачи. Что касается формы описания задач/подзадач, то часто их удобно описывать в терминах пространства состояний, задавая начальное состояние и множество операторов, а также целевое состояние или его свойства. В дополнение отметим, что подход с использованием пространства состояний можно рассматривать как вырожденный случай подхода, основанного на редукции задач, так как применение оператора в пространстве состояний сводит обычно исходную задачу к несколько более простой задаче, т.е. редуцирует ее. При этом результирующее множество подзадач состоит только из одного элемента, т.е. мы имеем простейший случай замены редуцируемой задачи на ей эквивалентную.

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

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

 Решающий граф – это подграф И/ИЛИ-графа, состоящий только из разрешимых вершин и доказывающий разрешимость начальной вершины.

 

Лекция 9. Методы решения задач. Метод исчисления предикатов

 

Цель лекций. Основные понятия исчисления предикатов первого порядка. Построение задачи с помощью подхода исчисления предикатов.

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

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

Синтаксис. Основной алфавит состоит из таких множества символов: Знаки пунктуации  : , . ( ); Логические символы:  ~, => (~- символ “не” –; а  => читается как – “влечет за собой”;  n – местные функциональные буквы:    ( )  (-константая буква, они обозначаются как а,в,с,  а   как - f, g, h; n – местные предикатные буквы: (). Их предлагают обозначать как    - P, Q, R – для простоты. С помощью этих символов можно построить различные выражения. В классе выражений можно определить следующие термины: Термы, Атомные формулы,  ППФ – Правильно Посроенные Формулы. Теперь добавим нашему алвафиту следующие логические символы: ٨ – “и” , V –“или” . Например: если х1  и х2  любой  ППФ, тогда

x1 ٨x2, x1V x2,  - тоже ППФ, 

т.е.  x1 ٨x2=~ (x1 =>~x2), x1V x2 =(~ x1 )=>x2).

Семантика  Для того чтобы придать ППФ- “содержание”, ее надо интерпретировать как некоторое утверждение, касающееся рассматриваемой области. Например, областью может служить некоторое непустое мнжество. Им может быть множество целых чисел или множество конфигураций игры в «8» или «множество всех математиков» и.т.д. Интересующие нас утверждения будут связаны отношениями между элементами этой области. Нарпимер, мы выскажем следующее утверждения: «Ержан -  отец Айдара».  Тогда областью будет множество людей, а отношением между людьми – бинарное отношение  –«отцовство». Нарпимер,  функция плюс  отображает пары целых чисел в целые числа в соответствии с хорошо известной операцией сложения. Для  ППФ сделать утверждения определенного смысла, мы связываем с этой ППФ – некоторую непустую область D. Затем связываем: с каждым констнатным символом в ППФ – некоторый конкретный элемент из D, с каждой функциональной буквой в ППФ –некоторую конкретную функцию на D, с каждой предикатной буквой в ППФ –некоторое  конкретное отношение между элементами из D.  Конкретизация области и указанных соответствий дает интерпретацию нашей ППФ, или модель нашей ППФ. При заданной ППФ и некоторой интерпретации каждой атомной формуле  в этой ППФ припсвается значение T или F. Правило приписывания значения атомной формулы очень простое: если термы предикатной буквы соответствуют элементам из D, удовлетворяющим соответствующему соотношению, то значениям атомной формулы будет T. В противном случае будет F. Например: пусть P(a,f(в,c)) – атомная  формула, и имеет она следующую интерпретацию: D - множество целых чисел, а – число 2, b –  число 4, c –  число 6,  f -  функция сложения, P – > отношение  «больше». При такой интерпретации наша атомная формула утверждает, что: «число 2 больше суммы чисел 4 и 6». Это утверждение неверно, поэтому  P(a,f(в,c)) – имеет значение F. Если  интерпретацию изменить так, что а=11, тогда P(a,f(в,c)) – будет имеет значение Т. Очевидно, что существует много других интерпретаций, для которых эта атомная формула имеет значение Т, и много таких  интерпретаций, для которых эта атомная формула имеет значение F. Но для любой интерпретаций будет либо Т, либо F и никогда то и другое одновременно. 

Обычно утверждения для конкретной предметной области можно записать в виде конъюнкции.   В таких случаях применяется словосочетания: для каждого и для всех.  В математической логике их обозначают следующим образом: ( для каждого). Например,  вместо (x1 ٨x2 ٨...٨xn) можно записать  (х) Р(х, ).  -  символ (перевернутый знак буквы А ), он  называется – квантором всеобщности. А переменная Х, которая находится после этого знака, называется переменной квантора всеобщности.  Такое же обозначение имеется и для (x1 V x2 V... V xn) – дизъюнкции. Вместо дизъюнкций используется знак  (перевернутый знак  буквы Е). Он называется  квантором существования. Допустим, что имеется следующее утверждение: «для четных чисел, которые находятся между числами 1 и 100, первое число больше второго».  Запишем это утверждение на языке ППФ следующим образом: (х) (у) Р(х,у),  тога ППФ принимает значение  - F.  Например утверждение: «для каждого целого числа существует  число больше этого числа» можно записать следующим образом: .

Общезначимость и выполнимость. Если некоторая  ППФ имеет значение Т при всех  интерпретациях,  то ее называют  общезначимой. Так,  по таблице истинности следующая  ППФ   P(a)=>(P(a)|P(b)) при любой интерпретации имеет значение Т и следовательно, она общезначима. С помощью таблиц истинности всегда можно определить, общезначима ли данная ППФ, не содержащая кванторов. Нужно просто проверить , имеет ли эта ППФ значение Т при всех возможных значениях (Т или F) содержащихся в ней атомных формул. Если при данной интерпретации каждая ППФ из некоторого множества имеет значение Т, то говорят, что данная интерпретация удовлетворяет данному множеству. 

ППФ -  W  логически следует из некоторого множества S - ППФ, если каждая интерпретация удовлетворяющая S удовлетворяет и W. Доказательствам того, что некоторая ППФ W логически вытекает из заданного  множества S - ППФ показывает тот факт, что W логически следует из S. Факт «неразрешимости»  исчиления предикатов означает также, что при заданных ППФ W и произвольном множества S ППФ не существует эффективной процедуры, позволяющей всегда решить, следует ли логически W из S. Именно эту  концепция, логического следования положена в основу понятия доказательства. Если некоторе мнжество ППФ не удовлетворяется ни при какой интерпретации, то она называется неудовлетворимым (или невыполнимым). Так если W логически следует из S, то объединение SU {~W} неудовлетворимо.  Обратно, если S U {~W} неудовлетворимо, то  W должна  логически следовать  из S. Этот результат используется для того, чтобы придать одинаковую форму всем задачам доказательства: для доказательства логического следования W из S  мы будем показывать, что объединение S U {~W} неудовлетворимо. Для того чтобы показать, что некоторое множество ППФ неудовлетворимо, надо доказать, что нет никакой интерпретации, при которой каждая ППФ в этом множестве имеет значение Т. Хотя эта задача и кажется трудоемкой, существуют довольно эффективные процедуры ее решения. Для выполнения этих процедур требуется сначала ППФ данного множества в специально удобном виде – в виде предложений (clouse). Любую ППФ в исчилении предикатов можно представить в виде предложения, применяя к ней последовательность простых операций. Предложения состоят из ППФ, объединеных  символами дизъюнкции (символ V) и отрицания (символ ~). Если это множество предложении неудовлетворимо, то считается,  что ППФ получена как логически следуемая из этого множества. Резольвентой называется предложение, которое появляется из двух родительских предложений.  В то же время эти два предложения должны находиться в одной интерпретации определенного множества. Например, рассмотрим два следующих предложений  

~P(f(y))VQ(f(y))

 ~Q(f(y) .

 Из двух этих предложений можно вывести следующее одно предложение ~P(f(y)). Это выведенное предложение является резольвентой двух предыдущих предложений.

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

Обратимся теперь к известной классической задаче об обезьяне и банане, простейшую формулировку которой мы и рассмотрим [13,15].

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

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

 

Лекция 10. Экспертные системы. Модели представления знаний

 

Цель лекций. Ознакомление с экспертными системами. Типы моделей представления знаний.

Содержание лекций. Виды и формы знаний. Виды моделей представления знаний. История экспертных систем. Структура экспертных систем. Состав и назначение компонент экспертных систем. Критерий применимости ЭС. Классификация языков и методов  представления знаний. 

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

Основными  отличиями экспертных систем от  других программных   продуктов являются использование не только данных, но и знаний, а также специального механизма вывода решений и новых знаний на основе имеющихся. Знания в ЭС представляются в такой форме, которая может быть легко обработана на ЭВМ. В ЭС известен алгоритм обработки знаний, а не алгоритм решения задачи. Поэтому  применение алгоритма обработки знаний может привести к получению такого результата, при решении конкретной задачи который не был предусмотрен. Более того, алгоритм обработки знаний заранее неизвестен и  строится по ходу решения задачи на основании эвристических правил. Решение задачи в экспертных системах сопровождается понятными пользователю объяснениями, качество получаемых решений обычно не хуже,  а иногда и лучше достигаемого специалистами. В системах, основанных на знаниях, правила (или эвристики), по которым решаются проблемы в конкретной предметной  области, хранятся в базе знаний. Проблемы ставятся перед системой в виде совокупности фактов, описывающих некоторую ситуацию, и система с помощью базы знаний пытается вывести заключение из этих фактов [17].

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

1) данные и знания надежны и не меняются со временем;

2) пространство возможных решений относительно невелико;

3) в процессе решения задачи должны использоваться формальные рассуждения;

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

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

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

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

 

Критерий применимости ЭС.

Таблица 6.

 применимы

неприменимы

Не могут быть построены строгие алгоритмы или процедуры, но существуют эвристические методы решения

Имеются эффективные алгоритмические методы

Есть эксперты, которые способны решить задачу

Отсутствуют эксперты или их число недостаточно

По своему характеру задачи относятся к области диагностики, интерпретации или прогнозирования

Задачи носят вычислительный характер

Доступные данные “зашумлены”

Известны точные факты и строгие процедуры

Задачи решаются методом формальных рассуждений

Задачи решаются процедурными методами, с помощью аналогии или интуитивно

Знания статичны (неизменны)

Знания динамичны (меняются со временем)

 

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

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

Состав и назначение компонент ЭС. Типичная ЭС состоит из следующих основ­ных компонентов (см.рисунок 4): решателя (интерпретатора); рабочей памяти (РП), называемой также базой данных (БД);  базы знаний (БЗ);  компонентов приобре­тения знаний; объяснительного и диалогового [24].

База данных предназначена для хранения исходных и промежуточных данных решаемой предметной области. База знаний в ЭС предназначена для хранения долгосрочных данных, опи­сывающих рассматриваемую область (а не текущих данных), и правил, описы­вающих целесообразные преобразования данных этой области. Решатель, используя исходные данные из РП и знания из БЗ, формирует такую последовательность правил, которые, будучи примененными к исходным данным, приводят к решению задачи. Компонент приобретения знаний автоматизирует процесс наполнения ЭС знаниями, осуществляемый пользователем-экспертом. Объяснительный компонент объясняет, как система получила решение задачи (или почему она не получила решения) и какие знания она при этом использо­вала, что облегчает эксперту тестирование системы и повышает доверие пользо­вателя к полученному результату.

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

 

 

 

 

 

 

 

 

Классификация языков и методов  представления знаний.  Языки представления знаний являются средством, позволяющим решать задачи. По существу, способ представления знания должен обеспечить естественную структуру выражения знания, позволяющую решить проблему. Способ представления должен сделать это знание доступным компьютеру и помочь программисту описать его структуру. Вообще говоря, задачи ИИ не решают путем их упрощения и “подгонки” к уже имеющимся понятиям, предлагаемым традиционными формальными системами, например, массивам. Эти задачи связаны скорее с качественными параметрами, а не вычислениями, с организацией больших объемов знаний, а не реализацией отдельного четкого алгоритма. Чтобы удовлетворять этим требованиям, язык представлений искусственного интеллекта должен обладать следующими свойствами:

1)   обрабатывать знания, выраженные в качественно форме;

2)   получать новые знания из набора фактов и правил;

3)   отображать общие принципы и конкретные ситуации;

4)   передавать сложные семантические значения;

5)   обеспечивать рассуждения на мета уровне.

Типичными моделями представления знаний являются: логическая модель; продукционная модель; модель, основанная на использовании фреймов; модель семантической сети [18,19]. Язык, используемый для разработки систем, спроектированных на основе этих моделей, называется языком представления знаний. Логическая модель используется для представления знаний в системе логики предикатов первого порядка и выведения заключений с помощью силлогизма. В настоящее время не во всех областях знаний можно построить экспертные системы. Для задачи “представления знаний” должны быть выполнены следующие условия:

 1)должен быть по меньшей мере, один человек-эксперт, который хорошо понимает задачу;

2)основным источником деятельности эксперта служат специальные знания, оценки и опыт;

3)эксперт должен быть способен четко сформулировать эти специальные знания, оценки и опыт, а также объяснить методы, которые надо применить при решении данной задачи;

4)задача должна иметь четко ограниченную область применения.

Иногда экспертные системы можно строить, не следуя точно указанным выше условиям. Например, в постановке задачи могут участвовать несколько экспертов. Структура экспертной системы является модульной. Факты и другие знания о данной области отделяются от процедур вывода или структуры управления, предназначенной для применения этих фактов, в то время как другая часть системы - глобальная база данных является моделью “мира”, связанного с решаемой задачей, с его статусом и историей. Желательно иметь интерфейс на естественном языке, который облегчает как разработку системы, так и ее применение в данной области. В некоторые сложные системы входит модуль, дающий разъяснения о принятых системой решениях и позволяющий пользователю оспаривать решения системы и исследовать лежащие в основе процессы рассуждений, ведущие к этим решениям. Экспертные системы отличаются от большинства обычных компьютерных программ несколькими важными аспектами. В обычных компьютерных программах знания и методы для использования этих знаний заложены таким образом, что изменить программу весьма сложно. В экспертной системе обычно имеется четкое разделение между общими знаниями о задаче (база знаний) и информацией о текущей задаче (входные данные), а также методами (правилами вывода), необходимыми для применения общих знаний к конкретной задаче. В результате программу можно видоизменять путем простой модификации базы знаний. Это особенно верно для систем, основанных на правилах, где система может быть изменена путем простого добавления или извлечения правил из базы знаний.

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

1) обычный пользователь (эксперт), которому требуется консультация экспертной системы - диалоговый сеанс работы с ней, в процессе которой она решает некоторую экспертную задачу;

2) экспертная группа инженерии знаний, состоящая из экспертов в предметной области и инженеров знаний. В функции этой группы входит заполнение базы знаний, осуществляемое с помощью специализированной диалоговой компоненты ЭС - подсистемы приобретения знаний, которая позволяет частично автоматизировать этот процесс. Диалог с системой осуществляется через диалоговый процессор - специальную компоненту ЭС. Существуют две основные формы диалога с ЭС:

1) диалог на ограниченном подмножестве естественного языка, с использованием  словаря – меню, при котором на каждом шаге диалога система предлагает выбор профессионального лексикона экспертов;

2) диалог на основе из нескольких возможных действий эксперта.

 

Лекция 11. Экспертные системы. Продукционные системы

 

Цель лекций. Знакомство с моделью продукционного типа. Вывод на основе данных. Способы, используемые в продукционной модели.

Содержание лекций. Факты и правила в продукционной модели. Компоненты продукционной модели. Механизм вывода. Поиск на основе цели и на основе данных.  Компоненты диалогов, компоненты объяснение и приобретение знаний продукционной модели.

В экспертных системах, основанных на правилах, знания о решении задач представляют в виде правил "если..., то...". Этот подход, являясь одним из старейших методов представления знаний о предметной области в экспертной системе. В системе, основанной на правилах, пары "условие-действие" представляются правилами "если..., то...", в которых посылка (часть если) соответствует условию, а заключение (часть то) - действию. Если условие удовлетворяется, экспертная система осуществляет действие, означающее истинность заключения. Данные частных случаев можно хранить в рабочей памяти. Механизм вывода осуществляет цикл продукционной системы "распознавание-действие". При этом управление может осуществляться либо на основе данных, либо на основе цели. Наиболее распространенный способ представления знаний - в виде конкретных фактов и правил, по которым из имеющихся фактов могут быть выведены новые. Факты представлены, например, в виде троек: (АТРИБУТ ОБЪЕКТ ЗНАЧЕНИЕ). Такой факт означает, что заданный объект имеет заданный атрибут   (свойства) с заданным значением. Например, тройка (ТЕМПЕРАТУРА  ПАЦИЕНТ1 37.5) представляет факт «температура   больного, обозначаемого ПАЦИЕНТ1, равна 37.5». В более простых случаях факт выражается неконкретным значением атрибута, а каким-либо простым утверждением, которое может быть истинным или ложным.  Правила в базе знаний имеют вид: ЕСЛИ А  ТО  S, где  А - условие; S - действие. Действие S исполняется, если А истинно. Наиболее часто действие S так же, как и условие, представляет собой утверждение, которое может быть выведено системой, если истинно условие правила А. Правила в базе знаний  служат для представления эвристических знаний, т.е. неформальных правил рассуждения, вырабатываемых экспертом на основе опыта его деятельности. В качестве условия A может выступать либо факт (как в данном примере), либо несколько фактов A1, ... , AN, соединенные логической операцией «и»: «A1 и A2 и ... и AN». В математической логике такое выражение называется коньюнкцией. Оно считается истинным в том случае, если истинны все его компоненты. Продукционная модель имеет вид:

(i); P; Q: Ai => Bj ; N;

где i - номер правила; P- приоритет правила; Q - область применения правила  Ai => Bj – ядро продукции; i, j - с какой части берется утверждение, чаще всего i = база данных, база знаний, диалог, О (блок объяснения);  j- тоже самое и помимо этого добавляется блок приобретение знаний. АБД => ВБД, N- комментарии к продукции [22]. Таким образом, действия модели продукционного типа  основаны на применении правила вывода, суть которого состоит в следующем: пусть известно, что истинно утверждение А и существует правило вида «Если А, то В», тогда утверждение В так же истинно. Правила срабатывают, когда находятся факты, удовлетворяющие их левой части: если истинна посылка, то должно быть истинно и заключение.   Хотя в принципе на первый взгляд, кажется, что такой вывод легко может быть реализован на компьютере, тем не менее, на практике человеческий мозг все равно оказывается более эффективным при решении задач. Если экспертную систему рассматривать как продукционную, то базу знаний о предметной области можно считать набором продукционных правил. В системе, основанной на правилах, если условие удовлетворяется, экспертная система осуществляет действие, означающее истинность заключения. Данные частных случаев можно хранить в рабочей памяти. Механизм вывода осуществляет цикл продукционной системы "распознавание-действие". При этом управление может осуществляться либо на основе данных, либо на основе цели. Многие предметные области больше соответствуют прямому поиску. Например, в проблеме интерпретации большая часть информации представляет собой исходные данные, при этом часто трудно сформулировать гипотезы или цель. Это приводит к прямому процессу рассуждения, при котором факты помещаются в рабочую память, и система ищет для них интерпретацию. В экспертной системе на основе цели в рабочую память помещается целевое выражение. Система сопоставляет заключения правил с целевым выражением и помещает их предпосылки в рабочую память. Это соответствует декомпозиции проблемы на более простые подцели. На следующей итерации работы продукционной системы процесс продолжается, эти предпосылки становятся новыми подцелями, которые сопоставляются с заключениями правил. Система работает до тех пор, пока все подцели в рабочей памяти не станут истинными, подтверждая гипотезу. Таким образом, обратный поиск в экспертной системе приближенно соответствует процессу проверки гипо­тез при решении проблем человеком-экспертом [23].

В экспертной системе, чтобы достичь подцели, следует запросить информацию у поль­зователя. В некоторых экспертных системах разработчики определяют, какие подцели мо­гут достигаться путем запроса к пользователю. Другие системы обращаются к пользователю, если не могут вывести истинность подцели на основе правил из базы знаний. Экспертная система должна быть открытой для инспектирования, легко модифицируемой и эвристической по природе. Архитектура продукционной системы является важным фактором для каждого из этих требований. Легкость модификации, например, определяется синтаксической независимостью продукционных правил: каждое правило является "глыбой" знаний, которая может модифицироваться независимо. Однако существуют семантические ограничения, поскольку индивидуальные правила связаны по смыслу. Значит, они должны быть согласованы в любом процессе редактирования или модификации. Ниже мы обсудим генерацию объяснений и управление выводом.

Объяснения и прозрачность при рассуждениях на основе цели. Продукционная система осуществляет поиск на графе. Программы подсистемы объяснений отслеживают процесс поиска на графе и используют эту информацию, чтобы отвечать на вопросы пользователя. С помощью продукционных правил каждый шаг процесса рассуждений документируется автоматически. Обычно экспертные системы, основанные на правилах, отвечают на два вопроса -"почему?" и "как?". Вопрос "почему?" возникает, когда программа запрашивает информацию у пользователя, и его ответ означает "почему вы запрашиваете эту информацию?". Ответом является текущее правило, которое система пытается активизировать. Ответом на вопрос: "Как вы получили этот результат?" - является последовательность правил, использованных для достижения цели. Итак, система, основанная на знаниях, отвечает на вопросы "почему?", отображая текущее правило, которое она пытается активизировать. В ответ на вопросы "как?" -  она предоставляет последовательность рассуждений, которая привела к цели. Хотя эти механизмы являются концептуально простыми, они обладают хорошими возможностями объяснений, если база знаний организована логически грамотно. Если объяснения должны быть логичными, важно не только, чтобы база знаний выдавала корректный ответ, но и чтобы каждое правило соответство­вало одному шагу процесса решения проблемы. Если в одном правиле базы знаний заключено несколько шагов или правила сформулированы произвольным образом, получить правильные ответы на вопросы "как?" и "почему?" будет сложнее. Это не только подрывает доверие пользователя к системе, но и делает программу более трудной для понимания и модификации разработчиками.

Использование продукционной системы для рассуждений на основе данных. Пример диагностики автомобиля иллюстрирует использование про­дукционной системы для реализации поиска на основе цели. В ней использовался поиск в глубину, так как перед переходом к соседним целям для каждой обнаруженной в базе правил подцели производился исчерпывающий поиск. Однако продукционная система является также идеальной архитектурой и для рассуждений на основе данных. В рассуждениях на основе данных чаще применяется поиск в ширину. Алгоритм очень прост: содержимое рабочей памяти сравнивается с предпосылками каждого правила в упорядоченной базе правил. Если данные в рабочей памяти приводят к активизации правила, результат помещается в рабочую память, и управление передается следую­щему правилу. После рассмотрения всех правил поиск повторяется сначала.

Рассмотрим пример. При разработке экспертной системы «Консалтинговые услуги» использована продукционная модель представления знаний. В качестве примера рассмотрим правило, словесное описание которого выглядит так: «Если процессор = «Celeron» и память = 256, то вывести данные обо всех компьютерах с такими параметрами». На языке запросов SQL данное правило запишется следующим образом:

SELECT * FROM basic WHERE proc like 'Celeron%' and memory='256' ORDER BY  art

Ядро продукции для рассмотренного правила имеет вид:

А1БД И А2БД Þ ВБЗ, то есть левая часть берется из БД, а правая - из БЗ.

При разработке экспертной системы «Консалтинговые услуги» была использована стратегия поиска, использующего ответ на вопрос  «Почему?».

Ответ системы будет выглядеть следующим образом: «Потому что «вы выбрали размер монитора, равный 17» (посылка А1) ИЛИ «вы не задавали тип процессора» (посылка А2),  поэтому «не указан размер жесткого диска » (заключение В1), «вы задали размер памяти =120» (посылка А3) ИЛИ «вы не задали размер видеокарты» (посылка А4), поэтому «не указан цена процессора » (заключение В2), так как В1 ИЛИ В2  не истинны, поэтому «не указана общая цена компьютера » (заключение В4) (см.рисунок 3).

Для вывода допустимо использовать сеть вывода, состоящую из нескольких правил. Например, сеть вывода состоит из трех правил:

- П1: Если А1 И А2 истина, то В1- истина;

- П2: Если А3 И А4 истина, то В2- истина;

- П3: Если В1 И В2 истина, то В3- истина.

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

  

Рисунок 5 - Схема блока Объяснение

 

Упорядочим слабые и сильные стороны хорошо известных  систем продукций. Сильные стороны: простота создания и понимание отдельных правил; простота пополнения, модификации и аннулирования; простота механизма логического вывода. Слабые стороны: неясность взаимных отношений правил; сложность оценки целостного образа знаний; крайне низкая эффективность обработки; отличие от человеческой структуры знаний; отсутствие гибкости в логическом выводе [24].

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

 

Лекция 12. Экспертные системы. Модели фрейма и семантических сетей

 

Цель лекций. Основные понятия о фреймах и семантических объектах. Способы выводов в этих моделях.

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

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

f[<N1, V1>, < N2, V2> , ... ,  < Nk, Vk > ], где  f - имя фрейма; пара  < N1, V1> -   1-ый слот, Ni - имя слота и Vi - его значение. Значение слота может быть представлено последовательностью:

 <К1><L1>; ... ; <Кп> <Lп>; <R1>;  ... ; <Rm>,

где К1 - имена атрибутов, характерных для данного слота; Ln - значение этих атрибутов, характерных для данного слота; Rj - различные ссылки на другие слоты.

Фреймовая модель представления знаний была предложена М.Минским в 1979 году и является развитием семантических сетей. Марвин Мински, профессор Массачусетского технологического института, основатель лаборатории искусственного интеллекта, автора ряда фундаментальных работ. Фрейм - абстрактный образ для представления некоторого стереотипа восприятия. Каждый фрейм имеет собственное название и список слотов и их значений. Слот может быть терминальным (листом иерархии) или представлять собой фрейм нижнего уровня. Значениями могут быть данные любого типа, а также название другого фрейма. Таким образом, фреймы образуют сеть. Кроме того, существует связь между фреймами типа АКО (a kind of), которая указывает на фрейм более высокого уровня иерархии, откуда неявно наследуются список и значения слотов. При этом возможно множественное наследование – перенос свойств от нескольких прототипов [19]. Любой фрейм может быть представлен следующим образом:

(ИМЯ ФРЕЙМА:

(имя 1-го слота: значение 1-го слота),

(имя 2-го слота: значение 2-го слота),

…………….

(имя N-гo слота: значение N-го слота)).

 

Фреймовая модель представляет собой систематизированную психологическую модель памяти человека и его сознания. Фреймы – это фрагменты знания, предназначенные для представления стандартных ситуаций. Фреймы имеют вид структурированных компонентов ситуаций, называемых слотами. Достоинство фрейма - представления во многом основываются на включении в него предположений и ожиданий. Это достигается за счет присвоения по умолчанию слотам фрейма стандартных ситуаций. В процессе поиска решений эти значения могут быть заменены более достоверными. Некоторые переменные выделены таким образом, что об их значениях система должна спросить пользователя. Часть переменных определяется посредством встроенных процедур, называемых внутренними. По мере присвоения переменным определенных значений осуществляется вызов других процедур. Этот тип представления комбинирует декларативные и процедурные знания. Для многих предметных областей фреймовые модели являются основным способом формализации знаний. Структуры данных фрейма.  Фрейм, как показано на рисунке 6, представлен определенной структурой данных. Фреймовая система - это иерархическая структура, узлами которой являются подобные фреймы. Значение каждого элемента, показанного на этом рисунке, рассмотрено ниже [24, 25].

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

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

 

 

Имя фрейма

 


Имя                       Указатель           Демон

                     фрейма                наследования

 


Слот 1

 

 

 

 

Слот 2

 

 

 

 

 

 

 

 

Слот n

 

 

 

 

Имя              Указатель             Значение

                    Слота        атрибутов слота                 слота

 

Рисунок 6 - Структура данных фрейма

 

Способы получения значений слотов:

1)По умолчанию от прототипа (родителя) Слоту присваивается значение, определенное по умолчанию во фрейме-прототипе, некоторые стандартные значения.

2)Через наследование. Отличается от первого способа тем, что значение задано в специальном слоте родительского фрейма, соединенного с текущим связью AKO.

3)По формуле. Слоту назначается формула, результат вычисления которой является значением слота.

4)Через присоединенную процедуру. Слоту назначается процедура, позволяющая получить значение слота алгоритмически.

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

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

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

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

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

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

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

Типы фреймов. Фреймы подразделяются на: фрейм-экземпляр – конкретная реализация фрейма, описывающая текущее состояние в предметной области; фрейм-образец – шаблон для описания объектов или допустимых ситуаций предметной области; фрейм-класс – фрейм верхнего уровня для представления совокупности фреймов образцов.

Состав фреймов и слотов в каждой конкретной фреймовой модели может быть разный, однако в рамках одной системы целесообразно единое представление для устранения лишнего усложнения. Глубина вложенности слотов во фрейме (число уровней) зависит от предметной области и языка, реализующего модель. Фреймы-прототипы (шаблоны, образцы) интенсиональные, они отражают знания об абстрактных стереотипных понятиях, которые являются классами каких-то конкретных объектов: человек, автомобиль. Фреймы-экземпляры (примеры) экстенсиональные отражают знания о конкретных фактах предметной области. Например, Талканбаев Кайрат имеет Мерседес. По функциональному назначению фреймы подразделяются на: Фреймы-структуры (объекты) декларативно отображают абстрактные и конкретные предметы и понятия предметной области (содержат набор характеристик, описывающий объект или понятие): заем, залог, вексель, человек, лекция; Фреймы-операции процедурные отображают различные процессы преобразования или использование объектов предметной области (содержат набор характеристик процесса), процессы получения заёма, синтеза устройств; Фреймы-Ситуации прагматические отображают типичные ситуации, в которых могут находиться фреймы объекты и фреймы роли (содержат набор характеристик, идентифицирующих ситуацию): авария, тревога, рабочий режим устройства; Фреймы-Сценарии  технологические отображают развитие ситуации: типовую структуру для некоторого действия, понятия, события, отображают динамику (содержат набор характеристик, позволяющих обеспечить развитие системы по данному сценарию) банкротства, празднование именин, сдачу экзамена; Фреймы-роли функциональные отображают типичную роль, выполняемую фреймом-объектом в определенной ситуации (содержат набор характеристик роли): менеджер, кассир, клиент, студент, преподаватель [20].

  Каждый фрейм, как структура хранит знания о предметной области (Фрейм-прототип), а при заполнении слотов знаниями превращается в конкретный фрейм события или явления.

Базовый тип. Процесс, в ходе которого проверяется правильность выбора фрейма, называется процессом сопоставления. Обычно этот процесс осуществляется в соответствии с текущей целью и инфор­мацией (значениями), содержащейся в данном фрей­ме. Другими словами, фрейм содержит условия, ограничивающие значения слота, а цель используется для определения, какое из этих условий, имея отношение к данной ситуации, является релевантным. Фреймовые системы связаны с информационно-по­исковыми сетями [18,19].  Если фрейм-кандидат не соответ­ствует текущей проблеме, другими словами, если установление соответствия с терминалом не вполне отвечает условию метки, такая сеть задает другой фрейм. С помощью подобной межфреймовой струк­туры можно представлять знания, касающиеся фак­тов, сходств и другой информации, полезной для по­нимания. Когда некоторый фрейм выбирается в каче­стве единицы представления некоторого состояния, то в процессе согласования во все терминалы каждого фрейма подставляются такие значения, чтобы выпол­нялись условия в соответствующих местах. В итоге процесс сопоставления фрейма осуществ­ляется следующим образом:

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

2) в противном случае: если в данном фрейме имеется слот, в котором воз­никла ошибка, касающаяся, например, условия согласованности с информацией, заданной по умолчанию, то необходима информация, обеспечивающая присваи­вание надлежащего значения данному слоту.

3) в качестве последнего шага управление передается другому надлежащему фрейму из этой системы. Если и этот фрейм не подходит, то управление передается соответствующему фрейму из другой фреймовой си­стемы.

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

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

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

Отношения «абстрактное-конкретное» и «це­лое-часть». Рассмотренная выше иерархическая структура основывается на этих отношениях.

Представление знаний семантическими сетями. Одним из способов представления знаний является семантическая сеть. Изначально семантическая сеть была задумана как модель представления структуры долговременной памяти в психологии, но впоследствии стала одним из основных способов представления знаний в инженерии знаний. Семантика означает определенные отношения между символами и объектами, представленными этими символами, а прагматика – выразительные отношения между символами и создателями этих символов. Первоначально в психологии изучались объекты, именуемые семантические с точки зрения известных ассоциативных свойств, накапливаемых в системе обучения и поведения человека. Затем были изучены принцип действия человеческой памяти, в частности, предположительные структурные модели долговременной памяти, и созданы моделирующие программы, понимающие смысл слов.  Одной из структурных моделей долговременной памяти является предложенная Куиллианом модель понимания смысла слов, получившая название TLC-модели (Teachable Language Comprehender: доступный механизм понимания языка). В данной модели для описания структуры долговременной памяти была использована сетевая структура как способ представления семантических отношений между концептами. Данная модель имитирует естественное понимание и использования языка человеком. Поэтому основной ее идеей было описание значений класса, к которому принадлежит объект, его прототипа и установление связи со словами, отображающими свойства объекта. Модели Куиллиана, концептуальные объекты, представлены ассоциативными сетями, состоящими из вершин, показывающих концепты, и дуг, показывающих отношения между концептами. Важность модели семантической сети Куиллиана с точки зрения многочисленных приложений определяется следующими моментами:

1) в отличие от традиционных методов семантической обработки с анализом  структуры предложения были предложены новые парадигмы в качестве модели представления структуры долговременной памяти, в которой придается значение объему языковой активности;

2) был предложен способ описания структуры отношений между фактами и понятиями с помощью средства, называемого семантической сетью, отличающейся несложным представлением понятий, а также способ семантической обработки в мире понятий на основе смысловой связи между прототипами;

3) была создана реальная система TLC, осуществлено моделирование человеческой памяти и разработана технологическая сторона концепции понимания смысла. Во многих областях искусственного  интеллекта решение задачи требует использования высоко структурированных  взаимосвязанных знаний [25].

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

              hassize(canary,small)

              hascovering(bird,feathers)

              hascolor(canary,yellow)

              hasproperty(bird,files)

              isa(canary,bird)

              isa(bird,vertebrate)

     Предикатное описание можно представить графически, используя для отображения предикатов, определяющих отношения, дуги (arc) или связи (link) графа (см.рисунок 7). Такое описание, называемое семантической сетью, является фундаментальной методикой представления семантического значения. Поскольку отношения явно выражены связями графа, алгоритм рассуждений о предметной области может строить соответствующие ассоциации, просто следуя по связям. В примере с канарейкой системе нужно проследовать только по двум дугам, чтобы решить, что канарейка – это позвоночное животное. Это значительно эффективнее, чем утомительный исчерпывающий поиск в базе данных, содержащей описание на языке исчисления предикатов вида isa(X,Y). Кроме того, знания могут быть организованы так, чтобы отражать естественную структуру экземпляра класса из данной предметной области. Теория графов эффективно и естественно выражает сложные семантические знания. Кроме того, она позволяет описывать структурную организацию базы знаний.

vertebrate

 

 
 

 

 

 

    files

 

 

    bird

 

feathers  

 
                             hascovering                           hasproperty

                                                                                                         

 

 

bluebird 

 

    blue

 

small

 
                                hassize                                      hascolor

 

 


Рисунок 7- Описание семантической сети для канарейки

 

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

 

Лекция 13. Экспертные системы. Особенности проектирования экспертных систем

 

Цель лекций. Знакомство с критериями  использования  и прототипами экспертных систем.

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

Разработка ЭС существенно отличается от разработки обычного программного продукта. Опыт разработки ранних экспертных систем показал, что использование при их разработке методологии, принятой в традиционном программировании, либо чрезмерно затягивает процесс создания ЭС, либо вообще приводит к отрицательному результату. Дело в том, что неформализованные задачи, решаемые в ЭС, отсутствие завершенной теории ЭС и методологии их раз­работки приводят к необходимости модифицировать принципы и способы по­строения ЭС в ходе процесса разработки по мере того, как увеличивается знание разработчиков о проблемной области. При разработке ЭС используется концепция «быстрого прототипа». Суть ее состоит в том, что разработчики не пытаются сразу создать конечный продукт. На начальном этапе они создают прототип ЭС, который должен удовлетворять двум противоречивым требованиям: с одной стороны, решать типичные задачи конкретного приложения, а с другой - время и тру­доемкость его разработки должны быть весьма незначительны, чтобы можно было максимально сделать параллельным процесс накопления и отладки знаний с процессом выбора программных средств. Для удовлетворения указанных требований при создании прототипа, как правило, используются разнообразные инструментальные средства, ускоряющие процесс проектирования. Экспертные системы отличаются от большинства обычных компьютерных программ несколькими важными аспектами. В обычных компьютерных программах знания и методы для использования этих знаний заложены таким образом, что изменить программу весьма сложно. В экспертной системе обычно имеется четкое разделение между общими знаниями о задаче и информацией о текущей задаче, а также методами, необходимыми для применения общих знаний к конкретной задаче. В результате программу можно видоизменять путем простой модификации базы знаний. Это особенно верно для систем, основанных на правилах, где система может быть изменена путем простого добавления или извлечения правил из базы знаний.

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

1) данные и знания надежны и не меняются со временем;

2) пространство возможных решений относительно невелико;

3) в процессе решения задачи должны использоваться формальные рассуждения;

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

Ограничения в применение экспертных систем. Даже лучшие из существующих ЭС, которые эффективно функционируют как на больших. Так и на мини-ЭВМ, имеют определенные ограничения по сравнению с человеком-экспертом. Большинство ЭС не очень комфортны для конечного пользователя. Если вы не имеете некоторого опыта работы с такими системами, то у вас могут возникнуть серьезные трудности. Многие системы оказываются доступными только тем экспертам, которые сами создавали базу знаний. Вопросно-ответный режим, обычно принятый в таких системах, замедляет получение решений. Например, без системы MYCIN врач может (а часто и должен) принять решение значительно быстрее, чем с ее помощью.  Навыки системы не возрастают после сеанса экспертизы.  Все еще остается проблемой приведение знаний, полученных от эксперта, к виду, обеспечивающему их эффективную машинную реализацию.  ЭС могут быть способным обучаться, но не обладают здравым смыслом. Домашние кошки способны обучаться даже без специальной дрессировки, ребенок в состоянии легко уяснить, что он станет мокрым, если опрокинет на себя стакан с водой, однако, если начать выливать кофе на клавиатуру компьютера, у него не хватит “ума” отодвинуть ее. ЭС не применим в больших предметных областях. Их использование ограничивается предметными областями, в которых эксперт может принять решение за время от нескольких минут до нескольких часов.  В тех областях, где отсутствуют эксперты (например, в астрологии), применение ЭС оказывается невозможным. Имеет смысл привлекать ЭС только для решения когнитивных задач. Теннис, езда на велосипеде не могут являться предметной областью для ЭС, однако такие системы можно использовать при формировании футбольных команд.  Человек-эксперт при решении задач обычно обращается к своей интуиции или здравому смыслу, если отсутствуют формальные методы решения или аналоги таких задач. Системы, основанные на знаниях, оказываются неэффективными при необходимости проведения скрупулезного анализа, когда число “решений” зависит от тысяч различных возможностей и многих переменных, которые изменяются во времени. В таких случаях лучше использовать базы данных с интерфейсом на естественном языке [23].

Преимущества ЭС перед человеком - экспертом.  Системы, основанные на знаниях, имеют определенные преимущества перед человеком-экспертом:

1)  У них нет предубеждений.

2)  Они не делают поспешных выводов.

3)  Эти системы работают в режиме, рассматривая все детали, часто выбирая наилучшую альтернативу из всех возможных.

4)  База знаний может быть очень и очень большой. Будучи введены в машину один раз, знания сохраняются навсегда. Человек же имеет ограниченную базу знаний, и если данные долгое время не используются, то они забываются и навсегда теряются.

 

 

Рисунок 8 - Три вида программирования

 

Экспертные системы – часть программ искусственного интеллекта. Обычно способы программирования можно разделить нв две группы.   Традиционное процедурное программирование и программирование методами искусственного интеллекта. В процедурном программировании компьютеру очень тщательно объяснется шаги действия. По такому способу обачно разрабатываются программы на   Бейсике, Фортране, Паскале, и в других язиках процедурного программирования [21]. А программы ЭС входят в состав программ ИИ и могут относится к видам программ декларативного программирования (см.рисунок 8).

Отличие программ ИИ от традиционных программ отражется также в том, что они используют следующее множество операторов:

Вызов процедуры;

Последовательное выполнение;

Рекурсия.

В процедурном программировании при работе сданными используются опреаторы присваивания: «=» или « :- », например:

if-then-else - переход;

Do- while – вызов процедуры;

repeat-until – выполнение по очереди.

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

Отличие между программами искусственного интеллекта и процедурных языков можно увидеть по следующим простым признакам: если программу удобно писать на  Фортране и  на Паскале, то такую программу трудно написать на ЛИСПе и ПРОЛОГе [14,24].

В качестве примеров можно привести следующие программы ИИ, которые не относятся программам ЭС.  В такой список можно отнести:

-       просмотр рассказа маленького ребенка (3 года ) и пересказ смысла такого рассказа. Такая программа должна «понимать» на определенном уровне естественный язык,  владеть «умением» выявления причинно-следственных связей  рассказа;

-       печать на принтер текст слов человеческого голоса. Человек пользователь говорит в микрофон, а программа  печатает его текст на принтер;

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

-       программы автоматический доказывающие математические теоремы и программы, которые могут найти новые теоремы;

-       программы,  которые делают сложный анализ видеоматериалов снятых телекамерой.

При проектировании программ ЭС необходимо в первую очередь понять цель создания. Основная цель при проектировании ЭС - создать такие компьютерные программы, которые смогли бы решить проблему в данной области не хуже человека-специалиста  [25].

К параметрам оценки программных продуктов ЭС можно отнести следующие признаки:

-       способность программ повторения основных функции;

-       способность программ объяснить свое решение на понятном языке;

-       способность программ вести преговоры с любым пользователем с помощью диалога на естественном языке.

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

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

-         выделение и управление знаниями;

-         способы поиска;

-         эвристические способы;

-         основанный на правилах автоматический анализ;

-         использование естественного языка.

Хотя эти элементы по отдельности являются простыми, при объединений они усиливая друг друга могут дать мощную компьютерную программу. Группировку основных элементов архитектуры экспертных систем можно представить в виде, представленном на рисунке 9. Проведем краткое описание этих групп.

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

Эвристики. Если при нахождении решения задачи нет определенного алгоритма или формулы, то поиск осуществляется с помощью правил, их иногда называют – эвристиками.

 

 

Рисунок 9 - Основные элементы архитектуры ЭС

 

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

Автоматический анализ. В экспертных системах способы поиска работают обычными правилами. Например, продукционное правило вида: «если А истина, то выполни В» может работать в программах экспертных систем.  Если бы у нас была возможность проблемы имеющиеся в любой предметной области смоделировать с помощью таких правил, тогда бы мы смогли  провести процесс автоматического анализа.  Основное понятие этого процесса – логический вывод. Он выполняется в двух аспектах. Во-первых, в таком выводе используется имеющиеся факты и правила для проверки гипотезы и выполняется попытка доказать, что она истинна. Такой ввод называется прямым выводом.  Во-вторых, из утвержденного вывода выполняется попытка  вывода истинных фактов. Его называют способом обратного вывода.

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

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

 

Лекция 14. Экспертные системы. Этапы и инструментальные средства создания экспертных систем

 

Цель лекций. Знакомство с этапами и инструментальными средствами создания экспертных систем.

Содержание лекций. Этапы создания экспертных систем. Основные функций этапов экспертных систем. Факторы развития базы знаний. Инструментальные средства создания экспертных систем их классификация.

В ходе работ по созданию ЭС сложилась определенная технология их раз­работки, включающая шесть следующих этапов: идентификация, концептуализация, формализация, выполнение,  тестирование, опытная эксплуатация [23].

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

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

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

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

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

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

В развитых зарубежных странах специальность “инженер знаний” введена во многих вузах, в нашей стране основы инженерии знаний изучаются пока в рамках специализаций по системному программированию. Функции эксперта и инженера знаний редко совмещаются в одном лице. Чаще функции инженера знаний выполняет разработчик ЭС. Как показал опыт многих разработок, для первоначального приобретения знаний, в которых участвуют эксперты, инженеры знаний и разработчики ЭС, требуется активная работа всех трех категорий специалистов. Она может длиться от нескольких недель до нескольких месяцев.

На этапе приобретения знаний могут возникнуть трудности и психологического порядка: эксперт может препятствовать передаче своих знаний ЭС, полагая, что это снизит его престиж как специалиста и создаст предпосылки для замены его “машиной”. Однако эти опасения лишены оснований: ЭС “уверенно” работает лишь в типовых ситуациях, а также удобна в случаях, когда человек находится в состоянии стресса, в наиболее сложных ситуациях, требующих нестандартных рассуждений и оценок, эксперт- человек незаменим.  Третья серьезная трудность - в очень большой трудоемкости создания ЭС : требуется разработать средства управления базой знаний, логического вывода, диалогового взаимодействия с пользователем и т.д. Объем пограммирования столь велик, а программы столь сложны и нетрадиционны, что имеет смысл, как это принято сейчас при разработке больших программ, на первом этапе создать демонстрационный прототип системы - предварительный вариант, в котором в упрощенном виде реализованы лишь ее основные планируемые возможности и которая будет служить для заказчика подтверждением того, что разработка ЭС для решения данной задачи принципиально возможна, а для разработчиков- основой для последующего улучшения и развития системы. 

Одной из причин неудач в создании ЭС стала недооценка авторами ЭС объемов и роли неявных знаний. Системы, базы знаний которых создавались на основе справочников, в лучшем случае так справочниками и остались. Большинство же таких систем оказывались даже хуже справочников, так как сковывали исследовательскую мысль пользователя. Вторым  “узким местом” ЭС оказалась модель, на которой были основаны их первые экземпляры, и лишь модель знаний, принимающая вид пороговой направленной иерархической сети с возможностью выбора в конечном из логических узлов (где каждая отдельная ситуация похожа на дерево с листьями), может стать базой для построения ЭС.

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

Рассмотрим факторы, стимулировавшие развитие систем с базами знаний:

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

- разработаны новые технологии создания баз знаний, является необходимым средством, которое может изменить бизнес- процесс;

- современные системы реализованы не на специализированном, а на стандартном оборудовании.

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

Объектная технология, на основе которой могут создаваться и развиваться современные ЭС - значительный шаг вперед по сравнению с CASE-средствами, так как она похожа на наше восприятие окружающей действительности. Наше представление о моделировании меняется, то же самое происходит и с объектами, поэтому сопровождение программируемых объектов может выполняться аналогично приспособлению наших умозрительных образов к изменению окружающих условий. Данная технология прекрасно подходит аналитикам и программистам, так как очень напоминает стратегию решения проблем  и соответствует мыслительным процессам людей, считающихся экспертами в своей области.

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

Методика объектно-ориентированного программирования основана на модели, напоминающей образы, возникающие в мозгу аналитика, которая представляет предметы и процессы в виде объектов и связей между ними. Наблюдая событие, эксперт легко выделяет знакомые образы. Для решения проблем он испытывает конкретные правила, рассматривая при этом исследуемую проблему под определенным ракурсом.

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

Инструментальные средства создания ЭС. Подчеркнем, что развитие систем, автоматизирующих разработку приводит к появлению инструментальных средств, которые можно назвать настраиваемыми оболочками. Эти инструментальные средства позволяют разработчику использовать оболочку не как нечто неизменное (как имело место ранее в EMYCIN, KAS и др.), а генерировать оболочку из множества механизмов, имеющихся в таких системах. Типичными примерами таких инструментальных средств являются KEE, ART, ЭКСПЕРТИЗА, ГЛОБ.   Инструментальные средства можно классифицировать и по классам ЭС на:

-       инструментальные средства для создания простых ЭС;

-       инструментальные средства для создания сложных ЭС.

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

 

Лекция 15. Экспертные системы. Существующие экспертные системы.  Классификация экспертных систем

 

Цель лекций. Знакомство с историей развития экспертных систем. Область применения и возможности существующих экспертных систем.

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

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

Области применения систем, основанных на знаниях, могут быть сгруппированы в несколько основных классов: медицинская диагностика, контроль и управление, диагностика неисправностей в механических и электрических устройствах, обучение [21,22].

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

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

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

Интерпретация. Интерпретирующие системы обладают способностью получать определенные заключения на основе результатов наблюдения. Система PROSPECTOR, одна из наиболее известных систем интерпретирующего типа, объединяет знания девяти экспертов. Используя сочетания девяти методов экспертизы, системе удалось обнаружить залежи руды стоимостью в миллион долларов, причем наличие этих залежей не предполагал ни один из девяти экспертов. Другая интерпретирующая система- HASP/SIAP. Она определяет местоположение и типы судов в тихом океане по данным акустических систем слежения.  

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

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

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

Существующие ЭС. Классификация ЭС. Наиболее  известные ЭС,  разработанные в 60-70-х годах, стали в своих областях уже классическими. По происхождению, предметным областям и по преемственности применяемых идей, методов и инструментальных программных средств их можно разделить на несколько семейств:

1)       MYCIN-EMYCIN-TEIREIAS-PUFF-NEOMYCIN. Это семейство медицинских ЭС и сервисных программных средств для их построения;

2)       PROSPECTOR-KAS. PROSPECTOR-предназначена для поиска (предсказания) месторождений на основе геологических анализов. KAS- система приобретения знаний для  PROSPECTOR;

3)       CASNET-EXPERT. Система CASNET- медицинская ЭС для диагностики выдачи рекомендаций по лечению глазных заболеваний. На ее основе разработан язык инженерии знаний EXPERT, с помощью которого создан ряд других медицинских диагностических систем;

4)       HEARSAY-HEARSAY-2-HEARSAY-3-AGE. Первые две системы этого ряда являются развитием интеллектуальной системы распознавания слитной человеческой речи, слова которой берутся из заданного словаря. Эти системы отличаются оригинальной структурой, основанной на использовании доски объявлений - глобальной базы данных, содержащей текущие результаты работы системы. В дальнейшем на основе этих систем были созданы инструментальные системы HEARSAY-3 и AGE (Attempt to Generalize - попытка общения) для построения ЭС;

5)       Системы AM (Artifical Mathematician - искусственный математик) и EURISCO были разработаны в Станфордском университете доктором Д.Ленатом для исследовательских и учебных целей. Ленат считает, что эффективность любой ЭС определяется закладываемыми в нее знаниями. По его мнению, чтобы система была способна к обучению, в нее должно быть введено около миллиона сведений общего характера. 

 

Список литературы

1.       Братко И. Программирование на языке Пролог для искусственного интеллекта. - М:Мир, 1990.

2.       Логическое программирование http: //ru.wukipedia.org/wiki/.   

3.       Доорс Дж. И др. Пролог- язык программирования будущего /Пер.с англ. – М.: Финансы и статистика, 1990. - 144 с.

4.       Дж. Стобо «Язык программирования Пролог».- М:Радио и связь 1993.

5.       Клоксин, Меллиш «Программирование на языке Пролог».- М:Мир, 1987.

6.       Л. Стерлинг, Э. Шапиро «Искусство программирования на языке Пролог». М:Мир, 1990.

7.       Хъювенен Э., Сеппянен Й. Мир Лиспа В 2-х т. Т.1: Введение в язык Лисп и функциональное прогаммирование. Пер. С финск. – М.:Мир, 1990. – 447 с.

8.       Хъювенен Э., Сеппянен Й. Мир Лиспа В 2-х т. Т.2: Методы и системы программирования. Пер. С финск. – М.:Мир, 1990. – 319 с.

9.       Сергиевский Г.М.  Функциональное и  Логическое программирование. –М.: Изд.Центр «Академия».  2010. – 320 c.

10.   Семенов М.Ю. Язык Лисп для персональных ЭВМ. - М.: Издательство МГУ, 1989.

11.   Люгер, Джордж,,Ф. Искусственный интеллект: стратегии и методы решения сложных проблем. - М:2003г.- 864 с.

12.   Большакова. И., Мальковский М. Г., Пильщиков В. Н.  Искусственный интеллект. Алгоритмы эвристического поиска (учебное пособие) - М.: Издательский отдел факультета ВМК МГУ, 2002. 83 с.

13.   Нильсон Н. Искусственный интеллект. Методы поиска решений./ Пер. с анг. –М.:Мир, 1973. - С. 270

14.   Д. Марселус. Программирование экспертных систем на Турбо Прологе. Пер. с анг. - М:Финансы и статистика, 1994, - 256 с.

15.   Ахметова М. Функционалдық-логикалық программалау және жасанды зерде жүйелері: Оқу құралы. -  Алматы: «Бастау» баспасы.  – 2012.- 330 б.

16.        Язык программирования Хаскелл http://haskell.org/, http://www.haskell.ru/

17.   Джексон Питер, Введение в экспертные системы./Пер.с англ.: Уч.пособие, 2001. – 624 с.

18.   Представление и использование знаний / Пер. с японск. /Под ред. Х.Уэно,  М.Исидзука, - М.: Мир, 1989. – 220 с.

19.   Приобретение знаний. / Пер. с японск. /Под ред. С.Осуги,  Ю.Саэки М.Исидзука, - М.: Мир, 1990. – 304 с.

20.   Фрейм. Модели представления знаний фреймами. http://alportal.ru.

21.   Попов Э.В. Экспертные системы: Решение неформализованных задач в диалоге с ЭВМ.- Наука, 1987. - 288 с.

22.   Алексеева Е.Ф., Стефанюк В.Л., Экспертные системы – состояние и перспективы. //Изв.АН СССР Техн. кибернетика. 1984. N5. С.153-167.

23.   Построение экспертных систем. Под.редакцией Ф.Хейес Рот, Д.Уотерман, Д.Ленат – М.:Мир, 1987. - 441 с.

24.   Базы знаний и интеллектуальные системы /Т.А.Гаврилова, В.Ф.Хорошевский – СП:Питер, 2000. – 384 с.

25.   Ахметова М. Сарапшы жүйе және оның құрамы: Оқу құралы. – Алматы, ҚазҰТУ, 2004, 100 б.

 

Содержание

 

Введение

3

Лекция 1. Языки искусственного интеллекта. Основы логического программирования

4

Лекция 2. Языки искусственного интеллекта. Работа в Прологе

7

Лекция 3. Языки искусственного интеллекта.  Основы функционального программирования

11

Лекция 4. Языки искусственного интеллекта.  Возможности языков Лисп и Хаскелл

15

Лекция 5. Введение в задачи искусственного интеллекта.  Основные понятия  ИИ

21

Лекция 6. Введение в задачи искусственного интеллекта.  Классификация задач ИИ

24

Лекция 7. Методы решения задач. Методы пространства состояний

27

Лекция 8. Методы решения задач. Эвристический метод и метод редукций

30

Лекция 9. Методы решения задач. Метод исчисления предикатов

33

Лекция 10. Экспертные системы. Модели представления знаний

37

Лекция 11. Экспертные системы. Продукционные системы

42

Лекция 12. Экспертные системы. Модели фрейма и семантических сетей

46

Лекция 13. Экспертные системы. Особенности проектирования экспертных систем

54

Лекция 14. Экспертные системы. Этапы и средства создания ЭС

60

Лекция 15. Экспертные системы. Существующие ЭС. Классификация ЭС

64

Список литературы

67

                                                Сводный план 2012 г. поз.357