19. Undirected graphical models (Markov random fields)

19.1. Introduction

2D 격자 위상을 가진 비순환 방향그래프 모델은 연관 마르코프 무작위 필드 또는 마르코프 메쉬라고 불린다. 그러나 이 모델이 항상 적합한 것은 아니다. 대안은 비방향 그래프 모델(UGM), 또는 마르코프 무작위 필드, 마르코프 망을 이용하는 것이다. 이는 간선간의 방향을 가정하지 않으므로 이미지 분석 같은 작업에 더 적합하다.

비방향 그래프 모델이 방향 그래프 모델에 대해 가지는 장점들은 다음과 같다.

  • 대칭적이므로 공간 데이터에 더 적합하다.
  • 조건부 확률분포를 정의하는 구별적 비방향그래프 모델은 구별적 방향그래프 모델보다 더 좋은 성능을 보인다.

비방향 그래프 모델이 방향 그래프 모델에 대해 가지는 단점들은 다음과 같다.

  • 매개변수의 표현력이 떨어진다.
  • 매개변수 추정의 연산량이 더 많이 든다.

19.2. Conditional independence properties of UGMs

19.2.1. Key properties

비방향그래프 모델은 다음과 같은 단순한 그래프 분리를 통해 조건부 독립 관계를 정의한다. 노드의 집합 A, B, C에 대해, \mathbf{x}_{A} \perp_{G} \mathbf{x}_{B} | \mathbf{x}_{C}는 그래프 G에서 C가 A와 B를 분할하는 것을 나타내는 기호이다. 즉, C의 노드를 전부 제거하면, A의 노드로부터 B의 노드로 가는 경로가 없게 되어 조건부독립이 된다. 이는 비방향그래프 모델의 전역 마르코프 특성이라 한다.

노드 t에 대해 그 집합 밖의 모든 노드에 대해 t가 조건부 독립이 되는 최소 집합을 마르코프 담요 \mathrm{mb}(t)라고 한다. 이는 \mathrm{cl}(t) = \mathrm{mb}(t) \cup \{ t \} 이 노드 t의 폐포일 때 t \perp \mathcal{V}  \setminus \mathrm{cl}(t) | \mathrm{mb}(t) 이 성립한다. 비방향그래프 모델에서 노드의 마르코프 담요는 근접한 이웃들과 같다. 이를 비방향 지역적 마르코프 특성이라 한다.

지역적 마르코프 특성으로부터, 두 노드 사이의 직접적 간선이 없으면 그 노드들은 조건부 독립이다. 이를 쌍별 마르코프 특성이라 하며, s \perp t | \mathcal{V} \setminus \{ s, t \} \Leftrightarrow G_{st} = 0으로 나타낸다.

전역 마르코프 특성, 지역 마르코프 특성, 쌍별 마르코프 특성은 셋 다 동치이다.

19.2.2. An undirected alternative to d-separation

비방향그래프모델에서는 조건부독립 관계를 밝히는 것이 방향그래프모델보다 훨씬 쉽다. 하지만 방향그래프모델에서 간선의 방향만 없앤다고 비방향그래프모델이 되는 것은 아니다. 정확한 변환을 위해서는 먼저 방향그래프에서 해당 비방향그래프에 속한 노드들과 그 조상을 제거해 조상 그래프를 만든다. 이에 대해 연결되지 않은 노드간 간선을 추가해야 하는데 이를 교화라고 한다. 그 이후 비방향그래프모델에 대한 그래프 분리 규칙을 적용하면 된다.

19.2.3. Comparing directed and undirected graphical models

비방향그래프모델과 방향그래프모델 중 어느 것이 더 표현력이 있는가? 이를 위해서는 먼저 그래프 G는 분포 p에 대해 I(G) \subseteq I(p)이면 p의 I-map이라 함을 상기시키자. I(G) = I(p)이면 G를 p의 완전 맵이라 한다. 즉, 그래프 G가 p의 조건부독립 정보를 정확히 표현하는 것이다. 비방향그래프모델과 방향그래프모델은 완전 맵이 되는 분포가 서로 다르기 때문에 어느 것이 더 표현력이 있다고 말할 수는 없다. 비방향그래프모델은 v자 구조를 가진 관계를 정확히 모델링할 수 없다. 방향그래프모델은 4-사이클 같은 관계를 정확히 모델링할 수 없다. 어떤 모델들은 비방향그래프모델과 방향그래프모델 모두로 정확히 모델링할 수 있는데 이를 분해 가능 또는 현형이라고 한다. 대충 이야기하자면, 그래프 내 변수들을 모두 최대 클리크로 몰아넣을 때 해당 그래프가 트리가 될 경우이다. 이미 트리라면 당연히 이 그래프는 분해 가능해진다.

19.3. Paremetrization of MRFs

비방향그래프모델의 조건부독립 특성이 방향그래프모델보다 더 단순하지만, 결합분포를 나타내는 것은 그렇게 자연스럽지는 않다.

19.3.1. The Hammersley-Clifford theorem

비방향그래프에 대해서는 위상 정렬의 개념이 존재하지 않으므로, 연쇄법칙을 통해 p(\mathbf{y})를 표현할 수는 없다. 그러므로 각 노드에 대해 조건부확률분포를 연관시키는 대신에, 그래프 내의 최대 클리크마다 잠재 함수 또는 인자들을 대응시킨다. 이를 클리크 c에 대해 \psi_{c}(\mathbf{y}_{c} | \mathbf{\theta}_{c})로 표현한다. 이는 매개변수에 대한 임의의 음이 아닌 함수가 될 수 있다. 이후 결합분포는 클리크 잠재 함수의 곱에 비례하는 함수로 정의한다. 비방향그래프 모델로 모델링되는 모든 양의 분포는 이런 식으로 표현할 수 있다.

Theorem (Hammersley-Clifford). 양의 분포 p(\mathbf{y}) > 0이 비방향그래프모델 G의 조건부독립 관계를 만족하는 것은, p가 그 최대 클리크의 어떠한 인자 함수들의 곱 p(\mathbf{y} | \mathbf{\theta}) = \frac{1}{Z(\mathbf{\theta})} \prod_{c \in \mathcal{C}} \psi_{c} (\mathbf{y}_{c} | \mathbf{\theta}_{c})으로 나타내어지는 것과 동치이다. (\mathcal{C}는 그래프 내 최대 클리크들의 집합, Z(\mathbf{\theta}) = \sum_{\mathbf{y}} \prod_{c \in \mathcal{C}} \psi_{c} (\mathbf{y}_{c} | \mathbf{\theta}_{c})은 표준화 계수)

비방향그래프 모델과 통계물리학은 깊은 관계가 있다. 예를 들어, 깁스 분포 p(\mathbf{y} | \mathbf{\theta}) = \frac{1}{Z(\mathbf{\theta})} e^{-\sum_{c} E(\mathbf{y}_{c} | \mathbf{\theta}_{c})}\psi_{c}(\mathbf{y}_{c} | \mathbf{\theta}_{c}) = e^{-E(\mathbf{y}_{c} | \mathbf{\theta}_{c})}로 정의함으로써 비방향그래프모델로 바꿀 수 있다. 높은 확률 상태는 낮은 에너지 상에 대응하는데, 이런 형태의 모델을 에너지 기반 모델이라 한다.

그래프의 간선에 대한 매개화는 꼭 최대 클리크로 하지 않을 수도 있다. 이를 쌍별 마르코프 무작위 장이라 한다.

19.3.2. Representing potential functions

변수들이 이산적인 경우에는 잠재나 에너지 함수들을 음이 아닌 수의 테이블로 만들 수 있다. 하지만 이 경우에 잠재 함수는 확률이 아니라 상대적인 친화도를 나타내게 된다. 더 일반적인 접근법은 잠재 함수의 로그를 매개변수의 선형 함수 \log \psi_{c} (\mathbf{y}_{c}) = \mathbf{\psi}_{c} (\mathbf{y}_{c})^{T} \mathbf{\theta}_{c}로 나타내는 것이다. 이 때 \mathbf{\psi}_{c} (\mathbf{y}_{c})\mathbf{y}_{c}로부터 유도되는 특성 벡터이다. 계산되는 로그 확률은 \log p(\mathbf{y} | \mathbf{\theta}) = \sum_{c} \mathbf{\psi}_{c} (\mathbf{y}_{c})^{T} \mathbf{\theta}_{c} - \log Z(\mathbf{\theta}) 이 되는데, 이를 최대 엔트로피 또는 로그-선형 모델이라 한다.

예를 들어, 영어 스펠링 검사를 트리그램으로 할 때 경우의 수는 17576개가 있지만 ing, qu- 등의 자주 등장하는 3글자 외에 다른 조합은 거의 등장하지 않는다. 그러므로 17576개의 경우를 모두 고려하는 것보다는 자주 등장하는 조합에 대해서만 이진 특성 함수를 만들어서 이들을 조합하는 것이 낫다. 이러한 특성 함수들은 도메인 지식을 반영해 직접 만들어질 수도 있지만 데이터로부터 학습될 수도 있다.

19.4. Examples of MRFs

19.4.1. Ising model

