Байєсовські алгоритми класифікації ґрунтуються на знанні апріорних ймовірностей класів і законів розподілу ймовірностей ознак в кожному класі. На практиці нам відома тільки навчальна вибірка об'єктів. Будемо вважати елементи вибірки незалежними випадковими величинами, що мають однакове розподіл. Потрібно за вибіркою оцінити щільність цього розподілу.
Потрібно оцінити щільність розподілу за вибіркою незалежних випадкових векторів, розподілених за цим законом.
Існують три основні підходи до оцінювання щільності розподілу: непараметрический, параметричний і відновлення сумішей розподілів.
Непараметричне відновлення щільності
Будемо вважати, що загальний вигляд функції розподілу невідомий, відомі тільки деякі властивості - наприклад, функція гладка, безперервна. Тоді для оцінки щільності застосовують непараметричні методи оцінювання.
Побудувати функцію, яка апроксимувати б невідому функцію в деякому сенсі.
Гістограмного метод оцінювання
Ідея. якщо - щільність випадкового вектора, то, де, - міра області. Якщо - вибірка, - число значень вибірки в, то
Значить, - оцінка щільності.
- знайдемо обмежену область простору (простору об'єктів), що містить всі вектори з навчальної вибірки;
- розіб'ємо на непересічні області;
- якщо - кількість елементів навчальної вибірки, що належать області, то
де - міра області.
Оцінка буде спроможною при деякому виборі. На жаль, немає універсального способу вибору областей таких, щоб оцінка була заможною.
Методи локального оцінювання
Ідея. оцінити щільність в точці за допомогою елементів навчальної вибірки, що потрапили в деяку околицю.
Нехай - послідовність вибірок незалежних випадкових векторів, - послідовність областей, що містять точку, - число вибіркових значень вибірки, що потрапили в область.
Теорема. Якщо функція неперервна в точці, всі області містять точку і задовольняють умовам
то функція, буде несмещенной, асимптотично ефективною і спроможною оцінкою щільності в точці.
Існують два основні підходи до вибору областей, що містять точку:
- метод парзеновского вікна. передбачаються регулярними областями, розміри яких задовольняють умовам теореми, виходячи з цього визначається число.
- метод k найближчих сусідів. Фіксуються не в ділянці, а число, потім для точки визначається регулярна область, яка містить найближчих до точок.
Метод оцінювання за допомогою апроксимації функції щільності
Ідея. функція апроксимується за допомогою системи базисних функцій - оцінка шукається у вигляді
Коефіцієнти вибираються таким чином, щоб похибка апроксимації була мінімальною, тобто
Реально замість нескінченного ряду (1) розглядається кінцева сума перших членів.
Як правило, розглядають ортогональную систему базисних функцій, при цьому використовують многочлени Лежандра, Чебишева, Ерміта, Лагранжа, Лагерра і т.п.
Параметричне відновлення щільності
Якщо загальний вигляд функції щільності розподілу випадкового вектора ξ відомий в тому сенсі, що точний вид функції повністю залежать від параметрів, які можна оцінити за навчальною вибіркою, то застосовують параметричні методи оцінювання щільності.
Відомий загальний вигляд функції щільності розподілу випадкового вектора, що залежить від вектора параметрів. Потрібно за навчальною вибіркою значень вектора отримати оцінку вектора.
Метод максимальної правдоподібності
Ідея. знайти такий вектор параметрів, що
Нехай, а щільність має вигляд багатовимірного нормального розподілу:
Тоді оцінки параметрів і за методом максимальної правдоподібності за вибіркою мають такий вигляд
Ідея. якщо - щільність розподілу випадкового вектора, то моменти -го порядку дорівнюють (вважаємо, що):
Оцінку можна знайти за вибіркою:
Оцінку можна знайти з системи рівнянь:
Якщо при будь якій - неперервна, то - заможна оцінка.
Відновлення сумішей розподілів
Якщо "форма" класів має досить складний вид, не «піддається" опису одним розподілом, то застосовують методи відновлення сумішей распрелении - описують клас декількома розподілами.
Припустимо, що щільність розподілу має вигляд суміші розподілів:
де - щільність розподілу -й компоненти суміші, - її завжди апріорна ймовірність. Функції правдоподібності належать параметричного сімейства розподілів і відрізняються тільки значеннями параметра,.
Відома вибірка - незалежних випадкових спостережень з суміші, відомі число і функція. Потрібно знайти оцінку параметрів.
Ідея. штучно вводиться вектор прихованих змінних, що володіє наступними властивостями:
- він може бути обчислений, якщо відомі значення вектора параметрів;
- пошук максимуму правдоподібності сильно спрощується, якщо відомі значення прихованих змінних.
EM-алгоритм складається з ітераційного повторення двох кроків. На E-кроці обчислюється очікуване значення (expectation) вектора прихованих змінних за поточним наближенню вектора параметрів. На М-кроці вирішується завдання максимізації правдоподібності (maximization) і знаходиться наступне наближення вектора за поточними значеннями векторів і.
Ітерації зупиняються, коли значення функціоналу, де
або прихованих змінних перестають істотно змінюватися. Зручніше контролювати приховані змінні, так як вони мають сенс ймовірностей і приймають значення з відрізка [0, 1].
"Проблеми", що виникають при реалізації EM-алгоритму
- Проблема вибору початкового наближення. Хоча алгоритм EM сходиться при досить загальних припущеннях, швидкість збіжності може істотно залежати від "хорошого" вибору початкового наближення. Збіжність погіршується в тих випадках, коли робиться спроба помістити кілька компонент в один фактичний згусток розподілу, або розмістити компоненту посередині між згустками.
- Проблема вибору числа компонент. До сих пір передбачалося, що число компонент відомо заздалегідь. На практиці це, як правило, не так.
EM-алгоритм з послідовним додаванням компонент дозволяє вирішити обидві ці проблеми. Ідея даного методу полягає в наступному. Маючи деякий набір компонент, можна виділити об'єкти, які найгірше описуються сумішшю - це об'єкти з найменшими значеннями правдоподібності. За цим об'єктам будується ще одна компонента. Потім вона додається в суміш і запускаються EM-ітерації, щоб нова компонента і старі "притерлися один до одного". Так триває до тих пір, поки всі об'єкти не виявляться покриті компонентами.
Були розглянуті три підходи до задачі оцінювання щільності розподілу: непараметрический, параметричний і поділ сумішей. Кожен з них застосовується при певних апріорних знаннях про щільність розподілу. Параметричні методи відновлення використовуються, якщо вид функції розподілу відомий з точністю до набору параметрів, які оцінюються за навчальною вибіркою. Непараметричні методи вже не вимагають знання функції розподілу з точністю до параметрів, а тільки деяких властивостей функції, наприклад, безперервність або гладкість. Якщо ж форма класів має досить "складний" вид, що не піддається опису одним розподілом, то застосовують методи розділення сумішей, коли передбачається, що всередині класу щільність розподілу являє собою суміш декількох розподілів.
Незважаючи на те, що, здавалося б, все підходи мають різні області застосування і використовують різні методи навчання можна виділити і риси подібності між ними. Непараметричні оцінки щільності можна розглядати як граничний окремий випадок суміші розподілів, в якій кожному навчальному об'єкту відповідає рівно одна компонента з апріорної ймовірністю і сферичної щільністю з центром в точці. З іншого боку, параметричний підхід також є крайнім випадком суміші - коли береться тільки одна компонента. Таким чином, всі три підходи відрізняються, в першу чергу, кількістю адитивних компонент в моделі розподілу:. Це призводить до якісних відмінностей в методах навчання. Вимоги до форми компонент послаблюються в міру збільшення їх числа. Відновлення суміші з довільного числа компонент k є, по всій видимості, найбільш загальним підходом в байєсівської класифікації.
Див. Також методичні вказівки по використанню Ресурсу MachineLearning.ru в навчальному процесі.