2. 문서의 구조 찾기

2.1. 서론

• 문서의 구조를 찾는 작업은 대다수 language-independent하지만, language-dependent한 부분도 존재한다.
• 가령, 한국어의 경우 형태소를 찾는 preprocessor이 존재할 수 있다. (토큰은 어절이 될 수도 있고 형태소가 될 수도 있지만)

문장 경계 인식

• 토큰열이 주어졌을 때 문장으로 나누는 작업을 의미한다.
• 문장 경계는 그 자체로 수행되기 보다 summarization, information extraction 등 다른 작업과 동시에 수행되는 경우가 많고, 무엇보다 machine translation 등의 후속 작업의 성능에 영향을 많이 미친다.
• 영어의 경우, 문장은 대문자로 시작하고 마침표나 물음표 등의 구두점으로 끝나는 것이 일반적이다.
• 하지만, 대문자는 대명사에도 사용되고, 마침표는 약어에도 사용된다.
  • 마침표가 약어에 사용되는 비율은, Brown 말뭉치가 10%, Wall Street Journal 말뭉치가 47%라고 함.
  • 약어의 경우, 사전을 이용해 높은 정확도로 detecting할 수 있지만, 문장의 마지막에 오는 경우, 미등록어, 오타 등은 커버하지 못한다.
• 그 외에도, 문장이 문장을 포함하고 있거나 (ex: 인용구), informal한 문서에서 (ex: 트위터) 구두점이 빠지거나 오타가 나는 경우, OCR, ASR의 결과물을 다루는 경우, 구어에서 발화자가 code switching을 하는 경우 등에서 sentence detection은 더욱 어려운 문제가 된다.
  • 특히 OCR을 하는 경우 시스템이 마침표와 쉼표를 혼동하는 경우가 잦고, ASR의 경우에는 대문자나 구두점이 아예 없을 때도 있다.

Code switching: The use of words, phrases, or sentences from multiple languages by multilingual speakers.

• 여기서 language라고 하는 것은 비단 자연어 뿐 아니라 programming language, 수학, URL 등의 표기법 등도 포함

토픽 경계 인식

• 토픽 경계를 인식하는 것은 information extraction/retrieval, summarization에서 중요한 태스크이다.
• 1990년대 후반, DARPA에서 뉴스에 대해 Topic detection and tracking (TDT) 프로그램을 시작하면서 많은 발전이 있었다.
• 토픽 경계가 어려운 가장 큰 이유는, 좋은 결과에 대한 정의가 사람마다 다르기 때문이며, 따라서 태스크 수행 이전에 정의를 명확히 내리는 것이 필수적이다.
• 또한, 문서의 경우 소제목이나 단락 구분이라도 있지만, 대화는 그런 힌트가 존재하지 않는데다가, 하나의 토픽이 끝나고 다른 토픽으로 이동한 후 다시 원래의 토픽으로 돌아가는 일도 빈번하기 때문에 더욱 풀기 어렵다.

2.2. 방법론

• 문장이나 토픽을 찾는 것은 보통 경계면 분류 문제(boundary classification problem)로 취급된다.
• 즉, 경계면의 후보가 주어지면, 그 후보의 갖가지 특징을 이용해 그것이 진짜 경계면인지 아닌지 추정하는 것이다.
• 문장 경계 후보로는 보통 단어 사이가, 토픽 경계 후보로는 문장 사이가 사용된다.

1. Generative sequence classification methods (ex: HMM)
2. Discriminative local classification methods (ex: TexTiling, SVM)
3. Discriminative sequence classification methods
4. Hybrid approaches

2.3. 방법론의 복잡도

개인적으로는 아래 표에 대한 의심이 갑니다만... - e9t

분류	상대적 장점
Generative methods	- 복잡도가 낮음 (discriminative는 feature weight를 찾기 위해 training data를 여러번 탐색함) - 학습과 예측이 빠름
Discriminative methods	- 좀 더 많은 feature을 사용할 수 있음 - unseen event에 강함 - 작은 training set으로도 좋은 성능을 냄
Local approaches	- Sequence method에 비해 단순 (decoding 불필요; 다행히 conditional independence 가정을 적용하면 polynomial time 안에 가능)

2.4. 성능평가

• Error rate, F1 measure, NIST error rate 등 사용
• 문서의 문장 경계 error rate
  • Mikheev, 2000: 1.41%, 0.45% (약어 사전 추가), 0.31% (POS 태그 추가)
  • Gillick, 2009 (SVM 사용): 0.25%
• 대화의 문장 경계 F1 measure
  • Doss et al., 2007 (다국어 뉴스 대상): 69.1% (MaxEnt 사용), 72.6% (Adaboost 사용), 72.7% (SVM 사용)
  • Zimmerman et al., 2006 (영어 뉴스 대상): 65.5% (Adaboost 사용), 67.3% (Adaboost + HELM 사용)
  • Guz et al., 2009 (터키어 뉴스 대상): 78.2% (HELM 사용), 86.2% (fHELM, 형태소 추가), 86.9% (Adaboost 사용), 89.1% (CRF 사용)

2.5. 특징(features)

어떤 특징을 쓸 것인지는 어떤 접근법을 쓸지에 좌우되곤 한다.

1. Lexical features (문어, 구어): n-grams, lexical chains와 같은 key features
2. Syntactic features (문어, 구어)
3. Discourse features (문어, 구어): "안녕하세요. KBS 아홉시 뉴스입니다." 등과 같이 시작과 끝을 알리는 cue phrases.
4. Typographical and structural features (문어)
5. Prosodic features (구어)

2.6. 프로세싱 절차

1. Determine candidate boundaries
2. Extract features for each candidate
3. Classify each candidate
4. Test