Напоминание: постановка задачи.

Дано: класс решающих функций , обучающая выборка

(1) (1) ( ) ( ) ( ) ( )( , ),..., ( , ),..., ( , )i i N Ns x y x y x y ,

( ) ( ) ( ) ( )

1 ,..., ,...,i i i N

j nx x x x .

Требуется: найти *f , оптимальную по некоторому

критерию качества Q.

Идеальный критерий качества – вероятность правильной классификации → max

(или вероятность ошибки → min)

Распределение вероятностей неизвестно. Пусть решающая функция ( )f x получена методом

(алгоритмом) по выборке Ns объема N : ( ) ( ; )Nf x x s ,

, ,Q , где - класс решающих функций, Q -

критерий качества р.ф., - алгоритм поиска оптимальной р.ф.

Глава 5. Оценивание качества решающих функций

РРааззллоожжееннииее оошшииббккии ннаа ссммеещщееннииее ии ддииссппееррссииюю

Ожидаемая вероятность ошибки метода обучения на выборках заданного объема:

, , [ ( ; )]NN S X Y NP E P Y X S .

Асимптотическая вероятность ошибки для :

, ,lim NN

P P

.

Смещение (мера адекватности метода):

,B

errB P P ,

где B

errP -вероятность ошибки Байесовской р.ф.

Дисперсия метода (мера статистической устойчивости)

, , ,N NV P P .

Выполняется:

, ,B

N err NP P B V

Пусть класс решающих функций упорядочен по сложности M

(например, M - степень полинома в уравнении разделяющей

функции).

Зависимость ожидаемой ошибки метода от сложности класса:

M

,NP

B

,NV

BerrP

optM

5.1. Эмпирическая ошибка

Вместо вероятности ошибки можно использовать ее оценку – частоту ошибки (эмпирическую, подстановочную ошибку):

( )

1

1ˆ ( , ) [ ( ]N

ii

err

i

P f s f x yN

I ,

где 1,

[ ]0, .

U trueU

U false

I

- метод минимизации эмпирической ошибки:

Найти * :эмпf *ˆ ˆ( , ) min ( , )err ýì ï errf

P f s P f s .

ННааппррииммеерр,, ннуужжнноо ннааййттии ллииннееййннууюю ((ккввааддррааттииччннууюю))

ррааззддеелляяюющщууюю ффууннккццииюю,, ддлляя ккооттоорроойй ччаассттооттаа оошшииббоокк ннаа

ооббууччааюющщеейй ввыыббооррккее ммииннииммааллььннаа..

Недостатки метода:

при ограниченной выборке, частотная оценка может обладать большой погрешностью («занижает» вероятность ошибки); решения – далеки от оптимальных.

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

Другие функционалы качества:

Минимизировать не частоту ошибки, а другие характеристики выборки, которые отражают вероятность ошибки и являются более «устойчивыми».

X

max

max minmin

Отступ, margin, межгрупповая дисперсия → max

дисперсия внутри классов → min

Критерий – дисперсионное отношение

maxразброс между группами

Fразброс внутри групп

.

55..22..ЭЭккссппееррииммееннттааллььннооее ооццееннииввааннииее ввеерроояяттннооссттии оошшииббккии Разделение выборки на обучающую (по которой находится решающая функция) и контрольную (по которой определяется качество решающей функции). Контрольной (экзаменационной) выборкой называют выборку, которая не используется при формировании решающей функции, а служит для оценки ее качества путем вычисления относительного числа ошибок.

- Более объективно отражает «истинную» неизвестную ошибку.

- При условии независимости наблюдений, частота ошибок подчиняется биномиальному распределению. Зная число ошибок на контрольной выборке, можно найти доверительный интервал, в котором с заданной вероятностью находится неизвестное значение вероятности ошибки.

Границы доверительного интервала для вероятности

ошибки, в зависимости от частоты ошибки и объема

контрольной выборки

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

- Большая трудоемкость, так как необходимо решить N задач построения решающей функции (N - объем выборки).

ССккооллььззяящщиийй ээккззааммеенн ооццееннииввааеетт ннее ккооннккррееттннууюю рреешшааюющщууюю

ффууннккццииюю,, нноо ммееттоодд ееее ппооссттррооеенниияя

Метод L-кратной перекрестной проверки ("L-fold cross-validation").

Исходная выборка случайным образом делится на L частей, приблизительно одинаковых по объему. Затем каждая часть поочередно выступает как контрольная выборка, а оставшиеся части объединяются в обучающую. Показателем качества метода служит усредненная по контрольным выборкам ошибка.

ННеессммеещщееннннооссттьь ооццееннккии ссккооллььззяящщееггоо ээккззааммееннаа

Обозначим:

( )N

s - метод построения решающей функции ( )y f x по

выборке Ns объема N ,

( ) ( ; )N

f x x s .

Риск ошибки распознавания для f :

,( , ) ( ( ), )

X YR f E L f X Y , где ( , )L Y Y - функция потерь,

( , )P X Y - закон распределения ( , )X Y .

Оценка риска скользящим экзаменом:

( ) ( ) ( ) ( )

1

1( , ) ( ( ; \ ( , ) ), )

Ni i i i

sc N N

i

R s L x s x y yN

.

Пусть 1 1

( , ( ))NS N

E R S

- ожидаемый риск для метода по всем

случайным выборкам объема 1N

- зависит от неизвестного распределения .

Теорема. Выполняется:1 1

( , ) ( , ( ))N NS sc N S N

E R S E R S

Доказательство.

( ) ( ) ( ) ( )

1

1( , ) ; \ ( , ) ,

N N

N

i i i i

S sc N S N

i

E R S E L X S X Y YN

( ) ( ) ( ) ( )

1

1; \ ( , ) ,

N

N

i i i i

S N

i

E L X S X Y YN

.

Но 1

( ) ( ) ( ) ( )

, 1; \ ( , ) , ( ( ; ), )

N N

i i i i

S N S X Y N

не зависит от i

E L X S X Y Y E E L X s Y

,

так как все ( ) ( )( , )i iX Y одинаково распределены с ( , )X Y .

То есть 1 , 1

1

1( , ) ( ( ; ), )

N N

N

S sc N S X Y N

i

E R S E E L X S YN

1 1, 1 1( ( ; ), ) ( , ( ))

N NS X Y N S NE E L X S Y E R S

.

То есть ожидаемая оценка риска для процедуры скользящего экзамена

совпадает с ожидаемым истинным риском для выборок объема 1N

несмещенность оценки скользящего экзамена.

Бутстрэп-анализ.

а) Исходная выборка случайным образом делится на обучающую и контрольную подвыборки заданных объемов.

