Computer Science Seminar
Yi Huang
UIC
On Budgeted Prediction and Network Inference
Abstract: This talk will consist of two separate topics.
In the first part, we consider the problem of feature-efficient prediction, a setting where features have costs and the learner is limited by a budget constraint on the total cost of the features it can examine in test time. We focus on solving this problem with boosting by optimizing the choice of base learners in the training phase We provide both theoretical and experimental justifications for our optimization methods. This part is based on work with Brian Powers and Lev Reyzin.
In the second part, we investigate how to reconstruct social networks from voting data. We study two plausible voting models, one edge-centric and the other vertex-centric. For these models, we give algorithms and lower bounds, and we also test our algorithms on United States Senate data. Despite the similarity of the two models, we show that their respective network recovery problems differ in complexity and involve distinct algorithmic challenges. Our results indicate that great care should be exercised when choosing a voting model for network recovery tasks. This is based on work with Ben Fish and Lev Reyzin.
Monday April 3, 2017 at 2:00 PM in SEO 612