|
MLFL Wiki |
Main /
Learning Hidden Graphs And Circuits With Query AccessConsider the problem of discovering some hidden object; the learner can perform certain costly experiments (or queries) to obtain information about the object, with the goal of learning its entire structure with as few such queries as possible. In this talk we consider the problem of learning hidden graphs and circuits given query access to them. We explain the value injection query model for learning hidden circuits and present some results on the learnability of boolean and analog circuits. We also compare the power of various queries for learning hidden graphs. In particular, we discuss learning graphs with shortest path, edge counting, and edge detecting queries. We also introduce the task of graph verification and examine when verifying is easier than learning. Finally, we look at the relationship between graph verification and matrix fingerprinting. All of the models we consider are motivated by real-world problems, mainly from bioinformatics. |