Содержание к диссертации
Введение
1. Проблема распознавания образов в анализе массивов взаимосвязанных данных 21
1.1. Массивы взаимосвязанных данных и задачи их анализа 21
1.2. Специфика задачи распознавания образов в массивах взаимосвязанных данных 24
1.3. Методы распознавания событий в сигналах со сложной структурой 28
1.4. Проблема малой выборки и методы регуляризации процесса обучения .;, 29
1.5. Основные задачи исследования 37
2. Вероятностный подход к распознаванию взаимосвязанных объектов 40
2.1. Граф смежности совокупности взаимосвязанных объектов 40
2.2. Скрытое марковское случайное поле принадлежностей объектов к классам 41
2.3. Локальные (индивидуальные) апостериорные вероятности классов объектов 42
2.4. Апостериорное марковское случайное поле классов совокупности взаимосвязанных объектов 45
2.5. Трудности реализации оптимальных решающих правил распознавания для произвольного графа смежности взаимосвязанных объектов 47
3. Процедуры распознавания для древовидных совокупностей взаимосвязанных объектов 51
3.1. Априорное и апостериорное древовидные марковские поля 51
3.2. Процедура фильтрации 58
3.3. Процедура интерполяции 61
3.4. Древовидная аппроксимация решетчатых графов смежности 63
4. Процедуры обучения: восстановление функций локальных апостериорных вероятностей классов в пространстве признаков з
4.1. Обучение на основе метода опорных векторов 66
4.2. Обучение на основе восстановления функций апостериорных вероятностей классов 76
4.3. Прямое восстановление апостериорных вероятностей классов 83
5. Обучение распознаванию линейно упорядоченных совокупностей взаимосвязанных объектов 89
5.1. Вероятностная задача распознавания потока событий 89
5.1.1. Распознавание скрытой марковской последовательности случайных событий 89
5.1.2. Распознавание марковского случайного поля с цепочечным графом смежности элементов 94
5.2. Детерминистская задача распознавания последовательности событий 98
5.2.1. Задача обучения и разделимость обучающего множества 98
5.2.2. Алгоритмы обучения 102
5.2.3. Формирование признаков 109
5.2.4. Последовательное распознавание событий 111
5.2.5. Источник кривых и граф возможных решений о классах событий 118
5.2.6. Алгоритм распознавания 129
6. Обучение распознаванию образов в пространствах взаимосвязанных признаков : 132
6.1. Природа пространств взаимосвязанных признаков 1 32
6.2. Требование гладкости решающего правила как метод регуляризации при обучении распознаванию образов по малым выборкам 133
6.3. Построение оптимальной разделяющей гиперплоскости по методу опорных векторов с учетом гладкости решающего правила 135
6.4. Восстановление функций апостериорных вероятностей классов с учетом критерия гладкости 138
6.5. Выбор величины штрафа на негладкость решающего правила 140
6.6. Регуляризация с учетом коррелированности признаков 143
7. Обучение распознаванию образов в просфанствах признаков парных отношений между объектами 148
7.1. Пространство признаков парных отношений между объектами 148
7.2. Оптимальное линейное решающее правило распознавания 152
7.3. Регуляризация решающего правила по критерию гладкости 154
7.4. Кластерные методы регуляризации 158
8. Обучение распознаванию зон коллекторов нефти и газа в монолитных породах по данным сейсморазведки с использованием результатов испытаний скважин 170
8.1. Проблема сейсмической разведки месторождений нефти и газа в монолитных породах 170
8.2. Текстурные признаки локальных коллекторских свойств породы в массивах данных сейсмической разведки 173
8.3. Обучение распознаванию зон коллекторов с использованием скважинной информации в качестве данных учителя 177
8.4. Прогноз зон коллекторов в фундаменте месторождения Бомбей Хай 182
9. Обучение распознаванию классов пространственной структуры белков 184
9.1. Проблема распознавания классов пространственной структуры белков : 1 84
9.2. Формирование пространства признаков 187
9.3. Исходные данные и результаты предварительных исследований 189
9.4. Улучшение надежности распознавания 196
Основные научные результаты работы 202
Литература
- Методы распознавания событий в сигналах со сложной структурой
- Апостериорное марковское случайное поле классов совокупности взаимосвязанных объектов
- Процедура интерполяции
- Прямое восстановление апостериорных вероятностей классов
Методы распознавания событий в сигналах со сложной структурой
На первый взгляд, несколько менее очевидным, но, в сущности, не менее ярким примером наличия внутренней структуры на множестве признаков является задача построения решающего правила распознавания класса пространственной структуры полимерной молекулы белка по исходной последовательности составляющих ее аминокислотных остатков [94, 95, 100, 102, 104-107,111, 114, 119, 122, 126, 132, 133, 135, 136, 149, 153], чрезвычайно актуальная в современной биоинформатике. При обучении распознаванию класса пространственной структуры удобно строить вектор признаков каждого отдельного белка в составе обучающей выборки белков с заранее известной структурой как совокупность относительно легко вычисляемых количественных показателей. Эти показатели определяют степень «сходства» или «несходства» аминокислотной последовательности белка, имеющей вид цепочки из нескольких сотен символов над алфавитом двадцати существующих в природе аминокислот, с аминокислотными последовательностями некоторого фиксированного множества базовых признакообразующих белков. При этом знание пространственной структуры признакообразующих белков, вообще говоря, не требуется. Важно лишь, чтобы они достаточно хорошо представляли разнообразие аминокислотных последовательностей белков рассматриваемого типа.
Возможность измерить различие между любыми двумя аминокислотными цепочками позволяет естественным образом рассматривать признако-образующие белки, то есть сами признаки, как элементы метрического пространства. Тогда оказывается возможным различать «близкие» и «далекие» признаки в смысле метрики данного пространства.
Тогда при построении, например, линейного решающего правила распознавания по обучающей выборке белков с известными пространственными структурами элементы направляющего вектора разделяющей гиперплоскости оказываются связанными с соответствующими признакообразующими белками. Но тогда естественным оказывается априорное предположение, что близким признакам должны соответствовать не слишком сильно отличающиеся друг от друга коэффициенты разделяющей гиперплоскости.
В итоге, как и в рассмотренной выше задаче обучения распознаванию сигналов, мы приходим к идее априорной «гладкости» коэффициентов разделяющей гиперплоскости, но теперь уже не на оси линейного порядка, а в метрическом пространстве признаков. Проведенные эксперименты показывают, что штраф на негладкость позволяет существенно улучшить экстрапо-ляционные свойства решающих правил распознавания классов пространственной структуры белков, полученных при обучении по малым выборкам.
Таким образом, существует широкий класс практических задач распознавания образов в массивах взаимосвязанных данных, которые не укладываются в традиционную постановку задачи распознавания образов. Необходимость расширения классической постановки связана с тем обстоятельством, что априорными структурными соотношениями связаны как объекты, предъявленные для распознавания, так и их признаки.
Примером такого расширения классической постановки является задача распознавания образов в сигналах с изменяющимися вероятностными свойствами, получившая название динамического подхода к проблеме распознавания образов [68]. Данный подход основан на модельном представлении о совокупности объектов как о последовательности событий. Предъявление очередного объекта рассматривается как случайное событие, последовательность которых образует случайный поток классифицированных событий, а изменение признаков понимается как условный случайный процесс на интервале от момента появления данного события до следующего. Но в данном подходе рассматривается только один возможный вид взаимозависимости объектов - их упорядоченная последовательность (цепочка). Более сложные и типичные для практики виды взаимосвязи объектов в данном подходе не рассматривается, как не рассматривается и взаимосвязанность признаков.
В целом, взаимосвязанность элементов массива данных вносит существенную специфику, как в процесс обучения, так и в процесс распознавания.
С одной стороны, заранее известные структурные отношения между элементами массива и их признаками несут существенную априорную, информацию об искомом решающем правиле и ожидаемом результате, сокращая степень его неопределенности. Наличие естественной априорной информации создает принципиальную возможность значительного повышения статистической стабильности результата распознавания. С другой стороны, эта же взаимосвязанность резко усложняет решение задач обучения и распознавания с теоретической и вычислительной точек зрения. А именно, появляется проблема учета данной информации в математической постановке задачи и проблема усложнения алгоритмов обучения и распознавания.
В данной работе предложена неклассическая постановка проблемы обучения распознаванию образов, понимаемая прежде всего как расширение классической постановки в связи с тем, что рассматриваются априорные структурные соотношения, заданные как на объектах распознавания, так и на их признаках.
В этой связи рассмотрены как общеметодологические проблемы, обусловленные наличием отношения порядка на множестве элементов массива данных, которые характерны для всех приложений, так и специальные, которые обусловлены особенностями классов решаемых задач.
Апостериорное марковское случайное поле классов совокупности взаимосвязанных объектов
Для предъявленного массива данных Y плотность полного распределения/(Г) в (2.1) является константой и обеспечивает нормировку апостериорной плотности \n(X\Y)dX = \,если f(Y) = \C3(X )T\{Y\X )dX (2.4) где интегрирование понимается в смысле Лебега по соответствующей а-конечной мере. В частности, если множество значений целевой переменной конечно Я" = {1,...,/??}, как это имеет место в задачах распознавания образов, то в ка 42 честве а-алгебры подмножеств множества SC удобно принять множество всех его подмножеств с так называемой считающей мерой, численно равной числу элементов подмножества и всегда являющейся а-конечной. Тогда априорная Q(X) и апостериорная к(Х\Г) плотности распределений являются априорной и апостериорной вероятностями для каждой совокупности значений номеров классов объектов X=(x,,t J ) є і-" 7 , а интегралы Лебега по считающей мере (2.4) есть суммы 2 (;ҐГ) = І, f(X)= ЕфґМПЛ Хє.9СЩ Х є ]Т{ В случае взаимосвязанных массивов вероятностные распределения на множестве переменных, связанных некоторым отношением соседства, являются случайными полями. Определение вероятностных свойств случайных полей с произвольным графом смежности представляет трудноразрешимую теоретическую проблему [96, 113, 121, 137, 147, 154]. Обычно предполагается, что такие поля являются марковскими, вероятностные свойства которых в целом полностью выражаются через условные распределения отдельных переменных х, относительно соседних xs по графу смежности (s, t) eG. Тем не менее, простые реализации алгоритмов известны только для сигналов, когда граф G является цепью, а случайное поле X является скрытым марковским случайным процессом, подлежащим восстановлению [67-71].
Будем полагать, что наблюдаемое поле Y = (y,Jel) образовано случайными векторами у,, условно независимыми относительно скрытого поля X=(xh /є7), причем условные вероятностные свойства каждого из них полностью определяются только значением соответствующей скрытой переменной и выражаются известной условной плотностью распределения v/,(y, X) - \\i,(Уі і хі) Тогда условные вероятностные свойства наблюдае 43 мого случайного поля в целом определяются условной совместной плотностью распределения: П0Ч ) = ГЬ,(У,1 ,)- (2-5) leT
Каковы бы ни были априорные предположения о скрытом случайном поле, априорное совместное распределение С,(Х) определяет частные априорные плотности распределения скрытых переменных cji(xt). Для известного значения наблюдаемой переменной у, апостериорное распределение значений соответствующей скрытой переменной определится выражением / ,( , ІУ,)= Z WMA )- (2-6) X, Є.ЯГ Во многих практических задачах оказывается более удобным выражать связь между скрытым и наблюдаемым полями именно в виде частных апостериорных распределений pt(x{ уг), чем в виде условных распределений v,(y, I ,) Теорема 2.1 Пусть наблюдаемые случайные переменные Y=(yh /є /) условно независимы относительно скрытого случайного поля классов объектов Х= (xh ІєТ). Тогда локальные апостериорные распределения pt(x,\y,), ієТи априорное совместное распределение Q(X) полностью определяют апостериорное скрытое поле классов я( 1П п( \ПМ ,ІУ,)- (2-7) іе Г Доказательство. На основании (2.6) выразим условные распределения р (х I V ) Ц ,(У,\Х,) = 5 /Л-Очл(У/К)- Подставив в (2.5) и в (2.1), полу /,( ,) w чим n{X\Y) C,{X) П Х ЮМ ЛУ, \Х\) П \ / Так как суммы в \iel-х е.Я JleT Я,\Хі) произведении не зависят от значении скрытых переменных, то это утверждение эквивалентно (2.7). Полная информация о скрытых переменных Х= (xh /є7) заключена в исходных данных и априорном совместном распределении вероятностей. Из теоремы 2.1 следует важный вывод, что вся информация в данных полностью выражается в частных апостериорных распределениях скрытых переменных, опирающихся только на один соответствующий элемент массива данных.
Поэтому без всяких потерь анализ массива данных всегда можно выполнить в два этапа: сначала из каждого элемента массива у, извлечь информацию о значении соответствующей скрытой переменной в виде ее апостериорного распределенияpt(x, yt), teT, а затем такие «размытые» решения согласовать между собой с учетом совместного априорного распределения
В частности, для задач распознавания образов в массивах взаимосвязанных объектов естественным способом поиска локальных апостериорных распределений pt(xt\ у,) является обучение по данным учителя, когда вместе со значениями наблюдаемых переменных у, известны и значения номеров классов х,. Теорема 2.1 показывает, что при известном априорном распределении СрС) объектов по классам не обязательно предъявлять данные учителя в упорядоченном виде, это может быть разрозненный набор объектов с известными номерами классов.
При таком предположении задача обучения распознаванию образов в массивах взаимосвязанных объектов ничем не отличается от классического обучения. Изменение традиционной процедуры обучения возникнет лишь при неизвестном априорном распределении ТЛ1- Только в этом случае потребуется дополнительная информация о локализации представителей отдельных классов во взаимосвязанном массиве, и возникнет необходимость в новых процедурах восстановления совместного априорного распределения по данным учителя.
Процедура интерполяции
Задача построения оптимальной разделяющей гиперплоскости эквивалентна задаче максимизации ,, или, что то же самое, минимизации а2=ага, поскольку квадрат нормы «нового» вектора а равен а а = (1/, )а а=(1/ ; ) при а а = 1, то есть при фиксированном квадрате нормы «старого» вектора. В результате мы придем к целевой функции ara mm, gy(aTyy+/?) !, у= l,...,N. (4.5) По своей форме этот критерий представляет собой стандартную задачу квадратичного программирования, которая решается также стандартно.
Но такой подход становится бессодержательным в случае неразделимых классов (рис. 4.16) из-за того что ограничения (4.3), и следовательно (4.7) несовместны. Чтобы получить аналогичный критерий для таких выборок, используем следующий прием. Пусть невозможно найти такой вектор а для которого выполняются неравенства (4.3) для положительного зазора ,, или, что то же самое, неравенства g;(ary7 +b) E) при а а = 1, однако это всегда можно сделать, допустив неотрицательные сдвиги g;(a у j +/ ) ,- j. Сдвиги 8; 0 должны-быть по возможности малы, обеспечивая как можно больший зазор , -тах или l/,-»min. Это можно выразить компромиссным критерием, например, 1/, + С . 8 - min или l/ + C ._j8y — min при а7а=1 с достаточно большим положительным коэффициентом С, минимизирующим сдвиги. Вводя обозначение 8; = (\/Z))bj и понимая под а нормированный направляющий вектор (1/)а, мы придем к критериям l/,2 + CY, =15; -» min либо і/с;2 + С]Г ._, 82 - min , где =а а, с ограничениями gДа у у+ Ь) 1 -8; и 87 0 . Идея такого приема заключается в мысленном сдвиге в сторону правильного (своего) класса 8, 0 тех объектов у,, которые попали в чужую область, при неизменном положении 8у = 0 тех объектов, которые не мешают 0 о#Фї//
Таким образом, мы получаем две задачи поиска оптимальной разделяющей гиперплоскости для разделимого и неразделимого случаев: Л а7а + С 5 - min, Первый критерий: 7=1 (4.6а) g7(a ry7+) l-5;, 8, 0, j = l...,N. N ara + C]TS - min, Второй критерий: j=\ (4.66) [gj(BTyJ+b) ]-bJt 8,. 0, y = l,...,M В обеих постановках нахождение оптимальной разделяющей гиперплоскости сводится к решению стандартной задачи квадратичного программирования с числом аргументов, равным размерности пространства признаков плюс число элементов обучающей выборки, и числом ограничений, равным удвоенному числу элементов выборки.
Переход к двойственной задаче в каждой из этих постановок приводит к эквивалентной задаче квадратичного программирования с числом аргументов, равным числу элементов выборки, что удобно при работе с малыми выборками. Более существенное преимущество двойственной формулировки задачи заключается в том, что она позволяет выделить в составе обучающей выборки те элементы, называемые опорными векторами, которые только и определяют оптимальную разделяющую гиперплоскость.
Важно отметить, что решение всегда будет находиться на границе области поиска. Это означает, что неравенства #/(агу + /;) 1-5 в (4.6) пре вращаются в равенства g.(a yJ+b) = ]-bJ для некоторых векторов у7.Именно эти объекты обучающей выборки В.Н. Вапник называет опорными векторами, так как только они участвуют в формировании направляющего вектора а оптимальной разделяющей гиперплоскости, представляющего собой их линейную комбинацию (рис. 4.1а и 4.2). Чтобы убедиться в этом, рассмотрим функции Лагранжа, соответствующие задачам (4.6,а) и (4.6,6).
Для первого критерия (4.6а) удобно записать функцию Лагранжа в виде Ца,6Д1,...Дл,,81,...,8А,,ц1,...,цлг) = -а а + —8у lr С N (4.7) j=i У=І где X 0, ц. 0,j = \,...,N - неотрицательные множители Лагранжа. Решением задачи является седловая точка функции Лагранжа L(a ,X1,..., /V,51,...,5yV,Li1,...,bi;V) min по a,/ ,5,,...,5/Y (4.8) без каких-либо ограничений и L(a,b,Xl,...,XN,bl,...,bN,iil,...,iiN)- max по Х,,..! , ,...,ц v (4.9) при ограничениях X 0, ц . 0, j -\,...,N . Первое из этих условий дает УяЦа,ЬД1,...Д ,5,,...,5л,,і1,...,Цд,) = 0, dL(a,b,X],...,XN,bi,...,bN,\i],...,\iN) о db dL(a,b,Xl,...,Xs,bl,...,bx,].il,... x) = 0, ./ = 1,...,Л/ as, откуда получим 7=1 А,у+цу=С/2, J=1,..,AC (4.12)
Заметим, что А,у 0,ц.- 0 и А,.+ц.-=С/2, тогда 0 А,. С/2 и О ц.. С/2. Подстановка (4.10) в условие (4.9) превращает последнее в целевую функцию, двойственную по отношению к исходной целевой функции (4.6) 2 /=U-=I 2 /=i /V /V /=1 А=1 7 = 1 7=1 7=1 где в силу равенств (4.11) и (4.12) активными аргументами являются только множители Лагранжа X 0, j = 1,... Д Таким образом, мы приходим к следующей двойственной формулировке задачи построения оптимальной разделяющей гиперплоскости в виде задачи квадратичного программирования: ;V 1 . V .V W(Xl,...,XN) = YJXJ--YJZ(gJgky1jyk)XJXk -»max, Н (4.13) I ,.gy = о, o i7 lc,7 = l... . y=i 2 Здесь оптимальные значения Х} 0 являются множителями Лагранжа при ограничениях g-(a7y;+ ) 1 - 8 , каждое из которых связанно с соответствующим элементом обучающей выборки у„ причем положительные множители Xj 0 указывают активные ограничения g .(а у +/ )= 1 -8;-. Направляющий вектор оптимальной разделяющей гиперплоскости, согласно (4.10), есть линейная комбинация, вообще говоря, всех векторов в со 72 ,v ставе обучающей выборки а = Х -g -у Днако фактически в его формиро вании участвуют лишь те их них, при которых множители Лагранжа отличны от нуля А./ 0. Это и есть опорные векторы, поскольку только на них «опирается» оптимальная разделяющая гиперплоскость. В случае линейно разделимой обучающей выборки это крайние точки подвыборок первого и второго класса, которыми они обращены друг к другу (рис. 4.1а). Если же выборка линейно неразделима, то ситуация несколько сложнее, и вместе со сдвинутыми «мешающими» точками подвыборок (рис. 4.2) опорными будут также и некоторые «хорошие» точки обеих подвыборок из числа крайних.
Прямое восстановление апостериорных вероятностей классов
Как было уже сказано, основной задачей при формировании признаков является отображение исходных данных в такое признаковое пространство, где выполнялась бы гипотеза компактности для классов объектов, имеющих содержательный смысл в исходном поле данных. Предварительно отметим следующее обстоятельство. Очевидно, что состав обучающих множеств Z и Z,/ существенно различен, в зависимости от того, какие объекты выделяет учитель в качестве граничных в исходном поле данных. Например, кривая может быть сформирована событиями разных типов (классов), каждый из которых определяет свое характерное возмущение, вызываемое его событием на кривой. Поэтому в одном случае могут быть указаны граничные объекты только одного класса, а другом - только некоторых или всех классов.
Следовательно, возникает необходимость сформировать т различных признаковых пространств для выделения граничных объектов каждого класса в отдельности, где т - число классов граничных объектов в исходном поле данных. В общем случае, когда граничные объекты некоторых классов не различаются между собой при построении границ в поле данных, необходимо меньшее число различных признаковых пространств. Но тогда алгоритм распознавания усложнится, так как потом необходимо определить классы объектов, выделенных в качестве граничных. Как было показано, объекты, выделенные в качестве граничных образуют в признаковом пространстве множество Z (а), где а - направляющий вектор разделяющей на уровне d гиперплоскости. Тогда необходимо, чтобы объекты разных классов, выделенные в качестве граничных, были разделимы, образуя множества 1/iiCiZ (а), к= 1,...,/», выпуклые оболочки которых не пересекаются. Для этого, возможно, потребуется сформировать новое пространство.
Рассмотрим один из возможных подходов к формированию признаков для экспериментальных кривых. Перенумеруем объекты в матрице данных Y (nxN) и представим ее в виде фрагмента многомерной кривой по У, = (у,, 1 / /V) из /V отсчетов. Будем рассматривать только одномерные экспериментальные кривые. Тогда, согласно введенным ранее обозначениям для матрицы данных, получим фрагмент одномерной кривой Y»=(y„\ut N). Рассмотрим на кривой скользящее окно У/ 1 =(ysJ.-X s t + x) дли . ны А +т, содержащее в себе А, +т +1 отсчетов, где X 0, т 0 - число отсчетов слева и справа от опорной точки окна /. Пусть опорная точка скользящего окна совпадает с моментом появления некоторого события t = 9,-. Выберем длину скользящего окна так, чтобы не захватывать моменты появления самых близко расположенных соседних событий А,, т min (&,-+ - &,), i=\,...JC-\.
Будем полагать, что фрагмент Y можно продлить влево на А, и вправо на т отсчетов, т.е. он является частью опорной кривой УД+Х из А + +т отсчетов. Зададимся некоторой системой п базисных функционалов zjVt -x) J- п і определенных в скользящем окне. Отобразим отсчеты у, посредством данных базисных функционалов в расширенное пространство размерности п+\, где каждый отсчет у, представлен некоторым вектором z = (z,,...,z„, 1)У.
Пусть функционалы рДУ ,Ун j, / = 1,...,« выражают некоторые представления о различии формы кривой в области двух непересекающихся ее фрагментов Yjj и YJ. В общем случае у меры р7 не предполагается свойств метрики и даже свойств симметрии. Просканируем кривую в окне У/_У меньшим окном K/J , t-X + r\ s t + T-{i и подсчитаем значение функционала рДУД Y 4L) для каждого отсчета .v. Найдем положение внутренне го окна s , при котором значение данного функционала достигает максимума (рис. 5.2.1), и вычислим значение признака z} как величину Ill . r-i to) = Py (tf-т, tf+ц)- 0/ a)max a ] \ t-k ) r j у S" T\
Здесь a 0 - некоторая константа. Если функционал р7 адекватен природе возмущения, вызванного событием некоторого класса, то последовательность значений признака z ДУ/_") образует треугольный импульс, когда скользящее окно захватывает момент появления события. Вершина треугольного импульса указывает на точку резкого нарушения локальной однородности формы кривой, а его ширина составляет 2а. Величину а удобно выбрать, например, из условия a = min (А,-Г, т-u).
у rfvA .y -rj s і .y +p. t a-1/-.s , 1+x (у»л V +V Признаковые пространства такого типа были использованы для построения решающих правил распознавания вступлений сейсмических волн и меток времени на сейсмограммах вулканических землетрясений [18, 24, 109].
Рассмотрим детерминистскую задачу распознавания последовательности событий в предположении, что появление в некоторый момент времени события определенного класса вызывает характерное для него возмущение на зарегистрированной экспериментальной кривой. Последовательное распознавание локальных возмущений на кривой (т.е. в реальном времени) возможно лишь с некоторой задержкой принятия решения о моменте появления очередного события и его классе. Исследуем принципиальную возможность решения задачи последовательного распознавания при определенных предположениях о характере следования событий и вызываемых ими локальных возмущениях, построим экономный по памяти алгоритм распознавания как алгоритм поиска последовательности непересекающихся классифицированных интервалов времени ограниченной длины, содержащих искомые события, и дадим оценку максимальной задержки распознавания событий.
Восстановим моменты появления событий в виде непересекающихся интервалов длины не более 5 (содержащих не более 5+1 отсчета) и их классы, где 8 0 - заданная грубость распознавания. Пусть источник кривых порождает пары, каждая из которых образована допустимой в рамках такого источника бесконечной кривой и формирующей ее бесконечной последовательностью событий. Инструментом распознавания являются дискриминант-ные функционалы, позволяющие при грубости 8 отличать на экспериментальной кривой моменты появления событий от моментов, смещенных от ближайшего к ним события более, чем на 5 отсчетов. Пусть такие дискрими-нантные функционалы сформированы традиционным в распознавании образов методом обучения с учителем, который указал на достаточно длинной обучающей кривой интересующие его события и их классы. В частности, наиболее просто обучиться распознаванию событий при детерминистском подходе к обучению, предположив разделимость образов соответствующих моментов времени в некотором пространстве. Тогда при линейной разделимости дискриминантные функционалы имеют смысл разделяющих гиперплоскостей.
Но требование отличать события каждого класса от событий всех остальных классов является весьма жестким. В этом случае интервалы, содержащие момент появления события, определяются для каждого класса своим дискриминантным функционалом, позволяющим при грубости 5 отличать момент появления события данного класса от моментов, смещенных от него более, чем на 5 отсчетов. Именно в этом случае алгоритм распознавания принимает наиболее простой вид, когда последовательность классифицированных интервалов моментов появления событий определяется как объединение последовательностей интервалов моментов появления событий каждого класса в отдельности.
Менее жесткие требования предъявляются к дискриминантным функционалам, когда события некоторых или даже всех классов не различаются между собой при построении последовательности интервалов моментов появления событий. Но тогда алгоритм распознавания усложнится, так как потом необходимо определить классы некоторых или всех интервалов в уже построенной последовательности. Для этого необходимо сформировать, вообще говоря, другие дискриминантные функционалы, различающие интервалы событий разных классов. Можно предположить, что учет априорной информации о последовательностях событий, порождаемых источником кривых, позволит снизить требования к таким дискриминантным функционалам.
Задача последовательного распознавания событий актуальна во многих практических приложениях. При ее решении важно оценить величину задержки распознавания событий и объем памяти алгоритма для хранения промежуточных данных на время задержки. В то же время очевидна некоторая противоречивость совокупности требований, предъявляемых к величине грубости распознавания, дискриминантным функционалам и сложности алгоритма распознавания, хотя удачное сочетание этих характеристик определяет успешность распознавания в реальном времени.
