# A novel methodological framework for the analysis of health trajectories and
survival outcomes in heart failure patients

Juliette Murris1, Tristan Amadei2, Tristan Kirscher2, Antoine Klein2,
Anne-Isabelle Tropeano3 & Sandrine Katsahian1,3
1 HeKA, Inserm, Inria, Université Paris Cité, Pierre Fabre R&D 2 ENSAE, IP de
Paris,
3 CIC-1418, HEGP, AP-HP, Paris, France
<EMAIL_ADDRESS>
###### Abstract

Heart failure (HF) contributes to circa 200,000 annual hospitalizations in
France. With the increasing age of HF patients, elucidating the specific
causes of inpatient mortality became a public health problematic. We introduce
a novel methodological framework designed to identify prevalent health
trajectories and investigate their impact on death. The initial step involves
applying sequential pattern mining to characterize patients’ trajectories,
followed by an unsupervised clustering algorithm based on a new metric for
measuring the distance between hospitalization diagnoses. Finally, a survival
analysis is conducted to assess survival outcomes. The application of this
framework to HF patients from a representative sample of the French population
demonstrates its methodological significance in enhancing the analysis of
healthcare trajectories.

##  1 Motivating example

Heart failure (HF) is a cardiovascular condition characterized by the heart’s
inability to pump sufficient blood to meet the body’s oxygen and nutrient
needs. It is a prevalent disease, affecting 1 to 2% of adults in developed
countries, and around 64 million people worldwide (Savarese et al., 2022).
Chronic HF often goes with repeated hospitalizations and embodies the
condition with highest 30-days re-hospitalization rate (Constantinou et al.,
2021). In France alone, over 1.5 million individuals suffer from HF, resulting
in approximately 200,000 hospitalizations annually. Thus, understanding
primary causes of death in these patients and identifying their most frequent
inpatient trajectories holds significant potential for public health impact.

Electronic health records in France aggregate data from all hospitalizations.
The EGB (Echantillon Généraliste des Bénéficiaires) is a random sample and
representative of 1/97th of the population over a two year follow-up (De
Roquefeuil et al., 2009). Trajectories are established using primary and
associated diagnoses based on the International Classification of Disease
(10th edition (ICD-10)). ICD-10 code syntax is text-based, and includes the
principal diagnosis category, indication of surgical procedures, a counter,
and a severity indicator (example given in Figure 1, ’05M092’ is the ICD-10
code for HF).

Figure 1: ICD-10 architecture

The primary objective of this work is to identify frequent inpatient health
trajectories in HF patients in France. Secondary objectives include the
investigation of their associations with mortality.

##  2 Related work

The analysis of trajectories in healthcare is a complex task which helps
understanding the evolution of patients pathway over time. Many approaches
deal clustering (Chouaïd et al., 2022; Lambert et al., 2023; Zhong et al.,
2021), and others with times series, like Markov chains (MacDonald & Zucchini,
1997) or neural networks (Hewamalage et al., 2021). More recently the advent
of text-based input enabled to collect more and more information (Nguyen et
al., 2018; Zhu et al., 2021).

However, none of these methodologies combine pattern mining, clustering and
survival analysis all together, even though these concepts are individually
well-established and active research fields (Kang et al., 2020; Leis et al.,
2023; Murris et al., 2023). This work is a demonstration of the assembling of
existing tools to answer concrete clinical need and represents a ”bridging
fields” contribution.

##  3 Methodological framework

###  3.1 Sequential pattern mining - the PrefixSpan algorithm

We used sequential pattern mining technique to extract frequent trajectories
(Masseglia et al., 2004). PrefixSpan algorithm uses sequence patterns as
tuples $(P,sup)$, where $P$ is a sequential pattern and $sup$ is the number of
sequences in the database that contain $P$ (Pei et al., 2001). The sequence
patterns are used to efficiently compute the support of candidate patterns and
avoid unnecessary database scans. The algorithm efficiently identifies
frequent sequential patterns in the database while maintaining a concise
representation of the patterns (see Algorithm 1).

###  3.2 Unsupervised learning with patient clustering

The clustering of patients brings the interpretability layer to the approach
(Pinaire, 2017). Clusters should fit closely patients’ trajectories based on
their successive hospitalization sequences (see Algorithm 2). K-medoids
algorithm was used to deal with string data and aims to partition input into
$k$ clusters (Kaur et al., 2014). Each cluster is represented by a single data
point called medoid.

Levenshtein distance $\mathcal{D}_{L}$ was used to measure the distance
between two hospitalization sequences (Yujian & Bo, 2007). Traditionally, the
Levenshtein distance calculates the minimum number of edits to perform on
single-characters to transform the word $a$ into the word $b$:

$\mathcal{D}_{L}(a,b)=\begin{cases}\max(|a|,|b|)&\text{if }\min(|a|,|b|)=0,\\\
lev(a_{1:},b_{1:})&\text{if }a[0]=b[0],\\\ 1+\min\begin{cases}lev(a_{1:},b)\\\
lev(a,b_{1:})\\\ lev(a_{1:},b_{1:})\end{cases}&\text{otherwise.}\end{cases}$

with $|\cdot|$ the number of letters in the word, $\cdot_{1:}$ the word
without its first letter and $\cdot[0]$ the first letter of the word.
Throughout our study, we will only use the Levenshtein ratio, being the
normalized value with $lev(a,b)=\frac{\mathcal{D}_{L}(a,b)}{\max(|a|,|b|)}$
with words of the same number of characters, hence $\max(|a|,|b|)=|a|=|b|$. We
used this string-distance to implement a new metric $\mathcal{D}_{ICD10}$ to
compute the distance between two ICD-10 codes $A$ and $B$:

$\displaystyle\mathcal{D}_{ICD10}(A,B)=$ $\displaystyle\omega_{1}\times
lev(A_{0:2},B_{0:2})$ $\displaystyle+\omega_{2}\times lev(A[2],B[2])$
$\displaystyle+\omega_{3}\times lev(A_{3:5},B_{3:5})$
$\displaystyle+\omega_{4}\times lev(A[5],B[5])$

with $\Omega=(\omega_{i})_{i\in[1,4]}\in\mathbb{N^{+}}$. This weighted
distance thus leverages the information from each ICD-10 component (as per
Figure 1). Then, we compare the $i^{th}$ ICD-10 code of a patient with the
$(i-1)^{th}$, $i^{th}$ and $(i+1)^{th}$ ICD-10 codes of another patient,
compute the distances and keep the minimum in order to get the distance
between two patient sequences (Figure 2).

The distance $\mathcal{D}_{P}$ between two patient sequences is the sum of all
ICD-10 codes to one another. This distance respects the symmetry assumption
and
$\mathcal{D}_{P}(patient_{i},patient_{j})=\mathcal{D}_{P}(patient_{j},patient_{i})$.
Further details on the distance matrix are given in Appendix.

Two hyperparameters require settings and are under constraint: $\Omega$ the
weights of the distance metric, with
$0\leq\omega_{4}\leq\omega_{3}\leq\omega_{2}\leq\omega_{1}\leq 100$, and
$k\in[2,20]$ the number of clusters. Cross-validation was used to find optimal
hyperparameters using Optuna (Akiba et al., 2019). The score $S$ to be
maximised was defined as follows, for each cluster $k$:

$s_{p,k}=\sum_{p=1}^{N_{p}}(P,sup)[p]_{k}-(P,sup)[p]$

And $S=\frac{1}{N_{p}\times N}\sum_{k=1}^{N}\sum_{p}^{N_{p}}s_{p,k}$. We set
$N_{p}=3$. Based on outputs from the PrefixSpan algorithm, the idea is to
determine the most frequently occurring ICD-10 code patterns of lengths 1, 2,
3 within each cluster, along with their respective frequencies. Subsequently,
we calculate the frequency of these patterns across the entire dataset and
compute the difference between the two. We then get the mean of these
differences separately for patterns of length 1, 2, and 3. The clustering
score $S$ is then established by averaging these means.

Figure 2: Measuring distances for two patient sequences

###  3.3 Survival analysis

For each patient, survival time and status are available. We implemented two
ensemble methods, namely random survival forests (RSF) and survival gradient
boosting. These methods are survival analysis counterparts of random forests
and gradient boosting algorithms tailored for censored data (Ishwaran et al.,
2008; Hothorn et al., 2006). Cross-validation was performed for hyperparameter
optimization.

Two metrics were used for evaluation. We assessed the goodness of fit using
the Akaike information criterion (AIC), with lower values indicating better
fit (Hu, 2007). Besides, the concordance index (C-index) is a generalization
of the ROC-AUC that can effectively handle censored data, providing a reliable
ranking of survival times based on individual risk scores (Harrell et al.,
1982; 1984).

##  4 Results

This study included adult HF patients who experienced their initial HF
hospitalization between 2010 and 2016. The cohort comprised 10,051 patients,
accounting for a total of 85,594 hospitalizations. Five clusters were
identified with optimal hyperparameters ($\Omega^{T}=[85,75,55,40]$).

(a) Frequent ICD-10 codes

(b) Sankey diagram

Figure 3: Key figures for Cluster 1

When we examined the ten most frequent ICD-10 codes for the $n^{th}$
hospitalization after HF, we observed that these ICD-10 codes collectively
accounted for approximately 50% from the first to the tenth occurrence. This
indicates significant similarity in the care sequences of these patients
(Figure 3). Furthermore, by visualizing the frequent trajectories for the
entire HF patients population, we can identify several common sequences
leading to death (e.g., ’05M09’ for HF hospitalization, ’04M05’ for pleurisy,
or ’04M13’ for pulmonary edema and respiratory distress).

We also observed a high proportion of deaths during the initial
hospitalizations in clusters 2 and 4, consistent with the older age and
shorter hospitalization sequences of these patients (see Appendix).
Additionally, HF patients in cluster 2 who experienced mortality had no more
than six hospitalizations following their first HF episode.

Figure 4 displays the survival trajectories for the most and least optimistic
scenarios within each cluster. Since clusters have varying numbers of
individuals, prediction accuracy varies considerably across models.
Specifically, cluster 3 yields more uncertain predictions compared to cluster
5. Aging consistently emerged as a significant factor contributing to
mortality across all clusters, as well as being male. Prolonged hospital stays
are also associated with a more pessimistic trajectory. We obtained similar
results using RSF and survival gradient boosting, yielding a mean C-index of
0.68 (details in Appendix).

Figure 4: Survival predictions in clusters with best and worst scenarios

##  5 Discussion

By systematically identifying and analyzing frequent hospitalization patterns,
we gained valuable insights into the care sequences of heart failure patients.
This comprehensive analysis enabled to not only discern the most common
reasons for hospitalization but also to trace the trajectories that often
culminate in patient mortality.

