Divide-and-Conquer Learning Task
A Divide-and-Conquer Learning Task is a Machine Learning Task for inducing Decision Trees.
- AKA: Recursive Partitioning Task; TDIDT Strategy.
- Context:
- It can be solved by a Divide-and-Conquer Learning System that implements a Divide-and-Conquer Learning Algorithm.
- It divides the dataset into smaller sets and recursively call itself on each subset.
- Example(s):
- Counter-Example(s):
See: Covering Algorithm, Recurrence Relation, Computer Science, Algorithm Design Paradigm, Algorithm, Sorting Algorithm, Quicksort, Merge Sort, Multiplication Algorithm, Karatsuba Algorithm, Closest Pair of Points Problem, Syntactic Analysis, Top-Down Parser.
References
2021
- (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm Retrieved:2021-5-16.
- In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.g., the Karatsuba algorithm), finding the closest pair of points, syntactic analysis (e.g., top-down parsers), and computing the discrete Fourier transform (FFT).
Designing efficient divide-and-conquer algorithms can be difficult. As in mathematical induction, it is often necessary to generalize the problem to make it amenable to recursive solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving recurrence relations.
- In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
2017
- (Sammut & Webb, 2017) ⇒ Claude Sammut (editor), and Geoffrey I. Webb (editor). (2017). “Divide-and-Conquer Learning”. In: (Sammut & Webb, 2017).
- QUOTE: The divide-and-conquer strategy is a learning algorithm for inducing Decision Trees. Its name reflects its key idea, which is to successively partition the dataset into smaller sets (the divide part) and recursively call itself on each subset (the conquer part). It should not be confused with the separate-and-conquer strategy which is used in the Covering Algorithm for rule learning.