On Training Neurons with Bounded Compilations

<p>Knowledge compilation offers a formal approach to explaining and verifying the behavior of machine learning systems, such as neural networks. Unfortunately, compiling even an individual neuron into a tractable representation such as an Ordered Binary Decision Diagram (OBDD), is an NP-hard problem. In this thesis, we consider the problem of training a neuron from data, subject to the constraint that it has a compact representation as an OBDD. Our approach is based on the observation that a neuron can be compiled into an OBDD in polytime if (1) the neuron has integer weights, and (2) its aggregate weight is bounded. Unfortunately, we first show that it is also NP-hard to train a neuron, subject to these two constraints. On the other hand, we show that if we train a neuron generatively, rather than discriminatively, a neuron with bounded aggregate weight can be trained in pseudo-polynomial time. Hence, we propose the first efficient algorithm for training a neuron that is guaranteed to have a compact representation as an OBDD. Empirically, we show that our approach can train neurons with higher accuracy and more compact OBDDs.</p>

Name thesis:degree_name

Master of Science in Computer Science (MSCS)

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Year dc:date.available

2023

Author dc:creator

• Kennedy, Lance

Contributors dc:contributor

• Arthur Choi
• Jiho Noh

• Artificial Intelligence
• Machine Learning
• XAI
• OBDD
• Knowledge Compilation
• Artificial Intelligence and Robotics

Repository record dc:identifier

https://digitalcommons.kennesaw.edu/cs_etd/58

OAI identifier oai:identifier

oai:digitalcommons.kennesaw.edu:cs_etd-1063