Attribute-based representations Hypothesis spaces How many distinct decision trees with n Boolean attributes?7 a ta u -uu uuu Tha (T)e (F) Decision trees Hypothesis spaces sible on for hypothese How many distinct decision trees with n Bodlean attributes? E."tree for deciding whethertowa -number of Boolean functions Expressiveness Hypothesis spaces A es with2ow Prefer to find more compact decision tree Attribute-based representations Examples described by attribute values (Boolean, discrete, continuous, etc.) E.g., situations where I will/won’t wait for a table: Example Attributes Target Alt Bar Fri Hun Pat Price Rain Res Type Est WillWait X1 T F F T Some $$$ F T French 0–10 T X2 T F F T Full $ F F Thai 30–60 F X3 F T F F Some $ F F Burger 0–10 T X4 T F T T Full $ F F Thai 10–30 T X5 T F T F Full $$$ F T French >60 F X6 F T F T Some $$ T T Italian 0–10 T X7 F T F F None $ T F Burger 0–10 F X8 F F F T Some $$ T T Thai 0–10 T X9 F T T F Full $ T F Burger >60 F X10 T T T T Full $$$ F T Italian 10–30 F X11 F F F F None $ F F Thai 0–10 F X12 T T T T Full $ F F Burger 30–60 T Classification of examples is positive (T) or negative (F) Chapter 18, Sections 1–3 13 Decision trees One possible representation for hypotheses E.g., here is the “true” tree for deciding whether to wait: No Yes No Yes No Yes No Yes No Yes No Yes None Some Full >60 30−60 10−30 0−10 No Yes Alternate? Hungry? Reservation? Bar? Raining? Alternate? Patrons? Fri/Sat? F T WaitEstimate? F T T T F T T F T F T Chapter 18, Sections 1–3 14 Expressiveness Decision trees can express any function of the input attributes. E.g., for Boolean functions, truth table row → path to leaf: T F A B F T B A B A xor B F F F F T T T F T T T F F F F T T T Trivially, there is a consistent decision tree for any training set w/ one path to leaf for each example (unless f nondeterministic in x) but it probably won’t generalize to new examples Prefer to find more compact decision trees Chapter 18, Sections 1–3 15 Hypothesis spaces How many distinct decision trees with n Boolean attributes?? Chapter 18, Sections 1–3 16 Hypothesis spaces How many distinct decision trees with n Boolean attributes?? = number of Boolean functions Chapter 18, Sections 1–3 17 Hypothesis spaces How many distinct decision trees with n Boolean attributes?? = number of Boolean functions = number of distinct truth tables with 2 n rows Chapter 18, Sections 1–3 18