RU2336552C2

RU2336552C2 - Лингвистически информированные статистические модели структуры составляющих для упорядочения в реализации предложений для системы генерирования естественного языка

Info

Publication number: RU2336552C2
Application number: RU2004108775/09A
Authority: RU
Inventors: Эрик РИНГГЕР (US); Эрик РИНГГЕР; Майкл ГЕЙМОН (US); Майкл ГЕЙМОН; Мартин СМЕТС (US); Мартин СМЕТС; Саймон КОРСТОН-ОЛИВЕР (US); Саймон КОРСТОН-ОЛИВЕР; Роберт К. МУР (US); Роберт К. МУР
Original assignee: Майкрософт Корпорейшн
Priority date: 2003-03-25
Filing date: 2004-03-24
Publication date: 2008-10-20
Also published as: MXPA04002816A; EP1462948A1; AU2004201089A1; US20040193401A1; KR101084786B1; CA2461777A1; CA2461777C; AU2004201089B2; DE602004003513T2; CN1542649A; ATE347711T1; BRPI0400778A; DE602004003513D1; RU2004108775A; CN1542649B; EP1462948B1; JP2004295884A; US7346493B2; KR20040084856A

Abstract

Настоящее изобретение относится к компонентам упорядочивания деревьев в системе реализации предложений. Техническим результатом является обеспечение правильного порядка слов в древовидной структуре. Для этого компонент принимает неупорядоченное синтаксическое дерево и генерирует ранжированный список альтернативно упорядоченных синтаксических деревьев из неупорядоченного синтаксического дерева. Компонент также включает в себя статистические модели структуры составляющих, используемые компонентом упорядочивания деревьев для оценивания альтернативно упорядоченных деревьев. 25 з.п. ф-лы, 11 ил.

Description

Предшествующий уровень техники

Настоящее изобретение связано с генерированием естественного языка. Конкретнее настоящее изобретение связано с реализацией предложений в системе генерирования естественного языка.

Система генерирования естественного языка генерирует текст из лингвистического представления предложения. Такие системы обычно включают в себя компонент планировщика текста или выбора содержания, компонент планировщика предложений и компонент реализации предложений.

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

Например, предположим, что планировщик текста обеспечивает слова содержания, такие как "Красная Шапочка", "идет" и "дом бабушки". Планировщик предложений определяет, что "Красная Шапочка" является деятелем, "идет" является действием, а "дом бабушки" - целью. Планировщик предложений обеспечивает это абстрактное лингвистическое представление в качестве входных данных для компонента реализации предложений. Компонент реализации предложений выполняет комплексную задачу по отображению абстрактного лингвистического представления в действительную последовательность слов и знаков препинания, соответствующую этому абстрактному лингвистическому представлению. Действительная последовательность слов и знаков препинания является реализованным предложением (также называемым "поверхностной строкой"), которое выводится системой.

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

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

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

Примером системы этой третьей категории является система Nitrogen, описанная в работе Langkilde, I. and К. Knight, 1998, "The Practical Value of N-Grams in Generation", Proceedings of the 9^th International Workshop on Natural Language Generation, Niagara-on-the-Lake, pp. 248-255; и в работе Langkilde, I. and К. Knight, 1998, "Generation that Exploits Corpus-Based Statistical Knowledge", Proceedings of the 36^th Annual Meeting of the Association for Computational Linguistics and 17^thInternational Conference on Computational Linguistics (COLING-ACL 1998), Montreal, Quebec, Canada, pp. 704-710.

В первой из этих систем вместо глубоких лингвистических знаний для выбора среди альтернативных итоговых предложений используются биграммы слов. Два набора правил, созданных на основе знаний, оперируют входным описанием, чтобы создавать итоговые предложения-кандидаты. Один набор правил выполняет отображения типа "один во множество" из недоопределенной семантики в возможные синтаксические формулировки, конкретизируя информацию, такую как определенность и число, которые могли быть пропущены в практических контекстах генерирования, таких как системы машинного перевода с японского на английский язык. Второй набор правил, которые включают в себя чувствительность к целевой предметной области, преобразует представления, созданные первым модулем, для получения еще большего количества предложений-кандидатов, которые представляются в виде словесной решетки. Морфологическая флексия, выполняемая при помощи простой таблицы соответствий, еще больше расширяет решетку. Биграммы слов используются для поиска оптимального порядка обхода решетки, производя итоговое предложение с наивысшим рангом. Эта система генерирует очень большое количество предложений-кандидатов, подлежащих оцениванию и ранжированию. Например, в одном из примеров, приведенных Langkilde, I. and к. Knight, вводная семантическая форма включает в себя пять лексических узлов, отношения между которыми определяются как ДЕЯТЕЛЬ, ЦЕЛЬ и ОБЪЕКТ. Словесная решетка, которая получается из этого семантического ввода, содержит более 11 миллионов возможных путей, причем наивысший ранг имеет кандидат «Туристы, которые приехали в Японию, восхищаются горой Фудзи». Другой подобный пример (для которого не дается вводного семантического представления), как выясняется, содержит только два слова содержания, которые преобразуются в решетку, содержащую более 155000 путей получения кандидата с наивысшим рангом «Я не могу обмануть их доверие».

Недостатком языковой модели на основе биграмм слов, используемой в этой системе, является неспособность уловить зависимости между несоседними словами. Можно увеличить порядок лингвистической модели до триграмм или даже до более высокого порядка n-грамм, но модели по-прежнему не могут уловить обычные отдаленные зависимости. Более того, разреженность данных является проблемой по мере увеличения порядка.

Мы также отмечаем другую соответствующую предшествующему уровню техники работу, имеющую отношение к частям настоящего описания, которая здесь именуется моделью порядка. Одна релевантная область включает в себя "генеративные"' модели синтаксического анализа. Такие модели используются в процессе синтаксического анализа, чтобы присваивать вероятности альтернативным синтаксическим деревьям. Название "генеративные" показывает, что модель позволяет выполнять случайные выборки при генерировании структуры предложения в соответствии с распределениями в модели. Как и в процессе синтаксического анализа, такая модель может присваивать вероятность возможным составляющим структурам при наличии релевантных признаков в процессе генерирования. Примеры таких моделей синтаксического анализа приведены в нижеследующих публикациях. Eugene Charniak, "A Maximum-Entropy-Inspired Parser"¹, Proceedings of NAACL-2000, Seattle, Washington, pp. 132-139. Также Eugene Charniak, "Immediate-Head Parsing for Language Models'⁷, Proceedings of the 39^th Annual Meeting of the Association for Computational Linguistics (2001), Toulouse, France, pp. 116-123. В исследовании, описанном в этой статье, оценки вероятности составляющих обусловлены контекстной информацией, такой как вершина составляющей. Один аспект моделей порядка в настоящем изобретении, который отделяет исследование, раскрытое здесь, от моделей Чарняка (Charniak) и от существующих моделей генеративного синтаксического анализа, заключается в использовании семантических связей и других признаков, доступных для задания генерации, но не во время синтаксического анализа.

Другой точкой отсчета является исследование синтаксического анализа Давидом Магерманом (David Magerman), который использовал деревья решений, чтобы оценить распределения, представляющие интерес для синтаксического анализа. См. Magerman M. 1995, "Statistical Decision-Tree Models for Parsing", Proceedings of ACL, pp. 276-283. Основные отличия между этим исследованием и настоящим изобретением заключаются в использовании при синтаксическом анализе, а не при генерировании и разнице в признаках, доступных для каждой модели. Более того, модели Магермана не являются генеративными.

Порядок слов и составляющих имеет решающее значение для установления плавности и внятности предложения. Установление порядка на этапе реализации предложения при генерировании естественного языка обычно выполняется по генеративной грамматике, созданной вручную в прошлом. См., например, Aikawa Т. et al., 2001. "Multilingual sentence generation". Proceedings of the 8^th European Workshop on Natural Language Generation, Toulouse, France, pp. 57-63; и Reiter E. et al., 2000, "Building natural language generation systems", Cambridge University Press.

В последнее время исследуются статистические подходы. Система Nitrogen, описанная выше, и система Fergus (см. Bangalore S. and Rambow 0., 2000, "Exploiting a probabilistic hierarchical model for generation". Proceedings of COLING 2000, Saarbrucken, Germany, pp. 42-48) используют словесные n-граммные модели языка, чтобы сделать выбор из обширного набора последовательностей-кандидатов слов, которые могут различаться в порядке составляющих, порядке слов, лексическом наборе и морфологической флексии, в системах Nitrogen и Fergus порядок составляющих моделируется только косвенным образом через словесные п-граммы на поверхностных строках; то есть порядок не изолирован в качестве отдельного явления от выбора соответствующих морфологических вариантов и разрешения недоопределенных входных данных. Также они не используют важные лингвистические признаки, доступные во время реализации.

Система Halogen (см. Langkilde, I., 2000, "Forest-Based Statistical Sentence generation". Proceedings of NAACL 200, pp. 170-177; и Langkilde-Geary I., 2002, "An Empirical Verification of Coverage and Correctness for a General-Purpose Sentence Generator", Proceedings of the International Language Generation Conference 2002, New-York, pp. 17-24), как и система Nitrogen, использует словесную n-граммную модель, но она эффективно выделяет наилучшие реализации поверхностей из совокупности деревьев (а не из решетки) путем ограничения поиска сначала пределами каждой составляющей.

Система Amalgam (см. Corston-Oliver et al., 2002, "An overview of Amalgam: a machine-learned generation module", Proceedings of the International Language Generation Conference 2002, New York, pp. 33-40) имеет этап явного упорядочивания, который определяет порядок составляющих и их дочерних элементов, а не слов напрямую. Система Amalgam использует древовидную структуру составляющих и признаки этих составляющих. Путем установления порядка среди составляющих система Amalgam ограничивает возможные реализации предложений на уровне слов. Однако усовершенствования в моделях системы Amalgam структуры составляющих, используемых для установления порядка составляющих при генерировании естественного языка, могут принести более хорошие результаты; и эти усовершенствования находятся в фокусе настоящего описания.

Сущность изобретения

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

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

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

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

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

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

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

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

Краткое описание чертежей

Фиг.1 - блок-схема одной примерной среды, в которой может быть использовано настоящее изобретение.

Фиг.2 - блок-схема одного варианта выполнения системы реализации предложений, включающей в себя компоненты для упорядочивания, представляющая настоящее изобретение и показывающая поток данных.

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

Фиг.4 - примерное синтаксическое представление предложения, используемое как входные данные для настоящего изобретения, выполненное в логической форме.

Фиг.5 - иллюстрация примера неупорядоченного синтаксического дерева, соответствующего логической форме по фиг.4 и являющегося примером типа входных данных для упорядочивающего компонента.

Фиг.6 - иллюстрация примера упорядоченного синтаксического дерева, соответствующего неупорядоченному дереву по фиг.5 и являющегося примером выходных данных из компонента упорядочивания деревьев.

Фиг.7 - блок-схема, иллюстрирующая разложение составляющей с ориентацией слева направо.

Фиг.8 - блок-схема, иллюстрирующая разложение вершинной составляющей.

Фиг.9 - блок-схема, иллюстрирующая разложение составляющей с ориентацией слева направо с использованием двоичной условной модели.

Фиг.10 - таблица результатов сравнения различных моделей порядка одновременно для немецкого и французского языков.

Фиг.11 - таблица результатов сравнения подмножества моделей порядка, имеющих и не имеющих признаки местоположения глагола.

Подробное описание примерных вариантов выполнения

Настоящее изобретение описывается в отношении системы реализации предложений. Настоящее изобретение включает в себя компонент упорядочивания деревьев всей системы реализации предложений и способы, используемые в этом компоненте.

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

Фиг.1 иллюстрирует пример среды 100 подходящей вычислительной системы, в которой может быть воплощено изобретение. Среда 100 вычислительной системы является только одним примером подходящей вычислительной среды и не предназначена для выдвижения каких-либо ограничений к объему использования или к функциональным возможностям изобретения. Вычислительная среда 100 также не должна интерпретироваться как имеющая какую-либо зависимость или требование, относящееся к какому-либо компоненту или комбинации компонентов, показанных в примерной рабочей среде 100.

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

Изобретение может быть описано в общем контексте машинно-исполняемых команд, таких как программные модули, исполняемые компьютером. В общем случае программные модули включают в себя процедуры, программы, объекты, компоненты, структуры данных и т.д., которые выполняют конкретные задачи или воплощают определенные абстрактные типы данных. Изобретение может также осуществляться в распределенных вычислительных средах, где задачи выполняются удаленными обрабатывающими устройствами, которые соединены через сеть связи. В распределенной вычислительной среде программные модули могут быть расположены как на локальном, так и на удаленном компьютерном носителе данных, включая запоминающие устройства.

На фиг.1 примерная система для воплощения изобретения включает в себя вычислительное устройство общего назначения в виде компьютера 110. Компоненты компьютера 110 могут включать в себя, но не в ограничительном плане - процессорный блок 120, системную память 130 и системную шину 121, которая соединяет различные компоненты системы, включая системную память, с процессорным блоком 120. Системная шина 121 может быть любого типа из нескольких типов структур шин, в том числе шиной памяти или контроллером памяти, шиной для связи с периферийными устройствами и локальной шиной, использующих любую из множества архитектур шин. Для примера, но не для ограничения, такие архитектуры включают в себя шину ISA (Industry Standard Architecture - архитектура промышленного стандарта), шину МСА (Micro Channel Architecture - микроканальная архитектура), шину EISA (Enhanced ISA - расширенная архитектура промышленного стандарта), локальную шину VESA (Video Electronics Standards Association - стандарт Ассоциации по стандартизации в области видеотехники и микроэлектроники) и шину PCI (Peripheral Component Interconnect - межсоединение периферийных компонентов), также известную как шину Mezzanine.

Компьютер 110 обычно включает в себя множество машиночитаемых носителей данных. Машиночитаемыми носителями данных могут быть любые доступные носители данных, к которым может осуществить доступ компьютер 110, и включают в себя энергозависимые и энергонезависимые носители данных, сменные и несменяемые носители данных. Для примера, но не для ограничения, машиночитаемые носители данных могут содержать компьютерные носители данных и среды передачи данных. Компьютерные носители данных включают в себя энергозависимые и энергонезависимые носители, сменные и несменяемые носители, воплощенные любым способом или по любой технологии для хранения информации, такой как машиночитаемые команды, структуры данных, программные модули или другие данные. Компьютерные носители данных включают в себя, но не в ограничительном смысле, ОЗУ (RAM), ПЗУ (ROM), электрически стираемое перепрограммируемое ПЗУ (EEPROM), флэш-память или память другой технологии, компакт-диски (cd-rom), цифровые многофункциональные диски (DVD) или другие носители в виде оптических дисков, магнитные кассеты, магнитные ленты, носители в виде магнитных дисков или другие магнитные запоминающие устройства, либо любой иной носитель данных, который может быть использован для хранения желаемой информации и к которому может осуществить доступ компьютер 110. Среды передачи данных обычно воплощают машиночитаемые команды, структуры данных, программные модули или другие данные в виде сигналов, модулированных данными, таких как сигнал, несущий колебание, или другой механизм передачи, и включают в себя любые среды доставки информации. Термин "сигнал, модулированный данными" означает, что у сигнала одна или более характеристик установлена или изменена таким образом, чтобы обеспечить кодирование информации в сигнале. Для примера, но не для ограничения, среды передачи данных включают в себя проводные среды, такие как проводная сеть или прямое кабельное соединение, и беспроводные среды, такие как акустические, радиочастотные, инфракрасные и другие беспроводные среды. Сочетания любых из перечисленных выше сред также должны быть включены в список машиночитаемых носителей данных.

Системная память 130 включает в себя компьютерные носители данных в виде энергозависимой и/или энергонезависимой памяти, такой как постоянное запоминающее устройство (ПЗУ, ROM) 131 и оперативное запоминающее устройство (ОЗУ, RAM) 132. В ПЗУ 131 обычно хранится базовая система ввода-вывода 133 (BIOS), содержащая основные процедуры, которые помогают передавать информацию между элементами в компьютере 110, например, во время загрузки. ОЗУ 132 обычно содержит данные и/или программные модули, которые оперативно доступны и/или обрабатываются в настоящее время процессорным блоком 120. Для примера, но не для ограничения, фиг.1 иллюстрирует операционную систему 134, прикладные программы 135, другие программные модули 136 и данные 137 программ.

Компьютер 110 также может включать в себя другие сменные/несменяемые энергозависимые/энергонезависимые компьютерные носители данных. Только для примера фиг.1 показывает накопитель 141 на жестких магнитных дисках, который считывает с несменяемого энергонезависимого магнитного носителя или записывает на него, дисковод 151 для магнитного диска, который считывает со сменного энергонезависимого магнитного диска или записывает на него, и дисковод 155 для оптического диска, который считывает со сменного энергонезависимого оптического диска 156, такого как компакт-диск или другой оптический носитель, или записывает на него. Другие сменные/несменяемые энергозависимые/энергонезависимые компьютерные носители данных, которые могут быть использованы в примерной рабочей среде, включают в себя, но не в ограничительном смысле, следующие носители: кассеты с магнитной лентой, цифровые многофункциональные диски (DVD), цифровую видеоленту, твердотельные ОЗУ, твердотельные ПЗУ и т.п. Накопитель 141 на жестких магнитных дисках обычно соединен с системной шиной 121 через интерфейс несменяемого запоминающего устройства, такой как интерфейс 140, а дисковод 151 для магнитного диска и дисковод 155 для оптического диска обычно соединены с системной шиной 121 интерфейсом сменного запоминающего устройства, таким как интерфейс 150.

Дисководы и связанные с ними компьютерные носители данных, обсужденные выше и показанные на фиг.1, обеспечивают хранение машиночитаемых команд, структур данных, программных модулей и других данных для компьютера 110. На фиг.1, например, накопитель 141 на жестких магнитных дисках показан как хранящий операционную систему 144, прикладные программы 145, другие программные модули 146 и данные 147 программ. Отметим, что эти компоненты могут либо быть такими же, как и операционная система 134, прикладные программы 135, другие программные модули 136 и данные 137 программ, либо отличаться от них. Операционной системе 144, прикладным программам 145, другим программным модулям 146 и данным 147 программ здесь присвоены отличающиеся ссылочные позиции, чтобы показать, что они как минимум являются другими копиями.

Пользователь может вводить команды и информацию в компьютер 110 через устройства ввода, такие как клавиатура 162, микрофон 163 и позиционирующее устройство 161, такое как мышь, шаровой манипулятор (трекбол) или сенсорная панель. Другие устройства ввода (не показаны) могут включать в себя джойстик, игровую приставку, спутниковую тарелку, сканер и т.п. Эти и другие устройства ввода часто соединены с процессорным блоком 120 через пользовательский интерфейс 160 ввода, который связан с системной шиной, но могут быть подключены и посредством другого интерфейса и структур шин, такого как параллельный порт, игровой порт или универсальная последовательная шина (USB). Монитор 191 или другой тип устройства отображения также подключен к системной шине 121 через интерфейс, такой как видеоинтерфейс 190. В дополнение к монитору компьютеры могут также включать в себя другие периферийные устройства вывода, такие как громкоговорители 197 и принтер 196, которые могут быть подключены через выходной периферийный интерфейс 195.

Компьютер 110 может работать в сетевой среде с использованием логических соединений с одним или более удаленными компьютерами, такими как удаленный компьютер 180. Удаленным компьютером 180 может быть персональный компьютер, переносное устройство, сервер, маршрутизатор, сетевой ПК, одноранговое устройство или другой общий сетевой узел, и обычно такой компьютер включает в себя множество или все элементы, описанные выше относительно компьютера 110. Логические соединения, показанные на фиг.1, включают в себя локальную сеть (ЛС, LAN) 171 и глобальную сеть (ГС, WAN) 173, но также могут включать в себя и другие сети. Такие сетевые среды обычны для офисов, компьютерных сетей масштаба предприятия, интрасетей и сети Интернет.

Когда используется сетевая среда ЛС, компьютер 110 соединен с ЛС 171 через сетевой интерфейс или адаптер 170. Когда используется сетевая среда ГС, компьютер 110 обычно включает в себя модем 172 или другое средство для установления связи через ГС 173, такую как сеть Интернет. Модем 172, который может быть внутренним или внешним, может быть подключен к системной шине 121 через пользовательский интерфейс 160 ввода или другой соответствующий механизм. В сетевой среде программные модули, показанные для компьютера 110 или его части, могут храниться в удаленном запоминающем устройстве. Для примера, но не для ограничения, фиг.1 показывает удаленные прикладные программы 185 как находящиеся на удаленном компьютере 180. Должно быть понятно, что показанные сетевые соединения являются примерами, и для установления линии связи между компьютерами могут быть использованы другие средства.

Фиг.2 является блок-схемой (также иллюстрирующей поток данных) компонента 200 реализации предложений, в котором используется настоящее изобретение. Компонент 200 реализации предложений включает в себя компонент 202 предварительной обработки, компонент 204 конкретизации, компонент 206 преобразования в основное дерево, компонент 208 глобального перемещения, компонент 210 упорядочивания внутри составляющих, компонент 212 очистки поверхности, компонент 214 введения пунктуации, компонент 216 генерирования флексий и компонент 218 чтения деревьев. Теперь описывается общее функционирование системы 200.

Система 200 принимает в качестве ввода абстрактное лингвистическое представление входного предложения. В обсуждаемом здесь варианте выполнения ввод осуществляется в логическом виде. Однако должно быть понятно, что по существу любое другое синтаксическое или семантическое представление предложения может быть принято в качестве входных данных. Структура логической формы устанавливается более подробно в патенте США № 5966686, выданном 12 октября 1999 года на имя Heidorn et al. под названием "Method and System for Computing Semantic Logical Forms from Syntax Trees"

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

Компонент 204 конкретизации принимает структуру 220 данных и добавляет к этой структуре данных синтаксическую информацию. Компонент 204 конкретизации также вводит функциональные слова, такие как определяющие слова, вспомогательные глаголы, семантически пустые предлоги, относительные местоимения и т.д. Компонент 204 также присваивает признаки падежа и признаки положения глаголов, а также вероятности распознавания именных групп в субъектных или объектных положениях. Компонент 204 конкретизации обеспечивает на выходе структуру 222, которая является структурой, полученной в результате расформирования представления в виде графа, с добавленной к ней синтаксической и другой информацией.

Компонент 206 преобразования в основное дерево принимает структуру 222 данных и преобразует эту структуру данных в основное синтаксическое дерево. Компонент 206 считывает структуру синтаксического дерева из структуры 222 данных, полученной в результате расформирования представления в виде графа, и выделяет отделяемые приставки от их основ. Компонент 206 также может ввести синтаксическое представление сочинения и обратить определенные синтаксические отношения зависимости. Компонент 206 обеспечивает на выходе основное неупорядоченное синтаксическое дерево 224.

Компонент 208 глобального перемещения принимает структуру 224 и выполняет глобальное перемещение или глобальное упорядочивание. Глобальное перемещение включает в себя перемещение вопросительных слов, относительных местоимений и процесс, известный в лингвистической теории как «выращивание» (raising). Компонент 208 также выполняет обработку экстрапозиции. Компонент 208 обеспечивает на выходе структуру 226, в которой каждая составляющая имеет корректно определенного предка, хотя составляющие в структуре 226 не упорядочены.

Компонент 210 упорядочивания внутри составляющих принимает структуру 226 на входе и полностью упорядочивает узлы в синтаксическом дереве, чтобы обеспечить на выходе полностью упорядоченное синтаксическое дерево 228.

Компонент 212 очистки поверхности принимает структуру 228 и выполняет операции по очистке поверхности, такие как реализация поверхности для определяющих слов, относительных местоимений и возвратных местоимений. Компонент 212 также удаляет продублированный материал в сочинении. Компонент 212 обеспечивает на выходе очищенное полностью упорядоченное синтаксическое дерево 230.

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

Компонент 216 генерирования флексий принимает структуру 232 и вырабатывает конечную флексию и выдает конечное флективное дерево 234. Компонент 218 чтения деревьев просто считывает дерево 234 и обеспечивает на выходе поверхностную строку 236 (или реализованное предложение 236), выдавая слова на листьях конечного флективного дерева 234. Этим заканчивается процесс, показанный на фиг.2.

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

Когда все синтаксические узлы созданы и все иерархические отношения установлены, определяется порядок среди составляющих неупорядоченного синтаксического дерева, чтобы выработать упорядоченное синтаксическое дерево. Это представлено в общем виде на фиг.3, на которой неупорядоченное синтаксическое дерево упорядочивается компонентом 210 упорядочивания, результатом чего является упорядоченное синтаксическое дерево (или список упорядоченных деревьев). Неупорядоченное синтаксическое дерево может быть, для примера, таким, как показано позицией 226 на фиг.2, тогда как упорядоченное синтаксическое дерево может быть таким, как показано позицией 228 на фиг.2. Например, рассмотрим неупорядоченное синтаксическое дерево для примера по фиг.5. Это неупорядоченное синтаксическое дерево получено из графа семантических зависимостей, показанного на фиг.4 для следующего предложения на немецком языке: "In der folgenden Tabelle werden die Optionen sowie deren Funktionen aufgelistet". Английский эквивалент этого предложения таков: "The options and their functions are listed in the following table" (В следующей ниже таблице перечислены варианты выбора и их функции). На фиг.5 семантические отношения между модификатором и вершиной показаны круглыми скобками на листьях дерева. Упорядоченным синтаксическим деревом для этого неупорядоченного синтаксического дерева может быть дерево, показанное на фиг.6.

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

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

Порядок слов и составляющих

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

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

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

Французский язык подобен английскому языку в том смысле, что отношение между синтаксисом поверхности и грамматическими отношениями более прямое. Французский язык находится между английским и немецким языками по сложности задачи упорядочивания. Как и английский, французский язык имеет вполне строгий порядок составляющих, но порядок слов во французском языке менее строгий, чем в английском. Как и английский, французский язык является языком "субъект-глагол-объект" (СГО, SVO), но порядок слов практически свободный: дополнения в предложном обороте часто предшествуют объектным дополнениям, которые больше одного слова, и они могут появляться в начале предложения. В относительных предложениях часто встречается инверсия неклитических субъектов. Положение прилагательных также менее строгое, чем в английском языке: многие прилагательные могут предшествовать или следовать за существительным, которое они определяют, в то время как остальные прилагательные только предшествуют или следуют за существительным.

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

Модели порядка составляющих

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

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

Хотя описанные модели не охватывают все пространство возможных моделей, мы выбрали важные точки в этом пространстве.

Совместные модели

Начинаем рассматривать совместные модели структуры

Составляющих в форме Р(π,ρ) на упорядоченных синтаксических деревьях π и неупорядоченных синтаксических деревьях ρ. Упорядоченное дерево π содержит являющиеся нетерминалами составляющие С, каждая из которых является предком упорядоченной последовательности дочерних элементов (-D₁,...,D_n), один из которых является вершинной составляющей H (все прописные латинские буквы означают составляющие, а соответствующие строчные латинские буквы означают их метки, то есть синтаксические категории). Для заданного упорядоченного дерева π значением функции unordered _tree(π) является неупорядоченное дерево ρ, соответствующее π, которое содержит составляющую В для каждого С в π, так что В=unordered_set(C)={D₁,...,D_n}, при этом H=D_i для некоторого i в (1...n). Иерархическая структура ρ идентична π.

Мы используем совместные модели для подсчета альтернативно упорядоченных деревьев следующим образом: дано неупорядоченное синтаксическое дерево ρ, требуется получить упорядоченное синтаксическое дерево

, которое максимально увеличивает совместную вероятность. То есть требуется найти

Как показывает уравнение 1, мы можем ограничить наш поиск теми деревьями π, которые являются альтернативными упорядочениями данного дерева ρ.

Для ограничения видов возможных моделей, которые мы рассматриваем, предположим, что порядок любой составляющей независим от порядка остальных составляющих в дереве, включая ее дочерние элементы. Таким образом, каждая составляющая может быть упорядочена независимо, следовательно

В частности для π мы имеем

Наконец, для каждого В∈constits(ρ),

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

В действительности мы можем дополнительно ограничить наш поиск в соответствии с вершиной B, поскольку вершина C должна совпадать с вершиной B

Единственными возможными упорядоченными деревьями являются деревья, построенные из составляющих, которые удовлетворяют указанному выше предикату. Необходимо нормировать Р(С) так, чтобы Р(π) отражало это. Пусть Z будет нормирующей постоянной:

Затем,

Конечно, для данного В Z является постоянной, а следовательно, не влияет на значение arg max, так что нет необходимости вычислять ее на практике.

Теперь, если желательно задать условия для некоторого признака х=f(ρ), то мы сначала должны предсказать его следующим образом:

Если x действительно является признаком ρ и не зависит от того, какую С, совместимую с ρ, мы рассматриваем, то тогда Р(x) является постоянной, и нет необходимости вычислять ее на практике. Следовательно, даже для совместной модели Р(С) мы можем прибавить обусловливающие признаки, которые зафиксированы в данном неупорядоченном дереве ρ без начального их предсказания, как указано в Уравнении 9.

Совместные модели, описанные здесь, имеют такой вид. По этой причине, когда мы описываем распределение Р(С|х), в случае, если мы жестко не утверждаем обратное, мы в действительности описываем часть совместной модели, которая нас интересует. Как отмечено выше, нам нет необходимости вычислять Р(х), и мы просто представим альтернативные формы P(C|x).

Мы можем разложить на множители распределение Р(С) (или Р(С|х)) множеством различных способов, используя цепное правило.

Мы принимаем класс моделей, называемых марковскими грамматиками, в качестве нашей отправной точки. "Марковская грамматика" является моделью структуры составляющих, которая начинается у корня дерева и присваивает вероятность одного дочернего элемента, являющегося нетерминалом, за один момент времени, а не целым продукциям (см. Charniak, E., "Statistical Techniques for Natural Language Parsing", AI Magazine (1997); и Charniak, E., "A Maximum-Entropy-Inspired Parser", Proceedings of NAACL-2000, pp. 132-139).

Ориентация слева направо

По-прежнему сосредоточиваясь на совместных моделях, сначала мы рассматриваем марковскую грамматику с ориентацией слева направо порядка j, которая выполняет разложение С путем предсказания его дочерних элементов D₁,...,D_n слева направо по одному за момент времени, как показано на фиг.7 в соответствии с распределением в Уравнении 11.

Чтобы задать условия в отношении другого признака каждого дочернего элемента D_i, такой как его семантическое отношение ψ_i, к вершинной составляющей H, мы также сначала предсказываем его в соответствии с цепным правилом. Результатом является Уравнение 12;

Таким образом, модель предсказывает семантическое отношение ψ_i, а затем метку d_i, в контексте семантической связи.

В качестве расширения описанной выше модели мы включили признаки, вычисленные следующими функциями на наборе α_i уже упорядоченных дочерних элементов С:

- Количество уже упорядоченных дочерних элементов (в наборе α_i);

- Количество дочерних элементов в α_i, имеющих конкретную метку для каждой из возможных меток составляющих {NP (именная конструкция), AUXP (вспомогательно-глагольная конструкция), VP (глагольная конструкция), и т.п.} (24 для немецкого языка, 23 для французского).

В этом случае модель Маркова порядка j может потенциально иметь истинный порядок, который больше j. В этом месте наше использование термина "марковская грамматика" отличается от обычных интерпретаций этой фразы. Мы обозначаем этот набор признаков для краткости как f(а_i):

Вершинная ориентация

В качестве альтернативы разложению на ориентации слева направо, мы можем охарактеризовать каждую составляющую С упорядоченного дерева π как дочерний элемент вершины Н, упорядоченные предваряющие модификаторы (L₁,...,L_m) (в отношении H), и упорядоченные последующие модификаторы (R₁,...,R_n), как показано на фиг.8. Мы называем это "вершинной марковской грамматикой". Если наш условный контекст заканчивается в вершине, то без потери общности наше разложение сначала начинается с предваряющих модификаторов, за которыми идут последующие модификаторы. Распределение состоит из двух частей, одна часть для разложения предваряющих модификаторов, а вторая часть для разложения последующих модификаторов:

Как и в случае с ориентацией слева направо, мы задаем условия в отношении семантического отношения дочернего элемента к вершинной составляющей Н. Для модели с более широкими возможностями мы задаем условия с отношении обусловливания полного набора а_i уже упорядоченных дочерних элементов (тем самым задавая условия в отношении признаков на всей вершине).

Теперь рассмотрим более сложные модели, которые используют дополнительные признаки; вершину Н составляющей С, неупорядоченную составляющую В, соответствующую С, их предка Р_В и предка G_B предка. В контексте Уравнения 13 каждый из В, Р_B и CB представляет набор лингвистических признаков по следующим соответствующим составляющим:

Следовательно, наша сложная модель с ориентацией слева направо структурирована следующим образом:

Здесь каждая модель P(C|h,B,P_B,G_B) может консультировать произвольные признаки В. Мы также включаем признаки, которые являются функциями на наборе а_i уже упорядоченных дочерних элементов С.

Наконец, мы оставляем совместные модели и вводим действительно условные модели путем включения признаков, которые являются функциями на наборе β_i дочерних элементов С, все еще подлежащих упорядочиванию. Например:

- количество остающихся дочерних элементов, подлежащих упорядочиванию (размер β_i)

- количество дочерних элементов в β_i, имеющих конкретную метку.

Мы обозначаем эти наборы признаков как f(а_i) и f(β_i);

Как и с простыми моделями, мы также рассматриваем сложные вершинные марковские грамматики того же вида.

Двоичная условная модель

Мы вводим третий тип модели, названный нами "двоичная условная модель". Она оценивает распределение двоичной переменной σ, названной "сортируемой следующей по очереди" со значениями в диапазоне {да, нет}. Она представляет событие, которое как все еще неупорядоченный элемент D в β_i, (множестве все еще неупорядоченных дочерних элементов предка С, как определено выше) должно быть "отсортировано" следующим, как показано на фиг.9. Обусловливающие признаки почти идентичны тем, которые используются в условных моделях с ориентацией слева направо, обсужденных выше, за исключением того, что D и ψ (семантическое отношение D с вершиной H), появляющиеся в условном контексте, никогда нельзя предсказать. в своей простой форме модель оценивает следующее распределение:

Мы опишем, как применить эту модель напрямую в "сортирующем" поиске с ориентацией слева направо позже в разделе поиска.

Оценка

Мы можем оценить распределения для модели с использованием различных методик. Для этого описания мы используем методику интерполированного моделирования языка (далее называемое МЯ - LM, language modeling), а также вероятностные деревья решений (ДР - DT, decision trees). Хотя они и не раскрыты подробно в настоящем описании, специалист в данной области техники поймет, что также могут быть использованы другие подходы к отбору признаков и оценке распределения.

В наших экспериментах мы описываем модели обоих типов. Все модели в этом описании являются марковскими моделями порядка 2 за исключением функций f(α_i) и f(β_i) дополнительных признаков, определенных выше.

Моделирование языка

Наши модели МЯ используют интерполирование Кнезера-Нея (Kneser-Ney) в качестве методики сглаживания. См. Kneser R. and Ney н., 1995, ^Improved backing-off for m-gram language modeling". Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, Vol. 1, pp. 181-184; и Goodman J.T., 2001, "A Bit of Progress in Language Modeling; Extended Version", Microsoft technical report MSR-TR-2001-72. Одним недостатком такого подхода (и инструментальных средств, которые мы используем), является необходимость отбора признаков вручную и определяемый вручную порядок возврата, практическое воздействие которого заключается только в том, что относительно небольшое количество признаков может быть использовано эффективно. В наших экспериментах мы используем единую вершинную модель такого типа.

Деревья решений

Мы строим деревья решений, используя инструментальное средство WinMine (см. Chickering D.M., 2002, "The WinMine Toolkit", Microsoft Technical Report 2002-103). Следует уточнить, что полученные на основе обучения с помощью WinMine деревья решений не являются простыми классификаторами; каждый лист является условным распределением вероятности по значениям целевого признака при условии, что все признаки доступны при обучении; следовательно, дерево само по себе является оценкой того же самого условного распределения. Основное преимущество в использовании деревьев решений, и в частности вероятностных деревьев решений, заключается в автоматическом отборе признаков из обширного круга признаков. Мы используем шесть моделей такого типа для широкого множества признаков. Две модели являются совместными; две являются совместными с признаками в наборе уже упорядоченных дочерних элементов (обозначаемых f(α_i)); две являются условными. Одна из моделей каждого типа является вершинной, а вторая из каждого типа является моделью с ориентацией слева направо. Кроме того, мы используем одну двоичную условную модель ДР с ориентацией слева направо как с нормировкой, так и без нее.

Признаки и отбор признаков

Для различных моделей деревьев решений выделяется широкий диапазон лингвистических признаков. Количество выбранных признаков для немецкого языка находится в диапазоне от 6 до 8 (из 8) для совместных моделей, от 7 до 16 (из 33) для совместных моделей f(α_i), от 21 до 107 (из 487 (вершинная), 494 (с ориентацией слева направо)) для условных моделей, и достигает 280 (из 651) в двоичной условной модели, для французского языка количество выбранных признаков находится в диапазоне от 6 до 8 (из 8) для совместных моделей, от 7 до 11 (из 32) для совместных моделей с f(α_i), от 22 до 91 (из 404 (вершинная), 429 (с ориентацией слева направо)) для условных моделей и достигает 218 (из 550) в двоичной условной модели, причем все эти признаки вполне сравнимы с моделями немецкого языка. Из полного спектра доступных признаков сложные и двоичные условные модели могут получить следующее:

- признаки лексического разбиения на категории, такие как транзитивность и совместимость с дополнениями в предложениях;

- леммы (или основы слова);

- семантические признаки, такие как семантическое отношение и наличие операторов квантификации;

- длина составляющей в словах;

- синтаксическую информацию, такую как метка и наличие синтаксических модификаторов.

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

Поиск - Исчерпывающий поиск

Для заданного неупорядоченного дерева ρ и модели структуры О составляющих, мы проводим поиск наилучшим образом упорядоченного дерева π, которое максимизирует Р_O(π|ρ), с контекстом, изменяющимся в соответствии со сложностью модели. Каждая из наших моделей (исключая двоичную условную модель) оценивает вероятность упорядочивания любой заданной составляющей С в π независимо от упорядочивания внутри других составляющих в π. Полным поиском является алгоритм динамического программирования либо с ориентацией слева направо в дочерних элементах С, либо с вершинной в зависимости от модели. Поиск поддерживает одно нестатистическое ограничение: он соблюдает порядок согласованных составляющих, как они появляются в ""неупорядоченном" дереве.

Поиск - Экономный поиск для двоичной условной модели Двоичная условная модель применяется в режиме "сортировки" с ориентацией слева направо, см. фиг.9 для схемы процесса. Для каждого неупорядоченного дочернего элемента D_j в B_i к модели обращаются за справкой в отношении вероятности того, что σ_j=yes, то есть того, что D_j. должно быть помещено справа от уже упорядоченных родственных составляющих а_i. Дочерний элемент в β_i, характеризуемый наивысшей вероятностью, удаляется из β_i и расширяет α_i, справа. Поиск продолжается для оставшихся неупорядоченными составляющих до тех пор, пока все составляющие в списке неупорядоченных составляющих не будут упорядочены таким экономичным образом.

Чтобы применить эту модель к исчерпывающему поиску ДР, мы нормируем модель на каждом этапе поиска и тем самым удерживаем ее в рамках распределения вероятности по всем оставшимся дочерним элементам в β_i. Мы представляем Уравнение 18 в кратком виде как Р(σ|d,ψ,Г_i), где Г_i представляет признаки контекста для данной поисковой гипотезы на этапе i поиска. Таким образом, наше нормированное распределение для этапа i задано в Уравнении 19. Свободная переменная j представляет список неупорядоченных дочерних элементов в β_i как и k.

Эксперименты - Обучение

Мы здесь описываем совокупность экспериментов для сравнения и противопоставление различных вышеописанных моделей. Для обучения мы использовали обучающий набор из 20000 предложений на французском и немецком языках. Данные были взяты из технических руководств в компьютерной области. Для каждого предложения в обучающем наборе предложение сначала анализировалось как синтаксическое дерево и граф семантической зависимости с использованием системы NLPWin (патент США № 5966686, выданный 12 октября 1999 года Heidorn et al. под названием "Method and System for Computing Semantic Logical Forms from Syntax Trees". Принимая во внимание граф семантической зависимости и синтаксическое дерево, вырабатывалось дерево со всеми характеристиками деревьев, увиденных на этапе упорядочивания с помощью системы Amalgam в течение времени генерирования за одним исключением: эти обучающие деревья должным образом упорядочены. Это дерево включает все представляющие интерес признаки, включая семантические отношения между вершиной и ее модификаторами. Используемые модели порядка обучаются на основе составляющих этих деревьев.

Эксперименты - Оценка

Для оценки моделей процесс упорядочивания оценивается изолированно, независимо от остального процесса реализации предложений в системе Amalgam. Используются тестовые наборы из 1000 предложений, также из технических руководств, для каждого языка. Чтобы изолировать упорядочивание для заданного тестового предложения, это предложение обрабатывается как и при обучении, чтобы выработать упорядоченное дерево π (эталон для оценки) и неупорядоченное дерево ρ из него. Для данного ρ мы затем проводим поиск гипотетического наилучшим образом упорядоченного дерева π с использованием изучаемой модели. Затем проводится сравнение π и

. Поскольку было выполнено лишь упорядочивание составляющих, π и

можно сравнивать путем сравнения порядка их соответствующих составляющих. Метрикой, используемой в этом случае для сравнения двух составляющих, является расстояние редактирования, измеряемое как процент от всех дочерних элементов, которые участвуют в перемещении. Общей балльной оценкой для гипотетического дерева

является взвешенное среднее значение расстояния редактирования на каждую составляющую.

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

Для каждой модели средняя балльная оценка в тестовом наборе для заданного языка отражена в таблице на фиг.10. Как для немецкого, так и для французского языка двоичная условная модель ДР с ориентацией слева направо (примененная в экономном поиске) превосходит все остальные модели. Нормировка двоичной условной модели и применение ее в избыточном поиске не помогает; в действительности небольшое ухудшение точности может происходить от проблемы смещения метки. См. Lafferty J. et al., 2001, "Conditional Random Fields: Probabilistic models for segmenting and labeling sequence data" в Proceedings of 18^th ICML. pp. 282-289.

Интерполированная модель языка занимает второе место по эффективности как для французского, так и для немецкого языка. Эта модель имеет простейшую структуру, но использует наиболее сложное сглаживание.

Интересно отметить, что совместные модели с ориентацией слева направо (без признаков f(α_i)) превосходят вершинные совместные модели как для немецкого, так и для французского языка. Включение признаков f(α_i) для моделей с ориентацией слева направо и вершинных моделей изменяет ситуацию для французского языка, но не для немецкого.

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

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

По отношению к отдельным синтаксическим категориям сила двоичной условной модели заключается в первую очередь в корректном установлении порядка составляющих внутри глагольных составляющих. Для немецкого языка показатель двоичной условной модели составил 9,892% для глагольных составляющих. Лучшая из оставшихся других моделей может показать 13,61% (совместная модель с ориентацией слева направо с f(α_i)). Для французского языка двоичная условная модель показала 3,602% для глагольных составляющих. Лучшая из оставшихся других моделей может показать 5,981% (вершинная совместная модель языка).

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

Опять-таки, наилучшей моделью является двоичная условная модель. Как и раньше, нормировка не помогает. Улучшение, привносимое доступностью признака положения глагола, дает 13%-ное относительное сокращение общей частоты ошибок при упорядочивании. Для глагольных составляющих показатель улучшается до 8,468% с признаками положения глагола. Следующей по качеству моделью для положения глагола является условная модель с ориентацией слева направо с показателем 12,59%.

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

Claims

1. Компонент упорядочивания деревьев в системе реализации предложений, которая принимает неупорядоченное синтаксическое дерево и генерирует ранжированный список альтернативно упорядоченных синтаксических деревьев, для элементов которого заданы балльные оценки, из неупорядоченного синтаксического дерева, при этом компонент упорядочивания деревьев содержит

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

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

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

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

4. Компонент упорядочивания деревьев по п.1, в котором в генеративной статистической модели структуры составляющих параметры модели оцениваются посредством методики максимальной энтропии.

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

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

7. Компонент упорядочивания деревьев по п.6, в котором в генеративной статистической модели структуры составляющих моделью, имеющей структуру марковской грамматики, является совместная модель структуры составляющих.

8. Компонент упорядочивания деревьев по п.6, в котором в генеративной статистической модели структуры составляющих моделью, имеющей структуру марковской грамматики, является условная модель структуры составляющих.

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

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

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

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

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

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

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

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

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

18. Компонент упорядочивания деревьев по п.1, в котором в генеративной статистической модели структуры составляющих набор признаков модели включает в себя признаки набора составляющих, определяемого следующим образом: для конкретной составляющей неупорядоченного дерева, в процессе упорядочивающего поиска, относительно одной гипотезы упорядочивания, дочерние элементы упомянутой составляющей уже упорядочены.

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

20. Компонент упорядочивания деревьев по п.18, в котором в генеративной статистической модели структуры составляющих признаки представляющего интерес набора составляющих включают в себя общее количество появлений каждой синтаксической категории в этом наборе.

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

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

23. Компонент упорядочивания деревьев по п.21, в котором в генеративной статистической модели структуры составляющих признаки представляющего интерес набора составляющих включают в себя общее количество появлений каждой синтаксической категории в этом наборе.

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

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

26. Компонент упорядочивания деревьев по п.24, в котором в генеративной статистической модели структуры составляющих признаки представляющего интерес набора составляющих включают в себя общее количество появлений каждой синтаксической категории в этом наборе.