Discovery Science: Second International Conference, DS'99, Tokyo, Japan, December 6-8, 1999 Proceedings (Lecture Notes in Computer Science, 1721)

This volume contains the papers presented at the Second International Conf- ence on Discovery Science (DS'99), held in Tokyo, Japan, December 6-8, 1999. The conference was colocated with the Tenth International Conference on Al- rithmic Learning Theory (ALT'99). This conference was organized as part of the activities of the Discovery S- ence Project sponsored by Grant-in-Aid for Scienti c Research on Priority Area fromthe MinistryofEducation, Science, SportsandCulture (MESSC)ofJapan. This is a three-year project starting from 1998 that aims to (1) develop new methods for knowledge discovery, (2) install network environments for kno- edge discovery, and (3) establish Discovery Science as a new area of computer science. The aim of this conference is to provide an open forum for intensive disc- sions and interchange of new information among researchers working in the new area of Discovery Science. Topics of interest within the scope of this conference include, but are not limited to, the following areas: Logic for/of knowledge discovery, knowledge d- coverybyinferences, knowledgediscoverybylearningalgorithms, knowledged- coverybyheuristicsearch, scienti cdiscovery, knowledgediscoveryindatabases, data mining, knowledge discovery in network environments, inductive logic p- gramming, abductive reasoning, machine learning, constructive programming as discovery, intelligentnetworkagents, knowledgediscoveryfromunstructuredand multimedia data, statistical methods for knowledge discovery, data and kno- edge visualization, knowledge discovery and human interaction, and human f- tors in knowledge discovery. The DS'99 program committee selected 26 papers and 25 posters/demos from 74 submissions. Papers were selected according to their relevance to the conference, accuracy, signi cance, originality, and presentation quality. Discovery Science Preface Table of Contents The Melting Pot of Automated Discovery: Principles for a New a Science What Is a Discovery Who Are Automated Discoverers Knowledge Discovery in Databases A Rich Brew Is Melting in the Pot Principles of Autonomy Theory of Knowledge Principles of Search Search Spaces Discovery as Problem Solving Search Search Control Beyond Simple-Minded Tools Statistics Conclusions Expressive Probability Models in Science Data, Hypotheses, and Probability Expressive Power First-Order Languages Weighted Majority Decision among Several Region Rules for Scientific Discovery Introduction Motivating Example Decision Tree and Entropy of a Splitting Improvement of Prediction Accuracy by Voting Rule Readability towards Scientific Discovery Weighted Majority among Relatively Powerful Voters Method---Decision by Majority Experimental Results Related Work Concluding Remarks CAEP:Classification by Aggregating Emerging Patterns Introduction Emerging Patterns and Preliminaries Classification by Aggregating EPs Partitioning Dataset to Get EPs of Classes Differentiating Power of Individual EPs Better Overall Accuracy by Aggregated Score Normalizing the Scores to Make Decision The Entire Process Efficient Mining of EPs Reduction of EPs Used Selection of Thresholds and Base Scores Rice-DNA, Sensitivity, and Precision Experimental Results An Appropriate Abstraction for an Attribute-Oriented Induction Introduction Attribute-Oriented Induction Overview Problems Information Theoretical Abstraction System Behavior of Information Gain Ratio Preservation of Class Distribution Using Information Gain Ratio Information Theoretical Abstraction Algorithm An Example of Knowledge Discovery by ITA Experiments on a Census Database Discovery of Discrimination Rules Discovery of Decision Tree from Generalized Database Conclusion Collaborative Hypthesis Testing Processes by Interactive Production Systems Introduction 2-4-6 Task and Hypothesis Testing Strategy Interactive Production System Collaboration Using Different Hypothesis Testing Strategies Collaboration Using Different Hypothesis Testing Strategies and Different Hypothesis Formation Strategies Conclusion Computer Aided Discovery of User's Hidden Interest for Query Restructuring Introduction: WWW and Information Retrieval Interest Discovery System for User Interests Expression Input: Search Query Division of Search Query Acquisition of Web Pages from a Partial Interest Keyword Extraction from Web Pages An Interface for Restructuring the Search Query Keywords to Support Searching Restructuring of Search Queries for Improving Results The Interface Overview of ASDUI Experiments: Discovering Interests and Supplying Keywords Interest Interpretation by the Interface The Role of the Keywords The Restructuring of a Search Query Recalling New User Interest Features and Evaluations Conclusion Iterative Naive Bayes Introduction Naive Bayes Classifier Iterative Naive Bayes Related Work Empirical Evaluation Bias-Variance Decomposition Learning Times The Attribute Redundancy Problem Conclusions and Future Work Schema Design for Causal Law Mining from Incomplete Database Introduction Data Model Association Rule Generation Semantics of Association Rules Rule Filtering Based on AIC Bayesian Network Generation Proposal towards Causal Law Mining Related Works Conclusion Design and Evaluation of an Environment to Automate the Construction of Inductive Applications Introduction Ontologies for Inductive Learning Process Ontology Object Ontology Basic Design of CAMLET Case Studies Using UCI ML Repository A Case Study Using Medical Database with Evaluations from a Domain Expert Related Work Conclusions and Future Work Designing Views in HypothesisCreator: System for Assisting in Discovery Introduction Preliminaries Genomic Data and Experiments Cyclin Genes DNA Replication Genes in Late G1 Cluster Generation with Viewscopes for cDNA Microarray Gene Expression Profile Data Knowledge Extraction of Disordered Regions of Proteins from PDB Conclusion Discovering Poetic Allusion in Anthologies of Classical Japanese Poems Introduction Similarity and Dissimilarity on Strings An Overview of Existing Measures A Unifying Scheme for Existing Measures Similarity Measures on {sc waka} Poems Changes of Line Order Evaluation of Similarity Measure New Similarity Measure Experimental Results Discussion and Future Work Characteristic Sets of Strings Common to Semi-Structured Documents Introduction Preliminaries Mining Algorithm Correctness and Complexity Conclusion Approximation of Optimal Two-Dimensional Association Rules for Categorical Attributes Using Semidefinite Programming* Introduction Problem Formulation Approximation Algorithm Computational Experiments Conclusion Data Mining of Generalized Association Rules Using a Method of Partial-Match Retrieval Introduction Generalized Partial-Match Retrieval Partial-Match Retrieval Using Signatures Data Mining Based on Partial-Match Retrieval Definitions Outline of System Efficient Candidate Generation Optimal Signature Design Conclusions Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms Introduction The Adaptive Sampling Algorithm Examples of Applications Concluding Remarks Scheduled Discovery of Exception Rules Introduction Undirected Discovery of Exception Rules Problem Description Discovery Algorithm Selection of an Atom for a Continuous Attribute Threshold Dependencies Scheduled Discovery of Rule Pairs Data Structure for Discovered Patterns with Multiple Keys Scheduling Policies Experimental Evaluation Data Sets with a Large Number of Rule Pairs Data Sets with a Small Number of Rule Pairs Conclusions Learning in Constraint Databases Introduction Constraint Databases Framework Join Selection Projection Union A New Framework for Learning in Constraint Databases Coverage - Generality Order Learning Setting Our System The Learning Algorithm Efficiency Preliminary Results Conclusion Discover Risky Active Faults by Indexing an Earthquake Sequence Introduction The Outline of Fatal Fault Finder Obtain a Sequence of Focal Faults from Data 2 Applying {it KeyGraph} to Earthquake Predictions Earthquake Mechanisms Considered Applying {it KeyGraph} to a Focal Fault Sequence Experimental Evaluations Results of Japanese Risky Faults Conclusions Machine Discovery Based on the Co-occurence of References in a Search Engine Introduction Related Work A Method of Discovery Based on the Co-occurrence of References Acquisition of HTML Files Extracting Hyperlinks Calculation of Jaccard Coefficient Graph Drawing Experimental Results Discussion Co-occurrence and Semantic Relation Information Filtering Conclusion Smoothness Prior Approach to Explore the Mean Structure in Large Time Series Data Introduction Smoothness Prior Modeling Flexible (Semi-parametric)Modeling Automatic Parameter Determination via Bayesian Interpretation Time Series Interpretation and State Space Modeling Modeling of Space-Time Data Applications Seasonal Adjustment, Earth Tide, and Groundwater Analysis of POS Data Analysis of GPS Data Conclusion Automatic Detection of Geomagnetic Sudden Commencement Using Lifting Wavelet Filters Introduction Wavelet Decomposition of Signals Lifting Wavelet Filter Detection Algorithm Learning Method Detection Theory Automatic Detection of Geomagnetic SC A Set of Old Wavelet Filters Simulation Conclusion A Noise Resistant Model Inference System Introduction Refinements and Markings The {sc Nrmis} Algorithm unhbox voidb @x hbox {texttt {Decision}}xspace text {texttt {Specialize}} text {texttt {Generalize}} unhbox voidb @x hbox {texttt {Compress}}xspace Experimental Results Sparse Data Noisy Data Discussion and Future Work Acknowledgements A Graphical Method for Parameter Learning of Symbolic-Statistical Models Introduction Modifying PRISM to $unhbox voidb @x hbox {PRISM}^{ast }$ Distributional Semantics PRISM Programs A Program Example Learning PRISM Programs Constructing $unhbox voidb @x hbox {PRISM}^{ast }$ Programs Learning $unhbox voidb @x hbox {PRISM}^{ast }$ Programs Graphical EM Algorithm Support Graphs Graphical EM Algorithm Learning HMMs Related Works Discussion Derivation of $unhbox voidb @x hbox {it learn-PRISM}$ and $unhbox voidb @x hbox {it learn-$unhbox voidb @x hbox {PRISM}^{ast }$}$ $unhbox voidb @x hbox {it learn-PRISM}$ $unhbox voidb @x hbox {it learn-$unhbox voidb @x hbox {PRISM}^{ast }$}$ Equivalence of $unhbox voidb @x hbox {it learn-$unhbox voidb @x hbox {PRISM}^{ast }$}$ and $unhbox voidb @x hbox {it learn-gEM}$ Parallel Execution for Speeding Up Inductive Logic Programming Systems Introduction A Hypothesis Search in ILP Parallel Algorithm Implementing the Search Algorithm in KL1 Analysis Experiment Related Work Conclusions Discovery of a Set Nominally Conditioned Polynomials Introduction RF6 Method Basic Framework Numeric Representation of Nominal Conditions Learning as a Single Network Criterion for Network Selection Restoring Nominally Conditioned Polynomials Evaluation by Experiments Artificial Data Set Automobile Data Set Conclusion H-Map: A Dimension Reduction Mapping for a Approximate Retrieval of Multi-Dimensional Data Introduction Metric Space Dimension Reduction Mappings: H-Map and K-L Transformation H-Map K-L Transformation Comparison of H-Map with K-L Transformation Concluding Remarks Normal Form Transformation for Object Recognition Based on Support Vector Machines Introduction Problem for Object Recognition Support Vector Machines Description of the Problem How to Obtain the OSH SVM-NFT Training Method Testing Method Experimental Results Experimental Condition Application to COIL Experimental Results and Discussion Conclusion A Defintion of Discovery in Terms of Generalized Descriptional Complexity Introduction Definitions and Propositions Feature Selection Using Consistency Measure A Model of Children's Vocabulary Acquisition Using Inductive Logic Programming Introduction Cognitive Psychological Constraints Sensory Inputs An ILP Model Current Status and Future Work Automatic Acquisition of Image Processing Procedures from Sample Sets fo Classified Images Based on Requirement of Misclassification Rate Introduction IMPRESS-Pro Conclusion "Thermodynamics" from Time Series Data Analysis Developing a Knowledge Network of URLs Introduction Knowledge on WWW Conclusion Derivation of the Topology Structure from Massive Graph Data Introduction Extension to Graph Structured Data Performance Evaluation Mining Association Algorithm Based on ROC Convex Hull Method in Bibliographic Navigation System Regularization of Linear Regression Models in Various Metric Spaces Argument-Based Agent Systems Motivations and Purposes Outline of Demonstration Argument-Based Agent Systems: A Brief Description Argument Examples Graph-Based Induction for General Graph Structured Data Introduction Graph-Based Induction for General Graphs Application to WWW Browsing Histories Rules Extraction by Constructive Learning of Neural Networks and Hidden-Unit Clustering Introduction Rules Extraction Algorithm Weighted Majority Decision among Region Rules for a Categorical Dataset Rule Discovery Technique Using GP with Crossover to Maintain Variety Purpose Method New Aspect of Work Results Conclusions From Visualization to Interactive Animation of Database Records Introduction Proposed Frameworks and System Overview Concluding Remarks Extraction of Primitive Motion for Human Motion Recognition Finding Meaningful Regions Containing Given Keywords from Large Text Collections Mining Adaptation Rules from Cases in CBR Systems An Automatic Acquisition of Acoustical Units for Speech Recognition Based on Hidden Markov Network Introduction Outline of the Construction Algorithm Experiments Conclusion Knowledge Discovery from Health Data Using Weighted Aggregation Classifiers Search for New Methods for Assignment of Complex Molecular Spectra Automatic Discovery of Definition Patterns Based on the MDL Principle Introduction Discovery of Definition Patterns Algorithm Experiment and Discussion Detection of the Structure of Particle Velocity Distribution by Finite Mixture Distribution Model Mutagenes Discovery Using PC GUHA Software System Discovering the Primary Factors of Cancer from Health and Living Habit Questionnaires Introduction Mining Process and Mining Results Conclusions Author Index

This book constitutes the refereed proceedings of the First International Conference on Discovery Science, DS'98, held in Fukuoka, Japan, in December 1998.
The volume presents 28 revised full papers selected from a total of 76 submissions. Also included are five invited contributions and 34 selected poster presentations. The ultimate goal of DS'98 and this volume is to establish discovery science as a new field of research and development. The papers presented relate discovery science to areas as formal logic, knowledge processing, machine learning, automated deduction, searching, neural networks, database management, information retrieval, intelligent network agents, visualization, knowledge discovery, data mining, information extraction, etc.