💬 NLP

Language Generation: Complexity Barriers and Implications for Learning

이 논문은 다양한 형식 언어 클래스에 대해 극한의 상황에서 언어 생성이 이론적으로는 가능하지만, 정규 언어나 문맥 자유 언어와 같이 비교적 단순한 클래스조차도 과도한 샘플 복잡도 요구 사항으로 인해 계산적으로 불가능함을 입증한다.

원저자: Marcelo Arenas, Pablo Barceló, Luis Cofré, Alexander Kozachinskiy

게시일 2026-01-30

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Marcelo Arenas, Pablo Barceló, Luis Cofré, Alexander Kozachinskiy

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

핵심 아이디어: 영원히 "흉내 내는 법"을 배울 수 있을까?

당신이 누군가가 사용하는 비밀 코드를 관찰하며 배우려고 노력 중이라고 상상해 보세요. 당신은 메시지의 흐름(긍정적 예시)을 보고 있으며, 결국에는 본 적 없는 메시지일지라도 실제 메시지와 똑같이 보이도록 자신만의 메시지를 보내는 법을 배우고 싶어 합니다.

컴퓨터 과학의 세계에서, 연구자 클라인버그(Kleinberg)와 멀레이너선(Mullainathan)은 이전에 이론적으로는 이것이 항상 가능하다는 것을 증명했습니다. 충분한 시간과 충분한 예시가 있다면, 아무리 복잡한 언어라도 완벽하게 가짜 데이터를 생성하는 법을 결국 배울 수 있다는 것입니다.

하지만 이 논문은 다른 질문을 던집니다: 이론적으로 가능하다는 것이, 실제로도 가능하다는 뜻일까요? 성공적으로 흉내 내기 시작하기 위해 실제로 얼마나 많은 예시가 필요할까요?

저자들(ArenAS, Barceló, Cofré, Kozachinskiy)은 이렇게 말합니다: "많은 흔한 유형의 언어들에 대해, 그 답은 '셀 수 없이 많거나' 혹은 '계산이 불가능하다'입니다. 이론적으로는 가능하지만, 계산적으로는 불가능합니다."

비유: "비밀 클럽" 게임

이들의 연구 결과를 이해하기 위해, 여러 개의 비밀 클럽이 있는 게임을 상상해 보세요. 각 클럽은 가입 조건(언어)에 대한 특정 규칙을 가지고 있습니다. 당신은 현재 클럽 안에 누가 있는지 관찰함으로써 특정 클방의 규칙을 알아내려는 탐정입니다.

당신의 목표는 규칙을 완벽하게 맞히는 것이 아닙니다. 당신의 목표는 설령 그 특정 사람을 본 적이 없더라도, 클럽이 받아들일 만한 새로운 회원을 만들어내는 것입니다.

이 논문은 당신이 새로운 회원을 성공적으로 생성할 수 있기까지 얼마나 많은 사람을 지켜봐야 하는지 확인하기 위해 네 가지 다른 유형의 클럽을 테스트합니다.

1. "문맥 자유(Context-Free)" 클럽 (복잡한 규칙)

특징: 이들은 중첩되고 복잡한 규칙을 가진 클럽과 같습니다 (예: "'if'가 있으면 반드시 'then'이 있어야 한다"). 이는 컴퓨터 프로그래밍에서 매우 흔합니다.
연구 결과: 저자들은 이러한 일부 클럽의 경우, 당신이 성공할 것이라고 보장할 수 있는 숫자를 적어 내려갈 수 없다는 것을 발견했습니다.
비유: 금고의 비밀번호를 맞히려고 노력하는 상황을 상상해 보세요. 이 논문은 특정 복잡한 클럽의 경우, 새로운 유효한 회원을 추측하기 위해 관찰해야 하는 사람의 수가 너무나 거대해서 어떤 컴퓨터도 그 숫자를 계산할 수 없다는 것을 증명합니다. 이는 마치 "우주에 모래알이 몇 개나 있는가?"라고 묻는 것과 같습니다. 하지만 그 답은 결코 풀릴 수 없는 퍼즐에 따라 계속 변합니다.
결과: 계산 불가능.

2. "정규(Regular)" 클럽 (단순한 규칙)

특징: 이들은 단순하고 반복적인 규칙을 가진 클럽입니다 (예: "빨간 셔츠를 입은 횟수가 짝수여야 한다"). 이들은 기본적인 컴퓨터 로직의 기초가 됩니다.
연구 결과: 여기서도 숫자(데이터의 양)는 존재하지만, 그 숫자는 천문학적으로 큽니다.
비유: 수영장을 물로 채워야 한다고 상상해 보세요. 이 클럽들의 경우, 필요한 예시의 수는 수영장을 물로 채운 다음, 다시 그 수영장을 물로 채우고, 이 과정을 물이 달까지 닿을 때까지 반복하는 것과 같습니다.
결과: 이중 지수적(Double-Exponential). 필요한 예시의 수가 너무 빠르게 증가하여, 작은 규모의 클럽 집단이라 할지라도 우주의 원자 수보다 더 많은 예시가 필요하게 됩니다. 이론적으로는 가능하지만, 실질적으로는 무용지물입니다.

3. "LTT" 클럽 (지역적 규칙)

특ing: 이들은 더 엄격하고 특수한 형태의 "정규" 클럽입니다. 이들은 단어의 즉각적인 주변 환경에만 관심을 가집니다 (예: "'A'가 두 번 연속으로 나올 수 없다").
연구 결과: 이 클럽은 앞선 유형보다 "나은" 클럽이지만, 여전히 문제는 매우 큽니다.
비유: 만약 "정규" 클럽이 달까지 닿는 수영장을 요구했다면, 이 "LTT" 클럽은 에베레스트 산 꼭대기까지 닿는 수영장을 요구하는 것과 같습니다. 엄청난 개선이지만, 단 하루 만에 해내기에는 에베레스트 산은 여전히 너무 높습니다.
결과: 단일 지수적(Single-Exponential). 여전히 너무 커서 실질적이지 않습니다.

4. "패턴(Pattern)" 클럽 (형태가 변하는 규칙)

특징: 이들은 변수(예: "X")를 사용하며, 이 변수는 반드시 비어 있지 않은 단어로 대체되어야 합니다. 이들은 보통 규칙을 식별(추측)하기 쉽다는 점에서 학습 이론에서 유명합니다.
연구 결과: 이들은 식별하기는 쉽다고 알려져 있지만, 생성하기는 어렵습니다.
비유: 클럽의 규칙이 "단어는 회문(palindrome) 형태여야 한다"인 상황을 상상해 보세요. 패턴을 찾아내기는 쉽지만, 이 논문은 새로운 유효한 회원을 생성하기 위해 지수적인 수의 사람들을 먼저 관찰해야 할 수도 있음을 보여줍니다.
결과: 지수적(Exponential). 여전히 실행하기에는 너무 많습니다.

핵심 결론

이 논문은 **존재(Existence)**와 실행 가능성(Feasibility) 사이에 날카로운 선을 긋습니다.

존재: "그렇다, 만약 당신이 영원히 기다리고 무한한 예시를 본다면, 당신은 결국 언어를 생성하는 법을 배울 수 있다." (이는 이미 알려진 사실입니다).
실행 가능성: "아니오, 왜냐하면 거기에 도달하기 위해 필요한 예시의 수가 너무 방대하여 당신은 결코 그 지점에 도달할 수 없기 때문이다."

"간극(The Gap)":
저자들은 많은 표준적인 유형의 언어들(프로그래밍이나 기본 로직에 사용되는 언어들처럼)에 대해, "샘플 복잡도"(필요한 예시의 수)가 장벽이 된다는 것을 보여줍니다. 이는 문을 여는 열쇠를 가지고 있지만, 그 열쇠를 만드는 데만 10억 년이 걸리는 재료로 만들어진 것과 같습니다.

이 논문이 중요한 이유 (논문에 따르면)

이 논문은 거대 언어 모델(LLM)이 언어를 쉽게 배우는 것처럼 보이지만, 어쩌 데는 운이 좋은 것일 수도 있다고 시사합니다. 이 모델들은 이러한 "불가능한" 교차점이 자주 발생하지 않거나, 혹은 저자들이 테스트한 최악의 시나리오보다 "비밀 클럽"의 규칙이 더 단순한 언어 구조를 다루고 있는 것일 수 있습니다.

하지만 논문은 우리에게 경고합니다: 컴퓨터가 텍스트를 생성할 수 있다고 해서, 그것이 밑바닥에 깔린 규칙을 계산적으로 효율적인 방식으로 "학습"했다는 의미는 아닙니다. 많은 이론적 언어 클래스에 있어, "가능함"과 "실제적임" 사이의 간극은 메울 수 없을 만큼 넓습니다.

요약하자면: 언어를 흉내 내는 법은 언젠가 반드시 배울 수 있지만, 많은 유형의 언어에 있어서 그 비용(데이터의 양)이 너무 높기 때문에 사실상 불가능한 것과 다름없습니다.

기술 요약: 한계에서의 언어 생성: 복잡성 장벽과 학습에 대한 시사점

문제 정의
본 논문은 Kleinberg와 Mullainathan(2024)이 도입한 개념인 "한계에서의 언어 생성(language generation in the limit)"의 계산적 타당성을 조사한다. 임의의 가산 언어족(countable family of languages)은 계산 가능성 수준에서 생성 가능하다(즉, 생성기가 무한한 양의 예시를 받으면 결국 타겟 언어와 구별할 수 없는 문자열을 생성할 수 있음)는 것은 이미 확립되어 있으나, 이러한 존재론적 결과는 타당성(feasibility) 문제를 다루지 않는다. 핵심 문제는 균등 생성(uniform generation)을 위해 필요한 표본 복잡도(sample complexity), 즉 유한한 언어족 전체에 걸쳐 타겟 언어로부터 새로운 문자열을 신뢰성 있게 생성하기 위해 얼마나 많은 예시가 필요한지를 결정하는 것이다. 저자들은 구조적으로 단순하거나 학습 가능하다고 알려진 정형 언어의 정준 클래스들에 대해 심각한 타당성 장벽이 존재하는지 확인하고자 한다.

방법론 및 프레임워크
저자들은 유한한 언어족에 대한 균등 생성의 표본 복잡도를 분석한다. 이는 "한계에서의 생성"(수렴 시간이 타겟 및 예시의 순서에 따라 임의로 달라질 수 있음) 및 "비균등 생성"(수렴이 타겟에는 의존하지만 순서에는 의존하지 않음)과 구분된다.

핵심 이론적 도구는 $m$ -생성 가능성을 특징짓는 명제 2.3이다. 가족 $\mathcal{F}$ 가 $m$ -생성 가능하지 않은 것은 $\bigcap_{L \in S} L$ 이 유한하고 그 크기가 $m$ 이상인 비어 있지 않은 부분집합 $S \subseteq \mathcal{F}$ 가 존재할 때와 동치이다. 결과적으로, 표본 복잡도는 가족 내 언어들의 최대 유한 교집합 크기에 의해 직접적으로 결정된다. 저자들은 다양한 클래스(문맥 자유, 정규, 국소 임계 테스트 가능, 패턴 언어) 내의 특정 언어 가족들을 구축하여 이 교집합 크기에 대한 하한과 상한을 도출함으로써, 요구되는 표본 복잡도의 범위를 설정한다.

주요 기여 및 결과

문맥 자유 언어 (Context-Free Languages, CFLs):
저자들은 문맥 자유 언어 가족에 대한 표본 복잡도가 **계산 불가능(non-computable)**함을 입증한다. 문맥 자유 문법(CFG) 또는 푸시다운 오토마타(PDA)로 지정된 두 개의 무한 언어로 구성된 가족에 대해서도, $m$ -생성 가능성을 보장하는 경계 $m$ 을 계산할 수 있는 알고리즘은 존재하지 않는다. 이 결과는 정지 문제(Halting Problem)로부터의 환원을 통해 증명되며, 두 무한 CFL의 교집합 크기를 결정하는 것이 결정 불가능함을 보여준다. 이는 결정적 PDA에 대해서도 성립하며, 비결정성보다는 클래스의 구조적 특성에서 기인함을 나타낸다.
정규 언어 (Regular Languages):
유한한 정규 언어 가족(DFA, NFA 또는 정규 표현식으로 지정됨)의 경우, 문제는 계산 가능해지지만 **이중 지수(double-exponential)**의 표본 복잡도를 수반한다.

상한: 해당 가족은 $a^{s|\mathcal{F}|}$ -생성 가능하다 (여기서 $s$ 는 오토마타의 상태 수, $|\mathcal{F}|$ 는 가족의 크기이다).
하한: 저자들은 요구되는 표본 크기가 적어도 $2^{\Omega(s)}$ 인 이진 정규 언어 가족을 구축한다. 이는 이중 지수 장벽이 표현 방식(오토마ata 또는 표현식)과 관계없이 정규 언어 클래스 자체에 내재된 것임을 입증한다.

국소 임계 테스트 가능 (Locally Threshold Testable, LTT) 언어:
LTT 언어는 부분 문자열에 대한 국소적 계수 조건에 의해 정의되는 정규 언어의 견고한 하위 클래스이다. 가족을 LTT 언어로 제한하면 복잡도가 이중 지수에서 **단일 지수(single-exponential)**로 감소한다.

상한: 표본 복잡도는 $a^{3s|\mathcal{F}|((s|\mathcal{F}|)^2+1)^2}$ 에 의해 제한된다.
하한: 저자들은 알파벳 크기가 $n$ 인 두 개의 LTT 언어 가족에 대해 $2^n$ 의 하한을 증명한다.
이는 일반적인 정규 언어에 비해 엄격한 개선이지만, 저자들은 단일 지수 복잡도 역시 실용적인 목적을 위해서는 여전히 계산적으로 불가능하다는 점을 언급한다.

비삭제 패턴 언어 (Non-Erasing Pattern Languages):
비어 있지 않은 변수 치환을 가진 패턴에 의해 생성되는 이 언어들은 Gold의 모델 하에서 한계 내 식별(identification in the limit)이 가능한 것으로 알려져 있다. 그러나 저자들은 이들이 생성에 있어 지수적 하한에 직면함을 보여준다. 저자들은 교집합 크기가 $2^n$ 인 두 개의 패턴을 가진 가족을 구축하여, 균등 생성을 위해 $2^n$ 개의 예시가 필요함을 입증한다. 이는 식별에 유리한 속성이 반드시 실행 가능한 생성으로 이어지지는 않는다는 점을 강조한다.

의의 및 시사점
본 논문은 이론적인 언어 생성의 가능성과 그것의 계산적 타당성 사이에 명확하고 근본적인 간극이 존재함을 확립한다. 저자들은 생성이 원칙적으로는 항상 가능하지만, 정준 언어 클래스(정규 및 문맥 자유 포함)에 대한 표본 복잡도는 매우 높거나 심지어 계산 불가능하다고 주장한다.

이러한 결과는 실제 환경(예: 거대 언어 모델)에서의 생성 가능성이 실제 마주치는 언어 가족의 특정 구조적 특성에 달려 있을 가능성이 높음을 시사한다. 만약 기저 언어 구조들의 교집합이 작다면 효율적인 생성이 가능할 것이나, 일반적인 정형 언어 클래스의 경우, "자극의 빈곤(poverty of the stimulus)"이 주요 장벽이 아니라, 유한 교집합의 조합 폭발이 극복할 수 없는 표본 복잡도 장벽을 만들어낸다는 것이다. 이 연구는 언어 생성을 언어의 비공집합성 및 교집합 크기 결정의 복잡도와 같은 고전적인 정형 언어 이론 문제와 연결하며, 일반화의 복잡성을 바라보는 새로운 관점을 제공한다.