ТИ МАШИНА
І Я МАШИНА
Частина 3
У попередньому матеріалі міні-курсу лекцій про машинне навчання спільно з Abto Software ми розглянули, які види машинного навчання існують та які типи завдань вони здатні вирішувати, а сьогодні заглибимося в технічні деталі й поговоримо про алгоритми, що стають у пригоді під час розв'язання різних завдань машинного навчання.


Написав: Дмитро Чумаченко
Картки намалювала: Дарія Манцола
Алгоритм методу виглядає так:

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


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

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

Перевагою методу є його простота в реалізації, а недоліком те, що необхідно знати кількість кластерів заздалегідь.



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

Алгоритм методу виглядає так:

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


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

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

Перевагою методу є його простота в реалізації, а недоліком те, що необхідно знати кількість кластерів заздалегідь.



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

Алгоритм методу виглядає так:

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


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

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

Перевагою методу є його простота в реалізації, а недоліком те, що необхідно знати кількість кластерів заздалегідь.



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

ЗА ПІДТРИМКИ
Наївний Баєс
Кожен з нас кожного дня отримує спам, а поштовий сервіс автоматично розподіляє більшість таких листів у папку «Спам». Раніше на методі наївного Баєса працювали всі спам-фільтри. Наприклад, машина рахувала, скільки разів трапляється слово «приз» у звичайних листах, а скільки в спамі. Потім перемножувала ці ймовірності за формулою Баєса, підсумовувала результати за всіма словами і виявляла спам.
Найпростіші рішення, як правило, найкрутіші, і наївний Баєс є хорошим прикладом цього. Попри великі успіхи машинного навчання за останні роки, цей алгоритм залишається не тільки простим, а й швидким, точним і надійним.
Наївний метод Баєса – це набір методів класифікації, заснованих на теоремі Баєса. Це не єдиний метод, а сімейство методів, які поділяють загальний принцип, згідно з яким кожна ознака, що класифікується, не залежить від значення будь-якої іншої ознаки. Наприклад, фрукт можна вважати яблуком, якщо він червоний, круглий і не перевищує 15 см у діаметрі. Наївний баєсівський класифікатор вважає, що кожна з цих «ознак» (червоний, круглий, діаметр 15 см) вносить незалежний внесок у ймовірність того, що фрукт – це яблуко, незалежно від будь-яких кореляцій між ознаками. Але насправді функції не завжди незалежні, а їхні параметри не завжди пов'язані один з одним. Саме це є недоліком методу Баєса, і тому його називають «наївним».
Дерева рішень
Як банку дізнатися, хто поверне кредит, а хто ні? На 100% це неможливо, але у банку є тисячі профілів клієнтів, які вже брали кредити, з даними про їхню освіту, стать, вік, дохід та багато іншого для кредитного скорингу (оцінки кредитоспроможності). Машина розділяє наявні дані на класи за допомогою запитань, на які можна відповісти «Так» або «Ні», а потім «проганяє» нового клієнта за ними. Саме так і з'являється дерево запитань.
Ще одним дуже популярним та простим у реалізації методом класифікації є дерева рішень. Дерево рішень будує моделі класифікації або регресії у вигляді деревоподібної структури. Метод розбиває набір даних на менші й менші підмножини. Кінцевий результат – дерево з вузлами рішення і кінцевими вузлами. Що глибше дерево, то складніші правила ухвалення рішень і точніша модель.
Однією з основних переваг дерев рішень є їхня інтуїтивність – тобто класифікаційна модель, що представлена у вигляді дерева рішень. Вона легко інтерпретується користувачем та спрощує розуміння завдання, яке потрібно вирішити, тому що дозволяє зрозуміти, чому конкретний об'єкт належить до відповідного класу. Ще однією важливою перевагою дерев рішень є їхня універсальність для вирішення задач класифікації та регресії. Але є в алгоритму і недоліки. По-перше, це нестабільність процесу. Тобто невеликі зміни в наборі даних можуть призводити до побудови іншого дерева. Це пов'язано з ієрархічністю дерева: зміни в вузлах на верхньому рівні можуть призвести до змін у всьому дереві нижче. По-друге, це складність контролю розміру дерева, що є критичним фактором, який зумовлює якість вирішення завдання.
На Заході все більше розвивається сфера контролю стану здоров'я на основі постійного аналізу його активності. Пацієнт носить зчитувач фізичної активності та показників, вони відправляються його лікарю та аналізуються разом з його аналізами та базою даних інших пацієнтів. Для цього зазвичай використовується логістична регресія.
Логістична регресія
Наприклад, маємо вибірку пацієнтів з показниками куріння, харчування, фізичної активності, вживання алкоголю. За допомогою логістичної регресії можемо побудувати модель, яка використовує ці чотири характеристики способу життя для передбачення наявності або відсутності ішемічної хвороби серця у вибірці пацієнтів. Використовувати модель можна, щоб дізнатися, наприклад, наскільки більше курці схильні до ішемічної хвороби серця, ніж некурці. Тобто, за отриманими значеннями, беремо пацієнта-курця та визначаємо, до якого класу він, ймовірно, належить: тих, хто має ішемічну хворобу серця, чи ні.
Логістичну регресію добре використовувати для завдань бінарної класифікації, тобто коли на виході потрібно отримати відповідь, до якого з двох класів належить об'єкт. Логістична регресія схожа на лінійну тим, що в ній теж потрібно знайти значення коефіцієнтів для вхідних змінних, але різниця в тому, що вихідне значення перетвориться за допомогою нелінійної або логістичної функції. Логістична функція перетворює будь-яке значення в число в межах від 0 до 1. Так і передбачається ймовірність належності до одного чи другого класу. Тобто, на відміну від логістичної регресії, тут не проводять передбачення значення числової змінної, виходячи з вибірки вихідних значень, а замість цього значенням функції є ймовірність того, що це початкове значення належить до певного класу.
До недоліків логістичної регресії можна віднести залежність від набору даних та низьку стійкість до помилок.
Інженери R&D компанії Abto Software розробили технологію, яка за допомогою камери автоматично визначає хто із велосипедистів вдягнув шолом, а хто ні.
Лінійний дискримінантний аналіз
Якщо класів більше, ніж два, то краще використовувати лінійний дискримінантний аналіз. Наприклад, лікарю потрібно визначити діагноз пацієнта. У нього є множина значень аналізів для кожного можливого захворювання. Лікар бере ці аналізи у пацієнта і порівнює їхні значення зі значеннями для захворювань. Так визначають ймовірності кожного з переліку захворювань у пацієнта.
Метод містить статистичні властивості даних, розраховані для кожного класу. Під час цього передбачається, що дані мають нормальний розподіл, тому перед початком роботи необхідно видалити з даних аномальні значення. Варто зазначити, що, на відміну від цього методу, в інших нормальний розподіл не обов'язковий. Прогнозні класи знаходять шляхом обчислення дискримінантного значення для кожного класу, тобто знаходження лінійної залежності комбінації значень для вибору класу, а потім обирають клас із найбільшим значенням.
Головна перевага методу – це простота реалізації та інтерпретації результатів, недолік – чутливість до розподілу вхідних даних, коли навіть невелике їхнє змінення призводить до значних змін результатів класифікації.
Метод опорних векторів
Згідно з доповіддю Всесвітньої організації інтелектуальної власності за 2019, кількість патентів у світі зростає саме в галузі застосування методу опорних векторів. Метод опорних векторів використовується для задач класифікації тексту, як-от призначення категорії і виявлення спаму. Також його використовують для розпізнавання зображень, він дуже популярний у багатьох сферах розпізнавання рукописних цифр, наприклад, у послугах поштової автоматизації, тобто розпізнавання поштового індексу відправника та отримувача.
Метод опорних векторів – найпопулярніший для класичної класифікації, тому що він простий та швидкий. Виходячи з того, що об'єкт, який перебуває в N-вимірному просторі, належить до одного з двох класів, метод опорних векторів будує гіперплощину з розмірністю (N – 1), щоб всі об'єкти виявилися в одній з двох груп. Що ж таке гіперплощина? Як простий приклад для завдання класифікації, що має тільки два класи, ви можете уявити собі гіперплощину як лінію, яка розділяє і класифікує набір даних. До того ж, що далі від гіперплощини лежать наші точки даних, то більше ми впевнені в тому, що вони були правильно класифіковані. Що менше схожих ознак між даними, то менша ймовірність належності до одного класу. Тому ідеально, якщо точки даних перебувають якомога далі від гіперплощини, і до того ж залишаються на правильній стороні.

