Information retrieval

Information retrieval systems (irs) are designed to search for relevant information in large documentary databases. This information can be of various kinds, with the queries ranging from “Find all the documents containing the word conjugar” to “Find information on the conjugation of Spanish verbs”. Accordingly, various systems use different methods of search.

The earliest irss were developed to search for scientific articles on a specific topic. Usually, the scientists supply their papers with a set of keywords, i.e., the terms they consider most important and relevant for the topic of the paper. For example, español, verbos, subjuntivo might be the keyword set of the article “On means of expressing unreal conditions” in a Spanish scientific journal.

These sets of keywords are attached to the document in the bibliographic database of the irs, being physically kept together with the corresponding documents or separately from them. In the simplest case, the query should explicitly contain one or more of such keywords as the condition on what the article can be found and retrieved from the database. Here is an example of a query: “Find the documents on verbos and español”. In a more elaborate system, a query can be a longer logical expression with the operators and, or, not, e.g.: “Find the documents on (sustantivos or adjetivos) and (not inglés)”.

Nowadays, a simple but powerful approach to the format of the query is becoming popular in irss for non-professional users: the query is still a set of words; the system first tries to find the documents containing all of these words, then all but one, etc., and finally those containing only one of the words. Thus, the set of keywords is considered in a step-by-step transition from conjunction to disjunction of their occurrences. The results are ordered by degree of relevance, which can be measured by the number of relevant keywords found in the document. The documents containing more keywords are presented to the user first.

In some systems the user can manually set a threshold for the number of the keywords present in the documents, i.e., to search for “at least m of n” keywords. With m = n, often too few documents, if any, are retrieved and many relevant documents are not found; with m = 1, too many unrelated ones are retrieved because of a high rate of false alarms.

Usually, recall and precision are considered the main characteristics of irss. Recall is the ratio of the number of relevant documents found divided by the total number of relevant documents in the database. Precision is the ratio of the number of relevant documents divided by the total number of documents found.

It is easy to see that these characteristics are contradictory in the general case, i.e. the greater one of them the lesser another, so that it is necessary to keep a proper balance between them.

In a specialized irs, there usually exists an automated indexing subsystem, which works before the searches are executed. Given a set of keywords, it adds, using the or operator, other related keywords, based on a hierarchical system of the scientific, technical or business terms. This kind of hierarchical systems is usually called thesaurus in the literature on irss and it can be an integral part of the irs. For instance, given the query “Find the documents on conjugación,” such a system could add the word morfología to both the query and the set of keywords in the example above, and hence find the requested article in this way.

Thus, a sufficiently sophisticated irs first enriches the sets of keywords given in the query, and then compares this set with the previously enriched sets of keywords attached to each document in the database. Such comparison is performed according to any criteria mentioned above. After the enrichment, the average recall of the irs system is usually increased.

Recently, systems have been created that can automatically build sets of keywords given just the full text of the document. Such systems do not require the authors of the documents to specifically provide the keywords. Some of the modern Internet search engines are essentially based on this idea.

Three decades ago, the problem of automatic extraction of keywords was called automatic abstracting. The problem is not simple, even when it is solved by purely statistical methods. Indeed, the most frequent words in any business, scientific or technical texts are purely auxiliary, like prepositions or auxiliary verbs. They do not reflect the essence of the text and are not usually taken for abstracting. However, the border between auxiliary and meaningful words cannot be strictly defined. Moreover, there exist many term-forming words like system, device, etc., which can seldom be used for information retrieval because their meaning is too general. Therefore, they are not useful for abstracts.

The multiplicity of irss is considered now as an important class of the applied software and, specifically, of applied linguistic systems. The period when they used only individual words as keys has passed. Developers now try to use word combinations and phrases, as well as more complicated strategies of search. The limiting factors for the more sophisticated techniques turned out to be the same as those for grammar and style checkers: the absence of complete grammatical and semantic analysis of the text of documents. The methods used now even in the most sophisticated Internet search engines are not efficient for accurate information retrieval. This leads to a high level of information noise, i.e., delivering of irrelevant documents, as well as to the frequent missing of relevant ones.

The results of retrieval operations directly depend on the quality and performance of the indexing and comparing subsystems, on the content of the terminological system or the thesaurus, and other data and knowledge used by the system. Obviously, the main tools and data sets used by an irs have the linguistic nature.

Topical summarization

