Week 8

Question 1

What are the 3 pillars of machine learning?

Answer 1

1. Linear Algebra
2. Probability
3. Optimization

Question 2

what does linear algebra pillar say?

Answer 2

Structure / Relationship between data

Question 3

what does probability pillar say?

Answer 3

Nose / Uncertainity

Question 4

what does the optimization pillar say?

Answer 4

finding the best fit

Question 5

What is the general form of an optimization problem?

Answer 5

we have a variable / parameter (x belongs to Rd) to which we need the minimum value and an objective function f (x) and constraints function gi(x)<=0 for all i =1,…,k (symbolizes all less than or equal to constraints - aka inequality constraints) and hj(x)=0 for all j=1,…,L (symbolizes all equal to constraints - aka equality constraints)

Question 6

how to solve an unconstrained optimisation problem?

Answer 6

we need to start at arbitrary value for x0 and choose a proper step size to converge like (1/t,1/t+1,1/t+2….)

Question 7

where does gradient descent algorithm converge to ?

Answer 7

Local Minimum (NOT Global Minimum) . In most optimization problem, Local Minimum is sufficient and good.

Question 8

What are convex functions?

Answer 8

Local minimum is also the global minimum of the function

Question 9

What is a Taylor series? what does it say?

Answer 9

Taylor’s series allows us to find the value of a function at point (x+d) given we know f(x) and all derivatives of f(x).

That is, if we have complete information about the derivatives at a point, we could find out the values of the function at any other point

Question 10

Why is Taylor’s series useful in optimization?

Answer 10

given n (eta) to be small.. we could ignore the higher order terms (2nd derivative and upwards) and approximate f(x+nd) to f(x) +ndf’(x)

f(x+nd) - f(x) = ndf’(x)

f(x+nd) - f(x) should be <0 if the function value is expected to decrease. This implies that ndf’(x) should be less than zero. since n and f’(x) are fixed, we need to find d such that the entire term is negative. selecting d to be -f’(x) negative slope ensures that we select a function of x that is sure to reduce the value if moved on that side

Question 11

how to use gradient descent for multivariate functions?

Answer 11

In multivariate function , derivative = Gradient (vector of partial derivatives)

If we move in the opposite direction from gradient, we are sure to move in the direction of steepest descent and we will decrease the value of the function the fastest.

Question 12

Is the direction of gradient descent always the right direction to choose?

Answer 12

For unconstrained optimization - YES

For constrained optimization - NO. The direction of steepest descent may be eliminated by the constraints.

Question 13

What is newton’s method for optimization?

Answer 13

Not parametric (n is not available)
update rule for newton’s method is
xn+1 = xn- (f’(x) / f’‘(x))

For higher dimensional functions, it requires computing inverse of Hessian matrix.
Newton method does not work if the Hessian is not invertible.

Newtons method may not converge. For some functions and some starting points, it may enter an infinite cycle.

It may converge to a saddle point instead of local minima

It takes more time per iterations and more computation and memory intensive.