Е. А. Васин московский государственный университет им. М. В. Ломоносова vasinea@cs msu su Исследование

Вид материала

Исследование

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

Подобный материал:

• Московский государственный университет им. М. В. Ломоносова московский государственный, 2110.62kb.
• Палеографическое и лингвистическое исследование сборника смешанного состава XVII, 574.19kb.
• М. В. Ломоносова система качества митхт уп с 080502 дс. 03 Учебная программа, 89.44kb.
• Московский государственный университет им. М. В. Ломоносова, 690.3kb.
• М. В. Ломоносова филологический факультет кафедра истории зарубежной литературы Диплом, 949.48kb.
• Французское «житие святого этьена де мюре»: историко-лингвистическое исследование текста, 726.35kb.
• Московский государственный университет имени М. В. Ломоносова ежегодная научная конференция, 79.23kb.
• Перспективы применения низкотемпературных термодиффузионных технологий для решения, 60.11kb.
• В. А. Тумольский московский инженерно-физический институт (государственный университет), 27.44kb.
• Москва Издательство "Республика", 7880.24kb.

Е.А. ВАСИН

Московский государственный университет им. М.В. Ломоносова

vasinea@cs.msu.su


ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА

РАСПОЗНАВАНИЯ ИСКАЖЕННЫХ ОБРАЗОВ НА

ВРЕМЕННЫХ РЯДАХ СОВОКУПНОСТЯМИ НЕЙРОСЕТЕЙ


Аннотация

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


Описание задачи


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

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

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

Ниже дается обобщенная постановка задачи распознавания нелинейно искаженных образов на временных рядах.

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

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


Обзор существующих подходов


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

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

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

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

4. Одиночные нейросети. Основная проблема при использовании нейросетей возникает при существенных искажениях образов по длине. Если нейросеть с N входами обучена на образах длины N, а реальный образ на временном ряду имеет длину больше или меньше N, точность распознавания резко снижается: в первом случае, нейросети подается на вход лишь часть образа, причем в таком виде, на который она не была обучена, во втором же случае существенную роль начинает играть случайный шум на участках, не содержащих искомых образов.

5. Алгебраический подход. Алгебраический подход основан на идее разметки ряда с помощью заранее определенного набора условий, аксиом, накладываемых на точки ряда [1]. Исследования подхода, проведенные в нашей лаборатории, показали высокую эффективность, особенно для рядов с большими искажениями по длине и низкочастотными существенными искажениями по амплитуде. По нашему мнению, метод является интересным и перспективным, однако пока требует слишком много ручной работы по подбору систем аксиом, что является большой проблемой для многомерных временных рядов [2].


Подход, основанный на использовании совокупностей нейросетей


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

Более строго, задача разбивается на два этапа: обучение и распознавание. На первом этапе формируется массив сетей и настраивается система голосования, на втором этапе происходит распознавание образов на предъявленных участках ряда. Ниже оба эти этапа будут кратко описаны.


Этап обучения


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

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

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


Этап распознавания


Этап распознавания может быть организован по одной их нескольких схем, определяемых выбранным методом голосования. Ниже кратко описаны три из них.


Схема с наивным голосованием


Наиболее простая схема. Пусть на вход подается ряд длины N. Тогда процесс распознавания будет состоять из независимых шагов. На каждом шаге в качестве начальной точки берется следующая точка ряда, начиная с точки . Затем, из ряда выбирается M отрезков вида длины от до . Каждый такой отрезок подается на вход соответствующей нейросети; нейросети формируют промежуточные заключения в виде M векторов длины K. I-й компонент j-го вектора соответствует степени близости предъявленного j-й сети участка ряда к образу с номером k. Затем для каждого вектора определяется наиболее вероятный образ (по степени близости компонент к 1), определяется степень его близости к эталонному (p) и определяется параметр качества (степень размытости образов). Наконец, для определения наиболее вероятного образа, заканчивающегося в точке , строится некоторая функция достоверности для каждого вектора; мы в качестве функций достоверности использовали линейные относительно p и q и ступенчатые функции с порогами на q. Если максимальное значение функции достоверности на шаге преодолело порог (этот параметр подбирается на этапе обучения), участок ряда перед размечается наиболее достоверным образом.

Одна из наиболее существенных проблем наивного голосования состоит в том, что если на участке присутствует более вероятный образ, чем на участке , однако оба они преодолевают порог достоверности, то первый образ будет частично «затерт» вторым. Это может привести к появлению на выходе алгоритма априори некорректной картины распределения образов во времени.


Схема с голосованием в порядке уменьшения вероятности


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

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

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

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

Для борьбы с этими эффектами было разработано еще два «промежуточных» типа голосования, однако объем статьи не позволяет их рассмотреть, так что тут мы ограничились только двумя экстремальными случаями.


Схема с корректным голосованием


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


Результаты тестирования


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

Искажения на участках второго типа (появление неисправности)	Одиночные нейросети (лучший результат)	Наивное голосование	Голосование в порядке уменьшения вероятности
Длина образа = 10
0%	100%, 0%	100%, 0%	100%, 0%
10%	86%, 2.7%	86%, 2.7%	87%, 2.1%
20%	87%, 9.6%	87%, 9.6%	87%, 6.9%
Длина образа от 8 до 12
0%	66%, 10%	100%, 0%	100%, 0%
10%	39%, 12%	84%, 10%	65, 7.1% 73%, 10%
20%	31%, 28%	60%, 26%	60%, 22%
Длина образа от 7 до 14
0%	44%/10%	100%, 0%	100%, 0%
10%	31%, 19%	77%, 15%	69%, 15%
20%	23%, 30%	53%, 25%	55%, 21%

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


Список литературы

1. Рудаков К.В., Чехович Ю.В. О проблеме синтеза обучаемых алгоритмов выделения трендов (алгебраический подход). // Прикладная математика и информатика N 8. М. Изд-во факультета ВМиК МГУ, 2001. С. 97-113.
   
2. Коваленко Д.С., Костенко В.А., Васин Е.А. Исследование применимости алгебраического подхода к анализу временных рядов. // Тезисы конференции МСО-2005.
   
3. Васин Е.А. Распознавание искаженных образов на временных рядах совокупностями нейросетей. // Тезисы конференции МСО-2005.
   
4. Шугай Ю.С., Доленко С.А., Персианцев И.Г., Орлов Ю.В. Нейросетевые алгоритмы прогнозирования событий и поиска предвестников в многомерных временных рядах.