Як змусити працювати бінарний класифікатор трішки краще

Disclaimer: пост написаний за мотивами даного . Я підозрюю, що більшість читачів прекрасно знає, як працює Наївний Байєсівський класифікатор, тому пропоную лише мигцем хоча б глянути на те, про що там йдеться, перед тим як переходити під кат.
Рішення задач за допомогою алгоритмів машинного навчання давно і міцно увійшло в наше життя. Це відбулося за всіма зрозумілим і об'єктивних причин: дешевше, простіше, швидше, ніж явно кодіть алгоритм вирішення кожної окремої задачі. До нас, звичайно, доходять «чорні ящики» класифікаторів (навряд чи той же ВК запропонує вам свій корпус розмічених імен), що не дозволяє ними керувати повною мірою.
Тут я б хотів розповісти про те, як спробувати домогтися «кращих» результатів роботи бінарного класифікатора, про те які характеристики бінарний класифікатор має, як їх вимірювати, і як визначити, що результат роботи став «краще».
 
 Теорія. Короткий курс

1. Бінарна класифікація

Нехай — безліч об'єктів, — кінцеве безліч класів. Класифікувати об'єкт — використовувати відображення . Коли , така класифікація називається бінарної , тому що у нас всього 2 варіанти на виході. Для простоти далі будемо вважати, що , оскільки абсолютно будь-яке завдання бінарної класифікації можна до цього призвести. Зазвичай , результатом відображення об'єкта в клас є дійсне число, і, якщо воно вище заданого порога , то об'єкт класифікується, як позитивний , і його клас — 1.
 
 

2. Таблиця спряженості бінарного класифікатора

Очевидно, що передбачений клас об'єкта, отриманий в результаті відображення , може або співпасти в реальним класом, або ні. Разом 4 варіанти в сумі. Це дуже наочно демонструється даної табличкою:
 
Якщо ми знаємо кількісні значення кожної з оцінок — ми знаємо все що можна про даний класифікаторі і можемо копати далі.
(Я навмисно не використовую терміни типу «помилка 1го роду», тому що мені це здається неочевидним і непотрібним)
Далі будемо використовувати наступні позначення:
 
     
— кількість True Positive результатів на даній вибірці.
  — кількість True Negative результатів на даній вибірці.
  — кількість False Positive результатів на даній вибірці.
  — кількість False Negative результатів на даній вибірці.
 
 

3. Характеристики бінарного класифікатора

Точність (precision) — показує, скільки з передбачених позитивних об'єктів, виявилися дійсно позитивними.
 
 Повнота (recall) — показує, скільки від загального числа реальних позитивних об'єктів, було передбачено, як позитивний клас.
 
Ці дві характеристики є основними для будь-якого бінарного класифікатора. Яка з характеристик важливіше — все залежить від завдання. Наприклад, якщо ми хочемо створити «шкільну пошукову систему», то в наших інтересах буде прибрати «недитячий» контент з видачі, і тут набагато важливіше повнота, ніж точність. У разі ж визначення статі імені — нам швидше цікава точність, ніж повнота.
 F-міра (F-measure) — характеристика, яка дозволяє дати оцінку одночасно по точності і повноти.
 
Коефіцієнт задає співвідношення ваг точності і повноти. Коли , F-міра надає однакову вагу обом характеристикам. Така F-міра називається збалансованою, або
 
 False Positive Rate () — показує, скільки від загального числа реальних негативних об'єктів, виявилися передвіщеними невірно.
 
 
 

4. ROC-крива і її AUC

ROC-крива — графік, який дозволяє оцінити якість бінарної класифікації. Графік показує залежність TPR (повноти) від FPR при варіюванні порога. У точці (0,0) поріг мінімальний, точно так само мінімальні і TPR і FPR . Ідеальним випадком для класифікатора є прохід графіка через точку (0,1). Очевидно, що графік даної функції завжди монотонно не убуває.
 
 AUC (Area Under Curve) — в області бінарної класифікації, даний термін (площа під графіком) використовується виключно стосовно ROC-кривої. AUC дає кількісну характеристику ROC-кривої: чим більше — тим краще. AUC — еквівалентна ймовірності, що класифікатор присвоїть більшого значення випадково обраному позитивному об'єкту, ніж випадково обраному негативному об'єкту. Саме тому раніше було сказано, що, зазвичай , позитивному класу ставиться оцінка вище, ніж негативному.
Коли AUC = 0.5 , то даний класифікатор дорівнює випадковому. Якщо AUC < 0.5 , то можна просто перевернути видаються значення класифікатором.
 
 Крос валідація Методів крос валідації (оцінки якості бінарного класифікатора) існує багато, і це — тема для окремої статті. Тут я хочу просто розглянути один з найпопулярніших методів, щоб зрозуміти, як ця штука взагалі працює, і навіщо вона потрібна.
Побудувати ROC-криву, звичайно ж, можна по будь-якій вибірці. Однак, ROC-крива, побудована за навчальною вибіркою, буде зміщена вліво-вгору через перенавчання. Щоб цього уникнути і отримати найбільш об'єктивну оцінку, використовується крос валідація.
 K-fold cross validation — пул розбивається на k фолдов, потім кожен фолд використовується для тіста, в той час як інші k-1 фолдов — для навчання. Значення параметра k може бути довільним. В даному випадку я використав його рівним 10. Для наданого класифікатора статі імені вийшли наступні результати AUC (get_features_simple — одна значуща буква, get_features_complex — 3 значущих літери)                                                              
