One-shot Key Information Extraction from Document with Deep Partial Graph Matching

Inc Lomin

Apr 19, 2022

One-shot Key Information Extraction from Document with Deep Partial Graph Matching

Contents

Introduction

Motivation

일반적인 KIE는 그림 2와 같이 text detection, recognition 및 text field labeling의 세 가지 주요 단계로 구성됩니다.
text detection 및 recognition 접근 방식은 문자 인식(OCR) 영역에서 널리 연구되었지만, 원샷 학습 기반의 텍스트 필드 레이블링은 덜 연구되고 있습니다.
문서의 레이아웃은 서로 다른 필드를 구별하는 데 중요한 역할을 합니다. KIE 작업에 텍스트와 시각적 패턴을 모두 활용하기 위해 많은 학습 기반 방법이 제안되었습니다. 그들은 좋은 성능을 보여 주었지만 충분한 훈련 데이터가 필요합니다.
본 연구에서는 인건비를 절감하고 별도의 모델로 문서 유형별 다량의 훈련 데이터 의존도를 완화하기 위해 원샷 학습 방법을 연구합니다.
원샷 방법의 초기 시도는 일반적으로 entity 추출을 위한 template을 기반으로 합니다. 그러나 이러한 rule-based 방법은 특정 레이아웃으로 제한되며 모든 유형의 문서로 확장할 만큼 일반적이지 않습니다. 즉, 기존 방법으로는 drifted fields와 outliers를 처리할 수 없습니다.

Contributions

one-to-(at most)-one mapping constraint과 partial graph matching을 사용하여 원샷 키 정보 추출(KIE)을 위한 deep end-to-end trainable network를 제안합니다. 본 방법은 이전의 많은 방법과 달리 명시적으로 분리된 similarity 학습 및 solving을 end-to-end 프레임워크에서 학습을 가능하게 합니다.
저자가 아는 한, 이는 globally optimized solutions를 생성하는 최초의 KIE 접근 방식입니다.
공간, 텍스트 및 측면 표현의 기능을 융합하기 위해 간단한 context ensemble block을 설계합니다.
KIE의 연구를 촉진하기 위해 하나의 데이터 세트를 구성하고 제안하는 one-shot KIE 모델을 곧 공개할 예정입니다. 이러한 데이터 세트는 다양한 유형의 문서 이미지를 다루며 이들 중 대부분은 spatial drift로 인해 매우 어렵습니다.
수집된 데이터 세트에 대한 state-of-the-art performance를 달성합니다.

Related Work

Keyword Spotting

KWS(KeyWord Spotting) 방식으로는 KIE 작업을 해결할 수 없습니다. KWS는 주어진 텍스트가 이미지에 존재하는지 확인하고 그 위치를 찾습니다. 예를 들어 ID 카드에서 "Tom"을 "이름"으로 식별합니다. 그러나 이름은 ID 카드마다 다를 수 있기 때문에 KWS는 support 문서에서 "Tom"을 찾을 수 없습니다. 따라서 KWS에 대한 방법과 데이터 세트는 모두 KIE에 적합하지 않습니다.

Key Information Extraction

Language model based methods은 일반 텍스트 표현에서 작동합니다. 그러나 문서 레이아웃 정보 또한 information extraction에 중요합니다. 그래서 기존의 많은 학습 기반 방법은 KIE의 성능을 향상시키기 위해 텍스트 및 시각적 임베딩을 모두 사용하는 경향이 있습니다.

이러한 접근 방식은 좋은 결과를 얻을 수 있지만, 각 유형의 문서에 대해 별도의 모델을 훈련해야만 하여 resources를 낭비합니다. 또한 각 문서 범주에 대해 레이블이 지정된 많은 이미지를 수집하고 수동으로 주석을 달아야 하므로 labor-intensive하며 많은 시간이 소요됩니다.

One-shot Learning of KIE

기존의 일회성 접근 방식은 대부분 rule-based이며 서로 가까운 텍스트 필드를 식별하는 데 어려움을 겪고 있습니다. 특히 랜드마크와 corresponding fields 사이에 큰 spatial drift가 관찰되는 경우 KIE 성능이 급격히 떨어졌습니다. 이러한 성능 하락은 기존 모델이 spatial relationship variations에 민감함을 시사합니다. 이 논문은 두 개의 서로 다른 필드가 같은 범주에 매핑되는 경우를 완화할 수 있도록 topology invariant 및 global optimized deep end-to-end trainable structured information extraction framework를 제안합니다.

Graph Matching

Graph matching approaches은 key-points matching과 같은 컴퓨터 비전 작업에서 널리 사용되었습니다.

Hammami et al. 은 색상 정보를 사용하여 행정 및 상업 형태의 정보 영역을 추출하는 subgraph isomorphism-based 방법을 제안했습니다. 그런 다음 information extraction task는 supporting document의 graph representation과 가장 잘 일치하는 쿼리 문서의 subgraph를 검색하도록 변환됩니다. 그러나 많은 문서가 이 방법의 적용을 제한하는 흑백으로 스캔됩니다.

Proposed Method

Notations on Graphs

단일 Document을 로 표현합니다.

Dynamic text regions as Fields
Set of node features

Landmark
text embedding
width and height of its OCR bounding box

Set of label
set of all edges

support 및 query documents에 대해 subscripts를 사용하여 표현합니다.

i th field in a query document , support documents
one-shot KIE problem은 각 query field 의 gt label 을 예측하는 것

본 논문에서는 one-shot KIE problem을 partial graph maching을 기반으로 해결합니다.

만약 query field 가 support field 와 match한다면, 모델은 의 라벨이 가 되도록 예측

Solving one-shot KIE with Partial Graph Matching

본 논문에서 제안하는 partial graph matching은 기존 graph matching problem의 concave quadratic formulation을 사용하여 동일한 개념을 공유하지만 제약 조건이 다릅니다.

permutation matrix 에서 query field 와 가 match한다면 는 1이 되고, unmatch라면 0이 됨

matrix는 와 사이의 matching을 설명하며, 의 elements를 가짐

affinity matrix 는 square matrix이며 의 vector version을 operate

의 shape은
와 가 있을 때, 이에 대한 similarity score는 로 표기 (edge similarity score)
와 에 대한 similarity score는 (vertex similarity score)

따라서 partial graph matching problem는 다음과 같이 constrained optimization problem으로 공식화 될 수 있습니다.

equation (1)

첫 번째 항은 vertex similarity score를 계산하기 위해 support fields와 query fields 간의 가능한 모든 일치를 합산
두 번째 항은 edge similarity score를 계산하기 위해 support edges와 query edges 간의 가능한 모든 일치를 합산

equation (2)

여기서 1은 요소가 모두 1인 열 방향 벡터
첫번째 부등식은 복수의 support fields를 단일 query field와 일치시키는 것을 금지
두번째 부등식은 복수의 query fields를 단일 support field와 일치시키는 것을 금지

와 가 일치한다면, 와 , 와 가 각각 일치

그림 4는 one-to-(at most)-one constraint이 보장될 수 있는 이유와 drifted fields 및 outliers 문제를 해결하는 데 도움이 되는 방법을 보여줍니다.

(a) Samples contain multi-region fields.

a1, a2처럼 multi-line fields를 처리할 때, 동일한 label을 공유하는 support fields의 average boxes를 사용할 경우 one-to-many mapping으로 이어져, one-to-(at most)-one mapping 제약을 위반합니다.
본 논문의 방법에서는 multi-line fields의 label에 숫자 접미사를 추가하여 a3 및 a4와 같이 multi-region fields 간의 one-to-(at most)-one mapping이 가능하게 합니다.
각 fields의 원래 label을 복원하기 위해 예측 후에는 숫자 접미사를 제거합니다.

(a) Samples contain multi-region fields.

drifted fields를 mapping하는 과정에서 b1, b2의 경우 잘못된 mapping이 발생했고 one-to-many mapping 또한 발견되었습니다.
본 논문의 방법에서는 두 fields가 most similar field가 아니더라도 각 support field를 올바른 query field에 매핑되도록 합니다.

④라는 outlier에 대해 기존 방법은 잘못된 support field를 mapping하지만, 본 논문의 방법에서는 이 과정을 거부할 수 있습니다.

Document Graph Construction

Graph Vertices

landmarks (spatial feature)

target 필드의 중심점과 모든landmarks를 연결하는 선분의 shape은
문서에서 단일 spatial features X의 overall shape은

OCR bounding box (aspect feature)

height 및 width를 concatenate하여 2-dimensional feature를 구성, shape은

Average word embedding (textual feature)

300-dimension을 가진 pre-trained word embedding을 사용하고 training 동안에는 freeze
따라서 단일 문서 내에서의 textual features의 shape은

모든 문서에 대해 landmarks와 fields는 OCR 시스템에 의해 자동으로 감지된 다음 수동으로 label이 지정됩니다. 각 문서 유형에 대해 하나의 문서를 support 문서로 선택하고 나머지는 query 문서로 사용합니다. support 문서는 가능한 완전해야 합니다.

query document에 대한 extra landmarks를 제거하고 support document와 비교하여 누락된 landmarks를 복구합니다. 불완전한 OCR 시스템으로 인해 필드가 여러 부분으로 분할되는 경우 이러한 필드를 병합합니다. 이 작업은 훈련 데이터에 대해서만 가능합니다. 모델은 평가 프로세스 동안 추가 필드에 "outliers" 레이블을 할당합니다.

Graph Edges

각 문서에 대해 fields 간에 visible graph를 만든 다음 이 그래프의 minimum spanning tree를 얻기 위해 Prime algorithm을 적용, 모든 loops를 제거합니다. 더 나은 성능을 가져오려면 neighbor fields를 연결하는 더 짧은 edge를 보존해야합니다.

각 edge에는 두가지 유형의 feature가 존재합니다.

direction feature : 두 fields를 연결하는 선분

aspect feature : start field의 높이와 너비를 end field의 높이와 너비로 연결한 4-dimensional feature

Vertex and Edge Affinities

query 및 support fields의 features을 concatenate한 다음 MLP(Multi-layer Perceptron)를 적용하여 이들 사이의 affinity score를 생성합니다.

모든 landmarks를 순회한 이후, 와 사이의 spatial affinity는 모든 landmarks를 기준으로하는 average affinity score와 동일합니다.

유사한 방식으로 별도의 MLP 모듈을 사용하여 aspect, textual affinity matrices를 계산합니다. 그리고 계산된 모든 affinity matrices의 평균은 최종 vertex affinity matrix로 계산됩니다.

의 off-diagonal elements 또한 비슷한 방식으로 계산됩니다. 그리고 vertex와 edge affinities에 대해 각각 다른 MLP modules를 사용합니다.

Combinatorial Solver

그림 3은 모델의 파이프라인을 보여줍니다. affinity matrix을 계산한 후 partial graph matching problem를 해결하고 solver를 통해 back-propagate해야 합니다.

Solving Partial Graph Matching Problem

DD-ILP Solver는 IRPS-LP(Integer-Relaxed PairwiseSeparable Linear Programs)라고 하는 특정 유형의 이산 최적화 문제를 해결하는 것을 목표로 합니다. 공식 (1)과 (2)가 이러한 문제의 예입니다.
ZAC-GM Solver를 재구현합니다.

ZAC-GM Solver는 공식 (1)및 (2)와 동일하지 않지만 입출력 제약 조건은 DD-ILP와 동일합니다.
MLP 모듈을 정규화하기 위해 additional ranking loss을 설계합니다. 이 ranking loss을 사용하여 훈련 중 올바른 vertex 쌍과 잘못된 vertex 쌍 간의 similarity score 차이를 확대합니다.

예측된 와 Label 사이의 hamming loss를 채택합니다.

Experiment

Datasets

Implementation Details

State-Of-The-Art models

LayoutLM, PICK, LF-BP와 비교했습니다. LayoutLM 모델과 PICK 모델은 supervised-learning models이며, LM-BP 모델은 원샷 학습 모델입니다.

Training Details

Pytorch를 사용하여 모델을 구현, 16GB 메모리가 탑재된 단일 NVIDIA Tesla V100 GPU에서 학습

ADAM을 적용, batch size = 8

좋은 성능을 유지하기 위해 supervised-learning-based model은 문서 스타일에 따라 서로 다른 parameters를 유지합니다. 따라서 각 스타일에 대한 별도의 parameters를 훈련하기 위해 각 문서 스타일을 훈련 및 테스트 데이터로 분할합니다.

반대로 one-shot-learning 기반 모델은 동일한 parameters를 사용하여 다양한 스타일의 문서를 처리할 수 있기에, 모든 스타일의 문서을 하나의 모델을 훈련합니다.

Testing Details

one-shot-learning 기반 모델의 경우 각 스타일의 support document를 미리 정의한 다음 동일한 스타일의 서로 다른 이미지를 query 문서로 사용합니다. 각 스타일에 대해 가능한 한 많은 landmarks/fields를 포함하는 문서는 좋은 support 문서 역할을 합니다. 모델은 support 문서에 정의된 레이블을 사용하여 query 문서의 각 field label을 예측합니다.