Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 214
Скачиваний: 4
266 гл. XI. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЙ
Следовательно, выполнены условия теоремы настоя щего параграфа, так как для систем S lf S 2, состоящих из выпуклых многоугольников с фиксированным числом сторон, равномерная сходимость установлена (пример 5 § 8 главы X).
Значит, равномерная сходимость имеет место при исследуемом распределении и для произвольных выпук лых множеств.
Отметим, что во всех рассмотренных ранее примерах непрерывное распределение было наиболее неблагоприят ным, а в данном случае ситуация обратная.
Г л а в а X II
О Ц Е Н К И Р А В Н О М Е Р Н О Г О О Т Н О С И Т Е Л Ь Н О Г О У К Л О Н Е Н И Я
Ч А С Т О Т О Т В Е Р О Я Т Н О С Т Е Й
ВК Л А С С Е С О Б Ы Т И Й
§1 . О равномерном относительном уклонении
Полученные в главе X оценки скорости равномерной сходимости в действительности оказываются завышенны
ми. |
Это связано |
с тем, что пришлось пойти |
на |
завыше |
ние |
оценок во |
избежание чрезмерной громоздкости |
||
самих оценок |
и технических сложностей |
при |
их вы |
|
воде. Но в еще большей степени это вызано тем, что, желая получить общий результат, пришлось ориентиро ваться на наихудший случай (с точки зрения оценивае мой величины) по тем параметрам, которые не входят явно в оценку.
В частности, для того чтобы уложиться в заданное абсолютное уклонение частоты от вероятности для не которого события А, придется взять большую выборку,
если вероятность А близка к 1/2, |
и меньшую при Р (А ), |
||||
близком к 0 или 1. В самом деле, |
для Р (Л) = 0,5 и до |
||||
пустимого уклонения в 1% |
(т. е. |
ѵ (Л) = |
Р (Л) |
± |
0,01) |
необходимо 104 показов, |
тогда |
как при |
Р (Л) |
= |
0,01 |
и том же допустимом уклонении |
достаточна длина вы |
||||
борки ~ 100 -г- 200. Если же необходимо получить оцен ку сверху, не зависящую от Р (Л), то приходится ориен тироваться на наихудший случай, т. е. Р (Л) = 0,5.
В нашем доказательстве тоже фактически необходимо было ориентироваться на тот случай, когда вероятности Р (Л) всех событий близки к Ѵ2.
Вообще известно, что для фиксированного события Л отклонение частоты от вероятности имеет порядок е, если
268 ГЛ. XII. ОЦЕНКИ ОТНОСИТЕЛЬНОГО УКЛОНЕНИЯ
среднеквадратичное уклонение а частоты имеет порядок е. В свою очередь
° = y f V P { A ) { \ - P { A ) ) ,
т. е. при фиксированном I отклонение пропорционально
У Р 1 - Р) .
Поэтому естественно было бы и равномерное уклоне ние измерять в относительных единицах, т. е. потребо вать, чтобы
sup |
у (А) — Р (А) |
- 0 . |
|
А |
У Р (А) (1 - Р (Л)) 7 |
Однако такого рода оценку при разумных предпо ложениях удается получить только для равномерного уклонения частот в двух последующих полувыборках, нормированного к эмпирической оценке величины
У Р (А) (1 — Р (Л)) по всей выборке. А именно, в следу ющем параграфе будет выведена оценка:
sup |
|ѵ' б 4 )-ѵ ''(Л )| |
> 8 < |
|
иes |
/ Н + А ) ( 1 — V( Л ) ■ 21 |
гЧ
4ms (21) е 4
где ѵ' (А) и ѵ" (А) — частоты выпадения события А со ответственно на первой и второй полувыборках, а ѵ(А) =
ѵ' (А) -|- ѵ" (А) |
А |
. |
на полной вы |
= — ■■9----—----частота выпадени і |
|
борке.
При этом достигается определенное «равноправие» со бытий класса S. Что же касается равномерного относи тельного уклонения частот от вероятностей, то здесь удается получить одностороннюю оценку:
£*/
(1 2 . 1 )
Нормирующий делитель У 1J (А) при малых Р (А) близок к величине У Р (А) (1 — Р (А)).
270 |
ГЛ. |
X II. ОЦЕНКИ ОТНОСИТЕЛЬНОГО УКЛОНЕНИЯ |
|
Д о к а з а т е л ь с т в о . Точно так же как при дока |
|
зательстве |
теоремы 1 0 .2 , сведем дело к рассмотрению |
|
относительного уклонения частот для одного фиксиро ванного события.
Обозначим |
через R a (х х, |
. . ., x2t) — R a (х 21) величину |
||||
|
|
|ѵ ' ( А ) - Ѵ ”(А) 1 |
_ |
|||
|
(ѵ04) + "2г) (і — ѴИ) + |
|||||
Тогда оцениваемая вероятность |
равна |
|||||
Р = |
\ |
Q[sup I R a (ж2!) — е I]dP (xil), |
||||
где |
хи |
AeS |
|
|
|
|
|
f |
|
при |
х^> 0 , |
||
|
|
1 |
||||
|
|
Ѳ(*) = |
п |
при |
а: |
0 . |
|
|
[ 0 |
||||
Рассмотрим опять всевозможные перестановки Tt после довательности хх, . . ., хц. Тогда
Ш
Р = т4т 2 S ѲlsuP I R a (TiXil) — 8 I\dP (xil) = (2/)!
= \ 7Ш 2 SUP ѲI r a (TiX*) - e I dP (a*). (12.3) i=1 Aes
Далее исследуется подынтегральное выражение. Теперь, так как выборка фиксирована, можно вместо S рассматривать конечную систему S', куда входят по одному представителю из каждого класса эквивалентно сти. Таким образом,
(2!)!
(Ш 2 SUP ѳ IЯА (7>2') — е I dP (х*1) < {=1 Aes
|
( 22)! |
< |
{(sJ t S ѲІІ^а (ТіХѵ) - e'l} . (12.4) |
Выражение в фигурных скобках и есть вероятность уклонения частот в двух полувыборках для фиксиро ванного события А для данного состава полной выборки.
