Maciej Zięba
email: maciej.zieba@pwr.wroc.pl

Jerzy Świątek
email: jerzy.swiatek@pwr.wroc.pl

Ensemble Classifier for Solving Credit Scoring Problems

Keywords: credit scoring, ensemble classifier, imbalanced data, cost-sensitive learning

The goal of this paper is to propose an ensemble classification method for the credit assignment problem. The idea of the proposed method is based on switching class labels techniques. An application of such techniques allows solving two typical data mining problems: a predicament of imbalanced dataset, and an issue of asymmetric cost matrix. The performance of the proposed solution is evaluated on German Credits dataset.

Introduction

The insecure financial condition of many institutions in UE and in the USA caused the growing popularity of decision making solutions in bank and financial sectors. Especially accurate decisions about credit assignment are essential for the banks to prevent them from the poor economic condition. Usually, experts from the financial segments are responsible for making credit assignment decisions what generates high costs of maintaining customers. The process of assigning credit status can be automated using methods and algorithms from data mining field. The decision models and their underlying techniques that aid lenders in the granting of consumer credit are known in literature as credit scoring solutions [START_REF] Edelman | Credit scoring and its applications[END_REF].

The key question for decision making about credit status assignment is what characteristics of the consumer should be taken under consideration. According to pragmatism and empiricism of credit scoring the characteristic of the customer (so the vector of the features) should contain only those features, which have meaningful impact on credit decision. Detailed discussion about credit consumer characteristics considered in credit scoring is described in [START_REF] Edelman | Credit scoring and its applications[END_REF].

Another very important aspect of credit scoring (and many other domains, where data mining techniques are applied) is character and quality of the data, which is used to construct decision models. In this work we concentrate on two problems with connected with data: (i) imbalanced data and (ii) asymmetric cost matrix [START_REF] Garcia | Learning from Imbalanced Data[END_REF]. The problem of imbalanced data is related with disproportions in number of examples from different decision variants (decision classes) in the training data. If we consider the decision problem with two possible decision variants, the imbalanced data problem occurs when the cardinality of examples labeled by one class (called majority class) is significantly higher than cardinality of examples labeled by the second class (called minority class). The problem of imbalanced data is often considered in parallel to asymmetric cost matrix problem. Such problem can be observed when the cost of classifying object from minority class as an object from majority class is significantly higher than the cost of classifying object from majority class as an object from minority class.

The aim of this work is to propose the decision making algorithm for credit scoring problem, which solves two of the mentioned data mining problems. The problem of making decision about credit assignment is classification task [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF] in which the characteristic of the credit consumer is represented by vector of features (also called attributes) ܠ and the set of decision variants is represented by the set class labels ܥ{ ଵ , … , ܥ }. The classification process refers to an algorithmic procedure for assigning a given input into one of a given classes. The algorithm that implements classification is known as classifier, which is denoted by Ψ. The is build in training procedure, using training set

ܵ ே = ܠ({ ଵ , ݕ ଵ ), … , ܠ( ே , ݕ ே )}.
In this work we recommend to use the ensemble classifier [START_REF] Kuncheva | Combining Pattern Classifiers[END_REF] that use switching class labels techniques to increase diversity between base classifiers of the ensemble. Our approach is inspired by Breiman's switching class labels technique [START_REF] Breiman | Randomizing Outputs to Increase Prediction Accuracy[END_REF], which was further extended by authors of [START_REF] Martinez-Munoz | Switching class labels to generate classification ensembles[END_REF]. In our approach switching probabilities are estimated basing on error rates between classes. According to the proposed procedure it is more probable to switch labels between classes, which are difficult to separate using single classifier and less probable if the classes are almost perfectly separable. Comparing to solution presented in [START_REF] Breiman | Randomizing Outputs to Increase Prediction Accuracy[END_REF] and extended in [START_REF] Martinez-Munoz | Switching class labels to generate classification ensembles[END_REF] our approach does not require setting any parameters and maintaining class distribution. In our work we would like to show that switching class labels techniques can be successively applied to deal with problems of imbalanced data and cost-sensitive learning in credit scoring field. Our solution is a alternative to existing solutions, which are mainly based on undersampling and oversampling techniques.

Contribution to Value Creation

Nowadays, the crisis on financial markets is observed so it is extremely important for banks and credit institutions to increase their quality rates. The good-quality data mining solutions may help such institutions to make accurate credit assignment decisions which help to reduce the number of dangerous debtors and keep financial status of such companies on the high level.

The proposed classification method is also implemented as a component of Service Oriented Data Mining Systems (SODMS), which is the web data mining system created basing on Service Oriented Architecture (SOA) paradigm. SODMS delivers classification, regression and clustering functionalities as web services [START_REF] Zieba | The proposal of service oriented data mining system for solving real-life classification and regression problems[END_REF]. Thanks to universal interfaces the proposed method can be easily used by various types of bank systems without the need of rebuilding the whole system. Such solution reduces Ψ the costs related with software development and makes the bank institution more competitive on the financial market.

Related Work

The first scientist, who discovered that the problem of separation "good" and "bad" credits is the problem of finding discriminant function was Durman in 1941 [START_REF] Edelman | Credit scoring and its applications[END_REF]. The growing interest of credit scoring solutions was observed when the credit cards occurred in 1960s but the computational resources were not sufficient to use more sophisticated solutions to deal with the problem. At the beginning of 1990s various data mining techniques were used to estimate the risk of credit approval, especially those, which collects the knowledge in visible form like decision rules and trees [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF]. At the beginning of XXI century a growing popularity of ensemble approaches for making credit decisions was observed [START_REF] Hsieh | A data driven ensemble classifier for credit scoring analysis[END_REF][START_REF] Zhou | Least squares support vector machines ensemble models for credit scoring[END_REF]. Such models, which were initialized by the Breiman by proposing bagging algorithm and corresponding statistical framework for the theory of ensembles [START_REF] Breiman | Bagging predictors[END_REF], are powerful tools for solving decision problems which are difficult to be solved using traditional approaches. One of the possible ensemble solutions which can be used to solve credit scoring problem is described in [START_REF] Zhou | Least squares support vector machines ensemble models for credit scoring[END_REF]. The authors of this work propose least a squares support vector machines (SVM) ensemble classification model, which combines the benefits gained by combining decision models in ensemble structure with high accuracy of decisions made using SVM. Other ensemble approach for the credit scoring problem is described in [START_REF] Hsieh | A data driven ensemble classifier for credit scoring analysis[END_REF]. Authors propose to use clustering solutions in preprocessing stage to solve the problem of unrepresentative samples and then they use the ensemble composed of various classification methods to find the final decision about credit assignment. Both of proposed solutions do not touch the problem of imbalanced data and asymmetric cost matrix.

The problem of imbalanced data and corresponding problem of asymmetric cost matrix can be solved by applying oversampling and undersampling techniques [START_REF] Garcia | Learning from Imbalanced Data[END_REF]. In the simplest case the initial imbalanced dataset can be balanced randomly, either by random sampling objects from minority class and merging them with initial dataset (random oversampling method), or by random selection of the objects from majority class and eliminating them from this dataset (random undersampling method). The random undersampling procedure can be only applied if the distribution of majority class in the training set will not be changed in undersampling process. To save the distribution in undersampling process the procedure of examples selection must be intelligent. One of the possible solutions is informed undersampling, which removes those examples, which are least needed and select only important elements from majority class. Interesting informed undersampling approach is presented in [START_REF] Mani | KNN Approach to Unbalanced Data Distributions: A Case Study Involving Information Extraction[END_REF]. Authors of this approach present various techniques for imbalanced data problem, which are based on K-NN algorithm.

On the other hand, synthetic samples can be generated in smart way to balance minority class with majority class. Good example of such type of methods is synthetic minority oversampling technique (SMOTE) presented in [START_REF] Chawla | SMOTE: Synthetic Minority Over-sampling TEchnique[END_REF]. This approach uses K-NN to create artificial examples.

