이번 글에서는 한국어의 의미역(theta role)에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 정연주 선생님 강의와 이선웅 경희대 교수님이 쓰신 ‘한국어 문법론의 개념어 연구’를 정리했음을 먼저 밝힙니다.

의미역의 정의

의미역이란 명사구가 서술어와 관련하여 지니는 의미 기능을 가리킵니다. 다시 말해 서술어가 나타내는 사태 속에서 논항이 나타내는 참여자가 수행하는 역할의 유형 혹은 논항이 서술어에 대해 갖는 의미상의 자격, 역할, 지위 따위를 나타냅니다. 예를 들어 보겠습니다.

가. 학교에서 운동회를 개최하였다.

나. 이 도시의 명칭은 그 전설에서 유래하였다.

위 예시에서 논항인 ‘학교에서’와 ‘그 전설에서’는 동일한 격조사(-에서)를 쓰고 있지만 서술어 와 관련하여 상이한 의미 기능을 하고 있습니다. 이 때 ‘학교에서(장소)’와 ‘그 전설에서(출발점)’가 가지는 의미기능을 의미역이라고 합니다.

한국어 의미역의 종류

한국어 자료를 대상으로 의미역의 종류에 대해 가장 정밀하게 기술한 논의는 홍재성 외(2002)라고 합니다. 이 연구를 정리/보완한 이선웅(2012)의 논의는 다음과 같습니다.

행위주역(Agent) : 동사가 행위를 표현할 경우 그 행위를 지배하는 논항이 갖는 의미역

피행위주역(Patient) : 동사가 행위를 표현할 경우 그 행위로 인해 영향을 입는 논항이 갖는 의미역

경험주역(Experiencer) : 인지(cognition), 지각(perception), 감정(emotion)을 나타내는 용언의 경우 그 현상의 경험 주체가 되는 논항이 갖는 의미역

동반주역(Companion) : 독립적으로 역할을 하지 못하고 다른 의미역, 즉 대개 행위주나 대상을 보조하여 그것과 같은 역할을 하는 주체를 나타내는 논항이 갖는 의미역

대상역(Theme) : 행위나 과정의 영향을 받지만 그 과정을 지배하지는 못하는 논항. 즉 위치, 조건, 상태가 바뀌거나 주어진 상태나 위치에 있는 참여자들을 나타내는 논항이 갖는 의미역

장소역(Location) : 행위주나 대상이 위치하는 물리적 혹은 추상적 시공간을 나타내는 논항이 갖는 의미역

도착점역(Goal) : 동사가 표현하는 사건이 물리적 이동을 포함하고 있을 경우 그 끝점, 추상적인 행위나 태도의 의미를 포함하고 있을 경우 그 지향점을 표현하는 논항이 갖는 의미역

결과상태역(Resultant State) : 동사가 인물의 자격 또는 물질의 성질이나 용도의 변화를 기본 의미로 가질 때, 그러한 변화의 결과를 나타내는 논항이 갖는 의미역

출발점역(Source) : 동사가 이동이나 변화의 의미를 포함하고 있을 경우 물리적, 추상적 시작 지점을 표현하는 논항이 갖는 의미역

도구역(Instrument) : 행위, 이동의 의미를 표현하는 동사의 경우 그 방편이나 경로, 재료를 나타내는 논항이 갖는 의미역

영향주역(Effector) : 동사가 나타내는 사건(행위, 상태)을 비의도적으로 (주로 ‘이동’이나 ‘위치’에 의해)유발하는 논항이 갖는 의미역

기준치역(Criterion) : 평가의 의미를 가진 동사의 경우 평가되는 대상에 상대하여 평가의 기준이 되는 논항이 갖는 의미역

내용역(Contents) : 발화동사, 사유동사 등의 절 논항이 갖는 의미역

경로역(Path) : 출발점과 도착점을 함께 명세하는 논항이 지닌 의미역

자격역(Eligibility) : 술어가 의미하는 어떤 행위의 지속시간동안 어떤 자격으로 그 행위가 이루어졌는지를 나타내는 의미역

분석 예시

예문을 보겠습니다.

태풍(행위주역)이 그 마을 전체에 피해를 입히고 지나갔다

아버지(행위주역)가 신문(피행위주역)을 읽으신다.

나(경험주역)는 이곳이 춥다.

나는 애인(동반주역)과 시내에서 만났다.

동생이 음악(대상역)을 듣는다.

진이(대상역)는 착하다.

김 씨는 이 공장(장소역)에서 일한다.

아버지가 아들을 서울(도착점역)로 보내었다.

감독이 골키퍼를 김병지(결과상태역)로 바꾸었다.

물이 얼음(결과상태역)으로 변했다.

그 사람은 러시아(출발점역)에서 왔습니다.

그녀는 늘 손(도구역)으로 입을 가리고 웃습니다.

철수가 길을 가다가 전봇대(영향주역)에 부딪혔다.

전봇대가 태풍(영향주역)에 쓰러졌다.

철수는 영희(기준치역)와 닮았다.

동생이 오늘 시험을 본다고(내용역) 말했다.

광화문에서 서울역까지의(경로역) 행진

철수의 떠돌이(자격역) 생활

선택제약

서술어와 논항이 아무렇게나 결합하는 것은 아닙니다. 서술어가 어떤 의미를 가진 요소를 논항으로 선택하는지에서 보이는 제약을 선택제약이라고 합니다. 예컨대 다음 예문은 의미상 비문입니다.

*소나무가 웃는다.

*나는 권력을 존경한다.

위 예문이 비문이 되는 이유는 ‘웃다’라는 서술어는 유정명사를 주어로, ‘존경하다’는 인성명사를 목적어로 취하기 때문입니다. 같은 의미를 지니는 서술어라도 의미가 다른 논항을 취하는 경우도 있습니다. 예문을 보겠습니다.

눈을 감다.

입을 다물다.

‘감다’와 ‘다물다’는 모두 ‘닫다’는 공통된 뜻을 가지고 있지만 이들이 각각 취하는 목적어 명사구의 종류가 다른 걸 확인할 수 있습니다.

이번 글에서는 말뭉치로부터 토픽을 추출하는 토픽모델링(Topic Modeling) 기법 가운데 하나인 잠재디리클레할당(Latent Dirichlet Allocation, LDA)에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

모델 개요

LDA란 주어진 문서에 대하여 각 문서에 어떤 주제들이 존재하는지에 대한 확률모형입니다. LDA는 토픽별 단어의 분포, 문서별 토픽의 분포를 모두 추정해 냅니다. LDA의 개략적인 도식은 다음과 같습니다.

우선 LDA는 특정 토픽에 특정 단어가 나타날 확률을 내어 줍니다. 예컨대 위 그림에서 노란색 토픽엔 gene이라는 단어가 등장할 확률이 0.04, dna는 0.02, genetic은 0.01입니다. 이 노란색 토픽은 대략 ‘유전자’ 관련 주제라는 걸 알 수 있네요.

