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

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

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

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

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

Претходно знање је дато као логичка теорија $B$ , обично у облику Хорн клаузуле које се користе у логичком програмирању. Позитивни и негативни примери су дати као целина $E^{+}$ и $E^{-}$ од unnegated и негираних подземних литерала. Исправно хипотеза $h$ је логичка пропозиција која задовољава следеће услове.^[6] | Потреба: | $B$ | $\not \models$ | $E^{+}$ |- | Довољност: | $B\land h$ | $\models$ | $E^{+}$ |- | Слаба конзистентност: | $B\land h$ | $\not \models$ | ${\textit {false}}$ |- | Јака конзистентност: | $B\land h\land E^{-}$ | $\not \models$ | ${\textit {false}}$ |} "Потреба" не намеће ограничавање $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... То почиње од позадине знања (упореди слику)

{\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)

,

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

{\textit {dau}}(m,h)\land {\textit {dau}}(e,t)

,

и тривијални предлог ${\textit {true}}$ да означи одсуство негативних примера.

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

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

Релативизује сваки позитиван пример буквално са комплетним предзнањем:
- ${\textit {dau}}(m,h)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)$
- ${\textit {dau}}(e,t)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)$ ,
Претвори у клаузулу нормаланог облика:
- ${\textit {dau}}(m,h)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)$
- ${\textit {dau}}(e,t)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)$ ,
Борба против сваког компатибилног^[10] пара^[11] литерала:
- ${\textit {dau}}(x_{me},x_{ht})$ од ${\textit {dau}}(m,h)$ и ${\textit {dau}}(e,t)$ ,
- $\lnot {\textit {par}}(x_{ht},x_{me})$ од $\lnot {\textit {par}}(h,m)$ и $\lnot {\textit {par}}(t,e)$ ,
- $\lnot {\textit {fem}}(x_{me})$ од $\lnot {\textit {fem}}(m)$ и $\lnot {\textit {fem}}(e)$ ,
- $\lnot {\textit {par}}(g,m)$ од $\lnot {\textit {par}}(g,m)$ и $\lnot {\textit {par}}(g,m)$ , сличан за све остале литерале позадинског знања
- $\lnot {\textit {par}}(x_{gt},x_{me})$ од $\lnot {\textit {par}}(g,m)$ и $\lnot {\textit {par}}(t,e)$ , и још много негираних литерала
Обриши све негиране литерале који садрже варијабле које се не јављају у позитивним литералима:
- након брисања свих негираних литерала који садрже друге променљиве од $x_{me},x_{ht}$ , само ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ Остаје, заједно са свим копненим литералима из знања позадине
Претвори клаузуле назад на Хорн форму:
- ${\textit {dau}}(x_{me},x_{ht})\leftarrow {\textit {par}}(x_{ht},x_{me})\land {\textit {fem}}(x_{me})\land ({\text{all background knowledge facts}})$

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

Што се тиче горенаведених услова, "Потреба" је задовољана јер предикат ${\textit {dau}}$ се не појављује у позадини знања, која стога не може означити било коју имовину која садржи овај предикат, као што су позитивни примери. "Довољност" је задовољена обрачунатим хипотезама $h$ , пошто она, заједно са ${\textit {par}}(h,m)\land {\textit {fem}}(m)$ од позадинског знања, подразумева први позитиван пример ${\textit {dau}}(m,h)$ , и слично $h$ и ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ из познавања позадине подразумева други позитиван пример ${\textit {dau}}(e,t)$ ."Слаба коинзистентност" је задовољена са $h$ , јер она држи $h$ у (коначној) Хербранд структури описа позадинског знања; слично за "Јака конзистентност".

