사용자:Frf1226/연습장: 두 판 사이의 차이

내용 삭제됨 내용 추가됨

인라인

2015년 4월 24일 (금) 15:09 판

조건부 무작위장(영어: conditional random field 조건부 랜덤 필드^[*])이란 통계적 모델링 방법중에 하나로, 패턴 인식과 기계 학습과 같은 구조적 예측에 사용된다. 일반적인 분류자(영어: classifier)가 이웃하는 표본을 고려하지 않고 단일 표본의 라벨을 예측하는 반면, 조건부 무작위장은 고려하여 예측한다. 자연 언어 처리 분야에서 자주 사용되는 선형 사슬 조건부 무작위장(영어: linear chain CRF)은 일련의 입력된 표본들에 대해 일련의 라벨들을 예측한다.

조건부 무작위장은 판별적 비방향성 그래프 모형의 한 형태이며, 관찰되는 것들의 알려진 관계를 암호화, 일관된 해석을 구성하는데 사용된다. 또, 자연언어로 된 글 또는 생물학적 서열 정보, 그리고 컴퓨터 비전 분야에서의 일련의 데이터에 대한 라벨 예측, 분석하는 데 사용되기도 한다. 구체적으로, 조건부 무작위장은 부분구문분석, 개체명 인식, 유전자 검색 등의 응용 분야에 사용될 수 있으며, 이러한 분야에서 은닉 마르코프 모델의 대안이 될 수 있다. 컴퓨터 비전 분야에서는 객체 인식, 이미지 분할에 종종 사용된다.

정의

조건부 무작위장을 간단하게 설명하면 입력 시퀀스에 대한 출력 시퀀스의 조건부 확률이라고 할 수 있다. 수학적인 표현을 사용하여 매우 간단하게 표시하면 다음과 같이 할 수 있다.

$p(y|x),$ 여기서, $x,y$ 는 시퀀스이다.
예를 들어, $x=(a,b,c),y=(x,y,z),$
$x,y$ 시퀀스에 대하여서는 제약이 없다.

즉 예를 들면, 조건부 무작위장은 문자 a, b, c 가 연속적으로 나타났을 때, 문자 x, y, z 를 연속적으로 부여할(나타날) 확률을 의미한다고 할 수 있다. 여기서 y는 마코프 성질을 만족하여야 한다. 그런데 만약 x의 집합과 y의 집합이 한정되어 있다면, 이 구조는 그래프 구조를 형성하게 된다. 일반적으로는 체인(chain) 그래프 구조를 형성한다고 한다. 그런데, 어떤 무작위장과도 양립할 수 없는(영어: not compatible) 완벽한(영어: consistent) 조건부 확률(영어: conditional probability) 체제가 있다고 한다^[1]. 따라서 조건부 확률을 사용하여 조건부 무작위장을 표현할 수는 없는 것이다.^[2]

조건부 무작위장 $(Y,X)$ 는 방향이 없는(영어: undirected) 그래프 $G=(V,E)$ 혹은 마코프 무작위장으로 간주할 수 있다. 만약, 입력 시퀀스에서 조건부 독립을 가정할 수 있다면, 이론적으로 그래프의 구조는 여러 가지 형태를 나타낼 수 있다. 하지만 응용에서는 일반적으로 $Y$ 에 해당되는 노드는 간단한 체인(chain)의 형태를 나타내는 경우가 많다[]. 조건부 랜덤 필드는 은닉 마코프 모델(HMM, Hidden Markov Model)에 비하여 변수 독립성 조건이 필요 없는 장점이 있다고 한다. 또한 조건부 무작위장은 최대 엔트로피 마코프 모델(MEMM, Maximum Entropy Markov Model)에 비하여 변수 치우침(bias)이 없는 장점이 있다고 한다^[3]. 다음은 조건부 무작위장의 정의 이다^[4].^[5]

$G=(V,E)$ 는 그래프 구조 이고, $Y=(Y_{v})_{v{\in V}}$ 로서, $Y$ 는 그래프 $G$ 의 버택스를 나타낸다고 하고 $E$ 는 에지라고 하자. 만약 랜덤 변수 $X$ 에 대하여 랜덤 변수 $Y_{v}$ 가 그래프에서 마코프 성질을 나타낸다면, 즉, $p(Y_{v}|X,Y_{w},w\neq v)=p(Y_{v}|X,Y_{w},w\sim v)$ 라면 $(X,Y)$ 는 조건부 랜덤 필드가 된다. (여기서 $w\sim v$ 는 $w$ 와 $v$ 는 서로 이웃이라는 의미)

추론

파라미터 학습

변형

선형 사슬 조건부 무작위장

일반 사슬 조건부 무작위장

소프트웨어

아래는 일반적인 조건부 무작위장 도구로 알려진 목록이다.

RNNSharp CRFs based on recurrent neural networks (C#, .NET)
CRF-ADF Linear-chain CRFs with fast online ADF training (C#, .NET)
CRFSharp Linear-chain CRFs (C#, .NET)
GCO CRFs with submodular energy functions (C++, Matlab)
GRMM General CRFs (Java)
factorie General CRFs (Scala)
CRFall General CRFs (Matlab)
Sarawagi's CRF Linear-chain CRFs (Java)
HCRF library Hidden-state CRFs (C++, Matlab)
Accord.NET Linear-chain CRF, HCRF and HMMs (C#, .NET)
Wapiti Fast linear-chain CRFs (C)^[6]
CRFSuite Fast restricted linear-chain CRFs (C)
CRF++ Linear-chain CRFs (C++)
FlexCRFs First-order and second-order Markov CRFs (C++)
crf-chain1 First-order, linear-chain CRFs (Haskell)
imageCRF CRF for segmenting images and image volumes (C++)
MALLET Linear-chain for sequence tagging (Java)
PyStruct Structured Learning in Python (Python)

아래는 조건부 무작위장과 관련된 도구로 알려진 목록이다.

Conrad CRF based gene predictor (Java)
Stanford NER Named Entity Recognizer (Java)
BANNER Named Entity Recognizer (Java)

국내에서의 연구

참고 문헌

↑ Hamilton, M., and W. J. Anderson. "A consistent system of conditional probabilities which is not compatible with any random field." Canadian Journal of Statistics 6.1 (1978): 95-101.
↑ 이호석. "조건부 랜덤 필드와 응용에 대한 고찰." 한국정보과학회 학술발표논문집 36.2C (2009): 184-187.
↑ Lafferty, John, Andrew McCallum, and Fernando CN Pereira. "Conditional random fields: Probabilistic models for segmenting and labeling sequence data." (2001).
↑ Lafferty, John, Andrew McCallum, and Fernando CN Pereira. "Conditional random fields: Probabilistic models for segmenting and labeling sequence data." (2001).
↑ 이호석. "조건부 랜덤 필드와 응용에 대한 고찰." 한국정보과학회 학술발표논문집 36.2C (2009): 184-187.
↑ T. Lavergne, O. Cappé and F. Yvon (2010). Practical very large scale CRFs. Proc. 48th Annual Meeting of the ACL, pp. 504-513.

[1] Hamilton, M., and W. J. Anderson. "A consistent system of conditional probabilities which is not compatible with any random field." Canadian Journal of Statistics 6.1 (1978): 95-101.

[2] 이호석. "조건부 랜덤 필드와 응용에 대한 고찰." 한국정보과학회 학술발표논문집 36.2C (2009): 184-187.

[3] Lafferty, John, Andrew McCallum, and Fernando CN Pereira. "Conditional random fields: Probabilistic models for segmenting and labeling sequence data." (2001).

[4] Lafferty, John, Andrew McCallum, and Fernando CN Pereira. "Conditional random fields: Probabilistic models for segmenting and labeling sequence data." (2001).

[5] 이호석. "조건부 랜덤 필드와 응용에 대한 고찰." 한국정보과학회 학술발표논문집 36.2C (2009): 184-187.

[6] T. Lavergne, O. Cappé and F. Yvon (2010). Practical very large scale CRFs. Proc. 48th Annual Meeting of the ACL, pp. 504-513.

[1]

[2]

[3]

[4]

[5]

[6]

@@ 5번째 줄: / 5번째 줄: @@
 == 정의 ==
 조건부 무작위장을 간단하게 설명하면 입력 시퀀스에 대한 출력 시퀀스의 [[조건부 확률]]이라고 할 수 있다. 수학적인 표현을 사용하여 매우 간단하게 표시하면 다음과 같이 할 수 있다.
+{| align="center" cellpadding ="20" cellspacing="0" border="1"
-<pre><math>p(y|x),</math> 여기서, <math>x , y</math>는 시퀀스이다.
+|
-예를 들어, <math>x=(a, b, c), y=(x, y, z),</math> <math>x, y</math> 시퀀스에 대하여서는 제약이 없다.
+<math>p(y|x),</math> 여기서, <math>x , y</math>는 시퀀스이다.<br>
-</pre>
+예를 들어, <math>x=(a, b, c), y=(x, y, z),</math><br> <math>x, y</math> 시퀀스에 대하여서는 제약이 없다.
+|}
 즉 예를 들면, 조건부 무작위장은 문자 a, b, c 가 연속적으로 나타났을 때, 문자 x, y, z 를 연속적으로 부여할(나타날) 확률을 의미한다고 할 수 있다. 여기서 y는 [[마코프 성질]]을 만족하여야 한다. 그런데 만약 x의 집합과 y의 집합이 한정되어 있다면, 이 구조는 그래프 구조를 형성하게 된다. 일반적으로는 체인(chain) 그래프 구조를 형성한다고 한다.
 그런데, 어떤 [[무작위장]]과도 양립할 수 없는({{llang|en|not compatible}}) 완벽한({{llang|en|consistent}}) [[조건부 확률]]({{llang|en|conditional probability}}) 체제가 있다고 한다<ref>Hamilton, M., and W. J. Anderson. "A consistent system of conditional probabilities which is not compatible with any random field." Canadian Journal of Statistics 6.1 (1978): 95-101.</ref>. 따라서 [[조건부 확률]]을 사용하여 조건부 무작위장을 표현할 수는 없는 것이다.<ref>이호석. "조건부 랜덤 필드와 응용에 대한 고찰." 한국정보과학회 학술발표논문집 36.2C (2009): 184-187.</ref><br><br>