Единое окно доступа к образовательным ресурсам

Математические методы распознавания образов (ММРО-11): Сборник докладов 11-й Всероссийской конференции

Голосов: 2

Издание содержит доклады 11-й Всероссийской конференции "Математические методы распознавания образов" (ММРО-11), сгруппированные по двум разделам "Математическая теория распознавания" и "Прикладные задачи и системы распознавания". Конференция регулярно проводится один раз в два года, начиная с 1983 г., и является самым представительным российским научным форумом в области распознавания образов и анализа изображений, интеллектуального анализа данных, машинного обучения, обработки сигналов, математических методов прогнозирования. Оригинал публикации размещен на официальном сайте конференций "Математические методы распознавания образов" <a target=_blank href="http://www.mmro.ru">http://www.mmro.ru</a>.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    синдромом.
   Работа адаптивного алгоритма в новых условиях при пополнении ОВ
может быть представлена следующим образом. Пусть на вход алгоритма
поступил очередной объект пополнения ОВ. Он подаётся на вход
решающего правила. Если объект принадлежит синдрому своего класса, то
коррекция решающего правила будет состоять в увеличении на единицу
числа объектов m , имеющих данный синдром. Аналогичной коррекции
решающее правило подвергается и в случае пополнения выборки группой
объектов, описываемой синдромом. Число объектов синдрома решающего
правила увеличивается на число m объектов синдрома пополнения. Однако
при этом должно выполняться условие полного покрытия синдрома
пополнения синдромом решающего правила того же класса. При
выполнении тех же условий аналогичным образом можно произвести
исключение из ОВ отдельного объекта или группы объектов, описываемых
синдромом, с соответствующим уменьшением числа m объектов в синдроме
решающего правила. В случае если объект не принадлежит ни одному из
синдромов решающего правила своего класса или группа объектов,
описываемая синдромом, не покрывается полностью синдромом решающего
правила того же класса, требуется построение заново решающего правила.
Но такое решающее правило будет строиться на исключительно малой
выборке, состоящей из пространственных объектов, соответствующих
синдромам имеющегося решающего правила, и объектов пополнения или
исключения. Такое построение отличается малой трудоёмкостью и малым
временем выполнения процедуры.
   Аналогичный алгоритм можно построить и для распознавания образов
без учителя, или кластерного анализа объектов. Для этого вначале решается
задача кластеризации для представительной выборки объектов и на
полученных кластерах строится решающее правило их распознавания на
основе нечётких тестов и синдромов. Дальнейшая работа по кластеризации
объектов с пополнением и исключением объектов из выборки сводится к
рассмотренному выше адаптивному алгоритму распознавания. Отличие
будет состоять лишь в том, что объекты пополнения и исключения не будут
иметь признака класса и будут получать его по принадлежности синдромам
решающего правила или по наибольшему сходству с ними.
   Работа       выполнена       при     финансовой      поддержке      РФФИ,
проект 02-01-00274.
                                  Литература
1. Kotel’nikov I.V. A Syndrom Recognition Method Based on Optimal
     Irreducible Fuzzy Tests// Pattern Recognition and Image Analysis, Vol. 11,
     No. 3, 2001, pp. 553-559.
2. Котельников И.В. Алгоритмы построения тупиковых нечётких тестов//
     Динамика систем. / Межвузовский сборник научных трудов под ред.
                                                                           111


      Неймарка Ю.И., изд. ННГУ, Н.Новгород, 1995, С.71-86.


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

                          ∑ ϕ (y
                          i
                                   i
                                              )
                                       − Θx i → min         (1)

где x – вектор независимых переменных, y – результирующая переменная
(отклик), Θ – вектор параметров, ϕ – локально выпуклая функция.




           а                   б                        в         г
                                              Рис. 1.
    Существует два различных способа получения робастных оценок [1-4] и
робастных нейронных сетей. Во-первых, добавлением функций влияния
[5,6] или, во-вторых, суперпозицией нелинейных функций вида
                 где ϕ1 (u ) = u , а в качестве ϕ 2 может использоваться
