Introduction
이 논문은 비정형 문서로부터 구조화된 정보를 추출(information extraction)하기 위한 end-to-end 알고리즘을 제안합니다. 기존 방법들은 이 문제를 텍스트를 1d로 serialize한 뒤 각각의 text token을 분류하는 sequential tagging 방식으로 해결하고자 하였습니다. 하지만 이 방법은 serialization 방법에 많이 의존하고, 복잡한 문서양식에 적용하기 어렵다는 문제가 있습니다. 본 논문에서는 serialization, tagging, structuralization으로 이어지는 여러 단계의 기존 접근법을 통합하여 directed graph를 생성하는 single end-to-end 알고리즘(SPADE)을 제안합니다.
Proposed Method
SPADE는 다음 세 모듈로 이루어집니다.
1) Text segment와 그 좌표를 입력받는 serializer-free encoder
2) Spatial dependency graph를 추론하는 neural graph generator
3) 최종 결과를 출력하는 parse generator
Information extraction via spatial dependency parsing
기존 shallow-parsing 접근법에서 1d serailized text를 각각 분류하는 것과 달리, SPADE에서는 2d에 위치한 text segment들의 '관계'를 유추(spatial dependency parsing)합니다. 이 관계에는 두 가지가 있는데, 첫 번째는 같은 '필드'에 속하는 text segment끼리의 관계("rel-s")이며, 두 번째는 같은 '그룹'에 속하는 text segment 끼리의 관계("rel-g") 입니다. 여기서 '필드'란 같은 카테고리의 정보를, '그룹'이란 서로 다른 필드들 중 같은 의미로 묶일 수 있는 것들의 집합을 의미합니다. 예를 들어 아래 그림의 a에 나타난 영수증에서는 첫 번째 메뉴명을 의미하는 ('volcano', 'iced', 'coffee') 세 text segment가 같은 필드를 구성하며, 이 필드와 함께 각각 수량, 단위가격, 총 금액을 의미하는 필드인 ('x4'), ('@1,000'), ('4,000') 들이 메뉴를 의미하는 하나의 그룹을 형성하게 됩니다. 이렇게 모든 텍스트를 두 가지의 관계로 설명하는 단순한 규칙은 아래 d, e 그림에서와 같이 명함, 표, 복잡한 문서의 구조를 설명하기 위한 일반적인 방법으로 사용될 수 있습니다.
Two dimensional text encoders
텍스트들의 공간적 배치를 고려한 encoding을 위하여 Transformer 구조를 차용했습니다. 서로 다른 두 text segment의 상대 좌표를 encoding하기 위하여, Transformer XL에 사용된 방식을 따라 self-attention의 계산을 아래와 같이 설계합니다.
여기서 , 는 각각 query, key 벡터를 의미하며 는 bias, 는 relative coordinate 벡터를 의미합니다. Relative coordinate는 두 text segment 사이의 상대 x, y 좌표, 거리, 각도 4개를 각각 positional embedding한 벡터를 concatenate하여 만들어집니다.
Graph Generator
rel-s, rel-g 두 가지 타입의 관계는 binary matrix 로 표현됩니다. 여기서 첨자들은 번째 text segment로부터 번째 text segment로의 타입 관계를 의미합니다. 은 만큼의 row와 만큼의 column을 가집니다. 이 matrix를 구하기 위하여 먼저 아래와 같이 을 구합니다.
여기서 는 각각의 text segment의 contextualize된 첫 번째 token을, 는 번째 field에 대한 trainable embedding vector를 의미합니다. 는 affine transform이며, 는 head text segment에 대한 vector representation을, 는 dependent text segment에 대한 vector representation을 의미합니다. 는 번째 node가 번째 field를 의미하는 virtual node라는 뜻입니다.
이 값은 아래와 같이 binarize하여 최종적으로 을 구하게 됩니다.
Parse Generator
위 단계에서 구해진 graph는 아래 세 가지 단계를 따라 parse로 바뀝니다.
1) SEEDING
rel-s를 사용하여 virtual start node들이 text segment들(seed)과 연결됩니다.
2) SERIALIZATION
Seed node들이 그래프를 통하여 연결된 text segment들과 연결됩니다.
3) GROUPING
위 1)~2)단계에서 serealized된 text segment들은 rel-g를 통하여 첫 번째 노드들끼리 연결됩니다.
이 프로세스를 요약하면 아래와 같습니다.
Experiment
Text extraction from document
SPADE 알고리즘은 post-OCR parsing에 사용됩니다. 따라서 이미지 형태의 문서는 CRAFT, Comb.best (Baek 2019)를 사용하여 먼저 OCR 결과를 얻어낸 후 SPADE를 적용하였습니다.
Learning
모델의 학습에는 cross-entropy loss와 ADAM optimizer를 사용했습니다. Batch size는 4~12였고, 전체 각도를 uniform하게 만큼 랜덤하게 회전하는 것과 삼각함수를 사용하여 전체 좌표를 랜덤하게 왜곡시키는 augmentation을 적용하였습니다.
영수증 인식 문제에서는 3.3%의 확률로 랜덤하게 한 개의 토큰을 지우거나 삽입하였고, 1.7%의 확률로 1~2개의 토큰을 text segment 뒤에 붙였습니다.
Performance metric
Evaluation은 prediction, gt에 해당하는 두 hierarchical groups of key-value pairs를 대상으로 F1 score를 측정하였습니다. Matching은 common key와 common value가 가장 많은 것을 기준으로 이루어졌고, true positive, false posotive, true negative를 각각 계산하여 F1 score를 계산하였습니다.
Image distortion
실제 문서 이미지들은 접히거나 구겨지는 등의 왜곡이 발생하는 경우가 많습니다. 이 실험에서도 마찬가지 상황을 모델링하기 위하여 translation, rotation, illumination, warping을 적용하였습니다.
Result
Parsing receipts
CORD (Park 2019)는 오픈소스 영수증 데이터셋으로, 총 1,000장으로 이루어져있습니다. SPADE의 성능은 serialization 기반의 이전 알고리즘인 POT (Hwang 2019)과 아래 표에서 비교되었습니다. CORD-R은 실제 세계에 존재하는 다양한 종이의 왜곡효과들을 표현한 데이터셋입니다. CORD-Two-Column은 두 개의 column으로 구성된 페이지를 모사하기 위하여 아래 그림과 같이 영수증 2개를 붙인 데이터셋입니다. {dev, test}-oracle 셋은 ocr을 사용하는 대신 사람이 라벨링 한 텍스트 인식 결과를 사용하는 경우입니다.
Parsing name cards
22k장의 명함 이미지에 대하여 SPADE를 적용하였습니다. 명함은 영수증에 비해 글자들의 배치가 훨씬 자유로운 현태를 가지고 있습니다. 결과는 아래와 같습니다.
Ablation study
비교실험에서, relative coordinate를 제거하거나 이를 absolute coordinate로 교체한 경우 매우 큰 성능 하락이 관찰되었습니다. Data augmentation을 제외한 경우에도 마찬가지로 큰 성능의 하락을 경험하였습니다.
Share article