Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



1. Вступ в машинне навчання

Скачати 201.51 Kb.

1. Вступ в машинне навчання




Скачати 201.51 Kb.
Дата конвертації13.04.2017
Розмір201.51 Kb.

1. Вступ в машинне навчання

Машинне навчання (machine learning) - це область наукового знання, яка працює з алгоритмами, "здатними навчатися". Необхідність використання методів машинного навчання пояснюється тим, що для багатьох складних - "інтелектуальних" - завдань (наприклад, розпізнавання рукописного тексту, мови і т. П.

Машинне навчання (англ. machine learning) - це підгалузь інформатики (зокрема, м'яких[en] та гранульованих обчислень[en]), яка еволюціювала з дослідження розпізнавання образів та теорії обчислювального навчання[en] в галузі штучного інтелекту.
Знання - форма інформації, існування систематизованого результату інтелектуальної діяльності людини (пізнання ). Виділяють різні види знання: наукове, повсякденне (здоровий глузд), інтуїтивне, релігійне та інші.
Розпізнава́ння рукопи́сного вве́дення - здатність комп'ютера отримувати та інтерпретувати інтелектуальний рукописний ввід з джерел, таких як паперові документи, фотографії, сенсорні екрани та інші пристрої.
) дуже складно (або навіть неможливо) розробити "явний" алгоритм їх вирішення, проте часто можна навчити комп'ютер навчитися вирішенню цих завдань. Одним з перших, хто використав термін "машинне навчання", був винахідник першої самонавчальної комп'ютерної програми гри в шашки А. Л. Самуель в 1959 р . Під навчанням він розумів процес, в результаті якого комп'ютер здатний показати поведінку, яка в неї не було закладено "явно". Це визначення не витримує критики, оскільки не зрозуміло, що означає прислівник "явно". Більш точне визначення дав набагато пізніше Т. М. Мітчелл : кажуть, що комп'ютерна програма навчається на основі досвіду E по відношенню до деякого класу задач T і міри якості P, якщо якість вирішення завдань з T, виміряний на основі P, поліпшується з набуттям досвіду E.

Зауважимо, що фаза навчання може передувати фазі роботи алгоритму (наприклад, детектування осіб на фотокамері), але може мати місце зворотна ситуація: навчання (і додаткове навчання) може проходити в процесі функціонування самого алгоритму (наприклад, визначення спаму).

В даний час машинне навчання має численні сфери використання, такі, як комп'ютерний зір, розпізнавання мови, комп'ютерна лінгвістика та обробка природних мов, медична діагностика, біоінформатика, технічна діагностика, фінансові додатки, пошук і рубрикація текстів, інтелектуальні ігри, експертні системи та ін.

Технічна діагностика - галузь науково-технічних знань, сутність якої складають теорія, методи і засоби постановки діагнозу про стан технічних об'єктів.
Експе́ртна систе́ма - це методологія адаптації алгоритму успішних рішень однієї сфери науково-практичної діяльності в іншу. З поширенням комп'ютерних технологій це тотожна (подібна, заснована на оптимізуючому алгоритмі чи евристиках) інтелектуальна комп'ютерна програма, що містить знання та аналітичні здібності одного або кількох експертів щодо деякої галузі застосування, і здатна робити логічні висновки на основі цих знань, тим самим забезпечуючи вирішення специфічних завдань (консультування, навчання, діагностування, тестування, проектування тощо) без участі експерта (фахівця в конкретній проблемній галузі). Також визначається як система, яка використовує базу знань для вирішення завдань (видачі рекомендацій) у деякій предметній галузі. Цей клас програмного забезпечення спочатку розроблявся дослідниками штучного інтелекту в 1960-ті та 1970-ті і здобув комерційне застосування, починаючи з 1980-х. Часто термін система, заснована на знаннях використовується як синонім експертної системи, однак можливості експертних систем ширші за можливості систем, заснованих на детермінованих (обмежених, реалізованих на поточний час) знаннях.
Розпізнава́ння мо́влення (англ. speech recognition) або Мо́влення у те́кст (англ. speech to text (STT))- процес перетворення мовленнєвого сигналу в текстовий потік. Не варто плутати із визначенням розпізнавання мови, оскільки «розпізнати мову» безпосередньо означає лише дати відповідь на питання, до якої мови належить сегмент мовленнєвого сигналу.

Розрізняють дедуктивне і індуктивне навчання. В задачах дедуктивного навчання є знання, яким-небудь чином формалізовані. Потрібна вивести з них правило, стосовно до конкретного випадку. Дедуктивное навчання відносять до області експертних систем і тут розглядатися не буде. Основне завдання індуктивного навчання полягає у відновленні деякій залежності за емпіричними даними.

Емпірика - все те, що отримано шляхом експерименту, на практиці, засноване на досвіді, спостереженні.
Індуктивне навчання підрозділяється на навчання з учителем, навчання без учителя, навчання з підкріпленням (reinforcement learning), активне навчання та ін.

Грунтовними підручниками по машинному навчанню є [1, 8, 9] та ін. Також рекомендуємо російськомовний ресурс www.machinelearning.ru і сайт курсу по машинному навчанню одного з авторів цього посібника www.uic.unn.ru/zny/ml.



1.1. Задача навчання з учителем

1.1.1. Постановка задачі навчання з учителем

Розглянемо постановку задачі навчання з учителем (supervised learning). Нехай Χ - деяка множина, елементи якої називаються об'єктами або прикладами, ситуаціями, входами (samples); а Υ - множина, елементи якої називаються відповідями або відгуками, мітками, виходами (responses). Є деяка залежність (детермінована і імовірнісна), що дозволяє по x Χ передбачити y Υ. Зокрема, якщо залежність детермінована, то існує функція . Залежність відома тільки на об'єктах навчальної вибірки



.

Упорядкована пара "об'єкт-відповідь" називається прецедентом.

Завдання навчання з учителем полягає у відновленні залежності між входом і виходом за наявною навчальній вибірці, тобто необхідно побудувати функцію (вирішальне правило), по нових об'єктах пророкує відповідь :

.

Функція при цьому вибирається з деякого безлічі можливих моделей F. Процес знаходження називається навчанням (learning), а також налаштуванням або підгонкою (fitting) моделі.

Алгоритм побудови функції по заданій навчальній вибірці називається алгоритмом навчання. Деякий клас алгоритмів називається методом навчання. Іноді терміни "алгоритм" і "метод" використовуються як синоніми.

Алгоритми навчання, звичайно ж, оперують не з самими об'єктами, а їх описами. Найбільш поширеним є ознаковими опис. При такому підході об'єкт представляється як вектор, де . Таким чином,



Компонента називається j-му ознакою, або властивістю (feature), або атрибутом об'єкта . Якщо , то j-й ознака називається кількісним або речовим. Якщо звичайно, те j-й ознака називається номінальним, або категоріальним, або фактором. Якщо при цьому , то ознака називається бінарною. Якщо звичайно і впорядковано, то ознака називається порядковим. Множина називається простором ознак.

Залежно від того, які значення може приймати відповідь , розрізняють різні класи завдань навчання з учителем. Якщо , то говорять про задачі відновлення регресії. Вирішальне правило при цьому називають регресією. Якщо звичайно, наприклад, , то говорять про завдання класифікації. Вирішальне правило при цьому називають класифікатором. В останньому випадку можна інтерпретувати як номер класу, до якого належить об'єкт . До завдань навчання відносять також задачі ранжування, прогнозування та ін.

Зробимо два зауваження, що стосуються якості рішення задачі.

По-перше, знайдене вирішальне правило повинно володіти узагальнюючої здатністю. Іншими словами, побудований класифікатор або функція регресії повинні відображати загальну залежність виходу від входу, грунтуючись лише на відомих даних про прецеденти навчальної вибірки. При вирішенні прикладних задач, як правило, говорити про відновлення істинної взаємозв'язку не доводиться, і, отже, мова може йти лише про відшукання деякої апроксимації. Таким чином, навчена модель повинна видавати в середньому досить точні передбачення на нових (що не входять в навчальну вибірку) прецедентах.

По-друге, слід приділити увагу проблемі ефективної вичислімості функції . Аналогічна вимога виноситься і до алгоритму навчання: настройка моделі повинна відбуватися за прийнятний час.

Нехай для завдання навчання з учителем визначено функцію втрат, або функцію штрафу, що представляє собою немінусову функцію від істинного значення виходу і передвіщеного за допомогою моделі значення .

Істинне значення (фізичної величини) (англ. true value (of a quantity)) - значення фізичної величини, яке ідеально відображало б певну властивість об'єкта.
В математичній оптимізації, статистиці, теорії рішень та машинному навчанні фу́нкція втрат (англ. loss function) або фу́нкція витра́т (англ. cost function) - це функція, яка відображує подію, або значення однієї чи декількох величин, на дійсне число, яке інтуїтивно представляє якісь «витрати», пов'язані з цією подією.
Наприклад, для завдання відновлення регресії часто використовують квадратичний штраф

або абсолютний штраф:



Для задачі класифікації можна взяти помилку передбачення



де - індикаторна функція:



Математичне сподівання функції втрат



називається середньою помилкою, або середнім ризиком.

Характеристична функція (індикаторна функція, індикатор) підмножини A ⊆ X - функція, визначена на множині X , яка визначає належність елемента x ∈ X підмножині A .
Класифіка́ція (фр. , англ. classification походить від лат. classis - клас і facio - роблю) - система розподілення об'єктів (процесів, явищ) за класами (групами тощо) відповідно до визначених ознак. Інколи вживають термін категоризація у значенні «розподілення об'єктів на категорії».
В якості вирішального правила розумно взяти функцію , яка мінімізує цю помилку:



Часто закон розподілу спільної випадкової величини не відомий, тому даний критерій не застосуємо.

Закон розподілу ймовірностей - це поняття теорії ймовірностей, яке для дискретної випадкової величини показує множину можливих подій з ймовірностями їхнього настання.
Випадкова величина (англ. Random variable) - одне з основних понять теорії ймовірностей.
Замість середнього ризику розглянемо емпіричний ризик, або емпіричну помилку,



Критерій (1) замінимо наступним:



де прецеденти ) складають навчальну вибірку.

У підсумку завдання звелася до відшукання функції з допустимого безлічі , що задовольняє умові (2), за умови, що і фіксовані і відомі. Це так званий принцип мінімізації емпіричного ризику.

Мініміза́ція емпіри́чного ри́зику (МЕР, англ. empirical risk minimization, ERM) - це принцип у теорії статистичного навчання, який визначає сімейство алгоритмів навчання, і застосовується для отримування теоретичних меж продуктивності алгоритмів навчання.
Як правило, клас параметризований, тобто мається його опис в виді , де - деяка відома множина. В процесі настройки моделі алгоритмом навчання вибираються значення набору параметрів , що забезпечують точне або наближене виконання умови (2), тобто мінімізації помилки на прецедентах навчальної вибірки. Проте ця умова не підходить для оцінки узагальнюючої здатності алгоритму. Більше того, і R (f) можуть значно відрізнятися. Ситуація, коли мале, а R (f) надто велике, називається перенавчанням.

На практиці всі наявні дані розбивають на навчальну і тестову вибірки. Навчання проводиться з використанням навчальної вибірки, а оцінка якості передбачення на основі даних тестової вибірки.

Іншим практичним методом оцінки узагальнюючої здатності вирішального правила є метод -кратного перехресного (ковзаючого) контролю (CV - cross validation). Усі наявні дані розбиваються на приблизно рівних (по числу прецедентів) частин. Далі, відокремлюючи з вибірки одну за одною кожну з цих частин, використовують залишилися дані (складені з частин) як навчальну вибірку, а відокремлену частина - як тестову. Підсумкова оцінка помилки визначається як середня за всі розбиття. Зауважимо, що саме підсумкове вирішальне правило будується за всієї наявної навчальній вибірці.

Часто використовують значення або 10. Якщо , то говорять про метод скльзящего контролю з одним виділеннями об'єктом (LOO - leave-one-out estimate).



1.1.2. Метод найближчих сусідів

Метод найближчих сусідів (k nearest-neighbor, k-NN) відноситься до найбільш простих і в той же час універсальних методам, використовуваним як для вирішення задач класифікації, так і відновлення регресії.

Задача класифіка́ції - формалізована задача, яка містить множину об'єктів (ситуацій), поділених певним чином на класи. Задана кінцева множина об'єктів, для яких відомо, до яких класів вони відносяться.
У разі класифікації новий об'єкт класифікується шляхом віднесення його до класу, що є переважаючим серед k найближчих (у просторі ознак) об'єктів з навчальної вибірки.
В розпізнаванні образів та машинному навчанні ве́ктор озна́к (англ. feature vector) - це n-вимірний вектор числових ознак, що представляють певний об'єкт. Багато алгоритмів у машинному навчанні вимагають чисельного представлення об'єктів, оскільки такі представлення полегшують обробку та статистичний аналіз.
Якщо , то новий об'єкт відноситься до того ж класу, що і найближчий об'єкт з навчальної вибірки.

Аналогічний спосіб використовується і в задачі відновлення регресії, з тією лише різницею, що як відповідь для об'єкта виступає середнє відповідей k найближчих до нього об'єктів з навчальної вибірки.

Опишемо метод більш формально. Нехай - множина найближчих до об'єктів з навчальної вибірки. Тоді для задачі класифікації покладемо



а для завдання відновлення регресії -



У деяких випадках дані відповіді враховуються з вагами, назад пропорційними відстані до об'єкта. Це особливо корисно для вирішення задачі класифікації з незбалансованими даними, тобто коли число об'єктів, що відносяться до різних класів, сильно різне.

Для визначення найближчих сусідів зазвичай використовується евклідова відстань

однак воно застосовується тільки для ознак, описуваних кількісними змінними. Якщо всі змінні якісні, то можна використовувати відстань Хеммінга



У загальному випадку використовують функцію



де - невід'ємні параметри, для якісних змінних, для якісних змінних.

Відстань Геммінга - число позицій, у яких відповідні цифри двох двійкових слів однакової довжини різні . У загальнішому випадку відстань Геммінга застосовується для рядків однакової довжини будь-яких q-кових абеток і служить метрикою відмінності (функцією, що визначає відстань в метричному просторі) об'єктів однакової вимірності.
Зауважимо, що функція відстані не обов'язково повинна бути метрикою і нерівність трикутника може бути не виконано.
Нерівність трикутника - одна з інтуїтивних властивостей відстані, що використовується в геометрії, функціональному аналізі.

Для підвищення точності моделі також можуть використовуватися спеціальні алгоритми навчання метрики відстані (наприклад, Large Margin Nearest Neighbour [8]).

Одним з основних параметрів, що впливають на узагальнюючу здатність алгоритму, є число "найближчих сусідів" . В цілому, вибір певного значення обумовлений характером даних завдання. Великі значення можуть призвести як до більш точного опису кордону, що розділяє класи, так і перенавчання. Зазвичай для вибору застосовують різні евристики, зокрема, метод перехресного контролю.



1.1.3. Машина опорних векторів

Один з найпопулярніших методів машинного навчання - машина опорних векторів (SVM - Support Vector Machine) - є розвитком ідей, запропонованих в 1960-1970 рр. В. Н. Вапніка і А. Я. Червоненкіса. Остаточне обрис метод прийняв в 1995 р, коли було показано, як в цьому методі можна ефективно використовувати ядра [4].

Розглянемо спочатку випадок двох лінійно разделімих класів. Для зручності будемо їх кодувати числами 1, -1, тобто

Оптимальною розділяє гиперплоскостью називається гіперплоскость, така, що відстань від неї до найближчої точки з навчальної вибірки (не важливо з якого класу) максимально. Таким чином, оптимальна розділяє гіперплоскость максимізує зазор (відступ) - відстань від неї до точок з навчальної вибірки. Часто це призводить до гарних результатів і на об'єктах тестової вибірки.

Математична постановка задачі виглядає наступним чином:

Потрібно знайти



при обмеженнях





де означає скалярний добуток



a - евклидову норму



Еквівалентна формулювання:



при обмеженнях



Можна показати, що вирішення цієї задачі має вигляд



рівняння розділяє гіперплощини є і класифікатор визначається правилом



Якщо , то називається опорною точкою або опорним вектором. Легко бачити, що опорні точки лежать на межі розділяє смуги



отже, де - довільний опорний вектор.

У разі лінійно не роздільна класів дозволимо деяким об'єктам з навчальної вибірки "злегка" заходити за розділяє гіперплоскость:

при обмеженнях







де - деяка константа (параметр методу). При отримуємо попередній випадок (лінійно разделімих класів). Значення пропорційно величині, на яку заходить за кордон розділяє смуги. Зокрема, -й об'єкт буде класифікований неправильно тоді і тільки тоді, коли . Чим менше , тим менше об'єктів класифікується неправильно. З іншого боку, повинно бути досить велика, щоб завдання було спільної.

Еквівалентне формулювання:

при обмеженнях



Тут параметр регулює величину штрафу за те, що деякі точки виходять за кордон розділяє смуги. Побудована задача є задачею квадратичного програмування.

Квадратичне програмування (англ. Quadratic programming, QP) - особливий тип оптимізаційної задачі. Це задача оптимізації (зведення до мінімуму або максимуму) квадратичної функції декількох змінних при лінійних обмеженнях на ці змінні.
Для її вирішення можна використовувати загальні методи для вирішення таких завдань, однак існують досить ефективні спеціальні методи.

Можна показати, що рішення задачі єдино, якщо в навчальній вибірці є принаймні один представник кожного з класів.

Подальше удосконалення методу - використання спрямляющий просторів. Нехай вдається перейти від початкового простору ознак до нового простору (яке є тим що спрямлює) за допомогою деякого відображення



де - базисні функції . Новий класифікатор визначається тепер функцією



Тут - розділяє поверхню. Якщо відображення підібрано вдало, в новому просторі класи можуть бути лінійно разделіми або близькі до таких.

Виявляється, всі обчислення при навчанні і при розрахунку функції можна організувати так, що зустрічається тільки у виразах виду

Зокрема рівняння розділяє поверхні має вигляд



що еквівалентно



або .

Функція називається ядром. На практиці, таким чином, замість того, щоб випробовувати різні функції можна (так і роблять) підбирати найбільш підходяще ядро ​​ . Зауважимо, що не будь функція подана в вигляді , тобто може бути використана в якості ядра. Наведемо перелік деяких популярних функцій-ядер:



  • лінійне ядро: ;

  • многочлен степені : ');

  • радіальна функція: ;

  • сигмоїдальна ("нейронна") функція: .

Для того щоб використовувати метод опорних векторів для задачі класифікації з числом класом , можливо використовувати дві стратегії:

  • "Кожен проти кожного": побудувати класифікаторів на всіх можливих підзадачах бінарної класифікації.
    Бінарнарна класифікація - клас задач класифікації елементів набору даних на дві групи на підставі правила класифікації.
    В машинному навчанні ме́тод опо́рних векторі́в (рос. метод опорных векторов) - це метод аналізу даних для класифікації та регресійного аналізу за допомогою моделей з керованим навчанням з пов'язаними алгоритмами навчання, які називаються опо́рно-ве́кторними маши́нами (ОВМ, англ. support vector machines, SVM, також опо́рно-ве́кторними мере́жами, англ. support vector networks)
    Новий об'єкт класифікується всіма побудованими вирішальними правилами, потім вибирається переважаючий клас.

  • "Один проти всіх": навчити моделей на завданнях бінарної класифікації виду "один клас проти всіх інших". Клас нового об'єкта вибирається за максимальним значенням відступу.

1.1.4. Дерева рішень

Дерева рішень [3] є одним з найбільш наочних і універсальних алгоритмів навчання. До переваг дерев рішень слід віднести:



  • Можливість робити навчання на вихідних даних без їх додаткової предобработки (нормалізація і т. П.);

  • Нечутливість до монотонним перетворенням даних;

  • Стійкість до викидів;

  • Можливість обробляти дані з пропущеними значення;

  • Підтримка роботи з вхідними змінними різних (змішаних) типів;

  • Можливість інтерпретації побудованого дерева рішень.

Крім того, існують ефективні алгоритми їх налаштування (навчання), наприклад, CART - Classification and Regression Trees [3] або See5 / C5.0.

Основна ідея дерев рішень полягає в рекурсивном розбитті простору ознак з допомогою разбиений (splits): гіперплоскостей, паралельних координатним гіперплоскостей (якщо ознака - кількісний), або за категоріями (якщо ознака номінальний). У кожному з отриманих в кінці процедури "скриньок" функція апроксимується константою:



  • Для задачі класифікації:



  • Для завдання відновлення регресії:

В алгоритмі CART розбиття мають вигляд:



  • , якщо j-й ознака кількісний;

  • , якщо j -й ознака якісний, , де - набір значень, які може приймати j-й ознака.

Дерево будується рекурсивно за допомогою наступної жадібної процедури, на кожному кроці максимально зменшуючи значення функції, яка описує неоднорідність даних, що містяться у вузлі дерева. Нехай на поточному кроці мається розбиття простору ознак на області (ящики)

  • Вибираємо область .

  • Вибираємо і (або ), так, щоб домогтися максимального зменшення неоднорідності, або забрудненості, (impurity) .

  • Будуємо розбиття і повторюємо дії.

Розбиття проводяться до тих пір, поки в споруджувані вершини потрапляє достатня кількість точок навчальної вибірки, або поки дерево не досягне заданої глибини.

Використовують різні способи виміряти неоднорідність, наприклад,



  • Для задачі класифікації:

,

  • Для завдання відновлення регресії:

.

де - кількість точок з навчальної вибірки, що потрапили в область .

Інший важливий параметр моделі - це глибина дерева рішень, регулююча, "як сильно" буде розбито простір ознак. Невелике число розбиття може призвести до того, що побудована модель не буде враховувати деякі особливості розподілу ознак, що описують ті чи інші класи, і таким чином призведе до зменшення точності передбачення. Надмірне число розбиття може призвести до перенавчання моделі і зниження її узагальнюючої здібності.

Для того щоб уникнути перенавчання, використовується процедура відсікань (prunning) [3].



1.1.5. Випадковий ліс

Один із загальних підходів у машинному навчанні полягає у використанні композиції "слабких" вирішальних правил. Підсумкове правило будується шляхом зваженого голосування ансамблю базових правил. Для побудови базових правил і обчислення ваг останнім часом часто використовуються дві ідеї:

Баггінг (bagging - bootstrap aggregation): навчання базових правил відбувається на різних випадкових підвибірках даних або / і на різних випадкових частинах признакового опису; при цьому базові правила будуються незалежно один від одного.

Бустінг (boosting): кожне наступне базове правило будується з використанням інформації про помилки попередніх правил, а саме, ваги об'єктів навчальної вибірки підлаштовуються таким чином, щоб нове правило точніше працювало на тих об'єктах, на яких попередні правила частіше помилялися.

Експерименти показують, що, як правило, бустінг працює на великих навчальних вибірках, тоді як баггінг - на малих.

Однією з реалізацій ідеї баггінгу є випадковий ліс [2].

Випадковий ліс, а точніше - випадкові ліси (random forests), є одним з найбільш універсальних та ефективних алгоритмів навчання з учителем, застосовним як для задач класифікації, так і для задач відновлення регресії. Ідея методу [2] полягає у використанні ансамблю з дерев рішень (наприклад, ), які навчаються незалежно один від одного. Підсумкове вирішальне правило полягає в голосуванні всіх дерев, що входять до складу ансамблю.

Для побудови кожного дерева рішень використовується наступна процедура:



  • Генерація випадкової підвибірки з навчальної вибірки шляхом процедури вилучення з поверненням (так звана бутстреп-вибірка). Розмір даної підвибірки зазвичай становить 50-70% від розміру всієї навчальної вибірки.

  • Побудова дерева рішень по даній підвибірки, причому в кожному новому вузлі дерева змінна для розбиття вибирається не з усіх ознак, а з випадково обраного їх підмножини невеликої потужності . Дерево будується до тих пір, поки не буде досягнутий мінімальний розмір аркуша (кількість об'єктів, що потрапили в нього). Рекомендовані значення: для задачі класифікації , для завдання відновлення регресії .

Однією з модифікацій методу випадкових дерев є алгоритм вкрай випадкових дерев (extremely random forests), в якому на кожному етапі для вибору ознаки, за яким буде проводитися розбиття, використовується знову згенерувала випадкова бутстреп-вибірка.

Серед переваг алгоритму випадкових дерев можна виділити високу якість передбачення, здатність ефективно обробляти дані з великим числом класів і ознак, внутрішню оцінку узагальнюючої здатності моделі. Легко побудувати паралельну високо масштабовану версію алгоритму. Крім того, доведено, що даний алгоритм НЕ перенавчати (із зростанням ). Також метод володіє всіма перевагами дерев рішень, у тому числі відсутністю необхідності предобработки вхідних даних, обробкою як речових, так і категоріальних ознак, підтримкою роботи з відсутніми значеннями.



1.1.6. Градієнтний бустінг дерев рішень

Градієнтний бустінг дерев рішень (Gradient Boosting Trees - GBT) [6, 7] - інший універсальний алгоритм машинного навчання, заснований на використанні ансамблю дерев рішень. На відміну від випадкового лісу градієнтний бустінг є розвитком бустінг-ідеї.

Алгоритм мінімізує емпіричний ризик жадібним покроковим алгоритмом, аналогічним методом градієнтного спуску.

Градіє́нтний спуск (англ. gradient descent) - це ітераційний алгоритм оптимізації першого порядку, в якому для знаходження локального мінімуму функції здійснюються кроки, пропорційні протилежному значенню градієнту (або наближеного градієнту) функції в поточній точці.
Розглянемо, наприклад, завдання відновлення регресії використовують. Розглянемо сумарний штраф на навчальній вибірці як функцію від значень вирішального правила в точках :

Тоді градієнт функції дорівнює



На попередньому етапі алгоритм будує оптимальну константну модель .

Градіє́нт, Ґрадіє́нт - міра зростання або спадання в просторі якоїсь фізичної величини на одиницю довжини.
На -й ітерації конструюється дерево рішень (невеликої глибини), апроксимує компоненти вектора антіградіента, обчисленого для поточної моделі .
Дерево ухвалення рішень (також можуть називатися деревами класифікацій або регресійними деревами) - використовується в галузі статистики та аналізу даних для прогнозних моделей. Структура дерева містить такі елементи: «листя» і «гілки».
Після цього значення у вузлах побудованого дерева переобчислюють, так, щоб мінімізувати сумарну величину штрафу . Далі здійснюємо присвоєння , що і завершує -ю ітерацію. Тут - параметр регуляризації (shrinkage), покликаний боротися з можливим перенавчанням. Він вибирається з інтервалу (0,1].

Для вирішення завдання відновлення регресії часто використовуються наступні штрафні функції:


  • квадратичний штраф



  • абсолютний штраф



  • або функція Хьюбера

Зауважимо, що функція Хьюбера і квадратичний штраф діфференцируєми усюди, тоді як абсолютний штраф - скрізь, крім точок, в яких .

Для задачі класифікації з класами метод залишається колишнім, тільки замість однієї функції конструюють відразу функцій В якості штрафу можна використовувати крос-ентропію

де

- є оцінка ймовірності того, що . Підсумковий класифікатор визначається як



Більш докладний опис алгоритму см. В [6, 7].

Іншим популярним методом, що використовують ідею бустінга, є алгоритм AdaBoost і його модифікації [5].

1.2. Кластеризація

В задачах навчання без вчителя (unsupervised learning) у об'єктів не відомі виходи, і потрібно знайти деякі закономірності в даних. До завдань навчання без учителя відносять завдання кластеризації, пониження розмірності, візуалізації та ін. Тут розглядається тільки кластеризація.

Задача кластеризації - це задача розбиття заданого набору об'єктів на кластери, т. Е. Групи близьких за своїм ознаковими опису об'єктів. "Схожі" один на одного об'єкти повинні входити в один кластер, «не схожі" об'єкти повинні потрапити в різні кластери.

Близькість ("схожість") об'єктів вимірюється на основі функції відстані



1.2.1. Метод центрів тяжіння

Розглянемо один з алгоритмів, що вирішують завдання кластеризації - метод центрів тягарів (K-means). На вхід алгоритму надходить набір даних



і натуральне число - кількість кластерів, на які потрібно розбити дані.

Натура́льні чи́сла - числа, що виникають природним чином при лічбі. Це числа: 1, 2, 3, 4, … Множину натуральних чисел прийнято позначати знаком N . .}
Алгоритм реалізує покрокову процедуру мінімізації





де - центр ваги об'єктів, що відносяться -го кластеру:

.

При цьому не гарантується знаходження глобального мінімуму. На попередньому етапі будується деякий розбиття вхідних даних на груп (наприклад, випадково). Нехай - номер групи, до якої належить -й об'єкт. У ході роботи алгоритму значення оновлюються. Наприкінці роботи алгоритму значення відповідатимуть разбиению даних на кластери. Кожна ітерація являє собою послідовність наступних кроків:



  • Обчислюємо центр ваги об'єктів у кожній групі.

  • Для кожного об'єкта знаходимо , для якого відстань від до , тобто , мінімальне. Оновлюємо функцію , поклавши .

Ітерації завершуються, коли настає стабілізація значень C (i), або по досягненні максимального значення числа ітерацій.

1.2.2. Метод медіан

Метод центрів тягарів працює з явними описами об'єктів . Модифікацією цього методу є метод медіан, або метод серединних точок, ( -medians, або -medoids). На вхід цього алгоритму подається число кластерів і матриця відстаней , де . Зауважимо, що сама функція може бути не відома.

Алгоритм нічим не відрізняється від попереднього, але замість центру тягарів, для кожної групи будемо знаходити медіану, або серединну точку, де

Кожна ітерація являє собою послідовність наступних кроків:



  • Обчислюємо медіану об'єктів у кожній групі.

  • Для кожного об'єкта знаходимо , для якого мінімально. Оновлюємо функцію поклавши .

Як правило, результати роботи алгоритмів центрів тягарів і медіан (якщо вони обидва застосовні до даних) близькі.


Скачати 201.51 Kb.

  • 1.1. Задача навчання з учителем 1.1.1. Постановка задачі навчання з учителем
  • 1.1.2. Метод
  • 1.1.3. Машина опорних векторів
  • 1.1.6. Градієнтний бустінг дерев рішень
  • 1.2.1. Метод центрів тяжіння