Making the best moves at each decision point will not always result in the best result 🔴

What are greedy algorithms?

Let's figure it out through decision trees!

🧵

1/8

In decision trees, the algorithm is making local decisions at every node.

It tries to find the best question, which helps to split the node.

Local optimal decisions can result in bad global results.

Why?

2/8

These types of algorithms only depend on the decisions made before.

They are not able to see into the future, nor reconsider their decisions.

Now the simple example 🔽

3/8

You get a simple question twice.

"How many apples do you want?"

Of course, at this point, you would choose the 5 apples instead of the 3.

4/8

Now you have to make the same decision.

You have 5 apples, you want to add 1 or 2?

If you select the best available option, you will end up with 7 apples.

Not bad right?

Not bad, but not that good.

Let's check what is on the other side.

5/8

What if you select 3 apples in the first case?

At the second decision point, you will get 8 apples for sure, so in either case, you will end up with 11 apples.

You made the "wrong" first decision but still ended up with a better result.

6/8

In the example, the rules were similar to decision trees.

You were not allowed to see into the future, nor reconsider your decision.

This is how greedy algorithms work.

7/8

That's it for today.

I hope you've found this thread helpful.

Like/Retweet the first tweet below for support and follow @levikul09 for more Data Science threads.

Thanks 😉

8/8