An understanding of antiviral drug resistance is important in the design of effective drugs. Comprehensive features of the interaction between drug designs and resistance mutations are difficult to study experimentally because of the very large numbers of drugs and mutants involved. We describe a computational framework for studying antiviral drug resistance. Data on HIV-1 protease are used to derive an approximate model that predicts interaction of a wide range of mutant forms of the protease with a broad class of protease inhibitors. An algorithm based on competitive coevolution is used to find highly resistant mutant forms of the protease, and effective inhibitors against such mutants, in the context of the model. We use this method to characterize general features of inhibitors that are effective in overcoming resistance, and to study related issues of selection pathways, cross-resistance, and combination therapies.

We propose a novel method for automatically adjusting parameters in ranked-output text retrieval systems to improve retrieval performance. A ranked-output text retrieval system implements a ranking function which orders documents, placing documents estimated to be more relevant to the user's query before less relevant ones. The system adjusts its parameters to maximize the match between the system's document ordering and a target ordering. The target ordering is typically given by user feedback on a set of sample queries, but is more generally any document preference relation. We demonstrate the utility of the approach by using it to estimate a similarity measure (scoring the relevance of documents to queries) in a vector space model of information retrieval. Experimental results using several collections indicate that the approach automatically finds a similarity measure which performs equivalently to or better than all “classic” similarity measures studied. It also performs within 1% of an estimated optimal measure (found by exhaustive sampling of the similarity measures). The method is compared to two alternative methods: A Perceptron learning rule motivated by Wong and Yao's (1990) Query Formulation method, and a Least Squared learning rule, motivated by Fuhr and Buckley's (1991) Probabilistic Learning approach. Though both alternatives have useful characteristics, we demonstrate empirically that neither can be used to estimate the parameters of the optimal similarity measure. © 1998 John Wiley & Sons, Inc.

We consider "competitive coevolution," in which fitness is based on direct competition among individuals selected from two independently evolving populations of "hosts" and "parasites." Competitive coevolution can lead to an "arms race," in which the two populations reciprocally drive one another to increasing levels of performance and complexity. We use the games of Nim and 3-D Tic-Tac-Toe as test problems to explore three new techniques in competitive coevolution. "Competitive fitness sharing" changes the way fitness is measured; "shared sampling" provides a method for selecting a strong, diverse set of parasites; and the "hall of fame" encourages arms races by saving good individuals from prior generations. We provide several different motivations for these methods and mathematical insights into their use. Experimental comparisons are done, and a detailed analysis of these experiments is presented in terms of testing issues, diversity, extinction, arms race progress measurements, and drift.

Machine learning of game strategies has often depended on competitive methods that continually develop new strategies capable of defeating previous ones. We use a very inclusive definition of game and consider a framework within which a competitive algorithm makes repeated use of a strategy learning component that can learn strategies which defeat a given set of opponents. We describe game learning in terms of sets H and X of first and second player strategies, and connect the model with more familiar models of concept learning. We show the importance of the ideas of teaching set [20] and specification number [19] k in this new context. The performance of several competitive algorithms is investigated, using both worst-case and randomized strategy learning algorithms. Our central result (Theorem 4) is a competitive algorithm that solves games in a total number of strategies polynomial in lg(jHj), lg(jX j), and k. Its use is demonstrated, including an application in concept learning ...

We apply a genetic algorithm whose genotypes represent simple grammars to search for families of compare-exchange networks that are merging networks. The grammars are restricted to be of a simple form based on prior knowledge about the search domain. Finding merging networks in this fashion leads to the discovery of networks that also sort if the data is cycled through them a small number of times. Random network and grammar generation results show that the problem is difficult and suggest some conjectures about how the genetic algorithm is operating for this problem. The genetic algorithm finds the best-known network of the kind for which we search, and further finds a novel, slightly suboptimal network that turns out to be an interesting combination of ideas from known, theoretically derived networks.

A method is proposed for creating vector space representations of documents based on modeling target interdocument similarity values. The target similarity values are assumed to capture semantic relationships, or associations, between the documents. The vector representations are chosen so that the inner product similarities between document vector pairs closely match their target interdocument similarities. The method is closely related to the Latent Semantic Indexing approach; in fact, they are equivalent when the target similarities are derived directly from document similarities based on term co-occurrence. However, our method allows for external sources of interdocument semantic constraints to be used in the indexing, though at greater computational expense. The method is applied to three standard text databases from the information retrieval literature. On the CISI database of information science abstracts, performance (measured by precision averaged over a range of recall levels) improves by 28% compared to a weighted term-vector approach, and improves 10% compared to Latent Semantic Indexing. Similar improvement is obtained on the Cranfield database, but no improvement is obtained for the artificial MED database of medical abstracts. The generally favorable performance suggests interesting potential for methods which explicitly modify the retrieval system to meet interdocument semantic constraints. © 1995 John Wiley & Sons, Inc.

Latent Semantic Indexing (LSI) is a technique for representing documents, queries, and terms as vectors in a multidimensional real-valued space. The representations are approximations to the original term space encoding, and are found using the matrix technique of Singular Value Decomposition. In comparison, Multidimensional Scaling (MDS) is a class of data analysis techniques for representing data points as points in a multidimensional real-valued space. The objects are represented so that inter-point similarities in the space match inter-object similarity information provided by the researcher. We illustrate how the document representations given by LSI are equivalent to the optimal representations found when solving a particular MDS problem in which the given inter-object similarity information is provided by the inner product similarities between the documents themselves. We further analyze a more general MDS problem in which the interdocument similarity information, although still...

SCALIR is a legal information retrieval system which uses a combination of symbolic and connectionist artificial intelligence techniques. Traditional systems used for automating legal research have many difficulties which make them “brittle”; SCALIR is an attempt to rectify many of these problems. SCALIR's hybrid nature is especially appropriate for the legal domain, which requires both logical and associative inferences. The system also benefits from a unique direct-manipulation style interface and the ability to improve its performance based on user feedback.

AIR represents a connectionist approach to the task of information retrieval. The system uses relevance feedback from its users to change its representation of authors, index terms and documents so that, over time, AIR improves at its task. The result is a representation of the consensual meaning of keywords and documents shared by some group of users. The central focus goal of this paper is to use our experience with AIR to highlight those characteristics of connectionist representations that make them particularly appropriate for IR applications. We argue that this associative representation is a natural generalization of traditional IR techniques, and that connectionist learning techniques are effective in this setting.

This report proposes that recent advances using low-level connectionist representations offer new possibilities to those interested in free text information retrieval (IR). The AIR system demonstrates that this representation suits the IR domain well, particularly the special problems attending the more sophisticated forms of conceptual retrieval required in legal applications. Also, the natural way in which connectionist representations allow learning means that AIR can avoid the high costs associated with manual indexing while providing comparable results. The paper begins by motivating the importance of legal information retrieval, from the perspectives of both the Law and artificial intelligence (AI). Our approach is then compared to traditional methods for IR, and to more recent work using higher-level symbolic representations from AL After a brief introduction to connectionist representations in general, the AIR system is presented. The paper closes with evidence that this system does, in fact, begin to support the use of those “open textured” concepts that make the Law both a very difficult and a very illuminating domain for AI research.