1
$\begingroup$

In other words can a linear classifier learn to correctly assign a class (label 0 to 3) for an input of 3 bits? Intuitively this cannot work, since the half-adder circuit contains an XOR block, which cannot be solved by a linearly classifier(with applying a kernel trick-transformation to the data).

In a lecture I just got told that intuitively the sum function should be a linear function ($\mathbb{1}^Tx=y$). But a linear classifier doesn't perform well on the task, getting about 75% accuracy, which is to be expected when trying to linearly classify XOR. Since the sum function seems the be a linear function, where does the non-linearity come from exactly? Some kind of change in representation of the data(bits to integers?)

So, can a linear regressor or classifier learn to sum 3 bits into an integer between 0-3? Why or why not?

EDIT: Assume you have a dataset like this:

x0   x1   x2   y
0     0    0   0
1     0    0   1
1     1    0   2
1     0    1   2
1     1    1   3
...
Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ Could you explain what you mean by "linear classifier"? In statistics this term is never defined or described in terms of circuits, which makes it sound like you are using it in a sense unusual in statistics. $\endgroup$
    – whuber ♦
    Commented Jun 2, 2021 at 13:37
  • $\begingroup$ I just used the circuit as a way to try and describe what the sum function should look like, e.g. what components it has, and whether that's linear or not. Since adding integers in computing requires an XOR block and XOR is not linear separable, I came to the conclusion that the sum function must be non-linear as well. My questions is whether this is correct and why/why not. Whether a regressor or classifier is used doesn't really matter to the question, what matters is whether the problem can be solved using a linear method/approximator(e.g. LogReg). $\endgroup$
    – jaaq
    Commented Jun 2, 2021 at 13:53
  • 1
    $\begingroup$ I think there’s some confusion here between addition as an abstract (‘declarative’) operation between two numbers and the representation of this operation within a computer. In the former case, your model never has to learn how to do XOR on bits. Addition of two integers is available as a subroutine that the model can employ. $\endgroup$
    – Arya McCarthy
    Commented Jun 2, 2021 at 14:30
  • $\begingroup$ Possibly. In the same assignment we had a dataset for XOR where we showed that a linear model can only be up to 75% accurate on the task, since there's no fitting hyperplane. See here. Maybe I mixed it into the sum problem without needing to, though it confused me enough to ask why sum works and xor does not. Also our example was more sophisticated, involving input spikes for SNNs and classifying input or Liquid State. Maybe breaking it down like this makes no sense, I am not sure. Maybe this MWE doesn't represent the essence of my question well. $\endgroup$
    – jaaq
    Commented Jun 2, 2021 at 14:34

1 Answer 1

Reset to default
4
$\begingroup$

So, can a linear regressor or classifier learn to sum 3 bits into an integer between 0-3? Why or why not?

Yes, a linear regression can solve this problem.

Write the prediction as an inner product $w ^T x=y$. A weight vector $w$ that is all 1s yields the desired result exactly. Since we only have eight cases (3 bits, so $2^3$ cases), you can just prove this directly by exhaustion. Or you could observe that the sum operation is just a special case of an inner product.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, that kind of answers/elaborates on the intuition that the sum function should be a linear function. Then the other part of my question is: How is this related to the XOR function? Since the sum function in logic requires the XOR function, which cannot be calculated without a nonlinearity, shouldn't this be reflected here somehow as well? $\endgroup$
    – jaaq
    Commented Jun 2, 2021 at 14:25
  • 3
    $\begingroup$ Computing a (weighted or unweighted) sum isn't a classification task, it's a regression task. $\endgroup$
    – Sycorax ♦
    Commented Jun 2, 2021 at 14:40
  • $\begingroup$ That depends on whether I want a single output value or class probabilities for the classes from 0 to 3. $\endgroup$
    – jaaq
    Commented Jun 2, 2021 at 17:01
  • $\begingroup$ The sum of some numbers is not a probability of class membership. We can see this because 2 and 3 are larger than 1, but probabilities must be nonnegative and sum to 1. $\endgroup$
    – Sycorax ♦
    Commented Jun 2, 2021 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.