A Risk Minimization Framework for Information Retrieval
Transkript
A Risk Minimization Framework for Information Retrieval
Bilgisayar Bilimlerinin Kuramsal Akış Temelleri • Matematiksel İspatlar “UBİ 501: Discrete Math and Its Application to Computer Science” • İspat Yöntemleri ve Stratejileri Ders - 2 • Küme Teorisi (Set Theory) İlker Kocabaş Bornova - İzmir – Giriş – Küme işlemleri – Vs…. İspatlar Tanımlar İspatlar Teorem İspat Yöntemleri E.Ü Uluslararası Bilgisayar Enstitüsü • • • Teorem: (İng. Theorem) • Doğrudan İspat (İng. Direct Proof) – P Q önermesinin doğruluğu ispat edilir – Doğru olduğu kanıtlanmış ifade veya önerme Aksiyom: (İng. Axiom) • P doğru kabul edilir • Adım adım çıkarsamalar yapılır. • Sonuç Q doğru bulunursa önerme doğru olmaktadır. – Öncül/hipotez: önceden kabul edilmiş ifadeler İspat: (İng. Proof) – Problem: “Eğer tam sayı n bir tek sayı ise, n2 tek sayıdır.” teoreminin dorudan ispatını gösteriniz? – Teoremin doğruluğunu gösteren “geçerli argüman” • Tanım: n tek sayı ise n=2k+1 ve çift ise n=2k olarak ifade edilebilir. n,k Tam sayılar. • Doğal Sonuç: (İng. Corollary) • Konjektür: (İng. Conjecture) – İspat edilmiş önceki bir teoremden doğrudan kanıtlanan teorem – Doğru gibi görünen fakat kanıtlanmamış önermeler • Dolaylı İspat : (İng. İndirect Proof) – Hipotezlerle başlayıp, sonuç ile bitmeyen ispat yöntemleri 1 İspatlar Teorem İspat Yöntemleri Dolaylı İspat : (İng. İndirect Proof) • Zıtlık ile İspat: (İng. Proof by Contraposition) • P Q Q P • “Q P” doğru olduğunun ispatı • Q doğru kabul edilir ve çıkarsama ile P önermesinin doğru olduğu İspatlar Teorem İspat Yöntemleri • bulunur. • Problem: “Tam sayı n için; Eğer 3n+2 tek sayı ise, n tek sayıdır.” • P: “3n+2 tek sayıdır” • Q: “n tek sayıdır.” • İfadelerin Çelişki ile İspatı: (İng. Proof by Contradiction) • • • P P F P (Q Q) “ P” = T ,doğru kabul edilecek Eğer bir çelişki sonucuna varılırsa (Q Q) = F olur. • • P (Q Q) ise T F = F olur. Bu önerme yanlış ise P = F ; yani P = T olması sonucunu doğurur. Problem: “2 irrasyonel bir sayıdır.” İspatlar Teorem İspat Yöntemleri Dolaylı İspat : (İng. İndirect Proof) • İspatlar Teorem İspat Yöntemleri • Koşullu İfadelerin Çelişki ile İspatı: • • P R (P R) F (P R) (Q Q) “ R” = T ,doğru kabul edilecek • Eğer bir çelişki sonucuna varılırsa (Q Q) = F olur. • • (P R) (Q Q) ise T F = F olur. Bu önerme yanlış ise R= F ; yani P = T olması sonucunu doğurur. • Problem: “Tam sayı n için; Eğer 3n+2 tek sayı ise, n tek sayıdır.” • İki koşullu ifadelerin ispatı • Tembel ispat: (İng. Vacuous Proof) • PQ • “P” = F ise P Q = T Apaçık ispat: (İng. Trivial Proof) • PQ • “Q” = T olarak ispat edilirse P Q = T • • Örnek: R(n): Eğer P:“a ≥ b” ise Q:“an ≥ bn “ R (n=0) için Q = T ve R(n) = T – P ↔ R (P R) (R P) 2 İspatlar İspat Stratejileri • Tüm olası durumlar tek bir argümanla ifade edilemediği durumlar vardır. • P = P1 ˅ P2 ˅ ….. ˅ Pn • • P Q (P1 ˅ P2 ˅ ….. ˅ Pn) Q (P1 Q) (P1 Q) ………….. (Pn Q) İspatlar İspat Stratejileri • Varoluş İspatları: (İng. Existance Proofs) • x P(x) ifadelerinin ispatı • Yapıcı Varoluş İspatı: (İng. Constructive Exhaustive Proof) • P(a)‟yı doğru yapan a gibi bir elemanın bulunması • Bütün İspat: (İng. Exhaustive Proof) • Problem: Eğer n beşten küçük pozitif bir tam sayı ise (n+1)3 ≥ 3n • Problem: “Eğer n tam sayı ise, n2 ≥ n.” İspatlar İspat Stratejileri Varoluş İspatları: (İng. Existance Proofs) • x P(x) ifadelerinin ispatı • • Çözüm: 1729 : (10,9) ve (12,1) Durumlar ile ispat : (İng. Proof by Cases) • • • Problem: x x = (a)3 + (b)3 x = (c)3 + (d)3 ; a, b, c, d farklı pozitif tamsayılar. Yapıcı olmayan Varoluş İspatı : (İng. Unconstructive Exhaustive Proof) • P(a)‟yı doğru yapan a gibi bir eleman bulunmadan ispat • Problem: x y (Eğer x ve y irrasyonel sayılar ise xy rasyonel sayıdır.) • Çözüm: • x,y için (2, 2) alınacak olursa (2 irrasyonel ispat edildi) • xy = 2 2 olur; Eğer bu sayı rasyonelse önerme doğrudur. • Eğer rasyonel değilse: x,y için (2 2,2) alınacak olursa xy = 2 2. 2 =2 rasyoneldir. Küme Teorisi Referans Evreni • Referans Evreni (İng. Universe of Reference) – Kümelerin içerdikleri elemanlarla tanımlanmış olmalarına rağmen bu elemanlar gelişigüzel olamaz. – Belirli bir Referans Evreni gerekir! – Yoksa, kendine referanstan kaynaklanan paradokslar oluşabilir. • Örnek : Russel’ın Paradoksu 3 Küme Teorisi Russel’ın Paradoksu Küme Teorisi Russel’ın Paradoksu • S= t [ t t] 1. S S: • – İddia : Böyle bir küme var olamaz. 2. S S – İspat : Böyle bir küme var ise, • 1. S S 2. S S Küme Teorisi Russel’ın Paradoksu • Bir küme belirli koşullarla tanımlanmış ise var olması gerekmektedir. Bir kümenin boş olması halinde de küme vardır. – Örnek: Konuşan ördekler kümesi, bu şart sağlanamazdır ve küme boş kümedir (). • Kümenin var oluşunu garanti etmek için referans evrenini (U) sabitlemek gerekir. – Soru: Kendini işaret (referans) etmeyen bir U var mıdır? S kendini eleman olarak içeriyor. S’nin elemanları kendilerini içeremiyecekleri için S S olmalıdır. Bu çelişkiden ötürü bu durum olamaz. • S kendini eleman olarak içermiyor. S’nin elemanları kendilerini içeremiyorlar ise S S olmalıdır. Bu durum da başlangıç varsayım ile çeliştiğinden ötürü bu durumda olamaz. Küme Teorisi Küme Oluşturma Gösterimi Parantezler arasında elemanları listelemek: – S = {-1, 0, -1, 5} • Açıklama ile tanımlamak: – Tüm doğal sayılar kümesi • Küme oluşturma gösterimi: – S = { f(x) | P(x) } , U. – U referans evrenindeki tüm f(x)’lerin kümesi öyle ki P(x) yüklemi doğru olmaktadır. 17 4 Küme Teorisi Küme Oluşturma Gösterimi • • • • • • Küme Teorisi Küme Oluşturma Gösterimi • • • S1: U = N. { x | y (y x ) } = ? S2: U = Z. { x | y (y x ) } = ? S3: U = Z. { x | y (y R y 2 = x )} = ? C2: U = Z. { x | y (y x ) } = { } C3: U = Z. { x | y (y R y 2 = x )} = { 0, 1, 2, 3, 4, … } = N S4: U = Z. { x | y (y R y 3 = x )} = ? S5: U = R. { |x | | x Z } = ? S6: U = R. { |x | } = ? 18 • C1: U = N. { x | y (y x ) } = { 0 } • • • – Birleşim ( İng. Union) - () C5: U = R. { |x | | x Z } = N C6: U = R. { |x | } = non-negative reals. L5 19 Küme Teorisi Venn Diyagramları Küme Teorisi İşlemler Küme teorisi işleçleri eski kümeleri kullanarak yeni kümeler oluşturmayı sağlar. Mantıksal işlemler gibi! Bunlar: C4: U = Z. { x | y (y R y 3 = x )} = Z • Venn diyagramları kümeleri ve küme işlemlerini göstermek için kullanışlı araçlardır. – Kesişim (İng. Intersection) - () – Fark (İng. Difference) - (-) – Tamamlayıcı (İng. Complement) - (―—‖) – Simmetrik Fark (İng. Symmetric Difference) - () • • Referans evrenini gösteren bir dikdörtgenin içinde çeşitli kümeler daireler ile gösterilir. A ve B gibi verilen iki küme için işlemlerle oluşturulan yeni kümeler: A B, A B, A-B, A B ve Ā L5 21 5 Birleşim Kesişim İki kümenin en az birindeki elemanlar kümesi Her iki kümede de bulunan elemanlar kümesi AB = { x | x A x B } AB = { x | x A x B } U U AB A A B L5 22 AB B L5 Ayrışık Kümeler 23 Ayrışık Birleşim Tanım: Eğer A ve B’nin ortak bir elemanları yok ise, bu kümeler ayrışık olarak adlandırılır, i.e. AB= . A ve B ayrışık olduğunda, ayrışık birleşim işleci iyi tanımlanmıştır. Birleşim sembolünün üzerindeki yuvarlak ayrışıklığı gösterir. U U A B A L5 B A 24 L5 B 25 6 Ayrışık Birleşim Küme Farkı Sonlu kümelerin ayrışık birleşiminin eleman sayısı (İng. cardinality) her bir kümenin eleman sayısının toplamıdır. İlk kümede bulunan fakat ikinci kümede bulunmayan elemanlar A-B = { x | x A x B } A B U A B A B A-B L5 26 L5 27 Tamamlayıcı Simetrik Fark İki kümeden sadece birinde bulunan elemanlar Kümede bulunmayan elemanlar (tekli işleç): AB = { x | x A x B } A = { x | x A } AB A L5 U U A B 28 L5 A 29 7 Küme Teorisi Küme Özdeşlikleri Tablo: Mantıksal Eşitlikler Eşitlikler PTP PFP PTT PFF PPP PPP (P) P • PQQP PQQP (P Q) R P (Q R) İsim Özdeşlik kanunları (Identity laws) Baskın olma kanunları (Domination laws) Denk güçlük kanunları (Idempotent laws) Çift Olumsuzlama kanunları (Double negation laws) Sıra bağımsız –değişim- kanunları (Commutative laws) Birleşim Kanunları (P Q) R P (Q R) (Associative laws) P (Q R) (P Q) (P R) Dağılım Kanunları P (Q R) (P Q) (P R) (Distributive laws) (P Q) P Q (P Q) P Q P (P Q) P P (P Q) P P P T P P F De Morgan kanunları • • • • • • Aslında, Mantıksal Özdeşlikler çeşitli küme işlem tanımlarını uygulayarak Küme Özdeşliklerini yaratır. – Örnek: (AB )C = A(B C ) “” “” “” “” “” “–” “F” “” “T” “U” Yutma kanunları (Absorption laws) Olumsuzlama Kanunları (Negation Laws) Küme Teorisi Küme Özdeşlikleri Aslında, Mantıksal Özdeşlikler çeşitli küme işlem tanımlarını uygulayarak Küme Özdeşliklerini yaratır. – Örnek: (AB )C = A(B C ) – İspat: Küme Teorisi Küme Özdeşlikleri Aslında, Mantıksal Özdeşlikler çeşitli küme işlem tanımlarını uygulayarak Küme Özdeşliklerini yaratır. – Örnek: (AB )C = A(B C ) – İspat: (AB )C » = {x | x A B x C } • Küme Teorisi Küme Özdeşlikleri (tanımdan) (AB )C » = {x | x A B x C } (tanımdan) » = {x | (x A x B ) x C } (tanımdan) 8 • Küme Teorisi Küme Özdeşlikleri Aslında, Mantıksal Özdeşlikler çeşitli küme işlem tanımlarını uygulayarak Küme Özdeşliklerini yaratır. • – Örnek: (AB )C = A(B C ) – İspat: • – İspat: (AB )C » = {x | x A B x C } (Tanımdan) » = {x | x A B x C } (Tanımdan) » = {x | (x A x B ) x C } (Tanımdan) » = {x | (x A x B ) x C } (Tanımdan) » = {x | x A ( x B x C ) } (Mantıksal Birl.) » = {x | x A ( x B x C ) } (Mantıksal Birl.) » = {x | x A x B C ) } (Tanımdan) Küme Teorisi Venn ile Küme Özdeşlikleri Aslında, Mantıksal Özdeşlikler çeşitli küme işlem tanımlarını uygulayarak Küme Özdeşliklerini yaratır. – Örnek: (AB )C = A(B C ) • Aslında, Mantıksal Özdeşlikler çeşitli küme işlem tanımlarını uygulayarak Küme Özdeşliklerini yaratır. – Örnek: (AB )C = A(B C ) (AB )C Küme Teorisi Küme Özdeşlikleri – İspat: Küme Teorisi Küme Özdeşlikleri • Venn diyagramı çizilerek bu özdeşlikleri anlamak çoğunlukla daha kolaydır. – Örnek: DeMorgan‟ın birinci kanunu (AB )C » = {x | x A B x C } (Tanımdan) » = {x | (x A x B ) x C } (Tanımdan) » = {x | x A ( x B x C ) } (Mantıksal Birl.) » = {x | x A x B C ) } (Tanımdan) » = A(B C ) (Tanımdan) A B A B Diğer kanunlarda bu şekilde türetilir. 9 Görsel DeMorgan Görsel DeMorgan B: A: B: A: AB L5 : 38 39 Görsel DeMorgan Görsel DeMorgan B: A: A: B: AB : A B : 40 41 10 Gösel DeMorgan Visual DeMorgan A: B: A: B: A: B: A: B: A B : 42 43 Küme Teorisi Bit Dizinleri olarak Kümeler Gösel DeMorgan • A B Eğer referans evrenini sıralar isek, kümeleri bit dizinleri biçiminde gösterebiliriz. – Örnek: U = {boğa, domuz, ceylan, aslan} – = U = {aslan, boğa, ceylan, domuz} (sıralı hali) • U‟nun alt kümeleri 4 uzunluğundaki bit dizini ile gösterilebilir!! • Soru: „0101‟ ile hangi küme gösterilmektedir? A B 44 11 Küme Teorisi Bit Dizinleri olarak Kümeler • Eğer referans evrenini sıralar isek, kümeleri bit dizinleri biçiminde gösterebiliriz. – Örnek: U = {boğa, domuz, ceylan, aslan} – U = {aslan, boğa, ceylan, domuz} (sıralı hali) • U‟nun alt kümeleri 4 uzunluğundaki bit dizini ile gösterilebilir!! Küme Teorisi Bit Dizinleri olarak Kümeler • Eğer referans evrenini sıralar isek, kümeleri bit dizinleri biçiminde gösterebiliriz. – Böyle bir gösterimde, küme teorisi işleçleri mantıksal bit dizini işleçleri haline gelir. – Örnek: {boğa} {aslan, boğa, domuz} • Soru: „0101‟ ile hangi küme gösterilmektedir? » 0100 1101 • Cevap: {boğa, domuz} » 1010 = {aslan, domuz} 12