Continuous Target Variable Prediction with Augmented Interval Pattern Structures: Lazy Algorithm

Abstract

Pattern structures are known to provide a tool for predictive modeling and classi cation. However, in order to generate classi cation rules concept lattice should be built. This procedure may take much time and resources. In previous work it was shown that it is possible to escape the problem with so-called lazy associative classi cation algorithm. It does not require lattice construction and it is applicable to classi cation problems such as credit scoring. In this paper we adjust this method to the case of continuous target variable, i.e. regression problem, and apply it to recovery rates forecasting. We perform parameters tuning, assess the accuracy of the algorithm based on the bank data and compare it to the models adopted in the bank system and other benchmarks.

Introduction

Banks and nancial institutions take and mitigate credit risk on daily basis. Credit risk commonly has the biggest contribution to the bank losses compared to other types of risks such as market, operational and liquidity risks [ 10 ]. The key to successful risk-management is to adequately assess the possibility of credit losses and potential amount of the loans that is going to be recovered in case of default. The problem of accurate risk assessment is not only important for an individual bank, but it is also crucial for the banking system as a whole. The problem is so vital that banking industry is strictly regulated by central banks and Basel supervising committee, which even pose certain requirements for predictive models that are used by banks [ 17 ]. Some predictive models, socalled "black-box" models provide good results that are hard to interprete. So, the major feature of risk management practice is that, regardless of the model accuracy, it must not be the black box. That is why methods such as neural networks and SVM classi ers did not earn much trust within the banking community [ 4 ]. At the same time, the more accurate the model is, the less capital charge the bank is going to have. So, banks prefer accurate models that provide interpretable decision-making. Therefore, FCA-based algorithms seem to be helpful since they rely on concepts that have obvious interpretation. The intent of a concept can be interpreted as a set of rules that is supported by the extent of the concept. In previous work it was shown that FCA-based interval pattern structures methods are applicable to credit scoring which represents the classi cation problem with binary target variable [ 14,16 ]. Classifying credit applicants into good and potentially delinquent clients is the rst part of credit risk assessment. The second part is to estimate recovery rate in case of default, i.e. the proportion of the loan that is going to be collected by the bank [ 10 ]. As far as recovery rates prediction is concerned, it implies continuous target variable. In this paper, we will adopt the lazy classi cation algorithm based on interval pattern structures to the case of continuous target variable, i.e. we will introduce modi ed lazy regression algorithm (MLRA). The paper is structured as follows: Section 2 provides basic formal concept analysis de nitions. Section 3 describes the architecture of MLRA and its parameters. Section 4 describes the data used for algorithm accuracy evaluation and comparison with benchmarks such as random forests. Section 5 concludes the paper. Finally, we attach a pseudo-code for the algorithm in Appendix. 2

Main De nitions

First, we recall some standard de nitions related to FCA, see e.g. [ 1,2 ].

Let G be a set (of objects), let (D, u) be a meet-semi-lattice (of all possible object descriptions) and let : G ! D be a mapping. Then (G, D , ), where D =(D, u), is called a pattern structure [ 1 ], provided that the set (G) := f (g)|g 2 Gg generates a complete subsemilattice (D , u) of (D, u), i.e., every subset X of (G) has an in mum uX in (D, u). Elements of D are called patterns and are naturally ordered by subsumption relation v: given c, d 2 D one has c v d $ c u d = c. Operation u is also called a similarity operation. A pattern structure (G; D; ) gives rise to the following derivation operators ( ) :

A = l (g) g2A

for A 2 G; d = fg 2 G j d v (g)g for d 2 (D; u):

These operators form a Galois connection between the powerset of G and (D; u). The pairs (A; d) satisfying A G, d 2 D, A = d, and A = d are called pattern concepts of (G,D, ), with pattern extent A and pattern intent d. Operator ( ) is an algebraical closure operator on patterns, since it is idempotent, extensive, and monotone [ 1 ]. In case of credit scoring we work with pattern structures on intervals as soon as a typical object-attribute data table is not binary, but has many-valued attributes. Instead of binarizing (scaling) data, one can directly work with many-valued attributes by applying interval pattern structure. For two intervals [a1; b1] and [a2; b2], with a1; b1; a2; b2 2 R the meet operation is de ned as [ 14 ]:

[a1; b1] u [a2; b2] = [min(a1; a2); max(b1; b2)]

