Risk-Sensitive Learning via Expected Shortfall Minimization
Hisashi Kashimahkashima@jp.ibm.com

Tokyo Research Laboratory
IBM Research623-14 Shimotsuruma, Yamato-shi, 242-8502 Kanagawa, Japan

Abstract
A new approach for cost-sensitive classification is proposed. We extend the frameworkof cost-sensitive learning to mitigate risks of huge costs occurring with low probabilities,
and propose an algorithm that achieves this goal. Instead of minimizing the expected costcommonly used in cost-sensitive learning, our algorithm minimizes expected shortfall, also
known as conditional value-at-risk, which is considered as a good risk metric in the areaof financial engineering. The proposed algorithm is a general meta-learning algorithm thatcan exploit existing example-dependent cost-sensitive learning algorithms, and is capable ofdealing with not only alternative actions in ordinary classification tasks, but also allocative
actions in resource-allocation type tasks. Experiments on tasks with example-dependent
costs show promising results.
Keywords: risk-sensitive learning, cost-sensitive learning, meta learning, risk management, expected shortfall, conditional value-at-risk

1. Introduction
Classification learning is one of the fundamental tasks in data mining. It is widely seen in
many important tasks in the real world such as diagnostics in health care, credit administration in finance, campaign management in direct marketing, and so on. Its task is topredict the actions (or classes) of the target objects whose appropriate action (or classes) are
unknown given pairs of an object and its appropriate action (or class) as training examples.
In other words, it aims to minimize the probability of misclassification.
However, there are many cases where it is not enough only to minimize the number of
mistakes. For example, the cost of misdiagnosis of classifying healthy people as sick andthat of classifying sick people as healthy are apparently not equal, since the latter leads toserious results. Moreover, the degree of seriousness differs among patients.
Similarly, when we make management decision on what project should be invested, theexecution cost, profit from success, and loss from failure depend on the characteristics ofthe project.
Cost-sensitive learning (Elkan, 2001; Bradford et al., 1998; Domingos, 1999; Fan et al.,
1999; Zadrozny and Elkan, 2001; Geibel et al., 2004; Zadrozny et al., 2003; Abe and. The extend abstract of this paper will appear in the proceedings of the Sixth SIAM
International Conference on Data Mining (SDM06), which is temporarily available at
http://www.geocities.jp/kashi pong/publication/Risk SDM.pdf .
c°2006
Hisashi Kashima.

Kashima

Zadrozny, 2004) is a suitable framework for such cases where costs are different amongclasses or objects, and the amounts of them are unknown at the stage of prediction. Wider
range of problems can be treated in the framework since it aims to minimize not the probability of misclassification, but the expected cost of misclassification. The ordinary classification problem is understood as a special case that assumes that all costs of misclassification
are 0 or 1.
However, from the standpoint of risk management, there are situations where costsensitive learning is still not enough. Minimizing the expected cost indeed decrease potential
cost averagely, but since it does not aggressively suppress the occurrence of huge costs, it
can not avoid such a risk of disasters. Therefore, if there is not a little chance of huge costs,
and also if users are interested in mitigating the risk, minimization of the expected costdoes not reflect the objective. Actually, risk aversion is one of the central topics in financial
engineering. For example in portfolio theory, it is expected to find a portfolio that maximizes
profit while suppressing the risks of huge costs occurring with low probabilities (Luenberger,
1998).
In this paper, we propose an approach of risk-sensitive classification that considers
cost distributions not to decrease the expected cost, but to mitigate the risks of hugecosts. Concretely, instead of the expected cost, we employ a risk metric called expectedshortfall (Artzner et al., 1999), also known as conditional value-at-risk, which is attracting considerable attentions in financial engineering. We propose a risk-sensitive learningalgorithm that minimizes the expected shortfall as the objective function. Our algorithm
is a meta-learning algorithm, which is quite a general procedure that can convert existing
cost-sensitive learners to risk-sensitive learners.
This paper is organized as follows. In Section 2, we review the definition and the existing
approaches of cost-sensitive learning, and then point out a drawback from the standpoint ofrisk management. In Section 3, we introduce our risk-sensitive learning approach using expected shortfall as the objective function, and propose a meta learning algorithm, MetaRisk.
We also introduce reduction from cost-sensitive learners to risk-sensitive learners not onlywith alternative actions, but also with allocative actions that are not considered in ordinary cost-sensitive learning problems. In Section 4, we show some experimental results on
two datasets, a synthetic dataset and a more realistic dataset for credit administration. In
Section 5, we review related works, and discuss their relations to our approach. Finally, we
conclude this paper with discussion and future work.

2. Cost-Sensitive Learning
In this section, we review the definition and the existing approaches of cost-sensitive learning, especially with example-dependent costs. And then, we point out a drawback of theseapproaches from the standpoint of risk management.
2.1 Decision Model
Let X be a set of all target objects, for example X = RM , and Y be a finite set of actions
taken against the target objects. For example in the context of direct marketing, x ∈ X isa customer profile, and Y is a set of possible marketing actions such as direct mail, email,telemarketing, and so on.
2Risk-Sensitive Learning via Expected Shortfall Minimization

Function h is called hypothesis, and defined as h(x, y; θ) : X × Y → R, where θ is its
model parameters. An action ŷ ∈ Y taken against x ∈ X is determined byŷ = argmax h(x, y; θ).

(1)

y∈Y

Usually, only one action is assumed to be taken at a time, hence we call this type of actions
alternative actions.
We might assume the following stochastic constraint in h(x, y; θ),X
h(x, y; θ) = 1, s.t. h(x, y; θ) ≥ 0,(2)y∈Y