Our study benefits from a large dataset, which provides a solid foundation for
our analyses. A significant highlight of our methodology is the use of
unsupervised clustering, not least with the introduction of a novel distance
metric. More recently, methodological research has been conducted to create
similarity measures for clustering purposes, either based on prevalence
(Mannino et al., 2017), or Bayesian framework (Wu & Hao, 2020). However, our
approach enables to keep into account the numbered order of hospitalizations,
and to assess the impact on death using the survival analysis (Pinaire et al.,
2017). Our methodology also allows us to avoid making any a priori assumptions
about the patient population, thereby reducing potential biases associated
with specific patient characteristics (clinical discussion is available in
Appendix A.4).

Health trajectories is a burning topic in clinical research. Within our
methodological framework, we introduce an innovative approach to comprehending
hospitalization sequences and their implications for survival outcomes. While
our focus has been on the HF patients, our approach is adaptable and can be
extended to address more intricate populations, and this way to meet a variety
of clinical challenges.

## References

  * Akiba et al. (2019) Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama.  Optuna: A next-generation hyperparameter optimization framework.  In _Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining_, pp. 2623–2631, 2019.
  * Al-Maolegi & Arkok (2014) Mohammed Al-Maolegi and Bassam Arkok.  An Improved Apriori Algorithm For Association Rules.  _International Journal on Natural Language Computing_ , 3(1):21–29, February 2014.  ISSN 23194111, 22781307.  doi: 10.5121/ijnlc.2014.3103.  URL http://www.airccse.org/journal/ijnlc/papers/3114ijnlc03.pdf.
  * Chouaïd et al. (2022) Christos Chouaïd, Valentine Grumberg, Alexandre Batisse, Romain Corre, Matteo Giaj Levra, Anne-Françoise Gaudin, Martin Prodel, Joannie Lortet-Tieulent, Jean-Baptiste Assié, and Francois-Emery Cotté.  Machine learning–based analysis of treatment sequences typology in advanced non–small-cell lung cancer long-term survivors treated with nivolumab.  _JCO Clinical Cancer Informatics_ , 6:e2100108, 2022.
  * Constantinou et al. (2021) Panayotis Constantinou, Nathalie Pelletier-Fleury, Valérie Olié, Christelle Gastaldi-Ménager, Yves JuillÈre, and Philippe Tuppin.  Patient stratification for risk of readmission due to heart failure by using nationwide administrative data.  _Journal of Cardiac Failure_ , 27(3):266–276, 2021.
  * Cox (1972) David R Cox.  Regression models and life-tables.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 34(2):187–202, 1972.
  * De Roquefeuil et al. (2009) Laurence De Roquefeuil, A Studer, A. Neumann, and Y. Merlière.  L’échantillon généraliste de bénéficiaires : représentativité, portée et limites.  _Pratiques et Organisation des Soins_ , 40(3):213–223, 2009.  ISSN 1952-9201.  doi: 10.3917/pos.403.0213.  URL https://www.cairn.info/revue-pratiques-et-organisation-des-soins-2009-3-page-213.htm.
  * Farré et al. (2017) Núria Farré, Emili Vela, Montse Clèries, Montse Bustins, Miguel Cainzos-Achirica, Cristina Enjuanes, Pedro Moliner, Sonia Ruiz, José María Verdú-Rotellar, and Josep Comín-Colet.  Real world heart failure epidemiology and outcome: A population-based analysis of 88,195 patients.  _PLOS ONE_ , 12(2):e0172745, February 2017.  ISSN 1932-6203.  doi: 10.1371/journal.pone.0172745.  URL https://dx.plos.org/10.1371/journal.pone.0172745.
  * Harrell et al. (1982) Frank E Harrell, Robert M Califf, David B Pryor, Kerry L Lee, and Robert A Rosati.  Evaluating the yield of medical tests.  _Jama_ , 247(18):2543–2546, 1982.
  * Harrell et al. (1984) Frank E Harrell, Kerry L Lee, Robert M Califf, David B Pryor, and Robert A Rosati.  Regression modelling strategies for improved prognostic prediction.  _Statistics in medicine_ , 3(2):143–152, 1984.
  * Hewamalage et al. (2021) Hansika Hewamalage, Christoph Bergmeir, and Kasun Bandara.  Recurrent neural networks for time series forecasting: Current status and future directions.  _International Journal of Forecasting_ , 37(1):388–427, 2021.
  * Hothorn et al. (2006) Torsten Hothorn, Peter Bühlmann, Sandrine Dudoit, Annette Molinaro, and Mark J Van Der Laan.  Survival ensembles.  _Biostatistics_ , 7(3):355–373, 2006.
  * Hu (2007) Shuhua Hu.  Akaike information criterion.  _Center for Research in Scientific Computation_ , 93:42, 2007.
  * Ishwaran et al. (2008) Hemant Ishwaran, Udaya B. Kogalur, Eugene H. Blackstone, and Michael S. Lauer.  Random survival forests.  _The Annals of Applied Statistics_ , 2(3):841–860, September 2008.  ISSN 1932-6157, 1941-7330.  doi: 10.1214/08-AOAS169.  URL https://projecteuclid.org/journals/annals-of-applied-statistics/volume-2/issue-3/Random-survival-forests/10.1214/08-AOAS169.full.
  * Jian Pei et al. (2001) Jian Pei, Jiawei Han, B. Mortazavi-Asl, H. Pinto, Qiming Chen, U. Dayal, and Mei-Chun Hsu.  PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth.  In _Proceedings 17th International Conference on Data Engineering_ , pp. 215–224, Heidelberg, Germany, 2001. IEEE Comput. Soc.  ISBN 978-0-7695-1001-9.  doi: 10.1109/ICDE.2001.914830.  URL http://ieeexplore.ieee.org/document/914830/.
  * Kang et al. (2020) Ji-Soo Kang, Ji-Won Baek, and Kyungyong Chung.  Prefixspan based pattern mining using time sliding weight from streaming data.  _IEEE Access_ , 8:124833–124844, 2020.
  * Kaur et al. (2014) Noor Kamal Kaur, Usvir Kaur, and Dheerendra Singh.  K-medoid clustering algorithm-a review.  _Int. J. Comput. Appl. Technol_ , 1(1):42–45, 2014.
  * Lambert et al. (2023) Judith Lambert, Anne-Louise Leutenegger, Anne-Sophie Jannot, and Anaïs Baudot.  Tracking clusters of patients over time enables extracting information from medico-administrative databases.  _Journal of Biomedical Informatics_ , 139:104309, 2023.
  * Leis et al. (2023) Aleda M Leis, Erin McSpadden, Hannah E Segaloff, Adam S Lauring, Caroline Cheng, Joshua G Petrie, Lois E Lamerato, Manish Patel, Brendan Flannery, Jill Ferdinands, et al.  K-medoids clustering of hospital admission characteristics to classify severity of influenza virus infection.  _Influenza and Other Respiratory Viruses_ , 17(3):e13120, 2023.
  * Mabroukeh & Ezeife (2010) Nizar R Mabroukeh and Christie I Ezeife.  A taxonomy of sequential pattern mining algorithms.  _ACM Computing Surveys (CSUR)_ , 43(1):1–41, 2010.
  * MacDonald & Zucchini (1997) Iain L MacDonald and Walter Zucchini.  _Hidden Markov and other models for discrete-valued time series_ , volume 110.  CRC Press, 1997.
  * Mannino et al. (2017) Michael Mannino, Joel Fredrickson, Farnoush Banaei-Kashani, Iris Linck, and Raghda Alqurashi Raghda.  Development and evaluation of a similarity measure for medical event sequences.  _ACM Transactions on Management Information Systems (TMIS)_ , 8(2-3):1–26, 2017.
  * Masseglia et al. (2004) Florent Masseglia, Maguelonne Teisseire, and Pascal Poncelet.  Extraction de motifs séquentiels. Problèmes et méthodes.  _Revue des Sciences et Technologies de l’Information - Série ISI : Ingénierie des Systèmes d’Information_ , 9(3/4):183, 2004.  doi: 10.3166/isi.9.3-4.183-210.  URL https://hal-lirmm.ccsd.cnrs.fr/lirmm-00108563.
  * Murris et al. (2023) Juliette Murris, Anais Charles-Nelson, Abir Tadmouri Sellier, Audrey Lavenu, and Sandrine Katsahian.  Towards filling the gaps around recurrent events in high dimensional framework: a systematic literature review and application.  _Biostatistics & Epidemiology_, 7(1):e2283650, 2023.
  * Nguyen et al. (2018) Dang Nguyen, Wei Luo, Svetha Venkatesh, and Dinh Phung.  Effective identification of similar patients through sequential matching over icd code embedding.  _Journal of medical systems_ , 42:1–13, 2018.
  * Pei et al. (2001) Jian Pei, Jiawei Han, B. Mortazavi-Asl, H. Pinto, Qiming Chen, U. Dayal, and Mei-Chun Hsu.  PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth.  In _Proceedings 17th International Conference on Data Engineering_ , pp. 215–224, April 2001.  doi: 10.1109/ICDE.2001.914830.  ISSN: 1063-6382.
  * Pinaire (2017) Jessica Pinaire.  _Explorer les trajectoires de patients via les bases médico-économiques : application à l’infarctus du myocarde_.  phdthesis, Université Montpellier, October 2017.  URL https://theses.hal.science/tel-01903477.
  * Pinaire et al. (2017) Jessica Pinaire, Jérôme Azé, Sandra Bringay, and Paul Landais.  Patient healthcare trajectory. an essential monitoring tool: a systematic review.  _Health information science and systems_ , 5:1–18, 2017.
  * Savarese et al. (2022) Gianluigi Savarese, Peter Moritz Becher, Lars H Lund, Petar Seferovic, Giuseppe MC Rosano, and Andrew JS Coats.  Global burden of heart failure: a comprehensive and updated review of epidemiology.  _Cardiovascular research_ , 118(17):3272–3287, 2022.
  * Simpson et al. (2020) Joanne Simpson, Pardeep S Jhund, Lars H Lund, Sandosh Padmanabhan, Brian L Claggett, LI Shen, Mark C Petrie, William T Abraham, Akshay S Desai, Kenneth Dickstein, et al.  Prognostic models derived in paradigm-hf and validated in atmosphere and the swedish heart failure registry to predict mortality and morbidity in chronic heart failure.  _JAMA cardiology_ , 5(4):432–441, 2020.
  * Tibshirani (1996) Robert Tibshirani.  Regression Shrinkage and Selection Via the Lasso.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 58(1):267–288, January 1996.  ISSN 00359246.  doi: 10.1111/j.2517-6161.1996.tb02080.x.  URL https://onlinelibrary.wiley.com/doi/10.1111/j.2517-6161.1996.tb02080.x.
  * Wu & Hao (2020) Zhenya Wu and Jianping Hao.  A maintenance task similarity-based prior elicitation method for bayesian maintainability demonstration.  _Mathematical Problems in Engineering_ , 2020:1–19, 2020.
  * Yujian & Bo (2007) Li Yujian and Liu Bo.  A normalized levenshtein distance metric.  _IEEE transactions on pattern analysis and machine intelligence_ , 29(6):1091–1095, 2007.
  * Zhong et al. (2021) Haodi Zhong, Grigorios Loukides, and Solon P Pissis.  Clustering demographics and sequences of diagnosis codes.  _IEEE Journal of Biomedical and Health Informatics_ , 26(5):2351–2359, 2021.
  * Zhu et al. (2021) Xudong Zhu, Joseph M Plasek, Chunlei Tang, Wasim Al-Assad, Zhikun Zhang, Yun Xiong, Liqin Wang, Sharmitha Yerneni, Carlos Ortega, Min-Jeoung Kang, et al.  Embedding, aligning and reconstructing clinical notes to explore sepsis.  _BMC Research Notes_ , 14:1–6, 2021.

##  Appendix A Appendix

###  A.1 Sequential pattern mining

####  A.1.1 Definitions

Itemset. Let $I=i_{1},...,i_{N_{p}}$ be the set of $N_{p}$ items. A subset of
$I$ is called an itemset. In this study, a pattern or itemset consists in an
ICD-10 code.

Event sequence. An event sequence $seq=\\{e_{1},...,e_{m}\\},e_{i}\subseteq I$
for $1\leq i\leq m$ is an ordered list of itemsets. The event sequence
database is the starting point for sequential pattern mining.

Subsequence. An event sequence $seq_{sub}=\\{r_{1},...,r_{q}\\}$ is a
subsequence of $seq$ if there exist integers $1\leq i_{1}\leq...\leq i_{q}\leq
m$, s. t. $r_{1}\subseteq e_{i_{1}},...,r_{q}\subseteq e_{i_{q}}$.

Support. Let $B=\\{seq_{1},...,seq_{N_{p}}\\}$ a set of sequences. The support
$Freq_{B}(seq)$ of a sequence $seq$ is the number of sequences in $B$ that
have $seq$ as a subsequence. The higher the support, the more frequently the
pattern occurs in the database.

Frequent sequential pattern. An event sequence $seq$ is frequent and called a
frequent sequential pattern if its support is greater than or equal to a
minimum threshold $\sigma:Freq_{B}(seq)\geq\sigma$.

####  A.1.2 Algorithm

The PrefixSpan algorithm was retained and uses the concept of ”prefixes” to
efficiently search for frequent patterns in a sequence database . The
algorithm works by first identifying all frequent single-item sequences, and
then iteratively extending these prefixes to form longer sequential patterns.

The algorithm starts with an empty prefix and the entire dataset as the
initial projected database. It then recursively explores and extends the
prefixes while checking the support of the generated sequences. Frequent
sequences above the minimum support threshold are output, and the process
continues until no more frequent sequences can be found.

Algorithm 1 The PrefixSpan algorithm

  1. 1.

Initialize: Start with an empty set of frequent patterns $I_{0}=\emptyset$

  2. 2.

Frequent Items: For each item $i$ in the first sequence $seq_{1}$ of the input
data, create a singleton pattern

  3. 3.

Generate Sequences: For each frequent item $i$ found in step 2, extend the
current prefix sequence by adding that item to the set of frequent patterns

  4. 4.

Recursive Search: For each new sequence created in step 3, repeat steps 2 and
3 recursively. For each pattern:

    1. (a)

Construct a database of all sequences that contain the pattern as a
subsequence

    2. (b)

For each item that appears after the last item of the pattern in the input
data, create a new pattern by extending the pattern with the item

    3. (c)

Compute the support of the new pattern by concatenating the support of the
item with the support of the database

    4. (d)

If the new pattern is frequent in the database, add it to the set of frequent
patterns and continue the recursive search

PrefixSpan algorithm is known for its efficiency and scalability, particularly
for mining long sequential patterns (Mabroukeh & Ezeife, 2010). Of note,
several sequential pattern mining algorithms were experimented, like APriori
(Al-Maolegi & Arkok, 2014). Similar support for patterns were found but
computing time was much higher. This is in line with existing literature in
terms of run-time and memory usage (Jian Pei et al., 2001).

Table 1: Most occurring patterns in health care pathway for each patient
clusters

Cluster | Count | Freq. | Top1 pattern (len1) | Count | Freq. | Top1 pattern (len2) | Count | Freq. | Top1 pattern (len3)
---|---|---|---|---|---|---|---|---|---
1 | 833 | 0.610 | [’Death’] | 507 | 0.371 | [’05M09’, ’Death’] | 301 | 0.220 | [’05M09’, ’05M09’, ’Death’]
2 | 3467 | 0.685 | [’Death’] | 1542 | 0.305 | [’05M09’, ’Death’] | 336 | 0.066 | [’05M09’, ’05M09’, ’Death’]
3 | 22 | 0.629 | [’23M20’] | 15 | 0.429 | [’23M20’, ’23M20’] | 8 | 0.229 | [’23M20’, ’23M20’, ’23M20’]
4 | 2082 | 0.651 | [’Death’] | 1111 | 0.347 | [’05M09’, ’Death’] | 487 | 0.152 | [’05M09’, ’05M09’, ’Death’]
5 | 224 | 0.579 | [’05M09’] | 132 | 0.341 | [’05M09’, ’05M09’] | 75 | 0.194 | [’05M09’, ’05M09’, ’05M09’]

Table 2: Second most occurring patterns in health care pathway for each
patient clusters

Cluster | Count | Freq. | Top2 pattern (len1) | Count | Freq. | Top2 pattern (len2) | Count | Freq. | Top2 pattern (len3)
---|---|---|---|---|---|---|---|---|---
1 | 777 | 0.569 | [’05M09’] | 431 | 0.316 | [’05M09’, ’05M09’] | 256 | 0.187 | [’05M09’, ’05M09’, ’05M09’]
2 | 2032 | 0.401 | [’05M09’] | 489 | 0.097 | [’04M05’, ’Death’] | 104 | 0.021 | [’05M09’, ’05M09’, ’05M09’]
3 | 18 | 0.514 | [’05M09’] | 10 | 0.286 | [’23M20’, ’16M11’] | 8 | 0.229 | [’23M20’, ’23M20’, ’23M20’]
4 | 1586 | 0.496 | [’05M09’] | 642 | 0.201 | [’05M09’, ’05M09’] | 285 | 0.089 | [’05M09’, ’05M09’, ’05M09’]
5 | 223 | 0.576 | [’Death’] | 129 | 0.333 | [’05M09’, ’Death’] | 75 | 0.194 | [’05M09’, ’05M09’, ’Death’]

Table 3: Third most occurring patterns in health care pathway for each patient
clusters

Cluster | Count | Freq. | Top3 pattern (len1) | Count | Freq. | Top3 pattern (len2) | Count | Freq. | Top3 pattern (len3)
---|---|---|---|---|---|---|---|---|---
1 | 456 | 0.334 | [’05K10’] | 255 | 0.187 | [’04M05’, ’Death’] | 124 | 0.091 | [’05K10’, ’05M09’, ’Death’]
2 | 615 | 0.121 | [’04M05’] | 418 | 0.083 | [’05M09’, ’05M09’] | 102 | 0.020 | [’02C05’, ’05M09’, ’Death’]
3 | 13 | 0.371 | [’06M03’] | 9 | 0.257 | [’23M20’, ’05M09’] | 8 | 0.229 | [’23M20’, ’23M20’, ’23M20’]
4 | 823 | 0.257 | [’02C05’] | 505 | 0.158 | [’04M05’, ’Death’] | 208 | 0.065 | [’02C05’, ’05M09’, ’Death’]
5 | 167 | 0.432 | [’05K10’] | 88 | 0.227 | [’05K10’, ’05M09’] | 56 | 0.145 | [’05K10’, ’05M09’, ’05M09’]

Table 4: Proportions of top 10 ICD-10 codes in nth hospitalization after first
hospitalization for heart failure - Deceased patients

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---|---
05M09 | 1.000 | 0.169 | 0.155 | 0.143 | 0.131 | 0.134 | 0.137 | 0.124 | 0.124 | 0.123
Death |  | 0.165 | 0.148 | 0.156 | 0.143 | 0.144 | 0.154 | 0.156 | 0.132 | 0.137
05K10 |  | 0.043 | 0.020 | 0.021 | 0.014 | 0.019 | 0.017 | 0.023 | 0.022 | 0.015
05M08 |  | 0.024 | 0.017 | 0.016 |  |  |  | 0.016 |  |
04M05 |  | 0.023 | 0.028 | 0.033 | 0.026 | 0.030 | 0.029 | 0.018 | 0.023 | 0.015
23M20 |  | 0.019 | 0.019 | 0.016 | 0.022 | 0.018 | 0.017 | 0.020 | 0.022 | 0.015
04M13 |  | 0.017 | 0.014 | 0.016 |  | 0.016 | 0.019 | 0.018 |  |
02C05 |  | 0.016 | 0.017 | 0.017 | 0.016 | 0.014 | 0.019 | 0.020 |  |
16M11 |  | 0.015 | 0.020 | 0.020 | 0.019 | 0.023 | 0.021 | 0.023 | 0.022 | 0.022
05K06 |  | 0.013 |  |  | 0.015 | 0.016 |  |  | 0.014 |
04M20 |  |  | 0.014 |  | 0.016 | 0.019 | 0.016 | 0.014 | 0.017 |
06M03 |  |  |  | 0.015 |  |  |  |  | 0.015 |
09M05 |  |  |  |  |  |  |  |  |  | 0.014
10M16 |  |  |  |  |  |  | 0.019 |  |  | 0.014
11M04 |  |  |  |  |  |  |  |  |  | 0.018
23M06 |  |  |  |  | 0.012 |  |  |  |  |
23Z02 |  |  |  |  |  |  |  |  | 0.014 | 0.017

###  A.2 Clustering

####  A.2.1 Distance matrix

Because we are working with strings of characters instead of numerical values
- and we must keep those strings, we cannot encode them into numerical values
- we cannot directly apply clustering algorithms on our data. With $N$ the
total number of patients, the distance matrix $A$ writes

$\forall(i,j)\in[1,N],A_{i,j}=\mathcal{D}_{P}(patient_{i},patient_{j})$ (1)

Two properties are noted:

  * •

$\forall i\in[1,N],A_{i,i}=0$,

  * •

$A^{T}=A\Leftrightarrow\forall(i,j)\in[1,N],A_{i,j}=A_{j,i}$.

####  A.2.2 K-medoids algorithm

The algorithm proceeds iteratively:

  1. 1.

Select $k$ random medoids from the dataset;

  2. 2.

Each data point is assigned to its closest medoid and calculates the total
distance between them;

  3. 3.

Improve the clustering by iteratively swapping one of the medoids with a non-
medoid point and recompute the total distance;

  4. 4.

Whenever the total distance decreases, the swap is accepted and the new point
becomes the medoid for the cluster.

This process is repeated until no further improvement can be made. The pseudo-
code is provided below.

Algorithm 2 K-Medoids Algorithm

1:$D$: dataset, $k$: number of clusters

2:$C$: set of clusters, $M$: set of medoids

3:Initialize $M$ with $k$ random data points from $D$

4:Assign each data point in $D$ to its closest medoid

5:Calculate the total distance $TD$ of all data points to their assigned
medoids

6:$change\leftarrow\textbf{true}$

7:$iter\leftarrow 1$

8:while change do

9: $change\leftarrow$ false

10: for all $m\in M$ do

11: for all $p\in D\setminus M$ do

12: Swap $m$ with $p$

13: Assign each data point in $D$ to its closest medoid

14: Calculate the total distance $TD^{\prime}$ of all data points to their
assigned medoids

15: if $TD^{\prime}<TD$ then

16: $M\leftarrow$ updated set of medoids

17: $C\leftarrow$ updated set of clusters

18: $TD\leftarrow TD^{\prime}$

19: $change\leftarrow$ true

20: else

21: Swap $m$ with $p$ $\triangleright$ Revert swap

22: end if

23: end for

24: end for

25:end while

26:return $C$, $M$

####  A.2.3 Clusters visualization

Except for cluster 3, there were no significant differences amongst clusters.
Cluster 3 with only 35 patients, stood out due to a considerably higher number
and/or longer duration of hospitalizations compared to other patients. Other
clusters included 1,366 patients (mean (sd) age = 78 (12.4) and 44.8% were
women), 5,063 patients (mean (sd) age = 83 (13.8) and 55.6% were women), 3,200
patients (mean (sd) age = 81 (12.3) and 47.8% were women), and 387 patients
(mean (sd) age = 72 (13.8) and 44.2% were women), respectively.

(a) Cluster 1

(b) Cluster 2

(c) Cluster 3

(d) Cluster 4

(e) Cluster 5

Figure 5: Most frequent ICD-10 codes after first hospitalization for heart
failure - Deceased patients - Cluster 1 to 5

Here is the Python code to generate the figures above:

Listing 1: Python code to compute most frequent ICD-10 codes after first
hospitalization for heart failure

⬇

length_care_pathway = 10

top_k = 5 # we’ll consider the top 5 most frequent ICD-10 codes

# for each step in the care pathways

database_top_k_frequent_codes = {}

for i in range(length_care_pathway):

# for hospitalization i in all care pathways,

# consider the 5 most frequent ICD-10 codes found

# the k most frequent codes per hospitalization step were found previoulsy

# through with text mining algorithms

top_k_frequent_codes_i = df.iloc[i].sort_values(ascending=False)[:top_k]

database_top_k_frequent_codes[f’{i}’] = top_k_frequent_codes_i

database_top_k_frequent_codes =
pd.DataFrame(database_top_k_frequent_codes).transpose()

database_top_k_frequent_codes.plot(kind=’bar’, stacked=True));

Table 5: Samples of the database_top_k_frequent_codes dataframe

04M05 04M13 04M24 05K10 05M08 05M09 05M22 10M16 11M04 16M11 23M20 23Z02 Death
0 NaN NaN NaN NaN NaN 1111.000000 NaN NaN NaN NaN NaN NaN 1 23.000000 NaN NaN
34.000000 28.000000 204.000000 NaN NaN NaN NaN NaN 118.000000 2 37.000000 NaN
NaN NaN 18.000000 191.000000 NaN NaN NaN 23.000000 NaN NaN 108.000000 3
39.000000 20.000000 NaN NaN NaN 160.000000 NaN NaN NaN NaN NaN 18.000000
124.000000 4 21.000000 NaN NaN NaN NaN 110.000000 NaN NaN NaN 15.000000
14.000000 NaN 133.000000

(a) Sankey Diagram Cluster 1

(b) Sankey Diagram Cluster 2

(c) Sankey Diagram Cluster 3

(d) Sankey Diagram Cluster 4

(e) Sankey Diagram Cluster 5

Figure 6: Sankey Diagrams: patient frequent flows at the cluster level

Here is the Python code for the generateSankey function using the prefixspan
library:

Listing 2: Python code for generating Sankey diagrams using PrefixSpan

⬇

from prefixspan import PrefixSpan

def generateSankey(df_care_pathways, cluster_n, top_k_frequent_codes):

# df_care_pathways represents the pathways of deceased heart-failure patients

df_pathways_cluster = df_care_pathways.loc[df_care_pathways.cluster ==
cluster_n]

nb_patients_cluster_n = len(df_pathways_cluster)

df_pathways_23 = df_pathways_cluster.astype(str).iloc[:,2:4]

# keep first and second ICD-10 codes

df_pathways_34 = df_pathways_cluster.astype(str).iloc[:,3:5]

# keep second and third ICD-10 codes

corpus_heart_failures = []

for patient in range(nb_patients_cluster_n):

icd_codes = [df_pathways_23.iloc[patient][0], df_pathways_23.iloc[patient][1]]

corpus_heart_failures.append(icd_codes)

ps = PrefixSpan(corpus_heart_failures)

ps.minlen = 2

output_corpus = ps.topk(top_k_frequent_codes)

corpus_heart_failures_2 = []

for patient in range(nb_patients_cluster_n):

if str(df_pathways_34.iloc[patient][1])!=’nan’:

icd_codes = [df_pathways_34.iloc[patient][0], df_pathways_34.iloc[patient][1]]

corpus_heart_failures_2.append(icd_codes)

else:

corpus_heart_failures_2.append([df_pathways_34.iloc[patient][0], ’nan’])

ps_corpus_2 = PrefixSpan(corpus_heart_failures_2)

ps_corpus_2.minlen = 2

output_corpus_2 = ps_corpus_2.topk(top_k_frequent_codes)

return output_corpus, output_corpus_2

The outputs of the function generateSankey above are then used with HTML code
to create the clean Sankey outputs.

We also evaluated the clusters by calculating the minimum distance between the
ICD-10 code of each data point and the ICD-10 codes of the cluster’s medoid
(see Figure 7). The shading in the graphs indicates the extent to which the
ICD-10 code deviates from the hospitalization pattern of the patient medoid.
Lighter areas, particularly in clusters 1 and 5, suggest that the data points
within these clusters exhibit relatively close similarity to one another.

Figure 7: Distance of ICD-10 codes with the medoid for each cluster

###  A.3 Survival analysis

We define the survival function

$S(t)=\mathbb{P}[T>t]=1-F(t)=\int_{t}^{\infty}f(u)du$

with $f$ the density and $F$ the distribution function. $T$ is the time of
occurrence of some specific event, time to death in our case. We introduce
censoring $C$ to the labels, whenever the patient died or not with
$T^{*}=\min(T,C)$ and $\Delta=\mathbb{1}_{\\{T\leq C\\}}$.

A convenient way of modeling relationships between $T$ and explanatory
features $X$ is the hazard function. Let $\lambda(t|X)$ denote the hazard
function associated with the distribution of $T$ given $X$.

The Cox proportional hazard (CPH) is the most common approach to model
survival events (Cox, 1972). It writes

$\lambda(t|X)=\lambda_{0}^{*}(t)\exp(f^{*}(X))$

$\lambda_{0}^{*}$ is the baseline hazard function and usually
$f^{*}(X)=X^{T}\beta$ with $\beta\in\mathbb{R}^{d}$.

This model assumes hazards to be proportional, i.e. hazard ratios to be
independent of time as

$\frac{\lambda_{i}(t|X_{i}=x_{i})}{\lambda_{j}(t|X_{j}=x_{j})}=\exp(f^{*}(x_{i})-f^{*}(x_{j}))$

This approach can be penalized and/or include splines to handle non-linear
relations (Tibshirani, 1996). This semi-parametric approach was applied to the
data, however its main assumptions were never met. For this reason ensemble
methods were selected.

Here is the Python code for the Survival random forest function using the
scikit survival library:

Listing 3: Python code for generating the Grid Search over the number of
estimator in our survival random forest

⬇

data=profil_patient[[’y_nais’,’BEN_SEX_COD’,’Nb_hospit’,’CHOC’,’Nb_jours_sej’]]

Label= profil_patient[[’Mort’,’Nb_survie’]].to_records(index=False)

X_train, X_test, y_train, y_test = train_test_split(data, Label,
test_size=0.25)

Liste_score = []

Liste_nb_estimators= []

rsf = RandomSurvivalForest(min_samples_split=10,

min_samples_leaf=15,

n_jobs=-1,

random_state=random_state,

verbose=0)

for i in range(1, 20):

n_estimators = i * 1

rsf.set_params(n_estimators=n_estimators)

rsf.fit(X_train, y_train)

Liste_score.append(rsf.score(X_test, y_test))

Liste_nb_estimators.append(n_estimators)

print(rsf.score(X_test, y_test))

plt.plot(Liste_nb_estimators, Liste_score)

plt.xlabel(””)

plt.ylabel(””)

plt.grid(True)

Table 6: Evaluation for each cluster Cluster | AIC | C-Index
---|---|---
1 | 8,495 | 0.612
2 | 41,748 | 0.640
3 | 39 | 0.887
4 | 24,015 | 0.621
5 | 1773 | 0.543

###  A.4 Clinical discussion

The cohort of this study was comparable to other similar studies, namely in
terms of age and gender, and with poor prognosis with high rate of
hospitalization and mortality (Farré et al., 2017). The results obtained from
this work may thus be comparable to those of other similar groups. For this
reason, age and being male being strongly associated with mortality were
expected findings (Simpson et al., 2020).

Nevertheless, our study is subject to several limitations. First, the
inclusion of primary diagnoses alongside the principal diagnoses in
hospitalizations could provide a more comprehensive view of patients’ medical
histories, enabling a deeper understanding of their healthcare trajectories.
Unfortunately, acquiring such data presents a challenge, as only a limited
subset of hospitalizations in our dataset contains this information.
Consequently, our analysis is constrained to ICD-10 codes. Besides, the
sequential pattern mining analysis uncovered certain high-risk patterns that
could potentially serve as additional features in our survival model, similar
to our inclusion of cardiac shock. Integrating these factors into our model
would enable to quantify the excess mortality associated with these risky
healthcare sequences. We believe that this additional information could
enhance the precision of our predictions and yield a more nuanced
understanding of the underlying causes of mortality among heart failure
patients.


# Unsupervised Contrast-Consistent Ranking with Language Models

