Как создать свой алгоритм поиска локаций, используя AI
Статья создана в соавторстве с Danil Kuhta.
В этом материале описан практический опыт решения задачи ранжирования локаций с использованием машинного обучения. Статья в основном рассчитана на начинающих разработчиков. Однако будет интересна и более опытным специалистам, которым нужен готовый рецепт, как на базе бесплатных инструментов сделать аналог 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, который делал обучение и давал в результате модель, которая использовалась в мобильном приложении.
Перед началом обучения мы решили реорганизовать сбор входных данных, пересмотреть и изменить некоторые вводные параметры, чтобы не загромождать ее лишними данными.
В результате мы получили
Динамика изменения настроек
Ниже приведены две таблицы со значениями, которые помогают понять, как показатель верных ответов зависит от конфигураций нейросети.
В Таблице № 1 представлены результаты обучения сети путем изменения вводимых параметров:
Таблица № 1
| Динамика изменения вводимых параметров | Показатель верных ответов |
| + Сопоставление поискового запроса с названиями локаций | 88% |
| + Сопоставление запроса с основными типами локаций | 91% |
| + Расстояние до сравниваемых локаций | 92.5% |
| + Предварительная обработка запроса (отделение названия локации от его адреса) | 94% |
| + Сопоставление запроса с адресными составляющими найденных локаций | 94% |
Что касается тех входных данных, которые использовались для сравнения строк, в Таблице № 2 можно проследить динамику изменения показателя правильных ответов после добавления дополнительных параметров.
Таблица № 2
| Параметр | Показатель верных ответов |
| + Редакционное расстояние (расстояние Левенштейна) | 68% |
| + Наибольшая общая подстрока | 92.5% |
| + Наибольшая общая подпоследовательность | 92.5% |
| + Полное совпадение с запросом | 89.5% |
| + Количество совпадающих слов | 94% |
Стоит отметить, что параметры «полное совпадение с запросом» и «количество совпадающих слов» по отдельности давали результаты хуже, чем в паре.
Кроме того, мы пришли к выводу, что количество скрытых слоев в нейросети не влияет на правильность ответов: проверив всё с одним, двумя слоями или даже без них — повлиять на показатель нам так и не удалось.
Хочется также упомянуть, что никаких специфических правил для настройки и обучения «классической» нейронной сети не существует. Это решается только эмпирическим путем.
Выводы
Нейронные сети и TensorFlow отлично справились с теми моментами построения обучения и реализации алгоритмов ИИ, где другие средства оказались неэффективны.
Для решения нашей задачи мы разработали метод нахождения подсказок в списке конкретных структур данных на основе поискового запроса пользователя. Нам удалось достичь показателя верных ответов в 94%, что для приложения вполне приемлемо.
Нейронные сети помогают решать широкий спектр задач, где трудно применить стандартную логику «if — else». Или же её реализация будет сложной, и она будет сильно зависеть от любых изменений в контексте потенциальной регрессии.
P. S. Дополнительный бонус нейросети — простой код бережет нервы программисту :)