б) Обучающая подвыборка формируется с помощью случайного отбора объектов с возвращением (т.е. проводится независимый повторный выбор одного из N объектов N раз).

Контрольная подвыборка состоит из оставшихся объектов.

Состав обучающей подвыборки – примерно 63.2% исходной.

111 1 1 0.632

N

eN

По обучающей подвыборке строится решающее правило классификации, а по контрольной подвыборке определяется частота ошибок. Ошибки по контрольным подвыборкам усредняются.

Комбинированная оценка:

.632ˆ0.368 0.632er bootP P P .

55..33.. ООццееннииввааннииее ккааччеессттвваа рреешшааюющщиихх ффууннккцциийй сс

ииссппооллььззооввааннииеемм ммооддееллии ннооррммааллььннооггоо рраассппррееддееллеенниияя Многомерный статистический анализ (модель нормального распределения): K.Фукунага, Ш.Раудис., … Теорема. Пусть распределения классов - многомерные нормальные, с одинаковыми ковариационными матрицами :

1 1 2 2( ) ~ ( , ), ( ) ~ ( , ),p x N m p x N m где 1 2,m m - вектора

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

( )2

F

,

где 1

1 2 1 2

Tm m m m - расстояние Махалонобиса

между классами, F - функция стандартного нормального

распределения.

Вероятность ошибки 2 1

1 2(1) ( ) (2) ( )

X X

B

D D

P P p x dx P p x dx

2/2

21

( )22

x

e dx F

2X

1X

1 2( , )

1 2( , )

2

2

Для выборочной оптимальной решающей функции вероятность ошибки – случайная величина (зависит от выборки).

Можно рассмотреть ожидаемую вероятность ошибки

NEP (усреднение по всевозможным выборкам объема N ).

Вывод выражения для NEP - сложная проблема; решалась

Ш.Раудисом, А.Деевым, М.Окамото и др. (60-80 гг).

Теорема. Пусть распределения классов – n-мерные

нормальные, с ковариационными матрицами 2 :I

1 1( ) ~ ( , )p x N m , 2 2( ) ~ ( , )p x N m , где 1 2,m m - вектора

математических ожиданий; априорные вероятности классов

совпадают. Тогда ожидаемая по выборкам вероятность

ошибки линейной дискриминантной функции равна

