СПОСОБ СУММАРИЗАЦИИ ТЕКСТА И ИСПОЛЬЗУЕМЫЕ ДЛЯ ЕГО РЕАЛИЗАЦИИ УСТРОЙСТВО И МАШИНОЧИТАЕМЫЙ НОСИТЕЛЬ ИНФОРМАЦИИ
TEXT SUMMARIZING METHOD AND DEVICE AND MACHINE-READABLE MEDIA USED FOR ITS IMPLEMENTATION

Область техники, к которой относится изобретение
Настоящее изобретение относится в целом к области электронной обработки информации, а в частности - к средствам суммаризации текста на основе анализа предикатно-аргументных структур каждого предложения в тексте.
Настоящее изобретение может быть использовано в тех случаях, когда пользователю требуется быстро и точно определить и извлечь основные идеи или события из электронных писем, новостей и других источников мультимедиа.
Уровень техники
Процесс автоматического преобразования первоначального текста электронного документа в более короткий текст (реферат), содержащий основные идеи первоначального текста, носит название суммаризации текста. Суммаризацию текста можно разделить на следующие два типа: квазиреферирование (extractive), если реферат документа составлен из предложений исходного документа; и краткое изложение (abstractive), если предложения первоначального документа перефразируются для составления реферата. Из-за требования перефразирования текста задача краткого изложения считается более трудной, чем квазиреферирование.
Существуют два типа входных данных в систему суммаризации текста: несколько документов и единственный документ. В случае нескольких входных документов их темы могут совпадать друг с другом, как в случае новостных документов одной тематики, или же их темы могут различаться между собой (в таком случае система суммаризации должна выделить наиболее важную информацию про тему каждого входного документа). В случае единственного входного документа важная информация может встретиться в документе только один раз. Проблема здесь состоит в том, что зачастую нет дополнительной статистики о том, какая информация является более важной в документе. Поэтому суммаризация единственного документа считается более сложной задачей.
Известные системы суммаризации текста можно разделить на группы, использующие (а) тематическое моделирование событий, (б) суммаризацию событий из нескольких документов, (в) квазиреферирование единственного документа и (г) краткое изложение единственного документа.
Что касается систем группы (а), то один их пример раскрыт в документе WO 2014171925 A1, в котором речь идет об использовании латентного размещения Дирихле (Latent Dirichlet Allocation, LDA) в качестве метода тематического моделирования событий в контенте социальных сетей. Сначала с помощью LDA извлекают кластеры событий, причем каждое событие описывает действие/ситуацию, произошедшую в жизни, а каждый кластер событий объединяет обобщенные события, близкие по смыслу. После этого находят кластеры событий, которые привлекли внимание людей (например, землетрясения или политические протесты). События в этих кластерах затем суммаризируются в качестве ответа на пользовательский запрос. Однако описанная система решает задачу построения суммаризации событий по запросу пользователя, либо для подбора материалов под определенного пользователя. Кроме того, в данном случае требуется обработка большого объема текстов, таких как твиты или блог-посты. Извлеченные события не могут быть перефразированы, что важно в случае суммаризации единственного текста.
Примеры систем группы (б) описаны, например, в указанных ниже документах, целью которых является суммаризация событий из потока текстовых документов.
В документе US 9020865 B2 раскрыта система, извлекающая события и мини-события из текста. С помощью мини-событий создают полное событие, позволяющее создать цепочку событий для суммаризации потока текстов. Однако в данном случае требуется хранить информацию о времени наступления события. Кроме того, требуется обработка потока текстов для суммаризации.
В документе US 20140172427 A1 описана система, извлекающая первое мини-событие из хронологически упорядоченных частей текста. Сначала разбивают сообщение на потоки, соответствующие участникам сообщения. Для каждого потока система находит мини-события, в которых участвует соответствующий участник, т.е. тот, кто участвует или упомянут в событии или связан с ним. После этого наиболее важные мини-события объединяют в глобальные рефераты из мини-событий. Однако этот подход требует наличия многочисленных мини-событий для суммаризации.
Примерами систем группы (в) являются те, что раскрыты в документах CN 201310072118 и US 20140195897 A1.
В документе CN 201310072118 описана система суммаризации единственного документа, извлекающая семантические блоки из текста. Эта система отбирает предложения с похожими терминами в соответствии с тезаурусом Hownet и группирует найденные предложения в семантический блок. Далее она использует веса терминов и сущностей в блоке для представления в виде вектора. После этого система ранжирует блоки в соответствии с косинусовой мерой близости с другими блоками. Для создания рефератов предложения ранжируют в соответствии с оценкой блока и оценкой предложения внутри блока. Однако такой подход не учитывает отношения между сущностями в блоке. Кроме того, такой подход не позволяет извлечь части предложений.
В документе US 2014/0195897 A1 описана система суммаризации текста, которая извлекает текстовые свойства, помогающие обнаружить важные части текста. Текстовые свойства состоят из предложений, параграфов и других структур, включающих в себя несколько предложений. Используя текстовые свойства, эта система создает граф со структурой микромира, отражающего содержание документа. Затем вершины графа ранжируют в соответствии с их важностью. Текстовые свойства, соответствующие наиболее важным вершинам, извлекают в качестве реферата документа. Основным недостатком такого подхода является невозможность удаления нерелевантных частей длинных предложений.
Примеры систем группы (г) раскрыты в следующих статьях: D. Pighin, M. Cornolti, E. Alfonseca and K. Filippova, Modelling Events through Memory-based, Open-IE Patterns for Abstractive Summarization, In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, 2014 (далее - статья 1); и Y. Kikuchi, T. Hirao, H. Takamura, M. Okumura and M. Nagata, Single document summarization based on nested tree structure, In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, 2014 (далее - статья 2).
В статье 1 описана система, извлекающая событие и генерирующая короткий реферат из единственного текста. Чтобы извлечь событие, система создает шаблоны событий с помощью эвристического подхода, подхода, базирующегося на компрессии, и подхода, базирующегося на использовании памяти. Для эффективного сохранения событий используется структура суффиксного дерева tree-trie. Однако получаемый реферат состоит только из единственного предложения. Кроме того, такой метод требует хранения 1 Гб шаблонов в оперативной памяти.
В статье 2 обсуждается комбинирование зависимостных отношений между словами с риторическими отношениями между предложениями в структуре вложенного дерева. Такой подход требует использования зависимостного и дискурсивного парсеров. Однако этот подход позволяет извлечь только части текста без их перефразирования. Кроме того, такой подход не позволяет объединять различные упоминания сущности или событий.
Раскрытие изобретения
Задача настоящего изобретения заключается в устранении или смягчении вышеупомянутых недостатков, присущих решениям, известным из уровня техники.
В частности, авторы настоящего изобретения разработали подход, работающий для всех вышеуказанных типов суммаризации текста. В то же время основное внимание в данном документе уделено краткому изложению единственного документа. В этом случае информация (новостные тексты, статьи, рекламные буклеты, электронные письма) обычно не повторяется (в отличие от случаев нескольких входных документов). Кроме того, в исходном тексте могут быть неправильно составленные предложения, содержащие важную информацию. Это усложняет задачу суммаризации текста и требует интенсивного использования лингвистического подхода для ее решения.
Action
Arg0
Arg1
<Arg0: мама; Action: мыла; Arg1: раму>
«мыла»
мама
раму
Основная идея настоящего изобретения состоит в моделировании текста в виде множества событий или, по-другому, действий. Примером события является следующая фраза: «Мама мыла раму», - в которой «мыла» - предикат действия, обозначаемый как , «мама» - 1-й аргумент (субъект действия), обозначаемый как , «раму» - 2-й аргумент (объект действия), обозначаемый как. Аргументы связаны с предикатом действия в виде следующей предикатно-аргументной структуры: , что позволяет ассоциировать предикат действия с его аргументами «» и «». После извлечения событий из текста и их анализа выбираются наиболее релевантные события (т.е. события, отражающие наилучшим образом содержание входного/исходного текста) для формирования реферата. Такой подход требует только компонентов предварительной обработки и извлечения событий. Так как предложенный подход суммаризации не зависит от языка, то он является мультиязычным (с учетом доработки для особенностей каждого языка).
В отличие от известных систем в настоящем изобретении происходит объединение предикатно-аргументных структур, характеризующих события в тексте. Этот этап авторы настоящего изобретения называют обогащением событий. В указанных выше документах уровня техники не упоминается такое обогащение событий для получения реферата из одного текста, состоящего из нескольких предложений.
С учетом вышесказанного технический результат, достигаемый при использовании настоящего изобретения, заключается в повышении эффективности суммаризации текста на основе анализа предикатно-аргументных структур каждого предложения в тексте.
Согласно первому аспекту настоящего изобретения предложен способ суммаризации текста, который выполняют с использованием одного или более процессоров. Сначала выбирают текст, подлежащий суммаризации. Далее осуществляют предварительную обработку упомянутого текста, направленную на получение первоначальной предикатно-аргументной структуры каждого предложения в упомянутом тексте, которая состоит из аргументов и предиката действия, выражающего отношение между аргументами. При этом аргументы охарактеризованы именными группами, каждая из которых содержит главное слово и необязательно содержит одно или более дополнительных слов, синтаксически связанных с главным словом, а предикат действия охарактеризован глаголом или глагольной группой. Затем находят и объединяют предикатно-аргументные структуры с совпадающими предикатами действия и аргументами, охарактеризованными именными группами, у которых главные слова совпадают или связаны соотношением кореферентности. После этого составляют первоначальный список событий, используя объединенные предикатно-аргументные структуры, причем каждое событие соответствует одной из объединенных предикатно-аргументных структур. Первоначальный список событий впоследствии ранжируют для формирования ранжированного списка событий. Основное событие идентифицируют на основании ранжированного списка событий и первоначального списка событий. В заключение, составляют реферат на основе первоначального и ранжированного списков событий, причем основное событие указывается в начале реферата.
В одном варианте осуществления этап осуществления предварительной обработки упомянутого текста выполняют путем:
- разбиения упомянутого текста на заданные участки текста;
- нормализации заданных участков текста;
- выделения одного или более предложений в упомянутом тексте на основании нормализованных участков текста;
- осуществления синтаксического анализа каждого из выделенных предложений в упомянутом тексте; и
- осуществления семантической разметки в отношении каждого предложения, причем результатом упомянутой семантической разметки является упомянутая предикатно-аргументная структура для каждого предложения в упомянутом тексте.
Каждый заданный участок текста каждого предложения может представлять собой слово или последовательность слов. Упомянутая нормализация заданных участков текста может быть основана на по меньшей мере одном из подходов стеммирования и лемматизации. Упомянутый синтаксический анализ каждого из выделенных предложений в упомянутом тексте может быть осуществлен на основе грамматики зависимостей.
В одном варианте осуществления этап выбора текста осуществляют с помощью тактильного ввода или голосовой команды. При этом тактильный ввод можно осуществлять посредством графического пользовательского интерфейса, реализуемого посредством упомянутого одного или более процессоров и состоящего из по меньшей мере одной кнопки выбора текста.
В одном варианте осуществления этап ранжирования первоначального списка событий осуществляют с помощью графового алгоритма.
<Argf, Action, {Argi}>
i
i
В одном варианте осуществления каждое событие из первоначального списка событий и ранжированного списка событий представляют в виде: , где Arg, i=0, 1, 2, 3,... - ргументы, Action - предикат действия, выражающий отношение между аргументами, f=argmin (0, 1, 2, 3,...) - минимальный индекс среди всех аргументов Arg.
В одном варианте осуществления используется текст только одного документа. При этом текст может представлять собой новость или электронное письмо. Кроме того, текст может состоять из слов разных языков.
Согласно второму аспекту настоящего изобретения предложено устройство суммаризации текста, содержащее по меньшей мере один процессор и память, соединенную с упомянутым по меньшей мере одним процессором. Память содержит машиноисполняемые инструкции, которые при исполнении упомянутым по меньшей мере одним процессором обеспечивают выполнение упомянутым по меньшей мере одним процессором этапов способа согласно первому аспекту настоящего изобретения.
Устройство согласно второму аспекту настоящего изобретения может быть выполнено в виде карманного персонального компьютера (КПК), смартфона или умных часов.
Согласно третьему аспекту настоящего изобретения предложено другое устройство суммаризации текста, содержащее модуль предварительной обработки, модуль извлечения событий и модуль составления реферата.
Модуль предварительной обработки выполнен с возможностью выбора текста, подлежащего суммаризации, и осуществления предварительной обработки упомянутого текста, направленной на получение первоначальной предикатно-аргументной структуры каждого предложения в упомянутом тексте. Первоначальная предикатно-аргументная структура каждого предложения состоит из аргументов и предиката действия, выражающего отношение между аргументами. Аргументы охарактеризованы именными группами, каждая из которых содержит главное слово и необязательно содержит одно или более дополнительных слов, синтаксически связанных с главным словом, а предикат действия охарактеризован глаголом или глагольной группой.
Модуль извлечения событий выполнен с возможностью:
- нахождения и объединения предикатно-аргументных структур с совпадающими предикатами действия и аргументами, охарактеризованными именными группами, у которых главные слова совпадают или связаны соотношением кореферентности;
- составления первоначального списка событий, используя объединенные предикатно-аргументные структуры, причем каждое событие соответствует одной из объединенных предикатно-аргументных структур;
- ранжирования первоначального списка событий для формирования ранжированного списка событий; и
- идентификации основного события на основании ранжированного списка событий и первоначального списка событий.
Модуль составления реферата выполнен с возможностью составления реферата для упомянутого текста на основе первоначального и ранжированного списков событий, причем основное событие указывается в начале реферата.
Согласно четвертому аспекту настоящего изобретения предложен машиночитаемый носитель информации, на котором хранятся машиноисполняемые инструкции, которые при их исполнении по меньшей мере одним процессором обеспечивают выполнение упомянутым по меньшей мере одним процессором этапов способа согласно первому аспекту настоящего изобретения.
Другие признаки и преимущества настоящего изобретения будут очевидны после прочтения нижеследующего подробного описания и просмотра сопроводительных чертежей.
Краткое описание чертежей
Сущность настоящего изобретения поясняется ниже со ссылкой на сопроводительные чертежи, на которых:
Фиг. 1 иллюстрирует блок-схему способа суммаризации текста в соответствии с примерным вариантом осуществления настоящего изобретения;
Фиг. 2 иллюстрирует примеры подэтапов предварительной обработки текста, а также выполняющие их модули;
Фиг. 3 показывает блок-схему алгоритма обогащения событий;
Фиг. 4 представляет собой таблицу с компонентами обработки текста, используемыми в способе с Фиг. 3;
Фиг. 5 представляет собой таблицу с информацией, собираемой о событиях в тексте;
Фиг. 6 показывает условия равенства для обогащения событий;
Фиг. 7 иллюстрирует идентификацию главного события;
Фиг. 8 иллюстрирует методику построения графа;
Фиг. 9 иллюстрирует блок-схему устройства суммаризации текста в соответствии с примерным вариантом осуществления настоящего изобретения;
Фиг. 10 иллюстрирует вариант осуществления устройства суммаризации текста, используемого для отбора контента;
Фиг. 11 иллюстрирует вариант осуществления устройства суммаризации текста, используемого для ответа на электронное письмо;
Фиг. 12 иллюстрирует вариант осуществления устройства суммаризации звукового контента;
Фиг. 13 иллюстрирует вариант осуществления устройства суммаризации текста, применяемого в отношении смс-сообщений.
Осуществление изобретения
Различные варианты осуществления настоящего изобретения описаны далее подробнее со ссылкой на сопроводительные чертежи. Однако настоящее изобретение может быть реализовано во многих других формах и не должно пониматься как ограниченное какой-либо конкретной структурой или функцией, представленной в нижеследующем описании. В отличие от этого, эти варианты осуществления предоставлены для того, чтобы сделать описание настоящего изобретения подробным и полным. Исходя из настоящего описания, специалистам в данной области техники будет очевидно, что объем настоящего изобретения охватывает любой вариант осуществления настоящего изобретения, который раскрыт в данном документе, вне зависимости от того, реализован ли этот вариант осуществления независимо или совместно с любым другим вариантом осуществления настоящего изобретения. Например, способ и устройство, раскрытые в данном документе, могут быть реализованы на практике посредством использования любого числа вариантов осуществления, описанных в данном документе. Кроме того, должно быть понятно, что любой вариант осуществления настоящего изобретения может быть реализован с использованием одного или более элементов, представленных в приложенной формуле изобретения.
Слово «примерный» используется в данном документе в значении «используемый в качестве примера или иллюстрации». Любой вариант осуществления, описанный здесь как «примерный», необязательно должен восприниматься как предпочтительный или имеющий преимущество над другими вариантами осуществления.
На Фиг. 1 показана блок-схема способа 100 суммаризации текста в соответствии с примерным вариантом осуществления настоящего изобретения. Как показано, способ 100 состоит из этапов выбора текста (S102), предварительной обработки (S104), извлечения событий (S106) и составления реферата (S108). Каждый из этапов S102-S108 будет описан далее более подробно.
Как будет очевидно специалистам в данной области техники, начальный этап S102, т.е. этап выбора текста, может быть выполнен с помощью тактильного ввода или голосовой команды. Например, тактильный ввод может быть реализован посредством графического пользовательского интерфейса, отображаемого на сенсорном экране мобильного устройства, такого как мобильный телефон, планшетный или переносной компьютер. При этом графический пользовательский интерфейс может содержать по меньшей мере одну кнопку выбора текста, в отношении которого необходимо выполнить способ 100 суммаризации. Что касается голосовой команды, то она может быть введена упомянутое мобильное устройство через встроенный или внешний микрофон для выполнения способа 100 суммаризации необходимого текста.
Этап S104, т.е. этап предварительной обработки выбранного текста, направлен на получение первоначальной предикатно-аргументной структуры каждого предложения в упомянутом тексте, которая состоит из аргументов и предиката действия, выражающего отношение между аргументами. По сути, одна предикатно-аргументная структура характеризует одно событие, упоминаемое в тексте (в частности, в одном предложении из упомянутого текста). Следует отметить, что термины «предикатно-аргументная структура», «аргумент» и «предикат действия» являются широко известными в данной области техники, вследствие чего их подробное описание будет опущено. Необходимо напомнить, что аргументы характеризуются именными группами, каждая из которых содержит главное слово и необязательно содержит одно или более дополнительных слов, синтаксически связанных с главным словом. Как хорошо известно в лингвистике, главные и дополнительные слова именных групп могут быть любыми частями речи, за исключением глагола. Глагол или глагольная группа характеризует предикат действия, при этом глагольная группа представляет собой комбинацию глагола и по меньшей мере одной именной группы, идущей после него в предложении.
В зависимости от необходимости этап S104 может состоять из различных подэтапов. В одном варианте осуществления он включает в себя: разбиение упомянутого (выбранного для суммаризации) текста на заданные участки текста (токенизация); нормализацию заданных участков текста; выделение одного или более предложений в упомянутом тексте на основании нормализованных участков текста; синтаксический анализ каждого из выделенных предложений в упомянутом тексте; и осуществление семантической разметки в отношении каждого предложения. Как было указано ранее, результатом этапа S104 является упомянутая предикатно-аргументная структура для каждого предложения в упомянутом тексте. Примеры возможных подэтапов предварительной обработки текста, а также выполняющие их модули, изображены на Фиг. 2. И вновь следует отметить, что указанные подэтапы являются общеизвестными в данной области техники, вследствие чего их подробное описание будет опущено. Специалист в данной области техники без труда сможет реализовать каждый из указанных подэтапов для надлежащей предварительной обработки выбранного текста.
На этапе S106 происходит извлечение событий. Для этого сначала находят и объединяют первоначальные предикатно-аргументные структуры с совпадающими предикатами действия и аргументами, охарактеризованными именными группами, у которых главные слова совпадают или связаны соотношением кореферентности. Такое объединение авторы настоящего изобретения называют обогащением событий. Далее составляют первоначальный список событий, используя объединенные предикатно-аргументные структуры. После этого ранжируют первоначальный список событий для формирования ранжированного списка событий. Ранжированный список событий используется вместе с первоначальным списком событий для идентификации основного события в тексте, которое должно быть указано первым в реферате. Каждый из упомянутых подэтапов этапа S106 будет описан далее более подробно.
[ʺObamaʺ, ʺMr Obamaʺ, ʺBarack Obamaʺ]
<ʺdoctor Phamʺ, ʺnurse Nina Phamʺ>
Следует отметить, что упомянутое обогащение событий, по сути, представляет собой обогащение действий и аргументов, которые характеризуют сами события. Аргумент зависит от действия, т.е. все (кроме действия) может быть упомянуто внутри документа несколько раз. Иногда эти упоминания повторяются, например: в политических текстах. В других случаях упоминания могут пересекаться: . В этом случае ориентируются на главное существительное и обобщают упоминания этого существительного. Разница между обобщением и обогащением состоит в том, что здесь обобщение представляет собой более общую сущность, а обогащение представляет собой добавление новой информации.
ʺmaleʺ
ʺfemaleʺ
Согласно наблюдениям авторов в большинстве случаев кореферентность аргументов возникает при упоминании людей или организаций. Увязка местоимений с существительным при упоминании людей или организаций в виде «он», «она», «оно» и т.д. может быть при условии его одноразового упоминания в начале предложения/новости. Поэтому достаточно извлечь именные группы из аргументов в предикатно-аргументной структуре текста и проанализировать их главные существительные на предмет их типа. Если множество гиперонимов главного существительного содержит тип «person» (одушевленная персона), то необходимо рассматривать такую именную группу, как именованную сущность с типом «person». В то же время, если гипоним содержит понятие  (мужской) или (женский), то присваивается соответствующий пол для именной сущности.
Nq
Nq=2
Nina Pham, или неодушевленных сущностей - стол, стул)
Предложенный алгоритм обогащения событий представлен на Фиг. 3. Начальные строки 2-7 описывают этапы построения и обновления очереди предложений в тексте. Длина очереди задается заранее (в своих экспериментах авторы устанавливали ). В строке 9 проверяют, связаны ли два аргумента (т.е. главные слова в двух именных группах) соотношением кореферентности. Для этой цели адаптируют задачу анализа кореферентности так, чтобы обеспечивался высокий уровень точности обогащения сущностей (т.е. именованных сущностей - . Для адаптации мотивирующими соображениями являются (а) эвристика ʺone sense per discourseʺ (см. D. Yarowsky, Unsupervised word sense disambiguation rivaling supervised methods, Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, Cambridge, Massachusetts, USA, June, 1995; статья доступна по адресу: http://www.aclweb.org/anthology/P95-1026); и (б) необходимость установления кореферентных связей только для тех сущностей текста, которые являются аргументами событий. Другими словами, можно извлекать кореферентные связи с высокой точностью без потери полноты при обогащении событий.
ʺvesselsʺ
ʺboatʺ
ʺSouth and North Koreaʺ
ʺNorth Koreaʺ
Сначала анализируют главное (единственное) существительное в именной группе каждого аргумента. Если главного существительного не обнаружено и отсутствует кореферентность, то считают, что такие именные группы не могут быть упоминанием одной сущности. Другими словами, если нет существительного перед действием, значит, нельзя сказать, что «он», «она», «оно» это действие совершает. В противном случае, извлекают род и число главного существительного, как изображено на Фиг. 4. Эти параметры используют для проверки, могут ли главные существительные быть связаны соотношением кореферентности. Например, чтобы связать упоминания человека с характеризующим его местоимением, таким как «он», «она», необходимо учитывать его пол/род. Также требуется учитывать единственное/множественное число синонимов, например в случаях (мн. ч.) и (ед. ч.), (мн. ч.) и (ед. ч.). Также осуществляют проверку, является ли сущность местоимением. В этом случае предложенный алгоритм старается найти предыдущую (идущую до текущей в тексте) именную группу в очереди предложений (так необходимо для точности, поскольку последующие именные группы могут быть менее релевантными). Если ближайшая предыдущая именная группа также является местоимением, то алгоритм не обобщает сущности.
[Nurse Nina Pham], 33, [became] [infected] [while treating the first Ebola patient Eric Duncan]ʺ
ʺDirector of the Disease Center apologized that [a health care worker] [became] [infected] [while helping Ebola patient]ʺ
<Arg0, Action, {Argi}>
Argi
Далее показан пример обогащения событий. События в тексте могут повторяться, хотя их аргументы в повторениях могут быть перефразированы. Например, одно из предложений может содержать событие ʺ, тогда как другое предложение, связанное с этим событием , содержится в конце документа. В этом случае необходимо объединить информацию (аргументы, предикаты действия) из обоих упоминаний повторившегося события. События представляют в виде: , при этом  обозначают дополнительные аргументы (т.е. все те аргументы, которые не являются первыми). Примеры извлеченных событий проиллюстрированы на Фиг. 5 справа. Для объединения событий проверяют совпадение предикатов действий и аргументов, характеризующих события, как показано на Фиг. 6, путем приведения глаголов в нормальную форму. После этого проверяют совпадения стеммированной формы (Фиг. 6) последнего слова в каждой глагольной группе. При совпадении упомянутых стеммированных форм глагольные группы считаются совпадающими (в том числе, глагольные группы событий).
ʺwhile treating Xʺ
ʺwhile helping Xʺ
ʺbeʺ
ʺamʺ
ʺwasʺ
ʺan airplane arrived yesterdayʺ
ʺan airplane arrived in 2001ʺ
ʺNina Pham treated the first Ebola patientʺ и ʺPham treated Thomas Eric Duncanʺ
Arg1
Pham
Arg0,
the first Ebola patient
Thomas Eric Duncan
Arg1
ʺNina Pham treated Duncanʺ
ʺthe nurse treated Duncanʺ
Arg0
Авторы настоящего изобретения также добавляют еще исключение для случая обстоятельственного придаточного предложения (adverbial clause), такого как или . События считают равными, если их предикат действия не является производной формой глагола  (,  и т.д.), устанавливающего отношение принадлежности между сущностями события. Глагол «to be» исключается, поскольку при несовпадении событий/явления вещи (например, «this is a table», «dog is an animal») этот глагол мешает правильно понять, какое именно действие совершается. Также авторы рекомендуют добавлять условие, что аргументы времени должны ссылаться на одинаковое время. Из-за этого условия событие типа не является равным событию . Установлено, что разные упоминания события могут возникать из-за разных аргументов. Например, в событиях не совпадает аргумент .  здесь является главным аргументом он совпадает для обоих событий, а  и  являются дополнительными аргументами и они не совпадают. Похожим образом, в событиях  и не совпадает аргумент . Поэтому для отождествления событий достаточно, чтобы только один из аргументов этих событий совпал.
После этого необходимо выполнить обогащение события путем объединения первоначальных предикатно-аргументных структур, характеризующих события, для получения одного окончательного события. Например, если совпал предикат действия и по меньшей мере один аргумент (а также при частичном совпадении остальных аргументов) в двух событиях, то такие события считаются одинаковыми, и поэтому они объединяются в одно событие.
Для последующего составления реферата (S108) необходимо выбрать и использовать наиболее перспективные события с учетом уже обогащенных событий. События в выбранном тексте имеют тенденцию повторяться и влиять друг на друга в повествовательной цепочке согласно статье N. Chambers and D. Jurafsky, Unsupervised Learning of Narrative Event Chains, In Proceedings of ACL, 2008. Зависимости между событиями должны быть отражены в реферате. Для моделирования зависимостей между событиями используют графы и используют эту модель для отбора подходящих событий в реферате. После извлечения событий находят основное событие, строя граф событий и используя построенный граф для ранжирования событий. Этот этап проиллюстрирован на Фиг. 7, и он критичен для отбора события, описывающего весь текст целиком. Так как логично начать реферат с этого события, авторы называют его основным. Основное событие зачастую может повторяться в реферате. В настоящем изобретении используется первое извлеченное событие в качестве основного. Однако это не должно рассматриваться как ограничение настоящего изобретения.
На Фиг. 7 левая колонка - ранжирование по порядку встречи, т.е. порядку, в котором события встретились (проявили себя, обнаружились) в тексте (не следует путать с количеством повторений или частотой повторений сверху-вниз). Другими словами, чем выше находится событие, тем оно встречается раньше в тексте. Правая колонка - ранжирование по важности снизу-вверх: чем выше находится событие, тем оно важнее. Отсюда следует вывод, что E1 - основное событие, поскольку оно по степени важности находится вверху, а по порядку встречи в начале текста. Структура колонок приведена только в качестве примера и никак не ограничивает настоящее изобретение.
Arg0n
Arg1n
Eventn
n
V
(
vertex
E
WWW
V
E
G=(V, E)
Vi
in(Vi)
out(Vi)
Далее выполняется ранжирование событий. Подход авторов настоящего изобретения к ранжированию событий состоит в организации событий в граф и дальнейшем применении графового алгоритма. Методика построения графа изображена на Фиг. 8, на которой  - первые аргументы событий,  - вторые аргументы событий,  - события, при этом =1, 2, 3,... Вершины графа от английского слова«»- вершина) представляют собой точки в круге на графе и являются событиями или аргументами событий. Ребра  - это ребра (черты), соединяющие вершины V между собой, т.е. они в данном случае соединяют события с их аргументами. Основываясь на допущении, что события могут повлиять друг на друга, добавляют дополнительные ребра для их соединения. В данном случае каждое ребро соединяет вершины в двух направлениях. После построения ребер вычисляют наиболее перспективные (наиболее важные) вершины событий. Для этой цели применяют «модель случайного блуждания» (random surfing model), используя алгоритм PageRank (S. Brin and L. Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, In , 1998). Пусть ,  обозначают множество вершин и ребер между вершинами соответственно; пусть  обозначает направленный граф. Для каждой вершины  определим  и  как множество входящих и выходящих ребер соответственно. Оценку PageRank для вершины получают, используя следующую формулу:
Так же, как и в вышеуказанной статье S. Brin и L. Page, устанавливают коэффициент d в 0.85, где d - damping factor - оценочная величина, позволяющая установить веса более 0, близкая к 1 - исключительная стартовая величина для примерной оценки, например, отдельной страницы текста. Эта формула рассчитывается в несколько итераций (для повышения важности). Кроме того, в вышеприведенной формуле Vk - индекс по всем вершинам (количество всех вершин), in(Vi), out(Vi) - в графе у каждой вершины есть входящие и выходящие ребра, т.е. в формуле используется количество входящих/или выходящих ребер.
Когда события отсортированы согласно их оценке PageRank, их можно снова переупорядочить для соблюдения первоначального порядка их появления. Последующее переупорядочивание необходимо для соблюдения целостности первоначального текста с уже примененной (посредством описанных выше этапов) суммаризацией, т.е. отсекается часть неактуальной в данный момент информации. Согласно наблюдениям авторов настоящего изобретения хороший реферат сохраняет первоначальный порядок событий, даже если события оказываются разъединены по теме. Поэтому сохраняется первоначальный порядок событий входного текста и события сортируются в соответствии с их первоначальным порядком.
ʺMary brought apples. John ate them yesterdayʺ
ʺMary brought apples. Yesterday, they were eaten by Johnʺ
<Argf; Action; Argi>
f=argmin (0, 1, 2)
Argi
ArgTmp
ʺ[ArgTmp:Yesterday] Pham became infectedʺ
ArgTmp
ʺPham became infected yesterdayʺ
ʺPham became yesterday infectedʺ
ArgTmp
Action
«became infected»
о
На последнем этапе S106 выполняется составление краткого изложения (т.е. реферата). Авторы настоящего изобретения заметили, что рефераты с пассивным залогом или с временными (описывающими время) аргументами в предложении оказываются менее связанными. Например, реферат вида  является ясным, складным, звучным, в то время как реферат вида  читается намного сложнее. Поэтому, чтобы сгенерировать связанный реферат, необходимо модифицировать порядок аргументов в каждом событии. С этой целью при генерации краткого изложения следует придерживаться порядка , в котором обозначает минимальный индекс (самый первый из аргументов) среди всех аргументов . Оставшиеся аргументы добавляют в первоначальном порядке. Иногда временной аргумент  возникает в начале события, как в случае предложения . Чтобы улучшить ясность, необходимо переставить  в событии. Установлено, что действие и его последующий аргумент могут быть тесно связаны, если аргумент состоит из небольшого количества слов. Например, предложение является ясным, звучным, однако предложение читается плохо. Поэтому в этих случаях целесообразно поставить  после () и перед первым аргументом, имеющим бльшую длину.
Настоящее изобретение предпочтительно реализовывать в персональном цифровом помощнике (personal digit assistant, PDA), таком как смартфон. На Фиг. 9 проиллюстрирована упрощенная блок-схема устройства 900 суммаризации текста в соответствии с примерным вариантом осуществления настоящего изобретения. Как показано, устройство 900 содержит три основных модуля: модуль 902 предварительной обработки, модуль 904 извлечения событий и модуль 906 составления реферата. Каждый из модулей 902-906 выполняет соответствующие этапы 102-108 способа 100, показанного на Фиг. 1. В частности, модуль 902 выполнен с возможностью осуществления этапов S102 и S104 и, если потребуется, может быть реализован в виде комбинации модулей, показанных на Фиг. 2. Модуль 904 выполнен с возможностью осуществления этапа S106. Модуль 906 выполнен с возможностью осуществления этапа S108.
Фиг. 10 изображает возможную прикладную программу, с помощью которой пользователь печатает текст про Сингапур и решает, что ему нужно добавить дополнительную информацию из Интернета. Он нажимает кнопку «W» для поиска в Википедии, после чего устройство 900 находит релевантные страницы про Сингапур. Пользователь выбирает интересную часть текста, нажимает кнопку «Cite» (цитировать), и затем устройство 900 добавляет краткое изложение в электронное письмо. В этом сценарии пользователю нужно только 2 клика и единственное движение пальца, чтобы напечатать относительно большой текст. Похожим образом пользователь может добавить контент мультимедиа. Поэтому создание контента с помощью устройства 900 приводит к ускорению набора текста. Этот сценарий также применим к многочисленным приложениям набора текста, например, для ведения блогов или общения в чатах.
Другой возможный похожий сценарий изображен на Фиг. 11, на которой квазиреферирование используется для выделения важных предложений в электронном письме. Когда пользователь решает ответить на письмо, выделенные посредством способа 100 суммаризации, предложения автоматически цитируются в качестве возможных аргументов, на которые пользователю нужно/можно/требуется ответить/прокомментировать, т.е. использовать итог работы способа 100 суммаризации (см. на Фиг. 10 справа поле для ввода комментария/ответа). В этом сценарии пользователю не нужно копировать важные процитированные предложения, поэтому набор текста значительно ускоряется.
Альтернативный сценарий приведен на Фиг. 12, на которой часофон (вариант осуществления устройства 900) генерирует аудиорефератыновостей. Пользователь при этом может управлять автомобилем или готовить еду, из-за чего обе его руки заняты. Для выбора интересных новостей он может использовать голосовые команды, позволяющие запросить короткий реферат новостных категорий или краткое изложение новостей в определенной категории. Если реферат новостей слишком длинный или слишком короткий, он может использовать голосовые команды для изменения длины реферата. Для пользователя появляется возможность выбирать темы новостей, их длину и содержание без использования рук.
Другой сценарий на Фиг. 13 показывает суммаризацию смс-сообщений на устройстве 900, также реализованном в виде часофона. Если пользователь с кем-то разговаривает, находится на деловой встрече или едет в автобусе, ему может быть неудобно использовать смартфон. Однако он по-прежнему может видеть краткое изложение наиболее важных смс-сообщений или электронных писем. Этот сценарий также применим к электронным очкам или устройствам для отображения информации в автомобиле. Для пользователя появляется возможность получить быстрый доступ к важной информации без использования рук.
С точки зрения удобства использования, описанный способ суммаризации имеет следующие преимущества. Во-первых, становится возможным генерировать рефераты на нескольких языках из событий посредством добавления различных синтаксических/семантических парсеров (средств синтаксического разбора и анализа) для каждого языка, что может быть реализовано дополнительным (но необязательным) модулем. Во-вторых, так как извлекаются события, даже одного текста достаточно для краткого изложения или для нахождения важных событий в исходном тексте. В-третьих, можно изменять рефераты в зависимости от интересов пользователя, таким образом экономя время пользователя (например, при выделении тематик, более интересных пользователю, используя тематическое моделирование, выполняемое дополнительным (но необязательным) модулем).
Применение изобретения
Предложенный авторами способ суммаризации может работать на каждом устройстве, имеющем процессор с частотой более 1 ГГц, оперативной памятью не менее 15 Мб и размером жесткого диска более 50 Мб. Алгоритм возможно реализовать в автомобиле, часофоне, планшете или телевизоре.
Составление реферата различных документов осуществляется, например, путем объединения этих нескольких документов, последовательно друг за другом. Далее вышеописанный способ суммаризации просто применяется в отношении объединенного текста.
Различные примерные модули, описанные в сочетании с раскрытыми в данном документе вариантами осуществления, могут быть реализованы или выполнены с помощью процессора общего назначения, процессора специального назначения, специализированной интегральной схемой (ASIC), программируемой пользователем вентильной матрицы (FPGA) или другого программируемого логического устройства, схемы на дискретных компонентах или транзисторной логики, дискретных компонентов аппаратного обеспечения или любой их комбинации, выполненных с возможностью осуществлять описанные в данном документе этапы.
Каждый из упомянутых выше процессоров может быть микропроцессором или, в качестве альтернативы, может быть любым традиционным процессором, контроллером, микроконтроллером или машиной состояний. Каждый процессор может быть также реализован в виде комбинации вычислительных устройств, например комбинации процессора общего назначения и микропроцессора, множества микропроцессоров, одного или более микропроцессоров или в виде любой другой подобной конфигурации.
Следует также отметить, что множество различных модулей устройства и этапов способа, описанные в сочетании с вариантами осуществления, раскрытыми в данном документе, могут быть реализованы в виде электронного аппаратного обеспечения, компьютерного программного обеспечения или их комбинации. Чтобы ясно проиллюстрировать эту взаимозаменяемость аппаратного и программного обеспечения, различные примерные модули и этапы были описаны выше, как правило, на основании их функциональных возможностей. Выбор реализации таких функциональных возможностей в виде аппаратного или программного обеспечения зависит от конкретного применения и ограничений конструкции, накладываемых на всю систему. Специалисты в данной области техники могут реализовать описанные функциональные возможности различными способами для каждого конкретного применения, но такие решения по реализации не должны истолковываться как выходящие за рамки объема охраны настоящего изобретения.
В одном или более примерных вариантах осуществления этапы способа, описанные в данном документе, могут быть реализованы в аппаратном обеспечении, программном обеспечении, аппаратно-программном обеспечении или любой их комбинации. Будучи реализованными в программном обеспечении, упомянутые функции могут храниться на или передаваться в виде одной или более инструкций или кода на машиночитаемом носителе. Машиночитаемые носители включают в себя любой носитель информации, который обеспечивает перенос компьютерной программы из одного места в другое. Носитель информации может быть любым доступным носителем, доступ к которому осуществляется посредством компьютера. В качестве примера, но не ограничения, такие машиночитаемые носители могут представлять собой RAM, ROM, EEPROM, CD-ROM или другой накопитель на оптических дисках, накопитель на магнитных дисках или другие магнитные запоминающие устройства, или любой другой носитель информации, который может использоваться для переноса или хранения требуемого программного кода в виде инструкций или структур данных и доступ к которому можно осуществлять с помощью компьютера. Кроме того, если программное обеспечение передается из веб-сайта, сервера или другого удаленного источника с использованием коаксиальных кабелей, оптоволоконных кабелей, витой пары, цифровой абонентской линии связи (DSL) или с использованием беспроводных технологий, таких как инфракрасные, радио- и микроволны, то такие проводные и беспроводные средства подпадают под определение носителя. Термин диск, используемый в данном документе, включает в себя компакт-диск (CD), лазерные диски, оптические диски, универсальные цифровые диски (DVD), флоппи-диски и диски blu-ray. Комбинации вышеозвученных носителей информации должны также попадать в объем охраны настоящего изобретения.
Хотя в настоящем описании показаны примерные варианты осуществления изобретения, следует понимать, что различные изменения и модификации могут быть выполнены, не выходя за рамки объема охраны настоящего изобретения, определяемого прилагаемой формулой изобретения. Функции, этапы и/или действия, упоминаемые в пунктах формулы изобретения, характеризующих способ, в соответствии с вариантами осуществления настоящего изобретения, описанными в данном документе, необязательно должны выполняться в каком-то конкретном порядке, если не отмечено или не оговорено иное. Более того, упоминание компонентов устройства в единственном числе не исключает множества таких элементов, если в явном виде не указано иное.