Unsupervised Learning

Question 1

reason for clustering

Answer 1

categorize data without labels

Question 2

cluster searching

Answer 2

1. search for closest cluster
2. search within the cluster

** Note: much faster than searching each document

Question 3

k-means training

Answer 3

1. initialize k random centers
2. calculate points in each cluster
3. recalculate the cluster centers using the mean

Question 4

responsibility

Answer 4

Question 5

fuzzy k-means (soft k-means) algorithm

Answer 5

• reflects confidence in cluster

1. initialize k random centers
2. calculate responsibilities (soft max)
3. calculate mean responsibilities (hard k-means is where r is 0 or 1)

Question 6

k-means cost function

Answer 6

• Euclidean - sensitive to scale and K, K=N -> 0 cost
• Davies Bouldin index - low ‘inter’ std and high ‘intra’ std; lower better

Question 7

where k-means fails

Answer 7

1. donut
2. assymetric (high var) gaussian
3. smaller cluster in bigger one

Question 8

k-means problems

Answer 8

1. choice of k
2. local minimum is bad in this case
3. sensitive to initial clusters
4. can only find spherical clusters
5. does take density into account

Question 9

ideal k value

Answer 9

• where the steep meets the flat
• not at the minimum

Question 10

hierarchical (agglomerative) clustering

Answer 10

• greedy algorithm
• merge two closest points until you have 1 group with all of the points
• threshold the cluster intra distance

Question 11

joining cluster

Answer 11

1. single linkage: min distance between any two points
2. complete linkage: max distance b/w any two points
3. mean distance (UPGMA): mean distance between all pts
4. Wards: minimize increase in variance

Question 12

dendrogram

Answer 12

Question 13

distances equations

Answer 13

Question 14

valid distance metrics

Answer 14

1. non-negative: d(x, y) ≥ 0, positive
2. identity: (x, y) = 0 <=> x=y, definite
3. symmetry: d(x, y) = d(y, x)
4. subadditive: d(x, z) ≤ d(x, y) + d(y, z)

Question 15

self-organized maps

Answer 15

• apply competitive learning as opposed to error-correction learning
• dimension reduces to discretized representation of the input
• called a map

Question 16

gaussian mixure model (GMM)

Answer 16

• form of density estimation
• gives approximation of the probability distribution
• use when notice multimodal data
• p(x)=π1N(µ1,∑ 1)1+π2N(µ2,∑ 2)2
• π=probility x belongs to to Gaussian k
• π sums to 1
• introduce latent Z for which π=p(Z=k)
  *

Question 17

GMM algorithm

Answer 17

Question 18

responsibility k-means v. GMM

Answer 18

• k-mean cluster use of softmax
• GMM uses normal times probabilities

Question 19

independent component analysis (ICA)

Answer 19

• special type of blind source separation
• cocktail party problem of listening in on one person’s speech in a noisy room
• data: x=(x₁,…,x_m)^T
• hidden components: s=(s₁,…,sn)^T
• mixing matrix: W n by n
• unmixing matrix recovers source: W=A^-1.
• generative model (noiseless): x=As
• noisy: x=As+n
  *

Question 20

benefits of GMM over fuzzy k-means

Answer 20

• GMM has multiple π as opposed to one ß
• it can handle elliptical whereas fuzzy k-means needs to be spherical

Question 21

GMM v. Fuzzy K-means

Answer 21

Question 22

singular covariance problem

Answer 22

• close points approach 0
  
  • division by 0 is singularity
• local minimum

Question 23

ways of dealing with singular covariance problem

Answer 23

1. diagonal covariance -
   
   1. solution to singular covariance
   2. speed up computation (easy to take inverse)
2. spherical gaussian
3. shared covariance

• each gaussian has the same covariance

Question 24

diagonal covariance

Answer 24

Question 25

kernel density estimation

Answer 25

fitting PDFs with kernels; can use GMM

Question 26

expectation-maximization (EM)

Answer 26

• general version of GMM
• latent variables
• coordinated descent
• increasing likelihood guarantee (max likelihood)

Question 27

dimensionality reduction

Answer 27

1) cleaner signal; 2) decreased transformation load -> reduced time; 3) allow visualization of data

Question 28

single value decomposition (SVD)

Answer 28

Question 29

PCA

Answer 29

• Z=XQ
• rotates the data (changes eigenvector and values), doesn’t change the length
• high variance = signal
• low variance = noise
• keep left most columns of Z (~95 %)

Question 30

how does PCA help?

Answer 30

1. cleaner signal
2. decreased transformation load -> reduced time
3. allow visualization of data

Question 31

naive bayes connection to PCA

Answer 31

PCA makes IID assumption true

Question 32

greedy layer-wise pretraining

Answer 32

• helps with supervised learning
• only objective of layer is to train itself
• only requires a few epochs of training to fine-tune

Question 33

autoencoder

Answer 33

• J=|X-s(S(XW)W.T)|**2
• non-linear PCA
• linear activation gives PCA
• predicts itself (auto=self)
• square error for x < 0 and x > 0
• cross-entropy works for 0 ≤ x ≤ 1
• different biases for hidden and output layers
• shared weights (type of regularization

Question 34

types of autoencoders

Answer 34

1. Denoising autoencoder
2. Sparse autoencoder
3. Variational autoencoder (VAE)
4. Contractive autoencoder (CAE)

Question 35

bottleneck network

Answer 35

• find useful and efficient representation
• compress V dimension into D in the encoding phase

Question 36

stacking

Answer 36

• we only care about the “inner” representation
• discard the 2nd half each time
• each layer smaller in size

1. train an autoencoder on X with HL output Z;
2. train a 2nd autoencoder on Z;
3. repeat

Question 37

denoising autencoder

Answer 37

• an autoencoder that is missing information
• attempt to address identity-function risk by randomly corrupting input
• its like training with dropout
• missing data not always represented by 0
  
  • mask the cost in back propagation

Question 38

sparse autoencoder

Answer 38

• when you train an autoencoder, the hidden units in the middle layer would fire (activate) too frequently, for most training samples
• sparsity constraint: lower the activation rate so that they only activate for a small fraction of the training examples
• sparse because each unit only activates to a certain type of inputs

Question 39

how to reproduce missing data

Answer 39

• use autoencode or the likes
• *

Question 40

recommender systems

Answer 40

• google, youtube, netflix
• use RBMs and autoencoders
  *

Question 41

naming convention

Answer 41

• Recommender
  
  • N is instances
  • M is movies
  • K is latent variables
• Typical Deep Learning
  
  • N is instances (same)
  • M is hidden units
  • K is number of classes
  • D is input dimensions

Question 42

boltzmann machine

Answer 42

• everything is connected to everything
• only works on trivial problems, unlike RBM
• non-tractable

Question 43

restricted boltzmann machine (RBM)

Answer 43

• bipartite graph
• produces visible vector from hidden and vice versa
• assume each hidden and output is IID
• use sigmoid (to keep output 0-1)
• act just like autoencoders
  
  • find latent variables
  • greedy pretraining
• non-tractable, therefore, needs to be approximated hidden units only connected to the visible unit
• square error for all X
• cross-entropy works for 0 ≤ x ≤ 1

Question 44

categorical RBM

Answer 44

Question 45

categorical RBM shapes

Answer 45

• h = M
• V = D x K
  
  • D is number of movies
  • K is the number of classes
• W = D x K x M
• b = D x K
• x = M

Question 46

deep belief network

Answer 46

deep network of stacked RBMs

Question 47

latent variable

Answer 47

variable that is hidden

Question 48

markov random field

Answer 48

• graph of states
• each node is a state
• state of each node only relies on adjacent node

Question 49

relaxed bernouli constraint

Answer 49

in RBM,

1. threshold
2. let the values go to whatever

Question 50

hidden markov model

Answer 50

* unsupervised learning method

• models sequences & classifies
• modified using bayes rules to create separate model for each class
• choose class with the highest likelihood

Question 51

HMM applications

Answer 51

1. recognizing male or female voice
2. NLP: macbook was created by “p(x|x-, x–)”
3. stock predicition
4. SEO and bounce rate optimization
5. speech to text: words to sound

Question 52

markov property

Answer 52

• p(x | all time) = p(x | x-)
• strong assumption

Question 53

joint probability

Answer 53

• chain rule of probability
• p(s3, s2, s1) = p(s3|s2)p(s2|s1)p(s1)

Question 54

markov order

Answer 54

• 1st order - p(y2 | y1)
• 2nd order - p(y3 | y2, y1)
• 3rd order - p(y4 | y3, y2, y1)

Question 55

markov model

Answer 55

• M states
• π = 1 x M, column vector
• A = M x M weights
• A(i, :).sum() = 1

Question 56

smoothing

Answer 56

• add smoothing to account for unobserved
  
  • p = (count(x)+λ)/(N+λµ₀)
• can smooth average ratings too
  
  • r = (∑x_i+λµ₀)/(N+λ)

Question 57

HMM model

Answer 57

1. π_i = probability of starting at state i
2. A(i, j)
   
   1. state transition matrix
   2. probability of going to state j from i
   3. P(tag₁|tag₀)
   4. if row sum to 1, A is markov matrix
3. B(j, k)
   
   1. observation probability matrix
   2. probability of observing k given j
   3. p(word|tag)

Question 58

double embedded

Answer 58

• layer 1: Markov model
• layer 2: choose observation

Question 59

forward, forward-backward algorithm

Answer 59

Question 60

backward, forward-backwards algorithm

Answer 60

Question 61

forward backwards code

Answer 61

Question 62

viterbi algorithm

Answer 62

• find the most probable hidden state sequence given the observed sequence
• the same as forward backward algorithm except taking the max instead of sum
  
  • delta variable is like alpha
  • psi is similar to delta but argmax instead and no B term
• have to backtrack the states

Question 63

vertirbi initialization

Answer 63

Question 64

vertirbi recursion

Answer 64

Question 65

vertirbi termination

Answer 65

Question 66

Baum-Welch algorithm

Answer 66

• Is similar to Gaussian mixture models
• Use expectation maximization (iterative algorithm) instead of maximum likelihood
• review at some other date, it is a very expensive algorithm and should be avoided if possible

Question 67

variational autoencoder

Answer 67

• Bayersian ML + Deep Learning

Question 68

generative adversarial network (GAN)

Answer 68

• 2 networks competing against eachother
  *

Question 69

generative versus discriminitive

Answer 69

• generative: P(X|Y)
• discriminitive: P(Y|X)
  
  • hard to tell what is happening with weights
  • not satisfactorial to statistician
• research shows that discriminitive works better

Question 70

types of recommender systems

Answer 70

• autorec: uses autoencoder to recommend missing data
• non-personalized:
  
  • shows popular items
    
    • confidence
  • takes time into account
  • product associations
• collaborative filter: what YOU and what OTHERS similar to you like

Question 71

matrix factorization

Answer 71

• SVD example is an: X=WSU^T
  
  • S is diagonal matrix of the variances
  • more variance = more important
• we only want square error where rating is known
• break up X into components for less parameters stored
• use K size ~50-100
• A_ij=log(X_ij)~=w_i^Tu

Question 72

account for age in recommender system?

Answer 72

• hacker news: penalty*(ups-downs-1)^0.8/(age+2)^gravity
  
  • gravity = 1.8
  • age in hours
  • business rules:
    
    • penalize self, controversial and popular websites posts
• reddit: sign(ups-downs)log{max(1, |ups-downs|)}+age/45000
  
  • age in seconds

Question 73

ranking with big systems

Answer 73

• discard users w/ few movies in common
• sum over nearest neighbors
  
  • take ones with higheset weights
  • say k = 25 to 50
  • closest absolute correlation
  • closest raw correlation
  • or use everybody

Question 74

training matrix factorization

Answer 74

• J = ∑(t_ij-w_i^Tu_j)
• dJ/dw_i = ∑(t_ij-w_i^Tu_j)u_j=∑u_ju_j^Tw_i
  
  • w_i = (∑u_ju_j^T)^-1∑r_iju_j^T
  • j is of Ψ
• dJ/du_j = ∑(t_ij-w_i^Tu_j)u_j=∑u_ju_j^Tw_i
  
  • u_j = (∑w_jw_j^T)^-1∑r_ijw_i
  • j is of Ω
• but really, r_ij=w_i^Tu_j+b_i+c_j+µ
  
  • c_j = r_ij-w_i^Tu_j+b_i+µ
  • b_i = r_ij-w_i^Tu_j+c_j+µ
  • µ = global average