Раздел 4. Автоматический синтаксический анализ
8.13. Формализмы и методы автоматического синтаксического анализа
Синтаксические отношения. Синтаксическая омонимия. Непосредственные составляющие. За- висимости.
Домашнее задание
Чтение [J&M]. Ch. 9. Pp. 319-353. Ch. 12 Pp. 443-473.
Упр.1. Синтаксический анализ предложения. Случаи синтаксической омонимии, синтаксиче- ские нули. Формальное представление синтаксической структуры предложения.
Упр.2. Нормальная форма Хомского. Применение алгоритма Кока-Янгера-Касами.
Упр.3. NLTK (
http://www.nltk.org/
). Написать контекстно-свободную грамматику для порожде- ния простых предложений на английском языке.
8.14. Унификационные грамматики
Понятие унификации. Правила унификации. Ограничения.
Семинарское занятие (14).
Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины “Компьютерная лингвистика” для направления
45.04.03 «Компьютерная лингвистика» подготовки бакалавра
Правила унификации. Тест. Разбор практических заданий. NLTK
Домашнее задание
Написать унификационную грамматику для порождения именных групп в русском языке с ис- пользованием NLTK
8.15. Лексикализованные и вероятностные грамматики
Практическое занятие (18).
Алгоритм Early. Оценка вероятностей.
8.16. Синтаксический анализ в терминах деревьев зависимостей
Зависимости. Критерий эндоцентричности. Критерий морфосинтаксического локуса. Непроек- тивность.
8.17. Алгоритмы анализа в терминах деревьев зависимостей
Практическое занятие (20).
Разбор алгоритмов синтаксического анализа в терминах зависимостей.
Домашнее задание
Применить алгоритмы синтаксического анализа в терминах зависимостей к анализу предложе- нию на русском языке
Выполнить синтаксическую разметку предложения
8.18. Universal Dependencies
Семинарское занятие (21).
Обсуждение универсальных связей в UD. Обсуждение правил конвертации в UD для русского языка. Сравнение с другими славянскими языками.
Домашнее задание
Разметка предложений на русском языке в UD
Запросы к Трибанку
Анализ ошибок конвертации в UD
8.19. Синтаксический анализю Современные методы завистмостного анализа
Семинарское занятие (20).
Обсуждение методов синтаксического анализа в терминах зависимостей
Литература к разделу
Jurafsky D., James H. Chapter 13. Parsing with Context-free Grammar. Speech and language pro- cessing an introduction to natural language processing, computational linguistics, and speech. – 2009.
The 2nd edition (Chapter 9. Edition - 2000).
Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины “Компьютерная лингвистика” для направления
45.04.03 «Компьютерная лингвистика» подготовки бакалавра
Апресян Ю. Д. и др. Синтаксически и семантически аннотированный корпус русского языка: современное состояние и перспективы //Национальный корпус русского языка. – 2003. – Т.
2005. – С. 193-214. URL: http://corpora.phil.spbu.ru/Works2008/Boguslavsky1_56_74.pdf (дата об- ращения: 27.01.2015)
Joakim Nivre, Sandra Kubler. Dependency Parsing. Tutorial at COLING-ACL, Sydney 2006. (пре- зентация) http://stp.lingfil.uu.se/nivre/docs/ACLslides.pdf
Дополнительная литература Анисимович К. В. и др. Синтаксический и семантический парсер, основанный на лингвистиче- ских технологиях ABBYY Compreno. // В кн. Компьютерная лингвистика и интеллектуальные технологии. (дата обращения: 27.01.2015)
По материалам ежегодной Международной конференции "Диалог" (2012). Том 2. Доклады спе- циальных секций – (URL: http://www.dialog-21.ru/digests/dialog2012/materials/pdf/anisimovich.pdf
(дата обращения: 27.01.2015))
Иомдин Л.Л. и др. Синтаксический анализатор системы ЭТАП: современное состояние. // В кн.
Компьютерная лингвистика и интеллектуальные технологии. По материалам ежегодной Меж- дународной конференции "Диалог" (2012). Том 2. Доклады специальных секций – (URL: dialog2012/materials/pdf/Iomdin.pdf (дата обращения: 27.01.2015))
Антонова А. А., Мисюрев А. В. Анализатор русского языка syntautom для соревнования синтак- сических парсеров (диАлог-2012). // В кн. Компьютерная лингвистика и интеллектуальные тех- нологии. По материалам ежегодной Международной конференции "Диалог" (2012). Том 2. До- клады специальных секций. (http://www.dialog-21.ru/digests/dialog2012/materials/pdf/98.pdf (дата обращения: 27.01.2015))
Корпуса для анализа: o
СинТагРус http://ruscorpora.ru/search-syntax.html (дата обращения: 27.01.2015), o
Тестовый корпус с параллельной синтаксической разметкой http://otipl.philol.msu.ru/soiza/testsynt/, (дата обращения: 27.01.2015), o Rus-Treebank http://otipl.philol.msu.ru/soiza/rtb/res01/rtb.php (дата обращения:
27.01.2015)
9 Образовательные технологии [Основой для знакомства с методологией анализа текстов и овладения практическими навыка- ми автоматического анализа текста с помощью программных средств в рамках
курса служит работа над учебным проектом, состоящим из двух частей, по анализу текстовой коллекции. В начале курса студентам предлагается на выбор несколько жанров. На протяжении курса студен- ты работают над сбором и анализом коллекции текстов в малых группах (2-3 человека). В зада- чи проекта входит создание собственного токенизатора и сплиттера, спелл-чеекера, распознава- теля языка. А также морфологический анализ текста. Тестирование одного из морфологи- чемских тегеров. По результатам анализа группы пишут отчет по проекту, который состоит из
(а) аналитиечской записки, содержащей краткое изложение существующих подходов к задаче, стандартных проблем, описанных в литературе по данному вопросу; (б) краткие характеристи- ки системы; (в) результаты тестирования системы с описанием сложных случаев и анализом ошибок.
В качестве простых упражнений рекомендуется также упражнения на пошаговое применение обсуждаемых в курсе алгоритмов вручную.
Для освоения материала на практических занятиях используются задания, предназначенные как для индивидуального решения задач по обработке текста, так и для коллективного обсуждения стратегии решения той или иной задачи. Проводится обсуждение отдельных методов компью- терной лингвистики в форме мини-докладов студентов по материалам проведенного анализа выбранной текстовой коллекции. Особое внимание уделяется организации самостоятельной ра- боты студентов с программным обеспечением, рассматриваемым в рамках курса.
Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины “Компьютерная лингвистика” для направления
45.04.03 «Компьютерная лингвистика» подготовки бакалавра
10 Оценочные средства для текущего контроля и аттестации студента
10.1 Средства для оценки качества освоения дисциплины в ходе текущего контроля
Примерный перечень вопросов к различным формам текущего контроля.
1. Задачи и направления компьютерной лингвистики
3 направления компьютерной лингвистики. Основные задачи в рамках каждого направления.
Типы систем и задач
2. Задачи автоматического анализа текста
Проверка правописания, грамматики и стиля. Распознавание текстов. Распознавание и синтез ре- чи. Машинный перевод текста и речи (классика NLP). Информационный поиск. Реферирование.
Классификация (кластеризация и рубрикация) текстов, установление сходства текстов (плагиат и т.п.). Автофильтрация. Вопросно-ответные и диалоговые системы. Системы извлечения знаний
(извлечение именованных сущностей, извлечение отношений и фактов, извлечение тонально- сти/мнений). Примеры систем
3. Типы лингвистических данных
Типы электронных ресурсов, представляющих лингвистические данные: лексикографические ресурсы; корпуса. Примеры
4. Корпуса текстов. Основные понятия корпусной лингвистики
Корпус текстов: определение, решаемые задачи. Национальный корпус текстов. Типы корпусов.
Понятие сбалансированного vs. мониторного корпуса. Требования к корпусам: репрезентатив- ность, полнота, структурированность. Единицы хранения. Типы аннотации корпусов. Назначе- ние корпусов. Использование корпусов при разработке систем автоматического анализа текстов.
5. Основные этапы автоматической обработки текста
Задачи каждого из этапов. Проблемы лингвистической обработки текста на разных этапах: неод- нозначность, несимметричность, избыточность, конвенциональность, эллиптичность и т.п.
6. Информационный поиск
Полнотекстовый поиск vs. индекс. Термин vs. лексема. Матрица термин-документ. Инвертиро- ванный индекс. Токен vs. лемма. Частотные характеристики элементов текста (лемм, n-грам).
7. Методы исправления ошибок
Замена, удаление символа, вставка символа. Расстояние Левенштейна. Вероятностные методы.
8. Методы распознавания языка
N-грамные модели распознавания. Методы детектирование языка по самым частотным словам.
9. Этапы предварительной обработки текста.
Сбор корпуса текстов. Проблема унификации текстов в корпусе (кодировка, «многозначность» служебных символов, нетекстовые элементы и т.п.). Стандарты представления текстов (напри- мер, TEI).
10. Предварительная обработка текста. Задачи и проблемы токенизации. Особенности токенизации для разных типов и жанров текстов. Сегментация текстов на предложения. Методы сегментации.
11. Автоматический морфологический анализ
Типы задач автоматического морфологического анализа: нормализация (стемминг и лемматиза- ция); частеречная/лекско-грамматическая аннотация; полный морфологический анализ; дизам- бигуация
12. Этапы автоматического морфологического анализа:
Токенизация, лемматизация, первичная частеречная аннотация, дизаимбигуация, идиоматизация, постобработка. Лингвистические проблемы, решаемые на различных этапах автоматического морфологического анализа.
13. Подходы к представлению данных в автоматическом морфологическом анализе.
Словарь vs. правила. Контекст словоформы vs. внутренняя структура словоформы. Словарь сло- воформ (информация, используемая в словаре словоформ, для каких методов анализа использу- ется чаще). Понятие основы и окончания при автоматическом морфологическом анализе, поня-
Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины “Компьютерная лингвистика” для направления
45.04.03 «Компьютерная лингвистика» подготовки бакалавра тие парадигмы (псевдоосновы и псевдооокончания). Правила порождения словоформ (правила перехода от глубинного представления словоформы к поверхностному (учет морфонологических чередований и т.п.)
14. Технологии реализации морфологического анализа Основные технологии: конечные автоматы;
конечные преобразователи; регулярные выражения.
Моделирование правил перехода от лексического уровня представления словоформы к проме- жуточному. Моделирование правил перехода от промежуточного уровня к поверхностному.
15. Методы частеречной разметки. Основные методы снятия морфологической омонимии Классификация методов лексико-грамматической (частеречной разметки). Организация грамма- тических аннотаций. Методы, основанные на правилах. Метод извлечения правил (трансформа- ционный метод) Э.Брилла. Метод, основанный на скрытых марковских моделях.
16. Основания оценки качества морфологического разбора Оценка общего качества работы модуля автоматической обработки текста. Разработка золотого стандарта. Метрики качества морфологического анализа: полнота, точность, степень омонимич- ности. Классификация ошибок. Проблемы тестирования систем морфологического анализа.
Функциональное тестирование.
17. Автоматический синтаксический анализ. Задачи. Способы представления синтаксической структуры Приложения, в которых используется автоматический синтаксический анализ. Задачи автомати- ческого синтаксического анализа. Основные единицы анализа. Формальные системы представ- ления синтаксической структуры предложения
18. Автоматический синтаксический анализ. Лингвистические проблемы Синтаксическая омонимия. Наиболее проблемные случаи для разрешения синтаксической омо- нимии при автоматическом синтаксическом анализе. Синтаксические нули. Способы решения.
Нестандартный порядок слов (перемещения, разрывы составляющих). Непроективные структу- ры. Дальние связи. Эллипсис и нули.
19. Контекстно-свободные грамматики. Особенности представления предложений в терминах деревьев непосредственных составляющих при автоматическом синтаксическом анализе. Проблемы: перемещения и разрывы составляю- щих, дальние связи. Способы решения проблем: «размножение» правил с учетом субкатеогриза- ции; вероятностные контекстно-свободные грамматики; лексикализованные вероятностные кон- текстно-свободные грамматики
20. Алгоритмы автоматического синтаксического анализа в терминах непосредственных со-ставляющих Унификации. Унификационные грамматики. Анализ с помощью унификационных грамматик
21. Автоматический анализ в терминах деревьев зависимостей. Основные подходы. Проблемы. Случаи неоднозначного определения вершины и зависимого.
Непроективность. Нестандартные решения при выборе направления связей
22. Автоматический анализ в терминах деревьев зависимостей. Анализ в терминах универсальных зависимостей. Проект UD.
23. Методы улучшения качества работы систем синтаксического анализа. Использование лексической и онтологической информации в системах автоматического морфологического анализа. Использование информации о частотных свойствах единиц синтаксического анализа (какие частотные характеристики используются, часта каких единиц учитывается).
24. Базовые алгоритмы анализа в терминах зависимостей Переход к деревьям НС. Грамматика ограничений. Алгоритм Нивра.
25.
Кратко опишите одну из систем автоматического синтаксического анализа Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины “Компьютерная лингвистика” для направления
45.04.03 «Компьютерная лингвистика» подготовки бакалавра
Основное предназначение. Внутренняя организация. Используемые модули. Используе- мые базовые алгоритмы. Подходы к решению проблемных случаев (непроективность, нули и т.п.). Методы «борьбы» с синтаксической неоднозначностью.
26. Частичный синтаксический анализ Задачи, в которых используется неполный синтаксический анализ (shallow parsing). Вы- деление связанных фрагментов предложения (chunking). Основные задачи и технологии.
11 Практические, аналогичные тем, которые были в ДЗ: 1. Для некоторого морфонологического процесса сформулировать правило; построить ко- нечный автомат, распознающий словоформы, получившиеся в результате действия дан- ного правила
2. Предложить правила построения некоторого класса словоформ: построить конечный преобразователь, задающий переход от лексического уровня к промежуточному или от промежуточного к поверхностному
3. Для некоторой цепочки словоформ с морфологической аннотацией сравнить 2 варианта последовательности морфологических тегов, найти более вероятную последовательность
4. Дано множество предложений: построить для них деревья непосредственных составля- ющих; построить кс-грамматику, которая порождает все данные деревья; применить ее к новому предложению
5. Дана кс-грамматика и предложение: перевести ее в нормальную форму Хомского и рас- писать шаги алгоритма CYK
6. Дана предложение; построить дерево зависимостей и описать места, проблемные для анализа в терминах деревьев зависимостей
7. Даны несколько предложений в
корпусе с параллельной синтаксической разметкой; про- анализировать расхождения в ответах систем; определить, какие расхождения объясня- ются разными теоретическими решениями; какие - являются ошибками системы
Бонусное задание:
8. Распишите отдельные шаги/условия применения одного из базовых алгоритмов для по- строения деревьев зависимостей для предложения
Дополнительные задания
9. Найти в тексте сложные случаи для предварительной обработки, предложить правила решения
10. Найти в тексте сложные случаи морфологического анализа текста для разных этапов морфологического анализа
11. Найти в предложении случаи, сложные для решения в системах автоматического синтак- сического анализа в терминах непосредственных составляющих
11.1 Примеры заданий промежуточной аттестации Пример контрольной работы
Часть 1. Без компьютера
1. Перечислите основные направления в области a. извлечения информации / знаний из текста.
Кратко охарактеризуйте основную задачу / основные задачи направления. Назовите 2-3 термина, связанные с этими направлениями с кратким пояснением
2. За что отвечает этап идиоматизации. Приведите примеры различных типов случаев, которые этот этап «обслуживает»
3. Что является наблюдаемой переменной в скрытой марковской модели, применяемой для часте- речной аннотации
Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины “Компьютерная лингвистика” для направления
45.04.03 «Компьютерная лингвистика» подготовки бакалавра
На каких допущениях относительно лексической вероятности (грамматических тегов для кон- кретной словоформы) базируется метод дизамбигуации, основанный на скрытых марковских моделях. Приведите пример ситуаций, когда это основное не работает.
4. Что является синтаксическими единицами, синтаксическими отношениями в представлении син- таксической структуры в терминах непосредственных составляющих
5. Приведите пример правил для синтаксического анализа в терминах КС- грамматики, которые позволяют порождать предложения
Я вижу лес
Ты видишь лес и т.п.
Но запрещают предложения типа
Я видишь лес
Ты видим лес и т.п.
Часть 2.
6. Найдите в НКРЯ три ошибки при делении на предложения. Ответ прокомментируйте. (Нужно придумать такие запросы, которые бы вам искали ошибки определенного типа)
7. Вычислите tf.idf для слов
медвежонок,
что, ворона в тексте
Сергей Козлов. Как Ёжик с Медвежонком спасли Волка // «Мурзилка», 2003 для коллекции НКРЯ «Детская литература»
8. Методы дизамбигуации:
Приведите пример 2-х правил (patch-а) в методе Эрика Брилла, которые можно вывести из сле- дующего фрагмента
Золотой стандарт:
The fly can fly
Det N V V
Первичная аннотация
Det Verb Verb N
Приведите пример миникорпуса (4 предожения), на котором одно из полученных правил увели- чит количество ошибок, а не уменьшит?
9. Приведите глубинное (lexical) – промежуточное (intermediate) – поверхностное представление
(Surface) для словоформы
дымка (в двухуровневой морфологии)
10. Дан набор словоформ. Предложить 3 варианта представления морфологических данных для дан- ной лексемы и данной подпарадигмы: глагол
сидеть в настоящем времени
11. Вычислите вероятность прилагательного в контексте предшествующего ему указательного ме- стоимения и сравните ее с вероятностью глагола в контексте предшествующего ему указатель- ного местоимения
12. Дан Трибанк из 4-х предложений, постройте по ним КС-грамматику и переведите ее в нормаль- ную форму Хомского
Дано предложение и грамматика. Представьте шаги анализа данного предложения при примене- нии алгоритма Кока-Янгера-Касами
1) Вася читает мою книгу
2) Напиши какое-нибудь письмо
3) Этот веселый мальчик идет
4) Он любит читать всякие книги
Предложение для разбора:
Они используют эти виды стали. 
Скачать 0.69 Mb.