Ядровий трюк

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

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

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

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

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

Ядрові методи можливо розглядати як навчання на прикладах: замість навчання якогось фіксованого набору параметрів, які відповідають ознакам їхніх входів, вони натомість «запам'ятовують» ${\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-х роках із винайденням ^[en]. Вони досягли великого піднесення разом з популярністю опорно-векторних машин (ОВМ) у 1990-х роках, коли було виявлено, що ОВМ є конкурентноздатними в порівнянні зі нейронними мережами на таких задачах як розпізнавання рукописного введення.

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

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

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

Теорема Мерсера є подібною до узагальнення того наслідку з лінійної алгебри, що (пов'язує внутрішній добуток із будь-якою додатноозначеною матрицею). Фактично, умову Мерсера може бути зведено до цього простішого прояву. Якщо ми оберемо як нашу міру лічильну міру ${\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})}$ (пор. ^[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}\}}$ (яку іноді також називають «ядровою матрицею», англ. "kernel matrix"), мусить бути додатно напівозначеною. Емпірично, для евристик машинного навчання варіанти обрання функції ${\displaystyle k}$, які не задовольняють умову Мерсера, все ще можуть працювати прийнятно, якщо ${\displaystyle k}$ щонайменше наближує інтуїтивне уявлення про подібність. Незалежно від того, чи є ${\displaystyle k}$ мерсеровим ядром, ${\displaystyle k}$ все одно можуть називати «ядром».

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

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

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

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

• ^[en]
• ^[en]
• Ядрове згладжування
• ^[en]
• ^[en]
• Стрічкові ядра

Див. також

• ^[en]
• ^[en]

Джерела

Цитати

1. Theodoridis, Sergios (2008). Pattern Recognition. Elsevier B.V. с. 203. ISBN . (англ.)
2. Aizerman, M. A.; Braverman, Emmanuel M.; Rozoner, L. I. (1964). Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control. 25: 821—837. Процитовано в Guyon, Isabelle; Boser, B.; Vapnik, Vladimir (1993). Automatic capacity tuning of very large VC-dimension classifiers. Advances in neural information processing systems. (CiteSeerX): 10.1.1.17.7215. (англ.)
3. Kernel Methods in Machine Learning. — 2008. — 7 липня. (англ.)
4. ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Foundations of Machine Learning (англ.). USA, Massachusetts: MIT Press. ISBN .
5. Sewell, Martin. . www.svms.org. Архів оригіналу за 15 жовтня 2018. Процитовано 16 жовтня 2016. (англ.)
6. Gaussian Processes for Machine Learning. — 2006. — 7 липня. (англ.)
7. Honarkhah, M.; Caers, J. (2010). Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling. ^[en]. 42: 487—517. doi:10.1007/s11004-010-9276-7. (англ.)

Література

Книги

• ; (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 (англ.)