improve algorithm to find answer's start index and end index properly and effectively

[Ssunbell]

목표

ocr 결과에서 뽑아낸 단어들 중에서 정답 단어 및 index를 뽑아내는 알고리즘이 너무 단순화되어있음.

def subfinder(self, words_list, answer_list):  
        matches = []
        start_indices = []
        end_indices = []
        for idx, i in enumerate(range(len(words_list))):
            #if words_list[i] == answer_list[0] and words_list[i:i+len(answer_list)] == answer_list:
            if len(words_list[i:i+len(answer_list)])==len(answer_list) and all(fuzzy(words_list[i+j],answer_list[j]) for j in range(len(answer_list))):
                matches.append(answer_list)
                start_indices.append(idx)
                end_indices.append(idx + len(answer_list) - 1)
        if matches:
          return matches[0], start_indices[0], end_indices[0] # <- 여기
        else:
          return None, 0, 0

return을 보면 match 되는 단어 후보군 중에서 가장 먼저 뽑힌 후보군을 정답으로 채택하므로 해당 후보가 정확히 정답인지 확인할 수 없음. 따라서 다음을 개선

예를 들어, 정답이 "뉴진스 최고"일 경우 ['뉴진스', '최고']라는 두개의 단어로 분리하고, '뉴진스'와 가장 유사한 단어(리히텐슈타인 거리 < 0.2)들을 리스트안에 담아두고 가장 첫번째로 뽑힌 후보를 선택. 하지만, 가장 첫번째로 뽑힌 단어가 '유진호'이고 두번째로 뽑힌 단어가 '뉴진스'인 경우, 잘못된 후보를 정답으로 선택하므로 이를 개선해야함.

• 정답이 될 수 있는 단어들(후보군)을 뽑는 알고리즘 작성
• 후보군들을 다음과 같은 알고리즘을 통해 최적의 정답을 선택
  1. 정답 단어와 100% 일치하는 후보를 선택
  2. 만약 ocr의 성능으로 인해 100% 일치하는 정답이 없는 경우
  3. 리히텐슈타인 거리가 가장 낮은 단어를 선택
  4. 정답 단어가 띄어쓰기로 되어있는 경우 start_idx 및 end_idx가 멀리 있지 않으므로 해당 start_idx 및 end_idx의 거리가 가장 낮은 값을 선택

[Ssunbell]

해결법 : heapq

최소힙큐를 사용해서 리벤슈타인 거리가 가장 낮은(정확히 일치하는) 정답을 최우선으로 뽑아냄

추가적인 문제

만약, 리벤슈타인 거리가 동일한 경우:

이 이미지에서 질문과 답은 다음과 같음

• question : what is the index for Retention of Franchise?
• answer : (100)

정답 후보군에서 뽑은 정답은 두개가 있음

1. 정답
   • 리벤슈타인 거리 : 0.0
   • 정답 : (100)
   • start_idx : 9
   • end_idx : 9
2. 오답
   • 리벤슈타인 거리 : 0.0
   • 정답 : (100)
   • start_idx : 39
   • end_idx : 39

운이 좋게도 질문이 start_idx, end_idx가 빠른 곳에 있어서 정답이지만, 만약 정답이 뒤에 있었다면 잘못된 정답을 채택

해결법 : question과 words의 공통된 단어의 거리를 동시에 고려

[Ssunbell]

해결법 : 유클리디안 거리

question의 핵심 단어와 answer간의 유클리디안 거리를 이용하여 정답들의 가중치를 설정하여 유클리디안 거리가 가장 낮은 정답을 제대로 된 정답이라고 설정

질문은 다음과 같음

what is the index for Retention of Franchise

여기서 가장 핵심적인 단어는 index, Retention, Franchise임. 따라서 해당되는 단어들을 뽑아냄.

핵심 단어 ngram으로 뽑아내기

핵심 단어만 뽑아낼 경우 Retention of Franchise를 뽑아낼 수 없음. 이를 뽑아내기 위해 ngram을 도입하여 bigram, trigram까지 고려하여 해당되는 단어의 위치 정보(bounding box)를 뽑아냄

유클리디안 거리

정답을 기준으로 정답과 핵심 단어간의 위치 정보를 이용하여 거리를 계산하게 되면, 거리가 짧다는 것은 핵심정보와 정답이 가까이에 위치하고 있다는 것을 의미하므로 질문과 가장 가까운 정답일 가능성이 높아짐. 따라서 유클리디안 거리가 가장 짧은 정답을 제대로된 정답으로 선택

[Ssunbell]

목표

레벤슈타인 거리의 바운더리를 몇으로 설정해야 가장 좋은 성능을 보이는지 하이퍼 파라미터 튜닝

[Ssunbell]

이러한 유클리디안 알고리즘이 적용이 잘되는 이유

DocVQA 데이터셋은 질문하는 사람이 이미 문서 안에 답이 있다는 것을 알고 있기 때문에 질문 구성이 문서 안의 핵심 단어를 포함하고 있는 Bias를 포함하고 있음. 따라서 오히려 이러한 Bias를 이용한 rule base algorithm이 성능을 올릴 수 있음. (즉, 과적합됨)