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

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


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

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


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

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

При предварительной обработке из обучающего текста извлекаются сведения об N-граммах. А именно: 1) набор (N-1)-грамм, с которых начинаются фразы, с указанием для каждой частоты встречаемости; 2) граф следования. Этот ориентированный граф содержит в качестве вершин (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)-грамму, в которую входит часть выбранного фрагмента, в худшем случае, одно слово из него. Желательно, чтобы слово было длинным. От найденной (N-1)-граммы реплика далее строится в обоих направлениях: «прямом» -- от середины к концу; и «обратном» -- от середины к началу.

В простом случае генерируемая реплика может состоять из одного предложения, но можно строить длинные реплики из нескольких предложений. Очевидно, что чем больше предложений будет в ответной реплике, тем нагляднее будет искусственность построенного текста. Смысловые связи между предложениями часто будут отсутствовать.

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

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

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

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

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

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

Обучать «Доктор» следует на составленном Вами наборе текстов. Тексты стоит подбирать по какой-то одной теме. Темы у разных студентов должны быть разные, поэтому необходимо заранее согласовать свой выбор темы с лектором. Тексты следует подбирать или даже специально составлять из простых повествовательных предложений. В обучающих текстах должны быть использованы устойчивые словосочетания. Благодаря этому генерируемые тексты будут хоть как-то напоминать естественные. Если Вы разыщите готовые коллекции обучающих текстов, подготовленные и опубликованные исследователями (а не студентами, выполнявшими задание «Весна» в прошлые годы), то можете использовать их. Использование в поисковике слов вроде «Chatbot Datasets for Machine Learning» может помочь.

Следует подобрать подходящую структуру для представления графа слов (например, Racket хэш-таблицу и/или Scheme ассоциированные списки или т. п.). Для этой структуры следует явно определить набор операций: конструктор, селекторы, предикаты-чеккеры, мутаторы. Следует сделать так, чтобы обучающая часть могла сохранять результаты своей работы в файле, считывать их из файла и пополнять при обработке очередного текста.

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

При реализации можно использовать мутируемые структуры и присваивание там, где это уместно. Демонстрацию работы программы второго этапа следует производить на разных обучающих выборках (с разными значениями N и разными обучающими текстами), чтобы показать влияние обучения и величины N на качество генерируемых фраз. Код программы должен быть правильно оформлен, структурирован, сопровождён комментариями.

Максимальная оценка за «Весну» -- 30 баллов. За реализованные нетривиальные решения в генерирующей и/или в обучающей части «Доктора» могут быть начислены дополнительные баллы.

По желанию может быть оформлен отчёт по выполненным заданиям «Доктор» и «Весна». Оценка за отчёт 5 баллов. Требования к отчёту опубликованы отдельно: [html].

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


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

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


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

  

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

Обновлено: 25.X.2021