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

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


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

Общие сведения о задании


Предварительное замечание: выполняя это упражнение не следует придерживаться ограничений базовой версии языка Scheme. Разумно начать код с директивы #lang scheme и применять библиотеки Racket, но использование написанных не Вами библиотек Natural Language Processing запрещено.

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

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

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

Второй способ -- «обратный». Очевидно, что можно при обучении сохранять и считать (N-1)-граммы, завершающие предложения. Стартуем от случайно с учётом веса выбранной такой (N-1)-граммы. Подбираем частого предшественника выбранной (N-1)-граммы и присоединяем его слева. Для этого нам нужен граф предшествования в котором (N-1)-граммы соединяются дугами со словами -- своими предшественниками. Этот граф тоже можно построить при обучении. За новую (N-1)-грамму берём собранную часть ответа, от которой отрезано последнее слово. Ищем и добавляем частого предшественника полученной (N-1)-граммы. Иак далее, пока не будет достигнуто начало предложения (т. е. точка и д. р.).

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

При любом способе генерации предложения имеет смысл обращать внимание на его длину. Из-за особенностей строения текстов реплика может содержать «циклы» (например, something of something of something ...). Из-за «циклов» есть возможность получать бесконечные и бессмысленные предложения. Генератор должен препятствовать такого рода эффектам. Например, чем больше длина построенной части предложения, тем настойчивее генератор может пытаться завершить предложение.

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

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

Добавление стратегии «Весна» следует начать с усовершенствования ввода и вывода «Доктора». Так, «Доктор», реализованный ранее, не способен нормально работать с фразами, внутри которых есть точки, вложенные круглые скобки и прочая пунктуация. Следует реализовать считывание реплики пользователя в строку (например, при помощи фунции Racket read-line), перевод строки во внутреннее представление, совместимое с реализованными ранее функциями построения ответных реплик. Допускается адаптировать эти функции для работы с новым внутренним представлением. Считывание в строку избавляет пользователя от необходимости писать свои фразы в скобках, отделять знаки пунктуации от предшествующих им слов пробелами и т. п.. Следует обратить внимание на то, что из-за нового ввода пользователь может давать реплики из нескольких предложений. Из-за этого «Доктор», применяя старые версии построения ответов по qualifier и history (из упражнений 2 и 3), будет выдавать чепуху. Поэтому «Доктора» следует переработать в этой части. Далее, преобразование строки должно быть реализовано так, чтобы лишние символы, не используемые в письменной речи, игнорировались. Также можно защититься от неверного использования пользователем прописных букв. Следует обеспечить новый вывод из внутреннего представления на экран (например, при помощи фунции Racket printf). При выводе не следует брать ответ «Доктора» в скобки. Вывод точек и других знаков пунктуации должен быть корректным, например точка не должна отделяться пробелом от предшествующего ей слова.

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

Максимальная оценка за 4-й этап -- 15 баллов. Срок сдачи без штрафа: по 1 ноября включительно. За реализованные улучшения для генерирующей и/или обучающей части «Доктора» могут быть начислены дополнительные баллы.

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

Требования при сдаче задания


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

Предупреждение


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

  

© Кафедра системного программирования ВМК МГУ.

Обновлено: 30.10.2016