A Hybrid Fuzzy Regression-Based Methodology for Normal Distribution (case study: Cumulative Annual Precipitation)

Keywords: Fuzzy linear regression, fuzzy sets, empirical probability function, normal distribution, cumulative annual precipitation

An advantage of the probabilistic approach is the exploitation of the observed probability values in order to test the goodness-of-fit for the examined theoretical probability distribution function (pdf). Since in fact, the interest of the engineers is to determine the hydrological variable which corresponds to a selected return period, a fuzzy linear relation between the standardized normal variable Z and the examined hydrologic random variable is achieved in condition that the hydrological variable is normally distributed. In this work, for the first time, the implementation of the fuzzy linear regression of Tanaka is proposed, to achieve a fuzzy relation between the standardized variable Z and the annual cumulative precipitation. Thus, all the historical data are included in the produced fuzzy band. The proposed innovative methodology provides the opportunity to achieve simultaneously a fuzzy assessment of the mean value and the standard deviation based on the solution of the fuzzy linear regression. The suitability test of the examined theoretical pdf is founded on the comparison of the spread of the fuzzy band and the distance between the achieved central values of the mean value and the standard deviation with the unbiased statistical estimation of the same variables.

Ιntroduction

During the hydraulic design and management the first step is the assessment of the hydrological variables. Unfortunately, these cannot be treated with crisp values. There is plenty of academic works and engineering experience about the probabilistic implementation of the hydrological variables. However, the couple between the statistic and theoretical probability distributions is not without problems. Thus, in this article, for first time, a hybrid model is proposed to improve the matching between the sample and the normal probability distribution function. This hybrid approach treats the couple between the normal distribution density function and the observed probabilities enhanced by the using of fuzzy linear regression.

An advantage of the probabilistic approach as a choice to treat the uncertainty is the exploitation of the cumulative empirical (observed) probability distribution in order to test the goodness-of-fit for a theoretical probability distribution with respect to the historical sample. In this article, a hybrid methodology is developed so that, both the concepts of the observed probability and the flexibility of the fuzzy approach can be used.

More specifically, the main idea is to express the probabilistic parameters as fuzzy numbers and thus, the flexibility of the fuzzy arithmetic and other concepts of the fuzzy sets can be exploited.

Mainly, in contrast with the traditional approaches, the proposed hybrid, fuzzy enhanced methodology produces a fuzzy relation which can be seen as a fuzzy band, which contains all the observed data, that is, all the pairs between the observed hydrological values and the observed probability. This fuzzy relation (it can be seen as a fuzzy band) is modulated based on the fuzzy linear regression model of [START_REF] Tanaka | Fuzzy data analysis by possibilistic linear models[END_REF]. Therefore, the thresholds of fuzziness are modulated with respect to the observed data, by following a constraining optimization problem, and not by following an a-priori information as in several cases of the fuzzy optimization problems.

Fuzzy linear regression may be a useful tool to express functional relationships between variables, especially when the available data are not sufficient (Ganoulis 1994). For instance, [START_REF] Kitsikoudis | Fuzzy regression analysis for sediment incipient motion under turbulent flow conditions[END_REF] employed a fuzzy regression to produce a lower and an upper limit for the critical dimensionless shear stress. Thus, we avoid the ambiguity of selecting a threshold for the initiation of motion, and hence, the model provides a smoother transition to the state of general movement.

More generally, for studying complex physical phenomena such as the interconnection between adjacent watersheds [START_REF] Tsakiris | Assessment of interconnection between two adjacent watersheds using deterministic and fuzzy approaches[END_REF]), the rainfall-runoff process without all the involved parameters, the use of fuzzy models should be investigated. In contrast to the statistical regression, fuzzy regression analysis has no error term, while the uncertainty is incorporated in the model by means of fuzzy numbers [START_REF] Spiliotis | Flooding risk assessment in mountain rivers[END_REF]Papadopoulos & Sirpi 1999).

In brief, the proposed methodology can be divided into three steps: modulation of the data (an analysis based on the conventional statistical approach), application of the fuzzy linear regression (which concludes to a constrained optimization problem) and finally evaluation of the solution achieved where the assumption of the considered pdf is tested. The proposed methodology concludes to a fuzzy relation between the probability and the hydrological variables simultaneously with the fuzzy assessment of the mean value and the standard deviation. In this work, the methodology is developed for normal distributed annual cumulative precipitation.

Basic Notions

Let a historical sample. The rank order method involves ordering the data from the largest hydrological value to the smallest hydrological value, assigning a rank of 1 to the largest value and a rank of N to the smallest value. Based on the Weibull empirical distribution (which is widely used in the Greek regions) to compute the plotting position probabilities, the cumulative exceedance probability can be calculated as follows (e.g. [START_REF] Chow | Applied Hydrology[END_REF]):

  1 m Prob P p     ( 1
)
where m is the rank of the value in a list ordered by descending magnitude [START_REF] Chow | Applied Hydrology[END_REF]). As P many hydrological random variables can be considered. In this work we focus on the annual cumulative precipitation.

It is evident that the cumulative probability of non-exceedance can be calculated as follows based on the exceedance probability (given that that P is a continuous random variable and according to the common practice in hydrology):

  1 1 m Prob P p      (2)
The Return period of an event, T, of a given magnitude may be viewed as the average recurrence length of time (usually years) between events equaling or exceeding a specified magnitude (Chow et al. 1998):

  1 1 Prob P p     (3)
In case of the normal distribution, based on the calculated unbiased estimation of the mean and the standard deviation with respect to the available historical sample, p, s, correspondingly, it holds:

  1 1 Prob P p T           , (4)
    1 1 T T T T Prob P p p p T Z p p Z p p Z                                   ( 5
)
where Z is the standardized normal variable and T p is the magnitude of the event having a return period T.

A used technique in hydrology is to investigate a linear relation between the standardized normal variable Z and the hydrological variable (here the cumulative annual precipitation), instead of the probability plot. Similarly with the probability plot, the calculation of the normal variable Z is based on the empirical probability of the sample which corresponds to each pair between the standardized normal variable and the examined hydrological variable:

0 1 T T p a a Z   (6)
It is desirable, that the coefficients α 0 and α 1 to be close to the unbiased estimation of the mean value and the standard deviation of the sample, p and s respectively, as it occurs in the case of the crisp formulation. In the past, the graphical method with specified paper plots were used in order to rather manually identify the proper curve and the corresponding parameters. Also the conventional regression can be used to determine the parameters α 0 and α 1 .

The main proposal of this article is the application of the fuzzy linear regression to determine the parameters α 0 and α 1 . That is,

0 1 T T p a a Z      (7)
An interesting point is that additionally, a fuzzy approach for the mean value and the standard deviation can be achieved. The proposed methodology is graphically presented in Fig. 1 and it will be presented bellow more analytically. As aforementioned, the produced fuzzy band will contain all the observed data and this is one significant advantage of the proposed methodology.

Proposed methodology

The aim of the proposed methodology is to provide a fuzzy relation between the standardized normal variable Z and the examined hydrological variable simultaneously with a fuzzy estimation of the mean value and the standard deviation. The proposed methodology is based on the observed probabilities of the sample and thereafter the fuzzy regression is used. However, the proposed method holds is the hypothesis of normal distributed random variable holds. Next the main three steps of the proposed methodology are presented.

Modulating the independent and dependent variables

Firstly, the data are ordered from the largest hydrological value to the smallest hydrological value, assigning a rank. Then, based on the Weibull 1939 empirical distribution, the cumulative non-exceedance probability is calculated. Subsequently, a hypothesis must be made about the theoretical probability distribution. Here, the normal distribution is examined. Hence, the standardized normal variable Z can be determined for each pair of data based on the empirical probabilities.

As aforementioned the independent variable is the Z T term. To determine the Z T term the following two assumptions must be made:

1 1 1 T m Z N            (8)
It should be clarified that the standard statistical tests of fitness can be used only to predispose the probability distribution. The proposed methodology does not use the standard statistical tests of fitness. Furthermore, the evaluation of the solution achieved is based on the fuzzy solution and not on any conventional statistical test.

Applying Fuzzy Regression

Fuzzy linear regression model proposed by [START_REF] Tanaka | Fuzzy data analysis by possibilistic linear models[END_REF] has the following form: ... ....

j j i i j j Y A Ax Ax A x             with j =1,…, M, i = 1,…,N ( 9
)
where N is the number of independent variables, M is the number of data, and i A 

= (a i , c i ) L are symmetric fuzzy triangular numbers selected as coefficients (Fig. 2

  0 1 1 Tj Τ, j j j p p s Z x                (10
) where T , j p  is the fuzzy assessment of the hydrological magnitude of the event (dependent variable) having a return period T for the j th set of data.

With respect to Eq. 10, the mean and the standard deviation p, s   respectively, are the fuzzy coefficients (fuzzy symmetrical triangular numbers in this application). The fuzzy coefficients are determined based on the Tanaka fuzzy linear regression method. The standardized normal variable is the independent variable, which takes only crisp values as well as the dependent variable which is the annual cumulative precipitation.

Thus, the proposed methodology can produce a fuzzy estimation of the mean value and the standard deviation. This fuzzy estimation is based on the fuzzy regression and hence, it is founded with the respect to the data. However, we highlight that the fuzzy estimation of the mean value and the standard deviation is related with the assumption of the normal distribution.

In this point it should be referred, that many problems of fuzzy logic, as the fuzzy arithmetic, the fuzzy linear regression e.t.c. are formulated with the aim of a-cuts. The α-cuts could be characterized as the bridge between the fuzzy and the crisp (conventional) sets. The α-cut set of the fuzzy number A (with 0 < α ≤ 1) is defined as follows: Note that the a-cut set is a crisp set determined from the fuzzy set according to a selected value of the membership function and, alternatively, a fuzzy set can be practically decomposed to a significant number of a-cut sets. In case of a = 0, the above definition (Eq. 14) can be modified without the equality in order to describe the zerocut (Kitsikoudis et The concept of inclusion can be defined with respect to the a-cut. The inclusion of a fuzzy set A to the fuzzy set B with the associated degree 0 1 h   (it is a critical point, that the inclusion property is based on a selected h-cut between all the other αcuts) is defined as follows:

    A A x (x)      (11)
    h h A B  (12)
The constraints of the problems are modulated based on the concept of inclusion. Thus, all the data (which are crisp numbers) must be included in the produced fuzzy band:

L R j h , j h , j p p , p      (13)
By taking into account the fuzzy arithmetic, for a selected level h, the inclusion constraints in case the decision variables are selected to be symmetrical triangular numbers, are equivalent to:

            L h, j j R h,
                             (14)
Since the fuzzy regression leads to a constrained optimization problem, the assessment of the fitness is based on the produced fuzzy band. The smaller the fuzzy band, the more proper the fuzzy model becomes. Hence, [START_REF] Tanaka | Fuzzy data analysis by possibilistic linear models[END_REF] suggested the minimization of the sum of the produced fuzzy semi-spreads for all the data (Spiliotis and Bellos, 2016, Kitsikoudis et al. 2016; Papadopoulos & Sirpi 1999):

1 1 M M pj p s Τ, j j j min J w M w w Z                       (objective function) (15)
The above measure is the sum of all the produced semi-spreads (from the fuzzy band) for all the observed data.

Therefore, in brief, based on the Tanaka methodology, the parameters of the fuzzy coefficients, that is, the centers and the widths of the fuzzy coefficients, are determined by solving a constrained optimization problem (Eqs. 14 and 15). In the examined problem, these fuzzy coefficients can be viewed as an estimation of the mean value and the standard deviation. The objective function is selected to be the total semi-spread of the fuzzy outputs.

Evaluation of the solution achieved

In fact, every fuzzy regression problem based on Tanaka formulation will have a solution, and hence, the magnitude of the produced fuzzy band could be a criterion about how successful is the proposed fuzzy linear transformation. A large semispread, J, indicates that the axis of the standardized normal variable Z must be changed and hence, other probability distribution could be examined [START_REF] Spiliotis | A hybrid fuzzy probabilistic assessment of the extreme hydrological events[END_REF].

Another measure to test the suitability of the examined probability distribution is proposed, F which is the Euclidean distance between the central values of the mean value and the standard deviation with the unbiased (usual statistical) estimation of the same variables, ˆ,

  :     2 2 ˆF p s       (16)

Application in case of annual rainfall time series

The meteorological station of Aldeia Nova de São Bento belongs to the National Information System for the Water Resources (SNIRH) of Portugal. The station is located inside the area of Guadiana between the Guadiana River and the Portugal -Spain border, as shown in Figure 3 [START_REF] Angelidis | Computation of drought index SPI with alternative distribution functions[END_REF]. The data cover a large time span, from 1931 up to 2007. The proposed methodology was applied to express the annual cumulative rainfall with respect to the for normal distributed rainfall. Indeed, by using the statistical test of Kolmogorov-Smirnov (K-S) with an interval confidence (1-α)=0.80, the result indicates that the normal distribution can be used to express the annual rainfall in Aldeia Nova de São Bento. As aforementioned the statistical test is not used directly in the proposed methodology, but it simply indicates a proper algebraic transformation. Fuzzy regression is applied for a selected h = 0 whilst fuzzy symmetrical triangular numbers were selected as fuzzy coefficients. Finally, based on the above assumptions, the problem of fuzzy regression leads to a linear programming problem. All in all, the following fuzzy curve between the standard normal random variable Z and the annual rainfall is produced through the constrained optimization problem according to Eqs. 14 and 15 (Fig. 4):

    551 50 39 95 L L P 161.96 , 3.58 Z . , .       (17)
where P   is a fuzzy number which represents the estimated cumulative annual runoff (dependent variable). Hence, by adopting the normal distribution, according to Eq.17, we achieve simultaneously a fuzzy assessment of the mean value

 

551 50 39 95 L . , .

and the standard deviation   L 161.96 , 3.58 . The first term in the bracket expresses the central value (Fig. 2) and the second term, the semi-width of each fuzzy symmetrical triangular number. The objective function of the fuzzy regression problem which expresses the total uncertainty is equal to:

N Τ, j j J Z      (18)
In addition, from the fuzzy curve (Eq. 17), it is easy to see that the central values of the fuzzy coefficients, which can be seen as a fuzzy approximation of the mean value and the standard deviation, are very close to their unbiased estimation based on the historical sample  

F mm      (19)
The values of both the objective function (Eq. 18) and the proposed measure F (Eq. 19) indicate that the fuzzified normal distribution can be used to express the annual cumulative rainfall in Aldeia Nova de São Bento. Therefore, from the application, it is evident that the objective function and the proposed measure of suitability, F, provide us the opportunity to test the suitability of the initial hypothesis about the use of the normal distribution as the theoretical probability distribution. Another interesting perspective to discuss is the proposed methodology in relation with the statistic test of Kolmogorov-Smirnov. The statistic test of Kolmogorov-Smirnov involves the absolute values of the distance between the observed probability and the probability value from the adopted theoretical cumulative distribution function for all the sample. By applying the proposed methodology, all the data, that is, each pair which includes the value of the hydrological value and the corresponding non-exceedance empirical probability is included in the produced fuzzy band at least to some degree (Fig. 4).

An interesting point is that the proposed fuzzy estimation of the mean value and the standard deviation is more founded to fuzzy logic and without subjective choices which must be made by the user, compared with Sfiris et al., 2014 approach. According to Sfiris et al., 2014, the mean value and the standard deviation are estimated as fuzzy numbers starting from the conventional probabilistic confidence interval. However, a confidence interval must be selected from the user, in order to move from the probabilistic approach to the fuzzy approach. In addition, the transition from the asymptotic to non asymptotic membership function was done by selecting a suitable function. According to the new methodology, the mean value and the standard deviation are estimated as fuzzy numbers based on the observed data by following a fuzzy regression approach without specific considerations from the user. Furthermore, two measures to test the validity of the method are proposed.

It should be clarified also that the proposed methodology is based on the probabilistic model with crisp data whilst the fuzziness arises from the matching between the theoretical probability distribution function and the observed probabilities. The method should not be confused with either methods which are based on fuzzy data (fuzzy sample, e.g. [START_REF] Viertl | Statistical Methods for Fuzzy Data[END_REF] or methods with starting from a probabilistic approach conclude to a fuzzy approach (e.g. [START_REF] Sfiris | Non-asymptotic fuzzy estimators based on confidence intervals[END_REF].

Another interesting point for further investigation is the use of several theoretical distributions. Then, the use of the suitability measure F and the value of the objective function J can be seen as the criteria according to which the selection of the suitable theoretical probability distribution can be done. Spiliotis and Papadopoulos, 2017 have already studied a similar methodology in case of lognormal theoretical probability distribution. In general, the proposed methodology could be expanded based on the frequency factor method which includes also the proposed analysis based on the standardized variable Z for normal probability distribution.

As aforementioned in case that a significant fuzzy band is produced, then the first think will be the change of the theoretical pdf and this can be seen as the main challenge for further investigation. However, the use of new techniques of fuzzy regression should also be investigated. For instance, it could be investigated the use of more sophisticated objective functions which will contain both the centers and the widths of the fuzzy coefficients. Hence, a new objective function could try either to increase the possibility of equality between the observations and fuzzy intervals [START_REF] Shakouri | Investigation on objective function and assessment rule in fuzzy regressions based on equality possibility, fuzzy union and intersection concepts[END_REF] or could incorporate simultaneously with the fuzzy spreads the sum of possibility grade in the objective function (Yoshiyuki, 2017). Alternatively, ideas from goal programming could be applied in order to reduce the impact of outliers [START_REF] Kitsikoudis | Fuzzy regression analysis for sediment incipient motion under turbulent flow conditions[END_REF] and hence, the objective function is changed accordingly.

Concluding remarks

A hybrid combination between the problem of coupling between the observed probabilities and the normal distribution with the aim of fuzzy linear regression analysis is proposed in this article. According to the proposed methodology, the exploitation of the empirical probability function can be achieved together with a fuzzy approach. The key of the proposed methodology is the application of the fuzzy linear regression model of Tanaka in order to achieve a linear relation with fuzzy numbers as coefficients. In addition, based on the proposed fuzzy regression, the mean value and the standard deviation are determined as fuzzy coefficients.

Hence, the proposed innovative methodology provides the opportunity to achieve simultaneously a fuzzy assessment of the mean value and the standard deviation based on the solution of the fuzzy linear regression. In contrast, the application of the conventional crisp regression products crisp numbers as coefficients, which differ from the unbiased estimation of the mean value and the standard deviation. The proposed fuzzy estimation of the mean value and the standard deviation is desirable to include the unbiased estimation of the mean value and the standard deviation.

Indeed, the measure of the distance between the central values of the mean value and the standard deviation with the unbiased (usual statistical) estimations together with its fuzziness, are proposed also as measures of suitability in order to test the validation of the method and consequently the selected probability pdf.

Another interesting property of the proposed methodology is that the proposed fuzzy band includes all the data at least at some degree. In general, the proposed methodology improves the matching between the sample of the hydrological variable and the used probability distribution.

Fig. 1 .

 1 Fig.1. Schematic representation of the proposed methodology.

Fig. 2 .

 2 Fig. 2. Fuzzy triangular symmetrical number.

Fig. 3 .

 3 Fig. 3. Location of the Aldeia Nova de São Bento rain station.

Fig. 4 .

 4 Fig.4. Observed data, fuzzy and conventional (crisp) regression between the standardize normal variable Z (based on the observed cumulative non-exceedance probabilities) and the annual rainfall of the sample.

  al. 2016; Spiliotis & Bellos 2016; Buckley & Eslami 2002).


Armando H Taucer
email: armando.h.taucer@gmail.com

Spencer Polk

B John Oommen
email: oommen@scs.carleton.ca

On Addressing the Challenges of Complex Stochastic Games Using "Representative" Moves

The problem of achieving competitive game play in a board game, against an intelligent opponent, is a well-known and studied field of Artificial Intelligence (AI). This area of research has seen major breakthroughs in recent years, particularly in the game of Go. However, popular hobby board games, and particularly Trading Card Games, have unique qualities that make them very challenging to existing game playing techniques, partly due to enormous branching factors. This remains a largely unexamined domain and is the arena we operate in. To attempt to tackle some of these daunting requirements, we introduce the novel concept of "Representative" Moves (RMs). Rather than examine the complete list of available moves at a given node, we rather propose the strategy of considering only a subset of moves that are determined to be representative of the player's strategic options. We demonstrate that in the context of a simplified Trading Card Game, the use of RMs leads to a greatly improved search speed and an extremely limited branching factor. This permits the AI player to play more intelligently than the same algorithm that does not employ them.

Introduction

The problem of playing a competitive board game, intelligently and effectively, against a human player is canonical in AI. Over the years, a broad range of literature has been published addressing the problem of game playing, introducing a wide range of highly effective techniques, for many different types of games [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF][START_REF] Schadd | Best Reply Search for multiplayer games[END_REF][START_REF] Shannon | Programming a computer for playing Chess[END_REF]. Historically, the literature has emphasized classical, deterministic, two-player board games, and in particular, Chess and Go [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF][START_REF] Xiao | Modification of uct algorithm with quiescent search in computer go[END_REF]. AI systems for many such games are powerful enough to overwhelm even the best human players.

In recent years, perhaps influenced by their growing popularity in popular culture, card-based games such as Bridge and Poker have seen an increased emphasis in the literature [START_REF] Moravčík | Deepstack: Expert-level artificial intelligence in heads-up no-limit poker[END_REF][START_REF] Onisawa | Construction of poker playing system considering strategies[END_REF]. However, there are still some categories of popular games (particularly amongst "hobbyist" game players), which have been the subject of proportionally limited investigation within the field. One of these includes large-scale, complex, multi-player strategy board games, such as the popular Settlers of Catan and Carcassone [START_REF] Pfeiffer | Reinforcement learning of strategies for settlers of catan[END_REF][START_REF] Szita | Monte-carlo tree search in settlers of catan[END_REF]. Another is the category of Trading Card Games (TCGs) 1 , which are an interesting hybrid between classical board games and card games.

In TCGs, which include popular games such as Yu-Gi-Oh! and Magic: The Gathering, players typically construct their own decks, selecting a subset of potentially thousands of published cards, each with differing effects, and place them onto a dynamically constructed field of play, where they act as the pieces of the game. Despite their interesting qualities, they have seen almost no attention from AI researchers, and this can be primarily attributed to the fact that resolving them is far from trivial. Besides, they are not easily modeled using the traditional Mini-Max or Monte-Carlo sets of strategies.

Both large-scale, hobby board games and TCGs are characterized by extremely broad, complex game states, which are manipulated by players who are able to take multiple actions on their turn (often as many as their available resources allow), and consist of both deterministic and stochastic elements. These elements cause these games to have extremely complicated game trees. They, thus, pose a particular challenge to established game playing strategies applicable for deterministic/stochastic games. To address these challenges, in this work, we introduce the concept of generalizing available actions into Representative Moves (RMs), and consider them in our search. While this will necessarily lead to unrealistic look-ahead in the game tree, the impact in decision making is far surpassed by the benefits in execution time and available search depth.

The remainder of the paper is laid out as follows. Section 2 describes the established techniques upon which we base our work, and Section 3 describes the novel concept of RMs. Section 4 describes the simplified TCG that we will use in our model, and how RMs can be applied to it. Section 5 describes our experimental design, and Sections 6 and 7 report our results and analysis. Lastly, Section 8 concludes the paper.

Background

The vast number of established search techniques for adversarial two-player and multiplayer games can be broadly divided into two paradigms, namely those of stochastic methods, such as the Monte-Carlo Tree Search (MCTS) algorithm and its many successful variants [START_REF] Gelly | Exploration Exploitation in Go: UCT for Monte-Carlo Go[END_REF][START_REF] Silver | Mastering the game of go with deep neural networks and tree search[END_REF][START_REF] Szita | Monte-carlo tree search in settlers of catan[END_REF], and the deterministic methods, generally based on the wellknown Mini-Max algorithm [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF][START_REF] Sturtevant | Multi-Player Games: Algorithms and Approaches[END_REF]. Both paradigms are based upon an intelligent, efficient, and informed search of the game tree, which refers to the set of game states reachable by each player making legal moves to alter the board. Mini-Max based approaches generally search to a selected ply depth, pruning sections of the tree using methods such as the well-known alpha-beta strategy, which will not impact its end state, thus enabling a deeper and more effective search with available computational resources [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF]. MCTS, and its many successful variants, such as the UCT algorithm, directs its search through random game playing, potentially weighted by learned or expert-provided strategies, and thus it determines the path to explore at each step via a bandit problem [START_REF] Gelly | Exploration Exploitation in Go: UCT for Monte-Carlo Go[END_REF].

Both of these paradigms must adapt when they encounter cases of imperfect information. For example, if applied to the game of Backgammon, the search must account for the fact that the available moves to each player, and therefore the efficacy of specific strategies, are partly based upon a roll of the die. In both these paradigms, this can be handled by the incorporation of "chance" nodes, which represent the possible, weighted outcomes of a random event [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF]. In the deterministic context, "chance" nodes are incorporated into the Mini-Max strategy in the Expectiminimax algorithm, where each node is assigned a score equal to its expected value, assuming players perform intelligently with the resources available to them [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF]. MCTS schemes can also incorporate "chance" nodes in the manner employed by the Expectiminimax [START_REF] Jouandeau | Monte-carlo tree reductions for stochastic games[END_REF]. Intuitively, the incorporation of "chance" nodes can seriously impact the performance of the search, as they lead to a much larger functional branching factor, and effective tree pruning, particularly in the deterministic case, where it becomes a much greater challenge.

While relatively simple random elements, such as rolling a die, can transform a simple search problem into a far more challenging one, these problems are exacerbated in the context of "hobby" board games, such as Settlers of Catan, and TCGs, which often have very complex random events and player moves made from of a wide range of individual parts. Current applications of game playing strategies to hobby games generally require a great deal of bias and expert knowledge to perform competitively [START_REF] Szita | Monte-carlo tree search in settlers of catan[END_REF]. This requirement necessarily limits the development of a domain-independent approach. In the context of TCGs, while a number of attempts have been made to play subsets, or accomplish specific tasks, in popular TCGs, to the best of our knowledge, no attempt to create a competitive TCG player exists in the literature. This is possibly because the number of available moves and random components involved are too daunting for current strategies, which do not rely heavily on expert knowledge. In this work, we will refer to these types of games as Complex Stochastic Games (CSGs).

As the extremely large number of "chance" nodes and branching factor of TCGs are a major hurdle in achieving competitive play, we suggest that an effective method for tackling them could be to simplify the game tree in some way. While this would have the effect of considering an invalid or incomplete game state, it may not be as catastrophic to do so as one may intuitively believe. This is analogous to what happens in the context of multi-player games. In recent years, the Best-Reply Search (BRS) has been shown to achieve excellent, competitive play, even through it explores invalid game trees [START_REF] Schadd | Best Reply Search for multiplayer games[END_REF]. The BRS is based on an observation that in a multi-player board game, the moves of the other players are not as important as the moves of the perspective player, and simplifies the turn order and search by considering all opponents as if they were a single "super-opponent", and searching as if the game had only two players [START_REF] Schadd | Best Reply Search for multiplayer games[END_REF] even though it considers invalid turn orderings. An example of this grouping in a single level of a BRS tree is shown in Figure 1. We propose an analogous strategy for CGSs.

Representative Moves

While there are many difficult challenges to overcome in achieving competitive game play in the domains of TCGs and hobby board games, a critical concern that severely hampers state-of-the-art techniques is the extremely large branching factors of these games, due to the wide range of possible decisions available to the player, and the presence of a substantial number of "chance" nodes in the game tree 2 . While traditional pruning methods can impact the branching factor, if there are hundreds of possible moves available to a player at each turn, their applicability will be limited. Therefore, it is worthwhile seeking out novel and radical methods for limiting the search space, to improve performance in these games. To achieve this, we propose the concept of Representative Moves (RMs).

The basic concept of RMs is as follows. In the scenario where a game, possibly, allows hundreds of moves, particularly when some are based on random chance, rather than considering all of these possible moves and their chance nodes, we, instead, consider a game model with only a much smaller set of moves. This smaller set of moves is "representative" of the total number available, standing in for "classes" of moves. They are either chosen representatives of their class, or some sort of average of the moves of that class. The classes of moves can be determined based on expert knowledge of the game's strategy, or potentially through unsupervised learning mechanisms. As a simple example, consider a game, similar to Backgammon, where during his turn, a player rolls two dice, and may advance two of his pieces by individual values shown on the pair of dice, towards a goal space. The player could move two different pieces, the same piece twice, reach the goal with one or two of his pieces, or perhaps, due to occupied spaces ahead, only move one, or even none of his pieces. These six types of moves could be the classes. Rather than consider all possibilities, we would consider these as RMs.

The main reason to do this is to limit the branching factor of the game. Instead of considering hundreds of available moves, we instead perform a search based upon distinct strategies available to the players at each level of the tree. Intuitively, by selecting only RMs at each level of the tree, we will be considering an incomplete version of the game tree, or, if averages are taken, potentially illegal board states. However, this is what the BRS does for multi-player games, and, despite this apparent weakness, it performs extremely well in the environments to which it applies [START_REF] Schadd | Best Reply Search for multiplayer games[END_REF]. When considering an exorbitantly large space, such as those associated with TCGs, this can potentially allow us to achieve a more substantial look-ahead, and faster search.

A disadvantage of using RMs is that a move, or random outcome, which is ignored, could be critical to formulating a winning strategy. Besides, it may not always be possible to properly select RMs. For example, in Chess, this technique would be unlikely to perform well, as it is difficult to strategically classify a player's available moves.

Game Model

The RMs paradigm was developed specifically to tackle the domain of TCGs, and therefore, it would be best to test its performance within the context of an actual TCG. However, due to the extreme complexity of these games, it is very difficult to implement an engine capable of fully capturing all their aspects. Therefore, in this exploratory work, we have created a custom TCG, designed to follow the conventions of the genre, while being a much simpler example than any on those available in market. TCG games generally represent a battle of some sorts, typically, in a fantasy or science fiction setting, with the names of cards, game mechanics, and so forth contributing to this story. Players draw cards from their own, customizable deck (with a unique set of rules for deck customization), and typically place these cards onto the "field of play", where they remain, functioning thereafter in a manner similar to game pieces, or have some effect and are then removed. For example, in a game like Magic: the Gathering, based on the concept of dueling wizards, a card could represent a dragon that could be summoned to battle, or a spell to destroy one of the opponents' summoned monsters. On each turn, a player can typically take as many actions as his cards would allow, plus some general-purpose acts, such as drawing a card from his deck.

In our custom TCG, each player has at their disposal a deck of twenty-five cards. As is typical of TCGs, each player has his own deck. However, in this case, the cards in each deck are identical. Two of these cards, when played, remove an opponent's card from the field immediately, and are then removed themselves; this is analogous to "Removal" cards in Magic: the Gathering. The other twenty-three represent "soldiers" of varying strength and quality, each having a value for "Fight", "Heal". and "Attack". Thus, each individual card can have different strengths and weaknesses. When played, these cards remain within the field of play, and afford the player additional actions on this turn and future turns, as is typical of TCG cards. The specific values of the "soldier" cards are chosen to provide an even spread of each value, with higher values being less common than lower values. The specific soldier cards are recorded in Table 1. Each player begins with fifty "Health Points" (HP), conceptually representing his remaining vitality. To begin play, each player draws five cards. Unlike a normal TCG, for the sake of simplicity, each player's hand is visible. During each turn, the player must first draw a card, unless this would cause him to have more than five cards in his hand. The player may then place a card from his hand onto the field of play 3 . Then, for each of the player's cards on the field, he may take one of the following actions:

1. Do nothing. 2. Increase his HP by the card's "Heal" value. 3. Decrease his opponent's HP by the card's "Attack" value. 4. Have this card do battle with another on the field. The card with the lower "Fight" value is removed. In the event of a tie, both are removed.

The first player whose HP is reduced to zero loses the game, and his opponent wins.

Experimental Design

While the concept of defining and utilizing RMs has intuitive value, its performance must be gauged in a quantitative manner so to ensure that the balance between its benefits and drawbacks supports its use in real game playing engines. The task of performing a formal analysis of game playing algorithms [START_REF] Sturtevant | Multi-Player Games: Algorithms and Approaches[END_REF] is well-known to possess extreme difficulties. Consequently, as is the accepted practice in the literature, we have chosen to verify its performance via experimentation. In this exploratory work, we will perform such an experimental verification using the custom TCG4 described above.

Our goals in verifying the performance of RMs are twofold. Firstly, we seek to confirm that the use of RMs does, indeed, save substantial amounts of search time. Secondly, we seek to determine whether this benefit in performance is obtained at the cost of effective game play, or whether this even improves the play. To do this, we first measure the execution speed of both a basic Expectiminimax algorithm, and also that of an Expectiminimax algorithm that employs RMs. More specifically, in this regard, we measure both the execution time, and the total number of leaf nodes expanded, where the latter serves as a "platform agnostic" metric. We then measure their performance against each other, over a number of games, to examine the impact of RMs on the win rate. We conduct this experiment both to an equivalent move depth, and thereafter to a greater depth whenever RMs are employed, if the latter is found to work faster.

To apply RMs to our custom TCG, we must first have some concept of how the classes of moves, and their representatives, are selected. Observe that in our custom TCG, each card (except the "Removal" cards) has a total of three values ("Fight", "Heal", and "Attack"), each of which represents a distinct strategy. Thus, when determining which card to play next, we consider three possible RMs, one for each of the three values. Each of these three moves has a value equal to the average of "Fight", "Heal", or "Attack", of all remaining cards in the player's hand and deck, with the value doubled for cards in the hand. This produces three "representatives", roughly corresponding to the player's current capacity in each of the three aspects of the game. This leaves us with the task of considering the "Removal" cards which function differently and which do not have three values. To factor them into our "representative" set, we observe that a "Removal" card has a purpose similar to a card with a high "Fight" value, that is, that of removing the opponent's cards from their field of play. We, therefore, consider each of the two "Removal" cards to be equivalent to a card with the values 5 "Fight", 0 "Heal", and 0 "Attack". Observe that this can "remove" almost anything from the field, but can do so only a single time. This is thus is not quite as good as the few cards which have 6 "Fight" values. This allows us to consider the "Removal" cards to be part of our three representatives.

For the sake of each of the players makes use of the same evaluation function. The evaluation function takes the player's "Health Points", and adds to it the total sum of all values, on all cards, on the player's field, divided by three. We subtract from this value a small factor which favours more "balanced" hands, thus encouraging the player to retain more strategic options. This factor is calculated by summing the three values on each card, and subtracting the lowest total value, from the highest (i.e., a card with "Fight" 3, "Heal" 1, and "Attack" 1 would have a sum of 5). The final value of the evaluation function is the difference between the perspective player's result, and his opponent's.

Our results are presented in the following section.

Results

Table 2 shows our execution time results for Expectiminimax when RMs were employed. In all cases, to ensure equivalent execution, each player had the starting hand 6/6/6, 2/1/1, 4/1/1, 2/3/2, and 1/3/3 ("Fight"/"Heal"/"Attack"). As expected from any game tree search algorithm, the runtime, and the number of leaf nodes examined, grow explosively as the ply depth is increased. Table 3 shows our execution time results for Expectiminimax when RMs were not employed. The same starting position was used, as with the previous experiments, to ensure consistency. As is immediately obvious, the use of RMs vastly cuts down the search space, with an Expectiminimax search to a ply depth of 3, taking much longer than one to a depth of 5 when RMs were not employed. At a greater depth, execution of the search showed no signs of halting after well over 30 minutes of execution time.

Table 4 shows our results when RM-enabled and Non-RM players faced each other, with equal search depths of 3. We found that, even when they were allowed only equiv- alent search depths, RMs achieved an 80% win rate over a non-RM search, winning with an average of 22.9 HP, and taking an average of 29.6 turns to finish the game. Table 5 shows our results when RM and Non-RM players faced each other, where the RM player was allowed to search to a depth of 5, given its proven efficiency. We found that, even allowed only equivalent search depth, RMs achieved an 72.7% win rate over a non-RM search, winning with an average of 19.9 HP, and taking an average of 26.2 turns to finish the game. The power of using RMs in the strategy is obvious!

Discussion

Our results very clearly demonstrate two things. First, the use of RMs significantly improves the speed and efficiency of the search. Secondly, despite considering only a small, representative portion of the complete game tree, not only does the use of RMs not hamper the strategic ability of the player in our custom TCG, but in fact, it achieves a noticeably higher win rate, compared to a player not using the RM technique.

Our first observation, about the speed of the search, is somewhat predictable. Indeed, the use of RMs converts a total of up to 25 possible cards that the player could place onto the field and which he must consider, into a total of three. However, it is still striking to observe how extreme the change is. Even comparing a search to a ply depth of five, using RMs, to a search to a depth of three, not using RMs, the RM-enabled search is two orders of magnitude faster. It also considers three orders of magnitude fewer leaf nodes. This result clearly demonstrates that the use of RMs can, indeed, enable a search to a much greater depth, in the same available processing time. The second observation is far more interesting. Our original, stated goal was to demonstrate that the use of RMs does not reduce the strategic capabilities of the Expectiminimax algorithm. However, we observed that it, in fact, regularly defeated a player who does not use it. More importantly, this effect was observed even when the primary predicted benefit of RMs, i.e., the faster search, was not factored in, to allow it to search deeper in the tree. This is a very interesting and unexpected, result. A possible explanation for this is that considering only the primary strategic factors of the game, rather than individually considering every possible card, RMs enabled a more focused search on the game's components. The RM technique did not perform better at a larger search depth, although given the restricted number of games we could play to completion (due to how slow the non-RM player was), this may easily be due to random chance.

We observed that in both experiments, the RM player would, on average, end the game with a similar (20 -23) HP score, and that the game would take a similar (26 -30) number of turns to complete. Examining individual cases, however, we observe some scenarios where the game took much longer, up to 56 turns, to finish, and some scenarios where the winning player would have a much higher, or lower, HP score. The highest winning HP score was 59, and the lowest was 6. Given that our custom TCG provides the ability for cards to "Heal" the player, it is likely that the cards drawn in games that either took a long time, or ended with high HP scores, had a much higher "Heal" value than other available cards. Conversely, whenever the winner won with a low HP score, it is likely that both opponents entered into a scenario where they had cards with high "Attack" values, and attempted to race to defeat each other. This balance of aggressive and defensive play is typical of real TCGs, such as Magic: the Gathering, and suggests that our custom TCG does, indeed, capture some of their strategic qualities.

Conclusions and Future Work

Our results in this paper very clearly demonstrate that, although it considers only a portion of the game tree, the use of RMs is capable of achieving competitive game play, with equivalent techniques that do not employ it. RMs are also capable of vastly improving the execution time of the search. Although we have done an examination of RMs in the context of Expectiminimax, it is also applicable to MCTS, and an examination of its capabilities in such settings is a possible avenue of future work.

In this work, we calculated the RMs based upon domain-specific knowledge of the game tree. However, as we briefly touched upon in Section 3, it would be possible to find classes of moves using an unsupervised learning technique, and elect specific representatives from the classes. Further, while our custom TCG replicates some of the strategic concerns of a real TCG, it is much simpler than the ones accessible in the market. It would be very interesting to examine the capacity of RMs in a realworld TCG, although significant work would need to be done in formalizing the game engine, before this would be possible. Finally, we believe that other non-TCG games, like Settlers of Catan, or Backgammon, could potentially benefit from the use of RMs.

Fig. 1 :

 1 Fig. 1: The operation of a single level of the Best-Reply Search. The scores that are reported have the opponent's player number listed next to them (in parenthesis) to assist in the clarification.

Table 1 :

 1 Statistical values of cards in our custom TCG.

	Fight Heal Attack Fight Heal Attack Fight Heal Attack
	1	1	1	1	1	2	1	0	3
	2	2	2	3	2	2	0	4	4
	3	3	3	1	1	5	4	4	0
	4	4	4	6	0	0	3	3	0
	4	0	3	3	3	2	1	3	3
	2	4	2	4	0	4	4	1	1
	0	0	7	2	4	1	6	6	6
	4	1	0	5	1	0	-	-	-

Table 2 :

 2 Execution time when RMs are employed.

	Depth Runtime (ms) Leaf Nodes
	3	108	3,100
	4	246	62,400
	5	2,200	238,100

Table 3 :

 3 Execution time when RMs are not employed.

	Depth Runtime (ms) Leaf Nodes
	3	132,100	263,836,900
	4	Inf.	Inf.

Table 4 :

 4 Games between RM and non-RM players at equivalent search depth.

	Winner RM final HP Non-RM final HP Number of Moves
	RM	25	-2	26
	Non-RM	-3	28	24
	RM	37	0	22
	RM	59	-2	45
	RM	6	-1	24
	RM	21	-3	16
	RM	20	-1	21
	RM	40	-2	20
	Non-RM	-5	11	42
	RM	29	0	56

Table 5 :

 5 Games between RM and non-RM players at differing search depths.

	Winner RM final HP Non-RM final HP Number of Moves
	RM	8	-1	16
	Non-RM	0	16	32
	RM	54	0	33
	RM	18	-1	21
	RM	29	-2	17
	RM	24	0	24
	RM	8	-5	25
	Non-RM	-2	42	26
	Non-RM	-5	15	26
	RM	41	-1	36
	RM	44	-1	32

As an example, in a TCG deck, there may be twenty or more possible cards, each with a different functional purpose, which the player could draw on any turn.

In a typical TCG, the ability to put a card onto the field of play is limited by some form of resource, often obtained from other cards. Thus, careful deck construction is an important consideration, as powerful cards are of no strategic use if they cannot be played. As our game does not factor in deck construction, we have omitted resource cards from the game.

We apologize for the detailed description of the game's moves, but it is necessary to clearly describe our work.


Castillejos

M Lopez-Suarez

E Armengol

S Calsamiglia
email: sergio.calsamiglia@uab.cat

L Castillejos
email: lorena.castillejos@uab.cat

Using Decision Trees to Extract Patterns for Dairy Culling Management

Keywords: Veterinary, Dairy farms, Milk production, Voluntary Culling, Artificial Intelligence, Machine Learning, Decision Trees

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

Introduction

To be highly productive a dairy farm needs good management. There are many complex technical and economic decisions that have to be taken in order to maintain or increase the productivity. Direct benefits of a dairy are those coming from either milk or animal sales. However, raising a cow has also many costs that should be discounted from these benefits (feeding, labor, veterinary care, depreciation of facilities, utilities, etc).

Culling is the departure of cows from the herd due to sale, slaughter or death. The main reasons to cull a cow are infertility, mastitis and poor milk production. Commonly, culling reasons have been classified as voluntary or involuntary or, as suggested by Fetrow et al. [START_REF] Fetrow | Culling: Nomenclature, definitions, and recommendations[END_REF], economic or biologic. Biological culls are those cows for which no possible productive future exists due to disease, injury or infertility. Thus, this class of culls are mainly involuntary as most of the times are "forced" decisions. Economic culls mean that a cow is removed because a replacement is expected to produce greater profit. In this case, farmer has freedom of choice over which cows are removed from the herd, although they are healthy [START_REF] Fetrow | Culling: Nomenclature, definitions, and recommendations[END_REF][START_REF] Ansari-Lari | Causes of culling in dairy cows and its relation to age at culling and interval from calving in Shiraz, Southern Iran[END_REF]. Hence, the farmer can do a voluntary selection of cows to cull based in the herd size and herd production level. Therefore, herd profitability can be improved by minimizing the proportion of the herd culled for involuntary or biological reasons and maximizing the proportion culled for voluntary or economic reasons [START_REF] Ansari-Lari | Causes of culling in dairy cows and its relation to age at culling and interval from calving in Shiraz, Southern Iran[END_REF]. Because it is important to know as soon as possible if a cow will be poorly productive, we propose to analyze first lactation production data to identify those animals in a herd which are candidates to be culled following milk yield improvement criteria.

For such a purpose, in the present paper, we used Decision Trees (DT) [START_REF] Quinlan | Induction of decision trees[END_REF], an Artificial Intelligence technique that allows the classification of objects, to extract patterns for making decision support during the culling process. This is our main contribution since the use of these patterns is an easy and understandable way to support the farmer in culling decision making. A DT represents a model of a given domain that can be used for classification tasks. Thus, given the description of a cow, a DT could classify her as Good or Bad, supporting in this way the culling process. In Section 2 we briefly revise some works that use Artificial Intelligence technologies for dairy management. Section 3 explains how we have modelled the culling task, and the data base we used in our experiments (Section 3.1). Section 4 explains our results, and in Section 5 these results are discussed. Finally, Section 6 is devoted to conclusions.

2

Related work

Most of the work focused on modelling the culling task or aspects related to it, try to construct statistical models based on the analysis of past cases of a dairy [START_REF] Calsamiglia | A dairy farm simulation model as a tool to explore the technical and economical consequences of management decisions[END_REF]. The use of artificial intelligence techniques is still not widely used for managing the culling although they have been used for other purposes. For instance, Cavero et al. [START_REF] Cavero | Mastitis detection in dairy cows by application of fuzzy logic[END_REF] developed a fuzzy logic model for mastitis detection; [START_REF] Sun | Detection of mastitis and its stage of progression by automatic milking systems using artificial neural networks[END_REF][START_REF] Wang | On-line detection of mastitis in dairy herds using artificial neural networks[END_REF] are some examples of using neural networks for classification and control of mastitis in cows milked using an automatic milking system; Shainfar et al. [START_REF] Shahinfar | Prediction of breeding values for dairy cattle using artificial neural networks and neuro-fuzzy systems[END_REF] used fuzzy neural networks to predict breeding values for dairy cattle; Grzesiak et al. [START_REF] Grzesiak | Methods of predicting milk yield in dairy cows: Predictive capabilities of wood's lactation curve and artificial neural networks (ANNs)[END_REF] also used neural networks to predict milk production; Sugiono et al. [START_REF] Sugiono | Investigating the impact of physiological aspect on cow milk production using artificial intelligence[END_REF] built an adaptive system (BPNN) to predict performance of dairy cattle based on environmental and physical data; and Sitkowska et al. [START_REF] Sitkowska | Detection of high levels of somatic cells in milk on farms equipped with an automatic milking system by decision trees technique[END_REF] used decision trees to predict the increment of the levels of somatic cells in milk. Thus, to our knowledge, Artificial Intelligence techniques and, particularly, decision trees, have not been used to support the decision of culling the herd. Also the multi-agent technology has been used in dairy farms to support the process of decision making in several aspects of a dairy farm. For instance, Parrot et al. [START_REF] Parrott | Design considerations for the implementation of multiagent systems in the dairy industry[END_REF] investigated the feasibility of using a multi-agent system for heifer management; Thangaraj et al. [START_REF] Thangaraj | Modelling a multi agent system for dairy farms for integrated decision making[END_REF] used a multi-agent system to make integrated decisions taking into account pasture availability, nutrients, and herd economic aspects. Goel et al. [START_REF] Goel | A multi-agent system for supporting the electronic contracting of food grains[END_REF] also developed a multiagent system to implement electronic contracting of food grains integrating various millers and producers in a food supply chain for better negotiations to reach a mutually acceptable price.

The approach we propose uses decision trees, a technique that, as far as we know, has not been used before in dairy management although Kamphuis et al [START_REF] Kamphuis | Detection of clinical mastitis with sensor data from automatic milking systems is improved by using decision-tree induction[END_REF] used decision trees to improve the detection of clinical mastitis with sensor data from automatic milking systems.

Most of the mentioned studies using Artificial Intelligence technologies employed neural networks and fuzzy logic. This is mainly due to real time needs, since they deal with problems that need to be solved in a short time. However, we considered that, for the objective of this study, the use of inductive learning methods to construct a domain model could be a better approach. Inductive models, differently than neural networks, can explain the results they provide since the descriptions used to classify an object can be interpreted as an explanation of the result. This is an interesting characteristic as it enables the final user to completely understand how an automatic system has reached the solution it proposes. For this reason, our approach can contribute to support the farmer in taking more informed decisions when he needs to cull his herd.

Modelling the Culling Task

In this paper we propose the use of inductive learning methods to construct a model able to predict and explain why a cow should be culled during her first lactation. The goal of inductive learning algorithms is the construction of a domain theory from the known data.

Commonly this domain theory is further used to predict the classification of unseen objects.

To characterize each one of the classes of the domain by means of discriminatory descriptions we have to solve the so-called discrimination task. Given a solution class C i , the discrimination task for inductive learning methods is defined as follows:

-Given: a set E of positive E + and negative E -examples of a class C i .

-Find: a description D i such that it is satisfied by elements in E + and it is not satisfied by any of the elements of E -.

The discrimination task produces discriminatory descriptions, i.e., descriptions satisfied only by objects of one of the classes. A class C i can be described by more than one discriminatory description D i . To build a model of a domain we have to perform the discrimination task over each one of the classes. In that way, the model is composed of descriptions that can classify univocally an object as belonging to a class. One of the widely used inductive learning methods are the Decision Trees (DT). The goal of using DT is to create a domain model predictive enough to classify future unseen domain objects. The leaves of a tree determine a partition of the original set of examples, since each domain object only can be classified following one of the paths of the tree. The construction of a decision tree is performed by splitting the source set of examples into subsets based on an attribute-value test. This process is repeated on each derived subset in a recursive manner. Figure 1 shows the ID3 algorithm [START_REF] Quinlan | Induction of decision trees[END_REF] commonly used to construct decision trees. The path from the root to each one of the leaves of a decision tree can be seen as a description of a class. When all the examples of a leaf belong to the same class the description is discriminatory, otherwise it is non-discriminatory. In our experiments we implemented our own version of the algorithm in Fig. 1 in order to control overfitting and also to construct the patterns from the tree paths.

Decision trees can be useful for our purpose because their paths give us patterns describing classes of objects (cows in our approach) in a user-friendly manner. One shortcoming of decision trees is overfitting, meaning that there are few objects in most of the leaves of the tree. In other words, paths are actually descriptions that poorly represent the domain. The main procedure to either avoid or reduce overfitting is by pruning the tree, i.e., under some conditions, a node is no longer expanded. However, this means that leaves can contain objects belonging to several classes and, therefore, paths do not represent discriminatory descriptions of classes, i.e., these descriptions are satisfied by objects of more than one class. In our approach, we managed overfitting by controlling the percentage of elements of each class. Let S N be the set of objects associated with an internal node N, the stopping condition in expanding N (the if of the ID3 algorithm) holds when the percentage of objects in S N that belong to the majority class decreases in one of the children nodes. In such a situation, the node N is considered as a leaf.

The Data Base

We used a data base containing 97987 objects. These objects are descriptions of Holstein-Frisian cows which lived from 2006 to 2016, belonging to dairy farms within the CONAFE register system 3 . Nowadays, most of farms have automatic systems to collect data, so there is a lot of information about each cow (genetics, production, morphology, reproductive indexes, disease control, etc.). In addition, most of farms pass a monthly control in which, for every lactating cow, the day milk yield is registered and a milk sample for analyses is taken. Therefore, the first step we carried out was to select which pieces of this information could be useful to detect as soon as possible poorly productive cows. To reach this goal, we decided to use only information relative to the first lactation. The attributes we considered for every cow were the following one:

-BirthMonth. Month (season) in which the cow was born. -Production/DIM: Average daily milk production of the first lactation (kg/day) calculated dividing total amount of milk produced by a cow during the whole lactation by the total days in milk (DIM).

Table 1. Intervals corresponding to each quartile of the attributes KgMilkPeak and Production/DIM

For the attributes BirthMonth and Month1Calving we divided the months according to seasons. All the remaining attributes have numerical values and we have discretised them. For all of them, we calculated the quartiles and divided the whole interval of values in four according to these quartiles. We associated to each of the 4 quartile interval the labels: VeryLow (VL), Low (L), High (H), and VeryHigh (VH). Table 1 shows the quartiles of the attributes KgMilkPeak and Production/DIM. For instance, for attribute KgMilkPeak, the interval from 5 to 28 of milk average during the lactation peak, means that the cow has had very low milk production (VL). We considered Production/DIM as the solution class, i.e., the decision tree will model and predict the first lactation milk production performance of a cow (kg/day).

Results

We used the whole data base as input for a decision tree algorithm to obtain patterns (the tree paths) describing the classes of cows according to the values of the attribute Production/DIM. The resulting tree was formed by patterns that are discriminatory and by patterns that are not (due to the stopping condition explained in previous section). Figure 2 shows an example of discriminatory pattern formed by 6 attributes (KgMilkPeak, Kl, Morpho, Month1Calving, AI, and Fat). This pattern is satisfied by 104 cows, where the 93.27% of them have a very low Production/DIM and the 6.73% of them have a low Production/DIM. None of the cows satisfying this pattern has Production/DIM high or very high. For model evaluation purposes, we decided to consider two final solution classes: Good formed by cows with Production/DIM high or very high; and Bad formed by cows with Production/DIM low or very low. This is because the actual goal is to identify the less productive cows of the herd, Therefore, the pattern in Fig. 2 classifies all the cows that satisfy it as Bad with a 100% of predictability. Once the good cows have been separated, a more fine procedure could be used to select which of the bad cows are the worst. In fact, this procedure could depend on factors different for each dairy. According to this pattern, all these cows will be classified as Bad.

Attribute

We evaluated the model using 10-fold cross-validation. Therefore, the whole data base has been divided in 10 parts. In each experiment we taken 9 of these parts to generate the patterns and the remaining part has been used as test on which we estimated the accuracy of the model. After the 10 experiments we obtained a mean accuracy of 84.10% in classifying a cow as Bad or Good.

We also tested the developed model using a different data base to check if the set of patterns shown in Table 2 could be used to classify the cows, using the same criteria, on any farm. For this test, we took a data base with information about 5474 cows different from the ones used during the construction of the model. In fact, these cows were alive from 1999 to 2006. We divided the data base in subsets of around 500 cows, and each subset was discretised according to the quartiles of the own subset. Then we used the patterns in Table 2 to classify the cows of each subset simulating, in that way, the difference between dairies. The mean accuracy of classification in this test was 82.72%. Comparing both this accuracy with the one from the 10-fold cross-validation (84.10%) we can conclude that it is feasible to use the model obtained from the data base of around 98000 since it provides good patterns for the classification of cows coming from different farms.

Discussion

All the patterns composing the model in Table 2 explain that milk production (kg/day) in the lactation peak of the first lactation (KgMilkPeak) of a cow is directly related to the average milk production (kg/day) of the whole first lactation (Production/DIM). This result is very interesting as the performance of a cow in her first lactation can be predicted in early lactation stages instead of having to wait until the end of the lactation (after 9 to 14 months). This is especially interesting to take early decisions about culling since, with around a 97% of predictability, poorly productive cows of a herd can be early detected. Therefore, the model composed by patterns that take into account only the attribute KgMilkPeak is a good predictor of the first lactation production of a cow. We also performed a statistical analysis to compare the results of the DT model with the statistical one. Table 3 shows that all the variables included in the model were significant

Fig. 1 .

 1 Fig. 1. ID3 algorithm for growing a decision tree.

-

  Month1Calving: Month (season) of the first calving of a cow. -Kl: Milk production genetic index. -ICO: Official cattle breeding index in Spain. -Morpho: Morphologic qualification of a cow. -KgMilkPeak: Average test-day milk yield (kg/day) of the second and third control of the first lactation (lactation peak). -Fat: Fat average percentage from the second and third controls of the first lactation. -Protein: Protein average percentage from the second and third control of the first lactation. -SCC: Somatic cell count in the milk. It is an indicator of the quality of milk as it expresses the likeliness to contain harmful bacteria. -OpenDays: Days from calving to conception. -Calving1stAI: Interval of days between the first calving and the first insemination after it. -AI: Number of artificial insemination attempts to conceive after the first calving.

Fig. 2 .

 2 Fig. 2. Discriminatory pattern satisfied by 104 cows having Production/DIM low or very low.According to this pattern, all these cows will be classified as Bad.

The Confederacion Nacional de la Raza Frisona (CONAFE) is a Spanish entity whose goal is to develop programs oriented to the improvement and selection of the Holstein-Frisian herd.

Acknowledgments

The authors acknowledge data support from CONAFE (Confederacion Nacional de la Raza Frisona). This research is partially funded by the projects (Project AGL2015-67409-C2-01-R) from the Spanish Ministry of Economy and Competitiveness; RPREF (CSIC Intramural 201650E044); and the grant 2014-SGR-118 from the Generalitat de Catalunya. Authors also thank to Àngel García-Cerdaña his helpful comments.

The model in Table 2 supports to split the herd in two groups corresponding to Good and Bad cows, regarding first lactation production. Once the Good cows have been separated, a next step to take could be the addition of more specific patterns to select which of the Bad cows are the worst. We could use, for instance, patterns including the next more relevant attribute which, as in the statistical model, is Kl. An example of such a pattern is [[KgMilkPeak, L], [Kl, VL]] satisfied by 7145 cows, the 89.85% of them are Bad and the remaining 10.15% are Good. This example shows the advantage of the DT model compared to the statistical model since the latter only shows that both KgMilkPeak and Kl explain the 74.36% of Production/DIM, whereas by using the patterns from the DT model, we know the range of values in both KgMilkPeak and Kl (L and VL respectively) that support the decision of culling a cow.

Conclusions

In the present work we used decision trees to obtain patterns supporting the culling decision process of a dairy farm. From a data base with around 98000 cows, we obtained a model formed by 4 patterns that predicts the milk production of a cow on her first lactation (Production/DIM). By using this model, Production/DIM can be predicted based on milk yield records from first lactation peak (KgMilkPeak) with an 84% of accuracy after one trial of 10-fold cross-validation, and 83% of accuracy on different dairy farms. This result is consistent with the statistical model constructed from the same data base, which shows a high correlation between both variables (Production/DIM and KgMilkPeak). Thus, the model could be a helpful tool for the decision of culling a cow in early stages of her lactation since, poorly productive cows can be identified using a pattern that has a predictability of around 97%.