Searching for the Rare

ABSTRACT Application Number: 2017723 (BSF); 1815559 (NSF) CCF-BSF:CIF:Small: Searching for the Rare: An Active Inference and Learning Approach Qing Zhao, Cornell University Kobi Cohen, Ben-Gurion University of the Negev Project overview: This research is concerned with the general problem of searching for a small amount of extremely useful information in a deluge of data quickly and reliably.

Example applications are detecting anomalies and extreme events over internet traffic flows, or computer system execution logs, detecting frauds in financial transaction records, identifying opportunities for transmission in adaptive communication networks, and various social-economic applications.

Regardless of the application domain, the problem of searching for the rare has the following properties: (i) the massive search space; (ii) the need for reliable inference; (iii) the lack of prior knowledge on the stochastic model of the rare events; (iv) the time sensitivity of the problem, either due to the transient nature of opportunities or the urgency for taking recourse measures in the face of anomalies. The performance measures of interest are sample complexity (e.g., detection time, number of iterations) and computational complexity with respect to the size of the search space, the required detection accuracy, and the available prior information on the rare events.

Broader impacts: Searching and learning in high dimension are particularly relevant in the era of increasing network size and abundance of data. From a long-term theoretical tools perspective, this research will contribute to advances in areas of signal processing, communications, applied probability, stochastic optimization, and machine learning. In practice, this research provides practical solutions to a broad range of emerging applications, such as searching for anomalies, trends and extreme events in network traffic data, financial transaction data, computer system execution logs, etc. On the educational front, the multidisciplinary nature of this research provides rich experience for graduate students and enriches undergraduate curriculum. The international collaboration among the project team members facilitates knowledge dissemination.