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

Структурове передбачування, структурове навчання або навчання структурованого ви́ходу (англ. 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.]