이번엔 문서를 보겠습니다. 주어진 문서를 보면 파란색, 빨간색 토픽에 해당하는 단어보다는 노란색 토픽에 해당하는 단어들이 많네요. 따라서 위 문서의 메인 주제는 노란색 토픽(유전자 관련)일 가능성이 큽니다. 이렇듯 문서의 토픽 비중 또한 LDA의 산출 결과물입니다.

위 그림 우측에 있는 ‘Topic proportions & assignments’가 LDA의 핵심 프로세스입니다. LDA는 문서가 생성되는 과정을 확률모형으로 모델링한 것이기 때문인데요. 글쓰기를 예로 들면 이렇습니다.

우선 글감 내지 주제를 정해야 합니다. 이후 실제 글을 작성할 때는 어떤 단어를 써야할지 결정합니다. LDA도 마찬가지입니다. 우선 말뭉치로부터 얻은 토픽 분포로부터 토픽을 뽑습니다. 이후 해당 토픽에 해당하는 단어들을 뽑습니다. 이것이 LDA가 가정하는 문서 생성 과정입니다.

이제 반대 방향으로 생각해보겠습니다. 현재 문서에 등장한 단어들은 어떤 토픽에서 뽑힌 단어들일까요? 이건 명시적으로 알기는 어렵습니다. 말뭉치에 등장하는 단어들 각각에 꼬리표가 달려있는 건 아니니까요.

그런데 LDA는 이렇게 말뭉치 이면에 존재하는 정보를 추론해낼 수 있습니다. LDA에 잠재(Latent)라는 이름이 붙은 이유입니다. LDA의 학습은 바로 이러한 잠재정보를 알아내는 과정입니다.

모델 아키텍처

LDA의 아키텍처, 즉 LDA가 가정하는 문서생성과정은 다음과 같습니다. $D$는 말뭉치 전체 문서 개수, $K$는 전체 토픽 수(하이퍼 파라메터), $N$은 $d$번째 문서의 단어 수를 의미합니다. 네모칸은 해당 횟수만큼 반복하라는 의미이며 동그라미는 변수를 가리킵니다. 화살표가 시작되는 변수는 조건, 화살표가 향하는 변수는 결과에 해당하는 변수입니다.

우리가 관찰 가능한 변수는 $d$번째 문서에 등장한 $n$번째 단어 $w_{d,n}$이 유일합니다(음영 표시). 우리는 이 정보만을 가지고 하이퍼파라메터(사용자 지정) $α,β$를 제외한 모든 잠재 변수를 추정해야 합니다. 앞으로 이 글에서는 이 그림을 기준으로 설명할 예정이기 때문에 잘 기억해두시면 좋을 것 같습니다.

LDA의 문서생성과정은 다음과 같습니다. 이는 저도 정리 용도로 남겨두는 것이니 스킵하셔도 무방합니다.

(1) Draw each per-corpus topic distributions $ϕ_k$~$Dir(β)$ for $k∈${$1,2,…K$}

(2) For each document, Draw per-document topic proportions $θ_d$~$Dir(α)$

(3) For each document and each word, Draw per-word topic assignment $z_{d,n}$~$Multi(θ_d)$

(4) For each document and each word, Draw observed word $w_{d,n}$~$Multi(ϕ_{z_{d,n},n})$

LDA 모델의 변수

우선 각 변수를 설명하겠습니다. $ϕ_k$는 $k$번째 토픽에 해당하는 벡터입니다. 말뭉치 전체의 단어 개수만큼의 길이를 가졌습니다. 예컨대 $ϕ_1$은 아래 표에서 첫번째 열입니다. 마찬가지로 $ϕ_2$는 두번째, $ϕ_3$은 세번째 열벡터입니다. $ϕ_k$의 각 요소값은 해당 단어가 $k$번째 토픽에서 차지하는 비중을 나타냅니다. $ϕ_k$의 각 요소는 확률이므로 모든 요소의 합은 1이 됩니다(아래 표 기준으로는 열의 합이 1).

그런데 아키텍처를 자세히 보면 $ϕ_k$는 하이퍼파라메터 $β$에 영향을 받는 걸 알 수 있습니다. 이는 LDA가 토픽의 단어비중 $ϕ_k$이 디리클레분포를 따른다는 가정을 취하기 때문입니다. LDA 기법에 디리클레라는 이름이 붙은 이유이기도 합니다. 디리클레분포 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

$θ_d$는 $d$번째 문서가 가진 토픽 비중을 나타내는 벡터입니다. 전체 토픽 개수 $K$만큼의 길이를 가집니다. 예컨대 $θ_1$은 아래 표에서 첫번째 행벡터, $θ_5$는 다섯번째 행벡터가 됩니다. $θ_d$의 각 요소값은 $k$번째 토픽이 해당 $d$번째 문서에서 차지하는 비중을 나타냅니다. $θ_d$는 확률이므로 모든 요소의 합은 1이 됩니다(아래 표 기준으로는 행의 합이 1).

$θ_d$ 역시 하이퍼파라메터 $α$에 영향을 받습니다. 이는 LDA가 문서의 토픽비중 $θ_d$이 디리클레분포를 따른다는 가정을 취하기 때문입니다.

이번엔 $z_{d,n}$에 대해 살펴보겠습니다. $z_{d,n}$은 $d$번째 문서 $n$번째 단어가 어떤 토픽에 해당하는지 할당해주는 역할을 합니다. 예컨대 세번째 문서의 첫번째 단어는 ‘Topic2’일 가능성이 높겠네요. Topic1과 2가 뽑힐 확률이 각각 0.375, 0.625이거든요.

$w_{d,n}$은 문서에 등장하는 단어를 할당해주는 역할을 합니다. $ϕ_k$와 $z_{d,n}$에 동시에 영향을 받습니다. 의미는 이렇습니다. 직전 예시에서 $z_{3,1}$은 실제로 Topic2에 할당됐다고 칩시다. 이제 $ϕ_2$를 봅시다. 그러면 $w_{3,1}$은 Money가 될 가능성이 높겠네요. Topic2의 단어 분포 가운데 Money가 0.313으로 가장 높거든요.

LDA의 inference

지금까지 LDA가 가정하는 문서생성과정과 잠재변수들이 어떤 역할을 하는지 설명했습니다. 이제는 $w_{d,n}$를 가지고 잠재변수를 역으로 추정하는 inference 과정을 살펴보겠습니다. 다시 말해 LDA는 토픽의 단어분포와 문서의 토픽분포의 결합으로 문서 내 단어들이 생성된다고 가정합니다. LDA의 inference는 실제 관찰가능한 문서 내 단어를 가지고 우리가 알고 싶은 토픽의 단어분포, 문서의 토픽분포를 추정하는 과정입니다.

