Beslutningstre

Beslutningstre (engelsk: decision tree) er innenfor kunstig intelligens en av de enklere læringsalgoritmene. Det brukes ofte innenfor induktiv læring, som er prosessen for å lære ved hjelp av eksempler og er svært enkel å implementere. Dette blir brukt når et system skal opprette regler for å tolke det som er observert. Beslutningtre er hardfør ovenfor «støyende data» (eng.: «noisy data»), det vil si informasjon som ikke kan tolkes direkte av en datamaskin (slik som tekstdokumenter og mediefiler). For at systemet skal kunne lære, bruker det beslutningstreet for å tolke informasjonen ved å utføre tester på hvert «trinn» og opprette nye grener på treet for å komme frem til et resultat.

Ytelseskriterier

Et beslutningstre tar imot objekter eller situasjoner som beskrives av et sett av egenskaper (også kalt attributter), og skal si noe om hvordan tilstanden er (for eksempel har vær attributter som sol, regn og overskyet). Ved å returnere en handling basert på regler blir det opprettet nye noder, output og input. Disse kan enten være diskrete (se diskret matematikk) som i et tastetrykk, eller kontinuerlige, det vil si data i forandring. Det finnes flere metoder for å lære diskrete funksjoner, disse kalles for classification learning og for å finne kontinuerlige data som er regresjon.

Et beslutningstre finner løsninger ved å utføre en rekke tester. Hver interne node i treet tilhører en slik test, hvor egenskapen av foregående verdi står som resultat. Ut fra denne noden (se: Grafteori) vil alle kantene bestå av mulige verdier av testen. I logikk kan man for eksempel finne et målpredikat (eng.: goal predicate ) som kan være VilVentePå i et domene med navn bussen. I denne modellen skal predikatet finne frem til egenskapene i dette domenet.

NR	Node	Tekst
1	Alternativ transport (AT)	Finnes alternativ transport, buss-taxi-tog, ja eller nei?
2	Neste avgang	Hvor lang tid til neste avgang, kort eller lang?
3	Temperatur	Hva er temperaturen der du står, kaldt eller ok?
4	Økonomi	Penger, lite eller nok til AT?
5	Avstand	Hvor langt skal du, innenfor rimelig gå avstand, ja eller nei?
6	Transport	Går det buss her?

Ved hjelp av et enkelt beslutningstre kan man finne ut om vi vil vente på bussen eller ikke.

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))

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²) ∧ Pris(r, p) ∧ Pris(r², p²) ∧ 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 sannhetstabellen 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å.

Induktiv beslutning ved hjelp av eksempler

I et eksempelkan en vektorisert variabel x gi informasjon om hvert attributt og danne grunnlag for videre iterasjon av treet. Et slikt eksempelsett kalles gjerne for «treningssett», og ved hjelp av verdiene kan man finne neste node i iterasjonen.

Eksempel nr.	Attributter						Goal
	Transport	Neste avgang	Temperatur	Økonomi	Avstand	AT	VilVentePÅ
X1	YES	< 10	Kaldt	OK	Langt	NO	YES
X2	YES	< 10	Kaldt	OK	Kort	NO	NO
X3	YES	10-30	Komfortabelt	0	Langt	YES	NO
X4	NO	0	Kaldt	OK	Kort	YES	NO
X5	YES	> 60	Varmt	OK	Medium	YES	YES

For å finne neste node i treet kan man bruke entropi, en metode for å finne noe som er målbart gitt en usikkerhet i en tilfeldig variabel. Gitt et datasett S, som inneholder både positive (TRUE/YES) og negative (FALSE/NO) verdier, blir entropien relativ til settet:

Entropi(S) = - p(positive) log² p(positive) - p(negative) log² p(negative)

hvor p er proporsjonen til positive og negative eksempler i settet delt på det totale antall av eksempler.

I entropikalkylen, hvor 0 log 0, er p alltid 0. Entropien for eksempel S blir:

Entropi([2+, 3-]) = -(2/5) log²(2/5) - (3/5) log²(3/5) = 0.970

(Dette kan også vises slik: -(2/5)*log(2/5,2)-(3/5)*log(3/5,2))

Entropien gir altså muligheten for å måle tributtens effektivitet, slik at man kan sammenligne de forskjellige attributter og velge den høyeste verdien som grunnlag for neste node.

Kilder

• Prenhall,com

Litteratur

• Stuart Russel og Peter Norvig (2003). Artificial Intelligence – a modern approach. Pearson Education. ISBN 0-13-080302-2.