Maria Hoțoiu
email: mariahotoiu@gmail.com

Federico Tavella
email: federicotavella.7@gmail.com

Jan Treur
email: j.treur@vu.nl

A Temporal-Causal Network Model for the Internal Processes of a Person with a Borderline Personality Disorder

Keywords:

This paper presents a computational network model for a person with a Borderline Personality Disorder. It was designed according to a Network-Oriented Modeling approach as a temporal-causal network based on neuropsychological background knowledge. Example simulations are discussed. The model was verified based on Mathematical Analysis of stationary points.

Introduction

Borderline Personality Disorder (often referred as BPD) is a psychiatric disorder characterized by a continuous pattern of swinging moods, self-image and behavior (NIH website, 2017). People suffering from this disorder may also experience acute episodes of anger, depression and anxiety which can have different duration (typically from a few hours to days). These symptoms often lead to impulsive actions and problems in social interactions (Lis et al., 2013;Mellisa et al., 2017).

As for a relevant amount of mental disorders, people with borderline personality disorder may experience different symptoms based on disorder acuity and severity. In the case of BPD, two of the most common indicators are mood swings and display uncertainty about how they see themselves and their role in the world (NIH website, 2017). People with borderline personality disorder also tend to view (i.e., interpret) things in a "dichromatic" way, such as all black or white. Consequently, their idea of other people can also change very quickly: an individual who is seen as a friend one day may be considered an enemy or traitor the day after. These fluctuating emotional states can lead to intense and unstable relationships. Other symptoms may include:  A pattern of intense and unstable relationships with relatives, friends, and loved ones, often swinging from extreme closeness and love (idealization) to extreme dislike or anger (devaluation)

 Feelings of dissociation [START_REF] Brand | Chronic complex dissociative disorders and borderline personality disorder: disorders of emotion dysregulation? Borderline Personality Disorder and[END_REF], such as feeling cut off from oneself, seeing oneself from outside one's body, or feelings of unreality  Self-harming behavior and recurring thoughts of suicidal behaviors or threats;  Difficulty imagining embodied others, i.e. different empathy levels [START_REF] Haas | Borderline personality traits and brain activity during emotional perspective taking[END_REF][START_REF] Dammann | The Self-Image in Borderline Personality Disorder: An in-Depth Qualitative Research Study[END_REF])  Inappropriate/intense anger or problems controlling anger  Distorted and unstable self-image or sense of self [START_REF] Dammann | The Self-Image in Borderline Personality Disorder: An in-Depth Qualitative Research Study[END_REF] As previously mentioned, not all the subjects with borderline personality disorder experience every symptom. Some individuals experience only a few symptoms, while others have many. These symptoms can be triggered by everyday life events. Moreover, studies show that people with borderline personality disorder can have structural and functional changes in the brain [START_REF] Soloff | Structural Brain Abnormalities in Borderline Personality Disorder: A Voxel-Based Morphometry Study[END_REF] specially in the areas that control impulses and emotional regulation (NIH website, 2008). However, it is not clear whether these changes are risk factors for the disorder, or caused by the disorder.

This paper presents a computational network model for a person with borderline. It was designed as a temporal-causal network based on the Network-Oriented Modeling approach described in (Treur, 2017). First in Section 2 some neuropsychological background is described. In Section 3 the model is introduced. Section 4 discusses some example simulations. In Section 5 it is described how the model was verified based on Mathematical Analysis.

Neuropsychological Background

The findings of numerous studies and research papers from Psychiatry, Cognitive and Social Neuroscience have been used to obtain a justifiable basis for the design of the computational model. The primary criteria for assessing the diagnosis of BPD according to [START_REF] Ellison | The clinical significance of single features of borderline personality disorder; anger, affective instability, impulsivity, and chronic emptiness in psychiatric outpatients[END_REF]; American Psychiatric Association, 2013) are (1) behavioral dysregulation, including impulsivity, excessive and inappropriate anger, self-harming and suicidality, (2) a history of failed relationships and feelings of "emptiness" , (3) affective dysregulation including excessive mood lability, paranoia and fear of abandonment. One explanation offered by (De Meulemeester et al., 2016) for the interpersonal problems that these people experience is identity diffusion, fundamentally characterized by problems with self-other boundaries. According to the study, patients suffering from BPD displayed an instability in their sense of self and identity.

A factor contributing to the affective instability of BPD, according to a study by (Koenigsberg et al., 2010), is that, compared to healthy controls, patients with BPD do not engage the cognitive control regions when employing a distancing strategy to regulate emotional reactions. Anxiety and mistrust, as well as fear of other people's intentions are also common findings in the studies regarding BPD. One such study by [START_REF] King-Casas | The rupture and repair of cooperation in borderline personality disorder[END_REF] involved a mix sample of BPD patients and healthy controls playing a multi round economic exchange game. The findings suggest that BPD subjects express significantly lower levels of self-reported trust relative to healthy controls, as well as negative expectations of social partners, which was also implied by their decisions throughout the game. When studying the link between empathy and social attributions in BPD patients, [START_REF] Homan | Aberrant link between empathy and social attribution style in borderline personality disorder[END_REF] found that BPD patients display the tendency to attribute behavior to traits rather than context, meaning that they have a reduced empathic capacity.

The implications of these studies to the computational model are further discussed is Section 3 and Section 4.

3

The Temporal-Causal Network Model

In order to conceptualize the internal processes, as well as the interaction with an external person, of a person suffering from BPD, a temporal-causal network modelling approach was used, as described in [START_REF] Treur | Network-Oriented Modeling: Addressing Complexity of Cognitive, Affective and Social Interactions[END_REF]. Causal modelling, causal reasoning and causal simulation have a long tradition in AI; e.g., (Kuipers and Kassirer, 1983;[START_REF] Kuipers | Commonsense reasoning about causality: Deriving behavior from structure[END_REF][START_REF] Pearl | Causality[END_REF]. The Network-Oriented Modelling approach based on temporal-causal networks described in [START_REF] Treur | Network-Oriented Modeling: Addressing Complexity of Cognitive, Affective and Social Interactions[END_REF] on the one hand can be viewed as part of this causal modelling tradition, and on the other hand in the perspective of mental states and their causal relations as described in Philosophy of Mind; e.g., [START_REF] Kim | Philosophy of Mind[END_REF].

It is a widely usable generic AI modelling approach that distinguishes itself by incorporating a dynamic and adaptive temporal perspective, both on states and on causal relations. This dynamical perspective enables modelling of cyclic and adaptive networks, and also of timing of causal effects. This enables modelling by adaptive causal networks for connected mental states and for social interaction. Temporal-causal network models can be represented at two levels: conceptual and numerical. These is discussed subsequently in Sections 3.1 and 3. In order to have an adequate social interaction, all these mechanisms should function properly. Since they are correlated to one another, the malfunction of any one of them can lead to problems in the social functioning of the individual. People who suffer from BPD display faults in some of these mechanisms, as described in Section 2. They do not express the tendency to avoid stimuli, even if they are unpleasant, therefore no avoiding mechanism was included in the model. The manner in which these faults are translated into the model is described in Section 4.

The Conceptual Representation of the Network Model

Temporal-causal networks can be represented in a conceptual manner declaratively in either a graphical form or in a matrix form. The elements of a conceptual representation of a design are:

• the states Y of the network • the connections between these states • connection weights X,Y which characterize the different strengths of these connections • a speed factor Y for each state, expressing how fast this state can change • for each state Y a combination function cY(…) indicating how the multiple impacts from the states with outgoing connections to Y combine into a single impact on that state.

In the graphical conceptual representation, states are displayed as nodes and connections as arrows, the pointed end of the arrow indicating the direction of the causal impact. The graphical conceptual representation depicted in Fig. 1 describes the states and their connections in a person suffering from BPD. The above mentioned concepts connection weights, speed factors and combination functions are labels for the arrows (connection weights) and nodes (speed factors and combination functions) of this graph, so that a fully specified graphical conceptual representation gets the form of a labeled graph. There are six types of states in the presented model:

 world states ws, indicating an external stimulus, in this case wss for the stimulus s and wsB for a person B  sensor states ssX (with X = s or X = B) for the sensing of these two external stimuli  sensory representation states srsX (with X = s or X = B) formed based on the sensor states, but also within the person itself and body states of aggression and anxiety  preparation states psX for expressing the body states of anxiety (X = anx) and aggression (X = agg), as well as for communicating to person B (X = B)  control states csX, which regulate the actual expression of anxiety and aggression (X = self) as well the self-other distinction between the person and the other person (X = B,s)  execution or expression states esX for anxiety and aggression and execution state escX for communication to person B

Besides the connections described previously, there are also two loops: the as-if body loops between the preparation states for expressing anxiety and aggression and their sensory representation states, which adapt the internal body map, as described in [START_REF] Treur | Network-Oriented Modeling: Addressing Complexity of Cognitive, Affective and Social Interactions[END_REF].

Numerical Representation of the Network Model

In order to obtain a basis for simulation and further mathematical analysis of the model, the conceptual representation can be transformed into a numerical representation in a systematic manner, as described in [START_REF] Treur | Network-Oriented Modeling: Addressing Complexity of Cognitive, Affective and Social Interactions[END_REF], as follows:

Y(t+t) = Y(t) + Y [aggimpactY(t) -Y(t)] t (3)
where Y is the speed factor of the state Y, or by the following differential equation:

dY(t)/dt = Y[aggimpactY(t) -Y(t)] (4)
As an example, by following the pattern described above based on formulae (1), ( 2), ( 3) and ( 4) the difference and the differential equation for psB are:

psB(t+t) = psB(t) + ps B [cps B (11anx srsanx(t), 11agg srsagg(t), 12B csB,s(t)) -psB(t)] t (5) dpsB(t)/dt = ps B [cps B (11anx srsanx(t), 11agg srsagg(t), 12B csB,s(t)) -psB(t)]
Each state of the model, except for the world states which have no incoming connections, gets a difference and a differential equation assigned. The interaction between these equations describe the behavior of the model. For the model considered here there are 16 coupled difference and differential equations. The combination function used for all the states with only one incoming impact is the identity function id(...) as described in [START_REF] Treur | Network-Oriented Modeling: Addressing Complexity of Cognitive, Affective and Social Interactions[END_REF], Ch 2): cY(V) = id(V) = V. By using this combination function, based on (1) to (4) the difference and the differential equation for srsB, for example, is the following:

