The problem with the simulations was that the number of functions that we might need to look at grows as a double-exponential function of the number of predictor variables. Specifically, if there is but one predictor variable, then there are four possible functions relating the predictor variable to the criterion variable. If there are 2 predictor variables, then there are 16 different functions; with 3 predictor variables the number of possible functional relationships has grown to 256; and, in general, for n predictor variables there are 22^n. However, many of those functions do not need to be tested separately because there is a great deal of redundancy amongst them, at least from the point of view of the learning algorithm. That is, one or more of the functions are essentially isomorphic. Consider, for example, the fact that whether we code the answer to the question, “Is the visitor male?” as 0 for Yes and 1 for No, or vice versa, is essentially irrelevant. Either coding system would work and we knew that if our learning algorithm were capable of detecting a relationship that was coded in one direction then it would be equally capable of detecting it if it had been coded in the opposite direction. The same logic applies to the criterion variable: the criterion could be coded as 1 for drug-smugglers and 0 for non-smugglers, or vice versa.
Two or more predictor variables
When one considers two or more predictor variables, rather than just a single one, as in the case of the sex of the visitor, the redundancy is even greater. It was irrelevant to us whether, for example, we treated the sex of the visitor as the first predictor variable and their (dichotomized) age as the second variable, or the other way around. When all the redundancies are taken into account, the number of functional relationships against which we needed to test our learning algorithm droped considerably. Instead of 256 functional relationships with three predictor variables, only 14 relationships need to be examined. Similarly, in the case of four predictor variables, the number of functions that need examining is reduced from 65536 to 247. It appears that the number of functions to be examined still grows as a double-exponential of the number of predictor variables, but nonetheless for any n, the number is much less than what it would otherwise be.
If you’re interested in more details of the Smugglers isomorphism, you will find them here.
How many non-isomorphic functions are there under the Smugglers isomorphism
It would be nice to have an analytical solution (i.e., an explicit formula) for the number of non-isomorphic functions on n predictor variables.
Contributors: Mark R. Diamond