Skip to main content
Computer Science

Return to Question

added 264 characters in body
Source Link
Charlie Parker
Charlie Parker
  • 3.1k
  • 21
  • 37

In short, if $x \neq u_i \in \{\pm1 \}^n$ then why is:

$$ \langle x, u_i \rangle \leq n-2 $$

but not:

$$ \langle x, u_i \rangle \leq n-1 $$

?

To add context:

I was reading understanding machine learning from theory to algorithms and it had claim 20.1 section 20.3 on the section of the expressive power of Neural Networks. In the proof it said to consider "binary" vectors $\{ \pm 1 \}^n$ (which I will call Rademacher vectors). Let $f$ be a Boolean function and consider the Rademacher vectors that make $f$ output 1. If we consider some $x \in \{ \pm 1\}^n$ such that $u_i \neq x$ then they claim that:

$$ \langle x, u_i \rangle \leq n-2 $$

Which I think is false. Isn't the correct statement:

$$ \langle x, u_i \rangle \leq n-1 $$

The reason I think this is if $x \neq u_i$ then there exists at least one entry in the vector that are difference. Call it entry/index $j$. Thus $x[j] \neq u_i[j] \implies x[j]u_i[j] -1 $ since they must have opposite sign and both are entries in Rademacher vectors. Thus since we only need 1 entry for this to be true we get $-1$ instead of $-2$. In more detail an inner product is:

$$ \langle x, u_i \rangle = \sum^n_{j=1} x[j] u_i[j]$$

since there are n terms we are adding, if we have n agreements then we have a sum of n, but if we have a single disagreement then we have only a decrease of 1, right? Is that correct or am I missing something super dum?

In short, if $x \neq u_i \in \{\pm1 \}^n$ then why is:

$$ \langle x, u_i \rangle \leq n-2 $$

but not:

$$ \langle x, u_i \rangle \leq n-1 $$

?

To add context:

I was reading understanding machine learning from theory to algorithms and it had claim 20.1 section 20.3 on the section of the expressive power of Neural Networks. In the proof it said to consider "binary" vectors $\{ \pm 1 \}^n$ (which I will call Rademacher vectors). Let $f$ be a Boolean function and consider the Rademacher vectors that make $f$ output 1. If we consider some $x \in \{ \pm 1\}^n$ such that $u_i \neq x$ then they claim that:

$$ \langle x, u_i \rangle \leq n-2 $$

Which I think is false. Isn't the correct statement:

$$ \langle x, u_i \rangle \leq n-1 $$

The reason I think this is if $x \neq u_i$ then there exists at least one entry in the vector that are difference. Call it entry/index $j$. Thus $x[j] \neq u_i[j] \implies x[j]u_i[j] -1 $ since they must have opposite sign and both are entries in Rademacher vectors. Thus since we only need 1 entry for this to be true we get $-1$ instead of $-2$. Is that correct or am I missing something super dum?

In short, if $x \neq u_i \in \{\pm1 \}^n$ then why is:

$$ \langle x, u_i \rangle \leq n-2 $$

but not:

$$ \langle x, u_i \rangle \leq n-1 $$

?

To add context:

I was reading understanding machine learning from theory to algorithms and it had claim 20.1 section 20.3 on the section of the expressive power of Neural Networks. In the proof it said to consider "binary" vectors $\{ \pm 1 \}^n$ (which I will call Rademacher vectors). Let $f$ be a Boolean function and consider the Rademacher vectors that make $f$ output 1. If we consider some $x \in \{ \pm 1\}^n$ such that $u_i \neq x$ then they claim that:

$$ \langle x, u_i \rangle \leq n-2 $$

Which I think is false. Isn't the correct statement:

$$ \langle x, u_i \rangle \leq n-1 $$

The reason I think this is if $x \neq u_i$ then there exists at least one entry in the vector that are difference. Call it entry/index $j$. Thus $x[j] \neq u_i[j] \implies x[j]u_i[j] -1 $ since they must have opposite sign and both are entries in Rademacher vectors. Thus since we only need 1 entry for this to be true we get $-1$ instead of $-2$. In more detail an inner product is:

$$ \langle x, u_i \rangle = \sum^n_{j=1} x[j] u_i[j]$$

since there are n terms we are adding, if we have n agreements then we have a sum of n, but if we have a single disagreement then we have only a decrease of 1, right? Is that correct or am I missing something super dum?

Source Link
Charlie Parker
Charlie Parker
  • 3.1k
  • 21
  • 37

Why is the inner product of -1,+1 binary variables at most $n-2$ and not at most $n-1$?

In short, if $x \neq u_i \in \{\pm1 \}^n$ then why is:

$$ \langle x, u_i \rangle \leq n-2 $$

but not:

$$ \langle x, u_i \rangle \leq n-1 $$

?

To add context:

I was reading understanding machine learning from theory to algorithms and it had claim 20.1 section 20.3 on the section of the expressive power of Neural Networks. In the proof it said to consider "binary" vectors $\{ \pm 1 \}^n$ (which I will call Rademacher vectors). Let $f$ be a Boolean function and consider the Rademacher vectors that make $f$ output 1. If we consider some $x \in \{ \pm 1\}^n$ such that $u_i \neq x$ then they claim that:

$$ \langle x, u_i \rangle \leq n-2 $$

Which I think is false. Isn't the correct statement:

$$ \langle x, u_i \rangle \leq n-1 $$

The reason I think this is if $x \neq u_i$ then there exists at least one entry in the vector that are difference. Call it entry/index $j$. Thus $x[j] \neq u_i[j] \implies x[j]u_i[j] -1 $ since they must have opposite sign and both are entries in Rademacher vectors. Thus since we only need 1 entry for this to be true we get $-1$ instead of $-2$. Is that correct or am I missing something super dum?