Точно Не проект 2 / Не books / Источник_1

Рисунок 2.17 – Альфа-бета поиск

Процесс поиска начинается в позиции S и идет в направлении вершины С, для которой выбирается максимальная из оценок вершинприемников позиции С, т.е. H(C)=5. Затем происходит возврат к вершине А и оценивание вершины D. Для этого рассматривается первая вершинаприемник позиции D с оценкой 6. В этот момент обнаруживается, что игроку в вершине D гарантирована оценка не меньшая, чем 6. Этого достаточно чтобы понять, что для противника позиция D хуже, чем С. Поэтому можно пренебречь вторым и третьим приемником позиции D и связать с вершиной D приближенную оценку 6. Точно также при обследовании правого поддерева вершины S игроку в позиции Е гарантируется оценка не меньшая, чем 4. Следовательно, противнику в позиции В гарантируется оценка не выше 4. Отсюда следует, что из позиции S лучше сделать ход S- A. Поэтому правое поддерево вершины В можно не анализировать. Таким образом, сложность поиска уменьшилась за счет отсечения части дерева поиска.

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

ГЛАВА 3

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

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

Понятие “знание” трактуется отдельными авторами по-разному и во многом носит дискуссионный характер. В главе рассматривается наиболее распространенное толкование этого понятия.

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

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

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

3.1. Знания и их представление в СИИ

Что же представляют собой знания? Четкий ответ на этот вопрос дан в энциклопедическом словаре. Знание – это “проверенный практикой результат познания действительности, верное её отражение в мышлении человека”. Отражение существующего мира в мышлении человека связано с процессом абстрагирования, который заключается в выделении наиболее существенных свойств и признаков явлений или объектов, наблюдаемых в окружающей действительности, и представлении их в такой упрощенной форме, которая необходима для логических умозаключений и принятия эффективных решений в самых различных ситуациях. Указанное упрощенное представление действительности называют моделью. Человек, познавая окружающий мир, строит модели явлений, процессов, предметов и т.п.

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

Внастоящее время в искусственном интеллекте нет формального единого определения понятия “знание”. Однако многими исследователями признается, что знания – сложноорганизованные данные, хранимые в памяти СИИ и включающие в себя сведения об объектах и отношениях предметной области, процессах взаимодействия объектов во времени и в пространстве, правилах осуществления логического вывода [2,16,38]. Важным элементом этого определения является указание на то, что знание

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

онных моделей данных. Перечислим эти свойства [21].

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

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

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

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

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

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

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

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

-логические модели;

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

-сетевые модели;

-фреймовые модели.

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

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

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

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

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

Семантические сети являются частным случаем сетевых моделей представления знаний. Формально сетевые модели задаются в виде [21]

H = < I, C1, C2, …, Cn, Q >,

где I – множество информационных элементов, хранящихся в узлах сети; C1, C2, …, Cn – типы связей между информационными элементами; Q – отображение, которое устанавливает соответствие между множеством типов связей и множеством информационных элементов сети.

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

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

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

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

Фреймовые модели представления знаний используют теорию организации памяти, понимания и обучения, предложенную М. Минским. Фрейм (от англ. frame – рамка, каркас, остов) – структура данных, предназначенная для представления стереотипных ситуаций. Фрейм состоит из слотов (slot - гнездо, щелка, паз). Значением слота могут быть числа, выражения, тексты, программы, ссылки на другие фреймы. Совокупности фреймов образуют иерархические структуры, построенные по родовидовым признакам, что позволяет наследовать значения слотов. Такое свойство фреймов обеспечивает экономное размещение базы знаний в памяти. Кроме этого, значения слотов могут вычисляться с помощью различных процедур, т.е. фреймы комбинируют в себе декларативные и процедурные представления знаний. Фреймовые модели можно понимать как сетевые модели представления знаний, когда фрагмент сети представляется фреймом с соответствующими слотами и значениями. С фреймовыми моделями связаны модели представления знаний на основе сценариев и объектов.

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

Рассмотрим подробнее упомянутые выше модели представления знаний.

3.2. Логические модели

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

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

Воснове логических моделей представления знаний лежит понятие формальной системы. Формальная система (ФС) задается четверкой

М={T,P,A,R},

78 Глава 4

суть элементов, образующих ФС.

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

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

ной. Такие совокупности называют правильно построенными формулами

(ППФ).

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

Наконец, множество R – это конечное множество отношений между ППФ, называемых правилами вывода. Правило вывода – это отношение на множестве формул. Если из формул F1, F2, …,Fn непосредственно выводится формула F, то это часто записывается в виде

F1 , F 2 ,..., F n ,

F

где формулы F1, F2, …,Fn называются посылками правила, а F – его след-

ствием (заключением).

Применяя правила вывода к множеству аксиом А, можно получать новые ППФ, к которым можно опять применить правила из множества R. Это позволяет осуществлять вывод новых ППФ. Множество R называют также множеством семантических правил. А множество ППФ, получаемое после применения правил к аксиомам, называется множеством семанти-

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

Выводом формулы В из формул А1,А2,..,Аn называется последовательность ППФ F1, F2, …,Fm такая, что Fm=B, а для любого i (1 i m) формула Fi есть либо аксиома ФС, либо одна из исходных формул А1,А2,..,Аn, либо непосредственное следствие формул F1, F2, …,Fi-1, полученное с помощью правил вывода. Некоторая ППФ F является выводимой в

ФС (является теоремой ФС), если существует вывод, в котором последней формулой является F. Сокращенно вывод F из F1, F2, …,Fn будем записывать в виде F1, F2, …,Fn F. Если имеется эффективная процедура, позволяющая по данной ППФ F устанавливать, существует ли ее вывод в ФС, то данная ФС называется разрешимой, в противном случае – неразрешимой.

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

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

3.2.2. Исчисление высказываний

Высказыванием называется предложение, содержание которого можно оценить как истинное или ложное. В естественных языках высказывания выражаются повествовательными предложениями. Например, “Сегодня ясная погода”, “Пять меньше трех” и т. п. Будем обозначать высказывания прописными латинскими буквами А,В,С,..,X,Y,Z и называть их пропозициональными (лат. propositio – предложение, высказывание). Пропозициональные буквы могут принимать два значения: истина (И) и ложь (Л).

Значения И и Л называют истинностными значениями.

На основе заданных высказываний с помощью логических связок (союзов) образуются сложные высказывания. Указанные связки выражаются в естественном языке словами “и”, “или”, “если…, то…”, “неверно, что А” и называются: конъюнкция, дизъюнкция, импликация и отрицание. Для обозначения данных связок используются специальные символы, соответ-

ственно: , , , A (или A). Каждую логическую связку можно рас-