Способ и система для ранжирования цифровых объектов на основе связанной с ними целевой характеристики

Изобретение относится к области вычислительной техники. Технический результат заключается в повышении точности ранжирования цифровых объектов на основе связанной с ними целевой характеристики. Технический результат достигается за счет выбора на основе запроса из пула цифровых объектов набора цифровых объектов, который релевантен запросу с учетом целевой характеристики цифровых объектов и может быть ранжирован согласно их целевой характеристике; получения от электронного устройства запроса фильтрации для переранжированного набора цифровых объектов из набора цифровых объектов, при этом запрос фильтрации основан на дополнительной характеристике, отличной от целевой характеристики; выбора цифровых объектов, подлежащих включению в переранжированный набор цифровых объектов, путем: определения для цифрового объекта из набора цифровых объектов соответствующего параметра объекта, указывающего на вероятность того, что включение этого цифрового объекта в переранжированный набор цифровых объектов увеличит метрику качества переранжированного набора цифровых объектов с учетом целевой характеристики цифровых объектов; выбора цифровых объектов на основе соответствующих параметров объектов; и ранжирования переранжированного набора цифровых объектов на основе соответствующих значений дополнительной характеристики для формирования переранжированного набора цифровых объектов, содержащего выбранные цифровые объекты, ранжированные согласно дополнительной характеристике. 2 н. и 18 з.п. ф-лы, 8 ил.

 

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

Уровень техники

[2] Сеть Интернет обеспечивает доступ к разнообразным ресурсам, таким как, видеофайлы, файлы изображений, аудиофайлы или веб-страницы. Для поиска этих ресурсов используются поисковые системы. Среди пользователей сети Интернет также популярны так называемые сервисы цифровых объектов, предназначенные для поиска цифровых объектов на конкретных веб-платформах. В качестве не имеющих ограничительного характера примеров таких сервисов цифровых объектов можно привести системы для поиска товаров (далее также называются коммерческими поисковыми системами), используемые на платформах электронной торговли (таких как Amazon™, eBay™ и т.п.) для поиска и покупки различных товаров, поставляемых множеством продавцов, или сервисы цифровых объектов, используемые Область техники, к которой относится изобретение

в социальных сетях (например, в социальной сети Facebook™) для поиска конкретных событий, людей или сообщений.

[3] Как и в традиционных поисковых системах (таких как поисковая система GOOGLE™, поисковая система Yahoo!™, поисковая система Baidu™ и т.п.), пользователь может выражать намерение найти конкретный цифровой объект (например, конкретный товар) путем формирования соответствующего поискового запроса для сервисов цифровых объектов и его отправки. В ответ на поисковый запрос пользователя сервис цифровых объектов определяет цифровые объекты (например, предложения от различных продавцов), соответствующие запросу пользователя, ранжирует их на основе их релевантности запросу пользователя (далее называется ранжированием на основе «целевой характеристики») и выбирает несколько наиболее подходящих цифровых объектов из ранжированного множества для представления набора этих объектов пользователю на экране пользовательского устройства.

[4] Функциональные возможности таких сервисов цифровых объектов позволяют не только представлять множество цифровых объектов, ранжированных на основе их релевантности поисковому запросу, отправленному пользователем, но и в общем случае выполнять фильтрацию представленного ранжированного множества согласно выбранному пользователем атрибуту (далее также называется ранжированием или фильтрацией на основе «дополнительных характеристик») цифрового объекта. В системах поиска товаров дополнительная характеристика может представлять собой цену цифровых объектов, позволяющую упорядочить ранжированное множество предложений по возрастанию, на основании чего пользователь может выбрать лучшее ценовое предложение.

[5] В патентной заявке US2017185602A1 (Yandex Europe AG, опубликована 29 июня 2017 г.) описаны способы и системы для формирования страницы результатов поисковой системы (SERP, Search Engine Results Page). Способ выполняется на сервере, реализующем поисковую систему и доступном через сеть связи по меньшей мере одному электронному устройству. Способ в качестве части процесса формирования списка результатов поиска, содержащего первый результат поиска и второй результат поиска, включает в себя: предсказание первого параметра интересов для первого результата поиска; предсказание второго параметра интересов для второго результата поиска; предсказание параметра полезности для первого результата поиска, выполняемое, по меньшей мере частично, на основе первого параметра интересов и второго параметра интересов; корректировка позиции первого результата поиска в ранжированном списке результатов поиска на основе предсказанного параметра полезности, в результате выполнения которой первый результат поиска размещается в скорректированной позиции в ранжированном списке результатов поиска.

[6] В патенте US8768932B1 (Google LLC, опубликован 1 июля 2014 г.) описана система для ранжирования результатов поиска. Во время работы система получает запрос, содержащий один или несколько терминов. Затем система выполняет поиск набора данных с использованием этого одного или нескольких терминов с целью получения результатов поиска. Далее система получает идентификатор атрибута для полученных результатов поиска. Затем система рассчитывает для результата поиска обобщенную оценку на основе значения этого атрибута и оценку релевантности для результата поиска. Далее система ранжирует результаты поиска на основе обобщенных оценок, связанных с результатами поиска. В конце система представляет ранжированные результаты поиска пользователю.

[7] В патенте US7577655B2 (Google LLC, опубликован 18 августа 2009 г.) описана система для ранжирования результатов. Система может получать список ссылок. Система может определять источник, с которым связана каждая ссылка, и ранжировать список ссылок, по меньшей мере частично, на основе качества определенных источников.

Раскрытие изобретения

[8] Разработчики настоящей технологии обнаружили определенные технические недостатки, связанные с существующими поисковыми системами для электронной торговли. В частности, были выявлены недостатки способов выбора цифровых объектов для переранжированного (повторно ранжированного) набора цифровых объектов.

[9] В частности, в результате фильтрации по особому атрибуту пользователю может быть представлен переранжированный набор цифровых объектов, где первые результаты из набора цифровых объектов оказываются значительно менее релевантными запросу пользователя, чем предоставленные до фильтрации первые результаты, представляющие собой результаты поиска, ранжированные на основе их целевой характеристики. Поэтому такой фильтрации может соответствовать сравнительно низкая метрика общего качества ранжирования набора цифровых объектов. Это, в свою очередь, может указывать на неудовлетворенность пользователя взаимодействием с сервисами цифровых объектов, поскольку пользователю приходится тратить больше времени и сил для поиска цифрового объекта, имеющего не только релевантную дополнительную характеристику, но и относительно высокий ранг согласно его целевой характеристике (т.е. релевантного цели поиска пользователя).

[10] Например, можно рассмотреть случай, когда пользователь желает купить смартфон iPhone™ X с использованием платформы для электронной торговли. Для этого пользователь может направить используемому сервису цифровых объектов соответствующий пользовательский поисковый запрос «iPhone X». Затем сервис цифровых объектов представляет пользователю ранжированный набор предложений, основанный на их релевантности введенному пользовательскому запросу. Пользователь может быть заинтересован в покупке телефона iPhone X по наименьшей цене. Соответственно, для поиска лучшего ценового предложения пользователь может использовать доступную на сервисе цифровых объектов фильтрацию по цене, чтобы упорядочить предложения по возрастанию (наименьшая цена в первой позиции). Тем не менее, после этого пользователь может получить переранжированный набор предложений, содержащий нерелевантные пользовательскому запросу предложения (такие как чехлы для iPhone, зарядные устройства для iPhone и т.д.), только потому, что они обычно дешевле смартфона iPhone.

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

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

[13] Согласно первому аспекту настоящей технологии реализован способ ранжирования цифровых объектов на основе связанной с ними целевой характеристики. Ранжирование выполняется в ответ на запрос, полученный от электронного устройства, связанного с пользователем. Способ выполняется сервером, доступным электронному устройству через сеть связи. Способ включает в себя: выбор на основе запроса из пула цифровых объектов набора цифровых объектов, который релевантен запросу с учетом целевой характеристики цифровых объектов и может быть ранжирован согласно их целевой характеристике; получение от электронного устройства запроса фильтрации для переранжированного набора цифровых объектов из набора цифровых объектов, при этом запрос фильтрации основан на дополнительной характеристике, отличной от целевой характеристики; выбор цифровых объектов, подлежащих включению в переранжированный набор цифровых объектов, путем определения для цифрового объекта из набора цифровых объектов соответствующего параметра объекта, указывающего на вероятность того, что включение цифрового объекта в переранжированный набор цифровых объектов увеличит метрику качества переранжированного набора цифровых объектов с учетом целевой характеристики цифровых объектов; выбор цифровых объектов на основе соответствующих параметров объектов; ранжирование переранжированного набора цифровых объектов на основе соответствующих значений дополнительной характеристики и, таким образом, формирование переранжированного набора цифровых объектов, содержащего выбранные цифровые объекты, ранжированные согласно дополнительной характеристике.

[14] В некоторых вариантах осуществления способа целевая характеристика указывает на релевантность цифрового объекта запросу.

[15] В некоторых вариантах осуществления способа дополнительная характеристика не указывает на релевантность цифрового объекта запросу.

[16] В некоторых вариантах осуществления способа дополнительная характеристика указывает на параметр относительной ценности цифрового объекта по сравнению с другим объектом из набора цифровых объектов.

[17] В некоторых вариантах осуществления способа дополнительная характеристика позволяет выполнять ранжирование цифровых объектов согласно дополнительной характеристике, отличное от ранжирования на основе целевой характеристики.

[18] В некоторых вариантах осуществления способа дополнительная характеристика указывает на собственный параметр цифрового объекта и другого объекта из набора цифровых объектов.

[19] В некоторых вариантах осуществления способа собственный параметр не указывает непосредственно на релевантность цифрового объекта запросу.

[20] В некоторых вариантах осуществления способ дополнительно включает в себя обучение алгоритма машинного обучения (MLA, Machine Learning Algorithm).

[21] В некоторых вариантах осуществления способа обучение алгоритма MLA включает в себя подачу в алгоритм MLA набора обучающих цифровых объектов, при этом каждый элемент в обучающем наборе цифровых объектов содержит: (а) обучающий цифровой объект из обучающего набора цифровых объектов; (б) обучающий запрос, использованный для формирования обучающего набора цифровых объектов; (в) указание на дополнительную характеристику обучающего цифрового объекта; и (г) формируемую оценщиком метку, указывающую на обязательность включения обучающего цифрового объекта в поднабор обучающих цифровых объектов с учетом дополнительной характеристики и релевантности обучающего цифрового объекта обучающему запросу.

[22] В некоторых вариантах осуществления способа алгоритм MLA представляет собой алгоритм MLA на основе дерева решений с градиентным бустингом.

[23] В некоторых вариантах осуществления способа переранжированный набор цифровых объектов содержит меньше цифровых объектов, чем набор цифровых объектов.

[24] В некоторых вариантах осуществления способа параметр объекта основан на компромиссе между количеством цифровых объектов, подлежащих включению в переранжированный набор цифровых объектов, и релевантностью цифровых объектов, включенных в переранжированный набор цифровых объектов.

[25] В некоторых вариантах осуществления способа компромисс относится к поднабору позиций с более высоким рангом из переранжированного набора цифровых объектов.

[26] В некоторых вариантах осуществления способа поднабор позиций с более высоким рангом соответствует первым N позициям переранжированного набора цифровых объектов.

[27] В некоторых вариантах осуществления способа метрика качества основана на релевантности переранжированного набора цифровых объектов запросу с учетом целевой характеристики.

[28] В некоторых вариантах осуществления способа метрика качества основана на предсказанном значении дополнительной характеристики первых N цифровых объектов из переранжированного набора цифровых объектов.

[29] Согласно второму аспекту настоящей технологии реализована система для ранжирования цифровых объектов на основе связанной с ними целевой характеристики. Система содержит аппаратный сервер, соединенный через сеть связи с электронным устройством, связанным с пользователем. Аппаратный сервер способен: получать от электронного устройства запрос на ранжирование цифровых объектов; на основе запроса выбирать из пула цифровых объектов набор цифровых объектов, который релевантен запросу с учетом целевой характеристики цифровых объектов и может быть ранжирован согласно их целевой характеристике; получать от электронного устройства запрос фильтрации для переранжированного набора цифровых объектов из набора цифровых объектов, при этом запрос фильтрации основан на дополнительной характеристике, отличной от целевой характеристики; выбирать цифровые объекты, подлежащие включению в переранжированный набор цифровых объектов, путем определения для цифрового объекта из набора цифровых объектов соответствующего параметра объекта, указывающего на вероятность того, что включение цифрового объекта в переранжированный набор цифровых объектов увеличит метрику качества переранжированного набора цифровых объектов с учетом целевой характеристики цифровых объектов; выбирать цифровые объекты на основе соответствующих параметров объектов; ранжировать переранжированный набор цифровых объектов на основе соответствующих значений дополнительной характеристики и, таким образом, формировать переранжированный набор цифровых объектов, содержащий выбранные цифровые объекты, ранжированные согласно дополнительной характеристике.

[30] В некоторых вариантах осуществления системы аппаратный сервер дополнительно способен определять параметр объекта с использованием алгоритма MLA.

[31] В некоторых вариантах осуществления системы аппаратный сервер дополнительно способен обучать алгоритм MLA путем подачи в алгоритм MLA набора обучающих цифровых объектов. Каждый элемент в обучающем наборе цифровых объектов содержит: (а) обучающий цифровой объект из обучающего набора цифровых объектов; (б) обучающий запрос, использованный для формирования обучающего набора цифровых объектов; (в) указание на дополнительную характеристику обучающего цифрового объекта; (г) формируемую оценщиком метку, указывающую на обязательность включения обучающего цифрового объекта в поднабор обучающих цифровых объектов с учетом дополнительной характеристики и релевантности обучающего цифрового объекта обучающему запросу.

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

[33] В контексте настоящего описания термин «клиентское устройство» означает любое компьютерное аппаратное средство, способное выполнять программы, подходящие для решения поставленной задачи. Таким образом, некоторые (не имеющие ограничительного характера) примеры клиентских устройств включают в себя персональные компьютеры (настольные, ноутбуки, нетбуки и т.п.), смартфоны и планшеты, а также сетевое оборудование, такое как маршрутизаторы, коммутаторы и шлюзы. Следует отметить, что в данном контексте устройство, функционирующее как клиентское устройство, также может функционировать как сервер для других клиентских устройств. Использование выражения «клиентское устройство» не исключает использования нескольких клиентских устройств для приема, отправки, выполнения или инициирования выполнения любой задачи или запроса либо результатов любых задач или запросов либо шагов любого описанного здесь способа.

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

[35] В контексте настоящего описания выражение «информация» включает в себя информацию любого рода или вида, допускающую хранение в базе данных. Таким образом, информация включает в себя аудиовизуальные произведения (изображения, фильмы, звукозаписи, презентации и т.д.), данные (данные о местоположении, числовые данные и т.д.), текст (мнения, комментарии, вопросы, сообщения и т.д.), документы, электронные таблицы, списки слов и т.д., но не ограничивается ими.

[36] В контексте настоящего описания выражение «компонент» включает в себя обозначение программного обеспечения (подходящего для определенных аппаратных средств), необходимого и достаточного для выполнения определенной функции или нескольких функций.

[37] В контексте настоящего описания выражение «пригодный для использования в компьютере носитель информации» означает носители любого рода и вида, включая оперативное запоминающее устройство (ОЗУ), постоянное запоминающее устройство (ПЗУ), диски (CD-ROM, DVD, гибкие диски, жесткие диски и т.д.), USB-накопители, твердотельные накопители, накопители на магнитных лентах и т.д.

[38] В контексте настоящей технологии «родное» приложение представляет собой программу, специально разработанную для использования в конкретном устройстве с его операционной системой.

[39] В контексте настоящего описания числительные «первый» «второй», «третий» и т.д. используются лишь для указания различия между существительными, к которым они относятся, но не для описания каких-либо определенных взаимосвязей между этими существительными. Например, должно быть понятно, что использование терминов «первый сервер» и «третий сервер» не подразумевает какого-либо определенного порядка, типа, хронологии, иерархии или классификации, в данном случае, серверов, а также что их использование (само по себе) не подразумевает наличия «второго сервера» в любой ситуации. Кроме того, как встречается в настоящем описании в другом контексте, ссылка на «первый» элемент и «второй» элемент не исключает того, что эти два элемента в действительности могут быть одним и тем же элементом. Таким образом, например, в некоторых случаях «первый» сервер и «второй» сервер могут представлять собой одно и то же программное и/или аппаратное средство, а в других случаях - различные программные и/или аппаратные средства.

[40] Каждый вариант осуществления настоящей технологии относится к по меньшей мере одной из вышеупомянутых целей и/или аспектов, но не обязательно ко всем ним. Должно быть понятно, что некоторые аспекты настоящей технологии, связанные с попыткой достижения вышеупомянутой цели, могут не соответствовать этой цели и/или могут соответствовать другим целям, явным образом здесь не упомянутым.

[41] Дополнительные и/или альтернативные признаки, аспекты и преимущества вариантов реализации настоящей технологии содержатся в дальнейшем описании, в приложенных чертежах и в формуле изобретения.

Краткое описание чертежей

[42] Дальнейшее описание приведено для лучшего понимания настоящей технологии, а также других аспектов и их признаков, и должно использоваться совместно с приложенными чертежами.

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

[44] На фиг. 2-4 приведен пример соответствующего не имеющим ограничительного характера вариантам осуществления настоящей технологии этапа обучения алгоритма MLA, используемого в представленной на фиг. 1 системе.

[45] На фиг. 5-7 приведен пример соответствующего не имеющим ограничительного характера вариантам осуществления настоящей технологии этапа использования алгоритма MLA, используемого в представленной на фиг. 1 системе.

[46] На фиг. 8 представлена блок-схема способа ранжирования цифровых объектов на основе связанной с ними целевой характеристики согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии.

[47] В конце настоящего документа приведены приложения А и Б. Приложение А содержит копию неопубликованной статьи «Обучение выбору для заранее заданного ранжирования». Приложение Б содержит копию неопубликованных дополнительных материалов к статье «Обучение выбору для заранее заданного ранжирования». Эти приложения содержат дополнительную информацию об уровне техники, описание не имеющих ограничительного характера вариантов осуществления настоящей технологии и некоторые дополнительные примеры. Эти приложения полностью включены в настоящий документ посредством ссылки во всех юрисдикциях, где допускается такое включение посредством ссылки.

Осуществление изобретения

[48] На фиг. 1 представлена схема системы 100, пригодной для реализации вариантов осуществления настоящей технологии, не имеющих ограничительного характера. Очевидно, что система 100 приведена лишь для демонстрации варианта реализации настоящей технологии. Таким образом, дальнейшее описание системы представляет собой описание примеров, иллюстрирующих настоящую технологию. Это описание не предназначено для определения объема или границ настоящей технологии. В некоторых случаях приводятся полезные примеры модификаций системы 100. Они способствуют пониманию, но также не определяют объем или границы настоящей технологии. Эти модификации не составляют исчерпывающего перечня. Как должно быть понятно специалисту в данной области, возможны и другие модификации. Кроме того, если в некоторых случаях модификации не описаны (т.е. примеры модификаций отсутствуют), это не означает, что они невозможны и/или что описание содержит единственно возможный вариант реализации того или иного элемента настоящей технологии. Специалисту в данной области должно быть понятно, что это не так. Кроме того, следует понимать, что система 100 в некоторых случаях может представлять собой упрощенную реализацию настоящей технологии и что такие варианты представлены, чтобы способствовать лучшему ее пониманию. Специалистам в данной области должно быть понятно, что различные варианты осуществления настоящей технологии могут быть значительно сложнее.

Электронное устройство

[49] Система 100 содержит электронное устройство 108, связанное с пользователем 112. Электронное устройство 108 может называться клиентским устройством, оконечным устройством, клиентским электронным устройством или просто устройством. Следует отметить, что связь электронного устройства 108 с пользователем 112 не означает необходимости предлагать или подразумевать какой-либо режим работы, например, вход в систему, регистрацию и т.п.

[50] На реализацию электронного устройства 108 не накладывается каких-либо особых ограничений. Например, электронное устройство 108 может быть реализовано в виде персонального компьютера (настольного, ноутбука, нетбука и т.д.), беспроводного устройства связи (смартфона, сотового телефона, планшета и т.д.) или сетевого оборудования (маршрутизатора, коммутатора, шлюза и т.д.). Электронное устройство 108 содержит известные в данной области техники аппаратные средства и/или прикладное программное обеспечение и/или встроенное программное обеспечение (либо их сочетание) для выполнения браузерного приложения. В общем случае браузерное приложение обеспечивает пользователю 112 доступ к одному или нескольким веб-ресурсам. На реализацию браузерного приложения не накладывается каких-либо особых ограничений. Например, браузерное приложение может быть реализовано в виде браузера Yandex™.

[51] В некоторых вариантах осуществления настоящей технологии браузерное приложение, реализованное с использованием электронного устройства 108, позволяет пользователю 112 отправлять пользовательские запросы сервису 110 цифровых объектов (например, размещенному на сервере 106). Сервис 110 цифровых объектов при обращении к нему электронного устройства 108 использует интерфейс 124 поиска, который может быть реализован в виде омнибокса, позволяющего пользователю 112 вводить или отправлять пользовательские запросы, и область 126 отображения результатов для отображения наборов цифровых объектов, соответствующих отправленному пользовательскому запросу пользователя 112. В общем случае сервис 110 цифровых объектов представляет собой систему, способную получать запросы от множества пользователей, выбирать из пула 122 цифровых объектов цифровые объекты, соответствующие принятым пользовательским запросам, для формирования соответствующих наборов цифровых объектов и предоставлять соответствующие наборы цифровых объектов электронному устройству 108 пользователя 112. В качестве некоторых примеров сервиса 110 цифровых объектов можно привести платформы для электронной торговли (такие как платформа для электронной торговли Amazon™, платформа для электронной торговли eBay™, платформа для электронной торговли Yandex™ Market и т.п.) и веб-сайты социальных сетей (такие как веб-сайт социальной сети Facebook™, веб-сайт социальной сети VK™ и т.п.).

[52] Например, пользователь 112 может использовать браузерное приложение (не показано) для доступа к сервису 110 цифровых объектов с использованием электронного устройства 108 для отправки пользовательского запроса. После ввода запроса электронное устройство 108 формирует пакет 114 данных, содержащий данные, указывающие на пользовательский запрос пользователя 112. Предполагается, что множество пакетов данных может быть сформировано множеством устройств системы 100 подобно тому, как электронное устройство 108 формирует пакет 114 данных, на основе соответствующего пользовательского запроса, введенного или отправленного соответствующим пользователем (не показан) в соответствующее браузерное приложение.

[53] В не имеющих ограничительного характера вариантах осуществления настоящей технологии вместо использования браузерного приложения для доступа к сервису 110 цифровых объектов пользователь 112 может обращаться к сервису 110 цифровых объектов с использованием связанного с ним «родного» приложения и электронного устройства 108.

Сеть связи

[54] Электронное устройство 108 соединено с сетью 104 связи для обеспечения доступа к сервису 110 цифровых объектов сервера 106. В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии в качестве сети 104 связи может использоваться сеть Интернет. В других не имеющих ограничительного характера вариантах осуществления данной технологии сеть 104 связи может быть реализована иначе, например, в виде любой глобальной сети связи, локальной сети связи, частной сети связи и т.п. Реализация линии связи (отдельно не обозначена) между электронным устройством 108 и сетью 104 связи зависит, среди прочего, от реализации электронного устройства 108.

[55] Лишь в качестве примера, не имеющего ограничительного характера, в тех вариантах осуществления настоящей технологии, где электронное устройство 108 реализовано в виде беспроводного устройства связи (такого как смартфон), линия связи может быть реализована в виде беспроводной линия связи (такой как канал сети связи 3G, канал сети связи 4G, Wireless Fidelity или сокращенно WiFi®, Bluetooth® и т.п.). В тех примерах, где электронное устройство 108 реализовано в виде ноутбука, линия связи может быть беспроводной (такой как Wireless Fidelity или сокращенно WiFi®, Bluetooth® и т.д.) или проводной (такой как соединение на основе Ethernet).

[56] Сеть 104 связи способна передавать, среди прочего, пакет 114 данных от электронного устройства 108 к серверу 106 и пакет 116 данных, указывающий на набор цифровых объектов, от сервера 106 к электронному устройству 108. Например, набор цифровых объектов может содержать цифровые объекты, выбранные сервером 106 из пула 122 цифровых объектов (например, хранящегося в базе 102 данных), и соответствовать пользовательскому запросу пользователя 112. Ниже более подробно описано, как сервер 106 формирует пакет 116 данных, указывающий на набор цифровых объектов, и представляет его в области 126 отображения результатов для показа пользователю 112 на электронном устройстве 108.

Сервер

[57] Система 100 также содержит сервер 106, который может быть реализован в виде традиционного компьютерного сервера. В примере осуществления настоящей технологии сервер 106 может быть реализован в виде сервера Dell™ PowerEdge™, работающего под управлением операционной системы Microsoft™ Windows Server™. Очевидно, что сервер 106 может быть реализован с использованием любых других подходящих аппаратных средств, прикладного программного обеспечения и/или встроенного программного обеспечения либо их сочетания. В представленных не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 106 представляет собой один сервер. В других не имеющих ограничительного характера вариантах осуществления настоящей технологии функции сервера 106 могут быть распределены между несколькими серверами.

[58] В общем случае сервер 106 может управляться и/или администрироваться сервисом 110 цифровых объектов (например, Yandex™ Market), как описано выше. Сервер 106 способен выполнять один или несколько поисков цифровых объектов в ответ на пользовательские запросы, отправленные пользователями сервиса 110 цифровых объектов.

[59] Сервер 106 способен выполнять по меньшей мере некоторые процедуры из множества компьютерных процедур, описанных ниже со ссылками на фиг. 2 и 3. Должно быть понятно, что сервер 106 также может выполнять дополнительные компьютерные процедуры, помимо не составляющих исчерпывающий перечень процедур, представленных на фиг. 2 и 3.

База данных

[60] В не имеющих ограничительного характера вариантах осуществления настоящей технологии система 100 также может содержать базу 102 данных, связанную с сервером 106 через сеть 104 связи и способную хранить пул 122 цифровых объектов и информацию, извлеченную или иным образом определенную либо сформированную сервером 106.

[61] Несмотря на то, что в представленных на фиг. 1 вариантах осуществления изобретения база 102 данных показана в виде отдельного сервера, соединенного с сервером 106 через сеть 104 связи, следует отметить, что в не имеющих ограничительного характера вариантах осуществления настоящей технологии база 102 данных также может представлять собой часть сервера 106 (например, храниться в памяти сервера 106, такой как твердотельный накопитель и/или ОЗУ (отдельно не показаны)).

[62] В общем случае база 102 данных может хранить пул 122 цифровых объектов. Пул 122 цифровых объектов содержит указание на цифровые объекты, связанные с сервисом 110 цифровых объектов. В не имеющих ограничительного характера вариантах осуществления настоящей технологии цифровые объекты представляют собой цифровые документы различных видов, включая текстовые документы, аудио- и видеодокументы, цифровые документы любых других видов, созданные с использованием различного программного обеспечения, или их сочетание, но не ограничиваясь ими. Кроме того, эти документы могут быть представлены в любом известном соответствующем формате. В общем случае в контексте настоящего документа цифровые объекты представляют собой элементы электронного медиаконтента, подходящие для отправки, получения, хранения и отображения.

[63] Например, в некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии, где сервис 110 цифровых объектов представляет собой веб-платформу для электронной торговли, цифровые объекты могут представлять собой предложения различных товаров. Например, цифровой объект может представлять собой веб-страницу, содержащую множество цифровых элементов, каждый из которых представляет собой отдельный цифровой объект в конкретном формате, при этом отдельный цифровой объект соответствует товару для продажи.

[64] В других не имеющих ограничительного характера вариантах осуществления настоящей технологии, где сервис 110 цифровых объектов представляет собой веб-сайт социальной сети, цифровые объекты могут, например, являться сообщениями, сформированными пользователями веб-сайта социальной сети, новостными сообщениями, публикациями, содержащими текстовую информацию и/или аудиоинформацию и/или видеоинформацию и т.д.

[65] В не имеющих ограничительного характера вариантах осуществления настоящей технологии база 102 данных может получать данные от сервера 106. Данные могут быть извлечены или в иным образом определены либо сформированы сервером 106 во время обработки для временного и/или постоянного хранения. Предполагается, что база 102 данных может быть разделена на несколько распределенных баз данных без выхода за границы настоящей технологии.

[66] В не имеющих ограничительного характера вариантах осуществления настоящей технологии база 102 данных, наряду с цифровыми объектами из пула 122 цифровых объектов, способна хранить вспомогательные данные, связанные с каждым объектом из пула 122 цифровых объектов. Эти данные могут быть извлечены (или сформированы) и отправлены в базу 102 данных сервером 106.

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

[68] В общем случае данные о прошлых пользовательских действиях представляют собой любые данные предыстории, указывающие на пользовательские действия с цифровым объектом множества пользователей, отправивших такие же или подобные пользовательские запросы. Следует отметить, что указание на прошлые пользовательские запросы также может храниться в базе 102 данных в сочетании с цифровым объектом. Согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии, данные о прошлых пользовательских действиях могут быть использованы для определения параметра релевантности цифрового объекта одному из пользовательских запросов.

[69] В качестве не имеющих ограничительного характера примеров данных о прошлых пользовательских действиях, которые могут быть сформированы и поддерживаться сервером 106, можно привести данные о коэффициенте «кликов» (CTR, Click-Through Rate), связанные с цифровым объектом и собранные от множества пользователей, «взаимодействовавших» с цифровым объектом после отправки таких же или подобных пользовательских запросов. Кроме того, данные о прошлых пользовательских действиях могут содержать среднеобратный ранг (MRR, Mean Reciprocal Rank) «клика» или инвертированное значение позиции первого «клика» для цифрового объекта. Наконец, данные о прошлых пользовательских действиях могут содержать коэффициент отказов, представляющий собой долю связанных с цифровыми объектами пользовательских запросов без кликов от множества пользователей.

[70] В не имеющих ограничительного характера вариантах осуществления настоящей технологии цифровой объект из пула 122 цифровых объектов имеет по меньшей мере одну дополнительную характеристику.

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

[72] В не имеющих ограничительного характера вариантах осуществления настоящей технологии собственный параметр указывает на соотношение цифрового объекта и другого цифрового объекта в по меньшей мере части пула 122 цифровых объектов. Иными словами, собственный параметр представляет собой общую характеристику по меньшей мере части цифровых объектов из пула 122 цифровых объектов. В примере, где сервис 110 цифровых объектов представляет собой веб-платформу для электронной торговли, а цифровой объект представляет собой предложение товара, собственному параметру может соответствовать наименование товара, цена предложения, цена, агрегированная по различным категориям, к которым относится товар, предлагаемая дата отправки, способ оплаты и т.п.

[73] В другом примере, где сервис 110 цифровых объектов представляет собой веб-сайт социальной сети, а цифровой объект, например, представляет собой сообщение в социальной сети, собственному параметру может соответствовать время создания сообщения или создавшее его лицо.

[74] Соответственно, по меньше мере одна дополнительная характеристика, связанная с цифровым объектом из пула 122 цифровых объектов, может не указывать на релевантность цифрового объекта связанным с ним пользовательским запросам.

[75] В качестве альтернативы, по меньше мере одна дополнительная характеристика, связанная с каждым цифровым объектом из по меньшей мере части пула 122 цифровых объектов, может указывать на параметр относительной ценности цифрового объекта по сравнению с каждым другим цифровым объектом из по меньшей мере части пула 122 цифровых объектов на основе соответствующего собственного параметра. Иными словами, цифровые объекты из пула 122 цифровых объектов также могут быть ранжированы на основе их взаимной относительной ценности, представленной связанной с ними дополнительной характеристикой (такой как цена, алфавитный порядок названий, даты отправки, популярность, пользовательские рейтинги и т.п.).

[76] Соответственно, в не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 106 может получать пакет 114 данных, содержащий данные, указывающие на пользовательский запрос (получение происходит после отправки пользователем 112 с использованием электронного устройства 108 пользовательского запроса интерфейсу 124 поиска сервиса 110 цифровых объектов). Сервер 106 способен выбирать из пула 122 цифровых объектов, размещенного в базе 102 данных, цифровые объекты, релевантные пользовательскому запросу, и таким образом формировать пакет 116 данных, указывающий на цифровые объекты, релевантные введенному пользовательскому запросу.

[77] Для этого сервер 106 способен формировать для каждого цифрового объекта из пула 122 цифровых объектов параметр ранжирования на основе целевой характеристики. Согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии, параметр ранжирования может указывать на релевантность цифрового объекта пользовательскому запросу. Параметр ранжирования может быть предсказан на основе данных о прошлых пользовательских действиях, связанных с цифровыми объектами из пула 122 цифровых объектов. Таким образом, можно сказать, что целевая характеристика цифрового объекта указывает на релевантность цифрового объекта введенному пользовательскому запросу.

[78] На способ формирования сервером 106 параметра ранжирования на основе целевой характеристики не накладывается каких-либо ограничений. Этот способ может включать в себя формирование параметра ранжирования с использованием одного или нескольких алгоритмов MLA, обученных предсказанию параметров ранжирования цифровых объектов, указывающих на их релевантность пользовательским запросам, на основе, среди прочего, данных о прошлых пользовательских действиях, связанных с цифровыми объектами. Обучение и последующее использование одного или нескольких алгоритмов MLA с целью предсказания параметров ранжирования цифровых объектов для пользовательского запроса описано в патентной заявке US20170185681 «Method of and system for processing a prefix associated with a search query» (опубликован 1 декабря 2016 г.), содержание которой полностью включено в настоящий документ посредством ссылки и поэтому более подробно не обсуждается.

[79] Сервер 106 способен выбирать набор цифровых объектов на основе их соответствующих целевых характеристик. Например, сервер 106 может выбирать первые 500 объектов на основе их релевантности пользовательскому запросу.

[80] Выбрав цифровые объекты из пула 122 цифровых объектов, сервер 106 может сформировать пакет 116 данных и может отправить пакет 116 данных, указывающий на цифровые объекты из набора цифровых объектов, электронному устройству 108 через сеть 104 связи для представления пользователю 112 по меньшей мере части набора цифровых объектов в области 126 отображения результатов сервиса 110 цифровых объектов.

[81] Следует отметить, что целевые характеристики цифровых объектов для набора цифровых объектов из пула 122 цифровых объектов могут быть пригодными для такого ранжирования цифровых объектов, чтобы цифровые объекты с значениями их целевых характеристик размещались в начале набора цифровых объектов. В связи с этим в не имеющих ограничительного характера вариантах осуществления настоящей технологии перед отправкой пакета 116 данных, указывающего на выбранный набор цифровых объектов, сервер 106 может ранжировать цифровые объекты в наборе согласно предсказанным параметрам ранжирования, сформированным на основе соответствующих целевых характеристик.

[82] После представления по меньшей мере части набора цифровых объектов в области 126 отображения результатов пользователю 112 может потребоваться переупорядочение набора цифровых объектов на основе одной из связанных с ними дополнительных характеристик.

[83] В примере, где сервис 110 цифровых объектов представляет собой платформу для электронной торговли, пользователю 112 может потребоваться переупорядочение предложений по возрастанию их цены (наименьшая цена в первой позиции).

[84] С этой целью пользователь 112 может использовать соответствующий один или несколько управляющих элементов (не показаны) сервиса 110 цифровых объектов для выбора одной из дополнительных характеристик и таким образом формировать указание 118 на запрос фильтрации для переранжированного набора цифровых объектов для последующей его отправки серверу 106 через сеть 104 связи.

[85] Получив указание 118 на запрос фильтрации, сервер 106 выбирает поднабор цифровых объектов из набора цифровых объектов для включения в переранжированный набор цифровых объектов, как показано на фиг. 5–7. Как показано на фиг. 7, в ответ на указание 118 на запрос фильтрации сервер 106 выбирает цифровые объекты для включения в переранжированный набор 712 цифровых объектов из набора 512 цифровых объектов (см. фиг. 5), упорядоченного на основе целевых характеристик содержащихся в нем цифровых объектов.

[86] С этой целью сервер 106 может определять для цифрового объекта из набора цифровых объектов параметр объекта, значение которого указывает на вероятность того, что включение цифрового объекта в переранжированный набор цифровых объектов увеличит метрику качества ранжирования переранжированного набора цифровых объектов с учетом целевой характеристики цифровых объектов.

[87] Метрика качества может включать в себя любую подходящую метрику качества, среди прочего, такую как:

- функция метрики качества на основе дисконтированного кумулятивного показателя (DCG, Discounted Cumulative Gain);

- функция метрики качества на основе нормализованного дисконтированного кумулятивного показателя (NDCG, Normalized Discounted Cumulative Gain);

- функция метрики качества на основе ожидаемого взаимного ранга (ERR, Expected Reciprocal Rank);

- функция метрики качества на основе средней точности (MAP, Mean Average Precision);

- функция метрики качества на основе среднего взаимного ранга (MRR, Mean Reciprocal Rank).

[88] Определив для каждого цифрового объекта из набора цифровых объектов параметры объектов, сервер 106 может перейти к выбору на их основе цифровых объектов для включения в переранжированный набор цифровых объектов. Способ выбора сервером 106 цифровых объектов на основе их параметров, на который не накладывается каких-либо ограничений, может, например, включать в себя выбор на основе заранее заданного порога.

[89] Выбрав цифровые объекты для включения в переранжированный набор цифровых объектов, сервер 106 может упорядочивать их согласно соответствующей дополнительной характеристике так, чтобы цифровые объекты из набора цифровых объектов с меньшими значениями дополнительной характеристики, выбранной пользователем 112, размещались в начале переранжированного набора цифровых объектов. Затем сервер 106 может формировать пакет 120 данных, указывающий на переранжированный набор цифровых объектов, в котором цифровые объекты упорядочены согласно их дополнительной характеристике. Наконец, сервер 106 может отправлять через сеть 104 связи пакет 120 данных электронному устройству 108 для представления по меньшей мере части переранжированного набора цифровых объектов пользователю 112 в области 126 отображения результатов сервиса 110 цифровых объектов.

[90] В не имеющих ограничительного характера вариантах осуществления настоящей технологии, выбрав цифровые объекты для включения в переранжированный набор цифровых объектов, сервер 106 способен выбирать их поднабор для ранжирования согласно дополнительной характеристике, выбранной пользователем 112. В этих вариантах осуществления изобретения количество цифровых объектов в поднаборе цифровых объектов может быть определено на основе количества цифровых объектов, которые могут быть представлены в области 126 отображения результатов сервиса 110 цифровых объектов.

[91] В не имеющих ограничительного характера вариантах осуществления настоящей технологии параметры объектов определяются алгоритмом MLA. В не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 106 может выполнять алгоритм MLA на основе нейронных сетей, модели дерева решений, алгоритм MLA на основе дерева решений с градиентным бустингом, алгоритм MLA на основе обучения правилам ассоциации, алгоритм MLA на основе глубинного обучения, алгоритм MLA на основе индуктивного логического программирования, алгоритм MLA на основе метода опорных векторов, алгоритм MLA на основе кластеризации, байесовские сети, алгоритм MLA на основе обучения с подкреплением, алгоритм MLA на основе обучения представлению, алгоритм MLA на основе обучения сходству и метрикам, алгоритм MLA на основе обучения на скудном словаре, алгоритм MLA на основе генетических алгоритмов и т.п. Сервер 106 может использовать алгоритм MLA на основе обучения с учителем без выхода за границы настоящей технологии.

[92] В общем случае можно сказать, что сервер 106 используется на двух этапах. Первый из двух этапов представляет собой этап обучения, на котором сервер 106 обучается на обучающем наборе данных для получения формулы алгоритма MLA.

[93] Второй из двух этапов представляет собой этап использования, на котором сервер 106 используется для определения параметров объектов для цифровых объектов из набора цифровых объектов.

[94] В дополнительных вариантах осуществления настоящей технологии сервер 106 после этапа использования может быть повторно обучен для получения новой формулы алгоритма MLA или для уточнения формулы алгоритма MLA. Как описано ниже, алгоритм MLA повторно обучается на улучшенных обучающих данных, полученных в результате реализации некоторых вариантов осуществления настоящей технологии.

[95] Ниже со ссылками на фиг. 2 и 7 описаны этапы обучения и использования алгоритма MLA.

Этап обучения

[96] На фиг. 2-4 схематически показан процесс формирования обучающего набора данных для обучения алгоритма MLA, используемого в системе 100 для ранжирования цифровых объектов на основе связанных с ними целевых характеристик, согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии.

[97] Как описано выше, процесс формирования обучающего набора данных может, например, выполняться сервером 106.

[98] На фиг. 2 схематически показан графический интерфейс 200 сервиса 110 цифровых объектов, используемый на этапе обучения. Как описано выше, пользователь (например, пользователь 112) формирует обучающий пользовательский запрос 202 в интерфейсе 124 поиска. В ответ на обучающий пользовательский запрос 202 сервер 106 способен выдавать набор 210 обучающих цифровых объектов (например, по меньшей мере часть цифровых объектов из пула 122 цифровых объектов), каждый из которых релевантен обучающему пользовательскому запросу 202, на основе связанных с ними соответствующих значений параметра 206 ранжирования. Соответствующие значения параметра 206 ранжирования формируются сервером 106 на основе соответствующих значений целевой характеристики, указывающей на релевантность обучающих цифровых объектов из набора 210 обучающих цифровых объектов обучающему пользовательскому запросу.

[99] Согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии, обучающие цифровые объекты из набора 210 обучающих цифровых объектов могут иметь индексы 204. В представленных на фиг. 2 вариантах осуществления изобретения набор 210 обучающих цифровых объектов содержит M обучающих цифровых объектов, при этом первый обучающий цифровой объект 212 имеет индекс 1, а последний обучающий цифровой объект 226 в наборе 210 обучающих цифровых объектов имеет индекс M. Первые N цифровых объектов из набора 210 цифровых объектов представляются пользователю 112 в области 126 отображения результатов сервиса 110 цифровых объектов. Таким образом, последний обучающий цифровой объект 216 в области 126 отображения результатов имеет индекс N. В не имеющих ограничительного характера вариантах осуществления настоящей технологии количество N может быть определено, среди прочего, на основе размера области 126 отображения результатов, который может зависеть от электронного устройства 108. Числа M и N, а также промежуточные числа принадлежат множеству целых положительных чисел, при этом M больше R, а R больше N.

[100] В представленных на фиг. 2 вариантах осуществления изобретения сервер 106 до представления обучающих цифровых объектов пользователю 112 способен упорядочивать обучающие цифровые объекты в наборе 210 обучающих цифровых объектов согласно соответствующим значениям связанного с ними параметра 206 ранжирования. Следовательно, обучающие цифровые объекты, вероятно, более релевантные обучающему пользовательскому запросу 202, размещаются в начале набора 210 обучающих цифровых объектов. Таким образом, обучающий цифровой объект 212, вероятно, наиболее релевантен обучающему пользовательскому запросу 202 в наборе 210 обучающих цифровых объектов, поскольку он имеет значение 1 параметра 206 ранжирования. Обучающий цифровой объект 226, вероятно, наименее релевантен обучающему пользовательскому запросу 202 в наборе 210 обучающих цифровых объектов, поскольку он имеет значение M параметра 206 ранжирования. Цифровые объекты 214–224 имеют промежуточные значения параметра 206 ранжирования от 2 до R, соответственно.

[101] Каждый объект из набора 210 обучающих цифровых объектов имеет по меньшей мере одну связанную с ним обучающую дополнительную характеристику, например, дополнительную характеристику 208. Дополнительная характеристика 208 указывает на соотношение одного обучающего цифрового объекта и другого обучающего цифрового объекта. Соответственно, обучающий цифровой объект 212 имеет значение S1 дополнительной характеристики 208. Другие обучающие цифровые объекты 214-226, соответственно, имеют значения от S2 до SM дополнительной характеристики 208.

[102] Кроме того, до представления пользователю 112 сервер 106 может удалять из набора 210 обучающих цифровых объектов некоторые обучающие цифровые объекты, у которых оценочное значение параметра 206 ранжирования превышает заранее заданное пороговое значение. Затем сервер 106 способен отфильтровывать менее релевантные обучающие цифровые объекты. В представленных на фиг. 2 вариантах осуществления изобретения заранее заданное пороговое значение равно R. Таким образом, обучающие цифровые объекты, у которых значение параметра 206 ранжирования равно R+1 и больше, удаляются из набора 210 обучающих цифровых объектов и пользователю 112 представляется поднабор 211 обучающих цифровых объектов, содержащее первые R обучающих цифровых объектов. Поднабор 211 обучающих цифровых объектов упорядочен согласно их целевой характеристике.

[103] Пользователь 112 может сформировать и отправить серверу 106 обучающий запрос 306 фильтрации (см. фиг. 3). Обучающий запрос 306 фильтрации используется, чтобы упорядочить по возрастанию поднабор 211 обучающих цифровых объектов согласно соответствующим значениям от S1 до SR связанной с ними дополнительной характеристики 208 (обучающий цифровой объект с наименьшим значением дополнительной характеристики размещен в первой позиции). В ответ на получение обучающего запроса 306 фильтрации сервер 106 способен упорядочивать обучающие цифровые объекты в поднаборе 211 обучающих цифровых объектов согласно дополнительной характеристике 208. Таким образом, сервер 106 способен формировать переранжированный поднабор 310 обучающих цифровых объектов.

[104] Обучающие цифровые объекты в переранжированном поднаборе 310 обучающих цифровых объектов уже не упорядочены согласно значениям связанного с ними параметра 206 ранжирования. Например, обучающему цифровому объекту 312, имеющему значение M–10 параметра 206 ранжирования, соответствует первая позиция, поскольку он имеет наименьшее значение дополнительной характеристики 208 в переранжированном поднаборе 310 цифровых объектов. Обучающему цифровому объекту 214, имеющему значение 2 параметра 206 ранжирования, теперь соответствует последняя позиция, поскольку он имеет наибольшее значение дополнительной характеристики 208.

[105] Затем в не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 106 может сохранять (например, в базе 102 данных) переранжированный поднабор 310 обучающих цифровых объектов в сочетании с обучающим пользовательским запросом 202.

[106] Сервер 106 может получать из базы 102 данных переранжированный поднабор 310 обучающих цифровых объектов для предоставления переранжированного поднабора 310 обучающих цифровых объектов оценщику-человеку 304 (см. фиг. 3). Затем оценщик-человек 304 назначает формируемые оценщиком метки для каждого объекта из переранжированного поднабора 310 обучающих цифровых объектов.

[107] В общем случае формируемые оценщиком метки 300 и 302 указывают на то, релевантен объект из переранжированного поднабора 310 обучающих цифровых объектов цели поиска из обучающего пользовательского запроса 202 (метка 300) или нет (метка 302). В зависимости от конкретных вариантов реализации, оценщику-человеку 304 предоставляется одна из инструкций по разметке (т.е. одно из разнообразных множеств формируемых оценщиком меток), например:

- двоичный выбор «да» или «нет»;

- диапазон от 1 до 5;

- диапазон от 1 до 10;

- диапазон «хороший» или «плохой»;

- диапазон «низкая релевантность», «средняя релевантность» или «высокая релевантность»;

- диапазон «идеальный - отличный - хороший - удовлетворительный - плохой» и т.д.

[108] Например, в представленных на фиг. 3 вариантах осуществления изобретения обучающие цифровые объекты 220, 314, 318 и 214 определены как релевантные обучающему пользовательскому запросу 202, поскольку помечены оценщиком-человеком 304 формируемой оценщиком меткой 300. Обучающие цифровые объекты 312, 316 и 320 определены как нерелевантные обучающему пользовательскому запросу 202, поскольку помечены оценщиком-человеком 304 формируемой оценщиком меткой 302. Сервер 106 также может сохранять в базе 102 данных переранжированный поднабор 310 обучающих цифровых объектов, содержащий размеченные оценщиком-человеком 304 обучающие цифровые объекты.

[109] В не имеющих ограничительного характера вариантах осуществления настоящей технологии вместо назначения меток оценщиком-человеком 304, алгоритм MLA может быть обучен сервером 106 предсказанию одной из формируемых оценщиком меток 300 или 302 для обучающих цифровых объектов из переранжированного поднабора 310 обучающих цифровых объектов.

[110] Сервер 106 дополнительно способен удалять обучающие цифровые объекты, помеченные как нерелевантные, из переранжированного поднабора 310 обучающих цифровых объектов (см. фиг. 4). Для этого сервер 106 способен формировать уточненный поднабор 410 обучающих цифровых объектов. Уточненный поднабор 410 обучающих цифровых объектов содержит только обучающие цифровые объекты, помеченные оценщиком-человеком 304 меткой 300. Таким образом, уточненный поднабор 410 цифровых объектов содержит обучающие цифровые объекты, которые (1) упорядочены согласно соответствующим значениям дополнительной характеристики 208 и (2) определены как релевантные обучающему пользовательскому запросу 202.

[111] Поскольку обучающие цифровые объекты, помеченные меткой 302, удалены сервером 106, уточненный поднабор 410 обучающих цифровых объектов содержит Q обучающих цифровых объектов, при этом Q меньше R.

[112] В не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 106 дополнительно способен на основе уточненного поднабора 410 обучающих цифровых объектов формировать и сохранять дополнительные признаки. Дополнительные признаки включают в себя: (1) наибольшее значение дополнительной характеристики 208 среди первых N обучающих цифровых объектов; (2) наибольшее значение параметра 206 ранжирования среди первых N обучающих цифровых объектов; (3) среднее значение дополнительной характеристики 208 для первых N обучающих цифровых объектов; (4) среднее значение параметра 206 ранжирования для первых N обучающих цифровых объектов.

[113] Например, сервер 106 способен определять, что значение 408 дополнительной характеристики 208 обучающего цифрового объекта 318 является наибольшим среди первых N обучающих цифровых объектов 220, 314, 318...402. Аналогичным образом, сервер 106 способен определять, что значение 412 параметра 206 ранжирования является наибольшим среди первых N обучающих цифровых объектов 220, 314, 318...402. Наконец, сервер 106 способен для первых N обучающих цифровых объектов из уточненного поднабора 410 обучающих цифровых объектов определять среднее значение 414 параметра 206 ранжирования и среднее значение 416 дополнительной характеристики 208.

[114] В не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 106 может предсказывать дополнительные признаки 408, 412, 414 и 416 с использованием другого алгоритма MLA. С этой целью сервер 106 может использовать по меньшей мере часть данных, описанных выше со ссылками на фиг. 1-4, для обучения алгоритма MLA предсказанию дополнительных признаков.

[115] Затем сервер 106 может сохранять дополнительные признаки 408, 412, 414 и 416 в сочетании с уточненным поднабором 410 обучающих цифровых объектов в базе 102 данных.

[116] Таким образом, на этапе обучения алгоритма MLA сервер 106 способен предоставлять алгоритму MLA такой обучающий набор данных, содержащий множество обучающих объектов, чтобы каждый обучающий цифровой объект, связанный с объектом из переранжированного поднабора 310 обучающих цифровых объектов, был снабжен: (1) обучающим пользовательским запросом 202; (2) соответствующим значением параметра 206 ранжирования; (3) соответствующим значением дополнительной характеристики 208; и (4) соответствующей меткой. В вариантах осуществления настоящей технологии метка может представлять собой описанные выше формируемые оценщиком метки 300 и 302.

[117] В не имеющих ограничительного характера вариантах осуществления настоящей технологии обучающий набор данных также может содержать (5) дополнительные признаки 408, 412, 414 и 416, связанные с первыми N обучающими цифровыми объектами из уточненного поднабора 410 обучающих цифровых объектов.

[118] Должно быть однозначно понятно, что согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии обучающий набор данных может не ограничиваться данными, сформированными сервером 106 в ответ лишь на обучающий пользовательский запрос 202. Согласно примерам, представленным в связи фиг. 2-4, сервер 106 может формировать обучающий набор данных в ответ на сотни, тысячи или даже сотни тысяч обучающих пользовательских запросов, подобных обучающему пользовательскому запросу 202.

[119] Таким образом, имея сформированный обучающий набор данных, сервер 106 способен обучать алгоритм MLA для получения формулы алгоритма MLA. Формула алгоритма MLA применяется на этапе использования с целью формирования значений параметра объекта для цифровых объектов.

[120] Соответственно, значение параметра объекта, которое алгоритм MLA обучен формировать на основе обучающего набора данных для цифрового объекта из набора 512 цифровых объектов, указывает на вероятность того, что включение цифрового объекта в переранжированный набор 712 цифровых объектов повышает полезность переранжированного набора 712 цифровых объектов для пользователя 112. Согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии, полезность переранжированного набора 712 цифровых объектов для пользователя 112 может быть определена на основе одной из описанных выше метрик качества.

[121] Ниже со ссылками на фиг. 5-7 описана реализация выбора цифровых объектов для включения в переранжированный набор 712 цифровых объектов.

Этап использования

[122] На фиг. 5 схематически представлен графический интерфейс 200 сервиса 110 цифровых объектов, используемый на этапе использования, согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии. В ответ на отправленный пользователем 112 пользовательский запрос 502 сервер 106 способен предоставлять набор 512 цифровых объектов, которые могут быть упорядочены согласно соответствующим значениям параметра 206 ранжирования. Значения с 1 по M параметра 206 ранжирования формируются сервером 106 на основе соответствующих значений целевой характеристики, указывающей на релевантность цифровых объектов пользовательскому запросу 502.

[123] Подобно примерам, представленным выше для этапа обучения, каждый цифровой объект, имеющий соответствующие индексы 204 с 1 по M в наборе 512 цифровых объектов, имеет соответствующее значение с S1 по SM дополнительной характеристики 208.

[124] Согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии, каждый цифровой объект из набора 512 цифровых объектов имеет соответствующее значение параметра 510 объекта от p1 до pM, сформированное сервером 106. Сервер 106 способен формировать значения параметра 510 объекта с использованием алгоритма MLA, обученного согласно методике, представленной выше со ссылками на фиг. 2-4. Значение параметра 510 объекта, связанное с цифровым объектом, указывает на вероятность того, что включение цифрового объекта в переранжированный набор 712 цифровых объектов (см. фиг. 7) увеличит метрику качества переранжированного набора 712 цифровых объектов.

[125] Согласно некоторым не имеющим ограничительного характера вариантам осуществления настоящей технологии, метрика качества может основываться на релевантности переранжированного набора 712 цифровых объектов пользовательскому запросу 502. При этом релевантность основывается на соответствующих значениях параметра 206 ранжирования, связанных с цифровыми объектами из переранжированного набора 712 цифровых объектов.

[126] Согласно другим не имеющим ограничительного характера вариантам осуществления настоящей технологии, метрика качества может основываться на соответствующих предсказанных значениях дополнительной характеристики 208, связанных с первыми N цифровыми объектами из переранжированного набора 712 цифровых объектов.

[127] В ответ на получение от электронного устройства 108 указания 118 на запрос фильтрации сервер 106 способен формировать переранжированный набор 712 цифровых объектов. Для этого сервер может выбирать цифровые объекты из набора 512 цифровых объектов на основе связанных с ними значений параметра 510 объекта.

[128] Не имеющие ограничительного характера варианты осуществления настоящей технологии основываются на компромиссе между количеством цифровых объектов, подлежащих включению в состав переранжированного поднабора цифровых объектов, и связанными с ними соответствующими значениями параметра 206 ранжирования. Иными словами, это компромисс между релевантностью цифровых объектов с более высокими позициями в переранжированном списке цифровых объектов и релевантностью цифровых объектов, перемещенных с более высоких позиций. Если целевая релевантность перемещенных объектов сравнительно выше, пользователь не будет удовлетворен. Таким образом, обученный алгоритм MLA в известном смысле обеспечивает оптимальное соотношение между релевантностью цифровых объектов, размещенных в более высоких позициях ранжированного списка, и релевантностью перемещенных цифровых объектов.

[129] В не имеющих ограничительного характера вариантах осуществления настоящей технологии количество цифровых объектов, подлежащих включению в переранжированный набор 712 цифровых объектов, может указывать на заранее заданное количество более высоких позиций цифровых объектов в переранжированном наборе 712 цифровых объектов. Например, заранее заданное количество более высоких позиций может быть определено как соответствующее N первым позициям в области 126 отображения результатов.

[130] Например, сервер 106 способен формировать значения параметра 510 объекта согласно следующему правилу: чем большее количество цифровых объектов подлежит включению в переранжированный набор 712 цифровых объектов, тем меньшее количество менее релевантных пользовательскому запросу 502 цифровых объектов будет включено в него, и наоборот. Таким образом, сервер 106 на основе соответствующих значений целевой характеристики способен варьировать цифровые объекты в переранжированном наборе 712 цифровых объектов в пределах заранее заданного количества позиций.

[131] В не имеющих ограничительного характера вариантах осуществления настоящей технологии цифровые объекты для переранжированного набора 712 цифровых объектов могут выбираться сервером 106 на основе заранее заданного порогового значения параметра 510 объекта. Таким образом, сервер 106 способен сначала формировать поднабор 612 цифровых объектов (см. фиг. 6). При этом сервер 106 может получать или иным образом определять либо формировать заранее заданное пороговое значение параметра 510 объекта до формирования поднабора 612 цифровых объектов.

[132] Сервер 106 может определять, что соответствующие значения параметра 510 объекта, связанные с цифровыми объектами 520, 522 и 532, меньше заранее заданного порогового значения параметра 510 объекта (см. фиг. 5 и 6). Соответственно, сервер 106 также может удалять цифровые объекты 520, 522 и 532 из набора 512 цифровых объектов.

[133] Таким образом, сервер 106 способен формировать поднабор 612 цифровых объектов. Поднабор 612 цифровых объектов содержит L цифровых объектов (при этом L меньше M), выбранных сервером 106 на основе их соответствующих значений параметра 510 объекта.

[134] Сервер 106 также может выбирать цифровые объекты из поднабора 612 цифровых объектов на основе количества цифровых объектов, подлежащих включению в переранжированный набор 712 цифровых объектов. В представленных на фиг. 7 вариантах осуществления изобретения количество цифровых объектов, подлежащих включению в переранжированный набор 712 цифровых объектов, определено равным N. Таким образом, сервер 106 выбирает N первых цифровых объектов из поднабора 612 цифровых объектов, ранжирует эти цифровые объекты согласно соответствующим значениям связанной с ними дополнительной характеристики 208 и в результате формирует переранжированный набор 712 цифровых объектов.

[135] Затем переранжированный набор 712 цифровых объектов в ответ на запрос фильтрации представляется пользователю 112 в области 126 отображения результатов сервиса 110 цифровых объектов, реализуемого на электронном устройстве 108.

[136] Описанные выше архитектура и примеры позволяют выполнять способ ранжирования цифровых объектов на основе связанной с ними целевой характеристики. На фиг. 8 представлена блок-схема способа 800 согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии. Способ 800 выполняется сервером 106.

[137] Шаг 802: выбор из пула цифровых объектов на основе пользовательского запроса набора цифровых объектов, релевантного запросу, с учетом целевой характеристики цифровых объектов.

[138] Способ 800 начинается с шага 802, на котором сервер 106 в ответ на пользовательский запрос выбирает (например, из пула 122 цифровых объектов) набор цифровых объектов. Например, сервер 106 может выбрать набор 512 цифровых объектов в ответ на пользовательский запрос 502, отправленный пользователем 112 сервису цифровых объектов (например, сервису 110 цифровых объектов) с использованием электронного устройства 108.