2 2 2

1

2 1 21 1

Fn n

N N

Аналогичные теоремы доказаны для более общих случаев.

Пример.

Пусть 1n , 1( ) ~ (2,1)p x N ,

2 ( ) ~ (5,1)p x N , число объектов 10N .

Ожидаемая по выборкам вероятность ошибки решающей

функции (классификация - по близости к центрам классов) равна

2 2 2

3 10.075

2 1 2 11 1

10 3 10 3

F

55..44.. ООццееннккии ккааччеессттвваа ВВааппннииккаа--ЧЧееррввооннееннккииссаа

При каких условиях метод минимизации эмпирической ошибки находит

классификатор с минимальной вероятностью ошибки, а при каких нет?

Закон больших чисел: частота события сходится к его вероятности при

N . Т.е. для фиксированной f частота вероятности ошибки.

Однако из ЗБЧ не следует, что для *

эмпf вероятность ошибки

минимальна или близка к минимальной ( *

эмпf случайна, т.к. зависит от

случайной выборки). Предположим, ( , ), [0; 1]f f x . Тогда

ˆ( , ) ( ), ( , ) ( )err errP f s P P f s .

Для того, чтобы по минимуму значения

функции ( ) можно было судить о

минимуме функции ( )P , достаточно,

чтобы кривая ( ) находилась внутри -

трубки кривой ( )P .

Если ( ) приближает ( )P равномерно по с точностью ,

то *

* * * *

min| ( ) ( ) | ( ) ( )emp emp

PP P P P

*

* * * * * *

0: min

( ) ( ) ( ) ( ) ( ) ( )

emp

emp emp empP P

* * * *( ) ( ) ( ) ( )emp empP P

* * * *| ( ) ( ) | | ( ) ( ) | 2emp empP P .

Так как случайна, можно потребовать:

Pr{sup | ( ) ( ) | } 0N

P

(равномерная сходимость частот к вероятностям) по

множеству решающих функций.

ТВ: теорема Гливенко: с ростом объема выборки эмпирическая

функция распределения равномерно сходится к функции

распределения.

Частный случай задачи распознавания: множество конечно:

1{ ,..., }Mf f . Для каждого if справедливо

неравенство Хёфдинга-Бернштейна (уточнение нер-ва Чебышева): 22Pr{| ( ) ( ) | } N

i if P f e .

Вероятность одновременного выполнения таких неравенств

для 1,..., Mf f :

Pr{sup | ( ) ( ) | }i ii

f P f (=какое-либо > )

22

1

Pr{| ( ) ( ) | }M

Ni i

i

f P f Me

равномерная сходимость, т.е.

Pr{sup | ( ) ( ) | } 0i i Ni

f P f

.

А если N конечно?

Пусть дано малое число , потребуем:

Pr{sup | ( ) ( ) | }i ii

f P f .

Неравенство выполняется, если 22 NMe

ln ln

2

M

N

или

2

ln ln

2

MN

.

ТТееооррееммаа ((ВВ..НН..ВВааппнниикк,, АА..ЯЯ..ЧЧееррввооннееннккиисс)).. Если из множества, состоящего из M решающих правил, выбирается решающее правило, частота ошибок которого на обучающей последовательности равна , то с вероятностью 1 можно

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

меньше 2

ln ln

2

MN

.

Качественный вывод: чем меньше сложность класса (M ), тем меньший объем выборки требуется для достижения заданного качества распознавания (в смысле отклонения вероятности ошибки от ее частоты).

Другая форма неравенства: с вероятностью 1

ln ln( ) ( )

2i i

MP f f

N

.

Пусть класс содержит бесконечное число решающих

функций некоторого типа.

Емкостью класса называется наибольшее число h , такое,

что существует подмножество из h объектов из XD , которое

функции из могут разбить на два класса всеми

возможными способами.

Емкость = размерность Вапника-Червоненкиса= dimVC .

Если такие подмножества существуют для сколь угодно

большого h , то dimVC .

Пример. 1 2XD X X

Разделение возможно

Разделение одной прямой невозможно

Емкость семейства линейных классификаторов на плоскости равна трем В случае n-мерного пространства емкость класса

линейных решающих функций равна n+1

Теорема (ВЧ). Пусть { ( , )}f x - класс решающих правил

ограниченной емкости h , ( ) - частота ошибки, ( )P -

вероятность ошибки правила со значением параметра .

Тогда имеет место равномерная сходимость частоты ошибки

к ее вероятности и справедливо неравенство: 2(2 )

Pr{sup | ( ) ( ) | } 9 exp! 4

hN NP

h

.

Следствие.

2 lnln 1

9( ) ( ) 2

штраф за сложность

Nh

hP

N

.

Метод структурной минимизации риска

Предположим, класс имеет вложенную структуру:

1 2 ... ...MS S S ,

причем их ВЧ-размерности 1 2 Mh h ...h ...

При увеличении сложности класса частота ошибки падает, а

штраф растет существует оптимальная сложность класса

Обсуждение теоремы:

+ справедлива для произвольных распределений; - выведена для «наихудшего» случая, оценки завышены; не учитывается наличие дополнительной априорной информации Пусть {0,1}, 1,..., , {0,1}jX j n Y .

Число векторов 1( ,..., )nx x - 2n , число решающих функций

(отображений X YD D ) - 22n

M

достаточный объем выборки 2

2 ln2 ln

2

n

N

.

например, при 3, 0.05, 0.05n , 1708N .

Причины завышенности: - алгоритм построения решающей функции может быть таким, что некоторые решающие функции никогда не могут быть выбраны, т.е. реальная сложность класса более низкая;

- вероятность объединения событий грубо оценивается через из сумму;

- погрешность экспоненциального неравенства для каждой решающей функции.

55..55.. ББааййеессооввссккиийй ппооддххоодд кк ооццееннииввааннииюю ккааччеессттвваа рраассппооззннаавваанниияя

((ддииссккррееттнныыйй ссллууччаайй))

Рассматривается не «наихудший», а «средний» случай.

X , 1{ }X j MD c … c … c - множество неупорядоченных

значений; Y :

1 2{ , }YD w w .

Закодируем X ,Y через их номера.

Пусть ( )i

jp - вероятность события ” X j Y i ”, ( ) 0i

jp , ( ) 1i

j

i j

p

, 1j … M , 1 2i .

Обозначим «состояние природы» 1( )j M… … , где (1) (2)( )j j jp p .

Наблюдения - iid случайные величины.

N – объем выборки, ( )ijn - число наблюдений i -го образа,

соответствующих j-й ячейке; ( )ij

i j

n N

.

Вектор частот 1( )j Ms s … s … s , где (1) (2)( )j j js n n .

Пусть S – случайный вектор частот, который подчиняется

полиномиальному распределению ( | ) ( )P S s p s , где ( )

( )

( )( )

ijn

iji

i jj

i j

Np s p

n

Рассмотрим семейство полиномиальных моделей

распределения вектора частот с множеством параметров { }

(множество стратегий природы, состояний природы)

Байесовский подход: на множестве определена случайная

величина (1) ( )1( )K

MP … P с некоторым известным априорным

распределением ( )p .

Например, равномерное априорное распределение ( )p const .

Частный вид формулы Лиувилля:

11

1 1

1 1 1 1 1 1

... 10

1

1

( ) ... ( ) (1 ... ) ...

!... !,

( ... 1)!

n n

n

i

d ddn n n

x xx

n

n

x x x x dx dx

d d

d d n

где 1,..., nd d –целые неотрицательные числа.

Отсюда ( ) 1 / { } (2 1)!p d M

(т.к. все 0id , 2n M ).

Рассмотрим апостериорную плотность распределения ( | ) ( | )p S s p s , где sS. По формуле Байеса

( | ) ( )( | )

( )

p s pp s

p s

где, ( ) ( | ) ( )p s p s p d

.

По формуле Лиувилля,

( )

( )

( ),

,

2 1 !( | )

!

ijn

i

jii jj

i j

N Mp s p

n

Решающая функция, минимизирующая эмпирическую ошибку:

(1) (2)1,

2,( | ) j jесли n n

j иначеf j s

.

Вероятность ошибки распознавания для этой функции:

( )

1

( )M

f jerr j

j

P p

,

где 1, ( ) 22,( )если f jиначеf j

.

Математическое ожидание величины вероятности ошибки:

errEP ( )|

1

( ) ( | )M

f js err j

j

P p p s d

( )( ( ))

( ),

,

2 1 !

!

iqn

f j ij qi

i qj q

i q

N Mp p d

n

(1) (2)

1

1(min , 1)

2

M

j j

j

n nN M

2

n M

N M

,

где n - число ошибок для f .

Аналогично дисперсия величины вероятности ошибки:

22

| |( )err s err s errVP E P

2

(1 )

2 1 2 1( 2 )

err errEP EPn M N M n

