zpravodaj ČSKI
aktuální číslo
přednáška
archiv
  - 2019
  - 2018
  - 2017
  - 2016
  - 2015
  - 2014
  - 2013
  - 2012
  - 2011
  - 2010
  - 2009
  - 2008
  - 2007
  - 2006
  - 2005
  - 2004
  - 2003
  - 2002
  - 2001
  - 2000
  - 1999
  - 1998
  - 1997
  - 1996
  - 1995
  - 1994
 
 
zpravodaj ČSKI - leden 2003 [ pdf ]
[ zaslat oznámení o přednášce ]
leden|únor|březen|duben|květen|červen|říjen|listopad|prosinec


datum: 13.1.2003 v 11:00
název: Pravděpodobnostní přístupy k indukci teorií prvého řádu
přednášející: Filip Železný (FEL ČVUT)
místo konání: FEL, 1.patro, místnost č.112 (Vyčichlova knihovna)

souhrn: Přednáškou shrnu svoji práv dokončenou disertační práci, je šířeji abstrahována na P/pubs/thesis.pdf a jej cel zněn je k dispozici na P/disertace.pdf, kde P = http://labe.felk.cvut.cz/ zelezny. Vzhledem k jejímu rozsahu a omezenému času semináře nepředpokládám pokryt všech podtémat a spíše lze očekávat pozastaven nad podrobnostmi, které vzbudí zájem či kritiku. Studie představuje dva pravděpodobnostní přístupy k indukci teorií prvého řádu, čili ke splněn úlohy induktivního logického programování. Oba jsou motivovány předešlými nepotěšujícími výsledky o efektivní řešitelnosti tohoto problému v různých konfiguracích ILP, a to z pohledu přísných rámců naučitelnosti, jako je např. PACnau čitelnost. Nejprve shrnuji výsledky v tomto směru dosud znám a konstatuji, že jejich většinou pesimistické závěry kontrastuj s častými úspěšnými aplikacemi ILP. V souladu s dřívějšími diskusemi v literatuře soudím, že PACnau čitelnost není vhodným hodnotícím rámcem pro ILP a uchyluji se k odlišnému způsobu hodnocen ILP algoritmu, jen je založen na průměrných mírách (namísto měr nejhorších případů), zejména na průměrné efektivitě algoritmu a průměrné kvalit jeho výsledků.
V tomto kontextu nejprve představuji přizpůsoben randomizační metody, díky níž drtivě snižuji průměrnou dobu běhu ILP algoritmu v případech, kdy pravděpodobnostní rozložení trvání konstrukce vhodných klauzulí má specifickou vlastnost (tzv. těžký ocas). Ukazuji, že tak je tomu například ve dvou důležitých problémech týkajících se predikce mutagenity a karcinogenity chemikálií (po uzavření disertace jsem jev pozoroval ještě v dalších doménách). Za zvýšení efektivity algoritmu ILP platíme jen malým snížením prediktivní schopnosti výsledných teorií. Urychlen dosahuji znáhodněným prohledáváním svazu klauzulí, zejména adaptací metody známé ako rychlá náhodná znovuspuštění. Diskutuji tak některé zetelné souvislosti s jevem fázového přechodu známého z roblémů plnění omezujících podmínek (constraint satisfaction problems).
Dále uvádím metodu hodnocen teorie prvého řádu založenou na pojmu vzdálenosti mezi logickými termy. Cílem metody je minimalizace statisticky očekávaní chyby konstruování hypotézy. Metoda využívá znalost konkrétního pravděpodobnostního rozložen šumu v argumentech základních faktů, které jsou vstupními příklady cílového predikátu. Zvláště se zaměřuji na případ normálního rozložení, či jeho diskrétní aproximace. Nato představuji efektivní metodu detekce odlehlých hodnot, je za určitých podmínek ještě zlepšuje kvalitu výsledných teorií. Následně uvažuji případ, kdy metoda založená na vzdálenostních funkcích není použitelná a i pro tuto situaci dokazuji několik teoretických pravidel pro výběr optimální teorie. Tak analyzuji několik heuristických funkcí běžně užívaných pro hodnocen pravidel a dokazuji jejich některé vlastnosti, je považuji za důležité. Výsledky testuji jak na datech laboratorní velikosti, tak na datech ze skutečného aplikačního projektu.
Nakonec předvádím aplikaci ILP v problému dobýván znalost v oblasti telekomunikací. V projektu testuji některé teoretické výsledky z předešlých částí práce, ale tak ilustruji dal postupy typické pro praxi dobýván znalostí. V tomto kontextu tak představuji systém pro tvorbu definic atributů (rysů) prvého řádu, které jsem implementoval a použil v experimentálních testech.