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

В машинному навчанні ядрові методи (Шаблон:Lang-en) — це клас алгоритмів для розпізнавання образів, найвідомішим представником якого є метод опорних векторів (Шаблон:Lang-en). Загальна задача розпізнавання образів полягає у знаходженні та вивченні основних типів відношень (наприклад, кластерів, ранжування, головних компонент, кореляцій, класифікацій) у наборах даних. Для багатьох алгоритмів, які розв'язують ці задачі, дані в сирому представленні має бути явним чином перетворено на представлення у вигляді векторів ознак через визначене користувачем відображення ознак (Шаблон:Lang-en): на противагу цьому ядрові методи вимагають лише вказаного користувачем ядра (Шаблон:Lang-en), тобто, функції подібності над парами точок даних у сирому представленні.

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

До алгоритмів, здатних працювати з ядрами, належать Шаблон:Нп, метод опорних векторів (Шаблон:Lang-en), ґаусові процеси, метод головних компонент (Шаблон:Lang-en), канонічно-кореляційний аналіз, гребенева регресія, спектральне кластерування, лінійні адаптивні фільтри та багато інших. Будь-яку лінійну модель може бути перетворено на нелінійну шляхом застосування до неї ядрового трюку: заміни її ознак (провісників) ядровою функцією.Шаблон:Citation needed

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

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

Ядрові методи можливо розглядати як навчання на прикладах: замість навчання якогось фіксованого набору параметрів, які відповідають ознакам їхніх входів, вони натомість «запам'ятовують» $i$-тий тренувальний зразок $({𝐱}_i,y_i)$ та навчаються відповідної йому ваги $w_i$. Для даних, відсутніх у тренувальному наборі, передбачення здійснюється застосуванням функції подібності $k$, яку називають ядром (Шаблон:Lang-en), до неміченого входу ${𝐱}^{\prime }$ та кожного із тренувальних входів ${𝐱}_i$. Наприклад, ядрований бінарний класифікатор зазвичай обчислює зважену суму подібностей

$\hat{y}=\mathrm{sgn}\sum _{i=1}^n{w}_i{y}_{i}k({𝐱}_i,{𝐱}^{\prime })$,

де

• $\hat{y}\in \{-1,+1\}$ є передбаченою ядрованим бінарним класифікатором міткою для неміченого входу ${𝐱}^{\prime }$, справжня прихована мітка $y$ якого нас і цікавить;
• $k:𝒳\times 𝒳\to ℝ$ є ядровою функцією, яка вимірює подібність будь-якої пари входів $𝐱,{𝐱}^{\prime }\in 𝒳$;
• сума пробігає Шаблон:Mvar мічених зразків $\{({𝐱}_i,y_i){\}}_{i=1}^n$ тренувального набору класифікатора, де $y_i\in \{-1,+1\}$;
• $w_i\in ℝ$ є вагами тренувальних зразків, визначеними згідно алгоритму навчання;
• функція знаку $\mathrm{sgn}$ визначає, чи виходить передбачена класифікація $\hat{y}$ позитивною, чи негативною.

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

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

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

Ядровий трюк уникає явного відображення, потрібного для тощо, щоби лінійні алгоритми навчання навчалися нелінійної функції або Шаблон:Нп. Для всіх $𝐱$ та ${𝐱}^{\prime }$ у вхідному просторі $𝒳$ певні функції $k(𝐱,{𝐱}^{\prime })$ може бути виражено як внутрішній добуток в іншому просторі $𝒱$. Функцію $k:𝒳\times 𝒳\to ℝ$ часто називають ядром або Шаблон:Нп. Слово «ядро» використовують в математиці для позначення зважувальної функції зваженої суми або інтегралу.

Деякі задачі в машинному навчанні мають складнішу структуру, ніж просто довільна зважувальна функція $k$. Обчислювання робиться набагато простішим, якщо ядро може бути записано в вигляді «відображення ознак» $\phi :𝒳\to 𝒱$, яке задовольняє

$k(𝐱,{𝐱}^{\prime })=⟨\phi (𝐱),\phi ({𝐱}^{\prime }){⟩}_{𝒱}.$

Ключовим обмеженням є те, що $⟨\cdot ,\cdot {⟩}_{𝒱}$ мусить бути власним внутрішнім добутком. З іншого боку, явне представлення $\phi$ не є необхідним, поки $𝒱$ є Шаблон:Нп. Ця альтернатива випливає з Шаблон:Нп: неявно визначена функція $\phi$ існує тоді, коли простір $𝒳$ може бути споряджено придатною мірою, яка забезпечувала би, щоби функція $k$ задовольняла Шаблон:Нп.

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

$\sum _{i=1}^n\sum _{j=1}^{n}k({𝐱}_i,{𝐱}_j)c_i{c}_j⩾0.$

Якщо це підсумовування виконується для всіх скінченних послідовностей точок $({𝐱}_1,\dots ,{𝐱}_n)$ в $𝒳$ і всіх варіантів вибору $n$ дійснозначних коефіцієнтів $(c_1,\dots ,c_n)$ (пор. Шаблон:Нп), то функція $k$ задовольняє умову Мерсера.

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

Теоретично, матриця Грама $𝐊\in {ℝ}^{n\times n}$ по відношенню до $\{{𝐱}_1,\dots ,{𝐱}_n\}$ (яку іноді також називають «ядровою матрицею», Шаблон:Lang-en), мусить бути додатно напівозначеною. Емпірично, для евристик машинного навчання варіанти обрання функції $k$, які не задовольняють умову Мерсера, все ще можуть працювати прийнятно, якщо $k$ щонайменше наближує інтуїтивне уявлення про подібність. Незалежно від того, чи є $k$ мерсеровим ядром, $k$ все одно можуть називати «ядром».

Якщо ядрова функція $k$ є також і Шаблон:Нп, як при застосуванні в ґаусових процесах, то матриця Грама $𝐊$ можуть також називати коваріаційною матрицею.

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

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

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

• Шаблон:Нп
• Шаблон:Нп
• Ядрове згладжування
• Шаблон:Нп
• Шаблон:Нп
• Стрічкові ядра

Див. також

• Шаблон:Нп
• Шаблон:Нп

Джерела

Література

Книги

• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en

Посилання

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