srsB(t+t) = srsB(t) + srs B [1B ssB(t) -srsB(t)] t (6) dsrsB(t)/dt = srs B [1B ssB(t) -srsB(t)]
For the states which have multiple incoming impacts the combination function used was the advanced logistic sum combination function alogistic(...), described in [START_REF] Treur | Network-Oriented Modeling: Addressing Complexity of Cognitive, Affective and Social Interactions[END_REF] as follows: cY(V1,...,Vk) = alogistic,(V1, …Vk) = [(1/(1+e -σ(V1, …Vk -) )) -1/(1+e σ )] (1+e -σ ) [START_REF] De Meulemeester | Mentalizing and interpersonal problems in borderline personality disorder: The mediating role of identity diffusion[END_REF] The parameters  and  of this advanced logistic function represent the threshold and the steepness. This function has the property that it maps 0 values to 0 and it also keeps the values between 0 and 1. With this combination function [START_REF] De Meulemeester | Mentalizing and interpersonal problems in borderline personality disorder: The mediating role of identity diffusion[END_REF], based on (1) to (4) the following difference and differential equations for psB, for example, are obtained: psB(t+t) = psB(t) + (8) ps B [alogistic,(11anx srsanx(t), 11agg srsagg(t), 12B csB,s(t)) -psB(t)] t dpsB(t)/dt = ps B [alogistic,(11anx srsanx(t), 11agg srsagg(t), 12B csB,s(t)) -psB(t)]

Simulation Results

The numerical representation presented above was implemented in Matlab, in order to obtain a realistic picture of how the mechanisms discussed in Section 3 interact in the case of a person suffering from BPD. The traits presented in Section 2 are translated into the model by constraints of some of the parameters, as shown in Table 1, thus providing the data at the basis of the simulation.

Following the reasoning presented in [START_REF] Treur | Network-Oriented Modeling: Addressing Complexity of Cognitive, Affective and Social Interactions[END_REF], Ch 10) a reduced self-other distinction means that the connections between srss and csB,s and srsB and csB,s are weak, therefore the values of 7, 8 are low. The intensity of the anger and of the anxiety experienced by these people implicates that the connections between their corresponding sensory representations srsanx and srsagg and the control state for sensing cssens,s are weak, as well as the connections between the control state for monitoring csself and srsanx and srsagg with 10anx, 10agg, 3agg, 3anx are low. The connection between the sensory representation srss of a stimulus s and the control state for sensing cssens,s is also weak, with 9 low, since people suffering from BPD do not exhibit a distancing behavior.

The poor monitoring of emotions translates into weak connections between the sensory representations of the agent itself srsself, as well as the sensory representation srss of stimulus s, and the control state for the agent itself csself with 7self and 8self low. Reduced self-control implicates that the connections coming from the control state cssens,s, as well as from csself, to the expression states esanx and esagg are weak, so 13anx, 13agg, 14anx, and 14agg are low. All the weights of the connections except for those in Table 1 are 1.

Table 1. Connection weights and their values

Connection

Value Connection Value 7 0.5 13anx, 13agg -0.2 8 0.5 7self, 8self 0.2 3agg, 3anx 0.2 14anx, 14agg -0.2 10anx, 10agg 0.2 9 0.2
In order to incorporate the impulsivity trait in the implementation, the speed factors of the control states cssens,s, csself and csB,s are adjusted as being lower than for the other states, for which it is 1. The speed factor of the states regarding communication, psB and escB are also a little lower than one, since verbalizing is a little difficult for people who suffer from BPD so it is most likely to happen after the body expressions of anxiety and aggression. The parameters for the advanced logistic sum combination function corresponding to each state are shown in Table 2. The step size is set at t = 0.5. The initial values of the states are 0, except for the input states wsB and wss which have either the value of 0.2 or 0, equivalent to no stimulus. The value of 0.2 is chosen so low in order to illustrate the strong impact a weak stimulus has on a person suffering from BPD. The results of the simulation for the values discussed above are shown in Fig. 2.

In the first part of the simulation, all the values go up, first the values of the stimuli related states, ssB and sss which are equal, so their graphical representations are overlapping, making only ssB visible. The same is happening with srsB and srss . Even though the value of the input is as low as 0.2, the values of the states for preparation psanx and psagg and expression esanx and esagg climb really fast to values as high as 0.8 and 0.9. This illustrates the power of a small stimuli, when self-control is not working correctly. Note that, since aggression and anxiety are expected to play an equal role in this model, their graphical representations are overlapping. The control states for emotion regulation and suppression and self-other distinction cssens,s, csB,s and csself are always low, as expected. The preparation psB communication to person B escB happen after the expressions of anxiety and aggression, corresponding to the behavior previously described.

Fig. 2. Results of the simulation

After the first 10 time steps, the stimuli go away, meaning that the values of wss and wsB become 0. In a normal person, this would imply that the values of all the other states should decrease to 0, but here the states related to anger and anxiety drop only very little , as expected. The sensory representation states for anxiety srsanx and aggression srsagg are always high in value, illustrating the constantly disturbed inner state people suffering from BPD experience. Since the value of the sensory representation state is high and the values of the control states are low, the expression of the feelings is also high, even if there are no stimuli present. This process of stimuli/no stimuli is repeated throughout the simulation a few times, with the same results.

Verification by Mathematical Analysis

In order to verify the implementation of the model, a mathematical analysis of the equilibria was performed

Y(t) = cY(X 1 ,Y X1(t),..., X k ,Y Xk(t)) (9)
where cY() is the combination function for the state Y and X1,...,Xk are the states which have an impact on Y; see (Treur, 2016, Ch 12). Following this representation if we consider the equilibrium equations for all the states Xi of the model, by leaving out the t and denoting the values as constants Xi, we get from ( 9) for all states Y that an equilibrium is a solution (X1,...,Xn) of the following n equations:

X1 = cX 1 (X 1 , X 1 X1,..., X n , X 1 Xn) (10) ... Xn = cX n (X 1 , X n X1,..., X n , X n Xn)
The model discussed here has 18 states, out of which two are world states, therefore 16 equilibrium equations. For example, the equilibrium equation for the state ssB, which has the identity combination function, is:

ssB = 19 wsB (11)
For the other states which use the identity combination function, the equilibrium equations are similar. For the states which use the combination function alogistic,(..) (see [START_REF] De Meulemeester | Mentalizing and interpersonal problems in borderline personality disorder: The mediating role of identity diffusion[END_REF] in Section 3.2), the equilibrium equations are similar to this one, which is for the state psB: psB = alogistic,(11anx srsanx, 11agg srsagg, 12B csB,s)

Due to the 10 equations that include a logistic function, the equilibrium equations cannot be solved analytically in an explicit manner, but they still can be used for verification of the model. Since the model discussed here has an alternating presence of the stimuli, the model reaches stationary points several times. In order to be able to analyse the stationary points of the model, the number of time steps for observation was increased from 120 to 1200, so that the values of the states would be observed more often. The stimulus is removed and added again once every 200 time steps, so we would expect that the model reaches stationary points 6 times in the simulation. This type of pattern is called a limit cycle, with state values changing all the time. In a limit cycle, each state fluctuates between a minimum and a maximum value. When it reaches the time points for either a minimum or a maximum, each state should have a stationary point, which means that the equation for a stationary point can be verified. The stationary point equations were fulfilled for all the states of the model, with a very high accuracy, as can be seen in Table 3 which is evidence that the implemented model does what is expected.

Discussion

In this paper a computational model of the internal processes of persons suffering from Borderline Personality Disorder was presented. The model was built as a temporalcausal network model according to the Network-Oriented Modelling approach presented in [START_REF] Treur | Network-Oriented Modeling: Addressing Complexity of Cognitive, Affective and Social Interactions[END_REF], incorporating the characteristics described by neuropsychological findings from the literature. The Borderline Personality Disorder is a rather complex disorder, difficult to address. Such a computational model for the Borderline Personality Disorder is new, as far as the authors know. Characteristics such as identity diffusion, the absence of a distancing mechanism, impulsivity, reduced emotion control and poor monitoring, low empathic capacity were incorporated in the model by setting specific values to the parameters concerning the underlying mechanisms, such as connection weights and speed factors. The model was verified by mathematical analysis, with satisfying results.

The model can be the basis for a virtual patient model application and used by therapists to perform what-if simulations to get insight in the borderline phenomenon. It may also be extended by therapies to simulate the effect of them. These can be next steps for future research.

2 .

 2 The following mechanisms based on different theories from the literature are incorporated in the model: • mirror neuron systems (Iacoboni and Dapretto 2006; Iacoboni, 2008) • control neurons with self-other distinction and control function (Iacoboni, 2008; Brass and Spengler, 2009) • emotion integration (Grèzes and de Gelder, 2009; Grèzes et al., 2009) • regulation of enhanced sensory processing sensitivity, in particular for face expressions (Neumann et al., 2006), (Spezio et al., 2007; Baker et al., 2008; Corden et al., 2008) • empathic responding using mirror neurons, self-other distinction and emotion integration (De Vignemont and Singer, 2006; Singer and Leiberg, 2009)

Fig. 1 .

 1 Fig. 1. The graphical conceptual representation of the temporal-causal network model

  [START_REF]American Psychiatric Association: Diagnostic and Statistical Manual of Mental Disorders[END_REF] where X i ,Y is the weight of the connection from Xi to Y • The total impact of all the connections X1,...,Xk to a state Y at time t is The change of the state Y from the time step t to the next time point t+t is represented by the following difference equation:

	aggimpactY(t) = cY(impactX 1 ,Y(t),..., impactX k ,Y(t))	(2)
	where cY(…) is the combination function
	•

• The value of each state Y at each time point t is denoted by Y(t) • The impact from any connection from a state Xi to a state Y at time point t is defined as impactXi,Y(t) = X i ,Y Xi(t)

Table 2 :

 2 Parameters for the combination function

alogistic,(..) for each state

	state			state		
	cssens,s	1	0.2	srsanx	5	0.4
	psB	4	0.2	psanx	5	0.4
	csB,s	2	0.2	esanx	5	0.4
	srsagg	5	0.4	psagg	5	0.4
	esagg	5	0.4	csself	1	0.2

  . A model is in equilibrium at a time point t if all the states of the model have a stationary point at that time t. A state Y has a stationary point at a time t if Y(t+t) = Y(t), for a small t. By considering the differential equation representation for a temporal-causal network model (see (1) to (4) in Section 3.2), a state Y has a stationary point a time t if and only:

Table 3 .

 3 Overview of the outcomes of the verification of the stationary points

	state	ssB	srsB	sss	srss	srsanx		srsagg		csself
	Maxima
	Time point	196	196	196	196	196		196		196
	Value	0.2	0.2	0.2	0.2	0.878487	0.878487	0.107426
	Aggimpact	0.2	0.2	0.2	0.2	0.878487	0.878487	0.107426
	Deviation	0	0	0	0	0		0		0
	Minima
	Time point	406	406	406	406	406		406		406
	Value 9.96e-61 1.97e-58	9.96e-61	1.97e-58	0.877405	0.877405	0.087503
	Aggimpact	0	0	0	0	0.877405	0.877405	0.087503
	Deviation 9.96e-61 1.97e-58	9.96e-61	1.97e-58	0		0		0
	state	csB,s	cssens,s	psB	psagg	psanx	esanx	esagg	escB
	Maxima
	Time point	196	196	196	196	196	196	196	196
	Value 0.189974 0.097537 0.688646 0.848264 0.848264 0.848264 0.848264 0.646615
	Aggimpact 0.189974 0.097537 0.688646 0.848264 0.848264 0.848264 0.848264 0.646615
	Deviation	0	0	0	0	0	0	0	0
	Minima
	Time point	406	406	406	406	406	406	406	406
	Value 2.77e-37 0.087503 0.627566 0.796629 0.796629 0.739934 0.739934 0.627566
	Aggimpact	0	0.087503 0.627566 0.796629 0.796629 0.739934 0.739934 0.627566
	Deviation 2.77e-37	0	0	0	0	0	0	0


Sven Löffler
email: sven.loeffler@b-tu.de

Ke Liu

Petra Hofstedt

The Regularization of CSPs For Rostering, Planning and Resource Management Problems

Keywords: Constraint Programming, CSP, Refinement, Planning, Resource Management, Scheduling

This paper presents a new approach to solve rostering, planning and resource management problems. This is achieved by transforming several kinds of finite domain constraints of a given constraint satisfaction problem (CSP) into a set of regular membership constraints; and then these regular membership constraints are combined together to a more specific regular membership constraint. The purpose of this approach is to improve the speed of CSPs resolution and to remove undesirable redundant constraints (constraints which slow down the resolution speed) by replacing part of or all constraints of a CSP with a set of regular membership constraints followed by the combination of multiple regular membership constraints into a new, more precise regular membership constraint.

A concise rostering example has demonstrated that our approach enables a significant improvement of the performance of the CSP resolution due to the pruning of the search tree.

Introduction

Constraint programming is a powerful method to model and solve NP-complete problems in a declarative way. Typical problems in constraint programming are planning, scheduling, resource management, graph coloring and satisfiability (SAT) problems [10]. Mostly, a CSP in practical can be described in various ways; and consequently, the problem can be modeled by different combinations of constraints, which results in the diversity of resolution speed and behavior. This phenomenon mainly caused by different propagators used by different constraints. Hence, the diversity of models and constraints for a given CSP offers us an opportunity to improve the problem solving by using another model in which a certain type of constraints can be replaced by a faster alternative or combined together to form more specific constraints.

This paper presents a way to model planning, scheduling and resource management problems using a regular CSP and discusses the use of the transformation from a CSP to a regular CSP. Because of the size of such planning, scheduling and resource management problems solving them is mostly very time consuming. The goal is to improve the resolution speed of CSPs, remove redundancy, strengthen propagation, and avoid unnecessary backtracks (or failed backtracks). We reach this goal by replacing some or all constraints of a CSP with regular membership constraints followed by the combination of such created multiple regular membership constraints into a new, more precise regular membership constraint. The regular membership constraint (in the following: regular constraint) and its propagation algorithm [START_REF] Prud'homme | Choco Documentation[END_REF][START_REF] Pesant | A Filtering Algorithm for the Stretch Constraint, Principles and Practice of Constraint Programming -CP 2004[END_REF][START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF] provide the basis of this approach. In [START_REF] Marriott | Programming with Constraints -An Introduction[END_REF] was shown that this approach can improve the solving speed of a CSP by reducing the number of backtracks and fails. In this paper we focus more on the question how we can transform special constraints (especially the count constraint) into regular constraints.

This paper is structured as follows: In Sect. 2 the basics of constraint satisfaction problems (CSPs) are explained and the notion of a regular CSP is presented. In Sect. 3 we show that every CSP can be transformed into a regular CSP, theoretically, and we present a selection of effective constraint transformations for practical use. Sect. 4 is dedicated to a discussion of the advantages and disadvantages and shows an example of this new approach. Finally, we give an outlook on the directions of future research in Sect. 5.

Basic Principles of Constraint Programming

This paper will consider constraint satisfaction problems (CSPs) which are defined as follows.

Definition 1: CSP. [START_REF] Dechter | Constraint processing[END_REF] A constraint satisfaction problem (CSP) is defined as a 3-tuple P = (X, D, C) with X = {x 1 , x 2 , ..., x n } is a set of variables, D = {D 1 , D 2 , ..., D n } is a set of finite domains where D i is the domain of x i , C = {c 1 , c 2 , ..., c m } is a set of primitive or global constraints on the subsets of X.

We distinguish primitive and global constraints. Primitive constraints are simple relations like x 1 = x 2 , x 1 ≠ x 2 or x 1 + x 2 < x 3 . Global constraints [15] are more complex and mostly employed with efficient dedicated propagation algorithms to solve a problem faster than counterpart primitive constraints. Examples of global constraints are the allDifferent, globalCardinality, cumulative, count, sum and regular constraints, described in [START_REF] Van Hoeve | Global Constraints[END_REF].

Definition 2: Global constraint. [START_REF] Van Hoeve | Global Constraints[END_REF] A global constraint is a restriction which describes a relationship between a non-fixed number of variables.

Furthermore, we define a solution of a CSP, local consistency and global consistency. Therefore, global consistency is much strong enforcement of consistency. In particular, the search interleaved with global consistency is backtrack free.

