# Fair Ranking with Distribution-free Risk Control

###### Abstract

Learning to Rank (LTR) methods are essential for influential applications such
as search and recommendation systems, playing a critical role in online
economies and impacting not only users but also people behind the items (e.g.,
sellers and content providers). Therefore, it is crucial to guarantee the
fairness in ranking systems such that items are allocated with exposure
proportional to their relevance. The widely used traditional deterministic
ranking systems can result in an unfair distribution of exposure to items,
especially when they predict slightly different ranking scores for items
sharing the same merit. While the Plackett-Luce (PL) model have been
incorporated to stochastic ranking systems to address these fairness issues,
they present significant drawbacks such as computational costliness and lack
of performance guarantees. To tackle these limitations, we introduce a novel
post-hoc model-agnostic method, Fair Learning to Rank with Distribution-free
Risk Control (FairLTR-RC). The proposed method can create a stochastic ranking
system using any pre-existing scoring function, without requiring expensive
training, and can provide guarantees on a specified metric based on
distribution-free risk control. Our approach incorporates a novel partially
stochastic ranking model, the Thresholded PL (TPL) model, to effectively
balance utility and fairness. Experimental results on various benchmark
datasets demonstrate that our method significantly enhances fairness in
widely-used scoring functions, outperforming state-of-the-art stochastic
ranking systems while providing a predefined level of utility. This represents
a significant step forward in the field of fair LTR, with potential for broad
real-world application.

##  1 Introduction

Learning to rank (LTR) relies on machine learning to optimize rankings of
items in applications such as search and recommendation [chapelle2011yahoo,
liu2009learning]. LTR models play a vital role in online multi-sided economies
involving users, item providers and the platform (e.g., e-commerce website),
where they have impact on the exposure of items. They are influential on the
economic outcomes of entities such as sellers, job candidates, and content
creators [ramanath2018towards, pei2019personalized].

A LTR model is typically composed of two components. The first component is a
scoring function. Given a query and a set of potential items to be recommened,
it predicts ranking scores for these items based on the predicted relevance to
the user’s query. The second component is a ranking model, which generates a
ranking list of products using the scores from stage 1. Traditional LTR models
generally employ deterministic ranking models, such as sorting items in
accordance to their ranking scores.

Given the growing impact of LTR on online platforms, the demands for fair
allocation of exposure among items [singh2019policy, morik2020controlling,
oosterhuis2021computationally, diaz2020evaluating] has significantly
increased. In current literature, fair allocation dictates that the exposure
of an item in ranked lists should be proportional to its relevance to the
query. However, deterministic ranking models can often result in unfair
distribution of exposure. For instance, with a pretrained scoring function
that is not 100% accurate, two products with identical relevance can have
slightly different ranking scores. With deterministic ranking models, this
would result in severely unequal allocation of exposure as the item with
higher ranking score will always be ranked at the a higher position
[singh2019policy].

In response to the inherent issue of deterministic LTR models w.r.t. exposure-
based fairness, there has been a shift towards stochastic LTR models. One such
representive incorporates the Plackett-Luce (PL) ranking model
[plackett1975analysis]. The PL ranking model predicts a distribution of
ranking lists based on ranking scores. Thie enables us to sample multiple
ranking lists from it, this significantly improving exposure fairness,
especially in cases where multiple items have slightly different scores but
the same relevance [singh2019policy].

However, challenges arise when integrating scoring functions from
deterministic models into the PL model, as they are not designed to optimize
the expected performance under predicted ranking distributions. In addition,
training scoring functions with the PL model is computationally intensive,
requiring computing gradients from numerous sampled ranking lists. Finally,
the lack of guarantees on ranking performance when we replace deterministic
LTR models with the existing stochastic ones presents a significant obstacle
to their widespread adoption in real-world applications.

To address these challenges, we present Fair Learning to Rank with
Distribution-free Risk Control (FairLTR-RC), a post-hoc, model-agnostic
approach for exposure-based fairness in LTR. By incorporating the framework of
conformal prediction [angelopoulos2021gentle, bates2021distribution,
angelopoulos2021learn, angelopoulos2022recommendation] into the LTR setting.
Our proposed method incorporates a novel partially stochastic ranking model –
Thresholded PL (TPL) ranking model, which offers a delicate trade-off between
fairness and utility in a post-hoc manner. TPL can work with pretrained
scoring function from deterministic LTR models. This circumvents the expensive
training needed by existing stochastic LTR models. In addition, FairLTR-RC
provides theoretically supported finite-sample guarantees, assuring a
specified performance level even under constrained data settings. and utility
by ensuring the utility of our LTR models will not fall below a predetermined
threshold.

The contributions of this paper are as follows:

  * [itemsep=0pt]

  * •

First, we propose FairLTR-RC, a post-hoc, model-agnostic method that
efficiently transforms pre-trained scoring functions from deterministic LTR
models, into stochastic ones this avoiding expensive training procedures.

  * •

Second, our method extends distribution-free risk control to LTR. FairLTR-RC
achieves a specified level of utility with high probability, despite its
stochastic nature.

  * •

Third, extensive experimental results on popular LTR datasets show that
FairLTR-RC enhances fairness of various scoring functions (CatBoost
[prokhorenkova2018catboost], LightGBM [ke2017lightgbm], and Neural Networks)
pretrained with deterministic ranking models, while maintaining the specified
level of utility.

##  2 Preliminaries

In this section, we begin by outlining the notation used throughout the paper.
Next, we provide a formal definition of a LTR model, which consists of a
scoring function and a ranking model. Following that, we introduce definitions
for utility and exposure-based fairness measures within the context of
Learning to Rank (LTR). Lastly, we conclude this section by presenting our
problem statement.

Notations. For a query $q$, there exists $n_{q}$ candidate documents
$\mathcal{D}^{q}=\\{d_{1}^{q},...,d_{n_{q}}^{q}\\}$ to be ranked. Each
document $d_{i}^{q}$ is described by a tuple
$(\mathbf{x}_{i}^{q},\rho(d_{i}^{q}))$, where the feature vector
$\mathbf{x}_{i}^{q}\in\mathcal{X}$ describes the item and its relationship to
the query $q$. For example, features used in e-commerce search can include the
price of the item and the average price of items clicked from the query. And
$\rho(d_{i}^{q})$ is the relevance of document $d_{i}^{q}$ annotated by human
experts. We assume that the relevance is given for each item corresponding to
the queries in the training, validation and calibration set, but unknown for
the test set. For simplicity of notation, we will omit the subscript $i$ and
the superscript $q$ when they are not necessary. A top-K ranking
$\mathbf{y}=[y_{1},...,y_{K}]\in\mathcal{Y}$ is a sorted list of $K$ items,
where $y_{k}=d$ means item $d$ is ranked at the $k$-th position in
$\mathbf{y}$, where $\mathcal{Y}$ is the space of permutations. Let
$\mathbf{y}_{1:k}$ be the sublist including first $k\leq K$ elements of
$\mathbf{y}$.

Scoring Function and Ranking Model. Here, we formally define the scoring
function and the ranking model of a LTR model. First, given query $q$ and its
item set $\mathcal{D}^{q}$, a scoring function
$f:\mathcal{X}\rightarrow\mathbb{R}$ maps the feature vectors of each item $d$
to its ranking scores $s(d)$. In this work, we assume that the scoring
function $f$ is fixed and ranking scores $s(d)$ are given for
$d\in\mathcal{D}^{q}$. Second, a ranking model
$\pi:\mathbb{R}^{n_{q}}\times\mathcal{Y}\rightarrow[0,1]$ which maps the
scores of all items in $\mathcal{D}^{q}$ and a ranking $\mathbf{y}$ to its
probability to be sampled. Thus, a ranking model
$\pi(\\{s(1),...,s(n_{q})\\},\mathbf{y})$ predicts a distribution of rankings
for each query $q$. For simplicity of notations, we denote the predicted
distribution of rankings for query $q$ as $\pi^{q}(\mathbf{y})$. Then, a
deterministic LTR model comes with $\pi^{q}(\mathbf{y})=1$ for a certain
ranking $\mathbf{y}$, and $\pi^{q}(\mathbf{y}^{\prime})=0$ for
$\mathbf{y}^{\prime}\neq\mathbf{y}$. While a stochastic model can have
$\pi^{q}(\mathbf{y})>0$ for multiple different rankings $\mathbf{y}$.

The PL ranking model is adopted for improving exposure-based fairness
singh2019policy,diaz2020evaluating,oosterhuis2021computationally . PL models
predict a distribution of rankings for fairer allocation of exposure among
items.

Given query $q$ and the set of items $\mathcal{D}^{q}$, their ranking scores
$s(d),d\in\mathcal{D}^{q}$, and the sampled items for positions $1,...,k-1$,
denoted by $\mathbf{y}_{1:k-1}$, the PL ranking model plackett1975analysis
samples an item $d$ for position $k$ from
$\pi_{PL}(\mathbf{y})=\prod_{k=1}^{K}p_{PL}(d|\mathbf{y}_{1:k-1})$ with:

$\begin{split}p_{PL}(d|\mathbf{y}_{1:k-1})=\frac{\mathds{1}(d\not\in\mathbf{y}_{1:k-1})\exp(s(d)/\tau)}{\sum_{d^{\prime}\in\mathcal{D}^{q}\setminus\mathbf{y}_{1:k-1}}\exp(s(d^{\prime})/\tau)},\end{split}$
(1)

where $\tau$ is the temperature. However, training such stochastic LTR models
is expensive, which requires sampling at least $100$ ranking lists for each
query oosterhuis2021computationally,bruch2020stochastic,singh2019policy and
compute gradients of model parameters based on these samples.

Utility and Fairness Metrics. Given the definitions above, here, we define the
utility and exposure-based fairness for a LTR model. In LTR, the ultility
function considers the ranking of each item by weighting each position $k$
with weight $\theta_{k}$. The utility of a ranking model $\pi$ on query $q$
can be defined as [oosterhuis2021computationally]:

$U^{q}(\pi)=\sum_{\mathbf{y}\in\mathcal{Y}}\pi^{q}(\mathbf{y})\sum_{k=1}^{K}\theta_{k}\cdot\rho(y_{k}),$

which leads to the overall utility $U(\pi)=\mathbb{E}_{q}[U^{q}(\pi)]$. If we
choose $\theta_{k}=\frac{\mathds{1}[k\leq K]}{\log_{2}(1+k)}$, then $U(\pi|q)$
is DCG@K. Let iDCG@k be the maximal DCG@k for a given query $q$ at position
$k$, then $U^{q}(\pi)$ is NDCG@K if $\theta_{k}=\frac{\mathds{1}[k\leq
K]}{\log_{2}(1+k)\times\text{iDCG@k}}$, which measures the normalized exposure
of items ranked at position $k$. In this work, we consider bounded utility
function$U^{q}(\pi)\in[0,1]$. Thus, the utility risk to be controlled is
$R_{util}(\pi)=1-U(\pi)$, e.g., $1-\text{NDCG@K}$.

Fairness in ranking deals with the allocation of exposure over items. Exposure
measures the probability of users to examine a certain position. The widely
used utility metric NDCG@K is based on the logarithmic reduction of exposure
proportional to the position. To measure item exposure fairness, we first
define exposure of item $d$ under the ranking model $\pi$ as

$\mathcal{E}^{q}(d;\pi)=\sum_{\mathbf{y}}\pi^{q}(\mathbf{y})\sum_{k=1}^{K}\theta_{k}\cdot\mathds{1}[y_{k}=d],$

where $\mathds{1}[y_{k}=d]\theta_{k}$ is the exposure of item $d$ in the
ranking $\mathbf{y}$. Intuitively, it measures the mean exposure of item $d$
in the rankings sampled from the predicted distribution $\pi^{q}(\mathbf{y})$.
Let $\mathcal{E}(d)$ denote $\mathcal{E}^{q}(d;\pi)$ when $q$ and $\pi$ can be
dropped. Based on this, we can define a disparity measure for exposure-based
fairness in ranking.

Exposure-based Fairness in Ranking
biega2018equity,singh2019policy,oosterhuis2021computationally. In this work,
we focus on fair allocation of exposures to items. Singh and Joachims
singh2019policy first propose a fairness notion: the exposure of an item
$\mathcal{E}(d)$ should be proportional to its relevance $\rho(d)$. They
compute the average difference of the exposure-relevance ratio
$\frac{\mathcal{E}(d)}{\rho(d)}-\frac{\mathcal{E}(d^{\prime})}{\rho(d^{\prime})}$
between each pair of items for each query. Oosterhuis
oosterhuis2021computationally proposes a variant of this disparity metric,
which handlew the cases for the items with $0$ relevance but was ranked in
top-K. Given the ranking model $\pi$, the disparity measure for exposure-based
fairness is defined as oosterhuis2021computationally, singh2019policy

$R_{fair}^{q}(\pi)=\frac{2\sum_{d\in\mathcal{D}^{q}}\sum_{d^{\prime}\in\mathcal{D}_{\neg
d}^{q}}\ell(\mathcal{E}^{q}(d;\pi)\rho(d^{\prime}),\mathcal{E}^{q}(d^{\prime};\pi)\rho(d))}{|\mathcal{D}^{q}|(|\mathcal{D}^{q}|-1)},$

where $\mathcal{D}_{\neg d}^{q}$ denotes $\mathcal{D}^{q}\setminus\\{d\\}$ and
$\ell(a,b)$ is $(a-b)^{2}$. Let
$R_{fair}(\pi)=\mathbb{E}_{q}[R_{fair}^{q}(\pi)]$ be the expectation over
queries. Intuitively, $R_{fair}^{q}(\pi)$ measures how is the exposure of
items under the ranking model $\pi$ different from the ideal case where the
exposure is proportional to the relevance,
$\frac{\mathcal{E}(d)}{\rho(d)}=\frac{\mathcal{E}(d^{\prime})}{\rho(d^{\prime})}$,
for all pairs of items $d,d^{\prime}\in\mathcal{D}^{q}$.

Problem Statement. This work examines a real-world situation. For any
pretrained scoring function $f$, we aim to improve exposure-based fairness of
the LTR model via a post-hoc method while maintaining a satisfactory level of
utility (e.g., NDCG@K is no less than a certain level) with high probability.

Given query $q$ and the candidate items $\mathcal{D}^{q}$, and a fixed scoring
function $f$, the goal is to optimize the ranking model $\pi$ to minimize the
disparity with a simluataneous guarantee on the utility, i.e.,

$\underset{\pi}{\min}\;R_{fair}(\pi)\;s.t.\;P(R_{util}(\pi)\leq\alpha)\geq
1-\delta,$ (2)

where $\alpha\in(0,1)$ ($1-\alpha$) is the desired risk (utility) level, and
$1-\delta\in(0,1)$ is the desired coverage rate.

##  3 Background

###  3.1 Background: Distribution-free Risk Control

Distribution-free risk control is a post-hoc model-agnostic method based on
split conformal prediction. It uses a calibration set $\mathcal{Q}_{cal}$ to
determine the value of a set of model parameters s.t.

Let $\mathcal{T}({\lambda})$ be a set-valued function with a scalar parameter
$\lambda$ (e.g., a threshold on item scores) that predicts a set of items.
Given a bounded risk function $R(\mathcal{T}(\lambda))\in[0,B]$ that measures
the expected loss of $\mathcal{T}(\lambda)$ over queries, we define of a Risk
Controlling Prediction Set bates2021distribution. For simplicity, let
$R(\lambda)$ denote $R(\mathcal{T}(\lambda))$. Distribution-free risk control
bates2021distribution uses an independent and identically distributed (i.i.d.)
data split as the calibration set $\mathcal{Q}_{cal}$ to select $\lambda$ for
the set-valued functions $\mathcal{T}(\lambda)$ s.t. the risk function $R$ is
guaranteed on the test set $\mathcal{Q}_{test}$. In our setting, set-valued
functions predict a set of items for each position in the ranking. The
connection between set-valued functions and ranking models is shown in Section
4.2.

Risk Controlling Prediction Set bates2021distribution. Given a desired risk
level $\alpha\in[0,B]$ and tolerance rate $\delta\in(0,1)$, a set-valued
function $\mathcal{T}(\lambda)$ is a $(\alpha,\delta)$ risk-controlling
prediction set iff

$P(R({\lambda})\leq\alpha)\geq 1-\delta$ (3)

Intuitively, in our setting, this means the probability of observing the risk
function $R\leq\alpha$ is at least $1-\delta$ across repeated runs with
different random data splits when the set-valued function
$\mathcal{T}(\lambda)$ is applied. Then, the following assumptions are
employed.

  * •

Nesting Properties.

$\lambda<\lambda^{\prime}\Rightarrow\mathcal{T}(\lambda)\subset\mathcal{T}(\lambda^{\prime}),\;\mathcal{S}\subset\mathcal{S}^{\prime}\Rightarrow
R(\mathcal{S})\geq R(\mathcal{S}^{\prime})$ (4)

  * •

Existence of an upper confidence bound (UCB) $\hat{R}^{+}({\lambda})$ for the
risk function. It satisfies $P(R({\lambda})\leq\hat{R}^{+}({\lambda}))\geq
1-\delta$.

Under the aforementioned assumptions, Bates et al. bates2021distribution
propose to select the threshold $\hat{\lambda}$ on the calibration set
$\mathcal{Q}_{cal}$ s.t. $\mathcal{T}(\hat{\lambda})$ is a $(\alpha,\delta)$
risk-controlling prediction set. Intuitively, they select the $\lambda$ s.t.
any $\lambda^{\prime}\geq\lambda$ leads to UBC smaller than the desired level
$\alpha$ as

$\hat{{\lambda}}=\inf\\{{\lambda}\in{\Lambda}:\hat{R}^{+}({\lambda^{\prime}})<\alpha,\forall{\lambda}^{\prime}\geq{\lambda}\\},$
(5)

Then, angelopoulos2021learn extends risk control to cases where the nesting
properties are violated, which also allows multi-dimensional thresholds. The
crux of [angelopoulos2021learn] is hypothesis testing by the duality of
p-values and concentration inequality, which selects a threshold by rejecting
its corresponding null hypothesis $R(\bm{\lambda})>\alpha$ with p-value
smaller than $\delta$, where $\bm{\lambda}$ is the vector representing a
multi-dimensional threshold. In Section 4.3, we will present concrete
instantiation of both UBC and p-value based risk control for ranking.

It can be infeasible to control risk at every level of $\alpha$ for every data
distribution angelopoulos2021learn. For example, guaranteeing
$\text{NDCG@K}\geq 0.9$ may be unattainable given a subpar fixed scoring
function $f$, where risk control methods should abstain from returning a
threshold.

##  4 Methodology

In this section, the background of distribution-free risk control is
introduced, followed by the proposed framework.

###  4.1 Background: Distribution-free Risk Control

Distribution-free risk control is a post-hoc model-agnostic method based on
split conformal prediction. It uses a calibration set $\mathcal{Q}_{cal}$ to
determine the value of a set of model parameters s.t.

Let $\mathcal{T}({\lambda})$ be a set-valued function with a scalar parameter
$\lambda$ (e.g., a threshold on item scores) that predicts a set of items.
Given a bounded risk function $R(\mathcal{T}(\lambda))\in[0,B]$ that measures
the expected loss of $\mathcal{T}(\lambda)$ over queries, we define of a Risk
Controlling Prediction Set bates2021distribution. For simplicity, let
$R(\lambda)$ denote $R(\mathcal{T}(\lambda))$. Distribution-free risk control
bates2021distribution uses an independent and identically distributed (i.i.d.)
data split as the calibration set $\mathcal{Q}_{cal}$ to select $\lambda$ for
the set-valued functions $\mathcal{T}(\lambda)$ s.t. the risk function $R$ is
guaranteed on the test set $\mathcal{Q}_{test}$. In our setting, set-valued
functions predict a set of items for each position in the ranking. The
connection between set-valued functions and ranking models is shown in Section
4.2.

Risk Controlling Prediction Set bates2021distribution. Given a desired risk
level $\alpha\in[0,B]$ and tolerance rate $\delta\in(0,1)$, a set-valued
function $\mathcal{T}(\lambda)$ is a $(\alpha,\delta)$ risk-controlling
prediction set iff

$P(R({\lambda})\leq\alpha)\geq 1-\delta$ (6)

Intuitively, in our setting, this means the probability of observing the risk
function $R\leq\alpha$ is at least $1-\delta$ across repeated runs with
different random data splits when the set-valued function
$\mathcal{T}(\lambda)$ is applied. Then, the following assumptions are
employed.

  * •

Nesting Properties.

$\lambda<\lambda^{\prime}\Rightarrow\mathcal{T}(\lambda)\subset\mathcal{T}(\lambda^{\prime}),\;\mathcal{S}\subset\mathcal{S}^{\prime}\Rightarrow
R(\mathcal{S})\geq R(\mathcal{S}^{\prime})$ (7)

  * •

Existence of an upper confidence bound (UCB) $\hat{R}^{+}({\lambda})$ for the
risk function. It satisfies $P(R({\lambda})\leq\hat{R}^{+}({\lambda}))\geq
1-\delta$.

Under the aforementioned assumptions, Bates et al. bates2021distribution
propose to select the threshold $\hat{\lambda}$ on the calibration set
$\mathcal{Q}_{cal}$ s.t. $\mathcal{T}(\hat{\lambda})$ is a $(\alpha,\delta)$
risk-controlling prediction set. Intuitively, they select the $\lambda$ s.t.
any $\lambda^{\prime}\geq\lambda$ leads to UBC smaller than the desired level
$\alpha$ as

$\hat{{\lambda}}=\inf\\{{\lambda}\in{\Lambda}:\hat{R}^{+}({\lambda^{\prime}})<\alpha,\forall{\lambda}^{\prime}\geq{\lambda}\\},$
(8)

Then, angelopoulos2021learn extends risk control to cases where the nesting
properties are violated, which also allows multi-dimensional thresholds. The
crux of [angelopoulos2021learn] is hypothesis testing by the duality of
p-values and concentration inequality, which selects a threshold by rejecting
its corresponding null hypothesis $R(\bm{\lambda})>\alpha$ with p-value
smaller than $\delta$, where $\bm{\lambda}$ is the vector representing a
multi-dimensional threshold. In Section 4.3, we will present concrete
instantiation of both UBC and p-value based risk control for ranking.

It can be infeasible to control risk at every level of $\alpha$ for every data
distribution angelopoulos2021learn. For example, guaranteeing
$\text{NDCG@K}\geq 0.9$ may be unattainable given a subpar fixed scoring
function $f$, where risk control methods should abstain from returning a
threshold.

###  4.2 Thresholded PL Ranking Model

Here, we propose the Thresholded PL (TPL) ranking model. Applying TPL on top
of pretrained scoring functions from deterministic LTR models achieves an
effective utility fairness trade-off. The TPL model is built upon set-valued
functions, which enables distribution-free risk control for LTR. With
parameters of the set-valued functions obtained from risk control algorithms,
the TPL model provides a guarantee on a specified risk function.

Suppose we have access to a risk control score $\tilde{s}(d)$ of each document
$d$, which approximates the relevance of the item. We let $\tilde{s}(d)$ be a
function of the provided ranking score $s(d)$ from the fixed scoring function
$f$. We choose the probability to sample item $d$ at the first position in the
PL model, $p(d|\emptyset,0)$. More detailed discussion on the choice of risk
control score can be found in Appendix D. For each position $k$, the TPL
ranking model uses a set-valued function $\mathcal{T}(\lambda_{k})$ to select
items whose predicted scores are high enough for each position $k$, where
$\lambda_{k}$ is the threshold parameter for position $k$:

$\mathcal{T}(\lambda_{k})=\\{d|\tilde{s}_{d}\geq\lambda_{k},\forall
d\notin\mathbf{y}_{1:k-1}\\},$ (9)

where $\mathbf{y}_{1:k-1}=\emptyset$ if $k=1$. For each position $k$, TPL
creates a distribution of the items selected based on the set-valued function
$\mathcal{T}(\lambda_{k})$ defined in Eq. (9) and then combines them to
predict a distribution of rankings as:

$\begin{split}p(d|\mathbf{y}_{1:k-1},\lambda_{k})&=\frac{\mathds{1}(d\in\mathcal{T}(\lambda_{k}))\exp({s}_{d}/\tau)}{\sum_{d^{\prime}\in\mathcal{T}(\lambda_{k})}\exp({s}_{d^{\prime}}/\tau)},\;\;\\\
\pi(\mathbf{y})&=\prod_{k=1}^{K}p(d|\mathbf{y}_{1:k-1},\lambda_{k}),\end{split}$
(10)

When $\lambda_{k}$ takes extreme values, the TPL model will reduce to the PL
and the deterministic ranking model. Specifically, when $\lambda_{k}=0$ and
$\lambda_{k}\geq\max(\\{\tilde{s}_{d}\\}_{d\in\mathcal{D}^{q}\setminus\mathbf{y}_{1:k-1}})$
for $k=1,...,K$, TPL is equivalent to PL and the deterministic ranking model,
respectively. We verify this empirically in Section 5.2 (see Fig. 1).

In conformal prediction, it is often desired to have a small prediction set
size $|\mathcal{T}({\lambda_{k}})|$, which is not the case here. To achieve
the goal described by the problem statement (Eq. (2)), our method first finds
a set of $\lambda_{k}$ that is large enough for maintaining a guaranteed level
of utility then adopts the minimal $\lambda_{k}$ in the set for optimizing
exposure-based fairness. More specifically, we aim to minimize $R_{fair}$
under the constraint that the utility is guaranteed, which is equivalent to
maximizing $|\mathcal{T}({\lambda_{k}})|$ with items whose scores are at least
$\lambda_{k}$. We discuss selecting $\lambda_{k}$ through distribution-free
risk control in Section 4.3. With the set-valued function
$\mathcal{T}(\lambda_{k})$, TPL can adapt to the distribution of scores to
achieve this goal, compared to the PL model which samples any item from
$\mathcal{D}^{q}\setminus\mathbf{y}_{1:k-1}$ and the deterministic model which
only takes the item with the highest score. When there are multiple items with
high and similar scores, it is desired to include all of them in the
prediction set. When there are two items with scores much higher than others,
the prediction set should only include them.

###  4.3 Risk Control with Thresholded PL Model

Here, we describe the distribution-free risk control algorithm that selects
thresholds for the TPL model to provide provable guarantees on the bounded
risk function $R_{util}$. Given user-specified desired utility level
$1-\alpha$ for a bounded list-wise utility function $U$ (e.g., NDCG@K), our
method utilizes the calibration set $\mathcal{Q}_{cal}$ to find thresholds
that provide guaranteed utility. Note that existing post-hoc methods for
exposure-based fairness [morik2020controlling] are not able to provide such
guarantees as they blindly optimize a weighted combination of utility and
fairness objectives.

Selecting Thresholds via Risk Control. We leverage distribution-free risk
control bates2021distribution,angelopoulos2021gentle to learn thresholds
$\bm{\lambda}=[\lambda_{1},...,\lambda_{K}]$ for top-K positions s.t. the risk
of the ranking model is under control, i.e., $P(R_{util}(\pi)\leq\alpha)\geq
1-\delta$, where $R_{util}(\pi)=R_{util}(\pi(\bm{\lambda}))$. When the
threshold is a vector, the nesting properties may not hold.

The risk control algorithm works as follows. First, we specify a search space
$\Lambda$ for the thresholds. Each value $\bm{\lambda}\in\Lambda$ corresponds
to a null hypothesis $R_{util}(\bm{\lambda})>\alpha$. Then, for each value of
$\bm{\lambda}$, we test the null hypothesis on the calibration set
$\mathcal{Q}_{cal}$, which is assumed to be exchangeable with the test data
$\mathcal{Q}_{test}$ angelopoulos2021learn. Specifically, we aim to obtain the
rejected values of $\bm{\lambda}$ through the hypothesis testing, which is
associated with a specified UCB $\hat{R}^{+}$ for the risk $R_{util}$ as

$\hat{\Lambda}=\\{\bm{\lambda}\in\Lambda|\hat{R}^{+}(\bm{\lambda})<\alpha\\}$
(11)

Finally, we choose
$\hat{\bm{\lambda}}={\arg\min}_{{\bm{\lambda}\in\hat{\Lambda}}}\;R_{fair}(\bm{\lambda})$
to optimize fairness.

However, the computation can be inhibitive if brute-force grid search is
performed to test all possible values of $\bm{\lambda}$ from a predefined grid
with $M$ values for each $\lambda_{k}$. This requires computing
$\hat{R}^{+}(\bm{\lambda})$ for $M^{K}$ times, each of which includes
computing the risk $R_{util}$ on the calibration set. In this work, we
overcome this issue by limiting the search space of $\bm{\lambda}$ with a
heuristic, where we simply let each position use the same threshold $\lambda$,
which empirically performs well.

Risk Control for LTR. Here, we provide concrete instantiations of the UCB
[bates2021distribution] and p-valued based risk control
[angelopoulos2021learn], which are crucial for determining the risk-
controlling thresholds $\hat{\Lambda}$.

First, with the duality of concentration inequality and p-values in hypothesis
testing, we adopt the widely adopted Hoeffding-Benktus (HB) inequality
bates2021distribution,bentkus2004hoeffding,hoeffding1994probability which
combines the two inequalities by taking the minimum of the p-values from the
two iequality. The p-value associated with HB inequality is a function of the
mean risk $\hat{R}_{util}(\lambda)$ of the calibration set and the number of
queries in the calibration set $|\mathcal{Q}_{cal}|$ as:

$\begin{split}p^{HB}(\lambda)=\min(\exp(-|\mathcal{Q}_{cal}|h_{1}(\hat{R}_{util}(\lambda)\wedge\alpha,\alpha)),\\\
\exp{(1)}\times
p(Bin(n,\alpha)\leq\lceil|\mathcal{Q}_{cal}|\hat{R}_{util}(\lambda)\rceil)),\end{split}$
(12)

where $h_{1}(a,b)=a\log(\frac{a}{b})+(1-a)\log(\frac{1-a}{1-b})$,
$Bin(n,\alpha)$ is the Binomial distribution and $\lceil a\rceil$ takes the
ceiling of the scalar $a$. Given the Hoeffding Benktus p-values computed by
Eq. (12), we can obtain the set of selected thresholds
$\hat{\Lambda}=\\{\lambda\in\Lambda|p^{HB}(\lambda)<\delta\\}$ based on the
p-value of its hypothesis and then take the minimal $\lambda\in\hat{\Lambda}$
as it heuristically minimizes the disparity measure $R_{fair}$.

Second, besides the UCBs introduced in bates2021distribution, we adopt a
theory-backed UCB based on the DKWM inequality massart1990tight for risk
functions taking discrete values (e.g., $R_{util}=1-\text{NDCG@K}$).

$\hat{R}^{+}=R_{util}({\lambda})+\texttt{const.}\cdot\sqrt{\frac{\ln(2/\delta)}{2\cdot|\mathcal{Q}_{cal}|}}.$
(13)

where const. is a constant that depends on the set of loss values – we specify
the details and provide the proof in Appendix A. With such a UCB, we can
search for the minimal $\lambda\in\Lambda$ that satisfies $R^{+}<\alpha$ (as
in Eq. (8)) on the calibration set and obtain the guarantee by Theorem 1 of
bates2021distribution. $R_{util}(\lambda)$ may not satisfy the nesting
assumption (Eq. (7)), but we can find
$\tilde{R}_{util}(\lambda)=\max_{t\leq\lambda}R_{util}(\lambda)\geq R_{util}$
that satisfies the assumption angelopoulos2022conformal. Then we can apply the
UCBs on $\tilde{R}_{util}$.

##  5 Experiment

###  5.1 Experimental Setup

Datasets. We consider two popular publicly available datasets for LTR:
Yahoo!Webscope (Yahoo) chapelle2011yahoo and MSLR-WEB30k (MSLR)
qin2013introducing.

Table 1: Statistics of the benchmark datasets | # queries (# items) | # features
---|---|---
| training | validation | original test |
Yahoo | 19,944 (473,134) | 6,983 (165,660) | 2,994 (71,083) | 700
MSLR-WEB30K | 18,919 (2,270,296) | 6,306 (753,611) | 12,581 (747,218) | 136

Table 1 shows the statistics describing the widely used datasets for
evaluating LTR models. We observe that Yahoo has more features and MSLR has
more queries and much more items per query. These datasets consist of queries,
their associated documents, and relevance labels in $0-4$ indicating the
expert-judged relevance between an item and a query. Each feature vector
represents a query-document pair.

Similar to angelopoulos2022recommendation, to compute the coverage rate, we
repeat the experiment $50$ times by randomly splitting the original test set
into calibration (25%) and test sets (75%). The scoring functions are
pretrained on the training set and model selection is done by maximizing
NDCG@5 on the validation set. Then, for risk control, the threshold
${\lambda}$ is selected based on UCB or p-value computed on the calibration
set. We compare the proposed FairLTR-RC with the deterministic and PL ranking
model with mean and standard deviation of the test performance over these 50
runs.

Finally, we follow bruch2020stochastic to ignore all queries with no relevant
documents for fair evaluation. It avoids arbitrarily assigning
$\text{NDCG@K}=1$ or $0$ to such queries with any ranking, to prevent unfair
comparisons. Thus, the NDCG@K reported in this work lower than those in the
literature.

Scoring Functions. We use CatBoost prokhorenkova2018catboost, LightGBM (LGB)
ke2017lightgbm and Neural Network (NN) as the pretrained scoring function. The
NN is a three-layer MLP with sigmoid activation trained with LambdaLoss
wang2018lambdaloss. On top of the pretrained scoring functions, we apply the
ranking models (deterministic, PL and TPL). More details about the
experimental setup can be found in Appendix B.

To make the coverage results more comprehensive, we also apply our method to
the state-of-the-art stochastic LTR models that train scoring function on the
top of the PL model, including PL-Rank-3 [oosterhuis2022learning],
StochasticRank ustimenko2020stochasticrank, and Policy Gradient
[singh2019policy], the results for which is in Appendix C.

Evaluation Metrics. We consider the widely used NDCG@5 as the utility metric.
For exposure-based fairness, we follow oosterhuis2021computationally to adopt
Eq. (2) with and $\ell(a,b)=(a-b)^{2}$ to measure the mean squared disparity
$R_{sq-fair}$. It measures how the assigned exposure of an item is different
from being proportional to its relevance.

For the guarantee, we repeat the experiment $50$ times and report the marginal
coverage on test sets with thresholds selected by risk control algorithms
$\hat{\lambda}$ as
$\sum_{t=1}^{T}\mathds{1}(R_{util}(\hat{\lambda})\leq\alpha)/T$. We choose
$\alpha$ based on the performance of the original deterministic model.

###  5.2 Experimental Results

Trade-off Results. We first verify that the proposed TPL ranking model can
achieve an effective trade-off between utility and fairness. As shown in Fig.
1, when the threshold $\lambda$ increases, the utility (risk) of the TPL
ranking model increases (decreases) while the disparity measure increases. In
addition, we verify the claim that TPL model can reduce to the PL and
deterministic model. When $\lambda=0$, the TPL model reduces to the PL ranking
model (Sto). When $\lambda\geq\max(\tilde{s}_{d})$, TPL reduces to the
deterministic ranking model (Det).