Головним недоліком методу є те, що він підходить тільки до розв'язання завдань з двома класами.
Метод К-середніх – один із найпопулярніших алгоритмів кластеризації, який використовується для поділу точок набору даних на K кластерів на основі найближчих середніх значень. До того ж, необхідно, щоб відстань між точками в кожному кластері була мінімальною.
Метод К-середніх
Алгоритм методу виглядає так:

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


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

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

Перевагою методу є його простота в реалізації, а недоліком те, що необхідно знати кількість кластерів заздалегідь.



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

Стекінг
На практиці компанії, що використовують машинне навчання для вирішення бізнес-завдань, користуються не одним методом, а ансамблем алгоритмів, тобто декількома алгоритмами для вирішення одного завдання машинного навчання. Це підвищує точність результатів. Одним з методів ансамблю алгоритмів є стекінг. Під час стекінгу на вхід різних моделей подаються однакові набори даних, а їхній вихід подається на вхід вирішального алгоритму, тобто алгоритму, що розраховує результат. До того ж, моделі першого шару повинні містити різні алгоритми. На практиці використовується нечасто, але є приклади дуже вдалого застосування, наприклад, в змаганні Otto Group Product Classification на сервісі змагань з машинного навчання Kaggle, призом якого були 10 тисяч доларів. Перше місце дали тим, хто запропонував рішення використовувати стекінг 33 класифікаційних алгоритмів
Беггінг
Ще одним популярним методом ансамблів є беґґінг (від англ. Bootstrap aggregating). На відміну від попереднього, тут використовують один алгоритм, але на його вхід подають випадкові вибірки з набору даних, і дані в цих випадкових вибірках можуть повторюватися. На вхідних даних навчаємо алгоритм, а потім усереднюємо результ. На практиці використовується нечасто, але є приклади дуже вдалого застосування, наприклад, в змаганні Otto Group Pт, якщо потрібна регресія, або вибираємо оптимальний голосуванням, тобто той, що вийшов більшу кількість разів, якщо потрібна класифікація.
В 2012 році компанія Netflix, розуміючи, що ринок змінюється дуже швидко, запустила конкурс на розробку рекомендаційної системи з призом у мільйон доларів США.
Більшість запропонованих рішень використовували випадковий ліс як основний алгоритм. За результатами конкурсу Netflix створили унікальну рекомендаційну систему, що взяла потрохи з найкращих запропонованих алгоритмів.
Випадковий ліс
Найпопулярніший методу беґґінгу – випадковий ліс. Як зрозуміло з його назви, він містить велику кількість окремих дерев рішень, які діють як ансамбль. Кожне окреме дерево у випадковому лісі обчислює прогноз класифікації, і клас із найбільшою кількістю голосів стає прогнозом моделі. Тобто ми робимо класифікацію методом дерев рішень багато разів і обираємо результатом той варіант, який випадав найчастіше.
Основна концепція випадкового лісу проста, але саме через неї модель так добре працює:
Велика кількість некорельованих дерев рішень, тобто тих, що знаходять рішення незалежно одне від одного й діють спільно, перевершить будь-яке рішення, отримане одним деревом рішення.

Саме некорельовані моделі можуть створювати ансамблеві прогнози, які є точнішими, ніж будь-який з окремо взятих прогнозів. Причиною такого ефекту є те, що кожне дерево рішень «захищає» одне одного від індивідуальних помилок: хоча деякі дерева рішень можуть бути неправильними, більшість із них будуть правильними, тому як група дерева будуть рухатися в правильному напрямку.



До переваг методу можна віднести можливість ефективно обробляти дані з великою кількістю ознак і класів та високу масштабованість. Серед недоліків можна виділити великий розмір моделей, що будуються. Що більша модель, то вища її обчислювальна складність та швидкість знаходження рішень.
Бустінг
Ще один ефективний ансамбль методів – бустінг. Особливістю бустінгу, на відміну від бегінгу, є послідовне, а не паралельне використання алгоритму, до того ж особливу увагу кожного наступного алгоритму звертається на помилки попереднього. Щоб знайти такі помилки, ми застосовуємо алгоритми базового навчання з різним розподілом. Щоразу, коли застосовується базовий алгоритм навчання, він генерує нове слабке правило прогнозування. Це ітеративний, тобто покроковий, процес, і після великої кількості ітерацій бустінг об'єднує ці помилки в одне правило.
Abto Software – українська ІТ компанія, що з 2007 року створює унікальні програмні рішення для лідерів у галузі інтернету, електронного урядування, енергетики, медицини, будівництва та безпеки. Візія компанії – стати партнером NASA та розвивати українських комп'ютерних інженерів. З 2015 року у Abto Software функціонує R&D відділ, який спеціалізується на Artificial Intelligence, Machine Learning та Computer Vision проектах і розробляє прототипи власних продуктів. Щороку компанія організовує безкоштовний літній навчальний інтенсив з Artificial Intelligence & Computer Vision.