Discrete Graphic Markov Model selection by a Genetic Algorithm: empirical comparison of two Fitting Convex Functions

ELVA DÍAZ DÍAZ
Electronic System Department, Basic Science Center
Universidad Autónoma de Aguascalientes,
Ave. Universidad # 940 CP. 20 100,
Aguascalientes, Aguascalientes, 
MÉXICO

EUNICE E. PONCE DE LEÓN SENTÍ
Electronic System Department, Basic Science Center
Universidad Autónoma de Aguascalientes,
Ave. Universidad # 940 CP. 20 100,
Aguascalientes, Aguascalientes,
MÉXICO

Abstract: - The problem treated is the comparison of the performance of two different fitting index, defined based in Information Theory criteria (Kullback-Leibler and Akaike) for the genetic algorithm. Samples of known models are generated with the IPF modified algorithm. As the true model is known, the performance is assessed through the percent of true edges of the true model in the best model selected by the algorithm. An experiment is designed to select the best combination of parameters of the considered genetic algorithm, and nine known models of different complexities are used to assess the performance of the genetic algorithm with each of the two fitting criteria. As results the genetic algorithm with the convex fitting index (CFI) find more or equal (equal only in one case) number of correct edges than the mixed fitting index (MFI), the better performance of the genetic algorithm occurs always selecting 60 percent of the best population individuals for reproducing the next population, the edges of the sparse models are more difficult to find for any of the fitting indexes than the edges of the medium and dense models. The more complex the models are, the better the performance of the algorithm is. The significant factors were: the fitting indexes, the percent of the best individuals selected to reproduce, and the complexity of the models.   

Key-Words: - Complexity, Genetic algorithm, Information criterion of fitness, Sample random generation, Graphical models, Contingency tables.

1   Introduction
The objective of this paper is to test the conjecture in [3] about the performance of two algorithms for models selection based on two different model fitting indexes. The case of graphic log-linear models for contingency tables, named Discrete Graphic Markov Models for binary variables is considered.  By selection of models is meant to find a graphic model (or more than one) that has the minimum Kullback-Leibler [8] distance to a sample, and at the same time has the least number of edges. In this article the study of the performance of an alternative model selection method for contingency tables based on a genetic algorithm constructed as in [3] is studied from a different point of view. In [3] the samples used, were classic examples from the literature and the performance was assessed by the number of times the algorithm finds the same model selected by the conventional methods, based on testing of hypothesis. In this paper the samples are generated by a known model using the IPF modified algorithm given in [4] and the performance is assessed counting the percent of the edges of the model that the algorithm obtains. Two different information criteria are used to define the fitting function for the genetic algorithm [7], the convex fitting index (CFI) and the mixed fitting index (MFI). In [3] the performance of the genetic algorithm using the CFI was better than the performance using the MFI. Samples of the known models are generated with the algorithm proposed in [4], and an experimental design is performed to compare the two information criterion. Following the same criteria of complexity defined in [3] and [5] we characterize the models as sparse, medium and dense. A factorial experiment is designed to select the best combination of parameters of the genetic algorithm, and to compare the two fitting criteria defined, nine samples generated by nine known models are used, to study the performance of the algorithms. 

2   Information Measures of fitting
Two convex fitting functions are defined based on Information Theory criteria (Kullback-Leibler and Akaike). They include a model simplicity restriction, which acts as a penalty taken account of the number of edges of the graph. 

Let  be the likelihood ratio statistic for a sample of size n from a multinomial distribution, where  is the maximum likelihood estimate assuming that the true model is. The log likelihood ratio in the multinomial case is
  
Definition: The convex fitting index for the model  is defined as in [3] by

where,

             (4)

and where  is the equiprobability model, is the number of edges of the model ,  is the maximal number of edges formed with   vertices, and  is a weighting coefficient which express the compromise between the fitting and the simplicity requirements of the model.

Definition: The Akaike Information Criterion [1] for the model is defined as

Definition: The mixed fitting index for the model is defined as

  (6)

3   Methodology
In this section the different components of the algorithms are described. In order to perform the selection of models comparison using the two different fitting indexes, we need the algorithms described in the following sub-sections. In the sub-sections 3.1 the genetic algorithm for models selection, and in sub-section 3.2 the modified iterative proportional algorithm are described.

3.1 Genetic Algorithm for the Model Selection
The algorithm can be sketched as follows: 

choose an initial population
determine the fitness of each individual
perform selection of individuals to be reproduced
repeat
  perform crossover
  perform mutation
  determine the fitness of each individual
  perform selection of individuals to be   reproduced
until some stopping criterion applies

Algorithm components:

Initial population: We form the initial population taken one edge out in all possible ways from the complete graph for the total of vertices. If the number of vertices is m the number of models in the initial population is m(m - 1)/2.
.
Fitting: The fitting criterion evaluates an individual in order to assess how near to the sample from the true model it is. For this task one of the two fitting criteria CFI or MFI could be used.

Selection:    A percent of the best fitted models of population   t   is selected to generate the population t + 1. This parameter is denoted by p.

Genetic Operators: In a random fashion the algorithm decides to do mutation (with probability pm) or crossover (with probability 1 - pm). The crossover and mutation operators are defined in [3].

3.2 Modified Iterative Proportional Algorithm
In [4] a modified iterative proportional fitting is presented to generate a table P of probabilities from a discrete graphic Markov model structure. The iterative proportional fitting algorithm, IPF [2] is modified to obtain a numerical table of probabilities, denoted as PIPF (S), of the family given by the restrictions of the structure model S. In this paper this algorithm is used to generate a frequency sample, FIPF (S) of the model structure S. 