여기에서 LDA가 가정하는 문서생성과정이 합리적이라면 해당 확률과정이 우리가 갖고 있는 말뭉치를 제대로 설명할 수 있을 것입니다. 바꿔 말해 토픽의 단어분포와 문서의 토픽분포의 결합확률이 커지도록 해야 한다는 이야기입니다. 확률과정과 결합확률을 각각 그림과 수식으로 나타내면 다음과 같습니다. ($z_{d,n}$:per-word topic assignment, $θ_d$:per-document topic proportions, $ϕ_k$:per-corpus topic distributions)

[\begin{align} p(&{ \phi }_{ 1:K },{ \theta }_{ 1:D },{ z }_{ 1:D },{ w }_{ 1:D })=\ &\prod _{ i=1 }^{ K }{ p({ \phi }_{ i }|\beta ) } \prod _{ d=1 }^{ D }{ p({ \theta }_{ d }|\alpha ) } \left{ \prod _{ n=1 }^{ N }{ p({ z }_{ d,n }|{ \theta }_{ d })p(w_{ d,n }|{ \phi }_{ 1:K },{ z }_{ d,n }) } \right} \end{align}]

위 수식에서 사용자가 지정한 하이퍼파라메터 $α,β$와 우리가 말뭉치로부터 관찰가능한 $w_{d,n}$을 제외한 모든 변수가 미지수가 됩니다. 따라서 우리는 사후확률(posterior) $p(z,ϕ,θ$|$w)$를 최대로 만드는 $z,ϕ,θ$를 찾아야 합니다. 이것이 LDA의 inference입니다. 그런데 사후확률을 계산하려면 분모에 해당하는 $p(w)$를 반드시 구해야 합니다. 이는 베이즈 정리에서 evidence로 불리는 것으로, $p(w)$는 잠재변수 $z,ϕ,θ$의 모든 경우의 수를 고려한 각 단어($w$)의 등장 확률을 가리킵니다. 그러나 $z,ϕ,θ$는 우리가 직접 관찰하는 게 불가능할 뿐더러, $p(w)$를 구할 때 $z,ϕ,θ$의 모든 경우를 감안해야 하기 때문에, 결과적으로 $p(w)$를 단번에 계산하는 것이 어렵습니다. 이 때문에 깁스 샘플링 같은 기법을 사용하게 됩니다. 깁스 샘플링 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

LDA와 깁스 샘플링

LDA에서는 나머지 변수는 고정시킨 채 한 변수만을 변화시키되, 불필요한 일부 변수를 샘플링에서 제외하는 collapsed gibbs sampling 기법을 씁니다. LDA에서는 $p(z,ϕ,θ$|$w)$를 구할 때 $ϕ,θ$를 계산에서 생략합니다. 깁스 샘플링으로 구한 $z$로 계산할 수가 있게 되거든요. 어쨌든 LDA의 깁스 샘플링 과정을 나타낸 수식은 다음과 같습니다.

위 식의 의미는 이렇습니다. 말뭉치가 주어졌기 때문에 $w$는 우리가 이미 알고 있는 값입니다. $z$는 각 단어가 어떤 토픽에 할당돼 있는지를 나타내는 변수인데요. $z_{-i}$는 $i$번째 단어의 토픽 정보를 제외한 모든 단어의 토픽 정보를 가리킵니다. 식 전체적으로는 $w$와 $z_{-i}$가 주어졌을 때 문서의 $i$번째 단어의 토픽이 $j$일 확률을 뜻합니다. 아래 그림을 볼까요?

위 그림에서 $z_i$는 record라는 단어가 속하는 토픽입니다. 깁스 샘플링을 위해 토픽 정보를 지워 놓았습니다. 나머지 단어에 대한 토픽 정보는 그대로 씁니다. 이것이 바로 $z_{-i}$입니다. 이 상태의 정보를 토대로 record라는 단어가 어떤 토픽에 속할지 할당하는 것이 LDA의 깁스 샘플링 과정입니다. 이해를 돕기 위해 그림 하나 더 보겠습니다.

위 그림은 이렇게 이해하면 됩니다. 각 행은 문서를 나타냅니다. 동그라미는 각 문서에 속한 단어들입니다. 동그라미 안의 숫자들은 토픽 ID입니다. 처음엔 랜덤하게 뿌려 놓습니다.

첫번째 깁스 샘플링 대상인 첫번째 문서의 첫번째 단어 $z_{0,0}$의 토픽 정보를 지웁니다. 나머지 단어들의 토픽정보를 토대로 가장 그럴싸한 토픽 ID를 새로 뽑았습니다. 예시 그림에선 3이네요.

이번엔 $z_{0,1}$ 차례입니다. 첫번째 문서의 두번째 단어 $z_{0,1}$의 토픽 정보를 지웁니다. 새로 뽑은 $z_{0,0}$을 포함한 나머지 단어들의 토픽정보를 토대로 가장 그럴싸한 토픽 ID를 또 새로 뽑습니다. 1입니다.

이런 식으로 문서 내 모든 단어와 말뭉치 내 모든 문서에 대해 깁스 샘플링을 반복하면 어느 순간부터는 모든 단어에 대한 토픽 할당 정보가 수렴하게 됩니다.

실제 계산과정

몇 가지 수식 정리 과정을 거치면 $d$번째 문서 $i$번째 단어의 토픽 $z_{d,i}$가 $j$번째에 할당될 확률은 다음과 같이 쓸 수 있습니다.

위 수식의 표기를 정리한 표는 다음과 같습니다.

예를 들어보겠습니다. 우선 아래와 같이 단어 5개로 구성된 문서 doc1이 있고, 각 단어마다 토픽 $z_i$도 이미 할당돼 있다고 가정해 보겠습니다(초기엔 랜덤하게 할당을 하니 이렇게 가정하는 게 무리가 없습니다). 토픽 수는 사용자가 3개로 지정해 놓은 상태입니다.

말뭉치에 등장하는 모든 단어들을 대상으로 각각의 단어들이 어떤 토픽에 속해 있는지를 일일이 세어서 만든 표도 다음과 같다고 가정하겠습니다(이 표 역시 초기엔 랜덤 할당을 합니다)

이제 깁스 샘플링을 할 차례입니다. $p(z_{1,2})$를 구해 보겠습니다. $z_{1,-2}$, 즉 첫번째 문서의 두번째 단어의 토픽($z_2$) 정보를 지운 상태에서, 나머지 단어들의 토픽 할당 정보를 활용해 계산하게 됩니다.

