Properties

Dependence on input variables

r-junta

f depends on only $r$ variables. k-junta has at most $2^k$ non 0 coefficients. Each of them is $2^{-k+1}$ heavy: Make two equally high stacks unequal.

Witness to the relevance of variable $x_i$: an assignment a which flips f(a) when ith bit is flipped.

Monotone fn f

Flipping $x_i$ from 1 to -1 cannot flip f(x) from -1 to 1. $(\mathrm{\forall }i,x_i\le y_i)⟹f(x_1,..x_n)\le f(y_1,..y_n)$.

Define $g(x_i,x_{-i})=f(x)$ naturally. Then $g(-1,x_{-i})=-g(1,x_{-i})$ iff \ $g(-1,x_{-i})=-1\wedge g(1,x_{-i})=1$;\ $$E_{x_{-i}}[g(1,x_{-i})-g(-1,x_{-i})]=2P{r}_{x_{-i}}(g(1,x_{-i})=1\wedge g(-1,x_{-i})=-1)$$.

Influence

$\hat{f}(\left\{i\right\})=2^{-1}(E_{x_{-i}}[g(1,x_{-i})]-E_{x_{-i}}[g(-1,x_{-i})])=I_i(f)$.

Total influence

As \(\norm{x}{1} \leq \sqrt{n}\norm{x}{2}\): $I(f)=\sum _i\hat{f}(\left\{i\right\})\le \sqrt{n}\sum _i\hat{f}(\left\{i\right\}{)}^2\le \sqrt{n}$.

For majority: $I(f)\approx n(\frac{2}{(n-1)\pi }{)}^{0.5}$.

Fairness

f is fair if it is 1 on exactly half the inputs.

Combinatorial properties

Sensitivity to bit i

Aka Influence of bit i. $x^{(i)}$: x with ith bit flipped. Sensitivity wrt bit i: $I_i(f)=P{r}_x(f(x)\ne f(x^{(i)})$.

Total influence or avg sensitivity or Energy: $I(f)=\sum _i{I}_i(f)$.

Noise sensitivity

Aka noise stability. $y=N_{ϵ}(x)$: \ x with $ϵ$ noise in each bit. $N{S}_{ϵ}(f)=P{r}_{x,y}(f(x)\ne f(y))=2P{r}_{x,y}(f(x)=1\wedge f(y)=-1)$ by symmetry of sign changing bit flips.

Expressiveness measures

Let $C$ be a class of boolean function. Viewing $c$ as the dichotomy it induces on a given set is profitable here.

Count the number of f in C

One can use $|C|$ or packing/ covering numbers. See the functional analysis survey for details.

Dichotomy count fn

Take S with $|S|=m$. $D_C(S)$: set of dichotomies on S induced by C; Max dichotomy count: $D_C(m)=\underset{|S|=m}{max}|D_C(S)|$.

Shattering and VCD d

If $D_C(S)=2^m$, it is said to be shattered by $C$. VCD(C) is the size of maximal set which is shattered by $C$.

Bounding using the VCD

If $m<=d$, $D_C(m)=\sum _{i=1}^m(\genfrac{}{}{0ex}{}{n}{i})=2^m=O(m^d)$. If $m>d$, we use Sauer’s lemma. These bounds are important in quantifying the number of samples required to accurately estimate probabilities of a class of events (an example event: a classifier is wrong.). For details, see statistics and computational learning theory surveys.

\paragraph{Sauer’s lemma} (Sauer) If d = vcd(C), by induction and intermediate function, \ $D_C(m)\le \sum _{i=1}^d(\genfrac{}{}{0ex}{}{m}{i})\le (\frac{em}{d}{)}^d=O(m^d)$.

Pf: Let $s=|X|$. By induction on s+d. \why Intuition: Can’t produce some dichotomy on some d+1 set.

Prove VCD(C) = d

Show some d-sized set shattered by C (Lower bound); show that no $d+1$ sized set is shattered (Upper bound). Use geometric intuition.

Lower bound

Try making a matrix of points shattered, whose rows are bit vectors of the shattered points.

Upper bound

Find optimal shattering geometry, optimal strategy; Use adversarial labelling. Find $D_C(m)$, solve $D_C(m)<2^d$. If C finite, shatters S, $|C|\ge 2^{|S|}$, so $\log |C|\ge d$.

VCD’s of some R

Intervals in R: 2. Halfspaces in $R^n$: n+1. Axis aligned rectangles: 4. d-gons in a plane: 2d+1. $VCD(C_G)\le 2ds\log (es)$.

$VCD(C_{r,n})\ge r(\log (n/r))$ if $C_{r,n}$ embedding closed, contains function f with exactly $r$ relevant vars. Take f. Key idea: A sample point $s_j$ is the witness of relevance of var j in f. Key idea: Make a matrix whose rows are points shattered by $C$. Let $k=\log (n/r)$. Build a $rk\times r{2}^k$ block matrix: 1 row block for every $s_j$. In row block j: every column block $i\ne j$ has same entry: $s_{j,i}$; but column block i has all separate entries from ${0,1}^k$. To select any set of points/ rows, select embedding of f into the right set of relevant vars.

So, for decision list of $r$ relevant vars: $r(\log (n/r))\le d\le$r$\log n$.