СППР

149

Для наглядности приведем лишь дендограммы для подвыборок AviB

(рис. 1.35), C vlD (рис.1.36).

Рис. 1.35 Иерархический перебор гипотез о числе кластеров: а - для подвыборкиА, б -для подвыборки В.

Как видно из рис.1.35 CYab = 0 при кА= кв - 2 что является в данном случае оптимальной кластеризацией. Запишем объединенные адреса объектов, при которых CYab = 0 (табл.1.19).

				Т а б л и ц а 1.19
			Объекты,
	Адрес	Диполь	объединенные в	Номер кластера
			кластер
	II	2-7	1,2,7	I
	IX	1-7
	I	3-8
	III	5-10
	IV	4-5
	V	8-9	3,4,5,6,8,9,10,11	II
	VI	3-9
	VII	4-U
	VIII	4-10
	X	6-9

150

Рис.1.36 Иерархическийперебор гипотез

о числе кластеров: а-для подвыборки С, б -для подвыборкиD

Как видно из рис.1.36 CYcd = 0 при кс = кв = 2 и кс = kD = 3, то есть имеем несколько нулей. Рассчитывая суммарный критерий CYz видно, что CYz = 0 при кл = кв = кс = kD = 2 , что и будет

соответствовать оптимальной кластеризации (табл.1.19).

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

1.9.Языковые средства систем поддержки принятии решений

1.9.1.ЯЗЫКОВЫЕ СРЕДСТВА ПРОГРАММИРОВАНИЯ СППР

ИПРЕДСТАВЛЕНИЯ ЗНАНИЙ В НИХ

Разработка СППР требует не только создания новых моделей и систем1 представления знаний, но также инициирует появление новых языковых

151

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

Классификация языковых средств СППР приведена на рис. f.37

Рис. 1.37 Языковые средстваСППР

Универсальные языки программирования (С, C++, Basic, Pasad, Smalltalk и др.) являются одним из инструментов для создания СППР, в том числе интеллектуальных, поскольку в них можно вьщелить декларативную (описательную) и процедурную (исполнительную) компоненты. В [95] и [96] описаны примеры создания систем, ориентированных на работу со знаниями путем использования универсальных языков. Однако сложность и трудоемкость разработки здесь настолько велики, что реальные (коммерческие) интеллектуальные СППР становятся недоступными для реализации. Именно это послужило толчком к разработке языков и систем, ориентированных на работу со знаниями, которые, в свою очередь, стали основным инструментом для создания интеллектуальных СППР.

К языковым средствам общего назначения относятся такие языки, как Lisp*Prolog, Snobol и Рефап, с их различными модификациями.

Одним	из первых и наиболее популярных языков для реализации
путем и	скутвенного интеллекта вообще и СППР, в частности, является
Ш р который был разработан в Стэнфорде под руководством Дж.
в	начале 60-х годов. Идеологией	языка Lisp является

РРРЧИМйейие данных и программ в одной и той же форме. Благодаря этому* данные могут интерпретироваться как программа, а любая Программа, в свою очередь, может быть интерпретирована как данные для

152

любой другой программы. Язык Lisp называют еще языком функционального программирования.

На сегодняшний день язык Lisp реализован практически на всех платформах ЭВМ, начиная от высокопроизводительных систем фирмы IBM, которіїе снабжаются интерпретаторами и компиляторами таких диалектов Lisp, как Interlisp и Common Lisp (последний претендует на роль стандарта), компьютерах фирмы DEC - диалекты Franz Lisp, Interlisp, Xlisp и кончая персональными компьютерами - диалекты muLisp, IQ-Lisp, Golden CommonLisp.

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

Вяпонском проекте ЭВМ пятого поколения именно Prolog был выбран в качестве базового языка для реализации машины логического вывода.

Внастоящее время язык Prolog так же, как и Lisp реализован на

разных платформах ЭВМ. К числу наиболее популярных отнесем интегрированную среду логического программирования Turbo Prolog [97], реализованную на персональных компьютерах.

К числу наиболее интересных языков СППР общего назначения можно отнести Snobol [98], в рамках которого впервые появилась и была реализована концепция поиска по образцу [45]. Практически, язык Snobol явился одной из первых реализаций продукционной системы.

К числу советских разработок можно отнести язык обработки символьной информации Рефал [102], созданный в ИПМ АН СССР. Рефал задумывался как метаалгоритмический язык, но для пользователя он являлся языком обработки символьной информации. В основу языка положено понятие рекурсивной функции [45], которая является определенной на множестве символьных выражений. В отличие от Lisp, базовой структурой языка Рефал являются не односвязные, а двунаправленные списки.

