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

Шаблон:Машинне навчання Структурове передбачування, структурове навчання або навчання структурованого ви́ходу (Шаблон:Lang-en) — це узагальнювальний термін для методик керованого машинного навчання, які включають передбачування структурованих об'єктів, а не скалярних дискретних або дійснозначних значень.

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

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

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

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

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

This	Шаблон:Нп
is	VBZ
a	Шаблон:Нп
tagged	JJ
sentence	NN
.	.

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

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

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

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

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

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

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

Зробити передбачення $\hat{y}=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}\{y\in GEN(x)\}(w^T\varphi (x,y))$

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

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

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

Див. також

• Умовне випадкове поле
• Шаблон:Нп
• Шаблон:Нп
• Рекурентна нейронна мережа, зокрема, мережі Елмана (ПРМ, Шаблон:Lang-en)

Література

• Noah Smith, Linguistic Structure Prediction Шаблон:Webarchive, 2011. Шаблон:Ref-en
• Michael Collins, Discriminative Training Methods for Hidden Markov Models Шаблон:Webarchive, 2002. Шаблон:Ref-en

Посилання

• Втілення структурового перцептрону Коллінза Шаблон:Webarchive