Chapter 24

Artificial Intelligence (AL)

 

 

This chapter introduces the reader to the fundamentals of Artificial Intelligence (AI). Artificial Intelligence is a science, which focuses on creating machines that engages on the behaviours performed by humans. The chapter begins by giving an overview of AI. The discussion continues with knowledge-based systems and various searching algorithms used in the development of AI system. The later part of the chapter explains with the natural language processing and importance of expert systems in future implications. The chapter concludes by providing a brief discussion on neural networks and AI languages.

24.1 INTRODUCTION

For a very long time, even before the advent of digital computers, many scientists were convinced that machines could be made to exhibit intelligent behaviour. Hence, it was natural that as soon as computers appeared, researchers began to program them to do things, considered to be possible for the human mind only such as solving non-numerical problems, understanding the English sentences, and playing chess. In the last few decades, computers have shrunk in size and also in terms of cost. The memory inside the computer system has increased so much that it is now equivalent to a substantial portion of human brain's storage capacity. With the availability of new hardware and software, computers are being specifically developed for performing some very complex tasks to ease the pressure on human mind. For example, nowadays computers are used to forecast weather conditions and simulate extraordinary galactic events like the birth of a star. Assessing these complex problems requires a lot of computational work, which puts tremendous strain on human mind. Scientists realized that human mind cannot be pushed beyond certain limits and thus they began working on the development of systems, which have certain level of intelligence, similar to that of human brain. This gave birth to the concept of Artificial intelligence (AI).

John McCarthy coined the term “Artificial Intelligence” in 1956 at the Massachusetts Institute of Technology (MIT). According to McCarthy, AI is the science and engineering of making intelligent machines, especially intelligent computer programs. It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable. In simple terms, AI is the branch of computer science devoted to developing programs that enable computers to display behaviour that can broadly be characterized as intelligent. This chapter deals with the basic understanding of AI and some of its most important aspects such as expert system, natural language processing (NLP), neural networks, and robotics.

24.1.1 What Is Intelligence?

Previously, we defined AI as a branch of computer science that deals with the study and creation of computer systems that exhibit some form of intelligence. Now the question arises what is intelligence. We can define intelligence as the ability to acquire, retrieve, and use knowledge in a meaningful way. It includes both raw and refined knowledge and the ability to memorize, recall facts, and express emotions. Mainstream thinking in psychology regards human intelligence not as a single ability or cognitive process but as an array of separate components. Research in AI has focussed chiefly on the following components of intelligence:

• Learning: It is the process of acquiring knowledge, skills, experience, or values by study, experience, or training.
• Reasoning: It refers to the ability of drawing conclusions that are appropriate to the situation in hand.
• Understanding: It refers to the identification of the significance, interpretation, or explanation for certain data or information. Simply put, it is the ability to employ knowledge.
• Creativity: It is the ability to generate new ideas or to conceive new perspectives on existing ideas. The creativity process involves producing ideas, which are original and potentially useful.
• Intuition: It is the inner knowledge, without rational processes and without being aware of how we know. Essentially, intuition is an uncanny sixth sense that tells people that whether they are right (Figure 24.1).

 

 

Scientists around the world have been trying to develop computer systems exhibiting the above features and they succeeded partially too. Systems have been developed to solve complex mathematical problems, plan strategies for military purposes, diagnose new medical diseases, and many such applications.

24.1.2 Turing Test

In 1950, Alan Turing proposed a test (known as Turing test) to prove the intelligence of a machine. This test provides the basis of what came out to be known as AI. There are three participants involved in this test: two humans and a machine. The idea was that a human and a machine, both outside the view, would give answers to a human interrogator, preferably in the form of a printed response. Based on the answers received, the interrogator would decide which respondent was the machine. The task of the machine is to deceive the interrogator into believing that it is a human being. The task of the other participant is to convince the interrogator that he/she is human. If the interrogator cannot reliably distinguish the human from the machine, then the machine does possess (artificial) intelligence (Figure 24.2).

 

24.2 ARTIFICIAL INTELLIGENCE: DEFINITION

Researchers around the world have defined AI in varied perspectives. Some of the well-known definitions of AI are:

“The automation of activities that we associate with human thinking, activities such as decision-making, problem-solving, learning” —Bellman, 1978	“The study of how to make computers do things at which, at the moment, people are better” —Rich and Knight, 1991
“The study of mental facilities through the use of computational models” —Charniak and McDermott, 1985	“The branch of computer science that is concerned with the automation of intelligent behaviour” —Luger and Stubblefield, 1993

As evident from these definitions, AI falls into four categories as shown in Figure 24.3.

 

 

Each of these categories represents a unique field in its own right but at the same time all four categories share a common ground.

• Thinking Humanly: Thinking comes naturally to human beings and we term it as common sense. The discipline that deals with the basic physics of human intelligence is known as cognitive science. Cognitive scientists try to construct theories of how the human mind works. In this process, a model of intelligent human behaviour is created to simulate on a computer to determine if it exhibits the same intelligent behaviour as humans.
• Acting Humanly: The system should pass the Turing test, which distinguishes intelligent entities from unintelligent ones. Acting humanly also includes physical interactions with environment such as speech recognition and robotics.
• Thinking Rationally: Rational behaviour means doing the right thing, which is expected to maximize goal achievement in available information. Thinking rationally involves mathematical logic as a tool (notation plus derivation rules). The problems and knowledge must be translated into formal descriptions. The system should use an abstract reasoning mechanism to derive a solution.
• Acting Rationally: It may not necessarily involve thinking but thinking should be in the service of rational action. Hence, acting rationally and thinking humanly are complementary. Most AI researchers in Computer Science go for acting rationally.

24.2.1 Domain Areas of AI

Various domain areas where AI is currently being used include:

• Game Playing: The greatest advancements in AI have been achieved in the field of game playing. For example, computer chess programs are now capable of beating humans. In May 1997, an IBM super computer called Deep Blue defeated the world chess champion Garry Kasparov.
• Speech Recognition: Computer speech recognition has reached a practical level for limited purposes. For example, airline organizations have replaced keyboard for flight information by a system using speech recognition of flight numbers and city names.
• Understanding Natural Language: Just getting a sequence of words into a computer is not enough, and even parsing sentences is not enough. The computer has to be provided with an understanding of the context of the text, and this is presently possible only for very limited systems.
• Computer Vision: The world is composed of three-dimensional objects, but the inputs to the human eye and computer's cameras are two dimensional. Some useful programs can work solely in two dimensions, but full computer vision requires partial three-dimensional information. At present, there are only limited ways of representing three-dimensional information directly, and they are not as good as what humans evidently use.
• Expert Systems: Computers are programmed to make decisions in real-life situations. For example, some expert systems help doctors diagnose diseases based on patient's symptoms. One of the first expert systems was MYCIN, which diagnosed bacterial infections of the blood and suggested treatments. This system performed better than medical students or practicing doctors.
• Heuristic Classification: A heuristic is a way of trying to discover something or an idea embedded in a program. An example is advising whether to accept a proposed credit card purchase. Information is available about the owner of the credit card, his record of payment, and also about the item he is buying and about the establishment from which he is buying it (for example, whether there have been previous credit card frauds at this establishment).
• Neural Networks: Computers are programmed to simulate intelligence by attempting to reproduce the types of physical connections that occur in human brains. Neural computing systems mimic the brain through a network of highly interconnected, processing elements, which give them learning capabilities and enable them to recognize and to understand subtle or complex patterns.
• Robotics: It deals with programming computers to see, hear, and react to other sensory stimuli. In the area of robotics, computers are now widely used in assembly plants, but they are capable of only limited tasks. Robots have great difficulty identifying objects based on appearance or feel, and they still move and handle objects clumsily.

Researchers have still not been able to produce systems, which can match the natural abilities possessed by an average human being. These abilities include learning new sounds as well as recognizing them later, adapting to new conditions, recognizing and remembering numerous objects through eyes, and many such things. These are some of the problems faced by researchers pioneering in the field of AI, and all these problems require breakthroughs before one can expect a system to behave and react like humans and exhibit 100 per cent intelligence. Currently, AI focuses on lucrative domain-specific applications, which do not necessarily require the full extent of AI capabilities. There is little doubt among researchers that artificial machines will be capable of intelligent thought in the near future. It is just a question of “how and when.”

24.2.2 Brief History of AI

Contrary to popular belief, AI did not start with the first computer. The first computer was developed in early 1940s. The discovery of the computer allowed AI to become possible. However, the link between human intelligence and machines was not made until the early 1950s when Norbert Wiener, an American computer scientist, observed that all intelligent behaviour was the result of feedback mechanisms, which could also be simulated by machines. Soon after, Allen Newell and Herbert Simon developed “The Logic Theorist,” considered by many to be the first AI program.

In 1956, John McCarthy organized a conference in Dartmouth on artificial Intelligence, thus coining the term. The conference laid the groundwork for the research on AI. In 1958, McCarthy developed the LISP (list processing) language, which is still used in AI programming even today. The progress in this field continued and it seems, for now, that we can expect to see many more advances. Some of the main highlights in the life of AI are listed in Table 24.1.

 

Table 24.1 Milestones in AI Development

Year	Milestones
1964	Danny Bobrow showed that computers were able to understand natural language enough to solve algebra word programs
1970	Colmcrauer created PROLOG
1974	First computer-controlled robot was developed
1979	The Stanford Cart, the first computer-controlled vehicle, was built The Journal of American Medical Association said that MYCIN was as good as medical experts
1981	Kazuhiro Fuchi announced Japanese Fifth Generation Project
1994	Mid-1990s brought major advances in all areas of AI including games, translations, reasoning, and virtual reality
1997	IBM computer Deep Blue beat chess world champion Garry Kasparov
1999	AI-based information extraction programs like web crawlers became an essential web tool
2000	Interactive robot pets became commercially available, the most famous being Sony's AIBO. MIT showed off Kismet, a robot able to express emotions. Carnegie Mellon robot Nomad explores remote areas of the Antarctica and locates meteorites
2002	Researchers at the MIT artificial Intelligence Lab, introduced Roomba, a vacuum cleaning robot
2005	Stanford robot won the DARPA Grand Challenge by driving autonomously for 131 miles along a desert trail. Also, Honda's ASIMO robot, a humanoid robot, is able to walk as fast as a human, delivering trays to customers in restaurant settings
2007	A team of researchers at the University of Alberta solved the game of Checkers
2009	The Blue Brain Project had successfully simulated parts of a rat's brain

AI is not just hype, as many real working applications use AI techniques. However, AI is not yet a reality either, as AI researchers are yet to develop a system that spans the full spectrum of intelligent behaviour.

24.3 KNOWLEDGE-BASED SYSTEMS

Knowledge is defined as the remembering of previously learned material. It is the psychological result of perception and learning and reasoning. It is the body of truth, information, and principles acquired by humankind. In humans, knowledge is stored as a collection of interconnected neurons (brain cells) in the brain, which contains approximately 1012 neurons. These neuron interconnections provide approximately 1014 bits of potential storage capacity. In computers, knowledge is stored in the form of voltage states. The gap between human and computer storage capacities has come down with computer now being able to store hundreds of gigabytes of data. However, there still exists a wide gap between humans and computers in terms of efficiency and the way data are represented. Knowledge plays an important role in building intelligent systems. Earlier, researchers developed general-purpose problem-solvers as an approach to prove theorems in geometry, perform complicated operations, and guide robots to perform the required tasks. All the systems made for these purposes failed to be of great help, as they required much of human interference for both identifying and finding solution to problems. These systems became effective only after the steps to achieve solution were incorporated with specific rules and facts. These systems were very general in nature, i.e. these were developed to solve different kinds of problems and were not specific to one problem. This realization led to the design of systems commonly known as knowledge-based systems. Many knowledge-based systems have been developed for different fields, for example, for diagnosing diseases, for configuring computer systems, in electrical circuits and financial markets, for scheduling airplanes and buses, and so on.

Knowledge plays an important role in building intelligent systems. Earlier, researchers developed general-purpose problem-solvers as an approach to prove theorems in geometry, perform complicated operations, and guide robots to perform the required tasks. All the systems made for these purposes failed to be of great help, as they required much of human interference for both identifying and finding solution to problems. These systems became effective only after the steps to achieve solution were incorporated with specific rules and facts. These systems were very general in nature, i.e. these were developed to solve different kinds of problems and were not specific to one problem. This realization led to the design of systems commonly known as knowledge-based systems. Many knowledge-based systems have been developed for different fields, for example, for diagnosing diseases, for configuring computer systems, in electrical circuits and financial markets, for scheduling airplanes and buses, and so on.

24.3.1 Knowledge Acquisition

A knowledge-based system depends on quantity as well as on quality of knowledge. For this, knowledge needs to be acquired from different sources such as specified procedures, rules, and facts. This acquisition of knowledge is one of the biggest bottlenecks in the construction of a knowledge-based system. Converting information gathered from various sources into knowledge and then using it is a big challenge. This may involve making raw knowledge explicit, identifying gaps in the knowledge already stored in the memory, acquiring and integrating new knowledge, and so on.

Knowledge acquisition is the foremost process in building knowledge-based systems. It is subject to in-depth research devoted towards the development of methods and software tools to provide knowledge content for knowledge-based systems. Many tools and techniques are now available for acquiring, analysing, and modelling knowledge. For example, the matrix-based technique involves the construction of grids to indicate problems encountered under some specific conditions. Some methodologies have been introduced to provide framework and standard knowledge to help knowledge acquisition activities and ensure that the development of each knowledge-based system is performed in an efficient manner.

24.3.2 Knowledge Organization

Knowledge-based systems usually require thousands of facts and rules to be incorporated in a system's memory. Therefore, it is essential that knowledge is stored in such a way that retrieval of information can be easy. Otherwise, a lot of time will be wasted in searching and testing large numbers of items (knowledge) stored in memory. One way of organizing knowledge in the memory is by using a method known as indexing. In this method, knowledge is grouped in such a way that the “key word points” are used to access the required group. By using this method, only a fraction of knowledge is referred to instead of referring the whole memory. Thus, it saves time and leads to improved efficiency. Further, if appropriate representation scheme is used then the complexity involved in organizing knowledge can be avoided.

24.3.3 Knowledge Manipulation

In knowledge-based systems, decisions and actions are based on the manipulation of knowledge in specified ways. Typically, some form of inputs (usually from keyboard) initiates a search. This process requires that the known facts be compared, and possibly be altered, in some way. The manipulation process is continued (may require further inputs) until a final solution is found. Manipulation of knowledge is the computational equivalent of reasoning, which requires a form of inference or deduction, using the knowledge and inferring roles.

24.3.4 Knowledge Representation

Knowledge can be acquired, organized, and manipulated but it is meaningless unless represented in a proper manner. Some AI researchers thought that the best way to represent knowledge would be the way it is represented in human mind. Unfortunately, the representation of knowledge in the human mind is not yet known. For this reason, various AI languages and notations have been proposed for representing knowledge in systems exhibiting intelligence. Generally, these are based on logic and mathematics, which includes easily parsed grammar to ease processing in a system. Knowledge can be represented in many forms, as spoken or written words, in the form of graphical representation, as strings, and so on. The choice of representation depends on the problem to be solved (Figure 24.4).

 

 

AI researchers, for developing intelligent systems, have used several representation schemes. One of the most successful and widely used representation schemes is first-order predicate logic (FOPL). It has gained popularity because it is a well-developed theory, which uses valid forms of reasoning, and has good expressive power. However, this scheme cannot be used in areas involving common sense reasoning. Another representation scheme is fuzzy logic, which is a process of reaching conclusions based on information and facts that are not 100 per cent certain. Other type of representation scheme, which is commonly used, is associative networks. It is a graphical representation scheme and uses concepts and nodes where each node represents a concept and arcs are used to define the relations between the concepts.

First-Order Predicate Logic (FOPL):    FOPL is one of the most widely used representation schemes developed by researchers for formal reasoning, primarily in the area of mathematics. This scheme offers a formal approach to reasoning and has a very strong base, which is essential when new systems are to be developed. It is a very descriptive representation scheme with a well-founded method of deriving new knowledge from a database. FOPL comprises logic, which contains symbolic representation to represent concepts. Like any logical theory, FOPL consists of specific design to construct syntactically correct statements (the well-formed formulas). Statements written in natural languages, for example, English, can be translated into a well-designed symbolic form. This symbolic form consists of the following symbols and rules.

• Predicate: This symbol returns a value as true or false. Capital letters and capital words like A, B, NOT, EQUAL are used to represent predicates.
• Functions: These are used to indicate relations and are denoted by small letters. For example, p, q, sister-of are used to represent functions.
• Variables: These are terms having different values and are represented by small letters, for example, x, y, and so on.
• Constants: These terms have fixed values, which cannot be changed and are denoted by small letters or numbers such as a, b, 3.
• Logical Quantifiers: There are two Quantifiers: existential and universal. Existential quantification (3x) means that there exists an x while universal quantifer (Vx) means for all x.
• Connectors: Symbols like v (disjunction), ~ (negation), a (conjunction), → (implication), and ↔ (equivalence) are used for connecting statements.

Example:

Let us discuss a simple example. Consider the following two statements.

1. All humans are mortal.
2. Maria is human.

Since all humans are mortal and Maria is a human being, it may be concluded that Maria is also mortal.

Hence, the following sentence is also correct.

Maria is mortal.

In FOPL, we represent the above discussion as:

For all objects h:

Human(h) → Mortal(h)

Thus, substituting Maria for h:

Human(Maria) → Mortal(Maria)

“for all” is written as ∀, so

((∀h)(Human(h) → Mortal(h)) ^ Human(Maria)) → Mortal(Maria)

Fuzzy Logic:    Fuzzy logic is a type of knowledge representation that resembles human thinking. Like humans, it can measure imprecise or vague entities. Logic based on the two truth values, true and false, is sometimes inadequate when describing human reasoning. Fuzzy logic uses the whole interval between 0 (false) and 1 (true) to describe human reasoning. In two-valued logic, a proposition is either true or false, but not both. The truth or falsity, which is assigned to a statement, is its truth value. In fuzzy logic, statements are not necessarily only true or false, but also can be very unlikely, or more, or less certain.

Lotfi Zadeh, a professor at the University of California at Berkley, developed the concept of fuzzy logic in 1965. Fuzzy logic allows computers to emulate the human reasoning process, which makes decisions based on vague or incomplete data, by assigning values of degree to all the elements of a set. Some of the characteristics of fuzzy logic are:

• It is useful in manipulating information that is incomplete, imprecise, or unreliable.
• It deals with ambiguities, rather than only yes/no options.
• Fuzzy sets may overlap one another such as something that is both sweet and sour.
• It uses the operations AND, OR, and NOT.
• It can be implemented in hardware or software or in both.

The approach followed by fuzzy logic is different from the earlier schemes. It uses a simple rule “IF A AND B THEN C” approach for solving a control problem rather than modelling a system mathematically (as done in FOPL). It is empirically based and depends on a user's experience rather than on technical knowledge of a system. Let us consider a simple example to understand the execution of fuzzy logic rule. Suppose, we have an object which is made up of glass and it emits light. Then, the fuzzy logic notation will be as follows:

IF (object is made up of glass) AND (light is yellow) THEN (object is a bulb) or

IF (object is made up of glass) AND (light is not yellow) THEN (object may or may not be a bulb) (Figure 24.5)

 

 

Fuzzy logic was originally conceived as a method for handling and sorting data, but researchers have used it successfully to control many system applications. An advantage of fuzzy logic is that it can be easily integrated into all types of products ranging from handheld to a large computerized processing system. Some applications where fuzzy logic has been very successful are consumer electronic goods such as washing machines, air conditioners, digital cameras, and video games. It is also used in automobiles for braking purpose, for cruise control, and has been successfully incorporated into some microprocessors.

Automatic washing machines, which became popular in the 1960s, use fuzzy logic to control the washing system. The fuzzy logic automates the washing process by controlling the water and soap intake, draining, and rotation of the drum in a proper sequence. The fuzzy logic present in it senses the load size (number of clothes) and detergent concentration and accordingly adjusts the timing for wash cycles. Different types of clothes can be handled using different programmed cycles. For example, a wool wash needs a low temperature and less agitation as compared to cotton wash. Most automatic washing machines control the sequence using an electromechanical timer which has inbuilt fuzzy logic.

Associative Networks:    An associative network, also known as semantic network, is commonly used as a form of knowledge representation. It is a directed graph consisting of labelled nodes and arcs, where the nodes represent concepts and arcs represent relationship between concepts. Computer implementations of semantic networks were first developed for AI and machine translation (MT), but they have long been used in philosophy, psychology, and linguistics. The most common form of semantic networks uses the relationship between nodes to represent IS-A and HAS relationships between nodes.

Figure 24.6 shows that a car IS-A vehicle; a vehicle HAS wheels. This kind of a relationship establishes an inheritance hierarchy in the network, with nodes lower down in the network inheriting properties from the nodes higher up. There are a number of commonly used semantic networks, which include definitional networks, assertional networks, implicational networks, executable networks, learning networks, and hybrid networks. All these semantic networks have a declarative graphic representation, which can be used either to represent knowledge or to support automated systems for reasoning about knowledge.

 

24.4 SEARCHING TECHNIQUES

In 1950s, researchers were engaged in developing systems in the field of theorem-proving and problem-solving. In both fields, the developed programs were characterized by complex algorithms that had a general solving capability independent of the problem domain at hand. Proving theorem was concerned with a given set of logics by a computer. Researchers in the field of problem-solving focused on the development of computer systems with a general capability for solving different types of problems. One of the early systems for problem-solving is GPS (general problem solver), developed by Alan Newell, Herb Simon, and Jack Shaw in 1960. It was developed as a research tool, which was responsible for separating task knowledge from the problem-solving part. The aim involved was to write a single computer program, which could solve any problem. In GPS, a given problem is represented in terms of an initial state, a final state, and a set of steps to transform existing states into new states. However, GPS was not very successful. The main disadvantages of using this were:

• Representing a non-trivial problem in terms of GPS proved to be a daunting task.
• GPS turned out to be inefficient because it was a general problem-solver and was not designed for handling specific problems.

Although the success of GPS as a problem-solver was limited, it shifted the attention of AI researchers towards more specialized systems. This shift in attention from general problem-solvers to specialized systems led to the development of certain searching techniques to solve specific problems.

Problems are defined in terms of different states and then searching is used to find an optimal state out of available states. For every problem, there are a number of alternatives available to find a solution. For example, a program written to understand natural language should be able to find exact matching words rather than finding individual letters. A search algorithm is represented as a directed graph or in terms of tree formation. A search tree is a graph in which each node (state) has only one parent, except the starting node, also known as the root node. The nodes that branch out of the parent node are known as children nodes. The nodes at which no further Classification of node (expansion) is specified are known as terminal nodes. The starting node is the initial state and the goal node is the final state (where optimal solution is achieved). While performing a search, a solution to the problem is considered as a sequence of operations that helps in achieving goal state from the given initial state. The best solution is achieved when a technique uses least operations or costs as compared to other states.

Using tree as a technique for finding a path, search is carried out by first identifying the child nodes from a parent node. Once this is accomplished, child nodes are generated from the parent node and this process is known as expansion of node. Search problems can be categorized into two groups:

• When only information relating to goal node and starting node is given, then search is performed using a uninformed or blind search.
• When some additional information is present other than the starting and goal node, then informed or heuristic search is used (Figure 24.7).

 

24.4.1 Uninformed Search

An uninformed search proceeds in a systematic way by exploring nodes in some predetermined order. This form of search can only distinguish between goal nodes from other nodes in the search tree and only knows the length of the path or the cost of the path from the starting node to each node. The important search strategies used in this form include breadth-first search and depth-first search.

Breadth-First Search:    In this searching technique, all the child nodes are placed at the end of the queue in any order. Search is performed by expanding all nodes at one level before proceeding to the next level (see Figure 24.8). Hence, all nodes at level i in the search tree are expanded before proceeding to level i +1. This strategy has the advantage of finding a minimal length solution whenever there exists one. However, many nodes are required to be expanded before reaching the goal node, which increases the time involved.

 

Depth-First Search:    Choosing the node at the deepest level of the tree performs the depth-first search. This is accomplished by first generating a child node, say at level i, from the most recently expanded node at level i – 1. This process is continued until the goal node is found or when the deepest level of the tree is reached. If the goal node is not found or when the deepest level is reached, search hits a dead-end and returns back to expand nodes at a preceding level. This process continues until a goal node is found or a failure occurs (Figure 24.9).

 

 

In cases where a problem has many solutions, depth-first search is a better option than breadth-first search, since there is a good chance that a goal node will be achieved after exploring only a small portion of the tree in depth-first search. However, depth-first search may not perform properly even when a solution exists at a relatively shallow level. Therefore, depth-first search is not complete and not optimal and is avoided for problems with deep or infinite paths.

24.4.2 Informed Search

Uninformed methods of search are capable of systematically exploring the search tree to find goal state. However, such methods have proved inefficient in most cases. Therefore, informed search strategies are used to find optimal solution (goal state). When information other than the starting node and goal node is given, a more efficient search method, known as informed search, is used. In informed search, a priority-ordered queue is used. This ordering is determined by an evaluation function, which for each node on the queue returns a number that signifies the value of that node. Functions that calculate such estimates are called heuristic functions. Heuristic means a common sense rule (or set of rules) that is intended to increase the probability of finding a solution of a given problem. In simple terms, heuristic information is used in searching techniques to guess which nodes to expand next, thereby obtaining a solution in less time. Solutions based on heuristics do not provide any guarantee in terms of achieving success because heuristics may be inaccurate or it may not find the best answer. Various search techniques using informed search include best-first search and hill-climbing search.

Best-First Search:    This technique uses heuristic information for performing search and finding the most promising (the least valued node) path to achieve the goal node. This technique always finds an optimal solution, even when local variance is present between the nodes. It also makes use of all estimates that were computed for previously generated nodes and makes a best selection among them. In this searching technique, the first element in the queue is removed, queue is expanded, and child nodes are placed in queue at either end and then arranged in ascending order (Figure 24.10).

 

Hill-Climbing Search:    In this method, hill is referred as goal state of any given problem. At each point in the search path, a successor node that appears to lead quickly to the top of the hill (goal state) is selected for exploration. When all the child nodes have been generated, alternative solutions are evaluated using heuristic function. The path that appears most promising (optimal) is chosen and no further reference to the parent node or children node is retained (Figure 24.11).

 

24.5 NATURAL LANGUAGE PROCESSING (NLP)

Natural language refers to a medium (like English) for expressing thoughts and feelings. It requires both linguistic knowledge of the particular language being used and worldly knowledge related to the topic being discussed. Understanding natural languages is difficult. Language processing is divided into two tasks.

• Processing written text by using lexical, syntactic, and semantic knowledge of the language.
• Processing spoken language by using all the information mentioned plus additional knowledge about phonology.

NLP involves the interpretation, manipulation, or generation of human language by computer so that one can communicate with a computer as one communicates with another person. It studies the problems inherent in the processing and manipulation of natural language. Achieving this goal is not easy, as it requires proper understanding of language, knowing concepts related with a word or a phrase. It is ironic that even though humans develop the computer, it still cannot understand the language spoken by humans. Humans perceive and communicate using five basic organs. These organs are eyes for visualizing, ears for hearing, skin for feeling, nose for smell, and tongue for taste. Among all these, visualization and hearing are very complex to comprehend. These are the major tasks facing researchers engaged in developing intelligent systems. This is because computers use mathematical processes to carry out tasks and understand these processes much more quickly than most humans. However, computers are not able to process human or natural language as compared to human beings. Thus, developing programs, which can relate to natural language, is very difficult. NLP involves many aspects of linguistics. These require analysis at low levels as well as at higher levels of syntax and discourse. The steps involved in the process of natural language comprehension are:

Morphological Analysis:    Individual words are analysed into components, and non-word tokens (like punctuation) are separated from the words. For example, in the phrase “Jack's office,” the proper noun Jack is separated from the possessive suffix “'s.”

Syntactic Analysis:    Linear sequences of words are transformed into structures to show relationship between one word and another. This step converts the list of words of the sentence into a structure that defines the units represented by that list. Constraints imposed include word order (“Adam 10 dollars” is an illegal constituent in the sentence “I gave Adam 10 dollars”), number agreement, and case agreement.

Semantic Analysis:    In this step, the structures created by the syntactic analyser are assigned meanings. This step maps individual words into appropriate objects in the knowledge base and creates correct structures corresponding to the individual words. For example, the sentence “ice-cream ate John” will be termed as a meaningless sentence.

Discourse Integration:    This step involves introduction of entities in the sentence either defined explicitly or introduced earlier in a logical manner. Here meaning of an individual sentence depends on the sentences that precede it and influence the sentences, which is yet to come. For example, the word “it” in the sentence: “Tom needed it” depends on the preceding context, while the word “Tom” could influence the meaning of later sentences such as “He always laughs.”

Pragmatic Analysis:    This is a high-level knowledge, which relates to the use of sentences in different context and how this context affects the meaning of the sentences.

24.5.1 Uses of NLP

NLP is mainly used in the following areas:

• Knowledge Acquisition: This includes programs that can read books and manuals or the newspaper. Therefore, there is no need to explicitly encode all the knowledge needed to solve problems.
• Information Retrieval: This includes searching articles about a given topic. The programs are developed in such a way that they determine whether the article matches a given query.
• Translation: This requires machines to translate from one language to another automatically.
• Helper Tools: It is used in the areas of spell and grammar checkers, accessibility aids, screen readers (such as JAWS), computer-assisted language learning (CALL), lexicography, and MT.

24.6 EXPERT SYSTEMS

A recent application of AI is expert systems, which began to emerge during the 1970s. These systems have proven effective for finding solutions to a large number of problem domains, which earlier required the assistance of human mind.

“An expert system can be defined as embodiment within a computer of knowledge-based component from an expert skill in such a form that the machine can offer intelligent advice or take an intelligent decision about a processing function.” It is an AI application that uses a knowledge base of human expertise to aid in solving problems. The degree of problem-solving is based on the quality of the data and rules obtained from the human expert. This system simulates the judgment and behaviour of a human or an organization that has expert knowledge and experience in a particular field. Typically, such a system contains a knowledge base containing accumulated experience and a set of rules for applying the knowledge base to each particular situation.

The primary goal of expert systems research is to make solutions available to decision-makers and technicians involved in an expert system. A system is designed in expert systems by manipulating and understanding knowledge, which is acquired through experience and extensive learning—rather than using simple information. Problem-solving is accomplished by applying specific knowledge rather than a specific technique. This reflects the belief that human experts do not process their knowledge differently from each other, but they do possess different knowledge. The principal distinction between expert systems and traditional problem-solving programs is the way in which the problem-related query is programmed. In traditional applications, problem is encoded in both program and data structures. While in expert system approach, the problem is encoded in data structures only. The general architecture of an expert system consists of two components:

• A problem-dependent set of data declarations called the knowledge base or rule base, and
• A problem-independent program called the inference engine. Some expert systems are designed to act or perform like human experts, while others are designed to aid human expert.

24.6.1 Characteristics of Expert System

An expert system must exhibit the following set of characteristics:

• It should solve difficult programs in a domain, as good as or better than human experts.
• It should possess vast qualities of domain-specific knowledge to the minute details.
• It should permit the use of heuristics search process.
• It should be capable of accepting advice, modify, update, and expand.
• It should deal with uncertain and irrelevant data.
• It should communicate in their natural languages.
• It should possess the capacity to cater the individual's desire.

24.6.2 Applications Areas of Expert System

Expert System originally focused its activities on specific products such as spelling correctors for both general purposes and/or specialized use for governments as well as for specific clients. This initial experience led to improvement in technical knowledge in text processing and development of various types of different applications. The main areas where expert systems are used include chemistry, biology, aerospace, finance, banking, and military.

Expert systems are currently being used in applications such as medical diagnosis, equipment repair, financial, and insurance planning, route scheduling for delivery vehicles, production control and training. For example, there are expert systems that can diagnose human illnesses, make financial forecasts, and so on. These expert-based applications of AI have greatly enhanced the productivity.

The early knowledge-based systems were mostly concerned with the field of medical diagnosis only. The best-known knowledge-based system in medicine, developed in the 1970s, was MYCIN. The development of this knowledge-based system took place at Stanford University. This system assists medical specialists in internal medicine to the diagnosis and the treatment of a number of infectious diseases, particularly meningitis and bacterial septicaemia. When a patient shows signs of such an infectious disease, usually a sample of blood and urine is taken in order to determine the bacterium species that causes the infection. MYCIN gives an interim indication of the organisms that are most likely to be the cause of the infection. Given this indication, MYCIN advises the administration of a number of drugs that control the disease by suppressing the indicated organisms.

With advances in the last decade, today's expert system clients can choose from a variety of commercial software packages with easy-to-use interfaces.

24.6.3 Users in Expert Systems

Generally, three individuals are involved in expert systems. These are:

• End-User: The end-user is an individual who uses the system for its problem-solving assistance
• Problem-Solving Expert: This expert builds the knowledge base for a system and is responsible for transferring the entire knowledge about the specific domain to the system.
• Knowledge Engineer: The knowledge engineer is concerned with assisting the representation chosen for the expert system. This engineer defines the inference engine used to process knowledge, which is required to obtain useful problem-solving activity (Figure 24.12).

 

24.6.4 Benefits of Expert Systems

The following are the benefits of expert system:

• Expert systems work faster than humans, which means that less number of workers are needed. This reduces the cost of the product and increases the output.
• Expert systems provide consistent advice, thus reducing the error rate.
• Expert systems make knowledge accessible to people easily, which query the system for some specific advice.
• Expert system provides a great amount of flexibility to the system.
• Expert systems are useful in interdisciplinary domains where multiple experts are required.

24.6.5 Limitations of Expert Systems

The following are limitations of expert systems:

• It is very specific in nature. The major problems lie in extracting the knowledge, building, and maintaining large knowledge bases.
• Lack of proper knowledge representation hampers the progress in expert system development.
• Program description is language dependent.
• Expert system development is quite expensive and time consuming.
• Present-day expert system lack human reasoning to some extent.

24.7 NEURAL NETWORKS

Neural networks have emerged as a specialized field within AI and engineering disciplines with collective efforts of engineers, physicists, mathematicians, and scientists (both computer and neuroscientists). Here, the area of research focuses on pattern recognition and pattern generation, embedded within an overall focus on development of systems.

Neural networks are computing systems, which imitate human brain through a network of highly, interconnected processing elements. These processes give these networks learning capabilities and enable them to recognize and to understand complex patterns. The key element of neural network is the presence of the information processing system. This system is composed of a large number of highly interconnected processing elements (neurons) working together to solve specific problems. Neural networks just like humans learn by example, that is, they are configured for a specific application such as pattern recognition or data Classification, through a learning process (Figure 24.13).

 

 

A perceptron is one of the earliest neural network model built by Rosenblatt in 1962. In this model, a neuron takes weighted sum of inputs and sends the output if sum is greater than any adjustable threshold value. The input in a perceptron are x₁, x₂,…, x_n and connection weights are w₁, w₂,…, w_n. If the presence of some feature xi tends to cause the perceptron to fre, the weight wi will be positive and if the feature xi inhibits the perceptron, the weight wi will be negative.

Neural networks take a different approach to solve a problem as compared to conventional computers. Conventional computer follows a set of instructions in order to solve a problem and requires specific steps to solve a problem. This restricts the problem-solving capability of conventional computers to problems whose solutions are already known. Neural network's ability to learn by example makes it a very flexible and powerful concept. Furthermore, there is no need to devise an algorithm in order to perform a specific task, that is, there is no need to understand the internal mechanisms of a problem.

Traditional AI and neural networks are generally considered for solving different types of problems. These two approaches appear to be different but currently the strengths of both the concepts are merged together to develop a system. The neural networks have been applied successfully in the AI field to speech recognition, image analysis and adaptive control, and to construct software agents (like video games) or autonomous robots.

24.7.1 Benefits of Neural Networks

Either humans or other computer techniques can use neural networks, with their ability to derive sense from complicated or imprecise data, to extract patterns and detect trends that are too complex to be noticed. Some of the important benefits of neural networks are:

• Ease of Use: Neural networks learn by example. The neural network user gathers representative data and then invokes training algorithms to automatically learn the structure of the data, thus reducing complexity.
• Adaptive Learning: An ability to learn how to do tasks based on the data given for training provides these networks an edge over the present systems.
• Self-Organization: A neural network can create its own organization or representation of the information it receives during learning time.
• Real-Time Operation: Computations are carried out in parallel, and special hardware devices are being designed and manufactured which take advantage of this capability.

24.7.2 Applications of Neural Networks

Neural networks are applicable in areas where a relationship between the predictor variables (independents, inputs) and predicted variables (dependents, outputs) exists. Neural networks have been used in a wide range of applications, the majority of which include areas associated with problems in pattern recognition and control theory. A few examples of problems to which neural network analysis have been applied successfully are:

• Medicine: A variety of health-related indices (like respiration rate) can be monitored. Neural networks have been used to recognize the predictive pattern so that the appropriate treatment can be prescribed.
• Stock Market: Neural networks are used by many technical analysts to make predictions about stock prices based upon a number of factors such as past performance of stocks and various economic indicators that are available.
• Monitoring Machinery: Neural networks can be instrumental in minimizing costs by bringing down costs of maintaining machines.
• Engine Management: The neural network controls various parameters within which the engine functions, in order to achieve a particular goal such as minimizing fuel consumption.

The prospect for neural networks is excellent. With the increase in sophistication of the underlying theory and range of applicability of the techniques, the research in this field is certain to persist and bring new strength into related fields.

24.8 AI LANGUAGES

AI programs are written in specialized languages designed specially for AI. The two AI languages commonly used are PROLOG (PROgramming LOGic) and LISP (LISt Processing). Both languages have features, which make them suitable for AI programming. These include support for list processing, pattern matching, and examining programming. The basic differences between AI and conventional programming are illustrated in Table 24.2.

 

Table 24.2 Comparing AI languages with Conventional Languages

Feature	AL Languages	Conventional Languages
Processing Type	Symbolic	Numeric
Technique Used	Heuristics search	Algorithmic search
Solution Steps	Implicit	Explicit and precise
Answer Sought	Satisfactory	Optimal
Involves	Large knowledge base	Large database
Knowledge	Imprecise	Precise
Process	Inferential	Repetitive

 

LISP was developed in the 1950s and was regarded as the base of functional programming. It is based on function definitions and remains a useful, powerful, and widely used programming language till today. LISP uses the list as its fundamental representation for function definitions and provides a wide range of inbuilt functions for manipulating lists. The list allows complex symbol structures (representing AI knowledge) to be easily manipulated. LISP is still a highly popular language used for the development of knowledge-based systems, although it has obtained significant competition from Java and C++, particularly in the development of systems that involve some numerical computation.

PROLOG is another language used for AI programming. It is presented with a set of facts, rules, and goals, and it attempts to prove that the goals become true when the set of rules are applied to facts. PROLOG is considered as a programming language derived from logic and theorem-proving. In particular, it is based on first-order predicate calculus. Writing simple PROLOG programs is similar to writing statements in predicate calculus, and “running” them involves setting queries for PROLOG.

Let Us Summarize

1. John McCarthy coined AI in 1956 at the Massachusetts Institute of Technology (MIT). According to him, AI is the science and engineering of making intelligent machines, especially intelligent computer programs.
2. Intelligence is the ability to acquire, retrieve, and use knowledge in a meaningful way. It includes both raw and refined knowledge and the ability to memorize, recall facts, and express emotions.
3. Intelligence is exhibited through learning, reasoning, understanding, creativity, and intuition.
4. Alan Turing proposed a Turing test to prove the intelligence of a machine. The test involved three participants: two humans and a machine.
5. AI is currently being used in various domain areas such as game playing, speech recognition, understanding natural language, computer vision, expert systems, heuristic Classification, neural networks, and robotics.
6. Knowledge is defined as the ability to remember earlier learned material, which involves the recalling of a wide range of materials; all that is required is bringing the appropriate information to mind.
7. Knowledge-based systems make extensive use of knowledge to perform complex tasks. This, in turn, led researchers to develop knowledge representation schemes and techniques to manipulate knowledge.
8. Knowledge acquisition involves conversion of information gathered from various sources into knowledge.
9. Knowledge organization involves storage of knowledge in such a way that retrieval of information becomes easy. This is done using indexing.
10. Knowledge manipulation is the computational equivalent of reasoning. This requires a form of inference or deduction, using knowledge and inferring roles.
11. Knowledge representation is based on logic and mathematics and has an easily parsed grammar to ease processing in a system. Some knowledge representation schemes are FOPL, fuzzy logic, and associative network.
12. Searching techniques involves the use of an optimal state out of available states. For every problem, there are a number of alternatives available to find a solution. It can be categorized into two groups: uninformed search and informed search.
13. Uninformed search proceeds in a systematic way by exploring nodes in some predetermined order. The important search strategies used in this form include breadth-first search and depth-first search.
14. Informed search strategies are used to find optimal solution. It involves evaluation function, called heuristic functions. It includes best-first search and hill-climbing search.
15. NLP involves the interpretation, manipulation, or generation of human language by computer so that one can communicate with a computer as one communicates with another person. It involves morphological analysis, syntactic analysis, semantic analysis, discourse integration, and pragmatic analysis.
16. Expert system is an AI application that uses a knowledge base of human expertise to aid in solving problems. The degree of problem-solving is based on the quality of the data and rules obtained from the human expert. This system simulates the judgment and behaviour of a human or an organization that has expert knowledge and experience in a particular field.
17. Expert systems are currently being used in applications such as medical diagnosis, equipment repair, financial and insurance planning, route scheduling for delivery vehicles, production control, and training.
18. Neural networks are computing systems, which imitate human brain through a network of highly, interconnected processing elements. These processes give these networks learning capabilities and enable them to recognize and to understand complex patterns.
19. Neural networks are applicable in areas where a relationship between the predictor variables and predicted variables exists such as medicine, stock market, monitoring machinery, and engine management.
20. AI languages are specialized languages designed specially for AI applications. These are PROLOG and LISP.

Exercises

Fill in the Blanks

1. Associative network is a direct graph consisting of..............and............
2. The important search strategies used in informed search are..............and...........
3. One of the earliest expert system developed for blood diseases was..............
4. Intelligence includes both..............and..............knowledge.
5. Knowledge plays an important role in building..............systems.
6. Fuzzy logic is another type of..............scheme.
7. Neural network's ability to learn by example makes it very..............and..............
8. Technique used in AI language is..............search.
9. ...............language uses the list as its fundamental representation for function definition.
10. .............. PROLOG is presented with a set of..............,.............., and.........

Multiple-choice Questions

1. AI is concerned with making computers behave like..............
   1. Humans
   2. Robots
   3. Home appliances
   4. None of these
2. In Turing test the number of participants are..............
   1. One
   2. Three
   3. Four
   4. None of these
3. Knowledge-based systems have been developed for fields such as..............
   1. Financial markets
   2. Diagnosing diseases
   3. Scheduling airplanes
   4. All of these
4. One way of organizing knowledge in memory is by using a method known as..............
   1. Chaining
   2. Matrix-based technique
   3. Indexing
   4. None of these
5. FOPL consists of some symbols and rules which are..............
   1. Predicate
   2. Functions
   3. Variables
   4. All of these
6. Fuzzy logic has been very successful in..............applications.
   1. Washing machines
   2. Air conditioners
   3. Dishwasher
   4. All of these
7. Which of the following search is not an uninformed search?
   1. Best-first search
   2. Depth-first search
   3. Breadth-first search
   4. All of these
8. NLP is mainly used in..............
   1. Knowledge acquisition
   2. Information retrieval
   3. Translation
   4. All of these
9. ...............individuals are not involved in expert system.
   1. Mechanical engineer
   2. End-user..............
   3. Problem-solving expert
   4. Knowledge engineer..............
10. .............. Which of the following is an AI language?..............
    1. COBOL
    2. LISP..............
    3. HTML
    4. XML

State True or False

1. Intelligence is defined as the ability to acquire, retrieve, and use knowledge in a meaningful way.
2. In 1950, Alan Turing proposed a test to prove the intelligence of a human.
3. Thinking humanly, acting humanly, thinking rationally, acting rationally are four categories of AI.
4. “The Logic Theorist” developed by Allen Newell and Herbert Simon is considered as the first AI program.
5. Knowledge-based systems make extensive use of knowledge to perform complex tasks.
6. Matrix-based technique is one of the techniques available for knowledge acquisition.
7. FOPL is one of the most widely used representation scheme.
8. Search problems can be categorized into three groups.
9. NLP involves the interpretation, manipulation, or generation of human language by computer.
10. The general architecture of an expert system consists of two components: rule-base and inference engine.

Descriptive Questions

1. Describe various components of AI.
2. Is Turing test sufficient to judge whether a machine is intelligent? Explain.
3. Name the domain areas of AI and explain any four of them.
4. Describe associative networks by giving an example.
5. How NLP is used in developing AI system?
6. What is an expert system? Give its characteristics and limitations.
7. Explain neural networks along with its advantages.
8. Write short notes on:
   1. Breadth-first search
   2. Depth-first search
   3. Hill-climbing search
   4. Knowledge representation

ANSWERS

Fill in the Blanks

1. Nodes, Arcs
2. Hill climbing, Best-first
3. MYCIN
4. Raw, Refined
5. Intelligent
6. Representation
7. Flexible, Powerful
8. Heuristic
9. LISP
10. Facts, Rules, Goals

Multiple-choice Questions

1. (a)
2. (b)
3. (d)
4. (c)
5. (d)
6. (d)
7. (a)
8. (d)
9. (a)
10. (b)

State True or False

1. True
2. False
3. True
4. True
5. True
6. True
7. True
8. False
9. True
10. True