|
Előadásomban beszélek a DeepMind AlphaZero algoritmus kulcs
alkotóelemeiről és bemutatom a közelmúlt néhány jelentősebb eredményét
a Machine Learning területéről. Végül filozofálgatok arról, hogy ezek
miket jelentenek a Mesterséges Intelligencia jövőjére nézve.
|
|
Az előadáson a Minimimum Key és a Minimum Target Set Selection problémákról lesz szó. Ez két nagyon nehéz optimalizálási probléma, melyek a matematika legkülönbözőbb területein merülnek fel más-más kontextusban. A problémák egy bázispoliéderekre vonatkozó általánosítását fogalmazzuk meg, és arra is választ kapunk, miért van helyesírási hiba a címben.
|
|
Morrill nyomán azt vizsgáljuk, hogyan lehet Pareto-optimális szobabeosztást találni. Ennek kapcsán mutatunk rá Edmonds párosításalgoritmusának egy nem annyira ismert alkalmazására.
|
|
Az előadásban olyan megtörtént eseteket elevenítünk fel, amelyekben bizonyos kérdések alapos vizsgálata tételeket eredményezett.
|
|
András doktori témának anno a merevség matroid minimális vágásának kérdését adta, azaz azt a kérdést hogy hány élet kell minimum kitörölni egy merev gráfból, hogy ne legyen már merev. A kérdésnek végül egy megfordítottját sikerült (count matroidokra) akkor algoritmikusan megoldani: hány élet kell hozzáadni, hogy a minimális vágás mérete legalább 2 legyen. Az algoritmusból viszont nem volt kiolvasható egy szép minimax tétel. Ezt most Mihálykó Andrással közös munkánkban pótoljuk.
|
|
Az előadás során rövid sétát teszünk a poliéderes kombinatorika világában, és mindenütt g-polimatroidokba botlunk.
|
|
Arról fogok mesélni, hogy András hogyan palizott be engem, és érte el, hogy Bonyolultságelmélet helyett inkább Komb.Opt.-tal foglalkozzak. Egy A gát erős, ha minden őt tartalmazó gát csak G-A páros komponenseibe harap bele. A fő eredmény (1994 környéke), hogy erős gátak metszete erős. Ennek néhány következményéről fogok mesélni. A Lovász-Plummer könyv második kiadásában van egy rövid appendix az első kiadás után megjelent eredményekről, ebben az első megemlített eredmény ez, ami sajnos soha nem jelent meg cikkben.
|
|
Andrással 1972-től dolgoztam együtt, először 12 évig a Távközlési Kutató Intézetben, azóta az ELTE-n. Néhány közös élmény felelevenítése mellett két olyan eredményéről lesz szó, amelyeket a villamosmérnökökkel való együttműködés motivált.
|
|
Egy első piszkét mutatunk be a büszkebokorból.
|
ANDRIStól EGRESig: Néhány friss pöszméte a köszmétebokorból II.
|
|
Egy második piszkét mutatunk be a büszkebokorból.
|
|
A trópusi geometria egy viszonylag fiatal terület, ami a (max, +) féltest feletti algebrai geometriát jelenti. A terület valahol félúton van a diszkrét és a folytonos között. A konkrét kérdések átfogalmazhatók metrikus gráfokra, azaz olyan élhosszakkal rendelkező gráfokra amiket metrikus térnek tekintünk. Egy olyan kérdésről fogok beszélni ahol működnek a klasszikus kombinatorikus optimalizálásbeli technikák. Konkrétabban: Szubmoduláris függvényeket és a kikeresztezési eljárást fogjuk alkalmazni, de a szubmoduláris függvény egy végtelen halmazrendszeren lesz értelmezve. Andreas Gross-al és Farbod Shokrieh-vel közös projekt.
|
|
Az előadásban az ellipszoid módszer néhány érdekes aspektusát járjuk körül. A közhiedelem szerint az ellipszoid módszer kizárólag primál algoritmus: nem ad bizonyítékot arra az esetre, ha a probléma nem megengedett. Az előadásban bemutatok egy, eredetileg Burrell és Todd által bevezetett nézőpontot, amely az ellipszoid algoritmust kvadratikus formák segítségével írja le. A reprezentáció segítségével egyszerűen kaphatunk duális bizonyítékokat az ellipszoid által garantált egyenlőtlenségekre, és Farkas bizonyítékot a meg nem engedettségi esetben. Ez a nézőpont különösen hasznos alacsonyabb dimenziós racionális poliédereknél. Egy természetes feltevés teljesülése esetén a szimultán diofantikus approximációt ki tudjuk váltani egy jóval egyszerűbb lánctört közelítéssel.
|