9.4 문제 : 광학 문자 인식(Python)

문제 출처 : algospot.com :: OCR

algospot.com :: OCR

---

1. 문제 분석

• 이 문제에서 어려운 부분은 입력에 주어진 요구 조건을 수학적으로 풀어 쓰고 정형화 하는 부분이다.
• 또한, 원문이 생성되는 과정이 '8.16 문제 : 두니발 박사의 탈옥'에서 소개된 마르코프 연쇄 모델을 따른다.

 

• 마르코프 연쇄
• 유한개의 상태가 존재한다.
• 매 시간마다 상태가 변경된다.
• 어떤 상태 a에서 다른 상태 b로 옮겨갈 확률은 현재 상태 a에 의해서만 좌우된다.
• a 이전에 어떤 상태에 있었는지, 현재 시간은 얼마인지 등은 영향을 주지 않는다.

(1) 확률 계산하기

• 이 문제의 중점은 분류기로 인식한 문장 R이 주어질 때, 조건부 확률 P(Q | R)을 최대화 하는 원문 Q를 찾는 것이다.
• 조건부 확률인 P(Q | R)를 베이즈 정리에 의해 다음과 같은 식을 얻을 수 있다.

 

• 베이즈 정리 : 베이즈 정리 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

베이즈 정리 - 위키백과, 우리 모두의 백과사전

베이즈 정리를 이용한 조건부 확률 P(QR)의 표현

• 여기서 P(R)은 모든 Q에 대해 같으므로 우변의 분자 부분인 두 확률의 곱 P(R | Q)*P(Q)을 최대화 하는 Q를 찾아야 한다.
• 먼저 P(R | Q)는 원문이 Q일 때, 분류기가 R을 반환할 확률이다.
• 분류기는 각 단어별로 독립적이기 때문에 P(R | Q)를 다음과 같이 표현할 수 있다.

 

• M(a, b) : 단어 a를 b로 분류할 확률

• 이제 원문이 출현할 확률인 P(Q)를 구해야 한다.
• 원문은 마르코프 연쇄에 의해 생성(아마도 원문일 확률은 분류기가 인식한 단어에 의해서만 좌우되기 때문으로 추정)된다고 가정한다.
• 이 때문에, 첫 번째 단어 Q[0]이 문장 처음에 등장할 확률인 B(Q[0])과 두 번째 이후의 단어가 앞 단어 다음에 출현할 조건부 확률 T(Q[i-1], Q[i])를 모두 곱하면 된다.
• 따라서, P(Q)는 다음과 같이 표현이 가능하다.

 

• T(a, b) : 이전 단어가 a일 때, 다음 단어로 b가 나올 확률

• 이 때, 가상의 시작 단어 Q[-1]이 존재한다고 가정하고 항상 이 Q[-1]이 시작단어로 등장한다고 하면, B(Q[0]) = T(Q[-1], Q[0]) 이므로 ∏에 포함하여 다음과 같이 간략화 할 수 있다.(이 가상의 시작 단어는 코드로 구현할 때는 따로 의미가 없다...?)

B(Q[0]) = T(Q[-1], Q[0])라고 가정했을 때의 P(Q)

• 따라서, 맨 처음 최대화 하려고 했던 두 확률의 곱 P(R | Q)*P(Q)은 다음과 같이 표현할 수 있다.

• 이를 최대화하여 P(R)로 나눌 경우 우리가 원하는 P(Q | R)의 값을 얻을 수 있다!
• 하지만, 사실상 P(R)은 사실상 모든 경우에 동일하므로 P(R | Q) * P(Q)에 대한 계산만 해도 되는것 같다.

(2) 동적 계획법 알고리즘

• 원문 Q를 만드는 과정을 n 조각으로 잘라 각 재귀 호출마다 Q에 들어갈 단어 하나를 정한다.
• Q의 단어를 하나 정하고 나면 Q의 나머지 부분은 재귀 호출로 생성할 수 있다.
• 다음 단어가 출현할 확률(T[i, j])이 이전 단어에 의해 결정되기 때문에 재귀 호출 시 이전 단어를 인수로 전달하여야 한다.
• 이를 바탕으로 부분 문제를 정의하면 아래와 같다.

 

• recognize(s, p) : Q[s-1]이 p일 때 Q[s] 부터 적절하게 단어를 채워서 만들 수 있는 P(R | Q) * P(Q)의 최대치

 

• 부분 문제 정의를 토대로 점화식을 만들면 된다.

 

• recognize(s, p) = max( recognize(s+1, t) * T(p, t) * M(t, r) )

• t : Q[s]에 선택될 수 있는 단어들
• r : 분류기가 인식한 단어

---

2. 코드 구현 - 문제 풀이 해설 방법

(1) 문제 입-출력

# 입력의 크기가 크기 때문에 빠른 입력 방식을 위한 sys 패키지 호출 및 입력 방법 변환
import sys
input = sys.stdin.readline

# 확률을 그대로 사용하면 언더플로가 발생할 수 있으므로 로그값을 이용하기 위해 math 패키지 호출
import math

INF = int(1e200) # 무한대 설정

# m : 원문에 출현할 수 있는 단어의 수
# q : 처리해야 할 문장의 수
m, q = map(int, input().split())

# 원문에 출현하는 단어 목록
origin_words = input().split()

# B[i] = i번 단어가 첫 단어로 출현할 확률
B = list(map(float, input().split()))

# T[i][j] = i번 단어의 다음 단어가 j번 단어일 확률(로그값으로 치환)
T = []
for i in range(m):
    T.append(input().split())
    for j in range(m):
        if float(T[i][j]) != 0.0:
            T[i][j] = math.log10(float(T[i][j])) # 로그값으로 치환
        else:
            T[i][j] = -INF

# M[i][j] = i번 단어를 j번 단어로 인식할 확률(로그 값으로 치환)
M = []
for i in range(m):
    M.append(input().split())
    for j in range(m):
        if float(M[i][j]) != 0.0:
            M[i][j] = math.log10(float(M[i][j])) # 로그값으로 치환
        else:
            M[i][j] = -INF

cache = [[1] * 502 for _ in range(102)]
choice = [[None] * 502 for _ in range(102)]

for _ in range(q):
    recognized = input().split()

    n = int(recognized[0])

    recognized_sentence = recognized[1:]
    # 분류기가 반환한 문장 중 단어들을 원문의 단어 번호로 대체하여 저장
    R = []
    for word in recognized_sentence:
        R.append(origin_words.index(word))

    recognize(0, 0)
    print(reconstruct(0, 0))

• 실제 확률을 사용할 경우 값이 너무 작아져 언더플로가 발생할 수 있기 때문에 로그값으로 치환
• 로그값을 사용할 경우 실제로 확률을 곱하는 것이 아닌 확률의 로그를 취한 값들을 더해서 계산이 가능하다.
• 리스트 choice는 원문을 역산하는 과정에서 필요한 저장 공간으로 이전 단어에 영향을 받아 segment째에 등장할 수 있는 가장 확률 높은 단어의 인덱스를 저장한다.

(2) recognize(segment, previousMatch)

# Q[segment] 부터 채워서 얻을 수 있는 최대 g() 곱의 로그 값을 반환
# Q[segment - 1] == previousMatch라고 가정함
def recognize(segment, previousMatch):
    if segment == n:
        return 0
    
    if cache[segment][previousMatch] != 1:
        return cache[segment][previousMatch]
    
    cache[segment][previousMatch] = -INF # log10(0)은 음의 무한대

    # R[segment]에 대응되는 단어 찾기
    for thisMatch in range(m):
        # log로 변환된 확률이기 때문에 곱이 아닌 합 연산을 한다.
        # M[thisMatch][R[segment]]를 M[previousMatch][R[segment]]로 적는 실수함...
        candid = T[previousMatch][thisMatch] + M[thisMatch][R[segment]] + recognize(segment + 1, thisMatch)

        if cache[segment][previousMatch] < candid:
            cache[segment][previousMatch] = candid
            choice[segment][previousMatch] = thisMatch # 역추적을 통해 원문 계산을 위해 별도로 단어의 인덱스를 저장

    return cache[segment][previousMatch]

• 이전 단어에 따라 특정 단어가 등장할 확률의 로그 값 + 현재 단어를 분류기가 인식할 확률의 로그값을 더하고 재귀호출을 통해 다음 단어들에 대해 반복적으로 합산
• 그 값의 최대값을 cache에 저장하여 반환한다.
• 또한 최댓값이 나오는 단어의 인덱스를 원문 단어를 추적하기 위해 별도로 리스트 choice 에 저장한다.

(3) reconstruct(segment, previousMatch)

# 실제 원문 역산으로 구하기
def reconstruct(segment, previousMatch):
    choose = choice[segment][previousMatch]
    result = origin_words[choose]
    if segment < n-1:
        result = result + " " + reconstruct(segment + 1, choose)

    return result

• choice에서 저장된 이전 단어에 따라 출현할 수 있는 segment에 등장할 수 있는 단어의 인덱스를 토대로 차례로 연결하여 반환

---

3. 후기

  이번 문제는 너무한다. 프로그래밍 대회가 아닌 기업 코딩테스트에서 이런 문제를 낼까하는 문제였다. 일단 확률에 대한 개념이 없으면 해결할 수도 없고 확률을 로그값으로 치환하여 문제를 해결하는 것 역시 경험이 없으면 생각할 수 없을 것 같다. 그리고 사실 문제를 몇 번씩 읽긴 했지만 아직도 완벽하게 이해하진 못 했다.... 덕분에 이 글을 읽는 사람들이 있다면 설명이 뭔가 난해하고 많이 빠진 부분이 많아 이해하기 어려울 것 같다는 생각이 든다. 아무래도 코드는 생각보다 안 복잡한데 진행 과정과 cache 및 choice의 저장 방식이 조금 난해해서 참고 자료가 없으면 다시 풀어도 혼자서는 못 풀거 같다...

  아무래도 8장까지는 자신감이 조금 붙어가는 상태였다면 9장 부터는 점점 벽을 느끼고 있다. 그래도 또 행복회로를 돌려서 이 벽만 넘으면 다시 자신감이 생기지 않을까 하는 기대를 해본다ㅠ

---

github : Algorithmic_Problem_Soving_Strategies/q9_4.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies