Байланысты емес жіктегіштерді үйрету алгоритмі (Binary Classifiersді оқыту алгоритмі)

Кіріспе

Бинарлық жіктегіштерді бақыланатын оқыту алгоритмі

Машиналық оқытуда перцептрон (немесе Маккалок-Питтс нейроны) – бинарлық жіктегіштерді бақыланатын оқытуға арналған алгоритм. Бинарлық жіктегіш – сандар векторы түрінде ұсынылған кіріс, белгілі бір сыныпқа жата ма, жатпай ма, деген шешім қабылдайтын функция. Бұл – сызықтық жіктегіштің бір түрі, яғни белгілі бір ерекшеліктер векторымен салмақтар жиынтығын біріктіретін сызықтық болжам функциясы негізінде болжамдар жасайтын жіктеу алгоритмі.

Ақпарат теориясы

Ақпарат теориясы тұрғысынан қарағанда, K кірісі бар бір перцептрон 2K бит ақпарат сыйымдылығына ие. Бұл нәтиже Томас Коверге тиесілі. Нақтырақ айтқанда, K өлшемде N нүктені сызықты түрде бөлудің қанша тәсілі бар екенін қарастырайық, онда K үлкен болғанда, жақын болса, бірақ жақын болмаса. Басқаша айтқанда, бір перцептрон бірлігі N нүктенің екілік белгілерінің кездейсоқ жиынтығын жақсырақ жаттай алады, бірақ жаттай алмайды.

Буль функциясы

Тек бінарлы кіріспен жұмыс істегенде перцептрон сызықтық бөлінетін Буль функциясы немесе шекті Буль функциясы деп аталады. n кірісіндегі шекті Буль функцияларының сандар тізбегі OEIS A000609 болып табылады. Мәні тек белгілі бір жағдайға дейін ғана нақты белгілі, бірақ шамасының реті өте дәл белгілі: оның жоғарғы және төменгі шегі бар. Кез келген Бульдік сызықтық шектік функцияны тек бүтін сандық салмақтармен іске асыруға болады. Сонымен қатар, бір бүтін сан салмақ параметрін көрсетуге қажетті және жеткілікті бит саны: . Егер оқу жиынтығы сызықтық түрде бөлінетін болса, онда перцептрон шекті сандағы қателер жасағаннан кейін сәйкестікке (конвергенцияға) жетеді. Теорема Розенблатт және авторлар тобымен дәлелденген. Келесі қарапайым дәлелдеу Новиковқа (1962) тиесілі. Дәлелдеудің идеясы салмақ векторы әрқашан теріс скалярлық көбейтіндісі бар бағытта шектелген мөлшерде түзетіледі, сондықтан ол жоғарыдан шектелуі мүмкін, мұнда t – салмақ векторының өзгерістерінің саны. Алайда, ол төменнен O(t) арқылы шектелуі мүмкін, себебі егер қанағаттандыратын (белгісіз) салмақ векторы болса, онда әрбір өзгеріс осы (белгісіз) бағытта оң мөлшерде алға жылжиды, бұл тек кіріс векторына байланысты. thumb|300px|Екі нүктелер класы және оларды бөлетін шексіз көп сызықтық шекаралардың екеуі. Шекаралар бір-біріне дерлік тік бұрышпен орналасқан болса да, перцептрон алгоритмі олардың арасынан таңдау жасай алмайды. Перцептрон алгоритмі сызықтық түрде бөлінетін оқу жиынтығы жағдайында қандай да бір шешімге сәйкестікке (конвергенцияға) жететіні кепілдендірілген, бірақ ол кез келген шешімді таңдауы мүмкін, ал проблемалар әртүрлі сападағы көптеген шешімдерді қабылдауы мүмкін. Оптималды тұрақтылыққа ие перцептрон, қазіргі кезде сызықтық қолдау векторы машинасы ретінде танымал, осы мәселені шешу үшін жасалған (Krauth және Mezard, 1987).

Перцептронның циклдеу теоремасы

Деректер жиынтығы сызықтық түрде бөлінбейтін болса, онда бір перцептронның жуысуы мүмкін емес. Дегенмен, бұл фактіні алғаш Брэдли Эфрон дәлелдеген.

