PaperlayerView exact revision on arXiv

Source-linked AI summary

Compound Probabilistic Context-Free Grammars for Grammar Induction

Yoon Kim, Chris Dyer, Alexander M. Rush

arXiv:1906.10225v9cs.CLstat.ML

TL;DR

문법 유도는 언어학적으로 의미 있는 계층 구조를 찾는 것을 목표로 하지만, 전통적인 PCFG 학습은 어려웠다. 이 논문은 문장 수준 잠재 변수를 사용하는 compound PCFG를 제안하고, English와 Chinese에서 비지도 구문 분석 성능이 향상됨을 보인다.

  • 문제

    자연어 데이터에서 직접 likelihood 최적화를 사용해 전통적인 PCFG를 유도하기는 어려웠으며, 이는 개선된 grammar induction 방법의 필요성을 제기했다.

  • 방법

    이 모델은 문장 수준 연속 잠재 변수를 사용해 neural PCFG rule probability를 조절하고, collapsed variational inference와 dynamic programming을 통한 latent tree marginalization을 적용한다.

  • 결과

    Compound PCFG는 English와 Chinese 모두에서 비지도 구문 분석 시 평가된 다른 모델을 유의미한 격차로 능가한다.

  • 시사점 및 한계

    Compound PCFG는 더 풍부한 grammar를 학습하고, 비지도 parser로 평가했을 때 성능을 향상한다.

  • 시사점 및 한계

    학습 비용이 NLM 기반 비지도 구문 분석 시스템보다 훨씬 높아, 이 접근법은 확장하기 어려울 수 있다.

Abstract

from arXiv · show

We study a formalization of the grammar induction problem that models sentences as being generated by a compound probabilistic context-free grammar. In contrast to traditional formulations which learn a single stochastic grammar, our grammar's rule probabilities are modulated by a per-sentence continuous latent variable, which induces marginal dependencies beyond the traditional context-free assumptions. Inference in this grammar is performed by collapsed variational inference, in which an amortized variational posterior is placed on the continuous variable, and the latent trees are marginalized out with dynamic programming. Experiments on English and Chinese show the effectiveness of our approach compared to recent state-of-the-art methods when evaluated on unsupervised parsing.

1 서론

이 논문은 log-likelihood 최적화를 통해 neural parameterization이 언어학적으로 의미 있는 grammar를 산출할 수 있고, collapsed variational inference가 효율적인 학습을 가능하게 함을 보이며 grammar induction을 재고한다. English와 Chinese benchmark에서 이 접근법은 최근 neural unsupervised parsing 방법들과 비교해 경쟁력 있는 성능을 보인다.

  • 동기: Grammar induction은 전통적으로 probabilistic grammar를 지정하고 그 parameter를 최적화해야 하지만, 성공적인 방법들은 원하는 구조가 나타나도록 auxiliary objectives, priors, non-parametric models 또는 engineered features를 추가하는 경우가 많다.이러한 추가 요소들은 원하는 구조의 출현을 유도하기 위해 사용되었다.
  • 기여: 분산 표현 위의 neural network는 최적화 문제가 여전히 non-convex임에도 log likelihood만 최적화하여 언어학적으로 의미 있는 PCFGs를 유도할 수 있게 한다.논문은 이 발견을 model parameterization과 inference의 발전에 기인한 것으로 보며, over-parameterized models에서 최적화상의 이점이 있음을 시사한다 (Arora et al.).
  • 추론: Collapsed inference는 latent vector를 고정하면 compound PCFG가 standard PCFG로 축소되므로 dynamic programming을 사용해 latent trees를 정확히 marginalize한다.연속 latent vector는 inference-network variational posterior에서 reparameterized samples를 사용한 amortized inference로 처리한다 (Kingma and Welling, 2014).
  • 결과: Standard English와 Chinese benchmark에서 제안된 접근법은 unsupervised parsing을 위한 최근 neural 방법들과 비교해 경쟁력 있는 성능을 보인다 (Shen et al., 2018, 2019; Drozdov et al., 2019; Kim et al., 2019).

2 확률적 문맥 자유 문법

PCFG는 parse tree, terminal string, 그리고 관측된 문장에 조건부인 latent tree에 대한 분포를 정의하는 rule probability를 할당한다. Neural parameterization은 분산된 symbol representation을 통해 rule type 간 정보를 공유하면서도 underlying context-free 가정을 유지한다.

  • PCFG는 context-free grammar와 rule probability를 결합하여 parse tree와 그 terminal yield에 대한 분포를 정의한다.어떤 tree의 probability는 그 유도 과정에서 사용된 rule probability의 곱이며, sentence probability는 양립 가능한 tree들에 대해 합산된다.
  • 관측된 문장이 주어지면 PCFG posterior는 해당 문장의 관측되지 않은 latent parse tree들에 probability를 분배한다.Latent tree는 문장의 관측된 leaf를 제외하고, 관측되지 않은 nonterminal 및 preterminal symbol만 포함한다.
  • Direct scalar parameterization은 EM이 closed-form M-step을 가지므로 알고리즘상 편리하지만, natural-language data에서 의미 있는 grammar를 학습하는 데 어려움을 겪는다.예비 실험에서도 이 PCFG parameterization으로 언어학적으로 의미 있는 grammar를 학습하는 데 실패했다.
  • Neural PCFG는 분산된 symbol embedding으로부터 rule probability를 parameterize하여 동일한 probabilistic assumption을 유지하면서 rule type 간 공유를 가능하게 한다.이 model은 여러 rule type에 neural network를 사용하지만, binary nonterminal rule을 위한 MLP는 결과를 경험적으로 개선하지 못했으므로 제외한다.

3 Compound PCFGs

Compound PCFGs는 연속 latent variable을 통해 각 문장에 고유한 rule probability를 부여함으로써, 다루기 쉬운 tree-based generation을 유지하면서 일반적인 PCFGs를 넘어서는 dependency를 유도한다. Learning에서는 inside algorithm으로 tree를 marginalize하고, collapsed amortized variational inference를 사용해 원래는 다루기 어려운 latent-variable integral을 근사한다.

  • Model: Compound PCFGs는 latent vector z로부터 sentence-level rule probabilities를 생성한 뒤, 그 결과로 얻은 PCFG에서 tree와 sentence를 샘플링한다.이 논문에서 prior pγ(z)는 spherical Gaussian이며, neural network fλ는 input-symbol embedding과 z를 결합해 πz를 생성한다.
  • Model: z가 주어지면 grammar는 context-free이지만, z를 marginalize하면 dependency가 생성되어 latent tree structure를 유지하면서도 compound PCFGs의 표현력이 높아진다.이 model은 PCFGs의 continuous mixture로 볼 수 있으며, 각 sentence는 고유한 rule probabilities를 받는다.
  • Learning: Latent-variable integral 때문에 exact marginal likelihood computation은 intractable하지만, conditional tree summation pθ(x | z)는 inside algorithm을 사용해 여전히 tractable하다.반면 neural PCFG likelihood는 differentiable inside algorithm을 사용해 latent tree를 직접 sum out할 수 있다.
  • Learning: Collapsed amortized variational inference는 qφ(z | x)에서 z를 샘플링하고, 해당 sample에 조건부로 tree를 marginalize한 뒤, reparameterization과 analytic KL term을 사용해 ELBO를 최적화한다.Variational posterior는 diagonal Gaussian이며, 그 parameter는 x에 대한 max-pooled LSTM hidden state에서 얻는다.
  • Decoding: Test time에는 inference-network mean μφ(x)에서 CKY를 평가하고 pθ(z | x)를 Dirac delta로 대체하여, 가장 가능성 높은 compound-PCFG tree를 근사한다.이 근사는 tractable하며 실제로 효율적이고 효과적인 것으로 나타났다.

4 실험 설정