In many cases, it is necessary to automatically determine what a given document is about. This information is used to classify the documents by their main topics, to deliver by Internet the documents on a specific subject to the users, to automatically index the documents in an irs, to quickly orient people in a large set of documents, and for other purposes.

Such a task can be viewed as a special kind of summarization: to convey the contents of the document in a shorter form. While in “normal” summarization by the contents the main ideas of the document are considered, here we consider only the topics mentioned in the document, hence the term topical summarization.

Figure III.3. Classifier program determines the main topics of a document.

As an example, let us consider the system Clasitex™ that automatically determines the main topics of a document. A variant of its implementation, Classifier™, was developed in the Center of Computing Research, National Polytechnic Institute at Mexico City [46] (see Figure III.3). It uses two kinds of linguistic information:

       First, it neutralizes morphologic variations in order to reduce any word found in the text to its standard (i.e., dictionary) form, e.g., oraciones  oración, regímenes  régimen, lingüísticas  lingüístico, propuesto  proponer.

       Second, it puts into action a large dictionary of thesaurus type, which gives, for each word in its standard form, its corresponding position in a pre-defined hierarchy of topics. For example, the word oración belongs to the topic lingüística, which belongs in turn to the topic ciencias sociales, which in its turn belongs to the topic ciencia.

Then the program counts how many times each one of these topics occurred in the document. Roughly speaking, the topic mentioned most frequently is considered the main topic of the document. Actually, the topics in the dictionary have different weights of importance [43, 45], so that the main topic is the one with the greatest total weight in the document.

Applied linguistics can improve this method in many possible ways. For example, in its current version, Clasitex does not count any pronouns found in the text, since it is not obvious what object a personal pronoun such as él can refer to.

What is more, many Spanish sentences contain zero subjects, i.e. implicit references to some nouns. This becomes obvious in English translation: Hay un libro. Es muy interesante  There is a book. It is very interesting  El libro es muy interesante. Thus, each Spanish sentence without any subject is implicitly an occurrence of the corresponding word, which is not taken into account by Clasitex, so that the gathered statictics is not completely correct.

Another system, TextAnalyst, for determining the main topics of the document and the relationships between words in the document was developed by MicroSystems, in Russia (see Figure III.4). This system is not dictionary-based, though it does have a small dictionary of stop-words (these are prepositions, articles, etc., and they should not be processed as meaningful words).

This system reveals the relationships between words. Words are considered related to each other if they co-occurred closely enough in the text, e.g., in the same sentence. The program builds a network of the relationships between words. Figure III.4 shows the most important words found by TextAnalyst in the early draft of this book, and the network of their relationships.

As in Clasitex, the degree of importance of a word, or its weight, is determined in terms of its frequency, and the relationships between words are used to mutually increase the weights. The words closely related to many of the important words in the text are also considered important.

Figure III.4. TextAnalyst program reveals the relationships between words.

In TextAnalyst, the list of the important words is used for the following tasks:

       Compression of text by eliminating the sentences or paragraphs that contain the minimal number of important words, until the size of the text reaches the threshold selected by the user,

       Building hypertext by constructing mutual references between the most important words and from the important words to others to which they are supposedly related.

The TextAnalyst technology is based on a special type of a dynamic neural network algorithm. Since the Clasitex program is based on a large dictionary, it is a knowledge-based program, whereas TextAnalyst is not.

Automatic translation

Translation from one natural language to another is a very important task. The amount of business and scientific texts in the world is growing rapidly, and many countries are very productive in scientific and business domains, publishing numerous books and articles in their own languages. With the growth of international contacts and collaboration, the need for translation of legal contracts, technical documentation, instructions, advertisements, and other texts used in the everyday life of millions of people has become a matter of vital importance.

The first programs for automatic, or machine, translation were developed more than 40 years ago. At first, there existed a hope that texts could be translated word by word, so that the only problem would be to create a dictionary of pairs of words: a word in one language and its equivalent in the other. However, that hope died just after the very first experiments.

Then the ambitious goal was formulated to create programs which could understand deeply the meaning of an arbitrary text in the source language, record it in some universal intermediate language, and then reformulate this meaning in the target language with the greatest possible accuracy. It was supposed that neither manual pre-editing of the source text nor manual post-editing of the target text would be necessary. This goal proved to be tremendously difficult to achieve, and has still not been satisfactorily accomplished in any but the narrowest special cases.

At present there is a lot of translation software, ranging from very large international projects being developed by several institutes or even several corporations in close cooperation, to simple automatic dictionaries, and from laboratory experiments to commercial products. However, the quality of the translations, even for large systems developed by the best scientists, is usually conspicuously lower than the quality of manual human translation.

As for commercial translation software, the quality of translation it generates is still rather low. A commercial translator can be used to allow people quite unfamiliar with the original language of the document to understand its main idea. Such programs can help in manual translation of texts. However, post-editing of the results, to bring them to the degree of quality sufficient for publication, often takes more time than just manual translation made by a person who knows both languages well enough.^[4] Commercial translators are quite good for the texts of very specific, narrow genres, such as weather reports. They are also acceptable for translation of legal contracts, at least for their formal parts, but the paragraphs specifying the very subject of the contract may be somewhat distorted.

To give the reader an impression of what kind of errors a translation program can make, it is enough to mention a well-known example of the mistranslation performed by one of the earliest systems in 1960s. It translated the text from Bible The spirit is willing, but the flesh is weak (Matt. 26:41) into Russian and then back into English. The English sentence then turned out to be The vodka is strong, but the meat is rotten [34]. Even today, audiences at lectures on automatic translation are entertained by similar examples from modern translation systems.

Two other examples are from our own experience with the popular commercial translation package PowerTranslator by Globalink, one of the best in the market. The header of an English document Plans is translated into Spanish as the verb Planifica, while the correct translation is the Spanish noun Planes (see Figure III.5). The Spanish phrase el papel de Francia en la guerra is translated as the paper of France in the war, while the correct translation is the role of France in the war. There are thousands of such examples, so that nearly any automatically translated document is full of them and should be reedited.

Figure III.5. One of commercial translators.

Actually, the quality of translation made by a given program is not the same in the two directions, say, from English to Spanish and from Spanish to English. Since automatic analysis of the text is usually a more difficult task than generation of text, the translation from a language that is studied and described better has generally higher quality than translation into this language. Thus, the elaboration of Spanish grammars and dictionaries can improve the quality of the translation from Spanish into English.

One difficult problem in automatic translation is the word sense disambiguation. In any bilingual dictionary, for many source words, dozens of words in the target language are listed as translations, e.g., for simple Spanish word gato: cat, moneybag, jack, sneak thief, trigger, outdoor market, hot-water bottle, blunder, etc. Which one should the program choose in any specific case? This problem has proven to be extremely difficult to solve. Deep linguistic analysis of the given text is necessary to make the correct choice, on the base on the meaning of the surrounding words, the text, as a whole, and perhaps some extralinguistic information [42].

Another, often more difficult problem of automatic translation is restoring the information that is contained in the source text implicitly, but which must be expressed explicitly in the target text. For example, given the Spanish text José le dio a María un libro. Es interesante, which translation of the second sentence is correct: He is interesting, or She is interesting, or It is interesting, or This is interesting? Given the English phrase computer shop, which Spanish translation is correct: tienda de computadora or tienda de computadoras? Compare this with computer memory. Is they are beautiful translated as son hermosos or son hermosas? Is as you wish translated as como quiere, como quieres, como quieren, or como queréis?^[5] Again, deep linguistic analysis and knowledge, rather than simple word-by-word translation, is necessary to solve such problems.

Great effort is devoted in the world to improve the quality of translation. As an example of successful research, the results of the Translation group of Information Science Institute at University of South California can be mentioned [53]. This research is based on the use of statistical techniques for lexical ambiguity resolution.

Another successful team working on automatic translation is that headed by Yu. Apresian in Russia [34]. Their research is conducted in the framework of the Meaning  Text model.

Natural language interface

The task performed by a natural language interface to a database is to understand questions entered by a user in natural language and to provide answers—usually in natural language, but sometimes as a formatted output. Typically, the entered queries, or questions, concern some facts about data contained in a database.

Since each database is to some degree specialized, the language of the queries and the set of words used in them are usually very limited. Hence, the linguistic task of grammatical and semantic analysis is much simpler than for other tasks related to natural language, such as translation.

There are some quite successful systems with natural language interfaces that are able to understand a very specialized sublanguage quite well. Other systems, with other, usually less specialized sublanguages, are much less successful. Therefore, this problem does not have, at least thus far, a universal solution, most of the solutions being constructed ad hoc for each specific system.

The developers of the most popular database management systems usually supply their product with a formal query-constructing language, such as sql. To learn such a language is not too difficult, and this diminishes the need for a natural language interface. We are not aware of any existing commercial interface system that works with a truly unlimited natural language.

