Posts Tagged ‘Artificial Intelligence’
A typical program has three major segments: input, processing and output. So regular programming and Artificial Intelligence programming can be compared in terms of these three segments.
In regular programming, input is a sequence of alphanumeric symbols presented and stored as per some given set of previously stipulated rules and that uses a limited set of communication media such as keyboard, mouse, disc, etc.
In Artificial Intelligence programming the input may be a sight, sound, touch, smell or taste. Sight means one dimensional symbols such as typed text, two dimensional objects or three dimensional scenes. Sound input include spoken language, music, noise made by objects. Touch include temperature, smoothness, resistance to pressure. Smell input include odors emanating from animate and inanimate objects. And taste input include sweet, sour, salty, bitter foodstuffs and chemicals.
In regular programming, processing means manipulation of the stored symbols by a set of previously defined algorithms. In AI programming, processing includes knowledge representation and pattern matching, search, logic, problem solving and learning.
In regular programming, output is a sequence of alphanumeric symbols, may be in a given set of colors, that represents the result of the processing and that is placed on such a medium as a CRT screen, paper, or magnetic disk.
In AI programming, output can be in the form of printed language and synthesized speech, manipulation of physical objects or locomotion i.e., movement in space.
Rules are the popular paradigm for representing knowledge. A rule based expert system is one whose knowledge base contains the domain knowledge coded in the form of rules.
Elements of a rule based expert system
A rule based expert system consists of the following components:
This is a mechanism to support communication between and the system. The user interface may be a simple text-oriented display or a sophisticated, high resolution display. It is determined at the time of designing the system. Nowadays graphical user interfaces are very common for their user-friendliness.
It explains the user about the reasoning process of the system. By keeping track of the rules that are fired, an explanation facility presents a chain of reasoning that led to a certain conclusion. So explanation facility is also called justifier. This feature makes a huge difference between expert systems and other conventional systems. almost all the commercial expert system shells do trace based explanation, that is, explaining the inferencing on a specific input data set. Some systems explain the knowledge base itself, and some explain the control strategy as well.
Working memoryThis is a database used to store collection of facts which will later be used by the rules. More effort may go into the design and implementation of the user interface than in the expert system knowledge base. Working memory is used by the inference engine to get facts and match them against the rules. The facts may be added to the working memory by applying some rules.
Inference EngineAs the name implies the inference engine makes inferences. It decides which rules are satisfied by the facts, prioritizes them, and executes the rule with the highest priority. There are two types of inference: forward chaining and backward chaining. Forward chaining is reasoning from facts to the conclusion while backward chaining is from hypothesis to the facts that support this hypothesis. Whether an inference engine performs forward chining or backward chaining entirely depends on the design which in turn depends on the type of problem. Some of the systems that do forward chaining are OPS5 and CLIPS. EMYCIN one of the most popular systems performs backward chining. Some systems, ART and KEE, for example, offer both the techniques. Forward chaining is best suited for prognosis, monitoring and control. Backward chaining is generally used for diagnostic problems. Inference engine operates in cycles, executing a group of tasks until certain criteria causes that halt the execution. The taks to be done repeatedly are conflict resolution, act, match and check for halt. Multiple rules may be activated and put on the agenda during one cycle.
Inference engine prepares a priotorized list of rules called agenda. The rules in the list must be satisfied by the facts in the working memory. When the inference engine notices a fact that satisfies the pattern in the condition part of the rule then it adds the rule to the agenda. If a rule has mulitple patterns then all of its patterns must be satisfied to get place in the agend. In a condition a>b and b>c, for example, both a>b and b>c must be satisfied. A rule whose patterns are satisfied is said to be activated or instantiated. When there is more than one activated rule in the agenda then the inference engine has to select one rule, based on priority or on other factors, for firing. Rule based expert systems are built using refraction to prevent trivial loops. That is a rule which is fired on a fact will not be fired again and again on the same fact. To implement this feature OPS5 uses a unique identifier called timetag. Then-part of the rule contains actions to be executed when the rule fires. Some of the actions are addition of facts to the working memory, removal of facts from the working memory and printing results. Agenda conflict occurs when different activations have the same priority. Agenda conflict is tackled by strategies such as first come first execute, assigning default priority, and so on.
Knowledge Acquisition Facility
This allows the user to enter knowledge in the system thereby avoiding the need of knowledge engineer explicitly code the knowledge. It is an optional feature on many expert systems. Simple rules can be created using rule induction. In rule based expert systems, knowledge base is also called production memory as rules in the form of if-then are called productions.
Advantages of Rule based Expert Systems
Modular nature: This allows encapsulating knowledge and expansion of the expert system done in a a easy way.
Explanation facilities: Rules make it easy to build explanation facilities. By keeping track of the rules that are fired, an explanation facility can present a chain of reasoning that led to a certain conclusion.
Similarity to the human cognitive process: Newel and Simon have showed that rules are the natural way of modeling how humans solve problems. Rules make it easy to explain the structure of knowledge to the experts.
What is Expert System?
Expert system is an artificial intelligence program that has expert-level knowledge about a particular domain and knows how to use its knowledge to respond properly. Domain refers to the area within which the task is being performed. Ideally the expert systems should substitute a human expert. Edward Feigenbaum of Stanford University has defined expert system as “an intelligent computer program that uses knowledge and inference procedures to solve problems that are difficult enough to require significant human expertise for their solutions.” It is a branch of artificial intelligence introduced by researchers in the Stanford Heuristic Programming Project.
The expert systems is a branch of AI designed to work within a particular domain. As an expert is a person who can solve a problem with the domain knowledge in hands it should be able to solve problems at the level of a human expert. The source of knowledge may come come from a human expert and/or from books, magazines and internet. As knowledge play a key role in the functioning of expert systems they are also known as knowledge-based systems and knowledge-based expert systems. The expert’s knowledge about solving the given specific problems is called knowledge domain of the expert.
Components of Expert Systems
Basic Concept of an Expert System Function
The expert system consists of two major components: knowledge base and inference engine.
Knowledge base contains the domain knowledge which is used by the inference engine to draw conclusions. The inference engine is the generic control mechanism that applies the axiomatic knowledge to the task-specific data to arrive at some conclusion. When a user supplies facts or relevant information of query to the expert system he receives advice or expertise in response. That is given the facts it uses the inference engine which in turn uses the knowledge base to infer the solution.
Characteristics of Expert Systems
High performance: They should perform at the level of a human expert.
Adequate response time: They should have the ability to respond in a reasonable amount of time. Time is crucial especially for real time systems.
Reliability: They must be reliable and should not crash.
Understandable: They should not be a black box instead it should be able explain the steps of the reasoning process. It should justify its conclusions in the same way a human expert explains why he arrived at particular conclusion.
A shell is a special purpose tool designed based on the requirements of particular applications. User should supply the knowledge base to the shell. Example for the shell is EMYCIN (Empty MYCIN) shell. Shell manages the input and output. It processes the information given by the user, relates it to the concepts contained in the knowledge base, and provides solution for a particular problem.
Advantages of Expert Systems
Availability: Expert systems are available easily due to mass production software.
Cheaper: The cost of providing expertise is not expensive.
Reduced danger: They can be used in any risky environments where humans cannot work with.
Permanence: The knowledge will last long indefinitely.
Multiple expertise: It can be designed to have knowledge of many experts.
Explanation: They are capable of explaining in detail the reasoning that led to a conclusion.
Fast response: They can respond at great speed due to the inherent advantages of computers over humans.
Unemotional and response at all times: Unlike humans, they do not get tense, fatigue or panic and work steadily during emergency situations.
What are Frames?
Natural language understanding requires inference i.e., assumptions about what is typically true of the objects or situations under consideration. Such information can be coded in structures known as frames.
Need of frames
Frame is a type of schema used in many AI applications including vision and natural language processing. Frames provide a convenient structure for representing objects that are typical to a stereotypical situations. The situations to represent may be visual scenes, structure of complex physical objects, etc. Frames are also useful for representing commonsense knowledge. As frames allow nodes to have structures they can be regarded as three-dimensional representations of knowledge.
A frame is similar to a record structure and corresponding to the fields and values are slots and slot fillers. Basically it is a group of slots and fillers that defines a stereotypical object. A single frame is not much useful. Frame systems usually have collection of frames connected to each other. Value of an attribute of one frame may be another frame.
A frame for a book is given below.
The above example is simple one but most of the frames are complex. Moreover with filler slots and inheritance provided by frames powerful knowledge representation systems can be built.
Frames can represent either generic or frame. Following is the example for generic frame.
if-added: Procedure ADD_COMPUTER
if-needed: Procedure FIND_SPEED
The fillers may values such as computer in the name slot or a range of values as in types slot. The procedures attached to the slots are called procedural attachments. There are mainly three types of procedural attachments: if-needed, default and if-added. As the name implies if-needed types of procedures will be executed when a filler value is needed. Default value is taken if no other value exists. Defaults are used to represent commonsense knowledge. Commonsense is generally used when no more situation specific knowledge is available.
The if-added type is required if any value is to be added to a slot. In the above example, if a new type of computer is invented ADD_COMPUTER procedure should be executed to add that information. An if-removed type is used to remove a value from the slot.
A semantic net (or semantic network) is a knowledge representation technique used for propositional information. So it is also called a propositional net. Semantic nets convey meaning. They are two dimensional representations of knowledge. Mathematically a semantic net can be defined as a labelled directed graph.
Semantic nets consist of nodes, links (edges) and link labels. In the semantic network diagram, nodes appear as circles or ellipses or rectangles to represent objects such as physical objects, concepts or situations. Links appear as arrows to express the relationships between objects, and link labels specify particular relations. Relationships provide the basic structure for organizing knowledge. The objects and relations involved need not be so concrete. As nodes are associated with other nodes semantic nets are also referred to as associative nets.
In the above figure all the objects are within ovals and connected using labelled arcs. Note that there is a link between Jill and FemalePersons with label MemberOf. Simlarly there is a MemberOf link between Jack and MalePersons and SisterOf link between Jill and Jack. The MemberOf link between Jill and FemalePersons indicates that Jill belongs to the category of female persons.
Unless there is a specific evidence to the contrary, it is assumed that all members of a class (category) will inherit all the properties of their superclasses. So semantic network allows us to perform inheritance reasoning. For example Jill inherits the property of having two legs as she belongs to the category of FemalePersons which in turn belongs to the category of Persons which has a boxed Legs link with value 2. Semantic nets allows multiple inheritance. So an object can belong to more than one category and a category can be a subset of more than one another category.
Semantic network allows a common form of inference known as inverse links. For example we can have a HasSister link which is the inverse of SisterOf link.The inverse links make the job of inference algorithms much easier to answer queries such as who the sister of Jack is. On discovering that HasSister is the inverse of SisterOf the inference algorithm can follow that link HasSister from Jack to Jill and answer the query.
Disadvantage of Semantic Nets
One of the drawbacks of semantic network is that the links between the objects represent only binary relations. For example, the sentence Run(ChennaiExpress, Chennai,Bangalore,Today) cannot be asserted directly.
There is no standard definition of link names.
Advantages of Semantic Nets
Semantic nets have the ability to represent default values for categories. In the above figure Jack has one leg while he is a person and all persons have two legs. So persons have two legs has only default status which can be overridden by a specific value.
They convey some meaning in a transparent manner.
They nets are simple and easy to understand.
They are easy to translate into PROLOG.