실험에서는 표준화된 전처리와 비지도 parsing 평가를 사용해 word-only PTB 및 Chinese PTB benchmark에서 접근법을 평가한다. 설정은 model과 training 구성을 명시하는 한편, 기존 평가 관행의 차이와 validation-F1 hyperparameter tuning으로 인한 한계를 언급한다.

  • Dataset과 전처리: 실험에서는 표준 PTB split과 Chinese PTB version 5.1을 사용하며, punctuation을 제거하고 빈도가 가장 높은 10K개 word type을 유지한다.PTB에서는 training에 split 2–21, validation에 22, testing에 23을 사용하며, Chinese PTB에서는 Chen and Manning (2014)의 split을 사용한다.
  • Model과 training: PCFG는 30개의 nonterminal과 60개의 preterminal을 가지며, compound PCFG는 64-dimensional latent vector와 512-dimensional single-layer bidirectional LSTM inference network를 사용한다.Symbol embedding은 256-dimensional이며, variational mean과 log variance는 LSTM hidden state에 max-pooling을 적용한 뒤 affine layer를 거쳐 계산한다.
  • 평가 protocol: PTB 결과는 validation-tree F1이 일부 hyperparameter를 선택했으므로 엄밀히 완전한 비지도 방식은 아니며, 공정한 비교를 위해 PRPN/ON hyperparameter도 유사하게 tuning했다.저자들은 이 관행을 PTB 평가의 한계로 명시적으로 언급한다.
  • 평가 protocol: 유도된 grammar는 trivial span을 제거한 뒤 sentence-level unlabeled F1을 사용해 비지도 parsing system으로 평가하며, 주로 PRPN [12]과 ON [13]을 비교 대상으로 삼는다.기존 연구는 input representation, punctuation 사용 여부, train/test 분리, F1 계산 방식이 서로 달라 표준화된 비교 protocol이 필요하다.

5 결과 및 논의

compound PCFG는 English와 Chinese에서 평가된 모델 중 가장 뛰어난 비지도 구문 분석 성능을 보이며, 유도된 트리는 유용한 downstream 문법성 판단도 뒷받침한다. 분석 결과 해석 가능한 nonterminal과 주제적 latent representation이 나타났지만, 민감도, 계산 비용, 그리고 지속적인 constituent 식별 한계도 확인되었다.

  • 비지도 구문 분석: compound PCFG는 English와 Chinese 모두에서 unlabeled F1 기준으로 다른 grammar-induction 모델을 상당한 차이로 앞섰지만, 전통적인 scalar PCFG 학습은 실패했다.모든 모델이 right-branching baseline을 앞섰지만, 광범위한 hyperparameter search에도 불구하고 전통적인 PCFG로는 의미 있는 grammar를 유도할 수 없었다.
  • Tree Structure Analysis: 여러 run에 걸쳐 PRPN은 특히 일관된 성능을 보였고, 모델마다 뛰어난 constituent label이 달랐으며, 모든 모델은 특히 긴 SBAR/VP constituent에서 어려움을 겪었다.이 결과는 gold, left, right, self tree와의 비교 및 label-recall 분석을 통해 도출되었다.
  • RNNG 평가: Compound-PCFG로 유도한 tree는 LSTM language model보다 RNNG에서 더 나은 문법성 판단을 산출했으며, perplexity는 더 낮았음에도 binarized gold tree로 학습한 RNNG와 일치했다.유도된 RNNG는 LSTM보다 perplexity를 향상시키지 못했지만, supervised RNNG는 향상시켰다. URNNG fine-tuning은 결과를 추가로 개선했으나, 보고된 F1은 낙관적이다.
  • Model Analysis: 최고 성능의 compound PCFG가 유도한 nonterminal은 linguistic constituent label과 정렬되었고, sentence-level latent representation은 정성적으로 주제 정보를 포착했다.이 분석은 유도된 label과 gold label 사이의 empirical alignment를 시각화하고, variational-posterior mean을 사용해 nearest-neighbor sentence를 식별한다.
  • 한계: 성능은 parameterization, grammar size, optimization, random seed에 민감했으며, O(|R||x|^3) dynamic program 때문에 학습 비용은 NLM 기반 parsing보다 상당히 높았다.더 factorized된 parameterization은 더 나쁜 성능을 보였고, 이러한 계산 비용은 접근법의 scale-up을 어렵게 만들 수 있다.

6 관련 연구

