<p>For the very limited situation in which $k=1$ and we're only interested in functions whose domain is $\{0,1\}^n$, the VC dimension is $\lfloor \log_2(n+1) + 1 \rfloor$.</p>

<p>The upper bound follows essentially from Sasho's argument: there are $2+2n$ 1-juntas on $n$ variables, and if there were more than $\log_2$ of that many inputs, we could find a function that avoids all 1-juntas.</p>

<p>To see the lower bound, consider the matrix whose columns contain the $2^{\lfloor \log_2(n+1) \rfloor} - 1 \le n$ not-all-zero bitstrings of length $\lfloor \log_2(n+1) \rfloor + 1$ that start with a zero. The inputs to shatter are the rows of this matrix (padded up to length $n$). Every function of these inputs is either constant, or else it or its negation appears as a column, so it's computed by a 1-junta.</p>

<hr>

<p>Here's an example for the case $n=7$ which illustrates the general idea. The claim is that the VC dimension of $1$-juntas on $7$ bits is $4$. Consider the matrix</p>

<p>$$\begin{array}{ccccccc}
  0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0\\
  1&amp;0&amp;0&amp;0&amp;1&amp;1&amp;1\\
  0&amp;1&amp;0&amp;1&amp;0&amp;1&amp;1\\
  0&amp;0&amp;1&amp;1&amp;1&amp;0&amp;1
\end{array}$$</p>

<p>formed by setting the columns to be all the length-$4$, not-all-zero bit strings that start with a zero. The claim is that the rows of this matrix are shattered by 1-juntas.</p>

<p>To see this, let $f$ be any boolean function of the rows. We can regard $f$ as a column. Now observe that either $f$ is constant, or else $f$ or its negation appears as some column in the matrix, simply by virtue of how we defined the matrix. In the first case, $f$ is obviously a 1-junta. In the latter case, suppose $f$ appears as column $i$, and observe that we can therefore compute $f$ as just the $i$-th dictator function. It follows that $f$ is again a 1-junta. A similar argument works when the negation of $f$ appears as a column--we represent $f$ by the negation of the $i$-th dictator. Thus in every case $f$ is a 1-junta. Since $f$ was arbitrary, it follows that the set formed by the rows of the above matrix is shattered by 1-juntas.</p>

<hr>

<p>This idea can in theory be extended to larger $k$, where you encode every function as some $k$ columns in the matrix. I don't see how best to argue this at the moment, though.</p>

CC BY-SA 3.0
2016-08-25T09:36:41.027Z
I'm sorry but I don't understand either your solution, or the problem itself. What are we trying to shatter, i.e., what are the points of the base set? I thought that it was the domain of $f$. If $n=2$, then how do you separate {(1,1)} from {(0,0),(0,1),(1.0)}?
domotorp
CC BY-SA 3.0
2016-08-25T16:23:23.097Z
Every function in the concept class shares a common domain $U$. "Shattered-ness" is a property of subsets of $U$: a subset is shattered if every function on that subset is a restriction of a function in the class. The VC dimension of the class is the size of the largest shattered set. So upper bounds are proven by showing every too-big subset has a function outside the class; lower bounds are proven by giving some set of points so that every function is in the class. In your final question, you've implicitly noticed that the subset of all 4 points is not shattered, because AND isn't a 1-junta.
Andrew Morgan
CC BY-SA 3.0
2016-08-25T16:31:34.450Z
Sorry for how terse that was- I tried to cram everything into one comment and should have just split it across two. Hopefully it's enough to resolve your confusion; otherwise I can try again.
Andrew Morgan
CC BY-SA 3.0
2016-08-25T18:41:26.500Z
Thx for the fast answer, but it didn't help much, I know the basics, but I'm very confused with what the domain is. Could you just spell out your example for, say,  n=3?
domotorp
CC BY-SA 3.0
2016-08-25T19:32:24.240Z
@domotorp: I added an example where $n=7$ (chosen instead of $n=3$ since then $n$ and the VC dimension are different numbers). A more succinct answer to your question though is that, when $n=3$, the domain would just be $\{0,1\}^3$. I realize now that this wasn't explicit in the question, but you can make the domain larger (say $\mathbb{R}^n$) and this can only make the VC dimension larger (as long as the codomain is still $\{0,1\}$).
Andrew Morgan
CC BY-SA 3.0
2016-08-25T19:34:15.097Z
I suppose you might object that a dictator $\mathbb{R}^n\to\{0,1\}$ can be any function that depends on only one coordinate, and this would severely break the upper bound argument. I'll add a disclaimer to my answer, but I think OP will most likely be interested in the case when the domain is $\{0,1\}^n$.
Andrew Morgan
CC BY-SA 3.0
2016-08-25T20:39:20.667Z
Thanks, now everything is clear. Moreover, I believe that in a similar way one can obtain the optimal $O(k\log n)$ bound mentioned by Sasho. All you have to do is take $k$ copies of this matrix diagonally, so like $$\begin{array}{cccccccccccccc}
  0&0&0&0&0&0&0&0&0&0&0&0&0&0\\
  1&0&0&0&1&1&1&0&0&0&0&0&0&0\\
  0&1&0&1&0&1&1&0&0&0&0&0&0&0\\
  0&0&1&1&1&0&1&0&0&0&0&0&0&0\\
 0&0&0&0&0&0&0&1&0&0&0&1&1&1\\
  0&0&0&0&0&0&0&0&1&0&1&0&1&1\\
  0&0&0&0&0&0&0&0&0&1&1&1&0&1
\end{array}$$
domotorp
CC BY-SA 3.0
2016-08-23T06:21:36.327Z
2016-08-25T19:37:50.533Z
2016-08-25T19:37:50.533Z
Andrew Morgan
<p>A boolean function $f(x_1,x_2,\dots,x_n)$ is $k$-Junta if it depends on at most $k$ variables. Consider the class $\mathcal{J}_{\leq k}$ of all $k$-Juntas over $n$ variables, what is the VC dimension of this class? </p>

<p>Or at least is there any known method to construct the largest shattered set for small values of $k$ say when $k=1$. </p>

CC BY-SA 3.0
2016-08-23T00:21:38.757Z
It's certainly between $2^k$ and $2^k + O(k\log d)$.
Sasho Nikolov
CC BY-SA 3.0
2016-08-23T00:29:03.703Z
@SashoNikolov Thanks. What is $d$? would you please elaborate a bit why you're certain?
seteropere
CC BY-SA 3.0
2016-08-23T01:16:10.547Z
sorry, $d$ should have been $n$. The $2^k$ lower bound is because you can shatter, for example, the points $\{x: x_{k+1} = \ldots = x_n = 0\}$ with the $k$-juntas that depend on $x_1, \ldots, x_k$. The upper bound is because VC-dimension is always at most log base 2 of the number of functions, and there are ${n\choose k}2^{2^k}$ many $k$-juntas: ${n \choose k}$ ways to pick $k$ coordinates and $2^{2^k}$ ways to pick the $2^k$ values of the coordinates.
Sasho Nikolov
CC BY-SA 3.0
2016-08-23T05:59:08.587Z
@AndrewMorgan why not turn your comment into an answer?
Aryeh
CC BY-SA 3.0
2016-08-23T06:35:01.920Z
@Aryeh I suppose I did answer part of the question, so I went ahead and moved my comment to an answer. Thanks for the recommendation.
Andrew Morgan
<boolean-functions><lg.learning><vc-dimension>
What is the VC Dimension of the $k-$Junta class
seteropere
# What is the VC Dimension of the $k-$Junta class

(Asked by: username_0 on 2016-08-22)

A boolean function $f(x\_1,x\_2,\dots,x\_n)$ is $k$-Junta if it depends on at most $k$ variables. Consider the class $\mathcal{J}\_{\leq k}$ of all $k$-Juntas over $n$ variables, what is the VC dimension of this class?

Or at least is there any known method to construct the largest shattered set for small values of $k$ say when $k=1$.

**Tags:** boolean-functions, lg.learning, vc-dimension
> **Comments:**
> **username_1**: It's certainly between $2^k$ and $2^k + O(k\log d)$.  
> **username_0**: @SashoNikolov Thanks. What is $d$? would you please elaborate a bit why you're certain?  
> **username_1**: sorry, $d$ should have been $n$. The $2^k$ lower bound is because you can shatter, for example, the points $\{x: x_{k+1} = \ldots = x_n = 0\}$ with the $k$-juntas that depend on $x_1, \ldots, x_k$. The upper bound is because VC-dimension is always at most log base 2 of the number of functions, and there are ${n\choose k}2^{2^k}$ many $k$-juntas: ${n \choose k}$ ways to pick $k$ coordinates and $2^{2^k}$ ways to pick the $2^k$ values of the coordinates.  
> **username_2**: @AndrewMorgan why not turn your comment into an answer?  
> **username_3**: @Aryeh I suppose I did answer part of the question, so I went ahead and moved my comment to an answer. Thanks for the recommendation.  

---

## 1 answers

### Answer by username_3 on 2016-08-23. Score: 7

For the very limited situation in which $k=1$ and we're only interested in functions whose domain is $\{0,1\}^n$, the VC dimension is $\lfloor \log\_2(n+1) + 1 \rfloor$.

The upper bound follows essentially from Sasho's argument: there are $2+2n$ 1-juntas on $n$ variables, and if there were more than $\log\_2$ of that many inputs, we could find a function that avoids all 1-juntas.

To see the lower bound, consider the matrix whose columns contain the $2^{\lfloor \log\_2(n+1) \rfloor} - 1 \le n$ not-all-zero bitstrings of length $\lfloor \log\_2(n+1) \rfloor + 1$ that start with a zero. The inputs to shatter are the rows of this matrix (padded up to length $n$). Every function of these inputs is either constant, or else it or its negation appears as a column, so it's computed by a 1-junta.

---

Here's an example for the case $n=7$ which illustrates the general idea. The claim is that the VC dimension of $1$-juntas on $7$ bits is $4$. Consider the matrix

$$\begin{array}{ccccccc}
0&0&0&0&0&0&0\\
1&0&0&0&1&1&1\\
0&1&0&1&0&1&1\\
0&0&1&1&1&0&1
\end{array}$$

formed by setting the columns to be all the length-$4$, not-all-zero bit strings that start with a zero. The claim is that the rows of this matrix are shattered by 1-juntas.

To see this, let $f$ be any boolean function of the rows. We can regard $f$ as a column. Now observe that either $f$ is constant, or else $f$ or its negation appears as some column in the matrix, simply by virtue of how we defined the matrix. In the first case, $f$ is obviously a 1-junta. In the latter case, suppose $f$ appears as column $i$, and observe that we can therefore compute $f$ as just the $i$-th dictator function. It follows that $f$ is again a 1-junta. A similar argument works when the negation of $f$ appears as a column--we represent $f$ by the negation of the $i$-th dictator. Thus in every case $f$ is a 1-junta. Since $f$ was arbitrary, it follows that the set formed by the rows of the above matrix is shattered by 1-juntas.

---

This idea can in theory be extended to larger $k$, where you encode every function as some $k$ columns in the matrix. I don't see how best to argue this at the moment, though.

> **Comments:**
> **username_4**: I'm sorry but I don't understand either your solution, or the problem itself. What are we trying to shatter, i.e., what are the points of the base set? I thought that it was the domain of $f$. If $n=2$, then how do you separate {(1,1)} from {(0,0),(0,1),(1.0)}?  
> **username_3**: Every function in the concept class shares a common domain $U$. "Shattered-ness" is a property of subsets of $U$: a subset is shattered if every function on that subset is a restriction of a function in the class. The VC dimension of the class is the size of the largest shattered set. So upper bounds are proven by showing every too-big subset has a function outside the class; lower bounds are proven by giving some set of points so that every function is in the class. In your final question, you've implicitly noticed that the subset of all 4 points is not shattered, because AND isn't a 1-junta.  
> **username_3**: Sorry for how terse that was- I tried to cram everything into one comment and should have just split it across two. Hopefully it's enough to resolve your confusion; otherwise I can try again.  
> **username_4**: Thx for the fast answer, but it didn't help much, I know the basics, but I'm very confused with what the domain is. Could you just spell out your example for, say,  n=3?  
> **username_3**: @domotorp: I added an example where $n=7$ (chosen instead of $n=3$ since then $n$ and the VC dimension are different numbers). A more succinct answer to your question though is that, when $n=3$, the domain would just be $\{0,1\}^3$. I realize now that this wasn't explicit in the question, but you can make the domain larger (say $\mathbb{R}^n$) and this can only make the VC dimension larger (as long as the codomain is still $\{0,1\}$).  
> **username_3**: I suppose you might object that a dictator $\mathbb{R}^n\to\{0,1\}$ can be any function that depends on only one coordinate, and this would severely break the upper bound argument. I'll add a disclaimer to my answer, but I think OP will most likely be interested in the case when the domain is $\{0,1\}^n$.  
> **username_4**: Thanks, now everything is clear. Moreover, I believe that in a similar way one can obtain the optimal $O(k\log n)$ bound mentioned by Sasho. All you have to do is take $k$ copies of this matrix diagonally, so like $$\begin{array}{cccccccccccccc}   0&0&0&0&0&0&0&0&0&0&0&0&0&0\\   1&0&0&0&1&1&1&0&0&0&0&0&0&0\\   0&1&0&1&0&1&1&0&0&0&0&0&0&0\\   0&0&1&1&1&0&1&0&0&0&0&0&0&0\\  0&0&0&0&0&0&0&1&0&0&0&1&1&1\\   0&0&0&0&0&0&0&0&1&0&1&0&1&1\\   0&0&0&0&0&0&0&0&0&1&1&1&0&1 \end{array}$$  

---

