On Bounding the Behavior of a Neuron

Abstract

A neuron with binary inputs and a binary output represents a Boolean function. Our goal is to extract this Boolean function into a tractable representation that will facilitate the explanation and formal verification of a neuron's behavior. Unfortunately, extracting a neuron's Boolean function is in general an NP-hard problem. However, it was recently shown that prime implicants of this Boolean function can be enumerated efficiently, with only polynomial time delay. Building on this result, we propose a best-first search algorithm that is able to incrementally tighten inner and outer bounds of a neuron's Boolean function. These bounds correspond to truncated prime-implicant covers of the Boolean function. We provide two case studies that highlight our ability to bound the behavior of a neuron.