Индуктивно логичко програмирање

Шаблон:Programming paradigms Индуктивно логичко програмирање (ИЛП) је подобласт машинског учења који користи логику програмирања као јединствену репрезентацију за примере, знање и хипотезе. Дало је кодирање познатог предзнања и скупа примера представљених као логична база чињеница, један ИЛП систем ће извести хипотеза логичких програма који обухвата све позитивне и ништа од негативних примера.

Шема: позитивни примери + негативни примери + предзнање => хипотеза.

Индуктивно логичко програмирање је посебно корисно у биоинформатици и обради природног језика. Ехуд Шапиро је положио теоријски темељ за индуктивно логичко програмирање^[1]^[2] и изградио своју прву примену (модел Инференце Система) 1981:^[3] Пролог програм који индуктивно закључене логичке програме из позитивних и негативних примера. Термин Индуктивно логичко програмирање је први пут уведено^[4] у рад Степхена Мугглетона 1991.^[5] Термин "индуктивно" овде се односи на филозофску (тј сугерише теорију да објасни посматране чињенице) више него на математичку (тј доказивања имовине за све чланове добро - организованог сета) индукцију.

Формална дефиниција

Претходно знање је дато као логичка теорија $B$ , обично у облику Хорн клаузуле које се користе у логичком програмирању. Позитивни и негативни примери су дати као целина $E^{+}$ и $E^{-}$ од unnegated и негираних подземних литерала. Исправно хипотеза $h$ је логичка пропозиција која задовољава следеће услове.^[6] | Потреба: | $B$ | $⊭$ | $E^{+}$ |- | Довољност: | $B \land h$ | $⊨$ | $E^{+}$ |- | Слаба конзистентност: | $B \land h$ | $⊭$ | $𝑓𝑎𝑙𝑠𝑒$ |- | Јака конзистентност: | $B \land h \land E^{-}$ | $⊭$ | $𝑓𝑎𝑙𝑠𝑒$ |} "Потреба" не намеће ограничавање $h$ , али забрањује сваку генерацију хипотеза све док се позитивне чињенице не објасне без ње. "Довољност" захтева никакву генерисану хипотезу $h$ за објашњење свих позитивних примера $E^{+}$ . "Слаба доследност" забрањује генерацију било које хипотезе $h$ која је у супротности са позадином знања $B$ . "Јака коинзистентност" такође забрањује стварање било које хипотезе h која није у складу са негативним примерима $E^{-}$ , с обзиром на претходно знање $B$ ; то подразумева "слабу конзистентност"; ако су дати никакви негативни примери, оба услова се поклапају. Џероски^[7] захтева само "довољност" (под називом "потпуност" тамо) и "Јаку доследност".

Пример

”

Следећи познати пример за учење дефиниција породичних односа користе скраћенице par : parent, fem : female, dau : daughter, g : George, h : Helen, m : Mary, t : Tom, n : Nancy, и e : Eve... То почиње од позадине знања (упореди слику)

𝑝𝑎𝑟 (h, m) \land 𝑝𝑎𝑟 (h, t) \land 𝑝𝑎𝑟 (g, m) \land 𝑝𝑎𝑟 (t, e) \land 𝑝𝑎𝑟 (n, e) \land 𝑓𝑒𝑚 (h) \land 𝑓𝑒𝑚 (m) \land 𝑓𝑒𝑚 (n) \land 𝑓𝑒𝑚 (e)

,

су позитивни примери

𝑑𝑎𝑢 (m, h) \land 𝑑𝑎𝑢 (e, t)

,

и тривијални предлог $𝑡𝑟𝑢𝑒$ да означи одсуство негативних примера.

Плоткинсова^[8]^[9] "Релативна најмања општа генерализација (Рног)" је приступ индуктивном логичком програмирању која се користи како би се добио предлог о томе како да се формално дефинише ћерка односно $𝑑𝑎𝑢$ .

Овај приступ користи следеће кораке.

Релативизује сваки позитиван пример буквално са комплетним предзнањем:
- $𝑑𝑎𝑢 (m, h) \leftarrow 𝑝𝑎𝑟 (h, m) \land 𝑝𝑎𝑟 (h, t) \land 𝑝𝑎𝑟 (g, m) \land 𝑝𝑎𝑟 (t, e) \land 𝑝𝑎𝑟 (n, e) \land 𝑓𝑒𝑚 (h) \land 𝑓𝑒𝑚 (m) \land 𝑓𝑒𝑚 (n) \land 𝑓𝑒𝑚 (e)$
- $𝑑𝑎𝑢 (e, t) \leftarrow 𝑝𝑎𝑟 (h, m) \land 𝑝𝑎𝑟 (h, t) \land 𝑝𝑎𝑟 (g, m) \land 𝑝𝑎𝑟 (t, e) \land 𝑝𝑎𝑟 (n, e) \land 𝑓𝑒𝑚 (h) \land 𝑓𝑒𝑚 (m) \land 𝑓𝑒𝑚 (n) \land 𝑓𝑒𝑚 (e)$ ,
Претвори у клаузулу нормаланог облика:
- $𝑑𝑎𝑢 (m, h) \lor \neg 𝑝𝑎𝑟 (h, m) \lor \neg 𝑝𝑎𝑟 (h, t) \lor \neg 𝑝𝑎𝑟 (g, m) \lor \neg 𝑝𝑎𝑟 (t, e) \lor \neg 𝑝𝑎𝑟 (n, e) \lor \neg 𝑓𝑒𝑚 (h) \lor \neg 𝑓𝑒𝑚 (m) \lor \neg 𝑓𝑒𝑚 (n) \lor \neg 𝑓𝑒𝑚 (e)$
- $𝑑𝑎𝑢 (e, t) \lor \neg 𝑝𝑎𝑟 (h, m) \lor \neg 𝑝𝑎𝑟 (h, t) \lor \neg 𝑝𝑎𝑟 (g, m) \lor \neg 𝑝𝑎𝑟 (t, e) \lor \neg 𝑝𝑎𝑟 (n, e) \lor \neg 𝑓𝑒𝑚 (h) \lor \neg 𝑓𝑒𝑚 (m) \lor \neg 𝑓𝑒𝑚 (n) \lor \neg 𝑓𝑒𝑚 (e)$ ,
Борба против сваког компатибилног^[10] пара^[11] литерала:
- $𝑑𝑎𝑢 (x_{m e}, x_{h t})$ од $𝑑𝑎𝑢 (m, h)$ и $𝑑𝑎𝑢 (e, t)$ ,
- $\neg 𝑝𝑎𝑟 (x_{h t}, x_{m e})$ од $\neg 𝑝𝑎𝑟 (h, m)$ и $\neg 𝑝𝑎𝑟 (t, e)$ ,
- $\neg 𝑓𝑒𝑚 (x_{m e})$ од $\neg 𝑓𝑒𝑚 (m)$ и $\neg 𝑓𝑒𝑚 (e)$ ,
- $\neg 𝑝𝑎𝑟 (g, m)$ од $\neg 𝑝𝑎𝑟 (g, m)$ и $\neg 𝑝𝑎𝑟 (g, m)$ , сличан за све остале литерале позадинског знања
- $\neg 𝑝𝑎𝑟 (x_{g t}, x_{m e})$ од $\neg 𝑝𝑎𝑟 (g, m)$ и $\neg 𝑝𝑎𝑟 (t, e)$ , и још много негираних литерала
Обриши све негиране литерале који садрже варијабле које се не јављају у позитивним литералима:
- након брисања свих негираних литерала који садрже друге променљиве од $x_{m e}, x_{h t}$ , само $𝑑𝑎𝑢 (x_{m e}, x_{h t}) \lor \neg 𝑝𝑎𝑟 (x_{h t}, x_{m e}) \lor \neg 𝑓𝑒𝑚 (x_{m e})$ Остаје, заједно са свим копненим литералима из знања позадине
Претвори клаузуле назад на Хорн форму:
- $𝑑𝑎𝑢 (x_{m e}, x_{h t}) \leftarrow 𝑝𝑎𝑟 (x_{h t}, x_{m e}) \land 𝑓𝑒𝑚 (x_{m e}) \land (all background knowledge facts)$

Добијена Хорн клаузула хипотеза $h$ добијена помоћу Риг приступа. Игнорисање позадине чињеница знања, клаузула неформално пише " $x_{m e}$ зове ћерку $x_{h t}$ ако $x_{h t}$ је родитељ од $x_{m e}$ и $x_{m e}$ је женско", што је уобичајено прихваћена дефиниција.

Што се тиче горенаведених услова, "Потреба" је задовољана јер предикат $𝑑𝑎𝑢$ се не појављује у позадини знања, која стога не може означити било коју имовину која садржи овај предикат, као што су позитивни примери. "Довољност" је задовољена обрачунатим хипотезама $h$ , пошто она, заједно са $𝑝𝑎𝑟 (h, m) \land 𝑓𝑒𝑚 (m)$ од позадинског знања, подразумева први позитиван пример $𝑑𝑎𝑢 (m, h)$ , и слично $h$ и $𝑝𝑎𝑟 (t, e) \land 𝑓𝑒𝑚 (e)$ из познавања позадине подразумева други позитиван пример $𝑑𝑎𝑢 (e, t)$ ."Слаба коинзистентност" је задовољена са $h$ , јер она држи $h$ у (коначној) Хербранд структури описа позадинског знања; слично за "Јака конзистентност".

