Структурове передбачування

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних АвтоМН Асоціативні правила Семантичний аналіз Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик Навчання онтологій Мультимодальне навчання
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання AdaBoost Дерева рішень MARS CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього
Знижування розмірності Факторний аналіз Метод незалежних компонент Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс
Штучна нейронна мережа Автокодувальник Когнітивні обчислення Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа Мемтранзистор Електрохімічна ПДД (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе
Навчання з людьми Активне навчання (машинне навчання) Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання Регуляризація LASSO Тихонова Еластично-сіткова Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання
Місця машинного навчання ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання

Структурове передбачування, структурове навчання або навчання структурованого ви́ходу (англ. structured prediction, structured (output) learning) — це узагальнювальний термін для методик керованого машинного навчання, які включають передбачування структурованих об'єктів, а не скалярних дискретних або дійснозначних значень.

Наприклад, задачу переведення речення природною мовою до синтаксичного представлення, такого як дерево розбору, можливо розглядати як задачу структурового передбачування, в якій область значень структурового виходу є множиною всіх можливих синтаксичних дерев.

Великий клас структурових передбачувальних моделей утворюють імовірнісні графові моделі. Зокрема, для розв'язування задач структурового передбачування в широкому спектрі застосувань, включно з біоінформатикою, обробкою природної мови, розпізнаванням мовлення та комп'ютерним баченням, популярним є застосування баєсових мереж та випадкових полів. До інших алгоритмів та моделей для структурового передбачування належать індуктивне логічне програмування, міркування на основі прецедентів, структурові ОВМ, марковські логічні мережі та обмежені умовні моделі.

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

Приклад: розмічування послідовностей

Розмічування послідовностей — це клас задач, що превалюють в обробці природної мови, де входові дані часто є послідовностями (наприклад, послідовностями тексту). Задача розмічування послідовностей з'являється під кількома личинами, такими як розмічування частин мови та розпізнавання іменованих сутностей. В розмічуванні частин мови, наприклад, кожне слово в послідовності мусить отримати «мітку» (класу), яка виражає свій «тип» слова:

This	DT
is	VBZ
a	DT
tagged	JJ
sentence	NN
.	.

Головним викликом в цій задачі є розв'язування багатозначностей: слово «sentence» в англійській мові може також бути дієсловом, і бути розміченим відповідно.

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

Структуровий перцептрон

Одним із найлегших способів зрозуміти алгоритми для загального структурового передбачування є структуровий перцептрон Коллінза. Цей алгоритм поєднує алгоритм перцептрону для навчання лінійних класифікаторів з алгоритмом висновування (класично при застосуванні на послідовнісних даних — алгоритм Вітербі), і його може бути абстрактно описано наступним чином. Спершу визначмо «спільну функцію ознак» Φ(x, y), що відображує тренувальний зразок x та кандидатуру передбачення y на вектор довжини n (x та y можуть мати будь-яку структуру; n залежить від задачі, але його мусить бути зафіксовано для кожної моделі). Нехай GEN — це функція, що породжує кандидатури передбачень. Тоді:

Нехай $w$ є ваговим вектором довжини n

Для визначеного наперед числа ітерацій:

Для кожного зразка $x$ в тренувальному наборі, зі справжнім виходом $t$:

Зробити передбачення ${\hat {y}}={\operatorname {arg\,max} }\,\{{y}\in {GEN}({x})\}\,({w}^{T}\,\phi ({x},{y}))$

Уточнити $w$, з ${\hat {y}}$ до $t$: ${w}={w}+{c}(-\phi ({x},{\hat {y}})+\phi ({x},{t}))$, $c$ є темпом навчання

На практиці знаходження argmax над ${GEN}({x})$ здійснюватиметься із застосуванням такого алгоритму, як Вітербі, або такого алгоритму, як max-sum, замість вичерпного пошуку експоненційно великим набором кандидатів.

Ідея навчання є подібною до багатокласового перцептрону.

Див. також

• Умовне випадкове поле
• Структурова опорно-векторна машина
• Структурові k-найближчі сусіди
• Рекурентна нейронна мережа, зокрема, мережі Елмана (ПРМ, англ. SRN)

Література

• Noah Smith, Linguistic Structure Prediction [Архівовано 27 липня 2018 у Wayback Machine.], 2011. (англ.)
• Michael Collins, Discriminative Training Methods for Hidden Markov Models [Архівовано 24 червня 2018 у Wayback Machine.], 2002. (англ.)

Посилання

• Втілення структурового перцептрону Коллінза [Архівовано 11 червня 2018 у Wayback Machine.]