Construction Analysis

Date: 23.04.28

Writer: 9tailwolf : doryeon514@gm.gist.ac.kr


Introduction

Construction Analysis is a important element of understanding natural language. In NLP, we can use some algorithms to process construction, there is a phrase structure grammer and dependency grammer. By these algorithm, we can challenge syntax ambiguity problem.


Phrase Structure Grammer

Phrase Structure Grammer is suggested by Noam Chomsky that analysis constituency relation.

Rule Based phrase structure analysis

By divide constituency from a rule, we can make sentence structure. Following is a process.

  1. Apply Vocabulary Dictionary.
  2. Apply the generation rule of NP(Noun Phrase) and VP(Verb Phrase).
  3. Apply VP -> NP,VP Rule. It is a process that to combine verb phrase and direct object to make one of the big verb phrase.
  4. Apply S -> NP, VP Rule. It is a process that to combile noun phrase(subject) and verb phrase to make one sentence.
Statistic Based phrase structure analysis

Probability phrase structure grammer is defined by below probability.

\[A \rightarrow B C [P]\]

And we can calculate above probability as follows.

\[P(\alpha\rightarrow\beta|\alpha) = \frac{Count(\alpha\rightarrow\beta)}{\Sigma_{\gamma}Count(\alpha\rightarrow\gamma)} = \frac{Count(\alpha\rightarrow\beta)}{Count(\alpha)}\]

And there is a inside-out algorithm. The result of phrase analysis can be write as below.

\[P(T|S) = \Pi_{i}P(\alpha_{i}\rightarrow\beta_{i}|\alpha_{i})\]

And the result can be the highest value of \(P(T | S)\) .

Deep Learning Based phrase structure analysis

Transsition based parsing is a algorithm that read each word and select action. Actions are determined by oracle. There is a three actions.

  • Shift (Push in stack)
  • Unary-reduce (Pop in stack)
  • Binary-reduce (Pop two element and combine)


Dependency Grammer

Dependency Grammer is suggested by Lucian Tesnière that analysis dependency relation. It is a algorithm that create modifier tree based on head. Graph based parsing is a famous algorithm of dependency grammer. In natural language sentence, calculate all score of dependency relationship. Other algorithm is simmilar as phrase structure analysis algorithm.