Chapter 2 Knowledge

  • knowledge-based agents
    Agents that reason by operating on internal representations of knowledge. Somehow inside the AI, they have some understanding of what it means to know something.

Terms and Symbols

  • sentence
    An assertion about the world in a knowledge representation language.

  • propositional logic
    Statement based on a logic of proposition, or just statements about the owrld.

    • Proposition Symbol
      P Q R, each of them represents a statement.

    • Logical Connectives
      $\neg$ not $\wedge$ and $\vee$ or $\rightarrow$ implication $\leftrightarrow$ biconditional

  • knowledge base
    A set of sentences known by a knowledge-based agent.

  • Entailment
    In every model in which sentence $\alpha$ is true, sentence $\beta$ is also true.

$$\alpha \models \beta$$

  • inference
    The process of driving new sentences from old ones.

Inference Algorithm

Model checking

  • To determine if KB $\models \alpha$
    • Enumertate all possible models
    • If in every model where KB is true, $\alpha$ is true, then KB entails $\alpha$
      (check whether KB is true first, and then check whether the Query is true under the circunstance that KB is true)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def model_check(knowledge, query):
    # Checks if knowledge base entails query
    def check_all(knowledge, query, symbols, model):
        # If model has an assignment for each symbol
        if not symbols:
            # If knowledge base is true in model, then the query must be true.
            if knowledge.evaluate(model):
                return query.evaluate(model)
            return True
        else:
            # Choose one of the unused remaining symbol.
            remaining = symbols.copy()
            p = remaining.pop()

            # Creat a model where symbol is true.
            model_true = model.copy()
            model_true[p] = True
            # Creat a model where symbol is true.
            model_false = model.copy()
            model_false[p] = False
            # Ensure entailment holds both circumstances
            return(check_all(knowledge, query, remaining, model_true) and check_all(knowledge, query, remaining, model_false))
        
    # Get all symbols in both knowledge and query
    symbols = set.union(knowledge.symbols(), query.symbols())

    #check that knowledge base entails query
    return check_all(knowledge, query, symbols, dict())

Knowledge Engineering

We can use a computer to be able to represent knowledge and draw conclusions based on that knowledge.
At anytime we can translate something into propositional logic symbols, type of aproach can be useful.

Inference Rules

Model Checking is not an efficient algorithm because it has to consider every possible model before giving the answer (a reminder: a query R is true if under all the models (truth assignments) where the KB is true, R is true as well). Inference rules allow us to generate new information based on existing knowledge without considering every possible model.

Inference rules are usually represented using a horizontal bar that separates the top part, the premise, from the bottom part, the conclusion. The premise is whatever knowledge we have, and the conclusion is what knowledge can be generated based on the premise.

In this example, our premise consists of the following propositions:

  • If it is raining, then Harry is inside.
  • It is raining.

Based on this, most reasonable humans can conclude that

  • Harry is inside.

Modus Ponens

The type of inference rule we use in this example is Modus Ponens, which is a fancy way of saying that if we know an implication and its antecedent to be true, then the consequent is true as well.

$$\alpha \rightarrow \beta$$

$$\alpha$$

$$\beta$$

This means if we have known the deduction that $\alpha$ implicates $\beta$, and also we have confirmed that $\alpha$ is true, so that we can also conclude that $\beta$ is true.

And Elimination

If an And proposition is true, then any one atomic proposition within it is true as well.

$$\alpha \wedge \beta$$

$$\alpha$$

Double Negation Elimination

A proposition that is negated twice is true. For example, consider the proposition “It is not true that Harry did not pass the test”. We can parse it the following way: “It is not true that (Harry did not pass the test)”, or “$\neg$(Harry did not pass the test)”, and, finally “$\neg$($\neg$(Harry passed the test)).” The two negations cancel each other, marking the proposition “Harry passed the test” as true.

$$(\neg(\neg \alpha))$$

$$\alpha$$

Implication Elimination

An implication is equivalent to an Or relation between the negated antecedent and the consequent. As an example, the proposition “If it is raining, Harry is inside” is equivalent to the proposition “(it is not raining) or (Harry is inside).”

$$\alpha \rightarrow \beta$$

