Бутстрепова агрегація

Бутстрепова агрегація або беггінг^[1] (англ. Bootstrap aggregating, bagging) — це машинний навчальний груповий мета-алгоритм, створений для покращення стабільності і точності машинних навчальних алгоритмів, які використовують статистичні класифікації і регресії. Він також зменшує неточність, хоча зазвичай застосовується до методів «дерева рішень», але може використовуватися з будь-яким типом методів.

Метод схожий на ансамбль методів однак, замість використання декількох моделей на одних і тих самих даних, кожна модель застосовується до різних вибірок отриманих методом бутстреп. ^[2]

Опис методу

Наприклад, дано стандартний навчальний набір D розміром n. Даний мета-алгоритм сукупності створює нові навчальні зразки ${\displaystyle D_{i}}$, відбираючи однорідно або із заміною зразки з набору D , кожен з яких розміром nʹ. Деякі спостереження можуть повторюватися в кожному ${\displaystyle D_{i}}$. Якщо n′=n, тоді для великого n набір ${\displaystyle D_{i}}$ очікувано матиме дріб (1 — 1/e) (≈63.2 %) єдиних прикладів D, а всі інші будуть дублюватися. Такий вид відбору відомий як бутстреп відбір.

Сумування приводить до «покращення нестійких процедур» (Брейман, 1996), які включають, наприклад, штучні нервові системи, класифікаційні і регресивні дерева та відбір підгрупи в лінійній регресії (Брейман, 1996). Цікаве застосування алгоритму показано тут.^[3][4] Алгоритм трішки понижує значення стійких методів таких як К-найближчі сусіди (Брейман, 1996).

Приклад: Озон

Щоб проілюструвати основні принципи бутстрепу, нижче показано аналіз відношення між озоном і температурою (дані з Rousseeuw and Leroy (1986), доступно в класичних наборах даних, аналіз робиться в R (мова програмування).

Взаємозв'язок між озоном і температурою в цьому прикладі є очевидно нелінійним, що видно на розсіяному графіку. Щоб описати математично це відношення застосовують LOESS рівні частинки. Замість того, щоб побудувати одну точку з повним набором даних, зразу намалювали 100 зразків за аналогією. Кожен зразок відрізняється від початкового набору даних, але він схожий за розподілом і мінливістю. Прогноз був зроблений на основі 100 груп. Перші 10 прогнозованих зразків є сірими лініями на графіку, які є дуже гнучкими.

Беручи середнє число із 100 зразків, кожний з них встановлює підгрупу початкових даних, ми підходимо до одного сукупного прогнозованого — це червона лінія на графіку:

Сукупність найближчих сусідніх класифікаторів

Похибка одного найближчого сусіднього класифікатора є вдвічі більшою за похибку баєсового класифікатора.^[5] За допомогою уважного вибору розміру зразків сукупність сумування цих зразків може привести до помітного покращення 1NN класифікатора. Беручи велику кількість зразків розміром ${\displaystyle n'}$, супутній найближчий класифікатор буде послідовним, забезпечуючи ${\displaystyle n'\to \infty }$ та відходячи від норми, але ${\displaystyle n'/n\to 0}$ як відібраний розмір ${\displaystyle n\to \infty }$.

Під безконечною симуляцією сукупний найближчий сусідній класифікатор може розглядатися як масовий найближчий сусідній класифікатор. Допускаємо, що характерний простір є ${\displaystyle d}$ вимірним і позначається ${\displaystyle C_{n,n'}^{bnn}}$, сукупний найближчий класифікатор базується на навчальному наборі розміром ${\displaystyle n}$ та зі зразком розміром ${\displaystyle n'}$. У безконечному відборі зразків за певних регулярних умов на групових розподілах крайня похибка має наступну формулу^[6]

${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n,n'}^{bnn})-{\mathcal {R}}_{\mathcal {R}}(C^{Bayes})=\left(B_{1}{\frac {n'}{n}}+B_{2}{\frac {1}{(n')^{4/d}}}\right)\{1+o(1)\},}$

для деяких констант ${\displaystyle B_{1}}$ and ${\displaystyle B_{2}}$. Оптимальний вибір nʹ, що збалансовує два терміни, є у формулі ${\displaystyle n'=Bn^{d/(d+4)}}$ для деякої константи ${\displaystyle B}$.

Історія

Бутстрепову агрегацію запропонував 1944 року Лео Брейман для покращення класифікації випадково утворених наборів даних. See Breiman, 1994. Technical Report No. 421.

Див. також

• Підсилювання (машинне навчання)
• Статистичний бутстреп
• Перехресне затверджування
• Random forest
• Random subspace method (attribute bagging)

Примітки

1. Вербівський Д. С., Карплюк С. О., Фонарюк О. В., Сікора Я. Б. Бустінг і беггінг як методи формування ансамблей моделей // Actual trends of modern scientific research. Abstracts of the 7th International scientific and practical conference.. — Житомирський державний університет імені Івана Франка, . — С. 163-169.
2. Practical Statistics for Data Scientists [Book]. www.oreilly.com (англ.). Архів оригіналу за 21 травня 2021. Процитовано 21 травня 2021.
3. Sahu, A., Runger, G., Apley, D., Image denoising with a multi-phase kernel principal component approach and an ensemble version, IEEE Applied Imagery Pattern Recognition Workshop, pp.1-7, 2011.
4. Shinde, Amit, Anshuman Sahu, Daniel Apley, and George Runger. «Preimages for Variation Patterns from Kernel PCA and Bagging.» IIE Transactions, Vol.46, Iss.5, 2014
5. Castelli, Vittorio. Nearest Neighbor Classifiers, p.5 (PDF). columbia.edu. Columbia University. Архів оригіналу (PDF) за 5 вересня 2015. Процитовано 25 квітня 2015.
6. Samworth R. J. (2012). Optimal weighted nearest neighbour classifiers. Annals of Statistics. 40 (5): 2733—2763. doi:10.1214/12-AOS1049.

Посилання

• Breiman, Leo (1996). Bagging predictors. Machine Learning. 24 (2): 123—140. doi:10.1007/BF00058655. CiteSeerX: 10.1.1.121.7654.

• Alfaro, E., Gámez, M. and García, N. (2012). adabag: An R package for classification with AdaBoost.M1, AdaBoost-SAMME and Bagging.