Ограниченная условная модель

Условная модель с ограничениями (CCM) — это платформа машинного обучения и вывода, которая дополняет обучение условным (вероятностным или дискриминативным) моделям декларативными ограничениями. Ограничение можно использовать как способ включения выразительных ^{[ нужны разъяснения ]} предварительные знания в модель и смещение заданий, сделанных изученной моделью, для удовлетворения этих ограничений. Эту структуру можно использовать для поддержки решений в выразительном пространстве вывода, сохраняя при этом модульность и гибкость обучения и вывода.

Подобные модели в последнее время ^{[ когда? ]} привлек много внимания ^{[ нужна ссылка ]} в сообществе специалистов по обработке естественного языка ( НЛП ).Формулирование задач в виде задач оптимизации с ограничениями по сравнению с результатами изученных моделей имеет несколько преимуществ. Это позволяет сосредоточиться на моделировании проблем, предоставляя возможность включить знания, специфичные для предметной области, в качестве глобальных ограничений с использованием языка первого порядка. Использование этой декларативной структуры освобождает разработчика от низкоуровневой разработки функций, одновременно фиксируя свойства проблемы, специфичные для предметной области, и гарантируя точный вывод. С точки зрения машинного обучения это позволяет отделить этап генерации модели (обучения) от этапа условного вывода, тем самым помогая упростить этап обучения и одновременно улучшить качество решений. Например, в случае генерации сжатых предложений вместо того, чтобы просто полагаться на языковую модель для сохранения наиболее часто используемых n-грамм в предложении, можно использовать ограничения, гарантирующие, что если модификатор сохраняется в сжатом предложении, его Тема также будет сохранена.

Мотивация

Принятие решений во многих областях (таких как обработка естественного языка и проблемы компьютерного зрения) часто включает присвоение значений наборам взаимозависимых переменных, где выразительная структура зависимостей может влиять или даже диктовать, какие назначения возможны. Эти настройки применимы не только к задачам структурированного обучения, таким как разметка семантических ролей, но также и для случаев, когда требуется использование нескольких предварительно изученных компонентов, таких как обобщение, текстовое сопровождение и ответы на вопросы. Во всех этих случаях естественно сформулировать проблему принятия решения как задачу оптимизации с ограничениями, с целевой функцией, состоящей из изученных моделей, с учетом ограничений, специфичных для предметной области или проблемы.

Условные модели с ограничениями образуют структуру обучения и вывода, которая дополняет обучение условных (вероятностных или дискриминативных) моделей декларативными ограничениями (написанными, например, с использованием представления первого порядка) как способ поддержки решений в выразительном пространстве вывода при сохранении модульность и управляемость обучения и вывода. Эти ограничения могут выражать либо жесткие ограничения, полностью запрещающие некоторые задания, либо мягкие ограничения, наказывающие маловероятные задания. В большинстве применений этой структуры в НЛП следующее: ^[1] В качестве основы вывода использовалось целочисленное линейное программирование (ILP), хотя для этой цели можно использовать и другие алгоритмы.

Формальное определение

Учитывая набор функций функции $\{\phi _{i}(x,y)\}$ и набор ограничений $\{C_{i}(x,y)\}$ , определенный во входной структуре $x\in X$ и структура вывода $y\in Y$ , условная модель ограничений характеризуется двумя весовыми векторами, w и $\rho$ , и определяется как решение следующей задачи оптимизации:

argmax_{y}\sum _{i}w_{i}\phi _{i}(x,y)-\sum \rho _{i}C_{i}(x,y)

.

Каждое ограничение $C_{i}\in C$ — это логическое отображение, указывающее, выполнено ли совместное присвоение $(x,y)$ нарушает ограничение и $\rho$ — штраф, налагаемый за нарушение ограничений. Ограничения, которым назначен бесконечный штраф, известны как жесткие ограничения и представляют собой невыполнимые назначения для задачи оптимизации.

Парадигмы обучения

Изучение локальных и глобальных моделей

Целевую функцию, используемую CCM, можно разложить и изучить несколькими способами: от полного совместного обучения модели вместе с ограничениями до полного разделения этапа обучения и вывода. В последнем случае несколько локальных моделей изучаются независимо, и зависимость между этими моделями учитывается только во время принятия решения посредством глобального процесса принятия решений. Преимущества каждого подхода обсуждаются в ^[2] который изучает две парадигмы обучения: (1) локальные модели: L+I (обучение + вывод) и (2) глобальную модель: IBT (обучение, основанное на выводах), и показывает как теоретически, так и экспериментально, что IBT (совместное обучение) является лучшим В пределе, при некоторых условиях (в основном, «хороших» компонентах) L+I может обобщать лучше.

Способность CCM комбинировать локальные модели особенно полезна в тех случаях, когда совместное обучение вычислительно сложно или когда данные обучения недоступны для совместного обучения. Эта гибкость отличает CCM от других сред обучения, которые также сочетают статистическую информацию с декларативными ограничениями, таких как логическая сеть Маркова , которая делает упор на совместное обучение.

Минимально контролируемый СКК

CCM может помочь уменьшить контроль, используя знания предметной области (выраженные в виде ограничений) для стимулирования обучения. Эти настройки были изучены в ^[3] и. ^[4] Эти работы представляют полуконтролируемое обучение, основанное на ограничениях.(CODL) и показывают, что за счет включения знаний предметной области производительность изученной модели значительно улучшается.

Обучение скрытым представлениям

CCM также применялись к структурам скрытого обучения, где проблема обучения определяется на уровне скрытого представления. Поскольку понятие правильного представления по своей сути нечетко определено, учащемуся не доступны никакие помеченные золотым стандартом данные, касающиеся решения о представлении. Определение правильного (или оптимального) представления обучения рассматривается как процесс структурированного прогнозирования и, следовательно, моделируется как CCM. Эта проблема была освещена в нескольких статьях, как под руководством ^[5] и без присмотра ^[6] настройки. Во всех случаях исследования показали, что явное моделирование взаимозависимостей между решениями о представлении с помощью ограничений приводит к повышению производительности.

Целочисленное линейное программирование для приложений обработки естественного языка

Преимущества декларативной формулировки CCM и доступность готовых решателей привели к тому, что обработки естественного языка в рамках этой структуры формулируется большое разнообразие задач , включая маркировку семантических ролей , ^[7] синтаксический разбор, ^[8] разрешение кореферентности , ^[9] обобщение, ^[10]^[11]^[12] транслитерация , ^[13] генерация естественного языка ^[14] и совместное извлечение информации. ^[15]^[16]

В большинстве этих работ для решения проблемы принятия решения используется решатель целочисленного линейного программирования (ILP). Хотя теоретически решение целочисленной линейной программы экспоненциально зависит от размера проблемы решения, на практике используются современные решатели и приближенного вывода. методы ^[17] крупномасштабные проблемы могут быть решены эффективно.

Ключевым преимуществом использования решателя ILP для решения задачи оптимизации, определенной условной моделью с ограничениями, является декларативная формулировка, используемая в качестве входных данных для решателя ILP, состоящая из линейной целевой функции и набора линейных ограничений.

Ресурсы

Учебное пособие по CCM. Структуры прогнозирования в НЛП: условные модели с ограничениями и целочисленное линейное программирование в НЛП.

Внешние ссылки

Ссылки

^ Дэн Рот и Вен-тау Йих, «Формулировка линейного программирования для глобального вывода в задачах на естественном языке». Архивировано 25 октября 2017 г. в Wayback Machine CoNLL (2004 г.).
^ Васин Пуньяканок, Дэн Рот, Вен-Тау Йих и Дав Зимак, «Обучение и выводы вместо ограниченного вывода». Архивировано 25 октября 2017 г. в Wayback Machine IJCAI (2005 г.).
^ Минг-Вэй Чанг, Лев Ратинов и Дэн Рот, «Руководство по полуконтролю с помощью обучения, основанного на ограничениях». Архивировано 3 марта 2016 г. в Wayback Machine ACL (2007 г.).
^ Минг-Вэй Чанг, Лев Ратинов и Дэн Рот, «Ограничения как предварительное знание». Архивировано 3 марта 2016 г. на семинаре ICML Wayback Machine по предварительным знаниям в области обработки текста и языка (2008 г.).
^ Минг-Вэй Чанг, Дэн Голдвассер, Дэн Рот и Вивек Срикумар, «Дискриминационное обучение по сравнению с ограниченными скрытыми представлениями». Архивировано 25 октября 2017 г. в Wayback Machine NAACL (2010).
^ Минг-Вэй Чанг Дэн Голдвассер Дэн Рот и Юанчэн Ту, «Обучение, основанное на ограничениях без присмотра, для открытия транслитерации». ^{[ постоянная мертвая ссылка ]} НААКЛ, (2009).
^ Васин Пуньяканок, Дэн Рот, Вен-тау Йих и Дав Зимак, «Разметка семантических ролей посредством вывода целочисленного линейного программирования». Архивировано 9 августа 2017 г. в Wayback Machine COLING (2004 г.).
^ Кенджи Сагае, Юсуке Мияо и Дзюнъити Цудзи, «Разбор HPSG с неглубокими ограничениями зависимостей». АКЛ (2007).
^ Паскаль Дени и Джейсон Болдридж, «Совместное определение анафоричности и разрешения кореференции с использованием целочисленного программирования». Архивировано 21 июня 2010 г. в Wayback Machine NAACL-HLT (2007).
^ Джеймс Кларк и Мирелла Лапата, «Глобальный вывод для сжатия предложений: подход к целочисленному линейному программированию». Архивировано 10 мая 2013 г. в журнале исследований искусственного интеллекта Wayback Machine (JAIR) (2008).
^ Катя Филиппова и Майкл Штрубе, «Сжатие предложений на основе дерева зависимостей». ^{[ постоянная мертвая ссылка ]} ИНЛГ , (2008).
^ Катя Филиппова и Майкл Штрубе, «Слияние предложений посредством сжатия графа зависимостей». ЭМНЛП , (2008).
^ Дэн Голдвассер и Дэн Рот, «Транслитерация как ограниченная оптимизация». Архивировано 11 августа 2017 г. в Wayback Machine EMNLP (2008).
^ Регина Барзилай и Миррела Лапата, «Агрегация посредством разделения множеств для генерации естественного языка». НААКЛ , (2006).
^ Дэн Рот и Вен-тау Йих, «Формулировка линейного программирования для глобального вывода в задачах на естественном языке». Архивировано 25 октября 2017 г. в Wayback Machine CoNLL (2004 г.).
^ Еджин Чой , Эрик Брек и Клэр Карди, «Совместное извлечение сущностей и отношений для распознавания мнений». ЭМНЛП , (2006).
^ Андре Ф.Т. Мартинс, Ной А. Смит и Эрик П. Син, «Краткие формулировки целочисленного линейного программирования для анализа зависимостей». АКЛ (2009).

[1] Дэн Рот и Вен-тау Йих, «Формулировка линейного программирования для глобального вывода в задачах на естественном языке». Архивировано 25 октября 2017 г. в Wayback Machine CoNLL (2004 г.).

[2] Васин Пуньяканок, Дэн Рот, Вен-Тау Йих и Дав Зимак, «Обучение и выводы вместо ограниченного вывода». Архивировано 25 октября 2017 г. в Wayback Machine IJCAI (2005 г.).

[3] Минг-Вэй Чанг, Лев Ратинов и Дэн Рот, «Руководство по полуконтролю с помощью обучения, основанного на ограничениях». Архивировано 3 марта 2016 г. в Wayback Machine ACL (2007 г.).

[4] Минг-Вэй Чанг, Лев Ратинов и Дэн Рот, «Ограничения как предварительное знание». Архивировано 3 марта 2016 г. на семинаре ICML Wayback Machine по предварительным знаниям в области обработки текста и языка (2008 г.).

[5] Минг-Вэй Чанг, Дэн Голдвассер, Дэн Рот и Вивек Срикумар, «Дискриминационное обучение по сравнению с ограниченными скрытыми представлениями». Архивировано 25 октября 2017 г. в Wayback Machine NAACL (2010).

[6] Минг-Вэй Чанг Дэн Голдвассер Дэн Рот и Юанчэн Ту, «Обучение, основанное на ограничениях без присмотра, для открытия транслитерации». ^{[ постоянная мертвая ссылка ]} НААКЛ, (2009).

[7] Васин Пуньяканок, Дэн Рот, Вен-тау Йих и Дав Зимак, «Разметка семантических ролей посредством вывода целочисленного линейного программирования». Архивировано 9 августа 2017 г. в Wayback Machine COLING (2004 г.).

[8] Кенджи Сагае, Юсуке Мияо и Дзюнъити Цудзи, «Разбор HPSG с неглубокими ограничениями зависимостей». АКЛ (2007).

[9] Паскаль Дени и Джейсон Болдридж, «Совместное определение анафоричности и разрешения кореференции с использованием целочисленного программирования». Архивировано 21 июня 2010 г. в Wayback Machine NAACL-HLT (2007).

[10] Джеймс Кларк и Мирелла Лапата, «Глобальный вывод для сжатия предложений: подход к целочисленному линейному программированию». Архивировано 10 мая 2013 г. в журнале исследований искусственного интеллекта Wayback Machine (JAIR) (2008).

[11] Катя Филиппова и Майкл Штрубе, «Сжатие предложений на основе дерева зависимостей». ^{[ постоянная мертвая ссылка ]} ИНЛГ , (2008).

[12] Катя Филиппова и Майкл Штрубе, «Слияние предложений посредством сжатия графа зависимостей». ЭМНЛП , (2008).

[13] Дэн Голдвассер и Дэн Рот, «Транслитерация как ограниченная оптимизация». Архивировано 11 августа 2017 г. в Wayback Machine EMNLP (2008).

[14] Регина Барзилай и Миррела Лапата, «Агрегация посредством разделения множеств для генерации естественного языка». НААКЛ , (2006).

[15] Дэн Рот и Вен-тау Йих, «Формулировка линейного программирования для глобального вывода в задачах на естественном языке». Архивировано 25 октября 2017 г. в Wayback Machine CoNLL (2004 г.).

[16] Еджин Чой , Эрик Брек и Клэр Карди, «Совместное извлечение сущностей и отношений для распознавания мнений». ЭМНЛП , (2006).

[17] Андре Ф.Т. Мартинс, Ной А. Смит и Эрик П. Син, «Краткие формулировки целочисленного линейного программирования для анализа зависимостей». АКЛ (2009).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]