Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Машиналық оқытудағы әдіс
Method in machine learning
Машиналық оқытуда күшейту – бұл негізінен қателік пен дисперсияны азайтуға арналған ансамбльдік мета-алгоритм. Ол бақыланатын оқытуда және әлсіз оқушыларды күштілерге айналдыратын машиналық оқыту алгоритмдері отбасында қолданылады. Күшейту концепциясы Кернс пен Валианттың (1988, 1989) қойған сұрағына негізделген: «Әлсіз оқушылардың жиыны бір күшті оқушыны құра ала ма?» Әлсіз оқушы – нақты жіктемемен тек аз ғана байланысы бар жіктеуіш (ол мысалдарды кездейсоқ болжаудан жақсырақ белгілей алады). Керісінше, күшті оқушы – нақты жіктемемен кез келген деңгейде байланысы бар жіктеуіш. Роберт Шапир 1990 жылы жарияланған мақаласында Кернс пен Валианттың қойған сұрағына жағымды жауап берді. Бұл машиналық оқыту мен статистикада маңызды салдарға ие болды, ең бастысы күшейтуді дамытуға әкелді. Алғаш рет енгізілген кезде, гипотезаны күшейту мәселесі әлсіз оқушыны күшті оқушыға айналдыру процесін білдірді. «Негізінен, [гипотезаны күшейту] мәселесі, тиімді оқу алгоритмі, кездейсоқ болжаудан (яғни әлсіз оқушыдан) сәл ғана жақсы нәтиже беретін гипотезаны шығаратын болса, онда кез келген дәлдіктегі гипотезаны шығаратын тиімді алгоритмнің бар екендігін білдіреді [яғни күшті оқушы]». Жалпы техника ретінде, бұл күшейтумен шамалас.
In machine learning, boosting is an ensemble meta algorithm for primarily reducing bias, variance. It is used in supervised learning and a family of machine learning algorithms that convert weak learners to strong ones. The concept of boosting is based on the question posed by Kearns and Valiant (1988, 1989): "Can a set of weak learners create a single strong learner?" A weak learner is defined to be a classifier that is only slightly correlated with the true classification (it can label examples better than random guessing). In contrast, a strong learner is a classifier that is arbitrarily well correlated with the true classification. Robert Schapire answered the question posed by Kearns and Valiant in the affirmative in a paper published in 1990. This has had significant ramifications in machine learning and statistics, most notably leading to the development of boosting. When first introduced, the hypothesis boosting problem simply referred to the process of turning a weak learner into a strong learner. "Informally, [the hypothesis boosting] problem asks whether an efficient learning algorithm [ ] that outputs a hypothesis whose performance is only slightly better than random guessing [i. e. a weak learner] implies the existence of an efficient algorithm that outputs a hypothesis of arbitrary accuracy [i. e. a strong learner]." as a general technique, is more or less synonymous with boosting.
Алгоритмдерді күшейту
Көтермелеу алгоритмдік тұрғыдан шектелмегенмен, көтеру алгоритмдерінің көпшілігі үлестірілімге қатысты әлсіз жіктеуіштерді қайталап үйренуден және оларды соңғы күшті жіктеуішке қосудан тұрады. Олар қосылғанда, олар әлсіз білім алушылардың дәлдігіне байланысты салмақталады. Әлсіз оқушы қосылғаннан кейін, деректердің салмағы қайта реттеледі, бұл "қайта салмақтау" деп аталады. Бұрыс жіктелген кіріс деректерінің салмағы жоғарылайды, ал дұрыс жіктелген мысалдар салмағын жоғалтады. Кейбір көтеруге негізделген жіктеу алгоритмдері қайта-қайта бұрыс жіктелген мысалдардың салмағын азайтады; мысалы, көпшілікпен күшейту және BrownBoost. Осылайша, болашақ нашар білім алушылар бұрынғы нашар білім алушылар бұрыс жіктеген мысалдарға көбірек назар аударады. Көтеру алгоритмдері көп. Роберт Шапир ұсынған түпнұсқалық (рекурсивті көпшілік қақпа формуласы) бейімделу қабілеті жоқ және әлсіз білім алушыларды толықтай пайдалана алмады. Шапир мен Фрёнд кейін атақты Гёдель сыйлығын жеңіп алған адаптивті күшейту алгоритмін AdaBoost әзірледі. Тек дәлелденетін, шамамен дұрыс оқыту формуласындағы көтеру алгоритмдерін ғана көтеру алгоритмдері деп атуға болады. Көтеру алгоритмдеріне ұқсас басқа алгоритмдер кейде "күшейту алгоритмдері" деп аталады, бірақ олар кейде дұрыс емес түрде күшейту алгоритмдері деп аталады. LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost және басқалары сияқты көптеген жаңа алгоритмдер бар. Көптеген көтеру алгоритмдері AnyBoost фреймворкіне сәйкес келеді.
While boosting is not algorithmically constrained, most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier. When they are added, they are weighted in a way that is related to the weak learners' accuracy. After a weak learner is added, the data weights are readjusted, known as "re weighting". Misclassified input data gain a higher weight and examples that are classified correctly lose weight. Some boosting based classification algorithms actually decrease the weight of repeatedly misclassified examples; for example boost by majority and BrownBoost. Thus, future weak learners focus more on the examples that previous weak learners misclassified. There are many boosting algorithms. The original ones, proposed by Robert Schapire (a recursive majority gate formulation), were not adaptive and could not take full advantage of the weak learners. Schapire and Freund then developed AdaBoost, an adaptive boosting algorithm that won the prestigious Gödel Prize. Only algorithms that are provable boosting algorithms in the probably approximately correct learning formulation can accurately be called boosting algorithms. Other algorithms that are similar in spirit to boosting algorithms are sometimes called "leveraging algorithms", although they are also sometimes incorrectly called boosting algorithms. There are many more recent algorithms such as LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost, and others. Many boosting algorithms fit into the AnyBoost framework,
Нысанды санаттауға арналған статус-кво
Суреттердегі нысандар санаттарын тану компьютерлік көруде қиын мәселе болып табылады, әсіресе санаттар саны көп болғанда. Бұл жоғары кластың өзгешелігіне және бір санаттағы нысандардың әртүрлі вариацияларында жалпылау қажеттілігіне байланысты. Бір санаттағы нысандар бір-бірінен мүлдем басқаша көрінуі мүмкін. Тіпті бір нысан да әртүрлі бұрыштан, масштабтан және жарықтан қарағанда өзгеше болып көрінеді. Фондағы қалыптаспағандық және ішінара жабылу да тануды қиындатады. Адамдар мыңдаған нысан түрлерін тани алады, ал қазіргі кездегі нысанды тану жүйелерінің көпшілігі тек бірнешеуін ғана таниды, мысалы, адам бетін, көліктерді, қарапайым нысандарды сияқты. Зерттеулер көптеген санаттармен жұмыс істеу және жаңа санаттарды үстелдік түрде қосуға мүмкіндік беру үшін белсенді түрде жүргізілуде. Жалпы мәселе әлі шешілмегенімен, бірнеше көп санатты нысанды анықтаушылар (жүздеген немесе мыңдаған санаттарға дейін) жасалған. Мұның бір жолы – мүмкіндіктерді бөлісу және арттыру.
The recognition of object categories in images is a challenging problem in computer vision, especially when the number of categories is large. This is due to high intra class variability and the need for generalization across variations of objects within the same category. Objects within one category may look quite different. Even the same object may appear unalike under different viewpoint, scale, and illumination. Background clutter and partial occlusion add difficulties to recognition as well. Humans are able to recognize thousands of object types, whereas most of the existing object recognition systems are trained to recognize only a few, e. g. human faces, cars, simple objects, etc. Research has been very active on dealing with more categories and enabling incremental additions of new categories, and although the general problem remains unsolved, several multi category objects detectors (for up to hundreds or thousands of categories) have been developed. One means is by feature sharing and boosting.
Көп сыныпты санаттауға арналған күшейту
Бинарлық санаттаумен салыстырғанда, көп сыныпты санаттау санаттар арасында ортақ болатын қасиеттерді бірден іздейді. Бұл қасиеттер көбінесе жалпыға ортақ жиектерге ұқсайды. Оқу кезінде әр санат үшін детекторларды бірлесіп оқытуға болады. Жеке оқытуға қарағанда, бұл жақсы жалпылайды, аз оқу деректерін қажет етеді және бірдей нәтижеге жету үшін аз мүмкіндіктерді талап етеді. Алгоритмнің негізгі ағыны бинарлық жағдайға ұқсас. Айрмашылығы, бірлескен оқу қатесін өлшеуі алдын ала анықталуы керек. Әрбір итерацияда алгоритм бір мүмкіндіктің жіктегішін таңдайды (көп санаттармен бөлісе алатын мүмкіндіктерге басымдық беріледі). Бұл көп сыныпты жіктеуді екілікке айналдыру арқылы (санаттар жиыны қалғандарына қарсы) немесе жіктегіште мүмкіндігі жоқ санаттардан айып тұрғызып жасалуы мүмкін. "Көп сыныпты және көп көріністі объектілерді анықтау үшін визуалды ерекшеліктерді бөлісу" деген мақалада А. Торралба және авторлар GentleBoost күшейтуін қолданып, оқу деректері шектеулі болғанда, мүмкіндіктерді бөлісу арқылы оқыту, бөліспеуге қарағанда әлдеқайда жақсы нәтиже беретінін көрсетті (бірдей күшейту раундтарында). Сондай-ақ, белгілі бір өнімділік деңгейі үшін, мүмкіндіктерді бөлісетін детекторларға қажетті мүмкіндіктердің жалпы саны (және, демек, жіктегіштің жұмыс уақытының құны) сыныптар санына пропорционалды түрде логарифмдік өседі, яғни бөліспейтін жағдайдағы сызықтық өсуден баяу. "Визуалды пішін алфавитін қолданып объектілерді анықтаушыларды ұлғайту" деген мақалада да ұқсас нәтижелер көрсетілген, бірақ авторлар күшейту үшін AdaBoost-ты қолданды.
Compared with binary categorization, multi class categorization looks for common features that can be shared across the categories at the same time. They turn to be more generic edge like features. During learning, the detectors for each category can be trained jointly. Compared with training separately, it generalizes better, needs less training data, and requires fewer features to achieve the same performance. The main flow of the algorithm is similar to the binary case. What is different is that a measure of the joint training error shall be defined in advance. During each iteration the algorithm chooses a classifier of a single feature (features that can be shared by more categories shall be encouraged). This can be done via converting multi class classification into a binary one (a set of categories versus the rest), or by introducing a penalty error from the categories that do not have the feature of the classifier. In the paper "Sharing visual features for multiclass and multiview object detection", A. Torralba et al. used GentleBoost for boosting and showed that when training data is limited, learning via sharing features does a much better job than no sharing, given same boosting rounds. Also, for a given performance level, the total number of features required (and therefore the run time cost of the classifier) for the feature sharing detectors, is observed to scale approximately logarithmically with the number of class, i. e., slower than linear growth in the non sharing case. Similar results are shown in the paper "Incremental learning of object detectors using a visual shape alphabet", yet the authors used AdaBoost for boosting.
Қиыршық және қиыршық емес көтеру алгоритмдері
Көтермелеу алгоритмдері дөңгелек немесе дөңгелек емес оңтайландыру алгоритмдеріне негізделуі мүмкін. AdaBoost және LogitBoost сияқты дөңгелек алгоритмдер кездейсоқ шуға ұшырап, "қарсы тұра алады", нәтижесінде әлсіз гипотезалардың қарапайым және оқуға болатын комбинацияларын үйрене алмайды. Бұл шектеуді 2008 жылы Long & Servedio көрсеткен. Дегенмен, 2009 жылға қарай бірнеше авторлар BrownBoost сияқты дөңгелек емес оңтайландыруға негізделген көтермелеу алгоритмдерінің шулы деректер жиынтығынан үйрене алатынын және Long–Servedio деректер жиынтығының жасырын жіктегішін нақты үйрене алатынын көрсетті.
Boosting algorithms can be based on convex or non convex optimization algorithms. Convex algorithms, such as AdaBoost and LogitBoost, can be "defeated" by random noise such that they can't learn basic and learnable combinations of weak hypotheses. This limitation was pointed out by Long & Servedio in 2008. However, by 2009, multiple authors demonstrated that boosting algorithms based on non convex optimization, such as BrownBoost, can learn from noisy datasets and can specifically learn the underlying classifier of the Long–Servedio dataset.