Ядрові методи

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних АвтоМН Асоціативні правила Семантичний аналіз Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик Навчання онтологій Мультимодальне навчання
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання AdaBoost Дерева рішень MARS CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього
Знижування розмірності Факторний аналіз Метод незалежних компонент Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс
Штучна нейронна мережа Автокодувальник Когнітивні обчислення Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа Мемтранзистор Електрохімічна ПДД (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе
Навчання з людьми Активне навчання (машинне навчання) Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання Регуляризація LASSO Тихонова Еластично-сіткова Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання
Місця машинного навчання ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання

В машинному навчанні ядрові методи (англ. kernel methods) — це клас алгоритмів для розпізнавання образів, найвідомішим представником якого є метод опорних векторів (англ. support vector machine, SVM). Загальна задача розпізнавання образів полягає у знаходженні та вивченні основних типів відношень (наприклад, кластерів, ранжування, головних компонент, кореляцій, класифікацій) у наборах даних. Для багатьох алгоритмів, які розв'язують ці задачі, дані в сирому представленні має бути явним чином перетворено на представлення у вигляді векторів ознак через визначене користувачем відображення ознак (англ. feature map): на противагу цьому ядрові методи вимагають лише вказаного користувачем ядра (англ. kernel), тобто, функції подібності над парами точок даних у сирому представленні.

Ядрові методи завдячують своєю назвою застосуванню ядрових функцій, які дозволяють їм діяти в неявному просторі ознак високої вимірності навіть без обчислення координат даних у цьому просторі, натомість просто обчислюючи скалярний добуток зображень всіх пар даних у цьому просторі ознак. Ця операція часто є обчислювально менш витратною, ніж явне обчислення координат. Цей підхід називають ядровим трюком (англ. kernel trick). Ядрові функції було представлено для даних послідовностей, графів, текстів, зображень, як і для векторів.

До алгоритмів, здатних працювати з ядрами, належать ядровий перцептрон, метод опорних векторів (англ. support vector machines, SVM), ґаусові процеси, метод головних компонент (англ. principal components analysis, PCA), канонічно-кореляційний аналіз, гребенева регресія, спектральне кластерування, лінійні адаптивні фільтри та багато інших. Будь-яку лінійну модель може бути перетворено на нелінійну шляхом застосування до неї ядрового трюку: заміни її ознак (провісників) ядровою функцією.^{[джерело?]}

Більшість ядрових алгоритмів ґрунтуються на опуклій оптимізації або власних векторах, і є статистично обґрунтованими. Як правило, їхні статистичні властивості аналізують за допомогою теорії статистичного навчання (наприклад, за допомогою складності Радемахера).

Обґрунтування та неформальне пояснення

Ядрові методи можливо розглядати як навчання на прикладах: замість навчання якогось фіксованого набору параметрів, які відповідають ознакам їхніх входів, вони натомість «запам'ятовують» $i$-тий тренувальний зразок $(\mathbf {x} _{i},y_{i})$ та навчаються відповідної йому ваги $w_{i}$. Для даних, відсутніх у тренувальному наборі, передбачення здійснюється застосуванням функції подібності $k$, яку називають ядром (англ. kernel), до неміченого входу $\mathbf {x'}$ та кожного із тренувальних входів $\mathbf {x} _{i}$. Наприклад, ядрований бінарний класифікатор зазвичай обчислює зважену суму подібностей

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

де

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

Ядрові класифікатори було описано ще в 1960-х роках із винайденням ядрового перцептрону. Вони досягли великого піднесення разом з популярністю опорно-векторних машин (ОВМ) у 1990-х роках, коли було виявлено, що ОВМ є конкурентноздатними в порівнянні зі нейронними мережами на таких задачах як розпізнавання рукописного введення.

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

ОВМ з ядром, заданим φ((a, b)) = (a, b, a² + b²), і відтак K(x, y) = x•y + x² y². Тренувальні точки відображено до 3-вимірного простору, де легко знайти розділову гіперплощину.

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

