[Artificial Intelligence] Knowledge Representation

Knowledge Representation

Knowledge based system

Graphical Representation of Knowledge

Inference

• (토요일 && 학점_A) ▶ 영화구경
• (중간고사_최상 && 기말고사_최상 ) ▶ 학점 A

• (토요일 && 기말고사_최상) ▶ 영화구경?

Knowledge Representation

• Knowledge : Facts, Procedural rules, Heuristic rules
• Facts : always true
  • Integrated circuit has power pin and GND(Ground) pin.
  • Boeing 747 can fly safely by three engines.
• Procedural rules: rules that describe a sequence of causal statements .
  • If we apply ‘1’ for every input of AND gate , the ouput of the gate becomes ‘1’ .
  • The higher voltage of DC motor is, the faster RPM is.
• Heuristic rules: not always true, true in most cases.
  • If the headlight beam of the car is not bright, voltage of battery is low.
  • If there is a linear element of which brightness changes rapidly, it is an edge of an object .

Logic

• Knowledge representation based on formal logic

• Formal logic
  • Easy to understand knowledge representation due to familiarity of formal logic system
  • Can adopt logical reasoning method Well developed deductive inference algorithm
  • Propositional Logic, Predicate Logic

• Ambiguous knowledge: Fuzzy Logic

Propositional Logic (명제 논리)

• Proposition(statement): a sentence that is either true or false.
  • ex) ‘The color of Tom’s car is black’,
  • ‘Tom’s car’,
  • ‘7+5’
• Capital letters of the alphabet, such as P, S, are used to represent propositions
• Statements are combined by connectives to become a compound statement.
• Implication : conveys the meaning that the truth of A implies or leads to the truth of B. The compound statement is denoted by A → B.
  • SWITCH_ON && DOOR_OPEN → ALARM

Atoms: T,F, countably infinite set of strings ,that begin with a capital letter ($P, Q, R, P1, \dots$)

• Connectives: ∨(or), ∧(and), →(implies), ’(not)

Propositional Logic - Syntax**

• Syntax of Well Formed Formula (wff)
• Any atom is a wff: P, R, P3
• Literals : atoms , atoms with ʹ

Propositional Logic - Semantics**

• Interpretation: Associate atoms with propositions about world. BAT_OK => “The battery is charged”
• Under a given interpretation, each atom has a value-true or false
• Sensing feature x1 => Store x1 in knowledge base

[Exercise] The negation of well formed formula,

– A “Block is liftable” – B “Arm is moving” – C “Battery is charged”

① If Block is liftable, then arm is moving. A → B is equivalent to ~ A ∨ B ② The block is liftable or arm is moving. A ∨ B

Predicate Login (술어 논리)

Syntax

– Term

• Constant : specific objects in the domain ex) Taeyun, Jina
• Variable : objects in the domain can be represented using variables ex) x or y
• function : mapping the object in the domain to other objects
• father(x) : x ←T aeyun object, output : Taeyun’s father object
• n-place function times(4, plus(3, 6)) , fatherof(John) – predicate(술어) : describe objects’ property or relations among objects ON(A, B), CLEAR(A)

Interpretation

• Maps object constants into objects in the world
• N-ary function constant into n-ary function in the world
• N-ary relation into n-ary relation in the world

Quantification

• Every object has a certain property.
  • Clear(B1) && Clear(B2) && Clear(B3) && Clear(B4) …
• At least one object has a certain property

  • Clear(B1)

    Clear(B2)

    Clear(B3)

    Clear(B4) …

• Variable symbols
• Quantifier symbols

• Quantifier(한정사) – Existential quantifier (존재 한정사) : ∃
  • (∃x) On(x,B) There is a block on Block B.
  • (∃x) Greater_than(x,0) – Universal quantifier (전체 한정사) : ∀
  • (∀x) Man (Father(x)) Father is a man for all x
  • (∀x) Attends (x,(CS221 && CS157))

[Ex 4.2] (∃x ) Odd(x)

• true : if domain of x is a set of integers
• false : if domain of x is a set of imaginary numbers

---

[ex 4.4] write each statement as a predicate wff (the domain is whole world)

• D(x) is “x is a day”, M is “Monday”
• S(x) is “x is sunny”, T is “Tuesday”
• R(x) is “x is rainy”,

① All days are sunny. (∀x)(D(x)→S(x)) ② some days are not rainy. (∃x)[D(x)∧R(x)’] or [(∀x)(D(x)→R(x))]’ ③ Every day that is sunny is not rainy. (∀x)[D(x)∧S(x)→R(x)’] ④ Some days are sunny and rainy. (∃x)[D(x)∧S(x)∧R(x)] ⑤ No day is both sunny and rainy. (∀x)[D(x)→(S(x)∧R(x))’] or (∀x)[D(x)∧S(x)∧R(x)]’

Fuzzy Logic

Ref. Adaptive Pattern Recognition and Neural Networks,Yoh-Han Pao,Addison Wesley

• Fuzzy Logic
  • “physically active” : a vague or fuzzy quantity
  • Defining this quantity as a fuzzy set
  • Crisp set
    • A={1, 3, 5, 7}

    • A={x	x is integer, 3<x<7}

    • If the element $x_1$ belongs to the set A($x_1$ A ), the degree of membership is 1
    • Otherwise ($x_1$ A ) , 0.

---

• Membership Function : $\mu_{A^0}(x_i)$
  • $x_i$가 $A^0$ 집합에 속하는 정도

I. The grade of membership of x in $A^O$ II. The fuzzy set $A^O$ : a set of ordered pairs of and III. a continuous or discrete membership function

For example, among 10 objects {x1, x2, … x10}, a set of heavy objects, $A^O$

→ a discrete membership function

---

• A continuous membership function : defining a fuzzy set in terms of membership function

Fuzzy Arithmetic (Intersection)

• Product or intersection of two fuzzy sets
  • Membership function of the intersection

---

Fuzzy Arithmetic (Union)

1