Грамматики над нечеткими и гранулярными структурами как средство формализации анализа и синтеза интеллектуальных систем

Размещено на http://www.allbest.ru

ГРАММАТИКИ НАД НЕЧЕТКИМИ И ГРАНУЛЯРНЫМИ СТРУКТУРАМИ КАК СРЕДСТВО ФОРМАЛИЗАЦИИ АНАЛИЗА И СИНТЕЗА ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ

Заболеева-Зотова А.В.,

д.т.н., профессор

Волгоградский государственный

технический университет

e-mail: zabzot@vstu.ru

ВВЕДЕНИЕ

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

гранулированный информация грамматика гибридизация интеллектуальный

ГРАММАТИКИ ДЛЯ КОНЦЕПТУАЛЬНОГО ПРОЕКТИРОВАНИЯ ТЕХНИЧЕСКИХ СИСТЕМ

Одной из таких задач является концептуальное (поисковое) проектирование. Как и любой творческий процесс, инженерное творчество предполагает использование интуиции для анализа и синтеза гранулированной и вербализованной информации. Данный симбиоз задач является крайне сложным для моделирования. Наиболее распространенными методами поискового конструирования являются эвристические; логико-комбинаторные, методы синтеза на И/ИЛИ-графах; а также автоматизированные методы поиска физических принципов действия на основе банка физических эффектов. В области создания технологии автоматизации поискового конструирования выделяется Волгоградская научная школа, возглавляемая А.И. Половинкиным и В.А. Камаевым [1,2]. Моделируются следующие этапы синтеза технических систем: выявление потребности, формирование технического задания (ТЗ), синтез потоковой функциональной структуры, синтез функционально-физической структуры, синтез конструктивной функциональной структуры, документирование результатов конструирования. Данные подходы являются достаточно эффективными при создании новых технических решений. В то же время возникает проблема адекватного отображения процесса поиска нового технического решения, и, соответственно, его результата.

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

Пусть S нечеткий семантический гиперграф, интерпретирующий структуру системы:

S = (S_N, R, p), (1)

где S_N = {S_i} множество элементарных подсистем, R множество типов соединения подсистем и p двухместный нечеткий предикат инцидентности.

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

S_i = ( Х^L_i,Y^M_i, O^K_i, _i, f_i), (2)

где Х^L_i множество входов, содержащее вещественные (V), энергетические (E) и информационные (P) воздействия: Х^L_i (VEP); Y^M_i множество выходов: Y^M_i (VEP); O^K_i множество состояний объекта воздействия; _i выходная функция; f_i преобразователь выходной функции. Верхние индексы в Х^L_i и Y^M_i определяют соответственно количество входов и выходов, а в O^K_i количество возможных состояний объекта воздействия. Определение элементарных подсистем в предложенном виде является наиболее общим и, в зависимости от организации каждого из множеств Х^L_i, Y^M_i, O^K_i а также функций _i и f_i, отражает все возможные варианты структурного представления реальных функциональных элементов современных технических систем, в частности, сборочных узлов (гиперэлементов), а также физических и конструктивных элементов. Так, например, при М=0 элементарная подсистема на физическом уровне отражает эффекты типа «поглощения» вещества, энергии или информации, при L=0 эффекты «излучения», при L=М=0 эффекты «преобразования» и т.п.[1,2]

Выходная функция (_i: O_iX_iY_i), задающая подсистему, определяется как композиция трех отображений:

₁: X_i O_i; ₂: O_i O_i; ₃: O_i Y_i. (3)

Если в _i отсутствует ₁ или ₃, то подсистема описывает так называемые «внутренние» эффекты, явления или процессы. Определение элементарных подсистем отражает все возможные варианты структурного представления реальных функциональных элементов современных технических систем (ТС), в частности, сборочных узлов (гиперэлементов), а также физических и конструктивных элементов

Универсальное множество U входных и выходных воздействий имеет иерархическую структуру.

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

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

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

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

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

Для формализации процесса анализа - синтеза структур ТС определим грамматику над описанными гранулярными структурами:

G = (T, N, P, C). (4)

Множество терминальных символов имеет следующий вид:

T = {S₁, S₂, ..., S_N, },

где S₁, S₂, ..., S_N элементарные подсистемы, тип соединения подсистем. Здесь подразумевается использование вычисляемого отношения для каждого типа соединения при применении соответствующего правила грамматики.

Множество нетерминалов N={C, S, S_i}, где C цель грамматики (структура ТС), S подструктура, S_i элементарная подсистема структуры.

Тогда система продукций будет содержать следующие правила:

C S; S S_iS; S SS_i; S S_i; S_i S₁| S₂ | ... | S_N. (5)

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

Адекватность данной модели (эффективность процесса проектирования) определяется объемом эмпирической информации экспертными знаниями в виде описания элементарных подсистем каждого уровня - гиперэлементов, физических эффектов, их конструктивных реализаций. Такие базы знаний разрабатываются и используются в процессе обучения студентов поисковому конструированию на кафедре систем автоматизированного проектирования и поискового конструирования ВолгГТУ уже более 20 лет.

