close

Вход

Забыли?

вход по аккаунту

?

Линейные методы распознавания образов на множествах объектов произвольной природы представленных попарными сравнениями. Общий случай.pdf

код для вставкиСкачать
Известия Тульского государственного университета
Естественные науки. 2012. Вып. 1. С. 141–152
Информатика
УДК 004.93
Линейные методы распознавания образов
на множествах объектов произвольной
природы, представленных попарными
сравнениями. Общий случай
О. С. Середин
Аннотация. Рассмотрены
линейные
методы
обучения
распознаванию образов для случая, когда объекты распознавания
представлены посредством измерения только действительнозначных
функций парного сравнения. В этой работе, являющейся
заглавной в серии публикаций, не налагается ограничений на
вид функций. Универсальный механизм порождения вторичных
признаков вводится через понятие базисной совокупности объектов
распознавания.
Ключевые слова: беспризнаковое распознавание образов,
линейное решающее правило распознавания, базисная совокупность
объектов распознавания, функция парного сравнения.
Введение
Очевидно, что ни один физический объект ω ∈ Ω не может быть
непосредственно воспринят компьютером. Посредником между теми или
иными свойствами объекта реального мира и ЭВМ выступает некоторая
формальная переменная x(ω) : Ω → X, которая играет роль представимого
в компьютере обобщенного признака (математического представления)
объекта вполне конкретного типа.
Пространство (шкала) X обобщенного признака может иметь весьма
сложную структуру. Например, круг биометрических характеристик
человека [1], используемых в системах идентификации, включает в себя,
в частности, отпечатки пальцев, изображение лица, подпись в виде
изображения либо динамической траектории пера, изображения радужных
оболочек глаз, голос, форму ушей, рисунок сетки кровеносных сосудов
в тех или иных частях тела, силуэт ладони. В медицинской диагностике
типичными видами представления информации о пациенте являются
рентгенограммы, ультразвуковые изображения, магнито-резонансные
томограммы, электро- и магнитоэнцефалограммы [2]. При проведении
142
О. С. Середин
опросов населения изучаемые свойства представителей популяции
измеряются в виде ответов на специальным образом сформулированные
вопросы анкет, каждый из которых образует специфическое множество
возможных вариантов ответов X.
Конкретный способ математического выражения информации об
объектах в задачах анализа данных принято называть модальностью
представления объектов. В терминах выбранной модальности исходное
множество объектов реального мира заменяется множеством их
представлений в пространстве значений соответствующего обобщенного
признака x(ω) ∈ X. Представления формируются в виде сигналов,
изображений, а в сравнительно редких наиболее простых ситуациях – в виде
действительных чисел или их векторов.
С самого начала развития теории машинного обучения делалось
предположение об индивидуальном представлении объектов. Суть её
в следующем: некоторая переменная x(ω) ∈ X : Ω → X определяет
наблюдаемое свойство объекта, представимое в компьютере. Например,
в простейшем случае: X = Rn — конечномерное линейное пространство;
x(ω) = x(ω) = (x1 (ω) . . . xn (ω))T : Ω → Rn — вектор из n числовых
признаков xi ∈ R. Именно такой подход фактически определил развитие
методов и алгоритмов восстановления эмпирических зависимостей на
десятки лет.
Примерно с конца 1990-х годов возникло устойчивое понимание того, что
в целом ряде прикладных задач индивидуальное представление объектов
признаками затруднительно и, как следствие, появилось сравнительное
числовое представление объектов, так называемый беспризнаковый подход
[3–7]. В такой постановке объекты могут быть восприняты компьютером
только через их попарное сравнение. Объективности ради отметим, что
временной раздел по последнему десятилетию двадцатого века весьма
условен. Так, например, один из простейших, давно известных и очевидных
методов обучения — метод ближайшего соседа — фактически использует
только сравнительную характеристику (обычно метрику) между объектами.
Однако, как правило, парная характеристика несходства объектов
появлялась как нечто вторичное, вспомогательное. Изначально объекты
рассматривались как «точки векторного пространства», т.е. имели вполне
измеримые характеристики-признаки (рост, вес, давление, время реакции,
цена акции и пр.).
Мощнейшим стимулом к возможности решения задач, в которых
объекты характеризуются парными свойствами, стал, безусловно,
метод опорных векторов, предложенный В.Н. Вапником [8]. Понятие
потенциальной функции (kernel в англоязычной литературе) [9] на
паре объектов распознавания позволило, оставаясь в рамках линейных
операций, эффективно решать задачу поиска оптимальной разделяющей
гиперплоскости в спрямляющем пространстве. Однако практические задачи
Линейные методы распознавания образов на множествах объектов
143
показывают, что не всякая функция парного сходства обладает свойствами
потенциальной функции.
В этой работе мы предлагаем использовать понятие вторичных признаков
объектов распознавания как универсальную методику, позволяющую
работать фактически с любыми функциями попарных сравнений между
объектами. Суть такого подхода выражается следующей идеей: зафиксируем
подмножество объектов генеральной совокупности, доступных наблюдателю
(базисную совокупность), и определим набор признаков для произвольного
объекта как набор его попарных отношений с объектами базисной
совокупности. В этом случае мы фактически сводим любую задачу
беспризнакового распознавания к «классической» векторной постановке
и можем использовать наработанный десятилетиями алгоритмический
аппарат. Такая идея высказывалась и ранее [10,11]. Однако в работе [10]
в качестве вторичного пространства предлагалось рассматривать только
признаки, порождаемые отношениями между объектами, выражающиеся
евклидовыми расстояниями (dissimilarity space), а в работе [11] — только
потенциальные функции. В этой статье мы показываем, что идея
погружения объектов произвольной природы в линейное пространство их
вторичных действительных признаков позволяет работать с функциями
парных сравнений объектов более широкого класса. Именно возможность
построения методов и алгоритмов работы в линейных пространствах
вторичных действительнозначных признаков дает нам право вынести
в заглавие работы анонс о развитии концепции линейных методов
восстановления эмпирических зависимостей.
Эта статья является заглавной в цикле работ, в которых мы
систематически рассматриваем различные функции сравнения между
объектами обучающей совокупности. В ней мы представляем общую
концепцию обучения в беспризнаковой ситуации и, вообще говоря,
не требуем даже симметричности функции попарного сравнения, а
также предлагаем стратегии обучения для различных практических
ситуаций. Далее мы планируем остановиться на частных случаях
общей концепции использования линейных методов восстановления
эмпирических зависимостей на множествах объектов произвольной природы,
представленных попарными сравнениями. В частности, будут рассмотрены
варианты, когда функция является произвольной метрикой, квадратом
евклидовой метрики, потенциальной функцией, функцией отношения
порядка. В заключительной статье цикла мы уделим особое внимание
селективному комбинированию множества разных функций сравнения,
заданных на одной и той же совокупности объектов. В действительности
оказывается, что такая методика полностью адекватна и, более того,
включает в себя как частный случай ситуацию отбора признаков для
классической «признаковой» постановки задачи интеллектуального анализа
данных.
144
О. С. Середин
1. Типовая задача восстановления закономерностей на
множествах объектов реального мира
Ставший уже классическим подход к восстановлению эмпирических
зависимостей на множествах объектов произвольной природы (в
англоязычной литературе используется термин «machine learning», прямой
перевод которого — «обучение машин» — сейчас уже почти не употребляется
в отечественных источниках) во главу угла ставит принцип обучения
по прецедентам. Это подразумевает, что в качестве исходного массива
эмпирических данных всегда служит некоторая ограниченная выборка из
генеральной совокупности объектов исследуемого вида, представленных,
вообще говоря, всеми модальностями с возможными пропусками данных
по некоторым из них. Обычно одна из модальностей выделена как
целевая, и анализ предъявленного массива данных ориентирован на
построение решающего правила, которое позволило бы отличать значение
соответствующего целевого свойства в принятой для него шкале измерения
от значений других свойств в их специальных шкалах. Главным требованием
является возможность применения решающего правила, построенного на
основе анализа предъявленного массива данных (обучающей совокупности),
к другим объектам, не представленным в нем. Если же целевая переменная
заранее не выделена, то задачей анализа массива данных как выборки из
генеральной совокупности объектов реального мира является построение
модели распределения объектов в гипотетическом пространстве всех их
выбранных свойств, которая была бы адекватной для всей генеральной
совокупности.
Обозначим множество реально существующих объектов как ω ∈ Ω, а
множество значений целевой характеристики объектов y ∈ Y: (ω, y) ∈ Ω × Y.
Наблюдателю предъявляется обучающая совокупность — подмножество
наблюдаемых объектов Ω∗ ⊂ Ω, для которых измерено значение целевой
характеристики (ω ∈ Ω∗ , y): {(ωj , yj ), j = 1, ..., N }. Задача, требующая
решения, заключается в нахождении функции yb(ω), определенной на всем
множестве Ω, такой, чтобы можно было в дальнейшем оценивать значение
рассматриваемой характеристики для новых объектов ω ∈ Ω\Ω∗ . Качество
такого инструмента оценивания скрытой характеристики для реальных
объектов yb(ω) : Ω → Y вполне может быть формализовано относительно
допущенной ошибки yb(ω) 6= y(ω).
Типовые задачи восстановления эмпирических зависимостей определяются
видом целевой переменной y ∈ Y:
— задача обучения распознаванию образов Y = {y1 , ..., ym } — конечное
неупорядоченное множество. В частности, в двухклассовой задаче
распознавания образов выходную величину часто кодируют следующим
образом: Y = {−1, 1}. Забегая вперед, отметим, что именно такие задачи
мы и будем рассматривать в этой статье;
Линейные методы распознавания образов на множествах объектов
145
— задача восстановления числовой регрессии, т.е. оценивания числовой
функции, Y = R – множество действительных чисел;
— задача восстановления ранговой регрессии Y = {y1 < ... < ym } —
конечное множество с отношением линейного порядка.
Очевидно, что непосредственно построить оценочную функцию yb(ω)
невозможно, поскольку объект реального мира ω ∈ Ω не может быть явно
представлен в компьютере. Необходимо обеспечить computer-perceptible representation — погружение объектов реального мира (пациентов, технических
устройств, акций на бирже, нефтеносных скважин, отпечатков пальцев и пр.)
в вычислительную среду ЭВМ. С самого начала развития теории машинного
обучения делалось предположение об индивидуальном представлении
объектов. Суть её в следующем: некоторая переменная x(ω) ∈ X : Ω → X
определяет наблюдаемое свойство объекта, представимое в компьютере.
Например, в простейшем случае: X = Rn — конечномерное линейное
пространство; x(ω) = x(ω) = (x1 (ω) . . . xn (ω))T : Ω → Rn – вектор из n
числовых признаков xi ∈ R и, соответственно, обучающая совокупность
представляется как {(xj = x(ωj ), yj = y(ωj )) , j = 1, ..., N }. Долгое время
именно такое понимание представления объектов анализа определяло
развитие методов и алгоритмов восстановления эмпирических зависимостей.
Примерно с конца 1990-х годов стало понятно, что в ряде прикладных задач
индивидуальное представление объектов признаками затруднительно и,
как следствие, появилось сравнительное числовое представление объектов,
так называемый беспризнаковый подход [3-7]. В такой постановке объекты
могут быть восприняты компьютером только через их попарное сравнение
S(ω 0 , ω 00 ) : Ω × Ω → S ⊆ R, т.е. числовую функцию, выражающую некоторое
сравнительное свойство пар объектов. Обучающая совокупность в этом
случае: {S(ωj , ωl ), yj = y(ωj ), j, l = 1, ..., N }.
В последнее время наиболее эффективным методом обучения
распознаванию образов в линейном пространстве действительнозначных
признаков объектов безусловно является метод опорных векторов (Support
Vectors Machine, SVM) ©
[8], реализующий идею
P оптимальнойª разделяющей
n
гиперплоскости Hn−1 = x ∈ Rn : aT x + b = ni=1 ai xi + b >
<0 ⊂ R .
Дискриминантная функция определяется евклидовым расстоянием от
точки до гиперплоскости с учетом знака
½
> 0 − класс 1,
d(x) = a x + b = ρ(Hn−1 , x)
< 0 − класс − 1,
T
при условии aT a = 1.
Наиболее простая, фактически классическая, форма критерия
обучения SVM получения оптимальной разделяющей гиперплоскости для
обучающей совокупности объектов Ω∗ = {ωj , j = 1, ..., N } двух классов, т.е.
{(xj ∈ Rn , yj = ±1), j = 1, ..., N } в признаковом пространстве:
146
О. С. Середин
P
½Pn
a2 + C N
i=1
j=1 δj → min(a1 , ..., an , b, δ1 , ..., δN ),
Pn i
yj ( i=1 ai xi + b) > 1 − δj , δj > 0, j = 1, ..., N,
(1)
представляет собой задачу выпуклого программирования. Традиционно
задача (1) решается в двойственной форме:
P
PN
½PN
T
λi − 12 N
i=1
j=1
k=1 yj yk xj xk λj λk → max(λ1 , ..., λN ),
PN
i=1 λi yi = 0, 0 6 λj 6 C/2, j = 1, . . . , N.
Результат обучения — дискриминантная функция, применимая к
произвольному объекту ω ∈ Ω, представленному вектором признаков x(ω):
X
>
yj λj xTj x(ω) + b 0,
d(ω) =
j: λj >0
<
xj = x(ωj ) : λj > 0 — так называемые опорные объекты обучающей
совокупности, соответствующие неотрицательным множителям Лагранжа
двойственной задачи.
2. Задача обучения для заданной функции попарного
сравнения объектов в пространстве вторичных признаков
Итак, мы рассматриваем ситуацию, когда наблюдателю доступна лишь
функция попарного сравнения объектов S(ω 0 , ω 00 ) : Ω × Ω → S ⊆ R и
обучающая совокупность Ω∗ = {ωj , j = 1, ..., N } ⊂ Ω, заданная квадратной
матрицей: {S(ωj , ωl ), yj = y(ωj ), j, l = 1, ..., N }. Зафиксируем подмножество
объектов генеральной совокупности,
доступных
наблюдателю, —
©
ª
базисную совокупность Ω0 = ωj0 , j = 1, ..., N 0 ⊂ Ω — и определим набор
порожденных фиктивных признаков для произвольного объекта как набор
его попарных отношений с объектами базисной совокупности. В этом случае
мы фактически сводим любую задачу беспризнакового распознавания к
«классической» векторной постановке и можем использовать наработанный
десятилетиями алгоритмический аппарат.
Особо отметим два момента. Первый: предполагается, что объекты
обучающей совокупности совпадают с элементами базисной. Вполне может
сложиться ситуация, что в прикладной задаче можно определить парные
отношения между объектами (или измерить числовые характеристики,
в ситуации признакового описания), но индексы классов получить
затруднительно. Мы категорически не желаем отказываться от
использования таких объектов в анализе. Уместно говорить в таком случае
о частично классифицированной совокупности объектов обучения. Вполне
разумным предположением является, на наш взгляд, то, что объекты
обучающей совокупности входят как подмножество в базисную Ω∗ ⊂ Ω0 ⊂ Ω.
Действительно, нет смысла отказываться от классифицированных объектов
при построении вторичных признаков. Хотя, в общем случае, вполне
Линейные методы распознавания образов на множествах объектов
147
возможна ситуация, когда в качестве признакообразующих будут взяты
подвыборки как из классифицированной, так и неклассифицированной
выборок объектов распознавания. Таким образом, в дальнейшем мы будем
фокусировать внимание на двух возможных ситуациях: Ω∗ 6= Ω0 , Ω∗ , Ω0 ⊂ Ω
и Ω∗ = Ω0 ⊂ Ω.
Второе существенное обобщение: мы будем рассматривать случай, когда
функция S(ω 0 , ω 00 ) несимметрична S(ω 0 , ω 00 ) 6= S(ω 00 , ω 0 ). Как правило, в
задачах анализа данных парные отношения между объектами являются
симметричными, хотя можно привести примеры и несимметричной
структуры отношений на множестве объектов. Например, социоматрицы
в социометрии, как правило, несимметричны и выражают отношения
между респондентами. Другой пример — это несимметричная функция
сходства изображений при их сопоставлении (image matching) на основе
эластичных трансформаций. В таком случае мы предполагаем, что каждый
объект базисной совокупности ωi порождает два вторичных признака
для объекта ω: S(ωi , ω) и S(ω, ωi ). Вектор вторичных признаков объекта
ω ∈ Ω относительно базисной совокупности размера N 0 определим как:
0
x(ω) = (xi (ω) = S(ωi0 , ω), xN +i (ω) = S(ω, ωi0 ), i = 1, ..., N 0 ) ∈ R2N . Далее,
в окончательных выводах, мы будем специально оговаривать ситуацию
частного случая, когда функция S(ω 0 , ω 00 ) симметрична S(ω 0 , ω 00 ) = S(ω 00 , ω 0 ),
что, безусловно, будет приводить к более простым математическим
формулировкам.
Таким образом, мы собираемся рассмотреть следующие возможные
случаи порождения вторичных признаков:
Таблица 1
0
00
00
0
S(ω , ω ) 6= S(ω , ω )
S(ω 0 , ω 00 ) = S(ω 00 , ω 0 )
Ω∗ , Ω0 ⊂ Ω, Ω∗ 6= Ω0
Общий случай
Частный случай 2
Ω∗ = Ω0 ⊂ Ω
Частный случай 1
Частный случай 3
Общий случай. Классический критерий обучения метода опорных
векторов, опирающийся на вторичные признаки, образованные на
несимметричной функции S(ω 0 , ω 00 ) 6= S(ω 00 , ω 0 ), в случае несовпадения
обучающей совокупности и множества базисных объектов Ω∗ ⊂ Ω0 ⊂ Ω будет
иметь вид:
P 0
PN
2N
2+C