$$\neg \alpha \vee \beta$$

Biconditional Elimination

A biconditional proposition is equivalent to an implication and its inverse with an And connective.

$$\alpha \Leftrightarrow \beta$$

$$(\alpha \rightarrow \beta) \wedge (\beta \rightarrow \alpha)$$

De Morgan’s Law

It is possible to turn an And connective into an Or connective. That is, for the And proposition earlier to be true, at least one of the propositions in the Or propositions must be true. Similarly, it is possible to conclude the reverse.

$$\neg(\alpha \wedge \beta)$$

$$\neg \alpha \vee \neg \beta$$

$$\neg(\alpha \vee \beta)$$

$$\neg \alpha \wedge \neg \beta$$

Distributive Property

A proposition with two elements that are grouped with And or Or connectives can be distributed, or broken down into, smaller units consisting of And and Or.

$$(\alpha \wedge(\beta \vee \gamma))$$

$$(\alpha \wedge \beta)\vee(\alpha \wedge \beta)$$

Theorem Proving

  • Initial state: starting knowledge base
  • Actions: inference rules
  • Transition model: new knowledge base after inference
  • Goal test: checking whether the statement that we are trying to prove is in the KB
  • Path cost function: the number of steps in the proof

Resolution

Resolution is a powerful inference rule that states that if one of two atomic propositions in an Or proposition is false, the other has to be true. More formally, we can define resolution the following way:

$$P \vee Q$$
$$\neg P$$

$$Q$$

Resolution relies on Complementary Literals, two of the same atomic propositions where one is negated and the other is not, such as P and $\neg$ P.

Complementary literals allow us to generate new sentences through inferences by resolution. Thus, inference algorithms locate complementary literals to generate new knowledge.

Clause

A Clause is a disjunction of literals (a propositional symbol or a negation of a propositional symbol, such as P, $\neg$ P). A disjunction consists of propositions that are connected with an Or logical connective (P $\vee$ Q $\vee$ R). A conjunction, on the other hand, consists of propositions that are connected with an And logical connective (P $\wedge$ Q $\wedge$ R). Clauses allow us to convert any logical statement into a Conjunctive Normal Form (CNF), which is a conjunction of clauses, for example: (A $\vee$ B $\vee$ C) $\wedge$ (D $ \vee \neg$ E) $\wedge$ (F $\vee$ G).

Steps in Conversion of Propositions to Conjunctive Normal Form

  • Eliminate biconditionals
    • Turn ($\alpha \Leftrightarrow \beta$) into ($\alpha \rightarrow \beta$) $\wedge$ ($\beta \rightarrow \alpha$).
  • Eliminate implications
    • Turn ($\alpha \rightarrow \beta$) into $\neg \alpha \vee \beta$.
  • Move negation inwards until only literals are being negated (and not clauses), using De Morgan’s Laws.
    • Turn $\neg(\alpha \wedge \beta)$ into $\neg \alpha \vee \neg \beta$

Here’s an example of converting $(P \vee Q) \rightarrow R$ to Conjunctive Normal Form:

$(P \vee Q) \rightarrow R$
$\neg(P \vee Q) \vee R$ ==Eliminate implication==
$(\neg P \wedge \neg Q) \vee R$ ==De Morgan’s Law==
$(\neg P \vee R) \wedge (\neg Q \vee R)$ ==Distributive Law==
At this point, we can run an inference algorithm on the conjunctive normal form. Occasionally, through the process of inference by resolution, we might end up in cases where a clause contains the same literal twice. In these cases, a process called factoring is used, where the duplicate literal is removed. For example, $(P \vee Q \vee S) \wedge (\neg P \vee R \vee S)$ allow us to infer by resolution that $(Q \vee S \vee R \vee S)$. The duplicate $S$ can be removed to give us $(Q \vee R \vee S)$.

Resolving a literal and its negation, i.e. $\neg P$ and $P$, gives the ==empty clause()==. The empty clause is always false, and this makes sense because it is impossible that both $P$ and $\neg P$ are true. This fact is used by the resolution algorithm.

  • To determine if $KB \models \alpha$:
    • Check: is $(KB \wedge \neg \alpha)$ a contradiction?
    • If so, then $KB \models \alpha$.
    • Otherwise, no entailment.

Proof by contradiction is a tool used often in computer science. If our knowledge base is true, and it contradicts $\neg \alpha$, it means that $\neg \alpha$ is false, and, therefore, $\alpha$ must be true. More technically, the algorithm would perform the following actions:

To determine if $KB \models \alpha$:

  • Convert $(KB \wedge \neg \alpha)$ to Conjunctive Normal Form.
  • Keep checking to see if we can use resolution to produce a new clause.
  • If we ever produce the empty clause (equivalent to False), congratulations! We have arrived at a contradiction, thus proving that $KB \models \alpha$.
  • However, if contradiction is not achieved and no more clauses can be inferred, there is no entailment.

Here is an example that illustrates how this algorithm might work:
Does $(A \vee B) \wedge (\neg B \vee C) \wedge (\neg C)$ entail $A$?
First, to prove by contradiction, we assume that A is false. Thus, we arrive at $(A \vee B) \wedge (\neg B \vee C) \wedge (\neg C) \wedge (\neg A)$.
Now, we can start generating new information. Since we know that $C$ is false $(\neg C)$, the only way $(\neg B \vee C)$ can be true is if $B$ is false, too. Thus, we can add $(\neg B)$ to our $KB$.
Next, since we know $(\neg B)$, the only way $(A \vee B)$ can be true is if $A$ is true. Thus, we can add $(A)$ to our $KB$.
Now our KB has two complementary literals, $(A)$ and $(\neg A)$. We resolve them, arriving at the empty set, $()$. The empty set is false by definition, so we have arrived at a contradiction.

First Order Logic 一阶逻辑

First order logic is another type of logic that allows us to express more complex ideas more succinctly than propositional logic. First order logic uses two types of symbols: Constant Symbols and Predicate Symbols. Constant symbols represent objects, while predicate symbols are like relations or functions that take an argument and return a true or false value.

For example, we return to the logic puzzle with different people and house assignments at Hogwarts. The constant symbols are people or houses, like Minerva, Pomona, Gryffindor, Hufflepuff, etc. The predicate symbols are properties that hold true or false of some constant symbols. For example, we can express the idea that Minerva is a person using the sentence $Person(Minerva)$. Similarly, we can express the idea the Gryffindor is a house using the sentence $House(Gryffindor)$. All the logical connectives work in first order logic the same way as before. For example, $\neg House(Minerva)$ expresses the idea that Minerva is not a house. A predicate symbol can also take two or more arguments and express a relation between them. For example, BelongsTo expresses a relation between two arguments, the person and the house to which the person belongs. Thus, the idea that Minerva belongs to Gryffindor can be expressed as $BelongsTo(Minerva, Gryffindor)$. First order logic allows having one symbol for each person and one symbol for each house. This is more succinct than propositional logic, where each person—house assignment would require a different symbol.

Universal Quantification

Quantification is a tool that can be used in first order logic to represent sentences without using a specific constant symbol. Universal quantification uses the symbol $\forall$ to express “for all.” So, for example, the sentence $\forall x. BelongsTo(x, Gryffindor) \rightarrow \neg BelongsTo(x, Hufflepuff) $ expresses the idea that it is true for every symbol that if this symbol belongs to Gryffindor, it does not belong to Hufflepuff.

Existential Quantification

Existential quantification is an idea parallel to universal quantification. However, while universal quantification was used to create sentences that are true for all x, existential quantification is used to create sentences that are true for at least one x. It is expressed using the symbol $\exists$. For example, the sentence $\exists x. House(x) \wedge BelongsTo(Minerva, x)$ means that there is at least one symbol that is both a house and that Minerva belongs to it. In other words, this expresses the idea that Minerva belongs to a house.

Existential and universal quantification can be used in the same sentence. For example, the sentence $\forall x. Person(x) \rightarrow (\forall y. House(y) \wedge BelongsTo(x, y))$ expresses the idea that if $x$ is a person, then there is at least one house, $ y$ , to which this person belongs. In other words, this sentence means that every person belongs to a house.

There are other types of logic as well, and the commonality between them is that they all exist in pursuit of representing information. These are the systems we use to represent knowledge in our AI.