Candidate-Elimination Algorithm

References

(Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/Version_space_learning Retrieved:2017-5-28.
- Version space learning is a logical approach to machine learning, specifically binary classification. Version space learning algorithms search a predefined space of hypotheses, viewed as a set of logical sentences. Formally, the hypothesis space is a disjunction^[1] : [math]\displaystyle{ H_1 \lor H_2 \lor … \lor H_n }[/math] (i.e., either hypothesis 1 is true, or hypothesis 2, or any subset of the hypotheses 1 through). A version space learning algorithm is presented with examples, which it will use to restrict its hypothesis space; for each example, the hypotheses that are inconsistent with are removed from the space. ^[2] This iterative refining of the hypothesis space is called the candidate elimination algorithm, the hypothesis space maintained inside the algorithm its version space.

(Sammut & Webb, 2011) ⇒ Claude Sammut (editor), and Geoffrey I. Webb (editor). (2011). “Candidate-Elimination Algorithm.” In: (Sammut & Webb, 2011) p.139
- Candidate-Elimination Algorithm - Mitchell's, (1982,1997) candidate-elimination algorithm performs a bidirectional search in the hypothesis space. It maintains a set, S, of most specific hypotheses that are consistent with the training data and a set, G, of most general hypotheses consistent with the training data. These two sets form two boundaries on the version space.

(Mitchell, 1982) ⇒ Mitchell, T. M. (1982). Generalization as search. Artificial Intelligence, 18(2), 203-226.DOI:0004-3702(82)90040-6
- ABSTRACT: The problem of concept learning, or forming a general description of a class of objects given a set of examples and non-examples, is viewed here as a search problem. Existing programs that generalize from examples are characterized in terms of the classes of search strategies that they employ. Several classes of search strategies are then analyzed and compared in terms of their relative capabilities and computational complexities.

(Mitchell, 1977) ⇒ Tom M. Mitchell. (1977). “Version Spaces: A candidate elimination approach to rule learning" In: Proceedings of the 5th international joint conference on Artificial intelligence.
- ABSTRACT:An important research problem in artificial intelligence is the study of methods for learning general concepts or rules from a set of training instances. An approach to this problem is presented which is guaranteed to find, without backtracing, all rule versions consistent with a set of positive and negative training instances. The algorithm put forth uses a representation of the space of those rules consistent with the observed training data. This "rule version space" is modified in response to new training instances by eliminating candidate rule versions found to conflict with each new instance. The use of version spaces is discussed in the context of Meta-DENDRAL, a program which learns rules in the domain of chemical spectroscopy.

↑ Russell, Stuart; Norvig, Peter (2003) [1995]. Artificial Intelligence: A Modern Approach (2nd ed.). Prentice Hall. pp. 683–686. ISBN 978-0137903955.
↑ Mitchell, Tom M. (1982). “Generalization as search". Artificial Intelligence. 18 (2): 203–226. doi:10.1016/0004-3702(82)90040-6.