fold get_features_simple get_features_complex
0 0.978011 0.962733
1 0.96791 0.944097
2 0.963462 0.966129
3 0.966339 0.948452
4 0.946586 0.945479
5 0.949849 0.989648
6 0.959984 0.943266
7 0.979036 0.958863
8 0.986469 0.951975
9 0.962057 0.980921
avg 0.9659703 0.9591563
 Практика

1. Підготовка

Весь репозиторій тут .
Я взяв той же розмічений файл і замінив в ньому «m» на 1, «f» — 0. Даний пул будемо використовувати для навчання, як і автор попередньої статті. Озброївшись першою сторінкою видачі улюбленого пошуковика і awk, я наклепав список імен, яких немає в первісному. Даний пул буде використовуватися для тесту.
Змінив функцію класифікації так, щоб вона повертала ймовірності позитивного і негативного класів, а не логарифмічні показники.
 Функція класифікації
def classify2(classifier, feats):
    classes, prob = classifier
    class_res = dict()
    for i, item in enumerate(classes.keys()):
        value = -log(classes[item]) + sum(-log(prob.get((item, feat), 10**(-7))) for feat in feats)
        if (item is not None):
            class_res[item] = value
    eps = 709.0
    posVal = '1'
    negVal = '0'
    posProb = negProb = 0
    if (abs(class_res[posVal] - class_res[negVal]) < eps):
        posProb = 1.0 / (1.0 + exp(class_res[posVal] - class_res[negVal]))
        negProb = 1.0 / (1.0 + exp(class_res[negVal] - class_res[posVal]))
    else:
        if class_res[posVal] > class_res[negVal]:
            posProb = 0.0
            negProb = 1.0
        else:
            posProb = 1.0
            negProb = 0.0
    return str(posProb) + '\t' + str(negProb)

 

2. Реалізація та використання

Як написано в заголовку, моїм завданням було змусити працювати бінарний класифікатор краще, чим він працює за замовчуванням. В даному випадку, ми хочемо навчитися визначати стать імені, краще ніж по ймовірності Наївного Байеса 0.5. Для цього і була написана ця найпростіша утиліта. Написана вона на С + +, тому що gcc є скрізь. Сама реалізація нічого цікавого, як мені здається, не представляє. З ключем -? або — help можна почитати довідку, я постарався описати її максимально детально.
Ну а тепер, власне те, до чого ми йшли: оцінка класифікатора і його тюнінг. На виході nbc.py створює простирадло з файлів з результатами класифікації, прямо їх я і використовую далі. Для наших цілей, нам буде наочно побачити графіки точності від порога, повноти від порога і F-міри від порога. Їх можна побудувати наступним чином:
 
$ ./OptimalThresholdFinder -A 3 -P 1 < names_test_pool.txt_simple -x thr -y prc -p plot_test_thr_prc_simple.txt
$ ./OptimalThresholdFinder -A 3 -P 1 < names_test_pool.txt_simple -x thr -y tpr -p plot_test_thr_tpr_simple.txt
$ ./OptimalThresholdFinder -A 3 -P 1 < names_test_pool.txt_simple -x thr -y fms -p plot_test_thr_fms_simple.txt
$ ./OptimalThresholdFinder -A 3 -P 1 < names_test_pool.txt_simple -x thr -y fms -p plot_test_thr_fms_0.7_simple.txt -a 0.7

Для освітніх цілей, я зробив 2 графіка F-заходи від порога, з різними вагами. Другий вага був обраний 0.7, тому що в нашій задачі нам більше цікава точність, ніж повнота. Графік за замовчуванням будується на основі 10000 різних точок, це дуже багато для таких простих даних, але це нецікаві тонкощі оптимізації. Точно так же побудувавши дані графіків для get_features_complex, отримуємо такі результати:
 
 
З графіків стає очевидно, що класифікатор показує кращі результати аж ніяк не при порозі 0.5. Графік F-міри виразно демонструє, що «складна фіча» дає кращий результат на всьому варіюванні порога. Це досить логічно, враховуючи, що на те вона і «складна». Отримаємо значення порога, при яких F-міра досягає максимуму:
 
$ ./OptimalThresholdFinder -A 3 -P 1 < names_test_pool.txt_simple --target fms --argument thr --argval 0
Optimal threshold = 0.8 Target function = 0.911937      Argument = 0.8
$ ./OptimalThresholdFinder -A 3 -P 1 < names_test_pool.txt_complex --target fms --argument thr --argval 0
Optimal threshold = 0.716068    Target function = 0.908738      Argument = 0.716068
Погодьтеся, ці значення набагато краще тих, що опинилися при порозі за замовчуванням 0.5.
 
 Висновок Такими простими маніпуляціями, ми змогли підібрати оптимальний поріг Наївного Байеса для визначення статі імені, який працює краще порога за замовчуванням. Тут постає резонне питання, як ми визначили, що він працює «краще»? Я не раз згадав про те, що в даній задачі нам важливіше точність, ніж повнота, однак питання про те наскільки вона важливіше — дуже і дуже складний, тому для оцінки роботи класифікатора використовувалася збалансована F-міра, яка в даному випадку може бути об'єктивним показником якості.
Що набагато цікавіше, результати роботи бінарного класифікатора на основі «простий» і «складною» фичи в підсумку виявилися приблизно однаковими, відрізняючись значенням оптимального порогу.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.