1996 NCARAI Published Papers
and Technical Reports

Librarian: Amy Keyser
phone: (202) 767-0018
email:library@aic.nrl.navy.mil.

Here is an order form to order reports by mail. Some of the following reports can be downloaded as PostScript, compressed PostScript, or HTML files.

1996 Publications

Perzanowski, Dennis, Gurney, John,
"The Message in the Medium: On the Functionality of It-clefts in Selected Discourses. January 1, 1996. NCARAI Report: AIC-96-011. Download Now

Information in a discourse can be obtained by analyzing several different linguistic properties of the discourse. Various syntactic and semantic triggers provide clues to the complex informational structure of a discourse. For the purposes of this investigation, we selected several discourses taken from a series of wire service messages dealing with terrorist incidents that occurred in Central America from 1989 to 1991. The corpus is known as the "MUC-3" corpus. Because of their inferential properties, we identified it-cleft constructions in the corpus. We argue that, despite their rarity in the corpus under investigation, it-clefts provide additional information, and do not just contrast or emphasize focused linguistic material, such as noun or prepositional phrases. By substituting so-called "normal" word order, or SVO paraphrases, for the it-clefts in the messages, we determined what information the it-cleft sentences provided in the discourse. Our investigation reveals that, as a subset of the information that can be obtained in a discourse, it-clefts can be used to avoid conflicting or differing interpretations inherent in their SVO paraphrases, thereby minimizing possible confusion regarding the interpretation of what the author is trying to communicate. In some cases the speaker/writer's point of view or attitude about the subject matter being discussed is also revealed. For example, we show how a focused generic noun phrase in an it-cleft sentence provides a clearer statement of the author's intended meaning.

Spears, William M.,
A NN Algorithm for Boolean Sastisfiability Problems. January 1, 1996. NCARAI Report: AIC-96-009. (Not available on-line at this time. Please see order form)

Satisfiability (SAT) refers to the task of finding a truth assignment that makes an arbitary boolean expression true. This paper compares a neural entwork algorithm (NNSAT) with GSAT [4], a greedy algorithm for solving satisfiability problems. GSAT can solve problem instances that are difficult for traditional satisfiability problems. Results suggest that NNSAT scales better as the number of variables increase, solving at least as many hard SAT problems.

Chang, Liwu, Harrison, Patrick R.,
Case-Based Retrieval and Indexing Using a Bayesian Network Model. 5th CSTS Conference on Computer Science & Operations Research: Recent Advances in the Interface, Dallas, Texas, January 7-10, 1996. NCARAI Report: AIC-96-008. (Not available on-line at this time. Please see order form)

Bayesian case-based reasoning has at its core a Bayesian network model for memory, retrieval, indexing and organization. In retrieval, a query network is constructed with the query as the root and features as the leaf nodes. We select the case that maximizes posterior probability of the query. In the presence on non-informative features, dependent features or noisy cases, we use adaptive methods such as feature selection, feature dependency analysis and representative cases selection to refine the Bayesian network model. Both feature selection and feature dependency analysis use a cross-validation scheme for evaluating different feature combinations and the back and forth hill-climbing search strategy. As a result, predictive accuracy of retrieval can be greatly improved via adaptation. As for indexing, conceptual clustering methods can be used to generate new indices for new and stored cases. We propose an iterative refinement clustering procedure. This procedure helps to avoid stopping at local minimal of performance functions too early. After labels of some new instances are assigned, clustering iteratively adjusts contents of clusters by re-calculating class probability for instances of some clusters. As a result, misplaced instances are minimized. The number of desired indices is the maximum of probabilities of a number given all stored instances Since the condition of the clusters is not known, it is viewed as a hidden variable. Thus, the final case organization is represented by a Bayesian network with hidden variables. Our implemented system has been used as a testbed for studying CBR functions.

Aha, David A., Chang, Li Wu,
Cooperative Bayesian and Case-Based Reasoning for Solving Multiagent Planning Tasks. January 1, 1996. NCARAI Report: AIC-96-005. Download Now

We describe an integrated problem solving architecture named INBANCA in which Bayesian networks and case-based reasoning (CBR) work cooperatively on multiagent planning tasks. This includes two-team dynamic tasks, and this paper concentrates on simulated soccer as an example. Bayesian networks are used to characterize action selection whereas a case-based approach is used to determine how to implement actions. This paper has two contributions. First, we survey integrations of case-based and Bayesian approaches from the perspective of a popular CBR task decomposition framework, thus explaining what types of integrations have been attempted. This allows us to explain the unique aspects of our proposed integration. Second, we demonstrate how Bayesian nets can be used to provide environmental context, and thus feature selection information, for the case-based reasoner.

Breslow, Leonard,
Greedy Utile Suffix Memory for Reinforcement Learning with Perceptually-Aliased States. January 1, 1996. NCARAI Report: AIC-96-004. Download Now

Reinforcement learning agents are faced with the problem of perceptual aliasing when two or more states are perceptually identical but require different actions. Purely reactive policies do not produce optimal performance in such situations. To address this problem, various researchers have incorporated memory of preceding events into the definition of states to distinguish perceptually-aliased states. Approaches to differentiating aliased states engage in two concurrent interacting learning processes: learning of the correct {\it state representation} and reinforcement learning of the correct {\it policy} of actions to take from each state. Recently, McCallum (1995b) has offered Utile Suffix Memory (USM), an instance-based algorithm using a tree to store instances and to represent states for reinforcement learning. USM's use of online instance-based state learning permits state definitions to be updated quickly based on the latest results of reinforcement learning. USM uses statistical tests to determine the relevance of history information considered for inclusion in state definitions. However, USM conducts many unnecessary statistical comparisons, making it vulnerable to false positive errors that produce state distinctions that are not useful and overbranching of the state tree. The algorithm cannot correct such errors since it does not prune the state tree. The problem of over-branching of the state tree is particularly serious when the algorithm is applied to tasks in which some aliased states cannot be differentiated on the basis of the event immediately prior to the current observation (i.e., at time t-1) but can only be differentiated on the basis of earlier events (e.g., t-2 or t-3). Greedy Utile Suffix Memory (GUSM) addresses these concerns through several modifications of USM: greedy state splitting, incremental state splitting, and the restriction of statistical comparions to potentially useful differences. GUSM is shown to learn action policies faster than USM and to generate smaller state spaces (i.e., more correctly-sized trees).

Kamgar-Parsi, Behrooz, Kamgar-Parsi, Behzad,
Rejection with Multilayer Neural Networks: Screening Image Data. NRL Review, 1996, January 1, 1996. NCARAI Report: AIC-96-003. (Not available on-line at this time. Please see order form)

Existing neural networks are unable to reject unfamiliar patterns, and thus misclassify them as members of classes of patterns with which they are familiar. Indeed, other classifiers in the fields of computer vision, statistical pattern recognition, etc., also suffer from a similar shortcoming, as they can only find the closest class-which may or may not be the correct class. Hence, the use of neural networks, and other classifiers, for pattern recognition have been limited to controlled environments, i.e., environments that only involve a limited number of known classes of patterns (classes used in the design of the classifier), e.g. , optical character recognition. In uncontrolled environments, encompassing many real life problems, however, there is no guarantee that all the patterns that will be presented to the network (or other classifiers) would actually belong to of the classes on which the network has been trained. For application in such environments., current pattern recognition and computer vision techniques resort to some ad hoc thresholds in order to decide whether to accept or reject the unknown [pattern as belonging to a certain class. This often produces unreliable results. We have developed a method to construct multilayer perceptrons with rejection capabilities for visual patterns that are meaningful to humans. The methods is potentially applicable to a variety of problem which are of interest both to the Navy and the commercial sector.

Perez-Quiones, Manuel A., Sibert, John L.,
Negotiating User-Initiated Cancellation and Interruption Requests. submitted to CHI '96, January 1, 1996. NCARAI Report: AIC-96-002. Download Now

Interruptions and cancellations are important parts of a user interface, yet they are treated as special cases in user interface design and notations. In an effort to build a dialogue notation that allows for effective definition of these commands or user turns, we present a behavioral definition of interruptions and cancellations. We show several examples of how our definition accounts for different forms of behavior. The behavioral definitions provided here are a step towards providing better support for the definition and implementation of these turns.

Perez-Quiones, Manuel A., Sibert, John L.,
A Collaborative Model of Feedback in Human-Computer Interaction. submitted to CHI '96, January 1, 1996. NCARAI Report: AIC-96-001. Download Now

Feedback plays an important role in human-computer interaction. It provides the user with evidence of closure, thus satisfying the communication expectations that users have when engaging in a dialogue. In this paper we present a model identifying five feedback states that must be communicated to the user to fulfill the communication expectations of a dialogue. The model is based on a linguistics theory of conversation, but is applied to a graphical user interface. An experiment is described in which we test users expectations and their behavior when those expectations are not met. The model subsumes some of the temporal requirements for feedback previously reported in the human-computer interaction literature.