1. A Walk Through Linear Models

(a) Perceptron

(a.i) Part 1: Preceptron & Part 2: Preceptron: Non-linearly separable case

Part 1: Preceptron

training set = 10
E_train is 0.00016666666666666666, E_test is 0.17675
Average number of iterations is 6.124.

In this condition, I set iteration threshold = 100.
As for E_train isn't equal to 0, I think there are 2 reasons:

1. The generated data forms some Non-linearly separable cases.
2. The iteration threshold is too small.

I lift the iters threshold to 1000, E_train = 0, the satisfied answer.
E_train is 0.0, E_test is 0.173
Average number of iterations is 5.992.

Part 2: Perceptron: Non-linearly separable case

training set = 100（noisy）
At first, the iteration threshold is 1000
E_train is 0.2771714285714284, E_test is 0.28826666666666606
Average number of iterations is 1000.0.

Then, I lift the iters threshold to 10000.
After calculating for a very long time,
E_train is 0.27365714285714265, E_test is 0.2900999999999996
Average number of iterations is 10000.0.

Conclusions

• Error on train set still exists and the number of average iterations is always the maximum iterations. It means the learning algorithm eventually repeats the same set of weights and enters an infinite loop.
• So when the dataset is large, we can't just use a two-dimensional line to separate them.

(a.ii)

When the iteration threshold is 1000

• train set = 10, the average number of iterations is 5.992.
• train set = 100, the average number of iterations is 1000.

(a.iii)

If the training data is not linearly separable, we can't find a line to separate all the data no matter how many iterations we use. The training error can't be 0.

(b) Linear Regression

(b.i) Part 3: Linear Regression

training set = 100
E_train is 0.037885714285714696, E_test is 0.05416666666666684

(b.ii) Part 4: Linear Regression: noisy

training set = 100（noisy）
E_train is 0.13465714285714314, E_test is 0.14853333333333318

Conclusions

• With noise increase, the E_train and E_test also increase.
• In the same condition, Linear Regression has less E_train and E_test than Perceptron, which may mean that LR can find more solutions in solution space.

(b.iii) Run Linear Regression on dataset poly_train.mat and poly_test.mat

w = [ -0.02413004, 0.23556134, -0.11510741 ]
E_train is 0.49, E_test is 0.5496

(b.iiii) Do the data transformation

w = [ -0.06872399, -0.02687646, 0.22464875, 0.13160111, -1.84827196, 2.00418171 ]
E_train is 0.05, E_test is 0.066

(c) Logistic Regression

(c.i)

training set = 100
E_train is 0.002428571428571429, E_test is 0.021333333333333343

(c.ii)

training set = 100, test set = 10000（noisy）
E_train is 0.1159, E_test is 0.13491999999999998

(d) Support Vector Machine

(d.i)

training set = 30, test set = 10
E_train is 0.001400000000000001, E_test is 0.036600000000000146

(d.ii)

training set = 100, test set = 30
E_train is 8.999999999999999e-05, E_test is 0.009799999999999977

(d.iii)

When nTrain = 100, the average number of support vectors is 3.094.
As I use the following code to define the support vector margin, where 1e-5 is set as a threshold so that it's not minimal margin exactly.

num = np.where(y_ - np.min(y_) < 1e-5)[0].__len__()

(d.iiii)

training set = 30, test set = 10（noisy）
E_train is 0.016366666666666637, E_test is 0.46869999999999973
Average number of support vectors is 29.381.

Conclusions

• When training SVM with noisy data, the classifier becomes overfitting on training data, the optimal hyperplane may be pushed far away from its original/correct place and the margin will be smaller than before, as the picture below.
• Adding slack variables can ease this problem.

2. Regularization and Cross-Validation

(a) Ridge Regression

(a.i)

• λ = 100

(a.ii)

• with regularization, sum(w²) = 0.13289524019362603
• without regularization, sum(w²) = 1.0204766956977154

(a.iii)

• with regularization, E_train = 0, E_test = 0.05976896032144651
• without regularization, E_train = 0, E_test = 0.12606730286288298

with regularization

without regularization

(b) Logistic Regression with Regularization

At first, the learning rate is 0.03

• λ = 1
• with regularization
  • E_train = 0, E_test = 0.0562531391260673
  • sum(w²) = 4.046897936351152
• without regularization
  • E_train = 0, E_test = 0.05725765946760422
  • sum(w²) = 158.64900269669087

with regularization, lr = 0.03

without regularization, lr = 0.03

Then I change the learning rate to 0.01

• λ = 1
• with regularization
  • E_train = 0, E_test = 0.050728277247614265
  • sum(w²) = 3.968900599887993
• without regularization
  • E_train = 0, E_test = 0.048719236564540434
  • sum(w²) = 25.414055343730237

with regularization, lr = 0.01

without regularization, lr = 0.01

Conclusions

• A suitable learning rate can also affect the model's complexity, in other words, little learning rate may get more little parameters in limited steps.
• When the learning rate changes from 0.03 to 0.01, the training error and test error also drop down. So sometimes, a good learning rate can generate a good model with less bias and variance.

3. Bias Variance Trade-off

(a)

1. False. High bias means the model is very simple, the estimated value is far away from the truth. In this condition, we should change the model to a more broad space by adding parameters or other measures. Just adding more training examples cannot solve this problem.
2. False. High variance means the model is overfitting on the training set, which will result in large test error. But we want to find a model behaving well on test data with good generalization ability.
3. True. By using more parameters we can create a quite complicated model. It can even have zero-error on the training set, which also results in overfitting problem with high variance.
4. False. Introducing regularization will control overfitting on the training set, and the model will behave better on the test set. This is the key reason we use regularization. And the performance also depends on the λ we choose. Sometimes, the model doesn't behave quite well on the training set but behave well on the test set.
5. False. Large λ means more control of parameters. It will make the parameters we learn so small that the eventual boundary is like a simple line, as the picture below. And the training set data will have little influence on the model training process. So the performance of your hypothesis will be severely hurt.