N M N MN M

.

Интересна лишь верхняя граница для ошибки. Для ее нахождения можно использовать неравенство Кантелли:

2

1( )

1XX EX k

kP

( ( )) )errP P ,

где

1err errEP P

V .

0.05

errEP errVP

Можно выразить объем выборки через другие параметры ( , , ,M n ).

Сравнение оценок достаточного объема выборки для подхода ВЧ ( VN ) и байесовского ( BN ) ( - частота ошибки):

M 10 20 30 40 70 100 200 300

=0, ε=0.05, η=0.05

NV 3970 6740 9516 12288 20606 28924 56650 84375

NB 453 745 1011 1263 1978 2657 4219 6880

=0.05, ε=0.15, η=0.05

NV 993 1686 2380 3073 5152 7232 14163 21094

NB 258 393 512 618 929 1213 2109 2955

Вывод: байесовские оценки менее завышенные.

55..66.. ААннааллиизз RROOCC--ккррииввыыхх ((RReecceeiivveerr OOppeerraattiinngg CChhaarraacctteerriissttiicc,, ккррииввааяя

оошшииббоокк,, ххааррааккттееррииссттииччеессккааяя ккррииввааяя)) Термин – из радиолокации (вражеский самолет ↔ свой самолет)

ROC кривая

•наглядное представление о поведении решающей функции при

изменении параметров;

•возможность визуального сравнения различных решающих

функций;

•больше информации, чем в одном показателе

Таблица сопряженности (предположим, вероятность

событий совпадает с их частотой)

Вместо 4 показателей - 2:

доля правильных положительных классификаций;

чувствительность:

TPR = TP/P

доля ложных положительных классификаций

FPR= FP/N

1- FPR : специфичность.

Истинный класс

Предсказываемый класс

Положительный Отрицательный

Положительный (P) TP P - TP

Отрицательный (N) FP N - FP

Пример: 3 классификатора

Ист

ина

Прогноз

+ -

+ 60 40

- 20 80

Ист

ина

Прогноз

+ -

+ 70 30

- 50 50

Ист

ина

Прогноз

+ -

+ 40 60

- 30 70

Классификатор 1

TPR = 0.4

FPR = 0.3

Классификатор 2

TPR = 0.7

FPR = 0.5

Классификатор 3

TPR = 0.6

FPR = 0.2

случайный

выбор решения

давление крови

чувствительность

специфичность

давление крови рост

0

1

1

F

F

Свойства ROC кривых

Пусть f ( x ) - решающая функция, {'+ }f ( x ) ',' ' .

1. Предположим, решение принимается на основе случ. величины

T h( X ) - ранг объекта (оценка вероятности принадлежности к

классу ' ' ; h - алгоритм вычисления оценки): если T t , то f ' ' ; если T t , то f ' ' , где t - порог.

Тогда

( ( )< ) ( )TPR P h X t |Y ' ' F t ,

( ( )< ) ( )FPR P h X t |Y ' ' F t .

Плотности: ' '( ) ( ), ( ) ( )p t F t p t F t . Получаем:

1 1

0 0

( ) ( ) ( ) ( )AUC F t dF t F t p t dt .

2. Пусть ( ' '), ( ' ')P P Y P P Y . Вид

ROC кривых не зависит от пропорции /P P

(возможен анализ «редких» событий).

Интерпретации AUC

Пусть T - ранг, полученный в соответствии с ( )p t ,

T - ранг, полученный в соответствии с ( )p t .

Тогда ( < )= ( < ) ( ) ( ) ( )P T T P T t p t dt F t p t dt AUC

.

• AUC= вероятность того, что алгоритм h даст случайно выбранному положительному объекту ранг (степень принадлежности к ' ' ) меньше, чем случайно выбранному отрицательному объекту.

из 1

0

( ) ( )AUC F t dF t

• AUC= ожидаемая чувствительность, при равномерно распределенных значениях специфичности (так как ( )~ [0,1]F t U ).

Пусть ,L - потери от принятия решения ' 'Y , когда в

действительности ' 'Y ;

,L - аналогично.

Тогда ожидаемые потери для решающей функции f :

, ,( ) ( ( ) ' ' | ' ') ( ( ) ' ' | ' ')fR t L P P f X Y L P P f X Y

, ,(1 ( )) ( )L P F t L P F t .

Оптимальный порог t – для которого риск минимален (максимален ожидаемый выигрыш)

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

Выбор оптимального порога зависит от конкретной задачи.

ожидаемый выигрыш