Хайкин С. - Нейронные сети (778923), страница 95
Текст из файла (страница 95)
° Этот процесс продолжается до тех пор, пока не будет отфнльтровано все множество из АГ1 примеров. Полученное множество примеров затем используется для обучения третьего эксперта. После окончания обучения третьего эксперта на отфильтрованном множестве примеров процесс обучения всей ассоциативной машины считается завершенным. Описанная выше процедура фильтрации графически представлена на рис. 7.2. Пусть Хз — количество примеров, отфильтрованных первым экспертом для получения обучающего множества второго эксперта, содержащего Хз элементов. Заметим, что число Х1 фиксировано, а число Хз зависит от ошибки обобщения первого эксперта. Пусть Мз — количество примеров, обработанных в процессе совместной фильтрации первым и вторым экспертами для формирования обучающего множества третьего эксперта из Х, элементов.
Так как это же число (Х,) ранее испольювалось для обучения первого эксперта, общий объем данных, необходимый для обучения ассоциативной машины, составляет %4 — — Х1 + Агз + Хз. Однако при этом вычислительная стоимость обучения зависит от З*Х, примеров, так как Х, — это количество примеров, действительно используемых для обучения всех трех экспертов. Таким образом, можно утверждать, что описанный здесь алгоритм усиления является действительно "интеллектуальным" (апаг~): для работы ассоциативной машины требуется большой объем примеров, но на самом деле для реального обучения будет использоваться только небольшое подмножество этих данных. 7.4. Метод усиления 469 )т примеров Обучаемый г эксперт гу! примеров со статистикой, ! омличлой от той, которой обучался эксперт ! а) Филь!ранил примеров, выполненная экспертом ! Л'! примеров со статистикой, ояыичлой от той, которой обучались эксперты ! и 2 Рис.
7.2. ГраФически представленный процесс усиления эа счет фильтрации б) Фильтрапия примеров, выполненная экспертами 2 н 3 Еще одним вопросом, на который хотелось бы обратить внимание, является следующий. Операция фильтрации, выполняемая первым экспертом, и операция совместной фильтрации, совмсстно выполняемая первым и вторым экспертами, заставляют второго и третьего экспертов сосредоточиться на "тяжелых для усвоения" частях распределения. В теоретическом выводе алгоритма усиления, впервые представленном в 1940], для оценки производительности ассоциативной машины на не встречавшихся ранее примерах использовалось простое голосование. А именно, на вход ассоциативной машины подавался тестовый пример. Если решения первого и второго экспертов совпадали, для маркировки использовался именно этот класс.
В противном случае использовалась оценка третьего эксперта. Однако экспериментально 1266],[267] было определено, что спор!гение соответствующих выходов трех экспертов приводит к лучшей производительности, нежели голосование. Например, в задаче оптического распознавания символов (орбса! с))атас)ег гесояп11(оп — ОСИ) операция сложения выполнялась сложением выходов "цифра 0" всех трех экспертов; аналогично — для всех остальных девяти цифр. Предположим, что все три эксперта (т.е. подгипотезы) имеют уровень ошибок б ( 1/2 по отношению к распределениям, на которых происходило их обучение. Это значит, что все три модели обучения являются слабыми.
В (940] было доказано, что общий уровень ошибок ассоциативной машины в данном случае ограничен следующей величиной: д(а) = За' — 2а'. (7.15) 470 Глава 7. Ассоциативные машины 0,5 0,4 6,* а 0,2 тсльнсстн 242 Од Рнс.
7.3. График зависимости (7.10) длн усиления за счет фильтрации 0 Од 0,2 ОД 0,4 0,5 т Зависимость д(е) от к показана иа рис. 7.3. На рисунке видно, что это ограиичение существенно меньше исходного уровня ошибок а. Рекурсивио применяя алгоритм усиления, уровень ошибок можно сделать сколь угодно малым.
Другими словами, модель слабого обучения, производительность которой мало отличается от случайного выбора, при помощи усиления можно преобразовать в сильную модель обучения. Именно в этом смысле можно с полным правом утверждать, что слабая и сильная модели обучения иа самом деле эквивалентны. Алгоритм адаптивного усиления АдаВоое$ ° АдаВоозг адаптивно настраивается иа ошибки слабых гипотез, возвращаемых слабыми моделями обучения.
Благодаря именно этому свойству алгоритм и получил свое название. Практическое ограничение усиления за счет фильтрации состоит в том, что для него часто требуется довольно большое множество примеров. Это ограничение можно обойти, используя другой алгоритм усиления, который называется АдаВоозт [3191, 13201 и принадлежит к категории усиления с использованием подвыборки. Контур подвыборки АдаВоозг является обычным контуром пакетного обучения.
И, что более важно, — ои допускает повторное использование данных обучения. Как и в случае использования алгоритма усиления за счет фильтрации, АдаВооз1 позволяет работать со слабыми моделями обучения. Целью этого алгоритма является поиск окончательной функции отображения или гипотезы, которая будет иметь иизкий уровень ошибок иа даииом распределении В маркированных примеров обучения. От других алгоритмов усиления АдаВоозг отличается следующим. 7.4. Метод усиления 471 ° Ограничение производительности алгоритма АбаВооз! зависит от производительности слабой модели обучения только иа тех распределениях, которые фактически формируются в процессе обучения. Алгоритм АдаВоом работает следующим образом.
На итерации п алгоритм усиления реализует слабую модель обучения с распределением Р„миожества примеров обучения Т. Слабая модель обучения вычисляет гипотезу Р„: Х вЂ” ~ У, которая корректио классифицирует часть примеров обучения. Ошибка измеряется относительно распределения Р„. Этот процесс продолжается Т итераций, в результате чего машина усиления объединяет гипотезы Р„Рз,...,Рг в единую заключительную гипотезу Ра„. Для того чтобы вычислить распределение Р„иа итерации п и заключительную гипотезу Ра„, используется простая процедура, описанная вкратце в табл. 7.2. Исходное распределение является равномерным иа множестве примеров обучения Т, т.е.
1 Р,(1) = — для всех(. Для даииого распределения Р„и слабой гипотезы Р„иа итерации п следующее распределение Р„ч, вычисляется умножением веса примера 1 иа некоторое число !3„Е [О, 1), если гипотеза Р„коррехтио классифицирует входной вектор х,. В противном случае вес остается неизменным. В итоге все веса заново иормируются делением иа константу нормировки Я„. В результате "легкие" примеры множества Т, корректно классифицированные предыдущей слабой гипотезой, будут иметь более низкий вес, в то время как "трудные" примеры, для которых частота ошибок классификации была высокой, будут иметь больший вес.
Таким образом, алгоритм АдаВоом концентрирует основной объем весов иа тех примерах, классифицировать которые оказалось сложнее всего. Окончательная гипотеза Ра„вычисляется голосованием (т.е. взвешенным линейиым порогом) из множества гипотез Рм Рз,...,Рг. Это значит, что для данного входного вектора х окончательная гипотеза дает иа выходе метку г(, которая максимизирует сумму весов слабых гипотез, которые определили эту метку. Вес гипотезы Р„определяется как!оя(1ф„), т.е. больший вес назначается гипотезе с меньшей ошибкой. Важное теоретическое свойство алгоритма АдаВооз! было сформулировано в следующей теореме (319). Пусть нри вызове алгоритма АдаВоозг слабая модель обучения сгенерировала гилотезы с ошибками аы аз,..., ат, где ошибка в„на итерации п алгоритлш АдаВооз! онределяется как 472 Глава 7.
Ассоциативные машины ТАБЛИЦА 7.2. Краткое описание алгоритма АдаВоов1 Дано: Множество примеров обучения ((х<, д;))~ ! Распределение Р для А/ маркированных примеров Слабая модель обучения Целое число Т, задающее количество итераций алгоритма Инициализация: Р>(!) = — 1/А> для всех ! Вычисления: . Для и = 1, 2,..., Т выполняются следующие действия. 1. Вызывается слабая модель обучения, реализуемая на распределении Р„ 2.
Формируется гипотеза г„: Х- У 3. Вычисляется ошибка гипотезы г„ е„= 2; Р„(<) ««е„/кдфл, 4. Вычисляется )3„ = (еь)/(1 — вп) 5. Изменяется распределение Р„: в <о ~(/3„, если Р„(х<) = д<, ( 1, в противном случае, где ӄ— константа нормировки (выбираемая таким образом, чтобы Р„<.! было распределением вероятности) Выход: Окончательная гипотеза вычисляется следующим образом: гя„(х) = ага>пах 2 1оя — ' п«я„<к)=л Пусть такт<се ап < 1/2 и 7„= 1/2 — а„. Тогда ошибка окончательной гипотезы ограничена сверху следующей величиной: т / т — ~(з: лгя„(х,) ф д,)( < П „Г1 — 4)д < ехр ~ — 2~~ Тз . (7.16) ч=! «=! Согласно этой теореме, если ошибка слабой гипотезы, построенной слабой моделью обучения, лишь немного меньше величины 1/2, то ошибка обучения окончательной гипотезы та„экспоненциально стремится к нулю.
Однако это совсем не значит, что ошибка обобщения на тестовых примерах тоже будет мала. Эксперименты, представленные в [319], показали следующее. Во-первых, теоретическая граница ошибки обучения часто оказывается слабой. Во-вторых, ошибка обобщения зачастую су<цественно лучше, нежели это следует из теоретических выкладок. В табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
