# Classifying with Uncertain Data Envelopment Analysis

Casey Garnera† and Allen Holder${}^{\,b^{*}\dagger}$

${}^{a}\,$Department of Mathematics, University of Minnesota, Minneapolis, MN,
USA<EMAIL_ADDRESS>
${}^{b}\,$Department of Mathematics, Rose-Hulman Institute of Technology,
Terre Haute, IN, USA<EMAIL_ADDRESS>
∗Corresponding author
${}^{\dagger}\,$ authors listed alphabetically and contributed equally,
research conducted at Rose-Hulman Institute of Technology

###### Abstract

Classifications organize entities into categories that identify similarities
within a category and discern dissimilarities among categories, and they
powerfully classify information in support of analysis. We propose a new
classification scheme premised on the reality of imperfect data. Our
computational model uses uncertain data envelopment analysis to define a
classification’s proximity to equitable efficiency, which is an aggregate
measure of intra-similarity within a classification’s categories. Our
classification process has two overriding computational challenges, those
being a loss of convexity and a combinatorially explosive search space. We
overcome the first by establishing lower and upper bounds on the proximity
value, and then by searching this range with a first-order algorithm. We
overcome the second by adapting the p-median problem to initiate our
exploration, and by then employing an iterative neighborhood search to
finalize a classification. We conclude by classifying the thirty stocks in the
Dow Jones Industrial average into performant tiers and by classifying prostate
treatments into clinically effectual categories.

Keywords: Data Envelopment Analysis, Robust Optimization,
Classification, Clustering

##  1 Motivation and Introduction

Classifications are ubiquitous and essential constructs across the human
experience, a reality motivated by the fact that we learn through association
and disassociation. Indeed, our thoughts are replete with comparisons and
contrasts among known and novel aspects of our understanding, and we routinely
toil to organize and group information into like collections for myriad
purposes. This overriding narrative to categorize information manifests itself
in the joys of life, say by classifying literature, art, food, and sport; it
promotes scientific progress by delineating the fields of study and by
interpreting the results of experimentation; and it aids innovation in fields
like engineering, healthcare, and politics as we study how the practical
benefits of basic research can promote the general welfare.

The classification concept has not escaped mathematical and practical study,
and the process of dividing entities into categories has a long and fruitful
history. The literature on how to classify is consequently substantial, well
studied, broad in application, and methodologically diverse as illustrated by
the following compendious list.

decision trees [34] | integer programming [3]
---|---
neural networks [35] | robust statistics [11]
Bayesian networks [25] | discriminant analysis [15]
graph clustering [30] | data mining [23]

Additional classification techniques, along with numerous citations, are
reviewed in [6, 17, 19, 29]. This disciplinary range challenges having a
categorical language that would promote shared efforts across disciplines, and
while all of mathematics, computer science, statistics, probability, data
science, operations research, and machine learning dabble with similar
classification problems, they each scope their problems in terms apropos for
their specific tasks, see [17, 20] for related comments. We use the term
classification diffusely to simply mean that entities are partitioned into
categories, and we refrain from related terms like clustering and grouping
that have more refined definitions in some settings.

We propose a classification technique motivated by uncertain data envelopment
analysis (uDEA) that scores a classification by how intra-equitable its
categories are. Our fundamental assumptions are that:

  1. 1.

classifications of the same entities are to be compared on a
common set of characteristics, and

  2. 2.

the characteristics are imperfect.

The assumption of imperfect characteristics is surely an anticipated general
rule and not a rare oddity; after all, a lack of preciseness taints everything
from scientific experimentation, to expert opinion, and to rule based
delineation. We do not make any stochastic assumption, and hence, we bypass
all hassle of verifying distributional suppositions. That said, we can
interpret our model stochastically if such an interpretation appropriately
aids analysis. We instead use the modern concept of uncertainty associated
with robust optimization to account for imperfect information, and our model
builds from the work in [8] to leverage uncertainty toward the goal of
establishing equity within a classification’s categories. We comment that data
envelopment analysis (DEA) is not new to the processes of clustering and
classification, see [4, 26, 32] as illustrative examples.

Sections 2 and 3 define the proximity to equitable efficiency and give an
algorithm to approximate its value. We present our classification scheme in
Section 4, and we review examples in finance and medicine in Section 5. Note
that all norms are $2$-norms unless otherwise noted, although we explicitly
denote all norms in the proof of Theorem 1 to avoid confusion.

##  2 Proximity to Equitable Efficiency

We define an assessment metric that models the quality of a classification.
Assume $\mathcal{O}=\left\\{o^{t}:t=1,2,...T\right\\}$ is a finite set of
objects that are to be partitioned into the nonempty disjoint categories
$C^{s}$, for $s=1,2,...,S$. So each $o^{t}$ is in some $C^{s}$, and
$\mathcal{C}=\\{C^{s}:s=1,2,...,S\\}$ partitions $\mathcal{O}$. We assess a
classification $\mathcal{C}$ by defining a measure of the intra-similarity of
the elements within the individual categories $C^{s}$, and the
classification’s overall quality then equates to the sum of its categorical
values.

Characteristics describe individual objects, and we assume that a
classification’s quality coincides with some of these characteristics being
small and some of them being large. Our language here agrees with the DEA
literature, see [5, 10, 16, 22] as reviews, and characteristics whose decrease
signifies improvement are called input-characteristics, or more simply inputs,
and those whose increase signifies improvement are called output-
characteristics, or more simply outputs. We let

$\begin{array}[]{rl}\displaystyle X^{s}_{it}&\mbox{be the value of the $i$-th
input-characteristic of object $t$ in category $C^{s}$, and}\\\\[4.0pt]
\displaystyle Y^{s}_{it}&\mbox{be the value of the $i$-th output-
characteristic of object $t$ in category $C^{s}$.}\end{array}$

We assume there are $N$ inputs and $M$ outputs, making $X^{s}$ an
$N\times|C^{s}|$ matrix and $Y^{s}$ an $M\times|C^{s}|$ matrix.

We employ the concept of efficiency from DEA, and the objects within a
category are our decision making units (DMUs). An object’s efficiency within
its category is measured as a ratio of weighted sums, with the numerator being
an aggregate of the output-characteristics and the denominator being an
aggregate of the input-characteristics. The primary goal of DEA is to decide
nonnegative weighting parameters to maximize an object’s efficiency while
maintaining that each object’s efficiency is no greater than one with the same
weights. There are several standard variants of this central theme, and we
select the canonical input oriented model with variable returns to scale [5].
We specifically chose to calculate efficiency with the dual of the LP that
maximizes the efficiency score for object $t$, which is

$E^{t}=\mbox{min}\left\\{c^{T}\eta:A^{t}\eta\leq 0,\,B\eta=e,\,\eta\geq
0\right\\},$ (1)

provided that

$A^{t}=\left[\begin{array}[]{c|c|c}-Y^{s}&y^{t}&0\\\ \hline\cr
X^{s}&0&-x^{t}\end{array}\right],\;B=\left[\begin{array}[]{c|c|c}e^{T}&0&0\\\
\hline\cr 0&1&0\end{array}\right],\;\mbox{ and
}\;c=\left(\begin{array}[]{c}0\\\ 0\\\ \vdots\\\ 0\\\ 1\end{array}\right),$

with $o^{t}\in C^{s}$ and $x^{t}$ and $y^{t}$ being the respective $t$-columns
of $X^{s}$ and $Y^{s}$. The all ones column vector is $e$, with its length
being decided by the context of its use. Note that

$\begin{array}[]{l}\displaystyle\hat{\eta\,}^{T}=\left(0,0,\ldots,0,1,0,\ldots,0,1,1\right)\\\\[4.0pt]
\hskip 31.3pt\mbox{position $t$ }\raisebox{4.0pt}{$\uparrow$}\end{array}$ (2)

is always feasible, and hence, $E^{t}\leq 1$. The value of $E^{t}$ is the
efficiency score of object $t$ relative to its category, and if this score is
less than one, then object $t$ is inefficient in its category. Inefficiency
means that another object’s efficiency score within the category bests the
efficiency score of object $t$ no matter how the inputs and outputs are
weighted.

Our assumption of uncertain information indicates that $E^{t}$ is likely
imprecise and that an inefficiency could be the result of inaccurate data. The
uDEA problem in [8] addresses this concern by acknowledging and modeling
uncertainty and by recasting the efficiency score as a robust linear program.
The solution of the robust linear program maximizes an object’s efficiency
score by selecting a best collection of data from among the uncertain
possibilities. Thus an inefficient object based on the original data might
become efficient with a prudent and reasonable selection of new data from a
set of uncertain options. We note that several modes of robust DEA are now
proposed and that applications are increasing, see [24] and its bibliography
as a review, as well as the more recent publications [28, 33].

We use an ellipsoidal model of uncertainty for each row of $A^{t}$, and
denoting the $i$-th row of $A^{t}$ by $A_{i}^{t}$, we set

$\mathcal{U}_{i}^{t}(\sigma_{i})=\\{A_{i}^{t}+\sigma_{i}\,u^{T}R_{i}:||u||_{2}\leq
1\\}.$

The scalar $\sigma_{i}$ is assumed to be nonnegative, and the matrix $R_{i}$
has $|C^{s}|+2$ columns along with a compatible number of rows to align with
the dimension of the vector $u$. The matrix $R_{i}$ defines the structure of
uncertainty, whereas $\sigma_{i}$ scales this structure to shrink or enlarge
the amount of uncertainty.

The format of $A^{t}$ imposes a concomitant format on $R_{i}$. The last two
columns of $A^{t}$ duplicate the input- and output-characteristics of object
$t$, and $R_{i}$ must maintain this format. Assume for illustrative purposes
that $t=2\in C^{s}$ corresponds with the second column of data in $X^{s}$ and
$Y^{s}$. Then, if

$X^{s}=\left[\begin{array}[]{cc}1.2\;,&0.8\end{array}\right]\;\mbox{ and
}\;Y^{s}=\left[\begin{array}[]{cc}0.9&0.5\\\ 0.6&0.7\end{array}\right],$

we have