Заједничка дефиниција бака односа, наиме. $𝑔𝑟𝑎 (x, z) \leftarrow 𝑓𝑒𝑚 (x) \land 𝑝𝑎𝑟 (x, y) \land 𝑝𝑎𝑟 (y, z)$ , не могу научити коришћењем горенаведеног приступа, пошто променљива $y$ се јавља само у телима клаузула; одговарајући литерали би били избрисана у 4. корака. Да би се превазишао овај пропуст, тај корак мора бити модификован тако да се може параметризовати са различитим литералима након селекције хеуристике. Историјски, имплементација ГОЛЕМ се заснива на Риг приступу.

Индуктивни логички програмски систем

Индуктивни логички програмски систем је програм који се узима као улаз логичких теорија $B, E^{+}, E^{-}$ и даје исправну хипотезу $H$ ВРТ теорије $B, E^{+}, E^{-}$ Алгоритам једног ИЛП система се састоји из два дела: хипотеза тражења и селекције хипотеза. Прво хипотеза је претрес са индуктивним поступком логичког програмирања, онда подскуп налази хипотезу (у већини система једна хипотеза) изабрану од стране избор алгоритма. Сортира бодове алгоритма, сваке од пронађени хипотеза и враћа оне са највећом оценом. Пример скор функција укључује минималну дужину компресије где је хипотеза са најнижом Колмогоровом комплексношчћу има највишу оцену и враћа се. ИЛП систем је комплетан акко за било какве улазе логичких теорија $B, E^{+}, E^{-}$ нека исправна хипотеза $H$ ВРТ ове улазне теорије може се наћи са својом хипотезом у истраживачкој процедури.

Претрага Хипотеза

Модерни ИЛП системи као што су Progol,^[5] Hail^[12] и Imparo^[13] проналазе хипотезу H користећи принцип инверзних елемената^[5] за теорију B, E, H: $B \land H ⊨ E ⟺ B \land \neg E ⊨ \neg H$ . Прво се конструише средња теорија F и назива се теорија моста која испуњава услове $B \land \neg E ⊨ F$ and $F ⊨ \neg H$ . Онда $H ⊨ \neg F$ , они генерализују негацију теорије моста F са anti-entailment. Међутим, рад на anti-entailment је високо не-детерминистички рачунски скуп. Дакле, алтернативна хипотеза претрага може се обавити помоћу рада инверзне супсумације (анти-супсумације) уместо што је мање недетерминистички од anti-entailment.

Питања потпуност поступка хипотеза за претрагу специфичног ИЛП система настају. На пример, Прогол хипотеза истраживања поступка на основу обрнутог entailment закључивања правила није завршен у Јамамото примеру.^[14] С друге стране, Импаро је завршена у anti-entailment поступку^[15] и његовој изузетно инверзној супсумацији^[16] поступка.

Имплементације

