Bayes Chip

(Thanks to Matt Swayne for alerting me to this news item)
(Photo: D-Wave’s Rainier Chip with picture of Reverend Thomas Bayes superimposed. This picture of Bayes, although well-known, is probably not really him.

Good news for Bayesian Network fans. A company called Lyric Semicondutors is producing a new chip and accompanying software which appears to be designed specifically for doing Bayesian net calculations.

In general, doing inference with a Bayesian network is NP-hard. Software like Netica and Hugin use an exact algorithm invented by Lauritzen and Spiegelhalter in 1988. The L&S algorithm is pretty fast, but still NP-hard. Therefore, for large networks, the L&S algorithm crawls to a halt, and one uses instead an approximate algorithm such as Gibbs sampling. For example, the software WinBUGS is a Gibbs sampler for doing inference with Bayesian nets. Kevin Murphy keeps a nice list of existing Bayesian Network software.

BNet calculations can be done with conventional chips, but according to Lyric’s website, Lyric’s LEC Core chip can achieve 30X reduction in area and 10X reduction in power consumption (with respect to what conventional chip and for what specific benchmark problem? They don’t say.)

According to Lyric’s Aug 17,2010 press release: “Lyric Semiconductor is a fabless semiconductor company founded in 2006 by MIT Ph.D. Ben Vigoda and semiconductor industry veteran David Reynolds, and is located in Cambridge, Mass. Lyric’s probability processing technology was first envisioned by Vigoda at MIT. Lyric’s lead investor and chairman of the board is Ray Stata, founder and 30-plus year CEO of Analog Devices and lead partner of Stata Venture Partners. Lyric currently employs 30 people and has received more than $20 million in government funding from DARPA and other agencies and venture investment from Stata Venture Partners. Lyric Semiconductor maintains a growing IP portfolio of 50 fundamental patent filings in the field of probability processing.”

So far, Lyric is only selling a LEC (Lyric Error Correction) chip for correcting errors made by flash memory chips. However, they’ve promised to start selling by 2013 a general purpose chip called GP5. The GP5 will be programmable in a language called PSBL (It looks to me like an abbreviation for “pissable”, but it’s actually an acronym for Probability Synthesizes to Bayesian Logic)

Ben Vigoda’s MIT Ph.D. Thesis, entitled “Analog Logic: Continuous-Time Analog Circuits for Statistical Signal Processing” can be found here.

According to Ben Vigoda, his Bayes chips are poised to become ubiquitous in this age of large data sets which beg for statistical analysis. A burning question in many people’s minds is how will Intel respond to this challenge to their chip hegemony. Will they roll out their own Bayes chip? But how can they sidestep Lyric’s 50 patents?

Lyric’s chips are definitely a cool technology. But how do they compare with quantum computers? Too early to tell precisely, but let me speculate. On the plus side, and it’s a very big plus, Lyric’s technology is already commercially available (or nearly so) and very portable. Current QCs don’t have as many qubits as one would like to have and are not very portable. On the minus side, I suspect that D-Wave’s adiabatic quantum computer, and gate model quantum computers, once those are available for a large number of qubits, will be more efficient than Lyric’s chip when doing similar calculations.

Lyric’s chips are analog computers that use room temperature wires and irreversible computation. Quantum computers, on the other hand, use superconductivity and reversible chips, so they produce less heat and probably use less power when doing similar “very large” calculations.

But more importantly, Lyric’s chips are classical computers, not quantum computers; there are good reasons to believe that quantum computers are typically quadratically faster (in a time-complexity sense) than classical computers when doing probabilistic sampling and optimization.

In my opinion, quantum computer are a more “natural” way to handle probabilistic calculations. Quantum computers harness quantum mechanics, which has true randomness built into it. By comparison, Lyric’s chip is deep down just another deterministic chip using pseudo-random numbers.