Newton Method for IK

Newton Method

• 잘 모르는 문제를 풀 때 사용하는 방식이다.
• Jacobian 과는 다르게 점진적으로 문제의 해를 찾는 방식이다.
• 순서
  • Problem definition
  • Problem linearization
  • Iterative update
  • Convergence check
• $f(x+\sigma)\approx f(x) + [\nabla f(x)]^T + \frac{1}{2}\sigma^T H_j(x)\sigma$
  • 테일러 시리즈의 2차 형태를 기반으로 한다.
  • 이때 Hessian 계산이 포함되어있기 때문에 느리다.
  • BFGS 라는 방식으로 근사화 해서 최적화를 한다.

Newton Method pros and cons

advantages

• Fast convergence : 초기값이 맞는 경우 매우 빠르다.
• Quadratic convergence : 문제와 condition을 잘 신경쓴 경우 errror가 감소한다.
• Applicability to nonlinear problem : 직관적인 값을 준다. (jacobian의 경우는 풀리지 않는 해가 존재하는 경우도 있는 것과 비교되는 점)

disadvantages

• Sensitivity to initial conditions : 초기값을 제대로 찾지 못하면 결과가 좋지 못하다.
• Computation of Jacobian and Hessian : jacobian과 hessian을 모두 계산해야 답이 나오기 때문에 계산이 많다.
• Inverse of Jacobian : jacobian의 inverse까지 계산해야 하는 경우가 존재한다.

그러나..

• iterative 방식이기 때문에 최적화를 하여 결론적으로 Newton method가 더 빠른 방식이다.

Taylor Series

• power series
  • $\sum_{n=1}^{\infin}a_n(x-c)^n$
  • 위의 형태로 나타나는 형태
• taylor 급수는 power series의 한 형태이다.
• $f(x) = f(a) + \frac{f'(a)}{1!}(x-a) + \frac{f''(a)}{2!}(x-a)^2 + ...$
• 만약 a = 0 인 경우는 Maclaurim series expansion 이라고 부른다.
• 3차 미분 이후의 것은 함수에 큰 영향을 주지 않아서 무시한다

Newton-Raphson Method and IK

• IK 문제에 있어서는 Newton method와 같은 말이다.
• Newton-Raphson Method는 non linear function의 root 를 찾는 것이 목적이다.
  -> 0이 되는 값을 찾기
• IK의 목표가 $F(x) = s_d - f(\theta) =0$의 $\theta$를 찾는 것이었음
  -> 이 문제를 Newton-Raphson으로 풀어보기
  • 우리가 알고 있는 것은 $s_d$와 함수 $f(x)$이다.
  • x축이 $\theta$이고, y축이 $F(x)$인 좌표 평면에서..
  • 이때 x에 $\theta_0$라는 임의의 초기값을 찍어서 대입한 후 계산을 한다.
  • 계산한 그 점에서 기울기를 구하면 $-\frac{\partial f}{\partial \theta}(\theta_0)$가 된다.
  • 이 기울기와 점을 지나는 직선을 하나 그린 후 x축과 닿은 점을 다시 $\theta_1$ 이라고 설정한 후 위의 과정을 반복한다.
  • 반복하다보면 $\theta$ 값이 $\theta_d$ 로 점점 가까워지게 된다.
    -> 이것을 판단하기 위해서는 $F(\theta_d) = 0$ 을 이용한다.
    -> 0의 값은 threshold 로 계산 (정확히 0 아님)
  • 일반항을 구해보면 $\theta_{n+1} = \theta_n + \frac{s_d - f(\theta_n)}{f'(\theta_n)}$ 이 된다.
    -> 다른 방식으로 표현하면, $x_{n+1} = x_n - \frac{F(xn)}{F'(xn)}$

Newton-Raphson Method and Optimization Problem

• optimization은 목적함수가 최소가 되는 값을 찾는 것
  -> root finding은 0을 찾는 것
• root finding 과 optimization은 서로 전환이 가능하다.
  -> $s_d - f(\theta_d)$ 가 0이 되는 $\theta$ 찾기
  -> $-f(\theta_d)$ 가 최소가 되는 $\theta$ 찾기
• 닿지 못하는 곳에 있는 $s_d$의 경우..
  • 끝까지 가서 값을 구하는 것이 아니라 iterative하게 풀어서 빠르게 convergence한 값을 찾기
• 계산
  • $F(\theta_0 + \Delta \theta) = F(\theta_0) + \frac{F'(\theta_0)}{1!}(\Delta \theta) + \frac{F''(\theta_0)}{2!}(\Delta \theta)^2$ + ...
    식을 한번 미분한 값이 0이 되는 점들을 찾기 (local min, local max, saddle point)
  • 위의 식에서 2차 미분 이후 것들은 무시
  • 일반항을 구하면 $\Delta\theta = -\frac{F'(\theta_0}{F''(\theta_0)}$
• 그림으로 생각하면 2차 함수 형태가 목적함수와 기울기가 같은 점을 찾은 후 2차 함수의 1차 미분이 0이 되는 값의 x값으로 $\theta$값을 업데이트 해가는 모습이다.

Multivariate Newton Method

• 그러나... IK문제는 변수가 달랑 x만 있는 문제가 아니다.
  -> 함수도, 변수도 여러가지가 존재한다.
• root finding : by Jacobian
  -> update function에 1차미분 있기 때문에
• optimization : by Hessian
  -> update function에 2차미분 있기 때문에

Multivariate root finding problem

• $\theta=[\theta_0,\theta_1, ...]^T$
• $F(\theta)$ : nxn 행렬 -> $F_1(\theta_1, \theta_2,...)$, $F_2(\theta_1, \theta_2,...)$, ...각각을 row 로 가지는 행렬
• $F(\theta_{n+1}) = F(\theta_n) + J(\theta_n)(\Delta\theta) + O(\Delta \theta^2)$
  -> 한번 미분한 항이 jacobian으로 바뀐 형태
• $F(0_{n+1}) = 0$ 인 값을 찾아야 하기 때문에 일반항은 $\theta_{n+1}=\theta_n - \frac{J(\theta_n)}{F(\theta_n)}$

Multivariate optimization problem

• $F(\theta) = \sum(s_d-f(\theta_d))^2$
• $F(\theta_{n+1}) = F(\theta_n) + H_F(\theta_n)(\Delta \theta)$
• $\nabla F(\theta)=0$인 값을 찾아야 하기 때문에 일반항은 $\theta_{n+1} = \theta_n - \frac{\nabla F(\theta_n)}{H_F(\theta_n)}$

정리

• root finding은 error가 0이 되도록 하는 값을 찾는 것
• optimization은 $error^2$ 값의 합의 루트값이 최소가 되는 값을 찾는 것
• reciprocal : 2차미분의 값을 분모로 가지는 분수형태
  • reciprocal 값을 통해 함수의 curvature를 구할 수 있다. -> curvature 값을 통해 오차 줄이기!
    • curvature가 크면, 조금만 이동해야 오차가 적음
    • curvature가 작으면, 많이 이동해도 오차가 적어서 많이 이동 가능