Язык Рефал нашел применение при решении задач, использующих аналитические преобразования [45], автоматизации построения трансляторов [103], а также в качестве инструментальной среды для реализации языков представления знаний [45]. Общей чертой всех перечисленных задач являются сложные преобразования над объектами^ определенные в некоторых формализованных языках.

153

К другой группе языков СППР, ориентированных на программирование поисковых задач (программирование интеллектуальных решателей) можно отнести Planner, Conniver и QA-4. В основном, они ориентированы на такую научную область, как решение проблем, характерными чертами которой являются хорошо формализуемые модели задач с усложненными методами поиска их решения.

Язык Planner был разработан в Массачусетском технологическом институте в 1971 году. Сначала это была надстройка над Лиспом, а в дальнейшем язык Planner был превращен в самостоятельный язык. В

СССР он был реализован в таких проектах, как Плэнер-БЭСМ [104] и Плэнер-Эльбрус [45]. Основными новшествами языка были: поиск по образцу, вызов процедур по образцу, автоматический поиск с возвратами, дедуктивный механизм и др., которые в совокупности делали Planner мощным языком программирования для реализации различных систем символьной обработки, а также для описания задач, связанных с заданием исходных ситуаций, целей и допустимых операций, решение которых должна искать система искусственного интеллекта.

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

Другой язык данной группы - Conniver, был разработан в 1972 году, причем его авторы критически отнеслись к некоторым идеям языка Planner, что привело к реализации в языке новых концепций. Примечательной особенностью языка стал новый тип данных - фрейм, который представлял собою некоторыйучасток памяти, доступ к которому осуществлялся по указателям. Для работы с фреймами использовались такие функции, как:

(ERAME) - вьlдача указателя на текущийфрейм; (ACCESSFR) - выдача указателя доступа из фрейма FR; (CONTROL FR) - выдача указателя возврата из фреймаFR;

(SETACCESS FR FRl) - сделать указателем доступа в фрейме FR ссылку на фрейм FR1;

(SETCONTROL FR FRl) -сделать указателем возврата в фрейме FR ссылку на фрейм FRL

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

154

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

Язык QA-4 был создан в Стэнфордском исследовательском институте

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

вто время метод резолюций. Помимо этого, Язык QA-4 вобрал в себя практически все идеи языков Planner и Conniver, а затем, развил их

дальше.

После формирования концепции представления знаний на основе семантических сетей и фреймов, появилась естественная потребность в специальных языках, ориентированных на представление знаний (ЯПЗ). Наиболее заметными среди них стали такие языки, как KRL, FRL и KL-ONE [45]. Наиболее характерными чертами этих языков были: двухуровневое представление данных; представление связей между понятиями и закономерностями предметной области; семантический подход к сопоставлению образцов и поиску по нему. Кроме того, дня всех ЯПЗ по сравнению с традиционными языками программирования характерна существенно большая "активность" данных, которая приводит к размытию граней между декларативной и процедурной частями. Кроме того, заметим, что учитывая реальные большие объемы обрабатываемых данных, необходимым условием при реализации ЯПЗ является использование концепции баз данных и методов обработки данных, связанных с ней.

Среди современных ЯПЗ наибольший интерес представляют [45]: RLL (Representation Language Language), ART (Automated Reasoning Tool) и OPS5 (Official Production System, version 5). Последний претендовал на роль стандарта в области представления знанийдля систем искусственного интеллекта.

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

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

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

155

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

Таким образом, анализ представления знаний и методов вывода решенийпозволяет сформулировать [33] основные требования к ЯПЗ:

наличие простых и мощных средств представления сложно структурированных и взаимосвязанных объектов;

наличие гибких средств управления выводом; переносимость описаний объектов на различные виды памяти ЭВМ;

возможность доопределения и переопределения системных механизмов на уровне входного языка;

возможность эффективной реализации.

1.9.2.ОБЩИЕ СВЕДЕНИЯ О ПРОГРАММИРОВАНИИ

НА ЯЗЫКЕ ПРОЛОГ

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

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

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

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

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

Программирование на языке Пролог состоит из следующих этапов:

1) объявление некоторых фактов об объектах и отношениях между ними;

2) определение некоторых правил об объектах и отношениях между ними;

156

Пролог-систему можно рассматривать как место, где хранятся факты и правила, которые используются для поиска ответов на вопросы. Пролог является интерактивным (диалоговым) языком.

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

