PaperlayerView exact revision on arXiv

Source-linked AI summary

MORE-PLR: multi-output regression employed for partial label ranking

Santo M. A. R. Thies, Juan C. Alfaro, Viktor Bengs

arXiv:2609.29386v1cs.LG

TL;DR

Partial label ranking must represent ties, which total-order approaches exclude. MORE-PLR uses multi-output regression to predict bucket orders and, with suitable component combinations, outperforms state-of-the-art methods in less time.

  • Problem

    Existing label-ranking approaches require total orders, excluding cases where multiple labels share a ranking position.

    Source: §1 · p. 2

  • Method

    MORE-PLR encodes bucket orders as multivariate regression targets and adds post-hoc layers to convert regression predictions into bucket orders.

    Source: §1 · p. 3

  • Results

    With the right combination of components, MORE-PLR can outperform state-of-the-art partial label ranking methods, achieving better results in less time.

    Source: §6 · p. 17

  • Takeaways & Limitations

    MORE-PLR typically has linear runtime dependence on the number of labels, compared with quadratic runtime for the state-of-the-art pairwise comparison method.

    Source: §1 · p. 3

    The prediction-interval layer can yield an order containing essentially one bucket, and not all methods inherently provide prediction intervals.

    Source: Prediction interval (PI) Layer · p. 10

Abstract

from arXiv · show

The partial label ranking problem is a supervised learning scenario that aims to fit a preference model that predicts a bucket order defined over a set of labels for a given input instance. This problem generalizes the well-known label ranking problem, which, in practice, is limited to outputting total orders of labels. Existing partial label ranking methods have primarily extended label ranking approaches to handle ties in predictions. This paper proposes using multi-output regression to address the partial label ranking problem, introducing an encoder that, during the learning phase, transforms the (possibly incomplete) rankings with ties of labels to multivariate regression targets, an underexplored perspective in both label ranking and partial label ranking. Moreover, during the inference phase, we introduce several post-hoc layers that convert the multi-output regression results into the output bucket order to effectively implement this approach. This framework provides learning strategies that are competitive with the current state-of-the-art partial label ranking methods, as demonstrated through experimental evaluations.

1 Introduction

MORE-PLR addresses partial label ranking by encoding bucket orders as multivariate regression targets and using post-hoc layers to convert predictions back into bucket orders. It extends total-order ranking to settings that allow ties and incomplete rankings.

1 Introduction

  • Unlike total-order label ranking, partial label ranking allows ties and incomplete rankings, so models can predict weak orders.Ties arise when outputs are equally good, mediocre, or bad, or when the labeler lacks enough information to distinguish them.Source: §1 · p. 2
  • MORE-PLR encodes bucket orders as multivariate targets for any multi-output regression learner, then applies a post-hoc layer to convert predictions into bucket orders.Each model combines an encoding module, a base multi-output regression learner, and a partial label ranking post-hoc layer.Source: §1 · p. 3
  • MORE-PLR typically has linear runtime in the number of labels versus quadratic runtime for Alfaro et al. (2023b), and achieves satisfactory benchmark accuracy depending on component choices.Accuracy depends on the encoder, multi-output regression learner, and post-hoc layer.Source: §1 · p. 3

Extension of the conference version

  • This expanded conference version adds an encoder module, three encoder variants, and an ϵ-closeness post-hoc layer, enabling broader experiments to identify promising component combinations.The earlier framework used a fixed dataset transformation alongside a base learner and post-hoc layer.Source: Extension of the conference version · p. 3

2 Related Work

Related work groups label-ranking methods into three broad approaches and describes partial label ranking as extending these methods to handle ties. MORE-PLR’s use of multi-output regression resembles earlier work, but differs in its treatment of dependencies between ranking positions.

Label Ranking

  • LR methods use classification reductions, algorithms adapted to model ranking structure, or ensembles that aggregate predictions (Zhou, Liu, Yang, et al., 2014).Reduction methods combine classification tasks (Cheng et al., 2013; Har-Peled et al., 2002; Hüllermeier et al., 2008; Vogel & Clémen, 2020); adapted learners include trees and neural networks (Cheng et al., 2009; de Sá et al., 2011; Ribeiro et al., 2012; Zhou, Liu, Gao, & Qiu, 2014), while ensemble examples include Aledo, Gámez, & Molina (2017), de Sá et al. (2017), and Dery & Shmueli (2020).Source: Label Ranking · p. 4
  • Fotakis et al. (2022) sorted single-target tree outputs into total orders, a special case of MORE-PLR that may miss dependencies between ranking positions.Their work emphasizes theoretical results, including sample-complexity bounds and Bayes errors; Cheng et al. (2013) explored a similar idea in restricted ordinal classification rather than MOR.Source: Label Ranking · p. 4

Partial Label Ranking

  • PLR methods typically adapt LR learners to handle ties in training data and predictions, including trees, ensembles, pairwise reductions, and nearest-neighbor approaches.Further PLR refinements to these approaches are described by Alfaro et al. (2023a, 2023b).Source: Partial Label Ranking · p. 4

3 Preliminaries

Section 3 introduces the partial label ranking problem and the multi-output regression framework used to understand the paper. It defines rankings with ties and describes common approaches to predicting them.

3.1 Partial Label Ranking

  • A bucket order partitions labels into ranked buckets, with labels tied within a bucket; singleton buckets yield a total order, and PLR permits incomplete rankings with ties.Source: §3.1 · pp. 4–5
  • A common PLR approach estimates pairwise preference, tie, and reverse-preference probabilities, then solves the optimal bucket order problem to find a closest bucket matrix under L1 distance.Source: §3.1 · p. 5

3.2 Multi-Output Regression

  • MOR predicts a vector of real-valued targets; approaches either combine single-output regressors or adapt algorithms to model dependencies among outputs.Transformation methods include independent single-target regression, stacking, regression chains, and multi-output support vector regression; algorithm adaptation includes multi-target Gaussian processes and regression trees.Source: §3.2 · p. 6

4 Multi-Output Regression Employed for Partial Label Ranking

MORE-PLR encodes bucket orders as rank-position vectors for multi-output regression, then applies post-hoc transformations to turn regression predictions into bucket orders.

4 Multi-Output Regression Employed for Partial Label Ranking

  • MORE-PLR replaces the classifier with a multi-output regressor and the OBOP step with a post-hoc layer, while allowing multiple training-data encodings.An encoder maps training bucket orders to rank-position vectors; at inference, a post-hoc layer maps the regressor’s prediction vector to a bucket order.Source: §4 · pp. 6–7

4.1 Bucket Orders as Rank Position Vectors

  • Equivalent rank-position-vector encodings represent bucket orders, and all variants yield the same results for total orders.Incomplete rankings assign NA to missing labels; single-target training uses each target’s available observations rather than discarding every incomplete instance.Source: §4.1 · pp. 7, 9

4.2 PLR post-hoc Layers

  • Because regressor prediction vectors may not themselves encode valid bucket orders, PLR post-hoc layers map them to bucket orders.The layers operate on the multi-output model’s k-dimensional output vector.Source: §4.2 · p. 9

Round-rank (RR) Layer

  • The round-rank layer orders predictions by their rounded values and places equal rounded values in the same bucket.Source: Round-rank (RR) Layer · p. 9

Prediction interval (PI) Layer

  • The prediction-interval layer groups items whose intervals overlap, including cascading overlaps, but can produce a single-bucket order.It uses model uncertainty to support ties; intervals are not available from every method, though conformal prediction can construct them for any prediction method (Angelopoulos, Bates, et al., 2023).Source: Prediction interval (PI) Layer · p. 10

ϵ-Closeness (EPS) Layer

5 Experiments

The experiments compare MORE-PLR learners with RPC on standard ranking datasets, evaluating accuracy and efficiency under complete and incomplete rankings. Across problem types and missing-label levels, the single-target methods show the strongest overall stability, while post-hoc encoding choices depend on the layer and missingness.

5.1 Methodology

  • Accuracy uses τX, with five repetitions of ten-fold cross-validation, 5% significance tests, and evaluations at 0%, 30%, and 60% missing labels.The study uses Friedman tests followed by Holm’s post-hoc comparisons when the null hypothesis of equal performance is rejected; reported CPU time averages training and inference across the 5 × 10-fold evaluations.Source: §5.1 · p. 11

5.2 Datasets and Algorithms

  • The evaluation uses standard PLR benchmarks and corresponding LR datasets, comparing RPC with ST, Chain, and Native multi-output regression methods using random forests.For Chain, target order is built recursively from additive correlations because exhaustive search over k! orders is infeasible.Source: §5.2 · pp. 11–12

• RR layer.

  • For RR, dense encoding performs best at 0% missing positions; at 30% and 60%, fractional ranking suits Chain and Native, while ST retains dense encoding.ST with dense encoding was selected as the general RR choice.Source: • RR layer · p. 12

• PI layer.

  • For PI, modified competition encoding is most suitable at 30% and 60% missing positions across methods and q values; it is selected generally with q = 1.At 0% missing positions there is no clear best encoding; q = 1 balances the differing accuracy trends described for LR and PLR.Source: • PI layer · p. 13, • EPS layer · p. 13

