1. Introduction

Computers are normally programmed using algorithms (recipes) that operate on data to achieve some desired goal or result. The implicit assumption in this approach is that the required algorithm is known. Additionally, any change in the problem domain often requires a significant change in the algorithm.

For many problems, it would be desireable to have a system where explicit programming of a solution was not required - even if it were possible. Ideally, only explicit knowledge and/or training examples from the domain would have to be applied to some process that would yield a solution or near solution. Any change to domain could readily be incorporated in the solution.

2. Knowledge-based Systems

A computer can be made to use explicit knowledge "fragments", acquired from human experts, to perform computing. Such knowledge consisting of facts, concepts, theories, heuristic methods, procedures and relationships is collected into knowledge-base (KB) system. The ability of these systems to explain their reasoning process in deriving a response is a feature that conventional programming does not provide.

2.1 Rule-based Systems

Of the many possible representation schemes for knowledge, those that are rule-based are popular. These are also known as rule-based (RB) expert systems.

Rule-based systems operate with rule-based reasoning (i.e. inference) methods. Inference is performed through a logical chaining of If-Then rules that are acquired from an expert. The logic on which these systems are based is deterministic.

RB systems consist of a knowledge base and an inference engine. This structure reflects the two main tasks of knowledge engineering: representing and storing large amounts of problem-domain knowledge, and actively using this knowledge for solving problems and answering queries. The system can operate in one of two modes.

  • A data-driven forward chaining mode, in which known data is input to determine if some conclusion may be reached;
  • Or, a goal-drive back-chaining mode, to determine if a given outcome has the necessary and sufficient supporting input data.

For example, in determining eligibility of a candidate for some benefit program, forward chaining would be used if all possible information was made available beforehand, and backward chaining would be used if the candidate was engaged into an interview process to extract only the minimal information to make a concrete determination of eligibility.

RB systems are used to diagnose diseases, locate mineral deposits, configure complex computer hardware, assist managers with complex planning and scheduling tasks, and commodity trading.

2.2 Fuzzy Logic Systems

The class of problems that RB system can address can be expanded with the use of "fuzzy" logic. Fuzzy logic is the generalization of conventional (Boolean) logic. The utility of fuzzy logic is in its ability to address situations that the traditional Boolean logic cannot adequately address, e.g. is the partially filled glass of water full or is it empty? Fuzzy logic is designed to handle imprecise "linguistic" concepts of degree such as good/better/best and relativism such as small, big, young, old, high, or low.

Fuzzy reasoning is the process of deriving conclusions from a given set of fuzzy rules acting on fuzzified data. Unlike a conventional Boolean rule which "fires" completely only if its antecedent is strictly satisfied, a fuzzy rule fires in some proportion to the satisfaction of its antecedent. In effect, fuzzy systems can embrace a broader set of situations in their reasoning.

One of the main strengths of fuzzy logic systems, compared with other schemes to deal with imprecise or incomplete data (e.g. neural networks), is that their knowledge bases, which are in rule format, are easy to examine and understand. This rule format also makes it easy to update and maintain the knowledge base.

Systems based on fuzzy logic exhibit an inherent flexibility and have proven to be successful in a variety of financial, industrial control, and pattern recognition tasks ranging from handwriting recognition to credit evaluation. There are now several consumer products including washing machines, microwave ovens and auto-focus cameras that use fuzzy logic in their control mechanism.

3. Learning-based Systems

When specific knowledge about a domain is either not available or incomplete, the only way to create a solution to a problem is to invoke a process that learns the requisite knowledge from a sufficiently representative set of training examples. Machine Learning (ML) is the sub-field of AI concerned with processes that learn from experience. Here, attention shifts from the static question of how to represent knowledge to the dynamic quest of how to acquire it.

Learning and associations are closely coupled. Associations are the basis for intelligent behavior of living organisms. Human memory is organised in an associative manner. Unlike inputs to digital computer memory, inputs are not addressed sensory patterns or parts of patterns. Given an input, the memory has the ability to recognise this input as being similar to some stored pattern (associative recall).

ML is a process in which extracts knowledge from a training set of data, yielding a solution(s) that can be tested against a test set of data for its quality and ability to generalise.

Associative systems provide a relatively easy way to model non-linear systems. This gives them an advantage over linear statistical methods. They are also very effective in learning patterns in data that is noisy and/or incomplete, and which may even contain contradictory examples.

The main limitation of associative systems is that they lack reasoning explanation capability.

3.1 Major Issues

The major issues in ML are representation, operators, search strategies and learning types.

Representation is a definition of what a possible solution might look like - the kinds of inputs, the kinds of input transformations, and the types of output. In short, the problem representation defines the set of all possible solutions to a problem that a particular ML system can find.

For most problems, the space of all possible solutions is huge. It is search operators that define how a ML system chooses solutions to test and in what order. Search operators define and limit the area of representation space that will actually be searched. Good machine learning systems tend to encounter better and bypass poorer solutions.

While the search operators define what types of jumps a system can make through the search space, the extend of the search conducted is determined by the search strategy. The three major strategies are:

  • Blind search, in which no information about the structure of the problem or results from previous steps are used;
  • Hill climbing, which starts its search in one spot and moves through the search space only if a transformation results in a better solution;
  • Beam search, in which a population of the more promising search points (according to some fitness measure) is maintained for further transformation;

The learning approach may be classified as:

  • Supervised, in which the output of a candidate solution is measured against the correct output;
  • Unsupervised, where the system is not told what the correct solution is, but rather looks for patterns in the input data;
  • Reinforcement learning, which falls between supervised and unsupervised learning, and is looking to optimize a solution;

3.2 Artificial Neural Networks

An artificial neural network (ANN) is composed of processing elements (neurons) organized in different ways to form a network structure. Each processing element can accept several inputs, process them and generate one output. The output can be the final product or it can be input to another neuron. Each ANN is composed of a collection of neurons that are grouped into layers, of which there is an input, one or more middle (hidden) and output layer are required at a minimum. Each connection has an associated weight that controls the relative importance of the signal on that connection.

Once the architecture is chosen, the ANN must be trained. Learning involves: computing the output; comparing the output with the target output; and adjusting the weights accordingly. Back-propagation is the most popular learning algorithm.

3.3 Case-based Reasoning Systems

The fundamental principle of Case-Based (CB) reasoning for problem-solving is to retrieve stored records of prior problem-solving episodes and to adapt their solutions to fit new problems.

The basic algorithm is to: retrieve from case memory a past case consisting of a problem and solution, that resembles the current problem from case memory; adapt a past solution to the current problem ; apply the adapted solution and evaluate the results; and, update case memory.

If the adapted solution works, a new case, composed of the problem just solved and the solution used, can be formed. If the solution at first fails, but can be repaired so the failure is avoided. the new case is composed of the problem just solved and the repaired solution. This new case is stored in case memory so that the new solution will be available for retrieval during future problem solving. In this way, the system becomes more competent as it gains experience.

CB systems have been designed to handle such diverse tasks as planning, design, diagnosis, legal argumentation, negotiation, and real-estate evaluation.

3.4 Genetic Algorithms

The GA is a model of machine learning that derives its behavior from a metaphor of the processes of evolution in nature. This is done by the creation, within the machine, of a population of randomly generated solutions. Each solution is represented by encoding a fixed length string of symbols. Each symbol or combination of symbols represents an encoding of some aspect of the total solution. The individual solutions in the population then go through a process of evolution. The system then attempt to produce new generations of solutions that are better than their predecessors. This is a direct analogue of the Darwinian principle of “survival of the fittest”, i.e. let the better solutions survive and replace the weaker ones. Genetic algorithms operate through a simple cycle consisting of the following stages: population creation, selection, reproduction, and evaluation.

In nature, we see that the encoding for our genetic information (genome) is done in a way that admits sexual reproduction. Sexual reproduction allows the creation of genetically radically different offspring that are still of the same general flavor (species).

Genetic algorithms have produced very good solutions for complex optimization problems that have a large number of parameters. Applications include electronic circuit layout, gas pipeline control, and job shop scheduling.

3.5 Genetic Programming

Genetic Programming (GP) is the extension of the genetic algorithm (GA) model of learning into the space of programs. That is, representation is perhaps the most important distinguishing feature of GP. Computers are programmed with computer programs – and GP creates computer programs. The objects that constitute the population are not fixed-length character strings that encode possible solutions to the problem at hand (GA), but rather, they are programs that are executable solutions to the problem.

These programs are expressed in GP as parse trees, rather than as lines of code. The population of parse tree programs are composed of elements from a function set and the terminal set, which are typically fixed sets of symbols selected to be appropriate to the solution of problems in the domain of interest. The crossover operation is implemented by taking randomly selected sub-trees in the individuals (selected according to fitness) and exchanging them.

GP addresses the problem of automatic programming, namely the problem of how to enable a computer to do useful things without having to provide explicit instructions on how to do so. By the term automatic programming we mean a system that: produces an entity that runs on a computer (i.e., either a computer program or something that is easily convertible into a program); solves a broad variety of problems; requires a minimum of usersupplied problem specific information; does not require the user to pre-specify the size and shape of the ultimate solution; implements, in some way, all the familiar and useful programming constructs (such as memory, iteration, subroutines, data structures and recursion); does not require the user to decompose the problem in advance, to identify sub-goals, or hand craft operators, or to tailor the system anew for each problem; scales to ever-larger problems; is capable of producing results competitive with those produced by human programmers, and, is well defined, is replicable, has no hidden steps, and requires no human intervention during the run.

GP is fundamentally different from other approaches to artificial intelligence, machine learning, adaptive systems, automated logic, expert systems, and neural networks in terms of: the representation (programs); the role of knowledge (none); the role of logic (none); and, its mechanism (gleaned from nature), for getting within the space of possible solutions.

4. Applications of AI Technology

4.1 Intelligent Data Mining

Intelligent Data Mining Data mining (knowledge discovery) is the analysis of data for relationships that have not previously been discovered. Data mining results include: associations, or when one event can be correlated to another event; sequences, or one event leading to another later event; classification, or the recognition of patterns and a resulting new organization of data; clustering, or finding and visualizing groups of facts not previously known; and, forecasting, or simply discovering patterns in the data that can lead to predictions about the future.

Vast amounts of corporate data is being captured in data warehouses. This data is being mined with intelligent technologies such as neural networks and genetic algorithms to find trends and unknown information.

4.2 Help Desk

Help-desks provide central information sources that can route problem requests, provide detailed information, and answer questions quickly and accurately. Cost/benefit analysis indicate that reducing the time required to route incoming problem requests and resolving problems can greatly reduce a company's costs and improve productivity. Help-desk software can capture the knowledge of technicians while using multimedia to provide on-demand expertise for operators. This technology incorporates multimedia and hypermedia, video, animation, voice, and intuitive interfaces, while using AI techniques for problem resolution. Expert systems simplify Help-desks production by providing flexible knowledge capturing capabilities and allowing the building of knowledge-bases on the fly.

4.3 Search Engines

Search engines are programs that enable users to search for files and information on the Internet. Search engines are very different from subject directories. While humans organize and catalog subject directories, search engines rely on computer programs called spiders or robots to crawl and search the Web. The better search engines take keywords provided by the user and generate relevant concepts from a knowledge base. The spider/robots are then armed with these concepts to search the Web looking for sites/pages with similar concepts. The search engine returns to the user a file with sites that contain concepts most closely matched with their request.

4.4 Intelligent Agents

Intelligent Agents execute tasks on behalf of a business process, computer application, or an individual. For example, corporate use of monitoring software based on agents can be a key component in cutting support costs and increase computer efficiency. Intelligent agents have been written to search through e-mail messages for certain keywords or simple concepts (phrases).

On the Internet, good agents will allow people to spend less time searching for information - and more time utilizing or analyzing "good" information that is "autoretrieved". They will allow information retrieval novices to achieve expert "power searcher" results. With people moving from clientserver computing, to the new model of network centric computing -- the network becomes the computer. In this realm, agents will help reduce complexity and increase efficiency. Nevertheless, currently, "agents" and personalization services don't search much of the Web, but instead, confine themselves to one or more databases controlled by the companies offering the service.

4.5 Intelligent Applications

Intelligent Applications (IA) are applications in which advanced technology is applied, transparent to the user, making user interfaces being adaptive and conversational. The goal is to have the applications behave like an assistant or advisor.

4.6 Natural Language Processing

Natural Language Processing (NLP) systems have the ability to analyze, understand, and generate natural human languages.

Applications of NLP include:

  • Machine translation of one human-language text to another;
  • Generation of human-language text such as fiction, manuals, and general descriptions;
  • Interfacing to other systems such as databases and robotic systems thus enabling the use of human-language type commands and queries;
  • Understanding human language text to provide a summary or to draw conclusions.

One of the easiest tasks for a NLP system is to parse a sentence to determine its syntax. A more difficult task is determining the semantic meaning of a sentence. One of the most difficult tasks is the analysis of the context to determine the true meaning and comparing that with other text.

References & Resources

  • The world of AI - a brief tutorial, from www.cognetics.ca