KR-102962733-B1 - SYSTEM AND METHOD FOR RANKING OBJECTS

KR102962733B1KR 102962733 B1KR102962733 B1KR 102962733B1KR-102962733-B1

Abstract

A computer implementation method for ranking a set of objects comprises: receiving a set of objects and a set of objective functions; defining a decision space using a permutohedron having n decision variables, where n is the number of objects to be ranked and the vertex coordinates of the permutohedron represent exposures associated with corresponding ranks; determining a Pareto set for the set of objective functions; determining a distribution of ranks for objects within the set using the decision space, with the Pareto optimal point within the Pareto set; selecting a sequence of ranks for the set of objects from the distribution of ranks according to ratios; and outputting the selected sequence of ranks.

Inventors

틸 클레티
장-미셸 렌더스

Assignees

네이버 주식회사

Dates

Publication Date: 20260511
Application Date: 20220426
Priority Date: 20211108

Claims (20)

As a computer implementation method for ranking a set of objects, A step of receiving a set of the above objects and a set of goal functions; A step of defining a decision space having n decision variables using a permutohedron, where n is the number of objects to be ranked, and the vertices of the permutohedron represent permutations of exposures provided to the objects in the set by corresponding ranks -; A step of determining a Pareto set for the set of the above objective functions; A step of determining a distribution of ranks for the objects within the set using the decision space, with the Pareto optimal point within the Pareto set—each rank within the distribution having a ratio—; A step of selecting a sequence of ranks for the objects in the set from a distribution for the ranks according to the ratios; and A computer-implemented method comprising the step of outputting a sequence of the selected ranks.
A computer-implemented method according to claim 1, wherein the set of objective functions includes quadratic functions and linear functions.
A computer-implemented method according to paragraph 2, wherein the quadratic function includes a fairness function and the linear function includes a utility function.
A computer-implemented method according to claim 1, wherein the set of objective functions includes a fairness function and a utility function.
A computer implementation method according to paragraph 4, wherein the fairness function is a normalized function of the difference between a vector composed of the decision variables and a target vector.
In paragraph 4, the above fairness function is a computer implementation method in which the fairness function is a normalized function.
A computer implementation method according to claim 6, wherein the normalized function is a squared L2-norm function.
A computer-implemented method according to claim 1, further comprising the step of receiving a relevance score for each object in the set, a list of exposures provided to the objects in the set, each associated with a rank, a ranking fairness objective function, and a ranking utility objective function.
A computer-implemented method according to claim 8, wherein the step of determining the Pareto set for the set of the objective functions comprises the step of calculating the Pareto set within the determination space by considering the ranking fairness objective function and the ranking utility objective function.
In claim 9, the step of determining the distribution of the ranks for the objects within the set using the determination space is: A step of receiving a specific point in the Pareto set that is converted into a target exposure across the objects in the set within the above decision space; and A computer-implemented method comprising the step of determining a distribution of ranks that achieve an average of all ranks for the target exposures for the objects in the set using the target exposures, wherein the ranks in the distribution of ranks correspond to vertices in the determination space.
In paragraph 10, the step of determining the distribution of the ranks for the objects within the set using the above-mentioned decision space is, with respect to the number of the objects within the set: (i) a step of determining an arbitrary vertex of the above-mentioned decision space; (ii) drawing the line starting from the arbitrary vertex through the target exposure until the line intersects the plane of the decision space; and (iii) further comprising the step of repeating (i) and (ii) on the intersecting plane of the determination space using the intersection point of the line and the plane of the determination space instead of the target exposure until the intersecting plane becomes a vertex, A computer implementation method in which each vertex of the above decision space has an associated ratio in the distribution for the above ranks.
In claim 1, the permutohedron comprises an expohedron representing the decision space in which each decision takes the form of a ranking policy ( π (q)) in which each decision is a distribution over m ranks, wherein m≤n σ i ( i 1 , …, m ) and: π ( q ) = is, A computer implementation method in which each rank (σ i ) maps each object ( d j ) to rank ( σ i ( d j )), and α i is the ratio of rank (σ i ) to π(q).
In paragraph 1, the set of objective functions includes a fairness function and a utility function, and The above fairness function is a computer implementation method based on meritocratic fairness.
In paragraph 1, the set of objective functions includes a fairness function and a utility function, and The above fairness function is a computer implementation method based on demographic fairness.
In claim 1, the step of determining the distribution of ranks for the objects within the set using the determination space is a computer-implemented method using a GLS (Grotschel, Lovasz and Schrijver) procedure.
A computer-implemented method according to claim 1, wherein the step of selecting a sequence of ranks for the objects within the set comprises one or more of stochastic sampling, low-discrepancy sequences, additive-recurrence sequences, stride scheduling, or m -balancing.
A computer-implemented method according to claim 1, wherein the objects within the set include a plurality of queries.
A computer-implemented method according to claim 1, wherein the objects within the set include a plurality of documents.
A computer-implemented method according to claim 1, wherein the objects within the set are identified in response to a query.
A computer implementation method according to claim 1, wherein the objects within the set include a plurality of recommendations.

