Learning Infinite Context-Free Grammars via Reduction Bias for Search Space

Abstract

확률 문맥 자유 문법(Probabilistic Context-Free Grammars, PCFGs)은 자연어의 구성 구문 분석을 위해 사용되는 계층적 확률 모델이다. PCFGs를 유도할 때, 기존에는 유한 파싱 트리에 대한 확률 질량의 손실을 방지하기 위해 PCFGs의 일관성(consistency)을 보존하였으나 이는 유한 문법 공간으로의 탐색 공간 편향을 발생시킨다. 이로 인하여 무한 문법 공간에 대한 탐색이 불가능해져 해당 공간에 존재 가능한 광역 최적점에 대한 탐색 기회를 저하한다. 우리는 주어진 문장으로부터 추정되는 유한 파싱 트리의 확률을 유한 파싱 트리의 확률 질량인 파티션 함수로 재정규화한다. 이는 유한 문법 공간으로의 편향을 제거한다. 이를 통해 전체 문법 공간에 대해 탐색 가능한 방법을 제안한다. 우리는 이론적으로 무한 문법 공간 내에 최적점이 존재할 수 있다는 사실을 보이고 이를 실험적으로 증명한다.|Probabilistic Context-Free Grammars (PCFGs) is a hierarchical probabilistic model used for constituency parsing of natural languages. The consistency of grammars has been preserved to avoid loss of probability mass over finite parsing trees when inducing PCFGs. However, Which results in a bias for search space into finite grammar space. This makes the search for infinite grammar space impossible, which reduces the opportunities of searching for the global optimum in that space. We renormalize probabilities of finite parsing trees by partition function, the probability mass of finite parsing trees. It reduces the bias into finite grammar space. By doing so, we propose the method that searches total grammar space. We theoretically show that the global optimum can exist within infinite grammar space and demonstrate experimentally.