optimal decision tree np-hard

Clash Royale CLAN TAG#URR8PPP

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;

up vote
1
down vote

favorite

Reading Elements of Statistical Learning and it says that decision trees are often constructed using greedy algorithms because it is computationally infeasible to create an optimal decision tree. There is a proof here but it relies upon several other topics (exact covers, 3-dimensional matching), so I was wondering first if anyone has an intuitive explanation for this.

cart

share|cite|improve this question

asked 4 hours ago

allstar

20916

add a comment | 

up vote
1
down vote

favorite

Reading Elements of Statistical Learning and it says that decision trees are often constructed using greedy algorithms because it is computationally infeasible to create an optimal decision tree. There is a proof here but it relies upon several other topics (exact covers, 3-dimensional matching), so I was wondering first if anyone has an intuitive explanation for this.

cart

share|cite|improve this question

asked 4 hours ago

allstar

20916

add a comment | 

up vote
1
down vote

favorite

up vote
1
down vote

favorite

Reading Elements of Statistical Learning and it says that decision trees are often constructed using greedy algorithms because it is computationally infeasible to create an optimal decision tree. There is a proof here but it relies upon several other topics (exact covers, 3-dimensional matching), so I was wondering first if anyone has an intuitive explanation for this.

cart

share|cite|improve this question

asked 4 hours ago

allstar

20916

Reading Elements of Statistical Learning and it says that decision trees are often constructed using greedy algorithms because it is computationally infeasible to create an optimal decision tree. There is a proof here but it relies upon several other topics (exact covers, 3-dimensional matching), so I was wondering first if anyone has an intuitive explanation for this.

cart

cart

share|cite|improve this question

asked 4 hours ago

allstar

20916

share|cite|improve this question

asked 4 hours ago

allstar

20916

share|cite|improve this question

share|cite|improve this question

asked 4 hours ago

allstar

20916

asked 4 hours ago

allstar

20916

asked 4 hours ago

allstar

20916

20916

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
2
down vote



accepted

Complexity theorists have identified a class of problems called "NP-hard" which are "intractable", meaning that no one has figured out how to solve them efficiently, despite much effort.

Suppose you know some problem A which you know is in this class of "NP-hard" problems. And suppose you can solve it by converting it to an instance of finding the optimal decision tree. Then, you know that finding an optimal decision tree must be very hard, because if it was easy, you could just solve problem A by converting it to an instance of the optimal decision tree problem and solving that. This is called a reduction.

For example, you can convert the problem of finding the maximum number in a list to the problem of sorting a list, since you can always sort the list, and then return the last number in the sorted list as your answer. You've now shown sorting is at least as hard as finding the maximum number, or analogously, that finding the optimal decision tree is as hard as problem A.

In the paper you linked, problem A goes by the name "exact cover by 3-sets". Then, you might ask how complexity theorists proved EC3 or any of the NP-hard problems are actually intractable. Actually there is no such proof, but the conjecture that NP-hard problems cannot be solved efficiently is called P $neq$ NP.

