Структурове передбачування, структурове навчання або навчання структурованого ви́ходу (англ.structured prediction, structured (output) learning) — це узагальнювальний термін для методик керованого машинного навчання, які включають передбачування структурованих об'єктів, а не скалярних дискретних або дійснозначних значень.[1]
Наприклад, задачу переведення речення природною мовою до синтаксичного представлення, такого як дерево розбору, можливо розглядати як задачу[en] структурового передбачування,[2] в якій область значень структурового виходу є множиною всіх можливих синтаксичних дерев.
Подібно до широко застосовуваних методик керованого навчання, моделі структурового передбачування зазвичай тренують за допомогою спостережених даних, в яких істинне значення передбачення використовують для налаштовування параметрів моделі. Через складність моделі та взаємопов'язаність передбачуваних змінних, процес передбачування із застосуванням натренованої моделі, та власне тренування, часто є обчислювально нездійсненним, і застосовують методи наближеного висновування[en] та навчання.
Приклад: розмічування послідовностей
Розмічування послідовностей — це клас задач, що превалюють в обробці природної мови, де входові дані часто є послідовностями (наприклад, послідовностями тексту). Задача розмічування послідовностей з'являється під кількома личинами, такими як розмічування частин мови та розпізнавання іменованих сутностей. В розмічуванні частин мови, наприклад, кожне слово в послідовності мусить отримати «мітку» (класу), яка виражає свій «тип» слова:
Головним викликом в цій задачі є розв'язування багатозначностей: слово «sentence» в англійській мові може також бути дієсловом, і бути розміченим відповідно.
І хоч цю задачу й можливо розв'язувати просто виконанням класифікації окремих лексем, такий підхід не враховує того емпіричного факту, що лексеми не трапляються незалежно; натомість, кожна мітка демонструє сильну умовну залежність[en] від мітки попереднього слова. Цей факт може бути використано в послідовнісній моделі, такій як прихована марковська модель або умовне випадкове поле,[2] що передбачує всю послідовність для речення, замість передбачування лише окремих міток, засобами алгоритму Вітербі.
Структуровий перцептрон
Одним із найлегших способів зрозуміти алгоритми для загального структурового передбачування є структуровий перцептрон Коллінза[en].[3] Цей алгоритм поєднує алгоритм перцептрону для навчання лінійних класифікаторів з алгоритмом висновування (класично при застосуванні на послідовнісних даних — алгоритм Вітербі), і його може бути абстрактно описано
наступним чином. Спершу визначмо «спільну функцію ознак» Φ(x, y), що відображує тренувальний зразок x та кандидатуру передбачення y на вектор довжини n (x та y можуть мати будь-яку структуру; n залежить від задачі, але його мусить бути зафіксовано для кожної моделі). Нехай GEN — це функція, що породжує кандидатури передбачень. Тоді:
Нехай є ваговим вектором довжини n
Для визначеного наперед числа ітерацій:
Для кожного зразка в тренувальному наборі, зі справжнім виходом :
Зробити передбачення
Уточнити , з до : , є темпом навчання
На практиці знаходження argmax над здійснюватиметься із застосуванням такого алгоритму, як Вітербі, або такого алгоритму, як max-sum[en], замість вичерпного пошуку експоненційно великим набором кандидатів.
