Research papers, articles and examples about parsing in NLP

NLP Parsing References

A context-free grammar consists of a set of rules or productions and a lexicon of words and symbols.  Each of those rules expresses the ways that symbols of the language can be grouped and ordered together.
For example, one rule for noun phrase, like "the flight", is that a noun phrase can be composed of a determiner and a nominal.
$$ NP --> Det \quad Nominal$$



Context-Free Grammars


A parse tree is one way to represent the syntactic structure of a string according to some context-free grammar. In parsing trees, each sentence starts with the start symbol $$S$$.


Parse Tree

The syntactic structure can also be expressed by bracketed notation, which is more compact than the parse tree.
$$ [\mathit{S}[NP [Pro\,\textrm{I}]] [VP [V \,\textrm{perfer}] [NP [Det \,\textrm{a}] [Nom [N \,\textrm{morning}] [Nom [N \,\textrm{flight}]]]]]]$$



Bracketed Notation


Categorical grammar is an early lexicalized grammar model which consists of three major elements: a set of categories, a lexicon that associates words with categories, and a set of rules that govern how categories combine in context.

Categorical Grammar

Unfortunately, the basic categorial approach does not give us any more expressive power than we had with traditional CFG rules; it just moves information from the grammar to the lexicon. To move beyond these limitations CCG is a modern extension of categorical grammar and includes operations that operate over functions.

Combinatory Categorical Grammar (CCG)

Constituency Parsing focuses on constituency structures, those assigned by context-free grammars. In order to know which parse tree is the right one, we need to augment CKY with scores for each possible constituent. 

Constituency Parsing

Dependency Parsing is fundamentally based on the dependency grammars in terms of grammar formalisms. In these formalisms, phrasal constituents and phrase-structure rules do not play a direct role as Constituent Parsing. Instead, the syntactic structure of a sentence is describe solely in terms of the words in a sentence and an associated set of directed binary grammatical relations that hold among the words.

Dependency Parsing

Given a sequence of sentences, automatically determine the coherence relations between them.

Discourse Structure Parsing

The Penn Discourse TreeBank (PDTB) is a second commonly used dataset that embodies model of coherence relations.

 Penn Discourse TreeBank (PDTB)

Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.



Within computational linguistics the term is used to refer to the formal analysis by a computer of a sentence or other string of words into its constituents, resulting in a parse tree showing their syntactic relation to each other, which may also contain semantic and other information (p-values). Some parsing algorithms may generate a parse forest or list of parse trees for a syntactically ambiguous input.



Simply speaking, parsing in NLP is the process of determining the syntactic structure of a text by analyzing its constituent words based on an underlying grammar (of the language).

University of Michigan - Ann Arbor

There is no exact definition for Natural Language Processing (NLP), but we could catch a glimpse through its goal and academic classification.
- The goal of this field (NLP) is to get computers to perform useful tasks involving human language. (Speech and Language Processing, 2nd edition)
- NLP is an interdisciplinary field of linguistics, computer science, information engineering, electrical engineering, psychology, and artificial intelligence. (Speech and Language Processing, 2nd edition; Wikipedia)

Natural language processing gives a computer the ability to analyze and synthesize human languages. 

Natural language processing

https://en.wikipedia.org/wiki/Parsing


https://forum.huawei.com/enterprise/en/what-is-parsing-in-nlp/thread/571685-100429#:~:text=Simply%20speaking%2C%20parsing%20in%20NLP,%E2%80%9CTom%20ate%20an%20apple%E2%80%9D.

Parsing Definition

- Information extraction
- Machine translation
- Discourse, dialogue and pragmatics
- Natural language generation
- Speech recognition
- Lexical semantics
- Phonology / morphology
- Language resources

Natural language processing in ACM Computing Classification

Book:
- Speech and Language Processing (3rd ed. draft) Written by Dan Jurafsky and James H. Martin
- Speech and Language Processing (2nd edition) Written by Dan Jurafsky and James H. Martin
Journal:
- A Survey on Dynamic Neural Networks for Natural Language Processing
- A Survey of Race, Racism, and Anti-Racism in NLP

