This article does not cite any references or sources. (November 2007) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

Natural language processing (NLP) is a subfield of artificial intelligence and computational linguistics. It studies the problems of automated generation and understanding of natural human languages. Natural language generation systems convert information from computer databases into normal-sounding human language, and natural language understanding systems convert samples of human language into more formal representations that are easier for computer programs to manipulate. Image File history File links Question_book-3. ... AI redirects here. ... Computational linguistics is an interdisciplinary field dealing with the statistical and logical modeling of natural language from a computational perspective. ... The term natural language is used to distinguish languages spoken and signed (by hand signals and facial expressions) by humans for general-purpose communication from constructs such as writing, computer-programming languages or the languages used in the study of formal logic, especially mathematical logic. ...

Tasks and limitations

In theory, natural language processing is a very attractive method of human-computer interaction. Early systems such as SHRDLU, working in restricted "blocks worlds" with restricted vocabularies, worked extremely well, leading researchers to excessive optimism which was soon lost when the systems were extended to more realistic situations with real-world ambiguity and complexity. // Human–computer interaction (HCI), alternatively man–machine interaction (MMI) or computer–human interaction (CHI)This interactive computer allows the user to intergrate a reaction towards oneself and the primary source that is the http server, the port and Ip address show as the user connects to the imb harddrive , is... // SHRDLU was an early natural language understanding computer program, developed by Terry Winograd at MIT from 1968-1970. ... The blocks world is one of the most famous planning domains in artificial intelligence. ...

Natural language understanding is sometimes referred to as an AI-complete problem, because natural language recognition seems to require extensive knowledge about the outside world and the ability to manipulate it. The definition of "understanding" is one of the major problems in natural language processing. AI-complete is, by analogy to NP-completeness in complexity theory, a term first coined by Fanya S. Montalvo to indicate that the difficulty of a computational problem is equivalent to solving the central Artificial Intelligence problem, i. ... Look up understanding in Wiktionary, the free dictionary. ...

Concrete problems

Some examples of the problems faced by natural language understanding systems:

• The sentences We gave the monkeys the bananas because they were hungry and We gave the monkeys the bananas because they were over-ripe have the same surface grammatical structure. However, in one of them the word they refers to the monkeys, in the other it refers to the bananas: the sentence cannot be understood properly without knowledge of the properties and behavior of monkeys and bananas.

• A string of words may be interpreted in different ways. For example, the string Time flies like an arrow may be interpreted in a variety of ways:
  • The common simile time moves quickly just like an arrow does;
  • measure the speed of flying insects like you would measure that of an arrow (thus interpreted as an imperative) - i.e. (You should) time flies as you would (time) an arrow.;
  • measure the speed of flying insects like an arrow would - i.e. Time flies in the same way that an arrow would (time them).;
  • measure the speed of flying insects that are like arrows - i.e. Time those flies that are like arrows;
  • all of a type of flying insect, "time-flies," collectively enjoys a single arrow (compare Fruit flies like a banana);
  • each of a type of flying insect, "time-flies," individually enjoys a different arrow (similar comparison applies);
  • the magazine, Time, travels straight when thrown

English is particularly challenging in this regard because it has little inflectional morphology to distinguish between parts of speech. A simile is a comparison of two unlike things, typically marked by use of like, as, than, or resembles. Common examples are Curley was flopping like a fish on a line(extract of Mice and Men) etc. ... Look up time in Wiktionary, the free dictionary. ... “TIME” redirects here. ... Inflection morphology is a process in natural language processing. ...

• English and several other languages don't specify which word an adjective applies to. For example, in the string "pretty little girls' school".
  • Does the school look little?
  • Do the girls look little?
  • Do the girls look pretty?
  • Does the school look pretty?

• We will often resolve ambiguities in language by the way we place stress on words. The sentence "I never said she stole my money" demonstrates the importance stress can play in a sentence, and thus the inherent difficulty a natural language processor can have in parsing it. Depending on which word the speaker places the stress, this sentence could have several distinct meanings:
  • "I never said she stole my money" - Someone else said it, but I didn't.
  • "I never said she stole my money" - I simply didn't ever say it.
  • "I never said she stole my money" - I might have implied it in some way or other, but I never explicitly said it.
  • "I never said she stole my money" - I said someone else took it, not her.
  • "I never said she stole my money" - I just said she probably borrowed it.
  • "I never said she stole my money" - I said she stole someone else's money.
  • "I never said she stole my money" - I accused her of stealing my elephant, but not my money.

Subproblems

Speech segmentation

In most spoken languages, the sounds representing successive letters blend into each other, so the conversion of the analog signal to discrete characters can be a very difficult process. Also, in natural speech there are hardly any pauses between successive words; the location of those boundaries usually must take into account grammatical and semantical constraints, as well as the context.

Text segmentation

Some written languages like Chinese, Japanese and Thai do not have single word boundaries either, so any significant text parsing usually requires the identification of word boundaries, which is often a non-trivial task.

Word sense disambiguation

Many words have more than one meaning; we have to select the meaning which makes the most sense in context.

Syntactic ambiguity

The grammar for natural languages is ambiguous, i.e. there are often multiple possible parse trees for a given sentence. Choosing the most appropriate one usually requires semantic and contextual information. Specific problem components of syntactic ambiguity include sentence boundary disambiguation.

Imperfect or irregular input 

Foreign or regional accents and vocal impediments in speech; typing or grammatical errors, OCR errors in texts.

Speech acts and plans

Sentences often don't mean what they literally say; for instance a good answer to "Can you pass the salt" is to pass the salt; in most contexts "Yes" is not a good answer, although "No" is better and "I'm afraid that I can't see it" is better yet. And for the question "How many students failed the class last year?", "The class was not offered last year" is a better answer than "None".

Speech segmentation is the process of identifying the boundaries between words, syllables, or phonemes in spoken natural languages. ... Written text segmentation is the process of dividing written text into words or other similar meaningful units. ... “WSD” redirects here. ... Syntactic ambiguity is a property of sentences which may be reasonably interpreted in more than one way, or reasonably interpreted to mean more than one thing. ... For the rules of English grammar, see English grammar and Disputes in English grammar. ... The term natural language is used to distinguish languages spoken and signed (by hand signals and facial expressions) by humans for general-purpose communication from constructs such as writing, computer-programming languages or the languages used in the study of formal logic, especially mathematical logic. ... - Emo Philips A word, phrase, sentence, or other communication is called ambiguous if it can be reasonably interpreted in more than one way. ... A parse tree or concrete syntax tree is a tree that represents the syntactic structure of a string according to some formal grammar. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... Sentence boundary disambiguation (SBD) is the problem in natural language processing of deciding where the beginning and ends of sentences are. ... Optical character recognition, usually abbreviated to OCR, is a type of computer software designed to translate images of handwritten or typewritten text (usually captured by a scanner) into machine-editable text, or to translate pictures of characters into a standard encoding scheme representing them (e. ... A speech act is an action performed by means of language, such as describing something (), asking a question (Is it snowing?), making a request or order (Could you pass the salt?, Drop your weapon or Ill shoot you!), or making a promise () For much of the history of linguistics...

Statistical NLP

Main article: statistical natural language processing

Statistical natural language processing uses stochastic, probabilistic and statistical methods to resolve some of the difficulties discussed above, especially those which arise because longer sentences are highly ambiguous when processed with realistic grammars, yielding thousands or millions of possible analyses. Methods for disambiguation often involve the use of corpora and Markov models. The technology for statistical NLP comes mainly from machine learning and data mining, both of which are fields of artificial intelligence that involve learning from data. A stochastic grammar (statistical grammar) is a grammar framework with a probabilistic notion of grammaticality: Stochastic context-free grammar Statistical parsing Data-oriented parsing Hidden Markov model Estimation theory Statistical natural language processing uses stochastic, probabilistic and statistical methods, especially to resolve difficulties which arise because longer sentences are highly... Stochastic, from the Greek stochos or goal, means of, relating to, or characterized by conjecture; conjectural; random. ... The word probability derives from the Latin probare (to prove, or to test). ... For Wikipedia statistics, see m:Statistics Statistics is the science and practice of developing human knowledge through the use of empirical data expressed in quantitative form. ... Corpus linguistics is the study of language as expressed in samples (corpora) or real world text. ... In mathematics, a (discrete-time) Markov chain is a discrete-time stochastic process with the Markov property. ... As a broad subfield of artificial intelligence, machine learning is concerned with the design and development of algorithms and techniques that allow computers to learn. At a general level, there are two types of learning: inductive, and deductive. ... Data mining is the principle of sorting through large amounts of data and picking out relevant information. ... AI redirects here. ...

Major tasks in NLP

• Automatic summarization
• Foreign Language Reading Aid
• Foreign Language Writing Aid
• Information extraction
• Information retrieval
• Machine translation
• Named entity recognition
• Natural language generation
• Optical Character Recognition
• Question answering
• Speech recognition
• Spoken dialogue system
• Text simplification
• Text to speech
• Text-proofing

Automatic summarization is the creation of a shortened version of a text by a computer program. ... A foreign language reading aid is a computer program that assists a non-native language user to read properly in their target language. ... A foreign language writing aid is a computer program that assists a non-native language user in writing decently in this target language. ... Information extraction (IE) is a type of information retrieval whose goal is to automatically extract structured or semistructured information from unstructured machine-readable documents. ... Information retrieval (IR) is the science of searching for information in documents, searching for documents themselves, searching for metadata which describe documents, or searching within databases, whether relational stand-alone databases or hypertextually-networked databases such as the World Wide Web. ... Machine translation, sometimes referred to by the acronym MT, is a sub-field of computational linguistics that investigates the use of computer software to translate text or speech from one natural language to another. ... Named entity recognition (NER) (also known as entity identification (EI) and entity extraction) is a subtask of information extraction that seeks to locate and classify atomic elements in text into predefined categories such as the names of persons, organizations, locations, expressions of times, quantities, monetary values, percentages, etc. ... Natural Language Generation (NLG) is the natural language processing task of generating natural language from a machine representation system such as a knowledge base or a logical form. ... Optical character recognition, usually abbreviated to OCR, is a type of computer software designed to translate images of handwritten or typewritten text (usually captured by a scanner) into machine-editable text, or to translate pictures of characters into a standard encoding scheme representing them (e. ... Question answering (QA) is a type of information retrieval. ... Speech recognition (in many contexts also known as automatic speech recognition, computer speech recognition or erroneously as Voice Recognition) is the process of converting a speech signal to a sequence of words, by means of an algorithm implemented as a computer program. ... A Spoken dialog system is a dialog system delivered through voice. ... In natural language processing, text simplification is an important task due to the fact that much of the english language is in complex compound sentences that are not easily processible for information tasks. ... Speech synthesis is the artificial production of human speech. ... Proofreading is reading a proof copy of text for the purpose of detecting errors. ...

Evaluation of natural language processing

The goal of NLP evaluation is to measure one or more qualities of an algorithm or a system, in order to determine if (or to what extent) the system answers the goals of its designers, or the needs of its users. Research in NLP evaluation has received considerable attention, because the definition of proper evaluation criteria is one way to specify precisely an NLP problem, going thus beyond the vagueness of tasks defined only as language understanding or language generation. A precise set of evaluation criteria, which includes mainly evaluation data and evaluation metrics, enables several teams to compare their solutions to a given NLP problem.

• History of evaluation in NLP

...

Depending on the evaluation procedures, a number of distinctions are traditionally made in NLP evaluation.

• Intrinsic vs. extrinsic evaluation

Intrinsic evaluation considers an isolated NLP system and characterizes its performance mainly with respect to a gold standard result, pre-defined by the evaluators. Extrinsic evaluation, also called evaluation in use considers the NLP system in a more complex setting, either as an embedded system or serving a precise function for a human user. The extrinsic performance of the system is then characterized in terms of its utility with respect to the overall task of the complex system or the human user.

• Black-box vs. glass-box evaluation

Black-box evaluation requires one to run an NLP system on a given data set and to measure a number of parameters related to the quality of the process (speed, reliability, resource consumption) and, most importantly, to the quality of the result (e.g. the accuracy of data annotation or the fidelity of a translation). Glass-box evaluation looks at the design of the system, the algorithms that are implemented, the linguistic resources it uses (e.g. vocabulary size), etc. Given the complexity of NLP problems, it is often difficult to predict performance only on the basis of glass-box evaluation, but this type of evaluation is more informative with respect to error analysis or future developments of a system.

• Automatic vs. manual evaluation

In many cases, automatic procedures can be defined to evaluate an NLP system by comparing its output with the gold standard (or desired) one. Although the cost of producing the gold standard can be quite high, automatic evaluation can be repeated as often as needed without much additional costs (on the same input data). However, for many NLP problems, the definition of a gold standard is a complex task, and can prove impossible when inter-annotator agreement is insufficient. Manual evaluation is performed by human judges, which are instructed to estimate the quality of a system, or most often of a sample of its output, based on a number of criteria. Although, thanks to their linguistic competence, human judges can be considered as the reference for a number of language processing tasks, there is also considerable variation across their ratings. This is why automatic evaluation is sometimes referred to as objective evaluation, while the human kind appears to be more subjective.

• Shared tasks
  • Message Understanding Conference
  • Text Retrieval Conference
  • BioCreative

The research in the Information Extraction (IE) in the late 1980s and 1990s was promoted and evaluated by the Message Understanding Conferences (MUCs) -- the seven conferences held at the end of the international IE competitions -- which were initiated and sponsored by the Defense Advanced Research Projects Agency (DARPA... The Text REtrieval Conference (TREC) is an on-going series of workshops focusing on a list of different information retrieval (IR) research areas, or It is co-sponsored by the National Institute of Standards and Technology (NIST) and Advanced Research and Development Activity (ARDA) center of the U.S. Department... BioCreative (A critical assessment of text mining methods in molecular biology) consists in a community-wide effort for evaluating information extraction and text mining developments in the biological domain. ...

Organizations and conferences

• Association for Computational Linguistics
• Association for Machine Translation in the Americas
• AFNLP - Asian Federation of Natural Language Processing Associations

The Association for Computational Linguistics (ACL) is the international scientific and professional society for people working on problems involving natural language and computation. ... AFNLP (Asian Federation of Natural Language Processing Associations) is the organization for coordinating the natural language processing related activities and events in the Asia-Pacific region. ...

Software tools

• General Architecture for Text Engineering
• Natural Language Toolkit
• Expert System S.p.A.

General Architecture for Text Engineering or GATE is a Java software toolkit originally developed at the University of Sheffield since 1995 and now used worldwide by a wide community of scientists, companies, teachers and students for all sorts of natural language processing tasks, including information extraction in many languages. ... Natural Language Toolkit or, more commonly, NLTK is a suite of libraries and programs for symbolic and statistical natural language processing (NLP) for the Python programming language. ... Expert System is a software company, founded in Italy in 1989, pioneer in developing and marketing semantic technologies to understand and manage unstructured information. ...

See also

• AskWiki
• Biomedical text mining
• Chatterbot
• Computational linguistics
• Computer-assisted reviewing
• Controlled natural language
• Human language technology
• Inform 7 programming language
• Information retrieval
• Latent semantic indexing
• lojban / loglan
• Name resolution
• Transderivational search
• Universal translator (fictional)

AskWiki, developed in partnership between AskMeNow and the Wikimedia Foundation, is a preliminary integration of a semantic search engine that seeks to provide specific answers to questions using information from Wikipedia articles. ... Biomedical text mining is a rather recent research field on the edge of natural language processing, bioinformatics, medical informatics and computational linguistics. ... A chatterbot is a computer program designed to simulate an intelligent conversation with one or more human users via auditory or textual methods. ... Computational linguistics is an interdisciplinary field dealing with the statistical and logical modeling of natural language from a computational perspective. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... Controlled Natural Languages are subsets of natural languages whose grammars and dictionaries have been restricted in order to reduce or eliminate both ambiguity and complexity. ... Language technology is often called Human Language Technology (HLT) and consists of computational linguistics (or CL) and speech technology as its core but includes also many application oriented aspects of them. ... Inform is a programming language and design system for interactive fiction originally created in 1993 by Graham Nelson. ... Information retrieval (IR) is the science of searching for information in documents, searching for documents themselves, searching for metadata which describe documents, or searching within databases, whether relational stand-alone databases or hypertextually-networked databases such as the World Wide Web. ... Latent semantic analysis (LSA) is a technique in information retrieval invented in 1990 [1]. It is sometimes called latent semantic indexing (LSI). ... Lojban (IPA ) is a constructed human language based on predicate logic. ... Loglan is a constructed language originally designed for linguistic research, particularly for investigating the Sapir-Whorf Hypothesis. ... In computer science, name resolution (also called name lookup) is the process of finding the entity that an identifier used in a certain context refers to. ... Transderivational search (often abbreviated to TDS) is a psychological and cybernetics term, meaning when a search is being conducted for a fuzzy match across a broad field. ... The universal translator is a fictional device common to many science fiction works, especially on television. ...

Implementations

• LinguaStream: a generic platform for Natural Language Processing experimentation
• MARF: framework for voice and statistical NLP processing

LinguaStream is a generic platform for Natural Language Processing (NLP), based on incremental enrichment of electronic documents. ... Modular Audio Recognition Framework (MARF) is a research platform and a collection of voice/sound/speech/text and natural language processing (NLP) algorithms written in Java and arranged into a very modular and extensible framework facilitating addition of new algorithms. ...

External links

The external links in this article may not comply with Wikipedia's content policies. Please improve this article by removing excessive or inappropriate external links.

Image File history File links Broom_icon. ...

Resources

• Stanford List of Statistical NLP Links
• Resources for Text, Speech and Language Processing
• A comprehensive list of resources, classified by category
• Language Technology Documentation Centre in Finland (FiLT)