a

i
j=1 δj → min(a1 , ..., a2N 0 , b, δ1 , ...,
 i=1
´ δN ),
³P 0
P
0
N
2N
0
0
yj
i=1 ai S(ωi , ωj ) +
i=N 0 +1 ai S(ωj , ωi ) + b >


> 1 − δ , δ > 0, j = 1, ..., N.
j
j
(2)
148
О. С. Середин
Двойственная задача по отношению к (2):
³P 0

PN
N
1 PN PN
0
0

λ
−
y
y
W
(λ
,
...,
λ
)
=
1
j
j

N
l
j=1
j=1
l=1
i=1 S(ωi , ωl )S(ωi , ωj )+
2 ´

P2N 0
+ i=N 0 +1 S(ωl , ωi0 )S(ωj , ωi0 ) λj λl ,


PN
j=1 yj λj = 0, 0 6 λj 6 (C/2) , j = 1, ..., N.
Решающее правило распознавания для нового объекта ω:
à N0
!
0
2N
X
X
X
>
d(ω) =
yj λj
S(ωi0 , ωj )S(ωi0 , ω) +
S(ωj , ωi0 )S(ω, ωi0 ) + b 0.
<
0
i=1
j: λj >0
i=N +1
Для определения константы b достаточно учесть ограничения
исходной задачи для части опорных объектов j : 0 < λj < C/2, т.е.
тех,
которых δj = 0. Тогда, просуммировав
такие ограничения
³Pдля
´
P
0
N0
2N
0
0
yj
= 1, j : 0 < λj < C/2,
i=1 ai S(ωi , ωj ) +
i=N 0 +1 ai S(ωj , ωi ) + b
оптимальный сдвиг гиперплоскости определим выражением:

X
1
(С /2)
P
b=−
yj +
λj
j:λj =С /2
j:0<λj <С /2
+
X
j:0<λj <С /2
λj
X
l:λl >0
yl λl
à N0
X
S(ωi0 , ωl )S(ωi0 , ωj ) +
i=1
0
2N
X
!
S(ωl , ωi0 )S(ωj , ωi0 )  .
i=N 0 +1
(3)
Если определить вторичные признаки объекта распознавания относительно
базисной совокупности как:
¡
¢
0
x(ωj ) = xij , i = 1, ..., 2N 0 ∈ R2N ,
½
S(ωi0 , ωj ), i = 1, ..., N 0 ,
xij =
0
0
0
S(ωj , ωi−N
0 ), i = N + 1, ..., 2N ,
то выражение (3) можно записать в краткой форме:
P
P
yl λl xTj xl + (С /2)
λj
b=−
j:0<λj <С /2
l:λl >0
P
λj
P
j:λj =С /2
yj
.
(4)
j:0<λj <С /2
Частный случай 1. Множество базисных объектов совпадает с
множеством обучающих, т.е. Ω∗ = Ω0 ⊂ Ω и N 0 = N , при несимметричной
Линейные методы распознавания образов на множествах объектов
149
функции сравнения на парах объектов S(ω 0 , ω 00 ) 6= S(ω 00 , ω 0 ):
(P2N 2
PN
a
+
C
i
i=1
j=1 δj → min(a1 , ..., a2N , b, δ1 , ...,
³P
´ δN ),
P2N
N
yj
i=1 ai S(ωi , ωj ) +
i=N +1 ai S(ωj , ωi ) + b > 1 − δj , δj > 0, j = 1, ..., N.
(5)
Двойственная задача по отношению к (5):
P
PN
N
1 PN PN

 i=1 λi − 2 j=1 k=1 yj yk i=1 (S(ωi , ωj )S(ωi , ωk )+
(6)
+S(ωj , ωi )S(ωk , ωi )) λj λk → max(λ1 , ..., λN ),

PN λ y = 0, 0 6 λ 6 C/2, j = 1, . . . , N.
j
i=1 i i
Как видим, запись квадратичной формы критерия двойственной задачи
оказалась достаточно громоздкой, поэтому ниже по тексту в случаях, где это
уместно, мы будем выписывать часть критерия в матричной форме. Такой
вариант для критерия (6) будет иметь вид:
¡
¢
P
PN
½ T
T SST + ST S λ → max(λ),
1 λ − 12 N
j=1
k=1 λ
yT λ = 0, 0 6 λ 6 (C/2)1,
здесь введены обозначения S = {S(ωi , ωj ), i, j = 1, ..., N }, λ = (λ1 . . . λN )T ,
y = (y1 . . . yN )T и 1 = (1. . . 1)T . Решающее правило распознавания для нового
объекта ω:
ÃN
!
2N
X
X
X
>
S(ωi , ωj )S(ωi , ω) +
S(ωj , ωi )S(ω, ωi ) + b 0.
yj λj
d(ω) =
<
i=1
j: λj >0
i=N +1
Константа b в этом случае будет определяться выражением:

X
1
(С /2)
P
yj +
b=−
λj
j:0<λj <С /2
+
X
j:0<λj <С /2
λj
X
l:λl >0
Ã
yl λl
N
X
i=1
j:λj =С /2
S(ωi , ωl )S(ωi , ωj ) +
2N
X
!
S(ωl , ωi )S(ωj , ωi )  ,
i=N +1
(7)
и если определить вторичные признаки объекта распознавания относительно
базисной (обучающей в данном частном случае) совокупности как:
½
S(ωi , ωj ), i = 1, ..., N,
2N
x(ωj ) = (xij , i = 1, ..., 2N ) ∈ R , xij =
S(ωj , ωi−N ), i = N + 1, ..., 2N,
то выражение (6) можно записать в краткой форме, точно совпадающей с
(4).
Частный случай 2. Для симметричной функции S(ω 0 , ω 00 ) = S(ω 00 , ω 0 )
в случае несовпадения обучающей совокупности и множества базисных
150
О. С. Середин
объектов Ω∗ , Ω0 ⊂ Ω, Ω∗ 6= Ω0 критерий обучения запишется в следующем
виде:
(PN 0
PN
2
1 , ..., aN 0 , b, δ1 , ..., δN ),
i=1
³Pai 0+ C j=1 δj → min(a
´
(8)
N
0
yj
i=1 ai S(ωi , ωj ) + b > 1 − δj , δj > 0, j = 1, ..., N.
Двойственная задача по отношению к (8) принимает вид:
(P
P
PN
P 0
N
0
0
yj yk N
λi − 12 N
i=1
j=1
k=1
i=1 (S(ωi , ωj )S(ωi , ωk ))λj λk → max(λ1 , ..., λN ),
PN
i=1 λi yi = 0, 0 6 λj 6 C/2, j = 1, . . . , N.
Результат обучения представлен дискриминантной функцией, применимой
к произвольному объекту ω ∈ Ω:
µX 0
¶
X
N
>
0
0
d(ω) =
yj λj
S(ωi , ωj )S(ωi , ω) + b 0.
j: λj >0
i=1
<
Константа сдвига гиперплоскости b определяется как:
´
³P 0
P
P
N
0
0
λj
yl λl
i=1 S(ωi , ωl )S(ωi , ωj ) + (C/2)
b=−
j:0<λj <С /2
l:λl >0
P
λj
P
j:λj =С /2
yj
,
j:0<λj <С /2
(9)
и если определить вторичные признаки объекта распознавания относительно
базисной совокупности как:
¡
¢
0
x(ωj ) = xij , i = 1, ..., N 0 ∈ RN , xij = S(ωi0 , ωj ), i = 1, ..., N 0 ,
то выражение (8) можно записать в краткой форме, совпадающей с (4).
Частный случай 3. В случае симметричной функции S(ωj , ωl ) =
= S(ωl , ωj ), j, l = 1, ..., N и совпадения множеств объектов обучающей и
базисной выборок Ω∗ = Ω0 ⊂ Ω критерий обучения, опирающийся на N 0 = N
вторичных признаков и оптимизируемый по коэффициентам a1 , ..., aN , будет
иметь вид:
(PN 2
PN
i=1
³Pai + C j=1 δj → ´min(a1 , ..., aN , b, δ1 , ..., δN ),
(10)
N
yj
i=1 ai S(ωi , ωj ) + b > 1 − δj , δj > 0, j = 1, ..., N.
Обучение проводится по N объектам обучающей совокупности,
представленным N взаимными вторичными признаками. Параметром
регуляризации является коэффициент С . Двойственная задача по
отношению к (10) принимает вид:
P
P
PN
½PN
yj yk N
λi − 12 N
i=1 (S(ωi , ωj )S(ωi , ωk ))λj λk → max(λ1 , ..., λN ),
j=1
k=1
i=1
PN
i=1 λi yi = 0, 0 6 λj 6 C/2, j = 1, . . . , N.
Линейные методы распознавания образов на множествах объектов
151
Результат обучения представлен дискриминантной функцией, применимой
к произвольному объекту ω ∈ Ω:
ÃN
!
X
X
>
d(ω) =
yj λj
S(ωi , ωj )S(ωi , ω) + b 0.
<
j: λj >0
i=1
Константа сдвига гиперплоскости b определяется как:
³P
´
P
P
N
λj
yl λl
S(ω
,
ω
)S(ω
,
ω
)
+ (C/2)
i
i
j
l
i=1
b=−
j:0<λj <С /2
l:λl >0
P
P
j:λj =С /2
λj
yj
,
j:0<λj <С /2
(11)
и если определить вторичные признаки объекта распознавания относительно
базисной совокупности как:
x(ωj ) = (xij , i = 1, ..., N ) ∈ RN ,
xij = S(ωi , ωj ), i = 1, ..., N,
то выражение (11) можно записать в краткой форме, совпадающей с (4).
Заключение
Этой работой мы начинаем цикл публикаций, посвященных линейным
методам беспризнакового обучения распознаванию образов. Рассмотрен
общий случай, когда на функцию попарного сходства объектов не
накладывается
ограничений.
Пространство
вторичных
признаков
порождается путем вычисления значений заданной функции сравнения
объектов относительно элементов базисной совокупности. Рассмотрены
частные варианты выбора подмножества базисных объектов и ситуация,
когда функция парного сравнения несимметрична. В следующей статье
мы детально рассмотрим ситуацию, когда функция отношения обладает
свойствами потенциальной функции.
Список литературы
1. Ross A., Jain A.K. Multimodal biometrics: An overview // Proceed. of the
12th European Signal Processing Conference (EUSIPCO). Vienna. Austria, 2004.
P.1221–1224.
2. A data fusion environment for multimodal and multi-informational neuronavigation
/P. Jannin [et al.] // Comput Aided Surg. 2000. V.5. №1. P.1–10.
3. Duin R.P.W, De Ridder D., Tax D.M.J. Featureless classification // Proceed. of the
Workshop on Statistical Pattern Recognition. Prague, 1997. P.37–42.
4. Duin R., Pekalska E., Ridder D. Relational Discriminant Analysis // Pattern Recognition Letters 20. 1999. P.1175–1181.
5. Classification on pairwise proximity data / T. Graepel [et al.] // NIPS. MIT Press.
Cambridge, MA. 1999. V.11.
152
О. С. Середин
6. Featureless Pattern Recognition in an Imaginary Hilbert Space and Its Application
to Protein Fold Classification / V.V. Mottl [et al.] // Proceedings of Second International Workshop on Machine Learning and Data Mining in Pattern Recognition.
Leipzig, 2001. P.322–336.
7. Pekalska E., Duin R. Automatic pattern recognition by similarity representations //
Electronic Letters. 2001. V. 37(3). P.159–160.
8. Vapnik V. Statistical Learning Theory. NY.: J. Wiley, 1998. 768 p.
9. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных
функций в теории обучения машин. М.: Наука, 1970. 384 с.
10. Pekalska E., Duin R.P.W., Paclik P. Prototype selection for dissimilarity-based
classifiers // Pattern Recognition. 2006. V.39. P.189–208.
11. Середин О.С. Методы и алгоритмы беспризнакового распознавания образов:
дис. ... канд. физ.-мат. наук. Тула, 2001.
Середин Олег Сергеевич (oseredin@yandex.ru), к.ф.-м.н., доцент, кафедра
автоматики и телемеханики, Тульский государственный университет.
Linear methods of pattern recognition for objects of arbitrary
nature via their pairwise comparisons. The general case
O. S. Seredin
Abstract. Linear methods of learning in the pattern recognition are considered
when objects are represented via pairwise comparison function. In this paper
which is the first in the series discussed the general case without any restrictions
on function output. The universal mechanism of secondary features production
is a concept of basis set of object.
Keywords: featureless pattern recognition, linear decision rule of recognition,
basis subset of recognized objects, comparison function.
Seredin Oleg (oseredin@yandex.ru), candidate of physical and mathematical
sciences, associated professor, department of automation and remote control, Tula
State University.
Поступила 15.12.2011
1/--страниц
Пожаловаться на содержимое документа