[available upon request]
Current structural genomics projects are likely to produce hundreds of proteins a year for structural analysis. The primary goal of our research is to speedup the process of crystal growth for proteins in order to support the determination of protein structure using single crystal X-ray diffraction. We describe Max, a working prototype that includes a high-throughput crystallization and evaluation setup in the wet lab with an intelligent software system in the computer lab. A robotic setup for crystal growth is able to prepare and evaluate over forty thousand crystallization experiments a day. Images of the crystallization outcomes captured with digital cameras are processed by an image analysis component which uses the two-dimensional Fourier transform to perform automated classification of the experiment outcome. An information repository component, which stores the data obtained from crystallization experiments, was designed with an emphasis on correctness, completeness and reproducibility. A Case-Based Reasoning component provides support for the design of crystal growth experiments by retrieving previous similar cases, and then adapting these in order to create a solution for the problem at hand. While development work on Max is still in progress, we report here on the implementation status of its components, discuss how our work relates to other research, and describe our plans for the future.
[available upon request]
A case base is a repository of past experiences that can be used for problem
solving. Given a new problem, expressed in the form of a query, the case base
is browsed in search of ``similar'' or ``relevant'' cases. Conversational
case-based reasoning (CBR) systems generally support user interaction during
case retrieval and adaptation. Here we focus on case retrieval where users
initiate problem solving by entering a partial problem description. During an
interactive CBR session, a user may submit additional queries to provide
a ``focus of attention''. These queries may be obtained by relaxing or
restricting the constraints specified for a prior query. Thus, case retrieval
involves the iterative evaluation of a series of queries against the case base,
where each query in the series is obtained by restricting or relaxing the
preceding query. This paper considers alternative approaches for implementing
iterative browsing in conversational CBR systems. First, we discuss a naive
algorithm, which evaluates each query independent of earlier evaluations.
Second, we introduce an incremental algorithm, which reuses the results of past
query evaluations to minimize the computation required for subsequent queries.
In particular, the paper proposes an efficient algorithm for case base browsing
and retrieval using database techniques for incremental view maintenance. In
addition, the paper evaluates the performance of the proposed algorithm with
respect to alternative approaches considering two perspectives: (i)
experimental efficiency evaluation using diverse application domains, and (ii)
scalability evaluation using the performance model of the proposed system.
Classification involves associating instances with particular classes by maximizing intra-class similarities and minimizing inter-class similarities. Thus, the way similarity among instances is measured is crucial for the success of the system. In case-based reasoning, it is assumed that similar problems have similar solutions. The case-based approach to classification is founded on retrieving cases from the case base that are similar to a given problem, and associating the problem with the class containing the most similar cases.
Similarity-based retrieval tools can advantageously be used in building flexible retrieval and classification systems. Case-based classification uses previously classified instances to label unknown instances with proper classes. Classification accuracy is affected by the retrieval process - the more relevant the instances used for classification, the greater the accuracy.
The paper presents a novel approach to case-based classification. The algorithm is based on a notion of similarity assessment and was developed for supporting flexible retrieval of relevant information. Case similarity is assessed with respect to a given context that defines constraints for matching. Context relaxation and restriction is used for controlling the classification accuracy. The validity of the proposed approach is tested on real-world domains, and the system's performance, in terms of accuracy and scalability, is compared to that of other machine learning algorithms.
[available upon request]
One can also read selected sections of this work
(unfortunately without proper quotation and reference) in Lynn Ling X Li (1999)
Knowledge-based problem solving: An approach to health assessment. Expert
Systems with Applications, 16(1):33-42. See also Expert Systems with
Applications 18:153, 2000.”
In vitro fertilization (IVF) is a medically-assisted reproduction technique, enabling infertile couples to achieve successful pregnancy. Given the unpredictability of the task, we propose to use a case-based reasoning system that exploits past experiences to suggest possible modifications to an IVF treatment plan in order to improve overall success rates. Once the system's knowledge base is populated with a sufficient number of past cases, it can be used to explore and discover interesting relationships among data, thereby achieving a form of knowledge mining.
The article describes the TA3IVF system - a case-based reasoning system which relies on context-based relevance assessment to assist in knowledge visualization, interactive data exploration and discovery in this domain. The system can be used as an advisor to the physician during clinical work and during research to help determine what knowledge sources are relevant for a treatment plan.
Structural genomics projects promise to produce hundreds of proteins a year for structural analysis. The challenge to crystal growers is to make some other step in the structural biology enterprise rate-limiting. Our approach is to combine high throughput (HTP) crystallization setup and evaluation in the wet lab with sophisticated algorithmic analyses of the HTP outcomes in the computer lab for the purposes of recipe prediction.
In the wet lab we now have the capacity to prepare and evaluate the results of over sixty thousand (61.4K) crystallization experiments a workweek. Each is a microbatch experiment conducted under paraffin oil. Pipetting is performed with robots outfitted with 96 or 384 syringes and XYZ translation stages. High density (1536 well) micro-assay plates hold the experiments. 1536 crystallization cocktails, covering a wide range of crystallizing agents, have been prepared. Current pipetting protocols allow us to deploy 200 nanoL droplets of protein solution and crystallization cocktails(total drop size 400 nanoL). Once a micro-assay plate is prepared with paraffin oil and crystallization cocktails it is possible to set protein solution into the wells in less than five minutes, allowing us to work quickly with unstable proteins. Current total protein requirements are being assessed, but are likely to be in the 10 mg range. After setup plates are placed on a computer controlled XY table with micron positioning accuracy. The plates are translated under a megapixel digital camera where images are captured by a frame grabber. The XY table can accommodate28 plates (43K experiments) at a time and the camera can record 43K images in approximately twelve hours.
In the computer lab the images are analyzed automatically to determine the outcomes of the crystallization experiments. We are developing a standard vocabulary of outcomes that will describe the results: clear drop, amorphous precipitate, phase separation, microcrystals, crystals, and uncertain outcome. These outcomes, recorded as a function of time, are the cornerstone of a crystallization database that will contain physical information about individual proteins as well as results of crystallization experiments with those proteins. Using case-based reasoning algorithms we will identify patterns of similar properties and crystallization outcomes relating two or more proteins in the database. Our hypothesis is that, given a quantitative measure of “similarity” between proteins, recipes successfully employed for one protein will be useful starting points for crystallization experiments with similar proteins. Future work will center upon the most predictive measures of “similarity”.
The medical potential of the various genome projects now underway will be realized when we know not only the sequences of the amino acids coded in open reading frames but also what these ORFs represent, both structurally and functionally. Structural proteomics will challenge us to grow more and better crystals for diffraction studies. Our labs are involved in two major aspects of that work: getting the techniques and equipment in place to do large scale, high throughput crystallization experiments, and assembling the expertise to make sense of all the data that will come from those experiments.
We need to use dynamic knowledge organization approaches in order to facilitate effective access and use of domain knowledge. Although there are many approaches to knowledge organization available, it is a challenge to systematically organize evolving domains, because it is not feasible to rely only on humans to create relationships among individual knowledge sources. Additional problems arise because knowledge may not be consistently and completely described, and quality control may not always be in place in distributed knowledge environments. In this article we describe a generic approach to knowledge organization by using systematic knowledge management and applying knowledge-discovery techniques. We use a case-based reasoning system, called TA3, as a core component for knowledge management. Application of symbolic knowledge-discovery component of TA3supports three main tasks: system optimization, knowledge evolution and evidence creation. To explain advantages of this approach, we use our experience from biomedical domains.
This paper describes the application of automated image analysis to evaluate morphology and developmental features of oocytes and embryos in the domain of in vitro fertilization (IVF). Although humans can analyze images more flexibly, computer vision techniques make the process more objective and precise. We propose to use computer-based morphometry to precisely and objectively identify developmental features of oocytes and embryos. Extracted morphological information can be linked with symbolic information to better predict pregnancy outcome and suggest further medical procedures. Recognized features can then be used to support case-based reasoning and knowledge discovery. The combination of image analysis techniques and case-based reasoning can thus serve as: (1) a feature extraction technique; (2) an indexing approach; and (3) an analysis tool. A combination of symbolic and image information can then be used to identify morphological features of oocytes and embryos that are vital for successful IVF. Extracting image features and analyzing them helps to perform knowledge discovery from images.
Knowledge management research focuses on the development of concepts, methods, and tools supporting the management of human knowledge. To further this objective, researchers are studying the way organizations, groups and individuals use knowledge in the performance of daily tasks. They are also developing computer-based tools and techniques to support the acquisition, representation, organization, retrieval, analysis and evolution of knowledge in its many forms. The main objective of this paper is to survey some of the primitive concepts that have been used in computer science for the representation of knowledge and summarize some of their advantages and drawbacks. A secondary objective is to relate these techniques to information sciences theory and practice.
Several research areas within computer science have developed techniques for representing knowledge so that it can be accessed and used by humans and software systems alike. In particular, Artificial Intelligence (AI) has developed techniques for representing knowledge so that it can be exploited by intelligent systems. Databases have focused on techniques, which allow the representation and management of large amounts of simple knowledge, using as vehicles relational databases and related technologies. Software Engineering and Information Systems have developed elaborate techniques for capturing knowledge that relates to the requirements, design decisions and rationale for a software system. We characterize all these techniques in terms of the primitive concepts they offer for representing knowledge within a given class of applications.
This paper presents some preliminary results on applying information retrieval and knowledge-mining techniques to reverse engineering of legacy systems. In order to support a dynamic environment, we take an approach of integrating lightweight tools. Instead of forcing a user to use a fixed environment, our approach provides a basic information repository, which manages information extracted from the documentation and source code. The system stores this information in a graph structure, it supports navigation through the repository, and modification of its structure and annotation. Preliminary evaluation of the proposed approach on the small-size software system is encouraging.
The health care industry faces constant demands to improve quality, extend services, and reduce cost. Telemedicine satisfies these demands by supporting distant consultations. In addition, knowledge-based systems may augment current synchronous telemedicine applications by storing and managing medical experience over time. By providing timely and efficient access to the knowledge repository, knowledge-based systems help to distribute experience, standardize procedures, lower cost, and increase quality of health care services. This facilitates asynchronous telemedicine.
Our previous experience from using a case-based reasoning system to support specialists in in vitro fertilization domain shows that this paradigm is suitable for building medical knowledge repositories for knowledge sharing. We propose to extend the system to support tele-consultations: (1) between specialists (rare medical cases); (2) between general practitioners and specialists (standard practices); and (3) between health care professionals and patients (generic medical information). This will help to standardize patient examination and treatment practices. In addition, physicians will be able to share experience via remote knowledge repository.
This paper focuses on extensions for specialists. We show how case-based reasoning can support evidence-based medicine, remote consultations, and improve knowledge sharing and domain understanding.
This
paper reviews several knowledge organization techniques used in Computer Science,
in areas such as Artificial Intelligence, Databases and Software Engineering.
Some of these computational mechanisms may assist in the organization and
management of immense digital information resources. At the same time, the
paper notes an increasing need for computer-based information systems to
operate in open networked environments. This need requires knowledge
organization principles, which are flexible and can be used with informally
expressed knowledge. We expect to find such knowledge organization techniques
in Library and Information Sciences, and hope to integrated them with the
computational techniques described in this paper.
A case base is a repository of past experiences that can be used for problem solving. Given a new problem, expressed in the form of a query, the case base is browsed in search of “similar” or “relevant” cases. One way to perform this search involves the iterative evaluation of a series of queries against the case base, where each query in the series is obtained by restricting or relaxing the preceding query.
The paper considers
alternative approaches for implementing iterative browsing in case-based
reasoning systems, including a naive algorithm, which evaluates each query
independent of earlier evaluations, and an incremental algorithm, which reuses
the results of past query evaluations to minimize the computation required for
subsequent queries. In particular, the paper proposes an efficient algorithm
for case base browsing and retrieval using database techniques for view
maintenance. In addition, the paper evaluates the performance of the proposed
algorithm with respect to alternative approaches considering two perspectives:
(1) experimental efficiency evaluation using diverse application domains, and
(2) scalability evaluation using the performance model of the proposed system.
Complex decision-support information systems for diverse domains need advanced facilities, such as knowledge repositories, reasoning systems, and modeling for processing interrelated information. System development must satisfy functional requirements, but must also systematically meet global quality factors, such as performance, confidentiality and accuracy, called non-functional requirements (NFRs).
Case-based reasoning (CBR) systems, an important class of decision support systems, require a design process that systematically produces high-quality applications. Beyond satisfying basic functional requirements for CBR, it is important to meet global quality factors, such as performance and confidentiality, called non-functional requirements (NFRs). This paper presents a goal-oriented, knowledge-based approach for aiding decision support system development and usage, namely, it proposes an approach for dealing with non-functional requirements (NFRs) for CBR systems. We show how quality can be built into a CBR system, using the “QualityCBR” approach, which integrates existing work on CBR and NFRs. We illustrate the use of the approach in a complex medical domain – in vitro fertilization [C8]. In this domain, a CBR system is used for:(1)suggesting hormonal therapy for in-vitro fertilization patients,(2)predicting the probability of successful pregnancy, and (3) interactively determining important patient's characteristics that can improve pregnancy rate. The QualityCBR approach is used to address important NFRs, such as performance, accuracy and confidentiality.
The paper presents a similarity-based retrieval framework for a software repository that aids the process of maintaining, understanding, and migrating legacy software systems. Designing a software repository involves three issues: (1) information content; (2) information representation; and (3) strategies for accessing repository artifacts. Given the architecture of a Bookshelf software repository, we extend the retrieval system to support imprecise queries, iterative browsing, and diverse users. Because of repository size, complexity of queries and relations among artifacts, we take a performance approach to support a scalable implementation. We propose a retrieval system that uses numeric and semantically rich context-based similarity. Efficient iterative browsing is based on an incremental query evaluation algorithm from database management systems. Explicitly defined context supports various retrieval strategies and diverse user models.
This paper introduces a generic approach to knowledge-based decision-support in medicine. We review problems present in medical domains and introduce available solutions. We describe a case-based reasoning system called SpotLight and discuss its advantages when applied to complex medical domains, in vitro fertilization and nephrology.
This paper presents a method, PALO, that side-steps the utility problem of explanation-based learning algorithms by using a set of samples to estimate the unknown distribution, and by using a set of transformations to hill-climb to a local optimum. It uses statistical techniques to determine whether the result of a proposed transformation will be better than the original system. We also present an efficient way of implementing this learning system in the context of a general class of performance elements, and include empirical evidence that this approach can work effectively.
Similarity plays a central role in theories of human problem solving and thus is important for artificial intelligence research. Although there are different approaches to similarity assessment, the underlying idea is to classify information according to some features, so that we can use it in similar situations. Depending on the application domain, the task at hand, and user preferences, the relevance of individual features may vary, and so will the similarity of the concepts they represent. It is paramount to know what affects feature relevance and how to represent such information explicitly.
The objective of this thesis is to improve case-based reasoning by: (1) achieving better accuracy during classification; (2)retrieving cases that are more relevant to a given problem; and (3) obtaining scalability with respect to case base size, case and query complexity. We achieve this goal by introducing a new theory of similarity-based retrieval that uses variable-context similarity assessment, and by defining an efficient iterative retrieval algorithm that employs ideas of incremental view maintenance algorithms from database management systems. Context is a parameter of similarity that specifies what attributes are involved in similarity assessment between cases, and what set of values may be considered for these attributes. It defines which aspects of a case are important in a particular situation. We also define a set of operations, namely relaxation and restriction, which enable to control the relevance of retrieved cases.
We evaluate competence,
scalability and algorithmic complexity of a prototype system on diverse
real-world domains. We show how the proposed similarity measure supports
flexible computation by trading off the accuracy or precision of the
computation process for time and space resources. In addition, the case
representation used supports case base organization so that cases similar in a
given context can be grouped into clusters. This representation also lends
itself to attribute-oriented discovery, a technique that finds relevant
attributes and their values. The discovery process improves the representation
by grouping together relevant, removing unneeded or adding essential
attributes. Performance evaluation shows how the discovery process improves
system's competence. Iterative retrieval of cases is efficiently handled by the
adoption of incremental view maintenance algorithms from database management
systems. Performance evaluation shows that this approach improves efficiency of
case retrieval and thus helps to achieve system scalability with respect to
case base size, case representation and query complexity.
· Jurisica, I. (1993). Query
Optimization for Knowledge Base Management Systems: A Machine Learning
Approach. MSc thesis, Department of Computer Science, University of Toronto,
Toronto, Ontario.
This thesis proposes new machine learning applications to optimize queries in a knowledge base management systems. In particular, an explanation-based machine learning algorithm is adopted, extended and tested. The algorithm, called PALO (Probably Approximately Locally Optimal), is a general model of a learning system and is directly applicable to a variety of systems as a speedup learning module. The algorithm is based on the theoretical work of Valiant [Valiant-CACM84] and uses statistical information to produce a close approximation of a locally optimal search strategy. Some additions are made to the original version of the algorithm, to solve a broader range of problems. In addition, the termination condition in the algorithm is changed in order to make it run faster without any degradation of its performance. The learning module is implemented and its integration into an architecture of a knowledge base management system is shown. The proposed optimization technique is tested with real and artificial examples to establish its effectiveness.
Biomedical
computing involves the application of computational methods for the
advancement of biological and medical science. Activities in this area range
from data acquisition, robotics and laboratory analysis to the dissemination,
storage and retrieval of knowledge. Modern biomedical computing is rooted in a
broad range of application areas. Imaging needs from microscopy to mammography
have motivated and relied on advances in imaging science. Medical data storage
and access systems benefit from the study of information retrieval. Algorithms
and software development are of key importance in areas such as genome sequence
analysis and acquisition, which also depend on techniques from statistics and
artificial intelligence. Medicine and the biological sciences already have an
accumulation of extraordinarily large and complex data sets that are
uninterpretable without the benefit of computational methods.
The main goal of this workshop will be the
presentation of existing problems and computational solutions in the biomedical
domain
The aim of the panel is to discuss state-of-the-art in telemedicine, present experience gained, and to consider advantages and disadvantages of telemedicine. We plan to propose architecture for telemedicine systems that would support currently available systems, but would enable extensions. We recognize two possible approaches: (1) Human– human; (2) Human - Intelligent Decision Support System. The first approach has the advantage of being simple and readily available. However, it does not solve the problem of shortage of experts, which can be handled by the second approach. In addition, the second approach has the advantage of providing better transaction processing since it uses global repository(a case base) to store and manage experience. The main advantage is that experts collect global experience and thus progress with domain understanding faster and that the communication between experts is asynchronous. The panel will bring together telemedicine specialists, practicing physicians, technology providers and researchers.
The panel brought together healthcare specialists, researchers in medical informatics, psychology and computer science, technology providers, and government agencies to discuss the issues related to building medical information management systems. Panel aimed at identifying a blueprint for medical information systems in Canada by discussing limitations of existing decision support tools, identifying technological challenges and the key organizational factors that arise from the implementation of large scale distributed information systems. On the basis of the response from the conference organizers and the audience, we believe the panel engendered collaborative research and development, and will steer the research and development into right direction. Summary of the panel is being prepared for publication in AI in Medicine journal.
I have presented tutorials on case-based reasoning (CBR), machine learning and knowledge base management systems (KBMS) on several occasions, including:
This tutorial provides an introduction to the latest computational techniques for data mining and knowledge discovery in biological domains. We will explore the fit of the traditional data-mining techniques for alphanumeric, visual and relational data to biology. After characterizing biological problems, basic definitions and diverse algorithms will be presented. This will include scientific discovery, pattern identification, organization, summarization and description, clustering, classifying, associating and predicting, and information extraction. An overview of current state-of-the-art commercial and academic systems will be covered, with the emphasis on successful examples of data mining and knowledge discovery in biology. The examples will include amino acid sequence analysis, homology detection, elucidation of biological function, protein structure prediction and identification of related proteins, systematic generation of bio-dictionaries(TM) and their exploitation, analysis of biological effects, model generation anduse, DNA microarrays analysis, data curation, hypothesis generation and testing. We will identify limitations of generic approaches, define problems and issues that must be addressed to successfully mine biological sequence and structure databases. We will close by discussing future directions of knowledge discovery in biology, and its relevance of knowledge visualization, knowledge evolution and management of scientific knowledge.