Ensembles are also used for imbalanced data problem [START_REF] Chawla | SMOTEBoost : Improving Prediction[END_REF][START_REF] Guo | Learning from Imbalanced Data Sets with Boosting and Data Generation: The DataBoost-IM Approach[END_REF]. One of the ensemble solutions for imbalanced problem is SMOTEBoost algorithm [START_REF] Chawla | SMOTEBoost : Improving Prediction[END_REF]. This method uses SMOTE sampling to generate artificial examples for minority class for each of boosting iterations. In such approach, each of created base classifiers concentrates more on minority class. As a consequence, the final classification decision made by ensemble classifier is more balanced. The other example of ensemble approach for imbalanced problem is DataBoost-IM method [START_REF] Guo | Learning from Imbalanced Data Sets with Boosting and Data Generation: The DataBoost-IM Approach[END_REF]. This algorithm also uses boosting approach to generate base classifiers. For each of boosting iterations hard examples are identified in current training set. The hard example, which is also called "seed" by the authors, is difficult-to-learn example. Next, each of identified hard examples is used, as a seed, to generate artificial examples. These artificial examples are added to the current training set and the boosting distribution is modified respecting newly added samples.

Ensemble Classifier with Switching Class Labels

The typical structure of ensemble classifier is composed of base classifiers on the first level (denoted in this work by Ψ ଵ (ଵ) , … , Ψ (ଵ) ), which make autonomic class assignment decisions and one combiner (denoted by Ψ (ଶ) ))ܠ( situated on the second level of the ensemble which combines decisions gathered from base classifiers and makes the final decision about class assignment. The base classifiers of the ensemble, which can be represented by any simple classification models e. g. decision tree, or neural network, are constructed using datasets ܵ ே భ , … , ܵ ே ಼ , which are generated from initial training set ܵ ே . Such operation is made to increase diversity of base classifiers what makes the classifier's decisions more independent. In this work we propose the method of building ensemble algorithm which uses switching class labels techniques to increase diversity of base classifiers. This method is based on changing class labels of the objects stored in ܵ ே భ , … , ܵ ே ಼ , which were generated using typical for ensembles diversification technique (e. g. bootstrap sampling). The operation of class switching is made according to the estimated probability values  (݅|݆), which represent the probability, that the object, which is a member of ݆-th class, will be switched to -th class. It can be observed, that main problem in switching class labels techniques is to find the estimated probability values  (݅|݆).

Usually, the switching classes techniques are used to increase the diversity of base classifiers, but in this work we focus on using this group of techniques to solve the problem of imbalanced data in parallel with the problem of asymmetric cost matrix for two-class credit scoring problem. Practically it means that we are interested in finding estimated probability values  (݆ |݆ ) and  (݆ |݆ ), where ݆ and ݆ represent majority (positive credit decision) and minority (negative credit decision) class labels respectively. Moreover, we assume that the unit misclassification cost of classifying the object from minority class (negative credit decision) as an object from majority class (positive credit decision) is significantly higher than misclassification cost in opposite direction. To estimate mentioned probability values we evaluate misclassification tendencies between majority and i minority class. To achieve this, the classifier Ψ (ଵ) (of the same model as base classifiers of the ensemble) is trained using complete set of examples ܵ ே . Next, the performance of classifier is tested on the same set ܵ ே . During testing procedure, for each pair of class labels (݅|݆), the number of examples from ݅-th class classified as member of ݆ -th class group (denoted by ݊ , ) is calculated. Using calculated values ݊ , , which creates so called confusion matrix, following probability estimators can be constructed:

 ൫݆ ห݆ ൯ = 0,  ൫݆ ห݆ ൯ = ೕ ,ೕ ೌೕ ೕ (1)
The ݊ value represents the number of examples from ݆ class situated in initial training set ܵ ே . It can be easily observed that switching classes technique is used only for examples from majority class,  ൫݆ ห݆ ൯ = 0. Such selection of probability estimator is indicated by the asymmetric misclassification costs and was in detailed discussed in [START_REF] Zieba | Ensemble Methods for customer classification in service oriented systems[END_REF]. The formal description of the procedure of creating the base classifiers of the ensemble classifier with switching class labels is listed below:

INPUTS:

Training set: As a second-level classifier, Ψ (ଶ) )ܠ( , we propose voting combiner [START_REF] Kuncheva | Combining Pattern Classifiers[END_REF], what means, that new object will be classified to the class, which will be selected by majority of base classifiers.

ܵ ே = ܠ({ ଵ , ݕ ଵ ), … , ܠ( ே , ݕ ே )} Number of
(ᇱ) = ∅ for ݅ from 1 to ܰ ଵ, do if ݕ( = ݆ ) 3.3.1.1 Generate random value ݎ from [0,1] if ݎ( ≤  ൫݆ ห݆ ൯) 3.3.1.2.1 Set ݕ = ݆ end if end if 3.3.2 Add example ܠ( , ݕ ) to ܵ ே భ,ೖ (ᇱ) end for 3.4 Build classifier Ψ ୩ (ଵ) on training set ܵ ே భ,ೖ (

Empirical Studies and Future Works

The goal of empirical studies is to evaluate the performance of ensemble classifier with switching class labels described in previous section. The evaluation is made for exemplary credit scoring dataset. The performance of the presented approach was measured with two indexes: (i) empirical risk value and (ii) false negative (FN) rate. The results gained during testing the ensemble classifier with switching class labels are compared with the results achieved by the base classifiers and ensemble approaches, which are commonly observed in classification domain.

The German Credit dataset, which is available in UCI Repository [START_REF]UCI machine learning repository[END_REF], is used to evaluate performance of the proposed ensemble classifier. The data set consists of a set of loans given to a total of 1000 applicants, consisting of 700 samples of creditworthy applicants and 300 samples where credit should not be extended. For each applicant, 20 variables describe credit history, account balances, loan purpose, loan amount, employment status, and personal information. Despite the fact that German Credit dataset is quite old it is still successively used for testing solutions related with credit scoring field [START_REF] Hsieh | A data driven ensemble classifier for credit scoring analysis[END_REF]. The authors of [START_REF] Hsieh | A data driven ensemble classifier for credit scoring analysis[END_REF] find The German credit data set very challenging because it is unbalanced and contains a mixture of continuous and categorical values, which confounds the task of classification learning. Moreover, the description of the German Credit dataset recommends using asymmetric cost matrix with the cost of classifying the customer with "bad" credit status to "good" class 5 times greater than misclassification in opposite direction.

The ensemble classifier with switching class labels is implemented using WEKA library. The implementation of the classifier is compatible with paradigms of creating data mining services described in [START_REF] Zieba | The proposal of service oriented data mining system for solving real-life classification and regression problems[END_REF]. It means that proposed classification method can be published as a web service as a component of the SODMS. As a model of base classifiers Breiman's Classification And Regression Tree (CART) was selected. The results of empirical studies made on German Credit dataset are presented in Table 1. The performance of ensemble classifier with switching class labels on mentioned dataset was compared with results achieved by classifiers: rule-based classifier (RIPPER), decision tree (C 4.5), K nearest neighbors (K), multilayer perceptron (MLP), logistic regression (LR), Naive Bayes classifier (NB) and ensemble classifiers: bagging, boosting and DECORATE. Two indexes were used to examine the performance: False Negative (FN) rate and empirical risk index (ERI). FN rate is defined as the number of examples from minority class classified as examples from majority class divided by the total number of examples from minority class. ERI can be interpreted as a weighted error value with weights equal to the misclassification costs. The ERI index value achieved by ensemble classifier with switching class labels was 0.1 lower than result gained by bagging, which performed the best among other tested classifiers. The switching class labels techniques implemented in presented approach significantly decrease the empirical risk value achieved on considered dataset. Similar conclusions arise when FN rate is used as comparison index. The value of FN rate for ensemble classifier with switching class labels was equal 23% and was over two times lower than 51%, which was the best result among the rest of tested algorithms. Practically it means, that 50% -60% customers, which should not obtain the credit, get good credit status when traditional classification approaches are used to make the decision and only 23%, when credit assignment decision is made using ensemble classifier with switching class labels.

The results gained by ensemble classifier with switching class labels significantly better than results achieved by other tested classifier. However, basing on results from one dataset, we can only presume that the proposed classification method outperformed the others by more than 0.1 with respect to ERI. To evaluate the overall performance it is necessary to collect the representative number of datasets and compare the results using statistical methods. Moreover, the ensemble classifier will be adjusted to solve missing values problem in the future works.

  In the first step of the algorithm, classifier Ψ(ଵ) is built on training set ܵ ே . The classifier is not the component of ensemble structure, it is created only to identify misclassification tendencies and, as a consequence, to estimate value of probability  ൫݆ ห݆ ൯, what is made in the second step of the procedure. Next, the base classifiers Ψ ଵ (ଵ) , … , Ψ (ଵ) of the ensemble are created in the loop in the following way. First, training set ܵ ே భ,ೖ is generated by bootstrap sampling without replacement from the initial training set ܵ ே . Bootstrap sampling without replacement is sampling with replacement ܰ examples and eliminating the duplicates. Following the procedure, dataset ܵ ே భ,ೖ is transformed to dataset ܵ ே భ,ೖ (ᇱ) using switching procedure. Each object from training set ܵ ே భ,ೖ , which is member of majority class ݆ , is switched to minority class ݆ with the probability  ൫݆ ห݆ ൯. The training set gained in such way is used to build base classifier Ψ ୩ (ଵ) .

Table 1 .

 1 Results of empirical evaluation on German Credit dataset for different types of classifiers

	Classifiers	ERI value	FN rate
	Ensemble algorithm with switching class labels	0,281	23%
	Bagging	0,386	52%
	Boosting	0,407	55%
	Decorate	0,436	60%
	RIPPER	0,442	58%
	C 4.5	0,436	56%
	KNN	0,453	60%
	MLP	0,408	52%
	LR	0,393	52%
	NB	0,393	51%

Acknowledgments. The research presented in this work has been partially supported by the European Union within the European Regional Development Fund program no. POIG.01.03.01-00-008/08.


Hesam Dashti
email: dashti@wisc.edu

Alireza Siahpirani

James Driver
email: driver@wisc.edu

Amir Assadi
email: ahassadi@wisc.edu

Information Surfaces in Systems Biology and Applications to Engineering Sustainable Agriculture

Keywords: Dynamical Systems, Multiscale Analysis, Multiresolution Analysis, Eigen Analysis

Systems biology of plants offers myriad opportunities and many challenges in modeling. A number of technical challenges stem from paucity of computational methods for discovery of the fundamental properties of complex dynamical systems in biology. In systems engineering, eigen-mode analysis has proved to be a powerful approach to extract system parameters. Following this philosophy, we introduce a new theory that has the benefits of eigen-mode analysis, while it allows investigation of complex dynamics prior to estimation of optimal scales and resolutions. Information Surfaces organize the many intricate relationships among "eigen-modes" of gene networks at multiple scales. Via an adaptable multi-resolution analytic approach, one could find the appropriate scale and resolution for discovery of functions of genes in plants. This article pertains the model plant Arabidopsis; however, almost all methods can be applied to investigate development and growth of crops for research on sustainable agriculture.

Introduction

The concept of dynamical systems has been proposed to investigate natural and synthetic time-dependent systems. Poincare first introduced dynamical systems to study the qualitative aspects of orbits in celestial mechanics [1]. The theory of dynamical systems has been extended to model broader classes of systems whose time-evolution may or may not have periodic orbits [1][2] [3] [4] [START_REF] Alicki | Quantum Dynamical Systems[END_REF].

The numerical study of dynamical systems is focused on modeling the current state of the system [START_REF] Rao | Differential Equations and Dynamical Systems[END_REF] for data mining purposes (i.e. supervised and unsupervised classification) [START_REF] Wingate | Kernel Predictive Linear Gaussian models for nonlinear stochastic dynamical systems[END_REF]. On the other hand, one can argue the need for models that explain the potentially complex relationships among two or more systems [7]. In this direction, we introduce a measurement for quantifying the distance between two dynamical systems. We illustrate the utility and technical power by application of the theory to time-series of gene expression profiles. The data set is comprised of a set of genes stored in rows along time-steps corresponding to expression values in columns.. To analyze such arrays, we introduce the method of "InfoSurf"s in accordance to the three well-known mathematical theories, namely, multiscale analysis [8], multiresolution analysis [START_REF] Rohwer | Nonlinear Smoothing and Multiresolution Analysis (International Series of Numerical Mathematics)[END_REF], and Eigenanalysis [START_REF] Sehmi | Large order structural eigenanalysis techniques: algorithms for finite element systems[END_REF]. The corresponding algorithms are implemented on a high-performance computing (HPC) platform. Briefly, the algorithm considers a two-dimensional array consisting of 'm' observations in the rows and 'n' time points in the columns. Clearly, when we regard the value of the i th observation at the j th time point as the height (z-coordinate) of a point (x=i, y=j) in a three-dimensional Euclidean space, then we would obtain a surface. In InfoSurf theory, one extracts the entries of the 2-dimensional array from eigenvalues of suitable operators, as outlined in Section 2.

In section 3, computational steps of the InfoSurf method are illustrated. In section 4 we apply InfoSurf's to a biological dynamical system associated to the Arabidopsis Thaliana.

Contributions to Value Creation

Sustainable agriculture is regarded as a domain that can greatly benefit from transformative innovations in molecular and cellular plant biology. Molecular methods in biotechnology and agricultural engineering promise rapid breeding of new lines of crops that would sustain stress from global warming and other harsh climatic events. Success of molecular methods depends on breakthroughs in molecular systems biology, and invention of new ways of understanding the complex dynamics formed by time-course data from genes, proteins and other biomolecules. The technical demand for development of new algorithms to surmount the present computational challenges requires re-examination of traditional methods that have proved successful in non-complex systems and their dynamics. In particular, researchers must address discovery of the necessary biological properties implicit inomic data, and mine the abundance of dynamical features that could be observed only in appropriate scales and via optimal resolutions. This research addresses some of the bottlenecks that are posed in providing effective applications of systems biology to sustainable agriculture. Thus, the applications of this research will contribute towards value creation and directly addressing critical scientific problems that face humankind today.

Method

One of the novelties of InfoSurf theory is that it provides a new representation for "global information contents" in a dynamical system that could be localized in a heterogeneous manner. InfoSurf's allow such information contents (in the sense of Shannon) in a discretized dynamical system (M mxn ) to be considered as a surface in three-dimensional Cartesian coordinates, where appropriately defined estimates of (Shannon) information are assigned to the entries in rows and columns of the matrix constructed from the dynamics. In the case of gene expression time-series, the dynamical systems matrix consist of m rows (genes) with n columns (expression values sampled at time points), and typically ݉ ≫ ݊ for whole genome or a similar High Throughput experimental assay due to that the high cost of performing experiments for each period of time [START_REF] Androulakis | Analysis of time-series gene expression data: methods, challenges, and opportunities[END_REF] [START_REF] Ernst | STEM: a tool for the analysis of short time series gene expression data[END_REF]. On the other hand, in the time-series that we study, smooth interpolation of the few number of time points enable us to include a greater number of finer-scale and finer-resolution attributes for situations that the time-series implicitly encode such information about the dynamics [START_REF] Bar-Joseph | Continuous representations of time-series gene expression data[END_REF].This method is a row-wise interpolation, and the choice of the algorithm is based on the regularity properties that are required from various real-valued or vector-valued functions. Further, regularity of the interpolation functions is important to ascertain the smoothness of the corresponding "information surfaces". Also, an InfoSurf requires regularity in how different columns are arranged in relative position (column-wise regularities). To achieve such regularity, an InfoSurf sorts the objects based on three features: the area underneath the curve for (a) the signal (a row), (b) its first derivative (speed of change), and (c) its second derivative (concavity). With these preliminary steps in mind, an InfoSurf is a transformation of the dynamical system onto a piecewise smooth surface (possibly without information loss, if so-desired, or according to estimates for lossy transformations) through multiscale and multiresolution analysis of singular value decompositions (SVD) of the numerous matrices that arise in the process.

Multiscale Analysis

Multiscale methods are used more commonly in recent years due to advances in computational speed that allow running parallel tasks for each scale simultaneously, as well as other hardware advances. In addition, an increasing number of biological modeling problems rely on disparate mathematics to describe phenomena at different spatial and temporal levels. Multiscale analysis [8] provides a bridge between these levels. Further, it allows one to analyze phenomena that are interdependent, to make their relationship explicit, and provide a synthesis of heterogeneous scales that might otherwise be impossible or too difficult to properly describe within the scope of a single model. Particularly in systems biology, biomolecular reactions occur at different rates (scales) and must be estimated at appropriate resolution that varies according to scale. In our setting,, multiscale analysis plays an important role to analyze data at different levels for biological realistic modeling, and as a result, requires us to identify new phenomena at different scales that may otherwise go undetected. This ability is especially important for the Arabidopsis systems biology, because the size of its genome is quite large (about 30,000 genes and other significant non-coding RNAs, or perhaps more.) To perform multiscale analysis on a dynamical system (M mxn ), InfoSurf theory considers a sliding window, a sub-matrix ܵ, of size ݇ × ݇, 2 ≤ ݇ ≤ min(݉, ݊), of M mxn . The size of ܵ varies between the construction of different surfaces but remains invariant for the entire surface under consideration and for the comparison of two surfaces as will be described later in this section. The submatrix slides in two directions; the first sub-matrix is defined by ܵ = M(1: ݇, 1: ݇) (left-top), and slides to right and down by one in every iteration. The following pseudo-code illustrates the process: for i=1:m-k for j=1:n-k S = M(i:i+k, j:j+k) //Performing analysis on S end end One finds that this process projects the matrix M mxn to a super-matrix containing (m-k)x(n-k) sub-matrices of dimension KxK. Overlaps in the sub-matrices reveals the continuous influence of objects on other groups of objects and allows for the method to proceed continuously and reveal information between data points that would otherwise be unaccounted for. Considering every point in different windows illustrates the effect of an object on other object/objects and is seen multiple times as the object remains in the sliding window. This amplifies the (probabilistic) effect(s) of the object and allows for it to be observed in different sliding windows. This allows for easier identification of an object and increases the accuracy of the algorithm when analyzing a dynamical system.

Multiresolution Analysis

Multiresolution analysis allows for larger features of a system to be reduced to the relationships of its fine features. For an example, in a gene expression time-series it allows for the detection of groups of genes that are potentially up or down regulated with respect to one another when verified through relevant biological data. Through use of surfaces, one can observe patterns of gene activity and reduce the macroscopic picture to the action of the individual genes responsible. Considering subsets of genes through different resolutions increases the accuracy of the InfoSurf algorithm. The different resolutions of InfoSurf are characteristic of the sliding window (S kxk ) described in the previous section. Through use of this window, InfoSurf's detection capabilities are increased and it allows for the extraction of specific attributes of genes and the construction of their interrelationships.

Starting multiscale analysis at a larger scale, larger k for the size of the sliding window, allows the algorithm to identify regions of differences of two dynamical systems. InfoSurf uses the multiresolution process to zoom into the regions with very fine sliding windows (smaller values of k) and identify the specific objects corresponding to the differences between the dynamical systems. It provides the ability to capture relationships between groups of objects (coarse scale) and tune it to identify relationships between the objects (fine scale) [START_REF] Nicholson | Modelling of Dynamical Systems[END_REF].

Eigen Analysis

Eigen analysis is a fundamental method of data analysis and the investigation of structural properties of datasets. The use of Eigen analysis in the InfoSurf algorithm was inspired by the kinematics of surface deformation as described in [START_REF] Lai | Introduction to Continuum Mechanics[END_REF]. This analysis of InfoSurf is conceptually similar to what introduced in [START_REF] Fallahati | Dynamic PCA for network feature extraction in multi-electrode recording of neurophysiological data in cortical substrate of pain[END_REF] in analysis of neuronal activation data in experiments on rat Anterior Cingulate Cortex in pain research, and in [START_REF] Wang | Extraction of nonlinear features in MEG and fMRI data of human brain[END_REF] for MEG data of human brain for detection of activated brain regions by measuring the starting point and estimate on length of time of the magnetic fields generated by neuronal spiking and ion transport properties.

For every invariant sliding window (section 3.1), InfoSurf computes its eigenvalues and eigenvectors. The eigenvalues of a sliding window represents a) the heights of the surface. The distribution of eigenvalues is representative of the number of eigenvectors needed to reconstruct S. Since the number of necessary eigenvalues for reconstruction of a surface depends on the smoothness of the surface, b) eigenvalues can be used to represent the smoothness of the surface. For every dynamical system the InfoSurf computes the eigenvalues of every sliding window. Since the sliding window iterates in two-dimensions the eigenvalues are stored in entries of a matrix, E. For the r th row and s th column iterations, InfoSurf associates the absolute value of the sum of the eigenvalues to E(r, s). The matrix E is called an Eigensurface and represents the internal properties of data. After constructing the Eigensurface, the InfoSurf method calculates the first and second derivatives of the Eigensurface. These derivatives are useful for identifying circadian clock information of dynamical systems [START_REF] Aase | Semi-algebraic optimization of temperature compensation in a general switch-type negative feedback model of circadian clocks[END_REF]. While the first derivative is characteristic of the slope of the change of the eigenvalues, relating the change of the information content of each window and the objects within it, the second derivative provides information on the concavity, or acceleration of changes, circadian clock, and shows whether a subset of objects within each window is having a larger or smaller effect as time progresses. After constructing the representative surfaces, the InfoSurf measures the dissimilarity between the dynamical systems. To compare two dynamical systems, the InfoSurf generates seven surfaces: a) distance of the Eigensurfaces, the surfaces of the first derivatives, and surfaces of the second derivatives. b) free-scale distance of the three representative surfaces, and c) the Jacobian matrix. The distance is the absolute value of the direct subtraction of two matrices (surfaces): ,ܣ(ݐݏ݅ܦ )ܤ = ܣ(ݏܾܽ -,)ܤ and the scale-free distance is defined ,ܣ(ݐݏ݅ܦ݁݁ݎܨ )ܤ = ௦(ି) ௦()ା௦() . The distance surfaces show differences/similarities of the dynamical systems. Figure 1 shows different steps of the InfoSurf method. After calculating the Distance, Free Distance surfaces, and finding the largest differences between the derivative surfaces, multiresolution analysis is applied to locate the biggest differences in behavior of Eigensurfaces, which in turn, focuses with a finer resolution and more accuracy towards an area in the original data set that caused these differences.

