- Random Classification Noise Model: The same as in PAC learning, except that when drawing an example, there is a probability of that the class label is flipped.
- Take learning disjunctions as an example:
- Let be the true label and the observed (probably flipped) label.
- Let be the set of relevant literals in the target function and .
- For , we have and .
- Assume for , . Then, to identify if , we only need to estimate (by sampling) to within . The number of samples required is .

- Statistical Query Model:
- SQ-Model can be seen as a restriction of PAC Model, where the learning algorithm cannot access directly to the example oracle. Instead, a SQ-learner can only make statistical queries of the form , which receives within additive error , where is a mapping . So the statistical algorithm can ask for the expectation, up to accuracy of any Boolean function of an example and its label. (We can replace Boolean function with bounded real-valued function).
- Algorithms in SQ-model are resistant to random classification noise.
- The proof idea is to show that each statistical query can be efficiently estimated by sampling from the noisy examples.
- Let and
- .
- can be estimated by sampling from the noisy examples (ignore the labels) and calculate the fraction of .
- Note that , and so can be estimated from the noisy examples.
- Therefore, it suffices to show can be estimated efficiently.
- . Rearrange, we get
- Therefore, we only need to estimate to within additive error of .

- E.g. Perceptron in SQ-model
- Ask for to within . Then update .

Advertisements
(function(g,$){if("undefined"!=typeof g.__ATA){
g.__ATA.initAd({collapseEmpty:'after', sectionId:26942, width:300, height:250});
g.__ATA.initAd({collapseEmpty:'after', sectionId:114160, width:300, height:250});
}})(window,jQuery);
var o = document.getElementById('crt-903372864');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-903372864",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-903372864'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}
var o = document.getElementById('crt-718234615');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-718234615",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-718234615'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}