Лекция 2. Линейная машина_ теория Вапника-Червоненкиса (2014 Лекции (Сенько)), страница 2

Частота ошибокνerr (A) = k/m распределена по биномиальному законуk[perr (A)]k [1 − perr (A)]m−kP [νerr (A)] = Cmгде perr (A) - вероятность ошибочной классификации для алгоритма A.Сенько Олег Валентинович ()МОТП, лекция 218 / 28Теория Вапника-ЧервоненкисаВероятность выполнения неравенства | νerr (A) − perr (A) |> ε задаётсяравенствомP {| νerr (A) − perr (A) |> ε} =(5)X00k0=Cm[perr (A)]k [1 − perr (A)](m−k )|k0 /m−perr (A)|>εСенько Олег Валентинович ()МОТП, лекция 219 / 28Теория Вапника-ЧервоненкисаДля оценки сверху вероятности P {| νerr (A) − perr (A) |> ε} прибольших m может быть использована интегральная теоремыМуавра–Лапласа: при m → ∞ оказывается справедливым неравенствоP {| νerr (A) − perr (A) |> ε} ≤ √−ε2 m2σe 2σ2 ,2mπεгде σ 2 = [1 − perr (A)]perr (A). Поскольку perr ∈ [0, 1], то нетруднопоказать, что σ 2 < 41 .

В результате убеждаемся в справедливостинеравенств при m → ∞P {| νerr (A) − perr (A) |> ε} ≤ √12e−2ε m ,2mπε(6)Нетрудно видеть, что правая часть неравенства (5) быстро стремитсяк 0 при m → ∞.Сенько Олег Валентинович ()МОТП, лекция 220 / 28Теория Вапника-ЧервоненкисаТаким образом, для каждого отдельного алгоритма распознавания наобучающей выборке частота ошибки быстро сходится к вероятностиошибки при m → ∞.

На самом деле в процессе обучения оцениваетсябольшое число всевозможных алгоритмов модели M̃ . Алгоритмы сминимальной частотой ошибки могут соответствовать как раз оченьвысоким отклонения частот от вероятностей. Достижение высокойобобщающей способности гарантируется при выполнении условияравномерной сходимости:при произвольном ε > 0P {max [| νerr (A) − perr (A) |] > ε} → 0(7)fA∈Mпри m → ∞.Сенько Олег Валентинович ()МОТП, лекция 221 / 28Теория Вапника-Червоненкисаeεm событие, заключающееся в выполнении дляОбозначим как Aалгоритма A неравенства | νerr (A) − perr (A) |> ε на обучающейвыборке Set длины m .

Тогда, принимая во внимание неравенство Буля,получаемeP {max | νerr (A) − perr (A) |> ε} = P (∪A∈MfAεm ) ≤fA∈MXeεm ) (8)P (AfA∈MПринимая во внимание неравенство (8) и (6) получаемP {max | νerr (A) − perr (A) |> ε} ≤fA∈MСенько Олег Валентинович ()XfA∈MМОТП, лекция 2√12e−2ε m2mπε(9)22 / 28Теория Вапника-Червоненкисаf конечна и содержит NСначала рассмотрим случай когда модель Mразличных алгоритмов.

Тогда очевидноP {max | νerr (A) − perr (A) |> ε} ≤ √fA∈MN2e−2ε m2mπε(10)В теории Вапника-Червоненкиса предлагается использовать дляf конечное множество Mfd if ⊆ Mf,оценки разнообразия модели Mобладающее следующими свойствами:множества ошибок для любых двух различных алгоритмов изfdif на обучающей выборке не совпадают;Mf, обладающегомощность любого конечного подмножества Mfdif .первым свойством, не превышает мощности MСенько Олег Валентинович ()МОТП, лекция 223 / 28Теория Вапника-ЧрвоненкисаЧисло таких алгоритмов задаётся коэффициентом разнообразияf, Set ), который определяется как число способов, которыми Set∆(Mf.может быть разбита на две подвыборки алгоритмами из модели MДля оценок наличия равномерной сходимости при обучении по моделиf, m): максимальное значениеиспользуется функция роста µ(Mкоэффициентов разнообразия на множестве Ωm всевозможныхобучающих выборок длины m:f, m) = max ∆(Mf, Set )µ(M(11)et ∈ΩmSСенько Олег Валентинович ()МОТП, лекция 224 / 28Теория Вапника-ЧервоненкисаУчитывая, что число отличных друг от друга алгоритмов в указанномранее смысле ограничено сверху функцией роста, получаем верхнююоценку вероятности выполнения неравенства | νerr (A) − perr (A) |> ε.f, m)µ(M2e−2ε mP {max | νerr (A) − perr (A) |> ε} ≤ √f2mπεA∈MСенько Олег Валентинович ()МОТП, лекция 2(12)25 / 28Теория Вапника-ЧервоненкисаФункция роста обладает следующим замечательным свойством.Существует два типа моделей распознавания.

Для произвольнойf1 при любом заданном m существует такаямодели первого типа M∗eвыборка S , содержащая m объектов, что произвольное разбиение Se∗f1 .на два подмножества может быть реализовано алгоритмами из MИными словами при произвольном m справедливо равенствоf, m) = 2m . Для произвольной модели второго типа Mf2 существуетµ(Mтакое натуральное m0 , что отсутствуют выборки, разделимые на дваf2 . Иными словамипроизвольных подмножества алгоритмами из Mсуществует такое натуральное m, чтоf2 , m) < 2m .µ(M(13)Предположим, что m0 - минимальное m, при котором справедливоf2 конечна инеравенство (13). В этом случае считается, что ёмкость M0равна m∗ = m − 1.Сенько Олег Валентинович ()МОТП, лекция 226 / 28Теория Вапника-ЧервоненкисаСчитается также, что ёмкость произвольной модели первого типаявляется бесконечной.f2 приБыло показано, что для произвольной модели второго типа Mпроизвольном m > m∗ для функции роста справедливо ограничениесверху(m∗ −1)f2 , m) ≤ 1.5 mµ(M(14)(m∗ − 1)!f2 , m) ограничена сверху полиномом степениИз следует, что µ(Mm∗ − 1.

Однако при произвольных вещественном α > 0 и натуральномk > 0 для произвольного положительного полинома P ol(m, k) степениk от аргумента mP ol(m, k)lim→ 0.(15)m→∞eαmИз (13) и (14) следует, что при произвольном ε > 0f2 , m)µ(M√→ 0.m→∞ e2mε2 2πmlimСенько Олег Валентинович ()МОТП, лекция 2(16)27 / 28Теория Вапника-ЧервоненкисаИз стремления к 0 правой части неравенства (12) следуетP {max | νerr (A) − perr (A) |> ε} → 0fA∈Mпри m → ∞,что означает выполнение условия равномерной сходимости. Такимобразом для любой модели, имеющей конечную ёмкость, получениеалгоритмов, обладающих обобщающей способностью являетсягарантированным при достаточно больших объёмах обучающихвыборок.

Бесконечная ёмкость модели не позволяет сделать вывод оналичии обобщающей способности даже при очень больших объёмахобучающей выборки.Сенько Олег Валентинович ()МОТП, лекция 228 / 28.