16.5. Döntési hálók

Ebben az alfejezetben egy általános mechanizmust fogunk megvizsgálni a racionális döntések meghozatalára. A felhasznált eszközt gyakran hatásdiagramnak (influence diagram) hívják (Howard és Matheson, 1984), de mi a többet sugalló döntési hálók (decision networks) elnevezést fogjuk használni. A döntési hálók a cselekvésekhez és a hasznosságokhoz szükséges újabb csomóponttípusok hozzáadásával továbbfejlesztett valószínűségi hálók. A repülőtéri elhelyezési problémát fogjuk használni példának.

16.5.1. Döntési problémák reprezentálása döntési hálókkal

Egy döntési háló a legáltalánosabb formájában az ágens jelenlegi állapotáról tartalmaz információkat, megadja az ágens lehetséges cselekvéseit, azt az állapotot, amit az ágens cselekvése eredményez, és ennek az állapotnak a hasznosságát. Tehát alapot szolgáltat az olyan hasznosságelvű ágensek megépítéséhez, amilyeneket a 2.4. alfejezetben vezettünk be először. A 16.5. ábra egy döntési hálót mutat a repülőtér helyszíne megválasztásának problémájához. Ez bemutatja a három felhasználásra kerülő csomóponttípust:

  • A véletlen csomópontok (chance nodes) (ovális) valószínűségi változókat jelölnek, pont úgy, ahogy a valószínűségi hálókban. Az ágens lehet bizonytalan az építési költségekben, a légi forgalom szintjében és a pereskedés lehetősége miatt, valamint a Halálesetek, a Zaj és a teljes Költség változókban, amelyek mindegyike szintén függ a kiválasztott helyszíntől. Minden egyes véletlen csomópontnak van egy feltételes valószínűségi táblája (FVT), ami a szülőcsomópontok állapotaival indexelt. A döntési hálókban a szülőcsomópontok lehetnek döntési csomópontok és véletlen csomópontok. Kiemelendő, hogy a jelenlegi-állapot véletlen csomópontok bármelyike része lehet egy nagyobb valószínűségi hálónak, ami az építkezés költségét, a légi forgalom nagyságát vagy a perek lehetőségét becsüli meg.

  • A döntési csomópontok (decision nodes) (négyszögek) azokat a beavatkozási pontokat reprezentálják, ahol a döntéshozónak lehetősége van a cselekvésre. Ebben az esetben a ReptérHelyszíne különböző értékeket vehet fel a megfontolás alatt álló helyszíneknek megfelelően. A választás befolyásolni fogja a kiadódó költséget, a biztonságot és a repülőtér által keltett zajt. Ebben a fejezetben feltételezzük, hogy egyetlen döntéssel foglalkozunk (azaz egyetlen ilyen csomópont létezik). A 17. fejezet tárgyalja azokat az eseteket, ahol több mint egy döntést kell meghozni.

  • A hasznosságcsomópontok (utility nodes) (rombusz) az ágens hasznosságfüggvényét reprezentálják.[168] A hasznosságcsomópontnak szülője az összes olyan változó, amelyek által leírt kimeneteli állapotok közvetlenül befolyásolják a hasznosságot. A hasznosságcsomóponthoz tartozik egy leírás, ami az ágens hasznosságát adja meg egy szülői attribútumokon definiált függvénnyel. A leírás lehet a függvény egy táblázatos megadása, vagy lehet egy parametrikus additív vagy lineáris függvény.

16.5. ábra - Egy egyszerű döntési hálózat a repülőtér-elhelyezési problémára
Egy egyszerű döntési hálózat a repülőtér-elhelyezési problémára

Sok esetben csupán egy egyszerűsített formát használunk. A jelölés ugyanaz marad, de az a véletlen csomópont, ami a kimeneti állapotot jelöli, elmarad. Ehelyett, a hasznosságcsomópontot közvetlenül a jelenlegi állapot csomópontokhoz és a döntési csomóponthoz kötik. Ebben az esetben a hasznosságcsomópont ahelyett, hogy az állapotokon definiált hasznosságfüggvényt reprezentálná, az egyes cselekvésekre vonatkozó várható hasznosságokat reprezentálja, ahogy azt a (16.1) egyenlet definiálja. Ezért az ilyen táblákat cselekvéshasznosság tábláknak (action-utility tables) nevezzük. A 16.6. ábra a repülőtér probléma cselekvéshasznosság-reprezentációját mutatja.

Láthatjuk, hogy mivel a Zaj, a Halálesetek és a Költség véletlen csomópontok a 16.5. ábrán a jövőbeli állapotokra vonatkoznak, ezek soha nem kaphatnak értéket, mint tényváltozók. Így az egyszerűsített verzió, amiből elhagytuk ezeket a csomópontokat, minden olyan esetben használható, amikor az általánosabb forma használható. Bár az egyszerűsített forma kevesebb csomópontot tartalmaz, az elhelyezés kimeneteleihez kapcsolódó közvetlen leírások elhagyása azt eredményezi, hogy kevésbé rugalmas a körülmények esetleges változásaira. Például a 16.5. ábrán a repülőgép zajszintjében bekövetkező változást a Zaj csomópont feltételes valószínűségi táblájának megfelelő megváltoztatásával lehet modellezni, ezzel szemben a zajszennyezés fontosságának a megváltozását a hasznosságfüggvényben a hasznosságtábla megváltoztatásával modellezhetjük. Másfelől a cselekvéshasznosság diagramban – 16.6. ábra – létrejövő minden ilyenfajta változtatást a cselekvéshasznosság táblázat megváltoztatásának kell tükröznie. Lényegében a cselekvéshasznosság forma az eredeti forma egy szerkesztett verziója.

16.5.2. Döntési hálók kiértékelése

A cselekvéseket úgy választjuk ki, hogy a döntési hálót kiértékeljük a döntési csomópont minden lehetséges beállítására. Ha egyszer a döntési csomópontot beállítottuk, úgy fog viselkedni, mint egy véletlen csomópont, amit egy tényváltozónak állítottunk be. A döntési háló kiértékelését a következő algoritmus végzi:

  1. Állítsa be a tényváltozókat a jelenlegi állapotra.

  2. A döntési csomópont minden egyes értékére:

    1. Állítsa be a döntési csomópontot erre az értékre.

    2. Számítsa ki az a posteriori valószínűségeket a hasznosságcsomópont szüleire, egy szabványos valószínűségi következtető algoritmust használva.

    3. Számítsa ki a cselekvés hasznosságát.

  3. Térjen vissza a legnagyobb hasznosságértékkel.

16.6. ábra - A repülőtér-elhelyezési probléma egy egyszerűsített reprezentációja. A kimeneti állapotokhoz tartozó véletlen csomópontok hatását kiszámítottuk, majd a csomópontokat elhagytuk.
A repülőtér-elhelyezési probléma egy egyszerűsített reprezentációja. A kimeneti állapotokhoz tartozó véletlen csomópontok hatását kiszámítottuk, majd a csomópontokat elhagytuk.

Ez a valószínűségi hálók következtető algoritmusának egy nyilvánvaló kiterjesztése, és közvetlenül beilleszthető az ágens 13.1. ábrán megadott tervezésébe. A 17. fejezetben látni fogjuk, hogy több egymást követő cselekvés lehetősége a problémát sokkal érdekesebbé teszi.



[168] Ezeket a csomópontokat gyakran értékcsomópontoknak (value nodes) nevezik az irodalomban. Mi jobbnak láttuk megtartani a különbséget a hasznosság- és az értékfüggvények között, ahogyan ezt korábban indokoltuk, ezért lehet, hogy a kimeneti állapot egy szerencsejátékot reprezentál.