CategoricalEntailmentEnsembleOptimizationContext Class

Class CategoricalEntailmentEnsembleOptimizationContext derives from SystemPerformanceOptimizationContext, and defines a Cross-Entropy context able to solve optimization problems regarding the selection of an ensemble of categorical entailments, i.e. objects defining collections of premises, about a given set of feature variables, that imply a specific response category, with the conclusion entailed by the premises with an eventually partial truth value, ranging between completely false to completely true.

Categorical entailments can be exploited when items from a given feature space must be classified into a set of labels. If feature categorical variables are taken into account, and if variable has finite domain , then can be represented as the Cartesian product . A categorical entailment is a triple , where is a proper subset of representing the entailment premises (, with ), is the concluded response category, and is the entailment truth value.

Class SystemPerformanceOptimizationContext thoroughly defines a system whose performance must be optimized. Class CategoricalEntailmentEnsembleOptimizationContext specializes that system by assuming that its performance, say , is defined on a collection of possible entailments about specific features and response variables in a given categorical data set.

Let be the number of entailments to be selected. For , let be the number of categories in the domain of the -th feature, say , and let be the number of categories in the response domain, say . An entailment can be represented by a partitioned row vector, say , whose blocks are defined as follows. For , , with being unity if the -th category of is included in the corresponding premise , zero otherwise, or, using indicator functions,



while block is a binary vector in which, using indicator functions,



i.e., there is only one entry equal to unity corresponding to the feature category concluded by the entailment.

An argument for the Cross-Entropy program hence admits the partitioned form , having dimensions , with being the overall number of available feature categories. Given a DoubleMatrix instance representing an argument, the collection of CategoricalEntailment instances it represents can be inspected by calling method GetCategoricalEntailmentEnsembleClassifier(DoubleMatrix, ListCategoricalVariable, CategoricalVariable).

The system's state-space , i.e. the domain of , can thus be represented as the Cartesian product of copies of the set , with the last closed interval representing the range of available truth values.

A Cross-Entropy optimizer is designed to identify the optimal arguments at which the performance function of a complex system reaches its minimum or maximum value. To get the optimal state, the system's state-space is traversed iteratively by sampling, at each iteration, from a specific density function, member of a parametric family



where is a possible argument of , and is the set of allowable values for parameter . The parameter exploited at a given iteration is referred to as the reference parameter of such iteration and indicated as . A minimum number of iterations, say , must be executed, while a number of them up to a maximum, say , is allowed.

Implementing a context for optimizing on categorical entailments

The Cross-Entropy method provides an iterative multi step procedure. In the context of combinatorial optimization, at each iteration a sampling step is executed in order to generate diverse candidate arguments of the objective function, sampled from a distribution characterized by the reference parameter of the iteration, say . Such sample is thus exploited in the updating step in which a new reference parameter is identified to modify the distribution from which the samples will be obtained in the next iteration: such modification is executed in order to improve the probability of sampling relevant arguments, i.e. those arguments corresponding to the function values of interest (See the documentation of class CrossEntropyProgram for a thorough discussion of the Cross-Entropy method).

When the Cross-Entropy method is applied in an optimization context, a final optimizing step is executed, in which the argument corresponding to the searched extremum is effectively identified.

These steps have been implemented as follows.

Sampling step

In a CategoricalEntailmentEnsembleOptimizationContext, the parametric family is outlined as follows. Each component of an argument of is attached to a parameter , and the Cross-Entropy sampling parameter is a partitioned row vector whose parts are those blocks, each one governing the sampling of a different entailment as follows. Firstly, a finite discrete distribution is defined on the label domain and sampled to obtain label . Secondly, the entailment premise must be sampled too. This is equivalent to select at random, for each input attribute , a subset of domain , and hence define : to obtain such result, a Bernoulli distribution, say , is assigned to each category in the attribute domain : sampling from enable us to set if and only if . For , is thus defined as , where, for , one has .

Finally, the truth value is set equal to unity if partial truth values are not allowed; otherwise, one has



so that higher truth values will be assigned to entailments whose corresponding response distributions are less heterogeneous.

As a consequence of the previous discussion, the Cross-Entropy sampling parameter can be represented as vector .

The parametric space should include a parameter under which all possible states must have a real chance of being selected: this parameter is specified as the initial reference parameter . A CategoricalEntailmentEnsembleOptimizationContext defines as a vector whose entries , corresponding to feature categories, are all set equal to , while entries , corresponding to response categories, are all set equal to .

Updating step

At iteration , let us represent the sample drawn as , where is the Cross-Entropy sample size, and the -th sample point is the sequence . The parameter's updating formula is, for and ,



where is the elite sample in this context, i.e. the set of sample points having the lowest performances observed during the -th iteration, if minimizing, the highest ones, otherwise, while is its indicator function.

Analogously, one has, for ,

Applying a smoothing scheme to updated parameters

In a CategoricalEntailmentEnsembleOptimizationContext, the sampling parameter is smoothed applying the following formula (See Rubinstein and Kroese, Remark 5.2, p. 189^[1] ):



where .

Optimizing step

The optimizing step is executed after that the underlying Cross-Entropy program has converged. In a specified context, it is expected that, given a reference parameter , a corresponding reasonable value could be guessed for the optimizing argument of , say , with a function from to . Function is defined by overriding method GetOptimalState(DoubleMatrix) that should return given a specific reference parameter .

Given the optimal parameter (the parameter corresponding to the last iteration executed by the algorithm before stopping),



the argument at which the searched extremum is considered as reached according to the Cross-Entropy method will be returned as follows.

For , one has , where for , , with equal to unity if , zero otherwise. Block is a binary vector , in which there is only one entry equal to unity, taken at random among those corresponding to probabilities equal to



Finally, is unity if partial truth values are not allowed; otherwise, it is set equal to

Stopping criterion

A CategoricalEntailmentEnsembleOptimizationContext never stops before executing a number of iterations less than MinimumNumberOfIterations, and always stops if such number is greater than or equal to MaximumNumberOfIterations.

For intermediate iterations, default method StopAtIntermediateIteration(Int32, LinkedListDouble, LinkedListDoubleMatrix) is called to check if a Cross-Entropy program executing in this context should stop or not.

Instantiating a context for optimizing on entailments

At instantiation, the constructor of a CategoricalEntailmentEnsembleOptimizationContext object will receive information about the optimization under study by means of parameters representing the objective function , the number of categories in the feature and response variables, and respectively, the number of entailments to be searched , the extremes of the allowed range of intermediate iterations, and , and a constant stating if the optimization goal is a maximization or a minimization. In addition, the smoothing parameter and a boolean constant signaling if entailment partial truth values should be allowed are also passed to the constructor.

After construction, and can be inspected, respectively, via properties MinimumNumberOfIterations and MaximumNumberOfIterations. The smoothing coefficient is also available via property ProbabilitySmoothingCoefficient. Count constants , and are returned by NumberOfCategoricalEntailments, FeatureCategoryCounts, and NumberOfResponseCategories, respectively. In addition, property OptimizationGoal signals that the performance function must be maximized if it evaluates to the constant Maximization, or that a minimization is requested if it evaluates to the constant Minimization.

To evaluate the objective function at a specific argument, one can call method Performance(DoubleMatrix) passing the argument as a parameter. It is expected that the objective function will accept a row vector representing a valid representation of an argument.

Reference