NLP references

The most important models are:
- state machines
- rule systems
- logic
- probabilistic models
- vector-space models

These models are all drawn from the standard toolkits of computer science, mathematics, and linguistics.

Models used in NLP

Text corpora may have different features that are needed to process differently due to 1)language; 2)genre; 3)the demographic characteristics of the writer (or speaker); 4)time. Proper text normalization is required to make sure the models are fit to the text data. Text normalization make sure that the text is changed into a suitable and excellent form for further processing.

Text normalization

In corpus linguistics, part-of-speech tagging (POS tagging or PoS tagging or POST), also called grammatical tagging is the process of marking up a word in a text (corpus) as corresponding to a particular part of speech, based on both its definition and its context. A simplified form of this is commonly taught to school-age children, in the identification of words as nouns, verbs, adjectives, adverbs, etc. 

Part-of-speech Tagging

Sentiment analysis (also known as opinion mining or emotion AI) refers to the use of natural language processing, text analysis, computational linguistics, and biometrics to systematically identify, extract, quantify, and study affective states and subjective information. 


Sentiment analysis is widely applied to voice of the customer materials such as reviews and survey responses, online and social media, and healthcare materials for applications that range from marketing to customer service to clinical medicine.

Sentiment Analysis

In machine learning and natural language processing, a topic model is a type of statistical model for discovering the abstract "topics" that occur in a collection of documents. 


Topic modeling is a frequently used text-mining tool for discovery of hidden semantic structures in a text body. Intuitively, given that a document is about a particular topic, one would expect particular words to appear in the document more or less frequently: "dog" and "bone" will appear more often in documents about dogs, "cat" and "meow" will appear in documents about cats, and "the" and "is" will appear approximately equally in both. A document typically concerns multiple topics in different proportions; thus, in a document that is 10% about cats and 90% about dogs, there would probably be about 9 times more dog words than cat words. The "topics" produced by topic modeling techniques are clusters of similar words. A topic model captures this intuition in a mathematical framework, which allows examining a set of documents and discovering, based on the statistics of the words in each, what the topics might be and what each document's balance of topics is.


Topic models are also referred to as probabilistic topic models, which refers to statistical algorithms for discovering the latent semantic structures of an extensive text body. In the age of information, the amount of the written material we encounter each day is simply beyond our processing capacity. Topic models can help to organize and offer insights for us to understand large collections of unstructured text bodies. Originally developed as a text-mining tool, topic models have been used to detect instructive structures in data such as genetic information, images, and networks. They also have applications in other fields such as bioinformatics and computer vision.

Topic Model

Parsing

For natural language applications, we often want to use words as the fundamental unit of the output. However, because vocabularies can be very large (up to hundreds of thousands of words), this can be computationally expensive. Both the high memory cost and the high computational cost, which occur at training and testing time, make the standard way to approach this type of distribution have many difficulties.

High Dimensional Outputs

Natural Language Processing has been developing alongside machine learning techniques for at least since 1990. In 1986 Rumelhart et al. developed one of the first instances of symbolic encoding for a neural network like structure. In 1990 Deerwester et al. then adapted this idea of symbolic encoding into word encoding which could then in theory be used in an NLP neural network. 

From 1991 until 2001, however, encoded word processing was ignored in favor of attempts at creating a character recognizing network instead. Such a system would have to learn both grammatical structure and the spelling of every word it would use in that structure. As a result, in 2001 when Bengio et al. reintroduced word processing, it initially had a higher performance than most other character processing networks. 

Although word processing networks were initially more performant, over time both methods for creating NLP networks have improved, and continue to show signs that more improvement may be possible. As such, it is hard to determine which method will ultimately prove more effective than the other.

Historical Perspective: Natural Language Processing

Natural language documents are read and studied by computers so they can answer the questions posed.

Machine Reading and Comprehension

