Перегляд вихідного коду сторінки Ядрові методи

{{Машинне навчання}}

В [[Машинне навчання|машинному навчанні]] '''ядрові методи''' ({{lang-en|kernel methods}})&nbsp;— це клас алгоритмів для [[розпізнавання образів]], найвідомішим представником якого є [[метод опорних векторів]] ({{lang-en|support vector machine, SVM}}). Загальна задача розпізнавання образів полягає у знаходженні та вивченні основних типів відношень (наприклад, [[Кластерний аналіз|кластерів]], [[ранжування]], [[Метод головних компонент|головних компонент]], [[Кореляція|кореляцій]], [[Статистична класифікація|класифікацій]]) у наборах даних. Для багатьох алгоритмів, які розв'язують ці задачі, дані в сирому представленні має бути явним чином перетворено на представлення у вигляді [[Вектор ознак|векторів ознак]] через визначене користувачем ''відображення ознак'' ({{lang-en|feature map}}): на противагу цьому ядрові методи вимагають лише вказаного користувачем ''ядра'' ({{lang-en|kernel}}), тобто, [[Функція подібності|функції подібності]] над парами точок даних у сирому представленні.

Ядрові методи завдячують своєю назвою застосуванню {{нп|Додатноозначене ядро|ядрових функцій||Positive-definite kernel}}, які дозволяють їм діяти в ''неявному'' [[Простір ознак|просторі ознак]] високої вимірності навіть без обчислення координат даних у цьому просторі, натомість просто обчислюючи {{нп|Скалярний добуток (лінійна алгебра)|скалярний добуток|en|Inner product}}<!-- Проблема вікіфікації: Сторінка [[:en:Inner product]] (→ [[:en:Inner product space]]) перекладена як [[Передгільбертів простір]], хоча хотіли [[Скалярний добуток (лінійна алгебра)]] (SashkoR0B0T)--> зображень всіх пар даних у цьому просторі ознак. Ця операція часто є обчислювально менш витратною, ніж явне обчислення координат. Цей підхід називають '''ядровим трюком''' ({{lang-en|kernel trick}}).<ref>{{Cite book|title=Pattern Recognition|last=Theodoridis|first=Sergios|publisher=Elsevier B.V.|year=2008|isbn=9780080949123|location=|pages=203}} {{ref-en}}</ref> Ядрові функції було представлено для даних послідовностей, {{нп|Графове ядро|графів||Graph kernel}}, текстів, зображень, як і для векторів.

До алгоритмів, здатних працювати з ядрами, належать {{нп|ядровий перцептрон|||Kernel perceptron}}, метод опорних векторів ({{lang-en|support vector machines, SVM}}), [[Ґаусів процес|ґаусові процеси]], [[метод головних компонент]] ({{lang-en|principal components analysis, PCA}}), [[канонічно-кореляційний аналіз]], [[Регуляризація Тихонова|гребенева регресія]], [[спектральне кластерування]], [[Адаптивний фільтр|лінійні адаптивні фільтри]] та багато інших. Будь-яку [[Лінійна модель|лінійну модель]] може бути перетворено на нелінійну шляхом застосування до неї ядрового трюку: заміни її ознак (провісників) ядровою функцією.{{Citation needed|date=Вересень 2019}}<!-- остерігайтеся джерел, що просто копіюють це твердження з Вікіпедії... -->

Більшість ядрових алгоритмів ґрунтуються на [[Опукла оптимізація|опуклій оптимізації]] або [[Власний вектор|власних векторах]], і є статистично обґрунтованими. Як правило, їхні статистичні властивості аналізують за допомогою [[Теорія статистичного навчання|теорії статистичного навчання]] (наприклад, за допомогою {{нп|Складність Радемахера|складності Радемахера||Rademacher complexity}}).

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

