Вопрос №3 Принципы проектирования информационного обеспечения программного комплекса

Вид материала

Документы

Содержание Вопрос №23. Системы ИИ. Фреймы, семантические сети и процедуры. База знаний Декларативные знания Семантические сети Фреймовые модели Имя фрейма Список работников

Подобный материал:

• Е. В. Чепин московский инженерно-физический институт (государственный университет), 30.11kb.
• Рабочая программа учебной дисциплины (модуля) case-средства проектирования программного, 143.56kb.
• Технология программирования, 643.21kb.
• Базы данных, 3110.93kb.
• А. А. Дюмин московский инженерно-физический институт (государственный университет), 30.84kb.
• Учебно-методический комплекс дисциплины разработка и стандартизация программных средств, 362.73kb.
• Методика выбора программного обеспечения турфирмой Антон Россихин (само-софт), 34.31kb.
• С. Д. Романин московский инженерно-физический институт (государственный университет), 24.74kb.
• Примерная программа наименование дисциплины Проектирование и архитектура программных, 182.2kb.
• Рабочая программа учебной дисциплины "системы автоматизированного проектирования электроустановок, 119.83kb.

Вопрос №23. Системы ИИ. Фреймы, семантические сети и процедуры.

Искусственный интеллект, основные понятия

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

Термин «искусственный интеллект» ( artificial intelligence ) предложен в 1956 году на семинаре с аналогичным названием, который состоялся в США и был посвящен решению логических задач.

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

ПРИМЕЧАНИЕ

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

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

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

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

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

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

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

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

Эвристика — правило, теоретически не обоснованное, но позволяющее сократить количество переборов в пространстве поиска;

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

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

Знания и модели их представления

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

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

ПРИМЕР

Рассмотрим понятие персональный компьютер. Его интенсионал: персональный компьютер — это ЭВМ, которую можно поставить на стол и купить менее чем за $3000. Экстенсионал этого понятия: персональный компьютер — это IBM PC, Macintosh и т. п.

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

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

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

ПРИМЕЧАНИЕ

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

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

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

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

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

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

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

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

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

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

При работе со знаниями используются два основных подхода:

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

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

Типичные модели представления знаний: логические модели; модели, основанные на использовании правил (продукционные модели); семантические сети; фреймовые модели.

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

Способ представления знаний с помощью сетевых моделей наиболее близок к тому, как они представлены в текстах на естественном языке. В его основе лежит идея о том, что вся необходимая информация может быть описана как совокупность троек ( arb ), где а и b — объекты или понятия, а r — бинарное отношение между ними. Формально сетевые модели представления знаний могут быть заданы в виде H = < I , C 1 ,…, Cn , Г>, где I — множество информационных единиц,

С 1 ,..., Сп — множество типов связей между элементами

I , отображение Г задает между информационными единицами, входящими в I , связи из заданного набора типов связей {С i }.

В зависимости от типов связей {С i } различают:

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

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

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

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

ПРИМЕЧАНИЕ

Термин «семантическая» означает «смысловая», а сама семантика — это наука, устанавливающая отношения между символами и объектами, которые они обозначают, то есть наука, определяющая смысл знаков.

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

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

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

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

Фреймовые модели

Термин фрейм ( frame — каркас, рамка) предложен М. Минским в 70-е годы для обозначения структуры знаний для восприятия пространственных сцен. Эта модель, как и семантическая сель, имеет глубокое психологическое обоснование. Под фреймом понимается абстрактный образ или ситуация. В психологии и фило софии известно понятие абстрактного образа. Например, слово «комната» вызывает образ комнаты — «жилое помещение с четырьмя стенами, полом, потолком, окнами и дверью». Из этого описания ничего нельзя убрать, например, убрав окна, мы получим уже чулан, а не комнату. Но в нем есть «слоты», или «щели», — незаполненные значения некоторых атрибутов — количество окон, цвет стен, высота потолка, покрытие пола и др. Такой образ и называется фреймом (фреймом минимального описания). Фреймом называется также и формализованная модель этого образа.

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

f = [( r 1 , v 1 ,), … ,( r n , v n )]

, где f — имя фрейма; vi — значение слота,

или

(ИМЯ ФРЕЙМА:

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

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

…

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

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

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

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

Например, структура таблицы, содержащей список работников, записанная в виде протофрейма , имеет вид

(СПИСОК РАБОТНИКОВ:

Фамилия (значение слота 1);

Год рождения (значение слота 2);


Специальность (значение слота 3);

Стаж (значение слота 4)

).

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

Важнейшим свойством фреймов является заимствованное из теории семантических сетей наследование свойств. И во фреймах, и в семантических сетях наследование происходит по АКО-связям (от A Kind Of = это). Слот АКО указывает на фрейм более высокого уровня иерархии, откуда неявно наследуются, то есть переносятся значения аналогичных слотов, причем наследование свойств может быть частичным.

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

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

фреймы-роли (менеджер, кассир, клиент);

фреймы-сценарии (банкротство, собрание акционеров, празднование именин);

фреймы-ситуации (тревога, авария, рабочий режим устройства и т. д.).

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

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

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

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

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

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

Обобщая анализ моделей представления знаний, можно сделать два основных вывода:

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

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