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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

Примером системы этой третьей категории является система 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^th International 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.

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

Больши