Principal Investigator Cynthia Rudin
Project Website http://www.nsf.gov/awardsearch/showAward.do?AwardNumber=1053407
Project Start Date September 2011
Project End Date August 2017
In numerous industries, decisions are based on large amounts of data, where a ranked list of possible actions determines how limited resources will be spent. Over the last decade, machine learning algorithms for ranking have been designed to address prioritization problems. These algorithms rank a set of objects according to the probability to possess a certain attribute; for example, we might rank a set of manholes in order of their probability to catch fire next year. However, current algorithms solve ranking problems approximately rather than exactly, and these approximate algorithms can be slow; furthermore they do not take into account many application-specific problems.
The goals of this project include:
(1) Finding exact solutions to ranking problems by developing a toolbox of algorithmic techniques based on mixed-integer optimization technology.
(2) Finding solutions faster by showing a fundamental equivalence of ranking problems to easier classification problems that can be solved an order of magnitude faster.
(3) Developing frameworks for new structured problems. The first framework pertains to ranking problems that have a graph structure that are relevant to the energy domain. The second framework handles a sequential prediction problem arising from recommender systems, with applications also in the medical domain.
Through collaboration with industry, the proposed methods are being applied in several different areas, including the prevention of serious events (fires and explosions) on NYC's electrical grid.