$A^{2}=\left[\begin{array}[]{rr|r|r}-0.9&-0.5&0.5&\lx@intercol\hfil
0\hfil\lx@intercol\\\ -0.6&-0.7&0.7&\lx@intercol\hfil 0\hfil\lx@intercol\\\
\hline\cr 1.2&0.8&\lx@intercol\hfil
0\hfil\lx<EMAIL_ADDRESS>
Suppose our model of uncertainty for the inputs assumes a $2\times 2$ identity
with regard to $X^{s}$. Such diagonal models are commonly motivated by
probabilistic assumptions such as the characteristics being uncorrelated
random variables. We have in this case that

$R_{3}=\left[\begin{array}[]{rr|r|r}1&0&0&0\\\ 0&1&0&-1\end{array}\right],$
(3)

from which

$A^{2}_{3}+\sigma_{3}u^{T}R_{3}=\left[\begin{array}[]{cccc}1.2+\sigma_{3}u_{1},&0.8+\sigma_{3}u_{2},&0,&-0.8-\sigma_{3}u_{2}\end{array}\right].$

The last column of $R_{3}$ must be the negative of the second column for the
structures of $A^{2}_{3}$ and $A^{2}_{3}+\sigma_{3}u^{T}R_{3}$ to agree as $u$
varies over the unit disc. Violations to this structural agreement would
essentially, and erroneously, equate to the second input-characteristic of the
second object having two values as the data ranged over the uncertainty set.
Similar requirements for the output-characteristics are necessary, with
illustrative (non-identity) options for $A^{2}$ being

$R_{1}=\left[\begin{array}[]{rr|r|r}-0.2&0.1&-0.1&0\\\
0.3&-0.2&0.2&0\end{array}\right]\;\mbox{ and
}\;R_{2}=\left[\begin{array}[]{rr|r|r}0.7\,,&0.6&-0.6&0\\\
0.1\,,&-0.3&0.3&0\end{array}\right].$

We express $R_{i}$ as $[R^{\prime}_{i}\,|\,R^{\prime\prime}_{i}]$ in the
forthcoming discussion, with $R^{\prime\prime}_{i}$ having two columns and
being decided by $R^{\prime}_{i}$ as illustrated.

We let $\sigma$ be the $M+N$ vector whose $i$-th component is $\sigma_{i}$,
and we define the robust efficiency score for object $t$ with respect to
$\sigma$ as,

$\displaystyle\mathcal{E}^{t}(\sigma)$ $\displaystyle=$
$\displaystyle\mbox{min}\left\\{c^{T}\eta:\hat{A}^{t}_{i}\eta\leq
0,\;\forall\,\hat{A}^{t}_{i}\in\mathcal{U}^{t}_{i}(\sigma_{i}),\;\forall\,i,\,B\eta=e,\,\eta\geq
0\right\\}$ $\displaystyle=$
$\displaystyle\mbox{min}\left\\{c^{T}\eta:\hat{A}^{t}_{i}\eta+\sigma_{i}\,\|R_{i}\eta\|\leq
0,\;\forall\,i,\,B\eta=e,\,\eta\geq 0\right\\},$

where the second math program is the standard second-order cone expression of
the robust problem. The structure of each $R_{i}$ mandates that
$\mathcal{E}^{t}(\sigma)\leq 1$ for the same reason that $E^{t}\leq 1$, i.e.
because $\hat{\eta}$ in (2) remains feasible.

We require that $\mathcal{E}^{t}(\sigma)=1$ for sufficiently large $\sigma$, a
property that ensures object $t$ is capable of efficiency, or more succinctly
capable, if enough uncertainty is assumed. A mathematically contrived example
in [8] without ellipsoidal uncertainty shows that
$\sup\\{\mathcal{E}^{t}(\sigma):\sigma\geq 0\\}$ can be strictly less than
one, and hence, capability is not necessarily ensured and requires applicable
justification. Theorem 1 gives serviceable assurance.

######  Theorem 1.

If $R^{\prime}_{i}$ has full column rank for each $i$, then
$\mathcal{E}^{t}(\sigma)=1$ for all sufficiently large $\sigma$.

###### Proof.

Proposition 1 in [8] establishes the following general monotonicity property.
If two collections of uncertainty satisfy
$\mathcal{U}^{\prime}_{i}\subseteq\mathcal{U}^{\prime\prime}_{i}$ for each
$i$, then

$\left.\begin{array}[]{rcl}\lx@intercol\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mbox{min}\left\\{c^{T}\eta:\hat{A}^{t}_{i}\eta\leq
0,\;\forall\,\hat{A}^{t}_{i}\in\mathcal{U}^{\prime}_{i}(\sigma_{i}),\;\forall\,i,\,B\eta=e,\,\eta\geq
<EMAIL_ADDRESS>&\leq&\mbox{min}\left\\{c^{T}\eta:\hat{A}^{t}_{i}\eta\leq
0,\;\forall\,\hat{A}^{t}_{i}\in\mathcal{U}^{\prime\prime}_{i}(\sigma_{i}),\;\forall\,i,\,B\eta=e,\,\eta\geq
0\right\\}\\\\[6.0pt] &\leq&1,\end{array}\hskip 8.0pt\right\\}$ (4)

where the last inequality follows from an assumption that $\hat{\eta}$ in (2)
is feasible in both problems.

Theorem 2 in [31] guarantees the existence of $\hat{\sigma}>0$ such that
$\mathcal{E}^{t}(\sigma)=1$ if $\sigma\geq\hat{\sigma}$ and if

$\mathcal{U}_{i}=\\{A_{i}:A_{i}^{t}+\sigma
u^{T}[I\,|\,R^{\prime}_{i}]:\|u\|_{\infty}\leq 1\\}.$

So the inequalities in (4) will complete the proof upon showing that for each
$i$ and for sufficiently large $\sigma$,

$\\{A_{i}:A_{i}^{t}+\hat{\sigma}_{i}u^{T}[I\,|\,R^{\prime\prime}_{i}]:\|u\|_{\infty}\leq
1\\}\subseteq\\{A_{i}:A_{i}^{t}+\sigma_{i}u^{T}R_{i}:\|u\|_{2}\leq 1\\}.$

The required format of $R^{\prime\prime}_{i}$ in both cases reduces this
argument to showing that

$\\{\hat{\sigma}_{i}\,u^{T}:\|u\|_{\infty}\leq
1\\}\subseteq\\{\sigma_{i}\,u^{T}R^{\prime}_{i}:\|u\|_{2}\leq 1\\},$

for each $i$ and sufficiently large $\sigma$.

Fix $i$ and select $v\in\\{\hat{\sigma}_{i}\,u^{T}:\|u\|_{\infty}\leq 1\\}$.
Then $\|v\|_{2}\leq\hat{\sigma}_{i}^{\,|C^{s}|}$. Further select $\sigma_{i}$
so that its components satisfy

$\sigma_{i}\geq\hat{\sigma}_{i}^{\,|C^{s}|}\,\left\|\left(R^{\prime}_{i}\right)^{+}\right\|_{2},$

where $\left(R^{\prime}_{i}\right)^{+}$ is the Moore-Penrose pseudo-inverse so
that

$u^{T}=\frac{1}{\sigma_{i}}\;v^{T}\left(R^{\prime}_{i}\right)^{+}\;\mbox{
solves }\;u^{T}\left(\sigma_{i}R^{\prime}_{i}\right)=v^{T}.$

We now have

$\|u\|_{2}\leq\frac{1}{\sigma_{i}}\,\|v\|_{2}\,\left\|\left(R^{\prime}_{i}\right)^{+}\right\|_{2}\leq\frac{1}{\sigma_{i}}\,\hat{\sigma}_{i}^{\,|C^{s}|}\,\left\|\left(R^{\prime}_{i}\right)^{+}\right\|_{2}\leq
1,$

which establishes the result. $\;\;\blacksquare$

An immediate consequence of Theorem 1 is that invertible $R^{\prime}_{i}$
matrices ensure capability, and since common examples set $R^{\prime}_{i}$ to
be positive diagonal matrices or covariance matrices, our assumption of
capability is routine. Note also that the rank condition is sufficient but not
necessary, and that examples not satisfying the rank condition can still
result in each object being capable. Indeed, all but cleverly constructed
examples lead to the capability of each object in the authors’ experience,
making the assumption of capability prevalent and not inimical to practical
application.

We classify objects into categories so that the objects within a category
require a minimum amount of uncertainty for each of the objects to have a
claim to efficiency. So our motivating question is, how much uncertainty does
a category need for all of its objects to have a robust efficiency score of
one? We define the proximity to equitable efficiency for category $s$ to
answer this question, which is

$\mathcal{P}^{s}=\mbox{min}\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1,\;\forall\,t\in
C^{s}\right\\}.$ (5)

The constraints of this problem necessitate that each object reaches its
maximum efficiency score by selecting characteristics from the uncertainty
sets $\mathcal{U}^{t}_{i}(\sigma_{i})$, a requirement that imparts equity
among the objects within the category relative to efficiency. Note that our
proximity model does not require each object to be assessed in the same
fashion because each object can combine their characteristic values
differently to reach an efficiency score of one. A straightforward
interpretation of $\mathcal{P}^{s}$ is that it defines a minimum vicinity over
which the characteristic data can vary so that each object is equally and
maximally efficient if it were allowed to select values from the uncertain
possibilities. We comment that a different sense of equity appears in the
multiple objective literature [1, 18].

We say that a nonnegative $\sigma$ is feasible-for-classification for category
$s$ if $\mathcal{E}^{t}(\sigma)=1$ for all $t\in C^{s}$, that is, if $\sigma$
is feasible for the optimization problem defining $\mathcal{P}^{s}$. Note that
we have two properties from (4), those being:

Property 1: | if $\sigma^{\prime\prime}\geq\sigma^{\prime}$ and $\mathcal{E}^{t}(\sigma^{\prime})=1$, then $\mathcal{E}^{t}(\sigma^{\prime\prime})=1$, and
---|---
Property 2: | if $\sigma^{\prime}$ is feasible-for-classification and $\sigma^{\prime\prime}\geq\sigma^{\prime}$,
| then $\sigma^{\prime\prime}$ is also feasible-for-classification.

