Supervised Learning
classification: true or false
regression
Credit history: lend money? -> classification: binary task
classification learning
– instances (input)
– concept function -> T,F
– target concept -> actual answer
– hypothesis -> class, all functions
– sample (training set)
– candidate: concept = target concept
– testing set
Decision Tree
entry: type italian, french, thai
atmosphere: fancy, hiw, casual
occupied
hot date?
cost, hungry, raining
node -> values -> attribute
representation vs algorithm
Decision Trees: Learning
1. Pick best attribute
Best ~ splits the data
2. Asked question
3. Follow the answer path
4. Go to 1
on til got an answer
Decision trees: Expressioness
Boolean
A and B, A or B, A xor B
n-or:any, n-xor:parity(odo)
XOR is hard, n attributes(boolean) o(n!), how many trees?, output is boolean
Truth table
a1, a2, a3, …△n, output
y, t, t … t
t, t, t … t