The concept-based learning model for standard object-attribute representation (i.e., formal contexts) is naturally extended to pattern structures, when we have a binary target attribute, i.e. a set of positive examples G+ and a set of negative examples G [ 16 ].

However, what should we do when the target attribute is not a class label but a continuous variable? For that case we augment the de nition of interval pattern structure by equipping it with additional feature h.

Augmented interval pattern structures

Let us de ne an augmented interval pattern structure as a quadruple (G, D , , h), where the description d consists of two elements dx and dy (dy is an interval for target attribute y 2 R and dx is a vector of intervals for explanatory attributes x which are supposed to predict the target attribute y), : G ! D and h 2 H, where H is a family of density distribution functions for target attribute y, i.e. R +1 h(s)ds = 1. We will also use notation x and y to distinguish 1 between descriptions containing explanatory attributes and target attribute correspondingly. The meet operation de nition is left unchanged.

Suppose, we have an arbitrary set of objects A0 G, i.e. A0 = fg1; g2; :::; gJ g, (gj ) = f x; yg = f[x1j ; x1j ]; :::; [xMj ; xMj ]; [yj ; yj ]g, for j = 1; :::; J , where M is number of explanatory attributes. Then we de ne the derivation operator in the following way

A0 = (d0; h0) where d0 = fdx0; dy0g, and dx0 = x(g1) u ::: u x(gJ ) and target attribute description dy0 = y(g1)u:::u y(gJ ) which is in fact a single interval [ymin; ymax] and h0 : dy0 ! [0; 1]. The h0 is in e ect a target attribute density distribution function based on observations of A0, which we describe below. Let 0; :::; K be a partition of dy0 and 0 = ymin; K = ymax and i = ymaxKymin = i i 1; i = 1; :::; K. Then: h([ i 1; i)) = jfg 2 Aj[ i 1; i) v y(g)gj ; 8i = 1; :::; K

A j j Thus, h is a density function of target attribute y values of objects in A. The derivation operator on descriptions returns the set of objects with description subsuming the description dx0 whatever target description dy0 and density function h are:

A0 = (d0; h0) d=ef dx0 = A1 where A1 = fg Gjdx0 v x(g)g. Finally, A1 = (d1; h1). Note, that d1 = fdx0; dy1g, i.e. only target attribute description dy is updated, so does h density function, while the explanatory variables description dx0 remains the same.

In order to approach target attribute prediction problem it will be useful to de ne -weak premises with allowed dropout. An h-augmented interval pattern d 2 D is called an -weak premise with allowed !-dropout i : jfg 2 A dmin j y A j j where d = (dx; dy), dy is a single interval [dymin; dymax] for target attribute y A = dx, and m is a median of density function h which re ects the distribution of target attribute within the interval dy based on objects from A. Parameter controls the frequency of hypothesis falsi cations and parameter ! controls the magnitude of falsi cation, i.e. how dramatically it is falsi cated. In our case the magnitude is evaluated as the times the y(g) dymax is larger than dymax m if y(g) > dymax or the times the y(g) dymin is larger than m dymin if y(g) < dymin Note, that in case when ! = 0 we apply the strictest criterion to consider a hypothesis as falsi cated: jfg 2 A dmin j y y(g)

dymaxgj , jfg 2 Ajdy 6v y(g)gj

A j j

Lazy predictive algorithm attribute with continuous target 3

1

Assume we have a set of objects G and numerical context with a set of explanatory attributes x1; :::; xM and target attribute y. In contrast to classi cation problem the context is not divided into positive and negative examples as soon as y take numerical values. Now, suppose we receive a test object gt with observable attributes x, but with unknown value of target attribute y. Is there a way to predict y using interval pattern structures approach? Indeed, there is, and we are going to describe it below and compare the accuracy results with some benchmarks.

The rst stage of algorithm is mining -weak premises with allowed !dropout, the second is to perform prediction for test object gt based on the mined premises. Let us start by choosing subsample size parameter which is the number of objects being randomly extracted from G. Then we specify and ! parameters that control for "anti-support" in terms of both frequency and magnitude. Upon randomly extracting some objects A0 = fg1; :::; gK g we compute following pattern d0 = (g1) u ::: u (gK ) u (gt) and density distribution function h0 for target attribute values. If d0 is an - weak premise with allowed !-dropout then it is added to the set of premises that will be used for prediction later. Together with the pattern it is necessary to store the density function h. But which of h0, h1 or other we have to use?