Property 1 shows that object $t$ maintains an efficiency score of one if
$\sigma$ surpasses what is required to satisfy $\mathcal{E}^{t}(\sigma)=1$,
which suggests that we can construct a feasible-for-classification $\sigma$ by
computing the componentwise maximums of solutions to

$\min\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1\right\\}.$

Theorem 2 confirms this suggestion and establishes both upper and lower bounds
on $\mathcal{P}^{s}$ based on this construction.

Let

${\bf\Sigma}=\left(\sigma^{1},\sigma^{2},\ldots,\sigma^{|C^{s}|}\right)\in\prod_{t\in
C^{s}}\arg\\!\min\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1\right\\},$

and let $\hat{\sigma}({\bf\Sigma})$ be the nonnegative vector whose components
are

$\hat{\sigma}_{i}({\bf\Sigma})=\max_{t}\left\\{\sigma_{i}^{t}\right\\}.$

Theorem 2 establishes upper and lower bounds on $\mathcal{P}^{s}$ in terms of
$\hat{\sigma}({\bf\Sigma})$.

######  Theorem 2.

We have for any

${\bf\Sigma}\in\prod_{t\in
C^{s}}\arg\\!\min\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1\right\\}$

that the proximity to equitable efficiency for category $s$ satisfies

$\frac{1}{\sqrt{M+N}}\,\|\hat{\sigma}({\bf\Sigma})\|\leq\mathcal{P}^{s}\leq\|\hat{\sigma}({\bf\Sigma})\|.$

###### Proof.

Select

${\bf\Sigma}=\left(\sigma^{1},\sigma^{2},\ldots,\sigma^{|C^{s}|}\right)\in\prod_{t\in
C^{s}}\arg\\!\min\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1\right\\}.$

Then $\hat{\sigma}({\bf\Sigma})\geq\sigma^{t}$ for all $t$ by definition, and
we have from Property 1 above that $\mathcal{E}^{t}(\hat{\sigma})=1$ for all
$t$. So $\hat{\sigma}({\bf\Sigma})$ is feasible-for-classification for
category $s$ and

$\mathcal{P}^{s}\leq\|\hat{\sigma}(\bf\Sigma)\|.$

The lower bound is established by first noticing that

$\sigma_{i}^{t}\leq\|\sigma^{t}\|=\min\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1\right\\}\leq\mathcal{P}^{s}\;\mbox{
for all $i$ and $t$.}$

So,

$\hat{\sigma}_{i}({\bf\Sigma})=\max_{t}\;\sigma_{i}^{t}\leq\mathcal{P}^{s}\,\;\mbox{
for all $i$}.$

We conclude that $\hat{\sigma}({\bf\Sigma})\leq\mathcal{P}^{s}\,e$, and hence,

$\|\hat{\sigma}({\bf\Sigma})\|\leq\sqrt{M+N}\;\mathcal{P}^{s},$

which completes the proof. $\;\;\blacksquare$

Two corollaries follow, the first of which is an immediate consequence of
Theorem 2.

######  Corollary 1.

The proximity to equitable efficiency for category $s$ satisfies,

$\frac{1}{\sqrt{M+N}}\,\left(\sup_{\bf\Sigma}\,\left\\{\|\hat{\sigma}({\bf\Sigma})\|\right\\}\right)\leq\mathcal{P}^{s}\leq\inf_{\bf\Sigma}\,\left\\{\|\hat{\sigma}({\bf\Sigma})\|\right\\},$

where the supremum and infemum are expressed over the collection

${\bf\Sigma}\in\prod_{t\in
C^{s}}\arg\\!\min\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1\right\\}.$

Theorem 2 can also be strengthened to show that $\mathcal{P}^{s}$ achieves its
upper bound should $\hat{\sigma}({\bf\Sigma})$ be decided by a single object.

######  Corollary 2.

If
$\hat{\sigma}({\bf\Sigma})\in\arg\\!\min\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1\right\\}$
for some $t\in C^{s}$, then

$\mathcal{P}^{s}=\|\hat{\sigma}({\bf\Sigma})\|.$

###### Proof.

Let $\hat{t}\in C^{s}$ have the property that
$\hat{\sigma}({\bf\Sigma})\in\arg\\!\min\left\\{\|\sigma\|:\mathcal{E}^{\hat{t}}(\sigma)=1\right\\}$.
Then

$\|\hat{\sigma}({\bf\Sigma})\|=\min\left\\{\|\sigma\|:\mathcal{E}^{\hat{t}}(\sigma)=1\right\\}\\\
\leq\min\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1,\;\forall\;t\in
C^{s}\right\\}\\\ =\mathcal{P}^{s},$

and the result follows because Theorem 2 gives the reverse inequality.
$\;\;\blacksquare$

We address how these mathematical results guide our computational effort to
compute $\mathcal{P}^{s}$ in the next section. However, we first note that we
assess a classification by summing the proximity values of the individual
categories, giving an overall proximity evaluation for the entire
classification. So we appraise a classification $\mathcal{C}$ with

$\mathcal{P}(\mathcal{C})=\sum_{s=1}^{S}\;\mathcal{P}^{s},$

and its value indicates how much uncertainty is needed so that all objects
have a claim to efficiency within their categories. Classifications with low
total proximity values are preferred because they partition objects into sets
that are intra-category efficient relative to low amounts of uncertainty.

##  3 Computing the Proximity to Equitable
Efficiency

Solving uDEA problems is generally difficult due to a loss of convexity, see
Example 3 in [8] as an illustration, and calculating the proximity to
equitable efficiency inherits this difficulty because Corollary 2 equates the
value of $\mathcal{P}^{s}$ to solving a uDEA problem under appropriate
conditions. A first order algorithm in [8] successfully solves uDEA problems,
and we use this algorithm to compute a $\bf\Sigma$ by iteratively solving for
each $t\in C^{s}$,

$\min\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1\right\\}.$

The resulting $\hat{\sigma}({\bf\Sigma})$ then bounds $\mathcal{P}^{s}$
according to Theorem 2, and it even computes $\mathcal{P}^{s}$ if
$\hat{\sigma}({\bf\Sigma})$ is defined by a single object, in which case
$\mathcal{P}^{s}=\|\hat{\sigma}({\bf\Sigma})\|$.

We work to calculate $\mathcal{P}^{s}$ by reducing $\hat{\sigma}({\bf\Sigma})$
if $\mathcal{P}^{s}$ is not decided by a single object. Let $\Gamma(\sigma)$
be the total sum of robust efficiency scores within the category,

$\Gamma(\sigma)=\sum_{t\in C^{s}}\mathcal{E}^{t}(\sigma).$

Then,

$\mathcal{P}^{s}=\min\left\\{\|\sigma\|:\mathcal{E}^{t}(\sigma)=1,\;\forall\,t\in
C^{s}\right\\}=\min\left\\{\|\sigma\|:\Gamma(\sigma)=|C^{s}|\right\\},$

where the last equality follows from the fact that $\Gamma(\sigma)$ is equal
to the number of objects in $C^{s}$ if and only if $\sigma$ is feasible-for-
classification. A unit-length improving direction $d$ from $\sigma$ is
calculated by solving,

$\min\left\\{d^{T}\sigma:d^{T}\nabla\Gamma(\sigma)\geq 0,\;d^{T}d\leq
1\right\\}.$ (6)

The first constraint ensures that $\sigma+\alpha d$ is marginally feasible-
for-classification, and the objective minimizes the directional derivative of
$\|\sigma\|^{2}$ along $d$ – note that we have removed the superfluous scalar
of two.

We search along the solution $d$ if the optimal value of (6) is negative, and
a straightforward calculation in this case shows that the step size $\alpha$
must satisfy

$0\leq\alpha\leq-\sigma^{T}d-\sqrt{\left(\sigma^{T}d\right)^{2}-\left(\|\sigma\|^{2}-\frac{1}{M+N}\,\|\hat{\sigma}({\bf\Sigma})\|^{2}\right)}$
(7)

to ensure that $\sigma+\alpha\,d$ does not violate the lower bound in Theorem
2. We search this interval with the method of bisection to find the largest
value of $\alpha$ guaranteeing
$\Gamma(\sigma+\alpha\,d)\geq|C^{s}|-\varepsilon$, where $\varepsilon$ is a
suitably small tolerance required by our computational study. We then update
$\sigma$, solve (6), and repeat our search for $\alpha$. The process starts
with $\sigma=\hat{\sigma}({\bf\Sigma})$ and terminates once the solution to
(6) is nonnegative.

We assumed the existence of $\nabla\Gamma$ in (6), but this vector is
approximated componentwise with the finite differences

$\frac{\partial\Gamma}{\partial\sigma_{i}}\approx\frac{\Gamma(\sigma)-\Gamma(\sigma-\delta
e_{i})}{\delta},$ (8)

where $e_{i}$ is the vector of zeros except for a one in the $i$-th position.
We note that this approximation exists even if the gradient doesn’t. The use
of a backward difference is important since the more common forward difference
would instead use $\Gamma(\sigma+\delta e_{i})$ and $\Gamma(\sigma)$. However,
$\sigma$ being feasible-for-classification implies that $\sigma+\delta e_{i}$
would also be feasible-for-classification, and hence, both
$\Gamma(\sigma+\delta e_{i})$ and $\Gamma(\sigma)$ would have the same value
and our approximate gradient would be zero. The search direction from (6)
would then be $d=-\sigma/\|\sigma\|$, making

$\sigma+\alpha d=\left(1-\frac{\alpha}{\|\sigma\|}\right)\sigma.$

The misguided computational interpretation would be that we could approximate
$\mathcal{P}^{s}$ by calculating any $\hat{\sigma}({\bf\Sigma})$ and then
scaling this vector down while satisfying

$\Gamma\left(\left(1-\frac{\alpha}{\|\hat{\sigma}({\bf\Sigma})\|}\right)\,\hat{\sigma}(\bf\Sigma)\right)\geq|C^{s}|-\varepsilon.$

