At the beginning of the Interspace implementation, we were using a noun phrase extractor, originally developed by our close collaborators in the AI Lab in the department of MIS at the University of Arizona, and which we have named FastNPE [6] (Fast Noun Phrase Extractor). Although FastNPE has been found to run reasonably efficiently, and give results which initially appear acceptable to users of the Interspace system, in our endeavors to improve the concept space generation, several other noun phrase extractors were evaluated to see how they compared with the existing FastNPE. For the concept space generation, the terms which are extracted should be as complete and accurate as possible. FastNPE is fine-tuned for a particular subject area, each time that a concept space is being run for a particular collection of documents. It operates by using a stopword list, and this list is adjusted for a particular collection. However, if we were to have twenty collections, this system might necessitate having twenty stoplists. It would be more ideal to have a noun phrase extractor that is cross-discipline, and would not need to be fine-tuned in any way for any collection. Therefore, we needed another noun phrase extractor that would handle cross-discipline collections.

In order to evaluate other possible noun phrase extractors, we first looked to see what natural language parsers were available that we could possibly use for our concept space generation. Three were thoroughly tested and compared with FastNPE. These were NPtool [14], which is commercially available from Lingsoft in Finland; Chopper from MIT's Machine Language Understanding Group; and the AZ Phraser [13], a new parser from the MIS group at the University of Arizona. The sample set of documents used for the parser evaluation was taken from the large testbed available for the Interspace project. It included ten full-text articles from the IEEE Computer Society journals, and forty abstracts, evenly distributed among INSPEC, Compendex, CancerLit, and Patterns. This data was taken as a representative sample of the types of texts that would normally be used for concept space generation, being from professional, technical fields, and covering several disciplines.

According to Quirk et al. [8], a noun phrase typically functions as the subject, object, and complement of a clause, and as the complement of a prepositional phrase. Using this definition of a noun phrase, each phrase found in the sample texts was marked. Despite Quirk's rigid definition of a noun phrase, some flexibility had to be given to each parser and its noun phrase extraction. For example, in the simple sentence, "He has red and blue books", "red and blue books" can be interpreted as an entire noun phrase describing books, each of which is of two colors, but also, two different groups of books - "red books" and "blue books". Most automatic parsers do not yet have the capability of the second interpretation, and would also in fact leave out the first adjective, so that "blue books" and its shorter phrase, "books", would be the only terms extracted. Therefore, when evaluating the parsers, none was penalized for not including the longest phrase in such cases.

2.1. FastNPE

In order to extract terms from a text document, FastNPE [6] operates by using a stopword list and a stemlist, combining these lists, and comparing the final list of words with all of the words found in the document. The stopword list contains words typically found in standard stopword lists, such as "a", "the", "by", or "to". It also contains almost 3,500 verbs, adverbs, and adjectives. The stemlist, which is a much shorter list, includes suffixes for verbs and adjectives, such as -ing, -es, or -ly. Each word found in the combined list is "removed" from the document, and the remaining words or phrases in the document are each assumed to be valid terms for concept space generation. From the remaining terms, multi-word terms are further processed to extract the various shorter terms that are contained within the longest term. Figure 2 shows the result of an example sentence processed by FastNPE.

HSNs dorsally placed

abnormal dorsally placed HSNs

abnormal positions e.g

anteriorally head

distal placed HSNs

distal tip positions

dorsally tip

Figure 2: Phrases extracted by FastNPE from the sample sentence, "This results in some very abnormal positions (e.g. anteriorally and dorsally placed HSNs, or distal tip cells in the head)."

NPtool [14] was specifically designed as a noun phrase extractor. It has two main operations, the first being where each term of the text is given a context-free description and part-of-speech tag, or tags, and the second where the actual noun phrases are output. Testing was undertaken by electronic mail, using an automatic program that Lingsoft has made available for users to evaluate NPtool.

(this <*> PRON DEM SG @NH)

(result <SV> <P/in> V PRES SG3 VFIN @V)

(in PREP @AH)

(some <Quant> DET CENTRAL SG/PL @>N)

(very ADV AD-A> @AH)

(abnormal A ABS @>N)

(position N NOM PL @NH)

lparen

(e.g. ADV ADVL @AH)

(anteriorally <?> <Nominal> A ABS @NH)

(anteriorally <?> ADV @AH)

(and CC @CC)

(dorsal <DER:ly> ADV @AH)

(place <SVO> <SV> PCP2 (:OR @>N @V))

(hsns <*> <?> <NoBaseformNormalisation> N NOM SG/PL @NH)