Discussion and Experimental Results

To evaluate the InfoSurf algorithm we used two dynamical systems from the Arabidopsis Diurnal Rhythms experiment [START_REF] Michael | Network discovery pipeline elucidates conserved time-of-day-specific cisregulatory modules[END_REF]. The data represents gene expression levels of Arabidopsis Thaliana when stimulated with changes in temperature and light. Samples of 22,810 genes were taken in 4 hour intervals over a period of 48 hours. The first experiment consists of exposing the plants to constant light and 22 C in temperature for 12 hours, and then 12 hours of darkness with a 12 C temperature. The second experiment was from plants that were exposed to light during the entire experiment while the change in temperature was the same as the previous experiment. The first data set is called LDHC (Light, Dark, Hot and Cold) and the second data set is called LLHC (Light, Light, Hot and Cold). Each data set has genes in 22,810 rows (genes) and 12 columns (the four hour time steps in the experiments). We interpolated the data sets by the cubic SPLINE method row-wise, and then resampled uniformly to obtain 100 time points for each gene expression.

To acquire a smoother starting surface, we sorted the genes through row exchange based on the similarity of their time series (i.e. expression values). If we denote the time series of a gene by f(t), we consider the value of g(x) =  f(x) +  f′(x) +  f′′(x) to be a good representation of the shape of the signal. The integrations are calculated by the trapezoidal approximation. We sort the LDHC data set and apply the algorithm to obtain the control surface; LDHC) and rearrange the second data set LLHC to impose the same order of genes in both data sets. The deformed surface corresponds to LLHC.

