这门课程所使用的教材是 Artificial Intelligence: A Modern Approach，本份笔记直接沿用书本中对变量及名词的定义，在此没有对它们进行特殊解释。

Lecture 9-10

1. Syntax (语法): how sentences are expressed; semantics (语义): meaning of the sentence, e.g., truth value.
2. If a sentence α is true in model m, we say m satisfies α, or m is a model of α:
   • M(α) is the set of all models of α; M(KB) is the set of all models of KB;
   • KB ⊨ α if and only if M(KB) is a subset M(α).
   • KB ⊨ α: KB entails sentence α, if and only if, α is true in all worlds where KB is true.
3. Entailment (⊨) is different from inference (⊢). Think of inference a the process of finding the entailment:
   • KB ⊢i α = sentence α can be derived from KB by procedure i.
   • Soundness: i is sound if whenever KB ⊢i α, it is also true that KB ⊨ α.
   • Completeness: i is complete if whenever KB ⊨ α, it is also true that KB ⊢i α.
4. Proof methods:
   1. Model checking: Truth table enumeration (sound and complete); Heuristic search in model space (sound but incomplete);
   2. Application of inference rules.
5. A sentence is valid if it is true in all models (tautologies); A sentence is satisfiable if it is true in at least one model.
   • α is valid if and only if ¬α is unsatisfiable;
   • α is satisfiable if and only if ¬α is not valid.
6. Names for important tautologies:
   • Commutativity of ⋀ / ⋁: 交换律
   • Associativity of ⋀ / ⋁: 结合律
   • Double-negation elimination
   • Contraposition: α ⇒ β ⇔ ¬β ⇒ ¬α
   • Implication elimination
   • Biconditional elimination
   • De Morgan
   • Distributivity of ⋀ / ⋁ over ⋁ / ⋀: 分配律
7. α ⊨ β if and only if the sentence (α ⋀ ¬β) is unsatisfiable.
8. Names for inference rules:
   • Modus ponens: from α ⇒ β, α, we get β
   • Modus tollens: from α ⇒ β, ¬β, we get ¬α
   • And-elimination: from α ⋀ β, we get α
   • Or-introduction: from α, we get α ⋁ β
   • Both directions of all tautologies like contraposition: (α ⇒ β) ⇔ (¬β ⇒ ¬α)

Lecture 11-12

1. Resolution Inference: Complete when coupled with complete search algorithm.
   • To prove that KB ⊨ α, we show that (KB ⋀ ¬α) is unsatisfiable:
     1. Convert (KB ⋀ ¬α) to CNF;
     2. Apply the resolution rule wherever possible and add the result as an additional clause in the conjunction;
     3. Repeat step 2 until either:
        • No new clauses can be added: KB does not entail α.
        • Two clauses resolve to yield the empty clause: KB entails α.
2. If each clause is a horn clause in KB and the queries are atomic, then we can use linear-time algorithm forward chaining and backward chaining to do the inference. Complexity for backward chaining can be much less than linear in size of KB.
3. Symbols for constants, predicates and functions usually start with upper-case letters; Variables are written in lowercase letters.
4. ⇒ is a natural connective to use with ∀; ⋀ is a natural connective to use with ∃.
5. De Morgan for quantifier negation: ¬∀x P ⇔ ∃x ¬P.

Lecture 13

1. A ground literal’s terms are all ground terms; A ground term is a term without variables.
2. SUBST(θ, α): rewrite a sentence, α, by applying substitution, θ.
3. For every unifiable pair of expressions there is a Most General Unifier (a unique substitution) that equates the pair while making the fewest restrictions on the values of the variables.
4. First-order definite clauses are disjunctions of literals, of which exactly one is positive:
   • Atomic sentences (positive literals) are also definite clauses;
   • Definite clauses can include variables. The variables are assumed to be universally quantified.
5. Datalog Knowledge base contains only first-order definite clauses with no function symbols.
6. Forward chaining is sound and complete for first-order definete clauses. We can use CSP heuristics like Minimum-Remaining Value to imporve efficiency. We can also do incremental forward chaining – only consider rules with premise that involves a literal that can unify with the facts newly inferred from the previous iteration.
7. Backward chaining is sound but incomplete due to infinite loops. But it’s linear in size of proof.

Lecture 14

1. Herbrand’s theorem: If there is a proof that a sentence is entailed by the original first-order knowledge base, then there is a proof involving just a finite subset of the propositionalized knowledge base. Entailment for first-order logic is semidecidable. We can say yes to every entailed sentence, but there is no way to say no to every non-entailed sentence.
2. CNF conversion for first-order logic:
   1. Eliminate implications;
   2. Move ¬ inward;
   3. Standardize variables;
   4. Skolemization;
      • Unique function names;
      • Arguments for all of the universally quantified variables in whose scope the existential quantifier appears;
      • We used Skolem Constants to remove existential quantifiers when the sentence was in a specific form (存在量词在最外面);
   5. Drop universal quantifiers;
   6. Distribute ⋁ over ⋀.
3. Russell’s Paradox:
   • The paradox arises within naive set theory by considering the set of all sets that are not members of themselves.
   • A master catalog of all library catalogs which do not include themselves.
   • A barber who shaves exactly those people who do not shave themselves.
4. Prolog.

(不知道为什么没有 Lecture 15)

Lecture 16

1. Knowledge engineering is declarative (not procedural).
2. Propositional and first-order logic are monotonic:
   • As new sentences α are added to KB what is entailed can never decrease.
   • Non-monotonic logic eliminates this restriction.
3. 4 efforts of knowledge sharing:
   • Knowledge Interchange Format (KIF): Translate from KB1 to KIF then to KB2;
   • Knowledge Representation System Specification: Create “standard” specification for KR language within a particular family of languages;
   • Standardized Query Interface: Share across KBs by querying from one KB to the other (as in databases);
   • Shared, Reusable Knowledge Bases: Create a common “upper” ontology that can form the basis for many knowledge based systems.
4. 4 possible KRR (knowledge representation and reasoning) approaches:
   • Knowledge engineering: Write down all of the necessary knowledge in a manner that supports automated inference;
     • Cyc / OpenMind Common Sense
   • Semantic web: Distribute the knowledge engineering task across the entire world, supported by international standards for encoding knowledge;
     • WikiData
   • Knowledge extraction: Find knowledge in natural language text (e.g. social media), and convert it into a representation that supports automated reasoning;
     • Hearst Patterns / Commonsense axioms from text
   • Experiential learning: Build a robot that can learn the knowledge by interacting with the world, just like a human child does;

Lecture 17

1. Situation Calculus:
   • Situations: Each time step is a “situation”. A function Result(a, s) gives the situation resulting from applying action a in situation s;
   • Fluents: Functions & predicates whose truth values can change from one situation to the other;
   • Atemporal (or eternal) predicates and functions.
2. Classical issues:
   • Frame problem: Representing all things that stay the same from one situation to the next;
   • Qualification problem: Defining the circumstances under which an action is guaranteed to work;
   • Ramification problem: Proliferation of implicit consequences of actions as actions may have secondary consequences.
3. STRIPS-style planning:
   • Representing states:
     • A conjunction of positive literals (must be grounded and function free);
     • Closed world assumption: If not explicitly mentioned as true, assumed false.
   • Representing goals:
     • Generally a partial state specification (still must be positive, grounded and function free);
     • A goal is satisfied if state contains all literals in goal.
   • Representing actions:
     • An action is specified by a name, a list of parameters, a precondition and an effect:
       • PRECOND: Must be true in state for action to execute (conjunction of function-free positive literals);
       • EFFECT: Changes to state when action executes (conjunction of function-free literals); Positive literals add facts, negated literals remove facts.
   • Assumption: Every literal not modified by EFFECT remains unchanged to avoids representational frame problem.
   • Planning Domain Definition Language (PDDL) is slightly more expressive (allows negative literals in goals and preconditions):
     • Neither language allows functions;
     • Neither deals with the ramification problem;
     • Neither deals with the qualification problem.
   • Forward: Progression planner / Backward: Regression planner. Both progression and regression are still NP-hard.
4. Partial-order planning (POP):
   • Each plan has 4 components:
     • A set of actions (steps in the plan);
     • A set of ordering constraints: A < B (A before B);
     • A set of causal links (protection intervals);
     • A set of open preconditions (goals).
5. Planning graph:
   • A planning graph consists of a sequence of levels that correspond to steps in the plan; each level consists of a set of literals and a set of actions:
     • Literals = all those that could be true at that time step, based on the actions executed at preceding time steps;
     • Actions = all those actions that could have their preconditions satisfied at that time step, based on which literals actually hold;
   • Connect preconditions of actions in A0 to S0 and effects to S1; Inaction is represented by persistence actions (like frame axioms);
   • Conflicts:
     • A mutex relation holds between two actions when:
       • Inconsistent effects: one action negates the effect of another;
       • Interference: an effect of one action negates a precondition of the other;
       • Competing needs: a precondition of one action is mutually exclusive with a precondition of the other;
     • A mutex relation holds between two literals when:
       • One is the negation of the other;
       • Each possible action pair that could achieve the literals is mutex;
   • Stop when two consecutive levels are identical; complexity is polynomial.