Nevertheless, the task of creating such an interface seems very attractive for many research teams all over the world. Especially useful could be natural language interfaces with speech recognition capabilities, which also would allow the user to make queries or give commands over a telephone line.

The task of development of natural language interfaces, though being less demanding to such branches of linguistics as morphology or syntax, are very demanding to such “deeper” branches of linguistics as semantics, pragmatics, and theory of discourse.

The specific problem of the interface systems is that they work not with a narrative, a monologue, but with a dialogue, a set of short, incomplete, interleaving remarks. For example, in the following dialogue:

User:      Are there wide high-resolution matrix printers in the store?

System:   No, there are no such printers in the store.

User:      And narrow?

it is difficult for the computer to understand the meaning of the last remark.

A rather detailed linguistic analysis is necessary to re-formulate this user’s question to Are there narrow high-resolution matrix printers in the store? In many cases, the only way for the computer to understand such elliptical questions is to build a model of the user’s current goals, its knowledge, and interests, and then try to guess what the computer itself would be asking at this point of the dialogue if it were the user, and in what words it would formulate such a question. This idea can be called analysis through synthesis.

Extraction of factual data from texts

Extraction of factual data from texts is the task of automatic generation of elements of a factographic database, such as fields, or parameters, based on on-line texts. Often the flows of the current news from the Internet or from an information agency are used as the source of information for such systems, and the parameters of interest can be the demand for a specific type of a product in various regions, the prices of specific types of products, events involving a particular person or company, opinions about a specific issue or a political party, etc.

The decision-making officials in business and politics are usually too busy to read and comprehend all the relevant news in their available time, so that they often have to hire many news summarizers and readers or even to address to a special information agency. This is very expensive, and even in this case the important relationships between the facts may be lost, since each news summarizer typically has very limited knowledge of the subject matter. A fully effective automatic system could not only extract the relevant facts much faster, but also combine them, classify them, and investigate their interrelationships.

There are several laboratory systems of that type for business applications, e.g., a system that helps to explore news on Dow Jones index, investments, and company merge and acquisition projects. Due to the great difficulties of this task, only very large commercial corporations can afford nowadays the research on the factual data extraction problem, or merely buy the results of such research.

This kind of problem is also interesting from the scientific and technical point of view. It remains very topical, and its solution is still to be found in the future. We are not aware of any such research in the world targeted to the Spanish language so far.

Text generation

The generation of texts from pictures and formal specifications is a comparatively new field; it arose about ten years ago. Some useful applications of this task have been found in recent years. Among them are multimedia systems that require a text-generating subsystem to illustrate the pictures through textual explanations. These subsystems produce coherent texts, starting from the features of the pictures.

Another very important application of systems of this kind is the generation of formal specifications in text form from quite formal technical drawings.

For example, compilation of a patent formula for a new device, often many pages long, is a boring, time-consuming, and error-prone task for a human. This task is much more suitable for a machine.

A specific type of such a system is a multilingual text generating system. In many cases, it is necessary to generate descriptions and instructions for a new device in several languages, or in as many languages as possible.

Due to the problems discussed in the section on translation, the quality of automatic translation of a manually compiled text is often very low.

Better results can be achieved by automatic generation of the required text in each language independently, from the technical drawings and specifications or from a text in a specific formal language similar to a programming language.

Text generating systems have, in general, half of the linguistic problems of a translation system, including all of the linguistic problems connected with the grammar and lexicon of the target language. This is still a vast set of linguistic information, which is currently available in adequate detail for only a few very narrow subject areas.

Systems of language understanding

Natural language understanding systems are the most general and complex systems involving natural language processing. Such systems are universal in the sense that they can perform nearly all the tasks of other language-related systems, such as grammar and style checking, information retrieval, automatic translation, natural language interface, extraction of factual data from texts, text generation, and so forth.

For example, automatic translation can be implemented as a text understanding system, which understands the text in the source language and then generates a precise description of the learned information in the target language.

Hence, creation of a text understanding system is the most challenging task for the joint efforts of computational linguistics and artificial intelligence.

To be more precise, the natural language processing module is only one part of such a system. Most activities related to logical reasoning and understanding proper are concentrated in another its part—a reasoning module. These two modules, however, are closely interrelated and they should work in tight cooperation.

The linguistic subsystem is usually bi-directional, i.e., it can both “understand,” or analyze, the input texts or queries, and produce, or generate, another text as the answer. In other words, this subsystem transforms a human utterance into an internal, or semantic, representation comprehensible to the reasoning subsystem, produces a response in its own internal format, and then transforms the response into a textual answer.

In different systems, the reasoning subsystem can be called the knowledge-based reasoning engine, the problem solver, the expert system, or something else, depending on the specific functions of the whole system. Its role in the whole system of natural language understanding is always very important.

Half a century ago, Alan Turing suggested that the principal test of intelligence for a computer would be its ability to conduct an intelligent dialogue, making reasonable solutions, giving advice, or just presenting the relevant information during the conversation.

This great goal has not been achieved thus far, but research in this direction has been conducted over the past 30 years by specialists in artificial intelligence and computational linguistics.

In order to repeat, the full power of linguistic science and the full range of linguistic data and knowledge are necessary to develop what we can call a true language understanding system.

Related systems

There are other types of applications that are not usually considered systems of computational linguistics proper, but rely heavily on linguistic methods to accomplish their tasks. Of these we will mention here two, both related to pattern recognition.

Optical character recognition systems recognize the graphemes, i.e., letters, numbers, and punctuation marks, in a point-by-point image of an arbitrary text printed on paper, and convert them to the corresponding ascii codes. The graphemes can be in any font, typeface or size; the background of the paper can contain some dots and spots. An example of what the computer sees is given in Figure III.6.

A human being easily reads the following text Reglas de interpretación semántica:  because he or she understands the meaning of the words. However, without understanding the meaning it is not possible to recognize, say, the first letter of the last string (is it a, s or g?), or the first letter(s) of the second line (is it r, i or m?).

Figure III.6. The image of a text, as the computer sees it. Figure III.7. Several letters of the same text, as the computer sees them.

The first letters of the second line are shown separately in Figure III.7. One who does not know what the whole word means, cannot even say for sure that this picture represents any letters. However, one can easily read precisely the same image, shown above, of the same letters in their complete context. Hence, it is obvious that the task of optical character recognition cannot be solved only by the methods of image recognition, without linguistic information.

The image recognition proper is beyond the competence of computational linguistics. However, after the recognition of an image even of much higher quality than the one shown in Figure III.6, some peculiar errors can still appear in the textual representation of the image. They can be fixed by the operations similar to those of a spell checker. Such a specialized spell checker should know the most frequent errors of recognition. For example, the lower-case letter l is very similar to the figure 1, the letter n is frequently recognized as the pair ii, while the m can be recognized as iii or rn. Vice versa, the digraphs in, rn and ni are frequently recognized as m, and so forth.

Most such errors can be corrected without human intervention, on the base of linguistic knowledge. In the simplest case, such knowledge is just a dictionary of words existing in the language. However, in some cases a deeper linguistic analysis is necessary for disambiguation. For example, only full parsing of the context sentence can allow the program to decide whether the picture recognized as *danios actually represents the existing Spanish words darnos or damos.

A much more challenging task than recognition of printed texts is handwriting recognition. It is translation into ascii form of the texts written by hand with a pen on paper or on the surface of a special computer device, or directly with a mouse on the computer screen. However, the main types of problem and the methods of solution for this task are nearly the same as for printed texts, at least in their linguistic aspect.

Speech recognition is another type of recognition task employing linguistic methods. A speech recognition system recognizes specific sounds in the flow of a speech of a human and then converts them into ascii codes of the corresponding letters. The task of recognition itself belongs both to pattern recognition and to phonology, the science bordering on linguistics, acoustics, and physiology, which investigates the sounds used in speech.

The difficulties in the task of speech recognition are very similar or quite the same as in optical character recognition: mutilated patterns, fused patterns, disjoint parts of a pattern, lost parts of the pattern, noise superimposing the pattern. This leads to even a much larger number of incorrectly recognized letters than with optical character recognition, and application of linguistic methods, generally in the same manner, is even more important for this task.

Conclusions

A short review of applied linguistic systems has shown that only very simple tasks like hyphenation or simple spell checking can be solved on a modest linguistic basis. All the other systems should employ relatively deep linguistic knowledge: dictionaries, morphologic and syntactic analyzers, and in some cases deep semantic knowledge and reasoning. What is more, nearly all of the discussed tasks, even spell checking, have to employ very deep analysis to be solved with an accuracy approaching 100%. It was also shown that most of the language processing tasks could be considered as special cases of the general task of language understanding, one of the ultimate goals of computational linguistics and artificial intelligence.