Поиск в Интернете станет точнее благодаря российским ученым

Разработчики МФТИ и Вычислительного центра РАН предложили новый метод автоматического построения ранжирующих моделей. Эти модели используются для того, чтобы обработать запрос от пользователя на поиск информации в коллекциях документов или в Интернете. Этот метод значительно увеличит скорость построения моделей. Результаты исследования опубликованы в журнале Expert Systems with Applications.

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

«Постановка задачи предполагала использование только коллекций документов и поисковых запросов. Не допускалось использование никакой внешней информации о контексте, в котором выполнялся поиск. Такая задача имеет наиболее общий характер. Ранжирующие модели, предназначенные для быстрого и точного поиска информации, используются во многих областях — от спам-фильтров до колл-центров», — прокомментировал соавтор работы, студент кафедры интеллектуальных систем МФТИ Андрей Кулунчаков.

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

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

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

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

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