아이싱 모델은 통계물리학에서 등장하는 마르코프 무작위 장의 예이다. 원자의 스핀을 y_{s} \in \{ -1, +1 \}이라 하면, 강자성체에서는 근접한 스핀이 같은 방향으로 위치하고, 반강자성체에서는 근접한 모델이 다른 방향으로 위치하는 경향이 있다. 강자성체는 마르코프 무작위 장으로 모델링할 수 있는데, 쌍별 클리크 잠재 함수를 e^{w_{st}}, e^{-w_{st}}를 엔트리로 갖는 행렬로 모델링한 뒤 w_{st} > 0으로 잡으면 된다. 이를 연관 마르코프 망이라 하며 가중치가 적절히 강하다면 대응되는 확률분포는 두 개의 최빈값을 갖는데 이를 계의 바닥 상태라 한다. 반대로 w_{st} < 0으로 잡으면 반강자성체를 모델링하게 되며, 좌절 계를 모델링하게 된다. 분할 함수 Z(J)를 계산하는 것은 연관 마르코프 망에 대해서는 다항 시간 안에 구할 수 있지만 일반적으로는 NP-난해이다.

아이싱 모델과 가우시안 그래프 모델과는 흥미로운 연관성이 있다.

가끔은 스핀에 대한 에너지 항 -\mathbf{b}^{T} \mathbf{y} (여기서 \mathbf{b}편향)인 외부 장이 작용할 수도 있다. 이 경우 아이싱 모델의 확률은 가우시안과 비슷한 형태인 \hat{p}(\mathbf{y}) \propto e^{-\frac{1}{2} (\mathbf{y} - \mathbf{W} \mathbf{b})^{T} \mathbf{W}^{-1} (\mathbf{y} - \mathbf{W} \mathbf{b}) + c} 의 형태로 나타낼 수 있다. 가우시안과 다른 점은 표준화 계수를 구할 때 가우시안은 O(D^{3}) 시간에 구할 수 있으나 아이싱 모델에 대해서는 O(2^{D}) 시간이 걸린다는 점이다.

19.4.2. Hopfield networks

홉필드 망은 가중치가 대칭이고 완전 연결된 아이싱 모델이다. 이 가중치와 편향은 훈련 데이터로부터 학습될 수 있다. 홉필드 망의 적용은 연관 기억 또는 연상 기억 장치이다. 발상은, 우리가 학습하고 싶은 패턴에 대응하는 완전히 관측된 비트 벡터를 학습한 뒤, 테스팅 시점에 부분적 패턴이 주어졌을 때 이 패턴을 완성시키는 것이다. 이를 패턴 완성이라 한다.

이 모델에서 정확한 추론은 계산 가능하지 않기 때문에, 반복적 조건부 최빈값 알고리즘을 사용한다. 이 추론은 결정론적이므로, 이 모델을 재귀 신경망으로 나타낼 수도 있다.

볼츠만 기계는 홉필드/아이싱 모델에 은닉 노드를 몇 개 추가시켜 일반화한 것이다.

홉필드 망의 적용 예.

19.4.3. Potts model

아이싱 모델을 여러 개의 이산적 상태에 대해 일반화시킨 것을 파츠 모델이라 한다. 파츠 모델에는 임계값이 존재해서 이 값을 경계로 클러스터들의 크기가 작은 클러스터에서 큰 클러스터로 급격히 달라지는 상전이가 일어난다. 이 모델은 이미지 세그멘테이션의 사전분포로 쓰일 수 있다. 인접한 픽셀은 같은 분할로 라벨링될 수 있기 때문이다. 이 사전분포를 가능도와 결합시키면 다음을 얻는다:

p(\mathbf{y}, \mathbf{x} | \mathbf{\theta}) = [\frac{1}{Z(J)} \prod_{s \sim t} \psi(y_{s}, y_{t} ; J)] \prod_{t} p(x_{t} | y_{t}, \mathbf{\theta})

이 관측 모델은 가우시안이나 비매개변수 밀도함수로 모델링될 수 있다. 대응되는 그래프 모델은 방향이 있는 간선인 국소적 증거와 없는 간선의 혼합인 연쇄 그래프가 된다. 이 모델은 은닉 마르코프 모델의 2차원 버전이라고 볼 수 있으며 부분적으로 관측된 마르코프 무작위 장이라고 부를 수도 있다. 은닉 마르코프 모델처럼, 목표는 사후예측분포를 수행하는 것이다. 2D 모델은 1D 모델보다 훨씬 어려우므로 근사적인 방법을 사용한다.

파츠 사전분포는 지도 이미지 세그멘테이션에는 적합하지만, 비지도 이미지 세그멘테이션을 진행하는 데는 적합하지 않다. 임의의 자연적 이미지에서 볼 수 있는 세그먼트를 모델링하지 못하기 때문이다. 비지도학습의 경우에는 절단된 가우시안 과정 사전분포 등을 사용한다.

파츠 모델의 적용 예.

19.4.4. Gaussian MRFs

비방향 가우시안 그래프 모델은 가우시안 마르코프 무작위 장이라고도 불린다. 이는 다음 형태의 쌍별 마르코프 무작위 장이다.

p(\mathbf{y} | \mathbf{\theta}) \propto \prod_{s \sim t} \psi_{st} (y_{s}, y_{t}) \prod_{t} \psi_{t} (y_{t})

\psi_{st}(y_{s}, y_{t}) = e^{-\frac{1}{2} y_{s} \Lambda_{st} y_{t}}

\psi_{t}(y_{t}) = e^{-\frac{1}{2} \Lambda_{tt} y_{t}^{2} + \eta_{t} y_{t}}

이 때 노드 잠재 함수 \psi_{t}를 간선 잠재 함수로 흡수시킬 수 있지만 의미상의 명확한 구분을 위해 그렇게 하지 않았다. 결합분포는 다음과 같다:

p(\mathbf{y} | \mathbf{\theta}) \propto e^{\mathbf{\eta}^{T} \mathbf{y} - \frac{1}{2} \mathbf{y}^{T} \mathbf{\Lambda} \mathbf{y}}

이는 정보형의 다변수 가우시안이 됨을 알 수 있다. \Lambda_{st} = 0이라면, s와 t를 연결하는 쌍별 항이 존재하지 않는 것이므로 y_{s} \perp y_{t} | \mathbf{y}_{-(st)}과 동치이다. 그래서 \mathbf{\Lambda} 내의 0인 항들은 구조적 영이라고 불린다. 즉, 비방향 가우시안 그래프 모델은 희소한 정밀도 행렬에 대응된다. 학습 시에 이러한 특성을 이용할 수 있다.

19.4.4.1. Comparing Gaussian DGMs and UGMs

방향 가우시안 그래프 모델은 희소한 회귀 행렬에 대응하고, 비방향 가우시안 그래프 모델은 희소한 정밀도 행렬에 대응한다. 방향그래프 표현의 장점은 회귀 행렬을 공분산 정보량에 대해 표현할 수 있다는 것이다. 단점은 그래프 내 간선들의 방향이 변수간의 자연적 관계를 잘 표현하지 못할 수 있다는 것이다. 방향그래프 표현과 비방향그래프 표현을 결합시켜 가우시안 연쇄 그래프로 나타낼 수 있다. 예를 들어 벡터 자동 회귀(VAR) 등의 모델이 계량 경제학에 쓰일 수 있다.

시계열은 대부분 방향 가우시안 그래프 모델로 모델링되지만, \mathbf{\Sigma}^{-1}이 희소하다면 비방향 가우시안 그래프 모델로 모델링할 수도 있다.

어떨 때는 희소한 정밀도 행렬 대신 희소한 공분산 행렬이 존재할 때도 있다. 이럴 때는 공분산 그래프로서 각 간선이 양방향으로 연결된 양방향 그래프를 사용하는데, 이 때 연결되지 않은 간선은 비조건부 독립이 된다.

양방향 그래프는 잠재 변수가 있는 비순환 방향그래프로 변환할 수 있다. 이 때 양방향 간선은 은닉 공동 원인 (혼동자)으로 대체된다. 연관된 조건부독립 특성은 d-분할로 판정할 수 있다.

양방향 간선과 방향 간선을 결합해 방향 혼합 그래프 모델을 만들 수 있다.

19.4.5. Markov logic networks

오브젝트가 가변 개수만큼 있을 때 상호 관계를 모델링하려면 어떻게 할까? 이런 모델은 일차 논리식을 사용한다. 이는 항상 사용할 수는 없으므로 통계적 관계형 인공지능이나 확률적 관계 모델링 등에서 확률론과 결합해 쓰인다. 간단한 접근법은 일차논리 각각에 가중치 (명확성 인자)를 부여해 조건부 확률분포로 나타내는 것이다. 하지만 결과 그래프가 비순환 방향 그래프로 나타내어진다는 보장은 없으므로 결합 분포가 일관적이지 않다.

또 다른 방법은 각각의 일차논리를 비방향그래프 모델에 대한 잠재 함수를 정의하는 데 사용하는 것이다. 이를 마르코프 논리망이라 하며, 이 때 모든 일차논리는 결합 정규형 또는 절형으로 다시 쓰여진다.

일차논리에서의 추론은 비결정론적이므로 언어를 호른 절로 제한시키고는 한다. 이는 모델이 연속된 if-then 규칙으로 분해됨을 의미한다. 이렇게 우리의 기반 지식을 절들로 분해하고 나면 각각에 가중치를 부여할 수 있다. 이는 \psi_{c}(\mathbf{x}_{c}) = e^{w_{c} \phi_{c}(\mathbf{x}_{c})}의 형태로 클리크 잠재 함수를 정의한다.

