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

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

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Штучний інтелект
Дата:	2011
Автори:	Крыжановский, М.В., Мальсагов, М.Ю.
Формат:	Стаття
Мова:	Російська
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2011
Теми:	Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/60237
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Особенности применения дискретизации в задачах поиска глобального минимума / М.В. Крыжановский, М.Ю. Мальсагов // Штучний інтелект. — 2011. — № 3. — С. 497-505. — Бібліогр.: 5 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860057709148110848
author	Крыжановский, М.В. Мальсагов, М.Ю.
author_facet	Крыжановский, М.В. Мальсагов, М.Ю.
citation_txt	Особенности применения дискретизации в задачах поиска глобального минимума / М.В. Крыжановский, М.Ю. Мальсагов // Штучний інтелект. — 2011. — № 3. — С. 497-505. — Бібліогр.: 5 назв. — рос.
collection	DSpace DC
container_title	Штучний інтелект
description	В работе рассматривается задача нейросетевой минимизации квадратичного функционала в пространстве бинарных переменных. Для решения задачи предложен и исследован модифицированный алгоритм минимизации, основанный на применении метода дискретизации. Показано, что его применение дает уменьшение объема вычислений. The problem of neural network minimization of quadratic functional in binary space is considered in this paper. To solve problem, modified minimization algorithm is proposed and researched. This algorithm is based on discretization procedure. It is shown that its applying decrease amount of calculation.
first_indexed	2025-12-07T17:02:12Z
format	Article
fulltext	«Штучний інтелект» 3’2011 497 8К УДК 004.8:004.9 М.В. Крыжановский, М.Ю. Мальсагов НИИ системных исследований РАН, г. Москва, Россия iont.niisi@gmail.com, Magomed.Malsagov@gmail.com Особенности применения дискретизации в задачах поиска глобального минимума1 В работе рассматривается задача нейросетевой минимизации квадратичного функционала в пространстве бинарных переменных. Для решения задачи предложен и исследован модифицированный алгоритм минимизации, основанный на применении метода дискретизации. Показано, что его применение дает уменьшение объема вычислений. Введение В настоящей работе рассматривается задача минимизации квадратичного функцио- нала    sBAss ,2, E , (1) в котором компоненты вектора s принимают значения ±1. Матрица A – симметричная, с нулевой диагональю, а ее элементы – случайные независимые величины. Количество минимумов функционала  sE велико и экспоненциально растет с ростом размерности задачи. Так уже при размерности вектора s равной 200 число минимумов ~100000 и поэтому нахождение достаточно глубокого минимума сложная задача. Алгоритм минимизации. За основу процедуры минимизации взята нейросетевая модель Хопфилда [1]. Это полносвязная рекуррентная нейронная сеть из N нейронов, имеющих два состояния ,1is Ni ,1 . Энергия сети задана выражением (1). Такую сеть можно рассматривать как систему, решающую задачу бинарной минимизации: кон- вергируя в устойчивое состояние, сеть находит конфигурацию, соответствующую миниму- му энергии E . Показано [2], [3], что при случайном поиске вероятность отыскания какого- либо минимума экспоненциально возрастает с ростом глубины этого минимума. Это оз- начает, что нейросеть с подавляющей вероятностью находит если не оптимальное решение (глобальный минимум), то одно из субоптимальных решений (локальный минимум). Мы будем рассматривать только асинхронную динамику сети Хопфилда, однознач- но приводящую к минимизации функционала энергии E : на каждом такте работы сети вычисляется одна из компонент (например, i -я) локального поля H sABH  , (2) и компоненте is присваивается значение .ii Hsigns  (3) Эта процедура последовательно применяется ко всем компонентам s до тех пор, пока сеть не конвергирует в устойчивое состояние, соответствующее минимуму энергии. 1 Работа поддержана проектом 2.15 Президиума РАН и грантом РФФИ 09-07-00159. Крыжановский М.В., Мальсагов М.Ю. «Искусственный интеллект» 3’2011 498 8К Для уменьшения объема вычислений в работе [4] предложен метод дискретизации матрицы A , т.е. выделение из матричных элементов среднего значения 0A и замены остатка матрицей C , нормированные элементы которой имеют целочисленные значения в диапазоне  mm  ; , где m – число градаций. При таком подходе поиск минимума  sE заменяется поиском минимума дискретизованного функционала    sbCss ,2,  , (4) если 00 A . Оптимизация функционала (4) проводится аналогично оптимизации функционала (1). На каждом такте работы вычисляется одна из компонент локального поля h sCbh  (2а) и компоненте присваивается значение ii hsigns  . (3а) Качество такой аппроксимации будет зависеть от выбранного числа градаций и определяется функцией распределения. С увеличением числа градаций максимум функции распределения смещается влево (рис. 1), в сторону более глубоких минимумов, что увеличивает вероятность их нахождения. Так, для «энергии» 05,0E имеем: при переходе от 1m к 8m плотность состояний увеличится в 1,5 раз. На рис. 1 пред- ставлены функции распределения плотности вероятности по «энергии» функционала (1) построенных на минимумах  s для разного числа градаций. По оси X отложена «энер- гия», которая определяется величиной   00 EEEE  , где 0E – энергия глобального минимума. 0 1 2 3 4 5 6 7 8 0 0,05 0,1 0,15 0,2 0,25 0,3 "Energy", S ta te d is tr ib u ti o n b y e n e rg y m = 8 m = 4 m = 2 m = 1 E Рисунок 1 – Распределение плотности вероятности состояний по энергии для разного числа градаций Минимум функционала. В данной работе применяется двухэтапный алгоритм [5]. Процесс минимизации функционала (1) начинается с некоторой случайной точки простран- ства s . Подчиняясь решающему правилу (3а), сеть конвергирует в некоторое устойчивое состояние  os , являющееся минимумом функционала  . Если из этой точки продолжить спуск с решающим правилом (3), то сеть конвергирует в состояние os , соответствующее Особенности применения дискретизации в задачах поиска глобального минимума «Штучний інтелект» 3’2011 499 8К минимуму функционала (1). На всем пути oo sss   величина ошибки (вероятность ошибки P в направлениях градиентов) только уменьшается. С ростом числа градаций m величина ошибки убывает как  12 1   m P  . (4) Эффективность минимизации определяется величиной   00 * 0 / EEEE  , где )(* 0  osEE – энергия минимума  os дискретизированного функционала, а )(0 osEE  – энергия ближайшего к нему минимума os , в который мы бы спустились при использо- вании исходного решающего правила (3). Показано [4], что эффективность минимизации PE  , (5) из которого следует, что разница в энергиях с ростом m убывает как 1~ mE . При этом Хеммингово расстояние между минимумами функционала E и его аналога  определяются простым соотношением NPd  . (6) Хеммингово расстояние не превышает значения Nd 11,0 , когда 1m , и снижается до значения Nd 02,0 при 16m . Сказанное подкрепляется результатами эксперимента (рис. 2). На рис. 2 кривые 1, 2, 4 – функции распределения состояний: начального s , дискретизированного  os и конеч- ного os . Кривая 3 – распределение состояний исходного функционала. На рис. 2 они же отмечают точки максимумов функций плотности. Расстояние между этими максимумами на графике соответствует в точности формуле (5). Видно, что величина первого участка пути  oss значительно больше второго участка oo ss  . Преимущество двухэтапного алгоритма в том, что первая часть пути  oss проходится с большей скоростью. Вследствие чего достигается общее увеличение скорости работы алгоритма. Так же функция распределения минимумов 2-этапного алгоритма лежит левее распределения исходного алгоритма. Таким образом, вероятность нахождения глубоких минимумов двухэтапным алгоритмом выше, чем простым методом. 0 5 10 15 20 25 -1,15 -1,05 -0,95 -0,85 -0,75 -0,65 -0,55 f EE N = 800 -0,15 0 ... 2 3 1 4 os  os s Рисунок 2 – Функции распределения состояний: начального s (кривая 1), дискретизированного  os (кривая 2) и конечного os (кривая 4). Кривая 3 – распределение состояний исходного функционала Крыжановский М.В., Мальсагов М.Ю. «Искусственный интеллект» 3’2011 500 8К Работа с укороченной арифметикой Полученные результаты дают основу для применения метода дискретизации, что означает возможность применения чисел малой разрядности. При этом для хранения матричного элемента при выборе параметра 1m достаточно 2 битов, а для 15m достаточно половины байта. В дальнейшем, размер чисел матрицы A мы будем называть исходным форматом, а p – количество чисел малой разрядности, которое упаковывается в исходный 4-байтный формат. Основной объем вычислений по алгоритму Хопфилда приходится на вычисление градиента, т.е. на вычисления скалярных произведений 2 векторов. Поэтому возможность такого представления элементов A позволяет увеличить быстродействие алгоритма. Например, сложение пары вещественных чисел в 4-байтном формате требует 1 такт процессорного времени. За то же время можно сложить 4 пары целых чисел в байтном формате. Ускорение алгоритма определяется величиной I I 0 , где 0I – время работы алгоритма, I – время работы алгоритма, когда элементы матрицы упакованы. На рис. 3 приведен пример увеличения скорости работы алгоритма ( 1m , пара- метр упаковки 8p ). По оси ординат отложено ускорение  , а по оси абсцисс – размер- ность нейросети N . С увеличением размерности нейросети его ускорение увеличивается и достигает своего предельного значения 3,7 . 0 1 2 3 4 5 6 7 8 0 2000 4000 6000 8000 10000 12000 14000  N Рисунок 3 – Ускорение алгоритма при использовании упаковки чисел малой разрядности На скорость работы сети так же влияет исходный формат чисел. Например, если элементы исходной матрицы A вещественные (4 байта), то время работы возрастет до 1.4, а для вещественных 10 байтных чисел возрастет до 6,3. Алгоритм расчета нейронной сети Хопфилда основан на последовательном вычислении компонент градиента H при каждом изменении состояния нейрона. Особенности применения дискретизации в задачах поиска глобального минимума «Штучний інтелект» 3’2011 501 8К 0 5 10 15 20 25 30 35 40 0 10 20 30 40 50 %,n T Рисунок 4 – Количество переворотов спинов на каждой итерации. Размерность нейросети 4000N На рис. 4 показано, как изменяется число изменений состояний нейронов от номера итерации (одна итерация соответствует проверке всех N нейронов). На вертикальной оси отложена доля измененных нейронов n в процентах. Как видно из рис. 4, с увеличением числа шагов число нейронов, которые изменяют свое направление, становится малым. Это означает, что направления компонент H также редко изменяется. Поэтому вычисле- ние на каждом шаге компоненты вектора H не эффективно. Вычислительная сложность алгоритма 22~ TN , где T – число итераций. С увеличением размерности сети число итераций T растет (рис. 5b). Например, при размерности 100N число шагов 5T , а при 10000N число шагов 80T . В настоящее время используется другой метод расчета. В исходном состоянии s вычисляются все компоненты H . На каждом шаге процедуры при изменении состояния нейрона вектор H модифицируется по правилу  iAHH 2 , если направление спина положительно/отрицательно.  iA – вектор строки с номером текущего нейрона. Объем вычислений компонент H в исходном состоянии равен 2N . При перевороте каждого спина производится N операций. Число переворотов спинов не превышает N (рис. 5а), поэтому вычислительная сложность такого алгоритма   21~ N , а 1 . Отношение объемов вычислений такого метода к исходному методу  1,~ TT . В дальнейшем, в качестве исходного алгоритма мы используем метод с обновлением компонент H . 0 10 20 30 40 50 60 70 80 90 100 0 2000 4000 6000 8000 10000 12000 (a) %,n N 0 10 20 30 40 50 60 70 80 90 100 0 2000 4000 6000 8000 10000 12000 (b) N T Рисунок 5 – (а) – Полное число изменений нейронов при увеличении размерности нейронной сети N ; (b) – Изменение числа итераций в зависимости от размерности сети N Крыжановский М.В., Мальсагов М.Ю. «Искусственный интеллект» 3’2011 502 8К Модификация алгоритма обновления при использовании чисел малой разрядности достигается их упаковкой в исходный формат. В результате этого достигается параллель- ное выполнение операций сложения и умножения, что приводит к увеличению скорости работы. На рис. 6 показано ускорение алгоритма при упаковке  1,8  mp для нейрон- ных сетей различной размерности. Установлено, что достигаемое ускорение 5 . При упаковке 4p в исходный формат ускорение составляет 8,3  15m , а при 16p  1m – 8 . 0 1 2 3 4 5 6 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000N  Рисунок 6 – Ускорение, получаемое при упаковке чисел  8p по сравнению с обычным методом Алгоритм случайного поиска Проведем анализ быстродействия двухэтапного алгоритма при использовании упакованных данных  8,1  pm на первом этапе. В этом случае 21 0 OO O I I H   . На I этапе число итераций при минимизации  s равно числу итераций исход- ным методом [5]. Поэтому объем вычислений на первом этапе – 51 HOO  . На II этапе число итераций T мало [5], соответственно мало число изменений в состояниях нейро- нов. Поэтому основной объем вычислений приходится на вычисление градиента  osH в промежуточных состояниях и составляет 22 HOO  . В этом случае ускорение алго- ритма составит 4,1 . Лимитирующим фактором, препятствующим увеличению быстродействия 2-этап- ного алгоритма, является объем вычислений градиентов H промежуточных состояний  os . Для его уменьшения на II этапе предлагается использование наиболее глубоких со- стояний  os . Например, если мы продолжим спуск только с половины всех точек, то ускорение составит 2,2 5,0 21    OO O H  . Конечно, при таком подходе есть шанс получить несколько худшее решение. Вероятность этого можно оценить, используя экспериментальные результаты (рис. 7). Особенности применения дискретизации в задачах поиска глобального минимума «Штучний інтелект» 3’2011 503 8К Для этого распределение минимумов  os разбивалось на левую и правую области от- носительно пика распределения, и определялась вероятность найти самый глубокий минимум при стартах из каждой области. На рис. 7 видно, что самый глубокий мини- мум с вероятностью 96% находится из состояний левой области, в то время как правая область дает вероятность близкую к нулю. Поэтому состояния правой области могут не участвовать на II этапе поиска. 0 20 40 60 80 100 120 0 1000 2000 3000 4000 5000 6000 7000 P ro b ab yl it y o f fi n d in g o f d ee p es t m in im u m , % Left region Right region N Рисунок 7 – Вероятность попадания в самый глубокий минимум из левой и правой областей распределения  os Качество алгоритма зависит от размера области состояний  os , которые исполь- зуются на II этапе, и определяется эффективным расстоянием   * 0 * 0 / EEEE  , где  0E – самый глубокий минимум, найденный со всех состояний  os , E – самый глубокий минимум, найденным при стартах из некоторой части состояний  os . Начало области со- ответствует наиболее глубокому минимуму дискретизированной сети. Конечная точка (граница области) – свободный параметр. С ростом величины стартовой области эффективное расстояние монотонно убывает (рис. 8), а качество минимизации улучшается, и после некоторого значения обращается в ноль, т.е. в этой области находится самый глубокий минимум. С помощью E можно оценить Хемминогово расстояние D между глобальным минимумом  0E и самым глубоким минимумом E , найденным при стартах из отрезка. Действительно, при изменении состояния одного нейрона, энергия меняется в среднем на величину e . Поскольку большая часть минимумов находится в области EcE 3 и отношение 1cE E , то cEE ~0  . eNEc ~ . Тогда N D E ~ . Таким образом, достаточно подобрать область состояний  os , для которой вы- полняется условие 1~NED   . (7) Для размерности сети 100N это условие будет выполняться в случае, когда гра- ница области отстоит от максимума функции распределения на расстоянии 8,1 . С уве- личением размерности сети при фиксированном эффективном расстоянии размер области уменьшается (рис. 9), ее граница смещается в сторону более глубоких дискретизи- рованных минимумов, что уменьшает объем вычислений. Крыжановский М.В., Мальсагов М.Ю. «Искусственный интеллект» 3’2011 504 8К 0 0,005 0,01 0,015 0,02 0,025 0,03 0,035 0,04 0,045 0,05 -3,5 -3 -2,5 -2 -1,5 -1 -0,5 0 E N = 100 N = 200 Рисунок 8 – Зависимость эффективного расстояния от размера стартовой области. Размер стартовой области задается в единицах  функции распределения энергии   os 0 0,005 0,01 0,015 0,02 0,025 0,03 0,035 0 200 400 600 800 1000 1200N E 0.2 5.2 0.3 Рисунок 9 – Эффективное расстояние в зависимости от размерности сети для трех значений размера стартовой области Действительно, распределение промежуточных состояний подчиняется нормаль- ному закону. Количество минимумов  os , находящихся на расстоянии более 0,2 от максимума функции распределения к общему их числу составляет меньше 0,05. В этом случае увеличение скорости работы алгоритма составит 5,4 05,0 21    OO O H  . Данная величина ускорения верна для размерностей нейронной сети более 200. Сравнение работы 2-этапного алгоритма с обычным (рис. 10) показывает, что моди- фикация алгоритма увеличивает вероятность нахождение глубоких минимумов. Так, на рис. 10 представлены две кривые (экспериментальные результаты). Верхняя кривая соответствует вероятности нахождения 2-этапным алгоритмом лучшего или равного минимума, чем алгоритмом Хопфилда. Нижняя кривая – вероятность того, что найден- ный минимум хуже, чем при простом алгоритме. Видно, что с увеличением размерности сети вероятность найти более глубокий минимум модифицированным алгоритмом всегда больше 0,5 по сравнению с исходным алгоритмом. Особенности применения дискретизации в задачах поиска глобального минимума «Штучний інтелект» 3’2011 505 8К 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 1,1 0 200 400 600 800 1000 1200 1400 1600 1800 1 2 P N Рисунок 10 – Вероятность найти более (кривая 1) глубокий минимум или менее (кривая 2) глубокий с помощью 2-этапного алгоритма Выводы Предложена процедура дискретизации, позволяющая использовать числа малой разрядности для увеличения быстродействия процедуры минимизации квадратичного функционала. Для этого был разработан 2-этапный алгоритм на основе нейросетевой модели Хопфилда. Ускорение работы алгоритма для сетей размерностью более 200 превышает 4,5. Качество 2-этапного алгоритма по нахождению глубоких минимумов выше, чем у исходного метода. Литература 1. Hopfield J.J. Neural networks and physical systems with emergent collective computational abilities / J.J. Hopfield // Proc. Nat. Acad. Sci. USA. –1982. – Vol. 79. – P. 2554-2558. 2. Крыжановский Б.В. Взаимосвязь глубины локального минимума и вероятности его нахождения в обобщенной модели Хопфилда / Б.В. Крыжановский, Б.М. Магомедов, А.Л. Микаэлян // ДАН. – 2005. – Т. 405, № 3. – С. 320-324. 3. Kryzhanovsky B.V. The shape of a local minimum and the probability of its detection in random search / B.V. Kryzhanovsky // Lecture Notes in Electrical Engineering. – 2009. – Vol. 24. – P. 51-61. 4. Крыжановский Б.В. Дискретизация матрицы в задаче бинарной минимизации квадратичного функционала / Б.В. Крыжановский, В.М. Крыжановский, М.Ю. Мальсагов // ДАН. – 2011. – Т. 438, № 3. – С. 312-317. 5. Kryzhanovsky M.V. Clipping procedure in optimization problems and its generalization / M.V. Kryzhanovsky, M.Yu. Malsagov // Optical Memory & Neural Networks. – 2009. – Vol. 18, № 3. – P. 181-187. Literatura 1. Hopfield J.J. Proc. Nat. Acad. Sci. USA. 1982. V. 79. P 2554-2558. 2. Kryzhanovskij B.V. DAN. T. 405. № 3. 2005. S. 320-324. 3. Kryzhanovsky B.V. Lecture Notes in Electrical Engineering. V. 24. 2009. P. 51-61. 4. Kryzhanovskij B.V., DAN. T. 438. № 3. 2011. S. 312-317. 5. Kryzhanovsky M.V. Optical Memory & Neural Networks. V. 18. № 3. 2009. P. 181-187. M.V. Kryzhanovsky, M.Yu. Malsagov Application Features of Discretization in the Problem of Global Minimum Search The problem of neural network minimization of quadratic functional in binary space is considered in this paper. To solve problem, modified minimization algorithm is proposed and researched. This algorithm is based on discretization procedure. It is shown that its applying decrease amount of calculation. Статья поступила в редакцию 22.06.2011.
id	nasplib_isofts_kiev_ua-123456789-60237
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1561-5359
language	Russian
last_indexed	2025-12-07T17:02:12Z
publishDate	2011
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
record_format	dspace
spelling	Крыжановский, М.В. Мальсагов, М.Ю. 2014-04-12T15:08:18Z 2014-04-12T15:08:18Z 2011 Особенности применения дискретизации в задачах поиска глобального минимума / М.В. Крыжановский, М.Ю. Мальсагов // Штучний інтелект. — 2011. — № 3. — С. 497-505. — Бібліогр.: 5 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/60237 004.8:004.9 В работе рассматривается задача нейросетевой минимизации квадратичного функционала в пространстве бинарных переменных. Для решения задачи предложен и исследован модифицированный алгоритм минимизации, основанный на применении метода дискретизации. Показано, что его применение дает уменьшение объема вычислений. The problem of neural network minimization of quadratic functional in binary space is considered in this paper. To solve problem, modified minimization algorithm is proposed and researched. This algorithm is based on discretization procedure. It is shown that its applying decrease amount of calculation. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Нейронные сети и нейросетевые технологии. Информационная безопасность ИС Особенности применения дискретизации в задачах поиска глобального минимума Application Features of Discretization in the Problem of Global Minimum Search Article published earlier
spellingShingle	Особенности применения дискретизации в задачах поиска глобального минимума Крыжановский, М.В. Мальсагов, М.Ю. Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
title	Особенности применения дискретизации в задачах поиска глобального минимума
title_alt	Application Features of Discretization in the Problem of Global Minimum Search
title_full	Особенности применения дискретизации в задачах поиска глобального минимума
title_fullStr	Особенности применения дискретизации в задачах поиска глобального минимума
title_full_unstemmed	Особенности применения дискретизации в задачах поиска глобального минимума
title_short	Особенности применения дискретизации в задачах поиска глобального минимума
title_sort	особенности применения дискретизации в задачах поиска глобального минимума
topic	Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
topic_facet	Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
url	https://nasplib.isofts.kiev.ua/handle/123456789/60237
work_keys_str_mv	AT kryžanovskiimv osobennostiprimeneniâdiskretizaciivzadačahpoiskaglobalʹnogominimuma AT malʹsagovmû osobennostiprimeneniâdiskretizaciivzadačahpoiskaglobalʹnogominimuma AT kryžanovskiimv applicationfeaturesofdiscretizationintheproblemofglobalminimumsearch AT malʹsagovmû applicationfeaturesofdiscretizationintheproblemofglobalminimumsearch

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

Репозитарії

Схожі ресурси