Bipartite Ranking From Multiple Labels: On Loss Versus Label Aggregation

Thank you for your positive feedback and insightful questions. We clarify below:

1. Regarding Interpretation of Prop 6.1 / Loss Aggregation Weighting & Practical Example:

Re: Prop 6.1 & loss weighting. Why problematic if $\pi^{(k)}\approx 0.5$? Isn't less weight on noisy labels reasonable? Clarify problematic nature & provide practical example where dictatorship undesirable.

We clarify that $\pi^{(k)}$ represents the overall balance or prevalence of label $k$ across the dataset, not the conditional uncertainty or noise $P(Y^{(k)}=1|x)$ for a specific instance $x$. A label can be perfectly balanced ($\pi^{(k)}=0.5$) while being conditionally deterministic (zero noise). For example, with instances $x_1, x_2$ where $\eta^{(1)}(x_1)=1, \eta^{(1)}(x_2)=0$, we have $\pi^{(1)}=0.5$ (balanced marginal) but zero conditional label noise.

Therefore, the loss aggregation weighting $1/[\pi^{(k)}(1-\pi^{(k)})]$ favors marginal imbalance (skewness), not necessarily conditional signal quality. Our concern is that this skew-based weighting may conflict with practical goals.

Illustrative Example: IR Example: Assume Y(1)='relevance' is balanced ($\pi^{(1)} \approx 0.5$) and Y(2)='is recent' is highly skewed ($\pi^{(2)} \approx 0$). Even if both relevance and recency signals are perfectly clean (conditionally deterministic, $\eta^{(k)}(x) \in \{0,1\}$), loss aggregation with uniform $a_k=1$ yields $\alpha^{(2)} \gg \alpha^{(1)}$, making 'is recent' dominate the ranking (Prop 6.1). If the user cares primarily about relevance, but the system heavily prioritizes recency regardless of relevance due to skew, this "dictatorship" is undesirable. The system optimizes for marginal imbalance, ignoring the balanced relevance signal.

This issue persists even with non-deterministic labels (Prop 5.2), where the optimal scorer remains sensitive to the marginal priors $\pi^{(k)}$. Our experiments (Section 7) on data with varying skewness provide empirical support.

Action: We will revise Section 5.1 and Section 6.1 to clearly distinguish marginal imbalance ($\pi^{(k)}$) from conditional label distributions ($\eta^{(k)}(x)$). We will incorporate an illustrative example and refine the IR explanation to clarify why favoring labels based on marginal skew $\pi^{(k)}$ can be practically undesirable.

2. Regarding Understanding Label Aggregation by Summation (Prop 5.3/5.4):

Re: Prop 5.3/5.4. Difficulty understanding label summation $\sum_k Y^{(k)}$. Are $Y^{(k)}$ binary? The sum is not {0,1}. How does this compare to multi-class label addition (e.g., "cat" + "dog")?

Thank you for requesting clarification.

• Setup: As introduced in Section 3.1, our setting involves $K$ distinct binary labels $Y^{(1)}, \ldots, Y^{(K)}$ for input $x$, where $Y^{(k)} \in \{0, 1\}$. These represent different facets or signals (e.g., clicks vs. ratings mentioned in Sec 1, 3.3). We aim to learn a single scorer $f : \mathcal{X} \rightarrow \mathbb{R}$.
• Summation: In Section 4.2 (specifically for Prop 5.3 and 5.4), we use the aggregation $\psi(Y^{(1)}, \ldots, Y^{(K)}) = \sum_{k=1}^K Y^{(k)}$. Since each $Y^{(k)}$ is binary, the sum $\bar{Y}$ is an integer in $\{0, 1, \ldots, K\}$, representing the count of positive labels.
• Resulting Label: You are correct, this sum $\bar{Y}$ is generally not binary (it is ordinal).
• Handling the Sum: This is handled by treating the task as multipartite ranking with respect to this ordinal label $\bar{Y}$. We optimize the multipartite AUC defined in Definition 2.3 / Eq. 5 using $\bar{Y}$.
• Role of Costs (Crucial): Prop 5.4's key insight relies on using specific costs $c_{\overline{y}\overline{y}^{\prime}} = \mathbf{1}(\overline{y} > \overline{y}^{\prime}) \cdot |\overline{y} - \overline{y}^{\prime}|$ within the multipartite AUC objective (Eq. 5). Under this specific cost structure, the Bayes-optimal scorer simplifies remarkably to $f^*(x) \propto \sum_{k=1}^K \eta^{(k)}(x)$ (Eq. 7). As shown in the proof, this occurs because $E[\bar{Y} | X=x] = \sum_k E[Y^{(k)}|X=x] = \sum_k \eta^{(k)}(x)$, and these specific costs make $E[\bar{Y}|X=x]$ the optimal scorer (per Uematsu & Lee, 2015). This simplification does not generally hold for other costs (like $c_{\overline{y}\overline{y}^{\prime}} = 1$ used for Prop 5.3).
• Distinction from Multi-Class: This is fundamentally different from having mutually exclusive multi-class labels (like "cat", "dog"). We are summing binary indicators related to the same instance, not arithmetically combining distinct semantic categories.

