Learning from Interdependent Examples

University Of Washington, Seattle WA

Investigators

Abstract

This project investigates machine learning that takes into account dependencies among examples. In contrast, most machine learning methods assume that all examples are independent and identically distributed ("i.i.d."). Domains where this assumption does not hold are widespread -- from the WWW, where the relevance of a page affects the relevance of linked pages, to molecular biology, where a protein's properties determine its role in metabolic networks. By lifting the i.i.d. assumption, this project will develop learning algorithms that can exploit the information each example carries about the others. This has the potential to improve predictive performance and broaden the range of phenomena that can be effectively modeled. However, it also greatly increases the complexity of learning. This project focuses on developing techniques to make non-i.i.d. learning practical, including: (1) feature search guided by known relations among examples; (2) aggregation of variable quantities of relevant information back into examples of fixed length; (3) increasing the efficiency of learning and inference by performing them at multiple levels of abstraction; and (4) using relational domain knowledge to constrain the search space and combat overfitting. The project will apply the resulting algorithms to modeling the WWW and scientific citation networks. The broader impact of this project includes extension of machine learning to domains, within and beyond computer science, where interdependencies among examples cannot be ignored (e.g., the WWW, social networks, ubiquitous computing). It will also create a publicly available repository of data sets with interdependent examples. The project involves undergraduates, particularly those from underrepresented groups.