 |
Stephen M. Nizyborski, Hsinchun Chen1, and Titus Purdin
Technological progress in areas such as microprocessor technology, secondary storage device technology, and display technologies are producing computers which are faster, more reliable, and more dazzling to the eye than until recently had been thought possible. Daily we read of advances that push the ``hottest" machines of today into seeming obsolescence by tomorrow. Local and wide area computer networks connected to internet link these machines to create vast avenues through which information can flow, while database managers and information professionals attempt to organize and store the resulting quantities of data to which today's knowledge workers have access.
This information (or knowledge) explosion has led to crucial issues that information systems professionals and researchers must face. How does one transform this overwhelming glut of data into meaningful and accessible information that is of real value in prospective actions, decisions, or research? What tools are available for intelligently exploring fact-crowded information spaces and retrieving ``chunks" of information pertinent to one's information needs?
Unfortunately, database management systems (DBMS) and information retrieval systems (IRS) are inadequate to meet these challenges. The problem with the current database technologies is that they rely on the users' abilities to manipulate the supporting information technologies, to articulate their needs precisely according to a system's requirements, and to search and filter a large amount of domain-specific information. Considering the increasingly more pressing information overload problem [2] experienced by researchers and practitioners, the cognitive demand for such document retrieval tasks is overwhelming. Only users with significant subject area, classification scheme, and subject knowledge are able to maneuver in the databases and locate information of interest to them [9].
Recently, however, the incorporation of thesaurus-like knowledge components based on artificial intelligence or knowledge-based methods have met with some success by creating a concept space of a specific subject domain which resembles a user's mental model and in which the knowledge worker may browse. Many knowledge-based information retrieval systems and commercial textual retrieval packages have begun to provide such thesaurus-browsing and concept exploration capabilities [19] [14] [11] that enable a user to refine and more accurately articulate his or her information needs, as well as find terms which will most accurately retrieve documents pertinent to specific queries. The user is not left to ``blindly" search an enormous document space in hopes of finding what is needed.
In this article we propose a prototype concept-based document retrieval system structured around a blackboard architecture and implemented with an X Window System-based graphical user interface. This system, called BIRD, incorporates three knowledge sources or thesauri which are activated by a neural net and whose iterative spreading activation behavior is dynamically displayed. This interactive hypertext system empowers users to browse in a system of document and concept spaces in an intelligent and user-friendly manner.
Several research areas are related to our work. We attempted to place our proposed design within the context of existing systems that incorporated a thesaurus or knowledge base component and therefore reviewed the use of thesauri in existing knowledge-based systems and commercial full-text retrieval systems. Because the system we proposed contained hypertext overtones, we also surveyed existing hypertext development systems, especially those based upon the X Window System.
Use of a thesaurus or knowledge base for ``intelligent'' information retrieval has drawn considerable attention from researchers in information science and computer science in recent years. There have been many attempts to capture experts' subject area knowledge for information retrieval. One example is CoalSORT [31], which facilitates the use of bibliographic databases in coal technology. A semantic network, representing an expert's domain knowledge, embodies the system's intelligence. GRANT [12], developed by Cohen and Kjeldsen, is an expert system for finding sources of funding for given research proposals. Its search method - constrained spreading activation in a semantic network - makes inferences about the goals of the user and thus finds information that the user did not explicitly request but that is likely to be useful. Shoval [37] developed an expert system for suggesting search terms. This system is composed of two components: the knowledge base, represented as a semantic network in which the nodes are words, concepts, or phrases. Links express the semantic relationships between the nodes. The second component is made up of rules, or procedures, which operate upon the knowledge base and are analogous to the decision rules or work patterns of the information specialist. Fox's CODER system [19] consists of a thesaurus that was generated from the Handbook of Artificial Intelligence and Collin's Dictionary. The ``Intelligent Intermediary for Information Retrieval'' (I3R), developed by Croft [14], consists of a group of ``experts'' that communicate via a common data structure, called the blackboard. The system consists of a user model builder, a query model builder, a thesaurus expert, a search expert (for suggesting statistics-based search strategies), a browser expert, and an explainer. Chen [9] incorporated a portion of the Library of Congress Subject Headings into the design of an intelligent retrieval system. The system adopted a branch-and-bound spreading activation algorithm to assist users in articulating their queries.
The National Library of Medicine's thesaurus projects are probably the largest-scale effort that use the knowledge in existing thesauri. In one of the projects, Rada and Martin [33] experimented with automatic addition of concepts to MeSH (Medical Subject Headings) by including the CMIT (Current Medical Information and Terminology) and SNOMED (Systematized Nomenclature of Medicine) thesauri. Access to various sets of documents can be facilitated by using thesauri and the connections that are made among thesauri. The Unified Medical Language System (UMLS) project is a long-term effort to build an intelligent automated system that understands biomedical terms and their interrelationships and uses this understanding to help users retrieve and organize information from machine-readable sources [25] [30] [27]. The UMLS includes a Metathesaurus, a Semantic Network, and an Information Sources Map. The Metathesaurus contains information about biomedical concepts and their representation in more than 10 different vocabularies and thesauri. The Semantic Network contains information about the types of terms (e.g., ``disease'', ``virus,'' etc.) in the Metathesaurus and the permissible relationships among these types. The Information Sources Map contains information about the scope, location, vocabulary, and access conditions of biomedical databases of all kinds.
Most of the knowledge bases used in these systems were either generated manually from the domain experts via the knowledge acquisition process or derived from existing thesauri (which were first created manually by indexing/subject experts). A complementary approach to manual knowledge base creation is the automatic thesaurus generation approach.
Virtually all techniques for automatic thesaurus generation are based on the statistical co-occurrence of word types in text [35] [15] [10]. Similarity coefficients are often obtained between pairs of distinct terms based on coincidences in term assignments to the documents of the collection. For example, a cosine computation can be used to generate normalized term similarities between 0 and 1. When pairwise similarities are obtained between all term pairs, an automatic term-classification process such as single-link or complete link classification can group into common classes all terms with sufficiently large pairwise similarities. The terms in the thesaurus classes can replace the initial search terms and be used to increase search recall. The automatically-generated subject-specific thesaurus can be extremely useful in capturing the specific domain knowledge in textual databases and in augmenting the subject coverage of other existing thesauri.
Most commercial full-text retrieval systems provide some thesaurus modules which are either user-defined or are extracted from existing thesaurus sources. Thesaurus modules in these systems are generally deemed useful and necessary in these commercial products. Several systems are reported in [11]. We summarize a few of them below.
Topic, developed by Verity, Inc., is unique among full-text retrieval systems in that it incorporates ``topic-based" information retrieval. Queries can be created using a tree-structured hierarchy of ``topics,'' akin to a small user-defined thesaurus. Topic captures the expertise of individuals knowledgeable about any given subject. Users define the relationships between sub-topics, words, and phrases, express the importance of each piece of evidence in the Topic Tree to the overall concept, and establish the rules for combining the weighted evidence in the Topic Tree. The user-defined Topic Trees are stored in the retrieval system. Topic also exhibits capability for including user-specified synonyms as well as external thesauri such as the Roget's Thesaurus. Users can browse the thesaurus and include related terms in their queries.
Basic/PLUS is an application development tool with a highly sophisticated query language and refined indexing that relies on the B-tree method. The thesaurus module in BASIS/PLUS performs term switching (from common search terms to preferred terms), vocabulary control, and supports the thirteen ANSI standard relationships, e.g., broader and narrower terms. The thesaurus also supports interactive dialogue in several European languages. In addition, to ensure thoroughness of retrieval, users may browse the thesauri to determine relationships associated with specific terms.
Fulcrum Ful/Text is a full-text indexing and retrieval software suited to applications involving both structured and unstructured text. It contains a library of over 100 callable routines that can be used by application developers to create their own document management environment. Elexir, developed by Third Eye Software, Inc., also provides a library of indexing, retrieval, format conversion, and interface routines that can be customized for users' applications. Both Fulcrum Ful/Text and Elexir include capabilities to incorporate an external thesaurus such as Roget's as a search aid. These systems can search the thesaurus and allow the user to draw terms from them.
Savvy was originally developed by Excalibur as a library of callable C routines. This library of neural network programs was repackaged for sale as various systems, including Savvy/TRS. With the optional Thesaurus Module, Savvy/TRS gives users the ability to use a thesaurus file to perform synonym searches. The thesaurus file can be user-created or be a public-domain thesaurus. Synonym searches provide content-based searches using one or more synonymous or associated phrases at the same time.
Most of the knowledge-based and commercial full-text retrieval systems provide only simple ways of browsing or terms search and replacement and they are also mostly based on a character-string menu interface. For query articulation and information retrieval in large-scale applications, creating more proactive (i.e., system-aided) and user-friendly (e.g., X Window-based Hypertext interface) are among the most pressing challenges for information systems designers.
As we began this project, we explored the availability of hypertext authoring systems which run under the X Window System. X Window System was chosen because of its portability and general acceptance by industrial, engineering, and scientific graphics applications. The aim of the project was to develop a prototype system that would run under the X Window on workstations. Several hypertext development environments exist for the X Window System environment. Some are commercially available, and others are either in the public domain or shareware products. These systems mostly provide a framework or structure on which to build hypertext systems. The following is a synopsis of several well-known systems that we look into.
Notecards is a hypertext development system designed as an information analyst's support tool. Notecards runs under the Medley lisp system, but is generally insulated from the underlying lisp subsystem. Its development was a result of research done at Xerox Palo Alto Research Center (PARC) several years ago [23] [22]. Notecards supports multiple windows and is fully X compatible2.
Viola is a highly manipulable interactive-media authoring tool. With this tool, users are able to create and modify hypertext objects either directly or through scripts. This system is described as the closest thing to Apple's HyperCard for the Unix/X environment3.
HyperNeWs 1.5 is an object-oriented interface development system which runs on Sun-3 and Sun-4 systems under OpenWindows 2.0. It was developed at the Turing Institute in Glasgow, Scotland and uses direct manipulation of objects for interface development. In this system, windows are represented as ``stacks,'' which consist of any number of ``cards" and ``objects.'' These stacks can have their own scripts written in postscript, or can be driven by client programs written in C, Prolog, or Lisp. The system provides a set of default objects such as menus and scrollable windows for incorporation into new systems4.
Facets by Reusable Solutions, Inc. is a package for ParcPlace Smalltalk Release 4 which includes a hypertext authoring system. It is mainly positioned as an object-oriented 4GL whose aim is the rapid construction of database entry forms. It is sold as Smalltalk source code and is therefore portable to a number of platforms, including X running in a Unix environment5.
GUIDE is a structured document browser that can handle both text and graphics. Users can expand hypertext buttons by pointing and clicking, thereby expanding the sections of the documents they wish to view. The system provides preprocessors which are able to convert conventional documents to GUIDE documents. GUIDE is a commercially available system which runs on Sun workstations and DECstations6.
While the proposed system, based upon a blackboard metaphor, will provide a semantics-rich information retrieval environment for the knowledge worker, its usability could be severely limited if the wrong interface tools were to be chosen for implementation. Since we were developing a system whose functionality was to include hypertext features, but whose architecture was based upon a blackboard model, these products did not possess the flexibility and extendibility we required. Therefore none of the hypertext systems described above was adopted as our development environment. Instead, the more flexible and portable X Window System and the Motif widget set were chosen for this project.
Because X offers a powerful and flexible development environment, we were able to equip the system with the multiple movable windows required to support hypertext functionality. The use of X allowed us to make the blackboard design graphically explicit with the help of movable, scrollable windows and push buttons. We were also able to create a real-time graphical display of the iterative spreading activation of the neural net used to activate the thesaurus component. A full description of the blackboard architecture and our system implementation can be found in the following sections.
As discussed earlier, management of the huge quantity of information available to knowledge workers is a significant problem. While information is desirable, too much information (especially ``noisy'' information) could be detrimental to an individual worker's understanding and performance [20] [2]. Information filtering, structuring, and presentation techniques are required for an effective information or document retrieval system. This section discusses some of the design considerations which we have integrated into our system to assist users in retrieving documents most relevant to their tasks. These considerations are mainly related to hypertext browsing and the blackboard architecture.
Science advisor to FDR, Vannevar Bush is credited with conceptualizing the first hypertext system. He created a browsing system based upon microfilm and photocells called Memex [5] which predated the modern digital computer. Since then, a number of hypertext systems have been conceptualized and developed.
But what exactly is ``hypertext"? Different researchers and system designers appear to have very different interpretations. Halasz defines it as a style of building information management and representation systems using typed links to create a network of nodes [22]. Smith and Weiss [38] define hypertext as a form of electronic document viewed through an interactive browser, as well as a network-based approach to information management. Booth [3] describes branching and networked hypertext as non-linear and interactive in contrast to linear and ``passive" text documents. Gygi [21] presents a humorous, but exhaustive checklist of the ``etiology of hypertext pathology, and some suggestions for a cure." Conklin [13] provides a comprehensive definition for hypertext from both a technical and a non-technical perspective. First, hypertext is (non-technically) described as a computer-based medium for thinking and communication. Secondly, and more precisely, hypertext is described as a hybrid technology which includes: (1) a database methodology allowing non-linear, non-query based direct access to text, (2) a representation scheme whose structure resembles that of a semantic net, and an (3) interface modality utilizing control buttons, windows, and task stacking.
Congruent with Conklin's definition, our system proposes to incorporate a non-linear, concept-driven database and document retrieval technology through the incorporation of a neural net activated thesaurus component which allows semantic-based access to text. This thesaurus component can be conceptualized as a semantic net which is based upon an underlying database and structured as a network of nodes and weighted links. Users will be able to traverse this network through the activation of the neural net component. And lastly, the proposed graphical user interface will provide the control buttons, multiple windows, and task-stacking functionality characteristic of hypertext systems.
After having chosen hypertext as the underlying interface, we proceeded to examine how the interface should look and be perceived by users in a concept-based document retrieval environment. It has been well documented in the human-computer interactions literature that software systems may form different mental models for users [3]. System metaphors are often adopted by software engineers to provide users with shortcuts to learning a complex system. For example, many conventional online cataloging systems were designed based on a ``tree metaphor,'' where users traverse different levels of menus in the tree and select appropriate search options (e.g., author search, subject search, ISBN search, etc.). The ``desktop computing metaphor'' is one which is in wide use today for scientific and engineering graphic applications. For a knowledge worker who needs to access a large amount of unstructured information in highly domain-specific databases, what might be a good system metaphor for their tasks? In order to answer this question, we consulted the human-computer interactions literature [6] [28] and relied upon (human) information processing theory [32].
A human being's information processing capabilities have been aptly compared to those of a computer [6] [32]. Both the human system and the computer system interact with the environment through well defined input and output channels such as the sensory and motor organs in the human, and serial and parallel ports in the computer system. Both possess a central processing unit (CPU or rational mind) to perform operations upon input or to create output. Both possess long-term memory areas which serve as permanent storage for information. Both also possess volatile short-term memory areas where information items are temporarily stored during processing. These information items find their way into short term memory through direct input, retrieval from long term memory, or as a result of the CPU's activities.
The blackboard architecture, first proposed and adopted in the HEARSAY-II natural language processing project in the 1970s [17], presents a computational model of problem solving analogous to the human information processing processes. The blackboard architecture also possesses a control module and short-term (working) and long-term memory areas, as shown in Figure 1. After HEARSAY-II the OPS5 rule-based language was developed based on the blackboard architecture and has set the standard for most expert system development tools (e.g., expert system shells) [4]. In OPS5, knowledge is represented as production rules and is ``fired'' by the working memory elements on the blackboard in an iterative process (the ``recognize-act'' cycle). Most expert systems or knowledge-based systems developed in the 1980s exhibit blackboard-like rule-based problem solving characteristics.
Since the blackboard model has been shown to adequately mirror human information acquisition and processing, we felt that it would serve as an apt metaphor for our information retrieval system design. Query articulation and information retrieval activities which are undertaken by the knowledge worker while completing a task may invoke the knowledge worker's mental model and subject knowledge. The system's knowledge sources and the searchers' intermediate queries and search results may be posted in a public blackboard area as short-term memory items. The process iterates until the retrieval session is completed.
Based on past research and our own system development experience [8] [11], we believe the ``blackboard metaphor'' is understandable and pleasingly intuitive. As other research has suggested [34], interface design should be task-oriented, not interface-oriented, meaning that an interface should be transparent to the user, allowing the focus to remain on the task, not the system interface. It is hoped that this blackboard metaphor will indeed become transparent to the user. Details of our proposed blackboard-based design for IR are presented in the next section.
The blackboard architecture has been the foundation of many knowledge-based retrieval systems such as CODER [19], I3R [14], and METACAT [8]. Knowledge sources in CODER include an external dictionary that can be invoked by users during search. I3R consists of a group of experts (e.g., thesaurus expert, search expert, browser expert, etc.) that communicate via a blackboard. In METACAT, Chen partitioned the blackboard into a document space and a concept space and incorporated a user model builder, a task model builder, an online thesaurus, a known item instantiater, a heuristic keyword searcher, and a thesaurus browser into a blackboard-based online cataloging system. These blackboard-based system design efforts have shown the feasibility and appropriateness of adopting the ``blackboard metaphor'' in knowledge-based retrieval system, especially for controlling and utilizing the multiple sources of knowledge which were incorporated into these systems.
Based upon the blackboard model, the proposed system also incorporated three components, namely, the knowledge sources, a blackboard working area, and a control module. We now describe each component in detail in the context of our implementation.
The first component of a blackboard system is the knowledge required to accomplish a task. This knowledge can be partitioned into different discrete knowledge sources, each contributing as a small ``expert" (or demon) to the solution or completion of a complex task - a task often requires the cooperative participation and involvement of individual experts. This component is analogous to the ``long-term memory" of the model human processor [6]. In a classical expert system [4], the knowledge is typically elicited from human experts, and each ``piece" of knowledge becomes a condition-action pair (or IF-THEN rule) within the system. These rules, being guided by the control module, fire based upon the condition of a global database called the blackboard, and subsequently act upon and modify this same blackboard, thereby contributing to the eventual problem solution.
In previous knowledge-based IR systems research, external thesaurus or domain-specific knowledge bases are often considered as knowledge sources which can contribute to system-aided query articulation and information retrieval. Using results from our past research [11], we incorporated three thesauri as knowledge sources in our prototype implementation. As with production rules in expert systems, these thesauri, guided by the control module and the user, will be ``activated" based on the contents in the blackboard. Users can browse or explore the domain-specific concept space which this thesaurus component offers. Each thesaurus will contribute its share of the domain knowledge to the completion of the tasks via term suggestion, query refinement, and eventual document retrieval. We summarize the three thesauri below. (Details about these thesauri can be found in [11].)
In our hypertext interface, the three thesauri were explicitly represented as icons in the main window. A user can specify which of these thesauri will be activated for his/her query during a session as well as relative weight or importance given to each activated thesaurus. In the upper right hand corner of the application's main window (shown in Figure 2) is a box containing three toggle buttons and three sliding scales. The user may select or de-select a thesaurus by clicking the pointer on its corresponding toggle button. The scale value for each sliding scale may be altered by ``grabbing" the slider mechanism with the pointer and ``dragging" it to the desired location along the scale. Each scale has a lower limit of 0 and an upper limit of 10. This value represents the relative weight for a given thesaurus to be applied during the neural net's activation process. Thus, the degree of relevance of each knowledge source to a search task can be explicitly stated by the user.
The second main component of the blackboard-based system is the control module. The control module in a typical production system is characterized by a recognize-act cycle, which allows the knowledge sources to respond ``opportunistically'' to the state of the blackboard [17] [4]. The control module ``recognizes" a match between given elements on the blackboard and the knowledge sources or rules. Based on a predetermined conflict resolution strategy (e.g., the specificity principle, the recency principle), the system then acts, or fires a rule, which in turn modifies the state of the blackboard. This process continues (cycles) until a desired stopping condition is met.
A. Browse or Activate:
Two control modules have been included in our system, namely, a browse module and an activate module. These modules can be activated by clicking the pointer on one of the two buttons in the lower right hand corner of the main window shown in Figure 2. The difference between the browse and the activate modules lies primarily in the extent of the traversal through a chosen thesaurus. The browse module traverses a distance of only one link between terms in the thesaurus and returns only those concepts which are directly connected to the initial terms. With the browse module, the thesauri can be explored in small increments, with the traversal through the knowledge sources being controlled mainly by the user. The module empowers the user to perform concept-based browsing prior to ever retrieving any actual documents. This browsing process may aid in areas such as terms matching and query refinement.
Browsing as an exploration strategy, even within a concept space such as the one we present, is not without its drawbacks. As is the case in most hypertext systems, browsing depends upon the user's mental model of the subject area and the system structure [13] [7]. This creates a cognitive overhead because of the effort required to maintain a sense of one's position within the system. As a result, users may easily become disoriented or lost in the system. Another browsing related problem is the ``Art Museum Phenomenon" [18], wherein the user spends a lot of time looking, while learning nothing specific. We attempt to address these hypertext browsing problems by means of the activate module described next.
The system's activate module allows a user to invoke selected thesauri and activate a neural net algorithm (the Hopfield net) to find relevant concepts which are multiple links away from the initial concepts. The process results in either a display of terms or documents depending upon the state of the blackboards. In contrast to the passive, one-link browse module described above, the activate module leaves the concept search and convergence task to the neural net algorithm. It returns a display of the (convergent) concepts most relevant to the initial search terms. This module thus can act as an ``intelligent assistant" to the searcher, aiding navigation through the knowledge space more effectively and purposefully than would be possible using the browse module. A summary of the neural network activation process based on the Hopfield parallel relaxation algorithm [24] [29] is presented below. A more detailed description can be found in [11].
The implementation reported below incorporated the basic Hopfield net iteration and convergence ideas. However, significant modification was also made to accommodate unique characteristics of information retrieval, e.g., asymmetric link weights and the continuous SIGMOID transformation function. Using the initial search terms provided by searchers and the association of keywords captured by the network, the Hopfield parallel relaxation algorithm activates neighboring terms, combines weighted links, performs a transformation function (a SIGMOID function, fs), and determines the outputs of newly activated nodes. The process repeats until node outputs remain unchanged with further iterations. The node outputs then represent the concepts that are strongly related to the initial search terms.
For the thesaurus generated automatically using a similarity function (i.e., the Public KB), the resulting links represent probabilistic, synaptic weights between any two concepts. For other external thesauri which contain only symbolic links (i.e., ACM CRCS and LCSH), an ad hoc procedure of assigning a probabilistic weight to each symbolic link can be adopted [11].
The ``training'' phase of the Hopfield net is completed when the weights have been computed or assigned. tij represents the ``synaptic'' weight from node i to node j.
An initial set of search terms, provided by the searcher, serves as the input pattern. Each node in the network which matches the search terms is initialized (at time 0) to have a weight of 1.
,
is the output of node
i at time t and xi which has a value between 0 and 1, indicates
the input pattern for node i.
![\begin{displaymath}\mu_{j}(t+1) = f_{s}[\sum_{i=0}^{n-1} t_{ij}\mu_{i}(t)], \:0\leq j\leq
n-1 \end{displaymath}](img7.gif)
where fs is the continuous SIGMOID transformation function as shown below [26] [16].
![\begin{displaymath}f_{s}(net_{j}) = \frac{1}{1+\exp[\frac{-(net_{j}-\theta_{j})}{\theta_{0}}]}\end{displaymath}](img8.gif)
where
,
serves
as a threshold or bias and
is used to modify the shape
of the SIGMOID function.
This formula shows the parallel relaxation property of the
Hopfield net.
At each iteration, all nodes are activated at the same time.
The weight computation scheme,
,
is a unique characteristic
of the Hopfield net algorithm.
Based on parallel activation, each newly activated node derives
its new weight based on the summation of
the products of the weights assigned
to its neighbors and their synapses, i.e., a summation of the relevance
probabilities.
The above process is repeated until there is no change in terms of output between two iterations, which is accomplished by checking:
where 
is the maximal allowable error (a small number).
The final output represents the set of
terms most relevant to the starting keywords.
Some default threshold values were selected for (
).
The net is said to have been converged when there is no difference between two successive iterations. It is important to note the iterative behavior of the net. After each iteration, the state of the net is such that nodes which were previously dormant are now activated, and previously activated nodes are now inactivated. Each iteration results in a set of nodes, or concepts, which are semantically related to those of the previous iterations. While the particular nodes of each iteration are crucial to the activation process, they may be not the nodes most pertinent to the user's initial activation terms. The most pertinent and meaningful concepts are found upon convergence as the final set of nodes. We believe the Hopfield-based activation module will be able to alleviate some of the cognitive burden for traversing a large network of domain-specific concepts and for converging on a selected set of most relevant concepts.
B. Graphical Display:
However, this is not to say that the intermediary nodes identified during activation are meaningless. On the contrary, these terms can become a significant resource for terms matching, query refinement, and concept space exploration. The intermediary terms, which may not find their way into the final set of terms upon convergence, might serve either as triggers (clues) for further concept space exploration, or suggest terms suitable to the task at hand which had not occurred to the user. (Human ability to recognize clues during problem solving and memory retrieval is well documented in cognitive psychology [1] and human-computer interactions [6] literature.) The display of nodes in each intermediate iteration prior to convergence can perhaps be viewed as an ``extended browse" feature of the system, allowing users access to terms not otherwise available. We feel that these terms can play such a significant role in the information retrieval process that we have designed into our system a graphical display of the complete Hopfield net's iterative activation results.
Upon the activation of the Hopfield net, the X Window System-based display first presents the initial activation terms as nodes (i.e., in bubbles). As each subsequent iteration is completed, the Hopfield net places the iteration data on a global message queue, which is then received by this graphical component and displayed. This continues until the neural net converges and the last iteration is displayed.
As shown in Figure 3, the display groups each node into columns corresponding to the iteration to which it belongs. Two additional pieces of information are presented: the activation level associated with the node and the parentage of each node. The size of the circle surrounding the term indicates the relative activation level of that particular node in the net. By comparing the size of the nodes, the user is able to see which nodes within a given iteration are more significant and which are less so. The lines connecting the nodes in the display indicate which nodes activated which subsequent nodes during the activation process (reading left to right). Being thus able to trace the activation path of the net in the context of the initial set of terms and seeing the relationship among concepts within the multiple thesauri can serve as a catalyst for the user for the exploration of alternate paths of investigation or suggest novel approaches to familiar ideas. This display, a ``portal" into a neural net's ``thinking" process, could also prove interesting to researchers in the area of artificial intelligence [36].
The display is interactive in nature. Users may highlight any number of nodes by clicking on them, thereby reversing the color of that node. These highlighted terms may then be used for further browsing or activation. Alternatively, these terms may also be selected as relevant and ``posted'' to the main blackboard, or be used to activate the document retrieval component. These processes are detailed in the next section.
Finally, a blackboard architecture must include a global working area, or the blackboard itself. In production systems, this is the working memory area that holds working memory elements. It is the given state of this working memory area which causes specific productions or rules to fire. It is also this working memory area which the rules modify after firing by writing new working memory elements to the area. These new elements, by their very existence on the blackboard, put the blackboard in a new state, creating a condition for new rules to be activated. This opportunistic recognize-act cycle continues until a stopping state is reached or a solution is found.
A. Concept and Document Blackboards:
In order to assist in concept-based IR, our system provides two main, permanent blackboards: a concept blackboard and a document blackboard. These take the form of two variable-size list areas on the left side of the main application window as shown in Figure 2. The user may select any number of contiguous or non-contiguous items in either list with the pointer. Selected items in either or both lists may be deleted, or entire blackboards cleared with pull-down menu options. The system also provides for numerous transient blackboard-like windows.
The concept blackboard is a global working area which can be thought of as a searcher's notepad for storage of relevant concepts during an interactive retrieval session. Terms are initially placed onto this blackboard by means of the text field immediately above the blackboard on the main window. This text field may also be used at any time during a session to put new search terms onto the board.
The terms on the concept blackboard are accessed by the system when the user presses the Activate or Browse buttons (the control module) to launch a search. If any items on the concept blackboard are highlighted, only those terms are used to activate the selected control module. If no terms are highlighted, all existing terms on the blackboard are used. The terms on the blackboard and the relative thesaurus weights indicated by the slider scale settings are sent to the control module (browser or Hopfield net) via a message queue. A graphical display window is instantiated and the results of the activation process are displayed in the window in real time.
Terms of interest on the graphical display may be highlighted and posted to the main concept blackboard with the Post button found on the right side of the display window. The user may now delete any unwanted terms, add any fresh terms, and select or de-select any or all of the current terms on the main concept list, and again press the Activate or Browse button to launch a new search. This ``select-activate cycle,'' analogous to a production system's recognize-act cycle, may be repeated as often as desired. During the course of this iterative process, the concepts on the concept blackboard evolve as the searcher's query becomes more refined, as old terms are given up for new, and as the searcher's intentions or interests change.
The document blackboard is the second global working area in the system and can be considered as the searcher's notepad for storage of relevant documents. On the right side of the graphical display window, adjacent to the Post button described above, is a Retrieve Documents button. This button activates the system's document retrieval module. This module takes highlighted terms on the display, finds all the documents in the Public database related to those terms, and displays them in ranked order in a separate document list window as shown in Figure 4. This window displays the text id number and first line of the document in a scrollable list window. The user may highlight a text line of interest and retrieve the entire text of that document in yet another scrollable window by clicking on the Retrieve Text button. Or the user can highlight one or more documents on the list and post them to the main document blackboard. Documents, like search terms, may be directly cleared or deleted from their respective blackboards by the user.
The documents listed on the main document blackboard may also contribute terms to the Hopfield net's activation process. The system finds all terms related to each appropriate document in the list, consolidates these terms with those from the concept blackboard, and puts them on the message queue for the Hopfield net. The system will then proceed as described above under control module, resulting in a graphical display based upon both the terms from the concept board and the terms related to each document in the document blackboard. Thus, concepts and documents of interest to a searcher may be combined to browse or activate the concept space of the thesauri.
In addition to the above relevance feedback process, which uses the document indexes to perform the document search, our system also includes a ``concept-based'' relevance feedback method. This method uses the multiple thesauri to identify other semantically-relevant but syntactically-different terms. To accomplish this, the system retrieves the indexes in the selected documents and automatically activates relevant concepts in the thesauri using the Hopfield net-based activation module. It then performs a document search using the initial document indexes and the activated thesaurus terms and ranks the retrieved documents in decreasing order of relevance. Due to the application of this concept-based relevance feedback method, documents which are semantically (not just syntactically) relevant to the user's information needs should ``bubble" to the top of the list. This module thus enables intelligent document-to-document browsing and document space exploration, transparently supported by the neural net activation of multiple thesauri.
B. Transient Windows:
The main application window and the two blackboard areas serve as an anchoring point or a ``home base" for the user during the course of a retrieval session. During a session, the user enters search terms, initiates the system activation or the browsing module, posts terms to the concept blackboard, posts documents to the document blackboard, etc. These blackboards can be seen as containing the information items relating to the user's primary information retrieval goals, and at any time reflect the current state of progress toward that goal. As the items in the blackboard areas evolve, the user comes closer to obtaining the documents of greatest interest. Working within a graphical and system-aided information retrieval environment as rich as the one we present here, it is likely that a user's goals may also evolve and proliferate during the session. It is for this reason, as well as for purposes of supporting the user's main information retrieval goal, that we incorporated into our system the capacity for tangential searches through the use of transient windows.
As described earlier, users are presented during search with results of the activation process which represent the intermediate as well as the final concepts that are semantically related to their own initial terms. Besides highlighting and/or posting terms to the main blackboard or retrieving documents associated with the highlighted terms, users can activate the system again from the display window by pressing the Activate or the Browse button located on that window. The system once again fires the Hopfield net (now using the current graphical display's highlighted terms), creates a second instance of a graphical display, and presents a new set of terms semantically related to those terms highlighted in the first display. This process may be repeated until a system-imposed limit of number of displayed windows is reached. Thus, a user would be able to perform any number of secondary searches that may augment his or her main information retrieval task or represent tangential exploration of related avenues of interest.
In a similar manner, the system supports secondary document retrieval and relevance feedback. Any term or document identified from tangential activation may be posted back to the main blackboard. Thus, the transient concept and document spaces created during exploration can serve as platform from which to launch subsequent searches. The multiple activation function incorporated in this design in essence supplies the task-stacking capabilities which are characteristic of other hypertext systems [13]. In terms of human-computer interface, the multiple activation process may result in a cascade of windows activated by users.
In summary, the system incorporates the main features of the blackboard architecture, namely, knowledge sources, control module, and blackboard. In our implementation, one of our knowledge sources was algorithmically generated, others were external thesauri. The blackboard stores terms corresponding to concepts within the underlying problem domain as well as documents from the database itself. Our control module provides both user-controlled browsing and neural net aided traversal of the multiple thesauri. Analogous to a production system's opportunistic reasoning and recognize-act cycle, our system incorporates a ``select-activate cycle'' with which the user is able to recognize ``opportunities" and act upon them. Augmenting the blackboard architecture are the hypertext-like features of links between concept terms and links between concepts and documents, all of which reside in a window environment. The main application window and the numerous transient windows allow one to explore tangential streams of thought without losing one's place within the system or sight of the larger information retrieval goal. This diminishes the chances of ``getting lost in hyperspace.''
Our prototype system was developed in an ULTRIX 4.1 environment on a DECstation 5000 RISC-based workstation. C was the development language for the neural net and the backend of the blackboard system. The graphical user interface (GUI) was developed using the X Window System. Details of X and the GUI development process are described below.
The neural net had been developed several months prior to the design and implementation of the X-based blackboard system. (For details of the neural net and a non-GUI-based blackboard system implementation from which the system described in this paper borrows, see [10].) The blackboard system employs Unix's multiprocessing capabilities to fork the Hopfield net as a child process. The net requires an initialization time of approximately 2 to 3 minutes. Communication occurs between the blackboard system and the neural net via the Unix System V interprocess communication (IPC) facility of message queues. (For a detailed discussion of message queues and an excellent reference to Unix network programming in general, readers are referred to [39].)
Messages in our system are of two types. First are those messages sent from the blackboard system to the Hopfield net. These contain the relative weights of the three thesauri as well as the key terms from the concept blackboard or activation display, or key terms derived from the documents on the document blackboard or document list windows. The second type of message is that sent by the Hopfield net back to the blackboard system. Each of these messages contains the key terms resulting from one iteration of the net, as well as the activation weight of each term and other information used for the activation display. These messages are multiplexed on the same message queue.
The Hopfield net signals the blackboard when a message containing iteration data has been placed on the queue. The message is then read off the queue and processed by the blackboard system. This message queuing and signaling continues until the Hopfield net converges, at which time a terminating message is queued by the net. This particular design was adopted to provide a real-time display of the each iteration as it is completed by the net and to allow user interaction with the system prior to the net's final convergence.
X11 Release 4 libraries of the X Window System, along with a GUI editor, were used to create the interface for the blackboard system. The X Window System is a network-transparent, event-driven window system which supports overlapping windows with graphics and text operations. It provides users with a graphical user interface with both keyboard and mouse support. X was developed at MIT in 1984 and quickly became an industry standard, due partly to its non-proprietary status and the fact that it is freely available. All major Unix vendors today provide X as their default GUI for their systems.
One of X's strengths lies in its operating system and hardware independence. While found predominately running on Unix RISC-based workstations, it also operates on personal, mini, mainframe and super computer platforms and under variety of major operating systems. Another strength of the system is its inherent network transparency. It was designed to operate effectively in a heterogeneous networked environment, allowing users to display text and graphic information from remotely running applications while producing a minimum of network traffic. This distributed processing capability is achieved by means of X's unique client-server architecture.
The X Window System's client-server architecture reverses the conventional concept of locality. The X server is the application which runs locally, controlling the display and providing display services to one or more clients, which themselves may be running locally (on multitasking systems) or across a network. The server draws the graphical objects, text, and windows according to messages (requests) received from clients. It can service multiple clients simultaneously, each having one or more windows. The server also distributes user input and events to its various clients. The client applications never directly draw the display, but rather communicate with the server via a well defined messaging system called the X Protocol. The use of this messaging system reduces potential network traffic.
The server itself does not provide the functionality which allows the user to control the size, position, iconization, or stacking order of the displayed windows. These functions are provided by the window manager, which supervises all displayed windows. The X Window System itself does not impose any particular look and feel upon the display. It is the window manager's role to supply the ``window dressing" such as the border, title bar, resize and move buttons, etc. A number of window managers are in use today, the most popular being Open Software Foundation's (OSF) Motif, AT&T's and Sun's Open Look, DEC's DecWindows,and Tab's (or Tom's) Window Manager.
X in general provides a rich object-oriented GUI development environment. But there are several levels at which one may approach software development of X Window System applications. Each level builds upon the previous level and attempts to hide the complexities of the lower levels. Applications may be developed at any one or more of these levels. It is impossible, however, to completely ignore or be ignorant of the lower layers at any given level. These development levels are now described briefly.
During the course of our prototype system development we had the opportunity to utilize each of these development layers. Xlib was required for the graphical display of the Hopfield net results. We made use of the Motif widget set for the GUI and the Motif and Xt function libraries to control and modify windows and their contents. We used the VUIT GUI development tool to design our initial interface. VUIT generated UIL code which was later modified as needed.
The X Window System development process has a fairly steep learning curve. As mentioned above, the higher development levels attempt to hide the complexity of the lower levels, but with only moderate success. The UIL and tools such as VUIT are extremely useful for the novice X developer since they offer some guidance in and a high level approach to learning the details of the complex object hierarchies of the Motif widget set. UIL, however, adds one more level of complexity to an already complex system. Tools such as VUIT, in our opinion, eventually become more constraining than liberating to use. Care must therefore be taken to choose the proper tools and proper approach when developing an X application. We hope other researchers can benefit from this review and the development experience we report in this paper.
In order to give a flavor of the capabilities of this blackboard-based system, we provide below a sample interactive document retrieval session. Screen dumps are used for the illustration purposes.
The user first entered the desired search term(s) onto the concept blackboard area by means of the term entry field. In this instance, the term ``Parc" was entered as shown in Figure 5 (the first term in the concept blackboard). The user enabled the Public thesaurus and set its relative weight to a setting of 8, set the ACM CRCS and LCSH thesauri each at a setting of 0 and 5, respectively, and then proceeded to press the Activate button.
A graphical display of the activation process is shown earlier in Figure 3. Several terms were selected (darkened), and the Retrieve Documents button was pressed, revealing a list of documents which were related to the highlighted terms as shown in Figure 6. By highlighting document list items and clicking on the Retrieve Text button, user then could read the text atoms.
Both highlighted terms in the activation display and highlighted documents from the document list were then posted to the concept blackboard and the document blackboard, respectively. The user was able to retrieve selected document texts, post documents to the main document blackboard, or once again highlight documents of interest and retrieve a list other semantically related documents iteratively, as shown in Figure 7.
The prototype blackboard-based IR system (BIRD) is currently implemented on a DECstation 5000/120. The system is fairly stable, but continues to undergo minor debugging and adjustments to fine tune the interface between the blackboard system and the Hopfield net. The thesaurus activation module itself also continues to be fine tuned so as to return an appropriate and meaningful number of terms to the user. The system currently uses flat files, not a relational database management system (DBMS). Neither the database nor the knowledge sources exist in a DBMS, although plans are currently being made to port them to a relational VAX VMS-based Rdb DBMS.
The Hopfield net currently requires approximately 3 minutes to initialize upon startup. Once initialized, system response time is relatively quick, with the system usually not exhibiting more than a 3-5 second delay time between pressing the activation button and receiving the first iteration from the net. In this prototype, we currently limit the maximum number of key terms sent to the net to between 5 and 10. We do this to accommodate the nature of the activation process of the net itself. Should the system receive too many terms, it might never converge, and all of the nodes in the neural net could theoretically become activated. The system currently has a limit of three instances of each of the transient windows, i.e., the activation display, the document list, and the document text window. This makes for a reasonable prototype, while also keeping the amount of data on displayed windows to a manageable level. It also reduces the chance that the display will become too cluttered with windows. These limits can be easily raised if the need arises. We are also planning a user evaluation experiment to examine the usefulness of our proposed system design.
In conclusion, many information systems professionals and researchers have expressed a pressing need for intelligent systems to help cope with the massive amounts of data and information besieging today's knowledge workers. From the business executive to the secretary, from the research professor to the college student, knowledge workers in all fields require some sort of ``intelligent agent" which has the capacity to assist in information retrieval and information management activities. In this research we have proposed a concept-based document retrieval prototype system structured around a blackboard architecture. This system has been implemented with the X Window System and Motif widget set to provide both the graphical user interface and a dynamic display of the iterative spreading activation behavior of a Hopfield net. The system features a concept blackboard and a document blackboard to which users may post intermediate search results, and from which he or she may launch subsequent activation or searches. Users may navigate through the concept space containing three thesauri via the browse module, or relinquish control to the neural net, which automatically returns the most pertinent terms to the user. This interactive hypertext design empowers users to explore in a system of document and concept spaces in an intelligent manner. It is hoped that this system research and implementation effort may contribute to the advancement of ``intelligent'' (knowledge-based) and user-friendly document retrieval systems design.
This project was supported in part by NSF grant # IRI-9211418, 1992-1994 (Division of Information, Robotics, and Intelligent Systems).
