BJJ - 다시 수련을 시작하며

근 1년 가까이 주짓수 수련을 쉬다가 최근 다시 시작했다.

다행히 집에서 버스 타고 10분 거리에 최근 도장이 생겼다.

그래서 예전과 달리 거리에 대한 부담도 없고, 애들 다 씻기고 생각날 때 휙 다녀올 수 있어 너무 좋다.

너무 쉬어서 다시 폼이 올라오려면 시간이 좀 걸리겠지만, 할 수 있다는 것 자체가 너무 기쁘다.

앞으로 하프 가드와 압박 패스를 주로 사옹하며 다듬을 예정이다.

물론 사범님이 가르쳐 주시는 기술도 꾸준히 다듬어야지.

Basis Spline

1. Basis Spline (B-Spline)이란?

 Spline을 영어 사전에서 찾아보면 다음과 같다.

Definition of SPLINE

1

:  a thin wood or metal strip used in building construction

2

:  a key that is fixed to one of two connected mechanical parts and fits into a keyway in the other;also :  a keyway for such a key

3

:  a function that is defined on an interval, is used to approximate a given function, and is composed of pieces of simple functions defined on subintervals and joined at their endpoints with a suitable degree of smoothness

 즉, 문자 그대로 어떤 두 지점을 잇는 어떤 것을 의미하는데, 커브 생성에 사용되는 spline도 같은 의미이다. (앞의 인용을 보면 3번 정의이다.)
 업계(금융 수치 해석)에서 많이 쓰는 spline은 cubic spline이라고 하여 두 점을 잇는 함수가 다음과 같이 3차 함수의 모양을 갖는다.

$ f(x) = ax^3 + bx^2 + cx + d $

 그래서 각 데이터 포인트를 연결하는 $a$에서 $d$까지의 계수를 찾아 부드러운 곡선으로 각 점을 잇는다. Basis-Spline(이하 B-Spline)은 조금 더 일반화 된 방식의 spline인데, 말 그대로 각 점을 정의된 Basis function으로 연결한다는 의미이다.
 (참고로 이 포스트의 내용 및 그림 등은 http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/ 이 사이트를 매우 많이 참고했다.)

 B-spline의 경우 knots, parameter, control point, data point, degree라는 개념을 짚고 넘어가야 한다.

• Data point : interpolation이나 추정 대상이 되는 점을 의미한다. 함수 $y = f(x)$에서 x를 의미한다.
• Parameter : 어떤 data point가 주어졌을 때 그 data point를 B-spline에 적용할 수 있게 쪼갠 값이다. 이 값을 구하기 위해 data point를 균등하게 자를 수도 있고, 그 외 현란한 방법으로 자를 수 도 있다.
• Knots : knot은 말 그대로 하면 매듭이란 뜻으로 풀이가 된다. 여기서 knot은 basis function을 정의하는 기준 점 정도로 이해할 수 있다. Knot의 경우 parameter를 평균 내거나, parameter와 상관 없이 구간을 일정하게 쪼개기도 한다.
• Control point : 이게 설명하기가 애매하다. 뒤에 나오겠지만, interpolation을 위해 사용되는 basis function에 곱해져 커브 상의 값을 가지고 오는데 쓰인다.
• Degree : basis function의 차수를 의미한다. 3이면 cubic-spline과 동일하다.

 B-spline의 curve 추정 함수는 다음과 같다.

$ C(u) = \sum^{n}_{0} N_{i, d}(u)Q_{i} $

 여기서 C가 추정하고자 하는 커브 상의 값이고, $n$은 data point의 갯수에서 하나를 뺀 값이다. 즉, $n+1$이 data point의 수가 된다. 그리고 $d$가 degree를 말하고 $Q$가 control point이다. 즉, data point 수 만큼의 basis function과 control point 값을 곱하여 합하면 추정하는 값이 나온다는 의미이다.

 Basis function ($N_{i, d}(u)$)는 다음과 같이 회귀적으로 정의한다.

$ N_{i, 0}(u) = \left \{ \begin{array}{ll} 1, \mbox{if $u_{i} \leq u < u_{i+1}$} \\ 0, \mbox{otherwise}  \end{array} \right.  $

$ N_{i, d} = \frac{u - u_{i}}{u_{i+p} - u_{i}} N_{i,p-1}(u) + \frac{u_{i+p+1} - u}{u_{i+p+1} - u{i+1}} N_{i+1,p-1}(u) $

 Degree가 0이면 찾고자 하는 값의 인수가 해당 knot에 해당할 경우 1, 아니면 0을 넘겨주고, 이후에는 회기 함수를 이용하여 basis function의 값을 구한다. 그리고 그 값을 이용하여 커브 상의 값을 추정한다.

2. 구현하기

 B-Spline을 구현할 때 다음과 같은 순서로 코드를 제작하였다.

1. Data point, 각 data point에 해당하는 결과 값, degree를 받아들임
2. Data point를 이용하여 parameter 만들기
3. Knot의 모음임 knot vector 만들기
4. Global interpolation 또는 Global fitting 방식을 쓸 것인지에 따라 control point 구하기
5. 값이 들어오면 추정 값을 넘겨주기

 이렇게 크게 다섯 개의 틀로 볼 수 있다.

 각각의 단계를 조금씩만 더 디벼보자. (조금만 디벼보자. 깊이는 나도 모르겠다. ㅎㅎ)

 2번의 경우 parameter를 생성하기 위해 데이터 구간을 균등하게 자르는 방법과, Chord length method, Centripetal method가 있다. 이 중 당연하게도(?) 가장 구현이 간단한 Uniformly spaced method(균등하게 자르기)를 이용하였다.  각 방식에 따라 추정하는 커브의 모양이 달라지는데, 다음의 퍼온 그림을 참고하자.

 3번의 경우 parameter와 상관 없이 knot을 구간의 갯수만큼 1/n하여 자르는 방법과 parameter를 평균내는 방법이 있다. 이 중 후자의 방법을 선택했다. 참고한 문서에서는 전자의 경우 chord length 등을 사용하면 결과가 제대로 안 나올 수 있다는 설명이 있다. (물론 쓰진 않지만. ㅎㅎ)
 knot을 만드는 과정을 식으로 표현하면 다음과 같다.

 여기서 p가 degree이다. knot의 경우 'data의 수(n+1) + degree(p) + 1'개 만큼 생성을 한다. 그리고 degree까지의 knot은 0(또는 data point 구간의 첫 번째 값)으로 지정하고, 'knot의 갯수(m+1) - degree(p) - 1'부터 마지막 knot은 1(또는 data point 구간의 마지막 값)으로 지정한다.

 그리고 마지막으로 control point를 구해주는데, global interpolation과 global fitting 두 가지 방식이 있다. Global interpolation의 경우 주어진 data point를 모두 통과하도록 제한을 두어 control point를 구하는 방식이고, global fitting은 least square 방식으로 커브의 에러를 최소화 시키는 방식으로 구하는 방식이다.
 Global interpolation은 다음의 식을 앞서 설명한 LU decomposition을 이용하여 푼다.

$ \mathbf{NQ=D}$

여기서 $\mathbf{N}$은 basis function의 $n\times n$ matrix이고 $D$는 data point vector 또는 matrix, $Q$는 control point vector 또는 matrix이다.
 Global fitting의 경우 다음의 식을 최소화 하도록 푼다.

$ E = 1/2 \sum^{m}_{k = 0} | \sum^{n}_{j=0}N_{j,d}\mathbf{Q_{j}} - \mathbf{D_{k}}|^2 $

 이 least square 식을 풀어 matrix 형태로 풀어내면 다음과 같은 system을 푸는 문제로 만들 수 있다.

$\mathbf{N^{T}NQ=N^{T}D}$

3. 결과 예제

 결과를 테스트 해보기 위해 간단하게 standard normal distribution의 PDF를 추정하도록 해보자. 여기서 degree는 3으로 하였으며, 데이터 포인트 갯수를 20개와 50로 나누어봤다. 그리고 interpolation과 fitting을 사용하여 어떤 차이가 있는지 보자.

N+1=50, D=3, Interpolation

N+1=50, D=3, Fitting

 100개의 data를 추정하는데 50개의 data point를 사용한 결과인데, x표가 closed form이고 선이 생성된 커브, +가 사용된 data point이다. point 수가 많기 때문에 fitting과 interpolation이 큰 차이를 보이지 않으나, fitting이 약간의 에러를 보여준다.

N+1=20, D=3, Interpolation

N+1=20, D=3, Fitting

 Data point를 20개로 줄이고 100개의 점을 추정할 경우, interpolation과 fitting이 차이를 보인다. 하지만 여기서 생각해봐야 할 것은 대상이 되는 커브 자체가 매우 부드러운 함수이기 때문에 상황에 따라서는 어떤 것이 원본치에 가까우냐는 이견의 여지가 있을 수 있다는 것이다.  (물론 datapoint 갯수가 더 줄어들면 fitting 방식의 커브가 더 많이 꺾이기도 한다.)

끝.

LU Decomposition

1. LU Decomposition이란?

 NxN 인 square matrix $ \mathbf{A}$가 있다. 이 matrix를 쪼갤 수 있는 방법은 매우 많다. 예를 들어 Cholesky decomposition을 통하여 $\mathbf{LL^{T}}$ 형식으로 lower triangle과 그 transpose로 쪼갤 수 있다. LU decomposition은 square matrix를 lower triangle과 upper triangle 두 부분으로 나누는 기법을 말한다.

$ \mathbf{A = LU} $

 예를 들어 $\mathbf{A}$라는 matrix가 3x3이라고 하면 이 matrix를 다음과 같이 나눌 수 있다.

$
\left( \begin{array}{ccc}  l_{1,1} & 0 & 0 \\ l_{2,1} & l_{2,2} & 0 \\ l_{3,1} & l_{3,2} & l_{3,3} \end{array} \right)
\left( \begin{array}{ccc}  u_{1,1} & u_{1,2} & u_{1,3} \\ 0 & u_{2,2} & u_{2,3} \\ 0 & 0 & u_{3,3} \end{array} \right)  =
\left( \begin{array}{ccc}  a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \end{array} \right) $

 이 matrix를 풀어보면 다음과 같이 쓸 수 있다.

$
\left( \begin{array}{ccc} l_{1,1}u_{1,1} & l_{1,1}u_{1,2} & l_{1,1}u_{1,3} \\
l_{2,1}u_{1,1} & l_{2,1}u_{1,2} + l_{2,2}u_{2,2} & l_{2,1}u_{1,3} + l_{2,2}u_{2,3} \\
l_{3,1}u_{1,1} & l_{3,1}u_{1,2} + l_{3,2}u_{2,2} & l_{3,1}u_{1,3} + l_{3,2}u_{2,3} + l_{3,3}u_{3,3} \end{array} \right)  =
\left( \begin{array}{ccc}  a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \end{array} \right) $

이렇게 보면 찾아야 하는 값은 $ 3 \times 3 + 3$개인데 식은 $3\times 3$개만 있는 상황이 된다. 즉 답이 하나가 아닐 수 있다는 의미이다. 이 때 자주 쓰이는 알고리듬이 'Crout's Method' 이다. 실제 내용이나 구현 방법은 링크 또는 Numerical Recipe라는 책을 찾아보면 자세히 나와있다.
 구현에 따라 $ \mathbf{A=LU}$가 아니라 $\mathbf{PA=LU}$의 형식으로 답을 구하는데 여기서 $\mathbf{P}$는 permutation matrix이고, orthogonal이므로 $\mathbf{A=P^{T}LU}$로 다시 역산할 수 있다.

2. 어디에 쓰는가. 

 LU Decomposition을 사용하면 $\mathbf{Ax=b}$ 형태의 linear system을 쉽게 풀 수가 있다. 일반적으로 이런 식을 풀기 위해 Gauss-Jordan Elimination을 사용한다. LU Decomposition으로 푸는 방식은 다음과 같다.

$ \mathbf{ Ax=(LU)x=L(Ux)=b} $

와 같이 식을 쓰게 되면 우선

$ \mathbf{ Ly=b }$ 

에서 $\mathbf{y}$를 Forward substitution방식으로 풀고,

$ \mathbf{Ux=y}$

식을 backward substitution으로 풀 수 있다.