Luận văn Hệ thống các độ đo gần đúng và lập luận xấp xỉ

-1- Lêi nãi ®Çu Nhu cÇu cña con ng−êi vÒ viÖc gi¶i quyÕt c¸c vÊn ®Ò thùc tÕ dùa trªn nhiÒu m« h×nh ngµy cµng phøc t¹p ®· gia t¨ng dÉn ®Õn sù cÇn thiÕt ph¶i thu thËp c¸c d÷ liÖu phøc t¹p. Ph©n tÝch kü l−ìng qu¸ tr×nh thùc tÕ thu thËp th«ng tin, chóng ta nhËn thÊy r»ng rÊt nhiÒu th«ng tin ®−îc thu thËp kh«ng ph¶i lµ nh÷ng sè liÖu chÝnh x¸c vµ râ rµng. TÝnh kh«ng chÝnh x¸c vµ ch−a râ rµng trong qu¸ tr×nh thu thËp th«ng tin xuÊt ph¸t tõ nhiÒu nguyªn nh©n kh¸c nhau: dông cô ®o kh«ng hoµn h¶o, hoÆc th«ng th−êng h¬n lµ nguån d÷ liÖu th«ng tin ®−îc thu thËp tõ mét hoÆc mét vµi c¸ nh©n mµ do ®ã th«ng tin lµ kh«ng chÝnh x¸c, kh«ng m¹ch l¹c vµ ch−a ®Çy ®ñ. §èi víi nh÷ng tr−êng hîp nh− thÕ, ph−¬ng ph¸p xö lý hoµn toµn t−îng tr−ng sÏ kh«ng ®¸p øng ®Çy ®ñ yªu cÇu cña viÖc xö lý th«ng tin. B¾t ®Çu tõ nh÷ng n¨m 1960 ®· h×nh thµnh vµ ph¸t triÓn c¸c khÝa c¹nh lý thuyÕt vµ kü thuËt liªn quan ®Õn vÊn ®Ò biÓu diÔn tÝnh kh«ng chÝnh x¸c vµ kh«ng ch¾c ch¾n. HiÖn nay, c¸c ph−¬ng ph¸p nghiªn cøu c¸c néi dung trªn ®©y ®· ®ãng gãp nh÷ng thµnh c«ng quan träng ®èi víi sù ph¸t triÓn cña khoa häc m¸y tÝnh. Kh«ng chØ n¶y sinh khã kh¨n khi mong muèn c¸c phÐp ®o ®−îc tiÕn hµnh mét c¸ch chÝnh x¸c, mµ thËm chÝ ngay c¶ trong nh÷ng t×nh huèng cã thÓ tiÕn hµnh ®−îc phÐp ®o th× kÕt qu¶ thu ®−îc l¹i Ýt h÷u Ých: hoÆc ý nghÜa sö dông thÊp hoÆc l¹i rÊt khã kh¨n khi diÔn gi¶i hay lµm s¸ng tá c¸c th«ng tin thu thËp ®−îc. Khã kh¨n t−¬ng tù còng x¶y ra khi tiÕn hµnh ph©n tÝch ho¹t ®éng cña mét hÖ thèng phøc t¹p hoÆc hÖ thèng ®a chiÒu (many-dimensional system). Trong nhiÒu t×nh huèng nh− thÕ viÖc ®−a ra mét ph−¬ng ph¸p chung ®Ó nhËn ®−îc th«ng tin h÷u Ých mét c¸ch kÞp thêi trë nªn cã ý nghÜa h¬n nhiÒu so víi viÖc t×m kiÕm mét ph−¬ng ph¸p qu¸ chi tiÕt vµ chÝnh x¸c. Khi ®é phøc t¹p cña hÖ thèng t¨ng lªn, kh¶ n¨ng x©y dùng nh÷ng ph¸t biÓu chÝnh x¸c vµ cã ý nghÜa vÒ ho¹t ®éng cña hÖ thèng sÏ gi¶m bít cho ®Õn khi ®¹t ®−îc mét - 2 - "ng−ìng" nµo ®ã, mµ trong ng−ìng ®ã, tÝnh chÝnh x¸c vµ tÝnh cã ý nghÜa trë nªn thèng nhÊt. Nguyªn lý c¬ b¶n cña sù kh«ng t−¬ng thÝch nh− ®· tr×nh bµy trªn ®©y phï hîp víi c¸ch con ng−êi lÜnh héi vµ suy luËn: chóng ta chñ yÕu sö dông c¸ch tr×nh bµy thùc tÕ mét c¸ch gi¶n l−îc, vµ v× vËy, viÖc tr×nh bµy nh− thÕ nhÊt ®Þnh lµ kh«ng chÝnh x¸c vµ chung chung theo suy nghÜ chñ quan cña mçi ng−êi. Nh− vËy, mét ph−¬ng ph¸p t èt cÇn ph¶i ®¹t ®−îc mét sù tho¶ hiÖp, trong ®ã, tr¸nh bÊt kú ®ßi hái sù chÝnh x¸c qu¸ møc còng nh− l¹m dông sù tïy høng (hay còng vËy, tÝnh kh«ng ch¾c ch¾n) mét c¸ch qu¸ møc. TÝnh kh«ng chÝnh x¸c thËm chÝ cßn ®−îc n¶y sinh do kh¶ n¨ng hiÓu biÕt cña c¸ nh©n mçi con ng−êi lµ bÞ giíi h¹n. Gi¶i tÝch kho¶ng vµ lý thuyÕt x¸c xuÊt lµ hai c¸ch tiÕp cËn truyÒn thèng ®Ó tr×nh bÇy th«ng tin kh«ng hoµn h¶o tuy nhiªn chóng l¹i kh«ng thÝch øng ®Ó gi¶i quyÕt nh÷ng vÊn ®Ò míi ®−îc n¶y sinh. Gi¶i tÝch kho¶ng ®−îc ¸p dông chØ trong t×nh huèng khi xö lý d÷ liÖu sè kh«ng ®óng. §èi víi th«ng tin kh«ng hoµn h¶o, lý thuyÕt x¸c suÊt ®−îc sö dông víi môc ®Ých ®−a ra mét khung mang tÝnh qui chuÈn vµ quan t©m ®Õn sù ph¸n quyÕt kh«ng ch¾c ch¾n. Lý thuyÕt kh¶ n¨ng ®−îc x©y dùng dùa trªn kh¸i niÖm tËp mê, vµ ®−îc Zadeh khëi sinh tõ nh÷ng n¨m 1960. Khi ¸p dông lý thuyÕt kh¶ n¨ng, mét ®èi t−îng cã thÓ ®−îc t−¬ng øng víi mét ph¹m trï ch¾c ch¾n mµ ®èi t−îng sÏ ®−îc ®¸nh gi¸ theo ph¹m trï ®ã. Khi møc ®é kh¶ n¨ng nhËn c¸c gi¸ trÞ hoÆc 0 hoÆc 1 th× sù tÝnh to¸n chÝnh x¸c trong lý thuyÕt kh¶ n¨ng trïng hîp víi gi¶i tÝch kho¶ng, trong ®ã th«ng tin kh«ng chÝnh x¸c ®−îc tr×nh bµy d−íi d¹ng tËp c¸c gi¸ trÞ cã thÓ (thay v× tËp c¸c gi¸ trÞ chÝnh x¸c). Khi nghiªn cøu vÒ lý thuyÕt kh¶ n¨ng, chóng ta quan t©m ®Õn mèi quan hÖ kÐp: mét mÆt, quan hÖ gi÷a lý thuyÕt kh¶ n¨ng vµ lý thuyÕt tËp hîp, vµ mÆt kh¸c, quan hÖ gi÷a lý thuyÕt kh¶ n¨ng vµ kh¸i niÖm ®é ®o. Trong c¸c nghiªn cøu lý thuyÕt kh¶ n¨ng, - 3 - tÝnh kh«ng chÝnh x¸c ®−îc tr×nh bµy d−íi d¹ng c¸c tËp mê vµ viÖc x¸c ®Þnh tÝnh kh«ng ch¾c ch¾n ®−îc th«ng qua viÖc x¸c ®Þnh cÆp ®é ®o kh¶ n¨ng vµ ®é ®o cÇn thiÕt. ViÖc nghiªn cøu c¸c ®é ®o trong c¸c hÖ thèng kh«ng hoµn h¶o ®−îc quan t©m ngay tõ thêi ®iÓm khëi ®Çu cña lÜnh vùc nghiªn cøu réng lín nµy cña Tin häc. Mçi mét m« h×nh míi vÒ c¸c hÖ thèng kh«ng hoµn h¶o th−êng g¾n víi mét líp ®é ®o nµo ®ã. §· cã rÊt nhiÒu c«ng tr×nh khoa häc nghiªn cøu vÒ c¸c ®é ®o trong c¸c hÖ thèng kh«ng hoµn h¶o ®−îc ®−a ra. HiÖn t¹i, vÊn ®Ò nghiªn cøu vÒ c¸c ®é ®o vÉn mang tÝnh thêi sù, liªn quan ®Õn nhiÒu lÜnh vùc kh¸c nhau trong Tin häc vµ ®Æc biÖt, liªn quan mËt thiÕt ®Õn lÜnh vùc khai ph¸ d÷ liÖu vµ t×m kiÕm tri thøc. LuËn v¨n "HÖ thèng c¸c ®é ®o gÇn ®óng vµ lËp luËn xÊp xØ" ®Þnh h−íng tíi c¸c néi dung vÒ ®é ®o trong hÖ thèng kh«ng hoµn h¶o, trong lËp luËn gÇn ®óng vµ t×m kiÕm tri thøc. Néi dung cña b¶n luËn v¨n ®−îc chia lµm 4 ch−¬ng: - Ch−¬ng 1 víi tiªu ®Ò "TËp mê vµ c¸c ®é ®o kh«ng chÝnh x¸c" tr×nh bÇy c¸c néi dung c¬ b¶n vÒ lý thuyÕt tËp mê, c¸c phÐp to¸n c¬ b¶n cña tËp mê, c¸c ®é ®o trong hÖ thèng kh«ng hoµn h¶o. C¸c ®é ®o ®−îc tr×nh bµy trong ch−¬ng nµy nh−: ®é ®o kh¶ n¨ng, ®é ®o cÇn thiÕt vµ c¸c mèi liªn hÖ gi÷a c¸c ®é ®o, gi÷a tËp mê vµ ®é ®o kh¶ n¨ng còng ®−îc xem xÐt. LuËn v¨n còng tr×nh bµy nh÷ng nÐt kh¸i qu¸t vÒ c¸c ph−¬ng ph¸p thùc tÕ x©y dùng hµm thµnh viªn, x©y dùng c¸c tËp mê tõ d÷ liÖu thèng kª. Mèi liªn hÖ gi÷a ph©n phèi kh¶ n¨ng vµ x¸c suÊt... còng ®−îc xem xÐt. ViÖc x©y dùng hµm thµnh viªn µG ®o møc ®é t−¬ng thÝch gi÷a gi¸ trÞ ®¸nh gi¸ c¸c ®èi t−îng vµ ý muèn cña ng−êi ra quyÕt ®Þnh ®−îc bµn luËn. §Ó ®¹t ®−îc môc tiªu chung cÇn kÕt hîp tõ nhiÒu tiªu chuÈn kh¸c nhau vµ dÉn ®Õn viÖc cÇn x©y dùng c¸c hµm tæ hîp c¸c tiªu chuÈn ®ã l¹i. - Ch−¬ng 2 cã tiªu ®Ò "C¸c ph−¬ng ph¸p lËp luËn xÊp xØ trong c¸c hÖ chuyªn gia" tr×nh bµy mét sè m« h×nh suy luËn gÇn ®óng trong c¸c hÖ chuyªn - 4 - gia. Dùa theo nÒn t¶ng lý thuyÕt c¬ b¶n ®−îc giíi thiÖu trong ch−¬ng 1, c¸c ®é ®o tin cËy, ®é ®o hîp lý ®−îc tr×nh bµy. Kh¸i niÖm vÒ mÖnh ®Ò kh«ng râ rµng vµ c¸ch −íc l−îng gi¸ trÞ ®óng ®¾n cña mét mÖnh ®Ò ®−îc xem xÐt t−¬ng ®èi kü l−ìng. C¸ch tiÕp cËn logic vµ tiÕp cËn hµm x©y dùng c¸c m« h×nh suy luËn trong hÖ chuyªn gia tõ c¸c tiÒn ®Ò kh«ng ch¾c ch¾n sö dông c¸c luËt Modus ponens vµ Modus tollens ®· ®−îc nghiªn cøu kh¸ c¬ b¶n trong ch−¬ng nµy. - "T×m kiÕm tri thøc vµ ®é ®o gÇn ®óng" lµ tiªu ®Ò cña ch−¬ng 3. Néi dung cña ch−¬ng nªu lªn quan ®iÓm c¸c ®é ®o gÇn ®óng còng lµ kÕt qu¶ cña khai ph¸ d÷ liÖu vµ t×m kiÕm tri thøc. C¸c néi dung c¬ b¶n cña t×m kiÕm tri thøc mµ mét trong nh÷ng tri thøc ®ã lµ c¸c ®é ®o trong lÜnh vùc lËp luËn gÇn ®óng ®· ®−îc tr×nh bµy. Mét sè ®é ®o liªn quan ®Õn lÜnh vùc lËp luËn xÊp xØ, ®Æc biÖt c¸c ®é ®o liªn quan ®Õn kh¸i niÖm tËp th« ®−îc hÖ thèng hãa. Gi¸ trÞ t×m ®−îc tõ c¸c ®é ®o nãi trªn cho phÐp ®−a ra mét sè ®¸nh gi¸ vÒ ®é tin cËy trong suy luËn gÇn ®óng. - Ch−¬ng 4 víi tiªu ®Ò "§Ò xuÊt mét ®é ®o gÇn ®óng vµ ¸p dông" lµ b−íc ph¸t triÓn néi dung cña ch−¬ng 3. §é ®o ®−îc ®Ò xuÊt tuy ch−a ®−îc ®¸nh gi¸ so s¸nh víi c¸c ®é ®o ë ch−¬ng 3 song ®é ®o ®ã vÉn cã ý nghÜa trong mét líp m« h×nh kh«ng qu¸ h¹n hÑp. LuËn ¸n nµy hoµn thµnh ®−îc tr−íc hÕt lµ nhê cã sù gióp ®ì h−íng dÉn khoa häc tËn t×nh cña PTS. Hµ Quang Thôy, PTS. §ç V¨n Thµnh. V× vËy, víi tÊt c¶ tÊm lßng cña m×nh t«i xin bÇy tá lßng biÕt ¬n s©u s¾c cña m×nh tíi hai ng−êi thÇy ®· trùc tiÕp gióp ®ì h−íng dÉn t«i lµm luËn ¸n. Vµ t«i còng xin ch©n thµnh göi lêi c¸m ¬n cña m×nh tíi c¸c thÇy c« gi¸o khoa C«ng nghÖ th«ng tin, c¸c thÇy c« gi¸o thuéc Phßng §µo t¹o sau ®¹i häc-tr−êng §¹i häc Khoa häc tù nhiªn ®· t¹o mäi ®iÒu kiÖn gióp ®ì t«i trong suèt qu¸ tr×nh häc. Ngoµi ra t«i còng v« cïng c¶m ¬n mäi ng−êi trong gia ®×nh vµ c¸c b¹n bÌ th©n cña t«i, ®· cho t«i nhiÒu sù ®éng viªn khÝch lÖ ®Ó t«i cã thÓ hoµn thµnh luËn ¸n cña m×nh. - 5 - Víi tÊt c¶ mäi tËp thÓ vµ c¸ nh©n ®· gióp ®ì t«i ë trªn, t«i xin ch©n thµnh göi c¸m ¬n cña m×nh tíi tÊt c¶ mäi ng−êi. - 6 - Ch−¬ng 1 TËp mê vµ c¸c ®é ®o kh«ng chÝnh x¸c 1. ®é ®o kh¶ n¨ng vµ tËp mê Mét trong nh÷ng c¸ch tiÕp cËn kh«ng truyÒn thèng ®èi víi tÝnh kh«ng chÝnh x¸c vµ tÝnh kh«ng ch¾c ch¾n lµ c¸ch tiÕp cËn tíi phÐp ®o kh¶ n¨ng. Tr−íc hÕt, chóng ta xem xÐt c¸c kh¸i niÖm tÝnh kh«ng chÝnh x¸c vµ tÝnh kh«ng ch¾c ch¾n. 1.1. kh¸i niÖm vÒ tÝnh kh«ng chÝnh x¸c vµ tÝnh kh«ng ch¾c ch¾n TÝnh kh«ng chÝnh x¸c vµ tÝnh kh«ng ch¾c ch¾n cã thÓ ®−îc coi lµ hai khÝa c¹nh c¬ b¶n cña tÝnh chÊt x¸c thùc liªn quan ®Õn th«ng tin kh«ng hoµn h¶o. Mét môc (gãi) th«ng tin cã thÓ lµ ®−îc tr×nh bÇy nh− lµ mét mÖnh ®Ò logic vµ mét kho tri thøc ®−îc thu gom tõ c¸c môc th«ng tin tõ c¸c c¸ nh©n (hoÆc mét hÖ thèng m¸y tÝnh, hoÆc mét nhãm c¸ nh©n) vµ liªn quan ®Õn Ýt nhÊt mét vÊn ®Ò. Nh÷ng kh¼ng ®Þnh xuÊt hiÖn trong qu¸ tr×nh biÓu diÔn th«ng tin cã thÓ ®−îc gi¶i thÝch nh− lµ nh÷ng tËp con cña mét miÒn tham kh¶o. Mét mÖnh ®Ò còng cã thÓ ®−îc coi lµ mét x¸c nhËn liªn quan tíi sù xuÊt hiÖn cña mét sù kiÖn. Nh÷ng sù kiÖn nh− vËy cã thÓ tù ®−îc tr×nh bÇy nh− lµ nh÷ng tËp con cña miÒn tham kh¶o, v× vËy ®−îc gäi lµ sù kiÖn ch¾c ch¾n. Chóng ta cã ba c¸ch t−¬ng ®−¬ng ®Ó thu thËp c¸c môc th«ng tin: hoÆc dùa theo cÊu tróc (khÝa c¹nh logic), hoÆc dùa theo néi dung môc th«ng tin (khÝa c¹nh lý thuyÕt tËp), hoÆc dùa theo mèi liªn hÖ cña c¸c môc th«ng tin víi c¸c sù kiÖn thùc (khÝa c¹nh thùc tÕ). Theo quan ®iÓm thùc tÕ, mét môc th«ng tin ®−îc ®Þnh nghÜa lµ mét bé- bèn (thuéc tÝnh, ®èi t−îng, gi¸ trÞ, ®é tin cËy). - 7 - §èi t−îng (object) chØ ra ®−îc phÇn tö trong mét tËp tæng thÓ c¸c ®èi t−îng ®ang ®−îc chóng ta quan t©m, nghiªn cøu. Trong môc th«ng tin, thµnh phÇn ®èi t−îng ®−îc tr×nh bµy lµ tªn ®èi t−îng cô thÓ liªn quan ®Õn môc th«ng tin ®· cho. Thuéc tÝnh (attribute) ®−îc ®Ò cËp nh− mét hµm g¾n mét gi¸ trÞ (hoÆc mét tËp gi¸ trÞ) víi ®èi t−îng (object). Thuéc tÝnh th−êng liªn quan ®Õn mét "tÝnh chÊt" nµo ®ã cña c¸c ®èi t−îng ®ang ®−îc xem xÐt. Gi¸ trÞ (value) thuéc vÒ mét tËp con cña vïng tham kh¶o liªn quan víi thuéc tÝnh. Trong môc th«ng tin, thµnh phÇn gi¸ trÞ lµ mét phÇn tö (hoÆc mét tËp con c¸c phÇn tö) liªn quan ®Õn ®èi t−îng cô thÓ trong môc th«ng tin. §é tin cËy (confident) x¸c ®Þnh ®é x¸c thùc cña môc th«ng tin. Môc th«ng tin cã thÓ ®−îc më réng theo h−íng mçi mét thµnh phÇn trong ®ã cã thÓ lµ tæ hîp (mét vµi ®èi t−îng, mét vµi thuéc tÝnh, m¶ng n-tÝnh chÊt, c¸c møc ®é tin cËy kh¸c nhau). Trong ng÷ c¶nh nµy, chóng ta cã thÓ nhËn thÊy sù ph©n biÖt râ rµng kh¸i niÖm kh«ng chÝnh x¸c (imprecision) víi kh¸i niÖm kh«ng ch¾c ch¾n (uncertainty): tÝnh kh«ng chÝnh x¸c liªn quan tíi néi dung mét môc th«ng tin (thµnh phÇn gi¸ trÞ), cßn trong khi ®ã, tÝnh kh«ng ch¾c ch¾n liªn quan tíi tÝnh ®óng ®¾n cña môc th«ng tin, ®−îc hiÓu nh− lµ tÝnh x¸c thùc (thµnh phÇn tin cËy). * TÝnh kh«ng ch¾c ch¾n TÝnh kh«ng ch¾c ch¾n cña mét môc th«ng tin cã thÓ ®−îc ®¸nh gi¸ th«ng qua nh÷ng tõ nh−: “cã thÓ” (probable), “kh¶ n¨ng”, “cÇn thiÕt”, “hîp lý” hoÆc “®¸ng tin” mµ chóng ta mong muèn cè g¾ng g¸n cho chóng mét ý nghÜa chÝnh x¸c nµo ®ã. M« h×nh “cã thÓ” ®· tõng ®−îc nghiªn cøu réng r·i vµ nã liªn quan tíi hai ý nghÜa kh¸c nhau. ý nghÜa ®Çu tiªn lµ ý nghÜa vËt lý, rµng buéc tíi c¸c thÝ nghiÖm thèng kª, vµ liªn quan tíi tÇn sè xuÊt hiÖn cña mét sù - 8 - kiÖn. ý nghÜa thø 2 (epistemic) lµ: ë ®©y “cã thÓ” nãi ®Õn mét c¸ch ®¸nh gi¸ chñ quan nµo ®ã. §èi víi nh÷ng m« h×nh “kh¶ n¨ng” vµ “cÇn thiÕt”, ta nhÊn m¹nh tÝnh ®èi ngÉu cña chóng, nÕu mét sù kiÖn lµ cÇn thiÕt, th× sù kiÖn ®èi ngÉu lµ kh«ng cã kh¶ n¨ng. Tr¸i ng−îc víi kh¸i niÖm “cã thÓ” vµ “kh¶ n¨ng”, kh¸i niÖm “cÇn thiÕt” th−êng xuyªn ®−îc coi nh− lµ ph¹m trï “tÊt c¶ hoÆc kh«ng cã g×”. Nh−ng, còng gièng nh− “cã thÓ”, “kh¶ n¨ng” cã hai c¸ch gi¶i thÝch: vËt lý, vµ ”epistemic”. MÆt kh¸c “cÇn thiÕt” lµ mét kh¸i niÖm m¹nh h¬n nhiÒu, trong mçi ý nghÜa vËt lý hoÆc “epistemic” . Nh÷ng kh¸i niÖm “hîp lý” vµ “®¸ng tin” lµ ®Æc biÖt “epistemic” vµ liªn quan lÇn l−ît ®Õn c¸c kh¸i niÖm “kh¶ n¨ng” vµ “cÇn thiÕt”. Tõng kh¸i niÖm t−¬ng øng tíi mét c¸ch thøc suy luËn dùa trªn mét kho tri thøc ®−îc ®−a ra: bÊt cø ®iÒu g× mµ cã thÓ suy luËn tõ kho tri thøc lµ “®¸ng tin”; bÊt cø ®iÒu g× mµ kh«ng m©u thuÉn víi kho tri thøc lµ ”hîp lý” (khÝa c¹nh qui n¹p). D−íi ®©y lµ mét vµi vÝ dô vÒ nh÷ng mÖnh ®Ò kh«ng ch¾c ch¾n: - Cã thÓ Nam cao Ýt nhÊt 1.70 m. (®é cao, Nam, ≥1.7 m, cã thÓ) -X¸c suÊt l−îng m−a ngµy mai ®¹t10 mm lµ 0.5 (l−îng, m−a ngµy mai, 10 mm, x¸c suÊt = 0.5) * TÝnh kh«ng chÝnh x¸c Mét môc cña th«ng tin sÏ ®−îc gäi lµ chÝnh x¸c khi tËp con t−¬ng øng víi thµnh phÇn “gi¸ trÞ” kh«ng thÓ chia nhá thªm. Dùa trªn khÝa c¹nh cña th«ng tin ®ang ®−îc nhÊn m¹nh, chóng ta cã thÓ ph¸t biÓu mét mÖnh ®Ò s¬ cÊp, cña mét “singleton” (khÝa c¹nh lý thuyÕt tËp), hoÆc lµ mét sù kiÖn c¬ b¶n. TÝnh chÝnh x¸c dùa trªn c¸ch x¸c ®Þnh miÒn tham kh¶o. Trong mét sè tr−êng hîp, chóng ta cã thÓ ph¸t biÓu th«ng tin kh«ng chÝnh x¸c (imprecise). Trong ng«n ng÷ tù nhiªn cã nh÷ng tõ liªn quan tíi tÝnh kh«ng chÝnh x¸c, vÝ dô nh− “kh«ng râ rµng”, “mê”, “tæng qu¸t”. “Tæng qu¸t” còng lµ mét - 9 - d¹ng kh«ng chÝnh x¸c gièng víi qu¸ tr×nh trõu t−îng ho¸. Mét môc th«ng tin ®−îc gäi lµ tæng qu¸t nÕu nã chØ dÉn mét líp ®èi t−îng mµ c¸c ®èi t−îng ®ã cïng biÓu diÔn mét tÝnh chÊt chung. Nh−ng gi÷a tÝnh kh«ng râ rµng vµ tÝnh mê trong mét môc th«ng tin lµ kh«ng cã mét ng¨n c¸ch râ rµng khi xem xÐt tËp gi¸ trÞ ®−îc g¾n tíi c¸c ®èi t−îng liªn quan. 1.2 §é ®o tin t−ëng (confidence) Trong viÖc nghiªn cøu kho tri thøc kh«ng chÝnh x¸c vµ kh«ng ch¾c ch¾n, sù kiÖn lµ tËp con cña mét tËp tham kh¶o Ω cho tr−íc. TËp rçng ®−îc ®ång nhÊt víi sù kiÖn kh«ng cã kh¶ n¨ng. Gi¶ sö r»ng víi mét sù kiÖn A ⊆ Ω cho t−¬ng øng víi mét sè thùc g(A) ®−îc gäi lµ ®é tin t−ëng vÒ kh¶ n¨ng xuÊt hiÖn sù kiÖn A (qui −íc, g(A) t¨ng cïng víi sù t¨ng ®é tin cËy). Thùc tÕ g(A) ®−îc cung cÊp tõ ng−êi së h÷u kho tri thøc (hoÆc tõ mét thñ tôc xö lý d÷ liÖu ®−îc ¸p dông ®èi víi th«ng tin ®−îc l−u gi÷ trong bé nhí cña mét hÖ thèng m¸y tÝnh). H¬n n÷a, nÕu A lµ mét sù kiÖn ch¾c ch¾n th× g(A)=1, vµ nÕu A lµ mét sù kiÖn kh«ng cã kh¶ n¨ng, th× g(A)=0, ®Æc biÖt g(∅)=0 vµ g(Ω)=1 (1.1) Tuy nhiªn, g(A)=1 (hoÆc 0) kh«ng nhÊt thiÕt cã nghÜa lµ A lµ ch¾c ch¾n (hoÆc kh«ng cã kh¶ n¨ng). Tiªn ®Ò 1.1 (Tiªn ®Ò ®¬n ®iÖu yÕu): Gi¶ sö Ω lµ tËp tham kh¶o, víi mäi sù kiÖn A ⊆ Ω th× g(A) ®o ®é tin t−ëng kh¶ n¨ng xuÊt hiÖn sù kiÖn A. Khi ®ã: ∀A ⊆ B g(A) ≤ g(B) (1.2) §Þnh nghÜa 1.1 (®é ®o confident): - 10 - Gi¶ sö Ω lµ tËp tham kh¶o, víi mäi sù kiÖn A ⊆ Ω th× g(A) ®o ®é tin t−ëng kh¶ n¨ng xuÊt hiÖn sù kiÖn A. Khi ®ã nÕu g tho¶ m·n tiªn ®Ò ®¬n ®iÖu yÕu (tiªn ®Ò 1.1) th× g ®−îc gäi lµ ®é ®o confident. Tiªn ®Ò 1.2 (Tiªn ®Ò liªn tôc): Khi Ω lµ mét tËp tham kh¶o v« h¹n, khi ®ã víi mäi d·y lång nhau (An)n c¸c tËp, gi¶ sö: A0 ⊆ A1 ⊆ ... ⊆ An ⊆ ..., hoÆc A0 ⊇ A1 ⊇ ... An ⊇ ... th× ( ) ∞→n Aglim n = ( )⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ∞→n Alimg n (1.3) Mét ®é ®o confidence ®−îc coi lµ tho¶ m·n tiªn ®Ò liªn tôc nÕu nã tháa m·n Ýt nhÊt mét hoÆc hai kiÓu d·y t¨ng hoÆc gi¶m. 1.2.1. ®é ®o kh¶ n¨ng vµ ®é ®o cÇn thiÕt Nh÷ng bÊt ®¼ng thøc d−íi ®©y lµ hÖ qu¶ trùc tiÕp cña tiªn ®Ò ®¬n ®iÖu (1.2), vµ liªn quan tíi c¸c phÐp hîp (A∪B) vµ giao (A∩B) cña c¸c sù kiÖn: ∀A,B ⊆ Ω, g(A∪B) ≥ max (g(A), g(B)) g(A∩B) ≤ min (g(A), g(B)) Mét trong nh÷ng bµi to¸n ®Æt ra lµ t×m kiÕm mét c¸ch tù nhiªn, nh÷ng tr−êng hîp h¹n chÕ c¸c phÐp ®o confidence. Sau ®©y ta sÏ giíi thiÖu hai ®é ®o kh¶ n¨ng vµ ®é ®o cÇn thiÕt. *§é ®o kh¶ n¨ng: §Þnh nghÜa 1.2: Ký hiÖu Π lµ mét ®é ®o confident tho¶ m·n: ∀A,B, Π(A∪B) = max (Π(A), Π(B)) (1.4) Khi ®ã Π ®−îc gäi lµ ®é ®o kh¶ n¨ng, trong ®ã A, B kh«ng nhÊt thiÕt ph¶i lµ c¸c tËp rêi nhau. - 11 - DÔ dµng kiÓm tra nhËn thÊy r»ng nÕu (1.4) lµ ®óng ®èi víi mäi cÆp A, B rêi nhau (A∩B = ∅) th× nã ®óng cho mäi cÆp c¸c sù kiÖn. Tõ nhËn ®Þnh nµy, viÖc kiÓm tra mét ®é ®o cã lµ ®é ®o kh¶ n¨ng hay kh«ng chØ h¹n chÕ trªn c¸c cÆp tËp rêi nhau. Sù tån t¹i ®é ®o kh¶ n¨ng cã thÓ ®−îc kh¼ng ®Þnh tõ c¸ch x©y dùng mét ®é ®o kh¶ n¨ng nh− sau: - Gi¶ sö r»ng E ⊆ Ω lµ mét sù kiÖn ®−îc coi lµ ch¾c ch¾n. Mét hµm Π lÊy gi¸ trÞ trong {0, 1} vµ tho¶ m·n (1.4), lµ dÔ dµng ®−îc ®Þnh nghÜa nh− sau: Π(A) = 1 nÕu A∩E ≠ ∅ = 0 nÕu A∩E = ∅ HiÓn nhiªn Π ®−îc x©y dùng nh− vËy lµ mét ®é ®o kh¶ n¨ng TÝnh chÊt 1.1: NÕu A vµ A lµ hai sù kiÖn tr¸i ng−îc (A lµ phÇn bï cña A trong Ω), khi ®ã ta cã: max(Π(A), Π(A )) =1 TÝnh chÊt trªn cã thÓ ®−îc chøng minh dÔ dµng nh− sau: max(Π(A), Π(A )) = Π(A∪A ) = Π(Ω) = 1 §Þnh nghÜa 1.3: Gi¶ sö Ω lµ h÷u h¹n, khi ®ã mäi ®é ®o kh¶ n¨ng Π cã thÓ ®−îc ®Þnh nghÜa d−íi d¹ng theo gi¸ trÞ cña nã trªn c¸c phÇn tö cña Ω nh− sau: ∀A Π(A) = sup {π(ω)|ω ∈ A} (1.5) trong ®ã π(ω) = Π({ω}); π lµ mét ¸nh x¹ tõ Ω vµo [0, 1] ®−îc gäi lµ ph©n phèi kh¶ n¨ng. §Þnh nghÜa 1.4: π lµ mét ph©n phèi kh¶ n¨ng. Khi ®ã π ®−îc gäi lµ chuÈn ho¸ nÕu ∃ω, π(ω) = 1 (1.6) - 12 - v× Π(Ω) = 1. Trªn thùc tÕ, chóng ta lu«n lu«n b¾t ®Çu víi mét ph©n phèi kh¶ n¨ng vµ x©y dùng Π nhê (1.5). Nãi chung, ®é ®o kh¶ n¨ng kh«ng tho¶ m·n tiªn ®Ò liªn tôc (1.3) ®èi víi d·y c¸c tËp lång nhau gi¶m dÇn. TÝnh chÊt 1.2: NÕu Π lµ ®é ®o kh¶ n¨ng th× Π tho¶ m·n tÝnh chÊt sau: Π(A) + Π(A ) ≥ 1 *§é ®o cÇn thiÕt: T−¬ng tù, ta ®Þnh nghÜa ®é ®o cÇn thiÕt (d−íi ®©y ®−îc ký hiÖu bëi N) dùa theo quan hÖ sau: §Þnh nghÜa 1.5: Gi¶ sö N lµ mét ®é ®o confident tho¶ m·n: ∀A,B, N(A∩B) = min (N(A), N(B)) (1.7) Khi ®ã N ®−îc gäi lµ ®é ®o kh¶ n¨ng Mét hµm N víi nh÷ng gi¸ trÞ trong {0, 1} cã thÓ dÔ dµng ®−îc x©y dùng nhê mét sù kiÖn ch¾c ch¾n E nh− sau: N(A) = 1 nÕu E ⊆ A = 0 nÕu E ⊄ A Râ rµng lµ hµm N ®−îc x©y dùng nh− vËy lµ mét ®é ®o cÇn thiÕt. N(A) = 1 mang ý nghÜa A lµ ch¾c ch¾n. MÖnh ®Ò 1.1: Mét hµm tËp N tho¶ m·n (1.7) nÕu vµ chØ nÕu hµm Π ®−îc ®Þnh nghÜa bëi ∀A, Π(A) = 1 - N(A ) (1.8) lµ mét phÐp ®o kh¶ n¨ng. - 13 - Ph−¬ng tr×nh (1.8) tr×nh bµy sù biÓu diÔn sè mèi quan hÖ ®èi ngÉu gi÷a c¸c m« h×nh kh¶ n¨ng vµ m« h×nh cÇn thiÕt. Quan hÖ ®èi ngÉu cho phÐp chóng ta lu«n x©y dùng ®−îc mét hµm cÇn thiÕt tõ mét ph©n phèi kh¶ n¨ng th«ng qua biÓu thøc: N(A) = inf{1- π(ω)| ω ∉ A} (1.9) Ta cã mét sè tÝnh chÊt sau: TÝnh chÊt 1.3: min(N(A), N(A )) = N(A∩(A )) = N(∅) = 0 TÝnh chÊt 1.4: ∀A⊆Ω, Π(A) ≥ N(A) Chøng minh: ∀A⊆Ω, Π(A)=1-N(A )-N(A)+N(A) =(1-(N(A )+N(A)))+N(A) ≥ N(A) TÝnh chÊt 1.3 cho mét nhËn xÐt trùc gi¸c r»ng mét sù kiÖn lµ cã kh¶ n¨ng tr−íc khi lµ cÇn thiÕt. Ngoµi ra ta cßn cã c¸c quan hÖ sau: TÝnh chÊt 1.5: N(A) > 0 ⇒ Π(A) = 1 Chøng minh: N(A) > 0 ⇒ N(A ) = 0 (do min(N(A), N(A )) = 0) ⇒ Π(A) = 1- N(A ) = 1 T−¬ng tù ta cã: TÝnh chÊt 1.6: Π(A) < 1 ⇒ N(A) = 0 TÝnh chÊt 1.7: N(A) + N(A ) ≤ 1 1.2.2. kh¶ n¨ng vµ x¸c suÊt §Þnh nghÜa 1.6: Sù kiÖn xuÊt hiÖn th«ng qua viÖc quan s¸t th−êng xuyªn c¸c sù kiÖn c¬ b¶n nhËn ®−îc mét ®é ®o confidence P tho¶ m·n tiªn ®Ò céng mét c¸ch tù nhiªn: ∀A, ∀B, vµ A∩B = ∅, P(A∪B) = P(A) + P(B) (1.10) - 14 - Th× ®é ®o P ®−îc gäi lµ ®é ®o x¸c suÊt. MÖnh ®Ò 1.2: Gi¶ sö Ω h÷u h¹n ta cã ∑ Ω∈ω ω= )(p)A(P (1.11) trong ®ã p(ω) = P({ω}). §Þnh nghÜa 1.7: Gi¶ sö P lµ ®é ®o x¸c suÊt. Khi ®ã nÕu p tho¶ m·n p(ω) = P({ω}) th× p ®−îc gäi lµ chuÈn ho¸ nÕu tho¶ m·n: 1)(p = Ω∈ω ω∑ TÝnh chÊt 1.8: P lµ ®é ®o x¸c suÊt th×: P(A) + P(A ) = 1 (1.12) *Mét sè ®iÓm kh¸c nhau chÝnh yÕu gi÷a ®é ®o kh¶ n¨ng vµ ®é ®o x¸c suÊt: -X¸c suÊt cña mét sù kiÖn hoµn toµn x¸c ®Þnh x¸c suÊt cña sù kiÖn ®èi lËp. -Kh¶ n¨ng hoÆc sù cÇn thiÕt cña mét sù kiÖn, vµ cña sù kiÖn ®èi lËp, lµ ®−îc liªn kÕt yÕu. Do ®ã ®Ó ®Þnh râ ®Æc ®iÓm kh«ng ch¾c ch¾n cña mét sù kiÖn A chóng ta cÇn c¶ hai sè Π(A) vµ N(A). Trong m« h×nh ph¸n quyÕt kh«ng ch¾c ch¾n, ta mong muèn kh«ng lµm cøng nh¾c mèi quan hÖ gi÷a nh÷ng dÊu hiÖu chóng ta cã cña mét sù kiÖn. Trong t×nh huèng nµy kh¸i niÖm x¸c suÊt d−êng nh− lµ kÐm linh ®éng h¬n kh¸i niÖm kh¶ n¨ng. *Ph−¬ng ph¸p x©y dùng hµm ph©n phèi kh¶ n¨ng th«ng qua x¸c suÊt: Gi¶ sö tiªn ®Ò céng lµ ®−îc tho¶ m·n, ta cã thÓ x©y dùng ®−îc nh÷ng phÐp ®o kh¶ n¨ng vµ cÇn thiÕt nh− sau: - 15 - Gi¶ sö pE,,E,E 21 K lµ nh÷ng tËp con kh¸c nhau tõng ®«i mét (nh−ng cã thÓ giao nhau) cña Ω ( Ω lµ h÷u h¹n), lÇn l−ît cã c¸c x¸c suÊt )pE(m,),E(m),E(m 21 K tho¶ m·n: ∑ = = p 1i 1)iE(m (1.13) vµ ∀i, m( iE ) > 0 (1.14) C¸c sù kiÖn iE nh− trªn ®−îc gäi lµ c¸c phÇn tö träng t©m (focal element), ®−îc sö dông ®Ó x©y dùng m« h×nh kh«ng chÝnh x¸c. Khi ®ã x¸c suÊt cña mét sù kiÖn A sÏ lµ kh«ng chÝnh x¸c, vµ sÏ n»m trong mét kho¶ng [P*(A), P *(A)], ®−îc ®Þnh nghÜa nh− sau: ∑ ⊆ =∗ AiE )iE(m)A(P (1.15) ∑ ∅≠∩ =∗ AiE )iE(m)A(P (1.16) HiÓn nhiªn: ∀A, P*(A) = 1 - P*(A ) (1.17) Ta c«ng nhËn kÕt qu¶ r»ng c¸c hµm P* vµ P* tho¶ m·n lÇn l−ît c¸c tiªn ®Ò (1.4) vµ (1.7), khi ®ã P* lµ mét ®é ®o kh¶ n¨ng (hoÆc P* lµ mét ®é ®o cÇn thiÕt) nÕu vµ chØ nÕu c¸c iE t¹o thµnh mét d·y c¸c tËp bao nhau (nhê tiªn ®Ò yÕu (1.2)). §Æc biÖt, nÕu pE,EE 21 ⊂⊂ K , cã thÓ ®Þnh nghÜa mét ph©n phèi kh¶ n¨ng π nh− sau: ∀ω, π(ω) = { } ∑ = =ω∗ p ij )iE(m)(P nÕu ω ∈ iE ω∉ 1iE − - 16 - = 0 nÕu ω ∈ Ω - Ep (1.18) MÆt kh¸c, nÕu nh÷ng phÇn tö träng t©m lµ c¬ b¶n (v× thÕ kh«ng giao nhau), th×: ∀A, P*(A) = P*(A) = P(A) khi ®ã P lµ mét phÐp ®o x¸c suÊt. Tõ c¸c c«ng thøc (1.15) vµ (1.16) ta cã mét líp c¸c phÐp ®o P tho¶ m·n: P = {P| ∀A , N(A) ≤ P(A) ≤ Π(A)} (1.19) 1.3.TËp mê Kh¸i niÖm tËp mê cã thÓ ®−îc ®Þnh nghÜa theo c¸ch kh«ng liªn quan tíi c¸c ®é ®o kh«ng ch¾c ch¾n nhê viÖc thay ®æi x¸c ®Þnh møc ®é thµnh viªn (hµm thµnh viªn) thay cho ®Þnh nghÜa hµm ®Æc tr−ng. §©y lµ mét c¸ch nh×n nhËn logic. Tuy nhiªn, víi mét biÕn x vµ mét con tËp A cña miÒn tham kh¶o, tån t¹i mét ®é kh«ng ch¾c ch¾n trong tri thøc cña c¸ nh©n mçi ng−êi vÒ mèi quan hÖ x∈A. * TËp mê theo ®Þnh nghÜa trùc tiÕp §Þnh nghÜa 1.7: Mét tËp mê F lµ t−¬ng ®−¬ng víi cÆp (®−a ra mét tËp tham kh¶o Ω vµ mét ¸nh x¹, µF tõ Ω vµo [0, 1]. )(F ωµ , mµ ω∈Ω, lµ ®−îc diÔn gi¶i nh− lµ møc thµnh viªn cña ω trong tËp mê F. )(F ωµ biÓu diÔn møc t−¬ng thÝch cña ω víi tËp mê F . NÕu Ω = R (sè thùc) th× F lµ mét l−îng mê (fuzzy quantity). Khi )(F ωµ ∈ {0, 1}∀ω, F t−¬ng tù nh− mét tËp con b×nh th−êng cña Ω. Trong tr−êng hîp nµy F ®−îc gäi lµ mét tËp con crisp cña Ω. - 17 - Trong tr−êng hîp ng−îc l¹i, cã thÓ chän mét ng−ìng α∈]0, 1] vµ ®Þnh nghÜa tËp: αF = {ω∈Ω| )(F ωµ ≥ α } (1.20) §Þnh nghÜa 1.8: Mét tËp αF ®−îc gäi lµ nh¸t c¾t møc α (“α-level cut” hoÆc “α-cut”) NÕu αF lµ tËp ®−îc ®Þnh nghÜa bëi c«ng thøc (1.20). αF bao gåm tÊt c¶ nh÷ng phÇn tö cña Ω mµ t−¬ng thÝch víi A t¹i møc Ýt nhÊt lµ α. MÖnh ®Ò 1.3: Hä C(F) = { αF | α∈]0, 1]} lµ ®¬n ®iÖu: 0 < α ≤ β ≤ 1 ⇒ αF ⊇ βF (1.21) TÝnh ®¬n ®iÖu cho phÐp tr×nh bÇy F theo c¸ch thøc vÉn ¸p dông ®èi víi tËp truyÒn thèng vµ ta cã tÝnh chÊt sau: TÝnh chÊt 1.8: ∀ω, )(F ωµ = sup{α| ω ∈ αF } (1.22) Ng−îc l¹i, ta cã: MÖnh ®Ò 1.4: Mét hä ®¬n ®iÖu h÷u h¹n nh÷ng tËp { 1 Fα ,...., mFα } ®−îc g¸n cho nh÷ng träng sè iα tho¶ m·n (1.21), t¹o thµnh tËp c¸c nh¸t c¾t α cña mét tËp mê ®−îc ®Þnh bëi (1.22). §Þnh nghÜa 1.9: Nh¸t c¾t αF tho¶ m·n: αF ={ω∈Ω| )(F ωµ > α}, α∈[0, 1[ khi ®ã αF ®−îc gäi lµ nh¸t c¾t α m¹nh. - 18 - D−íi ®©y ta ®Þnh nghÜa hai d¹ng nh¸t c¾t αF d−íi ®©y th−êng ®−îc sö dông: §Þnh nghÜa 1.10: Nh¸t c¾t α møc 1 ký hiÖu F& tho¶ m·n: F& ={ω∈Ω| )(F ωµ =1} ®−îc gäi lµ mét core hoÆc peak. §Þnh nghÜa 1.11: Nh¸t c¾t α m¹nh cña F t¹i møc 0, ®−îc gäi lµ support, ®−îc ký hiÖu: S(F) = {ω∈Ω| )(F ωµ >0} * TËp mê theo c¸ch tiÕp cËn ®é ®o kh¶ n¨ng C¸ch nh×n thø hai lµ coi tËp mê nh− lµ “vÕt “ cña mét ®é ®o kh¶ n¨ng trªn mçi phÇn tö cña Ω. Mét tËp E ⊂ Ω cho t−¬ng øng mét ®é ®o kh¶ n¨ng, kÝ hiÖu lµ EΠ . Trong ®ã )A(EΠ =1 nÕu vµ chØ nÕu E ∩ A≠∅, vµ EΠ = 0 nÕu ng−îc l¹i. -Khi ®é ®o kh¶ n¨ng cã gi¸ trÞ trong kho¶ng ®¬n vÞ, cã thÓ coi ph©n phèi π cña nã nh− lµ mét hµm thµnh viªn cña mét tËp mê F. Ký hiÖu [ ]Ω1,0 lµ tËp tÊt c¶ c¸c tËp con mê cña Ω, ∀Π, ∃F∈[ ]Ω1,0 , ∀ω∈Ω, )(F ωµ = Π({ω})=π(ω) (1.23) - Ng−îc l¹i, tõ mét tËp mê ®−îc chuÈn ho¸: ∃ω, )(F ωµ =1 (1.24) cã thÓ nhËn ®−îc mét hµm kh¶ n¨ng. NÕu kh«ng nhÊt thiÕt b¾t buéc ®iÒu kiÖn Π(Ω)=1, th× tõ (1.5) ta cã: ∀F∈[ ]Ω1,0 , ∃Π, ∀ω∈Ω, Π({ω})=π(ω)= )(F ωµ (1.25) MÖnh ®Ò 1.5: - 19 - NÕu hµm kh¶ n¨ng ®−îc ®Þnh nghÜa th«ng qua mét träng sè x¸c suÊt m, th× nh÷ng phÇn tö träng t©m t¹o thµnh hä c¸c nh¸t c¾t α cña mét tËp mê. *Khi ®ã ta cã thÓ biÓu diÔn mét tËp mê th«ng qua x¸c suÊt nh− sau: Gi¶ sö r»ng {A1 ⊆.....⊆Ap} lµ c¸c phÇn tö träng t©m, th× ii FA α= hoÆc ∑ = =α p ij ji )A(m Nãi c¸ch kh¸c, ∀ω, ∑µ α∈ω α=ω i iF )F(m)(F (1.26) 1.4. Nh÷ng phÐp to¸n c¬ b¶n cña tËp mê PhÐp to¸n chøa: F ⊆ G ∀ω, )(F ωµ ≤ )(G ωµ (1.27) PhÐp to¸n