Как формулировать задачи обучения в распознавании образов
Исследованы задачи распознавания образов в ситуации, когда статистическая модель распознаваемого объекта известна лишь частично. Выполнен критический анализ минимаксного подхода к решению таких задач и подхода, основанного на максимально правдоподобном оценивании модели по обучающей выборке. Сформул...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/5541 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Как формулировать задачи обучения в распознавании образов / М.И. Шлезингер, А.В. Бондаренко // Управляющие системы и машины. — 2009. — № 1. — С. 4-19. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859656677299585024 |
|---|---|
| author | Шлезингер, М.И. Бондаренко, А.В. |
| author_facet | Шлезингер, М.И. Бондаренко, А.В. |
| citation_txt | Как формулировать задачи обучения в распознавании образов / М.И. Шлезингер, А.В. Бондаренко // Управляющие системы и машины. — 2009. — № 1. — С. 4-19. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| description | Исследованы задачи распознавания образов в ситуации, когда статистическая модель распознаваемого объекта известна лишь частично. Выполнен критический анализ минимаксного подхода к решению таких задач и подхода, основанного на максимально правдоподобном оценивании модели по обучающей выборке. Сформулирована постановка задачи, покрывающая весь спектр ситуаций для обучающих выборок любого объема, от нулевого до бесконечного. Выполнен формальный анализ задач обучения в этой новой постановке и показано ее решение в некоторых простейших случаях.
Досліджено задачі розпізнавання образів у ситуації, коли статистична модель розпізнаваного об’єекта відома лише частково. Виконано критичний аналіз мінімаксного підходу до розв’язання таких задач та підходу, заснованого на максимально правдоподібному оцінюванні моделі за навчальною вибіркою. Сформульовано постановку задачі, яка покриває весь спектр ситуацій для навчальних вибірок будь-якого об’єму, від нульового до безкінечного. Виконано формальний аналіз задач навчання у цій новій постановці та показано її розв’язання у деяких найпростіших випадках.
Pattern recognition problems are considered for a case when a statistical model of an object is not completely known. A minimax approach to solution of such problems is critically analyzed as well as an approach based on the maximal likelihood model estimation with respect to given training multiset. The suggested formulation of the recognition learning problem embraces a whole spectrum of situations for training sets of an arbitrary size: from zero to infinite ones. Main formal properties of the suggested problem formulation are analyzed and its solution in several simplest cases is shown.
|
| first_indexed | 2025-12-07T13:39:38Z |
| format | Article |
| fulltext |
4 УСиМ, 2009, № 1
Фундаментальные и прикладные проблемы Computer Science
УДК 004.93’1: 519.157
М.И. Шлезингер, A.В. Бондаренко
Как формулировать задачи обучения в распознавании образов
Исследованы задачи распознавания образов в ситуации, когда статистическая модель распознаваемого объекта известна лишь
частично. Выполнен критический анализ минимаксного подхода к решению таких задач и подхода, основанного на макси-
мально правдоподобном оценивании модели по обучающей выборке. Сформулирована постановка задачи, покрывающая весь
спектр ситуаций для обучающих выборок любого объема, от нулевого до бесконечного. Выполнен формальный анализ задач
обучения в этой новой постановке и показано ее решение в некоторых простейших случаях.
Pattern recognition problems are considered for a case when a statistical model of an object is not completely known. A minimax ap-
proach to solution of such problems is critically analyzed as well as an approach based on the maximal likelihood model estimation
with respect to given training multiset. The suggested formulation of the recognition learning problem embraces a whole spectrum of
situations for training sets of an arbitrary size: from zero to infinite ones. Main formal properties of the suggested problem formulation
are analyzed and its solution in several simplest cases is shown.
Досліджено задачі розпізнавання образів у ситуації, коли статистична модель розпізнаваного об’єекта відома лише частково.
Виконано критичний аналіз мінімаксного підходу до розв’язання таких задач та підходу, заснованого на максимально правдо-
подібному оцінюванні моделі за навчальною вибіркою. Сформульовано постановку задачі, яка покриває весь спектр ситуацій
для навчальних вибірок будь-якого об’єму, від нульового до безкінечного. Виконано формальний аналіз задач навчання у цій
новій постановці та показано її розв’язання у деяких найпростіших випадках.
Введение. В работе исследуется задача распо-
знавания образов в обычной для практики си-
туации, когда статистическая модель распо-
знаваемого объекта известна не полностью, а
известен лишь класс моделей, которому она
принадлежит. Известно, например [1], что за-
дача распознавания допускает разумную, так
называемую минимаксную формулировку и в
такой, не полностью определенной статисти-
ческой ситуации. Задача в этой формулировке
состоит в построении стратегии, обеспечиваю-
щей удовлетворительное качество распознава-
ния при любой модели из заданного класса.
В случае, когда недостающие знания о мо-
дели объекта частично восполняются так на-
зываемой обучающей выборкой, возникает во-
прос, как эти дополнительные сведения исполь-
зовать для улучшения качества распознавания.
Совокупность подходов к решению этого во-
проса составляет современную теорию обуче-
ния в распознавании образов. Большая часть
этих подходов состоит в разделении процесса
распознавания на два этапа. Сначала находят
модель из заданного класса, которая в опреде-
ленном смысле наилучшим образом согласу-
ется с обучающей выборкой. Затем с этой на-
илучшей моделью поступают так, будто она
совпадает с действительной. Это отождествле-
ние правомерно лишь для обучающих выборок
достаточно большой длины. В противном слу-
чае возникает масса вопросов, известных как
проблема коротких выборок.
Указанные подходы охватывают далеко не
всю проблему, а лишь два ее крайних частных
случая: в отсутствие обучающей выборки (ми-
нимаксный подход) и при неограниченно боль-
шой ее длине (существующие методы обуче-
ния). Дадим такую формулировку задачи обу-
чения в распознавании, которая охватывает
весь спектр ситуаций для обучающих выборок
любой длины: от нулевой до бесконечной.
Формулировка основных понятий
Будем говорить об объекте, который харак-
теризуется двумя случайными параметрами x и
k. Эти параметры принимают значения из двух
конечных множеств, X и K соответственно.
Параметр x будем называть наблюдаемым при-
знаком объекта, или наблюдением, а параметр
k – его скрытым, непосредственно не наблю-
даемым состоянием. Также будем говорить о
УСиМ, 2009, № 1 5
конечном множестве M моделей и об m ∈ M,
как о некоторой модели из этого множества.
Пусть функция p : X × K × M → R такова, что
ее значение p(x, k; m), x X∈ , k K∈ , m M∈ ,
есть совместная вероятность наблюдения x и
состояния k в модели m.
Множество ( ){ }, , x k x X k K∈ ∈ обозначим
Λ , а через nΛ обозначим множество обучаю-
щих выборок длины n, 1, ...n = . Одна отдель-
ная выборка n nL ∈Λ имеет вид
( )1 1 2 2, ; , ; , ,n
n nL x k x k x k= … .
Введем также обозначение 0L для обучаю-
щей выборки нулевой длины и 0Λ для непус-
того множества, содержащего единственную
выборку 0L .
Примем, что на множестве nΛ задано рас-
пределение вероятностей, зависящее от модели
m, так что
( ) ( )
1
; , ;
n
n
i i
i
p L m p x k m
=
=∏ , n nL ∈Λ , m M∈ .
При этом считается, что ( )0; 1p L m = .
Функцию :q X K R× → будем называть
стратегией распознавания. Ее значение ( )/q k x
понимается как условная вероятность приня-
тия решения, что объект находится в состоя-
нии k, при условии, что на вход стратегии по-
дано наблюдение x. На данной стадии изложе-
ния введение такой рандомизированной стра-
тегии распознавания может показаться ненуж-
ным усложнением в сравнении с детерминиро-
ванной стратегией вида X K→ . Однако в
дальнейшем определение стратегии именно в
рандомизированном виде существенно упро-
стит доказательство некоторых утверждений.
Множество X KR × всех возможных страте-
гий вида :q X K R× → обозначим Q. При этом,
естественно, предполагается, что Q содержит
только те функции q, для которых
( )/ 1
k K
q k x
∈
=∑ , x X∈ , ( )/ 0q k x ≥ , x X∈ , k K∈ .
Под стратегией обучения, или алгоритмом
обучения, будем понимать функцию, которая
для каждой обучающей выборки nL указывает
стратегию распознавания из множества Q. Обо-
значим :n nq QΛ → стратегию обучения по обу-
чающей выборке длины n. Для каждой обу-
чающей выборки n nL ∈Λ она определит стра-
тегию ( ) :n nq L X K R× → распознавания. Эта
стратегия распознавания, примененная к неко-
торому конкретному значению x признака, вы-
дает случайное решение k о состоянии объекта
с вероятностью ( )( )/n nq L k x . Для каждой стра-
тегии :n nq QΛ → определим рандомизиро-
ванную стратегию :n nq L X× × K R→ , так что
( ) ( )( )/ , /n n n nq k x L q L k x= ,
и назовем ее стратегией обучения-распозна-
вания. Стратегии nq и nq – формально различ-
ные функции, так как первая имеет формат
n X K RΛ × × → , а вторая – n QΛ → . Однако их
содержательный смысл один и тот же. Страте-
гия обучения :n nq QΛ → указывает, как стра-
тегия распознавания зависит от обучающей
выборки, а стратегия обучения-распознавания
:n nq L × X K R× → указывает, как решение о
состоянии k объекта по признаку x должно за-
висеть от обучающей выборки nL . Поэтому в
дальнейшем будем использовать как понятие
стратегии обучения nq , так и равноценное ему
понятие стратегии nq обучения-распознавания.
Пусть :w K K R× → – функция потерь со
значениями ( ),w k k′ , обозначающими потери в
случае, когда об объекте, находящемся в со-
стоянии k, принимается решение, что он нахо-
дится в состоянии k ′ . Риском стратегии
:q X K R× → на модели m называется матема-
тическое ожидание штрафа, т.е. число
( ) ( ) ( ) ( ), / , ; ,
k K k K
x X
R q m q k x p x k m w k k
′∈ ∈
∈
′ ′= ⋅ ⋅∑ ∑ .
Для каждой модели m M∈ определим риск
( ) ( )min ,B
q Q
R m R q m
∈
= , который назовем байе-
совским риском для модели m, и стратегию
6 УСиМ, 2009, № 1
( ) ( )arg min ,B
q Q
q m R q m
∈
= , которую назовем бай-
есовской стратегией для модели m. Величина
( )( ),n nR q L m – это риск, который на модели m
достигается распознающей системой после ее
обучения на обучающей выборке nL . В силу
случайного характера выборки nL риск
( )( ),n nR q L m также будет случайным. Его ма-
тематическое ожидание по всем выборкам
n nL ∈Λ обозначим
( ) ( ) ( )( )
( ) ( )( )
1
, ; ,
, ; , .
n n
n n
n n n n n
L
n
n n
i i
iL
R q m p L m R q L m
p x k m R q L m
∈Λ
=∈Λ
= ⋅ =
= ⋅
∑
∑ ∏
(1)
Задача обучения в распознавании образов в
ее неформальном понимании состоит в том,
чтобы для заданного числа n и заданных
функций :p X K M R× × → и :w K K R× →
построить удовлетворительную в определен-
ном смысле стратегию nq обучения или, что то
же самое, стратегию nq обучения-распозна-
вания. Однако качество искомой стратегии оп-
ределяется не одним числом, а совокупностью
чисел Rn(qn, m), m ∈ M.
Современные исследования проблемы обу-
чения состоят совсем не в конкретизации
приведенной формулировки и получении про-
цедур обучения-распознавания как решения
конкретно сформулированной задачи, а в фик-
сировании некоторых общепризнанных про-
цедур обучения и последующем анализе си-
туаций, когда они оказываются особенно пло-
хими. Укажем наиболее известные такие про-
цедуры.
Известные подходы к распознаванию при
не полностью определенной модели распо-
знаваемого объекта
Минимаксная стратегия
Потребуем, чтобы стратегия распознавания
q обеспечивала удовлетворительное качество
распознавания для любой модели m из задан-
ного класса M, т.е. чтобы
( ){ ,R q m c≤ , m M∈ . (2)
При малых значениях величины c требова-
ния (2) могут оказаться противоречивыми. Поэ-
тому сформулируем задачу отыскания мини-
мального значения c, при котором требования
(2) еще выполнимы. Пусть это минимальное
значение равно с∗. Тогда стратегию q∗, удовле-
творяющую требованиям ( ){ , ,R q m c∗ ∗≤ m ∈ M
назовем минимаксной стратегией распознава-
ния на множестве M моделей. Поскольку зада-
ча построения минимаксной стратегии сфор-
мулирована для случая отсутствия обучающей
выборки, для некоторых классов моделей га-
рантированный уровень c∗ может оказаться
слишком плохим. Само по себе это не является
недостатком минимаксных стратегий, потому
что для некоторых моделей даже байесовский
риск может оказаться неприемлемо большим.
Существенный изъян минимаксного подхода
состоит в том, что минимаксные стратегии рас-
познавания без обучения не допускают разум-
ного обобщения на минимаксные стратегии
обучения. А именно, наилучший в минимакс-
ном смысле алгоритм обучения – это алго-
ритм, который обучающую выборку игнори-
рует. Далее подробно рассмотрим этот суще-
ственный недостаток минимаксного подхода.
Наиболее правдоподобное оценивание
модели
Пусть для каждой обучающей выборки
( )1 1 2 2, ; , ; , ,n
n nL x k x k x k= … определена наибо-
лее правдоподобная модель
( ) ( )
1
arg max , ;
n
n
i im M i
m L p x k m∗
∈
=
= ∏ ,
а для каждой модели m M∈ определена байе-
совская стратегия ( ) ( )arg min ,B
q Q
q m R q m
∈
= .
Стратегия обучения :n nq QΛ → определена
так, что
( ) ( )( )n n B nq L q m L∗= , n nL ∈Λ . (3)
Стратегии такого вида глубоко укоренились в
теории и практике распознавания. Именно в
силу того, что они хорошо исследованы, об-
УСиМ, 2009, № 1 7
щеизвестны их недостатки, обозначаемые крат-
ко, как проблема коротких выборок. Покажем
их на простом примере в следующем разделе.
Несмотря на эти известные недостатки, страте-
гия обучения (3) показала свою плодотвор-
ность в таких практических задачах, в которых
возможны достаточно длинные обучающие
выборки. Следует отметить также, что для
многих классов моделей как отыскание на-
иболее правдоподобной модели m∗(Ln), так и
построение байесовской стратегии qB(m) ока-
зывается далеко не тривиальной задачей, пред-
ставляющей самостоятельный интерес.
Минимизация эмпирического риска
Пусть Q(M) = {qB(m) ⎢m ∈ M} ⊂ Q – множе-
ство байесовских стратегий для моделей из
класса M, а ( ) ( ) ( )
1
, / ,
n
n
i i
i k K
R q L q k x W k k∋
= ∈
= ⋅∑∑ –
так называемый эмпирический риск стратегии
:q X K R× → на обучающей выборке Ln =
( )1 1 2 2, ; , ; , ,n nx k x k x k= … . Стратегия :n nq QΛ →
определена как
( )
( )
( )arg min ,n n n
q Q M
q L R q L∋
∈
= , n nL ∈Λ .
Наряду с методом наибольшего правдопо-
добия минимизация эмпирического риска яв-
ляется одним из наиболее популярных методов
обучения. Критический анализ этого подхода к
обучению в распознавании выполнен в [1].
Иллюстрация введенных понятий и из-
вестных подходов
Пусть X – множество вещественных чисел,
K = {1, 2} а p(x/k), k = 1, 2, – распределение
плотности условной вероятности, определен-
ное как
( ) ( )21 μ
21/
2π
kx
p x k e
− −
= , 1, 2k = , 1μ 1= , 2μ 1= − .
Пусть pk, k = 1, 2, – априорная вероятность
состояния k. Вероятности p1 и p2 неизвестны, и
пара (p1, p2) – неизвестная модель m объекта,
так что ( ) ( ), ; /kp x k m p p x k= ⋅ .
Таким образом, в данном примере статисти-
ческая модель распознаваемого объекта почти
полностью известна. Неизвестны только апри-
орные вероятности пребывания объекта в пер-
вом или втором состояниях. Этот специально
упрощенный пример предназначен для пре-
дельно ясной иллюстрации введенных фор-
мальных понятий, недостатков метода наи-
большего правдоподобия и сущности пред-
лагаемого далее подхода к обучению в распо-
знавании.
Пусть потери равны
( ), 1w k k′ = , если k k′≠ , ( ), 0w k k′ = , если k k′= .
Байесовская стратегия :q X K R× → для
модели m = (p1, p2) имеет вид
( )1/ 1q k x= = , если ( ) ( )1 2/1 / 2p p x p p x⋅ > ⋅ ,
( )2 / 1q k x= = , если ( ) ( )1 2/1 / 2p p x p p x⋅ < ⋅ .
На рис. 1 показана зависимость риска раз-
личных стратегий от модели m, в данном слу-
чае, от вероятности p1 первого состояния. Риск
RB(m) байесовской стратегии представлен
сплошной линией.
Рис. 1. Зависимость вероятности ошибочного распознавания от
априорных вероятностей состояний для различных стра-
тегий
Минимаксная стратегия q′(x) : X × K → R име-
ет вид
( )1/ 1q k x′ = = , если 0x > ,
( )2 / 1q k x′ = = , если 0x < .
Риск R(q′, m) для этой стратегии показан в
виде штрихпунктирной линии.
Пусть nL – обучающая выборка длины n > 0.
Наиболее правдоподобная модель ( )nm L∗ или,
8 УСиМ, 2009, № 1
что то же самое, наиболее правдоподобные зна-
чения 1 2,p p∗ ∗ априорных вероятностей равны
( ) ( ) 1 2
1 2, ,n n nm L p p
n n
∗ ∗ ∗ ⎛ ⎞= = ⎜ ⎟
⎝ ⎠
, где kn , 1, 2k = , –
количество элементов i в выборке nL , для ко-
торых ik k= . Стратегия :n nq X K RΛ × × → в
этом случае имеет вид
( )1/ , 1n nq k L x= = , если ( ) ( )1 2/1 / 2n p x n p x⋅ > ⋅ ,
( )2 / , 1n nq k L x= = , если ( ) ( )1 2/1 / 2n p x n p x⋅ < ⋅ .
Риск ( ),n nR q m этой стратегии зависит от
длины n выборки и для значений n, равных 1, 2
или 3, приведен на рис. 1 в виде пунктирной
линии. Очевидно, что при больших значениях
длины выборки риск ( ),n nR q m становится не-
отличимым от байесовского риска R
B(m). Од-
нако, как видно из рис. 1, при значениях длины
n, равных 1, 2 или 3, риск ( ),n nR q m заметно
отличается от байесовского. Существенно, что
риск ( ),n nR q m отличается в худшую сторону
и от риска минимаксной стратегии, которая
обучающую выборку просто игнорирует. Сле-
довательно, метод наибольшего правдоподо-
бия неэффективно использует информацию,
содержащуюся в обучающейся выборке, пото-
му что ее использование приводит к результа-
там, худшим, чем ее игнорирование.
В следующем разделе исследуется вопрос о
том, можно ли построить минимаксные страте-
гии обучения-распознавания так, чтобы исполь-
зование коротких выборок пусть незначитель-
но, но улучшало бы результаты в сравнении с
теми, которые получаются в отсутствие обуча-
ющей выборки. На этот вопрос будет получен
отрицательный ответ.
Минимаксные стратегии обучения-распо-
знавания
Сформулируем задачу отыскания такого ми-
нимального значения c, при котором еще не
противоречивы требования ( ){ ,n nR q m c≤ , m∈ M,
к стратегии nq обучения-распознавания.
Учитывая, что для n = 0 стратегия 0 0:q L ×
X K R× × → есть стратегия вида X K R× → и
( ) ( )
( ) ( ) ( )
0 0 , ,
'/ , ; , ,
k K k K
x X
R q m R q m
q k x p x k m w k k
′∈ ∈
∈
= =
′= ⋅∑ ∑
запишем эту задачу для n = 0 в виде следую-
щей пары двойственных задач линейного про-
граммирования.
Прямая задача:
min c (4)
( )
( )
( ) ( ) ( )
( )
( )
, ; , , (5)
;
1, ; (6)
0, ; .
k K k K
x X
k K
q k x p x k m w k k cm
m M
q k x x Xt x
q k x x X k K
′∈ ∈
∈
′∈
′ ′⋅ ≤τ
∈
′ = ∈
′ ′≥ ∈ ∈
∑ ∑
∑
Двойственная задача
( )max
x X
t x
∈
∑ (7)
( ) ( ) ( ) ( )
( )
( ) ( )
, ; (8)
/
, , , ;
1; 0, . (9)
k K m M
m M
t x m p x k m
q k x
w k k k K x X
m m x Xc
∈ ∈
∈
⎛ ⎞≤ τ ⋅ ×⎜ ⎟′ ⎝ ⎠
′ ′× ∈ ∈
τ = τ ≥ ∈
∑ ∑
∑
В приведенных формулах слева от каждого
ограничения прямой задачи записана соответ-
ствующая ей двойственная переменная; слева
от каждого ограничения двойственной задачи
записана соответствующая ей переменная в
прямой задаче.
Функцию вида τ : M R→ назовем весовой
функцией со значениями ( )τ m , которые назо-
вем весами. Множество весовых функций, удов-
летворяющих ограничениям ( )τ 1
m M
m
∈
=∑ , τ(m) ≥ 0,
m ∈ M, обозначим T. Определим модель ( )m τ
так, что совместная вероятность x и k в модели
m(τ)определяется выражением
( )( ) ( ) ( ), ; τ τ , ;
m M
p x k m m p x k m
∈
= ⋅∑ . (10)
УСиМ, 2009, № 1 9
Модели этого вида назовем смешанными
моделями в отличие от моделей из первона-
чального класса M, которые будем называть
чистыми. Ранее введенные стратегии qB(m),
m ∈ M, будем называть чистыми в отличие от
стратегий ( )( )arg min , τ
q Q
R q m
∈
, τ T∈ , которые
будем называть смешанными.
Лемма 1. Пусть q∗ и c∗ – решение прямой
задачи (4). В таком случае существует такой
набор τ∗(m), m M∈ , весов моделей, что
( ) ( )( )max , τB
m M
R q m R m∗ ∗
∈
= . (11)
Доказательство. Пусть ( )t x∗ и ( )τ m∗ –
решение двойственной задачи (7). В силу из-
вестной теоремы двойственности [4]
( )
x X
t x c∗ ∗
∈
=∑ . (12)
Выражение в левой части (5) есть риск
( ),R q m∗ , а c∗ – минимальное число, удовле-
творяющее условиям ( ),R q m c∗ ∗≤ , m M∈ .
Следовательно,
( )max ,
m M
c R q m∗ ∗
∈
= . (13)
Учитывая, что по определению (10)
( ) ( ) ( )( )τ , ; , ; τ
m M
m p x k m p x k m
∈
⋅ =∑ ,
запишем ограничение (8) в виде
( ) ( )( ) ( ), ; τ ,
k K
t x p x k m w k k
∈
′≤ ⋅∑ , k K′∈ .
Число ( )t x∗ есть максимальное число, удов-
летворяющее условиям
( ) ( )( ) ( ), ; τ ,
k K
t x p x k m w k k∗ ∗
∈
′≤ ⋅∑ , k K′∈ .
Следовательно,
( ) ( )( ) ( )min , ; τ ,
k K k K
t x p x k m w k k∗ ∗
′∈
∈
′= ⋅∑ ,
что в свою очередь обозначает, что
( ) ( )( )τB
x X
t x R m∗ ∗
∈
=∑ . (14)
Подставляя (13) и (14) в (12), получаем (11).
Таким образом, набор весов τ∗(m), существо-
вание которого требуется доказать, – это веса
τ∗(m), являющиеся решением двойственной за-
дачи (7). Лемма доказана.
Лемма 2. Для любой стратегии qn обучения
и любой модели m ∈ M справедливо неравен-
ство ( ) ( ),n n BR q m R m≥ .
Доказательство. По определению байесов-
ской стратегии неравенство ( )( ) ( ),n n BR q L m R m≥
справедливо для любой выборки n nL ∈Λ . Сле-
довательно, справедливо и неравенство
( ) ( )( ) ( ); ,
n n
n n n B
L
p L m R q L m R m
∈Λ
⋅ ≥∑ .
Левая часть этого неравенства есть Rn(qn, m)
по определению (1). Лемма доказана.
Теорема 1. Если для класса M моделей ре-
шение 0 :q X K R× → минимаксной задачи рас-
познавания (4) есть чистая стратегия, то для
любого 1, 2,n = … и любой стратегии :n nq L Q→
выполняется неравенство
( ) ( )0max , max ,n n
m M m M
R q m R q m
∈ ∈
≥ .
Доказательство. Пусть ( )0 0argmax , .
m M
m R q m
∈
=
В таком случае ( )max ,n n
m M
R q m
∈
≥ ( )0,n nR q m ≥
( ) ( )0 0max , .B
m M
R m R q m
∈
≥ =
Первое неравенство в этой цепочке очевид-
но. Второе – справедливо в силу леммы 2. В си-
лу предположения о том, что стратегия q0 – чис-
тая, и в силу леммы 1 справедливо равенство в
третьем звене цепочки. Теорема доказана.
Поскольку данная теорема представляет до-
статочно существенный отрицательный резуль-
тат, рассмотрим несколько примеров классов
моделей, где минимаксная стратегия распозна-
вания оказывается чистой.
1. Минимаксная стратегия оказывается чис-
той, конечно, в том случае, когда множество
смешанных моделей совпадает с множеством
чистых моделей. Эта ситуация, в частности,
имеет место в приведенном примере, когда
модель распознаваемого объекта почти полно-
стью известна, а неизвестны только априорные
вероятности состояний.
10 УСиМ, 2009, № 1
2. Пусть K ∈ {1, 2} – множество состояний
объекта, а x – многомерная гауссова случайная
величина с единичной ковариационной матри-
цей. Условное математическое ожидание этого
вектора при условии, что объект находится в
состоянии k, есть μ k. Математические ожида-
ния μ1 и μ2 неизвестны. Известны, однако, два
выпуклых множества M1 и M2, которым они
принадлежат. Множество чистых моделей в
этом случае есть M1 × M2 и оно, конечно, не
равно множеству смешанных моделей. Тем не
менее минимаксная стратегия распознавания –
чистая.
3. Для теории и практики распознавания
обычна ситуация, когда функции pk : X → R,
k ∈ K, со значениями p(x / k) неизвестны, но из-
вестно лишь, что все они входят в заданный
класс P функций, один и тот же для всех k ∈ K.
В этом случае минимаксная стратегия распо-
знавания также чистая. Эта наилучшая в ми-
нимаксном смысле стратегия оказывается со-
всем плохой. Она гарантирует лишь, что веро-
ятность ошибочного распознавания не пре-
восходит 50% для любой модели. Однако в силу
того, что эта стратегия чистая, вступает в силу
вывод доказанной теоремы, что никакая стра-
тегия обучения этот показатель не может
улучшить.
Исходя из указанного существенного изъя-
на минимаксного критерия обучения-распоз-
навания и общеизвестных недостатков макси-
мально правдоподобного оценивания модели,
приходим к выводу, что проблема распознава-
ния при не полностью известной статистиче-
ской модели исследована в весьма незначи-
тельной части. Известные и широко приме-
няемые методы охватывают лишь два крайних
ее случая: когда имеется обучающая выборка
неограниченно большой длины и когда обуча-
ющей выборки нет вообще. Желательно сфор-
мулировать задачу обучения-распознавания так,
чтобы риск распознавания при короткой обу-
чающей выборке оказывался хоть ненамного,
но лучше, чем риск распознавания без учета
этой выборки. Кроме того, необходимо, чтобы
при неограниченном увеличении длины вы-
борки качество распознавания становилось не-
отличимым от байесовского.
Общий вид стратегий обучения-распозна-
вания
Задача обучения состоит в выборе страте-
гии nq , оптимальной в определенном смысле,
из множества всех возможных стратегий вида
:n nq L X K R× × → . Эта задача допускает мно-
жество точных формулировок в зависимости
от того, как определено качество стратегии, ко-
торое следует оптимизировать. При этом следу-
ет учесть, что совокупность ( ),n nR q m , m ∈ M,
рисков позволяет задать на множестве всех воз-
можных стратегий вида :n nq L X K R× × → ес-
тественное отношение частичной упорядочен-
ности. А именно, стратегия 1
nq не хуже стра-
тегии 2
nq на классе моделей M, если для всех
моделей m ∈ M выполняется неравенство
( ) ( )1 2, ,n n n nR q m R q m≤ , а стратегия 2
nq во всех
отношениях хуже стратегии 1
nq , если указан-
ные неравенства выполняются строго. Форму-
лировка задачи обучения должна быть разум-
ной в том смысле, что ее решение не должно
оказаться стратегией, которая во всех отноше-
ниях хуже некоторой другой стратегии. На ос-
новании этих соображений можно априори су-
зить множество стратегий обучения-распо-
знавания еще до формулировки задачи обуче-
ния, требуя лишь, чтобы эта формулировка
была разумной в указанном выше смысле.
Для заданной весовой функции τ определим
стратегию обучения-распознавания так, что
( )/ , 1n nq k L x′ = , если для всех k k′′ ′≠ выполня-
ется неравенство
( ) ( ) ( ) ( )τ ; , ; ,n
k K m M
m p L m p x k m w k k
∈ ∈
⎛ ⎞ ′⋅ ⋅ ⋅ <⎜ ⎟
⎝ ⎠
∑ ∑
( ) ( ) ( ) ( )τ ; , ; ,n
k K m M
m p L m p x k m w k k
∈ ∈
⎛ ⎞ ′′< ⋅ ⋅ ⋅⎜ ⎟
⎝ ⎠
∑ ∑ .
Стратегию такого вида назовем байесовской
для весовой функции τ. Иными словами, при
обучающей выборке nL и наблюдении x байе-
УСиМ, 2009, № 1 11
совская стратегия принимает решение в пользу
состояния k∗,
( ) ( ) ( )
( )
arg min τ ; , ;
, .
n
k K k K m M
k m p L m p x k m
w k k
∗
′∈
∈ ∈
⎛ ⎞= ⋅ ⋅ ×⎜ ⎟
⎝ ⎠
′×
∑ ∑
При фиксированном классе M моделей бай-
есовская стратегия может быть той или иной в
зависимости от весовой функции τ. Докажем,
что решение любой разумно поставленной за-
дачи обучения – это байесовская стратегия для
некоторой весовой функции τ : M R→ .
Теорема 2. Для любой стратегии :n nq L∗ ×
X K R× × → обучения-распознавания существу-
ет байесовская стратегия :n nq L X K R× × → ,
для которой неравенство ( ) ( ), ,n n n nR q m R q m∗≤
выполняется для любой модели m M∈ .
Доказательство. Представим искомую стра-
тегию nq как решение следующей задачи ли-
нейного программирования:
min c
( )
( )
( ) ( )
( ) ( ) ( )
( )
( )
; / ,
, ; , , , (15)
;
, / , 1, , , (16)
/ , 0, , , ,
n n
n n n
x X k KL
n n
k K
n n n n n
k K
n n n n
m c p L m q k L x
p x k m w k k R q m
m M
t L x q k L x x X L
q k L x k K L x X
′∈ ∈∈Λ
∗
∈
′∈
′τ − ×
′× ⋅ ≥ −
∈
′ = ∈ ∈Λ
′ ′≥ ∈ ∈Λ ∈
∑ ∑∑
∑
∑
которой соответствует двойственная задача
( ) ( ) ( )max , τ ,
n n
n n n
x X m ML
t L x m R q m∗
∈ ∈∈Λ
⎡ ⎤
− ⋅⎢ ⎥
⎣ ⎦
∑ ∑ ∑
( ) ( ) ( )
( ) ( ))
( )
( ) ( )
, τ/ ,
; , ;
, , , , ;
τ 1; 0, .
nn n
k K m M
n
n n
m M
t L x mq k L x
p L m p x k m
w k k k K L x X
m m m Mc
∈ ∈
∈
⎛≤ ×′ ⎜
⎝
× ⋅ ×
′ ′× ∈ ∈Λ ∈
= τ ≥ ∈
∑ ∑
∑
(17)
Как и ранее, слева от уравнений-ограниче-
ний задач записаны соответствующие им двой-
ственные переменные.
Система линейных ограничений прямой за-
дачи не противоречива, так как ей удовлетво-
ряют значение c = 0 и значения ( )/ ,n nq k L x′ =
( )/ ,n nq k L x∗ ′= , k K′∈ , n nL ∈Λ , x X∈ . Нетруд-
но также увидеть, что величина c ограничена
снизу на множестве решений этой системы.
Отсюда, в силу известных теорем двойствен-
ности, следует, что ограничения в задаче (17)
также непротиворечивы, а целевая функция в
этой задаче ограничена сверху.
Пусть 0 :n nq L K X R× × → , 0c – решение
прямой задачи, а ( )0 ,nt L x , n nL ∈Λ , x X∈ , и
τ0(m), m∈ M – решение двойственной. Пусть
для некоторой тройки 0k K∈ , 0
n nL ∈Λ , 0x X∈
неравенство
( ) ( ) ( ) ( )0 0 0 0; , ; ,n
k K m M
m p L m p x k m w k k
∈ ∈
⎛ ⎞τ ⋅ ⋅ ⋅ <⎜ ⎟
⎝ ⎠
∑ ∑
( ) ( ) ( ) ( )0 0 0; , ; ,n
k K m M
m p L m p x k m w k k
∈ ∈
⎛ ⎞ ′< τ ⋅ ⋅ ⋅⎜ ⎟
⎝ ⎠
∑ ∑
выполняется для всех 0k k′ ≠ . Это значит, что
неравенство (17) выполняется строго для дан-
ных 0 0,nL x и всех 0k k′ ≠ . Отсюда, в силу из-
вестной теоремы двойственности, равенство
( )0 0 0/ , 0n nq k L x′ = выполняется для всех 0k k′ ≠ .
В свою очередь, в силу (16) отсюда следует,
что ( )0 0 0 0/ , 1n nq k L x = .
Таким образом, стратегия 0
nq является байе-
совской для весовой функции 0τ .
Поскольку значение c = 0 достигается на
множестве допустимых решений системы ог-
раничений прямой задачи, то 0 0c ≤ . Отсюда, в
силу неравенств (15), следует, что неравенство
( ) ( ) ( )
( ) ( )
0; / , , ;
, ,
n n
n n n
x X k K k KL
n n
p L m q k L x p x k m
w k k R q m
′∈ ∈ ∈∈Λ
∗
′ ×
′× ≤
∑ ∑∑ ∑
12 УСиМ, 2009, № 1
выполняется для всех m M∈ . Выражение в ле-
вой части этого неравенства есть ( )0 ,n nR q m и
( ) ( )0 , ,n n n nR q m R q m∗≤ , m M∈ . Теорема дока-
зана.
Таким образом, решение любой разумно по-
ставленной задачи обучения существенно от-
личается от общепринятых стратегий, указан-
ных ранее. В решении разумно поставленной
задачи отсутствует такой этап, как выбор од-
ной-единственной модели на основании обу-
чающей выборки, пусть даже наиболее прав-
доподобной модели или модели с минималь-
ным эмпирическим риском. В распознавании
после обучения учитываются все модели из
заданного класса, но с различными весами в
зависимости от того, насколько та или иная
модель согласуется с обучающей выборкой.
Одна из возможных формулировок зада-
чи обучения-распознавания и ее формаль-
ные свойства
Риск R
n(qn, m) зависит не только от стратегии
qn, но и от модели m. Для некоторых моделей
m даже байесовский риск RB(m) может ока-
заться неприемлемо большим. Поэтому ха-
рактеристикой собственно стратегии qn естест-
венно считать не столько величину R
n(qn, m),
сколько ее отклонение R
n(qn, m) – R
B(m) от бай-
есовского риска RB(m), который характеризует
собственно модель m, вне ее связи со стратеги-
ей qn. Именно исходя из разности R
n(qn, m) ––
R
B(m) исследуются отдельные процедуры обу-
чения в работах [2, 3] и других. Качеством же
стратегии qn безотносительно модели m при-
мем величину ( )max ,n n
m
R q m⎡ −⎣ ( )BR m ⎤⎦ и
сформулируем задачу обучения, как поиск стра-
тегии q∗n с наилучшим качеством, т.е.
( ) ( )arg min max ,
n
n n n B
mq
q R q m R m∗ ⎡ ⎤= −⎣ ⎦ . (18)
Теорема 3. Искомая стратегия nq∗ есть бай-
есовская стратегия для смешанной модели с
весовой функцией
( )( ) ( ) ( )τ arg max min , τ τ .
n
n n B
T q T
R q m m R m
τ τ
∗
∈
∈
⎡ ⎤= −⎢ ⎥⎣ ⎦
∑
Доказательство. Запишем искомую страте-
гию как решение следующей задачи линейного
программирования.
Прямая задача
min c
( ) ( )
( ) ( )
( ) ( )
( )
( )
/ ,
; , ;
, , ;
( , ) / , 1; , ;
/ , 0, , , .
n n
n n
x X k KL
n
k K
B
n n n n n
k K
n n n n
q k L xm
p L m p x k m
w k k R m c m M
t L x q k L x L x X
q k L x k K L x X
′∈ ∈∈Λ
∈
′∈
′ ×τ
× ×
′× − ≤ ∈
′ = ∈Λ ∈
′ ′≥ > ∈Λ ∈
∑ ∑∑
∑
∑
(19)
Переменными в этой задаче являются числа
( )/ ,n nq k L x′ , k K′∈ , n nL ∈Λ , x X∈ , и число c.
Задаче соответствует двойственная задача с
двойственными переменными ( )τ m , m M∈ , и
( ),nt L x , n nL ∈Λ , x X∈ .
Двойственная задача
( ) ( ) ( )max , τ
n n
n B
x X m ML
t L x m R m
∈ ∈∈Λ
⎡ ⎤
− ⋅⎢ ⎥
⎣ ⎦
∑ ∑ ∑
( ) ( ) ( )
( ) ( )) ( )
( ) ( )
, τ/ ,
; , ; , ,
, , ;
1; 0, .
nn n
k K m M
n
n n
m M
t L x mq k L x
p L m p x k m w k k
k K L m M
m m m Mc
∈ ∈
∈
⎛′ ≤ ×⎜
⎝
′× × ×
′∈ ∈Λ ∈
τ = τ ≥ ∈
∑ ∑
∑
Слева от ограничений прямой (или двой-
ственной) задачи записаны соответствующие
им переменные двойственной (или прямой)
задачи.
Пусть c∗ и nq∗ – решение прямой задачи, а
( ),nt L x∗ , n nL ∈Λ , x X∈ и ( )τ m∗ , m M∈ , –
решение двойственной. Пусть 0
nL , 0x , 0k – та-
кие значения, что для любого 0k k′ ≠ выполня-
ется строгое неравенство
УСиМ, 2009, № 1 13
( ) ( ) ( ) ( )0 0 0τ ; , ; ,n
k K m M
m p L m p x k m w k k∗
∈ ∈
⎛ ⎞⋅ ⋅ ⋅ <⎜ ⎟
⎝ ⎠
∑ ∑
( ) ( ) ( ) ( )0 0τ ; , ; ,n
k K m M
m p L m p x k m w k k∗
∈ ∈
⎛ ⎞ ′< ⋅ ⋅ ⋅⎜ ⎟
⎝ ⎠
∑ ∑ .
Отсюда немедленно следует, что и неравен-
ство
( )
( ) ( ) ( ) ( )
0
0 0
,
τ ; , ; ,
n
n
k K m M
t L x
m p L m p x k m w k k
∗ ∗
∗
∈ ∈
<
⎛ ⎞ ′< ⋅ ⋅ ⋅⎜ ⎟
⎝ ⎠
∑ ∑
также выполняется строго для всех k′ ≠ ko. От-
сюда, в силу известной теоремы двойственно-
сти о дополняющей жесткости, следует, что
( )0 0 0/ , 1n nq k L x∗ = , т.е., что искомая стратегия
есть байесовская стратегия для весовой функ-
ции τ∗, являющейся решением двойственной
задачи. Докажем теперь, что решение τ∗ двой-
ственной задачи совпадает с весовой функци-
ей, обеспечивающей максимальное значение
числа ( )( ) ( ) ( )min , τ τ
n
n n B
q m M
R q m m R m
∈
− ⋅∑ , как
это формулируется в теореме.
Риск ( )( ),n nR q m τ есть по определению
( )( ) ( )
( ) ( ) ( ) ( )
, ,
; , ; , .
n n
n n n n
k K x X L
n
k K m M
R q m q k L x
m p L m p x k m w k k
′∈ ∈ ∈Λ
∈ ∈
′τ = ×
⎛ ⎞ ′× τ ⋅ ⋅ ⋅⎜ ⎟
⎝ ⎠
∑ ∑ ∑
∑ ∑
Поскольку все числа ( ),n nq k L x′ не отри-
цательные, причем для любых n nL ∈Λ , x X∈
должно выполняться ( )/ , 1n n
k K
q k L x
′∈
′ =∑ , то
( )( )
( ) ( ) ( )
( )
min ,
min ; , ;
, .
n
n n
n n
q
n
k Kx X k K m ML
R q m
m p L m p x k m
w k k
′∈
∈ ∈ ∈∈Λ
τ =
⎛ ⎞= τ ⋅ ⋅ ×⎜ ⎟
⎝ ⎠
′×
∑ ∑ ∑ ∑
Поскольку в двойственной задаче величины
( ),nt L x должны принимать как можно большие
значения, то их можно однозначно определить
через весовые коэффициенты ( )mτ , так что
( )
( ) ( ) ( ) ( )
,
min ; , ; ,
n
n
k k K m M
t L x
m p L m p x k m w k k
′
∈ ∈
=
⎛ ⎞ ′= τ ⋅ ⋅⎜ ⎟
⎝ ⎠
∑ ∑
и
( ) ( ) ( )
( )( ) ( ) ( )
,
min , .
n n
n
n B
x X m ML
n n B
q m M
t L x m R m
R q m m R m
∈ ∈∈Λ
∈
− τ ⋅ =
= τ − τ
∑ ∑ ∑
∑
.
Теорема доказана.
Поиск оптимальной стратегии обучения-рас-
познавания сводится, таким образом, к отыска-
нию весовой функции : M Rτ → , обеспечи-
вающей максимальное значение числа
( ) ( )( ) ( ) ( )min ,
n
n n B
q m M
F R q m m R m
∈
τ = τ − τ∑ . (20)
Эта задача – задача выпуклой оптимизации,
как утверждает следующая теорема.
Теорема 4. Для любого класса M моделей
функция ( )F τ является вогнутой функцией.
Доказательство. Докажем, что для любой
весовой функции 0 Tτ ∈ существует линейная
функция
0
:L T Rτ → , такая, что неравенство
( ) ( ) ( )
0 0 0L F Fτ τ − τ ≥ τ − τ (21)
выполняется для всех Tτ∈ .
Пусть 0
nq – стратегия, обеспечивающая ми-
нимальный риск ( )( )0,n nR q m τ .
( )( ) ( )( )0 0 0, min ,
n
n n n n
q
R q m R q mτ = τ . (22)
Определим линейную функцию ( )
0
Lτ τ как
( ) ( ) ( ) ( )
0 0 ,n n B
m M
L m R q m R mτ
∈
⎡ ⎤τ = τ −⎣ ⎦∑ . (23)
Справедлива следующая цепочка:
( ) ( ) ( ) ( )
( ) ( ) ( )
0 0 0
0 0
,
,
n n B
m M
n n B
m M
L m R q m R m
m R q m R m
τ
∈
∈
⎡ ⎤τ − τ = τ − −⎣ ⎦
⎡ ⎤− τ − ≥⎣ ⎦
∑
∑
( ) ( ) ( )
( ) ( ) ( )0 0
min ,
,
n
n n B
q m M
n n B
m M
m R q m R m
m R q m R m
∈
∈
⎡ ⎤≥ τ − −⎣ ⎦
⎡ ⎤− τ − =⎣ ⎦
∑
∑
14 УСиМ, 2009, № 1
( ) ( ) ( )
( ) ( ) ( )0
min ,
min ,
n
n
n n B
q m M
n n B
q m M
m R q m R m
m R q m R m
∈
∈
⎡ ⎤= τ − −⎣ ⎦
⎡ ⎤− τ − =⎣ ⎦
∑
∑
= F(τ) – F(τ0).
Равенство в первом звене следует из (23).
Неравенство во втором звене очевидно. Равен-
ство в третьем звене следует из (22). Наконец,
последнее равенство следует из определения
(20). Таким образом, линейная функция (23)
есть искомая линейная функция, доказывающая
вогнутость функции F(τ). Теорема доказана.
В приведенном доказательстве получен вспо-
могательный результат: обобщенный градиент
0
gτ функции F(τ)в точке 0τ есть M -мерный
вектор с компонентами ( ) ( )0 ,n n BR q m R m− . Это
указывает пути отыскания весовой функции, а
следовательно, и стратегии обучения методом
обобщенных градиентов. В экспериментах,
приводимых далее, использован другой, теоре-
тически не обоснованный алгоритм.
Алгоритм работает по шагам i = 1, 2, … , и на
каждом шаге строит стратегию обучения n
iq и
весовую функцию ( )( )i i m m Mτ = τ ∈ .
Исходными для алгоритма являются конеч-
ное множество M моделей и число 0ε > – тре-
буемая точность решения задачи.
1. Для каждой модели m определить целое
число n(m) = 1.
2. Для каждой модели m ∈ M определить ее
вес ( ) ( )
( )
m M
n m
m
n m
∈
τ =
∑
.
3. Построить байесову стратегию обучения-
распознавания qn для весов τ(m).
4. Для каждой модели m ∈ M определить
число Rn(qn, m) – качество текущей стратегии
на модели m.
5. Найти гарантированное качество текущей
стратегии ( ) ( ) ( )max ,n n n n B
m
R q R q m R m⎡ ⎤= −⎣ ⎦ и
наихудшую модель
( ) ( )arg max , .n n B
m
m R q m R m∗ ⎡ ⎤= −⎣ ⎦
6. Выполнить ( )n m∗ + + .
7. Найти среднее качество
( ) ( ) ( ) ( ),n n n n B
m M
R q m R q m R m
∈
⎡ ⎤= τ −⎣ ⎦∑ .
8. Найти наилучший во всей предыстории
алгоритма гарантированный уровень minR =
( )( )minmin , n nR R q= и наилучшую во всей пре-
дыстории стратегию 0
nq .
9. Найти наихудшее во всей предыстории
среднее качество ( )( )max maxmax , n nR R R q= .
10. Если min maxR R− ≤ ε , останов.
11. Перейти на п. 3.
В настоящее время теоретически не доказа-
но, хотя экспериментально и подтверждается,
что приведенный алгоритм непременно выхо-
дит на останов при любой требуемой точности
0ε > . Однако, если он вышел на останов, то
его результатом является стратегия 0
nq , реша-
ющая задачу обучения с заданной точностью ε
в том смысле, что
( ) ( )
( ) ( )
0max ,
max , ,
n n B
m M
n n B
m M
R q m R m
R q m R m
∈
∗
∈
⎡ ⎤− −⎣ ⎦
⎡ ⎤− − ≤ ε⎣ ⎦
где nq∗ – решение задачи обучения (18) или,
что то же самое, задачи (19).
Иллюстрация метода обучения-распозна-
вания
Покажем, как предложенный метод обуче-
ния-распознавания реализуется для простейшего
класса моделей, описанного выше. В этом
классе наблюдение x есть одномерная вещест-
венная величина, K = {1, 2}, условные распре-
деления p (x / k) полностью известны и равны
( ) ( )21
21/ ,
2
kx
p x k e
− −μ
=
π
1, 2k = , 1 1μ = , 2 1μ =− .
Неизвестными являются только априорные
вероятности p1 и p2 состояний 1k = и 2k = .
Одна конкретная модель m, таким образом,
есть пара ( p1, p2 ). Поскольку в рассматривае-
мом примере условные распределения p (x / k)
полностью известны, нет необходимости рас-
УСиМ, 2009, № 1 15
сматривать обучающие последовательности ви-
да ( )1 1 2 2, ; , ; ; ,n
n nL x k x k x k= … , а достаточно рас-
сматривать обучающие последовательности ви-
да ( )1 2, , ,n n n
nL k k k K= ∈Λ =… .
Для специального вида потерь ( ),w k k′ =
k k′= − , исходя из теоремы 3, стратегия обу-
чения-распознавания должна иметь вид
1 1,n
kq L x
⎛ ⎞′ = =⎜ ⎟
⎝ ⎠
,
если ( ) 1
1
i
n
k
m M i
m p p
∈ =
⎛ ⎞
τ ⋅ ⋅⎜ ⎟
⎝ ⎠
∑ ∏ ( )1
xp >
( ) ( )2
1
;2i
n
k
m M i
xm p p p
∈ =
⎛ ⎞
> τ ⋅ ⋅⎜ ⎟
⎝ ⎠
∑ ∏
2 1,n
kq L x
⎛ ⎞′ = =⎜ ⎟
⎝ ⎠
,
если ( ) ( )1
1
/1
i
n
k
m M i
m p p p x
∈ =
⎛ ⎞
τ ⋅ ⋅ <⎜ ⎟
⎝ ⎠
∑ ∏
( )1 1
xp p⋅ ( ) ( )2
1
/ 2 .
i
n
k
m M i
m p p p x
∈ =
⎛ ⎞
< τ ⋅ ⋅⎜ ⎟
⎝ ⎠
∑ ∏
В этих выражениях для краткости не указа-
но, что величины p1 и p2 и, вообще,
ikp ,
1, 2, ,i n= … , зависят от модели m. Указанную
стратегию можно представить в более нагляд-
ном виде
1k∗ = , если ( )
( ) ( )1 2
/1
, ,
/ 2
p x
n n
p x
> θ τ ;
2k∗ = , если ( )
( ) ( )1 2
/1
, ,
/ 2
p x
n n
p x
< θ τ ,
где k∗ – решение о состоянии k по наблюдению
x и обучающей последовательности. Числа n1 и
n2 обозначают, сколько раз в обучающей по-
следовательности Ln встретилась ситуация, ко-
гда 1ik = и 2ik = . Решение о состоянии объ-
екта принимается на основании сравнения от-
ношения правдоподобия p(x/1) / p(x/2) с поро-
гом, зависящим от обучающей выборки. Одна-
ко значение этого порога определяется как
( )
( )
( )
1 2
1 2
1
1 2
1 2 1
1 2
, ,
n n
m M
n n
m M
m p p
n n
m p p
+
∈
+
∈
τ ⋅
θ τ =
τ ⋅
∑
∑
, (24)
а совсем не так просто и грубо,
( ) 1
1 2
2
, , nn n
n
θ τ = , (25)
как в методе наиболее правдоподобных моде-
лей. По-видимому, стратегии, основанные на
сравнении с порогами (24) и (25), становятся
неотличимыми при неограниченном росте обу-
чающей последовательности. Однако при ма-
лых значениях длины, как показали экспери-
менты, это различие существенно.
Описанный в предыдущей главе метод обу-
чения-распознавания включает в себя и оты-
скание значений весов τ (m), m ∈ M. Для реа-
лизации этого метода следует располагать
конструктивным методом вычисления риска
( ),n nR q m , который определен как
( ) ( ) ( )
( ) ( )
, / , ;
, ; , .
n n
n n n n n
x X k KL
k K
R q m q k L n p L n
p x k m w k k
′∈ ∈∈Λ
∈
′= ×
′×
∑ ∑∑
∑
В общем случае наибольшую трудность
здесь представляет суммирование по всем обу-
чающим выборкам Ln ∈ Λn. В рассматривае-
мом примере этот риск равен
( ) ( )( )1 2
11
, , , ,
i
n n
n n
n n
k k k
kiL
R q m p p n n
==∈Λ
⎛ ⎞
= ⋅Φ θ τ⎜ ⎟
⎝ ⎠
∑ ∑∏ (26)
где
( ) ( )21 1
2
1
1
2
x
e
θ
− −
−∞
Φ θ =
π∫ , ( ) ( )21 1
2
2
1
2
x
e
∞
− +
θ
Φ θ =
π∫ .
Представим множество Λn в виде
( )
1 2
1 2
1 2
,
,n
n n
n n n
n n
+ =
Λ = Λ∪ ,
где Λ(n1, n2) – множество всех тех выборок
( )1 2, , , , ,n
i nL k k k k= … … длины n1 + n2, в которых
событие ki = 1 произошло n1 раз, а событие
ki = 2– n2 раз. С учетом этого обозначения вы-
ражение для риска ( ),n nR q m приобретает вид
16 УСиМ, 2009, № 1
( ) ( )( )1 2
2
1 2 1 2
1
, , ,
n n
n nn n
k k
kL
R q m p p p n n
=∈Λ
= ⋅ ⋅Φ θ τ =∑ ∑
( )
( )( )1 2
1 2 1 2
1 2
2
1 2 1 2
, 1,
, ,
n
n n
k k
n n kL n n
n n n
p p p n n
=∈Λ
+ =
= ⋅ ⋅Φ θ τ =∑ ∑ ∑
( )( )
( )
1 2
1 2 1 2
1 2
2
1 2 1 2
, 1 ,
, , 1
n
n n
k k
n n k L n n
n n n
p p p n n
= ∈Λ
+ =
= ⋅ ⋅Φ θ τ =∑ ∑ ∑
( )( )1 1 2
1 2
1 2
1
1 2 1 1 2
,
, ,n n n
n
n n
n n n
C p p n n+
+ =
= ⋅ ⋅ ⋅Φ θ τ +∑
( )( )1 1 2
1 2
1 2
1
1 2 2 1 2
,
, , ,n n n
n
n n
n n n
C p p n n+
+ =
+ ⋅ ⋅ ⋅Φ θ τ∑
и его вычисление перестает быть проблема-
тичным.
На рис. 2–7 показана зависимость риска раз-
личных стратегий от модели m, в данном слу-
чае, от вероятности p1 первого состояния. Бай-
есовский риск RB(m) показан сплошной лини-
ей, риск стратегии по методу наибольшего
правдоподобия показан пунктирной линией, а
риск стратегии по предлагаемому методу –
жирной пунктирной линией. Рис. 2–7 соответ-
ствуют различным значениями длины n обу-
чающих выборок: 1, 2, 3, 10, 20 и 50.
Расчет весов τ (m), m ∈ M, выполнялся в со-
ответствии с алгоритмом, описанным в преды-
дущем разделе.
Заключение. Результаты данной статьи из-
ложены на определенном уровне общности,
Рис. 2. Вероятности ошибочного распознавания для различных
стратегий при длине обучающей выборки, равной 1
который мог быть и большим, и меньшим. Обо-
значим некоторые возможные обобщения при-
веденных результатов, которые уместно рас-
смотреть в данной статье.
Рис. 3. Вероятности ошибочного распознавания для различных
стратегий при длине обучающей выборки, равной 2
Рис. 4. Вероятности ошибочного распознавания для различных
стратегий при длине обучающей выборки, равной 3
Рис. 5. Вероятности ошибочного распознавания для различных
стратегий при длине обучающей выборки, равной 10
УСиМ, 2009, № 1 17
Обучение и самообучение
Обучающая информация, на основании ко-
торой строится собственно распознавание, со-
всем не обязательно должна быть выборкой ви-
да ( ) ( )1 1 2 2, ; , ; ; , n
n nx k x k x k X K∈ ×… . Это может
быть результат L любого эксперимента над рас-
Рис. 6. Вероятности ошибочного распознавания для различных
стратегий при длине обучающей выборки, равной 20
Рис. 7. Вероятности ошибочного распознавания для различных
стратегий при длине обучающей выборки, равной 50
познаваемым объектом. Важно только, чтобы
этот результат мог считаться случайным и за-
висящим от модели, так, чтобы имела смысл
вероятность p(L; m). Результаты статьи без из-
менения переносятся и на этот более общий
случай. В частности, обучающая информация
может быть выборкой L ( )1 2, , , n
nx x x X= ∈… ,
состоящей только из наблюдаемых при распо-
знавании признаков и не включающей в себя
информацию о скрытых состояниях. Построе-
ние распознающих систем при обучающей ин-
формации такого вида получило название са-
мообучение. Основным методом построения та-
ких систем стало, как и при обучении, макси-
мально правдоподобное оценивание модели на
основании выборки L = (x1, x2, …, xn), для ко-
торого широко применяются алгоритмы [5],
ставшие известными как ЕМ-алгоритмы [6].
Описанный подход вносит коррективы и в
эти известные методы распознавания в режиме
самообучения. Как и в случае обучения, лю-
бые разумные требования к распознаванию в
режиме самообучения приводят к алгоритмам,
в которых отсутствует такой этап, как поиск
наиболее правдоподобной модели на основании
выборки L = (x1, x2, …, xn). Эти коррективы мо-
гут быть существенными, особенно при малых
значениях длины n выборки L.
Здесь возможны и более существенные вы-
воды, которые покажем на примере. Пусть для
заданного класса моделей и обучающей ин-
формации произвольного вида построена стра-
тегия ( ),q k L x обучения-распознавания. Коль
скоро эта стратегия построена, то она предна-
значена не для одноразового применения при
распознавании какого-то одного объекта, а для
распознавания многих объектов. При этом
предполагается, что все эти объекты характе-
ризуются той же моделью m, при которой была
получена обучающая информация L. Пусть те-
перь требуется принять решение о состояниях
k1 и k2 двух объектов по признакам x1 и x2 этих
объектов. В этом случае можно поступить
двумя способами.
Первый способ состоит в применении полу-
ченной стратегии ( ),q k L x к каждому из двух
предъявленных объектов и с вероятностью
( )1 1,q k L x принять решение, что первый объ-
ект находится в состоянии k1, и с вероятностью
( )2 2,q k L x принять решение, что второй объ-
ект находится в состоянии k2.
Второй способ состоит в рассмотрении пары
предъявленных объектов как одного объекта с
18 УСиМ, 2009, № 1
состоянием из множества K × K = {(k1, k2)⎪k1 ∈
∈ K, k2∈ K}, с признаком (x1, x2), который при-
нимает значения из множества X × X, и клас-
сом M моделей m, таких, что
( ) ( ) ( )1 2 1 2 1 1 2 2, , , ; , ; , ; .p x x k k m p x k m p x k m= ⋅ (27)
Для такого класса моделей строится страте-
гия ( )1 2 1 2, / , ,q k k L x x′ , в соответствии с кото-
рой решения о состояниях (k1, k2) пары объек-
тов принимаются на основании пары (x1, x2)
признаков. Эти решения совсем не обязательно
окажутся независимыми одно от другого. Из
предположения (27) не следует, что
( ) ( ) ( )1 2 1 2 1 1 2 2, / , , / , / ,q k k L x x q k L x q k L x′ = ⋅ .
Даже в случае, когда два объекта, предъяв-
ленные для распознавания, взаимно независи-
мы, решения о их состояниях не являются не-
зависимыми. При этом качество стратегии q′,
конечно, не хуже, чем качество стратегии q, а
может быть и значительно лучшим.
Таким образом обнаруживается еще одна
предпосылка, принятая в современных подхо-
дах к обучению, как сама собою разумеющая-
ся, но не вытекающая из каких-либо разумных
соображений. Считается, что на основании
обучающей выборки происходит выбор той
или иной стратегии собственно распознавания,
которая затем в неизменном виде применяется
для всех объектов, предъявленных для распо-
знавания. Это – ненужное и ниоткуда не сле-
дующее ограничение.
Необходимость в обучении возникает вооб-
ще только при априорной неопределенности
модели объекта. Обучающая информация по-
зволяет лишь уменьшить эту неопределенность,
а не исключить ее. Каждое из наблюдений,
предъявленных для распознавания уже после
обработки обучающей информации, статисти-
чески зависит от модели и поэтому дополни-
тельно уменьшает ее неопределенность. Если
для распознавания предъявлена последователь-
ность из l объектов, т.е. последовательность
x1, x2, …, xl признаков этих объектов, то только
первый объект должен распознаваться в со-
ответствии со стратегией ( )1 1/ ,q k L x . При рас-
познавании второго объекта признак x1 стано-
вится уже частью обучающей информации и
распознавание должно выполняться в соответ-
ствии с другой стратегией вида q((k2 /(L, x1), x2).
И вообще, i-й объект должен распознаваться
в соответствии со стратегией вида q(ki /(L, x1, …
…, xi–1), xi).
Обучение, т.е. изменение стратегии распо-
знавания, совсем не должно заканчиваться об-
работкой обучающей информации L. Обработ-
ка этой информации является лишь нулевым
этапом обучения, которое затем продолжается
в течение всего периода эксплуатации распо-
знающей системы.
Эмпирический байесовский подход
Очевидно, что при неполном знании стати-
стической модели распознавание многих объ-
ектов одновременно может оказаться заметно
лучшим, чем независимое одно от другого рас-
познавание каждого объекта в отдельности.
Этот вывод справедлив независимо от вида обу-
чающей последовательности, в том числе и в
ее отсутствие. Эту идею в частном виде выска-
зал Г. Роббинс при формулировке предложен-
ного им эмпирического байесовского подхода
[7, 8]. Ученый сформулировал его для случая,
когда модель распознаваемого объекта почти
полностью известна, а неизвестны только апри-
орные вероятности скрытых состояний. Для
этого примера была указана реализация пред-
лагаемого подхода при неограниченном росте
количества объектов, предъявленных для распо-
знавания. Асимптотический характер подхода
выражен в самом его названии «асимптотиче-
ски субминимаксные решения в составных за-
дачах теории статистических решений». Во-
прос о том, каким должно быть решение не в
асимптотическом случае, а при распознавании
конечных совокупностей объектов, был остав-
лен для будущих исследований и до сих пор
оставался без ответа. Исследования задачи
обучения указывают путь к реализации эмпи-
рического байесовского подхода и в случае
конечной совокупности объектов, предъявлен-
ных для распознавания.
Проблема коротких выборок
В изложенном подходе совсем не обязатель-
но считать, что распознавание объекта состоит
УСиМ, 2009, № 1 19
в указании непременно состояния объекта.
Можно допустить и специальный ответ распо-
знающей системы, обозначаемый символом
# K∉ и понимаемый как отказ от распознава-
ния или ответ НЕ ЗНАЮ. В этом случае функ-
ция потерь имеет вид { }( ): #w K K× ∪ →R, а не
:w K K R× → , как раньше, а стратегия обу-
чения-распознавания принимает вид
{ }( ): #n nq L X K R× × ∪ → , а не :n nq L X K R× × → .
Изложенные идеи построения стратегии обу-
чения-распознавания без каких-либо затрудне-
ний можно обоснованно изложить и при таком
расширенном определении основных понятий.
Введение в рассмотрение понятия «отказ от
распознавания» приводит к новой точке зрения
на проблему коротких выборок. Исследования
по проблеме таких выборок имеют целью от-
ветить на вопрос, при какой минимальной
длине обучающей выборки последующее рас-
познавание остается еще удовлетворительным
в том или ином смысле. Все выборки с длиной,
ниже этого предельного значения, объявляют-
ся короткими и непригодными для последую-
щего распознавания. Фактически это обозна-
чает отказ от распознавания независимо от то-
го, какой именно оказалась конкретная корот-
кая выборка и каким оказалось текущее на-
блюдение над объектом, предъявленным для
распознавания.
Формулировка задачи обучения как постро-
ение оптимальной стратегии обучения-распо-
знавания, допускающей и отказ от распознава-
ния, позволяет принимать решение о хороших
или плохих выборках не просто на основании
значений их длины, а более точно, на основа-
нии того, какой именно оказалась та или иная
длинная или короткая выборка. А именно, среди
выборок, пусть даже очень коротких, есть та-
кие, на основании которых возможно вполне
удовлетворительное последующее распознава-
ние, равно как среди длинных могут оказаться
выборки, неудачные в этом отношении.
Понимание того, что результатом обучения
есть стратегия обучения-распознавания, по-
зволяет идти еще дальше. А именно, никакая
выборка, пусть даже очень короткая или очень
длинная, сама по себе не является ни хорошей,
ни плохой. Любая выборка позволяет качест-
венно распознавать одни наблюдения и не го-
дится для распознавания других. Хорошей или
плохой является не выборка сама по себе, а па-
ра «выборка-наблюдение», и стратегия обуче-
ния-распознавания через решение «отказ от
распознавания» реализует в том числе и эту
классификацию.
Таким образом, классификация выборок на
короткие, т.е. плохие, и длинные, т.е. хорошие,
есть лишь сильно загрубленная постановка во-
проса о построении оптимальной стратегии
обучения-распознавания с возможностью от-
каза от распознавания. Построение оптималь-
ной стратегии обучения-распознавания погло-
щает проблему коротких выборок и, поглотив
ее, решает ее более тонко, более дифференци-
рованно.
1. Шлезингер М., Главач В. Десять лекций по стати-
стическому и структурному распознаванию. – К.:
Наук. думка, 2004. – 545 с.
2. Гупал А.М., Пашко С.В., Сергиенко И.В. Эффек-
тивность байесовской процедуры распознавания
// Кибернетика и системный анализ. – 1995. – № 4. –
С. 76–89.
3. Гупал А.М., Сергиенко И.В. Оптимальные проце-
дуры распознавания и их применение // Там же. –
2007. – № 6. – С. 41–54.
4. Зуховицкий С.И., Авдеева Л.И. Линейное и выпук-
лое программирование. – М.: Наука, 1967. – 460 с.
5. Шлезингер М.И. Взаимосвязь обучения и самообу-
чения в распознавании образов // Кибернетика. –
1968. – № 2. – С. 81–88.
6. Demster A., Laird N., Rubin D. Maximum likelihood
from incomplete data via the EM algorithm // J. of the
royal Statistic Society. – 1977. – B39. – P. 1–38.
7. Роббинс Г. Асимптотически субминимаксные реше-
ния в составных задачах теории статистических ре-
шений // Математика. – 1964. – № 8:2. – С. 141–159.
8. Роббинс Г. Эмпирический байесовский подход к
статистике // Там же. – С. 133–140.
© М.И. Шлезингер, A.В. Бондаренко, 2009
|
| id | nasplib_isofts_kiev_ua-123456789-5541 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Russian |
| last_indexed | 2025-12-07T13:39:38Z |
| publishDate | 2009 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Шлезингер, М.И. Бондаренко, А.В. 2010-01-26T11:29:09Z 2010-01-26T11:29:09Z 2009 Как формулировать задачи обучения в распознавании образов / М.И. Шлезингер, А.В. Бондаренко // Управляющие системы и машины. — 2009. — № 1. — С. 4-19. — Бібліогр.: 8 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/5541 004.93’1: 519.157 Исследованы задачи распознавания образов в ситуации, когда статистическая модель распознаваемого объекта известна лишь частично. Выполнен критический анализ минимаксного подхода к решению таких задач и подхода, основанного на максимально правдоподобном оценивании модели по обучающей выборке. Сформулирована постановка задачи, покрывающая весь спектр ситуаций для обучающих выборок любого объема, от нулевого до бесконечного. Выполнен формальный анализ задач обучения в этой новой постановке и показано ее решение в некоторых простейших случаях. Досліджено задачі розпізнавання образів у ситуації, коли статистична модель розпізнаваного об’єекта відома лише частково. Виконано критичний аналіз мінімаксного підходу до розв’язання таких задач та підходу, заснованого на максимально правдоподібному оцінюванні моделі за навчальною вибіркою. Сформульовано постановку задачі, яка покриває весь спектр ситуацій для навчальних вибірок будь-якого об’єму, від нульового до безкінечного. Виконано формальний аналіз задач навчання у цій новій постановці та показано її розв’язання у деяких найпростіших випадках. Pattern recognition problems are considered for a case when a statistical model of an object is not completely known. A minimax approach to solution of such problems is critically analyzed as well as an approach based on the maximal likelihood model estimation with respect to given training multiset. The suggested formulation of the recognition learning problem embraces a whole spectrum of situations for training sets of an arbitrary size: from zero to infinite ones. Main formal properties of the suggested problem formulation are analyzed and its solution in several simplest cases is shown. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Фундаментальные и прикладные проблемы Computer Science Как формулировать задачи обучения в распознавании образов How Pattern Recognition and Learning Problems Should be Formulated Article published earlier |
| spellingShingle | Как формулировать задачи обучения в распознавании образов Шлезингер, М.И. Бондаренко, А.В. Фундаментальные и прикладные проблемы Computer Science |
| title | Как формулировать задачи обучения в распознавании образов |
| title_alt | How Pattern Recognition and Learning Problems Should be Formulated |
| title_full | Как формулировать задачи обучения в распознавании образов |
| title_fullStr | Как формулировать задачи обучения в распознавании образов |
| title_full_unstemmed | Как формулировать задачи обучения в распознавании образов |
| title_short | Как формулировать задачи обучения в распознавании образов |
| title_sort | как формулировать задачи обучения в распознавании образов |
| topic | Фундаментальные и прикладные проблемы Computer Science |
| topic_facet | Фундаментальные и прикладные проблемы Computer Science |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/5541 |
| work_keys_str_mv | AT šlezingermi kakformulirovatʹzadačiobučeniâvraspoznavaniiobrazov AT bondarenkoav kakformulirovatʹzadačiobučeniâvraspoznavaniiobrazov AT šlezingermi howpatternrecognitionandlearningproblemsshouldbeformulated AT bondarenkoav howpatternrecognitionandlearningproblemsshouldbeformulated |