[종만북] 문제: OCR

문제

문제 링크

---

알고리즘 구상

Dynamic Programming

이 문제는 어떤 문장을 단어별로 인식한 결과가 주어졌을 때, 원본일 조건부 확률이 가장 높은 문장을 찾아내는 프로그램을 작성하는 프로그램입니다.

Dynamic Programming을 이용해서 이를 풀 것입니다.

알아둘 것

문장 R이 주어질 때 조건부 확률 $P(Q|R)$을 최대화하는 원문 Q를 찾으려고 합니다.

베이즈 정리에 의해, $P(Q|R)$은 다음과 같습니다.

$P(Q|R) = \frac{P(R|Q)\cdot P(Q)}{P(R)}$

$P(R)$ 은 모든 Q에 대해 같으므로, $P(R|Q)\cdot P(Q)$ 를 최대화 하면 되는 것을 알 수 있습니다.

$P(R|Q)$ 는 원문이 Q일때 분류기가 R을 반환할 확률입니다. $P(R|Q) = \prod_{i=0}^{n-1} M(Q[i], R[i])$

$P(Q)$ 는 원문이 출현할 확률입니다. $P(Q) = First(Q[0])\cdot \prod_{i=1}^{n-1} T(Q[i-1], Q[i])$

여기서 가상의 시작 단어 $Q[-1]$를 만들어서, 다음과 같이 단순하게 표현할 수 있습니다. $P(Q) = \prod_{i=0}^{n-1} T(Q[i-1], Q[i])$

최종적으로 $f(Q) = P(R|Q)\cdot P(Q)$를 최대화하면 됩니다.

Problem과 Subproblem 정의

$Problem:$ $f(Q)$가 제일 높은 원문 $Q$를 찾는 것입니다.

문장 $R[1…i]$까지 의 가장 높은 확률을 구하는 것을 $Subproblem$으로 정의할 수 있습니다.

$Subproblem: \prod_{k=0}^{i-1} T(Q[k-1], Q[k])\cdot M(Q[k], R[k])$

---

알고리즘 구현

앞서 Subproblem을 정의해봤습니다. 이를 함수로 구현해봅시다.

double DP[101][502];
double function(int steps, int prev) {
    if (steps == R) return 1.0;

    double &ret = DP[steps][prev];
    if (ret != -1.0) return ret;

    if (steps == 0) {
        ret = first[prev] * M[prev][ R_list[0] ] * function(1, prev);
        answer[0][prev] = prev;
    }
    else {
        ret = 0.0;
        for (int i = 0; i < words; i++) {
            double cand = T[prev][i] * M[i][R_list[steps]] * function(steps + 1, i);
            if (ret < cand) {
                ret = cand;
                answer[steps][prev] = i;
            }
        }
    }
    return ret;
}

여기서 집중해야 할 부분은

ret = first[prev] * M[prev][ R_list[0] ] * function(1, prev);

double cand = T[prev][i] * M[i][R_list[steps]] * function(steps + 1, i);

로 점화식을 구현한 것입니다.

최종 코드는 여기에서 확인할 수 있습니다.

---

알고리즘 개선방안

DP와 recursion을 이용한 알고리즘의 작동시간은 300ms가 나왔으나. 반복문과 DP table을 이용해서 100ms까지 끌어 올릴 수 있습니다.

문제에서 String입력을 받는데 각자 index가 주어집니다. 이를 unordered_map을 이용해 구현하였으나.

struct나 array등을 이용하면 더 빠르게 구현 가능합니다.

---

정리

이 문제는 은닉 마르코프 모델(HMM)에 속하는 비터비 알고리즘 입니다.