IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics
IKI 30320: Sistem Cerdas Kuliah 15: Alternatives to FOL
Semantic Web Ringkasan
Ruli Manurung Fakultas Ilmu Komputer Universitas Indonesia
14 November 2007
Outline IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web
1
Semantic Networks
2
Description Logics
3
Semantic Web
4
Ringkasan
Ringkasan
Review IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Banyak riset AI → knowledge-based system/agent Representasi pengetahuan sbg. kalimat Kemampuan mengolah kalimat → “intelligent”
FOL cukup expressive Tetapi inference scr. umum intractable Banyak riset AI mencari “bahasa” alternatif. Terutama yg. berkaitan dengan Categories & Objects
Outline IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web
1
Semantic Networks
2
Description Logics
3
Semantic Web
4
Ringkasan
Ringkasan
Semantic Networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
“The Logic Of The FutureTM ” Existential Graphs (Charles Peirce, 1909)
Semantic Networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
“The Logic Of The FutureTM ” Existential Graphs (Charles Peirce, 1909) Semantic Nets (Quillian, 60an)
Semantic Networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
“The Logic Of The FutureTM ” Existential Graphs (Charles Peirce, 1909) Semantic Nets (Quillian, 60an) Conceptual Graphs (Sowa, 80an)
Semantic Networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
“The Logic Of The FutureTM ” Existential Graphs (Charles Peirce, 1909) Semantic Nets (Quillian, 60an) Conceptual Graphs (Sowa, 80an) Intinya: Notasi graph Node = object Edge = relation
Semantic Networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
“The Logic Of The FutureTM ” Existential Graphs (Charles Peirce, 1909) Semantic Nets (Quillian, 60an) Conceptual Graphs (Sowa, 80an) Intinya: Notasi graph Node = object Edge = relation
Bisa disimulasikan FOL!
Contoh semantic network IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Contoh semantic network IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Contoh semantic network IKI30320 Kuliah 15 14 Nov 2007
Mammals
Ruli Manurung Semantic Networks Description Logics
SubsetOf HasMother
Semantic Web
Legs
2
Persons
Ringkasan
Female Persons
SubsetOf
SubsetOf
MemberOf
Mary
Male Persons
MemberOf SisterOf
John
Legs
1
Sifat semantic networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Seru! Bandingkan dengan: ∀ x x ∈ Persons ⇒ [∀ y HasMother (x, y ) ⇒ y ∈ FemalePersons].
Sifat semantic networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Seru! Bandingkan dengan: ∀ x x ∈ Persons ⇒ [∀ y HasMother (x, y ) ⇒ y ∈ FemalePersons]. Ambigu: “Heli is_a dog” → Heli ∈ Dog “Dog is_a mammal” → Dog ⊆ Mammal
Sifat semantic networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Seru! Bandingkan dengan: ∀ x x ∈ Persons ⇒ [∀ y HasMother (x, y ) ⇒ y ∈ FemalePersons]. Ambigu: “Heli is_a dog” → Heli ∈ Dog “Dog is_a mammal” → Dog ⊆ Mammal Hanya bisa representasi relasi binary, kecuali dengan reification: Pergi(Anto, Depok , Bogor , Kemarin).
Sifat semantic networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Seru! Bandingkan dengan: ∀ x x ∈ Persons ⇒ [∀ y HasMother (x, y ) ⇒ y ∈ FemalePersons]. Ambigu: “Heli is_a dog” → Heli ∈ Dog “Dog is_a mammal” → Dog ⊆ Mammal Hanya bisa representasi relasi binary, kecuali dengan reification: Pergi(Anto, Depok , Bogor , Kemarin). menjadi Pergi(P). Pelaku(P, Anto). Asal(P, Depok ). Tujuan(P, Bogor ). Kapan(P, Kemarin).
Sifat semantic networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Seru! Bandingkan dengan: ∀ x x ∈ Persons ⇒ [∀ y HasMother (x, y ) ⇒ y ∈ FemalePersons]. Ambigu: “Heli is_a dog” → Heli ∈ Dog “Dog is_a mammal” → Dog ⊆ Mammal Hanya bisa representasi relasi binary, kecuali dengan reification: Pergi(Anto, Depok , Bogor , Kemarin). menjadi Pergi(P). Pelaku(P, Anto). Asal(P, Depok ). Tujuan(P, Bogor ). Kapan(P, Kemarin). Inheritance secara fleksibel: default reasoning + overriding (John = 1 leg), multiple inheritance (OOP?)
Sifat semantic networks IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Inference sangat cepat (inheritance,membership, dll.) Tidak se-expressive FOL: tidak ada negation, disjunction, function, quantifier, dll. Meskipun demikian, cukup banyak digunakan dalam AI. Contoh paling terkenal: WordNet.
Outline IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web
1
Semantic Networks
2
Description Logics
3
Semantic Web
4
Ringkasan
Ringkasan
FOL terlalu sulit? IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
+: FOL expressive, inference sound+complete -: FOL sulit dipahami, intractable
FOL terlalu sulit? IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
+: FOL expressive, inference sound+complete -: FOL sulit dipahami, intractable Description Logic (DL) adalah logic yang lebih sederhana Lebih mudah dipahami Inference lebih cepat (tractability)
FOL terlalu sulit? IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
+: FOL expressive, inference sound+complete -: FOL sulit dipahami, intractable Description Logic (DL) adalah logic yang lebih sederhana Lebih mudah dipahami Inference lebih cepat (tractability)
DL menitikberatkan struktur taksonomi (objects, categories) Semantic network yang “lebih diformalkan”
KB dalam DL IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
KB tentang domain D dalam Description Logic dibagi 2: TBox: kalimat Terminological - pengetahuan umum tentang D Mis: Anjing adalah sejenis mamalia, Anjing memiliki 4 kaki. ABox: kalimat Assertion - pengetahuan spesifik tentang D Mis: Heli adalah seekor anjing, Heli dimakan Bruno. TBox adalah tempat mendefinisikan konsep. ABox adalah tempat mendefinisikan instance. (Bisa) ada negation, quantifier, disjunction.
Contoh: FOL vs. DL IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung
“Bachelors are unmarried adult males” Semantic Networks Description Logics Semantic Web Ringkasan
DL: Bachelor = And(Unmarried, Adult, Male). FOL: ∀ x Bachelor (x) ⇔ Unmarried(x) ∧ Adult(x) ∧ Male(x).
Contoh: FOL vs. DL IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung
“Bachelors are unmarried adult males” Semantic Networks Description Logics Semantic Web Ringkasan
DL: Bachelor = And(Unmarried, Adult, Male). FOL: ∀ x Bachelor (x) ⇔ Unmarried(x) ∧ Adult(x) ∧ Male(x). “Pria yang memiliki sekurangnya 3 putra, semuanya pengangguran dan kawin dengan doktor, dan paling banyak 2 putri, semuanya profesor jurusan fisika atau kimia” DL: And(Man,AtLeast(3,Son),AtMost(2,Daughter), All(Son,And(Unemployed,Married,All(Spouse,Doctor))), All(Daughter,And(Professor,Fills(Department,Physics,Math)))). FOL: ???
Mengatasi kerancuan panah+lingkaran IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Apakah “artinya” kelinci --makan--> tanaman ?
Mengatasi kerancuan panah+lingkaran IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Apakah “artinya” kelinci --makan--> tanaman ? Kelinci hanya makan tanaman?
Mengatasi kerancuan panah+lingkaran IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Apakah “artinya” kelinci --makan--> tanaman ? Kelinci hanya makan tanaman? Kelinci bisa makan tanaman (dll.)?
Mengatasi kerancuan panah+lingkaran IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Apakah “artinya” kelinci --makan--> tanaman ? Kelinci hanya makan tanaman? Kelinci bisa makan tanaman (dll.)? Ada seekor kelinci spesifik yang hanya/bisa makan tanaman?
Mengatasi kerancuan panah+lingkaran IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Apakah “artinya” kelinci --makan--> tanaman ? Kelinci hanya makan tanaman? Kelinci bisa makan tanaman (dll.)? Ada seekor kelinci spesifik yang hanya/bisa makan tanaman? Ada beberapa ekor kelinci yang makan tanaman (yang lain makan rendang)?
Mengatasi kerancuan panah+lingkaran IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web
Apakah “artinya” kelinci --makan--> tanaman ? Kelinci hanya makan tanaman? Kelinci bisa makan tanaman (dll.)? Ada seekor kelinci spesifik yang hanya/bisa makan tanaman? Ada beberapa ekor kelinci yang makan tanaman (yang lain makan rendang)?
Ringkasan
Perlu representasi yang semantics-nya jelas, formal. DL → set theory (teori himpunan):
Mengatasi kerancuan panah+lingkaran IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web
Apakah “artinya” kelinci --makan--> tanaman ? Kelinci hanya makan tanaman? Kelinci bisa makan tanaman (dll.)? Ada seekor kelinci spesifik yang hanya/bisa makan tanaman? Ada beberapa ekor kelinci yang makan tanaman (yang lain makan rendang)?
Ringkasan
Perlu representasi yang semantics-nya jelas, formal. DL → set theory (teori himpunan): Domain → himpunan object
Mengatasi kerancuan panah+lingkaran IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web
Apakah “artinya” kelinci --makan--> tanaman ? Kelinci hanya makan tanaman? Kelinci bisa makan tanaman (dll.)? Ada seekor kelinci spesifik yang hanya/bisa makan tanaman? Ada beberapa ekor kelinci yang makan tanaman (yang lain makan rendang)?
Ringkasan
Perlu representasi yang semantics-nya jelas, formal. DL → set theory (teori himpunan): Domain → himpunan object Class/category → (sub)himpunan object
Mengatasi kerancuan panah+lingkaran IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web
Apakah “artinya” kelinci --makan--> tanaman ? Kelinci hanya makan tanaman? Kelinci bisa makan tanaman (dll.)? Ada seekor kelinci spesifik yang hanya/bisa makan tanaman? Ada beberapa ekor kelinci yang makan tanaman (yang lain makan rendang)?
Ringkasan
Perlu representasi yang semantics-nya jelas, formal. DL → set theory (teori himpunan): Domain → himpunan object Class/category → (sub)himpunan object Role/relation → himpunan pasangan object (dlm. DL, bisa ada ∃, ∀, n)
Inference pada DL IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Inference pada DL IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Subsumption: apakah category c1 adalah subset category c2 berdasarkan definisinya?
Inference pada DL IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Subsumption: apakah category c1 adalah subset category c2 berdasarkan definisinya? Classification: apakah object o adalah anggota category c berdasarkan definisinya?
Inference pada DL IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Subsumption: apakah category c1 adalah subset category c2 berdasarkan definisinya? Classification: apakah object o adalah anggota category c berdasarkan definisinya? Consistency: apakah definisi sebuah category c dapat dipenuhi (satisfiable)
Inference pada DL IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
Subsumption: apakah category c1 adalah subset category c2 berdasarkan definisinya? Classification: apakah object o adalah anggota category c berdasarkan definisinya? Consistency: apakah definisi sebuah category c dapat dipenuhi (satisfiable) Pada umumnya, cepat → inference dlm. waktu polynomial Contoh sistem DL: K L O NE, C LASSIC, K AON, R ACER, dll.
Outline IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web
1
Semantic Networks
2
Description Logics
3
Semantic Web
4
Ringkasan
Ringkasan
DL & Semantic Web IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web Ringkasan
DL menjadi dasar representation & inference pada Semantic Web. OWL Web Ontology Language: http://www.w3.org/TR/owl-features Ide dasar: Lengkapi data di Internet dengan metadata (RDF) Rancang ontology (OWL) http://protege.stanford.edu Inference dengan subsumption + classification
Contoh aplikasi: “Intelligent” searching Composable web services Semantic grid
Outline IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks Description Logics Semantic Web
1
Semantic Networks
2
Description Logics
3
Semantic Web
4
Ringkasan
Ringkasan
Ringkasan IKI30320 Kuliah 15 14 Nov 2007 Ruli Manurung Semantic Networks
Alternatif FOL yang lebih “enteng”
Description Logics
Gambar enak dilihat, tapi bisa ambigu!
Semantic Web Ringkasan
Description Logic: formal, efisien, fokus pada category + object Dasar dari inference Semantic Web (OWL) Representational trade-off antara expressiveness dan tractability