for ∀x ∈ X, ∀y ∈ Y . Instead of (1), we can make stochastic selection of one of alternative
actions with probability distribution (2).
If it is allowed to take multiple actions at a time, and to allocate resources to each of|Y | actions in proportion to h(x, y; θ) with (2), those kind of actions are called allocative.
Allocative actions are popular in the context of portfolio selection (Luenberger, 1998) where
funds are allocatively invested to financial products.
In this paper, we deal with those two cases, in one of which an action is alternatively
chosen with (1), and in the other of which stochastic selection or resource allocation isallowed with (2).
2.2 Cost Function
Cost function is a function c(x, y) : X × Y → R, which indicates how bad an action y ∈ Ytaken against x ∈ X is.
For instance in medical diagnosis, c(x, y) is the badness of the medical treatment y taken
for a patient with the results of medical tests x. c(x, y) becomes small if the treatment isappropriate, and becomes large if not. If the treatment is significantly inappropriate, andhis or her health is lost, c(x, y) becomes huge.
In this paper, we deal with the most general problem setting in cost-sensitive learning,where the true cost function is unknown, and depends on examples (Zadrozny and Elkan,
2001; Geibel et al., 2004; Abe and Zadrozny, 2004). Note that although those literatures
assume that the cost function also depends on classes, we adopt the notation without the dependency since it is convenient to think that the cost function incorporates the dependency
on classes implicitly.
Also, following the context of cost-sensitive learning, we evaluate actions in terms of
cost instead of reward or profit, but the following discussion still holds for reward or profit
by simply changing those signs.
Let c(x, h(θ)) be the cost of the action for x by using hypothesis h(x, y; θ). In the caseof alternative actions (1), c(x, h(θ)) becomesc(x, h(θ)) = c(x, argmax h(x, y; θ)).

(3)

y∈Y

In the case of allocative actions, it is not trivial to represent c(x, h(θ)). We consider thesimplest case where c(x, h(θ)) is represented asXc(x, h(θ)) =h(x, y; θ)c(x, y),
(4)
y∈Y

3

Kashima

where the cost of each action linearly depends the amounts of investment to the action.
This form corresponds to the return of a portfolio used in portfolio theory (Luenberger,
1998).
Note that if we make stochastic selection of an alternative action by (2), we can alsouse (4), but this is not the realized cost, but the expected cost for x.
2.3 Cost-Sensitive Learning
Cost-sensitive learning (Elkan, 2001; Bradford et al., 1998; Domingos, 1999; Fan et al., 1999;
Zadrozny and Elkan, 2001; Geibel et al., 2004; Zadrozny et al., 2003; Abe and Zadrozny,2004) is a framework for supervised classification learning with cost functions c(x, y). In
cost-sensitive learning, the expected cost is conventionally used as the objective function
for training to find the best θ. The expected cost with respect to data distribution D over
X × RY is defined ashi
C D (θ) = ED c(x, h(θ)) .
(5)
Unfortunately, since we do not know D, we exploit training examples E instead. N training
examples in E are assumed to be independently sampled from D. Let the i-th training
example in E be e(i) = (x(i) , {c(i) (x(i) , y)}y∈Y ), where x(i) ∈ X is the i-th target object andc(i) (x(i) , y) is the cost of action y ∈ Y for x(i) . Note that the cost of every action is given
for each training example.
The empirical expected cost for the training examples is defined asN

C E (θ) =1 X
c(x(i) , h(θ)).
N

(6)

i=1

From Hoeffding’s inequality (Hoeffding, 1963), the following inequality holds for ² > 0,hi
³ 2N ²2 ´,Pr | C E (θ) − C D (θ) |> ² < 2 exp − 2
Bwhere
B ≥ max c(x, h(θ)) − min c(x, h(θ)).
xx

Since C E (θ) is a good approximation of C D (θ) for sufficiently large N , parameter θ isdetermined so that C E (θ) is minimized (Zadrozny and Elkan, 2001; Geibel et al., 2004; Abeand Zadrozny, 2004).
2.4 Drawback of Mean-Cost Minimization Approach
Suppose that M test data are challenged after training. Since the total cost of M decisions
approaches to M · C D (θ) as M becomes large, minimization of C E (θ) in the training phasesounds reasonable.
However, let us imagine such a situation where M is relatively small so that the above
approximation does not hold, and also the occurrences of huge costs are fatal. For example, if
we have to make important management decisions, several consecutive mistaken judgements
might directly leads to risk of bankruptcy. Also, if the costs follow heavy-tailed distributions
4

Risk-Sensitive Learning via Expected Shortfall Minimization

with infinite variances, the expected cost is highly affected by one big cost. In those cases
where there are chances of unacceptably huge costs occurring even with small probability,
one would like to avoid those risks as far as possible.
Let us consider another example. Assume that two hypotheses h(θ1 ) and h(θ2 ), andboth of them have identical expected costs. h(θ1 ) has a cost distribution with high peakaround its expected cost, and h(θ2 ) has one with a gentle slope and a heavy tail in its highcost area. In this situation, risk aversive investors would apparently prefer h(θ1 ) to h(θ2 ).
The above discussion implies us that minimization of the expectation of c(x, h(θ)) is notenough, and suggests the need to consider the distribution of c(x, h(θ)) and aggressively
avoid the risk of huge costs.

3. Risk-Sensitive Learning
Motivated by the discussion in the previous section, we propose our risk-sensitive learning
approach using a new objective function that aggressively avoids the risk of huge costs, andthen propose a meta-learning algorithm that reduces cost-sensitive learners to risk-sensitive
learners.
3.1 Risk-Sensitive Learning via Expected Shortfall Minimization
3.1.1 Value-at-Risk
In the area of financial engineering, various risk metrics have been studied for decision
making with low risk of huge costs. Probably, one of the most popular risk metrics is valueat-risk (VaR) (Mausser and Rosen, 1998). Value-at-risk is defined to be the β-quantile ofcost distribution for a given constant 0 ≤ β ≤ 1. In other words, it is the minimum of
the top 100(1 − β)% costs. In our problem setting, the value-at-risk αβD (θ) with respect tohypothesis h and data distribution D is defined as (See Figure 1.)
¯
n
h
i
o
¯
αβD (θ) = min α ∈ R ¯ ED I ( c(x, h(θ)) ≥ α ) ≤ 1 − β ,where I(·) is a function that returns 1 when its argument is true, and returns 0 otherwise.
Note that the value-at-risk depends on model parameters θ.
Although value-at-risk is a widely-accepted risk metric, some drawbacks have been
pointed out (Mausser and Rosen, 1998). One problem is that once the cost surpasses
the value-at-risk, it is not cared at all how huge the cost becomes. On the other hand, weare rather interested in suppressing the amount of huge costs itself. Also, value-at-risk has
been shown to be non-convex in most cases theoretically and empirically, which is extremelyinconvenient. If the cost distribution follows a Gaussian distribution, the value-at-risk becomes a linear combination of the mean and the standard deviation of the cost, and theabove problems are resolved. However, the assumption usually does not hold.
3.1.2 Expected Shortfall
Expected shortfall (Artzner et al., 1999), also known as conditional value-at-risk, is attracting attentions as a relatively new risk metric in the field of financial engineering. It
is defined as the expected costs above the value-at-risk, in other words, the expectation of5Kashima

