- 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(){var c=function(){var a=document.getElementById("crt-1404221296");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-1404221296",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();
(function(){var c=function(){var a=document.getElementById("crt-1736663492");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-1736663492",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();