0

I'm not sure how to solve this problem. Problem statement is: Consider the binary classification problem where X = R d and Y = {0, 1}. Consider the class of Binary classifiers given by intersection of three half-spaces.

Show that proper learning w.r.t. this class of intersection of three half-spaces (the class F) is computationally hard to learn properly unless NP = RP. Specifically Hint: Remember we are thinking of only proper learning. Try a reduction using the 3 term DNF class. An extra hint is use d = 2m, m coordinates for the inclusion of each coordinate and m coordinates for inclusion of their negation.

I'm reducing from 3-DNF and trying to convert it to a 3-CNF which is possible by making x in [-1,+1]^d and w in [0,1]^d. But I'm not sure what steps to even go from there. Problem Description

I've written out the following as a general approach to the problem, but I'm not sure how to really explain how to prove the second statement of the reduction: Current work

1

0

Your Answer

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

Browse other questions tagged or ask your own question.