Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Основы обработки текстов
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Системное программирование и компьютерные науки
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299)

1. Дисциплина относится к вариативной части ОПОП ВО.

2. Входные требования для освоения дисциплины (модуля): учащиеся должны владеть знаниями по алгоритмам и алгоритмическим языкам, теории вероятностей и математической статистике в объеме, соответствующем программе первых двух лет обучения основных образовательных программ бакалавриата по укрупненным группам направлений и специальностей 01.00.00 «Математика и механика», 02.00.00 «Компьютерные и информационные науки».

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.

Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):

•	ОПК-1.Б Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики
•	ОПК-2.Б Способность применять и модифицировать математические модели, а также интерпретировать полученные математические результаты при решения задач в области профессиональной деятельности 
•	ПК-3.Б Способность в составе производственного коллектива участвовать в разработке и реализации в современных программных комплексах актуальных алгоритмов компьютерной математики
•	ПК-4.Б Способность применять в профессиональной деятельности современные средства разработки программного обеспечения и методы параллельной обработки данных, реализовывать отдельные этапы разработки системного и прикладного программного обеспечения, систем обработки и анализа данных, сетевых технологий
•	ПК-5.Б Способность определить совокупность математических методов и программных решений для отдельного этапа решения прикладной задачи в рамках заданной схемы

Планируемые результаты обучения по дисциплине (модулю):

Знать:
1.	фундаментальные понятия и идеи в области компьютерной обработки текстов
2.	современные направления исследований в данной области
3.	основные проблемы, возникающие при обработке текстов.

Уметь:
1.	решать задачи из области обработки текстов
2.	проектировать системы для анализа отдельных текстовых документов и коллекций текстовых документов
3.	применять методы статистического анализа и машинного обучения для решения прикладных задач области.

Владеть:
1.	современными технологиями и программными инструментами для обработки текстов.

4. Формат обучения: лекции и семинарские занятия проводятся с использованием мультимедийного проектора и экрана, для консультирования, приёма заданий и информирования студентов используется электронная почта, блог и система автоматической проверки решений на веб-странице курса.

5. Объем дисциплины (модуля) составляет 4 з.е., в том числе 72 академических часа, отведенных на контактную работу обучающихся с преподавателем, 72 академических часов на самостоятельную работу обучающихся. 

6. Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и виды учебных занятий.
Наименование и краткое содержание разделов и тем дисциплины (модуля),

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Введение. Задачи обработки текста. Многозначность при обработке текста. Проблема понимания. Тест Тьюринга. Китайская комната	6	2	2	4	2	
2.	Регулярные выражения и конечные автоматы. Распознавание языка с помощью КА. Построение КА для регулярных выражений	6	2	2	4	2	
3.	Методы поиска словосочетаний. Общая схема. Методы поиска кандидатов. Проверка статистических гипотез.	6	2	2	4	2	
4.	Языковые модели и задача определения частей речи. Модель N-грамм. Оценка вероятности высказывания. Методы сглаживания. Оценка качества. Тренировочный и проверочный корпуса. Задача определения частей речи. Существующие подходы. Алгоритмы, основанные на правилах. Алгоритмы, основанные на трансформации.. 	10	4	4	8	2	
5.	Скрытые марковские модели. Вероятность последовательности. Прямой алгоритм. Наиболее правдоподобное объяснение. Использование скрытой марковской модели для определения частей речи. Алгоритм Витерби. Методы классификации документов. Наивный байесовский классификатор. Логистическая регрессия. Модель максимальной энтропии	10	4	4	8	2	
6.	Контекстно-свободные грамматики и синтаксический анализ. Типы грамматик. Грамматика составляющих. Грамматика зависимостей. Категориальная грамматика. Контекстно-свободные грамматики. КС грамматики и регулярные языки. Банк деревьев. синтаксический разбор. Разбор сверху вниз и снизу вверх. Алгоритм Кока-Янгера-Касами (CKY parsing). Эквивалентность КС грамматик. Группировка (chunking)	10	4	4	8	2	
7.	Статистические методы синтаксического анализа. Стохастические контекстно-свободные грамматики. Разрешение синтаксической многозначности. Моделирование языка. Обучение стохастических КС грамматик. Вероятностная версия алгоритма Кока-Янгера-Касами. Оценка качества. Проблемы стохастический КС грамматик. Алгоритм Коллинза. 	10	4	4	8	2	
8.	Лексическая семантика. WordNet. Значения слов. Разрешение лексической многозначности. Алгоритмы классификации. Самонастройка. Методы основанные на словарях и тезаурусах. Варианты алгоритма Леска. Методы оценки качества. Семантическая близость слов. Подходы на основе тезаурусов. Подходы на основе статистик. Методы оценки качества.	10	4	4	8	2	
9.	Информационный поиск. Ранжирование документов. Векторная модель. Взвешивание терминов. Индексирование. Инвертированный индекс. Запросы с джокером. Исправление опечаток	6	2	2	4	2	
10.	Вопросно-ответные системы. Общая архитектура. Обработка запроса. Извлечение фрагментов текста. Обработка ответа. Автоматическое реферирование. Общая архитектура.	6	2	2	4	2	
11.	Машинный перевод. Классические подходы. Статистический машинный перевод. Модель зашумленного канала. Модель перевода на основе фраз. Выравнивание фраз. Декодирование. Выравнивание слов. Модель IBM Model 1. Тренировка моделей выравнивания.	10	4	4	8	2	
12.	Тематическое моделирование. Вероятностная латентная семантическая модель. Латентное размещение Дирихле. Робастные модели.	6	2	2	4	2	
13.	Комплексное практическое задание.	12	0	0	0	12	
Промежуточная аттестация: устный экзамен	36	0	0	0	36	
Итого	144	36	36	72	72	

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)

