Bayesian networks are an attractive modeling tool for human sensing, as they combine an intuitive graphical representation with efficient algorithms for inference and learning. Earlier work has demonstrated that boosted parameter learning could be used to improve the performance of Bayesian network classifiers for complex multi-modal inference problems such as speaker detection. In speaker detection, the goal is to use video and audio cues to infer when a person is speaking to a user interface. In this paper we introduce a new boosted structure learning algorithm based on AdaBoost. Given labeled data, our algorithm modifies both the network structure and parameters so as to improve classification accuracy. We compare its performance to both standard structure learning and boosted parameter learning on a fixed structure. We present results for speaker detection and for the UCI "chess" dataset.