ݺߣ

ݺߣShare a Scribd company logo

Иванов. Автоматизация построения предметных указателей

•Download as PPTX, PDF•
•
С
Спецсеминар "Искусственный Интеллект" кафедры АЯ ВМК МГУ

осень 2015

1 of 25
Download to read offline
Автоматизация построения предметных указателей Иванов К. М. Научный руководитель: к.ф.-м.н. доцент Большакова Е.И.
1.Предметные указатели: структура и состав 2.Задачи построения предметного указателя 3.Извлечение и фильтрация термов: подходы и методы 4.Структурирование извлеченной информации 5.Оценка корректности построенного предметного указателя 2/25 Содержание
•Алфавитно-предметный указатель (back-of-the-book index) – ПУ подробный перечень обсуждаемых в документе терминов, понятий и объектов предметной области (ПО) текста, с указанием страниц, на которых они встречаются в тексте. •Структура предметного указателя: Сегменты, соответствующие буквам алфавита (идентификаторам) Строки сегмента, содержащие терм: термин или название объекта ПО •Виды строк: Строка с родовым понятием Строка с видовым понятием A — ASCII 205 … … Б бинарный файл 67-69 блок символов 110 — линейный 112 — прямоугольный 121, 167 — строчный 130 блок-схема 20-25, 170 … … П понятие — абстракции 45 — алгоритма 50, 80 — анализа 145 — атрибута объекта 156, 179 … … Предметный указатель 3/25
Особенности строк предметных указателей: •Диапазоны номеров страниц для отдельных понятий •Инверсии •Персоналии •Перекрестные ссылки Нет стандартов на структуру предметного указателя 4/25 Предметный указатель: особенности H height — of a binomial tree, 527-530 pr. — black-, 309 … … F flow, 709–714 — augmentation of, 716 — net, across a cut, 720 — value of, 710 flow conservation, 709–710 L Lester Randolph Ford, Jr., 432 N network — admissible, 749–750 — flow, see flow network … …
•ПУ, как правило, строят для: •Книг: монографий, научных пособий, энциклопедий и т.п. •Объемных научно-технических текстов: отчетов, статей •Сайтов •Трудоемкость построения ПУ. Основная сложность: •Выявление терминов, понятий и названий объектов ПО •Определение наиболее важных мест их употребления в тексте •Определение связей выявленных терминов и понятий •Близость к задаче построения онтологии ПО: •Не для коллекции текстов, а для одного текста •Этот текст – объемный 5/25 Задача построения предметного указателя
Автоматизация построения предметного указателя I.Извлечение из текста термов (терминов и названий объектов ПО) I.Формирование иерархической структуры предметного указателя и построение ссылок II.Редактирование полученного результата 6/25 Автоматически Вручную • Современные коммерческие редакторы, например, Microsoft Word, частично автоматизируют только этап II. • Научные исследования: автоматизации первого и второго этапов. Этапы построения:
1. Извлечение из текста термов-кандидатов, которые могут войти в предметный указатель, например: бинарный файл, линейный блок символов, ASCII 2. Фильтрация термов-кандидатов: отбор релевантных 3. Выявление связей термов: семантических, родо-видовых 4. Определение наиболее важных мест употребления термов в документе 5. Формирование иерархической структуры предметного указателя Подзадачи автоматизации 7/25 Этап I Этап II
•Методы извлечения термов-кандидатов базируются на: •Лингвистической информации, в виде шаблонов и правил •Статистической информации •Их комбинации, в том числе используется машинное обучение •Простой метод – Метод Сэлтона (Salton G. Syntactic approaches to automatic book indexing //Proceedings of the 26th annual meeting on Association for Computational Linguistics. – Association for Computational Linguistics, 1988. – С. 204-210.): •Определение частей речи слов исходного текста •Термы – биграммы слов, например, low-frequency terms •Мера TF.IDF для отбора термов-кандидатов 8/25 Задача извлечения термов: подходы
Мера TF.IDF •TF (term frequency — частота слова) — отношение числа вхождения некоторого терма t к общему количеству термов в документе d. 𝑡𝑓 𝑡, 𝑑 = 𝑛 𝑡 𝑁 𝑑 • В некоторых работах TF считается в абсолютном смысле, т.е. • IDF (inverse document frequency) — инверсия частоты, с которой некоторый терм t встречается в документах коллекции D. 𝑖𝑑𝑓 𝑡, 𝐷 = 𝑙𝑜𝑔 𝑁 𝐷 𝑑𝑓𝑡 • 𝑛 𝑡 – число вхождений терма в документе • 𝑁𝑡 – общее число термов в документе • 𝑁 𝐷– число документов в коллекции D • 𝑑𝑓𝑡– число документов коллекции D, в которые входит терм t • TF.IDF — вес некоторого терма t в документе d коллекции D. 𝒕𝒇. 𝒊𝒅𝒇 𝒕, 𝒅 = 𝒕𝒇 𝒕, 𝒅 ∗ 𝒊𝒅𝒇(𝒕, 𝑫)Величина TF.IDF возрастает • с увеличением числа вхождений термина в документ; • со снижением частоты термина во всей коллекции. 9/25 𝑡𝑓 𝑡, 𝑑 = 𝑛 𝑡
•Работает для текстов на английском и французском языках •Для извлечения термов-кандидатов используется: •Пакет YaTeA3, извлекающий из размеченного корпуса терминологические словосочетания (http://search.cpan.org/~thhamon/Lingua-YaTeA/lib/Lingua/YaTeA.pm) •Дополнительные условия, определяемые пользователем •Для ранжирования используются: •Общая частота появления терма-кандидата в тексте (TF) •Частота появления терма-кандидата в определенных частях документа, например заголовках •Другие параметры 10/25 Методы извлечения термов для предметного указателя: InDoc, 2006 Zargayouna H. Nazarenko A. et al. IndDoc: an aid for the back-of-the-book indexer //The Indexer. – 2006. – Т. 25. – №. 2. – С. 122-125.
• Для ранжирования выявленных термов-кандидатов используются показатели информативности и сочетаемости Csomai A., Mihalcea R. Investigations in Unsupervised Back-of-the-Book Indexing //FLAIRS Conference. – 2007. – С. 211-216. 11/25 Методы извлечения термов: Mihalcea R., 2007 • Задача извлечения термов рассматривается как задача извлечения ключевых слов. • Исследованы методы извлечения: •Метод N-грамм (N=1,…,4) •Метод поиска именных словосочетаний (noun phrase chunks) •Машинный классификатор для выявления именованных сущностей (supervised named entity recognition) •Эвристический метод извлечения именованных сущностей Метод P R F N-грамм 0.01 84.20 0.02 NP-chunks 4.40 28.99 7.64 NE 15.79 39.10 22.49 NEheur 11.43 43.34 18.08
12/25 Методы извлечения термов: Mihalcea R., 2007 Ранжирование термов-кандидатов Информ. Соч. P R F TF.IDF, 𝛘 𝟐Соч. 16.85 17.51 17.18 𝛘 𝟐Инф., 𝛘 𝟐Соч. 20.65 21.25 20.95 LM.Инф., LM.Соч. 12.82 13.09 12.96 TF.IDF, NE 25.95 25.27 25.60 𝛘 𝟐Инф., 𝛘 𝟐Соч., NE 26.70 26.37 26.53 LM.Инф., LM.Соч., NE 22.63 22.36 22.49 TF.IDF, NEheur 21.12 20.68 20.89 𝛘 𝟐 Инф., 𝛘 𝟐 Соч., NEheur 23.17 23.14 23.15 LM.Инф., LM.Соч., NEheur 20.98 20.72 20.84 TF.IDF 10.33 11.12 10.71 • Информативность – мера репрезентативности терма-кандидата в тексте, для её расчёта используются: • Мера TF.IDF • Языковая модель информативности (language model informativeness) • Независимое тестирование распределением Хи-квадрат (𝜒2 independence test) • Сочетаемость – мера лексической связности терма-кандидата, для её расчёта используются: • Языковая модель сочетаемости • Независимое тестирование распределением Хи-квадрат 𝑝ℎ𝑟𝑎𝑠𝑒𝑙𝑎𝑛𝑔 𝑎, 𝑏 = 𝑝 𝑓𝑔 𝑎, 𝑏 log 𝑝 𝑓𝑔 𝑎, 𝑏 𝑝 𝑏𝑔 𝑎 𝑝 𝑏𝑔 𝑏 𝑖𝑛𝑓𝑙𝑎𝑛𝑔 𝑝ℎ𝑟𝑎𝑠𝑒 = 𝑝 𝑓𝑔 𝑝ℎ𝑟𝑎𝑠𝑒 log 𝑝 𝑓𝑔 𝑝ℎ𝑟𝑎𝑠𝑒 𝑝 𝑏𝑔 𝑝ℎ𝑟𝑎𝑠𝑒
13/25 Методы извлечения термов: Mihalcea R., 2007 Оценка методов Дополнительная фильтрация: •Выявление перефразирования и синонимов •Выявление общенаучной лексики •Выявление общих слов: вводные слова, местоимения и т.п. Фильтрация P R F Без фильтрации 10.33 11.12 10.71 Перефразирование 12.70 13.15 12.93 Общенаучная лексика 14.25 15.08 14.66 Общие слова 15.25 16.30 15.76 Комбинация 15.77 16.48 16.11 Метод ранжи- рования Метод извлечения N-граммы NP-chunks Без фильтрации Вся фильтрация Без фильтрации Вся фильтрация P R F P R F P R F P R F TF.IDF 10.33 11.12 10.71 15.76 16.48 16.11 10.86 11.02 10.94 16.13 16.24 16.19 𝝌 𝟐 11.00 11.85 11.41 16.28 17.34 16.79 09.24 09.01 09.12 11.81 11.92 11.87 LM 07.54 07.83 07.68 12.50 12.39 12.45 06.67 06.89 06.78 12.09 11.68 11.88
•Для извлечения термов-кандидатов используется метод N-грамм (N=1,..,4) с предварительным отсечением N-грамм содержащих запятые и общие слова (вводные слова, местоимения и т.п.) •Корпус для обучения – 289 книг •259 книг в обучающей коллекции, 30 книг в тестовой коллекции •Положительные примеры – термы из предметных указателей этих книг 14/25 Методы извлечения термов: Машинное обучение Mihalcea R., 2008 Csomai A., Mihalcea R. Linguistically Motivated Features for Enhanced Back-of-the-Book Indexing //ACL. – 2008. – С. 932-940 Обучающая коллекция Тестовая коллекция Положительные примеры Отрицательные примеры Соотношение Положительные примеры Отрицательные примеры Соотношение 66349 (71853) 1148532 (48499870) 1:17.31 (1:674.98) 7225 (7764) 1480045 (6164798) 1:793.02 (1:203.85)
Для обучения используются следующие признаки N-грамм: •Информативность •Сочетаемость •Синтаксическая информация, например, части речи слов •Цитируемость в Wikipedia •Мера TF.IDF •Контекстная информация (discourse based) 15/25 Методы извлечения термов: Mihalcea R., 2008 Ранжирование термов-кандидатов Признак Весомость признака Часть речи 0.2335 Цитируемость в Wiki 0.2251 Информативность 0.1722 DF 0.1031 TF.IDF 0.0870 Сочетаемость 0.0660 Длина N-граммы 0.0416 Контекст 0.0279 Внешняя DF 0.0227 TF 0.0209
Применялись методы обучения: •SVM •Деревья принятия решений (DT – decision tree) •MP (multilayer perceptron) 16/25 Методы извлечения термов: Mihalcea R., 2008 Оценка методов машинного обучения Метод Ранжирование с отсечением по порогу Бинарный классификатор P R F P R F MP 27.98 27.77 27.87 23.93 31.98 27.38 DT 27.06 27.13 27.09 22.75 34.12 27.30 SVM 20.94 20.35 20.64 21.76 30.27 25.32
•Текст представляется как набор N-грамм слов (до N=7) •Отдельно оцениваются заголовки и подзаголовки •Текст разбивается на сегменты: абзацы, разделы текста •Каждая N-грамма, заголовок или подзаголовок оценивается мерой TF.IDF в рамках одного сегмента •Максимально информативными в сегменте считаются N-граммы с наибольшим значением TF.IDF 17/25 Методы извлечения термов: Sylva L., 2013 Da Sylva L.Integrating knowledge from different sources for automatic back-of-the-book indexing //Proceedings of the Annual Conference of CAIS/Actes du congrès annuel de l'ACSI. – 2013. Исходный текст Оценивание Автоматическая сегментация Сегментированный текст Заголовки и подзаголовки N-граммы Предметный указатель Отбор N-Грамм, заголовков иподзаголовков Оценивание Врамках сегмента
•Текст представляется как последовательность контекстов: предложений или абзацев •Каждый контекст состоит из термов – N-грамм слов •Задача выявления и фильтрации термов-кандидатов сводится к задаче максимизации введенной меры индексируемости (indexability) •Индексируемость зависит от контекстной информативности и цитируемости: •Контекстная информативность определяет информативность N-граммы в рамках нескольких ближайших контекстов 18/25 Методы извлечения термов: Wu Z., 2013 Wu Z. et al. Can back-of-the-book indexes be automatically created? //Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. – ACM, 2013. – С. 1745-1750. •Цитируемость измеряется по используемости N-граммы в Wikipedia
Задача построения иерархической структуры предметного указателя 19/25  Почти не описывается в рассмотренных работах.  Основные проблемы: •Использовать или нет перекрестные ссылки и в какой мере? •Использовать или нет инверсии при формировании структуры? •Распознавание родового и видового понятия: блок символов – линейный блок символов граф – планарный граф
•Для определения текстовых вариантов термов кандидатов, а также их синонимов применяются: •Алгоритм Портера (Porter 1980) – алгоритм стемминга, т.е. определения псевдооснов слов •Поиска синонимов в WordNet •Для определения страниц документа, на которых встречаются термы используют: •Стандартный поиск всех вхождений терма-кандидата в тексте •Сегментацию исходного текста (например на абзацы), для определения максимально информативных термов-кандидатов в рамках сегмента Выявление связей термов, определение ссылок 20/25 Csomai A., Mihalcea R. Investigations in Unsupervised Back-of-the-Book Indexing //FLAIRS Conference. – 2007. – С. 211-216.
Оценка построенных предметных указателей 21/25 • В большинстве работ производится оценка только извлеченного списка термов-кандидатов • Способы проверки построенного ПУ: •Ручная, экспертом: Zargayouna H. Nazarenko A. 2006 •Автоматическая: •по текстовому массиву, построенному из реального предметного указателя •в специальной оценочной системе, например, Testbet
Testbet: “золотой стандарт” для оценки ПУ Csomai A., Mihalcea R. F. Creating a Testbed for the Evaluation of Automatically Generated Back-of-the-book Indexes //Computational Linguistics and Intelligent Text Processing. – Springer Berlin Heidelberg, 2006. – С. 429-440. 22/25 •Для построения тестовой коллекции использовано 56 книг на английском языке из коллекции проекта Гунтенберг •Выбранные книги охватывают 13 различных научных областей – содержат предметные указатели •Для каждого предметного указателя из книг было построено два списка термов: •Короткий, включающий только родовые понятия •Длинный, включающий полный список понятий При этом восстанавливались инверсии и полные понятия из родовых и видовых (для длинного)
Параметры оценки предметного указателя: •Общая длина предметного указателя по отношению к размеру текста (3% - 15% в словах) •Дина в словах строк предметного указателя • Оценка возможности поиска строк предметного указателя в тексте 23/25 Testbet: “золотой стандарт” для оценки ПУ: параметры Вероятность поиска Длина строки ПУ Тип списка термов Короткий Длинный 1 92.95% 92.20% 2 72.89% 48.80% 3 48.68% 23.75% 4 28.36% 10.16% 5 16.73% 4.15% 6 9.93% 1.99% 7 8.66% 0.85% 8 12.77% 0.79% 9 3.33% 0.32% 10 8.33% 0.55% Итого 81.29% 30.34% Распределение по длине Длина строки ПУ Тип списка термов Короткий Длинный 1 31312 8250 2 9068 9352 3 2232 7627 4 1268 7057 5 642 5787 6 311 4500 7 162 3188 8 56 1906 9 36 1241 10 13 727 >10 8 862
Заключение •Научные работы направлены, в основном, на: • извлечение термов (терминов и названий объектов ПО) из текста и их фильтрацию •Работу с текстом на английском языке •Реализованные методы не работают с русским языком •Необходимо исследовать следующие подзадачи: •Определение связей термов (синонимических, родо-видовых) •Определение мест употребления термов-кандидатов в тексте •Формирование иерархической структуры предметного указателя •Оценка построенного предметного указателя •Реализация системы построения ПУ с удобным пользовательским интерфейсом 24/25
Благодарю за внимание!

More Related Content

Иванов. Автоматизация построения предметных указателей

  • 1. Автоматизация построения предметных указателей Иванов К. М. Научный руководитель: к.ф.-м.н. доцент Большакова Е.И.
  • 2. 1.Предметные указатели: структура и состав 2.Задачи построения предметного указателя 3.Извлечение и фильтрация термов: подходы и методы 4.Структурирование извлеченной информации 5.Оценка корректности построенного предметного указателя 2/25 Содержание
  • 3. •Алфавитно-предметный указатель (back-of-the-book index) – ПУ подробный перечень обсуждаемых в документе терминов, понятий и объектов предметной области (ПО) текста, с указанием страниц, на которых они встречаются в тексте. •Структура предметного указателя: Сегменты, соответствующие буквам алфавита (идентификаторам) Строки сегмента, содержащие терм: термин или название объекта ПО •Виды строк: Строка с родовым понятием Строка с видовым понятием A — ASCII 205 … … Б бинарный файл 67-69 блок символов 110 — линейный 112 — прямоугольный 121, 167 — строчный 130 блок-схема 20-25, 170 … … П понятие — абстракции 45 — алгоритма 50, 80 — анализа 145 — атрибута объекта 156, 179 … … Предметный указатель 3/25
  • 4. Особенности строк предметных указателей: •Диапазоны номеров страниц для отдельных понятий •Инверсии •Персоналии •Перекрестные ссылки Нет стандартов на структуру предметного указателя 4/25 Предметный указатель: особенности H height — of a binomial tree, 527-530 pr. — black-, 309 … … F flow, 709–714 — augmentation of, 716 — net, across a cut, 720 — value of, 710 flow conservation, 709–710 L Lester Randolph Ford, Jr., 432 N network — admissible, 749–750 — flow, see flow network … …
  • 5. •ПУ, как правило, строят для: •Книг: монографий, научных пособий, энциклопедий и т.п. •Объемных научно-технических текстов: отчетов, статей •Сайтов •Трудоемкость построения ПУ. Основная сложность: •Выявление терминов, понятий и названий объектов ПО •Определение наиболее важных мест их употребления в тексте •Определение связей выявленных терминов и понятий •Близость к задаче построения онтологии ПО: •Не для коллекции текстов, а для одного текста •Этот текст – объемный 5/25 Задача построения предметного указателя
  • 6. Автоматизация построения предметного указателя I.Извлечение из текста термов (терминов и названий объектов ПО) I.Формирование иерархической структуры предметного указателя и построение ссылок II.Редактирование полученного результата 6/25 Автоматически Вручную • Современные коммерческие редакторы, например, Microsoft Word, частично автоматизируют только этап II. • Научные исследования: автоматизации первого и второго этапов. Этапы построения:
  • 7. 1. Извлечение из текста термов-кандидатов, которые могут войти в предметный указатель, например: бинарный файл, линейный блок символов, ASCII 2. Фильтрация термов-кандидатов: отбор релевантных 3. Выявление связей термов: семантических, родо-видовых 4. Определение наиболее важных мест употребления термов в документе 5. Формирование иерархической структуры предметного указателя Подзадачи автоматизации 7/25 Этап I Этап II
  • 8. •Методы извлечения термов-кандидатов базируются на: •Лингвистической информации, в виде шаблонов и правил •Статистической информации •Их комбинации, в том числе используется машинное обучение •Простой метод – Метод Сэлтона (Salton G. Syntactic approaches to automatic book indexing //Proceedings of the 26th annual meeting on Association for Computational Linguistics. – Association for Computational Linguistics, 1988. – С. 204-210.): •Определение частей речи слов исходного текста •Термы – биграммы слов, например, low-frequency terms •Мера TF.IDF для отбора термов-кандидатов 8/25 Задача извлечения термов: подходы
  • 9. Мера TF.IDF •TF (term frequency — частота слова) — отношение числа вхождения некоторого терма t к общему количеству термов в документе d. 𝑡𝑓 𝑡, 𝑑 = 𝑛 𝑡 𝑁 𝑑 • В некоторых работах TF считается в абсолютном смысле, т.е. • IDF (inverse document frequency) — инверсия частоты, с которой некоторый терм t встречается в документах коллекции D. 𝑖𝑑𝑓 𝑡, 𝐷 = 𝑙𝑜𝑔 𝑁 𝐷 𝑑𝑓𝑡 • 𝑛 𝑡 – число вхождений терма в документе • 𝑁𝑡 – общее число термов в документе • 𝑁 𝐷– число документов в коллекции D • 𝑑𝑓𝑡– число документов коллекции D, в которые входит терм t • TF.IDF — вес некоторого терма t в документе d коллекции D. 𝒕𝒇. 𝒊𝒅𝒇 𝒕, 𝒅 = 𝒕𝒇 𝒕, 𝒅 ∗ 𝒊𝒅𝒇(𝒕, 𝑫)Величина TF.IDF возрастает • с увеличением числа вхождений термина в документ; • со снижением частоты термина во всей коллекции. 9/25 𝑡𝑓 𝑡, 𝑑 = 𝑛 𝑡
  • 10. •Работает для текстов на английском и французском языках •Для извлечения термов-кандидатов используется: •Пакет YaTeA3, извлекающий из размеченного корпуса терминологические словосочетания (http://search.cpan.org/~thhamon/Lingua-YaTeA/lib/Lingua/YaTeA.pm) •Дополнительные условия, определяемые пользователем •Для ранжирования используются: •Общая частота появления терма-кандидата в тексте (TF) •Частота появления терма-кандидата в определенных частях документа, например заголовках •Другие параметры 10/25 Методы извлечения термов для предметного указателя: InDoc, 2006 Zargayouna H. Nazarenko A. et al. IndDoc: an aid for the back-of-the-book indexer //The Indexer. – 2006. – Т. 25. – №. 2. – С. 122-125.
  • 11. • Для ранжирования выявленных термов-кандидатов используются показатели информативности и сочетаемости Csomai A., Mihalcea R. Investigations in Unsupervised Back-of-the-Book Indexing //FLAIRS Conference. – 2007. – С. 211-216. 11/25 Методы извлечения термов: Mihalcea R., 2007 • Задача извлечения термов рассматривается как задача извлечения ключевых слов. • Исследованы методы извлечения: •Метод N-грамм (N=1,…,4) •Метод поиска именных словосочетаний (noun phrase chunks) •Машинный классификатор для выявления именованных сущностей (supervised named entity recognition) •Эвристический метод извлечения именованных сущностей Метод P R F N-грамм 0.01 84.20 0.02 NP-chunks 4.40 28.99 7.64 NE 15.79 39.10 22.49 NEheur 11.43 43.34 18.08
  • 12. 12/25 Методы извлечения термов: Mihalcea R., 2007 Ранжирование термов-кандидатов Информ. Соч. P R F TF.IDF, 𝛘 𝟐Соч. 16.85 17.51 17.18 𝛘 𝟐Инф., 𝛘 𝟐Соч. 20.65 21.25 20.95 LM.Инф., LM.Соч. 12.82 13.09 12.96 TF.IDF, NE 25.95 25.27 25.60 𝛘 𝟐Инф., 𝛘 𝟐Соч., NE 26.70 26.37 26.53 LM.Инф., LM.Соч., NE 22.63 22.36 22.49 TF.IDF, NEheur 21.12 20.68 20.89 𝛘 𝟐 Инф., 𝛘 𝟐 Соч., NEheur 23.17 23.14 23.15 LM.Инф., LM.Соч., NEheur 20.98 20.72 20.84 TF.IDF 10.33 11.12 10.71 • Информативность – мера репрезентативности терма-кандидата в тексте, для её расчёта используются: • Мера TF.IDF • Языковая модель информативности (language model informativeness) • Независимое тестирование распределением Хи-квадрат (𝜒2 independence test) • Сочетаемость – мера лексической связности терма-кандидата, для её расчёта используются: • Языковая модель сочетаемости • Независимое тестирование распределением Хи-квадрат 𝑝ℎ𝑟𝑎𝑠𝑒𝑙𝑎𝑛𝑔 𝑎, 𝑏 = 𝑝 𝑓𝑔 𝑎, 𝑏 log 𝑝 𝑓𝑔 𝑎, 𝑏 𝑝 𝑏𝑔 𝑎 𝑝 𝑏𝑔 𝑏 𝑖𝑛𝑓𝑙𝑎𝑛𝑔 𝑝ℎ𝑟𝑎𝑠𝑒 = 𝑝 𝑓𝑔 𝑝ℎ𝑟𝑎𝑠𝑒 log 𝑝 𝑓𝑔 𝑝ℎ𝑟𝑎𝑠𝑒 𝑝 𝑏𝑔 𝑝ℎ𝑟𝑎𝑠𝑒
  • 13. 13/25 Методы извлечения термов: Mihalcea R., 2007 Оценка методов Дополнительная фильтрация: •Выявление перефразирования и синонимов •Выявление общенаучной лексики •Выявление общих слов: вводные слова, местоимения и т.п. Фильтрация P R F Без фильтрации 10.33 11.12 10.71 Перефразирование 12.70 13.15 12.93 Общенаучная лексика 14.25 15.08 14.66 Общие слова 15.25 16.30 15.76 Комбинация 15.77 16.48 16.11 Метод ранжи- рования Метод извлечения N-граммы NP-chunks Без фильтрации Вся фильтрация Без фильтрации Вся фильтрация P R F P R F P R F P R F TF.IDF 10.33 11.12 10.71 15.76 16.48 16.11 10.86 11.02 10.94 16.13 16.24 16.19 𝝌 𝟐 11.00 11.85 11.41 16.28 17.34 16.79 09.24 09.01 09.12 11.81 11.92 11.87 LM 07.54 07.83 07.68 12.50 12.39 12.45 06.67 06.89 06.78 12.09 11.68 11.88
  • 14. •Для извлечения термов-кандидатов используется метод N-грамм (N=1,..,4) с предварительным отсечением N-грамм содержащих запятые и общие слова (вводные слова, местоимения и т.п.) •Корпус для обучения – 289 книг •259 книг в обучающей коллекции, 30 книг в тестовой коллекции •Положительные примеры – термы из предметных указателей этих книг 14/25 Методы извлечения термов: Машинное обучение Mihalcea R., 2008 Csomai A., Mihalcea R. Linguistically Motivated Features for Enhanced Back-of-the-Book Indexing //ACL. – 2008. – С. 932-940 Обучающая коллекция Тестовая коллекция Положительные примеры Отрицательные примеры Соотношение Положительные примеры Отрицательные примеры Соотношение 66349 (71853) 1148532 (48499870) 1:17.31 (1:674.98) 7225 (7764) 1480045 (6164798) 1:793.02 (1:203.85)
  • 15. Для обучения используются следующие признаки N-грамм: •Информативность •Сочетаемость •Синтаксическая информация, например, части речи слов •Цитируемость в Wikipedia •Мера TF.IDF •Контекстная информация (discourse based) 15/25 Методы извлечения термов: Mihalcea R., 2008 Ранжирование термов-кандидатов Признак Весомость признака Часть речи 0.2335 Цитируемость в Wiki 0.2251 Информативность 0.1722 DF 0.1031 TF.IDF 0.0870 Сочетаемость 0.0660 Длина N-граммы 0.0416 Контекст 0.0279 Внешняя DF 0.0227 TF 0.0209
  • 16. Применялись методы обучения: •SVM •Деревья принятия решений (DT – decision tree) •MP (multilayer perceptron) 16/25 Методы извлечения термов: Mihalcea R., 2008 Оценка методов машинного обучения Метод Ранжирование с отсечением по порогу Бинарный классификатор P R F P R F MP 27.98 27.77 27.87 23.93 31.98 27.38 DT 27.06 27.13 27.09 22.75 34.12 27.30 SVM 20.94 20.35 20.64 21.76 30.27 25.32
  • 17. •Текст представляется как набор N-грамм слов (до N=7) •Отдельно оцениваются заголовки и подзаголовки •Текст разбивается на сегменты: абзацы, разделы текста •Каждая N-грамма, заголовок или подзаголовок оценивается мерой TF.IDF в рамках одного сегмента •Максимально информативными в сегменте считаются N-граммы с наибольшим значением TF.IDF 17/25 Методы извлечения термов: Sylva L., 2013 Da Sylva L.Integrating knowledge from different sources for automatic back-of-the-book indexing //Proceedings of the Annual Conference of CAIS/Actes du congrès annuel de l'ACSI. – 2013. Исходный текст Оценивание Автоматическая сегментация Сегментированный текст Заголовки и подзаголовки N-граммы Предметный указатель Отбор N-Грамм, заголовков иподзаголовков Оценивание Врамках сегмента
  • 18. •Текст представляется как последовательность контекстов: предложений или абзацев •Каждый контекст состоит из термов – N-грамм слов •Задача выявления и фильтрации термов-кандидатов сводится к задаче максимизации введенной меры индексируемости (indexability) •Индексируемость зависит от контекстной информативности и цитируемости: •Контекстная информативность определяет информативность N-граммы в рамках нескольких ближайших контекстов 18/25 Методы извлечения термов: Wu Z., 2013 Wu Z. et al. Can back-of-the-book indexes be automatically created? //Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. – ACM, 2013. – С. 1745-1750. •Цитируемость измеряется по используемости N-граммы в Wikipedia
  • 19. Задача построения иерархической структуры предметного указателя 19/25  Почти не описывается в рассмотренных работах.  Основные проблемы: •Использовать или нет перекрестные ссылки и в какой мере? •Использовать или нет инверсии при формировании структуры? •Распознавание родового и видового понятия: блок символов – линейный блок символов граф – планарный граф
  • 20. •Для определения текстовых вариантов термов кандидатов, а также их синонимов применяются: •Алгоритм Портера (Porter 1980) – алгоритм стемминга, т.е. определения псевдооснов слов •Поиска синонимов в WordNet •Для определения страниц документа, на которых встречаются термы используют: •Стандартный поиск всех вхождений терма-кандидата в тексте •Сегментацию исходного текста (например на абзацы), для определения максимально информативных термов-кандидатов в рамках сегмента Выявление связей термов, определение ссылок 20/25 Csomai A., Mihalcea R. Investigations in Unsupervised Back-of-the-Book Indexing //FLAIRS Conference. – 2007. – С. 211-216.
  • 21. Оценка построенных предметных указателей 21/25 • В большинстве работ производится оценка только извлеченного списка термов-кандидатов • Способы проверки построенного ПУ: •Ручная, экспертом: Zargayouna H. Nazarenko A. 2006 •Автоматическая: •по текстовому массиву, построенному из реального предметного указателя •в специальной оценочной системе, например, Testbet
  • 22. Testbet: “золотой стандарт” для оценки ПУ Csomai A., Mihalcea R. F. Creating a Testbed for the Evaluation of Automatically Generated Back-of-the-book Indexes //Computational Linguistics and Intelligent Text Processing. – Springer Berlin Heidelberg, 2006. – С. 429-440. 22/25 •Для построения тестовой коллекции использовано 56 книг на английском языке из коллекции проекта Гунтенберг •Выбранные книги охватывают 13 различных научных областей – содержат предметные указатели •Для каждого предметного указателя из книг было построено два списка термов: •Короткий, включающий только родовые понятия •Длинный, включающий полный список понятий При этом восстанавливались инверсии и полные понятия из родовых и видовых (для длинного)
  • 23. Параметры оценки предметного указателя: •Общая длина предметного указателя по отношению к размеру текста (3% - 15% в словах) •Дина в словах строк предметного указателя • Оценка возможности поиска строк предметного указателя в тексте 23/25 Testbet: “золотой стандарт” для оценки ПУ: параметры Вероятность поиска Длина строки ПУ Тип списка термов Короткий Длинный 1 92.95% 92.20% 2 72.89% 48.80% 3 48.68% 23.75% 4 28.36% 10.16% 5 16.73% 4.15% 6 9.93% 1.99% 7 8.66% 0.85% 8 12.77% 0.79% 9 3.33% 0.32% 10 8.33% 0.55% Итого 81.29% 30.34% Распределение по длине Длина строки ПУ Тип списка термов Короткий Длинный 1 31312 8250 2 9068 9352 3 2232 7627 4 1268 7057 5 642 5787 6 311 4500 7 162 3188 8 56 1906 9 36 1241 10 13 727 >10 8 862
  • 24. Заключение •Научные работы направлены, в основном, на: • извлечение термов (терминов и названий объектов ПО) из текста и их фильтрацию •Работу с текстом на английском языке •Реализованные методы не работают с русским языком •Необходимо исследовать следующие подзадачи: •Определение связей термов (синонимических, родо-видовых) •Определение мест употребления термов-кандидатов в тексте •Формирование иерархической структуры предметного указателя •Оценка построенного предметного указателя •Реализация системы построения ПУ с удобным пользовательским интерфейсом 24/25

Editor's Notes