Хайкин С. - Нейронные сети (778923), страница 30
Текст из файла (страница 30)
которое является еще одной формой утверждения (2.80). Теперь можно формально сформулировать принцип минимизации эмпирического риска (рппс)р!е оГ ешр)пса! пзк ппшпнхайоп), состоящий из трех взаимосвязанных частей (1084), (1087]. 146 Глава 2. Процессы обучения 3. Равномерная сходимость, определяемая как Р(впр ~ В(тч) — В, „(ж) ~ ) в) — ~ 0 при )Ч вЂ” ~ со, является необходимым и достаточным условием непротиворечивости принципа минимизации эмпирического риска. Для физической интерпретации этого важного принципа проведем следующее наблюдение. До обучения машины все аппроксимирующие функции равноценны. По мере обучения правдоподобие тех функций аппроксимации, которые не противоречат обучающему множеству Дхт, т(;)),'» т, возрастает.
По мере увеличения количества использованных при обучении примеров и, следовательно, повышения "плотности" входного пространства точка минимума функционала эмпирического риска В, р(тт) сходится по вероятности к точке минимума функционала фактического риска зт(т»). ЧС-измерение Теория равномерной сходимости функционала эмпирического риска зт р(ж) к функционалу фактического риска В(тч) включает ограничения на скорость сходи- мости, которые основаны на важном параметре, получившем название нзнерения Вапника-Червоиенкиса (Чарпйг-Слег»опепЫз дппепз(оп) (или просто $'С-измерения) в честь ученых, которые в 1971 году ввели это понятие [1088).
Измерение ВапникаЧервоненкиса является мерой емкости (сарасйу) или вычислительной мощности семейства функций классификации, реализованных обучаемыми машинами. Для того чтобы описать концепцию ЧС-измерения в ракурсе изучаемой проблемы, рассмотрим задачу двоичной классификации образов, для которой множество ожидаемых откликов состоит всего из двух значений г( Е(0, 1). Для обозначения правила принятия решения или функции двоичной классификации будем использовать термин дихотомия (т((с)ютошу).
Пусть Р— множество дихотомий, реализованных обучаемой машиной, т.е. Р = (Г(х,и): ж е %,Р: Я Ж вЂ” ~ (0,1)). (2.85) Пусть 1. — множество, содержащее з» точек т-мерного пространства Х входных векторов: Е=(х; еХ (=1,2,...,)Ч). (2.86) Дихотомия, реализованная обучаемой машиной, разбивает множество Е на два непересекающихся подмножества Ес и 1.„таких, что 2.14. Теория статистического обучения 147 Рис. 2.23. Диаграмма дпи примера 2.1 ,( ) ) 0 для хЕ Ьо, (1 для хЕ Ь,.
(2.87) Пример 2.1 На рис. 2.23 показано двумерное входное пространство Х, состоящее из четырех точек хм хз, хз, хз. Показанные на рисунке границы решений функций го и г) соответствуют классам (гипотезам) 0 и 1. На рис. 2.23 видно, что функция го индуцирует дихотомию 1зо = (Со = (хм хг, хз), Сг = (хз)). С другой стороны, функция г'г описывает дихотомию Рг = (Со = (хг, хз), Сг = (хз, х4)). Так как множеспю С состоит из четырех точек, мощность 1С~ = 4. Следовательно, сзр(С) = 2 = 16. Возвращаясь к общему обсуждению ансамбля дихотомий Е, описываемого формулой (2.85), и соответствующего множества точек Е, задаваемого формулой (2.86), ЧС-измерение можно определить следующим образом (55 Ц, (1084), (1088), (1094). Пусты.'ьр(Ь) — количество различных дихотомий, реализованных обучаемой машиной; гз,р(1) — максимум г0 р(Ь) на множестве всех 1, для которых Щ = 1, где 1Ь~ — количество элементов в 1 .
Говорят, что ансамбль дихотомий к является разбиением множества Ь, если тзр(Ь)=21~1, те, если все возможные дихотомии в Ь могут быть реализованы функциями и. При этом сзр(1) называется функцией роста (8гоцт)г бгпсйоп). 148 Глава 2. Процессы обучения асс 0 Рис.
2.24. Два двумерных распределения для примера 2.2 б) а) )гС-измерением гг называется мощность наибольшего мноэ(сества А, разбиением которого являетсл л'. Другими словами, ЧС-измерением к (обозначается ЧСойш(й)) является самое большое значение )Ч, для которого Ьг()Ч) = 2(т.
В более знакомых терминах это утверждение можно переформулировать следующим образом. ЧС-измерение множества функций классификации (Г(х, и): иб%) — это максимальное число образов, на которых машина может быть обучена без ошибок для всех возможных бинарных маркировок функций классификации. Пример 2.2 Рассмотрим простое решающее правило в т-мерном пространстве Х входных векторов, описываемое следующим образом: Р ( и = (р(зт~х + Ь), (2.88) гле х — т-мерный вектор весов; Ь вЂ” порог.
Функция активации (р является пороговой, т.е. .(.)=(,' "„-;; ЧС-измерение решающего правила, определяемого формулой (2.88), определяется соотношением (2.89) ЧСсйш(Р) = т+ 1. Чтобы проиллюстрировать этот результат, рассмотрим двумерное входное пространство (т.е. т = 2), изображенное на рис. 2.24.
На рис. 2.24, а показаны три точки: х„хз и хз, а также три возможных варианта разделения этих точек. На рисунке ясно видно, что точки могут быть разделены тремя линиями. На рис. 2.24, б изображены четыре точки: х(, хз, хз и х,. Точки хз и хз относятся к классу О, а точки х, и х, — к классу 1. На рисунке видно, что точки хз и хз нельзя отделить от точек х, и х4 одной линней.
Таким образом, ЧС-измерение решающего правила, описанного формулой (2.88), при т = 2 равно 3, что соответствует формуле (2.89). 2.14. Теория статистического обучения 149 Пример 2.3 Поскольку ЧС-измерение является мерой емкости множества функций классификации (индикаторов), то можно ожидать, что обучаемая машина с большим числом свободных параметров будет иметь большое ЧС-измерение, и наоборот. Приведем контрпример, опровергающий это утверждецие!3 Рассмотрим однопврамегрическое семейство функций-индикаторов ((х,а) = вбп(шп(ах)),а Е Я, где зйл( ) — функция вычисления знака аргумента. Предположим, задано некоторое число Ч, для ипорого нужно найти гЧ точек, для которых необходимо построить разбиение.
Этому требованию удовлетворяет набор функций 7(х, а), где х,=10 *,з=1,2,...,!Ч. Чтобы разделить эти точки данных на два класса, определяемых последовательностью А,дг,,г(ч, А Е ( — 1, 1), достаточно выбрать параметр а согласно формуле ~- (1 — д,) 10* Отсюда можно заключить, что ЧС-измерение семейства функций-индикаторов 7" (х, о) с единственным свободным параметром и равно бесконечности. Важность ЧС-измерения и его оценка ЧС-измерение является сугубо комбинаторным понятием (соптЬ[па(от[а! сопсер() и никак не связано с геометрическим понятием измерения. Оно играет центральную роль в теории статистического обучения, что и будет показано в следующих двух подразделах. ЧС-измерение важно также и с конструкторской точки зрения.
Образно говоря, количество примеров, необходимых для обучения системы данным некоторого класса, строго пропорционально ЧС-измерению этого класса. Таким образом, ЧС-измерению стоит уделить первостепенное внимание. В некоторых случаях ЧС-измерение определяется свободными параметрами нейронной сети. Однако на практике ЧС-измерение довольно сложно получить аналитическими методами. Тем не менее границы ЧС-измерения для нейронной сети часто устанавливаются довольно легко. В этом контексте особый интерес представляют следующие два результата'". 'з Согласно [!65), пример 2.3 впервые был приведен в [!085] благодаря Левину (1.еып) и Дснкеру (Оепйяг!.
!х Верхний предел порядка И' 1ак ЬР ЧС-измерения нейронной сети прямого распространения, состоящей из линейных пороговых злсмснтав (псрссптранав), впервые был получен в [!07]. Впоследствии в [692] была паххзвна, чта для этою класса нейросетей нижний предел также имеет порядок И' !ак И'. Верхний предел ЧС-измерения лля снгмаидяльных нейронных сетей янярвыв был получал в [698]. Впоследствии авторы работы [586] решили поставленный в [692] следующий вопрос.
150 Глава 2. Процессы обучения 1. Пусть )д[ — произвольная нейронная сеть прямого распространения, состоящая из нейронов с пороговой функцией активации (Хэвисайда) РС-измерение сети )5[ составляет 0(Иг)ок И'), где Иг — общее количество свободных параметров сети. Этот результат был получен в [107) и [218).
2. Пусть [ч' — произвольная многослойная нейронная сеть прямого распространения, состоящая из нейронов с сигмоидальной функцией активации 1+ ехр( — о) РС-измерение сети Р[ равно 0(Игз), где Иг — общее количество свободных параметров сети. Второй результат был получен в [58б). Чтобы получить его, авторы сначала показали, что ЧС-измерение сетей, состоящее из двух типов нейронов (с линейной и пороговой функциями активации), пропорционально И'з. Это довольно неожиданный результат, так как в примере 2.2 было показано, что ЧС-измерение чисто линейных нейронных сетей пропорционально Иг, а ЧС-измерение нейронных сетей с пороговой функцией активации пропорционально Иг)8Иг (согласно п. 1).
Результат, относящийся к нейронным сетям с сигмоидальными функциями активации, был получен с помощью двух аппроксимаций. Во-первых, нейроны с пороговой функцией активации можно аппроксимировать узлами с сигмоидальными функциями и большими синаптическими весами. Во-вторых, линейные нейроны можно аппроксимировать нейронами с сигмоидальными функциями и малыми синаптическими весами. Здесь важно обратить внимание на то, что многослойные сети прямого распространения имеют конечное ЧС-измерение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
