Mô tơ suy diễn (Inference Engine/ motor)

Động cơ, mô tơ hay máy suy diễn gồm 2 bộ phận chính:

Cơ chế suy diễn (Processor) gồm:

Cơ chế cổ điển (control unit):

(nhìn thấy cái nào không cần thiết thì loại, xác định cái nào được chọn trước)

Fact Precedence Graph (FPG) = (F, A)

Đỉnh : tập các sự kiện
Cung: (a,b)∈ size 12{ in } {}A ⇔ size 12{ dlrarrow } {}∃ size 12{ exists } {} r: left → size 12{ rightarrow } {}b ∈ size 12{ in } {}R ; a∈ size 12{ in } {}left

D:

a → b
b → c
c → e
c → d
d ⋀ e → f
b → h
f ⋀ h → g

Tập sự kiện:

F = { a, b, c, d, e, f, g, h} tách ra hai sự kiện:

F₁= { a, b, c} R₁ = { a → size 12{ rightarrow } {} b, b → size 12{ rightarrow } {} c}

F₂= { e, d, f, g, h} R₂ = { d ⋀ size 12{ and } {}e → size 12{ rightarrow } {}→ f, f ⋀ size 12{ and } {}h → size 12{ rightarrow } {} → g}

R₀ = {c → size 12{ rightarrow } {} e, c → size 12{ rightarrow } {} d, b → size 12{ rightarrow } {} h}

F₀ = {b, c, d, b, h}

Đây là một cách phân rã CSTT eval({F1, F2}) min

Mô hình star

Nếu phân rã dựa trên tập luật làm gốc thì dẫn đến full condition

Phân rã theo tập sự kiện → hình sao.

Suy diễn tiến, lùi (nhắc lại)

Suy diễn tiến ≡ tìm kiếm

a → b
b → c
c → e
c → d
d ⋀ e → f
b → h
f ⋀ h → g

GT = {a}

SUY DIỄN TIẾN	ĐỒ THỊ SUY DIỄN TIẾN
1. GT	1. Đỉnh gốc
2. Thời gian (SK đã chứng minh)	Nút
3. Thỏa	3. Cung
Thời gian → Thời gian {q}	Thời gian (→r ) thờigian
r: left → q	Thời gian = Thời gian ∪ {q}
r ∈ thỏa
4. Kết thúc	4. Lá
Thời gian ⊇ KL
Vết	Đường đi

Nếu SDT theo vét cạn → độ phức tạp tương ứng với quá trình tìm kiếm trên đồ thị SD.

C_{SD trên(vecan)} ≈ C_{tìm kiếmVC} = 0(BH)

B: Branching (độ phân nhánh) và H là chiều cao của cây

Suy diễn lùi ≡ tìm kiếm

⇒ size 12{ drarrow } {} Suy diễn lùi ≡ size 12{ equiv } {} tìm kiếm theo chiều sâu

C_SDlùi size 12{ approx } {} ≈ C_TKsâu = 0 (B H' size 12{ {} rSup { size 8{H rSup { size 6{'} } } } } {})

Trong trường hợp suy diễn lùi mà có chu trình :

* Prolog

r₁ A ⋀ B → c
r₂ A ⋀ C → B
r₃ B ⋀ C → A
r₄ a ⋀ hc → A
r₅ b ⋀ hc → A

GT = {a,b,hc}

KL = {c}

Chỉ số max:

Chọn hướng SD

B_T = max B_T(GT, KL, R)

Giả thiết:

ước lượng B_T
1. a ⋀ b ⋀ C → c
2. a ⋀ b ⋀ ma → c
3. a ⋀ b ⋀ mb → c
4. A ⋀ B → C
5. a ⋀ hc → B
6. b ⋀ hc → A
7. a ⋀ R → A
8. b ⋀ R → B
9. a ⋀ b →c P
10. a ⋀ b ⋀ c → P
11. a ⋀ b ⋀ c → m_c
12. a ⋀ ha → S
13. a ⋀ b ⋀ C → S
14. a ⋀ b ⋀ c ⋀ P → S
15. b ⋀ S → hb
16. S ⋀ p → r
F₁= {a, b, C} ⇒ size 12{ drarrow } {} R₁ = {r₁, r₂}

F₂ = {a, b, m_a} ⇒ size 12{ drarrow } {} R₂ = {r₂}

F₃ = {a, b, m_b} ⇒ size 12{ drarrow } {} R₃ = {r₃}

F₄ = {A, B} ⇒ size 12{ drarrow } {} R₄ = {r₄}

F₅= {a, h_c} ⇒ size 12{ drarrow } {} R₅= {r₅}

F₆ = {b, h_c} ⇒ size 12{ drarrow } {} R₆ = {r₆}

F₇ = {a, R} ⇒ size 12{ drarrow } {} R₇ = {r₇}

F₈ = {b,R} ⇒ size 12{ drarrow } {} R₈= {r₈}

F₉ = {a, b, c, p} ⇒ size 12{ drarrow } {} R₉ = {r₉, r₁₀, r₁₁, r₁₄}

F₁₀ = {a, h_a} ⇒ size 12{ drarrow } {} R₁₀ = {r₁₂}

F₁₁ = {b, S} ⇒ size 12{ drarrow } {} R₁₁ = {r₁₅}

F₁₂ = {S, p} ⇒ size 12{ drarrow } {} R₁₂= {r₁₆}

Ước lượng:

B Tm size 12{ {} rSub { size 8{T} } rSup { size 8{m} } } {} = max (2, 1, 4) = 4

BT size 12{ {B rSub { size 8{T} } } cSup { size 8{_} } } {}= 1612 size 12{ { {"16"} over {"12"} } } {} = 1,33

Ước lượng B_L
c có 3 luật

Luật (Meta Knowlegde)

If B_T > B_L Then chọn Lùi
If B_T < B_L Then chọn Tiến
If B_T > B_L #GT > # KL Then Chọn Lùi
#GT < KL Then Chọn Tiến
If user thích Then chọn

Chọn luật trong quá trình SD (Bài toán đụng độ luật - Rule Conflict)

Suy diễn tiến

Tại 1 thời điểm nào đó trong quá trình SD tiến chúng ta có thể dùng nhiều luật cùng một lúc:

TGian = {sự kiện f đã CM}; TG = {GT}

(Mở) THOẢ = {r: left → size 12{ rightarrow } {} q/ left size 12{ in } {} ∈ TGian} tập luật có thể áp dụng

(Đóng) VET = {r₁… r_k} tập những luật đã dùng

Khi # THOA size 12{ >= {}} {} 2 → size 12{ rightarrow } {} chọn r size 12{ in } {}∈thoả ?

→ size 12{ rightarrow } {} Độ phức tạp 0 (B^h)

→ size 12{ rightarrow } {} Để chọn theo mềm dẻo hàm h ̅(r) (heurestic)

→ size 12{ rightarrow } {} Max/ min (extremum)

Đánh giá:

# VET → min (càng ít càng tốt)
Dư → min

(*)

Gt = {a, b, R}, KL = {p}

Nên theo CS Min VET = {r₇, r₈, r₄, r₁, r₉, r₁₀, r₁₁} (2)

CS Max VET = {r₈, r₇, r₄, r₁₃, r₁₁} (1)

FIFO VET = {r₇ r₈r₄ r₁₁ r₁₃ r₉ r₁₀ r₁₁} (3)

LIFO VET = {r₈ r₇ r₄ r₁₃ r₁₅ r₁ r₉ r₁₀ r₁₁} (4)

Vậy có cách nào để Dư = 0 ?

Đồ thị FPG (Fact Precedence Graph)
Sử dụng để miêu tả mối tương quan giữa điều này với điều khác
(*)
- f g FPG thì f được dùng trực tiếp để suy ra G (r: left → g, f → left)
- Có đường đi P: f → …… → g thì được dùng gián tiếp để suy ra g.
#VET +Complexity hˆ size 12{ { hat {h}}} {} x m

Đồ thị RPG(Rule Precedence Graph)
RPG=(R,A)

Trong đó R: Tập các đỉnh

A: là tập các cạnh sao cho:

{}

Xây dựng đồ thị RPG cho ví dụ trên ta có:

R_KL={r:left → size 12{ rightarrow } {} q/q size 12{ in } {} ∈ KL} size 12{ in } {}∈ R

Xét ví dụ sau:

GT={a b R}, KL={r}

Suy diễn lùi

Đồ thị FPG
Tình huống đụng độ khi suy diễn lùi:

Goal= Tập những sự kiện cần chứng minh; ban đầu Goal=KL

Xét f → size 12{ rightarrow } {}Goal. Có nhiều luật suy ra f. Ta chọn luật bằng các thử sai và quay lui. Để tránh phải quay lui ta cần chọn luật như thế nào.

Nhắc lại các cách chọn có quay lui:

GT={a b R}

{S}_12,13,14← size 12{ leftarrow } {}{a b c p} ← size 12{ leftarrow } {}{a b m_b p} ← size 12{ leftarrow } {}…….

GT={a b R}, KL={S}
Đồ thị RPG

R_GT={r: left → size 12{ rightarrow } {}q/left size 12{ in } {} ∈GT}

GT={a b R} KL={S}

Hạn chế các ứng viên trong quá trình suy diễn

Suy diễn tiến

Giả sử xét tại một thời điểm trong quá trình suy diễn :

Suy diễn lùi

Xét 1 sự kiện thuộc Goal.

Kết luận: Nâng cao hiệu quả quá trình suy diễn

Luật r_i P₁ (…) size 12{ and } {} P₂ (…) size 12{ and } {} …… size 12{ and } {}P_n(…) → size 12{ rightarrow } {} q (…)

Các định lý hình học

Suy diễn tiến

Giả thiết:

Kết luận { SS (PS, BC)

B1' size 12{ {} rSub { size 8{1} } rSup { size 8{'} } } {}: TG₀ = GT
THOA = {(r₁, Φ size 12{Φ} {}₁), (r₁, Φ size 12{Φ} {}₂), (r₁, Φ size 12{Φ} {}₃), (r₁, Φ size 12{Φ} {}₄)}

Φ size 12{Φ} {}₁ = {A/X; B/Y; C/Z; P/U; Q/V}

Φ size 12{Φ} {}₂= {C/X; Q/Y; P/Z; E/U; J/V}

Φ size 12{Φ} {}₃ = ...

Φ size 12{Φ} {}₄ = ....

Chọn (r₁, Φ size 12{Φ} {}₁)

TG₁ = TG₀ ∪ size 12{ union } {} {SS (UV, YZ), Φ size 12{Φ} {}₁} = TG₀ size 12{ union } {} ∪ {SS (PQ, BC)}

B2' size 12{ {} rSub { size 8{2} } rSup { size 8{'} } } {}: TG₁ =
THOA = {(r₁, Φ size 12{Φ} {}₂), (r₁, Φ size 12{Φ} {}₃), (r₁, Φ size 12{Φ} {}₄)

….

Vấn đề: Làm như thế nào để xác định (r_i, Φ size 12{Φ} {}_i)

Suy diễn lùi

Nói chung suy diễn tiến và suy diễn lùi đều giống như nhau trong logic mệnh đề vì đều là quá trình hợp nhất (Unification)

Để rõ hơn ta hãy xét ví dụ sau:

Ta áp dụng thủ tục suy diễn lùi, nhưng co khó khăn là khi không tiếp tục được ta lại phải quay lui.Từ đây ta có thể đưa ra nhận xét sau:

Sự giống và khác nhau giữa suy diễn lùi của logic vị từ và suy diễn Prolog

Giống nhau: cả trong prolog cvà logic vị từ đều có phép hợp nhất và quá trình thử sai
Khác nhau: Tính chất trong prolog là chúng minh suy ra điều vô lý, còn suy diễn lùi là suy ra goal=0. Cơ chế của prolog là theo chỉ số min và đi từ trái sang phải. Còn trong logic vị từ thì có thể áp dụng hất mọi cacchs đi thông thường: Trai, phải và ngược lại hay là trên duới và ngược lại.

Mô tơ suy diễn (Inference Engine/ motor)

Động cơ, mô tơ hay máy suy diễn gồm 2 bộ phận chính: Cơ chế suy diễn (Processor) gồm: Cơ chế cổ điển (control unit): (nhìn thấy cái nào ...

Suy diễn tiến, lùi (nhắc lại)

Suy diễn tiến ≡ tìm kiếm

Suy diễn lùi ≡ tìm kiếm

Chọn hướng SD

Luật (Meta Knowlegde)

Chọn luật trong quá trình SD (Bài toán đụng độ luật - Rule Conflict)

Suy diễn tiến

Suy diễn lùi

Hạn chế các ứng viên trong quá trình suy diễn

Suy diễn tiến

Suy diễn lùi

Suy diễn tiến

Suy diễn lùi

Đăng ký nhận thông báo

HỖ TRỢ HỌC VIÊN

VỀ ZAIDAP

HỢP TÁC VÀ LIÊN KẾT

KẾT NỐI VỚI CHÚNG TÔI

TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI