Exam 2

Question 1

Unsupervised Learning

Answer 1

• Data Description

Question 2

Single Linkage Cluster - SLC

Answer 2

• Consider each object a cluster (n objects)
• Define inter-cluster distance as the distance between the closest points in the two clusters
• Merge the two closest clusters
• Repeat n-k times to make k clusters
• How you define the inter-cluster distance = domain knowledge

Question 3

Single Linkage Cluster Run Time

Answer 3

O(n^3)

Question 4

Issues with SLC

Answer 4

Might end up with wrong clusters, depending on the distance definition

Question 5

k-means clustering

Answer 5

• Pick k random center points
• Each center claims its closest points
• Recompute the centers by averaging the clustered points
• Repeat until converge

Question 6

Configurations (k-means as an optimization problem)

Answer 6

center
P

Question 7

Scores (k-means as an optimization problem)

Answer 7

How much error you introduce by representing these points as centers

Question 8

Neighborhood (k-means as an optimization problem)

Answer 8

The neighborhood of a configuration is the set of pairs where you keep the centers the same and you change the partitions or you keep the partitions the same and you move the centers

Question 9

Properties of k-means clustering

Answer 9

• Each iteration is polynomial O(kn)
• Finite (exponential) iterations O(k^n)
• Error decreases (if ties are broken consistently)
• Can get stuck, if it started with wrong centers. This is similar to converging to a local optima. One solution is to use random restarts.

Question 10

Soft Clustering

Answer 10

Attaches cluster probability to each point instead of specific cluster

Task is to find a hypothesis that maximizes the probability of the data (Maximum likelihood)

Question 11

Maximum Likelihood Gaussian

Answer 11

The Maximum Likelihood mean of the Gaussian u is the mean of the data

Question 12

Expectation Maximization

Answer 12

• Assigns a cluster probability to each point
• Use the new u_j to recompute E[Z_ij]
• Expectation: E[Z_ij] defines the probability that element i was produced by cluster j.
• Maximization: u_j defines the mean of cluster j

Question 13

EM properties

Answer 13

• Monotonically non-decreasing likelihood: It’s not getting worse
• Does not converge
• Will not diverge
• Most probably will get stuck in a local optima. Use random restarts
• Works with any distribution (if E and u are solvable)

Question 14

Richness (Clustering Properties)

Answer 14

For any assignment C of objects to clusters, there’s some distance matrix D such that P_d returns that clustering C

Question 15

Scale-invariance (Clustering Properties)

Answer 15

Scaling distances by a positive value doesn’t change the clustering

Question 16

Consistency (Clustering Properties)

Answer 16

Shrinking intra-cluster distances (moving points towards each other) and expanding inter-cluster (moving clusters away from each other) distances doesn’t change the clustering

Question 17

Impossibility Theorem (Clustering Properties)

Answer 17

There’s no clustering algorithm that can achieve the three properties

Question 18

Time to select most relevant subset of features M, where M <= N

Answer 18

2^N

Question 19

Approaches to Feature Selection

Answer 19

Filtering and Wrapping

Question 20

Filtering (Feature Selection)

Answer 20

• Apply a search algorithm to produce fewer features to be passed to the learning algorithm
• Faster than wrapping
• Doesn’t account for the relationships between features
• Ignores the learning process (no feedback)
• We can use an algorithm (ex: Decision Tree) that can select the best features, then use another algorithm, with another inductive bias, for learning
• We can use different criterion to evaluate the usefulness of a subset of features:
  information gain, variance, entropy, eliminate dependent features

Question 21

Wrapping

Answer 21

• Given a set of features, apply a search algorithm to produce fewer features, pass them to the learning algorithm, then use the output to update the selected set of features
• Takes into account the learning model’s bias
• Very slow

We can use different techniques to search:
1. Randomized Optimization algorithms
2. Forward selection: select a feature and evaluate the effect of creating different combinations of this feature with other features. Stop once you stagnate. This is similar to hill climbing
3. Backward Elimination: start with all the features and evaluate the effect of eliminating each feature

Question 22

Forward selection

Answer 22

select a feature and evaluate the effect of creating different combinations of this feature with other features. Stop once you stagnate. This is similar to hill climbing

Question 23

Backward Elimination

Answer 23

start with all the features and evaluate the effect of eliminating each feature

Question 24

x_i is <> relevant if removing it degrades the Bayes Optimal Classifier

Answer 24

strongly

Question 25

x_i is <> relevant if its not strongly relevant or there's a subset of features S such that adding x_i to S improves the Bayes Optimal Classifier

Answer 25

weakly

Question 26

Relevance (Feature Selection)

Answer 26

Measures the effect of Bayes Optimal Classifier, how much information a particular feature provides

Question 27

Usefulness (Feature Selection)

Answer 27

Measures effect on error, measures if a feature helps in minimizing error given a particular model

Question 28

PCA

Answer 28

Example of an eigenproblem which will transform the features set by: - Finding the direction (vector) that maximizes variance, this is called the Principal Component - Finding directions that are orthogonal to the Principal component - Each Principal component has a prescribed eigenvalue - PCA gives the ability to do reconstruction, b/c its a linear rotation of the original space that minimizes L2 error by moving N to M dimensions so we don't lose information - We can center the problem around the origin by subtracting the mean of. the data - in effect, PCA produces a set of orthogonal gaussians - PCA is a global algorithm that is very fast.

Question 29

ICA

Answer 29

- Attempts to maximize independence - Tries to find a linear transformation of the feature space, such that each of the individual new features are mutually statistically independent - The mutual info b/w any 2 random features equals 0 - The mutual info b/w the new features set and the old features set is as high as possible

Question 30

Random Components Analysis

Answer 30

- Similar to PCA but instead of generating directions that maximize variance, it generates random directions - It captures some of the correlations that works well with classification settings - Faster than PCA and ICA

Question 31

Linear Discriminant Analysis

Answer 31

- Finds a projection that discriminates based on the label, it finds projections of features that ultimately align best with the desired output (wrapping function instead of filtering)

Question 32

5 Parts to a Markov Decision Process

Answer 32

Markov Decision Problem - State - representation - Model - Transition model, probability of transitioning to a new state given a state and an action - Actions - Things the object is allowed to do in a particular state s - Reward - Reward the object gets when transitioning to a state s, which tells it the "usefulness" of transitioning to that state Markov Decision Problem Solution - Policy - Takes a state and returns the proper action. A problem might have different policies

Question 33

Temporal Credit Assignment

Answer 33

We don't have instant rewards for each action, we have the problem of figuring out which specific action(s) lead us to a positive/negative outcome

Question 34

A small negative reward will encourage the agent to take the <> path to the positive outcome

Answer 34

Shortest

Question 35

A big negative reward will encourage the agent to take the <> path no matter what the result is, so it might end up with a negative outcome

Answer 35

shortest

Question 36

You can take <> paths to avoid possible risks if you have an infinite time horizon

Answer 36

longer

Question 37

If discount rate is 0 then:

Answer 37

we get the first reward and everything else will fall off to nothing

Question 38

If discount rate is 1 then:

Answer 38

we get a maximized reward

Question 39

Utility of Sequences

Answer 39

Summation of gamma to the t times reward of the state at time t Equals R_max divided by (1 - gamma)

Question 40

Value Iteration (Bellman Equation)

Answer 40

1. Start with arbitrary utilities 2. Update utilities based on neighbors 3. Repeat until convergence Guaranteed to converge because with each step we're adding R(s), which is a true value.

Question 41

Policy Iteration (Bellman Equation)

Answer 41

1. Start with an arbitrary policy pi_0 2. Evaluate how good that policy is by calculating the utility of using the policy 3. Improve the policy

Question 42

In MDP, our input is

Answer 42

a model consisting of a transition function T and a reward function R, and the intended output is to compute the policy pi (Planning)

Question 43

In Reinforcement Learning, the inputs are

Answer 43

transitions (initial state, action, reward, result state, ...), and the intended output is to "learn" the policy pi.

Question 44

Policy Search Algorithm (RL)

Answer 44

Mapping states to actions. Problem with this approach is that the data doesn't reveal which actions need to be taken (Temporal Credit Assignment Problem)

Question 45

Value Function based Algorithms (RL)

Answer 45

Mapping states to values. Use argmax to turn into policy

Question 46

Model-based Algorithm (RL)

Answer 46

Mapping (states & actions) to (next state & reward) Turn this into a utility function using Bellman equations then use argmax to get the policy. This is computationally indirect

Question 47

Q-function

Answer 47

Utility of leaving state s via action a, which is the reward of state s plus the discounted expected value of taking action a multiplied by the value of the optimum action in state s_prime

Question 48

Q-Learning

Answer 48

Estimating the value of Q(s,a) based on transitions and rewards Issue is that we don't have R(s) and T(s, a, s_prime) since we're not in an MDP setting

Question 49

Q_hat(s,a)

Answer 49

Estimate of the Q-function that we will update by a learning rate of alpha_t in the direction of the immediate reward r plus the estimated value of the next state

Question 50

Exploration

Answer 50

Getting the data that you need (learning)

Question 51

Exploitation

Answer 51

Stop learning and actually use what you've already learn

Question 52

Exploration-Exploitation dilemma

Answer 52

There is only one agent interacting with the world with conflicting actions

Question 53

Game Theory

Answer 53

Mathematics of conflicts of interests when making decisions. Related to AI when there's multiple agents acting in the environment

Question 54

In MDP we have the notion of a "policy", which is mapping states to actions. In Game Theory, we have the notion of a <>

Answer 54

Strategy

Question 55

Strategy (Game Theory)

Answer 55

Mapping of "all possible" states to actions

Question 56

Fundamental Result (Game Theory)

Answer 56

Everyone is trying to maximize his/her own reward while knowing that everyone is trying to do the same

Question 57

Nash Equilibrium (Game Theory)

Answer 57

We're in a situation where no one has any reason to change his strategy

Question 58

Mixed Strategies (Game Theory)

Answer 58

Instead of making the same decisions given the same circumstances (pure strategy), we assign probabilities to our state (distribution over strategy)

Question 59

Pure Strategies (Game Theory)

Answer 59

Make same decisions given the same circumstances

Question 60

3 Theorems resulting from Nash Equilibrium

Answer 60

1. In the n-player pure strategy game, if equilibrium of strictly dominated strategies eliminates all but one combination, that combination is the Nash equilibrium 2. Any Nash equilibrium will survive elimination of strictly dominated strategies 3. If the number of players is finite and we have finite number of strategies for each player, there exists at least one (possibly mixed) Nash equilibrium