1BC и 1BC2: првог реда наивни Баиесова класификатори: (-{R|http://www.cs.bris.ac.uk/Research/MachineLearning/1BC/}-)
ACE (Комбиновани Мотор) (-{R|http://dtai.cs.kuleuven.be/ACE/}- Шаблон:Wayback)
Aleph (-{R|http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/}-)
Atom (-{R|http://www.ahlgren.info/research/atom/}- Шаблон:Wayback)
Claudien (-{R|http://dtai.cs.kuleuven.be/claudien/}- Шаблон:Webarchive)
DL-Learner (-{R|https://web.archive.org/web/20190815184411/http://dl-learner.org/}-)
DMax (-{R|http://dtai.cs.kuleuven.be/dmax/}- Шаблон:Wayback)
FOIL(-{R|ftp://ftp.cs.su.oz.au/pub/foil6.sh}-Шаблон:Мртва веза)
Golem (ILP) (-{R|http://www.doc.ic.ac.uk/~shm/Software/golem}-)
Imparo^[15]
Inthelex (INcremental THEory Learner from EXamples) (-{R|http://lacam.di.uniba.it:8000/systems/inthelex/}- Шаблон:Wayback)
Lime (-{R|https://web.archive.org/web/20020516195248/http://cs.anu.edu.au/people/Eric.McCreath/lime.html}-)
Mio (-{R|http://libra.msra.cn/Publication/3392493/mio-user-s-manual}- Шаблон:Webarchive)
MIS (Model Inference System) by Ehud Shapiro
Ontolearn (-{R|https://github.com/dice-group/Ontolearn}-)
PROGOL (-{R|http://www.doc.ic.ac.uk/~shm/Software/progol5.0}-)
RSD (-{R|https://web.archive.org/web/20070301162526/http://labe.felk.cvut.cz/~zelezny/rsd/}-)
Tertius (-{R|http://www.cs.bris.ac.uk/publications/Papers/1000545.pdf}-)
Warmr (сада укључени у ACE)
ProGolem (-{R|http://ilp.doc.ic.ac.uk/ProGolem/}-)^[17]^[18]

Види још

Референце

Шаблон:Reflist

Литература

Шаблон:Литература

Шаблон:Cite journal
Шаблон:Cite book
Visual example of inducing the grandparenthood relation by the Atom system. -{R|http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html}- Шаблон:Wayback

Шаблон:Литература крај

Шаблон:Нормативна контрола

↑ Shapiro, Ehud Y. Inductive inference of theories from facts, Research Report 192, Yale University, Department of Computer Science, 1981. Reprinted in J.-L. Lassez, G. Plotkin (Eds.), Computational Logic, The MIT Press. Cambridge, MA. (1991). стр. 199–254.
↑ Shapiro, Ehud Y. . Algorithmic program debugging. Cambridge, Mass. Шаблон:Page1
↑ Shapiro, Ehud Y. "The model inference system." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981.
↑ Luc De Raedt. A Perspective on Inductive Logic Programming. The Workshop on Current and Future Trends in Logic Programming, Shakertown, to appear in Springer LNCS, 1999. CiteSeerX: Шаблон:Url
↑ ^5,0 ^5,1 ^5,2 Шаблон:Cite journal
↑ Шаблон:Cite journal; here: Sect.2.1
↑ Шаблон:Citation; here: Sect.5.2.4
↑ Шаблон:Cite journal
↑ Шаблон:Cite journal
↑ i.e. sharing the same predicate symbol and negated/unnegated status
↑ in general: $n$ -tuple when $n$ positive example literals are given
↑ Ray, O., Broda, K., & Russo, A. M. (2003). Hybrid abductive inductive learning. In LNCS: Vol. 2835. Proceedings of the 13th international conference on inductive logic programming (pp. 311–328). Berlin: Springer.
↑ Kimber, T., Broda, K., & Russo, A. (2009). Induction on failure: learning connected Horn theories. In LNCS: Vol. 5753. Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning (pp. 169–181). Berlin: Springer.
↑ Akihiro Yamamoto. Which hypotheses can be found with inverse entailment? In Inductive Logic Programming, pages 296–308. Springer, 1997.
↑ ^15,0 ^15,1 Timothy Kimber. Learning definite and normal logic programs by induction on failure. PhD thesis, Imperial College London, 2012.
↑ David Toth (2014). Imparo is complete by inverse subsumption. arXiv:1407.3836
↑ Шаблон:Cite journal
↑ Шаблон:Cite journal

[1] Shapiro, Ehud Y. Inductive inference of theories from facts, Research Report 192, Yale University, Department of Computer Science, 1981. Reprinted in J.-L. Lassez, G. Plotkin (Eds.), Computational Logic, The MIT Press. Cambridge, MA. (1991). стр. 199–254.

[2] Shapiro, Ehud Y. . Algorithmic program debugging. Cambridge, Mass. Шаблон:Page1

[3] Shapiro, Ehud Y. "The model inference system." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981.

[4] Luc De Raedt. A Perspective on Inductive Logic Programming. The Workshop on Current and Future Trends in Logic Programming, Shakertown, to appear in Springer LNCS, 1999. CiteSeerX: Шаблон:Url

[muggleton1995inverse-5] 5,0 ^5,1 ^5,2 Шаблон:Cite journal

[6] Шаблон:Cite journal; here: Sect.2.1

[7] Шаблон:Citation; here: Sect.5.2.4

[8] Шаблон:Cite journal

[9] Шаблон:Cite journal

[10] .e. sharing the same predicate symbol and negated/unnegated status

[11] ral: $n$ -tuple when $n$ positive example literals are given

[12] Ray, O., Broda, K., & Russo, A. M. (2003). Hybrid abductive inductive learning. In LNCS: Vol. 2835. Proceedings of the 13th international conference on inductive logic programming (pp. 311–328). Berlin: Springer.

[13] Kimber, T., Broda, K., & Russo, A. (2009). Induction on failure: learning connected Horn theories. In LNCS: Vol. 5753. Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning (pp. 169–181). Berlin: Springer.

[14] Akihiro Yamamoto. Which hypotheses can be found with inverse entailment? In Inductive Logic Programming, pages 296–308. Springer, 1997.

[kimber2009induction-15] 15,0 ^15,1 Timothy Kimber. Learning definite and normal logic programs by induction on failure. PhD thesis, Imperial College London, 2012.

[16] David Toth (2014). Imparo is complete by inverse subsumption. arXiv:1407.3836

[17] Шаблон:Cite journal

[18] Шаблон:Cite journal

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]