MidtermExam Flashcards
1
Q
What is the definition of ML that Dr. Isbell prefers?
A
ML is about using math, computation, engineering (among other things) to build computational artifacts that learn over time.
2
Q
What is inductive reasoning?
A
Reasoning that goes from specifics –> generalities
3
Q
What is deductive reasoning?
A
Applying general rules to draw specific (logical) conclusions
4
Q
At a high-level, what is supervised learning considered an example of?
A
Function approximation. It’s the process of inductively learning a general rule from observations.
5
Q
What is unsupervised learning all about?
A
It’s about DESCRIBING data. In UML, we’re only given “inputs”, so the objective is to learn if there is some latent structure in the data that we can use to describe the data in a more efficient (i.e. more concise) way. Clustering is a common time of unsupervised ML.
6
Q
What are two types of supervised machine learning?
A
- Classification (Discrete output values)
- Regression (Continuous output values)
7
Q
In a Decision Tree (DT) model, nodes are _______ and edges are _____?
A
Attributes, Values
8
Q
What is the decision tree algorithm?
A
- Pick the best attribute (where best splits the data roughly in half)
- Ask the question
- Follow the answer path
- Go to 1. (until arrive at answer)
9
Q
What is the complexity of XOR?
A
O(2^n) [i.e. exponential, NP-Hard]
10
Q
What is the complexity of OR?
A
O(n) [i.e. linear]
11
Q
What are the two types of biases we worry about when searching through a hypothesis space?
A
- Restriction bias: This is how restrictive the function space is we’ve chosen. So given that there are an infinite number of ways of representing a function, the restriction bias of a decision tree algorithm limits it to the space of boolean functions.
- Preference bias: This tells us what hypotheses within the space that we prefer. THIS IS AT THE HEART OF INDUCTIVE BIAS. (Because we have a preference for hypotheses that fit the data well.)
12
Q
What are some of the inductive biases of the ID3 algorithm for decision trees?
A
- Preference for good splits at the top of the tree as opposed to the bottom of the tree (because we build from the top of the tree down)
- Prefers models that fit the data well (i.e. prefers correct over incorrect)
- Tends to prefer shorter trees over taller trees (this is just a natural corollary that stems from the fact that we prefer trees that perform better splits at the top)
13
Q
According to Mitchell, what three features must be present in order to have a well-posed learning problem?
A
- The class of tasks
- The measure of performance to be improved
- The source of experience
14
Q
Historically, how did we end up with the term “regression”?
A
The idea of regression to the mean, e.g. the heights of a taller/shorter than average person have children that tend to ‘regress’ back to the mean.
15
Q
What are some examples of where error comes from?
A
- Sensor Error
- Malicious/adversarial data
- Transcription error
- Un-modeled influences
16
Q
What is one of the fundamental assumptions that we make in most supervised learning algorithms?
A
That the data from the training set are REPRESENTATIVE of what we expect in the future. If this isn’t the case, then our model won’t GENERALIZE, which is what we really care about as ML practitioners. More formally, the general assumption is that data are I.I.D. (Independent, Identically Distributed); that is, that the process the generated the training data is the same process that is generating the test data (in fact, any future data!).
17
Q
In the context of regression, the best constant in terms of the squared error is the _____?
A
mean
18
Q
Describe cross-validation and why we use it?
A
We split the training data into k-folds. Then we use n-1 of the folds for training and use the final n fold as a validation set (i.e. a stand-in for the test set). We can do this for all the combinatorial sets of k-folds, and then average the validation error across all of them. The best model is then the one with the lowest average error.
We use cross validation to avoid overfitting the model. Since we should have no access to the test set when developing our model, using cross validation improves generalization.
19
Q
Logical AND is expressible as a perceptron unit? (True/False)
A
True
20
Q
Logical OR is not expressible as a perceptron unit? (True/False)
A
False
21
Q
Logical NOT is expressible as a perceptron unit? (True/False)
A
True
22
Q
Logical XOR is not expressible as a perceptron unit? (True/False)
A
False
23
Q
For perceptron network training, what is the difference between the “perceptron rule” and the “gradient descent” rule?
A
The perceptron rule uses thresholded output values while gradient descent uses the UNthresholded values.
24
Q
If the data are linearly separable, wile the perceptron rule find the hyperplane that separates them in a finite number of iterations?
A
Yes
25
Why can we not a priori know whether a dataset is linearly separable (at least in non-trivial cases)?
Because while the perceptron rule does have a convergence guarantee to find the hyperplane that separates the data if it is linearly separable in a finite number of iterations, we have no way of knowing what "finite" means. Maybe the error finally goes to zero, but maybe it doesn't. It's really just a halting problem.
26
The perceptron training rule is more robust against non-linearly separable data than gradient descent is? (True/False)
False.
27
The perceptron rule does not have the theoretical guarantee of finite convergence? (True/False)
False
28
What assumption is made for the theoretical guarantee of finite convergence for the perceptron rule?
That the data are linearly separable.
29
What convergence guarantee does gradient descent offer?
Convergence to a local optimum. This is in contrast to the perceptron rule which does offer the guarantee of convergence to the global optimum in finite time, but only in the case of linearly separable data. Gradient descent is more ROBUST to non-linearly separable data than the perceptron rule.
30
Since gradient descent is more robust than the perceptron rule, why not just use GD on the weight update for the perceptron rule also?
Because the perceptron rule uses the THRESHOLDED output values, and the thresholding operation isn't smooth (it has a discontinuity at the point of thresholding), hence it is not differentiable, which means we can't use the calculus required for GD.
31
What is the domain for the sigmoid function? How does the output behave at the limits?
The domain is from -infinity to +infinity. As the function goes to -infinity, the output goes to 0; conversely, as the input goes to +infinity, the output asymptotically approaches +1.
32
What is the derivative of the sigmoid function?
Let 'a' := the activation and S(a) := the sigmoid function. Then the derivative dS(a)/da = S(a)\*(1 - S(a))
33
What is backpropogation?
It's a computationally beneficial organization of the chain rule from calculus that allows us to calculate how the weights should move to minimize the error of the output from a neural network.
34
What are some of the more advanced methods that are sometimes beneficial to help mitigate the tendency for gradient descent to get stuck in local minima?
1. Momentum terms
2. Using-higher order derivatives (the analogy would be like adding an error "velocity/acceleration" term(s) to borrow from physical motion equations)
3. Randomized optimization
4. Penalty for "complexity", where complexity might be the result of two large of network STRUCTURES (in terms of breadth and/or depth) or weights that are excessively large (in the latter case of weights we typically refer to this complexity penalty as "regularization")
35
What is the 'Restriction Bias'
It relates to the representational power of a learner by limiting the set of hypotheses that we will consider as valid.
36
What is the hypothesis space of a single perceptron unit?
Half-spaces (i.e. a hyperplane that perfectly separates data [although only in the case where the data is linearly separable!])
37
What is the restriction bias of a simple network of threshold-like units?
Boolean functions
38
If we add a single fully connected hidden layer that includes sigmoided activation functions, what is the restriction bias of the network?
Continuous functions
39
If we stitch together two or more fully connected hidden layers that include smooth (i.e. differentiable) activation functions, what is the restriction bias of the network?
Arbitrary functions
40
A network with two hidden layers containing 50 neurons each can represent any arbitrary function? (True/False)
False. While a finite neural net with at least two hidden layers can theoretically model an arbitrary function, we don't necessarily (in fact in almost every case we don't) know how "big" a sufficiently big network is required to model the function of interest.
41
If the error on the validation set increases while the error on the training set continues to decrease, what situation has occurred?
We've OVERFIT the training data. The model is no longer capable of generalizing.
42
What is 'Preference Bias'?
When a given algorithm is making a selection between one representation or another, it's preference bias determines which one of those representations it is more likely to choose.
43
Say while training a NN, a single weight is growing exponentially, becoming much larger than all the other weights in the network. What situation is likely occurring?
We're likely overfitting the dataset. In the case where one weight is growing much larger than all the others, the model has probably honed in on a single feature of the data that is highly correlated with the outputs in the training dataset, but it is unlikely to generalize to new data.
44
What are some of the preference biases of a Neural Network?
Initialization of weights to small random values results in a preference for - ceteris paribus - models with lower complexity (i.e. if most of the weights can stay small and still model the problem sufficiently well, then the model is going to prefer this situation)
45
Which is preferable: a restriction bias or preference bias?
Preference bias. At least in that case, we can be assured that the hypothesis space contains our target function of interest.
46
Where does the inductive bias of the ID3 algorithm for decision trees come from?
It’s search strategy. (Which makes it prefer shorter trees over taller trees, and tends to place attributes with the highest information gain towards the top of the tree.
47
In terms of computational complexity, learning for linear regression is _______ and querying \_\_\_\_\_\_?
Expensive | Cheap
48
In terms of computational complexity, learning for K-NN is _______ and querying \_\_\_\_\_\_?
Cheap | Expensive
49
What is the computional complexity and (run time and space) for KNN vs linear regression?
See screenshot below.
50
What are some of the preference biases of the KNN algorithm?
1. Locality: nearer points are similar
2. Smoothness: expectation that averaging data points works (i.e. the underlying function generating the data is smooth)
3. Equality: all features matter equally
51
What is the "Curse of Dimensionality"?
As the number of features or dimensions grows, the amount of data we need to generalize accurately grows exponentially.
52
The curse of dimensionality only applies to the KNN algorithm? (True/False)
False. It's true for any ML algorithm that as the number of features grow, we need exponentially more data to cover the space in order to generalize.
53
What is the difference between 'eager' and 'lazy' learners? What are some examples of each?
A lazy learner puts off learning as long as possible; eager learners solve the problem as soon as it is posed, and saves the result as some sort of parametric function that can be used later to quickly evaluate new data.
KNN is an example of a lazy learner. Linear regression is an example of an eager learner.
54
KNN can only handle classification problems?
False, it can handle classification and regression. In the case of regression, it could (as one example) simply take the average of the points to get a continuous output.
55
How does locally weighted KNN work and what does it allow us to do?
Locally weighted KNN allows us to represent more complex non-linear functions. It does this by approximating data locally as piece-wise functions. By stacking up these local functions we can generate non-linear outputs.
56
How does ensemble learning work?
1. Take a subset of the data and create individual learners that learn a rule for that subset
2. Combine all the individual learners into an ensemble
57
What are the two important ideas in boosting?
1. Select data subsets based on their difficulty
2. Use a weighted mean instead of simple average
58
What is the definition of a "weak learner"?
It's a learner that, no matter what the distribution of data is that you pull from, outputs a prediction that is better than random chance.
59
Define 'Inductive Learning' (per the computational learning theory lecture)
It's the process of "Learning from Examples".
1. Probability of successful training (i.e. 1 - δ, where δ is the probability of failure)
2. Number of examples to train on (i.e. *m*)
3. Complexity of the hypothesis class *H*
4. Accuracy to which target concept is approximate (often denoted as ε)
5. Manner in which training examples presented (batch vs online)
6. Maner in which training examples selected
60
What are the two main ways that examples can be *presented* to a learning algorithm?
1. Batch: we get a set of training data, and it's handed over to the learner all at once to learn from
2. Online: The learner is presented with samples one at a time, predicts a label, and then gets feedback from the algorithm/oracle about whether that prediction was correct or not
61
Describe the relationship between *Learners* and *Teachers.* How do they interact with one another?
1. Learner asks questions of the teacher - so for example, the learner gets some data/observation x, the teacher provides a concept *c(x)* that explains that data
2. Teacher gives examples to help learner (i.e. Teacher chooses *x,* tells *c(x)* to Learner)
3. Fixed Distribution, i.e *x* is chosen from *D* by **nature** (Dr. Isbell notes that this is mostly what we've talked about up until this point)
4. Evil distribution - i.e. some sort of adversarial approach
62
Random thoughts to consider: in the lectures discussing computational learning theory, one of the quizzes asks for the game like '20 Questions', where we have *H* hypotheses containing the set of possible people and *X* questions we can ask, how many questions does the learner need to ask if the **learner chooses** ***x*** to figure out the correct *h*? Dr. Isbell says log2(*x*) because we can, on average, eliminate half the hypotheses for each question we ask. Makes sense from an information theoretic perspective. This is predicated on the assumption that we can ask "good" questions, but doesn't really say anything about what makes a question "good". What distinguishes good questions from bad questions?
A naive response would be that it's one that eliminates roughly half the answers. But that's tautological. It seems to me that domain knowledge is really implicit here. In the case where *H* is a set of people, we naturally have background knowledge of this that admits a lot of binary questions (at least from an information theoretic perspective, if not exactly politically correct): is the person male/female? Are they older than 40? Etc, etc. Not only that, we also have really strong priors we can derive from this background knowledge: we know that the world population is roughly 50/50 male/female. Human life expectancy gives us a good idea how to split intro roughly equal groups.
But what about the case were we're much less certain (or have no information at all) about what *H* contains? I guess since we're human, the most reasonable place to start would be asking questions based on prevalance of some attribute that *H* is most likely to contain? So questions like "Is *h* in the space of people?", etc. It's tough to swallow as things become more abstract though. What if *H* is the set of all atoms in the universe, and the answer we're looking for is something ridiculous like: "the 3rd atom in Saturn's ring". (Interesting note that the first example that jumped to my mind was Saturn: I've also just shown my own preference bias for hypotheses that are in the set of things in our solar system).
I don't know exactly where I'm going with this, and I guess it comes down to the problem of a potentiall infinite hypothesis space, which I'm sure will discuss in the lectures. Anyway, it's interesting stuff to think about.
63
Why do constrained queries make things so hard for learners?
Because we can only ask things that amount to data points, and not the thing we're actually interested in itself. So think about the case of bit strings and a hypothesis class that consists of conjunctions of literals or negations. What we'd really like to ask are things like: is *x1* in the formula? But the constraint forces us to only ask questions where x takes on binary values. This means it could take a huge amount of samples before we finally get a positive result; the negative results simply don't tell us much. This means in the worse case it could take us 2k queries to find the actual answer.
64
What is 'Version Space'?
Let *S* be a training set of data drawn from *X*. The version space is simply the set of all candidate hypotheses *h* such that h is consistent w.r.t. the data *S* that it has seen thus far. More succinctly, it's the **"set of hypotheses consistent with the examples"**
65
In the context of PAC learning, what are the two types of error?
Training error and True Error
66
What is training error?
It is the fraction of training examples misclassified by hypothesis *h*
67
What is the 'True Error'?
The fraction of examples that **would be** missclassified on a sample drawn from *D* in the infinitie limit
68
What does this formula represent:
The True Error, i.e. the fraction of examples that would be misclassified by some hypothesis h(x) compared to the true hypothesis (i.e. concept) c(x)
69
What is the definition of PAC Learning ("Probably Approximately Correct")?
Concept class *C* is learnable by learner *L* using hypothesis space *H* if and only if the learner will, with probability 1 - δ, output a hypothesis *h in H* such that the error(h) \<= ε in time and samples polynomial in 1/ε, 1/δ, and n (where n is the size of the hypothesis space).
70
Mathematically, what do the words "Probably Approximately Correct" represent?
Probably := 1 - δ [i.e. the certainty goal]
Approximately := ε [i.e. the error goal]
Correct := h(x)=c(x) [i.e. the chosen hypothesis is equal to the actual concept hypothesis]
71
At a high-level, describe what PAC Learning is?
Something is considered PAC learnable if the learner *L* can find a hypothesis that has low *true error* **and** can be learned in polynomial time as a function of 1/ε, 1/δ and *n (*the size of the hypothesis space).
72
Is the concept in the image below PAC learnable?
Yes. We just keep track of the version space (the hypotheses that are consistent with the data) and then - since we don't have any additional information to suggest otherwise - we should simply pick uniformly from that version space.
---------------------
My original guess on the answer (it's wrong per the lectures)
I'm going to go with 'No'. So first let's remember what it means for something to be PAC learnable: it means the learner has to be able to find to a hypothesis *h* in *H* that has a low, bounded true error and that can be learned in polynomial time as a function of the error rate, certainty goal and hypothesis space size.
Well first off, we can see right away that our hypothesis space is going to go as a function of *k*. But that's constant, we at least tick that box. The error bounds seem more of an issue to me. Think about the case where we increased the length of k for each new sample
0
01
010
1000
73
What is ε-exhaustion of a Version Space (VS)?
A Version Space is epsilon exhausted in the case when every hypothesis you might possibly choose in the VS has an error less than ε. In that case we can return _any_ of the hypotheses in the VS by choosing uniformly because we have no prior information that compells us to choose one over the other, and they all provide the same error guarantees! [**Note: This is mentioned as a key concept!]**
74
If we know the size of our hypothesis space and desire to find a hypothesis that's bounded by some error goal ε and certainty goal δ, then the number of samples required to achieve that is polynomial? (True/False)
True. This comes from the Haussler Theorem (see screenshot)
75
One way to think of why the distribution need not be uniform for the number of samples needed for something to be PAC learnable is that the distribution in some sense sort of cancels out between the training and true error? (True/False)
True. See the second to last video in the computational learning theory lectures for a really good example of this.
76
What is the 'agnostic' situation in the context of PAC learnability?
It occurs when the target concept is **not** in our hypothesis space. In that case, the learner doesn't match the true concept, but just chooses the best one. The error bounds change a bit, but are more or less the same, and the learning sample complexity is still polynomial in all of the terms we've been discussing previously (size of the hypothesis space, error goal, failure rate)
77
Which one of these hypothesis spaces are infinite?
[yes] Linear separators - As an example, think of an SVM using a linear kernel to create a hyperplane between two classes. Could you rotate it 0.0000000001 degrees one direction or the other and still split the classes? There's a good chance.
[yes] Artificial Neural Networks - think about GPT3 with its billions of parameters. Each one of those parameters is some floating point number that could take on any real valued number. Definitely an infinite space.
[no] Decision Trees (discrete inputs) - there are only so many ways we can split discrete data, so the hypothesis space for discrete inputs is not infinite.
[yes] Decision Trees (continuous inputs) - a continuous input could be split at any arbitrary point along the number line and at infinite precision, so definitely hypothesis space is infinite.
78
Is the version space for a KNN classifier finite or infinite?
Trick question, and it really depends on your definition. Dr. Littman argues that it's finite because if your dataset is fixed, then there's only one configuration. But if the data is not fixed, then each new dataset yields a different hypothesis, so you could argue it is infinite. It all comes down to the fact that KNN is a non-parametric model; the data is what matters for a KNN.
79
What is the difference between a 'syntactic' and 'semantic' hypothesis space?
A syntactic space is one that consists of everything we could possible say. A semantic space just considers the space that is *meaningfully different*. Intuitively, think about a set of characters like {'h', 'e', 'r'}. The syntactic space might consist of all the 3 letter strings you could form, but the semantic space would only care about things that have meaning in some sense (perhaps actual words like 'her', etc).
80
What is the "Power of a hypothesis space"?
It is the larget set of inputs that the hypothesis class can label in all possible ways. Said another way, it is the larget set of inputs that the hypothesis class can ***shatter.*** It gives us an idea of how expressive a certain hypothesis class is.
81
What does VC stand for in the context of VC Dimensions?
Vapnik-Chervonenkis
82
What is shattering?
It's the largest input size that a hypothesis can label in all possible ways.
83
What is the VC dimension?
It is the larget set of inputs that a hypothesis class can shatter.
84
What does the VC dimension allow us to do?
Basically it allows us to obtain a bound on the amount of data needed to learn for some hypothesis class, *even if the hypothesis space is infinite.* It does this using the notion of *shattering* (i.e. the larget set of inputs that the hypothesis class can label in all possible ways)
85
A linear separator cannot model the XOR function? (True/False)
True.
86
The VC dimension is often the same as the number of parameters? (True/False)
True (See the example for d-dimensional linear separators)
87
What is the connection between the sample complexity and VC dimension?
88
If something is PAC learnable, then its VC dimension is finite? (True/False)
True
89
If something is of finite VC dimension, then it is PAC learnable? (True/False)
True.
90
VC dimension is related to the number of "true" hypothesis space parameters? (True/False)
True. See the example in the lectures about repeating a feature in a decision tree. When you do that though, you're not actually changing what the hypothesis can represent, so the VC dimension stays the same in that case.
91
What is a 'concept'?
It's a function or mapping between an object and an items membership in a set. Example: mapping pixels in an image to whether it's an image of a dog or cat.
92
What is the 'target concept'?
It's the concept (i.e. function or mapping) that we actually want to find (i.e. mapping from pixels in an image to whether that image contains a car or not)
93
What is a 'hypothesis' as defined in the lectures?
It's the *set of functions that we're willing to entertain as containing the target concept we're interested in.* (note that it could be ALL functions!)
94
What is a 'sample' as defined in the lectures?
It's just the training set of instances containing data and it's associated label or value.
95
What is a 'candidate hypothesis' as defined in the lectures?
It's the posing of the question: ?= target concept.
96
If we use a decision tree to represent n-or statements, how does the tree grow as a function of n?
It's linear in n.
97
If we use a decision tree to represent n-xor statements, how does the tree grow as a function of n? (Assume odd parity)
It's exponential in in, i.e. O(2^n)
98
How big is the search space for a decision tree as a function of the number of attributes n? (*exclusive* of the outputs)
2^n. See the truth table below.
99
How big is the search space for a decision tree as a function of the number of attributes n? (*inclusive* of the outputs)
2^(2^n)
100
Why are decision trees so expressive?
Because the hypothesis space grows according to 2^(2^n), where n is the number of attributes (this is assuming binary attributes)
101
Does it ever make sense to repeat an attribute along a path in a decision tree for *discrete valued attributes*? (by same path meaning along the same branch)
My intuitition says **False** (this is also the answer they give in the lectures). My reasoning is that if we're splitting based on maximally entropic methods, then once we've split along that attribute, all the information it contains has been extracted; that information could never "reappear", so it doesn't make sense to ever repeat the attribute. See lecture videos for additional explanation.
102
Does it ever make sense to repeat an attribute along a path in a decision tree *for continuous valued attributes*? (by same path meaning along the same branch)
Yes, it makes sense, as long as the question isn't exactly repeated. Think about an attribute that looks at whether a person's age is between 20 and 30. There wouldn't be any reason to repeat that exact question later in the tree (for the same information theoretic reasons as in the discrete valued case), but it's *perfectly reasonable to ask a related but different question*, like "is the person younger than 13?"
103
What are some of the stopping criteria we could use for the decision tree algorithm?
1. Everything is classified correctly (probably not a likely thing to happen in real-world cases)
2. No more attributes remaining (this works in the case of discrete valued trees, but not in the case of continuous variables since we could essentially ask an infinite number of questions)
3. No overfitting (having a tree that is too big), e.g. expand the tree until we meet some threshold of perfomance on my cross-validation set,
4. Pruning - overfit the tree then prune until we reach some balance between complexity and performance.
104
For linear regression, the best constant in terms of squared error is the \_\_\_\_\_?
mean (the lecture videos prove this using simple calculus)
105
What is a perceptron?
A computational unit that "activates" if the input signal *x* multiplied by some arbitrary weights *w* is above some threshold θ, i.e. it's some linear function of the inputs thresholded by some value
106
Let's say your using a simple network of perceptrons to build a binary classifer. When training the model, after several iterations you find your weights are no longer changing. What could we conclude about the dataset?
The data must be *linearly separable*. The perceptron rule is *guaranteed to converge in finite time* to the correct rule in the event that the data are in fact linearly separable.
107
In an ANN, _______ weight values increase the model \_\_\_\_\_\_\_\_\_\_? What is one of combatting this?
larger, complexity. We can use regularization techniques to try to minimize this problem.
108
What is the 'maximum likelihood' hypothesis?
See screenshot. It's the *product* of all the individual probabilities of the data given the hypothesis.
109
What conditions are required for Bayesian learning to be equivalent to minimizing the sum of squared error?
1. Deterministic function f(x)
2. Purely Gaussian noise (0 mean, unit variance)
110
What is the "maximum a posteriori"? What does it do?
MAP says that the optimal hypothesis is the one that *minimizes* the *misclassification* (i.e. error) and the *size of the hypothesis* (i.e. the complexity of the model). It's essentially a mathematical/information theoretical recapitulation of Occam's Razor in Bayesian terms. See screenshot.
111
The complexity of a model is the number of parameters it contains? (True/False)
False. It's related to this, but it's more about *encoding* those parameters, not the raw number of them. Think about neural networks. You can overfit because you have too many neurons (i.e. weights), but you can also overfit if the weights become really large. This makes sense from an information theoretic perspective. If the *weight values* become large, it requires more "bits" of information to encode those models, hence a higher complexity. This is what is meant by the "*size of hypothesis"* in the lectures.
112
Bayes Rule effectively allows you to swap _______ and \_\_\_\_\_\_\_\_?
Causes, Effects
113
Generally speaking, which is easier to compute, Pr(h|D) or Pr(D|h)?
Pr(D|h)
114
What is the connection between MAP and ML (Maximum Likelihood)?
Maximum likelihood is what you get when the prior over the hypotheses is uniform
115
To make a Baysian Optimal Classifier, what is the thing you should do?
Since what we're actually interested in is *getting the label of the data correct,* what we should do is allow the hypotheses to ***vote*** on the label (which makes it sort of connected to ensemble learning). Trying to calculate the Pr(h|D) is really just a means to an end at the end of the day; the label is what we care about, i.e. Pr(label|D)
116
What is the definition of conditional independence?
*X* is conditionally independent of *Y* given *Z* if the probability distribution governing *X* is independent of the value of *Y* given the value of *Z.* That is:
P(X|Y,Z) = P(X|Z)
Basically if we can predict X given Z alone, then Y provides no information to us, hence X is conditionally independent of Y.
117
For a Bayesian Belief Network, the size of the graph grows exponentially with more variables? (True/False)
True
118
We can infer causality by looking at the directional relationships in a Baysian Belief Network? (True/False)
False. What we're actually looking at is only dependent in a statistical sense; causality can't necessarily be inferred.
119
When sampling from the join distribution in a Bayesian net, the graph must be _______ \_\_\_\_\_\_?
***directed acyclic.*** This is because a Baysian net is essentially trying to encode cyclical independies, so if there were cycles, that would be tantamount to saying there are none.
120
For Reference: Cheat Sheet for Probabilities
121
In a Bayesian network, arrows between variablies indicate dependencies? (True/False)
False. They indicate ***conditional independencies***
122
What's one of they key takeaways from Naive Bayes? What is the MAP estimate for that class?
The takeaway is that in the real world, we often get an example of some class *V*, say spam mail. We observe that that class has certain attributes *a.* But for classification, what we really want is **NOT** a model that goes from *V* --\> *a,* but rather a model that maps from *a --\> V.* Bayes Rule helps us do this.
The MAP estimate for the class is simply the argmax of the prior probability of the class P(V) multiplied by the *product* of all the conditional probabilities of the attributes given the value.
123
What are some of the advantages of Naive Bayes?
1. Inference is cheap (we can also perform inference in any direction, e.g. to generate missing attributes)
2. Few parameters
3. Estimate parameters with labeled data (see screenshot for how this is actually calculated)
4. Connects inference and classification
5. Empirically successful
124
What are some of the challenges with Naive Bayes?
1. **Doesn't model interrelationships** between attributes (it assumes independence between attributes)
2. **Unseen attributes** - Since the calculate requires the product of all the conditional probabilities of the attributes, that means if we have a feature that is important for classification but for some reason doesn't appear in the dataset (perhaps too small of a dataset, etc.), the product ends up being 0!
125
As the annealing temperature T ---\> 0 in simulated annealing, what the does algorithm behave like?
Regular hill climbing
126
As the annealing temperature *T--\>infinity* in simulated annealing, what does the algorithm behave like?
Random walk
127
Compare and contrast genetic algorithms with hill climbing with random restarts?
In some ways you can think of them as the same. We're still initially sampling to get a fitness score, and then restarting to ensure we don't get stuck in local optima. The difference is with genetic algorithms, we're making the assumption that the *population distribution contains information that we can exploit to generate new combinations that are better than the individual values.*
128
What are some of the ways you can select the "most fit" individuals in a genetic algorithm.
Truncation selection, roulette wheel (i.e. weighted probabability, etc.). The latter one kind of reminds me of particles filters and the weighted resampling that we do there.
129
What's one of the assumptions we make when performing crossover in genetic algorithms?
1. Locality of the bits (assuming a discrete problem)
2. More generally, that there are ***independent* *subspaces to optimize***. That is, that there is some structure to the problem that we can optimize parts of it without impacting other parts (or in practice, at least minimally so). Think of the bit string example in the lectures. If we swapped the first half of the 8-bit sequence in "Charles" with the corresponding 4-bit sequence from "Sheila", that's only a sensible thing to do if there's some structure in place that makes it such that those positions exist in the same topological space.
130
What is uniform crossover in genetic algorithms?
Basically just randomly corrupting bits to form new string.
131
When is random optimization useful?
If there is no gradient pointing the way (e.g. function is too complex, unknown, not differentiable, etc.)
132
What's one of the big problem that all 4 of the first random optimization algorithms that are discussed in the lectures suffer from?
They're "amnesiacs". That is, they keep track of history, but they *don't really use that history to discover and communicate structure in the problem that they might be able to exploit to find a better solution* (or to find it more quickly)
133
MMIC does not require locality in the same way that genetic algorithms do? (True/False)
True.
134
What is the MMIC algorithm trying to represent?
Structure.
135
What price do you pay for using MMIC? What do you get in return for this price?
Time. MMIC often runs in many orders of magnitude *fewer* iterations than things like Simulated Annealing or GA, but each one of those iterations takes a lot *more time* because we're estimating the parameters for the distribution at each step.
The bonus that you get is *information* that is contained in the *structure of the problem.*
136
137
What is the connection between MAP (Maximum A Posteriori) and Bayesian Learning?
The connection is between the MAP formula: *HMAP* = argmax[P(D|h) \* P(h)] and information theory. If we manipulate the math a bit, this works out to being the same as *minimizing* the entropy of the *misclassification (i.e. error) **plus** the size of the hypothesis).* It's basically a recapitulation of Occam's Razor: ***"We should prefer the simplest (i.e. lowest complexity) hypothesis that best explains (i.e. accuracy) of the data."***
138
If you were to take a KNN and set *k=n,* (where n is the number of datapoints), what value would you get out? What's a way you could change that value? What other algorithm is this situation similar to?
Since KNN is instance based learning, if k=n then you're simpling using all the datapoints to generate your output, in which case you'll simply get a constant value: *the mean*. One way of changing the value would be to use a w*eighted average.*
Using k=n for KNN, using boosting (i.e. ensemble learning) would output the same value (the mean) in the case where each datapoint forms it's own subset that a 0th order polynomial learner is trained on. Each of the 0th order polynomials simply learns the value for that specific point, and the ensemble would just then average over all of those, hence the overall average of the dataset would be returned.
139
Similarity captures _______ \_\_\_\_\_\_\_\_\_?
Domain Knowledge (see the lectures on distance metrics and K-NN)
140
One of the weaknesses of K-NN is that it assumes smoothness of the underlying function. What's one way of getting around this?
You could use locally weighted regression. In fact, you could really stuff any learning algorithm you want into small, piecewise regions, and then stitch those together to form a non-linear hypothesis space.
141
If I want to use more features, how much more data do I need?
It grows exponentially in the number of dimensions: *O*(2*d*)
142
What is the connection between SVMs and K-NN?
K-NN is all about finding what datapoints actually *matter,* i.e. the k-nearest points to the query point according to some distance metric. SVM is similar, *except that instead of taking the lazy approach of a K-NN, it performs a calculation (eagerly) to figure out what datapoints it can throw away.* It can do this because only the points near the boundary actually matter in terms of constructing the margin for the hyper-plane.
143
How do we inject domain knowledge into the K-NN algorithm? How do we inject it into an SVM?
For K-NNs we do it using the distance (*similarity*) metric. For SVMs, the *kernel* plays the same role.
144
What is the Mercer Condition?
It's a requirement that for an SVM the kernel type must be a well-defined distance or similarity metric.
As a side note, I was wondering about using KL divergence as a kernel function, but I'm thinking that the Mercer Condition probably precludes that since KLD isn't symmetric.
145
What is the connection between SVMs and Boosting?
Boosting is in a sense increasing the confidence of its predictions by increasing the margin of it's decision boundary. This is the same thing that an SVM does, maximizing the margin of the hyperplane that separates the classes.
146
What type of noise can cause boosting to overfit?
Pink noise (i.e. *uniform noise*)
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