• EPS layer.

  • For EPS, modified competition encoding outperforms alternatives across methods, missingness levels, and ϵ values, so it is selected with ϵ = 0.03.Problem-specific q and ϵ choices could improve results; the selected ϵ balances LR’s best value of 0 against PLR’s optimal range of 0.05–0.07.Source: • EPS layer · p. 13

Accuracy

  • For LR, MORE-PLR methods lead RPC on complete rankings and ST methods perform best; for PLR, RPC leads at 0% and 30% missing labels, but ST-EPS leads at 60%.In incomplete PLR rankings, RPC, ST-RR, ST-EPS, and ST-PI perform equally well, and these learners are more stable than Native and Chain. ST retains an instance with a missing label for other label-specific learners, whereas RPC excludes it from all pairwise learners involving that label.Source: Accuracy · pp. 14–15
  • Native-RR ranks first on combined complete-ranking accuracy, while ST-EPS ranks first with 30% and 60% missing labels; ST-RR, ST-PI, and RPC are not statistically different in those incomplete cases.The comparison uses Friedman and Holm tests; Table 1 summarizes the hypothesis tests by problem type and missing-label percentage.Source: Accuracy · p. 15, Table 1 · p. 16

CPU Time

  • Native variants are fastest because they fit one model, while ST is faster overall than RPC; RPC can be faster on datasets with few labels.RR adds O(k) post-hoc work, PI and EPS add O(k^2), and RPC’s transformation requires O(klog(k)); time trends match theoretical complexities, with lower times for incomplete rankings.Source: CPU Time · pp. 16–17, Table 2 · p. 17

6 Conclusions

The paper presents MORE-PLR, a framework for applying multi-output regression to partial label ranking, including an encoder for transforming PLR datasets into MOR datasets. Experiments show that the right component combination can outperform state-of-the-art PLR methods in less time.

6 Conclusions

  • The framework combines multiple components, including a new encoder that transforms PLR datasets into MOR datasets, and can outperform state-of-the-art PLR methods in less time.The reported advantage depends on using the right combination of components.Source: §6 · p. 17
  • Future work could use dataset meta-information and automated machine learning to select MORE-PLR configurations and hyperparameters, and explore alternatives to the fixed encoder in traditional PLR learners.The authors cite automated machine learning techniques as a possible approach.Source: §6 · p. 17
  • Other proposed directions include a hybrid learner combining both frameworks’ strengths and applying the methods to real-world human decision-making, such as ranking prompts when fine-tuning LLMs.The authors describe both as avenues for future work.Source: §6 · pp. 17–18

A Transforming Buckets Orders to Rank Position Vectors

The section transforms bucket orders into rank position vectors for use with different encoding methods.

A Transforming Buckets Orders to Rank Position Vectors

Dense … Fractional

The Fractional subsection lists bucket-wise fractional terms and indicator values for four cases: B_u1, B_u3, B_u2, and B_u4.

Fractional

  • For B_u1, the B1 and B2 terms evaluate to 1 and 1.5, their accompanying values are 1 and 0, and both indicators are 0.Source: Fractional · p. 22
  • For B_u1, the B3 fractional term evaluates to 1 and its accompanying value is 0.Source: Fractional · p. 22
  • For B_u3, the B1 and B2 terms evaluate to 1 and 1.5, their accompanying values are 0 and 1.5, and both indicators are 0.Source: Fractional · p. 22
  • For B_u3, the B3 fractional term evaluates to 1 and its accompanying value is 0.Source: Fractional · p. 22
  • For B_u2, the B1 and B2 terms evaluate to 1 and 1.5, their accompanying values are 0 and 1.5, and both indicators are 0.Source: Fractional · p. 22
  • For B_u2, the B3 fractional term evaluates to 1 and its accompanying value is 0.Source: Fractional · p. 22
  • For B_u4, the B1 and B2 terms evaluate to 1 and 1.5, their accompanying values are 0 and 0, and the indicators are 1 and 0.Source: Fractional · p. 22
  • For B_u4, the B3 fractional term evaluates to 1 and its accompanying value is 1.Source: Fractional · p. 22

B Datasets Description

The section describes the benchmark datasets through identifiers and structural statistics, and notes that algae, movies, and political are real-world datasets.

  • Dataset descriptions include OpenML identifiers, instance and feature counts, label counts, numbers of unique rankings, and mean bucket counts.The identifier is from the OpenML repository.Source: B Datasets Description · p. 23
  • Algae, movies, and political are identified as real-world datasets in the experimental benchmark.Source: Table 3 · p. 23

C Complete Accuracy Results

The section presents accuracy results for complete rankings and incomplete rankings with 30% and 60% missing labels; the supplied passages do not report the table values or identify an overall winner.

Loading 2609.29386v1…