<p>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.  <a href="http://cseweb.ucsd.edu/~elkan/posonly.pdf">Here</a> is one.</p>

CC BY-SA 2.5
2011-01-26T15:12:06.060Z
Thanks, Lev! (For some reason this requires answers of at least 15 chars)
Aryeh
CC BY-SA 2.5
2011-01-26T14:20:47.013Z
2011-01-26T14:20:47.013Z
Lev Reyzin
<p>If I understood your question correctly, then Valiant's seminal paper "<a href="http://www.cse.iitk.ac.in/users/chitti/thesis/references/valiant.pdf" rel="nofollow">A theory of the learnable</a>" (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.)</p>

CC BY-SA 3.0
2013-02-07T09:50:33.003Z
2013-02-07T09:50:33.003Z
dd1
<p>This is more of a philosophical question -- I am looking for a reasonable mathematical formulation of 1-class learning.</p>

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

<p>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?</p>

CC BY-SA 3.0
2013-02-07T14:49:47.553Z
Well, we wrote a [paper](http://www.cs.bgu.ac.il/~karyeh/anomaly.pdf) 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
<lg.learning><machine-learning>
A PAC-like analogue for 1-class classification?
Aryeh
# A PAC-like analogue for 1-class classification?

(Asked by: username_0 on 2011-01-26)

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?

**Tags:** lg.learning, machine-learning

> **Comments:**
> **username_0**: Well, we wrote a [paper](http://www.cs.bgu.ac.il/~karyeh/anomaly.pdf) that takes a step in this direction, but I am not totally satisfied with this approach. Would be very curious to hear feedback/ideas!  

---

## 2 answers

### Answer by username_1 on 2011-01-26. Score: 7

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](http://cseweb.ucsd.edu/~elkan/posonly.pdf) is one.

> **Comments:**
> **username_0**: Thanks, Lev! (For some reason this requires answers of at least 15 chars)  

---

### Answer by username_2 on 2013-02-07. Score: 0

If I understood your question correctly, then Valiant's seminal paper "[A theory of the learnable](http://www.cse.iitk.ac.in/users/chitti/thesis/references/valiant.pdf)" (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.)


---

