85
, множителят експоненциално намалява с нарастването на N. Оставащият множител представлява граница на растежа на функцията за семействата от функции
. Този резултат описва лемата на Сауер
(Sauyer’s lemma). Ограничавайки бързия растеж на функцията може да се обезпечи сходимост на първата част на неравенството към 0 при N стремящо се към безкрайност.
Това се удовлетворява, ако VC-измерването h не се явява безкрайно голямо. С други думи краят на VC-измерването се явява необходимо и достатъчно условие за равномерна сходимост на принципа на минимиза VC-измерванеция на емпиричния риск. Ако изходното пространство Х
на крайното множество, то семейството на дихотомиите F има крайно VC-измерване по Х. Обратното твърдрнир не винаги е вярно.
Нека е верочтност на събитието
Тогава с вероятност може да се твърди, че всеки вектор на тегловите коефициенти удоволетворява следващото неравенство
Използвайки неравенство (2.93) и определената вероятност , можем да запишем:
Нека е
някоя стойност на , удовлетворяваща съотношението (2.95).
Тогава получаваме следния важен резултат
Величината се нарича
доверителен интервал (confidence interval). Тази стойност зависи от размера на N, VC-измерването h и вероятността .
Описаният израз (2.93) при достига в
най-лошия случай вероятност , но не за малки стойности на
, които са интересни при решаване на практически задачи. За малки стойности на е важно ограничението, което може да се получи в резултат на някои модификации на неравенство (2.93).
В литературата са представени различни видове ограничения (2.97), зависещи от конкретната форма на неравенствата, използвани за получаването им. Ако неравенството (2.97) има вероятност едновременно за всяко се изпълнява съотношението:
86
Където е новия доверителен интервал, определен в термините на предния разглеждан доверителен интервал представен по следния начин:
Този доверителен интервал зависи от
грешките на обучение . При
= 0 приема следващия упростен вид
Могат да се определят две ограничения на скоростта на равномерна сходимост.
1. В общия случай скоростта на равномерната сходимост удовлетворява следващото неравенство
Където се определя по формула (2.99).
2. При малки (близки до нула) стойности на грешките на обучение се използва неравенството
3. При големи стойности на грешките на обучение близки към единица се изпълнява следното ограничение
Сподели с приятели: