On Conditional Branches in Optimal Decision Trees

Channel:

Google TechTalks

Subscribers:

348,000

Published on October 9, 2007 1:44:14 AM ● Video Link: https://www.youtube.com/watch?v=uelPYSuGbeM

Duration: 37:28

2,711 views

6

Google Tech Talks February 8, 2007

Abstract

Decision trees are one of the most fundamental programming abstractions, and a commonly used type of decision tree is the alphabetic binary tree, which uses (without loss of generality) "less than"/"greater than or equal to" tests in order to determine an outcome event. The process of finding an optimal alphabetic binary tree for a known probabily distribution on outcome events usually has the underlying assumption that the cost per decision is uniform and thus independent of the outcome of the decision. Algorithms without this assumption generally use one cost if the decision result is "less than" and another cost if it is "greater than." In practice,...