Факты Пусть нам необходимо сообщить Пролог-системе следующий факт:

’’Петренко нравится физика”. Этот факт содержит в себе два объекта, обозначенных фамилией “Петренко” и предметом “физика”, а также отношением, обозначенным словом “нравится”.

В языке Пролог используется стандартная форма описания фактов: нравится (петренко, физика).

Петренко

физика

Q — -— -— * 0

нравится

Рис.1.38 Фрагмент семантической сети, отображающий фразу:, “Петренко нравится предметфизика”

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

1) имена всех объектов и отношений должны начинаться с маленькой буквы;

2) вначале записывается имя отношения, а затем - в круглых скобках через запятую записываются имена объектов, которые связаны данным отношением;

3)каждый факт должен заканчиваться точкой;

4)важно учитывать порядок объектов в скобках. Приведем примеры фактов.

1)студент(федотов). “Федотов является студентом”.

2)военнослужащий(офицер). “Офицер является военнослужащим”.

3)ценная(информация). “Информация является ценной”.

4)начальник (петров, федотов). “Петров является начальником

Федотова”.

5) отдает(иванов, приказ, петров). “Иванов отдает приказ Петрову”. Заметим, что в приведенных примерах (1) - (5) используются

предикаты с разным числом аргументов.

Вопросы

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

157

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

Например, вопрос: ?— имеет (петренко, увлечение), можно описать, как “Какие увлечения имеет Петренко?”

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

Если система находит факт, который можно сопоставить с вопросом, то она отвечает “да”. Если в базе знанийтакого факта не существует, то мы получаем ответ- “нет”.

Важно помнить, что ответ “нет” не является эквивалентным ответу “ложь”.

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

военнослужащий(курсант). военнослужащий(рядовой). военнослужащий(иванов).

сопровождает (рлсі, цель5). сопровождает (рлс2, цель2). сопровождает (рлсі, цель2). Сформулируем вопрос:

?- военнослужащий(петренко). нет (имеем ответ- “нет”).

?- военный(иванов).

нет (имеем ответ- “неяг”).

?- сопровождает(рлс1,цель5). да (имеем ответ- “да”).

?- сопровождает(рлс1, цельЗ). нет (имеем ответ- “нет”).

?- уничтожить(истребитель1, цель1). нет (ответ- “нет”).

Переменные

Разберем ситуацию, когда необходимо сформулировать следующий к Пролог-системе: “Какие цели сейчас сопровождаются радарами в воздушном пространстве?” (иными словами, выдать все цели, которые сопровождают какая-либо PJ1C). Такие вопросы можно формулировать

путем использования переменных для обозначения объекта, например:

158

?- сопровождает (рлсі Д). (“Какие воздушные цели сопровождает первый радар?”), или: ? - сопровождает (У, X). (“Кто, кого сопровождает?”).

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

?— сопровождает (рлс1,С). (“какие цели сопровождает первый радар?”).

В этом вопросе “рлсі” - это конкретный объект (его обозначение начинается с маленькой буквы), а “С” - это переменная (обозначение начинается с большой буквы).

На этот вопрос может быть ответ:

С= цель5;

С= цельб; (первый радар сопровождает пятую и шестую цели).

Конъюнкции

Бывают случаи, когда необходимо получить ответ на вопрос о более сложном отношении предметной области, например:

“Сопровождается ли вторая цель двумя радарами: PJICl и PJIC2 ?”

.Одним из способов сделать это - сначала определить “Сопровождает ли первый радар вторую цель?” и, если будет получен положительный ответ, то сформулировать следующий вопрос: “Сопровождает ли второй радар ту же самую цель?”

Однако, то же самое можно сделать намного быстрее, если в вопросе применить операцию конъюнкции, или логическую связку “И”. Для этого необходимо записать две части вопроса через запятую;

?- сопровождает (рлсі, цель2), сопровождает (рлс2, цель2).

Вообще, о механизме вывода фактов в этом вопросе мы поговорим позднее.

Правила

В Прологе правило состоит из заголовка и тела, разделенных обозначением которое можно интерпретировать, как условие “если”.

Например:

нравится (василий, А) :- автомобиль (А).

Это правило можно интерпретировать» как фразу: ’’Василию нравится объект А, если объект А является автомобилем”, или более осмысленно: “Василию нравятся все марки автомобилей”.

Напомним, что в этом правиле “василий” - это объект, который задается с помощью обозначения с маленькой буквы, а “А” - это переменная, которая задается с большой буквы.

Приведем пример правила для факта: “Василию нравятся автомобили, которые производятся в Германии”.