2.2 Представление знаний о предметной области в виде вычислительных метасетей

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

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

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

Объекты системы с постоянной структурой делятся на три типа:

- статусные объекты - объекты состояния;

- реляционные объекты;

- функциональные объекты.

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

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

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

При описании структуры системы в виде графа f-, s- и r-объекты представляются вершинами различных типов. Это графовое представление системы называется fsr-сетью. Таким образом, для моделирования предметики необходимо формализовать целевую систему в виде fsr-сети в заданном базисе f-, s- и r-объектов.

s-объект f-объект

┌───────┐ ╔═══════╗ ┌───────┐

│ ├────────►║ ║──►│ │

└───┬───┘ ╚═══════╝ └───────┘

│

│ ╔═══════╗ ┌───────┐

└────║░░░░░░░║────+ │

╚═══════╝ └───────┘

r-объект

Рисунок 2.4 - Fsr-сеть

Fsr-сеть обладает следующими особенностями:

- вершины, обозначающие f- и r-объекты, непосредственно связаны только с s-объектами; связи между f- и r-объектами отсутствуют;

- связи f-объекта с s-объектами - ориентированные, r-объекта с s-объектами - неориентированные;

- семантика связей f-объекта заключается в преобразовании входных s-объектов в выходные; смысл связей r-объекта - наличие отношений между s-объектами.

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

Дело в том, что машины фон-Неймана оперируют базисным набором f- и s-объектов (системой команд и памятью). Модель системы в этом случае - это один структурированный f-объект, программа, решающая задачу пользователя. Главный модуль (f-объект) программы содержит в своей внутренней структуре подобъекты f- и s-типов, которые также могут структурироваться до уровня базисных объектов (машинных команд и ячеек памяти). Таким образом, перед разработчиком системы моделирования возникает проблема представления r-объектов на ЭВМ.

R-объекты по своей природе не являются конструктивными. Они моделируется на ЭВМ несколькими f- и s-объектами. В системе семантического моделирования происходит преобразование fsr-сети в fs-сеть, которая затем преобразуется в алгоритм решения задачи на системной модели:

fsr-сеть -> fs-сеть -> алгоритм

Другая проблема реализации модели на ЭВМ заключается в том, что процедурная модель системы (f-объект, программа) решает только одну задачу пользователя из множества возможных задач на этой модели. В данном случае под задачей мы понимаем нахождение по известным значениям объектов состояния системы {s_i}, i=1,...,n значений других - искомых статусных объектов {s_j}, j=n+1,...,N,

где N - общее число s-объектов в модели системы;

n - число s-объектов с известными значениями, исходных s-объектов;

m=N-n - число s-объектов с неизвестными значениями, искомых s-объектов.

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

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

Знания классифицируются в системе следующим образом:

знания ◄─ вид знаний

(вычислительные метасети) ◄─ (представление)

│

┌──────────────┴─────────────────┐

▼ ▼

метазнания знания о предметной области

(правила продукций) (классы объектов и отношений)

│

┌───────┴────────┐

▼ ▼

процедурные непроцедурные

(алгоритмы) (вычислительные сети)

Рисунок 2.5 - Знания в системе семантического моделирования

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

┌─┐ ╔═╗

графом, состоящим из сущностных └─┘ и реляционных ╚═╝ объектов. В качестве базового представления формализованных знаний в системе семантического моделирования принят двудольный ориентированный граф, что значительно упрощает язык описания знаний, язык описания задач и сам процесс преобразования знаний.

┌──────────────────┐

▼ │

┌─┐ │

┌─┐ ┌────►│ ├┐ ╔═╗ ┌─┐ │

│ ├┐ │ └─┘└──►║ ╟───►│ │ │

└─┘└-►╔╧╗ ┌─┐ ╚═╝ └─┘ ╔╧╗

║ ╟───►│ ├───────────────►║ ║

┌─┐┌─►╚╤╝ └─┴───►╔═╗ ┌─┐ ╚═╝

│ ├┘ │ ┌─┐ ║ ╟───►│ │

└─┘ └────►│ ├───►╚╤╝ └─┘

└─┘ │

▼

┌─┐

│ │

└─┘

Рисунок 2.6 - Семантическая сеть

Fsr-сеть представляет особый вид семантической сети, выражающей структуру системы и отношения между ее компонентами.

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

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

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

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

Формально fsr-сеть задается набором троек:

fsr = <rs,fs>,

rs = {(r,{s_in},{s_out})},

где r - идентификатор r-объекта;

{s_in} - множество входных s-объектов r-объекта;

{s_out} - множество выходных s-объектов r-объекта;

fs = {(f,{s_in},{s_out})},

где f - идентификатор f-объекта;

