В машинному навчанні ядрові методи (англ. 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]).
Обґрунтування та неформальне пояснення
Ядрові методи можливо розглядати як навчання на прикладах: замість навчання якогось фіксованого набору параметрів, які відповідають ознакам їхніх входів, вони натомість «запам'ятовують» -тий тренувальний зразок та навчаються відповідної йому ваги . Для даних, відсутніх у тренувальному наборі, передбачення здійснюється застосуванням функції подібності , яку називають ядром (англ. kernel), до неміченого входу та кожного із тренувальних входів . Наприклад, ядрований бінарний класифікатор зазвичай обчислює зважену суму подібностей
- ,
де
- є передбаченою ядрованим бінарним класифікатором міткою для неміченого входу , справжня прихована мітка якого нас і цікавить;
- є ядровою функцією, яка вимірює подібність будь-якої пари входів ;
- сума пробігає n мічених зразків тренувального набору класифікатора, де ;
- є вагами тренувальних зразків, визначеними згідно алгоритму навчання;
- функція знаку визначає, чи виходить передбачена класифікація позитивною, чи негативною.
Ядрові класифікатори було описано ще в 1960-х роках із винайденням [en]. Вони досягли великого піднесення разом з популярністю опорно-векторних машин (ОВМ) у 1990-х роках, коли було виявлено, що ОВМ є конкурентноздатними в порівнянні зі нейронними мережами на таких задачах як розпізнавання рукописного введення.
Математика: ядровий трюк
Ядровий трюк уникає явного відображення, потрібного для тощо, щоби лінійні алгоритми навчання навчалися нелінійної функції або [en]. Для всіх та у вхідному просторі певні функції може бути виражено як внутрішній добуток в іншому просторі . Функцію часто називають ядром або [en]. Слово «ядро» використовують в математиці для позначення зважувальної функції зваженої суми або інтегралу.
Деякі задачі в машинному навчанні мають складнішу структуру, ніж просто довільна зважувальна функція . Обчислювання робиться набагато простішим, якщо ядро може бути записано в вигляді «відображення ознак» , яке задовольняє
Ключовим обмеженням є те, що мусить бути власним внутрішнім добутком. З іншого боку, явне представлення не є необхідним, поки є [en]. Ця альтернатива випливає з [en]: неявно визначена функція існує тоді, коли простір може бути споряджено придатною мірою, яка забезпечувала би, щоби функція задовольняла [en].
Теорема Мерсера є подібною до узагальнення того наслідку з лінійної алгебри, що (пов'язує внутрішній добуток із будь-якою додатноозначеною матрицею). Фактично, умову Мерсера може бути зведено до цього простішого прояву. Якщо ми оберемо як нашу міру лічильну міру для всіх , яка лічить число точок всередині множини , то інтеграл у теоремі Мерсера зводиться до підсумовування
Якщо це підсумовування виконується для всіх скінченних послідовностей точок в і всіх варіантів вибору дійснозначних коефіцієнтів (пор. [en]), то функція задовольняє умову Мерсера.
Деякі алгоритми, які залежать від довільних взаємозв'язків у рідному просторі , фактично мають лінійну інтерпретацію за іншої постановки: області значень . Лінійна інтерпретація дає нам прояснення алгоритму. Понад те, часто немає потреби під час обчислень обчислювати безпосередньо, як у випадку методу опорних векторів. Деякі дослідники посилаються на цю раціоналізацію часу як на головну перевагу. Дослідники також використовують її для обґрунтування сенсу та властивостей наявних алгоритмів.
Теоретично, матриця Грама по відношенню до (яку іноді також називають «ядровою матрицею», англ. "kernel matrix"), мусить бути додатно напівозначеною. Емпірично, для евристик машинного навчання варіанти обрання функції , які не задовольняють умову Мерсера, все ще можуть працювати прийнятно, якщо щонайменше наближує інтуїтивне уявлення про подібність. Незалежно від того, чи є мерсеровим ядром, все одно можуть називати «ядром».
Якщо ядрова функція є також і [en], як при застосуванні в ґаусових процесах, то матриця Грама можуть також називати коваріаційною матрицею.
Застосування
Сфери застосування ядрових методів є різноманітними, до них належать геостатистика,кригінг, [en], об'ємна відбудова, біоінформатика, хемоінформатика, витягування інформації та розпізнавання рукописного введення.
Популярні ядра
- [en]
- [en]
- Ядрове згладжування
- [en]
- [en]
- Стрічкові ядра
Див. також
- [en]
- [en]
Джерела
Цитати
- Theodoridis, Sergios (2008). Pattern Recognition. Elsevier B.V. с. 203. ISBN . (англ.)
- 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. (англ.)
- Kernel Methods in Machine Learning. — 2008. — 7 липня. (англ.)
- ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Foundations of Machine Learning (англ.). USA, Massachusetts: MIT Press. ISBN .
- Sewell, Martin. . www.svms.org. Архів оригіналу за 15 жовтня 2018. Процитовано 16 жовтня 2016. (англ.)
- Gaussian Processes for Machine Learning. — 2006. — 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 (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V mashinnomu navchanni yadrovi metodi angl kernel methods ce klas algoritmiv dlya rozpiznavannya obraziv najvidomishim predstavnikom yakogo ye metod opornih vektoriv angl support vector machine SVM Zagalna zadacha rozpiznavannya obraziv polyagaye u znahodzhenni ta vivchenni osnovnih tipiv vidnoshen napriklad klasteriv ranzhuvannya golovnih komponent korelyacij klasifikacij u naborah danih Dlya bagatoh algoritmiv yaki rozv yazuyut ci zadachi dani v siromu predstavlenni maye buti yavnim chinom peretvoreno na predstavlennya u viglyadi vektoriv oznak cherez viznachene koristuvachem vidobrazhennya oznak angl feature map na protivagu comu yadrovi metodi vimagayut lishe vkazanogo koristuvachem yadra angl kernel tobto funkciyi podibnosti nad parami tochok danih u siromu predstavlenni Yadrovi metodi zavdyachuyut svoyeyu nazvoyu zastosuvannyu en yaki dozvolyayut yim diyati v neyavnomu prostori oznak visokoyi vimirnosti navit bez obchislennya koordinat danih u comu prostori natomist prosto obchislyuyuchi en zobrazhen vsih par danih u comu prostori oznak Cya operaciya chasto ye obchislyuvalno mensh vitratnoyu nizh yavne obchislennya koordinat Cej pidhid nazivayut yadrovim tryukom angl kernel trick Yadrovi funkciyi bulo predstavleno dlya danih poslidovnostej en tekstiv zobrazhen yak i dlya vektoriv Do algoritmiv zdatnih pracyuvati z yadrami nalezhat en metod opornih vektoriv angl support vector machines SVM gausovi procesi metod golovnih komponent angl principal components analysis PCA kanonichno korelyacijnij analiz grebeneva regresiya spektralne klasteruvannya linijni adaptivni filtri ta bagato inshih Bud yaku en mozhe buti peretvoreno na nelinijnu shlyahom zastosuvannya do neyi yadrovogo tryuku zamini yiyi oznak provisnikiv yadrovoyu funkciyeyu dzherelo Bilshist yadrovih algoritmiv gruntuyutsya na opuklij optimizaciyi abo vlasnih vektorah i ye statistichno obgruntovanimi Yak pravilo yihni statistichni vlastivosti analizuyut za dopomogoyu teoriyi statistichnogo navchannya napriklad za dopomogoyu en Obgruntuvannya ta neformalne poyasnennyaYadrovi metodi mozhlivo rozglyadati yak navchannya na prikladah zamist navchannya yakogos fiksovanogo naboru parametriv yaki vidpovidayut oznakam yihnih vhodiv voni natomist zapam yatovuyut i displaystyle i tij trenuvalnij zrazok xi yi displaystyle mathbf x i y i ta navchayutsya vidpovidnoyi jomu vagi wi displaystyle w i Dlya danih vidsutnih u trenuvalnomu nabori peredbachennya zdijsnyuyetsya zastosuvannyam funkciyi podibnosti k displaystyle k yaku nazivayut yadrom angl kernel do nemichenogo vhodu x displaystyle mathbf x ta kozhnogo iz trenuvalnih vhodiv xi displaystyle mathbf x i Napriklad yadrovanij binarnij klasifikator zazvichaj obchislyuye zvazhenu sumu podibnostej y sgn i 1nwiyik xi x displaystyle hat y operatorname sgn sum i 1 n w i y i k mathbf x i mathbf x de y 1 1 displaystyle hat y in 1 1 ye peredbachenoyu yadrovanim binarnim klasifikatorom mitkoyu dlya nemichenogo vhodu x displaystyle mathbf x spravzhnya prihovana mitka y displaystyle y yakogo nas i cikavit k X X R displaystyle k colon mathcal X times mathcal X to mathbb R ye yadrovoyu funkciyeyu yaka vimiryuye podibnist bud yakoyi pari vhodiv x x X displaystyle mathbf x mathbf x in mathcal X suma probigaye n michenih zrazkiv xi yi i 1n displaystyle mathbf x i y i i 1 n trenuvalnogo naboru klasifikatora de yi 1 1 displaystyle y i in 1 1 wi R displaystyle w i in mathbb R ye vagami trenuvalnih zrazkiv viznachenimi zgidno algoritmu navchannya funkciya znaku sgn displaystyle operatorname sgn viznachaye chi vihodit peredbachena klasifikaciya y displaystyle hat y pozitivnoyu chi negativnoyu Yadrovi klasifikatori bulo opisano she v 1960 h rokah iz vinajdennyam en Voni dosyagli velikogo pidnesennya razom z populyarnistyu oporno vektornih mashin OVM u 1990 h rokah koli bulo viyavleno sho OVM ye konkurentnozdatnimi v porivnyanni zi nejronnimi merezhami na takih zadachah yak rozpiznavannya rukopisnogo vvedennya Matematika yadrovij tryukOVM z yadrom zadanim f a b a b a2 b2 i vidtak K x y x y x2y2 Trenuvalni tochki vidobrazheno do 3 vimirnogo prostoru de legko znajti rozdilovu giperploshinu Yadrovij tryuk unikaye yavnogo vidobrazhennya potribnogo dlya tosho shobi linijni algoritmi navchannya navchalisya nelinijnoyi funkciyi abo en Dlya vsih x displaystyle mathbf x ta x displaystyle mathbf x u vhidnomu prostori X displaystyle mathcal X pevni funkciyi k x x displaystyle k mathbf x mathbf x mozhe buti virazheno yak vnutrishnij dobutok v inshomu prostori V displaystyle mathcal V Funkciyu k X X R displaystyle k colon mathcal X times mathcal X to mathbb R chasto nazivayut yadrom abo en Slovo yadro vikoristovuyut v matematici dlya poznachennya zvazhuvalnoyi funkciyi zvazhenoyi sumi abo integralu Deyaki zadachi v mashinnomu navchanni mayut skladnishu strukturu nizh prosto dovilna zvazhuvalna funkciya k displaystyle k Obchislyuvannya robitsya nabagato prostishim yaksho yadro mozhe buti zapisano v viglyadi vidobrazhennya oznak f X V displaystyle varphi colon mathcal X to mathcal V yake zadovolnyaye k x x f x f x V displaystyle k mathbf x mathbf x langle varphi mathbf x varphi mathbf x rangle mathcal V Klyuchovim obmezhennyam ye te sho V displaystyle langle cdot cdot rangle mathcal V musit buti vlasnim vnutrishnim dobutkom Z inshogo boku yavne predstavlennya f displaystyle varphi ne ye neobhidnim poki V displaystyle mathcal V ye en Cya alternativa viplivaye z en neyavno viznachena funkciya f displaystyle varphi isnuye todi koli prostir X displaystyle mathcal X mozhe buti sporyadzheno pridatnoyu miroyu yaka zabezpechuvala bi shobi funkciya k displaystyle k zadovolnyala en Teorema Mersera ye podibnoyu do uzagalnennya togo naslidku z linijnoyi algebri sho pov yazuye vnutrishnij dobutok iz bud yakoyu dodatnooznachenoyu matriceyu Faktichno umovu Mersera mozhe buti zvedeno do cogo prostishogo proyavu Yaksho mi oberemo yak nashu miru lichilnu miru m T T displaystyle mu T T dlya vsih T X displaystyle T subset X yaka lichit chislo tochok vseredini mnozhini T displaystyle T to integral u teoremi Mersera zvoditsya do pidsumovuvannya i 1n j 1nk xi xj cicj 0 displaystyle sum i 1 n sum j 1 n k mathbf x i mathbf x j c i c j geqslant 0 Yaksho ce pidsumovuvannya vikonuyetsya dlya vsih skinchennih poslidovnostej tochok x1 xn displaystyle mathbf x 1 dotsc mathbf x n v X displaystyle mathcal X i vsih variantiv viboru n displaystyle n dijsnoznachnih koeficiyentiv c1 cn displaystyle c 1 dots c n por en to funkciya k displaystyle k zadovolnyaye umovu Mersera Deyaki algoritmi yaki zalezhat vid dovilnih vzayemozv yazkiv u ridnomu prostori X displaystyle mathcal X faktichno mayut linijnu interpretaciyu za inshoyi postanovki oblasti znachen f displaystyle varphi Linijna interpretaciya daye nam proyasnennya algoritmu Ponad te chasto nemaye potrebi pid chas obchislen obchislyuvati f displaystyle varphi bezposeredno yak u vipadku metodu opornih vektoriv Deyaki doslidniki posilayutsya na cyu racionalizaciyu chasu yak na golovnu perevagu Doslidniki takozh vikoristovuyut yiyi dlya obgruntuvannya sensu ta vlastivostej nayavnih algoritmiv Teoretichno matricya Grama K Rn n displaystyle mathbf K in mathbb R n times n po vidnoshennyu do x1 xn displaystyle mathbf x 1 dotsc mathbf x n yaku inodi takozh nazivayut yadrovoyu matriceyu angl kernel matrix musit buti dodatno napivoznachenoyu Empirichno dlya evristik mashinnogo navchannya varianti obrannya funkciyi k displaystyle k yaki ne zadovolnyayut umovu Mersera vse she mozhut pracyuvati prijnyatno yaksho k displaystyle k shonajmenshe nablizhuye intuyitivne uyavlennya pro podibnist Nezalezhno vid togo chi ye k displaystyle k merserovim yadrom k displaystyle k vse odno mozhut nazivati yadrom Yaksho yadrova funkciya k displaystyle k ye takozh i en yak pri zastosuvanni v gausovih procesah to matricya Grama K displaystyle mathbf K mozhut takozh nazivati kovariacijnoyu matriceyu ZastosuvannyaSferi zastosuvannya yadrovih metodiv ye riznomanitnimi do nih nalezhat geostatistika kriging en ob yemna vidbudova bioinformatika hemoinformatika vityaguvannya informaciyi ta rozpiznavannya rukopisnogo vvedennya Populyarni yadra en en Yadrove zgladzhuvannya en en Strichkovi yadraDiv takozh en en DzherelaCitati Theodoridis Sergios 2008 Pattern Recognition Elsevier B V s 203 ISBN 9780080949123 angl 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 Procitovano v 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 angl Kernel Methods in Machine Learning 2008 7 lipnya angl Rostamizadeh Afshin Talwalkar Ameet 2012 Foundations of Machine Learning angl USA Massachusetts MIT Press ISBN 9780262018258 Sewell Martin www svms org Arhiv originalu za 15 zhovtnya 2018 Procitovano 16 zhovtnya 2016 angl Gaussian Processes for Machine Learning 2006 7 lipnya angl 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 angl Literatura Knigi 2004 Kernel Methods for Pattern Analysis Cambridge University Press angl Liu W Principe J Haykin S 2010 Kernel Adaptive Filtering A Comprehensive Introduction Wiley angl PosilannyaKernel Machines Org vebsajt spilnoti angl www support vector machines org literatura oglyad programne zabezpechennya posilannya pov yazani z metodom opornih vektoriv akademichnij sajt angl Stattya Kernel Methods na onlineprediction net angl