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

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

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

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

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

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

${\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} }$ є вагами тренувальних зразків, визначеними згідно алгоритму навчання;
• функція знаку ${\displaystyle \operatorname {sgn} }$ визначає, чи виходить передбачена класифікація ${\displaystyle {\hat {y}}}$ позитивною, чи негативною.

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

Ядровий трюк уникає явного відображення, потрібного для тощо, щоби лінійні алгоритми навчання навчалися нелінійної функції або межі рішень. Для всіх ${\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} }$ часто називають ядром або ядровою функцією. Слово «ядро» використовують в математиці для позначення зважувальної функції зваженої суми або інтегралу.

Деякі задачі в машинному навчанні мають складнішу структуру, ніж просто довільна зважувальна функція ${\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}}}$ є простором з внутрішнім добутком. Ця альтернатива випливає з теореми Мерсера: неявно визначена функція ${\displaystyle \varphi }$ існує тоді, коли простір ${\displaystyle {\mathcal {X}}}$ може бути споряджено придатною мірою, яка забезпечувала би, щоби функція ${\displaystyle k}$ задовольняла умову Мерсера.

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

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

Якщо це підсумовування виконується для всіх скінченних послідовностей точок ${\displaystyle (\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})}$ в ${\displaystyle {\mathcal {X}}}$ і всіх варіантів вибору ${\displaystyle n}$ дійснозначних коефіцієнтів ${\displaystyle (c_{1},\dots ,c_{n})}$ (пор. додатноозначене ядро), то функція ${\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}\}}$ (яку іноді також називають «ядровою матрицею», англ. "kernel matrix"^[3]), мусить бути додатно напівозначеною.^[4] Емпірично, для евристик машинного навчання варіанти обрання функції ${\displaystyle k}$, які не задовольняють умову Мерсера, все ще можуть працювати прийнятно, якщо ${\displaystyle k}$ щонайменше наближує інтуїтивне уявлення про подібність.^[5] Незалежно від того, чи є ${\displaystyle k}$ мерсеровим ядром, ${\displaystyle k}$ все одно можуть називати «ядром».

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

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

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

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

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