Машиналық оқу және статистикада белгілерді таңдау процедурасы

Кіріспе

Машиналық оқыту және статистикадағы процедуралар. Ерекшеліктерді таңдау – модель құру үшін қажетті ерекшеліктердің (айнымалылар, болжаушылар) кіші жиынтығын таңдау процесі. Стилметрия және ДНК микромассивтік талдау – ерекшеліктерді таңдау қолданылатын екі мысал. Оны ерекшеліктерді шығарудан ажырату қажет. Ерекшеліктерді таңдау техникалары бірнеше себепке байланысты қолданылады: зерттеушілер/пайдаланушылар үшін түсіндіруді жеңілдету үшін модельдерді қарапайымдау, оқыту уақытын қысқарту, өлшемділіктің қарғысынан (curse of dimensionality) сақтану, деректердің білім беру моделі класымен сәйкестігін жақсарту, кіріс кеңістігіндегі туа біткен симметрияларды кодтау. Ерекшеліктерді таңдау техникасын қолданғандағы басты ұстаным – деректерде артық немесе маңызсыз ерекшеліктер бар, оларды көп ақпарат жоғалтпай жоюға болады. Артық және маңызсыз – екі бөлек түсінік, себебі бір маңызды ерекшелік, өте тікелей байланысты басқа маңызды ерекшелік болғанда артық болуы мүмкін. Ерекшеліктерді шығару бастапқы ерекшеліктердің функцияларынан жаңа ерекшеліктер жасайды, ал ерекшеліктерді таңдау ерекшеліктердің кіші жиынтығын қайтарады. Ерекшеліктерді таңдау техникалары көбінесе көптеген ерекшеліктері бар, бірақ салыстырмалы түрде аз үлгілері (немесе деректер нүктелері) бар салаларда қолданылады.

Кіріспе

Ерекшеліктерді таңдау алгоритмі жаңа ерекшеліктер жиынтығын ұсынуға арналған іздеу әдісінің және әртүрлі ерекшеліктер жиынтығын бағалайтын бағалау шарасының үйлесімі ретінде қарастырылуы мүмкін. Ең қарапайым алгоритм – қателік деңгейін азайтатын ерекшеліктердің барлық мүмкін кіші жиынтығын тексеру. Бұл кеңістікті толыққанды іздеу болып табылады және ең кішкентай ерекшелік жиынтықтарынан басқасы үшін есептеу жағынан қиын. Бағалау метрикасын таңдау алгоритмге күшті әсер етеді және осы бағалау метрикалары ерекшеліктерді таңдау алгоритмдерінің үш негізгі санатын ажыратады: wrapper әдістер, filter әдістер және енгізілген әдістер. Wrapper әдістер ерекшеліктердің кіші жиынтығын бағалау үшін болжамдық модельді пайдаланады. Әрбір жаңа кіші жиынтық модельді оқыту үшін қолданылады, ол бөлек қалған жиынмен тексеріледі. Бөлек қалған жиынға жасалған қателердің санын (модельдің қателік деңгейін) санау осы кіші жиынтыққа ұпай береді. Wrapper әдістері әрбір кіші жиынтық үшін жаңа модельді оқытатындықтан, олар есептеу жағынан өте күшті, бірақ әдетте модельдің немесе типтік мәселенің осы түрі үшін ең жақсы ерекшеліктер жиынтығын ұсынады. Filter әдістері ерекшеліктер жиынтығын бағалау үшін қателік деңгейінің орнына жақын өлшемді пайдаланады. Бұл өлшем есептеу жылдамдығы үшін таңдалады, сонымен бірге ерекшеліктер жиынтығының пайдалылығын сақтайды. Көп қолданылатын өлшемдерге өзара ақпарат, сыныптар арасындағы/сыныптар ішіндегі арақашықтық немесе әрбір сынып/ерекшелік комбинациясы үшін маңыздылық сынақтарының ұпайлары жатады. Filter әдістері әдетте wrapper әдістеріне қарағанда есептеуді аз қажет етеді, бірақ олар нақты болжамдық модельге сәйкес келмейтін ерекшеліктер жиынтығын шығарады. Бұл реттеме болмауы filter әдісінен алынған ерекшеліктер жиынтығы wrapper әдісінен алынған жиынтыққа қарағанда көбінесе жалпырақ болады және төмен болжамдық өнімділікті ұсынады. Алайда, ерекшеліктер жиынтығы болжамдық модельдің болжамдарын қамтымайды, сондықтан ерекшеліктер арасындағы қатынастарды анықтау үшін пайдалы. Көптеген filter әдістері ең жақсы ерекшеліктердің нақты кіші жиынтығын емес, ерекшеліктердің тізімін ұсынады, ал тізімдегі кесу нүктесі кросс-валидация арқылы таңдалады. Filter әдістері wrapper әдістерінің алдын ала өңдеу қадамы ретінде де қолданылады, бұл wrapper әдісін үлкен мәселелерде қолдануға мүмкіндік береді. Тағы бір танымал тәсіл – рекурсивті ерекшеліктерді жою алгоритмі, ол жиі қолдаушы векторлық машиналармен модельді қайта-қайта құру және төмен салмақты ерекшеліктерді жою үшін қолданылады. Енгізілген әдістер – модельді құру процесінің бір бөлігі ретінде ерекшеліктерді таңдауды жүзеге асыратын әдістердің барлық тобы. Бұл тәсілдің үлгісі – сызықтық модельді құру үшін LASSO әдісі, ол регрессия коэффициенттерін L1 жазасымен жазалайды, олардың көпшілігін нөлге дейін қысқартады. Нөлден өзгеше регрессия коэффициенттері бар кез келген ерекшелік LASSO алгоритмімен «таңдалады». LASSO-ның жақсартулары: үлгілерді жүктейтін Bolasso; LASSO-ның L1 жазасын қырқа регрессиясының L2 жазасымен біріктіретін Elastic net реттеуі; және регрессия коэффициенттерінің комбинаторлық талдауына негізделген барлық ерекшеліктерді бағалайтын FeaLect. AEFS LASSO-ны автокодерлермен сызықтық емес сценарийге дейін кеңейтеді. Бұл тәсілдер есептеу күрделілігі жағынан filter және wrapper әдістері арасында болады. Дәстүрлі регрессиялық талдауда ерекшеліктерді таңдаудың ең танымал түрі – қадамдық регрессия, ол wrapper техникасы. Бұл – әрбір раундта ең жақсы ерекшелікті қосатын (немесе ең нашар ерекшелікті жоятын) ашкөз алгоритм. Негізгі басқару мәселесі – алгоритмді қашан тоқтату керектігін анықтау. Машиналық оқытуда бұл әдетте кросс-валидация арқылы жүзеге асырылады. Статистикада кейбір критерийлер оңтайландырылады. Бұл ұя салу мәселесіне әкеледі. Одан әрі, бұтақ және байлау және бөлшектік сызықтық желі сияқты сенімді әдістер зерттелді.

A feature selection algorithm can be seen as the combination of a search technique for proposing new feature subsets, along with an evaluation measure which scores the different feature subsets. The simplest algorithm is to test each possible subset of features finding the one which minimizes the error rate. This is an exhaustive search of the space, and is computationally intractable for all but the smallest of feature sets. The choice of evaluation metric heavily influences the algorithm, and it is these evaluation metrics which distinguish between the three main categories of feature selection algorithms: wrappers, filters and embedded methods. Wrapper methods use a predictive model to score feature subsets. Each new subset is used to train a model, which is tested on a hold out set. Counting the number of mistakes made on that hold out set (the error rate of the model) gives the score for that subset. As wrapper methods train a new model for each subset, they are very computationally intensive, but usually provide the best performing feature set for that particular type of model or typical problem. Filter methods use a proxy measure instead of the error rate to score a feature subset. This measure is chosen to be fast to compute, while still capturing the usefulness of the feature set. Common measures include the mutual information, and inter/intra class distance or the scores of significance tests for each class/feature combinations. Filters are usually less computationally intensive than wrappers, but they produce a feature set which is not tuned to a specific type of predictive model. This lack of tuning means a feature set from a filter is more general than the set from a wrapper, usually giving lower prediction performance than a wrapper. However the feature set doesn't contain the assumptions of a prediction model, and so is more useful for exposing the relationships between the features. Many filters provide a feature ranking rather than an explicit best feature subset, and the cut off point in the ranking is chosen via cross validation. Filter methods have also been used as a preprocessing step for wrapper methods, allowing a wrapper to be used on larger problems. One other popular approach is the Recursive Feature Elimination algorithm, commonly used with Support Vector Machines to repeatedly construct a model and remove features with low weights. Embedded methods are a catch all group of techniques which perform feature selection as part of the model construction process. The exemplar of this approach is the LASSO method for constructing a linear model, which penalizes the regression coefficients with an L1 penalty, shrinking many of them to zero. Any features which have non zero regression coefficients are 'selected' by the LASSO algorithm. Improvements to the LASSO include Bolasso which bootstraps samples; Elastic net regularization, which combines the L1 penalty of LASSO with the L2 penalty of ridge regression; and FeaLect which scores all the features based on combinatorial analysis of regression coefficients. AEFS further extends LASSO to nonlinear scenario with autoencoders. These approaches tend to be between filters and wrappers in terms of computational complexity. In traditional regression analysis, the most popular form of feature selection is stepwise regression, which is a wrapper technique. It is a greedy algorithm that adds the best feature (or deletes the worst feature) at each round. The main control issue is deciding when to stop the algorithm. In machine learning, this is typically done by cross validation. In statistics, some criteria are optimized. This leads to the inherent problem of nesting. More robust methods have been explored, such as branch and bound and piecewise linear network.

Оптималдылық критерийлері

Оптималдылық критерийлерін таңдау қиын, себебі ерекшеліктерді іріктеу міндетінде бірнеше мақсат бар. Көптеген қолданылатын критерийлер таңдалған ерекшеліктер санына пропорционалды айыппұлмен дәлдікті қамтиды. Мысалға, Акайке ақпараттық критерийі (AIC) және Маллоустың Cp критерийі, олар әрбір қосымша ерекшелік үшін 2 айыппұл салады. AIC ақпарат теориясына негізделген және максималды энтропия принципі арқылы шығарылған. Басқа критерийлерге – әрбір қосылған ерекшелік үшін айыппұл қолданатын Бейес ақпараттық критерийі (BIC), асимптотикалық жағдайда қолданылатын ең төменгі сипаттама ұзындығы (MDL), Бонферрони / RIC, максималды тәуелділік ерекшеліктерін іріктеу, сондай-ақ жалған жаңқа жылдамдығымен (FDR) негізделген жаңа критерийлер жатады. Ең маңызды ерекшеліктердің кіші жиынтығын іріктеу үшін максималды энтропия жылдамдығы критерийін де қолдануға болады.

Құрылымдық оқыту

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

Квадраттық бағдарламалаудың ерекшеліктерін таңдау

mRMR – ерекшеліктерді таңдау үшін қолданылатын ағынмен жақсарылатын стратегияның классикалық мысалы: бір рет таңдалған ерекшелік кейіннен алынып тасталмайды. mRMR кейбір ерекшеліктерді қысқарту үшін «жүзу іздеу» әдісімен оңтайландырылуы мүмкін, бірақ оны келесідей жаһандық квадраттық бағдарламалау оңтайландыру мәселесі ретінде де формулиреуге болады:

мұнда – барлық ерекшеліктердің саны n болғанда, ерекшеліктердің маңыздылығын көрсететін вектор, – ерекшеліктердің жұптық артықшылығының матрицасы, ал – салыстырмалы ерекшелік салмақтарын білдіреді. QPFS квадратық бағдарламалау арқылы шешіледі. Жақында QFPS энтропиясы төмен ерекшеліктерге қарай бейім екендігі көрсетілді, мұнда және SPECCMI-нің артықшылығы – оны Q матрицасының басты өз векторын таба отырып оңай шешуге болады, бұл оның кеңейтімділігін арттырады. SPECCMI сондай-ақ ерекшеліктердің екінші реттік өзара әрекеттесуін де қамтиды.

Бірлескен өзара ақпарат

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

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

Тұрақты ағаш

Шешім ағашының немесе ағаш ансамблінің белгілері артық екені көрсетілді. Жақында қолданыла бастаған реттелген ағаш әдісі белгілердің кіші жиынтығын іріктеу үшін пайдаланылуы мүмкін. Реттелген ағаштар, ағымдағы түйінге бөлу үшін бұрынғы ағаш түйіндерінде таңдалған айнымалыларға ұқсас айнымалыны пайдалануды жазады. Реттелген ағаштарға тек бір ағаш моделін (немесе бір ағаш ансамблі моделін) құру қажет, демек, олар есептеу тұрғысынан тиімді. Реттелген ағаштар сандық және санаттық белгілерді, өзара әрекеттесулерді және сызықтық емес қасиеттерді табиғи түрде өңдейді. Олар белгілердің масштабтарына (өлшем бірліктеріне) тәуелсіз және сыртқы мәндерге (аутлаерлерге) төзімді, сондықтан нормалдау сияқты деректерді алдын ала өңдеудің қажеті шамалы. Реттелген кездейсоқ орман (RRF) – реттелген ағаштардың бір түрі. Басқарылатын RRF – бұл қарапайым кездейсоқ орманның маңыздылық бағаларымен басқарылатын жетілдірілген RRF.

Метагеуристикалық әдістер туралы жалпы түсінік

Метаэвристика – классикалық шешу әдістері жоқ, қиын (әдетте NP-толық) оңтайландыру мәселелерін шешуге арналған алгоритмнің жалпы сипаттамасы. Әдетте, метаэвристика – жаһандық оптимумға ұмтылатын стохастикалық алгоритм. Қарапайым жергілікті іздеуден бастап күрделі жаһандық іздеу алгоритмдеріне дейін көптеген метаэвристикалар бар.

Негізгі қағидалар

Қасиеттерді таңдау әдістері, әдетте, таңдау алгоритмі мен модельді құру қалай үйлесетініне қарай үш топқа бөлінеді.

Сүзгілеу әдісі

Сүзгі түрі әдістері модельге қарамастан айнымалыларды таңдайды. Олар тек болжалатын айнымалымен байланысты жалпы белгілерге ғана негізделеді. Сүзгі әдістері ең аз қызығушылық тудыратын айнымалыларды жояды. Қалған айнымалылар деректерді жіктеу немесе болжау үшін қолданылатын жіктеу немесе регрессия модельдерінің құрамына кіреді. Бұл әдістер есептеу уақыты бойынша тиімді және артық үйлесімге (overfitting) қарсы тұрақты. Сүзгі әдістері айнымалылар арасындағы байланысты ескермегенде, қабылдауға болмайтын артық айнымалыларды таңдауға бейім. Дегенмен, күрделірек әдістер бұл мәселені бір-бірімен күшті байланыстағы айнымалыларды жою арқылы азайтуға тырысады, мысалы, Жылдам Корреляцияға Негізделген Сүзгі (FCBF) алгоритмі.

Қаптама әдісі

Wrapper әдістері айнымалылардың кіші топтарын бағалайды, бұл сүзгі тәсілдерінен өзгеше, айнымалылар арасындағы мүмкін өзара әрекеттестіктерді анықтауға мүмкіндік береді. Бұл әдістердің екі негізгі кемшілігі бар: байқаулар саны жеткіліксіз болса, артық үйлесімге (overfitting) ұшырау қаупі артады. Айнымалылардың саны көп болса, есептеуге кететін уақыт өте ұзақ болады.

Енгізілген әдіс

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