{s_in} - множество входных s-объектов f-объекта;

{s_out} - множество выходных s-объектов f-объекта.

На семантической сети предметной области можно поставить задачу:

task = <{s_in}, {s_out}>,

где {s_in} - множество исходных s-объектов семантической сети;

{s_out} - множество искомых s-объектов семантической сети.

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

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

fs = {(f,{s_in},{s_out})},

где f - идентификатор f-объекта;

{s_in} - множество входных s-объектов f-объекта;

{s_out} - множество выходных s-объектов f-объекта.

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

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

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

╔═╗

операторов ╚═╝-f-объектов (функциональных объектов) и операндов

┌─┐

└─┘ - s-объектов (объектов состояния). Оператор может быть связан с другими операторами посредством информационных связей ─► (через операнды) и с помощью управляющих связей ═► (изображающих передачу управления от одного оператора другому в процессе выполнения алгоритма). Среди описателей вычислительного процесса чаще всего используются информационный граф (ИГ) и граф преобразований (ГП).

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

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

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

информационную или управляющую структуру. Наиболее полным описателем вычислительного процесса является информационный граф преобразований (ИГП), учитывающий все виды связей в функциональном (f) и объектном (s) базисах. ИГП представляет собой двудольный ориентированный граф, сеть, с вершинами двух типов: f- и s-объекты, и двумя типами дуг, показывающими связи по данным и по управлению.

┌─┬──────────────►╔═╗

┌─►│ ├───────┐╔═════►║ ║

┌─┐ │ └─┴─┐ │║ ╚═╝

│ ├┐ │ ▼ │║

└─┘└─►╔╧╗ ╔═╗ ▼╩

║ ╠═══►║ ╠═══►║ ║

┌─┐┌─►╚═╝ ╚═╝─┐ ╦

│ ├┘ ▲ ▲ │ ║

└─┘ │ │ │ ║

┌┴┐ │ ▼ ║ ╔═╗

│ ├─────┘ ┌─┐ ╚═════►║ ║

└─┘ │ ├────────►╚═╝

└─┘

Рисунок 2.7 - Информационный граф преобразований (ИГП)

Формально ИГП задается следующим образом:

alg = <{f}, begin, end, {s}, ctrl, info>,

ctrl={(f_o,f_y,f_n)},

info={(f,{s_in},{s_out})},

где {f} - функциональный базис ИГП, в котором выделены

begin - оператор начала программы;

end - оператор окончания программы;

{s} - статусный базис ИГП;

ctrl - описатель управляющей структуры ИГП;

info - описатель информационной структуры ИГП.

Управляющая структура ИГП описывается набором троек

(f_o,f_y,f_n),

где f_o - f-объект, которому на данном шаге вычислительного процесса передано управление; f_o выполняется и вырабатывает логический код завершения, который анализируется вычислителем;

f_y - f-объект, которому на следующем шаге вычислительного процесса будет передано управление в случае успешного завершения f-объекта f_o (код завершения - "истина");

f_n - f-объект, которому на следующем шаге вычислительного процесса будет передано управление в случае неуспешного завершения f-объекта f_o (код завершения - "ложь").

Информационная структура ИГП описывается набором троек

(f,{s_in},{s_out}),

где f - идентификатор f-объекта;

{s_in} - множество входных s-объектов f-объекта;

{s_out} - множество выходных s-объектов f-объекта.

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

┌ ┐ ┌ ┐

│ ┌─┐ │ │ ┌─┐ │

│ ┌─┐ ┌────►│ │ │ │ ┌─┐ ╔═╗───►│ │ │

│ │ ├┐ │ └─┘ │ │ │ ├──►║ ╟┐ └─┘ │

│ └─┘└─►╔╧╗ ┌─┐ │ │ └─┘ ╚═╝│ ┌─┐ │

│ ║ ╟───►│ │ │ ──► │ └──►│ │ │

│ ┌─┐┌─►╚╤╝ └─┘ │ │ ┌─┐ └─┘ │

│ │ ├┘ │ ┌─┐ │ │ │ ├┐ ╔═╗ ┌─┐ │

│ └─┘ └────►│ │ │ │ └─┘└─►║ ╟───►│ │ │

│ └─┘ │ │ ╚═╝ └─┘ │

└ ┘ └ ┘

Рисунок 2.8 - Продукционная сеть (p-сеть)

Формально p-сеть задается следующим образом:

p = {(fsr_in, fsr_out)},

где fsr_in - входная fsr-сеть правила;

fsr_out - выходная fsr-сеть правила.

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

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

m = <fsr, p, alg>.

Таким образом, формально процесс решения задач в системе семантического моделирования можно описать так:

<m,task> = <fsr, p, alg, task> -> <fs, alg, task> -> alg