МАТЕМАТИЧЕСКИЕ МЕТОДЫ _распознавания образов

f (x, y) < f (x, y ) являетcя следствием соотношения: x A( y ). Работа поддержана РФФИ ( проект 97-01-00370 ) и ГНТП/ПИТ.

Литература

1.Журавлёв Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов, I - II - III - Кибернетика - 1977 - №4, 1977 -№6б 1978 - №2.

2.Ерёмин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования - М. - «Наука» - 1979.

3.Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. - М. - «Наука» - 1990.

4.Vl.D.Mazurov. Duality in pattern recognition - PRIA - 1991 - vol.1 - №2.

Хранение и воспроизведение последовательности бинарных векторов сетями из w - нейронов

В.В. Майоров, Г.В. Шабаршина

(Ярославль)

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

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

Приведем описание W-нейрона. В любой дискретный момент времени t W - нейрон находится в одном из трех состояний: s(t) = 0 - состояние покоя,

s(t) =1 - состояние возбуждения, s(t) = −1 - состояние рефрактерности. Из

состояния покоя W - нейрон может перейти в возбужденное состояние под действием синаптических сигналов. Возбуждение длится один такт. Оно

сменяется состоянием рефрактерности - длится r0 тактов, за которым

наступает состояние ожидания (покоя). В каждый момент времени W - нейрон формирует выходной сигнал x(t) = δ0 (s(t) −1) , где δ0 (v) =1 при

v = 0 и δ0 (v) = 0 при v ≠ 0 . W - нейрон имеет суммирующие синаптические входы. Для W - нейрона в состоянии ожидания определим мембранный

возбужденное состояние и формирует выходной сигнал x(t +1) =1.

Ниже рассматриваются сети, состоящие из p нейронных ассоциаций

(модулей), каждая из них содержит N элементов. Связи между W - нейронами внутри модулей и между элементами разных модулей осуществляются с помощью суммирующих синапсов.

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

Произвольно пронумеруем модули и W - нейроны внутри модулей. Пусть Uk (t) и X k (t) - соответственно векторы мембранных потенциалов и

выходных сигналов k-ого модуля в момент времени t. Обозначим через Wk, j матрицу, в текущей i - ой (i =1,..., N ) строке которой расположен вектор, состоящий из синаптических весов воздействия W - нейронов j - ого

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

Теорема. Пусть продолжительность рефрактерного состояния W - нейронов r0 = p − 2 . Существует периодический режим функционирования сети, в котором в последовательные моменты времени генерируются

Для доказательства теоремы опишем механизм инициализации колебательных режимов. Снабдим каждый W - нейрон внешним входом. Если в момент времени t нейрон находится в состоянии ожидания s(t = 0) ,

то внешний сигнал xвн(t) = −1 (абсолютно тормозящий) переводит его в следующий момент времени в состояние рефрактерности, которое продлится r0 тактов. В свою очередь, сигнал xвн(t) = 1 (возбуждающий) переводит W -

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

Пусть в нулевой момент времени все W - нейроны находятся в состоянии ожидания. Используя внешние входы, последовательно в моменты времени t = k (k=1,…,p) подадим на нейроны k -ого модуля абсолютно тормозящие сигналы. В момент времени t = p нейроны первого модуля уже выйдут из

рефрактерного состояния. В этот момент времени подадим на нейроны первого модуля в качестве внешнего воздействия вектор X1 . В момент времени t = p +1 W - нейроны второго модуля находятся в состоянии ожидания, а модулей с номерами 3,…,p - в рефрактерном состоянии. Также

состояние X 2 . Согласно (2) в момент времени t = p + 3 выходным вектором

~

для второго модуля будет вектор X 2 , для третьего - X 3 . В дальнейшем сеть

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

~

сигналов ( X k −1 и X k соответственно), W - нейроны k+1-модуля находятся в

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

Таким образом, сеть, состоящая из W - нейронов играет роль ассоциативной памяти: по фрагменту восстанавливает ассоциативный ряд.

О выборе размерностей евклидовых представлений метрических описаний прецедентов

А.И. Майсурадзе

(Москва)

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

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

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

непрерывно дифференцируемых функционалов уклонения, которые (1)

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

метрической конфигурации ρ~* точками n-мерного евклидова пространства при использовании функционала уклонения χ . Очевидно, что с ростом n величина ошибки разве что убывает. Для функционалов из χ~ верен