(This answer misses out on a lot of complexity theory details for the sake of intuition, so it's not completely rigorous.)

share|cite|improve this answer

edited 3 hours ago

answered 3 hours ago

shimao

6,57611226

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you shimao, I think I followed the idea of comparing to another type of problem, but the key point is that if something is an NP-hard problem, the conjecture suggests that it cannot be solved in polynomial time. So I guess that currently the best solution for optimal decision tree is worse than polynomial, hence it's in the NP-hard category? For example, you could try all the possible trees in exponential time, which is worse than polynomial.
  – allstar
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  @allstar You are right that NP-hard suggests it cannot be solved in polynomial time, however, just because we don't know a polytime algorithm to a problem does not mean it's NP-hard (see graph isomorphism). There is actually a formal mathematical definition of what it means to be NP-hard which extends beyond not knowing how to solve a problem efficiently.
  – shimao
  2 hours ago
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "65"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstats.stackexchange.com%2fquestions%2f370645%2foptimal-decision-tree-np-hard%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote



accepted

Complexity theorists have identified a class of problems called "NP-hard" which are "intractable", meaning that no one has figured out how to solve them efficiently, despite much effort.

Suppose you know some problem A which you know is in this class of "NP-hard" problems. And suppose you can solve it by converting it to an instance of finding the optimal decision tree. Then, you know that finding an optimal decision tree must be very hard, because if it was easy, you could just solve problem A by converting it to an instance of the optimal decision tree problem and solving that. This is called a reduction.

For example, you can convert the problem of finding the maximum number in a list to the problem of sorting a list, since you can always sort the list, and then return the last number in the sorted list as your answer. You've now shown sorting is at least as hard as finding the maximum number, or analogously, that finding the optimal decision tree is as hard as problem A.

In the paper you linked, problem A goes by the name "exact cover by 3-sets". Then, you might ask how complexity theorists proved EC3 or any of the NP-hard problems are actually intractable. Actually there is no such proof, but the conjecture that NP-hard problems cannot be solved efficiently is called P $neq$ NP.

(This answer misses out on a lot of complexity theory details for the sake of intuition, so it's not completely rigorous.)

share|cite|improve this answer

edited 3 hours ago

answered 3 hours ago

shimao

6,57611226

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you shimao, I think I followed the idea of comparing to another type of problem, but the key point is that if something is an NP-hard problem, the conjecture suggests that it cannot be solved in polynomial time. So I guess that currently the best solution for optimal decision tree is worse than polynomial, hence it's in the NP-hard category? For example, you could try all the possible trees in exponential time, which is worse than polynomial.
  – allstar
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  @allstar You are right that NP-hard suggests it cannot be solved in polynomial time, however, just because we don't know a polytime algorithm to a problem does not mean it's NP-hard (see graph isomorphism). There is actually a formal mathematical definition of what it means to be NP-hard which extends beyond not knowing how to solve a problem efficiently.
  – shimao
  2 hours ago
  
  

  
  
  
  

add a comment | 

up vote
2
down vote



accepted

Complexity theorists have identified a class of problems called "NP-hard" which are "intractable", meaning that no one has figured out how to solve them efficiently, despite much effort.

Suppose you know some problem A which you know is in this class of "NP-hard" problems. And suppose you can solve it by converting it to an instance of finding the optimal decision tree. Then, you know that finding an optimal decision tree must be very hard, because if it was easy, you could just solve problem A by converting it to an instance of the optimal decision tree problem and solving that. This is called a reduction.

For example, you can convert the problem of finding the maximum number in a list to the problem of sorting a list, since you can always sort the list, and then return the last number in the sorted list as your answer. You've now shown sorting is at least as hard as finding the maximum number, or analogously, that finding the optimal decision tree is as hard as problem A.

In the paper you linked, problem A goes by the name "exact cover by 3-sets". Then, you might ask how complexity theorists proved EC3 or any of the NP-hard problems are actually intractable. Actually there is no such proof, but the conjecture that NP-hard problems cannot be solved efficiently is called P $neq$ NP.

(This answer misses out on a lot of complexity theory details for the sake of intuition, so it's not completely rigorous.)

share|cite|improve this answer

edited 3 hours ago

answered 3 hours ago

shimao

6,57611226

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you shimao, I think I followed the idea of comparing to another type of problem, but the key point is that if something is an NP-hard problem, the conjecture suggests that it cannot be solved in polynomial time. So I guess that currently the best solution for optimal decision tree is worse than polynomial, hence it's in the NP-hard category? For example, you could try all the possible trees in exponential time, which is worse than polynomial.
  – allstar
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  @allstar You are right that NP-hard suggests it cannot be solved in polynomial time, however, just because we don't know a polytime algorithm to a problem does not mean it's NP-hard (see graph isomorphism). There is actually a formal mathematical definition of what it means to be NP-hard which extends beyond not knowing how to solve a problem efficiently.
  – shimao
  2 hours ago
  
  

  
  
  
  

add a comment | 

up vote
2
down vote



accepted

up vote
2
down vote



accepted

Complexity theorists have identified a class of problems called "NP-hard" which are "intractable", meaning that no one has figured out how to solve them efficiently, despite much effort.

Suppose you know some problem A which you know is in this class of "NP-hard" problems. And suppose you can solve it by converting it to an instance of finding the optimal decision tree. Then, you know that finding an optimal decision tree must be very hard, because if it was easy, you could just solve problem A by converting it to an instance of the optimal decision tree problem and solving that. This is called a reduction.

For example, you can convert the problem of finding the maximum number in a list to the problem of sorting a list, since you can always sort the list, and then return the last number in the sorted list as your answer. You've now shown sorting is at least as hard as finding the maximum number, or analogously, that finding the optimal decision tree is as hard as problem A.

In the paper you linked, problem A goes by the name "exact cover by 3-sets". Then, you might ask how complexity theorists proved EC3 or any of the NP-hard problems are actually intractable. Actually there is no such proof, but the conjecture that NP-hard problems cannot be solved efficiently is called P $neq$ NP.

(This answer misses out on a lot of complexity theory details for the sake of intuition, so it's not completely rigorous.)

share|cite|improve this answer

edited 3 hours ago

answered 3 hours ago

shimao

6,57611226

Complexity theorists have identified a class of problems called "NP-hard" which are "intractable", meaning that no one has figured out how to solve them efficiently, despite much effort.

Suppose you know some problem A which you know is in this class of "NP-hard" problems. And suppose you can solve it by converting it to an instance of finding the optimal decision tree. Then, you know that finding an optimal decision tree must be very hard, because if it was easy, you could just solve problem A by converting it to an instance of the optimal decision tree problem and solving that. This is called a reduction.

For example, you can convert the problem of finding the maximum number in a list to the problem of sorting a list, since you can always sort the list, and then return the last number in the sorted list as your answer. You've now shown sorting is at least as hard as finding the maximum number, or analogously, that finding the optimal decision tree is as hard as problem A.

In the paper you linked, problem A goes by the name "exact cover by 3-sets". Then, you might ask how complexity theorists proved EC3 or any of the NP-hard problems are actually intractable. Actually there is no such proof, but the conjecture that NP-hard problems cannot be solved efficiently is called P $neq$ NP.

(This answer misses out on a lot of complexity theory details for the sake of intuition, so it's not completely rigorous.)

share|cite|improve this answer

edited 3 hours ago

answered 3 hours ago

shimao

6,57611226

share|cite|improve this answer

share|cite|improve this answer

edited 3 hours ago

edited 3 hours ago

edited 3 hours ago

answered 3 hours ago

shimao

6,57611226

answered 3 hours ago

shimao

6,57611226

answered 3 hours ago

shimao

6,57611226

6,57611226

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you shimao, I think I followed the idea of comparing to another type of problem, but the key point is that if something is an NP-hard problem, the conjecture suggests that it cannot be solved in polynomial time. So I guess that currently the best solution for optimal decision tree is worse than polynomial, hence it's in the NP-hard category? For example, you could try all the possible trees in exponential time, which is worse than polynomial.
  – allstar
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  @allstar You are right that NP-hard suggests it cannot be solved in polynomial time, however, just because we don't know a polytime algorithm to a problem does not mean it's NP-hard (see graph isomorphism). There is actually a formal mathematical definition of what it means to be NP-hard which extends beyond not knowing how to solve a problem efficiently.
  – shimao
  2 hours ago
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you shimao, I think I followed the idea of comparing to another type of problem, but the key point is that if something is an NP-hard problem, the conjecture suggests that it cannot be solved in polynomial time. So I guess that currently the best solution for optimal decision tree is worse than polynomial, hence it's in the NP-hard category? For example, you could try all the possible trees in exponential time, which is worse than polynomial.
  – allstar
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  @allstar You are right that NP-hard suggests it cannot be solved in polynomial time, however, just because we don't know a polytime algorithm to a problem does not mean it's NP-hard (see graph isomorphism). There is actually a formal mathematical definition of what it means to be NP-hard which extends beyond not knowing how to solve a problem efficiently.
  – shimao
  2 hours ago
  
  

  
  
  
  

Thank you shimao, I think I followed the idea of comparing to another type of problem, but the key point is that if something is an NP-hard problem, the conjecture suggests that it cannot be solved in polynomial time. So I guess that currently the best solution for optimal decision tree is worse than polynomial, hence it's in the NP-hard category? For example, you could try all the possible trees in exponential time, which is worse than polynomial.
– allstar
2 hours ago

Thank you shimao, I think I followed the idea of comparing to another type of problem, but the key point is that if something is an NP-hard problem, the conjecture suggests that it cannot be solved in polynomial time. So I guess that currently the best solution for optimal decision tree is worse than polynomial, hence it's in the NP-hard category? For example, you could try all the possible trees in exponential time, which is worse than polynomial.
– allstar
2 hours ago

2

2

@allstar You are right that NP-hard suggests it cannot be solved in polynomial time, however, just because we don't know a polytime algorithm to a problem does not mean it's NP-hard (see graph isomorphism). There is actually a formal mathematical definition of what it means to be NP-hard which extends beyond not knowing how to solve a problem efficiently.
– shimao
2 hours ago

@allstar You are right that NP-hard suggests it cannot be solved in polynomial time, however, just because we don't know a polytime algorithm to a problem does not mean it's NP-hard (see graph isomorphism). There is actually a formal mathematical definition of what it means to be NP-hard which extends beyond not knowing how to solve a problem efficiently.
– shimao
2 hours ago

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstats.stackexchange.com%2fquestions%2f370645%2foptimal-decision-tree-np-hard%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email