IID Relaxation by Logical Expressivity: A Research Agenda for Fitting Logics to Neurosymbolic Requirements
Pages 3 - 13
Abstract
Neurosymbolic background knowledge and the expressivity required of its logic can break Machine Learning assumptions about data Independence and Identical Distribution. In this position paper we propose to analyze IID relaxation in a hierarchy of logics that fit different use case requirements. We discuss the benefits of exploiting known data dependencies and distribution constraints for Neurosymbolic use cases and argue that the expressivity required for this knowledge has implications for the design of underlying ML routines. This opens a new research agenda with general questions about Neurosymbolic background knowledge and the expressivity required of its logic.
References
[1]
Ahmed, K., et al.: Semantic loss functions for neuro-symbolic structured prediction (2024)
[2]
Andréka H, Németi I, and van Benthem J Modal languages and bounded fragments of predicate logic J. Philos. Log. 1998 27 3 217-274
[3]
Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The description logic handbook: theory, implementation, and applications. Cambridge University Press (2003). http://dblp.uni-trier.de/db/conf/dlog/handbook2003.html
[4]
van Bekkum M, de Boer M, van Harmelen F, Meyer-Vitali A, and Teije A Modular design patterns for hybrid learning and reasoning systems Appl. Intell. 2021 51 9 6528-6546
[5]
Besold, T.R., et al.: Neural-symbolic learning and reasoning: a survey and interpretation (2017)
[6]
Bishop, C.M.: Pattern Recognition and Machine Learning (Information Science and Statistics). Springer, 1 edn. (2007)
[7]
Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. No. 53 in Cambridge Tracts in Theoretical Computer Science, Cambridge University Press (2001)
[8]
Bottou, L., Curtis, F.E., Nocedal, J.: Optimization methods for large-scale machine learning (2016). https://arxiv.org/abs/1606.04838
[9]
Bárány, V., Gottlob, G., Otto, M.: Querying the guarded fragment. Logical Methods Comput. Sci. 10(2) (2014). https://lmcs.episciences.org/675
[10]
Casella, G., Berger, R.: Statistical Inference. Duxbury Resource Center (June 2001)
[11]
Casteels, W., Hellinckx, P.: Exploiting non-IID. data towards more robust machine learning algorithms (2020)
[12]
Cate, B., Franceschet, M.: Guarded fragments with constants (2005). https://link.springer.com/article/10.1007/s10849-005-5787-x
[13]
Ciampiconi, L., Elwood, A., Leonardi, M., Mohamed, A., Rozza, A.: A survey and taxonomy of loss functions in machine learning (2023). https://arxiv.org/abs/2301.05579
[14]
Darrell T, Kloft M, Pontil M, Rätsch G, and Rodner EMachine learning with interdependent and non-identically distributed data (Dagstuhl Seminar 15152)Dagstuhl Rep.20155418-55https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.4.18
[15]
Dehghani, M., et al.: The benchmark lottery (2021)
[16]
Dundar, M., Krishnapuram, B., Bi, J., Rao, R.B.: Learning classifiers when the training data is not IID. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence, pp. 756–761. IJCAI’07, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2007)
[17]
Frick M and Grohe M The complexity of first-order and monadic second-order logic revisited Ann. Pure Appl. Logic 2004 130 1 3-31
[18]
Fu L, Zhang H, Gao G, Zhang M, and Liu X Client selection in federated learning: principles, challenges, and opportunities IEEE Internet Things J. 2023 10 24 21811-21819
[19]
d’Avila Garcez, A., Lamb, L.C.: Neurosymbolic AI: The 3rd wave (2020). https://arxiv.org/abs/2012.05876
[20]
Gutin, G., Yeo, A.: parameterized constraint satisfaction problems: a survey. In: Krokhin, A., Zivny, S. (eds.) The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups, vol. 7, pp. 179–203. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2017).
[21]
Haller, M., Lenz, C., Nachtigall, R., Awaysheh, F., Alawadi, S.: Handling non-IID data in federated learning: an experimental evaluation towards unified metrics (2023).
[22]
He, Y., Shen, Z., Cui, P.: Towards non-I.I.D. image classification: a dataset and baselines. Pattern Recogn. 110, 107383 (2021)
[23]
Horrocks, I., Patel-Schneider, P.F., McGuinness, D.L., Welty, C.A.: OWL: A Description-Logic-Based Ontology Language for the Semantic Web, pp. 458–486 Cambridge University Press (2007)
[24]
Hustadt, U., Schmidt, R.A., Georgieva, L.: A survey of decidable first-order fragments and description logics (2004). http://citeseer.ist.psu.edu/hustadt04survey.html
[25]
Johnson, J., Hariharan, B., van der Maaten, L., Fei-Fei, L., Zitnick, C.L., Girshick, R.: CLEVR: a diagnostic dataset for compositional language and elementary visual reasoning (2017). https://openaccess.thecvf.com/content_cvpr_2017/html/Johnson_CLEVR_A_Diagnostic_CVPR_2017_paper.html
[26]
Krspstzsch, M., Simancik, F., Horrocks, I.: A description logic primer (2012). https://arxiv.org/abs/1201.4089
[27]
Li, Q., Huang, S., Hong, Y., Chen, Y., Wu, Y.N., Zhu, S.C.: Closed loop neural-symbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning (2020). http://proceedings.mlr.press/v119/li20f.html
[28]
Li, Y., Oliva, J.B.: Partially observed exchangeable modeling (2021). https://arxiv.org/abs/2102.06083
[29]
Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T., De Raedt, L.: DeepProbLog: Neural probabilistic logic programming. In: Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 31. Curran Associates, Inc. (2018). https://proceedings.neurips.cc/paper_files/paper/2018/file/dc5d637ed5e62c36ecb73b654b05ba2a-Paper.pdf
[30]
Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T., De Raedt, L.: DeepProbLog: neural probabilistic logic programming. In: Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Adv. Neural Inf. Process. Syst. 31. Curran Associates, Inc. (2018). https://proceedings.neurips.cc/paper_files/paper/2018/file/dc5d637ed5e62c36ecb73b654b05ba2a-Paper.pdf
[31]
Marra G, Dumančić S, Manhaeve R, and De Raedt L From statistical relational to neurosymbolic artificial intelligence: a survey Artif. Intell. 2024 328 https://www.sciencedirect.com/science/article/pii/S0004370223002084
[32]
Morra, L., et al.: Designing logic tensor networks for visual sudoku puzzle classification. In: d’Avila Garcez, A.S., Besold, T.R., Gori, M., Jiménez-Ruiz, E. (eds.) Proceedings of the 17th International Workshop on Neural-Symbolic Learning and Reasoning, La Certosa di Pontignano, Siena, Italy, July 3-5, 2023. CEUR Workshop Proceedings, vol. 3432, pp. 223–232. CEUR-WS.org (2023). https://ceur-ws.org/Vol-3432/paper19.pdf
[33]
Mossakowski, T.: Modular design patterns for neural-symbolic integration: refinement and combination (2022). https://arxiv.org/abs/2206.04724
[34]
Ott, J., Ledaguenel, A., Hudelot, C., Hartwig, M.: How to think about benchmarking neurosymbolic AI? In: d’Avila Garcez, A.S., Besold, T.R., Gori, M., Jiménez-Ruiz, E. (eds.) Proceedings of the 17th International Workshop on Neural-Symbolic Learning and Reasoning, La Certosa di Pontignano, Siena, Italy, July 3-5, 2023. CEUR Workshop Proceedings, vol. 3432, pp. 248–254. CEUR-WS.org (2023). https://ceur-ws.org/Vol-3432/paper22.pdf
[35]
Pratt-Hartmann, I.: Complexity of the guarded two-variable fragment with counting quantifiers (2006)
[36]
Pratt-Hartmann, I.: Introduction. In: Fragments of First-Order Logic. Oxford University Press (03 2023. https://doi.org/10.1093/oso/9780192867964.003.0001
[37]
Prince, S.J.: Understanding deep learning. MIT Press (2023)
[38]
Rabanser, S., Günnemann, S., Lipton, Z.C.: Failing loudly: an empirical study of methods for detecting dataset shift (2018). https://arxiv.org/abs/1810.11953
[39]
Samer, M., Szeider, S.: Fixed-parameter tractability. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability - Second Edition, Frontiers in Artificial Intelligence and Applications, vol. 336, pp. 693–736. IOS Press (2021)., https://doi.org/10.3233/FAIA201000
[40]
Schlichtkrull, M., Kipf, T.N., Bloem, P., van den Berg, R., Titov, I., Welling, M.: Modeling relational data with graph convolutional networks (2017). https://arxiv.org/abs/1703.06103
[41]
Schspslkopf, B., et al.: Towards causal representation learning (2021). https://arxiv.org/abs/2102.11107
[42]
Shi, Y., Li, W., Gao, Y., Cao, L., Shen, D.: Beyond IID: learning to combine non-IID metrics for vision tasks. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 31(1) (2017)., https://ojs.aaai.org/index.php/AAAI/article/view/10748
[43]
Steinwart, I., Hush, D., Scovel, C.: Learning from dependent observations (2009). https://www.sciencedirect.com/science/article/pii/S0047259X08001097
[44]
Tan, Y., Liu, Y., Long, G., Jiang, J., Lu, Q., Zhang, C.: Federated learning on non-IID graphs via structural knowledge sharing (2023). https://doi.org/10.1609/aaai.v37i8.26187
[45]
Thompson, N.C., Greenewald, K., Lee, K., Manso, G.F.: The computational limits of deep learning (2020). https://arxiv.org/abs/2007.05558
[46]
Wang, Q., Ma, Y., Zhao, K., Tian, Y.: A comprehensive survey of loss functions in machine learning (2020). https://link.springer.com/article/10.1007/s40745-020-00253-5
[47]
Xu, J., Zhang, Z., Friedman, T., Liang, Y., Broeck, G.: A semantic loss function for deep learning with symbolic knowledge (2018). http://proceedings.mlr.press/v80/xu18h.html
[48]
Zhang, T., Dai, J., Song, W., Zhao, R., Zhang, B.: Oslpnet: a neural network model for street lamp post extraction from street view imagery. Expert Syst. Appl. 231, 120764 (2023). https://www.sciencedirect.com/science/article/pii/S0957417423012666
[49]
Zhu, H., Xu, J., Liu, S., Jin, Y.: Federated learning on non-IID data: a survey. Neurocomput. 465(C), 371–390 (2021).
Index Terms
- IID Relaxation by Logical Expressivity: A Research Agenda for Fitting Logics to Neurosymbolic Requirements
Index terms have been assigned to the content through auto-classification.
Recommendations
Expressivity of Imperfect Information Logics without Identity
In this article we investigate the family of independence-friendly (IF) logics in the equality-free setting, concentrating on questions related to expressive power. Various natural equality-free fragments of logics in this family translate into ...
Expressivity of coalgebraic modal logic: The limits and beyond
Modal logic has a good claim to being the logic of choice for describing the reactive behaviour of systems modelled as coalgebras. Logics with modal operators obtained from so-called predicate liftings have been shown to be invariant under behavioural ...
Three-valued Logics in Modal Logic
Every truth-functional three-valued propositional logic can be conservatively translated into the modal logic S5. We prove this claim constructively in two steps. First, we define a Translation Manual that converts any propositional formula of any three-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2024
356 pages
ISBN:978-3-031-71169-5
DOI:10.1007/978-3-031-71170-1
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 10 September 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Nov 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in