[139] В не имеющих ограничительного характера вариантах осуществления настоящей технологии из набора 512 цифровых объектов выбираются цифровые объекты, релевантные пользовательскому запросу 502, на основе значений связанной с ними целевой характеристики. С этой целью сервер 106 может формировать для каждого объекта из набора 512 цифровых объектов соответствующее значение параметра 206 ранжирования на основе целевой характеристики. Сформированные таким образом значения параметра 206 ранжирования подходят для ранжирования связанных с ними цифровых объектов. Таким образом, набор 512 цифровых объектов может быть упорядочен согласно соответствующим значениям параметра 206 ранжирования.

[140] Шаг 804: получение от электронного устройства запроса фильтрации для переранжированного набора цифровых объектов из набора цифровых объектов, при этом запрос фильтрации основан на дополнительной характеристике, отличной от целевой характеристики.

[141] На шаге 804 сервер 106 способен получать указание на запрос фильтрации (например, указание 118 на запрос фильтрации) для переранжированного набора цифровых объектов (например, для переранжированного набора 712 цифровых объектов).

[142] При этом в не имеющих ограничительного характера вариантах осуществления настоящей технологии каждый набор 512 цифровых объектов также имеет соответствующее значение по меньшей мере одной дополнительной характеристики (например, дополнительной характеристики 208).

[143] В не имеющих ограничительного характера вариантах осуществления настоящей технологии дополнительная характеристика 208 отличается от целевой характеристики цифровых объектов из набора 512 цифровых объектов. Кроме того, значения дополнительной характеристики 208 не указывают на релевантность цифровых объектов из набора 512 цифровых объектов пользовательскому запросу 502. Соответственно, ранжирование набора 512 цифровых объектов согласно соответствующим значениям дополнительной характеристики 208 отличается от ранжирования согласно значениям параметра 206 ранжирования на основе целевой характеристики.

[144] В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии дополнительная характеристика 208 указывает на собственный параметр цифрового объекта и другого объекта из набора 512 цифровых объектов.

[145] В других не имеющих ограничительного характера вариантах осуществления настоящей технологии дополнительная характеристика 208 указывает на параметр относительной ценности цифрового объекта по сравнению с другим цифровым объектом из набора 512 цифровых объектов.

[146] Соответственно, если сервис 110 цифровых объектов представляет собой платформу для электронной торговли, то цифровые объекты могут представлять собой предложения конкретного товара, а их дополнительная характеристика 208 может представлять собой цену, дату отправки или популярность у пользователей и т.п. либо их относительную ценность.

[147] Таким образом, указание 118 на запрос фильтрации основывается на дополнительной характеристике 208, в соответствии с которой пользователь 112 может переранжировать набор 512 цифровых объектов согласно соответствующим значениям связанной с ними дополнительной характеристики 208, например, по возрастанию.

[148] Шаг 806: определение для цифрового объекта из набора цифровых объектов соответствующего параметра объекта, указывающего на вероятность того, что включение цифрового объекта в переранжированный набор цифровых объектов увеличит метрику качества переранжированного набора цифровых объектов с учетом целевой характеристики цифровых объектов.

[149] На шаге 806 сервер 106 способен определять для каждого цифрового объекта из набора 512 цифровых объектов соответствующее значение параметра 510 объекта. Значение параметра 510 объекта, связанное с цифровым объектом из набора 512 цифровых объектов, указывает на вероятность того, что включение цифрового объекта в переранжированный набор 712 цифровых объектов увеличит метрику качества переранжированного набора 712 цифровых объектов.

[150] Метрика качества указывает на «полезность» переранжированного набора 712 цифровых объектов и согласно не имеющим ограничительного характера вариантам осуществления настоящей технологии может включать в себя одно из следующего:

- функцию метрики качества на основе дисконтированного кумулятивного показателя (DCG);

- функцию метрики качества на основе нормализованного дисконтированного кумулятивного показателя (NDCG);

- функцию метрики качества на основе ожидаемого взаимного ранга (ERR);

- функцию метрики качества на основе средней точности (MAP);

- функцию метрики качества на основе среднего взаимного ранга (MRR).

[151] В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии метрика качества может основываться на релевантности переранжированного набора 712 цифровых объектов пользовательскому запросу 502. В этом отношении релевантность основывается на соответствующих значениях параметра 206 ранжирования, связанных с цифровыми объектами из переранжированного набора 712 цифровых объектов.

[152] В других не имеющих ограничительного характера вариантах осуществления настоящей технологии метрика качества может основываться на соответствующих предсказанных значениях дополнительной характеристики 208, связанных с первыми N цифровыми объектами из переранжированного набора 712 цифровых объектов.

[153] В не имеющих ограничительного характера вариантах осуществления настоящей технологии значения параметра 510 объекта формируются сервером 106 с использованием алгоритма MLA, обученного предсказанию вероятности того, что включение цифрового объекта в переранжированный набор 712 цифровых объектов увеличит метрику качества. Для этого сервер 106 способен формировать обучающий набор данных для обучения алгоритма MLA, как описано выше со ссылками на фиг. 2-4.

[154] Таким образом, в не имеющих ограничительного характера вариантах осуществления настоящей технологии обучающий набор данных, используемый для обучения алгоритма MLA, содержит набор обучающих цифровых объектов, каждый из которых связан (а) с обучающим запросом, который использовался для формирования обучающего набора цифровых объектов; (б) с указанием на дополнительную характеристику обучающего цифрового объекта; (в) с формируемой оценщиком меткой, указывающей на обязательность включения обучающего цифрового объекта в поднабор обучающих цифровых объектов с учетом дополнительной характеристики и релевантности обучающего цифрового объекта обучающему запросу.

[155] В не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 106 способен формировать и использовать в качестве части обучающего набора данных для обучения алгоритма MLA следующие дополнительные признаки: (1) наибольшее значение дополнительной характеристики среди первых N обучающих цифровых объектов в поднаборе обучающих цифровых объектов; (2) наибольшее значение параметра ранжирования среди первых N обучающих цифровых объектов в поднаборе обучающих цифровых объектов; (3) среднее значение дополнительной характеристики 208 для первых N обучающих цифровых объектов в поднаборе обучающих цифровых объектов; (4) среднее значение параметра 206 ранжирования для первых N обучающих цифровых объектов в поднаборе обучающих цифровых объектов.

[156] В не имеющих ограничительного характера вариантах осуществления настоящей технологии алгоритм MLA представляет собой алгоритм MLA на основе дерева решений с градиентным бустингом.

[157] В не имеющих ограничительного характера вариантах осуществления настоящей технологии значения параметра 510 объекта основываются на компромиссе между количеством цифровых объектов, подлежащих включению в переранжированный набор 712 цифровых объектов, и их релевантностью, представленной соответствующими значениями параметра 206 ранжирования. Иными словами, обученный алгоритм MLA в известном смысле обеспечивает оптимальное соотношение между релевантностью цифровых объектов, размещенных в более высоких позициях ранжированного списка, и релевантностью перемещенных цифровых объектов.

[158] В не имеющих ограничительного характера вариантах осуществления настоящей технологии количество цифровых объектов в переранжированном наборе 712 цифровых объектов может выбираться равным количеству более высоких позиций в переранжированном наборе 712 цифровых объектов. Согласно этим вариантам осуществления изобретения, количество более высоких позиций в переранжированном наборе 712 цифровых объектов зависит от области 126 отображения результатов, связанной с электронным устройством 108.

[159] Шаг 808: выбор цифровых объектов на основе соответствующих параметров объектов.

[160] Сформировав для каждого цифрового объекта из набора 512 цифровых объектов соответствующее значение параметра 510 объекта, сервер 106 на основе этих значений и количества цифровых объектов, подлежащих включению, способен выбирать цифровой объект для включения в переранжированный набор 712 цифровых объектов.

[161] В не имеющих ограничительного характера вариантах осуществления настоящей технологии этот выбор может включать в себя выбор на основе заранее заданного порогового значения параметра 510 объекта.

[162] Шаг 810: ранжирование переранжированного набора цифровых объектов на основе соответствующих значений дополнительной характеристики и формирование переранжированного набора цифровых объектов, содержащего выбранные цифровые объекты, ранжированные согласно дополнительной характеристике.

[163] На шаге 810 сервер 106 способен упорядочивать цифровые объекты, выбранные на шаге 808 для переранжированного набора 712 цифровых объектов, согласно соответствующим значениям связанной с ними дополнительной характеристики 208 и в результате формировать переранжированный набор 712 цифровых объектов.

[164] Ранжирование цифровых объектов согласно их соответствующим значениям дополнительной характеристики 208 соответствует указанию 118 на запрос фильтрации.

[165] Затем в не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 106 может формировать пакет 120 данных, указывающий на переранжированный набор 712 цифровых объектов, и отправлять его электронному устройству 108 для представления переранжированного набора 712 цифровых объектов пользователю 112 в области 126 отображения результатов сервиса 110 цифровых объектов.

[166] В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии способ 800 может быть реализован в виде одного этапа, когда список цифровых объектов ранжируется и фильтруется на одном шаге (т.е. представленный список является ранжированным и отфильтрованным списком). В других вариантах осуществления настоящей технологии способ 800 может быть реализован в виде двух этапов: сначала формируется ранжированный список цифровых объектов (на основе целевой характеристики), а затем в ответ на запрос фильтрации формируется переранжированный и отфильтрованный список.

[167] Очевидно, что не все упомянутые в данном описании технические эффекты должны присутствовать в каждом варианте осуществления настоящей технологии.

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

[169] Приложение А

Обучение выбору для заранее заданного ранжирования

Анонимные авторы (Анонимная организация, анонимный город, анонимный регион, анонимная страна. Для корреспонденции: anon.email@domain.com)

Аннотация

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

1. Введение