즉, 우리는 상수 심볼들에 대한 이진 변수를 통해 그라운드 망을 만드는 것이다. 마르코프 논리망을 비방향그래프모델 템플릿을 특정하는 편리한 식으로 볼 수도 있다. 이는 열린 우주 모델 등에 쓰인다.

19.5. Learning

마르코프 무작위 망에 대한 최대가능도 또는 최대사후확률추정은 대체로 연산량을 많이 쓴다. 그래서 마르코프 무작위 망에 대한 베이지안 추론은 잘 하지 않는다.

19.5.1. Training maxent models using gradient methods

다음의 로그-선형 꼴의 마르코프 무작위 장을 고려해 보자. (c는 클리크의 인덱스)

p(\mathbf{y} | \mathbf{\theta}) = \frac{1}{Z(\mathbf{\theta})} e^{\sum_{c} \mathbf{\theta}_{c}^{T} \mathbf{\phi}_{c}(\mathbf{y})}

로그 가능도는 다음과 같다.

l(\mathbf{\theta}) = \frac{1}{N} \sum_{i} [\sum_{c} \mathbf{\theta}_{c}^{T} \mathbf{\phi}_{c} (\mathbf{y}_{i}) - \log Z(\mathbf{\theta})]

마르코프 무작위 장은 지수족이므로, \mathbf{\theta}에 대해 볼록함수가 되어 경사 기반 최적화를 사용할 때 유일한 전역 최적해를 갖는다. 이 때 클리크 c에 대한 가중치의 도함수는 다음과 같다.

\frac{\partial l}{\partial \mathbf{\theta}_{c}} = \frac{1}{N} \sum_{i} [\mathbf{\phi}_{c} (\mathbf{y}_{i}) - \frac{\partial}{\partial \mathbf{\theta}_{c}} \log Z(\mathbf{\theta})]

로그 분할 함수의 도함수는 다음과 같다.

\frac{\partial \log Z(\mathbf{\theta})}{\partial \mathbf{\theta}_{c}} = \mathbb{E}[\mathbf{\phi}_{c}(\mathbf{y}) | \mathbf{\theta}] = \sum_{\mathbf{y}} \mathbf{\phi}_{c} (\mathbf{y}) p(\mathbf{y} | \mathbf{\theta})

따라서 로그가능도의 경사는 다음과 같게 된다.

\frac{\partial l}{\partial \mathbf{\theta}_{c}} = [\frac{1}{N} \sum_{i} \mathbf{\phi}_{c} (\mathbf{y}_{i})] - \mathbb{E}[\mathbf{\phi}_{c} (\mathbf{y})]

첫 번째 항에서는 \mathbf{y}가 관측된 값으로 고정되어 고정된 항으로도 불린다. 두 번째 항에서는 그런 제한이 없으므로 비고정 항 또는 대조항으로 불린다. 비고정 항을 구할 때에는 모델을 통한 추론이 필요하고 이것은 경사 하강법을 할 때마다 해주어야 하기 때문에 비방향그래프 모델은 방향그래프 모델보다 훨씬 학습이 느리다.

로그가능도의 경사는 다음과 같이 쓸 수도 있다.

\frac{\partial l}{\partial \mathbf{\theta}_{c}} = \mathbb{E}_{p_{\mathrm{emp}}}[\mathbf{\phi}_{c} (\mathbf{y})] - \mathbb{E}_{p(\dot | \mathbf{\theta})}[\mathbf{\phi}_{c} (\mathbf{y})]

최적해에서는 경사가 0이므로, 특성의 실측 분포가 예측값과 맞아떨어지게 된다고 볼 수 있다.

\mathbb{E}_{p_{\mathrm{emp}}}[\mathbf{\phi}_{c} (\mathbf{y})] = \mathbb{E}_{p(\dot | \mathbf{\theta})}[\mathbf{\phi}_{c} (\mathbf{y})]

이를 모멘트 매칭이라 한다.

19.5.2. Training partially observed maxent models

유실되거나 은닉된 데이터나 변수가 모델에 존재한다고 가정해보자. 이 경우 모델은 다음과 같이 표현할 수 있다.

p(\mathbf{y}, \mathbf{h} | \mathbf{\theta}) = \frac{1}{Z(\mathbf{\theta})} e^{\sum_{c} \mathbf{\theta}_{c}^{T} \mathbf{\phi}_{c} (\mathbf{h}, \mathbf{y})}

\hat{p}(\mathbf{y}, \mathbf{h} | \mathbf{\theta}) = e^{\sum_{c} \mathbf{\theta}_{c}^{T} \mathbf{\phi}_{c} (\mathbf{h}, \mathbf{y})}이라 할 때 로그 가능도는 다음과 같다.

l(\mathbf{\theta}) = \frac{1}{N} \sum_{i = 1}^{N} \log (\frac{1}{Z(\mathbf{\theta})} \sum_{\mathbf{h}} \hat{p}(\mathbf{y}_{i} , \mathbf{h} | \mathbf{\theta}))

내부의 항은 전체 모델의 분할 함수를 \mathbf{y}\mathbf{y}_{i}에 고정시킨 것이다. 그러므로 경사는 \mathbf{y}\mathbf{y}_{i}에 고정시킨 뒤 \mathbf{h}에 대해 평균낸 특성 기대값과 같다.

\frac{\partial}{\partial \mathbf{\theta}_{c}} \log (\sum_{\mathbf{h}}\hat{p}(\mathbf{y}_{i} , \mathbf{h} | \mathbf{\theta}) ) = \mathbb{E}[\mathbf{\phi}_{c} (\mathbf{h}, \mathbf{y}_{i}) | \mathbf{\theta}]

그러므로 전체 경사는 다음과 같다.

\frac{\partial l}{\partial \mathbf{\theta}_{c}} = \frac{1}{N} \sum_{i} [\mathbb{E}[\mathbf{\phi}_{c} (\mathbf{h}, \mathbf{y}_{i}) | \mathbf{\theta}] - \mathbb{E}[\mathbf{\phi}_{c} (\mathbf{h}, \mathbf{y}) | \mathbf{\theta}]]

즉 내부 항은 \mathbf{y}\mathbf{y}_{i}로 고정시킨 기대값과 고정시키지 않은 기대값의 차를 \mathbf{h}_{i}에 대해 평균낸 것이라고 볼 수 있다.

다른 방법은 일반화된 기대값 최대화 방법을 쓰는 것이다. 이 때 M 단계에서 경사법을 쓴다. 정확한 추론이 불가능할 경우에는 근사적 추론을 수행한다.

19.5.3. Approximate methods for computing the MLEs of MRFs

비방향그래프 모델을 피팅할 때에는 일반적으로 최대가능도추정이나 최대사후확률추정을 닫힌 꼴로 구할 수 없으므로 경사 기반 최적화법을 사용해야 한다. 이는 추론을 필요로 하는데, 추론이 계산 가능하지 않은 모델에서는 학습 또한 계산 불가능해진다. 그래서 근사적인 추정을 접목시키는 것이 필요하다.

19.5.4. Pseudo likelihood

최대가능도추정에 대한 대안은 다음의 유사가능도를 최대화시키는 것이다.

l_{\mathrm{PL}}(\mathbf{\theta}) = \sum_{\mathbf{y}} \sum_{d=1}^{D} p_{\mathrm{emp}}(\mathbf{y}) \log p(y_{d} | \mathbf{y}_{-d}) = \frac{1}{N} \sum_{i=1}^{N} \sum_{d=1}^{D} \log p(y_{id} | \mathbf{y}_{i, -d}, \mathbf{\theta})

즉, 조건부 밀도함수의 곱인 합성 가능도를 최적화시키는 것이다. 가우시안 마르코프 무작위 장의 경우에는 유사가능도는 최대가능도추정과 같지만, 일반적으로는 같지 않다. 이는 각각 조건부 밀도함수를 구하는 데에 있어 단일 노드의 상태들만을 필요로 하기 때문에 계산 측면에서도 더 빠르다.

유사 가능도의 문제점은 은닉 변수가 있는 모델에 적용하기 힘들다는 것이다. 또한, 각 노드들이 인접한 노드들의 값을 알아야 한다는 문제도 있다. 만약 인접한 노드들이 완전한 학습기라면 인접한 노드들의 값만으로 해당 노드의 유사가능도를 국소적 증거 없이 구할 수 있기는 하다. 유사가능도는 전체 관측된 아이싱 모델에 대해서는 정확한 최대가능도추정과 비슷한 성능을 내지만, 훨씬 빠르다.

19.5.5. Stochastic maximum likelihood

전체가 관측된 마르코프 무작위 망의 로그 가능도의 경사는 다음과 같다.

\nabla_{\mathbf{\theta}} l(\mathbf{\theta}) = \frac{1}{N} \sum_{i} [\mathbf{\phi}(\mathbf{y}_{i}) - \mathbb{E}[\mathbf{\phi}(\mathbf{y})]]

부분적으로 관측된 마르코프 무작위 망에 대한 경사도 비슷하다. 두 경우 모두, 모델 기대값에 대한 근사는 몬테 카를로 표본 추출을 통해 진행한다. 이것과 실측 분포에서 표본을 추출하는 추계적 경사 하강법을 결합하는 것이 이 알고리즘이다.

물론, 각 반복문마다 마르코프 연쇄 몬테 카를로를 적용하는 것은 대단히 느리다. 다행히도, 마르코프 연쇄 몬테 카를로를 이전 값에서 시작해서 몇 단계만 진행하는 것만으로도 충분하다. 즉, \mathbf{y}_{s, k}를 마르코프 연쇄 몬테 카를로법을 \mathbf{y}_{s, k - 1}로 초기값을 줌으로부터 시작해서 몇 단계를 수행하면 되는 것이다. 이는 p(\mathbf{y} | \mathbf{\theta}_{k})p(\mathbf{y} | \mathbf{\theta}_{k - 1})과 별 차이가 없는 값이기 때문에 가능한 방법이다. 이를 추계적 최대가능도(SML)라 한다.

19.5.6. Feature introduction for maxent models

마르코프 무작위 망은 좋은 특성 집합을 필요로 한다. 이런 특성을 학습하는 비지도 방식은 특성 귀납이라 하는데, 기본 특성 집합으로부터 연속적으로 새로운 특성들을 탐욕적 알고리즘으로 최선의 특성을 하나씩 추가해 얻어내는 것이다. 영어 스펠링 교정의 예로, 글자 뭉치에서 최적의 한 글자씩을 추가해 나가는 것을 예로 들 수 있다. 이러한 접근법은 그래프 모델 구조 학습의 형태로 생각할 수 있지만, 결과 그래프가 조밀하게 연결되어 있으므로 추론과 매개변수 추정이 계산 가능하지 않아진다는 점이 다르다.

19.5.7. Iterative proportional fitting (IPF)

잠재 함수가 테이블로 나타내어지는 쌍별 마르코프 무작위 장을 생각해 보자. 이는 다음의 로그-선형 꼴로 나타낼 수 있다.

\phi_{st}(y_{s}, y_{t}) = e^{\mathbf{\theta}_{st}^{T} [\mathbf{1}_{y_{s} = 1, y_{t} = 1}, \cdots, \mathbf{1}_{y_{s} = K, y_{t} = K}]}

\phi_{t}에 대해서도 비슷하다. 즉 특성 벡터들이 그냥 지시자 함수인 것이다. 이 때 최대가능도 근사에서는 특성의 실측 기대값이 모델의 기대값과 같아진다.

p_{\mathrm{emp}}(y_{s} = j, y_{t} = k) = p(y_{s} = j, y_{t} = k | \mathbf{\theta})

즉 일반적인 그래프에 대해서는 최적해에 대해 다음이 성립해야 한다.

p_{\mathrm{emp}}(\mathbf{y}_{c}) = p(\mathbf{y}_{c} | \mathbf{\theta})

분해 가능한 그래프에서는 클리크마다 p(\mathbf{y}_{c} | \mathbf{\theta}) = \phi_{c}(\mathbf{y}_{c})이 성립한다. 분해가 가능하지 않더라도 다음의 반복적 알고리즘을 사용할 수 있다:

\phi_{c, t+1}(\mathbf{y}_{c}) = \phi_{c, t}(\mathbf{y}_{c}) \frac{p_{\mathrm{emp}} (\mathbf{y}_{c})}{p(\mathbf{y}_{c} | \phi_{t})}

이를 반복적 비례 피팅(IPF)이라 한다.

19.5.7.1. Example

남/녀의 왼손잡이/오른손잡이 비율을 학습하는 예가 있다.

19.5.7.2. Speed of IPF

반복적 비례 피팅은 모멘트 매칭을 강제하는 고정점 알고리즘이고 전역 최적해로 수렴함이 보장되어 있다. 시행해야 하는 반복의 수는 모델의 형태에 따라 다르다. 그래프가 분해 가능 하다면 한 번의 반복으로 수렴하지만, 일반적으로는 여러 번의 반복을 필요로 한다. 반복적 비례 피팅의 계산량의 대부분을 차지하는 부분은 모델의 주변분포를 계산하는 것이다. 정션 트리같은 알고리즘을 적용하는 효율적 반복적 비례 피팅 등의 알고리즘이 알려져 있다. 그럼에도 불구하고, 좌표 하강법은 느릴 수 있다. 대안은 모든 매개변수를 한 번에 업데이트하는 대신, 가능도의 경사를 따라가게 하는 방법이 있다. 이는 클리크 잠재 함수가 완전히 매개화되지 않은 경우에도 사용할 수 있다는 장점이 있다. 즉, 특성들이 지시자 함수가 아니라 다른 임의의 함수여도 가능하다는 것이다. 반복적 스케일링 등의 방법을 사용하면 반복적 비례 피팅을 적용할 수 있지만, 경사 하강법이 훨씬 빠르다.

19.5.7.3. Generalizations of IPF

반복적 비례 피팅을 사용해 가우시안 그래프 모델을 피팅할 수 있다. 실측 횟수를 다루는 대신, 실측 평균과 공분산을 쓰면 된다. 모델의 매개변수의 사후분포로부터 샘플링을 해서 베이지안 반복적 비례 피팅을 수행할 수도 있다.

19.5.7.4. IPF for decomposable graphical models

비방향그래프모델의 특별한 케이스로 분해 가능한 그래프 모델들이 있다. 이는 거칠게 말하자면 트리와 비슷한 구조의 그래프 모델들이다. 이런 그래프들은 비방향그래프모델이나 방향그래프모델 어느 쪽으로도 정보의 손실 없이 표현될 수 있다. 분해 가능한 그래프 모델의 경우에는 반복적 비례 피팅이 한 번의 반복으로 수렴한다. 이 경우 테이블 잠재 함수는 \hat{\phi}_{c}(\mathbf{y}_{c} = k) = \frac{\sum_{i=1}^{N} \mathbf{1}_{\mathbf{y}_{i, c} = k}}{N} 가 된다.

가우시안 잠재 함수의 경우에는 \hat{\mathbf{\mu}}_{c} = \frac{\sum_{i=1}^{N} \mathbf{y}_{ic}}{N}, \hat{\mathbf{\Sigma}}_{c} = \frac{\sum_{i=1}^{N} (\mathbf{y}_{ic} - \hat{\mathbf{\mu}}_{c})(\mathbf{y}_{ic} - \hat{\mathbf{\mu}}_{c})^{T}}{N}이 된다.

이 경우 켤레사전분포를 통해, 모델의 전체 사후분포를 계산할 수도 있다.

19.6. Conditional random fields (CRFs)

조건적 무작위 장(CRF) 또는 구별적 무작위 장은 마르코프 무작위 장이 입력 특성에 대해 조건이 걸린 것이다.

p(\mathbf{y} | \mathbf{x}, \mathbf{w}) = \frac{1}{Z(\mathbf{x}, \mathbf{w})} \prod_{c} \phi_{c} (\mathbf{y}_{c} | \mathbf{x}, \mathbf{w})

조건적 무작위 장은 로지스틱 회귀에 구조적 출력이 적용된 확장이라고 생각할 수 있으며, 입력 특성에 조건이 걸린 출력 라벨간의 상관 관계를 모델링한다. 잠재 함수들은 대개 로그-선형 표현식을 가정한다.

\phi_{c}(\mathbf{y}_{c} | \mathbf{x}, \mathbf{w}) = e^{\mathbf{w}_{c}^{T} \mathbf{\phi}(\mathbf{x}, \mathbf{y}_{c})}

여기서 \mathbf{\phi}(\mathbf{x}, \mathbf{y}_{c})은 전역 입력 \mathbf{x}와 라벨의 지역적 집합 \mathbf{y}_{c}로부터 유도된 특성 벡터이다.

조건적 무작위 장이 마르코프 무작위 장에 대해 갖는 이점은 구별적 분류기가 생성적 분류기에 비해 갖는 이점과 비슷하다. 즉, 항상 관측이 가능한 데이터를 생성하는 모델링을 하는 대신 데이터의 분류에 대해 더 신경을 쓰는 것이다. 조건적 무작위 장의 또 다른 중요한 이점은 잠재 함수를 데이터에 의존적으로 만들 수 있다는 것이다. 예를 들어, 이미지 프로세싱을 할 때에는 두 픽셀간 연결이 없는 것이 분명할 경우 드 노드간의 레이블 다듬질을 건너뛸 수 있다. 비슷하게, 자연어 처리 문제에서, 잠재 변수들을 문장의 전역적 특성 (어느 언어로 쓰여졌는지 등)으로 제한시킬 수 있다. 생성적 분류기에 대해서는 이런 방법들을 적용하기가 힘들다.

조건적 무작위 장이 마르코프 무작위 장에 대해 갖는 단점은 학습이 더 느리고, 라벨링된 학습 데이터를 필요로 한다는 것이다. 이는 로지스틱 회귀와 나이브 베이즈간 차이점과 비슷하다.

19.6.1. Chain-structured CRFs, MEMMs and the label-bias problem

가장 널리 사용되는 조건적 무작위 장은 인접 라벨간의 상호 연관을 모델링하는 연쇄 구조 그래프이다. 이런 그래프는 순차적 라벨링 작업에 유용한데, 이런 작업들에는 전통적으로 은닉 마르코프 모델들이 p(\mathbf{x}, \mathbf{y} | \mathbf{w}) = p(y_{1}) \prod_{t=1}^{T} p(y_{t} | y_{t-1}, \mathbf{w})p(\mathbf{x}_{t} | y_{t}, \mathbf{w})의 결합분포 형태로 많이 쓰였다. \mathbf{x}_{t}y_{t}가 모두 관측가능할 경우 이러한 형태의 모델은 학습시키기 쉽다.

은닉 마르코프 모델의 구별적 버전을 만드는 방법은 \mathbf{x}_{t}y_{t}간의 인과관계를 역전시키는 것이다. 이렇게 하면 p(\mathbf{y} | \mathbf{x}, \mathbf{w}) = \prod_{t} p(y_{t} | y_{t-1}, \mathbf{x}, \mathbf{w}) 형태의 구별적 모델을 정의한다. 이 때 \mathbf{x}_{t}는 노드 t에 대한 특성이고 \mathbf{x}_{g}는 전역적 특성으로서 \mathbf{x} = (\mathbf{x}_{1 : T} ,\mathbf{x}_{g})은 전체 특성이 된다. 이를 최대 엔트로피 마르코프 모델(MEMM)이라 한다.

최대 엔트로피 마르코프 모델은 상전이 확률이 입력 특성에 조건이 걸린 마르코프 연쇄이다. 그러므로 입-출력 은닉 마르코프 모델의 특수한 경우라고 볼 수 있다. 이는 라벨 편향이라는 문제를 겪는데, 즉, 시점 t에서의 지역적 특성이 시점 t 이전의 상태에 영향을 미치지 못하기 때문이다. 이는 문장 인식에서 앞의 단어가 뒤의 단어에 대한 정보를 제공할 수 있는 경우를 다루지 못하게 된다.

이제 연쇄 구조 조건적 무작위 장을 고려해 보자. 이는 p(\mathbf{y} | \mathbf{x}, \mathbf{w}) = \frac{1}{Z(\mathbf{x}, \mathbf{w})} \prod_{t=1}^{T} \phi(y_{t} | \mathbf{x}, \mathbf{w}) \prod_{t=1}^{T-1} \phi(y_{t}, y_{t+1} | \mathbf{x}, \mathbf{w})의 형태를 가진다. 이 경우에는 라벨 편향의 문제가 없는데, \mathbf{x}_{t}y_{t} 외 다른 노드에서도 정보를 얻을 수 있기 때문이다.

최대 엔트로피 마르코프 모델의 라벨 편향 문제는 방향그래프 모델이 지역적으로 표준화되었기 때문에 발생한다. 즉, 각 조건부확률분포가 합하면 1이 된다. 반면에, 마르코프 무작위 장과 조건적 무작위 장은 전역적으로 표준화된다. 즉, 지역적 인자들의 합이 1이 될 필요가 없다. 별도의 분할 함수가 존재하기 때문이다. 단점은 전체 지역적 인자들을 구하기 전까지 정확한 분포를 구할 수 없다는 점이다. 때문에 문장을 다 듣기 전에 문장 구조를 분석하는 등의 온라인이나 실시간 작업에는 쓸 수 없다. 그래서 조건적 무작위 장은 이런 경우에는 방향그래프 모델들보다 유용하지 않다. 또한 분할 함수 Z는 모든 노드에 의존하는 값이기 때문에 학습도 더 느리다.

19.6.2. Applications of CRFs

조건적 무작위 장의 용례를 알아보자.

19.6.2.1. Handwriting recognition

조건적 무작위 장의 용례는 손글씨 문자열 감지이다. 지역적으로는 글자를 알아보기 힘들 수 있으나, 그 글자들 옆에 있는 글자들을 알아내 오차율을 줄일 수 있다.

19.6.2.2. Noun phrase chunking

자연어 처리에서 명사구 단위화옅은 파싱에 조건적 무작위 장이 쓰인다. 즉, 각 문장을 BIO (명사구 시작, 명사구 내부, 명사구 밖)으로 분할하는 것이다. 전통적인 방법은 단어들의 문자열에 문장 성분 태깅을 하고, 이런 문장 성분 태깅을 명사구 태깅으로 전환하는 법이 있지만, 이런 파이프라인 법은 오차를 전파할 수도 있으므로, 문장 성분과 명사구에 대한 결합확률분포 모델을 만들기도 한다. 이 때 조건적 무작위 장이 쓰인다. 인접한 라벨간의 연결성은 BIO 상태간의 전이 확률을 저장하고, B가 I 앞에 와야 한다는 등의 조건을 강제한다. 이런 특성들은 단어가 대문자로 시작하는지, 명사인지 등을 따져 수작업으로 작성된다. 이런 특성들은 종류가 매우 많지만 관측되기만 할 뿐 합해질 필요는 없기 때문에 추론 시점에는 별 상관이 없다. 추론 시점에 큰 영향을 주는 것은 그래프 구조이다. 그래프 구조가 조금 달라짐에 따라서 추론이 계산 가능해질 수도 불가능해질 수도 있다.

19.6.2.3. Named entity recognition

명사구 단위화와 관계된 일은 개체명 추출이다. 명사구를 단지 의미 분할하는 것 말고도 인명과 지역명 등의 의미를 구분할 수 있다. 이를 정보 추출이라 한다. 간단한 접근법은 연쇄 구조 조건적 무작위 장을 사용하는 것이지만, 고유명사들은 열린 클래스에 속하기 때문에 다루기 어렵다. 이 때 단어들 간 장기적 연관성을 고려함으로써 정확도를 높일 수 있다. 즉, 같은 단어가 문장 내 등장했을 때 이들 간 연결을 해서 같은 태그를 매기든가 등의 방법을 쓰는 것이다. 이를 건너뛰기-연쇄 조건적 무작위 장이라 한다.

조건적 무작위 장이 생성적 모델에 대해 갖는 이점으로 그래프 구조가 입력에 따라 변한다는 것을 들 수 있다. 하지만, 추론 시 연산량은 더 많이 필요하다.

19.6.2.4. Natural langauge parsing

언어에 대한 연쇄 구조 모델의 일반화는 확률적 문법을 사용하는 것이다. 확률적 문맥 자유 문법(PCFG)을 통해 단어의 나열에 대한 확률분포를 정의한다. 특정 단어의 나열에 대한 확률은 그 단어를 생성하는 모든 트리에 대한 합을 구함으로써 얻을 수 있다. 이는 내부-외부 알고리즘을 통해 O(T^{3}) 시간에 계산할 수 있다.

확률적 문맥 자유 문법은 생성적 모델이며, p(\mathbf{y} | \mathbf{x}) \propto e^{\mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}, \mathbf{y})} 꼴의 조건부 무작위 장을 통해 라벨이 정해진 트리에 대한 확률을 저장하는 구별적 버전을 만들 수 있다.

19.6.2.5. Hierarchical classification

레이블 분류를 가진 다클래스 분류를 수행해 클래스간 계층을 군집화할 때, 계층 구조 내 노드의 위치를 이진 벡터에 저장할 수 있다. 이를 입력 특성과 텐서곱을 취하는 방법이 텍스트 분류에 널리 쓰인다. 이 방법의 이점은 인접한 분류의 매개변수간 정보가 공유된다는 것이다.

19.6.2.6. Protein side-chain prediction

단백질 구조 예측 문제에 건너뜀-연쇄 모델와 비슷한 모델이 쓰인다. 이 때 인접한 원소간의 쌍별 상호 반응에 대한 에너지 함수를 정의한 뒤 가장 확률 높은 단백질 구조를 계산한다. 이는 일반적으로 NP-난해 문제이지만, 특수한 경우들에 한해 효율적으로 계산될 수 있다.

19.6.2.7. Stereo vision

저레벨 시각 문제는 입력이 이미지이고 출력이 이미지의 처리 결과인 문제이다. 대부분 2D 격자 구조 모델을 쓰고, 쌍별 조건적 무작위 장을 가정한다.

고전적인 저레벨 시각 문제는 조밀 스테레오 재구성으로, 약간 다른 각도에서 찍힌 두 이미지를 바탕으로 각 픽셀의 깊이를 추정하는 것이다. 전처리 과정을 통해, 깊이 추정은 두 이미지 간 픽셀의 차이를 추정하는 문제로 변형될 수 있다. 이 때 노드의 국소적 잠재 함수를 \phi_{s}(y_{s} | \mathbf{x}) \propto e^{-\frac{1}{2 \sigma^{2}} (x_{L}(i_{s}, j_{s}) - x_{R}(i_{s} + y_{s}, j_{s}))^{2}} 형태로 정의할 수 있다. 이 모델은 픽셀 뿐만 아니라 이미지 내 특정한 위치를 노드로 잡아서 정의할 수도 있다. 텍스쳐가 높을 수록 상호 연관성 분석을 통해 두 이미지간 대응 관계를 찾아내기 쉬우며 텍스쳐가 낮으면 어려워진다.

이 때 사용하는 마르코프 무작위 장에 대해서 간선의 잠재 함수에 대해 \phi_{st}(y_{s}, y_{t}) \propto e^{-\frac{1}{2 \gamma^{2}} (y_{s} - y_{t})^{2}} 형태의 가우시안 사전분포를 쓸 수도 있지만, 문제점은 이러한 사전분포는 인접한 픽셀이 의미 경계로 명확히 구분되어 차이값이 커지는 경우를 다루지 못한다는 것이다. 때문에 대안으로 최대 징벌값 \delta_{0}을 정해 절단된 가우시안 잠재 함수 \phi_{st}(y_{s}, y_{t}) \propto e^{-\frac{1}{2 \gamma^{2}} \min ((y_{s} - y_{t})^{2}, \delta_{0})}을 사용할 수 있다. 이를 불연속 보존 잠재 함수라 한다. 이 잠재 함수는 볼록함수가 아님에 주의하라. 국소적 증거 잠재 함수도 비슷한 방식으로 강건하게 만들어 가림 등의 이상치를 다룰 수 있다.

실변수 함수에 대해 효과적인 추론을 하는 것은 결합분포가 가우시안이 아닌 이상 계산량이 많이 든다. 따라서 대개 변수를 이산화하고는 한다. 이를 계량형 조건적 무작위 장이라 하는데, 이산적 라벨에 자연적 순서가 없는 경우 더 효과적이다.

19.6.3. CRF training

조건적 무작위 장에 대한 경사 하강 기반 최적화는 마르코프 무작위 장에서 했던 것을 변형해서 얻을 수 있다. 로그 가능도는 다음과 같다.

l(\mathbf{w}) = \frac{1}{N} \sum_{i} \log p(\mathbf{y}_{i} | \mathbf{x}_{i}, \mathbf{w}) = \frac{1}{N} \sum_{i} [\sum_{c} \mathbf{w}_{c}^{T} \mathbf{\phi}_{c} (\mathbf{y}_{i}, \mathbf{x}_{i}) - \log Z(\mathbf{w}, \mathbf{x}_{i})]

경사는 다음과 같다.

\frac{\partial l}{\partial \mathbf{w}_{c}} = \frac{1}{N} \sum_{i} [\mathbf{\phi}_{c} (\mathbf{y}_{i}, \mathbf{x}_{i}) - \mathbb{E}[\mathbf{\phi}_{c}(\mathbf{y}, \mathbf{x}_{i})]]

이는 각 경사 단계 내의 각 훈련 샘플마다 추론을 수행해야 하기 때문에, 마르코프 무작위 장에 비해 O(N)배 느리다. 분할 함수가 모든 \mathbf{x}_{i}에 의존하기 때문이다.

조건적 무작위 장의 대부분의 용례에서 그래프 구조의 크기는 변화할 수 있다. 때문에 임의 크기의 분포를 정의하기 위해서 매개변수를 고정시키고는 한다. 이 때 모델은 다음과 같다.

p(\mathbf{y} | \mathbf{x}, \mathbf{w}) = \frac{1}{Z(\mathbf{w}, \mathbf{x})}e^{\mathbf{w}^{T} \mathbf{\phi}(\mathbf{y}, \mathbf{x})}

여기서 \mathbf{w} = [\mathbf{w}_{n}, \mathbf{w}_{c}]은 노드와 간선 매개변수이고, \mathbf{\phi}(\mathbf{y}, \mathbf{x}) = [\sum_{t} \mathbf{\phi}_{t} (y_{t}, \mathbf{x}), \sum_{s \sim t} \mathbf{\phi}_{st}(y_{s}, y_{t}, \mathbf{x})] 은 노드와 간선 특성을 합한 것이다. 이 경우 경사를 쉽게 구할 수 있다.

실제로는 사전분포 또는 정규화를 사용해 과적합을 방지하는 것이 중요하다. 가우시안 사전분포를 사용한다면 새 목적 함수는 다음과 같아진다.

l^{\prime}(\mathbf{w}) = \frac{1}{N} \sum_{i} \log p(\mathbf{y}_{i} | \mathbf{x}_{i}, \mathbf{w}) - \lambda \lVert \mathbf{w} \rVert_{2}^{2}

또는 희소한 그래프 구조를 학습하기 위해 간선 가중치 \mathbf{w}_{c}에 대해 l_{1} 정규화를 사용할 수도 있다. 이 경우 목적 함수는 다음과 같다.

l^{\prime}(\mathbf{w}) = \frac{1}{N} \sum_{i} \log p(\mathbf{y}_{i} | \mathbf{x}_{i}, \mathbf{w}) - \lambda_{1} \lVert \mathbf{w}_{c} \rVert - \lambda_{2} \lVert \mathbf{w}_{n} \rVert_{2}^{2}

이 경우 최적화 알고리즘은 더 복잡해진다. 볼록성은 유지되기는 한다.

많은 데이터셋을 다루기 위해, 추계적 경사 하강법을 사용할 수 있다. 정확한 추론이 불가능한 경우를 다루기 위해, 추계적 최대가능도를 사용할 수 있다. 이는 마르코프 연쇄 몬테 카를로 추론과 추계적 경사 하강 매개변수 학습을 결합한다.

가능도를 최대화시키는 것뿐만 아니라 손실 함수도 최소화시키는 추계적 최대 가능도의 확장은 SampleRank로 알려져 있다. 기본 아이디어는, L(\mathbf{y}_{i})를 손실 함수를 i번째 반복에서 샘플링된 라벨 벡터에서 구한 값이라 할 때 \mathbf{\Delta} = \mathbf{\phi}(\mathbf{y}_{i - 1}) - \mathbf{\phi}(\mathbf{y}_{i})로 잡고, \mathbf{\theta}를 손실 함수와 확률값의 증감 관계에 따라 계단 크기 \alpha에 대해 \alpha \mathbf{\Delta}만큼 증감시키는 것이다. 이는 가능도뿐만 아니라 손실함수에 영향을 주는 매개변수값을 학습할 수 있게 해준다.

은닉 변수에 대해 조건적 무작위 장을 정의하는 것도 가능하다. 관측가능한 특성과 은닉 라벨간의 미지의 관계를 허용하기 위해 이를 쓸 수 있다. 이 경우에는 목적 함수가 볼록이 아니게 되지만, 기대값 최대화 또는 경사 기반 방법을 통한 최대가능도추정 또는 최대사후확률추정을 통해 국소적인 최적해를 구할 수 있다.

19.7. Structural SVMs

조건적 무작위 장을 학습하는 과정에서 경사를 계산하기 위한 충족 통계량을 계산하기 위해서는 추론을 필요로 한다. 어떤 모델들에 대해서는 상태들의 결합 최대사후확률추정을 계산하는 것이 주변분포를 계산하는 것보다 간단할 수도 있다. 이 절에서는 이러한 빠른 최대사후확률추정법 (복호화)을 이용해 구조적 출력 분류기를 학습하는 방법을 다룬다. 이를 구조적 보조 벡터 기계라고 한다. 비슷한 방법으로 최대 차이 마르코프 망 또는 M3net 등이 있다.

19.7.1. SSVMs: a probabilistic view

지금까지는 다음 함수를 최소화시키는 최대사후확률추정을 다루었다.

R_{\mathrm{MAP}}(\mathbf{w}) = -\log p(\mathbf{w}) - \sum_{i=1}^{N} \log p(\mathbf{y}_{i} | \mathbf{x}_{i}, \mathbf{w})

하지만 테스팅 시점에는 사후기대손실을 최소화시키는 라벨을 다음과 같이 구할 수도 있다.

\hat{\mathbf{y}}(\mathbf{x} | \mathbf{w}) = \mathrm{argmin}_{\hat{\mathbf{y}}} \sum_{\mathbf{y}} \mathcal{L}(\mathbf{y}, \hat{\mathbf{y}}) p(\mathbf{y} | \mathbf{x}, \mathbf{w})

여기서 \mathcal{L}(\mathbf{y}^{\ast}, \hat{\mathbf{y}})는 실제 값이 \mathbf{y}^{\ast}인데 추정은 \hat{\mathbf{y}}로 했을 때의 손실이다. 그러므로, 학습 데이터에 대해 다음의 사후기대손실을 최소화시킬 수도 있다.

R_{\mathrm{EL}}(\mathbf{w}) = -\log p(\mathbf{w}) + \sum_{i=1}^{N} \log [\sum_{\mathbf{y}} \mathcal{L}(\mathbf{y}_{i},\mathbf{y}) p(\mathbf{y} | \mathbf{x}_{i}, \mathbf{w})]

0-1 손실을 사용하는 특수한 경우에는 이는 최대사후확률추정과 동일하다.

모델의 형태는 다음과 같이 나타낼 수 있다고 가정하자.

p(\mathbf{y} | \mathbf{x}, \mathbf{w}) = \frac{e^{\mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}, \mathbf{y})}}{Z(\mathbf{x}, \mathbf{w})}

p(\mathbf{w}) = \frac{e^{-E(\mathbf{w})}}{Z}

Z(\mathbf{x}, \mathbf{w}) = \sum_{\mathbf{y}} e^{\mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}, \mathbf{y})}

L(\mathbf{y}_{i}, \mathbf{y}) = \log \mathcal{L} (\mathbf{y}_{i}, \mathbf{y})

이 때, 목적 함수를 다음과 같이 쓸 수 있어진다.

R_{\mathrm{EL}}(\mathbf{w}) = E(\mathbf{w}) + \sum_{i} [-\log Z(\mathbf{x}_{i}, \mathbf{w}) + \log \sum_{\mathbf{y}} e^{L(\mathbf{y}_{i}, \mathbf{y}) + \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y})}]

그러면 다음이 성립한다.

R_{\mathrm{EL}}(\mathbf{w}) \sim E(\mathbf{w}) + \sum_{i=1}^{N} [\max_{\mathbf{y}} [L(\mathbf{y}_{i}, \mathbf{y}) + \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y})] - \max_{\mathbf{y}} \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y})]

문제는 우변이 \mathbf{w}에 대한 볼록함수가 아니라는 것이지만, 다음의 볼록한 상한을 이용할 수 있다.

R_{\mathrm{EL}}(\mathbf{w}) \leq E(\mathbf{w}) + \sum_{i=1}^{N} [\max_{\mathbf{y}} [L(\mathbf{y}_{i}, \mathbf{y}) + \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y})] -  \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i})]

\mathcal{Y} = \{-1, +1\}, L(y^{\ast}, y) = 1 - \delta_{y, y^{\ast}}, \mathbf{\phi}(\mathbf{x}, y) = \frac{1}{2} y \mathbf{x}인 경우에 이 함수는 표준 이진 보조 벡터 기계 목적함수와 같아진다.

그러므로 구조적 보조 벡터 기계 기준은 베이지안 목적 함수에 대한 상한을 최적화하는 것으로 볼 수 있다. \lVert \mathbf{w} \rVert가 크다면 이 상한은 강한 상한이 될 것이지만, 과적합의 위험이 있다. 대안은 결정 경계에 영향을 미치는 매개변수들에 대해서만 피팅을 하는 방법이 있다.

19.7.2. SSVMs: a non-probabilistic view

구조적 보조 벡터 기계를 다른 방식으로 알아보자. f(\mathbf{x}; \mathbf{w}) = \mathrm{argmax}_{\mathbf{y} \in \mathcal{Y}} \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}, \mathbf{y})을 예측 함수라 하자. 이 때 모든 i에 대해

\max_{\mathbf{y} \in \mathcal{Y} \setminus \mathbf{y}_{i}} \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}) \leq \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i})

이 성립하면 훈련 데이터에서 손실을 0으로 만들 수 있다. 이는 모든 i에 대해 \mathbf{y} \neq \mathbf{y}_{i}인 모든 \mathbf{y}에 대해 \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i}) - \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}) = \mathbf{w}^{T} \mathbf{\delta}_{i} (\mathbf{y})\geq 0인 것과 동치이다.

손실을 0으로 만드는 \mathbf{w}는 여러 가지인데, 그 중에서 크기 1을 만족하면서 차이값 \gamma = \min_{i} \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i}) - \max_{\mathbf{y} \in \mathcal{Y} \setminus \mathbf{y}_{i}} \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y})을 최대화시키는 것을 고른다. 이는 모든 i에 대해 \mathbf{y} \neq \mathbf{y}_{i}에 대해 \mathbf{w}^{T} \mathbf{\delta}_{i}(\mathbf{y}) \geq 1을 만족하면서 \min_{\mathbf{w}} \frac{1}{2} \lVert \mathbf{w} \rVert^{2}인 해를 구하는 것과 같다.

만약 손실 0을 만들 수 없는 경우라면 (예를 들어 이진 분류에서 데이터가 분리 가능하지 않을 경우), 데이터 항마다 여유 항 \zeta_{i}를 둬서 \mathbf{w}^{T} \mathbf{\delta}_{i} (\mathbf{y}) \geq 1 - \zeta_{i} 조건에 대해 \min_{\mathbf{w}, \mathbf{\zeta}} \frac{1}{2} \lVert \mathbf{w} \rVert^{2} + C \sum_{i=1}^{N} \zeta_{i} 인 것으로 제한을 완화시킨다.

구조적 출력의 경우에는 모든 제한 위반을 똑같이 다루지 말고 손실의 크기로 나눌 수 있다. 이 경우 조건이 \mathbf{w}^{T} \mathbf{\delta}_{i} (\mathbf{y}) \geq 1 - \frac{\zeta_{i}}{L(\mathbf{y}_{i}, \mathbf{y})}로 변한다. (여유치 변환) 또는 차이값을 손실에 비례하도록 할 수도 있다. 이 경우 조건이 \mathbf{w}^{T} \mathbf{\delta}_{i} (\mathbf{y}) \geq L(\mathbf{y}_{i}, \mathbf{y}) - \zeta_{i} 로 변한다. (차이 재변환)

재활용을 위해, \zeta_{i}^{\ast} = \max_{\mathbf{y}} (L(\mathbf{y}_{i}, \mathbf{y}) - \mathbf{w}^{T} \mathbf{\delta}_{i}(\mathbf{y}))을 구해놓을 수도 있다. 이를 대입해 조건을 없애면 다음의 문제를 얻는다.

\min_{\mathbf{w}} \frac{1}{2} \lVert \mathbf{w} \rVert^{2} + C \sum_{i} \max_{\mathbf{y}} [L(\mathbf{y}_{i}, \mathbf{y}) + \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y})] - \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i})

19.7.2.1. Empirical risk minimization

위의 목적 함수는 합리적일까? 빈도학파적인 접근에서의 기계학습에서 목적은 정규화된 실측 위험도 \mathcal{R}(\mathbf{w}) + \frac{C}{N} \sum_{i=1}^{N} L(\mathbf{y}_{i}, f(\mathbf{x}_{i}, \mathbf{w}))를 최소화시키는 것이다. (\mathcal{R}(\mathbf{w})은 정규화자, f(\mathbf{x}_{i}, \mathbf{w}) = \mathrm{argmax}_{\mathbf{y}} \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}) = \hat{\mathbf{y}}_{i}은 예측값)

이 때 손실 함수가 미분가능하지 않기 때문에 이를 최적화하기는 힘들다. 그래서 볼록한 상한\mathcal{R}(\mathbf{w}) + \frac{C}{N} \sum_{i} \max_{\mathbf{y}} (L(\mathbf{y}_{i}, \mathbf{y}) - \mathbf{w}^{T} \mathbf{\delta}_{i}(\mathbf{y}))을 대신 쓴다. 정규화자에 \mathcal{R}(\mathbf{w}) = \frac{1}{2N} \lVert \mathbf{w} \rVert^{2}을 대입하면 이전에 얻었던 목적 함수를 얻는다.

19.7.2.2. Computational issues

위의 목적 함수는 단순한 2차 최적화 문제이지만 O(N \lvert \mathcal{Y} \rvert)개의 문제를 풀어야 한다는 점이 문제이다. \lvert \mathcal{Y} \rvert은 대단히 클 수 있으므로 이는 계산가능하지 않다. 이에 대처하는 법으로, 손실 함수와 특성 벡터가 그래프 모델에 대해 분해될 경우에 한해서는, 제한조건의 수를 다항식 개수로 줄일 수 있음이 알려져 있다. 아니면 제한조건을 줄이지 말고 직접 절단면 법이나 추계적 부분경사법을 쓸 수도 있다.

19.7.3. Cutting plane methods for fitting SSVMs

SVMstruct 패키지에서는 볼록 최적화 기법인 절단면법을 이용해 구조적 보조 벡터 기계를 피팅한다. 기본 발상은 다음과 같다. 초기 추측 \mathbf{w}와 제한조건 없는 상태에서 시작한다. 각 반복마다, 조건을 가장 심하게 위반하는 \mathbf{x}_{i}\hat{\mathbf{y}}_{i}을 찾는다. 차이 위반값이 현재의 \zeta_{i}보다 \epsilon 이상 크다면 학습 데이터의 제한 조건 목록에 \hat{\mathbf{y}}_{i}를 추가한다. 이후 새로운 2차 최적화 문제를 풀어 \mathbf{w}, \mathbf{\zeta}을 찾는다. L(\mathbf{y}_{i}, \mathbf{y}) - \mathbf{w}^{T} \mathbf{\delta}_{i}(\mathbf{y}_{i})L(\mathbf{y}_{i}, \mathbf{y})(1 - \mathbf{w}^{T} \mathbf{\delta}_{i}(\mathbf{y}_{i}))로 바꾸면 여유값 변환 버전을 적용할 수 있다.

이 방법의 효율성은 제한조건을 다항식 개수만큼 추가해도 다른 지수 개수만큼의 제한조건을 최대 \epsilon 만큼만 위반한 채로 만족시킬 수 있다는 점이다. 전체 수행 시간은 O(\frac{1}{\epsilon^{2}})이다.

19.7.3.1. Loss-augmented decoding

이 방법의 또 다른 효율성은 가장 위반되는 제한조건을 찾는 \mathrm{argmax}_{\mathbf{y} \in \mathcal{Y}} L(\mathbf{y}_{i}, \mathbf{y}) - \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}, \mathbf{y})을 계산하는 것이다. 이를 손실-증강 복호화 또는 분리 신탁이라 한다. 이 때 손실 함수가 특성 벡터에 대한 같은 형태의 함수의 합으로 분해된다면, 손실 함수를 가중치 벡터 안으로 주입시킬 수 있다. 즉, \mathbf{v}^{T} \mathbf{\delta}_{i} (\mathbf{y}) = -L(\mathbf{y}_{i}, \mathbf{y}) + \mathbf{w}^{T} \mathbf{\delta}_{i} (\mathbf{y})이 되는 새 매개변수 집합 \mathbf{v}를 찾을 수 있다. 이후 p(\mathbf{y} | \mathbf{x}, \mathbf{v})에 대해 비터비 알고리즘 같은 표준적인 복호화 알고리즘을 사용하면 된다.

0-1 손실의 경우에는 최적해가 최선의 해이거나 두 번째로 최선의 해가 됨이 알려져 있다. 연쇄 구조 조건적 무작위 장에 대해서는, 비터비 알고리즘으로 복호화를 수행한다. 이 때 차선의 해는 최선의 해와 한 부분에서만 다른데, 최대 차이값이 결정 경계와 가장 가까운 변수를 두 번째로 가까운 변수로 바꾸면 된다. 이를 일반화해 N개의 최선의 해를 구할 수 있다.

