Привет, Хабр! Совсем недавно мы кратко рассказывали о Natural Language Interfaces (Естественно-Языковых Интерфейсах). Ну а сегодня у нас не кратко. Под катом вы найдете полноценный рассказ о создании NL2API для Web-API. Наши коллеги из подразделения Research опробовали уникальный подход к сбору обучающих данных для фреймворка. Присоединяйтесь!

Аннотация

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

Мы предлагаем первую комплексную платформу (фреймворк), позволяющую создать NL2API для конкретного веб-API. Ключевой задачей является сбор данных для обучения, то есть пар «команда NL — вызов API», позволяющих NL2API изучить семантику как команд NL, не имеющих строго определенного формата, так и формализованных вызовов API. Мы предлагаем собственный уникальный подход к сбору обучающих данных для NL2API с помощью краудсорсинга — привлечения многочисленных удаленных работников к генерации различных команд NL. Сам процесс краудсорсинга мы оптимизируем с целью сокращения затрат.

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

Введение

Программные интерфейсы приложения (API) играют все более важную роль и в виртуальном, и в физическом мире благодаря развитию таких технологий, как сервис-ориентированная архитектура (SOA), облачные вычисления и Интернет вещей (IoT). Например, размещенные в облаке веб-службы (погода, спорт, финансы и др.) через веб-API предоставляют данные и услуги конечным пользователям, а устройства IoT дают возможность другим сетевым устройствам использовать свою функциональность.


Рисунок 1. Пары «NL-команда (слева) и вызов API (справа)», собранные
нашим фреймворком, и сравнение с IFTTT. GET-Messages и GET-Events — два веб-API для поиска электронных писем и событий календаря соответственно. API можно вызывать с различными параметрами. Мы концентрируемся на полностью параметризованных вызовах API, в то время как IFTTT ограничивается API с простыми параметрами.

Обычно API используются в различном программном обеспечении: в приложениях для рабочего стола, веб-сайтах и мобильных приложениях. Также они обслуживают пользователей с помощью графического пользовательского интерфейса (GUI). GUI внес большой вклад в популяризацию компьютеров, но, по мере развития вычислительной техники, все чаще проявляются его многочисленные ограничения. С одной стороны, поскольку устройства становятся все меньше размером, мобильнее и умнее, требования к графическому изображению на экране постоянно повышаются, например, в отношении переносных устройств или устройств, подключенных к IoT.

С другой стороны, пользователям приходится адаптироваться к различным специализированным GUI для различных служб и устройств. По мере увеличения числа доступных сервисов и устройств расходы на обучение и адаптацию пользователей также растут. Естественно-языковые интерфейсы (NLI), например, виртуальные помощники Apple Siri и Microsoft Cortana, которые также называют разговорными или диалоговыми интерфейсами (CUI), демонстрируют значительный потенциал в качестве единого интеллектуального инструмента для широкого спектра серверных служб и устройств.

В этой работе рассматривается проблема создания естественно-языкового интерфейса для API (NL2API). Но, в отличие от виртуальных помощников, это не NLI общего назначения,
мы разрабатываем подходы к созданию NLI для конкретных веб-API, то есть API веб-служб, подобных мультиспортивному сервису ESPN1. Такие NL2APIs могут решить проблему масштабируемости NLI общего назначения, предоставив возможность распределенной разработки. Полезность виртуального помощника во многом зависит от широты его возможностей, то есть от количества поддерживаемых им сервисов.

Однако интегрировать веб-сервисы в виртуального помощника по одному — невероятно кропотливая работа. Если бы у индивидуальных провайдеров веб-сервисов был недорогой способ создания NLI для своих API, то затраты на интеграцию удалось бы значительно сократить. А виртуальному помощнику не пришлось бы обрабатывать разные интерфейсы для разных веб-сервисов. Ему достаточно было бы просто интегрировать отдельные NL2API, которые достигают единообразия благодаря естественному языку. С другой стороны, NL2API также могут упростить обнаружение веб-служб и программирование систем рекомендаций и помощи для API, что избавит от необходимости запоминать большое количество доступных веб-API и их синтаксис.

Пример 1. Два примера показаны на рисунке 1. API можно вызывать с различными параметрами. В случае с API поиска электронных писем пользователи могут фильтровать электронную почту по определенным свойствам или искать письма по ключевым словам. Главная задача NL2API заключается в сопоставлении NL-команд с соответствующими вызовами API.

Задача. Сбор обучающих данных — одна из наиболее важных задач, связанных с исследованиями в области разработки интерфейсов NLI и их практического применения. Интерфейсы NLI используют контролируемые обучающие данные, которые в случае NL2API состоят из пар «команда NL — вызов API», чтобы изучить семантику и однозначно сопоставить NL-команды с соответствующими формализованными представлениями. Естественный язык очень гибкий, поэтому пользователи могут описывать вызов API синтаксически различными способами, то есть имеет место парафразирование.

Рассмотрим второй пример на рисунке 1. Пользователи могут перефразировать этот вопрос следующим образом: «Где пройдет следующая встреча» или «Найди место проведения следующей встречи». Поэтому крайне важно собрать достаточные обучающие данные, чтобы система в дальнейшем распознавала подобные варианты. Существующие NLI обычно придерживаются принципа «лучшее из возможного» в процессе сбора данных. Например, наиболее близкий аналог нашей методологии для сопоставления NL-команд с вызовами API использует концепцию IF-This-Then-That (IFTTT) — «если это, тогда то» (рисунок 1). Обучающие данные поступают напрямую с сайта IFTTT.

