Нұсқаулықтарды талдау алгоритмдерінің класы

Кіріспе

Үлгілерді талдау алгоритмдерінің класы

Машиналық оқытуда ядролық машиналар – үлгілерді талдау алгоритмдерінің класы болып табылады, оның ең танымал мүшесі – қолдау векторлық машинасы (SVM). Бұл әдістер сызықтық емес мәселелерді шешу үшін сызықтық жіктегіштерді пайдалануды қамтиды. Үлгілерді талдаудың жалпы міндеті – дерек жиынтықтарындағы жалпы қатынастарды (мысалы, кластерлер, рейтингтер, негізгі компоненттер, корреляциялар, жіктелімдер) табу және зерттеу. Бұл міндеттерді шешетін көптеген алгоритмдер үшін шикі деректер пайдаланушы белгілеген белгі картасы арқылы ерекшелік векторлық бейнелеулерге айналдырылуы керек: керісінше, ядролық әдістер тек пайдаланушы белгілеген ядроны, яғни барлық дерек нүктелерінің жұптары бойынша ішкі көбейтулерді пайдалана отырып есептелген ұқсастық функциясын қажет етеді. Ядролық машиналардағы белгі картасы шексіз өлшемді, бірақ Representer теоремасы бойынша пайдаланушы кірісінен шекті өлшемді матрицаны қажет етеді. Ядролық машиналар параллель өңдеусіз бірнеше мыңнан астам мысалдан тұратын дерек жиынтығын есептеуде баяу болады. Ядролық әдістер өздерінің атын ядролық функцияларды пайдалануға байланысты алады, олар деректердің координаттарын ешқашан есептемей, жоғары өлшемді, жасырын ерекшелік кеңістігінде жұмыс істеуге мүмкіндік береді, тек ерекшелік кеңістігіндегі барлық дерек жұптарының бейнелері арасындағы ішкі көбейтулерді есептеу арқылы. Бұл операция көбінесе координаталарды нақты есептеуден есептеу жағынан тиімді. Бұл тәсіл «ядролық амал» деп аталады. Ядролық функциялар келесі деректерге – тізбектерге, графтарға, мәтінге, суреттерге, сондай-ақ векторларға енгізілді. Ядролармен жұмыс істей алатын алгоритмдерге ядролық перцептрон, қолдау векторлық машиналар (SVM), Гаусс процестері, негізгі компоненттер талдауы (PCA), каноникалық корреляциялық талдау, қырқа регрессиясы, спектрлік кластерлеу, сызықтық адаптивті сүзгілер және тағы да басқалары жатады. Көптеген ядролық алгоритмдер конвекстік оптимизацияға немесе меншік мәселелерге негізделген және статистикалық тұрғыдан жақсы негізделген. Әдетте олардың статистикалық қасиеттері статистикалық оқыту теориясын (мысалы, Радемахер күрделілігін пайдалану арқылы) пайдалана отырып талданады.

In machine learning, kernel machines are a class of algorithms for pattern analysis, whose best known member is the support vector machine (SVM). These methods involve using linear classifiers to solve nonlinear problems. The general task of pattern analysis is to find and study general types of relations (for example clusters, rankings, principal components, correlations, classifications) in datasets. For many algorithms that solve these tasks, the data in raw representation have to be explicitly transformed into feature vector representations via a user specified feature map: in contrast, kernel methods require only a user specified kernel, i. e., a similarity function over all pairs of data points computed using inner products. The feature map in kernel machines is infinite dimensional but only requires a finite dimensional matrix from user input according to the Representer theorem. Kernel machines are slow to compute for datasets larger than a couple of thousand examples without parallel processing. Kernel methods owe their name to the use of kernel functions, which enable them to operate in a high dimensional, implicit feature space without ever computing the coordinates of the data in that space, but rather by simply computing the inner products between the images of all pairs of data in the feature space. This operation is often computationally cheaper than the explicit computation of the coordinates. This approach is called the "kernel trick". Kernel functions have been introduced for sequence data, graphs, text, images, as well as vectors. Algorithms capable of operating with kernels include the kernel perceptron, support vector machines (SVM), Gaussian processes, principal components analysis (PCA), canonical correlation analysis, ridge regression, spectral clustering, linear adaptive filters and many others. Most kernel algorithms are based on convex optimization or eigenproblems and are statistically well founded. Typically, their statistical properties are analyzed using statistical learning theory (for example, using Rademacher complexity).

Математика: ядролық амал

Ядролық тәсіл сызықтық емес функцияларды немесе шешім шекарасын оқыту үшін сызықтық оқыту алгоритмдерін алуға қажетті нақты бейнелеуден аулақтайды. Барлық және кіріс кеңістігіндегі белгілі бір функцияларды басқа кеңістікте ішкі көбейтінді ретінде өрнектеуге болады. Функция көбінесе ядро немесе ядролық функция деп аталады. Математикада "ядро" сөзі салмақталған соманың немесе интегралдың салмақтау функциясын білдіру үшін қолданылады. Машиналық оқытудағы кейбір мәселелер кездейсоқ салмақ функциясынан гөрі көбірек құрылымға ие. Егер ядроны "ерекшеліктер картасы" түрінде жазу мүмкін болса, есептеу әлдеқайда жеңілдетіледі. Екінші жағынан, егер кеңістік ішкі көбейтінді кеңістігі болса, үшін нақты бейнелеу қажет емес. Мерсер теоремасынан мынасы келеді: егер кеңістік функция Мерсер шартын қанағаттандыратындай тиісті өлшеммен жабдықталса, онда имплицитті түрде анықталған функция бар. Мерсер теоремасы сызықтық алгебрадан алынған нәтиженің жалпылауына ұқсас, ол кез келген оң анықталған матрицаны ішкі көбейтіндімен байланыстырады. Шындығында, Мерсер шартын осы қарапайым жағдайға дейін тоғытуға болады. Егер біз барлық нүктелердің санын санау үшін санау шарасын таңдасақ, онда Мерсер теоремасындағы интеграл қосындыға дейін тоғытылады.

The kernel trick avoids the explicit mapping that is needed to get linear learning algorithms to learn a nonlinear function or decision boundary. For all and in the input space , certain functions can be expressed as an inner product in another space The function is often referred to as a kernel or a kernel function. The word "kernel" is used in mathematics to denote a weighting function for a weighted sum or integral. Certain problems in machine learning have more structure than an arbitrary weighting function The computation is made much simpler if the kernel can be written in the form of a "feature map" which satisfies

The key restriction is that must be a proper inner product. On the other hand, an explicit representation for is not necessary, as long as is an inner product space. The alternative follows from Mercer's theorem: an implicitly defined function exists whenever the space can be equipped with a suitable measure ensuring the function satisfies Mercer's condition. Mercer's theorem is similar to a generalization of the result from linear algebra that associates an inner product to any positive definite matrix. In fact, Mercer's condition can be reduced to this simpler case. If we choose as our measure the counting measure for all , which counts the number of points inside the set , then the integral in Mercer's theorem reduces to a summation

If this summation holds for all finite sequences of points in and all choices of real valued coefficients (cf. positive definite kernel), then the function satisfies Mercer's condition. Some algorithms that depend on arbitrary relationships in the native space would, in fact, have a linear interpretation in a different setting: the range space of The linear interpretation gives us insight about the algorithm. Furthermore, there is often no need to compute directly during computation, as is the case with support vector machines. Some cite this running time shortcut as the primary benefit. Researchers also use it to justify the meanings and properties of existing algorithms. Theoretically, a Gram matrix with respect to (sometimes also called a "kernel matrix"), where , must be positive semi definite (PSD). Empirically, for machine learning heuristics, choices of a function that do not satisfy Mercer's condition may still perform reasonably if at least approximates the intuitive idea of similarity. Regardless of whether is a Mercer kernel, may still be referred to as a "kernel". If the kernel function is also a covariance function as used in Gaussian processes, then the Gram matrix can also be called a covariance matrix.

Егер бұл қосынды барлық шекті нүктелер тізбегі және барлық нақты коэффициенттердің таңдаулары үшін орындалса (мысалы, оң анықталған ядро), онда функция Мерсер шартын қанағаттандырады. Негізгі кеңістіктегі кездейсоқ қатынастарға тәуелді кейбір алгоритмдер, шын мәнінде, басқа жағдайда сызықтық интерпретацияға ие болады: сызықтық интерпретация алгоритм туралы түсінік береді. Сонымен қатар, көбінесе есептеу кезінде тікелей есептеудің қажеті жоқ, мысалы, қолдау векторлық машиналарда. Кейбіреулер осы уақытты үнемдеуді негізгі артықшылық деп атайды. Зерттеушілер оны қолданылып жүрген алгоритмдердің мағынасын және қасиеттерін негіздеу үшін де пайдаланады. Теориялық тұрғыдан алғанда, грам матрицасы (кейде "ядролық матрица" деп те аталады), онда , оң жартылай анықталған (PSD) болуы керек. Эмпирикалық тұрғыдан алғанда, машиналық оқыту эвристикасы үшін Мерсер шартын қанағаттандырмайтын функцияның таңдауы, егер ол кем дегенде ұқсастық туралы интуитивті идеяға жақындаса, әлі де ақылға қонымды нәтижелер бере алады. Мерсер ядросы болып табыла ма, жоқ па, оған "ядро" деп атауға болады. Егер ядролық функция Гаусс процестерінде қолданылатын ковариациялық функция болса, онда грам матрицасын ковариациялық матрица деп те атауға болады.

Қолданбалар

Ядролық әдістердің қолданылу салалары кең және геостатистика, кригинг, кері қашықтық салмақтау, 3D реконструкция, биоинформатика, химиоинформатика, ақпаратты ізкесу және қолмен жазылған мәтінді тану сияқты салаларды қамтиды.