To find the genes that have different dynamic behavior in the two data sets, we considered the differences between the second derivatives of the two Eigensurfaces with the sliding window of size 40, and found the local extrema. These points represent a window of 40x40 in the original data sets (40 genes in 40 time steps) whose eigenvalues are different in the two data sets. To refine the selection of genes, we used a higher resolution sliding window (20x20) inside of the 40x40 matrix. Then the Eigensurface is constructed and the second derivative is calculated in order to elucidate a better understanding of the genes' dynamic behavior within their group and at a finer resolution. This leads to a 20x20 window in the original data that includes the local extrema. We further continued increasing the resolution by using the Eigensurfaces of the10x10 and 5x5 sliding windows which yield a 5x5 area (5 genes in 5 time steps). Algorithm 1 delineates these steps. We considered these 5 genes as potential candidates for being the culprit for the differences in the Eigensurfaces. We then looked up the phenotypic traits attributed to these genes using DAVID (the Database for Annotation, Visualization and Integrated Discovery [START_REF] Dennis | DAVID: Database for Annotation, Visualization, and Integrated Discovery[END_REF]) to check their functionality, and found a gene whose functionality is related to the response of temperature or light stimulus. Due to the large amount of data we ran our program on high performance computing facilities of the Keeneland project [START_REF] Keeneland | National Institute for Experimental Computing[END_REF]. The

Fig. 1 .

 1 Fig.1. The InfoSurf workflow diagram. This figure shows the flow of data in the algorithm.

Acknowledgments. The authors thank Professor Joanne Chory for providing the data sets and discussion about the biological problem. We thank personnel of the "Keeneland: National Institute for Experimental Computing" for their kind supports. This material is based upon work supported by the National Science Foundation under Grant No. 0923296. This projected is partially supported by the National Institute of Health under Grant No. EY21357.


Maciej Drwal
email: maciej.drwal@pwr.wroc.pl

Jerzy Józefczyk
email: jerzy.jozefczyk@pwr.wroc.pl

Decentralized Approximation Algorithm for Data Placement Problem in Content Delivery Networks

Keywords: computer networks, facility location, randomized rounding

Recent advancements in Internet technology research, as well as the widespread of commercial content delivery networks, motivates the need for optimization algorithms designed to work in decentralized manner. In this paper we formulate data placement problem, a special case of universal facility location problem with quadratic terms in objective function. The considered combinatorial optimization problem is NP-hard. A randomized algorithm is presented that approximates the solution within factor O(log n) in decentralized environment, assuming asynchronous message passing of bounded sizes.

Introduction

Content delivery networks (CDN) are systems used to efficiently distribute the Internet traffic to the users by replicating data objects (media files, applications, database queries, etc.) and caching them at multiple locations in the network. This allows not only to reduce the processing load on the server hardware, but also helps eliminating transmission network congestion. Currently all major content providers entrust their offered services to such systems. The optimal data placement problem is one of the most fundamental theoretical challenges arising from the design of such systems.

The emergence of CDNs has triggered a rebirth of algorithmic research in the locational theory, a long established branch of operations research [START_REF] Bektas | Exact Algorithms for the Joint Object Placement and Request Routing Problem in Content Distribution Networks[END_REF]. One of the new aspects of locational problems, which have not yet been investigated thoroughly, is the decentralized solution approach. Such characteristic is especially important for applications in the area of computer network systems design. In the decentralized environment we assume that input data to the optimization problem is scattered among different network nodes, and it is impossible to collect them at one location in order to apply a traditional centralized algorithm. Similarly, decision variables are bound to different nodes, and feasible solutions are constrained by the interactions between them.

In this paper we investigate the problem of optimal placement of single data object in network, as formalized in Section 3. In Section 4 we give a decentralized approximation algorithm, based on randomized rounding, which decides at which nodes to cache data object and finds an assignment of users, resulting in a solution of a value bounded by O(log n) factor of the optimal.

Contribution to Value Creation

