최대엔트로피모델 파라메터 추정
29 Oct 2017 | Maximum Entropy Model
이번 글에서는 최대엔트로피모델(Maximum Entropy model)의 파라메터 추정을 살펴보도록 하겠습니다. 이 글은 기본적으로 이곳을 참고하였습니다. 그럼 시작하겠습니다.
모델 정의
최대엔트로피 모델은 다음과 같이 정의됩니다.
\[{ P }_{ \Lambda }(y|x)=\frac { { exp( }\sum _{ i }^{ }{ { \lambda }_{ i }{ f }_{ i }\left( x,y \right) } ) }{ \sum _{ y }^{ }{ { exp( }\sum _{ i }^{ }{ { \lambda }_{ i }{ f }_{ i }\left( x,y \right) } ) } }\]
위 식에서 $f$는 $x$와 $y$가 주어졌을 때 0 또는 1의 값을 반환하는 함수이며, $f_i(x,y)$는 자질벡터의 $i$번째 값을 나타냅니다. $λ$는 $f_i(x,y)$가 얼마나 중요한지 나타내는 가중치입니다. $Λ$는 그 요소가 ${λ_1, λ_2,…,λ_n}$인 가중치 벡터입니다.
최대우도추정
최대엔트로피모델 $P_Λ$에 대한 실제 데이터 분포(empirical distribution) $\widetilde{p}(x,y)$의 로그우도 함수는 다음과 같이 정의됩니다.
\[{ L }_{ \tilde { p } }=\sum _{ x,y }^{ }{ \tilde { p } \left( x,y \right) \log { { P }_{ \Lambda } } } \left( y|x \right)\]
자질벡터와 데이터가 주어졌을 때 위 로그우도 함수를 최대화하는 파라메터 $Λ$를 찾는 것이 목적이 됩니다. ${ L }_{ \tilde { p } }$는 1차 도함수가 0인 지점에서 극값을 가지므로, 우리가 구하고자 하는 미지수인 $λ_i$에 대해 각각 편미분을 하여 정리하면 다음과 같습니다.
\[\frac { \partial { L }_{ \tilde { p } } }{ \partial { \lambda }_{ i } } =\sum _{ x,y }^{ }{ \tilde { p } \left( x,y \right) { f }_{ i }\left( x,y \right) } -\sum _{ x }^{ }{ \tilde { p } \left( x \right) { P }_{ \Lambda }\left( y|x \right) { f }_{ i }\left( x,y \right) }\]
위 식에서 첫번째 항은 실제 데이터 분포에 대한 $f_i(x,y)$의 기대값입니다. 두번째 항은 모델 $P_Λ$에 대한 $f_i(x,y)$의 기대값입니다. 최적의 $λ_i$는 첫번째 항과 두번째 항이 정확히 같을 때 도출되므로, 최대우도추정은 실제 데이터의 확률분포와 모델이 예측하는 확률분포를 같게 만든다는 의미가 됩니다.
위 식은 딥러닝 모델의 손실함수인 크로스엔트로피(cross entropy)와 부호만 다를 뿐 정확히 같습니다. 크로스엔트로피는 두 확률분포 간 차이를 계산하는 함수입니다. 다시 말해 ‘우도의 최대화’와 ‘데이터-모델 두 확률분포 간 차이 최소화’가 본질적으로 동일한 의미를 지닌다는 겁니다.
파라메터 Λ 찾기
우리는 우도를 최대화하는 $Λ$를 구하고 싶습니다. 위 식을 보면 이러한 $Λ$를 구하려면 $P_Λ$를 알아야 합니다. 그런데 $P_Λ$를 계산하려면 $Λ$를 알아야 합니다. 돌고 도는 문제가 되는 셈이죠. 이같은 문제를 해결하기 위해 다음과 같이 새로운 파라메터 $Λ+Δ$를 설정해 보겠습니다.
\[\Lambda +\Delta =\left\{ { \lambda }_{ 1 }+{ \delta }_{ 1 },{ \lambda }_{ 2 }+{ \delta }_{ 2 },...{ \lambda }_{ n }+{ \delta }_{ n } \right\}\]
처음엔 우도를 최대화하는 $Λ$를 알 수 없으니 랜덤하게 값을 정해줍니다. $L_{ \tilde { p } }(Λ+Δ)-L_{ \tilde { p } }(Λ)$이 0 이상이라면 랜덤하게 정해준 $Λ$보다 $Λ+Δ$가 더 나은 파라메터라고 할 수 있을 것입니다. 몇 가지 수식 정리 과정을 거치면 $ L_{ \tilde { p } }(Λ+Δ)-L_{ \tilde { p } }(Λ)$의 하한(low-bound)은 다음과 같이 도출됩니다.
\[\begin{align*}
{ L }_{ \tilde { p } }(\Lambda +\Delta )-{ L }_{ \tilde { p } }(\Lambda )\ge &\sum _{ x,y }^{ }{ \tilde { p } \left( x,y \right) \sum _{ i }^{ }{ { { \delta }_{ i }f }_{ i }\left( x,y \right) } }+ \\ &1-\sum _{ x }^{ }{ \tilde { p } \left( x \right) { P }_{ \Lambda }\left( y|x \right) \sum _{ i }^{ }{ \left( \frac { { f }_{ i }\left( x,y \right) }{ \sum _{ i }^{ }{ { f }_{ i }\left( x,y \right) } } \right) } } exp\left( { \delta }_{ i }\sum _{ i }^{ }{ { f }_{ i }\left( x,y \right) } \right)
\end{align*}\]
위 식 우변을 $Β(Δ$|$Λ)$라고 치환해 보면 $L_{ \tilde { p } }(Λ+Δ)-L_{ \tilde { p } }(Λ)$의 하한은 $Β(Δ$|$Λ)$이 됩니다. $Λ$는 이미 랜덤하게 값을 정했기 때문에 이미 주어진 값입니다. 다시 말해 $Δ$만 알면 우도를 높일 수 있다고 기대할 수 있다는 이야기입니다. $Β(Δ$|$Λ)$는 1차 도함수가 0이 되는 지점에서 극값(최대값)을 가지기 때문에 우리가 구하고자 하는 미지수인 $δ_i$에 대해 각각 편미분을 하여 정리하면 다음과 같습니다.
\[\begin{align*}
\frac { \partial Β \left( \Delta |\Lambda \right) }{ \partial { \delta }_{ i } } =&\sum _{ x,y }^{ }{ \tilde { p } \left( x,y \right) { f }_{ i }\left( x,y \right) } \\ &-\sum _{ x }^{ }{ \tilde { p } \left( x \right) \sum _{ }^{ }{ { P }_{ \Lambda }\left( y|x \right) } { f }_{ i }\left( x,y \right) } exp\left( { \delta }_{ i }\sum _{ i }^{ }{ { f }_{ i }\left( x,y \right) } \right)
\end{align*}\]
위 식을 보면 exp 안에 있는 미지수 $δ_i$를 제외하면 모두 주어진 상수값이어서 $δ_i$를 구할 수 있습니다. 지금까지 설명한 내용을 알고리즘 형태로 정리하면 다음과 같습니다.
- $Λ={λ_1, λ_2,…,λ_n}$ 랜덤 초기화
- $∂Β/∂δ_i=0$인 $δ_i$ 계산
- $λ_i←λ_i+δ_i$
- $Λ$가 수렴할 때까지 2, 3 반복
이와 같은 iterative scaling algorithm은 딥러닝에서 많이 쓰이는 그래디언트 디센트와 유사하다는 생각이 듭니다. 그래디언트 디센트는 주어진 데이터와 파라메터를 가지고 손실(loss)에 대한 그래디언트를 구해, 그래디언트의 반대 방향으로 파라메터를 업데이트합니다. 다만 iterative scaling algorithm은 ‘우도 최대화’, 그래디언트 디센트는 ‘손실 최소화’가 목적이기 때문에 파라메터를 업데이트할 때 각각 덧셈, 뺄셈을 해준다는 점에서 다른 것 같습니다.
이번 글에서는 최대엔트로피모델(Maximum Entropy model)의 파라메터 추정을 살펴보도록 하겠습니다. 이 글은 기본적으로 이곳을 참고하였습니다. 그럼 시작하겠습니다.
모델 정의
최대엔트로피 모델은 다음과 같이 정의됩니다.
\[{ P }_{ \Lambda }(y|x)=\frac { { exp( }\sum _{ i }^{ }{ { \lambda }_{ i }{ f }_{ i }\left( x,y \right) } ) }{ \sum _{ y }^{ }{ { exp( }\sum _{ i }^{ }{ { \lambda }_{ i }{ f }_{ i }\left( x,y \right) } ) } }\]위 식에서 $f$는 $x$와 $y$가 주어졌을 때 0 또는 1의 값을 반환하는 함수이며, $f_i(x,y)$는 자질벡터의 $i$번째 값을 나타냅니다. $λ$는 $f_i(x,y)$가 얼마나 중요한지 나타내는 가중치입니다. $Λ$는 그 요소가 ${λ_1, λ_2,…,λ_n}$인 가중치 벡터입니다.
최대우도추정
최대엔트로피모델 $P_Λ$에 대한 실제 데이터 분포(empirical distribution) $\widetilde{p}(x,y)$의 로그우도 함수는 다음과 같이 정의됩니다.
\[{ L }_{ \tilde { p } }=\sum _{ x,y }^{ }{ \tilde { p } \left( x,y \right) \log { { P }_{ \Lambda } } } \left( y|x \right)\]자질벡터와 데이터가 주어졌을 때 위 로그우도 함수를 최대화하는 파라메터 $Λ$를 찾는 것이 목적이 됩니다. ${ L }_{ \tilde { p } }$는 1차 도함수가 0인 지점에서 극값을 가지므로, 우리가 구하고자 하는 미지수인 $λ_i$에 대해 각각 편미분을 하여 정리하면 다음과 같습니다.
\[\frac { \partial { L }_{ \tilde { p } } }{ \partial { \lambda }_{ i } } =\sum _{ x,y }^{ }{ \tilde { p } \left( x,y \right) { f }_{ i }\left( x,y \right) } -\sum _{ x }^{ }{ \tilde { p } \left( x \right) { P }_{ \Lambda }\left( y|x \right) { f }_{ i }\left( x,y \right) }\]위 식에서 첫번째 항은 실제 데이터 분포에 대한 $f_i(x,y)$의 기대값입니다. 두번째 항은 모델 $P_Λ$에 대한 $f_i(x,y)$의 기대값입니다. 최적의 $λ_i$는 첫번째 항과 두번째 항이 정확히 같을 때 도출되므로, 최대우도추정은 실제 데이터의 확률분포와 모델이 예측하는 확률분포를 같게 만든다는 의미가 됩니다.
위 식은 딥러닝 모델의 손실함수인 크로스엔트로피(cross entropy)와 부호만 다를 뿐 정확히 같습니다. 크로스엔트로피는 두 확률분포 간 차이를 계산하는 함수입니다. 다시 말해 ‘우도의 최대화’와 ‘데이터-모델 두 확률분포 간 차이 최소화’가 본질적으로 동일한 의미를 지닌다는 겁니다.
파라메터 Λ 찾기
우리는 우도를 최대화하는 $Λ$를 구하고 싶습니다. 위 식을 보면 이러한 $Λ$를 구하려면 $P_Λ$를 알아야 합니다. 그런데 $P_Λ$를 계산하려면 $Λ$를 알아야 합니다. 돌고 도는 문제가 되는 셈이죠. 이같은 문제를 해결하기 위해 다음과 같이 새로운 파라메터 $Λ+Δ$를 설정해 보겠습니다.
\[\Lambda +\Delta =\left\{ { \lambda }_{ 1 }+{ \delta }_{ 1 },{ \lambda }_{ 2 }+{ \delta }_{ 2 },...{ \lambda }_{ n }+{ \delta }_{ n } \right\}\]처음엔 우도를 최대화하는 $Λ$를 알 수 없으니 랜덤하게 값을 정해줍니다. $L_{ \tilde { p } }(Λ+Δ)-L_{ \tilde { p } }(Λ)$이 0 이상이라면 랜덤하게 정해준 $Λ$보다 $Λ+Δ$가 더 나은 파라메터라고 할 수 있을 것입니다. 몇 가지 수식 정리 과정을 거치면 $ L_{ \tilde { p } }(Λ+Δ)-L_{ \tilde { p } }(Λ)$의 하한(low-bound)은 다음과 같이 도출됩니다.
\[\begin{align*} { L }_{ \tilde { p } }(\Lambda +\Delta )-{ L }_{ \tilde { p } }(\Lambda )\ge &\sum _{ x,y }^{ }{ \tilde { p } \left( x,y \right) \sum _{ i }^{ }{ { { \delta }_{ i }f }_{ i }\left( x,y \right) } }+ \\ &1-\sum _{ x }^{ }{ \tilde { p } \left( x \right) { P }_{ \Lambda }\left( y|x \right) \sum _{ i }^{ }{ \left( \frac { { f }_{ i }\left( x,y \right) }{ \sum _{ i }^{ }{ { f }_{ i }\left( x,y \right) } } \right) } } exp\left( { \delta }_{ i }\sum _{ i }^{ }{ { f }_{ i }\left( x,y \right) } \right) \end{align*}\]위 식 우변을 $Β(Δ$|$Λ)$라고 치환해 보면 $L_{ \tilde { p } }(Λ+Δ)-L_{ \tilde { p } }(Λ)$의 하한은 $Β(Δ$|$Λ)$이 됩니다. $Λ$는 이미 랜덤하게 값을 정했기 때문에 이미 주어진 값입니다. 다시 말해 $Δ$만 알면 우도를 높일 수 있다고 기대할 수 있다는 이야기입니다. $Β(Δ$|$Λ)$는 1차 도함수가 0이 되는 지점에서 극값(최대값)을 가지기 때문에 우리가 구하고자 하는 미지수인 $δ_i$에 대해 각각 편미분을 하여 정리하면 다음과 같습니다.
\[\begin{align*} \frac { \partial Β \left( \Delta |\Lambda \right) }{ \partial { \delta }_{ i } } =&\sum _{ x,y }^{ }{ \tilde { p } \left( x,y \right) { f }_{ i }\left( x,y \right) } \\ &-\sum _{ x }^{ }{ \tilde { p } \left( x \right) \sum _{ }^{ }{ { P }_{ \Lambda }\left( y|x \right) } { f }_{ i }\left( x,y \right) } exp\left( { \delta }_{ i }\sum _{ i }^{ }{ { f }_{ i }\left( x,y \right) } \right) \end{align*}\]위 식을 보면 exp 안에 있는 미지수 $δ_i$를 제외하면 모두 주어진 상수값이어서 $δ_i$를 구할 수 있습니다. 지금까지 설명한 내용을 알고리즘 형태로 정리하면 다음과 같습니다.
- $Λ={λ_1, λ_2,…,λ_n}$ 랜덤 초기화
- $∂Β/∂δ_i=0$인 $δ_i$ 계산
- $λ_i←λ_i+δ_i$
- $Λ$가 수렴할 때까지 2, 3 반복
이와 같은 iterative scaling algorithm은 딥러닝에서 많이 쓰이는 그래디언트 디센트와 유사하다는 생각이 듭니다. 그래디언트 디센트는 주어진 데이터와 파라메터를 가지고 손실(loss)에 대한 그래디언트를 구해, 그래디언트의 반대 방향으로 파라메터를 업데이트합니다. 다만 iterative scaling algorithm은 ‘우도 최대화’, 그래디언트 디센트는 ‘손실 최소화’가 목적이기 때문에 파라메터를 업데이트할 때 각각 덧셈, 뺄셈을 해준다는 점에서 다른 것 같습니다.
Comments