Niklas Stoehr${}^{\text{1}}$ Pengxiang Cheng${}^{\text{2}}$ Jing
Wang${}^{\text{2}}$
Daniel Preoţiuc-Pietro${}^{\text{2}}$ Rajarshi Bhowmik${}^{\text{2}}$
${}^{\text{1}}$ETH Zürich ${}^{\text{2}}$Bloomberg
<EMAIL_ADDRESS>{pcheng134,jwang1621,dpreotiucpie,
<EMAIL_ADDRESS>Work done during an internship at Bloomberg

###### Abstract

Language models contain ranking-based knowledge and are powerful solvers of
in-context ranking tasks. For instance, they may have parametric knowledge
about the ordering of countries by size or may be able to rank reviews by
sentiment. Recent work focuses on pairwise, pointwise, and listwise prompting
techniques to elicit a language model’s ranking knowledge. However, we find
that even with careful calibration and constrained decoding, prompting-based
techniques may not always be self-consistent in the rankings they produce.
This motivates us to explore an alternative approach that is inspired by an
unsupervised probing method called Contrast-Consistent Search (CCS). The idea
is to train a probing model guided by a logical constraint: a model’s
representation of a statement and its negation must be mapped to contrastive
true-false poles consistently across multiple statements. We hypothesize that
similar constraints apply to ranking tasks where all items are related via
consistent pairwise or listwise comparisons. To this end, we extend the binary
CCS method to Contrast-Consistent Ranking (CCR) by adapting existing ranking
methods such as the Max-Margin Loss, Triplet Loss, and Ordinal Regression
objective. Our results confirm that, for the same language model, CCR probing
outperforms prompting and even performs on a par with prompting much larger
language models.

##  1 Introduction

Figure 1: We study pairwise, pointwise, and listwise prompting and probing for unsupervised ranking. prompt type | template | prompting | CCR probing
---|---|---|---
ItemPair P | Is  {item A} more positive than  {item B}?  $X$ |  | constrain $X$ to
---
{Yes / No}
| set $X$ to
---
{Yes / No}
ItemSingle S |  | {"optional": On a scale from 0 to 10,}
---
The  stance of  {item} is  $X$
| constrain $X$ to
---
{0, 1,…,10}
| set $X$ to
---
[MASK]
ItemList L |  | {"optional": context}. Order by  stance. Options: "A"
---
{item A}, "B"  {item B}… .The correct ordering is:  $X$
| constrain $X$ to
---
{A, B, …}
| embed via ItemSingle
---
then listwise loss
Table 1: We consider three different prompt types, ItemPair P, ItemSingle S,
and ItemList L, that all consist of a  ranking criterion, a  comparison token,
and one or multiple  items to be ranked. ItemPair and ItemSingle can be used
for prompting and CCR probing in a similar fashion. To realize listwise CCR
probing, we first obtain individual vector representations of items via
ItemSingle and then connect all items through a listwise loss objective.

“What is the correct ordering of the following countries by size: [USA, China,
Russia, Canada, …]?”

Language models have been shown to store plenty of facts and have powerful
reasoning capacities (Petroni et al., 2019; Brown et al., 2020). Ranking tasks
require both of these skills: multiple items have to be put in order based on
a comparison criterion. We are posing the question: what is the best way to
elicit a model’s ranking knowledge and in-context ranking capacities without
supervision? Knowing the answer to this question brings the following
benefits: we can evaluate what ranking knowledge a language model contains and
uncover knowledge gaps, outdated information, and existing biases before
applying the model. Once we trust a model, we can then query ranking-based
facts or apply the model to solve ranking tasks.

A natural starting point for unsupervised ranking is prompting (Li et al.,
2022a). In § 2, we explore different task formulations: pairwise, pointwise,
and listwise prompting, as outlined in Fig. 1. In the pairwise setting, any
two items are compared and pairwise results are converted into a global
ranking post-hoc. In pointwise prompting, the model assigns a score to each
item individually. The listwise approach tasks the model to directly decode
the entire ranking. For all of these approaches, constrained decoding is
essential to ensure the output can be converted into a ranking including all
items. Yet, even with constrained decoding and calibration, we find that
prompting often leads to inconsistent rankings.

For this reason, we turn to the model-internal representations of ranking
tasks and their items in § 3. We train a “probing model” with various
unsupervised ranking objectives to find a latent ordering direction of the
items’ vector representations. Burns et al. (2023) recently proposed the
Contrast-Consistent Search (CCS) method to find a direction in a language
model’s activation space that distinguishes truthful statements from false
ones (Li et al., 2023). This is achieved with a loss that imposes a logical
constraint: the representation of a statement and its negation must be mapped
to opposite (contrasting) poles.

Ranking tasks share similar properties. We can convert a ranking task into
multiple pairwise comparisons and train a probe to find a “ranking direction”
that allows ranking one item higher than the other consistently across all
pairs. This has one significant advantage over the original CCS method for
factual statements—instead of requiring a training set of multiple yes-no
questions, we can source all pairwise permutations from a list of items which
allows training the probe on a single ranking task.

We translate the original binary CCS method into Contrast-Consistent Ranking
(CCR) by exploring pairwise (§ 3.1), pointwise (§ 3.2), and listwise (§ 3.3)
approaches as illustrated in Fig. 1. Pairing items in the prompt and obtaining
the vector representations of all pairs is computationally expensive.
Moreover, binary contrastive poles may not be ideally suited for ranking tasks
where the distances between items are not unit-length. In line with the
pointwise approach, we instead embed each item individually, e.g., “The size
of the U.S. is [MASK], The size of China is [MASK], …”. We then pair the items
represented by the activations of the [MASK] tokens in the loss function. In
particular, we propose variants of the well-known Max-Margin and Triplet Loss
by including a _consistency_ and _confidence_ component. As a final
adjustment, we mitigate the limitation that pairwise and pointwise objectives
do not guarantee transitivity: item A may be ranked above B, B above C, but C
above A, creating a circular contradiction. To address this, we introduce an
unsupervised ordinal regression objective for listwise CCR probing.

Our experiments in § 4 confirm that CCR probing outperforms prompting with
DeBERTa (He et al., 2021) and GPT-2 (Jiang et al., 2021) models. Among the CCR
probing methods, the Triplet Loss variant performs best on average. CCR
probing with DeBERTa and GPT-2 even achieves similar performance to prompting
a much larger MPT-7B (MosaicML, 2023) model across $6$ datasets. In addition,
CCR probing has the advantage of better control and interpretability as we
discuss in § 5.

##  2 Prompting for Rankings

Prompting is an accessible way to test a language model’s ranking knowledge
(Li et al., 2022a). We experiment with three different prompt types outlined
in Table 1: pairwise, pointwise, and listwise prompting (Qin et al., 2023).
All prompt types contain at least one  item to be ranked, a  criterion to rank
on, and what we refer to as  comparison token. In every setting, we rely on
some form of “constrained decoding” or “constrained mask-filling” with
encoder-only models. In essence, we restrict the vocabulary to a list of
candidates and select the highest-scoring tokens.

#### Pairwise Prompting.

ItemPair P: _Is {item A} more positive than  {item B}?  Yes / No_—Between any
two items, the language model is tasked to make ranking decisions which are
then converted into a ranking post-hoc as elaborated in § 4.3. Without
calibration (Zhao et al., 2021), the model tends to always output the token
most frequently observed during training, basically disregarding the context.
Following (Burns et al., 2023), we compute the mean score of the “Yes” and
“No” tokens in all pairwise prompts and then subtract the respective mean from
each token score.

#### Pointwise Prompting.

ItemSingle S: _On a scale from $0$ to $10$, the  stance of  {item} is  $X$_—In
pointwise prompting, the language model ranks one item at a time. If two items
are assigned the same rank (i.e., the same candidate token from the list
${\color[rgb]{0.76171875,0.046875,0.5234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.76171875,0.046875,0.5234375}X}\in\\{0,1,2,\ldots,10\\}$),
we break the tie by sorting tokens by their scores.

#### Listwise Prompting.

ItemList L _optional: context. Order by stance. Options: “A”  {item A}, “B”
{item B}… The correct ordering is:  $X$_—For listwise prompting, we apply a
step-wise approach: we let the model select the highest-scoring item from the
list of candidates
${\color[rgb]{0.76171875,0.046875,0.5234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.76171875,0.046875,0.5234375}X}\in\\{A,B,...\\}$,
remove this token from the list, and append it to the prompt. We repeat the
process until the candidate list is exhausted. Importantly, the ordering of
the candidate options in the prompt poses a “positional bias” (Han et al.,
2023; Wang et al., 2023). Therefore, we randomly shuffle the ordering of the
options and repeat the listwise prompting multiple times.

| prompt type | emb calls | loss / model | datapoints
---|---|---|---|---
CCR probing |  ItemPair P | $\mathcal{O}(N^{2})$ | origCCS | $\mathcal{O}(N^{2})$
ItemSingle S | $\mathcal{O}(N)$ | origCCS | $\mathcal{O}(N^{2})$
ItemSingle S | $\mathcal{O}(N)$ | MarginCCR | $\mathcal{O}(N^{2})$
ItemSingle S | $\mathcal{O}(N)$ | TripletCCR | $\mathcal{O}(N^{3})$
ItemSingle S | $\mathcal{O}(N)$ | OrdRegCCR | $\mathcal{O}(N)$
prompting |  ItemPair P | $\mathcal{O}(N^{2})$ | MLM / causal | $\mathcal{O}(N)$
ItemSingle S | $\mathcal{O}(N)$ | MLM / causal | $\mathcal{O}(N)$
ItemList L | $\mathcal{O}(N)$ | MLM / causal | $\mathcal{O}(1)$
Table 2: Complexity of each approach as a factor of the number of items $N$
per ranking task. We distinguish between the number of required calls of an
“embedding function” (i.e., a language model) and the number of resulting data
points to be considered in a subsequent loss objective. The asymptotic
complexity of permutations and combinations is both $\mathcal{O}(N^{2})$.

##  3 Unsupervised Probing for Rankings

Querying a language model’s knowledge via prompting, we limit ourselves to
prompt design and evaluating token scores. In contrast, probing accesses the
information contained within a language model more directly by operating on
latent vector representations. Conventionally, probing involves training a
“diagnostic classifier” to map the vector representations of an utterance to a
target label of interest (e.g., tense, gender bias) in a supervised fashion
(Pimentel et al., 2022). The goal typically is to measure what information is
contained within a language model. While the motivation of this work is
closely related, we focus on an unsupervised probing variant and consider
supervised probing only as a performance upper bound for validation purposes
in § 4.5 and § 5.

#### Contrast-Consistent Search (CCS).

Burns et al. (2023) propose Contrast-Consistent Search (CCS), an unsupervised
probing method which seeks to train a probe to satisfy logical constrains on
the model’s activations. Instead of labels, CCS requires paired prompts in the
form of yes-no questions:

$\displaystyle{\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}x_{i}^{+}}$
$\displaystyle=\text{``{Are elephants mammals?
{\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}
Yes}}''}$ (1)
$\displaystyle{\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}x_{i}^{-}}$
$\displaystyle=\text{``{Are elephants mammals?
{\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}
No}}''}$

Both statements
${\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}x_{i}^{+}}$
and
${\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}x_{i}^{-}}$
are fed into a language model and the activations of the model’s last hidden
layer corresponding to the “Yes” and “No” token,
${\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}\bm{x}_{i}^{+}}$
and
${\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}\bm{x}_{i}^{-}}$
(bolded), are considered in subsequent steps. First, the vector
representations
${\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}\bm{x}_{i}^{+}}$
and
${\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}\bm{x}_{i}^{-}}$
from different yes-no questions have to be Z-score normalized to ensure they
are no longer forming two distinct clusters of all “Yes” and “No” tokens.
Next, the paired vectors are projected to a score value $s_{i}$ via the probe
$f_{\theta}(\bm{x}_{i})=\sigma(\bm{\theta}^{T}\bm{x}_{i}+b)$ which is trained
using the origCCS loss objective:

$\displaystyle\textsc{origCCS}=$
$\displaystyle\overbrace{\Big{(}f_{\theta}({\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}\bm{x}_{i}^{+}})-\big{(}1-f_{\theta}({\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}\bm{x}_{i}^{-}})\big{)}\Big{)}^{2}}^{\text{\emph{consistency}}}$
(2)
$\displaystyle+\underbrace{\min\big{(}f_{\theta}({\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}\bm{x}_{i}^{+}}),f_{\theta}({\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}\bm{x}_{i}^{-}})\big{)}^{2}}_{\text{\emph{confidence}}}$

origCCS comprises two terms: the _consistency_ term encourages
$f_{\theta}({\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}\bm{x}_{i}^{+}})$
and
$f_{\theta}({\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}\bm{x}_{i}^{-}})$
that sum up to $1$. The _confidence_ term pushes the scalars away from a
deficient
$f_{\theta}({\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}\bm{x}_{i}^{+}})=f_{\theta}({\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}\bm{x}_{i}^{-}})=0.5$
solution, and instead encourages one to be close to $0$ and the other to be
close to $1$. This means, the origCCS objective promotes mapping true and
false statements to either $0$ or $1$ consistently, when the probe is trained
on multiple yes-no questions.111CCS (and CCR) are direction-invariant, see
(Appendix A).

#### From Yes-No Questions to Rankings.

On a more abstract level, origCCS relies on logical constraints to identify a
true-false mapping in the models’ activations. We argue that ranking
properties can similarly be expressed as logical constraints which are
discernable by a probing model. In fact, the pairing of yes-no statements in
Eq. 1 resembles the ItemPair prompt type presented in Table 1. However,
instead of true-false poles, ItemPair expresses an ordering relationship.

One advantage of ranking tasks is that we can source many pairwise comparisons
from a single ranking task, which reduces the need for a training set of
different yes-no questions. The original CCS paper showed that a training set
of as few as $8$ pairwise comparisons can be enough for good test set
performance. A ranking task of $8$ items allows for $28$ comparisons when
considering all pairwise combinations, and even $56$ comparisons when
considering all pairwise permutations.

We adapt binary CCS to CCR by gradually modifying three components of the
original method: the prompt design, the loss function, and the probing model.
In § 3.1, we start by changing the binary prompt to the ItemPair prompt type.
Next, we explore pointwise CCR probing in § 3.2 and modify the prompt type and
loss function. Finally, in § 3.3, we alter prompt type, loss function, and
probe model altogether to propose a transitivity-consistent listwise approach.

###  3.1 Pairwise CCR Probing

Pairwise CCR probing for rankings is straight-forward as we only need to
change the binary prompt in Eq. 1 to the ItemPair P prompt type in § 3.1, but
apply the original origCCS objective (Eq. 2), which we abbreviate as “origCCS
(P)”.

###  3.2 Pointwise CCR Probing

We observe several methodological shortcomings of the pairwise CCR probing
approach based on origCCS that we address in the following. We start with the
observation that it is computationally expensive to “embed” all pairwise item
permutations as depicted in Table 2. Instead, we propose to “embed” each item
individually and to pair their representations in the subsequent loss
objective. To this end, we consider the ItemSingle S prompt type for CCR
probing which requires fewer “calls” of a language model:

$\displaystyle{\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}x_{n}^{A}}$
$\displaystyle=\text{``{The size of country A is
{\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}
[MASK]}}''}$ (3)
$\displaystyle{\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}x_{n}^{B}}$
$\displaystyle=\text{``{The size of country B is
{\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}
[MASK]}}''}$
$\displaystyle{\color[rgb]{0.0390625,0.5234375,0.00390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.5234375,0.00390625}x_{n}^{C}}$
$\displaystyle=\text{``{The size of country C is
{\color[rgb]{0.0390625,0.5234375,0.00390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.5234375,0.00390625}
[MASK]}}''}$ $\displaystyle\ldots$

In the original CCS approach, one data point $i$ is given by a binary yes-no
question. Adapted to ranking, we denote a ranking task with $i$ and index its
$N$ items with $n$. Since we never compare items between different ranking
tasks, we omit the $i$ index for simplicity. Now, the probing model
$f_{\theta}$ assigns a ranking score
$s_{n}=\sigma(\bm{\theta}^{T}\bm{x}_{n}+b)$ directly to each item $x_{n}$. The
scores $s_{n}$ can then be paired with the origCCS objective resulting in
“origCCS (S)”.

However, the origCCS loss enforces a hard binary decision, while an important
property of rankings is that the distances between items do not have unit
length. This “ordinal property” is typically reflected by some notion of
“margin” in existing ranking objectives such as the Max-Margin and Triplet
Loss. To incorporate this, we propose the MarginCCR loss which represents a
modification of the well-known Max-Margin loss.

$\displaystyle\min\bigg{(}$
$\displaystyle\max\Big{(}0,\big{(}f_{\theta}({\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}\bm{x}_{n}^{A}})-f_{\theta}({\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}\bm{x}_{n}^{B}})\big{)}+m\Big{)},$
(4)
$\displaystyle\max\Big{(}0,\big{(}f_{\theta}({\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}\bm{x}_{n}^{B}})-f_{\theta}({\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}\bm{x}_{n}^{A}})\big{)}+m\Big{)}\bigg{)}$

MarginCCR enforces that
${\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}x_{n}^{A}}$
ranks higher or lower than
${\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}x_{n}^{B}}$
by at least a margin $m$, which can be seen as a _confidence_ property.
However, since there are no labels, the probe has to figure out whether
scoring
${\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}x_{n}^{A}}$
higher or lower than
${\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}x_{n}^{B}}$
yields better _consistency_ and reduces the loss across all item pair
permutations.

In a similar style, we can adapt the popular Triplet Loss to TripletCCR. To
simplify notation, we denote the distance
$|f_{\theta}({\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}\bm{x}_{n}^{A}})-f_{\theta}({\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}\bm{x}_{n}^{B}})|$
between two items
${\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}x_{n}^{A}}$
and
${\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}x_{n}^{B}}$
as
$d({\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}x_{n}^{A}},{\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}x_{n}^{B}})$
and compute TripletCCR according to:

$\displaystyle\min\Big{(}$
$\displaystyle\max\big{(}0,d({\color[rgb]{0.0390625,0.5234375,0.00390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.5234375,0.00390625}x_{n}^{C}},{\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}x_{n}^{A}})-d({\color[rgb]{0.0390625,0.5234375,0.00390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.5234375,0.00390625}x_{n}^{C}},{\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}x_{n}^{B}})+m\big{)},$
$\displaystyle\max\big{(}0,d({\color[rgb]{0.0390625,0.5234375,0.00390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.5234375,0.00390625}x_{n}^{C}},{\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}x_{n}^{B}}))-d({\color[rgb]{0.0390625,0.5234375,0.00390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.5234375,0.00390625}x_{n}^{C}},{\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}x_{n}^{A}})+m\big{)}\Big{)}$

In simple words, the objective forces the “positive item” to be closer to a
third item
${\color[rgb]{0.0390625,0.5234375,0.00390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.5234375,0.00390625}x_{n}^{C}}$,
referred to as “anchor”, than a “negative item”, plus a _confidence_ margin
$m$. Yet, this is enforced without knowing which item should be labeled as
“positive” and “negative”. Instead, the probe is trained to make this decision
by being _consistent_ across all items in a given ranking task. In the
following, we refer to both presented methods as “MarginCCR (S)” and
“TripletCCR (S)” and provide further technical details on batching and
normalization in App. A.

###  3.3 Listwise CCR Probing

Pairwise and pointwise methods are not guaranteed to yield transitivity-
consistent rankings: item A may win over B, B may win over C, yet C may win
over A, creating a circular ordering (Cao et al., 2007). To tackle this
shortcoming, we design a listwise probing method with a loss objective that
considers all items at the same time. Various existing ordinal regression
methods are based on binary classifiers (Li and Lin, 2006; Niu et al., 2016;
Shi et al., 2021), making them a natural candidate for a CCS-style objective
that does not require additional parameters. These methods often rely on the
extended binary representation (Li and Lin, 2006) of ordered classes, where,
for instance, rank $k=3$ out of $K=4$ would be represented as $[1,1,1,0]$, as
illustrated on the right side of Fig. 2.

We first obtain a vector representation $\bm{x}_{n}$ of item $x_{n}$ using the
ItemSingle prompt type. Next, we consider the Consistent Rank Logits (CORAL)
model (Cao et al., 2020), which offers guarantees for rank-monotonicity by
training a probe $f_{\theta,k}$ to map $\bm{x}_{n}$ to one of $K$ ranks. The
probe consists of the weight vector $\bm{\theta}^{T}$ and $K$ separate bias
terms $b_{k}$ to assign a rank score $s^{k}_{n}$ according to
$s^{k}_{n}=f_{\theta,k}(\bm{x}_{n})=\sigma(\bm{\theta}^{T}\bm{x}_{n}+b_{k})$.
In essence, for each item $n$, the CORAL probe outputs a vector of $K$ scores.
Scores are monotonically decreasing because the bias terms $b_{k}$ are clipped
to be monotonically decreasing as $k$ grows larger. Predicting a rank in the
extended binary representation thus comes down to
$\hat{k}=1+\sum_{k=1}^{K}\mathds{1}[s^{k}>0.5]$.

Figure 2: We translate the two aspects of _consistency_ and _confidence_ from
the binary CCS objective to an ordinal multi-class setting resulting in
OrdRegCCR.

In a listwise approach, all $N$ items are to be jointly considered and
assigned a rank $k$.222We note that the number of ranks $K$ equals the number
of items $N$, but keep both letters for notation simplicity. The predicted
scores can thus be represented as a square $N\times K$ matrix as displayed in
Fig. 2. We enforce a unique rank assignment via an unsupervised ordinal
regression objective, which we term OrdRegCCR:

$\displaystyle\overbrace{\sum_{k}^{K-1}\Big{(}\big{(}K-(k-1)\big{)}-\sum_{n}^{N}s^{k}_{n}\Big{)}}^{\text{\emph{consistency}}}+$
$\displaystyle\underbrace{\sum_{n}^{N}\sum_{k}^{K}\min\Big{(}s^{k}_{n},\big{(}1-s^{k}_{n}\big{)}\Big{)}}_{\text{\emph{confidence}}}$
(5)

For a ranking of $K=4$ items, the _consistency_ term encourages each column to
sum up to $4$, $3$,…, $1$ respectively, as visualized in Fig. 2. Yet, to avoid
a deficient solution, the _confidence_ term enforces each score towards either
$0$ or $1$.

When applying this “OrdRegCCR (S)” approach, there are two difficulties to
overcome. First, we require the number of parameters of the probing model to
be the same across different approaches to ensure a fair comparison. Second,
we prefer training a probing model whose parameters are independent from the
number of items of a given ranking task. To mitigate both issues, we
parametrize the $K$ bias terms via a polynomial function. In turn, this
function is parametrized by only two parameters, $\alpha$ and $\beta$, which
are optimized during training.

| dataset | tasks | items | ranking example
---|---|---|---|---
fact-based | SynthFacts | 2 | 6.00 |  | criterion: order the numbers by cardinality
---
items: {1, 10, 100, 1000…}
ScalarAdj | 38 | 4.47 |  | criterion: order the adjectives by semantic intensity
---
items: {small, smaller, tiny, microscopic…}
WikiLists | 14 | 14.43 |  | criterion: order the countries by size
---
items: {Russia, Canada, China, United States…}
context-based | SynthContext | 2 | 6.00 |  | context: “Tom owns $100, Jenny has $1000,…”
---
items: {Tom, Jenny, Emily, Sam…}
criterion: order entities by wealth
EntSalience | 362 | 7.5 |  | context: “The UN secretary met with climate activists…”
---
items: {UN secretary, climate activists, US government…}
criterion: order the entities by salience in the given text
Table 3: Overview of datasets, their number of ranking tasks, and the average
number of items per task. We consider datasets that require knowledge of facts
(fact-based) and in-context reasoning (context-based). Figure 3: Pairwise and
listwise results of the prompting and CCR probing methods for the DeBERTa,
GPT-2, and MPT-7B model, averaged over all fact-based and context-based
learning datasets. Results show mean and standard deviation over $5$ runs. We
find that CCR probing outperforms prompting for the same-size model. Among the
CCR probing methods, TripletCCR is the best-performing. Orange bars represent
ceilings of a supervised probe trained and tested on the same ranking task.

##  4 Experimental Design

###  4.1 Language Models

We evaluate the prompting and CCR probing methods on an encoder-only and a
decoder-only model. For the encoder-only model, we choose deberta-v1-base (He
et al., 2021) which has $100$ million parameters and is the best-performing
encoder-only model for answering yes-no questions in the original CCS paper.
For the decoder-only model, we consider GPT-2 (small) (Jiang et al., 2021)
which has $124$ million parameters. We compare these models against prompting
results achieved with a much bigger, $7$ billion parameter MPT-7B (MosaicML,
2023) model.

###  4.2 Ranking Task Datasets

We consider “fact-based” and “context-based” ranking tasks. Solving “fact-
based” ranking tasks depends mostly on world knowledge. All datasets,
displayed in Table 3, are publicly available and we discard all ranking tasks
with fewer than four items and those that include ties between items.

#### Fact-based Ranking Tasks.

SynthFacts: We manually conceive two synthetic ranking tasks with six items
each. One task asks to rank the adjectives “horrible, bad, okay, good, great,
awesome” based on sentiment, and the other to rank numbers based on their
cardinality. ScalarAdj: We consider rankings of scalar adjectives based on de
Melo and Bansal (2013) and curated by Garí Soler and Apidianaki (2020)
adjectives that are ordered by their semantic intensity, e.g., “small,
smaller, tiny”. WikiLists: We manually ensemble $14$ rankings that pertain to
constant (e.g., countries ordered by size) or changing (e.g., countries
ordered by GDP) facts using Wikipedia as a reference.

#### In-Context Ranking Tasks.

SynthContext: Analogously to SynthFacts, we design two synthetic in-context
ranking tasks. The first concerns ranking colors by popularity, where the
popularity is unambiguously stated in a prepended context. The second task is
about ordering entities by their wealth, as described in context. EntSalience:
As another in-context ranking task, we consider the Salient Entity Linking
(SEL) task (Trani et al., 2016). Given a news passage, we ask the model to
rank the mentioned entities by salience.

###  4.3 Evaluation Metrics

We are considering pairwise, pointwise, and listwise approaches as displayed
in Table 1. This means we need to convert pairwise results to a listwise
ranking and vice versa and consider evaluation metrics for both pairwise and
listwise results. Following the original CCS method, our evaluation is
direction-invariant as further discussed in Appendix A. In essence, the
ranking $A>B>C$ is considered the same as $C>B>A$.

#### Pairwise Metric and Ranking Conversion.

We rely on accuracy to evaluate pairwise comparisons. To account for
direction-invariance, we reverse the predicted order if the reverse order
yields better results. This leads to a baseline accuracy of $50$%. For
aggregating pairwise results into a listwise ranking, we follow Qin et al.
(2023): if an item wins a pairwise comparison it gains a point and points are
summed to obtain a ranking. If the sum of wins is tied between items, we break
the tie by considering the sum of the items’ scores for all comparisons.

#### Ranking Metric and Pairwise Conversion.

To evaluate rankings, we consider Kendall’s tau correlation, which is
independent of the number of items per ranking task and the directionality of
the ordering. These desiderata are not given by other ranking and retrieval
metrics such as the Normalized Discounted Cumulative Gain (NDCG) (Wang et al.,
2013). We derive pairwise comparisons from a ranking by permuting any two
items and labeling the pairs based on their position in the ranking.

###  4.4 Supervised Ceilings

The prompting as well as CCR probing approaches can all be applied zero-shot
without a train-test split, which is infeasible for supervised probing. As an
alternative, we simply use the same ranking task for training and testing a
supervised probe. The performance of this probe indicates a performance upper
bound of what can possibly be extracted given the difficulty of a task and the
prompt design. For instance, if a prompt is entirely random, a supervised
probe trained and tested on the same ranking task would not be able to
discriminate between different items. We rely on the unaltered loss functions,
e.g., Binary Cross-Entropy instead of origCCS, Max-Margin loss instead of
MarginCCR, for training the supervised probes (see Fig. 5 for an overview).

###  4.5 Results

For ease of evaluation, Fig. 3 presents the mean results over all datasets
containing either fact-based or context-based ranking tasks. The plot presents
the mean results and their standard deviation over $5$ runs. All individual
results are provided in Fig. 6 from Appendix A. Most importantly, we find that
CCR probing outperforms prompting for the same model. Among the CCR probing
methods, TripletCCR is the best performing approach across all models and
datasets. The orange dashed lines represent the supervised ceilings for each
of the CCR probing approaches as motivated in § 4.4. Interestingly, Triplet
Loss does not have the highest upper bound. Between the fact-based and
context-based datasets, CCR probing and prompting performance drops overall,
but more for the much smaller encoder-only DeBERTa than for the other models.
When considering the listwise metric, our results confirm that listwise
prompting is inferior to pairwise and, surprisingly, also to pointwise
prompting (Qin et al., 2023; Liusie et al., 2023). However, pairwise methods
(P symbol) are also computationally more expensive, making CCR probing even
more favorable. For pairwise methods, we observe a discrepancy between the
pairwise and listwise results. This stems from the fact that pairwise methods
are more fault-tolerant—some of the pairwise comparisons may be erroneous,
but, in aggregate, the resulting ranking can still be correct. Similarly, we
observe that listwise approaches (L) are generally more volatile, possibly due
to more difficult calibration, positional biases (Han et al., 2023; Wang et
al., 2023), and low fault-tolerance—listwise approaches directly return a
single ranking.

##  5 Discussion

To scrutinize our results, we explore settings with a train-test split, and
discuss interpretability considerations of CCR probing.

#### Ranking Direction across Tasks.

Instead of training our probes on a single ranking task, we train them on a
training set of multiple rankings and evaluate on a held-out set. To this end,
we use $4$-fold cross-validation, which allows comparing CCR probing against
supervised probing in a fair setup. This setup is more similar to the
experiments in the original CCS paper (Burns et al., 2023) and thus rests on a
similar hypothesis: is there are a more universal “ranking direction” in the
activations of a language model that holds across ranking tasks? Fig. 5 in
Appendix A presents the results of this k-fold validation experiment. First,
our probes identify ranking properties that exist across different ranking
tasks. This particularly holds for ranking tasks that resemble each other more
closely as in ScalarAdj. Second, CCR probing does not fall far behind
supervised probing. Since this is especially evident for datasets with fewer
ranking tasks, we hypothesize that CCR probing is less likely to overfit and
instead exploits general ranking properties.

#### Interpretability.

Besides performance, another argument for CCR probing is control and post-hoc
interpretability offered by the parametric probe. For instance, in Fig. 4 we
plot the scores $s_{n}=\sigma(\bm{\theta}^{T}\bm{x}_{n}+b)$ for each item
yielded by the probe trained with TripletCCR. This allows us to inspect the
distances between items projected onto the latent ranking scale.

Figure 4: CCR probing offers interpretability benefits such as the post-hoc
analysis of the probe’s parameters.

##  6 Related Work

Pairwise and listwise prompting has been explored on different tasks (Ma et
al., 2023; Lee and Lee, 2023; Liusie et al., 2023), but is most frequently
focused on document retrieval (Ferraretto et al., 2023). Pairwise (RankNet)
(Burges et al., 2005) and listwise (ListNet) (Cao et al., 2007) ranking
approaches have also been compared outside of language model prompting. We
additionally explore pointwise prompting and find that, other than expected,
pointwise often outperforms listwise prompting. To move beyond prompting, we
propose an expansion of the Contrast-Consistent Search (CCS) (Burns et al.,
2023) method to rankings. Recent work explores calibrated versions of CCS (Tao
et al., 2023) and adapting CCS to order-invariant, multi-class settings
(Zancaneli et al., 2023). Our CCR probing approach is strongly influenced by
unsupervised ranking (Frydenlund et al., 2022) and probing of semantic axes
(Garí Soler and Apidianaki, 2020; Li et al., 2022b; Engler et al., 2022;
Stoehr et al., 2023a, b).

##  7 Conclusion

We analyze the ranking capabilities of language models by comparing pairwise,
pointwise, and listwise prompting techniques and find that the latter is most
susceptible to mistakes. We then propose an unsupervised probing method termed
Contrast-Consistent Ranking (CCR) and find that, for the same model, CCR
probing improves upon prompting. CCR learns an affine mapping between a
language model’s activations and a model-inherent ranking direction. On a more
abstract level, we relate multiple language model queries through a surrogate
model that projects the language model’s outputs to a shared ranking scale.

The direction-invariance of both CCS and CCR poses a potential limitation that
may be lifted by future work as further outlined in Appendix A. In particular
for pointwise and listwise prompting, omitting the direction of a desired
ranking can hurt performance. The language model may be confused whether to
rank the highest or lowest item first, leading the items’ corresponding scores
to cannibalize each other.

Since we do not consider a train-validation-test set split, we refrain from
hyperparameter-tuning (e.g., margins, learning rate, sub-batching, probe
initialization). However, based on initial prototyping, we see performance
boosts for CCR when tuning these hyperparameters. Other promising directions
for future work are testing CCR probing with larger language models, lifting
the direction-invariance of both CCS and CCR (Appendix A), and experimenting
with more expressive probes.

## Acknowledgments

We would like to thank Ozan Irsoy, Atharva Tendle, Faner Lin, Umut Topkara,
Ziyun Zhang, Ashim Gupta, Suchin Gururangan, Nikita Soni and the entire
Bloomberg AI Group for valuable discussions and feedback on the manuscript.
Moreover, we would like to express special thanks to Kevin Du and Luca Beurer-
Kellner from ETH Zürich for early-stage discussions and initial prototyping.

## References

  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901.
  * Burges et al. (2005) Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. 2005.  Learning to rank using gradient descent.  In _Proceedings of the 22nd International Conference on Machine Learning_ , pages 89–96.
  * Burns et al. (2023) Collin Burns, Haotian Ye, Dan Klein, and Jacob Steinhardt. 2023.  Discovering latent knowledge in language models without supervision.  In _International Conference on Learning Representations_.
  * Cao et al. (2020) Wenzhi Cao, Vahid Mirjalili, and Sebastian Raschka. 2020.  Rank consistent ordinal regression for neural networks with application to age estimation.  _Pattern Recognition Letters_ , 140.
  * Cao et al. (2007) Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li. 2007.  Learning to rank: From pairwise approach to listwise approach.  In _International Conference on Machine Learning_ , pages 129–136. ACM.
  * de Melo and Bansal (2013) Gerard de Melo and Mohit Bansal. 2013.  Good, great, excellent: Global inference of semantic intensities.  _Transactions of the Association for Computational Linguistics_ , 1:279–290.
  * Engler et al. (2022) Jan Engler, Sandipan Sikdar, Marlene Lutz, and Markus Strohmaier. 2022.  SensePOLAR: Word sense aware interpretability for pre-trained contextual word embeddings.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 4607–4619, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Ferraretto et al. (2023) Fernando Ferraretto, Thiago Laitz, Roberto Lotufo, and Rodrigo Nogueira. 2023.  Exaranker: Explanation-augmented neural ranker.  _arXiv_ , 2301.10521.
  * Frydenlund et al. (2022) Arvid Frydenlund, Gagandeep Singh, and Frank Rudzicz. 2022.  Language modelling via learning to rank.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 36\.
  * Garí Soler and Apidianaki (2020) Aina Garí Soler and Marianna Apidianaki. 2020.  BERT knows Punta Cana is not just beautiful, it’s gorgeous: Ranking scalar adjectives with contextualised representations.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7371–7385.
  * Han et al. (2023) Zhixiong Han, Yaru Hao, Li Dong, Yutao Sun, and Furu Wei. 2023.  Prototypical calibration for few-shot learning of language models.  _International Conference on Learning Representations_.
  * He et al. (2021) Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. 2021.  DeBERTa: Decoding-enhanced BERT with disentangled attention.  _International Conference on Learning Representations_.
  * Jiang et al. (2021) Zhengbao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. 2021.  How can we know when language models know? On the calibration of language models for question answering.  _Transactions of the Association for Computational Linguistics_ , 9:962–977.
  * Kingma and Ba (2015) Diederik Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations_ , page 337.
  * Lee and Lee (2023) Bruce W. Lee and Jason Lee. 2023.  Prompt-based learning for text readability assessment.  In _Findings of the Association for Computational Linguistics: EACL 2023_ , pages 1819–1824, Dubrovnik, Croatia. Association for Computational Linguistics.
  * Li et al. (2022a) Jiaoda Li, Ryan Cotterell, and Mrinmaya Sachan. 2022a.  Probing via prompting.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1144–1157.
  * Li et al. (2023) Kenneth Li, Oam Patel, Fernanda Viégas, Hanspeter Pfister, and Martin Wattenberg. 2023.  Inference-time intervention: Eliciting truthful answers from a language model.  _arXiv_ , 2306.03341.
  * Li and Lin (2006) Ling Li and Hsuan-tien Lin. 2006.  Ordinal regression by extended binary classification.  In _Advances in Neural Information Processing Systems_.
  * Li et al. (2022b) Lucy Li, Divya Tadimeti, and David Bamman. 2022b.  Discovering differences in the representation of people using contextualized semantic axes.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_.
  * Liusie et al. (2023) Adian Liusie, Potsawee Manakul, and Mark J. F. Gales. 2023.  Zero-shot NLG evaluation through pairware comparisons with LLMs.  _arXiv_ , 2307.07889.
  * Ma et al. (2023) Xueguang Ma, Xinyu Zhang, Ronak Pradeep, and Jimmy Lin. 2023.  Zero-shot listwise document reranking with a large language model.  _arXiv_ , 2305.02156.
  * MosaicML (2023) NLP Team MosaicML. 2023.  MPT-7B Language Model.
  * Niu et al. (2016) Zhenxing Niu, Mo Zhou, Le Wang, Xinbo Gao, and Gang Hua. 2016.  Ordinal regression with multiple output CNN for age estimation.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4920–4928.
  * Petroni et al. (2019) Fabio Petroni, Tim Rocktäschel, Sebastian Riedel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander Miller. 2019.  Language models as knowledge bases? In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_ , pages 2463–2473.
  * Pimentel et al. (2022) Tiago Pimentel, Josef Valvoda, Niklas Stoehr, and Ryan Cotterell. 2022.  The architectural bottleneck principle.  In _Conference on Empirical Methods in Natural Language Processing (EMNLP)_.
  * Qin et al. (2023) Zhen Qin, Rolf Jagerman, Kai Hui, Honglei Zhuang, Junru Wu, Jiaming Shen, Tianqi Liu, Jialu Liu, Donald Metzler, Xuanhui Wang, and Michael Bendersky. 2023\.  Large language models are effective text rankers with pairwise ranking prompting.  _arXiv_ , 2306.17563.
  * Shi et al. (2021) Xintong Shi, Wenzhi Cao, and Sebastian Raschka. 2021.  Deep neural networks for rank-consistent ordinal regression based on conditional probabilities.  _Pattern Analysis and Applications_ , 26.
  * Stoehr et al. (2023a) Niklas Stoehr, Ryan Cotterell, and Aaron Schein. 2023a.  Sentiment as an ordinal latent variable.  In _Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics_.
  * Stoehr et al. (2023b) Niklas Stoehr, Benjamin J. Radford, Ryan Cotterell, and Aaron Schein. 2023b.  The Ordered Matrix Dirichlet for state-space models.  In _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_.
  * Tao et al. (2023) Lucas Tao, Holly McCann, and Felipe Calero Forero. 2023.  Calibrated contrast-consistent search.  _Stanford CS224N Custom Project_.
  * Trani et al. (2016) Salvatore Trani, Diego Ceccarelli, Claudio Lucchese, Salvatore Orlando, and Raffaele Perego. 2016.  SEL: A unified algorithm for entity linking and saliency detection.  In _Proceedings of the 2016 ACM Symposium on Document Engineering_ , pages 85–94. ACM.
  * Wang et al. (2023) Peiyi Wang, Lei Li, Liang Chen, Dawei Zhu, Binghuai Lin, Yunbo Cao, Qi Liu, Tianyu Liu, and Zhifang Sui. 2023.  Large language models are not fair evaluators.  _arXiv_ , 2305.17926.
  * Wang et al. (2013) Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Tie-Yan Liu, and Wei Chen. 2013.  A Theoretical Analysis of NDCG Type Ranking Measures.  _COLT_.
  * Zancaneli et al. (2023) Diego Zancaneli, Santiago Hernández, and Tomás Pfeffer. 2023.  Adapting the contrast-consistent search method to multiclass classification.  _Stanford CS224N Custom Project_.
  * Zhao et al. (2021) Tony Z. Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. 2021.  Calibrate before use: Improving few-shot performance of language models.  _International Conference on Machine Learning_.

##  Appendix A Appendix

#### Direction-invariance of CCS and CCR.

We limit the scope of this work to direction-invariant rankings: i.e., the
ranking $A>B>C$ is considered to be the same as $C>B>A$. This assumption
aligns well with the original Contrast-Consistent Search (CCS) method (Burns
et al., 2023). In CCS, the probe is trained to map statements and their
negation to either a $0$ or $1$ pole consistently across multiple paired
statements. However, it is not defined a priori which of the two poles
corresponds to all truthful and all false statements. We argue that this is
even less a shortcoming for CCR than it is for CCS. While the meaning of the
poles, “true” versus “false” for CCS, “high rank” versus “low rank” for CCR,
need to be interpreted post-hoc, the ordering of items obtained with CCR can
be directly read off. With origCCS, the probe predicts the label of a new
statement according to:

$\displaystyle
s_{i}=\frac{1}{2}\Big{(}f_{\theta}({\color[rgb]{0,0,0.6015625}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.6015625}\bm{x}_{i}^{+}})-\big{(}1-f_{\theta}({\color[rgb]{0.87890625,0.5234375,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.5234375,0.0078125}\bm{x}_{i}^{-}})\big{)}\Big{)}$
(6)

In the case of MarginCCR, TripletCCR, and OrdRegCCR, the probe directly
predicts a ranking score $s_{n}$, because items are represented by individual
vectors via the ItemSingle prompt type.

#### Technical Details.

In all CCR probing setups, we dynamically set the batch size to the number of
items of a ranking task. For the pairwise approaches, we perform sub-batching
with two items at a time. For the approaches based on ItemSingle, we Z-score
normalize all vector representations in a batch. We set the margin $m=0.2$ and
include an additional positive margin term in TripletCCR to avoid having the
anchor and positive item collapse to the same value. We train all supervised
and unsupervised probes using the Adam optimizer (Kingma and Ba, 2015) with
its default settings for $200$ epochs.

Figure 5: K-fold cross-validation results comparing unsupervised CCR probing
and supervised probing. Figure 6: Mean ranking results and standard deviation
for all methods and datasets over $5$ runs.