본문 바로가기
Enginius/Machine Learning

Representer Theorem

해리s 2015. 11. 6. 18:17

이번 포스팅은 분류와 회귀, classification과 regression중에서 regression에 representer theorem을 적용하는 것에 대한 것이다. 여기서 한가지 집고 넘어가고 싶은 것은 representer theorem 자체는 위의 두 문제 모두 적용될 수 있는 알고리즘이라는 것이다. 


1. Problem Setting


먼저 우리가 갖고 있는 데이터가 다음과 같다고 하자. 

$$ (x_1, y_1), \ (x_2, y_2), \ \cdots \ , \ (x_m, y_m)  \in X \times R $$

그리고 '$X$'의 두 원소의 product space에서 정의된 kernel이 있다고 하자. 

$$ k: X \times X \to R \ \ \ \ (x, x') \mapsto k(x, x') $$

이 kernel 함수를 통해서 우리는 Gram matrix 혹은 kernel matrix를 만들 수 있다. 

$$ K := (k(x_i, x_j))_{ij} \in R^{m \times m} $$


Associated Feature Space

'$C^X$'를 '$X \to C$'인 함수들이 살고 있는 공간이라고 하자. 그리고 '$X \to C^X$'의 mapping을 '$\phi$'라 하자. 헛갈리지말자. '$\phi$'가 살고 있는 공간이 '$C^X$'가 아니다. '$X$'를 '$X$'에서 정의된 함수로 연결해주는 함수이다. 

$$ \phi: X \to C^X, x \mapsto k(\cdot, x) $$


이 함수들이 살고 있는 공간을 일종의 linear space라 한다면, 우리는 이 공간에서 살고 있는 임의의 함수 '$f$'와 '$g$'를 다음과 같이 표현할 수 있다.

$$ f(\cdot) = \sum_{i=1}^m \alpha_i k(\cdot, x) , \\ g(\cdot) = \sum_{j=1}^{m'} \beta_j k(\cdot, x'_j)$$

그리고 이 두 함수, 혹은 원소의 내적 (dot product)를 다음과 같이 정의한다. 

$$ <f, g> := \sum_{i=1}^m \sum_{j=1}^{m'} \alpha_i \beta_j k(x_i, x'_j). $$


이렇게 정의할 경우 몇 가지 재밌는 성질들이 유도된다. 

1. '$ <k(\cdot, x), f> = f(x) $'

여기서 '$k(\cdot, x)$'를 representer of evaluation이라 한다. 


2. '$ <k(\cdot, x), k(\cdot, x')> = k(x, x') $'


3. '$ k(x, x') = <\phi(x), \phi(x')> $'


위의 성질 때문에, 임의의 kernel로 형성되는 함수들의 공간을 reproducing kernel Hilbert space (RKHS)라고 한다. Hilbert space는 원소들과 이 원소들의 내적이 정의된 공간을 의미한다. 


2. The Representer Theorem


우리에게 임의의 nonempty set '$X$'가 있고, positive definite한 kernel '$k(\cdot)$'이 있다고 하자. 그리고 학습 데이터가 다음과 같이 주어졌다고 하자. 

$$ (x_1, y_1), \ (x_2, y_2), \ \cdots \ , \ (x_m, y_m) \in X \times R $$

또한 strictly increasing function '$g(\cdot)$'과 cost function '$C: (X \times R^2)^m \to R \cup \{\infty\}$'이 있다고 하자. 그리고 우리가 찾고자 하는 함수가 다음의 꼴로 표현된다고 하자. 

$$ F = \{ f \in R^X | f(\cdot) = \sum_{i=1}^\infty \beta_i k(\cdot, z_i) \} \\ \| \sum_{i=1}^{\infty} \beta_i k(\cdot, z_i) \|^2_2 = \sum_{i=1, j=1}^{\infty} \beta_i \beta_j k(z_i, z_j) $$

모든 가능한 조합이라고 생각하면 된다. 혹은 vector space를 생각해보면 선형 조합에 닫혀있으므로 모든 원소라고 생각해도 된다. 그 뒤의 식인 이 공간에서 정의된 내적의 정의이다. 

자 여기서부터가 중요하다. 

임의의 '$f \in F$'에 대해서 아래 최적화 문제를 푼다고 생각해보자. 

$$ c((x_1, y_1, f(x_1), \ \cdots \, \ (x_m, y_m, f(x_m)) ) + g(\| f \|_2^2) $$

그러면 이 문제의 solution은 다음의 꼴로 표현될 수 있다. 

$$ f(\cdot) = \sum_{i=1}^m \alpha_i k(\cdot, x_i) $$

>> The significance of the theorem is that it shows that a whole range of learning algorithms have optimal solutions that can be expressed as expansions in terms of the training examples.



3. Applications of Representer Theorem


구슬이 서말이래도 꿰어야 보배라고, 이제 실제로 써먹어보자. 두 가지 문제를 풀어볼 것이다. 

첫 번째는 일반적인 regression 문제이다. 즉 입력과 출력에 해당하는 학습 데이터를 주고, 이 데이터들을 잘 표현하는 함수를 찾는 것이다. 두 번째는 문제는 조금 복잡한 문제로, 이 함수가 특정 점들과는 가깝고, 다른 점들과는 멀어지게 해보자. 결론부터 써보면 아래와 같다. 


Representer theorem이 멋진 이유는 비선형 함수를 찾는 문제를 Convex quadratic programming으로 바꾼다는 것이다! 그럼 기존의 convex solver를 쓸 수 있다. 또한 negative data를 고려하는 문제가 indefinite QP이므로 이는 sequential QP와 Newton KKT로 풀수 있다. (모두 아래 매트랩 파일에 있다.)


동영상은 다음과 같다. 


Matlab code


1. main.m


2. buttonDownCallback.m


3.keyDownListener.m


4. lfnd.m


5. kernel_se.m






'Enginius > Machine Learning' 카테고리의 다른 글

Boosting Methods  (0) 2015.12.02
Practical usage of Representer theorem  (5) 2015.11.07
A Reduction of the Elastic Net to Support Vector Machines  (0) 2015.10.27
An Introduction to Variable and Feature Selection  (0) 2015.10.24
Markov Chain  (0) 2015.10.14

'Enginius/Machine Learning' Related Articles

티스토리툴바