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

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

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

Библиографический список

1. Гэтлин К.С.. OpenMP и C++ / К.С. Гэтлин, П. Айсенси // МСДН Журна. - 2005. - №10. - C.10-18.

2. Т-система с открытой архитектурой / С.М. Абрамов [и др.] // Суперкомпьютер ные системы и их применение SSA’2004: тр. Международной научной конференции, 26-28 октября 2004 г. Минск, ОИПИ НАН Беларуси. - Минск, 2004. - С. 18-22.

3. Дейкстра Э. Дисциплина программирования / Э.Дейкстра. - М.: Мир, 1978 .- 408 с.

4. Валиев М.К. Применение временной логики к спецификации программ. / М.К. Ваиев // Программирование. - 1998. - №2. - С.3-9.

5. Макконнелл С. Совершенный код / С. Макконнелл. - СПб.: Питер, 2007. - 896 с.

6. Yu Y. RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Tracking / Y. Yu, T. Rodeheffer, W. Chen // SOSP05, October 23-26, 2005, Brighton, United Kingdom.

Получено 23.04.08

УДК 681.327.12

В.В. Моттль, А.И. Татарчук, (Москва, ВЦРАН),

А.П. Елисеев

ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДОВ МНОГОМОДАЛЬНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ С РЕГУЛИРУЕМОЙ СЕЛЕКТИВНОСТЬЮ

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

Работа втолненапри поддержке РФФИ проекты № 05-01-00679, 06-01-08042, 06-07-89249.

Введение

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

197

доступной информации об объектах реального мира coeQ, который принято шзывать модальностью (modality) представления объектов [1,2]. Модальность может быть выражена в виде признака объекта x(ю) е X с некоторой шкалой измерения X или в виде меры попарного сходства р(ю', ю") е R+ между объектами со', сЮ е Q.

Интенсивное развитие беспризнаковой методологии распознавания образов [3-6], основанной на понятии потенциальной функции (kernel) K (ю',сЮ) eR, унифицирующей различные представления объектов ю',ю"еО в виде элементов гипотетического линейного пространства x(o'),x(o") eX со скатным произведением K(<ю',ю"), позволяет использовать фактически весь наработанный арсенал линейных методов анализа данных. Стремление обеспечить требуемое качество распознавания привело к созданию многомодальных систем распознавания.

Эффект переобучения приводит к проблеме сокращения исходного множества модальностей или отбора признаков (modality or feature selection). Принято разделять все методы отбора признаков на фильтры (filters) и встроенным методы (wrappers) [7].

В данной работе рассматриваются две модификации метода опорных векторов (SVM) [4]: метод релевантных потенциальных функций (Relevance Kernel Machine или RKM) [8,9] и метод опорных потенцшльных функций (Support Kernel Machine или SKM) [9,10]. Результаты экспериментального исследования на модельных данных наглядно демонстрируют адекватность механизма регулируемой селективности при многомодальном распознавании образов.

Квазивероятностный подход

Будем предполагать, что все объекты ю е Q поделены на два класса Хю) е Y = {-1,+1} и на этом множестве объектов заданы n признаков ил

модальностей в некоторых шкалах xi(ю) eXi• ,i = 1,,n. Однако беспризна-ковая концепция распознавания образов фактически полностью стирает грань между различными видами представлений объектов и позволяет для простоты изложения рассматривать все исходные модальности xj(ю) е Xj в

виде действительных признаков Xj = R.

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

(X1,.,n)е Rx...xR = Rn, в котором объективно существует некоторая гиперплоскость _y(x1,.,n |с?1,.,an,) = ХГ=1 ajXj +b = 0. При этом выбор на-

правляющего вектора (аі,...уп) є Яп и значения порога Ь є Я полностью задает классификацию множества объектов юеО.

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

Будем предполагать существование плотности распределения в пространстве наблюдаемых признаков и скрытых индексов классов (х\,...,хп у) еЯх...хЯ х7, а также то, что элементы обучающей совокупности (Х,У )={хі у у. у Уу У =1у . N1, Ху = ху (юу), у] = у(юу), юу еО

выбраны независимо.

В качестве модели генераьной совокупности будем рассматривать два параметрических семейства плотностей распределения ф(Хіу.,хп | аі,...,ап,Ь,у) с у є {-іуі}, связанных с разделяющей гиперплоскостью ХП=і аіХі(ю) +Ь =0 в комбинированном признаковом пространст-

ве:

ф

сош^ у (Ц=іа1х1 + Ь) > і,

-(і-у(іп=іах + Ь)) ,уХп=іах + Ь<і.

Будем рассматривать направляющий вектор (аі,...уп) разделяющей гиперплоскости ХГ=і а^хі + Ь = 0 как случайный вектор с априорной плотностью распределения ^(аі,...,ап |), задаваемой параметром ц. Что

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

^(а!,..., У І) сх^(аі,...,ап І).

Принцип максимизации апостериорной плотности распределения Р(аі, ...,апУ |Х,Уу) в пространстве параметров модели (аі,...,хп,Ь) приводи к байесовскому правилу обучения:

где ф(XІУіх.УпУ) =П^)=іф(хіух-Уп] \аіх.;ХпУУ]) .