Буль функцияларын үйрену

Деректер жиынтығын қарастырайық, онда n өлшемді гиперкубтың төбелері , яғни, барлық оң мәні бар деректер нүктелері , және керісінше. Перцептронның конвергенция теоремасы бойынша, перцептрон ең көп дегенде қате жасағаннан кейін конвергенцияға жетеді. Егер біз осы міндетті орындау үшін логикалық бағдарлама жазсақ, әрбір оң мысал координаттардың бірі дұрыс екенін көрсетеді, ал әрбір теріс мысал оның толықтырғышы оң мысал екенін көрсетеді. Барлық белгілі оң мысалдарды жинап, бір координатты қоспағанда, қалғанын жоямыз, сонда деректер жиынтығы оқытылған болады. Бұл шектеу ең жаман жағдайда асимптотикалық түрде тығыз. Ең жаман жағдайда, алғашқы ұсынылған мысал толығымен жаңа болып келеді және бит ақпарат береді, бірақ әрбір келесі мысал бұрынғы мысалдардан минималды түрде өзгеше болады және 1 бит ақпарат береді. мысалдан кейін бит ақпарат болады, бұл перцептрон үшін жеткілікті (бит ақпаратпен). Сызықтық түрде ажыратылатын жағдайда, ол оқу мәселесін шешеді – қаласа, тіпті оңтайлы тұрақтылықпен (сыныптар арасындағы максималды арақашықтық). Ажыратылмаған деректер жиынтығы үшін ол аз ғана қате жіктелімдермен шешім береді. Барлық жағдайларда алгоритм оқу процесінде, бұрынғы күйлерді жаттамай және стохастикалық секірулерсіз, шешімге қадам-қадаммен жақындайды. Конвергенция ажыратылатын деректер жиынтығы үшін жаһандық оптималдыққа, ал ажыратылмаған деректер жиынтығы үшін жергілікті оптималдыққа қатысты. Дауыс берген перцептрон (Freund and Schapire, 1999) – бірнеше салмақталған перцептрон қолданатын нұсқа. Алгоритм әрбір мысал қате жіктелгенде жаңа перцептрон бастайды, салмақтар векторын соңғы перцептронның соңғы салмақтарымен инициализациялайды. Әр перцептронға дұрыс жіктелген мысалдар санына сәйкес келетін қосымша салмақ беріледі, ал соңында шығыс барлық перцептронның салмақталған дауысы болады. Ажыратылатын мәселелерде перцептрон оқыту сыныптар арасындағы ең үлкен ажырату шегін табуға бағытталған. Оптималды тұрақтылық перцептроны итеративтік оқыту және оптимизациялау схемалары арқылы анықталуы мүмкін, мысалы, Min Over алгоритмі (Krauth and Mezard, 1987). AdaTron сәйкес келетін квадратикалық оптимизациялау мәселесі дөңгелек екендігін пайдаланады. Оптималды тұрақтылық перцептроны, ядролық амалмен бірге, қолдау векторлық машинаның тұжырымдық негіздері болып табылады. Перцептрон сонымен қатар тұрақты кездейсоқ салмақтардан тұратын алдын ала өңдеу қабатын, шекті шығыс бірліктерін қолданды. Бұл перцептронға аналогты үлгілерді екілік кеңістікке проекциялау арқылы жіктеуге мүмкіндік берді. Шындығында, жеткілікті жоғары өлшемді проекциялық кеңістік үшін үлгілер сызықтық түрде ажыратылатын болады. Бірнеше қабаттарды пайдаланбай, сызықтық емес мәселелерді шешудің тағы бір жолы – жоғары реттік желілерді (сигма-пи бірлігі) пайдалану. Бұл желі түрінде кіріс векторындағы әрбір элемент көбейтілген кірістердің әрбір жұптық комбинациясымен (екінші реттік) кеңейтіледі. Бұл n-реттік желіге дейін кеңейтілуі мүмкін. Алайда, ең жақсы жіктеуіш барлық оқу деректерін мінсіз жіктейтінін естен шығармаған жөн. Шындығында, егер бізде деректер эквиварианттық Гаусс үлестірімдерінен келетіні туралы алдын ала шектеу болса, кіріс кеңістігіндегі сызықтық ажырату оптималды, ал сызықтық емес шешім артық сәйкестікке (overfitting) ұшырайды. Басқа сызықтық жіктеу алгоритмдеріне Winnow, қолдау векторлық машинасы және логистикалық регрессия кіреді.

Consider a dataset where the are from , that is, the vertices of an n dimensional hypercube centered at origin, and That is, all data points with positive have , and vice versa. By the perceptron convergence theorem, a perceptron would converge after making at most mistakes. If we were to write a logical program to perform the same task, each positive example shows that one of the coordinates is the right one, and each negative example shows that its complement is a positive example. By collecting all the known positive examples, we eventually eliminate all but one coordinate, at which point the dataset is learned. This bound is asymptotically tight in terms of the worst case. In the worst case, the first presented example is entirely new, and gives bits of information, but each subsequent example would differ minimally from previous examples, and gives 1 bit each. After examples, there are bits of information, which is sufficient for the perceptron (with bits of information). In the linearly separable case, it will solve the training problem – if desired, even with optimal stability (maximum margin between the classes). For non separable data sets, it will return a solution with a small number of misclassifications. In all cases, the algorithm gradually approaches the solution in the course of learning, without memorizing previous states and without stochastic jumps. Convergence is to global optimality for separable data sets and to local optimality for non separable data sets. The Voted Perceptron (Freund and Schapire, 1999), is a variant using multiple weighted perceptrons. The algorithm starts a new perceptron every time an example is wrongly classified, initializing the weights vector with the final weights of the last perceptron. Each perceptron will also be given another weight corresponding to how many examples do they correctly classify before wrongly classifying one, and at the end the output will be a weighted vote on all perceptrons. In separable problems, perceptron training can also aim at finding the largest separating margin between the classes. The so called perceptron of optimal stability can be determined by means of iterative training and optimization schemes, such as the Min Over algorithm (Krauth and Mezard, 1987) AdaTron uses the fact that the corresponding quadratic optimization problem is convex. The perceptron of optimal stability, together with the kernel trick, are the conceptual foundations of the support vector machine. The perceptron further used a pre processing layer of fixed random weights, with thresholded output units. This enabled the perceptron to classify analogue patterns, by projecting them into a binary space. In fact, for a projection space of sufficiently high dimension, patterns can become linearly separable. Another way to solve nonlinear problems without using multiple layers is to use higher order networks (sigma pi unit). In this type of network, each element in the input vector is extended with each pairwise combination of multiplied inputs (second order). This can be extended to an n order network. It should be kept in mind, however, that the best classifier is not necessarily that which classifies all the training data perfectly. Indeed, if we had the prior constraint that the data come from equi variant Gaussian distributions, the linear separation in the input space is optimal, and the nonlinear solution is overfitted. Other linear classification algorithms include Winnow, support vector machine, and logistic regression.

Көп сыныпты перцептрон

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

Оқыту процесі мысалдарды қайтадан қарастырып, әрқайсысы үшін шығысты болжайды, болжаған шығыс мақсатты шығысқа сәйкес келсе салмақтарды өзгеріссіз қалдырады, ал сәйкес келмесе өзгертеді. Жаңарту келесідей жүзеге асырылады:

Бұл көп сыныпты кері байланыс формуласы, егер ерекшеліктер векторы нақты сандық болса, кіріс жиынынан таңдалса және болса, бастапқы перцептронға дейін тоғысып қалады. Кейбір мәселелер үшін кіріс/шығыс бейнелеулері мен ерекшеліктерін оңтайлы таңдау арқылы, тіпті өте үлкен немесе шексіз жиынтықтан таңдалған жағдайда да, тиімді шешім табуға болады. 2002 жылдан бері перцептронды оқыту табиғи тілді өңдеу саласында сөздердің түрлерін анықтау және синтаксистік талдау сияқты міндеттерде кеңінен қолданылуда (Collins, 2002). Сонымен қатар, ол үлестірілген есептеу ортасындағы үлкен көлемді машиналық оқыту мәселелерінде де қолданылады.