W05 Supervised Learning

Question 1

Classification:

data basis

Answer 1

several independent attributes

one dependent attribute, the class

Question 2

Classification:

condition

Answer 2

a priori knowledge of classification for some instances (supervised learning!)

Question 3

Classification:

model building

Answer 3

generate rules from classified instances

first: generate best fit
then: prune based on validation set

Question 4

Classification:

generalization

Answer 4

apply rules to new instances

Question 5

Classification:

methods

Answer 5

logistic regression
naive bayes classifier
support vector machines
decision trees
random forest
neural networks
nearest neighbour

Question 6

Decision Tree Terminology:

Binary Tree

Answer 6

each node splits data at most in 2 sets

Question 7

Decision Tree Terminology:

Classification Tree

Answer 7

split can lead to >2 branches

Question 8

Decision Tree Terminology:

Decision Tree

Answer 8

Nominal (categorical) Classes

Question 9

Decision Tree Terminology:

Regression Tree

Answer 9

Cardinal Classes

Question 10

Decision Tree Terminology:

Input

Answer 10

Instance pool

Question 11

Decision Tree Terminology:

Output

Answer 11

Full Tree

Question 12

Decision Tree Terminology:

Objective

Answer 12

Formulate rules of type:

If condition 1-n, THEN condition n

Question 13

Decision Tree Terminology:

Rule

Answer 13

Path from root to leaf

Question 14

Generating a decision tree algorithm

Answer 14

1 all objects in single node
2 search for best classification criterion
3 classify all objects accordingly
4 recusively apply 2+3 until STOP
5 prune tree

Question 15

Classifcation algorithms variety

Answer 15

1 stop criteria
2 pruning strategy
3 choice of attributes as classification criterion
4 number of splits per node
5 scale of measurement

Question 16

(CH)AID

Answer 16

chi squared automatic interaction detection

->find significantly different subsets of data so select attributes to generate those

Question 17

CART

Answer 17

classification and regression trees

->maximize information content i so select attributes accordingly

Question 18

ID3

Answer 18

iterative dichotomizer 3

->minimize entropy so split on attribute producing that

Question 19

Entropy Formula

Answer 19

H(S) = - sum [pi*log2pi]

Question 20

Information Entropy formula

Answer 20

I(a) = sum[qi+H(S)]

Question 21

Decision Tree Pruning

Answer 21

simplify complicated decision trees to incease efficiency and avoid over-fitting

top-down pruning->stopping criteria when building trees

bottom-up-pruning
->ex post:
prune splits that not increase subset homogeneeity sufficiently
prune to undo over-fitting based on validation set: prune tree parts that not increase success quota

Question 22

Decision Tree Properties:

number of generated rules

Answer 22

number of leaves

Question 23

Decision Tree Properties

maximum rule length

Answer 23

depth of tree

Question 24

Decision Tree Properties

sum of all path lengths from root fo leaf

Answer 24

external path length;

determines memory requirements

Question 25

Decision Tree Properties

sum of path lengths from root to leaf multiplied by number of represented instances

Answer 25

weighted external length;

measures classification costs

Question 26

Decision Trees:
understandability?
relationships?
too complex rules?

Answer 26

• high understandability and interpretability
• non-linear relationships
• pruning important

Question 27

Random Forest

Answer 27

-several randomised instances of model - use aggreagated results for clasification

1 generate k trees by drawing with replacement k times
2 generalize by classifying with k trees and choose most frequently determined class

Question 28

Gradient Boosted Trees

Answer 28

1 initialize a prediction model with constant vlaue
2 compute pseudo-residuals
3 extend model by creating a regression tree to predict pseudo residuals
4 apply and repeat 2 for M iterations

Question 29

Support Vector Machines

Answer 29

built a linear discriminant function to separate two classes as widely as possible

critical boundary instances are termed support vectors

Question 30

Neural Networks

Answer 30

imitate concepts of brain

connect several simple models in hierarchical strucure

simple models are perceptrons, massively interconnected, decomposing problems and forwarding them

backpropagation -> modify weights based on contribution to accurate solution