Деякі задачі в машинному навчанні мають складнішу структуру, ніж просто довільна зважувальна функція $k$. Обчислювання робиться набагато простішим, якщо ядро може бути записано в вигляді «відображення ознак» $\varphi \colon {\mathcal {X}}\to {\mathcal {V}}$, яке задовольняє

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

Ключовим обмеженням є те, що $\langle \cdot ,\cdot \rangle _{\mathcal {V}}$ мусить бути власним внутрішнім добутком. З іншого боку, явне представлення $\varphi$ не є необхідним, поки ${\mathcal {V}}$ є простором з внутрішнім добутком. Ця альтернатива випливає з теореми Мерсера: неявно визначена функція $\varphi$ існує тоді, коли простір ${\mathcal {X}}$ може бути споряджено придатною мірою, яка забезпечувала би, щоби функція $k$ задовольняла умову Мерсера.

Теорема Мерсера є подібною до узагальнення того наслідку з лінійної алгебри, що пов'язує внутрішній добуток із будь-якою додатноозначеною матрицею. Фактично, умову Мерсера може бути зведено до цього простішого прояву. Якщо ми оберемо як нашу міру лічильну міру $\mu (T)=|T|$ для всіх $T\subset X$, яка лічить число точок всередині множини $T$, то інтеграл у теоремі Мерсера зводиться до підсумовування

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

Якщо це підсумовування виконується для всіх скінченних послідовностей точок $(\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})$ в ${\mathcal {X}}$ і всіх варіантів вибору $n$ дійснозначних коефіцієнтів $(c_{1},\dots ,c_{n})$ (пор. додатноозначене ядро), то функція $k$ задовольняє умову Мерсера.

Деякі алгоритми, які залежать від довільних взаємозв'язків у рідному просторі ${\mathcal {X}}$, фактично мають лінійну інтерпретацію за іншої постановки: області значень $\varphi$. Лінійна інтерпретація дає нам прояснення алгоритму. Понад те, часто немає потреби під час обчислень обчислювати $\varphi$ безпосередньо, як у випадку методу опорних векторів. Деякі дослідники посилаються на цю раціоналізацію часу як на головну перевагу. Дослідники також використовують її для обґрунтування сенсу та властивостей наявних алгоритмів.

Теоретично, матриця Грама $\mathbf {K} \in \mathbb {R} ^{n\times n}$ по відношенню до $\{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\}$ (яку іноді також називають «ядровою матрицею», англ. "kernel matrix"), мусить бути додатно напівозначеною. Емпірично, для евристик машинного навчання варіанти обрання функції $k$, які не задовольняють умову Мерсера, все ще можуть працювати прийнятно, якщо $k$ щонайменше наближує інтуїтивне уявлення про подібність. Незалежно від того, чи є $k$ мерсеровим ядром, $k$ все одно можуть називати «ядром».

Якщо ядрова функція $k$ є також і функцією коваріації, як при застосуванні в ґаусових процесах, то матриця Грама $\mathbf {K}$ можуть також називати коваріаційною матрицею.

Застосування

Сфери застосування ядрових методів є різноманітними, до них належать геостатистика, кригінг, зважування зворотних відстаней, об'ємна відбудова, біоінформатика, хемоінформатика, витягування інформації та розпізнавання рукописного введення.

Популярні ядра

• Ядро Фішера
• Графові ядра
• Ядрове згладжування
• Поліноміальне ядро
• РБФ-ядро
• Стрічкові ядра

Див. також

• Ядрові методи для отримування векторних результатів
• Теорема про представлення

Джерела

Література

Книги

• Shawe-Taylor, J.; Cristianini, N. (2004). Kernel Methods for Pattern Analysis. Cambridge University Press. (англ.)
• Liu, W.; Principe, J.; Haykin, S. (2010). Kernel Adaptive Filtering: A Comprehensive Introduction. Wiley. (англ.)

Посилання

• Kernel-Machines Org — вебсайт спільноти (англ.)
• www.support-vector-machines.org (література, огляд, програмне забезпечення, посилання пов'язані з методом опорних векторів — академічний сайт) (англ.)
• Стаття Kernel Methods на onlineprediction.net (англ.)