(a) CatBoost on Yahoo

(b) NN on Yahoo

(c) CatBoost on MSLR-WEB30K

(d) NN on MSLR-WEB30K

Figure 1: Trade-off between utility and fairness achieved by TPL. The x-axis is the threshold $\lambda$, the left (right) y-axis is the risk $R_{{util}}=1-\text{NDCG@5}$ (the disparity $R_{sq-fair}$). Det and Sto are the deterministic and the PL ranking models. The shade is one standard deviation. As $\lambda$ increases, TPL only includes items with higher scores, leading to lower risk and higher disparity. Complete results are in Fig. 2 of Appendix C. Table 2: Coverage Results with thresholds $\lambda$ selected by the p-value of Hoeffding-Benktus. Similar results for DKWM can be found in Appendix C. | Yahoo
---|---
| Coverage |  1-$\alpha$ | NDCG@5 | $1-\frac{R_{sq-fair}}{R_{sq-fair}^{*}}$ | # Abstain
CatBoost | 100% | 0.687 | 0.727 | 23.99% | 2
LGB | 100% | 0.687 | 0.727 | 20.77% | 0
NN | 100% | 0.641 | 0.673 | 35.05% | 0
| MSLR
CatBoost | 100% | 0.449 | 0.481 | 16.08% | 0
LGB | 100% | 0.449 | 0.480 | 13.29% | 2
NN | 100% | 0.405 | 0.430 | 26.14% | 0

Coverage and Fairness Improvement. Let $U^{*}$ and $R_{sq-fair}^{*}$ be the
NDCG@5 and mean squared disparity of the pretrained deterministic LTR model,
respectively. Results in Table 2 show that, with risk control based on
Hoeffding-Benktus, in at least 48 out of 50 runs ($\leq 2$ abstentions), our
method achieves 100% coverage (NDCG@5$\geq 1-\alpha$). At the same time, our
method improves fairness significantly with at least 13.29% drop in $R_{sq-
fair}$. In practice, when the risk control method abstains from selecting any
thresholds, we can set the threshold $\lambda=1$ to make TPL reduce to the
deterministic ranking model. Fig. 3 in Appendix C shows distribution of NDCG@5
with thresholds selected by Hoeffding-Benktus and DKWM iequality.

##  6 Related Work

Stochastic Ranking and Exposure-based Fairness. Stochastic LTR models were
initially adopted to address the challenge of optimizing ranking metrics,
which are flat or discontinuous
wang2018lambdaloss,bruch2020stochastic,ustimenko2020stochasticrank, where it
is shown that training scoring functions with the PL ranking model improves
their ranking performance. In addition, the PL ranking model also can enable
exploration for by the estimated uncertainty as it explcitly estimates
uncertainty of the scoring function through the probability distribution from
the PL ranking model [oosterhuis2021computationally]. This can be helpful when
there exists samples (e.g., users, queries and items) with few interactions.
Recently, stochastic LTR models are adopted to improve exposure-based
fairness. Singh et al. [singh2019policy] proposed the notion of exposure-based
fairness and a policy gradient algorithm to train LTR models to optimize a
combination of utility and fairness. diaz2020evaluating evaluated two types of
stochastic ranking models including the PL model w.r.t. exposure-based
fairness based on various click models.
oosterhuis2021computationally,oosterhuis2022learning improve the efficiency of
training scoring functions with the PL model forrelevance and fairness.
Different from them, our method transforms a pretrained scoring function from
a deterministic LTR model to a stochatic one.

Distribution-free Risk Control for Ranking. Distribution-free risk control is
based on split conformal prediction
papadopoulos2002inductive,angelopoulos2021gentle. Bates et al.
bates2021distribution propose a method to predict an interval of a pair-wise
score of items with guaranteed confidence. It abstains from predicting
unconfident pairs. However, it does not directly provide guarantees on list-
wise ranking performance. Angelopoulos et al. angelopoulos2022recommendation
apply Learn then Test [angelopoulos2021learn] to the recall stage of
recommendation systems, which predicts sets with items with scores higher than
a threshold, with a guarantee on the expected ratio of false positives. Wang
et al. [wang2022improving] propose a method based on [bates2021distribution]
to select a threshold for marginal guarantee on the number of candidates from
each group and minimizes the prediction set size for each query, which is
further extended to the scenario with noisy and biased implicit feedbacks
(e.g., clicks) [wang2022fairness] . Different from the existing work, this
work focuses on providing guarantee on widely used list-wise ranking metrics
(e.g., NDCG@K).

##  7 Conclusion

In this work, we propose FairLTR-RC, a post-hoc model-agnostic method for Fair
Learning to Rank (LTR). It can create a stochastic LTR model with improved
exposure-based fairness with a scoring function from a pretrained
deterministic LTR model. With distribution-free risk control, our method can
provide guarantee on a user-specified utility function. The integration of the
Thresholded Plackett-Luce (TPL) model balances utility and fairness. FairLTR-
RC avoids expensive training and provides guarantees on a specified metric
based on distribution-free risk control. Results on benchmark datasets verify
the effectiveness of our proposed method, improving fairness of state-of-the-
art deterministic models while ensuring a predefined level of utility.

Despite its promising results, this work is not without limitations. FairLTR-
RC may abstain from selecting thresholds with subpar pretrained scoring
functions, small calibration sets, conservative bounds in risk control
methods, and when $\alpha$ is too small.

##  Appendix A Proof

We will use the DKWM inequality to derive a general UCB with discrete risk
$R$:

######  Lemma 1.

Given a natural number $n$, let $Z_{1},Z_{2},...,Z_{n}$ be real-valued
independent and identically distributed random variables with cumulative
distribution function $F(\cdot)$. Let $F_{n}$ denote the associated empirical
distribution defined by

$F_{n}(z)=\frac{1}{n}\sum_{i}1(Z_{i}\leq z),~{}~{}z\in\mathbb{R}$

Then $\forall\delta\in(0,1)$, with probability at least $1-\delta$,

$\sup_{z\in\mathbb{R}}|F(z)-F_{n}(z)|\leq\sqrt{\frac{\ln 2/\delta}{2n}}$

In order to apply the aforementioned lemma, we have to show that the risk
function
$R^{q}(\lambda)=\frac{1}{m}\sum_{j=1}^{m}l(\hat{\mathbf{y}}^{j},\mathbf{y}^{*})$
can be equivalently written as an indicator random variable w.r.t. a certain
threshold $\lambda$. More specifically, when we take $1-\text{NDCG@K}$ as the
risk function $R$ and $l$ as the 0-1 loss function. Each threshold $\lambda$
corresponds to a certain probability that the best item is shown at the top
position, which is denoted as $z(\lambda)$. Denote by $Z_{j}$ a uniformly
random variable defined on $[0,1]$. Then

$l(\hat{\mathbf{y}}^{j},\mathbf{y}^{*})=1(Z_{j}\leq z(\lambda)),$

and therefore

$R^{q}(\lambda)=\frac{1}{m}\sum_{j=1}^{m}1(Z_{j}\leq z(\lambda)).$

The lemma can therefore apply. Since the lemma covers all $z\in\mathbb{R}$, it
for sure will cover $z(\lambda)$.

Then we show how to generalize the argument to the case with multiple but
discrete loss levels. Suppose the loss values are $l_{1},l_{2},...,l_{K}$ and
the chance of incuring a loss $l_{k}$ is captured by an interval
$[z_{k-1}(\lambda),z_{k}(\lambda))$ with $z_{K}(\lambda)=1$:

$[0,z_{1}(\lambda)),[z_{1}(\lambda),z_{2}(\lambda)),...,[z_{K-1}(\lambda),1)$

Then

$l(\hat{\mathbf{y}}^{j},\mathbf{y}^{*})=\Sigma\cdot 1(Z_{j}\leq
z_{k}(\lambda))+l_{K},$

where $\Sigma$ denotes the summation $\sum_{k=1}^{K-1}(l_{k}-l_{k+1})$. Then,
the empirical CDF can be written as

$F_{m}(z_{k}(\lambda)):=\frac{1}{m}\sum_{j=1}^{m}1(Z_{j}\leq z_{k}(\lambda))$

With this we have

$\displaystyle R^{q}(\lambda)$
$\displaystyle=\Sigma\cdot\frac{1}{m}\sum_{j=1}^{m}1(Z_{j}\leq
z_{k}(\lambda))+l_{k}$ $\displaystyle=\Sigma\cdot F_{m}(z_{k}(\lambda))+l_{k}$

Then we can derive the following inequality

$\displaystyle|R^{q}(\lambda)-\mathds{E}[R^{q}(\lambda)]|$
$\displaystyle=\left|(\Sigma\cdot F_{m}(z_{k}(\lambda))+l_{k})-(\Sigma\cdot
F(z_{k}(\lambda))+l_{k})\right|$
$\displaystyle=\left|\Sigma\cdot(F_{m}(z_{k}(\lambda)-F(z_{k}(\lambda)))\right|$
$\displaystyle\leq\sum_{k=1}^{K-1}|l_{k}-l_{k+1}|\cdot|F_{m}(z_{k}(\lambda))-F(z_{k}(\lambda))|$

Since for all $z$ we have

$|F_{m}(z)-F(z)|\leq\sqrt{\frac{\ln 2/\delta}{2m}}$

Then

$|R^{q}(\lambda)-E[R^{q}(\lambda)]|\leq\sum_{k=1}^{K-1}|l_{k}-l_{k+1}|\cdot\sqrt{\frac{\ln
2/\delta}{2m}},\forall\lambda.$

P-value for the DKWM Concentration Inequality. Here, we provide a discussion
on the p-value corresponding to the DKWM inequality based UCB. The DKWM
inequality does not naturally comes with a p-value as it is bounding the
difference between the empirically CDF $F_{m}(z)$ and the true one $F(z)$. The
p-value upper bounds the probability of observing a deviation at least as
large as the observed deviation. In our case, while we can approximate
$F_{m}(z)$ and $\sqrt{\frac{\ln 2/\delta}{2m}}$, the true CDF $F(z)$ is
unknown, the DKWM inequality tells us, for any $z$,

$p(\mathds{E}[R(\lambda)]>\hat{R}(\lambda)+\sum_{k=1}^{K-1}|l_{k}-l_{k+1}|\sqrt{\frac{\ln
2/\delta}{2m}})\leq\delta/2,$

where $\hat{R}$ is the mean risk computed on the calibration set
$\mathcal{Q}_{cal}$.

Then, we are interested in the p-value which refers to the probability that a
user-specified level of risk $\alpha$ is larger than true mean of risk
function $\hat{R}(\lambda)$:

$p(\mathds{E}[R(\lambda)]<\alpha).$ (14)

Intuitively, if we know $p(\mathds{E}[R(\lambda)]<\alpha)$, then we can choose
the threshold $\lambda$ accordingly to ensure that
$p(\mathds{E}[R(\lambda)]<\alpha)\geq 1-\delta$ to achieve the constraint in
our problem statement in Eq. (2).

Without any assumption on the distribution of the true mean
$p(\mathds{E}[R(\lambda)])$, this implies that, for all
$\alpha\geq\hat{R}(\lambda)+2\sum_{k=1}^{K-1}|l_{k}-l_{k+1}|\sqrt{\frac{\ln
2/\delta}{2m}}$, we can guarantee

$p(\mathds{E}[{R}(\lambda)]<\alpha)\geq 1-\delta/2.$

This is equivalent to

$p(\mathds{E}[{R}(\lambda)]<\alpha)\geq 1-\delta,$

with
$\alpha\geq\hat{R}(\lambda)+2\sum_{k=1}^{K-1}|l_{k}-l_{k+1}|\sqrt{\frac{\ln
1/\delta}{2m}}$.

By assuming the distribution of $p(R(\lambda))$ (e.g., normal distribution),
we can compute this p-value by the CDF of $R(\lambda)$, which can further
enable us to combine it with the existing p-value provided by Hoeffding-
Benktus.

##  Appendix B Experimental Setup Details

CatBoost prokhorenkova2018catboost and LightGBM ke2017lightgbm. We perform
grid search following the benchmark repository of CatBoost for
LTR111https://github.com/catboost/benchmarks/tree/master/ranking. In
particular, we search the following hyperparameters: learning rate in
$\\{0.03,0.07,0.15,0.3\\}$, max_bin in $\\{64,128,254\\}$, and max_depth in
$\\{4,6,8,10\\}$. We select the best model is based on NDCG@5 in the
validation set.

Neural Network Scoring Function. We follow the open-source
code222https://github.com/HarrieO/2022-SIGIR-plackett-luce of
[oosterhuis2022learning] to train the NN base model for our method and
reproduce results of the state-of-the-art stochastic LTR models. Specifically,
we use a three-layer MLP with sigmoid activation. The number of hidden units
is $32$, batch size is $256$. Each model is trained for $100$ epochs. A
checkpoint is saved for each epoch. We select the checkpoint with highest
NDCG@5 in the validation set.

##  Appendix C Complete Experimental Results

Here, we demonstrate the complete experimental results.

###  C.1 Complete Trade-off Results

Here, Fig. 2 shows the complete results of utility fairness trade-off for the
two datasets with all three scoring functions pretrained with deterministic
LTR models.

(a) CatBoost on Yahoo

(b) LGB on Yahoo

(c) NN on Yahoo

(d) CatBoost on MSLR-WEB30K

(e) CatBoost on MSLR-WEB30K

(f) NN on MSLR-WEB30K

Figure 2: Complete results for trade-off between utility and fairness achieved by TPL. The x-axis is the threshold $\lambda$, the left (right) y-axis is the risk $R_{{util}}=1-\text{NDCG@5}$ (the disparity $R_{sq-fair}$). Det and Sto are the deterministic and the PL ranking models. The shade is one standard deviation. As $\lambda$ increases, TPL only includes items with higher scores, leading to lower risk and higher disparity. Table 3:  Coverage Results with thresholds $\lambda$ selected by DKMW inequality. | Yahoo
---|---
| Coverage |  1-$\alpha$ | NDCG@5 | $1-\frac{R_{sq-fair}}{R_{sq-fair}^{*}}$ | # Abstain
CatBoost | 100% | 0.687 | 0.734 | 13.69% | 16
LGB | 100% | 0.687 | 0.734 | 10.95% | 16
NN | 100% | 0.641 | 0.682 | 30.37% | 0
| MSLR
CatBoost | 100% | 0.449 | 0.484 | 11.19% | 12
LGB | 100% | 0.449 | 0.483 | 8.39% | 15
NN | 100% | 0.405 | 0.435 | 22.22% | 0

###  C.2 Complete Coverage Results

Here, we first show the coverage rates by DKWM inequality. We can observe
that, compared to Hoeffding-Benktus, DKWM inequality leads to a less tight
UCB. This explains why DKWM results in higher NDCG@5, less drop in the
disparity measure $R_{sq-fair}$ and larger number of absteintions. We leave
finding a tighter bound than the Hoeffding-Benktus to future work.

Then, for the two datasets, we show more detailed results on coverage – the
distributions of NDCG@5 with all three scoring functions in Fig. 3. We make
the following observations.

  * •

With thresholds selected by both Hoeffing-Benktus and DKWM, our method can
achieve 100% coverage rate to provide the guarantee that NDCG@5$\geq 1-\alpha$
on both datasets with all three scoring functions.

  * •

The UCB of DKWM is less tight than that of Hoeffing-Benktus, leading to more
conservative selection of thresholds, higher NDCG@5, worse improvement in
fairness, and greater number of absteintions.

(a) CatBoost on Yahoo

(b) LGB on Yahoo

(c) NN on Yahoo

(d) CatBoost on MSLR

(e) LGB on MSLR

(f) NN on MSLR

Figure 3: Distribution of NDCG@5 achieved by FairLTR-RC over $50$ runs with
$\lambda$ selected by Hoeffding-Benktus. The red (green) vertical line is the
desired NDCG@5 level $1-\alpha=0.9U^{*}$. $U^{*}$ is the NDCG@5 of the
deterministic model.

(a) CatBoost on Yahoo

(b) LGB on Yahoo

(c) NN on Yahoo

(d) CatBoost on Yahoo

(e) LGB on MSLR

(f) NN on MSLR

Figure 4: Distribution of NDCG@5 achieved by FairLTR-RC over $50$ runs with
$\lambda$ selected by DKWM inequality. The red (green) vertical line is the
desired NDCG@5 level $1-\alpha=0.9U^{*}$. $U^{*}$ is the NDCG@5 of the
deterministic model. We also show the coverage rate, number of abstentions and
$R_{sq-fair}$.

###  C.3 Coverage Results for Stochastic LTR models

Here, we illustrate the complete coverage results for CatBoost, LightGBM,
LambdaLoss, and the state-of-the-art stochastic LTR models including PL-Rank-3
[oosterhuis2022learning], StochasticRank [ustimenko2020stochasticrank], and
Policy Gradient [singh2019policy]. With the results shown in Table 4, we make
the following observations:

  * •

First, the proposed method achieves effective utility fairness trade-off while
maintaining the guarantee on utility. With the scoring function from the
pretrained stochastic LTR models, our method can improve exposure-based
fairness by at least 30.52% on Yahoo and 26.14% on MSLR, respectively, with
guarantee that the NDCG@5 is at least 90% of that obtained with the same
scoring function on the top of a deterministic ranking model.

  * •

Second, with PL-Rank-3, our method achieves the most effective trade-off with
35.05% and 29.61% improvement in exposure-based fairness measured by $R_{sq-
fair}$. We conjecture that this is due to the scoring function pretrained by
PL-Rank-3 maintains the best ranking performance.

Table 4:  Complete coverage results with thresholds $\lambda$ selected by HB
inequality. Yahoo
---
| Coverage | 1-$\alpha$ | NDCG@5 | $1-\frac{R_{sq-fair}}{R_{sq-fair}^{*}}$ | # Abstain
CatBoost | 100% | 0.687 | 0.727 | 23.99% | 2
LightGBM | 100% | 0.687 | 0.727 | 20.77% | 0
LambdaLoss | 100% | 0.641 | 0.673 | 35.05% | 0
PL-Rank-3 | 100% | 0.641 | 0.673 | 35.05% | 0
Policy Gradient | 100% | 0.641 | 0.674 | 30.52% | 0
StochasticRank | 100% | 0.641 | 0.673 | 34.88% | 0
MSLR
CatBoost | 100% | 0.449 | 0.481 | 16.08% | 0
LightGBM | 100% | 0.449 | 0.480 | 13.29% | 2
LambdaLoss | 100% | 0.405 | 0.430 | 26.14% | 0
PL-Rank-3 | 100% | 0.405 | 0.430 | 29.61% | 0
Policy Gradient | 100% | 0.405 | 0.430 | 26.14% | 0
StochasticRank | 100% | 0.405 | 0.429 | 27.63% | 0

##  Appendix D Score for Distribution-free Risk Control

Risk control (RC) score is a crucial design choice for distribution-free risk
control bates2021distribution,angelopoulos2021learn. In TPL, RC score
determines whether an item would be included in the prediction set
$\mathcal{T}(\lambda_{k})$ for position $k$. A natural choice of RC score is
the expected position-wise sampling probability
$\mathbb{E}_{\mathbf{y}_{1:k-1}}[p(d|\mathbf{y}_{1:k-1},0)]$ in the PL model,
which is a calibrated measure of the predicted relevance of item $d$ for
position $k$. However, it can be computationally expensive to compute
$p(d|\mathbf{y}_{1:k-1},0)$ for all possible $(d,\mathbf{y}_{1:k-1})$ when
$|\mathcal{D}^{q}|$ and $k$ are large. To decouple the score function of
position $k$ from the sampled partial rankings $\mathbf{y}_{1:k-1}$, we
propose to use the probability to sample $d$ at the first position in the PL
model, i.e., $p(d|\emptyset,0)$, as the RC score. Unlike the original ranking
score $s_{d}$, as probability density, $p(d|\emptyset,0)\in[0,P^{max}]$ for
$d\in\mathcal{D}^{q}$ for all queries $q$, is always bounded. In addition, the
maximum $P^{max}=\max_{d}(p(d|\emptyset,0))$ can be easily computed using the
calibration set, making it convenient to obtain the range for the threhsolds
$\lambda_{k}$ for creating the set of candidate thresholds $\hat{\Lambda}$ for
distribution-free risk control. Furthermore, it can be easily demonstrated
that $p(d|\emptyset,0)$ exhibits monotonicity with respect to the expected
position-wise sampling probability
$\mathbb{E}_{\mathbf{y}{1:k-1}}[p(d|\mathbf{y}_{1:k-1},0)]$.

In practice, we use the softmax of normalized ranking scores from pretrained
scoring function $f$ as the scores:

$\begin{split}s_{d}&=(s_{d}^{raw}-mean({s}^{raw}))/std(s^{raw})\\\
p_{d}&=softmax(s_{d}),\\\ \end{split}$ (15)

where $mean({s}^{raw})$ and $std(s^{raw})$ are the mean and standard deviation
of the ranking scores computed on the validation set.

Empirically, we find it is much easier to design the range for searching
$\lambda$ if the scores are normalized. Recall that ranking scores are
unbounded real values, normalizing them makes the range of scores, i.e.,
$p(d|\emptyset)$. much easier to compute.


$|\widehat{\beta_{2}}^{(-1)}-\beta_{2}|=\left|\beta_{1}\frac{\sigma_{2e}\sigma_{1}^{2}}{\sigma_{2}^{2}\sigma_{1}^{2}-\sigma_{2e}^{2}}\right|$.

Finally, we compare
$|\widehat{\beta_{2}}^{(-1)}-\beta_{2}|=\left|\beta_{1}\frac{\sigma_{2e}\sigma_{1}^{2}}{\sigma_{2}^{2}\sigma_{1}^{2}-\sigma_{2e}^{2}}\right|$
and
$|\widehat{\beta_{2}}-\beta_{2}|=\left|\beta_{1}\frac{\sigma_{2e}\sigma_{1}^{2}}{\sigma_{2}^{2}(\sigma_{1}^{2}+\sigma_{e}^{2})-\sigma_{2e}^{2}}\right|$,
or equivalently, compare
$\frac{1}{\left|\sigma_{2}^{2}\sigma_{1}^{2}-\sigma_{2e}^{2}\right|}$ and
$\frac{1}{\left|\sigma_{2}^{2}(\sigma_{1}^{2}+\sigma_{e}^{2})-\sigma_{2e}^{2}\right|}$.
Therefore, the condition
$\left|\sigma_{2}^{2}\sigma_{1}^{2}-\sigma_{2e}^{2}\right|<\left|\sigma_{2}^{2}(\sigma_{1}^{2}+\sigma_{e}^{2})-\sigma_{2e}^{2}\right|$
implies that
$\frac{1}{\left|\sigma_{2}^{2}\sigma_{1}^{2}-\sigma_{2e}^{2}\right|}>\frac{1}{\left|\sigma_{2}^{2}(\sigma_{1}^{2}+\sigma_{e}^{2})-\sigma_{2e}^{2}\right|}\Rightarrow|\widehat{\beta_{2}}^{(-1)}-\beta_{2}|>|\widehat{\beta_{2}}-\beta_{2}|$,
i.e., the SIMEX corrected coefficient on $X_{2}$ becomes even more biased than
it would be in the absence of correction. ∎

Remark. We note that the condition
$\left|\sigma_{2}^{2}\sigma_{1}^{2}-\sigma_{2e}^{2}\right|<\left|\sigma_{2}^{2}(\sigma_{1}^{2}+\sigma_{e}^{2})-\sigma_{2e}^{2}\right|$
is quite easily satisfied. The right-hand-side of the inequality is equivalent
to
$\left|\sigma_{2}^{2}\sigma_{1}^{2}-\sigma_{2e}^{2}+\sigma_{2}^{2}\sigma_{e}^{2}\right|$.
Therefore, a sufficient (but not necessary) condition for the inequality to
hold is $\sigma_{2}^{2}\sigma_{1}^{2}-\sigma_{2e}^{2}\geq 0$. Because
$\sigma_{2}^{2}\sigma_{1}^{2}-\sigma_{2e}^{2}\geq
0\Leftrightarrow\frac{\sigma_{1}^{2}}{\sigma_{e}^{2}}\geq\frac{\sigma_{2e}^{2}}{\sigma_{2}^{2}\sigma_{e}^{2}}=\rho_{2e}^{2}$,
we can see that the inequality always holds if
$\sigma_{1}^{2}\geq\sigma_{e}^{2}$, which means that the variance of
measurement error is no larger than the variance of true covariate. This is
typically true unless the measurement error is exceedingly large.

Essentially, the SIMEX approach relies on the implicit assumption that degree
of measurement error is positively related to degree of bias. This assumption
is violated when a precisely-measured covariate is correlated with the
measurement error, as we have shown in the above theorem. As a result, unless
special modifications are made to the SIMEX procedure, it produces incorrect
results on the precisely-measured covariate. However, our ForestIV approach
does not suffer from this issue, because it does not rely on the same implicit
assumption. Instead, the identified instruments should mitigate estimation
bias on the error-prone covariate, without introducing additional bias to the
estimates of precisely-measured covariates.

We empirically demonstrate this limitation of SIMEX and the robustness of
ForestIV via another set of simulations, using the Boston Housing dataset. The
basic setup is the same as before, with one change: one control variable,
$Z_{2}\sim N(0,1)$, is generated so that it is correlated with the prediction
error in $\widehat{MEDV}$ (the aggregate predictions from the random forest
model), with a correlation coefficient of 0.3. We repeat the same set of
regression analyses and report the results in Table 13.

| True | Biased | SIMEX | ForestIV
---|---|---|---|---
Intercept | 1.0 | -0.962 (0.399) | 0.688 (0.385) | 0.840 (0.384)
|  | [0.002] | [0.418] | [0.677]
$MEDV$ | 0.5 | 0.588 (0.016) | 0.513 (0.060) | 0.506 (0.015)
|  | [0.004] | [0.416] | [0.689]
$Z_{1}$ | 2.0 | 2.017 (0.232) | 2.011 (0.258) | 2.017 (0.219)
|  | [0.458] | [0.966] | [0.938]
$Z_{2}$ | 1.0 | 0.483 (0.114) | 0.401 (0.155) | 0.837 (0.126)
|  | [0.000] | [0.000] | [0.196]
Ave_MSE |  | 4.351 | 0.699 | 0.264
Table 13: Estimation Results using SIMEX and ForestIV with
$\rho_{Z_{2},e}=0.3$. Standard errors in parentheses. $p$-values comparing
estimates with true values in square brackets. Ave_MSE contains the average
empirical MSE associated with each set of estimates across 100 simulation
runs.

Based on Table 13, we can see that, when the measurement error is correlated
with the precisely-measured control variable $Z_{2}$, the coefficient on
$Z_{2}$ is drastically underestimated by 51.7%, and, consistent with our
theoretical result, the SIMEX-corrected coefficient becomes even more biased.
However, our proposed ForestIV approach is able to not only mitigate the bias
on $MEDV$, but also notably correct the coefficient on $Z_{2}$ in the right
direction. This suggests that ForestIV is more robust than SIMEX when the
measurement error is correlated with certain control variables in the model.

###  G.4 Benchmarking with LatentIV

Next, we benchmark our proposed ForestIV with the LatentIV approach on the
Bike Sharing dataset. We adopt the implementation of LatentIV in the R package
“REndo”. Note that this implementation of LatentIV does not support the
estimation of other exogenous control variables in the model. Therefore, we
drop the control variables from the simulation, and the dependent variable is
simulated simply as $Y=1+0.5lnCnt+\varepsilon$, where $\varepsilon\sim
N(0,4)$. We apply both ForestIV and LatentIV on this data. The average
estimates from LatentIV across 100 simulation runs, together with the biased,
unbiased, and ForestIV estimates, are reported in Table 14.

| True | Biased | Unbiased | ForestIV | LatentIV
---|---|---|---|---|---
Intercept | 1.0 | 0.711 (0.062) | 0.972 (0.203) | 0.938 (0.148) | 0.776 (0.733)
|  | [0.001] | [0.568] | [0.677] | [0.760]
$lnCnt$ | 0.5 | 0.564 (0.013) | 0.507 (0.040) | 0.515 (0.029) | 0.549 (0.166)
|  | [0.002] | [0.538] | [0.613] | [0.770]
Ave_MSE |  | 0.112 | 0 | 0.010 | 1.346
Table 14: Benchmarking ForestIV with LatentIV on Bike Sharing Data. Standard
errors in parentheses. $p$-values comparing estimates with true values in
square brackets. Ave_MSE contains the average empirical MSE associated with
each set of estimates across 100 simulation runs.

We find that LatentIV is able to mitigate the estimation biases on $lnCnt$ and
the intercept term to some degree. Nonetheless, the method appears to be
systematically less effective than ForestIV. In addition, the standard errors
of the LatentIV estimates are much larger than those yielded by ForestIV,
indicating potential instability of the results.

###  G.5 Benchmarking with Generated Regressor Adjustment

Finally, we benchmark ForestIV against the regression adjustment approach
developed by Meng et al.,  (2016) for measurement error in nonparametrically
generated regressors. We apply the formula in (Meng et al., , 2016, p.305) to
obtain the adjusted coefficient and standard error on $lnCnt$.999Meng et al.,
(2016) does not explicitly discuss how to adjust for bias in the intercept
term. We therefore report the same intercept term as the biased regression.
The average estimates from the regression adjustment across 100 simulation
runs, together with the biased, unbiased, and ForestIV estimates, are reported
in Table 15.

| True | Biased | Unbiased | ForestIV | Generated Regressor Adjustment
---|---|---|---|---|---
Intercept | 1.0 | 0.702 (0.063) | 1.018 (0.204) | 0.957 (0.134) | 0.702 (0.063)
|  | [0.004] | [0.511] | [0.745] | [0.004]
$lnCnt$ | 0.5 | 0.566 (0.013) | 0.498 (0.040) | 0.512 (0.027) | 0.563 (0.147)
|  | [0.002] | [0.530] | [0.652] | [0.664]
$Z_{1}$ | 2.0 | 2.000 (0.003) | 1.999 (0.011) | 2.000 (0.003) | 2.000 (0.003)
|  | [0.459] | [0.524] | [0.977] | [0.459]
$Z_{2}$ | 1.0 | 1.000 (0.002) | 0.999 (0.006) | 1.000 (0.002) | 1.000 (0.002)
|  | [0.480] | [0.486] | [0.989] | [0.480]
Ave_MSE |  | 0.150 | 0 | 0.017 | 0.164
Table 15: Benchmarking ForestIV with Generated Regressor Adjustment on Bike
Sharing Data. Standard errors in parentheses. $p$-values comparing estimates
with true values in square brackets. Ave_MSE contains the average empirical
MSE associated with each set of estimates across 100 simulation runs.

We find that the generated regressor adjustment approach only slightly reduces
the bias on $lnCnt$, and is clearly less effective than ForestIV. We believe
that the limitations of the regression adjustment approach in this case are
potentially attributable to the fact that it only exploits distributional
information on the mean and variance of measurement error, essentially
ignoring other distributional information. As a final note, we acknowledge
that alternative methodologies which have seen recent theoretical development
in the generated regressors literature (or the econometrics literature at
large) may achieve better bias correction results than ForestIV in certain
situations. As such, we believe this to be a potentially quite fruitful future
research direction by which our method could be improved upon.

##  Appendix H Proofs of Theoretical Results

See 1

###### Proof.

Adopting notations from Breiman,  (2001), as the number of trees in the random
forest goes to infinity, the generalization error of the forest is denoted as
$PE(forest)=\lim_{M\rightarrow\infty}\mathbb{E}_{\mathbf{f}}[\widehat{X}-X]^{2}$.
Next, we restate two known results as lemmas.

######  Lemma 1.

(Breiman, , 2001, Theorem 11.2.)
$PE(forest)=\mathbb{E}_{i}\mathbb{E}_{j}\mathbb{E}_{\mathbf{f}}Cov(e^{(i)},e^{(j)})$.

######  Lemma 2.

(Scornet et al., , 2015, Theorem 1) Under Assumptions 1-2 ,
$\lim_{n\rightarrow\infty}PE(forest)=0$.

The two lemmas collectively imply that
$\lim_{n\rightarrow\infty}\mathbb{E}_{i}\mathbb{E}_{j}\mathbb{E}_{\mathbf{f}}Cov(e^{(i)},e^{(j)})=0$.
It follows that

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}_{i}\mathbb{E}_{j}\mathbb{E}_{\mathbf{f}}Cov(e^{(i)},e^{(j)})=0$
$\displaystyle\Leftrightarrow$
$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}_{i}\mathbb{E}_{j}\mathbb{E}_{\mathbf{f}}Cov\left(e^{(i)},(\widehat{X}^{(j)}-X)\right)=0$
$\displaystyle\Leftrightarrow$
$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}_{i}\mathbb{E}_{j}\mathbb{E}_{\mathbf{f}}Cov(e^{(i)},\widehat{X}^{(j)})-\lim_{n\rightarrow\infty}\mathbb{E}_{i}\mathbb{E}_{\mathbf{f}}Cov(e^{(i)},X)=0$

Based on Assumption 3 (classical measurement error),
$\lim_{n\rightarrow\infty}\mathbb{E}_{i}\mathbb{E}_{\mathbf{f}}Cov(e^{(i)},X)=0$.
Therefore, we have
$\lim_{n\rightarrow\infty}\mathbb{E}_{i}\mathbb{E}_{j}\mathbb{E}_{\mathbf{f}}Cov(\widehat{X}^{(j)},e^{(i)})=0$.
∎

See 2

###### Proof.

Breiman,  (2001) proves that the error rate of a random forest decreases with
$\mathbb{E}_{j}\mathbb{E}_{i}\left[Corr(rmg(\widehat{X}^{(i)}),rmg(\widehat{X}^{(j)}))\right]$,
where $rmg(\widehat{X}^{(i)})$ represents the raw marginal function of tree
$i$’s predictions. Under binary classification, the raw marginal function is
defined as
$rmg(\widehat{X}^{(i)})=\mathbb{I}(\widehat{X}^{(i)}=X)-\mathbb{I}(\widehat{X}^{(i)}\neq
X)$, where $\mathbb{I}$ is an indicator function that checks vectors
$\widehat{X}^{(i)}$ and $X$ element-wise, and takes value 1 if the enclosed
relationship is true or 0 otherwise. In other words,
$\mathbb{I}(\widehat{X}^{(i)}=X)$ is a vector where correct predictions are
marked with 1, and $\mathbb{I}(\widehat{X}^{(i)}\neq X)$ is a vector where
incorrect predictions are marked with 1. Denote $\boldsymbol{1}=(1,\dots,1)$
as a vector of 1 with the same length as the vector of predictions. Clearly,
we have
$\mathbb{I}(\widehat{X}^{(i)}=X)=\boldsymbol{1}-\mathbb{I}(\widehat{X}^{(i)}\neq
X)$, and $\mathbb{I}(\widehat{X}^{(i)}\neq X)=|e^{(i)}|$. Therefore, we know
$Corr((rmg(\widehat{X}^{(i)}),rmg(\widehat{X}^{(j)}))=Corr(\mathbb{I}(\widehat{X}^{(i)}=X)-\mathbb{I}(\widehat{X}^{(i)}\neq
X),\mathbb{I}(\widehat{X}^{(j)}=X)-\mathbb{I}(\widehat{X}^{(j)}\neq
X))=Corr(\boldsymbol{1}-2\mathbb{I}(\widehat{X}^{(i)}\neq
X),\boldsymbol{1}-2\mathbb{I}(\widehat{X}^{(j)}\neq
X))=Corr(\mathbb{I}(\widehat{X}^{(i)}\neq X),\mathbb{I}(\widehat{X}^{(j)}\neq
X))=Corr(|e^{(i)}|,|e^{(j)}|)$. ∎

See 3

###### Proof.

We prove this theorem for a given sample with size $N$. For notational
simplicity, write the ground truth as $X=\\{a_{k}\\}_{k=1}^{N}$, and similarly
write the prediction vector and error vector of tree $i$ as
$\widehat{X}^{(i)}=\\{p_{ik}\\}_{k=1}^{N}$, $e^{(i)}=\\{e_{ik}\\}_{k=1}^{N}$.
Suppose the number of data points where $a_{k}=\alpha$ and $p_{ik}=\beta$ is
$n_{\alpha\beta}$ ($\alpha,\beta\in\\{0,1\\}$). Clearly,
$n_{00}+n_{01}+n_{10}+n_{11}=N$, and the relationship between $X$ and
$e^{(i)}$ is fully described as follows:

  * •

There are $n_{00}$ data points where $a_{k}=0$ and $e_{ik}=0$;

  * •

There are $n_{01}$ data points where $a_{k}=0$ and $e_{ik}=1$;

  * •

There are $n_{10}$ data points where $a_{k}=1$ and $e_{ik}=-1$;

  * •

There are $n_{11}$ data points where $a_{k}=1$ and $e_{ik}=0$.

Next, write $Cov(e^{(i)},X)=\dfrac{1}{N^{2}}(N\sum e_{ik}a_{k}-\sum e_{ik}\sum
a_{k})$. Note that $\sum e_{ik}a_{k}=-n_{10}$, $\sum e_{ik}=n_{01}-n_{10}$,
and $\sum a_{k}=n_{10}+n_{11}$. Therefore, we have $N\sum e_{ik}a_{k}-\sum
e_{ik}\sum
a_{k}=-(n_{00}+n_{01}+n_{10}+n_{11})n_{10}-(n_{01}-n_{10})(n_{10}+n_{11})=-n_{00}n_{10}-2n_{01}n_{10}-n_{01}n_{11}<0$,
and accordingly, $Cov(e^{(i)},X)<0$. ∎

See 4

###### Proof.

Similarly, we prove this theorem for a given sample with size $N$. Again, we
write the ground truth as $X=\\{a_{k}\\}_{k=1}^{N}$, and write the prediction
vector and error vector of tree $i$ as
$\widehat{X}^{(i)}=\\{p_{ik}\\}_{k=1}^{N}$, $e^{(i)}=\\{e_{ik}\\}_{k=1}^{N}$.
First, we lay out all possible value combinations of
$a_{k},p_{ik},p_{jk},e_{ik},e_{jk}$ in the following table:

$a_{k}$ | $p_{ik}$ | $p_{jk}$ | Count | $e_{ik}$ | $e_{jk}$ | Abbr. Count Notation
---|---|---|---|---|---|---
0 | 0 | 0 | $n_{000}=N\times p_{000}$ | 0 | 0 | $n_{1}$
0 | 1 | 0 | $n_{010}=N\times p_{010}$ | 1 | 0 | $n_{2}$
0 | 0 | 1 | $n_{001}=N\times p_{001}$ | 0 | 1 | $n_{3}$
0 | 1 | 1 | $n_{011}=N\times p_{011}$ | 1 | 1 | $n_{4}$
1 | 0 | 0 | $n_{100}=N\times p_{100}$ | -1 | -1 | $n_{5}$
1 | 1 | 0 | $n_{110}=N\times p_{110}$ | 0 | -1 | $n_{6}$
1 | 0 | 1 | $n_{101}=N\times p_{101}$ | -1 | 0 | $n_{7}$
1 | 1 | 1 | $n_{111}=N\times p_{111}$ | 0 | 0 | $n_{8}$

Next, write $Cov(e^{(i)},e^{(j)})=\dfrac{1}{N^{2}}(N\sum e_{ik}e_{jk}-\sum
e_{ik}\sum e_{jk})$. Note that $\sum e_{ik}e_{jk}=n_{4}+n_{5}$, $\sum
e_{ik}=(n_{2}+n_{4})-(n_{5}+n_{7})$, and $\sum
e_{jk}=(n_{3}+n_{4})-(n_{5}+n_{6})$. Then, $N\sum e_{ik}e_{jk}-\sum e_{ik}\sum
e_{jk}=(n_{1}+\dots+n_{8})(n_{4}+n_{5})-[(n_{2}+n_{4})-(n_{5}+n_{7})][(n_{3}+n_{4})-(n_{5}+n_{6})]$.
Denote $A=(n_{1}+\dots+n_{8})(n_{4}+n_{5})$ and
$B=[(n_{2}+n_{4})-(n_{5}+n_{7})][(n_{3}+n_{4})-(n_{5}+n_{6})]$, we calculate
the two quantities separately as follows.

First, we rewrite

$\begin{split}A&=(n_{1}+\dots+n_{8})n_{4}+(n_{1}+\dots+n_{8})n_{5}\\\
&=(n_{1}+n_{8})(n_{4}+n_{5})+(n_{2}+n_{3}+n_{4})n_{4}+(n_{5}+n_{6}+n_{7})n_{4}+(n_{2}+n_{3}+n_{4})n_{5}+(n_{5}+n_{6}+n_{7})n_{5}\\\
\end{split}$

Second, we rewrite

$\begin{split}B&=(n_{2}n_{3}+n_{2}n_{4}+n_{3}n_{4}+n_{4}^{2})+(n_{6}n_{7}+n_{5}n_{6}+n_{5}n_{7}+n_{5}^{2})\\\
&\quad\quad-(n_{2}n_{5}+n_{4}n_{5}+n_{2}n_{6}+n_{4}n_{6})-(n_{3}n_{5}+n_{3}n_{7}+n_{4}n_{5}+n_{4}n_{7})\\\
&=(n_{2}n_{3}+n_{6}n_{7}-n_{2}n_{6}-n_{3}n_{7})+(n_{2}+n_{3}+n_{4})n_{4}+(n_{5}+n_{6}+n_{7})n_{5}\\\
&\quad\quad-(n_{5}+n_{6}+n_{7})n_{4}-(n_{2}+n_{3}+n_{4})n_{5}\\\ \end{split}$

Together, we have $N\sum e_{ik}e_{jk}-\sum e_{ik}\sum
e_{jk}=A-B=(n_{1}+n_{8})(n_{4}+n_{5})+2(n_{5}+n_{6}+n_{7})n_{4}+2(n_{2}+n_{3}+n_{4})n_{5}+(n_{2}n_{6}+n_{3}n_{7}-n_{2}n_{3}-n_{6}n_{7})=(n_{1}+n_{8})(n_{4}+n_{5})+2(n_{5}+n_{6}+n_{7})n_{4}+2(n_{2}+n_{3}+n_{4})n_{5}+(n_{2}-n_{7})(n_{6}-n_{3})$.
Using the original count notations, the right-hand-side is equivalent to
$(n_{000}+n_{111})(n_{011}+n_{100})+2(n_{0\bullet\bullet}-n_{000})n_{100}+2(n_{1\bullet\bullet}-n_{111})n_{011}+(n_{010}-n_{101})(n_{110}-n_{001})$.
Therefore, we have
$Cov(e^{(i)},e^{(j)})>0\Leftrightarrow\frac{1}{N^{2}}[(n_{000}+n_{111})(n_{011}+n_{100})+2(n_{0\bullet\bullet}-n_{000})n_{100}+2(n_{1\bullet\bullet}-n_{111})n_{011}+(n_{010}-n_{101})(n_{110}-n_{001})]>0\Leftrightarrow(p_{000}+p_{111})(p_{011}+p_{100})+2(p_{0\bullet\bullet}-p_{000})p_{100}+2(p_{1\bullet\bullet}-p_{111})p_{011}+(p_{010}-p_{101})(p_{110}-p_{001})>0$.
∎

##  Appendix I Using ForestIV in Practice

In practice, because true coefficients are not known a priori, it is useful to
have a few guidelines to gauge the effectiveness of ForestIV in a particular
finite sample.

  1. 1.

Using the hold-out dataset (e.g., $D_{test}$), researchers can empirically
evaluate instrument validity and strength, both before and after the proposed
two-step lasso-based selections.

  2. 2.

The Hotelling $T^{2}$ test statistic can also be a useful signal. The
$p$-value associated with the Hotelling $T^{2}$ test comparing
$\widehat{\boldsymbol{\beta}}_{label}$ and ForestIV estimates indicates the
probability of observing their empirical differences under the null of
equality. Researchers can define the threshold of evidence they require before
accepting ForestIV estimates, by adjusting the significance level for this
test.

  3. 3.

Researchers can also examine whether the asymptotic properties of ForestIV
have yet to “kick-in” by examining empirical convergence in resulting
coefficient estimates as the procedure is exposed to more unlabeled data. If a
convergence plot indicates that the coefficient estimates have not yet
plateaued, this may be a sign that ForestIV estimates have not yet converged,
and that more unlabeled data is perhaps needed.

Finally, to better delineate the use case of ForestIV, we reiterate that if
the size of labeled data is large enough that
$\widehat{\boldsymbol{\beta}}_{label}$ can be estimated reliably and precisely
enough using only the available labeled data, then there is no need to mine
variables in the first place. One should simply take
$\widehat{\boldsymbol{\beta}}_{label}$ and proceed with inferences and
decision making. Accordingly, statistical power analyses are likely to be
useful when determining whether “big data” and machine learning methods are
needed for a particular inference problem (Ellis, , 2010).

## References

  * Aggarwal, (2015) Aggarwal, C. C. (2015).  Data mining: the textbook.  Springer.
  * Angrist and Krueger, (1995) Angrist, J. D. and Krueger, A. B. (1995).  Split-sample instrumental variables estimates of the return to schooling.  Journal of Business & Economic Statistics, 13(2):225–235.
  * Angrist and Pischke, (2008) Angrist, J. D. and Pischke, J.-S. (2008).  Mostly harmless econometrics: An empiricist’s companion.  Princeton university press.
  * Angwin et al., (2016) Angwin, J., Larson, J., Mattu, S., and Kirchner, L. (2016).  Machine bias.  ProPublica, May, 23.
  * Athey and Imbens, (2016) Athey, S. and Imbens, G. (2016).  Recursive partitioning for heterogeneous causal effects.  Proceedings of the National Academy of Sciences, 113(27):7353–7360.
  * Athey and Imbens, (2017) Athey, S. and Imbens, G. W. (2017).  The state of applied econometrics: Causality and policy evaluation.  Journal of Economic Perspectives, 31(2):3–32.
  * Belloni et al., (2012) Belloni, A., Chen, D., Chernozhukov, V., and Hansen, C. (2012).  Sparse models and methods for optimal instruments with an application to eminent domain.  Econometrica, 80(6):2369–2429.
  * Bernard et al., (2012) Bernard, S., Adam, S., and Heutte, L. (2012).  Dynamic random forests.  Pattern Recognition Letters, 33(12):1580–1586.
  * Bernard et al., (2010) Bernard, S., Heutte, L., and Adam, S. (2010).  A study of strength and correlation in random forests.  In International Conference on Intelligent Computing, pages 186–191. Springer.
  * Blackburn and Neumark, (1992) Blackburn, M. and Neumark, D. (1992).  Unobserved ability, efficiency wages, and interindustry wage differentials.  Quarterly Journal of Economics, 107(4):1421–1436.
  * Blaser and Fryzlewicz, (2016) Blaser, R. and Fryzlewicz, P. (2016).  Random rotation ensembles.  The Journal of Machine Learning Research, 17(1):126–151.
  * Blundell and Powell, (2004) Blundell, R. W. and Powell, J. L. (2004).  Endogeneity in semiparametric binary response models.  The Review of Economic Studies, 71(3):655–679.
  * Breiman, (1996) Breiman, L. (1996).  Bagging predictors.  Machine learning, 24(2):123–140.
  * Breiman, (2001) Breiman, L. (2001).  Random forests.  Machine Learning, 45(1):5–32.
  * Buolamwini and Gebru, (2018) Buolamwini, J. and Gebru, T. (2018).  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In Conference on Fairness, Accountability and Transparency, pages 77–91.
  * Buse, (1992) Buse, A. (1992).  The bias of instrumental variable estimators.  Econometrica: Journal of the Econometric Society, pages 173–180.
  * Carroll et al., (1999) Carroll, R. J., Maca, J. D., and Ruppert, D. (1999).  Nonparametric regression in the presences of measurement error.  Biometrika, 86(3):541.
  * Chernozhukov et al., (2016) Chernozhukov, V., Chetverikov, D., Demirer, M., Duflo, E., Hansen, C., and Newey, W. K. (2016).  Double machine learning for treatment and causal parameters.  Technical report, cemmap working paper.
  * Conley et al., (2012) Conley, T. G., Hansen, C. B., and Rossi, P. E. (2012).  Plausibly exogenous.  Review of Economics and Statistics, 94(1):260–272.
  * Cook and Stefanski, (1994) Cook, J. and Stefanski, L. (1994).  Simulation-extrapolation estimation in parametric measurement error models.  Journal of the American Statistical Association, 89(428):1314–1328.
  * Denisko and Hoffman, (2018) Denisko, D. and Hoffman, M. M. (2018).  Classification and interaction in random forests.  Proceedings of the National Academy of Sciences, page 201800256\.
  * Ebbes et al., (2009) Ebbes, P., Wedel, M., and Böckenholt, U. (2009).  Frugal iv alternatives to identify the parameter for an endogenous regressor.  Journal of Applied Econometrics, 24(3):446–468.
  * Ebbes et al., (2005) Ebbes, P., Wedel, M., Böckenholt, U., and Steerneman, T. (2005).  Solving and testing for regressor-error (in) dependence when no instrumental variables are available: With new evidence for the effect of education on income.  Quantitative Marketing and Economics, 3(4):365–392.
  * Ellis, (2010) Ellis, P. D. (2010).  The essential guide to effect sizes: Statistical power, meta-analysis, and the interpretation of research results.  Cambridge University Press.
  * Fanaee-T and Gama, (2014) Fanaee-T, H. and Gama, J. (2014).  Event labeling combining ensemble detectors and background knowledge.  Progress in Artificial Intelligence, 2(2-3):113–127.
  * Fernández-Delgado et al., (2014) Fernández-Delgado, M., Cernadas, E., Barro, S., and Amorim, D. (2014).  Do we need hundreds of classifiers to solve real world classification problems?  The Journal of Machine Learning Research, 15(1):3133–3181.
  * Fong and Tyler, (2017) Fong, C. and Tyler, M. (2017).  Regression with Classifier-Generated Covariates.  Working Paper.
  * Freund et al., (1996) Freund, Y., Schapire, R. E., et al. (1996).  Experiments with a new boosting algorithm.  In Icml, volume 96, pages 148–156. Bari, Italy.
  * Gebru et al., (2017) Gebru, T., Krause, J., Wang, Y., Chen, D., Deng, J., Aiden, E. L., and Fei-Fei, L. (2017).  Using deep learning and google street view to estimate the demographic makeup of neighborhoods across the united states.  Proceedings of the National Academy of Sciences, page 201700035\.
  * Giot and Cherrier, (2014) Giot, R. and Cherrier, R. (2014).  Predicting bikeshare system usage up to one day ahead.  In 2014 IEEE symposium on Computational Intelligence in Vehicles and Transportation Systems, pages 22–29. IEEE.
  * Goodfellow et al., (2016) Goodfellow, I., Bengio, Y., and Courville, A. (2016).  Deep Learning.  MIT press.
  * Grace, (2016) Grace, Y. Y. (2016).  Statistical Analysis with Measurement Error Or Misclassification.  Springer.
  * Greene, (2003) Greene, W. H. (2003).  Econometric analysis.  Pearson Education India.
  * Gustafson, (2003) Gustafson, P. (2003).  Measurement error and misclassification in statistics and epidemiology: impacts and Bayesian adjustments.  CRC Press.
  * Harrison Jr and Rubinfeld, (1978) Harrison Jr, D. and Rubinfeld, D. L. (1978).  Hedonic housing prices and the demand for clean air.  Journal of environmental economics and management, 5(1):81–102.
  * Hausman, (2001) Hausman, J. (2001).  Mismeasured variables in econometric analysis: problems from the right and problems from the left.  Journal of Economic Perspectives, 15(4):57–67.
  * Hausman et al., (1991) Hausman, J., Newey, W., Ichimura, H., and Powell, J. (1991).  Measurement errors in polynomial regression models.  Journal of Econometrics, 50(3):273–295.
  * Hausman et al., (1995) Hausman, J. A., Newey, W. K., and Powell, J. L. (1995).  Nonlinear errors in variables estimation of some engel curves.  Journal of Econometrics, 65(1):205–233.
  * Jelveh et al., (2015) Jelveh, Z., Kogut, B., and Naidu, S. (2015).  Political language in economics.  Working Paper.
  * Küchenhoff et al., (2007) Küchenhoff, H., Lederer, W., and Lesaffre, E. (2007).  Asymptotic variance estimation for the misclassification SIMEX.  Computational Statistics and Data Analysis, 51(12):6197–6211.
  * Küchenhoff et al., (2006) Küchenhoff, H., Mwalili, S. M., and Lesaffre, E. (2006).  A general method for dealing with misclassification in regression: The misclassification SIMEX.  Biometrics, 62(1):85–96.
  * Lewbel, (2019) Lewbel, A. (2019).  Using instrumental variables to estimate models with mismeasured regressors.  Working Paper.
  * Li, (2002) Li, T. (2002).  Robust and consistent estimation of nonlinear errors-in-variables models.  Journal of Econometrics, 110(1):1–26.
  * Lim et al., (2000) Lim, T.-S., Loh, W.-Y., and Shih, Y.-S. (2000).  A comparison of prediction accuracy, complexity, and training time of thirty-three old and new classification algorithms.  Machine learning, 40(3):203–228.
  * Loken and Gelman, (2017) Loken, E. and Gelman, A. (2017).  Measurement error and the replication crisis.  Science, 355(6325):584–585.
  * Mammen et al., (2016) Mammen, E., Rothe, C., and Schienle, M. (2016).  Semiparametric estimation with generated covariates.  Econometric Theory, 32(5):1140–1177.
  * Mammen et al., (2012) Mammen, E., Rothe, C., Schienle, M., et al. (2012).  Nonparametric regression with nonparametrically generated covariates.  The Annals of Statistics, 40(2):1132–1170.
  * McFowland III et al., (2018) McFowland III, E., Somanchi, S., and Neill, D. B. (2018).  Efficient discovery of heterogeneous treatment effects in randomized experiments via anomalous pattern detection.  arXiv preprint arXiv:1803.09159.
  * Meng et al., (2016) Meng, L., Wu, B., and Zhan, Z. (2016).  Linear regression with an estimated regressor: applications to aggregate indicators of economic development.  Empirical Economics, 50(2):299–316.
  * Moro et al., (2014) Moro, S., Cortez, P., and Rita, P. (2014).  A data-driven approach to predict the success of bank telemarketing.  Decision Support Systems, 62:22–31.
  * Murphy and Topel, (1985) Murphy, K. M. and Topel, R. H. (1985).  Estimation and inference in two-step econometric models.  Journal of Business & Economic Statistics, 20(1):88–97.
  * Murray, (2006) Murray, M. P. (2006).  Avoiding invalid instruments and coping with weak instruments.  Journal of economic Perspectives, 20(4):111–132.
  * Nagar, (1959) Nagar, A. L. (1959).  The bias and moment matrix of the general k-class estimators of the parameters in simultaneous equations.  Econometrica: Journal of the Econometric Society, pages 575–595.
  * Newey, (1984) Newey, W. K. (1984).  A method of moments interpretation of sequential estimators.  Economics Letters, 14(2-3):201–206.
  * Newey, (2001) Newey, W. K. (2001).  Flexible simulated moment estimation of nonlinear errors-in-variables models.  Review of Economics and statistics, 83(4):616–627.
  * Oxley and McAleer, (1993) Oxley, L. and McAleer, M. (1993).  Econometric issues in macroeconomic models with generated regressors.  Journal of Economic Surveys, 7(1):1–40.
  * Pagan, (1984) Pagan, A. (1984).  Econometric issues in the analysis of regressions with generated regressors.  International Economic Review, pages 221–247.
  * Roodman, (2009) Roodman, D. (2009).  A note on the theme of too many instruments.  Oxford Bulletin of Economics and Statistics, 71(1):135–158.
  * Rose, (1998) Rose, K. (1998).  Deterministic annealing for clustering, compression, classification, regression, and related optimization problems.  Proceedings of the IEEE, 86(11):2210–2239.
  * Ryu et al., (2018) Ryu, J. Y., Kim, H. U., and Lee, S. Y. (2018).  Deep learning improves prediction of drug–drug and drug–food interactions.  Proceedings of the National Academy of Sciences, 115(18):E4304–E4311.
  * Schennach, (2004) Schennach, S. M. (2004).  Estimation of nonlinear models with measurement error.  Econometrica, 72(1):33–75.
  * Schennach, (2016) Schennach, S. M. (2016).  Recent advances in the measurement error literature.  Annual Review of Economics, 8:341–377.
  * Schennach and Hu, (2013) Schennach, S. M. and Hu, Y. (2013).  Nonparametric identification and semiparametric estimation of classical measurement error models without side information.  Journal of the American Statistical Association, 108(501):177–186.
  * Scornet et al., (2015) Scornet, E., Biau, G., Vert, J.-P., et al. (2015).  Consistency of random forests.  The Annals of Statistics, 43(4):1716–1741.
  * Seber, (2009) Seber, G. A. (2009).  Multivariate Observations, volume 252.  John Wiley & Sons.
  * Sperlich, (2009) Sperlich, S. (2009).  A note on non-parametric estimation with predicted variables.  The Econometrics Journal, 12(2):382–395.
  * Verikas et al., (2011) Verikas, A., Gelzinis, A., and Bacauskiene, M. (2011).  Mining data with random forests: A survey and results of new tests.  Pattern recognition, 44(2):330–349.
  * Wang and Lin, (1998) Wang, N. and Lin, X. (1998).  Bias analysis and SIMEX approach in generalized linear mixed measurement error models.  Journal of the American Statistical Association, 93:249–261.
  * Wolberg and Mangasarian, (1990) Wolberg, W. H. and Mangasarian, O. L. (1990).  Multisurface method of pattern separation for medical diagnosis applied to breast cytology.  Proceedings of the national academy of sciences, 87(23):9193–9196.
  * Wooldridge, (2002) Wooldridge, J. M. (2002).  Econometric analysis of cross section and panel data.  MIT Press, Cambridge and London.
  * Yang et al., (2018) Yang, M., Adomavicius, G., Burtch, G., and Ren, Y. (2018).  Mind the gap: Accounting for measurement error and misclassification in variables generated via data mining.  Information Systems Research, 29(1):4–24.