Построенная семантическая модель алгоритмизирована и частично реализована программно.

ГРАММАТИКИ ДЛЯ КОНЦЕПТУАЛЬНОГО ПРОЕКТИРОВАНИЯ ПРОГРАММНЫХ СИСТЕМ

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

Грамматика для анализа текста ТЗ Автоматизация этапа анализа текста технического задания при проектировании программного обеспечения в последнее время привлекает все большее внимание разработчиков программных продуктов. Такая система позволит значительно повысить эффективность данного процесса. Однако решение этой задачи пока находится в стадии проб и ошибок. Это связано с необычайной сложностью проблемы синтеза и анализа семантики технического текста. Для данной проблемы мы также предлагаем использовать логико-лингвистический подход. В частности, разработана нечеткая атрибутная грамматика над фреймовой структурой формального документа «Техническое задание» [3,4].

Расширенная нечеткая атрибутная грамматика, необходимая для автоматизированного анализа текста технического задания, определена в виде:

AG = N, T, P, S, B, F, A, D(A), (6)

где N - конечное множество нетерминальных символов; T - непересекающееся с N множество терминальных символов; Р - конечное множество правил; S - начальный символ; B - множество лингвистических переменных в_k,i, соответствующих терминальным символам; F - множество функций принадлежности, определяющих степень принадлежности лингвистических переменных в_k,i; A - множество атрибутов, A=A_sinA_sem, где A_sin - синтаксические атрибуты, A_sem - семантические атрибуты; D(A) - конечное множество семантических действий. Лингвистические переменные из множества B={в_k,i}_k,i используемые для анализа текста технического задания, писывается следующей пятеркой:

в_k,i =<в, T(в), U, G, M>, (7)

где в название лингвистической переменной (наименование и область применения, основание для разработки, назначение разработки, технические требования к программному изделию, стадии и этапы разработки и т.д.); T(в) языковые выражения. Для лингвистических переменных верхнего уровня они являются лингвистическими переменными, соответствующими терминалам правой части правила. Для лингвистических переменных нижнего уровня - нечеткими переменными, т.е. выражениями естественного языка; U-универсум; G-правила морфологического и синтаксического описания языковых выражений, которые определяют синтаксические атрибуты A_sin; М - семантическое правило для лингвистических переменных, которое индуцируется морфологическими и синтаксическими правилами, так как смысл терма в Т частично определяется его синтаксическим деревом и семантическими атрибутами A_sem.

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

Лингвистические переменные верхнего уровня являются составными, т.е. включают лингвистические переменные нижнего уровня. Благодаря этому можно построить дерево лингвистических переменных и установить зависимость между ними.

Функции принадлежности из множества F={f_k,i}_k,i лингвистических переменных {в_k,i}_k,i необходимы для построения нечеткого вывода. В частности, каждому правилу грамматики из множества P ставится в соответствие функция принадлежности f_k,i. Эта двойственная система подстановок используется для вычисления смысла лингвистической переменной.

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

Грамматика для языка описания гибридных логических моделей Концептуальной основой автоматизации проектирования программных систем и решения задач анализа и синтеза являются накопленные проектные знания. В настоящее время в этой области собрано достаточное количество информации о существующих методах построения точных архитектур программных систем, шаблонов поведения и существующих компонентах готовых для повторного использования для последующей автоматизации всего процесса проектирования. Успешность автоматизации всего процесса проектирования зависит от создания единого формального базиса, обеспечивающего взаимодействие разнородных моделей, методов, технологий. Таким образом, актуальными задачами являются: выбор подходящего метода представления знаний обо всех этапах проектирования и составление алгоритмов автоматизированной композиции архитектурного решения, основанных на выбранных методах представления знаний [5].

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

Язык описания гибридных логических моделей строится на основе выбранных языка описания онтологий (Description Logic), языка описания правил (SWRL), модальной логики K_n.

Пусть N_R и N_C - непересекающиеся множества имен отношений и классов; N - множество натуральных чисел, N_I - множество имен объектов классов, M_n - множество модальных параметров, тогда:

Class | T | className | Class | Class Class | Class Class |

Class | relation. Class | relation. Class |

number relation | number relation (8)

где Class - это терм/класс; className N_C - имя класса; r N_R - имя отношения между классами; number N - натуральное число.

assertion a : Class | (a, b) : relation, (9)

где assertion - выражение, определяющее принадлежность объекта класса к какому-то определенному классу, и задающее отношения между объектами классов; a, b N_I - объекты классов.

rule (Condition consequence)

Condition atom | atom Condition

consequence atom

atom Class(x) | relation(x, y) | sameAs(x, y) | differentFrom(x, y), (10)

где rule - правило/зависимость значений объекта класса; condition - предусловие правила; consequence - последствие правила; x, y - переменные, объекты классов или конкретные значения данных; sameAs - отношение эквивалентности; differentFrom - отношение различия; atom - атомарное выражение.

ProbabilityExpr Class | ProbabilityExpr ProbabilityExpr |

ProbabilityExpr ProbabilityExpr | ProbabilityExpr |

[m] ProbabilityExpr | <m> ProbabilityExpr (11)

где mM_n - модальный параметр; ProbabilityExpr - модальная формула.

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

Для описания предметных областей, относящихся к многокомпонентным программным системам, разработан список наиболее употребляемых отношений:

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

has задает различные свойства объекта (например, характеристики программного компонента);

isConsequenceOf отражает причинно-следственные связи (например, выражение Postcondition isConsequenceOf.Task означает, что постусловие есть следствие задания автоматизации);

hasValue задает значения свойств объектов (например, выражение NameOfComponent hasValue.String означает, что имя компонента должно иметь значение с типом данных String);

consistsOf задает составные части объекта проектирования (например, многокомпонентная программная система состоит из компонентов и описывается следующим образом: System consistsOf.Component, и это будет означать, что система состоит хотя бы из одного компонента);

belongsTo задает параметр принадлежности описываемой характеристики к определенной области или внешнему компоненту (например, выражение Property consistsOf.Component относится к общей модели и определяет, что каждая характеристика должна относится к определенному компоненту);

specifiedBy задает отношение компонент-модель или компонент-документация. Используется при указании других (внешних) источников информации;

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

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

Задача описания правил сравнения характеристик программных компонентов и требований к программной системе решается с помощью применения системы правил ЕСЛИ-ТО. Таким образом, процедуры композиции многокомпонентной программной системы задаются с помощью правил, например как показано на следующем примере:

Property(?property) uses(?property, ?protocol)

hasValue(?protocol, “https”) matches(Reliable, ?property). (12)

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

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

Usability hasValue.Usable и Usability hasValue.Usable, (13)

соответственно.

Также в этом примере показано использование модального оператора для определения выражения «не очень».

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

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

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

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

В первом случае используется грамматика аналогичная описанной в п.1. Алгоритм цель проектирования - определяется как нечеткая система =(X, Y, S), где X и Y множества входных и выходных воздействий, являющихся частью универсума, содержащего наименования информационных потоков и их нечеткие характеристики; S нечеткий семантический гиперграф (нечеткая решетка), интерпретирующая структуру системы. Здесь S = (S_N, R, p), R множество типов соединения подсистем и двухместный нечеткий предикат инцидентности, определенный для всех пар (S_i, r) (S_iS_N, rR) и принимающий значения из интервала [0,1]. Нечеткие подсистемы S_N интерпретируются как базовые структуры алгоритмизации: линейная, развилка, цикл и т.п. Построенная грамматика (п.1) позволяет получать описания структуры различной сложности. При этом механизм вложенности подсистем реализуется как технологией заполнения вакантных подсистем, так и выбором типов подструктур. Механизм вертикального синтеза отражает принцип структурного программирования сверху-вниз. Вместе с тем, приведенная выше формализация является излишне громоздкой при разработке (или применении созданного) программного обеспечения.

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

Разработанный язык “Стимул” и транслятор с него в Паскаль используется в процессе обучения основам алгоритмизации в Волгоградской гимназии №9, в Волгоградском технологическом колледже, а также при изучении основ трансляции в ВолгГТУ.

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

ЗАКЛЮЧЕНИЕ

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

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

ЛИТЕРАТУРА

1. Половинкин А.И. Основы инженерного творчества. M.: Машиностроение, 1988.

2. Концептуальное проектирование. Развитие и совершенствование методов. Коллективная монография/ Под ред. В.А. Камаева. - М: Машиностроение, 2005.

3. Заболеева-Зотова А.В., Орлова Ю.А. Автоматизация семантического анализа документации технического задания// Вестник компьютерных и информационных технологий. М.: Машиностроение. 2008. №9.

4. Заболеева-Зотова А.В., Орлова Ю.А. Computer-Aided System of Semantic Text Analysis of a Technical Specification/ Information Technologies & Knowledge. Sofia: Institute of Information Theories and Applications FOI ITHEA, 2008. Vol.II. P.139-145.

5. Заболеева-Зотова А.В., Рощин М.А. Логическое моделирование характеристик программных компонентов// Интегрированные модели и мягкие вычисления в искусственном интеллекте. Труды IV-й Международной научно-практической конференции (Коломна, 28-30 мая 2007 г.). - М.: Физматлит, 2007. - С.141-148.

6. Рощин М.А., Заболеева-Зотова А.В., Камаев В.А. Использование (Semantic Web) - технологий при аннотировании программных компонентов// Information Theories and Applications. - 2005. - Vol.2, № 1. - P.171-173.

7. Заболеева-Зотова А.В., Пастухов А.Ю. Учет психолингвистических особенностей процесса чтения при разработке языков программирования// Концептуальное проектирование в образовании, технике и технологии. Сборник научных трудов ВолгГТУ Волгоград: ВолгГТУ, 2001.

8. Заболеева-Зотова А.В., Пастухов А.Ю. Применение естественно-языковых конструкций в программировании: преобразование текста программы в более удобный вид// Труды Международного семинара Диалог'2000 по компьютерной лингвистике и ее приложениям. 2000. Т.2. С.130-134.

Размещено на Allbest.ru