Machine Learning

Question 1

Inductive learning

Answer 1

generalize from a given set of (training) examples so that accurate predictions can be made about future examples; learn an unknown function

Question 2

how to represent a “thing” in machine learning

Answer 2

x: example or instance of a specific object; represented by a feature vector; each dimension - feature

Question 3

feature vector representation

Answer 3

extract a feature vector x, that describes all attribute relevant for an object; each x is a list of (attribute, value) pairs

Question 4

types of features

Answer 4

numerical features - discrete or continuous
categorical features - no intrinsic ordering
ordinal features - similar to categorical but clear ordering

Question 5

point in feature vector representation

Answer 5

each example can be interpreted as a point in a D-dimensional feature space, where D is the number of features/attributes

Question 6

Training set

Answer 6

A training set is a collection of examples (instances), which is the input to the learning process; assume instances are independent and identically distributed. training set = experience given to learning algorithm

Question 7

idd

Answer 7

independent and identically distributed

Question 8

Unsupervised learning

Answer 8

training set = x1, …xn; no “teacher” to show how examples should be handled; tasks: clustering, discovery, novelty detection; dimensionality reduction

Question 9

goal of clustering

Answer 9

group training samples into clusters such that examples in the same cluster are similar, and examples in different clusters are different

Question 10

Clustering methods

Answer 10

Hierarchical Agglomerative Clustering
K-means Clustering
Mean Shift Clustering

Question 11

Hierachical Clustering General Idea

Answer 11

initially every point is in its own cluster
find the pair of clusters that are the closest
merge the two into a single cluster
repeat
end result: binary tree

Question 12

How to measure closeness between 2 clusters (hierarchical clustering)

Answer 12

Single linkage, complete-linkage, average linkage

Question 13

single-linkage

Answer 13

the shortest distance from any member of 1 cluster to any member of another cluster

Question 14

complete linkage

Answer 14

the largest distance from any member of 1 cluster to any member of another cluster

Question 15

average linkage

Answer 15

the average distance between all pairs of members, one from each cluster

Question 16

How to measure the distance between a pair of examples?

Answer 16

Euclidean, manhattan/city block, hamming

Question 17

Dendrogram

Answer 17

binary tree resulting from hierarchical clustering; the tree can be cut at any level to produce different numbers of clusters

Question 18

What factors affect the outcome of hierarchical clustering?

Answer 18

features used, range of values for each feature, linkage method, distance metric used, weight of each feature

Question 19

K-Means Clustering

Answer 19

Specify the desired number of clusters and use an iterative algorithm to find them

Question 20

K-means clustering general idea

Answer 20

if have cluster centers, for each point, choose closest center, if have points, choose a cluster center to be the mean/centroid of the points in the cluster; repeat until convergence

Question 21

K-means algorithm

Answer 21

input: x…xn
select k cluster centers c1, …ck
fore each point x, determine it’s cluster by finding closest cluster center; update cluster centers as centroid (mean)

Question 22

Distortion

Answer 22

Sum of squared distances of each data point to its cluster center; optimal clustering minimizes distortion (over all possible possible cluster locations/assignments)

Question 23

How to pick k in k-means clustering

Answer 23

pick number of k to minimize distortion - pick one close to elbow of the distortion curve

Question 24

Does K-means always terminate?

Answer 24

Yes (finite number of ways of partioning a finite number of points into k groups)

Question 25

Is K-means guarunteed to find “optimal clustering”?

Answer 25

No, but each iteration will reduce the error/distortion of the clustering

Question 26

Which local optimum k-means goes to is determined by:

Answer 26

solely by the starting cluster centers

Question 27

Ways to pick good starting cluster centers

Answer 27

1. run multiple times with different starting random cluster centers
2. pick starting points based on farthest apart from each other

Question 28

How to pick number of clusters

Answer 28

difficult problem, heuristics depend on number of points/dimensions

Question 29

mean shift clustering

Answer 29

choose search window size and initial location; compute centroid; center search window at mean; repeat

Question 30

mean shift clustering objective:

Answer 30

find the densest region

Question 31

Supervised learning

Answer 31

learns a function H: x->y in some function family H, such that h(x) predictions the true label y on future data (classification if discrete, regression if continuous)

Question 32

what is a label (supervised learning)?

Answer 32

the desired prediction on an instance x

Question 33

what is a class?

Answer 33

discrete label

Question 34

concept learning

Answer 34

determine from a given set of examples if a given example is or is not an instance of the concept/class/category

Question 35

positive/negative example (concept learning)

Answer 35

if an example is or isn’t an instance of concept/class/category

Question 36

Supervised Concept Learning by Induction

Answer 36

Given a training set of positive and negative examples of a concept, construct a description that accurately classifies whether future examples are positive or negative

Question 37

Nearest Neighbor Classification

Answer 37

Save each training example in feature space; classify a new example by giving it the same classification as its nearest neighbor

Question 38

How to pick k for nearest neighbor?

Answer 38

split data into training/tuning sets
classify turning set with different k values
pick k that produces least turning-set error

Question 39

When doesn’t k-NN generalize well?

Answer 39

If the examples in each class are not well clustered

Question 40

How is distribution from training set important?

Answer 40

If train on set from different distribution from future data, will not be as accurate

Question 41

Inductive bias

Answer 41

Any knowledge created by generalization from specific facts cannot be proven true, only false; used when one function is chosen over another

Question 42

Inductive biases commonly used in ML?

Answer 42

restricted hypothesis space bias

preference bias

Question 43

Restricted hypothesis space bias

Answer 43

allow only certain types of h’s, not aribitrary ones

Question 44

preference bias

Answer 44

define a metric for comparing h’s so as to determine whether one is better than another