# A PAC-like analogue for 1-class classification?

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?

• Did you find a theoretical justification for this question yet? – user13647 Feb 7 '13 at 6:33
• 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! – Aryeh Feb 7 '13 at 14:49

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.

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

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.)