AI in Autonomic Computing: A Survey of Research Challenges and Real-World Applications
The rapidly growing complexity of integrating and managing computing systems threatens to overwhelm the capabilities of even the most expert software developers and system administrators. Many of the basic components of computing systems, such as databases, storage devices, and servers, now have hundreds of tuning parameters. Systems of these components are growing in size and heterogeneity, giving rise to complex and increasingly dynamic inter-element dependencies and interactions. If these trends continue, it will soon become impossible for humans to effectively configure and optimize systems, and maintain them in real time. Most major IT vendors agree that this looming crisis can be averted only if computing systems become more self-managing. IBM coined the term "Autonomic Computing" to describe its vision of a future in which large-scale computing systems would manage their own behavior in accordance with high-level objectives specified by administrators. The development of such self-configuring, self-optimizing, and self-repairing systems is a major scientific and engineering challenge. To meet this challenge, Autonomic Computing requires extensive use of AI techniques such as automated real-time reasoning and decision making, machine learning, and planning. Thus, Autonomic Computing promises to be a major application area for AI, a driver for basic research, and a cross-pollinator across many sub-fields of AI.
This tutorial will survey state-of-the-art applications of AI technologies in the major problem domains within Autonomic Computing and identify AI research challenges that lie ahead in designing self-managing computing systems. The tutorial is directed to a general AI audience, in particular to people interested in learning about opportunities and challenges in applying AI to real-world problems, or to those who are seeking an interesting new application domain for AI techniques in which they are expert. The tutorial will be accessible to all IJCAI attendees, as it provides the necessary background on Autonomic Computing, and assumes only a basic knowledge of AI topics.
Rajarshi Das (rajarshi[at]us[dot]ibm[com]com)
Tutorial on Empirical Methods
Most sciences, but not computer science, train graduate students in empirical methods. Although sciences emphasize different methods, most teach a core set of visualizations and descriptive statistics, hypothesis testing and analysis methods, and experiment design and modeling methods. A competent researcher knows several dozen methods, more that can be taught in a tutorial, so we must take a different approach to the subject: this tutorial is organized around ten lessons or maxims, the rules of good practice one rarely sees in books but that explain why empirical methods are designed as they are. Then, through case studies, we introduce very common methods such as t tests, factorial designs, confidence intervals, regression, and many others. We emphasize how these methods work and say little about their underlying statistical theory. Students learn what to do and why, they learn common methods in a way that helps them go to the literature and learn more.
Specifically this tutorial begins with explanatory data analysis, how to look at data, visualizations and transformations. Next comes variance, what causes it and what to do about it. Given this foundation we can deconstruct hypothesis tests. All tests have the same logic and purpose, so understanding one test really is our goal. We begin with t tests, then test of correlations and dependency, then test analysis of variance. We discuss confidence intervals, errors and the power of tests, and relate them to ROC curves. While classical test are based on assumptions and analysis, modern “computer intensive” tests simply mimic the process of drawing samples on a computer. We will discuss the bootstrap and related methods. Experiment design seems simple until one tries it. We illustrate pitfalls and good practices, and conclude with a checklist for every experiment designer.
Paul Cohen (cohen[at]ISI[dot]EDU)
Bio-Inspired Optimization Algorithms
This half day tutorial will present an informative account of a class of bio-inspired algorithms and their applications to optimization problems. The flocking mechanisms found in biological swarms like ants, termites, bees, wasps, and bacteria are a result of actions performed by relatively simple individuals that are solely based on neighbor-interactions and local information from the environment inhabited by the agent-collective. These emergent behaviors offer an insight into the basis to devise distributed algorithms that solve complex problems related to diverse fields such as optimization, multi-agent decision making, and collective robotics. Recent literature abounds in examples of such bio-mimetic algorithms including ant colony optimization (ACO), particle swarm optimization (PSO), glowworm swarm optimization (GSO), and several swarm based collective robotic algorithms.
In this tutorial, we will focus our attention on ACO, PSO, and GSO algorithms. We will discuss the three algorithms, specifically in terms of their underlying ideas, basic algorithmic structures and software tools available, some major variants proposed in the literature, their merits/demerits, and applications to optimization problems. We will also provide a comparison among these techniques. Finally, we will describe some applications to collective robotics.
Debasish Ghose (dghose[at]aero[dot]iisc[dot]ernet[dot]in) and K.N. Krishnanand (krishna[at]aero[dot]iisc[dot]ernet[dot]in)
Exploring Non-Traditional Benefits of AI to the Global Society
The United Nations (UN) reports almost half of the world’s population lives on less than $2 a day. Another billion people join them at the poverty base of the economic pyramid that includes almost two thirds of the global population! While solutions to poverty require food and other basic necessities in the short-term, a sustainable long-term solution to global poverty must involve empowerment of the poor to feed themselves and make their own livelihoods. Thus, eradication of poverty will require a concerted global effort; it cannot be accomplished by the actions of a few. While most wonder how this topic concerns the field of Computing and Artificial Intelligence, an increasing number of people are lobbying for innovative technology as a necessary tool for the empowerment of developing communities. One of the pioneers in AI, and the recipient of the 2005 IJCAI Donald E. Walker Distinguished Service Award, Professor Raj Reddy, in his 1988 AAAI presidential address, urged AI researchers to consider the challenges of the poor in technology research, and highlighted the necessity for innovative technology that will benefit the poor. Inspired by the vision set forth by pioneers such as Professor Reddy and by the theme of IJCAI 2007, “AI and its benefits to society,” this tutorial addresses the growing demand for technological innovation to empower developing communities and enable sustainable development, and the resulting requirement for new and creative educational and research initiatives. The tutorial presents the benefits, challenges and opportunities of research and education in AI and related topics relevant to developing communities. www.techbridgeworld.org/IJCAI2007
More specifically, this tutorial describes how partnerships between developed and developing communities must play a major role in creating technology relevant to developing communities and also explores directions in which research and education in AI can benefit developing communities around the world, help achieve the Millennium Development Goals, and increase the diversity and creativity of the field through the process. While most of the world’s poor do not directly use computers (though many do use cell phones), they are certainly impacted by computers as used in the economy. One hypothetical path for AI and advanced computing technologies is one of competition, where it is a choice of human vs. machine. Instead, we think machines can and will be optimized for synergies with humans. In terms of developing communities, while labor may be purportedly cheap, skilled labor is a precious commodity, especially one with technology skills (e.g., doctors). AI and experts systems have a clear role to play in improving development and empowering such communities. This tutorial will examine the role of AI in these communities by providing an overview of relevant background, describing several models for incorporating this topic into AI education, analyzing several case studies of AI applied in developing communities, and sharing important lessons learned through current and past work in this area.
M. Bernardine Dias (mbdias[at]ri[dot]cmu[dot]edu), Rahul Tongia (tongia[at]andrew[dot]cmu[dot]edu), and Kentaro Toyama(Kentaro[dot]Toyama[at]microsoft[dot]com)
Temporal Information Extraction from Natural Language
The problem of temporal information extraction from natural language poses many interesting challenges. The potential applications include the automatic construction of chronologies from news, medical narratives, accident reports, etc. This tutorial will begin with an overview of theoretical work on tense, aspect, and event structure in natural language, as well as introduce the fundamentals of temporal reasoning. It will discuss the annotation of temporal and event expressions in corpora, including the TimeML and ACE annotation schemes. The tutorial will examine a variety of methods for ordering events in time from natural language, including rule-based and machine-learning methods. It will also identify outstanding research problems in automatically constructing chronologies of events in the above genres. Tutorial attendees can expect to learn about current methodologies, computational tools and corpora, as well as obtain follow-up pointers to the literature.
Indergeet Mani (imani[at]mitre[dot]org)
Constraint Processing
Solving combinatorial optimization problems like planning, scheduling, design, or configuration is a non-trivial task being attacked by many solving techniques. Constraint satisfaction, that emerged from AI research and nowadays integrates techniques from areas like operations research and discrete mathematics, provides a natural modeling framework for description of such problems supported by general solving technology. Though it is a mature area now, surprisingly many researchers outside the CSP community do not use the full potential of constraint satisfaction and frequently put equality between constraint satisfaction and simple enumeration. A nice example demonstrating the power of constraints are popular Sudoku problems that can be solved almost trivially by means of constraints, if proper technology is known.
The tutorial gives an introduction to mainstream constraint satisfaction techniques available in existing constraint solvers, namely constraint propagation combined with depth-first search, and answers the questions “How does constraint satisfaction work?” and “How to efficiently model problems using constraints?”. The tutorial explains methods like arc consistency and shows how filtering algorithms are designed for constraints (this is a way how algorithms from other areas can be easily integrated into constraint solvers). Then it presents how consistency techniques are integrated with depth-first search algorithms and, finally, several modeling examples are given to demonstrate how constraints can be used in problem solving (including the popular Sudoku problems).
The tutorial is targeted to a broad AI community, in particular to everyone who is not familiar with the details of constraint satisfaction technology. It introduces novices as well as expert non-specialists to one of the major topics of AI. The tutorial also provides instructions how to use constraint satisfaction in problem solving. No prior knowledge of constraint satisfaction is required.
Roman Bartak (roman[dot]bartak[at]mff[dot]cuni.cz)
Traditional Approaches to Knowledge Management
In this tutorial, we will present traditional approaches to knowledge management from two perspectives ñ management of traditional knowledge, and application of such concepts to current day scenario for knowledge organization and interpretation. We will illustrate this with techniques from Indian knowledge systems such as Nyaya Shastra (logic), Mimamsa (interpretation), and Nanool (grammar). We will present some key concepts of these systems and discuss their applications to important areas of AI including knowledge organization, knowledge representation, reasoning, sentence and dialog interpretation.
We will begin with techniques used to organize knowledge for precision, brevity, interpretation, security, and communication. We then move on to classical ontology, and its applications, followed by inference mechanisms as applied to reasoning. We will finally deal with interpretation techniques. All along, we will provide pointers to how these traditional techniques can be adapted to explore new approaches and models to tackle typical issues of AI. The aim is to motivate researchers to investigate this challenging area of applying traditional knowledge systems to interesting AI problems.
Ranjani Parthasarathi (rp[at]annauniv[dot]edu) and T.V. Geetha (tvgeedir[at]cs[dot]annauniv[dot]edu)
Graphical Models for Machine Learning in Natural Language Processing
Of late, probabilistic approaches to natural language processing has assumed great importance. While this interest has been spurred by the demonstration of the utility of Hidden Markov Model (HMM) in language processing, there have been more sophisticated probabilistic models applied to the processing of linguistic data. These are Maximum Entropy Markov Models (MEMM), Conditional Random Fields (CRF) and Semi-Markov Conditional Random Fields. Since these models make use of “state nodes” and “transition edges” linking the nodes, they are called Graphical Models. These models have recently been extensively used in NLP tasks.
This tutorial will give an extensive coverage of these machine learning based algorithms. We will keep in view critical NLP tasks, viz., part of Speech Tagging, Named Entity Recognition, Chunking and Parsing. Each of the above mentioned models will be elaborately discussed with examples, accompanied by the discussion on the application to specific NLP tasks. Recent developments and the observed trends and directions will close the deliberations.
This tutorial is directed at introducing expert non-specialists to an AI sub-area which is also an emerging technology. NLP researchers, Machine Learning researchers concerned with text, Statisticians interested in language processing, and even sequence miners from other fields like bio-informatics will be interested in this tutorial. The presentation will be suitable for R&D personnel from both academia and industry.
Pushpak Bhattacharyya(pb[at]cse[dot]iitb[dot]ac[dot]in) and Ganesh Ramakrishnan (ganramkr[at]in[dot]ibm[dot]com)
Agents for Web Services
Web services have become an important paradigm for information technology architectures and applications. The main advantage of Web services arises from their "mashups" -- when we can compose them to create new services.
Although some ideas needed for services originate in heterogeneous databases, distributed computing, and traditional AI, the essential openness and scale of the Web forces a rethinking of some key principles. For Web services to be effectively composed requires an understanding of several key concepts from agents and multi-agent systems. This tutorial presents the necessary concepts and the associated architectures, theories, standards, and techniques to compose Web services effectively.
Until recently, a lot of attention has been focused on lower-level, infrastructural themes, which either become obsolete or become assimilated into tools. This tutorial, by contrast, deals with the deeper foundational topics. It evaluates the state of the art and suggests several directions for research and development.
This tutorial is presented at a senior undergraduate student level.
It is accessible to Web programmers, advanced developers, and students.
Typical attendees for our past tutorials have been researchers and practitioners from industry and government, advanced developers, graduate and senior undergraduate students, and university faculty.
Munindar P. Singh(singh[at]ncsu[dot]edu) and Michael Hunhes(huhns[at]engr[dot]sc[dot]edu)
The Art and Science of Action Programming
Intelligent software agents, general game players, and high-level controllers for autonomous robots are three examples of systems for which the ability to reason about their actions and their effects play a key role. For this purpose, action programming languages have recently been developed on the basis of 40 year of research in knowledge representation. Thanks to a high level of abstraction, action programs allow to solve complex tasks while easy to write, understand, and maintain. Highly optimized implementations have recently been developed for various action programming languages.
This tutorial will give an introduction to selected languages and systems. Participants will learn how to specify domains and how to write programs for endowing autonomous agents with problem solving abilities. The tutorial will provide an insight into the underlying mathematics and into the advantages and disadvantages of these languages in comparison. A variety of successful applications of action programming languages will be discussed with a focus on general game playing on the one hand, and the combination with low-level control of autonomous robots on the other hand.
The tutorial is directed at every AI researcher who wants to gain an insight into state-of-the-art research in knowledge representation for actions and action programming languages. In particular, the agent programmer and roboticist will be shown what symbolic methods can offer to enhance the autonomy and flexibility of intelligent systems. The only required background is some basic knowledge of standard propositional and first-order logic.
Michael Thielscher (mit[at]inf[dot]tu-dresden[dot]de)
Software Agents and Applications
The globalization of business and resulting information explosion calls for automated and distributed decision-making on behest of human beings. The Internet platform presents an opportunity for on-line interaction of software elements without human supervision. Software Agents are “intelligent” computer programs that reside in the cyberspace. They can analyze the available information and proactively act to further the interests of their respective users. The software agents live in the milieu of a cyber-society. They collaborate with each other to realize agent-based systems and at the same time, compete with each other to maximize the gains of their owners. The subject “Software agents” is an amalgamation of several knowledge disciplines, e.g. distributed computing, artificial intelligence, economics and sociology, to name a few.
The tutorial aims at introducing the theory and the practical applications of agents to the audience. It will broadly cover the following topics
What are and what are not software agents
Architecture of software agents
Communication and coordination in software agents
Mobile Agents
Agent negotiation
Agent Applications
The tutorial will provide references to books, research papers and Internet sites that hold comprehensive and authentic information on various aspects of software agents for further reading.
The intended audience for the tutorial is students and practitioners, who either have a casual interest in the subject or needs an introduction to pursue further research. We assume a general background in information technology and familiarity with the web environment; no specific computer science / technology skills are necessary.
Hiranmay Ghosh (hiranmay[at]ieee[dot]org)
Planning Graph Based Reachability Heuristics
The primary revolution in automated planning in the last decade has been the very impressive scale-up in planner performance. A large part
of the credit for this can be attributed squarely to the invention and
deployment of powerful reachability heuristics. Most, if not all,
modern reachability heuristics are based on a remarkably extensible
datastructure called the planning graph--which made its debut as a bit
player in the success of Graphplan, but quickly grew in prominence to occupy the center-stage.
In this tutorial, we will start with a discussion of the foundations of reachability analysis with planning graphs. We will then discuss
the many ways of applying this analysis to develop scalable planners.
Starting with classical planning, we will discuss heuristics for
cost-based planning, over-subscription planning, planning with
resources, temporal planning, non-deterministic planning as well as
stochastic planning.
Dr. Subbarao Kambhampati (subbarao2z[at]gmail[dot]com) and Daniel Bryce (dan[dot]bryce[at]asu[dot]edu)
Reasoning about dynamic systems by satisfiability testing: planning, model-checking and diagnosis
The classical propositional logic and its satisfiability problem (SAT) have always had a central role in computer science. However, only during the last ten years, as a result of several algorithmic innovations and the development of efficient implementation techniques, has the SAT problem gained importance as a practical solution method. In artificial intelligence, the last ten years have seen the emergence of SAT as a general framework for expressing and solving a wide range of challenging problems faced by intelligent systems, including planning, constraint satisfaction, validation, and diagnosis. The declarativeness and flexibility associated with logical approaches to knowledge representation, and now also extremely powerful implementations, make the SAT framework an increasingly attractive approach to problem solving, in many cases surpassing earlier ad hoc solution techniques in both efficiency and simplicity.
The objective of the tutorial is to present an overview of the algorithmic basis of modern SAT solvers, to outline the main representation techniques for solving planning, model-checking and diagnosis problems by using SAT, and to give an overview of extensions of the satisfiability problem which are needed for solving still more general problem classes.
Jussi Rintanen (ussi[dot]Rintanen[at]nicta[dot]com[dot]au)
Reinforcement Learning: From Foundations to Advanced Techniques
Reinforcement Learning (RL) refers to the study of algorithms and programs that learn by taking actions and receiving rewards from a possibly stochastic environment. Many of these algorithms work by learning a value function, i.e., a real-valued function, that represents the long-term value of a state or a state-action pair to the agent. These algorithms are derived from the theory of Markov Decision Processes (MDPs) and rely on the tools of stochastic approximation for their analysis.
In the first part of this three-part tutorial, we describe the basic value-function-based RL algorithms, relate them to MDPs, and derive their convergence properties from stochastic approximation theory. In the second part, we cover practical approaches that are important for scaling these algorithms to large real-world domains, including value function approximation, hierarchical reinforcement learning, and direct policy search. In the third and final part, we discuss promising new research in the area of spectral methods and automatic learning of representations, a long-cherished dream of AI.
Prasad Tadepalli (tadepall[at]eecs[dot]oregonstate[dot]edu) , Sridhar Mahadevan (mahadeva[at]cs[dot]umass[dot]edu) and Vivek S. Borkar (mahadeva[at]cs[dot]umass[dot]edu)
Text Mining and Link Analysis for Web and Semantic Web
The tutorial on Text Mining and Link Analysis for Web Data will focus on two main analytical approaches when analyzing web data: text mining and link analysis for the purpose of analyzing web documents and their linkage. First, the tutorial will cover some basic steps and problems when dealing with the textual and network (graph) data showing what is possible to achieve without very sophisticated technology. The idea of this first part is to present the nature of un-structured and semi-structured data. Next, in the second part, more sophisticated methods for solving more difficult and challenging problems will be shown. In the last part, some of the current open research issues will be presented and some practical pointers on the available tolls for solving previously mentioned problems will be provided.
Dunja Mladenic (dunja[dot]mladenic[at]ijs[dot]si) and Marko Grobelnik (marko[dot]grobelnik[at]ijs[dot]si)
Policy-Based Computing
The need for a more autonomous management of distributed systems and networks has driven research and industry to look for management frameworks that go beyond the direct manipulation of network devices and systems. One approach towards this aim is to build policy-based management systems. Policy-based computing refers to a software paradigm developed around the concept of building autonomous systems that provide system administrators and decision makers with interfaces that let them set general guiding principles and policies to govern the behavior and interactions of the managed systems. Although many of the tasks are still carried out manually and ad hoc, instances of policy-based systems can be found in areas such as internet service management, privacy, security and access management, management of quality of service and service level agreements in networks. This tutorial will present policy-based management from an AI perspective. Using temporal logic and borrowing concepts from action theories we will develop elementary definitions of policy systems that will let us compare different approaches to implementations. We will present a generic policy framework and show how natural language processing, theorem proving, agents and other AI techniques can help us develop better policy-based computing programming environments. We will discuss the limitations of current implementations and directions of research.
Seraphin Calo and Jorge Lobo (jlobo[at]us[dot]ibm[dot]com)
Learning Methodologies for Intelligent classification
Learning is an integral part of AI and decision-making. In absence of proper learning algorithm or even proper learning reference set decision-making may not be correct. Here in this tutorial we will discuss various learning methodologies, selection of proper learning techniques. We will discuss other aspects of learning methodologies one should take in to account while selecting learning technique. This tutorial will try to address various issues in learning (unsupervised as well as unsupervised) in practical scenarios. The tutorial will address various aspects of learning to make classification intelligent. Further we will address some of the decision-making aspects of learning. The tutorial also talks about classification from the perspective of learning. The tutorial will cover usage of various methods like SVM, intelligent feature extraction; feature based clustering for these applications. In this tutorial we will cover various difficulties in classification and learning methodologies in handling nonlinear problems very effectively. The tutorial will also present industrial applications of classification and case studies for classifying images and textual data. It will also throw some light on how these techniques can be extended for other applications in decision engineering. The tutorial will discuss practical scenarios for incremental learning and impact of learning strategies at various levels of decision-making
Dr. Parag Kulkarni (parag[dot]
kulkarni[at]capsilon[dot]com), Dr. P.K. Chande
Ambient Intelligence: Applications in Society and Opportunities for AI
Ambient Intelligence (AmI) is an emergent paradigm referring to an environment actively helping the people that use it. Places like a house, a hospital, a train station, an airport or a street can be enriched with technology and intelligent software to make human activities easier, safer and more enjoyable. We will consider the basic technology used in AmI, the applications and the challenges ahead, all from an AI perspective.
Dr. J.C. Augusto (jc[dot]augusto[at]ulster[dot]ac[dot]uk) and Dr. Diane Cook
Pattern Recognition and Evolution Methods for Chemo and Bio-Informatics
Genetic algorithms (GA) are based on the principle of evolution. Starting from a population of potential solutions, the algorithm evolves better solutions by means of natural selection and genetic operations like crossover and mutation that are akin to biological systems. Support vector machines (SVM) is a powerful learning algorithm firmly based on statistical learning theory and structural risk minimization principle. The effectiveness of GA is mainly because of its derivative free search and ease of modeling, and that of SVM is due to its excellent, learning and generalization capabilities. The tutorial will introduce the participants to GA, SVM and their applications in the areas of chemo- and bio- informatics. The application case studies would include gene identification, cancer detection, process fault detection, Quantitative Structure-Activity Relationships, protein structure prediction and similarity search.
V.K. Jayaraman (vk[dot]jayaraman[at]ncl[dot]res[dot]in) and Vijayraghavan Sundararajan
Language Independent Methods of Clustering Similar Contexts (with applications)
Methods that identify similar (but not identical) units of text have wide potential application. For example, Web search results can be better organized by grouping together pages with related and similar content. Email can be automatically foldered and categorized by finding which messages are similar to each other. Word senses can be discovered by clustering multiple contexts that use a particular ambiguous word.
This tutorial will introduce language independent methods for identifying similar contexts based on lexical features. The tutorial will explore the use of first and second order co--occurrence vectors for representing contexts, and introduce methods for carrying out dimensionality reduction that lower the noise and computational complexity associated with these large feature spaces. A number of different clustering algorithms will be discussed, along with methods that can automatically determine when the clustering algorithm should stop and what the "right" number of clusters should be. Finally, the tutorial will explore techniques for automatically generating descriptive labels for clusters.
The tutorial will also include a hands-on option for attendees with laptop computers that have an x86 processor (Intel Pentium, AMD Athlon, etc.) Attendees will be provided with a Live (ie Knoppix) CD that includes the SenseClusters system (http://senseclusters.sourceforge.net), as well as a variety of sample data that can be used for experimenting.
Ted Pedersen (tpederse[at]d[dot]umn[dot]edu)
