4
$\begingroup$

$\DeclareMathOperator{\sgn}{sign}$The perceptron (similarly, logistic regression) of the form $y=\sgn(w^T \cdot x+b)$ is famously known for its inability to solve the XOR problem, meaning it can get only to 75% accuracy.

I'm trying to understand what is its maximal accuracy on a generalized n bit XOR problem, which is the parity problem. The $n$ bit parity function returns, given a vector of $n$ bits, the parity of the number of 1 bits (0 if the number of 1 bits is even, 1 otherwise).

My initial hypothesis was that it should be $1/2+1/(2^n) $, meaning there we can correctly classify half of the points, plus one more.

However I was surprised to realize that the accuracy on the 3bit parity is 75% as well.

So for $n > 2$, empirically I'm getting $ 1/2 + 1/2^{(n-1)} $.

Is that true? What is the proof?

Improve this question
$\endgroup$
3
  • $\begingroup$ Welcome! What is the plane that gets 75% in 3bits? $\endgroup$
    – Jaume Oliver Lafont
    Commented Jan 29, 2023 at 23:12
  • $\begingroup$ And what is a"perceptron"? $\endgroup$
    – fedja
    Commented Jan 30, 2023 at 1:54
  • $\begingroup$ @fedja, I've added a clarification about the form of the perceptron. $\endgroup$
    – ido4848
    Commented Jan 30, 2023 at 6:37

1 Answer 1

Reset to default
4
$\begingroup$

This is not a complete answer but hopefully contains useful hints.

In the 2-bit case, there are three types of points, having $0$, $1$ or $2$ bits on. The four lines that achieve 75% accuracy with maximum margin are $x_0+x_1=\frac{1}{2} $ and $x_0+x_1=\frac{3}{2}$, $x_0-x_1=\frac{1}{2}$ and $x_0-x_1=-\frac{1}{2}$.

With 3 bits, there are $1, 3, 3, 1$ points having $0, 1, 2, 3$ bits on. This is naturally represented in 3D space. A plane between the parallel planes described by the three-point sets classifies correctly $6$ points over $8$, $\frac{3}{4}$ as well.

In 4 bits, with point counts $1, 4, 6, 4, 1$, there is correct classification for $4+6+1$ points, $\frac{11}{16}$.

If the patterns continues the same way, the number of points classified correctly is $2,3,6,11,22,42,84,163,326,638,1276,2510,5020,9908,19816,39203...$

This conjectured sequence is not in the OEIS and has the following equation.

$$\sum_{k=0}^{n/2} \binom{n}{k} $$ for $k$ even,

$$\sum_{k=0}^{(n-1)/2} \binom{n-1}{k} $$ for $k$ odd.

Since the odd index values in the sequence are the double of their previous count and the accuracy is obtained dividing by $2^n$, the repetition observed in $2$ and $3$ bits (repeating accuracy $\frac{3}{4}$) follows for all even-odd pairs. For instance, $\frac{11}{16}$ is the accuracy obtained at $4$ and $5$ bits.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Yes, with 4 bits, if you classify "even" when $s := \sum x_i < 2.5$, you get correct classification for $s=0, 2, 3$, that is $1+6+4=11$ points. Whether this is the best possible, I have no idea. $\endgroup$
    – Jukka Kohonen
    Commented Jan 30, 2023 at 11:14
  • $\begingroup$ The symmetric solution would be "even" when $\sum{x_i} >1.5$, which hits $s=1,2,4$ with $4+6+1=11$ points. Considering symmetric linear combinations of the inputs... is there any possible best solution? $\endgroup$
    – Jaume Oliver Lafont
    Commented Jan 30, 2023 at 12:03
  • 1
    $\begingroup$ FWIW, the complementary sequence 0,1,2,5,10,22,44,93 (number of points misclassified by that particular linear classifier) is found as OEIS A045621. $\endgroup$
    – Jukka Kohonen
    Commented Jan 31, 2023 at 19:34
  • $\begingroup$ The article The Minimum Number of Errors in the N-Parity and its Solution with an Incremental Neural Network (Torres-Moreno et al 2002) claims a theorem about the minimal number of errors, but the proof seems to take it granted that the optimal hyperplane is of the form $\sum x_i = c$, leading directly to the summation of the binomial coefficients. Perhaps it is well-known or obvious that this is the optimal orientation of the separating hyperplane, but it is not obvious to me and I did not see this issue addressed. $\endgroup$
    – Jukka Kohonen
    Commented Feb 1, 2023 at 8:05
  • $\begingroup$ It is neither obvious to me. Even in the simple 2d case, the boundary line between two points can have multiple orientations. We need the three support vectors to determine the line, two points do not suffice. So let us keep the "conjecture" caveat, right? I thought about basic orientations in 3d (hyperplane perpendicular to no axis plane, to one plane, to two planes) and this is the best. But how to generalize to higher dimensions? Plus, the optimal orientation is not unique. I wrongly mentioned only two lines in the answer, but there are four, since there are four three-point sets. $\endgroup$
    – Jaume Oliver Lafont
    Commented Feb 1, 2023 at 8:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .