All.pdf

Artificial Intelligent Introduction to Artificial Intelligent Dr Ahmed Al-Arashi December 2017 1 11/12/2023 Brief review of AI History ⚫ 1950: Initiation. ⚫ 1955-60: Formation (GPS) ⚫ 1961-70: Development and redirection ⚫ 1971-80: Specialization 2 11/12/2023 Introduction What is Artificial intelligence (AI)? Elaine Rich defined AI as follows: “Artificial Intelligence is the study of how to make computers do things at which, at the moment, people are better” What is AI Aim? To make computers do things which, if they were done by people would be considered intelligent. The question is What is intelligence? 3 11/12/2023 What is intelligence? It could be seen in three human activities: ⚫ Thinking ⚫ Knowledge ⚫ Learning 4 11/12/2023 General Introduction to Artificial Intelligence Sensor What is an Precepts intelligent agent? Environment Action Effectors Any thing that can perceives it’s environment through sensors and acts upon the environment 5 through effectors. 11/12/2023 Examples Agent Sensors Effectors Human Eyes, ears and other Hands, legs, mouth organs and other body parts Robotic Cameras and other Motors sensors Software Bits Bits 6 11/12/2023 Structure of intelligent agent Agent = Architecture + Functions Or Agent = A sort of computer + Programs AI job is to design agent programs. From AI point of view an intelligent agent is a device called architecture, which uses some functions to implement the agent actions (precepts and actions). 7 11/12/2023 Difference between Computer and People Computers are good at: People are better at: ⚫ Numerical computation. ⚫ Understanding. ⚫ Information storage. ⚫ Make decision. ⚫ Text processing. ⚫ Use common sense. ⚫ Communication. 8 11/12/2023 Area of AI research and application ⚫ Expert System ⚫ Natural Language Processing ⚫ Understanding ⚫ Generation ⚫ Speech Recognition ⚫ Vision and Image Processing ⚫ Robotics ⚫ Intelligent Computer Assisted Learning ⚫ Automatic Programming ⚫ Planning and Decision Support ⚫ Design ⚫ Machine Learning 9 11/12/2023 Difference between AI programs and conventional programs Details to compare Con. Programs AI programs Input Sequence of Sight: Text, Image alphanumeric Sound: Language, symbols music,…. Touch: Temp. Smell 10 11/12/2023 Difference between AI programs and conventional programs Details to compare Con. Programs AI programs Processing Step by step Search instruction to Pattern Matching solve the Logic problem Learning 11 11/12/2023 Difference between AI programs and conventional programs Details to compare Con. Programs AI programs Output Sequence of Text alphanumeric Sound symbols. Action Graphics 12 11/12/2023 Artificial Intelligent Problem and Problem Space Dr Ahmed Al-Arashi August 2023 1 11/12/2023 To solve any AI problem we need to: ⚫ Define the problem. ⚫ Analyze the problem. ⚫ Obtain and represent the knowledge. ⚫ Find or choose problem solving technique. ⚫ Apply the problem solving technique. 2 11/12/2023 Problem Definition Converting the problem from typical problem statement to formal representation of the problem suitable for use by computer i.e. specify the problem. Which is stating the following: ⚫ Initial state. ⚫ Goal State ⚫Rules. 3 11/12/2023 Problem Definition Example Water Jug Problem Define the following problem statement We have two jugs 4-gallons and 3-gallons. Neither of them has any measuring marks. It is required to get exactly 2 gallons of water into the 4-gallons jug. How can you do that? 4 11/12/2023 Water Jug Problem Definition Assumption Let: ⚫ (x) Represents number of gallons in the 4-gallons jug. ⚫ (y) Represents number of gallons in the 3-gallons jug. Initial state ⚫ Both jugs are empty i.e. (0,0). Goal state ⚫ 2 gallons of water in the 4-gallon jug i.e. (2,y). 5 11/12/2023 Water Jug Problem Definition (Cont.) Rules (1/2) NO For (x,y) If Then Result Water in 4-gallon Jug less than 4 1 Fill the 4-gallon jug. (4,y) gallons. Water in the 3-gallon jug less than 3 2 Fill the 3-gallon jug. (x,3) gallons There is some water in the 4-gallon Pour some water out of 3 (x-d,y) jug. the 4-gallon jug. There is some water in the 3-gallon Pour some water out of 4 (x,y-d) jug. the 3-gallon jug. There is some water in the 4-gallon Empty the 4-gallon jug on 5 (0,y) jug. the ground. There is some water in the 3-gallon Empty the 3-gallon jug on 6 jug (x,0) the ground 6 11/12/2023 Water Jug Problem Definition (Cont.) Rules (2/2) NO For (x,y) If Then Result There is 4 gallon of water or more in Pour water from the 3-gallon jug 7 both the jugs and there is some water in into the 4-gallon jug until (4,y-(4-x)) the 3-gallon jug the 4-gallon jug is full There is 3 gallon of water or more in Pour water from the 4-gallon 8 both the jugs and there is some water in jug into the 3-gallon jug until (x-(3-y),3) the 4-gallon jug the 3-gallon jug is full There is 4 gallon of water or less in both Pour all the water from the 3- 9 the jugs and there is some water in the (x+y,0) gallon jug into the 4-gallon jug 3-gallon jug There is 3 gallon of water or less in both Pour all the water from the 4- 10 the jugs and there is some water in the (0,x+y) gallon jug into the 3-gallon jug 4 -gallon jug There is no water in the 4-gallon jug Pour the 2 gallons from the 3- 11 and there is 2 gallons of water in the (2,0) gallon jug into the 4-gallon jug 3-gallon jug There is 2 gallons of water in the 4- Empty the 2 gallons in the 4- 12 gallon jug and there is some water in the (0,y) gallon jug on the ground 7 3-gallon jug 11/12/2023 Water Jug Problem Problem solution Sequences of operations to solve the problem may be: Rule Before Appling the rule Before Appling the rule to Gallons in apply Gallons in Gallons in Gallons in 3-gallon jug 4-gallon jug 4-gallon jug 4-gallon jug 0 0 Initial state 0 0 2 0 3 0 3 9 3 0 3 0 2 3 3 3 3 7 4 2 5; 12 4 2 0 2 9; 11 0 2 2 0 8 2 0 Goal state 11/12/2023 Rules preparation Pointes to be taken into consideration ⚫ Rules which lead to problem solution should be considered. ⚫ Special case rules should be avoided. ⚫ Rules lift side should have constrain to limit application to states that will lead to solution. 9 11/12/2023 Problem State Space Represention ⚫ It describes activities in term of it’s component events. ⚫ It has some nodes joined by arrows as shown Step up Step up Step up Bottom 1st Step 2nd Step Top Step down Step down Step down A simple state space representation 10 11/12/2023 Problem Types ⚫ Single state problem There is only one action from starting state to goal stat. ⚫ Multiple state problem Where sequence of actions are needed to reach the goal stat. ⚫ Contingency problem Where a precaution action is added to the actions them selves. ⚫ Exploration problem Where states are discovered by experiments. Such as being lost in unknown city with no map. 11 11/12/2023 Problem component in state space representation ⚫ Initial state It is the state the agent knew it self to be in at the starting. ⚫ Current state It is the state the agent knew it self to be in. ⚫ Goal stat The state which the agent can want to reach to solve the problem. ⚫ State operator Is the possible action available to the agent witch will 12 move the agent from one state to another. 11/12/2023 Problem component in state space representation (Cont.) ⚫ State space If the set of all states reachable from the initial state by any sequence of actions. ⚫ Path It is any sequence of actions leading to form on state to another. ⚫ Goal test Which the agent can apply to a state to determine if it is a goal test. ⚫ Path cost Is a function that assign cost to a path the cost at a path is the sum of costs of all individual actions. 13 11/12/2023 Forms of state space diagrams 1- Graphs Where there is looping. a B C E b c H F e Graph 14 11/12/2023 Forms of state space diagrams (Cont.) 2- Tree Where there is no looping. a A B C b c d D E F G H e f g h l 15 11/12/2023 Converting from graph to tree As Trees are much easier to search, graphs may be converted to trees Using two lists as follows: Waiting be the list for states waiting processing. Done be the list for states, which has been processed. Apply the Conversion Algorithm. 16 11/12/2023 Converting from graph to tree Conversion Algorithm ⚫ Set l = L. ⚫ Set waiting to [initial state , L]. ⚫ Set done to empty = [ ]. ⚫ Do until waiting is empty ⚫ Add 1 to L. ⚫ Take first pair from waiting and call it ( X , Y ). ⚫ If X is the first part of a pair in done then remove pairs from done until ⚫ reaching a pair with one level less than the level of first pair of waiting. ⚫ Else find successors of X and from pairs in the form ( X successor , L ) add them to the beginning of waiting in away such that those with states not appearing in done first and the 17 rest in the some order as in done. 11/12/2023 Graph Conversion Example Convert the graph shown in the figure below to a tree a b c e f 18 11/12/2023 Graph Conversion Example Waiting Done [] [(b,2),(c,2)] [(a,1)] [(c,3),(e,3),(c,2)] [(a,1),(b,2)] [(f,4),(e,3),(c,2)] [(a,1),(b,2),(c,3)] [(e,5),(e,3),(e,2)] [( a , 1 ) , ( b , 2 ) , ( c , 3 ) , ( f , 4 ) ] [ ( f , 6 ), ( c , 6 ), ( e , 3 ), ( c , 2 [ ( a , 1 ) , ( b , 2 ) , ( c , 3 ) , ( f , 4 ), ( e , 5 ) ] break )] tracking (bt) [(c,6),(e,3),(c,2)] [(a,1),(b,2),(c,3),(f,4),(e,5)] path end (pe) [(e,3),(c,2)] [(a,1),(b,2)] [(c,4),(f,3),(c,2)] [(a,1),(b,2),(e,3)] [(f,5),(f,4),(c,2)] [(a,1),(b,2),(e,3)] [(e,5),(f,4),(c,2)] [(a,1),(b,2),(e,3),(c,4),(f,5)] pe [(f,4),(c,2)] [ ( a , 1 ) , ( b , 2 ) , ( e , 3 ) ] bt [(e,5),(c,2)] [( a , 1 ),( b , 2 ), ( e , 3 ), f , 4 ) ] pe [(c,2)] [ ( a , 1 ) ] bt [(f,3)] [(a,1),(c,2)] [(e,4)] [(a,1),(c,2),(f,3)] [(c,5),(f,5)] [(a,1),(c,2),(f,3),(e,4)] [(f,5)] [(a,1),(c,2),(f,3),(e,4)] 19 [] [ ( a , 1 ) , ( c , 2 ) , ( f , 3 ) , ( e , 4 ) ] end 11/12/2023 Artificial Intelligent Search Dr Ahmed Al-Arashi August 2023 1 8/22/2023 Introduction  How an intelligent agent can decide what to do by considering the output of various sequences of actions that it might take.  Consider the simplified rood map for some Yemeni cities Fig. (SR1) 2 8/22/2023 Expert system 1 Introduction Consider the simplified rood map for some Yemeni cities Fig. (SR1) 3 8/22/2023 Introduction How to find the road from Sanaa to Taiz? 4 8/22/2023 Expert system 2 Introduction  Start from initial stat i.e. Sanaa  Expand Sanaa state i.e. find all successors, which are Amran, Mahweet, Mareb, Dahmar and Bajel as shown in Fig. (SR2).  Now which state should be expanded next?  Next step depends on the search strategy the agent will use. 5 8/22/2023 Search Strategy In order to reach to a reasonable solution with in certain time a good search strategy should be adopted. Good search strategy should have the following characteristics:  It should cause motion.  It should be systematic. 6 8/22/2023 Expert system 3 Search Search is a step by step method to solve a search problem in a specified search space. In other words, search is a class of techniques for systematically finding or constructing solutions to problems. Example 1. Generate a possible solution. 2. Test the solution. 3. If solution found THEN done ELSE return to step 1. 7 8/22/2023 Search thru a Problem Space / State Space Input: – Set of states – Operators – Start state – Goal state Output: – Path: start  a state satisfying goal test – [May require shortest path] Expert system 4 Search evaluation criteria  Competence: is the strategy guaranteed to obtain a solution if there is one?  Time complexity: how long does it take to find a solution?  Space complexity: how much memory does it need to find a solution?  Optimality: does the strategy find highest quality solution when there are several different solutions? 9 8/22/2023 Type of Search Uninformed/Blind Search This type of search takes all nodes of tree in a specific order until it reaches to goal. The order can be in the breath and the strategy will be called breadth–first–search, or strategy will be called depth first search Informed/Heuristic Search It uses additional information to guide the search by using a function to estimate how close a state is to the goal stat. 10 8/22/2023 Expert system 5 Depth-firset  When a state is examined all its children and descendants are examined before any siblings.  It goes deeper until a dead end is hit or goal is found.  If dead end is hit the most recently created state from which alternative moves are available are revisited and new state are created. Progress to search is shown in the Fig 11 8/22/2023 Depth-firset Procedure to implement depth first search using Two lists waiting end done  Waiting is the list containing the initial state and done is empty  Repeat until waiting is empty or goal state is on the end of done.  Remove the first state from waiting and put it at the end of done, find its successors and put it the beginning of waiting Advantage of depth first search  Requires less memory since only nodes on current bath are stored.  By chance it might find solution with out searching much of the state space 12 8/22/2023 Expert system 6 Depth firset 13 8/22/2023 Breadth firset  The root is expanded first.  Then all the nodes generated by the root are expanded next.  Then their successors. The Figure to the right shows the progress at the search. 14 8/22/2023 Expert system 7 Breadth first Procedure to implement breadth first search using two waiting and done.  Waiting containing the initial state and done is empty.  Repeat until waiting is empty or goal state is on the end of done.  Remove from waiting and put it at the end of done, find its successors and put it the end of waiting. Advantage of breadth first search  It with not get trapped at end of state space path. 15 8/22/2023 Breadth First Search 16 8/22/2023 Expert system 8 Looking to some search problem 1- Traveling Salesman Problem A salesman has to visit N cities to sale his products. How can he plan his trip so that all cities are visited.  Optimal solution is costly to fine as no of solutions for blind search N!  Acceptable solution may be found applying the following  Select any city to start from  Visit the nearest city to the current city which has not been visited  Repeat 2 until all city are visited. 17 8/22/2023 Looking to some search problem 2- Puzzle Problem In an eight digit 9 empty tiles puzzle has certain initial stat and it is required to reach certain goal stat. how can it be done?  Optimal solution can take 9! = 362880  Different Arrangements may be trailed.  Search can be improved using the following  Checking number of tails in the wrong position  Checking the sum of distances of the tile from their goal position. 18 8/22/2023 Expert system 9 Looking to some search problem 3- Book finding problem If a book is lost in in a house with N rooms. How normally people search the house to find the lost book.  Blind search for a lost book in a house with N rooms may take long time (start from the first room moving in a straight line forth and back).  Search may be improved using the following.  Select only rooms when reading has been done  Start with the places where most of the reading has been done. 19 8/22/2023 Looking to some search problem Findings From the three previous problems, It could be concluded that:  Most of the people would use additional information to reduce search space.  It does not guarantee the solution but it works.  Exact solution is not always needed but an acceptable one will be ok.  It is faster than blind/unguided search.  It leads to deeper understanding of the problem. 20 8/22/2023 Expert system 10 Heuristic Search  It is the search strategy that use any sort of information to guide the search.  It is also know as guided search, directed search or informed search.  Knowledge about the knowledge, when available, is used to guide the search.  Heuristic Search is much faster than blind search.  In this type of search exact solution is not always guaranteed. 21 8/22/2023 Heuristic Search  There are number Heuristic Search methods, we will look at the following ones: (I) Hill climbing search (a) Simple hill climbing search (b) Steepest-ascent Hill climbing (II) Best first search method  Any Heuristic Search would need an algorithm that have two “Functions” 1- Generate: It Generates a solution 2- Evaluate: It Evaluates the solution 22 8/22/2023 Expert system 11 (I) Hill climbing search It is a depth first search method with evaluation function that can decide which direction to move in the search space we can look at two forms of hill climbing search method Which are: (a) Simple hill climbing search In this search method the first better successor is considered. (b) Steepest-ascent Hill climbing In this method all the successors are checked before making a move the most promising one is select. 23 8/22/2023 (a) Simple hill climbing search Algorithm Algorithm  Evaluate initial state if goal stop, otherwise make the initial state the current state.  Repeat until all nodes one examined or solution is found  Select a successor that has not been visited.  Evaluate the successor – If it is a goal state stop. – If not goal state but better then current ,then make it current state. – If not goal stat end not better then current state, then repeat. 24 8/22/2023 Expert system 12 (b) Steepest-ascent Hill climbing Algorithm 1-Evaluate the initial stat. If a goal state stop. Else make it the current state. 2-Repeat until solution is fond or all nodes are examined. 2. 1. generated successors of the current state and select a successor. Make it temporary state. 2.2.evaluate all other successors of the current state one by one  if the successor is a goal state stop.  if not the goal state then compare it with the temp successor  If better then temp. successor make it temp successor and repeat 2.2  If not better leave it and repeat 2.2 2.3. make temp. Successor current state. 25 8/22/2023 (II) Best first search method In best first search use the available knowledge to direct the search. it differs from hill climbing search in that it is not limited to the children or a node but the most promising successor all the nodes in the waiting list. Algorithm 1-Evaluate initial state , if it is a goal state stop. Otherwise put it in waiting list 2-Repeat until solution found or all nodes have been examined.  Assess on the states in waiting and remove the most promising , generate it is successors and put then in waiting 26 8/22/2023 Expert system 13 Expert System Dr. Ahmed Al-Arashi. Introduction ⚫ Early 80s of 20th century was the years of AI specialization and success where the knowledge based systems were created and some expert systems were developed such as MYCIN that address medical diagnosis problems and DENDRAL that analyses mass spectrographic nuclear magnetic resonance. ⚫ Expert systems are firmly at the application end of the AI. The other branches of AI are concerned with common intelligent tasks such as interpreting scenes and understanding languages. ⚫ Expert systems can also undertake tasks such as process control. Introduction (cont.) To find out what is the expert system lets first find out who is the expert? He is a person who has some of the following characteristics ⚫ Special knowledge in a given area, which exceeds our own in the area. ⚫ Specialized training in that area. ⚫ Work experience in the area. ⚫ Ability to give reliable advice. ⚫ May has more knowledge than any one else. ⚫ May has good knowledge out side his area of expertise. Expert System Definition ⚫ Expert system is a program that simulates the performance of a human expert in a specific narrow field. ⚫ The word expert may mislead, as we expect the performance of the expert to be perfect. Is there a doctor who has never misdiagnosed? ⚫ Hence Expert System may be better called a Knowledge Based System ⚫ The expert system may be seen as an intelligent computer programme that uses knowledge and inference procedures to solve problems that would normally require human expertise to arrive to a solution. Expert System Definition ⚫ Expert system is a program that simulates the performance of a human expert in a specific narrow field. ⚫ The word expert may mislead, as we expect the performance of the expert to be perfect. Is there a doctor who has never misdiagnosed? ⚫ Hence Expert System may be better called a Knowledge Based System ⚫ The expert system may be seen as an intelligent computer programme that uses knowledge and inference procedures to solve problems that would normally require human expertise to arrive to a solution. Expert System Definition (cont.) An expert system is a computer program that simulates the judgment and behavior of a human or 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 that is described to the program. Process of Building Expert System 1- Project selection: Selecting the project and carrying out a feasibility study to find out if the problem can be solved by the expert system technique. The following questions are answered to find out wither it is preferable to build expert system or not ⚫ Is the knowledge acquired by experience over long time? ⚫ Are the experts the only people who can really understand the decision factors involved? ⚫ Is more consistence decision making process needed? ⚫ Does the task require expertise for the solution? Does non expert perform poorly? ⚫ Is there a shortage of expertise? ⚫ Is the problem solution depends on common sense ⚫ Is the domain well defined? ⚫ Is the domain stable? ⚫ Does the domain rely more on heuristics than algorithms? ⚫ Does the expert deals more with symbols than numbers? Process of Building Expert System 2- User identification Who will use the programme and what is his knowledge. 3- Knowledge election: Extracting the knowledge needed to solve the problem. 4- Knowledge Analysis: Choosing the most suitable way of representing the knowledge from those available (production rules, frames, semantic nets, etc.). More details are given in later section. 5- Choice of tools: Choosing the suitable tool for implementing the expert system and also choosing the hardware. 6- Coding the knowledge: Converting the knowledge from normal English to the selected programming language. Process of Building Expert System 7- Validation of the system: Testing the developed system and comparing the results with other results obtained by other means. 8- Maintenance procedure design: A policy of how future changes to the system are to be dealt with. 9- Evaluation of the system: Testing the system by the users and see what improvements may be needed. 10- Maintenance: While the system is in use many small but important deficiencies are discovered which need to be dealt with in according with pre- set procedures. Characteristics of Expert Systems An expert system stores expert knowledge in certain subject areas, and solves problems by drawing logical conclusions. Expert systems are used in those cases where specialized knowledge and experience are available and where conventional programming techniques cannot be used or if used may be uneconomic. From the point of view of the user, the expert system is a computer programme to be used in the same way as any other programme, but from the point of view of the designers and implementers an expert system is quite different from conventional computer programme. Differences Between Expert systems and Conventional Programs Some of the important differences are listed below: ⚫ Expert systems incorporate a symbolically structured knowledge base, which contains the knowledge it needs, while the conventional programmes work with numerically addressed data bases. ⚫ Searching for a solution, in expert systems, is "heuristic". A heuristic solution is a method or set of rules for solving a problem without showing exactly how the computer is to perform its task. In contrast the conventional programmes solution is algorithmic, i.e. step by step procedures that guarantee that the right conclusion will be reached when the correct data have been entered. ⚫ In the conventional programmes the data and the control are mixed and cannot be separated. This fact makes the conventional programmes hard to amend or modify. In the expert systems the modification is much easier because the knowledge in the programme is coded using special language and kept separate from the control (knowledge which guides the search). ⚫ Expert systems can handle uncertain knowledge and solve problems using approximate methods, which are not guaranteed to succeed with algorithmic programmes. Differences Between Expert systems and Conventional Programs According to the British computer committee of the specialist group on expert systems (BCS) expert systems require the following : ⚫ An expert system contains knowledge. ⚫ The programme offers intelligent advice. ⚫ The system should be able to explain its line of reasoning. ⚫ Expert systems are typically rule based. Advantages of Expert Systems ⚫ Expert systems can offer a very good assistance for all its users, so user can avoid complex tasks. ⚫ The knowledge stored in the expert system is permanent and will not be lost. ⚫ The cost of the expert system is much cheaper than the human expert. Once the expert system is developed new experts can be acquired by simply copying the programme. ⚫ The development of the expert system extracts the expert knowledge and formalises the knowledge. It also helps in exploring the reasoning process. ⚫ The expert system is available for use at all times, unlike the human expert who needs to eat, relax and sleep. ⚫ Planning using expert system can be more complete and consistent. ⚫ The information is contained in the knowledge base in the form of rules, hence it is very convenient to add, remove or modify the knowledge base. Disadvantages of Expert Systems ⚫ As expert systems have some advantages, they also have disadvantages. Some of them are listed below: ⚫ The expert system cannot adopt to changes unless it is told to do so. ⚫ Human experts, sometimes apply some global or commonsense knowledge, whilst the expert system can only apply the specific domain knowledge. ⚫ Human experts can formulate new, more efficient, algorithms to apply to existing problems. ⚫ For the expert system to remain useful it needs to be constantly maintained by an expert. Areas of Expert Systems Problem area Problem domain Example Interpretation Infers situation description from observation Speech understanding and signal interpretation Prediction Infers likely consequences from given information Weather forecasting and traffic prediction Diagnosis Infer system characteristics from systems Medical diagnosis Design Purpose configuration under some constraint Electric circuit design and building structural design Control Governing the overall behaviour of a system Production process control, air traffic control and mission control Areas of Expert Systems (cont.) ⚫ Each area of application has to be studied and the main characteristic of that area should be known. ⚫ As example lets take the design problem, it is generally to develop configurations of objects satisfying groups of constraints. ⚫ The main goal of the design can be broken down into three sub goals, to propose a design, criticise it and modify it. ⚫ Each sub goal may be broken farther, if required, into smaller sub goals depending on the type of the design problem under consideration. ⚫ Selection and connection of the components is an important step in the design process. ⚫ When a design is developed it is usually analysed to ensure that the proposed design satisfies the constraints. ⚫ From the results of the analysis only components which do not meet the specifications are reconsidered. Areas of Expert Systems (cont.) The problem of design can be defined by identifying the goal, known and constrains. Design problem can be solved by taking number of actions such propose, criticise, modify and present. Each can be divided farther as shown below. Problem Definition ⚫ Goal – To produce a design that meets a set of constraints and specifications. ⚫ Known – Set of specifications regarding the system required. – Standard component specifications. – Possible relations between the components. ⚫ Constraints – For each design problem, there are some constraints that must be satisfied. Areas of Expert Systems (cont.) Design Process (Actions) Propose Suggest overall design. Suggest relation between the components. Select components properties and details. Criticise Prepare data for analysis. Analyse and test the primary design. Modify Check the analytical results. Update the design if necessary. Present Present the design details. The above design processes may vary according to the design problem. However, they can be used as a general guide for several design problems such as electrical distribution system design. Components of Expert Systems Fundamental components of an expert system are: Knowledge base Inference Engine User interface Components of Expert Systems Knowledge base ⚫ The knowledge base of an expert system contains high quality knowledge about a specific problem domain organised as facts or rules or any other representation. ⚫ Facts represent one single instance of either a property of an object or a relation between objects. Rules are properties or relations known to be true when some set of other relations is known. Facts and rules and other knowledge representation Components of Expert Systems Inference Engine ⚫ The inference engine is that part of the expert system that simulate the problem solving strategy of the human expert. It represents the logical unit by means which conclusions are drawn. The function of the inference engine includes the following: ⚫ To determine which action is to be executed between the individual parts of the expert system. ⚫ To determine how and when rules will be processed. ⚫ To control the dialog with the user. ⚫ There are two inference strategies. Components of Expert Systems User interface This is the means by which the user communicates with the expert system, and it is responsible for how the expert system interacts with the user. The user interface, which is a set of programmes that asks questions and accepts replies, plays a very important rule in the success of the expert system. It presents the questions and provides explanations and conclusions to the user. The questions and explanation must be understandable and the results must be in a form appropriate for the user. Sometimes the user may not be an expert in the system's domain and this fact must be noted at the time of setting up this part of the expert system. Building Components of Expert Systems Knowledge base This starts from knowledge extracting, analysis and then the most appropriate method of representation is sleeted. Inference Engine Depending on the type knowledge and available information about the problem domain a suitable inference strategy is selected and then designed and implemented. User interface The most effective user interface is selected based on the how and what details need to be communicated with the users. Various expert systems building tools are available and which offer of user inference methods. Next lectures will discuss the above topics in more details Knowledge and Knowledge Representation Dr. Ahmed Al-Arashi. Knowledge Engineering Knowledge engineering is a general term for the processes involved in extracting knowledge and building expert systems. This involves: Planning. Knowledge acquisition, System building, System installation. System maintenance. Knowledge Classification Knowledge can be classified as follows ⚫ Structural knowledge Knowledge about the domain it self such as knowing that meningitis is an infection which could be a cute or chronic. ⚫ Supporting knowledge Knowledge used to help understanding the structural knowledge. ⚫ 3- Meta knowledge Knowledge about the knowledge Knowledge Acquisition Sources of knowledge: ⚫ Documents: textbooks, journal articles, technical reports, case histories, etc. This will almost never be sufficient to provide the knowledge base for a real-world expert system. ⚫ Human experts. Knowledge Elicitation The most important branch of knowledge acquisition is knowledge elicitation (Obtaining knowledge from a human expert (or human experts) for use in an expert system). Knowledge elicitation is difficult. This is the principle reason why expert systems have not become more widespread - the knowledge elicitation is a bottleneck. It is necessary to find out what the expert(s) know, and how they use their knowledge. Knowledge Representation Knowledge representation is the technique and processes by which the knowledge extracted about a particular domain is translated into a useful form for expert system application. Forms of knowledge representation includes rules, frames, semantic networks and conceptual graphs. Good Knowledge Representation ⚫ Representational adequacy: The ability to represent all kind of knowledge that are needed in the domain. ⚫ Representational efficiency: It should allow efficient acquisition. ⚫ Inferential adequacy: It should be possible to use the knowledge any way that may be appropriate. ⚫ Inferential efficiency: Should be used rapidly. Knowledge Representation Schemes 1- Rules A rule is a conclusion that is known to be true if one or more condition or fact are found to be true. Production rules are the simplest knowledge representation and the most widely used method. Knowledge Representation Schemes (Rules) A rule is a conclusion that is known to be true if one or more condition or fact are found to be true. Production rules are the simplest knowledge representation and the most widely used method. Rules take the general form: IF < conditions > THEN < actions > The IF part can contain number of conditions and facts. A fact can represent a relation between objects or a property of an object. Knowledge Representation Schemes (Rules) For example the idea that a person will buy a car if the car is for sale and the person likes that car can be represented as: IF - person likes a car and - the car is for sale THEN - the person will buy the car When the two conditions of the rule are true the rule is said to be fired and the conclusion is drawn. Knowledge Representation Schemes (cont.) 2 - Semantic networks This is a diagrammatic representation of knowledge. The items are represented as nodes and they are connected by arcs labelled with the particular relation linking the two nodes. Knowledge Representation Schemes (Semantic networks) Simple semantic network looks like the figure below: Knowledge Representation Schemes (cont.) 3 - Frames A frame represents an object or situation by describing the collection of attributes that it possesses. It does this by listing all the attributes of a typical case and by providing a slot for each. Knowledge Representation Schemes (Frames) A frame structure can be as shown below is_a: bird colour: value set: green red and blue white default: green weight:from 2 lb to 6 lb origin: value set: India Africa Latin America default: India Inference Strategies Dr. Ahmed Al-Arashi. Inference Strategies ⚫ Drawing conclusions from fulfilled conditions is known as an inference. ⚫ In other words inference is the act of inferring new conclusion from a body of knowledge. ⚫ A series of inferences is inference chain. ⚫ There are two methods of inference : – Forward chaining (forward reasoning). – Backward chaining (backward reasoning). Forward Chaining ⚫ It is also known as data driven because it starts from data and infers conclusions. ⚫ To make this idea clear, assume that we have an expert system which has the following rules in its knowledge base: – Rule 1: IF A person age is less than 30 years. THEN Person is young. – Rule 2: IF Person worked more than 3 years in a job. THEN Person has experience. – Rule 3: IF A person is young and, The person has experience. Then The person has priority to get the job. Forward Chaining Assume that: A 25 years old person worked for 5 years in certain job wants to find out whether he can get a job or not. Entering these facts to the data base of the the expert system the inference engine will starts to test the rules starting from rule 1 downward as follows: Rule no. 1 will be fired (applied) and the conclusion that the person is young is drawn and added to the data base. Then rule no. 2 will be fired and the conclusion of that rule, that the person has experience, is added to the data base. When the rules are tested for the third time the only rule which will be fired is rule no. 3 and it will be concluded that the person has priority to get the job. Forward Chaining It should be noted that the practical expert system may include hundreds or even thousands of rules in its knowledge base. This may result in a large number of rules being fired which have no relation to the final conclusion that we want to reach. Due to this deficiency forward chaining inference is not recommended for expert systems with a large knowledge base. Backward Chaining In this method inference starts with the desired conclusion that we want to prove so this inference strategy is called goal driven reasoning. To illustrate how this strategy works consider the knowledge base given in the previous slide for Forward Chaining. – Rule 1: IF A person age is less than 30 years. THEN Person is young. – Rule 2: IF Person worked more than 3 years in a job. THEN Person has experience. – Rule 3: IF A person is young and, The person has experience. Then The person has priority to get the job. With the same information (A 25 years old person worked for 5 years in certain job) Lets try to see whether this person can get the job or not. In other words the goal is to find if the person has priority to get the job. Backward Chaining To prove this the inference engine takes the conclusion of rule no. 3 and tries to prove it. This needs to prove that Sub goal 1- Person is young Conclusion of Rule no. 1 Sub goal 2- The person has experience Conclusion of Rule no. 2 The inference engine will try to prove that both sub goal 1 and 2 of rule no. 3 are true. It will start with trying to find out if "the person is young" , to prove this the backward mechanism tries to prove that conclusion of rule no. 1 is true which will make the rule fired as the information in the database confirms that the person is “25 years old” Now it will try to find out if " Person has experience " , by trying to prove that conclusion of rule no.2 is true which will make rule no. 2 fired as the information in the database confirms that “person worked for 5 years in certain job“. Inference mechanizem will back track to rule no. 3 with both sub goals proven to be true and rule no. 3 is fired and the conclusion “The person has priority to get the job.” is found to be true. The advantage of this method is that only the rules that related to the desired conclusion are tested which makes this inference strategy more effective particularly if there are many rules. Expert Systems Building Tools Dr. Ahmed Al-Arashi. Expert Systems Building Tools Expert systems can be built using one of the following: ⚫ High level languages. ⚫ Programming environment. ⚫ Expert system shells Expert Systems Building Tools High level languages ⚫ It include BASIC, FORTRAN and C, but expert systems are commonly built using the artificial intelligence programming languages such as LISP (LISt Processing) and PROLOG (PROgraming in LOGic). ⚫ The decision about whether to use PROLOG or LISP depends on: – The hardware. – The knowledge representation scheme, whether rules or frames or any other scheme. – The inference strategy suitable for solving the problem under consideration. ⚫ PROLOG is a good choice if the problem is more goal driven than data driven and if the knowledge is to be represented as rules and frames. While LISP is better if the problem is data driven and if a complex frame based knowledge representation is required. ⚫ PROLOG has the following advantages over LISP: – Less expensive. – Easier to learn. – PROLOG saves time for the programmer since it has a built in backward chaining facility. Expert Systems Building Tools Programming environments ⚫ It provide some ready functions in LISP or PROLOG or any other programming language. A programming environment offers different knowledge representation methods and backward and forward inference strategies. Using a programming environment like KEE and ART may help developing a large and complex system, but the drawback of this system is that they are very expensive. Expert system shells ⚫ The shells are generated by taking an expert system and generalising it e.g. EMYCIN generated from MYCIN. There are many expert systems shells but the problem with them is that each one of them is only suitable to construct a system that addresses problems similar to the original expert system. Criteria for Tool Selection 1-Fit of the tool to the problem knowledge representation method and inference method. – Rule- based system – Form based system – Hybrid system – (Forward, backward inference method), or hybrid 2. Effectiveness of the developer interface – Documentation, on line help, tutorials – Knowledge entry and command function – Editor – Menus – Visualization of knowledge structure – Uncertainty – handling Criteria for Tool Selection (cont.) 3. Effectiveness and friendliness of the user interface – User response format (answers tuber) answer taken as – Typed text – Box – Lists – Mouse use, and menus, windows – Menus creation – Sound – Reply to the user – Graphic handling – Display visual images 4. Integration capability with other languages and databases 5. Costs Notes on Expert Systems Prepared by Dr. A Al-Arashi April 2018 1 © Dr.A Al-Arashi 2018 1.1 Introduction This notes introduces the concept of expert systems briefly. It is not intended to cover all the details of the expert system technique, but to offer a helpful introduction to this programming technique. The history of the expert system and it's relation with artificial intelligence (AI) is reviewed in the beginning of this notes whilst the rest of the notes focus on the expert systems components, advantages and disadvantages, areas of applications and the different tools used to build an expert system. 1.2 Artificial intelligence and expert systems Computers are much faster than men in handling very complicated numerical calculation as well as processing large amounts of text. Researchers, who study the application of computers, have always been trying to use the computer for more than a communication device and for more than high speed calculating machines. They wanted this electronic machine to behave intelligently. Artificial intelligence is the study of how to make computers do things at which, at the moment, people are better. Artificial intelligence's main aim, very broadly, is to make computers do things which, if they were done by people, would be considered intelligent. The initiation of artificial intelligence research goes back to the 1950's. 1955-1960 were the formation years and the years 1961-1970 were the development and redirection years. Researchers concentrated on the representation of the knowledge rather than the way of searching the knowledge. The researchers realised that the intelligence lies in the ability to hold large amount of knowledge about a problem in a good structured way such that it can be applied to new problems. 1971-1980 were the years of specialization and success where the knowledge based systems were created and some expert systems were developed such as MYCIN that address medical diagnosis problems and DENDRAL that analyses mass spectrographic nuclear magnetic resonance. Until 1980 most of the artificial intelligence work was academic. From the year 1981 onward the AI attracts the commercial and governmental interests and much of the interest was in the expert system. This results in taking the AI from the research to the applications and the generation of more complex expert systems. Expert systems are firmly at the application end of the artificial intelligence. The other branches of AI are concerned with common intelligent tasks such as interpreting scenes and understanding languages. Expert systems can also undertake tasks such as process control. To find out what is the expert system lets first find out who is the expert? He is a person who has some of the following characteristics  Special knowledge in a given area, which exceeds our own in the area.  Specialized training in that area.  Work experience in the area.  Ability to give reliable advice.  May has more knowledge than any one else.  May has good knowledge out side his area of expertise. Then the Expert system is a program that simulates the performance of a human expert in a specific narrow field. The word expert may mislead, as we expect the performance of the expert to be perfect. Is there a doctor who has never misdiagnosed? Hence Expert System may be better called a Knowledge Based System The expert system may be seen as an intelligent computer programme that uses knowledge and 2 © Dr.A Al-Arashi 2018 inference procedures to solve problems that would normally require human expertise to arrive to a solution. 1.2.1 Process of building an expert system The use of expert systems in solving power system problems goes through several steps. The most important steps are described briefly below: 1) Project selection: Selecting the project and carrying out a feasibility study to find out if the problem can be solved by the expert system technique. The following questions are answered to find out wither it is preferable to build expert system or not  Is the knowledge acquired by experience over long time?  Are the experts the only people who can really understand the decision factors involved?  Is more consistence decision making process needed?  Does the task require expertise for the solution? Does non expert perform poorly?  Is there a shortage of expertise?  Is the problem solution depends on common sense  Is the domain well defined?  Is the domain stable?  Does the domain rely more on heuristics than algorithms?  Does the expert deals more with symbols than numbers? 2) User identification: Who will use the programme and what is his knowledge. 3) Knowledge election: Extracting the knowledge needed to solve the problem. 4) Knowledge Analysis: Choosing the most suitable way of representing the knowledge from those available (production rules, frames, semantic nets, etc.). More details are given in later section. 5) Choice of tools: Choosing the suitable tool for implementing the expert system and also choosing the hardware. 6) Coding the knowledge: Converting the knowledge from normal English to the selected programming language. 7) Validation of the system: Testing the developed system and comparing the results with other results obtained by other means. 8) Maintenance procedure design: A policy of how future changes to the system are to be dealt with. 9) Evaluation of the system: Testing the system by the users and see what improvements may be needed. 10) Maintenance: While the system is in use many small but important deficiencies are discovered which need to be dealt with in according with pre-set procedures. 1.3 Characteristics of expert systems An expert system stores expert knowledge in certain subject areas, and solves problems by drawing logical conclusions. Expert systems are used in those cases where specialized knowledge and experience are available and where conventional programming techniques cannot be used or if used may be uneconomic. From the point of view of the user, the expert system is a computer programme to be used in the same way as any other programme, but from the point of view of the designers and implementers an expert system is quite different from conventional computer programme. Some of the important differences are listed below:  Expert systems incorporate a symbolically structured knowledge base, which contains the knowledge it needs, while the conventional programmes work with numerically addressed data bases. 3 © Dr.A Al-Arashi 2018  Searching for a solution, in expert systems, is "heuristic". A heuristic solution is a method or set of rules for solving a problem without showing exactly how the computer is to perform its task. In contrast the conventional programmes solution is algorithmic, i.e. step by step procedures that guarantee that the right conclusion will be reached when the correct data have been entered.  In the conventional programmes the data and the control are mixed and cannot be separated. This fact makes the conventional programmes hard to amend or modify. In the expert systems the modification is much easier because the knowledge in the programme is coded using special language and kept separate from the control (knowledge which guides the search).  Expert systems can handle uncertain knowledge and solve problems using approximate methods, which are not guaranteed to succeed with algorithmic programmes. According to the British computer committee of the specialist group on expert systems (BCS) expert systems require the following :  An expert system contains knowledge.  The programme offers intelligent advice.  The system should be able to explain its line of reasoning.  Expert systems are typically rule based. 1.4 Advantages and disadvantages of expert systems Much literature has reviewed the advantages and the disadvantages of the expert systems in detail such as and. Some of the advantages and the disadvantages are given below: Advantages Some of the expert systems advantages are: 1) Expert systems can offer a very good assistance for all its users, so user can avoid complex tasks. 2) The knowledge stored in the expert system is permanent and will not be lost. 3) The cost of the expert system is much cheaper than the human expert. Once the expert system is developed new experts can be acquired by simply copying the programme. 4) The development of the expert system extracts the expert knowledge and formalises the knowledge. It also helps in exploring the reasoning process. 5) The expert system is available for use at all times, unlike the human expert who needs to eat, relax and sleep. 6) Planning using expert system can be more complete and consistent. 7) The information is contained in the knowledge base in the form of rules, hence it is very convenient to add, remove or modify the knowledge base. Disadvantages As expert systems have some advantages, they also have disadvantages. Some of them are listed below: 1) The expert system cannot adopt to changes unless it is told to do so. 2) Human experts, sometimes apply some global or commonsense knowledge, whilst the expert system can only apply the specific domain knowledge. 3) Human experts can formulate new, more efficient, algorithms to apply to existing problems. 4) For the expert system to remain useful it needs to be constantly maintained by an expert. 4 © Dr.A Al-Arashi 2018 1.5 Type of problems addressed by expert systems Expert systems can addresses a variety of problems Table 1.1 show some of the areas of which the expert system technique can be used. Problem area Problem domain Example Interpretation Infers situation description from Speech understanding and signal observation interpretation Prediction Infers likely consequences from Weather forecasting and traffic given information prediction Diagnosis Infer system characteristics from Medical diagnosis systems Design Purpose configuration under Electric circuit design and some constraint building structural design Control Governing the overall behaviour Air traffic control and mission of a system control Table 1.1 different types of applications of the knowledge based systems Each area of application has to be studied and the main characteristic of that area should be known. As example lets take the design problem, it is generally to develop configurations of objects satisfying groups of constraints. The main goal of the design can be broken down into three sub-goals, to propose a design, criticise it and modify it. Each sub-goal may be broken farther, if required, into smaller sub-goal depending on the type of the design problem under consideration. Selection and connection of the components is an important step in the design process. When a design is developed it is usually analysed to ensure that the proposed design satisfies the constraints. From the results of the analysis only components which do not meet the specifications are reconsidered. The process of the design can be summarised as follow: Goal To produce a design that meets a set of constraints and specifications. Known  Set of specifications regarding the system required.  Standard component specifications.  Possible relations between the components. Constraints  For each design problem, there are some constraints that must be satisfied. Actions  Propose * Suggest overall design. * Suggest relation between the components. 5 © Dr.A Al-Arashi 2018 * Select components properties and details.  Criticise * Prepare data for analysis. * Analyse and test the primary design.  Modify * Check the analytical results. * Update the design if necessary.  Present * Present the design details. The above design processes may vary according to the design problem. However, they can be used as a general guide for several design problems such as electrical distribution system design. 1.6 Components of expert systems The fundamental components of an expert system are:  Knowledge base  Inference Engine  User interface Figure 1.1 shows the basic structure of an expert system. Working memory User interface Inference engine Knowledge base Rules Facts Figure 1.1 components of an expert system Expert system components are briefly discussed below. Knowledge base The knowledge base of an expert system contains high quality knowledge about a specific problem domain organised as facts or rules or any other representation. Facts represent one single instance of either a property of an object or a relation between objects. Rules are properties or relations known to be true when some set of other relations is known. Facts and rules and other knowledge representation schemes are discussed in section 1.7. Inference Engine The inference engine is that part of the expert system that simulate the problem solving strategy of the human expert. It represents the logical unit by means which conclusions are drawn. The function of the inference engine includes the following: 6 © Dr.A Al-Arashi 2018 1. To determine which action is to be executed between the individual parts of the expert system. 2. To determine how and when rules will be processed. 3. To control the dialog with the user. There are two inference strategies, which are described in more detail in section 1.8. User interface This is the means by which the user communicates with the expert system, and it is responsible for how the expert system interacts with the user. The user interface, which is a set of programmes that asks questions and accepts replies, plays a very important rule in the success of the expert system. It presents the questions and provides explanations and conclusions to the user. The questions and explanation must be understandable and the results must be in a form appropriate for the user. Sometimes the user may not be an expert in the system's domain and this fact must be noted at the time of setting up this part of the expert system. 1.7 Knowledge and knowledge representation schemes 1.7.1 Type of knowledge Knowledge can be classified as follows 1- Structural knowledge Knowledge about the domain it self such as knowing that meningitis in an infection which could be a cute or chronic 2- Support knowledge Knowledge used to help understanding the structural knowledge is known as supporting knowledge. e.g. 3- Meta knowledge Knowledge about the knowledge 1.7.2 Knowledge representation Good knowledge representation should have the following characteristics: Representational adequacy: The ability to represent all kind of knowledge that are needed in the domain Representational efficiency: It should allow efficient acquisition Inferential adequacy: It should be possible to use the knowledge any way that may be appropriate Inferential efficiency: Ability to be used rapidly However, before thinking about how to represent the knowledge in an expert system, the knowledge is selected and recorded in a suitable form for understanding and examining. The next step before coding the knowledge is to select the most appropriate form of knowledge 7 © Dr.A Al-Arashi 2018 representation. A number of different representation techniques can be used in developing an expert system. Three commonly used knowledge representation schemes are : 1. Production rules 2. Semantic networks 3. Frames 1.7.2.1 Production rules A rule is a conclusion that is known to be true if one or more condition or fact are found to be true. Production rules are the simplest knowledge representation and the most widely used method. Rules take the general form: IF < conditions > THEN < actions > The IF part can contain number of conditions and facts. A fact may represent a relation between objects or a property of an object for example joins(roads,cities) expresses the relation between roads and cities, the sentence in natural language is : roads join cities Facts can also express a property of an object for example cat(cindy) in natural language the sentence is Cindy is a cat For example the idea that a person can buy a car if the car is for sale and the person likes that car can be represented as: IF - person likes a car and - the car is for sale THEN - the person can buy the car When the two conditions of the rule are true the rule is said to be fired and the conclusion is drawn. 1.7.2.2 Semantic networks This is diagrammatic representation of knowledge. The items are represented as nodes and they are connected by arcs labelled with the particular relation linking the two nodes. Figure 1.2 shows a simple semantic network. 8 © Dr.A Al-Arashi 2018 Has_prop No of sides closed quadrillatoral 4 AKO parallelgram AKO Has_prop opposit sides rectangle equal AKO Has_prop = Has property Has_prop all sides are Squar AKO = A Kind Of equal Figure 1.2 semantic network structure In figure 1.2 the arc labelled Has_prop denotes that the object from which the arc originates has the property to which the arc points. This representation method is particularly useful for classification problems. 1.7.2.3 Frames A frame represents an object or situation by describing the collection of attributes that it possesses. It does this by listing all the attributes of a typical case and by providing a slot for each. A frame structure can be as shown below: parrot is_a: bird colour: value set: green red and blue white default: green weight: from 2 lb to 6 lb origin: set value: India Africa Latin America default: India From the above example we can see that each slot is filled with appropriate data and some of the slots can have a range of permitted values and a default value. Some frames can also be filled from other frames which are linked to it. 9 © Dr.A Al-Arashi 2018 1.8 Inference strategies Drawing conclusions from fulfilled conditions is known as an inference. In other words inference is the act of inferring new conclusion from a body of knowledge. A series of inferences is inference chain. There are two methods of inference:  Forward chaining (forward reasoning).  Backward chaining (backward reasoning). 1.8.1 Forward chaining Forward chaining is also known as data driven because it starts from data and infers conclusions. To make this idea clear, assume that we have an expert system which has the following rules in its knowledge base: Rule 1: IF A person age is less than 30 years. THEN Person is young. Rule 2: IF A person worked for more than 3 years in a job. THEN Person has experience. Rule 3: IF A person is young and, The person has experience. THEN The person has priority to get the job. Now assume that the expert system is asked to find out whether a person can get a job. Assuming that the person is: 1- 25 years old. 2- Worked for 5 years in a certain field. Starting with the above two facts in the data base, the first time the rules are tested rule no. 1 is fired (applied) and the conclusion that the person is young is drawn and added to the data base. The second time the rules are tested rule no. 2 is fired and the conclusion of that rule, that the person has experience, is added to the data base. When the rules are tested for the third time the only rule which will fire is rule no. 3 and the conclusion of this rule is driven, i.e. the person has priority to get the job. It should be noted that the practical expert system may include hundreds or even thousands of rules in its knowledge base. This may result in a large number of rules being fired which have no relation to the final conclusion that we want to reach. Due to this deficiency forward chaining inference is not recommended for expert systems with a large knowledge base. 1.8.2 Backward chaining In this method inference starts with the desired conclusion that we want to prove so this inference strategy is called goal driven reasoning. To illustrate how this strategy works consider the knowledge base of section 1.8.1. Let us follow how the conclusion of rule no. 3 can be proven with the same information in the example of the previous section. The goal is to find if the person has priority to get the job. To prove this the inference engine takes the conditions of rule no. 3 and tries to prove it. The first sub-goal is to find that "the person is young" , to prove this the backward mechanism tries to prove that this sub-goal is true 10 © Dr.A Al-Arashi 2018 causing rule no. 1 to be fired concluding that the first condition is true. The second sub-goal is to find wither the person has experience or not i.e. if the second condition of rule no. 3 is true or not, this causes rule no. 2 to be fired concluding that the second sub-goal is true. Having proved that both the conditions of rule no. 3 are true the conclusion of that rule is also true and the person has priority to get the job. The advantage of this method is that only the rules that related to the desired conclusion are tested which makes this inference strategy more effective particularly if there are many rules. 1.9 Tools and languages for building expert systems Expert systems can be built using one of the following:  High level languages.  Programming environment.  Expert system shells each one of the expert systems tools is briefly described below. 1.9.1 High level languages High level languages include BASIC, FORTRAN and C, but expert systems are commonly built using the artificial intelligence programming languages such as LISP (LISt Processing) and PROLOG (PROgraming in LOGic). The decision about whether to use PROLOG or LISP depends on:  The hardware.  The knowledge representation scheme, whether rules or frames or any other scheme.  The inference strategy suitable for solving the problem under consideration. PROLOG is a good choice if the problem is more goal driven than data driven and if the knowledge is to be represented as rules and frames. While LISP is better if the problem is data driven and if a complex frame based knowledge representation is required. PROLOG has the following advantages over LISP:  Less expensive.  Easier to learn.  PROLOG saves time for the programmer since it has a built in backward chaining facility 1.9.2 Programming environments Programming environments provide some ready functions in LISP or PROLOG or any other programming language. A programming environment offers different knowledge representation methods and backward and forward inference strategies. Using a programming environment like KEE and ART may help developing a large and complex system, but the drawback of this system is that they are very expensive. 1.9.3 Expert system shells The shells are generated by taking an expert system and generalising it e.g. EMYCIN generated from MYCIN. There are many expert systems shells but the problem with them is that each one of them is only suitable to construct a system that addresses problems similar to the original expert system. 11 © Dr.A Al-Arashi 2018 1.9.4 Criteria for tool selection 1-Fitness of the tool to the problem knowledge representation method and inference method.  Knowledge representation:  Rule- based system  Form based system  Hybrid system  Inference methods  Forward inference  Backward inference  Hybrid 2. Effectiveness of the developer interface  Documentation, on line help, tutorials  Knowledge entry and command function  Editor  Menus  Visualization of knowledge structure  Uncertainty – handling 3. Effectiveness and friendliness of the user interface  User response format (answers tuber) answer taken as  Typed text  Box  Lists  Mouse use, and menus, windows  Menus creation  Sound  Reply to the user  Graphic handling  Display visual images 4. Integration capability with other programs and databases 5. Costs Including run time costs licensing developed expert system 12 © Dr.A Al-Arashi 2018 Introduction to Machine Learning Dr. Ahmed Al-Arashi March 2017 Topics to Cover  Why Machine Learning?  Definition of Machine Learning.  Importance of Machine Learning  Area of application  Types of Learning.  Learning Algorithms.  Learning Algorithms for supervised learning (with example).  Regression Problems.  Classification Problems  How to use learning algorithms  How to fine-tune the algorithms for better performance 1 Why Machine Learning?  If an expert system–brilliantly designed, engineered and implemented–cannot learn not to repeat its mistakes, it is not as intelligent as a worm or a or a kitten.  Find a bug in a program, and fix it, and the program will work today. Show the program how to find and fix a bug, and the program will work forever.  If we are ever to make claims of creating an artificial intelligence, we must address issues in natural language, automated reasoning, and machine learning. What is Machine Learning?  Machine learning refers to a system capable of the autonomous acquisition and integration of knowledge. This capacity to learn from experience, analytical observation, and other means, results in a system that can continuously self-improve and thereby offer increased efﬁciency and effectiveness.  “A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.”  So if It is required to predict, for example, traffic patterns at a busy intersection (task T), it could be run through a machine learning algorithm with data about past traffic patterns (experience E) and, if it has successfully “learned”, it will then do better at predicting future traffic patterns (performance measure P). 2 Applications for Machine Learning  Machine perception  Computer vision, including object recognition  Natural language processing  Pattern recognition  Search engines  Medical diagnosis  Bioinformatics  Brain-machine interfaces  Stock market analysis  Classifying DNA sequences  Information retrieval  Recommender systems Types of Machin Learning There are tow different types of Machine Learning:  Supervised machine learning: The program is “trained” on a predefined set of “training examples”, which then facilitate its ability to reach an accurate conclusion when given new data. (We are going to look at this type only)  Unsupervised machine learning: The program is given a bunch of data and must find patterns and relationships therein. 3 Supervised Machine Learning In the majority of supervised learning applications, the ultimate goal is to develop excellently tuned predictor function h(x) (sometimes called the “hypothesis”). “Learning” consists of using sophisticated mathematical algorithms to optimize this function so that, given input data (x) about a certain domain (say, square footage of a house), will accurately predict some interesting value h(x) (say, market price for said house). In practice, (x) almost always represents multiple data points. So, for example, a housing price predictor might take not only square meters (x1) but also number of bedrooms (x2), number of bathrooms (x3), number of floors (x4), year built (x5), and so forth. Determining which inputs to use is an important part of ML design. However, for the sake of explanation, it is easiest to assume a single input value is used. Supervised Machine Learning (cont.) So let our simple predictor has this form: Where, and are constants and our goal is to find the perfect values Of and to make our predictor work as well as possible. Optimizing the predictor h(x) is done using training examples. For each training example, we have an input value (x-train), for which a corresponding output, y, is known in advance. For each example, we find the difference between the known, correct value y, and our predicted value h (x-train). With enough training examples, these differences give us a useful way to measure the “wrongness” of h(x). We can then tweak h(x) by tweaking the values of and to make it “less wrong”. This process is repeated over and over until the system has converged on the best values for and. In this way, the predictor becomes trained, and is ready to do some real world predicting. 4 Simple Machine Learning Example Let’s take a simple problem for illustrating this concept, however, in the real world, the problems are much more complex. On this flat screen we can draw you a picture of, at most, a three dimensional data set, but Machine Learning problems commonly deal with data with millions of dimensions, and very complex predictor functions. Machine Learning solves problems that cannot be solved by numerical means alone. With that in mind, let’s look at a simple example. Say we have the following training data, wherein company employees have rated their satisfaction on a scale of 1 to 100. Simple Machine Learning Example (cont.) 5 Simple Machine Learning Example (cont.) Note the following The data is a little noisy. It does not all fit neatly on a straight line. However it could be seen that there is a pattern to it ( employee satisfaction tends to go up as salary goes up). This is always the case with real world data (and we absolutely want to train our machine using real world data). The objective is, how can we train a machine to perfectly predict an employee’s level of satisfaction? The answer, of course, is that we can’t. The goal of ML is never to make “perfect” guesses, because ML deals in domains where there is no such thing. The goal is to make guesses that are good enough to be useful. Simple Machine Learning Example (cont.) Let’s give our machine the data given above and have it learn. We have our predictor as: First we have to initialize our predictor h(x) with some reasonable values of and Say 12 and 0.2. The result is: The result will be as shown in the graph below. 6 Simple Machine Learning Example (cont.) Let’s give our machine the data given above and have it learn. We have our predictor as: First we have to initialize our predictor h(x) with some reasonable values of and , say 12 and 0.2. The result is: Lets see the result in the graph below. Simple Machine Learning Example (cont.) What is the employee satisfaction of $ 60 salary? How good is it compered to the real world? How to improve it? 7 Simple Machine Learning Example (cont.) How to improve our predictor? Give this predictor all the salaries from our training set, and take the differences between If we perform a little the resulting predicted mathematic, the value of satisfaction ratings and θ0 and θ1 can be calculate, the actual satisfaction with very high certainty, ratings of the that values of 13.12 for θ0 corresponding and 0.61 for θ1 are going to give a better predictor. employees. Simple Machine Learning Example (cont.) If the values of and c are change the predictor will be changed we may have it as after about 1500 iterations and the graph will look like the one below The value of the predictor can be improved by using cost function such as well established standard (linear least squares function) 8 Simple Machine Learning Example (cont.) If the values of and c are change the predictor will be changed we may have it as after about 1500 iterations and the graph will look like the one below The value of the predictor can be improved by using cost function such as well established standard (linear least squares function) Real World ML Problems The above example is technically a simple problem of univariate linear regression, which in reality can be solved by deriving a simple normal equation and skipping this “tuning” process altogether. In the real world, the problems are much more complex. On this flat screen we can draw a picture of, at most, a three dimensional data set, but Machine Learning problems commonly deal with data with millions of dimensions, and very complex predictor functions. Machine Learning solves problems that cannot be solved by numerical means alone. More complex predictor that looks like this: 9 Real World ML Problems (cont.) Note the following: ML builds heavily on statistics. For example, when machin

Document Details

Related

Full Transcript

Upgrade to continue