Skip navigation
Return to
Colloquia & Seminar listing.
Learning Circuits and Networks with Value Injection Queries |
| Distinguished Lecturer |
| Speaker: | Dana Angluin |
| Location: | 1065 Kemper Hall |
| When: | 2010-04-01 15:10:00 |
| Host: | Dan Gusfield |
We survey results on algorithms to learn Boolean,
analog and probabilistic circuits using value injection
queries. A value injection query is a kind of enhanced
membership query, in which we may control the values
on interior wires, as well as on input wires of the circuit,
but still may only observe the values on output wire(s)
of the circuit. This type of query is inspired by the
capabilities of gene suppression and gene over-expression
in studying the structure of gene regulatory networks.
We consider the theoretical power of such queries in
learning Boolean circuits, where we give polynomial
time algorithms to learn circuits with bounded fan-in
and logarithmic depth, as well as unbounded fan-in
constant depth circuits over AND, OR and NOT.
For analog circuits, a topological parameter, the
shortcut width of the circuit, turns out to be a
key to its efficient learnability. For probabilistic
circuits (equivalently, Bayesian networks) we can
generalize the Boolean case for 0/1 values, but we also
encounter novel phenomena. Models of social networks
are an interesting case of probabilistic circuits.
|
|
