
Joseph S. FriedmanStochastic Bayesian InferenceBayesian inference is a powerful approach for integrating independent conflicting information for decisionmaking and robotics, performed with limited efficiency by generalpurpose computers. Excitingly, Bayesian inference can be performed extremely efficiently through stochastic computing with Muller Celements. This faulttolerant circuit structure enables naive Bayesian inference with multiple orders of magnitude decrease in AEDP.CElement Bayesian InferenceThe Muller Celement, characterized by the truth table below is a twoinput memory element composed of eight transistors. The output Z maintains its state Z_{prev} unless both inputs X and Y are opposite the current output state, in which case the output switches to the shared input value.For Celement input signals with no autocorrelation, the output probability is given by the equation below. This equation is equivalent to an inference based on Bayes' rule, demonstrating that with stochastic computing, a simple Celement performs a complete Bayesian inference. Example: Naive Bayesian Spam FilterMultiple Celements can be cascaded to perform complex inferences incorporating numerous independent sources of information. This extends the stochastic inference described above, enabling the fusion of evidence inputs E_{i} to determine the probability of an event V. Spam filtering illustrates the capability of cascaded Celements to perform a canonical Bayesian inference. Consider the messages in the table below: A and B are likely to be ham (i.e., not spam), C is almost definitely spam, D seems to be ham but contains many words that are associated with spam, E is probably spam, and F is entirely ambiguous. To infer the probability that a message is spam, a simple Bayesian spam filter considers the "spamicity" of key words in a message.The threestage Celement tree above can be used to perform the spam filter operation on messages AF for eight key words. The simulation results show that for increasingly long stochastic bitstreams, the stochastic circuit computes probabilities (dots) that approach the exact naive Bayesian inference (solid line). This simple Bayesian system successfully filters the messages, with high outputs for message C and E, low outputs for messages A, B, and D, and an ambiguous output for F.
Efficiency & Fault ToleranceThe primary benefits of this stochastic inference structure are exceptional efficiency and fault tolerance for applications that do not require exact solutions. For an output KL divergence of 0.01 (sufficient accuracy for some practical applications), the stochastic inference circuit provides a areaenergydelay product (AEDP) decrease by a factor of nearly one billion! The system is also extremely robust to faults, providing nearly perfect results for stuckat fault rates of nearly 100%.
Related Publications