Here we introduce another parameter of the algorithm which is called "capped ". Capped is a boolean value, and if true then the range for target attribute dy1 in d0 is truncated to dy0 and corresponding density function is h1 calculated on the truncated set of target values. If capped parameter is false, then we add dy1 and calculate the density function based on all target values that fell into dy1 based on objects from d0. The whole procedure is repeated many times and the number of iterations parameter controls for that.

Having nished with premises mining, we move on to the next stage which is building up a prediction for target attribute based on mined premises. In our case, the resulting prediction was de ned by mixture of distributions from all premises. In practice all target attribute values stored within premises were put together to form a nal distribution. Finally, we tried both an average and a median of that distribution as the prediction for target attribute. Such approach takes into accout di erent support of the premises as soon as premises with greater number of objects will contribute more.

However, one can argue that premises are di erent in sense of anti-support and deviation in target attribute values. Indeed, we would put more weight to the prediction based on premises with narrow range of target attribute values and the ones with less falsifying examples from set G. Therefore, we added target values to the nal distributions with di erent weights, thus both weighted average and weighted median were used as forecast.

We introduced two boolean parameters which controlled the weightening schemes. The rst parameter is account for anti-support and the second is penalty for high deviation. When account for anti-support parameter is true, then the target values y(g) of objects g 2 A with the premise d are given weight according to the anti-support of that premise: wa = jfg 2 A dmin j y !(m When penalty for high deviation is true, then the weight is decreased with the higher deviation in the target attribute values: where ( y(g)) is standard deviation of target attribute values. If the parameters values are false then the weigths are equal to one. The nal weight for the target attribute value of the object g, which will be contributed to aggregate distribution used for prediction, is de ned as product of the two weights: w(g) = wa wpen Finally, suppose that P is a set of mined -weak premises with allowed !dropout. The prediction for target attribute y of a test object gt can be based on weighted average:

P In case where P is an empty set, the prediction is average or median of all target attribute values in G, i.e. the prediction is based on "naive" model. 4

Data and experiments

The data we used for the computation represent a pool of delinquent corporate clients loans, which were expected to be restructured. The process of restructuring is started at the early stage when the client shows the rst signs of insolvency. At that very moment a bank chooses either to execute default strategy, when the court processes are launched and any disposable collateral is displayed for sale, or to execute restructuring strategy, when the funding conditions are being revisited usually resulting in a longer credit period. In case of corporate clients banks usually do not want to go to extremes right from the start as soon as court launch and collateral sales imply costs and spending time resources. Also, the bank would prefer to maintain relations with the client if nancial distress is temporary. So, the decision whether to launch default strategy or not is based to the greater extent on the recovery expectations. This makes the problem of recovery prediction crucial for banking decision making. Recovery rate is a number between zero and one which re ects the share of the current exposure which the client is going to payback on some time horizon. If recovery rate expectation is at high level, the bank would prefer restructuring and court launch otherwise.

In this paper we use nancial data from balance sheets and pro t and loss statements of 612 corporate clients of a top-10 Russian bank. Among others factors we used assets-to-liabilities ratio, debt-to-equity ratio, earnings before taxes and interest payments, return on assets etc, resuting. These clients were assessed at the time of early insolvency signals and the resulting recovery rate was collected.

The data was randomly divided into two parts with 70% of observations in one part and 30% in the other. The bigger part was used as a context with known target attribute for the lazy algorithm and 30% was used as a test set to evaluate predictions and their accuracy. The same data partition was used to run random forests with di erent tunings with 70% part used as a training set and the other as test set. For random forests there were three parameters tuned by grid search which are minimum nodesize, number of trees and number of feasible variables.

The accuracy of predictions were evaluated in terms of mean absolute deviation (MAD): where yi is a target attribute (recovery rate) for i-th client in the test set and y^i is prediction.

The random forests were run with following parameters grid: minimum nodesize ranging from 30 to 100 with increment 10, number of trees ranging took values 10, 30, 50 and 100, and number of feasible variables from ranging from 5 to 45 with increment of 5.

As far as lazy algorithm is concerned, we tuned seven parameters, four of them were continuous and three were boolean. Subsample size took following values: 0.01, 0.02, 0.03, 0.04, 0.05, 0.1. Number of iterations : 100, 500, 1000, 2000. Alpha threshold : 0, 0.05, 0.01, 0.015, 0.02. Allowed dropout : 0, 0.1, 0.5, 1, 1.5.

For each combination of parameters we calculated MAD for the test set and in fact that produced metadata for the analysis. E ectively we obtained MAD distributions, which at the rst step helped us to choose in favour of forecast based on weighted median forecast rather than weighted average as soon as MAD distributions for the latter took dramatically higher values which are, of course, undesirable.

When building new algorithm one has some intuition about it mechanism and we performed regression analysis of algorithm accuracy versus parameters values to check that intuition. Also, the analysis was important to determine better parameters tuning and explain variation in accuracy of the predictions. The results of regression are presented below: Coe cients Estimate Std.Error t p-value (Intercept) 0,3288 0,0006 519,4 0,0000 Subsample size 0,0155 0,0031 4,940 0,0000 Number of iterations -0,0004 0,0000 -18,05 0,0000 Alpha-threshold -0,0457 0,0270 -1,695 0,0903 Allowed dropout -0,0011 0,0004 -2,975 0,0030 Capped -0,0022 0,0004 -5,401 0,0000 Account for anti-support 0,0002 0,0004 0,624 0,5329

Penalty for high deviation 0,0010 0,0004 2,433 0,0150

We see that increasing number of iterations, allowing dropouts and using capped improve algorithm performance as soon as the coe cients are negative and signi cant: overall error of prediction decreases as those factors increase. Surprisingly, adjusting account for anti-support and penalty for high deviation parameters do not show signi cant improvement in accuracy. Also, we expected that there are some non-linear dependencies between MAD and parameter values as soon as, intuitively, there has to be an optimal subsample size of randomly extracted objects. Therefore, we support the regression output with one-factor scatter plots with average MAD across all other iterations versus each parameter:

As expected, there is a local minimum for the subsample size being extracted from G. It is quite natural because as the subsample size grows, the intersection of the subsample with a test object results in a generic description, which is very likely to be falsi ed by objects with target attribute value out of the premise description target range.

According to performed grid search the range with the lowest MAD (0.247 0.290) on the test sample is achieved in following parameter area: alpha-threshold = 1.5%, number of iterations = 10, subsample size = 1%, allowed dropout = 0.1. The result was compared to benchmarks represented by random forest tunings. 5

Conclusion

Formal concept analysis o ers attractive instruments to extract knowledge from data as soon as intents of concepts can be considered as associative rules. FCA-based algorithms are suitable for predictive modeling in areas where model interpretation clarity is of great priority. However, in previous work only classication problems were considered, while continuous target attribute prediction, i.e. regression problem, was out of focus. In this paper, we adjusted the lazy algorithm [ 3,16 ], so that it can perform continuous predictions. The adjustment required a new de nition of an augmented interval pattern structure. In e ect, the adjusted algorithm mines the premises (with target attribute expected distribution) that are relevant to test object and then prediction is performed based on the target attribute distribution, e.g. based on the median of the distribution.

We applied the algorithm to delinquent corporate clients loans in order to predict the recovery rate for each loan. The data we used comes from the pilot project with one of the top-10 banks in Russia. Mean absolute deviation was chosen as accuracy metric of the algorithm. We performed simple grid search by running the algorithm with di erent parameter values and chose the tuning with the lowest value of the metric. The classi cation accuracy of the algorithm was compared to some benchamrks represented by random forests, as soon as their predictions are based on combination of simple rules, too. The proposed modi ed lazy regression algorithm showed comparable quality in the greater number of runs and in certain parameters area it outperformed random forests. However, it has to be mentioned that the number of parameters is greater in our algorithm what, in e ect, results in greater algorithm complexity and greater degrees of freedom. As an area for further research, one can consider keeping the density function h not only for target attribute in premises, but also make use of those density functions for explanatory attributes as well. It can be expected, that if the premises are mined not only based on allowed dropout and alpha-threshold parameters, but also based on some properties of attributes distribution, then the premises will be more relevant for the test objects and will produce more accurate predictions for target attribute.

Pp2P Pg2Ap y(g) w(g)

Pp2P Pg2Ap w(g) If P is empty, then calculate the median for target attributes of all g 2 G (naive prediction).

References

1. B. Ganter and S.O. Kuznetsov: Pattern structures and their projections, in Conceptual Structures: Broadening the Base, Harry Delugach and Gerd Stumme, Eds., vol. 2120 of Lecture Notes in Computer Science, pp. 129 { 142 . Springer, Berlin/Heidelberg, 2001 .

2. B. Ganter , R. Wille: Formal Concept Analysis: Mathematical Foundations . Springer, Berlin, 1999 .

3. S.O. Kuznetsov : Scalable knowledge discovery in complex data with pattern structures , in PReMI, Pradipta Maji, Ashish Ghosh, M. Narasimha Murty , Kuntal Ghosh, and Sankar K. Pal, Eds., vol. 8251 of Lecture Notes in Computer Science, pp. 30 { 39 , Springer, 2013 .

4. L. Thomas , D. Edelman , J. Crook: Credit Scoring and Its Applications , Monographs on Mathematical Modeling and Computation , SIAM: Philadelphia, pp. 107 { 117 , 2002 .

5. N. Siddiqi: Credit Risk Scorecards: Developing and Implementing Intelligent Credit Scoring , WILEY, ISBN: 978-0-471-75451-0 , 2005 .

6. B. Baesens , T.V. Gestel , S. Viaene , M. Stepanova , J. Suykens: Benchmarking stateof-the-art classi cation algorithms for credit scoring , Journal of the Operational Research Society 54 ( 6 ), 627 - 635 , 2003 .

7. A. Ghodselahi : A Hybrid Support Vector Machine Ensemble Model for Credit Scoring , International Journal of Computer Applications ( 0975 { 8887), Volume 17 { No. 5 , 2011 .

8. L. Yu , S. Wang and K.K. Lai : An intelligent agent-based fuzzy group decision making model for nancial multicriteria decision support: the case of credit scoring . European journal of operational research . vol. 195 . pp. 942 - 959 , 2009 .

9. T.V. Gestel , B. Baesens , J.A. Suykens , Poel V.D.V., B. : Bayesian kernel based classi cation for nancial distress detection . European journal of operational research . vol. 172 . pp. 979 - 1003 , 2006 .

10. P. Ravi and V. Ravi: Bankruptcy Prediction in Banks and Firms via Statistical and Intelligent Techniques-A Review , European Journal of Operational Research , Vol. 180 , No. 1 , pp. 1 - 28 , 2007

11. S.O. Kuznetsov and M.V. Samokhin : Learning closed sets of labeled graphs for chemical applications ., in ILP , Stefan Kramer and Bernhard Pfahringer, Eds., vol. 3625 of Lecture Notes in Computer Science, pp. 190 { 208 , Springer, 2005

12. SAS Institute Inc., Developing Credit Scorecards Using Credit Scoring for SAS R Enterprise MinerTM 12 .1, Cary , NC: SAS Institute Inc., 2012 .

13. R.R. Hocking : The Analysis and Selection of Variables in Linear Regression , Biometrics, 32 , 1976 .

14. M. Kaytoue , S.O. Kuznetsov , A. Napoli , and S. Duplessis: Mining gene expression data with pattern structures in formal concept analysis , Information Sciences , vol. 181 , no. 10 , pp. 1989 { 2001 , 2011 .

15. A. Veloso and W. Meira , Jr.: Demand-Driven Associative Classi cation ., Springer, 2011 .

16. A. Masyutin , Y. Kashnitsky , S.O. Kuznetsov: Lazy Classi cation with Interval Pattern Structures: Application to Credit Scoring , In: Proc. 4th International Workshop "What can FCA do for Arti cial Intelligence?" (FCA4AI 2015 ), pp. 43 - 54 , 2015 .

17. E.I. Altman , A. Resti and A. Sironi: The link between default and recovery rates: e ects on the procyclicality of regulatory capital ratios" , BIS Working Papers No 113, Monetary and Economic Department , 2002 .

Algorithm 1 Lazy Regression by Sub-Samples with Continuous Target Attribute

P { a set of premises, i.e. associative rules produced for the test object gt. P can be empty. for iter from 1 to num:iter do A0=random.sample(G,size=sub:smpl jGj) | mine - weak premises with !- allowed dropout. d0 = x(g1) u ::: u x(gs) u x(gt), gs 2 A08s Compute empirical density function h0 for d0y. A1 = d0 if 1 jfg2A1jd0ymin !(m d0ymin)jA1yj(g) d0ymax+!(d0ymax m)gj then Update empirical density function h0 to h1 based on new values of target attribute in A1. Add (d0; h1) to the set P of - weak premises with !-allowed dropout. else Do nothing end if end for De ne weighting scheme wa; wpen. Calculate the median for mixture of distribution functions hp based on dpy, 8p 2 P .