Figure 1: Expected cost, value at risk, and expected shortfall.

the top 100(1 − β)% costs (See Figure 1.), hence it can consider the amount of huge costs.
Moreover, expected shortfall has desirable characteristics such as convexity (Rockafellar andUryasev, 2000). This is exactly the risk metric that we want to employ as the objectivefunction of risk-sensitive learning.
In our problem setting, the expected shortfall φDβ (θ) with respect to hypothesis h anddata distribution D is defined as
h ³
´
i
1
D
φD
(θ)
=
E
I
c(x,
h(θ))
≥
α
(θ)
·c(x,
h(θ))
,
D
β
β
1−β
where αβD (θ) is the value-at-risk defined above, and note that the definition of the expectedshortfall includes value-at-risk.
Since the expected shortfall is the expected costs surpassing αβD (θ), (7) is decomposed
into two terms as
h
i+
1
D
D
φD
(θ)
=
α
(θ)
+
c(x,
h(θ))
−
α
(θ)
E
,
D
β
β
β
1−β
where [x]+ is a function that returns x when x ≥ 0, and returns 0 otherwise.
3.2 Model Estimation
3.2.1 MetaRisk: A Risk-Sensitive Learner to Minimize Expected Shortfall
Let us derive an algorithm to optimize parameter θ. Although (7) is the objective functionthat we want to minimize, we employ the following empirical expected shortfall defined on
training examples E instead of D which is unknown.
i+Xh1c(x(i) , h(θ)) − αβE (θ) ,(1 − β)NNE
φE
β (θ) = αβ (θ) +

(7)

i=1

where αβE (θ) is the value-at-risk for the training examples E,
αβE (θ) = min

n

N
¯ 1 X
o
¯
α∈R¯
I ( c(x(i) , h(θ)) ≥ α )≤ 1 − β .
N
i=1

6

(8)

Risk-Sensitive Learning via Expected Shortfall Minimization

Algorithm: MetaRisk(E, β)[Step:1] Set α̃ := 0.
[Step:2] For the current α̃, find θ0 = argmin C̃α̃E (θ),θ

and set θ := θ0 .
[Step:3] For the current θ. find the empirical
VaR αβE (θ), and set α̃ := αβE (θ).
[Step:4] Continue [Step:2] and [Step:3] until theconvergence of FβE (θ, α̃).
Figure 2: MetaRisk: Risk-sensitive meta-learning algorithm.
Now, if we suppose that αβE (θ) is a known constant α̃ in (7), we only have to minimize
the second term of the second term (7),
i+
1 Xh
(i)
c(x , h(θ)) − α̃.
NNC̃α̃E (θ) :=

(9)

i=1

Note that (9) is convex if c(x(i) , h(θ)) is convex with respect to θ. For the time being, we
assume existence of algorithms to find θ that minimizes (9).
Next, we fix θ, and find the VaR (8) for θ. Since (8) is defined for the training examples
E, it is rewritten asαβE (θ) =nmin

k=1,...,N

(k)

c(x

N
¯ 1 X
³
´
o
¯
, h(θ)) ¯I c(x(i) , h(θ)) ≥ c(x(k) , h(θ)) ≤ 1 − βN
i=1which is equivalent to c(x(k) , h(θ)) where k is the index of the training datum with theb(1 − β)N c-th largest cost by θ. αβE (θ) is naively computed by sorting the costs by θ inO(N log N ), or it can be reduced to O(N ) by using efficient algorithms for finding order
statistics (Cormen et al., 1990).
Based on the above discussion, we propose a risk-sensitive meta-learning algorithm
named MetaRisk (Figure 2)∗ , which minimizes the empirical expected shortfall by exploiting
existing cost-sensitive learners, and by finding the model parameter and the corresponding
value-at-risk alternately.
3.2.2 Optimality and Convergence of MetaRisk
The optimality and convergence of the algorithm (Figure 2) are directly guaranteed by thefollowing theorem by Rockafellar and Uryasev (2000) that shows the convexity of the upperbound of expected shortfall.
Theorem 1 (Rockafellar and Uryasev, 2000, Theorem 1&2) Leti+Xh1c(x(i) , h(θ)) − α ,(1 − β)NN

FβE (θ, α) = α +i=1∗. MetaRisk is named after the cost-sensitive meta-learning algorithm MetaCost (Domingos, 1999).

7

(10)

Kashima

Figure 3: Reduction from cost-insensitive learners to risk-sensitive learners.

thenE
min φEβ (θ) = min Fβ (θ, α).
θ

θ,α

(11)

FβE (θ, α) is convex with respect to α. If (6) is convex with respect ot θ, FβE (θ, α) is also
jointly convex with respect to θ and α. Also,on(12)αβE (θ) = min α ∈ argmin FβE (θ, α)αholds. ¤(11) indicates that minimization of (10) is equivalent to minimization of expected shortfall, and the joint convexity of (10) ensures the gradient-based optimization with respectto θ and α. Moreover, from (12), αβE (θ) is the minimizer of FβE (θ, α) at θ, hence MetaRisk
exactly performs coordinate-wise descent of FβE (θ, α).
3.3 Reduction from Cost-Sensitive/Insensitive Learners to Risk Sensitive
Learners
3.3.1 Recycling Existing Cost-Sensitive Learners
In the previous subsection, we assumed to have learning algorithms to find θ that minimizes(9). However, it is not desired to design from scratch the risk-sensitive versions of existinglearners such as perceptrons, decision trees, or SVMs. In this subsection, we demonstrate approaches that minimize (9) by iteratively calling existing example-dependent cost-sensitive
learners with reweighted costs based on the current hypothesis.
Several example-dependent cost-sensitive learners (Fan et al., 1999; Zadrozny et al.,
2003; Abe and Zadrozny, 2004) realize cost-sensitive learning by weighting or resampling
training examples according to their costs, and feeding them to cost-insensitive learners.
Merging this mechanism with our reduction enables reduction from existing cost-insensitive
learners to risk-sensitive learners (See Figure 3).
8

