Game Engineering 5

gb_leem·2023년 4월 25일
0

Game Engineering

목록 보기
3/8

Quasi-Newton Method for IK

Introduction

  • Newton Method 에서 2차 미분 형태
    • 장점 : converge more quickly
    • 단점 : 계산이 많다. -> Quasi-Newton method로 hessian을 근사하기!
  • Quasi-Newton's flow
    • optimal solution을 위한 초기값 설정
    • gradient (1차미분) 계산
    • Hessian (2차미분) 근사
    • 근사한 Hessian으로 solution update
    • iteration (위의 step 반복)
  • Quasi-Newton
    • 장점
      • computational 복잡도 감소
      • 빠른 convergence (for ill-condition)
      • initial guess에 less sensitive함
    • 단점
      • hessian 정확도 감소
      • 특정 문제에서 느린 convergence (IK의 경우 아크로바틱한 문제에서 어려움을 겪음)

Basics

1. Ill-conditioned problem

  • hessian의 condition number가 너무 커서 optimization이 어려운 상황
    • condition number of matrix : 가장 큰 eigen value와 가장 작은 eigen value간의 비율
      -> eigen value 간의 차이가 너무 클때
      -> 수렴치가 한 축으로만 쏠리는 현상 발생 (numerical unstable)
  • Ill-condition의 원인
    • poor scaling of varialbles
    • high-dimensional problem (파라메터가 너무 많을 때)
    • objective function 자체의 문제
  • 해결 방안
    • appropriate variable scaling
    • preconditioning
    • use optimization algorithm

2. Definite Matrix

  • 의미
    • Positive, negative, indefinite 한 지 미리 구별하는 방법
    • objective function의 curvature를 알 수 있다.
      -> convergence and stability 파악 가능
  • 구하는 방법
    xx의 transpose : xTx^T, n-dimensional zero-vector : 0
    n x n symmetic real matrix M에 대하여
    Positive-definite : xTMx>0x^TMx>0
    Positive-semidefinite, non-negative-definite : xTMx0x^TMx\ge0
    negative-definite : xTMx<0x^TMx<0
    negative-semidefinite, non-positive-definite : xTMx0x^TMx\le0
  • 개념
    • Hessian Matrix of function 이 점 p에서 positive definite한 경우 그 function은 p근처에서 convex 하다
      -> iterative 하면 해를 찾을 수 있다는 의미!
  • 특징
    • positive-definite matrix
      1) all positive eigen value
      2) invertible
      3) symmmetric
      4) convex / unique global minimum -> converge to unique point
    • negative-definite matrix
      1) all negative eigen value
      2) invertible
      3) symmetric
      4) concave / unique global maximum -> converge to unique point
    • indefinite matrix
      1) negative and positive eigen value
      2) symmetric (real matrix)

3. Secant Method

  • 개념
    • 1차 미분을 구하기 어려울 때, 1차 미분의 유사값을 찾는 방법
    • root finding algorithm (Newton-method 랑 유사한 방식)
    • 이전의 두 점을 가지고 미분 값을 찾는 방법
      f(x)ΔyΔx=f(x+Δ)f(x)(x+Δ)xf'(x)\approx \frac{\Delta y}{\Delta x}=\frac{f(x+\Delta)-f(x)}{(x+\Delta)-x} 에서 \approx가 secant method의 의미

4. Frobenius norm (Euclidean norm)

  • 개념
    • matrix의 size를 구하기 위한 matrix norm
  • 정의
    AF=i=1mj=1naij2||A||_F = \sqrt{\sum_{i=1}^m\sum_{j=1}^n|aij|^2}
  • 특징
    • trace property와 관련이 있다.
      • trace property : matrix의 diagonal을 더한 값
    • trace of square matrix A : tr(A)tr(A)
    • conjugate transpose of A : AHA^H
      squared Frobenius norm을 다시 정의하면
      AF=tr(AAH)||A||_F = \sqrt{tr(AA^H)} (real matrix에서는 AH=ATA^H=A^T)

5. Lagrane Multiplier

  • 개념
    • 제한이 걸려있는 상황에서 최적화 문제를 푸는 방법
    • 그림에서
      • f(x,y)f(x,y) 가 objective function
      • g(x,y)g(x,y) 가 constraint
      • f(x,y)=d1f(x,y) = d_1이 제한 상황에서 maximum 구한 것

  • 수식
    • Lagrange function : L(x,y,λ)L(x,y,\lambda)
    • L(x,y,λ)=f(x,y)+λg(x,y)L(x,y,\lambda) = f(x,y) + \lambda g(x,y)
      -> λ\lambda가 Larange multiplier
    • 위의 식을 편미분 하고 각 식들이 0이 되는 값을 연립해서 풀기

Quasi-Newton Method

  • 목표

    • scalar-valued function의 minimum or maximum 을 구하기
    • = search for zero of the gradient of that function
  • 수식
    J[f(x)]=H[f(x)]J[\nabla f(x)]=H[f(x)] (g=f)g=\nabla f)
    Newton method에서의 문제 : θn+1=θnF(θn)HF(θn)\theta_{n+1}=\theta_n-\frac{\nabla F(\theta_n)}{H_F(\theta_n)}
    -> Hessian을 쉽게 푸는 것이 목적!

  • 과정 (Hessian 간단하게 하기)

    • secant equation (Taylor series)
      F(θn+1)=F(θn)+F(θn)(Δθ)+O(Δθ2)F(\theta_{n+1)}=F(\theta_n)+\nabla F(\theta_n)(\Delta \theta)+O(\Delta \theta^2)
      -> 미분
      F(θn+1)=F(θn)+HF(θn)(Δθ)\nabla F(\theta_{n+1})=\nabla F(\theta_n)+H_F(\theta_n)(\Delta \theta)
      -> HF(θn)(Δθ)=F(θn+1)F(θn)H_F(\theta_n)(\Delta \theta)=\nabla F(\theta_{n+1})-\nabla F(\theta_n)
      -> θn\theta_nθn+1\theta_{n+1}에서 Hessian의 값 차이가 없다면..
      BF(θn)(Δθ)F(θn+1)F(θn)B_F(\theta_n)(\Delta \theta)\approx \nabla F(\theta_{n+1})-\nabla F(\theta_n) (BB는 Hessain 근사)
  • Quasi-Newton steps
    1) Δθ=BF1(θn+1)(F(θn+1)F(θn))\Delta \theta = B_F^{-1}(\theta_{n+1})(\nabla F(\theta_{n+1})-\nabla F(\theta_n)) 풀기
    2) learning rate tnt_n 결정
    3) update θn+1=θn+tnΔθn\theta_{n+1}=\theta_n+t_n\Delta\theta_n

  • Quasi-Newton 방식들

    • 지금까지의 방식들 중 가장 좋은 방식은 BFGS
    • Broyden, DFP, SR1 등이 있음

Broyden-Fletcher-Goldfarb-Shanno Method

Broyden Method

  • 목적: Bn+1B_{n+1}BnB_n 간의 Frobenius norm을 최소화 하기
    -> minBn+1BnF2=AF2=tr(AAT)min||B_{n+1}-B_n||_F^2 = ||A||_F^2=tr(AA^T)
  • subject to (조건)
    BF(θn+1)Δθn=F(θn+1)F(θn)B_F(\theta_{n+1})\Delta\theta_n=\nabla F(\theta_{n+1})-\nabla F(\theta_n)
    -> BF(θn+A)Δθn=F(θn+1)F(θn)B_F(\theta_{n}+A)\Delta\theta_n=\nabla F(\theta_{n+1})-\nabla F(\theta_n)
    -> F(θn+1)F(θn)BF(θn)ΔθnAΔθn=0\nabla F(\theta_{n+1})-\nabla F(\theta_n)- B_F(\theta_{n})\Delta\theta_n - A\Delta\theta_n = 0
  • 위의 문제는 제한 조건이 있는 문제이므로
    L(A,λ)=tr(AAT)+λT(F(θn+1)F(θn)BF(θn)ΔθnAΔθn)L(A,\lambda)=tr(AA^T)+\lambda^T(\nabla F(\theta_{n+1})-\nabla F(\theta_n)- B_F(\theta_{n})\Delta\theta_n - A\Delta\theta_n)
    -> 풀면 A=12λΔθnTA=\frac{1}{2}\lambda\Delta \theta_n^T
  • 정리
    F(θn+1)F(θn)BF(θn)ΔθnAΔθn=0\nabla F(\theta_{n+1})-\nabla F(\theta_n)- B_F(\theta_{n})\Delta\theta_n - A\Delta\theta_n = 0 식과
    A=12λΔθnTA=\frac{1}{2}\lambda\Delta \theta_n^T 식을 연립
    A=(F(θn+1)F(θn)BnΔθn)ΔθnTΔθnTΔθnA = (\nabla F(\theta_{n+1})-\nabla F(\theta_n)-B_n\Delta\theta_n)\frac{\Delta\theta_n^T}{\Delta\theta_n^T\Delta\theta_n}
    Frobenius (trace property) 에 의하여 Bn+1Bn=AB_{n+1}-B_n = A
    -> 결론 : Bn+1=Bn+(F(θn+1F(θn)BnΔθn)ΔθTΔθnΔθnTB_{n+1} = B_n + \frac{(\nabla F(\theta_{n+1}-\nabla F(\theta_n)-B_n\Delta\theta_n)}{\Delta\theta^T\Delta\theta_n}\Delta\theta_n^T

0개의 댓글