Bài giảng Tầng tri thức dựa luật và logic - Lê Thanh Hương

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

72
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Tầng tri thức dựa luật và logic" do Lê Thanh Hương biên soạn cung cấp cho người học các kiến thức: Biểu diễn tri thức, luật Horn, các biểu thức đơn, lập trình logic – logic programming, các đặc tính của DLP, lập trình logic, các biểu thức đơn,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tầng tri thức dựa luật và logic - Lê Thanh Hương

TẦNG TRI THỨC DỰA LUẬT VÀ LOGIC Hanoi University of Technology – Master 2006 2 Biểu diễn tri thức Luật Horn BDTT là cơ sở của các hệ thống thông minh Là tập con của First Order Logic Vai trò của ontology trong BDTT Biểu thức Horn là phép hợp của các biểu thức đơn với Để ể khai báo các tri thức về thế giới 1 giá trị khẳng định (∀) ¬B1 ∨ ¬B2 ∨ … ∨ ¬Bn ∨ H Ontology đưa khai báo vào các loại (khái niệm, vai trò, …) Tương đương với (∀) B1 ∧ B2 ∧ … ∧ Bn → H Luật và suy diễn Luật suy diễn cho phép suy ra các tri thức ẩn (procedural knowledge) từ các tri thức rõ (declarative knowledge) Luật cho phép diễn tả các ràng buộc giữa các đối tượng 3 4 1
Lập trình logic – logic programming Các biểu thức đơn (1) Các hằng số với các giá trị xác định Là mở rộng của logic Horn logic a, b, john,… ậ là kết hợp Luật ợp của các các biến với Các á biến bế Biến dương là biểu thức nguyên tử: p(x), q(x),... x, y,… Biến âm là phủ định của biểu thức nguyên tử: Các hàm trả về giá trị với các tham số nhất định not p(x), not q(x),... f(x), fatherOf(john),… not (negation-as-failure) ≠ ¬ Các hằng, biến, hàm (gọi là các thuật ngữ) Biến cơ sở là biến không có tham số Các vị từ liên kết các thuật ngữ p(x, p(x a), a) marriage(mary, marriage(mary john),… john) Luật Horn (H ::- B1,...,Bn) or (H ← B1 ∧... ∧ Bn) Nếu p là vị từ, t là thuật ngữ, khi đó p(t1, t2,…) là biểu H là biến dương thức đơn B1,...,Bn là các biến Nếu t1, t2 là thuật ngữ, khi đó t1 = t2 là biểu thức đơn f(x) = a, marc = fatherOf(john) 5 6 Lập trình logic (2) Các đặc tính của DLP Một sự kiện là 1 biểu thức nguyên tử (luật Tập con RDFS của DL cho phép các phát biểu sau: không có thân) Lớp C là lớp con của lớp D. Miền của thuộc tính P là lớp C person(john) Giới hạn phạm vi của thuộc tính P là lớp D. ĐÍch hoặc câu truy vấn là luật không có phần Thuộc tính P là thuộc tính con của thuộc tính Q đầu, biểu diễn bởi (?- B1,...,Bn) A là một giá trị của lớp C. ?- person(x) (a,b) là một giá trị của thuộc tính P. LP không có phủ định tương đương với tập con DLP có thể biểu diễn: của FOL (Horn Logic Programs) Sử dụng kết nối Intersection trong mô tả lớp Khai báo thuộc tính P là truyền ứng (Transitive). Datalog là tập con của LP Khai báo thuộc tính P là đối xứng (Symmetric). Không có ký hiệu hàm DLP có thể biểu diễn hầu hết các đặc tính của DL Không có phủ định Các vấn đề kỹ thuật trong LP: Xử lý tính bằng nhau (vd, tính duy nhất của tên) 7 8 2
Ví dụ Expressivity overlaps Các sự kiện về quan hệ mother(mary, john) father(marc, john) male(john) Luật về quan hệ parent(X,Y) :- mother(X,Y) parent(X,Y) :- father(X,Y) female(X) :- mother(X,Y) male(X) :- father(X,Y) Truy vấn ?- female(mary) ?- parent(x, john) 9 10 Kết hợp luật với ontology Khác biệt giữa DL và DLP DLs cho phép biểu diễn tri thức khai báo DLP là tập con của DL. LPs cho p phép p biểu diễn tri thức thủ tục ụ ggắn với Ví dụ của DL không biểu diễn một cách hoàn biểu diễn tri thức chỉnh hỉ h ttrong DLP DLP: DLP (Description Logic Programs) là cách đơn Khai báo lớp con của biểu thức liên kết lớp qua phép hợp: giản nhất để kết hợp DLs với logic Horn (Human ∩ Adult) ⊆ (Man ∪ Woman) Phần OWL có thể định nghĩa dưới dạng Horn Khai báo lớp con của biểu thức liên kết lớp Phần logic Horn có thể định nghĩa dưới dạng qua lượng từ tồn tại: OWL R di ⊆ ∃hasPart.Tuner Radio ∃h P t T Tại sao không? Vì: LP/Horn, và do đó DLP, không thể biểu diễn được 11 12 3
Khác biệt giữa LP và DLP DLP có thể làm gì DLP là tập con của Horn LP. Các luật LP trên các DL ontologies. ụ về Horn LP không Ví dụ g biểu diễn được ợ bằng g DLP: Dịch các luật LP sang DL ontologies và ngược lại Luật liên quan nhiều biến: Sử dụng các luật LP cho các phần của DL PotentialLoveInterestBetween(?X,?Y)← Man(?X) ∧ Woman(?Y). Tạo các ontologies trong LP Chuỗi (ngoài phép lan truyền đơn giản) để sinh giá Tạo các luật trong DL. trị thuộc tính. Dịch các kết luận LP sang DL InvolvedIn(?Company, ?Industry) Dịch các kết luận DL sang LP ← Subsidiary(?Company, y( p y, ?Unit)) ∧ AreaOf(?Unit, ( , ?Industry). y) Tại sao? Tính quyết định cuả DLs phụ thuộc chủ yếu vào thuộc tính của mô hình cây DL không dùng để biểu diễn nhiều hơn một biến 13 14 Ưu điểm của DLP Chuyển từ DL sang Horn logic (1) Mô hình hóa: Sử dụng DL hoặc luật (C rdfs:subClassOf D) C D ⇔ D(x) ← C(x) Cài đặt: ặ sử dụng ụ g cơ chế suyy luận ậ của DL hoặc ặ (Q rdfs:subPropertyOf P) hệ thống suy diễn dựa luật Q P ⇔ P(x, y) ← Q(x, y) Dịch các luật LP sang DL ontologies và ngược lại (P rdfs:range C) ∀P.C ⇔ C(y) ← P(x, y) Tạo các ontologies trong LP (hoặc luật trong DL) (P rdfs:domain C) Linh động, có thể sử dụng nhiều công cụ khác ∀P-.C ⇔ C(y) ← P(y, x) nhau (vd, khai thác các công cụ LP/DB để chạy (a rdf:type C) các ontology quy mô lớn) a:C ⇔ C(a) (a ( P b) Khả năng biểu diễn: OWL ontologies thường chỉ (a, b): P ⇔ P(a, b) dùng rất ít các phép biểu diễn ngoài DLP (C owl:equivalentClass D) C ≡ D ⇔ D(x) ← C(x); C(x) ← D(x) (Q owl:equivalentProperty P) Q ≡ P ⇔ P(x, y) ← Q(x, y); Q(x, y) ← P(x, y) 15 16 4
Chuyển từ DL sang Horn logic (2) Semantic Web Rule Language (Q owl:inverseOf P) Q P- ⇔ Q(y, x) ← P(x, y) (P rdf:type owl:TransitiveProperty) Semantic Web Rule Language (SWRL): P+ P ⇔ P(x, z) ← P(x, y) ∧ P(y, z) Kết hợp ợp ontologies g và luật: ậ owl:intersectionOf l i t ti Of C1 C2 D ⇔ D(x) ← C1(x) ∧ C2(x) Ontologies: OWL-DL C D1 D2 ⇔ D1(x) ← C(x); D2(x) ← C(x) Rules: RuleML owl:unionOf SWRL = OWL-DL + RuleML C1 C2 D ⇔ D(x) ← C1(x); D(x) ← C2(x) C D1 C2 ⇔ impossible translation OWL-DL: không có biến owl:allValuesFrom tương ứng với SHOIN(D) C ∀P.D ⇔ ((D(y)(y) ← P(x, ( y)) ← C(x) ( ) ∀P.C D ⇔ impossible translation RuleML: R l ML sử ử dụng d biến. biế owl:someValuesFrom C ∃P.D ⇔ impossible translation ∃P.C D ⇔ D(x) ← P(x, y) ∧ C(y) owl:complementOf (negation), owl:minCardinality, owl:maxCardinality không thể dịch được 17 18 RuleML Ví dụ của RuleML RuleML, ngôn ngữ datalog của mệnh đề Horn: 1 quan hệ n-ary (n= 0, 1, 2, … ) trong RuleML. 1. Datalog là tập con của Prolog: VD: A customer is gold if her purchasing has been minimum 200 dollars in the previous year. year Function-free: cách biểu diễn P(f(2),5) không hợp lệ head (unary relationship): A customer is gold. body (3-ary relationship): Her purchasing . . . 2. Mệnh đề Horn (hợp của các ký hiệu và có tối đa 1 ký hiệu dương), vd ¬p ∨ ¬ q ∨ . . . ∨ ¬ t ∨ u có thể viết thành, p ∧ q ∧ ldots ∧ t Æ u Chỉ có phép giao của các phần tử 19 20 5
Luật với nhiều phần tử Luật RuleML trong SWRL Luật với nhiều phép and trong thân: Chỉ có các quan hệ unary/binary The discount for a customer on a product is 5% if Các ví dụụ ở slide trước không gpphải là luật ậ the customer is gold and the product is seasonal. SWRL Các quan hệ n-ary relations được chuyển thành quan hệ nhị phân. Luật với nhiều phép and trong thân khá phổ biến. Vd The discount for a customer on a product is 5% if the customer is gold and the product is seasonal. 21 22 Cú pháp SWRL Cú pháp SWRL Các phần tử SWRL được định nghĩa như sau: Cú pháp luật SWRL: ( )| D(v) Atom ← C(i)| ( ) | R(I, ( , j) | U(I, ( , v)) | a ←b1, …,, bn trong g đó,, builtIn(p, v1, …, vn) | i = j | i ≠ j a : head (1 atom) bs: body (nhiều atom) C = Class D = Data type 1 CSTT SWRL (k) được định nghĩa như sau: R = Object Property U = Data type Property k = (∑,P) trong đó, i,j = Object variable names or Object individual ∑ = CSTT của SHOIN(D) names P = tập luật V1, …, vn = Data type variable names or Data type value names p = Built-in names 23 24 6
Ngữ nghĩa SWRL Ngữ nghĩa SWRL Cho I = (ΔI, ΔD, .I, .D) trong đó Bảng ràng buộc B(I) đối với các phần tử SWRL I=p phépp dịch ị ΔI = miền dịch đối tượng ΔD = miền dịch dữ liệu .I = hàm dịch đối tượng .D = hàm dịch kiểu dữ liệu ΔI ∩ ΔD = ∅, sao cho VIX Æ P(ΔI) VDX Æ P(ΔD) trong đó, VIX = biến đối tượng VDX = biến kiểu dữ liệu P = phép toán lực lượng 25 26 Ngữ nghĩa SWRL Ví dụ về SWRL Các phần tử SWRL trong phần trước Trong 1 định dạng bảng, các thuật ngữ SWRL (antecedent) thỏa nếu: như sau: Nó rỗng (đúng hiển nhiên) Hoặc mọi phần tử của nó thỏa 1 phần tử SWRL trong phần sau (consequent) Biến được xác định qua dấu ? trong luật thỏa nếu: Ví dụ: Nó rỗng FastComputer(?c) Å Computer(?c) ∧ Hoặc nó thỏa hasCPU(?c ?cpu) ∧ hasSpeed(?cpu, hasCPU(?c, hasSpeed(?cpu ?sp) ∧ 1 luật thỏa phép dịch I nếu HighSpeed(?sp) Mọi ràng buộc B(I) thỏa phần trước FastComputer(?c): thuật ngữ C(i) trong bảng B(I) thỏa phần sau hasCPU(?c, ?cpu): thuật ngữ R(i, j) trong bảng 27 28 7
Diễn tả luật không sử dụng SWRL Dịch luật từ SWRL sang DL Có thể diễn tả một số luật chỉ sử dụng DL: Số biến chung giữa phần trước và phần sau: VD: với luật ị Có thể dịch được ợ nếu: FastComputer(?c) Å Computer(?c) ∧ hasCPU(?c, 2 phần chung nhau 0 biến, nhưng có ít nhất 1 cá ?cpu) ∧ hasSpeed(?cpu, ?sp) ∧ HighSpeed(?sp) thể chung Luật chỉ sử dụng DL: 2 phần chung nhau 1 biến Computer ∩ ∃hasCPU. ∃hasSpeed.HighSpeed ⊆ Không dịch được nếu: FastComputer 2 phần chung nhau >= 2 biến Dịch luật từ SWRL sang DL, Phụ thuộc ộ vào à sốố biến ế dựa vào à các á biến ế chung giữa phần trước và phần sau 29 30 Quá trình dịch từ SWRL sang DL Dịch luật từ SWRL sang DL Phần trước và phần sau trở thành các truy vấn FastComputer(?c) Å Computer(?c) ∧ hasCPU(?c, giao ?cpu) ∧ hasSpeed(?cpu, ?sp) ∧ HighSpeed(?sp) Truy vấn kết quả được dịch thành diễn tả lớp 1. Phần trước và phần sau trở thành các truy vấn Sử dụng kỹ thuật rolling-up giao Phần trước trở thành lớp con của phần sau 1a. ?c: FastComputer 1b. ?c: Computer∧ (?c, ?cpu): hasCPU ∧ (?cpu, ?sp):hasSpeed ∧ ?sp:HighSpeed Các phép giao tạo ra đồ thị có hướng: Mỗi nút là 1 biến hoặc 1 tên Mỗi cạnh là 1 quan hệ 1 đồ thị truy vấn 31 32 8
Dịch luật từ SWRL sang DL Dịch luật từ SWRL sang DL 2. Sử dụng kỹ thuật rolling-up Lớp của biến đích ?c : là Computer Giao với lớp Computer ∩ Kết quả rolling-up : Mỗi cạnh ra được biểu diễn dưới dạng 1 lượng Computer ∩ ∃hasCPU.∃hasSpeed.HighSpeed từ tồn tại Lớp của biến đích ?c Cạnh được biểu diễn như các ràng buộc ?c : FastComputer dịch thành FastComputer Mỗi cạnh ra (?x, ?y) : R được dịch thành ∃R.Y 3. Làm phần trước trở thành lớp con của phần sau Computer Co pute ∩ ∃hasCPU.∃hasSpeed.HighSpeed asC U asSpeed g Speed ⊆ Y là ràng à buộc b ộ vềề tê tên lớp lớ ?y ? FastComputer ∃hasCPU.∃hasSpeed.HighSpeed 33 34 Luật SWRL không chuyển sang Luật SWRL không chuyển sang được được DL DL SWRL có thể biểu diễn một số luật mà DL Mặc dù không thể suy diễn hasUncle(Bob,Bill) từ không biểu diễn được hasParent(Bob,Mary) và hasBrother(Mary,Bill), VD: Quan hệ hasUncle có thể được dùng trực tiếp hasUncle(?nephew,?uncle) ÅhasParent(?nephew, hoặc gián tiếp ?parent) ∧ hasBrother(?parent,?uncle) VD: People whose uncles are all lawyers, Luật trên không thể dịch sang DL vì Sử dụng trực tiếp hasUncle: ∀hasUncle.Lawyer phần sau có 2 biến khác nhau Sử dụng gián tiếp hasUncle: ∀ hasParent. Việc sinh phép thế cho từng biến không đủ để ∀hasBrother.Lawyer giải quyết 35 36 9
SWRL’s XML syntax Ví dụ Family Family ontology Class Person x1 Cácá thuộc h ộ tính í h của ủ Person: hasParent, h hasBrother, h h x2 hasUncle Luật SWRL x2 hasParent(x1,x2) ∧ hasBrother(x2,x3) → x3 hasUncle(x1,x3) Astract syntax Implies( Antecedent(hasParent(I-variable(x1) I-variable(x2)) hasBrother(I- variable(x2) I-variable(x3))) x1 x3 Consequent(hasUncle(I-variable(x1) I-variable(x3))) ) 37 38 Further reading WRL’s RDF syntax “Combining Rules and Ontologies. A survey”, s Deliverable I3, REWERSE project, 2005. Combining OWL and RuleML: http://www.w3.org/Submission/SWRL/ B. N. Grosof, I. Horrocks, R. Volz, and S. Decker. Description logic programs: Combining SW logic programs with description logic. In Proc.