c ⊆ D 1 × ••• × D k is locally consistent if ∀i ∈ {1, ... ,k}, ∀d ∈ D i ,∃(d 1 , ..., d i-1 , d i+1 , ..., d k ) ∈ D 1 × ••• × D i-1 × D i+1 × ••• × D k such that (
We introduce regular CSPs as CSPs (as defined in Definition 1), where all constraints must be regular membership constraints. Definition 6: Regular CSP. A regular constraint satisfaction problem (RCSP) is defined as a 3-tuple P = (X, D, C) with X = {x 1 , x 2 , ..., x n } is a set of variables, D = {D 1 , D 2 , ..., D n } is a set of finite domains where D i is the domain of x i ∀i ∈ {1, 2, ..., n} and C = {c 1 , c 2 , ..., c m } is a set of regular constraints on the subsets of X.

The only difference between a CSP and an RCSP is that a CSP allows all kinds of constraints while an RCSP only allows regular constraints. Because every regular constraint is hyper arc consistent, an RCSP with only one (regular) constraint is globally consistent. This means no backtracking will be necessary when solving such a problem.

Transformation From a CSP Into a RCSP

In this section, we briefly show that for every CSP exists at least one equivalent RCSP (theoretically), and then we present a selection of effective constraint transformations for the practical use.

Theoretical Considerations

According to Definition 1 a CSP P has a fixed number n of variables X = {x 1 , ..., x n } and their respective domains D = {D 1 , ..., D n } are finite, it follows that the potential solution space of the CSP P is limited by l (1).

𝑙 = ∏ |𝐷 𝑖 | 𝑛 𝑖=1 (1)
If the number of solutions is finite, then these can be enumerated by a regular language; besides, for every regular language exists at least one automaton which describes this language (Myhill-Nerode theorem [START_REF] Löffler | The Power of Regular Constraints in CSPs[END_REF]). It follows that for every CSP P exists at least one regular CSP P reg which is declaratively equivalent to P and contains only one regular constraint. Such a RCSP P reg = (X, D, C reg ) can obviously be generated if all solutions of P are known, because, given the language L, we can easily create an appropriate deterministic finite automaton (DFA) M. In practice, however, this is not useful because we intend to use the RCSP P reg to find one, all or the best solutions of P faster than with the original CSP.

For this reason, we consider the direct transformation from multiple types of constraints to regular constraints. For several global constraints (see 3.2), we defined corresponding efficient transformations, among them count, global cardinality constraint, and table constraints.

Transformations From Special Global Constraints Into Regular Constraints

Nevertheless, there is a gap between theory and practice because finding all solutions for the fast transformation from CSP to RCSP can hardly be used in practice. Thus, we seek an efficient transformation method for global constraints. In the following, we are going to present the transformations for several global constraints defined and implemented in [START_REF] Rossi | Handbook of Constraint Programming[END_REF].

The Count Constraint. The count constraint is defined as count(X', occ, v), where X' = {x 1 , x 2 , ..., x n } is a set of variables (X' ⊆ X, X is the set of Variables in the CSP) and occ ∈ X with D occ = {occ min , ..., occ max } is a variable to denote admissible numbers of occurrences of the value v ∈ N in X'.

In order to transform a count constraint into a regular constraint, we take into consideration the following two different cases:

Case 1: The occ variable is not used in other constraints.

In this case, the occ variable can be implicitly represented in the DFA. We create a DFA M = (Q, Σ, δ, q 0 , F) with  Q = {q 0 , q 1 , ...,q occ max }, M = ({q 0 , q 1 , q 2 , q 3 }, {1, 2, 3}, δ, q 0 , {q 1 , q 3 }) with δ = { ((q 0 , 1) → q 0 ), ((q 0 , 2) → q 1 ), ((q 0 , 3) → q 0 ), ((q 1 , 1) → q 1 ), ((q 1 , 2) → q 2 ), ((q 1 , 3) → q 1 ), ((q 2 , 1) → q 2 ), ((q 2 , 2) → q 3 ), ((q 2 , 3) → q 2 ), ((q 3 , 1) → q 3 ), ((q 3 , 3) → q 3 )}.

 ∑ = ⋃ 𝐷 𝑖 𝑛 𝑖=1  q 0 is the initial state,  F = {q i |i ∈ D occ }  δ(q i , v) = q i+1 |∀i ∈ {0, ..., occ max-1 }  δ(q i , v 2 ) = q i |∀i ∈ {0, ..., occ max }, ∀v 2 ∈ Σ\v.
A graphical presentation of M is depicted in Fig. 1a.

Case 2:

The occ variable is used by other constraints.

In this case, we perform as follows: First, we create an automaton M with set of states Q = {q 0 }∪ (q occ t |∀t ∈ D occ ). We let q 0 be the initial state, all other states are labelled with occ t , t ∈ D occ . In the next step, we create |occ| successor automata M t , t ∈ D occ as described for case 1 with variables X 0 , value v and occ = t as input. We combine these automata M t with the automaton M such that the initial state of each M t is replaced with the state q occ t from M. The original count constraint can replace by the regular constraint regular({occ, x 1 , ..., x |X'| }, M) with the resulting DFA M. A graphical presentation of M for the previous example is depicted in Fig. 1b.

The global cardinality constraint. The global cardinality constraint can be interpreted as several count-constraints for which an efficient transform into regular constraints is given above.

The stretch constraint. A good description of the stretch constraint and its transformation into a regular constraint is given in [START_REF] Pesant | A Filtering Algorithm for the Stretch Constraint, Principles and Practice of Constraint Programming -CP 2004[END_REF].

The table-constraint. The table constraint is defined as table(X', A, b), where X' = {x 1 , x 2 , ...,

x n } ⊆ X is a set of variables, and the Matrix A m×n list all tuples extensionally. If boolean variable b is true, any allowed assingment of X' for the table constraint must be limited among the rows of matrix A, otherwise not. Without loss of generality, we only sketch the automaton construction for b is true. For each table constraint with b is false an equivalent table constraint with b is true can be found.

The idea here is to create m DFAs M j , j ∈ {1, ..., m} which only accept the words w j = A j,1 A j,2 ...A j,n . We build M as the union of these m automata M j . This DFA M can be used as a replacement of the table constraint with regular(X', M).

We have presented examples of possible replacements of constraints with regular constraints. However, there exist more, e.g., cumulative constraint, which, however, is beyond the scope of this paper. Please note that a regular constraint created directly from another constraint might be slower than the original constraint. Thus, this transformation is, fairly often, useful if it is possible to combine several regular constraints into one new regular constraint. This can be done by the intersection of automata in which several regular constraints are combined together into one new regular constraint so that fewer backtracks and failures will be encountered. The next section will show more details about this.

4

The Use of Regular CSPs

In this section, we discuss advantages and disadvantages of the transformation of a general CSP P into an equivalent regular CSP P reg , and use a rostering problem as an example.

Advantages and Disadvantages

There are some obvious disadvantages: a transformation for every constraint is necessary (not trivial for some global constraints) and it may be time-consuming to transform a constraint to a regular constraint. Furthermore, the newly created regular constraints might even reduce the performance of the solver.

To illustrate the advantages we briefly repeat how a final domain solver finds solutions. The solver uses depth-first search (DFS) nested with consistency enforcement. In contrast to some other constraints (e.g. sum or cumulative constraint), the regular constraint enforces hyper arc consistency (local consistency) over its variables. Therefore, transforming constraints with a lower consistency level into regular constraints, can (while potentially in-/decreasing the complexity for consistency enforcement) reduce the number of fails and backtracks in DFS in the solution process.

Furthermore, an important advantage is that several constraints can be combined into one new constraint by means of automata intersection. This reduces the number of overlapping constraints and, if we reach a single (hyper-arc consistent) constraint, then the whole CSP has global consistency and no backtracking is necessary any more. Similarly, this idea will often use to substitute pairwise inequality constraints with one allDifferent [START_REF] Rossi | Handbook of Constraint Programming[END_REF][START_REF] Demassey | Global Constraint Catalog[END_REF] constraint.

A great advantage is that the transformation into regular constraints allows combining constraints of originally different types into a new constraint with joint propagation function. This happens by generating the automata, building their intersection (create product automata), and minimizing the resulting DFAs. This, furthermore, leads to a removal of redundancy and, in general, to a reduction of fails and backtracking steps in the depth-first search process.

This preprocessing algorithm happens before other algorithms like common parallelization algorithms will be used. This means that the performance improvements of both approaches (regularization and parallelization) can be used simultaneously.

A Rostering Example

In this section, an example is shown to demonstrate the power of regular constraints. We use the same example as [START_REF] Marriott | Programming with Constraints -An Introduction[END_REF] but the results are summarized. The study [START_REF] Marriott | Programming with Constraints -An Introduction[END_REF] states that regular constraints can improve the performance of CSPs; however, the regular constraints were created directly by the developer requiring domain knowledge about DFAs and regular languages. In this paper we added some automatic transformations by the solver so that the designer of the CSP can model the problem by normal constraints without additional knowledge about regular languages. Based on the constraints count, stretch, table and arithm which are defined in [START_REF] Rossi | Handbook of Constraint Programming[END_REF][START_REF] Demassey | Global Constraint Catalog[END_REF] the constraints C can be modeled as follows:

 C shiftRequirements 1 = {count(X i , occ, j) ∀i ∈ {1, 2, ..., 7},j ∈ {0, 1, 2, 3}} where X i = {x i , x 7+i , x 14+i , ...} ⊂ X and 𝑜𝑐𝑐 = {⌊

 C shiftOrder = {table(x i , x i+1 , ( 3 1 3 2 2 1
), false) ∀i ∈ {1, 2, ..., n -1}}  C equalDays = {arithm(x i , "=", x i+1 ) ∀i ∈ {6, 13, ..., n -1}}

We consider n (n ∈ N, n mod 7 = 0) days, i.e. several weeks. A variable x i , i ∈ {1, 2, ..., n} represents the shift of a person A 1 at day i, where we have four possible shifts: 0, 1, 2, and 3 represent a day off, an early shift, a late shift, and a night shift respectively.

As typical for many rostering problems, we just consider the plan of one person A 1 and assume, that the plan for further staff is received by rotating A 1 s plan by e.g. a week. For example given a shift plan sol A 1 = (v 1 , v 2 , ..., v 7 , v 8, ...,v 14 , v 15 ,... ,v n ) (as a solution of the CSP P) for A 1 , the plan for a person A 2 would be sol A 2 = (v 8 , ..., v 14 , v 15 , ..., v n , v 1 , v 2 , ..., v 7 ). The constraints C are explained in the following:  The C shiftRequirements constraints guarantee that for each day for each shift are exactly as many staff persons as needed. For example there must be between 3 and 4 employees each Monday in morning shift.  The C shiftRepetitions constraints guarantee that the same shift in consecutive days is limited by a lower and an upper bound. This is necessary because in some countries (i.e. Germany) ergonomic knowledge must be respected [START_REF](BAuA) -Design of night and shift work[END_REF].  The C shiftOrder constraints restrict the order of shifts. We consider a forward rotation of shifts which guarantees conformance with the regulations on rest periods in the German labor time law [5, §5].  C equalDays are constraints which guarantee that on Saturday a person always has the same shift as on the following Sunday, which is recommended in [START_REF](BAuA) -Design of night and shift work[END_REF].

Remark: Of course, for real rostering problems, further restrictions and recommendations must be considered.

Evaluation.

A series of tests with different values for n (28, 35, 42, 49, 56) days and four different search strategies, a combination of the variable selectors and FirstFail and the value selectors IntDomainMin and IntDomainMedian was investigated. We applied variable and value selection strategies as defined by Charles Prud'homme for the Choco 4 solver (for details see [START_REF] Rossi | Handbook of Constraint Programming[END_REF]).

We compare the solution behavior of the original version of the CSP P and its regular version CSP P reg , as a result of the intersection of the automatons created with the presented transformations.

In the regular version P reg all constraints have been transformed as described in the previous sections and then all automata -except the C shiftRequirements -were intersected and minimized to a new constraint c regular as described before. We omitted the intersection of the automatons which represents the C shiftRequirements constraints with the other automata because this requires more time as available. The presented transformations in our example have a time requirement in double-digit micro seconds, which is negligible in comparison to the needed solution time.

Table 1 shows the average improvements of the constructed regular CSP P reg in comparison to the original CSP P over all four search strategies and for the respective values of n. For example, for n = 28 days the regular approach was in average 4.546 times faster to find the first solution and 2.413 times faster to find all solutions in comparison to the original approach. For n = 42 and n = 49 there exist no solutions. The regular approach was 3.950 respectively more than 2.780 times faster than the original approach to come to this conclusion. Because problems can need a lot of time, we limited the solution time. The original approach for n = 49 doesn't find a solution in this time limit but the time limit was 2.780 times over the time which the regular approach needed. So the regular approach was at least 2.780 times faster as the original approach. For n = 56 not all solutions were found in the time limit, but the first solution was found more than six times faster in average and within the limited time more than nine times so many solutions were found. Furthermore table 2 shows the reduction factor of the number of nodes (fails resp. backtracks) of the original approach divided by the number of nodes (fails resp. backtracks) of the regular approach. You can see that the full search tree of the regular approach has at least two times less nodes, fails and backtracks as the original approach which is also an indication for the faster solution speed. For the reason of the time limit the whole search tree was not created for n = 56 so that it cannot be said how much smaller the search tree for this RCSP is.

Conclusion

We are going to give a brief summary of this paper, a conclusion, and we explain our next steps.

Summary and Conclusion.

We presented a new approach for the modelling and optimization of general CSPs using the regular constraint.

It was explained how a set of selected global constraints can be transformed into a regular CSP. A regular constraint can be minimized by the use of automata intersection and minimization. By employing a rostering example we have demonstrated that this approach allows to reduce the size of the search tree and to significantly improve the solution speed. For practical problems the execution time for the transformation must be taken into consideration.

Our investigations support that our approach can be applied successfully when considering sub-problems of a potentially large CSP P and, thus, subsets of its variables X. Transforming only sub-problems (instead of P completely) is, thus, much faster and, still, leads to a reduction of the number of constraints (also the number of backtracks) and of redundancy which, altogether, improves the solution speed.

Future work. Future work will be finding more direct transformations for global constraints, finding an automated transformation algorithm, investigating promising variable orderings to optimize the size of the DFAs. Furthermore we would like to study variable and value orderings for the regular constraint, research on potential benefits of decomposition of automata, general (static) criteria to decide when to apply the approach as well as extracting promising application areas in general.

Fig. 1 .Example 1 .

 11 Fig. 1. Automaton representations of the count constraint from example 1 (both cases). Example 1. Given the count constraint count({x 1 , x 2 , x 3 , x 4 , x 5 }, occ, 2) with D i = {1, 2, 3} ∀i ∈ {1, 2, ..., 5} and D occ = {1, 3}. The legal assignments for variables of count constraint must contain value 2 with 1 or 3 occurrences. Our transformation yields the automaton M:

CSP 1 .

 1 Consider a rostering problem, CSP P = (X, D, C), with X = {x 1 , x 2 , ..., x n | n mod 7 = 0}, D = {D 1 , D 2 , ..., D n }, where i ∈ {1, ..., n}:D i = {0,1,2,3}} and C = {C shiftRequirements , C shiftRepetitions , C shiftOrder , C equalDays }.

4 ⌉}}

 4 C shiftRepetitions = stretch(X, {2, 2, 2, 2}, {4, 4, 4, 3}, {0, 1, 2, 3})

Definition 4: Local consistency (Hyper-arc consistency).

	where
	Definition 3: Solution. A value valuation σ = d 1 × ••• × d n , ∀i ∈ {1, ..., n} : d i ∈ D i of
	the variables X = {x 1 , x 2 , ..., x n } in which the value d i is assigned to the variable x i , is a
	solution of P if all constraints C are satisfied.
	[1] A constraint c ∈ C

  The CSP P is globally consistent, if ∀i ∈ {1, ..., n},∀d i ∈ D i :∃d 1 ∈ D 1 , ..., ∃d i-1 ∈ D i-1 , ∃d i+1 ∈ D i+1 , ..., ∃d n ∈ D n such that the valuation σ with σ(x k ) = d k , k ∈ Local consistencyguarantees that each value of a variable in the scope of the constraint is at least part of one solution of this constraint. In contrast, global consistency implies that each value of the variable of the CSP can be extended to at least one solution of the entire CSP.

	d 1 , ..., d i-1 , d, d i+1 , ..., d k )
	satisfies c.
	Definition 5: Global consistency. [2] Let P = (X, D, C) be a CSP with the variables
	X = {x 1 , ..., x n }, the domains D = (D 1 , ..., D n ) and the set of constraints C = {c 1 , ..., c k }
	over X. {1, ..., n} is a solution for P, i.e. satisfies the conjunction of all constraints in C.
	To find a solution of a CSP, a certain level of consistency-enforcing algorithm is
	interleaved with backtrack search. The consistency-enforcing algorithm (e.g., local or
	global consistency) removes the illegal values that cannot occur in any solutions of
	the CSP in the domain of the variables.
	It is important to differentiate between local consistency and global consistency in
	this paper.

Table 1 .

 1 Statsitics for n = 28, …, 56.

	Criteria \n	28	35	42	49	56
	1 st solution	4.546	5.774	-	-	>6.278
	All solutions	2.413	6.146	-	-	-
	No solution	-	-	3.950	>2.780	-

Table 2 .

 2 Statsitics for n = 28, …, 56.

	Criteria \n	28	35	42	49	56
	Nodes	3.018	2.501	4.538	>2.385	-
	Fails	3.043	3.636	4.538	>2.385	-
	Backtracks	3.069	11.824	4.538	>2.385	-

The use of global cardinality constraints would be an alternative here, but, in performance measurements yields worse results in our experiments.


Paul Kelly

Luca Longo
email: luca.longo@dit.ie

An investigation into the effects of Multiple Kernel combinations on solutions spaces in Support Vector Machines

The use of Multiple Kernel Learning (MKL) for Support Vector Machines (SVM) in Machine Learning tasks is a growing field of study. MKL kernels expand on traditional base kernels that are used to improve performance on non-linearly separable datasets. Multiple kernels use combinations of those base kernels to develop novel kernel shapes that allow for more diversity in the generated solution spaces. Customising these kernels to the dataset is still mostly a process of trial and error.

Guidelines around what combinations to implement are lacking and usually they requires domain specific knowledge and understanding of the data. Through a brute force approach, this study tests multiple datasets against a combination of base and non-weighted MKL kernels across a range of tuning hyperparameters. The goal was to determine the effect different kernels shapes have on classification accuracy and whether the resulting values are statistically different populations. A selection of 8 different datasets are chosen and trained against a binary classifier. The research will demonstrate the power for MKL to produce new and effective kernels showing the power and usefulness of this approach.

Introduction

Support Vector Machines are one of the many methods in Machine Learning used as a discriminative classification algorithm. They are a form of supervised learning that allows the categorisation of inputs based on their position in a feature space. They traditionally address binary classification problems by separating data points in the solution hyperspace by means of a hyperplane. The goal is to generate the maximal margin between the hyperplane and the closest points of each category being classified. When a hyperplane cannot be found, which can adequately separate the data points, a kernel can be used [START_REF] Mercer | Functions of positive and negative type, and their connection the theory of integral equations[END_REF]. Kernels are used in SVMs to allow non-linearly separable data points to be mapped to a higher, and potentially infinitely higher dimensional space [START_REF] Vapnik | Support-Vector Networks[END_REF]. Using the kernel trick this can be done with relatively low computation cost as the simple inner product of vectors. In the case of Mercer compliant kernels [START_REF] Mercer | Functions of positive and negative type, and their connection the theory of integral equations[END_REF] , which are the focus of this study, the kernels have the property of being positive semi-definite (PSD) that guarantees a convex solution space. A PSD matrix is defined as one that has only positive eigenvalues. It's resultant convex space guarantees a search minimum and it reduces the search requirements of non-convex solution spaces associated with methods such as Artificial Neural Networks (ANNs). Multiple Kernel Learning is an expansion on these base kernels and used when the traditional kernels, such as Radial Based Functions or Polynomial expansions, are insufficient. Properties of PSD kernels is that the product of two will always produce another semi-definite kernel. This allows for a broad range of combinations and shapes of kernel to be used against data that is difficult to classify. Previous studies on Multiple Kernel Learning have focused on a few themes, the use of a genetic algorithm for hyperparameters selection [START_REF] Gupta | Optimisation of turning parameters by integrating genetic algorithm with support vector regression and artificial neural networks[END_REF], genetic algorithms for kernel selection, the weighted combination of multiple kernels to determine kernel shape [START_REF] Xu | Simple and efficient multiple kernel learning by group lasso[END_REF], and large scale kernel combinations [1] [6]. These approaches focus on specifics of the MKL implementation for a chosen task such as image identification [START_REF] Siddiquie | Combining multiple kernels for efficient image classification[END_REF] or landslide detection [START_REF] Li | Application of GA-SVM method with parameter optimization for landslide development prediction[END_REF]. They are also generally more specific in the choice of kernel combinations and commonly focus on combinations of two different base kernel types. The computation time of constructing the kernels and testing them against the data is a prohibitive feature of the MKL research and the sparse knowledge around global kernel shape approaches makes the scope of research quite broad. The fundamental question of whether the MKL kernel will produce novel results is not explicitly addressed and that is the goal of this research. This paper is structured as follows. Section 2 will address the previous work done in this field and the varying approaches used in relation to their strength and weaknesses regard computation time and performance. Section 3 will detail the approach put forward in the paper and address the choice for experimental design, evaluation methods used, and datasets chosen. Sections 4 and 5 will deal with the results, and what conclusions can be drawn from them, respectively.

Related Work

SVM optimisation is based on the configuration and adjustment of hyperparameters along with the kernel choice when the data is non-linearly separable. Additional hyperparameters also come into play regarding the kernels themselves with specific values needed based on type. Multiple approaches to tuning these hyperparameters have been used to overcome what was originally described by Boser [START_REF] Boser | A Training Algorithm for Optimal Margin Classifiers[END_REF] as needing direct configuring and altering. This problem of tuning is described by Diosan [START_REF] Diosan | Improving classification performance of Support Vector Machine by genetically optimising kernel shape and hyperparameters[END_REF] as an empirical one and should be treated in similar ways to other problems of scale. As an example, the weight of any one hyperparameter, such as the slack variable, has a direct effect on the influence of each support vector [START_REF] Shermeh | Recognition of communication signal types using genetic algorithm and support vector machines based on the higher order statistics[END_REF]. Slack in SVMs is the allowance given to the algorithm to accept misclassified or anomalous data points in the training data. Similarly, the gamma value for the kernel defines the nonlinear mapping to the higher feature space [START_REF] Lu | A GA-SVM hybrid classifier for multiclass fault identification of drivetrain gearboxes[END_REF]. Weighting these vital parameters, and avoiding over-weighting, then becomes a trade-off between maximising the support vector width and reducing errors in classification [START_REF] Deng | Hybrid Method of Multiple Kernel Learning and Genetic Algorithm for Forecasting Short-Term Foreign Exchange Rates[END_REF]. The following sections will describe the different approaches used to tackle the tuning of hyperparameters, the use of genetic algorithms in previous MKL work, and what considerations computational complexity plays in the implementation of MKLs.

Hyperparameter Tuning

One approach used by both Shermeh [START_REF] Shermeh | Recognition of communication signal types using genetic algorithm and support vector machines based on the higher order statistics[END_REF] and Lessmann [START_REF] Lessmann | Genetic Algorithms for Support Vector Machine Model Selection[END_REF] to find optimal hyperparameter values for a kernel is the grid search approach where a range of values are iterated through to find the best solution. Alternatively, Genetic Algorithms (GA) whereby a fitness measure is used to assess a population of randomly chosen parameter sets applied to the SVM is also popularly used to determine the best values. The computation cost, however, of Genetic Algorithm Support Vector Machines (GASVMs) makes them less useful, particularly over larger datasets, as the execution time for all the permutations becomes high. While GASVM approaches have gained popularity in recent years, they have not addressed general rules for the effectiveness or differentiation from base kernel outcomes that the specific kernel combinations produce. While SVM and kernel specific hyperparameter tuning are needed to ensure robust modeling, the use of which kernel combinations determines what shape and eventual properties the MKL kernel will have.

Genetic Algorithm approach to Kernel weights

The question of which kernels to combine and their effect on robust models is another imprtant decision after hyperparameter selection and can also use GA-SVMs to solve for more effective combinations. Polynomial and Radial Based Function(RBF) kernels were combined by Howley [START_REF] Howley | The genetic evolution of kernels for support vector machine classifiers[END_REF] to identify hand-written characters, which is an extremely well-studied problem, to see the effect of their different weighting. The RBF kernel, or Gaussian Kernel, is known for its effectiveness at handling small, high dimensionality datasets which are both notoriously difficult properties for a classification algorithm. Li [START_REF] Li | Application of GA-SVM method with parameter optimization for landslide development prediction[END_REF] demonstrated the RBF's ability to perform well at nonlinear mapping while Diosan [START_REF] Diosan | Improving classification performance of Support Vector Machine by genetically optimising kernel shape and hyperparameters[END_REF] highlights its effectiveness at nonparametric classification functions. Both papers, however, point out the conflicting trade-off that optimisation brings in gains of training accuracy over the complexity of the model. Other approaches have also used a weighted method to determine the role that each of the component kernels has in the resulting MKL kernel. For example, Deng took this approach to include higher weight based on individual features of the dataset but highlighted the resultant search space as being a prohibitive factor [START_REF] Deng | Integrated Model of Multiple Kernel Learning and Differential Evolution for EUR / USD Trading[END_REF]. Similarly to the previous approaches, they suggested a possible approach being the use of a GASVM (Genetic Algorithm SVM) to calculate the optimal solution for kernels as opposed to hyperparameter choice, but again this comes with the high cost of computation expense and time required. Weighting can be counter productive also as strong weighting of less optimal kernels in the MKL arrangement can undermine performance, as documented by by Li et al [START_REF] Li | Application of GA-SVM method with parameter optimization for landslide development prediction[END_REF] in their EEG classification MKL-SVM, and Hao's [START_REF] Hao | A primal method for multiple kernel learning[END_REF] research into primal MKL.

Computational Cost

Computational cost is not only restricted to the choice of kernel combinations or hyperparameter settings but also in either maintaining Mercer compliance to allow simple gradient descent search or employing a more advanced search algorithm to account for the non-convex solution space that non-Mercer kernels produce. Ensuring the Mercer compliance can be maintained easily by making kernels the inner product of existing Mercer compliant kernels and removing the need for these tests that prove positive semi-definiteness. This combination always results in a continuous, positive semi-definite kernel and due to the commutative property of Mercer kernels the order of base kernels has no bearing on the output. MKL kernels can be tested to ensure that the combinations of kernels are compliant with the positive semi-definite properties of a Mercer kernel as highlighted by Howley et al in their use of GASVMs [START_REF] Howley | The genetic evolution of kernels for support vector machine classifiers[END_REF].

Design and Methodology

The approach for this paper is to show that over a broad range of configurations, MKL kernels are valid and novel in shape. To take in a large range of possibilities, a broad range of parameters for the individual kernels will be selected. These will be a choice of kernel specific parameters and tested against the various datasets. Each of the starting, or base, kernels will be first tested against the datasets and then each combined to give the new MKL kernels. This combination will be guaranteed PSD, as discussed earlier, as the base kernels will be chosen from preexisting PSD kernels. The aim will be to test the outputs of the base kernels compared to that of the MKL kernels derived from those specific base kernels. The goal is to move beyond most MKL approaches which use fixed or heuristic based techniques identified by Gonen et al [START_REF] Gonen | Multiple kernel learning algorithms[END_REF] and demonstrate the power of combinations. The approach used will be the CRISP DM method (Cross Industry Standard Process for Data Mining) [START_REF] Shearer | The CRISP-DM Model: The New Blueprint for Data Mining[END_REF] and involves six major stages: 1)Business understanding, 2)Data understanding, 3)Data preparation, 4)Modelling, 5)Evaluation, and 6)Deployment.

Business Understanding

The research hypothesis behind this study is that the accuracy of models induced by SVM classifiers by employing base kernels is statistically significantly less than the accuracy of models induced by employing multiple base kernels, at a 95% confidence level. Formally: H : acc(SV M -baseKernel) <> acc(SV M -M KL), with alpha=0.05

Data Understanding

To test the research hypothesis 8 testing datasets have been taken from the UCI repository and are exclusively binary output variables. The datasets selected are the Prognosis, Heart, Ionosphere, Student Math, Diagnosis, Indian Liver, Student Portuguese, and Pima Indian sets. The datasets were chosen to be relatively small binary sets that have a been previously used in SVM papers and could be run against the full range of hyperparameters and kernels within the allotted time. Variation of the dimensionality, post normalised ranges for standard deviation and variance, and proportion of nominal to categorical variables were also selected for to give a more diverse range of datasets. The focus will be on the individual dataset responses to the different kernel structures and not the specifics of the data.

Data Preparation

All of the datasets were formatted in the folowing ways to maintain consistency and to make them suitable for the SVM implementation.

-Formatted to CSV file type to allow for import and to standardise to a common file type -Column values added from Metadata description files for easier referencing -Categorical and non-numeric fields encoded to numeric values representing each unique entry. This is done to allow them to be used by the SVM. -Normalised between values of 0 and 1 across all dimension excluding on the output/ classification variable to minimise the influence of large number fields.

-The output variable is converted to a -1 and 1 encoding which will be used as factors in the R code.

-Training and testing datasets are both merged as the k-fold method described later will construct multiple training and testing groups later in the process to ensure the quality of accuracy measurement.

Modeling

The 10-fold cross validation technique has been adopted to induce models using the original Support Vector Machine learning algorithm. This validation technique has been chosen because it will ensure a measure of accuracy that prevents over-fitting and maximises the variation in the relatively small datasets used.

Base Kernel Details 1. Linear Kernel Inner product of [x,y] and c value for offset

[k(x, y) = x * y + c]
2. Polynomial Kernel (Degrees 2,3,and 4) Polynomial kernels expand the examination of similarity between entries in the data. The hyperparameters for the polynomial kernel are the slope, the constant C, as in the Linear Kernel , and the degree, d, of the Polynomial used aginst the combined transposed x and y input vectors.

[k(x, y) = (x T y + c) d ]

Gaussian Kernel

The Gaussian Kernel, also known as the Radial Based Function Kernel, is essentially a weighted linear combination that results in a smooth function of the Hilbert space that is defined as a Euclidean space which is complete, separable and infinitely-dimensional.

[k(x, y) = e -x-y 2 2σ 2

]

The sigma parameter determines the width from the classifying points with smaller sizes trending towards local classification and larger sigma for more general classification. It is specifically important for an effective implementation as if underestimated the model becomes particularly susceptible to noise in the training data whereas, if overestimated, it reduces the nonlinear power that is associated with Gaussian kernels.

Hyperbolic Tangent (Sigmoid) Kernel

The Hyperbolic Tangent, or Sigmoid Kernel, has its origins in Artificial Neural Networks (ANNs) where the sigmoid function is used by neurons in the ANN for an activation function. It is also referred to as the Multilayer Perceptron Kernel.

[k(x, y) = tanh(αx T y + c)]

The Sigmoid Kernel is very effective but is not guaranteed to be positive semi definite at higher levels. These higher levels will be avoided for the purposes of this study in order not to affect Mercer conditions.

Hyperparameter Ranges Hyperparameters used across the kernels are:

-Slack: it determines the cost of improperly labelled data points. Range: (0.1, 1, 10, 100, 1000) -Tolerance: required for termination of SVM. Range:(0.1, 0.01, 0.001, 0.0001, 0.00001) -Sigma: parameter for Gaussian kernel. Range: (.01,0.1,0.2,0.5,0.7,0.9).

-Offset: add an additional offset to data points. Range: (1,2,3) -Scale: used by the Sigmoid and Polynomial. Range: (1,2,3) -Degree: used as the power for the Polynomial kernel. Range: [START_REF] Boser | A Training Algorithm for Optimal Margin Classifiers[END_REF][START_REF] Deng | Integrated Model of Multiple Kernel Learning and Differential Evolution for EUR / USD Trading[END_REF][START_REF] Deng | Hybrid Method of Multiple Kernel Learning and Genetic Algorithm for Forecasting Short-Term Foreign Exchange Rates[END_REF] Novel kernels will be named based on their basic kernel components and will total 11 unique combinations all tested again every configuration of hyperparameters. They will be referred to going forward as LinSigGauPoly(LSGP), LinSigGau(LSG), LinSigPoly(LSP), LinGauPoly(LGP), SigGauPoly(SGP), Lin-Sig(LS), LinGau(LG), LinPoly(LP), SigGau(SG), SigPoly(SP), and GauPoly(GP).

Evaluation

Due to the fact that 10-fold cross validation has been used in the training phase, 10 surrogate models have been produced. Therefore, a distribution of 10 classification accuracies for each combination of dataset, hyper-parameters and kernel, is available for comparison purposes [START_REF] Mosteller | Data analysis, including statistics[END_REF]. The Kruskal Wallis test has been chosen to compare obtained distributions of accuracies and to test the research hypothesis. In particular, the distributions obtained when using combination of multiple simple kernels is compared against the distributions of accuracies obtained when employing these individual kernels alone. This method allows for an analysis of variance that is not restricted to normal distributions of equal size. The Kruskal Wallis technique allows for non-parametric analysis of variance [START_REF] Kruskal | Use of ranks in one-criterion variance analysis[END_REF]. This means that the distribution of values does not need to be normal and also accommodates differing sample sizes for comparison. Both characteristics are needed in the case of the SVM outputs as there are non-normal, and occasionally bimodal, distributions of cross validation results for certain kernels across the hyperparameter range. The range of hyperparameters themselves are also kernel specific which will result in differing population sizes that need to be compared. As an example the Linear/Vanilla kernel doesn't take in kernel specific hyperparameters but instead just requires the slack and tolerance values to be tested which totals only 24 combinations. Other kernels, however, such as Lin, Sig, Gau, Poly will require the entire range of combinations resulting in over 4000 results per dataset. The Kruskal Wallis test is run across each of the 8 datasets and compares each base kernel with the kernels that have it as a component part. An example would be all the result for Polynomial Kernel against the Ionosphere dataset compared to those of the LinPoly kernel which is composed, in part, by the Polynomial kernel. A threshold of 95 percent confidence is required to establish if the distributions match and therefore show a lack of a novel solution space 4 Results

Cross Validation

Results show (Table 1) the classification accuracies obtained across selected datasets, base kernels and combined kernels. It also placed these accuracies in context by comparing them with those obtained in another similar studies in the literature (GMKL) [START_REF] Varma | More Generality in Efficient Multiple Kernel Learning Manik[END_REF]. The SimpleMKL [START_REF] Rakotomamonjy | SimpleMKL[END_REF] package, which is very popular method, has also been included with comparable results although over a different set of hyperparameters and completion criteria. Cross validation is used as it gives an indication of a kernels tendency to overfit. Within our results we see multiple 'error' values for the SVM that represent the best outcome achieved in fitting to the dataset which return a zero value. This represents one hundred percent classification accuracy for the training values. The cross validation being much higher than this zero value indicated that the kernel shape has been over fitted to the training and therefore under-performs when presented with novel data. The role of particular kernels and hyperparameters is not in the scope of this specific research but there are trends visible in the data showing a tendency to overfit when the slack value is set too high. This makes intuitive sense as a high punishment for incorrect value will tend to force the SVM to over accommodate mislabels or outliers. The cross validated SVMs results will be using the second evaluation stage as the populations, per kernel and dataset, that need to be compared to the base kernel values.

Kruskal Wallis Analysis

The Kruskal Wallins test is performed against each kernel/dataset combination to determine statistically significant differences in the combined kernels output results and that of the base kernels used in their creation

H = (N -1) g i=1 n i (r i• -r) 2 g i=1 ni j=1 (r ij -r) 2 ,
This method allows for an analysis of variance (ANOVA) that is not restricted to normal distributions of equal size. The test will result in a p value which will allow a rejection or acceptance of the null or alternate hypothesis set out in the business understanding section. Of the 224 results there were only 8 populations which show a distribution unchanged through the addition of another kernel. The 8 ranges of accuracies, produced by the new kernels, that didn't show a new distribution are highlighted in bold below (Table 2). This shows that for the Maths dataset the gaussian kernel was the only one unchanges in some MKl instance. For the Iono, Liver, and Pima the Sigmoid base kernel was the one without changes in some cases and for the Diag dataset the Polynomial had this property. All other 216 combinations produced a new solution space as a result of being combined with another Mercer Kernel.

Summary of findings, strengths and limitations

The findings of the study means that the expansion of the base kernels using additional base kernel(s) does result in a unique range of cross validated results in the vast majority of cases. Most of the p-values related to the comparison of models trained with a base kernels and models trained by adding another base kernel were less than 0.00001. Despite findings strongly support the research hypothesis, these do not give any insight on the impact of multiple kernel on the enhancement of classification accuracies. The confidence in the results can only be stated for the small datasets used relatively balanced target variables. While characteristics of the dataset were noted at the start phase for dimensionality, proportion of categorical fields, and range of values pre and post normalisation, these factors have not been analysed as part of this research and a further investigation is needed to understand how the classification accuracies change and whether dataset properties have a predictable response to the MKL expansions. However, this empirical study does have an impact in validating kernels as viable and distinct kernels for use in SVMs.

Base

Conclusion

The conclusion of this study finds that for the vast majority of base kernel result across the varying datasets, the combination with an additional base kernel or base kernel combination resulted in a statistically significant different range of cross validated accuracies. This helps to further validate the use of multiple kernel learning as a solution to inseparable data through the use of combined conventional kernels. It further opens up investigation into how certain data sets might respond to different kernel shapes based on the dataset properties. Future work should be around investigating the specific hyperparameters role, alongside the dataset characteristics. While this study concentrated on accuracy as the measure of the populations of output, additional work could investigate the ways in which the distributions were altered, positively or negatively, to determine patterns and trends that could help with future MKL creation. The datasets in this study were also relatively small, however, later implementations should address the computational cost using higher performing machines to incorporate larger datasets. Differing proportions of output variables should also be tested and, with it, an examination into the role of kernel shape in accommodating datasets with high sensitivity and specificity requirements. As noted before, when increasing the data size and the balance of outcomes, seed values should be set in the code to ensure the SVM runs against the same partitions of data when using the k-fold cross-validation approach. The scale parameter can also be ignored in future work as the data was pre-normalised but was included for completeness. Finally, the number of base kernels should be expanded to add to the diversity of MKL kernels along with a weighting approach that can consider multiple additions of a specific kernel type rather than MKL kernel composed of just one instance of a particular base kernel.

Table 1 .

 1 Base Kernel and MKL Kernel performance

	Dataset GMKL SimpleMKL Base Kernel	MKL
				Gaussian	SigGau
	WPBC 79.0	76.7	83.9	82.9
				Gaussian SigGauPoly
	Iono	93.0	91.5	96.2	96.2
				Polynomial LinGau
	Liver	72.7	65.9	72.5	72.0
				Polynomial LinPoly
	Pima	77.2	76.5	78.4	78.4

Table 2 .

 2 Base Kernel and MKL Kernel performance

		LSGP	LSG	LGP	SGP	LG	SG	GP
	Math Gau <0.01 0.66685 0.01632 0.73788 0.80290 0.03859 0.73731
		LSGP	LSG	LSP	SGP	LS	SG	SP
	Iono Sig	<0.01 <0.01 0.86221 <0.01	<0.01 <0.01 <0.01
	Liver Sig 0.02753 0.05394 <0.01 0.01759 0.21516 0.01934 0.08873
	Pima Sig 0.02017 <0.01 0.01120 <0.01 0.08193 <0.01 <0.01
		LSGP	LSP	LGP	SGP	LP	SP	GP
	Diag Poly <0.01 <0.01	<0.01	<0.01	<0.01 <0.01 0.12087