In NLP, we need to find out how similar the two strings are to each other. Minimum edit distance finds out the dissimilarity of two strings and counts the minimum number of modifications to transform a string to another. Levenshtein distance is the method that is used to measure the minimum edit distance.

Minimum Edit Distance

Pieces of text used to train and/or develop NLP models can vary in several ways that may need to be accounted for, such as: 
- The language the text is written in
- The type/genre of text
- The author/speaker of the text
- How old the text is

Variation Factors of Input Texts

A common NLP task that applies logistic regression- to determine if the period symbol "." is the end of a sentence or not. A feature  express a single property or a combination of properties, such as the capitalization of the current word or previous word.

Period Disambiguation

Features of the instances are designed by hand- by examining the training set with linguistic intuitions and literacy level on the domain. 

Features Design for NLP Classification Problems

Vectors semantics is the standard way to represent word meaning in NLP. The idea of vector semantics is to represent a word as a point in a multidimensional semantic space that is derived from the distributions of the term is sometimes more strictly applied only to dense vectors like word2vec, rather than sparse tf-idf or PPMI vectors. The word 'embedding' derives from its mathematical sense as a mapping form one space or structure to another, although the meaning has shifted.

Vector Semantics and Embeddings

Vector or distributional models of meaning are generally based on a co-occurrence matrix, a way of representing how often words co-occur. We'll look at two popular matrices: the term-document matrix and the term-term matrix.

Words and Vectors

While word classes do have semantic tendencies—adjectives, for example, often describe properties and nouns people— parts of speech are defined instead based on their grammatical relationship with neighboring words or the morphological properties about their affixes.

English Word Classes

Computational Desiderata for Representations:

Verifiability:

Verifiability is a system’s ability to compare the state of affairs described by a representation to the state of affairs in some world as modeled in a knowledge base. 

Unambiguous Representations:

The meaning representations itself cannot be ambiguous. The representation of an input’s meaning should be free from any ambiguity, so that the system can reason over a representation that means either one thing or the other in order to decide how to answer. Vagueness: in which a meaning representation leaves some parts of the meaning underspecified. 

Canonical Form:

The doctrine of canonical form says that distinct inputs that mean the same thing
should have the same meaning representation. Canonical form does complicate the task of semantic parsing. 


Logical Representations of Sentence Meaning

First-Order Logic (FOL) is a flexible, well-understood, and computationally tractable meaning representation language.


First-Order Logic

Information extraction is a fundamental task in NLP where many problems can be framed as extracting specific, structured information from unstructured text. This process involves identifying data points such as named entities, relationships, and events. The ultimate goal is to convert this raw textual data into a structured format suitable for analysis and utilization in various downstream applications.

Information Extraction

A sense (or word sense) is a discrete representation of one aspect of the meaning of a word.

Word Senses

Utilized as a way to express the role that arguments of a predicate take
in a event.

Semantic Roles: Labeling

Semantic roles focus about what a word actually means and is actually doing in the semantic context they do not care about the structure of the sentence.

Semantic Roles ( Thematic Roles )

Question Answering is a computer science discipline within the fields of information retrieval and natural language processing (NLP), which is concerned with building systems that automatically answer questions posed by humans in a natural language.

Question Answering

It is the process of obtaining information system resources that are relevant to an information need from a collection of those resources. 

Information Retrieval

Dialogue systems, or conversational agents, are programs that communicate with users, through text and/or speech, in natural language.

Dialogue Systems

Intricate components of natural human conversation that must be considered when creating a dialogue system

1) Turn Structure

2) Speech Acts

3) Grounding

4) Dialogue Structure

5) Initiative

6) Implicature

Properties of Human Conversation

Prompt tuning is a parameter-efficient adaptation method for Large Language Models. It involves incorporating a set of trainable vectors, or soft prompts, which are adjusted during training to steer the model for a specific task. A defining characteristic of this technique is that it only modifies the model's input embedding layer, leaving the rest of the pre-trained model's parameters frozen.

Prompt Tuning

1. Fully Supervised Learning(Non-Neural Network)
2. Fully Supervised Learning(Neural Network)
3. Pre-train, Fine-tune
4. Pre-train, Prompt, Predict

Types of NLP Model Paradigms

1. Standard Language Model(SLM)
2. Corrupted Text Reconstruction(CTR)
3. Full Text Reconstruction(FTR)

Types of Training Objectives of Pre-trained LM

1. Promptless Fine-tuning
2. Tuning-free Prompting
3. Fixed-LM Prompt Tuning
4. Fixed-Prompt LM Tuning
5. Prompt+LM Fine-tuning

Major Tuning Strategy Types

Articulatory Phonetics is an area of study that focuses on how throat, mouth and nose work together to modify the airflow from lung to produce phonetics,

Articulatory Phonetics

Phonetics is the field of study in which speech sounds from world languages are studied - how they are created in a vocal tract, how they materialize in an acoustic sense, and how they can be relayed or processed digitally. 

Phonetics

Rather than representing words as discrete variables, word embeddings map words into low-dimensional real-valued vectors. This continuous representation space makes it possible to compute the meanings of words and word $$n$$-grams. As a result of this distributed representation, language models are no longer burdened with the curse of dimensionality, allowing them to represent exponentially many $$n$$-grams via a compact and dense neural model.

Word embedding

https://arxiv-download.xixiaoyao.cn/pdf/2105.03075.pdf

A Survey of Data Augmentation Approaches for NLP

Data augmentation (DA) refers to strategies for increasing the diversity of training examples without explicitly collecting new data. Related methods are first explored in computer vision (CV), and DA’s adaptation for natural language processing (NLP) seems secondary and comparatively underexplored.

Data Augmentation in NLP

Spelling correction is often considered from two perspectives, non-word spelling correction and real word spelling correction.

Spelling correction and the noisy channel

Syntactic constituency is the idea that groups of words can act as single units, which are called constituents

Constituency

The categorization of texts into organized groups, which is usually implemented by supervised learning.
Applications: sentiment analysis, spam detection, news categorization, topic analysis, and more.

Text Classification

Information extraction aims to extract structural information from unstructured text, which is a key field within natural language processing. 

Information Extraction (IE)

https://dspace.mit.edu/bitstream/handle/1721.1/116314/10462_2017_9588_ReferencePDF.pdf?sequence=2&isAllowed=y

A Survey of Natural Language Based Financial Forecasting

Han, X., Gao, T., Lin, Y., Peng, H., Yang, Y., Xiao, C., … Zhou, J. (2020). More Data, More Relations, More Context and More Openness: A Review and Outlook for Relation Extraction. doi:10.48550/ARXIV.2004.03186


More Data, More Relations, More Context and More Openness: A Review and Outlook for Relation Extraction

https://ieeexplore.ieee.org/abstract/document/9328413

A Survey of the State-of-the-Art Models in Neural Abstractive Text Summarization

From Standard Summarization to New Tasks and Beyond: Summarization with Manifold Information

Machine translation (MT) is the task of automatically translating from one language to another without human labor, which brings convenience and reduces labor cost in international exchange and cooperation.

Machine Translation (MT)

Extracting temporal cues from text, and constructing a global temporal view about the order of described events is a major challenge of automatic natural language understanding. 

Temporal reasoning (TR), the process of combining different temporal cues into a coherent temporal view, plays a central role in temporal information extraction.

Temporal Reasoning

A structured way of representing knowledge.
It consists of entities, relationships, and semantic descriptions. In other words, knowledge graphs represent logical relationship between entities.

Knowledge Graph

Increasing model capacity is an effective approach for better performance in NLP. However, larger model capacity will increase computational load and memory consumption, which becomes a bottleneck for increasing model capacity. Dynamic Neural Network is used to overcome this issue, by adjusting the computational path based on the inputs.

Dynamic Neural Network in Natural Language Processing

Label preservations are transformations of training data that preserve class information. If the label is adjusted correctly, they are sometimes also adapted to cover transformations that alter the class information.

Learn Before

Related

Learn After