Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 269
Текст из файла (страница 269)
В частности, предположим, что используются следующие три характеристики: Г2 = Хг 12 = Х2 Г2 =. т/2хтх2 (20.1б) Вскоре будет показано, как получены эти выражения, а пока просто рассмотрим, что происходит. На рис. 20.25, б показаны данные в этом новом, трехмерном пространстве, определенном тремя характеристиками; очевидно, что данные в этом пространстве являются линейно разделимыми! Такой подход действительно является достаточно общим: если данные отображаются на пространство с достаточно большим количеством размерностей, то они всегда могут быть преобразованы в линейно разделимую форму.
В данном случае использовались только три размерности'4, но если бы количество точек данных было равно О), то, за исключением частных случаев, они всегда являются разделимыми в пространстве с )0-1 размерностями или больше (упр. 20.21). 1,5 а о с 3 2 1 0 -1 -2 -3 0 0,5 б„ о со о 0 о о о оо ев 2,5 2 1,5 1 х,' 0,5 -0,5 -1,5 -1,5 -1 -0,5 0 0,5 1 1,5 х а) Рис. 20.25. Пример применения преобразования: двухмерная задача обучения с положительными примерами, показанными в виде черных кружков, и отрицательными примерами, обозначенными белыми кружками. Показана также истинная граница решений, х224кгг<2 (а); те же данные после отображения на трехмерное пространство входов (хт,х2~,3~2хтхг).
Круглая граница решений, показанная на рис. 20.25, а, в трехмерном пространстве становится линейной границей решения (б) '4 Читатель мог заметить, что достаточно было использовать только характеристики г, и Е2, но трехмерное отображение позволяет лучше проиллюстрировать зту идею. Итак, можно ли считать, что на этом проблема исчерпана? Достаточно ли просто подготовить целый ряд расчетных характеристик, а затем найти линейный разделитель в соответствующем многомерном пространстве? К сожалению, все не так просто. Напомним, что линейный разделитель в пространстве с с) размерностями определяется уравнением с с) параметрами, поэтому возникает серьезная опасность 993 Глава 20. Статистические методы обучения О,В -„- 0,6 0,4 0,2 о 0 0,2 0,4 0,6 О,В ) 2 х, lЪс.
20.2б. Замыкание оптимального разделителя, показанного на рис. 20.25, б, спроектированное на первые две размерности. Разделитель показан в виде жирнои линии, а ближайшие точки Гподдерживагоилие векторы) обозначены кружками. Край представляет собой разделение между положительными и отрицательными примерами Но как найти такой разделитель? Оказалось, что эта задача представляет собой задачу оптимизации из области 'ж квадратичного программирования. Предположим, что имеютсЯ пРимеРы хь с классификациЯми Уь=-ь1 и необходимо найти оптимальный разделитель в пространстве входов; в таком случае задача квадратичного программирования сводится к поиску значений параметров а„которые максимизируют слепую)цее выражение с учетом ограничений аз>0 и ~~, (хг у, = 0: Х --Х 1'Ч ' пг - 2~ и, пз уг у, (хг х ) (20.17) 1, з Хотя для понимания излагаемого материала не обязательно знакомиться с тем, как было выведено данное выражение, следует отметить, что оно имеет два важных свойства.
Во-первых, это выражение имеет единственный глобальный максимум, который может быть найден с помощью эффективных методов. Во-вторых, св данные входят в это выражение только в форме точечных произведений пар точек. Утверждение о существовании чрезмерно тщательной подгонки данных, если с)=д), т.е. приблизительно равно количеству точек данных. (Такая ситуация аналогична чрезмерно тщательной подгонке к данным с помощью полинома высокой степени, о чем шла речь в главе! 8.) По этой причине ядерные машины обычно находят оптимальный линейный разделитель, т.е.
такой разделитель, который имеет наибольший 'в, край между ним и положительными примерами, с одной стороны, и отрицательными примерами, с другой (рис. 20.26). Можно показать, используя аргументы, основанные на теории вычислительного обучения (см, раздел 18.5), что такой разделитель обладает желаемыми свойствами с точки зрения возможности надежного обобщения новых примеров. 994 Часть х). Обучение такого второго свойства является также справедливым применительно к уравнению для самого разделителя; как только будут вычислены оптимальные значения цз, появляется возможность вычислить следуюгдее выражение: (20.
18) Последнее важное свойство оптимального разделителя, определяемого этим уравнением, заключается в том, что веса а„связанные с каждой точкой данных, являются нулевыми, кроме тех точек, которые являются ближайшими к разделителю; эти точки называются ек поддерживающими векторами (они получили такое название потому, что на них как бы "опирается" разделяюшая гиперплоскость).
Поскольку количество поддерживающих векторов обычно намного меньше, чем количество точек данных, результирующее количество параметров, определяющих оптимальный разделитель, так же намного меныпе, чем М. Итак, обычно не стоит рассчитывать на то, что удастся найти линейный разделитель в пространстве входов х, но легко показать, что можно найти линейные разделители в многомерном пространстве характеристик в'(х), просто заменяя точечное произведение х,.х, в уравнении 20.17 произведением л'(х,) д'(х,) . В этой операции, отдельно взятой, нет ничего необычного (поскольку требуемый эффект может быть достигнут путем замены х на г(х) в любом алгоритме обучения), но точечное произведение обладает некоторыми особыми свойствами.
Как оказалось, значение в'(х,) .в'(х,) часто можно вычислить без предварительного вычисления характеристики Е'для каждой точки. В рассматриваемом трехмерном пространстве, определяемом уравнением 20.!б, с помошью несложных алгебраических преобразований можно показать, что справедливо следуюшее соотношение: к(х ) к(х ) = (х, хз) Выражение (х, х;) ' называется ядерной функцией и обычно записывается как к(х,,х,). В контексте проблематики ядерных машин под этим подразумевается любая функция, которая может быть применена к парам выходных данных для вычисления точечных произведений в некотором соответствующем пространстве характеристик.
Таким образом, утверждение, приведенное в начале данного абзаца, можно сформулировать следующим образом; линейные разделители в многомерном пространстве характеристик в'(х) можно найти, заменив выражение х,.х, в уравнении 20.17 ядерной функцией к(х„х,) . Таким образом, может быть организовано обучение в многомерном пространстве, но для этого придется вычислять только значения ядерных функций, а не значения полного списка характеристик для каждой точки данных.
Следуюший этап, который теперь должен стать полностью очевидным, состоит в демонстрации того, что в ядерной функции К(х„хз) = (х, х, ) ' НЕт НИЧЕГО Особенною, просто она соответствует конкретному пространству характеристик с большим количеством размерностей, а другие ядерные функции соответствуют другим пространствам характеристик. Один из знаменитых результатов в математике, 'еь теорема Мерсера 995 Глава 20.
Статистические методы обучения 11035], гласит, что любая "приемлемая" ядерная функция" соответствует некоторому пространству характеристик. Эти пространства характеристик могут оказаться очень большими даже применительно к таким ядерным функциям, которые выглядят совершенно "невинно".
Например, 'т, полиномиальная ядерная функция, К(хь,х,) = (1+хгх,), соответствует пространству характеристик, количество размерностей которого определяется экспоненциальной зависимостью от с(. Поэтому использование ядерных функций, подобных приведенной в уравнении 20.17, с(у обеспечивает эффективный поиск оптимальных линейных разделителей в пространствах характеристик с миллиардал~и Га в некоторых случаях с бесконечным количеством) размерностей. Полученные в результате линейные разделители после их обратного отображения на первоначальное пространство входов могут соответствовать произвольно сложным, нелинейным границам между положительными и отрицательными примерами. Как было упомянуто в предыдущем разделе, ядерные машины превосходят все другие способы распознавания рукописных цифр; кроме того, они быстро находят применение и в других приложениях, особенно в тех, которые отличаются большим количеством входных характеристик.
В составе этого процесса было разработано много новых ядерных функций, позволяющих работать со строками, деревьями и другими нечисловыми типами данных. Было также отмечено, что метод ядерных функций может применяться не только в алгоритмах обучения, которые находят оптимальные линейные разделители, но и в любых других алгоритмах, которые можно переформулировать применительно к использованию только точечных произведений пар точек данных, как в уравнениях 20.17 и 20.18.
После выполнения такого преобразования точечное произведение заменяется ядерной функцией, что приводит к получению версии того же алгоритма, Ъ. преобразованной в ядернузо форму. Кроме всего прочего, такое преобразование можно легко применить для обучения с )т ближайшими соседними точками и для обучения персептрона. 20.7. ПРАКТИЧЕСКИЙ ПРИМЕР: РАСПОЗНАВАНИЕ РУКОПИСНЫХ ЦИФР Задача распознавания рукописных цифр является важной во многих приложениях, включая автоматизированную сортировку почты по почтовому коду, автоматизированное чтение чеков и налоговых деклараций, а также ввод данных для портативных компьютеров. В этой области достигнут быстрый прогресс отчасти благодаря применению лучших алгоритмов обучения и отчасти благодаря наличию лучших обучающих наборов. В Национальном институте стандартов и технологии ()ь)а(!опа1 1пзйгще оГ Бгапдагда апс1 Тес)зпо!ояу — )ь)1ЯТ) США был создан архив, представляющий собой базу данных из 60 000 рукописных цифр с расшифровками (с так называемой разметкой), каждая из которых задана в виде изображения, состоящего из 20х20=400 пикселов с восьмибитовой кодировкой уровня серого.
Распознавание и Здесь под понятием "приемлемой** ядерной функции подразумевается, что матрица к,,= к(х., х, ) является положительной и определенной; см, приложение А. Глава 20. Статистические методы обучения 997 быть небольшими, поскольку иначе цифра 6 могла бы превратиться в 9!). Наилучшим значением частоты ошибок, достигнутым с помощью сетей ) еХег, было 0,9% В усиленной нейронной сети комбинировались три копии архитектуры )еХец притом что вторая обучалась на смеси образцов, которые первая распознавала с ошибками 50% а третья обучалась на образцах, для которых не было достигнуто согласование с помощью первых двух копий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
