구문 분석(컴퓨터언어학)

Syntactic parsing (computational linguistics)

통사적 파싱은 자연 언어, 특히 통사적 관계(상속성 문법)와 구성원의 라벨링 범위(선거구 문법)의 통사적 구조를 자동 분석하는 것이다.[1]자연어에서의 구조적 모호성 문제에서 동기를 얻는다: 문장에 문법 파를 여러 개 할당할 수 있기 때문에, 계산 문법 규칙을 넘어선 어떤 종류의 지식은 어떤 파스를 의도하는 것인지 알 필요가 있다.통사 파싱은 계산언어학 및 자연어 처리에서 중요한 과제 중 하나로, 컴퓨터의 등장으로 20세기 중반부터 연구의 대상이 되어 왔다.

문법의 다른 이론들은 문장의 통사 구조를 설명하기 위해 다른 형식주의를 제안한다.계산상, 이러한 공식은 선거구 문법과 종속 문법에 따라 분류될 수 있다.각 클래스의 파서들은 다른 유형의 알고리즘을 요구하며, 두 문제에 대한 접근방식은 다른 형태를 취해왔다.다양한 공식성(예: 보편적 종속성)을 이용한 인간공지 트리뱅크의 창조는 새로운 알고리즘과 파싱 방법의 개발과 함께 진행되었다.

부분 음성 태그 지정(일부 의미적 모호성을 해소하는)은 관련 문제로서, 종종 구문 분석의 하위 문제 또는 선행 조건이다.구문 분석은 정보 추출(예: 사건 구문 분석, 의미 역할 라벨링, 개체 라벨링)에 사용할 수 있으며, 공식 의미 표현을 추출하는 데 추가로 사용될 수 있다.

선거구 구문 분석

참고 항목:구문 구조 문법

선거구 구문 분석은 미니멀리즘이나 펜트리뱅크의 형식주의와 같은 선거구 문법 공식화에 따라 파싱하는 것을 포함한다.이는 최소한 어느 범위가 구성 요소인지(예: [남자]가 여기에 있는지) 그리고 어떤 구성 요소인지(예: [남자]는 명사구)를 나타내는 것을 의미하며, 구성 요소 구성과 병합에 대한 규칙을 인코딩하는 문맥 없는 문법(CFG)에 기초한다.[2]

알고리즘은 일반적으로 CFG를 촘스키 정상 형태(구성원당 자녀 2명 포함)로 변환할 것을 요구한다. CFG는 1979년 홉크로프트와 울먼이 처음 설명한 알고리즘을 사용하여 트리에 대한 정보를 잃어버리거나 표현성을 줄이지 않고 수행할 수 있다.[3]

씨케이

선거구 구문 분석에서 가장 인기 있는 알고리즘은 코케-카사미-이다.는 최악의 경우 O({\displaystyle{{O\mathcal}}\left(n^{3}\cdot \left G\right \right)}시간에, n{n\displaystyle}한 문장과는 CFG g의 G{\displaystyle \left G\right}은 규모에 대한 구문 분석을 생성한다 젊은 알고리즘(CKY)[4][5] 있는 동적 프로그래밍 알고리즘iven 나는n 촘스키 노멀 폼.

여러 개의 허용 가능한 파문으로 이어지는 모호성(예: 영어의 전치사-부착의 모호성) 문제를 고려할 때, 가장 가능성 있는 파스를 선택하기 위해서는 파문의 확률을 점수화할 수 있어야 한다.이를 위한 한 가지 방법은 각 선거구 규칙의 확률을 갖는 확률론적 맥락 없는 문법(PCFG)을 사용하고, 상향식 구문 분석 시 확률을 극대화할 수 있도록 CKY를 수정하는 것이다.[6][7][8]

추가적인 수정은 각 구성 요소에 헤드를 할당하고 해당 헤드 슬롯의 각 어휘소에 대한 규칙을 인코딩하는 어휘화된 PCFG이다.따라서 PCFG가 "NP → DT NN"(명사 구문은 결정자 및 명사) 규칙을 가질 수 있는 반면, 어휘화된 PCFG는 "NP(개) → DT N(개)" 또는 "NP(개인) 등과 같은 규칙을 구체적으로 가질 수 있다.실제로 이것은 일부 성능 향상으로 이어진다.[9][10]

보다 최근의 작업은 반복적인 신경망 또는 단어 임베딩 위에 변압기를[11] 사용하는 것과 같이 CKY에 공급하기 위해 스팬 확률(P)CFGs와 달리 맥락을 고려할 수 있는)의 신경 채점을 한다.

전환 기반

종속성 그래머에 O() 전환 기반 파싱의 성공에 따라, 선거구 파싱에 대한 접근방식을 적응시키는 작업이 시작되었다.그러한 첫 번째 작품은 2005년 켄지 사개와 알론 라비에의 작품으로, 이들은 탐욕스럽게 전환 결정을 내리기 위해 특징에 기초한 분류자에 의존했다.[12]이는 2009년 웨 장과 스티븐 클라크의 작업에 이은 것으로, 디코더에 빔 검색을 추가해 세계적으로 최적화된 파스를 만들었다.[13]이 가문이 차트 기반 파서를 능가하는 첫 번째 파서는 2013년 무화주 외가 파서였는데, 이 파서는 패딩 연산을 추가함으로써 단선거구 규칙(종속성 파싱에는 존재하지 않는 문제)으로 인한 서로 다른 전환 시퀀스의 길이 차이 문제를 떠안았다.[14]

전환 기반 구문 분석은 순전히 탐욕적일 수 있으며(즉, 트리를 건설하는 각 시간 단계에서 최상의 옵션을 선택하여 잠재적으로 최적화되지 않거나 잘못된 형태의 트리를 만들 수 있음) 효율을 희생하지 않으면서 성능을 높이기 위해 빔 검색을 사용할 수 있다는 점에 유의하십시오.

시퀀스 대 시퀀스

참고 항목:세크2세크

신경 시퀀스 모델을 활용한 선거구 구문 분석에는 2015년 오리오 비얄스 등이 다른 접근법을 개발했다.[15]이 접근방식에서, 구성 요소 구문 분석은 기계 번역처럼 모델링된다. 과제는 주의 메커니즘이 있는 깊은 LSTM을 사용한 원본 논문에서 문장에서 선거구 구문까지의 순서 변환이다.이런 종류의 모델을 위해 금 훈련 트리를 선형화해야 하지만, 변환은 어떤 정보도 잃지 않는다.이것은 너비 10의 빔 검색 디코더로 () 에서 실행되며(그러나 그들은 더 큰 빔 크기에서 거의 이익을 얻지 못했으며 심지어 그것을 탐욕스러운 디코딩으로 제한함) CKY와 같은 컨텍스트 없는 파싱에 대한 전통적인 알고리즘으로 경쟁적 성능을 달성했다.

종속성 구문 분석

참고 항목:종속문법

종속성 구문 분석은 보편적 종속성(다국어 종속성 트리뱅크를 생산하는 프로젝트이기도 하다)과 같은 종속성 문법 형식주의에 따라 구문 분석하는 것이다.즉, 모든 토큰에 머리(또는 조정의 경우 등)를 할당하고 각 에지에 대한 해당 종속성 관계를 할당하고, 결국 전체 문장에 트리나 그래프를 구성한다는 것을 의미한다.[16]

의존성 파싱을 모델링하는 현대 패러다임에는 대체로 세 가지가 있다. 전환 기반, 문법 기반, 그래프 기반이다.[17]

전환 기반

의존성 트리 파싱에 대한 많은 현대적 접근법은 2003년 조아킴 니브레가 공식화한 전환 기반 파싱(이것의 기본 형태는 아크 표준이라고도 함)을 사용하며,[18] 이는 토큰 스택을 계속 유지함으로써 시프트-리듀스 파싱을 확장하고, 다음 토큰을 위한 세 가지 작업 중에서 결정한다.

  • LeftArc(현재 토큰은 스택 상단의 하위 토큰이며 스택에 추가되지 않음)
  • RightArc(현재 토큰은 스택 상단의 상위 항목이며 상위 항목을 대체함)
  • Shift(스택에 현재 토큰 추가)

알고리즘은 스택의 상위 두 토큰(스택에 다음 토큰을 추가한 후) 또는 스택의 상위 토큰과 문장의 다음 토큰을 비교하는 것으로 공식화할 수 있다.

그러한 알고리즘에 대한 훈련 데이터는 금나무에서 분류기로 공급되는 일련의 전환을 구성하는 오라클을 사용하여 생성된다.분류자는 스택, 버퍼 및 현재 토큰의 현재 상태를 고려할 때 세 가지 작업 중 어떤 작업이 최적의지 학습한다.현대적인 방법은 2014년 단키 첸과 크리스토퍼 매닝의 작업을 시작으로 단어 임베딩에 훈련된 신경 분류기를 사용한다.[19]과거에는 특징 기반 분류자도 공통적으로 사용되었는데, 음성 태그 부분, 문장 위치, 형태학적 정보 등에서 특징이 선택되었다.

이것은 ( ) 탐욕 알고리즘이므로 가능한 최선의 파스나 심지어 반드시 유효한 파스를 보장하지는 않지만 효율적이다.[20]또한 특정 트리가 그것에 도달할 수 있는 유효한 전환의 시퀀스 하나만 가질 수 있으므로 동적 오라클(여러 가지 운영 선택을 허용할 수 있음)이 성능을 증가시킬 수 있는 경우도 반드시 있는 것은 아니다.[21]

이에 대한 수정은 호-eager 구문 분석으로, 다음 작업을 추가한다.감소(스택에서 상단 토큰 제거)사실상, 이것은 더 이른 호 형성을 초래한다.

이 모든 것은 지금까지 투영 트리만 지원하며, 문장에서 토큰 순서를 지정하면 가장자리가 교차하지 않는다.비투영 트리의 경우, 2009년에 Nivre는 운영 스왑을 추가하기 위해 아크 표준 전환 기반 파싱을 수정했다(다음 토큰이 항상 스택에 먼저 추가되는 제형을 가정하여 스택의 상위 2개 토큰을 스왑).이것은 최악의 경우에서 런타임을 ( 2) 로 증가시키지만 실제로는 거의 선형에 가깝다.[22]

문법 기반

투영적 의존성 파싱에 대한 도표 기반의 동적 프로그래밍 접근법은 1996년 마이클[23] 콜린스에 의해 제안되었고 같은 해에 제이슨 아이즈너에[24] 의해 더욱 최적화되었다.[25]이는 CKY(구별 구문 분석에서 이전에 언급된)를 헤드 의존성에 적응시킨 것으로, 선거구 구문 분석에서 유일한 변화는 모든 구성원이 하위 노드 중 하나에 의해 주도된다는 것이다.따라서 어떤 아이가 문법상의 모든 선거구 규칙에 대해 머리를 제공하는지(예: NP는 자신의 자녀 N이 책임진다)를 단순히 특정하여 선거구 CKY 구문 분석에서 종속성 CKY 구문 분석으로 전환할 수 있다.

맥도널드의 원래 적응은 ( O의 런타임이 있었고 아이즈너의 동적 프로그래밍 최적화는 을 O( )로 줄였다아이즈너는 논문에서 스팬 확률을 계산하는 세 가지 다른 채점 방법을 제안했다.

그래프 기반

잘못된 형식의 트리가 생성된 경우 역추적을 사용하여 종속 트리에서 가능한 n의 가장자리를 철저히 검색하면 그래프 기반 종속성 구문을 위한 기준선 O( 런타임이 제공된다.이 접근법은 처음에 마이클 A에 의해 공식적으로 설명되었다. 2001년 코빙턴은 "1960년대 이후 어떤 형태로든 알려진 알고리즘"[26]이라고 주장했다.

파싱 문제는 또한 가능한 모든 종속성 가장자리의 그래프에 걸쳐 있는 최대 확률을 찾아낸 다음 우리가 찾은 나무 가장자리의 종속성 레이블을 선택하는 것으로 모델링될 수 있다.이를 감안하면 엣지 득점자와 레이블 득점자가 있는 추-류/에드몬드 알고리즘의 연장을 사용할 수 있다.이 알고리즘은 2005년 라이언 맥도널드, 페르난도 페레이라, 키릴 리바로프, 얀 하지치가 처음 기술했다.[27]아크 표준 전이 기반 파서, CKY와는 달리 비투사 트리를 처리할 수 있다.이전과 같이 점수 매기는 신경(단어 임베딩으로 교육) 또는 특징 기반일 수 있다.이 작업은 Tarjan의 알고리즘 확장과 함께 (n ){\})로 실행된다.[28]

평가하기

구문 분석기의 성능은 표준 평가 지표를 사용하여 측정한다.선거구와 종속성 구문 분석 접근법 모두 참조 및/또는 가설 구문 분석의 숫자에 대한 구문 분석에서 정확한 일치율(완전 구문 분석된 문장의 백분율)과 정확한 선거구 또는 종속성 할당에 기초하여 계산된 정밀도, 리콜 및 F1-점수에 대해 평가할 수 있다.후자는 PARSEVAL 지표로도 알려져 있다.[29]

종속성 구문 분석은 첨부 파일 점수를 사용하여 평가할 수도 있다.라벨링되지 않은 첨부파일 점수(UAS)는 헤드가 올바르게 할당된 토큰의 백분율이며, 라벨링된 첨부파일 점수(LAS)는 헤드와 종속성 관계 레이블이 올바르게 할당된 토큰의 백분율이다.[30]

파스 간 변환

영어 통사적 구문 분석에 대한 많은 작업이 선거구 형식주의를 사용한 펜트리뱅크에 달려 있다는 점을 감안할 때, 의존성 구문에 대한 많은 연구들은 그것을 훈련 자료로 사용하기 위해 펜의 형식주의를 결정적으로 종속성 구문으로 전환하는 방법을 개발했다.주요한 전환 알고리즘 중 하나는 펜2몰트였는데, 이것은 이 문제에 대한 이전의 작업을 재구성한 것이다.[31]

종속성 구문 분석 알고리즘의 런타임 단축으로 인한 종속성 대 통합 전환 방향의 이점을 활용하십시오..[32]또 다른 접근법은 구조적 동형을 야기하는 모든 토큰에 모든 부양 가족에 대한 사에 주문을 찾는 데는 선형 분급기 훈련하는 것이다 하나의 접근 방법 있는데 그것은 의존도를 구문 분석의 구조를 위반하는 수명을 무시하고 따라서 O런타임을 줄이는 제약 CKY 구문 분석을 사용하고 있(n2){O(n^{2})\displaystyle}nst관능의 [33]파스

참조

  1. ^ 주라프스키 & 마틴 2021.
  2. ^ 주라프스키 & 마틴 2021, 13장.
  3. ^ Lange, Martin; Leiß, Hans (2009). "To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm" (PDF). Informatica Didactica. 8.
  4. ^ Younger, Daniel H. (1967). "Recognition and parsing of context-free languages in time n3". Information and Control. 10 (2): 189–208.
  5. ^ Kasami, T. (1966). "An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages". Bedford, MA: Air Force Cambridge Research Laboratory. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  6. ^ Tsvetkov, Yulia; Titov, Ivan; Berg-Kirkpatrick, Taylor; Klein, Dan (2018). "Algorithms for NLP: Parsing I" (PDF). Algorithms for NLP. Carnegie Mellon University. Retrieved 29 September 2021.
  7. ^ Salomaa, Arto (1969). "Probabilistic and weighted grammars". Information and Control. 15 (6): 529–544.
  8. ^ Booth, Taylor L. (1969). Probabilistic representation of formal languages. 10th Annual Symposium on Switching and Automata Theory.
  9. ^ Chen, Danqi; Narasimhan, Karthik (2019). "Constituency Parsing" (PDF). COS 484: Natural Language Processing.
  10. ^ Collins, Michael (2003). "Head-Driven Statistical Models for Natural Language Parsing". Computational Linguistics. 29 (4): 589–637.
  11. ^ Kitaev, Nikita; Klein, Dan (2018). Constituency Parsing with a Self-Attentive Encoder. Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics. pp. 2676–2686.
  12. ^ Sagae, Kenji; Lavie, Alon (2005). A Classifier-Based Parser with Linear Run-Time Complexity. Proceedings of the Ninth International Workshop on Parsing Technology. pp. 125–132.
  13. ^ Zhang, Yue; Clark, Stephen (2009). Transition-Based Parsing of the Chinese Treebank using a Global Discriminative Model. Proceedings of the 11th International Conference on Parsing Technologies (IWPT’09). pp. 162–171.
  14. ^ Zhu, Muhua; Zhang, Yue; Chen, Wenliang; Zhang, Min; Zhu, Jingbo (2013). Fast and Accurate Shift-Reduce Constituent Parsing. Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics. pp. 434–443.
  15. ^ Vinyals, Oriol; Kaiser, Łukasz; Koo, Terry; Petrov, Slav; Sutskever, Ilya; Hinton, Geoffrey (2015). Grammar as a Foreign Language. Advances in Neural Information Processing Systems 28 (NIPS 2015).
  16. ^ 주라프스키 & 마틴 2021, 14장.
  17. ^ Kübler, McDonald & Nivre 2009.
  18. ^ Nivre, Joakim (2003). An Efficient Algorithm for Projective Dependency Parsing. Proceedings of the Eighth International Conference on Parsing Technologies. pp. 149–160.
  19. ^ Chen, Danqi; Manning, Christopher (2014). A Fast and Accurate Dependency Parser using Neural Networks. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 740–750.
  20. ^ Stymne, Sara (17 December 2014). "Transition-based dependency parsing" (PDF). Syntactic analysis (5LN455). Uppsala Universitet. Retrieved 22 October 2021.
  21. ^ Goldberg, Yoav; Nivre, Joakim (2012). A Dynamic Oracle for Arc-Eager Dependency Parsing. Proceedings of COLING 2012. pp. 959–976.
  22. ^ Nivre, Joakim (2009). Non-Projective Dependency Parsing in Expected Linear Time. Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP. pp. 351–359.
  23. ^ Collins, Michael John (1996). A New Statistical Parser Based on Bigram Lexical Dependencies. 34th Annual Meeting of the Association for Computational Linguistics. pp. 184–191.
  24. ^ Eisner, Jason M. (1996). Three New Probabilistic Models for Dependency Parsing: An Exploration. COLING.
  25. ^ Stymne, Sara (15 December 2014). "Collins' and Eisner's algorithms" (PDF). Syntactic analysis (5LN455). Uppsala Universitet. Retrieved 22 October 2021.
  26. ^ Covington, Michael A. (2001). A Fundamental Algorithm for Dependency Parsing. Proceedings of the 39th Annual ACM Southeast Conference.
  27. ^ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). Non-Projective Dependency Parsing using Spanning Tree Algorithms. Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing. pp. 523–530.
  28. ^ Goldberg, Yoav (2021). "Dependency Parsing" (PDF). Introduction to Natural Language Processing. Bar Ilan University. Retrieved 22 October 2021.
  29. ^ Black, E.; Abney, S.; Flickenger, D.; Gdaniec, C.; Grishman, R.; Harrison, P.; Hindle, D.; Ingria, R.; Jelinek, F.; Klavans, J.; Liberman, M.; Marcus, M.; Roukos, S.; Santorini, B.; Strzalkowski, T. (1991). A Procedure for Quantitatively Comparing the Syntactic Coverage of English Grammars. Speech and Natural Language: Proceedings of a Workshop Held at Pacific Grove, California, February 19-22, 1991.
  30. ^ Kübler, McDonald & Nivre 2009, 6장.
  31. ^ Nivre, Joakim; Hall, Johan; Nilsson, Jens (2006). MaltParser: A Data-Driven Parser-Generator for Dependency Parsing. Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC’06).
  32. ^ Kong, Lingpeng; Rush, Alexander M.; Smith, Noah A. (2015). Transforming Dependencies into Phrase Structures. Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 788–798.
  33. ^ Fernández-González, Daniel; Martins, André F. T. (2015). Parsing as Reduction. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing. pp. 1523–1533.

추가 읽기

종속성 구문 분석

  • Kübler, Sandra; McDonald, Ryan; Nivre, Joakim (2009). Graeme Hirst (ed.). Dependency Parsing. Synthesis Lectures on Human Language Technologies. Morgan & Claypool.