Исследование и реализация методов многоязыкового автоматического резюмирования Pavlovic Boris, 527 Moscow, 2012

Содержание Что? Где? Когда? Тестирование Подходы к резюмированию Результаты Ссылки

Что? Где? Когда? Определение Автоматическое резюмирование (automatic summarization) - это процесс получения сокращенной версии текста при помощи программы. Полученный текст: – Во много раз меньше (например 100 слов) – Содержит основные положения исходного документа

Что? Где? Когда? Причины возникновения Экспоненциальное увеличение количества документов Размытость информации Информационное перекрытые Необходимость Эффективной обработки Ограниченные возможности человека

Что? Где? Когда? Используется в: Поисковых системах – Сужение области поиска – Сниппеты (snippet) Новости Аннотации

Что? Где? Когда? Сниппет пример 1

Что? Где? Когда? Сниппет пример 2

Что? Где? Когда? Что такое сниппет? Это часть исходного текста, содержащая слова запроса пользователя Определяет контекст в котором найдены слова

Что? Где? Когда? Используется в: Поисковых системах – Сужение области поиска – Сниппеты (snippet) Новости Аннотации

Что? Где? Когда? Новости Объединение нескольких новостей из разных источников в одну (новость)

Что? Где? Когда? Используется в: Поисковых системах – Сужение области поиска – Сниппеты (snippet) Новости Аннотации

Что? Где? Когда? Генерация рефератов в Microsoft Word

Что? Где? Когда? Классификация типов резюме по: Содержанию: – Информативные – Индикативные – Критические Количеству входных документов Интересующей информаций: – Относительно запроса пользователя – Равномерно распределенная Способу генерации: – Summary extraction – Summary generation

Тестирование Сложности Тестирование в ручную одной системы занимает >9k времени (~3k h) Автоматическое тестирование осложняется: – Не существует общего алгоритма оценки – Разные люди создают разные резюме – Отсутствие размеченных документов

Тестирование Общий подход Набор пар документов (исходный текст, резюме) Расстояния между сгенерированным текстом и вручную сделанным резюме

Тестирование Материалы DUC (Document Understanding Conferences) – – Для общих резюме (без запроса пользователя) подходят DUC 2001 и DUC 2004 – В архиве нету исходных текстов? – Да их нужно отдельно запрашивать. Для DUC 2001 нужно зайти на страницу nlpir.nist.gov/projects/duc/data/2001_data.html

Тестирование Содержание архива DUC 2001 data/test – /docs/ - содержит в себе директории(кластеры) d\d\d\w в которых находятся XML файлы содержащие собственно исходные тексты – /orginal.summaries/ и /duplicated.summaries/ содержат папки содержащие резюме. Для каждого кластера есть 3 папки в каждой из которых есть 5 файлов 50, 100, 200, 400 словное резюме сразу по все документам perdocs – xml файл содержащий резюме для каждого из текстов в кластере data/training – аналогично

Тестирование Проблемы с DUC 2001 и python xml Perdocs не имеет root элемента Часто опечатки в perdocs файлах (неверно указанное имя файла к которому относится резюме) XML файлы часто содержат символ & – /&(?![\w\W\d]+;)/ -> /&/ Во всех FBI документах значения некоторых тегов не в кавычках

Тестирование Система тестирования ROUGE (Recall-Oriented Understudy for Gisting Evaluation) – – Perl скрипт оценивающий качество резюме, сравнивая его с вручную сделанными резюме – Есть несколько алгоритмов оценки

Тестирование Как работает ROUGE N-Grams – это подпоследовательность из n- элементов некоторой последовательности Пример – N=3 «Совсем скоро придется учить госы.» Совсем, скоро, придется скоро, придется, учить придется, учить, госы.

Тестирование Как работает ROUGE ROUGE-N – основывается на совпадении n- gram из полученной резюме и вручную созданных – n длина n-gram – Count match (gram n ) количество совместных n-gram в сгенерированном резюме и вручную созданных

Тестирование Как работает ROUGE Rouge-L: Longest Common Subsequence – Подпосл-сть Z = [z 1,z 2, …, z n ] посл-сти X = [x 1,x 2, x m ] [i 1,..,i n ] : j=1,k => x ij = z j Rouge-L: Пример (то как видит Rouge-2) С1 = police killed the gunman. - тестируемое C2 = police kill the gunman. C3 = the gunman kill police. – LSC(C1,C2) = ¾, LSC(C1,C3) = ½ – В целом лучше чем Rouge-2 который выдает в обоих случаях ½ – Но есть проблемы например С4 = «the gunman police killed» В случае Rouge-L оценка будет ½ при этом Rouge-2 дает оценку 1

Тестирование Как работает ROUGE Rouge-L: Longest Common Subsequence – Подпосл-сть Z = [z 1,z 2, …, z n ] посл-сти X = [x 1,x 2, x m ] [i 1,..,i n ] : j=1,k => x ij = z j Rouge-L: Пример (то как видит Rouge-L) С1 = police killed the gunman. - тестируемое C2 = police kill the gunman. C3 = the gunman kill police. – LSC(C1,C2) = ¾, LSC(C1,C3) = ½ – В целом лучше чем Rouge-2 который выдает в обоих случаях ½ – Но есть проблемы например С4 = «the gunman police killed» В случае Rouge-L оценка будет ½ при этом Rouge-2 дает оценку 1

Тестирование Как работает ROUGE Rouge-L: Longest Common Subsequence LSC U (r i,C) – r i – одно предложение модельного резюме, C все предложения из оцениваемого резюме. U – количество предложении, m – общее количество слов в модельном резюме Пример r1 = w 1 w 2 w 3 w 4 w 5, c1 = w 1 w 2 w 6 w 7 w 8 => общаяw 1 w 2 c2 = w 1 w 2 w 3 w 5 => общая w 1 w 3 w 5 – Общая подпоследовательность w 1 w 2 w 3 w 5 => LSC U (r i,C) = 4/5

Тестирование Как работает ROUGE Rouge-W: Weighted Longest Common Subsequence – Улучшение Rouge-L Пример X = [ABCDEFG] Y1 = [ABCDHIK] Y2 = [AHBKCID] – Rouge-L(X,Y1) == Rouge-L(X,Y2) – хотя интуитивно Y1 лучше Идея улучшения: – Запоминать самую длинную непрерывную последовательность – Ввести функцию веса f(x) : f(x+y) > f(x) + f(y), например f(x) = x 2

Тестирование Как работает ROUGE Rouge-W: немного программирования – For (i = 0; i

Тестирование Как работает ROUGE Rouge-W: результаты X = [ABCDEFG] Y1 = [ABCDHIK] Y2 = [AHBKCID] – Rouge-W(X,Y1) = – Rouge-W(X,Y2) = 0.286

Тестирование Как работает ROUGE Rouge-S: Skip-Bigram Co-Occurrence Statistics – Пример биграм с пропусками: «police killed the gunman» - (police killed, police the, police gunman, killed the, killed gunman, the gunman) – SKIP2(X,Y) – количество совпадающих skip-bigram – C(m,n) = m!/ ((m-n)!n!) – Из того, что могут возникнуть skip-bigram вида the the, of in следует ограничивать максимальное расстояние между словами

Тестирование Как работает ROUGE Rouge-SU: Extension of Rouge-S S1 = police killed the gunman. S5 = gunman the killed police. – В данном случае Rouge-S(S1,S5) = 0, хотя нам бы хотелось учитывать, когда предложения состоят из похожих слов и то когда они совсем разнные, поэтому можно учитывать также uni-gram добавить к числителю количество общих добавить к знаменателю количество uni-gram

Тестирование Rouge: Корреляция с ручным тестированием

Тестирование Как запустить Rouge? Вид конфигурационного файла: – –../rouge/text_extractor/systems –../rouge/text_extractor/models – – 0_2.html – 0_7.html – – 0_0.html – 0_1.html – 0_2.html – – …… – …………. –

Тестирование Как запустить Rouge? Формат резюме – – 0_0.html – – [0] De Beers' Venetia mine began production in 1992, and was the first newdiamond mine to open in South Africa in 25 years. – [1] Production wascurtailed for a while after opening when the De Beers' selling cartelimposed quotas on producers because of a flood of gems from Angola,and uncertainty about Russian exports. – [2] Last year the mines outputdoubled. – [3] About 70 percent of Ventia's diamonds are of gem quality, andannual production is expected to reach 500 million dollars. –

Тестирование Как запустить Rouge? Волшебная команда запускающая Rouge-SU* –./ROUGE pl -e data -f A -a -l 100 -x -s -m u text_extractor/settings.xml -e data – мозги rouge -a тестировать все системы -l 100 учитывать только первые 100 слов -x не считать Rouge-L -m использование стемминга u – использовать skip-bigrami при этом макс. Растояние между словами 4, а также добавить unigrami.

Подходы к резюмированию Классификация подходов: Способ выделения ключевых фраз, предложении Сортировка данных Упрощение предложении

Подходы к резюмированию Классификация методов выделения предложении (ключевых слов): С учителем Без учителя

Подходы к резюмированию Ранние методы (Luhn 1958, Edmundson 1969) Текст разбивается на предложения. Каждое предложение оценивается исходя из того, удовлетворяет ли оно некоторым признакам. Существует много разных признаков =)

Подходы к резюмированию Ранние методы (Luhn 1958, Edmundson 1969) Признак сue words – Пример: «В заключении», «Важно», «Результатом», «В данной работе»… – Если предложение содержит «cue words», то интуитивно понятно, что оно является важнее

Подходы к резюмированию Ранние методы (Luhn 1958, Edmundson 1969) Признак положение предложения – Начало текста более информативно – Очень сильный критерии – Часто используется в виде baseline

Подходы к резюмированию Ранние методы (Luhn 1958, Edmundson 1969) Признак корреляция с названием – Если предложение содержит части названия, то оно более важное

Подходы к резюмированию Ранние методы (Luhn 1958, Edmundson 1969) Признак «позитивные (негативные) ключевые слова» – примеры : лучше, хуже, более, менее..

Подходы к резюмированию Ранние методы (Luhn 1958, Edmundson 1969) Признак частота слов – Разбиваем текст на слова, считаем частоту каждого слова. Логично предположить, что предложения содержащие больше часто употребляемых слов имеют больший вес – Важный подход но не применяется напрямую, в виду того, что в тексте, часто встречаются слова паразиты и стоп-слова.

Подходы к резюмированию Ранние методы (Luhn 1958, Edmundson 1969) Метод td-idf частота слов – Вес больше у тех слов, которые часто встречаются в текущем документе, но редко в обучающем копрусе – Weight(w)= tf i,j *idf i, tf i,j - частот w в текущем документе Idf i = log(N/N with_w ) – логарифм отношения количества всех документов к документам содержащим наш термин

Подходы к резюмированию Ранние методы (Luhn 1958, Edmundson 1969) Метод основании на центрировании – Вычисление расстоянии между предложениями и выбор тех которые в среднем ближе – Для меры расстояния можно использовать метод bag of words (предложение представляется в виде вектора слова). Вычисляется косинус угла между векторами – a – Для каждого предложения посчитать среднее расстояние – Отсортировать и выбрать те у которых расстояние минимально

Подходы к резюмированию Ранние методы (Luhn 1958, Edmundson 1969) Метод симметричного резюмирования – Выделяем ключевые слова (заранее) – Для каждого предложения считаем количество ссылок на другие предложения Ссылка – это одинаковое ключевое слово в обоих предложениях – Отбираем предложения у которых больше всего ссылок

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

Подходы к резюмированию Методы машинного обучения Дерево принятий решения – Атрибут (параметр функции) – Тестовые примеры(f (0, 0, 1), f (0, 1, 1), f (1, 1, 0), f (1, 1, 1)) – Нужно продолжить функцию на другие значения атрибутов

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

Подходы к резюмированию Методы машинного обучения Дерево принятия решений (вход. данные)

Подходы к резюмированию Методы машинного обучения Дерево принятия решений

Подходы к резюмированию Методы машинного обучения Наивный Байесовский классификатор – h - гипотеза «принадлежит ли данное предложение к резюме?» – D - набор признаков «предложение в самом начале?»

Подходы к резюмированию Методы машинного обучения Наивный Байесовский классификатор «Наивность» – Предположим, что признаки из D независимы, тогда p(D|h) = p(d1|h) * p(d2 | h) … * p(h) / p(D) – Если предположить что все гипотезы равновероятны, то p(h) можно опустить – p(D) = const => не влияет на счет

Подходы к резюмированию Методы машинного обучения Наивный Байесовский классификатор Итоговая формула: – Принадлежит ли предложение к резюме? argmax h p(d 1 |h)*p(d 2 |h)*…*p(d n |h)

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

Результаты Baseline first 100 ROUGE-SU* Average_R: first 100 ROUGE-SU* Average_P: first 100 ROUGE-SU* Average_F: first 30 ROUGE-SU* Average_R: first 30 ROUGE-SU* Average_P: first 30 ROUGE-SU* Average_F: