[ML] Unsuperviced learning / K-means algorithm / Principal Component Analysis(PCA)

Unsuperviced learning:

No labels.
Clustering Algorithm.

Used for:
Market segmentation
Social network analysis
Organize computing clusters
Astronomical data analysis


---
K-means algorithm (Mostly used)
1. iterative algorithm
2. randomly init. cluster centroids.
3. for data sets, assign each dataum , which is
closer to which centroids, assign to the closer centroid.

4. move centroid. Compute the mean for each centroid.
This will move the centroid.

5. Redo step 3.


Input:
    1. K(number of clusters)
    2. Training set {x(1), x(2), ..., x(m)}
   
x(i) ∈ R^n (drop x(0) = 1 convention)

If a centroid has no data assign to it
(which is that no data is closer to this centroid)
The centroid can be removed.
Or re-random initialize the centroid.
(Usually removing the centroid is more common)


K-means for non-separated clusters.



------
Optimization objective

1. Help debugging the algorithm
2. Help K mean find better cluster


While K mean's running, monitor 2 set of variables:
1. C(i) , index of cluster(1,2,...,K) to which example
    x(i) is currently assigned
   
2. u(k) , cluster centroid k (u(k) ∈ R^n)


Distortion Cost Function:
Find the min distance between data set and the assigned centroid.

-------------
Random Initializing.

1. Should have K < m
i.e number of centroid should less than number of testing data set.

2. Randomly pick K training examples

3. Set u(1),...,u(k) equal to these K examples

Be aware that the way we choose centroid, could end up
with different result.

Local optima:

To deal with local optima, run K mean random initialization multiple times. (usually 50 ~ 1000 times)

Pick one of the Distortion Cost function result as the Best solution.

----

Choosing the number of clusters.
Elbow method: (Worth a shot, but not always useful.)

Choosing the value of K:

----------------------
Dimentionality reduction
(i.e 2D -> 1D)

Motivation:
1. Data compression

2D -> 1D

3D -> 2D / 10000D -> 1000D

Motivation:
2. Data visualization



----------
How to reduce dimension?

Principal Component Analysis problem formulation(PCA)

Projection error. (The distance from sample to the linear line)

PCA:
Reduce from 2-dimension to 1-dimension: Find a direction
(a vector u(1) ∈ R^n)
onto which to project the data so as to minimize the projection error.

Reduce from n-dimension to k-dimension: Find k vector u(1), u(2), ..., u(k) onto which to project the data, so as to minimize the projection error.


PCA is not linear regression.

Left: linear regression, right: PCA

-----
PCA algorithm:

1.Compute 'covariance matrix'

2. Compute 'eigenvectors' of matrix ∑

--------
Reconstruction from compressed representation.

i.e reverse back to original data.

------
Dimentionality reduction:
Choosing the number of principal components.(k)

Method 1:
Start from k=1 ... k=17

Method 2:

Summerize:

-------
Advice for applying PCA


Use PCA on supervised data:
1. Extract inputs
    unlabeled dataset:
        x(1), ... , X(m) ∈ R^100000
    through PCA:
        x(1), ... , X(m) ∈ R^1000
       
2. new training set:
        (z(1), y(1)) , ... , (z(m), y(m))
   

Summerize:

Bad use of PCA:
1. to prevent overfitting, because reduce the features.
2. PCA does not honor label y

Use regularization instead.

3. Design of ML system:

Start without PCA _FIRST_.

[ML] Debugging a learning algorithm

Debugging a learning algorithm:

1. Get more training examples. Really? Think.
2. Try smaller sets of features.
3. Try getting additional features.
4. Try adding polynomial features
5. Try decreasing λ
6. Try increasing λ

Which to choose? Please don't randomky picking up one!
Think!

-----------------
How to evaluate algorithm:

While there are too many features, plotting the learning algorithm
isn't practical to see if the learning algorithm fits.


Idea:
Given a set of dataset, we could first seperate it into 2 portions.
one for training set, another one for test set. 7:3 split.
Randomly choose which data go to training set, which go to test set.


Training/testing procedure for linear regression:
   

   
Training/testing procedure for logistic regression:

---
Model selection:
Which polynomial function to choose?
To prevent overfit.

d = degree of polynomial.

d=1, ϴ(1)  ,  compute test set: J(ϴ(1))
d=2, ϴ(2)  ,  compute test set: J(ϴ(2))
...
d=10, ϴ(10)  ,  compute test set: J(ϴ(10))
   
Choose the one generates min error as the polynomial function.

Say, we choose d=5.
Problem:
J(ϴ(5)) is likely to be an optimistic estimate of generalization error.
i.e our extra parameter(d=degree of polynomial) is fit to test set.

To address the problem:
1. Instead of split dataset into 2 portions, we split dataset into
    3 portions.

2. Training set (6), Cross validation set(CV)(2), test set(2).

{Train/validataion/test} error:
   

   
Instead of testing with test set, test the picked ϴ for dn
with Cross validation set.

   

-----------------

Bias vs. Variance:
   

   
Question: How to differentiate the error is comming from high bias
or high variance?

Easy...

When d=1 or lower degree of polynomial function,
that means, the power of the variable is small, which won't
effect the error that much, thus, the ϴ(0) , i.e the bias,
play a more criticle role of the error.

When d=large, the error could be coming from variance.

   

   
-----------

To prevent overfitting, we use regularization.
1. While λ is LARGE, the ϴ will be penalized through iteration, which will close to 0.
    Thus ϴ0 will dominate the h(x) function.
2. While λ close to 0, the ϴ will be closely fit after iterations, causing h(x) overfits.
3. While λ is intermidiate "just right", the h(x) is good.

How to find the λ for us?
1. define Jtraining(ϴ)  without regularization term.
2. define Jcv(ϴ) without regularization term.
3. define Jtest(ϴ) without regularization term.
   

   
Choosing the regularization parameter λ:
1.
λ = 0, 0.01, 0.02, 0.04...10 , for each λ, we find the min J(ϴ), and get ϴ.

2. Use Jcv(ϴ) , the ϴ found in step 1. for each of the λ.

3. Pick the smallest Jcv(ϴ), and that λ is the correct regularization λ.

4. Last, use test set to feed the picked λ with Jtest(ϴ) see how well the result it.

------------------
Learning Curve:
Plot:
Jtrain
Jcv

m as number of training set.

Let's now tuning the m.

While m number is small, our h(x) can fit the set perfectly.
While m number is large, h(x) is hard to fit.

If a learning algorithm is suffering from high bias, getting more training data
won't help.

If a learning algorithm is suffering from high variance, getting more training data
is likely to help.

------------
Recap:

There are  variable can be tuned.

1. d = degree of polynomial.
2.  λ, regularization.
3. m, number of data

--------------

1. Get more training examples.  Fix high variance problem.
2. Try smaller sets of features. Fix high variance problem. (Won't work for high bias problem)
3. Try getting additional features. Fix for high bias problem. Since the currnet hypothsis is too simple.
4. Try adding polynomial features. Fix for high bias problem.
5. Try decreasing λ.  Fix high bias, since λ times Totle of ϴ, smaller λ, minimize the effection of bias ϴ0
6. Try increasing λ. Fix high variance. Since high λ will cause the iteration finding of ϴ be smaller. Which make the Degree that ϴ times to be less
    effective.
   
----------------
Back to neural network:
1. More layers + regularization is better than less layers(under fitting), although takes more computation.

-----------------
Machine learning diagnostic:
Diagnostic: (can take time to implement)
A test that you can run to gain insigt what is/isn't
working with a learning algorithm, and gain guidance as to how best to improve its
performance.

[ML] Back propagation

L : Total number of layers in network.
s(l) : number of units (bias unit not included) in layer (l)
K : number of out put unit.

For binary classification,

y = 0 or 1

there will be only 1 output unit, either 0 or 1

i.e:

h(x) ∈ R

----
For multi-class classification (K classes),
y ∈ R^(K)

K output units.

i.e:
h(x) ∈ R^(K)

------

Cost function:

-------
Now, let's minimize the cost function output.

Backpropagation algorithm:

δj^(l) = "error of node (j) in layer (l).

With the use of matrix, we can get rid of j, only keep the layer (l).

i.e:
δ^l = a^l - y , each symbol as a matrix of   dimention (K X 1)

So, if we want layer 4 error δ,

δ^4 = a^4 - y for each node K.

δ^3 = (⊖^3)[transpose]δ^4 .* g'(z^3)

Steps:

1. Forward propagation to get the last layer L's  [a] nodes results
2. Use the last layer [a] result to calculate the last layer's  δ value.
3. There's no δ^1, layer 1 is the input layer, no errors.
4. Use ∆^l as accumulative results of all the δ^l of every training examples.
i.e:
    a^l * δ^(l+1)
5. vectorize it.

i.e:
a^l is 5 X 1 matrix, that is, for that layer l, have 5 nodes.
δ^(l+1) is 1 X 4 matrix, that is, for last layer, has only 4 nodes, K = 4.

a^l * δ^(l+1) is a 5 X 4 matrix.

Every a(i) nodes times the δ1 forms a column of 5 X 1 matrix. And
there are 4 δ.

---------------
Forward propagation:

[a] is called activation function, i.e g(h(x))

Steps by steps:

Simplified explaination:

-------------

Back propagate, consider each layer has only 1 node.

i.e , to calculate δ2^(2), from right to left, we have ⊖(12)^2 * δ1^(3) + ⊖(22)^2 * δ2^(3)

When we say :
 ⊖(12) , means that 1 is for node 1, 2 is for the 2nd feature.

----------------
Implementation detail:

Reshape command:
By unrolling, same as for loop unrolling, make all elements into a row vector.

While need the original vector, reshape from the unrolled row vector.


e.g:
octave:

theta1 = ones(10,11)
theta2 = 2*ones(10,11)
theta3 = 3*ones(1,11)

% unroll
thetaVec = [ theta1(:); theta2(:); theta3(:)];

reshape(thetaVec(1,110),  10, 11) % arg1: input vector;  arg2: row count; arg3: col count

symbol meaning:
***  X12 , ALWAYS, which NODE, which FEATURE.  i.e : Node 1, Feature 2.


------------------
Gradient checking:

Numerical estimation of gradients:
Simple, use J(x +/- ε) to find the 2 points slope, that could estimate the J(x).
Use 2 sides approach than 1 side approach, which former is more accurate.
(free from error causes, which average will cover that.)

i.e:

While  ⊖ is in n dimention:
 ⊖ ∈ R^n  ( ⊖ is unroll with ⊖1, ⊖2, ..., ⊖n features)

So, after compute the approximate value of deferentiated value, compare

with the backpropagation result, they should be close, otherwise, our backpropagation

code should have a bug...

steps:

----------------

Random initialization:

We need initial value for ⊖.  

Don't do zero initialization for all the ⊖.

It's meaning less...

Thus, using random value for every ⊖.

--------------
 So, let's start using this:

Pick a network architecture(connectivity pattern between neurons)
 (number of nodes in hidden layers, default is that each hidden layer has same nodes,
 the more hidden layers the better.)
 (number of input nodes, i.e features)
 (number of output nodes, i.e number of classes, i.e
 y=
 [1
 ...
 0] ;
 [0
  1
  ...
  0];
 [0
  0
  1
  ...
  0];
 
 

 
------------------

Training a neural network:

Beware that since this is a classification problem, the cost function is non-convex,
i.e, could stuck in local minimum.
However, in practice, this isn't a issue due to even it's local minimum, it's good enough
for the h(x) to predict future input.

graph e.g:

-----------------