A pseudo code for the algorithm:

Read the number of random variables (total entries of the contingency table).
Read the structure of the Graphic-Model S (list of strings).  
Generate the frequency table FIPF (S) using the modified IPF.

A pseudo code for the modified IPF:

Generate a first table at random without restrictions.
Adjust a table to the margins of the given structure of the Graphic Model using the IPF.
Substitute the old table with the new adjusted table.
Repeat until some convergence criterion holds.

4 Experimental design
To compare the two fitting functions, CFI and MFI, a factorial experiment was designed and run, consisting of three factors for the genetic algorithm: percent of the best individuals selected to reproduce in the next generation, percent selected to mutate, and the weighting coefficient for the fitting indexes, two factors for the complexity of the models structure: the first factor is the number of variables (vertices of the graph), with levels, 6, 8 and 10; the second factor is given by the conditional independence restrictions (Markov graph) with levels dense, mean and sparse. For each of the nine FIPF (S) table generated, and each fitting index the genetic algorithm was run 20 times to select the best model with respect to one of the fitting indexes.   
The used algorithms and the design runs are programmed in C++ and executed in a Pentium IV PC at 1.6 MHz.
Results:
(a) For all combinations of factors of the design models, considering each FIPF(S) table as a sample, the strategy of model selection backward, programmed in MIM [6] obtains the corresponding model structure of depart S. 

(b) The genetic algorithm with the convex fitting index (CFI) find more or equal (equal only in one case) number of correct edges than the mixed fitting index (MFI). (See Table 1)  

(c) The better performance of the genetic algorithm occurs always selecting 60 percent of the best population individuals for reproducing the next population. (See Table 1)  

(d) The edges of medium and dense models are easier to find for the 8 and 10 variables. The edges of the sparse models are more difficult to find for any of the fitting indexes than the edges of the medium and dense models. (See Table 1)  

 (e)  The significant factors were: the fitting indexes, the percent of the best individuals selected to reproduce, and the complexity of the models.   

5 Conclusions
The CFI fitting index performance is better than the performance of the MFI fitting index; hence the conjecture in [3] is false. The result (a) is the same as found in [4]. The result (b) is coherent with the one reported in [3], the difference is that in [3] the assessment of the performance was with respect to classic examples where the true models were unknown. The result (c) is coherent with the one obtained in [3]. The result (d) means that the more complex the models the better performance of the algorithm and in (e) are the principal results, especially that the performance of the algorithm depends on the complexity of the model. Interesting is that the more complex the model is, the better performance the algorithm has. The new results that appear in this experiment, when we know the true models in advance, and generate the samples to test the algorithms performance, are related to the complexity of the models. Results about this will be the object of a next paper.   

References:
[1] Akaike, H. (1974) A new look at the statistical model identification. IEEE Transactions on Automatic Control, 19: 716-23.

[2] Darroch, J.N., Ratcliff, D. (1972) Generalized iterative scaling for log-linear models. Annals of Mathematical Statistics, 43: 1470-1480.

[3] Díaz, E., Ponce de León, E. (2002) Discrete Markov Model Selection by a Genetic Algorithm. En: Avances en Ciencias de la Computación e Ingeniería de Cómputo. Ed. Sossa Azuela J. H et al, Vol II:315-324. Mexico. CIC 2002.

[4] Díaz, E., Ponce de León, E. (2004) Modelling and Simulating Complexity for Discrete Graphic Markov Models: an experimental study. WSEAS Transactions on Mathematics. Issue 1.,Vol. 3. January 2004, 288-291.

[5] Edmonds, B. (2003) What is Complexity?: the   philosophy of Complexity per se with application to some examples in evolution, in F. Heylighen, J. Bollen & A. Riegler (eds.) The evolution of Complexity, Kluwer, Dordrecht.

[6] Edwards, D. (2000) Introduction to Graphical Modeling. Springer-Verlag. New York.

[7] Goldberg, D.E. (1989) Genetic algorithm in Search, Optimization and Machine Learning. Reading: Addison-Wesley.

[8] Kullback, S. (1959) Information Theory and Statistics. John Wiley and Sons, New York. 

TABLE 1.  Genetic Algorithm performance: CFI and MFI comparison. 
MO
DELS
	MODEL’S CONFIGU
RATIONS 	MO
DEL’S ED
GES	CFI 
ED
GES %	MFI
 ED
GES
 %	CFI PARAME
TERS
(1)     (2)     (3) 	
6 VAR.
SPARCE	AB
BC
CD
DE
EF	5	80	40	0.6    10     0.3
	
6 VAR.
ME
DIUM	ABC
DEF
AF	7
	100	86	*	
6 VAR.DEN
SE	BF
ABCDE	11	100	100	*	
8 VAR.
SPARCE	ABC
CD
DH
EF
GH	7	70
	70	0.6    10     0.3	
8 VAR.
ME
DIUM	ABCD
AGH
EFG	12	92	67	0.5     15    0.5
	
8 VAR. 
DEN
SE	ABCDE
AGH
FGH
EF	16	100	75	*	
10 VAR.
SPARCE	AB,  BC, CD, DE, EF, FG, GH, HI,  IJ	9	44	11	0.6     10    0.3	
10 VAR.
ME
DIUM	ABCDE
AIJ
GHI
EFG	19	95	74	0.6     20    0.5	
10 VAR.
DEN
SE	ABCDEF
AIJ
HIJ
GHI
FGH
AHI	25	96	76	0.6     10    0.3	

*   find the correct model for all factors combinations

(1)	Proportion of the best individuals selected to reproduce.
(2)	Percent of individuals selected to mutation.
(3)	Proportion index in the convex function.