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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Did you find a theoretical justification for this question yet? $\endgroup$
    – user13647
    Commented Feb 7, 2013 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
    Commented Feb 7, 2013 at 14:49

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, Lev! (For some reason this requires answers of at least 15 chars) $\endgroup$
    – Aryeh
    Commented Jan 26, 2011 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.)

Improve this answer
$\endgroup$

Your Answer

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

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