 |
|
| Computers Forum Index » Computer Artificial Intelligence - Neural Nets » A Question About PAC Learning... |
|
Page 1 of 1 |
|
| Author |
Message |
| DCR... |
 Posted: Wed Oct 28, 2009 12:46 am |
|
|
|
Guest
|
This question is from the book "An Introduction to Computational
Learning Theory" by Kearns and Vazirani.
You can find an alternative phrasing here (screenshot of textbook
page):
http://imgur.com/oE2ep.jpg
Consider the following two-oracle variant of the PAC model: when c is
the target concept, there are separate and arbitrary distributions:
D+ over only the positive examples of c and D- over only the negative
examples of c.
The learning algorithm now has access to two oracles O1(c,D+), O2
(c,D-) that return a random positive example or a random negative
example each time.
For error parameter e and delta, the learning algorithm must find a
hypothesis satisfying two condition:
1) "For all examples from D+, with probability 1-delta, the
probability that the learning algorithm is wrong for any given example
is at most e"
2) "For all examples from D-, with probability 1-delta, the
probability that the learning algorithm is wrong for any given example
is at most e".
Let C be any concept class. Prove that C is efficiently PAC learnable
in the original one-oracle model if and only if C is efficiently PAC
learnable using in the two-oracle model. In other words, prove these 2
models are equivalent. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Tue Dec 01, 2009 1:48 pm
|
|