0
$\begingroup$

Before facing this question, I always thought non-learnable problems are those which the provided data for the problem has high amount of outliers, those which don't have sufficient features or those for which the Bayes error is large because of having same features with different labels. As you can see, it seems that the data is fine because the learning should be comparable with human level inference. A human can distinguish between even or odd numbers by just looking at them. I know that we as human begins, do modulus two operation in our mind to decide whether a number is even or odd, the feature extraction part, but we are doing that with just the number itself. It is clear that we can not find a decision boundary to be able to generalize because the inputs have alternative behavior. 1 is even 2 is odd, 3 is even 4 is odd and all the other numbers in this manner. I want to know this kind of problem ,which does not have the mentioned problems which may cause an algorithm not to learn, has any special name?

$\endgroup$
3
$\begingroup$

In this discussion, it is described how a neural network that distinguishes odd and even numbers can be constructed. Your question can be rephrased more generally: Is there a function that cannot be learned by a machine learning algorithm. This question was discussed here and here. Both discussions refer to the Universal Approximation Theorem that basically states that any computable function on a given finite range can be approximated by a neural network. So, what is left is uncomputable functions or undecidable problems. These cannot be learned by a machine-learning algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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