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

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

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

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

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

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

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

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

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

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

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

Одним із найлегших способів зрозуміти алгоритми для загального структурового передбачування є структуровий перцептрон ^[en]. Цей алгоритм поєднує алгоритм перцептрону для навчання лінійних класифікаторів з алгоритмом висновування (класично при застосуванні на послідовнісних даних — алгоритм Вітербі), і його може бути абстрактно описано наступним чином. Спершу визначмо «спільну функцію ознак» Φ(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})}$ здійснюватиметься із застосуванням такого алгоритму, як Вітербі, або такого алгоритму, як ^[en], замість вичерпного пошуку експоненційно великим набором кандидатів.

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

Див. також

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

Примітки

1. Gökhan BakIr, Ben Taskar, Thomas Hofmann, Bernhard Schölkopf, Alex Smola and SVN Vishwanathan (2007), Predicting Structured Data [ 15 липня 2018 у Wayback Machine.], MIT Press. (англ.)
2. Lafferty, J., McCallum, A., Pereira, F. (2001). (PDF). Proc. 18th International Conf. on Machine Learning. с. 282—289. Архів оригіналу (PDF) за 7 червня 2013. Процитовано 15 липня 2018. (англ.)
3. Collins, Michael (2002). (PDF). Proc. EMNLP. Т. 10. Архів оригіналу (PDF) за 8 грудня 2006. Процитовано 15 липня 2018. (англ.)

Література

• 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.]