Perceptron Optimisation and Gradient Descent

Question 1

Explain local optimisation

Answer 1

If you graph the error for all values of a single weight and you want to reduce the error, you can use the gradient to decide which direction to reduce the error.

Question 2

Explain zero order gradient descent method for optimization

Answer 2

This method is essentially taking any step towards the goal regardless of the gradient of the slope.
Mathematically you know the gradient is up or down but not the magnitude so you take any step down.

Question 3

Explain first order gradient descent method for optimisation

Answer 3

You kow the gradient of the slope so you take the step that has the greatest descent towards your goal.

Question 4

How useful is zero order gradient descent? Why?

Answer 4

> Not effective

> Slow

Question 5

What is the equation for first order gradient descent?

Answer 5

x_(t+1) = x_t - η∇f(x_t)

Question 6

Explain the usefullness and benefits of second order gradient descent

Answer 6

> Extremely computationally intensive when you have a lot of varaibles
The benefit is that it takes a single (idillic) step in the right direction.
Often easier to just take lots of small steps

Question 7

When do you stop with gradient descent?

Answer 7

When the change in the gradient is less than a threshold

Question 8

What is the learning rate?

Answer 8

This is the step size

Question 9

What is the effect of the size of the learning rate?

Answer 9

If the step is too large you can travel too far and overshoot the minimum error.
This can cause diversion

Question 10

What is the effect of local minima?

Answer 10

There are multiple values each with a different minma. Gradient descent does not take this into account so it will converge on a local minima which may not be the smallest minima.

Question 11

What can we do to prevent local minima?

Answer 11

We can restart learning with random initial weights and it will converge on a different minima

Question 12

What is the issue with calculating gradient using E(X) = ∑ | y_n - t_n | ?

Answer 12

The equation (E(X) = ∑ | y_n - t_n |) is pievewise constant. So even if we improve the classification, if there is no change in error then it appears not to improve. The equation is not linearly differentiable so it has no gradient.

Question 13

How do we measure error where the value is continuous even if the number of misclassified points does not change?

Answer 13

By measuring how close each point is to the decision boundary

Question 14

What is the equation for calculating the distance of the misclassified point ot he decision boudnary

Answer 14

> x = x_p + d×w/||w||
> (x - x_p)||w|| / w = d
> d = distance to hyper place
> w = vector perpendicular to the hyper plane
> x_p = point on hyper plane
> x = misclassified point

Question 15

What is the new equation to calculate the total distance of all misclassified points?

Answer 15

E(X) = ∑ (w^T x_n + w_0)

Question 16

What is the new function for the error that is differentiable?

Answer 16

E(X) = ∑ w^T x_g (y_n - t_n)

Question 17

What is the equation of the gradient of the new error function?

Answer 17

E(X) = ∑ x_g (y_n - t_n)

Question 18

What is the gradient descent function with the new measurement of error?

Answer 18

w_k+1 = w_k - η × ∑ x_g (y_n - t_n)

Question 19

What is the issue of using this equation ( w_k+1 = w_k - η × ∑ x_g (y_n - t_n) ) for gradient descent?

Answer 19

It requires a lot of computation because eac h point needs to be calculated

Question 20

How do you reduce the amount of computation for gradient descent?

Answer 20

Using stchastic gradient descent

Question 21

What is stchastic gradient descent?

Answer 21

Instead of minimising the total error, we randomly select points and minimise the average error of those points

Question 22

What is the equation for calculating the average error?

Answer 22

E(X) = 1/N ∑w^T x_n (y_n-t_n )

Question 23

What is the equation for stchastic gradient descent?

Answer 23

w_(k+1) = w_k - ηx(y - t)

Question 24

What is the benefit of stchastic gradient descent? What is the trade off? What will happen overall?

Answer 24

Benefit: It uses much less computational power

Trade off: Sometimes the error can increase

Overall: The error will trend downward