Русская Википедия:Ядерный метод
Ядерные методы в машинном обучении — это класс алгоритмов распознавания образов, наиболее известным представителем которого является метод опорных векторов (МОВ, Шаблон:Lang-en). Общая задача распознавания образов — найти и изучить общие типы связей (например, кластеров, ранжирования, главных компонент, корреляций, классификаций) в наборах данных. Для многих алгоритмов, решающих эти задачи, данные, представленные в сыром виде, явным образом преобразуются в представление в виде вектора признаков посредством специфичной схемы распределения признаков, однако ядерные методы требуют только задания специфичного ядра, т.е. функции сходства пар точек данных в сыром представлении.
Ядерные методы получили своё название из-за использования Шаблон:Нп5, которые позволяют им оперировать в неявном пространстве признаков высокой размерности без вычисления координат данных в пространстве, просто вычисляя скалярные произведения между образами всех пар данных в пространстве признаков. Эта операция часто вычислительно дешевле явных вычислений координат. Этот подход называется «ядерным трюком»Шаблон:Sfn. Ядерные функции были введены для последовательных данных, Шаблон:Нп5, текстов, изображений, а также для векторов.
Среди алгоритмов, способных работать с ядрами, находятся Шаблон:Нп5, методы опорных векторов, гауссовские процессы, метод главных компонент (МГК, Шаблон:Lang-en), канонический корреляционный анализ, гребневая регрессия, спектральная кластеризация, линейные адаптивные фильтры и многие другие. Любая Шаблон:Нп5 может быть переведена в нелинейную модель путём применения к модели ядерного трюка, заменив её признаки (предсказатели) ядерной функцией.
Большинство ядерных алгоритмов базируются на выпуклой оптимизации или нахождении собственных векторов и статистически хорошо обоснованы. Обычно их статистические свойства анализируются с помощью теории статистического обучения (например, используя Шаблон:Нп5).
Причины возникновения и неформальное объяснение
Ядерные методы можно рассматривать как обучение на примерах — вместо обучения некоторым фиксированным наборам параметров, соответствующим признакам входа, они «запоминают» <math>i</math>-й тренировочный пример <math>(\mathbf{x}_i, y_i)</math> и обучают согласно его весам <math>w_i</math>. Предсказание для непомеченного ввода, т.е. не входящего в тренировочное множество, изучается при помощи функции сходства <math>k</math> (называемой ядром) между непомеченным входом <math>\mathbf{x'}</math> и каждым из тренировочных входов <math>\mathbf{x}_i</math>. Например, ядерный бинарный классификатор обычно вычисляет взвешенную сумму похожести по формуле
- <math>\hat{y}=\sgn \sum_{i=1}^n w_i y_i k(\mathbf{x}_i, \mathbf{x'})</math>,
где
- <math>\hat{y} \in \{-1, +1\}</math> является ядерным бинарным классификатором предсказанной пометки для непомеченного входа <math>\mathbf{x'}</math>, скрытая верная пометка которого <math>y</math> нужна;
- <math>k \colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}</math> является ядерной функцией, которая измеряет схожесть пары входов <math>\mathbf{x},\mathbf{x'}\in\mathcal{X}</math>;
- сумма пробегает по всем Шаблон:Mvar помеченным примерам <math>\{(\mathbf{x}_i, y_i)\}_{i=1}^n</math> в тренировочном наборе классификатора с <math>y_i \in \{-1, +1\}</math>;
- <math>w_i \in \mathbb{R}</math> являются весами тренировочных примеров, как определено алгоритмом обучения;
- Функция sgn определяет, будет предсказанная классификация положительной или отрицательной.
Ядерные классификаторы были описаны в начале 1960-х годов с изобретением ядерного перцептронаШаблон:Sfn. Они получили большое распространение вместе с популярностью метода опорных векторов в 1990-х годах, когда обнаружили, что МОВ конкурентоспособна с нейронными сетями на таких задачах, как распознавание рукописного ввода.
Математика: ядерный трюк
Ядерный трюк избегает явного отображения, которое нужно для получения линейного обучающего алгоритма для нелинейной функции или Шаблон:Нп5. Для всех <math>\mathbf{x}</math> и <math>\mathbf{x'}</math> во входном пространстве <math>\mathcal{X}</math> некоторые функции <math>k(\mathbf{x}, \mathbf{x'})</math> могут быть представлены как скалярное произведение в другом пространстве <math>\mathcal{V}</math>. Функцию <math>k \colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}</math> часто называют ядром или ядерной функцией. Слово «ядро» используется в математике для обозначения весовой функции или интеграла.
Некоторые задачи машинного обучения имеют дополнительную структуру, а не просто весовую функцию <math>k</math>. Вычисления будут много проще, если ядро можно записать в виде "отображения признаков" <math>\varphi\colon \mathcal{X} \to \mathcal{V}</math>, которое удовлетворяет равенству
- <math>k(\mathbf{x}, \mathbf{x'})=\langle \varphi(\mathbf{x}), \varphi(\mathbf{x'}) \rangle_\mathcal{V}.</math>
Главное ограничение здесь, что <math> \langle \cdot, \cdot \rangle_\mathcal{V}</math> должно быть подходящим скалярным произведением. С другой стороны, явное представление для <math>\varphi</math> не обязательно, поскольку <math>\mathcal{V}</math> является пространством со скалярным произведением. Альтернатива следует из Шаблон:Нп5 — неявно заданная функция <math>\varphi</math> существует, если пространство <math>\mathcal{X}</math> может быть снабжено подходящей мерой, обеспечивающей, что функция <math>k</math> удовлетворяет Шаблон:Нп5.
Теорема Мерсера подобна обобщению результата из линейной алгебры, которое связывает скалярное произведение с любой положительно определённой матрицей. Фактически, условие Мерсера может быть сведено к этому простому случаю. Если мы выбираем в качестве нашей меры считающую меру <math> \mu(T) =|T|</math> для всех <math> T \subset X </math>, которая считает число точек внутри множества <math>T</math>, то интеграл в теореме Мерсера сводится к суммированию
- <math> \sum_{i=1}^n\sum_{j=1}^n k(\mathbf{x}_i, \mathbf{x}_j) c_i c_j \geq 0.</math>
Если это неравенство выполняется для всех конечных последовательностей точек <math>(\mathbf{x}_1, \dotsc, \mathbf{x}_n)</math> в <math>\mathcal{X}</math> и всех наборов <math>n</math> вещественнозначных коэффициентов <math>(c_1, \dots, c_n)</math> (сравните, Шаблон:Нп5), тогда функция <math>k</math> удовлетворяет условию Мерсера.
Некоторые алгоритмы, зависящие от произвольных связей, в исходном пространстве <math>\mathcal{X}</math> будут, фактически, иметь линейное представление в других условиях — в ранжированном пространстве <math>\varphi</math>. Линейная интерпретация даёт нам представление об алгоритме. Более того, часто нет необходимости вычислять <math>\varphi</math> прямо во время вычислений, как в случае метода опорных векторов. Некоторые считают уменьшение времени за счёт этого главным преимуществом алгоритма. Исследователи используют его для уточнения смысла и свойств существующих алгоритмов.
Теоретически, матрица Грама <math>\mathbf{K} \in \mathbb{R}^{n \times n}</math> по отношению к <math>\{\mathbf{x}_1, \dotsc, \mathbf{x}_n\}</math> (иногда называемая «ядерной матрицей»Шаблон:Sfn), где <math>K_{ij}=k(\mathbf{x}_i, \mathbf{x}_j)</math>, должна быть положительно полуопределенаШаблон:Sfn. Эмпирически, для эвристики машинного обучения, выбор функции <math>k</math>, которая не удовлетворяет условию Мерсера, может оставаться оправданным, если <math>k</math>, по меньшей мере, аппроксимирует интуитивную идею похожести[1]. Независимо от того, является ли <math>k</math> ядром Мерсера, о <math>k</math> могут продолжать говорить как о «ядре».
Если ядерная функция <math>k</math> является также Шаблон:Нп5, что используется в гауссовском процессе, тогда матрица Грама <math>\mathbf{K}</math> может быть названа ковариационной матрицейШаблон:Sfn.
Приложения
Области применения ядерных методов разнообразны и включают геостатистикуШаблон:Sfn, кригинг, Шаблон:Нп5, трёхмерную реконструкцию, биоинформатику, хемоинформатику, извлечение информации и распознавание рукописного ввода.
Популярные ядра
Примечания
Литература
- Шаблон:Статья Процитировано в статье
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
Литература
Ссылка
- Kernel-Machines Org — community website
- www.support-vector-machines.org (Literature, Review, Software, Links related to Support Vector Machines - Academic Site)
- onlineprediction.net Kernel Methods Article
Шаблон:Машинное обучение Шаблон:Rq
