Aliasing on Purpose
10 min read
Suppose evaluating a group of inputs is expensive, and we want the average result across groups of different sizes. Evaluating every possible group would require exponentially many measurements. The average can depend on much less information than that full collection of values.
The averaging rule here gives each group size equal weight, then averages uniformly over groups of that size. This is the Shapley distribution, used to average a player’s contributions in the Shapley value. Write \(g(S)\) for the result on a group \(S\) drawn from \([d]=\{1,\ldots,d\}\). We want the mean of \(g\) under this rule.
An interaction describes how inputs jointly affect the result beyond their separate effects. When \(g\) has no interactions involving more than three inputs, this mean depends only on a constant term and the sum of the pairwise interactions. Each pair has the same weight, so measurements can mix those interactions together without losing the sum we need. The fractional-factorial construction of Zhou, Mee, Hamers & Zheng uses this freedom to recover the mean exactly from fewer than \(4d\) evaluations, in place of all \(2^d\) [ZMHZ, JASA ’25]. The next section makes the interaction assumption precise.
From Coalitions to Interactions
What does “no interaction involving more than three elements” mean for a set function? The cleanest answer comes from encoding a coalition by one sign per element:
\[ x_j(S) = \begin{cases} +1, & j \in S, \\ -1, & j \notin S. \end{cases} \]
We write \(g(x)\) for the value of \(g\) at the coalition represented by a sign vector \(x\). For each \(T \subseteq [d]\), write \(\chi_T(S)=\prod_{j\in T}x_j(S)\) for the product of the signs indexed by \(T\), with \(\chi_\emptyset(S)=1\).
The corresponding Fourier coefficient is the signed average of \(g\) over the whole cube:
\[ \widehat g(T) = \frac{1}{2^d} \sum_{S\subseteq[d]}g(S)\chi_T(S). \]
Lemma (Fourier reconstruction): These coefficients reconstruct every value of \(g\) exactly:
\[ g(S) = \sum_{T\subseteq[d]}\widehat g(T)\chi_T(S). \]
Proof
Fix the coalition \(S\) whose value we want to reconstruct. Substitute the definition of every coefficient and interchange the two finite sums:
\[\begin{align} \sum_{T\subseteq[d]}\widehat g(T)\chi_T(S) &= \sum_{T\subseteq[d]} \left( \frac{1}{2^d}\sum_{A\subseteq[d]}g(A)\chi_T(A) \right) \chi_T(S) \\ &= \frac{1}{2^d} \sum_{A\subseteq[d]}g(A) \sum_{T\subseteq[d]}\chi_T(A)\chi_T(S). \end{align}\]
The inner sum has one term for each choice of which coordinates to multiply. Expanding a product of \(d\) two-term factors gives exactly that sum:
\[ \sum_{T\subseteq[d]}\chi_T(A)\chi_T(S) = \prod_{j=1}^d\bigl(1+x_j(A)x_j(S)\bigr). \]
If \(A=S\), every factor is \(2\), so the product is \(2^d\). If \(A\neq S\), some coordinate has opposite signs, so its factor is \(1-1=0\) and the whole product vanishes. Only the term \(A=S\) survives in the outer sum:
\[\begin{align} \sum_{T\subseteq[d]}\widehat g(T)\chi_T(S) &= \frac{1}{2^d}g(S)2^d \\ &=g(S). \end{align}\]
This calculation reconstructs the value at the chosen coalition \(S\), so it holds throughout the cube.
Operationally, reconstruction has two steps: compute each signed average \(\widehat g(T)\) from the values of \(g\), then, for the desired coalition \(S\), multiply every coefficient by its sign \(\chi_T(S)\) and add. The lemma proves that this sum produces \(g(S)\) itself, not merely another description of the coefficients.
The coefficient \(\widehat g(\emptyset)\) is the uniform average of \(g\). A coefficient with \(|T|=1\) is a main effect, and one with \(|T|\geq2\) is an interaction among the elements of \(T\). The degree-three assumption is now exact:
\[ \widehat g(T)=0 \qquad\text{whenever }|T|>3. \]
Some such bound is unavoidable: every coalition has positive probability under the Shapley distribution, so changing \(g\) at a single unobserved coalition changes its mean without changing what any fixed fraction sees. Fixing the bound at degree three is what makes fewer than \(4d\) evaluations enough. The rest of the page shows why: the mean needs only the intercept and the sum of the pairwise coefficients, and a fraction of the cube can measure that sum without ever separating the pairs.
What the Mean Sees
Which of these coefficients does the Shapley-distribution mean depend on? Averaging the expansion term by term requires the mean of each parity.
Lemma (Shapley parity moments): Under the Shapley distribution, the mean of a parity depends only on the number of signs being multiplied:
\[ \mathbb{E}[\chi_T(S)] = \begin{cases} \dfrac{1}{|T|+1}, & |T|\text{ even}, \\[5pt] 0, & |T|\text{ odd}. \end{cases} \]
Proof
There is a useful second way to draw the same random coalition. First draw \(p\) uniformly from \([0,1]\); conditional on \(p\), include each element independently with probability \(p\). For any fixed coalition \(A\), this procedure gives:
\[\begin{align} \Pr(S=A) &=\int_0^1p^{|A|}(1-p)^{d-|A|}\,dp \\ &=\frac{|A|!\,(d-|A|)!}{(d+1)!} \\ &=\frac{1}{d+1}\binom{d}{|A|}^{-1}. \end{align}\]
The second line is the beta integral, and the third uses the factorial formula for the binomial coefficient. For a fixed size, summing over its \(\binom{d}{|A|}\) coalitions gives probability \(1/(d+1)\), and all coalitions of that size are equally likely. This is exactly the Shapley distribution.
Conditional on \(p\), the signs are independent and each has mean \(2p-1\). Independence lets us multiply those means:
\[\begin{align} \mathbb{E}[\chi_T(S)\mid p] &= \mathbb{E}\left[\prod_{j\in T}x_j(S)\mathrel{\Big|}p\right] \\ &= \prod_{j\in T}\mathbb{E}[x_j(S)\mid p] \\ &=(2p-1)^{|T|}. \end{align}\]
The second line uses conditional independence, and the third uses the same mean for each of the \(|T|\) signs. Average over \(p\) and substitute \(u=2p-1\):
\[\begin{align} \mathbb{E}[\chi_T(S)] &=\int_0^1(2p-1)^{|T|}\,dp \\ &=\frac12\int_{-1}^1u^{|T|}\,du \\ &= \begin{cases} \dfrac12\left[\dfrac{u^{|T|+1}}{|T|+1}\right]_{-1}^{1} =\dfrac{1}{|T|+1}, & |T|\text{ even}, \\[8pt] 0, & |T|\text{ odd}. \end{cases} \end{align}\]
For even \(|T|\), the antiderivative takes opposite values at \(1\) and \(-1\) and their difference is \(2/(|T|+1)\). For odd \(|T|\), the integrand is odd, so its integral over the symmetric interval \([-1,1]\) is zero.
We can now average the Fourier expansion:
\[\begin{align} \mathbb{E}[g(S)] &= \mathbb{E}\left[ \sum_{T\subseteq[d]}\widehat g(T)\chi_T(S) \right] \\ &= \sum_{T\subseteq[d]}\widehat g(T)\mathbb{E}[\chi_T(S)] \\ &= \sum_{\substack{T\subseteq[d]:\\|T|\text{ even}}} \frac{\widehat g(T)}{|T|+1} \\ &= \widehat g(\emptyset) +\frac13\sum_{|T|=2}\widehat g(T) +\frac15\sum_{|T|=4}\widehat g(T) +\cdots. \end{align}\]
The first line inserts the Fourier expansion, the second uses linearity of expectation, and the third substitutes the parity moments just proved. The last line groups the surviving coefficients by their even order.
Odd-order interactions disappear. Even-order interactions survive, and all interactions of the same order carry the same weight.
Corollary (Degree-three mean): Under the degree-three assumption, only the intercept and the sum of the pairwise interactions remain:
\[ \mathbb{E}[g(S)] = \widehat g(\emptyset) +\frac13\sum_{|T|=2}\widehat g(T). \]
We do not need the individual pairwise coefficients. We need only their sum, so a design may safely merge pairwise coefficients as long as it keeps them away from the intercept.
What a Fraction Measures
If we evaluate \(g\) on only part of the cube, what do signed averages over that part measure? Let \(H\leq\{-1,+1\}^d\) be a subgroup under coordinatewise multiplication, and evaluate \(g\) only at the coalitions in \(H\). For every \(U\subseteq[d]\), take the signed average:
\[ Y_U := \frac{1}{|H|} \sum_{x\in H}g(x)\chi_U(x). \]
The plain average of the observed values is \(Y_\emptyset\). The other \(Y_U\) multiply those same values by the sign pattern of \(\chi_U\) before averaging.
Two sets are aliased when their parities agree at every observed coalition.
Lemma (Aliasing identity): Each signed average is the sum of the coefficients aliased with its parity:
\[ Y_U = \sum_{\substack{T\subseteq[d]:\\ \chi_T(x)=\chi_U(x)\text{ for every }x\in H}} \widehat g(T). \]
Proof
Substituting the Fourier expansion shows exactly which coefficients each measurement combines:
\[\begin{align} Y_U &= \frac{1}{|H|} \sum_{x\in H} \left( \sum_{T\subseteq[d]}\widehat g(T)\chi_T(x) \right) \chi_U(x) \\ &= \sum_{T\subseteq[d]}\widehat g(T) \cdot \frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(x). \end{align}\]
The first line inserts the expansion. The second swaps the sums and uses \(\chi_T\chi_U=\chi_{T\mathbin{\triangle}U}\). It remains to evaluate the inner average.
First suppose \(\chi_T\) and \(\chi_U\) agree throughout \(H\). Then their product is one at every observed point:
\[\begin{align} \chi_{T\mathbin{\triangle}U}(x) &=\chi_T(x)\chi_U(x) \\ &=\chi_T(x)^2 \\ &=1 \qquad\text{for every }x\in H. \end{align}\]
The average is therefore one:
\[ \frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(x) = \frac{1}{|H|} \sum_{x\in H}1 =1. \]
Now suppose the parities do not agree throughout \(H\). There is then some \(y\in H\) for which their signs differ, and hence:
\[ \chi_{T\mathbin{\triangle}U}(y) = \chi_T(y)\chi_U(y) =-1. \]
Because \(H\) is a subgroup, the map \(x\mapsto yx\) is a permutation of \(H\). Reindexing the average by that permutation and using multiplicativity gives:
\[\begin{align} \frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(x) &= \frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(yx) \\ &= \frac{1}{|H|} \sum_{x\in H} \chi_{T\mathbin{\triangle}U}(y) \chi_{T\mathbin{\triangle}U}(x) \\ &= -\frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(x). \end{align}\]
The same real number equals its negative, so it must be zero. Thus the inner average obeys the cancellation rule:
\[ \frac{1}{|H|} \sum_{x\in H}\chi_{T\mathbin{\triangle}U}(x) = \begin{cases} 1, & \chi_T(x)=\chi_U(x)\text{ for every }x\in H,\\ 0, & \text{otherwise}. \end{cases} \]
Substituting this rule into the expression for \(Y_U\) removes every nonaliased coefficient and proves the lemma.
A fractional measurement therefore returns an alias-class sum, not an individual coefficient.
Choosing the Fraction
Which fraction merges pairs with each other but never with the intercept? We construct \(H\) so that selected pair parities agree on every observed coalition. Whenever \(\chi_U|_H=\chi_W|_H\), their signed averages are literally the same number, \(Y_U=Y_W\), and the aliasing lemma says that this common measurement contains the coefficients indexed by both \(U\) and \(W\). The aim is to put pairs into such groups without putting any pair in the intercept’s group.
First consider the three-factor half fraction \(x_1x_2x_3=1\). Its four runs are \((+1,+1,+1)\), \((+1,-1,-1)\), \((-1,+1,-1)\), and \((-1,-1,+1)\). Multiplication by \(x_3\) gives \(x_1x_2=x_3\), so \(Y_{\{1,2\}}=Y_{\{3\}}\). This is the wrong alias: it merges a pair, whose Shapley weight is \(1/3\), with a main effect, whose weight is zero.
For five elements, let \(z_0,z_1,z_2,z_3\in\{-1,+1\}\) vary freely and use the columns:
\[\begin{align} x_1&=z_0, & x_2&=z_0z_1, & x_3&=z_0z_2,\\ x_4&=z_0z_1z_2, & x_5&=z_0z_3.&& \end{align}\]
Their only nontrivial defining relation is \(x_1x_2x_3x_4=1\). It gives three equal pairs of measurements:
\[\begin{align} Y_{\{1,2\}}&=Y_{\{3,4\}}, & Y_{\{1,3\}}&=Y_{\{2,4\}}, & Y_{\{1,4\}}&=Y_{\{2,3\}}. \end{align}\]
The four measurements involving element \(5\) remain distinct. Thus the ten pairs form seven groups, and under the degree-three assumption, adding one \(Y_U\) from each group counts every pairwise coefficient once.
The same construction works for any \(d\geq2\). Set:
\[ r=\lceil\log_2d\rceil. \]
Choose distinct sets \(A_1,\ldots,A_d\subseteq[r]\) satisfying:
\[ A_1=\emptyset, \qquad \bigl\{\emptyset,\{1\},\ldots,\{r\}\bigr\} \subseteq \{A_1,\ldots,A_d\} \subseteq 2^{[r]}, \qquad A_j\neq A_\ell\ \text{for }j\neq\ell. \]
Such a choice exists because \(r+1\leq d\leq2^r\). For every \(z=(z_0,\ldots,z_r)\in\{-1,+1\}^{r+1}\), define:
\[ x_j(z) = z_0\prod_{k\in A_j}z_k, \qquad j\in[d], \]
and take the fraction:
\[ H = \bigl\{(x_1(z),\ldots,x_d(z)): z\in\{-1,+1\}^{r+1}\bigr\}. \]
For \(d=5\), the choice \((A_1,\ldots,A_5)=(\emptyset,\{1\},\{2\},\{1,2\},\{3\})\) gives exactly the five columns above. For \(d=1\), use the full two-point cube.
Lemma (Regular fraction): The set \(H\) is a subgroup of \(\{-1,+1\}^d\) with \(|H|=2^{r+1}\). Every restricted parity is a product of \(z_0,\ldots,z_r\), all \(2^{r+1}\) such products occur, and every defining relation contains an even number of factor columns.
Proof
For \(z,w\in\{-1,+1\}^{r+1}\), write \(zw=(z_0w_0,\ldots,z_rw_r)\). Coordinatewise multiplication gives another run because:
\[ x_j(z)x_j(w) = (z_0w_0)\prod_{k\in A_j}(z_kw_k) = x_j(zw). \]
The all-\(+1\) choice gives the identity and \(x(z)^2\) is the identity, so \(H\) is a subgroup.
The map \(z\mapsto x(z)\) is injective. Indeed, \(A_1=\emptyset\) gives \(z_0=x_1(z)\). For each \(k\in[r]\), one chosen set equals \(\{k\}\); if it is \(A_j\), then:
\[ z_k=x_1(z)x_j(z). \]
The run therefore determines every free sign, and hence \(|H|=2^{r+1}\).
For any \(U\subseteq[d]\), its parity on a run is:
\[ \chi_U(x(z)) = z_0^{|U|} \prod_{k=1}^r z_k^{\,|\{j\in U:k\in A_j\}|}. \]
Thus every restricted parity is a product of the free signs after even powers cancel. Conversely, \(\chi_{\{1\}}(x(z))=z_0\), and whenever \(A_j=\{k\}\) we have \(\chi_{\{1,j\}}(x(z))=z_k\). Products of these parities produce all \(2^{r+1}\) products of the free signs.
Finally, a defining relation has \(\chi_U(x(z))=1\) for every \(z\). The exponent of \(z_0\) in the preceding display is \(|U|\), so independence of the free signs forces \(|U|\) to be even. Every defining relation therefore has even length.
This is a regular fractional factorial design in the terminology of Wu and Hamada [WH, ’21]. Even-order coefficients therefore alias only with even-order coefficients, and odd-order coefficients only with odd-order coefficients.
The observed values form a function on the \((r+1)\)-dimensional sign cube. A Walsh–Hadamard transform returns its signed average against every product of the free signs, which is one \(Y_U\) for each alias class. With \(2^{r+1}\) inputs and \(r+1\) stages, this takes \(O(d\log d)\) arithmetic operations.
Recovering the Mean
Why does one measurement per alias class give the exact mean, and how many evaluations is that? Choose one pair from each alias class that contains a pair, and let \(\mathcal{R}\) be the set of chosen representatives.
Claim (Exact mean recovery): If \(g\) has Fourier degree at most three, then the fraction recovers its Shapley-distribution mean by:
\[ \mathbb{E}[g(S)] = Y_\emptyset +\frac13\sum_{U\in\mathcal{R}}Y_U. \]
Proof
Every defining relation has even length, so even-order coefficients never alias with odd-order coefficients. Under degree three, an even-order coefficient is either the intercept or a pairwise interaction.
The intercept is not aliased with any pair. If \(\chi_{\{j,k\}}(x)=1\) on every run, then \(x_j=x_k\) on every run because each sign is its own inverse. That would make the two factor columns identical, contradicting the construction’s use of distinct products of the free signs. The aliasing lemma therefore gives \(Y_\emptyset=\widehat g(\emptyset)\).
Now start from a pair \(U\). Its alias class contains only even-order coefficients, and the intercept has just been excluded. Under degree three, \(Y_U\) is therefore the sum of exactly the pairwise coefficients in that class. In the five-element example, the relation \(x_1x_2=x_3x_4\) gives \(Y_{\{1,2\}}=\widehat g(\{1,2\})+\widehat g(\{3,4\})\).
The pair alias classes partition all pairwise coefficients. Choosing one representative from each class counts every pairwise coefficient once, so \(\sum_{U\in\mathcal{R}}Y_U=\sum_{|T|=2}\widehat g(T)\). Substituting this identity and \(Y_\emptyset=\widehat g(\emptyset)\) into the earlier mean formula proves the claim.
The design uses one value of \(g\) for each of its \(2^{r+1}\) coalitions, and \(|H|=2^{1+\lceil\log_2d\rceil}<2^{1+(\log_2d+1)}=4d\). The strict inequality uses \(\lceil a\rceil<a+1\) with \(a=\log_2d\). Thus fewer than \(4d\) evaluations recover the exact mean, rather than the \(2^d\) values used by full enumeration.
Shapley Values
Where does the Shapley value come in? Let \(f:2^{[d]}\to\mathbb{R}\) be a cooperative game and fix player \(i\). On the remaining \(d-1\) players, define the marginal-contribution function:
\[ g(S) = f(S\cup\{i\})-f(S), \qquad S\subseteq[d]\setminus\{i\}. \]
Its Shapley-distribution mean is the Shapley value:
\[ \phi_i(f) = \mathbb{E}[g(S)]. \]
Here the Shapley distribution is on the remaining \(d-1\) players: choose \(|S|\) uniformly from \(\{0,\ldots,d-1\}\), then choose \(S\) uniformly among coalitions of that size.
Lemma (A first difference lowers degree): If \(f\) has Fourier degree at most four, then \(g\) has Fourier degree at most three.
Proof
Split the Fourier expansion into terms that contain \(i\) and terms that do not. The sign of coordinate \(i\) is \(+1\) at \(S\cup\{i\}\) and \(-1\) at \(S\), so the two expansions are:
\[\begin{align} f(S\cup\{i\}) &= \sum_{T\not\ni i}\widehat f(T)\chi_T(S) +\sum_{T\ni i}\widehat f(T)\chi_{T\setminus\{i\}}(S), \\ f(S) &= \sum_{T\not\ni i}\widehat f(T)\chi_T(S) -\sum_{T\ni i}\widehat f(T)\chi_{T\setminus\{i\}}(S). \end{align}\]
Subtracting the second expansion from the first cancels every term not involving \(i\) and doubles every term involving \(i\):
\[\begin{align} g(S) &= \sum_{T\ni i}\widehat f(T)\chi_{T\setminus\{i\}}(S) +\sum_{T\ni i}\widehat f(T)\chi_{T\setminus\{i\}}(S) \\ &= 2\sum_{T\ni i}\widehat f(T)\chi_{T\setminus\{i\}}(S). \end{align}\]
An order-\(|T|\) interaction containing \(i\) has become an order-\(|T|-1\) interaction on the remaining players. Thus degree at most four for \(f\) implies degree at most three for \(g\).
Lemma (Squaring can double degree): If \(f\) has Fourier degree at most \(k\), then the pointwise square \(f^2(S)=f(S)^2\) has Fourier degree at most \(\min\{d,2k\}\).
Proof
Expand both copies of \(f\) and use \(\chi_T\chi_U=\chi_{T\mathbin{\triangle}U}\):
\[\begin{align} f(S)^2 &= \left(\sum_{|T|\leq k}\widehat f(T)\chi_T(S)\right) \left(\sum_{|U|\leq k}\widehat f(U)\chi_U(S)\right) \\ &= \sum_{|T|\leq k}\sum_{|U|\leq k} \widehat f(T)\widehat f(U)\chi_{T\mathbin{\triangle}U}(S). \end{align}\]
Every parity in the last sum has order:
\[ |T\mathbin{\triangle}U| \leq |T|+|U| \leq 2k. \]
No parity can have order above \(d\), so the degree is at most \(\min\{d,2k\}\). The degree can be smaller because repeated variables cancel and different products can cancel in the coefficient sum.
For \(d\geq2\), applying the fractional design on the remaining \(d-1\) players uses fewer than \(4(d-1)\) evaluations of \(g\) for one exact Shapley value. Each evaluation of \(g\) uses the two coalition values \(f(S\cup\{i\})\) and \(f(S)\). The sampled sets \(S\) are distinct, and a coalition without \(i\) cannot equal one with \(i\). Thus one Shapley value costs fewer than \(8(d-1)\) evaluations of \(f\), and computing all \(d\) values separately, without reusing evaluations between players, costs fewer than \(8d(d-1)<8d^2\) evaluations of \(f\).
Zhou, Mee, Hamers & Zheng reuse evaluations of \(f\) across players more cleverly. When every interaction involving five or more players is zero, their recursive construction recovers all Shapley values, and their Theorem 4 bounds the number of distinct evaluations of \(f\) by \(4d^2-4\) [ZMHZ, JASA ’25]. Compared with our direct implementation’s leading bound of \(8d^2\), their reuse cuts the leading evaluation count by a factor of two.
Beyond Exact Low Degree
What happens when the degree assumption fails? If \(f\) has interactions above order four, then \(g\) can have interactions above order three and the fractional estimate need not be exact. The same construction can still work well when those higher-order Fourier coefficients are small and have varying signs: the error enters through alias-class sums, so positive and negative contributions can cancel. This is a useful empirical regime, not a worst-case guarantee.
After estimating every Shapley value, efficiency gives an exact diagnostic. The true Shapley values satisfy efficiency, \(\sum_{i=1}^d\phi_i(f)=f([d])-f(\emptyset)\), so estimates \(\widehat\phi_i\) obey:
\[ \left| f([d])-f(\emptyset)-\sum_{i=1}^d\widehat\phi_i \right| = \left| \sum_{i=1}^d\bigl(\phi_i(f)-\widehat\phi_i\bigr) \right| \leq \sum_{i=1}^d\left|\phi_i(f)-\widehat\phi_i\right|. \]
The left side is the magnitude of the total signed error in the estimates and a lower bound on their total absolute error. A large efficiency gap certifies that the estimates are collectively inaccurate; in fact, at least one player’s absolute error is at least the gap divided by \(d\). A small gap is reassuring but does not prove individual accuracy, because individual errors can cancel across players.