Redigerer Beslutningstre (avsnitt)

=== Ekspressivitet av beslutningstre ===
Bortimot alle hypoteser for ''VilVentePå'' kan bruke et beslutningstre form tilsvarende denne:

'''∀(s) VilVentePå(s) ⇔ (P¹(s) V (p²(s) V...V Pⁿ(s))<br />'''

hvor hver tilstand Pi(s) er sammensatt av tester som tilsvarer stien fra treets root til en kant (og neste node) med et positivt resultat. Et beslutningstre beskriver relasjonen mellom ''VilVentePå'' og noen logiske kombinasjoner av egenskapenes verdier.

Derimot kan man ikke bruke et beslutningstre for å representere tester som viser til to eller flere forskjellige objekter, for eksempel hvor '''r''' representerer "restaurant":

'''∃ r ∃ r²  Nærheten(r, r²) <big>∧</big> Pris(r, p) <big>∧</big> Pris(r², p²) <big>∧</big> Billigere (p, p²)'''

(Finnes det er restaurant i nærheten som er billigere?)

Ved bruk at boolske uttrykk og egenskaper kan man addere bruk av flere objekter, men dette vil være nærmest uløselig med tanke på alle egenskapene som må legges til.

Enhver [[boolsk variabel]] eller funksjon kan skrives i en beslutningstre-algoritme og er trivielt med at hver rad i en [[sannhetstabell]] tilsvarer funksjonens sti i treet (rot til node til kant til node osv.). Dette vil imidlertid føre til en eksponentielt lang tre representasjon, fordi [[sannhetstabell]]en vil ha eksponentielt mange rader, eksempel som ved bruk av en algoritme slik som [[ID3]] og hvor rot noden representerer et dato felt, vil et [[bredde-først-søk]] føre til mange rader på første nivå.