7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.
Пример практического задания
Постановка задачи
Целью работы является создание системы, позволяющей оценивать эмоциональную окраску сообщений микроблога Twitter. Задача анализа эмоциональной окраски (или тональности) текста (англ. sentiment analysis  или opinion mining) состоит в автоматическом выявлении в текстах эмоциональной оценки автора по отношению к некоторому объекту.
Примеры:
•	"Начинается новый день" - нейтральная оценка
•	"Какой прекрасный день" - позитивная
•	"Ужасный день" - негативная
Предлагается разработать систему, которая на вход получает короткий текст (твит), а на выходе отдает одну из трех меток:
•	neutral - нейтральная
•	positive  - позитивная
•	negative - негативная
Решение задачи
Практические аспекты
Решения должны быть написаны на языке Python (версия 2.7). Можно использовать все стандартные библиотеки, а также 
•	NLTK - инструменты для обработки текстов
•	scikit-learn - алгоритмы машинного обучения
•	numpy - работа с многомерными массивами
Доступ в Интернет на проверяющей машине закрыт.
Теоретические аспекты
Предполагается использование алгоритмов машинного обучения. Для обучения алгоритма требуется придумать признаки и дать ему на вход правильные примеры - обучающий корпус. Считается, что чем больше обучающий корпус, тем лучше работает алгоритм. Однако создание большого обучающего корпуса - довольно трудоемкая задача, непосильная одному человеку. Поэтому предлагается создать его с помощью коллективной работы. Чтобы облегчить эту работу, был сделан сайт: http://markup.at.ispras.ru.
Разметка обучающего корпуса
Для разметки корпуса необходимо зарегистрироваться на сайте http://markup.at.ispras.ru. Пожалуйста, вводите правильные данные, так как они будут использоваться при выставлении зачетов. Вне рамок практикума эти данные использоваться не будут.
После регистрации появится окно с тремя полями (Рис 1).

Рис 1. Форма для ввода твитов

Далее вы идете на сайт twitter.com выбираете любых пользователей, которые пишут на русском языке. Ищете у них сообщения, которые содержат эмоциональную окраску (либо однозначно позитивную, либо однозначно негативную) или не содержат никаких эмоций (например, констатация факта). Копируете эти сообщения в соответствующие поля формы и нажимаете add (enter тоже работает).  Если есть сомнение в передаваемых эмоциях, лучше пропустить твит (см. следующий раздел). 
После того, как будет размечено не менее 25 позитивных, 25 негативных и 50 нейтральных сообщений, появится кнопка, позволяющая скачать размеченные твиты (см. раздел "тренировочный корпус").
Под формой ввода твитов будут появляться все твиты, размеченные и вашими коллегами. Эмоциональная окраска будет отмечена разными цветами (зеленый - позитивная, красный - негативная, серый - нейтральная). Вы можете оценить правильность разметки, нажав соответствующую кнопку рядом сообщением. Эта информация будет доступна в файле с тренировочным корпусом и ее можно использовать при обучении.
Какие твиты стоит размечать
Для разметки следует использовать твиты на русском языке. То есть твиты могут содержать иностранные названия, но основная часть текста должна быть представлена на русском языке кириллическими буквами.
ни дня без хорошей новости - recent studies suggest that sexual activity causes neurogenesis in the hippocampus.	Этот твит не считается твитом на русском языке. Такие твиты добавлять не стоит.	
Мне понравилось видео "Anime | THE SIMPSONS | ANIMATION on FOX" (http://youtu.be/R94Q6NhuS3A?a ) на @YouTube.	Этот твит нельзя считать твитом на русском языке, поскольку слов на английском языке значительно больше, чем на русском. 	
Жители Сан-Франциско атаковали автобус Google http://bit.ly/JZ9iZF	Этот твит можно считать твитом на русском языке, поскольку он содержит небольшое количество иностранных слов, которые являются именами собственными	

При оценке эмоциональной окраски твита следует учитывать только субъективное мнение автора текста (твита) по отношению к описываемому объекту/явлению. Твиты могут содержать как явную эмоциональную окраску, так и не явную. Не следует путать печальные сообщения (по смыслу) с негативной эмоциональной окраской сообщения. 
Фотосессии на ВМК всегда весёлые! http://instagram.com/p/jwm9GKx3Q5/	Это сообщение имеет явную положительную эмоциональную окраску. Такие твиты стоит добавлять.	
Кочкин становится свидетелем того, как кортеж олигарха сбивает женщину, переходящую дорогу. #photo	Это эмоционально нейтральное сообщение. Несмотря на то, что описывает оно печальное событие.	
Никогда ничего не покупайте в магазине Pleer.ru http://j.mp/KKiqSe	Это сообщение имеет неявную отрицательную эмоциональную окраску.	

Не стоит добавлять твиты, содержащие одновременно и негативную и позитивную оценку каких-либо объектов
С одной стороны, я бы не хотела жить одна - скучно и одиноко, но с другой стороны - чистота в доме, свобода, не нужно готовить - рай.	Это сообщение содержит в себе две эмоционально окрашенные части: первая – отрицательная, вторая – положительная. Однозначно трактовать эмоциональную окраску всего предложения не возможно. Такие твиты добавлять не стоит. 	

Не стоит добавлять твиты, содержащие сарказм:
Члены партии единой России обладают великим искусством правильно подобрать варианты ответа к опросу http://er.ru/poll/5.html/ 	Сарказм. Без дополнительных знаний о контексте этого сообщения невозможно определить положительное оно или отрицательное. Такие сообщения добавлять не стоит. 	

Рекомендуется размечать максимально честно, так как от этого будет зависеть качество всех классификаторов. Если есть сомнения, к какому классу лучше отнести сообщение, то его стоит пропустить.
Тренировочный корпус
Тренировочный корпус будет доступен для скачивания в формате json. Для извлечение информации из этого файла рекомендуется использовать стандартную библиотеку Python с одноименным названием.
Для синхронизации обучения и тестирования в течении недели, корпус будет состоять из твитов, размеченных автором классификатора, плюс все твиты, размеченные в течении предшествующей недели.

Тестирование
Вместе с кнопкой скачивания тренировочного корпуса появится ссылка на форму для загрузки файла и личную страницу со статистикой. На личной странице находится статистика со всеми результатами в т.ч. результатами последнего тестирования (дата, описание, достоверность).
Загрузка решения. Загружаемый файл должен представлять собой zip архив с любым именем. Архив должен обязательно содержать:
•	классификатор в файле SentimentAnalyzer.py. В файле должен содержаться класс SentimentAnalyzer. В классе должны присутствовать методы
o	train(self, training_corpus), где training_corpus - это список пар (text, class). Внимание: метод train будет вызываться отдельно, так что не стоит вызывать его в конструкторе класса.
o	getClasses (self,texts), который получает на вход список текстовых сообщений и возвращает список ответов классификатора. (Пример: [neutral, positive, positive, ...])
•	описание применяемых алгоритмов в файле description.txt
•	все используемые внешние библиотеки, кроме библиотек пакетов NLTK, scikit-learn и numpy (они доступны автоматически).
Результаты тестирования появятся на личной странице, как только закончится обучение  и тестирование. При загрузке нового классификатора обучение будет производится на корпусе из твитов, размеченных автором классификатора, плюс все твиты, размеченные в течении предшествующей загрузке недели.
В течении недели студенты не видят прогресс своих коллег и могут посмотреть только свой результат. В конце каждой недели (каждый вторник в 23.59.59) будет производится переобучение последнего присланного решения от каждого студента на новом корпусе, а результаты тестирования будут показаны в сводной таблице.
Ограничения
1.	каждую неделю можно послать только 10 версий программы (внимание! Итоговое тестирование будет проводится на последнем загруженном решении)
2.	размер архива не может превышать 15Мб
В связи с  первым ограничением, для тестирования на локальной машине рекомендуется использовать метод перекрестной проверки (http://en.wikipedia.org/wiki/Cross-validation_(statistics)). В библиотеке scikit-learn есть функции, которые могут помочь в использовании этого метода. Рекомендуется использовать метод StratifiedKFold().
Оценка качества
Для оценки качества используются метра достоверности (accuracy), которая равна отношению количества правильных ответов к общему количеству примеров в тестовой выборке.
accuracy  =
Описание в документации к библиотеке scikit-learn: http://scikit-learn.org/stable/modules/model_evaluation.html#accuracy-score
Baseline
Baseline 1. В качестве нижней границы используется классификатор, который дает всегда ответ "neutral". Достоверность этого метода равна 0.5.
Baseline 2. В качестве второй, более сложной нижней границы используется один из стандартных алгоритмов классификации с N-граммами в качестве признаков. Этот классификатор будет тренироваться на том же корпусе, что и присланные алгоритмы, и его достоверность будет меняться соответственно.

7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации.

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

ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Экзамен	Отсутствие знаний	Фрагментарные знания	Общие, но не структурированные знания	Сформированные систематические знания	
Умения
Комплексное практическое задание 	Отсутствие умений	В целом успешное, но не систематическое умение	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципиального характера)	Успешное и систематическое умение	
Навыки 
(владения, опыт деятельности)
Экзамен
Комплексное практическое задание	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие фрагментарного опыта)	В целом, сформированные навыки (владения), но используемые не в активной форме	Сформированные навыки (владения), применяемые при решении задач	

Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	фундаментальные понятия и идеи в области компьютерной обработки текстов
2.	современные направления исследований в данной области
3.	основные проблемы, возникающие при обработке текстов.	

ОПК-1.Б	
Знать:
1.	фундаментальные понятия и идеи в области компьютерной обработки текстов
2.	современные направления исследований в данной области
3.	основные проблемы, возникающие при обработке текстов.	

ОПК-2.Б	
Уметь:
1.	решать задачи из области обработки текстов
2.	проектировать системы для анализа отдельных текстовых документов и коллекций текстовых документов
3.	применять методы статистического анализа и машинного обучения для решения прикладных задач области.

Владеть:
1.	современными технологиями и программными инструментами для обработки текстов.	

ПК-3.Б	
Уметь:
1.	решать задачи из области обработки текстов

Владеть:
1.	современными технологиями и программными инструментами для обработки текстов.	

ПК-4.Б	
Уметь:
1.	проектировать системы для анализа отдельных текстовых документов и коллекций текстовых документов
2.	применять методы статистического анализа и машинного обучения для решения прикладных задач области.
Владеть:
1.	современными технологиями и программными инструментами для обработки текстов.	

ПК-5.Б	

8. Ресурсное обеспечение:

Основная литература:
  
1.	Daniel Jurafsky and James H. Martin. 2008. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition. Second Edition. Prentice Hall.
2.	Christopher D. Manning and Hinrich Schütze. 1999. Foundations of Statistical Natural Language Processing. MIT Press.
3.	Steven Bird, Ewan Klein, and Edward Loper. Natural Language Processing with Python. O'Reilly Media, 2009 (http://www.nltk.org/book)

Дополнительная литература:

1.	Mark Lutz. Learning Python, 5th Edition. O'Reilly Media, June 2013
2.	Jimmy Lin and Chris Dyer. Data-Intensive Text Processing with MapReduce. Morgan & Claypool Publishers, 2010.
3.	Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск. Издательство Вильямс. 2011
4.	Тоби Сегаран, “Программируем коллективный разум” . издательство Символ-Плюс. 2008

Информационные справочные системы:

1.	Веб-страница дисциплины:  http://modis.ispras.ru/tpc/
2.	Язык Python: http://python.org
3.	Система установки библиотек для языка Python Setup tools: https://pypi.python.org/pypi/setuptools

Материально-техническое обеспечение:

Используются  компьютер и мультимедийный проектор для демонстрации слайдов в ходе лекций. Для самостоятельной работы студенты используют компьютеры в машинных залах и/или личные компьютеры.

9. Язык преподавания - русский.

10. Преподаватели:  доцент факультета ВМК МГУ Д.Ю. Турдаков.

11. Авторы программы:  доцент факультета ВМК МГУ Д.Ю. Турдаков.