ЯДЕРНЫЕ МАШИНЫ
Приведенное выше описание нейронных сетей не дает ответа на одну дилемму. Однослойные сети позволяют использовать простой и эффективный алгоритм обучения, но обладают лишь очень ограниченной выразительной мощью, поскольку способны определять в процессе обучения только линейные границы между решениями в пространстве входов. Многослойные сети, с другой стороны, являются гораздо более выразительными (они способны представлять нелинейные функции общего вида), но задача их обучения становится очень сложной из-за большого количества локальных минимумов и высокой размерности пространства весов. В этом разделе рассматривается относительно новое семейство методов обучения, основанных на использовании машин поддерживающих векторов (Support Vector Machine — SVM), или, в более общем смысле, ядерных машин (kernel machine). Ядерные машины позволяют в определенной степени воспользоваться наилучшими свойствами и однослойных, и многослойных сетей. Это означает, что в методах, основанных на их использовании, предусмотрен эффективный алгоритм обучения, а сами они позволяют представить сложные, нелинейные функции.
Полное описание ядерных машин выходит за рамки данной книги, но мы можем проиллюстрировать их основную идею на примере. На рис. 20.25, а показано двухмерное пространство входов, определяемое атрибутами х= (х1,х2), в котором положительные примеры (у=+1) находятся внутри круга, а отрицательные примеры (у=-1)— вне его. Очевидно, что для данной задачи не существует линейного разделителя. А теперь предположим, что входные данные выражены иначе, с помощью каких-то вычислимых характеристик, т.е. что каждый вектор входных данных х отображен на новый вектор значений характеристик, F(x). В частности, предположим, что используются следующие три характеристики:
fl = X!2
f2 = х22
f3 = фх!Х2 (20.16)
Итак, можно ли считать, что на этом проблема исчерпана? Достаточно ли просто подготовить целый ряд расчетных характеристик, а затем найти линейный разделитель в соответствующем многомерном пространстве? К сожалению, все не так просто. Напомним, что линейный разделитель в пространстве с d размерностями определяется уравнением с d параметрами, поэтому возникает серьезная опасность чрезмерно тщательной подгонки данных, если d~N, т.е. приблизительно равно количеству точек данных. (Такая ситуация аналогична чрезмерно тщательной подгонке к данным с помощью полинома высокой степени, о чем шла речь в главе 18.) По этой причине ядерные машины обычно находят оптимальный линейный разделитель, т.е. такой разделитель, который имеет наибольший край между ним и положительными примерами, с одной стороны, и отрицательными примерами, с другой (рис. 20.26). Можно показать, используя аргументы, основанные на теории вычислительного обучения (см. раздел 18.5), что такой разделитель обладает желаемыми свойствами с точки зрения возможности надежного обобщения новых примеров.
Вскоре будет показано, как получены эти выражения, а пока просто рассмотрим, что происходит. На рис. 20.25, б показаны данные в этом новом, трехмерном пространстве, определенном тремя характеристиками; очевидно, что данные в этом пространстве являются линейно разделимыми! Такой подход действительно является достаточно общим: если данные отображаются на пространство с достаточно большим количеством размерностей, то они всегда могут быть преобразованы в линейно разделимую форму. В данном случае использовались только три размерности14, но если бы количество точек данных было равно N, то, за исключением частных случаев, они всегда являются разделимыми в пространстве с N-1 размерностями или больше (упр. 20.21).
Но как найти такой разделитель? Оказалось, что эта задача представляет собой задачу оптимизации из области квадратичного программирования. Предположим, что имеются примеры х± с классификациями у±=±1 и необходимо найти оптимальный разделитель в пространстве входов; в таком случае задача квадратичного программирования сводится к поиску значений параметров ai? которые максимизируют
следующее выражение с учетом ограничений.
Хотя для понимания излагаемого материала не обязательно знакомиться с тем, как было выведено данное выражение, следует отметить, что оно имеет два важных свойства. Во-первых, это выражение имеет единственный глобальный максимум, который может быть найден с помощью эффективных методов. Во-вторых, данные входят в это выражение только в форме точенных произведений пар точек. Утверждение о существовании такого второго свойства является также справедливым применительно к уравнению для самого разделителя; как только будут вычислены оптимальные значения аь появляется возможность вычислить следующее выражение:
Последнее важное свойство оптимального разделителя, определяемого этим уравнением, заключается в том, что веса аь связанные с каждой точкой данных, являются нулевыми, кроме тех точек, которые являются ближайшими к разделителю; эти точки называются поддерживающими векторами (они получили такое название потому, что на них как бы "опирается" разделяющая гиперплоскость). Поскольку количество поддерживающих векторов обычно намного меньше, чем количество точек данных, результирующее количество параметров, определяющих оптимальный разделитель, также намного меньше, чем N
Итак, обычно не стоит рассчитывать на то, что удастся найти линейный разделитель в пространстве входов х, но легко показать, что можно найти линейные разделители в многомерном пространстве характеристик F(x), просто заменяя точечное произведение xx-j в уравнении 20.17 произведением F(Xi)-F(XJ ). В этой операции, отдельно взятой, нет ничего необычного (поскольку требуемый эффект может быть достигнут путем замены х на F(x) в любом алгоритме обучения), но точечное произведение обладает некоторыми особыми свойствами. Как оказалось, значение F(xi) -F(XJ) часто можно вычислить без предварительного вычисления характеристики F для каждой точки. В рассматриваемом трехмерном пространстве, определяемом уравнением 20.16, с помощью несложных алгебраических преобразований можно показать, что справедливо следующее соотношение:
F(xi) • F(Xj) = (xi • x-j)2
Выражение (Xi-Xj)2 называется ядерной функцией и обычно записывается как iC(xi,Xj). В контексте проблематики ядерных машин под этим подразумевается любая функция, которая может быть применена к парам выходных данных для вычисления точечных произведений в некотором соответствующем пространстве характеристик. Таким образом, утверждение, приведенное в начале данного абзаца, можно сформулировать следующим образом: линейные разделители в многомерном пространстве характеристик F(x) можно найти, заменив выражение Xi-Xj в уравнении 20.17 ядерной функцией iC(xi,Xj). Таким образом, может быть организовано обучение в многомерном пространстве, но для этого придется вычислять только значения ядерных функций, а не значения полного списка характеристик для каждой точки данных.
Следующий этап, который теперь должен стать полностью очевидным, состоит в демонстрации того, что в ядерной функции JC(Xi,Xj) = (xi-Xj)2 нет ничего особенного, просто она соответствует конкретному пространству характеристик с большим количеством размерностей, а другие ядерные функции соответствуют другим пространствам характеристик. Один из знаменитых результатов в математике, теорема Мерсера
[1035], гласит, что любая "приемлемая" ядерная функция15 соответствует некоторому пространству характеристик. Эти пространства характеристик могут оказаться очень большими даже применительно к таким ядерным функциям, которые выглядят совершенно "невинно". Например, полиномиальная ядерная функция, K{Xi,Xj) = (1+Xi-Xj)d, соответствует пространству характеристик, количество размерностей которого определяется экспоненциальной зависимостью от d. Поэтому использование ядерных функций, подобных приведенной в уравнении 20.17,
обеспечивает эффективный поиск оптимальных линейных разделителей в пространствах характеристик с миллиардами (а в некоторых случаях с бесконечным количеством) размерностей. Полученные в результате линейные разделители после их обратного отображения на первоначальное пространство входов могут соответствовать произвольно сложным, нелинейным границам между положительными и отрицательными примерами.
Как было упомянуто в предыдущем разделе, ядерные машины превосходят все другие способы распознавания рукописных цифр; кроме того, они быстро находят применение и в других приложениях, особенно в тех, которые отличаются большим количеством входных характеристик. В составе этого процесса было разработано много новых ядерных функций, позволяющих работать со строками, деревьями и другими нечисловыми типами данных. Было также отмечено, что метод ядерных функций может применяться не только в алгоритмах обучения, которые находят оптимальные линейные разделители, но и в любых других алгоритмах, которые можно переформулировать применительно к использованию только точечных произведений пар точек данных, как в уравнениях 20.17 и 20.18. После выполнения такого преобразования точечное произведение заменяется ядерной функцией, что приводит к получению версии того же алгоритма, преобразованной в ядерную форму. Кроме всего прочего, такое преобразование можно легко применить для обучения с к ближайшими соседними точками и для обучения персептрона.
Задача распознавания рукописных цифр является важной во многих приложениях, включая автоматизированную сортировку почты по почтовому коду, автоматизированное чтение чеков и налоговых деклараций, а также ввод данных для портативных компьютеров. В этой области достигнут быстрый прогресс отчасти благодаря применению лучших алгоритмов обучения и отчасти благодаря наличию лучших обучающих наборов. В Национальном институте стандартов и технологии (National Institute of Standards and Technology — NIST) США был создан архив, представляющий собой базу данных из 60 000 рукописных цифр с расшифровками (с так называемой разметкой), каждая из которых задана в виде изображения, состоящего из 2 0x20=400 пикселов с восьмибитовой кодировкой уровня серого.