Диссертация (1137507), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

Наша задача – найтизначения переменных, которые попадают в эту зону и при которых достигаетсямаксимальное значение целевой функции. Наиболее простой метод решениязадачи, т.н. симплекс-метод1, заключается в переборе всех вершинмногогранника зоны допустимых решений, т.к. доказано, что решение всегданаходится в одной из вершин. В данном случае решение — 2 гектара пшеницыи 6 гектаров кукурузы значение целевой функции — 28000 рублей.Данный пример иллюстрирует задачи, решаемые в рамках парадигмылинейного программирования. Большинство приложений этой парадигмы дляавтоматической обработки языка, однако, опирается на более строгуюформулировку задачи — целочисленное линейное программирование (илипросто целочисленное программирование).1Симплекс-метод - наиболее простой и наглядный способ решения задач ЛП.

Он имеетэкспоненциальную сложность и не подходит для решения задач с большим числом переменных.108В рамках целочисленного программирования для всех переменныхвводится дополнительное ограничение: теперь переменные могут приниматьтолько целые значения. Такое ограничение позволяет, в частности, делатьпеременные бинарными и моделировать логические ограничения в рамкахоптимизируемой системы (т.н. булевское программирование). Введениебулевыхпеременныхпозволяетиспользоватьцелочисленноепрограммирование для задач принятия решений. В некоторых случаях задачацелочисленного программирования может быть сведена к задаче линейногопрограммирования с последующей проверкой решения на целочисленность,однако существуют более совершенные методы, которые используютограничение на тип переменных для того чтобы найти решение быстрее(например, branch-and-bound, см. [Land, Doig, 1960]).II.4.3 Модуль глобальной оптимизацииИтак, мы рассмотрели общие принципы линейного и целочисленноголинейного программирование и можем теперь сформулировать задачуоптимизации,котораясделаетрезультатыработынашейсистемыприемлемыми с формальной точки зрения и в перспективе сможет повыситькачество работы системы.

Напомним, что требование, которому выход нашейсистемы должен удовлетворять, звучит следующим образом: каждаясемантическаярольможетбытьприписанатолькоодномуузлувпредложении. Дополнительно мы хотели бы, чтобы такое приписаниеобеспечивало максимальную "уверенность" системы в предоставленныхответах. Мы будем считать, что уверенность системы при присвоении узлу тогоили иного класса пропорциональна весу этого класса, который в терминахметода опорных векторов определяется как расстояние от точки доразделяющей гиперплоскости. Веса в методе опорных векторов формируются109таким образом, что для опорного вектора вес всегда равен единице или минусединице (в зависимости от того, с какой стороны от разделяющейгиперплоскости он находится). Любая точка, получившая вес больше 1, можетинтерпретироваться как однозначно относящаяся к проверяемому классу, алюбая точка с весом меньше -1 с точки зрения классификатора в этот класс невключена.

Для точек в весом в интервале (-1,1) классификатор не можетпредложить уверенного решения, однако знак в любом случае свидетельствуето принадлежности точки к тому или иному классу.Для того чтобы нашу задачу можно было решить с помощьюцелочисленного линейного программирования, необходимо сформулироватьеё в соответствующих терминах.Пусть у нас имеется набор ролей {1 , 2 , 3 … } и набор узлов{1 , 2 , 3 … } . Одна из ролей является "пустой" ролью и обозначаетотсутствие семантической роли на выбранном узле. Эта роль имеет особыйстатус, т.к., в отличие от других ролей, может быть заполнена неограниченноечисло раз. Обозначим её как ∅ . Введём набор переменных-индикаторов ,которые обозначают, что роль приписана узлу , и набор переменных , вкоторых хранится вес роли для узла , определённый классификатором наоснове свойств, выделенных для данного узла.

Следующий примериллюстрирует семантику переменной :Иван купил яблоко1 (Покупатель)2 (Товар)∅1 (Иван)11 = 0.821 = 0.2∅1 = 0.12 (Яблоко)12 = 0.422 = 0.7∅2 = 0.2Таблица 4: Распределение весов в задаче ЛП110Задача оптимизации состоит в следующем. Необходимо выбратьзначения переменных таким образом, чтобы максимизировать функциюуверенности ∑, .Приэтомсуществуетдвапринципиальныхограничения, которые должны быть соблюдены.

Во-первых, одному узлуможет быть приписана только одна роль. Для каждого узла необходимообеспечить ∀: ∑ = 1 . За счёт того, что переменные целые и принимаютзначения {0,1} , это условие может быть верно только когда узел имеетединственную роль. Во-вторых, каждая роль, за исключением "пустой" роли,может быть приписана только один раз. Это условия выражается в терминахнаших переменных следующим образом: ∀ ≠ ∅: ∑ ≤ 1.Обратим внимание на тот факт, что мы не требуем, чтобы каждая рольбыла выражена, а лишь настаиваем, чтобы каждая роль, если она выражена,была присвоена только один раз. Мы допускаем, что данное условие можетбыть сформулировано более гибко, т.к. некоторые роли имеют большуювероятность быть выраженными, чем другие.

Если какая-то роль в обучающихданных почти всегда выражается, то можно было бы дополнительно повыситьвероятность того, что она будет выявлена и на этапе примененияклассификатора. Тем не менее, с учётом того, что в русском языке частовстречается явление эллипсиса, а также с учётом неточностей в нашихтренировочных и тестовых данных, мы считаем выбранную формулировкунаиболее устойчивой к отклонениям.Сформулированная таким образом задача оптимизации передаётся вмодуль линейного программирования, который решает её с помощьюсимплексного метода.

Ниже мы приводим пример полной формулировкизадачи для предложения из Таблица 4:111Максимизировать:11 11 + 12 12 + 21 21 + 22 22 + ∅1 ∅1 + ∅2 ∅2С учётом ограничений:“каждый узел получает одну роль”11 + 21 + ∅1 = 112 + 22 + ∅2 = 1“каждая роль заполняется максимум один раз”11 + 12 ≤ 121 + 22 ≤ 1112II.5 Особенности имплементация системыВ предудущих разделах мы описали механизм работы нашей системы.Прежде чем перейти к анализу результатов, кратко остановимся на деталяхтехнической реализации системы. Кроме того, что такая информациянеобходима для воспроизведения полученных результатов, она также можетбыть полезна при создании альтернативных систем, основанных на тех жекомпонентах. Наконец, необходимо помнить, что в целом результат работысистемы – это продукт взаимодействия нескольких многих факторов , а именно инструкций, в соответствии с которыми разметчики аннотироваликорпус FrameBank токенизатора, использованного при подготовке материалов дляразметки морфологического анализатора синтаксического анализатора качества и исходного материала кластеризации непосредственно нашей системыПоскольку наша система находится в самом конце этой цепочки,результат её работы аккумулирует результаты, полученные на предыдущихэтапах.

В случае, когда разметка по семантическим ролям производится наоснове синтаксическго корпуса, оказывается возможным оценить работусистемы SRL изолированно, т.е. исходя из того, что автоматический анализ напредыдущихэтапахбылвыполненправильно.Посколькувнашемраспоряжении нет синтаксически аннотированного корпуса с разметкой посемантическим ролям, мы можем лишь оценить общее качество работысистемы. Несмотря на то что такой подход хуже подходит для описаниянепосредственно работы системы,он, тем не менее, даёт лучшее113представление о результатах её работы в реальных условиях, когда данныеперед поступлением в систему обрабатываются автоматически.Ниже мы приводим технические детали предложенной системыавтоматической разметки актантов. Напомним, что общая архитектура системывыглядит следующим образом:Рисунок 35: Архитектура системыИсходные данные из корпуса FrameBank в формате xml проходятфильтрацию, после чего поступают в модуль предобработки.

Фильтрациявыполняется с помощью набора правил на языке python. В качестве модуляпредобработки мы используем набор инструментов, созданный С. Шаровым иЙ. Нивре [Sharoff, Nivre, 2011] и включающий в себя токенизатор,морфологический анализатор, лемматизатор и синтаксический парсер.114Поскольку исходная разметка корпуса FrameBank была выполнена науровне токенов, т.е. отдельных слов, мы сохраняем разбиение на слова ипредложения из исходного корпуса, чтобы оставить за собой возможностьобогатить автоматические данные разметкой по семантическим ролям послезавершения предварительной обработки. Тексты, разбитые на слова ипредложения, передаются в модуль морфологического анализа на основеTreeTagger, который использует набор тегов MSD [Sharoff и др., 2008],разработанный для представления морфолгической информации для языков сбогатой морфологией.

TreeTagger был предложен в работе [Schmid, 1994] иявляется одним из наиболее популярных на сегодняшний день инструментовдля морфологического анализа на основе машинного обучения. Анализатороснованнадеревьяхпринятиярешенийиимплицитноснимаетморфологическую неоднозначность, т.к. каждый лист дерева содержит толькоодну морфологическую метку. В TreeTagger используются тесты на полноелексическое совпадение (lex=дом) и тест на совпадение суффикса (suffix=ость).

Характеристики

Список файлов диссертации