Greedy algorithm

The second approach leaves the data fixed, and introduces a random element into the selection of the splitting variable. So if, for example, predictors x29, x47, and x82 were the only significant splitters and had multiplicity-adjusted p values of say 2 x 10-7, 5 x 10-8, and 3 x 10-3, the conventional greedy algorithm would pick x47 as the splitting variable as it was the most significant. The RRP procedure would pick one of these three at random. Repeating the analysis with fresh random choices would then lead to a forest of trees different random choices will create different trees. 

As the first test case, we selected 20 aliphatic primary amines from a set of 493 commercially available ones by three different methods random reagent selection, entropy-optimised ProSAR selection and an occupancy-optimised method which purely maximises the occupancy of pharmacophore bins (56), i.e. ensures that as many bins as possible are covered by the reagent selection regardless of the pharmacophore distribution. As the greedy algorithm... 

The goal out of all ( ) subsets of k molecules from a candidate set C, find the subset M where dis(M ), defined in (1), is largest. The problem is that it is not feasible to enumerate and evaluate all possible subsets. The solution is to use a sequential approximation (greedy algorithm). 

Greedy algorithms are explicitly or implicitly mentioned in many chapters of this book. 

Tables 7.3-7.6 show the experimental values of the 12 properties (for the origin of these values see Pogliani 2010). Tables 7.7 and 7.8 shows the best results obtained with the greedy algorithm, and they are either pure MCI or semi-empirical descriptions (MCI plus experimental indices). Superscripts on the left and right side of a combination means the type of configuration, for instance, superscript/7 means that the (i5 -based) valence MC indices have been obtained with the /j hydrogen perturbation, while superscript pp-odd on the right means that these...

The full combinatorial algorithm confirms the validity of the ad hoc parameters, AH, AH", and 1) introduced with the use of the greedy algorithm to model Tt, and and p, respectively. The rationale for these three ad hoc parameters wUl be explained in the next section. The descriptimis obtained with the full combinatorial method, either pure MCI or semiempirical, are collected in Tables 7.9 and 7.10. 

Table 7.7 The best descriptors for the 12 properties (P) of the organic solvents obtained with the greedy algorithm... 

The greedy algorithm without ethylencarbonate, which is a strong outlier (Tables 7.7 and 7.8), was unable to find such a descriptor. Without the strong outlier ethylencarbonate the full combinatorial search finds the following improved semiempirical combination (last five indices belong to the Kp(p-odd) / configuration), which outperforms the bad zero-level description shown in Tables 7.11 and 7.12. 

The full combinatorial technique finds also an improved semiempirical combinations with five indices (see later on), which include Tf, and T im but we prefer the more economical three-index combination. The improvement relatively to the greedy algorithm is mainly in The strongest correlations are r(Ti, = 0.60, the strongest correlation of the dielectric constant is, r e, T /m) = 0.93. Notice that the T /m tettn encodes the information about the molar mass but also about the overall -State index of the electronegative atoms. It reflects the charge distribution due to these atoms, normalized to the molar mass, a no trivial choice. 

To achieve a satisfactory description the greedy algorithm requires the exclusion of CH2Br2 compound and uses only experimental parameters (Tables 7.7 and 7.8). The full combinatorial technique (Tables 7.9 and 7.10) finds a very good Kp(p-odd)/fs semiempirical descriptor, with no need to exclude CH2Br2. The zero-level description is shown in Tables 7.11 and 7.12 and shows poor s and statistics. The correlation vector for the descriptor of Table 7.9, with whom Fig. 7.9 has been obtained, is,... 

All different MC or empirical indices of the full normal (non semi-random) descriptors of Tables 7.9 and 7.10 are now joined together to form a new space of indices, kind of super-indices, which will be used for a full combinatorial search of the best super-descriptors in a kind of configuration interaction of best indices. This super-descriptor space gave no remarkable results with the greedy algorithm, but it does find improved descriptions for the following four properties. 

In Biller et al [18], the authors analyze a pricing and production problem where (in extensions), multiple products may share limited production capacity. When the demand for products is independent and revenue curves are concave, the authors show that an application of the greedy algorithm provides the optimal pricing and production decisions. 

---