Machine Learning Midterm

Question 1

What is True Error?

Answer 1

The error between the hypothesis and the target concept regarding a distribution. The hypothesis and target concept may disagree on some instances in the distribution

Question 2

PAC Learning - Learner definition

Answer 2

Our learner is what outputs an approximately correct hypothesis.
Is a consistent learner if outputs hypotheses that perfectly fit the training data.

Question 3

PAC - Probably definition

Answer 3

Our Learner will probably (i.e., probability) produce an approximately correct learner

Question 4

PAC - Approximately Correct definition

Answer 4

Error on the distribution with a small epsilon (i.e., noise/distribution/etc.)

Question 5

PAC - Hypotheses parameter

Answer 5

If the number of hypotheses is finite we can bound the number of training examples needed for the concept to be PAC learnable by our Learner

Question 6

What is Version Space?

Answer 6

Set of hypotheses in H that perfectly fit the training data.

Question 7

How is a Version Space Epsilon Exhausted?

Answer 7

If every hypothesis in the Version Space has true error less than epslion for a set of training examples

Question 8

What is PAC Learning?

Answer 8

The probability (1 - parameter1) the version space is epsilon exhausted (i.e., a consistent learner will produce a hypothesis with error on the distribution less than equal to epsilon on the training set)
Gives us the minimum training samples needed to PAC-learn  a concept.

Question 9

What is a VC Dimension?

Answer 9

For a given instance space X and hypothesis space H, it is the largest subset of X that can be shattered by H

Question 10

What is Shattering?

Answer 10

A set of instances S from X is shattered by H if and only if for every possible dichotomy of S, there exists a hypothesis h from H that is consistent with the dichotomy.
S is shattered by H if there are enough hypotheses in H to agree with every possible labeling of S

Question 11

VC Dimension and PAC Learning relationship

Answer 11

If VC(H) is finite, then we can bound the number of training examples needed for epsilon exhaustion the version space of H.
A concept class is only PAC learnable if and only if VC(H) is finite

Question 12

What does Bayes’ Rule help with?

Answer 12

Integrate prior information with our data to come up with new information that we can use to confirm our suspicions

Question 13

What is Posterior Probability?

Answer 13

The conditional probability that is assigned to a hypothesis after relevant evidence is taken into account

Question 14

What is the Bayes Rule formula?

Answer 14

P(h|D) = P(D|h) * P(h) / P(D)

h represents a hypothesis

Question 15

What is Bayes Rule?

Answer 15

We find the maximum probability hypothesis given the data across all hypotheses (i.e., Maximum a Posteriori)

Question 16

What is the Maximum Likliehood?

Answer 16

Comes from our assumption that all P(h)’s are equivalent, so wan can compute this for a hypothesis

Question 17

What is Occam’s Razor?

Answer 17

States that among competing hypotheses, the one with the fewest assumptions should be selected

Question 18

How do we go with finding the shortest hypothesis?

Answer 18

Find the Minimal Description Length

Question 19

How to find the most probable hypothesis?

Answer 19

Use MAP

Question 20

How to find the most probable classifier?

Answer 20

Average all the hypotheses of their probable answers

Question 21

What is a con for Bayes Optimal Classifier?

Answer 21

It takes a long time to compute because the posterior needs to be computed for every hypothesis

Question 22

Why Naive Bayes classifier?

Answer 22

It is computationally efficent that Bayesian Optimal Classifier

Question 23

What is a Belief Network?

Answer 23

A graph with nodes and edges that show the probability distribution of a set of variables in terms of their conditional dependencies

Question 24

How to compute Joint Probabilities?

Answer 24

Can compute them from the Belief Network by using all the probabilities of the parents of a Node and each Node

Question 25

How does a Naive Bayes Classifier work?

Answer 25

What to find the most probable target value of the classification variable from the average of all the attribute childs.

Question 26

What is the benefit of Naive Bayes

Answer 26

Computation advantage. Small number of terms that must be estimated (i.e., number of attributes multiplied by the number of distance classification values)

Question 27

What is a problem with Joint Probability

Answer 27

Suffers from Cusre of Dimensionality

Question 28

What is a con of Naive Bayes?

Answer 28

Assumption of strong conditional independence. Can’t predict XOR