Description

System and Method for Ranking Objects Reference to priority claims and related applications This application claims priority under 35 USC 119 from French patent application No. FR 2104801 filed on May 6, 2021, the contents of which are incorporated herein by reference. This application further claims priority under 35 USC 119 from European patent application no. EP21306565 filed on November 8, 2021, the contents of which are incorporated herein by reference. Technology field The field of the present invention is information retrieval and recommendation. More specifically, embodiments of the present invention relate to computer-implemented methods and systems for fair ranking of objects to be retrieved. Generally, information retrieval and recommendation consist of two stages. The first stage focuses on searching for a set of candidate results, and the second stage focuses on ranking the set of candidate results. The candidate set of results may include search results (e.g., lists of links to documents from search results that responded to the query) and recommendations (e.g., lists of interest point recommendations that responded to the identified location, or lists of song recommendations that responded to the genre selection, etc.). For example, for information retrieval, a query may be entered into a first-stage searcher, which processes the query (e.g., based on relevance) and retrieves a set of documents accordingly. Subsequently, a second stage or ranker (or reranker) ranks the set of retrieved documents and outputs a set of ranked documents, the number of which may be, for example, equal to or less than that of the first set. Users (e.g., content consumers) expect the most relevant results to be exposed the most, whereas providers (e.g., content producers) seek fair (or equitable) exposure for their content. Therefore, when ranking a set of candidate results in the second stage, it is desirable for the ranking method to maintain a balance between utility (representing users accessing the set of results) and fairness (representing providers comprising the set of results). While there are some ranking methods that maintain a balance between utility and fairness, the complexity of these methods generally prohibits their use in realistic scenarios. Therefore, there is a continuing need for optimal methods that are less complex than existing methods (e.g., capable of calculating accurate optimal solutions) to enable, for example, web-scale fairness-utility ranking. Exemplary methods of the present invention provide a computer-implemented method for ranking a set of objects according to a first aspect, and the method is, A step of receiving a set of objects and a set of goal functions; A step of defining a decision space with n decision variables using a permutohedron—where n is the number of objects to be ranked, and the vertices of the permutohedron represent permutations of exposures provided to objects in the set by corresponding ranks—; Step of determining the Pareto set for the set of objective functions; A step of determining the distribution of ranks for objects within the set using a decision space, with the Pareto optimal point within the Pareto set—wherein each rank and proportion within the said distribution is associated—; A step of selecting a sequence of ranks for objects in a set from a distribution of ranks according to ratios; and It includes a step of outputting a sequence of selected ranks. Preferred but non-limiting modes of the method according to the first mode are as follows: - The set of objective functions may include quadratic and linear functions; - A quadratic function can be a fairness function, and a linear function can be a utility function; - The fairness function can be a normalized difference, such as the L2-norm, which is the square of the difference between a vector of decision variables and a target vector; - The method may further include the step of receiving a relevance score for each object in the set, a list of exposures provided to the objects in the set, each associated with a rank, a ranking fairness objective function, and a ranking utility objective function; - The step of determining a Pareto set for a set of objective functions may include the step of calculating a Pareto set in a decision space by considering a ranking fairness objective function and a ranking utility objective function, and the step of determining a distribution of ranks for objects in a set using the decision space may include the step of receiving specific points in the Pareto set that are converted into target exposures across objects in the set in the decision space, and the step of determining a distribution of ranks that achieve target exposures for objects in the set on average using the target exposures, wherein each rank of the distribution of ranks corresponds to a peak in the decision space; - The step of determining the distribution of ranks for objects within a set using the