# Remarks on Loss Function of Threshold Method for Ordinal Regression Problem

Ryoya Yamasaki&Toshiyuki Tanaka

###### Abstract

Threshold methods are popular for ordinal regression problems, which are
classification problems for data with a natural ordinal relation. They learn a
one-dimensional transformation (1DT) of observations of the explanatory
variable, and then assign label predictions to the observations by
thresholding their 1DT values. In this paper, we study the influence of the
underlying data distribution and of the learning procedure of the 1DT on the
classification performance of the threshold method via theoretical
considerations and numerical experiments. Consequently, for example, we found
that threshold methods based on typical learning procedures may perform poorly
when the probability distribution of the target variable conditioned on an
observation of the explanatory variable tends to be non-unimodal. Another
instance of our findings is that learned 1DT values are concentrated at a few
points under the learning procedure based on a piecewise-linear loss function,
which can make difficult to classify data well.

##  1 Introduction

_Ordinal regression_ (_OR_ , or called ordinal classification) is the
classification of _ordinal data_ in which the underlying target variable is
labeled from a categorical _ordinal scale_ that is considered to be equipped
with a _natural ordinal relation_ for the underlying explanatory variable, as
formalized in Section 2.1. The ordinal scale is typically formed as a graded
summary of objective indicators like age groups {‘0–9’, ‘10–19’, …, ‘90–99’,
‘100–’} or graded evaluation of subjectivity like human rating {‘excellent’,
‘good’, ‘average’, ‘bad’, ‘terrible’}. OR techniques are employed in a variety
of practical applications, for example, age estimation (Niu et al., 2016; Cao
et al., 2020), information retrieval (Liu, 2011), movie rating (Yu et al.,
2006), and questionnaire survey (Bürkner and Vuorre, 2019).

_Threshold methods_ are popular for OR problems as a simple way to capture the
ordinal relation of ordinal data, and have been studied vigorously in machine
learning research (Shashua and Levin, 2003; Lin and Li, 2006; Chu and Keerthi,
2007; Lin and Li, 2012; Li and Lin, 2007; Pedregosa et al., 2017; Yamasaki,
2023). Those methods learn a _one-dimensional transformation (1DT)_ of the
observation of the explanatory variable so that an observation with a larger
class label tends to have a larger 1DT value; they then assign a label
prediction to the learned 1DT according to the rank of an interval to which
the 1DT belongs among intervals on the real line separated by _threshold
parameters_. See also Section 2.2 for their formulation.

Despite its popularity, the question of what data distribution threshold
methods will work well or poorly for is not sufficiently elucidated. For
example, Rennie and Srebro (2005); Gutierrez et al. (2015) performed numerical
experiments to compare the classification performance of OR methods including
threshold methods, but did not attempt to elucidate factors behind the
difference in those performances. Therefore, with the aim of providing an
answer to this question, we study the influence of the underlying data
distribution and of the learning procedure of the 1DT on the classification
performance of the threshold method (see Section 2.3 for a mathematical
formulation of the research objectives of this work). We present theoretical
analysis and conjectures in Section 3, and verify these results via numerical
experiments as described in Sections 4 and Appendix A.111See
https://github.com/yamasakiryoya/RLTM for program codes for all the
experiments in this work. These construct qualitative understanding of what
properties of the ordinal data or of the learning procedure contribute to the
success or failure of a threshold method. Refer to Section 5 for summary of
results obtained by this work and for future works, and Appendix B for proofs
of theoretical results.

##  2 Preparation

###  2.1 Formulation of Ordinal Regression Tasks and Ordinal Data

####  2.1.1 Ordinal Regression Tasks

Suppose that we are interested in behaviors of the categorical target variable
$Y\in[K]:=\\{1,\ldots,K\\}$ given a value of the explanatory variable
${\bm{X}}\in{\mathbb{R}}^{d}$, and that we can access data
$({\bm{x}}_{1},y_{1}),\ldots,({\bm{x}}_{n},y_{n})\in{\mathbb{R}}^{d}\times[K]$
that are considered to be independent and identically distributed observations
of the pair $({\bm{X}},Y)$ and have a natural ordinal relation like examples
described in Section 1, where $K,d,n\in{\mathbb{N}}$ such that $K\geq 3$; we
call such data ordinal data. An OR task is a classification task for ordinal
data and often formulated as searching for a classifier
$f:{\mathbb{R}}^{d}\to[K]$ that is good in minimization of the _task risk_
$\operatorname{{\mathbb{E}}}[\ell(f({\bm{X}}),Y)]$ for a user-specified _task
loss function_ $\ell:[K]^{2}\to[0,+\infty)$, where the expectation
$\operatorname{{\mathbb{E}}}[\cdot]$ is taken for all included random
variables (here ${\bm{X}}$ and $Y$).222For evaluation in OR tasks, one may use
criteria that cannot be decomposed into a sum of losses for each sample point
such as quadratic weighted kappa (Cohen, 1960, 1968). One of the main topics
in this paper concerns troubles caused in relation to the learning procedure
(defined later in Section 2.2.2), and those troubles are there similarly even
for such other criteria. Our formulation is not comprehensive for the OR task,
but restricting the formulation does not seriously affect our discussion.
Popular task loss functions for OR tasks include not only the zero-one task
loss $\ell_{\rm zo}(k,l):=\operatorname{{\mathbbm{1}}}(k\neq l)$ for
minimization of misclassification rate, but also V-shaped losses for cost-
sensitive classification tasks that reflect user’s preference of smaller
prediction errors over larger ones such as the absolute task loss $\ell_{\rm
ab}(k,l):=|k-l|$, squared task loss $\ell_{\rm sq}(k,l):=(k-l)^{2}$, and
$\ell_{{\rm zo},\epsilon}(k,l):=\operatorname{{\mathbbm{1}}}(|k-l|>\epsilon)$
with $\epsilon>0$, where $\operatorname{{\mathbbm{1}}}(c)$ is 1 if the
condition $c$ is true and 0 otherwise.

####  2.1.2 Ordinal Data

OR tasks assume that ordinal data have a natural ordinal relation. As the
natural ordinal relation, in this work, we basically suppose the _unimodality
hypothesis_ adopted in da Costa et al. (2008); Beckham and Pal (2017);
Yamasaki (2022). Namely, we assume that many ordinal data are almost unimodal,
on the basis of the following terminologies: For a _probability mass function_
(_PMF_)
${\bm{p}}=(p_{k})_{k\in[K]}\in\Delta_{K-1}:=\\{(q_{k})_{k\in[K]}\mid\sum_{k=1}^{K}q_{k}=1;q_{k}\in[0,1],\forall
k=[K]\\}$, we call
$M({\bm{p}})\in\operatorname{{arg\,max}}_{k}(p_{k})_{k\in[K]}$ a _mode_ of
${\bm{p}}$, and say that ${\bm{p}}$ is _unimodal_ if it satisfies
$p_{1}\leq\cdots\leq p_{M({\bm{p}})}$ and $p_{M({\bm{p}})}\geq\cdots\geq
p_{K}$ for every mode $M({\bm{p}})$. Moreover, if the _conditional probability
distribution_ (_CPD_) $(\Pr(Y=y|{\bm{X}}={\bm{x}}))_{y\in[K]}$ of the target
variable $Y$ conditioned on an observation ${\bm{x}}$ of the explanatory
variable ${\bm{X}}$ is unimodal for any ${\bm{x}}$ in the support
${\mathcal{X}}$ of the probability distribution of ${\bm{X}}$, we say that the
data is _unimodal_ ; if the CPD $(\Pr(Y=y|{\bm{X}}={\bm{x}}))_{y\in[K]}$ is
unimodal at any ${\bm{x}}$ in a sub-domain
${\mathcal{X}}_{0}\subseteq{\mathcal{X}}$ with a large or small probability
$\Pr({\bm{X}}\in{\mathcal{X}}_{0})$, we say that the data is _almost unimodal_
or _almost non-unimodal_. Yamasaki (2022) verified that many data, which have
been treated as ordinal data by other previous OR studies (Chu and Ghahramani,
2005; Gutierrez et al., 2015), tend almost unimodal.

As further preparation, we introduce qualitative notions regarding scale of
the data as well: For a PMF ${\bm{p}}=(p_{k})_{k\in[K]}\in\Delta_{K-1}$ having
a mode $m\in[K]$, we call the degree of spread of ${\bm{p}}$ around $m$ the
_scale_ of ${\bm{p}}$. Refer to Figure 1; we say that a more right PMF in
Figure 1 has a larger scale than a more left one. If the scale of the CPD
${\bm{p}}({\bm{x}})=(\Pr(Y=y|{\bm{X}}={\bm{x}}))_{y\in[K]}$ tends to be large
or small over whole the support of the probability distribution of the
explanatory variable ${\bm{X}}$, we say that the data has large scale or small
scale. Also, if the scale of the CPD ${\bm{p}}({\bm{x}})$ is similar or
dissimilar over whole the support, we say that the data is _homoscedastic_ or
_heteroscedastic_. In particular, we refer to heteroscedastic data as _mode-
wise heteroscedastic_ or _overall heteroscedastic_ data, if the scale of their
CPD ${\bm{p}}({\bm{x}})$ is similar or can be dissimilar in each domain where
the conditional mode $M({\bm{p}}({\bm{x}}))$ is the same.

|  |
---|---|---
Figure 1: Instances of the 10-dimensional unimodal PMF
${\bm{p}}=(p_{k})_{k\in[10]}$ with the mode 5.

###  2.2 Formulation of Threshold Methods

####  2.2.1 Overview

A _1DT-based method_ (Yamasaki, 2023) is formulated with two procedures,
_learning procedure_ and _labeling procedure_ of the 1DT. In the learning
procedure, 1DT-based methods learn a 1DT (a real-valued function defined on
${\mathbb{R}}^{d}$) of the explanatory variable ${\bm{X}}$ based on the data
$({\bm{x}}_{1},y_{1}),\ldots,({\bm{x}}_{n},y_{n})$. In the labeling procedure,
1DT-based methods construct a classifier $f$ as $f=h\circ\hat{a}$ with a
learned 1DT $\hat{a}$ and a _labeling function_ $h:{\mathbb{R}}\to[K]$. Many
of those methods predict a label for ${\bm{X}}={\bm{x}}$ as
$f({\bm{x}})=h_{\rm thr}(\hat{a}({\bm{x}});{\bm{t}})$ using a _threshold
labeling function_ ,

$\displaystyle h_{\rm
thr}(u;{\bm{t}}):=1+\sum_{k=1}^{K-1}\operatorname{{\mathbbm{1}}}(u\geq t_{k})$
(1)

with a _threshold parameter vector_
${\bm{t}}=(t_{k})_{k\in[K-1]}\in{\mathbb{R}}^{K-1}$. In particular, such 1DT-
based methods that employ a threshold labeling function are called threshold
methods or threshold models, and have been studied actively in machine
learning research (Shashua and Levin, 2002; Chu and Keerthi, 2005; Rennie and
Srebro, 2005; Lin and Li, 2006, 2012; Pedregosa et al., 2017; Cao et al.,
2020; Yamasaki, 2023). The succeeding two sections detail the learning and
labeling procedures further.

####  2.2.2 Learning Procedure

The learning procedure of many existing threshold methods is designed
according to the idea of the _surrogate risk minimization_ (Pedregosa et al.,
2017) that allows for easier continuous optimization instead of directly
minimizing the task risk. In this work, we study threshold methods that can be
seen to learn a 1DT $a:{\mathbb{R}}^{d}\to{\mathbb{R}}$ from a function class
${\mathcal{A}}$ and a _bias parameter vector_ ${\bm{b}}=(b_{k})_{k\in[K-1]}$
from a class ${\mathcal{B}}$ by minimizing the _empirical surrogate risk_ for
a specified _surrogate loss function_ $\phi$,

$\displaystyle\min_{a\in{\mathcal{A}},{\bm{b}}\in{\mathcal{B}}}\frac{1}{n}\sum_{i=1}^{n}\phi(a({\bm{x}}_{i}),{\bm{b}},y_{i})$
(2)

(we denote the minimizer $(\hat{a},\hat{{\bm{b}}})$ with
$\hat{{\bm{b}}}:=(\hat{b}_{k})_{k\in[K-1]}$) or its regularized version.
Discussion in the main part of this paper focuses on the non-regularized
(empirical) surrogate risk minimization; see Appendix B for supplemental
discussion on the regularized version.

In this work, we consider popular surrogate loss functions in the class of
_all-threshold (AT) losses_ or _immediate-threshold (IT) losses_ (Pedregosa et
al., 2017). An AT loss is representable as

$\displaystyle\phi(a({\bm{x}}),{\bm{b}},y)=\begin{cases}\sum_{k=1}^{K-1}\varphi(b_{k}-a({\bm{x}}))&\text{if~{}}y=1,\\\
\sum_{k=1}^{K-1}\varphi(a({\bm{x}})-b_{k})&\text{if~{}}y=K,\\\
\sum_{k=1}^{y-1}\varphi(a({\bm{x}})-b_{k})+\sum_{k=y}^{K-1}\varphi(b_{k}-a({\bm{x}}))&\text{otherwise},\end{cases}$
(3)

and an IT loss is representable as

$\displaystyle\phi(a({\bm{x}}),{\bm{b}},y)=\begin{cases}\varphi(b_{1}-a({\bm{x}}))&\text{if~{}}y=1,\\\
\varphi(a({\bm{x}})-b_{K-1})&\text{if~{}}y=K,\\\
\varphi(a({\bm{x}})-b_{y-1})+\varphi(b_{y}-a({\bm{x}}))&\text{otherwise},\end{cases}$
(4)

with a certain function $\varphi:{\mathbb{R}}\to[0,\infty)$. As a function
$\varphi$, one often applies a convex loss function that is an upper bound of
the function $u\mapsto\operatorname{{\mathbbm{1}}}(u\leq 0)$ and commonly used
in binary classification. Table 1 summarizes instances of the function
$\varphi$ that we consider in this paper, corresponding AT and IT losses, and
reference papers for them. To represent these functions, we subscript their
abbreviation name in lowercase to $\varphi$ and $\phi$, like $\varphi_{\rm
logi}(u)=\log(1+e^{-u})$ and $\phi_{\rm logi\text{-}at}$ and $\phi_{\rm
logi\text{-}it}$ for the corresponding AT and IT losses.

Table 1: Name in this paper (its abbreviation) and functional form of
$\varphi$, and reference and name therein of the corresponding AT/IT loss
$\phi$.

Name of $\varphi$ in this paper (abbr.) | Functional form of $\varphi(u)$ | Reference and name therein of AT/IT loss $\phi$
---|---|---
Logistic (logi) | $\log(1+e^{-u})$ |  (Rennie and Srebro, 2005), CORAL (Cao et al., 2020)
Hinge (hing) | $(1-u)_{+}$ | SVOR-EXC/SVOR-IMC (Chu and Keerthi, 2005)
Ramp (ramp) |  $\min\\{(1-u)_{+},s\\}$ with $s>0$ | (Pfannschmidt et al., 2020)
Smoothed-Hinge (smhi) | $1-2u~{}(u\leq 0),\\{(1-u)_{+}\\}^{2}~{}(u>0)$ | (Rennie and Srebro, 2005)
Squared-Hinge (sqhi) | $\\{(1-u)_{+}\\}^{2}$ | AT/IT construction with modified least squares (Rennie and Srebro, 2005)
Exponential (expo) | $e^{-u}$ | ORBoost-LR/ORBoost-ALL (Lin and Li, 2006, 2012; Li and Lin, 2007)
Absolute (abso) | $|1-u|$ | –
Squared (squa) | $(1-u)^{2}$ | Squared AT (Pedregosa et al., 2017)

As a class of the 1DT ${\mathcal{A}}$, one applies, for example, a linear
model class
$\\{{\bm{x}}\mapsto{\bm{w}}^{\top}{\bm{x}}+w_{0}\mid{\bm{w}}\in{\mathbb{R}}^{d},w_{0}\in{\mathbb{R}}\\}$
and a neural network model with a fixed network architecture and learnable
bias and weight parameters. In this paper, we do not discuss the design of the
class of the 1DT, and simply assume
${\mathcal{A}}\subseteq\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}$ in the
following discussion.

The AT and IT surrogate losses $\phi(a({\bm{x}}),{\bm{b}},y)$ have the
translation invariance:
$\phi(a({\bm{x}}),{\bm{b}},y)=\phi(a({\bm{x}})+c,{\bm{b}}+c\bm{1}_{K-1},y)$
with all-1 vector $\bm{1}_{K-1}\in{\mathbb{R}}^{K-1}$ for any
$c\in{\mathbb{R}}$. Also, many methods incorporate the order constraint
$b_{1}\leq\cdots\leq b_{K-1}$ on the bias parameter vector ${\bm{b}}$. Thus,
we study the popular instances of the class ${\mathcal{B}}$,
${\mathcal{B}}_{0}:=\\{{\bm{b}}\in{\mathbb{R}}^{K-1}\mid b_{1}=0\\}$ (_non-
ordered class_) and ${\mathcal{B}}^{\rm
ord}_{0}:=\\{{\bm{b}}\in{\mathbb{R}}^{K-1}\mid b_{1}=0\leq b_{2}\leq\cdots\leq
b_{K-1}\\}$ (_ordered class_). The order constraint on the bias parameter
vector ${\bm{b}}$ can be implemented, for example, by
$b_{k+1}=b_{k}+c_{k}^{2}$ for $k\in[K-2]$ with other parameters
$c_{1},\ldots,c_{K-2}\in{\mathbb{R}}$ (Franses and Paap, 2001).

####  2.2.3 Labeling Procedure

The threshold labeling $h_{\rm thr}(u;{\bm{t}})$ is non-decreasing in
$u\in{\mathbb{R}}$ and the simplest labeling function in the sense that the
resulting 1DT-based classifier has only $(K-1)$ decision boundaries for the
learned 1DT at most (Yamasaki, 2023). Partly because of this simplicity, the
threshold labeling is preferred for many 1DT-based methods. Pedregosa et al.
(2017); Cao et al. (2020) adopt the learned bias parameter vector
$\hat{{\bm{b}}}$ to the threshold parameter vector ${\bm{t}}$, and Shashua and
Levin (2003); Chu and Keerthi (2007) use the labeling function
$h(u)=\min(\\{k\in[K-1]\mid u<\hat{b}_{k}\\}\cup\\{K\\})$. The latter labeling
function is also a certain threshold labeling, which is same as (resp.
different from) the former $h_{\rm thr}(\cdot;\hat{{\bm{b}}})$ when
$\hat{{\bm{b}}}$ are ordered (resp. non-ordered) (Yamasaki, 2023, Proposition
2). Yamasaki (2023) proposed to use the _empirical optimal threshold parameter
vector_ that minimizes the empirical task risk,
$\hat{{\bm{t}}}\in\operatorname{{arg\,min}}_{{\bm{t}}\in{\mathbb{R}}^{K-1}}\frac{1}{n}\sum_{i=1}^{n}\ell(h_{\rm
thr}(\hat{a}({\bm{x}}_{i});{\bm{t}}),y_{i})$ for the learned 1DT $\hat{a}$ and
specified task loss $\ell$. This minimization problem can be solved by a
dynamic-programming-based algorithm (Lin and Li, 2006) or computationally
efficient parallel algorithm (Yamasaki and Tanaka, 2024) for tasks with a task
loss function that is convex with respect to the first argument. Also,
Yamasaki (2023) experimentally confirmed that this labeling function can lead
to better classification performance than other labeling functions including
the above-mentioned two previous ones. Therefore, we suppose to employ the
empirical optimal threshold parameter vector $\hat{{\bm{t}}}$ in this work.

###  2.3 Research Objectives of This Work and Related Works

We are ultimately interested in the _generalization error_ (or _prediction
error_) $\operatorname{{\mathbb{E}}}[\ell(f({\bm{X}}),Y)]$ for the classifier
$f(\cdot)=\hat{f}(\cdot):=h_{\rm thr}(\hat{a}(\cdot);\hat{{\bm{t}}})$ of the
threshold method, where the learned 1DT $\hat{a}$ and learned threshold
parameter vector $\hat{{\bm{t}}}$ are obtained by the two-step optimization

$\displaystyle(\hat{a},\hat{{\bm{b}}})\in\underset{a\in{\mathcal{A}},{\bm{b}}\in{\mathcal{B}}}{\operatorname{{arg\,min}}}\,\frac{1}{n}\sum_{i=1}^{n}\phi(a({\bm{x}}_{i}),{\bm{b}},y_{i}),\quad\hat{{\bm{t}}}\in\underset{{\bm{t}}\in{\mathbb{R}}^{K-1}}{\operatorname{{arg\,min}}}\,\frac{1}{n}\sum_{i=1}^{n}\ell(h_{\rm
thr}(\hat{a}({\bm{x}}_{i});{\bm{t}}),y_{i}).$ (5)

The generalization error
$\operatorname{{\mathbb{E}}}[\ell(\hat{f}({\bm{X}}),Y)]$ is often understood
through the decomposition into the _approximation error_ and _estimation
error_ ,

$\displaystyle\operatorname{{\mathbb{E}}}[\ell(\hat{f}({\bm{X}}),Y)]=\underbrace{\operatorname{{\mathbb{E}}}[\ell(\bar{f}({\bm{X}}),Y)]}_{\text{approximation
error}}+\underbrace{\operatorname{{\mathbb{E}}}[\ell(\hat{f}({\bm{X}}),Y)]-\operatorname{{\mathbb{E}}}[\ell(\bar{f}({\bm{X}}),Y)]}_{\text{estimation
error}},$ (6)

like Shalev-Shwartz and Ben-David (2014, Section 5.2), where the classifier
$\bar{f}(\cdot):=h_{\rm thr}(\bar{a}(\cdot);\bar{{\bm{t}}})$ is defined with
the surrogate risk minimizer $(\bar{a},\bar{{\bm{b}}})$ and the optimal
threshold parameter vector $\bar{{\bm{t}}}$:

$\displaystyle(\bar{a},\bar{{\bm{b}}})\in\underset{a\in{\mathcal{A}},{\bm{b}}\in{\mathcal{B}}}{\operatorname{{arg\,min}}}\,\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)],\quad\bar{{\bm{t}}}\in\underset{{\bm{t}}\in{\mathbb{R}}^{K-1}}{\operatorname{{arg\,min}}}\,\operatorname{{\mathbb{E}}}[\ell(h_{\rm
thr}(\bar{a}({\bm{X}});{\bm{t}}),Y)].$ (7)

Behaviors of the generalization error
$\operatorname{{\mathbb{E}}}[\ell(f({\bm{X}}),Y)]$ for a classifier of the
threshold method have not been sufficiently understood. One important
theoretical analysis of the threshold method is Lin and Li (2006, 2012); Li
and Lin (2007): they gave a sample-based probably-approximately-correct bound
of the generalization error $\operatorname{{\mathbb{E}}}[\ell(f({\bm{X}}),Y)]$
for a classifier $f(\cdot)=h_{\rm thr}(a(\cdot);{\bm{t}})$ with a boosting-
based 1DT $a$ and ordered threshold parameter vector ${\bm{t}}$. Their bound
has a term of the order ${\mathcal{O}}(\log(n)/\sqrt{n})$ regarding the sample
size $n$ and another sample-based constant-order term, which are interpretable
as corresponding to the estimation and approximation errors respectively.
However, the influence of the learning procedure of the threshold method on
that constant-order approximation error term has not been sufficiently
studied.

Therefore, in this work, we focus only on the approximation error as a first
step. In general, as the training sample size $n$ increases, the estimation
error is expected to approach zero, and in such cases the approximation error
becomes dominant in the generalization error. Thus, we expect that our
consideration will be suggestive for behaviors of the generalization error of
the threshold method with the sufficiently large sample size $n$.

Typical binary or multi-class classification methods such as logistic
regression have a guarantee that their surrogate risk minimization with the
most representable model class possible (counterpart of
$({\mathcal{A}},{\mathcal{B}})$) yields a _Bayes optimal classifier_ (i.e.,
approximation error becomes the so-called _Bayes error_
$\min_{f:{\mathbb{R}}^{d}\to[K]}\operatorname{{\mathbb{E}}}[\ell(f({\bm{X}}),Y)]$)
for any probability distribution of $({\bm{X}},Y)$; such a guarantee is known
as _Fisher consistency_ or classification calibration (Bartlett et al., 2006;
Tewari and Bartlett, 2007; Liu, 2007; Pires et al., 2013). In contrast, most
threshold methods do not, as described in Pedregosa et al. (2017, Section 4),
namely, $\operatorname{{\mathbb{E}}}[\ell(\bar{f}({\bm{X}}),Y)]$ defined via
(7) is not necessarily equal to
$\min_{f:{\mathbb{R}}^{d}\to[K]}\operatorname{{\mathbb{E}}}[\ell(f({\bm{X}}),Y)]$
even if ${\mathcal{A}}=\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}$. In other
words, deviation of the approximation error of a threshold method from the
Bayes error generally varies depending on the underlying data distribution and
its learning procedure.

Therefore, we study the dependence of the underlying data distribution and of
the learning procedure of the 1DT on the approximation error of the threshold
method, in order to qualitatively understand what threshold methods work well
or poorly for what data. It aims to advance the previous theoretical result
(Pedregosa et al., 2017, Section 4) that just suggests that many threshold
methods do not have Fisher consistency, and refine the experimental comparison
of loss functions regarding the classification performance of the classifier
$h_{\rm thr}(\hat{a}(\cdot);\hat{{\bm{b}}})$ by Rennie and Srebro (2005);
Gutierrez et al. (2015) to a theoretical comparison regarding the
classification performance of the classifier $\hat{f}$. Also, this study is
the first attempt to discuss properties of threshold methods under a more in-
depth characterization of the natural ordinal relation (here, the unimodal
hypothesis) as far as we know.

##  3 Analyses and Conjectures

###  3.1 All-Threshold (AT) Loss

####  3.1.1 Order of Optimized Bias Parameters

In Section 3.1, we give analysis of the surrogate risk minimization of the
threshold method that uses an AT surrogate loss function, and conjecture about
what data distributions the resulting classifier will perform well or poorly
for.

We first discuss behaviors of the optimized bias parameter vector in Section
3.1.1. The following theorem states that, for many popular AT surrogate loss
functions, minimization of the (empirical) surrogate risk yields the bias
parameter vector that satisfies the order condition even without imposing the
order condition.

######  Theorem 1.

Let ${\mathcal{A}}\subseteq\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}$ and
${\mathcal{B}}_{0}^{\rm ord}\subseteq{\mathcal{B}}\subseteq{\mathcal{B}}_{0}$
and introduce the conditions

  * (a1)

$\varphi(u_{1})-\varphi(-u_{1})-\varphi(u_{2})+\varphi(-u_{2})\geq 0$ for any
$u_{1},u_{2}\in{\mathbb{R}}$ s.t. $u_{1}<u_{2}$;

  * (a2)

$\varphi(u)$ is non-increasing in $u\in{\mathbb{R}}$ (e.g.,
$\varphi=\varphi_{\rm ramp}$);

  * (a3)

$\varphi(u)-\varphi(-u)$ is non-increasing in $u\in{\mathbb{R}}$ (e.g.,
$\varphi=\varphi_{\rm abso}$);

  * (a4)

$\varphi(u_{1})-\varphi(-u_{1})-\varphi(u_{2})+\varphi(-u_{2})>0$ for any
$u_{1},u_{2}\in{\mathbb{R}}$ s.t. $u_{1}<u_{2}$;

  * (a5)

$\varphi(u)$ is decreasing in $u\in{\mathbb{R}}$ (e.g., $\varphi=\varphi_{\rm
logi},\varphi_{\rm expo}$);

  * (a6)

$\varphi(u)-\varphi(-u)$ is decreasing in $u\in{\mathbb{R}}$ (e.g.,
$\varphi=\varphi_{\rm hing},\varphi_{\rm smhi},\varphi_{\rm sqhi},\varphi_{\rm
squa}$);

  * (a7)

$\\{i\in[n]\mid y_{i}=y\\}\neq\emptyset$ for all $y\in[K]$;

  * (a8)

$\Pr(Y=y)>0$ for all $y\in[K]$.

Then, it holds that

  * (a9)

(a1) holds if (a2) or (a3) holds, and (a4) holds if (a5) or (a6) holds;

  * (a10)

when $\phi$ is an AT loss (3) with $\varphi$ satisfying (a1), there exists
$(\hat{a},\hat{{\bm{b}}})$ defined by (5) that satisfies
$\hat{b}_{1}\leq\cdots\leq\hat{b}_{K-1}$ if (a7) holds, and there exists
$(\bar{a},\bar{{\bm{b}}})$ defined by (7) that satisfies
$\bar{b}_{1}\leq\cdots\leq\bar{b}_{K-1}$ if (a8) holds;

  * (a11)

when $\phi$ is an AT loss (3) with $\varphi$ satisfying (a4), any
$(\hat{a},\hat{{\bm{b}}})$ defined by (5) satisfies
$\hat{b}_{1}\leq\cdots\leq\hat{b}_{K-1}$ if (a7) holds, and any
$(\bar{a},\bar{{\bm{b}}})$ defined by (7) satisfies
$\bar{b}_{1}\leq\cdots\leq\bar{b}_{K-1}$ if (a8) holds.

There are existing results similar to this theorem: Chu and Keerthi (2005)
showed (a10) for the Hinge-AT surrogate loss $\phi=\phi_{\rm hing\text{-}at}$
in their Theorem 1, and Li and Lin (2007) showed (a10) for $\varphi$
satisfying (a2) in their Theorem 2. We found more general conditions (a1) and
(a4) and other sufficient conditions (a3) and (a6) for the general ones.
Consequently, Theorem 1 newly covers the losses $\phi=\phi_{\rm
abso\text{-}at},\phi_{\rm squa\text{-}at}$.

This theoretical guarantee differs from Crammer and Singer (2002, Lemma 1) for
a perceptron-based algorithm as also pointed out by Chu and Keerthi (2005):
this lemma guarantees that a learned bias parameter vector always satisfies
the order condition on the basis of the nature of their optimization procedure
(initialization and update rule for perceptron), while Theorem 1 guarantees it
on the basis of the global optimality in the (empirical) surrogate risk
minimization. Thus, it should be noted that, for example, when the bias
parameter vector is learned by some iterative algorithm that adopts the
empirical surrogate risk as the objective function under the setting of
Theorem 1, it may be trapped by a local optimum and may not satisfy the order
condition in practice. So as to evade such an unexpected behavior, we
hereafter adopt the ordered class of the bias parameter vector
${\mathcal{B}}={\mathcal{B}}^{\rm ord}_{0}$ when we adopt an AT loss that
satisfies (a1) or (a4).

####  3.1.2 Analysis for Special Instances: Logistic- and Exponential-AT
Losses

We are interested in what data distributions a classifier obtained via the
surrogate risk minimization with an AT loss will perform well or poorly for.
As one answer to this question, in this section, we clarify special instances
of the data distributions for which classifiers of the threshold methods based
on the Logistic-AT or Exponential-AT loss perform well, and analyze those
special instances.

The following theorem shows that the threshold methods based on the Logistic-
AT or Exponential-AT loss perform well when the data follow a certain
likelihood model, which is well known as the (_proportional odds_) _cumulative
logit_ (_CL_) _model_ in the OR research (McCullagh, 1980; Agresti, 2010).

######  Theorem 2.

Assume that the random variable $({\bm{X}},Y)$ has the conditional probability
of $Y=y$ at ${\bm{X}}={\bm{x}}$,

$\displaystyle\Pr(Y=y|{\bm{X}}={\bm{x}})=P_{\rm
cl}(y;\tilde{a}({\bm{x}}),\tilde{{\bm{b}}}):=\begin{cases}\frac{1}{1+e^{-(\tilde{b}_{1}-\tilde{a}({\bm{x}}))}}&\text{if
}y=1,\\\ 1-\frac{1}{1+e^{-(\tilde{b}_{K-1}-\tilde{a}({\bm{x}}))}}&\text{if
}y=K,\\\
\frac{1}{1+e^{-(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}-\frac{1}{1+e^{-(\tilde{b}_{y-1}-\tilde{a}({\bm{x}}))}}&\text{otherwise},\end{cases}$
(8)

with $\tilde{a}:{\mathbb{R}}^{d}\to{\mathbb{R}}$ and
$\tilde{{\bm{b}}}\in{\mathcal{B}}_{0}^{\rm ord}$, for any ${\bm{x}}$ in the
support of the probability distribution of ${\bm{X}}$ and every $y\in[K]$. Let
$\phi$ be the Logistic-AT loss ($\phi=\phi_{\rm logi\text{-}at}$) or
Exponential-AT loss ($\phi=\phi_{\rm expo\text{-}at}$), and
${\mathcal{A}}\times{\mathcal{B}}\subseteq\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}\times{\mathcal{B}}_{0}^{\rm
ord}$ include $(\tilde{a},\tilde{{\bm{b}}})$ or
$(\tilde{a}(\cdot)/2,\tilde{{\bm{b}}}/2)$ respectively when $\phi=\phi_{\rm
logi\text{-}at}$ or $\phi=\phi_{\rm expo\text{-}at}$. Then, it holds that

  * (b1)

$(\bar{a},\bar{{\bm{b}}})$ defined by (7) satisfies
$(\bar{a}({\bm{X}}),\bar{{\bm{b}}})=(\tilde{a}({\bm{X}}),\tilde{{\bm{b}}})$ or
$(\bar{a}({\bm{X}}),\bar{{\bm{b}}})=(\tilde{a}({\bm{X}})/2,\tilde{{\bm{b}}}/2)$
almost surely respectively when $\phi=\phi_{\rm logi\text{-}at}$ or
$\phi=\phi_{\rm expo\text{-}at}$;

  * (b2)

$\bar{f}(\cdot)=h_{\rm thr}(\bar{a}(\cdot);\bar{{\bm{t}}})$ with $\bar{a}$ and
$\bar{{\bm{t}}}$ defined by (7) satisfies
$\operatorname{{\mathbb{E}}}[\ell(\bar{f}({\bm{X}}),Y)]=\min_{f:{\mathbb{R}}^{d}\to[K]}\operatorname{{\mathbb{E}}}[\ell(f({\bm{X}}),Y)]$,
if $\ell=\ell_{\rm zo},\ell_{{\rm zo},\epsilon}$ with $\epsilon\in[0,\lfloor
K/2\rfloor)$ or if $\ell$ satisfies (b3) (e.g., $\ell=\ell_{\rm ab},\ell_{\rm
sq}$) described below.

Here, $\lfloor u\rfloor$ for $u\in{\mathbb{R}}$ is the greatest integer less
than or equal to $u$, and the condition (b3) is as follows:

  * (b3)

$\ell(k,l)$ at each fixed $k\in[K]$ is non-increasing in $l$ for $l\leq k$ and
non-decreasing in $l$ for $l\geq k$, and
$\ell(k,j)-\ell(k,j+1)-\ell(l,j)+\ell(l,j+1)$ at each fixed $k,l\in[K]$ s.t.
$k<l$ is non-positive for all $j\in[K-1]$.

For the Logistic-AT surrogate loss $\phi=\phi_{\rm logi\text{-}at}$, the
statement (b1) is proved in Yamasaki (2023, Theorem 2), and the statement (b2)
relies on Yamasaki (2023, Theorems 3 and 4). The statements for the
Exponential-AT surrogate loss $\phi=\phi_{\rm expo\text{-}at}$ are novel
findings.

For the CL model (8), we found the following properties.

######  Theorem 3.

Assume ${\bm{b}}\in{\mathcal{B}}_{0}^{\rm ord}$. Then, it holds that

  * (c1)

$\sum_{l=1}^{k}P_{\rm cl}(l;u,{\bm{b}})=\frac{1}{1+e^{-(b_{k}-u)}}$ is
decreasing in $u$, and $\sum_{l=k+1}^{K}P_{\rm
cl}(l;u,{\bm{b}})=\frac{1}{1+e^{(b_{k}-u)}}$ is increasing in $u$, for
$k=1,\ldots,K-1$;

  * (c2)

$P_{\rm cl}(1;u,{\bm{b}})\to 1$ and $P_{\rm cl}(k;u,{\bm{b}})\to 0$ for
$k=2,\ldots,K$ as $u\to-\infty$, and $P_{\rm cl}(K;u,{\bm{b}})\to 1$ and
$P_{\rm cl}(k;u,{\bm{b}})\to 0$ for $k=1,\ldots,K-1$ as $u\to+\infty$;

and that, for each $k\in\\{2,\ldots,K-1\\}$,

  * (c3)

$P_{\rm cl}(k;u,{\bm{b}})$ is symmetric in $u$ around
$u=\frac{b_{k-1}+b_{k}}{2}$;

  * (c4)

$P_{\rm cl}(k;u,{\bm{b}})$ is maximized in $u$ at $u=\frac{b_{k-1}+b_{k}}{2}$,
increasing in $u$ if $u<\frac{b_{k-1}+b_{k}}{2}$, and decreasing in $u$ if
$u>\frac{b_{k-1}+b_{k}}{2}$;

  * (c5)

$P_{\rm cl}(k;u,{\bm{b}})$ with fixed $u$ and $\frac{b_{k-1}+b_{k}}{2}$ is
increasing in $b_{k}-b_{k-1}$.

Assume further that ${\bm{b}}={\bm{b}}^{[\Delta]}$ for some $\Delta>0$, and
that $b_{m-1}\leq u<b_{m}$ for some $m\in[K]$, where
${\bm{b}}^{[\Delta]}:=\Delta\cdot(0,1,\ldots,K-2)^{\top}$, $b_{0}:=-\infty$,
and $b_{K}:=+\infty$. Then, it holds that

  * (c6)

$P_{\rm cl}(2;u,{\bm{b}})\leq\cdots\leq P_{\rm cl}(m;u,{\bm{b}})$ if $m\geq
2$, and $P_{\rm cl}(m;u,{\bm{b}})\geq\cdots\geq P_{\rm cl}(K-1;u,{\bm{b}})$ if
$m\leq K-1$;

  * (c7)

$P_{\rm cl}(1;u,{\bm{b}})\leq\cdots\leq P_{\rm cl}(m;u,{\bm{b}})$ if $m\geq 2$
and $\Delta\geq\Delta_{1}$, and $P_{\rm cl}(m;u,{\bm{b}})\geq\cdots\geq P_{\rm
cl}(K;u,{\bm{b}})$ if $m\leq K-1$ and $\Delta\geq\Delta_{2}$, where
$\Delta_{1}$ is $\Delta$ satisfying
$\frac{2}{1+e^{-(b_{1}-u)}}=\frac{1}{1+e^{-(b_{2}-u)}}$ and $\Delta_{2}$ is
$\Delta$ satisfying $\frac{2}{1+e^{(b_{K-1}-u)}}=\frac{1}{1+e^{(b_{K-2}-u)}}$,
and where $\Delta_{1}$ and $\Delta_{2}$ are uniquely determined for each $u$.

The results (c1) and (c2) would be trivial, and the results (c3)–(c5) have
been described in Yamasaki (2023, Lemma 1), while the results (c6) and (c7)
are novel and important for our subsequent discussion.

(d1) ${\bm{b}}={\bm{b}}^{[\Delta]}$, $\Delta=1/3$ | (d2) ${\bm{b}}={\bm{b}}^{[\Delta]}$, $\Delta=1$ | (d3) ${\bm{b}}={\bm{b}}^{[\Delta]}$, $\Delta=3$
---|---|---
|  |
(e1) ${\bm{b}}=\acute{{\bm{b}}}^{[\Delta]}$, $\Delta=1/3$ | (e2) ${\bm{b}}=\acute{{\bm{b}}}^{[\Delta]}$, $\Delta=1$ | (e3) ${\bm{b}}=\acute{{\bm{b}}}^{[\Delta]}$, $\Delta=3$
|  |

Figure 2: Instances of the CL model of $K=10$. Figures show $P_{\rm
cl}(y;u,{\bm{b}})$ for $y=1,\ldots,10$, $u\in[-\Delta,9\Delta]$,
${\bm{b}}={\bm{b}}^{[\Delta]}$ (plates (d1)–(d3)),
$\acute{{\bm{b}}}^{[\Delta]}$ (plates (e1)–(e3)), and $\Delta=1/3,1,3$. At $u$
in the region where the background color is white or gray, the PMF $(P_{\rm
cl}(y;u,{\bm{b}}))_{y\in[10]}$ is unimodal or not.

Figure 2 shows instances of the CL model $(P_{\rm
cl}(y;u,{\bm{b}}))_{y\in[K]}$ of $K=10$ with the ordered equal-interval bias
parameter vector
${\bm{b}}={\bm{b}}^{[\Delta]}=\Delta\cdot(0,1,\ldots,8)^{\top}$ and ordered
unequal-interval bias parameter vector
${\bm{b}}=\acute{{\bm{b}}}^{[\Delta]}:=\Delta\cdot(0,0.5,0.9,1.5,4,6.5,7.1,7.6,8)^{\top}$
for $\Delta=1/3,1,3$. As Theorem 3 (c6) and (c7) show, the CL model with the
ordered equal-interval bias parameter vector ${\bm{b}}={\bm{b}}^{[\Delta]}$ is
unimodal when the gap $\Delta$ of adjacent bias parameters is large; see
Figure 2 (d1)–(d3). Therefore, one can find that the CL model is well suited
for representing homoscedastic unimodal data (especially, data having a CPD in
which the scale tends to be small overall). The CL model with the ordered
unequal-interval bias parameter vector ${\bm{b}}=\acute{{\bm{b}}}^{[\Delta]}$
shown in Figure 2 (e1)–(e3) are mode-wise heteroscedastic, and the CPD with
$\Delta=3$ is unimodal overall. This result suggests that the CL model can
represent mode-wise heteroscedastic unimodal data as well. On the other hand,
it should be noted that the CL model cannot represent overall heteroscedastic
data, for example, data that follow the large-scale CPD in Figure 2 (d2) in a
certain domain and the small-scale CPD in Figure 2 (d3) in another domain.

####  3.1.3 Analysis for a Special Instance: Squared-AT Loss

The Absolute- and Squared-AT losses adopt a non-monotonic function $\varphi$,
in which the shape is not similar to those we analyzed in Section 3.1.2.
Therefore, analogies from behaviors of the surrogate risk minimizer with the
Logistic- and Exponential-AT losses may not be convincing in understanding
those with the Absolute- and Squared-AT losses. We thus studied behaviors of
the surrogate risk minimizer with the Squared-AT loss and the corresponding
classifier, and obtained the following result (see Section 3.3 for results for
the Absolute-AT loss):

######  Theorem 4.

Let $\phi$ be the Squared-AT loss ($\phi=\phi_{\rm squa\text{-}at}$), and
${\mathcal{A}}\times{\mathcal{B}}\subseteq\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}\times{\mathcal{B}}_{0}^{\rm
ord}$ include $(\tilde{a},\tilde{{\bm{b}}})$ that satisfies, with
$c_{1}:=\Pr(Y\leq 1)$ and $c_{2}:=1+\frac{2}{K-1}(\sum_{y=1}^{K-1}\Pr(Y\leq
y)-K)-c_{1}$,

$\displaystyle\tilde{a}({\bm{x}})=c_{2}+\frac{2}{K-1}\sum_{y=1}^{K-1}y\Pr(Y=y|{\bm{X}}={\bm{x}}),\quad\tilde{b}_{y}=\Pr(Y\leq
y)-c_{1}$ (9)

for any ${\bm{x}}$ in the support of the probability distribution of
${\bm{X}}$ and every $y\in[K]$. Then, $(\bar{a},\bar{{\bm{b}}})$ defined by
(7) satisfies
$(\bar{a}({\bm{X}}),\bar{{\bm{b}}})=(\tilde{a}({\bm{X}}),\tilde{{\bm{b}}})$
almost surely. Also, $\bar{f}(\cdot)=h_{\rm
thr}(\bar{a}(\cdot);\bar{{\bm{t}}})$ with $\bar{{\bm{t}}}$ defined by

$\displaystyle\bar{t}_{k}=c_{2}+\frac{2}{K-1}(k+0.5)\text{ for }k\in[K-1]$
(10)

satisfies
$\operatorname{{\mathbb{E}}}[\ell(\bar{f}({\bm{X}}),Y)]=\min_{f:{\mathbb{R}}^{d}\to[K]}\operatorname{{\mathbb{E}}}[\ell(f({\bm{X}}),Y)]$,
if $\ell=\ell_{\rm sq}$.

This result guarantees the optimality of the classifier of the threshold
method independent of the underlying data distribution (only for the case with
$(\phi,\ell)=(\phi_{\rm squa\text{-}at},\ell_{\rm sq})$). Even in cases other
than $\ell=\ell_{\rm sq}$, which are not covered by this theorem, the
expression of the surrogate risk minimizer suggests that the threshold method
with $\phi=\phi_{\rm squa\text{-}at}$ works well when the data follow a
unimodal CPD with a small scale: Consider that, when
$\Pr(Y=y|{\bm{X}}={\bm{x}})\approx 1$ if
$y=M((\Pr(Y=y|{\bm{X}}={\bm{x}}))_{y\in[K]})$ and $0$ otherwise, one has
$\bar{a}({\bm{x}})\approx
c_{2}+\frac{2}{K-1}M((\Pr(Y=y|{\bm{X}}={\bm{x}}))_{y\in[K]})$ (on the other
hand, when $\Pr(Y=y|{\bm{X}}={\bm{x}})\approx\frac{1}{K}$ for all $y\in[K]$,
one has $\bar{a}({\bm{x}})\approx c_{2}+1$).

####  3.1.4 Conjecture

Theorem 2 guarantees the optimality of the surrogate risk minimizer and of the
resulting classifier under several popular tasks only for the Logistic-AT and
Exponential-AT losses and restricted class of the data distribution. However,
we conjecture that the goodness of the surrogate risk minimizer and resulting
classifier will be maintained to some extent even if the data distribution and
loss function change their shape somewhat. Thus, from Theorem 3, we conjecture
that, for AT losses based on a non-increasing function $\varphi$ that is
similar to the Logistic and Exponential losses and has no special property
(see Section 3.3), a classifier of threshold methods tends to perform well for
homoscedastic unimodal data and mode-wise heteroscedastic unimodal data. In
contrast, such threshold methods may perform poorly for overall
heteroscedastic unimodal data and almost non-unimodal data. Also, Theorem 4
gives a closed-form expression of the surrogate risk minimizer based on
$\phi=\phi_{\rm squa\text{-}at}$ and guarantees the optimality of the
resulting classifier independent of the data distribution for the task with
$\ell=\ell_{\rm sq}$. According to that expression, we conjecture that the
learning procedure with an AT loss based on a V-shaped function $\varphi$ like
$\varphi_{\rm squa}$ (with no special property; see Section 3.3) also performs
well when the data follow a unimodal CPD with a small scale.

###  3.2 Immediate-Threshold (IT) Loss

####  3.2.1 Analysis for Special Instances: Logistic- and Exponential-IT
Losses

In Section 3.2, we give analysis of the surrogate risk minimization of the
threshold method with an IT surrogate loss function, and conjecture about what
data distributions the resulting classifier will perform well or poorly for.

The following theorem suggests that threshold methods based on the Logistic-IT
or Exponential-IT loss perform well when the data follow a certain likelihood
model, known as the (_proportional odds_) _adjacent categories logit_ (_ACL_)
_model_ (Agresti, 2010; Yamasaki, 2022).

######  Theorem 5.

Assume that the random variable $({\bm{X}},Y)$ has the conditional probability
of $Y=y$ at ${\bm{X}}={\bm{x}}$,

$\displaystyle\Pr(Y=y|{\bm{X}}={\bm{x}})=P_{\rm
acl}(y;\tilde{a}({\bm{x}}),\tilde{{\bm{b}}}):=\frac{e^{-\sum_{k=1}^{y-1}(\tilde{b}_{k}-\tilde{a}({\bm{x}}))}}{\sum_{l=1}^{K}e^{-\sum_{k=1}^{l-1}(\tilde{b}_{k}-\tilde{a}({\bm{x}}))}},$
(11)

with $\tilde{a}:{\mathbb{R}}^{d}\to{\mathbb{R}}$ and
$\tilde{{\bm{b}}}\in{\mathcal{B}}_{0}$, for any ${\bm{x}}$ in the support of
the probability distribution of ${\bm{X}}$ and every $y\in[K]$. Let $\phi$ be
the Logistic-IT loss ($\phi=\phi_{\rm logi\text{-}it}$) or Exponential-IT loss
($\phi=\phi_{\rm expo\text{-}it}$), and
${\mathcal{A}}\times{\mathcal{B}}\subseteq\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}\times{\mathcal{B}}_{0}$
include $(\tilde{a},\tilde{{\bm{b}}})$ or
$(\tilde{a}(\cdot)/2,\tilde{{\bm{b}}}/2)$ respectively when $\phi=\phi_{\rm
logi\text{-}it}$ or $\phi=\phi_{\rm expo\text{-}it}$. Then, it holds that

  * (f1)

$(\bar{a},\bar{{\bm{b}}})$ defined by (7) satisfies
$(\bar{a}({\bm{X}}),\bar{{\bm{b}}})=(\tilde{a}({\bm{X}}),\tilde{{\bm{b}}})$ or
$(\bar{a}({\bm{X}}),\bar{{\bm{b}}})=(\tilde{a}({\bm{X}})/2,\tilde{{\bm{b}}}/2)$
almost surely respectively when $\phi=\phi_{\rm logi\text{-}it}$ or
$\phi=\phi_{\rm expo\text{-}it}$;

  * (f2)

$\bar{f}=h_{\rm thr}(\bar{a}(\cdot);\bar{{\bm{t}}})$ with $\bar{a}$ and
$\bar{{\bm{t}}}$ defined by (7) satisfies
$\operatorname{{\mathbb{E}}}[\ell(\bar{f}({\bm{X}}),Y)]=\min_{f:{\mathbb{R}}^{d}\to[K]}\operatorname{{\mathbb{E}}}[\ell(f({\bm{X}}),Y)]$,
if $\ell=\ell_{\rm zo}$;

  * (f3)

$\operatorname{{\mathbb{E}}}[\ell(h_{\rm
thr}(\bar{a}({\bm{X}});\bar{{\bm{t}}}),Y)]=\operatorname{{\mathbb{E}}}[\ell(h_{\rm
thr}(\bar{a}({\bm{X}});\bar{{\bm{b}}}),Y)]$ with $(\bar{a},\bar{{\bm{b}}})$
and $\bar{{\bm{t}}}$ defined by (7), if $\ell=\ell_{\rm zo}$ and
$\tilde{{\bm{b}}}\in{\mathcal{B}}_{0}^{\rm ord}$.

Alternatively let ${\mathcal{A}}=\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}$ and
${\mathcal{B}}={\mathcal{B}}_{0}^{\rm ord}$. Then, it holds that

  * (f4)

$\bar{{\bm{b}}}$ defined by (7) has overlapped components (i.e.,
$\bar{b}_{k}=\bar{b}_{l}$ for some $k,l\in[K-1]$ s.t. $k\neq l$), if
$\tilde{{\bm{b}}}\not\in{\mathcal{B}}_{0}^{\rm ord}$.

To our knowledge, this type of result is the first for IT losses.

For the ACL model (11), we found the following properties.

######  Theorem 6.

It holds that, with $b_{0}:=-\infty$ and $b_{K}:=+\infty$,

  * (g1)

for each $k\in[K-1]$, $P_{\rm acl}(k+1;u,{\bm{b}})/P_{\rm
acl}(k;u,{\bm{b}})=(\frac{1}{1+e^{(b_{k}-u)}})/(\frac{1}{1+e^{-(b_{k}-u)}})=e^{-(b_{k}-u)}$;

  * (g2)

$(P_{\rm acl}(y;u,{\bm{b}}))_{y\in[K]}$ is unimodal at any $u\in{\mathbb{R}}$
(i.e., $P_{\rm acl}(1;u,{\bm{b}})\leq\cdots\leq P_{\rm acl}(m;u,{\bm{b}})$ and
$P_{\rm acl}(m;u,{\bm{b}})\geq\cdots\geq P_{\rm acl}(K;u,{\bm{b}})$ when
$b_{m-1}\leq u\leq b_{m}$ for $m\in[K]$), if
${\bm{b}}\in{\mathcal{B}}_{0}^{\rm ord}$;

  * (g3)

$(P_{\rm acl}(y;u,{\bm{b}}))_{y\in[K]}$ is unimodal, if
$\max(\\{1\\}\cup\\{k\in[K-1]\mid b_{k}\leq u\\})\leq\min(\\{k\in[K-1]\mid
b_{k}\geq u\\}\cup\\{K\\})$;

  * (g4)

$(P_{\rm acl}(y;u,{\bm{b}}))_{y\in[K]}$ is not unimodal at any
$u\in(b_{l},b_{k})$, if $b_{k}>b_{l}$ for $k,l\in[K-1]$ s.t. $k<l$.

The results (g1) and (g2) are shown in Yamasaki (2022, Theorem 3), while the
results (g3) and (g4) are novel findings.

(h1) ${\bm{b}}={\bm{b}}^{[\Delta]}$, $\Delta=1/3$ | (h2) ${\bm{b}}={\bm{b}}^{[\Delta]}$, $\Delta=1$ | (h3) ${\bm{b}}={\bm{b}}^{[\Delta]}$, $\Delta=3$
---|---|---
|  |
(i1) ${\bm{b}}=\acute{{\bm{b}}}^{[\Delta]}$, $\Delta=1/3$ | (i2) ${\bm{b}}=\acute{{\bm{b}}}^{[\Delta]}$, $\Delta=1$ | (i3) ${\bm{b}}=\acute{{\bm{b}}}^{[\Delta]}$, $\Delta=3$
|  |
(j1) ${\bm{b}}=\grave{{\bm{b}}}^{[\Delta]}$, $\Delta=1/3$ | (j2) ${\bm{b}}=\grave{{\bm{b}}}^{[\Delta]}$, $\Delta=1$ | (j3) ${\bm{b}}=\grave{{\bm{b}}}^{[\Delta]}$, $\Delta=3$
|  |

Figure 3: Instances of the ACL model of $K=10$. Figures show $P_{\rm
acl}(y;u,{\bm{b}})$ for $y=1,\ldots,10$, $u\in[-\Delta,9\Delta]$,
${\bm{b}}={\bm{b}}^{[\Delta]}$ (plates (h1)–(h3)),
$\acute{{\bm{b}}}^{[\Delta]}$ (plates (i1)–(i3)),
$\grave{{\bm{b}}}^{[\Delta]}$ (plates (j1)–(j3)), and $\Delta=1/3,1,3$. At $u$
in the region where the background color is white or gray, the PMF $(P_{\rm
acl}(y;u,{\bm{b}}))_{y\in[10]}$ is unimodal or not.

Figure 3 shows instances of the ACL model $(P_{\rm
acl}(y;u,{\bm{b}}))_{y\in[K]}$ of $K=10$ with the ordered equal-interval bias
parameter vector ${\bm{b}}={\bm{b}}^{[\Delta]}$, ordered unequal-interval bias
parameter vector ${\bm{b}}=\acute{{\bm{b}}}^{[\Delta]}$, and non-ordered bias
parameter vector
${\bm{b}}=\grave{{\bm{b}}}^{[\Delta]}:=\Delta\cdot(0,1,2,3,5,4,6,7,8)^{\top}$
for $\Delta=1/3,1,3$. Theorem 6 (g2)–(g4) can be confirmed from Figure 3: the
ACL model $(P_{\rm acl}(y;u,{\bm{b}}))_{y\in[10]}$ is unimodal for the ordered
bias parameter vectors
${\bm{b}}={\bm{b}}^{[\Delta]},\acute{{\bm{b}}}^{[\Delta]}$, and partly non-
unimodal for the non-ordered bias parameter vector
${\bm{b}}=\grave{{\bm{b}}}^{[\Delta]}$. The CL and ACL models with the ordered
equal-interval bias parameter vector ${\bm{b}}={\bm{b}}^{[\Delta]}$ are
similar; compare Figure 2 (d1)–(d3) and Figure 3 (h1)–(h3). Therefore, one can
find that the ACL model is also well suited for representing homoscedastic
unimodal data. The ACL model with the ordered unequal-interval bias parameter
vector ${\bm{b}}=\acute{{\bm{b}}}^{[\Delta]}$ shown in Figure 3 (i1)–(i3) is
mode-wise heteroscedastic, and similar to the counterpart of the CL model
shown in Figure 2 (e1)–(e3). This result suggests that the ACL model can
represent mode-wise heteroscedastic unimodal data as well. On the other hand,
as the CL model, the ACL model cannot represent overall heteroscedastic data
well.

####  3.2.2 Analysis for a Special Instance: Squared-IT Loss

A function $\varphi$ adopted for the Absolute- and Squared-IT losses is non-
monotonic and dissimilar to those we analyzed in Section 3.2.1. Therefore,
analogies from behaviors of the surrogate risk minimizer with the Logistic-
and Exponential-IT losses may not be convincing in understanding those with
the Absolute- and Squared-IT losses. We thus studied behaviors of the
surrogate risk minimizer with the Squared-IT loss and the corresponding
classifier, and obtained the following result (see Section 3.3 for results for
the Absolute-IT loss):

######  Theorem 7.

Assume that $\Pr(Y\in\\{y,y+1\\})>0$ for all $y\in[K-1]$, and let $\phi$ be
the Squared-IT loss ($\phi=\phi_{\rm squa\text{-}it}$), and
${\mathcal{A}}\times{\mathcal{B}}\subseteq\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}\times{\mathcal{B}}_{0}$
include $(\tilde{a},\tilde{{\bm{b}}})$ that satisfies

$\displaystyle\begin{split}&\tilde{a}({\bm{x}})=\frac{\sum_{y=1}^{K-1}\Pr(Y\in\\{y,y+1\\}|{\bm{X}}={\bm{x}})\tilde{b}_{y}-\Pr(Y=1|{\bm{X}}={\bm{x}})+\Pr(Y=K|{\bm{X}}={\bm{x}})}{2-\Pr(Y\in\\{1,K\\}|{\bm{X}}={\bm{x}})},\\\
&\tilde{b}_{y}=\frac{\Pr(Y=y)-\Pr(Y=y+1)+\operatorname{{\mathbb{E}}}[\Pr(Y\in\\{y,y+1\\}|{\bm{X}})\tilde{a}({\bm{X}})]}{\Pr(Y\in\\{y,y+1\\})}\end{split}$
(12)

for any ${\bm{x}}$ in the support of the probability distribution of
${\bm{X}}$ and every $y\in[K]$ and $\tilde{b}_{1}=0$, where the expectation
$\operatorname{{\mathbb{E}}}[\cdot]$ is taken for ${\bm{X}}$. Then,
$(\bar{a},\bar{{\bm{b}}})$ defined by (7) satisfies
$(\bar{a}({\bm{X}}),\bar{{\bm{b}}})=(\tilde{a}({\bm{X}}),\tilde{{\bm{b}}})$
almost surely.

Note that (12) can be solved by
$\bar{{\bm{b}}}={\mathbf{D}}\bar{{\bm{b}}}+{\bm{c}}$, that is,
$\bar{{\bm{b}}}=({\mathbf{I}}-{\mathbf{D}})^{-1}{\bm{c}}$ under the
invertibility of the matrix ${\mathbf{I}}-{\mathbf{D}}$ with the
$(K-1)\times(K-1)$ identity matrix ${\mathbf{I}}$,
${\bm{c}}=(c_{y})_{y\in[K-1]}$, and ${\mathbf{D}}=(d_{y,k})_{y,k\in[K-1]}$
that are consisted of

$\displaystyle\begin{split}&c_{y}:=\frac{\Pr(Y=y)-\Pr(Y=y+1)-\operatorname{{\mathbb{E}}}\bigl{[}\frac{\Pr(Y\in\\{y,y+1\\}|{\bm{X}})\\{\Pr(Y=1|{\bm{X}})-\Pr(Y=K|{\bm{X}})\\}}{2-\Pr(Y\in\\{1,K\\}|{\bm{X}})}\bigl{]}}{\Pr(Y\in\\{y,y+1\\})},\\\
&d_{y,k}:=\begin{cases}0&\text{if }k=1,\\\
\frac{\operatorname{{\mathbb{E}}}\bigl{[}\frac{\Pr(Y\in\\{y,y+1\\}|{\bm{X}})\Pr(Y\in\\{k,k+1\\}|{\bm{X}})}{2-\Pr(Y\in\\{1,K\\}|{\bm{X}})}\bigl{]}}{\Pr(Y\in\\{y,y+1\\})}&\text{otherwise}.\end{cases}\end{split}$
(13)

The expression of the surrogate risk minimizer suggests that the threshold
method with $\phi=\phi_{\rm squa\text{-}it}$ works well when the data follow a
unimodal CPD with a small scale: consider that, when
$\Pr(Y=y|{\bm{X}}={\bm{x}})\approx 1$ if
$y=M((\Pr(Y=y|{\bm{X}}={\bm{x}}))_{y\in[K]})$ and $0$ otherwise for any
${\bm{x}}$ and $\Pr(Y=y)\approx\frac{1}{K}$ for all $y\in[K]$, one has
$\bar{b}_{k}\approx 2(k-1)$ for all $k\in[K-1]$ and $\bar{a}({\bm{x}})\approx
2M((\Pr(Y=y|{\bm{X}}={\bm{x}}))_{y\in[K]}-3$ (on the other hand, when
$\Pr(Y=y|{\bm{X}}={\bm{x}})\approx\frac{1}{K}$ for any ${\bm{x}}$ and
$\Pr(Y=y)\approx\frac{1}{K}$ for all $y\in[K]$, one has that
$\bar{b}_{k}\approx 0$ for $y=1$, $\frac{1}{2}$ for $y=2,\ldots,K-2$, and $1$
for $y=K-1$ and $\bar{a}({\bm{x}})\approx\frac{1}{2}$).

####  3.2.3 Overlap of Optimized Bias Parameters

For an IT loss $\phi$, a minimizer
$(a,{\bm{b}})=(\bar{a}^{\prime},\bar{{\bm{b}}}^{\prime})$ of the surrogate
risk $\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]$ over
${\mathcal{A}}\times{\mathcal{B}}_{0}$ has no guarantee to satisfy the order
condition unlike that for an AT loss, namely, it may satisfy
$\bar{{\bm{b}}}^{\prime}\not\in{\mathcal{B}}_{0}^{\rm ord}$. When
$\bar{{\bm{b}}}^{\prime}\not\in{\mathcal{B}}_{0}^{\rm ord}$, the bias
parameter vector of the surrogate risk minimizer
$(a,{\bm{b}})=(\bar{a},\bar{{\bm{b}}})$ over
${\mathcal{A}}\times{\mathcal{B}}_{0}^{\rm ord}$ has overlapped components.
Such a situation is not only exemplified in Theorem 5 (f3), but occurs
frequently in practice. In this section, we describe an inherent trouble of
the threshold method that adopts an IT loss function and the ordered class of
the bias parameter vector, owing to the overlap of optimized bias parameters.

Assume that the surrogate risk minimizer $(\bar{a},\bar{{\bm{b}}})$ satisfies

$\displaystyle\bar{b}_{k}=c\text{ for all }k\in\\{l,\ldots,m\\}\text{ with
some }c\in{\mathbb{R}},l,m\in[K-1]\text{ s.t. }l<m.$ (14)

Under this setting, the conditional surrogate risk at ${\bm{X}}={\bm{x}}$
becomes

$\displaystyle\begin{split}\operatorname{{\mathbb{E}}}[\phi(\bar{a}({\bm{x}}),\bar{{\bm{b}}},Y)]&=\Pr(Y\in\\{l+1,\ldots,m\\}|{\bm{X}}={\bm{x}})\\{\varphi(\bar{a}({\bm{x}})-c)+\varphi(c-\bar{a}({\bm{x}}))\\}\\\
&+\sum_{y\in\\{\ldots,l,m+1,\ldots\\}}\Pr(Y=y|{\bm{X}}={\bm{x}})\\{\varphi(\bar{a}({\bm{x}})-\bar{b}_{y-1})+\varphi(\bar{b}_{y}-\bar{a}({\bm{x}}))\\}.\end{split}$
(15)

If $\Pr(Y\in\\{\ldots,l,m+1,\ldots\\}|{\bm{X}}={\bm{x}})=0$ for
${\bm{x}}\in{\mathcal{X}}_{0}$ with a some domain
${\mathcal{X}}_{0}\subseteq{\mathbb{R}}^{d}$, the optimized 1DT value
$\bar{a}({\bm{x}})\in\operatorname{{arg\,min}}_{a({\bm{x}})\in{\mathbb{R}}}\operatorname{{\mathbb{E}}}[\phi(a({\bm{x}}),\bar{{\bm{b}}},Y)]$
for ${\bm{x}}\in{\mathcal{X}}_{0}$ is determined independently of the
conditional probabilities
$\Pr(Y=l+1|{\bm{X}}={\bm{x}}),\ldots,\Pr(Y=m|{\bm{X}}={\bm{x}})$. Especially
when $\varphi$ is strictly convex, optimized 1DT values are concentrated like
$\bar{a}({\bm{x}})=c$ for any ${\bm{x}}\in{\mathcal{X}}_{0}$. Then, the
resulting classifier cannot classify data in ${\mathcal{X}}_{0}$ well.

The above demonstration is on an extreme situation. However, even in more mild
situation, overlap of the optimized bias parameter vector makes it difficult
to reflect variation of the data distribution in the learning of the 1DT. This
trouble is inherent to the combination of the IT loss and ordered class
${\mathcal{B}}_{0}^{\rm ord}$ of bias parameter vector and may lead to the
sub-optimal approximation error.

####  3.2.4 Conjecture

According to the discussion (Theorems 5 and 6) in Section 3.2.1, for the case
using IT losses we present a conjecture similar to that for AT losses: for IT
losses based on a non-increasing function $\varphi$ that has no special
property, the classifier of threshold methods would tend to perform well for
homoscedastic unimodal data and mode-wise heteroscedastic unimodal data, and
may perform poorly for overall heteroscedastic unimodal data and almost non-
unimodal data. Also, Theorem 7 gives a closed-form expression of the surrogate
risk minimizer based on $\phi=\phi_{\rm squa\text{-}it}$. According to that
expression, we conjecture that the learning procedure with an IT loss based on
a V-shaped function $\varphi$ like $\varphi_{\rm squa}$ (with no special
property; see Section 3.3) performs well when the data follow a unimodal CPD
with a small scale. Furthermore, the order constraint on the bias parameter
vector ${\mathcal{B}}={\mathcal{B}}_{0}^{\rm ord}$ for IT losses may cause the
overlap of learned bias parameter vector, which has a risk to negatively
influence the classification performance, as described in Section 3.2.3.

###  3.3 Piecewise-Linear (PL) Loss

We here study the learning procedure based on a _piecewise-linear_ (_PL_)
function $\varphi$.

We define the piecewise-linearity as follows:

######  Definition 1.

If a function $\varphi:{\mathbb{R}}\to{\mathbb{R}}$ satisfies that
$\varphi(u)=a_{i}+b_{i}u$ for $u$ in $i$-th one of the intervals
$(-\infty,c_{1}],(c_{1},c_{2}],\ldots,(c_{I-1},c_{I}],(c_{I},+\infty)$ for all
$i\in[I+1]$, with
$a_{1},\ldots,a_{I+1},b_{1},\ldots,b_{I+1},c_{1},\ldots,c_{I}\in{\mathbb{R}}$
satisfying $a_{i}\neq a_{i+1}$ or $b_{i}\neq b_{i+1}$ for all $i\in[I]$ and
$c_{1}<\cdots<c_{I}$, we say that $\varphi$ is PL with $I$ _knots_
$c_{1},\ldots,c_{I}$.

For example, the hinge loss function $\varphi_{\rm hing}$ and the absolute
loss function $\varphi_{\rm abso}$ are PL with 1 knot, and the ramp loss
function $\varphi_{\rm ramp}$ is PL with 2 knots.

When $\varphi$ is PL, the corresponding AT and IT loss functions and the
conditional surrogate risk
$\operatorname{{\mathbb{E}}}[\phi(a({\bm{x}}),{\bm{b}},Y)]$ are also PL:

######  Theorem 8.

Assume that $\varphi$ is PL with $I$ knots, and ${\bm{b}}=(b_{k})_{k\in[K-1]}$
consists of different $J$ values, with $I\in{\mathbb{N}}$ and $J\in[K-1]$.
Then, the AT loss $\phi(\cdot,{\bm{b}},y)$ defined by (3) with $\varphi$ is PL
with at most $IJ$ knots, and the IT loss $\phi(\cdot,{\bm{b}},y)$ defined by
(4) with $\varphi$ is PL with $I$ knots if $y\in\\{1,K\\}$ or at most $2I$
knots otherwise. Moreover, for both of the AT and IT losses, the conditional
surrogate risk $\operatorname{{\mathbb{E}}}[\phi(\cdot,{\bm{b}},Y)]$ is PL
with at most $2IJ$ knots.

In general, the PL conditional surrogate risk
$\operatorname{{\mathbb{E}}}[\phi(a({\bm{x}}),{\bm{b}},Y)]$ is minimized with
respect to $a({\bm{x}})\in{\mathbb{R}}$ at one of its knots (except for, when
the CPD $(\Pr(Y=y|{\bm{X}}={\bm{x}}))_{y\in[K]}$ is special so that
$\operatorname{{\mathbb{E}}}[\phi(a({\bm{x}}),{\bm{b}},Y)]$ has a plateau
regarding $a({\bm{x}})$ and its minimizer is not uniquely determined). When
the optimized 1DT $\bar{a}({\bm{x}})$ takes the same value for ${\bm{x}}$’s
with different CPD values, the resulting classifier cannot classify data on
such ${\bm{x}}$’s successfully, as the following example:

######  Example 1.

Consider the setting with $K=3$, $\phi=\phi_{\rm hing\text{-}it}$,
${\mathcal{A}}=\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}$, and
${\mathcal{B}}={\mathcal{B}}_{0}^{\rm ord}$. In this setting, Theorem 9 in
Appendix B shows $\bar{b}_{2}\in[0,2]$, and the conditional surrogate risk for
$(a,\bar{{\bm{b}}})$ given ${\bm{X}}={\bm{x}}$ at its knots
$-1,\bar{b}_{2}-1,1,\bar{b}_{2}+1$ becomes

$\displaystyle\operatorname{{\mathbb{E}}}[\phi(a({\bm{x}}),\bar{{\bm{b}}},Y)]$
(16)
$\displaystyle=\begin{cases}2\Pr(Y=2|{\bm{X}}={\bm{x}})+(2+\bar{b}_{2})\Pr(Y=3|{\bm{X}}={\bm{x}})&\text{if~{}}a({\bm{x}})=-1,\\\
\bar{b}_{2}\Pr(Y=1|{\bm{X}}={\bm{x}})+(2-\bar{b}_{2})\Pr(Y=2|{\bm{X}}={\bm{x}})+2\Pr(Y=3|{\bm{X}}={\bm{x}})&\text{if~{}}a({\bm{x}})=\bar{b}_{2}-1,\\\
2\Pr(Y=1|{\bm{X}}={\bm{x}})+(2-\bar{b}_{2})\Pr(Y=2|{\bm{X}}={\bm{x}})+\bar{b}_{2}\Pr(Y=3|{\bm{X}}={\bm{x}})&\text{if~{}}a({\bm{x}})=1,\\\
(2+\bar{b}_{2})\Pr(Y=1|{\bm{X}}={\bm{x}})+2\Pr(Y=2|{\bm{X}}={\bm{x}})&\text{if~{}}a({\bm{x}})=\bar{b}_{2}+1.\end{cases}$

By comparing the above four terms, one can see that the minimizer
$\bar{a}({\bm{x}})=\operatorname{{arg\,min}}_{a({\bm{x}})\in{\mathbb{R}}}\operatorname{{\mathbb{E}}}[\phi(a({\bm{x}}),\bar{{\bm{b}}},Y)]$
is

$\displaystyle\bar{a}({\bm{x}})=\begin{cases}-1&\text{if~{}}{\bm{x}}\in{\mathcal{X}}_{1},\\\
\bar{b}_{2}-1&\text{if~{}}{\bm{x}}\in{\mathcal{X}}_{2},\\\
1&\text{if~{}}{\bm{x}}\in{\mathcal{X}}_{3},\\\
\bar{b}_{2}+1&\text{if~{}}{\bm{x}}\in{\mathcal{X}}_{4},\end{cases}$ (17)

where the domains
${\mathcal{X}}_{1},\ldots,{\mathcal{X}}_{4}\subseteq{\mathbb{R}}^{d}$
splitting the support of the distribution of ${\bm{X}}$ are defined as

$\displaystyle\begin{split}&{\mathcal{X}}_{1}:=\\{{\bm{x}}\mid\Pr(Y=1|{\bm{X}}={\bm{x}})>\Pr(Y=2|{\bm{X}}={\bm{x}})+\Pr(Y=3|{\bm{X}}={\bm{x}})\\},\\\
&{\mathcal{X}}_{2}:=\\{{\bm{x}}\mid\Pr(Y=2|{\bm{X}}={\bm{x}})>\Pr(Y=1|{\bm{X}}={\bm{x}})-\Pr(Y=3|{\bm{X}}={\bm{x}})>0\\},\\\
&{\mathcal{X}}_{3}:=\\{{\bm{x}}\mid\Pr(Y=2|{\bm{X}}={\bm{x}})>\Pr(Y=3|{\bm{X}}={\bm{x}})-\Pr(Y=1|{\bm{X}}={\bm{x}})>0\\},\\\
&{\mathcal{X}}_{4}:=\\{{\bm{x}}\mid\Pr(Y=3|{\bm{X}}={\bm{x}})>\Pr(Y=1|{\bm{X}}={\bm{x}})+\Pr(Y=2|{\bm{X}}={\bm{x}})\\}.\end{split}$
(18)

The surrogate risk becomes

$\displaystyle\begin{split}\operatorname{{\mathbb{E}}}[\phi(\bar{a}({\bm{X}}),\bar{{\bm{b}}},Y)]&=\bar{b}_{2}\bigl{\\{}\Pr({\bm{X}}\in{\mathcal{X}}_{2}\cup{\mathcal{X}}_{4},Y=1)-\Pr({\bm{X}}\in{\mathcal{X}}_{2}\cup{\mathcal{X}}_{3},Y=2)\\\
&\hphantom{=\bar{b}_{2}\bigl{\\{}}+\Pr({\bm{X}}\in{\mathcal{X}}_{1}\cup{\mathcal{X}}_{3},Y=3)\bigr{\\}}+(\text{$\bar{b}_{2}$-independent
term}),\end{split}$ (19)

which implies that the surrogate risk minimizer $(\bar{a},\bar{{\bm{b}}})$
depends on the condition

$\displaystyle\Pr({\bm{X}}\in{\mathcal{X}}_{2}\cup{\mathcal{X}}_{4},Y=1)+\Pr({\bm{X}}\in{\mathcal{X}}_{1}\cup{\mathcal{X}}_{3},Y=3)\gtrless\Pr({\bm{X}}\in{\mathcal{X}}_{2}\cup{\mathcal{X}}_{3},Y=2).$
(20)

If the left-hand side is greater than the right-hand side in the above, then
the surrogate risk minimizer becomes ‘phase-1’: $\bar{b}_{1}=\bar{b}_{2}=0$
and

$\displaystyle\bar{a}({\bm{x}})=\begin{cases}-1&\text{if~{}}{\bm{x}}\in{\mathcal{X}}_{1}\cup{\mathcal{X}}_{2},\\\
1&\text{if~{}}{\bm{x}}\in{\mathcal{X}}_{3}\cup{\mathcal{X}}_{4}.\end{cases}$
(21)

In the other case, the surrogate risk minimizer becomes ‘phase-2’:
$\bar{b}_{1}=0$, $\bar{b}_{2}=2$, and

$\displaystyle\bar{a}({\bm{x}})=\begin{cases}-1&\text{if~{}}{\bm{x}}\in{\mathcal{X}}_{1},\\\
1&\text{if~{}}{\bm{x}}\in{\mathcal{X}}_{2}\cup{\mathcal{X}}_{3},\\\
3&\text{if~{}}{\bm{x}}\in{\mathcal{X}}_{4}.\end{cases}$ (22)

The phase-1 may be particularly problematic for the 3-class classification
problem. We demonstrate below that the surrogate risk minimizer tends to be in
the phase-1 especially when the scale of the CPD is large. Assume further that
${\bm{X}}$ has probabilities $\Pr({\bm{X}}={\bm{x}}^{[i]})=p_{i}$ for
$i\in[4]$ with $(p_{i})_{i\in[4]}\in\Delta_{3}$ at four different points
${\bm{x}}^{[1]},\ldots,{\bm{x}}^{[4]}$, and the CPD of $Y$ at each of these
points is unimodal and
$(\Pr(Y=y|{\bm{X}}={\bm{x}}^{[i]}))_{y\in[3]}=(q_{1},q_{2},q_{3}),(q_{1},q_{3},q_{2}),(q_{2},q_{3},q_{1}),(q_{3},q_{2},q_{1})$
for $i\in[4]$ with $(q_{i})_{i\in[3]}\in\Delta_{2}$ s.t. $0\leq
q_{1}<q_{2}<q_{3}$.

If $q_{3}>q_{1}+q_{2}$, it holds that
${\mathcal{X}}_{1}=\\{{\bm{x}}^{[4]}\\}$,
${\mathcal{X}}_{2}=\\{{\bm{x}}^{[3]}\\}$,
${\mathcal{X}}_{3}=\\{{\bm{x}}^{[2]}\\}$,
${\mathcal{X}}_{4}=\\{{\bm{x}}^{[1]}\\}$, and
$\Pr({\bm{X}}\in{\mathcal{X}}_{2}\cup{\mathcal{X}}_{4},Y=1)=p_{3}q_{2}+p_{1}q_{1}$,
$\Pr({\bm{X}}\in{\mathcal{X}}_{2}\cup{\mathcal{X}}_{3},Y=2)=p_{3}q_{3}+p_{2}q_{3}$,
$\Pr({\bm{X}}\in{\mathcal{X}}_{1}\cup{\mathcal{X}}_{3},Y=3)=p_{4}q_{1}+p_{2}q_{2}$,
and the condition for the phase transition (20) becomes

$\displaystyle(p_{1}+p_{4})q_{1}\gtrless(p_{2}+p_{3})(q_{3}-q_{2}).$ (23)

If $q_{3}<q_{1}+q_{2}$, it holds that ${\mathcal{X}}_{1}=\emptyset$,
${\mathcal{X}}_{2}=\\{{\bm{x}}^{[3]},{\bm{x}}^{[4]}\\}$,
${\mathcal{X}}_{3}=\\{{\bm{x}}^{[1]},{\bm{x}}^{[2]}\\}$,
${\mathcal{X}}_{4}=\emptyset$, and
$\Pr({\bm{X}}\in{\mathcal{X}}_{2}\cup{\mathcal{X}}_{4},Y=1)=p_{3}q_{2}+p_{4}q_{3}$,
$\Pr({\bm{X}}\in{\mathcal{X}}_{2}\cup{\mathcal{X}}_{3},Y=2)=p_{1}q_{2}+p_{2}q_{3}+p_{3}q_{3}+p_{4}q_{2}$,
$\Pr({\bm{X}}\in{\mathcal{X}}_{1}\cup{\mathcal{X}}_{3},Y=3)=p_{1}q_{3}+p_{2}q_{2}$,
and the condition for the phase transition (20) becomes

$\displaystyle(p_{1}+p_{4})\gtrless(p_{2}+p_{3}).$ (24)

(k1) $(p_{1},p_{2})=\ldots,(0.2,0.3)$ |  (k2) $(p_{1},p_{2})=(0.3,0.2)$ |  (k3) $(p_{1},p_{2})=(0.4,0.1)$ |  (k4) $(p_{1},p_{2})=(0.5,0)$
---|---|---|---
|  |  |
Figure 4: Phase transition of the surrogate risk minimizer for Example 1 with
$(p_{1},p_{2})=(p_{4},p_{3})=(0,0.5),(0.1,0.4),\ldots,(0.5,0)$. The surrogate
risk minimizer for $(q_{1},q_{2},q_{3})$ in the red (resp. blue) region is in
the phase-1 (resp. phase-2). For example, the CPD has a small scale for
$(q_{1},q_{2},q_{3})\approx(0,0,1)$ or a large scale for
$(q_{1},q_{2},q_{3})\approx(1/3,1/3,1/3)$.

Figure 4 shows the phase transition of the surrogate risk minimizer. From this
figure, one can find that the larger the scale of the CPD, the more likely the
surrogate risk minimizer tends to be in the phase-1.

Binary classification methods such as support vector classification (Cortes
and Vapnik, 1995) also apply a PL surrogate loss so that outputs of the
optimized model can be concentrated at a few points, but they have no trouble
that the approximation error becomes sub-optimal; the trouble of the PL loss
in threshold methods becomes striking when learned 1DT values are concentrated
on a number of points less than $K$ under a $K$-class problem.

According to the consideration in this section, one can see that the
combination of an IT surrogate loss and the ordered class of the bias
parameter vector should be used with caution and may not work well when the
data have large scale, even if they are unimodal.

##  4 Numerical Experiments

###  4.1 Simulation Study

With the aim of understanding how the design of the learning procedure for a
threshold method affects the approximation error of that method, we presented
several theorems and conjectures in Section 3. In order to verify these
results experimentally, we performed the following simulation study: As a
simulation of the surrogate risk minimization
$\min_{a\in{\mathcal{A}},{\bm{b}}\in{\mathcal{B}}}\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]$,
we solved the numerical optimization problem

$\displaystyle\underset{a_{1},\ldots,a_{N}\in{\mathbb{R}},{\bm{b}}\in{\mathcal{B}}}{\min}\,\frac{1}{N}\sum_{i=1}^{N}\sum_{y=1}^{K}p_{i,y}\phi(a_{i},{\bm{b}},y)$
(25)

with $N=100$ and $K=10$. This problem simulates the learning procedure of a
threshold method with the surrogate loss function $\phi$, class of the 1DT
${\mathcal{A}}=\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}$, and class of the bias
parameter vector ${\mathcal{B}}$ for data in which the underlying explanatory
variable ${\bm{X}}$ follows the uniform distribution on $N$ different points
${\bm{x}}^{[1]},\ldots,{\bm{x}}^{[N]}$ and in which the CPD of the $K$-class
target variable $Y$ takes $(p_{i,y})_{y\in[K]}$ at $i$-th point
${\bm{x}}^{[i]}$.

##### Data Distributions

Let $\tilde{a}^{[N,\Delta]}_{i}:=(\tfrac{(i-1)K}{N-1}-1)\Delta$. We considered
the following 15 instances of the CPD: homoscedastic unimodal data
distribution H-$\Delta$ with $\Delta=1/3,1,3$,

$\displaystyle p_{i,y}=P_{\rm
acl}(y;\tilde{a}^{[N,\Delta]}_{i},{\bm{b}}^{[\Delta]})\text{~{}for~{}}i\in[N],y\in[K];$
(26)

mode-wise heteroscedastic unimodal data distribution M-$\Delta$ with
$\Delta=1/3,1,3$,

$\displaystyle p_{i,y}=P_{\rm
acl}(y;\tilde{a}^{[N,\Delta]}_{i},\acute{{\bm{b}}}^{[\Delta]})\text{~{}for~{}}i\in[N],y\in[K];$
(27)

almost unimodal (partly non-unimodal) data distribution A-$\Delta$ with
$\Delta=1/3,1,3$,

$\displaystyle p_{i,y}=P_{\rm
acl}(y;\tilde{a}^{[N,\Delta]}_{i},\grave{{\bm{b}}}^{[\Delta]})\text{~{}for~{}}i\in[N],y\in[K];$
(28)

overall heteroscedastic data unimodal distribution O-($\Delta_{1},\Delta_{2}$)
with $(\Delta_{1},\Delta_{2})=(1/3,1),(1/3,3),(1,3)$,

$\displaystyle p_{i,y}=P_{\rm
acl}(y;\tilde{a}^{[N/2,\Delta_{1}]}_{i},{\bm{b}}^{[\Delta_{1}]})\text{ and
}p_{i+N/2,y}=P_{\rm
acl}(y;\tilde{a}^{[N/2,\Delta_{2}]}_{i},{\bm{b}}^{[\Delta_{2}]})\text{~{}for~{}}i=[\tfrac{N}{2}],y\in[K];$
(29)

almost non-unimodal data distribution N-$\Delta$ with $\Delta=1/3,1,3$,

$\displaystyle p_{i,y}=P_{\rm
acl}(\pi(y);\tilde{a}^{[N,\Delta]}_{i},{\bm{b}}^{[\Delta]})\text{~{}for~{}}i\in[N],y\in[K],$
(30)

where the function $\pi$ maps $1,\ldots,10$ to $1,10,2,9,3,8,4,7,5,6$. These
instances are based on those shown in Figure 3. Here,
${\bm{b}}^{[\Delta]}=\Delta\cdot(0,1,\ldots,8)^{\top}$ is ordered equal-
interval,
$\acute{{\bm{b}}}^{[\Delta]}=\Delta\cdot(0,0.5,0.9,1.5,4,6.5,7.1,7.6,8)^{\top}$
is ordered unequal-interval, and
$\grave{{\bm{b}}}^{[\Delta]}=\Delta\cdot(0,1,2,3,5,4,6,7,8)^{\top}$ is non-
ordered. Also, $\Delta$, $\Delta_{1}$, and $\Delta_{2}$ control the scale of
the data distribution; the larger they are, the smaller scale the associated
data distribution have. We basically suppose that the ordinal data tend to
have the unimodality, and hence consider that the data distributions
H-$\Delta$, M-$\Delta$, A-$\Delta$, and O-($\Delta_{1},\Delta_{2}$) can be
adequate as a data distribution underlying the ordinal data, but N-$\Delta$ is
not.

##### Methods

As the surrogate loss function $\phi$, we tried the Logistic, Hinge, Smoothed-
Hinge, Squared-Hinge, Exponential, Absolute, and Squared-AT and -IT losses. As
the class of the bias parameter vector ${\mathcal{B}}$, we considered
${\mathcal{B}}_{0}^{\rm ord}$ (ordered class) for AT losses, and
${\mathcal{B}}_{0}$ (non-ordered class) and ${\mathcal{B}}_{0}^{\rm ord}$ for
IT losses; we denote these three settings AT-O, IT-N, and IT-O, respectively.
Under these settings, the problem (25) is a convex optimization problem, and
hence it is relatively easy to seek the global minimizer (this is a reason why
we did not try the Ramp-AT and -IT losses). We solved the problem (25)
numerically using full-batch Adam optimization with the descending learning
rate $0.1^{1+3t/T}$ at $t$-th epoch during $T=10^{5}$ epochs.

##### Evaluation

We considered three popular OR tasks (Tasks-Z, -A, and -S) with the task loss
function $\ell=\ell_{\rm zo},\ell_{\rm ab},\ell_{\rm sq}$. We denote the
solution of (25) $\bar{a}_{1},\ldots,\bar{a}_{N},\bar{{\bm{b}}}$, omitting the
dependency on $p_{i,y}$’s, $\phi$, and ${\mathcal{B}}$. For the task loss
$\ell$ and learned 1DT values $\bar{a}_{1},\ldots,\bar{a}_{N}$, we calculated
the optimal threshold parameter vector
$\bar{{\bm{t}}}_{\ell}\in\operatorname{{arg\,min}}_{{\bm{t}}\in{\mathbb{R}}^{K-1}}\frac{1}{N}\sum_{i=1}^{N}\sum_{y=1}^{K}p_{i,y}\ell(h_{\rm
thr}(\bar{a}_{i};{\bm{t}}),y)$ following a way that modifies a dynamic-
programming-based algorithm (Lin and Li, 2006; Yamasaki, 2023) that is for a
sample-based situation. To evaluate the method’s label prediction
$\bar{f}_{\ell,i}=h_{\rm thr}(\bar{a}_{i};\bar{{\bm{t}}}_{\ell})$, we
calculated the approximation errors,
$\frac{1}{N}\sum_{i=1}^{N}\sum_{y=1}^{K}p_{i,y}\ell(\bar{f}_{\ell,i},y)$ with
$\ell=\ell_{\rm zo},\ell_{\rm ab},\ell_{\rm sq}$ (mean zero-one error (MZE),
mean absolute error (MAE), and mean squared error (MSE)) respectively for
Tasks-Z, -A, and -S. Under the task with the task loss $\ell$, the optimal
label prediction for $i$-th point ${\bm{x}}^{[i]}$ is
$\tilde{f}_{\ell,i}\in\operatorname{{arg\,min}}_{k\in[K]}\sum_{y=1}^{K}p_{i,y}\ell(k,y)$,
and the optimal error (Bayes error) is
$\frac{1}{N}\sum_{i=1}^{N}\sum_{y=1}^{K}p_{i,y}\ell(\tilde{f}_{\ell,i},y)$.
Note that, in the following, the evaluation for Task-S is reported as ‘root of
MSE’ (RMSE), not as MSE itself.

##### Results

We show results for all the combinations of 15 data distributions, 21
threshold methods, and 3 tasks and optimal values in Tables 2–6 in Appendix
A.1, and representative behaviors of learned 1DT values $\bar{a}_{i}$’s in
Figure 5 in Appendix A.1. We observed the following facts:

  * (l1)

Non-PL losses gave optimal approximation errors for H-$\Delta$, M-$\Delta$,
and A-$\Delta$. Not only squa-AT-O for Task-S, logi-IT-N and expo-IT-N for all
of these data distributions, and logi-IT-O and expo-IT-O for H-$\Delta$ and
M-$\Delta$ with the optimality guarantee (Theorems 4 and 5), but also logi-
AT-O, smhi-AT-O, and others performed well; see Tables 2–4. Figure 5 (m1)–(m3)
show plots of $(i,\bar{a}_{i})$’s only for logi-AT-O, -IT-N, and -IT-O, but
other non-PL losses gave similar results.

  * (l2)

All the losses gave sub-optimal approximation errors for many
O-$(\Delta_{1},\Delta_{2})$ and N-$\Delta$ with a large scale; see Tables 5
and 6 and Figure 5 (m4) and (m5). The deviation of the approximation error
from the optimal value was small for O-$(\Delta_{1},\Delta_{2})$ and large for
N-$\Delta$.

  * (l3)

PL losses (Hinge and Absolute-AT and -IT losses) gave sub-optimal
approximation errors for many data distributions with a large scale. Learned
1DT values $\bar{a}_{i}$’s with different CPD values were concentrated at a
few points, which resulted in the deterioration of the approximation error of
the resulting classifier in many cases. Figure 5 (m6)–(m8) show plots of
$(i,\bar{a}_{i})$’s only for hing-AT-O, -IT-N, and -IT-O, but plots for abso-
AT-O, -IT-N, and -IT-O similarly indicated the concentration of
$\bar{a}_{i}$’s.

###  4.2 Synthesis Data Experiment

Our ultimate interest is in the prediction performance of threshold methods.
We have proceeded with the study under the working hypothesis that the
approximation error dominates the prediction error when the number of training
data is sufficiently large. To test this working hypothesis and to show that
our discussion is suggestive in studying the ultimate interest, we performed a
performance comparison experiment with synthesis data, which were generated
from the data distributions we considered in Section 4.1.

##### Datasets

Let $N=100$, $K=10$, $n_{\rm to}=11000$,
$\tilde{a}^{[N,\Delta]}_{i}=(\tfrac{(i-1)K}{N-1}-1)\Delta$,
$\operatorname{{\mathrm{Uni}}}({\mathcal{S}})$ be the uniform distribution on
the set ${\mathcal{S}}$, and $\operatorname{{\mathrm{Cat}}}({\bm{p}})$ be the
categorical distribution for $K$ categories with event probabilities
$p_{1},\ldots,p_{K}$ of ${\bm{p}}=(p_{k})_{k\in[K]}\in\Delta_{K-1}$. We used
the following datasets: homoscedastic unimodal data H-$\Delta$ with
$\Delta=1/3,1,3$,

$\displaystyle
x_{i}\sim\operatorname{{\mathrm{Uni}}}\bigl{(}\\{\tilde{a}^{[N,\Delta]}_{j}\\}_{j\in[N]}\bigr{)}\text{~{}and~{}}y_{i}\sim\operatorname{{\mathrm{Cat}}}\bigl{(}(P_{\rm
acl}(k;x_{i},{\bm{b}}^{[\Delta]}))_{k\in[K]}\bigr{)}\text{~{}for~{}}i\in[n_{\rm
to}];$ (31)

mode-wise heteroscedastic unimodal data M-$\Delta$ with $\Delta=1/3,1,3$,

$\displaystyle
x_{i}\sim\operatorname{{\mathrm{Uni}}}\bigl{(}\\{\tilde{a}^{[N,\Delta]}_{j}\\}_{j\in[N]}\bigr{)}\text{~{}and~{}}y_{i}\sim\operatorname{{\mathrm{Cat}}}\bigl{(}(P_{\rm
acl}(k;x_{i},\acute{{\bm{b}}}^{[\Delta]}))_{k\in[K]}\bigr{)}\text{~{}for~{}}i\in[n_{\rm
to}];$ (32)

almost unimodal (partly non-unimodal) data A-$\Delta$ with $\Delta=1/3,1,3$,

$\displaystyle
x_{i}\sim\operatorname{{\mathrm{Uni}}}\bigl{(}\\{\tilde{a}^{[N,\Delta]}_{j}\\}_{j\in[N]}\bigr{)}\text{~{}and~{}}y_{i}\sim\operatorname{{\mathrm{Cat}}}\bigl{(}(P_{\rm
acl}(k;x_{i},\grave{{\bm{b}}}^{[\Delta]}))_{k\in[K]}\bigr{)}\text{~{}for~{}}i\in[n_{\rm
to}];$ (33)

overall heteroscedastic unimodal data O-($\Delta_{1},\Delta_{2}$) with
$(\Delta_{1},\Delta_{2})=(1/3,1),(1/3,3),(1,3)$,

$\displaystyle\begin{split}&x_{i}\sim\operatorname{{\mathrm{Uni}}}\bigl{(}\\{\tilde{a}^{[N/2,\Delta_{1}]}_{j}\\}_{j\in[N/2]}\bigr{)}\text{~{}and~{}}y_{i}\sim\operatorname{{\mathrm{Cat}}}\bigl{(}(P_{\rm
acl}(k;x_{i},{\bm{b}}^{[\Delta_{1}]}))_{k\in[K]}\bigr{)},\text{~{}or}\\\
&x_{i}\sim\operatorname{{\mathrm{Uni}}}\bigl{(}\\{\tilde{a}^{[N/2,\Delta_{2}]}_{j}+c\\}_{j\in[N/2]}\bigr{)}\text{~{}and~{}}y_{i}\sim\operatorname{{\mathrm{Cat}}}\bigl{(}(P_{\rm
acl}(k;x_{i},{\bm{b}}^{[\Delta_{2}]}+c\cdot\bm{1}_{K-1}))_{k\in[K]}\bigr{)}\\\
&\text{with equal probabilities for~{}}i\in[n_{\rm to}],\end{split}$ (34)

where we added $c=K\Delta_{1}+\Delta_{2}$ to prevent the overlap of the
domains of $x_{i}$’s for the two cases, which changes the CPD there from (29);
almost non-unimodal data N-$\Delta$ with $\Delta=1/3,1,3$,

$\displaystyle
x_{i}\sim\operatorname{{\mathrm{Uni}}}\bigl{(}\\{\tilde{a}^{[N,\Delta]}_{j}\\}_{j\in[N]}\bigr{)}\text{~{}and~{}}y_{i}\sim\operatorname{{\mathrm{Cat}}}\bigl{(}(P_{\rm
acl}(\pi(k);x_{i},{\bm{b}}^{[\Delta]}))_{k\in[K]}\bigr{)}\text{~{}for~{}}i\in[n_{\rm
to}].$ (35)

We used each of these datasets with randomly splitting them into the training
set of 900 data points, validation set of 100 data points, and test set of
10000 data points.

##### Methods

We considered threshold methods based on the two-step optimization (5). As
their surrogate loss function $\phi$ and class of the bias parameter vector
${\mathcal{B}}$, we tried the 21 settings same as those of the simulation
study in Section 4.1. As their class of the 1DT ${\mathcal{A}}$, we used a
4-layer neural network model, in which each hidden layer has 100 nodes and
every activation function is ReLU. For comparison, we also experimented with
multinomial logistic regression (MLR), which applies the negative-log-
likelihood as a surrogate loss and a similar 4-layer neural network model to
the above. We learned models by Adam optimization with the empirical surrogate
risk as the objective function, the mini-batch size 4, and the descending
learning rate $0.1^{2.5+t/T}$ at $t$-th epoch during $T=2000$ epochs.

##### Evaluation

During 2000 training epochs, we evaluated the empirical surrogate risk for the
validation set after every epoch. For a model at the point in time when the
validation error was minimized, we calculated the empirical task risks with
the task loss $\ell=\ell_{\rm zo},\ell_{\rm ab},\ell_{\rm sq}$ for the test
set. To judge the significance, we performed 20 independent trials and applied
the one-sided Wilcoxon rank-sum test with the $p$-value 0.05 (Wilcoxon test)
for 20 observations of each evaluation criterion.

##### Results

Tables 7–11 in Appendix A.2 show the mean and standard deviation (SD) of MZE,
MAE, and RMSE over 20 trials, and Figure 6 in Appendix A.2 shows
representative behaviors of learned 1DT values $\hat{a}({\bm{x}}^{[i]})$’s.
The experiment in this section has two differences from the simulation in
Section 4.1: In this experiment, we considered a finite-sample situation, and
there is no guarantee that we obtained the global minimizer of the empirical
surrogate risk (i.e., optimization error may exist, for example, because the
optimization may be trapped in a local minimizer). Even under such
differences, we could see the following observations similar to those observed
in the simulation in Section 4.1, as expected under our working hypothesis:

  * (n1)

Non-PL losses gave competitive or smaller test errors for unimodal data,
H-$\Delta$, M-$\Delta$, A-$\Delta$, and O-$(\Delta_{1},\Delta_{2})$, compared
with MLR; see Tables 7–10 and Figure 6 (o1)–(o4). We consider that, for
O-$(\Delta_{1},\Delta_{2})$, that the approximation error of these threshold
methods was slightly larger than that of MLR (see Table 5 again) but the
estimation error was smaller than that of MLR, and hence those threshold
methods performed well.

  * (n2)

Most threshold methods performed poorly than MLR for N-$\Delta$; see Table 11
and Figure 6 (o5).

  * (n3)

PL losses resulted in the concentration of learned 1DT values
$\hat{a}({\bm{x}}^{[i]})$’s especially for large-scale data (see Figure 6
(o6)–(o8)), and provided larger test errors than non-PL losses in many cases.

###  4.3 Real-World Data Experiment

Finally, we performed an OR experiment with real-world data, mainly to confirm
troubles owing to the use of an IT loss and ordered class of the bias
parameter vector and the use of a PL loss for practical OR tasks. We here
addressed an OR problem of estimating age from facial image by a discrete-
value prediction, with reference to the experiments in the previous OR studies
(Cao et al., 2020; Yamasaki, 2023). It would be supposed that the distribution
of age of people conditioned on their facial image tends to be unimodal.

##### Datasets

We used MORPH-2, CACD, and AFAD datasets (Ricanek and Tesafaye, 2006; Chen et
al., 2014; Niu et al., 2016). We purchased MORPH-2 (MORPH Album2) dataset at
https://ebill.uncw.edu/C20231_ustores/web/ and preprocessed it so that the
face spanned the whole image with the nose tip, which was located by facial
landmark detection (Sagonas et al., 2016), at the center. We used 55,013
instances with ages from 16 to 70 in this dataset. We downloaded CACD dataset
from https://bcsiriuschen.github.io/CARC/, and preprocessed this dataset
similarly to MORPH-2. Excluding images, in which no face or more than two
faces were detected in the preprocessing, we used 159,402 facial images in the
age range of 14–62 years. For AFAD dataset (https://github.com/afad-
dataset/tarball), because faces in its images were already centered, we took
no preprocessing. We used its 164,418 instances with ages 15–40. Because data
of MORPH-2 were collected in a laboratory setting and data of CACD and AFAD
were collected by web scraping, CACD and AFAD are inferred to have a larger
scale (this can also be inferred from that errors for CACD and AFAD were
larger as shown in Table 12 in Appendix A.3). For each dataset, we resized all
images to $128\times 128$ pixels of 3 RGB channels and randomly split the
dataset into 72 % training, 8 % validation, and 20 % test sets. The training
phase used images randomly cropped to $120\times 120$ pixels of 3 channels as
input to improve the stability of the model against the difference of facial
positions, and validation and test phases used images center-cropped to the
same size.

##### Methods

We tried 21 threshold methods and MLR as in the experiment in Section 4.2. We
implemented all the methods with ResNet34 (He et al., 2016). We trained the
network using Adam optimization with the mini-batch size 256 and the
descending learning rate $0.1^{2.5+t/T}$ at $t$-th epoch during $T=200$
epochs.

##### Evaluation

We took 5 trials, and considered the three OR tasks with the task loss
$\ell=\ell_{\rm zo},\ell_{\rm ab},\ell_{\rm sq}$ and used the test MZE, MAE,
and RMSE for the evaluation similarly to the experiment in Section 4.2.

##### Results

Table 12 in Appendix A.3 shows the mean and SD of MZE, MAE, and RMSE over the
5 trials, and Figure 7 in Appendix A.3 shows plots of
$(y_{i},\hat{a}({\bm{x}}_{i}))$’s. These results lead to the following
findings:

  * (p1)

Non-PL losses, especially, non-PL AT losses, gave the prediction performance
comparable to MLR. Plots of $(y_{i},\hat{a}({\bm{x}}_{i}))$’s for other non-PL
losses were similar to those for logi-AT-O, -IT-N, and -IT-O (Figure 7
(q1)–(q3)).

  * (p2)

Plots of $(y_{i},\hat{a}({\bm{x}}_{i}))$’s for abso-AT-O, -IT-N, and -IT-O
were similar to those for hing-AT-O, -IT-N, and -IT-O (Figure 7 (q4)–(q6)).
Although there was a little blur probably due to the optimization error, 1DT
values $\hat{a}({\bm{x}}_{i})$’s learned with PL losses were concentrated at a
few points. Partly because of such concentration phenomenon, PL losses gave
worse prediction performance than non-PL losses in many cases (especially for
CACD and AFAD that are inferred to have a larger scale).

  * (p3)

Table 13 shows the mean and SD of the number of unique elements of learned
bias parameter vector, and indicates that the setting IT-O resulted in much
heavy overlap of the learned bias parameter vector than the setting AT-O. This
phenomenon might contribute to low performance of the threshold methods with
the setting IT-O.

##  5 Conclusion and Future Works

We studied the influence of the underlying data distribution and of the
learning procedure of the 1DT on the approximation error of threshold methods,
under the expectation that it would lead to understand the prediction
performance of those methods learned with a sufficiently large-size sample.
First, Theorems 2 and 5 clarify data distributions for which the threshold
methods based on the learning procedure with the Logistic and Exponential-AT
and -IT losses can yield the minimum approximation error. On the ground of
these results and Theorems 3 and 6, we conjecture that threshold methods using
the Logistic and Exponential-AT and -IT losses or similarly-shaped losses will
perform well for homoscedastic unimodal data and mode-wise heteroscedastic
unimodal data and may perform poorly for overall heteroscedastic unimodal data
and almost non-unimodal data. Second, according to Theorems 4 and 7, which
give a closed-form expression of the surrogate risk minimizer with the
Squared-AT and -IT losses respectively, we also conjecture that threshold
methods using the Squared-AT and -IT losses or similarly-shaped losses will
perform well for unimodal data with a small scale. Third, the learning
procedure based on an IT loss and ordered class of the bias parameter vector
can output overlapped learned bias parameter vector: In Section 3.2.3, we
demonstrated that such overlap may deteriorate the ability of the threshold
method to reflect variation in the underlying data distribution. Fourth, we
showed in Section 3.3 that, under the learning procedure based on a PL loss,
learned 1DT values are concentrated at a few points. It is considered that
these troubles can act as negative factors that degrade the prediction
performance. We confirmed these results and conjectures as (l1)–(l3),
(n1)–(n3), and (p1)–(p3) experimentally. Consequently, these results advance
the previous theoretical work (Pedregosa et al., 2017, Section 4), which
suggests the absence of Fisher consistency for many threshold methods, and the
experimental comparisons (Rennie and Srebro, 2005; Gutierrez et al., 2015) of
threshold methods using various surrogate loss functions.

The results of this study may be useful in developing novel learning
procedures for threshold methods. On the other hand, these results also
indicate that a classifier of several threshold methods based on the strict
surrogate risk minimization may not be good. Devised design of the
optimization procedure, including the setting of initial parameters and
appropriate stopping, may improve the practical classification performance of
the classifier. Also, it would be still important to analyze the estimation
error of the classifier based on the two-step optimization (5). These topics
are future works.

## References

  * Agresti [2010] A. Agresti.  _Analysis of Ordinal Categorical Data_ , volume 656.  John Wiley & Sons, 2nd edition, 2010.
  * Bartlett et al. [2006] P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe.  Convexity, classification, and risk bounds.  _Journal of the American Statistical Association_ , 101(473):138–156, 2006.
  * Beckham and Pal [2017] C. Beckham and C. Pal.  Unimodal probability distributions for deep ordinal classification.  In _Proceedings of the International Conference on Machine Learning_ , pages 411–419, 2017.
  * Bürkner and Vuorre [2019] P.-C. Bürkner and M. Vuorre.  Ordinal regression models in psychology: A tutorial.  _Advances in Methods and Practices in Psychological Science_ , 2(1):77–101, 2019.
  * Cao et al. [2020] W. Cao, V. Mirjalili, and S. Raschka.  Rank consistent ordinal regression for neural networks with application to age estimation.  _Pattern Recognition Letters_ , 140:325–331, 2020.
  * Chen et al. [2014] B.-C. Chen, C.-S. Chen, and W. H. Hsu.  Cross-age reference coding for age-invariant face recognition and retrieval.  In _Proceedings of the European Conference on Computer Vision_ , pages 768–783, 2014.
  * Chu and Ghahramani [2005] W. Chu and Z. Ghahramani.  Gaussian processes for ordinal regression.  _Journal of Machine Learning Research_ , 6(Jul):1019–1041, 2005.
  * Chu and Keerthi [2005] W. Chu and S. S. Keerthi.  New approaches to support vector ordinal regression.  In _Proceedings of the International Conference on Machine Learning_ , pages 145–152, 2005.
  * Chu and Keerthi [2007] W. Chu and S. S. Keerthi.  Support vector ordinal regression.  _Neural Computation_ , 19(3):792–815, 2007.
  * Cohen [1960] J. Cohen.  A coefficient of agreement for nominal scales.  _Educational and Psychological Measurement_ , 20(1):37–46, 1960.
  * Cohen [1968] J. Cohen.  Weighted kappa: nominal scale agreement provision for scaled disagreement or partial credit.  _Psychological Bulletin_ , 70(4):213, 1968.
  * Cortes and Vapnik [1995] C. Cortes and V. Vapnik.  Support-vector networks.  _Machine Learning_ , 20:273–297, 1995.
  * Crammer and Singer [2002] K. Crammer and Y. Singer.  Pranking with ranking.  In _Advances in Neural Information Processing Systems_ , pages 641–647, 2002.
  * da Costa et al. [2008] J. F. P. da Costa, H. Alonso, and J. S. Cardoso.  The unimodal model for the classification of ordinal data.  _Neural Networks_ , 21(1):78–91, 2008.
  * Franses and Paap [2001] P. H. Franses and R. Paap.  _Quantitative Models in Marketing Research_.  Cambridge University Press, 2001.
  * Gutierrez et al. [2015] P. A. Gutierrez, M. Perez-Ortiz, J. Sanchez-Monedero, F. Fernandez-Navarro, and C. Hervas-Martinez.  Ordinal regression methods: survey and experimental study.  _IEEE Transactions on Knowledge and Data Engineering_ , 28(1):127–146, 2015.
  * He et al. [2016] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 770–778, 2016.
  * Li and Lin [2007] L. Li and H.-T. Lin.  Ordinal regression by extended binary classification.  In _Advances in Neural Information Processing Systems_ , pages 865–872, 2007.
  * Lin and Li [2006] H.-T. Lin and L. Li.  Large-margin thresholded ensembles for ordinal regression: Theory and practice.  In _Algorithmic Learning Theory_ , pages 319–333, 2006.
  * Lin and Li [2012] H.-T. Lin and L. Li.  Reduction from cost-sensitive ordinal ranking to weighted binary classification.  _Neural Computation_ , 24(5):1329–1367, 2012\.
  * Liu [2011] T.-Y. Liu.  _Learning to Rank for Information Retrieval_.  Springer Science & Business Media, 2011.
  * Liu [2007] Y. Liu.  Fisher consistency of multicategory support vector machines.  In _Proceedings of the International Conference on Artificial Intelligence and Statistics_ , pages 291–298, 2007.
  * McCullagh [1980] P. McCullagh.  Regression models for ordinal data.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 42(2):109–127, 1980.
  * Niu et al. [2016] Z. Niu, M. Zhou, L. Wang, X. Gao, and G. Hua.  Ordinal regression with multiple output cnn for age estimation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4920–4928, 2016.
  * Pedregosa et al. [2017] F. Pedregosa, F. Bach, and A. Gramfort.  On the consistency of ordinal regression methods.  _Journal of Machine Learning Research_ , 18(Jan):1769–1803, 2017.
  * Pfannschmidt et al. [2020] L. Pfannschmidt, J. Jakob, F. Hinder, M. Biehl, P. Tino, and B. Hammer.  Feature relevance determination for ordinal regression in the context of feature redundancies and privileged information.  _Neurocomputing_ , 416:266–279, 2020.
  * Pires et al. [2013] B. A. Pires, C. Szepesvari, and M. Ghavamzadeh.  Cost-sensitive multiclass classification risk bounds.  In _Proceedings of the International Conference on Machine Learning_ , pages 1391–1399, 2013.
  * Rennie and Srebro [2005] J. D. Rennie and N. Srebro.  Loss functions for preference levels: Regression with discrete ordered labels.  In _Proceedings of the IJCAI Multidisciplinary Workshop on Advances in Preference Handling_ , pages 180–186, 2005.
  * Ricanek and Tesafaye [2006] K. Ricanek and T. Tesafaye.  Morph: A longitudinal image database of normal adult age-progression.  In _Proceedings of the IEEE International Conference on Automatic Face and Gesture Recognition_ , pages 341–345, 2006.
  * Sagonas et al. [2016] C. Sagonas, E. Antonakos, G. Tzimiropoulos, S. Zafeiriou, and M. Pantic.  300 faces in-the-wild challenge: Database and results.  _Image and Vision Computing_ , 47:3–18, 2016.
  * Shalev-Shwartz and Ben-David [2014] S. Shalev-Shwartz and S. Ben-David.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University Press, 2014.
  * Shashua and Levin [2002] A. Shashua and A. Levin.  Taxonomy of large margin principle algorithms for ordinal regression problems.  In _Advances in Neural Information Processing Systems_ , pages 937–944, 2002.
  * Shashua and Levin [2003] A. Shashua and A. Levin.  Ranking with large margin principle: Two approaches.  In _Advances in Neural Information Processing Systems_ , pages 961–968, 2003.
  * Tewari and Bartlett [2007] A. Tewari and P. L. Bartlett.  On the consistency of multiclass classification methods.  _Journal of Machine Learning Research_ , 8(May):1007–1025, 2007.
  * Yamasaki [2022] R. Yamasaki.  Unimodal likelihood models for ordinal data.  _Transactions on Machine Learning Research_ , 2022.  URL https://openreview.net/forum?id=1l0sClLiPc.
  * Yamasaki [2023] R. Yamasaki.  Optimal threshold labeling for ordinal regression methods.  _Transactions on Machine Learning Research_ , 2023.  URL https://openreview.net/forum?id=mHSAy1n65Z.
  * Yamasaki and Tanaka [2024] R. Yamasaki and T. Tanaka.  Parallel algorithm for optimal threshold labeling of ordinal regression methods.  _arXiv preprint arXiv:2405.12756v1_ , 2024.
  * Yu et al. [2006] S. Yu, K. Yu, V. Tresp, and H.-P. Kriegel.  Collaborative ordinal regression.  In _Proceedings of the International Conference on Machine Learning_ , pages 1089–1096, 2006.

##  Appendix A Tables and Figures about Experimental Results

###  A.1 Results for Simulation Study in Section 4.1

Tables 2–6 show the simulated approximation errors of 21 threshold methods and
optimal values (Bayes errors) for the simulation study in Section 4.1. Results
for a threshold method with the error equal to the optimal value are omitted
or marked as ‘-’.

Table 2: Results for the simulation in Section 4.1 with the data distributions
$\text{H-}1/3$, $\text{H-}1$, and $\text{H-}3$.

|  | H-1/3 | H-1 | H-3
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
optimal | .726 | 1.144 | 1.492 | .571 | .686 | .959 | .349 | .356 | .609
AT-O | hing | .727 | 1.150 | 1.502 | .575 | .690 | .963 | - | - | -
abso | .746 | 1.233 | 1.585 | .657 | .878 | 1.183 | .592 | .775 | 1.052
IT-N | hing | .728 | 1.150 | 1.502 | .577 | .695 | .972 | - | - | -
abso | .731 | 1.164 | 1.520 | .586 | .725 | 1.010 | .378 | .390 | .644
IT-O | hing | .727 | 1.148 | 1.497 | .575 | .692 | .966 | - | - | -
abso | .730 | 1.161 | 1.517 | .578 | .700 | .976 | .366 | .376 | .630

Table 3: Results for the simulation in Section 4.1 with the data distributions
$\text{M-}1/3$, $\text{M-}1$, and $\text{M-}3$.

|  | M-1/3 | M-1 | M-3
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
optimal | .716 | 1.122 | 1.452 | .529 | .660 | .952 | .296 | .318 | .597
AT-O | hing | .717 | 1.126 | 1.457 | .530 | .665 | .957 | - | - | -
abso | .786 | 1.503 | 1.887 | .619 | .957 | 1.335 | .484 | .666 | 1.042
IT-N | hing | .721 | 1.143 | 1.479 | .531 | .671 | .966 | - | - | .598
abso | .730 | 1.215 | 1.585 | .536 | .684 | .974 | .303 | .330 | .619
IT-O | hing | .720 | 1.141 | 1.478 | .531 | .666 | .961 | - | - | -
abso | .722 | 1.172 | 1.527 | .541 | .694 | .983 | .299 | .326 | .616

Table 4: Results for the simulation in Section 4.1 with the data distributions
$\text{A-}1/3$, $\text{A-}1$, and $\text{A-}3$.

|  | A-1/3 | A-1 | A-3
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
optimal | .720 | 1.141 | 1.493 | .553 | .681 | .960 | .309 | .335 | .606
AT-O | hing | .722 | 1.150 | 1.502 | .554 | .683 | .963 | - | - | -
abso | .750 | 1.256 | 1.626 | .662 | .918 | 1.225 | .528 | .727 | 1.042
IT-N | hing | .728 | 1.172 | 1.530 | .560 | .707 | .991 | .313 | .343 | .612
abso | .728 | 1.174 | 1.537 | .574 | .737 | 1.043 | .357 | .409 | .688
IT-O | hing | .722 | 1.149 | 1.503 | .557 | .691 | .977 | - | - | .607
abso | .728 | 1.180 | 1.548 | .562 | .710 | .995 | .332 | .360 | .635

Table 5: Results for the simulation in Section 4.1 with the data distributions
$\text{O-}(1/3,1)$, $\text{O-}(1/3,3)$, and $\text{O-}(1/3,3)$.

|  | O-(1/3,1) | O-(1/3,3) | O-(1,3)
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
optimal | .646 | .911 | 1.250 | .535 | .746 | 1.135 | .457 | .517 | .800
AT-O | logi | .650 | - | - | .543 | .748 | - | .458 | .518 | -
hing | .652 | .918 | 1.261 | .543 | .748 | 1.137 | - | - | -
smhi | .650 | - | - | .543 | - | - | .458 | - | -
sqhi | .650 | - | - | .543 | .748 | - | .458 | .518 | -
expo | .654 | .913 | - | .544 | .748 | 1.136 | .459 | .518 | .801
abso | .694 | 1.053 | 1.395 | .635 | .954 | 1.356 | .587 | .780 | 1.104
squa | .650 | - | - | .543 | .748 | - | .458 | .518 | -
IT-N | logi | .649 | - | - | .540 | - | 1.136 | .458 | - | -
hing | .650 | .915 | 1.256 | .546 | .755 | 1.146 | .458 | - | -
smhi | .648 | - | 1.251 | .538 | - | - | .458 | - | -
sqhi | .649 | - | - | .540 | - | - | .458 | - | -
expo | .649 | - | - | .542 | - | - | .458 | .518 | -
abso | .656 | .932 | 1.273 | .578 | .809 | 1.182 | .468 | .536 | .820
squa | .649 | - | - | .542 | - | - | .458 | - | -
IT-O | logi | .649 | - | - | .540 | - | 1.136 | .458 | - | -
hing | .648 | .912 | 1.252 | .552 | .762 | 1.144 | - | - | -
smhi | .648 | - | 1.251 | .538 | - | - | .458 | - | -
sqhi | .649 | - | - | .540 | - | - | .458 | - | -
expo | .649 | - | - | .542 | - | - | .458 | .518 | -
abso | .651 | .921 | 1.261 | .555 | .770 | 1.158 | .466 | .531 | .815
squa | .649 | - | - | .542 | - | - | .458 | - | -

Table 6: Results for the simulation in Section 4.1 with the data distributions
$\text{N-}1/3$, $\text{N-}1$, and $\text{N-}3$.

|  | N-1/3 | N-1 | N-3
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
optimal | .726 | 1.887 | 2.372 | .571 | 1.242 | 1.666 | .349 | .672 | 1.068
AT-O | logi | .788 | 1.905 | - | .687 | 1.280 | - | .517 | .727 | -
hing | .778 | 1.924 | 2.386 | .661 | 1.272 | 1.672 | .487 | .721 | 1.077
smhi | .787 | 1.903 | - | .682 | 1.276 | - | .509 | .718 | -
sqhi | .788 | 1.905 | - | .687 | 1.280 | - | .522 | .727 | -
expo | .788 | 1.905 | - | .687 | 1.279 | - | .531 | .735 | -
abso | .822 | 2.217 | 2.652 | .687 | 1.347 | 1.734 | .626 | 1.072 | 1.415
squa | .788 | 1.905 | - | .687 | 1.280 | - | .517 | .727 | -
IT-N | logi | .768 | 1.928 | 2.396 | .666 | 1.287 | 1.669 | .508 | .726 | -
hing | .770 | 2.076 | 2.524 | .665 | 1.364 | 1.793 | .446 | .797 | 1.177
smhi | .757 | 1.948 | 2.402 | .655 | 1.284 | 1.671 | .471 | .711 | 1.070
sqhi | .768 | 1.930 | 2.396 | .666 | 1.287 | 1.669 | .514 | .730 | -
expo | .769 | 1.928 | 2.395 | .668 | 1.287 | 1.668 | .509 | .731 | 1.069
abso | .770 | 2.038 | 2.478 | .668 | 1.449 | 1.863 | .484 | .868 | 1.211
squa | .768 | 1.930 | 2.396 | .666 | 1.287 | 1.669 | .515 | .732 | -
IT-O | logi | .769 | 1.928 | 2.396 | .666 | 1.287 | 1.669 | .508 | .726 | -
hing | .769 | 2.035 | 2.479 | .646 | 1.334 | 1.735 | .496 | .774 | 1.128
smhi | .764 | 1.928 | 2.394 | .655 | 1.284 | 1.671 | .471 | .711 | 1.070
sqhi | .769 | 1.928 | 2.396 | .666 | 1.287 | 1.669 | .514 | .730 | -
expo | .769 | 1.928 | 2.395 | .668 | 1.287 | 1.668 | .509 | .731 | 1.069
abso | .776 | 2.054 | 2.510 | .678 | 1.391 | 1.797 | .510 | .849 | 1.166
squa | .769 | 1.928 | 2.396 | .666 | 1.287 | 1.669 | .515 | .732 | -

Figure 5 shows the learned 1DT values $\bar{a}_{i}$, method’s label prediction
$\bar{f}_{\ell,i}$, and optimal label prediction $\tilde{f}_{\ell,i}$ for
several instances of the simulation in Section 4.1. This indicates
representative behaviors of threshold methods based on a learning procedure
with non-PL and PL losses.

| (m1) H-1, logi | (m2) M-1, logi | (m3) A-1, logi | (m4) O-(1/3,3), logi
---|---|---|---|---
AT-O |  |  |  |
IT-N |  |  |  |
IT-O |  |  |  |
| (m5) N-1, logi | (m6) H-1/3, hing | (m7) H-1, hing | (m8) H-3, hing
AT-O |  |  |  |
IT-N |  |  |  |
IT-O |  |  |  |

Figure 5: Learned 1DT value $\bar{a}_{i}$ and optimal label prediction
$\tilde{f}_{\ell,i}$ (color of point) versus $i$, and method’s label
prediction (lightened background color), which represents $\bar{f}_{\ell,i}$,
for the simulation in Section 4.1 with Task-Z. For example, 3 plates of (m1)
show 3 results for H-1 with logi-AT-O, -IT-N, and -IT-O from top to bottom.

###  A.2 Results for Synthesis Data Experiment in Section 4.2

Tables 7–11 show the mean and SD of the test prediction errors (as
‘$\text{mean}_{\text{SD}}$’) of MLR and 21 threshold methods for the
experiment in Section 4.2. For each combination of the data distribution and
error, the best results (with the smallest mean of errors) among the results
for threshold methods are shown in red, the result for MLR is shown in red if
it is significantly better than the best results, and results significantly
worse than the best results in blue. We see these tables graphically,
concentrating especially on two points: whether the results for each threshold
method are in blue (i.e., trouble inherent to the learning procedure), and
whether the results for MLR are colored (i.e., comparison between threshold
methods and standard classification method).

Table 7: Results for the experiment in Section 4.2 with the data
$\text{H-}1/3$, $\text{H-}1$, and $\text{H-}3$.

|  | H-1/3 | H-1 | H-3
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
MLR | $.752_{.033}$ | $1.224_{.273}$ | $1.574_{.284}$ | $.589_{.007}$ | $.708_{.013}$ | $.977_{.014}$ | $.365_{.009}$ | $.371_{.008}$ | $.621_{.008}$
AT-O | logi | $.740_{.008}$ | $1.166_{.011}$ | $1.513_{.011}$ | $.587_{.007}$ | $.706_{.010}$ | $.976_{.012}$ | $.361_{.008}$ | $.369_{.009}$ | $.620_{.007}$
hing | $.741_{.009}$ | $1.173_{.022}$ | $1.519_{.016}$ | $.589_{.007}$ | $.708_{.012}$ | $.980_{.014}$ | $.360_{.007}$ | $.369_{.008}$ | $.620_{.007}$
smhi | $.739_{.007}$ | $1.168_{.012}$ | $1.511_{.012}$ | $.587_{.008}$ | $.705_{.011}$ | $.977_{.013}$ | $.361_{.008}$ | $.370_{.009}$ | $.620_{.007}$
sqhi | $.739_{.007}$ | $1.166_{.011}$ | $1.511_{.011}$ | $.587_{.008}$ | $.706_{.011}$ | $.976_{.012}$ | $.361_{.007}$ | $.369_{.009}$ | $.620_{.008}$
expo | $.740_{.007}$ | $1.170_{.013}$ | $1.514_{.014}$ | $.587_{.007}$ | $.706_{.009}$ | $.976_{.012}$ | $.362_{.008}$ | $.371_{.009}$ | $.621_{.007}$
abso | $.746_{.014}$ | $1.195_{.058}$ | $1.545_{.069}$ | $.620_{.049}$ | $.795_{.133}$ | $1.075_{.160}$ | $.455_{.099}$ | $.541_{.197}$ | $.818_{.234}$
squa | $.739_{.007}$ | $1.164_{.011}$ | $1.512_{.010}$ | $.587_{.008}$ | $.705_{.011}$ | $.976_{.013}$ | $.361_{.008}$ | $.370_{.009}$ | $.621_{.007}$
IT-N | logi | $.740_{.009}$ | $1.168_{.012}$ | $1.513_{.012}$ | $.587_{.007}$ | $.704_{.010}$ | $.976_{.013}$ | $.362_{.008}$ | $.372_{.009}$ | $.623_{.008}$
hing | $.743_{.009}$ | $1.176_{.025}$ | $1.524_{.034}$ | $.587_{.008}$ | $.706_{.014}$ | $.977_{.014}$ | $.362_{.008}$ | $.371_{.010}$ | $.623_{.009}$
smhi | $.740_{.007}$ | $1.167_{.012}$ | $1.512_{.012}$ | $.587_{.007}$ | $.705_{.011}$ | $.976_{.013}$ | $.362_{.007}$ | $.371_{.009}$ | $.621_{.007}$
sqhi | $.740_{.007}$ | $1.166_{.011}$ | $1.511_{.011}$ | $.586_{.008}$ | $.705_{.012}$ | $.976_{.013}$ | $.361_{.008}$ | $.370_{.009}$ | $.621_{.008}$
expo | $.741_{.008}$ | $1.169_{.011}$ | $1.513_{.012}$ | $.588_{.007}$ | $.708_{.011}$ | $.980_{.012}$ | $.363_{.009}$ | $.371_{.011}$ | $.622_{.009}$
abso | $.742_{.009}$ | $1.179_{.022}$ | $1.526_{.020}$ | $.590_{.008}$ | $.715_{.016}$ | $.984_{.020}$ | $.364_{.008}$ | $.373_{.009}$ | $.625_{.008}$
squa | $.739_{.008}$ | $1.165_{.011}$ | $1.512_{.012}$ | $.586_{.008}$ | $.704_{.009}$ | $.975_{.012}$ | $.361_{.008}$ | $.370_{.009}$ | $.620_{.007}$
IT-O | logi | $.738_{.007}$ | $1.165_{.011}$ | $1.511_{.010}$ | $.586_{.007}$ | $.705_{.010}$ | $.974_{.012}$ | $.361_{.008}$ | $.370_{.009}$ | $.621_{.007}$
hing | $.742_{.010}$ | $1.172_{.017}$ | $1.521_{.027}$ | $.588_{.008}$ | $.709_{.016}$ | $.981_{.016}$ | $.360_{.007}$ | $.369_{.008}$ | $.620_{.007}$
smhi | $.739_{.008}$ | $1.165_{.011}$ | $1.511_{.011}$ | $.587_{.007}$ | $.706_{.011}$ | $.976_{.014}$ | $.361_{.007}$ | $.370_{.009}$ | $.621_{.008}$
sqhi | $.739_{.007}$ | $1.164_{.011}$ | $1.510_{.011}$ | $.586_{.008}$ | $.705_{.011}$ | $.976_{.013}$ | $.360_{.007}$ | $.369_{.009}$ | $.620_{.007}$
expo | $.740_{.007}$ | $1.167_{.013}$ | $1.512_{.011}$ | $.587_{.008}$ | $.705_{.010}$ | $.976_{.013}$ | $.362_{.008}$ | $.370_{.009}$ | $.621_{.008}$
abso | $.741_{.008}$ | $1.177_{.032}$ | $1.528_{.040}$ | $.589_{.010}$ | $.710_{.017}$ | $.981_{.018}$ | $.364_{.008}$ | $.374_{.011}$ | $.626_{.011}$
squa | $.740_{.008}$ | $1.165_{.012}$ | $1.510_{.011}$ | $.586_{.007}$ | $.705_{.010}$ | $.975_{.012}$ | $.361_{.008}$ | $.370_{.009}$ | $.620_{.007}$

