chương 1 Hạng tử (term): hằng, biến hay biểu thức hàm. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 18 trình logic.1 mô tả một số khái niệm tương đương trong cơ sở dữ liệu và lập trình logic. Khái niệm cơ sở dữ liệu Khái niệm lập trình logic tên quan hệ p ký hiệu vị từ p thuộc tính của quan hệ p đối số của vị từ p Bản ghi <a1, a2, … an> tri thức nền p(a1, a2, … an) quan hệ p là một tập các bản ghi vị từ p được định nghĩa mở rộng bởi một tập tri thức nền Bảng 2. Các thuật ngữ cơ sở dữ liệu và lập trình logic tương đương Các khái niệm khác trong học quy nạp (inductive concept learning) [18]: Định nghĩa 2.
Cho tri thức nền B, một giả thuyết H và tập mẫu E. Một mệnh đề c H được gọi là phủ (coverage) mẫu e E trên tập tri thức nền B nếu c B ⊨ e. Theo đó, một mệnh đề c được gọi là phủ một vùng trong không gian mẫu nếu như nó phủ tất cả các mẫu có thể thuộc vùng đó. Cho tri thức nền B, một giả thuyết H và tập mẫu E.
Giả thuyết H được gọi là phủ mẫu e E đối với tri thức nền B nếu B H ⊨ e, hay covers(B, H, e) = true nếu B H ⊨ e Định nghĩa 2. Cho tri thức nền B, một giả thuyết H và tập mẫu E. Một hàm phủ của giả thuyết H đối với tri thức nền B trên tập E được định nghĩa bởi covers(B, H, E)={e E |B H ⊨e } Định nghĩa 2. Một giả thuyết H được gọi là toàn vẹn đối với một tập mẫu E và tri thức nền B nếu như nó phủ hết tất cả các mẫu khẳng định trong E, hay covers(B, H, E+) = E+.
Một giả thuyết H được gọi là nhất quán đối với tập mẫu E và tri thức nền B nếu như nó không phủ một mẫu phủ định nào, covers(B, H, E-) = LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Lập trình logic quy nạp Tri thức nền (background knowledge) đóng một vai trò quan trọng trong học quan hệ khi nhiệm vụ được đặt ra là phải tìm từ các mẫu đã cho một quan hệ chưa biết hay quan hệ cần suy diễn theo ngữ nghĩa dựa trên các quan hệ có được từ tri thức nền. Nếu như ngôn ngữ được sử dụng trong học quan hệ là ngôn ngữ của lập trình logic thì quá trình học được gọi là lập trình logic quy nạp [42,43; 18]. Trong các hệ thống ILP, tập mẫu huấn luyện, tập tri thức nền và giả thuyết quy nạp cần học đều được biểu diễn dưới dạng chương trình logic.
Ví dụ một hệ thống ILP có thể học các luật về quan hệ con gái (quan hệ mục tiêu) dựa vào một tập các mẫu khẳng định và phủ định về quan hệ con gái và một tập các sự kiện (fact) - tri thức nền về các quan hệ khác như quan hệ cha mẹ, giới tính của các thành viên trong một gia đình xác định như sau : Ví dụ 2.1 Tập mẫu huấn luyện khẳng định: daughter(mary,ann) daughter(eve,tom) Tập mẫu huấn luyện phủ định: daughter(tom,ann) daughter(eve,ann) Tri thức nền Parent(ann, mary) Parent(ann, tom) Parent(tom, eve) Parent(tom, ian) Female(ann) Female(mary) Female(eve) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 20 ann mary tom eve ian Hình 2. Mô tả tri thức nền trong ví dụ về gia đình Luật có thể được học: Daughter(x,y) female(x), parent(y, x) Một định nghĩa cơ bản của ILP có thể được mô tả như sau ([18], [42], [43]): Cho: Tập mẫu huấn luyện E bao gồm tập mẫu khẳng định E+ và tập mẫu phủ định E- là các tri thức về vị từ p (quan hệ đích p) Một ngôn ngữ L mô tả các giới hạn hình thức trên định nghĩa của vị từ p Tập tri thức nền B định nghĩa các vị từ qi (khác p) mà có thể sử dụng trong việc mô tả p Cần tìm: Một giả thuyết H cho p, được biểu diễn trong L, thỏa mãn tính toàn vẹn và nhất quán với tập mẫu E trên tri thức nền B - e E+: H U B ⊨ e (toàn vẹn) - e E-: H U B ⊭ e (nhất quán) LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Tìm kiếm trong không gian giả thuyết 2. Xây dựng không gian giả thuyết Trong không gian mệnh đề, số lượng mẫu cần tìm kiếm là lớn và trong trường hợp không gian mẫu quan hệ, số lượng mẫu còn lớn hơn nhiều và điều cần thiết là phải giới hạn không gian tìm kiếm mẫu bằng việc cung cấp các thông tin giới hạn.
Các thông tin giới hạn này sẽ miêu tả chi tiết các quan hệ nào liên quan đến mẫu, các quan hệ làm thế nào để kết nối với nhau, cú pháp mà mẫu phải tuân theo… Và các thông tin đặc tả này thường được biết đến dưới thuật ngữ “declarative bias”. Một giới hạn ngôn ngữ L (language bias) giới hạn các dạng của mệnh đề có thể được xây dựng dựa trên các điều kiện của vị từ , hàm hay các hằng ngôn ngữ. Để giới hạn không gian tìm kiếm, L trong mỗi một hệ thống ILP có thể là một vài dạng giới hạn của chương trình logic như chỉ chứa các mệnh đề không chứa biểu thức hàm (function-free program clause) như trong FOIL [51]. Để tìm kiếm trong không gian mệnh đề một cách hiệu quả, cần chỉ ra được cấu trúc của không gian, ví dụ trên một thứ tự nào đó.
Sau đây là 2 định nghĩa quan trọng trong việc xây dựng cấu trúc không gian tìm kiếm. (Substitution) [37] Một phép thế θ = {X1 / t1, ………., Xk / tk } là sự thay thế các biến bởi các hạng tử. Kết quả của một phép thế θ trên một hạng tử, atom hay mệnh đề là một hạng tử, atom hay mệnh đề Fθ nhận được bởi thay thế tất cả các biến Xi bởi các hạng tử ti. (θ-subsumption) [37] Cho c và c’ là hai mệnh đề chương trình.
Mệnh đề c được gọi là bao hàm-θ c’ (θ-subsume) nếu tồn tại một phép thế θ, thỏa mãn cθ c’. Hai mệnh đề c và d được gọi là “θ-subsumption” tương đương nếu c bao hàm-θ d và d bao hàm-θ c. Một mệnh đề được gọi là tối thiểu nếu nó không thể θ subsumption tương đương bất kỳ tập con nào của nó. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Cho c là mệnh đề c = daughter(X,Y) parent(Y,X) Với một phép thế θ = {X/mary, Y/ann} áp dụng trên c bằng cách áp dụng θ trên các literal: cθ = daughter(mary, ann) parent(ann, mary) Ví dụ 2.1, mệnh đề c trong ví dụ 2.2 có thể được xem như một tập mệnh đề {daughter(X,Y), parent(Y,X)} Theo đó, một mệnh đề c bao hàm-θ c’ nếu như có một phép thế θ có thể áp dụng trên c sao cho mọi literal xuất hiện trong mệnh đề kết quả đều xuất hiện trong c’.
Ví dụ mệnh đề c bao hàm-θ mệnh đề c’ với c’ = daughter(X,Y) parent(Y,X), female(X) dưới phép thế θ = vì tập {daughter(X,Y), parent(Y,X)} là một tập con của {daughter(X,Y), parent(Y,X), female(X)} hay mệnh đề c bao hàm-θ mệnh đề c’’ với c’’=daughter(mary,ann)female(mary),parent(ann, mary) dưới phép thế θ = {X/mary, Y/ann} Định nghĩa 2. [18] Mệnh đề c được gọi là tổng quát ít nhất như mệnh đề c’ (c <= c’) nếu c bao hàm-θ c’. Mệnh đề c được gọi là tổng quát hơn c’ (c < c’) nếu c <= c’ và không có c’ <= c. Trong trường hợp c < c’, ta nói c’ là một đặc biệt hóa (specialization/ refinement) của c và c gọi là một tổng quát hóa của c’ [18].
Và mệnh đề đặc biệt hóa thường được xem xét bởi một hệ thống ILP là mệnh đề đặc biệt hóa nhỏ nhất (tổng quát nhất) của một mệnh đề cho trước. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 23 Có hai đặc tính quan trọng của θ- subsumption Nếu c bao hàm-θ c’ thì c thỏa c’ , c ⊨ c’. Chiều ngược lại không phải lúc nào cũng đúng. Quan hệ <= giới thiệu một dàn (lattice) trên tập các mệnh đề tối thiểu.
Điều này có nghĩa với bất kỳ hai mệnh đề có ít nhất một biên trên nhỏ nhất (least upper bound - lub) và một biên dưới lớn nhất (greatest lower bound-glb). Cả lub và glb đều là duy nhất trên các tương đương của θ- subsumption. Mệnh đề tối thiểu là biểu diễn nhỏ nhất trong lớp các mệnh đề tương đương được định nghĩa bởi θ- subsumption. Ví dụ: mệnh đề daughter((X,Y) parent(Y,X) , parent (W,V) và mệnh đề daughter(X,Y) parent(Y,X) là bao hàm-θ lẫn nhau và theo đó nó tương đương.
Trong đó mệnh đề sau là tối thiểu, mệnh đề trước không là tối thiểu. Đặc tính thứ hai của θ- subsumption dẫn đến định nghĩa Định nghĩa 2.12 (least general generalization) [18] Tổng quát hóa tối thiểu của 2 mệnh đề tối thiểu c và c’, được ký hiệu bởi lgg(c, c’) là biên trên nhỏ nhất của c và c’ trong mặt θ- subsumption. Mệnh đề c được gọi là tổng quát ít nhất như c’ trên tập lý thuyết nền B nếu B U {c} ⊨ c’. Trong ILP khái niệm θ-subsumption là rất quan trọng với các lý do sau: Cung cấp một phương pháp cơ bản để sắp thứ tự cho các giả thuyết, theo đó xây dựng cấu trúc cho không gian giả thuyết Có thể được sử dụng nhằm cắt xén trong không gian tìm kiếm - Khi khái quát hóa (tổng quát hóa) c thành c’, c’ < c, mọi mẫu huấn luyện được giải thích/phủ bởi c sẽ được giải thích bởi c’ (vì nếu có B U {c} ⊨ e thì cũng có B U {c’} ⊨ e).
Đặc tính này được sử dụng để cắt bớt không gian tìm kiếm khi e là một mẫu huấn luyện phủ định: nếu c là không nhất quán (có phủ một mẫu huấn luyện) thì tất cả các LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 24 tổng quát hóa của nó cũng sẽ là không nhất quán. Theo đó, việc xây dựng các tổng quát hóa của c là không cần thiết. - Khi đặc biệt hóa c thành c’, c < c’, một mẫu không được phủ bởi c sẽ không được phủ bởi bất kỳ một đặc biệt hóa nào của c. Đặc tính này được sử dụng nhằm cắt xén các mệnh đề đặc biệt hóa của một mệnh đề khi mệnh đề đó không phủ một mẫu huấn luyện khẳng định – nếu một mệnh đề không phủ một mẫu khẳng định thì mọi đặc biệt hóa của nó cũng sẽ không phủ mẫu đó.
Và việc xây dựng các đặc biệt hóa là không cần thiết. Khái niệm θ-subsumption cũng là cơ sở cho hai kỹ thuật tìm kiếm trong ILP: Kỹ thuật tìm kiếm từ dưới lên. Kỹ thuật tìm kiếm từ trên xuống.