Повна версія

Головна arrow Інформатика arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ЧАСТИНА II ОСНОВИ МАШИННОГО НАВЧАННЯ

ВСТУП В МАШИННЕ НАВЧАННЯ. ЕТАПИ ВИРІШЕННЯ ЗАВДАНЬ МАШИННОГО НАВЧАННЯ

В результаті освоєння даного розділу навчається буде: знати

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

Цілі і завдання машинного навчання

Завдання машинного навчання

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

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

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

Як би людина, яка не знає алгоритмів машинного навчання, підійшов до вирішення даного завдання? По-перше, він спробував би відшукати слова або послідовності слів в тексті листа або його заголовку, які часто можна побачити в спам, наприклад такі слова або словосполучення, як «тільки зараз», «неймовірна пропозиція», «подарунок», «купите» , «знижка» і т.д. По-друге, спробував би знайти безліч картинок або ж, наприклад, посилань на шкідливі сайти. Такі критерії можуть в тій чи іншій мірі характеризувати «спамность» листи. Кожному критерію можна зіставити деяку змінну, яка визначала б його значення. У табл. 4.1 наведено опис таких змінних.

Таблиця 4.1

Ознаки «сіамності» повідомлення

Мінлива

опис

Можливі значення

х

Відсоток слів зі словника спама, таких як «подарунок», «знижка» і т.п.

[0,0; 1,0] -

речовинний ознака

х2

Кількість картинок в тексті

[О..Ч-oo] -

натуральне число, дискретні значення

хз

Наявність посилань на шкідливий сайт

{0,1} -

бінарний ознака

Критерії, представлені в табл. 4.1, в машинному навчанні називаються ознаками (Jeatures) x (Флах, 2015) і є головними параметрами , визначальними об'єкт завдання. Саме з їх допомогою алгоритм машинного навчання буде намагатися вирішити задачу. Таким чином, від того, наскільки правильно і повно підібрані ознаки, що описують об'єкт завдання, залежить якість роботи алгоритму машинного навчання. Про оцінку якості роботи алгоритму машинного навчання ми будемо говорити в параграфі 4.4, а поки спробуємо розібратися з тим, як же алгоритм машинного навчання буде використовувати ці ознаки.

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

ня, є зважена сума всіх цих ознак. Зваженою сумою називається згортка значень ознак з деякими ваговими коефіцієнтами, що визначають ступінь важливості даної ознаки. Далі, отримавши значення згортки, можна використовувати деяку порогову функцію, область значень якої {0; 1} - Ні-спам і спам.

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

Якщо уявити функцію як sign (x) = [т> 0], де вираз в квадратних дужках являє собою нотацію Айверсона [2]

то стане очевидно, що вся функція (4.2) як раз задає гіперплоскость, що представляє собою кордон між двома класами - (0; 1}. Функція (4.2) в термінах машинного навчання називається алгоритмом, за допомогою якого вирішується поставлене завдання. У даному випадку представлений алгоритм лінійного класифікатора (linear classifier) ' [2] . Більш докладно про алгоритми класифікації ми будемо говорити в гл. 5.

Вибравши ваги для згортки, ми отримаємо так звану модель класифікації, тобто конкретний вид функції (4.2), що дозволяє [4]

вирішувати нашу задачу класифікації. Як вибрати ваги w для даної функції? Можна спробувати поставити їх вручну, але швидко стає ясно, що зробити це не так просто, так як різні ваги для одного і того ж набору значень ознак будуть давати різні види функцій, але при цьому для даних об'єктів значення самої функції відрізнятися не будуть. Приклад в табл. 4.2 наочно це демонструє.

Таблиця 4.2

Приклад схожих між собою моделей

значення

ознак

Спам?

приклад моделі

альтернатива

(1,1.1)

1

(1,0,1)

0

(1,0,0)

1

Так, в першому рядку табл. 4.2 для об'єкта зі значеннями ознак (1, 1, 1) і відповіддю «спам» можна підібрати дві функції / (х, w) = sign (х { + х 2 + х 3 ) і / (х, w) = sign ( х { + 2 + Зх 3 + 1), які для цього набору ознак повертатимуть відповідь «спам». У даній ситуації виникає невизначеність - яку з двох моделей необхідно вибрати?

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

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

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

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

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

По-друге, у визначенні повноти присутній термін «вірні гіпотези». Ми оцінюємо повноту по деякому класу, наприклад по класу «спам». Тоді гіпотезою є пара «об'єкт - відповідь класифікатора». Відповідно, вірною гіпотезою називається така гіпотеза, яка підтверджується в нашому випадку тестової вибіркою, тобто в тестовій вибірці міститься така пара «об'єкт - відповідь». Загальне ж число відповідей по даному класу - це число пар «об'єкт - відповідь», де відповідь - це цікавий для нас клас. У прикладі зі спамом - це число всіх пар «об'єкт - спам». [5]

Формула повноти для випадку класифікації спаму виглядає наступним чином (більш загальну формулу ми розглянемо в параграфі 4.4):

де N - загальне число прикладів в тестовій вибірці; х { - i-й об'єкт тестової вибірки; г /, - правильна відповідь але г-му об'єкту.

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

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

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

Таким чином, вибір ваг можна визначити як завдання математичного програмування, наприклад:

де mm означає мінімізацію по вектору w .

w

У формулі (4.3) представлено не що інше, як оцінка середньоквадратичної помилки. Причому з точки зору завдання мінімізації від вилучення корінь та дисперсії можна відмовитися:

Таким чином ми зможемо мінімізувати всі помилки на навчальній вибірці. Однак постає непросте питання: як мінімізувати цей вислів аналітичними методами, якщо під функцією f (x , w) коштує операція sign ? Це досить неприємне заняття, так як дана функція недіфференціруемого і знайти її мінімум просто так не вийде. Саме в цій точці виникає безліч алгоритмів, зване лінійними алгоритмами класифікації. Про них ми поговоримо в гл. 5, але вся різниця між різними лінійними алгоритмами класифікації в основному і полягає в тому, що в різних алгоритмах вибирається та чи інша апроксимация функції sign, щоб було простіше мінімізо- вать помилку.

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

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

Всі методи машинного навчання можна класифікувати в залежності від способу навчання. Метод навчання, розглянутий в завданні фільтрації спаму, називається навчанням з учителем. Навчання з учителем (supervised learning) - це метод навчання моделі, що полягає в тому, що для кожного об'єкта, на якому відбувається навчання (в прикладі зі спамом - его набір ознак, вирахуваних за листом) задається пара: «прецедент - рішення». Таким чином, навчання з учителем фактично моделює індуктивний висновок, коли на основі прикладів робиться деяке узагальнення. Навчання без вчителя (unsupervised learning) передбачає, що заздалегідь відомих відповідей для набору прецедентів немає і модель повинна сама, на основі, наприклад, подібності даних, об'єднати дані в кластер, який би і був відповіддю, загальним для цих даних. У цьому сенсі навчання без вчителя є прекрасним інструментом для пошуку нових знань і даних в роботі аналітика. Існує безліч інших різновидів методів навчання, проте в даному посібнику будуть розглядатися саме ці два.

  • [1] Див .: Флах П. Машинне навчання. Наука і мистецтво побудови алгоритмів, які витягують знання з даних. М .: ДМК-Пресс, 2015.
  • [2] 2 Грехем Р., Кнут Д., Паташік О. Конкретна математика. Підстави інформатики. М .: Світ, 1998..
  • [3] 2 Грехем Р., Кнут Д., Паташік О. Конкретна математика. Підстави інформатики. М .: Світ, 1998..
  • [4] Ian II., Witten Е. F. Data Mining. Practical Machine Learning Tools andTechniques. Burlington: Elsevier, 2011 року.
  • [5] Hastie Т., Tibshirani R, Friedman J. The Elements of Statistical Learning, DataMining, Inference, and Prediction. California: Springer, 2008.
 
<<   ЗМІСТ   >>