POAI-UNIT 4 PPT NOTES PDF

Rajalakshmi Engineering College An Autonomous Institution Chennai-602105  PRINCIPLES OF ARTIFICIAL INTELLIGENCE (AI19341) Department of CSE  SYLLABUS UNIT-IV Knowledge & reasoning Statistical Reasoning: Probability and Bays’ Theor...

Rajalakshmi Engineering College An Autonomous Institution Chennai-602105  PRINCIPLES OF ARTIFICIAL INTELLIGENCE (AI19341) Department of CSE  SYLLABUS UNIT-IV Knowledge & reasoning Statistical Reasoning: Probability and Bays’ Theorem, Certainty Factors and Rule-Base Systems, Bayesian Networks, Dempster- Shafer Theory, Fuzzy Logic. AI for knowledge representation, rule-based knowledge representation, procedural and declarative knowledge, Logic programming, Forward and backward reasoning. Department of CSE  Statistical Reasoning Reasoning in Artificial Intelligence refers to the process by which AI systems analyze information, make inferences, and draw conclusions to solve problems or make decisions. It is a fundamental cognitive function that enables machines to mimic human thought processes and exhibit intelligent behavior. Statistical reasoning in AI is a critical component that underpins the ability of algorithms to learn from data. It involves the application of statistical principles to interpret and analyze data, enabling AI systems to make informed decisions based on patterns and trends. Probability In Probabilistic approach of knowledge representation a given sentence is labelled with a real number in the range 0 to 1. 0 meaning the sentence is completely false, and 1 meaning it is completely true. A label of 0.5 means there is equal chance that the sentence is true or false. If a coin is flipped there is an equal chance of it landing on the heads side or the tails side, so if we say that H1 stands for “on the first toss of the coin it lands Heads-up”, we can express this by p(H1)=0.5. Let us say that H2 stands for “on the second toss of the coin it lands heads- up” then p(H2) is 0.5  Conditional Probability Conditional probability is a principle in probability theory. It relates to the probability that a certain event will occur based on the fact that a previous event has already occurred. It involves two or more events that are not independent, and asks, "If we know A has happened, what's the chance of B also happening?" Conditional probability is calculated by multiplying the probability of the preceding event by the updated probability of the succeeding, or conditional, event.  Conditional probability measures the likelihood of a certain outcome (A), based on the occurrence of some earlier event (B). Two events are said to be independent if one event occurring does not affect the probability that the other event will occur. However, if one event occurring (or not occurring) does affect the likelihood that the other event will happen, the two events are said to be dependent. If events are independent, then the probability of event B occurring is not contingent on what happens with event A. For example, an increase in Apple's shares has nothing to do with a drop in wheat prices.  Let A and B be the two events associated with a random experiment. Then, the probability of A's occurrence under the condition that B has already occurred and P(B) ≠ 0 is called the Conditional Probability. It is denoted by P (A/B). Thus, you have P(A/B) = Probability of occurrence of A given that B has already occurred. P (B/A) = Probability of occurrence of B given that A has already occurred.  Bayes Theorem Bayes' Theorem, named after 18th-century British mathematician Thomas Bayes, is a mathematical formula for determining conditional probability. Conditional probability is the likelihood of an outcome occurring based on a previous outcome in similar circumstances. Bayes' Theorem provides a way to revise existing predictions or theories (update probabilities) given new or additional evidence. Exampl ehave been planning a picnic for your family. You You are trying to decide whether to postpone due to rain. The chance of rain on any day is 15%. The morning of the picnic, its cloudy. The probability of it being cloudy is 25% and on days where it rains, it’s cloudy in the morning 80% of the time. P(rain) = 0.15 P(cloudy) = 0.25 P(cloudy|rain) = 0.80  Certainty Factors When analyzing a situation and drawing certain results about it in the real world, we cannot be cent percent sure about our conclusions. There is some uncertainty in it for sure. We as human beings have the capability of deciding whether the statement is true or false according to how much certain we are about our observations. But machines do not have this analyzing power. So, there needs to be some method to quantize this estimate of certainty or uncertainty in any decision made. To implement this method, the certainty factor was introduced for systems which work on Artificial Intelligence.  The Certainty Factor (CF) is a numeric value which tells us about how likely an event or a statement is supposed to be true. It is somewhat similar to what we define in probability, but the difference in it is that an agent after finding the probability of any event to occur cannot decide what to do. Based on the probability and other knowledge that the agent has, this certainty factor is decided through which the agent can decide whether to declare the statement true or false. The value of the Certainty factor lies between -1.0 to +1.0, where the negative 1.0 value suggests that the statement can never be true in any situation, and the positive 1.0 value defines that the statement can never be false. The value of the Certainty factor after analyzing any situation will either be a positive or a negative value lying between this range. The value 0 suggests that the agent has no information about the event or the situation.  A minimum Certainty factor is decided for every case through which the agent decides whether the statement is true or false. This minimum Certainty factor is also known as the threshold value. For example, if the minimum certainty factor (threshold value) is 0.4, then if the value of CF is less than this value, then the agent claims that particular statement false. Measures for Certainty Factors Measure of Belief Measure of Disbelief CF always lies in the interval -1 to +1 -1 if statement is false and +1 if statement is true always.  CFs are calculated using two other measures: 1. MB(H, E) – Measure of Belief: value between 0 and 1 representing the degree to which belief in the hypothesis H is supported by observing evidence E. It is intended to capture the degree to which the evidence increases probability: p(H|E)-p(H) in proportion to the maximum possible increase in probability: 1-p(H) 2. MD(H, E) – Measure of Disbelief: value between 0 and 1 representing the degree to which disbelief in the hypothesis H is supported by observing evidence E. CF is calculated in terms of the difference between MB and MD: Formulas for CF Multiple Evidences single Hypothesis MB [ H, E1 and E2] = MB[H,E1]+MB[H,E2] * [1- MD(H,E1)] MD [ H, E1 and E2] = MD[H,E1]+MD[H,E2] * [1- MD(H,E1)] Therefore CF is calculated in terms of the difference between MB and MD:  Rule Based Systems A rule-based system in AI is a system that applies human-made rules to store, sort and manipulate data. In doing so, it mimics human intelligence. Rule based system in AI require a set of facts or source of data, and a set of rules for manipulating that data. These rules are sometimes referred to as ‘If statements’ as they tend to follow the line of ‘IF X happens THEN do Y’. The steps can be simplified to: First comes the data or new business event Then comes the analysis: the part where the system conditionally processes the data against its rules Then comes any subsequent automated follow-up actions  Some of the important elements of rule-based system in AI include: A set of facts These facts are assertions or anything that is relevant to the beginning state of the system. Set of Rules This set contains all the actions that should be performed within the scope of a problem and defines how to act on the assertion set. In the set of rules facts are represented in an IF-THEN form.  Components of Rule Based Systems The knowledge base: It contains the specialized expertise required for problem- solving. The information is represented as a set of rules in a rules-based system. Every rule has an IF (condition) THEN (action) structure and defines a relationship, suggestion, directive, strategy, or heuristic. The rule is activated, and the action portion is carried out as soon as the conditional portion of the rule is met. The database: The database contains a collection of facts compared to the knowledge base's rules IF (condition) clause. The inference engine: The expert system uses the inference engine to derive the logic and arrive at a conclusion. The inference engine's task is to connect the facts kept in the database with the rules specified in the knowledge base. The semantic reasoner is another name for the reasoning engine. It deduces information or executes necessary actions based on data and the rule base present in the knowledge base. For example, the match-resolve-act loop used by the semantic reasoner goes like this: Match: A portion of the production rule system is compared to the information in the working memory to create a conflict in which numerous examples of satisfied productions are present Conflict Resolution: Following the matching of the production systems, one of the production cases involved in the conflict will be executed to gauge the procedure's status Act: The production instance chosen in the step before is carried out, changing the information in the working memory. Explanations facilities: The user can use the explanation facilities to question the expert system on how it came to a particular conclusion or why a particular fact is necessary. The expert system must be able to defend its logic, recommendations, analyses, and conclusions. User Interface: The user interface is the channel through which the user interacts with the expert system to find a solution to an issue. The user interface should be as simple and intuitive as possible, and the dialogue should be as helpful and friendly as possible. Each of these five components is essential to any rule-based system in AI. These form the basis of the rule-based structure. However, the mechanism might also include a few extra parts. The working brain and the external interface are two examples of these parts. External connection: An expert system can interact with external data files and programs written in traditional computer languages like C, Pascal, FORTRAN, and Basic, thanks to the external interface. Active recall: The working memory keeps track of transient data and knowledge. Bayesian Networks A Bayesian network is a type of graphical model that uses probability to determine the occurrence of an event. It is also known as a belief network or a causal network. It consists of directed cyclic graphs (DCGs) and a table of conditional probabilities to find out the probability of an event happening. It contains nodes and edges, where edges connect the nodes. The graph is acyclic - meaning there is no direct path where one node can reach another. The table of probability, on the other hand, shows the likelihood that a random variable will take on certain values. Example Problem To prevent break-ins, Harry put a brand-new burglar alarm at his house. The alarm consistently reacts to a break-in, but it also reacts to little earthquakes. James and Safina, two of Harry's neighbors, have agreed to call Harry at work when they hear the alarm. James always calls Harry when the alarm goes off, but occasionally he gets distracted by the phone ringing and calls at other times. Safina, on the other hand, enjoys listening to loud music, so occasionally she doesn't hear the alarm. Here, we'd want to calculate the likelihood of a burglar alarm. Determine the likelihood that the alarm went off but that neither a burglary nor an earthquake had taken place, and that both James and Safina had phoned Harry. List Of All Events Occurring in a Bayesian Network Burglary (B) Earthquake(E) Alarm(A) James Calls(D) Safina calls(S)  Let's take the observed probability for the Burglary and earthquake component: P(B=True)=0.002, which is the probability of burglary. P(B=False)=0.998, which is the probability of no burglary. P(E=True)=0.001, which is the probability of a minor earthquake P(E=False)=0.999, Which is the probability that an earthquake Determine the likelihood that the alarm went off but that neither a burglary nor an earthquake had taken place, and that both James and Safina had phoned Harry. P(S,D,A, ¬B,B, ¬E)E) = P(S∣A)∗P(D∣A)∗P(A∣P(S∣A)∗P(D∣A)∗P(A∣ ¬BB ¬E)∗P(E)∗P(¬B)∗P(B)∗P(¬E)E) =0.75∗0.91∗0.001∗0.998∗0.999 =0.00068045=0.00068045 Dempster Shafer Theory Dempster-Shafer Theory was given by Arthur P. Dempster in 1967 and was later developed by his student Glenn Shafer in 1976. This theory was released because of the following reason:- Bayesian theory is only concerned about single evidence. Bayesian probability cannot describe ignorance. DST is a mathematical theory of evidence based on belief functions and plausible reasoning. It is used to combine separate pieces of information (evidence) to calculate the probability of an event. DST offers an alternative to traditional probabilistic theory for the mathematical representation of uncertainty. The idea is to allocate a number between 0 and 1 to indicate a degree of belief on a proposal as in the probability framework. However, it is not considered a probability but a belief mass. The distribution of masses is called basic belief assignment.  Consider a scenario in AI two friends are in a room and a theft happened. One of the friend finds out that other person have stolen his wallet, but that person denies it. Person 1 knows that by checking the attendance log he can find out whether theft is done or not. By checking the log he finds that person 2 has entered his room in his absence. P(Entered|Theft) = 0.9 P(Entered) = 0.3 P(theft) = 0.25 P(Theft|Entered) = P(Entered) * P(Entered|Theft) /  0.3 x 0.9 /0.25 = 0.75 Evidence One P(Entered other work | Theft) = 0.6 P(Not Entered) = 0.5 P(Theft|Entered other work) = P(Theft)* P( Entered other work|Theft)/P(Theft) Second Evidence Department of CSE  Logic in general Logic is the primary vehicle for representing and reasoning about knowledge. In AI we deal with formal logic. The advantage of using formal logic as a language of AI is that it is precise and definite. Logical representation is a language with some definite rules which deal with propositions and has no ambiguity in representation. It represents a conclusion based on various conditions and lays down some important communication rules. Also, it consists of precisely defined syntax and semantics which supports the sound inference. Each sentence can be translated into logics using syntax and semantics. Logics are formal languages for representing information such that conclusions can be drawn. A logic consists of two parts, a language and a method of reasoning. The logical language, in turn, has two aspects, syntax and semantics. Department of CSE  Parts of Logic Thus, to specify or define a particular logic, one needs to specify three things: Syntax defines how symbols can be put together to form the sentences in the language. Semantics define the "meaning" of sentences; i.e., define truth of a sentence in a world (given an interpretation) Syntactic Inference Method: It refers to mechanical method for computing (deriving) new (true) sentences from existing sentences. Department of CSE  Propositional logic A proposition is a declarative statement that’s either TRUE or FALSE (but not both). Propositional logic is also called as Boolean logic as it represents 0 or 1 The symbols of the language: Propositional symbols (Prop): A, B, C,… Connectives: ∧ and ∨ or ¬ not → implies ↔ equivalent to ⊗ xor (different than) ⊥, > False, True Parenthesis :(,). Statements which are questions or commands or opinions are not propositions such as “ How are you’, “what is your name”, are not Department propositions. of CSE  Propositional logic: Syntax Propositional logic is the simplest logic – illustrates basic ideas The proposition symbols P1, P2 etc are (atomic) sentences – If S is a sentence, (S) is a sentence (negation) – If S1 and S2 are sentences, (S1  S2) is a sentence (conjunction) – If S1 and S2 are sentences, (S1  S2) is a sentence (disjunction) –Department If S1 and S2 are sentences, (S1  S2) is a sentence of CSE (implication)  Truth tables for connectives Department of CSE Peter can play Tennis P Peter cannot Play tennis ~P Peter can play tennis and badminton P^Q Peter can play tennis or badminton P˅Q If peter can play tennis then he can play badminton P→Q Peter can play tennis if and onLy if he can play P↔Q badminton Department of CSE  First Order logic In propositional logic, we can only represent the facts, which are either true or false. E.g. “it is raining” But Propositional logic is not sufficiently expressive to represent the following statements “Some humans are intelligent” “All mangoes are sweet” First-order logic is capable of expressing facts about some or all objects in the universe. FOL specifies objects, relations and functions. First-orderDepartment logic is also Known as predicate logic. of CSE Syntax: function (term 1, term 2, …., term n) Predicate(term1, term2,…., termn) X is a girl girl(X) Subject Predicate Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE Department of CSE