What does an exponent on set notation mean?

Question

I'm reading this paper that establishes SHAP values for Machine Learning explainability.

On page 2 of the paper they put some set builder notation to an exponent $M$, as below:

$$z' \in \{1, 0\}^M$$

I presume this means that $z'$ is a vector of size $M$, where each index takes the value $0$ or $1$.

Is this the correct way to interpret this notation?

@J.W.Tanner Sorry, still struggling to understand after reading that resource, is my intuition right or not? — Connor, Jan 26 '23 at 14:15
Excellent, and, to carry it forward, does that mean ${1, 0}^M$ represents every possible vector of $0$s or $1$s of length $M$? — Connor, Jan 26 '23 at 14:17
Yes; in formal terms is the set of all functions from set $M$ to set ${ 0,1 }$. For simplicity, let $M = { a,b,c }$: a function from $M$ to ${ 0,1 }$ is a function that maps $a$ to one of $0,1$ and $b$ to... — Mauro ALLEGRANZA, Jan 26 '23 at 14:21
In those formal terms $M$ stands for ${1,2,3,...,M}$ in this example — J. W. Tanner, Jan 26 '23 at 14:23

score 3 · Accepted Answer · answered Jan 26 '23 at 14:25

Yes, since $M$ is a natural number ("the number of simplified input features"). In the paper, this is in the context of a definition $$ g(z') = \phi_0 + \sum_{i=1}^M \phi_iz'_i $$ where $z'$ is being indexed by $i$ for $1 \le i \le M$. The calculation is adding up $\phi_0$ and some of the other $\phi_i$ values, with $z'$ telling us which ones to include in the total.

More generally, people write $B^A$ for the set of functions from $A$ to $B$. If you like, you can think of $\{0,1\}^M$ as meaning the same as $\{0,1\}^{\{1, 2, \dots, M\}}$, which is the set of functions that take in a number between $1$ and $M$, and spit out either $0$ or $1$. If $f$ is a function like that, then you can make a vector of $0$s and $1$s: $$ (f(1), f(2), f(3), \dots, f(M)). $$ And also, if you had a vector of that length, you could use it to define a function, just by indexing into the vector. So the function and the vector are really two different views of the same data. Mathematicians often switch freely between these viewpoints.

What does an exponent on set notation mean?

1 Answers1