Risk-Sensitive Learning via Expected Shortfall Minimization

3.3.2 Hypothesis with Alternative Actions
Reduction is relatively easy in the case of alternative actions (1). Paying attentions to
its similarity to (6), we notice that this is the expectation of only costs exceeding αβE (θ).
Also, since actions are exclusive to each other, realized costs are limited to the form of[c(i) (x(i) , y) − α̃]+ + α̃. Therefore, substitutingc̃(i) (x(i) , y) = [c(i) (x(i) , y) − α̃]+(13)

for the original costs, (6) becomesN

C̃α̃E (θ) =1 X (i) (i)c̃ (x , y),
N

(14)

i=1

and this has the same form as the expected cost (6).
The reduction is realized by feeding example-dependent cost-sensitive learners (Geibel
et al., 2004; Zadrozny et al., 2003; Abe and Zadrozny, 2004) with modified training examples
Ẽ, where the i-th example of Ẽ is defined asẽ(i) = (x(i) , {c̄(i) (x(i) , y)}y∈Y ).
3.3.3 Hypothesis with Allocative Actions
Next, let us consider the case where stochastic or allocative decision making by the constrained hypothesis (2) is allowed. (9) is rewritten as
C̃α̃E (θ) =

N hX
X
i=1

h(x(i) , y; θ)c(x(i) , y) − α̃

i+

.

(15)

y

Unlike the case of alternative actions, c(i) (x(i) , h(θ)) depends on a convex combination ofc(i) (x(i) , y), hence simple reweighting like (13) does not work.
A natural choice of the classifiers used as h(x, y; θ) is the exponential family satisfying(2) such as multi-class logistic regression. However, in logistic regression, c(x(i) , h(θ)) is notconvex with respect to its parameters, and even worse, it is a multi-modal function. Therefore, we employ a family of classifiers with which c(x(i) , h(θ)) is linear with respect to θ. (15)is convex with respect to its parameters. In this paper, we use gradient boosting (Friedman,
2001; Rosset and Segal, 2002) as our optimization approach.
In gradient boosting, h(x, y; θ) is represented as a linear combination of T deterministic
hypotheses f1 , . . . , fT ,h(x, y; θ) = hT (x, y; θT ) =TX

wt ft (x, y),t=1

where θt = (w1 , . . . , wt ) are the parameters. Since h(x, y; θ) has to satisfy the stochastic
constraints (2), we needTX

wt = 1, s.t. wt ≥ 0.

t=1

9Kashima

At each boosting round t, suppose that we already have ht−1 , a new weak hypothesis ft issequentially added to ht−1 to construct ht . ht is recursively represented as
ht (x, y; θt ) = (1 − γt )ht−1 (x, y; θt−1 ) + γt ft (x, y)= ht−1 (x, y; θt−1 ) + γt (ft (x, y) − ht−1 (x, y; θt−1 )),where 0 < γt ≤ 1 is a updating parameter at round t, and finally, the parameters θt are
determined asTYwt = γt(1 − γτ ).
τ =t+1Once ft is determined, (15) is convex and piecewise linear with respect to γt . Therefore, γt
is easily found by linear search or linear programming.
In order to find the weak hypothesis ft at the boosting round t, assume that γt is
sufficiently small, then the Taylor series expansion of (15) around ht−1 gives

C̃α̃E =

N hX
X
i=1

+ γt
+

ht−1 (x(i) , y; θt−1 )c(x(i) , y) − α̃yN Xµ ∂
X

i+

hP

(i)
(i)
y ht−1 (x , y; θt−1 )c(x , y) − α̃

i+

(i)

(i)

´¶

ft (x , y) − ht−1 (x , y)∂ ht−1 (x(i) , y; θt−1 )i=1 yO(γt2 ).

³

Neglecting the second or higher order terms, it is enough to find ft that minimized thesecond term,
γt

N
´ ³X
³X
´
X
c(x(i) , y)ft (x(i) , y) .
ht−1 (x(i) , y; θt−1 )c(x(i) , y) > α̃ ·
I
i=1

y

y

As is the case with alternative actions, this term is also minimized by feeding exampledependent cost-sensitive learners with modified training examples Ẽ, where (13) is modifiedas³X´
c̃(x(i) , y) = c(x(i) , y) · I
ht−1 (x(i) , y; θt−1 )c(x(i) , y) > α̃yin the case of allocative actions.

4. Experiments
In order to compare the risk aversion abilities of cost-sensitive learning and risk-sensitive
learning, we conducted two preliminary experiments on a synthetic dataset and a more
realistic dataset for credit administration.
10

Risk-Sensitive Learning via Expected Shortfall Minimization

