Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Journal of Intelligent Information Systems
Erschienen in: Journal of Intelligent Information Systems 1/2016

01.02.2016

Policy-based memoization for ILP-based concept discovery systems

verfasst von: Alev Mutlu, Pinar Karagoz

Erschienen in: Journal of Intelligent Information Systems | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Inductive Programming Logic (ILP)-based concept discovery systems aim to find patterns that describe a target relation in terms of other relations provided as background knowledge. Such systems usually work within first order logic framework, build large search spaces, and have long running times. Memoization has widely been incorporated in concept discovery systems to improve their running times. One of the problems that memoization brings to such systems is the memory overhead which may be a bottleneck. In this work we propose policies that decide what types of concept descriptors to store in memotables and for how long to keep them. The proposed policies have been implemented as extensions to a concept discovery system called Tabular CRIS wEF, and the resulting system is named Policy-based Tabular CRIS. Effects of the proposed policies are evaluated on several datasets. The experimental results show that the proposed policies greatly improve the memory consumption while preserving the benefits introduced by memoization.
Vorheriger Artikel Labelset topic model for multi-label document classification
Nächster Artikel A multimodal approach for extracting content descriptive metadata from lecture videos

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
For detailed information about the dataset users may refer to King et al. (1996)
 
2
Our observation from our past studies is that 3 is a commonly used value for the concept descriptor length; however, the maximum clause length depends greatly on the granularity of the background knowledge. Therefore, clause length limit of 3 may not be sufficient to find good concept descriptors for some domains. By using this limit one can incur less accurate concept descriptors. One reason for using this length limit in our experiments was to obtain concept descriptors under less amount of execution time.
 
3
Although it is commonly used to evaluate the performance of parallelized computer programs, several ILP-based concept discovery systems that incorporate memoization followed this metric to evaluate their proposed methods (Blockeel et al. 2002; Costa et al. 2003; Struyf and Blockeel 2003).
 
Literatur
Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A.I. (1996). Fast discovery of association rules. In: Advances in Knowledge Discovery and Data Mining, pp. 307–328. AAAI/MIT Press.
Blaták, J., & Popelínskỳ, L. (2006). Drap: A framework for distributed mining first-order frequent patterns. In: Proceedings of the 16th conference on inductive logic programming, pp. 25–27.
Blockeel, H., Dehaspe, L., Demoen, B., Janssens, G., Vandecasteele, H. (2002). Improving the efficiency of inductive logic programming through the use of query packs. Journal of Artificial Intelligence Research, 16, 135–166.MATH
Cohen, W.W. (1995). Learning to classify english text with ilp methods. Advances in inductive logic programming, 32, 124–143.
Costa, V.S., Srinivasan, A., Camacho, R., Blockeel, H., Demoen, B., Janssens, G., Struyf, J., Vandecasteele, H., Laer, W.V. (2003). Query transformations for improving the efficiency of ILP systems. Journal of Machine Learning Research, 4, 465–491.MATH
Davis, M., Liu, W., Miller, P., Redpath, G. (2011). Detecting anomalies in graphs with numeric labels. In: CIKM, pp. 1197–1202.
Dehaspe, L., & Raedt, L.D. (1995). Parallel inductive logic programming. In Proceedings of the MLnet Familiarization Workshop on Statistics, Machine Learning and Knowledge Discovery in Databases, pp. 112–117.
Dehaspe, L., & Raedt, L.D. (1997). Mining association rules in multiple relations. In: N. Lavrac, S. Dzeroski (eds.) ILP, Lecture Notes in Computer Science, vol. 1297, pp. 125–132. Springer.
Divina, F., Keijzer, M., Marchiori, E. (2003). A method for handling numerical attributes in ga-based inductive concept learners. In: E. Cantú-Paz, J.A. Foster, K. Deb, L. Davis, R. Roy, U.M. O’Reilly, H.G. Beyer, R.K. Standish, G. Kendall, S.W. Wilson, M. Harman, J. Wegener, D. Dasgupta, M.A. Potter, A.C. Schultz, K.A. Dowsland, N. Jonoska, J.F. Miller (eds.) GECCO, Lecture Notes in Computer Science, vol. 2723, pp. 898–908. Springer.
Dolsak, B. (2002). Finite element mesh design expert system. Knowledge-based Systems, 15 (8), 315–322.CrossRef
Dolsak, B., & Muggleton, S. (1992). The application of Inductive Logic Programming to finite element mesh design. In: Inductive Logic Programming. Academic Press.
Doncescu, A., Waissman, J., Richard, G., Roux, G. (2002). Characterization of bio-chemical signals by inductive logic programming. Knowledge-Based Systems, 15 (1–2), 129–137.CrossRef
Dong, Y., Du, X., Ramakrishna, Y., Ramakrishnan, C., Ramakrishnan, I., Smolka, S., Sokolsky, O., Stark, E., Warren, D. (1999). Fighting livelock in the i-Protocol: A comparative study of verification tools. In TACAS’99: Proceedings of the 5th International Conference on Tools and Algorithms for Construction and Analysis of Systems, Lecture Notes in Computer Science, vol. 1579, pp. 74–88. Springer Berlin / Heidelberg.
Džeroski, S. (1993). Handling imperfect data in inductive logic programming. In: Proceedings of the Fourth Scandinavian Conference on Artificial intelligence—93, SCAI93, pp. 111–125. IOS Press, Amsterdam, The Netherlands, The Netherlands.
Džeroski, S., Dehaspe, L., Ruck, B., Walley, W. (1994). Classification of river water quality data using machine learning. In: Proceedings of the 5th International Conference on the Development and Application of Computer Techniques to Environmental Studies, Vol. I: Pollution modelling, pp. 129–137.
Dzeroski, S. (2003). Multi-relational data mining: An introduction. SIGKDD Explorations, 5 (1), 1–16.CrossRef
Dzeroski, S., Jacobs, N., Molina, M., Moure, C., Muggleton, S., Laer, W.V. (1998). Detecting traffic problems with ILP. In: ILP’98: Proceedings of the 8th International Workshop on Inductive Logic Programming, pp. 281–290.
Fayyad, U.M., & Irani, K.B. (1993). Multi-interval discretization of continuous-valued attributes for classification learning. In: R. Bajcsy (ed) IJCAI, pp. 1022–1029. Morgan Kaufmann.
Fonseca, N., Silva, F., Camacho, R. (2006). April An inductive logic programming system. In: JELIA’06: Proceedings of the 10th European Conference on Logics in Artificial Intelligence, Lecture Notes in Computer Science, vol. 4160, pp. 481–484. Springer Berlin / Heidelberg.
Goutte, C., & Gaussier, E. (2005). A probabilistic interpretation of precision, recall and f-score, with implication for evaluation. In: ECIR’05: Proceedings of the 27th European Conference on Information Retrieval, pp. 345–359. Springer.
Graefe, G., & McKenna, W. (1993). The volcano optimizer generator: extensibility and efficient search. In: ICDE’93: Proceedings of the 9th International Conference on Data Engineering, pp. 209–218.
James, C. (1996). Part-of-speech disambiguation using ilp. Tech. rep., PRG-TR-25-96 Oxford University Computing Laboratory.
Jia, Y., Zhang, J., Huan, J. (2011). An efficient graph-mining method for complicated and noisy data with real-world applications. Knowledge Information System, 28 (2), 423–447.CrossRef
Kavurucu, Y., Senkul, P., Toroslu, I.H. (2009). ILP-based concept discovery in multi-relational data mining. Expert Systems with Applications, 36 (9), 11,418–11,428.CrossRef
Kavurucu, Y., Senkul, P., Toroslu, I.H. (2009). ILP-based concept discovery in multi-relational data mining. Expert Systems with Applications, 36 (9), 11,418–11,428.CrossRef
Kavurucu, Y., Senkul, P., Toroslu, I.H. (2010). Concept discovery on relational databases: New techniques for search space pruning and rule quality improvement. Knowledge-Based Systems, 23 (8), 743–756.CrossRef
King, R.D. (2004). Applying inductive logic programming to predicting gene function. AI Magazine, 25 (1), 57.
King, R.D., Muggleton, S.H., Srinivasan, A., Sternberg, M. (1996). Structure-activity relationships derived by machine learning: The use of atoms and their bond connectivities to predict mutagenicity by inductive logic programming. Proceedings of the National Academy of Sciences, 93 (1), 438–442.CrossRef
Krogel, M.A., & Wrobel, S. (2001). Transformation-based learning using multirelational aggregation. In: C. Rouveirol, M. Sebag (eds.) ILP, Lecture Notes in Computer Science, vol. 2157, pp. 142–155. Springer.
Kuželka, O., Szabóová, A., železnỳ, F. (2013). A method for reduction of examples in relational learning. Journal of Intelligent Information Systems, 1–27. 10.​1007/​s10844-013-0294-z.
Lavrac, N., & Dzeroski, S. (1993). Inductive Logic Programming: Techniques and Applications. Routledge, New York, NY, 10001.
Lavrač, N., Džeroski, S., Grobelnik, M. (1991). Learning nonrecursive definitions of relations with LINUS. In: Y. Kodratoff (ed.) Proceedings of the 5th European Working Session on Learning, Lecture Notes in Artificial Intelligence, vol. 482, pp. 265–281. Springer-Verlag.
Li, H.F., Huang, H.Y., Lee, S.Y. (2011). Fast and memory efficient mining of high-utility itemsets from data streams: with and without negative item profits. Knowledge and Information Systems, 28, 495–522.CrossRef
Michalski, R., & Larson, J. (1997). Inductive inference of VL decision rules. In: Workshop on Pattern-Directed Inference Systems, vol. 63, pp. 33–44. SIGART Newsletter, ACM.
Mooney, R.J., & Califf, M.E. (1995). Induction of first-order decision lists: Results on learning the past tense of english verbs. Journal of Artificial Intelligence Research, 3, 1–24. 10.​1613/​jair.​148.
Muggleton, S. (1990). Inductive logic programming. In: ALT, pp. 42–62.
Muggleton, S. (1995). Inverse entailment and Progol. New Generation Computing. Special issue on Inductive Logic Programming, 13 (3-4), 245–286.
Muggleton, S. (1999). Inductive Logic Programming. In: The MIT Encyclopedia of the Cognitive Sciences (MITECS). MIT Press.
Muggleton, S., & Buntine, W. (1988). Machine invention of first order predicates by inverting resolution. In: ML’88: Proceedings of the 5th International Conference on Machine Learning, pp. 339–351.
Muggleton, S., & Feng, C. (1990). Efficient induction of logic programs. In: ALT’90: Proceedings of the 1st Conference on Algorithmic Learning Theory, pp. 368–381.
Mutlu, A., Berk, M.A., Senkul, P. (2010). Improving the time efficiency of ILP-based multi-relational concept discovery with dynamic programming approach. In: ISCIS’10: Proceedings of the 25th International Symposium on Computer and Information Sciences, pp. 43–50.
Mutlu, A., & Senkul, P. (2012). Improving hash table hit ratio of an ilp-based concept discovery system with memoization capabilities. In: ISCIS’12: Proceedings of the 27th International Symposium on Computer and Information Sciences.
Mutlu, A., & Senkul, P. (2014). Improving hit ratio of ILP-based concept discovery system with memoization. Computer Journal, 57 (1), 138–153.CrossRef
Nassif, H., Al-Ali, H., Khuri, S., Keirouz, W., Page, D. (2010). An inductive logic programming approach to validate hexose binding biochemical knowledge. In: ILP’09: Proceedings of the 19th International Conference on Inductive Logic Programming, pp. 149–165. Springer-Verlag.
Nědellec, C., Adě, H., Bergadano, F., Tausend, B. (1996). Declarative bias in ILP.
Pazzani, M.J., Brunk, C., Silverstein, G. (1991). A knowledge-intensive approach to learning relational concepts. In: ML, pp. 432–436.
Penn, G., & Munteanu, C. (2003). A tabulation-based parsing method that reduces copying. In: ACL’03: Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, vol. 1, pp. 200–207.
Pompe, U., & Kononenko, I. (1995). Linear space induction in first order logic with relieff. Mathematical and Statistical Methods in Artificial Intelligence. CISM Course and Lecture Notes, 363, 185–220.MathSciNetMATH
Quinlan, J.R. (1990). Learning logical definitions from relations. Machine Learning, 5 (3), 239–266.
Robnik-Sikonja, M., & Kononenko, I. (2003). Theoretical and empirical analysis of relieff and rrelieff. Machine Learning, 53 (1–2), 23–69.CrossRefMATH
Rocha, R. (2007). On improving the efficiency and robustness of table storage mechanisms for tabled evaluation. In: PADL, pp. 155–169.
Rocha, R., Fonseca, N.A., Costa, V.S. (2005). On applying tabling to inductive logic programming. In: ECML’05: Proceeedings of the 16th European Conference on Machine Learning, pp. 707–714.
Rocha, R., Silva, F., Costa, V.S. (2000). YapTab: A Tabling Engine Designed to Support Parallelism. In: TAPD’00: Proceedings of the 2nd Conference on Tabulation in Parsing and Deduction, pp. 77–87.
Romero, O.E., Gonzalez, J.A., Holder, L.B. (2011). Handling of numeric ranges with the subdue system. In: FLAIRS Conference.
Sagonas, K.F., & Stuckey, P.J. (2004). Just enough tabling. In: PPDP, pp. 78–89.
Sato, T. (2008). A glimpse of symbolic-statistical modeling by prism. Journal of Intelligent Information Systems, 31 (2), 161–176.CrossRef
Sebag, M., & Rouveirol, C. (1997). Tractable induction and classification in first order logic via stochastic matching. In: IJCAI’97: Proceedings of the 15th International Joint Conferences on Artificial Intelligence, pp. 888–893.
Shapiro, E. (1983). Algorithmic Program Debugging. The MIT Press.
Skillicorn, D.B., & Wang, Y. (2001). Parallel and sequential algorithms for data mining using inductive logic. Knowledge and Information Systems, 3, 405–421.CrossRefMATH
Srinivasan, A. (1999). A study of two sampling methods for analyzing large datasets with ILP. Data Mining and Knowledge Discovery, 3 (1), 95–123.CrossRef
Srinivasan, A., King, R.D., Muggleton, S.H., Sternberg, M. (1997). The predictive toxicology evaluation challenge. In: IJCAI-97: Proceedings of the 15th International Joint Conference on Artificial Intelligence, pp. 1–6.
Srinivasan, A., Muggleton, S.H., King, R., Sternberg, M. (1994). Mutagenesis: Ilp experiments in a non-determinate biological domain. In: Proceedings of the 4th International Workshop on Inductive Logic Programming, volume 237 of GMD-Studien, pp. 217–232.
Struyf, J., & Blockeel, H. (2003). Query optimization in inductive logic programming by reordering literals. In: ILP’03: Proceedings of the 13th International Conference on Inductive Logic Programming, pp. 329–346. Springer-Verlag.
Tran, T.N., Satou, K., Ho, T.B. (2005). Using inductive logic programming for predicting protein-protein interactions from multiple genomic data. PKDD, pp. 321–330.
Troncon, R., Demoen, B., Janssens, G. (2006). When tabling does not work. In: Proceedings of Colloquium on Implementation of Constraint Logic Programming Systems.
Tveit, A., & Hetland, M. (2003). Multicategory incremental proximal support vector classifiers. In: V. Palade, R. Howlett, L. Jain (eds.) Knowledge-Based Intelligent Information and Engineering Systems, Lecture Notes in Computer Science, vol. 2773, pp. 386–392. Springer Berlin / Heidelberg.
Metadaten
Titel
Policy-based memoization for ILP-based concept discovery systems
verfasst von
Alev Mutlu
Pinar Karagoz
Publikationsdatum
01.02.2016
Verlag
Springer US
Erschienen in
Journal of Intelligent Information Systems / Ausgabe 1/2016
Print ISSN: 0925-9902
Elektronische ISSN: 1573-7675
DOI
https://doi.org/10.1007/s10844-015-0354-7

Weitere Artikel der Ausgabe 1/2016

Journal of Intelligent Information Systems 1/2016 Zur Ausgabe

OriginalPaper

Proximity-based federation of smart objects

OriginalPaper

An efficient and flexible scanning of databases of protein secondary structures

OriginalPaper

A framework for enriching Data Warehouse analysis with Question Answering systems

OriginalPaper

A sentence structure-based approach to unsupervised author identification

OriginalPaper

Labelset topic model for multi-label document classification

OriginalPaper

A multimodal approach for extracting content descriptive metadata from lecture videos