Кіріспе
Адаптивті күшейтуге негізделген жіктеу алгоритмі. AdaBoost, Адаптивті Күшейтудің қысқартылған атауы, – 1995 жылы Йоав Фрёнд пен Роберт Шапир жасаған статистикалық жіктеу мета-алгоритмі, олар өз жұмысы үшін 2003 жылы Гёдель сыйлығын алды. Оны орындалуды жақсарту үшін көптеген басқа оқу алгоритмдерімен бірге қолдануға болады. Басқа оқу алгоритмдерінің («әлсіз оқушылар») нәтижелері күшейтілген жіктегіштің соңғы нәтижесін көрсететін салмақталған қосындыға біріктіріледі. Әдетте, AdaBoost екілік жіктеу үшін ұсынылады, бірақ оны көптеген сыныптарға немесе нақты сандар осіндегі шектеулі интервалдарға бейімдеуге болады. AdaBoost адаптивті, яғни келесі әлсіз оқушылар бұрынғы жіктегіштер дұрыс жіктемеген жағдайларға қарай түзетіледі. Кейбір мәселелерде ол басқа оқу алгоритмдеріне қарағанда артық үйлесім проблемасына аз бейімделуі мүмкін. Жеке оқушылар әлсіз болуы мүмкін, бірақ әрқайсысының нәтижесі кездейсоқ табанудан сәл жақсы болса, соңғы модельдің күшті оқушыға жақындауы дәлелденген. AdaBoost көбінесе әлсіз базалық оқушыларды (мысалы, шешім ағаштарын) біріктіру үшін қолданылса да, ол күшті базалық оқушыларды (мысалы, терең шешім ағаштарын) тиімді біріктіре алатыны көрсетілді, бұл одан да дәл модельді құрайды. Әрбір оқу алгоритмі кейбір мәселелерге басқаларынан жақсырақ сәйкес келеді және деректер жиынтығында оңтайлы нәтижеге жету үшін әдетте көптеген параметрлер мен конфигурацияларды реттеуді қажет етеді. AdaBoost (шешім ағаштары әлсіз оқушылар ретінде) көбінесе қораптан шыққандағы ең жақсы жіктегіш ретінде танылады. Шешім ағаштарын оқыту кезінде AdaBoost алгоритмінің әр кезеңінде әрбір оқу үлгісінің салыстырмалы «қиындығы» туралы жиналған ақпарат ағаш өсіру алгоритміне беріледі, сондықтан келесі ағаштар жіктеуге қиын жағдайларға көбірек назар аударады.
AdaBoost, short for Adaptive Boosting, is a statistical classification meta algorithm formulated by Yoav Freund and Robert Schapire in 1995, who won the 2003 Gödel Prize for their work. It can be used in conjunction with many other types of learning algorithms to improve performance. The output of the other learning algorithms ('weak learners') is combined into a weighted sum that represents the final output of the boosted classifier. Usually, AdaBoost is presented for binary classification, although it can be generalized to multiple classes or bounded intervals on the real line. AdaBoost is adaptive in the sense that subsequent weak learners are tweaked in favor of those instances misclassified by previous classifiers. In some problems it can be less susceptible to the overfitting problem than other learning algorithms. The individual learners can be weak, but as long as the performance of each one is slightly better than random guessing, the final model can be proven to converge to a strong learner. Although AdaBoost is typically used to combine weak base learners (such as decision stumps), it has been shown that it can also effectively combine strong base learners (such as deep decision trees), producing an even more accurate model. Every learning algorithm tends to suit some problem types better than others, and typically has many different parameters and configurations to adjust before it achieves optimal performance on a dataset. AdaBoost (with decision trees as the weak learners) is often referred to as the best out of the box classifier. When used with decision tree learning, information gathered at each stage of the AdaBoost algorithm about the relative 'hardness' of each training sample is fed into the tree growing algorithm such that later trees tend to focus on harder to classify examples.
Оқыту
AdaBoost – күшейтілген жіктегішті оқытудың нақты бір әдісін білдіреді. Күшейтілген жіктегіш – бұл мынадай формадағы жіктегіш:
мұнда әрқайсысы әлсіз оқушы болып табылады, ол объектіні кіріс ретінде қабылдап, объектінің класын көрсететін мәнді қайтарады. Мысалы, екі кластық мәселеде әлсіз оқушының нәтижесінің таңбасы болжамды объектінің класын анықтайды, ал абсолюттік мәні – осы жіктеуге сенімділікті көрсетеді. Сол сияқты, -шы жіктегіш, егер үлгі оң класта болса, оң, ал әйтпесе теріс болады. Әр әлсіз оқушы оқу жиынтығындағы әрбір үлгі үшін болжамды бекітетін нәтижелік гипотезаны жасайды. Әр итерацияда әлсіз оқушы таңдалып, оған коэффициент тағайындалады, соның нәтижесінде алынған кезеңдік күшейтілген жіктегіштің жалпы оқу қатесі ең төменгі деңгейге дейін азайтылады. Мұнда – бұл алдыңғы кезеңде оқытылған күшейтілген жіктегіш, ал – соңғы жіктегішке қосу үшін қарастырылып жатқан әлсіз оқушы.
Теңгерімдеу
Оқу процесінің әрбір итерациясында оқу жиынтығындағы әрбір үлгіге, сол үлгідегі қазіргі қателікке тең салмақ тағайындалады. Бұл салмақтар әлсіз оқушыны оқыту кезінде қолданылуы мүмкін. Мысалы, үлкен салмаққа ие үлгілер жиынтығын бөлуге басымдық беретін шешім ағаштары құруға болады.
Нағыз AdaBoost
Шешім ағаштарының нәтижесі – бұл кластық ықтималдықты бағалау, яғни оң класта болу ықтималдығы. Фридман, Хасти және Тибширани белгілі бір тұрақты мән үшін (әдетте салмақты ең кіші квадраттар қатесі арқылы таңдалған) аналитикалық минимизаторды шығарады: Сондықтан, бүкіл ағаштан алынған нәтижені белгілі бір тұрақты мәнге көбейтудің орнына, әрбір жапырақ түйіні алдыңғы мәнінің логит түрлендіруінің жартысын шығару үшін өзгерттіріледі.
Жұмсақ AdaBoost
Алдыңғы күшейткіш алгоритмдер әр қадамда жалпы тест қатесін барынша азайтуға ұмтылып, «ашкөздікпен» таңдайды, ал GentleBoost шектелген қадам өлшемдерін қолданады. -ты азайту үшін таңдалады және басқа коэффициент қолданылмайды. Сондықтан, егер әлсіз оқушы мінсіз жіктеу нәтижесін көрсетсе, GentleBoost дәл тең мәнді таңдайды, ал ең тік төмен түсу алгоритмдері оны орнатуға тырысады. GentleBoost-тың жақсы нәтижелері туралы эмпирикалық байқаулар Шапир мен Сингердің тым үлкен мәндерге рұқсат беру жалпылаудың нашар нәтижелеріне әкелуі мүмкін деген пікірін қолдайтын сияқты.
Ертерек тоқтату
Күшейтілген жіктегіштерді өңдеуді жылдамдату техникасы, ерте аяқтау – әрбір потенциалды объектіні соңғы жіктегіштің қажетті ғана қабаттарымен, белгілі бір сенімділік деңгейіне жету үшін сынауды білдіреді, бұл объектінің класын оңай анықтауға болатын жағдайларда есептеуді жеделдетеді. Мұндай схеманың бір мысалы – Виола мен Джонс ұсынған объектіні анықтау жүйесі: оң үлгілерге қарағанда теріс үлгілер көп болған кезде, жеке күшейтілген жіктегіштердің каскады оқытылады, әр кезеңнің нәтижесі теріс жаққа қарай бұрылады, сондықтан оң үлгілердің белгілі бір мөлшері қателікпен теріс деп жіктеледі, ал әр кезеңнен кейін теріс деп белгіленген барлық үлгілер алынып тасталады. Егер әр кезеңде теріс үлгілердің 50% сүзіліп тасталса, онда өте аз ғана объектілер толық жіктегіштен өтеді, бұл есептеу шығындарын азайтады. Бұл әдіс кейіннен жалпыланды, әр кезеңде қате оң және қате теріс көрсеткіштерге қол жеткізу үшін оңтайлы шектік мәндерді таңдау формуласы ұсынылды. Статистика саласында, мұнда AdaBoost көбінесе орташа өлшемді мәселелерге қолданылады, ерте тоқтату – артық үйлесімділікті азайту стратегиясы ретінде қолданылады. Оқу жиынтығынан валидациялық үлгілер жиынтығы бөлінеді, жіктегіштің оқу үшін пайдаланылған үлгілердегі көрсеткіштері валидациялық үлгілердегі көрсеткіштермен салыстырылады және егер оқу жиынтығындағы көрсеткіш жақсарып жатса да, валидациялық үлгілердегі көрсеткіш төмендегені байқалса, оқу тоқтатылады.
Толық түзету алгоритмдері
AdaBoost-тың ең тік түсу нұсқаларында, әр қабатта t сынақ қатесін азайту үшін таңдалғанда, қосылатын келесі қабат t қабатынан максималды түрде тәуелсіз болады: t оқушысына ұқсас әлсіз оқушы t+1 таңдау ықтимал емес. Дегенмен, t+1 бұрынғы басқа қабаттар сияқты ақпарат бере алады. LPBoost сияқты толық түзету алгоритмдері әр қадамнан кейін әрбір коэффициенттің мәнін оңтайландырады, осылайша қосылған жаңа қабаттар әрқашан барлық бұрынғы қабаттардан максималды тәуелсіздікке ие болады. Бұл артқа орнату, сызықтық бағдарламалау немесе басқа әдіс арқылы жүзеге асырылуы мүмкін.
Кесу
Кесу – бұл нашар жұмыс істейтін әлсіз жіктегіштерді жою процесі, күшейтілген жіктегіштің жадты пайдалануын және орындалу уақытын жақсарту мақсатында жасалады. Ең қарапайым әдістер, әсіресе толық түзетумен үйретумен бірге қолданғанда тиімді нәтиже береді, – салмақ немесе қателік шегін кесу: егер әлсіз жіктегіштің коэффициенті немесе жалпы тест қатесіне қосатын үлесі белгілі бір шектен төмен болса, онда ол жіктегіш алынып тасталады. Margineantu & Dietterich ансамбльдің әртүрлілігін барынша арттыратын әлсіз жіктегіштерді таңдауға баламалы критерий ұсынды. Егер екі әлсіз оқушы өте ұқсас нәтижелер берсе, тиімділікті арттыру үшін олардың біреуін жойып, қалған әлсіз оқушының коэффициентін арттыруға болады.