Dveˇ aplikace bayesovsky´ch sı´tı´? Jirˇ´ı Vomlel
[email protected] Laboratorˇ inteligentnı´ch systemu˚, Vysoka´ sˇkola ekonomicka´, Praha
Abstrakt V cˇla´nku prˇedstavujeme dveˇ modernı´ aplikace bayesovsky´ch sı´tı´ - adaptivnı´ testova´nı´ a technickou diagnostiku (angl. troubleshooting). Nejprve strucˇneˇ shrneme teoreticke´ za´klady a navrhneme obecny´ ra´mec pouzˇity´ prˇi vytva´rˇenı´ strategiı´ pomocı´ bayesovsky´ch sı´tı´. Na´sledneˇ popı´sˇeme aplikaci teorie prˇi adaptivnı´m testova´nı´ a v technicke´ diagnostice. Tento cˇla´nek vycha´zı´ ze zkusˇenostı´, ktere´ jsme zı´skali prˇi rˇesˇenı´ dvou projektu˚: - studentske´m semestra´lnı´m projektu beˇhem neˇhozˇ byl navrzˇen adaptivnı´ test znalostı´ zˇa´ku˚ rˇesˇ´ıcı´ch za´kladnı´ u´lohy se zlomky - a prˇi projektu SACSO, spolecˇne´m projektu firmy Hewlett-Packard a Aalborgske´ univerzity v Da´nsku, zameˇrˇene´m na diagnostiku slozˇity´ch elektro-mechanicky´ch zarˇ´ızenı´.
´ vod U
1
V te´to kapitole prˇedstavı´me bayesovske´ sı´teˇ a popı´sˇeme dveˇ za´kladnı´ u´lohy spolecˇne´ pro obeˇ aplikace popsane´ v tomto cˇla´nku: (1) vytva´rˇenı´ modelu bayesovske´ sı´teˇ a (2) pouzˇitı´ modelu pro hleda´nı´ rˇesˇ´ıcı´ strategie. 1.1
Bayesovske´ sı´teˇ
Bayesovske´ sı´teˇ patrˇ´ı do skupiny pravdeˇpodobnostnı´ch grafovy´ch modelu˚ ktere´ jsou schopny modelovat proble´my, ve ktery´ch je trˇeba pracovat s nejisty´mi (va´gnı´mi) informacemi. Na´vrh pouzˇ´ıt bayesovske´ sı´teˇ v oblasti expertnı´ch syste´mu se poprve´ objevuje v pracı´ch [18] a [21]. Prvnı´ skutecˇnou aplikacı´ byl expertnı´ syste´m pro elektromyografii Munin [2] a Pathfinder system [7]. Od te´ doby byly bayesovske´ sı´teˇ u´speˇsˇneˇ pouzˇity v mnoha oblastech. Sı´la teˇchto modelu˚ je zalozˇena nejen na jejich schopnosti prova´deˇt efektivneˇ vy´pocˇty se stovkami velicˇin za´rovenˇ, naprˇ. pouzˇitı´m metody popsane´ v pracech [14]) a v [11], ale take´ na jejich schopnosti pomoci cˇloveˇku le´pe porozumeˇt modelovane´ oblasti. Toho je dosazˇeno hlavneˇ dı´ky velmi dobrˇe srozumitelne´ reprezentaci neza´vislostı´ mezi velicˇinami pomocı´ acyklicky´ch orientovany´ch grafu˚. Bayesovska´ sı´t’ je tvorˇena acyklicky´ch orientovany´m grafem G = (V, E), ke kazˇde´mu uzlu i ∈ V je prˇirˇazena jedna na´hodna´ velicˇina Xi s konecˇnou mnozˇinou Xi navza´jem disjunktnı´ch stavu˚ a tabulka podmı´neˇne´ pravdeˇpodobnosti P (Xi | (Xj )j∈pa(i) ), kde pa(i) oznacˇuje mnozˇinu rodicˇu˚ uzlu i v grafu G. Viz obra´zek 1, kde je uveden prˇ´ıklad bayesovske´ sı´teˇ. ?
Tato pra´ce je cˇeskou verzı´ cˇla´nku publikovane´ho na konferenci Znalosti 2003. Autor byl podporˇen grantem Grantove´ agentury Cˇeske´ republiky cˇ´ıslo 201/02/1269.
X1 P (X1 )
X2 P (X2 )
P (X3 | X1 ) X3 X5 P (X5 | X1 )
X7
X8
P (X7 | X5 )
X4 P (X4 | X2 ) X6 P (X6 | X3 , X4 )
X9 P (X9 | X6 )
P (X8 | X7 , X6 )
Obra´zek 1. Prˇ´ıklad bayesovske´ sı´teˇ
Bayesovska´ sı´t’reprezentuje kvalitativnı´ i kvantitativnı´ znalosti. Kvantitativnı´ znalosti jsou reprezentova´ny pomocı´ tabulek podmı´neˇne´ pravdeˇpodobnosti, zatı´mco kvalitativnı´ znalosti pomocı´ acyklicke´ho orientovane´ho grafu. Tento graf vyjadrˇuje vztahy podmı´neˇne´ neza´vislosti mezi velicˇinami (Xi )i∈V . Koncept nazy´vany´ d-separace, zavedeny´ v pra´ci [19], mu˚zˇe by´t vyuzˇit pro zı´ska´nı´ podmı´neˇny´ch neza´vislostı´ z grafu. Jestlizˇe P (Xi | Y) = P (Xi | Y, Xj ) ˇr´ıka´me, zˇe velicˇiny Xi , Xj jsou podmı´neˇneˇ neza´visle´, je-li da´na mnozˇina velicˇin Y. Velicˇiny Xi , Xj jsou d-separova´ny mnozˇinou Y jestlizˇe, pro vsˇechny cesty1 spojujı´cı´ uzly i a j existuje mezilehly´ uzel k takovy´, zˇe bud’ (1) hrany se nesetka´vajı´ “head-to-head” v uzlu k a Xk ∈ Y, nebo (2) hrany se setka´vajı´ “head-to-head” v uzlu k a ani Xk , ani zˇa´dny´ jeho potomek v grafu G, nepatrˇ´ı do Y. Za´kladnı´ pozˇadavek na pravdeˇpodobnostnı´ rozdeˇlenı´ P odpovı´dajı´cı´ bayesovske´ sı´ti je, aby vsˇechny velicˇiny Xi , Xj , ktere´ jsou d-separova´ny mnozˇinou Y, byly podmı´neˇneˇ neza´visle´ da´no Y v P . Pomeˇrneˇ snadno se da´ uka´zat, zˇe pravdeˇpodobnostnı´ rozdeˇlenı´ splnˇujı´cı´ uvedeny´ pozˇadavek a za´rovenˇ majı´cı´ podmı´neˇne´ pravdeˇpodobnosti rovny P (Xi | (Xj )j∈pa(i) ), i ∈ V je pra´veˇ jedno a rovna´ se soucˇinu podmı´neˇny´ch pravdeˇpodobnostı´, t.j. P ((Xi )i∈V ) =
Y
P (Xi | (Xj )j∈pa(i) ) .
i∈V
Cˇtena´rˇe, ktere´ by zajı´mal detailnı´ u´vod do teorie bayesovsky´ch sı´tı´, odkazujeme na knihu [9]. 1.2
Vytva´rˇenı´ modelu˚
Pro vytva´rˇenı´ modelu˚ bayesovsky´ch sı´tı´ se obvykle pouzˇ´ıvajı´ trˇi za´kladnı´ prˇ´ıstupy: 1
Cestou v orientovane´m grafu G rozumı´me posloupnost uzlu˚ v1 , . . . , vk takovou, zˇe pro i = 2, . . . , k bud’ (vi−1 , vi ) nebo (vi , vi−1 ) je hranou grafu G a pro i 6= j platı´, zˇe vi 6= vj .
– Na´vrha´rˇ modelu konzultuje experta oboru, ktery´ mu poskytne expertnı´ znalosti o modelovane´m proble´mu, oblasti, cˇi zarˇ´ızenı´. Tyto znalosti na´vrha´rˇ pouzˇije prˇi vytva´rˇenı´ struktury modelu a pro specifikaci cˇ´ıselny´ch hodnot v tabulka´ch podmı´neˇne´ pravdeˇpodobnosti. – Shroma´zˇdı´ se data obsahujı´cı´ za´znamy o chova´nı´ modelovane´ho proble´mu, oblasti, cˇi zarˇ´ızenı´. Na´sledneˇ se pouzˇije neˇktera´ metoda strojove´ho ucˇenı´, pomocı´ ktere´ zı´ska´me jak strukturu modelu, tak odhady cˇ´ıselny´ch hodnot v tabulka´ch podmı´neˇne´ pravdeˇpodobnosti. – Trˇetı´ za´kladnı´ prˇ´ıstup je kombinace prˇedchozı´ch dvou. Naprˇ´ıklad struktura modelu je navrzˇena prˇi konzultacı´ch s expertem, ale cˇ´ıselne´ parametry jsou odhadova´ny ze shroma´zˇdeˇny´ch dat pomocı´ neˇktere´ ze statisticky´ch metod. I strucˇny´ prˇehled ru˚zny´ch metod, ktere´ je mozˇne´ pouzˇ´ıt pro vytva´rˇenı´ modelu˚ bayesovsky´ch sı´tı´ by znacˇneˇ prˇekrocˇil rozsah tohoto cˇla´nku. Vı´ce informacı´ mu˚zˇe cˇtena´rˇ nale´zt naprˇ´ıklad v knize [5], kde je neˇkolik kapitol veˇnova´no ucˇenı´ modelu˚. V kapitole 2 popı´sˇeme, jak byla vytvorˇena bayesovska´ sı´t’pouzˇita´ prˇi adaptivnı´m testova´nı´ znalostı´. 1.3
Vytva´rˇenı´ strategiı´ pomocı´ modelu˚
Strategie popisuje kroky, ktere´ ma´ uzˇivatel syste´mu ucˇinit, aby dosa´hl pozˇadovany´ cı´l. Prˇ´ıklady kroku˚ jsou: (1) akce na zarˇ´ızenı´, kterou uzˇivatel udeˇla´, nebo (2) pozorova´nı´, ktere´ uzˇivatel ucˇinı´, nebo (3) odpoveˇd’ uzˇivatele na polozˇenou ota´zku. Protozˇe nenı´ doprˇedu zrˇejme´, jaky´ bude vy´sledek provedene´ho kroku, kazˇda´ strategie musı´ specifikovat, co ma´ uzˇivatel ucˇinit pro vsˇechny mozˇne´ kombinace vy´sledku˚ vsˇech prˇedchozı´ch kroku˚. Takzˇe strategie mu˚zˇe by´t reprezentova´na pomocı´ orientovane´ho stromu. Je vy´hodne´ definovat dva druhy uzlu˚ stromu - na´hodne´ uzly a termina´lnı´ uzly. Kazˇdy´ na´hodny´ uzel odpovı´da´ jednomu kroku strategie. Termina´lnı´ uzly jsou listy stromu, kde strategie koncˇ´ı. Jedno pouzˇitı´ strategie, ktere´ budeme nazy´vat sezenı´, odpovı´da´ cesteˇ ve stromu zacˇ´ınajı´cı´ v korˇenu stromu a koncˇ´ıcı´ v neˇktere´m z uzlu˚ stromu. Obra´zek 2 prˇedstavuje prˇ´ıklad strategie adaptivnı´ho testu slozˇene´ ze dvou ota´zek. Elipsy prˇedstavujı´ na´hodne´ uzly a kosocˇtverce termina´lnı´ uzly. Kazˇdy´ na´hodny´ uzel je oznacˇen na´zvem kroku, ktery´ mu odpovı´da´. Kazˇda´ hrana vycha´zejı´cı´ z na´hodne´ho uzlu je oznacˇena vy´sledkem kroku odpovı´dajı´cı´ho dotycˇne´mu uzlu. Strategie reprezentovana´ tı´mto stromem je na´sledujı´cı´: Jestlizˇe odpoveˇd’ na prvnı´ ota´zku X2 je spra´vneˇ pak druha´ ota´zka je X3 jinak druha´ ota´zka je X1 . Necht’ S oznacˇuje mnozˇinu vsˇech prˇ´ıpustny´ch strategiı´ rˇesˇenı´ dane´ho proble´mu a necht’ L(s) oznacˇuje mnozˇinu vsˇech termina´lnı´ch uzlu˚ strategie s ∈ S. Definujeme hodnotı´cı´ funkci f : ∪s∈S L(s) 7→ R. Cı´lem je minimalizovat hodnotu te´to funkce na konci sezenı´. Vy´stupy navrzˇeny´ch kroku˚ nejsou doprˇedu zna´my, pouze pravdeˇpodobnost P (e` ) ukoncˇenı´ sezenı´ v uzlu ` ∈ L mu˚zˇe by´t spocˇtena pomocı´ modelu reprezentovane´ho bayesovskou sı´tı´. Pro strategii s ∈ S definujeme ocˇeka´vanou hodnotu hodnotı´cı´ funkce Ef (s) =
X `∈L(s)
P (e` ) · f (e` ) .
(1)
X3 = yes X3 :
1 4
X2 = yes X2 :
1 5
<
2 ? 5
X3 = no
1 ? 4
X2 = no
<
X1 = yes X1 :
1 5
<
2 ? 5
X1 = no
Obra´zek 2. Prˇ´ıklad strategie adaptivnı´ho testu
Cı´l tak mu˚zˇe by´t formalizova´n jako hleda´nı´ strategie s? ∈ S majı´cı´ minima´lnı´ hodnotu Ef (s) ze vsˇech prˇ´ıpustny´ch strategiı´ s ∈ S. Cˇasto se sta´va´, zˇe nenı´ mozˇne´, kvu˚li kombinatoricke´ slozˇitosti proble´mu, najı´t optima´lnı´ strategii. Mı´sto toho se pouzˇ´ıvajı´ ru˚zne´ heuristicke´ metody poskytujı´cı´ suboptima´lnı´ rˇesˇenı´. V kapitole 2 je tento prˇ´ıstup pouzˇit v adaptivnı´m testova´nı´ a v kapitole 3 v technicke´ diagnostice. Tyto aplikace majı´ ru˚zne´ typy modelu˚ bayesovsky´ch sı´tı´, ru˚zneˇ definovane´ mnozˇiny prˇ´ıpustny´ch strategiı´ a rozdı´lne´ hodnotı´cı´ funkce f . Uvidı´me, zˇe take´ metody pouzˇite´ prˇi hleda´nı´ suboptima´lnı´ strategiı´ jsou rozdı´lne´.
2
Adaptivnı´ testova´nı´
Testy, ktere´ se automaticky prˇizpu˚sobujı´ zjisˇteˇne´ u´rovni znalostı´ zkousˇene´ho, se nazy´vajı´ adaptivnı´ testy. Po zı´ska´nı´ odpoveˇdi na polozˇenou ota´zku, automaticky´ syste´m vybere na´sledujı´cı´ ota´zku s vyuzˇitı´m znalosti zı´skane´ na za´kladeˇ prˇedchozı´ch odpoveˇdı´ zkousˇene´ho. Jednoduchy´ prˇ´ıklad adaptivnı´ho testu byl uka´za´n na obra´zku 2. Protozˇe realizace adaptivnı´ho testu vyzˇaduje pouzˇitı´ pocˇ´ıtacˇu˚, je tento prˇ´ıstup cˇasto nazy´va´n pocˇ´ıtacˇove´ adaptivnı´ testova´nı´, anglicky computerized adaptive testing (CAT). Vı´ce informacı´ je mozˇne´ zı´skat v publikacı´ch [25] a [15]. 2.1
Bayesovska´ sı´t’pro adaptivnı´ testova´nı´
Autorˇi pra´ce [1] navrhli pouzˇitı´ grafovy´ch pravdeˇpodobnostnı´ch modelu˚ pro pocˇ´ıtacˇove´ adaptivnı´ testova´nı´. Jejich model se skla´da´ z modelu studenta a neˇkolika pozorovacı´ch modelu˚. Kazˇdy´ pozorovacı´ model odpovı´da´ jedne´ ota´zce. Nejprve na´vrha´rˇ testu specifikuje testovane´ znalosti a dovednosti Y = {Y1 , . . . , Yk } a prˇipravı´ soubor ota´zek X = {X1 , . . . , Xm }. Model studenta popisuje vztahy mezi znalostmi a dovednostmi studenta. Expertnı´ znalost o studentech je tak reprezentova´na sdruzˇeny´m pravdeˇpodobnostnı´ rozdeˇlenı´m P (Y1 , . . . , Yk ) definovane´m pro velicˇiny z modelu studenta. Nynı´ se budeme veˇnovat konkre´tnı´mu prˇ´ıpadu vytva´rˇenı´ modelu studenta rˇesˇ´ıcı´ho za´kladnı´ u´lohy se zlomky [23].
Nejprve, skupina studentu˚ Aalborgske´ univerzity prˇipravila papı´rove´ testy. Tyto testy rˇesˇili studenti prvnı´ho rocˇnı´ku strˇednı´ sˇkoly v obci Brønderslev. Byly testova´ny cˇtyrˇi za´kladnı´ dovednosti - scˇ´ıta´nı´, odcˇ´ıta´nı´, na´sobenı´ a porovna´va´nı´ zlomku˚, cˇtyrˇi operacˇnı´ dovednosti - kra´cenı´ zlomku˚, prˇevod nepravy´ch zlomku˚ na slozˇene´ zlomky a obra´ceneˇ, hleda´nı´ spolecˇne´ho deˇlitele a schopnosti aplikovat operacˇnı´ dovednosti v komplexnı´ch u´loha´ch. Studenti Aalborgske´ univerzity shrnuli vy´sledky jako seznam datovy´ch za´znamu˚ o jednotlivy´ch studentech. Bylo objeveno neˇkolik typicky´ch sˇpatny´ch prˇ´ıstupu˚ k rˇesˇenı´ neˇktery´ch operacı´, ktere´ byly take´ zahrnuty jako velicˇiny do modelu studenta. Jako druhy´ krok byla pomocı´ PC-algoritmu [22], implementovane´ho v syste´mu Hugin [8], vytvorˇena struktura modelu studenta. Tato automaticka´ metoda ucˇenı´ poskytla prvnı´ na´hled na vztahy mezi velicˇinami. Na´sledneˇ byly neˇktere´ vztahy mezi velicˇinami vysveˇtleny pomocı´ takzvany´ch latentnı´chch velicˇin2 . Byly take´ vynuceny neˇktere´ za´vislosti mezi velicˇinami pomocı´ vynuceny´ch hran v modelu. Vy´sledny´ model byl opeˇt naucˇen pomocı´ PC-algoritmu avsˇak prˇi pouzˇitı´ vy´sˇe zminˇovany´ch pozˇadavku˚ na vy´sledny´ model. Cˇ´ıselne´ parametry konecˇne´ho modelu byly odhadnuty z dat pomocı´ EM-algoritmu [13]. Vy´sledny´ model studenta je zobrazen na obra´zku 3. Uzly v prvnı´ rˇadeˇ odspoda odpovı´dajı´ pozorovany´m sˇpatny´m postupu˚m, sˇede´ uzly ve druhe´ rˇadeˇ za´kladnı´m dovednostem, nevyplneˇne´ uzly v druhe´ rˇadeˇ odpovı´dajı´ operacˇnı´m dovednostem a sˇede´ uzly ve trˇetı´ rˇadeˇ aplikacˇnı´m dovednostem. Uzel umı´steˇny´ nejvy´sˇe odpovı´da´ jedne´ latentnı´ velicˇineˇ. Detailneˇjsˇ´ı popis modelu je mozˇne´ nale´zt v cˇla´nku [23].
HV1
ACL
CP
MMT1
MT
MMT4
MMT3
CL
MMT2
CMI
CIM
ACMI
ACIM
MC
ACD
CD
AD
SB
MAD
MSB
Obra´zek 3. Model studenta.
Jak bylo uvedeno na zacˇa´tku te´to kapitoly, pro kazˇdou ota´zku Xj ∈ X je vytvorˇen jeden pozorovacı´ model. Tento model popisuje za´vislost mezi danou ota´zkou Xj a relevantnı´mi dovednostmi, prˇ´ıpadneˇ sˇpatny´mi postupy v modelu studenta. Prˇ´ıklad u´lohy je 1 1 4 1 3 1 ´ lohu meˇl by mı´t 3 − 12 = 12 − 12 = 12 = 4 . Aby student byl schopen vyrˇesˇit tuto u dovednosti SB (odcˇ´ıta´nı´), CL (kra´cenı´), ACL (aplikace kra´cenı´), CD (nalezenı´ spolecˇne´ho deˇlitele), ACD (aplikace nalezenı´ spolecˇne´ho deˇlitele), a nemeˇl by mı´t M SB 2
Latentnı´ velicˇina je velicˇina, jejı´zˇ hodnota nenı´ v datech nikdy pozorova´na. Mu˚zˇe vsˇak naprˇ´ıklad modelovat spolecˇnou nepozorovanou prˇ´ıcˇinu neˇkolika pozorovany´ch velicˇin.
sˇpatny´ postup prˇi odcˇ´ıta´nı´. Na obra´zku 4 je zobrazena struktura pozorovacı´ho modelu pro tuto u´lohu. Vztah mezi velicˇinou Tj a souvisejı´cı´mi dovednostmi a sˇpatny´m postupem
CL
ACL
MSB
SB
CD
Tj
ACD
Xj
Obra´zek 4. Pozorovacı´ model u´lohy Xj .
mu˚zˇe by´t popsa´n boolovskou funkcı´. Ve skutecˇnosti ale student mu˚zˇe udeˇlat chybu, ikdyzˇ ma´ vsˇechny potrˇebne´ prˇedpoklady pro spra´vne´ rˇesˇenı´ u´lohy. Na druhou stranu, spra´vna´ odpoveˇd’ nemusı´ vzˇdy znamenat, zˇe student ma´ vsˇechny potrˇebne´ prˇedpoklady, naprˇ´ıklad kdyzˇ spra´vnou odpoveˇd’ pouze uhodl. Tato nejistota je modelova´na pomocı´ podmı´neˇne´ho pravdeˇpodobnostnı´ho rozdeˇlenı´ P (Xj | Tj ) odhadnute´ho ze shroma´zˇdeˇny´ch dat. 2.2
Vytva´rˇenı´ adaptivnı´ch testu˚
Obvykle adaptivnı´ test skoncˇ´ı, kdyzˇ byl polozˇen prˇedem urcˇeny´ pocˇet ota´zek, nebo kdyzˇ zkousˇejı´cı´ zı´skal postacˇujı´cı´ informace o zkousˇene´m. Takove´ podmı´nky definujı´ mnozˇinu prˇ´ıpustny´ch strategiı´ S. Kazˇdy´ zkousˇejı´cı´ chce maximalizovat informace, ktere´ ma´ o zkousˇene´m na konci testu. Jednou z mozˇnostı´ formalizace tohoto pozˇadavku je usilovat o pravdeˇpodobnostnı´ rozdeˇlenı´ P (Y1 , . . . , Yk ) minimalizujı´cı´ Shannonovu entropii na konci testu [3]. Shannonova entropie (zkra´ceneˇ entropie) H(P ) pravdeˇpodobnostnı´ho rozdeˇlenı´ P (Y1 , . . . , Yk ) je definova´na na´sledovneˇ: X H(P ) = − P (Y1 = y1 , . . . , Yk = yk ) · log P (Y1 = y1 , . . . , Yk = yk ) . y1 ,...,yk
V kazˇde´m termina´lnı´m uzlu ` testovacı´ strategie s spocˇteme entropii podmı´neˇne´ho pravdeˇpodobnostnı´ho rozdeˇlenı´ podmı´neˇne´ho zı´skanou evidencı´, t.j. H(e` ) = H(P (Y1 , . . . , Yk | e` )) . Pouzˇijeme-li substituci f (e` ) = H(e` ) vzorec 1 mu˚zˇeme prˇepsat jako X EH (s) = P (e` ) · H(e` ) .
(2)
`∈L(s)
Cı´lem je tedy najı´t testovacı´ strategii s ∈ S minimalizujı´cı´ ocˇeka´vanou entropii EH (s).
V praxi se cˇasto pouzˇ´ıvajı´ tzv. hladove´ heuristiky, pomocı´ ktery´ nalezneme suboptima´lnı´ test. Test, ktery´ se nazy´va´ kra´tkozrace optima´lnı´ je test slozˇeny´ z ota´zek vybrany´ch tak, zˇe kazˇda´ ota´zka minimalizuje ocˇeka´vanou entropii po odpoveˇzenı´ jedne´ ota´zky. Strategie nalezene´ tı´mto zpu˚sobem nemusı´ by´t optima´lnı´, ale v praxi se cˇasto ukazuje, zˇe se prˇ´ılisˇ nelisˇ´ı od optima´lnı´ch strategiı´. 2.3
Vy´sledky a porovna´nı´ s jiny´mi prˇ´ıstupy
Klasicky´m prˇ´ıstupem pouzˇ´ıvany´m v testova´nı´ znalostı´ od 60. let 20. stoletı´ je teorie odezvy (angl. item response theory - IRT) [16, 20]. Tato metoda modeluje studenta pomocı´ jedne´ velicˇiny Θ. Tento jednoduchy´ model je vhodny´ naprˇ´ıklad pro hodnocenı´ studentu˚, ale nenı´ schopen poskytnout detailneˇjsˇ´ı diagnostiku. Rozsˇ´ırˇenı´m je vı´cerozmeˇrna´ teorie odezvy, kde se pouzˇ´ıva´ neˇkolik velicˇin reprezentujı´cı´ch ru˚zne´ aspekty souvisejı´cı´ se znalostmi a schopnostmi zkousˇene´ho. Aplikace bayesovsky´ch sı´tı´ je mozˇne´ povazˇovat za zobecneˇnı´ vı´cerozmeˇrna´ teorie odezvy prˇina´sˇejı´cı´ dveˇ za´kladnı´ vy´hody. – Bayesovska´ sı´t’ je schopna le´pe modelovat usuzova´nı´ studenta a umozˇnuje hlubsˇ´ı pochopenı´ modelovane´ho proble´mu. – Protozˇe model studenta reprezentovany´ pomocı´ bayesovske´ sı´teˇ je schopen zachytit vztahy mezi testovany´mi dovednostmi a schopnostmi, je mozˇne´ podstatneˇ zkra´tit adaptivnı´ test prˇi zachova´nı´ spolehlivosti vy´sledku˚. Vy´sledky experimentu˚ s adaptivnı´mi testy vyuzˇ´ıvajı´cı´mi bayesovske´ sı´teˇ, prezentovane´ v cˇla´nku [23], ukazujı´, zˇe bylo mozˇne´ dobrˇe odhadovat skutecˇne´ dovednosti studenta. V pru˚meˇru vı´ce nezˇ 90% dovednostı´ bylo spra´vneˇ odhadnuto jizˇ po sedmi polozˇeny´ch ota´zka´ch. V papı´rovy´ch (neadaptivnı´ch testech) bylo trˇeba polozˇit 20 ota´zek pro dosazˇenı´ stejne´ kvality predikce. Dalsˇ´ı experimenty s bayesovsky´mi sı´teˇmi v oblasti adaptivnı´ho testova´nı´ a vy´uky (angl. tutoring) jsou popsa´ny v cˇla´nku [17], respektive v cˇla´nku [4].
3
Technicka´ diagnostika
Technicka´ diagnostika je cˇasto velmi slozˇita´ u´loha. Proto pocˇ´ıtacˇove´ syste´my vyuzˇ´ıvajı´cı´ postupneˇ zı´skane´ informace o diagnostikovane´m zarˇ´ızenı´ mohou podstatneˇ zrychlit diagnosticky´ proces [6]. 3.1
Bayesovske´ sı´teˇ v technicke´ diagnostice
V cˇla´nku [10] je popsa´no vyuzˇitı´ bayesovske´ sı´teˇ v technicke´ diagnostice. Model bayesovske´ sı´teˇ zachycuje vztahy mezi trˇemi typy velicˇin: poruchami zarˇ´ızenı´ F ∈ F, akcemi A ∈ A, t.j. opravny´mi kroky ktere´ mohou odstranit poruchu a pozorova´nı´mi Q ∈ Q kroky ktere´ nemohou odstranit poruchu, ale mohou ji pomoci odhalit. Kazˇde´ akci a pozorova´nı´ je prˇirˇazena cena c, ktera´ mu˚zˇe naprˇ´ıklad prˇedstavovat cˇas potrˇebny´ pro provedenı´ dotycˇne´ akce cˇi pozorova´nı´, nebo cenu, kterou je trˇeba za provedenı´ akce cˇi pozorova´nı´
zaplatit. Pouzˇijeme zjednodusˇeny´ prˇ´ıklad z cˇla´nku [24], abychom ilustrovali, jak mu˚zˇe probı´hat technicka´ diagnostika laserove´ tiska´rny. Example 1 (Sveˇtly´ tisk). Prˇedpokla´dejme, zˇe tiska´rna vytiskne stra´nku, ktera´ je prˇ´ılisˇ sveˇtla´. Tento proble´m mu˚zˇe mı´t mnoho prˇ´ıcˇin. Uvazˇujme zjednodusˇeny´ model obsahujı´cı´ pouze 4 mozˇne´ prˇ´ıcˇiny sveˇtle´ho tisku: F1 distribucˇnı´ proble´m toneru, F2 vadny´ toner, F3 narusˇeny´ tok dat, a F4 sˇpatne´ nastavenı´ ovladacˇe. Necht’ akce, ktere´ mohou vyrˇesˇit tento proble´m jsou: A1 “vyjmeˇte toner, zatrˇeste s nı´m a ulozˇte ho zpeˇt” s cenou c1 = 5, A2 “zkuste jiny´ toner” s cenou c2 = 15 a A3 “vypneˇte a zase zapneˇte tiska´rnu” s cenou c3 = 1. Pro kazˇdou akci expert zadal podmı´neˇnou pravdeˇpodobnost P (Ai = yes | Fj ). Naprˇ´ıklad, akce A2 “zkuste jiny´ toner” vyrˇesˇ´ı distribucˇnı´ proble´m toneru a vadny´ toner s pravdeˇpodobnostı´ 0.9, t.j. P (A2 = yes | Fi ) = 0.9, i = 1, 2, ale nevyrˇesˇ´ı sˇpatne´ nastavenı´ ovladacˇe, t.j. P (A2 = yes | F4 ) = 0. Cˇasto je vy´hodne´ polozˇit beˇhem diagnostiky neˇkolik ota´zek o stavu zarˇ´ızenı´. Odpoveˇdi mohou pomoci identifikovat prˇ´ıcˇinu proble´mu zarˇ´ızenı´. Naprˇ´ıklad, jestlizˇe odpoveˇd’ na ota´zku Q1 “Je konfiguracˇnı´ stra´nka vytisˇteˇna sveˇtle?” je negativnı´ pak prˇ´ıcˇiny F1 distribucˇnı´ proble´m toneru a F2 vadny´ toner je mozˇne´ vyloucˇit. Pro kazˇdou ota´zku Qi a kazˇdou prˇ´ıcˇinu Fj expert definuje podmı´neˇnou pravdeˇpodobnost P (Qi = yes | Fj ). U veˇtsˇiny technicky´ch zarˇ´ızenı´ je mozˇne´ prˇedpokla´dat, zˇe akce a ota´zky jsou navza´jem podmı´neˇneˇ neza´visle´ je-li zna´ma prˇ´ıcˇina. T.j. pro kazˇde´ Ai ∈ A, Qk ∈ Q P (Ai |F) = P (Ai |F, V) pro kazˇde´ V ⊆ (A ∪ Q) \ {Ai } P (Qk |F) = P (Qk |F, U) pro kazˇde´ U ⊆ (A ∪ Q) \ {Qk } . Da´le je cˇasto mozˇne´ prˇedpokla´dat, zˇe v jednom okamzˇiku zpu˚sobuje sˇpatnou funkci zarˇ´ızenı´ pouze jedna prˇ´ıcˇina. Bayesovska´ sı´t’na obra´zku 5 zachycuje oba prˇedpoklady. Actions Faults
A1
F1 A2 Problem
F2 A3
F F3 F4
Questions Q1
Obra´zek 5. Bayesovska´ sı´t’pro zjednodusˇeny´ proble´m sveˇtle´ho tisku
3.2
Diagnosticka´ strategie
Kazˇda´ diagnosticka´ strategie mu˚zˇe skoncˇit dveˇma zpu˚soby, bud’ u´speˇsˇny´m vyrˇesˇenı´m proble´mu nebo neu´speˇsˇneˇ - proble´m zu˚stane nevyrˇesˇen. Proto definujeme dva typy termina´lnı´ch uzlu˚: (1) u´speˇsˇne´ termina´lnı´ uzly odpovı´dajı´ vyrˇesˇenı´ proble´mu, (2) neu´speˇsˇne´ termina´lnı´ uzly odpovı´dajı´ situaci, kdy diagnostika skoncˇ´ı drˇ´ıve, nezˇ je proble´m vyrˇesˇen. ´ speˇsˇne´ termina´lnı´ uzly jsou sˇede´, Obra´zek 6 zobrazuje prˇ´ıklad diagnosticke´ strategie. U zatı´mco neu´speˇsˇne´ termina´lnı´ uzly jsou sveˇtle´.
A1 = yes Q1 = no
A1
Q1 = yes
A2
A1 = no
A2 = yes
A2
A2 = no
Q1 A2 = no
A2 = yes
A1
A1 = no
A1 = yes
Obra´zek 6. Diagnosticka´ strategie
Definujeme hodnotı´cı´ funkci CR(e` ), ktera´ odpovı´da´ ceneˇ opravy zarˇ´ızenı´. Skla´da´ se ze dvou slozˇek. Prvnı´ slozˇka t(e` ) je celkova´ cena provedeny´ch akcı´ a polozˇeny´ch ota´zek, ktere´ jsou na cesteˇ do stavu e` odpovı´dajı´cı´mu uzlu ` ve stromu strategie s. Druha´ slozˇka je penalizacˇnı´ funkce c(e` ), ktera´ se aplikuje v kazˇde´m termina´lnı´m uzlu. Jestlizˇe je proble´m u´speˇsˇneˇ vyrˇesˇen (v u´speˇsˇne´m termina´lnı´m uzlu), pak penalizacˇnı´ funkce je rovna nule. V neu´speˇsˇne´m termina´lnı´m uzlu ma´ penalizacˇnı´ funkce kladnou hodnotu, ktera´ mu˚zˇe by´t naprˇ´ıklad interpretova´na jako cena za zavola´nı´ servisnı´ch techniku˚, kterˇ´ı zarˇ´ızenı´ zarucˇeneˇ opravı´ (naprˇ´ıklad tı´m, zˇe ho cele´ vymeˇnı´). Takzˇe CR(e` ) = t(e` ) + c(e` ). Provedeme-li substituci f (e` ) = CR(e` ) do vzorce 1 zı´ska´me krite´rium nazy´vane´ ocˇeka´vana´ cena opravy. X ECR (s) = P (e` ) · ( t(e` ) + c(e` ) ) . (3) `∈L(s)
Za´kladnı´ u´lohou technicke´ diagnostiky je najı´t diagnostickou strategii s ∈ S minimalizujı´cı´ ECR (s).
Rˇesˇenı´ je mozˇne´ snadno najı´t v prˇ´ıpadeˇ, kdyzˇ (1) kazˇda´ akce mu˚zˇe odstranit pra´veˇ jednu prˇ´ıcˇinu, kdyzˇ (2) vsˇechny akce jsou navza´jem neza´visle´, (3) v jednom okamzˇiku zpu˚sobuje sˇpatnou funkci zarˇ´ızenı´ pouze jedna prˇ´ıcˇina a (4) nenı´ mozˇne´ pouzˇ´ıt zˇa´dne´ ota´zky. V takove´m prˇ´ıpadeˇ, postacˇuje serˇadit ota´zky sestupneˇ podle pomeˇru P (A = yes)/cA , viz [12]. V pra´ci [24] bylo uka´za´no, zˇe kdyzˇ neˇktere´ akce mohou odstranit vı´ce nezˇ dveˇ prˇ´ıcˇiny, u´loha nalezenı´ optima´lnı´ diagnosticke´ strategie se sta´va´ N P -teˇzˇkou. Proto je trˇeba pouzˇ´ıt metody, ktere´ naleznou dostatecˇneˇ dobre´ (ikdyzˇ neoptima´lnı´) diagnosticke´ strategie v polynomia´lnı´m cˇase. 3.3
Vy´sledky
Diagnosticky´ syste´m vyvinuty´ v ra´mci projektu SACSO vyuzˇ´ıva´ bayesovskou sı´t’ pro reprezentaci diagnosticke´ho proble´mu. Protozˇe struktura modelu je jednoducha´ (odpovı´da´ tzv. naivnı´mu bayesovske´mu modelu), je mozˇne´ prˇi vy´beˇru dalsˇ´ıho kroku strategie prove´st velky´ pocˇet vy´pocˇtu˚ podmı´neˇny´ch pravdeˇpodobnostı´. Prˇ´ıstup pouzˇity´ v projektu SACSO je zalozˇeny´ na heuristika´ch vyuzˇ´ıvajı´cı´ch pomeˇr P (A = yes)/cA a za´rovenˇ rozsˇirˇuje prˇ´ıstup popsany´ v [6], v ra´mci ktere´ho je mozˇne´ vybı´rat i ota´zky. V cˇla´nku [10] jsou diagnosticke´ strategie zı´skane´ pomocı´ prˇ´ıstupu projektu SACSO porovna´ny s optima´lnı´mi strategiemi zı´skany´mi vy´pocˇetneˇ na´rocˇny´m prohleda´va´nı´m stavove´ho prostoru vsˇech mozˇny´ch strategiı´. Hodnoty ECR strategiı´ zı´skany´ch diagnosticky´m syste´mem SACSO byly velmi blı´zko optima´lnı´m hodnota´m, pru˚meˇrna´ odchylka byla me´neˇ nezˇ 2%. Tento diagnosticky´ syste´m je nynı´ komercˇneˇ nabı´zen pod jme´nem DezisionWorks da´nskou spolecˇnostı´ Dezide. Vı´ce informacı´ o syste´mu je mozˇne´ nale´zt na webovske´ stra´nce spolecˇnosti: http://www.dezide.com/.
Reference 1. Russell G. Almond and Robert J. Mislevy. Graphical models and computerized adaptive testing. Applied Psychological Measurement, 23(3):223–237, 1999. 2. S. Andreassen, F. V. Jensen, S. K. Andersen, B. Falck, U. Kjærulff, M. Woldbye, A. R. Sørensen, A. Rosenfalck, and F. Jensen. MUNIN — an expert EMG assistant. In John E. Desmedt, editor, Computer-Aided Electromyography and Expert Systems, chapter 21. Elsevier Science Publishers, Amsterdam, 1989. 3. Moshe Ben-Bassat. Myopic policies in sequential classification. IEEE Transactions on Computers, 27(2):170–174, 1978. 4. Cristina Conati, Abigail S. Gertner, Kurt VanLehn, and Marek J. Druzdzel. On-line student modeling for coached problem solving using Bayesian networks. In Anthony Jameson, Cecile Paris, and Carlo Tasso, editors, Proc. of the Sixth Int. Conf. on User Modeling (UM97), Chia Laguna, Sardinia, Italy. Springer Verlag, 1997. 5. Robert G. Cowell, A. Philip Dawid, Steffen L. Lauritzen, and David J. Spiegelhalter. Probabilistic Networks and Expert Systems. Statistics for Engineering and Information Science. Springer Verlag, 1999. 6. D. Heckerman, J. S. Breese, and K. Rommelse. Decision-theoretic troubleshooting. Communications of the ACM, 38(3):49–57, 1995. 7. David Heckerman, E. Horwitz, and B. Nathwani. Towards normative expert systems: Part I, the Pathfinder project. Methods of Information in Medicine, 31:90–105, 1992. 8. Hugin Explorer, ver. 6.0. Computer software, 2002. http://www.hugin.com.
9. Finn V. Jensen. Bayesian networks and decision graphs. Statistics for Engineering and Infromation Science. Springer Verlag, New York, Berlin, Heidelberg, 2001. 10. Finn V. Jensen, Uffe Kjærulff, Brian Kristiansen, Helge Langseth, Claus Skaanning, Jirˇ´ı Vomlel, and Marta Vomlelova´. The SACSO methodology for troubleshooting complex systems. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 15:321–333, 2001. 11. Finn V. Jensen, Steffen L. Lauritzen, and Kristian G. Olesen. Bayesian updating in recursive graphical models by local computation. Computational Statistics Quarterly, 4:269–282, 1990. 12. J. Kalagnanam and M. Henrion. A comparison of decision analysis and expert rules for sequential analysis. In P. Besnard and S. Hanks, editors, The Fourth Conference on Uncertainty in Artificial Intelligence, pages 271–281, New York, 1988. 13. Steffen L. Lauritzen. The EM-algorithm for graphical association models with missing data. Computational Statistics and Data Analysis, 1:191–201, 1995. 14. Steffen L. Lauritzen and David J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems (with discussion). Journal of the Royal Statistical Society, Series B, 50:157–224, 1988. 15. Wim J. Van Der Linden and Cees A. W. Glas, editors. Computerized Adaptive Testing: Theory and Practice. Kluwer Academic Publishers, 2000. 16. F. M. Lord. A theory of test scores. Number 7 in Psychometric Monographs. Psychometric Society, 1952. 17. Eva Milla´n and Jose´ Luis Pe´rez-de-la-Cruz. A Bayesian diagnostic algorithm for student modeling and its evaluation. User modeling and User-Adapted Interaction, 12(2–3):281–330, 2002. 18. Judea Pearl. Reverend Bayes on inference engines: a distributed hierarchical approach. In Proceedings, AAAI National Conference on AI,Pittsburgh, PA, pages 133–136, August 1982. 19. Judea Pearl. Fusion, propagation and structuring in belief networks. Artificial Intelligence, 29(3):241– 288, 1986. 20. G. Rasch. Probabilistic models for some intelligence and attainment tests. Technical report, Danish Institute for Educational Research, Copenhagen, 1960. 21. D. J. Spiegelhalter and R. P. Knill-Jones. Statistical and knowledge-based approaches to clinical decision-support systems. Journal of the Royal Statistical Society, Series A, (147):35–77, 1984. 22. Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search. Number 81 in Lecture Notes in Statistics. Springer Verlag, 1993. 23. Jirˇ´ı Vomlel. Bayesian networks in educational testing. In Proceedings of First European Workshop on Probabilistic Graphical Models (PGM’02), Cuenca, Spain, November 6-8 2002. 24. Marta Vomlelova´ and Jirˇ´ı Vomlel. Troubleshooting: NP-hardness and solution methods. Soft Computing Journal, 7(5):357–368, April 2003. 25. Howard Wainer, David Thissen, and Robert J. Mislevy. Computerized adaptive testing : a primer. Mahwah, N.J. : Lawrence Erlbaum Associates, second edition, 2000.