The research on new Internet technologies is of a priority importance for the information age society. Given the observed growth in the amount of content provided in the Internet and the limitations of existing IP transfer technology, new networking paradigms are sought. One of such novel concepts is the "content-aware" networking [START_REF] Jacobson | Networking Named Content[END_REF]. Across the years of Internet history, the stage, at which the main performance bottlenecks in the Web access were located, changed gradually. Initially it was the last mile (slow user's access connection, e.g. dial-up modems), which later turned to the first mile (insufficient server infrastructure for handling thousands of concurrent requests) in mid 1990s. Nowadays, as these problems have been largely averted, it is the middle mile (Internet backbone network and edge router devices) that is considered to be the most performance critical area [START_REF] Leighton | Improving Performance on the Internet[END_REF].

As for now, middle mile content delivery methods have already contributed to the generation of value by such Internet enterprises as Akamai Technologies (pioneers in CDN technology research), which provides services to numerous content supplier companies (Amazon, Apple, Facebook, Netflix, Yahoo!, and others). On the top of that, the shift towards the cloud-computing paradigm, observed in recent years, shows the prevalence of content location problems.

The theoretical underpinnings of considered methods would allow to further increase the performance of server systems. This creates the added value by allowing for transfers of much more data in short time without the expensive replacement of the existing telecommunication infrastructure.

Problem Formulation

The data placement problem (or cache location problem) is formulated as follows. Given is a set of clients, each described by the demand w i ≥ 0, denoting the expected (or exact) number of data access requests issued by client i. Given is a set of cache servers, where the application's content can be stored. Each client or server is located at a vertex of a connected and directed graph with vertex set V, |V| = n. A matrix D = [d ij ] of nonnegative distances between nodes i, j ∈ V is given. Each cache server j is characterized by the cost of caching the object b j ≥ 0 (e.g. time needed to download it from the origin server and/or time spent on performing updates), as well as the cost of processing a single client's request h j ≥ 0. In general, a client and server can coincide at the same node in V.

Two decision variables are used. First one is a binary vector z = [z j ], j = 1, …, n, which assumes value z j = 1 if server j caches the data object, and z j = 0 otherwise. Second one is a binary n-by-n matrix x = [x ij ], where x ij = 1 if client i is assigned to server j for requesting the data.

The goal is to minimize the total cost of placement and assignment decisions, which is expressed as the sum of connection costs, server processing costs and object caching cost. Each node i ∈ V generates the following fraction of total cost:

v i (x, z i ) = x ij d ij w i j ∑ + x ij h j x kj w k k ∑       j ∑ + z i b i . ( 1
)
It is assumed that the more clients access the same server, the higher is the response latency perceived by each of the clients. Since all the clients accessing the same server perceive the same latency, the middle sum in (1) contains a quadratic term in x ij x kj . In this paper we consider only the min-sum formulation of the problem, i.e. the objective is to minimize the expression:

V(x, z) = v i (x, z i ) i ∑ , (2)
subject to the following constraints:

∀i x ij = 1 j ∑ , (3) ∀i
, j x ij ≤ z j . ( 4
)
The method is based on the filtering scheme given in [START_REF] Vitter | e-Approximations with Minimum Packing Constraint Violation[END_REF], which was originally developed for approximating k-median and uncapacitated facility location problems (the latter is also known as fixed-cost median problem). A decentralized version of similar scheme for UFLP was used in [START_REF] Moscibroda | Facility Location: Distributed Approximation[END_REF]. The basic idea is to solve the linear programming relaxation of the original problem and use the obtained solution to construct a provably good solution of an associated 0-1 programming problem of minimizing the packing constraint violation, as described below.

Unfortunately, since the considered problem has quadratic terms in objective function, it does not admit straightforward linear programming relaxation. There are, however, many ways to linearize a quadratic binary problem to obtain equivalent linear binary problem. Then a lower bound on the optimal binary value can be computed by solving linear programming relaxation. An example of such method is the reformulation-linearization technique [START_REF] Sherali | A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems[END_REF]. Another way to get the relaxation of quadratic problem is to use semidefinite programming [START_REF] Vandenberghe | Semidefinite Programming[END_REF], [START_REF] Drwal | Load Balanced Location-Routing Problem in Content Distribution Networks[END_REF], which results in polynomial-time solvable convex optimization problem. Such problems can be also solved in decentralized environment (within a bounded accuracy), see for example algorithms based on Gaussian belief propagation [START_REF] Bickson | Gaussian Belief Propagation Based Multiuser Detection[END_REF]. Both approaches increase the number of decision variables and the number of constraints. Moreover, different approaches vary in the tightness of obtained relaxation and consequently in the resulting precision of approximation. Nevertheless, for the purpose of this paper, we assume that a feasible fractional solution of ( 2)-( 4), denoted ( x, ẑ) , can be computed in decentralized way, such that 0 ≤ xij , ẑi ≤ 1, for all i, j = 1, …, n, and is a lower bound on the optimal binary solution, i.e. V( x, ẑ) ≤ V(x * , z * ). For further details on the decentralized linear and convex programming we refer to [START_REF] Moscibroda | Facility Location: Distributed Approximation[END_REF].

Let ( x, ẑ) be a fractional solution of the linear programming relaxation of (2)-(4).

Let us define the weighted cost of client-to-server assignment, obtained from the fractional solution x:

Ĉi = xij d ij w i + h j xkj w k k ∑       j ∑ . ( 5
)
This includes a linear combination of connection and processing costs. Next, for appropriately high ε > 0 we define a neighborhood of node i ∈ V:

W i = { j ∈ V : d ij w i + h j w k k: xkj >0 ∑ ≤ (1+ε) Ĉi }. ( 6
)
The value of ε must be chosen in such a way that each W i is nonempty. It is easy to check that under this definition of W i the following property holds [START_REF] Vitter | e-Approximations with Minimum Packing Constraint Violation[END_REF]:

Proposition 1. Let ε > 0. For each node i ∈ V: ẑj j ∈W i ∑ ≥ xij j∈W i ∑ > ε 1+ε . ( 7
)
Consider the following 0-1 integer programming problem in variables (x, z) of minimizing real variable L subject to:

∀i ∈ V x ij j ∈W i ∑ = 1, ( 8
) b i z i ≤ L i ∈V ∑ , ( 9
) ∀i, j ∈ V x ij ≤ z j , ( 10
) ∀i ∈ V, j ∈ V -W i x ij = 0. ( 11
)
Proposition 2. Let ε > 0 and let x be a fractional solution of problem ( 2)-( 4). Any feasible 0-1 solution x to the problem ( 8)-( 11) satisfies:

x ij d ij w i j ∑ + x ij h j x kj w k k ∑       j ∑         ≤ (1+ε) i ∑ xij d ij w i j ∑ + xij h j xkj w k k ∑       j ∑         i ∑ . ( 12
)
The proof follows from the definition (6) of W i . If in the binary solution a client i is assigned to server j, and some subset S ⊂ V of clients is also connected to the same server j, then the total connection cost of clients S∪{i} is upper-bounded by the corresponding value computed from fractional solution of (2)-( 4).

The packing constraint (9) bounds the placement cost in the original problem. Observe that the Proposition 2 implies, that if we construct a feasible solution of the integer problem ( 8)- [START_REF] Sherali | A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems[END_REF] we would also obtain an approximate solution of the considered data placement problem (2)-( 4), which violates the optimal connection and processing costs at most by a factor (1+ε). Additionally, such solution also gives the placement cost at most L times the optimal, where L is equal to the value of solution of binary problem ( 8)- [START_REF] Sherali | A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems[END_REF].

We now show that it is enough to select only up to O(log n) server nodes to place the data object, in order to obtain a solution that is feasible with high probability. Consequently, the connection and processing costs will be O(1) times higher than optimal and the placement cost would be up to O(log n) higher than optimal, which in turn gives O(log n)-approximation algorithm for the data placement problem.

The idea is to perform appropriate randomized rounding of the fractional solution ( x, ẑ) . Given ε > 0 and 0 < δ < 1, the algorithm selects (1+1 / ε)mlog(n / δ) nodes with replacement and the set of selected nodes will hold the data object, i.e. their decision variables z i are rounded to 1. Each node is selected with probability p(i) = ẑi / m, where m is normalization constant. Thus the total expected cost of all selected nodes is no greater than O(log n) times optimal placement decisions:

(1+1/ ε)mlog(n / δ) ẑj m j ∑ b j ≤ (1+1/ ε)log(n / δ) z j * j ∑ b j . (13)
In the second phase, each client connects to the "cheapest" selected server. The parameter δ controls the probability that the random solution constructed by the algorithm is feasible for ( 8)- [START_REF] Sherali | A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems[END_REF]. It is assumed that each node i knows only the values: i (its own index), n (network size), b i , h i , w i , a row D i of matrix D, and fractional solution ( xi , ẑi ) of the relaxation of problem ( 2)-( 4).

The following procedure is performed concurrently by all server machines j ∈ V:

1. Send ẑj to all other server nodes.

2. Receive values ẑk , k ≠ j, from other nodes.

Compute m= ẑi

i ∑ and put ẑk := ẑk / m for all k.

4. Determine the minimal and maximal ẑk , denoted ẑmin and ẑmax , respectively. 5. If ẑj = ẑmin then let R j = nẑ j / m and Y j = k max , where k max is the index of node with ẑmax . Go to step 8.

6. If ẑj = ẑmax then substitute ẑj = ẑmax m -( 1 n -ẑmin m ) .
7. Go to step 1 (skipping step 3, as the normalization constant is already known). 8. Wait for all nodes to complete the steps 1-7 (e.g. by sending/receiving status messages to all servers). 9. Let t = 0. 10. Generate random bit and send it to all other server nodes. 11. Receive random bits from all other server nodes. Construct random variable 0 ≤ R≤ 1by concatenating all n bits. 12. Let q = nR, and p = (nR) mod 1.

13. If q = j and p < R j then send "mark" to node j+1. 14. If q = j and p ≥ R j then send "mark" to node Y j .

15. If q ≠ j then receive messages from other nodes. If a "mark" message is received then server j is selected for holding data object. 16. Increment t by 1 and go to step 10, until t ≥ (1+1 / ε)mlog(n / δ) .

The above algorithm can be seen as fully decentralized version of Walker's method for sampling from discrete probability distribution [START_REF] Knuth | The Art of Computer Programming[END_REF]. Observe that one server node may be selected multiple times in step 15. When the above algorithm terminates the object placement z is determined. Then the second algorithm is executed to obtain connection matrix x. Each client i queries all servers j for which xij > 0 , obtaining information whether an object is placed at that node. In the response, along with the value z j , client also receives the worst-case processing cost, i.e. the value of h j w k k: xkj >0

∑

. For j such that z j = 1 each client computes d ij w i + h j w k k: xkj >0

∑

, and connects to server j for which this value is the lowest. If for some client there is no such server that z j = 1 and xij > 0 at the same time, then algorithm chooses among all servers caching the object.

The following theorem is based on approach described in [START_REF] Vitter | e-Approximations with Minimum Packing Constraint Violation[END_REF].

Theorem 1. The randomized rounding algorithm constructs a feasible solution of problem ( 8)-( 12) with probability at least 1 -δ.

Proof sketch: In steps 1-7 the algorithm constructs lookup tables for Walker's sampling method [START_REF] Knuth | The Art of Computer Programming[END_REF]. In steps 9-16 the distributed sampling is performed. A feasible solution of the 0-1 integer program ( 8)-( 11) consists of such selection of server nodes z, that every client node i has at least one server with z j =1 in its neighborhood W i . From the Proposition 2, the probability that there would be at least one selected server in the neighborhood W i is:

p( j ) = j ∈W i ∑ ẑj m > ε m(1+ε) j∈W i ∑ . ( 14
)
Since the algorithm selects (with replacement) exactly (1+1 / ε)mlog(n / δ) nodes, the probability that no server from ith client's neighborhood is selected is:

1- ε m(1+ε)       (1+1/ε )mlog(n/δ ) < δ n . (15)
Since there are up to n client nodes, then with probability at least 1 -δ all clients will neighbor a selected server.

Experimental Results

The presented algorithm was implemented in simulation environment. A short summary of experimental results for different input parameters is presented in Table 1. Optimal solutions for problem instances of size n≤15 were obtained by exhaustive search, while problem of size n=100 was taken from plant location benchmarks library [START_REF]UFLP Benchmark Library[END_REF]. The results confirm proven bounds.

Conclusions and Further Work

In this paper the problem of optimal data placement in content delivery network was formulated in a variant, which combines connection, processing and storage costs. A decentralized algorithm was given, based on randomized rounding, which achieves an asymptotically logarithmic performance bounds with high probability. The presented algorithm combines the general filtering technique given by [START_REF] Vitter | e-Approximations with Minimum Packing Constraint Violation[END_REF] with a novel decentralized sampling method applied for randomized rounding. A major drawback of the presented algorithm is that it requires on the input a fractional solution of the relaxation of the original problem (lower bound). Unfortunately, obtaining such solution efficiently for a quadratic problem in decentralized environment is a nontrivial task, which will be subject to further work.

Table 1 .

 1 Comparison of approximate and optimal values for random problem instances

	n	ε	δ	(1+1 / ε)mlog(n / δ)	approx. value	optimal
	5	2	0.1	10	36.0	32.5
	10	0.1	0.2	70	740.9	427.0
	10	1	0.01	70	938.4	427.0
	15	1	0.1	48	723.3	383.8
	15	2	0.2	43	519.0	383.8
	100	2	0.2	84	66246.4	36154

The set defined by the constraints (3)-(4) and x ij , z j ∈ {0,1} is the same as in the well-known uncapacitated facility location problem (UFLP)[START_REF] Jain | Approximation Algorithms for Metric Facility Location and k-median Problems Using the Primal-Dual Schema and Lagrangian Relaxation[END_REF]. In particular, it is assumed that the storage capacities of servers are unlimited (which is reasonable in most practical applications, as the mass storage memory is the cheapest resource among the considered ones). Note that UFLP can be reduced to the considered problem by setting w i = 1 and h i = 0 for all i. Thus the presented problem is NP-hard and at least as hard to approximate as UFLP. In particular, there is no εapproximation algorithm for the considered problem unless P=NP.

Decentralized Rounding Algorithm

In this section the description of a decentralized method of minimizing function (2) in binary variables subject to constraints (3)-( 4) is given. It is assumed that each node i in the network controls a row x i of the decision matrix x, and the decision variable z i . The algorithm works in asynchronous communication rounds. In each round of communication any two nodes can exchange up to O(log n) bits of information. They use two asynchronous operations: send and receive. The receive operation triggers waiting for other nodes to send information. Thus it is required to assure that algorithm will not cause a node to be blocked indefinitely. Any node may send information even to all n-1 remaining nodes (in a form of broadcast), but the message sizes are bounded proportionally to the network size. For example, it is not possible to send whole vector D i to a neighbor, as that requires sending Ω(n log n) bits.

Acknowledgments. This research is partially supported by the scholarship cofinanced by European Union within European Social Fund.


Gonçalo Cândido

Giovanni Di Orio

José Barata

Sebastian Scholze
email: scholze@atb-bremen.de

Adapter for Self-Learning Production Systems

Keywords: Production Systems, Context Awareness, Service-Oriented Architecture, Machine Learning, Context Adaptation

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Along with several other domains, production market has deeply felt the effects of globalization on all its different layers [START_REF] Levitt | The Globalization of Markets[END_REF]. The consumer is continuously demanding for high quality and highly customized products at low cost, with a minimum time-tomarket delay [START_REF] Pine | Mass Customization: The new frontier in business competition[END_REF].

To achieve this goal, modern companies need to take into account not only production control and execution processes but also associated secondary processes in a fully integrated approach. Secondary processes, such as maintenance, energy saving or lifecycle optimization, are typically detached from the core system what leads to poor machine performance and higher lifecycle production costs. As pointed in [START_REF]MANUFUTURE: Strategic Research Agenda[END_REF], the merge of these two domains promises to enhance the efficiency of production processes, maintenance and optimization tasks.

Therefore, the way to attain this goal is to embed self-learning skills alongside monitoring and control of a production system to ease the handling of product variations, process changes, equipment performance degradation, etc. A self-learning system must be able to monitor and detect changes of context by continuously verifying process and equipment parameters initiating an adaptation process whenever current context obliges to. Nowadays, there is very little doubt that Service-Oriented Architecture (SOA) paradigm [START_REF] Bell | Service-oriented Architecture: service analysis, design and architecture[END_REF] is already a major topic in many branches of technology, not exclusively in original business layer ICT [START_REF] Jammes | Service-oriented paradigms in industrial automation[END_REF] [START_REF] Cândido | Service-oriented Architecture at device level to support Evolvable Production Systems[END_REF].

The objective of the work presented in this article is to define an Adapter architecture for Self-Learning Production Systems based on SOA premises. The Adapter is responsible for executing an Adaptation process whenever a change of context is detected in the system. It uses learning techniques along system lifecycle to determine the adaptation that best fits current context.

Contribution to Value Creation

The application of a generic architecture to support the integration of the monitoring and control of secondary processes into production system core promises to open new perspectives for a new generation of intelligent equipment but also for new tools to control and monitor the lifecycle of future production system.

The application of machine learning techniques allied expert input and feedback can improve system autonomy and reliability, while uncovering new knowledge that can be used in future versions of the equipment in incremental way. Also, the inclusion of three industry partners bringing real industrial challenges to be addressed can validate current generic architecture and approach through its use cases results, as well as it can provide a reliable test-bench for future Self-Learning deployments.

Self-Learning Production Systems

The research motivation behind this work relates with the strategic objective of strengthening EU leadership in production technologies in the global marketplace by developing innovative self-learning solutions to enable tight integration of control and maintenance of production systems [START_REF]Self-Learning[END_REF]. This approach requires a paradigm shift in production systems domain aiming to allow adaptation and merging the world of control with other manufacturing activities of the production systems so-called secondary.

To face this, need, the FP7-NMP Self-Learning research project comprising partner organizations from academia, research and industry, experienced in international projects is designing and developing an highly reliable and secure service-oriented based arquitecture to assure effective self-adaptation of the production systems in order to improve control and energy efficiency, utilizing context awareness and machine learning techniques.

Goals

As mentioned in [START_REF] Uddin | Service Oriented Computing to Self-Learning Production System[END_REF], the main goal of the Self-Learning project is to develop innovative self-learning solutions to enable a tight integration of control and other processes of production systems, through the implementation of a SOA infrastructure used to support the proposed self-learning paradigm.

The self-learning approach is intended to have a high impact on manufacturing industries and solve open questions concerning:

• Reduction of time and efforts needed for development/installation of production lines control systems. • High degree of flexibility in the development and installation of production control systems. • Reduction of down times during product exchange and/or conflicts situations.

• Increasing of Overall Equipment Effectiveness (OEE), i.e. plant availability and its productivity over time. This research initiative is driven by three disparate application scenarios applied to real world industrial environment: Integration of control and energy optimization of production processes, enhancing flexibility of machines, and optimized job dispatching of flexible production cells.

Architecture

In the envisioned architecture (see Fig. 1), two basic generic components (Extractor and Adapter) are together able to identify the current context under which the production system is operating, and adapt the production system behaviour at run time in order to improve its performance in face of the contextual changes. The result of the extraction and consequent adaptation activity is exposed to the system expert through the Expert Collaboration UI.

Since the system response must take into account not only the particular context, but most important, the entire lifecycle behavior of both system and expert, a Learning module has been provided to learn relying on data mining and operator's decisions over time. All processed data and knowledge generated are stored in repositories (Context Repository and Adaptation Repository). These components of the Data Access Layer allow both Extractor and Adapter to access it when needed. The general Self-Learning production system architecture has been designed following a modular and abstract approach in order to remain hardware-independent and still compliant with each application scenario.

Adapter

The Adapter is described by focusing on its behavior within the proposed architecture, especially showing the main modules and the interactions between them during the adaptation process.

The issues briefly introduced in the previous sections have been deeply studied during the first stage of the Self-Learning project, reaching a set of features and functionalities for the adapter:

• React to a change of context and provide a suitable adaptation proposal to be validated by the system expert. • Employ the Learning module as a mean to process large amounts of data concerning a particular context and identify the best suite adaptation proposal to be presented to the system expert. • Detect expert input and deploy the validated adaptation into the system.

• Manage Adaptation Repository ensuring that each adaptation process is stored for future use.

Architecture

The generic architecture of the Self-Learning Adapter component is shown in Fig. 2. Each component has a different scope and role during the process of collaboratively providing adaptation proposals on system behavior and parameters according to the current context. Since Adapter is simply one brick of the overall infrastructure, it needs to interact with other surrounding modules to entirely fulfill its objective. This way the Adapter will interact with the Context Extractor component, Learning module, Expert Collaboration UI component and Data Access Layer.

The envisioned architecture shows a reactive behavior since the adaptation process is triggered by an Extractor notification, but also offers a proactive behavior thanks to continuous learning performed by the Proactive Learning component.

Adaptation Process Description

The adaptation process (see Fig. 3) consists of a sequence of procedures to be executed whenever the Extractor notifies the Adapter about a change of context with the objective to adapt the system to face that same context change.

Fig. 3. Adaptation process

After being notified by a context change and launching the Adaptation process, the Repository Extractor component retrieves, from the Data Access Layer, all the necessary data about the current context (Monitoring Data) and models. This collection of data is then transferred to the Repository Parser component to transform it into a generic structure, comprising a context dataset, which can be processed by the Learning module. The result of the Learning module reasoning will be sent to the Learning Parser component which process it and finally creates the Adaptation proposal following a generic template. The Adaptation proposal will be transmitted through the Comm UI component to the Expert Collaboration UI that waits for an expert operator validation or modification of the original proposal. After choosing the final adaptation to be performed, the according Adaptation structure will be distributed to the Self-Learning environment, i.e. the following tasks will be executed: notify the Extractor about the new Adaptation, store the Adaptation into the according repository and send it to the Learning parser component to update existing learning models. 5 Early-Prototype early-prototype has been implemented providing a first version of the Self-Learning platform in order to assure that the proposed solution and infrastructure as well as the methodology is generic and valid to be applied at different levels of control & maintenance integration in distinct industrial environments. The Early-Prototype will be integrated and validated in three distinct application scenarios.

Extract

Business Case 1: Optimization of Secondary Processes in Machine Tools

The first business case concerns the optimization of secondary processes on CNC machines, such as maintenance and/or energy efficiency activity, during the machine tools lifecycle, integrating Self-Learning solutions to the existing service platform as introduced in [START_REF] Bittencourt | Energy Efficiency improvement through context sensitive self-learning of machine availability[END_REF]. Thus, the vision in this business case is to improve manufacturing lines sustainability and maintenance systems.

This way, information about machine tools idle times is exchanged between the equipment and the Self-Learning system in order to:

• Automatically synchronize production and maintenance plan by inserting special monitoring services like friction tests with the smallest effect to productivity, etc.

• Increase of machine efficiency especially with respect to the energy consumption.

During the runtime phase all the machine control states will be monitored in order to recognize the idle-time patterns, classified in time domain, which in turn will be sent to the Adapter. Depending on the temporal dimension of the identified idle-times and on the entire lifecycle of the system, i.e. taking into account the different tasks executed in the past, the Adapter will be able to select one of the two main tasks, respectively:

• Save Energy: switch-off the machine or its auxiliary services improving the energy consumption.

• Maintenance: dynamically modify the maintenance plan for the machine reducing the impact that these operations have on the production.

Business Case 2: Intelligent Monitoring and Adaptation of Machines for Shoe Industry

This business case reports the application of an intelligent monitoring system to extend current monitoring system with the objective of finding and identifying problems that potentially may cause a line stopping.

According to this objective, the Self-Learning platform will be connected to the legacy control system infrastructure improving both the capability of:

• System parameters adaptation based on contextual information coming from shop-floor machines.

• Fault detection and trends in the machines/components behaviour.

According with these two main objectives, two use case scenarios have been provided, respectively: Tanks refilling and Valves synchronization.

The refilling scenario consists of a hydraulic circuit composed of two liquid material tanks. Whenever a tank is refilled the new colder material causes some environment alteration, in particular, material temperature drop down and increasing of the injection pressure.

During runtime, whenever a context change will be detected tanks conditions are sent, to the Adapter, in order to process all this information to identify a tank refilling condition and adapt the control temperature and pressure limits.

In the Valve synchronization scenario a mechanical system consists of five valves connected to different hydraulic circuits with different components that can be composed selecting which valves to open synchronously. During the components dosing process the synchronicity of the different valve circuits is a fundamental aspect to guarantee the quality of the composition.

In this case all the information about the system will be sent to the Adapter that, based on the entire system lifecycle, will be able to predict for each valve the next opening time alerting the operator about a asynchrony between the valves.

Business Case 3: Self-Learning Scheduling and Dispatching in Flexible Manufacturing Systems (FMS) for Automotive Industry

The third business case tries to improve the performance of Flexible Manufacturing System cells by optimizing machine scheduling model according to actual context. The Self-Learning solution is aimed to improve the reactive scheduling model by considering the following main aspects: • Taking into account operator supervision concerning the optimization criteria.

• Introducing resource planning features.

• Identifying process states and operator supervision and learning from them.

A connection between Self-Learning platform and the existing control platform will be necessary to acquire all the necessary contextual information about the system. In the application scenario provided, the main objectives are maximizing the machine utilization rate and avoiding loading stations starvation.

Based on the information about the state of the shop floor environment in a specific point in time and on the previous knowledge about the entire system lifecycle, the Adapter will be able to select the appropriate rule to determine if the clamping job queue is simultaneously satisfying the two main objectives.

The Adapter is allowed to provide output to the process only if the operator validation will be positive otherwise the Adapter will learn from the operator feedback.

Conclusions and Further Work

Current work presents an innovative input to the Self-Learning production systems research domain by introducing the Adapter architecture, features and early prototype specifications. The proposed solution addresses the adaptation of various process/control parameters and procedures to achieve integration of control and secondary processes based on the same generic architecture. This approach relies on context awareness to be able to adapt to contextual changes at run time and learn from adaptation and operator's input.

As future work, a final prototype will be specified and implemented by covering Adaptations procedures more complex based on further extensive machine learning techniques. The automated Adaptation behavior will be also integrated to increase equipment autonomy for tasks where the Self-Learning system already proved to offer accurate and reliable Adaptation proposals.

As a service-based Self-Learning approach, it will be also necessary to address aspects related to reliability, availability, interoperability and security & trust of services, specifically real-time services in device space.

Fig. 1 .

 1 Fig.1. Self-Learning Architectural overview[START_REF]Reliable Self-Learning Production System based on Context aware Services[END_REF]

Fig. 2 .

 2 Fig. 2. Adapter architectural overview The core task-oriented components of the proposed architecture are the following: Repository Extractor, Context Change Handler, Repository Parser, Learning Parser, UI Comm, Adaptation Distribution and Proactive Learning.

Acknowledgments. This work is partly supported by the Self-Learning (Reliable selflearning production system based on context aware services) project of European Union's 7th Framework Program, under the grant agreement no. NMP-2008-228857. This document does not represent the opinion of the European Community, and the European Community is not responsible for any use that might be made of its content. This work is also supported by FCT -Fundação para a Ciência e Tecnologia under project grant Pest-OE/EEI/UI0066/2011.