Szepesvári Csaba, 2004 június
Egy tigris lapul a bózótban, arra várva, hogy a prédaállat
közelebb kerüljön hozzá. A múlt héten egy vendégemet akartam elvinni autóval a
szálláshelyére. A dolog több szempontból is nehezen ment: először dugóba
kerültünk, aztán pedig a sok egyirányú utca és egy útlezárás miatt többször is
kerülnöm kellett mire végre odaértünk. Egy mobil telefontársaság csökkenti a
percdíjakat, hogy így növelje előfizetői bázisát és ezáltal
jövőbeni profitját. Egy mosóporgyártó egy speciális reklámkampányba kezd.
A fenti példák mind olyan döntési problémákat takarnak, amikor a döntéseket
egymás után, szekvenciálisan, hozzák meg. Az ilyen szekvenciális döntési
problémák lényege, hogy a "ma" hozott döntéseknek mind rövid-, mind
hosszútávú hatásai is lehetnek és a ma legjobb döntése erősen függ a
jövőbeli szituációktól. A problémát tovább nehezíti, hogy a döntések
jövőbeni hatása gyakran nem-determinisztikus (azaz a kimenetelek nem
"biztosak").
A szekvenciális döntési
problémákat az 50-es évektől kezdve intenzíven kutatták, először
főként az amerikai hadügyminisztérium megbízásából, később azonban
már az ipari alkalmazások is előtérbe kerültek. A kialakult kutatási terület
"dinamikus programozás" néven vált ismertté (nevében a
"dinamikus" szó utal arra, hogy időbeli folyamatok
optimaliciójáról van szó), legnevesebb úttörője Richard Bellman
(1920-1984).
Bár a dinamikus programozás
módszerével számos gyakorlati problémát sikerült megoldani, a kutatók (köztük
Bellman is) már korán felismerték, hogy a nagyobb méretű, sok-változós
feladatok megoldása igen kemény dió lehet. Mivel a nehézségeken általában nem
sikerült túljutni, Bellman el is nevezte ezt a "dimenzionalitás
átkának". (A dimenzió a változók száma amivel leírható a rendszer
"állapota" - egy komolyabb probléma esetén a változók száma több
száz, vagy akár több ezer is lehet.)
A "megerősítéses
tanulás" kutatói olyan algoritmusokat kutatnak, amelyek képesek minden
korábbinál nagyobb problémák hatékony megoldására is. Ugyan egy matematikai
eredmény alapján tudjuk, hogy a "dimenzionalitás átkát" csak
szerencsés esetben lehet elkerülni, sok esetben már a közelítőleg
optimális megoldások is nagy előrelépést jelenthetnek a heurisztikus, netán
ad hoc megoldások által elért teljesítményhez képest. Az újdonság az, hogy a
megerősítéses tanulás kutatói modern, gépi tanulás és mesterséges
intelligencia módszereket (pl. neuronhálókat) elegyítenek a dinamikus
programozási módszerekkel. Ezzel a módszerrel először G. Tesauro ért el
látványos sikert, amikor 1989-ben egy megerősítéses tanulás segítségével
tanított programja megnyerte a "backgammon" programok olimpiáját,
legyőzve minden más, többnyire évekig kézzel is hangolt programot. Azóta
programját továbbfejlesztette és ma a világ legjobb humán játékosainak szintjén
játszik. A módszer azonban nem csak játékok megoldására alkalmas. Zhang &
Dietterich például a NASA űrrepülőgépének rakodási idejének
minimalizálására használta - sikerrel. A sikeres alkalmazások sora folytatható:
felhőkarcolók liftjei működtetésének optimalizálása, kommunikációs
hálózatokban dinamikus "csatorna" kiosztás optimalizálása a
megbízhatóság növelése érdekében, robotok vezérlése, stb.
Egy adott feladat megoldása a
feladat felmérésével kezdődik. Ennek során a kutatók a kliens
szakembereivel konzultálva közösen kialakítják a folyamat modellt, azonosítják
az egyszerűsítési lehetőségeket, az adat forrásokat. Ez utóbbinak
kiemelkedő jelentősége van: a megerősítéses tanulásnak vannak
olyan módszerei, amelynek segítségével a folyamat elméleti modelljének
felállítása nélkül, pusztán az adatok segítségével is lehetséges a folyamat
optimalizálása. Az eredmények minőségét az adatok minőségén és
mennyiségén kívűl persze az is befolyásolja, hogy a feladatnak vannak-e
olyan speciális tulajdonságai, amelyek segítségével egyszerűbb és
pontosabb modellek építhetőek.