CSAIL Event Calendar: Previous Series

Networks of Relations for Representation, Inference, and Learning

Speaker: Dr. Matthew Cook , California Institute of Technology
Date: March 13 2006
Time: 4:00PM to 5:00PM
Location: 32-G449 Patil/Kiva
Host: Prof. Daniela Rus, CSAIL

Many cases where brains currently outperform computers can be understood in terms of relational processing, where rather than imposing a feed-forward flow from inputs toward outputs, instead every value is both an input and an output, with information flowing in all directions. Visual understanding, pattern recognition, and sensor-motor control provide examples of this phenomenon. Whereas a function specifies the values of the output variable given values for the input variables, a relation generalizes this notion to specify simply a set of allowable value tuples, without any fixed assignment of inputs or outputs. Although we are experts in how to combine very simple functions (such as AND gates and NOT gates) to build machines with amazing calculational capabilities, in contrast we do not yet have a good understanding of how simple relations (such as A-MAJORITY- OF-VALUES-ARE-ONE or ALL-VALUES-ARE-EQUAL) can efficiently and reliably be combined to take us from a low level to a high level representation. It is my belief that such an understanding will allow the development of techniques to compose relations on a large scale, enabling us to build machines that can reason as well as our contemporary machines can calculate. In this direction, we need to establish fundamental results for composition of basic relations to implement larger relations, paralleling fundamental results for circuit composition. I will present decidability and undecidability results for implementability among discrete relations. (These results also lead to other work showing that stochastic chemical reaction networks are capable of performing uniform computation with only a polynomial time slowdown compared to Turing machines.)

Inference in relational networks is similar to methods for constraint satisfaction problems (CSPs) and belief propagation. But in contrast with belief propagation networks, relational networks always converge to a well-defined state even on graphs with cycles. And in contrast with CSPs, relational networks allow fuzzy representations of values, useful for interpolation and inference on continuous values. I will show a learning rule that allows fuzzy relations in a network to learn what form they should take so that the network will implement an arbitrary relationship, with applications to physical control problems.

See other events that are part of CS Special Seminar Series Spring 2006

See other events happening in March 2006