So the use of a forward difference would limit the search to compute
$\mathcal{P}^{s}$ from an initial $\hat{\sigma}({\bf\Sigma})$ to a single
search direction due to the erroneous assumption that $\Gamma(\sigma)$ is
constant if $\sigma$ is in some small neighborhood of
$\hat{\sigma}({\bf\Sigma})$. The use of the backward differences removes this
concern and provides a more accurate search strategy.

Our algorithmic approach to compute $\mathcal{P}^{s}$ is:

Step 0: | Initialize |  Use the algorithm in [8] to compute a $\bf\Sigma$ and a resulting $\hat{\sigma}({\bf\Sigma})$. If $\hat{\sigma}({\bf\Sigma})$ is defined by a single object, then set $\mathcal{P}^{s}=\|\hat{\sigma}({\bf\Sigma})\|$ and stop. Otherwise, initialize $\sigma$ to $\hat{\sigma}({\bf\Sigma})$.
---|---|---
Step 1: | Search Direction |  Compute an approximate $\nabla\Gamma(\sigma)$ with (8) and then use this approximation to calculate a search direction $d$ by solving (6). Stop if $d^{T}\sigma\geq 0$.
Step 2: | Line Search |  Use the method of bisection to calculate the largest $\alpha$ satisfying $\Gamma(\sigma+\alpha d)\geq S-\varepsilon$, where $\alpha$ satisfies (7). Update $\sigma$ to $\sigma+\alpha d$ and return to Step 1.

We could add a termination criterion to stop if $\Gamma(\sigma+\alpha d)$
reached its lower bound in Step 2; however, theory indicates that the
directional derivative from (6) would be nonnegative in this case, and we use
the termination criterion in Step 1 to validate our computational scheme’s
agreement with theory. This approach has been computationally successful.

We comment that each evaluation of $\Gamma(\sigma)$ requires $|C^{s}|$ robust
optimization problems to be solved, and while the algorithmic structure above
is standard, assembling the computational effort is less so. Robust solvers
are increasingly trustworthy, but still, they lack some of the dependability
associated with other problem classes like linear programming [2, 14]. We use
Gurobi with many of the numeric options set to their most stringent
possibilities, and we validate the optimal status of each solve. Success is
routine with the increased numeric focus but is more questionable with default
settings. If a problem fails our stringent expectations, then we iteratively
relax convergent tolerances while guaranteeing optimal values, which are
efficiency scores, to at least six decimal places – so an efficiency score of
at least 0.999999 equates to 1.0. The vast majority of solves more stringently
reaches 16 decimal places of accuracy.

##  4 Classification with Uncertain Data

Our classification problem partitions the $T$ objects in $\mathcal{O}$ into
the $S$ categories in $\mathcal{C}$ in a way that (approximately) minimizes
the total proximity $\mathcal{P}(\mathcal{C})$, i.e. we seek to solve

$\min\\{\mathcal{P}(\mathcal{C}):|\mathcal{C}|=S\\}.$ (9)

The search space of this problem is combinatorially problematic for even
modest problems because its size is the Sterling number of the second kind
that counts the number of ways to disjointly partition $T$ objects into $S$
nonempty sets. To illustrate, the search spaces of the examples in the next
section are

$\left\\{\begin{array}[]{c}30\\\ 3\end{array}\right\\}\approx 3.4\times
10^{13}\mbox{ and }\left\\{\begin{array}[]{c}42\\\
3\end{array}\right\\}\approx 1.8\times 10^{19}.$

The immensity of these spaces fundamentally challenges a classification scheme
independent of how we assess individual classifications, which prompts the
need for heuristics to navigate a search. We divide our search for a (near)
optimal classification into an initialization procedure, which efficiently
solves several adapted $p$-median problems, and an iterative improvement
strategy, which is a neighborhood search that reassigns one object per
iteration.

The $p$-median problem partitions objects into sets so that the aggregate
distance from the objects within the sets to their representative medians is
as small as possible. We begin by considering the entire collection of objects
as a single classification, i.e. we do not assume a partition and originally
set $\mathcal{C}=\\{\mathcal{O}\\}$. The $p$-median problem depends on a
distance between the objects, and we let the distance between objects $t_{i}$
and $t_{j}$ be

$d(t_{i},\,t_{j})=|\,\|\sigma^{i}\|-\|\sigma^{j}\|\,|,$

where $\sigma^{i}$ and $\sigma^{j}$ respectively solve

$\min\\{\|\sigma\|:\mathcal{E}^{t^{i}}(\sigma)=1\\}\;\mbox{ and
}\;\min\\{\|\sigma\|:\mathcal{E}^{t^{j}}(\sigma)=1\\}.$

Again, these $\sigma$ vectors are relative to the entire collection of objects
and not to a proposed partition of $S$ categories; so there is no intra-
category consideration in the initialization process. The idea is that
calculating the minimum amount of uncertainty for each object against the
whole set of objects should be a reasonable proxy to seed our search to
minimize the sum of the intra-category uncertainties comprising
$\mathcal{P}(\mathcal{C})$.

We adapt the $p$-median problem to include constraints that mandate the sizes
of the sets. For instance, if we seek to classify $30$ objects into three
categories, then we solve an adapted $p$-median problem for sets whose sizes
are $(2,2,26)$, $(2,3,25)$, $(2,4,24)$, etc. If the set sizes are
$(p_{1},p_{2},\ldots,p_{S})$, then we solve

$\begin{array}[]{rrcl}\min&\lx@intercol\sum\limits_{ij}d(t_{i},t_{j})\,\zeta_{ij}\hfil\lx@intercol\\\
\mbox{subject to}&\sum\limits_{j}\zeta_{ij}&=&1,\;\forall i\\\
&\sum\limits_{j}\zeta_{jj}&=&S,\\\ &\zeta_{jj}&\geq&\zeta_{ij},\;\forall
i,j,\,i\neq j\\\ &\sum\limits_{k}\omega_{jk}&\leq&1,\;\forall j\\\
&\sum\limits_{i}\zeta_{ij}&=&\sum\limits_{k}p^{\prime}_{k}\,\omega_{jk},\;\forall
j\\\
&\sum\limits_{j}\omega_{jk}&=&|\,\\{p_{q}:p_{q}=p^{\prime}_{k}\\}\,|,\;\forall
k\\\ &\zeta_{ij}&\in&\\{0,1\\},\;\forall i,j\\\
&\omega_{jk}&\in&\\{0,1\\},\;\forall j,k,\end{array}$

where $i$ and $j$ index over $\\{1,2,\ldots,S\\}$,
$(p^{\prime}_{1},p^{\prime}_{2},\ldots,p^{\prime}_{S^{\prime}})$ lists the
unique elements of $(p_{1},p_{2},\ldots,p_{S})$, and $k$ indexes over
$\\{1,2,\ldots,S^{\prime}\\}$. The first three constraints model the
traditional $p$-median problem, whereas the next three ensure that the
partitioning sets have the specified cardinalities. We note that we do not
need to consider singletons because any set with only one or two elements
trivially has a proximity value of zero. So we solve the adapted $p$-median
for all other summative partitions of $S$, and we calculate
$\mathcal{P}(\mathcal{C})$ for each. Our initial classification is the one
with the smallest value of $\mathcal{P}(\mathcal{C})$.

Suppose $\mathcal{C}=\\{C^{1},C^{2},\ldots,C^{S}\\}$ is our initial incumbent
classification. We define a neighbor of $\mathcal{C}$ to be any classification
that moves a single object from one category to another. So
$\mathcal{C}^{\prime}$ is a neighbor of $\mathcal{C}$ if for some $s^{\prime}$
and $s^{\prime\prime}$, and for some object $o^{t}\in C^{s^{\prime}}$,

$\mathcal{C}^{\prime}=\left(\mathcal{C}\backslash\\{C^{s^{\prime}},C^{s^{\prime\prime}}\\}\right)\bigcup\left\\{C^{s^{\prime}}\backslash\\{o^{t}\\},\,C^{s^{\prime\prime}}\cup\\{o^{t}\\}\right\\}.$

From the current incumbent classification $\mathcal{C}$, we solve

$\min\\{\mathcal{P}(\mathcal{C}^{\prime}):\mathcal{C}^{\prime}\mbox{ is a
neighbor of }\mathcal{C}\\}$ (10)

by iteratively swapping each object from its current category to the other
categories. We accept a solution to (10) as the next incumbent if its value is
less than $\mathcal{P}(\mathcal{C})$, but we otherwise terminate with a final
classification. This process repeats with the updated incumbent if improvement
is found.

We conclude with a few comments about our computational process. Our
initialization and subsequent neighborhood search does not guarantee a
solution to (9). However, our adapted $p$-median problem efficiently and
efficaciously seeds our neighborhood search algorithm so that it converges in
a few iterations. Moreover, and beyond combinatorial concerns, shrewd and
judicious navigation through the collection of all possible classifications is
prudent due to the computational burden of calculating
$\mathcal{P}(\mathcal{C})$, which requires thousands of SOCP solves even on
modestly sized problems. Our two phase approach demonstrates persuasively on
the examples of the next section, and we advocate it as a reasonable and
practically justified approximation algorithm. Lastly, we have experimented
with numerous minor variations, e.g. by adjusting the distances in our adapted
$p$-median problem to $d(t_{1},t_{2})=\|\sigma^{1}-\sigma^{2}\|_{p}$ or by
tweaking the definition of a classification’s neighborhood. We considered such
adjustments in an attempt to expediting our computational task without
degrading fidelity to the goal of identifying an optimal classification, but
all adjustments either diminished outcomes or lacked computational
improvement.

##  5 Illustrative Examples

We apply our classification scheme to two problems to demonstrate its employ.
The first example partitions the 30 stocks in the Down Jones Industrial
Average into three performance tiers, and the second categorizes 42 prostrate
treatments that were originally analyzed with DEA in [22] and subsequently
with uDEA in [8, 31]. The objects, i.e. stocks and prostate treatments, have
one input and one output characteristic in each case. Single input and output
examples lend themselves to graphical inspection to help verify efficacy, and
they guarantee that the upper and lower bounds on $\mathcal{P}(\mathcal{C})$
are within $\sqrt{2}$ of each other from Theorem 2. Both examples set
$R^{\prime}_{i}=I$, so a feasible-for-classification $\sigma$ exists from
Theorem 1.

A few comments about the computational burden are worthwhile. Our code is
written in python and is available as a supplement to this article. We use
Pyomo [12] to model all optimization problems and Gurobi to solve all models.
Our initial computational testing suggested that both examples would take
about a week of serial calculation on a modern laptop, which seemed extreme. A
parallel version of the code that distributes the calculation over twelve
nodes has significantly reduced the calculation time to several hours, with
the stock example solving in about six hours and the prostate example solving
in about eight. The computational burden of classifying with regard to
uncertain data is nonetheless significant and requires careful consideration.

The input and output characteristics of each stock are respectively the semi-
deviation and the average annual return, both of which are uncertain estimates
of future values. Semi-deviation is a common measure of risk and is the
standard deviation of downside returns, whereas the average annual return is a
routine measure of reward. The risk reward trade-off is steeped in investing,
with risk adverse individuals accepting lower average returns to help
safeguard principal and risk accepting individuals jeopardizing principal as
they pursue higher returns. The input and output characteristics are
calculated from the twelve annual returns ending at the beginning of each
month in 2021.

Classifying stocks relative to efficiency with regard to risk and reward does
not preference risk or reward but instead considers them as uncertain co-equal
trade-offs, and hence, the categories tier stocks into performant classes
independent of risk tolerance. A reasonable interpretation is that Tier 1
stocks should be considered over Tier 2 or 3 stocks regardless of one’s
palatability toward risk. Tier 2 stocks should likewise be considered over
Tier 3 stocks.

Figures 4 through 4 show the progression of our classification process. Tier 1
stocks are green squares, Tier 2 stocks are blue squares, and Tier 3 stocks
are red diamonds. The outcome from the initialization process is in Figure 4,
and we note that Tier 3 can obviously add stocks from Tier 2 while maintaining
a proximity value of zero. The first two improvements identify this fact and
reduce the uncertainty of Tier 2 by moving two of its stocks to Tier 3. The
third and final improvement moves a Tier 1 stock to Tier 2, and the algorithm
identifies no subsequent improvement. Table 1 lists the categories throughout
the classification process along with the proximity values. Stocks are listed
by their ticker symbol.

Figure 1: Initial Classifications

Figure 2: First Improvement

Figure 3: Second Improvement

Figure 4: Final Classification

| Tier 1 | Tier 2 | Tier 3 | $\mathcal{P}(\mathcal{C})$
---|---|---|---|---
Initial | $\mathcal{P}^{1}=0.1361$ | $\mathcal{P}^{2}=0.0889$ | $\mathcal{P}^{3}=0.000$ | $0.2250$
| AXP,AMGN,AAPL,CAT, | AXP,CVX,CSCO,KO, | BA,WBA |
| DIS,GS,HD,HON,INTC, | DOW,IBM,JPM,TRV |  |
| JNJ,MCD,MRK,MSFT, |  |  |
| NKE,PG,CRM,UNH,VZ, |  |  |
| V,WMT |  |  |
Improvement 1 | $\mathcal{P}^{1}=0.1361$ | $\mathcal{P}^{2}=0.0646$ | $\mathcal{P}^{3}=0.000$ | $0.2001$
| AXP,AMGN,AAPL,CAT, | AXP,CSCO,KO,DOW | BA,CVX, |
| DIS,GS,HD,HON,INTC, | IBM,JPM,TRV | WBA |
| JNJ,MCD,MRK,MSFT, |  |  |
| NKE,PG,CRM,UNH,VZ, |  |  |
| V,WMT |  |  |
Improvement 2 | $\mathcal{P}^{1}=0.1361$ | $\mathcal{P}^{2}=0.0172$ | $\mathcal{P}^{3}=0.000$ | $0.1532$
| AXP,AMGN,AAPL,CAT, | AXP,CSCO,KO,DOW | BA,CVX, |
| DIS,GS,HD,HON,INTC, | JPM,TRV | IBM,WBA |
| JNJ,MCD,MRK,MSFT, |  |  |
| NKE,PG,CRM,UNH,VZ, |  |  |
| V,WMT |  |  |
Final | $\mathcal{P}^{1}=0.1153$ | $\mathcal{P}^{2}=0.0209$ | $\mathcal{P}^{3}=0.000$ | $0.1361$
| AXP,AMGN,AAPL,CAT, | AXP,CSCO,KO,DOW | BA,CVX, |
| DIS,GS,HD,HON,INTC, | JPM,TRV,CRM | IBM,WBA |
| JNJ,MCD,MRK,MSFT,V |  |  |
| NKE,PG,UNH,VZ,WMT |  |  |
Table 1: Stock tiers through the classification process

The second example is a collection of 42 prostate cases that were previously
evaluated with DEA and uDEA, see [8, 21, 31]. These treatments were delivered
to patients in New Zealand and were approved for observational studies.
Treatment planning has an established history in operations research, and we
refer readers to [7, 9, 13, 27] as summary reviews. The overriding goal of
treatment planning is to design a treatment that delivers a uniform,
tumoricidal dose to the targeted region while sparing nearby organs from
harmful effects. The targeted region is the planning treatment volume (PTV),
which is a clinically delineated portion of the anatomy that encompasses both
cancerous tumors and their perceived microscopic extensions. The organs at
risk in a prostate case are generally the rectum, the bladder, and the femoral
heads, with the rectum and bladder being particularly concerning because they
abut the prostate.

Each treatment is patient specific, and although trained experts tailor
treatments with sophisticated optimization software to clinical standards,
treatment quality remains nebulous and varied for many reasons. There are
preference and software differences among clinics and clinicians, there are
mathematical and computational assumptions that only approximate what is
actually delivered, and there are uncertainties in treatment delivery. All 42
cases were deemed clinically acceptable, but that does not mean that they were
bereft of improvement. Indeed, one of the outcomes of [21] was that treatments
identified for possible improvement actually benefited from reconsideration.
So the practical importance of reviewing previously delivered treatments is to
learn from those that were outstanding so that clinical acceptability
improves.

The original work in [21] posited the use of DEA to analyze treatments, but
this effort assumed certain characteristic data. The subsequent efforts in [8]
and [31] recognized the uncertainty of the characteristics and provided
alternate assessments that benefited from this recognition. The computational
processes in [8, 31] evaluated individual treatments on the amount of
uncertainty required to be efficient within the entire collection of
treatments, and those that necessitated larger amounts of uncertainty were
recommended for review and possible improvement.

Our classification scheme advances the work in [8, 21, 31]. First, it
recognizes and models uncertainty like [8, 31], so it gains fidelity over [21]
with regard to the uncertain clinical situation. Second, the analysis methods
in [8, 31] are not directly classification processes, but rather, they ask
clinicians to discern which treatments might benefit from additional
consideration post calculation. For instance, the authors of [8] suggest
segmenting the cases with a threshold on the amount of uncertainty, but this
threshold can only be decided after the computational effort. Our
classification process instead identifies (near) optimal categories and
partitions the cases into a fixed number of categories without an after-the-
fact cutoff. We partition the 42 cases into three categories: those deemed to
be clinical exemplars, those deemed to be clinical standards, and those that
should be considered for additional improvement. Classifying into three
categories is clinically reasonable because it identifies clinical exemplars
that illustrate best practices, which is unlike the previous dichotomies that
primarily distinguish the treatments that should be reconsidered. Our
trichotomy does both, i.e. it identifies clinical exemplars and it
distinguishes those that should be reconsidered.

The input characteristic is the rectal generalized equivalent uniform dose
(gEUD), which measures the average homogeneous dose delivered to the rectum,
and the output characteristic is the dose received by 95% of the PTV
($D_{95}$). The unit of dose is a Gray (Gy). These are the same input and
output characteristics in [8, 21, 31], and all three of these articles review
additional clinical details. The categories throughout the classification
process are in Figures 6 and 6. The category of green squares contains
exemplar treatments, the category of blue circles contains clinical standards,
and the category of red diamonds contains treatments that should be
reconsidered. Note that the search following the initialization process only
identifies a single improvement, with one of the treatments moving into the
category of clinical standards from those that would have been recommended for
continued review.

Figure 5: Initial Classifications

Figure 6: First Improvement

The initial and improved proximity values are:

| $\mathcal{P}^{1}$ | $\mathcal{P}^{2}$ | $\mathcal{P}^{3}$ | $\mathcal{C}(\mathcal{P})$
---|---|---|---|---
Initial | $0.1851$ | $0.1693$ | $0.8049$ | $1.1593$
Final | $0.1851$ | $0.1693$ | $0.7997$ |  $1.1541$.

Our partitioning suggests 15 cases would have likely benefited from additional
planning, which is fewer than the 20 cases shown to exceed the proposed
threshold in [8]. Some of this decrease is due, at least in part, to the fact
that we partition into three categories instead of two. Three final
observations are worthwhile. First, the interplay between the second and third
categories suggests that it would be difficult to discern a clear separation
between these categories without a tool that optimizes the classification.
Second, just because a treatment is classified as warranting a review does not
immediately suggest that the treatment fell below clinical guidelines.
Remember that trained experts tailor each treatment to a patient’s specific
needs, and sometimes this imposes considerations other than standard
performance metrics. So being classified as warranting a review would simply
alert an expert to the fact that continued design might be worthwhile. Third,
the categories visually segment themselves more vertically than horizontally,
which suggests that the $D_{95}$ value is somewhat more important as a
classification parameter. This observation is less clear between the second
and third categories, but it is the type of visual acuity provided by the
classification.

##  6 Conclusion

Uncertain data envelopment analysis can be useful within a classification
process, and we have advanced the employ of the proximity to equitable
efficiency as a sound tool to classify in the presence of uncertain data. We
overcome two computational issues, those being the innate difficulty of
calculating our proximity value due to a loss of convexity and the
combinatorially fraught problem of searching over all possible partitions. The
downside to our classification process is that it necessitates a protracted
calculation in serial, a fact that we sidestep on our examples by
parallelizing our algorithm. Future work could seek to streamline the
computational effort to better address larger problems with more
characteristics. Applying the classification process to additional problems
should also be fruitful.

## Acknowledgements

The authors are grateful for thoughtful comments made by Matthias Ehrgott.

## References

  * [1] D. Baatar and M.M. Wiecek.  Advancing Equitability in Multiobjective Programming.  Computers & Mathematics with Applications, 52(1):225–234, 2006\.
  * [2] A. Ben-Tal and A. Nemirovski.  On Polyhedral Approximations of the Second-Order Cone.  Mathematics of Operations Research, 26(2):193–205, 2001.
  * [3] D. Bertsimas and R. Shioda.  Classification and Regression via Integer Optimization.  Operations Research, 55(2):252–271, 2007.
  * [4] S. Cinaroglu.  Integrated k-means clustering with data envelopment analysis of public hospital efficiency.  Health Care Management Science, 23:325–338, 2020.
  * [5] W. Cooper, L. Seiford, and K. Tone.  Data Envelopment Analysis: A Comprehensive Text with Models, Applications, References and DEA-solver Software.  Springer, New York, 2007.
  * [6] B. Duran and P. Odell.  Cluster Analysis: A Survey, volume 100.  Springer Science & Business Media, 2013.
  * [7] M. Ehrgott, Ç. Güler, H. W. Hamacher, and L. Shao.  Mathematical optimization in intensity modulated radiation therapy.  4OR, 6(3):199–262, 2008.
  * [8] M. Ehrgott, A. Holder, and O. Nohadani.  Uncertain Data Envelopment Analysis.  European Journal of Operational Research, 268:231–242, 2018.
  * [9] Matthias Ehrgott and Allen Holder.  Operations research methods for optimization in radiation oncology.  Journal of Radiation Oncology Informatics, 6(1):1–41, Oct. 2017\.
  * [10] A. Emrouznejad, B. Parker, and G. Tavares.  Evaluation of Research in Efficiency and Productivity: A Survey and Analysis of the First 30 Years of Scholarly Literature in DEA.  Socio-economic Planning Sciences, 42:151–157, 2008.
  * [11] L. García-Escudero, A. Gordaliza, C. Matrán, and A. Mayo-Iscar.  A Review of Robust Clustering Methods.  Advances in Data Analysis and Classification, 4(2-3):89–109, 2010\.
  * [12] W. Hart, C. Laird, J.-P. Watson, D. Woodruff, G. Hackebeil, B. Nicholson, and J. Siirola.  Pyomo - Optmization Modeling in Python.  Springer, 2017.
  * [13] A. Holder.  Radiotherapy treatment design and linear programming.  In M.L. Brandeau, F. Sainfort, and W.P. Pierskalla, editors, Operations Research and Health Care, pages 741–774. Kluwer Academic Publishers, Norwell MA, 2004.
  * [14] A. Holder and B. Lyu.  A Simplex Approach to Solving Robust Metabolic Models with Low-Dimensional Uncertainty.  In Harvey J. Greenberg: A Legacy Bridging Operations Research and Computing. Springer, 2020.
  * [15] C. Huberty and S. Olejnik.  Applied MANOVA and Discriminant Analysis, volume 297.  John Wiley & Sons, 2nd edition, 2006.
  * [16] S. Hwang, H. Lee, and J. Zhu, editors.  Handbook of Decision Making Using Data Envelopment Analysis.  Springer, New York, 2016.
  * [17] A. Jain, M. Murty, and P. Flynn.  Data Clustering: A Review.  ACM Comput. Surv., 31(3):264–323, 1999.
  * [18] M. Kostreva and W. Ogryczak.  Linear Optimization with Multiple Equitable Criteria.  RAIRO Operations Research, 33:275–297, 1999.
  * [19] S. Kotsiantis.  Supervised Machine Learning: A Review of Classification Techniques.  In Proceedings of the 2007 Conference on Emerging Artificial Intelligence Applications in Computer Engineering: Real Word AI Systems with Applications in EHealth, HCI, Information Retrieval and Pervasive Technologies, page 3–24. IOS Press, Neatherlands, 2007.
  * [20] J. Lee and S. Olafsson.  Data Clustering by Minimizing Disconnectivity.  Information Sciences, 181(4):732–746, 2011.
  * [21] Kuan-Min Lin, John Simpson, Giuseppe Sasso, Andrea Raith, and Matthias Ehrgott.  Quality assessment for VMAT prostate radiotherapy planning based on data envelopment analysis.  Physics in Medicine and Biology, 58(16):5753, 2013.
  * [22] J. Liu, L. Lu, W. Lu, and B. Lin.  A Survey of DEA Applications.  Omega, 41:893–902, 2013.
  * [23] S. Olafsson, X. Li, and S. Wu.  Operations Research and Data Mining.  European Journal of Operational Research, 187(3):1429–1448, 2008\.
  * [24] P. Peykani, E. Mohammadi, R. F. Saen, S. J. Sadjadi, and M. Rostamy-Malkhalifeh.  Data envelopment analysis and robust optimization: A review.  Expert Systems, 37(4):e12534, 2020.
  * [25] T. Phyu.  Survey of Classification Techniques in Data Mining.  In Proceedings of the International MultiConference of Engineers and Computer Scientists, volume 1, pages 18–20, 2009.
  * [26] Rung-Wei Po, Yuh-Yuan Guh, and Miin-Shen Yang.  A new clustering approach using data envelopment analysis.  European Journal of Operational Research, 199(1):276–284, 2009\.
  * [27] H.E. Romeijn and J.F. Dempsey.  Intensity modulated radiation therapy treatment plan optimization.  Top, 16:215–243, 2008.
  * [28] Maziar Salahi, Mehdi Toloo, and Narges Torabi.  A new robust optimization approach to common weights formulation in dea.  Journal of the Operational Research Society, 72(6):1390–1402, 2021\.
  * [29] A. Saxena, M. Prasad, A. Gupta, N. Bharill, O. Patel, A. Tiwari, M. Er, W. Ding, and C. Lin.  A Review of Clustering Techniques and Developments.  Neurocomputing, 267:664–681, 2017.
  * [30] S. Schaeffer.  Graph Clustering.  Computer Science Review, 1(1):27–64, 2007.
  * [31] E. Stubington, M. Ehrgott, and O. Nohadani.  Uncertain Data Envelopment Analysis: Box Uncertainty.  preprint, 2020.
  * [32] E. Thanassoulis.  A data envelopment analysis approach to clustering operating units for resource allocation purposes.  Omega, 24(4):463–476, 1996.
  * [33] Mehdi Toloo, Emmanuel Kwasi Mensah, and Maziar Salahi.  Robust optimization and its duality in data envelopment analysis.  Omega, 108:102583, 2022.
  * [34] C. Vens, J. Struyf, L. Schietgat, S. Džeroski, and H. Blockeel.  Decision Trees for Hierarchical Multi-Label Classification.  Machine Learning, 73, 2008.
  * [35] G. Zhang.  Neural Networks for Classification: A Survey.  IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 30(4):451–462, 2000.


# SemEval-2023 Task 4: Fine-tuning vs Prompting,
Can Language Models Understand Human Values?

Pingwei SUN
BDT program, HKUST
<EMAIL_ADDRESS>

###### Abstract

Accurately handling the underlying support values in sentences is crucial for
understanding the speaker’s tendencies, yet it poses a challenging task in
natural language understanding (NLU). In this article, we explore the
potential of fine-tuning and prompt tuning in this downstream task, using the
_Human Value Detection 2023_. Additionally, we attempt to validate whether
models can effectively solve the problem based on the knowledge acquired
during the pre-training stage. Simultaneously, our interest lies in the
capabilities of large language models (LLMs) aligned with RLHF in this task,
and some preliminary attempts are presented.

##  1 Introduction

The persuasiveness of arguments is heavily influenced by individuals’ values,
and variations in the priority assigned to these values can lead to disputes,
especially between different cultures. To address this, computational
linguistics leverages human values to categorize and evaluate arguments.

Schwartz’s value categorization(Schwartz, 1994) serves as a common framework.
However, existing datasets have limitations, such as small sizes and cultural
biases. To overcome these issues, the competition holder proposes an
extension, Touché23-ValueEval (Mirzakhmedova et al., 2023), containing 9324
diverse arguments from various sources and cultures. This dataset aims to
facilitate the development of Pre-trained Language Models (PLM) for the
automatic identification of human values in persuasive communication,
supporting a broad array of applications. The task attracted many researchers
to work on it and various methods were proposed to solve the problem.

However, from the leaderboard, this task still requires more in-depth
research, with the top performer only achieving an average F1 score of 0.56.
Most participating teams tried to solve it as a classification task and
employed techniques such as model ensembling and expanding the dataset to
improve scores. Taking into account computational resources and the rise of
LLMs, our project will focus on the following questions based on the dataset:

  * •

Q1: Does prompt-tuning work compared with fine-tuning on the complex
downstream task?

  * •

Q2: Can PLMs handle human values powered by knowledge from the pre-training
stage?

  * •

Q3: How do LLMs perform on the task after aligning with human preference?

##  2 Related Work

Feature | Value Type |  Example
---|---|---
Argument ID | Str |  ”A01002”
Conclusion | Str |  ”We should ban fast food”
Stance | Str |  [”supporting”, ”against”]
Premise | Str |  ”Fast food should be banned because it is really bad …”
Value Labels | Int |  [0, 1]
Value categories: ”Achievement”, ”Stimulation”, etc.
Value Description | Str |  ”Self-direction: thought. It is good to have own ideas and interests.
Contained values and associated arguments (examples): …”
Table 1: The dataset used in the experiment with the corresponding types and
examples. Stance is mapped to single words to simplify the prompting template.
Square brackets represent single selections from among. The Value Description
are defined in Schwartz, 1994.

Human Value Detection 2023. Among the submissions, most teams applied
transformers-based models as their backbone and treated it as a classification
task.

Team Adam Smith (Schroter et al., 2023) employs an ensemble strategy,
including DeBERTa and RoBERTa. They trained these models for loss minimization
or F1-score maximization on three folds each RoBERTa model was pretrained on
the IBM-ArgQ-Rank30KArgs dataset. Ensembling involved averaging predictions
with an optimized decision threshold. They experimented with a stacked meta-
classifier based on logistic regression.

Team John Arthur (Balikas, 2023) fine-tuned a DeBERTa model on the task’s
data, using a concatenated representation of stance, premise, and conclusion.
They found that separate token symbols for stance improved classification. The
model was trained to minimize binary cross-entropy loss, and the team observed
performance benefits with more training data.

Team PAI (Ma, 2023) combined models using various input datasets. They applied
weight voting based on F1 score for ensembling and explored different loss
functions, ultimately favoring a class-balanced loss. Classification
thresholds were tested, but no performance improvement was achieved.

Fine-tuning. Since the release of BERT (Devlin et al., 2019), the approach of
large-scale pre-training followed by fine-tuning on downstream tasks has been
widely explored and applied to various NLP subtasks.

Through the integration of a range of training techniques, this method has
achieved impressive results. The bi-encoder structure employed during pre-
training inherently endows it with the ability to effectively extract semantic
information from sequences. However, it performs poorly when facing few-shot
and zero-shot scenarios.

Prompting. Recently, researchers have been attempting to transform NLP tasks
into a seq-to-seq format using prompts. T5 (Raffel et al., 2020) marked the
first successful endeavor in this direction. Such an approach leverages the
knowledge acquired by language models during the pre-training phase rather
than treating them as feature extractors. Consequently, it exhibits excellent
performance on few-shot and zero-shot tasks, with the added benefit of reduced
fine-tuning costs.

GPT, with its decoder structure, demonstrates enhanced capabilities in
language modeling. The team Hitachi Tsunokake et al. (2023) has used BART, T5,
and GPT3, feeding the data to them in question-answering format.

##  3 Methods

To answer the questions proposed in § 1, we propose the following techniques,
to our best knowledge, to measure the potential of models on the complex task
of detecting human values. Figure 1 illustrates our workflow in the project.

###  3.1 Data Utilization

The data file contains various annotations and supplementary datasets from
platforms like Zhihu and The New York Times. Experiments are conducted on the
main dataset, and due to the unavailability of test labels, all results in
this paper reflect the model’s performance on the validation set.

Before commencing the experiments, the data files are reorganized, and certain
features are preprocessed, as shown in Table 1.

###  3.2 Fine-tuning as a Classification Task

Classifier. To solve the multi-label classification task, there are two
methods to choose from. On the one hand, it is sensible to use a single
classifier, apply the sigmoid function to each $x_{i}$ in the
$output=\left\\{x_{1},x_{2},...,x_{c}\right\\}$, and then calculate the Binary
Cross Entropy Loss as follows.

$\sum_{i=1}^{C}y_{i}\cdot\log\sigma(x_{i})+(1-y_{i})\cdot\log(1-\sigma(x_{i}))$
(1)

On the other hand, it also works by setting up the same number of classifiers
as the number of labels, each classifier to handle one category.

Hidden States. Serving as an encoding module, BERT can provide various levels
of features of the sequence. It is commonly agreed that the deeper layers
always output high-level semantic information (Sun et al., 2019) and the first
token [CLS] can be used for sequence classification.

Avoid Forgetting. Since the model has learned solid knowledge during pre-
training, we need to find an appropriate way to arrange the learning rate for
fine-tuning. The lower layers handle more general information so they should
be updated with relatively lower learning rates. We use the decay factor to
achieve layer-wise learning rates.

Figure 1: Illustration of the workflow of our experiments. Tracks marked by
different colors stand for combinations of models, tasks, and methods, details
of which are told in § 4. The dashed lines mean methods are theoretically
available but we do not consider them in the project because of poor
performance or being computationally demanding. The colorful dots are
experiment results and indicate the analysis for the questions proposed in §
1.

###  3.3 Contrastive Learning

This project is a complex Natural Language Understanding task, so obtaining a
good embedding representation of the sequence is crucial for the subsequent
training of the classifier.

Inspired by the SimCSE (Gao et al., 2021), Contrastive Learning (CL) loss is
applied to optimize the embedding states of sequences. Since the target is
multi-label classification, the positive and negative samples can not be
defined directly inside a mini-batch. Consequently, we compute the CL loss
according to the following formulas:

$\begin{split}w_{ij}=&\frac{y_{i}^{T}\cdot y_{j}}{\sum_{k=1}^{B}y_{i}^{T}\cdot
y_{k}+\varepsilon}\\\ {CL\ \ell}_{i}=-&\log\frac{\sum_{j=1}^{B}w_{ij}\cdot
e^{\frac{sim(x_{i},x_{j})}{\tau^{\prime}}}}{\sum_{j=1}^{B}e^{\frac{sim(x_{i},x_{j})}{\tau^{\prime}}}}\end{split}$
(2)

where $y$ is the label vector, $x$ is the embedding representation and $B$ is
the batch size. The $\tau^{\prime}$ stands for the temperature hyper-parameter
of CL, which is a scaling factor of similarity scores.

###  3.4 Prompt Tuning Techniques

When doing prompt tuning, the model should be transferred to other modes to
fit the template’s requirements, shown in Figure 2. The details of template
construction are introduced below.

Binary choice template. It is easy to come up with the idea to transfer the
multi-label classification task to several binary choice questions. It can be
solved either with a Masked Language Model(MLM) by filling the blank or a
Generative Language Model(GLM) by generation.

Open answering template with knowledgeable verbalizer. When our templates
become more complex and open, it often allows for better stimulation of
internal model knowledge. At this point, we need a verbalizer to map the
output results to labels, and the choice of verbalizer significantly impacts
the outcomes (Hu et al., 2022).

Notably, the dataset includes descriptions and examples of human values.
However, they were artificially defined by linguists two decades ago. To
enhance the dataset’s generalization, we introduce LLM to rewrite the
descriptions and provide synonyms, which will serve as a knowledgeable
verbalizer to map the output results to labels of human values.

Chain-of-Thought template. Language models, particularly LLMs, have
demonstrated remarkable reasoning capabilities, as evidenced by studies such
as (Kojima et al., 2022). Despite the challenge of directly comprehending
whether specific human values are implied in triples, models can acquire
relevant knowledge through a systematic prompting process. This step-by-step
approach allows LLMs to navigate and extract pertinent information, ultimately
enabling them to effectively address the intricacies of classification
problems.

In light of this, we have incorporated templates in the form of CoT. These
templates serve as structured prompts that guide the model in interpreting and
understanding the nuances of human values within extra knowledge.

Figure 2: Prompt templates for different task processing modes, including
classification(CLS), masked binary choice(MBC), binary choice answering(BCA),
open answering(OA), and Chain-of-Thought(CoT). The bolded content in brackets
represents the features in the dataset, shown in Table 1.

##  4 Experiments

The following experiments are conducted to answer questions mentioned in § 1.
Since we aim to explore fine-tuning methods and have a limited computational
budget, tricks such as model ensembling to improve scores are not applied.

###  4.1 Exp-I: Fine-tuning

Based on the previous team’s papers, we choose RoBERTa and DeBERTa followed by
a classifier for fine-tuning experiments. The Premise, Conclusion, and Stance
features are directly fed to the model. Settings of hyperparameters for
training are listed in Table 2.

The performance of different models and classifiers is presented in Table 3.
RoBERTa with multiple classifiers is selected after the preliminary fine-
tuning experiment.

Then Contrastive Learning is introduced for further improvement of the
performance. In this part, we treat it as either a pre-training task or an
extra loss item at the fine-tuning stage. The second strategy performs
slightly better, and both of them make progress on the macro F1 score.

Parameters | Value
---|---
_Trainer_
Batch size | 8
Epochs | 3.0
Lr scheduler | cosine
Warmup ratio | 0.1
Lr decay | 0.97
_Optimizer_
Optimzier | Adamw
Learning rate | 2e-5
Trainable param | last 8 layers + classifier(s)
Table 2: We try various combinations of the hyperparameters and compare validation scores after training. The above is an optimal choice among them. Model | Macro F1 score
---|---
$RoBERTa_{Large}$ |
w/ SH | .481
w/ MH | .507
$DeBERTa_{Large}$ |
w/ SH | .477
w/ MH | .493
$RoBERTa_{Large}$ w/ MH |
CL pre-train | .518
CL fine-tune | .522
Table 3: Performance of finetuned encoding models with classifiers on the
validation set. SH means single classification head, while MH means multiple
heads.

Method / F1 score | All |  Self-direction: thought |  Self-direction: action |  Stimulation |  Hedonism |  Achievement |  Power: dominance |  Power: resources |  Face |  Security: personal |  Security: societal |  Tradition |  Conformity: rules |  Conformity: interpersonal |  Humility |  Benevolence: caring |  Benevolence: dependability |  Universalism: concern |  Universalism: nature |  Universalism: tolerance |  Universalism: objectivity
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
_Classification_ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
RoBERTa w/ MH | .51 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | -
RoBERTa-CLS | .54 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | -
DeBERTa-CLS | .52 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | -
_MLM_ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
RoBERTa-MBC | .47 | .52 | .63 | .22 | .31 | .58 | .33 | .56 | .30 | .69 | .62 | .58 | .55 | .27 | .16 | .50 | .32 | .66 | .75 | .39 | .43
DeBERTa-MBC | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | -
_GLM_ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
T5†-BCA | .45 | .49 | .59 | .23 | .30 | .58 | .37 | .50 | .25 | .70 | .61 | .44 | .46 | .25 | .21 | .48 | .28 | .68 | .73 | .33 | .50
T5†-OA | .45 | .49 | .58 | .25 | .31 | .58 | .32 | .49 | .27 | .73 | .60 | .49 | .45 | .25 | .19 | .47 | .28 | .66 | .74 | .35 | .52
T5-BCA | .52 | .57 | .70 | .18 | .44 | .65 | .41 | .54 | .33 | .78 | .68 | .67 | .59 | .30 | .13 | .50 | .35 | .76 | .85 | .49 | .56
T5-OA | .50 | .51 | .69 | .13 | .27 | .61 | .44 | .49 | .30 | .74 | .62 | .58 | .55 | .36 | .17 | .52 | .41 | .73 | .80 | .45 | .55
GPT2†-BCA | .42 | .41 | .57 | .15 | .21 | .55 | .26 | .43 | .23 | .66 | .53 | .47 | .49 | .31 | .20 | .42 | .28 | .64 | .72 | .36 | .53
GPT2†-OA | .44 | .45 | .62 | .11 | .42 | .47 | .31 | .41 | .23 | .71 | .56 | .44 | .51 | .33 | .20 | .45 | .30 | .67 | .77 | .39 | .52
GPT2-BCA | .46 | .44 | .63 | .19 | .23 | .58 | .38 | .47 | .25 | .69 | .56 | .52 | .54 | .34 | .23 | .43 | .28 | .68 | .79 | .32 | .56
GPT2-OA | .48 | .47 | .65 | .25 | .29 | .56 | .37 | .51 | .31 | .72 | .60 | .51 | .55 | .27 | .19 | .50 | .33 | .67 | .81 | .52 | .54
_LLM-CoT_ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Llama-7B | .49 | .55 | .66 | .20 | .39 | .64 | .35 | .48 | .26 | .77 | .63 | .54 | .53 | .35 | .20 | .53 | .38 | .71 | .80 | .34 | .42
ChatGPT | .53 | .52 | .71 | .26 | .33 | .61 | .48 | .52 | .38 | .75 | .65 | .60 | .56 | .47 | .16 | .55 | .42 | .72 | .83 | .42 | .57

Table 4: F1 score of various prompt tuning methods. T5 and GPT2 with † stand
for the base and medium versions respectively and the others are of their
large versions except for LLMs. There is something wrong with
DeBERTaForMaskedLM in huggingface, so DeBERTa-MBC is of no reference value.

###  4.2 Exp-II: Prompt Tuning

The previously mentioned prompt templates are sequentially tested in this
section in conjunction with models of different parameter sizes and
structures. The training strategies are inspired by Liu et al., 2021 and
implementations are based on OpenPrompt (Ding et al., 2022).

To be specific, the CLS template is treated as a hard prompt of which
parameters are frozen and fed to encoding models with trainable multiple
classifiers. Its trainable parameters are consistent with the previous fine-
tuning settings.

Templates in the forms of mask filling and question answering are also
proposed. At this time, we set PLMs fixed and allow prompts’ parameters to be
updated. Extra knowledge in the OA template is processed in advance, which is
manually selected from feedback from ChatGPT.

###  4.3 Exp-III: Works on LLMs

The capabilities of the LLMs on this complex NLU task are also what we plan to
explore. Experiments are conducted with a CoT template which is designed to
stimulate the logical inference ability and knowledge inside LLMs.

Considering the computational budget, no gradient updating process is included
in this template. Instead, the scores are obtained by taking 5% of the
validation dataset for local inference (Llama7B) or API calls (GPT series) and
computing F1 scores on predicted results, which is shown in Table 4.

##  5 Analysis

###  5.1 Effectiveness of Fine-tuning and Input Description

We achieved a relatively competitive result compared with last year’s
leaderboard. At the same time, we also validated the contribution of
contrastive learning to obtaining more discriminative embedding
representations.

Furthermore, we observed that, in handling NLU tasks with complex inputs,
providing reasonable descriptions for complex input examples enhances model
performance compared to directly concatenating and inputting individual
components.

###  5.2 Performance of Prompt Tuning

Finding versions of different models with the same parameter size is a
challenge, to ensure the validity of the results, we attempted to compensate
by the trainable parameters during training.

From the table, it is evident that on models with a size less than 500M, fine-
tuning outperforms prompt tuning, which is reasonable being given more
trainable parameters. However, when the model size approaches 1B (two to three
times that of the formers), prompt tuning shows comparable performance to
fine-tuning. Yet, during training, we observed a larger variance in the
performance of prompt tuning with changes in the initialization methods of
templates.

Does it mean fine-tuning is always a better choice in this range of parameter
size (<1B)? Our two additional experiments explain this in more detail. The
results of NLI and few-shot are listed in Table 5.

We built a simple NLI task using the Premise Conclusion and Stance features in
the dataset and tuned some models using the same method as before. As can be
seen, there is no significant gap between fine-tuning and prompt tuning in
this simpler task, even with fewer trainable parameters, indicating that with
the increase in task complexity, prompt tuning requires a larger base model,
meaning better language modeling abilities and more knowledge to achieve
performance comparable to the encoder + classifier paradigm.

When faced with few-shot datasets, prompt tuning shows obvious advantages. In
contrast, fine-tuning seems failed to solve the task.

###  5.3 Prompting LLMs to Detect Human Values

In the aspect of LLMs, even without any fine-tuning, a well-designed
questioning style (prompts) can enable them to perform well on the task.

However, this improvement is more uncertain than the previously mentioned
methods (as can be seen from the variation in scores across categories) and
relies on an experienced questioner. Failures in a few categories may be
attributed to inconsistencies between external knowledge from ChatGPT and task
definitions.

Models / Task | NLI | 5-shot HVD
---|---|---
RoBERTa | .872 | -
T5 | .866 | .413
GPT2 | .849 | .408
Table 5: Results of NLI and few-shot Human Value Detection. The model sizes
are close and all below 500M. NLI is evaluated by accuracy while HVD still
uses the F1 score.

##  6 Conclusion

###  6.1 Fine-tuning vs Prompt Tuning

This is a problem that involves multiple variables as we mentioned in the
analysis section. Each approach has its own strengths and weaknesses.

Briefly, prompt tuning can achieve and sometimes surpass the performance of
direct fine-tuning when the model size is large enough. It exhibits better
generalization and enhanced transferability. However, direct fine-tuning, as a
more straightforward approach, is worth considering when training samples are
abundant, as it allows for stable performance leveraging a smaller model,
which is particularly crucial in industrial applications.

###  6.2 Human values detection

PLMs of medium size: From the F1 scores, it is evident that the model requires
further improvement. However, the accuracy metric in the experiments reflects
the model’s detection capability is viable. The main direction for improvement
lies in reducing false positives.
Chat-LLMs: Despite evaluating only a small subset of data, LLMs have
demonstrated commendable performance in understanding human values.

###  6.3 Limitations

When comparing the performance of fine-tuning and prompt tuning, the inability
to control model parameter sizes and trainable parameters leads to a decrease
in the persuasiveness of the results.

However, such conclusions remain meaningful for practical applications
because, in the face of various trade-off conditions, considerations across
all aspects are often needed rather than an itemized comparison of pros and
cons.

## References

  * Balikas (2023) Georgios Balikas. 2023.  John-Arthur at SemEval-2023 Task 4: Fine-Tuning Large Language Models for Arguments Classification.  In _Proceedings of the 17th International Workshop on Semantic Evaluation (SemEval’23)_ , pages 1428–1432, Toronto, Canada. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Ding et al. (2022) Ning Ding, Shengding Hu, Weilin Zhao, Yulin Chen, Zhiyuan Liu, Haitao Zheng, and Maosong Sun. 2022.  OpenPrompt: An open-source framework for prompt-learning.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 105–113, Dublin, Ireland. Association for Computational Linguistics.
  * Gao et al. (2021) Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021.  SimCSE: Simple contrastive learning of sentence embeddings.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 6894–6910, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Hu et al. (2022) Shengding Hu, Ning Ding, Huadong Wang, Zhiyuan Liu, Jingang Wang, Juanzi Li, Wei Wu, and Maosong Sun. 2022.  Knowledgeable prompt-tuning: Incorporating knowledge into prompt verbalizer for text classification.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2225–2240, Dublin, Ireland. Association for Computational Linguistics.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022.  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ , 35:22199–22213.
  * Liu et al. (2021) Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. 2021.  Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing.
  * Ma (2023) Long Ma. 2023.  PAI at SemEval-2023 Task 4: A General Multi-label Classification System with Class-balanced Loss Function and Ensemble Module.  In _Proceedings of the 17th International Workshop on Semantic Evaluation (SemEval’23)_ , pages 256–261, Toronto, Canada. Association for Computational Linguistics.
  * Mirzakhmedova et al. (2023) Nailia Mirzakhmedova, Johannes Kiesel, Milad Alshomary, Maximilian Heinrich, Nicolas Handke, Xiaoni Cai, Barriere Valentin, Doratossadat Dastgheib, Omid Ghahroodi, Mohammad Ali Sadraei, Ehsaneddin Asgari, Lea Kawaletz, Henning Wachsmuth, and Benno Stein. 2023.  The touché23-valueeval dataset for identifying human values behind arguments.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21:140:1–140:67.
  * Schroter et al. (2023) Daniel Schroter, Daryna Dementieva, and Georg Groh. 2023.  Adam-Smith at SemEval-2023 Task 4: Discovering Human Values in Arguments with Ensembles of Transformer-based Models.  In _Proceedings of the 17th International Workshop on Semantic Evaluation (SemEval’23)_ , pages 532–541, Toronto, Canada. Association for Computational Linguistics.
  * Schwartz (1994) Shalom H Schwartz. 1994.  Are there universal aspects in the structure and contents of human values?  _Journal of social issues_ , 50(4):19–45.
  * Sun et al. (2019) Chi Sun, Xipeng Qiu, Yige Xu, and Xuanjing Huang. 2019.  How to fine-tune bert for text classification?  In _Chinese Computational Linguistics: 18th China National Conference, CCL 2019, Kunming, China, October 18–20, 2019, Proceedings 18_. Springer.
  * Tsunokake et al. (2023) Masaya Tsunokake, Atsuki Yamaguchi, Yuta Koreeda, Hiroaki Ozaki, and Yasuhiro Sogawa. 2023.  Hitachi at SemEval-2023 Task 4: Exploring Various Task Formulations Reveals the Importance of Description Texts on Human Values.  In _Proceedings of the 17th International Workshop on Semantic Evaluation (SemEval’23)_ , pages 1723–1735, Toronto, Canada. Association for Computational Linguistics.