Cognitive Science > Methods of AI > Final

Contents 1 Logic 1.1 Fuzzy Logic 1.2 Relevance Logic 1.3 Intuitionism 1.4 Boolean Algebra 1.5 Clause form: Disjunction of literals 1.6 Horn clause: At most one positive literal 1.7 Resolution calculus 1.8 Semantics of first-order logic 1.9 Tense logic 1.10 Space logic 1.11 Reiters default logic 2 Planning 2.1 Deductive planning: Situation calculus 2.2 State-based: STRIPS 2.3 Classic problems 3 Machine learning 3.1 Bayesian learning 3.2 Decision trees 4 Computability 4.1 Ackermann 5 Cognitive Architectures 5.1 SOAR 5.2 ACT-R 5.3 Subsumption architecture

[edit] Logic

[edit] Fuzzy Logic

• A logic dealing with vague predicates
• Conjunction and disjunction
  • Functions called t-norm (conj) and s-norm (dis), commutative/monotone/associative
  • A function (t-norm) mapping two real numbers to another real number, with zero element,
  • Conjunction: 1 is a neutral element, min operation
  • Disjunction: 0 is a neutral element, max operation
  • alg_t(x, y) is a t-norm, alg_s(x, y) = x + y - x*y is a s-norm
  • quo_t(x, y) = (xy)/(x+y-xy) is a t-norm, quo_s(x,y) = (x + y - 2xy)/(1-xy) is a s-norm
• Implication based on idea Premise less true than consequence

  mu(x -> y) = min(1, 1+mu(y)-mu(x))

[edit] Relevance Logic

• Nonclassical inferences, nonmonotonic reasoning
• Skip bottom and top (neutral) element laws, add complement law: a <= b then not(b) <= not(a)
• Resulting structure: DeMorgan Algebra
• Does not satisfy in general Boolean laws
• One of these laws added and we get Boolean algebra, classical logic

[edit] Intuitionism

• Change negation, introduce law: not(phi) = (phi -> bottom_element)
• Intuition: A proof for not(phi) is a proof for transforming phi to the bottom element
• phi or not phi is not a tautology
• Only constructive proofs
• Algebraic structure: Heyteng Algebra
  • A Heyting Algebra is a bounded distributive lattice such that for all a and b there is a greatest x such that: a∧x≤b.
  • Implication in a Heyting algebra: z≤x⇒y iff z∧x≤y

[edit] Boolean Algebra

• Algebraic structure corresponding to propositional logic
• If a <= b, then the supremum of a and b equals b
• A distributive lattice that has a complement operation and a top and a bottom element
• If a <= b, then: not b <= not a

[edit] Clause form: Disjunction of literals

[edit] Horn clause: At most one positive literal

[edit] Resolution calculus

• Resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic.
• Iteratively applying the resolution rule in a suitable way allows for telling whether a propositional formula is satisfiable and for proving that a first-order formula is unsatisfiable.

[edit] Semantics of first-order logic

• Interpretation function I: Maps terms to universe/domain and formulas to truth values

  A homomorphism

• Model: M is a model for formula phi if interpretation of formula with respect to structure M = < U, I> results in truth value true

  Interpretation that maps all formulas to true

• Validity: If every structure M = < U, I> is a model for phi, we call phi valid
• Satisfiability: If there is a model M = < U, I> for phi, we call phi satisfiable
• If for every unsatisfiable formula the negative can be proven, then a calculus is complete

[edit] Tense logic

• Operators: Fp, Pp, Hp, Gp (was the case, will be the case etc)
• Model: Strict partially ordered time line
• Not all models linear time line
• Allens tense logic: 7 basic relations (overlaps etc)
• Points or intervalls, both ok

[edit] Space logic

• RCC 5, RCC 8
  • Based on concept of a region
  • Describes relations of regions
  • Motion corresponds to transitions
  • Cannot be used to specify directions on a 2D plane
  • Under/before/left of cannot be specified
  • Generalization of Allens tense logic relations
  • RCC 8: {DC, EC, PO, TPP, NTPP, TPPI, NTPPI}
  • RCC 5: Some collapsed to discrede, proper part, proper part inverse
  • RCC 7: RCC 8 without partial overlap
• Simple & Double Cross Calculus

[edit] Reiters default logic

• Can model contradictions
• Nonmonotonous
• Default theory is a pair <W, delta>
• W: Strict world description
• delta: Set of defaults, revisable
• Interpretation of inference rule: If γ is known and if there is no evidence that θ might be false, then τ can be derived.
• Justification is based on something similar to the closed world assumption: if ¬θ cannot be derived from W, then assume that θ holds.

[edit] Planning

[edit] Deductive planning: Situation calculus

• Plan construction by resolution
• Extension of FOL
• Connections to modal logic
• Idea: Prove logically that a set of goals follows from an initial state given operator definitions (axioms).
• Perform the proof in a constructive way.
• No CWA
• Frame axioms necessary that specify invariants, to allow prove of conjunctions of literals

[edit] State-based: STRIPS

• Applies resolution
• State descriptions are conjunctions of positive ground literals with domain objects (constants)
• CWA
• Operator: Precondition + Effect
• Instantiated operators: Actions

[edit] Classic problems

• Frame problem: Unchanged things
• Qualification problem: Preconditions
• Ramification problem: Indirect effects

[edit] Machine learning

[edit] Bayesian learning

• Maximum a posteriori lerner
• argmax_{h} P(D|h)
• Naive Bayes: Conditionally independent features

[edit] Decision trees

• Inner nodes = attributes
• arcs: values
• leaf nodes: categories
• ID3: top-down, breadth-first, greedy

[edit] Computability

[edit] Ackermann

• ack(0, y) = y + 1
• ack(x+1, 0) = ack(x, 1)
• ack(x+1, y+1) = ack(x, ack(x+1, y))

[edit] Cognitive Architectures

[edit] SOAR

• SOAR = State, Operator And Result
• Cognitive architecture according to Newells Cognitive Bands
• Components
  • Long-term memory

    productions (condtions + actions) store preferences for working memory elements

    conditions match on all current goals/operators/... in context

    actions may only add elements to preference memory

  • Preference memory

    decides which elements get into decision cycle

    elaboration cycle: working memory updated according to preferences

    decision cycle: new context object selected according to preferences

  • Working memory

    attribute-value elements

    context stack, each connected to a goal

    gpals point to higher goalsm

    modification of context in decision cycle

[edit] ACT-R

• Declarative (types, slots) + procedural knowledge (if, then)

[edit] Subsumption architecture

• No explicit knowledge representation
• Reflexive
• Bottom-up
• Distributed behaviors
• Layered architecture
• Levels: Reactive, deliberate, meta
• Towers: Perception, processing, action