CSCI 343 Quiz 2

Question 1

K-nearest neighbor (KNN) is a ? learner

Answer 1

lazy

Question 2

a lazy learner has no…

Answer 2

no training, no model

Question 3

in a typical machine learning algorithm, ? takes more time; in a KNN algorithm, ? takes more time

Answer 3

typical: training takes time
KNN: testing/prediction takes time

Question 4

KNN uses a

Answer 4

similarity measure

Question 5

the parameter k for KNN is usually

Answer 5

odd & small

Question 6

K-nearest neighbor works by

Answer 6

finding the k closest samples, using majority rules to pick the label; can also use weighted average

Question 7

the parameter k for KNN is defaulted to be

Answer 7

5

Question 8

Naive Bayes Classification can be used for (examples)

Answer 8

spam classification, medical diagnosis, weather

Question 9

Naive Bayes: given ? predict ?

Answer 9

given features x1, x2, …, xn, predict label Y

Question 10

conditional probability

Answer 10

the probability that the event B will occur, given event A has already occurred; P(B|A)

Question 11

if A and B are independent, the conditional probability of B given A is

Answer 11

P(B)

Question 12

if A and B are NOT independent, the probability of both events occurring is

Answer 12

P(A,B) = P(A) * P(B|A)

Question 13

the conditional probability of B given A (NOT independent) is

Answer 13

P(B|A) = P(A,B) / P(A)

Question 14

Bayes Rule written out

Answer 14

P(Y | X1, …, Xn) = [P(X1, …, Xn | Y) * P(Y)] / P(X1, …, Xn)

Question 15

Bayes Rule in simpler terms

Answer 15

(likelihood * prior) / normalization constant

Question 16

likelihood in Bayes Rule

Answer 16

the probability of everything given that it’s Y

Question 17

prior in Bayes Rule

Answer 17

assume uniform distribution P(Y)

Question 18

how many parameters are required to specify the prior for the digit recognition example?

Answer 18

one – Y (so what number it is)

Question 19

how many parameters are required to specify the likelihood for the digit recognition example?

Answer 19

2(2^900 - 1) because for each Y, all X’s could either exist or not exist (0 or 1) for all 900 pixels

Question 20

the problem with explicitly modeling P(X1,…,Xn | Y) is

Answer 20

there are usually too many parameters (we’ll run out of space, time, and need tons of training data)

Question 21

Naive Bayes Assumption

Answer 21

assume that all features are independent given the class label Y

Question 22

Naive Bayes Model equation

Answer 22

P(X1,…,Xn | Y) = the product from i to n of P(Xi | Y)

Question 23

How to use the Naive Bayes Model:

Answer 23

assume independence and use whichever likelihood is equal to the product of the probabilities

Question 24

Why is the Naive Bayes Model useful?

Answer 24

changes the number of parameters from exponential to linear

Question 25

How to train in Naive Bayes

Answer 25

estimate the prior P(Y=v) as the fraction of records with Y=v & estimate P(Xi=u | Y=v) as the fraction of records with Y=v for which Xi=u

Question 26

In practice, some counts can be zero. Fix this by adding "virtual" counts. This is called

Answer 26

smoothing

Question 27

What's nice about Naive Bayes is that it returns probabilities, which tell us ?

Answer 27

how confident the algorithm is

Question 28

Naive Bayes assumption

Answer 28

all features are independent given the class label Y

Question 29

does the Naive Bayes assumption hold for the digit recognition problem?

Answer 29

no because if a pixel is black, the ones next to it are more likely to be black as well

Question 30

an example where conditional independence fails is

Answer 30

XOR (exclusive or -- either X1 or X2 but NOT both)

Question 31

the Naive Bayes assumption is almost (never/always) true

Answer 31

never (but it still performs well)

Question 32

numeric underflow

Answer 32

ML works with very small numbers, but computing the probability of 2000 independent coin flips (.5)^2000 would be output as zero

Question 33

to fix numeric underflow, instead of comparing P(Y=5 | X1, ..., Xn) with P(Y=6 | X1, ..., Xn), compare their ?

Answer 33

logarithms

Question 34

it is better to ? of probabilities rather than multiplying probabilities

Answer 34

sum logs

Question 35

log(xy) =

Answer 35

log(x) + log(y)

Question 36

can there be more than one decision tree that fits the same data?

Answer 36

yes

Question 37

decision tree classification process

Answer 37

training set -> induction (tree induction algorithm) -> learn model -> model (decision tree) -> apply model -> deduction -> test set

Question 38

how to apply decision tree model to test data

Answer 38

start from the root of the tree and move according to the splitting attributes

Question 39

Hunt's Algorithm

Answer 39

``` Dt = set of training records that reach a node t if Dt contains records that all belong to the same class, create a leaf node for that class if Dt is an empty set, then create a leaf node for the default class if Dt contains records that belong to more than one class, use an attribute test to split the data into smaller subsets recurse ```

Question 40

greedy strategy for tree induction

Answer 40

split the records based on an attribute test that optimizes certain criterion

Question 41

issues with tree induction

Answer 41

how to split records and how to know when to stop splitting

Question 42

multi-way split

Answer 42

use as many partitions as distinct values | ex: CarType -> Family, Sports, Luxury

Question 43

binary split

Answer 43

divide values into two subsets; need to find optimal partitioning ex: CarType -> {Sports, Luxury} and {Family}

Question 44

discretization forms

Answer 44

an ordinal categorical attribute

Question 45

static discretization

Answer 45

discretize once at the beginning (ex: split at the median)

Question 46

dynamic discretization

Answer 46

ranges can be found by equal interval bucketing, equal frequency bucketing, or clustering

Question 47

equal interval bucketing

Answer 47

look at value of the object (ex: every 10 points, every $5000)

Question 48

equal frequency bucketing

Answer 48

take from percentiles so there's an equal number of records in each range (ex: each quartile)

Question 49

clustering

Answer 49

look for gaps (ex: give ones closest together the same grade)

Question 50

binary decision splitting

Answer 50

(A < v) or (A >= V) | consider all possible splits and finds the best cut; can be computationally expensive

Question 51

the best splits will result in

Answer 51

purer records (ex: Class 0 may have 1 but Class 1 has 7 -- want these numbers to be far apart and at least one to get as close to zero as possible)

Question 52

nodes with ? class distribution are preferred

Answer 52

homogeneous

Question 53

ex: Class 0 - 5, Class 1 - 5

Answer 53

non-homogeous, high degree of impurity

Question 54

ex: Class 0 - 9, Class 1 - 1

Answer 54

homogeneous, low degree of impurity

Question 55

measures of node impurity

Answer 55

Gini Index, Entropy, Misclassification Error

Question 56

GINI(t) =

Answer 56

1 - the sum of all the (p sub j given t)^2

Question 57

you want to (minimize/maximize) the GINI

Answer 57

minimize

Question 58

GINI's range is

Answer 58

0-0.5

Question 59

GINI example: C1 - 2 C2 - 4

Answer 59

``` P(C1) = 2/6, P(C2) = 4/6 GINI = 1 - (2/6)^2 - (4/6)^2 = 0.444 ```

Question 60

GINI index for binary attributes

Answer 60

GINI for Node1 * proportion of records that come down that way + GINI for Node2 * proportion of records that come down that way

Question 61

for efficient computation on where to split, for each attribute, ...

Answer 61

sort the attribute on values, linearly scan these values, each time updating the count matrix and computing the Gini index, **choose the split position that has the smallest Gini index**

Question 62

Entropy based computations are similar to the ?

Answer 62

GINI index computations

Question 63

Entropy's range is

Answer 63

0-1

Question 64

want to (minimize/maximize) entropy

Answer 64

minimize

Question 65

want to (minimize/maximize) GAIN

Answer 65

maximize

Question 66

GAIN of a split is a function of entropy; to maximize it, we

Answer 66

choose the split that achieves the most reduction

Question 67

classification error at a node t Error(t) =

Answer 67

1 - max P(i | t)

Question 68

want to (minimize/maximize) Error

Answer 68

minimize

Question 69

when to stop splitting

Answer 69

when all records belong to the same class, when all the records have similar attribute values (maybe at least 90% in same class), early termination based on "level" or number of records narrowed down

Question 70

advantages of decision tree based classification

Answer 70

inexpensive to construct, extremely fast classification, easy to interpret small trees, accuracy is comparable to other techniques for similar data sets