Главная страница « Информация « 4 курс « курс ВвФП «

Задание «Весна». 2015-16 учебный год

„Нет проблем! Мы можем покончить с этой ерундой за выходные!“
Э. Йордон „Путь камикадзе“

Задание посвящено добавлению в «Доктор» новой стратегии построения ответов. Добавляемый способ состоит в генерации случайной последовательности слов. Чтобы оставалась видимость осмысленности текста, генератор будет использовать данные, накопленные после обработки текстов по психоаналитике. В ходе этой обработки выявляются пары идущих друг за другом слов. Логично предположить, что порядок слов в осмысленном тексте не случаен. Значит, генератор может при составлении ответной реплики после текущего слова ставить то, которое часто встречается в текстах следом за ним. Заметим, что понятие «слова» толкуется расширительно, так как знаки пунктуации тоже следует рассматривать как «слова». Например, это позволит генератору решать, уместно ли закончить предложение (уместно, если за текущим словом часто следуют точка, восклицательный знак или вопросительный знак). Также генератор сможет составлять предложения со знаками пунктуации внутри (запятыми, двоеточиями, тире). И наконец, генератор сможет начинать реплики с тех слов, которые в тексте часто следуют после точек, восклицательных знаков или вопросительных знаков.

При предварительной обработке текста -- обучении -- , фактически, формируется граф. Это ориентированный граф, вершинами которого являются слова, а дугами -- отношения следования, соединяющие слова, которые соседствуют в тексте. Дуги графа имеют веса. Более весомой будет дуга, соединяющая два слова, которые чаще всего следуют друг за другом.

Рассмотрим, как можно использовать построенный граф для генерации реплик. Первый способ, условно называемый прямым, состоит в следующем: На первом шаге ищутся в графе слова, следующие за концом предложения (точкой и др.). С учетом весов дуг случайно выбирается одно из таких слов. Оно будет начальным в реплике. Далее ищутся в графе слова, следующие за начальным. Случайно с учетом весов дуг выбирается один из кандидатов. И так далее, до тех пор пока на очередном шаге не будет выбрано слово, являющееся концом предложения (точка, восклицательный знак или др.). Если ответная реплика состоит из одного предложения, то на этом построение ответа прямым способом завершается. Второй способ -- обратный. Очевидно, что можно, стартуя от конца предложения, подбирать последнее слово -- частого предшественника точки, воклицательного или вопросительного знаков. Перед последним словом в ответ можно добавить предпоследнее, и так далее, пока не будет достигнуто начало предложения. Третий способ -- смешанный. При этом способе можно выбрать некоторое слово, которое будет находиться внутри предложения. Например, в качестве такого слова можно взять более-менее длинное слово из реплики пользователя, на которую генерируется ответ. От текущего слова реплика далее строится в обоих направлениях: прямом -- от середины к концу; и обратном -- от середины к началу. В простом случае реплика может состоять из одного предложения, но можно строить длинные реплики из нескольких предложений.

Заметим, что рассмотренные техники тривиальны. Реальные программы, генерирующие тексты, используют много больше сведений о словах, чем их порядок следования в тексте. Примером такой программы является MIT SCIgen, результаты работы которой удавалось публиковать на научных конференциях с низким контролем принимаемых докладов. Эта программа сгенерировала текст известной статьи, перевод которой на русский язык известен под названием «Корчеватель: Алгоритм типичной унификации точек доступа и избыточности».

Выполнение задания «Весна» разделено на три этапа. На первом этапе (подготовительном) следует усовершенствовать ввод и вывод «Доктора». Так, «Доктор», реализованный ранее, не способен нормально работать с фразами, внутри которых есть точки, вложенные круглые скобки и т. п.. Следует реализовать считывание реплики пользователя в строку (например, при помощи фунции Racket read-line), перевод строки во внутреннее представление, совместимое с реализованными ранее функциями построения ответных реплик. Допускается адаптировать эти функции для работы с новым внутренним представлением. Считывание в строку избавляет пользователя от необходимости писать свои фразы в скобках, отделять знаки пунктуации от предшествующих им слов пробелами и т. п.. Следует обратить внимание на то, что из-за нового ввода пользователь может давать реплики из нескольких предложений. Применяя старые версии построения ответов по qualifier и history (из упражнений 2 и 3), «Доктора» из-за этого будет выдавать чепуху. Поэтому «Доктора» следует переработать в этой части. Далее, перевод строки должен быть реализован так, чтобы лишние символы, не используемые в письменной речи, игнорировались. Также можно защититься от неверного использования прописных букв. Следует обеспечить новый вывод из внутреннего представления на экран (например, при помощи фунции Racket printf). При выводе не следует брать ответ «Доктора» в скобки. Вывод точек и других знаков пунктуации должен быть корректным, например точка не должна отделяться пробелом от предшествующего ей слова. Как часть подготовительного этапа следует составить обучающую выборку англоязычных текстов по психоаналитике. В выбоке должно быть от 3 до 7 текстов разных авторов. Объем каждого текста не менее 2000 знаков. Тексты из выборки должны быть подготовлены к дальнейшей обработке обучающей частью «Доктора» (переведены в нужную кодировку и/или формат и/или регистр, избавлены от спецсимволов и т. п.) Максимальная оценка за 1-й этап -- 10 баллов. Срок сдачи без штрафа: по 20 ноября включительно.

На втором этапе разрабатывается версия «Доктора», содержащая обучающую часть, которая анализирует тексты, и генератор, способный по результатам обучения строить фразы прямым и смешанным способами. Следует подобрать подходящую структуру для представления графа слов (например, Racket хэш-таблицу и/или Scheme ассоциированные списки). Следует сделать так, чтобы обучающая часть могла сохранять результаты своей работы в файле, считывать их из файла и пополнять при работе с новым текстом. Генератор должен иметь возможность считывать результаты обучения из файла. Генератор должен быть встроен в «Доктор», как одна из стратегий с большим весом/приоритетом. При выполнении второго этапа можно использовать мутируемые структуры и присваивание там, где это уместно. Демонстрацию работы программы второго этапа следует производить на разных обучающих выборках, чтобы показать влияние обучения на качество генерируемых фраз. Код программы должен быть правильно оформлен, структурирован, сопровожден комментариями. Максимальная оценка за 2-й этап -- 15 баллов. Срок сдачи без штрафа: по 11 декабря включительно. Для получения дополнительных баллов можно предложить и реализовать улучшения для генерирующей и/или обучающей части «Доктора».

На третьем этапе готовится отчет обо всех выполненных заданиях по «Доктору». Отчет сдается по электронной почте в формате PDF. Требования к отчету указаны ниже. Максимальная оценка за 3-й этап -- 5 баллов. Срок сдачи без штрафа: по 19 декабря включительно.

На всех этапах за каждую неделю просрочки сдачи этапа будет начисляться штраф в размере 1/4 от максимального балла. По прошествии 4-х недель этап можно сдать, но баллы начислены не будут. По окончании семестра (в период зачетных и экзаменационных сессий и каникул) скорость роста штрафов может возрасти. Студенты, не сдавшие задание, не смогут получить положительную оценку на экзамене.

Требования к отчету

Отчет пишется на русском языке. Текст отчета должен быть разбит на следующие части:

• Титульный лист, с «шапкой» - «Московский государственный университет имени М. В. Ломоносова, факультет Вычислительной математики и кибернетики». Далее следует заголовок: «Отчет по "Доктору"», сведения об исполнителе (фамилия, имя и отчество полностью, номер группы). Внизу титульного листа указывается город и год. Нелишне обратить внимание на то, что точки после заголовков не ставятся.
  

• Содержание состоит из перечня названий глав и подглав, сопровождаемых указанием номеров страниц, с которых они начинаются. Нумеруются все страницы, за исключением титульного листа. Номер страницы с содержанием: 2.
  

• Первая глава, названная «Упражнения 1-6», содержит пояснения Ваших решений. Для каждого упражнения следует указать идею, лежащую в основе решения, используемые структуры данных, сигнатуры и текстовые описания функций, реализованных/исправленных/усовершенствованных при выполнении упражнения. Описание должно соответствовать версии с улучшенным вводом/выводом, и содержать комментарии по его реализации. Каждую главу следует начинать с новой страницы.
  

• Вторая глава, названная «Упражнение 7», содержит пояснение Вашего решения в этой части. Содержание строится стереотипно предыдущей главе. Если Вы не выполняли 7-е упражнение, то ее текст тривиален: «Решение упражнения 7 отсутствует.»
  

• Третья глава, названная «Весна. Обучение», содержит описание обучающей части генератора случайных фраз. Следует пояснить выбранную структуру данных, алгоритм обучения, формат файла для хранения результатов обучения. Также следует привести список текстов, выбранных для обучения, и обосновать свой выбор. Если тексты проходили предварительную подготовку с помощью программ, то следует дать пояснения по этой части.
  

• Четвертая глава, названная «Весна. Генерация», содержит описание генератора. Следует привести алгоритмы генерации для прямого и смешанного способов, пояснить основные функции в составе своей программы. Если Вы усовершенствовали способ генерации фраз, опишите предложенное Вам решение и его реализацию.
  

• Пятая глава, названная «Результаты», содержит фрагменты протоколов работы доктора с комментариями. Выбор фрагментов должен быть таким, чтобы демонстрировались все стратегии построения ответов. Должны быть примеры как удачных, так и неудачных реплик «Доктора». В комментариях следует привести соображения о том, насколько удачно, на Ваш взгляд, Ваша реализация «Доктора» общается с пользователем. В пятой главе должно быть проанализировано влияние обучения на качество генерируемых реплик.
  

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

• Список использованной литературы приводится, если в ходе работы над заданием были использованы статьи и/или книги. Библиографические записи в списке следует оформлять по рекомендациям ГОСТ. На каждую запись списка в тексте отчета должна быть ссылка.
  

• Приложение, которое содержит Ваш код.

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

Содержание
1. Упражнения 1-6 .......................3
2. Упражнение 7 ..........................
3. Весна. Обучение .......................
4. Весна. Генерация ......................
5. Результаты ............................
Заключение ...............................
Список литературы ........................
Приложение. Код программы.................

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