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

Поведение можно лучше контролировать, добавив в систему немного математической строгости. На помощь приходят классические алгоритмы — те самые, которые рассказывают в олимпиадных школах и используют на АСМ.

А под катом — палиндроматические сэндвичи, алгоритмизированные официанты, немного теории формальных языков и рассказ о том, к чему мы это все.

Представьте себя в ресторане. Официант подходит к вам, и происходит диалог:

- Выбрали что-нибудь?
- Да, мне, пожалуйста, черепашьи сердца с водорослями и мороженое.
- Какое мороженое? Есть вкусы мятная ваниль и ванильная мята.
- Ванильная мята, пожалуйста.
- Хорошо, заказ принят. По нашим расчетам приготовление займет примерно 43.333333 минуты. Приятного вечера!

Звучит легко, не так ли? Попробуем автоматизировать официанта в этом диалоге.

Текущие решения

Как уже было упомянуто, большая часть существующих популярных решений для NLP основано на машинном обучении, а алгоритмические методы рассматриваются как устаревшие и неэффективные. Однако, с ML-методами тоже не всё так просто:

• Решения моделей невозможно (или очень сложно) объяснить, следовательно, непонятно как отлаживать проблемы
• Нельзя быть уверенным в надежности решения, поэтому приходится добавлять огромные черные списки для оскорбительных словосочетаний
• Для обучения нужны большие выборки данных, которые сложно собрать на начальном этапе
• Требуется более сложная схема ведения диалога, чем реакция на интенты и slot-filling

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

Есть и комбинированные решения. В частности, фреймворк для обучения диалоговых систем, выпущенный недавно лабораторией iPavlov.ai, поддерживает комбинированные сценарии — можно совмещать компоненты машинного обучения и Rule-based подход в рамках одного чат-бота. Ниже мы приведем еще некоторые примеры интеграции машинного обучения в грамматику.

Архитектура системы

Решение, которое мы предлагаем рассмотреть, состоит из трех основных частей:

• Модуль понимания
• Постоянная память
• Модуль генерации ответа

Стоит упомянуть, что кроме NLP-ядра в диалоговой системе обычно есть еще голосовой движок. Мы не будем рассматривать архитектуру этого компонента, но к нашему официанту можно легко добавить голос.

На весенней школе (про которую чуть позже) мы реализуем всю эту иерархию на С++ на примере нескольких мини-проектов, и даже прикрутим чат-бота к телеграмму при помощи библиотеки одного из учеников нашей школы.

Экскурс в теорию

На самом деле, теория формальных языков представляет собой формализацию лингвистики математическим языком. Базовые определения — это алфавит и слово. Алфавит — просто множество символов. Конечная последовательность символов из алфавита образует слово.

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

Наконец, важнейшее определение. Грамматика — это набор правил вывода, по которым одни слова можно преобразовывать в другие.

В нашем же случае формальные определения немного расходится с интуицией. “Терминалы” в наших примерах — это слова русского языка. А значит, “слова” — это, по сути, реплики. Нетерминалы будут обозначаться словами в <угловых> скобках. Звучит сложно? Дальше будет хуже.

Приведем пример. Поскольку сейчас блок теории, пример должен быть не очень жизненным. Допустим, вы очень любите есть палиндроматические сэндвичи на завтрак. Проснувшись рано утром, вы решили сгенерировать себе такой сэндвич из C (сыра), Х (хлеба), К (колбасы). Нам также потребуется пара нетерминалов <СТАРТ> и <СОДЕРЖИМОЕ>.
Примеры палиндроматических сэндвичей:

Хлеб Хлеб (XX)
Хлеб Сыр Хлеб (XCX)
Xлеб Cыр Cыр Колбаса Сыр Cыр Хлеб (XCCКСCХ) *

* Выбор авторов

Грамматика следующая:

<СТАРТ> -> Х <СОДЕРЖИМОЕ> X
<СОДЕРЖИМОЕ> -> \perp | C | К | C <СОДЕРЖИМОЕ> C | К <СОДЕРЖИМОЕ> К

Вертикальная черта означает, что в этом правиле выбирается произвольная правая часть (последовательность после ->).

Память

Самое простое в реализации — это память, просто набор переменных, объединенных в структуру. Память — единственное средство передать информацию между модулем понимания и генеративной системой.

Помимо сырых фактов (в нашем примере — перечисленных блюд) в память очень удобно записывать некоторое внутреннее состояние, которое само по себе будет описывать контекст диалога. Эти состояния объединены в так называемую машину состояний (по сути, детерминированный конечный автомат).

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

В алгоритмическом официанте достаточно следующих состояний: $НАЧАЛО ДИАЛОГА$, $УТОЧНИТЬ ВИД$, $ПОДТВЕРДИТЬ ЗАКАЗ$. В вышеприведенном примере диалога каждая реплика официанта происходит в каждом из упомянутых состояний соответственно. Логику переходов мы опишем чуть позже.

Модуль понимания

С точки зрения теории формальных языков это задача распознавания грамматики.

Пример грамматики:

<ЗАКАЗ> -> <ДАЙТЕ> <ЕДЫ> <И ЕЩЕ ЕДЫ>
<ДАЙТЕ> -> <ДАЙ> | <ПОЖАЛУЙСТА> <ДАЙ> | <ДАЙ> <ПОЖАЛУЙСТА>
<ДАЙ!> -> принесите мне | я хочу | мой заказ
<ПОЖАЛУЙСТА> -> пожалуйста | будьте добры
<ЕДЫ> -> <ЦЕЛОЕ БЛЮДО> | <БЛЮДО> с <ГАРНИРОМ>
<И ЕЩЕ ЕДЫ> -> <> | <ЕДЫ> <И ЕЩЕ ЕДЫ> 
<ГАРНИРОМ> -> рисом | картофелем | водорослями 
<ЦЕЛОЕ БЛЮДО> -> паста | мороженое 
<БЛЮДО> -> куриная грудка | черепашьи сердца | сладкую котлетку
<КАКОЙ ВИД> -> <ВИД> | <ВИД> <ПОЖАЛУЙСТА>
<ОСТАВИТЬ ОТЗЫВ> -> Хочу оставить отзыв: <ОТЗЫВ>

Такая грамматика называется контекстно-свободной, поскольку в правой части расположены нетерминалы и применение правил возможно вне зависимости от другой части фразы. Существует и более узкий класс грамматик — регулярные. Именно на них основаны регулярные выражения.

Вспоминая про машину состояний, добавим переходы:

$НАЧАЛО ДИАЛОГА$, <ЗАКАЗ> -> $ПОДТВЕРДИТЬ ЗАКАЗ$
$ПОДТВЕРДИТЬ ЗАКАЗ$, <ЦЕЛОЕ БЛЮДО> -> $УТОЧНИТЬ ВИД$
$УТОЧНИТЬ ВИД$, <КАКОЙ ВИД> -> $ПОДТВЕРДИТЬ ЗАКАЗ$

Таким образом, в зависимости от реплики клиента можно перейти либо в $УТОЧНИТЬ ВИД$, либо сразу в $ПОДТВЕРДИТЬ ЗАКАЗ$. На самом деле, в правило можно добавить несколько правых частей. Тогда автомат из детерминированного превратится в недетерминированный, и переход нужно будет как-то выбирать. Можно выбирать случайно, можно использовать эвристики, а можно применить машинное обучение, решив задачу классификации.

Разбор осуществляется через LL(1)-парсер. Это сравнительно простой алгоритм, с небольшими модификациями позволяющий распознать намерение пользователя и выбрать наиболее важные факты из его реплики.

Но не всё так просто:
Понимать фразу необходимо по-разному в зависимости от текущего контекста. Посетитель хочет только сделать заказ или уточнить? Чтобы это определить, введем функцию от памяти, которая будет выдавать стартовый нетерминал: $start(memory)$
На самом деле, недостаточно просто понять корректность фразы. Из фразы нужно вычленить максимальное количество самой разной информации. Некоторые нетерминалы в таблице не имеют ни одной последовательности, в которую их можно раскрыть — просто потому, что, например, <ОТЗЫВ> может содержать всё что угодно. Поэтому вместо традиционного разбора просто запишем всё, что попало в этот нетерминал в правильное поле памяти.

Модуль генерации

Небольшая предыстория. В России чтобы поступить в ВУЗ, необходимо сдать ЕГЭ, в т. ч. и по русскому языку. Как известно, ЕГЭ призвано формализовать систему проверки знаний выпускников школы. Одно из заданий в ЕГЭ — написать сочинение по тексту. А что мы делаем, если есть формальные требования? Используем формальную грамматику!

Подробности и другие примеры в репозитории

Вернемся к алгоритмизации официанта.

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

<УТОЧНИТЬ ВИД> -> Какое <ЦЕЛОЕ БЛЮДО> ? Есть <ОПЦИЯ 1> и <ОПЦИЯ 2>.
<ПОДТВЕРДИТЬ> -> <ПОДТВЕРЖДЕНО> <ОЖИДАЙТЕ> <ВРЕМЯ>
<ПОДТВЕРЖДЕНО> -> Заказ принят | принято 
<ОЖИДАЙТЕ> -> будет готово через | ожидаемое время приготовления 

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

Как же должен быть построен алгоритм генерации? На самом деле, здесь все предельно интуитивно: в качестве начальной фразы берем стартовый нетерминал и начинаем раскрывать нетерминалы по случайному правилу из грамматики. Процесс продолжается, пока все нетерминалы не будут раскрыты.
Этот алгоритм можно продолжать улучшать: вводить вероятности, с которыми то или иное правило будет использовано, раскрывать цепочки параллельно или даже использовать методы обучения с подкреплением. Ключевое отличие от классических генеративных моделей (например, основанных на LSTM или Transformer) в том, что порожденная фраза всегда будет находиться в грамматике, а значит, будет уместна в данной ситуации.

Заключение

Примерно так можно применить теорию алгоритмов (конечные автоматы и формальные грамматики), к, казалось бы, нетривиальной задаче обработки языка.

В России есть сильная алгоритмическая школа: школьники побеждают на международной олимпиаде по информатике, студенты — на финале ACM ICPC, курсы по алгоритмам в лучших университетах страны вмещают в себя крайне продвинутый материал.

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

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

Зимой направление "Алгоритмы и приложения" получило боевое крещение, и на весенней школе GoTo направление вновь состоится. Обновленная программа уже появилась на сайте, и мы устраиваем конкурс GoTo Algorithms Challenge Spring18.

Конкурс представляет собой виртуальное соревнование. У вас будет 5 часов на то, чтобы решить 8 задач. Сортировка участников происходит по сумме баллов за задачи

Результаты будут подведены 21 марта. Победители и призеры получат гранты и скидки на обучение в весенней школе GoTo.

Контест

Заказ принят. Ожидаемое время приготовления: 25 марта. Применяйте алгоритмы!