автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Интеллектуальная система моделирования и оценки вероятностных характеристик временных рядов

/

Самарский Государственный аэрокосмический университет

На правах рукописи ДМИТРИЕВА ЕЛЕНА ВИЛЬЕВНА

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

ВРЕМЕННЫХ РЯДОВ

Специальность 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель - д.т.н., проф. Прохоров С.А.

имени акад. С.П.Королева

Самара 1999

СОДЕРЖАНИЕ

стр.

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ, ЕДИНИЦ И ТЕРМИНОВ 5

ВВЕДЕНИЕ 9

ГЛАВА 1. АНАЛИЗ СОВРЕМЕННЫХ МЕТОДОВ И СРЕДСТВ 23 МОДЕЛИРОВАНИЯ И ОЦЕНКИ ВЕРОЯТНОСТНЫХ ХАРАКТЕРИСТИК ВРЕМЕННЫХ РЯДОВ

1.1. Объекты исследования 23

1.2. Модели случайных процессов 25

1.3. Модели потоков событий 31

1.4. Вероятностные характеристики процессов и потоков 33

1.4.1. Основные виды нормированных корреляционных 34 функций

1.4.2. Законы распределения интервалов и их моментные 35 характеристики

1.4.3. Законы распределения сумм интервалов 36

1.4.4. Интервальная корреляционная функция 36

1.4.5. Интенсивность потока 40

1.5. Методы и алгоритмы моделирования временных рядов с 41 заданными свойствами

1.6. Методы и алгоритмы оценивания вероятностных 45 характеристик временных рядов

1.7. Проблемы интеллектуализации программных средств АСНИ 48 Выводы по первой главе и основные результаты 52

ГЛАВА 2. МЕТОДЫ ФОРМАЛЬНОГО ПРЕДСТАВЛЕНИЯ 53 ЗНАНИЙ ПРЕДМЕТНОЙ ОБЛАСТИ ДЛЯ ЗАДАЧИ АВТОМАТИЧЕСКОЙ ГЕНЕРАЦИИ ИСПОЛНЯЕМОГО МОДУЛЯ ПО ЕЯ-ОПИСАНИЮ

2.1. Основные виды логико-лингвистических моделей 53

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

2.3. Естественно-языковое описание задач и объектов предметной 60 области

2.3.1. Анализ синтаксической структуры предложения 61

2.3.2. Исследование формальных методов определения части 67

речи

2.3.3. Анализ семантической структуры предложения 78

2.3.4. Анализ прагматической структуры предложения 82

2.4. Анализ процесса генерации программных модулей 84

2.5. Методика решения задачи автоматической генерации 87

исполняемого модуля по естественно-языковому описанию

Выводы по второй главе и основные результаты 91

ГЛАВА 3. РЕАЛИЗАЦИЯ ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЫ 92 МОДЕЛИРОВАНИЯ И ОЦЕНКИ ВЕРОЯТНОСТНЫХ ХАРАКТЕРИСТИК ВРЕМЕННЫХ РЯДОВ

3.1. Назначение, возможности и структура системы 93

3.2. Функциональное назначение элементов системы 94

3.2.1. Лингвистический процессор и его подсистемы 94

3.2.2. База знаний и фактов ЮЗ

3.2.3. Словарь базовых модулей 106

3.2.4. Подсистема генерации текста управляющей программы на 107 языке Си

3.3. Основные характеристики интеллектуальной системы 109

3.4. Технические характеристики инструментального и П1 программного обеспечения

Выводы по третьей главе и основные результаты ИЗ

ЗАКЛЮЧЕНИЕ 114

СПИСОК ИСПО ЛЬЗОВ АННЫХ ИСТОЧНИКОВ 117

ПРИЛОЖЕНИЕ 1. Параметры рекурсивных фильтров и типовые 126

законы распределения ПРИЛОЖЕНИЕ 2. Фрагмент словаря основных программных 129

модулей предметной области ПРИЛОЖЕНИЕ 3. Пример программы моделирования 136

нестационарного временного ряда по ЕЯ-описанию

ПРИЛОЖЕНИЕ 4. Документы, подтверждающие внедрение 146

результатов диссертационной работы

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ, ЕДИНИЦ И ТЕРМИНОВ

АСНИ — автоматизированные системы научных исследований БД — база данных БЗ — база знаний BP — временной ряд ВХ — вероятностная характеристика ЕЯ — естественный язык ЗР — закон распределения ИКФ — интервальная корреляционная функция ИМ — имитационное моделирование ШИШ — интеллектуальный пакет прикладных программ ИС — интеллектуальная система КС — контекстно-свободная КФ — корреляционная функция ЛП — лингвистический процессор МО — математическое ожидание НВР — неэквидистантный временной ряд НРД — неравномерная дискретизация ОИ — объект исследования ПО — предметная область ПП — программный продукт ПСП — псевдослучайная последовательность ПЭВМ — персональная ЭВМ

РД — равномерная дискретизация САПР — система автоматизации проектирования СКО — среднеквадратическое отклонение

СП — случайный процесс ЯПЗ — язык представления знаний

< глаг> — глагол <деепр> — деепричастие

< до> — деепричастный оборот <нар> — наречие

< прил> — прилагательное

< прич> — причастие

< по> — причастный оборот

< сущ> — существительное

< гс> — глагольное словосочетание

< ис> — именное словосочетание

< пс > — предложное словосочетание

At — множество атомарных значений атрибутов С (J) — интервальная корреляционная функция CX(J) _ оценка интервальной корреляционной функции

CASE — Computer Aided Software Engineering - автоматизированное проектирование программных продуктов D — многомерный временной ряд DX — дисперсия Е — множество фраз естественного языка ent [о] — операция выделения целой части

fr — имя фрейма fx (X) — плотность распределения случайной величины X Fx (X) — функция распределения случайной величины X Fun — множество функций вычисления атрибутов G — грамматика языка представления знаний К — количество моделей предметной области Ка — коэффициент асимметрии Кэ — коэффициент эксцесса Кх(т) — корреляционная функция непрерывного СП X(t)

Kx(j) _ оценка корреляционной функции

Lk — число анализирумых отсчетов Md — множество моделей объектов предметной области M¡ — число функций вычисления /-го статусного данного Nj — длина у'-ой последовательности (временного ряда) Nk — объем выборки

Nst — число статусных атрибутов предметной области

Р — вероятность Prg — совокупность программных модулей обработки данных Prtq — прототип решения задачи Tskq Q — число задач предметной области R — правила вывода цепочек языка Rz — число реализаций (последовательностей) Rui — совокупность правил - продукций S — предложение грамматики

St — совокупность статусных атрибутов предметной области Tsk — множество задач предметной области Tskq — q-ая задача предметной области

t¡ — момент появления /-го отсчета временного ряда X (t)— случайный процесс Xj (7) — у'-ая реализация СП X(t)

о

X(t} — центрированный СП X(t)

Xj¡ = x/tj) — отсчет временного ряда (выборочное значение X (t)) {xj(tj)}={xji} — многомерный временной ряд < V,-, h¡> — z-ый слот фрейма

Ум — нетерминальный словарь грамматики VT — терминальный словарь грамматики Q [X(t)] — вероятностная характеристика случайного процесса X(t)

^ С С w и

а — показатель затухания нормированной корреляционной функции 5 [о] — дельта функция Дирака

£ — среднеквадратический критерий Я — интенсивность потока Ato — интервал равномерной дискретизации

A t — временной интервал между отсчетами временного ряда Рх(т) — нормированная корреляционная функция Ч тах — максимальный интервал корреляции <ри(и) — характеристическая функция

сщ — частота колебания нормированной корреляционной функции £ — случайная величина

ВВЕДЕНИЕ

Широко признанными методами научных исследований являются моделирование и идентификация, поскольку они позволяют решать задачи анализа, синтеза и оптимизации сложных технических объектов, прежде всего в автоматизированных системах научных исследований (АСНИ) (см. рис. 1).

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

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

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

АСНИ дают возможность измерять информативные параметры изучаемого явления, строить, уточнять модель объекта исследования (ОИ), оценивать его характеристики.

Методы оценивания характеристик ОИ делятся на экспериментальные, теоретические и с использованием имитационного моделирования [62]. Экспериментальные исследования, обладая высокой точностью и достоверностью, требуют, как правило, больших материальных затрат на полную или частичную реализацию объекта. Теоретические методы,

Воздействие внешних факторов

ОБЪЕКТ исследования

(явление, процесс)

Априорная информация обОИ

БАЗА МОДЕЛЕЙ ОИ

Модель ОИ

Структура АСНИ

Выбор

модели ОИ

Параметры модели ОИ

пользователь

АСНИ1

УСД Интер-

• фейс

ЭВМ

Интерфейс пользователя

Система статистической обработки

С-, 1 "- ■ X : л \ Виды обеспечения АСНИ : ;

Информационное: Алгоритмическое Программное Методическое Метрологической Техническое

Апостериорная информация

Уточнение модели ОИ

рис. 1

о

Компоненты задач моделирования и идентификации

Модель и ее характеристики

> / у

ЗАДАЧА МОДЕЛИРОВАНИЯ <=>

Совокупность моделей

Реальные данные предметной области

у

ЗАДАЧА <=> ИДЕНТИФИКАЦИИ

Данные моделирования

Оценка качества полученных решений

/\ / ^

> с

у

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

> * V

Модель и ее характеристики

рис. 2

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

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

Реализация триады "модель-* алгоритм -» программа" [31] приводит к созданию библиотек, включающих в себя программы обработки данных предметной области, а также вспомогательные сервисные программы.

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

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

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

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

- наличие навыков программирования;

- знание внешних и внутренних межмодульных связей;

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

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

Таким образом, объектом исследования в диссертационной работе является интеллектуальная система АСНИ.

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

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

- язык меню;

- язык шаблонов;

- язык типа "вопрос - ответ";

- язык запросов к базам данных (БД);

- графические интерфейсы;

- естественный язык (ЕЯ).

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

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

Формальные языки типа "вопрос - ответ" исторически происходят от информационно-поисковых процедур [102]. Для большинства систем, использующих такие языки характерна жесткая структура диалога, при которой каждое последующее высказывание (возможно, не связанное с предыдущим) воспринимается как очередной запрос [38].

Языки запросов к базам данных предоставляют для обеспечения взаимодействия с пользователем специальные формализованные языки. При этом пользователь должен знать синтаксис этих языков, логическую структуру БД, обладать навыками программирования. По возможностям практического использования системы общения с БД значительно опережают системы типа "вопрос - ответ" [38].

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

кроме того, еще и знаниями о связях между пиктограммами и порядке их соединения.

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

Исследования в области "обработки естественного языка" (Natural Language Processing) оформились в самостоятельное направление искусственного интеллекта в конце 60-х годов. Задачей этого направления стала разработка методов, алгоритмов и программных средств реализации процесса общения на естественном языке. Сложность создания средств ЕЯ-взаимодействия с компьютером обусловлена отсутствием универсальной формальной базы, поэтому при разработке систем ЕЯ-общения для различных прикладных задач приходиться налагать ограничения на предметную область и на модель языка. Исследованиям в области ЕЯ-общения посвящены работы многочисленных отечественных и зарубежных авторов - Апресяна Ю.Д. [5], Поспелова Г.С. [64-66], Поспелова Д.А. [26, 51, 66, 67], Попова Э.В., Преображенского А.Б. [27], Уотермана Д., Winograd Т. [102], Grosz B.J., Haas N. [98] и др.

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

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

• Под лингвистическим процессором, как правило, понимаются автоматизированные средства обработки текстовой информации на естественном языке, в том числе и не рассчитанные на работу с ЕЯ в полном объеме [5].

Обзор литературных источников показывает, что в направлении создания лингвистических процессоров ведутся многочисленные работы - [5, 54, 59, 95]. При этом ЛП строятся с учетом ограничений на предметную область и на модель языка. В [15] приводится классификация существующих ЛП по тре