Метод ядер в машинном обучении: анализ закономерностей и "ядерный трюк"

Введение

Класс алгоритмов для анализа шаблонов

В машинном обучении, методы ядер (kernel machines) представляют собой класс алгоритмов для анализа шаблонов, наиболее известным представителем которого является метод опорных векторов (SVM). Эти методы используют линейные классификаторы для решения нелинейных задач. Общая задача анализа шаблонов заключается в поиске и изучении общих типов связей (например, кластеров, ранжирований, главных компонент, корреляций, классификаций) в наборах данных. Для многих алгоритмов, решающих эти задачи, данные в исходном представлении должны быть явно преобразованы в векторные признаки с помощью заданного пользователем отображения признаков. В отличие от них, методы ядер требуют только заданного пользователем ядра, то есть функции сходства для всех пар точек данных, вычисляемой с использованием скалярного произведения. Отображение признаков в методах ядер является бесконечномерным, но требует только конечномерной матрицы, основанной на входных данных пользователя, согласно теореме о представителе (Representer theorem). Методы ядер работают медленно с наборами данных, содержащими более нескольких тысяч примеров, без использования параллельной обработки. Свое название методы ядер получили благодаря использованию ядерных функций, которые позволяют им работать в высокоразмерном, неявном пространстве признаков, не вычисляя координаты данных в этом пространстве, а просто вычисляя скалярные произведения между образами всех пар данных в пространстве признаков. Эта операция часто вычислительно дешевле, чем явное вычисление координат. Этот подход называется "ядерным трюком" (kernel trick). Ядерные функции были разработаны для последовательных данных, графов, текста, изображений, а также векторов. Алгоритмы, способные работать с ядрами, включают в себя перцептрон с ядром, метод опорных векторов (SVM), гауссовские процессы, анализ главных компонент (PCA), канонический корреляционный анализ, гребневую регрессию, спектральное кластерирование, линейные адаптивные фильтры и многие другие. Большинство ядерных алгоритмов основаны на выпуклой оптимизации или собственных задачах и имеют прочную статистическую основу. Обычно их статистические свойства анализируются с использованием теории статистического обучения (например, с использованием сложности Радемахера).

In machine learning, kernel machines are a class of algorithms for pattern analysis, whose best known member is the support vector machine (SVM). These methods involve using linear classifiers to solve nonlinear problems. The general task of pattern analysis is to find and study general types of relations (for example clusters, rankings, principal components, correlations, classifications) in datasets. For many algorithms that solve these tasks, the data in raw representation have to be explicitly transformed into feature vector representations via a user specified feature map: in contrast, kernel methods require only a user specified kernel, i. e., a similarity function over all pairs of data points computed using inner products. The feature map in kernel machines is infinite dimensional but only requires a finite dimensional matrix from user input according to the Representer theorem. Kernel machines are slow to compute for datasets larger than a couple of thousand examples without parallel processing. Kernel methods owe their name to the use of kernel functions, which enable them to operate in a high dimensional, implicit feature space without ever computing the coordinates of the data in that space, but rather by simply computing the inner products between the images of all pairs of data in the feature space. This operation is often computationally cheaper than the explicit computation of the coordinates. This approach is called the "kernel trick". Kernel functions have been introduced for sequence data, graphs, text, images, as well as vectors. Algorithms capable of operating with kernels include the kernel perceptron, support vector machines (SVM), Gaussian processes, principal components analysis (PCA), canonical correlation analysis, ridge regression, spectral clustering, linear adaptive filters and many others. Most kernel algorithms are based on convex optimization or eigenproblems and are statistically well founded. Typically, their statistical properties are analyzed using statistical learning theory (for example, using Rademacher complexity).

Математика: трюк с ядром

