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

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

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

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

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

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

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

This	DT[en]
is	VBZ
a	DT[en]
tagged	JJ
sentence	NN
.	.

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

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

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

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

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

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

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

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

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

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

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

Див. також

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