Table 8: Results for the experiment in Section 4.2 with the data
$\text{M-}1/3$, $\text{M-}1$, and $\text{M-}3$.

|  | M-1/3 | M-1 | M-3
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
MLR | $.730_{.008}$ | $1.144_{.016}$ | $1.470_{.016}$ | $.544_{.008}$ | $.683_{.013}$ | $.971_{.012}$ | $.315_{.011}$ | $.332_{.012}$ | $.612_{.013}$
AT-O | logi | $.729_{.007}$ | $1.145_{.011}$ | $1.466_{.009}$ | $.543_{.009}$ | $.679_{.010}$ | $.971_{.014}$ | $.310_{.008}$ | $.332_{.011}$ | $.614_{.016}$
hing | $.730_{.007}$ | $1.152_{.012}$ | $1.474_{.013}$ | $.544_{.009}$ | $.682_{.011}$ | $.975_{.017}$ | $.310_{.008}$ | $.332_{.011}$ | $.612_{.016}$
smhi | $.728_{.006}$ | $1.144_{.013}$ | $1.464_{.011}$ | $.542_{.008}$ | $.678_{.010}$ | $.970_{.011}$ | $.310_{.008}$ | $.331_{.010}$ | $.612_{.014}$
sqhi | $.727_{.006}$ | $1.145_{.013}$ | $1.465_{.010}$ | $.542_{.009}$ | $.680_{.009}$ | $.970_{.013}$ | $.310_{.008}$ | $.332_{.010}$ | $.612_{.015}$
expo | $.729_{.006}$ | $1.146_{.014}$ | $1.466_{.011}$ | $.543_{.008}$ | $.679_{.010}$ | $.971_{.013}$ | $.309_{.008}$ | $.332_{.010}$ | $.614_{.015}$
abso | $.730_{.008}$ | $1.152_{.029}$ | $1.480_{.037}$ | $.551_{.020}$ | $.696_{.027}$ | $.984_{.029}$ | $.387_{.147}$ | $.555_{.435}$ | $.897_{.555}$
squa | $.728_{.006}$ | $1.146_{.013}$ | $1.466_{.012}$ | $.542_{.009}$ | $.679_{.010}$ | $.971_{.012}$ | $.309_{.008}$ | $.332_{.011}$ | $.613_{.015}$
IT-N | logi | $.728_{.007}$ | $1.151_{.013}$ | $1.469_{.015}$ | $.542_{.009}$ | $.679_{.009}$ | $.970_{.012}$ | $.311_{.009}$ | $.333_{.011}$ | $.616_{.015}$
hing | $.729_{.007}$ | $1.155_{.014}$ | $1.479_{.023}$ | $.544_{.009}$ | $.687_{.015}$ | $.982_{.027}$ | $.312_{.008}$ | $.337_{.009}$ | $.623_{.015}$
smhi | $.729_{.007}$ | $1.146_{.014}$ | $1.469_{.014}$ | $.543_{.009}$ | $.679_{.009}$ | $.971_{.013}$ | $.310_{.008}$ | $.332_{.010}$ | $.612_{.014}$
sqhi | $.728_{.007}$ | $1.146_{.012}$ | $1.467_{.012}$ | $.542_{.008}$ | $.680_{.010}$ | $.972_{.013}$ | $.311_{.009}$ | $.332_{.010}$ | $.613_{.015}$
expo | $.729_{.007}$ | $1.150_{.015}$ | $1.470_{.014}$ | $.544_{.008}$ | $.686_{.009}$ | $.976_{.014}$ | $.334_{.019}$ | $.381_{.060}$ | $.684_{.085}$
abso | $.732_{.008}$ | $1.165_{.035}$ | $1.489_{.049}$ | $.546_{.011}$ | $.693_{.020}$ | $.983_{.025}$ | $.314_{.008}$ | $.341_{.011}$ | $.625_{.015}$
squa | $.728_{.006}$ | $1.146_{.012}$ | $1.467_{.011}$ | $.542_{.009}$ | $.680_{.009}$ | $.971_{.013}$ | $.310_{.008}$ | $.332_{.011}$ | $.613_{.015}$
IT-O | logi | $.728_{.006}$ | $1.146_{.012}$ | $1.464_{.010}$ | $.542_{.009}$ | $.678_{.009}$ | $.969_{.012}$ | $.309_{.008}$ | $.332_{.011}$ | $.613_{.015}$
hing | $.730_{.007}$ | $1.160_{.021}$ | $1.483_{.029}$ | $.546_{.009}$ | $.697_{.025}$ | $.993_{.038}$ | $.310_{.008}$ | $.332_{.011}$ | $.614_{.016}$
smhi | $.727_{.006}$ | $1.146_{.014}$ | $1.466_{.008}$ | $.542_{.009}$ | $.679_{.009}$ | $.970_{.013}$ | $.310_{.008}$ | $.332_{.010}$ | $.613_{.014}$
sqhi | $.728_{.007}$ | $1.146_{.013}$ | $1.465_{.009}$ | $.542_{.009}$ | $.679_{.009}$ | $.971_{.013}$ | $.309_{.008}$ | $.331_{.010}$ | $.613_{.015}$
expo | $.728_{.007}$ | $1.146_{.013}$ | $1.465_{.015}$ | $.543_{.008}$ | $.678_{.009}$ | $.970_{.012}$ | $.310_{.009}$ | $.333_{.011}$ | $.614_{.015}$
abso | $.731_{.009}$ | $1.156_{.015}$ | $1.484_{.019}$ | $.546_{.012}$ | $.696_{.029}$ | $.985_{.039}$ | $.317_{.011}$ | $.346_{.017}$ | $.635_{.026}$
squa | $.728_{.007}$ | $1.147_{.014}$ | $1.465_{.013}$ | $.542_{.009}$ | $.679_{.009}$ | $.971_{.013}$ | $.310_{.008}$ | $.332_{.010}$ | $.614_{.014}$

Table 9: Results for the experiment in Section 4.2 with the data
$\text{A-}1/3$, $\text{A-}1$, and $\text{A-}3$.

|  | A-1/3 | A-1 | A-3
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
MLR | $.738_{.010}$ | $1.162_{.018}$ | $1.511_{.019}$ | $.572_{.009}$ | $.702_{.012}$ | $.976_{.013}$ | $.321_{.008}$ | $.347_{.011}$ | $.619_{.012}$
AT-O | logi | $.736_{.008}$ | $1.164_{.012}$ | $1.513_{.012}$ | $.570_{.009}$ | $.701_{.011}$ | $.976_{.011}$ | $.320_{.006}$ | $.347_{.009}$ | $.617_{.008}$
hing | $.738_{.008}$ | $1.170_{.018}$ | $1.520_{.015}$ | $.571_{.009}$ | $.704_{.012}$ | $.978_{.012}$ | $.320_{.005}$ | $.348_{.008}$ | $.617_{.006}$
smhi | $.736_{.007}$ | $1.163_{.012}$ | $1.512_{.014}$ | $.570_{.008}$ | $.701_{.009}$ | $.975_{.011}$ | $.321_{.007}$ | $.347_{.008}$ | $.617_{.007}$
sqhi | $.736_{.007}$ | $1.162_{.012}$ | $1.512_{.013}$ | $.570_{.008}$ | $.699_{.010}$ | $.975_{.011}$ | $.320_{.006}$ | $.347_{.008}$ | $.616_{.007}$
expo | $.737_{.007}$ | $1.165_{.012}$ | $1.515_{.014}$ | $.570_{.008}$ | $.700_{.010}$ | $.975_{.011}$ | $.322_{.006}$ | $.348_{.009}$ | $.618_{.008}$
abso | $.746_{.015}$ | $1.203_{.071}$ | $1.559_{.087}$ | $.625_{.048}$ | $.824_{.115}$ | $1.114_{.142}$ | $.500_{.089}$ | $.679_{.188}$ | $.985_{.200}$
squa | $.736_{.007}$ | $1.162_{.013}$ | $1.514_{.012}$ | $.570_{.008}$ | $.699_{.009}$ | $.975_{.011}$ | $.320_{.007}$ | $.348_{.009}$ | $.618_{.007}$
IT-N | logi | $.737_{.008}$ | $1.163_{.012}$ | $1.513_{.014}$ | $.570_{.009}$ | $.700_{.009}$ | $.975_{.011}$ | $.321_{.006}$ | $.349_{.008}$ | $.618_{.007}$
hing | $.742_{.011}$ | $1.183_{.042}$ | $1.542_{.050}$ | $.571_{.008}$ | $.704_{.013}$ | $.979_{.014}$ | $.322_{.007}$ | $.349_{.008}$ | $.619_{.009}$
smhi | $.737_{.007}$ | $1.165_{.013}$ | $1.514_{.016}$ | $.570_{.008}$ | $.701_{.010}$ | $.975_{.011}$ | $.321_{.006}$ | $.347_{.008}$ | $.617_{.007}$
sqhi | $.737_{.007}$ | $1.163_{.012}$ | $1.514_{.016}$ | $.570_{.008}$ | $.700_{.009}$ | $.976_{.012}$ | $.319_{.006}$ | $.346_{.008}$ | $.616_{.007}$
expo | $.737_{.007}$ | $1.165_{.012}$ | $1.513_{.013}$ | $.572_{.008}$ | $.702_{.010}$ | $.978_{.012}$ | $.348_{.027}$ | $.405_{.060}$ | $.668_{.057}$
abso | $.741_{.008}$ | $1.179_{.042}$ | $1.535_{.051}$ | $.574_{.010}$ | $.712_{.016}$ | $.980_{.014}$ | $.333_{.021}$ | $.367_{.044}$ | $.638_{.043}$
squa | $.736_{.007}$ | $1.163_{.012}$ | $1.512_{.013}$ | $.569_{.008}$ | $.700_{.010}$ | $.976_{.011}$ | $.320_{.006}$ | $.347_{.008}$ | $.617_{.007}$
IT-O | logi | $.736_{.007}$ | $1.164_{.012}$ | $1.512_{.013}$ | $.570_{.008}$ | $.700_{.009}$ | $.975_{.012}$ | $.320_{.006}$ | $.348_{.008}$ | $.617_{.007}$
hing | $.740_{.008}$ | $1.192_{.049}$ | $1.546_{.071}$ | $.573_{.008}$ | $.706_{.010}$ | $.980_{.014}$ | $.320_{.006}$ | $.348_{.008}$ | $.617_{.007}$
smhi | $.736_{.007}$ | $1.165_{.013}$ | $1.514_{.014}$ | $.570_{.008}$ | $.701_{.010}$ | $.975_{.010}$ | $.320_{.006}$ | $.347_{.008}$ | $.617_{.007}$
sqhi | $.736_{.007}$ | $1.165_{.016}$ | $1.513_{.013}$ | $.570_{.007}$ | $.700_{.010}$ | $.975_{.011}$ | $.320_{.005}$ | $.347_{.008}$ | $.617_{.007}$
expo | $.737_{.008}$ | $1.164_{.013}$ | $1.512_{.013}$ | $.570_{.008}$ | $.699_{.010}$ | $.975_{.012}$ | $.322_{.007}$ | $.350_{.009}$ | $.619_{.009}$
abso | $.737_{.007}$ | $1.170_{.030}$ | $1.524_{.035}$ | $.579_{.013}$ | $.721_{.026}$ | $.998_{.029}$ | $.327_{.015}$ | $.355_{.018}$ | $.626_{.019}$
squa | $.735_{.007}$ | $1.163_{.014}$ | $1.512_{.013}$ | $.569_{.008}$ | $.700_{.010}$ | $.976_{.011}$ | $.321_{.005}$ | $.348_{.008}$ | $.617_{.008}$

Table 10: Results for the experiment in Section 4.2 with the data
$\text{O-}(1/3,1)$, $\text{O-}(1/3,3)$, and $\text{O-}(1/3,3)$.

|  | O-(1/3,1) | O-(1/3,3) | O-(1,3)
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
MLR | $.678_{.033}$ | $.989_{.194}$ | $1.335_{.230}$ | $.575_{.075}$ | $.858_{.374}$ | $1.251_{.377}$ | $.495_{.059}$ | $.600_{.236}$ | $.903_{.298}$
AT-O | logi | $.668_{.008}$ | $.940_{.014}$ | $1.276_{.012}$ | $.561_{.008}$ | $.776_{.016}$ | $1.165_{.016}$ | $.483_{.010}$ | $.551_{.016}$ | $.844_{.065}$
hing | $.668_{.009}$ | $.942_{.016}$ | $1.284_{.016}$ | $.561_{.013}$ | $.779_{.019}$ | $1.173_{.037}$ | $.481_{.009}$ | $.547_{.019}$ | $.841_{.067}$
smhi | $.670_{.010}$ | $.941_{.014}$ | $1.278_{.014}$ | $.560_{.010}$ | $.773_{.013}$ | $1.165_{.012}$ | $.480_{.009}$ | $.543_{.011}$ | $.827_{.020}$
sqhi | $.669_{.007}$ | $.939_{.013}$ | $1.278_{.015}$ | $.561_{.010}$ | $.775_{.012}$ | $1.165_{.013}$ | $.479_{.011}$ | $.542_{.007}$ | $.825_{.006}$
expo | $.670_{.008}$ | $.940_{.015}$ | $1.278_{.013}$ | $.562_{.012}$ | $.776_{.013}$ | $1.164_{.013}$ | $.483_{.011}$ | $.546_{.009}$ | $.828_{.013}$
abso | $.721_{.044}$ | $1.126_{.148}$ | $1.479_{.156}$ | $.670_{.071}$ | $1.056_{.158}$ | $1.434_{.138}$ | $.615_{.057}$ | $.848_{.154}$ | $1.149_{.158}$
squa | $.668_{.008}$ | $.938_{.012}$ | $1.278_{.013}$ | $.557_{.008}$ | $.777_{.018}$ | $1.165_{.018}$ | $.476_{.009}$ | $.542_{.009}$ | $.826_{.010}$
IT-N | logi | $.667_{.008}$ | $.941_{.018}$ | $1.279_{.015}$ | $.558_{.008}$ | $.774_{.012}$ | $1.166_{.013}$ | $.480_{.011}$ | $.542_{.010}$ | $.825_{.012}$
hing | $.667_{.010}$ | $.946_{.013}$ | $1.282_{.013}$ | $.559_{.008}$ | $.781_{.016}$ | $1.169_{.020}$ | $.480_{.011}$ | $.547_{.010}$ | $.829_{.011}$
smhi | $.667_{.010}$ | $.944_{.020}$ | $1.286_{.039}$ | $.556_{.008}$ | $.777_{.016}$ | $1.170_{.022}$ | $.478_{.010}$ | $.543_{.009}$ | $.825_{.011}$
sqhi | $.667_{.009}$ | $.937_{.011}$ | $1.279_{.013}$ | $.558_{.010}$ | $.777_{.018}$ | $1.170_{.019}$ | $.479_{.010}$ | $.544_{.009}$ | $.825_{.012}$
expo | $.667_{.008}$ | $.946_{.015}$ | $1.287_{.023}$ | $.557_{.011}$ | $.776_{.013}$ | $1.168_{.011}$ | $.483_{.019}$ | $.557_{.049}$ | $.837_{.053}$
abso | $.673_{.010}$ | $.960_{.031}$ | $1.301_{.042}$ | $.566_{.010}$ | $.796_{.021}$ | $1.181_{.021}$ | $.485_{.014}$ | $.554_{.025}$ | $.837_{.028}$
squa | $.665_{.007}$ | $.940_{.012}$ | $1.279_{.013}$ | $.558_{.009}$ | $.772_{.012}$ | $1.162_{.012}$ | $.480_{.008}$ | $.544_{.009}$ | $.827_{.009}$
IT-O | logi | $.669_{.009}$ | $.947_{.020}$ | $1.288_{.031}$ | $.558_{.009}$ | $.777_{.012}$ | $1.165_{.015}$ | $.479_{.007}$ | $.544_{.008}$ | $.825_{.008}$
hing | $.670_{.008}$ | $.947_{.016}$ | $1.282_{.018}$ | $.559_{.009}$ | $.777_{.014}$ | $1.169_{.017}$ | $.479_{.011}$ | $.543_{.010}$ | $.827_{.012}$
smhi | $.668_{.009}$ | $.944_{.016}$ | $1.281_{.013}$ | $.557_{.009}$ | $.775_{.017}$ | $1.164_{.020}$ | $.480_{.009}$ | $.545_{.011}$ | $.826_{.011}$
sqhi | $.668_{.009}$ | $.943_{.013}$ | $1.280_{.012}$ | $.558_{.009}$ | $.781_{.016}$ | $1.172_{.030}$ | $.478_{.011}$ | $.541_{.007}$ | $.825_{.009}$
expo | $.667_{.008}$ | $.940_{.023}$ | $1.284_{.042}$ | $.559_{.011}$ | $.776_{.015}$ | $1.166_{.012}$ | $.478_{.010}$ | $.543_{.008}$ | $.824_{.009}$
abso | $.672_{.010}$ | $.953_{.028}$ | $1.294_{.032}$ | $.568_{.010}$ | $.800_{.023}$ | $1.191_{.020}$ | $.481_{.011}$ | $.550_{.014}$ | $.832_{.014}$
squa | $.670_{.010}$ | $.947_{.020}$ | $1.283_{.022}$ | $.559_{.009}$ | $.777_{.020}$ | $1.173_{.039}$ | $.479_{.010}$ | $.548_{.013}$ | $.833_{.028}$

Table 11: Results for the experiment in Section 4.2 with the data
$\text{N-}1/3$, $\text{N-}1$, and $\text{N-}3$.

