💬 NLP

Compiling Rewrite Rules to Finite-State Transducers with the Worsening Trick

이 논문은 모든 합법적인 재작성 후보를 생성하고 하위 최적의 후보들을 필터링하는 "worsening trick"에 기반하여, 기존 방식들과의 정확한 동등성을 유지하면서도 PyFoma 도구 내에서 복잡한 재작성 규칙의 구현을 단순화하는 유한 상태 트랜스듀서용 컴팩트하고 균일한 컴파일 방식을 소개한다.

원저자: Mans Hulden, Michael Ginn

게시일 2026-06-10

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Mans Hulden, Michael Ginn

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

개요: "악화시키기(Worsening)" 필터로 텍스트 수정하기

당신이 책의 오타를 고치려는 엄격한 편집자라고 상상해 보세요. 당신에게는 이런 규칙이 있습니다. "만약 a 두 개 사이에 글자 b가 보이면, 그것을 p로 바꿔라."

컴퓨터의 세계(구체적으로 언어학 분야)에서는 이것을 **재작성 규칙(rewrite rule)**이라고 부릅니다. 문제는 컴퓨터는 매우 문자 그대로 동작한다는 점입니다. 만약 abababa와 같은 긴 문자열이 있다면, 컴퓨터는 혼란에 빠집니다:

첫 번째 b를 바꿔야 할까요?
두 번째 b를 바꿔야 할까요?
둘 다 바꿔야 할까요?
만약 하나를 바꾸는 것이 또 다른 변화가 필요한 새로운 패턴을 만들어낸다면 어떻게 될까요?

저자인 맨스 훌덴(Mans Hulden)과 마이클 긴(Michael Ginn)은 컴퓨터가 루프에 빠지거나 최선의 해결책을 놓치지 않고 이러한 규칙을 적용하는 법을 가르치는 더 단순한 방법을 제시합니다. 그들은 이 방법을 **"악화시키기 기법(Worsening Trick)"**이라고 부릅니다.

기존 방식: "마커(Marker)" 미로

이전에는 컴퓨터 과학자들이 복잡한 미로를 구축하여 이 문제를 해결하려 했습니다. 그들은 텍스트 안에 보이지 않는 "마커"(마치 작은 깃발 같은 것)를 삽입하여, "이곳이 변경 대상 후보입니다"라고 표시했습니다. 그런 다음 그 깃발들이 올바른 위치에 있는지 확인하고, 변경을 수행한 뒤, 다시 깃발을 제거하는 거대한 기계를 만들었습니다.

저자들은 이 기존 방식이 마치 모든 벽돌을 일단 서로 다른 색으로 칠하고, 색을 확인한 다음, 다시 그 페인트를 전부 샌딩(사포질)해서 벗겨내는 방식으로 집을 짓는 것과 같다고 말합니다. 작동은 하지만, 지저도하고 복잡하며 업데이트하기 어렵습니다.

새로운 방식: "악화시키기" 필터

저자들은 훨씬 더 깔끔한 3단계 프로세스를 제안합니다. 이것을 심사위원이 매우 엄격한 **"오디션 프로그램"**이라고 생각해 보세요.

1단계: 모든 가능성 생성 (오픈 마이크)

먼저, 컴퓨터는 텍스트가 변할 수 있는 모든 가능한 방식을 생성합니다. 아직 규칙은 신경 쓰지 않습니다.

비유: 사람들이 가득 찬 방을 상상해 보세요. 모두가 "나는 이 단어를 바꿔야 한다고 생각한다"라고 적힌 표지판을 들고 있습니다. 어떤 사람들은 첫 번째 단어에 대한 표지판을, 어떤 사람들은 두 번째 단어에 대한 것을, 또 어떤 사람들은 둘 다에 대한 표지판을 들고 있습니다. 모든 가능한 변화의 조합이 존재하는 혼란스러운 방입니다.

2단계: 문맥 확인 (장소 규칙)

다음으로, 컴퓨터는 그 변화들이 실제로 규칙(문맥)에 의해 허용되는지 확인합니다.

비유: 공연장 매니저가 들어와서 말합니다. "단어는 반드시 두 개의 'a' 사이에 있을 때만 바꿀 수 있습니다." 'a' 사이에 있지 않은 단어에 대해 표지판을 들고 있는 사람들은 퇴장 조치됩니다.
이제 방에는 합법적인 변화 아이디어를 가진 사람들만 남았습니다. 하지만 여로 사람이 남아있을 수도 있습니다. 예를 들어, 한 명은 첫 번째 단어만 바꾸고 싶어 하고, 다른 한 명은 둘 다 바꾸고 싶어 할 수도 있습니다.

3단계: "악화시키기" 기법 (엄격한 심사위원)

이것이 이 논문의 핵심 비법입니다. 컴퓨터는 다음과 같이 질문합니다: "이 변화 아이디어를 더 '나쁘게(worse)' 만들 방법이 있는가?"

논리: 만약 어떤 후보가 아무것도 바꾸지 않는다면, (규칙이 반드시 바꿔야 한다고 명시했을 경우) 그것은 무언가를 바꾸는 후보보다 "더 나쁜(worse)" 상태입니다. 만약 어떤 후보가 첫 번째 단어만 바꾸려고 하는데, 사실 첫 번째와 두 번째 단어를 모두 바꿀 수도 있었다면, "첫 번째만 바꾸는" 후보는 "더 나쁜(worse)" 후보입니다.
기법: 컴퓨터는 "좋은" 후보를 가져와서 변화를 제거함으로써 "나쁜" 후보로 만드는 특별한 필터("악화시키는 도구")를 구축합니다.
- 비비유: 엄격한 심사위원이 마법의 지우개를 가지고 있다고 상상해 보세요. 만약 방 안의 어떤 사람이 변화를 나타내는 표지판을 들고 있다면, 심사위원은 그 표인(표지판)을 지우려고 시도합니다.
- 만약 심사위원이 표지판을 지웠음에도 불구하고 그 사람이 여전히 유효한 후보로 보인다면, 원래의 사람은 "차선의(suboptimal)" 상태였던 것입니다(즉, 변화를 놓친 것입니다). 그들은 탈락합니다.
- 끝까지 남는 사람들은 더 이상 악화될 수 없는(cannot be made worse) 사람들입니다. 이들이 바로 해야 할 모든 것을 가장 최선의 방식으로 바꾼 사람들입니다.

이것이 왜 중요한가

간결함: 저자들이 사용하는 수학 공식은 기존의 "마커" 방식보다 훨씬 짧고 깔끔합니다. 이는 20개의 혼란스러운 문단 대신 3개의 명확한 단계로 된 레시피를 쓰는 것과 같습니다.
유연성: 이 동일한 "악화시키기 기법"은 다음과 같은 모든 종류의 복잡한 규칙에 적용됩니다:
- 다중 규칙: b를 p로 바꾸는 동시에 d를 t로 바꾸는 것.
- 선호도: "가장 먼저 보이는 것을 바꾼다"(Leftmost) 또는 "가장 긴 구간을 바꾼다"(Longest).
- 가중치: 어떤 변화가 더 많은 "에너지"를 소모한다면, 이 방식은 이를 처리할 수 있습니다.
검증됨: 저자들은 이 새로운 방법을 기존의 확립된 방식(foma)과 비교 테스트했습니다. 결과는 동일했습니다. 컴퓨터는 내부적인 숫자 체계만 다를 뿐, 정확히 같은 출력을 만들어냈습니다.

"확산(Spreading)"의 놀라운 점

이 논문은 또한 "확산" 규칙(예: 단어 속의 모음이 접미사의 모음에 영향을 주는 방식)에 관한 흥미로운 부수 효과를 언급합니다.

보통 규칙은 입력값(당신이 입력한 것)을 확인합니다.
하지만 때로는 출력값(방금 당신이 만들어낸 것)을 확인해야 할 때가 있습니다.
저자들은 단순히 단계의 순서를 바꿈으로써, "악화시키기 기법"이 이러한 "확산" 동작을 자연스럽게 처리할 수 있음을 보여줍니다. 이는 핀란드어의 모음 조화와 같은 현상에 매우 유용합니다.

요요약

이 논문은 컴퓨터에게 텍스트를 편집하는 법을 가르치는 새롭고 우아한 방법을 소개합니다. 복잡한 마커 미로를 만드는 대신, 모든 가능성을 생성하고, 불법적인 것들을 걸러낸 다음, "악화시키기 기법"을 사용하여 최선이 아닌 옵션을 제거합니다. 이는 언어학자들이 수십 년 동안 직면해 온 문제들을 해결하는 더 단순하고 강력한 방법입니다.

기술 요약: 악화 기법(Worsening Trick)을 이용한 유한 상태 변환기(FST)로의 재작성 규칙 컴파일

문제 정의
유한 상태 변환기(FST)는 계산 언어학, 특히 음운론 및 형태론적 규칙인 $A \to B / L \_ R$ 형태의 문자 재작성을 모델링하는 데 필수적이다. 여기서 정규 언어 $A$ 로부터의 문자열은 정규 언어 $L$ 과 $R$ 이라는 문맥 내에서 $B$ 로 교체된다. 이러한 일반적인 규칙을 FST로 컴파일하는 것은 중첩된 매치, 다중 문맥, 그리고 다양한 선호도(예: 가장 왼쪽, 가장 긴, 또는 가장 짧은 매치)를 처리해야 하기 때문에 계산적으로 복잡하다. Kaplan과 Kay 또는 Karttunen의 방식과 같은 전통적인 컴파일 방법은 재작성 위치를 제한하기 위해 보조 표식(auxiliary markers)을 포함하는 복잡한 합성(composition)에 의존한다. 이러한 접근 방식은 복잡하고 비균질적인 공식을 초래하며, 병렬 재작성, 임의의 변환, 또는 가중치가 부여된 규칙과 같은 고급 기능으로 확장하기 어렵다.

방법론
저자들은 이전에 정규 집합 및 변환에 적용되었던 "악화 기법(worsening trick)"에 기반한 컴파일 체계를 제안한다. 이 방법은 규칙 $A \to B / L \_ R$ 을 컴파일하기 위해 세 가지 투명한 단계로 작동한다:

후보 생성 ( $T_{base}$ ): 시스템은 브래킷(bracket)을 통해 잠재적인 변환 위치를 지정함으로써 가능한 모든 재작성 후보를 생성한다. 이는 입력 알파벳 $\Sigma$ 의 기호들이 변경 없이 통과하거나, 변환 $A:B$ 를 나타내는 브래킷 $< \dots >$ 내에서 $B$ 의 문자열로 교체되도록 하는 기본 변환기를 구축함으로써 달성된다. 경계 문맥을 균일하게 처리하기 위해 단어 경계는 #로 명시적으로 표시된다.
문맥 제한 ( $L_{context}$ ): 부적절한 문맥에 포함된 후보들은 필터링되어 제거된다. 여러 문맥을 처리하기 위한 지수적 공식을 사용하는 대신, 저자들은 "점 찍힌 위치(dotted-position)" 기술(Yli-Järä 및 Koskenniemi)을 사용한다. 보조 기호 ·가 단일 재작성 위치를 표시하며, 이 표시된 위치가 유효한 문맥( $L$ 및 $R$ )에 의해 둘러싸인 문자열을 나타내는 언어 $K$ 가 구축된다. 유효한 문맥과 후보 집합의 교집합은 합법적이고 선택적인 재작성 집합을 산출한다.
선호도 필터링 (악화): 의무적 재작성을 강제하고 특정 선호도(예: 가장 왼쪽, 가장 긴, 또는 가장 짧은)를 구현하기 위해, 시스템은 "악화" 변환기( $W$ )를 정의한다. 이 변환기는 "더 나은" 후보를 브래킷을 제거하거나 이동시킴으로써(예: 재작성을 되돌리거나 범위를 단축함) "더 나쁜" 것으로 매핑한다. 최종 변환기는 $W$ 를 적용했을 때 엄격하게 더 나빠질 수 있는 후보를 필터링함으로써 구축된다. 수학적으로, 후보 집합 $C$ 와 악화기 $W$ 에 대하여, 최적의 집합은 $C \cap \neg \text{range}(C \circ W)$ 이다.

이 프레임워크는 PyFoma에 구현되어 있으며 다음을 지원한다:

다중 문맥: 점 찍힌 위치 언어에서의 합집합(union)을 통해 처리된다.
방향성 재작성: 가장 왼쪽, 가장 긴, 또는 가장 짧은 것과 같은 선호도는 특정 악화 변환기( $W_{left}, W_{long}, W_{short}$ )에 의해 인코딩된다.
임의의 변환: 입력 $T$ 는 단순한 곱집합일 필요가 없으며, 임의의 FST가 될 수 있다.
병렬 재작성: 여러 규칙은 인덱스된 브래킷을 사용하여 처리되며, 문맥 제한과 악화 과정은 인덱스당 적용된다.
가중치: 구성은 열대 반군(tropical semiring) 내에서 작동하며, 악화기는 할당된 가중치를 변경하지 않고 후보를 필터링한다.
엡실론(Epsilon) 처리: 특정 필터는 연속된 빈 브래킷 쌍을 방지하여, 경계당 단일 위치로 엡실론 삽입을 제한한다.

주요 기여

균일성 및 간결성: 논문은 고전적인 마커 중심 또는 멀티테이프 방식에 비해 훨씬 짧고 균일한 공식으로 표현되는 컴파일 로직을 제시한다.
확장성: 이 구성은 새로운 규칙 유형이나 보조 장치 없이도 복잡한 양상(병렬 규칙, 가중치, 마크업, 출력 측 문맥 확인)으로 자연스럽게 확장된다.
구현 및 검증: 저자들은 이 컴파일러를 PyFoma에 구현하였다. 검증은 31개의 문법(427개 규칙)과 2,217개의 사례로 구성된 자동 회귀 테스트 세트를 사용하여 기존의 C 기반 foma 컴파일러와 비교 수행되었다.
동등성: 의미가 일치하는 모든 테스트 케이스에서, 결과 변환기는 (상태 번호만 다를 뿐) foma가 생성하는 것과 구조적으로 동일함을 확인하였으며, 이는 악화 기반 접근 방식의 정확성을 입증한다.

의의 및 주장
본 논문은 악화 기법이 유한 상태 음운론의 절차적 선택 과업에 대한 견고한 대수적 대안을 제공한다고 주장한다. 정규 집합의 후보를 생성하고 악화 관계를 통해 이를 필터링함으로써, 복잡한 선호 순서를 정규 계산 내에서 선언적으로 인코딩할 수 있다. 저자들은 이 접근 방식이 고전적인 컴파일러의 의미론을 재현할 뿐만 아니라, 재작성 시스템의 이론적 및 실용적 확장을 단순화한다고 단언한다. 이 기술은 단순히 컴파일 도구를 넘어, 선호되는 정규 언어 및 관계의 부분 집합(예: 최소 또는 최대 대표값)을 추출하기 위한 일반적인 유한 상태 설계 패턴으로서의 효용을 보여준다. 본 연구는 악화 기법을 유한 상태 최적성 이론(Optimality Theory)의 이전 응용 범위를 넘어, 고전적 재작성 규칙의 전체 스펙트럼을 처리하는 데 있어 그 유효성을 입증하며, 악화 기법이 가진 가치를 강화한다.