Лекция 2. Регулярные выражения и конечные автоматы

Доступны слайды второй лекции (lecture2.pdf). Рассматриваемые темы:

  • формальные языки;
  • регулярные выражения и их практическое применение;
  • детерминированные и недетерминированные конечные автоматы;
  • регулярные языки;
  • связь конечных автоматов, регулярных выражений и регулярных языков.

Первое занятие в осеннем семестре 2012 года

Первое занятие состоится в аудитории П-6 в пятницу 28-го сентября в 18.00. На вводной лекции будут рассмотрены классические задачи обработки текстов и типичные проблемы, возникающие при решении этих задач. Также будут обсуждаться некоторые организационные моменты.

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

Спецкурс в осеннем семестре 2012 года

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

Спецкурс по синтаксическому анализу

В этом семестре на ВМК будет читаться спецкурс "Автоматический синтаксический анализ текстов на естественном языке". С деталями и лектором я не знаком, но судя по описанию, там будет рассмотрен синтаксический уровень анализа намного более подробно, чем в лекциях 5 и 6. Так что, если Вы интересуетесь темой, рекомендую послушать. Кроме того, лектор - руководитель группы семантического анализа технологического департамента компании ABBYY.

Hotfix к практическому заданию

Так как некоторые из участников не сумели совладать с codecs.open, то теперь можно послать письмо в следующем формате:

имя_системы
имя_участника
plain

Магическое слово "plain" отключит в вашем решении codecs.open, и файлы будут открываться при помощи стандартного open, как это реализовано в baseline.

Билеты к экзамену

Готовы билеты к экзамену (скачать в pdf).

  1. Задачи обработки текста. Многозначность при обработке текста. Проблема понимания
  2. Регулярные выражения
  3. Конечные автоматы, распознавание языка с помощью КА
  4. Регулярные языки и конечные автоматы. Построение КА для регулярных выражений
  5. Модель N-грамм. Оценка вероятности высказывания
  6. Модель N-грамм. Сглаживание (Лапласа и Откат)
  7. Модель N-грамм. Оценка качества. Тренировочный и проверочный корпуса
  8. Задача определения частей речи. Существующие подходы
  9. Использование скрытой марковской модели для определения частей речи
  10. Скрытые марковские модели. Вероятность последовательности. Прямой алгоритм
  11. Скрытые марковские модели. Наиболее правдоподобное объяснение. Алгоритм Витерби
  12. Модели классификации. Наивный байесовский классификатор
  13. Модели классификации. Логистическая регрессия
  14. Модели классификации. Модель максимальной энтропии
  15. Модели классификации. Марковская модель максимальной энтропии
  16. Типы грамматик. Грамматика составляющих. Грамматика зависимостей. Категориальная грамматика
  17. Контекстно-свободные грамматики. КС грамматики и регулярные языки. Банк деревьев.
  18. Синтаксический разбор. Разбор сверху вниз и снизу вверх
  19. Синтаксический разбор. Алгоритм Кока-Янгера-Касами (CKY parsing). Эквивалентность КС грамматик
  20. Фрагментирование
  21. Стохастические контекстно-свободные грамматики. Разрешение синтаксической многозначности
  22. Моделирование языка. Обучение стохастических КС грамматик
  23. Вероятностная версия алгоритма Кока-Янгера-Касами. Оценка качества
  24. Проблемы стохастический КС грамматик. Алгоритм Коллинза. Оценка качества
  25. Лексическая семантика. WordNet. Значения слов
  26. Разрешение лексической многозначности. Алгоритмы классификации. Самонастройка. Методы оценки качества
  27. Разрешение лексической многозначности. Методы основанные на словарях и тезаурусах. Варианты алгоритма Леска. Методы оценки качества
  28. Семантическая близость слов. Подходы на основе тезаурусов. Методы оценки качества
  29. Семантическая близость слов. Подходы на основе статистик. Методы оценки качества
  30. Вопросно-ответные системы. Общая архитектура. Обработка запроса
  31. Вопросно-ответные системы. Общая архитектура. Извлечение фрагментов текста
  32. Вопросно-ответные системы. Общая архитектура. Обработка ответа
  33. Автоматическое реферирование. Общая архитектура
  34. Машинный перевод. Классические подходы
  35. Статистический машинный перевод. Модель зашумленного канала. Модель перевода на основе фраз. Выравнивание фраз (если слова выровнены). Декодирование
  36. Статистический машинный перевод. Выравнивание слов. Модель IBM Model 1
  37. Статистический машинный перевод. Выравнивание слов. Тренировка моделей выравнивания
  38. Статистический машинный перевод. Методы оценки качества. BLUE

Лекция 9. Машинный перевод

Выложил слайды к девятой лекции. На лекции рассматриваются

  • Классические подходы к машинному переводу
  • Статистический машинный перевод
  • Модель зашумленного канала
  • Модель перевода на основе фраз
  •  Выравнивание слов. Модель IBM Model 1
  • Тренировка моделей выравнивания
  • Декодирование
  • Методы оценки качества. Метрика BLUE