|  | N-1/3 | N-1 | N-3
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
MLR | $.742_{.008}$ | $1.914_{.013}$ | $2.397_{.011}$ | $.591_{.010}$ | $1.283_{.024}$ | $1.693_{.018}$ | $.362_{.008}$ | $.697_{.015}$ | $1.087_{.010}$
AT-O | logi | $.782_{.017}$ | $1.940_{.022}$ | $2.407_{.018}$ | $.665_{.021}$ | $1.310_{.019}$ | $1.695_{.018}$ | $.523_{.016}$ | $.758_{.015}$ | $1.091_{.013}$
hing | $.784_{.022}$ | $1.946_{.024}$ | $2.425_{.024}$ | $.657_{.024}$ | $1.324_{.021}$ | $1.705_{.024}$ | $.504_{.066}$ | $.809_{.244}$ | $1.167_{.273}$
smhi | $.780_{.017}$ | $1.940_{.022}$ | $2.411_{.025}$ | $.671_{.015}$ | $1.312_{.026}$ | $1.696_{.020}$ | $.507_{.018}$ | $.747_{.019}$ | $1.094_{.015}$
sqhi | $.782_{.015}$ | $1.935_{.021}$ | $2.411_{.022}$ | $.665_{.019}$ | $1.315_{.030}$ | $1.699_{.022}$ | $.514_{.014}$ | $.759_{.021}$ | $1.093_{.013}$
expo | $.780_{.011}$ | $1.939_{.018}$ | $2.409_{.019}$ | $.674_{.020}$ | $1.311_{.025}$ | $1.697_{.022}$ | $.526_{.020}$ | $.763_{.018}$ | $1.094_{.011}$
abso | $.788_{.018}$ | $1.935_{.021}$ | $2.410_{.019}$ | $.688_{.037}$ | $1.360_{.066}$ | $1.752_{.071}$ | $.684_{.107}$ | $1.188_{.333}$ | $1.530_{.358}$
squa | $.778_{.018}$ | $1.944_{.019}$ | $2.415_{.013}$ | $.665_{.014}$ | $1.310_{.023}$ | $1.697_{.020}$ | $.523_{.013}$ | $.764_{.018}$ | $1.096_{.011}$
IT-N | logi | $.771_{.014}$ | $1.949_{.033}$ | $2.422_{.024}$ | $.661_{.011}$ | $1.317_{.016}$ | $1.695_{.019}$ | $.514_{.010}$ | $.764_{.020}$ | $1.097_{.017}$
hing | $.786_{.023}$ | $2.072_{.101}$ | $2.533_{.086}$ | $.641_{.014}$ | $1.384_{.079}$ | $1.795_{.089}$ | $.464_{.041}$ | $.797_{.037}$ | $1.151_{.035}$
smhi | $.769_{.013}$ | $1.974_{.038}$ | $2.438_{.025}$ | $.654_{.014}$ | $1.337_{.029}$ | $1.730_{.037}$ | $.486_{.016}$ | $.760_{.021}$ | $1.108_{.020}$
sqhi | $.770_{.011}$ | $1.954_{.025}$ | $2.422_{.015}$ | $.659_{.010}$ | $1.319_{.019}$ | $1.697_{.021}$ | $.511_{.014}$ | $.761_{.018}$ | $1.095_{.012}$
expo | $.773_{.011}$ | $1.944_{.028}$ | $2.416_{.024}$ | $.669_{.012}$ | $1.321_{.028}$ | $1.702_{.021}$ | $.511_{.016}$ | $.766_{.020}$ | $1.097_{.012}$
abso | $.780_{.022}$ | $2.082_{.095}$ | $2.538_{.070}$ | $.657_{.015}$ | $1.435_{.063}$ | $1.861_{.073}$ | $.484_{.023}$ | $.870_{.053}$ | $1.215_{.050}$
squa | $.768_{.007}$ | $1.942_{.020}$ | $2.419_{.019}$ | $.656_{.014}$ | $1.312_{.022}$ | $1.700_{.019}$ | $.510_{.014}$ | $.760_{.017}$ | $1.098_{.016}$
IT-O | logi | $.773_{.007}$ | $1.951_{.027}$ | $2.420_{.021}$ | $.666_{.012}$ | $1.317_{.018}$ | $1.700_{.017}$ | $.512_{.014}$ | $.759_{.020}$ | $1.098_{.012}$
hing | $.775_{.016}$ | $2.028_{.085}$ | $2.481_{.063}$ | $.653_{.013}$ | $1.340_{.036}$ | $1.739_{.044}$ | $.510_{.078}$ | $.919_{.292}$ | $1.291_{.352}$
smhi | $.773_{.010}$ | $1.955_{.028}$ | $2.424_{.026}$ | $.658_{.012}$ | $1.323_{.026}$ | $1.708_{.026}$ | $.495_{.017}$ | $.761_{.021}$ | $1.104_{.012}$
sqhi | $.774_{.008}$ | $1.959_{.032}$ | $2.426_{.026}$ | $.665_{.012}$ | $1.318_{.026}$ | $1.703_{.024}$ | $.514_{.013}$ | $.765_{.018}$ | $1.097_{.013}$
expo | $.772_{.008}$ | $1.947_{.023}$ | $2.420_{.019}$ | $.669_{.014}$ | $1.328_{.043}$ | $1.709_{.039}$ | $.542_{.060}$ | $.904_{.340}$ | $1.269_{.419}$
abso | $.788_{.025}$ | $2.085_{.114}$ | $2.531_{.096}$ | $.665_{.043}$ | $1.408_{.107}$ | $1.823_{.113}$ | $.562_{.109}$ | $1.161_{.453}$ | $1.573_{.552}$
squa | $.773_{.011}$ | $1.958_{.031}$ | $2.429_{.030}$ | $.667_{.015}$ | $1.317_{.026}$ | $1.705_{.025}$ | $.518_{.014}$ | $.769_{.022}$ | $1.098_{.014}$

Figure 6 shows the learned 1DT value $\hat{a}_{i}=\hat{a}(x^{[i]})$, method’s
label prediction $\hat{f}_{\ell,i}=\hat{f}(x^{[i]})$, and optimal label
prediction $\tilde{f}_{\ell,i}$ for several instances of the experiment in
Section 4.2. This indicates representative behaviors of threshold methods
based on a learning procedure with non-PL and PL losses in a finite-sample
situation.

| (o1) H-1, logi | (o2) M-1, logi | (o3) A-1, logi | (o4) O-(1/3,3), logi
---|---|---|---|---
AT-O |  |  |  |
IT-N |  |  |  |
IT-O |  |  |  |
| (o5) N-1, logi | (o6) H-1/3, hing | (o7) H-1, hing | (o8) H-3, hing
AT-O |  |  |  |
IT-N |  |  |  |
IT-O |  |  |  |

Figure 6: Learned 1DT value $\hat{a}_{i}$ and optimal label prediction
$\tilde{f}_{\ell,i}$ (color of point) versus $i$, and method’s label
prediction (lightened background color), which represents $\hat{f}_{\ell,i}$,
with $i$-th smallest point $x^{[i]}$ in the domain of $X$, in a certain trial
for the experiment in Section 4.2 with Task-Z. For example, 3 plates of (o1)
show 3 results for H-1 with logi-AT-O, -IT-N, and -IT-O from top to bottom.

###  A.3 Results for Real-World Data Experiment in Section 4.3

Table 12 shows the mean and SD of the test prediction errors (as
‘$\text{mean}_{\text{SD}}$’) of MLR and 21 threshold methods for the
experiment in Section 4.3. This table is colored according to the same rule as
that for Tables 7–11.

Table 12: Results for the experiment in Section 4.3.

|  | MORPH-2 | CACD | AFAD
---|---|---|---|---
|  | MZE | MAE | RMSE | MZE | MAE | RMSE | MZE | MAE | RMSE
MLR | $.878_{.006}$ | $3.218_{.092}$ | $4.303_{.121}$ | $.931_{.003}$ | $5.541_{.110}$ | $7.578_{.120}$ | $.873_{.003}$ | $3.402_{.043}$ | $4.564_{.051}$
AT-O | logi | $.882_{.003}$ | $3.151_{.097}$ | $4.176_{.126}$ | $.937_{.001}$ | $5.649_{.055}$ | $7.629_{.046}$ | $.879_{.001}$ | $3.383_{.026}$ | $4.529_{.026}$
hing | $.882_{.002}$ | $3.091_{.047}$ | $4.105_{.062}$ | $.931_{.001}$ | $5.424_{.033}$ | $7.506_{.047}$ | $.885_{.002}$ | $3.532_{.016}$ | $4.756_{.017}$
smhi | $.878_{.004}$ | $3.060_{.039}$ | $4.075_{.050}$ | $.933_{.001}$ | $5.526_{.051}$ | $7.553_{.056}$ | $.878_{.002}$ | $3.376_{.020}$ | $4.531_{.019}$
sqhi | $.880_{.005}$ | $3.113_{.053}$ | $4.155_{.057}$ | $.936_{.002}$ | $5.707_{.026}$ | $7.690_{.035}$ | $.879_{.002}$ | $3.399_{.035}$ | $4.556_{.033}$
expo | $.886_{.007}$ | $3.206_{.176}$ | $4.231_{.221}$ | $.943_{.002}$ | $6.187_{.117}$ | $8.110_{.124}$ | $.883_{.004}$ | $3.508_{.096}$ | $4.655_{.105}$
abso | $.926_{.018}$ | $5.327_{1.773}$ | $6.744_{2.061}$ | $.963_{.005}$ | $8.667_{.646}$ | $10.588_{.604}$ | $.915_{.007}$ | $4.771_{.262}$ | $6.028_{.278}$
squa | $.869_{.003}$ | $2.818_{.026}$ | $3.824_{.043}$ | $.923_{.000}$ | $5.120_{.042}$ | $7.346_{.061}$ | $.879_{.002}$ | $3.376_{.013}$ | $4.559_{.019}$
IT-N | logi | $.894_{.005}$ | $3.685_{.113}$ | $4.884_{.149}$ | $.943_{.002}$ | $6.376_{.074}$ | $8.368_{.063}$ | $.883_{.002}$ | $3.775_{.020}$ | $4.968_{.025}$
hing | $.891_{.003}$ | $3.623_{.123}$ | $4.794_{.167}$ | $.967_{.002}$ | $9.304_{.456}$ | $11.150_{.411}$ | $.908_{.004}$ | $4.690_{.125}$ | $5.940_{.131}$
smhi | $.891_{.003}$ | $3.517_{.070}$ | $4.671_{.096}$ | $.942_{.001}$ | $6.253_{.120}$ | $8.219_{.116}$ | $.884_{.002}$ | $3.751_{.022}$ | $4.946_{.010}$
sqhi | $.896_{.003}$ | $3.700_{.094}$ | $4.896_{.133}$ | $.947_{.003}$ | $6.662_{.220}$ | $8.630_{.219}$ | $.883_{.002}$ | $3.747_{.043}$ | $4.940_{.039}$
expo | $.904_{.002}$ | $4.276_{.190}$ | $5.627_{.242}$ | $.947_{.002}$ | $6.571_{.116}$ | $8.543_{.119}$ | $.889_{.001}$ | $3.955_{.095}$ | $5.170_{.100}$
abso | $.892_{.003}$ | $3.643_{.098}$ | $4.834_{.143}$ | $.970_{.002}$ | $9.634_{.220}$ | $11.442_{.187}$ | $.912_{.005}$ | $4.780_{.109}$ | $6.032_{.110}$
squa | $.894_{.003}$ | $3.703_{.079}$ | $4.905_{.112}$ | $.945_{.001}$ | $6.486_{.076}$ | $8.457_{.073}$ | $.884_{.002}$ | $3.749_{.049}$ | $4.943_{.050}$
IT-O | logi | $.899_{.004}$ | $4.015_{.157}$ | $5.310_{.206}$ | $.944_{.001}$ | $6.432_{.125}$ | $8.407_{.121}$ | $.883_{.003}$ | $3.679_{.046}$ | $4.861_{.053}$
hing | $.895_{.007}$ | $3.573_{.172}$ | $4.715_{.198}$ | $.967_{.003}$ | $9.174_{.403}$ | $11.037_{.365}$ | $.905_{.008}$ | $4.445_{.270}$ | $5.686_{.281}$
smhi | $.893_{.005}$ | $3.617_{.145}$ | $4.787_{.201}$ | $.945_{.003}$ | $6.511_{.246}$ | $8.479_{.239}$ | $.878_{.002}$ | $3.579_{.031}$ | $4.760_{.039}$
sqhi | $.902_{.003}$ | $4.068_{.146}$ | $5.382_{.196}$ | $.945_{.001}$ | $6.492_{.080}$ | $8.463_{.076}$ | $.882_{.002}$ | $3.656_{.046}$ | $4.840_{.048}$
expo | $.895_{.004}$ | $3.780_{.110}$ | $5.010_{.126}$ | $.945_{.002}$ | $6.575_{.191}$ | $8.551_{.200}$ | $.887_{.004}$ | $3.849_{.099}$ | $5.055_{.104}$
abso | $.888_{.003}$ | $3.540_{.068}$ | $4.683_{.087}$ | $.966_{.007}$ | $9.140_{.953}$ | $10.966_{.888}$ | $.918_{.002}$ | $4.899_{.013}$ | $6.161_{.013}$
squa | $.901_{.006}$ | $3.965_{.099}$ | $5.234_{.143}$ | $.946_{.001}$ | $6.596_{.103}$ | $8.556_{.117}$ | $.883_{.002}$ | $3.692_{.057}$ | $4.874_{.054}$

Table 13 shows the mean and SD of the number of unique elements of the learned
bias parameter vector for the experiment in Section 4.3.

Table 13: Mean and SD of the number of unique elements of the learned bias
parameter vector for the experiment in Section 4.3.

|  | MORPH-2 | CACD | AFAD
---|---|---|---|---
AT-O | logi | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$
hing | $54.0_{.000}$ | $47.8_{.400}$ | $24.4_{.800}$
smhi | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$
sqhi | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$
expo | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$
abso | $18.6_{3.878}$ | $14.0_{1.414}$ | $9.6_{1.356}$
squa | $49.2_{1.327}$ | $48.0_{.000}$ | $25.0_{.000}$

|  | MORPH-2 | CACD | AFAD
---|---|---|---|---
IT-N | logi | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$
hing | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$
smhi | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$
sqhi | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$
expo | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$
abso | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$
squa | $54.0_{.000}$ | $48.0_{.000}$ | $25.0_{.000}$

|  | MORPH-2 | CACD | AFAD
---|---|---|---|---
IT-O | logi | $42.4_{3.499}$ | $28.6_{1.960}$ | $8.0_{.000}$
hing | $35.8_{4.792}$ | $35.4_{10.131}$ | $6.2_{.400}$
smhi | $42.6_{5.389}$ | $27.8_{.748}$ | $8.0_{.000}$
sqhi | $48.6_{3.611}$ | $28.8_{2.638}$ | $8.0_{.000}$
expo | $40.4_{5.276}$ | $32.2_{.748}$ | $9.2_{.980}$
abso | $26.2_{2.857}$ | $36.4_{8.499}$ | $6.4_{.490}$
squa | $45.0_{4.817}$ | $29.6_{1.960}$ | $8.0_{.000}$

Figure 7 gives plots of $(y_{i},\hat{a}({\bm{x}}_{i}))$’s for representative
settings of the experiment in Section 4.3. In results with the Hinge-IT loss
in Figure 7 (q5) and (q6), learned 1DT values $\hat{a}({\bm{x}}_{i})$’s are
concentrated at 1 point.

| (q1) MORPH-2, logi | (q2) CACD, logi | (q3) AFAD, logi
---|---|---|---
AT-O |  |  |
IT-N |  |  |
IT-O |  |  |
| (q4) MORPH-2, hing | (q5) CACD, hing | (q6) AFAD, hing
AT-O |  |  |
IT-N |  |  |
IT-O |  |  |
Figure 7: Scatter and violin plots of $(y_{i},\hat{a}({\bm{x}}_{i}))$’s for
test data for the experiment in Section 4.3. The vertical axis is restricted
to $[L-0.05(U-L),U+0.05(U-L)]$ with $1$ percentile $L$ and $99$ percentile $U$
of $\hat{a}({\bm{x}}_{i})$’s.

##  Appendix B Proofs of Theorems

We here provide proofs of the theoretical results presented in this paper.

##### Proof of Theorem 1

We first provide a proof of Theorem 1:

###### Proof of Theorem 1.

Proof of (a9) We first prove the relationship (a9) between the conditions
(a1)–(a6). When $\varphi$ is non-increasing (a2),
$\varphi(u_{1})\geq\varphi(u_{2})$ and $\varphi(-u_{2})\geq\varphi(-u_{1})$ if
$u_{1}<u_{2}$. When $\varphi(\cdot)-\varphi(-\cdot)$ is non-increasing (a3),
$\varphi(u_{1})-\varphi(-u_{1})\geq\varphi(u_{2})-\varphi(-u_{2})$ if
$u_{1}<u_{2}$. Since both the results imply (a1), one has ‘(a2) $\Rightarrow$
(a1)’ and ‘(a3) $\Rightarrow$ (a1)’. The statements ‘(a5) $\Rightarrow$ (a4)’
and ‘(a6) $\Rightarrow$ (a4)’ can be proved in a similar way.

In the following, we prove the population version of the statements (a10) and
(a11) regarding the order of the optimized bias parameter vector. Note that
the surrogate risk for the AT surrogate loss is

$\displaystyle\begin{split}\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]&=\operatorname{{\mathbb{E}}}\biggl{[}\sum_{y=1}^{K}\Pr(Y=y|{\bm{X}})\biggl{\\{}\sum_{k=1}^{y-1}\varphi(a({\bm{X}})-b_{k})+\sum_{k=y}^{K-1}\varphi(b_{k}-a({\bm{X}}))\biggr{\\}}\biggr{]}\\\
&=\operatorname{{\mathbb{E}}}\biggl{[}\sum_{y=1}^{K-1}\\{\Pr(Y\leq
y|{\bm{X}})\varphi(b_{y}-a({\bm{X}}))+\Pr(Y>y|{\bm{X}})\varphi(a({\bm{X}})-b_{y})\\}\biggr{]}.\end{split}$
(36)

Proof of (a10) Assume that any surrogate risk minimizer
$(\bar{a},\bar{{\bm{b}}})$ has a pair $(\bar{b}_{l},\bar{b}_{m})$ satisfying
$\bar{b}_{l}>\bar{b}_{m}$ with $l,m\in[K-1]$ such that $l<m$. For
$\check{{\bm{b}}}=(\check{b}_{k})_{k\in[K-1]}$ consisting of

$\displaystyle\check{b}_{k}:=\begin{cases}\bar{b}_{m}&\text{if }k=l,\\\
\bar{b}_{l}&\text{if }k=m,\\\ \bar{b}_{k}&\text{otherwise},\end{cases}$ (37)

one has that

$\displaystyle\begin{split}&\operatorname{{\mathbb{E}}}[\phi(\bar{a}({\bm{X}}),\bar{{\bm{b}}},Y)]-\operatorname{{\mathbb{E}}}[\phi(\bar{a}({\bm{X}}),\check{{\bm{b}}},Y)]\\\
&=\operatorname{{\mathbb{E}}}[\Pr(Y\leq
l|{\bm{X}})\varphi(\bar{b}_{l}-\bar{a}({\bm{X}}))+\Pr(Y>l|{\bm{X}})\varphi(\bar{a}({\bm{X}})-\bar{b}_{l})\\\
&\hphantom{=\operatorname{{\mathbb{E}}}[}+\Pr(Y\leq
m|{\bm{X}})\varphi(\bar{b}_{m}-\bar{a}({\bm{X}}))+\Pr(Y>m|{\bm{X}})\varphi(\bar{a}({\bm{X}})-\bar{b}_{m})\\\
&\hphantom{=\operatorname{{\mathbb{E}}}[}+(\text{$(\bar{b}_{l},\bar{b}_{m})$-independent
term})]\\\ &-\operatorname{{\mathbb{E}}}[\Pr(Y\leq
l|{\bm{X}})\varphi(\bar{b}_{m}-\bar{a}({\bm{X}}))+\Pr(Y>l|{\bm{X}})\varphi(\bar{a}({\bm{X}})-\bar{b}_{m})\\\
&\hphantom{=\operatorname{{\mathbb{E}}}[}+\Pr(Y\leq
m|{\bm{X}})\varphi(\bar{b}_{l}-\bar{a}({\bm{X}}))+\Pr(Y>m|{\bm{X}})\varphi(\bar{a}({\bm{X}})-\bar{b}_{l})\\\
&\hphantom{=\operatorname{{\mathbb{E}}}[}+(\text{$(\bar{b}_{l},\bar{b}_{m})$-independent
term})]\\\
&=\operatorname{{\mathbb{E}}}[\Pr(Y\in\\{l+1,\ldots,m\\}|{\bm{X}})\\\
&\hphantom{=\operatorname{{\mathbb{E}}}[}\times\\{\varphi(\bar{a}({\bm{X}})-\bar{b}_{l})-\varphi(\bar{b}_{l}-\bar{a}({\bm{X}}))-\varphi(\bar{a}({\bm{X}})-\bar{b}_{m})+\varphi(\bar{b}_{m}-\bar{a}({\bm{X}}))\\}].\end{split}$
(38)

From the assumption (a8), there exists a point ${\bm{x}}\in{\mathbb{R}}$ such
that $\Pr(Y\in\\{l+1,\ldots,m\\}|{\bm{X}}={\bm{x}})>0$. The condition (a1)
with $u_{1}=\bar{a}({\bm{X}})-\bar{b}_{l}$ and
$u_{2}=\bar{a}({\bm{X}})-\bar{b}_{m}$ ($u_{1}<u_{2}$ since
$\bar{b}_{l}>\bar{b}_{m}$) implies
$\varphi(\bar{a}({\bm{X}})-\bar{b}_{l})-\varphi(\bar{b}_{l}-\bar{a}({\bm{X}}))-\varphi(\bar{a}({\bm{X}})-\bar{b}_{m})+\varphi(\bar{b}_{m}-\bar{a}({\bm{X}}))\geq
0$. Therefore, one has
$\operatorname{{\mathbb{E}}}[\phi(\bar{a}({\bm{X}}),\check{{\bm{b}}},Y)]\leq\operatorname{{\mathbb{E}}}[\phi(\bar{a}({\bm{X}}),\bar{{\bm{b}}},Y)]$.
Also, as changing the bias parameter vector from $\bar{{\bm{b}}}$ to
$\check{{\bm{b}}}$, the total number of pairs of bias parameters validating
the order is reduced by at least one. Therefore, by repeating the above
operations sequentially for pairs of bias parameters validating the order, one
can finally obtain the bias parameter vector satisfying the order condition
without increasing the surrogate risk. This result contradicts to the
assumption that any $\bar{{\bm{b}}}$ has a pair $(\bar{b}_{l},\bar{b}_{m})$
satisfying $\bar{b}_{l}>\bar{b}_{m}$ with $l<m$. Thus, there exists a
surrogate risk minimizer $(\bar{a},\bar{{\bm{b}}})$ satisfying
$\bar{b}_{l}\leq\bar{b}_{m}$ for any $l,m\in[K-1]$ such that $l<m$.

Proof of (a11) This can be proved in the same way as the above proof. ∎

##### Generalization of Theorem 1

Moreover, Theorem 1 can be generalized to a regularized version as follows:

######  Corollary 1.

Let ${\mathcal{A}}\subseteq\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}$,
${\mathcal{B}}_{0}^{\rm ord}\subseteq{\mathcal{B}}\subseteq{\mathcal{B}}_{0}$,
and a real-valued functional $\Lambda$ satisfy
$\Lambda(a,{\bm{b}},{\bm{x}},y)\geq\Lambda(a,\pi({\bm{b}}),{\bm{x}},y)$ for
any $a\in{\mathcal{A}}$, ${\bm{b}}\in{\mathcal{B}}$,
${\bm{x}}\in{\mathbb{R}}^{d}$, $y\in[K]$ and sort