해밍 손실 함수 L(\mathbf{y}^{\ast}, \mathbf{y}) = \sum_{t} \mathbf{1}_{y_{t}^{\ast} \neq y_{t}}와 F1 점수에 대해서는 동적 계획법을 써서 계산할 수 있다. 다른 손실 함수에 대해서는 다른 방법이 필요하다.

19.7.3.2. A linear time algorithm

선형 커널을 쓸 경우 선형 시간 알고리즘도 가능하다. 이 때에는 여유 변수를 \zeta 1개만 두는 대신 제한 조건을 \lvert \mathcal{Y} \rvert^{N}개를 두어, 조건 \frac{1}{N} \mathbf{w}^{T} \sum_{i=1}^{N} \mathbf{\delta}_{i} (\bar{\mathbf{y}}_{i}) \geq \frac{1}{N} L(\mathbf{y}_{i}, \bar{\mathbf{y}}_{i}) - \zeta에 대해 최적화 문제 \min_{\mathbf{w}, \zeta \geq 0} \frac{1}{2} \lVert \mathbf{w} \rVert_{2}^{2} + C \zeta 를 푸는 것이다. 이 때 구해지는 여유 변수의 해는 원본 문제의 여유 변수의 평균 \zeta^{\ast} = \frac{1}{N} \sum_{i=1}^{N} \zeta_{i}^{\ast}와 같다.

이는 절단면법으로 최적화가 가능하다. 손실-증강 복호화에 대해 N번의 호출을 하고, 루프 반복의 수는 N에 대해 독립이므로, 총 수행 시간은 선형 시간이 된다.

19.7.4. Online algorithms for fitting SSVMs

절단면 알고리즘은 데이터 수에 대해 선형 시간이 될 수 있지만, 데이터셋이 클 경우 그래도 느릴 수 있다. 이 경우엔 온라인 학습을 할 수 있다.

19.7.4.1. The structured perceptron algorithm

구조적 보조 벡터 기계를 피팅하는 간단한 방법은 구조적 퍼셉트론 알고리즘이다. 이는 일반 퍼셉트론 알고리즘의 확장으로서, 각 단계마다 \hat{\mathbf{y}} = \mathrm{argmax} p(\mathbf{y} | \mathbf{x})을 구한다. (비터비 알고리즘 등을 쓸 수 있다) \hat{\mathbf{y}} = \mathbf{y}이면 아무것도 하지 않는다. 아니라면, 가중치 벡터를 \mathbf{w}_{k+1} = \mathbf{w}_{k} + \mathbf{\phi}(\mathbf{y}, \mathbf{x}) - \mathbf{\phi}(\hat{\mathbf{y}}, \mathbf{x})을 이용해 업데이트한다. 성능을 높이기 위해서는 매개변수들을 업데이트할 때 가장 최근의 값을 쓰는 대신 최근의 값 몇 개를 평균내어 사용하는 것이 좋다.

19.7.4.2. Stochastic subgradient descent

구조적 퍼셉트론 알고리즘의 단점은 암묵적으로 0-1 손실을 가정하며, 차이값을 강제하지 않는다는 점이다. 대안은 추계적 부분 경사 하강법을 사용하는 것이다. 예로는 페가소스 알고리즘이 있다. 이는 이진 보조 벡터 기계에 대해 설계된 알고리즘이었지만 구조적 보조 벡터 기계에 대해서도 확장될 수 있다.

다음 목적 함수를 생각해 보자:

f(\mathbf{w}) = \sum_{i=1}^{N} \max_{\hat{\mathbf{y}}_{i}}[L(\mathbf{y}_{i}, \hat{\mathbf{y}}_{i}) + \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \hat{\mathbf{y}}_{i})] - \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i}) + \lambda \lVert \mathbf{w} \rVert^{2}

이 때 \hat{\mathbf{y}}_{i}를 최대화자라 하자. 그러면 이 목적 함수의 부분 경사를 다음과 같이 정의한다:

g(\mathbf{w}) = \sum_{i=1}^{N} \mathbf{\phi}(\mathbf{x}_{i}, \hat{\mathbf{y}}_{i}) - \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i}) + 2 \lambda \mathbf{w}

추계적 부분 경사 하강법에서는 이 경사를 근사한 뒤 다음과 같이 업데이트한다:

\mathbf{w}_{k + 1} = \mathbf{w}_{k} - \eta_{k} g_{i} (\mathbf{w}_{k})

이 때 계단 크기 \eta_{k}는 로빈스-몬로 조건을 만족시켜야 한다. 퍼셉트론 알고리즘은 \lambda = 0, \eta_{k} = 1인 특이 케이스라는 것을 눈여겨보라. \mathbf{w}가 단위 길이를 가짐을 보장하기 위해서 각 업데이트 이후마다 이를 단위 구에 사영시킨다.

19.7.5. Latent structural SVMs

구조적 보조 벡터 기계에 잠재 변수 \mathbf{h}가 있는 경우를 고려해 보자. 예를 들면 프랑스어에서 영어로 번역을 한다는 것은 알지만 단어 순서를 어떻게 재배치할지는 알지 못할 때.

이럴 때에는 모델을 다음의 잠재 조건적 무작위 장으로 확장시킨다.

p(\mathbf{y}, \mathbf{h} | \mathbf{x}, \mathbf{w}) = \frac{e^{\mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}, \mathbf{y}, \mathbf{h})}}{Z(\mathbf{x}, \mathbf{w})}

Z(\mathbf{x}, \mathbf{w}) = \sum_{\mathbf{y}, \mathbf{h}} e^{\mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}, \mathbf{y}, \mathbf{h})}

이후 손실 함수 \mathcal{L}(\mathbf{y}^{\ast}, \mathbf{y}, \mathbf{h})을 정의한다. (L(\mathbf{y}^{\ast}, \mathbf{y}, \mathbf{h}) = \log \mathcal{L}(\mathbf{y}^{\ast}, \mathbf{y}, \mathbf{h})) 이는 잠재 변수 \mathbf{h}을 통해 \mathbf{y}을 예측하는 데 드는 손실을 측정하는 함수이다. 이 손실 함수가 주어졌을 때, 목적 함수는 다음과 같다.

R_{\mathrm{EL}}(\mathbf{w}) = -\log p(\mathbf{w}) + \sum_{i} \log [\sum_{\mathbf{y}, \mathbf{h}}e^{L(\mathbf{y}_{i})} \frac{e^{\mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}, \mathbf{y}, \mathbf{h})}}{Z(\mathbf{x}, \mathbf{w})}]

이전과 같은 형태의 상한을 적용하면, 다음을 얻는다.

R_{\mathrm{EL}}(\mathbf{w}) \leq E(\mathbf{w}) + \sum_{i=1}^{N} \max_{\mathbf{y}, \mathbf{h}} [L(\mathbf{y}_{i}, \mathbf{y}, \mathbf{h}) + \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}, \mathbf{h})] - \sum_{i=1}^{N} \max_{\mathbf{h}} \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i}, \mathbf{h})

이 때 에너지 함수 E(\mathbf{w}) = -\frac{1}{2C} \lVert \mathbf{w} \rVert_{2}^{2}을 쓰면 이는 잠재 보조 벡터 기계에서 최적화되는 목적 함수와 같다.

이 목적 함수는 볼록함수가 아니지만, 두 볼록 함수의 차로 나타내어진다. 그러므로 오목-볼록 과정(CCCP)을 통해 풀 수 있다. 이는 국소적 최적해나 안장점으로 수렴함이 보장된다. 잠재 구조적 보조 벡터 기계에 적용되었을 때에는 기대값 최대화 알고리즘과 비슷하다. E 단계에서는 \mathbf{h}_{i}^{\ast} = \mathrm{argmax}_{\mathbf{h}} \mathbf{w}_{t}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i}, \mathbf{h})일 때 \mathbf{v}_{t} = -C \sum_{i=1}^{N} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i}, \mathbf{h}_{i}^{\ast})로 세팅해 선형 상한을 계산한다. M 단계에서는 \frac{1}{2} \lVert \mathbf{w} \rVert_{2} + C \sum_{i=1}^{N} \max_{\mathbf{y}, \mathbf{h}} [\tilde{L}(\mathbf{y}_{i}, \mathbf{y}, \mathbf{h}) + \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}, \mathbf{h})] - C \sum_{i=1}^{N} \mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}_{i}, \mathbf{y}_{i}, \mathbf{h}_{i}^{\ast})를 최소화시켜 \mathbf{w}를 추정한다.

요점 정리

  • 마르코프 무작위 망은 비방향 그래프로 모델링되는 모델이다.
  • 비방향 그래프 모델은 전역/지역/쌍별 마르코프 특성을 가진다. 이 세 특성은 모두 동치이다. 방향 그래프 모델에 비해 구별적 분류기가 갖는 장점이 존재한다.
  • 마르코프 무작위 망은 잠재 함수의 곱으로 매개화된다.
  • 마르코프 무작위 망에는 아이싱 모델 등 여러 용례가 존재한다.
  • 마르코프 무작위 망은 경사법이나 유사가능도 등으로 학습한다.
  • 조건적 무작위 망은 마르코프 무작위 망의 클리크 잠재 함수가 입력 특성에 대해 조건이 걸린 버전이다.
  • 구조적 보조 벡터 기계는 구조적 출력을 가진 분류기를 빠른 최대사후확률추정을 이용해 피팅하는 것이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중