DSE Fest — технично и понятно про data science для разработчиков. Первые доклады уже на сайте >>
×Закрыть

Как создать свой алгоритм поиска локаций, используя AI

Статья создана в соавторстве с Mike Makarov.

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

Коротко о поиске локаций

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

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

Google-решению есть и альтернативы, такие как:

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

Предварительная обработка запроса

Чтобы система выдавала более качественные результаты, сам поисковый запрос нужно предварительно обработать — очистить от лишних адресных составляющих. У Android для этого есть встроенный «Геокодер» (Geocoder), который способен обрабатывать прямое и обратное геокодирование, а это, в свою очередь, помогает выстроить алгоритм удаления тех самых лишних компонентов из каждого поискового запроса.

Геокодер работает по следующему принципу: составляется список адресов для каждого поискового запроса, в котором этот запрос сравнивается с каждой составляющей адреса. Таким образом, лишние составляющие легко удаляются.

Магия искусственного интеллекта

Так почему Google выдает результаты лучше других? Как он обрабатывает запрос? Разработчики Google в свой поисковик встроили собственный алгоритм искусственного интеллекта (ИИ), который помогает выдавать нужные пользователю результаты.

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

Как этого можно достичь в контексте поиска мест: задача «Hello, world!», в Machine Learning — ответить на вопрос «Какое число нарисовано на картинке?», а возможные ответы — цифры «0, 1, 2... 9». В качестве входного параметра используется картинка.

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

Как применить ИИ для поиска мест

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая реализация

Попыток претворить в жизнь нашу идею было несколько. Первый раз было принято решение использовать библиотеку FANN (Fast Artificial Neural Network — быстрая искусственная нейронная сеть). Она имеет открытый исходный код и позволяет применять многослойные искусственные нейросети в C.

Главные особенности библиотеки состоят в следующем:

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

Во второй раз мы использовали TensorFlow. Среди его преимуществ:

  • быстрая работа, для обработки можно использовать GPU;
  • есть вся документация, написана доступно и понятно;
  • есть инструменты для визуализации.

Первая нейросеть

Для начала мы интегрировали библиотеку FANN в приложение Android с помощью NDK.

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

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

Проверялось обучение так: все собранные данные делились на две части, в пропорции 70% / 30%, где 70% было отведено под само обучение, а оставшиеся 30% — уже на проверку. Для наочного отображения результатов после каждого этапа рассчитывался параметр, который показывал процент правильных ответов из набора проверочных данных.

Лучший результат во время первого обучения нейросети составил 75% правильных ответов. Такой низкий показатель объясняется большим количеством помех во входных данных. После того как мы начали отбирать информацию более тщательно, коэффициент заметно улучшился.

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

После повторного сбора данных нейросеть стала выдавать 94% правильных ответов. На этом было решено остановиться и приступить ко второй попытке разработки нейросети.

Вторая нейросеть

Здесь реализацию проекта мы поделили на две части.

В первой использовали предыдущие наработки по алгоритму, но уже с применением Android SDK и Java. Эта часть отвечала за сбор и подготовку данных для обучения. Вторая же была полностью написана в виде скрипта на Python, который делал обучение и давал в результате модель, которая использовалась в мобильном приложении.

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

В результате мы получили 93-94% правильных ответов.

Динамика изменения настроек

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

В Таблице № 1 представлены результаты обучения сети путем изменения вводимых параметров:

Таблица № 1

Динамика изменения вводимых параметровПоказатель верных ответов
+ Сопоставление поискового запроса с названиями локаций88%
+ Сопоставление запроса с основными типами локаций91%
+ Расстояние до сравниваемых локаций92.5%
+ Предварительная обработка запроса (отделение названия локации от его адреса)94%
+ Сопоставление запроса с адресными составляющими найденных локаций94%

Что касается тех входных данных, которые использовались для сравнения строк, в Таблице № 2 можно проследить динамику изменения показателя правильных ответов после добавления дополнительных параметров.

Таблица № 2

ПараметрПоказатель верных ответов
+ Редакционное расстояние (расстояние Левенштейна)68%
+ Наибольшая общая подстрока92.5%
+ Наибольшая общая подпоследовательность92.5%
+ Полное совпадение с запросом89.5%
+ Количество совпадающих слов94%

Стоит отметить, что параметры «полное совпадение с запросом» и «количество совпадающих слов» по отдельности давали результаты хуже, чем в паре.

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

Хочется также упомянуть, что никаких специфических правил для настройки и обучения «классической» нейронной сети не существует. Это решается только эмпирическим путем.

Выводы

Нейронные сети и TensorFlow отлично справились с теми моментами построения обучения и реализации алгоритмов ИИ, где другие средства оказались неэффективны.

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

Нейронные сети помогают решать широкий спектр задач, где трудно применить стандартную логику «if — else». Или же её реализация будет сложной, и она будет сильно зависеть от любых изменений в контексте потенциальной регрессии.

P. S. Дополнительный бонус нейросети — простой код бережет нервы программисту :)

LinkedIn

29 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Спасибо за статью. Хочу добавить на счет следующего утверждения:

Хочется также упомянуть, что никаких специфических правил для настройки и обучения „классической” нейронной сети не существует. Это решается только эмпирическим путем.

Вот вспомнил набор рекомендаций по настройке обучения сети с курса от гугл — developers.google.com/...​ine-learning/crash-course

Is There a Standard Heuristic for Model Tuning?
This is a commonly asked question. The short answer is that the effects of different hyperparameters are data dependent. So there are no hard-and-fast rules; you’ll need to test on your data.

That said, here are a few rules of thumb that may help guide you:

Training error should steadily decrease, steeply at first, and should eventually plateau as training converges.
If the training has not converged, try running it for longer.
If the training error decreases too slowly, increasing the learning rate may help it decrease faster.
But sometimes the exact opposite may happen if the learning rate is too high.
If the training error varies wildly, try decreasing the learning rate.
Lower learning rate plus larger number of steps or larger batch size is often a good combination.
Very small batch sizes can also cause instability. First try larger values like 100 or 1000, and decrease until you see degradation.
Again, never go strictly by these rules of thumb, because the effects are data dependent. Always experiment and verify.

Есть ли у вас примеры данных которые подавались на вход и какой результат в итоге ожидался ?

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

Может цель была получить что-то скромнее скажем ввод «митро шлявка» интерпретировать как «метро шулявка» ?

Як плануєте монетизовувати цей розв’язок?

К сожалению на данном этапе мы не можем разглашать такую информацию.

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

И вам не показалось это странным?

Це може означати, що занадто мало тренувальних даних для вибраної кількості вхідних атрибутів.

Может у них данные линейно сепарируемые, тогда скрытые слои и не нужны)

Но тогда и нейронка не нужна, если я правильно понимаю нейронки. SVM можно заюзать.

If-then-else можно заюзать

В смысле дерево решений? Можно.

Можно, конечно, но наверное сложно. Тут же как раз идея была и в том чтобы задачу подбора коэффициентов важности входных параметров поручить AI.

Random forest це такий самий АІ як і застосована ANN.

Но они же не исследовательской задачей занимались, а коммерческой — здесь вообще круто, что они хоть немного происследовали.

Ну добре, я не проти, якщо задача комерційна, то як вони збираються це монетизовувати?

Спроси их. Я почем знаю.

А зачем использовали нейросети для данной задачи? Регрессия, Random Forest или на худой конец XgBoost решили бы вам проблему с намного меньшими трудозатрами. Ансамбли деревьев всеядны, устойчивы к переобучению, хорошо интерпретируются (например, важность фич вы могли бы просто вытянуть после обучения, а не подавать их на вход по очереди), и дают на подобных табулярных задачах точность даже выше, чем «капризные» нейросети.

Нет, нейросети сейчас быстрее и проще заюзать. Python и TF и дергай 3 функции.

Да ладно. Речь же не об API, а о том, чтобы получить на выходе что-то вменяемое

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

Да. По факту можно было бы еще проще системы использовать.

Странным — нет. Немного обидным — да) Это нормальная ситуация, когда оказывается, что для решения проблемы подходит более простая система чем предполагалось вначале. ANN тут по факту оказался оверкилом, но для унификации решения, когда ресурсы не критичны почему бы и нет )

Странным — нет

А должно было бы. Потому что ваша модель не имеет ни практической, ни теоретической ценности. Как и эта статья, в следствии.

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

Т.е. по вашему если проблема с использованием машинного обучения успешно решается простой системой, то она не имеет практической ценности? )

Да при чём тут простота? Практическая ценность — это соотношение вложенных сил к итоговому выхлопу. Вы сами признаёте, что использование нейросетей — это оверкилл. Так в чём простота?
Инженерный/научный подход в данной области подразумевает наличие шагов по исследованию данных и базовых экспериментов с реально простыми моделями. После чего приходит понимание, что из себя представляют данные (самое важное в ML, к слову), какие алгоритмы могут зайти, как под них готовить данные, как обучать и контролировать качество.
В вашем случае вы взяли нечто максимально хайповое, что-то положили на вход, что-то ожидали на выходе... Потом внезапно выяснилось, что ваши результаты вообще не зависят от архитектуры сети... И запилили статью об искусственном интеллекте. Серьёзно?

В том, что тот же тензорфлов сейчас заюзать чаще проще, чем libsvm, спасибо гуглу.

Да и программирование в целом — это очень просто. Спасибо стековерфлоу. :)

Да. Только проблемы начинаются в нюансах конкретного энвайронмента.
Здесь ребята решили долбануть из пушки по воробьям. Получилось. Чуть поигрались с пушкой, оказалось, что и пушка не нужна. Но работа уже сделана, да и для понтов для заказчиков — целую нейронную сеть заюзали.
По сути одни плюсы для всех.
И уже плюс в том, что поисследовали немного и обнаружили, что можно и проще было (проще с точки зрения алгоритмов, а не реализации). Сейчас действительно чаще быстрее и проще нейронку заюзать, чем прямые методы настраивать и отлаживать.

Проблемы начинаются когда входные данные никакие или быстродействия железа не хватает или не на чем обучать сеть. Тут уже и требуется ручная работа.

Так что с моей стороны это была не критика, а уточнение того, что получилось.

Друзья! Пару слов о том, почему всетаки нейронная сеть была использована для решения задачи.
Изначально задача была решена простой if-then-else логикой. Но так как не всегда результаты были корректными, эта логика разрасталась, и становилась все сложнее и сложнее. Заказчик постоянно присылал примеры запросов, на которые алгоритм не давал правильных результатов. И мы вынуждены были нагромождать нашу логику дополнительными проверками. Получалось, что чинили одно, ламалось другое.
В итоге было принято решение, что нужно использовать искуственный интелект, и переложить на него эту задачу.
По поводу сложности применения нейронных сетей — я бы не сказал что это самое сложное в этой задаче. Пожалуй, собрать и организовать данные куда сложнее. И тут уже не важно, какой инструмент будет использоватся. Питоновский скрипт для TF — это всего около сотни строк кода. О какой сложности идет речь?
По поводу ненадобности скрытых слоев. Тут я думаю все зависит от количества и качества входных данных. Так как у нас входных данных было не много, по меркам нейронных сетей, то увеличение количества скрытых слоев не играло роли. Если бы цель стояла обучить нейронную сеть для более сложных запросов, то и данных нужно было бы больше, и параметров, и возможно и скрытых слоев. Мы добились хорошего результата для поставленной задачи. Данное решение является гибким и расширяемым.

Интересно, спасибо !

Подписаться на комментарии