문법 귀납(grammar induction)은 관찰된 문자열이나 문장의 집합으로부터 형식 문법(예: 문맥 자유 문법 또는 확률적 문맥 자유 문법)을 자동으로 추론하는 작업이다. 그 목표는 언어의 기저에 있는 통사적 규칙성을 포착하여 시스템이 새로운 유효한 문장을 생성하거나 보지 못한 문장을 구문 분석할 수 있게 하는 것이다. 이 문제는 기계 학습, 인공 지능, 그리고 전산 언어학의 교차점에 있으며, 컴퓨터 과학의 초기부터 연구되어 왔다. 명시적 레이블이 있는 지도 학습과 달리, 문법 귀납은 종종 주석이 없는 텍스트를 대상으로 작동하므로 비지도 학습 또는 약한 지도 학습의 한 형태이다.
이 분야는 이론 컴퓨터 과학과 인지 과학 모두에 깊은 뿌리를 두고 있다. 고전적인 Gold의 정리(1967)는 특정 문법 클래스가 극한에서 긍정적인 예만으로는 학습될 수 없음을 보여주었으며, 이는 추가적인 제약이나 확률적 프레임워크의 사용을 촉진하였다. 이후의 연구, 예를 들어 Inside-Outside 알고리즘(확률적 문맥 자유 문법에 대한 forward-backward 알고리즘의 일반화)의 개발은 모수 추정을 위한 실용적인 방법을 제공하였다. 현대적 접근법은 종종 신경망 아키텍처, 특히 트랜스포머 기반 모델을 활용하여 대규모 말뭉치에서 문법과 유사한 구조를 유도한다.
역사적 기초
문법 귀납에 대한 형식적 연구는 1950년대와 1960년대에 Noam Chomsky와 다른 학자들의 형식 언어 이론 연구와 함께 시작되었다. Chomsky의 위계는 정규 문법에서 재귀 열거 문법까지 생성력에 따라 문법을 분류하였다. 1967년, E. Mark Gold는 문맥 자유 문법이 긍정적인 예만으로는 학습될 수 없음을 증명하였고, 이 결과는 이후 연구의 방향을 형성하였다. 이는 긍정적 및 부정적 예 모두에서 학습하는 탐구와, 데이터가 주어졌을 때 가장 가능성 있는 문법을 찾는 것을 목표로 하는 확률적 문법의 사용으로 이어졌다.
1980년대와 1990년대에는 CYK 파서와 Inside-Outside 알고리즘과 같은 알고리즘의 도입으로 전산 방법이 발전하였다. 이는 확률적 문맥 자유 문법에서 효율적인 구문 분석과 모수 추정을 가능하게 하였다. Dana Angluin과 같은 연구자들은 학습자가 문자열의 소속 여부에 대해 오라클에 질의할 수 있는 능동 학습 프레임워크를 개발하여 Gold의 한계 중 일부를 우회하였다. 이 분야는 또한 인지 과학, 특히 인간 유아가 제한된 입력에서 언어를 획득하는 방법에 대한 질문에서 영감을 얻었으며, 이 주제는 브렌던 레이크와 조슈아 테넨바움과 같은 연구자들이 인간과 유사한 학습의 맥락에서 탐구하였다.
확률적 및 베이지안 접근법
문법 귀납의 주요 전환점은 확률적 및 베이지안 방법의 채택과 함께 이루어졌다. 단일 문법을 검색하는 대신, 이러한 접근법은 가능한 문법에 대한 분포를 유지하고 더 많은 데이터가 관찰됨에 따라 이를 업데이트한다. 1979년 James Baker가 도입한 Inside-Outside 알고리즘은 핵심 예로, 확률적 문맥 자유 문법의 모수를 추정하기 위한 기대-최대화(EM) 절차를 제공한다. 이 알고리즘은 은닉 마르코프 모델에서 사용되는 forward-backward 알고리즘과 유사하다.
Mark Johnson과 다른 연구자들이 개발한 베이지안 접근법은 문법 구조에 대한 사전 분포를 통합하여 더 간결하고 일반화 가능한 문법을 유도할 수 있게 한다. 이러한 방법은 종종 마르코프 체인 몬테카를로(MCMC) 샘플링을 사용하여 문법 공간을 탐색한다. 주목할 만한 예로는 자연어에 대한 베이지안 문법 귀납 연구가 있으며, 이는 소규모 말뭉치에 적용되어 인간 문법의 통사적 범주와 유사한 범주를 복구하는 것으로 나타났다. 이러한 기법은 또한 언어 습득에 대한 가설을 테스트하기 위한 인지 모델링에도 사용되었다.
신경망 및 딥러닝 방법
딥러닝의 부상과 함께, 문법 귀납은 신경망 아키텍처를 사용하여 재검토되었다. 초기 신경망 접근법은 순차 데이터를 모델링하기 위해 순환 신경망(RNN)과 장단기 메모리(LSTM) 네트워크를 사용했지만, 이들은 명시적으로 문법을 유도하지는 않았다. 최근에는 대규모 언어 모델에서 사용되는 트랜스포머 기반 모델이 암묵적으로 통사 구조를 포착하는 것으로 나타났다. 예를 들어, 프로빙 연구는 이러한 모델이 명시적인 문법 지도 없이 훈련되었음에도 불구하고 내부 표현에 계층적 및 문법적 정보를 인코딩한다는 것을 입증하였다.
명시적 신경 문법 귀납 모델도 개발되었다. 2019년 Yikang Shen과 동료들이 도입한 ON-LSTM(Ordered Neurons LSTM)은 잠재 트리 구조를 유도하기 위해 특수 게이팅 메커니즘을 사용한다. Andrew Drozdov와 다른 연구자들이 제안한 DIORA(Dynamically-Inferred Ontology for Recursive Annotation) 모델은 내부-외부 알고리즘의 미분 가능한 버전을 사용하여 구성소 트리를 유도한다. 이러한 모델은 원시 텍스트로 훈련되며 인간이 주석을 단 트리뱅크와 상당히 잘 일치하는 구문 분석 트리를 생성할 수 있어, 비지도 구문 분석 벤치마크에서 최첨단 결과를 달성한다.
응용 및 과제
문법 귀납은 여러 영역에서 실용적인 응용을 가지고 있다. 자연어 처리에서 유도된 문법은 비지도 구문 분석에 사용될 수 있으며, 이는 주석이 달린 트리뱅크가 없는 저자원 언어에 유용하다. 기계 학습에서 문법 귀납은 구조적 귀납 편향을 제공하여 모델의 샘플 효율성을 향상시킬 수 있다. 인지 과학에서는 언어 습득을 이해하기 위한 계산적 프레임워크를 제공한다. 또한, 문법 귀납은 생물정보학(예: RNA 2차 구조 예측) 및 프로그램 합성과 같은 다른 영역에도 적용되었으며, 여기서 기저 구조는 문법적이다.
진전에도 불구하고, 문법 귀납은 여전히 어려운 문제로 남아 있다. 가능한 문법의 검색 공간은 방대하고, 목적 함수는 종종 비볼록하여 지역 최적해에 빠질 수 있다. 평가도 어렵다. 주어진 언어에 대해 단일한 올바른 문법이 없기 때문이다. 서로 다른 문법이 동등하게 유효할 수 있다. 이 분야는 계속 진화하고 있으며, 최근 연구는 문법 귀납을 대규모 언어 모델과 통합하여 해석 가능성과 구성적 일반화를 개선하는 방향을 탐구하고 있다. MIT CSAIL 및 스탠포드 AI 연구소와 같은 기관의 연구자들은 이러한 방향을 적극적으로 조사하며, 언어에 대한 기호적 접근과 연결주의적 접근 사이의 격차를 메우는 것을 목표로 하고 있다.