Однако если API не поддерживается или поддерживается не полностью, никакого способа исправить ситуацию нет. Кроме того, обучающие данные, собранные таким образом, малоприменимы для поддержки расширенных команд с несколькими параметрами. Например, мы проанализировали анонимизированные журналы вызовов API Microsoft для поиска электронных писем за месяц и обнаружили, что около 90 % из них используют два или три параметра (примерно в одинаковых количествах), и эти параметры довольно разнообразны. Поэтому мы стремимся обеспечить полную поддержку параметризации API и реализовать расширенные NL-команды. Проблема развертывания активного и настраиваемого процесса сбора обучающих данных для конкретного API в настоящее время остается нерешенной.

Вопросы применения NLI в сочетании с другими формализованными представлениями, такими как реляционные базы данных, базы знаний и веб-таблицы, проработаны достаточно хорошо, при этом разработке NLI для веб-API внимание практически не уделялось. Мы предлагаем первую комплексную платформу (фреймворк), позволяющую создать NL2API для конкретного веб-API с нуля. В реализации для веб-API наш фреймворк включает три этапа: (1) Представление. Исходный HTTP-формат веб-API содержит множество избыточных и, значит, отвлекающих деталей с точки зрения интерфейса NLI.

Мы предлагаем использовать промежуточное семантическое представление для веб-API, чтобы не перегружать NLI лишней информацией. (2) Набор обучающих данных. Мы предлагаем новый подход к получению контролируемых обучающих данных на основе краудсорсинга. (3) NL2API. Мы также предлагаем две модели NL2API: модель извлечения на основе языковой модели и модель рекуррентной нейронной сети (Seq2Seq).

Одним из ключевых технических результатов этой работы является принципиально новый подход к активному сбору обучающих данных для NL2API на основе краудсорсинга — мы привлекаем удаленных исполнителей для аннотирования вызовов API при их сопоставлении с NL-командами. Это позволяет достичь трех целей проектирования, обеспечив: (1) Настраиваемость. Необходимо обеспечить возможность указать, какие параметры для какого API использовать и какой объем обучающих данных собрать. (2) Низкие затраты. Услуги краудсорсинговых работников стоят на порядок дешевле услуг профильных специалистов, поэтому именно их и нужно нанимать. (3) Высокое качество. Качество обучающих данных не должно снижаться.

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

Затем мы продумываем грамматику для автоматического преобразования каждого вызова API в каноническую NL-команду, которая может оказаться довольно громоздкой, но зато будет понятна среднему краудсорсинговому работнику (см. раздел 3.1). Исполнителям останется только перефразировать каноническую команду, чтобы она звучала более естественно. Такой подход позволяет предотвратить многие ошибки при сборе обучающих данных, поскольку задача перефразирования намного проще и понятнее для среднего краудсорсингового работника.

Во-вторых, необходимо понять, как определять и аннотировать только те вызовы API, которые представляют реальную ценность для обучения NL2API. Возникающий при параметризации «комбинаторный взрыв» приводит к тому, что количество вызовов даже для одного API может быть довольно большим. Аннотировать все вызовы не имеет смысла. Мы предлагаем принципиально новую иерархическую вероятностную модель для реализации процесса краудсорсинга (см. раздел 3.2). По аналогии с языковым моделированием с целью получения информации, мы предполагаем, что NL-команды генерируются на основе соответствующих вызовов API, поэтому языковую модель следует использовать для каждого вызова API, чтобы зарегистрировать этот «порождающий» процесс.

Наша модель базируется на композиционной природе вызовов API или формализованных представлений смысловой структуры в целом. На интуитивном уровне, если вызов API состоит из более простых вызовов (например, «непрочитанные электронные письма о заявке на получение степени кандидата наук» = «непрочитанные электронные письма» + «электронные письма о заявке на получение степени кандидата наук», мы можем построить его языковую модель из простых вызовов API даже без аннотирования. Поэтому, аннотируя небольшое количество вызовов API, мы можем рассчитать языковую модель для всех остальных.

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

Мы применяем наш фреймворк к двум развернутым API из пакета Microsoft Graph API2. Мы демонстрируем, что высококачественные обучающие данные можно собирать с минимальными затратами при условии использования предложенного подхода3. Мы также показываем, что наш подход повышает эффективность краудсорсинга. При аналогичных затратах мы собираем более качественные обучающие данные, значительно превосходя базовые показатели. Как следствие, наши решения NL2API обеспечивают более высокую точность.

В целом, наш основной вклад включает три аспекта:

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

Таблица 1. Параметры запроса OData.

Преамбула

RESTful API

В последнее время веб-API, отвечающие архитектурному стилю REST, то есть RESTful API, становятся все более популярными благодаря своей простоте. Интерфейсы RESTful API также применяются в смартфонах и IoT-устройствах. Restful API работают с ресурсами, адресуемыми через URI, и предоставляют доступ к этим ресурсам для широкого круга клиентов с помощью простых команд HTTP: GET, PUT, POST и др. Мы, в основном, будем работать с RESTful API, но базовые методы можно применять и к другим интерфейсам API.

Для примера возьмем популярный протокол открытых данных (OData) для RESTful API и два веб-API из пакета Microsoft Graph API (рисунок 1), которые, соответственно, используются для поиска электронных писем и событий календаря пользователя. Ресурсы в OData представляют собой сущности, каждая из которых связана со списком свойств. Например, сущность Message — электронное письмо — обладает такими свойствами, как subject (тема), from (от), isRead (прочитано), receivedDateTime (дата и время получения) и т. д.

Кроме того, OData определяет набор параметров запроса, позволяя выполнять расширенные манипуляции над ресурсами. Например, параметр FILTER (ФИЛЬТР) позволяет искать электронные письма от конкретного отправителя или письма, полученные на конкретную дату. Параметры запроса, которые будем использовать мы, представлены в таблице 1. Мы вызываем каждую комбинацию команды HTTP и сущности (или набор сущностей) как API, например, GET-Messages — для поиска электронных писем. Любой параметризованный запрос, например, FILTER(isRead=False), называется параметром, а вызов API — это API со списком параметров.

NL2API

Основная задача NLI заключается в сопоставлении высказывания (команды на естественном языке) с определенным формализованным представлением, например, логических форм или запросов SPARQL для баз знаний или веб-API в нашем случае. Когда необходимо сосредоточиться на семантическом отображении, не отвлекаясь на несущественные детали, обычно используется промежуточное семантическое представление, чтобы не работать непосредственно с целевым. Например, комбинаторная категориальная грамматика широко применяется при создании интерфейсов NLI для баз данных и баз знаний. Подобный подход к абстракции также очень важен для NL2API. Множество деталей, включая соглашения URL, заголовки HTTP и коды ответов, могут «отвлекать» NL2API от решения главной задачи — семантического отображения.

Поэтому мы создаем промежуточное представление для интерфейсов RESTful API (рисунок 2) с именем API frame, это представление отражает семантику кадра. Кадр API состоит из пяти частей. HTTP Verb (Команда HTTP) и Resource (Ресурс) — базовые элементы для RESTful API. Return Type (Возвращаемый тип) позволяет создавать составные API, то есть объединять несколько вызовов API для выполнения более сложной операции. Required Parameters (Обязательные параметры) чаще всего используется в вызовах PUT или POST в API, например, для отправки электронной почты обязательными параметрами являются адресат, заголовок и тело письма. Optional Parameters (Дополнительные параметры) часто присутствуют в вызовах GET в API, они помогают сузить информационный запрос.

Если обязательные параметры отсутствуют, мы выполняем сериализацию кадра API, например: GET-messages{FILTER(isRead=False), SEARCH(“PhD application”), COUNT()}. Кадр API может быть детерминирован и преобразован в реальный вызов API. В процессе преобразования будут добавлены необходимые контекстные данные, включая идентификатор пользователя, местоположение, дату и время. Во втором примере (рисунок 1) значение now в параметре FILTER будет заменено на дату и время выполнения соответствующей команды в ходе преобразования кадра API в реальный вызов API. Далее понятия кадра API и вызова API мы будем использовать как взаимозаменяемые.


Рисунок 2. Кадр API. Сверху: команда на естественном языке. Посередине: Кадр API. Снизу: Вызов API.


Рисунок 3. Конвейер краудсорсинга.

Сбор обучающих данных

В этом разделе описан предлагаемый нами принципиально новый подход к сбору обучающих данных для решений NL2API с помощью краудсорсинга. Сначала мы генерируем вызовы API и преобразуем каждый из них в каноническую команду, опираясь на простую грамматику (раздел 3.1), а затем привлекаем краудсорсинговых работников для перефразирования канонических команд (рисунок 3). Учитывая композиционный характер вызовов API, мы предложили иерархическую вероятностную модель краудсорсинга (раздел 3.2), а также алгоритм оптимизации краудсорсинга (раздел 3.3).


Рисунок 4. Генерация канонической команды. Слева: лексикон и грамматика. Справа: пример деривации.

Вызов API и каноническая команда

Мы генерируем вызовы API исключительно на основе спецификации API. Помимо элементов схемы, таких как параметры запроса и свойства сущности, нам необходимы значения свойств для генерации вызовов API, которые спецификацией API не предусмотрены. Для свойств со значениями перечислимого типа, например Boolean, мы перечисляем возможные значения (True/False).

Для свойств со значениями неограниченного типа, например Datetime, мы синтезируем несколько репрезентативных значений, например today или this_week для receivedDateTime. Необходимо понимать, что это абстрактные значения на уровне кадра API и они будут преобразованы в реальные в соответствии с контекстом (например, реальную дату и время) при преобразовании кадра API в реальный вызов API.

Перечислить все комбинации параметров запроса, свойств и значений свойств для создания вызовов API несложно. Простая эвристика позволяет отсеять не совсем подходящие комбинации. Например, к сортированному списку применяется TOP, поэтому использовать этот параметр необходимо в сочетании с ORDERBY. Кроме того, свойства типа Boolean, например isRead, в ORDERBY использоваться не могут. Тем не менее «комбинаторный взрыв» в любом случае обусловливает наличие большого количества вызовов API для каждого API.

Среднему пользователю сложно понять вызовы API. По аналогии с мы преобразуем вызов API в каноническую команду. Мы формируем специфический для API лексикон и общую для API грамматику (рисунок 4). Лексикон позволяет получить лексическую форму и синтаксическую категорию для каждого элемента (команды HTTP, сущности, свойства и значения свойств). Например, лексическая запись ?sender > NP[from]? показывает, что лексической формой свойства from является «sender», а синтаксической категорией — именное словосочетание (NP), которое будет использоваться в грамматике.

Синтаксические категории также могут быть глаголами (V), глагольными словосочетаниями (VP), прилагательными (JJ), словосочетаниями-номинализаторами (CP), обобщенными именными словосочетаниями, за которыми следуют другие именные словосочетания (NP/NP), обобщенными предложными словосочетаниями (PP/NP), предложениями (S) и т. д.

Необходимо отметить, что хотя лексикон специфичен для каждого API и должен быть предоставлен администратором, грамматика разработана как общая и поэтому может тиражироваться на любой RESTful API на основе протокола OData — «как есть» или после незначительных модификаций. 17 грамматических правил на рисунке 4 позволяют охватить все вызовы API, используемые в следующих экспериментах (раздел 5).

Грамматика дает понять, как шаг за шагом получить каноническую команду из вызова API. Это набор правил вида ?t1, t2, ..., tn > c[z]?, где представляет собой последовательность токенов, z является частью вызова API, а c z — его синтаксической категорией. Обсудим пример на рисунке 4. К вызову API в корне дерева деривации, который имеет синтаксическую категорию S, мы сначала применяем правило G4, чтобы разбить исходный вызов API на четыре части. C учетом их синтаксической категории, первые три можно непосредственно преобразовать во фразы на естественном языке, в то время как последняя использует другое поддерево деривации и поэтому будет преобразована в словосочетание-номинализатор «that is not read».

Следует отметить, что синтаксические категории допускают условную деривацию. Например, к VP[x = False] может применяться и правило B2, и правило B4, поэтому принять решение помогает синтаксическая категория x. Если x относится к синтаксической категории VP, выполняется правило B2 (например, x is hasAttachments > «do not have attachment»); а если это JJ, то выполняется правило B4 (например, x is isRead > «is not read»). Это позволяет избегать громоздких канонических команд («do not read» or «is not have attachment») и делает сгенерированные канонические команды более естественными.

Семантическая сеть

Мы можем генерировать большое количество вызовов API, используя вышеуказанный подход, но аннотировать их все с помощью краудсорсинга нецелесообразно с экономической точки зрения. Поэтому мы предлагаем иерархическую вероятностную модель для организации краудсорсинга, которая помогает решить, какие вызовы API следует аннотировать. Насколько нам известно, это первая вероятностная модель применения краудсорсинга для создания интерфейсов NLI, позволяющая решить уникальную и интригующую задачу моделирования взаимодействия между представлениями на естественном языке и формализованными представлениями смысловой структуры. Формализованные представления смысловой структуры в целом и вызовы API в частности имеют композиционную природу. Например, z12 = GET-Messages {COUNT(),FILTER(isRead=False)} состоит из z1 = GET- Messages{FILTER(isRead=False)} и z2 = GET-Messages{COUNT()} (эти примеры мы подробнее обсуждаем далее).


Рисунок 5. Семантическая сеть. i-й слой состоит из вызовов API с i параметрами. Ребра — это композиции. Распределения вероятностей на вершинах характеризуют соответствующие языковые модели.

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

Для начала мы определяем композицию на основе набора параметров вызовов API.

Определение 3.1 (композиция). Возьмем API и набор вызовов API
, если мы определим r (z) как набор параметров для z, то является композицией тогда и только тогда, когда является частью

Опираясь на композиционные взаимосвязи вызовов API, можно организовать все вызовы API в единую иерархическую структуру. Вызовы API с одинаковым количеством параметров представлены как вершины одного слоя, а композиции представлены как
направленные ребра между слоями. Эту структуру мы называем сематической сетью (или SeMesh).

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

В силу причин, которые станут очевидны немного позже, вместо стандартной языковой униграм-модели мы предлагаем использовать набор распределений Бернулли (Bag of Bernoulli, BoB). Каждое распределение Бернулли соответствует случайной величине W, определяющей, появляется ли слово w в высказывании, сгенерированном на основе z, а распределение BoB — это набор распределений Бернулли для всех слов . Мы будем использовать как краткое обозначение для .

Предположим, мы сформировали (мульти)набор высказываний для z,
оценка максимального правдоподобия (MLE) для распределения BoB позволяет отобрать высказывания, содержащие w:



Пример 2. Относительно упомянутого выше вызова API z1 предположим, что мы получили два высказывания u1 = «find unread emails» и u2 =«emails that are not read», то u = {u1, u2 }. pb («emails»|z) = 1.0, поскольку «emails» присутствует в обоих высказываниях. Аналогичным образом, pb («unread»|z) = 0.5 и pb («meeting»|z) = 0.0.

В семантической сети существует три основных операции на уровне вершин:
аннотирование, компоновка и интерполяция.

ANNOTATE (аннотировать) значит собирать высказывания для перефразирования канонической команды вершины z с помощью краудсорсинга и оценивать эмпирическое распределение методом максимального правдоподобия.

COMPOSE (компоновать) пытается вывести языковую модель на основе композиций вычислить ожидаемое распределение . Как мы покажем экспериментально, — это композиция для z. Если мы исходим из предположения о том, что соответствующие высказывания характеризуются этой же композиционной связью, то должно раскладываться на :



где f является композиционной функцией. Для распределения BoB композиционная функция будет выглядеть следующим образом:



Другими словами, если ui является высказыванием zi, u — высказыванием композиционно формирует u, то слово w не принадлежит u. Тогда и только тогда, когда оно не принадлежит какому-либо ui. Когда у z множество композиций, ?e x вычисляется отдельно, а затем усредняется. Стандартная языковая униграм-модель не приводит к естественной композиционной функции. В процессе нормализации вероятностей слов участвует длина высказываний, которая, в свою очередь, учитывает сложность вызовов API, нарушая разложение в уравнении (2). Именно поэтому мы предлагаем распределение BoB.

Пример 3. Предположим, мы подготовили аннотацию для упомянутых ранее вызовов API z1 и z2, в каждом из которых два высказывания: = {«find unread emails», «emails that are not read»} и = {«how many emails do I have», «find the number of emails»}. Мы оценили языковые модели и . Операция композиции пытается оценить , не запрашивая . Например, для слова «emails», pb («emails»|z1) = 1.0 и pb («emails»|z2) = 1.0, таким образом, из уравнения (3) следует, что pb («emails»|z12) = 1.0, то есть мы считаем, что это слово будет входить в любое высказывание z12. Аналогично, pb («find»|z1) = 0.5 и pb («find»|z2) = 0.5, таким образом, pb («find»|z12) = 0.75. Слово имеет хорошие шансы быть сгенерированным из любого z1 или z2, поэтому его вероятность для z12 должна быть выше.

Разумеется, высказывания не всегда сочетаются композиционно. Например, несколько элементов в формализованном представлении смысловой структуры могут быть переданы одним словом или фразой на естественном языке, это явление получило название сублексической композиционности. Один такой пример показан на рисунке 3, где три параметра — TOP(1), FILTER(start>now) и ORDERBY(start,asc) — представлены одним словом «next». Тем не менее невозможно получить такую информацию без аннотирования вызова API, поэтому сама проблема напоминает проблему курицы и яйца. При отсутствии такой информации разумно придерживаться принятого по умолчанию предположения, что высказывания характеризуются той же композиционной связью, что и вызовы API.

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

INTERPOLATE (интерполяция) объединяет всю доступную информацию о z, то есть аннотированные высказывания z и информацию, полученную из композиций, и получает более точную оценку путем интерполяции и .



Балансовый параметр ? контролирует компромиссные решения между аннотациями
текущей вершины, которые точны, но достаточны, а информация, полученная из композиций, основанных на предположении о композиционности, может быть не такой точной, зато она обеспечивает более широкий охват. В определенном смысле, служит той же цели, что и сглаживание в языковом моделировании, позволяющее лучше оценить распределение вероятностей при недостаточности данных (аннотаций). Чем больше , тем больше вес в . Для корневой вершины, не имеющей композиции, = . Для неаннотированной вершины = .

Далее мы опишем алгоритм обновления семантической сети, то есть вычисления для всех z (алгоритм 1), даже если была аннотирована лишь небольшая часть вершин. Мы предполагаем, что значение уже обновлено для всех аннотированных узлов. Спускаясь сверху вниз по слоям, мы последовательно вычисляем и для каждой вершины z. Сначала необходимо обновить верхние слои, чтобы можно было вычислить ожидаемое распределение вершин нижнего уровня. Мы аннотировали все корневые вершины, поэтому можем вычислить для всех вершин.

Алгоритм 1. Update Node Distributions of Semantic Mesh

3.3 Оптимизация краудсорсинга

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

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

Прежде чем углубиться в обсуждение подходов к вычислению эффективной политики, предположим, что она у нас уже есть, и дадим высокоуровневое описание нашего алгоритма краудсорсинга (алгоритм 2), чтобы описать сопутствующие методы. Говоря более конкретно, мы сначала аннотируем все корневые вершины, чтобы оценить распределение для всех вершин в Z (строка 3). При каждой итерации мы обновляем распределения вершин (строка 5), вычисляем
политику на основе текущего состояния семантической сети (строка 6), выбираем неаннотированную вершину с максимальной оценкой (строка 7), и аннотируем вершину и результат в новом состоянии (строка 8). В практическом плане, можно аннотировать несколько вершин в рамках итерации, чтобы повысить эффективность.


Рисунок 6. Дифференциальное распространение. z12 и z23 представляют собой изучаемую пару вершин. w — оценка, рассчитанная на основе d(z12, z23), и распространяется итеративно снизу вверх, вдвое в каждой итерации. Оценкой для вершины будет абсолютная разница его оценок из z12 и z23 (поэтому дифференциальное). z2 получает оценку 0, поскольку это общая родительская сущность для z12 и z23; аннотирование в данном случае будет мало полезным с точки зрения обеспечения различимости z12 и z23.

В широком смысле решаемые нами задачи можно отнести к проблеме активного обучения, мы ставим перед собой цель определить подмножество примеров для аннотирования, чтобы получить обучающий набор, который может повысить результативность обучения. Однако несколько ключевых различий не позволяют непосредственно применять классические активные методы обучения, такие как «неопределенность отбора». Обычно в процессе активного обучения обучаемый, который в нашем случае был бы интерфейсом NLI, пытается изучить сопоставление f: X > Y, где X — входной образец пространства, состоящий из небольшого набора маркированных и большого количества немаркированных образцов, а Y обычно представляет собой набор маркеров класса.

Обучаемый оценивает информативность немаркированных примеров и выбирает наиболее информативный, чтобы получить метку в Y от краудсорсинговых работников. Но в рамках решаемой нами проблемы задача аннотирования ставится по-другому. Нам нужно выбрать экземпляр из Y, большого пространства вызовов API, и попросить краудсорсинговых работников промаркировать его, указав образцы в X, пространстве высказываний. Кроме того, мы не привязаны к конкретному обучаемому. Таким образом, мы предлагаем новое решение для рассматриваемой проблемы. Мы черпаем вдохновение из многочисленных источников по вопросам активного обучения.

Сначала мы определим цель, на основе которой будет оцениваться информативность узлов. Очевидно, мы хотим, чтобы различные вызовы API можно было отличить. В семантической сети это означает, что распределения различных вершин имеют явные отличия. Для начала мы представляем каждое распределение как n-размерный вектор , где n = || — размер словаря. Под определенной метрикой векторного расстояния d (в своих экспериментах мы используем расстояние между векторами рL1) мы понимаем , то есть расстояние между двумя вершинами равно расстоянию между их распределениями.

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



где указывает на первые K пар вершин, если мы ранжируем все пары узлов по расстоянию в порядке возрастания.

Алгоритм 2. Iteratively Annotate a Semantic Mesh with a Policy



Алгоритм 3. Compute Policy based on Diferential Propagation



Алгоритм 4. Recursively Propagate a Score from a Source Node to All Its Parent Nodes



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

В противном случае вершина должна получить высокую оценку, и чем пара вершин ближе, тем выше должна быть оценка. Например, если расстояние между вершинами «unread emails about PhD application» и «how many emails are about PhD application» небольшое, то аннотировать их родительскую вершину «emails about PhD application» не имеет большого смысла с точки зрения обеспечения различимости этих вершин. Целесообразнее аннотировать родительские узлы, которые не будут для них общими: «unread emails» и «how many emails».

Пример такой ситуации показан на рисунке 6, а ее алгоритм — это алгоритм 3. В качестве оценки мы берем обратную величину расстояния узла, ограниченную константой (строка 6), поэтому наиболее близкие пары вершин оказывают наибольшее влияние. Работая с парой вершин, мы параллельно присваиваем оценку каждой вершины всем ее родительским вершинам (строка 9, 10 и алгоритм 4). Оценка неаннотированной вершины — это абсолютная разница оценок соответствующей пары вершин с суммированием по всем парам вершин (строка 12).

Естественно-языковой интерфейс

Чтобы оценить предложенный фреймворк, необходимо обучить модели NL2API с использованием собранных данных. На данный момент готовая модель NL2API недоступна, но мы адаптируем две апробированные модели NLI из других областей с целью их применения к API.

Модель извлечения на базе языковой модели

Опираясь на недавние разработки в области NLI для баз знаний, мы можем рассматривать создание NL2API в разрезе проблемы извлечения информации, чтобы адаптировать модель извлечения на базе языковой модели (LM) под наши условия.

Для высказывания u необходимо найти вызов API z в семантической сети с наилучшим соответствием для u. Сначала мы преобразуем распределение BoB каждого вызова API z в языковую униграм-модель:



где мы используем аддитивное сглаживание, и 0 ? ? ? 1 — это параметр сглаживания. Чем больше значение , тем больше вес слов, которые еще не были проанализированы. Вызовы API можно ранжировать по их логарифмической вероятности:



(при условии равномерного априорного распределения вероятностей)



Вызов API с самым высоким рейтингом используется как результат моделирования.

Модуль перефразирования Seq2Seq

Нейронные сети получают все большее распространение в качестве моделей для NLI, при этом модель Seq2Seq лучше остальных подходит для этой цели, поскольку позволяет естественным образом обрабатывать входные и выходные последовательности переменной длины. Эту модель мы адаптируем для NL2API.

Для входной последовательности e , модель оценивает условное распределение вероятностей p(y|x ) для всех возможных выходных последовательностей . Длины T и T? могут различаться и принимать любые значения. В NL2API, x является выходным высказыванием. y может быть сериализованным вызовом API либо его канонической командой. Мы будем использовать канонические команды в качестве целевых выходных последовательностей, что фактически превращает нашу проблему в проблему перефразирования.

Кодировщик, реализованный в виде рекуррентной нейронной сети (RNN) с управляемыми рекуррентными блоками (GRU), сначала представляет x как вектор фиксированного размера,



где RN N является кратким представлением для применения GRU ко всей входной последовательности, маркер за маркером, с последующим выводом последнего скрытого состояния.

Декодер, который также представляет собой RNN с GRU, принимает h0 как начальное состояние и обрабатывает выходную последовательность y, маркер за маркером, чтобы сгенерировать последовательность состояний,



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



Конечная условная вероятность, которая позволяет оценить, насколько хорошо каноническая команда y перефразирует входное высказывание x, — . Вызовы API затем ранжируются по условной вероятности их канонической команды. Рекомендуем ознакомиться с источником, где процесс обучения модели описан более подробно.

Эсперименты

Экспериментальным путем мы изучаем следующие предметы исследования: [ПИ1]: Можем ли мы с помощью предлагаемого фреймворка собрать качественные обучающие данные по разумной цене? [ПИ2]: Обеспечивает ли семантическая сеть более точную оценку языковых моделей, чем оценка максимального правдоподобия? [ПИ3]: Позволяет ли стратегия дифференциального распространения повысить эффективность краудсорсинга?

Краудсорсинг

Мы применяем предложенный фреймворк к двум веб-API от Microsoft — GET-Events и GET-Messages — которые предоставляют доступ к службам расширенного поиска электронных писем пользователя и событий календаря соответственно. Мы создаем семантическую сеть для каждого API, перечисляя все вызовы API (раздел 3.1) и до четырех параметров в каждом. Распределение вызовов API показано в таблице 2. Мы используем внутреннюю платформу для краудсорсинга, подобную Amazon Mechanical Turk. Чтобы обеспечить гибкость эксперимента, мы аннотировали все вызовы API с максимум тремя параметрами.

Однако в каждом конкретном эксперименте мы будем использовать только определенное подмножество для обучения. Каждый вызов API аннотируется 10 высказываниями, и за каждое высказывание мы платим 10 центов. К аннотированию привлекается 201 участник, все они прошли отбор с помощью квалификационного теста. В среднем на перефразирование канонической команды у исполнителя уходило 44 секунды, поэтому мы можем получить 82 обучающих примера от каждого исполнителя в час, и стоимость составит 8,2 доллара, что, по нашему мнению, совсем немного. Что касается качества аннотаций, мы вручную проверили 400 собранных высказываний и обнаружили, что доля ошибок составляет 17,4 %.

Основные причины ошибок связаны с отсутствием определенных параметров (например, исполнитель не указал параметр ORDERBY или a COUNT parameter) либо неправильным толкованием параметров (например, указано ранжирование по возрастанию, когда на самом деле идет ранжирование по убыванию). На приведенные примеры приходится около половины ошибок. Доля ошибок сопоставима с таковой у других краудсорсинговых проектов в области NLI. Таким образом, мы считаем, что ответ на [ПИ1] положительный. Качество данных можно улучшить путем привлечения независимых краудсорсинговых работников для постпроверки.

Кроме того, мы получили аннотированное независимое тестовое множество, сформированное случайным образом из всей семантической сети и включающее, в том числе, вызовы API с четырьмя параметрами (табл. 3). Каждый вызов API в тестируемом множестве изначально имел три высказывания. Мы провели проверку и отсеяли высказывания с ошибками, чтобы повысить качество тестирования. Итоговое тестовое множество включало 61 вызов API и 157 высказываний для GET-Messages, а также 77 вызовов API и 190 высказываний для GET-Events. В обучающие данные вошли не все тестовые высказывания, кроме того, многие тестовые вызовы API (например, вызовы с четырьмя параметрами) не были задействованы в обучении, следовательно, тестовое множество было очень сложным.


Таблица 2. Распределение вызовов API.


Таблица 3. Распределение тестового множества: высказывания (вызовы).

Постановка эксперимента

В качестве оценочного показателя мы используем точность, то есть долю тестовых высказываний, для которых максимальный прогноз оказался верным. Если не указано иное, балансовый параметр ? = 0,3, а параметр сглаживания LM ? = 0,001. Число пар вершин K, используемых при дифференциальном распространении, равно 100 000. Установленное значение для состояния, размера, кодировщика и декодера в модели Seq2Seq — 500. Параметры отбираются по результатам предварительного исследования на отдельном проверочном множестве (независимо от тестирования).

Семантическая сеть не только полезна для оптимизации краудсорсинга как первая в своем роде модель краудсорсингового процесса для NLI, она имеет и технические преимущества. Поэтому мы будем оценивать семантическую сеть и алгоритм оптимизации отдельно.

Оценка семантической сети

Общая эффективность. В этом эксперименте мы оцениваем модель семантической сети и, в частности, эффективность операций композиции и интерполяции с точки зрения оптимизации оценки языковых моделей. Качество языковых моделей может оцениваться по эффективности модели LM: чем точнее оценка, тем выше эффективность. Мы используем несколько обучающих множеств, соответствующих различным множествам аннотированных вершин. ROOT — это корневые вершины. TOP2 = ROOT + все узлы слоя 2; а TOP3 = TOP2 + все узлы слоя 3. Это позволяет провести оценку семантической сети с помощью разного количества обучающих данных.

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

Добавив композицию в MLE, мы можем оценить ожидаемое распределение для неаннотированных вершин, но по-прежнему используется для аннотированных вершин, то есть интерполяция отсутствует. Это позволяет значительно оптимизировать API и множества обучающих данных. При наличии всего 16 аннотированных вызовов API (ROOT) простая модель LM с SeMesh может превзойти по эффективности более сложную модель Seq2Seq с более чем сотней аннотированных вызовов API (TOP2) и приблизиться к модели, содержащей около 500 аннотированных вызовов API (TOP3).

Эти результаты ясно показывают, что языковые модели, оцениваемые с помощью операции композиции, достаточно точны, достоверность допущения композиционности высказываний (раздел 3.2) доказана эмпирическим путем. Можно отметить, что работать с GET-Events в общем случае сложнее, чем с GET-Messages. Это обусловлено тем, что GET-Events использует
больше команд, которые привязаны ко времени, и события могут относиться к будущему или прошлому, тогда как электронные письма всегда относятся только к прошлому.


Таблица 4. Общая точность в процентах. Операции семантической сети значительно оптимизируют простую модель LM, делая ее лучше более сложной модели Seq2Seq, когда объем обучающих данных достаточно невелик. Результаты доказывают, что семантическая сеть обеспечивает точную оценку языковых моделей.

Эффективность LM + композиция снижается, когда мы используем больше обучающих данных, что говорит о нецелесообразности использования только и необходимости комбинирования с ?em with . Когда мы интерполируем и , то добиваемся улучшений везде, за исключением уровня ROOT, где ни одной из вершин не может быть одновременно и . В отличие от композиции, чем больше обучающих данных мы используем для интерполяции, тем лучше результат операции. В целом семантическая сеть обеспечивает значительную оптимизацию по сравнению с базовыми показателями MLE. Таким образом, мы считаем, что ответ на [ПИ2] положительный.

Лучшие показатели точности лежат в диапазоне от 0,45 до 0,6: они не очень высоки, но находятся на одном уровне с показателями современных методов применения NLI к базам знаний. Это отражает сложность проблемы, так как модель должна точно найти лучший среди тысяч связанных вызовов API. Путем сбора дополнительных высказываний для каждого вызова API (см. также рисунок 7) и использования более совершенных моделей, таких как двунаправленные RNN с механизмом внимания, можно еще больше повысить эффективность. Эти вопросы мы оставим для будущей работы.

Воздействие гиперпараметров. Теперь рассмотрим влияние двух гиперпараметров на семантическую сеть: количество высказываний |u | и балансовый параметр ?. Здесь мы по-прежнему опираемся на эффективность модели LM (рисунок 7). Высказывания выбираются случайным образом, когда |u | < 10, и на выход модели выдаются средние оценки за 10 повторных прогонов. Мы показываем результаты для GET-Events, для GET-Messages они аналогичны.

Неудивительно, что чем больше высказываний мы аннотируем для каждой вершины, тем выше эффективность, хотя прирост постепенно уменьшается. Поэтому, при наличии такой возможности, рекомендуется собирать дополнительные высказывания. С другой стороны, эффективность модели практически не зависит от ?, поскольку этот параметр лежит в допустимом диапазоне ([0.1, 0.7]). Влияние параметра ? усиливается при увеличении числа аннотированных вершин, что вполне ожидаемо, поскольку интерполяция затрагивает только аннотированные вершины.

Оптимизация краудсорсинга

В этом эксперименте мы оцениваем эффективность применения предложенной стратегии дифференциального распространения (DP) для оптимизации краудсорсинга. Различные стратегии краудсорсинга итеративно отбирают вызовы API для аннотирования. При каждой итерации каждая стратегия выбирает 50 вызовов API, а затем они аннотируются, и две модели NL2API используют накопленные аннотированные данные для обучения.

Наконец, модели оцениваются на тестовом множестве. Мы используем базовую модель LM, которая не зависит от семантической сети. Лучшая стратегия краудсорсинга должна обеспечивать лучшую эффективность модели для такого же количества аннотаций. Вместо аннотирования вершин на лету с помощью краудсорсинга мы используем аннотации, собранные ранее в качестве пула кандидатов (раздел 5.1), поэтому все стратегии будут выбираться только из имеющихся вызовов API с тремя параметрами.


Рисунок 7. Воздействие гиперпараметров.


Рисунок 8. Эксперимент по оптимизации краудсорсинга. Слева: GET-Events. Справа: GET-Messages

В качестве базовой стратегии принимаем стратегию breadth first (BF), которая в нисходящем направлении постепенно аннотирует каждый слой семантической сети. Это напоминает стратегию из. Так мы получаем базовые показатели. Вызовы API верхнего уровня обычно важнее, поскольку они представляют собой композиции вызовов API нижнего уровня.

Результаты эксперимента показаны на рисунке 8. Для обеих моделей NL2API и обоих API стратегия DP в общем случае обеспечивает повышение эффективности. Когда мы аннотируем только 300 вызовов для каждого API, применительно к модели Seq2Seq, DP обеспечивает абсолютный прирост точности более 7 % для обоих API. При исчерпании пула кандидатов два алгоритма сходятся, что ожидаемо. Результаты показывают, что DP позволяет определить вызовы API, имеющие высокую ценность для обучения NL2API. Таким образом, мы считаем, что ответ на [ПИ3] положительный.

Смежные направления исследований

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

Достаточно хорошо изучены вопросы применения NLI к реляционным базам данных, базам знаний и веб-таблицам, но в отношении API исследований практически нет. Разработчики NL2API сталкиваются с двумя основными проблемами: отсутствие единого семантического представления для API и, отчасти именно из-за этого, отсутствие обучающих данных. Мы работаем над решением обеих проблем. Мы предлагаем унифицированное семантическое представление API на основе стандарта REST и принципиально новый подход к сбору обучающих данных в этом представлении.

Сбор обучающих данных для NLI. Существующие решения по сбору обучающих данных для NLI обычно придерживаются принципа «лучшее из возможного». Например, в вопросы на естественном языке собираются с помощью Google Suggest API, а авторы получают команды и соответствующие вызовы API с сайта IFTTT. Исследователи сравнительно недавно начали изучать подходы к созданию NLI, подразумевающие сбор обучающих данных с помощью краудсорсинга. Краудсорсинг уже стал привычной практикой в различных исследованиях, связанных с языком.

Однако мало изучены вопросы его применения для создания интерфейсов NLI, позволяющих решать уникальную и интригующую задачу моделирования взаимодействия между представлениями на естественном языке и формализованными представлениями смысловой структуры. Большая часть подобных исследований связана с применением NLI к базам знаний, где формализованное представление выражено логическими формами в определенном логическом формализме. Авторы предлагают преобразовывать логические формы в канонические команды с помощью грамматики, а в описаны методы уточнения сгенерированных логических форм и отсеивания тех, что не соответствуют значимому вопросу на естественном языке.

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

Семантические методы для веб-API. Существует ряд других семантических методов, разработанных для веб-API. Например, семантические описания веб-API извлекаются в для упрощения композиции API, в то время как в предлагается механизм поиска веб-API для составления композиций. Технология NL2API потенциально позволит решать такие проблемы, например, при использовании в виде единой поисковой системы для поиска API.

Выводы и направления дальнейших исследований

Мы сформулировали проблему создания естественно-языкового интерфейса для веб-API (NL2API) и предложили комплексный фреймворк для разработки NL2API с нуля. Одним из ключевых технических результатов работы является принципиально новый подход к сбору обучающих данных для NL2API на основе краудсорсинга. Работа открывает несколько направлений для дальнейших исследований: (1) Языковая модель. Как путем обобщения перейти от отдельных слов к более сложным языковым единицам, например, фразам? (2) Оптимизация краудсорсинга.

Как использовать семантическую сеть максимально эффективно? (3) Модель NL2API. Например, фреймворк для заполнения слотов в голосовых диалоговых системах оптимально подходит для нашего представления кадров API. (4) Композиция API. Как собирать обучающие данные при одновременном использовании нескольких API? (5) Оптимизация в ходе взаимодействия: как продолжить улучшение NL2API в процессе взаимодействия с пользователем после первоначального обучения?