Networks and Natural Language Processing

By Radev, Dragomir R.; Mihalcea, Rada | AI Magazine, Fall 2008 | Go to article overview

Networks and Natural Language Processing


Radev, Dragomir R., Mihalcea, Rada, AI Magazine


In a cohesive text, language units--whether they are words, phrases, or entire sentences--are connected through a variety of relations, which contribute to the overall meaning of the text and maintain the cohesive structure of the text and the discourse unity. Since the early ages of artificial intelligence, associative or semantic networks have been proposed as representations that enable the storage of such language units and the relations that interconnect them and that allow for a variety of inference and reasoning processes, simulating some of the functionalities of the human mind. The symbolic structures that emerge from these representations correspond naturally to graphs--where text constituents are represented as vertices and their interconnecting relations form the edges in the graph.

The last decade has brought on a number of exciting research papers that apply graph-based methods to an increasingly large range of natural language problems, ranging from lexical acquisition to text summarization. In this article, we overview several of these methods and their application to natural language processing. To reflect the fact that the algorithms and representations originate in different communities--natural language processing and graph theory--we will be using a dual vocabulary to describe these methods: networks are graphs, nodes are vertices, and links are edges.

In terms of graph-based representations, depending on the natural language-processing application, a variety of node and edge types have been used. Text units of various sizes and characteristics can be added as vertices in the graph, for example, words, collocations, word senses, entire sentences, or even entire documents. Note that the graph nodes do not have to belong to the same category. For example, both sentences and

words can be added as vertices in the same graph. Edges can represent cooccurrence (such as two words that appear in the same sentence or in the same dictionary definition), collocation (for example, two words that appear immediately next to each other or that may be separated by a conjunction), syntactic structure (for example, the parent and child in a syntactic dependency), and lexical similarity (for example, cosine between the vector representations of two sentences).

In terms of graph-based algorithms, the main methods used so far can be classified into: (1) semisupervised classification (Zhu and Ghahramani 2002; Zhu and Lafferty 2005; Toutanova, Manning, and Ng 2004; Radev 2004; Otterbacher, Erkan, and Radev 2005), where random walks or relaxation are applied on mixed sets of labeled and unlabeled nodes; (2) network analysis (Masucci and Rodgers 2006; Caldeira et al. 2006), where network properties such as diameter, centrality, and so on, are calculated; (3) graph-based clustering methods (Pang and Lee 2004, Widdows and Dorow 2002), such as min-cut methods; (4) minimum spanning-tree algorithms (McDonald et al. 2005).

In this article, we overview several graph-based approaches for natural language-processing tasks, which we broadly group into three main categories. First, we review research work done in the area of syntax, including syntactic parsing, prepositional attachment, and coreference resolution. We then describe methods used in lexical semantics, including word-sense disambiguation, lexical acquisition, and sentiment and subjectivity analysis. Finally, we review several natural language-processing applications that rely on graph methods, including text summarization, passage retrieval, and keyword extraction.

[FIGURE 1 OMITTED]

Syntax

In this section we will discuss three papers, addressing methods for syntactic parsing (McDonald et al. 2005), prepositional attachment (Toutanova, Manning, and Ng 2004), and coreference resolution (Nicolae and Nicolae 2006).

Dependency Parsing

Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajic (McDonald et al. …

The rest of this article is only available to active members of Questia

Sign up now for a free, 1-day trial and receive full access to:

  • Questia's entire collection
  • Automatic bibliography creation
  • More helpful research tools like notes, citations, and highlights
  • Ad-free environment

Already a member? Log in now.

Notes for this article

Add a new note
If you are trying to select text to create highlights or citations, remember that you must now click or tap on the first word, and then click or tap on the last word.
One moment ...
Default project is now your active project.
Project items

Items saved from this article

This article has been saved
Highlights (0)
Some of your highlights are legacy items.

Highlights saved before July 30, 2012 will not be displayed on their respective source pages.

You can easily re-create the highlights by opening the book page or article, selecting the text, and clicking “Highlight.”

Citations (0)
Some of your citations are legacy items.

Any citation created before July 30, 2012 will labeled as a “Cited page.” New citations will be saved as cited passages, pages or articles.

We also added the ability to view new citations from your projects or the book or article where you created them.

Notes (0)
Bookmarks (0)

You have no saved items from this article

Project items include:
  • Saved book/article
  • Highlights
  • Quotes/citations
  • Notes
  • Bookmarks
Notes
Cite this article

Cited article

Style
Citations are available only to our active members.
Sign up now to cite pages or passages in MLA, APA and Chicago citation styles.

(Einhorn, 1992, p. 25)

(Einhorn 25)

1

1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

Cited article

Networks and Natural Language Processing
Settings

Settings

Typeface
Text size Smaller Larger Reset View mode
Search within

Search within this article

Look up

Look up a word

  • Dictionary
  • Thesaurus
Please submit a word or phrase above.
Print this page

Print this page

Why can't I print more than one page at a time?

Full screen

matching results for page

Cited passage

Style
Citations are available only to our active members.
Sign up now to cite pages or passages in MLA, APA and Chicago citation styles.

"Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn, 1992, p. 25).

"Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn 25)

"Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences."1

1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

Cited passage

Thanks for trying Questia!

Please continue trying out our research tools, but please note, full functionality is available only to our active members.

Your work will be lost once you leave this Web page.

For full access in an ad-free environment, sign up now for a FREE, 1-day trial.

Already a member? Log in now.