Продукционная модель представления знаний. Логические модели. Сетевые модели или семантические сети. Фреймовые модели

Особенности знаний:

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

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

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

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

Существуют два типа методов представления знаний (ПЗ):

1. Формальные модели ПЗ;

2. Неформальные (семантические, реляционные) модели ПЗ.

Каждому из методов ПЗ соответствует свой способ описания знаний.

1. Логические модели. В основе моделей такого типа лежит формальная система, задаваемая четверкой вида: M = < T, P, A, B> . Множество T есть множество базовых элементов различной природы, например слов из некоторого ограниченного словаря, деталей детского конструктора, входящих в состав некоторого набора и т.п. Важно, что для множества T существует некоторый способ определения принадлежности или непринадлежности произвольного элемента к этому множеству. Процедура такой проверки может быть любой, но за конечное число шагов она должна давать положительный или отрицательный ответ на вопрос, является ли x элементом множества T. Обозначим эту процедуру П(T).

2. Сетевые модели. В основе моделей этого типа лежит конструкция, названная ранее семантической сетью. Сетевые модели формально можно задать в виде H = < I, C₁, C₂, ..., C_n, Г> . Здесь I есть множество информационных единиц; C₁, C₂, ..., C_n- множество типов связей между информационными единицами. Отображение Г задает между информационными единицами, входящими в I, связи из заданного набора типов связей.

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

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

(Имя фрейма:

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

Имя слота 2(значение слота 2)

......................

Имя слота К (значение слота К)).

Существует 2 группы языков: модульные и сетевые.

Модульные языки оперируют отдельными несвязными элементами знаний (правила

или аксиомы).

Сетевые языки дают возможность связать эти фрагменты через отношения в семантические сети (или сети фреймов).

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

Лекция 12-13. Моделирование процессов обработки информации для принятия решений

План

1. Моделирование процессов обработки информации для принятия решений

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

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

Дадим классификацию методов, используемых при решении SS- и PR-проблем.

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

Пространство состояний можно представить как граф, вершины которого помечены состояниями, а дуги-операторами. Если некоторая дуга направлена от вершины n_i, к вершине n,, то п, называется дочерней, а n_j; -родительской вершинами

Последовательность вершин n_i1, n_i2, ..., n_ik, в которой каждая n_i-дочерняя вершина для вершины n_ij-1, /=2,..., k, называется путем длиной k от вершины n_i1, к вершине n_ik.

Таким образом, проблема поиска решения задачи < А, В> при планировании по состояниям представляется как проблема поиска на графе пути из A в B. Обычно графы не задаются, а генерируются по мере надобности.

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

Алгоритм кратчайших путей Мура. Исходная вершина x₀ помечается числом 0. Пусть в ходе работы алгоритма на текущем шаге получено множество дочерних вершин Г(x_i) вершины x_i. Тогда из него вычеркиваются все ранее полученные вершины, оставшиеся помечаются меткой, увеличенной на единицу по сравнению с меткой вершины x_i, и от них проводятся указатели к x_i. Далее, на множестве помеченных вершин, еще не фигурирующих в качестве адресов указателей, выбирается вершина с наименьшей меткой и для нее строятся дочерние вершины. Разметка вершин повторяется до тех пор, пока не будет получена целевая вершина.

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

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

Алгоритм Харта, Нильсона и Рафаэля. В алгоритме объединены оба критерия: стоимость пути до вершины g(x) и стоимость пути от вершины h(x) - в аддитивной оценочной функции f (x) = g (x) + h (x). При условии h(x)< h_p(x), где h_p(x)- действительное расстояние до цели, алгоритм гарантирует нахождение оптимального пути.

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

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

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

Метод иерархической системы продукций решателя ABSTRIPS. В этом методе разбиение пространства поиска на уровни иерархии осуществляется с помощью детализации продукций, используемых в методе STRIPS. Для этого каждой литере ППФ, входящей в множество Р условий применения продукции, присваивается вес j, j=0, k, и на i-м уровне планирования, осуществляемом методом системы STRIPS, учитываются лишь литеры веса j. Таким образом, на k-ом уровне продукции описываются наименее детально, на нулевом-наиболее детально как в методе системы STRIPS. Подобное разбиение позволяет для планирования на j-м уровне использовать решение (j+1)-го уровня как скелет решения j-го уровня, что повышает эффективность поиска в целом.

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

⇐ Предыдущая 1 2 3 4 5 678 Следующая ⇒