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



Your Answer

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