이 논문은 초기 비지도 문법 유도에서 통계적, 휴리스틱, neural, latent-variable PCFG 방법으로 이어지는 발전 과정 속에 자신의 접근법을 위치시킨다. 특히 문법 표현에 continuous vector와 latent subsymbol을 사용하는 모델과 관련된다.

  • 초기 비지도 문법 유도는 대체로 성공적이지 못했으며, 이후 Clark (2001)과 Klein and Manning (2002)의 constituent-context model을 비롯한 영향력 있는 통계적 접근법이 등장했다.초기의 부정적 결과로는 Lari and Young (1990), Carroll and Charniak (1992), Charniak (1993)이 있으며, Pereira and Schabes (1992)는 부분적으로 괄호가 표시된 데이터에서 성공을 보고했다.
  • 대안적 비지도 parsing 방법은 grammar를 명시하고 그 parameter를 학습하는 대신, random subtree subset, incremental heuristic decision, 또는 cascaded application을 사용한다.
  • 최근 neural 접근법은 language model의 soft gating, inside-outside inference를 사용하는 recursive autoencoder, structured inference network, 또는 image-caption grounding을 이용해 단어로부터 tree를 유도한다.이러한 접근법은 Shen et al. (2018, 2019), Drozdov et al. (2019), Kim et al. (2019), Shi et al. (2019)와 관련된다.
  • 이 연구는 nonterminal을 latent subsymbol로 분할하는 latent variable PCFG와도 관련되며, 여기에는 continuous vector를 사용하는 latent vector grammar와 compositional vector grammar가 포함된다.인용된 접근법으로는 Matsuzaki et al. (2005), Petrov et al. (2006), Cohen et al. (2012), Zhao et al. (2018), Socher et al. (2013)이 있다.

7 결론

본 연구는 PCFGs를 활용한 문법 유도를 위한 neural-network 접근법을 개발한다. 먼저 distributed latent-symbol representations로부터 rule probabilities를 parameterize한 뒤, sentence-level continuous latent vector를 도입하도록 모델을 확장한다. neural PCFG는 단순한 maximum-likelihood learning을 통해 언어학적으로 의미 있는 문법 유도를 지원하며, 확장 모델은 전통적인 first-order assumptions를 넘어서는 의존성을 유도한다.

  • 이 연구는 latent symbols의 distributed representations에 대한 neural networks로 rule probabilities를 parameterize하는 neural PCFGs를 제안한다.
  • neural PCFG를 사용한 단순한 maximum-likelihood learning으로 언어학적으로 의미 있는 문법을 유도할 수 있다.
  • neural PCFG를 sentence-level continuous latent vector로 확장하면 전통적인 first-order assumptions를 넘어서는 marginal dependencies가 유도된다.

A 부록 · A.1 모델 파라미터화

이 모델은 좌측 기호의 embedding에 적용한 neural network로 rule probability를 parameterize한다. Compound PCFG에서는 sentence-level latent vector z를 추가 입력으로 사용하며, input dimension만 조정하고 동일한 MLP architecture를 유지한다.

  • A.1 모델 파라미터화: 각 좌측 기호 N에 대한 embedding w_N에 neural network를 적용해 rule probability를 생성한다.기호에는 S, nonterminal, preterminal이 포함된다.
  • A.1 모델 파라미터화: 서로 다른 rule type은 관련 기호 embedding의 neural transformation을 사용해 probability parameter를 생성한다.제시된 parameterization은 root, binary, terminal 관련 rule type을 구분한다.
  • A.1 모델 파라미터화: parameterization은 각각 두 개의 residual layer를 갖는 MLP로 구현된 별도 함수 f1과 f2를 사용한다.product space는 M = (N ∪ P) × (N ∪ P)이다.
  • A.1 모델 파라미터화: Compound PCFG에서는 rule probability π_z가 latent vector z에 조건부로 주어진다.neural processing 전에 latent vector를 해당 symbol embedding과 concatenate한다.
  • A.1 모델 파라미터화: latent-conditioned parameterization은 모델의 rule type 전반에 걸쳐 동일한 concatenated-input design을 적용한다.제시된 형식에는 [w_S; z], [w_A; z], [w_T; z]와 같은 input을 사용하는 root, binary, terminal 관련 rule parameter가 포함된다.
  • A.1 모델 파라미터화: 함수 f1과 f2의 structure는 그대로 유지되지만, z와의 concatenation을 수용하도록 first-layer input dimensions가 확장된다.이를 통해 기존 neural parameterization을 유지하면서 latent variable을 통합한다.

A.2 문장 길이별 Corpus/Sentence F1

