Newton's Method

Newton-Raphson Method

(see also Maximum Likelihood Visualization via SAS and R)

"Newton's method, also called the Newton-Raphson method, is a root-finding algorithm that uses the first few terms of the Taylor series of a function f(x) in the vicinity of a suspected root."­ - http://mathworld.wolfram.com/NewtonsMethod.html

Given we want to find some root value x* that optimizes the function f(x) such that f(x*)=0, we start with an initial guess x­­_n and expand around that point with a taylor series:

f(x_n + Δx ) = f(x_n) + f’(x_n)Δx + …=0 where Δx represents the difference between the actual solution x* and the guess x_n.

Retaining only the first order terms we can solve for Δx :

Δx = -[f(x_n)/f’(x_n)]

If x_n is an initial guess, the next guess can be obtained by:

x_n+1 = x_n - [f(x_n)/f’(x_n)]

Note as we get closer to the true root value x*, f(x_n) gets smaller and Δx gets smaller, such that the value x_n+1 from the next iteration changes little from the previous. This is referred to as convergence to the root value x*, which optimizes f(x).

Numerical Estimation of Maximum Likelihood Estimators

Recall, when we undertake MLE we typically maximize the log of the likelihood function as follows:

Max Log(L(β)) or LL ‘log likelihood’ or solve:

∂Log(L(β))/∂β = 0    =  'score matrix'   = u( β) = 0

Generally, these equations aren’t solved directly, but solutions ( β^hat 's) are derived from an iterative procedure like the Newton-Raphson algorithm.

Following the procedure outlined above, let

β^t = initial guess or parameter value at iteration t

β^t+1 = β^t –[ ∂ u(β^t) / ∂ β^t]^-1 [u(β^t)]  

(note the product in the 2^nd term is the same as –[f(x_n)/f’(x_n)]

given  [∂ u(β₀) / ∂β] = hessian matrix ‘H’ and u( β) = ∂Log(L(β))/∂β = score matrix ‘S’

the update function can be rewritten as:

β^t+1 = β^t –H ^-1(β^t) S (β^t)

Step 1: Guess initial value β^t 

Step 2: Evaluate update function to obtain β^t+1

Step 3: Repeat until convergence (differences between estimates approach zero)

Fisher Scoring

Similar to Newton's method above, but replace  H^-1 with its expected value E(H^-1 ) =  I^-1 and use

β^hat=  β₀ - I^-1(β₀) *u(β₀) in the update, repeating until convergence.