위 표를 보면 $z_{1,2}$를 지우고 나니 첫번째 문서엔 1번/3번 토픽이 각각 절반씩 있는 걸 확인할 수 있습니다. 바꿔 말해 $n_{1,1}=2$, $n_{1,3}=2$라는 것이죠. $α$는 사용자가 지정하는 하이퍼파라메터로 깁스 샘플링 과정에서 변하는 값이 아니므로 $A$의 크기는 $n_{1,1}$과 $n_{1,3}$에 영향을 받을 겁니다. 즉, $z_{1,2}$가 2번 토픽이 될 확률은 0이고, 1번/3번은 같습니다. $A$는 아래 그림과 같이 이해할 수 있습니다.

이번엔 수식의 오른쪽 부분인 $B$를 보겠습니다. 전체 말뭉치를 대상으로 단어들의 토픽 할당 정보를 조사한 표는 다음과 같다고 칩시다. 여기서 주의할 점은 깁스 샘플링을 수행하면서 trade의 토픽 정보를 지웠으므로 단어별 토픽 분포 표에서 $v_{2,trade}$가 1이 줄어든다는 사실입니다.

어쨌든 위 표를 보면 우리의 관심인 trade라는 단어의 토픽은 Topic1일 가능성이 제일 높겠네요. 전체 말뭉치에서 trade의 토픽은 1번, 2번, 3번 순으로 많거든요. 바꿔 말해 $v_{1,trade}=10$, $v_{2,trade}=7$, $v_{3,trade}=1$입니다. $B$에 적용된 $β$ 역시 샘플링 과정에서 바뀌는 과정이 아니므로 $B$의 크기는 $v_k$에 가장 많은 영향을 받을 겁니다. 이를 그림으로 나타내면 다음과 같습니다.

$p(z_{1,2})$는 $A$와 $B$의 곱으로 도출됩니다. $A$와 $B$를 각각 직사각형의 높이와 너비로 둔다면, $p(z_{1,2})$는 아래와 같이 직사각형의 넓이로 이해할 수 있습니다.

이 계산 예시에서 $z_{1,2}$는 Topic1에 할당될 가능성이 제일 큽니다. 하지만 Topic3에 할당될 가능성도 Topic1에 비해선 작지만 아주 없는 건 아닙니다. 확률적인 방식으로 토픽을 할당하기 때문입니다.

어쨌든 결과적으로 $z_{1,2}$이 Topic1에 할당됐다고 가정해 보겠습니다. 그러면 Doc1의 토픽 분포($θ_1$)와 첫번째 토픽의 단어 분포($ϕ_1$)가 각각 다음과 같이 바뀝니다.

이런 방식으로 모든 문서, 모든 단어에 대해 깁스 샘플링을 수행하면 모든 단어마다 토픽을 할당해줄 수가 있게 됩니다. 이 과정에서 $ϕ,θ$ 또한 자연스럽게 구할 수 있습니다. 보통 1000회~1만회 반복 수행하면 그 결과가 수렴한다고 합니다.

디리클레 파라메터의 역할

$d$번째 문서에 $i$번째로 등장하는 단어의 토픽이 $j$번째일 확률을 다시 쓰면 다음과 같습니다.

$A$는 $d$번째 문서가 $j$번째 토픽과 맺고 있는 연관성 강도를 나타냅니다. $B$는 $d$번째 문서의 $n$번째 단어($w_{d,n}$)가 $j$번째 토픽과 맺고 있는 연관성의 강도를 가리킵니다.

그러면 여기에서 $α​$ 값은 어떤 역할을 할까요? 이전 예시에서 첫번째 문서에 Topic2에 할당된 단어들이 하나도 없었습니다($n_{1,2}=0​$). 원래대로라면 첫번째 문서가 Topic2와 맺고 있는 연관성 강도, 즉 $A​$는 0이어야 할 겁니다. 이렇게 되면 $z_{d,i}​$가 Topic2가 될 확률 또한 0이게 됩니다.

하지만 사용자가 지정하는 하이퍼파라메터 $α$ 존재 덕분에 $A$가 아예 0으로 되는 일을 막을 수 있게 됩니다. 일종의 smoothing 역할을 한다는 것이죠. 따라서 $α$가 클수록 토픽들의 분포가 비슷해지고, 작을 수록 특정 토픽이 크게 나타나게 됩니다. 이는 $β$가 $B$에서 차지하는 역할과 대동소이합니다.

아래는 디리클레 파라메터 변화에 따른 토픽 분포의 변화를 직관적으로 나타난 그림입니다.

최적 토픽 수 찾기

LDA의 토픽수 $K$는 사용자가 지정하는 하이퍼파라메터입니다. 최적 토픽수 또한 여러 실험을 통해 구해야 하는 미지수라는 이야기입니다. 최적 토픽수를 구하는 데 쓰는 Perplexity 지표가 있어 소개합니다.

LDA는 문서가 생성되는 과정을 확률모형으로 가정합니다. LDA로부터 추정된 토픽 정보($z$)를 활용해 계산한 각 단어의 발생확률이 클수록 학습 말뭉치가 생성되는 과정을 제대로 설명하는 것이라는 얘기입니다. 최적 토픽 수를 찾기 위한 방법도 이 아이디어를 차용합니다.

우선 깁스 샘플링으로 구한 $ϕ,θ$를 활용해 전체 문서, 모든 단어의 발생 확률 $p(w)$를 식으로 쓰면 다음과 같습니다. $p(w)$는 말뭉치에 등장한 모든 단어의 발생확률을 종합적으로 따지기 때문에 곱으로 연결되지만, 이를 로그를 취한 결과가 아래 식입니다.

[\log { \left{ p(w) \right} } =\sum { d=1 }^{ D }{ \sum _{ j=1 }^{ V }{ { n }^{ jd }\log { \left[ \sum _{ k=1 }^{ K }{ { \theta }{ k }^{ d }{ \phi }_{ k }^{ j } } \right] } } }]

$log(p(w))$ 개념은 이렇습니다. 첫번째 문서 세번째 단어가 ‘King’이라고 칩시다. 이 단어가 첫번째 문서에 나타난 빈도가 3이라고 하면 $n^{31}=3$입니다. 여기에 토픽의 단어분포 정보인 $ϕ$와 문서의 토픽 비중 정보인 $θ​$를 element-wise 곱 방식으로 계산하게 됩니다. 그런데 ‘King’이라는 단어는 하나의 토픽에만 있는게 아니고 여러 토픽에 걸쳐 있을 수 있습니다. 흔한 단어일 경우 더욱 그렇겠지요. 그래서 모든 토픽에 대해 합을 계산하게 됩니다.

위 정보를 활용한 Perplexity 지표는 다음과 같이 구합니다.

[Perplexity(w)=exp\left[ -\frac { log\left{ p(w) \right} }{ \sum _{ d=1 }^{ D }{ \sum _{ j=1 }^{ V }{ { n }^{ jd } } } } \right]]

$p(w)$는 클수록 좋은 inference이므로 $exp(-log(p(w)))$는 작을수록 좋을 겁니다. 따라서 아래 그림처럼 토픽 수 $K$를 바꿔가면서 Perplexity를 구한 뒤 가장 작은 값을 내는 $K$를 최적의 토픽수로 삼으면 됩니다.

이번 글에서는 깁스 샘플링(Gibbs Sampling)에 대해 간단히 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의와 위키피디아, ‘밑바닥부터 시작하는 데이터과학(조엘 그루스 지음, 인사이트 펴냄)’, 그리고 이곳을 정리했음을 먼저 밝힙니다.

개요

깁스 샘플링은 두 개 이상의 확률변수의 결합확률분포로부터 일련의 표본을 생성하는 확률적 알고리즘입니다. 결합확률분포나 그에 관련된 확률 계산을 근사하기 위해 널리 사용되고 있습니다. 깁스 샘플링은 마코프 연쇄 몬테카를로 방법(Markov Chain Monte Carlo;MCMC) 알고리즘의 한 예라고 합니다. 깁스 샘플링을 이해해보기 위해 몬테카를로 방법과 MCMC를 먼저 알아보겠습니다.

몬테카를로 방법

몬테카를로 방법(Monte Carlo Method)이란 랜덤 표본을 뽑아 함수의 값을 확률적으로 계산하는 알고리즘을 가리킵니다. 수학이나 물리학 등에 자주 사용되며 계산하려는 값이 닫힌 형식으로 표현되지 않거나 복잡한 경우에 그 값을 근사적으로 계산하려고 할 때 쓰입니다. 몬테카를로 방법의 대표적인 사례가 바로 원주율 계산입니다. 아래 그림(출처)을 보겠습니다.

원주율 계산을 위한 몬테카를로 방법은 다음과 같습니다.

(1) [0,1] x [0,1]에서 점 $(x,y)$를 무작위로 뽑는다.

(2) 이 점이 중심이 (0,0)이고 반지름이 1인 원에 속하는지 계산한다. (즉 $x^2+y^2≤1$을 만족하면 빨간색 점, 그렇지 않으면 파란색 점으로 분류)

(3) 위의 두 과정을 충분히 반복한다.

위 그림에서 4분 원의 넓이는 $π/4$입니다. 전체 점 개수를 빨간색 점 개수로 나눈 비율이 이 값에 근사합니다. 이를 통해 우리는 $π$값이 얼마인지 대략적으로 추정할 수 있습니다.

마코프 연쇄

마코프 연쇄(Markov Chain)란 마코프 가정(Markov assumption)을 따르는 이산 시간 확률 과정을 가리킵니다. 마코프 가정은 러시아 수학자 마코프가 1913년경에 러시아어 문헌에 나오는 글자들의 순서에 관한 모델을 구축하기 위해 제안된 개념입니다. 특정 시점의 상태 확률은 단지 그 이전 상태에만 의존한다는 것이 핵심입니다. 즉 한 상태에서 다른 상태로의 전이(transition)는 그동안 상태 전이에 대한 긴 이력(history)을 필요로 하지 않고 바로 직전 상태에서의 전이로 추정할 수 있다는 이야기입니다. 마코프가정은 아래와 같이 도식화됩니다.

그런데 특정 조건을 만족한 상태에서 마코프 연쇄를 반복하다 보면 현재 상태의 확률이 직전 상태의 확률과 같아지게, 즉 수렴하게 됩니다. 이렇게 평형 상태에 도달한 확률 분포를 정적분포(Stationary Distribution)라고 합니다.

마코프 연쇄 몬테카를로 방법

MCMC란 마코프 연쇄에 기반한 확률 분포로부터 표본을 추출하는 몬테카를로 방법입니다. 다음과 같습니다.

MCMC 알고리즘은 우리가 샘플을 얻으려고 하는 목표분포를 Stationary Distribution으로 가지는 마코프 체인을 만든다. 이 체인의 시뮬레이션을 가동하고 초기값에 영향을 받는 burn-in period를 지나고 나면 목표분포를 따르는 샘플이 만들어진다.

깁스 샘플링

깁스 샘플링은 MCMC의 일종인데요. 몬테카를로와 MCMC와의 차이점은 이렇습니다. 몬테카를로 방법은 모든 샘플이 독립(independent)이고 생성될(뽑힐) 확률 또한 랜덤입니다. 반면 마코프 연쇄에 기반한 MCMC는 다음번 생성될(뽑힐) 샘플은 현재 샘플의 영향을 받습니다. 깁스 샘플링은 다음번 생성될 표본은 현재 샘플에 영향을 받는다는 점에서는 MCMC와 같지만, 나머지 변수는 그대로 두고 한 변수에만 변화를 준다는 점이 다릅니다.

예를 들어보겠습니다. 3개의 확률변수의 결합확률분포 $p(x_1,x_2,x_3)$로부터 1개의 표본을 얻으려고 할 때 깁스 샘플링의 절차는 다음과 같습니다.

(1) 임의의 표본 $X^0=(x_1^0,x_2^0,x_3^0)$을 선택한다.

(2) 모든 변수에 대해 변수 하나만을 변경하여 새로운 표본 $X^1$을 뽑는다.

실제 사용시에는 처음 수집한 표본 $X^0$은 버리고 $X^1$만 쓰게 됩니다. (2)를 자세하게 쓰면 다음과 같습니다.

(ㄱ) 현재 주어진 표본 $X^0$의 두번째, 세번째 변수 $x_2^0$, $x_3^0$를 고정시킨다.

(ㄴ) 첫번째 기존 변수 $x_1^0$를 대체할 새로운 값 $x_1^1$을 다음과 같은 확률로 뽑는다. p($x_1^1$|$x_2^0$,$x_3^0$)

(ㄷ) 첫번째 변수 $x_1^1$, 세번째 변수 $x_3^0$ 를 고정시킨다.

(ㄹ) 두번째 기존 변수 $x_2^0$를 대체할 새로운 값 $x_2^1$을 다음과 같은 확률로 새로 뽑는다. p($x_2^1$|$x_1^1$,$x_3^0$)

(ㅁ) 첫번째 변수 $x_1^1$, 두번째 변수 $x_2^1$를 고정시킨다.

(ㅅ) 세번째 기존 변수 $x_3^0$를 대체할 새로운 값 $x_3^1$을 다음과 같은 확률로 새로 뽑는다. p($x_3^1$|$x_1^1$,$x_2^1$)

(ㅇ) 최종적으로 구한 $X^1$은 다음과 같다. $X^1=(x_1^1,x_2^1,x_3^1)$

(2)에서 새로운 값을 뽑는 데 쓰인 조건부 확률은 결합확률분포 $p(x_1,x_2,x_3)$에 비례한다고 합니다. 표본의 앞부분은 초기 상태 $X^0$에 크게 의존하지만 충분히 많이 뽑고 난 뒤에는 초기 상태에 관계 없이 $p$에 기반한 표본을 수집할 수 있다고 합니다.

2차원의 가우시안 분포를 만들어 내기 위해 깁스 샘플링을 적용한 예시 그림은 다음과 같습니다.

깁스 샘플링의 변형들

변수가 $(a,b,c)$ 세 개인 데이터에 대해 깁스 샘플링을 수행한다면 $b,c$를 고정시킨 채로 $a$를, $a,c$를 고정시킨 채로 $b$를, $a,b$를 고정시킨 채로 $c$를 차례대로 뽑아야 합니다.

Block Gibbs sampling 기법은 그룹으로 묶어 뽑는 기법입니다. $c$를 고정시킨 채로 $a,b$를 뽑고 $a,b$를 고정시킨 채로 $c$를 뽑는 방식입니다.

Collapsed Gibbs sampling 기법은 불필요한 일부 변수를 샘플링에서 생략하는 기법입니다. $b$가 그런 변수라 가정하면 $c$를 고정시킨 상태에서 $a$를 뽑고, $a$를 고정시킨 상태에서 $c$를 뽑습니다.

파이썬 구현

이해를 돕기 위해 ‘밑바닥부터 시작하는 데이터 과학’에 나온 간단한 예시를 들겠습니다. 깁스 샘플링은 임의의 $x$ 또는 $y$값에서 출발해서 $x$에 대한 $y$의 조건부확률과 $y$에 대한 $x$의 조건부확률 사이를 오가며 반복적으로 값을 선택하는 방법입니다. 이 과정을 여러번 반복하여 얻은 $x$와 $y$는 결합확률분포에서 얻은 샘플과 유사한 값이 됩니다.

우선 문제를 정의해 보겠습니다. 주사위 두 개를 던진다고 해 봅시다. 첫번째 주사위의 눈을 $x$, 두 주사위의 눈을 합한 값을 $y$라고 하면 $x$와 $y$의 결합확률분포 함수는 다음과 같습니다.

import random

def roll_a_die():
    # 주사위 눈은 1~6
    # 각 눈이 선택될 확률은 동일(uniform)
    return random.choice(range(1,7))

def direct_sample():
    d1 = roll_a_die()
    d2 = roll_a_die()
    return d1, d1+d2

$x$에 대한 $y$의 조건부확률과 $y$에 대한 $x$의 조건부확률 함수는 다음과 같습니다.

def random_y_given_x(x):
    # x값을 알고 있다는 전제 하에
    # y값이 선택될 확률
    # y는 x+1, x+2, x+3
    # x+4, x+5, x+6 가운데 하나
    return x + roll_a_die()

def random_x_given_y(y):
    # y값을 알고 있다는 전제 하에
    # x값이 선택될 확률
    # 첫째 둘째 주사위 값의 합이 7이거나
    # 7보다 작다면
    if y <= 7:
        # 첫번째 주사위의 눈은 1~6
        # 각 눈이 선택될 확률은 동일
        return random.randrange(1, y)
    # 만약 총합이 7보다 크다면
    else:
        # 첫번째 주사위의 눈은
        # y-6, y-5,..., 6
        # 각 눈이 선택될 확률은 동일
        return random.randrange(y-6, 7)

깁스 샘플링 함수는 다음과 같습니다.

def gibbs_sample(num_iters=100):
    # 초기값이 무엇이든 상관없음
    x, y = 1, 2
    for _ in range(num_iters):
        x = random_x_given_y(y)
        y = random_y_given_x(x)
    return x, y

깁스 샘플 수를 늘려서 결합확률분포 direct_sample로부터 뽑은 결과와 비교하면 유사한 결과가 나오는걸 확인할 수 있습니다. 다시 말해 결합확률분포를 모를 때, 이미 알고 있는 일부 조건부 확률분포에 깁스 샘플링을 적용하여 해당 결합확률분포의 표본을 얻어낼 수 있다는 것입니다.

이번 글에서는 서포트 벡터 머신(SVM)의 변형인 Kernel-SVM에 대해 살펴보도록 하겠습니다. 이 글 역시 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. SVM의 일반적인 내용에 대해서는 이곳을, C-SVM에 대해서는 이곳을 참고하시기 바랍니다. 그럼 시작하겠습니다.

Kernel-SVM의 목적의식

SVM은 두 범주를 잘 분류하면서 마진(margin)이 최대화된 초평면(hyperplane)을 찾는 기법입니다. 기본적으로 선형분류를 한다는 것이죠. 하지만 어떤 직선을 그어도 두 범주를 완벽하게 분류하기 어려운 경우도 많습니다. Kernel-SVM은 이 문제를 해결하기 위해 제안됐습니다. 먼저 아래 그림을 보겠습니다.

그림에서도 알 수 있듯 Kernel-SVM의 핵심 아이디어는 이것입니다.

원공간(Input Space)의 데이터를 선형분류가 가능한 고차원 공간(Feature Space)으로 매핑한 뒤 두 범주를 분류하는 초평면을 찾는다.

mapping function

여기에서 가장 중요한 것은 Input Space와 Featuer Space 사이를 매핑해주는 함수 $Φ$입니다. 예를 들어 $Φ$가 아래와 같이 정의돼 있다고 칩시다.

[\Phi :({ x }{ 1 },{ x }{ 2 })\rightarrow ({ x }{ 1 }^{ 2 },{ x }{ 2 }^{ 2 },\sqrt { 2 } { x }{ 1 },\sqrt { 2 } { x }{ 2 },\sqrt { 2 } { x }{ 1 }{ x }{ 2 },1)]

$Φ$는 $R^2$에 속한 입력을 받아서 그보다 고차원인 $R^6$으로 변환해 줍니다. 이렇게 되면 원래는 선형분리가 불가능했던 XOR문제가 선형분리가 가능한 데이터로 바뀌게 됩니다. 아래와 같습니다.

그러면 SVM에 $Φ$를 어떻게 적용하는지 살펴보겠습니다. Hard-margin SVM과 Soft-Margin SVM의 라그랑지안 Dual 식은 동일하며 다음과 같습니다. ($L_D$ 제약식은 생략)

[\max { { L }{ D }({ \alpha }{ i }) } =\sum { i=1 }^{ n }{ { \alpha }{ i } } -\frac { 1 }{ 2 } \sum { i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }{ i }{ { \alpha }{ j }y }{ i }{ y }{ j }{ x }{ i }^{ T }{ x }_{ j } } }]

Kernel-SVM은 $Φ$로 변환된 고차원 공간에서 두 범주를 분류하는 초평면을 만들기 때문에 $x_i^T$와 $x_j$에 $Φ$를 적용해 주어야 합니다. 식은 다음과 같이 쓸 수 있습니다.

[\max { { L }{ D }({ \alpha }{ i }) } =\sum { i=1 }^{ n }{ { \alpha }{ i } } -\frac { 1 }{ 2 } \sum { i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }{ i }{ { \alpha }{ j }y }{ i }{ y }{ j }{ \Phi ({ x }{ i }) }^{ T }{ \Phi ({ x }_{ j }) } } }]

Kernel Trick!

그런데 커널을 도입하게 되면 연산량이 폭증하게 됩니다. 그도 그럴 것이 모든 관측치에 대해 고차원으로 매핑하고 이를 다시 내적(inner product)해야 하기 때문입니다. 고차원 매핑과 내적을 한방에 할 수는 없을까요? 이를 위해 도입된 것이 바로 커널(Kernel)입니다. 커널 $K$는 다음과 같이 정의됩니다.

\(K({ x }_{ i },{ x }_{ j })={ \Phi ({ x }_{ i }) }^{ T }{ \Phi ({ x }_{ j }) }\) 매핑함수 $Φ$는 선형변환(Linear Transformation)이고 그에 해당하는 표준행렬(standard matrix)을 $A$라고 두면 다음과 같이 쓸 수 있습니다.

[{ \Phi (x) }=Ax]

그러면 $K$는 다음과 같이 다시 쓸 수 있습니다.

[K({ x }{ i },{ x }{ j })={ \Phi ({ x }{ i }) }^{ T }{ \Phi ({ x }{ j }) }={ x }{ i }^{ T }{ A }^{ T }A{ x }{ j }]

여기에서 $Φ$를 $m$차원에서 $n$차원으로 매핑해주는 함수라고 가정해 봅시다. 그러면 각각의 차원수는 다음과 같습니다.

(1) $x_i^T$ : (1 x m)

(2) $A^T$ : (m x n)

(3) $A$ : (n x m)

(4) $x_j$ : (m x 1)

따라서 $K$의 결과는 스칼라가 됩니다. 그런데 $K(x_i, x_i)$인 경우 항상 0 이상의 값을 지녀야 할 겁니다. 또 $K(x_i, x_j)=K(x_j, x_i)$을 만족해야 할 겁니다. 이러한 맥락에서 $K(x_i,x_j)$로 구성된 행렬은 positive semi-definite matrix여야 하며 대칭행렬(symetric matrix)이어야 합니다.

이와 관련된 Mercer’s Theorem은 다음과 같습니다.

위 조건을 만족하는 임의의 함수는 모두 커널 함수로 쓸 수 있습니다. 그 종류는 다음과 같습니다.

[\begin{align} linear\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })={ x }_{ 1 }^{ T }{ x }_{ 2 }\ polynomial\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })={ ({ x }_{ 1 }^{ T }{ x }_{ 2 }+c) }^{ d },\quad c>0\ sigmoid\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })=\tanh { \left{ a({ x }_{ 1 }^{ T }{ x }_{ 2 })+b \right} } ,\quad a,b\ge 0\ gaussian\quad &:\quad K({ x }_{ 1 },{ x }_{ 2 })=exp\left{ -\frac { { \left| { x }_{ 1 }-{ x }_{ 2 } \right| }_{ 2 }^{ 2 } }{ 2{ \sigma }^{ 2 } } \right} ,\quad \sigma \neq 0 \end{align}]

Gaussian Kernel

polynomial 커널을 쓰는 경우 사용자가 지정한 $d$가 Feature space의 차원이 됩니다. 그러면 가우시안 커널은 어떨까요? $2σ^2=1$이어서 분모가 생략된 간단한 형태를 보겠습니다. \(\begin{align*}\\ K({ x }_{ 1 },{ x }_{ 2 })&=exp\left\{ -{ ({ x }_{ 1 }-{ x }_{ 2 }) }^{ 2 } \right\} \\ &=exp(-{ x }_{ 1 })exp(-{ x }_{ 2 })exp(2{ x }_{ 1 }{ x }_{ 2 })\end{align*}\)

테일러급수 정리에 의해 $exp(2x_ix_2)$를 다음과 같이 쓸 수 있습니다.

[exp(2{ x }{ 1 }{ x }{ 2 })=\sum { k=0 }^{ \infty }{ \frac { { 2 }^{ k }{ x }{ 1 }^{ k }{ x }_{ 2 }^{ k } }{ k! } }]

따라서 가우시안 커널은 Input Space가 몇 차원이 됐든 무한대 차원의 Feature Space로 매핑한다는 얘기입니다.

Kernel의 효과

기존 SVM에 해당하는 Linear 커널은 선형 분류경계면을 만들어냅니다. Polynomial 등 이 글에서 소개하는 커널은 비선형 경계면이 만들어집니다. 다음과 같습니다.

이번엔 가우시안 커널을 보겠습니다. gamma는 지수의 분모에 해당하는 하이퍼 파라메터인데요. 작을수록 마진이 넓어지는 걸 확인할 수 있습니다.

이번 글에서는 서포트 벡터 머신(SVM)의 변형인 C-SVM에 대해 살펴보도록 하겠습니다. 이 글 역시 고려대 강필성 교수님과 역시 같은 대학의 김성범 교수님 강의를 정리했음을 먼저 밝힙니다. SVM의 일반적인 내용에 대해서는 이곳을 참고하시기 바랍니다. 그럼 시작하겠습니다.

C-SVM의 목적의식

SVM은 두 범주를 잘 분류하면서 마진(margin)이 최대화된 초평면(hyperplane)을 찾는 기법입니다. 기본적으로 선형분류를 한다는 것이죠. 하지만 아래 그림처럼 어떤 직선을 그어도 두 범주를 완벽하게 분류하기 어려운 경우도 많습니다.

이 경우에는 두 가지 해결 방법이 있습니다. minus-plane과 plus-plane 사이(즉 마진) 안에 관측치가 존재할 수 있도록 제약을 완화하는 방안이 첫번째입니다. 두번째로는 분류 경계면을 아예 구불구불한 비선형 모양으로 만드는 겁니다. 전자가 C-SVM, 후자가 Kernel-SVM 기법의 핵심 아이디어입니다. Kernel-SVM 기법에 대해서는 이곳을 참고하시면 좋을 것 같습니다.

C-SVM 개요

기존 SVM은 마진 안에 관측치가 들어올 수 없습니다(hard-margin). 마진 폭이 줄어드는 걸 감수하고서라도 그런 관측치가 없도록 마진을 설정하기 때문이죠. 그런데 C-SVM은 마진 안에 관측치의 존재를 허용합니다. 이를 Soft-margin이라고 합니다. 아래 그림을 보겠습니다.

위 그림에서 minus-plane을 벗어난 빨간점과 plus-plane을 벗어난 파란점이 눈에 띕니다. 마진을 최대화하되 이런 관측치들을 허용하는 게 바로 C-SVM입니다. 다만 plus/minus-plane을 벗어난 $ξ$ 만큼 panelty를 부과합니다. 우리가 찾아야할 C-SVM의 초평면을 $w^Tx+b$라고 할 때 C-SVM의 목적식은 다음과 같습니다. ($n$=관측치 개수)

[\min { \frac { 1 }{ 2 } { \left| w \right| }{ 2 }^{ 2 } } +C\sum _{ i=1 }^{ n }{ { \xi }{ i } }]

위 목적식에서 $C$는 사용자가 설정하는 하이퍼파라메터(hyperparameter)입니다. $C$가 커질수록 마진 폭이 줄어듭니다. 이 기법이 C-SVM으로 불리는 이유입니다. $C$의 크기에 따른 효과는 이후 자세히 살펴보겠습니다.

C-SVM의 제약식은 다음과 같습니다. ($i=1,2,…,n$)

[{ y }{ i }({ w }^{ T }{ x }{ i }+b)\ge 1-{ \xi }{ i },\quad { \xi }{ i }\ge 0]

제약식의 의미는 이렇습니다. 원 SVM의 제약식은 $y_i(w^Tx_i+b)≥1$이었습니다. 마진 폭이 $ξ_i$만큼 줄어들 수 있기 때문에 이를 반영한 것입니다. $ξ_i$가 음수라면 plus/minus-plane을 벗어나지 않은 경우이므로 고려할 필요가 없습니다.

해 구하기

제약식에 라그랑지안 승수를 곱해 목적식에 합쳐 라그랑지안 Primal 문제로 바꾸면 다음과 같습니다.

[{ \min { L_{ p }(w,b,{ { \xi }{ i },\alpha }{ i },{ \mu }{ i }) } }=\frac { 1 }{ 2 } { \left| w \right| }{ 2 }^{ 2 }+C\sum { i=1 }^{ n }{ { \xi }{ i } } -\sum { i=1 }^{ n }{ { \alpha }{ i }({ y }{ i }({ w }^{ T }{ x }{ i }+b)-1 + {\xi}{ i }) } -\sum _{ i=1 }^{ n }{ { { \mu }{ i }\xi }_{ i } }]

원 문제의 제약식의 범위가 0 이상이므로 $L_p$의 제약은 다음과 같습니다.

[{ \alpha }{ i }\ge 0,\quad{ \mu }{ i }\ge 0,\quad i=1,…,n]

KKT 조건에서는 $L_p$를 미지수로 각각 편미분한 식이 0이 되는 지점에서 $L_p$가 최소값을 갖습니다. 다음과 같습니다.

[\begin{align} \frac { \partial L_{p} }{ \partial w } =0\quad &\rightarrow \quad w=\sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i }{ x }_{ i } } \ \frac { \partial L_{p} }{ \partial b } =0\quad &\rightarrow \quad \sum _{ i=1 }^{ n }{ { \alpha }_{ i }{ y }_{ i } } =0\\frac { \partial L_{ p } }{ \partial { \xi }_{ i } } =0\quad &\rightarrow \quad C-{ \alpha }_{ i }-{ \mu }_{ i }=0 \end{align}]

위 식을 $L$에 넣어 정리하면 라그랑지안 Primal 문제가 Dual 문제로 바뀝니다. $a_i$에 관한 문제로 단순해졌고, 미지수 최고차항 계수가 음수여서 최대화 문제로 바뀌었습니다. 이는 기존 SVM의 Dual 식과도 일치합니다.

[\max { { L }{ D }({ \alpha }{ i }) } =\sum { i=1 }^{ n }{ { \alpha }{ i } } -\frac { 1 }{ 2 } \sum { i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ { \alpha }{ i }{ { \alpha }{ j }y }{ i }{ y }{ j }{ x }{ i }^{ T }{ x }_{ j } } }]

KKT 조건에 의해 $L_D$의 제약식은 다음과 같습니다.

[\sum { i=1 }^{ n }{ { \alpha }{ i }{ y }{ i } } =0 \0\le { \alpha }{ i }\le C,\quad i=1,…,n]

위 제약식에서 $0≤α_i≤C$가 도출된 배경은 이렇습니다. $L_p$ 제약에 의해 $α_i$, $μ_i$는 모두 0 이상의 값을 가져야 합니다. 여기에서 KKT 조건에 의해 $L_p$를 $ξ_i$로 미분한 식을 0으로 두고 풀어서 나온 $C-α_i-μ_i=0$을 생각해 봅시다. 그렇다면 $α_i$는 아무리 커도 $C$ 이상의 값을 가질 수 없습니다.

C-SVM의 서포트 벡터

우리가 찾고자 한 답은 마진이 최대화된 분류경계면 $w^Tx+b$입니다. $w$와 $b$를 찾으면 SVM의 해를 구할 수 있게 됩니다. KKT 조건을 탐색하는 과정에서 $w$는 다음과 같이 도출됐습니다.

[w=\sum { i=1 }^{ n }{ { \alpha }{ i }{ y }{ i }{ x }{ i } }]

$x_i​$와 $y_i​$는 우리가 가지고 있는 학습데이터이므로 라그랑지안 승수인 $α_i​$값들만 알면 $w​$를 찾을 수 있습니다. 그런데 여기에서 $α_i​$가 0인 관측치들은 분류경계면 형성에 아무런 영향을 끼치지 못하는 non-support vector들입니다.

KKT 조건에 의해 $L_D$가 최대값을 갖는다면 아래 두 개 가운데 하나는 반드시 0입니다.

(1) $α_i​$

(2) $y_i(w^Tx_i+b)-1+{\xi}_{i}​$

아울러 아래 두 개 가운데 하나도 반드시 0입니다.

(1) $μ_i$

(2) $ξ_i$

$α_i$는 다음의 범위를 갖습니다.

[0\le { \alpha }_{ i }\le C]

$α_i$가 0보다 크고 $C$ 이하라면 $y_i(w^Tx_i+b)-1+ξ_{i}$는 0입니다. $ξ_{i}$는 0이 될 수 있습니다(${\mu}_{i}$가 0보다 큰 값인 경우). 따라서 이 조건을 만족하는 관측치들은 마진 위에 있는 support vector들이 됩니다.

$α_i​$가 $C​$라면 $μ_i​$는 0입니다. $C-α_i-μ_i=0​$가 성립해야 하기 때문입니다. 그러면 $ξ_i​$는 0보다 큰 값을 갖습니다. 따라서 이 조건을 만족하는 관측치들은 plus-plane과 minus-plane 사이에 있는, 즉 마진 안에 있는 support vector들이 됩니다.

C의 효과

하이퍼파라메터 $C$는 마진 폭을 줄이거나 넓히는 역할을 합니다. $C$가 크면 라그랑지안 문제에서 $ξ_i$의 역할이 커지고, 그만큼 마진 폭이 줄어듭니다. 그 효과를 나타낸 그림은 아래와 같습니다.