4.1 Experimental Settings
First, we explain the implementation and datasets used in the experiments. We used thecost-sensitive perceptron algorithm (Geibel et al., 2004) (See also Appendix.) as the hypothesis h(x, y) in the case of alternative actions and the weak hypothesis ft (x, y) in the case of
allocative actions. Especially for the second dataset, we used the kernelized version of thecost-sensitive perceptron with Gaussian kernel (A.4) to incorporate nonlinearity into the
hypothesis. All constant parameters of the perceptron are chosen to have the cost-sensitive
perceptron record the best expected cost, and, they are recycled for the perceptrons usedin risk-sensitive learning† . This is because we would like to observe the effect of switching
the objective function from the cost-sensitive one to the risk-sensitive one. We used thefollowing two datasets.
Synthetic Dataset
In this dataset, there are two dimensional data x = (x1 , x2 ), and two actions y ∈ {+1, −1}.
x1 and x2 are uniformly randomly sampled over −5 ≤ x1 , x2 ≤ 5. The cost for eachaction only depends on x1 as shown in Figure 4. The cost of action +1 is determined by
˙ 1 + 5) (Figure 4, solid line), and the cost of action −1 is determined byc(x, +1) = 0.1(xc(x, −1) = N (0, 0.52 ) (Figure 4, dashed line). In each experiment, 300 data were generated
for training, and 30,000 for test.
Since the expected cost of action −1 is always smaller that that of action +1, it isenough for cost-sensitive learners to have the trivial hypothesis that always take action −1.
However, the costs of action -1 sometimes exceed those of action +1 because of the noise
added, In the area of large x1 , it is needed for risk-sensitive learners to switch the action toaction +1 to suppress the chance of large costs, since the cost of action +1 is more stable
than that of action −1.
Credit Administration
Next, we consider a more realistic application of risk sensitive learning, which is to predictthe credit risks of customers. In this task, the learner must predict whether a particularcustomer can make a loan or not based on his/her profile. Misclassification of a ”goodcustomer” as a ”bad customer” loses the potential interest, and on the contrary, misclassification of a ”bad customer” as a ”good customer” loses most of the loan.
We used the ”German Credit Data Set” (Michie et al., 1994) from the STATLOGPROJECT‡ also used in (Geibel et al., 2004). This dataset includes 700 good customers
and 300 bad customers, and x consists of 20 attributes including sex, age, job, credit history,
purpose, and so on. In our experiment, we used the data included in the dataset whose
attributes are converted into 24 numerical attributes.
Although the original dataset does not have example-dependent costs, we follow the
instruction in (Geibel et al., 2004), and the misclassification cost of a “good customer” as a“bad customer” is defined to be 0.1 · duration· amount, which means 10% interest per year.
12
The average, variance and maximum cost of this type of cost are 6.27, 43.512 , and 78.27,†. For example, the width parameter of the Gaussian kernel (A.4) was determined as σ = 50.
‡. Data are available from UCI Machine Learning repository (Newman et al., 1998).

11

Kashima

Figure 4: Expected cost for each action on the synthetic dataset. Note that Gaussian noise
N (0, 0.52 ) with 0.5 standard deviation is added to c(x, −1).

respectively. Also, the misclassification cost of a “bad customer” as a “good customer” isdefined to be 0.75 × amount, which means 75% of the loan is lost. The average, varianceand maximum cost of this type of cost are 29.54, 78.092 , and 138.18, respectively. The othercosts are defined to be 0.
While the learner with alternative actions makes binary decisions of whether making loan
or not, we can interpret that the learner with allocative actions determines what fractionof the loan is allowed. The realized cost becomes (4) in this case.
4.2 Results
The anticipated result is that the cost-sensitive learner has the smallest expected cost,
and the risk-sensitive learner has a smaller expected shortfall for given β than that of thecost-sensitive learner.
Let us examine the results. Table 4.2 and Table 4.2 show the results for the synthetic
data in the cases of alternative actions and allocative actions, respectively. Similarly, Table
4.2 and Table 4.2 show the results for the German Credit Data Set. The results for thesynthetic data were measured by the averaged values of 5 experiments, and those for theGerman Credit Data Set were measured by 3-fold cross validation (666 training data and334 test data). The columns labeled ‘Cost-Sensitive’ show the results by the cost-sensitive
perceptron. The columns labeled ‘Risk-Sensitive’ show the results by the MetaRisk with
β = 0.80, 0.90, 0.95, 0.99, respectively. Each row shows the values of the expected shortfall
on test data for the corresponding β, and the numbers with ± show the standard errors.
The row at the bottom show the mean cost. The values indicated by boldface show thebest results among each row.
Overall, as we expected, MetaRisk achieves lower expected shortfalls than those of thecost-sensitive perceptron at the corresponding βs at the price of the mean cost.
12

Risk-Sensitive Learning via Expected Shortfall Minimization

Test ES(VaR)
β =0.99
β =0.95β =0.90β =0.80
Mean Cost

CostSensitive
1.30±0.01
0.98±0.01
0.82±0.01
0.63±0.01
0.03±0.01

Risk-Sensitive
β =0.90β =0.95
1.19±0.01
1.11±0.05
0.84±0.01 0.83±0.02
0.71±0.01 0.75±0.02
0.60±0.01
0.67±0.04
0.17±0.01
0.25±0.04

β = 0.80
1.24±0.01
0.91±0.02
0.74±0.02
0.58±0.01
0.10±0.02

β =0.991.10±0.09
0.98±0.02
0.93±0.04
0.85±0.06
0.37±0.01

Table 1: Alternative prediction results for synthetic data.

Test ES(VaR)
β =0.99
β =0.95β =0.90β =0.80
Mean Cost

CostSensitive
1.29±0.00
0.98±0.00
0.82±0.01
0.63±0.01
0.03±0.01

Risk-Sensitive
β =0.90β =0.95
1.12±0.04
1.07±0.06
0.81±0.02 0.80±0.02
0.68±0.01 0.71±0.01
0.58±0.01
0.64±0.02
0.20±0.03
0.26±0.05

β = 0.80
1.20±0.01
0.87±0.01
0.71±0.01
0.56±0.01
0.12±0.01

β =0.99
0.99±0.05
0.87±0.02
0.82±0.05
0.75±0.08
0.37±0.08

Table 2: Allocative prediction results for synthetic data.

Also, allocative actions achieve better results than alternative actions since the former
can realize “portfolios” by combining the costs of two actions. Note that the results forallocative actions are also interpreted as the results from the distribution of the cost expected
for each example when the stochastic selection (2) is performed.
Let us examine the cost distributions of the resulted hypotheses. Figure 5 shows thecost distributions for the synthetic data by MetaRisk with alternative actions and β = 0.95.
Even in such a simple case, the cost distribution shows non-Gaussianity since it is a mixtureof Gaussian distributions and uniform distribution. Generally, the cost distribution easily
becomes non-Gaussian even if each costs follows its own Gaussian distributions, since theresulted cost distribution becomes an infinite mixture of Gaussian distributions.
Figure 6 the cost distributions for the German Credit Data Set by MetaRisk withalternative actions and β = 0.95. The cost are significantly skewed to left, and showsits heavy tail property. In other to confirm the heavy tail property, Figure 7 is double
logarithmic plot of the cost distribution. We can observe linear trend that typical heavy
tail distributions show. In both datasets, traditional mean-variance type approaches are
not appropriate.

5. Related WorkIn this section, we review some works related to risk-sensitive learning, and discuss relations
among them.
13Kashima

Test ES(VaR)
β =0.99
β =0.95β =0.90β =0.80
Mean Cost

CostSensitive
64.47±6.46
34.66±1.1423.58±0.94
14.71±0.78
3.31±0.23

β = 0.80
66.23±6.45
35.69±1.32
23.26±0.51
14.40±0.56
3.52±1.12

Risk-Sensitive
β =0.90β =0.95
67.91±3.95
60.68±7.06
34.45±1.76 30.13±2.30
23.04±1.74 21.15±1.61
14.93±1.1614.33±1.10
3.92±0.32
3.90±0.34

β =0.9955.34±5.16
32.00±3.73
22.89±3.04
15.38±1.99
3.99±0.63

Table 3: Alternative prediction results for the German Credit Data Set Michie et al. (1994)(3-fold cross validation).

Test ES(VaR)
β =0.99
β =0.95β =0.90β =0.80
Mean Cost

CostSensitive
64.47±6.46
34.66±1.1423.58±0.94
14.71±0.78
3.31±0.2

β = 0.80
60.29±6.70
31.48±2.03
20.76±1.36
13.01±0.80
3.98±0.13

Risk-Sensitive
β =0.90β =0.95
57.89±3.71
52.74±1.61
30.03±1.45 26.17±1.27
20.25±1.25 19.21±0.85
13.73±0.70
14.47±0.58
4.68±0.22
5.08±0.17

β =0.9944.29±7.2828.16±3.1922.45±2.31
16.65±1.87
5.55±0.51

Table 4: Allocative prediction results for the German Credit Data Set Michie et al. (1994)(3-fold cross validation).

5.1 Financial Engineering
Decision making theory considering risk aversion originates Markovitz (1952)’s mean-variancemodel, and thereafter, has been actively studied as the portfolio theory in the fields of operations research and financial engineering (Luenberger, 1998). Value-at-Risk (VaR) (Mausser
and Rosen, 1998) is probably the most commonly used metric of risks. The convexity ofthe optimization problem of VaR is guaranteed if the underlying cost distribution follows

Figure 5: Cost distribution at β = 0.95 for the synthetic data shows its non-Gaussianity.

14

Risk-Sensitive Learning via Expected Shortfall Minimization

Figure 6: Cost distribution at β = 0.95 for the German Credit Data shows its nonGaussianity.

Figure 7: Double logarithmic plot of cost distribution at β = 0.95 for the German Credit
Data shows its heavy tail property.

Gaussian distribution, but this assumption does not hold in many real situations. Recently,
a new risk metric called expected shortfall (Artzner et al., 1999) (a.k.a. conditional valueat-risk) is attracting considerable attention since it considers the amount of costs exceeding
VaR, and conveniently, is convex without the Gaussian assumption of the cost distribution.
Most of the works in this field focus on estimating the amount of risks (Mausser andRosen, 1998), or solving mathematical programming for optimal decision making given
models (Rockafellar and Uryasev, 2000), and there are little works from machine learningperspective such as learning risk-avoiding decision rules from examples.
15

Kashima

5.2 Cost-Sensitive Learning
There are many types of costs treated in cost-sensitive learning (Turney, 2000). In earlyworks (Bradford et al., 1998; Domingos, 1999; Elkan, 2001), the cost function is assumed
to be known, and not to depend directly on x, but on classes as latent variables. Recently,
direct minimization of the expected cost (6) in more general situations where the cost function is not known beforehand, and depend on x, has been widely accepted (Fan et al.,
1999; Zadrozny et al., 2003; Geibel et al., 2004; Abe and Zadrozny, 2004; Zadrozny andElkan, 2001). There are three types of approaches in existing cost-sensitive learners, one
is decision-theoretic approaches that perform Bayes-optimal decision making based on estimated class probabilities and cost distributions (Elkan, 2001; Zadrozny and Elkan, 2001),
another approach is the cost-sensitive versions of the existing cost-insensitive learners suchas decision trees (Bradford et al., 1998), perceptrons (Geibel et al., 2004), and support
vector machines (Fumera and Roli, 2002; Geibel et al., 2004), and the other approach ismeta-learners that exploit existing cost-insensitive learners to realize cost-sensitive learning
by reweighting or resampling examples (Domingos, 1999; Fan et al., 1999; Zadrozny et al.,
2003; Geibel et al., 2004; Abe and Zadrozny, 2004). However, all works are oriented toward minimizing the expected cost, and not toward mitigating the risks of huge costs as we
discussed in this paper.
5.3 Risk-Sensitive Reinforcement Learning
After the seminal work by Herger (1994), there are some attempts to incorporate the ideaof risk aversion in the context of reinforcement learning (Neuneier, 1998; Sato et al., 2001).
However, they all remain to focus on minimizing the value-at-risk in limited cases. For example, instead of the expected discounted reward, Herger proposes α-value criterion (Herger,
1994) as the objective function, which is essentially identical to value-at-risk of the discounted reward, and which is not convex. Also, the Bellman equation is presented for the
worst case, that is, β = 1, and it is not possible for general β.
Neuneier (1998) realized soft risk aversion by employing a parameter that emphasizes
actions whose rewards are less than expected, but this parameter is rather intuitive, anddoes not have clear correspondence to the risk metric to be optimized.
The above methods are both designed as the variants of Q-learning, hence do not aim
directly to optimize the risk metrics, but aim to estimate the expected discounted reward
function accurately.
On the other hand, Sato et al. (2001) propose an approach that directly optimizes
an objective function defined as a linear combination of the mean and the variance of
discounted reward. This is based on the assumption of the mean-variance model where the
distribution of the discounted reward follows Gaussian distribution, which does not hold in
most situations. Moreover, in the case of alternative actions, the objective function is notconvex even under the assumption.
5.4 Robust Statistics
Robust statistics (Hampel et al., 1986; Rousseeuw and Leroy, 1987) aims to robust estimation of models by eliminating influence of outliers, which is an antithetical to our
16Risk-Sensitive Learning via Expected Shortfall Minimizationrisk-sensitive approach. There are some classes of robust estimators, one of which is Lestimator defined as a linear combination of order statistics. For example, least trimmed
square (Rousseeuw and Leroy, 1987) is an instance of L-estimator which minimizes the sumof squared losses less than some quantile by trimming off the largest losses. The idea oftrimmed estimator has been generalized for general loss functions (Cizek, 2004).
By definition, minimization of expected shortfall is identical to minimization of the losses
above β-quantile. Our risk-sensitive approach goes against the trimmed estimators in thatsense. In contrast to cutting off outliers to robustify estimators, it makes the most of theoutliers, and aggressively “overfits” to them to avoid potential risks. In addition, trimmed
estimation is not usually convex optimization problems while minimizing expected shortfallis.

6. Conclusion and Future Works
In this paper, we tackled cost-sensitive learning problem from the perspective of risk aversion, and proposed to minimize not the expected cost but the risk metric called expectedshortfall which is being widely accepted in the area of financial engineering. Its definitionand characteristics such as convexity play key roles to elegantly realize risk aversion, which
has not been discussed in the area of data mining. The proposed method is a meta-learningalgorithm that exploits any existing cost-sensitive learner to solve risk-sensitive learning
problems with alternative or allocative actions.
Although we focused on supervised classification problems in this paper, this idea isalso applicable to a wide class of data mining problems, such as clustering, regression, andso on. Also, from another perspective, the cost function can be substituted by generalloss functions such as log-likelihood. This indicates that the meta-learning framework weproposed in this paper has possibilities of converting existing machine learning algorithms
to have large margin and sparsity properties by enforcing them to focus on difficult examples
just like boosting and suport vector machines.
Finally, we conclude this paper with mentioning some possible future works. Although
we used the expected shortfall in a stand-alone manner in this paper, there might be cases
where one wants not only to minimize risks of large costs, but also to minimize the expected
cost at the same time. Actually, such idea is widely accepted in portfolio theory thatmaximizes expected returns while suppressing risks. Similarly, we should incorporate theexpected cost into the objective function in real applications. One way to do this is toemploy a linear combination of the expected cost (6) and the risk metric (7) as the objectivefunction,
ηC E (θ) + (1 − η)φDβ (θ),
where 0 ≤ η ≤ is a mixing constant. It is easily confirmed that this objective function also
has convexity, and MetaRisk can be extended to afford this objective function.
Another possibility is to develop tailor-made algorithms for risk-sensitive learning thatminimize (10) with respect to both θ and α at the same time, while MetaRisk optimizes
θ and α alternately in this paper. In the case of allocative actions, we assumed a linear
constraint (4) on the cost of action portfolio, and this made it possible to take the gradientboosting approach. However, this assumption might be too strong in some applications.
As Theorem 1 assures, expected shortfall is convex if we make a more general assumption
17

Kashimathat c(x, h(θ)) is convex. Approaches from direct convex optimization might be pursued
in such cases. From the viewpoint of computational efficiency, perceptron learning that we
employed in the experiment is incremental with respect to θ, but MetaRisk itself is a batchalgorithm. This is not efficient for huge data, and thoroughly on-line type algorithms aredesirable.
The other direction of the future research is to loosen the assumption on the training data. The assumption that we know costs for all actions seems to be too strong.
There should be many cases where we know the cost for the action we really took, forexample, data on direct marketing usually has the results only for the actions that wereactually taken. This kind of situations might be modeled as an one-benefit learning problem (Zadrozny, 2005), or similarly, an associative reinforcement learning problem (Kaelbling, 1994; Williams, 1992). More generally, reinforcement learning with the expectedshortfall of discounted reward might be seen beyond them.

Acknowledgments
The author thanks the colleagues of IBM Tokyo Research Laboratory, especially, Rikiya
Takahashi for introducing me valuable information on financial engineering, Tsuyoshi Idè,
Takayuki Osogami, Yuta Tsuboi, and Ryo Sugihara for fruitful discussion. The author also
thanks Koji Tsuda of AIST-CBRC for the highly suggestive comments.

References
Naoki Abe and Bianca Zadrozny. An iterative method for multi-class cost-sensitive learning.
In Proceedings of ACM SIGKDD Conference, 2004.
Philippe Artzner, Freddy Delbaen, Jean-Marc Eber, and David Heath. Coherent measuresof risk. Mathematical Finance, 9:203–228, 1999.
Jeffrey P. Bradford, Clayton Kunz, Ron Kohavi, Cliff Brunk, and Carla E. Brodley. Pruning
decision trees with misclassification costs. In Proceedings of the 9th European Conference
on Machine Learning (ECML), 1998.
Pavel Cizek. General trimmed estimation: Robust approach to nonlinear and limited dependent models. Technical Report 2004-1300, CentER Discussion Paper, 2004.
Thomas C. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms.
MIT Press, Cambridge, MA, 1990.
Pedro Domingos. MetaCost: A general method for making classifier cost sensitive. In Proceedings of the 5th International Conference on Knowledge Discovery and Data Mining,
pages 155–164, 1999.
Charles Elkan. The foundations of cost-sensitive learning. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI), pages 973–978, 2001.
18

Risk-Sensitive Learning via Expected Shortfall Minimization

Wei Fan, Salvatore J. Stolfo, Junxin Zhang, and Philip K. Chan. AdaCost: Missclassification cost sensitive boosting. In Proceedings of the 16th International Conference on
Machine Learning (ICML), pages 97–105, 1999.
Jerome H. Friedman. Greegy function approximation: A gradient boosting machine. Annalsof Statistics, 29(5), 2001.
Giorgio Fumera and Fabio Roli. Cost-sensitive learning in support vector machines. In VIII
Convegno Associazione Italiana per L’Intelligenza Artificiale, 2002.
Peter Geibel, U. Bredford, and Fritz Wysotzki. Perceptron and SVM learning with generalized cost models. Intelligent Data Analysis, 8(5):439–455, 2004.
Frank R. Hampel, Elvezio M. Ronchetti, Peter J. Rousseeuw, and Werner A. Stahel. Robust
Statistics: The Approach Based on Influence Functions. John Wiley and Sons, New York,1986.
Matthias Herger. Considering of risk in reinforcement learning. In Proceedings of the 11th
International Conference on Machine Learning (ICML), pages 105–111, 1994.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journalof the American Statistical Association, 58:13–30, 1963.
Leslie Pack Kaelbling. Associative reinforcement learning: Function in k-DNF. Machine
Learning, 15(3):279–298, 1994.
David G. Luenberger. Investment Science. Oxford University Press, 1998.
Harry M. Markovitz. Portfolio selection. Journal of Finance, 7(1):77–91, 1952.
Helmut Mausser and Dan Rosen. Beyond VaR: From measuring risk to managing risk.
ALGO Research Quarterly, 1(2):5–20, 1998.
Donald Michie, D. J. Spiegelhalter, and C. C. Taylor. Machine Learning, Neural andStatistical Classification. Ellis Horwood, 1994.
Ralph Neuneier. Risk sensitive reinforcement learning. In Advances in Neural Information
Processing Systems 11, 1998.
D. J. Newman, S. Hettich, C.L. Blake, and C.J. Merz. UCI repository of machine learning
databases, 1998. URL http://www.ics.uci.edu/∼mlearn/MLRepository.html.
R. Tyrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk.
Journal of Risk, 2(3):21–41, 2000.
Saharon Rosset and Eran Segal. Boosting density estimation. In Advances in Neural
Information Processing Systems 15, 2002.
Peter J. Rousseeuw and Annick M. Leroy. Robust Regression and Outlier Detection. John
Wiley and Sons, New York, 1987.
19

Kashima

Makoto Sato, Hajime Kimura, and Shigenobu Kobayashi. TD algorithm for the varianceof return and mean-variance reinforcement learning [in Japanese]. Journal of JapaneseSociety of Artificial Intelligence, 16(3):353–362, 2001.
Peter Turney. Types of cost in inductive concept learning. In Proceedings of Workshop
on Cost-Sensitive Learning (WSCL) at the 17th International Conference on Machine
Learning (ICML), pages 15–21, 2000.
Ronald J. Williams. Simple statistical gradient following algorithms for connectionist reinforcement learning. Machine Learning, 8(3):229–256, 1992.
Bianca Zadrozny. One-benefit learning: cost-sensitive learning with restricted cost information. In Proceedings of the 1st International Workshop on Utility-based Data Mining(UDBM), pages 53–58, 2005.
Bianca Zadrozny and Charles Elkan. Learning and making decisions when costs and probabilities are both unknown. In Proceedings of ACM SIGKDD Conference, 2001.
Bianca Zadrozny, John Langford, and Naoki Abe. Cost-sensitive learning by costproportionate example weighting. In Proceedings of the 3rd International Conferenceon Data Mining (ICDM), pages 435–442, 2003.

Appendix: Cost-Sensitive Perceptron (Geibel et al., 2004)
In order to make this paper self-contained, we briefly review the cost-sensitive perceptron (Geibel et al., 2004) employed in the experiment.
Suppose that we have two actions Y = {+1, −1}. The decision rule (1) is defined as thesign of hθ, xi,³´ŷ = sign hθ, xi
Note that we suppose that the feature vector x has a constant element for incorporating
the bias like x> = (x0 > , 1), where x0 indicates the original feature vector.
In terms of hypothesis h, the hypothesis of the cost-sensitive perceptron is representedash(x, y; θ) = yhθ, xi.
The objective function (6) is written asN

1 X
C (θ) =c(x(i) , +1)I(ŷ = 1) + c(x(i) , −1)I(ŷ = −1).
N
E

i=1

Without loss of generality, we can suppose either of c(x(i) , +1) and c(x(i) , −1) is zero bysubtracting min{c(x(i) , +1), c(x(i) , −1)} from both costs, which does not effect the minimizerof C E (θ) at all.
20

Risk-Sensitive Learning via Expected Shortfall Minimization

Instead of the original objective function, the cost-sensitive perceptron employs thefollowing convex objective function,hi+
1 X
c(x(i) , ŷ) ŷhθ, x(i) i.
N
NC̄ E (θ) =

(A.1)

i=1

Intuitively, the cost of each action is multiplied by the confidence level of the current hypothesis, |hθ, x(i) i|. Since (A.1) has a trivial solution θ = 0, margin ² > 0 is employed foravoiding this.
N
h
i+
1 X X
E
C̄ (θ) =c(x(i) , y) yhθ, x(i) i + ²(A.2)
N
i=1 y∈{+1,−1}Fortunately, the scale of ² does not influence the final solution at all.
Taking the subgradient of (A.2),N

1 X∂ C̄ E (θ)
=
∂θ
N

X

c(x(i) , y)yx(i) I ( yhθ, x(i) i + ² > 0 ),i=1 y∈{+1,−1}hence the incremental rules for on-line update of θ become• If hθ, x(i) i > −², then θ ← θ − γt c(x(i) , +1)x(i) ,• If hθ, x(i) i < ², then θ ← θ + γt c(x(i) , −1)x(i) ,where the learning
P∞the 2conditions for stochastic approximation such as
P∞ rates γt satisfy
limt→∞ γt = 0, t=0 γt = ∞, and t=0 γt < ∞.
The dual version of the cost-sensitive perceptron is derived by representing the parameters as a linear combination of feature vectors,θ=NXa(j) x(j) ,j=1

where a(i) s are the dual parameters of θ. Replacing all the parameters by the dual parameters, the dual decision rule becomesŷ = signN³X´
a(j) hx(j) , xi ,j=1

and similarly, the incremental rules become
• If
• If

PN

(j) (j)(i)(i) ← a(i) − γ c(x(i) , +1)t
j=1 a hx , x i > −², then aPN(j) (j)(i)(i) ← a(i) + γ c(x(i) , −1) .
t
j=1 a hx , x i < ², then a

21

(A.3)

Kashima

The inner product hx, x0 i can be replaced by a kernel function,
K(x, x0 ) = hx, x0 i,
and (A.3) becomesŷ = signN³X

a(j) K(x(j) , x)

´
.

j=1

One possible choice of the kernel function is the Gaussian kernel,¶µk x − x0 k 2
0,K(x, x ) = exp −σ2where σ is a width parameter.

22(A.4)