Table 6은 문장 길이별 corpus-level 및 sentence-level F1을 보고하며, 각 model의 네 번 실행 결과를 평균낸 값이다.

  • A.2 문장 길이별 Corpus/Sentence F1: Table 6은 문장 길이별 corpus-level 및 sentence-level F1을 제시하며, 각 model의 결과를 4회 실행에 걸쳐 평균낸 값이다.제공된 본문에는 표의 수치가 포함되어 있지 않다.

A.3 RNNG 실험

실험에서는 Kim et al. (2019)의 architecture를 사용해 RNNG를 평가하고, capacity를 맞춘 상태에서 모델을 비교하며, parsing, perplexity, grammaticality judgment를 평가한다. 추가 세부사항에서는 RNNG generation process와 fine-tuning setup을 명시한다.

  • A.3 RNNG 실험: RNNG 실험에서는 Kim et al. (2019)을 따라 0.5 dropout을 적용한 2-layer, 650-dimensional stack LSTM과 650-dimensional tree LSTM composition function을 사용한다.tree LSTM은 Tai et al. (2015)과 Zhu et al. (2015)을 따른다.
  • A.3 RNNG 실험: RNNG는 stack에서 SHIFT 또는 REDUCE를 예측해 문장을 생성하고, SHIFT 후 단어를 sampling하며, REDUCE 후 constituent를 composition한다.SHIFT/REDUCE decision에는 affine transformation 뒤에 sigmoid를 사용하고, vocabulary prediction에는 affine transformation 뒤에 softmax를 사용한다.
  • A.3 RNNG 실험: Fine-tuning에서는 induced trees로 pretrained된 discriminative parser를 evidence lower bound 최적화를 위한 structured inference network로 사용한다.이 setup은 Kim et al. (2019)을 따르며, 추가 세부사항은 해당 논문의 open-source implementation을 통해 제공된다.
  • A.3 RNNG 실험: Table 3의 모든 모델은 대략적으로 capacity가 맞춰져 있다. LSTM baseline은 stack LSTM과 일치하고, PRPN과 ON은 동일한 depth, hidden size, dropout을 사용한다.LSTM baseline은 완전히 right-branching인 tree를 사용하는 RNNG와 동등하다.
  • A.3 RNNG 실험: Grammaticality evaluation에서는 10K-word PTB vocabulary에 없는 단어를 포함한 pair를 제거한 뒤 Marvin and Linzen (2018)의 33K sentence pairs를 유지한다.RNNG와 compound PCFG의 perplexity는 1000개의 importance-weighted samples를 사용해 추정한다.

A.4 비단말/전단말 정렬 · A.5 부분 트리 분석

부록에서는 compound PCFG와 neural PCFG가 전단말을 품사 태그에, 비단말을 gold label에 어떻게 정렬하는지 분석한다. 또한 전체 데이터셋에서 variational posterior mean의 principal component를 사용해 부분 트리별 constituent 패턴을 살펴본다.

  • A.4 비단말/전단말 정렬: 정렬 분석은 compound PCFG와 neural PCFG의 품사 전단말과 비단말 label을 모두 다룬다.
  • A.5 부분 트리 분석: Table 8은 top principal component를 변화시킬 때 각 부분 트리와 연관된 constituent를 나열한다.
  • A.5 부분 트리 분석: 데이터 희소성 때문에 부분 트리 분석은 전체 데이터셋에서 수행한다.분석에 대한 추가 논의는 section 5.2에 제시한다.
  • A.4 비단말/전단말 정렬: Figure 3은 compound PCFG와 neural PCFG의 전단말 정렬을 품사 태그와 비교한다.
  • A.4 비단말/전단말 정렬: Table 7은 두 PCFG에 대해 비단말 label 정렬, 예측된 constituent 빈도, precision, gold-tree 빈도를 보고한다.Label 정렬은 특정 gold label에 대응하는 constituent 중 올바르게 예측된 constituent의 비율로 정의한다.
  • A.5 부분 트리 분석: 각 부분 트리에 대해 해당 부분 트리와 연관된 variational posterior mean vector에 PCA를 적용하고, 점수가 가장 낮은 constituent 다섯 개와 가장 높은 constituent 다섯 개를 나열한다.
Loading 1906.10225v9…