SpringerLink
Log in

ENIGMA-NG: Efficient Neural and Gradient-Boosted Inference Guidance for E

  • Conference paper
  • First Online:
Automated Deduction – CADE 27 (CADE 2019)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 11716))

Included in the following conference series:

  • 927 Accesses

Abstract

We describe an efficient implementation of given clause selection in saturation-based automated theorem provers, extending the previous ENIGMA approach. Unlike in the first ENIGMA implementation where a fast linear classifier is trained and used together with manually engineered features, we have started to experiment with more sophisticated state-of-the-art machine learning methods such as gradient boosted trees and recursive neural networks. In particular, the latter approach poses challenges in terms of efficiency of clause evaluation, however, we show that deep integration of the neural evaluation with the ATP data-structures can largely amortize this cost and lead to competitive real-time results. Both methods are evaluated on a large dataset of theorem proving problems and compared with the previous approaches. The resulting methods improve on the manually designed clause guidance, providing the first practically convincing application of gradient-boosted and neural clause guidance in saturation-style automated theorem provers.

Supported by the ERC Consolidator grant no. 649043 AI4REASON, and by the Czech project AI&Reasoning CZ.02.1.01/0.0/0.0/15_003/0000466 and the European Regional Development Fund.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Spain)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 67.40
Price includes VAT (Spain)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 83.19
Price includes VAT (Spain)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Other, less immediately relevant, previous work on combining machine learning with automated theorem proving includes, e.g., [6, 8, 9, 11, 39].

  2. 2.

    We use the XGBoost parameter \(\texttt {scale\_pos\_weight}\).

  3. 3.

    Due to various numerical problems with deep recursive networks we have obtained better results with ReLU6, defined by \(\min (\max (0,x),6)\), or \(\tanh \).

  4. 4.

    https://pytorch.org/cppdocs/.

  5. 5.

    For instance, using the probability (1) for a more fine-grained order on clauses dictated by the neural model.

  6. 6.

    The benchmark can be found at https://github.com/JUrban/MPTP2078. For all the remaining materials for reproducing the experiments please check out the repository https://github.com/ai4reason/eprover-data/tree/master/CADE-19.

  7. 7.

    This appears to be a reasonable waiting time for, e.g., the users of ITP hammers [5].

  8. 8.

    Combining the dimensions for the clause and the conjecture.

  9. 9.

    Moreover, we always try to put examples with the same conjecture G into the same batch to share the time for recomputing the representation of G.

  10. 10.

    For \(\mathcal {M}_\text {lin}\), we show the numbers after five iterations of the boosting loop (see Sect. 3.2). The values in the first round were 40.81% for the positive and 98.62% for the negative rate.

  11. 11.

    We have also measured how much \(\mathcal {S}\) benefits from increased time limits. It solves 1099 problems in 20 s and 1137 problems in 300 s.

  12. 12.

    This metric is similar in spirit to given clause utilization introduced by Schulz and Möhrmann [41].

  13. 13.

    Note that more global caching (of, e.g., whole clauses and frequent combinations of literals) across multiple problems may further amortize the cost of the neural evaluation. This is left as future work here.

References

  1. Alama, J., Heskes, T., Kühlwein, D., Tsivtsivadze, E., Urban, J.: Premise selection for mathematics by corpus analysis and kernel methods. J. Autom. Reason. 52(2), 191–213 (2014)

    Article  MathSciNet  Google Scholar 

  2. Alemi, A.A., Chollet, F., Eén, N., Irving, G., Szegedy, C., Urban, J.: DeepMath - deep sequence models for premise selection. In: Lee, D.D., Sugiyama, M., Luxburg, U.V., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, Barcelona, Spain, 5–10 December 2016, pp. 2235–2243 (2016)

    Google Scholar 

  3. Bancerek, G., et al.: Mizar: state-of-the-art and beyond. In: Kerber, M., Carette, J., Kaliszyk, C., Rabe, F., Sorge, V. (eds.) CICM 2015. LNCS (LNAI), vol. 9150, pp. 261–279. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-20615-8_17

    Chapter  Google Scholar 

  4. Blanchette, J.C., Greenaway, D., Kaliszyk, C., Kühlwein, D., Urban, J.: A learning-based fact selector for Isabelle/HOL. J. Autom. Reason. 57(3), 219–244 (2016)

    Article  MathSciNet  Google Scholar 

  5. Blanchette, J.C., Kaliszyk, C., Paulson, L.C., Urban, J.: Hammering towards QED. J. Formalized Reason. 9(1), 101–148 (2016)

    MathSciNet  MATH  Google Scholar 

  6. Bridge, J.P., Holden, S.B., Paulson, L.C.: Machine learning for first-order theorem proving - learning to select a good heuristic. J. Autom. Reason. 53(2), 141–172 (2014)

    Article  MathSciNet  Google Scholar 

  7. Chen, T., Guestrin, C.: XGBoost: a scalable tree boosting system. In: KDD, pp. 785–794. ACM (2016)

    Google Scholar 

  8. Denzinger, J., Fuchs, M., Goller, C., Schulz, S.: Learning from previous proof experience. Technical report AR99-4, Institut für Informatik, Technische Universität München (1999)

    Google Scholar 

  9. Ertel, W., Schumann, J.M.P., Suttner, C.B.: Learning heuristics for a theorem prover using back propagation. In: Retti, J., Leidlmair, K. (eds.) 5. Österreichische Artificial Intelligence-Tagung. INFORMATIK, vol. 208, pp. 87–95. Springer, Heidelberg (1989). https://doi.org/10.1007/978-3-642-74688-8_10

    Chapter  Google Scholar 

  10. Fan, R.-E., Chang, K.-W., Hsieh, C.-J., Wang, X.-R., Lin, C.-J.: LIBLINEAR: a library for large linear classification. J. Mach. Learn. Res. 9, 1871–1874 (2008)

    MATH  Google Scholar 

  11. Färber, M., Brown, C.: Internal guidance for satallax. In: Olivetti and Tiwari [33], pp. 349–361

    Google Scholar 

  12. Färber, M., Kaliszyk, C., Urban, J.: Monte Carlo tableau proof search. In: de Moura, L. (ed.) CADE 2017. LNCS (LNAI), vol. 10395, pp. 563–579. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63046-5_34

    Chapter  Google Scholar 

  13. Gauthier, T., Kaliszyk, C.: Premise selection and external provers for HOL4. In: Certified Programs and Proofs (CPP 2015) (2015). https://doi.org/10.1145/2676724.2693173

  14. Goertzel, Z., Jakubův, J., Schulz, S., Urban, J.: ProofWatch: watchlist guidance for large theories in E. In: Avigad, J., Mahboubi, A. (eds.) ITP 2018. LNCS, vol. 10895, pp. 270–288. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94821-8_16

    Chapter  Google Scholar 

  15. Goertzel, Z., Jakubuv, J., Urban, J.: ProofWatch meets ENIGMA: first experiments. In: Barthe, G., Korovin, K., Schulz, S., Suda, M., Sutcliffe, G., Veanes, M. (eds.) LPAR-22 Workshop and Short Paper Proceedings. Kalpa Publications in Computing, vol. 9, pp. 15–22. EasyChair (2018)

    Google Scholar 

  16. Goller, C., Küchler, A.: Learning task-dependent distributed representations by backpropagation through structure. In: Proceedings of International Conference on Neural Networks (ICNN 1996), vol. 1, pp. 347–352, June 1996

    Google Scholar 

  17. Gottlob, G., Sutcliffe, G., Voronkov, A. (eds.): Global Conference on Artificial Intelligence, GCAI 2015, Tbilisi, Georgia, 16–19 October 2015. EPiC Series in Computing, vol. 36. EasyChair (2015)

    Google Scholar 

  18. Hochreiter, S., Schmidhuber, J.: Long short-term memory. Neural Comput. 9, 1735–1780 (1997)

    Article  Google Scholar 

  19. Jakubův, J., Urban, J.: ENIGMA: efficient learning-based inference guiding machine. In: Geuvers, H., England, M., Hasan, O., Rabe, F., Teschke, O. (eds.) CICM 2017. LNCS (LNAI), vol. 10383, pp. 292–302. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62075-6_20

    Chapter  Google Scholar 

  20. Jakubův, J., Urban, J.: Enhancing ENIGMA given clause guidance. In: Rabe, F., Farmer, W.M., Passmore, G.O., Youssef, A. (eds.) CICM 2018. LNCS (LNAI), vol. 11006, pp. 118–124. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96812-4_11

    Chapter  Google Scholar 

  21. Jakubův, J., Urban, J.: Hierarchical invention of theorem proving strategies. AI Commun. 31(3), 237–250 (2018)

    Article  MathSciNet  Google Scholar 

  22. Jakubuv, J., Urban, J.: BliStrTune: hierarchical invention of theorem proving strategies. In: Bertot, Y., Vafeiadis, V. (eds.) Proceedings of the 6th ACM SIGPLAN Conference on Certified Programs and Proofs, CPP 2017, Paris, France, 16–17 January 2017, pp. 43–52. ACM (2017)

    Google Scholar 

  23. Joulin, A., Grave, E., Bojanowski, P., Mikolov, T.: Bag of tricks for efficient text classification. In: Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics, Short Papers, vol. 2, pp. 427–431. Association for Computational Linguistics, April 2017

    Google Scholar 

  24. Kaliszyk, C., Urban, J.: Learning-assisted automated reasoning with Flyspeck. J. Autom. Reason. 53(2), 173–213 (2014)

    Article  MathSciNet  Google Scholar 

  25. Kaliszyk, C., Urban, J.: FEMaLeCoP: fairly efficient machine learning connection prover. In: Davis, M., Fehnker, A., McIver, A., Voronkov, A. (eds.) LPAR 2015. LNCS, vol. 9450, pp. 88–96. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48899-7_7

    Chapter  Google Scholar 

  26. Kaliszyk, C., Urban, J., Michalewski, H., Olsák, M.: Reinforcement learning of theorem proving. In: Bengio, S., Wallach, H.M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, Canada, Montréal, 3–8 December 2018, pp. 8836–8847 (2018)

    Google Scholar 

  27. Kaliszyk, C., Urban, J., Vyskocil, J.: Efficient semantic features for automated reasoning over large theories. In: IJCAI, pp. 3084–3090. AAAI Press (2015)

    Google Scholar 

  28. Kovács, L., Voronkov, A.: First-order theorem proving and Vampire. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 1–35. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39799-8_1

    Chapter  Google Scholar 

  29. Kuehlwein, D., Urban, J.: Learning from multiple proofs: first experiments. In: Fontaine, P., Schmidt, R.A., Schulz, S. (eds.) PAAR-2012. EPiC Series, vol. 21, pp. 82–94. EasyChair (2013)

    Google Scholar 

  30. Kühlwein, D., van Laarhoven, T., Tsivtsivadze, E., Urban, J., Heskes, T.: Overview and evaluation of premise selection techniques for large theory mathematics. In: Gramlich, B., Miller, D., Sattler, U. (eds.) IJCAR 2012. LNCS (LNAI), vol. 7364, pp. 378–392. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31365-3_30

    Chapter  Google Scholar 

  31. Loos, S.M., Irving, G., Szegedy, C., Kaliszyk, C.: Deep network guided proof search. In: Eiter, T., Sands, D. (eds.) LPAR-21, 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Maun, Botswana, 7–12 May 2017. EPiC Series in Computing, vol. 46, pp. 85–105. EasyChair (2017)

    Google Scholar 

  32. Meng, J., Paulson, L.C.: Translating higher-order clauses to first-order clauses. J. Autom. Reason. 40(1), 35–60 (2008)

    Article  MathSciNet  Google Scholar 

  33. Olivetti, N., Tiwari, A. (eds.): IJCAR 2016. LNCS (LNAI), vol. 9706. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40229-1

    Book  MATH  Google Scholar 

  34. Otten, J., Bibel, W.: leanCoP: lean connection-based theorem proving. J. Symb. Comput. 36(1–2), 139–161 (2003)

    Article  MathSciNet  Google Scholar 

  35. Overbeek, R.A.: A new class of automated theorem-proving algorithms. J. ACM 21(2), 191–200 (1974)

    Article  MathSciNet  Google Scholar 

  36. Piotrowski, B., Urban, J.: ATPboost: learning premise selection in binary setting with ATP feedback. In: Galmiche, D., Schulz, S., Sebastiani, R. (eds.) IJCAR 2018. LNCS (LNAI), vol. 10900, pp. 566–574. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94205-6_37

    Chapter  Google Scholar 

  37. Polikar, R.: Ensemble based systems in decision making. IEEE Circuits Syst. Mag. 6(3), 21–45 (2006)

    Article  Google Scholar 

  38. Schäfer, S., Schulz, S.: Breeding theorem proving heuristics with genetic algorithms. In: Gottlob et al. [17], pp. 263–274

    Google Scholar 

  39. Schulz, S.: Learning search control knowledge for equational deduction. DISKI, vol. 230. Infix Akademische Verlagsgesellschaft (2000)

    Google Scholar 

  40. Schulz, S.: E - a brainiac theorem prover. AI Commun. 15(2–3), 111–126 (2002)

    MATH  Google Scholar 

  41. Schulz, S., Möhrmann, M.: Performance of clause selection heuristics for saturation-based theorem proving. In: Olivetti and Tiwari [33], pp. 330–345

    Google Scholar 

  42. Urban, J.: MPTP 0.2: design, implementation, and initial experiments. J. Autom. Reason. 37(1–2), 21–43 (2006)

    MATH  Google Scholar 

  43. Urban, J.: BliStr: the blind strategymaker. In: Gottlob et al. [17], pp. 312–319

    Google Scholar 

  44. Urban, J., Sutcliffe, G., Pudlák, P., Vyskočil, J.: MaLARea SG1 - machine learner for automated reasoning with semantic guidance. In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS (LNAI), vol. 5195, pp. 441–456. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71070-7_37

    Chapter  MATH  Google Scholar 

  45. Urban, J., Vyskočil, J., Štěpánek, P.: MaLeCoP machine learning connection prover. In: Brünnler, K., Metcalfe, G. (eds.) TABLEAUX 2011. LNCS (LNAI), vol. 6793, pp. 263–277. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22119-4_21

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Czech Technical University in Prague, Prague, Czech Republic

    Karel Chvalovský, Jan Jakubův, Martin Suda & Josef Urban

Authors
  1. Karel Chvalovský
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan Jakubův
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Martin Suda
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Josef Urban
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Karel Chvalovský .

Editor information

Editors and Affiliations

  1. University of Lorraine, Villers-lès-Nancy, France

    Pascal Fontaine

A Strategy \(\mathcal {S}\) from Experiments in Sect. 5

A Strategy \(\mathcal {S}\) from Experiments in Sect. 5

The following E strategy has been used to undertake the experimental evaluation in Sect. 5. The given clause selection strategy (heuristic) is defined using parameter “ ”.

figure c

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Chvalovský, K., Jakubův, J., Suda, M., Urban, J. (2019). ENIGMA-NG: Efficient Neural and Gradient-Boosted Inference Guidance for E. In: Fontaine, P. (eds) Automated Deduction – CADE 27. CADE 2019. Lecture Notes in Computer Science(), vol 11716. Springer, Cham. https://doi.org/10.1007/978-3-030-29436-6_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-29436-6_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-29435-9

  • Online ISBN: 978-3-030-29436-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation