WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

Ядерные методы в машинном обучении — это класс алгоритмов распознавания образов, наиболее известным представителем которого является метод опорных векторов (МОВ, англ. SVM). Общая задача распознавания образов — найти и изучить общие типы связей (например, кластеров, ранжирования, главных компонент, корреляций, классификаций) в наборах данных. Для многих алгоритмов, решающих эти задачи, данные, представленные в сыром виде, явным образом преобразуются в представление в виде вектора признаков^[en] посредством специфичной схемы распределения признаков, однако ядерные методы требуют только задания специфичного ядра, т.е. функции сходства пар точек данных в сыром представлении.

Ядерные методы получили своё название из-за использования ядерных функций^[en], которые позволяют им оперировать в неявном пространстве признаков^[en] высокой размерности без вычисления координат данных в пространстве, просто вычисляя скалярные произведения между образами всех пар данных в пространстве признаков. Эта операция часто вычислительно дешевле явных вычислений координат. Этот подход называется «ядерным трюком»^[1]. Ядерные функции были введены для последовательных данных, графов^[en], текстов, изображений, а также для векторов.

Среди алгоритмов, способных работать с ядрами, находятся ядерный перцептрон^[en], методы опорных векторов, гауссовские процессы, метод главных компонент (МГК, англ. PCA), канонический корреляционный анализ, гребневая регрессия, спектральная кластеризация, линейные адаптивные фильтры и многие другие. Любая линейная модель^[en] может быть переведена в нелинейную модель путём применения к модели ядерного трюка, заменив её признаки (предсказатели) ядерной функцией.

Большинство ядерных алгоритмов базируются на выпуклой оптимизации^[en] или нахождении собственных векторов и статистически хорошо обоснованы. Обычно их статистические свойства анализуруются с помощью теории статистического обучения^[en] (например, используя радемахеровскую сложность^[en]).

Причины возникновения и неформальное объяснение

Ядерные методы можно рассматривать как обучение на примерах — вместо обучения некоторым фиксированным наборам параметров, соответствующим признакам входа, они «запоминают» ${\displaystyle i}$ -й тренировочный пример ${\displaystyle (\mathbf {x} _{i},y_{i})}$ и обучают согласно его весам ${\displaystyle w_{i}}$ . Предсказание для непомеченного ввода, т.е. не входящего в тренировочное множество, изучается при помощи функции сходства ${\displaystyle k}$ (называемой ядром) между непомеченным входом ${\displaystyle \mathbf {x'} }$ и каждым из тренировочных входов ${\displaystyle \mathbf {x} _{i}}$ . Например, ядерный бинарный классификатор^[en] обычно вычисляет взвешенную сумму похожести по формуле

${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i=1}^{n}w_{i}y_{i}k(\mathbf {x} _{i},\mathbf {x'} )}$ ,

где

• ${\displaystyle {\hat {y}}\in \{-1,+1\}}$ является ядерным бинарным классификатором предсказанной пометки для непомеченного входа ${\displaystyle \mathbf {x'} }$ , скрытая верная пометка которого ${\displaystyle y}$ нужна;
• ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$ является ядерной функцией, которая измеряет схожесть пары входов ${\displaystyle \mathbf {x} ,\mathbf {x'} \in {\mathcal {X}}}$ ;
• сумма пробегает по всем n помеченным примерам ${\displaystyle \{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n}}$ в тренировочном наборе классификатора с ${\displaystyle y_{i}\in \{-1,+1\}}$ ;
• ${\displaystyle w_{i}\in \mathbb {R} }$ являются весами тренировочных примеров, как определено алгоритмом обучения;
• Функция sgn определяет, будет предсказанная классификация положительной или отрицательной.

Ядерные классификаторы были описаны в начале 1960-х годов с изобретением ядерного перцептрона^[en][2]. Они получили большое распространение вместе с популярностью метода опорных векторов в 1990-х, когда обнаружили, что МОВ конкурентноспособна с нейронными сетями на таких задачах, как распознавание рукописного ввода.

Математика: ядерный трюк

Ядерный трюк избегает явного отображения, которое нужно для получения линейного обучающего алгоритма для нелинейной функции или границы решений^[en]. Для всех ${\displaystyle \mathbf {x} }$ и ${\displaystyle \mathbf {x'} }$ во входном пространстве ${\displaystyle {\mathcal {X}}}$ некоторые функции ${\displaystyle k(\mathbf {x} ,\mathbf {x'} )}$ могут быть представлены как скалярное произведение в другом пространстве ${\displaystyle {\mathcal {V}}}$ . Функцию ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$ часто называют ядром или ядерной функцией^[en]. Слово «ядро» используется в математике для обозначения весовой функции или интеграла.

Некоторые задачи обучения машин имеют дополнительную структуру, а не просто весовую функцию ${\displaystyle k}$ . Вычисления будут много проще, если ядро можно записать в виде "отображения признаков " ${\displaystyle \varphi \colon {\mathcal {X}}\to {\mathcal {V}}}$ , которое удовлетворяет равенству

${\displaystyle k(\mathbf {x} ,\mathbf {x'} )=\langle \varphi (\mathbf {x} ),\varphi (\mathbf {x'} )\rangle _{\mathcal {V}}.}$

Главное ограничение здесь, что ${\displaystyle \langle \cdot ,\cdot \rangle _{\mathcal {V}}}$ должно быть подходящим скалярным произведением. С другой стороны, явное представление для ${\displaystyle \varphi }$ не обязательно, поскольку ${\displaystyle {\mathcal {V}}}$ является пространством со скалярным произведением. Альтернатива следует из теоремы Мерсера^[en] — неявно заданная функция ${\displaystyle \varphi }$ существует, если пространство ${\displaystyle {\mathcal {X}}}$ может быть снабжено подходящей мерой, обеспечивающей, что функция ${\displaystyle k}$ удовлетворяет условию Мерсера^[en].

Теорема Мерсера подобна обобщению результата из линейной алгебры, которое связывает скалярное произведение с любой положительно определённой матрицей. Фактически, условие Мерсера может быть сведено к этому простому случаю. Если мы выбираем в качестве нашей меры считающую меру ${\displaystyle \mu (T)=|T|}$ для всех ${\displaystyle T\subset X}$ , которая считает число точек внутри множества ${\displaystyle T}$ , то интеграл в теореме Мерсера^[en] сводится к суммированию

${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{n}k(\mathbf {x} _{i},\mathbf {x} _{j})c_{i}c_{j}\geq 0.}$

Если это неравенство выполняется для всех конечных последовательностей точек ${\displaystyle (\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})}$ в ${\displaystyle {\mathcal {X}}}$ и всех наборов ${\displaystyle n}$ вещественнозначных коэффициентов ${\displaystyle (c_{1},\dots ,c_{n})}$ (сравните, Положительно определенное ядро^[en]), тогда функция ${\displaystyle k}$ удовлетворят условию Мерсера.

Некоторые алгоритмы, зависящие от произвольных связей, в исходном пространстве ${\displaystyle {\mathcal {X}}}$ будут, фактически, иметь линейное представление в других условиях — в ранжированном пространстве ${\displaystyle \varphi }$ . Линейная интерпретация даёт нам представление об алгоритме. Более того, часто нет необходимости вычислять ${\displaystyle \varphi }$ прямо во время вычислений, как в случае метода опорных векторов. Некоторые считают уменьшение времени за счёт этого главным преимуществом алгоритма. Исследователи используют его для уточнения смысла и свойств существующих алгоритмов.

Теоретически, матрица Грама ${\displaystyle \mathbf {K} \in \mathbb {R} ^{n\times n}}$ по отношению к ${\displaystyle \{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\}}$ (иногда называемая «ядерной матрицей»^[3]), где ${\displaystyle K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})}$ , должна быть положительно полуопределена^[4]. Эмпирически, для эвристики обучения машин, выбор функции ${\displaystyle k}$ , которая не удовлетворяет условию Мерсера, может оставаться оправданным, если ${\displaystyle k}$ , по меньшей мере, аппроксимирует интуитивную идею похожести^[5]. Независимо от того, является ли ${\displaystyle k}$ ядром Мерсера, о ${\displaystyle k}$ могут продолжать говорить как о «ядре».

Если ядерная функция ${\displaystyle k}$ является также ковариантной функцией^[en], что используется в гауссовском процессе, тогда матрица Грама ${\displaystyle \mathbf {K} }$ может быть названа ковариационной матрицей^[6].

Приложения

Области применения ядерных методов разнообразны и включают геостатистику^[7], кригинг, метод (обратных) взвешенных расстояний^[en], трёхмерную реконструкцию, биоинформатику, хемоинформатику, извлечение информации и распознавание рукописного ввода.

Популярные ядра

• Ядро Фишера^[en]
• Ядра графов^[en]
• Ядерный сглаживатель^[en]
• Полиномиальное ядро^[en]
• Ядро радиальной базисной функции^[en]
• Строковые ядра

Примечания

Литература

Ссылка

• 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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.