7
$\begingroup$

This is more of a philosophical question -- I am looking for a reasonable mathematical formulation of 1-class learning.

In the PAC model, it's very natural to formulate our demand on the learner: produce a hypothesis with low generalization error.

What might be a reasonable formalization of 1-class learning? This may also be called "anomaly detection": in the training phase, the learner only gets to see positive ("normal") examples, but in the test phase he needs to predict whether a given new example is positive ("normal") or negative (an anomaly). The formal details are quite open-ended -- what's a reasonable assumption on the training sample (generated from some distribution, etc)? What's a reasonable success criterion?

$\endgroup$
  • $\begingroup$ Did you find a theoretical justification for this question yet? $\endgroup$ – user13647 Feb 7 '13 at 6:33
  • $\begingroup$ Well, we wrote a paper that takes a step in this direction, but I am not totally satisfied with this approach. Would be very curious to hear feedback/ideas! $\endgroup$ – Aryeh Feb 7 '13 at 14:49
7
$\begingroup$

I think there is a model called "Learning from Positive Examples (Only)" or you can additionally allow unlabeled data (I don't remember the details). A search for these terms should bring up various papers and models. Here is one.

$\endgroup$
  • $\begingroup$ Thanks, Lev! (For some reason this requires answers of at least 15 chars) $\endgroup$ – Aryeh Jan 26 '11 at 15:12
0
$\begingroup$

If I understood your question correctly, then Valiant's seminal paper "A theory of the learnable" (Communications of the ACM 27(11), 1134-1142) defines a model you are looking for, if you exclude queries to ORACLE and stick with EXAMPLE (which provides the learner with a positive instance; however, see details of the definition in the paper). I believe it was only afterwards that this model got transformed into PAC with both positive and negative instances returned by such an oracle. (Note that, e.g., the algorithm for learning k-CNF defined in this paper does not use ORACLE, only EXAMPLE.)

$\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.