Ядрові методи можливо розглядати як [[навчання на прикладах]]: замість навчання якогось фіксованого набору параметрів, які відповідають ознакам їхніх входів, вони натомість «запам'ятовують» <math>i</math>-тий тренувальний зразок <math>(\mathbf{x}_i, y_i)</math> та навчаються відповідної йому ваги <math>w_i</math>. Для даних, відсутніх у тренувальному наборі, передбачення здійснюється застосуванням [[Функція подібності|функції подібності]] <math>k</math>, яку називають '''ядром''' ({{lang-en|kernel}}), до неміченого входу <math>\mathbf{x'}</math> та кожного із тренувальних входів <math>\mathbf{x}_i</math>. Наприклад, ядрований [[бінарний класифікатор]] зазвичай обчислює зважену суму подібностей

: <math>\hat{y} = \sgn \sum_{i=1}^n w_i y_i k(\mathbf{x}_i, \mathbf{x'})</math>,

де

* <math>\hat{y} \in \{-1, +1\}</math> є передбаченою ядрованим бінарним класифікатором міткою для неміченого входу <math>\mathbf{x'}</math>, справжня прихована мітка <math>y</math> якого нас і цікавить;
* <math>k \colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}</math> є ядровою функцією, яка вимірює подібність будь-якої пари входів <math>\mathbf{x}, \mathbf{x'} \in \mathcal{X}</math>;
* сума пробігає {{mvar|n}} мічених зразків <math>\{(\mathbf{x}_i, y_i)\}_{i=1}^n</math> тренувального набору класифікатора, де <math>y_i \in \{-1, +1\}</math>;
* <math>w_i \in \mathbb{R}</math> є вагами тренувальних зразків, визначеними згідно алгоритму навчання;
* [[функція знаку]] <math>\sgn</math> визначає, чи виходить передбачена класифікація <math>\hat{y}</math> позитивною, чи негативною.

Ядрові класифікатори було описано ще в 1960-х роках із винайденням {{нп|Ядровий перцептрон|ядрового перцептрону||Kernel perceptron}}.<ref>{{cite journal |last1=Aizerman |first=M. A. |first2=Emmanuel M. | last2 = Braverman |first3=L. I. |last3=Rozoner |title=Theoretical foundations of the potential function method in pattern recognition learning |url=https://archive.org/details/sim_automation-and-remote-control_1964-06_25_6/page/821 |journal=Automation and Remote Control |volume=25 |year=1964 |pages=821–837}} Процитовано в {{Cite conference |last1=Guyon |first1=Isabelle |first2=B. |last2=Boser |first3=Vladimir |last3=Vapnik |title=Automatic capacity tuning of very large VC-dimension classifiers |conference=Advances in neural information processing systems |year=1993 |id = {{citeseerx|10.1.1.17.7215}}}} {{ref-en}}</ref> Вони досягли великого піднесення разом з популярністю [[Метод опорних векторів|опорно-векторних машин]] (ОВМ) у 1990-х роках, коли було виявлено, що ОВМ є конкурентноздатними в порівнянні зі [[Штучна нейронна мережа|нейронними мережами]] на таких задачах як [[розпізнавання рукописного введення]].

== Математика: ядровий трюк ==
[[Файл:Kernel trick idea.svg|thumb|500px|ОВМ з ядром, заданим φ((''a'', ''b'')) = (''a'', ''b'', ''a''<sup>2</sup> + ''b''<sup>2</sup>), і відтак ''K''('''x''', '''y''') = '''x'''•'''y''' + '''x'''<sup>2</sup> '''y'''<sup>2</sup>. Тренувальні точки відображено до 3-вимірного простору, де легко знайти розділову гіперплощину.]]
Ядровий трюк уникає явного відображення, потрібного для тощо, щоби лінійні [[Машинне навчання|алгоритми навчання]] навчалися нелінійної функції або {{нп|Межа рішення|межі рішень||Decision boundary}}. Для всіх <math>\mathbf{x}</math> та <math>\mathbf{x'}</math> у вхідному просторі <math>\mathcal{X}</math> певні функції <math>k(\mathbf{x}, \mathbf{x'})</math> може бути виражено як [[внутрішній добуток]] в іншому просторі <math>\mathcal{V}</math>. Функцію <math>k \colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}</math> часто називають ''ядром'' або ''{{нп|Ядрова функція|ядровою функцією||Kernel function}}''. Слово «ядро» використовують в математиці для позначення зважувальної функції зваженої суми або [[інтеграл]]у.

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

: <math>k(\mathbf{x}, \mathbf{x'}) = \langle \varphi(\mathbf{x}), \varphi(\mathbf{x'}) \rangle_\mathcal{V}.</math>

Ключовим обмеженням є те, що <math> \langle \cdot, \cdot \rangle_\mathcal{V}</math> мусить бути власним внутрішнім добутком. З іншого боку, явне представлення <math>\varphi</math> не є необхідним, поки <math>\mathcal{V}</math> є {{нп|Простір з внутрішнім добутком|простором з внутрішнім добутком||Inner product space}}<!-- Проблема вікіфікації: Сторінка [[:en:Inner product space]] перекладена як [[Передгільбертів простір]], хоча хотіли [[Простір з внутрішнім добутком]] (SashkoR0B0T)-->. Ця альтернатива випливає з {{нп|Теорема Мерсера|теореми Мерсера||Mercer's theorem}}: неявно визначена функція <math>\varphi</math> існує тоді, коли простір <math>\mathcal{X}</math> може бути споряджено придатною [[Міра (математика)|мірою]], яка забезпечувала би, щоби функція <math>k</math> задовольняла {{нп|Умова Мерсера|умову Мерсера||Mercer's condition}}.

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

: <math> \sum_{i=1}^n\sum_{j=1}^n k(\mathbf{x}_i, \mathbf{x}_j) c_i c_j \geqslant 0.</math>

Якщо це підсумовування виконується для всіх скінченних послідовностей точок <math>(\mathbf{x}_1, \dotsc, \mathbf{x}_n)</math> в <math>\mathcal{X}</math> і всіх варіантів вибору <math>n</math> дійснозначних коефіцієнтів <math>(c_1, \dots, c_n)</math> (пор. {{нп|додатноозначене ядро|||Positive-definite kernel}}), то функція <math>k</math> задовольняє умову Мерсера.

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

Теоретично, [[матриця Грама]] <math>\mathbf{K} \in \mathbb{R}^{n \times n}</math> по відношенню до <math>\{\mathbf{x}_1, \dotsc, \mathbf{x}_n\}</math> (яку іноді також називають «ядровою матрицею», {{lang-en|"kernel matrix"}}<ref>{{cite paper | first1 = Thomas | last1 = Hofmann | first2 = Bernhard | last2 = Scholkopf | first3 = Alexander J. | last3 = Smola | date = 2008 | title = Kernel Methods in Machine Learning |url=https://projecteuclid.org/download/pdfview_1/euclid.aos/1211819561 }} {{ref-en}}</ref>), мусить бути [[Додатно напівозначена матриця|додатно напівозначеною]].<ref>{{Cite Mehryar Afshin Ameet 2012}}</ref> Емпірично, для евристик машинного навчання варіанти обрання функції <math>k</math>, які не задовольняють умову Мерсера, все ще можуть працювати прийнятно, якщо <math>k</math> щонайменше наближує інтуїтивне уявлення про подібність.<ref>{{cite web|url=http://www.svms.org/mercer/|title=Support Vector Machines: Mercer's Condition|first=Martin|last=Sewell|date=|website=www.svms.org|accessdate=2016-10-16|archive-date=2018-10-15|archive-url=https://web.archive.org/web/20181015031456/http://www.svms.org/mercer/}} {{Webarchive|url=https://web.archive.org/web/20181015031456/http://www.svms.org/mercer/ |date=2018-10-15 }} {{ref-en}}</ref> Незалежно від того, чи є <math>k</math> мерсеровим ядром, <math>k</math> все одно можуть називати «ядром».

Якщо ядрова функція <math>k</math> є також і {{нп|Функція коваріації|функцією коваріації||Covariance function}}, як при застосуванні в [[Ґаусів процес|ґаусових процесах]], то матриця Грама <math>\mathbf{K}</math> можуть також називати [[Коваріаційна матриця|коваріаційною матрицею]].<ref>{{cite paper | first1 = C. E. | last1 = Rasmussen | first2 = C. K. I. | last2 = Williams | date = 2006 | title = Gaussian Processes for Machine Learning }} {{ref-en}}</ref>

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

Сфери застосування ядрових методів є різноманітними, до них належать [[геостатистика]],<ref>{{cite journal | last1 = Honarkhah | first1 = M. | last2 = Caers | first2 = J. | date = 2010 | doi = 10.1007/s11004-010-9276-7 | title = Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling |journal={{нп|Mathematical Geosciences}} | volume = 42 | pages = 487–517 }} {{ref-en}}</ref> [[кригінг]], {{нп|зважування зворотних відстаней|||Inverse distance weighting}}, [[об'ємна відбудова]], [[біоінформатика]], [[хемоінформатика]], [[витягування інформації]] та [[розпізнавання рукописного введення]].

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

* {{нп|Ядро Фішера|||Fisher kernel}}
* {{нп|Графове ядро|Графові ядра||Graph kernel}}
* [[Ядрове згладжування]]
* {{нп|Поліноміальне ядро|||Polynomial kernel}}
* {{нп|РБФ-ядро|||RBF kernel}}
* [[Стрічкове ядро|Стрічкові ядра]]

== Див. також ==
* {{нп|Ядрові методи для отримування векторних результатів|||Kernel methods for vector output}}
* {{нп|Теорема про представлення|||Representer theorem}}

== Джерела ==
=== Цитати ===
{{reflist}}

=== Література ===
{{refbegin}}
; Книги
* {{cite book | authorlink1 = Джон Шоуї-Тейлор | first1 = J. | last1 = Shawe-Taylor | authorlink2 = Нелло Хрістіаніні | first2 = N. | last2 = Cristianini | title = Kernel Methods for Pattern Analysis | publisher = Cambridge University Press | year = 2004 }} {{ref-en}}
* {{cite book | first1 = W. | last1 = Liu | first2 = J. | last2 = Principe | first3 = S. | last3 = Haykin | title = Kernel Adaptive Filtering: A Comprehensive Introduction | publisher = Wiley | year = 2010 |url=https://books.google.com/books?id=eWUwB_P5pW0C&printsec=frontcover#v=onepage&q&f=false}} {{ref-en}}
{{refend}}

== Посилання ==
* [http://www.kernel-machines.org Kernel-Machines Org]&nbsp;— вебсайт спільноти {{ref-en}}
* [http://www.support-vector-machines.org www.support-vector-machines.org] ''(література, огляд, програмне забезпечення, посилання пов'язані з методом опорних векторів&nbsp;— академічний сайт)'' {{ref-en}}
* [http://onlineprediction.net/?n=Main.KernelMethods Стаття Kernel Methods на onlineprediction.net] {{ref-en}}

[[Категорія:Ядрові методи для машинного навчання]]
[[Категорія:Геостатистика]]
[[Категорія:Алгоритми класифікації]]