comma

(or CC @CC)

(distal A ABS @>N)

(tip N NOM SG @>N)

(cell N NOM PL @NH)

(in PREP @AH)

(the <Def> DET CENTRAL ART SG/PL @>N)

(head N NOM SG/PL @NH)

rparen

fullstop

An example of the tagging, on the sample sentence from Figure 2, is shown in Figure 3. The second operation of NPtool is where unacceptable or illegitimate tags are eliminated, resulting in the final output which is made up of two lists of noun phrases which are marked either "ok" or "?". The second pass runs in two parallel stages, a NP-friendly parser, and a NP-hostile parser. The results of these two parses are subsequently intersected, and the "ok" noun phrases are those where both parses agree, while those phrases marked "?" are for cases where the two parsing stages did not concur, normally where there was ambiguity in a particular phrase of the text. For example, in the example sentence where "anteriorally" is given two tags (see Figure 3), a choice would have to be made whether or not to keep it as part of a noun phrase. The final list of extracted noun phrases is shown in Figure 4.

ok: tip cell

ok: position

ok: hsns

ok: head

ok: distal tip cell

ok: cell

ok: abnormal position

?: placed hsns

2.3. Chopper

Chopper, developed by Dr Ken Haase at MIT, will parse a text, breaking it down into constituent sentences or phrases. The input document can be sent to the parser through MIT's World-Wide Web page. The output text is received back in sentence-reverse order, each term of the text also having been tagged with its part-of-speech tag. Figure 5 shows the example sentence (from Figure 2), having been processed by Chopper. The sentence has been broken down into two phrases, and the output is in reverse order of the phrases. In cases where a word might belong to two phrases, the word will be repeated in the output (see lines 1 and 2 in the Figure).

Figure 5: Output from Chopper

2.4. AZ Phraser

The University of Arizona has been striving to improve the existing method of generating noun phrases, and has developed a new parser, which is known as the AZ Phraser [13]. The Phraser is made up of three parts. Firstly, the text is tokenized, processing the texts to check for items such as punctuation which is adjacent to text words, and to separate irrelevant punctuation marks from the actual text of the document. Next, each word of the text is tagged with a part-of-speech, using the tagger developed by Dr. Eric Brill [1], [2]. Finally, using a set of grammatical rules for noun phrases, a list of noun phrases is output. The noun phrase rules used at this point, were those also used by NPtool in its "NP-friendly" parser, and are listed in [14]. Figure 6 shows the terms extracted from the sample sentence by the AZ Phraser.

results HSNs

abnormal positions distal tip cells

e.g head

2.5. Evaluation of Term Extraction

As well as actual term extraction, there are a number of other processes, which must be undertaken to generate a concept space, and these are discussed further in Section 4. However, for the generation of concept spaces, it has been found that the term extraction takes up the longest amount of time of these processes. As its name implies, FastNPE has been found to be quite efficient in terms of processing speed. Term extraction from SGML-tagged full-text articles from several IEEE magazines, such as "Computer", and "Annals of the History of Computing", was considerably faster than NPtool, as shown in Figure 7.

Despite the efficiency of FastNPE in terms of processing speed, it is apparent that many of the phrases that are extracted are not correct noun phrases. In previous experiments, and depending on the type of text, this noise was removed by editing stopword lists. This has meant having professionals from a particular field of study check the stop lists to see if they are appropriate. However, as the amount of documents in the collections grows, it would be preferable to automate the entire process of generating the phrases, and not have to do any manual checking.

The noun phrases extracted by each parser were compared against the marked phrases in each document. During the evaluation of the parsers on our texts, a number of points arose. Firstly, each text document must be tokenized correctly before the noun phrases are extracted. In pre-processing of a text, NPtool tokenizes much of the text, as does the AZ Phraser, but Chopper did not appear to tokenize as efficiently. Tokenization is a particularly important issue for the types of texts that are used for concept space generation. For example, in biology texts, which might discuss "c.elegans", if that term were tokenized incorrectly to "c" and "elegans", the organism name has been destroyed.

Another important issue is normalization of the texts, where the root form of a word is extracted, or words which were capitalized because they were at the beginning of sentence would be changed to lower case. NPtool normalizes the text entirely, changing everything to lower case, and also outputting all nouns to their singular form, and other parts of speech such as verbs to their root form. This is acceptable most of the time, but for acronyms, which should not be changed to lower case, it causes a problem. Chopper does not normalize texts in any way, although for some terms, it attempts to also output the normalized form of a word in parentheses after the part-of-speech tag. The AZ Phraser does not currently normalize the texts, but it is understood that there are plans to include normalization in future development.

Using well-known terms taken from information retrieval literature, the parsers were evaluated using "recall" and "precision" measures. For the purposes of the evaluation, recall was defined to be the number of noun phrases correctly identified by the parser, divided by the number of actual noun phrases. Precision was taken to be the number of words, which were identified as nouns by the parser, divided by the total number of nouns identified in the document.

As can be seen in Figure 8, NPtool was found to have the best overall recall and precision. Consequently, it was chosen to extract noun phrases for concept space generation in the Interspace. However, the main disadvantage with NPtool is that it is a commercial system, and its source code is not available, although a binary version is sold on a year by year basis for research purposes. The AZ Phraser showed great potential for development and use in generating good noun phrases with minimal noise in the output phrases. While it was not ready for production use this year, with some further development, it can be improved to a point where it can be used instead of NPtool. Using NPtool, or the AZ Phraser, will allow generation of concept spaces for universal subject areas without the user having to adjust stop lists manually in the future.

As shown in Figure 7, NPtool is considerably slower than FastNPE. As a result, it was decided to give the user the option of saving processing time, when correctness of extracted phrases is not as important, and to have both FastNPE and NPtool available to the user who must ultimately decide which one to use. Both parsers were included in the CE module, which is described in the following sections.

3. Concept Extractor

The ultimate goal of the Concept Extractor is to extract concepts by subject, and media type, such as text, image, and audio. Thus far, the Concept Extractor (CE) has been implemented fully for text collections. It has been tested on much of the text collections available to the Interspace project. In the future, it will be implemented for image and other media. In Section 5, we have included some discussion of how we are planning to implement concept extraction for image collections. In this section, we will be discussing implementation of the Concept Extractor, shown in Figure 9, specifically for text collections.

The main task of the CE is to extract concepts from documents, and to then create a concept space, which is a critical part of the Interspace. Each document from a collection, such as text, image, or audio, is considered to be a class of source unit. When a document, or source unit, is about to be processed by the CE, the user will have already specified the document attributes in an earlier module of the Interspace. The attributes of a source unit include Type, Policy and Setting. Type specifies the format of a source unit, for example, in the case of text documents, SGML, HTML. If the source unit were image, the format might be gif, tif or jpeg. The Policy specifies the media parser for a particular source unit. A Policy sets the media parser for a source unit, according to its format type. In addition, a Policy also specifies which parts, or fields, such as title, abstract, or author, etc., of a document would be useful for the concept extraction and computation, and the names of these fields are saved into a list. This information will be pertinent for different types of user.

The Setting specifies values for the extraction of concepts and computation of concept space. These values include document collection size, maximum concept size, option to create new concepts, quality, and so on. Setting the collection size is beneficial in helping the Concept Extractor determine an optimal result set. Maximum concept size is used to determine the maximum size (length, in the case of text) of the extracted concept. If the current source unit is a text document, then Quality will be used to specify the quality of the noun phrase extractor - FastNPE, or NPtool. The final output of the Concept Extractor includes a list of concepts.

3.1. Concept Extraction in Text Documents

In order to process the document source unit, several functions have been implemented. The basic process is as shown in the diagram in Figure 10. According to the Policy, the system will call the appropriate media parser to pre-process the source unit. In the case of the media parser for text source units, the main function is to convert documents from a particular format, such as an SGML-tagged document, into a clear raw text. At the same time, the document is divided into several parts and saved into a list of parse nodes.

The next step is to extract noun phrases from the list of fields according to the Setting. In the Setting of the source unit, the user will specify the Quality required from the noun phrase extractor, and the CE will call the corresponding extractor according to the level of quality desired. For higher values, NPtool will be called. In addition to the extracted noun phrases, FastNPE outputs the frequency of each noun phrase in a document. NPtool does not automatically count the frequency of occurrence of the phrases extracted, so a separately developed function has been implemented for that purpose (see Section 4.3). The final output is a list of noun phrases and their frequency of occurrence.

The final step in this process is the actual concept extraction, which is done by the concept extractor. The system retains a list of global concepts, which is compared with the list of extracted noun phrases. If a noun phrase is found in the global concept list, it will be saved in the extracted concept list of the current source unit. If it is not found, a new concept will be created for it, or it will be inserted into a noun phrase list. This is determined by the value of the option Create in the setting of the current source unit. At this stage, the source unit will get a list of concepts, and a noun phrase list. The list of concepts is used for the final computation of the concept space.

4. CONCEPT EXTRACTION Development

The development of the CE involved much experiment and testing on collections. Based on experience during this development phase, the decisions for concept extraction discussed in the following sections were made.

Figure 10: The CE Process

4.1. Field Names

For text documents, when the media type is being parsed, not all fields are parsed fully. Firstly, the field names are specified in the policy as a list of strings, which is fixed for each Policy class. For example, for SGMLPolicy, the field list includes title, author, keyword (or thesaurus term), abstract, body and citation. For HTMLPolicy, only the title and body fields are kept. The fields that are kept is determined by the format of the documents in a particular collection, taking note of the field tags, for example, SGML tags such as <ti>, or <au>. While testing the Concept Extractor, several concept spaces were created, based on the different field tags. It has been found, from valuable user feedback, that some fields are more useful to the computation of concept space than others. Even within one field, different parts can have different effects on the quality of the concept space. For example, in the citation field, the title of the cited references are retained, but no author or source journal name is kept.

4.2. Thesaurus Terms

When the noun phrase extraction process is being run, rather than extracting any phrases from the author fields, or the thesaurus terms, these terms are automatically retained. For the author field, it is intuitively obvious that an author name is also a noun phrase. It saves some processing time by not running a noun phrase extractor on author names. For thesaurus terms, we know that some terms, such as "object-oriented", or "real-time" (from the INSPEC thesaurus) are not actual noun phrases. If the noun phrase extractor were to be run on such phrases, they would not appear in the noun phrase list, yet they are evidently useful to generate a good concept. Therefore, the concept space will be more useful to the user if such phrases are kept, and no noun phrase extraction on such terms will save processing time and computation.

4.3. Noun Phrase Frequency

The definition of a concept for an image collection is analogous to that for a text document collection. Just as in a text document, an image is a source unit processed by the CE. Instead of a set of noun phrases, however, the concepts for an image are a set of objects, which have been identified using both manual and automatic techniques. In the same sense that a concept (noun phrase) might include several words, each concept (object) in an image will include a set of visual features, such as the RGB values for color and coarseness, contrast, and directionality for texture. All of these values will be stored as a feature vector associated with each concept.

The nature of the concepts and their associated feature vectors are related to the domain of the image collection. We are currently working with a collection of aerial photos, which includes approximately 11K US aerial photos at the University of California at Santa Barbara Map and Imagery Library. Each photo is about 55 MBs in size, with 6224-by-7687 pixels, 1-meter ground resolution, and is in JPEG PBMT storage, based on 1983 standards. At 1-meter resolution, fine-grained geo-concepts such as houses, schools, factories, or parks, can be easily identified. The images will be segmented into feature regions containing texture tiles. Whereas text collections are segmented according to terms, based on noun phrases, image collections are segmented according to textures, or objects, based on orientation on pixel densities.

The concept extraction process for images is summarized as follows. Firstly, a concept (object) list is created manually. This step is to identify representative objects, which will form a part of the object list. Next, the visual feature vectors for each representative object must be computed, and these features are then linked with the location of the object in the image. The object list is stored for later use in object filtering of the actual images.

After this process, concepts are automatically extracted from images based on the object list created in the first step (described above). Each image is segmented into its constituent objects automatically using segmentation routines. The feature vectors of each such extracted object and its coordinates in the image are then saved. Next, each such extracted object is compared with the representative objects in the object list created at the beginning. This comparison consists of a calculation of the difference between two feature vectors. The extracted object is identified with the representative object to which it is most similar. This results in a list of concepts (objects) which have been extracted, identified and located in a given image. This list of objects with its location information will be used later to compute a Concept Space based on object proximity in the image. We will then have Concept Spaces for images, as well as for text documents.

The Concept Extractor has been applied to text documents, and is fully operational. It will shortly be implemented for image documents. We are optimistic that generic extraction procedures can successfully transform real-world heterogeneous objects into concepts. In the next few years, we plan to show that such procedures will scale across subject domains and media types across a wide variety of real-world materials. Then it will be possible to build the Interspace, where users interact directly with spaces of concepts and categories, which are generated automatically from the normalized concepts produced by the extraction procedures. This new level of functionality will help bring information analysis to the Net.

ACKNOWLEDGEMENTS

This work is supported by the National Science Foundation, under NSF Cooperative Agreement No. IRI 94-11318. The authors would like to thank their colleagues at the AI Lab, Dept of MIS at the University of Arizona, Dr Hsinchun Chen, Dorbin Ng, and Kristin Tolle. They also would like to particularly thank Dr William M. Pottenger for his useful comments and help in preparing this paper.

 

References