# Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming +
## 5 Experimental Phase
### Uncertainty Position Percentage  
In this step, we perform an in-depth analysis of the results obtained in the previous experimental steps to provide an explanation of and a justification for the negative results highlighted in Section 5.1. As we have already explained in Section 4, when applying spectral inversion to a symbolic formula representing a generic Walsh transform, we obtain a pseudo-Boolean function, which is basically a pseudo-truth table in polar form containing integer values. These values may be either strictly negative, strictly positive, or zero. We have explained that, since the output of spectral inversion is a function in polar form, negative values are mapped to _True_ and positive values are mapped to _False_. On the other hand, zero values are said to be \"uncertain\" positions, which need to be filled via a random criterion (i.e., an uncertainty filling strategy, such as the ones proposed in Section 4). In a setting like this one, if the percentage of uncertain positions in the pseudo-truth table is high, then the nearest Boolean function is computed almost entirely at random. This is not beneficial for the fitness optimization, since in this way, we lose the advantages of an actual evolution and end up with a standard random-search-based method that adds no intelligence to the way the fitness landscape is explored. To this end, we analyze the mean uncertainty position percentage of the pseudo-truth tables corresponding to the individuals in the population across the executed generations and repetitions. We perform this experiment with \(n\) equal to 8 bit, 12 bit, and 16 bit. We test all the symbolic representations for the Walsh transform. We adopt the biased uncertainty \begin{table}
\begin{tabular}{c c c c} \hline \hline \(n\) & **Biased** & **Unbiased** & \(p\)**-Value** \\ \hline  & \(\mu\,\pm\,\sigma\) & \(\mu\,\pm\,\sigma\) & \\ \hline
6 & 0.53 \(\pm\) 2.0 & 7.53 \(\pm\) 2.12 & 0.0 \\
7 & 0.0 \(\pm\) 0.0 & 9.86 \(\pm\) 5.34 & 0.0 \\
8 & 0.0 \(\pm\) 0.0 & 15.67 \(\pm\) 6.95 & 0.0 \\
9 & 0.0 \(\pm\) 0.0 & 24.03 \(\pm\) 10.42 & 0.0 \\
10 & 0.0 \(\pm\) 0.0 & 34.03 \(\pm\) 19.28 & 0.0 \\
11 & 0.0 \(\pm\) 0.0 & 37.96 \(\pm\) 21.88 & 0.0 \\
12 & 0.0 \(\pm\) 0.0 & 62.84 \(\pm\) 44.66 & 0.0 \\
13 & 0.0 \(\pm\) 0.0 & 78.07 \(\pm\) 42.94 & 0.0 \\
14 & 0.0 \(\pm\) 0.0 & 94.27 \(\pm\) 67.75 & 0.0 \\
15 & 0.0 \(\pm\) 0.0 & 137.8 \(\pm\) 107.01 & 0.0 \\
16 & 0.0 \(\pm\) 0.0 & 278.87 \(\pm\) 185.31 & 0.0 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Table that details the mean (\(\mu\)) and standard deviation (\(\sigma\)) of the balancedness degree belonging to the best individuals. The \(p\)-values of the Wilcoxon test [48] are detailed as well. The results are based on GP with \(\mathcal{S}_{\text{F1}}^{\text{N,REC}}\) as the tree structure. \begin{table}
\begin{tabular}{c c c c} \hline \hline \(n\) & **Biased** & **Unbiased** & \(p\)**-Value** \\ \hline  & \(\mu\,\pm\,\sigma\) & \(\mu\,\pm\,\sigma\) & \\ \hline
6 & 0.0 \(\pm\) 0.0 & 7.03 \(\pm\) 2.36 & 0.0 \\
7 & 0.0 \(\pm\) 0.0 & 9.89 \(\pm\) 4.07 & 0.0 \\
8 & 0.0 \(\pm\) 0.0 & 17.47 \(\pm\) 8.2 & 0.0 \\
9 & 0.0 \(\pm\) 0.0 & 26.22 \(\pm\) 11.89 & 0.0 \\
10 & 0.0 \(\pmfilling strategy. The trend of the mean uncertainty position percentage is presented in Figure 18 (shaded area represents variance). The plot shows that in almost all the cases, the mean uncertainty position percentage is approximately 1.0 for the whole evolution, meaning that the method resembles a random-search-based technique. Interestingly, we can see that the trend is lower only for \(\mathcal{S}_{\text{F1}}^{\text{N,ERC}}\) and \(\mathcal{S}_{\text{F1}}^{\text{N}}\), i.e., the only tree structures that have been shown to outperform RS. This means that if we use a configuration that is different from \(\mathcal{S}_{\text{F1}}^{\text{N,ERC}}\) and \(\mathcal{S}_{\text{F1}}^{\text{N}}\), then we identify pseudo-Boolean functions with an extremely high percentage of uncertain entries, which are, consequently, assigned with non-deterministic choices.