Evolutionary fusion of a multi-classifier system for efficient face recognition

In this paper an evolutionary classifier fusion method inspired by biological evolution is presented to optimize the performance of a face recognition system. Initially, different illumination environments are modeled as multiple contexts using unsupervised learning and then the optimized classifier ensemble is searched for each context using a Genetic Algorithm (GA). For each context, multiple optimized classifiers are searched; each of which are referred to as a context based classifier. An evolutionary framework comprised of a combination of these classifiers is then applied to optimize face recognition as a whole. Evolutionary classifier fusion is compared with the simple adaptive system. Experiments are carried out using the Inha database and FERET database. Experimental results show that the proposed evolutionary classifier fusion method gives superior performance over other methods without using evolutionary fusion. Recommended by Guest Editor Daniel Howard. This work was supported by INHA UNIVERSITY Research Grant. Zhan Yu received the B.E. degree in Software Engineering from Xiamen University, China, in 2008. He is currently a master student in Intelligent Technology Lab, Computer and Information Department, Inha University, Korea. He has research interests in image processing, pattern recognition, computer vision, machine learning and statistical inference and computating. Mi Young Nam received the B.Sc. and M.Sc. degrees in Computer Science from the University of Silla Busan, Korea in 1995 and 2001 respectively and the Ph.D. degree in Computer Science & Engineering from the University of Inha, Korea in 2006. Currently, She is Post-Doctor course in Intelligent Technology Laboratory, Inha University, Korea. She’s research interest includes biometrics, pattern recognition, computer vision, image processing. Suman Sedai received the M.S. degree in Software Engineering from Inha University, China, in 2008. He is currently a Doctoral course in Western Australia University, Australia. He has research interests in image processing, pattern recognition, computer vision, machine learning. Phill Kyu Rhee received the B.S. degree in Electrical Engineering from the Seoul University, Seoul, Korea, the M.S. degree in Computer Science from the East Texas State University, Commerce, TX, and the Ph.D. degree in Computer Science from the University of Louisiana, Lafayette, LA, in 1982, 1986, and 1990 respectively. During 1982–1985 he was working in the System Engineering Research Institute, Seoul, Korea as a research scientist. In 1991 he joined the Electronic and Telecommunication Research Institute, Seoul, Korea, as a Senior Research Staff. Since 1992, he has been an Associate Professor in the Department of Computer Science and Engineering of the Inha University, Incheon, Korea and since 2001, he is a Professor in the same department and university. His current research interests are pattern recognition, machine intelligence, and parallel computer architecture. dr. rhee is a Member of the IEEE Computer Society and KISS (Korea Information Science Society).     

Hierarchies of parallel rewriting P systems — A survey

The paper is about some families of rewriting P systems, where the application of evolution rules is extended from the classical sequential rewriting to the parallel one (as, for instance, in Lindenmayer systems). As a result, consistency problems for the communication of strings may arise. Three variants of parallel rewriting P systems (already present in the literature) are considered here, together with the strategies they use to face the communication problem, and some parallelism methods for string rewriting are defined. We give a survey of all known results about each variant and we state some relations among the three variants, thus establishing hierarchies of parallel rewriting P systems. Various open problems related to the subject are also presented. Danicla Besozzi: She is assistant professor at the University of Milano. She received her M.S. in Mathematics (2000) from the University of Como and Ph.D. in Computer Science (2004) from the University of Milano. Her research interests cover topics in Formal Language Theory, Molecular Computing, Systems Biology. She is member of EATCS (European Association for Theoretical Computer Science) and EMCC (European Molecular Computing Consortium). Giancarlo Mauri: He is full professor of Computer Science at the University of Milano-Bicocca. His research interests are mainly in the area of theoretical computer science, and include: formal languages and automata, computational complexity, computational learning theory, soft computing techniques, cellular automata, bioinformatics and molecular computing. On these subjects, he published more than 150 scientific papers in international journals, contributed volumes and conference proceedings. Claudio Zandron: He received Ph.D. in Computer Science at the University of Milan, Italy, in 2001. Since 2002 he is assistant professor at the University of Milano-Bicocca, Italy. He is member of the EATCS (European Association for Theoretical Computer Science) and of EMCC (European Molecular Computing Consortium). His research interests are Molecular Computing (DNA and Membrane Computing) and Formal Languages.     

Learning Horn definitions: Theory and an application to planning

A Horn definition is a set of Horn clauses with the same predicate in all head literals. In this paper, we consider learning non-recursive, first-order Horn definitions from entailment. We show that this class is exactly learnable from equivalence and membership queries. It follows then that this class is PAC learnable using examples and membership queries. Finally, we apply our results to learning control knowledge for efficient planning in the form of goal-decomposition rules. Chandra Reddy, Ph.D.: He is currently a doctoral student in the Department of Computer Science at Oregon State University. He is completing his Ph.D. on June 30, 1998. His dissertation is entitled “Learning Hierarchical Decomposition Rules for Planning: An Inductive Logic Programming Approach.” Earlier, he had an M. Tech in Artificial Intelligence and Robotics from University of Hyderabad, India, and an M.Sc.(tech) in Computer Science from Birla Institute of Technology and Science, India. His current research interests broadly fall under machine learning and planning/scheduling—more specifically, inductive logic programming, speedup learning, data mining, and hierarchical planning and optimization. Prasad Tadepalli, Ph.D.: He has an M.Tech in Computer Science from Indian Institute of Technology, Madras, India and a Ph.D. from Rutgers University, New Brunswick, USA. He joined Oregon State University, Corvallis, as an assistant professor in 1989. He is now an associate professor in the Department of Computer Science of Oregon State University. His main area of research is machine learning, including reinforcement learning, inductive logic programming, and computational learning theory, with applications to classification, planning, scheduling, manufacturing, and information retrieval.     

Adaptive group scheduling mechanism using mobile agents in peer-to-peer grid computing environment

Peer-to-peer grid computing is an attractive computing paradigm for high throughput applications. However, both volatility due to the autonomy of volunteers (i.e., resource providers) and the heterogeneous properties of volunteers are challenging problems in the scheduling procedure. Therefore, it is necessary to develop a scheduling mechanism that adapts to a dynamic peer-to-peer grid computing environment. In this paper, we propose a Mobile Agent based Adaptive Group Scheduling Mechanism (MAAGSM). The MAAGSM classifies and constructs volunteer groups to perform a scheduling mechanism according to the properties of volunteers such as volunteer autonomy failures, volunteer availability, and volunteering service time. In addition, the MAAGSM exploits a mobile agent technology to adaptively conduct various scheduling, fault tolerance, and replication algorithms suitable for each volunteer group. Furthermore, we demonstrate that the MAAGSM improves performance by evaluating the scheduling mechanism in Korea@Home. SungJin Choi is a Ph.D. student in the Department of Computer Science and Engineering at Korea University. His research interests include mobile agent, peer-to-peer computing, grid computing, and distributed systems. Mr. Choi received a M.S. in computer science from Korea University. He is a student member of the IEEE. MaengSoon Baik is a senior research member at the SAMSUNG SDS Research & Develop Center. His research interests include mobile agent, grid computing, server virtualization, storage virtualization, and utility computing. Dr. Baik received a Ph.D. in computer science from Korea University. JoonMin Gil is a professor in the Department of Computer Science Education at Catholic University of Daegu, Korea. His recent research interests include grid computing, distributed and parallel computing, Internet computing, P2P networks, and wireless networks. Dr. Gil received his Ph.D. in computer science from Korea University. He is a member of the IEEE and the IEICE. SoonYoung Jung is a professor in the Department of Computer Science Education at Korea University. His research interests include grid computing, web-based education systems, database systems, knowledge management systems, and mobile computing. Dr. Jung received his Ph.D. in computer science from Korea University. ChongSun Hwang is a professor in the Department of Computer Science and Engineering at Korea University. His research interests include distributed systems, distributed algorithms, and mobile computing. Dr. Hwang received a Ph.D. in statistics and computer science from the University of Georgia.     

Using discriminant analysis for multi-class classification: an experimental investigation

Many supervised machine learning tasks can be cast as multi-class classification problems. Support vector machines (SVMs) excel at binary classification problems, but the elegant theory behind large-margin hyperplane cannot be easily extended to their multi-class counterparts. On the other hand, it was shown that the decision hyperplanes for binary classification obtained by SVMs are equivalent to the solutions obtained by Fisher's linear discriminant on the set of support vectors. Discriminant analysis approaches are well known to learn discriminative feature transformations in the statistical pattern recognition literature and can be easily extend to multi-class cases. The use of discriminant analysis, however, has not been fully experimented in the data mining literature. In this paper, we explore the use of discriminant analysis for multi-class classification problems. We evaluate the performance of discriminant analysis on a large collection of benchmark datasets and investigate its usage in text categorization. Our experiments suggest that discriminant analysis provides a fast, efficient yet accurate alternative for general multi-class classification problems. Tao Li is currently an assistant professor in the School of Computer Science at Florida International University. He received his Ph.D. degree in Computer Science from University of Rochester in 2004. His primary research interests are: data mining, machine learning, bioinformatics, and music information retrieval. Shenghuo Zhu is currently a researcher in NEC Laboratories America, Inc. He received his B.E. from Zhejiang University in 1994, B.E. from Tsinghua University in 1997, and Ph.D degree in Computer Science from University of Rochester in 2003. His primary research interests include information retrieval, machine learning, and data mining. Mitsunori Ogihara received a Ph.D. in Information Sciences at Tokyo Institute of Technology in 1993. He is currently Professor and Chair of the Department of Computer Science at the University of Rochester. His primary research interests are data mining, computational complexity, and molecular computation.     

Applying language modeling to session identification from database trace logs

A database session is a sequence of requests presented to the database system by a user or an application to achieve a certain task. Session identification is an important step in discovering useful patterns from database trace logs. The discovered patterns can be used to improve the performance of database systems by prefetching predicted queries, rewriting the current query or conducting effective cache replacement.In this paper, we present an application of a new session identification method based on statistical language modeling to database trace logs. Several problems of the language modeling based method are revealed in the application, which include how to select values for the parameters of the language model, how to evaluate the accuracy of the session identification result and how to learn a language model without well-labeled training data. All of these issues are important in the successful application of the language modeling based method for session identification. We propose solutions to these open issues. In particular, new methods for determining an entropy threshold and the order of the language model are proposed. New performance measures are presented to better evaluate the accuracy of the identified sessions. Furthermore, three types of learning methods, namely, learning from labeled data, learning from semi-labeled data and learning from unlabeled data, are introduced to learn language models from different types of training data. Finally, we report experimental results that show the effectiveness of the language model based method for identifying sessions from the trace logs of an OLTP database application and the TPC-C Benchmark. Xiangji Huang joined York University as an Assistant Professor in July 2003 and then became a tenured Associate Professor in May 2006. Previously, he was a Post Doctoral Fellow at the School of Computer Science, University of Waterloo, Canada. He did his Ph.D. in Information Science at City University in London, England, with Professor Stephen E. Robertson. Before he went into his Ph.D. program, he worked as a lecturer for 4 years at Wuhan University. He also worked in the financial industry in Canada doing E-business, where he was awarded a CIO Achievement Award, for three and half years. He has published more than 50 refereed papers in journals, book chapter and conference proceedings. His Master (M.Eng.) and Bachelor (B.Eng.) degrees were in Computer Organization & Architecture and Computer Engineering, respectively. His research interests include information retrieval, data mining, natural language processing, bioinformatics and computational linguistics. Qingsong Yao is a Ph.D. student in the Department of Computer Science and Engineering at York University, Toronto, Canada. His research interests include database management systems and query optimization, data mining, information retrieval, natural language processing and computational linguistics. He earned his Master's degree in Computer Science from Institute of Software, Chinese Academy of Science in 1999 and Bachelor's degree in Computer Science from Tsinghua University. Aijun An is an associate professor in the Department of Computer Science and Engineering at York University, Toronto, Canada. She received her Bachelor's and Master's degrees in Computer Science from Xidian University in China. She received her PhD degree in Computer Science from the University of Regina in Canada in 1997. She worked at the University of Waterloo as a postdoctoral fellow from 1997 to 1999 and as a research assistant professor from 1999 to 2001. She joined York University in 2001. She has published more than 60 papers in refereed journals and conference proceedings. Her research interests include data mining, machine learning, and information retrieval.     

On the suitability of Biological structure determination by electron microscopy to Grid Computing

The present contribution describes a potential application of Grid Computing in Bioinformatics. High resolution structure determination of biological specimens is critical in BioSciences to understanding the biological function. The problem is computational intensive. Distributed and Grid Computing are thus becoming essential. This contribution analyzes the use of Grid Computing and its potential benefits in the field of electron microscope tomography of biological specimens. Jose-Jesus Fernandez, Ph.D.: He received his M.Sc. and Ph.D. degrees in Computer Science from the University of Granada, Spain, in 1992 and 1997, respectively. He was a Ph.D. student at the Bio-Computing unit of the National Center for BioTechnology (CNB) from the Spanish National Council of Scientific Research (CSIC), Madrid, Spain. He became an Assistant Professor in 1997 and, subsequently, Associate Professor in 2000 in Computer Architecture at the University of Almeria, Spain. He is a member of the supercomputing-algorithms research group. His research interests include high performance computing (HPC), image processing and tomography. Jose-Roman Bilbao-Castro: He received his M.Sc. degree in Computer Science from the University of Almeria in 2001. He is currently a Ph.D. student at the BioComputing unit of the CNB (CSIC) through a Ph.D. CSIC-grant in conjuction with Dept. Computer Architecture at the University of Malaga (Spain). His current research interestsinclude tomography, HPC and distributed and grid computing. Roberto Marabini, Ph.D.: He received the M.Sc. (1989) and Ph.D. (1995) degrees in Physics from the University Autonoma de Madrid (UAM) and University of Santiago de Compostela, respectively. He was a Ph.D. student at the BioComputing Unit at the CNB (CSIC). He worked at the University of Pennsylvania and the City University of New York from 1998 to 2002. At present he is an Associate Professor at the UAM. His current research interests include inverse problems, image processing and HPC. Jose-Maria Carazo, Ph.D.: He received the M.Sc. degree from the Granada University, Spain, in 1981, and got his Ph.D. in Molecular Biology at the UAM in 1984. He left for Albany, NY, in 1986, coming back to Madrid in 1989 to set up the BioComputing Unit of the CNB (CSIC). He was involved in the Spanish Ministry of Science and Technology as Deputy General Director for Research Planning. Currently, he keeps engaged in his activities at the CNB, the Scientific Park of Madrid and Integromics S.L. Immaculada Garcia, Ph.D.: She received her B.Sc. (1977) and Ph.D. (1986) degrees in Physics from the Complutense University of Madrid and University of Santiago de Compostela, respectively. From 1977 to 1987 she was an Assistant professor at the University of Granada, from 1987 to 1996 Associate professor at the University of Almeria and since 1997 she is a Full Professor and head of Dept. Computer Architecture. She is head of the supercomputing-algorithms research group. Her research interest lies in HPC for irregular problems related to image processing, global optimization and matrix computation.     

Equilibrium of E-markets populated with reputation oriented learning agents

In this paper, we propose reputation oriented reinforcement learning algorithms for buying and selling agents in electronic marketplaces. We consider the fact that the quality of a good offered by multiple selling agents may not be the same, and a selling agent may alter the quality of its goods. In our approach, buying agents learn to avoid the risk of purchasing low quality goods and to maximize their expected value of goods by dynamically maintaining sets of reputable and disreputable sellers. Selling agents learn to maximize their expected profits by adjusting product prices and optionally altering the quality of their goods. This paper focusses on presenting results from experiments investigating the behaviour of an e-market populated with our buying and selling agents. Our results show that such a market can reach an equilibrium state where the agent population remains stable, and this equilibrium is optimal for the participant agents. Thomas Tran, Ph.D.: He is an Assistant Professor in the School of Information Technology and Engineering at the University of Ottawa. He received his Ph.D. from the University of Waterloo in 2004. His current research work is on Multi-Agent Systems, Intelligent Agents, Reinforcement Learning, Trust and Reputation Modelling, Agent Negotiation, Mechanism Design and Applications of AI to E-Commerce. Robin Cohen, Ph.D.: She is a Professor in the School of Computer Science at the University of Waterloo. She received her Ph.D. from the University of Toronto in 1983. Her current research work is on User Modeling, Intelligent Interaction, Multi-Agent Systems, Adjustable Autonomy and Mixed-Initiative Systems and Dialogue, including Applications to E-Commerce.     

A purely reactive navigation scheme for dynamic environments using Case-Based Reasoning

This paper presents a new sonar based purely reactive navigation technique for mobile platforms. The method relies on Case-Based Reasoning to adapt itself to any robot and environment through learning, both by observation and self experience. Thus, unlike in other reactive techniques, kinematics or dynamics do not need to be explicitly taken into account. Also, learning from different sources allows combination of their advantages into a safe and smooth path to the goal. The method has been succesfully implemented on a Pioneer robot wielding 8 Polaroid sonar sensors. Cristina Urdiales is a Lecturer at the Department of Tecnología Electrónica (DTE) of the University of Málaga (UMA). She received a MSc degree in Telecommunication Engineering at the Universidad Politécnica de Madrid (UPM) and her Ph.D. degree at University of Málaga (UMA). Her research is focused on robotics and computer vision. E.J. Pérez was born in Barcelona, Spain, in 1974. He received his title of Telecommunication Engineering from the University of Málaga, Spain, in 1999. During 1999 he worked in a research project under a grant by the Spanish CYCIT. From 2000 to the present day he has worked as Assistant Professor in the Department of Tecnología Electrónica of the University of Málaga. His research is focused on robotics and artificial vision. Javier Vázquez-Salceda is an Associate Researcher of the Artificial Intelligence Section of the Software Department (LSI), at the Technical University of Catalonia (UPC). Javier obtained an MSc degree in Computer Science at UPC. After his master studies he became research assistant in the KEMLg Group at UPC. In 2003 he presented his Ph.D. dissertation (with honours), which has been awarded with the 2003 ECCAI Artificial Intelligence Dissertation Award. The dissertation has been also recently published as a book by Birkhauser-Verlag. From 2003 to 2005 he was researcher in the Intelligent Systems Group at Utrecht University. Currently he is again member of the KEMLg Group at UPC. His research is focused on theoretical and applied issues of Normative Systems, software and physical agents' autonomy and social control, especially in distributed applications for complex domains such as eCommerce or Medicine. Miquel Sànchez-Marrè (Barcelona, 1964) received a Ph.D. in Computer Science in 1996 from the Technical University of Catalonia (UPC). He is Associate Professor in the Computer Software Department (LSI) of the UPC since 1990 (tenure 1996). He was the head of the Artificial Intelligence section of LSI (1997–2000). He is a pioneer member of International Environmental Modelling and Software Society (IEMSS) and a board member of IEMSS also, since 2000. He is a member of the Editorial Board of International Journal of Applied Intelligence, since October 2001. Since October 2004 he is Associate Editor of Environmental Modelling and Software journal. His main research topics are case-based reasoning, machine learning, knowledge acquisition and data mining, knowledge engineering, intelligent decision-support systems, and integrated AI architectures. He has an special interest on the application of AI techniques to Environmental Decision Support Systems. Francisco Sandoval was born in Spain in 1947. He received the title of Telecommunication Engineering and Ph.D. degree from the Technical University of Madrid, Spain, in 1972 and 1980, respectively. From 1972 to 1989 he was engaged in teaching and research in the fields of opto-electronics and integrated circuits in the Universidad Politécnica de Madrid (UPM) as an Assistant Professor and a Lecturer successively. In 1990 he joined the University of Málaga as Full Professor in the Department of Tecnología Electrónica. He is currently involved in autonomous systems and foveal vision, application of Artificial Neural Networks to Energy Management Systems, and in Broad Band and Multimedia Communication.     

Ranking-based evaluation of regression models

We suggest the use of ranking-based evaluation measures for regression models, as a complement to the commonly used residual-based evaluation. We argue that in some cases, such as the case study we present, ranking can be the main underlying goal in building a regression model, and ranking performance is the correct evaluation metric. However, even when ranking is not the contextually correct performance metric, the measures we explore still have significant advantages: They are robust against extreme outliers in the evaluation set; and they are interpretable. The two measures we consider correspond closely to non-parametric correlation coefficients commonly used in data analysis (Spearman's ρ and Kendall's τ); and they both have interesting graphical representations, which, similarly to ROC curves, offer useful various model performance views, in addition to a one-number summary in the area under the curve. An interesting extension which we explore is to evaluate models on their performance in “partially” ranking the data, which we argue can better represent the utility of the model in many cases. We illustrate our methods on a case study of evaluating IT Wallet size estimation models for IBM's customers. Saharon Rosset is Research Staff Member in the Data Analytics Research Group at IBM's T. J. Watson Research Center. He received his B.S. in Mathematics and M.Sc., in Statistics from Tel Aviv University in Israel, and his Ph.D. in Statistics from Stanford University in 2003. In his research, he aspires to develop practically useful predictive modeling methodologies and tools, and apply them to solve problems in business and scientific domains. Currently, his major projects include work on customer wallet estimation and analysis of genetic data. Claudia Perlich has received a M.Sc. in Computer Science from Colorado University at Boulder, a Diploma in Computer Science from Technische Universitaet in Darmstadt, and her Ph.D. in Information Systems from Stern School of Business, New York University. Her Ph.D. thesis concentrated on probability estimation in multi-relational domains that capture information of multiple entity types and relationships between them. Her dissertation was recognized as an additional winner of the International SAP Doctoral Support Award Competition. Claudia joined the Data Analytics Research group at IBM's T.J. Watson Research Center as a Research Staff Member in October 2004. Her research interests are in statistical machine learning for complex real-world domains and business applications. Bianca Zadrozny is currently an associate professor at the Computer Science Department of Federal Fluminense University in Brazil. Her research interests are in the areas of applied machine learning and data mining. She received her B.Sc. in Computer Engineering from the Pontifical Catholic University in Rio de Janeiro, Brazil, and her M.Sc. and Ph.D. in Computer Science from the University of California at San Diego. She has also worked as a research staff member in the data analytics research group at IBM T.J. Watson Research Center.     

Belief revision via Lamarckian evolution

We present a system for performing belief revision in a multi-agent environment. The system is called GBR (Genetic Belief Revisor) and it is based on a genetic algorithm. In this setting, different individuals are exposed to different experiences. This may happen because the world surrounding an agent changes over time or because we allow agents exploring different parts of the world. The algorithm permits the exchange of chromosomes from different agents and combines two different evolution strategies, one based on Darwin’s and the other on Lamarck’s evolutionary theory. The algorithm therefore includes also a Lamarckian operator that changes the memes of an agent in order to improve their fitness. The operator is implemented by means of a belief revision procedure that, by tracing logical derivations, identifies the memes leading to contradiction. Moreover, the algorithm comprises a special crossover mechanism for memes in which a meme can be acquired from another agent only if the other agent has “accessed” the meme, i.e. if an application of the Lamarckian operator has read or modified the meme. Experiments have been performed on the η-queen problem and on a problem of digital circuit diagnosis. In the case of the η-queen problem, the addition of the Lamarckian operator in the single agent case improves the fitness of the best solution. In both cases the experiments show that the distribution of constraints, even if it may lead to a reduction of the fitness of the best solution, does not produce a significant reduction. Evelina Lamma, Ph.D.: She is Full Professor at the University of Ferrara. She got her degree in Electrical Engineering at the University of Bologna in 1985, and her Ph.D. in Computer Science in 1990. Her research activity centers on extensions of logic programming languages and artificial intelligence. She was coorganizers of the 3rd International Workshop on Extensions of Logic Programming ELP92, held in Bologna in February 1992, and of the 6th Italian Congress on Artificial Intelligence, held in Bologna in September 1999. Currently, she teaches Artificial Intelligence and Fondations of Computer Science. Fabrizio Riguzzi, Ph.D.: He is Assistant Professor at the Department of Engineering of the University of Ferrara, Italy. He received his Laurea from the University of Bologna in 1995 and his Ph.D. from the University of Bologna in 1999. He joined the Department of Engineering of the University of Ferrara in 1999. He has been a visiting researcher at the University of Cyprus and at the New University of Lisbon. His research interests include: data mining (and in particular methods for learning from multirelational data), machine learning, belief revision, genetic algorithms and software engineering. Luís Moniz Pereira, Ph.D.: He is Full Professor of Computer Science at Departamento de Informática, Universidade Nova de Lisboa, Portugal. He received his Ph.D. in Artificial Intelligence from Brunel University in 1974. He is the director of the Artificial Intelligence Centre (CENTRIA) at Universidade Nova de Lisboa. He has been elected Fellow of the European Coordinating Committee for Artificial Intelligence in 2001. He has been a visiting Professor at the U. California at Riverside, USA, the State U. NY at Stony Brook, USA and the U. Bologna, Italy. His research interests include: knowledge representation, reasoning, learning, rational agents and logic programming.     

Relative positioning for team robot navigation

The research presented in this paper approaches the issue of robot team navigation using relative positioning. With this approach each robot is equipped with sensors that allow it to independently estimate the relative direction of an assigned leader. Acoustic sensor systems are used and were seen to work very effectively in environments where datum relative positioning systems (such as GPS or acoustic transponders) are typically ineffective. While acoustic sensors provide distinct advantages, the variability of the acoustic environment presents significant control challenges. To address this challenge, directional control of the robot was accomplished with a feed forward neural network trained using a genetic algorithm, and a new approach to training using recent memories was successfully implemented. The design of this controller is presented and its performance is compared with more traditional classic logic and behavior controllers. Patrick McDowell received his bachelor's degree in Computer Science in 1984 from the University of Idaho. He spent the next 15 years working as a computer scientist for a small defense contractor where he specialized in real time data acquisition, application development, and image processing. In 1999 he received his master's degree in computer science from the University of Southern Mississippi. In 2000 he began work at the Naval Research Lab where he has focused on application of machine learning techniques to autonomous underwater navigation. In 2005 he received his Ph.D. in Computer Science from Louisiana State University. His research interests include legged robotics, machine learning, and artificial intelligence. In Fall of 2006 he joined Southeastern Louisiana University as an assistant professor of Computer Science. Brian S. Bourgeois received his Ph.D. in Electrical Engineering from Tulane University located in New Orleans, LA in 1991. Since then he has worked at the Stennis Space Center, MS detachment of the Naval Research Laboratory. He has worked on research projects spanning an array of technologies including airborne survey sytems, acoustic backscattering, bathymetry and imaging sonar systems, the ORCA unmanned underwater vehicle and the development of an autonomous survey system for hydrographic survey ships. He is presently the head of the Position, Navigation and Timing team at NRL with research interests including underwater positioning and communications and autonomous navigation. Ms. McDowell received her M.S. in Applied Physics in 2002 from the University or New Orleans. She is presently a candidate for a Ph. D. in Engineering and Applied Science. She joined the Naval Research Laboratory in 1991 as a research engineer and has spent most of that time working in experimental and theoretical acoustic modeling. Ms. McDowell's specific research interest lie in the areas of sonar performance analysis. Dr. S. S. Iyengar is the Chairman and Roy Paul Daniels Chaired Professor of Computer Science at Louisiana State University and is also Satish Dhawan Chaired Professor at Indian Institute of Science. He has been involved with research in high-performance algorithms, data structures, sensor fusion, data mining, and intelligent systems since receiving his Ph.D. degree (1974) and his M.S. from the Indian Institute of Science (1970). He has been a consultant to several industrial and government organizations (JPL, NASA etc.). In 1999, Professor Iyengar won the most prestigious research award titled Distinguished Research Award and a university medal for his research contributions in optimal algorithms for sensor fusion/image processing. Dr. Jianhua Chen received her Ph.D. in computer science in 1988 from Jilin University, Chang Chun, China. In August 1988, She joined the Computer Science Department of Louisiana State University, Baton Rouge, USA, where she is currently an associate professor. Dr. Chen's research interests include Machine Learning and Data Mining, Fuzzy Sets and Systems, Knowledge Representation and Reasoning.     

Inference of abduction theories for handling incompleteness in first-order learning

In real-life domains, learning systems often have to deal with various kinds of imperfections in data such as noise, incompleteness and inexactness. This problem seriously affects the knowledge discovery process, specifically in the case of traditional Machine Learning approaches that exploit simple or constrained knowledge representations and are based on single inference mechanisms. Indeed, this limits their capability of discovering fundamental knowledge in those situations. In order to broaden the investigation and the applicability of machine learning schemes in such particular situations, it is necessary to move on to more expressive representations which require more complex inference mechanisms. However, the applicability of such new and complex inference mechanisms, such as abductive reasoning, strongly relies on a deep background knowledge about the specific application domain. This work aims at automatically discovering the meta-knowledge needed to abduction inference strategy to complete the incoming information in order to handle cases of missing knowledge. Floriana Esposito received the Laurea degree in electronic Physics from the University of Bari, Italy, in 1970. Since 1994 is Full Professor of Computer Science at the University of Bari and Dean of the Faculty of Computer Science from 1997 to 2002. She founded and chairs the Laboratory for Knowledge Acquisition and Machine Learning of the Department of Computer Science. Her research activity started in the field of numerical models and statistical pattern recognition. Then her interests moved to the field of Artificial Intelligence and Machine Learning. The current research concerns the logical and algebraic foundations of numerical and symbolic methods in machine learning with the aim of the integration, the computational models of incremental and multistrategy learning, the revision of logical theories, the knowledge discovery in data bases. Application include document classification and understanding, content based document retrieval, map interpretation and Semantic Web. She is author of more than 270 scientific papers and is in the scientific committees of many international scientific Conferences in the field of Artificial Intelligence and Machine Learning. She co-chaired ICML96, MSL98, ECML-PKDD 2003, IEA-AIE 2005, ISMIS 2006. Stefano Ferilli was born in 1972. After receiving his Laurea degree in Information Science in 1996, he got a Ph.D. in Computer Science at the University of Bari in 2001. Since 2002 he is an Assistant Professor at the Department of Computer Science of the University of Bari. His research interests are centered on Logic and Algebraic Foundations of Machine Learning, Inductive Logic Programming, Theory Revision, Multi-Strategy Learning, Knowledge Representation, Electronic Document Processing and Digital Libraries. He participated in various National and European (ESPRIT and IST) projects concerning these topics, and is a (co-)author of more than 80 papers published on National and International journals, books and conferences/workshops proceedings. Teresa M.A. Basile got the Laurea degree in Computer Science at the University of Bari, Italy (2001). In March 2005 she discussed a Ph.D. thesis in Computer Science at the University of Bari titled “A Multistrategy Framework for First-Order Rules Learning.” Since April 2005, she is a research at the Computer Science Department of the University of Bari working on methods and techniques of machine learning for the Semantic Web. Her research interests concern the investigation of symbolic machine learning techniques, in particular of the cooperation of different inferences strategies in an incremental learning framework, and their application to document classification and understanding based on their semantic. She is author of about 40 papers published on National and International journals and conferences/workshops proceedings and was/is involved in various National and European projects. Nicola Di Mauro got the Laurea degree in Computer Science at the University of Bari, Italy. From 2001 he went on making research on machine learning in the Knowledge Acquisition and Machine Learning Laboratory (LACAM) at the Department of Computer Science, University of Bari. In March 2005 he discussed a Ph.D. thesis in Computer Science at the University of Bari titled “First Order Incremental Theory Refinement” which faces the problem of Incremental Learning in ILP. Since January 2005, he is an assistant professor at the Department of Computer Science, University of Bari. His research activities concern Inductive Logic Programming (ILP), Theory Revision and Incremental Learning, Multistrategy Learning, with application to Automatic Document Processing. On such topics HE is author of about 40 scientific papers accepted for presentation and publication on international and national journals and conference proceedings. He took part to the European projects 6th FP IP-507173 VIKEF (Virtual Information and Knowledge Environment Framework) and IST-1999-20882 COLLATE (Collaboratory for Annotation, Indexing and Retrieval of Digitized Historical Archive Materials), and to various national projects co-funded by the Italian Ministry for the University and Scientific Research.     

Design and analysis of the Dual-Torus Network

In this paper, we propose a new topology called theDual Torus Network (DTN) which is constructed by adding interleaved edges to a torus. The DTN has many advantages over meshes and tori such as better extendibility, smaller diameter, higher bisection width, and robust link connectivity. The most important property of the DTN is that it can be partitioned into sub-tori of different sizes. This is not possible for mesh and torus-based systems. The DTN is investigated with respect to allocation, embedding, and fault-tolerant embedding. It is shown that the sub-torus allocation problem in the DTN reduces to the sub-mesh allocation problem in the torus. With respect to embedding, it is shown that a topology that can be embedded into a mesh with dilation δ can also be embedded into the DTN with less dilation. In fault-tolerant embedding, a fault-tolerant embedding method based on rotation, column insertion, and column skip is proposed. This method can embed any rectangular grid into its optimal square DTN when the number of faulty nodes is fewer than the number of unused nodes. In conclusion, the DTN is a scalable topology well-suited for massively parallel computation. Sang-Ho Chae, M.S.: He received the B.S. in the Computer Science and Engineering from the Pohang University of Science and Technology (POSTECH) in 1994, and the M.E. in 1996. Since 1996, he works as an Associate Research Engineer in the Central R&D Center of the SK Telecom Co. Ltd. He took part in developing SK Telecom Short Message Server whose subscribers are now over 3.5 million and Advanced Paging System in which he designed and implemented high availability concepts. His research interests are the Fault Tolerance, Parallel Processing, and Parallel Topolgies. Jong Kim, Ph.D.: He received the B.S. degree in Electronic Engineering from Hanyang University, Seoul, Korea, in 1981, the M.S. degree in Computer Science from the Korea Advanced Institute of Science and Technology, Seoul, Korea, in 1983, and the Ph.D. degree in Computer Engineering from Pennsylvania State University, U.S.A., in 1991. He is currently an Associate Professor in the Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, Korea. Prior to this appointment, he was a research fellow in the Real-Time Computing Laboratory of the Department of Electrical Engineering and Computer Science at the University of Michigan from 1991 to 1992. From 1983 to 1986, he was a System Engineer in the Korea Securities Computer Corporation, Seoul, Korea. His major areas of interest are Fault-Tolerant Computing, Performance Evaluation, and Parallel and Distributed Computing. Sung Je Hong, Ph.D.: He received the B.S. degree in Electronics Engineering from Seoul National University, Korea, in 1973, the M.S. degree in Computer Science from Iowa State University, Ames, U.S.A., in 1979, and the Ph.D. degree in Computer Science from the University of Illinois, Urbana, U.S.A., in 1983. He is currently a Professor in the Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, Korea. From 1983 to 1989, he was a staff member of Corporate Research and Development, General Electric Company, Schenectady, NY, U.S.A. From 1975 to 1976, he was with Oriental Computer Engineering, Korea, as a Logic Design Engineer. His current research interest includes VLSI Design, CAD Algorithms, Testing, and Parallel Processing. Sunggu Lee, Ph.D.: He received the B.S.E.E. degree with highest distinction from the University of Kansas, Lawrence, in 1985 and the M.S.E. and Ph.D. degrees from the University of Michigan, Ann Arbor, in 1987 and 1990, respectively. He is currently an Associate Professor in the Department of Electronic and Electrical Engineering at the Pohang University of Science and Technology (POSTECH), Pohang, Korea. Prior to this appointment, he was an Associate Professor in the Department of Electrical Engineering at the University of Delaware in Newark, Delaware, U.S.A. From June 1997 to July 1998, he spent one year as a Visiting Scientist at the IBM T. J. Watson Research Center. His research interests are in Parallel, Distributed, and Fault-Tolerant Computing. Currently, his main research focus is on the high-level and low-level aspects of Inter-Processor Communications for Parallel Computers.     

Inductive logic programming for relational knowledge discovery

Inductive logic programming (ILP) is concerned with the induction of logic programs from examples and background knowledge. In ILP, the shift of attention from program synthesis to knowledge discovery resulted in advanced techniques that are practically applicable for discovering knowledge in relational databases. This paper gives a brief introduction to ILP, presents selected ILP techniques for relational knowledge discovery and reviews selected ILP applications. Nada Lavrač, Ph.D.: She is a senior research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1978) and a visiting professor at the Klagenfurt University, Austria (since 1987). Her main research interest is in machine learning, in particular inductive logic programming and intelligent data analysis in medicine. She received a BSc in Technical Mathematics and MSc in Computer Science from Ljubljana University, and a PhD in Technical Sciences from Maribor University, Slovenia. She is coauthor of KARDIO: A Study in Deep and Qualitative Knowledge for Expert Systems, The MIT Press 1989, and Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994, and coeditor of Intelligent Data Analysis in Medicine and Pharmacology, Kluwer 1997. She was the coordinator of the European Scientific Network in Inductive Logic Programming ILPNET (1993–1996) and program cochair of the 8th European Machine Learning Conference ECML’95, and 7th International Workshop on Inductive Logic Programming ILP’97. Sašo Džeroski, Ph.D.: He is a research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1989). He has held visiting researcher positions at the Turing Institute, Glasgow (UK), Katholieke Universiteit Leuven (Belgium), German National Research Center for Computer Science (GMD), Sankt Augustin (Germany) and the Foundation for Research and Technology-Hellas (FORTH), Heraklion (Greece). His research interest is in machine learning and knowledge discovery in databases, in particular inductive logic programming and its applications and knowledge discovery in environmental databases. He is co-author of Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994. He is the scientific coordinator of ILPnet2, The Network of Excellence in Inductive Logic Programming. He was program co-chair of the 7th International Workshop on Inductive Logic Programming ILP’97 and will be program co-chair of the 16th International Conference on Machine Learning ICML’99. Masayuki Numao, Ph.D.: He is an associate professor at the Department of Computer Science, Tokyo Institute of Technology. He received a bachelor of engineering in electrical and electronics engineering in 1982 and his Ph.D. in computer science in 1987 from Tokyo Institute of Technology. He was a visiting scholar at CSLI, Stanford University from 1989 to 1990. His research interests include Artificial Intelligence, Global Intelligence and Machine Learning. Numao is a member of Information Processing Society of Japan, Japanese Society for Artificial Intelligence, Japanese Cognitive Science Society, Japan Society for Software Science and Technology and AAAI.     

Advantages of decision lists and implicit negatives in Inductive Logic Programming

This paper demonstrates the capabilities offoidl, an inductive logic programming (ILP) system whose distinguishing characteristics are the ability to produce first-order decision lists, the use of an output completeness assumption as a substitute for negative examples, and the use originally motivated by the problem of learning to generate the past tense of English verbs; however, this paper demonstrates its superior performance on two different sets of benchmark ILP problems. Tests on the finite element mesh design problem show thatfoidl’s decision lists enable it to produce generally more accurate results than a range of methods previously applied to this problem. Tests with a selection of list-processing problems from Bratko’s introductory Prolog text demonstrate that the combination of implicit negatives and intensionality allowfoidl to learn correct programs from far fewer examples thanfoil. This research was supported by a fellowship from AT&T awarded to the first author and by the National Science Foundation under grant IRI-9310819. Mary Elaine Califf: She is currently pursuing her doctorate in Computer Science at the University of Texas at Austin where she is supported by a fellowship from AT&T. Her research interests include natural language understanding, particularly using machine learning methods to build practical natural language understanding systems such as information extraction systems, and inductive logic programming. Raymond Joseph Mooney: He is an Associate Professor of Computer Sciences at the University of Texas at Austin. He recerived his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 1988. His current research interests include applying machine to natural language understanding, inductive logic programming, knowledge-base and theory refinement, learning for planning, and learning for recommender systems. He serves on the editorial boards of the journalNew Generation Computing, theMachine Learning journal, theJournal of Artificial Intelligence Research, and the journalApplied Intelligence.     

Learning with globally predictive tests

We introduce a new bias for rule learning systems. The bias only allows a rule learner to create a rule that predicts class membership if each test of the rule in isolation is predictive of that class. Although the primary motivation for the bias is to improve the understandability of rules, we show that it also improves the accuracy of learned models on a number of problems. We also introduce a related preference bias that allows creating rules that violate this restriction if they are statistically significantly better than alternative rules without such violations. Michael J. Pazzani, Ph.D.: He is a Full Professor and Chair in the Department of Information and Computer Science at the University of California, Irvine. He obtained his bachelors degree from the University of Connecticut in 1980 and his Ph. D. from University of California, Los Angles in 1987. His research interests are in machine learning, cognitive modeling and information access. He has published over 100 research papers and 2 books. He has served on the Editorial Board of the Machine Learning and the Journal of Artificial Intelligence Research.     

From eager to lazy constrained data acquisition: A general framework

^*1 Constraint Satisfaction Problems (CSPs)¹⁷⁾ are an effective framework for modeling a variety of real life applications and many techniques have been proposed for solving them efficiently. CSPs are based on the assumption that all constrained data (values in variable domains) are available at the beginning of the computation. However, many non-toy problems derive their parameters from an external environment. Data retrieval can be a hard task, because data can come from a third-party system that has to convert information encoded with signals (derived from sensors) into symbolic information (exploitable by a CSP solver). Also, data can be provided by the user or have to be queried to a database. For this purpose, we introduce an extension of the widely used CSP model, called Interactive Constraint Satisfaction Problem (ICSP) model. The variable domain values can be acquired when needed during the resolution process by means of Interactive Constraints, which retrieve (possibly consistent) information. A general framework for constraint propagation algorithms is proposed which is parametric in the number of acquisitions performed at each step. Experimental results show the effectiveness of the proposed approach. Some applications which can benefit from the proposed solution are also discussed. This paper is an extended and revised version of the paper presented at IJCAI’99 (Stockholm, August 1999)⁴⁾. Paola Mello, Ph.D.: She received her degree in Electronic Engineering from University of Bologna, Italy, in 1982 and her Ph.D. degree in Computer Science in 1989. Since 1994 she is full Professor. She is enrolled, at present, at the Faculty of Engineering of the University of Bologna where she teaches Artificial Intelligence. Her research activity focuses around: programming languages, with particular reference to logic languages and their extensions towards modular and object-oriented programming; artificial intelligence; knowledge representation; expert systems. Her research has covered implementation, application and theoretical aspects and is presented in several national and international publications. She took part to several national (Progetti Finalizzati e MURST) and international (UE) research projects in the context of computational logic. Michela Milano, Ph.D.: She is a Researcher in the Department of Electronics, Computer Science and Systems at the University of Bologna. From the same University she obtained her master degree in 1994 and her Ph.D. in 1998. In 1999 she had a post-doc position at the University of Ferrara. Her research focuses on Artificial Intelligence, Constraint Satisfaction and Constraint Programming. In particular, she worked on using and extending the constraint-based paradigm for solving real-life problems such as scheduling, routing, object recognition and planning. She has served on the program committees of several international conferences in the area of Constraint Satisfaction and Programming, and she has served as referee in several related international journals. Marco Gavanelli: He is currently a Ph.D. Student in the Department of Engineering at the University of Ferrara, Italy. He graduated in Computer Science Engineering in 1998 at the University of Bologna, Italy. His research interest include Artificial Intelligence, Constraint Logic Programming, Constraint Satisfaction and visual recognition. He is a member of ALP (the Association for Logic Programming) and AI^*IA (the Italian Association for Artificial Intelligence). Evelina Lamma, Ph.D.: She got her degree in Electrical Engineering at the University of Bologna in 1985, and her Ph.D. in Computer Science in 1990. Her research activity centers on logic programming languages, Artificial Intelligence and software engineering. She was co-organizers of the 3rd International Workshop on Extensions of Logic Programming ELP92, held in Bologna in February 1992, and of the 6th Italian Congress on Artificial Intelligence, held in Bologna in September 1999. She is a member of the Executive Committee of the Italian Association for Artificial Intelligence (AI^*IA). Currently, she is Full Professor at the University of Ferrara, where she teaches Artificial Intelligence and Fondations of Computer Science. Massimo Piccardi, Ph.D.: He graduated in electronic engineering at the University of Bologna, Italy, in 1991, where he received a Ph.D. in computer science and computer engineering in 1995. He currently an assistant professor of computer science with the Faculty of Engineering at the University of Ferrara, Italy, where he teaches courses on computer architecture and microprocessor systems. Massimo Piccardi participated in several research projects in the area of computer vision and pattern recognition. His research interests include architectures, algorithms and benchmarks for computer vision and pattern recognition. He is author of more than forty papers on international scientific journals and conference proceedings. Dr. Piccardi is a member of the IEEE, the IEEE Computer Society, and the International Association for Pattern Recognition — Italian Chapter. Rita Cucchiara, Ph.D.: She is an associate professor of computer science at the Faculty of Engineering at the University of Modena and Reggio Emilia, Italy, where she teaches courses on computer architecture and computer vision. She graduated in electronic engineering at the University of Bologna, Italy, in 1989 and she received a Ph.D. in electronic engineering and computer science from the same university in 1993. From 1993 to 1998 she been an assistant professor of computer science with the University of Ferrara, Italy. She participated in many research projects, including a SIMD parallel system for vision in the context of an Italian advanced research program in robotics, funded by CNR (the Italian National Research Council). Her research interests include architecture and algorithms for computer vision and multimedia systems. She is author of several papers on scientific journals and conference proceedings. She is member of the IEEE, the IEEE Computer Society, and the International Association for Pattern Recognition — Italian Chapter.     

Seeing things: Inventive reasoning with geometric analogies and topographic maps

This paper examines two seemingly unrelated qualitative spatial reasoning domains; geometric proportional analogies and topographic (land-cover) maps. We present a Structure Matching algorithm that combines Gentner’s structuremapping theory with an attributematching process. We use structure matching to solve geometric analogy problems that involve manipulating attribute information, such as colors and patterns. Structure matching is also used to creatively interpret topographic (land-cover) maps, adding a wealth of semantic knowledge and providing a far richer interpretation of the raw data. We return to the geometric proportional analogies, identify alternate attribute matching processes that are required to solve different categories of problems. Finally, we assess some implications for computationally creative and inventive models. Diarmuid P. O’Donoghue, Ph.D.: He received his B.Sc. and M.Sc. from University College Cork in 1988 and 1990, and his Ph.D. from University College Dublin. He has been a lecturer at the Department of Computer Science NUI Maynooth since 1996 and is also an associate of the National Centre for Geocomputation. His interests are in artificial intelligence, analogical reasoning, topology, and qualitative spatial reasoning. Amy Bohan, B.Sc, M.Sc.: She received her B.Sc. from the National University of Ireland, Maynooth in 2000. She received her M.Sc. in 2003 from University College Dublin where she also recently completed her Ph.D. She is a member of the Cognitive Science society. Her interests are in cognitive science, analogical argumentation, geometric proportional analogies and computational linguistics. Prof. Mark T. Keane: He is Chair of Computer Science and Associate Dean of Science at University College Dublin. He is also Director of ICT, at Science Foundation Ireland. Prof. Keane has made significant contributions in the areas of analogy, case-based reasoning and creativity. He has published over 100 publications, including 16 books, that are cited widely. He is co-author of a Cognitive Science textbook, written with Mike Eysenck (University of London) that has been translated into Portuguese, Hungarian, Italian and Chinese and is now entering its fifth edition. Prof. Keane is a fellow of ECCAI (European Co-ordinating Committee on Artificial Intelligence) and received the Special Award for Merit from the Psychology Society of Ireland, for his work on human creativity.