ϕ (t ) = ϕ1(ϕ 2 (t )) ,                   2

одно из преобразований, графики которых приведены на рисунке 1 (а-г).
Использование в качестве ϕ 2 (t ) функции, график которой приведен на
112


рисунке 1а, дает робастную оценку Хьюбера.
   Рассмотрим параметрическое семейство оценок Мешалкина [7] с
оценочными функциями вида         ξ ( x ) = x exp(− λx 2 / 2 ) , где λ > 0 – параметр.
Использование в качестве       ϕ (t ) функции из этого семейства при λ = 1 дает
ОМУ. Свойство этой оценки изложены в книге А.М. Шурыгина [4].
   Использование робастного оценивания параметров при обучении
нейронных сетей прямого распространения представляется достаточно
логичным. На примере численного моделирования показано, какие
результаты дает использование ОМУ при обучении нейронных сетей
прямого распространения. Обучение нейронных сетей прямого
распространения, базируется на решении задачи

                      ∑ ϕ (y
                          i
                                    i
                                                 (    ))
                                        −ψ Θ, x i → min ,           (2)

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

            ∑ − exp{− [y                     (       )] / 2}→ min ,
                                                      2
                                i
                                    −ψ Θ, x i                             (3)
             i

   Все эти оценки, и соответствующие им нейронные сети, могут быть
реализованы с помощью Neural Network Constructor [8-10].
                  Пример численного моделирования
   Численное моделирование проводилось на искусственно созданной
выборке, содержащей 20 наблюдений, каждое из которых описывалось 8
                         i
дескрипторами. Каждое x j : i = 1,2,...,20; j = 1,2,...,8 представляло собой
произведение двух независимых случайных величин, имеющих нормальное
распределение N(0;3). Результирующая переменная была определена
следующим образом:
                                         8
                              y i = ∑ x ij + ε i ,            (4)
                                        j =1

   где ошибка ε также имела нормальное распределение N(0;3). В матрицу
                 i

исходных данных целенаправленно были введены две большие
погрешности. Это ε = 30 и ε = 15.
                     17                 18

   Было найдено 3 оценки параметров моделей: оценка макимального
правдоподобия (далее ОМП), робастная оценка, полученная с
                                                                                  113


использованием описанной в [6] функции влияния, и ОМУ. В
рассматриваемом случае оказалось, что робастная оценка не сильно
отличается от ОМП, поскольку 17 и 18 наблюдения не располагаются
«далеко» от вектора оценки центра выборки. Ниже на рисунке 2 (а,б)
приведены диаграммы рассеяния для робастной модели и модели
максимальной устойчивости. В таблице 1 приведены некоторые расчетные
характеристики построенных моделей.
     Таблица 1. Расчетные характеристики построенных моделей.
Оценка        R2        σ2        s2        R       eff Θ     stb Θ
ОМП                    0,97                           3,29                  8,79                             5,50                          1,00          0,00
Робастная              0,97                           3,29                  8,67                             5,37                          1,00          0,02
ОМУ                    0,92                           6,56                  6,65                             0,09                          0,50          1,00
                                                                                                                                      2
   В таблице используются следующие обозначения: R – квадрат парного
коэффициента корреляции между множеством наблюдаемых и расчетных
величин, σ – среднеквадратичная ошибка модели, s – среднеквадратичная
            2                                                                                                                2

ошибка при скользящем контроле, R – погрешность модели за счет оценки
параметров, eff Θ – эффективность оценки и stb Θ – устойчивость оценки.
Последние три показателя определены и исследованы в работах [2-4].
   Робастная модель оказалась не способной распознать в 8-мерном
пространстве 2 большие ошибки, введенные в исходные данные. Модель,
использующая оценку максимальной устойчивости, исправила ошибку ε ,
                                                                                                                                                            17

но оказалась не в состоянии выявить и исправить в два раза меньшую
ошибку ε . Снижение эффективности модели, использующей ОМУ,
            18

компенсируются заметным увеличением устойчивости.
                 50                                                              50
                                  Model                                                            Model
                 40                                                              40
                                  Control                                                          Control

                 30                                                              30

                 20                                                              20

                 10                                                              10


                 0                                                                0                ε18
                            ε18
                -10                                                              -10

                -20                                    ε17                       -20
                                                                                                                       ε17
                -30                                                              -30

                -40                                                              -40
                      -40   -30     -20     -10   0   10     20   30   40   50         -40   -30     -20     -10   0     10      20       30   40   50


                               а                        б
                 Рис. 2. Диаграммы рассеяния для построенных моделей.
   Несмотря на большую, чем у ОМП устойчивость робастных методов
оценивания (пример этой устойчивости описан в [6]) существуют и другие
методы оценивания параметров нейронных сетей (в частности нейронные
сети, использующие оценку максимальной устойчивости параметров),
114


которые еще более устойчивы к ошибкам в исходных данных. Как правило,
робастные нейронные сети, как и другие робастные методы оценивания
корректны, когда выполняется предположение о низкой размерности
пространства признаков. Свойства робастных нейронных сетей проявляются
в полной мере при p/n→0 при неограниченном росте n, где p – количество
дескрипторов, которыми описывается конечная выборка, а n – количество
наблюдений в этой выборке [1,5,6].
                                  Вывод
   При решении прикладных задач в различных предметных областях
наиболее логичным представляется использовать нейронные сети,
использующие оценку максимальной устойчивости параметров совместно с
другими устойчивыми методами оценивания. Это обуславливается
незначительным количеством наблюдений в экспериментальных данных, а
нейронные сети, использующие оценку максимальной устойчивости
параметров, проявляют свои свойства как раз на выборках небольшого
объема. Именно в этих условиях следует отдавать предпочтение нейронным
сетям, использующим оценку максимальной устойчивости параметров.
                               Литература
1. Хьюбер П. Робастность в статистике. – М.: Мир, 1984.
2. Шурыгин А.М. Размерности многомерной статистики. // Автоматика и
    Телемеханика, № 8, 1995.
3. Шурыгин А.М. Регрессия: выбор вида зависимости, эффективность и
    устойчивость оценок. // Автоматика и Телемеханика, № 6, 1996.
4. Шурыгин А.М. Прикладная стохастика: робастность, оценивание,
    прогноз. – М.: Финансы и статистика, 2000.
5. Хампель Ф., Рончетти Э., Рауссеу П., Штаэль В. Робастность в
    статистике. Подход на основе функций влияния. – М.: Мир, 1989.
6. Шакин В.В., Крепец В.В. Робастные нейронные сети и методы
    регуляризации. // Тезисы докладов IX Всероссийской конференции по
    Математическим Методам Распознавания Образов (ММРО-9) – М.: ВЦ
    РАН, 1999.
7. Мешалкин Л.Д. Использование весовой функции при оценке
    регрессионной зависимости. В сб. Многомерный статистический анализ
    в социально-экономических исследованиях. – М.: Наука, 1974.
8. Крепец В.В., Белкина Н.В., Скворцов В.С., Петричук С.В., Шакин В.В.,
    Иванов А.С. Программа NNC и ее возможности при построении
    нейросетевых моделей в биологии и медицине. // Тезисы докладов VII
    Всероссийской конференции "Нейрокомпьютеры и их применение", –
    Москва, 2001.
9. Белкина Н.В., Крепец В.В., Шакин В.В. Об устойчивом оценивании
    параметров нейронных сетей прямого распространения при работе с
    биологическими объектами. // Автоматика и Телемеханика, № 1, 2002.
                                                                   115


10. http://lmgdd.ibmh.msk.su/NNC


      Ассоциативная память на нелинейно-оптических
                       принципах
                 Б.В. Крыжановский, Л.Б. Литинский
                               (Москва)
                   Параметрическая нейронная сеть
   В [1] была предложена модель ассоциативной памяти, ориентированная
на обработку и хранение информации, закодированной в виде частотно-
фазовой модуляции. Одной из целей при этом было – уйти от искусственной
адаптации оптической нейросети к амплитудно модулированным сигналам и
максимально использовать преимущества, связанные с возможностью
передачи сигналов по оптическим межсвязям на q различных частотах
ϖ k , k = 1,..., q . За основу сети был принят параметрический нейрон –
обладающий кубической нелинейностью элемент, способный к
преобразованию и генерации квазимонохроматических импульсов в
процессах             параметрического    четырехволнового     смешения
ϖi − ϖ j + ϖk → ϖr .         Если отждествить параметрический нейрон с
элементарным пикселем экрана, а каждое из q его возможных состояний – с
цветом, в который окрашен данный пиксель, то набор одновременных
состояний всех N нейронов будет отвечать какому-то цветному
изображению на экране.
   Память сети локализована в межсвязях, где хранится информация о p
паттернах - p наперед заданных цветных изображениях. Межсвязи
устроены по обобщенному Хеббовскому правилу [2] и легко
модифицируются при добавлении новых паттернов.
    Сигналы, которыми обмениваются нейроны, преобразуются межсвязями
в процессах параметрического четырехволнового смешения. В результате,
сеть релаксирует из произвольного начального состояния в ближайшую
неподвижную точку.         Чтобы вся система работала как ассоциативная
память, необходимо, чтобы стартовав из начального состояния, являющегося
искажением одного из паттернов, сеть релаксировала именно к этому
паттерну. Естественно, хотелось бы, чтобы области притяжения паттернов,
определяющие допустимый в системе уровень искажений, были как можно
больше. Этого удалось добиться за счет выдвинутого в [1] принципа
несоизмеримости частот как непременного условия процессов
параметрического четырехволнового смешения: никакая комбинация
частот ϖ i − ϖ j + ϖ k не может принадлежать набору {ϖ r }1 , если все три
                                                          q


частоты различны. Именно принцип несоизмеримости частот гарантирует
116


высокую степень подавления в системе внутренних шумов и обеспечивает
паттернам большие области притяжения.
   Данная     модель   ассоциативной      памяти       получила       название
параметрической нейронной сети (ПНС). Ее дальнейшее иследование
пошло по пути создания более универсального языка описания. В частности,
удалось    разработать   матрично-векторный        формализм,        адекватно
передающий все заложенные в модель физические принципы. Это
позволило, с одной стороны, уяснить для себя связь ПНС с векторными
нейросетями типа Поттс-стекольной нейросети [2], а с другой – увидеть
ресурс модели и построить новые ее варианты, в том числе – с рекордными
на   сегодняшний     день   показателями     по      емкости       памяти    и
помехоустойчивости. Все математические подробности можно найти в [3].
                                ПНС-II
   В зависимости от способа реализации принципа несоизмеримости (а их
возможно несколько), возможны и различные варианты ПНС. Всюду в
дальнейшем будем считать, что принцип несоизмеримости реализован в
следующей форме: ωi - ωj + ωk ∈ {ωr}q только когда ωj совпадает с ωk .
Такой вариант принципа несоизмеримости положил начало новой серии
моделей - ПНС-II и ПНС-III, - с лучшими, чем в [1] характеристиками.
Сформулируем основные результаты для ПНС-II.
   Различные      состояния     параметрического             нейрона      суть
квазимонохроматические импульсы κ (t ) = exp(i (ϖt + ψ )) , где фаза ψ равна
либо 0, либо π , а частота ϖ принимает одно и q значений: ϖ ∈ { r }1 .
                                                              ϖ q
Состояние сети как целого задается набором одновременных состояний N
нейронов: Κ = (κ 1 (t ), κ 2 (t ), K , κ N (t )) , а p паттернов – это p каких-то,
наперед заданных образов:
              Κ µ = (κ µ1 (t ), κ µ 2 (t ),K , κ µ N (t )), µ = 1,.., p.
           Пусть на вход сети подается искаженный m -й паттерн
            ˆ         ˆ             ˆ                    ˆ
            Κ m = (a1b1κ m1 (t ), a2b2κ m 2 (t ),K , a N bN κ mN (t )),

            {}
                  N
             ˆ
где {ai }N и bi       - операторы мультипликативного шума: ai - независимые
случайные величины, принимающие значения -1 и +1 с вероятностями a и
                          ˆ
1 − a соответственно; bi - независимые случайные операторы, с
вероятностью b меняющие частоту ϖ mi            на какую-то иную, а с
вероятностью 1 − b оставляющие ее неизменной. Иначе говоря, a ∈ [0,1]
характеризует существующий в системе уровень искажений по фазе, а
b ∈ [0,1] - уровень искажений по частоте. Тогда, используя статистическую
                                                                       117


технику Чебышева-Чернова [3], вероятность неправильного распознавания
m -го паттерна при N >> 1 можно оценить как
                             ⎡ Nq 2                     ⎤
                 Prerr ∝ exp ⎢ −    (1 − 2a) 2 (1 − b)2 ⎥ .
                             ⎢ 2p
                             ⎣                          ⎥
                                                        ⎦
Иными словами, вероятность неправильного распознавания экспоненциально
затухает с ростом q , а помехозащищенность ПНС-II экспоненциально
улучшается.
    Емкость памяти α , традиционно измеряемая отношением предельно
допустимого           числа         паттернов    к   размеру    сети, равна
           (1 − 2a ) 2
                    2
α ПНС-II =            q (1 − b) 2 . Таким образом, с увеличением q растет и
               2
емкость памяти ПНС-II, в q2 превосходя аналогичный показатель для
модели Хопфилда, и в 2 раза – емкость памяти ПНС-I [1] и Поттс-
стекольной нейросети [2]. Число паттернов может теперь во много раз
превышать число нейронов N - результат, недостижимый для модели
Хопфилда.
    Мы моделировали работу ПНС-II на компьютере. При числе нейронов
N=100 и числе различных состояний q=32 сеть надежно распознавала
любой из 200 паттернов, искаженный не более чем на 90% (b = 0.9) . С
увеличением числа паттернов помехоустойчивость сети, естественно,
уменьшалась: при              p=2000 ( α =20) сеть распознавала паттерны с
искажениями до 65%, а при p=5000 ( α =50) – с искажениями до 50%.
Заметим, что и для таких, предельно высоких значений α ,
помехоустойчивость сети можно улучшить, увеличив q до принятого при
компьютерной обработке изображений значения q = 256.
    Разработанные модели использовались при создании компьютерно-
синтезированных голограмм в ближней зоне дифракции.
    Работа выполнена при поддержке гранта РФФИ 01-07-90134 и
программы «Интеллектуальные компьютерные системы» (проект 2.45).
                                        Литература
1. Крыжановский Б.В., Микаэлян А.Л.// Доклады АН, сер. мат.физика,
     2002, т.383, №3, с318-321.
2. Kanter I. Potts-glass neural network // Physical Review A, 1988, v.37,
     p.2739-2742.
3. Крыжановский Б.В., Литинский Л.Б. Векторные нейронные сети //
     Автоматика и Телемеханика, 2003, №10 (в печати).



118


Непереборный алгоритм отыскания глобального минимума
                 одного функционала
                 Б.В. Крыжановский, Л.Б. Литинский
                              (Москва)
                Постановка задачи и идея ее решения
   1° . В теории нейронных сетей, в физических рассмотрениях и при
решении различных оптимизационных задач [1], [2] нередко возникает
задача отыскания глобального минимума симметричной квадратичной
формы N бинарных переменных si :

    ⎧ r
    ⎪              r r          N            ⎫
                                             ⎪
min ⎨ E ( s ) = −(Js , s ) = − ∑ J ij si s j ⎬ , J ij = J ji , si = ±1.
 r                                                                                   (1)
 s ⎪                          i,j=1          ⎪
    ⎩                                        ⎭
                                 r
