Extended probe method for linkage discovery over high-cardinality alphabets

The work addresses the problem of identifying the epistatic linkage of a function from high cardinality alphabets to the real numbers. It is a generalization of Heckendorn and Wright's work that restricts problem representation into the binary-string domain. Discrete Fourier transform is used to analyze underlying structure in high-cardinality alphabets space. Boolean operators are replaced with new operators such as ⊕, ⊖, ⊗ and so on in high cardinality alphabets. The "probe" formulation is redesigned to determine epistatic properties of non-binary function. Theoretical analysis shows the close relationship between probe value and problem structure. A deterministic and a stochastic algorithm based on properties of probes are proposed to completely identify the linkage structure and rigourously compute all Fourier coefficients. Some discussion about linkage detection for continuous problems is given.