Нетрудно покаать, что при такой постановке задачи обучения (1) получим следующий оптимизационный критерий:

і99

В частности, если в качестве априорного распределения компонент направляющего вектора ^(а^,,ап||ы) =х¥(а]_,...,ап) принять нормальное распределение с независимыми компонентами, нулевыми математическими ожиданиями и равными дисперсиями г и обозначить С = 2гс, то получим классический метод опорных векторов ^УМ) [4] для вещественных признаков Ху еX; =Я и вещественных компонентов направляющего вектора а; еХ;=Я:

В терминах потенциальных функций К;(х'г-,х'/) -X; XX; ^Я, заданных в произвольных шкалах соответствующих модальностей х; е X;, метод опорных векторов (3) примет вид

Компоненты направляющего вектора а; могут быть не представлены в исходной шкае значений признаков а; £ X;, а принадлежать гипотетическом линейному пространству а; е X; з X;, в которое исходная шкаа значений погружена заданной потенциальной функцией. Однако всегда оказывается, что оптимальный направляющий элемент а; является линейной комбинацией реально существующих объектов из обучающей совокупности а; = Ху:% .>оХуУуХу еX;, а решающее правило

Ху:. . >0 X у У у ХП=1 К; (Ху, х ;)+ Ь полностью определяется неотрицательными

множителями Лагранжа X у > 0 при ограничения оптимизационной задачи (4), соответствующих опорным объектам.

Метод релевантных потенциальных функций с регулируемой селективностью

Примем в качестве априорной плотности распределения компонент а; направляющего вектора разделяющей гиперплоскости

у(х1,.,.хп |а!,.,ап,Ь) = 0 нормальное распределение с нулевыми математическими ожиданими и дисперсиями г;:

ЕП=1 а2 + СЕу= Ъ у ^ т1п

У у (п=1аху + ь) > 1 -Ъу , Ъу > 0, у = 1, .,N1.