Заједничка дефиниција бака односа, наиме. ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(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\models E\iff B\land \neg E\models \neg H$ . Прво се конструише средња теорија F и назива се теорија моста која испуњава услове $B\land \neg E\models F$ and $F\models \neg H$ . Онда $H\models \neg F$ , они генерализују негацију теорије моста F са anti-entailment. Међутим, рад на anti-entailment је високо не-детерминистички рачунски скуп. Дакле, алтернативна хипотеза претрага може се обавити помоћу рада инверзне супсумације (анти-супсумације) уместо што је мање недетерминистички од anti-entailment.

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

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

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

Види још

Референце

^ 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. . MIT Press. 1983. ISBN 978-0-262-19218-7.
^ 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: 10.1.1.56.1790
^ ^а ^б ^в Muggleton, S. (1991). „Inductive logic programming”. New Generation Computing. 8 (4): 295—318. doi:10.1007/BF03037089.
^ Muggleton, Stephen (1999). „Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic”. Artificial Intelligence. 114: 283—296. doi:10.1016/s0004-3702(99)00067-3. ; here: Sect.2.1
^ Džeroski, Sašo (1996), „Inductive Logic Programming and Knowledge Discovery in Databases”, Ур.: Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R., Advances in Knowledge Discovery and Data Mining, MIT Press, стр. 117—152 ; here: Sect.5.2.4
^ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D., ур. „A Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 5: 153—163.
^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D., ур. „A Further Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 6: 101—124.
^ 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.
^ ^а ^б 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
^ Muggleton, Stephen; Santos, Jose; Tamaddoni-Nezhad, Alireza (2009). „ProGolem: a system based on relative minimal generalization” (PDF). ILP.
^ Santos, Jose; Nassif, Houssam; Page, David; Muggleton, Stephen; Sternberg, Mike (2012). „Automated identification of features of protein-ligand interactions using Inductive Logic Programming: a hexose binding case study” (PDF). BMC Bioinformatics. 13: 162. doi:10.1186/1471-2105-13-162. Архивирано из оригинала (PDF) 03. 03. 2016. г. Приступљено 08. 01. 2016.

Литература

Muggleton, S.; De Raedt, L. (1994). „Inductive Logic Programming: Theory and methods”. The Journal of Logic Programming. 19-20: 629—679. doi:10.1016/0743-1066(94)90035-3.
Lavrac, N.; Dzeroski, S. (1994). Inductive Logic Programming: Techniques and Applications. New York: Ellis Horwood. ISBN 978-0-13-457870-5. Архивирано из оригинала 6. 9. 2004. г. Приступљено 8. 1. 2016.
Visual example of inducing the grandparenthood relation by the Atom system. http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html Архивирано на сајту Wayback Machine (26. март 2014)

[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. . MIT Press. 1983. ISBN 978-0-262-19218-7.

[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: 10.1.1.56.1790

[muggleton1995inverse-5] а ^б ^в Muggleton, S. (1991). „Inductive logic programming”. New Generation Computing. 8 (4): 295—318. doi:10.1007/BF03037089.

[6] Muggleton, Stephen (1999). „Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic”. Artificial Intelligence. 114: 283—296. doi:10.1016/s0004-3702(99)00067-3. ; here: Sect.2.1

[7] Džeroski, Sašo (1996), „Inductive Logic Programming and Knowledge Discovery in Databases”, Ур.: Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R., Advances in Knowledge Discovery and Data Mining, MIT Press, стр. 117—152 ; here: Sect.5.2.4

[8] Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D., ур. „A Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 5: 153—163.

[9] Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D., ур. „A Further Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 6: 101—124.

[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] а ^б 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] Muggleton, Stephen; Santos, Jose; Tamaddoni-Nezhad, Alireza (2009). „ProGolem: a system based on relative minimal generalization” (PDF). ILP.

[18] Santos, Jose; Nassif, Houssam; Page, David; Muggleton, Stephen; Sternberg, Mike (2012). „Automated identification of features of protein-ligand interactions using Inductive Logic Programming: a hexose binding case study” (PDF). BMC Bioinformatics. 13: 162. doi:10.1186/1471-2105-13-162. Архивирано из оригинала (PDF) 03. 03. 2016. г. Приступљено 08. 01. 2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]