следующий результат. Если метрическая конфигурация для m объектов точно представима в некотором конечномерном евклидовом пространстве, то последовательность P(n), n=0,1,2…, достигает минимального (а именно, нулевого) значения при размерности представления не более m-1, иначе P(n) достигает минимального (причем положительного) значения при размерности не более m-2.

Для анализа качества представления прецедентов можно использовать величину e(k)=[P(k-1)-P(k)]/[P(k)-P(k+1)], называемую эффективностью размерности k. Эффективными размерностями называются размерности, для которых на графике эффективности имеется локальные максимумы, т.е. e(k)>e(k-1) и e(k)>e(k+1). То, какие размерности являются эффективными, является характеристикой метрических свойств заданного набора объектов. При выборе размерности описаний исходных объектов можно обоснованно использовать именно эффективные размерности.

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

Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (код проекта 99-01-00562).

О проблеме обоснования качества классов алгоритмов с универсальными ограничениями монотонности

В.Л. Матросов, А.Н. Сёмочкин

(Москва)

В работе К.В. Рудакова [1] была сформулирована общая постановка задачи построения алгоритмов преобразования информации с так

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

Пусть определены частично упорядоченные множества X и Ω = {0,1} , существует известное на конечном подмножестве множества X отображение

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

множестве Х. Случай, когда все элементы множества Х попарно несравнимы относительно заданного на нем частичного порядка был подробно изучен в работе [2]. С другой стороны, справедлива теорема о том, что достаточным условием решения задачи распознавания с надежностью η < 1 получения

заданного качества ε <1 является существование на множестве объектов Х линейного порядка.

В общем случае задания частичного порядка на множестве Х определена вероятностная характеристика этого порядка, фиксирующая вероятность

того, что выборка S q не является линейно упорядоченной, и выражающаяся некоторой функцией g(q) . Функцию ρq =1− g(q) назовем характеристикой

плотности порядка на множестве Х. Для оценки скорости сходимости функционала качества в данном случае вводится понятие линейного достроения частичного порядка на конечном множестве. Число линейных достроений на q-конечном множестве обозначим h(ρq , q) . Справедливо

для любого q, верно неравенство

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

Литература

1.Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации //Распознавание, классификация,

прогноз. М.:Наука,1989. с. 176-201.

2.Вапник В.Н., Червоненкис А.Я. Теория распознавания образов(статистические проблемы обучения). М.: Наука, 1974.418с.

Задание порядка в области определения признаков как метод структурированного описания сложных объектов

Н.А. Меркулова

(Новосибирск)

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

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

Пусть область определения каждого признака разбита на подобласти. Для некоторого объекта a зададим структуру отношений на множестве значений признаков объекта. Считаем, что на i -м этапе задано разбиение

определяются на основе экспертных высказываний вида: если значения

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

X (ji+1)k . Множество связей между элементами дерева может быть задано

структуру множества признаков; T - матрица размера l × l с элементами, определенными следующим образом: tij =1 (i, j) ατ , tij = 0

(i, j) ατ .

Пусть заданы структурированные описания двух различных объектов a и a′ . Расстояние между структурами ατ , ατ′ можно определить по

матрицам T и T ′ , как число поразрядных несовпадений элементов матриц:

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

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

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

Работа выполнена при финансовой поддержке РФФИ, проект 98-01- 00673.

Литература

1.Куперштох, В.Л., Трофимов, В.А. Алгоритм анализа структуры матрицы связи// Автоматика и телемеханика, 1975, № 11, с. 170-180.

2.Лбов, Г.С. Логические решающие функции. – Новосибирск, Изд-во НГТУ,1998,с.70

3. Kaufman, K.A., Michalski, R.S. A Method for Reasoning with Structured and Continuous Attributes in the INLEN-2 Multistrategy Knowledge Discovery System// Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, Portland, 1996. pp. 232-237.

Древовидные марковские случайные поля в задачах анализа массивов упорядоченных данных

В.В. Моттль, С.Д. Двоенко А.Б. Блинов

(Тула)

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

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

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

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

Рассмотрим массив данных как функцию yt на множестве элементов

массива t Τ , принимающую значения из некоторого множества, определенного природой источника данных. На множестве T задано антирефлексивное симметричное бинарное отношение G T×T,