Action: We will add text clarifying that $Y^{(k)}$ are binary, $\bar{Y}=\sum_k Y^{(k)}$ serves as an intermediate ordinal target for multipartite ranking, and emphasize the critical role of the specific cost function $c_{\overline{y}\overline{y}^{\prime}} = |\overline{y} - \overline{y}^{\prime}|$ in deriving the clean result of Prop 5.4.

Please let us know if any further clarification is needed.

Thank you for your positive feedback and insightful questions. We address the specific points you raised below.

1. Regarding Theory Guiding Design:

"...nor does it explain how the theoretical results guide the design of the method." "How can the theoretical results guide the design of the method?"

Thank you for this important question on the practical implications of our theory. As opposed to informing methods from theory, we follow a different structure in our paper, where we start with an established goal of Pareto-optimality, describe two methods for achieving that goal (i.e., label aggregation and linear scalarization), and using the Bayes optimality framework analyze whether they achieve it. Indeed the theoretical results do not serve a purpose of constructing methods, but rather, they allow us to analyze the proposed methods.

That being said, our analysis does lead to practical conclusions. First, we introduce a novel criterion eluding Pareto optimality, the “dictatorial issue”, which a practitioner may want to keep in mind. Second, as demonstrated with our experiments on both synthetic and real world experiments, one should be careful when choosing linear scalarization, as it suffers from the dictatorial issue, contrary to label aggregation techniques.

2. Regarding Application Scenarios:

"The paper does not provide a detailed discussion of the application scenarios of the method..."

We appreciate this point and agree that a more elaborate discussion of application scenarios would strengthen the paper. The applications of multi-objective learning to rank are widespread. We briefly mentioned potential areas like information retrieval and medical diagnosis in the Introduction and used a motivating example from information retrieval (relevance vs. engagement trade-off) in Section 3.3. To further elaborate, in the revised manuscript, we will add a dedicated subsection to discuss potential real-world applications in greater detail. This will include more concrete examples, such as:

• Multi-faceted Information Retrieval: Ranking documents based on relevance to different query interpretations or aspects (e.g., topicality, freshness, geographical relevance). [R1]
• Recommendation Systems: Recommending items (e.g., products, movies, news articles) by balancing multiple objectives like predicted user click/purchase probability, relevance to long-term interests, promotion of diversity, or fairness considerations across item groups. [R2]
• Computational Advertising: Ranking ads based on predicted click-through rate and predicted conversion rate. [R3]

For each scenario, we will briefly discuss why synthesizing multiple labels is necessary and how the choice between loss aggregation and label aggregation (informed by our analysis of Pareto optimality and the "dictatorship" issue) might impact the final ranking outcome. We believe this expanded discussion will better illustrate the practical relevance and potential impact of our work.

[R1] Perkio, Jukka, et al. "Multi-faceted information retrieval system for large scale email archives." The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI'05). IEEE, 2005.

[R2] Zheng, Yong, and David Xuejun Wang. "A survey of recommender systems with multi-objective optimization." Neurocomputing 474 (2022): 141-153.

[R3] Wang, Xuewei, et al. "Towards the Better Ranking Consistency: A Multi-task Learning Framework for Early Stage Ads Ranking." AdKDD (2023).

Thank you for your positive feedback and insightful questions. We address the specific points you raised below.

1. Anti-correlated Labels:

"test label aggregation … with ‌anti-correlated labels‌"

Thank you for this insightful question. We show below that the optimal scorer does depend on the correlation between the labels; for the special case of anti-correlated labels, we get no useful signals, resulting in a constant scorer.

Specifically, Proposition 5.4 shows the optimal scorer for label aggregation (cost $c_{\overline{y}\overline{y}^{\prime}} = |\overline{y} - \overline{y}^{\prime}|$) ranks by $f^*(x) \propto \sum_k \eta^{(k)}(x)$. For $K=2$, this is equivalent to ranking by $\delta(x) = p(Y_1=1, Y_2=1 | x) - p(Y_1=0, Y_2=0 | x)$. The derivation below shows $f^*(x) \propto \delta(x)$.

(Derivation: From Prop 5.4, the scorer is $\eta_1(x)+\eta_2(x)$. We have $\eta_1(x) = p(Y_1=1, Y_2=0 | x) + p(Y_1=1, Y_2=1 | x)$ and $\eta_2(x) = p(Y_1=0, Y_2=1 | x) + p(Y_1=1, Y_2=1 | x)$. Summing them gives $\eta_1(x) + \eta_2(x) = p(Y_1=1, Y_2=0 | x) + p(Y_1=0, Y_2=1 | x) + 2 p(Y_1=1, Y_2=1 | x)$. Since $p(Y_1=1, Y_2=0 | x) + p(Y_1=0, Y_2=1 | x) + p(Y_1=1, Y_2=1 | x) + p(Y_1=0, Y_2=0 | x) = 1$, the sum simplifies to $1 - p(Y_1=0, Y_2=0 | x) + p(Y_1=1, Y_2=1 | x) = 1 + \delta(x)$.)

Thus the optimal scorer depends on label correlations via $\delta(x)$. Let's consider the implications:

• Overlapping ($Y_1=Y_2$): $\delta(x) \propto \eta_1(x)$, so the ranking uses $\eta_1(x)$, which is sensible.
• Anti-correlated ($Y_1 = 1-Y_2$): $\delta(x) = 0$. The scorer $f^*(x)$ is constant, yielding no ranking. This is unsurprising as the aggregated label $Y_1+Y_2=1$ is constant, making the AUC objective ill-defined.
• Mild anti-correlation: Here, both $p(Y_1=1, Y_2=1 | x)$ and $p(Y_1=0, Y_2=0 | x)$ would be small, and the ranking depends on their difference via $\delta(x)$. For example, when $\delta(x) > 0$, it is more likely that both labels are 1 than 0, resulting in $x$ being ranked higher.

2. Sensitivity of Label Aggregation to Weights:

"How‌ sensitive are the results to … ‌mixing weights‌ in label aggregation?"

This is a great question! Below, we generalize label aggregation with non-uniform weights $\alpha_1, \alpha_2 > 0$, i.e., $\bar{Y} = \alpha_1 \cdot Y_1 + \alpha_2 \cdot Y_2$, again for the $K=2$ case for simplicity.

From Proposition 5.4, the Bayes-optimal scorer $\bar{\eta}(x) = E[\bar{Y}|X=x]$ becomes: $\bar{\eta}(x) = 0 \cdot p(Y_1=0, Y_2=0 | x) + \alpha_1 \cdot p(Y_1=1, Y_2=0 | x) + \alpha_2 \cdot p(Y_1=0, Y_2=1 | x) + (\alpha_1+\alpha_2) \cdot p(Y_1=1, Y_2=1 | x)$ $= \alpha_1 \cdot [ p(Y_1=1, Y_2=0 | x) + p(Y_1=1, Y_2=1 | x) ] + \alpha_2 \cdot [ p(Y_1=0, Y_2=1 | x) + p(Y_1=1, Y_2=1 | x) ] = \alpha_1 \eta_1(x) + \alpha_2 \eta_2(x)$

This shows that the optimal scorer is a direct linear combination of the class-probability functions $\eta_k(x)$, weighted by the explicitly chosen aggregation weights $\alpha_k$.

This contrasts sharply with the optimal scorer for loss aggregation (Proposition 5.2), which is $\sum_k \frac{a_k}{\pi^{(k)}(1-\pi^{(k)})} \eta^{(k)}(x)$. Here, the effective weight on $\eta^{(k)}(x)$ depends not only on the chosen weight $a_k$ but also implicitly on the label prior $\pi^{(k)}$.

Therefore, regarding sensitivity:

• The label aggregation optimal scorer is sensitive to the choice of weights $\alpha_k$ in a direct and predictable way: the final scorer is exactly the $\alpha_k$-weighted sum of the $\eta_k(x)$. It is notably insensitive to the class priors $\pi^{(k)}$.
• The loss aggregation optimal scorer is sensitive to both the chosen weights $a_k$ and the class priors $\pi^{(k)}$ through the $\pi^{(k)}(1-\pi^{(k)})$ term.

3. Deterministic Label Assumption:

"Theorem 1‌ assumes deterministic labels .However, most labels in real-world are noisy."

Thank you for pointing this out. We searched our manuscript but could not find "Theorem 1". We kindly ask for clarification on which result is being referred to.

Assuming the concern relates to our use of deterministic labels in Section 6 (where $\eta^{(k)}(x) \in \{0, 1\}$): this was purely for illustrative purposes, to provide a clear and simple setting to demonstrate the "label dictatorship" phenomenon associated with loss aggregation (Proposition 6.1, Figure 1).

Our main theoretical results on Bayes-optimal scorers in Prop 5.2 (Loss Agg.) and Prop 5.4 (Label Agg.) do not require deterministic labels: they hold for general $\eta^{(k)}(x)$.

Furthermore, our Section 7 experiments use both synthetic dataset (generated from a non-deterministic distribution) and real-world datasets (Banking, MSLR), confirming relevance in non-deterministic settings.