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

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

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

В качестве понятий обычно выступают абстрактные или конкретные объекты, а отношения это связи типа: "это" ("АКО — A-Kind-Of, "is" или "элемент класса"), "имеет частью" ("has part"), "принадлежит", "любит".

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

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

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

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

r По типам отношений:

o бинарные (в которых отношения связывают два объекта);

o N-арные (в которых есть специальные отношения, связывающие более двух понятий).

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

r элемент класса (роза это цветок);

r атрибутивные связи /иметь свойство (память имеет свойство — объем);

r значение свойства (цвет имеет значение — желтый);

r пример элемента класса (роза, например — чайная);

r связи типа "часть-целое" (велосипед включает руль);

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

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

r пространственные (далеко от, близко от, за, под, над...)',

r временные (раньше, позже, в течение...);

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

Минимальный состав отношений в семантической сети таков:

r элемент класса или АКО;

r атрибутивные связи /иметь свойство;

r значение свойства.

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

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

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

Рис. 2.Семантическая сеть

Для реализации семантических сетей существуют специальные сетевые языки, например, NET, язык реализации систем SIMER + MIR и др. Широко известны экспертные системы, использующие семантические сети в качестве языка представления знаний — PROSPECTOR, CASNET, TORUS.

Фреймы

Термин фрейм (от англ, frame — "каркас" или "рамка") был предложен Мар-вином Минским, одним из пионеров ИИ, в 70-е годы для обозначения структуры знаний для восприятия пространственных сцен. Эта модель, как и семантическая сеть, имеет глубокое психологическое обоснование.

Фрейм — это абстрактный образ для представления стереотипа объекта, понятия или ситуации.

Интуитивно понятно, что под абстрактным образом понимается некоторая обобщенная и упрощенная модель или структура. Например, произнесение вслух слова "комната" порождает у слушающих образ комнаты: "жилое помещение с четырьмя стенами, полом, потолком, окнами и дверью, площадью 6—20 м2". Из этого описания ничего нельзя убрать (например, убрав окна, мы получим уже чулан, а не комнату), но в нем есть "дырки" или "слоты"— это незаполненные значения некоторых атрибутов— например, количество окон, цвет стен, высота потолка, покрытие пола и др.

В теории фреймов такой образ комнаты называется фреймом комнаты. Фреймом также называется и формализованная модель для отображения образа.

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

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

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

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

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

Традиционно структура фрейма может быть представлена как список свойств:

(ИМЯ ФРЕЙМА:

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

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

…

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

Ту же запись можно представить в виде таблицы (см. табл. 6), дополнив ее двумя столбцами.

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

Таблица 6.Структура фрейма

Существует несколько способов получения слотом значений во фрейме-экземпляре:

r по умолчанию от фрейма-образца (Default-значение);

r через наследование свойств от фрейма, указанного в слоте АКО;

r по формуле, указанной в слоте;

r через присоединенную процедуру;

r явно из диалога с пользователем;

r из базы данных.

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

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

Рис. 3.Сеть фреймов

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

Специальные языки представления знаний в сетях фреймов FRL (Frame Representation Language), KRL (Knowledge Representation Language), фреймовая "оболочка" Kappa и другие программные средства позволяют эффективно строить промышленные ЭС. Широко известны такие фрейм-ориентированные экспертные системы, как ANALYST, МОДИС, TRISTAN, ALTERID.

1. Понятие искусственного интеллекта. Языки программирования для ИИ и языки представления знаний. Инструментальные пакеты для ИИ.

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

Он ставил вопрос:

"Могут ли машины мыслить?"

Ответ:

"Да, я думаю, что это будет возможно через пятьдесят лет".

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

Искусственный интеллект (ИИ) эти два слова противоположны по значению:

Интеллект — это чаще связывают с поведением человека;

Искусственный — относится к объектам, которые не являются естественными, и в этом смысле получаем парадокс.

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

Слово "интеллект"— лат. "Entelligentia", образовано от глагола "Entelligere"— означает способность понимать, определять смысл.

В учебниках "Психология" и "Логика" относятся к понятию интеллект как "знать", "понимать", "запоминать". Т.е. способность познавать понятия, которые не зависят от опыта. Это предполагает наличие образа действий, которые не зависят от знаний.

Цель дисциплины ИИ:

существует две точки зрения:

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

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

С точки зрения информатики можно выделить три направления:

1. Разработка оригинальных методов, задач. Которые дают результаты, подобные человеческим (может даже лучше).

П р и м е р: программа игры в шахматы.

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

3. Разработка средств ИИ, позволяющих по описанию задачи на профессиональном - ЕЯ - построить нужную программу, на основании имеющихся программных модулей.

Специалисты по ИИ ставят такие научные проблемы как:

- доказательство математических теорем;

- диагностика заболеваний или неисправностей в оборудовании;

- финансовый анализ субъектов хозяйствования;

- синтез программ на основе спецификаций;

- понимания текста на ЕЯ;

- анализ изображения и идентификация его содержимого;

- управление работами;

- и пр.

Перечислим программы решения интеллектуальных задач:

Игровые программы:

- человеческие игры;

- переборные игры;

- топологические игры;

- стохастические игры;

- компьютерные игры:

- игры с жёсткой схемой;

- игры со сценарием.

Естественно-языковые программы:

- машинный перевод;

- автоматическое реферирование;

- генерация текстов:

- прозаические тексты;

- поэтические тексты.

Музыкальные программы:

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

- имитация исполнительного стиля.

Узнающие программы.

Программы создания произведений графики и живописи

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

Для настоящего этапа характерна концентрация усилий в следующих направлениях:

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

2.Расширение базисных языков ИИ до систем представления знаний за счет специализированных библиотек и пакетов.

3.Создание языков представления знаний (ЯПЗ), специально ориентированных на поддержку определенных формализмов, и реализация соответствующих трансляторов с этих языков.

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

К концу 80-х годов ЛИСП был реализован на всех классах ЭВМ, начиная с персональных компьютеров и кончая высокопроизводительными вычислительными системами. Новый толчок развитию ЛИСПа дало создание ЛИСП-машин, которые и в настоящее время выпускаются рядом фирм США, Японии и Западной Европы.

Уже в середине 60-х годов, то есть на этапе становления ЛИСПа, разрабатывались языки, предлагающие другие концептуальные основы. Наиболее важными из них в области обработки символьной информации являются СНОБОЛ, разработанный в лабораториях Белла, и язык РЕФАЛ, созданный в ИПМ АН СССР.

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

В основу языка РЕФАЛ положено понятие рекурсивной функции, определенной на множестве произвольных символьных выражений. Базовой структурой данных этого языка являются списки, но не односвязные, как в ЛИСПе, а двунаправленные.

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

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

В 70-х годах в ИИ сформировались концепции представления знаний на основе семантических сетей и фреймов. Естественно, что появились и специальные языки программирования, ориентированные на поддержку этих концепций. Но из десятков, а может и сотен языков представления знаний (ЯПЗ) первого поколения лишь несколько сыграли заметную роль в программной поддержке систем представления знаний. Среди таких ЯПЗ явно выделяются KRL, FRL, KL-ONE и некоторые другие. Характерными чертами этих ЯПЗ были: двухуровневое представление данных (абстрактная модель предметной области в виде иерархии множеств понятий и конкретная модель ситуации как совокупность взаимосвязанных экземпляров этих понятий); представление связей между понятиями и закономерностей предметной области в виде присоединенных процедур; семантический подход к сопоставлению образцов и поиску по образцу.

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

Анализ формализмов представления знаний и методов вывода решений позволяет сформулировать следующие требования к ЯПЗ:

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

r возможность отображения описаний объектов на разные виды памяти ЭВМ;

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

r «прозрачность» системных механизмов для программиста, предполагающая возможность их доопределения и переопределения на уровне входного языка;

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

Экспертные системы появились в рамках исследований по искусственному интеллекту (ИИ) (artificial intelligence) в тот период, когда эта наука переживала серьезный кризис, и требовался существенный прорыв в развитии практических приложений. Этот прорыв произошел, когда на смену поискам универсального алгоритма мышления и решения задач исследователям пришла идея моделировать конкретные знания специалистов-экспертов. Так в США появились первые коммерческие системы, основанные на знаниях, или экспертные системы (ЭС). Эти системы по праву стали первыми интеллектуальными системами, и до сих пор единственным критерием интеллектуальности является наличие механизмов работы со знаниями.

Имеется большое число программных средств, реализующих продукционный подход (например, языки высокого уровня CLIPS и OPS 5; "оболочки" или "пустые" ЭС — EXSYS Professional и Карра, инструментальные системы КЕЕ, ARTS, PIES), а также промышленных ЭС на его основе (например, ЭС, созданных средствами.

Для реализации семантических сетей существуют специальные сетевые языки, например, NET, язык реализации систем SIMER + MIR и др. Широко известны экспертные системы, использующие семантические сети в качестве языка представления знаний — PROSPECTOR, CASNET, TORUS.

Специальные языки представления знаний в сетях фреймов FRL (Frame Representation Language), KRL (Knowledge Representation Language), фреймовая "оболочка" Kappa и другие программные средства позволяют эффективно строить промышленные ЭС. Широко известны такие фрейм-ориентированные экспертные системы, как ANALYST, МОДИС, TRISTAN, ALTERID.

1. Вывод на знаниях. Машина вывода. Цикл работы интерпретатора. Управление выводом. Стратегии поиска в системах, основанных на знаниях.

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

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

Обычно она выполняет две функции:

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

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

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

Действие компонента вывода основано на применении правила, называемого modus ponens: "Если известно, что истинно утверждение А, и существует правило вида "ЕСЛИ А, ТО В", тогда утверждение В также истинно".

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

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

Управляющий компонент определяет порядок применения правил и выполняет четыре функции:

r Сопоставление — образец правила сопоставляется с имеющимися фактами.

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

r Срабатывание — если образец правила при сопоставлении совпал с какими-либо фактами из рабочей памяти, то правило срабатывает.

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

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

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

Рис. 4.Цикл работы интерпретатора

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

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

Рис. 5.Схема функционирования интерпретатора