Векторы с бинарными координатами s = ( s1 , s 2 ,..., s N ) - мы будем называть
их конфигурационными, - описывают различные состояния системы из N
                                                                       r
бинарных «агентов» (спинов, нейронов и т.д.), а квадратичную форму E ( s )
с симметричной матрицей связей                J = ( J ij )iN j =1
                                                           ,        трактуют как энергию
состояния (ценовую функция, функцию затрат)             и стремятся
минимизировать.
   В моделях ассоциативных нейронных сетей Хопфилдова типа, состояние,
                                    r
отвечающее локальному минимуму E ( s ) , является неподвижной точкой
динамической системы
                                     ⎛ N               ⎞
                    si (t + 1) = sgn ⎜ ∑ J ij s j (t ) ⎟ ,                         (2)
                                     ⎜ j =1            ⎟
                                     ⎝                 ⎠
в которую система релаксирует за несколько тактов своей эволюции.
Глобальный минимум отвечает неподвижной точке с наибольшей областью
притяжения. Энергетическая поверхность, как правило, многоэкстремальна,
                                                                      N
а отыскивать глобальный минимум перебором всех 2 конфигурационных
          r
векторов s уже при N > 40 практически невозможно.
    Распространенным методом решения подобных задач является
моделирование отжига, использующее известный алгоритм Метрополиса
[3]. Соответствующая вычислительная процедура весьма затратна по
времени и не гарантирует отыскания глобального минимума. Наш подход
позволяет надеяться на создание алгоритма с вычислительной сложностью
               3
порядка O ( N ) .

                                                                                     119


     2° . Главная идея нашего подхода состоит в том, чтобы искать вектор
r
s * , доставляющий функционалу глобальный минимум,                 среди
конфигурационных векторов, ближайших к наибольшим собственным
векторам матрицы J – к тем собственным векторам, которые отвечают
наибольшим собственным значениями матрицы.
    В самом деле, симметричная матрица J обладает полным набором
                         r (i )
собственных векторов f , которые мы будем нумеровать в порядке
убывания собственных значений λ i :
          r           r                          r r
      J ⋅ f (i ) = λi f (i ) , λ1 ≥ λ2 K ≥ λN , (f (i ) , f ( j ) ) = δ ij , i, j = 1,K N ;
здесь δ ij - символ Кронекера. Тогда можно записать:

     r
               (  r r                 r r                     r r
 E ( s ) = − λ1 ( s , f (1) )2 + λ2 ( s , f (2) )2 + K + λN ( s , f ( N ) )2 . )             (3)

Нетрудно показать, что когда наибольшее собственное значение λ 1
существенно превосходит все остальные      собственные значения -
λ1 >> λi , i = 2,K N , − решением задачи    (1) будет в точности
                                             r (1)
конфигурационный вектор, ближайший к f . Координаты этого
конфигурационного вектора найти очень просто – они задаются знаками
                         r (1)
координат самого вектора f :


                   ( )
                                                       N
                               r r                                       r r           r
      si * = sgn fi(1) ∀ i ⇒ ( s*, f ( 1 ) ) =        ∑ | fi(1) | ≥ | (s , f ( 1 ) ) | ∀s.
                                         i =1
Следовательно, в этом случае решение задачи (1) проблем не вызывает.
   Сложности начинаются, когда у матрицы J несколько наибольших
собственных значений сравнимы по величине. В этом случае приходится
анализировать целое множество конфигурационных векторов, ближайших к
нескольким наибольшим собственным векторам. Однако, вычислительная
                                                              3
сложность этой процедуры оценивается как O ( N ) , что вполне приемлемо
с точки зрения временных затрат.
               Результаты компьютерного моделирования
    Мы сгенерировали случайным образом 1500 симметричных матриц J -
по 500 матриц размерностями (15x15), (16x16) и (17x17) соответственно.
Внедиагональные элементы независимым и случайным образом выбирались
из интервала [-4,+4], а диагональные элементы клались равными 0. Для
каждой матрицы, с одной стороны, полным перебором отыскивались все
120



    
Яндекс цитирования Яндекс.Метрика