Трюк с ядром позволяет избежать явного отображения, необходимого для того, чтобы линейные алгоритмы обучения могли изучать нелинейную функцию или границу принятия решений. Для всех и в исходном пространстве, определенные функции могут быть выражены как скалярное произведение в другом пространстве. Функция часто называется ядром или ядерной функцией. В математике слово "ядро" используется для обозначения весовой функции для взвешенной суммы или интеграла. Некоторые задачи в машинном обучении обладают большей структурой, чем произвольная весовая функция . Вычисления значительно упрощаются, если ядро можно представить в виде "отображения признаков" , которое удовлетворяет условию, что должно быть корректным скалярным произведением. С другой стороны, явное представление для не требуется, пока является скалярно-производным пространством. Альтернатива следует из теоремы Мерсера: неявно определенная функция существует всякий раз, когда пространство можно снабдить подходящей мерой, обеспечивающей выполнение функцией условия Мерсера. Теорема Мерсера аналогична обобщению результата из линейной алгебры, связывающего скалярное произведение с любой положительно определенной матрицей. Фактически, условие Мерсера можно свести к этому более простому случаю. Если мы выберем в качестве меры счетную меру для всех , которая подсчитывает количество точек внутри множества , то интеграл в теореме Мерсера сводится к суммированию .

The kernel trick avoids the explicit mapping that is needed to get linear learning algorithms to learn a nonlinear function or decision boundary. For all and in the input space , certain functions can be expressed as an inner product in another space The function is often referred to as a kernel or a kernel function. The word "kernel" is used in mathematics to denote a weighting function for a weighted sum or integral. Certain problems in machine learning have more structure than an arbitrary weighting function The computation is made much simpler if the kernel can be written in the form of a "feature map" which satisfies

The key restriction is that must be a proper inner product. On the other hand, an explicit representation for is not necessary, as long as is an inner product space. The alternative follows from Mercer's theorem: an implicitly defined function exists whenever the space can be equipped with a suitable measure ensuring the function satisfies Mercer's condition. Mercer's theorem is similar to a generalization of the result from linear algebra that associates an inner product to any positive definite matrix. In fact, Mercer's condition can be reduced to this simpler case. If we choose as our measure the counting measure for all , which counts the number of points inside the set , then the integral in Mercer's theorem reduces to a summation

If this summation holds for all finite sequences of points in and all choices of real valued coefficients (cf. positive definite kernel), then the function satisfies Mercer's condition. Some algorithms that depend on arbitrary relationships in the native space would, in fact, have a linear interpretation in a different setting: the range space of The linear interpretation gives us insight about the algorithm. Furthermore, there is often no need to compute directly during computation, as is the case with support vector machines. Some cite this running time shortcut as the primary benefit. Researchers also use it to justify the meanings and properties of existing algorithms. Theoretically, a Gram matrix with respect to (sometimes also called a "kernel matrix"), where , must be positive semi definite (PSD). Empirically, for machine learning heuristics, choices of a function that do not satisfy Mercer's condition may still perform reasonably if at least approximates the intuitive idea of similarity. Regardless of whether is a Mercer kernel, may still be referred to as a "kernel". If the kernel function is also a covariance function as used in Gaussian processes, then the Gram matrix can also be called a covariance matrix.

Если это суммирование выполняется для всех конечных последовательностей точек в и всех возможных выборов коэффициентов с действительными значениями (см. положительно определенное ядро), то функция удовлетворяет условию Мерсера. Некоторые алгоритмы, зависящие от произвольных соотношений в исходном пространстве , на самом деле имеют линейную интерпретацию в другом контексте: в пространстве значений. Линейная интерпретация дает нам представление об алгоритме. Кроме того, часто нет необходимости вычислять непосредственно в процессе вычислений, как это происходит, например, с машинами опорных векторов. Некоторые считают это сокращение времени выполнения основным преимуществом. Исследователи также используют его для обоснования значений и свойств существующих алгоритмов. Теоретически, матрица Грама относительно (иногда также называемая "ядерной матрицей"), где , должна быть положительно полуопределенной (PSD). Эмпирически, для эвристик машинного обучения, выбор функции , которая не удовлетворяет условию Мерсера, все равно может работать приемлемо, если хотя бы приближенно соответствует интуитивному понятию сходства. Независимо от того, является ли ядром Мерсера, его все равно можно называть "ядром". Если ядерная функция также является функцией ковариации, как это используется в гауссовских процессах, то матрицу Грама также можно назвать матрицей ковариации.

Приложения

Области применения методов ядра разнообразны и включают геостатистику, кригинг, взвешивание обратных расстояний, 3D-реконструкцию, биоинформатику, хемоинформатику, извлечение информации и распознавание рукописного текста.