0
$\begingroup$

In a typical supervised learning problem, one observe $(X,Y)$ where $Y$ is a categorical variable. We confront the such a problem that $Y$ is hidden and instead $(X,Z)$ is observed where both covariates lie in $R^p$. The goal is to find the hyperplanes $w_X,w_Z$ such that $Y=1$ if and only if $(w_X,X)<0\wedge (w_Z,Z)<0$, and $Y=-1$ if and only if $(w_X,X)>0\wedge (w_Z,Z)>0$. The objective is to learn $w_X,w_Z$.

Any idea on such problem? How to adapt SVM to it?

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't quite see the point of introducing $Z$. Unsupdervised SVM is typically formalized in the literature as the Furthest Hyperplane Problem: "Given a set of $n$ points in $\mathbb{R}^d$, the objective is to produce the hyperplane (passing through the origin) which maximizes the separation margin, that is, the minimal distance between the hyperplane and any input point." That definition is taken from Karnin, Liberty, Lovett, Schwartz, Weinstein: Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem. COLT 2012: 2.1-2.17, [pdf here: http://www.jmlr.org/proceedings/papers/v23/karnin12/karnin12.pdf ] where the authors give a nearly optimal (under standard assumptions) efficient approximation algorithm for solving this NP-hard problem.

$\endgroup$
1
  • $\begingroup$ The problem we encountered is not the typical unsupervised SVM problem. But it is a definite question and is different from the problem of finding $w_X,w_Z$ that maximize the sesperation margin $(w_X,X)+(w_Z,Z)$. $\endgroup$
    – Jiayi Liu
    May 12, 2016 at 9:49

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.