v(a I r) = (1 / ц12 (2л)1/2 j exp(-(1/ 2 r )ai) j,

an | I,..,) «(П^Ц j exP(-(1/2)Zf=/(1/Ц)щ j.

Кроме того, будем предполагать, что и сами величины, обратные дисперсиям 1/ г, имеют априорное гамма-распределение

у((1/ ц) |а,3 j с (1/ r)а_1 exp(-3(1/ ц)j с равными математическими ожиданиями E(1 /ц) = а/3 и дисперсиями

D (1/ ц ) = а / 32, а также примем а = (1 + |ы)2 / 2д и 3 = 1/ 2д. Таким образом, получаем параметрическое семейство распределений относительно параметра д>0 такое, что E(1 / ц) = (1+д)2 и D(1 / ц) = 2д(1+д)2. Если д 0, то значения 1 /ц уравниваются 1/ц =... = 1 / rn = 1, однако при увеличении д величины 1/ ц могут значотельно различаться, а при д ^ 1 /ц ^ да.

Апостериорная совместная плотность распределения величин 1 / ц примет вид

G(r1,,,rn 1д)с(пп=11/ rj 1exP(-3Zf=1(1/r)j.

Принцип максимизации совместной апостериорной плотности

P

приводит к критерию обучения:

Zn

7=1

1 ( 1 ^ 2 1 f 1 і ^

at + — + + 1 + д ln Гі

ri 1 lJ 1д J

+ CZ^=1S/ ^ mln(ai,rXXj),

У/(Х”=іах +ь)>і-§/,8/ >0,

Наименьшие значения ц соответствуют неменьшим по величине компонентам щ и, следовательно, і -й признак фактически не участвует в

решающем правиле ХП=і аіхі +Ъ, что легко видеть, если записать решающее правило через потенциальные функции

Х /-х >о Х/У/ Х”=і ЦКі(Xі,Х) +Ь, в котором дисперсии ц выступают в ро-

ли весов соответствующих потенциальных функций.

Для решения оптимизационной задачи (5) предлагается проводить поочередную минимизацию по группам переменных (а^,.,,Ь) и

2G1

При д = 0 критерий (5) примет вид классического SVM (3), не обладающего селективностью, но пи получим критерий

ХП=1 (1/ Г)а2 +М'1п Г +СХу=1 ^ тт в (5), который будет более селек-

тивным, чем исходный критерий ХП=1 (1/ Г )а2 +1п Г + С Х^=1^ ^ тт

RKM [8,9], вследствие чего предлагаемый метод отбора признаков был назван методом релевантных потенциальных функций с регулируемой селективностью.

Метод опорных потенциальных функций с регулируемой селективностью

Теперь пусть априорна плотность ^(а^...,ап ||ы) выражена через

выпуклую функцию q(а | д) в виде

^( а1,...,ап I д)«ехр (-£П=^(а/1 д)).

Очевидно, что общий критерий обучения (2) примет вид

Xn=1 q(ai | д) + с£$=1 jj ^ min(a1,, an,b,1,..,N),

q

q( ai 1д) =

yj (Ti^aXij + bj > 1 - jj ,j > 0,' = 1,,,N.

Для действительных признаков X/ e R предлагается кусочнолинейна квадратична функция

В терминах потенциаьных функций эквиваентна запись функции имеет вид

2д^Ki (an ai), если^/Kt (ai ,i) < д,

д2 + Ki(ai,ai), если jK/(a/,a/) > д.

C учетом (7) оптимизационна задача (6) является задачей выпуклого программирования:

2д1| |<дК- 1+Хц д(a2 + д2)+с j jj ^ min(a1,.an ,b,j1,.,jN )j yj (Z/L1 axj + ь j > 1 - jj, jj >o, = 1,,,n.

Параметр 0 < д < да выполняет роль параметра селективности и при

д = 0 ^ q(ai | д) = const + ai оптимизационный критерий (8) экиваентен SVM [4], а пи д да ^ q(ai | д) с д | ai | представляет собой метод SKM [9,10] с увеличивающейся способностью отбора признаков по мере увеличения д относительно параметра с.

Такой подход был назван методом опорных потенциальных функций с регулируемой селективностью, поскольку аналогично метод опорных потенциальных функций (SKM) в результате обучения при заданном значении параметра селективности д > 0 формируется подмножество

опорных признаков (потенциальных функций) с ненулевыми компонентами fy >0 направляющего вектора искомой раделяющей

гиперплоскости.

Экспериментальное исследование

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

T

ax =0 и ориентированных вдоль ее направляющего вектора a = («i =0,8,«2 =0,75,...,«5 = 0,6,a6 = 0,...,а^0 =0), в котором первые 5 элементов отличны от нуля. Таким обраом, только 5 признаков содержат информацию о разделении классов и 95 являются шумовыми. Генерировались обучающие выборки рамером N = N+i = N_ =50 +50 =100 и тестовые Ntest = 5000 + 5000 =10000 .

Для набора возрастающих значений параметра селективности д > 0 проводилось обучение по критериям (5) и (8) и оцениваась обобщающая способность полученных решений на тестовой совокупности (ошибку на тестовой совокупности для больших Ntest можно считать ошибкой на ге-нераьной совокупности), а также на скользящем контроле (10-fold validation). Результаты экспериментов приедены на рис. 1 и 2.

0,08

0,00

'Доля ошибок классификации

^ СКОЛЬЗЯЩИЙ і Dir А* ^ контроль і И Klxlrl 0,5 ♦

ч 1

\ \ \ V і / 1 і / 1 1

тестовая совокупность 1 1 1

>

0,0Е+00 1.0Е+01 1.0Е+02 1,0Е+03 1,0Е+04 1,0Е+05

Рис. 1. Качество обучения на тестовой совокупности и по результатам скользящего контроля (10-fold validation) для метода селективного RKM при возрастающем наборе значений параметра

селективности 0 ^ д да

0,08

u-SKM \ °\5

0,00

0,06

0,04

0,02

0,0Е+00 1,0Е+01 1,ОЕ+02 1,0Е+03 1,0Е+04 1,0Е+05

Рис. 2. Качество обучения на тестовой совокупности и по результатам скользящего контроля (10-fold validation) для метода селективного SKM при возрастающем наборе значений параметра

селективности 0 ^ д да

При наименьшей селективности д = 0 ошибка обоих методов на тестовой совокупности составляет 0,0538, что эквивалентно обучению SVM на всех 100 признаках одновременно.

Минимаьна ошибка, достигаема методом RKM, составляет

0,0052, что сравнимо с ошибкой SVM 0,0085 на первых 5 "аумных” признаках. Однако ошибка метода SKM 0,0124 в два раа больше, чем у RKM, что можно объяснить недостаточной гибкостью метода с отбором подмножества опорных признаков в сравнении с взвешиванием признаков.

При даьнейшем увеличении селективности д да все веса у RKM

стремятся к нулю r ^ 0, а SKM сокращает множество опорных признаков

до пустого множества. Соответственно ошибка обучения сначаа достигает критического уровня 0,0245, а затем ошибка поднимается до максимального уровня 0,5.

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

1. Ross A. Multimodal biometrics: An overview / A. Ross, A. Jain // Proceedings of the 12th European Signal Processing Conference, Vienna, Austria, 2004.

2. A data fusion environment for multimodal and multi-informational neuronavigation / P. Jannin [et al.] // Computer Aided Surgery. - 2000. - Vol.5.

Библиографический список

- No. 1 - P. 1-10.

3. Aizerman M.A. Theoretical foundations of the potential function method in pattern recognition learning / M.A. Aizerman, E.M. Braverman,

L.I. Rozonoer // Automation and Remote Control. - 1964. - Vol. 25. - P. 821837.

4. Vapnik V. Statistical Learning Theory / V. Vapnik // John-Wiley & Sons, Inc. 1998.

5. Duin R.P.W. Featureless classification / R.P.W Duin, D. De Ridder,

D.M.J. Tax // Proceedings of the Workshop on Statistical Pattern Recognition, Prague, June, 1997.

6. Моттль В. В. Метрические пространства, допускающие введение линейных операций и скаярного произведения / В. В. Моттль // Доклады Российской академии наук. - 2003. - Т. 67. - № 1. - С. 140-143.

7. Feature Extraction, Foundations and Applications / I. M. Guyon [et al.] - Springer, 2006.

8. Sulimova V. Multi-kernel approach to on-line signature verification / V. Sulimova, V. Mottl, A Tatarchuk// Proceedings of the 8th IASTED International Conference on Signal and Image Processing. - Honolulu, Hawaii, August 14-16, 2006.

9. Combining pattern recognition modalities at the sensor level via kernel fusion / V. Mottl [et al.] // Proceedings of the 7th International Workshop on Multiple Classifier Systems. - Czech Academy of Sciences, Prague, Czech Republic, May 23-25, 2007.

10. Sonnenburg S. A general and efficient multiple kernel learning algorithm / S. Sonnenburg, G. Ratsch, C. Schafer // Proceedings of the 19th Annual Conference on Neural Information Processing Systems. - Vancouver, December 5-8, 2005.

Получено 23.04.08

УДК 621.762.4:621.983.044

Е.Н. Пальчун, Н.Е. Проскуряков, Н.Н. Архангельска

МОДЕЛИРОВАНИЕ ПРОЦЕССА ОБЖИМА ИМПУЛЬСНЫМ МАГНИТНЫМ ПОЛЕМ СИСПОЛЬЗОВАНИЕМ ТЕОРИИ ПОДОБИЯ

Рассмотрены вопросы моделирования операций электромагнитной штамповки и предложен критерий оценки и сравнения их энергоемкости для

заготовок из разных материалов.

Применительно к процессам обработки металлов давлением (ОМД) моделированием можно исследовать закономерности формоизменения