SWRC) Table Extraction Using Conditional Random Fields
Table Extraction Using Conditional Random Fields
CRF를 이용한 Table 추출.
David Pinto, et al., Table Extraction Using Conditional Random Fields, Center for Intelligent Information Retrieval, University of Massachusetts Amherst.
David Pinto, et al., Table Extraction Using Conditional Random Fields, Center for Intelligent Information Retrieval, University of Massachusetts Amherst.
Abstract
Table을 찾고 정보를 table로부터 추출하는 능력은 data mining, QA, 그리고 정보 추출 직무에서 매우 필수적인 요소이다. 문서들은 종종 밀집하게 포장된 다차원의 정보와 소통하기 위해 table을 포함하곤 한다.
Table은 효과적으로 범위와 기록들을 2차원의 형태로 가리키기 위해 layout pattern을 적용한다.
전통적인 언어 모델링 기술을 위한 그들의 formatting과 content의 값비싼 조합은 전통적인 언어 모델링 기술에 어려움을 제공한다. 이 논문에서는 table 추출을 위한 CRF 기술의 사용을 제공하고, 그 기술을 HMM과 비교한다.
HMM과는 다르게 CRF는 많은 값비싸고 겹치는 layout의 사용과 언어 특징을 지지하고, 결과적으로 그들의 performance가 더 좋았다. 우리는
plain-text 정부기관 통계 자료를 보여준다. 그 table은 92% F1와 함께, 그들의 구성하는 줄들은 12개의 연관 카테고리로 94% 정확도로 분류되었다. 우리는 또한, 방향성이 없는 그래픽 모델에서 column을 분할하고,
cell들을 찾고, 그들을 data cell이나 label cell로 분류하기 위한 future work를 제안한다.
Introduction
많은 문서상의 정보들은 항상 단어들의 목록으로만 전달되는 것이 아니라 이렇나 단어들이 layout 형태로 전달되기도 한다. 구 사이에 관계를 만들기 위해 전치사가 쓰이는 것처럼, 2차원상의 layout 형태 또한 grouping, 연결, 제약들을 조정한다. 이러한 layout을 통해 어떠한 의미를 포함하고 있는 궁극적인 예시는
Table이다.
Table은 – tabular 형태로 텍스트 토큰들이 놓여진 – 종종 밀집하게 정보들을 분야와 기록에 잇는 정보들을 조정하기 위해 사용된다. 그것들은 사람의 눈을 위한 디자인된 데이터베이스로 묘사된다. 테이블은 초기 점토 문서부터 현대 웹 페이지까지에 나타난다. 몇몇은 line-art를 사용하기도 하고 몇몇은 공백을 사용하기도 한다. 그것은 때때로 두 개의 간단한 열로 이루어지거나 때때로는 매우 복잡한 제목들의 모음, 압축된 소제목, 그리고 다양한 셀 사이즈로 이루어진다. 그것들은 정부 보고서, 잡지 기사, 그리고 학회 논문까지 다양한 곳에서 사용되고 있다.
QuASM(Question Answering Using Semi-structured Metadata) system에서 이루어진 이전 작업에서 테이블 테이터를 뽑아내는 것은 직면된 최고의 도전적인 작업으로 증명됐다. QA
system은 전형적으로 query와 관련된 정보를 찾는 두 단계의 추출을 시행한다. 첫 번째로, 질문과 매칭된 문서들이 추출되고, 그 후에 가능성 있는 해답들을 위해 이 문서들이 검색된다.
QuASM은 각각의 data cell과 meta data들을 그것들의 작은 문서로 바꾸고자 heuristic program을 사용한다. 그 작은 문서들을 보다 정확히 추출될 수 있고 빠르게 검색할 수 있다.
Metadata의 양과 질은 시스템의 성공에 극도로 중요하며, 특히 문서 추출 단계에서 중요하다. 공교롭게도 QuASM은 table로부터 너무 많은 정보를 추출해내는 경향이 있어 performance에 영향이 있다.
추출을 향상시키기 위해, 질문에 답하는 능력을 확장시키기 위해 heuristic를 회피하고, 모다 형태적인 model을 만드는 것이 제안되었다. 정보 추출 작업을 위한 통계 언어 모델링에 중요한 노력과 과정이 있을지라도, 언어와 layout을 합치는 model에는 오직 조금의 관련된 연구만 있었다. 전통적인 언어 모델링은, 언어 컨텐츠의 일렬에만 집중했고, 간단히 콘텐츠와 layout feature의 2차워 합성물과 같은 data에는 적용시킬 수 없었다.
이 논문은 조건부 무작위장 (CRF)를 사용하여 콘텐츠와 layout 동시에서 나타나는 증거들을 통합하는 테이블 추출 모델을 제시한다.
CRF는 판별된 훈련 비방향 그래프 모델로, 이는 세분성의 다양한 단계나 다양한 양식에서 나타나는 복잡하고, 겹치고 종속적인 세트들에 큰 자유도를 갖는다. 우리는 plain-text 정보 통계 레포트에서 동시에 table을 배치하고,
header, sub-hearder, data, seperator와 같은 tag와 함께 table의 구성 라인 각각에 레이블을 하는 방법을 설명한다. 그 feature들은 알파벳 문자의 퍼센트, 개월과 연수와 매칭되는 regular expression의 존재 그리고 현재 라인의 공백이 이전 라인의 공백과 얼마나
align되어 있는지와 같은 input stream의 양상을 측정한다. 정보 보고서의 실험에서, table은 92% F1의 정확도로 배치되었고,
line들은 94%의 정확도로 레이블되었으며, 같은 feature를 사용하는 유사한 HMM의 80% 결과물보다 에러를 줄였다. 우리의 QA 시스템에 적용하기 위해 우리는 최근 셀 boundary를 찾기 위해, 그리고 cell들을 data나 label로 분류하기 위해, 그리고 data cell들을 그들의 상응하는 label cell과 결합시키기 위해 후속
heuristic과 함께 이러한 태그를 사용했다.
이 논문은 또한 수직적으로, 그리고 수평적으로 모두 작동하는 모다 복잡한 CRF 모델에 대한 현재 진행죽인 작업을 묘사하고, 근사 추론 절차를 사용하고, 그리고 테이블 검출, 셀 세분화 및 분류를 위한 조건부 확률 모델을 제공한다.
TABLE EXTRACTION
Related Work
Matthew Hurst는 layout과 언어 조합의 하나로써 table로부터 정보 추출 문제를 묘사했다: table의 원소들은 모호할 수 있으며, cell들은 다중의 열이나 다중의 행에 분포하여 존재할 수 있다; 제목 정보는 복수의 cell들을 가로질러 존재할 수 있다; 그곳에는
table line간 연속성이 부족할 수 있다.
System이 layout이나 언어에 기반을 둘 수 있을지라도, 두 개의 혼합물은 테이블의 데이터에서 나타나는 모호성을 해결하는 것이 필수적이다. 테이블이 주어지면,
Hurst의 모델은 표 텍스트를 블록을 분할한 다음,
block이 무엇을 나타내는 지를 결정하는데, 이 두 단계 모두 생성 언어 모델을 사용한다.
순수히 layout에만 기반을 둔 접근 방법의 예시는 Pyreddy와 Croft의 논문에서 찾을 수 있다. 문자열 alignment 그래프 (CAG)는 정보 추출을 위한 indexing을 위해 이러한 table을 추출하기 위한 문서들에서 text table을 찾는데 사용되었다. 그 CAG는 table을 text 문자열과 공백으로 추상화하고 제목, 캡션, 그리고 CAG에서 계시된 구조에 기반을 맞춘 데이터 행을 정의하기 위해 노력했다. 전체 테이블이 추출될 동안, table의 괜찮은 원소를 정의하려는 시도는 없었고 오직 table의 section을 정의하려고만 하였다. (제목 구역, 데이터 구역). Ng, Lim과 Koo는 table상에서 행과 열을 정의하는 머신 러닝 기술을 적용했지만, 그곳에는 오직 line이나 cell의 용어인 그것의 다른 구성 요소를 추출하는 것이 아니라 text의 table의 위치를 찾는 데에만 흥미를 가졌다.
Pinto는 QA를 위한 개별 cell들을 추출하는 heuristic 방법과 함께 CAG를 만들었다. 이 시스템에서, cell data를 추출하고 그것을 그것의 metadata와 결합하는데, 몇몇의 언어 처리는 데이터 행으로부터 제목을 구분하는데 사용되었다. 이 작업을 통해 정보 검색에 사용된 표현을 만드는 데 테이블의 정확한 태깅이 중요하다는 것을 배웠다. 하지만, 시스템이 헤더 행의 타입을 미세하게 구분하지 않기 때문에 그것은 외부 메타 데이터를 사용하려는 경향이 있다. QA 시스템에 의해 만들어진 오류에 대한 연구는 관계 없는 메타데이터가 적절한 문서를 추출하지 못하는 주요 원인임을 말해준다.
Task and Approach
테이블 추출은 아마 6가지의 sub problem으로 분류할 수 있다:
1.
테이블을 배치한다.
2.
열의 위치와 유형을 정의한다.
3.
행의 위치와 유형을 정의한다.
4.
테이블을 cell로 분해한다.
5.
cell들을 data나 header로써 태그한다.
6.
Data cell들을 그에 상응하는 header와 결합한다.
이 논문에서는 문서의 line에 레이블하기 위해 조건부 확률 Markov model을 사용하는 데, 항목 1번과 2번에 집중한다. 그 레이블은 line이 table의 일부분인지 아닌지를 추측하고, 만약 그렇다면,
table에서 어떠한 역할을 맡는지 추측한다. 유한 상태 Markov model의 사용은 유용한 context를 대표하는데 도움을 주는데, 예를 들어 title뒤엔 table header, 그 뒤엔 data row, 그 뒤엔 footnote와 같은 사실들 말이다. 상태 전환 확률은 텍스트로부터 유도된 다양한 feature의 function이다.
웹 페이지는 두 가지 유형의 table을 포함한다. 텍스트 table은 사람을 위해 형태화되었으며,
일반적으로 공백과 고정된 font를 사용하여 열을 align시킨다.
HTML table은 기계를 위해 형태화되었으며, cell들의 위치를 디자인하기 위한 markup 언어가 사용되었다. 모든 HTML table 원소가 실제적으로 table을 위해 사용되는 것이 아님에도, 텍스트 테이블 추출은 어려운 문제이며, 마크업이 table의 layout으로부터 유추되어야만 하기 때문이다.
이러한 테이블을 위한 source는 2001년 6월 www.FedStats.com에서 크롤링할 수 있다. 이러한 문서들은 다양한 주제의 거대한 양의 데이터 테이블에서 희귀하다. 이러한 문서들의 set들은 무작위로 선택되었고, 논문에서 나오는 실험을 위해 수작업으로 레이블되었다.
텍스트 테이블의 예시가 Figure 1에서 나타나있다. 이 테이블은 테이블이 직면한 많은 도전 과제들을 보여주고 있다. 6번째 데이터 라인인, 레이블 Sprouts을 보자. 해당 line에서 3번째 숫자 (3200)을 올바르게 추출하기 위해, 우리는 그것을 세 개의 제목 line, super-header “Area Planted”, 열 header “1999”, 소제목 “acres”, section 제목 “Brussels”, 그리고 row-header
“Sprouts”와 결합해야 한다. 면밀한 조사를 해보면 “Area Planted”는 거의 두 번째 데이터 열에 놓여진 것을 볼 수 있다. 왜 그것은 두 번째 열에만 결합하지 않는가? 왜 “Brussels”라는 단어는 비어있는 data 행 대신에 sprouts data 행의 일부분인가? Pinto et al.에서, 이 문제는 metadata를 아낌없이 포함하는 것으로 다루었다. 더해서, 열과 행의 header를 추출하기 위해, header로 label된 모든 행이 전체적으로 포함되었다. 이번 작업의 목표 중 하나는 QA 직무 상에서 추출을 향상시키기 위해 외부의 메타데이터를 줄이는 것이다.
HTML table로부터 데이터 추출이 옳지 않은 것이 아님을 상기하지만, 그것은 다른 문제를 준다. 행과 cell, 표는HTML
markup에 의해 묘사되므로 표를 찾는 것이 어렵지는 않다. 하지만 HTML 테이블은 종종 data를 제공하는 대신에 문서들을 형태화한다 – 언어와 레이아웃의 조합이 테이블에서 정보를 추출하는 데에 있어 중요하다는 것을 다시 한번 입증했다. 내용의 판단은 테이블에 데이터가 처리될만한 가치가 있는지 확인해야 한다. 마크업의 사용은 일관되지 않아 header line과 data cell이 아직 정의가 필요하며, text table안에 그저 존재한다. 우리는 여기에 제공된 기술이 HTML table에도 적용되길 바라고 있다.
Conditional Random Fields
Conditional Random Fields는 다른 지정된 input node에 assign된 지정된 output node의 조건부 확률을 계산하는 데 쓰이는 비방향성 그래프 모델이다.
그래프 모델의 지정된 output node와 같은 특수한 경우는 선형 체인으로 edge가 링크되어 있으며, CRF는 output node 사이에서 일차 마르코프 독립 가정을 만드므로 유한 상태 머신 (FSM)에 상응한다. 이러한 경우 CRF는 조건부 훈련된 hidden Markov 모델로서 거칠게 이해될 수 있다. 이러한 타입의 CRF들은 globally-normalized 확장인데, label-bias problem을 회피하는 MEMM이다.
이 때, $Z_o$는 모든 상태 서열에 대한 normalization factor이며, $f_k (s_{t-1},s_t,o,t)$는 임의의 feature function이며, $\lambda_k$는 각각 feature function에 대한 학습된 weight이다. 예를 들어 feature function는 대부분의 케이스에서 0 값을 가지며, 오직 $s_{t-1}$이 상태가 #1 (label HEADER를 갖는 상태)일 경우에만 값을 1가지고, $s_t$값이 상태가 #2 (DATAROW 라벨을 갖는 상태) 일 경우여야 하고, 그리고 $o$의 position t에서의 관찰값이 한 칸 이상으로 분리된 숫자를 포함한 text line이여만 한다. 보다 높은 값의 $\lambda$ 값은 그들의 상응하는 FSM 변환을 더 일으키며, 그렇기 때문에 이 예시의 weight $\lambda_k$값은 넓게 분포된 숫자들의 대부분 table의 data row에 있기 때문에 positive 값이여만 한다. 보다 일반적으로, feature function은 이전 행, 다음 행 및 모든 행렬에 대한 질의를 포함하여 입력 시퀀스에 대한 임의의 질문을 강력하게 요청할 수 있는데, 그들은 또한 $-\infty$에서 $\infty$까지의 임의의 값을 가질 수 있다.
CRF는 상태 서열의 전체 확률을 기반으로 label 서열의 조건부 확률을 정의한다:
$$ p_\Lambda (l|o) = \sum_{s:l(s)=1} p_\Lambda(s|o) $$
이 때, $l(s)$는 sequence s에 있는 상태의 label에 상응하는 label 서열이다.
normalization factor, $Z_o$ (partition function으로써 통계 물리학으로 알려진)이 가능한 모든 상태 서열의 "score"라는 것을 상기해라.
$$ Z_o = \sum_{s \in S^T} exp( \sum_{t=1}^T \sum_k \lambda_k f_k(s_{t-1},s_t,o,t) ) $$
그리고 상태 서열의 숫자는 input 서열 길이 T의 exponential이다. 임시 구조화된 CRF에서 닫혀진 형태에서 partition function을 계산하는 것은, 다루기 힘들고 Gibbs sampling이나 loopy belief propagation과 같은 근사 방법이 사용되어야만 한다. 선형 사슬 구조 CRF에서 그 partition function은 동적 프로그래밍에서 효과적으로 계산될 수 있다. 보다 더 디테일한 내용은 subsection에서 확인할 수 있다.
Efficient Inference in CRFs
히든 마르코프 모델 (HMM)을 위한 forward-backward로써, input 서열의 특정한 위치에 있는 두 개의 RF 상태 사이에 기반되는 특정 변환의 확률은 동적 프로그래밍에서 효과적으로 계산될 수 있다. 우리는 쉽게 수정된 "forward value"를 정의할 수 있다, $\alpha_t(s_i)$, 이며 observation $<o_1, ...,o_t>$가 주어진 상태 $s_i$에 도달하는 확률이다. 우리는 $\alpha_0(s)$가 각각의 상태 s에서 시작하는 확률이며 다음과 같이 정의된다:
$$\alpha_{t+1}(s) = \sum_{s^{\prime}} \alpha_t(s^{\prime})exp(\sum_k \lambda_k f_k(s^{\prime},s,o,t))$$
backward 방법과 Baum-Welch의 남아있는 디테일도 유사하게 정의되어있다. $Z_o$는 그후 $\sum_s \alpha_T(s)$가 된다. 주어진 관찰 서열에서 가장 있을 법한 상태 서열을 찾는 Viterbi 알고리즘을 원래 HMM 형태로부터 상응하여 수정될 수 있다.
Training CRFs
CRF의 $\Lambda = {\lambda...}$ weight는 대표적으로 training set의 label 서열의 조건부 log-likelihood, L을 최대화시키게 설정되어 있다, training set은 $D = \{<o,l>^{(1)}, ... <o,l>^{(j)}, ..., <o,l>^{(N)} \}$이다
$$ L = \sum_{j=1}^N log(p_\Lambda(l^{(j)}|o^{(j)})) - \sum_k \frac {\lambda_k^2}{2\sigma^2} $$
parameter상에 있는 second sum은 Gaussian prior이며, variance $\sigma^2$을 사용하여, training data의 희소성을 극복하는 데 도움이 되는 smoothing을 제공한다.
training label들이 상태 서열을 모호하지 않게 만들어 줄 때, CRF과 같은 exponential model의 likelihood function은 convex하고, 그렇기 때문에 그곳에 local maxima가 없고, 그러므로 global optimum을 찾는 것이 보증된다.
CRF의 본 목표가 iterative scaling에 기반된 training 방법을 묘사하더라도, CRF와 다른 maximum extropy - (L-BFGS와 같은 quasi-Newton 방법에 의한 exponential model style)를 훈련하는 것이 현저히 빠르다. 이 방법은 이전 1차 미분 파생어의 유한 window를 지속적으로 실행하는 것으로 likelihood의 2차 미분을 근사한다. Sha와 Pereira는 L-BFGS에 의한 CRF를 훈련하는 것이 반복적인 스케일링보다 몇 배 빠르고, conjugate gradient보다 훨씬 빠르다는 것을 보여준다.
L-BFGS는 간단히 black-box 최적화로 다뤄질 수 있으며, 이는 오직 function의 일차 미분이 최적화되도록 제공하는 것을 요구한다. instance j에 대한 training label이 그 상태 경로를 모호하지 않게 만든다고 했을 때, $s^(j)$가 경로를 말한다고 할때, log-likelihood의 일차 미분은 다음과 같다.
$$ \frac{\delta L}{\delta \lambda_k} = ( \sum^N_{j=1} C_k(s^{(j)},o^{(j)})) - (\sum^N_{j=1}\sum_s p_\Lambda (s|o^{(j)})C_k(s,o^{(j)})) - \frac{\lambda_k}{\sigma^2} $$
$C_k(s,o)$는 모든 position에서 $f_k(s_{t-1},s_t,o,t)$ 값의 합과 같은, s, o상에서 feature k의 count값이다. 마지막 term은 Gaussian prior의 미분 값이다.
괄호 안의 위쪽 용어는 트레이닝 레이블이 올바른 상태 결로를 결정하는 데 사용되는 경우 특성 k의 예상 갯수에 해당한다. 괄호 안의 아랫쪽 용어는 가능성있는 상태 경로를 결정하기 위한 현재의 CRF 매개 변수인 $\Lambda$를 사용하여 특징 k의 예상 갯수에 상응시킨다. 간단히 매칭이 된다면, CRF 매개 변수로 선택된 상태 경로가 레이블이 지정된 데이터의 상태 결로와 일치할 때 미분값은 0이 된다. 학습 레이블이 단일 상태 경로를 불분명하게 하지 않으면, 기대 최적화를 사용하여 누락 상태 경로를 채울 수 있다.
TABLE EXTRATION WITH CRFS
Line Labels
tag가 있는 문서의 각 line label을 하는 것으로 table 추출을 시작한다. 이 때 tag는 table에 관계되는 line의 기능등을 설명한다. 우리가 사용하는 label의 set은 Web 문서에서 table의 거대한 양을 검사해 보는 것으로 디자인했다. 좋은 labeling은 두 가지 목표를 이룬다. 그것은 table location 즉, table의 boundary를 표시하고 QA를 위해 유용하게 row의 type들을 정의한다. 이 section은 각각의 label을 설명한다.
Non-extraction Labels
비 추출 label은 table cell들에 대한 정보 제공에 기여하지 않는 line들을 말한다. 세 개의 label은, Nontable, Blankline 그리고 Separator가 있다. Non-table은 table과 관련이 없는 text line들을 의미한다. Nontable을 보통 table의 바깥 부분에서 나타난다. Blankline은 보이는 text가 없는 line들을 말한다. blankline label은 table의 안과 밖 모두에서 나타난다. Separator는 punctuation character (-, *, 기타 등등)을 section을 구분하기 위해 사용되는 line들을 의미한다. 이것은 문서 어디에서든 발견할 수 있다.
Header Labels
Header label은 data cell들의 metadata들을 포함하는 line을 말한다. header line에 있는 Information의 일부분이나 전체는,아래 data cell들과 결합된다. 그 Header label은, Title, Superheader, TableHeader, SubHeader, SectionHeader로 이루어진다. Title은 모든 내용이 table의 모든 data cell들과 연결되어야 하는 text의 line을 의미한다. Superheader line은 복수의 열에 분포하는 data cell들과 결합해야하는 text를 포함한다. Superheader는 Table Header line의 위에 나타난다. TableHeader는 data cell과 header cell 사이에 1대1 대응하는 line을 의미한다. SuperHeader와 같이 SubHeader는 복수의 열 결합을 가지고 있는 text를 의미하지만 TableHeader label의 아래에 위치한다. SectionHeader는 data의 다음 몇 줄의 데이터와 관련된 텍스트 줄을 나타낸다. SectionHeader label은 SectionHeader의 하위 주제인 데이터 행을 그룹화하는 경우가 많다.
Data Row Labels
Data row label은 추출하기 위한 개별의 정보인, data cell들을 포함하는 행을 말한다. Data row는 종종 row를 위한 header 정보를 포함하기도 한다. data row는 DataRow, SectionDatarow로 이루어진다. DataRow는 SuperHeader, TableHeader 그리고 SubHeader line 상에서 발견된 column header인 행을 말한다. SectionDataRow는 data cell들이 SectionaHeader에 의해 마킹되었을 때의 행을 말한다.
Caption Labels
Caption Label은 data 밑에 있지만, table에 적용되는 행들을 말한다. caption label에는 TableFootnote, TableCaption이 있다. TableFootnote는 table 상에서 cell과 line을 위한 reference를 제공하고, TableCaption은 전체 table을 참조하는 text line을 의미한다.
Feature Set
Pinto et al.은 line type의 얕은 범위를 정의하기 위해 heuristic table extractor를 사용한 feature를 묘사했다. 이 작업은 feature의 시작점으로 제공된다. 하지만, 한 가지 차이점은 dash와 같은 separator character를 다룬다는 것이다. CAG를 생성하는 동안, 이러한 문자는 공백으로 처리된다. 구분 기호 문자가 공백 문자와는 다른 의미를 전달할 수 있다는 믿음은 이 실험에 포함되는 것을 자극했다. 시스템이 개발됨에 따라 개발 데이터의 성능을 향상시키는 다른 기능이 추가되었다.
White Space Features
문서와 표에 사용되는 공백은 가독성을 향상시킨다. 보통 이러한 사용은 table cell을 나누고, table에 들여쓰기를 하거나 sub-section data row에 들여쓰기를 하고, text line의 구분을 주기 위해서였다. 이 연구의 목적을 위해 공백은 Java 패턴 클래스에서 정의된 정규화 표현식 "\s"와 매칭시키는 character가 된다. 그 공백 feature는 다음과 같다:
1. 최소 4개의 연속된 공백 character가 data row에서 발견되고, data로부터 행 header를 구분시키고, 중앙에 있는 title에 있는 경우
2. 최소 네 칸의 공백 들여쓰기는 title line에서 발견되고 종종 row header column이 label되지 않는 header line이나, sub-header나 super-header의 시작포인트에서 발견된다.
3. space가 아닌 문자열 사이에 최소 두 개의 연속적인 공백은 보통 data와 header line에서 cell들을 나누는 데 쓰인다. 최소 두 개의 gap은 table line의 지시자로 쓰인다
4. 최소 다섯 개의 연속적인 공백의 큰 gap은 때때로 data로부터 row header를 구분하기 위한 몇 개의 column이 있는 table에서 쓰인다.
5. 들여 쓰기로 인해 이러한 행이 일반 데이터 행에서 벗어나기 때문에 평범한 data row로부터 단수의 공백 들여쓰기는 종종 section data row에서 발견된다.
6. 모든 space 문자열은 정규화 표현 ^\s*$\$$, 비어있는 줄과 매칭되는 행의 특징이다.
7. 첫번째 공백이 아닌 문자열로부터의 공백의 percentage는 산문으로부터 data row를 구분해준다. data row는 공백의 높은 비율을 가지는 경향이 있다.
Text Features
출력이 가능한 문자열들은 또한 관찰되고 있는 행의 유형들에 대한 정보를 포함한다. 숫자, 핵심이 되는 단어, line의 layout 형태의 사용은 전부 line이 table인지 아닌지를 구분가능케하는 특징을 부여한다. text feature는 다음과 같다.
1. Cell들은 gap 사이에 있는 text이다. 한 line의 세 개의 cell은 data line의 특징이다.
2. table 머리글 (월 약어, 연도 문자열, 다른 키워드)에서 일반적인 문자열은 머리글 기능을 구성한다. 이 기능은 해당 문자열에서 발견된 행의 문자에 대한 백분율로 표시된다.
3. Alphabet characters (A-Za-z)는 table의 text header로부터 숫자로 이루어진 data row를 구분하는데 유용하다. 그 기능은 line상에서 공백이 아닌 문자열의 백분율로 표시된다.
4. Digit characters (0-9)도 table의 text header로부터 숫자로 이루어진 data row를 구분하는데 유용하며, 그 기능 역시 line상에서 공백이 아닌 문자열의 백분율로 표시된다.
Separator Features
구두점 (기호)들은 table을 형태화시키는데 사용된다. dash의 line은 table의 section의 구분선들을 묘사한다. 수직 기호는 cell들을 구분하며 두 개의 특징이 구두점에서 직접적으로 보인다.
1. Separator characters (-,+,_,!,=,:,*)는 보통 table의 section을 구분하는 데 쓰이며 열의 section을 표시한다. 이러한 특징은 행의 공백이 아닌 문자열의 백분율로 표시된다.
2. 네 개의 연속적인 온점 (.) 은 행 머리글이 목차와 같이 단일 데이터 열에서 큰 거리로 구분되는 테이블을 나타낸다. 마침표는 공백 문자로 구분되거나 구분되지 않을 수도 있다.
Feature Representation
각각의 특징들은 binary value로 표시된다. 1은 feature가 나타남을 말하고, 0은 feature의 부재를 말한다. 백분율 특징을 위해, threshold가 설정되는데, feature가가 이들에 하나의 점수를 부여한다. Threshold는 다음과 같다.
CRF와 함께 연속적인 값 feature들을 사용하는 것은 이산 값 feature를 사용하는 것만큼이나 쉬워졌다. 이러한 백분율 feature가 binary feature로 다뤄지지 않지만 실제 백분율 값이 입력이라는 것을 상기해라.
Conjunctions of Features
Feature의 결합.
CRF는 현재 label의 전후로부터 정보를 고려하는 능력이 있다. 이 작업을 수행하는 방법 중 하나는 feature의 결합을 살펴보는 것이다. 한 line에서 feature의 값은 또 다른 line의 feature 값에 의해 곱해지고, 새로운 feature를 생성한다. (Feature1&Feature2와 같이). 결합은 feature의 선형 결합이 가질 수 없는 관계를 포착하는 데 도움이 된다. 이번 실험들에서, 사용된 결합은 이전 line과 현재 line, 현재 line과 다음 line 그리고 다음 두 개의 line의 결합이다.
Data Set
우리는 2001년 6월에 형성된 www.FedStats.gov 사이트를 crawl링 하는 것으로 문서의 거대한 set를 모았다. 문서들은 이러한 문서가 table을 포함하고 있다고 추측하는 초기의 heuristic 알고리즘에 기반한 이 실험들로 선택되었다. 이 set로부터 문서들이 무작위로 선정되었다. 이 set는 table을 포함하거나 포함하지 않은 문서들을 포함한다.
이 문서들의 각각의 line은 section 4.1에서 묘사된 12개의 label 중 하나로 label되었다. 간단한 heuristic program이 각 행의 label을 위한 추측을 만들고 실행한다. 사람 판단은 그 후에 heuristic labeling의 실수를 바로잡고자 고용되었다.
첫번째 52개의 문서들은 training set으로 label되었다. 이 52개의 문서들은 31915개의 text line과 5764개의 table line을 포함한다. 그 후 6개의 문서들은 개발 set으로 선정되었다. 이 6개의 문서는 5817개의 text line과 3607개의 table line으로 구성되어있다. 마지막으로 52개보다 많은 문서들이 label되었고, 26947개의 text line과 5916개의 table line을 포함하고 있다. 이 문서는 마지막 test data로 사용되었다.
Experimental Results
Alternative Models
우리는 CRF를 이전에 설명한 동일한 (이진) feature set을 사용하도록 구성된 두 개의 대체 모델과 비교한다. CRF는 finite state model과 conditionally-trained log-linear model의 장점을 결합한다. 이 임시의 모델들은 두 가지 이점을 통합의 중요성을 입증하기 위해 선택된다.
CRF와 같은 히든 마르코프 모델은 마르코프 모델이다. 하지만 관측 시퀀스에 주어진 레이블 시퀀스의 조건부 확률보다는 관측 시퀀스와 레이블 상태 시퀀스의 생성적 공동 확률을 최대화하도록 훈련된다. 우리는 smooth한 multivariate Bernoulli와 함께 복수의 이진 발견된 feature를 포착한다.
두 번째 대안 모델인, Maimum Entropy 분류자는 CRF와 비슷하게 조건부 확률을 최대화하도록 훈련받은 log-linear model이다. 하지만 그것은 유한상태 context를 대표하지 않는다. 그것은 대신에 각각의 line들을 독립적으로 분류한다. CRF와 함께 우리는 Gaussian prior를 사용하고 L-BFGS을 사용하여 학습한다.
Training CRFs
우리의 Java implementation을 사용하여, 우리는 L-BFGS에 의한 CRF의 두 가지 버전을 학습했다. 오직 CRF Binary의 이진 feature를 사용한 하나의 버전은 147번의 반복을 통해 수렴시켰다. 다른 버전은 백분율 feature의 실제 값을 사용했지만 다른 모든 feature들은 이진 방법으로 다뤄졌고, 188번의 반복으로 수렴시켰다. 이 두 버전 모두 Gaussian prior와 feature의 같은 결합을 사용하였다.
Evaluation
Table Line Location
table 위치의 정확도는 F-measure에 의해 평가되었다: $\frac{2*Recall*Precision}{Recall+Precision}$. 이 경우, recall은 table에 실제로 포함된 것으로 표시된 라벨의 수(NonTable, BlankLine, Separator 제외)를 실제 테이블 줄 수로 나눈 값이다. Precision은 프로그램에서 테이블 line으로 label된 총 줄 수와 동일한 분자를 분모로 사용한다. Table 2가 HMM과 두 개의 CRF에 대한 결과를 보여준다. CRF Binary는 CRF continuous가 실제 백분율로 백분율 feature를 표시하는 반면에 binary feature를 사용하였다.
Line Identification
system이 발전되는 동안, 작은 평가 set이 performance가 향상되는지를 확인하기 위해 사용되었다. data의 더 큰 set은 마지막 test를 위해 사용되었고, 최고로 훈련된 CRF가 결정될 때 까지는 평가가 이루어지지 않는다. development와 test data의 결과가 Table 3에 있다. 모든 네 개의 process는 development set에서 잘 작동하였지만, CRF의 우월성이 test data 상에서 빛이 난다. test data를 보면, 대부분의 문서가 평범하지 않은 구성을 가졌고, text의 line 사이에 많은 blank line이 있었다. HMM은 실수로 NonTable line을 Title로 확인했다. CRF는 이러한 점을 더 현명하게 다뤘다.
CRF가 error를 만드는지에 대한 실험에도 유용했다. Table 4는 test data에서 작동하는 가장 우수한 performance를 보여주는, CRF와 CRF Continous의 label에 대한 recall과 precision을 제공한다. 이 data set에서 Table-Header의 labeling은 특히 저조했고, 문제가 있었는데 그 이유는 잘못 label된 TableHeader line의 과반수가 NonTable이나 DataRow로 label되었기 때문이다. 이러한 것은 development set과 대조되는데, Table-Header가 대부분 다른 header line으로 missing되는 경우가 많았다. table이 missing되었을때 DataRow line이 대부분 missing 되더라도, SectionDatarow line은 대부분 DataRow line으로 missing되었고, 그래서 NonTable이 가장 빈도수가 많은 실수로 선정되었다. NonTable line의 대부분은 Table-Caption으로 mislabel되었고 이러한 mislabel들은 table의 끝의 문맥에서는 나타나지 않았다. CRF의 이러한 양상을 더욱 더 파헤쳐볼 필요가 있다.
Figure 2는 table label이 잘못된 두 개의 예시를 보여준다. 첫 번째는 contents의 table의 예시이다. 그곳에 gap structure가 없다는 것을 확일해라. 그곳에는 table의 몸체를 가르키는 구조를 갖고 있는 일련의 line이 없다. 네 개의 연속적인 온점 feature는 data row를 label하기에 충분히 강력하다는 것을 입증하지 못했다. data row 없이, table은 없다. 이것은 training data가 overfitting되었다는 예시가 된다. training set에 table의 이 형태가 두 가지 예시가 있더라도 sample은 table의 다른 유형과 비교하여 매우 적다. 더해서, 네 개의 연속적인 온점은 특징은 gap을 포함하고 있는 data row가 있는 training set에서만 빈번하게 일어난다.
두 번째 table은 부분적으로 옳다. 하지만, row의 대부분에서 cell 사이에 gap이 부족하고 저 line들은 TableHeader로 label되었다. 하지만 CRF는 해당 line에 table-type label을 할당하는 것에 좋은 퍼포먼스를 보여주는 데 왜냐하면 식별 가능한 테이블 구조가 있기 때문이다. 그것은 이 데이터를 보는 것으로부터 명확하지만, gap이 data row를 결정할 때 over weight되었다. training data의 실험은 숫자 cell이 오직 하나의 공간으로 구분되었을 때 data row로써 오직 두 개의 line만이 label된 것을 보여준다.
결과는 또한 Pinto의 방법에 기반한 heuristic 결과함 비교되었다. 그 시스템은 line을 표시하기 위해 4개의 이름 (Caption, headers, data and non-table)을 사용했지만 우리의 label이 더 좋게 mapping되었다. CRF는 보다 적은 수의 테이블에 의해 주어진 관대한 척도를 기반으로 Heuristic program보다 더 좋은 performance를 보여주었다. CRF system에서의 향상은 오직 자동으로 추출될 수 있는 새로운 feature를 정의하는 것을 요구로 하는 반면에, heuristic system에서의 향상은 program code의 지속적인 변경을 필요로 하기 때문에 이는 매우 고무적이다. 이러한 결과는 또한 토론된 세 가지 방법 중 CRF가 가장 일관된 성능을 가짐을 보여준다.
Future Work in Table information Extraction
위에서 묘사된 CRF model은 table과 tag를 구성 line에 위치시키지만, 열에 대한 정보는 알지 못하고 개별 테이블 셀을 가로 또는 세로로 구분하지 않으며 개별 셀을 데이터 또는 헤더로 태그 지정하지 않는다. 진행중인 작업에서 우리는 다양한 수준의 노드와 수직 및 수평으로 실행되는 종속성 boundary를 가진 graphic model을 사용하여 이러한 모든 문제점을 해결하는 보다 풍부한 CRF를 구현할 것이다.
이 새로운 모델에는 텍스트의 각 줄 (위에서 설명한 모델에서처럼)의 태그를 나타내는 노드, 각 개별문자 2 (셀의 수평 분할을 나타내는 레이블이 있는)에 수평으로 연결된 노드 및 각 개별 문자에 대해 수직으로 연결된 노드 (셀의 수직 분할을 나타내는 레이블)가 있다. 후자의 두 가지 유형의 노드는 표준 OIB 스타일 분할 레이블을 사용하여 셀의 시작, 내부 및 외부 (data cell 대 header cell을 나타내는 이러한 tag의 다른 유형)를 나타낸다.
그러므로, 예를 들어 문자열 node는 Vertical-Begin/Data와 Horizontal-Interior/Data로 tag될 것이며, 이는 문자열 node가 data cell의 top이 수평적으로, data cell의 수직적으로 가운데에 있는지 추측한다.
이 모델은 선형 사슬 대신에 grid pattern으로 연결되고 위에서 설명한 동적 프로그래밍에 기반된 효과적인 추론은 더이상 불가능할 것이다. Gibbs sampling이나 loopy belief propagation은 둘 다 적용하지마, 그러나 우리는 대신에 tree agreement에 기반한 정확한 MAP 추측을 위한 방법에 의존한다. 우리의 모델의 추론은 한 사이클에서 수행되는 세 단계로 구성된다. 첫 번째로, 위에서 묘사한 것 처럼, belief propagation이 선형사슬형태의 CRF상에서 실행되는데, 이는 text의 각 line에 tag하기 위함이다. 두 번째는, belief propagation이 문자열 노드의 수평 선을 사용하여 실행되는 것이다. 세 번째 belief propagation은 문자열 노드의 수직적 선을 사용하여 실행되는 것이다. 전체 추론 절차는 1단계로 순환하며, 이전 추론 단계의 태깅 결정을 이제 feature로써 검토할 수 있다. 절차라 수렴되도록 보장된다.
효율성을 위해, 문자열 level의 추론은 오직 첫번째 단계에서 table이 포함되었을 법한 문서의 지역에서만 나타난다. data cell과 그들의 상응하는 header cell의 결합은 정교한 모델링을 요구하지 않는다. - 각각의 data cell을 위해 수평 및 수직으로 교차하는 header cell을 찾는 것을 매우 견고하게 수행할 것으로 기대되며 이 새 모델에 대한 실험이 보류 중이다.
이 모델이 개발되는 동안 QuASM 추출 프로그램을 사용하여 CRF 라벨을 사용하는 실험도 진행된다. 우리의 가설은 구식 프로그램의 Heuristic을 찾는 Column과 결합된 보다 세밀한 라벨링은 외부 메타 데이터의 문제를 해결할 것이라는 것이다. 그런 다음 cleaner 문서가 품질 관리 검색 작업에서 더 잘 수행되는 것을 보여주길 기대하고 있다.
CRF는 상태 서열의 전체 확률을 기반으로 label 서열의 조건부 확률을 정의한다:
$$ p_\Lambda (l|o) = \sum_{s:l(s)=1} p_\Lambda(s|o) $$
이 때, $l(s)$는 sequence s에 있는 상태의 label에 상응하는 label 서열이다.
normalization factor, $Z_o$ (partition function으로써 통계 물리학으로 알려진)이 가능한 모든 상태 서열의 "score"라는 것을 상기해라.
$$ Z_o = \sum_{s \in S^T} exp( \sum_{t=1}^T \sum_k \lambda_k f_k(s_{t-1},s_t,o,t) ) $$
그리고 상태 서열의 숫자는 input 서열 길이 T의 exponential이다. 임시 구조화된 CRF에서 닫혀진 형태에서 partition function을 계산하는 것은, 다루기 힘들고 Gibbs sampling이나 loopy belief propagation과 같은 근사 방법이 사용되어야만 한다. 선형 사슬 구조 CRF에서 그 partition function은 동적 프로그래밍에서 효과적으로 계산될 수 있다. 보다 더 디테일한 내용은 subsection에서 확인할 수 있다.
Efficient Inference in CRFs
히든 마르코프 모델 (HMM)을 위한 forward-backward로써, input 서열의 특정한 위치에 있는 두 개의 RF 상태 사이에 기반되는 특정 변환의 확률은 동적 프로그래밍에서 효과적으로 계산될 수 있다. 우리는 쉽게 수정된 "forward value"를 정의할 수 있다, $\alpha_t(s_i)$, 이며 observation $<o_1, ...,o_t>$가 주어진 상태 $s_i$에 도달하는 확률이다. 우리는 $\alpha_0(s)$가 각각의 상태 s에서 시작하는 확률이며 다음과 같이 정의된다:
$$\alpha_{t+1}(s) = \sum_{s^{\prime}} \alpha_t(s^{\prime})exp(\sum_k \lambda_k f_k(s^{\prime},s,o,t))$$
backward 방법과 Baum-Welch의 남아있는 디테일도 유사하게 정의되어있다. $Z_o$는 그후 $\sum_s \alpha_T(s)$가 된다. 주어진 관찰 서열에서 가장 있을 법한 상태 서열을 찾는 Viterbi 알고리즘을 원래 HMM 형태로부터 상응하여 수정될 수 있다.
Training CRFs
CRF의 $\Lambda = {\lambda...}$ weight는 대표적으로 training set의 label 서열의 조건부 log-likelihood, L을 최대화시키게 설정되어 있다, training set은 $D = \{<o,l>^{(1)}, ... <o,l>^{(j)}, ..., <o,l>^{(N)} \}$이다
$$ L = \sum_{j=1}^N log(p_\Lambda(l^{(j)}|o^{(j)})) - \sum_k \frac {\lambda_k^2}{2\sigma^2} $$
parameter상에 있는 second sum은 Gaussian prior이며, variance $\sigma^2$을 사용하여, training data의 희소성을 극복하는 데 도움이 되는 smoothing을 제공한다.
training label들이 상태 서열을 모호하지 않게 만들어 줄 때, CRF과 같은 exponential model의 likelihood function은 convex하고, 그렇기 때문에 그곳에 local maxima가 없고, 그러므로 global optimum을 찾는 것이 보증된다.
CRF의 본 목표가 iterative scaling에 기반된 training 방법을 묘사하더라도, CRF와 다른 maximum extropy - (L-BFGS와 같은 quasi-Newton 방법에 의한 exponential model style)를 훈련하는 것이 현저히 빠르다. 이 방법은 이전 1차 미분 파생어의 유한 window를 지속적으로 실행하는 것으로 likelihood의 2차 미분을 근사한다. Sha와 Pereira는 L-BFGS에 의한 CRF를 훈련하는 것이 반복적인 스케일링보다 몇 배 빠르고, conjugate gradient보다 훨씬 빠르다는 것을 보여준다.
L-BFGS는 간단히 black-box 최적화로 다뤄질 수 있으며, 이는 오직 function의 일차 미분이 최적화되도록 제공하는 것을 요구한다. instance j에 대한 training label이 그 상태 경로를 모호하지 않게 만든다고 했을 때, $s^(j)$가 경로를 말한다고 할때, log-likelihood의 일차 미분은 다음과 같다.
$$ \frac{\delta L}{\delta \lambda_k} = ( \sum^N_{j=1} C_k(s^{(j)},o^{(j)})) - (\sum^N_{j=1}\sum_s p_\Lambda (s|o^{(j)})C_k(s,o^{(j)})) - \frac{\lambda_k}{\sigma^2} $$
$C_k(s,o)$는 모든 position에서 $f_k(s_{t-1},s_t,o,t)$ 값의 합과 같은, s, o상에서 feature k의 count값이다. 마지막 term은 Gaussian prior의 미분 값이다.
괄호 안의 위쪽 용어는 트레이닝 레이블이 올바른 상태 결로를 결정하는 데 사용되는 경우 특성 k의 예상 갯수에 해당한다. 괄호 안의 아랫쪽 용어는 가능성있는 상태 경로를 결정하기 위한 현재의 CRF 매개 변수인 $\Lambda$를 사용하여 특징 k의 예상 갯수에 상응시킨다. 간단히 매칭이 된다면, CRF 매개 변수로 선택된 상태 경로가 레이블이 지정된 데이터의 상태 결로와 일치할 때 미분값은 0이 된다. 학습 레이블이 단일 상태 경로를 불분명하게 하지 않으면, 기대 최적화를 사용하여 누락 상태 경로를 채울 수 있다.
TABLE EXTRATION WITH CRFS
Line Labels
tag가 있는 문서의 각 line label을 하는 것으로 table 추출을 시작한다. 이 때 tag는 table에 관계되는 line의 기능등을 설명한다. 우리가 사용하는 label의 set은 Web 문서에서 table의 거대한 양을 검사해 보는 것으로 디자인했다. 좋은 labeling은 두 가지 목표를 이룬다. 그것은 table location 즉, table의 boundary를 표시하고 QA를 위해 유용하게 row의 type들을 정의한다. 이 section은 각각의 label을 설명한다.
Non-extraction Labels
비 추출 label은 table cell들에 대한 정보 제공에 기여하지 않는 line들을 말한다. 세 개의 label은, Nontable, Blankline 그리고 Separator가 있다. Non-table은 table과 관련이 없는 text line들을 의미한다. Nontable을 보통 table의 바깥 부분에서 나타난다. Blankline은 보이는 text가 없는 line들을 말한다. blankline label은 table의 안과 밖 모두에서 나타난다. Separator는 punctuation character (-, *, 기타 등등)을 section을 구분하기 위해 사용되는 line들을 의미한다. 이것은 문서 어디에서든 발견할 수 있다.
Header Labels
Header label은 data cell들의 metadata들을 포함하는 line을 말한다. header line에 있는 Information의 일부분이나 전체는,아래 data cell들과 결합된다. 그 Header label은, Title, Superheader, TableHeader, SubHeader, SectionHeader로 이루어진다. Title은 모든 내용이 table의 모든 data cell들과 연결되어야 하는 text의 line을 의미한다. Superheader line은 복수의 열에 분포하는 data cell들과 결합해야하는 text를 포함한다. Superheader는 Table Header line의 위에 나타난다. TableHeader는 data cell과 header cell 사이에 1대1 대응하는 line을 의미한다. SuperHeader와 같이 SubHeader는 복수의 열 결합을 가지고 있는 text를 의미하지만 TableHeader label의 아래에 위치한다. SectionHeader는 data의 다음 몇 줄의 데이터와 관련된 텍스트 줄을 나타낸다. SectionHeader label은 SectionHeader의 하위 주제인 데이터 행을 그룹화하는 경우가 많다.
Data Row Labels
Data row label은 추출하기 위한 개별의 정보인, data cell들을 포함하는 행을 말한다. Data row는 종종 row를 위한 header 정보를 포함하기도 한다. data row는 DataRow, SectionDatarow로 이루어진다. DataRow는 SuperHeader, TableHeader 그리고 SubHeader line 상에서 발견된 column header인 행을 말한다. SectionDataRow는 data cell들이 SectionaHeader에 의해 마킹되었을 때의 행을 말한다.
Caption Labels
Caption Label은 data 밑에 있지만, table에 적용되는 행들을 말한다. caption label에는 TableFootnote, TableCaption이 있다. TableFootnote는 table 상에서 cell과 line을 위한 reference를 제공하고, TableCaption은 전체 table을 참조하는 text line을 의미한다.
Feature Set
Pinto et al.은 line type의 얕은 범위를 정의하기 위해 heuristic table extractor를 사용한 feature를 묘사했다. 이 작업은 feature의 시작점으로 제공된다. 하지만, 한 가지 차이점은 dash와 같은 separator character를 다룬다는 것이다. CAG를 생성하는 동안, 이러한 문자는 공백으로 처리된다. 구분 기호 문자가 공백 문자와는 다른 의미를 전달할 수 있다는 믿음은 이 실험에 포함되는 것을 자극했다. 시스템이 개발됨에 따라 개발 데이터의 성능을 향상시키는 다른 기능이 추가되었다.
White Space Features
문서와 표에 사용되는 공백은 가독성을 향상시킨다. 보통 이러한 사용은 table cell을 나누고, table에 들여쓰기를 하거나 sub-section data row에 들여쓰기를 하고, text line의 구분을 주기 위해서였다. 이 연구의 목적을 위해 공백은 Java 패턴 클래스에서 정의된 정규화 표현식 "\s"와 매칭시키는 character가 된다. 그 공백 feature는 다음과 같다:
1. 최소 4개의 연속된 공백 character가 data row에서 발견되고, data로부터 행 header를 구분시키고, 중앙에 있는 title에 있는 경우
2. 최소 네 칸의 공백 들여쓰기는 title line에서 발견되고 종종 row header column이 label되지 않는 header line이나, sub-header나 super-header의 시작포인트에서 발견된다.
3. space가 아닌 문자열 사이에 최소 두 개의 연속적인 공백은 보통 data와 header line에서 cell들을 나누는 데 쓰인다. 최소 두 개의 gap은 table line의 지시자로 쓰인다
4. 최소 다섯 개의 연속적인 공백의 큰 gap은 때때로 data로부터 row header를 구분하기 위한 몇 개의 column이 있는 table에서 쓰인다.
5. 들여 쓰기로 인해 이러한 행이 일반 데이터 행에서 벗어나기 때문에 평범한 data row로부터 단수의 공백 들여쓰기는 종종 section data row에서 발견된다.
6. 모든 space 문자열은 정규화 표현 ^\s*$\$$, 비어있는 줄과 매칭되는 행의 특징이다.
7. 첫번째 공백이 아닌 문자열로부터의 공백의 percentage는 산문으로부터 data row를 구분해준다. data row는 공백의 높은 비율을 가지는 경향이 있다.
Text Features
출력이 가능한 문자열들은 또한 관찰되고 있는 행의 유형들에 대한 정보를 포함한다. 숫자, 핵심이 되는 단어, line의 layout 형태의 사용은 전부 line이 table인지 아닌지를 구분가능케하는 특징을 부여한다. text feature는 다음과 같다.
1. Cell들은 gap 사이에 있는 text이다. 한 line의 세 개의 cell은 data line의 특징이다.
2. table 머리글 (월 약어, 연도 문자열, 다른 키워드)에서 일반적인 문자열은 머리글 기능을 구성한다. 이 기능은 해당 문자열에서 발견된 행의 문자에 대한 백분율로 표시된다.
3. Alphabet characters (A-Za-z)는 table의 text header로부터 숫자로 이루어진 data row를 구분하는데 유용하다. 그 기능은 line상에서 공백이 아닌 문자열의 백분율로 표시된다.
4. Digit characters (0-9)도 table의 text header로부터 숫자로 이루어진 data row를 구분하는데 유용하며, 그 기능 역시 line상에서 공백이 아닌 문자열의 백분율로 표시된다.
Separator Features
구두점 (기호)들은 table을 형태화시키는데 사용된다. dash의 line은 table의 section의 구분선들을 묘사한다. 수직 기호는 cell들을 구분하며 두 개의 특징이 구두점에서 직접적으로 보인다.
1. Separator characters (-,+,_,!,=,:,*)는 보통 table의 section을 구분하는 데 쓰이며 열의 section을 표시한다. 이러한 특징은 행의 공백이 아닌 문자열의 백분율로 표시된다.
2. 네 개의 연속적인 온점 (.) 은 행 머리글이 목차와 같이 단일 데이터 열에서 큰 거리로 구분되는 테이블을 나타낸다. 마침표는 공백 문자로 구분되거나 구분되지 않을 수도 있다.
Feature Representation
각각의 특징들은 binary value로 표시된다. 1은 feature가 나타남을 말하고, 0은 feature의 부재를 말한다. 백분율 특징을 위해, threshold가 설정되는데, feature가가 이들에 하나의 점수를 부여한다. Threshold는 다음과 같다.
Conjunctions of Features
Feature의 결합.
CRF는 현재 label의 전후로부터 정보를 고려하는 능력이 있다. 이 작업을 수행하는 방법 중 하나는 feature의 결합을 살펴보는 것이다. 한 line에서 feature의 값은 또 다른 line의 feature 값에 의해 곱해지고, 새로운 feature를 생성한다. (Feature1&Feature2와 같이). 결합은 feature의 선형 결합이 가질 수 없는 관계를 포착하는 데 도움이 된다. 이번 실험들에서, 사용된 결합은 이전 line과 현재 line, 현재 line과 다음 line 그리고 다음 두 개의 line의 결합이다.
Data Set
우리는 2001년 6월에 형성된 www.FedStats.gov 사이트를 crawl링 하는 것으로 문서의 거대한 set를 모았다. 문서들은 이러한 문서가 table을 포함하고 있다고 추측하는 초기의 heuristic 알고리즘에 기반한 이 실험들로 선택되었다. 이 set로부터 문서들이 무작위로 선정되었다. 이 set는 table을 포함하거나 포함하지 않은 문서들을 포함한다.
이 문서들의 각각의 line은 section 4.1에서 묘사된 12개의 label 중 하나로 label되었다. 간단한 heuristic program이 각 행의 label을 위한 추측을 만들고 실행한다. 사람 판단은 그 후에 heuristic labeling의 실수를 바로잡고자 고용되었다.
첫번째 52개의 문서들은 training set으로 label되었다. 이 52개의 문서들은 31915개의 text line과 5764개의 table line을 포함한다. 그 후 6개의 문서들은 개발 set으로 선정되었다. 이 6개의 문서는 5817개의 text line과 3607개의 table line으로 구성되어있다. 마지막으로 52개보다 많은 문서들이 label되었고, 26947개의 text line과 5916개의 table line을 포함하고 있다. 이 문서는 마지막 test data로 사용되었다.
Experimental Results
Alternative Models
우리는 CRF를 이전에 설명한 동일한 (이진) feature set을 사용하도록 구성된 두 개의 대체 모델과 비교한다. CRF는 finite state model과 conditionally-trained log-linear model의 장점을 결합한다. 이 임시의 모델들은 두 가지 이점을 통합의 중요성을 입증하기 위해 선택된다.
CRF와 같은 히든 마르코프 모델은 마르코프 모델이다. 하지만 관측 시퀀스에 주어진 레이블 시퀀스의 조건부 확률보다는 관측 시퀀스와 레이블 상태 시퀀스의 생성적 공동 확률을 최대화하도록 훈련된다. 우리는 smooth한 multivariate Bernoulli와 함께 복수의 이진 발견된 feature를 포착한다.
두 번째 대안 모델인, Maimum Entropy 분류자는 CRF와 비슷하게 조건부 확률을 최대화하도록 훈련받은 log-linear model이다. 하지만 그것은 유한상태 context를 대표하지 않는다. 그것은 대신에 각각의 line들을 독립적으로 분류한다. CRF와 함께 우리는 Gaussian prior를 사용하고 L-BFGS을 사용하여 학습한다.
Training CRFs
우리의 Java implementation을 사용하여, 우리는 L-BFGS에 의한 CRF의 두 가지 버전을 학습했다. 오직 CRF Binary의 이진 feature를 사용한 하나의 버전은 147번의 반복을 통해 수렴시켰다. 다른 버전은 백분율 feature의 실제 값을 사용했지만 다른 모든 feature들은 이진 방법으로 다뤄졌고, 188번의 반복으로 수렴시켰다. 이 두 버전 모두 Gaussian prior와 feature의 같은 결합을 사용하였다.
Evaluation
Table Line Location
table 위치의 정확도는 F-measure에 의해 평가되었다: $\frac{2*Recall*Precision}{Recall+Precision}$. 이 경우, recall은 table에 실제로 포함된 것으로 표시된 라벨의 수(NonTable, BlankLine, Separator 제외)를 실제 테이블 줄 수로 나눈 값이다. Precision은 프로그램에서 테이블 line으로 label된 총 줄 수와 동일한 분자를 분모로 사용한다. Table 2가 HMM과 두 개의 CRF에 대한 결과를 보여준다. CRF Binary는 CRF continuous가 실제 백분율로 백분율 feature를 표시하는 반면에 binary feature를 사용하였다.
Line Identification
system이 발전되는 동안, 작은 평가 set이 performance가 향상되는지를 확인하기 위해 사용되었다. data의 더 큰 set은 마지막 test를 위해 사용되었고, 최고로 훈련된 CRF가 결정될 때 까지는 평가가 이루어지지 않는다. development와 test data의 결과가 Table 3에 있다. 모든 네 개의 process는 development set에서 잘 작동하였지만, CRF의 우월성이 test data 상에서 빛이 난다. test data를 보면, 대부분의 문서가 평범하지 않은 구성을 가졌고, text의 line 사이에 많은 blank line이 있었다. HMM은 실수로 NonTable line을 Title로 확인했다. CRF는 이러한 점을 더 현명하게 다뤘다.
CRF가 error를 만드는지에 대한 실험에도 유용했다. Table 4는 test data에서 작동하는 가장 우수한 performance를 보여주는, CRF와 CRF Continous의 label에 대한 recall과 precision을 제공한다. 이 data set에서 Table-Header의 labeling은 특히 저조했고, 문제가 있었는데 그 이유는 잘못 label된 TableHeader line의 과반수가 NonTable이나 DataRow로 label되었기 때문이다. 이러한 것은 development set과 대조되는데, Table-Header가 대부분 다른 header line으로 missing되는 경우가 많았다. table이 missing되었을때 DataRow line이 대부분 missing 되더라도, SectionDatarow line은 대부분 DataRow line으로 missing되었고, 그래서 NonTable이 가장 빈도수가 많은 실수로 선정되었다. NonTable line의 대부분은 Table-Caption으로 mislabel되었고 이러한 mislabel들은 table의 끝의 문맥에서는 나타나지 않았다. CRF의 이러한 양상을 더욱 더 파헤쳐볼 필요가 있다.
Figure 2는 table label이 잘못된 두 개의 예시를 보여준다. 첫 번째는 contents의 table의 예시이다. 그곳에 gap structure가 없다는 것을 확일해라. 그곳에는 table의 몸체를 가르키는 구조를 갖고 있는 일련의 line이 없다. 네 개의 연속적인 온점 feature는 data row를 label하기에 충분히 강력하다는 것을 입증하지 못했다. data row 없이, table은 없다. 이것은 training data가 overfitting되었다는 예시가 된다. training set에 table의 이 형태가 두 가지 예시가 있더라도 sample은 table의 다른 유형과 비교하여 매우 적다. 더해서, 네 개의 연속적인 온점은 특징은 gap을 포함하고 있는 data row가 있는 training set에서만 빈번하게 일어난다.
두 번째 table은 부분적으로 옳다. 하지만, row의 대부분에서 cell 사이에 gap이 부족하고 저 line들은 TableHeader로 label되었다. 하지만 CRF는 해당 line에 table-type label을 할당하는 것에 좋은 퍼포먼스를 보여주는 데 왜냐하면 식별 가능한 테이블 구조가 있기 때문이다. 그것은 이 데이터를 보는 것으로부터 명확하지만, gap이 data row를 결정할 때 over weight되었다. training data의 실험은 숫자 cell이 오직 하나의 공간으로 구분되었을 때 data row로써 오직 두 개의 line만이 label된 것을 보여준다.
결과는 또한 Pinto의 방법에 기반한 heuristic 결과함 비교되었다. 그 시스템은 line을 표시하기 위해 4개의 이름 (Caption, headers, data and non-table)을 사용했지만 우리의 label이 더 좋게 mapping되었다. CRF는 보다 적은 수의 테이블에 의해 주어진 관대한 척도를 기반으로 Heuristic program보다 더 좋은 performance를 보여주었다. CRF system에서의 향상은 오직 자동으로 추출될 수 있는 새로운 feature를 정의하는 것을 요구로 하는 반면에, heuristic system에서의 향상은 program code의 지속적인 변경을 필요로 하기 때문에 이는 매우 고무적이다. 이러한 결과는 또한 토론된 세 가지 방법 중 CRF가 가장 일관된 성능을 가짐을 보여준다.
Future Work in Table information Extraction
위에서 묘사된 CRF model은 table과 tag를 구성 line에 위치시키지만, 열에 대한 정보는 알지 못하고 개별 테이블 셀을 가로 또는 세로로 구분하지 않으며 개별 셀을 데이터 또는 헤더로 태그 지정하지 않는다. 진행중인 작업에서 우리는 다양한 수준의 노드와 수직 및 수평으로 실행되는 종속성 boundary를 가진 graphic model을 사용하여 이러한 모든 문제점을 해결하는 보다 풍부한 CRF를 구현할 것이다.
이 새로운 모델에는 텍스트의 각 줄 (위에서 설명한 모델에서처럼)의 태그를 나타내는 노드, 각 개별문자 2 (셀의 수평 분할을 나타내는 레이블이 있는)에 수평으로 연결된 노드 및 각 개별 문자에 대해 수직으로 연결된 노드 (셀의 수직 분할을 나타내는 레이블)가 있다. 후자의 두 가지 유형의 노드는 표준 OIB 스타일 분할 레이블을 사용하여 셀의 시작, 내부 및 외부 (data cell 대 header cell을 나타내는 이러한 tag의 다른 유형)를 나타낸다.
그러므로, 예를 들어 문자열 node는 Vertical-Begin/Data와 Horizontal-Interior/Data로 tag될 것이며, 이는 문자열 node가 data cell의 top이 수평적으로, data cell의 수직적으로 가운데에 있는지 추측한다.
이 모델은 선형 사슬 대신에 grid pattern으로 연결되고 위에서 설명한 동적 프로그래밍에 기반된 효과적인 추론은 더이상 불가능할 것이다. Gibbs sampling이나 loopy belief propagation은 둘 다 적용하지마, 그러나 우리는 대신에 tree agreement에 기반한 정확한 MAP 추측을 위한 방법에 의존한다. 우리의 모델의 추론은 한 사이클에서 수행되는 세 단계로 구성된다. 첫 번째로, 위에서 묘사한 것 처럼, belief propagation이 선형사슬형태의 CRF상에서 실행되는데, 이는 text의 각 line에 tag하기 위함이다. 두 번째는, belief propagation이 문자열 노드의 수평 선을 사용하여 실행되는 것이다. 세 번째 belief propagation은 문자열 노드의 수직적 선을 사용하여 실행되는 것이다. 전체 추론 절차는 1단계로 순환하며, 이전 추론 단계의 태깅 결정을 이제 feature로써 검토할 수 있다. 절차라 수렴되도록 보장된다.
효율성을 위해, 문자열 level의 추론은 오직 첫번째 단계에서 table이 포함되었을 법한 문서의 지역에서만 나타난다. data cell과 그들의 상응하는 header cell의 결합은 정교한 모델링을 요구하지 않는다. - 각각의 data cell을 위해 수평 및 수직으로 교차하는 header cell을 찾는 것을 매우 견고하게 수행할 것으로 기대되며 이 새 모델에 대한 실험이 보류 중이다.
이 모델이 개발되는 동안 QuASM 추출 프로그램을 사용하여 CRF 라벨을 사용하는 실험도 진행된다. 우리의 가설은 구식 프로그램의 Heuristic을 찾는 Column과 결합된 보다 세밀한 라벨링은 외부 메타 데이터의 문제를 해결할 것이라는 것이다. 그런 다음 cleaner 문서가 품질 관리 검색 작업에서 더 잘 수행되는 것을 보여주길 기대하고 있다.
댓글
댓글 쓰기