Proceedings

Building Concise Logical Patterns by Constraining Tsetlin Machine Clause Size

Download BibTeX Cite

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. Main Track. Pages 3395-3403.

https://doi.org/10.24963/ijcai.2023/378

Abstract

Tsetlin Machine (TM) is a logic-based machine learning approach with the crucial advantages of being transparent and hardware-friendly. While TMs match or surpass deep learning accuracy for an increasing number of applications, large clause pools tend to produce clauses with many literals (long clauses). As such, they become less interpretable. Further, longer clauses increase the switching activity of the clause logic in hardware, consuming more power. This paper introduces a novel variant of TM learning -- Clause Size Constrained TMs (CSC-TMs) -- where one can set a soft constraint on the clause size. As soon as a clause includes more literals than the constraint allows, it starts expelling literals. Accordingly, oversized clauses only appear transiently. To evaluate CSC-TM, we conduct classification, clustering, and regression experiments on tabular data, natural language text, images, and board games. Our results show that CSC-TM maintains accuracy with up to 80 times fewer literals. Indeed, the accuracy increases with shorter clauses for TREC and BBC Sports. After the accuracy peaks, it drops gracefully as the clause size approaches one literal. We finally analyze CSC-TM power consumption and derive new convergence properties.

  1. [Abeyrathna et al., 2020a] K. Darshana Abeyrathna, Ole- Christoffer Granmo, and Morten Goodwin. Extending the Tsetlin Machine With Integer-Weighted Clauses for In- creased Interpretability. arXiv preprint arXiv:2005.05131, 2020.
  2. [Abeyrathna et al., 2020b] K. Darshana Abeyrathna, Ole- Christoffer Granmo, Rishad Shafik, Alex Yakovlev, Adrian Wheeldon, Jie Lei, and Morten Goodwin. A Novel Multi-Step Finite-State Automaton for Arbitrarily Deter- ministic Tsetlin Machine Learning. In the 40th Interna- tional Conference on Innovative Techniques and Applica- tions of Artificial Intelligence (SGAI-2020). Springer In- ternational Publishing, 2020.
  3. [Abeyrathna et al., 2020c] K. Darshana Abeyrathna, Ole- Christoffer Granmo, Xuan Zhang, Lei Jiao, and Morten Goodwin. The Regression Tsetlin Machine -A Novel Approach to Interpretable Non-Linear Regression. Philo- sophical Transactions of the Royal Society A, 378, 2020.
  4. [Abeyrathna et al., 2021] K. Darshana Abeyrathna, Bimal Bhattarai, Morten Goodwin, Saeed Gorji, Ole-Christoffer Granmo, Lei Jiao, Rupsa Saha, and Rohan K. Yadav. Mas- sively Parallel and Asynchronous Tsetlin Machine Archi- tecture Supporting Almost Constant-Time Scaling. In International Conference on Machine Learning (ICML), 2021.
  5. [Abouzeid et al., 2022] Ahmed Abouzeid, Ole-Christoffer Granmo, Morten Goodwin, and Christian Webersik. Label-Critic Tsetlin Machine: A Novel Self-supervised Learning Scheme for Interpretable Clustering. In Interna- tional Symposium on the Tsetlin Machine (ISTM), pages 41-48. IEEE, 2022.
  6. [Bakar et al., 2022a] Abu Bakar, Tousif Rahman, Alessan- dro Montanari, Jie Lei, Rishad Shafik, and Fahim Kawsar. Logic-based Intelligence for Batteryless Sensors. In the Annual International Workshop on Mobile Computing Sys- tems and Applications (HotMobile), pages 22-28. Associ- ation for Computing Machinery, 2022.
  7. [Bakar et al., 2022b] Abu Bakar, Tousif Rahman, Rishad Shafik, Fahim Kawsar, and Alessandro Montanari. Adap- tive Intelligence for Batteryless Sensors Using Software- Accelerated Tsetlin Machines. In the 20th Conference on Embedded Networked Sensor Systems. ACM, 2022.
  8. [Bhattarai et al., 2021] Bimal Bhattarai, Ole-Christoffer Granmo, and Lei Jiao. Measuring the novelty of natural language text using the conjunctive clauses of a Tsetlin machine text classifier. In International Conference on Agents and Artificial Intelligence, 2021.
  9. [Bhattarai et al., 2022a] Bimal Bhattarai, Ole-Christoffer Granmo, and Lei Jiao. Explainable Tsetlin Machine Framework for Fake News Detection with Credibility Score Assessment. In the 13th Conference on Language Resources and Evaluation, pages 4894-4903, 2022.
  10. [Bhattarai et al., 2022b] Bimal Bhattarai, Ole-Christoffer Granmo, and Lei Jiao. Word-level Human Interpretable Scoring Mechanism for Novel Text Detection Using Tsetlin Machines. Applied Intelligence, 52:17465-17489, 2022.
  11. [Bhattarai et al., 2023a] Bimal Bhattarai, Ole-Christoffer Granmo, and Lei Jiao. An interpretable knowledge repre- sentation framework for natural language processing with cross-domain application. In Advances in Information Re- trieval: 45th European Conference on Information Re- trieval, ECIR 2023, Dublin, Ireland, April 2-6, 2023, Pro- ceedings, Part I, pages 167-181, 2023.
  12. [Bhattarai et al., 2023b] Bimal Bhattarai, Ole-Christoffer Granmo, Lei Jiao, Rohan Yadav, and Jivitesh Sharma. Tsetlin Machine Embedding: Representing Words Using Logical Expressions. arXiv preprint arXiv:2301.00709, 2023.
  13. [Borgersen et al., 2022] Karl Audun Kagnes Borgersen, Morten Goodwin, and Jivitesh Sharma. A Comparison Between Tsetlin Machines and Deep Neural Networks in the Context of Recommendation Systems. arXiv preprint arXiv:2212.10136, 2022.
  14. [Chang et al., 2002] Eric Chang, Frank Seide, Helen M Meng, Zhuoran Chen, Yu Shi, and Yuk-Chi Li. A Sys- tem for Spoken Query Information Retrieval on Mobile Devices. IEEE Transactions on Speech and Audio pro- cessing, 10(8):531-541, 2002.
  15. [Dally et al., 2016] William J. Dally, Harting R. Curtis, and Tor M. Aamodt. Digital Design Using VHDL: a Systems Approach. Cambridge University Press, 2016.
  16. [Debole and Sebastiani, 2005] Franca Debole and Fabrizio Sebastiani. An analysis of the relative hardness of reuters- 21578 subsets. Journal of the American Society for Infor- mation Science and technology, 56(6):584-596, 2005.
  17. [Giri et al., 2022] Charul Giri, Ole-Christoffer Granmo, Herke Van Hoof, and Christian D. Blakely. Logic-based AI for Interpretable Board Game Winner Prediction with Tsetlin Machine. In 2022 International Joint Conference on Neural Networks (IJCNN), pages 1-9, 2022.
  18. [Glimsdal and Granmo, 2021] Sondre Glimsdal and Ole- Christoffer Granmo. Coalesced Multi-Output Tsetlin Machines with Clause Sharing. arXiv preprint, arXiv:2108.07594, 2021.
  19. [Glimsdal et al., 2022] Sondre Glimsdal, Rupsa Saha, Bi- mal Bhattarai, Charul Giri, Jivitesh Sharma, Svein Anders Tunheim, and Rohan Kumar Yadav. Focused Negative Sampling for Increased Discriminative Power in Tsetlin Machines. In 2022 International Symposium on the Tsetlin Machine (ISTM), pages 73-80, 2022.
  20. [Granmo et al., 2019] Ole-Christoffer Granmo, Sondre Glimsdal, Lei Jiao, Morten Goodwin, Christian W. Omlin, and Geir Thore Berge. The Convolutional Tsetlin Machine. arXiv preprint arXiv:1905.09688, 2019.
  21. [Granmo, 2018] Ole-Christoffer Granmo. The Tsetlin Ma- chine -A Game Theoretic Bandit Driven Approach to Op- timal Pattern Recognition with Propositional Logic. arXiv preprint arXiv:1804.01508, 2018.
  22. [Greene and Cunningham, 2006] Derek Greene and Pádraig Cunningham. Practical Solutions to the Problem of Diag- onal Dominance in Kernel Document Clustering. In Inter- national Conference on Machine Learning (ICML), pages 377-384. ACM Press, 2006.
  23. [Hendrickx et al., 2009] Iris Hendrickx, Su Nam Kim, Zor- nitsa Kozareva, Preslav Nakov, Diarmuid Ó Séaghdha, Sebastian Padó, Marco Pennacchiotti, Lorenza Romano, and Stan Szpakowicz. Semeval-2010 task 8: Multi-way classification of semantic relations between pairs of nom- inals. In the Workshop on Semantic Evaluations: Recent Achievements and Future Directions, pages 94-99. Asso- ciation for Computational Linguistics, 2009.
  24. [Jiao et al., 2021] Lei Jiao, Xuan Zhang, and Ole-Christoffer Granmo. On the Convergence of Tsetlin Machines for the AND and the OR Operators. arXiv preprint https://arxiv.org/abs/2109.09488, 2021. Link
  25. [Jiao et al., 2023] Lei Jiao, Xuan Zhang, Ole-Christoffer Granmo, and K. Darshana Abeyrathna. On the Conver- gence of Tsetlin Machines for the XOR operator. IEEE Transactions on Pattern Analysis and Machine Intelli- gence, 45(5):6072-6085, 2023.
  26. [Lei et al., 2021] Jie Lei, Tousif Rahman, Rishad Shafik, Adrian Wheeldon, Alex Yakovlev, Ole-Christoffer Granmo, Fahim Kawsar, and Akhil Mathur. Low-Power Audio Keyword Spotting Using Tsetlin Machines. Journal of Low Power Electronics and Applications, 11, 2021.
  27. [Liang and Van den Broeck, 2019a] Yitao Liang and Guy Van den Broeck. Learning logistic circuits. In Proceedings of the 33rd Conference on Artificial Intelligence (AAAI), jan 2019.
  28. [Liang and Van den Broeck, 2019b] Yitao Liang and Guy Van den Broeck. Learning logistic circuits. In the AAAI Conference on Artificial Intelligence, volume 33, pages 4277-4286, 2019.
  29. [Maas et al., 2011] Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning Word Vectors for Sentiment Analysis. In the 49th Annual Meeting of the Association for Computational Lin- guistics: Human Language Technologies, pages 142-150, 2011.
  30. [Maheshwari et al., 2023] Sidharth Maheshwari, Tousif Rahman, Rishad ShafikSenior member, Alex Yakovlev, Ashur Rafiev, Lei Jiao, and Ole-Christoffer Granmo. Re- dress: Generating compressed models for edge inference using tsetlin machines. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1-16, 2023.
  31. [Saha et al., 2021] Rupsa Saha, Ole-Christoffer Granmo, and Morten Goodwin. Using Tsetlin Machine to Discover Interpretable Rules in Natural Language Processing Ap- plications. Expert Systems, page e12873, 2021.
  32. [Saha et al., 2022] Rupsa Saha, Ole-Christoffer Granmo, Vladimir Zadorozhny, and Morten Goodwin. A Relational Tsetlin Machine with Applications to Natural Language Understanding. Journal of Intelligent Information Sys- tems, 2022.
  33. [Seraj et al., 2022] Raihan Seraj, Jivitesh Sharma, and Ole Christoffer Granmo. Tsetlin Machine for Solving Contextual Bandit Problems. In Neural Information Pro- cessing Systems (NeurIPS), 2022.
  34. [Sharma et al., 2023] Jivitesh Sharma, Rohan Kumar Yadav, Ole-Christoffer Granmo Granmo, and Lei Jiao. Drop Clause: Enhancing Performance, Robustness and Pattern Recognition Capabilities of the Tsetlin Machine. In the AAAI Conference on Artificial Intelligence (AAAI), 2023.
  35. [Tsetlin, 1961] Michael Lvovitch Tsetlin. On Behaviour of Finite Automata in Random Medium. Avtomat. i Tele- mekh, 22(10):1345-1354, 1961.
  36. [Valiant, 1984] Leslie G Valiant. A Theory of the Learnable. Communications of the ACM, 27(11):1134-1142, 1984.
  37. [Wheeldon et al., 2020] Adrian Wheeldon, Rishad Shafik, Tousif Rahman, Jie Lei, Alex Yakovlev, and Ole- Christoffer Granmo. Learning Automata based Energy- efficient AI Hardware Design for IoT. Philosophical Transactions of the Royal Society A, 2020.
  38. [Yadav et al., 2021a] Rohan Yadav, Lei Jiao, Ole-Christoffer Granmo, and Morten Goodwin. Enhancing interpretable clauses semantically using pretrained word representation. In the 4th BlackboxNLP Workshop on Analyzing and In- terpreting Neural Networks for NLP, 2021.
  39. [Yadav et al., 2021b] Rohan Yadav, Lei Jiao, Ole-Christoffer Granmo, and Morten Goodwin. Human-Level Inter- pretable Learning for Aspect-Based Sentiment Analysis. In the AAAI Conference on Artificial Intelligence (AAAI), 2021.
  40. [Yadav et al., 2022] Rohan Kumar Yadav, Lei Jiao, Ole Christoffer Granmo, and Morten Goodwin. Ro- bust Interpretable Text Classification against Spurious Correlations Using AND-rules with Negation. In Interna- tional Joint Conference on Artificial Intelligence (IJCAI), 2022. IJCAI
  41. [Zhang et al., 2022] Xuan Zhang, Lei Jiao, Ole-Christoffer Granmo, and Morten Goodwin. On the Convergence of Tsetlin Machines for the IDENTITY-and NOT Operators. IEEE Transactions on Pattern Analysis and Machine Intel- ligence, 44(10):6345-6359, 2022.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards