Error tolerance (PAC learning)

In PAC learning, error tolerance refers to the ability of an algorithm to learn when the examples received have been corrupted in some way. In fact, this is a very common and important issue since in many applications it is not possible to access noise-free data. Noise can interfere with the learning process at different levels: the algorithm may receive data that have been occasionally mislabeled, or the inputs may have some false information, or the classification of the examples may have been maliciously adulterated.

Notation and the Valiant learning model

edit

In the following, let   be our  -dimensional input space. Let   be a class of functions that we wish to use in order to learn a  -valued target function   defined over  . Let   be the distribution of the inputs over  . The goal of a learning algorithm   is to choose the best function   such that it minimizes  . Let us suppose we have a function   that can measure the complexity of  . Let   be an oracle that, whenever called, returns an example   and its correct label  .

When no noise corrupts the data, we can define learning in the Valiant setting:[1][2]

Definition: We say that   is efficiently learnable using   in the Valiant setting if there exists a learning algorithm   that has access to   and a polynomial   such that for any   and   it outputs, in a number of calls to the oracle bounded by   , a function   that satisfies with probability at least   the condition  .

In the following we will define learnability of   when data have suffered some modification.[3][4][5]

Classification noise

edit

In the classification noise model[6] a noise rate   is introduced. Then, instead of   that returns always the correct label of example  , algorithm   can only call a faulty oracle   that will flip the label of   with probability  . As in the Valiant case, the goal of a learning algorithm   is to choose the best function   such that it minimizes  . In applications it is difficult to have access to the real value of  , but we assume we have access to its upperbound  .[7] Note that if we allow the noise rate to be  , then learning becomes impossible in any amount of computation time, because every label conveys no information about the target function.

Definition: We say that   is efficiently learnable using   in the classification noise model if there exists a learning algorithm   that has access to   and a polynomial   such that for any  ,   and   it outputs, in a number of calls to the oracle bounded by   , a function   that satisfies with probability at least   the condition  .

Statistical query learning

edit

Statistical Query Learning[8] is a kind of active learning problem in which the learning algorithm   can decide if to request information about the likelihood   that a function   correctly labels example  , and receives an answer accurate within a tolerance  . Formally, whenever the learning algorithm   calls the oracle  , it receives as feedback probability  , such that  .

Definition: We say that   is efficiently learnable using   in the statistical query learning model if there exists a learning algorithm   that has access to   and polynomials  ,  , and   such that for any   the following hold:

  1.   can evaluate   in time  ;
  2.   is bounded by  
  3.   outputs a model   such that  , in a number of calls to the oracle bounded by  .

Note that the confidence parameter   does not appear in the definition of learning. This is because the main purpose of   is to allow the learning algorithm a small probability of failure due to an unrepresentative sample. Since now   always guarantees to meet the approximation criterion  , the failure probability is no longer needed.

The statistical query model is strictly weaker than the PAC model: any efficiently SQ-learnable class is efficiently PAC learnable in the presence of classification noise, but there exist efficient PAC-learnable problems such as parity that are not efficiently SQ-learnable.[8]

Malicious classification

edit

In the malicious classification model[9] an adversary generates errors to foil the learning algorithm. This setting describes situations of error burst, which may occur when for a limited time transmission equipment malfunctions repeatedly. Formally, algorithm   calls an oracle   that returns a correctly labeled example   drawn, as usual, from distribution   over the input space with probability  , but it returns with probability   an example drawn from a distribution that is not related to  . Moreover, this maliciously chosen example may strategically selected by an adversary who has knowledge of  ,  ,  , or the current progress of the learning algorithm.

Definition: Given a bound   for  , we say that   is efficiently learnable using   in the malicious classification model, if there exist a learning algorithm   that has access to   and a polynomial   such that for any  ,   it outputs, in a number of calls to the oracle bounded by   , a function   that satisfies with probability at least   the condition  .

Errors in the inputs: nonuniform random attribute noise

edit

In the nonuniform random attribute noise[10][11] model the algorithm is learning a Boolean function, a malicious oracle   may flip each  -th bit of example   independently with probability  .

This type of error can irreparably foil the algorithm, in fact the following theorem holds:

In the nonuniform random attribute noise setting, an algorithm   can output a function   such that   only if  .

See also

edit

References

edit
  1. ^ Valiant, L. G. (August 1985). Learning Disjunction of Conjunctions. In IJCAI (pp. 560–566).
  2. ^ Valiant, Leslie G. "A theory of the learnable." Communications of the ACM 27.11 (1984): 1134–1142.
  3. ^ Laird, P. D. (1988). Learning from good and bad data. Kluwer Academic Publishers.
  4. ^ Kearns, Michael. "Efficient noise-tolerant learning from statistical queries Archived 3 May 2013 at the Wayback Machine." Journal of the ACM 45.6 (1998): 983–1006.
  5. ^ Brunk, Clifford A., and Michael J. Pazzani. "An investigation of noise-tolerant relational concept learning algorithms." Proceedings of the 8th International Workshop on Machine Learning. 1991.
  6. ^ Kearns, M. J., & Vazirani, U. V. (1994). An introduction to computational learning theory, chapter 5. MIT press.
  7. ^ Angluin, D., & Laird, P. (1988). Learning from noisy examples. Machine Learning, 2(4), 343–370.
  8. ^ a b Kearns, M. (1998). [www.cis.upenn.edu/~mkearns/papers/sq-journal.pdf Efficient noise-tolerant learning from statistical queries]. Journal of the ACM, 45(6), 983–1006.
  9. ^ Kearns, M., & Li, M. (1993). [www.cis.upenn.edu/~mkearns/papers/malicious.pdf Learning in the presence of malicious errors]. SIAM Journal on Computing, 22(4), 807–837.
  10. ^ Goldman, S. A., & Sloan, Robert, H. (1991). The difficulty of random attribute noise. Technical Report WUCS 91 29, Washington University, Department of Computer Science.
  11. ^ Sloan, R. H. (1989). Computational learning theory: New models and algorithms (Doctoral dissertation, Massachusetts Institute of Technology).