Соседи, сети и системы: почему обучение в реальном мире требует комбинации параметрических и непараметрических методов

Короткая версия доклада:

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

Метод ближайших соседей – один из самых старых алгоритмов машинного обучения (machine learning, ML), до сих пор широко применяемый и продолжающий улучшаться. Фактически он является основой промышленного ML. Помимо классического варианта с поиском соседей и присвоением им метки, естественным продолжением метода являются алгоритмы, основанные на ядрах и опорных векторах. Все современные модификации метода соседей решают две связанные между собой проблемы – как увеличить его точность (проблема похожести) и как повысить его скорость (проблема поиска похожих). Обычно под похожестью понимают геометрические представления в эвклидовом понимании, с тремя свойствами метрики – симметрией, нулём к самому себе и треугольником, однако, как установил Амос Тверски в 1977 г., в представлении людей эти функции похожести не являются метриками.

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

Развитие сетей особенно сильно повлияло на поиск – проблема стоит так: если есть запрос и есть документ, как может читаться похожесть? Можно использовать строковые состояния, но эффективнее выучить функцию похожести, и архитектура для этого основана на так называемых «сиамских сетях», в которых каждый из объектов прогоняется через свою сеть, и потом их представления сравниваются. В случае похожести запроса на странице важно выучивать другие энкодеры, так как там другой домен и другое представление. Вышедший в прошлом году поисковый алгоритм Яндекса «Королев» также является вариацией обучения функций похожести для текстов.

Что касается проблемы эффективности, то для лучшей работы соседей необходимо их быстро находить, что не всегда возможно сделать простым перебором. Соответственно, нужно каким-то образом проиндексировать набор для поиска запроса или ближайших к нему соседей. Индексация осуществляется путем разбивки пространства на деревья и ячейки (листы), где и находятся соседи – методы k-d trees, R trees, VP trees. Однако при большой размерности деревья теряют эффективность , и нам на помощь приходят примерные методы индексации, которые через хэшинг, кластеринг и пути на графе позволяют эффективно находить локальных соседей. Они работают по одному двухходовому шаблону – сначала проецируются индексируемые данные и сам запрос, а затем в этом низкоразмерном представлении можно уже индексировать, используя деревья и другие методы из баз данных.

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

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

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

Алиса уникальна наличием «болталки» - возможностью диалога на общие темы, в которых помощник, в отличие от западных аналогов, проявляет изрядное чувство юмора и даже дерзость, иногда очень рискованную. Ответы Алисы основаны на изучении огромного корпуса диалогов в сети, и даже многоступенчатая фильтрация не дает гарантии появления оскорбительных ответов со стороны помощника. Неудачный опыт других компаний показал, что для профилактики возможных проблем необходимо быть готовым бороться с ними в режиме реального времени, учитывая, что запрещенный и чувствительный контент практически бесконечен. Обучение для фильтрации «плохих» ответов осложнено тем, что Алиса – многокомпонентная система с широким кругом участников. Для фильтрации плохого контента мы применяем метод соседей путем добавлениям новых примеров, что не требует изменений кода и бинарников. Однако возникает вопрос: как можно правильно комбинировать ансамбли из соседей, которые позволят быстро реагировать и давать максимальную точность? Проблема требует внимания ученых, мы в Яндексе этой проблемой занимаемся, надеемся на участие и других исследователей.