02/02/2021

SAT-based Decision Tree Learning for Large Data Sets

Andre Schidler, Stefan Szeider

Keywords:

Abstract Paper Similar Papers

Abstract: Decision trees of low depth are beneficial for understanding and interpreting the data they represent. Unfortunately, finding a decision tree of lowest depth that correctly represents given data is NP-hard. Hence known algorithms either (i) utilize heuristics that do not optimize the depth or (ii) are exact but scale only to small or medium-sized instances. We propose a new hybrid approach to decision tree learning, combining heuristic and exact methods in a novel way. More specifically, we employ SAT encodings repeatedly to local parts of a decision tree provided by a standard heuristic, leading to a global depth improvement. This allows us to scale the power of exact SAT-based methods to almost arbitrarily large data sets. We evaluate our new approach experimentally on a range of real-world instances that contain up to several thousand samples. In almost all cases, our method successfully decreases the depth of the initial decision tree; often, the decrease is significant.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948862
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 3:13 
 0
 0
 0
 0
 15:44 
 0
 0
 0
 0
 14:32 
 1
 0
 0
 1
 12:56 
 0
 0
 0
 0
 11:15 
 0
 0
 0
 0
 3:07 
 0
 0
 0
 0
 16:59 
 0
 0
 0
 0
 2:58 
 0
 0
 0
 0
 12:19 
 0
 0
 0
 0
 4:41 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 14:05 
 0
 0
 0
 0
 18:06 
 0
 0
 0
 0
 17:38 
 0
 0
 0
 0
 3:19 
 0
 0
 0
 0
 10:21 
 0
 0
 0
 0
 14:38 
 0
 0
 0
 0
 14:24 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 10:14 
 0
 0
 0
 0
 3:00 
 0
 0
 0
 0
 5:45 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 24:38 
 0
 0
 0
 0
 3:06 
 0
 0
 0
 0
 13:10 
 0
 0
 0
 0
 4:56 
 0
 0
 0
 0
 9:34 
 0
 0
 0
 0
 3:05 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 14:17 
 0
 0
 0
 0
 20:29 
 0
 0
 0
 0
 16:52 
 0
 0
 0
 0
 2:38 
 0
 1
 0
 0
 3:21 
 0
 0
 0
 0
 10:53 
 0
 0
 0
 0
 10:40 
 0
 0
 0
 0
 17:29 
 0
 0
 0
 0
 17:50 
 0
 0
 0
 0
 3:23