Современные поисковые системы часто сталкиваются с задачей обеспечения пользователей упорядоченными списками элементов, наилучшим образом соответствующими их потребностям в разных контекстах. Одна из наиболее важных задач заключается в предоставлении пользователю списка релевантных элементов, упорядоченных не по их релевантности, а по особому атрибуту элементов (часто выбираемому пользователем после формулирования первоначального запроса). Примерами таких случаев могут служить упорядочение по времени на веб-сайте социальных медиа (Hasanain et al., 2015) или упорядочение предложений по цене на веб-сайте электронной торговли (например, Amazon (Предварительный материал. Для рассмотрения оргкомитетом международной конференции по машинному обучению (International Conference on Machine Learning (ICML)). Не для распространения. https://www.amazon.com). В этом случае алгоритмическая проблема сводится к выбору элементов с целью включения в список для показа пользователю.

Выбор всех полученных элементов, в общем случае, является плохим вариантом, поскольку наиболее подходящие по особому атрибуту элементы могут оказаться совершенно нерелевантными нуждам пользователя, например, наиболее дешевые предложения часто не являются наиболее релевантными пользовательскому запросу. В действительности алгоритмы выбора часто оказываются далекими от совершенства и множество пользователей, например, популярных движков для поиска товаров или работы, регулярно страдают от низкого качества ранжирования результатов по цене или по времени публикации. В частности, см. иллюстративные статистические данные в работе (Spirin et al., 2015, Section 1) и рис. 1 в дополнительных материалах, где представлена страница с результатами в одной из наиболее популярных систем поиска товаров.

Несмотря на наличие большого количества литературы по обучению ранжированию, неожиданно оказалось, что работы по обучению выбору для заранее заданного ранжирования отсутствуют. Один простой способ выбора, называемый далее подходом с отсечкой, предназначен (1) для обучения модели предсказания релевантности и (2) для выбора только тех элементов, предсказанная релевантность которых превышает некоторый порог (Hasanain et al., 2015). Как показано в работе (Spirin et al., 2015), этот подход оказывается довольно грубым и в целом обеспечивает совершенно неэффективное решение. В самом деле, с одной стороны, требуется показать наиболее релевантные элементы в начале ранжированного списка и поэтому следует исключить из их числа все хотя бы немного менее релевантные элементы. С другой стороны, пороговое значение, подходящее для такой цели, скроет от пользователя также много релевантных результатов с пониженным рангом. Например, для упорядоченного по особому атрибуту списка элементов (d1, d2, d3) с соответствующими значениями релевантности (2, 7, 1) максимальное значение дисконтированного кумулятивного показателя (Discounted Cumulative Gain (, где – релевантность элемента в позиции ), см. (Järvelin & Kekäläinen, 2002) для первых трех результатов (DCG@3) достигается при выборе набора (d2, d3), при этом элемент d3 оказывается выбранным, а элемент d1 – нет, несмотря на более высокое значение релевантности (подробности см. в табл. 1). В то же время подход с отсечкой при лучшем пороговом значении релевантности выбирает только элемент d2, что гораздо ближе к исходному списку, чем лучшее решение согласно DCG@3.

Если предположить, что значения релевантности известны, задача выбора превращается в простую комбинаторную задачу с конкретным решением, сложность которой имеет квадратную зависимость от количества элементов-кандидатов (Spirin et al., 2015). К сожалению, это решение оказывается неприменимым на практике для высоконагруженных систем из-за высокой временно́й сложности и несовместимости с распределенной архитектурой систем для крупномасштабных поисковых движков (см. подробности в разделе 2.1).

Табл. 1. Пример неоптимальности подхода с отсечкой

Исходный список Лучшая отсечка Лучший выбор
Список d1, d2, d3 d2 d2, d3
Значения
атрибутов
1, 2, 3 2 2, 3
Значения
релевантности
2, 7, 1 7 7, 1
Показатель DCG@3 списка 6,92 7 7,63

В настоящей работе задача выбора сформулирована как проблема машинного обучения, в которой требуется обучить модель выбора F, принимающую решение по каждому элементу d – включать его в список (F(d) = 1) или не включать (F(d) = 0). В отличие от обычных задач классификации, целью при этом является максимизация основанной на релевантности меры качества ранжирования выбранного набора элементов, упорядоченного заранее заданным образом. Задача в такой формулировке далее называется проблемой обучения выбору по порядку (Learning to Select with Order (LSO)) по аналогии с проблемой обучения ранжированию (Learning To Rank (LTR)). Для решения этой задачи предложены практически реализуемые и эффективные алгоритмы выбора.

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

(1) Сформулирована проблема обучения выбору по порядку (LSO) - новая задача машинного обучения с особой целевой функцией.

(2) Предложено два подхода к решению проблемы LSO, включающие в себя сглаживание целевой функции и два способа градиентной оценки: градиент политики и использование нижней границы целевой функции, см. раздел 4.2.

(3) Для исключения локальных экстремумов невыпуклой сглаженной целевой функции ее оптимизация сочетается с оптимизацией ее выпуклой аппроксимации, см. раздел 4.3.

(4) В офлайн- и онлайн-экспериментах с крупномасштабным поисковым движком для электронной торговли предложенные подходы в сочетании с деревьями решений методом градиентного бустинга (GBDT) продемонстрировали заметное превосходство над существующими решениями проблемы LSO.

2. Постановка задачи

2.1. Алгоритмы выбора: локальные или глобальные

Сначала описана передовая системная архитектура современных поисковых движков, в целом определяющая постановку вопроса для задачи выбора, сформулированной в разделе 1. Крупные коммерческие поисковые системы с миллиардами элементов в базах данных и миллионами ежедневно обслуживаемых пользователей обычно полагаются на распределенную обработку запросов. Это означает параллельную работу нескольких поисковых движков над раздельными корзинами элементов-кандидатов (на первом этапе ранжирования) и агрегирование элементов с высшим рейтингом в финальную страницу с результатами поиска на метапоисковом движке (на втором этапе ранжирования), см. (Glover et al., 1999; Patel & Shah, 2011; Wang et al., 2011).

В такой задаче выбора элементы с высшим рейтингом выбираются по особому атрибуту. Следовательно, критически важно обеспечить правильный выбор на первой стадии до определения элементов с высшим рейтингом. В противоположном случае метапоисковый движок получит в основном нерелевантные элементы от каждого движка первой стадии. Имея меньшее количество элементов-кандидатов, на уровне метапоиска можно реализовать дополнительный выбор на основе более сложных признаков по аналогии с иерархическими алгоритмами ранжирования результатов веб-поиска (Glover et al., 1999; Wang et al., 2011).

В то же время, поскольку каждому поисковому движку первой стадии, где должен производиться выбор, доступно лишь одно подмножество из числа всех элементов-кандидатов, алгоритм выбора не имеет доступа к агрегированной информации обо всех элементах-кандидатах. Это означает, что любой глобальный алгоритм выбора (по аналогии с подходами глобального ранжирования (Ji et al., 2009)), требующий полного списка элементов-кандидатов для принятия решения по одному из них, оказывается неприменимым. В частности, невозможно применить квадратично-временной способ оптимизации из работы (Spirin et al., 2015), более подробно см. в разделе 3.

Данная ситуация относится к обучению алгоритма локального выбора, одновременно принимающего решение по каждому элементу без явных данных о других элементах. Такой локальный подход позволяет минимизировать задержку ответа системы, что особенно важно для повышения удовлетворенности пользователя и, в конечном счете, для обеспечения дохода от поисковой системы (Schurman & Brutlag, 2009). Поэтому передовые модели LTR являются локальными (Liu et al., 2009a).

2.2. Формулировка проблемы LSO

Рассмотрим набор упорядоченных наборов (называемых далее списками). Каждый список состоит из элементов общим числом . На практике список соответствует набору элементов-кандидатов, полученных в определенном контексте человеко-системного взаимодействия, элемент соответствует контекстно-элементной паре, представленной вектором для признаков и назначенным значением релевантности r, неизвестным системе. Элементы из списка распределены по множеству поисковых движков первой стадии. Для удобства предположим, что элементы каждого списка упорядочены по возрастанию (без потери общности) особого атрибута (т.е. , что может соответствовать дате публикации для новостей и новостных лент социальных медиа или цене для поискового движка для товаров. В популярном контексте количество элементов может достигать миллионов. Списки из набора представляют собой выборки независимых одинаково распределенных величин (i.i.d.) из некоторого распределения ℙ в пространстве списков любой длины. Кроме того, реализована некоторая целевая мера Q для списков, на практике соответствующая мере качества ранжирования, например, дисконтированному кумулятивному показателю (DCG), ожидаемому взаимному рангу (Expected Reciprocal Rank (ERR)), см. (Chapelle et al., 2009), или точности с учетом ранга (Rank-Biased Precision (RBP)), см. (Moffat & Zobel, 2008). Ее значение определяется только вектором значений релевантности элемента для некоторого и, естественно, она должна быть неубывающей для каждого аргумента .

Алгоритм выбора определяется как бинарное правило выбора на основе признака , а результат его применения к списку представляет собой выбранный список , где и . Проблема обучения выбору по порядку (LSO) формулируется как обучение алгоритма выбора на наборе для максимизации ожидаемого качества ранжирования выбранного списка , где исходный список представляет собой выборку из ℙ:

2.3. Анализ

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

В разделе 1 дополнительных материалов сформулированы некоторые естественные требования к целевой мере Q и с их учетом доказано следующее положение:

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

Непосредственно из него может быть выведено следующее следствие:

Следствие 1. Если выбран элемент , то должны быть выбраны также и все элементы с более низкими позициями (т.е. ), имеющие по меньшей мере равную релевантность ().

Фактически, алгоритм оптимального выбора должен быть в целом более селективным в верхней части списка, чем в нижней его части.

3. Другие работы

Насколько известно авторам настоящей работы, единственный изученный алгоритм выбора, применимый к крупномасштабным системам, основан на подходе с отсечкой, в котором выбираются либо первые k элементов на основе предсказания релевантности, либо элементы с предсказанной релевантностью выше порогового значения b. Этот подход имеет линейную сложность и широко используется в задачах различного назначения, включая выборку из микроблогов (Hasanain et al., 2015), отсечение по статическим индексам (Carmel et al., 2001) или отсечение элементов в процессе извлечения (Wang et al., 2011). Подход с отсечкой часто может быть улучшен путем настройки для каждого контекста (например, для пользовательского запроса). Обычно это реализуется с использованием контекстных признаков для предсказания оптимального значения либо k (в случае отсечки по рангу) (Hasanain et al., 2015; Wang et al., 2011), либо b (в случае отсечки по оценке) (Carmel et al., 2001; Wang et al., 2011). Согласно анализу оптимальных списков в разделе 2.3, даже лучшее значение порога отсечки дает слишком грубый результат: решение зависит только от релевантности элемента и не учитывает его позицию (см. Положение 1 и пример в разделе 1).

Если значения релевантности известны, проблема LSO может рассматриваться как комбинаторная задача оптимизации (подобно тому, как проблема LTR при известных значениях релевантности вырождается в задачу сортировки). В случае аддитивной целевой меры Q в работе (Spirin et al., 2015) предложен точный алгоритм решения этой задачи с временно́й сложностью , где – количество элементов-кандидатов. Этот алгоритм назван точным алгоритмом с квадратичной сложностью (Exact Quadratic Complexity Algorithm (EQA)). В духе динамического программирования он выполняет проход сверху вниз по списку и для каждых формирует наилучшее подмножество длиной j из списка длиной . Список формируется как лучший среди и , где «» означает конкатенацию. На практике при неизвестных значениях релевантности в работе (Spirin et al., 2015) для предсказания релевантности применен алгоритм EQA, обученный с использованием функции потерь среднеквадратичной ошибки (MSE). Такой подход является глобальным и, кроме того, он имеет квадратичную зависимость сложности от количества элементов, что делает его неприменимым для архитектуры распределенных систем (см. раздел 2). Даже в отношении проблемы глобального выбора этот подход не обязательно дает лучшее решение, поскольку он не является сквозным. В частности, выбор функции потерь (MSE в работе (Spirin et al., 2015)) может быть адаптирован к посписочной целевой функции Q. В случае проблемы LTR посписочные алгоритмы существенно превосходят поточечные алгоритмы (Liu et al., 2009a). В настоящей работе для решения локальной проблемы LSO предложен подход с прямой оптимизацией.

4. Подход

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

4.1. Предсказание оптимального решения

Сначала предлагается построение модели M, предсказывающей решение алгоритма EQA по элементу на основе признаков этого элемента (см. раздел 3). Для этого алгоритм EQA в офлайн-режиме применяется к наборам элементов в обучающем наборе данных D с известными метками релевантности (здесь следует напомнить, что работа алгоритма EQA в онлайн-режиме невозможна). В результате для каждого элемента принимается оптимальное бинарное решение . Затем бинарный классификатор M обучается на обучающих примерах до современной модели классификации LogitBoost, см. (Friedman et al., 2000) путем максимизации логарифмической функции правдоподобия (т.е. путем минимизации логистических потерь).

После обучения модели M на ее основе определяется алгоритм выбора в виде , где - предсказание модели для вектора признаков , порог - постоянный гиперпараметр алгоритма , а означает индикатор события .

В сравнении с подходом с отсечкой и предсказанным порогом, как описано в разделе 3, в предложенном подходе, названном оптимальным предиктором выбора (Optimal Selection Predictor (OSP)), в качестве цели использован оптимальный выбор вместо выбора с лучшей отсечкой. Поэтому ожидается, что его характеристики с точки зрения целевой функции (1) проблемы LSO окажутся выше характеристик подхода с отсечкой. Тем не менее, функция потерь, оптимизированная в соответствии с подходом OSP (а именно в отношении логистических потерь), не имеет непосредственного отношения к целевой функции . В частности, величина потерь для некоторого элемента не зависит от положения этого элемента в выбранном списке (а зависит лишь от бинарного решения алгоритма EQA и от вероятности, предсказанной алгоритмом OSP). В то же время влияние ошибки на целевую меру снижается с увеличением (например, как в случае показателя DCG). Этот эффект напоминает слабые места поточечного подхода к задаче LTR, см. (Liu et al., 2009b, раздел 2.5.2).

4.2. Прямая оптимизация целевой меры

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

для некоторых , т.е. выбираются элементы с оценками выше порогового значения (как предложено в алгоритме OSP). Тем не менее, в этом случае целевая мера является прерывистой функцией от оценки , а она должна быть дифференцируемой. В предыдущих публикациях (Chapelle & Wu, 2010; Wu et al., 2009; Valizadegan et al., 2009) была описана аналогичная сложность в отношении меры качества ранжирования в проблеме LTR. Несмотря на то, что мера качества ранжирования (например, показатель DCG) реализует одну функцию от релевантности элементов в результирующем списке, она соответствует различным функциям от вектора оценок элементов-кандидатов в проблемах LTR и LSO. Разумеется, что результирующий список элементов и, таким образом, их значения релевантности, формируется на основе такого вектора по-разному: путем ранжирования по оценкам элементов в случае LTR и путем выбора на основе порогового значения в случае LSO. Таким образом, непосредственное применение предложенного способа сглаживания к проблеме LSO оказывается невозможным.

Следует отметить, что алгоритм выбора является бинарным классификатором, который на основе признаков элемента принимает решение относительно выбора этого элемента. Это приводит к мысли об адаптации к поставленной задаче технологии сглаживания, являющейся наиболее передовой в отношении проблемы бинарной классификации и используемой в качестве компонента в модели LogitBoost и в логистической регрессионной модели (Chapelle et al., 2015).

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

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

Тогда для алгоритма выбора ℱ и списка элементов выбранный список является случайным и имеет следующее распределение :

где , а - выбранный список, соответствующий вектору решений относительно выбора .

Далее целевая мера Q логично расширяется до меры с учетом ожидаемого значения Q в отношении случайности выбранного списка

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

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

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

Градиент политики. Первый подход направлен на оценку ожидания в уравнении (4) путем выборки списков методом Монте Карло согласно распределению из уравнения (3). Этот способ известен как метод отношения правдоподобия (Glynn, 1990) в случае более общей проблемы, представляющей собой оценку градиента ожидания функции вознаграждения ( в случае проблемы LSO) случайной переменной (список в случае проблемы LSO). Алгоритм оптимизации, основанный на этой методике, известен как градиент политики (Baxter & Bartlett, 2001).

Поскольку такая оценка градиента имеет высокую вариативность, в работе (Kimura et al., 1995) было предложено использовать нижнюю границу вознаграждения : если рассматривать вознаграждение вместо в процедуре оценки градиента, то использование подходящего значения позволяет предотвратить смещение этой оценки и при этом сократить ее вариативность. Действительно, можно ожидать, что переменная из уравнения (4) имеет низкую вариативность, если среднее значение переменной близко к нулю, поскольку множитель меняет знак с изменением , а величина слабо зависит от Более подробный анализ см. в работе (Kimura et al., 1995).

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

В результате такой подход с градиентом политики оказывается основанным на следующей оценке градиента:

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

Оптимизация нижней границы. Другой подход относится к аппроксимации целевой функции другой функцией от предсказаний модели с учетом градиента, вычисляемого точно и с низкой сложностью. Для этого можно рассмотреть наиболее практичный случай аддитивной целевой меры , где - выпуклая функция от позиции . Например, этому условию соответствуют показатели DCG и RBP. В этом случае преобразование идеи, предложенной в работе (Valizadegan et al., 2009) для проблемы LTR, приводит к тому, что целевая функция может иметь нижнюю границу согласно следующей мере:

где - альтернативное написание для . Очевидно, что использование выражения для позиции элемента в выбранном списке (в случае включения в него этого элемента) и применение неравенства Йенсена дает следующий результат:

Градиенты целевой функции соответствуют следующему уравнению:

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

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

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

Реализация всех предложенных здесь подходов описана в разделе 5.

4.3. Борьба с локальным экстремумом

Тем не менее, в случае проблемы LSO оба вышеописанных подхода имеют существенный недостаток: обе целевые функции и в пространстве предсказаний модели на обучающих примерах могут иметь точки локального максимума, не совпадающие с точками глобального максимума (для параметрической модели точка экстремума в пространстве предсказаний модели соответствует экстремуму в пространстве параметров , если непрерывна в отношении и точка лежит в области значений ). Результаты экспериментов показывают (см. раздел 6), что этот недостаток критичен для эффективного обучения алгоритмов выбора, описанных в разделе 4.2. Следующая теорема показывает, что такие точки локального максимума возможны даже в случае единственного списка, т.е. когда распределение ℙ сконцентрировано в нем (доказательство см. в разделе 2 дополнительных материалов).

Теорема 1. В отношении проблемы LSO с мерой качества :

1) если весовой коэффициент является логарифмически выпуклой (вогнутой) функцией от позиции (т.е. ), то существует список и такой алгоритм выбора , что обеспечивает локальный, а не глобальный максимум для и для , где , в пространстве , где распределение ℙ исходного списка сконцентрировано в списке , т.е. ;

2) если множество является геометрической прогрессией, т.е. , то для любого списка в случае глобальный максимум для и совпадает с единственным локальным максимумом.

В частности, условие относительно логарифмически выпуклых взвешивающих функций действительно и для показателя DCG. Следовательно, подходы прямой оптимизации, основанные на градиентном спуске, могут ошибочно тяготеть к точкам локального максимума. Следует отметить, что в случае алгоритмов индивидуальной оценки каждого элемента эта особенность характерна для проблемы LSO, в отличие от проблемы LTR, в которой любая функция потерь имеет единственный локальный минимум. Разумеется, что для точки (ранжированного списка элементов), отличной от точки глобального оптимума , существует пара соседних элементов в , ранжированных иначе, чем в . Тогда возможно заменить только эти два элемента путем смены модели предсказания для одного из них и таким образом повысить качество ранжирования. Следовательно, точка не является точкой локального минимума.

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

Рис. 1. Схематическая иллюстрация двух шагов обучения: (а) алгоритм OSP: оптимизация выпуклой аппроксимации (функции логистических потерь) и (б) прямая оптимизация .

5. Условия эксперимента

Данные. Данные собирались из «живых» потоков поисковых запросов, сделанных в октябре-ноябре 2017 г. к популярному движку для поиска товаров, обрабатывающему миллионы запросов пользователей ежедневно и консолидирующему предложения товаров от онлайн-магазинов. При этом рассматривались только те запросы, в которых пользователи запрашивали упорядочение по возрастанию цены и в результате был сформирован набор объемом 30 тыс. запросов. При этом предложение соответствует элементу в терминах раздела 2, а цена предложения соответствует особому атрибуту. Для каждого запроса рассматривались лишь первые 500 наиболее дешевых предложений-кандидатов из десятков тысяч предложений (в среднем по 60 тыс. предложений), выбранных слабым рабочим алгоритмом выбора, при этом выбирались все предложения, содержащие в названии или в описании по меньшей мере одно слово из запроса. Затем все запросы из собранного набора случайным образом разделялись на пять частей одинакового размера для выполнения пятикратной кросс-валидации: на каждом i-ом проходе из пяти проходов 80% запросов () использовались для обучения, 10% запросов () использовались для настройки гиперпараметров алгоритма и 10% запросов () использовались для тестирования. Эти данные доступны в открытом источнике (https://drive.google.com/open?id=1WQwYcImup54yl42oiGw-8zujwqtXVo6).

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

Тем не менее, в соответствии с формой алгоритма оптимального выбора (см. Положение 1), в случае проблемы LSO полезно неявно предсказывать не только релевантность элемента (как в случае проблемы LTR), но также и позицию этого элемента в исходном упорядоченном списке L и пороговое значение для этого списка, зависящее от агрегированной релевантности элементов, расположенных ниже в этом списке L. Это приводит к формированию признаков, в которых закодировано распределение релевантности и цены по предложениям в списке L. Таким образом, для экспериментов было добавлено четыре признака (для всех методик, включая образцовые): модели, обученные предсказанию средней цены (или релевантности) для первого предложения и первых 10 предложений по значению рабочей релевантности обозначены как AvPricePred (или AvRelPred).

Метки. Оценка релевантности каждого элемента, назначенная при рабочем ранжировании, (далее называемая рабочей релевантностью), использована в качестве предсказанной релевантности в образцовых подходах и в качестве объективного значения релевантности в предложенных подходах. Подробное описание см. в разделе 5 дополнительных материалов.

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

Для основной независимой оценки релевантности страницы с результатами были собраны суждения живых людей относительно релевантности с пятью степенями (от 0 до 4) для первых 10 результатов из каждого выбранного списка, сформированного тестируемыми алгоритмами, обученными на наборе и примененными к 2 тыс. запросов из набора . Таким образом измерялись показатель DCG@10 и точность p@10 (доля по меньшей мере частично релевантных предложений, т.е. содержащих метки релевантности 1, 2, 3, 4, среди первых 10 предложений), а также показатель «тупых» предложений stup@12 (доля «тупых» (особый подкласс нерелевантных результатов, отличающийся предельной/удивительной нерелевантностью) результатов среди результатов на первой странице).

Затем наиболее показательные алгоритмы сравнивались в условиях онлайн-экспериментов в течение трех дней (результатом которых стали 23 тыс. уникальных пользователей и 100 тыс. запросов для каждого алгоритма). Для оценки использовались следующие основные рабочие метрики: среднеобратный ранг «клика» (MRR) (Craswell, 2009) (равный инвертированному значению позиции первого «клика» или нулю при отсутствии «клика»), коэффициент отказов (доля запросов без «кликов») и коэффициент «кликов» CTR@12 (доля результатов с «кликами» среди первых 12 результатов). По соображениям конфиденциальности приводятся лишь относительные величины этих онлайн-метрик.

Алгоритм машинного обучения. В качестве алгоритма машинного обучения (ML) для всех сравниваемых подходов был выбран алгоритм деревьев решений с градиентным бустингом (GBDT). В частности, была использована реализация CatBoost (https://catboost.ai) с открытым исходным кодом (Prokhorenkova et al., 2018) из комплекта для Python. Алгоритм GBDT представляет собой современную методику для решения многих практических задач, включая обучение ранжированию при веб-поиске (Chapelle & Chang, 2011; Burges, 2010) и предсказание «кликов» (Konig et al., 2009; Trofimov et al., 2012). CatBoost превосходит наиболее популярные реализации алгоритма GBDT с открытым исходным кодом - XGBoost (Chen & Guestrin, 2016) и LightGBM (Ke et al., 2017), согласно результатам сравнения в работе (Prokhorenkova et al., 2018).

Для формального описания алгоритма обучения, используемого для конкретной функции потерь, следует заменить L в алгоритме 3 в работе (Prokhorenkova et al., 2018) на эту функцию потерь. Патч, необходимый для получения предложенной реализации на основе CatBoost release 0.10.04, представлен в приложенном программном файле. Использованные в экспериментах параметры CatBoost приведены в разделе 4 дополнительных материалов. Полный исходный код также доступен (https://github.com/TakeOver/catboost/tree/0.10.4_release).

Тестируемые алгоритмы.

Oracle: предназначен для нахождения оптимального списка путем применения алгоритма EQA (см. раздел 3) в отношении объективных меток релевантности с целью оптимизации показателя DCG-RR. Oracle обеспечивает недостижимый идеальный список.

Образцовые алгоритмы, описанные в разделах 1 и 3.

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

ConstCutoff предназначен для выбора элементов с предсказанной релевантностью выше постоянного порогового значения , подобранного для (подобранные значения этих и других описанных ниже порогов см. в табл. 3 дополнительных материалов).

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

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

OSP (Optimal Selection Predictor) - модель, обученная предсказанию решений для оптимального выбора (см. раздел 4.1).

PG (Policy Gradient) модель предсказания, обученная прямой оптимизацией функции , сглаженной модификации оригинальной меры , с оценкой градиента на основе выборки, начиная с предсказаний для всех обучающих примеров (см. раздел 4.2).

LBO (Lower Bound Optimization) - модель предсказания, обученная прямой оптимизацией функции , нижней границы функции , начиная с предсказаний (см. раздел 4.2).

OSP + PG / OSP + LBO - модель предсказания, обученная как OSP в ходе первых итераций, а затем, после преобразования предсказания, обученная как PG / LBO в ходе оставшихся итераций ( и требуют подбора) (см. раздел 4.3). Таким образом, в этом подходе используется тот же лимит из 1000 обучающих итераций, что и в других подходах на основе машинного обучения. Подобранные значения параметра масштабирования равны, соответственно, 2 и 1. Количество сформированных выбранных списков в расчете на каждый обучающий список при оценке градиента согласно уравнению (5) был установлен равным 1, поскольку множественное формирование списков не повышало качество при экспериментах.

6. Результаты эксперимента

Анализ проблемы локального экстремума. Прежде всего, следует отметить, что алгоритмы LBO и PG с подобранными параметрами отличаются от алгоритма WeakCutoff незначительно: процессы их обучения начинаются с решений WeakCutoff () и эти решения почти не изменяются (обученные алгоритмы исключают, соответственно, 0 и 0,2 элемента на запрос). При начальных решениях ни один из этих обученных алгоритмов не достиг даже качества алгоритма WeakCutoff. Для более понятной иллюстрации проблемы локального экстремума, описанной в разделе 4.3, для конкретного алгоритма стохастического выбора были определены трудные элементы , для которых решение относительно выбора, достаточно надежное при , оказывается глобально неоптимальным (т.е. не совпадает с оптимальным выбором), но локально оптимальным (т.е. оптимальным с учетом фиксированных решений относительно выбора других элементов). Среднее количество трудных элементов в расчете на список представлено в табл. 3 дополнительных материалов. Очевидно, что алгоритмы LBO и PG заметно страдают от таких трудных элементов: для них значение составило, соответственно, 62,6 и 58,9, в то время как алгоритм Oracle исключал в среднем 78,9 элементов. Поскольку значение оказывается довольно малым для алгоритма OSP, представляется целесообразным начинать прямую оптимизацию именно с этого алгоритма. Следует отметить, что в случае начала с алгоритма OSP алгоритмы LBO и PG даже уменьшают количество трудных элементов (значение составило 6,1 и 10,6), т.е. исправляют ошибки алгоритма OSP.

Основные результаты. Результаты офлайн-экспериментов представлены в табл. 2. Очевидно, что подход ConstCutoff превосходит подход WeakCutoff по всем метрикам. Тем не менее, дополнительный рост при его доработке до QueryCutoff оказывается еще более впечатляющим, что подчеркивает важность признаков запросов в проблеме LSO. Это не удивительно, поскольку они содержат информацию о релевантности и распределении цен среди предложений-кандидатов, что полезно в проблеме LSO, согласно предположениям, сделанным при определении признаков и изложенным в разделе 5.

Далее, алгоритм OSP обеспечивает заметный прирост по всем метрикам. Причина этого заключается в том, что его целью является оптимальный выбор и он не ограничен какими-либо предварительными предположениями относительно зависимости порога релевантности от позиции элемента (в терминах Положения 1), в отличие от подходов с отсечкой, в которых предполагается, что для каждого запроса.

Наконец, комбинации подходов OSP + LBO и OSP + PG заметно превосходят подход OSP, подтверждая предположение о преимуществах их компонентов, как описано в разделе 4.3. Среди этих двух комбинированных подходов OSP + PG имеет несколько лучшие характеристики с существенным отличием в отношении p@10 (p-value < 0,05 для однозаходного парного t-теста). Таким образом, вариативность оценки градиента в PG, сокращенная за счет нижней границы вознаграждения, оказывается меньшей проблемой, чем смещение оценки градиента в LBO. Все остальные попарные сравнения алгоритмов в табл. 2 также дают существенный результат10. Качество комбинации OSP + PG в отношении DCG-RR, нормализованное по отношению к Oracle, составило 0,91.

В ходе онлайн-экспериментов лучший предложенный подход OSP + PG сравнивался с наиболее удачным образцовым подходом QueryCutoff и с подходом OSP в качестве подхода на основе машинного обучения без ограничительных допущений модели. Результаты сравнения представлены в табл. 3 и подтверждают все предыдущие заключения. Все попарные сравнения дают существенный результат10, за исключением пары OSP + PG и OSP в случае метрики отказа.

Табл. 2. Характеристики: абсолютные для WeakCutoff и относительные Δ по отношению к WeakCutoff в процентах – для остальных

Подход DCG-RR DCG@10 p@10 stup@12
WeakCutoff 0,52 1,07 0,73 0,06
ConstCutoff
QueryCutoff
OSP
OSP + LBO
OSP + PG
Oracle
0,05%
0,56%
3,86%
4,17%
4,33%
14,44%
2,9%
6,3%
20,3%
22,4%
22,4%
1,6%
4,3%
10,7%
12,0%
12,2%
–11,7%
–17,5%
–33,2%
–37,6%
–36,8%

Табл. 3. Онлайн-характеристики: относительные Δ по отношению к WeakCutoff в процентах

Подход Отказ CTR@12 MRR
QueryCutoff
OSP
OSP + PG
–1,4%
–4,5%
–5,1%
8,7%
19,7%
24,8%
5,7%
24,6%
36,3%

Анализ признаков. Анализ признаков содержится в разделе 3 дополнительных материалов. В частности, анализ показывает, что новые признаки, сформированные специально для решения проблемы LSO, заметно улучшают качество в подходе OSP + PG. Это подтверждает предположение при формировании признаков, описанное в разделе 5.

7. Заключение

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

Ссылки

Baxter, J. and Bartlett, P. L. Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research, 15:319-350, 2001.

Burges, C. J. From ranknet to lambdarank to lambdamart: An overview. Technical report, June 2010.

Carmel, D., Cohen, D., Fagin, R., Farchi, E., Herscovici, M., Maarek, Y. S., and Soffer, A. Static index pruning for information retrieval systems. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, pp. 43-50. ACM, 2001.

Chapelle, O. and Chang, Y. Yahoo! learning to rank challenge overview. In Yahoo! Learning to Rank Challenge, pp. 1-24, 2011.

Chapelle, O. and Wu, M. Gradient descent optimization of smoothed information retrieval metrics. Information retrieval, 13(3):216-235, 2010.

Chapelle, O., Metlzer, D., Zhang, Y., and Grinspan, P. Expected reciprocal rank for graded relevance. In Proceedings of the 18th ACM conference on Information and knowledge management, pp. 621-630. ACM, 2009.

Chapelle, O., Manavoglu, E., and Rosales, R. Simple and scalable response prediction for display advertising. ACM Transactions on Intelligent Systems and Technology (TIST), 5(4):61, 2015.

Chen, T. and Guestrin, C. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 785-794. ACM, 2016.

Craswell, N. Mean reciprocal rank. In Encyclopedia of Database Systems, pp. 1703-1703. Springer, 2009.

Friedman, J., Hastie, T., Tibshirani, R., et al. Additive logistic regression: a statistical view of boosting (with discussion and a rejoinder by the authors). The annals of statistics, 28(2):337-407, 2000.

Glover, E. J., Lawrence, S., Birmingham, W. P., and Giles, C. L. Architecture of a metasearch engine that supports user information needs. In Proceedings of the eighth international conference on Information and knowledge management, pp. 210-216. ACM, 1999.

Glynn, P. W. Likelihood ratio gradient estimation for stochastic systems. Communications of the ACM, 33 (10):75-84, 1990.

Hasanain, M., Elsayed, T., and Magdy, W. Improving tweet timeline generation by predicting optimal retrieval depth. In Asia Information Retrieval Symposium, pp. 135-146. Springer, 2015.

Järvelin, K. and Kekäläinen, J. Cumulated gain-based evaluation of ir techniques. ACM Transactions on Information Systems (TOIS), 20(4):422-446, 2002.

Ji, S., Zhou, K., Liao, C., Zheng, Z., Xue, G.-R., Chapelle, O., Sun, G., and Zha, H. Global ranking by exploiting user clicks. In Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, pp. 35-42. ACM, 2009.

Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., Ye, Q., and Liu, T.-Y. Lightgbm: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems, pp. 3149-3157, 2017.

Kimura, H., Yamamura, M., and Kobayashi, S. Reinforcement learning by stochastic hill climbing on discounted reward. In Machine Learning Proceedings 1995, pp. 295-303. Elsevier, 1995.

Konig, A. C., Gamon, M., and Wu, Q. Click-through prediction for news queries. In Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, pp. 347-354. ACM, 2009.

Liu, T.-Y. et al. Learning to rank for information retrieval. Foundations and Trends R in Information Retrieval, 3(3): 225-331, 2009a.

Liu, T.-Y. et al. Learning to rank for information retrieval. Foundations and Trends in Information Retrieval, 3(3): 225–331, 2009b.

Moffat, A. and Zobel, J. Rank-biased precision for measurement of retrieval effectiveness. ACM Transactions on

Information Systems (TOIS), 27(1):2, 2008.

Patel, M. B. and Shah, D. D. Meta search ranking strategies. International Journal of Information and Computing Technology (RESEARCH@ ICT) ISSN, 976(5999):24-25, 2011.

Prokhorenkova, L., Gusev, G., Vorobev, A., Dorogush, A. V., and Gulin, A. Catboost: unbiased boosting with categorical features. In Advances in Neural Information Processing Systems, pp. 6639-6649, 2018.

Schurman, E. and Brutlag, J. The user and business impact of server delays, additional bytes, and http chunking in web search. In Velocity Web Performance and Operations Conference, 2009.

Spirin, N. V., Kuznetsov, M., Kiseleva, J., Spirin, Y. V., and Izhutov, P. A. Relevance-aware filtering of tuples sorted by an attribute value via direct optimization of search quality metrics. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 979-982. ACM, 2015.

Trofimov, I., Kornetova, A., and Topinskiy, V. Using boosted trees for click-through rate prediction for sponsored search. In Proceedings of the Sixth International Workshop on Data Mining for Online Advertising and Internet Economy, pp. 2. ACM, 2012.

Valizadegan, H., Jin, R., Zhang, R., and Mao, J. Learning to rank by optimizing ndcg measure. In Bengio, Y., Schuurmans, D., Lafferty, J. D., Williams, C. K. I., and Culotta, A. (eds.), Advances in Neural Information Processing Systems 22, pp. 1883-1891. Curran Associates, Inc., 2009. URL http://papers.nips.cc/paper/3758-learning-to-rank-by-optimizing-ndcg-measure.pdf.

Wang, L., Lin, J., and Metzler, D. A cascade ranking model for efficient ranked retrieval. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, pp. 105–114. ACM, 2011.

Wu, M., Chang, Y., Zheng, Z., and Zha, H. Smoothing DCG for learning to rank: A novel approach using smoothed hinge functions. In Proceedings of the 18th ACM conference on Information and knowledge management, pp. 1923–1926. ACM, 2009.

Приложение Б

Дополнительные материалы к публикации

Обучение выбору для заранее заданного ранжирования

Анонимные авторы (Анонимная организация, анонимный город, анонимный регион, анонимная страна. Для корреспонденции: <anon.email@domain.com>.

Предварительный материал. Для рассмотрения оргкомитетом международной конференции по машинному обучению (International Conference on Machine Learning (ICML)). Не для распространения.)

1. Анализ алгоритма оптимального выбора

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

Требование R1. Для любых списков и элементов выполняется условие

где «⌢» означает конкатенацию. Иными словами, перестановка двух соседних элементов в списке приводит к изменению их релевантности в соответствии с порядком релевантности этих элементов.

Требование R2. Если выполняется условие для списков и алгоритма выбора , то выполняется условие для любого алгоритма выбора. Иными словами, чем меньшее количество элементов расположено выше оставшейся части списка, тем более полезным оказывается применение алгоритма выбора к этой оставшейся части. В наиболее практичном случае аддитивной меры это эквивалентно нестрогой логарифмической выпуклости как функции позиции , т.е. и относится к случаям DCG и RBP с и , соответственно.

При выполнении этих требований верно следующее положение:

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

Доказательство 1. Очевидно, что для фиксированной позиции оптимальное решение относительно элемента имеет пороговую зависимость от его релевантности , т.е. для некоторой функции . Предположим, эта зависимость - невозрастающая. Тогда существуют такие списки , такие элементы с релевантностью и такой список , что оптимальный выбор для списка обеспечивает список , где элемент остается невыбранным, а означает список после выбора. Предположим без потери общности, что является нижним элементом в списке , расположенным выше элемента в списке , и его релевантность . Тогда для каждого элемента его релевантность удовлетворяет условию . Это позволяет применить свойство R1 к элементу и к каждому элементу последовательно сверху донизу и получить

Далее:

где первое неравенство является следствием возрастания монотонности функции в отношении релевантности каждого элемента, а второе неравенство следует из неравенства

и применения свойства R2 к ,, , . Сочетание неравенств (1) и (2) дает

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

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

Рис. 1. Страницы с результатами для запроса «глобальное потепление» (global warming), направленного сайту www.ebay.com при упорядочении результатов по релевантности (вверху) и по цене (внизу).

2. Доказательство теоремы 1

Доказательство 2. 1) В случае логарифмически выпуклой рассмотрим следующий пример:

Определим списки-кандидаты на лучший выбор:

Легко убедиться, что

Заметим, что функции и являются монотонными функциями для каждой модели предсказания . Действительно, знак обеих производных (см. уравнение 6 в основном тексте) и (см. уравнение 5 в основном тексте) не зависит от , что является существенным условием монотонности. Для второй из этих двух производных это легко показать, представив эту производную в следующем виде:

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

В случае логарифмически вогнутой , по аналогии с первым случаем, может быть рассмотрен следующий пример:

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

3. Признаки и их важность

При экспериментах были использованы все признаки (во всех методиках, включая образцовые), применяемые при рабочем ранжировании в исследуемом поисковом движке, помимо дополнительных признаков, описанных в разделе 5.1. Эти признаки включают в себя ценовые признаки (цена предложения, агрегированная цена по различным категориям, к которым относится предлагаемый товар), признаки пар запрос-предложение (например, текстовые признаки, указывающие на релевантность предложения запросу, статистика «кликов») и признаки предложения (например, признаки, описывающие предлагаемый товар, магазин, доставку, оплату).

Табл. 1. Важность признаков

Группа признаков OFP + PG Предсказание релевантности
AvPricePred
AvRelPred
Price
Query
QueryOffer+Offer
12,0
3,5
31,6
19,0
34,5
1,0
2,8
3,3
20,7
71,4

Для анализа важности в проблеме LSO различных групп признаков, описанных в разделе 5 основного текста, и для сравнения с их важностью для предсказания рабочей релевантности значения важности признаков суммировались по всем признакам в каждой группе. Важность признака определялась как сумма снижения в функциях потерь по всем частям на основе данного признака (Diaz et al. [1]). Результирующая статистика для OFP + PG и для предсказания рабочей релевантности представлена в табл. 1. Как и следовало ожидать, ценовые признаки (и рабочие, и AvPricePred) оказались существенно более важными для проблемы LSO. Кроме того, признаки запроса также оставались важными для проблемы LSO, поскольку они содержат сигнал о релевантности и распределении цены по предложениям для этого запроса.

Табл. 2. Влияние на показатель DCG-RR, Δ по отношению к WeakCutoff, %

Признаки (для OFP + PG) DCG-RR
AvPricePred + AvRelPred
AvPricePred
AvRelPred
4,33
3,27
3,25
2,55

Дополнительно для OFP + PG оценивалось влияние на показатель DCG-RR признаков AvPricePred и AvRelPred, сформированных специально для проблемы LSO. Относительные изменения качества для WeakCutoff представлены в табл. 2. Эти признаки заметно увеличивали качество выбора и подтвердили предположения о важности признаков, кодирующих распределение особого атрибута и релевантности в исходном списке элементов.

4. Параметры CatBoost

Для обучения каждой модели использовались следующие настройки параметров CatBoost:

depth = 6;

leaf_estimation_iterations = 100;

border_count = 32;

random_strength = 0

bagging_temperature = 0;

iterations = 1000,

loss_function = UserQuerywiseMetric.

Лучшая итерация (ограниченная сверху 1000) и параметр learning_rate были подобраны в сочетании с особыми гиперпараметрами алгоритмов путем максимизации показателя DCG-RR, остальные параметры CatBoost имели значения по умолчанию. Все признаки обрабатывались как численные.

5. Метки релевантности

Рабочая релевантность элемента представляет собой оценку, используемую выбранной системой для ранжирования без упорядочения по цене. Она рассчитывается как сочетание предсказанной релевантности и составляющей на основе «кликов», полученной путем машинного обучения и нормализованной в интервале [0,1]. Первая причина такого сочетания основана на хорошо известном факте, что «клики» обеспечивают сильный сигнал о релевантности элемента [3], что побуждает комбинировать метки релевантности с «кликами» в качестве целей в проблеме LTR [5]. Вторая причина заключается в том, что количество «кликов» непосредственно влияет на доход системы при схеме оплаты Cost Per Mille (CPM) [2]. В этой схеме магазин платит системе фиксированную цену за каждую тысячу показов его предложения, а показ возникает при «клике» пользователя на соответствующем элементе (фрагменте (snippet) с предложением) на странице с результатами.

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

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

Табл. 3. Описательная статистика для алгоритмов выбора

Подход Количество
сложных
элементов
на список, Nhard
Количество
исключенных
элементов
на список
Порог
(, или )
ConstCutoff
QueryCutoff
OFP
LBO
PG
OFP+LBO
OFP + PG
Oracle


16,9
62,6
58,9
6,1
10,6
0
3,4
41,3
68,4
0
0,2
73,1
73,1
78,9
0,058
[0,03, 0,67]
0,547
0,033
0,703
0,552
0,561

Табл. 4. Характеристики: абсолютные для WeakCutoff и
относительные Δ по отношению к WeakCutoff в процентах – для остальных

Подход DCG-RR DCG@5 DCG@10 p@10 stup@12
WeakCutoff 0,52 0,69 1,07 0,73 0,06
ConstCutoff
QueryCutoff
OFP
OFP + LBO
OFP + PG
Oracle
0,05
0,56
3,86
4,17
4,33
14,44
2,91
6,6
23,8
25,95
26,04
2,94
6,26
20,3
22,35
22,35
1,55
4,29
10,71
11,95
12,23
–11,66
–17,49
–33,17
–37,61
–36,78

Табл. 5. Пример неоптимальности подхода с отсечкой

Исходный список Лучший вариант
с отсечкой
Лучший выбор
Список d1, d2, d3 d2 d2, d3
Значения атрибутов 1, 2, 3 2 2, 3
Значения релевантности 2, 7, 1 7 7, 1
Показатель DCG@5 списка 6,92 7 7,63

Ссылки

[1] F. Diaz, D. Metzler, and S. Amer-Yahia. Relevance and ranking in online dating systems. In Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval, pages 66–73. ACM, 2010.

[2] D. C. Fain and J. O. Pedersen. Sponsored search: A brief history. Bulletin of the Association for Information Science and Technology, 32(2):12-13, 2006.

[3] T. Joachims, L. Granka, B. Pan, H. Hembrooke, and G. Gay. Accurately interpreting clickthrough data as implicit feedback. In ACM SIGIR Forum, volume 51, pages 4-11. Acm, 2017.

[4] C. Martınez. Partial quicksort. In Proc. 6th ACMSIAM Workshop on Algorithm Engineering and Experiments and 1st ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics, pages 224-228, 2004.

[5] K. M. Svore, M. N. Volkovs, and C. J. Burges. Learning to rank with multiple objective functions. In Proceedings of the 20th international conference on World wide web, pages 367-376. ACM, 2011.

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

- выбор на основе запроса из пула цифровых объектов набора цифровых объектов, который релевантен запросу с учетом целевой характеристики цифровых объектов и может быть ранжирован согласно их целевой характеристике;

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

- выбор цифровых объектов, подлежащих включению в переранжированный набор цифровых объектов, путем:

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

- выбора цифровых объектов на основе соответствующих параметров объектов; и

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

2. Способ по п. 1, отличающийся тем, что целевая характеристика указывает на релевантность цифрового объекта запросу.

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

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

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

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

7. Способ по п. 6, отличающийся тем, что собственный параметр не указывает непосредственно на релевантность цифрового объекта запросу.

8. Способ по п. 1, отличающийся тем, что параметр объекта определяется алгоритмом машинного обучения (MLA).

9. Способ по п. 8, отличающийся тем, что он дополнительно включает в себя обучение алгоритма MLA.

10. Способ по п. 9, отличающийся тем, что обучение алгоритма MLA включает в себя подачу в алгоритм MLA набора обучающих цифровых объектов, при этом каждый элемент в обучающем наборе цифровых объектов содержит: (а) обучающий цифровой объект из обучающего набора цифровых объектов; (б) обучающий запрос, использованный для формирования обучающего набора цифровых объектов; (в) указание на дополнительную характеристику обучающего цифрового объекта; и (г) формируемую оценщиком метку, указывающую на обязательность включения обучающего цифрового объекта в поднабор обучающих цифровых объектов с учетом дополнительной характеристики и релевантности обучающего цифрового объекта обучающему запросу.

11. Способ по п. 8, отличающийся тем, что алгоритм MLA представляет собой алгоритм MLA на основе дерева решений с градиентным бустингом.

12. Способ по п. 1, отличающийся тем, что переранжированный набор цифровых объектов содержит меньше цифровых объектов, чем набор цифровых объектов.

13. Способ по п. 1, отличающийся тем, что параметр объекта основан на компромиссе между количеством цифровых объектов, подлежащих включению в переранжированный набор цифровых объектов, и релевантностью цифровых объектов, включенных в переранжированный набор цифровых объектов.

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

15. Способ по п. 14, отличающийся тем, что поднабор позиций с более высоким рангом соответствует первым N позициям переранжированного набора цифровых объектов.

16. Способ по п. 1, отличающийся тем, что метрика качества основана на релевантности переранжированного набора цифровых объектов запросу с учетом целевой характеристики.

17. Способ по п. 1, отличающийся тем, что метрика качества основана на предсказанном значении дополнительной характеристики первых N цифровых объектов из переранжированного набора цифровых объектов.

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

- получения от электронного устройства запроса на ранжирование цифровых объектов;

- выбора на основе запроса из пула цифровых объектов набора цифровых объектов, который релевантен запросу с учетом целевой характеристики цифровых объектов и может быть ранжирован согласно их целевой характеристике;

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

- выбора цифровых объектов, подлежащих включению в переранжированный набор цифровых объектов, путем:

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

- выбора цифровых объектов на основе соответствующих параметров объектов; и

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

19. Система по п. 18, отличающаяся тем, что аппаратный сервер дополнительно выполнен с возможностью определения параметра объекта с использованием алгоритма MLA.

20. Система по п. 18, отличающаяся тем, что аппаратный сервер дополнительно выполнен с возможностью обучения алгоритма MLA путем подачи в алгоритм MLA набора обучающих цифровых объектов, при этом каждый элемент в обучающем наборе цифровых объектов содержит: (а) обучающий цифровой объект из обучающего набора цифровых объектов; (б) обучающий запрос, использованный для формирования обучающего набора цифровых объектов; (в) указание на дополнительную характеристику обучающего цифрового объекта; и (г) формируемую оценщиком метку, указывающую на обязательность включения обучающего цифрового объекта в поднабор обучающих цифровых объектов с учетом дополнительной характеристики и релевантности обучающего цифрового объекта обучающему запросу.



 

Похожие патенты:

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

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

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

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

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

Группа изобретений относится к технологии Интернета вещей (IoT). Технический результат заключается в повышении безопасности устройств в IoT-окружении.

Изобретение относится к вычислительной технике. Технический результат заключается в повышении эффективности защиты номеров банковских карт.

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

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

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

Изобретение относится к области вычислительной техники для обеспечения информационной безопасности. Технический результат изобретения заключается в повышении точности определения степени вредоносности приложения. Технический результат достигается за счет: а) формирования для заданного приложения его исходного кода; б) формирования промежуточного кода на основании сформированного исходного кода; в) осуществления выборки характеристик по меньшей мере одного приложения из базы приложений на основании сформированного промежуточного кода; г) определения степени вредоносности заданного приложения на основании выбранных характеристик приложения. 2 н. и 16 з.п. ф-лы, 3 ил.
Наверх